CGAL users discussion list

[Peter Hachenberger <>]

On Tue, 2008-02-12 at 00:09 +0800, Max wrote:
> Hello Peter,
> 
> Sorry for my late response. But having more time studying the relevant 
> stuff 
> could get the discussion more effective.
> 
> >
> >> My question is: How can I mannualy (with code) construct a 
> >> (non-manifold) 
> >> Nef_polyhedron given a set of vertices and facets in 3D?
> >
> >Actually, just as you tried. I hope that the number type makes the
> >difference. We'll see.

> I'm afraid I've not get all that you meant. :-)
> 
> I've had a look at the Shell_to_nef_3 visitor class, and it seems to be 
> a kind of 'incremental builder' of nef_3 similar to that of Polyhedron_3. 
> 

You can use the incremental builder to construct a Polyhedron_3 and then
convert it to a Nef_3. There is nothing like that for Nef_3.


> Just more questions:
> 1) I found two implementations in your sample code: one uses "old impl"
> convert_inner_shell_to_polyhedron() and another new constrctor of Nef_3
> accepting a source nef_3 and a SFace_const_iterator of it. AFAIUC, they
> implementation the same functionality, but according to the result of my
> simple test, as mentioned in my previous post, the latter is a little bit
> faster. Is that right?

Yes. Implementing an even faster method is not trivial.

> 2) In your sample code, you use ++(N.volumes_begin()); to skip the first
> unbounded voulme of N, is it a formal convention that the infinite volume 
> of a nef_3 be at the very first position when we traverse the volumes?

The unbounded volume is always the first.

