Title

Digital Geometry Processing
Exercise 5 - Delaunay Triangulations
Edward Chien, edchien@bu.edu
Computer Graphics & Geometry Processing

Exercise 4 Commentary

Iterator Use

  • Some used multiple iterators or circulators unnecessarily
  • Recommendation: use one of the half-edge iterators
void Curvature::calc_vertices_weights() {
   double area = 0.;
   for (auto vh: mesh_.vertices()) {
       area = 0.0;

       for(auto vih_it = mesh_.vih_iter(vh); vih_it.is_valid(); ++vih_it) {
           if(mesh_.is_boundary(*vih_it))
               continue;

           area += mesh_.calc_sector_area(*vih_it) * 0.3333f;
       }

       mesh_.property(vertex_weight_, vh) = 0.5 / area;
   }
}

Curvature and Scaling

  • Curvature should decrease as shape is scaled
  • Mean curvature is the average of the normal section curvatures
  • Scaling would scale the osculating circles and \(|\kappa| = 1/r\)
normal_curv_demo.png

Exercise 5 Information

Incremental Algorithm

  • Given a set of 2D sample points \(\{ \vec{p}_1, \vec{p}_2, \vec{p}_3, \ldots \}\)
    • Insert points one by one
    • Flip edges to establish Delaunay property
  • Avoid special cases
    • Add a big triangle \((\vec{q}_1, \vec{q}_2, \vec{q}_3)\) containing all \(\vec{p}_i\)
    • Those points can later be removed
    • Points are then always inserted into existing triangles

Incremental Algorithm

delaunay-algo-00.svg delaunay-algo-01.svg delaunay-algo-02.svg delaunay-algo-03.svg delaunay-algo-04.svg delaunay-algo-05.svg delaunay-algo-06.svg delaunay-algo-07.svg delaunay-algo-08.svg delaunay-algo-09.svg delaunay-algo-10.svg delaunay-algo-11.svg

Incremental Algorithm

  • For each point \(\vec{p}_i\)
    • Find containing triangle
    • Insert point into triangle (1-to-3 split)
    • Flip edges to re-establish Delaunay property
    • Start with boundary edges of triangle containing \(\vec{p}_i\)
    • If an edge is flipped, check all edges that share a face with the flipped edge
    • Use a FIFO queue to store edges to check
  • Complexity is \(\mathcal{O}(n^2)\); not optimal, but simple to implement

Two Useful Methods

// OpenMesh::TriConnectivity::flip(EdgeHandle _eh)
mesh->flip(eh);

// halfedge_handle(EdgeHandle _eh, unsigned int _i)
hh0 = mesh->halfedge_handle(eh, 0);
hh1 = mesh->halfedge_handle(eh, 1);

In-Circle Test

  • How to efficiently compute \(\func{InCircle}\of{ \vec{A}, \vec{B}, \vec{C}, \vec{D} }\)?
    • Project onto paraboloid: \((x,y) \mapsto (x, y, x^2 + y^2)\)
    • Projected points \(\vec{A}'\), \(\vec{B}'\), \(\vec{C}'\) define a plane cutting through the paraboloid
    • 3D intersection curve projects to 2D circumcircle
    • \(\vec{D}\) is in/out circumcircle \(\Leftrightarrow\) \(\vec{D}'\) is below/above plane
    • \(\vec{D}'\) below/above plane \(\Leftrightarrow\) \(\func{volume}(\vec{A}',\vec{B}',\vec{C}',\vec{D}') < 0\) or \(>0\)
    • \[\func{volume}(\vec{A}',\vec{B}',\vec{C}',\vec{D}') \;=\; \func{det} \matrix{ A_x & A_y & A_x^2 + A_y^2 & 1 \\ B_x & B_y & B_x^2 + B_y^2 & 1 \\ C_x & C_y & C_x^2 + C_y^2 & 1 \\ D_x & D_y & D_x^2 + D_y^2 & 1} \]

in-circle-test-1.svg in-circle-test-2.svg