Tessellation

Tessellation

Wanho Choi


(wanochoi.com)

Tessellation

•

Tiling of a given surface (or volume) with geometric

elements (=tiles) with no overlaps and no gaps

Simplex

•

A k-simplex is a k-dimensional polytope

which is the convex hull of its k+1 vertices.

0-simplex

1-simplex

2-simplex

3-simplex

point

line segment

triangle

tetrahedron

Cell (Regular Element)

•

Pixel: picture element (rectangular cell)

•

_{Voxel: volume cell (volumetric pixel)}

Uniform Grid (Dense Grid)

•

Resolution: Nx, Ny (# of cells in each direction)

•

_{Dimension: Lx (=Nx*Dx), Ly (=Ny*Dy)}

Spaces

•

World space: transformed space

•

_{Voxel space: Dx=Dy=1 (axis-aligned)}

Sparse Grid

•

2D: quadtree (four children)

•

_{3D: octree (eight children)}

Structured / Unstructured Grid

•

Structured grid: regular grid (uniform/quadtree grid)

•

_{Unstructured grid: irregular grid (triangle/tet. grid)}

Effective Resolution

Where is the Value?

•

Cell center, node, edge, and face

•

_{Mac (staggered) grid}

Open Source Libraries

•

OpenVDB (http://www.openvdb.org/)

Triangle Mesh

Mesh Quality

•

What is the best mesh?

Mesh Quality

•

Do not have long edges.

•

Do not have triangle with both short and long edges.

•

_{Do not have triangles with very small angles.}

•

_{Do not have triangles with obtuse angles.}

•

…

https://www.ics.uci.edu/~eppstein/pubs/Epp-IMR-01.pdf

Sliver Triangle

•

A triangle with one or two extremely acute angles,

hence a long/thin shape, which has undesirable

properties during some interpolation or rasterization

processes.

Delaunay Triangulation

•

No point inside the circumcircle of any triangle

•

_{It maximize the minimum angle of all the angles of}

the triangles. (therefore, no sliver triangle)

•

Lift the given 2D points onto a paraboloid.

•

_{Compute the convex hull of the lifted 3D points.}

•

_{Project the convex hull back to the plane.}

Lifting Transformation

Delaunay Triangulation: Algorithm

To insert a new vertex…

Delaunay Triangulation: Algorithm

... first, find which triangles have a circumscribed circle encompassing the vertex.

Delaunay Triangulation: Algorithm

Remove those triangles, but remember their edges.

Delaunay Triangulation: Algorithm

Remove double edges, keeping only the unique ones.

Delaunay Triangulation: Algorithm

Form new triangles between the remaining edges and the new vertex...

Delaunay Triangulation: Algorithm

... and, finally, put those new triangles back.

Delaunay Triangulation Art

Voronoi Diagram

•

A partitioning the space into regions based on

distance to the given points

Dual Relationship

•

Voronoi diagram is dual to Delaunay triangulation

Tetrahedral Volume Mesh

Neighbor Elements

•

Why needed?

•

_{Derivative! (gradient, divergence, curl, and Laplacian)}