CGAL users discussion list

[Andreas Fabri <>]

Dear Qianqian,

Attached you find a modified version of your file.
I've put comments with AF:  where I changed something.

Concerning your other question, I am not aware of
mesh simplification that can guarantee that there
are no self intersections.

Note that in CGAL we have a package to check if
there are self intersections, so you could make
a copy of the mesh, run the simplification,
test if everything is ok, and only then replace
the mesh. This admittedly is far from elegant.

Best regards,

Andreas

On 03/12/2014 18:45, Qianqian Fang wrote:
> On 11/26/2014 03:11 AM, Andreas Fabri wrote:
> > Dear Qianqian,
> >
> > We cleaned up the mechanism to mark edges as non-removable.
> > Please have a look at the example in the manual:
> >
> > http://doc.cgal.org/latest/Surface_mesh_simplification/index.html#title14
>
> hi Andreas
>
> thanks for your reply. I did notice the new implementation when I read the
> updated documentation. However, I don't think this addresses what I
> hope to achieve, i.e. using both Midpoint and LT placement policies in a
> single unit.
>
> Can you, or one of your colleagues, point me to a sample code where
> the LT placement is used? I'd like to see how to combine this with
> the Midpoint code sample.
>
> Also, can any of you comment on the second question I had?
>
> > My second question: using the Midpoint placement method, a
> > simplified surface often presents self-intersecting elements. I am
> > wondering if the LT placement, or any other approaches that can
> > prevent the surface elements from intersecting after decimation?
>
> thanks
>
> Qianqian
>
> > Best regards,
> >
> > Andreas
> >
> > On 24/11/2014 23:09, Qianqian Fang wrote:
> > > Dear list:
> > >
> > > I have a slightly modified surface mesh simplification code, with
> > > the previous help from Fernando Cacciola, compiled for my meshing
> > > toolbox "iso2mesh". I just made some changes to this code to
> > > add the support for the default Lindstrom Turk placement policy
> > > in addition to the Midpoint placement, allowing them to be selected
> > > through the command options. However, my modified code no
> > > longer compiles.
> > >
> > > My code change can be found at
> > >
> > > https://sourceforge.net/p/iso2mesh/code/456
> > >
> > > and the full sample unit can be browsed here:
> > >
> > > https://sourceforge.net/p/iso2mesh/code/HEAD/tree/trunk/cgalsimp2/edge_collapse_enriched_polyhedron.cpp
> > >
> > >
> > > (the previous changes suggested by Fernando was to
> > > fix the edges on the boundary when a surface is open)
> > >
> > > the compilation errors are attached.
> > >
> > > Perhaps there is something simple that I have overlooked, can someone
> > > tell me how can I get this to work?
> > >
> > > My second question: using the Midpoint placement method, a
> > > simplified surface often presents self-intersecting elements. I am
> > > wondering if the LT placement, or any other approaches that can
> > > prevent the surface elements from intersecting after decimation?
> > >
> > > thanks
> > >
> > > Qianqian

--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
//-------------------------------------------------------------------------
//===================================================================
//=   CGAL Mesh Simplification Code Modified for iso2mesh toolbox   =
//===================================================================
//
//Modified by Qianqian Fang <fangq at nmr.mgh.harvard.edu>
//with help from Fernando Cacciola <fernando.cacciola at geometryfactory.com>
//
//Date: 2008/03
//
//-------------------------------------------------------------------------

#include <iostream>
#include <fstream>

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>

// Adaptor for Polyhedron_3
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>// AF: added
//#include <CGAL/Surface_mesh_simplification/HalfedgeGraph_Polyhedron_3.h> // 
AF: removed

// Simplification function
#include <CGAL/Surface_mesh_simplification/edge_collapse.h>

// Extended polyhedron items which include an id() field
#include <CGAL/Polyhedron_items_with_id_3.h>

// Stop-condition policy
#include 
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Count_ratio_stop_predicate.h>

// Default cost and placement policies
#include 
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/LindstromTurk_placement.h>
 

// Non-default cost and placement policies
#include 
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Midpoint_and_length.h>
 

typedef CGAL::Simple_cartesian<double> Kernel;

typedef Kernel::Point_3 Point ;

//
// Setup an enriched polyhedron type which stores an id() field in the items
//
typedef CGAL::Polyhedron_3<Kernel,CGAL::Polyhedron_items_with_id_3> Surface; 

typedef Surface::Halfedge_handle Halfedge_handle ;

namespace SMS = CGAL::Surface_mesh_simplification ;

typedef SMS::Edge_profile<Surface> Profile ;


// The following is a Visitor that keeps track of the simplification process.
// In this example the progress is printed real-time and a few statistics are
// recorded (and printed in the end).
//
struct Visitor
{
  Visitor() 
    : collected(0)
    , processed(0)
    , collapsed(0)
    , non_collapsable(0)
    , cost_uncomputable(0) 
    , placement_uncomputable(0) 
  {} 

  // Called on algorithm entry  
  void OnStarted( Surface& ) {} 
  
  // Called on algorithm exit  
  void OnFinished ( Surface& ) { std::cerr << "\n" << std::flush ; } 
  
  // Called when the stop condition returned true
  void OnStopConditionReached( Profile const& ) {} 
  
  // Called during the collecting phase for each edge collected.
  void OnCollected( Profile const&, boost::optional<double> const& )
  {
    ++ collected ;
//    std::cerr << "\rEdges collected: " << collected << std::flush ;
  }                
  
