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
|