snc_decorator.h

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

    SM_io_parser IO1( std::cerr, D1);
    CGAL_NEF_TRACEN(" sphere maps before local binary operation");
    CGAL_NEF_TRACEN(v0->debug());
    CGAL_NEF_TRACEN(v1->debug());
    IO0.debug();    IO1.debug();
    IO0.print();    IO1.print();
#endif // CGAL_NEF3_DUMP_SPHERE_MAPS
#undef CGAL_NEF3_DUMP_SPHERE_MAPS

   CGAL_assertion( v0->point() == v1->point());
    Vertex_handle v01 = rsnc.new_vertex( v0->point(), BOP( v0->mark(),v1->mark()));
    //    std::cerr <<"BOP Vertex "<< v0->point() << ":" 
    //       	      << v0->mark()<<" "<<v1->mark()<<std::endl;
    CGAL_NEF_TRACEN("  binop result on vertex "<<&*v01<<" on "<<&*(v01->sncp()));
    SM_overlayer O(&*v01);
    O.subdivide( &*v0, &*v1, A);
    /*
    SHalfedge_iterator sei2;
    CGAL_forall_sedges(sei2, O) {
      std::cerr << "front " << sei2->get_index() << std::endl;
      std::cerr << "back  " << sei2->twin()->get_index() << std::endl;
      } */
    O.select( BOP);
    O.simplify(A);

#ifdef CGAL_NEF3_DUMP_SPHERE_MAPS
    CGAL_NEF_TRACEN(" result sphere map:");
    SM_io_parser IO01( std::cerr, v01);
    CGAL_NEF_TRACEN(v01->debug());
    IO01.print();
    CGAL_NEF_TRACEN(" sphere maps after local binary operation");
    IO0.debug();
    IO1.debug();
#endif //CGAL_NEF3_DUMP_SPHERE_MAPS

#ifdef CGAL_NEF3_SM_VISUALIZOR
    typedef SNC_SM_visualizor<SNC_structure> SMV;
    CGAL::OGL::add_sphere();
    SMV V0(v0, CGAL::OGL::spheres_.back());
    V0.draw_map();
    SMV V1(v1, CGAL::OGL::spheres_.back());
    V1.draw_map();
    SMV V01(v01, CGAL::OGL::spheres_.back());
    V01.draw_map();
    CGAL::OGL::start_viewer();
    CGAL_NEF_TRACEN("any key to continue...");
    char c;
    std::cin >> c;
