1 // Copyright (c) 2004-2005 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/Mesher_level/include/CGAL/Mesher_level.h $ 7 // $Id: Mesher_level.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Laurent RINEAU 12 13 #ifndef CGAL_MESHER_LEVEL_H 14 #define CGAL_MESHER_LEVEL_H 15 16 #include <string> 17 18 namespace CGAL { 19 20 enum Mesher_level_conflict_status { 21 NO_CONFLICT = 0, 22 CONFLICT_BUT_ELEMENT_CAN_BE_RECONSIDERED, 23 CONFLICT_AND_ELEMENT_SHOULD_BE_DROPPED 24 }; 25 26 struct Null_mesher_level { 27 28 template <typename Visitor> refineNull_mesher_level29 void refine(Visitor) {} 30 31 template <typename P, typename Z> test_point_conflict_from_superiorNull_mesher_level32 Mesher_level_conflict_status test_point_conflict_from_superior(P, Z) 33 { 34 return NO_CONFLICT; 35 } 36 is_algorithm_doneNull_mesher_level37 bool is_algorithm_done() const 38 { 39 return true; 40 } 41 42 template <typename Visitor> try_to_insert_one_pointNull_mesher_level43 bool try_to_insert_one_point(Visitor) 44 { 45 return false; 46 } 47 48 template <typename Visitor> one_stepNull_mesher_level49 bool one_step(Visitor) 50 { 51 return false; 52 } 53 debug_infoNull_mesher_level54 std::string debug_info() const 55 { 56 return ""; 57 } debug_info_headerNull_mesher_level58 std::string debug_info_header() const 59 { 60 return ""; 61 } 62 63 }; // end Null_mesher_level 64 65 template < 66 class Tr, /**< The triangulation type. */ 67 class Derived, /**< Derived class, that implements methods. */ 68 class Element, /**< Type of elements that this level refines. */ 69 class Previous, /* = Null_mesher_level, */ 70 /**< Previous level type, defaults to 71 \c Null_mesher_level. */ 72 class Triangulation_traits /** Traits class that defines types for the 73 triangulation. */ 74 > 75 class Mesher_level 76 { 77 public: 78 /** Type of triangulation that is meshed. */ 79 typedef Tr Triangulation; 80 /** Type of point that are inserted into the triangulation. */ 81 typedef typename Triangulation::Point Point; 82 /** Type of vertex handles that are returns by insertions into the 83 triangulation. */ 84 typedef typename Triangulation::Vertex_handle Vertex_handle; 85 /** Type of the conflict zone for a point that can be inserted. */ 86 typedef typename Triangulation_traits::Zone Zone; 87 88 typedef Element Element_type; 89 typedef Previous Previous_level; 90 91 private: 92 /** \name Private member functions */ 93 94 /** Curiously recurring template pattern. */ 95 //@{ derived()96 Derived& derived() 97 { 98 return static_cast<Derived&>(*this); 99 } 100 derived()101 const Derived& derived() const 102 { 103 return static_cast<const Derived&>(*this); 104 } 105 //@} 106 107 /** \name Private member datas */ 108 109 Previous& previous_level; /**< The previous level of the refinement 110 process. */ 111 public: 112 typedef Mesher_level<Tr, 113 Derived, 114 Element, 115 Previous_level, 116 Triangulation_traits> Self; 117 118 /** \name CONSTRUCTORS */ Mesher_level(Previous_level & previous)119 Mesher_level(Previous_level& previous) 120 : previous_level(previous) 121 { 122 } 123 124 /** \name FUNCTIONS IMPLEMENTED IN THE CLASS \c Derived */ 125 126 /** Access to the triangulation */ triangulation()127 Triangulation& triangulation() 128 { 129 return derived().triangulation_ref_impl(); 130 } 131 132 /** Access to the triangulation */ triangulation()133 const Triangulation& triangulation() const 134 { 135 return derived().triangulation_ref_impl(); 136 } 137 previous()138 const Previous_level& previous() const 139 { 140 return previous_level; 141 } 142 insert(Point p,Zone & z)143 Vertex_handle insert(Point p, Zone& z) 144 { 145 return derived().insert_impl(p, z); 146 } 147 conflicts_zone(const Point & p,Element e)148 Zone conflicts_zone(const Point& p, Element e) 149 { 150 return derived().conflicts_zone_impl(p, e); 151 } 152 153 /** Called before the first refinement, to initialized the queue of 154 elements that should be refined. */ scan_triangulation()155 void scan_triangulation() 156 { 157 derived().scan_triangulation_impl(); 158 } 159 160 /** Tells if, as regards the elements of type \c Element, the refinement is 161 done. */ no_longer_element_to_refine()162 bool no_longer_element_to_refine() 163 { 164 return derived().no_longer_element_to_refine_impl(); 165 } 166 167 /** Retrieves the next element that could be refined. */ get_next_element()168 Element get_next_element() 169 { 170 return derived().get_next_element_impl(); 171 } 172 173 /** Remove from the list the next element that could be refined. */ pop_next_element()174 void pop_next_element() 175 { 176 derived().pop_next_element_impl(); 177 } 178 179 /** Gives the point that should be inserted to refine the element \c e */ refinement_point(const Element & e)180 Point refinement_point(const Element& e) 181 { 182 return derived().refinement_point_impl(e); 183 } 184 185 /** Actions before testing conflicts for point \c p and element \c e */ 186 template <typename Mesh_visitor> before_conflicts(const Element & e,const Point & p,Mesh_visitor visitor)187 void before_conflicts(const Element& e, const Point& p, 188 Mesh_visitor visitor) 189 { 190 visitor.before_conflicts(e, p); 191 derived().before_conflicts_impl(e, p); 192 } 193 194 /** Tells if, as regards this level of the refinement process, if the 195 point conflicts with something, and do what is needed. The return 196 type is made of two booleans: 197 - the first one tells if the point can be inserted, 198 - in case of, the first one is \c false, the second one tells if 199 the tested element should be reconsidered latter. 200 */ private_test_point_conflict(const Point & p,Zone & zone)201 Mesher_level_conflict_status private_test_point_conflict(const Point& p, 202 Zone& zone) 203 { 204 return derived().private_test_point_conflict_impl(p, zone); 205 } 206 207 /** Tells if, as regards this level of the refinement process, if the 208 point conflicts with something, and do what is needed. The return 209 type is made of two booleans: 210 - the first one tells if the point can be inserted, 211 - in case of, the first one is \c false, the second one tells if 212 the tested element should be reconsidered latter. 213 This function is called by the superior level, if any. 214 */ 215 Mesher_level_conflict_status test_point_conflict_from_superior(const Point & p,Zone & zone)216 test_point_conflict_from_superior(const Point& p, 217 Zone& zone) 218 { 219 return derived().test_point_conflict_from_superior_impl(p, zone); 220 } 221 222 /** 223 * Actions before inserting the point \c p in order to refine the 224 * element \c e. The zone of conflicts is \c zone. 225 */ 226 template <class Mesh_visitor> before_insertion(Element & e,const Point & p,Zone & zone,Mesh_visitor visitor)227 void before_insertion(Element& e, const Point& p, Zone& zone, 228 Mesh_visitor visitor) 229 { 230 visitor.before_insertion(e, p, zone); 231 derived().before_insertion_impl(e, p, zone); 232 } 233 234 /** Actions after having inserted the point. 235 * \param vh is the vertex handle of the inserted point, 236 * \param visitor is the visitor. 237 */ 238 template <class Mesh_visitor> after_insertion(Vertex_handle vh,Mesh_visitor visitor)239 void after_insertion(Vertex_handle vh, Mesh_visitor visitor) 240 { 241 derived().after_insertion_impl(vh); 242 visitor.after_insertion(vh); 243 } 244 245 /** Actions after testing conflicts for point \c p and element \c e 246 * if no point is inserted. */ 247 template <class Mesh_visitor> after_no_insertion(const Element & e,const Point & p,Zone & zone,Mesh_visitor visitor)248 void after_no_insertion(const Element& e, const Point& p, Zone& zone, 249 Mesh_visitor visitor) 250 { 251 derived().after_no_insertion_impl(e, p, zone); 252 visitor.after_no_insertion(e, p, zone); 253 } 254 255 /** \name MESHING PROCESS 256 * 257 * The following functions use the functions that are implemented in the 258 * derived classes. 259 * 260 */ 261 262 /** 263 * Tells it the algorithm is done, regarding elements of type \c Element 264 * or elements of previous levels. 265 */ is_algorithm_done()266 bool is_algorithm_done() 267 { 268 return ( previous_level.is_algorithm_done() && 269 no_longer_element_to_refine() ); 270 } 271 272 /** Refines elements of this level and previous levels. */ 273 template <class Mesh_visitor> refine(Mesh_visitor visitor)274 void refine(Mesh_visitor visitor) 275 { 276 while(! is_algorithm_done() ) 277 { 278 previous_level.refine(visitor.previous_level()); 279 if(! no_longer_element_to_refine() ) 280 process_one_element(visitor); 281 } 282 } 283 284 /** 285 * This function takes one element from the queue, and try to refine 286 * it. It returns \c true if one point has been inserted. 287 * @todo Merge with try_to_refine_element(). 288 */ 289 template <class Mesh_visitor> process_one_element(Mesh_visitor visitor)290 bool process_one_element(Mesh_visitor visitor) 291 { 292 Element e = get_next_element(); 293 294 const Mesher_level_conflict_status result 295 = try_to_refine_element(e, visitor); 296 297 if(result == CONFLICT_AND_ELEMENT_SHOULD_BE_DROPPED) 298 pop_next_element(); 299 return result == NO_CONFLICT; 300 } 301 302 template <class Mesh_visitor> 303 Mesher_level_conflict_status try_to_refine_element(Element e,Mesh_visitor visitor)304 try_to_refine_element(Element e, Mesh_visitor visitor) 305 { 306 const Point& p = refinement_point(e); 307 308 before_conflicts(e, p, visitor); 309 310 Zone zone = conflicts_zone(p, e); 311 312 const Mesher_level_conflict_status result = test_point_conflict(p, zone); 313 #ifdef CGAL_MESHES_DEBUG_REFINEMENT_POINTS 314 std::cerr << "(" << p << ") "; 315 switch( result ) 316 { 317 case NO_CONFLICT: 318 std::cerr << "accepted\n"; 319 break; 320 case CONFLICT_BUT_ELEMENT_CAN_BE_RECONSIDERED: 321 std::cerr << "rejected (temporarily)\n"; 322 break; 323 case CONFLICT_AND_ELEMENT_SHOULD_BE_DROPPED: 324 std::cerr << "rejected (permanent)\n"; 325 break; 326 } 327 #endif 328 329 if(result == NO_CONFLICT) 330 { 331 before_insertion(e, p, zone, visitor); 332 333 Vertex_handle v = insert(p, zone); 334 335 after_insertion(v, visitor); 336 337 return NO_CONFLICT; 338 } 339 else 340 after_no_insertion(e, p, zone, visitor); 341 return result; 342 } 343 344 /** Return (can_split_the_element, drop_element). */ 345 Mesher_level_conflict_status test_point_conflict(const Point & p,Zone & zone)346 test_point_conflict(const Point& p, Zone& zone) 347 { 348 const Mesher_level_conflict_status result = 349 previous_level.test_point_conflict_from_superior(p, zone); 350 351 if( result != NO_CONFLICT ) 352 return result; 353 return private_test_point_conflict(p, zone); 354 } 355 356 /** \name STEP BY STEP FUNCTIONS */ 357 358 /** 359 * Inserts exactly one point, if possible, and returns \c false if no 360 * point has been inserted because the algorithm is done. 361 */ 362 template <class Mesh_visitor> try_to_insert_one_point(Mesh_visitor visitor)363 bool try_to_insert_one_point(Mesh_visitor visitor) 364 { 365 while(! is_algorithm_done() ) 366 { 367 if( previous_level.try_to_insert_one_point(visitor.previous_level()) ) 368 return true; 369 if(! no_longer_element_to_refine() ) 370 if( process_one_element(visitor) ) 371 return true; 372 } 373 return false; 374 } 375 376 /** 377 * Applies one step of the algorithm: tries to refine one element of 378 * previous level or one element of this level. Return \c false iff 379 * <tt> is_algorithm_done()==true </tt>. 380 */ 381 template <class Mesh_visitor> one_step(Mesh_visitor visitor)382 bool one_step(Mesh_visitor visitor) 383 { 384 if( ! previous_level.is_algorithm_done() ) 385 previous_level.one_step(visitor.previous_level()); 386 else 387 if( ! no_longer_element_to_refine() ) 388 process_one_element(visitor); 389 return ! is_algorithm_done(); 390 } 391 392 }; // end Mesher_level 393 394 } // end namespace CGAL 395 396 #include <CGAL/Mesher_level_visitors.h> 397 #include <CGAL/Mesher_level_default_implementations.h> 398 399 #endif // CGAL_MESHER_LEVEL_H 400