GitLab

The ConstrainedDelaunay2 class had two bugs that needed to be fixed. The first bug was incorrect handling of adjacent triangles during retriangulation of the triangle strips containing the constrained edges. This problem shows up when the triangle strip snakes around and has a shared edge with another triangle that is not its immediate predecessor in the strip. The second bug was an incorrect computation of the pseudosquared distance function. This problem shows up when locating the closest vertex of a boundary polygon to the base polygon edge. In particular, the bug was exercised when the projections of the candidate vertices to the base edge of the polygon contained at least one projection on the segment and one projection outside the segment.

This code is approximately 13 years old and was complicated to read and debug. It discarded the mGraph member from the Delaunay triangulation and instead used the compact arrays mIndices and mAdjacencies. I rewrote ConstrainedDelaunay2 to continue using the mGraph member, in the process simplifying the implementation to be readable. Many comments were added, but I plan on adding a PDF to the website describing the pitfalls of the retriangulation and how to avoid them. The original code was based on an online research paper that discussed the simplest retriangulation configuration, but had no discussion about the pitfall cases. The various file changes are described next.

GTE/GTMathematics/ConstrainedDelaunay2.h: Reimplemented ConstrainedDelaunay2 according to the aforementioned comments.

GTE/GTMathematics/Delaunay2.h: Factored out some code into a new function UpdateIndicesAdjacencies. This code occurred after the Delaunay triangulation to synchronize the information in mGraph with the compact arrays mIndices and mAdjacencies. To support ConstrainedDelaunay2, the factored function can be called after a user-determined set of edges have been inserted one at a time.

GTE/GTMathematics/ETManifoldMesh.h: Added two helper functions to ETManifoldMesh::Triangle, namely, GetAdjacentOfEdge and GetOppositeVertexOfEdge. I will continue to encapsulate commmon operations and add them to ETManifoldMesh. These operations tend to occur as in-application code, but that code should be shared.

GTE/GTMathematics/TriangulateCDT.h: The modifications to ConstrainedDelaunay2 required a small modification to the polygon triangulation that uses constrained Delaunay triangulation. The code copies the Delaunay mGraph object to the local graph object.

GTE/Samples/Geometrics/ConstrainedDelaunay2D/ConstrainedDelaunay2DWindow2.cpp: The insertions are not batched; rather, they are executed one at a time based on key strokes. The application now needs to call UpdateIndicesAdjacencies after each edge insertion.