I. Introduction

Definitions

• 1D, 2D, 3D spaces
• Curve, Surface Mesh, Spatial Decomposition
• Vertices, Edges, Faces, Cells

Well-Formed Surfaces

• Components Intersect "Properly"
1. Faces are: disjoint, share single Vertex, or share 2 Vertices and the Edge joining them
2. Every edge is incident to exactly 2 vertices
3. Every edge is incident to exactly 2 faces
• Local Topology is "Proper"
1. Neighborhood of a Vertex is homeomorphic to a disk (permits stretching and bending, but not tearing)
2. Called a 2-manifold
3. Boundaries: half-disk, "manifold with boundaries"
4. Link of Vertex is a simple closed path
• Global Topology is "Proper"
1. Connected
2. Closed
3. Bounded

Bad!		Fixed		Bad!

Subdividing a Domain

• Structured Subdivision
• Unstructured Subdivision

Structured		Unstructured

Data

• Geometric Information
1. Vertex Locations
2. Others?
• Attribute Information
1. Color (at vertex or face)
2. Temperature/Pressure (at vertex, face, or cell)
3. Vegetation, Population, other statistics
4. Others?

Applications

• Polygon Mesh for Efficient Object Representation
• Scientific Computation (fluid dynamics)
• Subdivision Surfaces
• Partitioning: Voronoi Diagram / Delaunay Triangulation