snc_decorator.h

很多二维 三维几何计算算法 C++ 类库

#endif 
      Object_handle o = pl2->locate(p0);
#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
      timer_point_location.stop();
#endif 
    
#if defined(CGAL_NEF3_TIMER_OVERLAY)
      timer_overlay.start();
#endif
      if( CGAL::assign( v, o)) {
	CGAL_NEF_TRACEN("p0 found on vertex");
	binop_local_views( v0, v, BOP, *sncp(),A);
	ignore[v] = true;
      }
      else if( CGAL::assign( e, o)) {
	CGAL_NEF_TRACEN("p0 found on edge");
	Vertex_handle v1 = create_local_view_on( p0, e);
	binop_local_views( v0, v1, BOP, *sncp(),A);
	sncp()->delete_vertex(v1);
      }
      else if( CGAL::assign( f, o)) {
	CGAL_NEF_TRACEN("p0 found on facet" << f->plane());
	Vertex_handle v1 = create_local_view_on( p0, f);
	binop_local_views( v0, v1, BOP, *sncp(),A);
	sncp()->delete_vertex(v1);
      }
      else if( CGAL::assign( c, o)) {
	CGAL_NEF_TRACEN("p0 found on volume with mark " << c->mark());
#ifdef CGAL_NEF3_OVERLAY_IF_NEEDED_OFF
        if(true) {
#else
	if( BOP( true, c->mark()) != BOP( false, c->mark())) {
#endif
#ifdef CGAL_NEF3_OVERLAY_BY_HAND_OFF
	  Vertex_handle v1 = create_local_view_on( p0, c);
	  binop_local_views( v0, v1, BOP, *sncp(),A);
	  sncp()->delete_vertex(v1);
#else
	  SNC_constructor C(*sncp());
	  Vertex_handle v1 = C.clone_SM(v0);
	  SM_decorator SM(&*v1);
	  SM.change_marks(BOP, c->mark());
	  SM_overlayer O(&*v1);
	  O.simplify(A);
#endif
	} else {
	  CGAL_NEF_TRACEN("vertex in volume deleted " << std::endl << 
		 "  vertex: " <<  v0->point() << std::endl << 
		 "  mark of volume: " << c->mark()); 
	}
      }
      else CGAL_assertion_msg( 0, "wrong handle");

#if defined(CGAL_NEF3_TIMER_OVERLAY)
      timer_overlay.stop();
#endif
      }
    CGAL_NEF_TRACEN("\nnumber of vertices (so far...) = "<< sncp()->number_of_vertices());

    CGAL_NEF_TRACEN("=> for all v1 in snc1, qualify v1 with respect snc0");
    CGAL_forall_vertices( v0, snc2) {
      //      v_qualifying++;
      if(ignore[v0]) continue;
      Point_3 p1(v0->point());
      Halfedge_handle e;
      Halffacet_handle f;
      Volume_handle c;
      CGAL_NEF_TRACEN("Locating point " << p1);

#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
      number_of_point_location_queries++;
      timer_point_location.start();
#endif 
      Object_handle o = pl1->locate(p1);
#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
      timer_point_location.stop();
#endif 
      
      CGAL_assertion_code(Vertex_handle v);
      CGAL_assertion( !CGAL::assign( v, o));

#if defined(CGAL_NEF3_TIMER_OVERLAY)
      timer_overlay.start();
#endif
      if( CGAL::assign( e, o)) {
	CGAL_NEF_TRACEN("p1 found on edge");
	Vertex_handle v1 = create_local_view_on( p1, e);
	binop_local_views( v1, v0, BOP, *sncp(),A);
	sncp()->delete_vertex(v1);
      } 
      else if( CGAL::assign( f, o)) {
	CGAL_NEF_TRACEN("p1 found on facet");
	Vertex_handle v1 = create_local_view_on( p1, f);
	binop_local_views( v1, v0, BOP, *sncp(),A);
	sncp()->delete_vertex(v1);
      } 
      else if( CGAL::assign( c, o)) {
	CGAL_NEF_TRACEN("p1 found on volume with mark " << c->mark());
#ifdef CGAL_NEF3_OVERLAY_IF_NEEDED_OFF
        if(true) {
#else
	if( BOP( c->mark(), true) != BOP( c->mark(), false)) {
#endif
#ifdef CGAL_NEF3_OVERLAY_BY_HAND_OFF
	Vertex_handle v1 = create_local_view_on( p1, c);
	binop_local_views( v1, v0, BOP, *sncp(),A);
	sncp()->delete_vertex(v1);	  
#else
	  SNC_constructor C(*sncp());
	  Vertex_handle v1 = C.clone_SM(v0);
	  SM_decorator SM(&*v1);
	  SM.change_marks(c->mark(), BOP);
	  SM_overlayer O(&*v1);
	  O.simplify(A);
#endif
	} else {
	  CGAL_NEF_TRACEN("vertex in volume deleted " << std::endl << 
		 "  vertex: " <<  v0->point() << std::endl << 
		 "  mark of volume: " << c->mark()); 
	}
      }
      else CGAL_assertion_msg( 0, "wrong handle");

#if defined(CGAL_NEF3_TIMER_OVERLAY)
      timer_overlay.stop();
#endif
      }

    CGAL_NEF_TRACEN("\nnumber of vertices (so far...) = "<< sncp()->number_of_vertices());

    // Each time the intersect method of the point locator for the 
    // SNC structure finds an intersection between the segment defined
    // by an edge on the other SNC structure, the call back method is
    // called with the intersecting objects and the intersection point.
    // The responsability of the call back functor is to construct the
    // local view on the intersection point on both SNC structures,
    // overlay them and add the resulting sphere map to the result.

    // CGAL_NEF_SETDTHREAD(19*509*43*131);

    //    Progress_indicator_clog ee_intersections
    //      (sncp()->number_of_edges(),
    //       "binary_operator: finding edge-edge intersections...");

    Intersection_call_back<SNC_decorator, Selection, Association> call_back0
      ( const_cast<SNC_structure&>(snc1), const_cast<SNC_structure&>(snc2), BOP, *sncp(), false, A);
    Intersection_call_back<SNC_decorator, Selection, Association> call_back1 
      ( const_cast<SNC_structure&>(snc2), const_cast<SNC_structure&>(snc2), BOP, *sncp(), true, A);

#ifdef CGAL_NEF3_TIMER_INTERSECTION
    double split_intersection = timer_overlay.time();
    CGAL::Timer timer_intersection;
    timer_intersection.start();
#endif
   
    // choose between intersection algorithms
#ifdef CGAL_NEF3_INTERSECTION_BY_KDTREE
    Halfedge_iterator e0, e1;
    /*
    CGAL_NEF_TRACEN("=> finding edge-edge intersections...");
    CGAL_forall_edges( e0, snc1) {
      //      ee_intersections++;
      pl2->intersect_with_edges( e0, call_back0);
    }
    CGAL_NEF_TRACEN("\nnumber of vertices (so far...) = "<< sncp()->number_of_vertices());

    //    Progress_indicator_clog ef_intersections
    //      (sncp()->number_of_edges()+snc1i.number_of_edges(),
    //       "binary_operator: finding edge-facet intersections...");

    CGAL_NEF_TRACEN("number of vertices (so far...) = "<< sncp()->number_of_vertices());
    CGAL_NEF_TRACEN("=> finding edge0-facet1 intersections...");
    CGAL_forall_edges( e0, snc1) {
      //      ef_intersections++;
      pl2->intersect_with_facets( e0, call_back0);
    }
    CGAL_NEF_TRACEN("\nnumber of vertices (so far...) = "<< sncp()->number_of_vertices());
    */

    CGAL_forall_edges(e0,const_cast<SNC_structure&>(snc1))
      pl2->intersect_with_edges_and_facets(e0,call_back0);


    CGAL_NEF_TRACEN("=> finding edge1-facet0 intersections...");
    CGAL_forall_edges( e1,const_cast<SNC_structure&>(snc2)) {
      //      ef_intersections++;
      pl1->intersect_with_facets( e1, call_back1);
    }
    CGAL_NEF_TRACEN("\nnumber of vertices (so far...) = "<< sncp()->number_of_vertices());
#elif defined CGAL_NEF3_INTERSECTION_NAIVE
    
    CGAL::SNC_point_locator_naive<SNC_decorator> pln1;
    CGAL::SNC_point_locator_naive<SNC_decorator> pln2;
    pln1.initialize(const_cast<SNC_structure*>(&snc1));
    pln2.initialize(const_cast<SNC_structure*>(&snc2));
    Halfedge_iterator e0;   
    CGAL_forall_edges(e0,const_cast<SNC_structure&>(snc1))
      pln2.intersect_with_edges_and_facets(e0,call_back0);
    CGAL_forall_edges(e0,const_cast<SNC_structure&>(snc2))
      pln1.intersect_with_facets( e0, call_back1);

#else
    CGAL_NEF_TRACEN("intersection by fast box intersection");
        binop_intersection_test_segment_tree<SNC_decorator> binop_box_intersection;
        binop_box_intersection(call_back0, call_back1, 
			       const_cast<SNC_structure&>(snc1), 
			       const_cast<SNC_structure&>(snc2));
#endif

#ifdef CGAL_NEF3_TIMER_INTERSECTION
    timer_intersection.stop();
    if(cgal_nef3_timer_on)
      std::cout << "Runtime_intersection: "
		<< timer_intersection.time()-timer_overlay.time()+split_intersection 
		<< std::endl;
#endif

    CGAL_NEF_TRACEN("=> resultant vertices (before simplification): ");
    CGAL_assertion_code(CGAL_forall_vertices( v0, *sncp()) 
			  CGAL_NEF_TRACEN(&*v0<<" "<<v0->point()));

    SNC_external_structure es(*sncp(), pl0);
    es.build_after_binary_operation(A);

#ifdef CGAL_NEF3_DUMP_SNC_OPERATORS
    CGAL_NEF_TRACEN("=> construction completed, result: ");
    SNC_io_parser<SNC_structure> Op(std::cout, *sncp());
    Op.print();
#endif

#ifdef CGAL_NEF3_TIMER_PLANE_SWEEPS
    if(cgal_nef3_timer_on) {
      std::cout << "Number_of_plane_sweeps: " 
		<< number_of_plane_sweeps << std::endl;
      std::cout << "Runtime_plane_sweeps: "
		<< timer_plane_sweeps.time() << std::endl;
    }
#endif
    
#ifdef CGAL_NEF3_DUMP_STATISTICS
    if(cgal_nef3_timer_on) {
      std::cout << "Vertices_in_object_A: "
		<< snc1.number_of_vertices() << std::endl;
      std::cout << "Vertices_in_object_B: "
		<< snc2.number_of_vertices() << std::endl;
      std::cout << "Number_of_intersections: "
		<< number_of_intersections << std::endl;
      std::cout << "Number_of_intersection_candidates: "
		<< number_of_intersection_candidates << std::endl;    
      std::cout << "Vertices_in_Result: "
		<< sncp()->number_of_vertices() << std::endl;
    }
#endif

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
    if(cgal_nef3_timer_on) {
      std::cout << "Number_of_edge_facet_overlays: " 
		<< number_of_edge_facet_overlays << std::endl;
      std::cout << "Number_of_clones: " 
		<< number_of_clones << std::endl;
      std::cout << "Number_of_sphere_sweeps: " 
		<< number_of_sphere_sweeps << std::endl;
      std::cout << "Runtime_sphere_sweeps: "
		<< timer_sphere_sweeps.time() << std::endl;
    }
#endif

#if defined (CGAL_NEF3_TIMER_SPHERE_SWEEPS) && defined (CGAL_NEF3_TIMER_PLANE_SWEEPS)
    if(cgal_nef3_timer_on) {
      std::cout << "Runtime_all_sweeps: "
		<< timer_sphere_sweeps.time()+timer_plane_sweeps.time() << std::endl;
    }
#endif

#ifdef CGAL_NEF3_TIMER_OVERLAY
    if(cgal_nef3_timer_on) {
      std::cout << "Runtime_overlay: " 
		<< timer_overlay.time() << std::endl;
    }
#endif

#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
    if(cgal_nef3_timer_on) {
      std::cout << "Number_of_ray_shooting_queries: "
		<< number_of_ray_shooting_queries << std::endl;
      std::cout << "Runtime_ray_shooting: "
		<< timer_ray_shooting.time() << std::endl;
      std::cout << "Number_of_point_location_queries: "
		<< number_of_point_location_queries << std::endl;
      std::cout << "Runtime_point_location: "
		<< timer_point_location.time() << std::endl;
      std::cout << "Number_of_kd_tree_queries: "
		<< number_of_point_location_queries + 
	           number_of_ray_shooting_queries << std::endl;
      std::cout << "Runtime_kd_tree_queries: "
		<< timer_point_location.time() + 
                   timer_ray_shooting.time() << std::endl;
    }
#endif 

#ifdef CGAL_NEF3_TIMER_BINARY_OPERATION
    if(cgal_nef3_timer_on) {
      timer_binary_operation.stop();
      std::cout << "Runtime_binary_operation: " 
		<< timer_binary_operation.time() << std::endl;
    }
#endif 
    }
  

  bool is_valid( bool verb = false, int level = 0) {
    
    Verbose_ostream verr(verb);
    verr << "begin CGAL::SNC_decorator<...>::is_valid( verb=true, "
      "level = " << level << "):" << std::endl;
    
    int max = number_of_vertices() 
      + number_of_halfedges() 
      + number_of_halffacets() 
      + number_of_volumes()
      + 2 * sncp()->number_of_shalfedges()
      + sncp()->number_of_shalfloops()
      + sncp()->number_of_sfaces();
    int count = 0;

    bool valid = true;
    Vertex_iterator vi;
    std::list<Point_3> Points(false);   // durch hashmap ersetzen    
    CGAL_forall_vertices(vi,*this) {
      if(!valid) break;

      valid = valid && (vi->sncp()==sncp());
      valid = valid && vi->is_valid(verb, level);

      SM_decorator SD(&*vi);
      Unique_hash_map<SVertex_handle, bool> SVvisited(false);
      Unique_hash_map<SHalfedge_handle, bool> SEvisited(false);
      Unique_hash_map<SFace_handle, bool> SFvisited(false);

      valid = valid && SD.is_valid(SVvisited,SEvisited,SFvisited, verb, level);

      Points.push_back(vi->point());