Transcript Boundary Representations and Topology

Boundary Representations
and Topology
Dr. Scott Schaefer
1
Boundary Representations

Stores the boundary of a solid
 Geometry: vertex locations
 Topology: connectivity information
 Vertices
 Edges
 Faces
2/38
Boundary Representations

Constant time adjacency information
 For each vertex,
 Find edges/faces touching vertex
 For each edge,
 Find vertices/faces touching edge
 For each face,
 Find vertices/edges touching face
3/38
Boundary Representations

Typically assume the surface is manifold

A surface is manifold if, for every point,
locally the surface is equivalent to an open
disk
4/38
Boundary Representations

Typically assume the surface is manifold

A surface is manifold if, for every point,
locally the surface is equivalent to an open
disk
Locally manifold
5/38
Boundary Representations

Typically assume the surface is manifold

A surface is manifold if, for every point,
locally the surface is equivalent to an open
disk
Non-manifold edge
6/38
Boundary Representations

Typically assume the surface is manifold

A surface is manifold if, for every point,
locally the surface is equivalent to an open
disk
Non-manifold vertex
7/38
Winged Edge Data Structure
NL
NR
N
Left face
Right face
E
P
PL
PR
8/38
Winged Edge Data Structure
WingedEdge {
WingedEdge nextLeft, nextRight,
prevLeft, prevRight;
Face leftFace, rightFace;
Vertex prevVert, nextVert;
}
Face {
WingedEdge edge;
}
Vertex {
WingedEdge edge;
}
NL
NR
N
Left face
Right face
E
P
PL
PR
9/38
Winged Edge Data Structure
Given a face, find all vertices touching that
face
 Given a vertex, find all edge-adjacent
vertices
 Given a face, find all
NL
NR
N
adjacent faces

Left face
Right face
E
P
PL
PR
10/38
Half Edge Data Structure
NHE
face
HE E Flip
PHE
V
11/38
Half Edge Data Structure
HalfEdge {
HalfEdge next, prev, flip;
Face face;
Vertex origin;
Edge edge;
}
Face {
HalfEdge edge; // part of this face
}
Vertex {
HalfEdge edge; // points away
}
Edge {
HalfEdge he;
}
NHE
face
HE E Flip
PHE
V
12/38
Half Edge Data Structure
Very similar to WingedEdge Data Structure,
but edges have unique orientation
 Slightly more storage
 Less conditional operations
NHE
 Assumes polygons are oriented

face
HE E Flip
PHE
V
13/38
QuadEdge Data Structure
V1
F2
F1
V2
14/38
Navigating a QuadEdge
Data Structure
V1
F2
F1
V2
15/38
Navigating a QuadEdge
Data Structure
Origin
V1
F2
F1
V2
16/38
Navigating a QuadEdge
Data Structure
V1
Flip
F2
F1
V2
17/38
Navigating a QuadEdge
Data Structure
V1
Rot
F2
F1
V2
18/38
Navigating a QuadEdge
Data Structure
V1
invRot
F2
F1
V2
19/38
Navigating a QuadEdge
Data Structure
V1
Prev
F2
F1
V2
20/38
Navigating a QuadEdge
Data Structure
V1
Next
F2
F1
V2
21/38
QuadEdge Data Structure
Treats faces just like vertices
 Stores both the shape and its dual


Beneficial for many types of
subdivision surfaces
V1
F2
F1
V2
22/38
Building a Topological Data Structure
Must connect adjacent edges/faces/vertices
 Edges are critical in most data structures


Use a hash table indexed by
two vertices
NHE
face
HE E Flip
PHE
V
23/38
Euler Characteristic
V  E  F  2  2G   (G )
V: number of vertices
 E: number of edges
 F: number of faces
 G: genus of surface (number of holes)

24/38
Euler Characteristic
V  E  F  2  2G   (G )
V: number of vertices
 E: number of edges
 F: number of faces
 G: genus of surface (number of holes)

25/38
Euler Characteristic
V  E  F  2  2G   (G )
V: number of vertices
 E: number of edges
 F: number of faces
 G: genus of surface (number of holes)

8 12  6  2  2 * 0
26/38
Euler Characteristic
V  E  F  2  2G   (G )
V: number of vertices
 E: number of edges
 F: number of faces
 G: genus of surface (number of holes)

4  6  4  2  2*0
27/38
Euler Characteristic
V  E  F  2  2G   (G )
V: number of vertices
 E: number of edges
 F: number of faces
 G: genus of surface (number of holes)

16  32  16  2  2 *1
28/38
Topological Operations: Hole Filling
Find a half-edge whose flip is null
 Use next and flip points to find next adjacent
half-edge with null flip
 Repeat until back at original
NHE
half-edge
face
Flip  null
 Create new half-edges along
HE
E
boundary and face containing
PHE
those edges
V

29/38
Topological Operations: Edge
Collapse
30/38
Topological Operations: Edge
Collapse

Set origin of all edges pointing outwards from
two vertices to new vertex and vertex to one of
the half-edges
31/38
Topological Operations: Edge
Collapse


Set origin of all edges pointing outwards from
two vertices to new vertex and vertex to one of
the half-edges
Set flip on outer edges to point to opposite edge
32/38
Topological Operations: Edge
Collapse



Set origin of all edges pointing outwards from
two vertices to new vertex and vertex to one of
the half-edges
Set flip on outer edges to point to opposite edge
Make sure half-edge pointer for edges point to
correct half-edge
33/38
Topological Operations: Edge
Collapse




Set origin of all edges pointing outwards from
two vertices to new vertex and vertex to one of
the half-edges
Set flip on outer edges to point to opposite edge
Make sure half-edge pointer for edges point to
correct half-edge
Update half-edge for
wing-vertices
34/38
Topological Operations: Edge
Collapse





Set origin of all edges pointing outwards from
two vertices to new vertex and vertex to one of
the half-edges
Set flip on outer edges to point to opposite edge
Make sure half-edge pointer for edges point to
correct half-edge
Update half-edge for
wing-vertices
Delete faces/edges/vertices
35/38
Topological Operation: Edge
Collapse

Edge collapse preserves topology as long as
the local Euler characteristic of the surface
remains the same
V  E  F   (G )
36/38
Topological Operation: Edge
Collapse

Edge collapse preserves topology as long as
the local Euler characteristic of the surface
remains the same
V  E  F   (G )
Vˆ  Eˆ  Fˆ  (V  1)  ( E  3)  ( F  2)  V  E  F
Vˆ  V  1
Eˆ  E  3
Fˆ  F  2
37/38
Topological Operation: Edge
Collapse

Edge collapse does NOT always preserve
topology
38/38
Detecting Unsafe Edge Collapses
Let N(v) be the set of vertices edge-adjacent
to v
 Safe to collapse if N (v1 )  N (v2 )  2

v1
v2
39/38