CGAL users discussion list

[Rob Patro <>]

Fernando,


  Thank you so much for your detailed response!  I'd come to a similar
solution, but let me explain to you my problem.  The set of handles
which your General_case_step class maintains can be invalidated after
the edge_collapse.  For example, referring to the same figure in the
manual.  In order to split the vertex, v1 back into v1 and v0, we need
to call split_vertex( vy0_v1, vx0_v1 ).  However, the problem is that
the edge collapse (not General_case_step::do, but the edge collapse
called directly after Visitor::OnCollapsing) will alter these edges as
they are obtained prior to the collapse.  Thus, one has no guarantee
where these things will point (to a removed vertex that's been
destructed?).  That was my primary concern when I asked about the
validity of the information collected in the EdgeProfile -- that after
collapse the halfedges may point to different (and possibly invalid)
structures than those to which they pointed prior to the collapse.
Here, since the initial collapse won't be done with
General_case_step::do, but with  halfedge_collapse, you won't have
control over the initial calls to join_facet and join vertex.  Thus, you
won't have access to the information they provide on their return, only
to the surface *prior* to the actual collapse.  Do you have any
suggestions on how to overcome these difficulties?  Thank you again for
your time and all your help!

Sincerely,
Rob


Fernando Cacciola wrote:
> Hi Rob,
> 
> 
> Ok, here's a sketch of how the PM could be implemented based on the edge
> profile and placement passed to the visitor.
> 
> The following (pseudo) code describes the (forward) halfedge collaspe
> algorithm, as implemented in
> 
>  haldedge_collapse_Polyhedron_3.h
> 
> but seen from the information visible in the visitor from the edge profile:
> 
> While you follow this look at the collapse figures in the manual:
> 
> 
> http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Surface_mesh_simplification_ref/Concept_EdgeCollapsableMesh.html#Cross_link_anchor_1335
> 
> 
> 
> 
> v0_erased = false ;
> v1_erased = false ;
> 
> if ( ! profile.is_v0_v1_a_border() )
> {
>   if ( ! profile.vL_v0()->opposite()->is_border() )
>   {
>     surface.join_facet( profile.vL_v0()->opposite() ) ;
>   }
>   else
>   {
>     surface.erase_facet( profile.vL_v0() ) ;
> 
>     v0_erased = profile.is_v1_v0_a_border() ;
>   }
> }
> 
> if ( ! profile.is_v1_v0_a_border() )
> {
>   if ( ! profile.vL_v0()->opposite()->is_border() )
>   {
>     surface.join_facet( profile.vR_v1() ) ;
>   }
>   else
>   {
>     surface.erase_facet( profile.vR_v1()->opposite() ) ;
> 
>     v1_erased = profile.is_v0_v1_a_border() ;
>   }
> }
> 
> if ( ! v0_erased && ! v1_erased )
> {
>   surface.join_vertex( v0_v1() );
>   v0_erased = true ;
> }
> 
> vertex_kept = v0_erased = profile.v1() : profile.v0() ;
> 
> if ( placement_given )
>   vertex_kept->point() = placement ;
> 
> 
> 
> 
> Based on the above, I would implement the PM by recording on each
> visitor call not the edge profile but some record of the actual sequence
> of euler operations that took place.
> 
> 
> Something like the following (*OFF THE TOP OF MY HEAD*):
> 
> 
> void OnCollapsing(Profile const& profile, OPoint const& placement )
> {
> 
>   v0_erased   = false ;
>   v1_erased   = false ;
>   v01_joined  = false ;
>   f01L_joined = false ;
>   f01L_erased = false ;
>   f10R_joined = false ;
>   f10R_erased = false ;
> 
>   if ( ! profile.is_v0_v1_a_border() )
>   {
>     if ( profile.vL_v0()->opposite()->is_border() )
>     {
>       f01L_joined = true ;
>     }
>     else
>     {
>       f01L_erased = false ;
> 
>       v0_erased = profile.is_v1_v0_a_border() ;
>     }
>   }
> 
>   if ( ! profile.is_v1_v0_a_border() )
>   {
>     if ( profile.vL_v0()->opposite()->is_border() )
>     {
>       f10R_joined = false ;
>     }
>     else
>     {
>       f10R_erased = false ;
> 
>       v1_erased = profile.is_v0_v1_a_border() ;
>     }
>   }
> 
>   if ( ! v0_erased &&  ! v1_erased )
>   {
>     v01_joined = true ;
>     v0_erased  = true ;
>   }
> 
> 
>   // General Case:
>   if ( f01L_joined && f10R_joined && v01_joined )
> 
>     PM.add_step( new General_case_step(profile.surface()
>                                       ,profile.vL_v0()->opposite()
>                                       ,profile.v1_vR()->opposite()
>                                       ,profile.v0()
>                                       ,profile.v1()
>                                       ,placement
>                                       )
>                ) ;
>    else
> 
>     .. similar for all other possible cases ..
> 
> }
> 
> whith
> 
> class General_case_step
> {
>   General_case_step( Surface s
>                    , Halfedge_handle v0_vL
>                    , Halfedge_handle v1_vR
>                    , Vertex_handle   v0
>                    , Vertex_handle   v1
>                    , optional<Point> v1_new_point
>                    )
>    ...
> 
>   virtual void do()
>   {
>     // some information needed for undo is initialized here
> 
>     vx0_v0 = s.join_facet(v0_vL);
>     vy0_v1 = s.join_facet(v1_vR);
> 
>     v0_point = v0->point();
>     v1_point = v1->point();
> 
>     s.join_vertex(v0,v1);
> 
>     if ( v1_new_point )
>       v1->point() = v1_new_point ;
> 
>     // v0_vL, v1_vR and v0 invalid at this point
>   }
> 
>   virtual void undo()
>   {
>     // undo resets the invalidated handles so that do()
>     // can be called again
> 
>     v0 = s.split_vertex(v1);
> 
>     v0->point() = v0_point ;
>     v1->point() = v1_point ;
> 
>     v1_vR = s.split_facet(v1_vL,vx0_v0);
> 
>     v0_vL = s.split_facet(v0_vR,vy0_v1);
> 
>   }
> } ;
> 
> then, executing the PM would amount to call do() or undo() over the
> collection of polymorhpic steps collected with the visitor.
> 
> 
> That is of course totally untested and off the top of my head.
> 
> HTH
> 
> Fernando Cacciola
> 
> www.geometryfactory.com
> 
> 
> 
> 
> 
> 
>