hello guys,
i'm trying to split all the edges of a mesh into 2 sub-edges, the pseudo code could be simple as this: for each edge e in the edge list { split edge e into e1 and e2; } but i'm afraid if i simply do that, the code will loop forever, since the newly generated edges e1 and e2 can be traveled also by the loop and generate more edges, however i only need the original edges to be splitted. i don't know where the new edges e1 and e2 are inserted into the edge list of the CGAL polyhedron data structure. are they all inserted to the end of the list or somewhere else or just replace the position of e? and another question is for(edgeiter=edge.begin();edgeiter<edge.end();++edgeiter) { split edgeiter; // will edgeiter become null here? } thank you very much. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
hi Bill,
you may wanna try recursive longest edge bisection using a priority queue such as /* USAGE Polyhedron mesh; Bisection bisection(&mesh); unsigned int nb_splits = bisection(sqlen); // max sq edge len */ template <class Kernel, class Items> class CEdge { public: typedef typename Kernel::FT FT; typedef typename VMESH::PSC<Kernel,Items> P; typedef typename P::Halfedge_handle Halfedge_handle; private: FT m_sqlen; Halfedge_handle m_he; public: // life cycle CEdge(const Halfedge_handle& he) { m_sqlen = squared_len(he); m_he = he; } CEdge(const CEdge& edge) : m_sqlen(edge.sqlen()), m_he(edge.he()) { } ~CEdge() {} public: // squared length of an edge static FT squared_len(Halfedge_handle he) { return CGAL::squared_distance(he->vertex()->point(), he->opposite()->vertex()->point()); } public: // accessors FT& sqlen() { return m_sqlen; } const FT sqlen() const { return m_sqlen; } Halfedge_handle he() { return m_he; } const Halfedge_handle he() const { return m_he; } }; // functor for priority queue template<class Edge> struct less // read more priority { bool operator()(const Edge& e1, const Edge& e2) const { return e1.sqlen() < e2.sqlen(); } }; template <class kernel, class items> class CLongest_edge_bisection { // types typedef typename kernel::FT FT; typedef typename CEdge<kernel,items> Edge; typedef typename PSC<kernel,items> P; typedef typename P::Halfedge_handle Halfedge_handle; typedef typename P::Edge_iterator Edge_iterator; typedef typename std::priority_queue<typename Edge, std::vector<typename Edge>, less<typename Edge> > PQueue; // data PQueue m_queue; P* m_pMesh; public : // life cycle CLongest_edge_bisection(P* pMesh) { m_pMesh = pMesh; } ~CLongest_edge_bisection() {} public : void fill_queue(const FT& max_sqlen) { for(Edge_iterator he = m_pMesh->edges_begin(); he != m_pMesh->edges_end(); he++) if(Edge::squared_len(he) > max_sqlen) m_queue.push(Edge(he)); } // run unsigned int operator()(const FT& max_sqlen) { // fill queue fill_queue(max_sqlen); unsigned int nb_split = 0; while(!m_queue.empty()) { // get a copy of the candidate edge Edge edge = m_queue.top(); m_queue.pop(); Halfedge_handle he = edge.he(); FT sqlen = Edge::squared_len(he); if(sqlen > max_sqlen) { // update point Halfedge_handle hnew = m_pMesh->split_edge(he); hnew->vertex()->point() = CGAL::midpoint(he->vertex()->point(), he->opposite()->vertex()->point()); // hit has been split into two edges m_queue.push(Edge(hnew)); m_queue.push(Edge(he)); // split facet if possible if(!hnew->is_border()) { m_pMesh->split_facet(hnew,hnew->next()->next()); m_queue.push(Edge(hnew->next())); } // split facet if possible if(!hnew->opposite()->is_border()) { m_pMesh->split_facet(hnew->opposite()->next(), hnew->opposite()->next()->next()->next()); m_queue.push(Edge(hnew->opposite()->prev())); } nb_split++; } // end if(sqlen > max_sqlen) } // end while(!m_queue.empty()) return nb_split; } // end run }; #endif // _LONGEST_EDGE_BISECTION_ Bill Conan a écrit : > hello guys, > > i'm trying to split all the edges of a mesh into 2 sub-edges, the > pseudo code could be simple as this: > > for each edge e in the edge list > { > split edge e into e1 and e2; > } > > but i'm afraid if i simply do that, the code will loop forever, since > the newly generated edges e1 and e2 can be traveled also by the loop > and generate more edges, however i only need the original edges to be > splitted. > > i don't know where the new edges e1 and e2 are inserted into the edge > list of the CGAL polyhedron data structure. are they all inserted to > the end of the list or somewhere else or just replace the position of > e? > > and another question is > > for(edgeiter=edge.begin();edgeiter<edge.end();++edgeiter) > { > split edgeiter; > > // will edgeiter become null here? > } > > > thank you very much. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
hello Pierre,
thank you very much for your reply. but i don't want to make things complicated. i just need to split each edge into two. so here is my understanding: if i split an edge e into e1 and e2, then e1 will be at the same location in the edge list as the edge e is, and e2 will be added to the end of the list. so if i write the code as this enditer=edge.end(); for(edgeiter=edge.begin();edgeiter<enditer;++edgeiter) { split edgeiter; // will edgeiter become null here? } i'll be fine (the code will not loop forever). am i right? thank you very much. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
Hello Bill, what you might do is to copy the edges you want to split into a container and then just split them. The behaviour of an iteration over the edges as they are stored in the datastructure itself interlaced with operations modifying the datastructure depends too much on how they are stored. andreas Bill Conan wrote: > hello Pierre, > > thank you very much for your reply. but i don't want to make things > complicated. i just need to split each edge into two. > > so here is my understanding: if i split an edge e into e1 and e2, > > then e1 will be at the same location in the edge list as the edge e is, > > and e2 will be added to the end of the list. > > so if i write the code as this > > enditer=edge.end(); > for(edgeiter=edge.begin();edgeiter<enditer;++edgeiter) > { > split edgeiter; > > // will edgeiter become null here? > } > > i'll be fine (the code will not loop forever). am i right? > > thank you very much. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
hello Andreas,
thank you very much. I think that is an option, but is that efficient? I'm wondering how people do this kind of operation normally? for example, when applying a subdivision on a geometry object, should i make a cloned object and do all the modification on it and return the cloned one, or i just need to modify the original one. i know the first way is easier to implement and also safer, but it eats up more memory. i think those commercial software, say 3D max, always keeps the original geometry and do modification on a cloned object. thank you, On Mon, Jun 16, 2008 at 3:13 PM, Andreas Fabri <[hidden email]> wrote: > > Hello Bill, > > what you might do is to copy the edges you want to split > into a container and then just split them. > > The behaviour of an iteration over the edges as they are stored in the > datastructure itself interlaced with operations modifying the datastructure > depends too much on how they are stored. > > andreas > > > Bill Conan wrote: >> >> hello Pierre, >> >> thank you very much for your reply. but i don't want to make things >> complicated. i just need to split each edge into two. >> >> so here is my understanding: if i split an edge e into e1 and e2, >> >> then e1 will be at the same location in the edge list as the edge e is, >> >> and e2 will be added to the end of the list. >> >> so if i write the code as this >> >> enditer=edge.end(); >> for(edgeiter=edge.begin();edgeiter<enditer;++edgeiter) >> { >> split edgeiter; >> >> // will edgeiter become null here? >> } >> >> i'll be fine (the code will not loop forever). am i right? >> >> thank you very much. > > -- > You are currently subscribed to cgal-discuss. > To unsubscribe or access the archives, go to > https://lists-sop.inria.fr/wws/info/cgal-discuss > -- Dept. of Computer Science University of California, Davis Homepage:http://wwwcsif.cs.ucdavis.edu/~yans/ -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
On 6/16/08, Bill Conan <[hidden email]> wrote:
> I'm wondering how people do this kind of operation normally? > for example, when applying a subdivision on a geometry object, Hi Bill, K-3D meshes used to have a structure similar to the CGAL Halfedge structure. To split edges, we traveled along the edges using the next() method, making sure to store a handle to the old "next" edge before moving on. Pseudo code would be like this: For each facet Get first edge first_edge while edge != first_edge old_clockwise = edge->next() split edge edge = old_clockwise Dunno if this is OK in CGAL, though. Also, you might need to make sure the opposite edges remain in sync. Cheers, -- Bart -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
thanks Bart,
i did an experiment, the truth is that if i split an edge e, the newly generated sub edges will be at the old position of e. suppose the original edge list is e1->e2->e3->e4 now if i want to split the e2 to eA and eB, then the list will be like this e1->eA->eB->e3->e4 therefore, if i write the code as this: Edge_iterator iter=p.edges_begin(); Edge_iterator iterE=p.edges_end(); for(iter;iter!=iterE;++iter) { p.split_edge(iter); } it will loop forever, the correct code should be like this: Edge_iterator iter=p.edges_begin(); Edge_iterator iterE=p.edges_end(); for(iter;iter!=iterE;++iter) { p.split_edge(iter); ++iter; } cheers, On Tue, Jun 17, 2008 at 3:46 AM, Bart Janssens <[hidden email]> wrote: > On 6/16/08, Bill Conan <[hidden email]> wrote: >> I'm wondering how people do this kind of operation normally? >> for example, when applying a subdivision on a geometry object, > > Hi Bill, > > K-3D meshes used to have a structure similar to the CGAL Halfedge > structure. To split edges, we traveled along the edges using the > next() method, making sure to store a handle to the old "next" edge > before moving on. Pseudo code would be like this: > > For each facet > Get first edge first_edge > while edge != first_edge > old_clockwise = edge->next() > split edge > edge = old_clockwise > > Dunno if this is OK in CGAL, though. Also, you might need to make sure > the opposite edges remain in sync. > > Cheers, > > -- > Bart > -- > You are currently subscribed to cgal-discuss. > To unsubscribe or access the archives, go to > https://lists-sop.inria.fr/wws/info/cgal-discuss > You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss |
Free forum by Nabble | Edit this page |