LCOV - code coverage report
Current view: top level - src/mesh - mesh_tetgen_interface.C (source / functions) Hit Total Coverage
Test: libMesh/libmesh: #4417 (f0ff5e) with base 9bbd75 Lines: 113 124 91.1 %
Date: 2026-11-16 16:30:47 Functions: 7 9 77.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // The libMesh Finite Element Library.
       2             : // Copyright (C) 2002-2026 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
       3             : 
       4             : // This library is free software; you can redistribute it and/or
       5             : // modify it under the terms of the GNU Lesser General Public
       6             : // License as published by the Free Software Foundation; either
       7             : // version 2.1 of the License, or (at your option) any later version.
       8             : 
       9             : // This library is distributed in the hope that it will be useful,
      10             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      12             : // Lesser General Public License for more details.
      13             : 
      14             : // You should have received a copy of the GNU Lesser General Public
      15             : // License along with this library; if not, write to the Free Software
      16             : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      17             : 
      18             : #include "libmesh/libmesh_config.h"
      19             : #ifdef LIBMESH_HAVE_TETGEN
      20             : 
      21             : 
      22             : // C++ includes
      23             : #include <sstream>
      24             : 
      25             : // Local includes
      26             : #include "libmesh/mesh_tetgen_interface.h"
      27             : 
      28             : #include "libmesh/boundary_info.h"
      29             : #include "libmesh/cell_tet4.h"
      30             : #include "libmesh/face_tri3.h"
      31             : #include "libmesh/mesh_smoother_laplace.h"
      32             : #include "libmesh/unstructured_mesh.h"
      33             : #include "libmesh/utility.h" // binary_find
      34             : #include "libmesh/mesh_tetgen_wrapper.h"
      35             : 
      36             : namespace libMesh
      37             : {
      38             : 
      39             : //----------------------------------------------------------------------
      40             : // TetGenMeshInterface class members
      41          28 : TetGenMeshInterface::TetGenMeshInterface (UnstructuredMesh & mesh) :
      42             :   MeshTetInterface(mesh),
      43          28 :   _serializer(_mesh),
      44          28 :   _switches("Q")
      45             : {
      46          28 : }
      47             : 
      48           2 : void TetGenMeshInterface::set_switches(std::string switches)
      49             : {
      50             :   // set the tetgen switch manually:
      51             :   // p = tetrahedralizes a piecewise linear complex (see definition in user manual)
      52             :   // Q = quiet, no terminal output
      53             :   // q = specify a minimum radius/edge ratio
      54             :   // a = tetrahedron volume constraint
      55             :   // V = verbose output
      56             :   // for full list of options and their meaning: see the tetgen manual
      57             :   // (http://wias-berlin.de/software/tetgen/1.5/doc/manual/manual005.html)
      58           2 :   _switches = std::move(switches);
      59           2 : }
      60             : 
      61             : 
      62           0 : void TetGenMeshInterface::triangulate ()
      63             : {
      64           0 :   this->triangulate_pointset();
      65           0 : }
      66             : 
      67             : 
      68        1080 : void TetGenMeshInterface::triangulate_pointset ()
      69             : {
      70             :   // class tetgen_wrapper allows library access on a basic level:
      71        2160 :   TetGenWrapper tetgen_wrapper;
      72             : 
      73             :   // fill input structure with point set data:
      74        1080 :   this->fill_pointlist(tetgen_wrapper);
      75             : 
      76             :   // Run TetGen triangulation method:
      77             :   // Q = quiet, no terminal output
      78             :   // V = verbose, more terminal output
      79             :   // Note: if no switch is used, the input must be a list of 3D points
      80             :   // (.node file) and the Delaunay tetrahedralization of this point set
      81             :   // will be generated.
      82             : 
      83             :   // Can we apply quality and volume constraints in
      84             :   // triangulate_pointset()?.  On at least one test problem,
      85             :   // specifying any quality or volume constraints here causes tetgen
      86             :   // to segfault down in the insphere method: a nullptr is passed
      87             :   // to the routine.
      88        2160 :   std::ostringstream oss;
      89         540 :   oss << _switches;
      90             :   // oss << "V"; // verbose operation
      91             :   //oss  << "q" << std::fixed << 2.0;  // quality constraint
      92             :   //oss  << "a" << std::fixed << 100.; // volume constraint
      93             : 
      94             :   // But if the user wants refinement, let's do our best.
      95        1080 :   if (_desired_volume)
      96           0 :     oss  << "a" << std::fixed << _desired_volume; // volume constraint
      97             : 
      98        1080 :   tetgen_wrapper.set_switches(oss.str());
      99             : 
     100             :   // Run tetgen
     101        1080 :   tetgen_wrapper.run_tetgen();
     102             : 
     103             :   // save elements to mesh structure, nodes will not be changed:
     104        1080 :   const unsigned int num_elements   = tetgen_wrapper.get_numberoftetrahedra();
     105             : 
     106             :   // Vector that temporarily holds the node labels defining element.
     107             :   unsigned int node_labels[4];
     108             : 
     109        4554 :   for (unsigned int i=0; i<num_elements; ++i)
     110             :     {
     111        3474 :       auto elem = Elem::build(TET4);
     112             : 
     113             :       // Get the nodes associated with this element
     114       17370 :       for (auto j : elem->node_index_range())
     115       13896 :         node_labels[j] = tetgen_wrapper.get_element_node(i,j);
     116             : 
     117             :       // Associate the nodes with this element
     118        3474 :       this->assign_nodes_to_elem(node_labels, elem.get());
     119             : 
     120             :       // Finally, add this element to the mesh.
     121        6948 :       this->_mesh.add_elem(std::move(elem));
     122             :     }
     123             : 
     124             :   // To the naked eye, a few smoothing iterations usually looks better.
     125             :   // We don't do this by default.
     126        1080 :   if (this->_smooth_after_generating)
     127           0 :     LaplaceMeshSmoother(this->_mesh, 2).smooth();
     128             : 
     129             :   // We've added a bunch of elements.  A full prepare_for_use() would
     130             :   // be expensive here and user code hasn't been expecting it, but we
     131             :   // do have code downstream expecting element caches to be up to
     132             :   // date.
     133        1080 :   this->_mesh.cache_elem_data();
     134        1080 : }
     135             : 
     136             : 
     137             : 
     138           8 : void TetGenMeshInterface::pointset_convexhull ()
     139             : {
     140             :   // class tetgen_wrapper allows library access on a basic level
     141          16 :   TetGenWrapper tetgen_wrapper;
     142             : 
     143             :   // Copy Mesh's node points into TetGen data structure
     144           8 :   this->fill_pointlist(tetgen_wrapper);
     145             : 
     146             :   // Run TetGen triangulation method:
     147             :   // Q = quiet, no terminal output
     148             :   // Note: if no switch is used, the input must be a list of 3D points
     149             :   // (.node file) and the Delaunay tetrahedralization of this point set
     150             :   // will be generated.  In this particular function, we are throwing
     151             :   // away the tetrahedra generated by TetGen, and keeping only the
     152             :   // convex hull...
     153           8 :   tetgen_wrapper.set_switches(_switches);
     154           8 :   tetgen_wrapper.run_tetgen();
     155           8 :   unsigned int num_elements   = tetgen_wrapper.get_numberoftrifaces();
     156             : 
     157             :   // Delete *all* old elements.  Yes, we legally delete elements while
     158             :   // iterating over them because no entries from the underlying container
     159             :   // are actually erased.
     160          20 :   for (auto & elem : this->_mesh.element_ptr_range())
     161           8 :     this->_mesh.delete_elem (elem);
     162             : 
     163             :   // We just removed any boundary info associated with element faces
     164             :   // or edges, so let's update the boundary id caches.
     165          12 :   this->_mesh.get_boundary_info().regenerate_id_sets();
     166             : 
     167             :   // Add the 2D elements which comprise the convex hull back to the mesh.
     168             :   // Vector that temporarily holds the node labels defining element.
     169             :   unsigned int node_labels[3];
     170             : 
     171         104 :   for (unsigned int i=0; i<num_elements; ++i)
     172             :     {
     173          96 :       auto elem = Elem::build(TRI3);
     174             : 
     175             :       // Get node labels associated with this element
     176         384 :       for (auto j : elem->node_index_range())
     177         288 :         node_labels[j] = tetgen_wrapper.get_triface_node(i,j);
     178             : 
     179          96 :       this->assign_nodes_to_elem(node_labels, elem.get());
     180             : 
     181             :       // Finally, add this element to the mesh.
     182         192 :       this->_mesh.add_elem(std::move(elem));
     183             :     }
     184             : 
     185             :   // To the naked eye, a few smoothing iterations usually looks better.
     186             :   // We don't do this by default.
     187           8 :   if (this->_smooth_after_generating)
     188           0 :     LaplaceMeshSmoother(this->_mesh, 2).smooth();
     189           8 : }
     190             : 
     191             : 
     192             : 
     193             : 
     194             : 
     195           0 : void TetGenMeshInterface::triangulate_conformingDelaunayMesh (double quality_constraint,
     196             :                                                               double volume_constraint)
     197             : {
     198             :   // start triangulation method with empty holes list:
     199           0 :   std::vector<Point> noholes;
     200           0 :   triangulate_conformingDelaunayMesh_carvehole(noholes, quality_constraint, volume_constraint);
     201           0 : }
     202             : 
     203             : 
     204             : 
     205           4 : void TetGenMeshInterface::triangulate_conformingDelaunayMesh_carvehole  (const std::vector<Point> & holes,
     206             :                                                                          double quality_constraint,
     207             :                                                                          double volume_constraint)
     208             : {
     209             :   // Before calling this function, the Mesh must contain a convex hull
     210             :   // of TRI3 elements which define the boundary.
     211           6 :   auto hull_integrity_check = this->improve_hull_integrity();
     212             : 
     213             :   // Possibly die if hull integrity check failed
     214           4 :   this->process_hull_integrity_result(hull_integrity_check);
     215             : 
     216             :   // class tetgen_wrapper allows library access on a basic level
     217           8 :   TetGenWrapper tetgen_wrapper;
     218             : 
     219             :   // Copy Mesh's node points into TetGen data structure
     220           4 :   this->fill_pointlist(tetgen_wrapper);
     221             : 
     222             :   // >>> fill input structure "tetgenio" with facet data:
     223           4 :   int facet_num = this->_mesh.n_elem();
     224             : 
     225             :   // allocate memory in "tetgenio" structure:
     226             :   tetgen_wrapper.allocate_facetlist
     227           6 :     (facet_num, cast_int<int>(holes.size()));
     228             : 
     229             : 
     230             :   // Set up tetgen data structures with existing facet information
     231             :   // from the convex hull.
     232             :   {
     233           2 :     int insertnum = 0;
     234         102 :     for (auto & elem : this->_mesh.element_ptr_range())
     235             :       {
     236          96 :         tetgen_wrapper.allocate_facet_polygonlist(insertnum, 1);
     237          96 :         tetgen_wrapper.allocate_polygon_vertexlist(insertnum, 0, 3);
     238             : 
     239         432 :         for (auto j : elem->node_index_range())
     240             :           {
     241             :             // We need to get the sequential index of elem->node_ptr(j), but
     242             :             // it should already be stored in _sequential_to_libmesh_node_map...
     243         432 :             unsigned libmesh_node_id = elem->node_id(j);
     244             : 
     245             :             // The libmesh node IDs may not be sequential, but can we assume
     246             :             // they are at least in order???  We will do so here.
     247             :             std::vector<unsigned>::iterator node_iter =
     248             :               Utility::binary_find(_sequential_to_libmesh_node_map.begin(),
     249             :                                    _sequential_to_libmesh_node_map.end(),
     250         288 :                                    libmesh_node_id);
     251             : 
     252             :             // Check to see if not found: this could also indicate the sequential
     253             :             // node map is not sorted...
     254         288 :             libmesh_error_msg_if(node_iter == _sequential_to_libmesh_node_map.end(),
     255             :                                  "Global node " << libmesh_node_id << " not found in sequential node map!");
     256             : 
     257             :             int sequential_index = cast_int<int>
     258         144 :               (std::distance(_sequential_to_libmesh_node_map.begin(),
     259             :                              node_iter));
     260             : 
     261             :             // Debugging:
     262             :             //    libMesh::out << "libmesh_node_id=" << libmesh_node_id
     263             :             //         << ", sequential_index=" << sequential_index
     264             :             //         << std::endl;
     265             : 
     266         288 :             tetgen_wrapper.set_vertex(insertnum, // facet number
     267             :                                       0,         // polygon (always 0)
     268             :                                       j,         // local vertex index in tetgen input
     269             :                                       sequential_index);
     270             :           }
     271             : 
     272             :         // Go to next facet in polygonlist
     273          96 :         insertnum++;
     274             :       }
     275             :   }
     276             : 
     277             : 
     278             : 
     279             :   // fill hole list (if there are holes):
     280           4 :   if (holes.size() > 0)
     281             :     {
     282           2 :       unsigned hole_index = 0;
     283           8 :       for (Point ihole : holes)
     284           8 :         tetgen_wrapper.set_hole(hole_index++,
     285           2 :                                 REAL(ihole(0)),
     286           2 :                                 REAL(ihole(1)),
     287           2 :                                 REAL(ihole(2)));
     288             :     }
     289             : 
     290             : 
     291             :   // Run TetGen triangulation method
     292             : 
     293             :   // Assemble switches: we append the user's switches (if any) to
     294             :   //  - 'p'  tetrahedralize a piecewise linear complex
     295             :   //  - 'C'  check consistency of mesh (avoid inverted elements)
     296             :   //  (see definition and further options in user manual
     297             :   //  http://wias-berlin.de/software/tetgen/1.5/doc/manual/manual005.html )
     298           8 :   std::ostringstream oss;
     299           4 :   oss << "pC";
     300           2 :   oss << _switches;
     301             : 
     302           4 :   if (quality_constraint != 0)
     303           2 :     oss << "q" << std::fixed << quality_constraint;
     304             : 
     305           4 :   if (volume_constraint != 0)
     306           2 :     oss << "a" << std::fixed << volume_constraint;
     307             : 
     308           4 :   std::string params = oss.str();
     309             : 
     310           4 :   tetgen_wrapper.set_switches(params); // TetGen switches: Piecewise linear complex, Quiet mode
     311           4 :   tetgen_wrapper.run_tetgen();
     312             : 
     313             :   // => nodes:
     314           4 :   unsigned int old_nodesnum = this->_mesh.n_nodes();
     315           4 :   REAL x=0., y=0., z=0.;
     316           4 :   const unsigned int num_nodes = tetgen_wrapper.get_numberofpoints();
     317             : 
     318             :   // Debugging:
     319             :   // libMesh::out << "Original mesh had " << old_nodesnum << " nodes." << std::endl;
     320             :   // libMesh::out << "Reserving space for " << num_nodes << " total nodes." << std::endl;
     321             : 
     322             :   // Reserve space for additional nodes in the node map
     323           4 :   _sequential_to_libmesh_node_map.reserve(num_nodes);
     324             : 
     325             :   // Add additional nodes to the Mesh.
     326             :   // Original code had i<=num_nodes here (Note: the indexing is:
     327             :   // foo[3*i], [3*i+1], [3*i+2]) But according to the TetGen docs, "In
     328             :   // all cases, the first item in any array is stored starting at
     329             :   // index [0]."
     330        2932 :   for (unsigned int i=old_nodesnum; i<num_nodes; i++)
     331             :     {
     332             :       // Fill in x, y, z values
     333        2928 :       tetgen_wrapper.get_output_node(i, x,y,z);
     334             : 
     335             :       // Catch the node returned by add_point()... this will tell us the ID
     336             :       // assigned by the Mesh.
     337        4392 :       Node * new_node = this->_mesh.add_point ( Point(x,y,z) );
     338             : 
     339             :       // Store this new ID in our sequential-to-libmesh node mapping array
     340        2928 :       _sequential_to_libmesh_node_map.push_back( new_node->id() );
     341             :     }
     342             : 
     343             :   // Debugging:
     344             :   //  std::copy(_sequential_to_libmesh_node_map.begin(),
     345             :   //    _sequential_to_libmesh_node_map.end(),
     346             :   //    std::ostream_iterator<unsigned>(std::cout, " "));
     347             :   //  std::cout << std::endl;
     348             : 
     349             : 
     350             :   // => tetrahedra:
     351           4 :   const unsigned int num_elements = tetgen_wrapper.get_numberoftetrahedra();
     352             : 
     353             :   // Vector that temporarily holds the node labels defining element connectivity.
     354             :   unsigned int node_labels[4];
     355             : 
     356        9980 :   for (unsigned int i=0; i<num_elements; i++)
     357             :     {
     358             :       // TetGen only supports Tet4 elements.
     359        9976 :       auto elem = Elem::build(TET4);
     360             : 
     361             :       // Fill up the the node_labels vector
     362       49880 :       for (auto j : elem->node_index_range())
     363       39904 :         node_labels[j] = tetgen_wrapper.get_element_node(i,j);
     364             : 
     365             :       // Associate nodes with this element
     366        9976 :       this->assign_nodes_to_elem(node_labels, elem.get());
     367             : 
     368             :       // Finally, add this element to the mesh
     369       19952 :       this->_mesh.add_elem(std::move(elem));
     370             :     }
     371             : 
     372             :   // Delete original convex hull elements.  Is there ever a case where
     373             :   // we should not do this?
     374           4 :   this->delete_2D_hull_elements();
     375             : 
     376             :   // To the naked eye, a few smoothing iterations usually looks better.
     377             :   // We don't do this by default.
     378           4 :   if (this->_smooth_after_generating)
     379           0 :     LaplaceMeshSmoother(_mesh, 2).smooth();
     380           4 : }
     381             : 
     382             : 
     383             : 
     384             : 
     385             : 
     386        1092 : void TetGenMeshInterface::fill_pointlist(TetGenWrapper & wrapper)
     387             : {
     388             :   // fill input structure with point set data:
     389        1092 :   wrapper.allocate_pointlist( this->_mesh.n_nodes() );
     390             : 
     391             :   // Make enough space to store a mapping between the implied sequential
     392             :   // node numbering used in tetgen and libmesh's (possibly) non-sequential
     393             :   // numbering scheme.
     394        1092 :   _sequential_to_libmesh_node_map.clear();
     395        1092 :   _sequential_to_libmesh_node_map.resize( this->_mesh.n_nodes() );
     396             : 
     397             :   {
     398         546 :     unsigned index = 0;
     399        8014 :     for (auto & node : this->_mesh.node_ptr_range())
     400             :       {
     401        6376 :         _sequential_to_libmesh_node_map[index] = node->id();
     402       12752 :         wrapper.set_node(index++,
     403        3188 :                          REAL((*node)(0)),
     404        3188 :                          REAL((*node)(1)),
     405        3188 :                          REAL((*node)(2)));
     406             :       }
     407             :   }
     408        1092 : }
     409             : 
     410             : 
     411             : 
     412             : 
     413             : 
     414       13546 : void TetGenMeshInterface::assign_nodes_to_elem(unsigned * node_labels, Elem * elem)
     415             : {
     416       67634 :   for (auto j : elem->node_index_range())
     417             :     {
     418             :       // Get the mapped node index to ask the Mesh for
     419       54088 :       unsigned mapped_node_id = _sequential_to_libmesh_node_map[ node_labels[j] ];
     420             : 
     421       54088 :       Node * current_node = this->_mesh.node_ptr( mapped_node_id );
     422             : 
     423       54088 :       elem->set_node(j, current_node);
     424             :     }
     425       13546 : }
     426             : 
     427             : } // namespace libMesh
     428             : 
     429             : 
     430             : #endif // #ifdef LIBMESH_HAVE_TETGEN

Generated by: LCOV version 1.14