CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

A smart thing to do would be to leave the simplices in the polyhedra
(modify halfedge_collapse) and only store all the relationships+the 
embeddings around the edges to be simplified.
Then upon an undo, you simply restore these relationships (you don't
care about what has been done) and that's it. You also need a function
to clean up the data structure from the pending simplices.

I join the version of the headers that will end up in 4.4


Sebastien.

On 02/28/2014 03:26 PM, Zohar wrote:
> Only in the last case v0 would remain instead of v1. But in the fourth case
> there's an edge that is left (I have my special needs to update some data on
> the edges). Even if the result of the first three cases is the same, the
> operations performed (join_facet, join_vertex, delete_facet) are different,
> and thus need to be undone differently.
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Multi-level-polyhedron-tp4656471p4658887.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.

// Copyright (c) 2006  GeometryFactory (France). All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
// Author(s)     : Fernando Cacciola <>
//
#ifndef CGAL_SURFACE_MESH_SIMPLIFICATION_COLLAPSE_TRIANGULATION_EDGE_POLYHEDRON_3_H
#define CGAL_SURFACE_MESH_SIMPLIFICATION_COLLAPSE_TRIANGULATION_EDGE_POLYHEDRON_3_H

#include <CGAL/Surface_mesh_simplification/Detail/Common.h>
#include <CGAL/Polyhedron_3.h>

#  define CGAL_HDS_PARAM_ template < class Traits, class Items, class Alloc> class HDS

