计算机图形学03-mesh
- 格式：pdf
- 大小：1.89 MB
- 文档页数：58
struct Halfedge { HalfedgeRef next_halfedge; HalfedgeRef opposite_halfedge; FaceRef face; VertexRef to_vertex; }; struct Face { HalfedgeRef halfedge; };
v2
11 12 21 22
VERTEX TABLE
v1 v2 v3 v4 v5 (x1,y1,z1) (x2,y2,z2) (x3,y3,z3) (x4,y4,z4) (x5,y5,z5) e1 e6 e3 e5 e6
EDGE TABLE f1 f1 f1 f2 f3 f2 f2 f3 f3
FACE TABLE
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
• Scanners
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Overview
• 3D polygonal mesh
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Lecture 3 Mesh
Dr. Shuang LIANG School of Software Engineering Tongji University Spring 2013
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
e1 (v1,v3) e2 (v1,v2) e3 (v2,v3) e4 (v3,v4) e5 (v2,v4) e6 (v2,v5) e7 (v4,v5) Mesh, Advanced Computer Graphics
e2 e1 e2 e1 e3 e5 e4
e2 e1 e5 e3 e6 e2 e5
e1 e4 e3 f1 e3 e3 e6 f2 e5 e1 e4 f3 e7 e5 e4 e7 e7 e7 e6 e6 Shuang LIANG, SSE, Spring 2013
Shuang LIANG, SSE, Spring 2013
Independent Faces
• Each face lists vertex coordinates
– Redundant vertices
(x3,y3,z3) f2 f1 (x1,y1,z1)
FACE TABLE f1 f2 f3 (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) (x2,y2,z2), (x4,y4,z4), (x3,y3,z3) (x2,y2,z2), (x5,y5,z5), (x4,y4,z4)
• Desired characteristics • Main data structures
• Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Desired Characteristics
• Scanners
– Laser range scanners
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
– Efficient usage of memory – Efficient updates
• We need to consider
– Algorithms – Operations
Mesh, Advanced Computer Graphics Shuang LIANG, SSE, Spring 2013
– Shared vertices – No adjacency information
(x3,y3,z3) f2 f1 (x1,y1,z1)
VERTEX TABLE v1 v2 v3 v4 v5 (x1,y1,z1) (x2,y2,z2) (x3,y3,z3) (x4,y4,z4) (x5,y5,z5)
• Scanners
– Laser range scanners – CT, MRI, etc.
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013 Today’s Topics
• Overview • Mesh Acquisition • Mesh Data Structures
SketchUp
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Blender
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
v2,v4,v3 e5,e4,e3 f3,f1
e1,e4,e2,e5,e6
f1,f2
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Partial Adjacency Lists
• Can we store only some adjacency relationships and derive others?
Overview
• 3D polygonal mesh
– Representing a 2D surface embedded in 3D by using a set of polygons
• Why are they of interest?
– – – – Simple, common representation Rendering with hardware support Output of many acquisition tools Input to many simulation/analysis tools
(x4,y4,z4)
f3 (x5,y5,z5) (x2,y2,z2)
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Vertex and Face Tables
• Each face lists vertex references
• Store all vertex, edges and face adjacencies
– Efficient adjacency traversal – Extra storage e4 v3
f2 e 5
v4
e7
f3
e 1 f1
v1
v2,v3
e3
e2
v5 e6
v2
v5,v4,v3,v1 e6,e5,e3,e2 f3,f2,f1
Overview
• 3D polygonal mesh
Geometry & topology
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
• For each face, we store a reference to
– One of its half-edges
• For each vertex, we store a reference to
– One of its outgoing half-edges
Mesh, Advanced Computer Graphics Shuang LIANG, SSE, Spring 2013
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Half-edge
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Half-edge
A basic half-edge structure can be realized using the following classes
Half-edge
• Instead of a single edge, 2 directed “half edges” • For each half-edge, we store a reference to
v2
11 12 21 22
VERTEX TABLE
v1 v2 v3 v4 v5 (x1,y1,z1) (x2,y2,z2) (x3,y3,z3) (x4,y4,z4) (x5,y5,z5) e1 e6 e3 e5 e6
EDGE TABLE f1 f1 f1 f2 f3 f2 f2 f3 f3
FACE TABLE
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
• Scanners
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Overview
• 3D polygonal mesh
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Lecture 3 Mesh
Dr. Shuang LIANG School of Software Engineering Tongji University Spring 2013
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
e1 (v1,v3) e2 (v1,v2) e3 (v2,v3) e4 (v3,v4) e5 (v2,v4) e6 (v2,v5) e7 (v4,v5) Mesh, Advanced Computer Graphics
e2 e1 e2 e1 e3 e5 e4
e2 e1 e5 e3 e6 e2 e5
e1 e4 e3 f1 e3 e3 e6 f2 e5 e1 e4 f3 e7 e5 e4 e7 e7 e7 e6 e6 Shuang LIANG, SSE, Spring 2013
Shuang LIANG, SSE, Spring 2013
Independent Faces
• Each face lists vertex coordinates
– Redundant vertices
(x3,y3,z3) f2 f1 (x1,y1,z1)
FACE TABLE f1 f2 f3 (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) (x2,y2,z2), (x4,y4,z4), (x3,y3,z3) (x2,y2,z2), (x5,y5,z5), (x4,y4,z4)
• Desired characteristics • Main data structures
• Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Desired Characteristics
• Scanners
– Laser range scanners
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
– Efficient usage of memory – Efficient updates
• We need to consider
– Algorithms – Operations
Mesh, Advanced Computer Graphics Shuang LIANG, SSE, Spring 2013
– Shared vertices – No adjacency information
(x3,y3,z3) f2 f1 (x1,y1,z1)
VERTEX TABLE v1 v2 v3 v4 v5 (x1,y1,z1) (x2,y2,z2) (x3,y3,z3) (x4,y4,z4) (x5,y5,z5)
• Scanners
– Laser range scanners – CT, MRI, etc.
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013 Today’s Topics
• Overview • Mesh Acquisition • Mesh Data Structures
SketchUp
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Blender
Mesh Acquisition
• Interactive modeling
– Polygon editors – Interactive software
v2,v4,v3 e5,e4,e3 f3,f1
e1,e4,e2,e5,e6
f1,f2
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Partial Adjacency Lists
• Can we store only some adjacency relationships and derive others?
Overview
• 3D polygonal mesh
– Representing a 2D surface embedded in 3D by using a set of polygons
• Why are they of interest?
– – – – Simple, common representation Rendering with hardware support Output of many acquisition tools Input to many simulation/analysis tools
(x4,y4,z4)
f3 (x5,y5,z5) (x2,y2,z2)
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Vertex and Face Tables
• Each face lists vertex references
• Store all vertex, edges and face adjacencies
– Efficient adjacency traversal – Extra storage e4 v3
f2 e 5
v4
e7
f3
e 1 f1
v1
v2,v3
e3
e2
v5 e6
v2
v5,v4,v3,v1 e6,e5,e3,e2 f3,f2,f1
Overview
• 3D polygonal mesh
Geometry & topology
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
• For each face, we store a reference to
– One of its half-edges
• For each vertex, we store a reference to
– One of its outgoing half-edges
Mesh, Advanced Computer Graphics Shuang LIANG, SSE, Spring 2013
Today’s Topics
• • • • Overview Mesh Acquisition Mesh Data Structures Subdivision Surfaces
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Half-edge
Mesh, Advanced Computer Graphics
Shuang LIANG, SSE, Spring 2013
Half-edge
A basic half-edge structure can be realized using the following classes
Half-edge
• Instead of a single edge, 2 directed “half edges” • For each half-edge, we store a reference to
