Polygonal Mesh
Lecture: 5
Fall 2016
Computer Graphics (CS3388) Department of Computer Science
University of Western Ontario
Polygonal Mesh Modelling
Outline
Range data
From range data to surface
Polygonal mesh data structure
Mesh triangulation
Mesh simplification
Surface of revolution
(materials from Jessica K. Hodgins (CMU), Alla Sheffer (UBC), M. Kreveld (Utrecht Univ.), Stanford graphics class, S. Jamin (MU))
1
Polygonal Mesh Modelling
Modelling complex shapes
We want to build models of very complicated objects
An equation for a sphere is possible, but how about an equation for a telephone, or a face?
Goals
Model anything with arbitrary precision Easy to build and modify
Efficient computations
2
Mesh applications
3
Polygonal Mesh Modelling
3D modelling
Process of developing mathematical representation of any three-dimensional surface of an object through a software.
3D geometry representations
Points: 2D range image or 3D point cloud
Solids: voxels/solid geometry
Surfaces: polygonal mesh, parametric surface, subdivision surface, implicit surface
Procedural: particle system, fractal
4
Range data
Range data representations
Range image
Pixel location (r,c)
Pixel contains depth, not color 3D point cloud
Set of points in 3D space (xi,yi,zi)
5
How to get the range data?
Classic Digital Michaelangelo project
6
How to get the range data?
Where do meshes come from?
Specify manually
Write out all polygons
Write some code to generate them Interactive editing
Acquisition from real objects Laser scanners
Generate set of points on the surface Need to convert to polygons
7
Point Clouds to Surface
Input: Unstructured 3D points (Point Cloud) Output: Polygonal data set (Surface Mesh)
Mesh:
Connected set of polygons (usually triangles) Straight line graph embedded in R3
8
Mesh: pros & cons
Pros: Flexible. Can be rendered quickly. Most of the 3D models nowadays are built as textured polygonal models.
Cons: polygons are planar and can only approximate curved surfaces using many polygons.
(image from L. Zhang, SSE 2012)
9
Polygon meshes
Any shape can be modelled out of polygons
Polygons with how many sides? Triangles are most common
Polygon meshes are built out of
vertices (points)
edges (line segments between vertices) faces (polygons bounded by edges)
10
Polygon meshes
Why polygons?
Polygons are simple to represent and manipulate They can be used to approximate smooth surfaces each polygon (if planar) has a unique normal vector
Normal to a triangle
Triangles define unique plane normal n = a×b
||a×b||
Depends on vertex orientation. Clockwise order gives n′ = −n
11
Representing polygon meshes
Simplest (but dumb)
float triangle[n][3][3];
redundant: each vertex stored multiple times
Vertex List, Face List
List of vertices (only vertex coordinates)
List of triangles, each a triple of vertex id’s (takes O(F) time for F faces)
Fancier schemes
Store more topological info so adjacency queries can be answered in O(1) time
12
.obj file format example
# OBJ file format
v -1.0 1.0 1.0
v -1.0 -1.0 1.0
v 1.0 -1.0 1.0
v 1.0 1.0 1.0
v -1.0 1.0 -1.0 v -1.0 -1.0 -1.0 v 1.0 -1.0 -1.0 v 1.0 1.0 -1.0 f1234 f8765 f4378 f5148 f5621 f2673
13
How Many Polygons to Use?
14
Mesh Triangulation
Let P = {p1,··· ,pn} be a point set. A triangulation of P is a maximal planar subdivision with vertex set P
15
Mesh Triangulation
But which triangulation?
16
Mesh Triangulation
Voronoi diagram
Given some trees, which region will they occupy?
17
Mesh Triangulation
Given ambulance posts in a country, in case of an emergency somewhere, where should the ambulance come from?
18
Mesh Triangulation
Voronoi diagram: Subdivision of the plane where the faces correspond to the regions where one site is closest
19
Mesh Triangulation
Let P be a set of n points in the plane
Let Vor(P) is the subdivision of the plane into Voronoi cells
Let G be the dual graph of Vor(P)
dual graph: The dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge
20
Delaunay Triangulation
The Delaunay graph is the straight line embedding of the dual graph G
21
Mesh Simplification
Why do we need mesh simplification?
need for accuracy depends on the application storage efficiency
faster rendering
simpler manipulation
22
Mesh Simplification
Size-quality trade-off
23
Mesh Simplification
vertex clustering mesh retiling mesh decimation
vertex remove edge collapse pair contraction
24
Mesh Simplification
Vertex Clustering
partition space into cells (grids, spheres, octrees, etc.) merge all vertices within the same cell
general & robust, but not best quality
25
Mesh Simplification
Mesh Retiling
Resample mesh with “uniformly spaced” random vertices triangulate the new vertices
slow, blurs the sharp features
26
Mesh Simplification
Mesh decimation
vertex removal
v ← v − 1, f ← f − 2
requires manifold surface around vertex preserves local topological structure filing hole may not be easy
27
Mesh Simplification
Mesh decimation
edge collapse
v ← v − 1, f ← f − 2
requires manifold surface around vertex preserves local topological structure allows smooth transition
28
Mesh Simplification
Mesh decimation
pair contraction
usually limited to small distance not best quality
29
Mesh Data Structure
Let’s look at our usual mesh representation Face Set
Shared Vertex
30
Mesh Data Structure
Questions:
What are the vertices of face f1? (okay this is O(1), but how about
others?)
what are the neighbours of V3? (requires full pass over all vertices!) are V1 & V5 adjacent? (requires full pass over all faces!)
31
Mesh Data Structure
Half edge data structure: an efficient way to store mesh data Record for each face, edge and vertex
Geometric information Topological information Attribute information
also called DCEL (Doubly Connected Edge List) or Winged-Edge Structure
32
Half Edge Data Structure
Vertex record
Coordinates
Pointer to one half-edge that has V as its origin
Face record
Pointer to one half-edge on its boundary
Half-edge record
Pointer to its origin, origin(e)
Pointer to its twin half-edge, twin(e)
Pointer to the face it bounds, IncidentFace(e)
Next and previous edge on boundary of IncidentFace(e)
33
Half Edge Data Structure
Example:
34
Half Edge Data Structure
Pros
All queries in O(1) time
All operations are O(1) (usually)
Cons
Represents only manifold meshes
35
Surfaces of Revolution
Surface of Revolution or “sweep surface”
A technique to produce 3D objects
A simple way of defining objects is obtained by rotating a curve or a line around an axis
36
Surfaces of Revolution
Rotate given 2D profile curve
Sweeping the profile completely around (360◦) generates a full circle triangulate the discrete points
render the surface
37