#endif // CGAL_NEF3_VISUALIZOR
    return v01;
  }

  template<typename Selection>
    Vertex_handle binop_local_views(Vertex_const_handle v0, 
				    Vertex_const_handle v1,
				    const Selection& BOP, 
				    SNC_structure& rsnc) {

    CGAL_assertion( v0->point() == v1->point());
    Vertex_handle v01 = rsnc.new_vertex( v0->point(), BOP( v0->mark(),v1->mark()));
    CGAL_NEF_TRACEN("  binop result on vertex "<<&*v01<<" on "<<&*(v01->sncp()));
    SM_overlayer O(&*v01);
    O.subdivide( &*v0, &*v1);
    O.select( BOP);
    O.simplify();
    return v01;
  }

  Vertex_handle create_local_view_on( const Point_3& p, Halfedge_handle e) {
    SNC_constructor C(*sncp());
    return C.create_from_edge( e, p);
  }
  
  Vertex_handle create_local_view_on( const Point_3& p, Halffacet_handle f) {
    SNC_constructor C(*sncp());
    return C.create_from_facet( f, p);
  }

  Vertex_handle create_local_view_on( const Point_3& p, Volume_const_handle c) {
    Vertex_handle v = sncp()->new_vertex( p, c->mark());
    SM_decorator SD(&*v);
    SFace_handle f = SD.new_sface();
    f->mark() = c->mark();
    CGAL_NEF_TRACEN("volume "<<&*c<<" marked as "<<c->mark()); 
    //    SM_point_locator PL(v);
    //    PL.init_marks_of_halfspheres(); // necessary to init default marks
    return v;
  }

  /*
  Vertex_handle 
    qualify_with_respect( const Point_3 p, 
			  const SNC_point_locator* pl1,
			  SNC_structure& result) {
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
    Volume_handle c;
    Self D(result);

#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
    number_of_point_location_queries++;
    timer_point_location.start();
#endif
    Object_handle o = pl1->locate(p);
#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
    timer_point_location.stop();
#endif
    if( CGAL::assign( v, o)) {
      CGAL_NEF_TRACEN("<-> vertex local view on "<< v->point());
      return v;
    }
    else if( CGAL::assign( e, o)) {
      CGAL_NEF_TRACEN("<-> edge local view of "<<p<<" on "<<&*e);
      return D.create_local_view_on( p, e);
    }
    else if( CGAL::assign( f, o)) {
      CGAL_NEF_TRACEN("<-> facet local view of "<<p<<" on "<<&*f);
      return D.create_local_view_on( p, f);
    }
    else if( CGAL::assign( c, o)) {
      CGAL_NEF_TRACEN("<-> volume local view of "<<p<<" on "<<&*c);
      return D.create_local_view_on( p, c);
    }
    else CGAL_assertion_msg(0, "Where is the point then?");
    return Vertex_handle(); // never reached
  }
  */
  /*
  Vertex_handle 
    qualify_with_respect( const Point_3& p, 
	                  Object_handle o,
			  const SNC_structure& snc) {
    Halfedge_const_handle e;
    Halffacet_handle f;
    if( CGAL::assign( e, o))
      return create_local_view_on( p, e);
    else if( CGAL::assign( f, o))
      return create_local_view_on( p, f);
    else 
      CGAL_assertion_msg( 0, "wrong handle");
    return Vertex_handle(); // never reached
  }
      */

  template <typename SNC_decorator, 
            typename Selection, 
            typename Association>
  class Intersection_call_back : 
    public SNC_point_locator::Intersection_call_back 
  {
    typedef typename SNC_decorator::Decorator_traits Decorator_traits;
    typedef typename Decorator_traits::Halfedge_handle Halfedge_handle;
    typedef typename Decorator_traits::Halffacet_handle Halffacet_handle;
    
  public:
    Intersection_call_back( SNC_structure& s0, SNC_structure& s1,
			    const Selection& _bop, SNC_structure& r, 
			    bool invert_order, Association& Ain) :
      snc0(s0), snc1(s1), bop(_bop), result(r),
      inverse_order(invert_order), A(Ain) {}

      void operator()(Halfedge_handle e0, Object_handle o1, const Point_3& ip)
      const {
          
#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersections;
#endif

      Halfedge_handle e;
      Halffacet_handle f;
      
      Point_3 p(normalized(ip));

      CGAL_NEF_TRACEN("Intersection_call_back: intersection reported on " << p << " (normalized: " << normalized(p) << " )");
#ifdef CGAL_NEF_DEBUG
      CGAL_NEF_TRACEN("edge 0 has source " << e0->source()->point() << " and direction " << e0->vector());
      if( CGAL::assign( e, o1)) {
	CGAL_NEF_TRACEN("edge 1 has source " << e->source()->point() << " and direction " << e->vector());
      }
      else if( CGAL::assign( f, o1)) {
	CGAL_NEF_TRACEN("face 1 has plane equation " << f->plane());
      }
      else 
      	CGAL_assertion_msg( 0, "wrong handle");
#endif      

#if defined (CGAL_NEF3_TIMER_OVERLAY) || (CGAL_NEF3_TIMER_INTERSECTION)
      timer_overlay.start();
#endif

      if( CGAL::assign( e, o1)) {
	//	std::cerr << "inverse order " << inverse_order << std::endl;
	Self D(result);
	Vertex_handle v0, v1;
	v0 = D.create_local_view_on( p, e0);
	v1 = D.create_local_view_on( p, e);
	if( inverse_order)
	  std::swap( v0, v1);
	SNC_constructor C(result);
#ifdef CGAL_NEF_EXPERIMENTAL_CODE
	Sphere_map* M0 = C.create_edge_edge_overlay(e0, e, p, bop, inverse_order, A);
	//	SM_overlayer O(M0);
	//	O.simplify(A);
#else
	D.binop_local_views( v0, v1, bop, result,A);
	result.delete_vertex(v0);
	result.delete_vertex(v1);
#endif
      }
      else if( CGAL::assign( f, o1)) {
#ifdef CGAL_NEF3_OVERLAY_BY_HAND_OFF
	Self D(result);
	Vertex_handle v0, v1;
	v0 = D.create_local_view_on( p, e0);
	v1 = D.create_local_view_on( p, f);
	if( inverse_order)
	  std::swap( v0, v1);
	D.binop_local_views( v0, v1, bop, result,A);
	result.delete_vertex(v0);
	result.delete_vertex(v1);	
#else // CGAL_NEF3_OVERLAY_BY_HAND_OFF
	SNC_constructor C(result);
	Sphere_map* M0 = C.create_edge_facet_overlay(e0, f, p, bop, inverse_order, A);
	SM_overlayer O(M0);
	O.simplify(A);
#endif // CGAL_NEF3_OVERLAY_BY_HAND_OFF
      }
      else 
	CGAL_assertion_msg( 0, "wrong handle");

#if defined (CGAL_NEF3_TIMER_OVERLAY) || (CGAL_NEF3_TIMER_INTERSECTION)
      timer_overlay.stop();
#endif

    }
  private:
    const SNC_structure& snc0;
    const SNC_structure& snc1;
    const Selection& bop;
    SNC_structure& result;
    bool inverse_order;
    Association& A;
  };

  template <typename Selection>
    void binary_operation( SNC_point_locator* pl0,
			   const SNC_structure& snc1,
			   const SNC_point_locator* pl1,
			   const SNC_structure& snc2,
			   const SNC_point_locator* pl2,
			   const Selection& BOP)
    /*{\opPerforms a binary operation defined on |BOP| between two
      SNC structures.  The input structures are not modified and the
      result of the operation is stored in |result|.
      \precondition: the structure |result| is empty.}*/ {

    //    std::cerr << "check order " << &snc1 << ", " << &snc2 << std::endl;
    //    CGAL_NEF_SETDTHREAD(23);
    CGAL_assertion( sncp()->is_empty());
    CGAL_assertion( pl1 != NULL && pl2 != NULL);
    //    CGAL_NEF_SETDTHREAD(19*131*43);
    //    Progress_indicator_clog v_qualifying
    //      (sncp()->number_of_vertices()+snc1i.number_of_vertices(),
    //       "binary_operator: qualifying vertices...");

#ifdef CGAL_NEF3_TIMER_BINARY_OPERATION
    CGAL::Timer timer_binary_operation;
    timer_binary_operation.start();
#endif 

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
    timer_sphere_sweeps.reset();
    number_of_sphere_sweeps=0;
    number_of_edge_facet_overlays=0;
    number_of_clones=0;
#endif

#ifdef CGAL_NEF3_TIMER_POINT_LOCATION    
    timer_point_location.reset();
    number_of_point_location_queries=0;
#endif

#ifdef CGAL_NEF3_TIMER_OVERLAY
      timer_overlay.reset();
#endif

#ifdef CGAL_NEF3_DUMP_STATISTICS
      number_of_intersections=0;
      number_of_intersection_candidates=0;
#endif

    Unique_hash_map<Vertex_const_handle, bool> ignore(false);
    Vertex_const_iterator v0;

    //    CGAL_NEF_SETDTHREAD(19*43*131);
    CGAL_NEF_TRACEN("=> binary operation");

#ifdef CGAL_NEF3_DUMP_SNC_OPERATORS
    CGAL_NEF_TRACEN("=> first operand:");
    SNC_io_parser<SNC_structure> O0(std::cout, const_cast<SNC_structure&>(snc1));
    O0.print();
    CGAL_NEF_TRACEN("=> second operand:");
    SNC_io_parser<SNC_structure> O1(std::cout, const_cast<SNC_structure&>(snc2));
    O1.print();
#endif // CGAL_NEF3_DUMP_SNC_OPERATORS

#ifdef CGAL_NEF3_FACET_WITH_BOX 
    SNC_constructor C1(snc1);
    C1.create_box();
    SNC_constructor C2(snc2);
    C2.create_box();
#endif

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

    CGAL_NEF_TRACEN("=> for all v0 in snc1, qualify v0 with respect snc2");
    //    int i=2;
    Association A;
    SHalfedge_const_iterator sei;
    CGAL_forall_shalfedges(sei, snc1)
      A.initialize_hash(sei);
    CGAL_forall_shalfedges(sei, snc2)
      A.initialize_hash(sei);
    SHalfloop_const_iterator sli;
    CGAL_forall_shalfloops(sli, snc1)
      A.initialize_hash(sli);
    CGAL_forall_shalfloops(sli, snc2)
      A.initialize_hash(sli);

    CGAL_forall_vertices( v0, snc1) {
      CGAL_assertion(!ignore[v0]);
      Point_3 p0(v0->point());
      Vertex_handle v;
      Halfedge_handle e;
      Halffacet_handle f;
      Volume_handle c;
      CGAL_NEF_TRACEN("Locating point " << p0);
      
#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
      ++number_of_point_location_queries;
      timer_point_location.start();