1 // Copyright (c) 1997-2000 Max-Planck-Institute Saarbruecken (Germany). 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/Nef_3/include/CGAL/Nef_3/SNC_SM_overlayer.h $ 7 // $Id: SNC_SM_overlayer.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de> 12 // Peter Hachenberger <hachenberger@mpi-sb.mpg.de> 13 14 #ifndef CGAL_SNC_SM_OVERLAYER_H 15 #define CGAL_SNC_SM_OVERLAYER_H 16 17 #include <CGAL/license/Nef_3.h> 18 19 20 #include <CGAL/basic.h> 21 #include <CGAL/Union_find.h> 22 #include <CGAL/Nef_2/Segment_overlay_traits.h> 23 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO 24 #include <CGAL/Nef_2/geninfo.h> 25 #else 26 #include <boost/any.hpp> 27 #endif 28 #include <CGAL/Nef_S2/Sphere_geometry.h> 29 #include <CGAL/Nef_S2/SM_decorator.h> 30 #include <CGAL/Nef_S2/SM_const_decorator.h> 31 #include <CGAL/Nef_S2/SM_overlayer.h> 32 #include <CGAL/Nef_3/SNC_structure.h> 33 #include <CGAL/Nef_3/SNC_indexed_items.h> 34 35 #undef CGAL_NEF_DEBUG 36 #define CGAL_NEF_DEBUG 131 37 #include <CGAL/Nef_2/debug.h> 38 39 #ifndef CGAL_USE_LEDA 40 #define LEDA_MEMORY(t) 41 #endif 42 43 namespace CGAL { 44 45 /*{\Manpage {SNC_SM_overlayer}{Refs_}{Overlay in the sphere}{O}}*/ 46 47 template <typename Items, typename SM_decorator_> 48 class SNC_SM_overlayer : public SM_overlayer<SM_decorator_> { 49 public: 50 51 typedef SM_decorator_ SM_decorator; 52 typedef typename SM_decorator::Map Map; 53 typedef SM_overlayer<SM_decorator_> Base; 54 typedef SNC_SM_overlayer<Items, SM_decorator_> Self; 55 56 typedef typename Base::SVertex_handle SVertex_handle; 57 typedef typename Base::SHalfedge_handle SHalfedge_handle; 58 typedef typename Base::SHalfloop_handle SHalfloop_handle; 59 typedef typename Base::SFace_handle SFace_handle; 60 typedef typename Base::SVertex_iterator SVertex_iterator; 61 typedef typename Base::SHalfedge_iterator SHalfedge_iterator; 62 typedef typename Base::SFace_iterator SFace_iterator; 63 typedef typename Base::SHalfedge_around_sface_circulator 64 SHalfedge_around_sface_circulator; 65 66 typedef typename Base::Sphere_kernel Sphere_kernel; 67 68 typedef typename Map::Infi_box Infi_box; 69 70 using Base::clear_face_cycle_entries; 71 using Base::link_as_loop; 72 using Base::is_closed_at_source; 73 using Base::is_isolated; 74 using Base::delete_edge_pair; 75 using Base::delete_vertex_only; 76 using Base::delete_face_only; 77 using Base::store_sm_boundary_object; 78 using Base::first_out_edge; 79 using Base::set_face; 80 using Base::has_outdeg_two; 81 using Base::convert_edge_to_loop; 82 using Base::merge_edge_pairs_at_target; 83 84 public: 85 SNC_SM_overlayer(Map* M, 86 const Sphere_kernel& G = Sphere_kernel()) Base(M,G)87 : Base(M,G) {} 88 89 template <typename Association> simplify(Association &)90 void simplify(Association&) { 91 CGAL_NEF_TRACEN("simplifying"); 92 93 typedef typename CGAL::Union_find<SFace_handle>::handle Union_find_handle; 94 CGAL::Unique_hash_map< SFace_handle, Union_find_handle> Pitem(nullptr); 95 CGAL::Unique_hash_map< SVertex_handle, Union_find_handle> Vitem(nullptr); 96 CGAL::Union_find< SFace_handle> UF; 97 98 SFace_iterator f; 99 CGAL_forall_sfaces(f,*this) { 100 Pitem[f] = UF.make_set(f); 101 clear_face_cycle_entries(f); 102 } 103 104 if ( this->has_shalfloop() ) { 105 SHalfloop_handle l = this->shalfloop(); 106 SFace_handle f = *(UF.find(Pitem[l->incident_sface()])); 107 link_as_loop(l,f); 108 f = *(UF.find(Pitem[l->twin()->incident_sface()])); 109 link_as_loop(l->twin(),f); 110 } 111 112 SHalfedge_iterator e, en; 113 for(e = this->shalfedges_begin(); e != this->shalfedges_end(); e = en) { 114 en = e; ++en; if ( en==e->twin() ) ++en; 115 CGAL_NEF_TRACEN("can simplify ? " << PH(e)); 116 if(!Infi_box::is_sedge_on_infibox(e)) { 117 CGAL_NEF_TRACEN(e->mark() << " " << 118 e->incident_sface()->mark() << " " << 119 e->twin()->incident_sface()->mark()); 120 if (( e->mark() == e->incident_sface()->mark() && 121 e->incident_sface()->mark() == e->twin()->incident_sface()->mark())){ 122 CGAL_NEF_TRACEN("deleting "<<PH(e)); 123 if ( !UF.same_set(Pitem[e->incident_sface()], 124 Pitem[e->twin()->incident_sface()]) ) { 125 126 UF.unify_sets( Pitem[e->incident_sface()], 127 Pitem[e->twin()->incident_sface()] ); 128 CGAL_NEF_TRACEN("unioning disjoint faces"); 129 } 130 131 CGAL_NEF_TRACEN("is_closed_at_source " << is_closed_at_source(e) << 132 " " << is_closed_at_source(e->twin())); 133 134 if ( is_closed_at_source(e) ) 135 Vitem[e->source()] = Pitem[e->incident_sface()]; 136 137 if ( is_closed_at_source(e->twin())) 138 Vitem[e->target()] = Pitem[e->incident_sface()]; 139 140 delete_edge_pair(e); 141 } 142 } 143 } 144 145 CGAL::Unique_hash_map<SHalfedge_handle,bool> linked(false); 146 for (e = this->shalfedges_begin(); e != this->shalfedges_end(); ++e) { 147 if ( linked[e] ) continue; 148 SHalfedge_around_sface_circulator hfc(e),hend(hfc); 149 SFace_handle f = *(UF.find( Pitem[e->incident_sface()])); 150 CGAL_For_all(hfc,hend) { set_face(hfc,f); linked[hfc]=true; } 151 store_sm_boundary_object(e,f); 152 } 153 154 SVertex_iterator v,vn; 155 for(v = this->svertices_begin(); v != this->svertices_end(); v=vn) { 156 vn=v; ++vn; 157 if ( is_isolated(v) ) { 158 if(Vitem[v] != nullptr) { 159 set_face(v,*(UF.find(Vitem[v]))); 160 CGAL_NEF_TRACEN("incident face of " << PH(v) << " set to " << &*(v->incident_sface())); 161 } 162 else { 163 set_face(v, *(UF.find(Pitem[v->incident_sface()]))); 164 CGAL_NEF_TRACEN("isolated svertex " << PH(v) << 165 " already has incident face " << &*(v->incident_sface())); 166 } 167 if ( v->mark() == v->incident_sface()->mark() ) { 168 CGAL_NEF_TRACEN("removing isolated vertex"<<PH(v)); 169 delete_vertex_only(v); 170 } 171 else 172 store_sm_boundary_object(v,v->incident_sface()); // isolated, but should stay 173 } else { // v not isolated 174 SHalfedge_handle e2 = first_out_edge(v), e1 = e2->sprev(); 175 if ( has_outdeg_two(v) && 176 v->mark() == e1->mark() && e1->mark() == e2->mark() && 177 e1->circle() == e2->circle() ) { 178 CGAL_NEF_TRACEN("collinear at "<<PH(v)<<PH(e1)<<PH(e2)); 179 if ( e1 == e2 ){ 180 CGAL_NEF_TRACEN("edge_to_loop"); 181 convert_edge_to_loop(e1); 182 } else { 183 CGAL_NEF_TRACEN("merge_edge_pairs"); 184 merge_edge_pairs_at_target(e1); 185 } 186 } 187 } 188 } 189 190 SFace_iterator fn; 191 for (f = fn = this->sfaces_begin(); f != this->sfaces_end(); f=fn) { 192 ++fn; 193 Union_find_handle pit = Pitem[f]; 194 if ( UF.find(pit) != pit ) { 195 CGAL_NEF_TRACEN("delete face " << &*f); 196 delete_face_only(f); 197 } 198 } 199 200 CGAL_NEF_TRACEN(" "); 201 CGAL_NEF_TRACEN("resulting vertex "); 202 203 CGAL_forall_svertices(vn, *this) 204 CGAL_NEF_TRACEN("|" << vn->point() << "|" << vn->mark()); 205 CGAL_NEF_TRACEN(" "); 206 207 CGAL_forall_shalfedges(en,*this) 208 CGAL_NEF_TRACEN("|" << en->circle() << 209 "|" << en->mark() << 210 " " << en->incident_sface()->mark()); 211 CGAL_NEF_TRACEN("---------------------"); 212 } 213 214 }; 215 216 template <typename SM_decorator_> 217 class SNC_SM_overlayer<SNC_indexed_items, SM_decorator_> 218 : public SM_overlayer<SM_decorator_> { 219 220 typedef SM_decorator_ SM_decorator; 221 typedef typename SM_decorator::Map Map; 222 typedef SM_overlayer<SM_decorator_> Base; 223 typedef SNC_SM_overlayer<SNC_indexed_items, 224 SM_decorator_> Self; 225 226 typedef typename Base::SVertex_handle SVertex_handle; 227 typedef typename Base::SHalfedge_handle SHalfedge_handle; 228 typedef typename Base::SHalfloop_handle SHalfloop_handle; 229 typedef typename Base::SFace_handle SFace_handle; 230 typedef typename Base::SVertex_iterator SVertex_iterator; 231 typedef typename Base::SHalfedge_iterator SHalfedge_iterator; 232 typedef typename Base::SFace_iterator SFace_iterator; 233 typedef typename Base::SHalfedge_around_sface_circulator 234 SHalfedge_around_sface_circulator; 235 236 typedef typename Base::Sphere_kernel Sphere_kernel; 237 238 typedef typename Map::Infi_box Infi_box; 239 240 using SM_decorator::clear_face_cycle_entries; 241 using SM_decorator::link_as_loop; 242 using SM_decorator::link_as_prev_next_pair; 243 using SM_decorator::is_closed_at_source; 244 using SM_decorator::is_closed_at_target; 245 using SM_decorator::delete_edge_pair; 246 using SM_decorator::set_face; 247 using SM_decorator::is_isolated; 248 using SM_decorator::delete_vertex_only; 249 using SM_decorator::delete_face_only; 250 using SM_decorator::first_out_edge; 251 using SM_decorator::set_first_out_edge; 252 using SM_decorator::has_outdeg_two; 253 using SM_decorator::store_sm_boundary_object; 254 using SM_decorator::is_sm_boundary_object; 255 using SM_decorator::undo_sm_boundary_object; 256 using SM_decorator::delete_edge_pair_only; 257 258 public: 259 SNC_SM_overlayer(Map* M, 260 const Sphere_kernel& G = Sphere_kernel()) Base(M,G)261 : Base(M,G) {} 262 convert_edge_to_loop(SHalfedge_handle e)263 void convert_edge_to_loop(SHalfedge_handle e) { 264 /*{\Mop converts the edge at |v = e->target()| to the unique 265 loop |l| of |\Mvar|. |e|, |e->twin()| and |v| are deleted 266 in the conversion. \precond there was no loop in |\Mvar|. 267 As |e| was entry point of |e->incident_sface()| then |l| takes this role.}*/ 268 269 CGAL_NEF_TRACEN("convert_edge_to_loop "<<PH(e)); 270 CGAL_assertion( e->source()==e->target() ); 271 CGAL_assertion( !this->has_shalfloop() ); 272 SHalfloop_handle l = this->new_shalfloop_pair(); 273 SVertex_handle v = e->target(); 274 SFace_handle f1 = e->incident_sface(), f2 = e->twin()->incident_sface(); 275 if( is_sm_boundary_object(e)) { 276 CGAL_assertion( is_sm_boundary_object(e->twin())); 277 undo_sm_boundary_object(e,f1); undo_sm_boundary_object(e->twin(),f2); 278 } 279 link_as_loop(l,f1), link_as_loop(l->twin(),f2); 280 l->circle() = e->circle(); l->twin()->circle() = e->twin()->circle(); 281 l->mark() = l->twin()->mark() = e->mark(); 282 l->set_index(e->get_index()); 283 l->twin()->set_index(e->twin()->get_index()); 284 delete_vertex_only(v); 285 delete_edge_pair_only(e); 286 } 287 288 template <typename Association> merge_edge_pairs_at_target(SHalfedge_handle e,Association & A)289 void merge_edge_pairs_at_target(SHalfedge_handle e, Association& A) { 290 /*{\Mop merges the edge pairs at |v = e->target()|. |e| and |twin(e)| 291 are preserved, |e->snext()|, |twin(e->snext())| and |v| are deleted 292 in the merger. \precond |v| has outdegree two. The adjacency at 293 |e->source()| and |target(e->snext())| is kept consistent. 294 If |e->snext()| was entry point of |e->incident_sface()| then |e| takes this role. 295 The same holds for |twin(e->snext())| and |face(twin(e))|.}*/ 296 297 CGAL_NEF_TRACEN("merge_edge_pairs_at_target "<<PH(e)); 298 SHalfedge_handle en = e->snext(), eno = en->twin(), enn, enno, 299 eo = e->twin() ; 300 if ( is_closed_at_target(en) ) { enn = eo; enno=e; } 301 else { enn = en->snext(), enno = eno->sprev(); } 302 SVertex_handle v = e->target(), vn = en->target(); 303 CGAL_assertion(has_outdeg_two(v)); 304 SFace_handle f1 = en->incident_sface(), f2 = eno->incident_sface(); 305 // transfer the opposite face cycles e-en-enn to e-enn 306 if ( enn != eno ) { 307 link_as_prev_next_pair(e,enn); 308 link_as_prev_next_pair(enno,eo); 309 } else { 310 link_as_prev_next_pair(e,eo); 311 } 312 // set vertex of e and deal with vertex-halfedge incidence 313 eo->source() = vn; 314 315 CGAL_NEF_TRACEN("rehash " << en->get_index() << " " << e->get_index()); 316 CGAL_NEF_TRACEN(" " << A.get_hash(en->get_index()) << " " << A.get_hash(e->get_index())); 317 CGAL_NEF_TRACEN("rehash " << eno->get_index() << " " << eo->get_index()); 318 CGAL_NEF_TRACEN(" " << A.get_hash(eno->get_index()) << " " << A.get_hash(eo->get_index())); 319 320 int index1 = A.get_hash(e->get_index()); 321 int index2 = A.get_hash(en->get_index()); 322 if(index2 < index1) { 323 A.set_hash(e->get_index(), index2); 324 e->set_index(index2); 325 } else 326 A.set_hash(en->get_index(), index1); 327 328 index1 = A.get_hash(eo->get_index()); 329 index2 = A.get_hash(eno->get_index()); 330 if(index2 < index1) { 331 A.set_hash(eo->get_index(), index2); 332 eo->set_index(index2); 333 } else 334 A.set_hash(eno->get_index(), index1); 335 336 CGAL_NEF_TRACEN("hash sedge " << e->get_index() 337 << "->" << A.get_hash(e->get_index())); 338 CGAL_NEF_TRACEN("hash sedge " << en->get_index() 339 << "->" << A.get_hash(en->get_index())); 340 CGAL_NEF_TRACEN("hash sedge " << eo->get_index() 341 << "->" << A.get_hash(eo->get_index())); 342 CGAL_NEF_TRACEN("hash sedge " << eno->get_index() 343 << "->" << A.get_hash(eno->get_index())); 344 345 346 if ( first_out_edge(vn) == eno ) set_first_out_edge(vn,eo); 347 if ( is_sm_boundary_object(en) ) 348 { undo_sm_boundary_object(en,f1); store_sm_boundary_object(e,f1); } 349 if ( is_sm_boundary_object(eno) ) 350 { undo_sm_boundary_object(eno,f2); store_sm_boundary_object(eo,f2); } 351 delete_vertex_only(v); 352 delete_edge_pair_only(en); 353 CGAL_NEF_TRACEN("END "<<PH(e->sprev())<<PH(e)<<PH(e->snext())); 354 } 355 356 template <typename Association> simplify(Association & A)357 void simplify(Association& A) { 358 CGAL_NEF_TRACEN("simplifying"); 359 360 typedef typename CGAL::Union_find<SFace_handle>::handle Union_find_handle; 361 CGAL::Unique_hash_map< SFace_handle, Union_find_handle> Pitem(nullptr); 362 CGAL::Unique_hash_map< SVertex_handle, Union_find_handle> Vitem(nullptr); 363 CGAL::Union_find< SFace_handle> UF; 364 365 SFace_iterator f; 366 CGAL_forall_sfaces(f,*this) { 367 Pitem[f] = UF.make_set(f); 368 clear_face_cycle_entries(f); 369 } 370 371 if ( this->has_shalfloop() ) { 372 SHalfloop_handle l = this->shalfloop(); 373 SFace_handle f = *(UF.find(Pitem[l->incident_sface()])); 374 link_as_loop(l,f); 375 f = *(UF.find(Pitem[l->twin()->incident_sface()])); 376 link_as_loop(l->twin(),f); 377 } 378 379 SHalfedge_iterator e, en; 380 for(e = this->shalfedges_begin(); e != this->shalfedges_end(); e = en) { 381 en = e; ++en; if ( en==e->twin() ) ++en; 382 CGAL_NEF_TRACEN("can simplify ? " << PH(e)); 383 if(!Infi_box::is_sedge_on_infibox(e)) { 384 CGAL_NEF_TRACEN(e->mark() << " " << 385 e->incident_sface()->mark() << " " << 386 e->twin()->incident_sface()->mark()); 387 if (( e->mark() == e->incident_sface()->mark() && 388 e->incident_sface()->mark() == e->twin()->incident_sface()->mark())){ 389 CGAL_NEF_TRACEN("deleting "<<PH(e)); 390 if ( !UF.same_set(Pitem[e->incident_sface()], 391 Pitem[e->twin()->incident_sface()]) ) { 392 393 UF.unify_sets( Pitem[e->incident_sface()], 394 Pitem[e->twin()->incident_sface()] ); 395 CGAL_NEF_TRACEN("unioning disjoint faces"); 396 } 397 398 CGAL_NEF_TRACEN("is_closed_at_source " << is_closed_at_source(e) << 399 " " << is_closed_at_source(e->twin())); 400 401 if ( is_closed_at_source(e) ) 402 Vitem[e->source()] = Pitem[e->incident_sface()]; 403 404 if ( is_closed_at_source(e->twin())) 405 Vitem[e->target()] = Pitem[e->incident_sface()]; 406 407 delete_edge_pair(e); 408 } 409 } 410 } 411 412 CGAL::Unique_hash_map<SHalfedge_handle,bool> linked(false); 413 for (e = this->shalfedges_begin(); e != this->shalfedges_end(); ++e) { 414 if ( linked[e] ) continue; 415 SHalfedge_around_sface_circulator hfc(e),hend(hfc); 416 SFace_handle f = *(UF.find( Pitem[e->incident_sface()])); 417 CGAL_For_all(hfc,hend) { set_face(hfc,f); linked[hfc]=true; } 418 store_sm_boundary_object(e,f); 419 } 420 421 SVertex_iterator v,vn; 422 for(v = this->svertices_begin(); v != this->svertices_end(); v=vn) { 423 vn=v; ++vn; 424 if ( is_isolated(v) ) { 425 if(Vitem[v] != nullptr) { 426 set_face(v,*(UF.find(Vitem[v]))); 427 CGAL_NEF_TRACEN("incident face of " << PH(v) << " set to " << &*(v->incident_sface())); 428 } 429 else { 430 set_face(v, *(UF.find(Pitem[v->incident_sface()]))); 431 CGAL_NEF_TRACEN("isolated svertex " << PH(v) << 432 " already has incident face " << &*(v->incident_sface())); 433 } 434 if ( v->mark() == v->incident_sface()->mark() ) { 435 CGAL_NEF_TRACEN("removing isolated vertex"<<PH(v)); 436 delete_vertex_only(v); 437 } 438 else 439 store_sm_boundary_object(v,v->incident_sface()); // isolated, but should stay 440 } else { // v not isolated 441 SHalfedge_handle e2 = first_out_edge(v), e1 = e2->sprev(); 442 if ( has_outdeg_two(v) && 443 v->mark() == e1->mark() && e1->mark() == e2->mark() && 444 e1->circle() == e2->circle() ) { 445 CGAL_NEF_TRACEN("collinear at "<<PH(v)<<PH(e1)<<PH(e2)); 446 if ( e1 == e2 ){ 447 CGAL_NEF_TRACEN("edge_to_loop"); 448 convert_edge_to_loop(e1); 449 } else { 450 CGAL_NEF_TRACEN("merge_edge_pairs"); 451 merge_edge_pairs_at_target(e1, A); 452 } 453 } 454 } 455 } 456 457 SFace_iterator fn; 458 for (f = fn = this->sfaces_begin(); f != this->sfaces_end(); f=fn) { 459 ++fn; 460 Union_find_handle pit = Pitem[f]; 461 if ( UF.find(pit) != pit ) { 462 CGAL_NEF_TRACEN("delete face " << &*f); 463 delete_face_only(f); 464 } 465 } 466 467 CGAL_NEF_TRACEN(" "); 468 CGAL_NEF_TRACEN("resulting vertex "); 469 470 CGAL_forall_svertices(vn, *this) 471 CGAL_NEF_TRACEN("|" << vn->point() << "|" << vn->mark()); 472 CGAL_NEF_TRACEN(" "); 473 474 CGAL_assertion_code(CGAL_forall_shalfedges(en,*this) 475 CGAL_NEF_TRACEN("|" << en->circle() << 476 "|" << en->mark() << 477 " " << en->incident_sface()->mark())); 478 479 CGAL_NEF_TRACEN("check indexes"); 480 CGAL_assertion_code(CGAL_forall_sedges(en, *this) 481 CGAL_NEF_TRACEN(en->source()->point() << "->" 482 << en->twin()->source()->point() << " : " 483 << en->get_index() << " " 484 << en->twin()->get_index())); 485 CGAL_NEF_TRACEN("---------------------"); 486 } 487 488 }; 489 490 } //namespace CGAL 491 #endif //CGAL_SNC_SM_OVERLAYER_H 492