Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Input: Boundary loop consisting of vertices .
Goal: Triangulation of the loop interior which minimizes some triangulation cost which is a combination of e.g.

• the area of the triangles
• the maximum dihedral angle

which produces a hole filling with low area and low normal deviation.

We denote by the cost of the best triangulation for only the vertices .
Obviously:




Solve using dynamic programming.
Complexity: (Compute table for and . For every entry, consider possible middle triangles)

Optional post-processing steps
Refine the triangulation of the hole.
Apply smoothing to the hole region.

Problems
Does not work for islands.
Does not consider self-intersections.