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*

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^-$


Volumetric approaches


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

Direct methods

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


Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.