CGAL users discussion list

["Max" <>]

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. 

>
>> Another question further: After the construction, how can I get a group 
>> of manifold Polyhedron_3 as a "regularization" of this Nef_3?
>
>You mean, you want to have a separate Nef_3 for every solid in a single
>given Nef_3? Have I already given you code for extracting a boundary
>from a Nef_3?
>

Yes. but I'm afraid my knowledge was too limited to follow you at that time.
Now, following the direction I could extract all of the 'inner shells' of 
the bounded volumes of a nef_3. Thank you.

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?

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?

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)

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();
        }
};

Thanks for any help.

Max

>Peter
>-- 
>You are currently subscribed to cgal-discuss.
>To unsubscribe or access the archives, go to
>https://lists-sop.inria.fr/wws/info/cgal-discuss
>