> 3) In my understanding, the 'outter shell' (I mean by this name the shell 
> that's only incident to the infinite volume) of a nef_3 is no different 
> from those 'inner shells'. I attempted omitting the ++(N.volumes_begin()); 
> statement to convert the 'outer shell' to a 'polyhedron' (here I means the 
> data structure and file format similar to a polyhedron, not necissarily 
> closed), but failed. Any hints is appriciated. (Both 'old' and 'new' impl
> tested)

Every volume is incident to one shell enclosing it (outer shell) and
several inner shells bounding objects taken away from that volume. The
volume always gives the outer shell first. Note that the unbounded
volume does not have an outer shell. You cannot convert the inner shell
of the infimaximal box into an off file. It does not have normal
coordinates. Polyhedron_3 does not support such coordinates and it
actually also does not make much sense.

> 4) I also attempted to attract the Build_polyhedron class from 
> Nef_polyhedron_3 
> and adapted it to meet my needa. But It also didn't work, my code is:
> 
> template <class Nef_3>
> class Build_polyhedron_from_nef_3 
>       : public CGAL::Modifier_base<typename CGAL::Polyhedron_3<typename 
> Nef_3::Kernel>::HDS>
> {
>       typedef typename Nef_3::Kernel Kernel;
>       typedef typename CGAL::Polyhedron_3<Kernel>::HDS HDS;
>       typedef typename Nef_3::Vertex_const_iterator Vertex_const_iterator;
>       typedef typename Nef_3::Volume_const_handle Volume_const_handle;
>       typedef typename Nef_3::Halffacet_cycle_const_iterator 
> Halffacet_cycle_const_iterator;
>       typedef typename Nef_3::SHalfedge_around_facet_const_circulator 
> SHalfedge_around_facet_const_circulator;
>       typedef typename Nef_3::Nef_rep::SNC_const_decorator 
> SNC_const_decorator;
> 
>       typedef typename Nef_3::Halffacet_const_handle Halffacet_const_handle;
>       typedef typename Nef_3::SFace_const_handle SFace_const_handle;
>       typedef typename Nef_3::Halfedge_const_handle Halfedge_const_handle;
>       typedef typename Nef_3::Vertex_const_handle Vertex_const_handle;
>       typedef typename Nef_3::SHalfedge_const_handle SHalfedge_const_handle;
>       typedef typename Nef_3::SHalfloop_const_handle SHalfloop_const_handle;
> 
>       template<typename Traits>
>       class Triangulation_handler2 
>       {
>               typedef typename Traits::Rp Kernel;
>               typedef CGAL::Nef_polyhedron_3<Kernel> Nef_3;
>               typedef typename Nef_3::Vertex_const_iterator 
> Vertex_const_iterator;
>               typedef typename Nef_3::Vertex_const_handle 
> Vertex_const_handle;
>               typedef typename Nef_3::Halffacet_const_handle 
> Halffacet_const_handle;
>               typedef typename Nef_3::Halffacet_cycle_const_iterator 
> Halffacet_cycle_const_iterator;
>               typedef typename 
> Nef_3::SHalfedge_around_facet_const_circulator 
> SHalfedge_around_facet_const_circulator;
>               typedef typename Kernel::Plane_3 Plane_3;
> 
>               typedef typename CGAL::Triangulation_vertex_base_2<Traits>    
>            Vb;
>               typedef typename 
> CGAL::Constrained_triangulation_face_base_2<Traits>     Fb;
>               typedef typename CGAL::Triangulation_data_structure_2<Vb,Fb>  
>            TDS;
>               typedef typename 
> CGAL::Constrained_triangulation_2<Traits,TDS>           CT;
> 
>               typedef typename CT::Face_handle           Face_handle;
>               typedef typename CT::Vertex_handle         CTVertex_handle;
>               typedef typename CT::Finite_faces_iterator 
> Finite_face_iterator;
>               typedef typename CT::Edge                  Edge;
> 
>               CT ct;
>               CGAL::Unique_hash_map<Face_handle, bool> visited;
>               CGAL::Unique_hash_map<CTVertex_handle, Vertex_const_handle> 
> ctv2v;
>               Finite_face_iterator fi;
>               Plane_3 supporting_plane;
> 
>       public:
>               Triangulation_handler2(Halffacet_const_handle f) : 
>                 visited(false), supporting_plane(f->plane()) {
> 
>                         Halffacet_cycle_const_iterator fci;
>                         for(fci=f->facet_cycles_begin(); 
> fci!=f->facet_cycles_end(); ++fci) {
>                                 if(fci.is_shalfedge()) {
>                                         
> SHalfedge_around_facet_const_circulator sfc(fci), send(sfc);
>                                         CGAL_For_all(sfc,send) {
>                                                 CGAL_NEF_TRACEN("  insert 
> point" << sfc->source()->source()->point());
>                                                 CTVertex_handle ctv = 
> ct.insert(sfc->source()->source()->point());
>                                                 ctv2v[ctv] = 
> sfc->source()->source();
>                                         }
>                                 }
>                         }
> 
>                         for(fci=f->facet_cycles_begin(); 
> fci!=f->facet_cycles_end(); ++fci) {
>                                 if(fci.is_shalfedge()) {
>                                         
> SHalfedge_around_facet_const_circulator sfc(fci), send(sfc);
>                                         CGAL_For_all(sfc,send) {
>                                                 CGAL_NEF_TRACEN("  insert 
> constraint" << sfc->source()->source()->point()
>                                                         << "->" << 
> sfc->source()->twin()->source()->point());
>                                                 
> ct.insert_constraint(sfc->source()->source()->point(),
>                                                         
> sfc->source()->twin()->source()->point());
>                                         }
>                                 }
>                         }
>                         CGAL_assertion(ct.is_valid());
> 
>                         CGAL_NEF_TRACEN("number of finite triangles " << 
> ct.number_of_faces());
> 
>                         typename CT::Face_handle infinite = 
> ct.infinite_face();
>                         typename CT::Vertex_handle ctv = 
> infinite->vertex(1);
>                         if(ct.is_infinite(ctv)) ctv = infinite->vertex(2);
>                         CGAL_assertion(!ct.is_infinite(ctv));
> 
>                         typename CT::Face_handle opposite;
>                         typename CT::Face_circulator vc(ctv,infinite);
>                         do { opposite = vc++;
>                         } while(!ct.is_constrained(typename 
> CT::Edge(vc,vc->index(opposite))));
>                         typename CT::Face_handle first = vc;
> 
>                         CGAL_assertion(!ct.is_infinite(first));
>                         traverse_triangulation(first, 
> first->index(opposite));
> 
>                         fi = ct.finite_faces_begin();
>                 }
> 
>                 void traverse_triangulation(Face_handle f, int parent) {
>                         visited[f] = true;
>                         if(!ct.is_constrained(Edge(f,ct.cw(parent))) && 
> !visited[f->neighbor(ct.cw(parent))]) {
>                                 Face_handle 
> child(f->neighbor(ct.cw(parent)));
>                                 traverse_triangulation(child, 
> child->index(f));
>                         } 
>                         if(!ct.is_constrained(Edge(f,ct.ccw(parent))) && 
> !visited[f->neighbor(ct.ccw(parent))]) {
>                                 Face_handle 
> child(f->neighbor(ct.ccw(parent)));
>                                 traverse_triangulation(child, 
> child->index(f));
>                         } 
>                 } 
> 
>                 template<typename Triangle_3>
>                 bool get_next_triangle(Triangle_3& tr) {
>                         while(fi != ct.finite_faces_end() && visited[fi] == 
> false) ++fi;
>                         if(fi == ct.finite_faces_end()) return false;
>                         tr = Triangle_3(fi->vertex(0)->point(), 
> fi->vertex(1)->point(), fi->vertex(2)->point());
>                         ++fi;
>                         return true;
>                 }
> 
>                 bool same_orientation(Plane_3 p1) const {
>                         if(p1.a() != 0)
>                                 return CGAL::sign(p1.a()) == 
> CGAL::sign(supporting_plane.a());
>                         if(p1.b() != 0)
>                                 return CGAL::sign(p1.b()) == 
> CGAL::sign(supporting_plane.b());
>                         return CGAL::sign(p1.c()) == 
> CGAL::sign(supporting_plane.c());
>                 }
> 
>                 template<typename PIB, typename Index>
>                 void handle_triangles(PIB& pib, Index& VI) {
>                         while(fi != ct.finite_faces_end() && visited[fi] == 
> false) ++fi;
>                         while(fi != ct.finite_faces_end()) {
>                                 Plane_3 plane(fi->vertex(0)->point(),
>                                         fi->vertex(1)->point(),
>                                         fi->vertex(2)->point());
>                                 pib.begin_facet();
>                                 if(same_orientation(plane)) {
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(0)]]);
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(1)]]);
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(2)]]);
>                                 } else {
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(0)]]);
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(2)]]);
>                                         
> pib.add_vertex_to_facet(VI[ctv2v[fi->vertex(1)]]);
>                                 }
>                                 pib.end_facet();
>                                 do {
>                                         ++fi;
>                                 } while(fi != ct.finite_faces_end() && 
> visited[fi] == false);
>                         }
>                 }
>       };
> 
>       class Visitor 
>       {
>               typedef typename 
> CGAL::Triangulation_euclidean_traits_xy_3<Kernel> XY;
>               typedef typename 
> CGAL::Triangulation_euclidean_traits_yz_3<Kernel> YZ;
>               typedef typename 
> CGAL::Triangulation_euclidean_traits_xz_3<Kernel> XZ;
> 
>               const CGAL::Object_index<Vertex_const_iterator>& VI;
>               CGAL::Polyhedron_incremental_builder_3<HDS>& B;
>               const SNC_const_decorator& D;
> 
>       public:
>               Visitor(CGAL::Polyhedron_incremental_builder_3<HDS>& BB,
>                       const SNC_const_decorator& sd,
>                       CGAL::Object_index<Vertex_const_iterator>& vi) : 
> VI(vi), B(BB), D(sd){}
> 
>               void visit(Halffacet_const_handle opposite_facet)
>               {
>                       CGAL_NEF_TRACEN("Build_polyhedron_from_nef_3: visit 
> facet " << opposite_facet->plane());
> 
>                       SHalfedge_const_handle se;
>                       Halffacet_cycle_const_iterator fc;
> 
>                       Halffacet_const_handle f = opposite_facet->twin();
> 
>                       SHalfedge_around_facet_const_circulator 
>                               sfc1(f->facet_cycles_begin()), sfc2(sfc1);
> 
>                       if(++f->facet_cycles_begin() != f->facet_cycles_end() 
> ||        // ?
>                               ++(++(++sfc1)) != sfc2) // facet's vertices 
> is more than 3
>                       {
>                               Vector_3 orth = 
> f->plane().orthogonal_vector();
>                               int c = CGAL::abs(orth[0]) > 
> CGAL::abs(orth[1]) ? 0 : 1;
>                               c = CGAL::abs(orth[2]) > CGAL::abs(orth[c]) ? 
> 2 : c;
> 
>                               if(c == 0) {
>                                       Triangulation_handler2<YZ> th(f);
>                                       th.handle_triangles(B, VI);
>                               } else if(c == 1) {
>                                       Triangulation_handler2<XZ> th(f);
>                                       th.handle_triangles(B, VI);
>                               } else if(c == 2) {
>                                       Triangulation_handler2<XY> th(f);
>                                       th.handle_triangles(B, VI);
>                               } else
>                                       CGAL_assertion_msg(false, "wrong 
> value");
>                       } 
>                       else 
>                       {
>                               B.begin_facet();
>                               fc = f->facet_cycles_begin();
>                               se = SHalfedge_const_handle(fc);
>                               CGAL_assertion(se!=0);
>                               SHalfedge_around_facet_const_circulator 
> hc_start(se);
>                               SHalfedge_around_facet_const_circulator 
> hc_end(hc_start);
>                               CGAL_For_all(hc_start,hc_end) {
>                                       CGAL_NEF_TRACEN("   add vertex " << 
> hc_start->source()->center_vertex()->point());
>                                       
> B.add_vertex_to_facet(VI[hc_start->source()->center_vertex()]);
>                               }
>                               B.end_facet();
>                       }
>               }
> 
>               void visit(SFace_const_handle) {}
>               void visit(Halfedge_const_handle) {}
>               void visit(Vertex_const_handle) {}
>               void visit(SHalfedge_const_handle) {}
>               void visit(SHalfloop_const_handle) {}
>       };
> 
> public:
>       const Nef_3 &n_;
>       CGAL::Object_index<Vertex_const_iterator> VI;
> 
>       Build_polyhedron_from_nef_3(const Nef_3& n) : 
>       n_(n), VI(n.vertices_begin(),n.vertices_end(),'V') {}
> 
>       void operator()( HDS& hds) 
>       {
>               typedef CGAL::Polyhedron_incremental_builder_3<HDS> Builder;
>               Builder B(hds, true);
> 
>               int skip_volumes;
>               B.begin_surface(n_.number_of_vertices(), 
>                       2*n_.number_of_vertices()-4,
>                       3*n_.number_of_vertices()-6);
>                       skip_volumes = 1;
> 
>               int vertex_index = 0;
>               Vertex_const_iterator v;
>               CGAL_forall_vertices(v,n_) {
>                       VI[v]=vertex_index++;
>                       B.add_vertex(v->point());
>               }     
> 
>               Visitor V(B,n_,VI);
>               Volume_const_handle c;
>               CGAL_forall_volumes(c,n_)
>                       
> n_.visit_shell_objects(SFace_const_handle(c->shells_begin()),V);
>               B.end_surface();
>       }
> };

I need time to browse through it, but the incremental builder does not
work for Nef_3 objects---you can only build Polyhedron_3 objects with
it.

Peter