// Copyright (c) 2007 Max-Planck-Institute Saarbruecken (Germany). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Nef_3/include/CGAL/Nef_3/Edge_edge_overlay.h $ // $Id: Edge_edge_overlay.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Peter Hachenberger #ifndef CGAL_EDGE_EDGE_OVERLAY_H #define CGAL_EDGE_EDGE_OVERLAY_H #include #include #include #include #include #include #undef CGAL_NEF_DEBUG #define CGAL_NEF_DEBUG 71 #include namespace CGAL { template class Edge_edge_overlay { public: typedef SNC_structure_ SNC_structure; typedef typename SNC_structure::Items Items; typedef typename SNC_structure_::Kernel Kernel; typedef typename Kernel::RT RT; typedef CGAL::Edge_edge_overlay Self; typedef CGAL::SNC_decorator SNC_decorator; typedef typename CGAL::SNC_constructor SNC_constructor; typedef typename SNC_structure::Sphere_map Sphere_map; typedef CGAL::SM_decorator SM_decorator; typedef CGAL::SM_const_decorator SM_const_decorator; typedef CGAL::SM_point_locator SM_point_locator; typedef typename SNC_structure::Vertex_iterator Vertex_iterator; typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator; typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator; typedef typename SNC_structure::Vertex_handle Vertex_handle; typedef typename SNC_structure::Halfedge_handle Halfedge_handle; typedef typename SNC_structure::Halffacet_handle Halffacet_handle; typedef typename SNC_structure::Vertex_const_handle Vertex_const_handle; typedef typename SNC_structure::Halfedge_const_handle Halfedge_const_handle; typedef typename SNC_structure::Halffacet_const_handle Halffacet_const_handle; typedef typename SNC_structure::Halffacet_const_iterator Halffacet_const_iterator; typedef typename SNC_structure::SVertex_iterator SVertex_iterator; typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator; typedef typename SNC_structure::SFace_iterator SFace_iterator; typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator; typedef typename SNC_structure::SVertex_handle SVertex_handle; typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle; typedef typename SNC_structure::SFace_handle SFace_handle; typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle; typedef typename SNC_structure::SVertex_const_handle SVertex_const_handle; typedef typename SNC_structure::SHalfedge_const_handle SHalfedge_const_handle; typedef typename SNC_structure::SHalfloop_const_handle SHalfloop_const_handle; typedef typename SNC_structure::SFace_const_handle SFace_const_handle; typedef typename SNC_structure::SHalfedge_around_facet_circulator SHalfedge_around_facet_circulator; typedef typename SNC_structure::SHalfedge_around_facet_const_circulator SHalfedge_around_facet_const_circulator; typedef typename SNC_structure::SFace_cycle_iterator SFace_cycle_iterator; typedef typename SNC_structure::SFace_cycle_const_iterator SFace_cycle_const_iterator; typedef typename SNC_structure::Halffacet_cycle_iterator Halffacet_cycle_iterator; typedef typename SNC_structure::Halffacet_cycle_const_iterator Halffacet_cycle_const_iterator; typedef typename SNC_structure::Point_3 Point_3; typedef typename SNC_structure::Vector_3 Vector_3; typedef typename SNC_structure::Segment_3 Segment_3; typedef typename SNC_structure::Plane_3 Plane_3; typedef typename SNC_structure::Aff_transformation_3 Aff_transformation_3; typedef typename SNC_structure::Sphere_point Sphere_point; typedef typename SNC_structure::Sphere_segment Sphere_segment; typedef typename SNC_structure::Sphere_circle Sphere_circle; typedef typename SNC_structure::Mark Mark; typedef typename SM_decorator::SHalfedge_around_svertex_circulator SHalfedge_around_svertex_circulator; typedef typename SM_decorator::SHalfedge_around_sface_circulator SHalfedge_around_sface_circulator; typedef typename SM_const_decorator::SHalfedge_around_svertex_const_circulator SHalfedge_around_svertex_const_circulator; SNC_structure& snc; Halfedge_const_handle e0, e1; SM_decorator D; SM_const_decorator E; Edge_edge_overlay( SNC_structure& snc_, Halfedge_const_handle e0_, Halfedge_const_handle e1_) : snc(snc_), e0(e0_), e1(e1_) {} template Sphere_map* overlay_isolated_edges(const Point_3& p, const Selection& BOP, bool inv) { Vertex_handle v = snc.new_vertex(p); v->mark() = BOP(e0->mark(), e1->mark(), inv); D = SM_decorator(&*v); SFace_handle sf = D.new_sface(); sf->mark() = BOP(e0->incident_sface()->mark(), e1->incident_sface()->mark(), inv); SVertex_handle sv = D.new_svertex(e0->point()); sv->mark() = BOP(e0->mark(), e1->incident_sface()->mark(), inv); D.link_as_isolated_vertex(sv, sf); sv = D.new_svertex(e0->twin()->point()); sv->mark() = BOP(e0->mark(), e1->incident_sface()->mark(), inv); D.link_as_isolated_vertex(sv, sf); sv = D.new_svertex(e1->point()); sv->mark() = BOP(e0->incident_sface()->mark(), e1->mark(), inv); D.link_as_isolated_vertex(sv, sf); sv = D.new_svertex(e1->twin()->point()); sv->mark() = BOP(e0->incident_sface()->mark(), e1->mark(), inv); D.link_as_isolated_vertex(sv, sf); return D.sphere_map(); } template Sphere_map* create_edge_edge_overlay( const Point_3& p, const Selection& BOP, bool inv, Association& ) { // CGAL_NEF_SETDTHREAD(43*71); CGAL_NEF_TRACEN(std::endl << "edge_edge " << p ); E = SM_const_decorator(&*e1->source()); if(E.is_isolated(e0)) { if(E.is_isolated(e1)) { return overlay_isolated_edges(p, BOP, inv); } else { std::swap(e0, e1); inv = !inv; E = SM_const_decorator(&*e1->source()); } } SNC_constructor C(snc); Vertex_handle v(C.create_from_edge(e0,p)); v->mark() = BOP(v->mark(), e1->mark(), inv); D = SM_decorator(&*v); SVertex_handle sv[4]; sv[0] = sv[1] = v->svertices_begin(); ++sv[1]; Vector_3 vec0 = sv[0]->point() - CGAL::ORIGIN; Vector_3 vec1 = e1->source()->point() - CGAL::ORIGIN; Plane_3 mid_plane(Point_3(0,0,0), cross_product(vec0, vec1)); Sphere_segment test_seg(sv[0]->point(), CGAL::ORIGIN + mid_plane.orthogonal_vector()); Oriented_side test_os = test_seg.sphere_circle().oriented_side(e1->point()); CGAL_assertion(test_os != ON_ORIENTED_BOUNDARY); if(test_os == ON_NEGATIVE_SIDE) { CGAL_NEF_TRACEN("change orientation of e1 " ); e1 = e1->twin(); } SM_point_locator PL(&*v); Object_handle o2 = PL.locate(e1->point()); Object_handle o3 = PL.locate(e1->twin()->point()); sv[2] = D.new_svertex(e1->point()); sv[3] = D.new_svertex(e1->twin()->point()); for(int i=0; i<4; ++i) CGAL_NEF_TRACEN("sv[" << i << "]= " << sv[i]->point()); bool equator[4]; equator[0] = equator[1] = equator[2] = equator[3] = false; bool on_sface[2]; SHalfedge_handle se0, se1; SHalfedge_handle previous_first, previous_last; SFace_handle sf0, sf1; SHalfedge_around_svertex_circulator seb[2], see[2]; SHalfedge_around_svertex_const_circulator scb[2], sce[2]; bool empty_e[2]; bool empty_c[2]; empty_e[0] = empty_e[1] = empty_c[0] = empty_c[1] = false; on_sface[0] = CGAL::assign(sf0, o2); on_sface[1] = CGAL::assign(sf1, o3); // set seb[0], see[1] if(on_sface[0]) { CGAL_NEF_TRACEN("found sf0 " ); sv[2]->mark() = BOP(sf0->mark(), e1->mark(), inv); SFace_cycle_iterator sfci(sf0->sface_cycles_begin()); CGAL_assertion(sfci.is_shalfedge()); SHalfedge_handle se_tmp(sfci); see[1] = se_tmp; if(see[1]->source() != sv[0]) see[1] = see[1]->snext(); see[1] = see[1]->sprev()->twin(); seb[0] = see[1]; } else { CGAL::assign(se0, o2); CGAL_assertion(CGAL::assign(se0, o2)); CGAL_NEF_TRACEN("found se0 " << se0->source()->point() << "->" << se0->twin()->source()->point() ); CGAL_NEF_TRACEN("insert sv " << sv[2]->point() ); if(se0->source() != sv[0]) se0 = se0->twin(); CGAL_assertion(se0->source() == sv[0]); sv[2]->mark() = BOP(se0->mark(), e1->mark(), inv); SHalfedge_handle se_new = D.split_at(se0, sv[2]); se_new->mark() = se_new->twin()->mark() = se0->mark() = se0->twin()->mark() = BOP(se0->mark(), sv[2]->mark(), inv); // TODO: test mark of se0 see[1] = seb[0]= se0; ++seb[0]; equator[0] = equator[1] = true; } // set seb[1] and see[0] if(on_sface[1]) { CGAL_NEF_TRACEN("found sf1 " ); sv[3]->mark() = BOP(sf1->mark(), e1->mark(), inv); SFace_cycle_iterator sfci(sf1->sface_cycles_begin()); CGAL_assertion(sfci.is_shalfedge()); SHalfedge_handle se_tmp(sfci); see[0] = se_tmp; if(see[0]->source() != sv[0]) see[0] = see[0]->snext(); see[0] = see[0]->sprev()->twin(); seb[1] = see[0]; } else { CGAL::assign(se1, o3); CGAL_assertion(CGAL::assign(se1, o3)); CGAL_NEF_TRACEN("found se1 " << se1->source()->point() << "->" << se1->twin()->source()->point() ); CGAL_NEF_TRACEN("insert sv " << sv[3]->point() ); if(se1->source() != sv[0]) se1 = se1->twin(); CGAL_assertion(se1->source() == sv[0]); sv[3]->mark() = BOP(se1->mark(), e1->mark(), inv); SHalfedge_handle se_new = D.split_at(se1, sv[3]); se_new->mark() = se_new->twin()->mark() = se1->mark() = se1->twin()->mark() = BOP(se1->mark(), sv[3]->mark(), inv); // TODO: test mark of se1 see[0] = seb[1] = se1; ++seb[1]; equator[2] = equator[3] = true; } CGAL_assertion(seb[0]->source() == sv[0]); // set empty_e if necessary if(seb[0] == see[0] && seb[1] == see[1]) { CGAL_NEF_TRACEN("both empty intervals"); Oriented_side osx = seb[0]->circle().oriented_side(sv[3]->point()); if(osx == ON_NEGATIVE_SIDE) { CGAL_NEF_TRACEN("empty 0 " ); empty_e[0] = true; } else if(osx == ON_POSITIVE_SIDE) { empty_e[1] = true; } else { empty_e[0] = empty_e[1] = true; } } else if(seb[0] == see[0]) { empty_e[0] = true; } else if(seb[1] == see[1]) { empty_e[1] = true; } CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); // finish overlay if one edge is isolated if(E.is_isolated(e1)) { Mark sfm = e1->incident_sface()->mark(); sv[0]->mark() = BOP(sv[0]->mark(), sfm, inv); sv[1]->mark() = BOP(sv[1]->mark(), sfm, inv); SHalfedge_around_svertex_circulator svc(sv[0]->out_sedge()), send(svc); CGAL_For_all(svc, send) { svc->incident_sface()->mark() = BOP(svc->incident_sface()->mark(), sfm, inv); if(svc->twin()->source() != sv[1]) continue; svc->mark() = BOP(svc->mark(), sfm, inv); } if(on_sface[0]) D.link_as_isolated_vertex(sv[2], sf0); if(on_sface[1]) D.link_as_isolated_vertex(sv[3], sf1); return D.sphere_map(); } SHalfedge_around_svertex_const_circulator svc(e1->out_sedge()), send(svc); // determine scb and sce for one side int i=0; bool done = false; Oriented_side os0 = svc->circle().oriented_side(sv[0]->point()); Oriented_side os1 = os0; while(os0 == os1 && os1 != ON_ORIENTED_BOUNDARY && ++svc != send) os1 = svc->circle().oriented_side(sv[0]->point()); CGAL_NEF_TRACEN("osi " << os0 << ", " << os1 ); CGAL_assertion(os1 == svc->circle().oriented_side(sv[0]->point()) || svc == send); if(os1 == ON_ORIENTED_BOUNDARY) { CGAL_NEF_TRACEN("svc on boundary "); Sphere_segment seg(sv[2]->point(), sv[3]->point(), svc->circle()); int sv_index = seg.has_on(sv[0]->point()) ? 0 : 1; equator[sv_index] = equator[sv_index+2] = true; CGAL_NEF_TRACEN("sv " << sv[0]->point() << ", " << sv[1]->point() ); // svc is the segment from sv[2] to sv[3] that has sv[sv_index] // in its interior if(on_sface[0]) { CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); // add shalfedge_pair between sv[2] and sv[sv_index] SFace_cycle_iterator sfci = sf0->sface_cycles_begin(); CGAL_assertion(sfci.is_shalfedge()); SHalfedge_handle se_tgt(sfci); while(se_tgt->source() != sv[sv_index]) { se_tgt = se_tgt->snext(); CGAL_NEF_TRACEN(se_tgt->source()->point() << " " << sv[sv_index]->point() ); CGAL_NEF_TRACEN(&(se_tgt->source()) << " " << &sv[sv_index] ); } CGAL_NEF_TRACEN("sv[sv_index] " << sv[sv_index]->point()); CGAL_NEF_TRACEN("after " << se_tgt->source()->point() << "->" << se_tgt->twin()->source()->point()); SHalfedge_around_svertex_circulator se_next(se_tgt); ++se_next; CGAL_assertion(se_tgt->source() == sv[sv_index]); CGAL_NEF_TRACEN("new_shalfedge_pair" ); SHalfedge_handle se_new = D.new_shalfedge_pair(sv[2], se_tgt, 1); se_new->mark() = se_new->twin()->mark() = BOP(sf0->mark(), svc->mark(), inv); se_new->circle() = normalized(Sphere_circle(se_new->source()->point(), se_new->twin()->source()->point())); se_new->twin()->circle() = se_new->circle().opposite(); se_new->incident_sface() = se_new->twin()->incident_sface() = sf0; CGAL_NEF_TRACEN("seb[0] " << seb[0]->source()->point() << "->" << seb[0]->twin()->source()->point() ); CGAL_NEF_TRACEN("see[0] " << see[0]->source()->point() << "->" << see[0]->twin()->source()->point() ); CGAL_assertion(seb[0]->source() == sv[0]); CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); if(se_next == see[0] && !empty_e[0]) --see[0]; else if(se_next == see[1] && !empty_e[1]) --see[1]; } CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); if(on_sface[1]) { CGAL_NEF_TRACEN("sf1->mark() " << sf1->mark()); // add shalfedge_pair between sv[3] and sv[sv_index] CGAL_NEF_TRACEN("seb[0] " << seb[0]->source()->point() << "->" << seb[0]->twin()->source()->point() ); CGAL_NEF_TRACEN("see[0] " << see[0]->source()->point() << "->" << see[0]->twin()->source()->point() ); SFace_cycle_iterator sfci = sf1->sface_cycles_begin(); CGAL_assertion(sfci.is_shalfedge()); SHalfedge_handle se_tgt(sfci); while(se_tgt->source() != sv[sv_index]) { se_tgt = se_tgt->snext(); CGAL_NEF_TRACEN(se_tgt->source()->point() << " " << sv[sv_index]->point() ); CGAL_NEF_TRACEN(&(se_tgt->source()) << " " << &sv[sv_index] ); } SHalfedge_around_svertex_circulator se_next(se_tgt); ++se_next; CGAL_NEF_TRACEN("sv[sv_index] " << sv[sv_index]->point()); CGAL_NEF_TRACEN("after " << se_tgt->source()->point() << "->" << se_tgt->twin()->source()->point()); CGAL_assertion(se_tgt->source() == sv[sv_index]); CGAL_NEF_TRACEN("new_shalfedge_pair" ); SHalfedge_handle se_new = D.new_shalfedge_pair(sv[3], se_tgt, 1); // CGAL_assertion(se_new->snext() == se_tgt); CGAL_NEF_TRACEN("se_new " << se_new->source()->point() << "->" << se_new->twin()->source()->point() ); se_new->mark() = se_new->twin()->mark() = BOP(sf1->mark(), svc->mark(), inv); se_new->circle() = normalized(Sphere_circle(se_new->source()->point(), se_new->twin()->source()->point())); se_new->twin()->circle() = se_new->circle().opposite(); se_new->incident_sface() = se_new->twin()->incident_sface() = sf1; CGAL_NEF_TRACEN("seb[0] " << seb[0]->source()->point() << "->" << seb[0]->twin()->source()->point() ); CGAL_NEF_TRACEN("see[0] " << see[0]->source()->point() << "->" << see[0]->twin()->source()->point() ); CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); if(se_next == see[0] && !empty_e[0]) --see[0]; else if(se_next == see[1] && !empty_e[1]) --see[1]; CGAL_NEF_TRACEN("se[01] " << (std::distance(seb[0], see[0])) << ", " << (std::distance(seb[1], see[1])) ); } CGAL_NEF_TRACEN("see[0] " << see[0]->source()->point() << "->" << see[0]->twin()->source()->point() ); if(svc == svc->twin()->snext()) { scb[0] = scb[1] = sce[0] = sce[1] = svc; empty_c[0] = empty_c[1] = true; done = true; } else { ++svc; os1 = svc->circle().oriented_side(sv[0]->point()); CGAL_NEF_TRACEN("++os1 " << os1 ); if(os1 == ON_ORIENTED_BOUNDARY) { CGAL_assertion_msg(false, "not implemented, yet"); // don't forget empty_c ++svc; scb[0] = scb[1] = sce[0] = sce[1] = svc; if(svc != send) { os1 = svc->circle().oriented_side(sv[0]->point()); i = os1 == ON_POSITIVE_SIDE ? 0 : 1; --sce[i]; } equator[1-sv_index] = equator[3-sv_index] = true; done = true; } else { i = os1 == ON_POSITIVE_SIDE ? 0 : 1; CGAL_NEF_TRACEN("second change found on side " << os1); scb[i] = svc; --svc; sce[1-i] = svc; --svc; if(svc->circle().oriented_side(sv[0]->point()) == os1) { // sedges are only on one side " sce[i] = scb[1-i] = sce[1-i]; empty_c[1-i] = true; done = true; } } } } else if(svc == send) { // everything is on one side CGAL_NEF_TRACEN("svc == send"); Vector_3 vec1(svc->source()->point() - CGAL::ORIGIN), vec2(svc->circle().orthogonal_vector()); Sphere_point sp1(CGAL::ORIGIN + cross_product(vec2,vec1)); while(svc->sprev()->twin()->circle().oriented_side(sp1) == ON_POSITIVE_SIDE) { ++svc; vec1 = vec2; vec2 = svc->circle().orthogonal_vector(); sp1 = CGAL::ORIGIN + cross_product(vec2,vec1); } i = os1 == ON_POSITIVE_SIDE ? 0 : 1; // ++svc; scb[i] = sce[i] = svc; empty_c[1-i] = true; done = true; } else { CGAL_NEF_TRACEN("found sedges on both sides "); // CGAL_assertion_msg(false, "not implemented, yet"); // Code should work, but is not tested CGAL_assertion(os0 != os1); i = os1 == ON_POSITIVE_SIDE ? 0 : 1; sce[1-i] = scb[i] = svc; } // CGAL_assertion(scb[1-i] == svc); // determine scb, sce for other side if necessary if(!done) { CGAL_NEF_TRACEN("not done yet"); // both sides are not empty os0 = svc->circle().oriented_side(sv[0]->point()); CGAL_assertion(os0 != ON_ORIENTED_BOUNDARY); do { ++svc; os1 = svc->circle().oriented_side(sv[0]->point()); } while(os1 == os0); sce[i] = scb[1-i] = svc; if(os1 == ON_ORIENTED_BOUNDARY) { CGAL_assertion_msg(false, "degenerate case not implemented, yet"); ++scb[1-i]; CGAL_assertion(svc->circle().has_on(sv[0]->point()) == i); equator[i] = equator[2+i] == true; } } for(int i=0; i<4; ++i) CGAL_NEF_TRACEN("equator[" << i << "]= " << equator[i]); CGAL_NEF_TRACEN("svmark " << sv[0]->mark() << ", " << sv[1]->mark()); // TODO: marks if sv[0] and sv[1] lie on edge sv[0]->mark() = BOP(sv[0]->mark(), sce[empty_c[0]]->twin()->incident_sface()->mark(), inv); sv[1]->mark() = BOP(sv[1]->mark(), scb[empty_c[0]]->twin()->incident_sface()->mark(), inv); CGAL_NEF_TRACEN("empty[0] " << empty_c[0] << ", " << empty_e[0] ); CGAL_assertion(seb[0]->source() == sv[0]); CGAL_assertion_msg(!empty_c[0] || !empty_c[1], "not implemented, yet"); CGAL_assertion_msg(!empty_e[0] || !empty_e[1], "not implemented, yet"); bool first_first = true; bool first_last = true; if(!empty_c[0] && !empty_e[0]) { CGAL_NEF_TRACEN("sv[2] " << sv[2]->point()); if(equator[0] || equator[1]) { first_first = false; previous_first = sv[2]->out_sedge(); if(equator[0] && previous_first->twin()->source() != sv[0]) previous_first = previous_first->twin()->snext(); CGAL_assertion(!equator[0] || previous_first->twin()->source() == sv[0]); } if(equator[2] || equator[3]) { first_last = false; previous_last = sv[3]->out_sedge(); if(equator[2] && previous_last->twin()->source() != sv[0]) previous_last = previous_last->twin()->snext(); CGAL_assertion(!equator[2] || previous_last->twin()->source() == sv[0]); } SHalfedge_around_svertex_const_circulator curr_outer(scb[0]); CGAL_For_all(curr_outer, sce[0]) { CGAL_NEF_TRACEN("outer " << curr_outer->incident_sface()->mark() ); SHalfedge_handle previous_inner; Sphere_segment seg1(sv[2]->point(), sv[3]->point(), curr_outer->circle()); SHalfedge_around_svertex_circulator curr_inner(seb[0]); CGAL_For_all(curr_inner, see[0]) { CGAL_NEF_TRACEN("inner " << curr_inner->incident_sface()->mark() ); CGAL_assertion(!curr_inner->circle().has_on(sv[2]->point())); CGAL_assertion(!curr_outer->circle().has_on(sv[0]->point())); Sphere_segment seg0(sv[0]->point(), sv[1]->point(), curr_inner->circle()); Sphere_segment segX(curr_inner->source()->point(), curr_inner->twin()->source()->point(), curr_inner->circle()); CGAL_assertion(!seg0.is_long()); CGAL_assertion(!seg1.is_long()); Sphere_point sp = normalized(seg0.intersection(seg1)); CGAL_NEF_TRACEN("intersections oben " << sp ); CGAL_assertion(sp != sv[0]->point()); CGAL_assertion(sp != sv[1]->point()); CGAL_assertion(sp != sv[2]->point()); CGAL_assertion(sp != sv[3]->point()); CGAL_assertion(segX.has_on(sp)); CGAL_assertion(curr_inner == seb[0] || Sphere_segment(sv[2]->point(), sp).has_on (previous_inner->twin()->source()->point())); CGAL_assertion(seg0.source() == sv[0]->point()); CGAL_assertion(seg0.target() == sv[1]->point()); CGAL_assertion(seg1.source() == sv[2]->point()); CGAL_assertion(seg1.target() == sv[3]->point()); CGAL_assertion(seg0.has_on(sp)); CGAL_assertion(seg1.has_on(sp)); CGAL_NEF_TRACEN("seg 0 " << seg0.source() << "->" << seg0.target()); CGAL_NEF_TRACEN("seg 1 " << seg1.source() << "->" << seg1.target() << ":" << seg1.sphere_circle()); SHalfedge_handle along = D.split_at(curr_inner, sp); along->source()->mark() = BOP(curr_inner->mark(), curr_outer->mark(), inv); CGAL_NEF_TRACEN("first_first " << first_first); SHalfedge_handle across; if(curr_inner == seb[0]) across = first_first ? D.new_shalfedge_pair(sv[2], along, -1) : D.new_shalfedge_pair(previous_first, along, -1, -1); else across = D.new_shalfedge_pair(previous_inner->twin(), curr_inner->twin(), -1, 1); across->circle() = curr_outer->circle(); across->twin()->circle() = curr_outer->twin()->circle(); CGAL_NEF_TRACEN("across " << across->source()->point() << "->" << across->twin()->source()->point() << ":" << across->circle()); CGAL_NEF_TRACEN("across " << normalized(across->circle()) << ", " << normalized(Sphere_circle(across->source()->point(), across->twin()->source()->point()))); CGAL_assertion(normalized(across->circle()) == normalized(Sphere_circle(across->source()->point(), across->twin()->source()->point()))); across->mark() = across->twin()->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), curr_outer->mark(), inv); along->mark() = along->twin()->mark() = BOP(curr_inner->mark(), curr_outer->twin()->incident_sface()->mark(), inv); CGAL_NEF_TRACEN("across " << across->source()->point() << "->" << across->twin()->source()->point() << ":" << across->circle() ); if(curr_inner == seb[0]) previous_first = across; if(!first_first) { SFace_handle sf_new = D.new_sface(); D.link_as_face_cycle(across->twin(), sf_new); sf_new->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), curr_outer->twin()->incident_sface()->mark(), inv); CGAL_NEF_TRACEN("new sface " << sf_new->mark()); } previous_inner = curr_inner; first_first = false; } previous_last = first_last ? D.new_shalfedge_pair(sv[3], previous_inner->twin(), -1) : D.new_shalfedge_pair(previous_last, previous_inner->twin(), 1, -1); previous_last->circle() = curr_outer->twin()->circle(); previous_last->twin()->circle() = curr_outer->circle(); CGAL_assertion(previous_last->circle() == normalized(Sphere_circle(previous_last->source()->point(), previous_last->twin()->source()->point()))); previous_last->mark() = previous_last->twin()->mark() = BOP(previous_inner->incident_sface()->mark(), curr_outer->mark(), inv); if(!first_last) { SFace_handle sf_new = D.new_sface(); D.link_as_face_cycle(previous_last, sf_new); sf_new->mark() = BOP(previous_inner->incident_sface()->mark(), curr_outer->twin()->incident_sface()->mark(), inv); } first_last = false; } CGAL_NEF_TRACEN("sce[0]->mark() " << sce[0]->twin()->incident_sface()->mark()); SHalfedge_around_svertex_circulator curr_inner(seb[0]); CGAL_For_all(curr_inner, see[0]) { CGAL_NEF_TRACEN("schleife oben " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); curr_inner->mark() = curr_inner->twin()->mark() = BOP(curr_inner->mark(), sce[0]->twin()->incident_sface()->mark(), inv); if(!equator[0] && curr_inner == seb[0]) continue; SFace_handle sf = curr_inner->twin()->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner->twin()), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; sf->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), sce[0]->twin()->incident_sface()->mark(), inv); } CGAL_assertion(curr_inner == see[0]); CGAL_NEF_TRACEN("before equator[0] oben " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); if(equator[2]) { SFace_handle sf = curr_inner->twin()->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner->twin()), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; sf->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), sce[0]->twin()->incident_sface()->mark(), inv); } else --curr_inner; CGAL_NEF_TRACEN("final sface oben " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); SFace_handle sf = curr_inner->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; } else if(empty_e[0] && !empty_c[0]) { CGAL_assertion_msg(!equator[0] && !equator[1] && !equator[2] && !equator[3], "not implemented, yet" ); CGAL_assertion_msg(empty_c[1], "not implemented, yet"); CGAL_assertion_msg(sv[2]->out_sedge() == SHalfedge_handle(), "not implemented, yet"); CGAL_assertion_msg(sv[3]->out_sedge() == SHalfedge_handle(), "not implemented, yet"); CGAL_assertion_msg(!empty_e[1], "not implemented, yet"); Mark outer_sf = seb[1]->twin()->incident_sface()->mark(); SHalfedge_handle se_prev = D.new_shalfedge_pair(sv[2], sv[3]); se_prev->circle() = scb[0]->circle(); se_prev->twin()->circle() = scb[0]->twin()->circle(); se_prev->mark() = se_prev->twin()->mark() = BOP(outer_sf, scb[0]->mark()); SHalfedge_around_svertex_const_circulator curr(scb[0]); ++curr; while(curr != scb[0]) { se_prev = D.new_shalfedge_pair(se_prev, se_prev->twin(), 1, -1); // SM_io_parser::dump(D, std::cerr); se_prev->circle() = curr->circle(); se_prev->twin()->circle() = curr->twin()->circle(); se_prev->mark() = se_prev->twin()->mark() = BOP(outer_sf, curr->mark()); SFace_handle sf_new = D.new_sface(); sf_new->mark() = BOP(outer_sf, curr->twin()->incident_sface()->mark(), inv); D.link_as_face_cycle(se_prev->twin(), sf_new); ++curr; } seb[1]->twin()->incident_sface()->mark() = BOP(outer_sf, scb[0]->twin()->incident_sface()->mark(), inv); D.link_as_face_cycle(se_prev, seb[1]->twin()->incident_sface()); // SM_io_parser::dump(D, std::cerr); } else if(empty_c[0] && !empty_e[0]) { CGAL_assertion_msg(!equator[0] && !equator[1] && !equator[2] && !equator[3], "not implemented, yet" ); CGAL_assertion_msg(empty_e[1], "not implemented, yet"); CGAL_assertion_msg(!empty_c[1], "not implemented, yet"); Mark outer_sf = scb[1]->twin()->incident_sface()->mark(); SHalfedge_around_svertex_circulator curr(seb[0]); CGAL_For_all(curr, see[0]) { curr->mark() = curr->twin()->mark() = BOP(curr->mark(), outer_sf, inv); curr->incident_sface()->mark() = BOP(curr->incident_sface()->mark(), outer_sf, inv); } } // else // CGAL_assertion_msg(false, "not implemented, yet"); CGAL_NEF_TRACEN("empty[1] " << empty_c[1] << ", " << empty_e[1] ); CGAL_NEF_TRACEN("[1] " << (std::distance(scb[1], sce[1])) << ", " << (std::distance(seb[1], see[1])) ); if(!empty_c[1] && !empty_e[1]) { CGAL_assertion(first_first == empty_c[0]); if(first_first) { // nothing happend on the other half if(equator[2] || equator[3]) { first_first = false; previous_first = sv[3]->out_sedge(); if(equator[3] && previous_first->twin()->source() != sv[1]) previous_first = previous_first->twin()->snext(); CGAL_assertion(!equator[3] || previous_first->twin()->source() == sv[1]); } if(equator[0] || equator[1]) { first_last = false; previous_last = sv[2]->out_sedge(); if(equator[1] && previous_last->twin()->source() != sv[1]) previous_last = previous_last->sprev()->twin(); CGAL_assertion(!equator[1] || previous_last->twin()->source() == sv[1]); } } else { // rotate over gap on unhandled half CGAL_assertion(!first_first && !first_last); std::swap(previous_last, previous_first); previous_first = previous_first->twin()->snext(); if(equator[0]) previous_first = previous_first->twin()->snext(); previous_last = previous_last->sprev()->twin(); if(equator[2]) previous_last = previous_last->sprev()->twin(); } SHalfedge_around_svertex_const_circulator curr_outer(sce[1]); do { --curr_outer; CGAL_NEF_TRACEN("outer " << curr_outer->incident_sface()->mark()); CGAL_assertion(curr_outer->source()->point() == sv[2]->point()); SHalfedge_handle previous_inner; Sphere_segment seg1(sv[2]->point(), sv[3]->point(), curr_outer->circle()); SHalfedge_around_svertex_circulator curr_inner(seb[1]); CGAL_For_all(curr_inner, see[1]) { CGAL_NEF_TRACEN("inner " << curr_inner->incident_sface()->mark()); CGAL_assertion(curr_inner->source() == sv[0]); Sphere_segment seg0(sv[0]->point(), sv[1]->point(), curr_inner->circle()); Sphere_segment segX(curr_inner->source()->point(), curr_inner->twin()->source()->point(), curr_inner->circle()); CGAL_assertion(!seg0.is_long()); CGAL_assertion(!segX.is_long()); Sphere_point sp = normalized(seg0.intersection(seg1)); CGAL_NEF_TRACEN("first_first " << first_first); CGAL_NEF_TRACEN("first_last " << first_last); CGAL_NEF_TRACEN("intersections unten " << sp ); CGAL_assertion(segX.has_on(sp)); CGAL_assertion(curr_inner == seb[1] || Sphere_segment(sv[3]->point(), sp).has_on (previous_inner->twin()->source()->point())); CGAL_assertion(seg0.has_on(sp)); CGAL_assertion(seg1.has_on(sp)); CGAL_NEF_TRACEN("seg 0 " << seg0.source() << "->" << seg0.target()); CGAL_NEF_TRACEN("seg 1 " << seg1.source() << "->" << seg1.target() << ":" << seg1.sphere_circle()); SHalfedge_handle along = D.split_at(curr_inner, sp); along->source()->mark() = BOP(curr_inner->mark(), curr_outer->mark(), inv); SHalfedge_handle across; if(curr_inner == seb[1]) across = first_first ? D.new_shalfedge_pair(sv[3], along, -1) : D.new_shalfedge_pair(previous_first, along, 1, -1); else across = D.new_shalfedge_pair(previous_inner->twin(), curr_inner->twin(), -1, 1); across->circle() = curr_outer->twin()->circle(); across->twin()->circle() = curr_outer->circle(); CGAL_NEF_TRACEN("across " << across->source()->point() << "->" << across->twin()->source()->point() << ":" << across->circle()); CGAL_NEF_TRACEN("across " << normalized(across->circle()) << ", " << normalized(Sphere_circle(across->source()->point(), across->twin()->source()->point()))); CGAL_assertion(normalized(across->circle()) == normalized(Sphere_circle(across->source()->point(), across->twin()->source()->point()))); across->mark() = across->twin()->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), curr_outer->mark(), inv); along->mark() = along->twin()->mark() = BOP(curr_inner->mark(), curr_outer->incident_sface()->mark(), inv); if(curr_inner == seb[1]) previous_first = across; if(!first_first) { SFace_handle sf_new = D.new_sface(); D.link_as_face_cycle(across->twin(), sf_new); sf_new->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), curr_outer->incident_sface()->mark(), inv); CGAL_NEF_TRACEN("new sface" << sf_new->mark() ); } previous_inner = curr_inner; first_first = false; } previous_last = first_last ? D.new_shalfedge_pair(sv[2], previous_inner->twin(), -1) : D.new_shalfedge_pair(previous_last, previous_inner->twin(), -1, -1); previous_last->circle() = curr_outer->circle(); previous_last->twin()->circle() = curr_outer->twin()->circle(); CGAL_assertion(normalized(previous_last->circle()) == normalized(Sphere_circle(previous_last->source()->point(), previous_last->twin()->source()->point()))); previous_last->mark() = previous_last->twin()->mark() = BOP(previous_inner->incident_sface()->mark(), curr_outer->mark(), inv); if(!first_last) { SFace_handle sf_new = D.new_sface(); D.link_as_face_cycle(previous_last, sf_new); sf_new->mark() = BOP(previous_inner->incident_sface()->mark(), curr_outer->incident_sface()->mark(), inv); CGAL_NEF_TRACEN("new sface" << sf_new->mark() ); } first_last = false; } while(curr_outer != scb[1]); SHalfedge_around_svertex_circulator curr_inner(seb[1]); CGAL_For_all(curr_inner, see[1]) { CGAL_NEF_TRACEN("schleife " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); curr_inner->mark() = curr_inner->twin()->mark() = BOP(curr_inner->mark(), scb[1]->twin()->incident_sface()->mark(), inv); if(!equator[0] && curr_inner == seb[1]) continue; SFace_handle sf = curr_inner->twin()->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner->twin()), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; sf->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), scb[1]->twin()->incident_sface()->mark(), inv); } CGAL_assertion(curr_inner == see[1]); CGAL_NEF_TRACEN("before equator[2] " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); if(equator[2] || (!empty_c[0] && !empty_e[0])) { SFace_handle sf = curr_inner->twin()->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner->twin()), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; sf->mark() = BOP(curr_inner->twin()->incident_sface()->mark(), scb[1]->twin()->incident_sface()->mark(), inv); } else --curr_inner; CGAL_NEF_TRACEN("final sface " << curr_inner->source()->point() << "->" << curr_inner->twin()->source()->point()); SFace_handle sf = curr_inner->incident_sface(); SHalfedge_around_sface_circulator hfc(curr_inner), hend(hfc); CGAL_For_all(hfc,hend) hfc->incident_sface() = sf; } else if(empty_e[1] && !empty_c[1]) { CGAL_assertion_msg(!equator[0] && !equator[1] && !equator[2] && !equator[3], "not implemented, yet" ); CGAL_assertion_msg(empty_c[0], "not implemented, yet"); CGAL_assertion_msg(sv[2]->out_sedge() == SHalfedge_handle(), "not implemented, yet"); CGAL_assertion_msg(sv[3]->out_sedge() == SHalfedge_handle(), "not implemented, yet"); CGAL_assertion_msg(!empty_e[0], "not implemented, yet"); Mark outer_sf = seb[0]->twin()->incident_sface()->mark(); SHalfedge_handle se_prev = D.new_shalfedge_pair(sv[2], sv[3]); se_prev->circle() = scb[1]->circle(); se_prev->twin()->circle() = scb[1]->twin()->circle(); se_prev->mark() = se_prev->twin()->mark() = BOP(outer_sf, scb[1]->mark()); SHalfedge_around_svertex_const_circulator curr(scb[1]); ++curr; while(curr != scb[1]) { se_prev = D.new_shalfedge_pair(se_prev, se_prev->twin(), 1, -1); // SM_io_parser::dump(D, std::cerr); se_prev->circle() = curr->circle(); se_prev->twin()->circle() = curr->twin()->circle(); se_prev->mark() = se_prev->twin()->mark() = BOP(outer_sf, curr->mark()); SFace_handle sf_new = D.new_sface(); sf_new->mark() = BOP(outer_sf, curr->twin()->incident_sface()->mark(), inv); D.link_as_face_cycle(se_prev->twin(), sf_new); ++curr; } seb[0]->twin()->incident_sface()->mark() = BOP(outer_sf, scb[1]->twin()->incident_sface()->mark(), inv); D.link_as_face_cycle(se_prev, seb[0]->twin()->incident_sface()); } else if(empty_c[1] && !empty_e[1]) { CGAL_assertion_msg(!equator[0] && !equator[1] && !equator[2] && !equator[3], "not implemented, yet" ); CGAL_assertion_msg(empty_e[0], "not implemented, yet"); CGAL_assertion_msg(!empty_c[0], "not implemented, yet"); Mark outer_sf = scb[0]->twin()->incident_sface()->mark(); SHalfedge_around_svertex_circulator curr(seb[1]); CGAL_For_all(curr, see[1]) { curr->mark() = curr->twin()->mark() = BOP(curr->mark(), outer_sf, inv); curr->incident_sface()->mark() = BOP(curr->incident_sface()->mark(), outer_sf, inv); } } // else // CGAL_assertion_msg(false, "not implemented, yet"); // SM_io_parser::dump(D, std::cerr); return D.sphere_map(); } }; } //namespace CGAL #endif //CGAL_EDGE_EDGE_OVERLAY_H