CGAL users discussion list

[Fernando Cacciola <>]

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