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

page revision: 5, last edited: 18 Mar 2007 11:20
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.