Appendix A: Incremental constrained Delaunay triangulation algorithm.

Given a set of surface samples, the goal is to build a mesh, that is a faceted (triangulated) representation of the surface. The main challenge here is to find ``neighbors'' of given a pixel in such a way that the least amount of long and narrow polygons are produced.

.

Initial estimation
Before the algorithm proceeds it needs an initial estimate of a convex hull containing all the points of the data set. We use the corners of the disparity map as the ``initial value'' for the triangulation.

.

Including a new point
A point of the interior area is included in the mesh. The point is connected to its enclosing triangle by three new triangle edges between the point and the vertices of the triangle.

.

Reordering
The quadrilaterals, which have got the ``old'' edges of the enclosing triangle as a diagonal, are tested by the maximum angle-sum rule, which states that in a quadrilateral formed by two adjacent triangles in a Delaunay triangulation, the diagonal goes between two opposite vertices where the sum of the interior angles is greater or equal to $\pi$. This ensures that short and wide triangles are preferred in this triangulation. If the old edges do not meet the criterion, their diagonals are swapped and the new, opposite edges to the inserted point will be examined as diagonals in their quadrilaterals.

.

Iteration
The Delaunay network now contains one more point. We iterate the two previous steps until all the data points are included.