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

- Voronoi diagram of samples
- Delaunay triangulation / tetrahedrization of samples together with $p_i^+, p_i^-$ (some voronoi vertices)
- 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

page revision: 5, last edited: 18 Mar 2007 11:20