CODEWITHSUNDEEP
c++algorithmcomputational-geometrymeshcgal
Pranav
Pranav

Reputation: 475

Creating and re-filling a hole inside existing Delaunay tetrahedralization

I am trying to implement a mesh generation algorithm. I am representing Delaunay tetrahedralization using CGAL::Delaunay_triangulation_3 class.

In one stage of the algorithm(section 7: Facet recovery), I have a Delaunay tetrahedralization(say DT0), I need to create a cavity(or hole)C inside the Delaunay tetrahedralization(thereby transforming it to say DT1) and fill it again with new tetrahedrons by performing Delaunay tetrahedralization(say DT2) on the vertices of the cavity. Resulting tetrahedralization need not be purely Delaunay(i.e, it may have some cells not satisfying empty sphere criteria). More details on why such cavity needs to be created and refilled again are mentioned below in the context section.

Question:
Is it possible in CGAL to create such a cavity inside an existing Delaunay tetrahedralization and fill it with another tetrahedralization?

Relevent details:

Context:
The purpose for creating the cavity and refilling it is the following: Algorithm(mentioned above) is for computing a constraint preserving Delaunay tetrahedralization. Input to the algorithm is a set of vertices,segments(a segment connects 2 vertices) and facets(in my case these are triangles) given as constraints that must be preserved in the final tetrahedralization. In this question, I am discussing about implementation of facet preservation part of the algorithm. To recover any missing constraint facet in the final tetrahedralization, algorithm creates a cavity and refills it with tetrahedrons(or cells) in such way that combination of the facets of some of these cells recover the constraint facet(i.e., f1+f2+...+fn=f where f1,f2..fn are facets of some newly created cells in the cavity and f is the constraint facet, or in other words, f1,f2..fn are sub-facets of f) in the output tetrahedralization. Output tetrahedralization is called Constrained Delaunay tetrahedralization in literature and it may or may not be Delaunay.

My attempt:
Currently, I do not find any relevant CGAL class to directly solve this issue so I am thinking of doing the following:

  1. Representing initial Delaunay tetrahedralization DT0 using CGAL::Delaunay_triangulation_3.
  2. Computing cavity C inside DT0 following the algorithm and representing C as a separate Polyhedron_3 object. Remaining set of tetrahedrons are collectively denoted by DT1.
  3. Computing Delaunay tetrahedralization DT2' of the vertices of C.
  4. Selecting cells from DT2'(as per algorithm) to compute DT2.
  5. Finally, merging DT1 and DT2. Since both share facets of C(guaranteed by the algorithm), so they can be connected in principle.

Right now I am thinking of representing DT1 and DT2 as std::list<Tetrahedron_3> object but how to merge them to create a tetrahedralization?

Upvotes: 3

Views: 660

Answers (2)

Pranav
Pranav

Reputation: 475

After reading CGAL documentation, I realized that I can represent my output mesh in form of Linear cell complex instead. I can now do the following:

  1. Import my original Delaunay tetrahedralization to Linear cell complex format using import_from_triangulation_3().
  2. Create cavity inside it by applying the algorithm and using remove_cell().
  3. Filling the cavity with the Delaunay tetrahedralization of vertices of the cavity(as per algorithm) and adding these new cells to the original tetrahedral mesh using sew3_same_facets()(undocumented function). I have got reference for sew3_same_facets() from CGAL discussion forum.

Right now, I am not accepting my response as the answer since I am still in process of implementing it. But I thought of sharing it meanwhile.

Upvotes: 1

olivier
olivier

Reputation: 221

This is the way that the point removal is implemented in CGAL. You may want to look at the code for remove.

Upvotes: 3

Related Questions