namespace CGAL {

namespace Surface_mesh_simplification
{
/*
Function responsible for contracting an edge while respecting constrained edges

Notations used in the following function:
Top=TopFace
Btm=BottomFace

          t
        /   \
       /     \
      /  Top  \
     p -------- q
      \  Btm  /
       \     /
        \   /
          b

Prerequisites:
If Top exists, amongst p-t and t-q only one is constrained
If Btm exists, amongst p-b and q-b only one is constrained
p-q is not constrained
*/
template<class Gt, class I, CGAL_HDS_PARAM_, class A, class EdgeIsConstrainedMap>
typename boost::graph_traits< Polyhedron_3<Gt,I,HDS,A> >::vertex_descriptor
halfedge_collapse( typename boost::graph_traits< Polyhedron_3<Gt,I,HDS,A> >::edge_descriptor const& pq
                 , Polyhedron_3<Gt,I,HDS,A>& aSurface
                 , EdgeIsConstrainedMap Edge_is_constrained_map
                 )
{
  CGAL_assertion( !get(Edge_is_constrained_map,pq) );
  typedef Polyhedron_3<Gt,I,HDS,A> Surface ;

  typedef typename boost::graph_traits<Surface>::vertex_descriptor vertex_descriptor ;
  typedef typename boost::graph_traits<Surface>::edge_descriptor   edge_descriptor ;

  edge_descriptor qp = opposite_edge(pq,aSurface);
  edge_descriptor pt = opposite_edge(prev_edge(pq,aSurface),aSurface);
  edge_descriptor qb = opposite_edge(prev_edge(qp,aSurface),aSurface);
  edge_descriptor tq = pq->next()->opposite();
  edge_descriptor bp = qp->next()->opposite();

  bool lTopFaceExists         = !pq->is_border() ;
  bool lBottomFaceExists      = !qp->is_border() ;

  CGAL_precondition( !lTopFaceExists    || (lTopFaceExists    && ( pt->vertex()->vertex_degree() > 2 ) ) ) ;
  CGAL_precondition( !lBottomFaceExists || (lBottomFaceExists && ( qb->vertex()->vertex_degree() > 2 ) ) ) ;

  vertex_descriptor q = pq->vertex();
  vertex_descriptor p = pq->opposite()->vertex();

  CGAL_ECMS_TRACE(3, "Collapsing p-q E" << pq->id() << " (V" << p->id() << "->V" << q->id() << ")" ) ;

  //used to collect edges to remove from the surface
  edge_descriptor edges_to_erase[2];
  edge_descriptor* edges_to_erase_ptr=edges_to_erase;

  // If the top facet exists, we need to choose one out of the two edges which one disappears:
  //   p-t if it is not constrained and t-q otherwise
  if ( lTopFaceExists )
  {
    CGAL_precondition( !pt->opposite()->is_border() ) ; // p-q-t is a face of the mesh
    if ( !get(Edge_is_constrained_map,pt) )
    {
      CGAL_ECMS_TRACE(3, "Removing p-t E" << pt->id() << " (V" << p->id() << "->V" << pt->vertex()->id()) ;
      *edges_to_erase_ptr++=pt;
    }
    else
    {
      CGAL_ECMS_TRACE(3, "Removing t-q E" << pt->id() << " (V" << pt->vertex()->id() << "->V" << q->id() ) ;
      CGAL_assertion( !get(Edge_is_constrained_map,tq) );
      *edges_to_erase_ptr++=tq;
    }
  }

  // If the bottom facet exists, we need to choose one out of the two edges which one disappears:
  //   q-b if it is not constrained and b-p otherwise
  if ( lBottomFaceExists )
  {
    if ( !get(Edge_is_constrained_map,qb) )
    {
      CGAL_ECMS_TRACE(3, "Removing q-b E" << qb->id() << " (V" << q->id() << "->V" << qb->vertex()->id() ) ;
      *edges_to_erase_ptr++=qb;
    }
    else{
      CGAL_ECMS_TRACE(3, "Removing b-p E" << qb->id() << " (V" << qb->vertex()->id() << "->V" << p->id() ) ;
      CGAL_assertion( !get(Edge_is_constrained_map,bp) );
      *edges_to_erase_ptr++=bp;
    }
  }

  if (lTopFaceExists && lBottomFaceExists)
  {
    if ( edges_to_erase[0]->facet()==edges_to_erase[1]->facet()
         && !edges_to_erase[0]->is_border() )
    {
      // the vertex is of valence 3 and we simply need to remove the vertex
      // and its indicent edges
      bool lP_Erased=false;
      edge_descriptor edge =
        edges_to_erase[0]->next()==edges_to_erase[1]?
          edges_to_erase[0]:edges_to_erase[1];
      if (edge->vertex()==p)
        lP_Erased=true;
      aSurface.erase_center_vertex(edge);
      return lP_Erased? q : p;
    }
    else
    {
      if (!edges_to_erase[0]->is_border())
        aSurface.join_facet(edges_to_erase[0]);
      else
        aSurface.erase_facet(edges_to_erase[0]->opposite());
      if (!edges_to_erase[1]->is_border())
        aSurface.join_facet(edges_to_erase[1]);
      else
        aSurface.erase_facet(edges_to_erase[1]->opposite());
      aSurface.join_vertex(pq);
      return q;
    }
  }
  else
  {
      if (lTopFaceExists)
      {
        if (!edges_to_erase[0]->is_border()){
          aSurface.join_facet(edges_to_erase[0]);
          aSurface.join_vertex(pq);
          return q;
        }
        bool lQ_Erased=pq->next()->opposite()->is_border();
        aSurface.erase_facet(edges_to_erase[0]->opposite());
        return lQ_Erased?p:q;
      }

      CGAL_assertion(lBottomFaceExists);
      if (!edges_to_erase[0]->is_border()){
        aSurface.join_facet(edges_to_erase[0]);
        aSurface.join_vertex(qp);
        return p;
      }
      bool lP_Erased=qp->next()->opposite()->is_border();
      aSurface.erase_facet(edges_to_erase[0]->opposite());
      return lP_Erased?q:p;
  };
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename boost::graph_traits< Polyhedron_3<Gt,I,HDS,A> >::vertex_descriptor
halfedge_collapse( typename boost::graph_traits< Polyhedron_3<Gt,I,HDS,A> >::edge_descriptor const& pq
                 , Polyhedron_3<Gt,I,HDS,A>& aSurface
                 )
{
  return halfedge_collapse( pq,
                            aSurface,
                            No_constrained_edge_map<Polyhedron_3<Gt,I,HDS,A> >() );
}

} // namespace Surface_mesh_simplification

} //namespace CGAL

#undef CGAL_HDS_PARAM

#endif // CGAL_SURFACE_MESH_SIMPLIFICATION_COLLAPSE_TRIANGULATION_EDGE_POLYHEDRON_3_H
// EOF //

// Copyright (c) 2006  GeometryFactory (France). All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
// Author(s)     : Fernando Cacciola <>
//
#ifndef CGAL_SURFACE_MESH_SIMPLIFICATION_DETAIL_COMMON_H
#define CGAL_SURFACE_MESH_SIMPLIFICATION_DETAIL_COMMON_H 1

#include <functional>
#include <utility>
#include <vector>
#include <vector>
#include <set>

#include <boost/config.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/scoped_ptr.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/optional/optional.hpp>
#include <boost/none.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/format.hpp>
#include <boost/scoped_array.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <CGAL/Cartesian/MatrixC33.h>
#include <CGAL/Modifiable_priority_queue.h>
#include <CGAL/boost/graph/halfedge_graph_traits.h>

namespace CGAL {

namespace Surface_mesh_simplification 
{

using boost::num_edges ;
using boost::num_vertices ;
using boost::edges ;
using boost::out_edges ;
using boost::in_edges ;
using boost::source ;
using boost::target ;

using boost::shared_ptr ;
using boost::optional ;
using boost::none ;
using boost::put_get_helper ;
using boost::get ;
using boost::put ;
using boost::addressof ;

using namespace boost::tuples ;

template<class Handle>
inline bool handle_assigned( Handle h ) { Handle null ; return h != null ; }

template<class Iterator, class Handle>
bool handle_exists ( Iterator begin, Iterator end, Handle h )
{
 if ( handle_assigned(h) )
 {
   while ( begin != end )
     if ( begin++ == h )
       return true ;
 }
 return false ;
}

template <class ECM>
struct No_constrained_edge_map{
  typedef typename boost::graph_traits<ECM>::edge_descriptor key_type;
  typedef bool value_type;
  typedef value_type reference;
  typedef boost::readable_property_map_tag category;
  friend bool get(No_constrained_edge_map, key_type) {
    return false;
  }
};

} // namespace Surface_mesh_simplification

template<class N>
inline std::string n_to_string( N const& n )
{
  return boost::str( boost::format("%|5.19g|") % n ) ;   
}

template<class XYZ>
inline std::string xyz_to_string( XYZ const& xyz )
{
  return boost::str( boost::format("(%|5.19g|,%|5.19g|,%|5.19g|)") % xyz.x() % xyz.y() % xyz.z() ) ;   
}

template<class Matrix>
inline std::string matrix_to_string( Matrix const& m )
{
  return boost::str( boost::format("[%1%|%2%|%3%]") % xyz_to_string(m.r0()) % xyz_to_string(m.r1()) % xyz_to_string(m.r2()) ) ;
}

template<class T>
inline std::string optional_to_string( boost::optional<T> const& o )
{
  if ( o )
       return boost::str( boost::format("%1%") % *o ) ;   
  else return std::string("NONE");  
}


} //namespace CGAL

#if   defined(CGAL_SURFACE_SIMPLIFICATION_ENABLE_TRACE)    \
   || defined(CGAL_SURFACE_SIMPLIFICATION_ENABLE_LT_TRACE) 
#define CGAL_ECMS_ENABLE_TRACE
#endif

#ifdef CGAL_ECMS_ENABLE_TRACE

#  include<string>
#  include<iostream>
#  include<sstream>
namespace internal { namespace  { bool cgal_enable_ecms_trace = false ; } }
#  define CGAL_ECMS_TRACE_IMPL(m) \
     if ( ::internal::cgal_enable_ecms_trace ) { \
       std::ostringstream ss ; ss << m ; std::string s = ss.str(); \
       Surface_simplification_external_trace(s); \
     }
     
#  define CGAL_ECMS_DEBUG_CODE(code) code     

#else

#  define CGAL_ECMS_DEBUG_CODE(code)

#endif

#ifdef CGAL_SURFACE_SIMPLIFICATION_ENABLE_LT_TRACE
#  define CGAL_ECMS_LT_TRACE(l,m) if ( (l) <= CGAL_SURFACE_SIMPLIFICATION_ENABLE_LT_TRACE ) CGAL_ECMS_TRACE_IMPL(m)
#else
#  define CGAL_ECMS_LT_TRACE(l,m)
#endif

#ifdef CGAL_SURFACE_SIMPLIFICATION_ENABLE_TRACE
#  define CGAL_ECMS_TRACE_IF(c,l,m) if ( (c) && ( (l) <= CGAL_SURFACE_SIMPLIFICATION_ENABLE_TRACE) ) CGAL_ECMS_TRACE_IMPL(m)
#  define CGAL_ECMS_TRACE(l,m)      if ( (l) <= CGAL_SURFACE_SIMPLIFICATION_ENABLE_TRACE ) CGAL_ECMS_TRACE_IMPL(m)
#else
#  define CGAL_ECMS_TRACE_IF(c,l,m)
#  define CGAL_ECMS_TRACE(l,m)
#endif

#undef CGAL_ECMS_ENABLE_TRACE

#ifdef CGAL_TESTING_SURFACE_MESH_SIMPLIFICATION
#  define CGAL_SURF_SIMPL_TEST_assertion(EX)         CGAL_assertion(EX)
#  define CGAL_SURF_SIMPL_TEST_assertion_msg(EX,MSG) CGAL_assertion_msg(EX,MSG) 
#  define CGAL_SURF_SIMPL_TEST_assertion_code(CODE)  CGAL_assertion_code(CODE)
#else
#  define CGAL_SURF_SIMPL_TEST_assertion(EX) 
#  define CGAL_SURF_SIMPL_TEST_assertion_msg(EX,MSG) 
#  define CGAL_SURF_SIMPL_TEST_assertion_code(CODE) 
#endif


#endif // CGAL_SURFACE_MESH_SIMPLIFICATION_DETAIL_COMMON_H //
// EOF //