1 // Copyright (c) 2009 INRIA Sophia-Antipolis (France).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Mesh_3/include/CGAL/refine_mesh_3.h $
7 // $Id: refine_mesh_3.h 3e03d50 2021-05-05T15:32:22+02:00 Maxime Gimeno
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Stephane Tayeb
12 //
13 //******************************************************************************
14 // File Description : refine_mesh_3 function declaration and implementation.
15 //******************************************************************************
16
17 #ifndef CGAL_REFINE_MESH_3_H
18 #define CGAL_REFINE_MESH_3_H
19
20 #include <CGAL/license/Mesh_3.h>
21
22 #include <CGAL/disable_warnings.h>
23
24 #include <CGAL/config.h>
25 #include <CGAL/boost/parameter.h>
26 #include <CGAL/Mesh_3/config.h>
27 #include <CGAL/Mesh_3/Dump_c3t3.h>
28 #include <CGAL/Mesh_3/Mesher_3.h>
29 #include <CGAL/Mesh_error_code.h>
30 #include <CGAL/optimize_mesh_3.h>
31
32 #include <boost/parameter/preprocessor.hpp>
33
34 #include <atomic>
35
36 namespace CGAL {
37
38 namespace details {
39
40 /**
41 * @class Insert_vertex_in_c3t3
42 *
43 * A functor designed to insert unweighted points into the triangulation
44 * of a C3T3 from C3T3::Tr::Vertex , keeping the dimension and indices.
45 */
46 template <typename C3T3>
47 class Insert_vertex_in_c3t3
48 {
49 private:
50 typedef typename C3T3::Vertex_handle Vertex_handle;
51 typedef typename C3T3::Index Index;
52
53 typedef typename C3T3::Triangulation Tr;
54 typedef typename Tr::Geom_traits Geom_traits;
55 typedef typename Tr::Vertex Vertex;
56 typedef typename Tr::Weighted_point Weighted_point;
57 typedef typename Weighted_point::Weight Weight;
58
59 public:
Insert_vertex_in_c3t3(C3T3 & c3t3)60 Insert_vertex_in_c3t3(C3T3& c3t3)
61 : r_c3t3_(c3t3) {}
62
operator()63 void operator()(const Vertex& vertex) const
64 {
65 typename Geom_traits::Construct_point_3 cp =
66 r_c3t3_.triangulation().geom_traits().construct_point_3_object();
67 typename Geom_traits::Compute_weight_3 cw =
68 r_c3t3_.triangulation().geom_traits().compute_weight_3_object();
69
70 // Get vh properties
71 int dimension = vertex.in_dimension();
72 Weight w = (dimension < 2) ? cw(vertex.point()) : 0;
73 Weighted_point point(cp(vertex.point()), w);
74 Index index = vertex.index();
75
76 // Insert point and restore handle properties
77 Vertex_handle new_vertex = r_c3t3_.triangulation().insert(point);
78 r_c3t3_.set_index(new_vertex, index);
79 r_c3t3_.set_dimension(new_vertex, dimension);
80
81 #if defined(CGAL_LINKED_WITH_TBB)\
82 && !defined(CGAL_PARALLEL_MESH_3_DO_NOT_ADD_OUTSIDE_POINTS_ON_A_FAR_SPHERE)
83 if (boost::is_convertible<typename C3T3::Concurrency_tag, CGAL::Parallel_tag>::value)
84 {
85 if (dimension == -1)
86 r_c3t3_.add_far_point(new_vertex);
87 }
88 #endif
89 #ifdef CGAL_SEQUENTIAL_MESH_3_ADD_OUTSIDE_POINTS_ON_A_FAR_SPHERE
90 if (boost::is_convertible<typename C3T3::Concurrency_tag, CGAL::Sequential_tag>::value)
91 {
92 if (dimension == -1)
93 r_c3t3_.add_far_point(new_vertex);
94 }
95 #endif
96 }
97
98 private:
99 C3T3& r_c3t3_;
100 };
101
102 } // namespace details
103
104 namespace parameters {
105
106 namespace internal {
107
108 const int undef_parameter = -1;
109
110 // Helpers
111 struct Optimization_options_base
112 {
Optimization_options_baseOptimization_options_base113 Optimization_options_base(bool b)
114 : b_(b), time_limit_(undef_parameter), bound_(undef_parameter) {}
115
116 operator bool() const { return b_; }
117
is_time_limit_setOptimization_options_base118 bool is_time_limit_set() const { return time_limit_ != undef_parameter; }
set_time_limitOptimization_options_base119 void set_time_limit(double d) { time_limit_ = d; }
time_limitOptimization_options_base120 double time_limit() const { return time_limit_; }
121
is_bound_setOptimization_options_base122 bool is_bound_set() const { return bound_ != undef_parameter; }
set_boundOptimization_options_base123 void set_bound(double d) { bound_ = d; }
boundOptimization_options_base124 double bound() const { return bound_; }
125
126 private:
127 bool b_;
128 double time_limit_;
129 double bound_;
130 };
131
132 struct Global_optimization_options_base
133 {
Global_optimization_options_baseGlobal_optimization_options_base134 Global_optimization_options_base()
135 : convergence_(undef_parameter), max_it_nb_(undef_parameter) {}
136
is_convergence_setGlobal_optimization_options_base137 bool is_convergence_set() const { return convergence_ != undef_parameter; }
set_convergenceGlobal_optimization_options_base138 void set_convergence(double d) { convergence_ = d; }
convergenceGlobal_optimization_options_base139 double convergence() const { return convergence_; }
140
is_max_iteration_number_setGlobal_optimization_options_base141 bool is_max_iteration_number_set() const { return max_it_nb_ != undef_parameter; }
set_max_iteration_numberGlobal_optimization_options_base142 void set_max_iteration_number(int i) { max_it_nb_ = i; }
max_iteration_numberGlobal_optimization_options_base143 int max_iteration_number() const { return max_it_nb_; }
144
145 private:
146 double convergence_;
147 int max_it_nb_;
148 };
149
150 // Perturb
151 struct Perturb_options : public Optimization_options_base
152 {
Perturb_optionsPerturb_options153 Perturb_options(bool b) : Optimization_options_base(b) {}
154 };
155
156 // Exude
157 struct Exude_options : public Optimization_options_base
158 {
Exude_optionsExude_options159 Exude_options(bool b) : Optimization_options_base(b) {}
160 };
161
162 // Odt
163 struct Odt_options : public Optimization_options_base
164 , public Global_optimization_options_base
165 {
Odt_optionsOdt_options166 Odt_options(bool b) : Optimization_options_base(b)
167 , Global_optimization_options_base() {}
168 };
169
170 // Lloyd
171 struct Lloyd_options : public Optimization_options_base
172 , public Global_optimization_options_base
173 {
Lloyd_optionsLloyd_options174 Lloyd_options(bool b) : Optimization_options_base(b)
175 , Global_optimization_options_base() {}
176 };
177
178 // Manifold
179 struct Manifold_options {
180 enum {
181 NON_MANIFOLD = 0,
182 MANIFOLD_WITH_BOUNDARY = 8,
183 NO_BOUNDARY = 16,
184 MANIFOLD = 24
185 };
186
Manifold_optionsManifold_options187 Manifold_options(const int topology)
188 : mesh_topology(topology)
189 {}
Manifold_optionsManifold_options190 Manifold_options()
191 : mesh_topology(NON_MANIFOLD)
192 {}
193
194 int mesh_topology;
195 };
196
197 // Various Mesh_3 option
198 struct Mesh_3_options {
199 #ifndef CGAL_NO_ATOMIC
200 typedef std::atomic<bool>* Pointer_to_stop_atomic_boolean_t;
201 #else
202 typedef bool* Pointer_to_stop_atomic_boolean_t;
203 #endif
204 Mesh_3_options(bool nonlinear = false)
205 // This parameter `nonlinear` adds a compatibility with previous
206 // API of the constructor of `C3t3_initializer`.
207 // -- Laurent Rineau, 2019/05/03
dump_after_init_prefixMesh_3_options208 : dump_after_init_prefix()
209 , dump_after_refine_surface_prefix()
210 , dump_after_refine_prefix()
211 , dump_after_glob_opt_prefix()
212 , dump_after_perturb_prefix()
213 , dump_after_exude_prefix()
214 , number_of_initial_points(-1)
215 , nonlinear_growth_of_balls(nonlinear)
216 , maximal_number_of_vertices(0)
217 , pointer_to_error_code(0)
218 #ifndef CGAL_NO_ATOMIC
219 , pointer_to_stop_atomic_boolean(0)
220 #endif
221 {}
222
223 std::string dump_after_init_prefix;
224 std::string dump_after_refine_surface_prefix;
225 std::string dump_after_refine_prefix;
226 std::string dump_after_glob_opt_prefix;
227 std::string dump_after_perturb_prefix;
228 std::string dump_after_exude_prefix;
229 int number_of_initial_points;
230 bool nonlinear_growth_of_balls;
231 std::size_t maximal_number_of_vertices;
232 Mesh_error_code* pointer_to_error_code;
233 #ifndef CGAL_NO_ATOMIC
234 Pointer_to_stop_atomic_boolean_t pointer_to_stop_atomic_boolean;
235 #endif
236
237 }; // end struct Mesh_3_options
238
239 } // end namespace internal
240
241 #if defined(BOOST_MSVC)
242 # pragma warning(push)
243 # pragma warning(disable:4003) // not enough actual parameters for macro
244 #endif
245
246 // see <CGAL/config.h>
247 CGAL_PRAGMA_DIAG_PUSH
248 // see <CGAL/boost/parameter.h>
249 CGAL_IGNORE_BOOST_PARAMETER_NAME_WARNINGS
250
251
252 // -----------------------------------
253 // Perturb
254 // -----------------------------------
255 BOOST_PARAMETER_FUNCTION((internal::Perturb_options), perturb, tag,
256 (optional (time_limit_, *, internal::undef_parameter )
257 (sliver_bound_, *, default_values::perturb_sliver_bound )))
258 {
259 internal::Perturb_options options(true);
260
261 if ( internal::undef_parameter != time_limit_ )
262 options.set_time_limit(time_limit_);
263
264 options.set_bound(sliver_bound_);
265
266 return options;
267 }
268
no_perturb()269 inline internal::Perturb_options no_perturb() { return internal::Perturb_options(false); }
270
271 // -----------------------------------
272 // Exude
273 // -----------------------------------
274 BOOST_PARAMETER_FUNCTION((internal::Exude_options), exude, tag,
275 (optional (time_limit_, *, internal::undef_parameter )
276 (sliver_bound_, *, default_values::exude_sliver_bound )))
277 {
278 internal::Exude_options options(true);
279
280 if ( internal::undef_parameter != time_limit_ )
281 options.set_time_limit(time_limit_);
282
283 options.set_bound(sliver_bound_);
284
285 return options;
286 }
287
no_exude()288 inline internal::Exude_options no_exude() { return internal::Exude_options(false); }
289
290 // -----------------------------------
291 // Odt
292 // -----------------------------------
293 BOOST_PARAMETER_FUNCTION((internal::Odt_options), odt, tag,
294 (optional (time_limit_, *, 0 )
295 (max_iteration_number_, *, 0 )
296 (convergence_, *, default_values::odt_convergence_ratio )
297 (freeze_bound_, *, default_values::odt_freeze_ratio )))
298 {
299 internal::Odt_options options(true);
300
301 options.set_time_limit(time_limit_);
302 options.set_bound(freeze_bound_);
303 options.set_convergence(convergence_);
304 options.set_max_iteration_number(max_iteration_number_);
305
306 return options;
307 }
308
no_odt()309 inline internal::Odt_options no_odt() { return internal::Odt_options(false); }
310
311 // -----------------------------------
312 // Lloyd
313 // -----------------------------------
314 BOOST_PARAMETER_FUNCTION((internal::Lloyd_options), lloyd, tag,
315 (optional (time_limit_, *, 0 )
316 (max_iteration_number_, *, 0 )
317 (convergence_, *, default_values::lloyd_convergence_ratio )
318 (freeze_bound_, *, default_values::lloyd_freeze_ratio )))
319 {
320 internal::Lloyd_options options(true);
321
322 options.set_time_limit(time_limit_);
323 options.set_bound(freeze_bound_);
324 options.set_convergence(convergence_);
325 options.set_max_iteration_number(max_iteration_number_);
326
327 return options;
328 }
329
no_lloyd()330 inline internal::Lloyd_options no_lloyd() { return internal::Lloyd_options(false); }
331
332 // -----------------------------------
333 // Manifold options ------------------
334 // -----------------------------------
335 BOOST_PARAMETER_FUNCTION((internal::Manifold_options), manifold_options, tag,
336 (optional
337 (mesh_topology_, (int), -1)
338 )
339 )
340 {
341 internal::Manifold_options options;
342 options.mesh_topology = mesh_topology_;
343 return options;
344 }
345
manifold()346 inline internal::Manifold_options manifold()
347 {
348 return internal::Manifold_options(
349 internal::Manifold_options::MANIFOLD);
350 }
manifold_with_boundary()351 inline internal::Manifold_options manifold_with_boundary()
352 {
353 return internal::Manifold_options(
354 internal::Manifold_options::MANIFOLD_WITH_BOUNDARY);
355 }
non_manifold()356 inline internal::Manifold_options non_manifold()
357 {
358 return internal::Manifold_options(
359 internal::Manifold_options::NON_MANIFOLD);
360 }
361
362 // -----------------------------------
363 // Mesh options
364 // -----------------------------------
365
366 // Undocumented Boost parameter for refine_mesh_3 and make_mesh_3.
367 // Allows to dump the mesh at given stage of the mesh generation
368 // algorithm.
369 BOOST_PARAMETER_FUNCTION((internal::Mesh_3_options), mesh_3_options, tag,
370 (optional
371 (dump_after_init_prefix_, (std::string), "" )
372 (dump_after_refine_surface_prefix_, (std::string), "" )
373 (dump_after_refine_prefix_, (std::string), "" )
374 (dump_after_glob_opt_prefix_, (std::string), "" )
375 (dump_after_perturb_prefix_, (std::string), "" )
376 (dump_after_exude_prefix_, (std::string), "" )
377 (number_of_initial_points_, (int), -1)
378 (maximal_number_of_vertices_, (std::size_t), 0)
379 (nonlinear_growth_of_balls_, (bool), false)
380 (pointer_to_error_code_, (Mesh_error_code*), ((Mesh_error_code*)0))
381 (pointer_to_stop_atomic_boolean_, (internal::Mesh_3_options::Pointer_to_stop_atomic_boolean_t), ((internal::Mesh_3_options::Pointer_to_stop_atomic_boolean_t)0))
382 )
383 )
384 {
385 internal::Mesh_3_options options;
386
387 options.dump_after_init_prefix=dump_after_init_prefix_;
388 options.dump_after_refine_surface_prefix=dump_after_refine_surface_prefix_;
389 options.dump_after_refine_prefix=dump_after_refine_prefix_;
390 options.dump_after_glob_opt_prefix=dump_after_glob_opt_prefix_;
391 options.dump_after_perturb_prefix=dump_after_perturb_prefix_;
392 options.dump_after_exude_prefix=dump_after_exude_prefix_;
393 options.number_of_initial_points=number_of_initial_points_;
394 options.nonlinear_growth_of_balls = nonlinear_growth_of_balls_;
395 options.maximal_number_of_vertices=maximal_number_of_vertices_;
396 options.pointer_to_error_code=pointer_to_error_code_;
397 #ifndef CGAL_NO_ATOMIC
398 options.pointer_to_stop_atomic_boolean=pointer_to_stop_atomic_boolean_;
399 #endif
400
401 return options;
402 }
403
404 // Undocumented Boost parameter for refine_mesh_3 and make_mesh_3.
405 // Default Mesh_3_options: dump at every stage of the mesh generation.
mesh_3_dump()406 inline internal::Mesh_3_options mesh_3_dump()
407 {
408 internal::Mesh_3_options options;
409
410 options.dump_after_init_prefix = "mesh_dump_after_init";
411 options.dump_after_refine_surface_prefix = "mesh_dump_after_refine_surface";
412 options.dump_after_refine_prefix = "mesh_dump_after_refine";
413 options.dump_after_glob_opt_prefix = "mesh_dump_after_glob_opt";
414 options.dump_after_perturb_prefix = "mesh_dump_after_perturb";
415 options.dump_after_exude_prefix = "mesh_dump_after_exude";
416
417 return options;
418 }
419
420 CGAL_PRAGMA_DIAG_POP
421
422 #if defined(BOOST_MSVC)
423 # pragma warning(pop)
424 #endif
425
426 // -----------------------------------
427 // Reset_c3t3 (undocumented)
428 // -----------------------------------
429 CGAL_BOOLEAN_PARAMETER(Reset,reset_c3t3,no_reset_c3t3)
430 // CGAL_BOOLEAN_PARAMETER defined in <CGAL/boost/parameter.h>
431
432
433 // see <CGAL/config.h>
434 CGAL_PRAGMA_DIAG_PUSH
435 // see <CGAL/boost/parameter.h>
436 CGAL_IGNORE_BOOST_PARAMETER_NAME_WARNINGS
437
438 // -----------------------------------
439 // Parameters
440 // -----------------------------------
441 BOOST_PARAMETER_NAME( exude_param )
442 BOOST_PARAMETER_NAME( perturb_param )
443 BOOST_PARAMETER_NAME( odt_param )
444 BOOST_PARAMETER_NAME( lloyd_param )
445 BOOST_PARAMETER_NAME( reset_param )
446 BOOST_PARAMETER_NAME( mesh_options_param )
447 BOOST_PARAMETER_NAME( manifold_options_param )
448
449 CGAL_PRAGMA_DIAG_POP
450
451 } // end namespace parameters
452
453
454
455 #if defined(BOOST_MSVC)
456 # pragma warning(push)
457 # pragma warning(disable:4003) // not enough actual parameters for macro
458 #endif
459
460 // see <CGAL/config.h>
461 CGAL_PRAGMA_DIAG_PUSH
462 // see <CGAL/boost/parameter.h>
463 CGAL_IGNORE_BOOST_PARAMETER_NAME_WARNINGS
464
465 BOOST_PARAMETER_FUNCTION(
466 (void),
467 refine_mesh_3,
468 parameters::tag,
469 (required (in_out(c3t3),*) (domain,*) (criteria,*) ) // nondeduced
470 (deduced
471 (optional
472 (exude_param, (parameters::internal::Exude_options), parameters::exude())
473 (perturb_param, (parameters::internal::Perturb_options), parameters::perturb())
474 (odt_param, (parameters::internal::Odt_options), parameters::no_odt())
475 (lloyd_param, (parameters::internal::Lloyd_options), parameters::no_lloyd())
476 (reset_param, (parameters::Reset), parameters::reset_c3t3())
477 (mesh_options_param, (parameters::internal::Mesh_3_options),
478 parameters::internal::Mesh_3_options())
479 (manifold_options_param, (parameters::internal::Manifold_options),
480 parameters::internal::Manifold_options())
481 )
482 )
483 )
484 {
485 return refine_mesh_3_impl(c3t3,
486 domain,
487 criteria,
488 exude_param,
489 perturb_param,
490 odt_param,
491 lloyd_param,
492 reset_param(),
493 mesh_options_param,
494 manifold_options_param);
495 }
496
497 CGAL_PRAGMA_DIAG_POP
498
499 #if defined(BOOST_MSVC)
500 # pragma warning(pop)
501 #endif
502
503 /**
504 * @brief This function refines the mesh c3t3 wrt domain & criteria
505 *
506 * @param c3t3 the mesh to be refined.
507 * @param domain the domain to be discretized
508 * @param criteria the criteria
509 * @param exude if \c true, an exudation step will be done at
510 * the end of the Delaunay refinement process
511 * @param perturb if \c true, an explicit vertex perturbation step will be
512 * done at the end of refinement process
513 * @param reset_c3t3 if \c true, a new C3T3 will be construct from param c3t3.
514 * The new c3t3 keeps only the vertices (as NON-weighted points with their
515 * dimension and Index) of the triangulation. That allows to refine a mesh
516 * which has been exuded.
517 * @param mesh_3_options is a struct object used to pass non-documented options,
518 * for debugging purpose.
519 */
520 template<class C3T3, class MeshDomain, class MeshCriteria>
521 void refine_mesh_3_impl(C3T3& c3t3,
522 const MeshDomain& domain,
523 const MeshCriteria& criteria,
524 const parameters::internal::Exude_options& exude,
525 const parameters::internal::Perturb_options& perturb,
526 const parameters::internal::Odt_options& odt,
527 const parameters::internal::Lloyd_options& lloyd,
528 bool reset_c3t3,
529 const parameters::internal::Mesh_3_options&
530 mesh_options = parameters::internal::Mesh_3_options(),
531 const parameters::internal::Manifold_options&
532 manifold_options = parameters::internal::Manifold_options())
533 {
534 // Note: this function is almost entirely copied in refine_periodic_3_mesh.h
535 // and any change to this function should likely be ported to the periodic version.
536
537 typedef Mesh_3::Mesher_3<C3T3, MeshCriteria, MeshDomain> Mesher;
538
539 // Reset c3t3 (i.e. remove weights) if needed
540 if ( reset_c3t3 )
541 {
542 C3T3 tmp_c3t3;
543 std::for_each(c3t3.triangulation().finite_vertices_begin(),
544 c3t3.triangulation().finite_vertices_end(),
545 details::Insert_vertex_in_c3t3<C3T3>(tmp_c3t3));
546 // TODO: corners and edges are not restored
547 c3t3.swap(tmp_c3t3);
548 }
549
550 dump_c3t3(c3t3, mesh_options.dump_after_init_prefix);
551
552 // Build mesher and launch refinement process
553 Mesher mesher (c3t3, domain, criteria, manifold_options.mesh_topology,
554 mesh_options.maximal_number_of_vertices,
555 mesh_options.pointer_to_error_code
556 #ifndef CGAL_NO_ATOMIC
557 , mesh_options.pointer_to_stop_atomic_boolean
558 #endif
559 );
560 double refine_time = mesher.refine_mesh(mesh_options.dump_after_refine_surface_prefix);
561 c3t3.clear_manifold_info();
562
563 dump_c3t3(c3t3, mesh_options.dump_after_refine_prefix);
564
565 // Odt
566 if ( odt )
567 {
568 odt_optimize_mesh_3(c3t3,
569 domain,
570 parameters::time_limit = odt.time_limit(),
571 parameters::max_iteration_number = odt.max_iteration_number(),
572 parameters::convergence = odt.convergence(),
573 parameters::freeze_bound = odt.bound());
574 }
575
576 // Lloyd
577 if ( lloyd )
578 {
579 lloyd_optimize_mesh_3(c3t3,
580 domain,
581 parameters::time_limit = lloyd.time_limit(),
582 parameters::max_iteration_number = lloyd.max_iteration_number(),
583 parameters::convergence = lloyd.convergence(),
584 parameters::freeze_bound = lloyd.bound());
585 }
586
587 if( odt || lloyd) {
588 dump_c3t3(c3t3, mesh_options.dump_after_glob_opt_prefix);
589 }
590
591 // Perturbation
592 if ( perturb )
593 {
594 double perturb_time_limit = refine_time;
595
596 if ( perturb.is_time_limit_set() )
597 perturb_time_limit = perturb.time_limit();
598
599 perturb_mesh_3(c3t3,
600 domain,
601 parameters::time_limit = perturb_time_limit,
602 parameters::sliver_bound = perturb.bound());
603
604 dump_c3t3(c3t3, mesh_options.dump_after_perturb_prefix);
605 }
606
607 // Exudation
608 if ( exude )
609 {
610 double exude_time_limit = refine_time;
611
612 if ( exude.is_time_limit_set() )
613 exude_time_limit = exude.time_limit();
614
615 exude_mesh_3(c3t3,
616 parameters::time_limit = exude_time_limit,
617 parameters::sliver_bound = exude.bound());
618
619 dump_c3t3(c3t3, mesh_options.dump_after_exude_prefix);
620 }
621 }
622
623 } // end namespace CGAL
624
625 #include <CGAL/enable_warnings.h>
626
627 #endif // CGAL_REFINE_MESH_3_H
628