question on splitting edges

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

question on splitting edges

Shi Yan
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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

Pierre Alliez
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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

Shi Yan
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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

andreas.fabri

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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

Shi Yan
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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

bART Janssens-2
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
Reply | Threaded
Open this post in threaded view
|

Re: question on splitting edges

Shi Yan
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