Geometric Modeling - Explicit - Implicit Representations
Geometric Modeling - Explicit - Implicit Representations
Geometric Modeling - Explicit - Implicit Representations
• Surface representations
– Explicit vs. Implicit
• Explicit representations
– Triangle meshes
• Implicit representations
– Signed distance fields
• Conversions
– Explicit Implicit
2
Explicit vs. Implicit
T
• Explicit: f (x) = (r cos(x), r sin(x))
– Range of parametrization function
f ([0, 2π])
� F (x, y) < 0
• Implicit: F (x, y) = x2 + y 2 − r
– Kernel of implicit function
F (x, y) = 0
F (x, y) > 0
3
Explicit vs. Implicit
T
• Explicit: f (x) = (r???
cos(x), r sin(x))
– Range of parametrization function
– Piecewise approximation!
�
• Implicit: F (x, y) = ???
x2 + y 2 − r
– Kernel of implicit function
– Piecewise approximation!
4
Explicit vs. Implicit
• Explicit:
– Range of parametrization function
– Piecewise approximation!
– E.g. splines, triangle mesh
– Easy enumeration
– Easy geometry modification
• Implicit:
– Kernel of implicit function
– Piecewise approximation!
– E.g. scalar-valued 3D grid
– Easy in/out test
– Easy topology modification (CSG)
5
Overview
• Surface representations
– Explicit vs. Implicit
• Explicit representations
– Triangle meshes
• Implicit representations
– Signed distance fields
• Conversions
– Explicit Implicit
6
Polynomial Approximation
• Issues
– smoothness of the target data ( maxt f (p+1)(t) )
– smoothness conditions between segments
7
Spline Surfaces
8
Spline Surfaces
• Topological constraints
– Rectangular patches
– Regular control mesh
• Geometric constraints
– Large number of pathes
– Continuity between patches
– Trimming
9
Last Time
– approximation O(h2)
– arbitrary topology
– adaptive refinement
– efficient rendering
10
Triangle Meshes
11
Triangle Meshes
• Euler-Poincaré formula
|V| − |E| + |F| = 2(1 − g)
• Mesh statistics
– |F| ≈ 2 · |V|
– |E| ≈ 3 · |V|
– Avg. valence ≈ 6
12
Overview
• Surface representations
– Explicit vs. Implicit
• Explicit representations
– Triangle meshes
• Implicit representations
– Signed distance fields
• Conversions
– Explicit Implicit
13
Implicit Representations
14
Implicit Representations
15
Signed Distance Function
• SDF of 2D circle?
• General shapes
16
SDF Discretization
F011 F111
F000 (1 − u) (1 − v) (1 − w) +
F010 F101 F100 u (1 − v) (1 − w) +
F010 (1 − u) v (1 − w) +
F001 (1 − u) (1 − v) w +
..
F110 .
F111 u v w
F000 F100
17
3-Color Octree
18
Adaptively Sampled Distance Fields
19
Binary Space Partitions
20
Regularity vs. Complexity
– Irregular hierarchies
• binary space partition (BSP)
21
Regularity vs. Complexity
22
Literature
• Frisken et al, “Adaptively Sampled Distance Fields: A
general representation of shape for computer
graphics”, SIGGRAPH 2000
23
Implicit Representations
24
Constructive Solid Geometry
• Union
FC∪S (·) = min {FC (·) , FS (·)}
• Intersection
FC∩S (·) = max {FC (·) , FS (·)}
• Difference
FC\S (·) = max {FC (·) , −FS (·)}
25
CSG Example
26
CSG Example: Milling
27
Overview
• Surface representations
– Explicit vs. Implicit
• Explicit representations
– Triangle meshes
• Implicit representations
– Signed distance fields
• Conversions
– Explicit Implicit
28
Conversions
• Explicit to Implicit
– Compute signed distance at grid points
– Compute distance point-mesh
– Fast marching
• Implicit to Explicit
– Extract zero-level iso-surface F(x,y,z)=0
– Other iso-surfaces F(x,y,z)=C
– Medical imaging, simulations, measurements, ...
29
Signed Distance Computation
• Distance Point-Triangle
– Distance to plane, edge, or vertex
– See http://www.geometrictools.com
• Inside or outside?
– Based on interpolated surface normals
30
Signed Distance Computation
pj
n
p
ni
pi
31
Fast Marching Techniques
1. Initialize with exact distance in mesh’s vicinity
2. Fast-march outwards
3. Fast-march inwards
32
Literature
• Schneider, Eberly, “Geometric Tools for Computer
Graphics”, Morgan Kaufmann, 2002
33
Conversions
• Explicit to Implicit
– Compute signed distance at grid points
– Compute distance point-mesh
– Fast marching
• Implicit to Explicit
– Extract zero-level iso-surface F(x,y,z)=0
– Other iso-surfaces F(x,y,z)=C
– Medical imaging, simulations, measurements, ...
34
2D: Marching Squares
1. Classify grid nodes as inside/outside
– Is F(xi,j) > 0 or < 0
35
2D: Marching Squares
36
3D: Marching Cubes
1. Classify grid nodes as inside/outside
– Is F(xi,j,k) > 0 or < 0
37
Marching Cubes
38
Intersection Points
39
Intersection Points
40
Intersection Points
41
Intersection Points
42
Marching Cubes
• Look-up table with 28 entries
– 15 representative cases shown
– Others follow by symmetry
43
Marching Cubes
44
Marching Cubes
65×65×65
45
Increasing Resolution?
46
Extended Marching Cubes
65×65×65
47
Extended Marching Cubes
• Feature detection
– Classify into edges / corners
– Based on angle between normals ni
48
Extended Marching Cubes
• Feature sampling
– Intersect tangent planes (si, ni)
.. ..
.T x T.
n · y = n si
i i
.. z ..
. .
49
Extended Marching Cubes
• Feature sampling
– Intersect tangent planes (si, ni)
– Triangle fans centered at feature point
50
Extended Marching Cubes
51
Milling Simulation
257×257×257
52
CSG Modeling
65×65×65
53
Marching Cubes
55
Literature
• Polygon Mesh Processing
– Chapter 1
56