  // Called during the processing phase for each edge selected.
  // If cost is absent the edge won't be collapsed.
  void OnSelected(Profile const&          
                 ,boost::optional<double> cost
                 ,std::size_t             initial
                 ,std::size_t             current
                 )
  {
    ++ processed ;
    if ( !cost )
      ++ cost_uncomputable ;
 /*     
    if ( current == initial )
      std::cerr << "\n" << std::flush ;
    std::cerr << "\r" << current << std::flush ;
 */
  }                
  
  // Called during the processing phase for each edge being collapsed.
  // If placement is absent the edge is left uncollapsed.
  void OnCollapsing(Profile const&          
                   ,boost::optional<Point>  placement
                   )
  {
    if ( placement )
         ++ collapsed;
    else ++ placement_uncomputable ;
  }                
  
  // Called for each edge which failed the so called link-condition,
  // that is, which cannot be collapsed because doing so would
  // turn the surface into a non-manifold.
  void OnNonCollapsable( Profile const& )
  {
    ++ non_collapsable;
  }      

  // AF: added 
  void OnCollapsed(Profile const&, Surface::Vertex_handle)
  {}
  
  std::size_t  collected
             , processed
             , collapsed
             , non_collapsable
             , cost_uncomputable  
             , placement_uncomputable ; 
} ;

template<class GetCost_>
struct Cost_with_fixed_edges : GetCost_
{
 typedef GetCost_ GetCost ;

  // typedef typename GetCost::Profile     Profile ; // AF Profile no longer 
nested type
  //typedef typename GetCost::Point       Point ; // AF
  //typedef typename GetCost::result_type result_type ; // AF

  template <typename Profile, typename T> // AF: make it a template 
  boost::optional<typename Profile::FT>  
operator()( 
Profile const& aProfile, 
T const& aPlacement ) const // replace result_type
 {
    if ( aProfile.border_edges().size() > 0 )
          return boost::none ;
    else
         return this->GetCost::operator()(aProfile, aPlacement);
 }
} ;

typedef Cost_with_fixed_edges< SMS::Edge_length_cost<Surface> > My_cost ; 
typedef Cost_with_fixed_edges< SMS::LindstromTurk_cost<Surface> > LT_cost ; 


int main( int argc, char** argv ) 
{
  Surface surface; 
  float maxface=0.1;
  int defaultpolicy=0;

  std::ifstream is(argv[1]) ; is >> surface ;
  if(argc>2) maxface=atof(argv[2]);
  if(maxface<0){
      defaultpolicy=1;
      maxface=-maxface;
  }

  printf("max face ratio=%f\n",maxface);
   
   
  // The items in this polyhedron have an "id()" field 
  // which the default index maps used in the algorithm
  // need to get the index of a vertex/edge.
  // However, the Polyhedron_3 class doesn't assign any value to
  // this id(), so we must do it here:
  int index = 0 ;
  
  for( Surface::Halfedge_iterator eb = surface.halfedges_begin()
     , ee = surface.halfedges_end()
     ; eb != ee
     ; ++ eb
     ) 
    eb->id() = index++;

  printf("edge index number %d\n",index);


  index = 0 ;
  for( Surface::Vertex_iterator vb = surface.vertices_begin()
     , ve = surface.vertices_end()
     ; vb != ve
     ; ++ vb
     ) 
    vb->id() = index++;
    
  // In this example, the simplification stops when the number of undirected 
edges
  // drops below 10% of the initial count
  SMS::Count_ratio_stop_predicate<Surface> stop(maxface);
     
  Visitor vis ;
  
  // The index maps are not explicitelty passed as in the previous
  // example because the surface items have a proper id() field.
  // On the other hand, we pass here explicit cost and placement
  // function which differ from the default policies, ommited in
  // the previous example.
  
  printf("mesh simplificaton in progress ...\n");

  int r;
  if(defaultpolicy)
      r = SMS::edge_collapse
           (surface
           ,stop
            ,CGAL::vertex_index_map(get(CGAL::vertex_external_index,surface)) 
// AF was boost::get
                 .edge_index_map  (get(CGAL::edge_external_index ,surface))
                 .get_cost        (LT_cost())
                 .get_placement   (SMS::LindstromTurk_placement<Surface>())
            .visitor(vis)  // AF: not a pointer
           );
  else
      r = SMS::edge_collapse
           (surface
           ,stop
           ,CGAL::vertex_index_map(get(CGAL::vertex_external_index,surface))
                 .edge_index_map  (get(CGAL::edge_external_index ,surface))
                 .get_cost        (My_cost())
                 .get_placement   (SMS::Midpoint_placement<Surface>())
                 .visitor(vis)
           );  
  
  std::cout << "\nEdges collected: " << vis.collected
            << "\nEdges proccessed: " << vis.processed
            << "\nEdges collapsed: " << vis.collapsed
            << std::endl
            << "\nEdges not collapsed due to topological constrians: " 
            << vis.non_collapsable
            << "\nEdge not collapsed due to cost computation constrians: " 
            << vis.cost_uncomputable 
            << "\nEdge not collapsed due to placement computation constrians: 
" 
            << vis.placement_uncomputable 
            << std::endl ; 
            
  std::cout << "\nFinished...\n" << r << " edges removed.\n" 
            << (surface.size_of_halfedges()/2) << " final edges.\n" ;
        
  std::ofstream os( argc > 3 ? argv[3] : "out.off" ) ; os << surface ;
  
  return 0 ;      
}



// EOF //