Mesh Generation

Delaunay Property

• Accomplishing this maximizes the minimum inner triangle angle
• Circumcircle of any triangle does not contain any vertices
• For every edge there is a circle intersecting the adjacent vertices only
• Unique iff. every circumcircle intersects only three vertices

Voronoi Diagram

• For every vertex $p_i$ there is a $V_i$ which contains all points closer to $p_i$ than to any other vertex.
• Important definitions: Voronoi cell, Voronoi vertex

Incremental Delaunay Algorithm

• Build a triangle frame around all points
• Insert one point after another, updating the triangulation (and keeping it delaunay all the time using edge flipping)
• $O(n \log n)$

Sweepline Algorithm

Aka *Fortune's algorithm*
TODO

Contour tesselation

Medial Axis: Consists of points which have minimal distance to more than one point of the contour.

Voronoi filtering

Aka *Crust algorithm*
Idea: Use medial axis to identify contour

1. Voronoi diagram of samples
2. Delaunay triangulation / tetrahedrization of samples together with $p_i^+, p_i^-$ (some voronoi vertices)
3. Remove edges / faces containing $p_i^+, p_i^-$

TODO

Volumetric approaches

TODO

There were better ones, but I think it was in the seminar.

Direct methods

++++++++ Registration, ICP, Zippering, Stichting, etc

TODO