CGAL users discussion list

[crobar <>]

Sebastien Loriot (GeometryFactory) wrote
> You can try using the Surface mesh simplification package and remove 
> short edges:
> 
> http://doc.cgal.org/latest/Surface_mesh_simplification/index.html
> 
> Sebastien.


I've had a go using this, but I'm not getting the results I'm expecting, or
rather I'm failing to prune the short edges. Here is what I tried (largely
based on the example shown in
http://doc.cgal.org/latest/Surface_mesh_simplification/Surface_mesh_simplification_2edge_collapse_enriched_polyhedron_8cpp-example.html
):


#include <CGAL/Polyhedron_items_with_id_3.h>
#include<CGAL/Nef_polyhedron_3.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include<CGAL/Polyhedron_incremental_builder_3.h>
#include<CGAL/Polyhedron_3.h>
#include<CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Iterator_project.h>
#include <CGAL/function_objects.h>

// Adaptor for Polyhedron_3
#include <CGAL/Surface_mesh_simplification/HalfedgeGraph_Polyhedron_3.h>
// Simplification function
#include <CGAL/Surface_mesh_simplification/edge_collapse.h>
// Visitor base
#include <CGAL/Surface_mesh_simplification/Edge_collapse_visitor_base.h>
// Stop-condition policy
#include
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Count_ratio_stop_predicate.h>
// Non-default cost and placement policies
#include <CGAL/Surface_mesh_simplification/Detail/Common.h>
#include
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Midpoint_and_length.h>
//#include
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/LindstromTurk_placement.h>
#include
<CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Edge_profile.h>


typedef CGAL::Exact_predicates_exact_constructions_kernel     Kernel;
typedef CGAL::Polyhedron_3<Kernel>         Polyhedron;
typedef Polyhedron::HalfedgeDS             HalfedgeDS;
typedef CGAL::Nef_polyhedron_3<Kernel>     Nef_polyhedron;

// the following is used for checking for degenerate meshes
typedef Kernel::Point_3 Point ;
typedef CGAL::Polyhedron_3<Kernel,CGAL::Polyhedron_items_with_id_3>
Polyhedron_id;
typedef Polyhedron_id::Halfedge_handle Halfedge_handle ;
typedef Polyhedron_id::Vertex_handle Vertex_handle ;
typedef CGAL::Surface_mesh_simplification::Edge_profile<Polyhedron_id>
Profile ;
typedef  boost::graph_traits<Polyhedron_id>::edges_size_type size_type ;

//*******************************************************************************************************************
// -= stopping condition predicate =-
//
// Determines whether the simplification has finished.
// The arguments are
(current_cost,vertex,vertex,is_edge,initial_pair_count,current_pair_count,surface)
and the result is bool
//
//*******************************************************************************************************************
//
// Stops when the cost is below some tolerance
//
template<class ECM_>
        class length_stop_predicate
{
        public:
            typedef ECM_ ECM ;
            typedef CGAL::Surface_mesh_simplification::Edge_profile<ECM>
Profile ;
            typedef typename boost::graph_traits<ECM>::edge_descriptor
edge_descriptor ;
            typedef typename boost::graph_traits<ECM>::edges_size_type
size_type ;
            typedef typename CGAL::halfedge_graph_traits<ECM>::Point Point ;
            typedef typename CGAL::Kernel_traits<Point>::Kernel Kernel ;
            typedef typename Kernel::FT FT ;
        public :
            length_stop_predicate( double tolerance ) : _tol(tolerance) {}
            bool operator()( FT const& aCurrentCost // aCurrentCost
                    , Profile const& //aEdgeProfile
                    , size_type //aInitialCount
                    , size_type //aCurrentCount
                    ) const
            {
                std::cout << "sqrt aCurrentCost Is " <<
sqrt(CGAL::to_double(aCurrentCost)) << " _tol is " << _tol << std::endl;
                return ( sqrt(CGAL::to_double(aCurrentCost)) > _tol );
            }
        private:
            double _tol;
};

 // 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 Stats
 {
     Stats()
     : collected(0)
     , processed(0)
     , collapsed(0)
     , non_collapsable(0)
     , cost_uncomputable(0)
     , placement_uncomputable(0)
     {}
     std::size_t collected ;
     std::size_t processed ;
     std::size_t collapsed ;
     std::size_t non_collapsable ;
     std::size_t cost_uncomputable ;
     std::size_t placement_uncomputable ;
 } ;

 struct My_visitor :
CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base<Polyhedron_id>
 {
     My_visitor( Stats* s) : stats(s){}
     // Called during the collecting phase for each edge collected.
     void OnCollected( Profile const&, boost::optional<Kernel::FT> const& )
     {
         ++ stats->collected ;
         std::cerr << "Edges collected: " << stats->collected << std::endl
<< 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<Kernel::FT> cost
             ,std::size_t initial
             ,std::size_t current
             )
     {
         ++ stats->processed ;
         if ( !cost )
             ++ stats->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 )
             ++ stats->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 mesh into a non-manifold.
     void OnNonCollapsable( Profile const& )
     {
         ++ stats->non_collapsable;
     }

     // Called AFTER each edge has been collapsed
     void OnCollapsed( Profile const&, Vertex_handle )
     {
         ++ stats->collapsed;
     }
     Stats* stats ;
 } ;


Then, where I convert from CGAL to my own polyhedron construct, I first do
the mesh simplification like so:


polyhedron cgal_to_polyhedron( const Nef_polyhedron &NP ){
    Polyhedron_id P;
    polyhedron ret;

    if( NP.is_simple() )
    {
        NP.convert_to_polyhedron(P);

        // ensure there are no degenerate (too small) edges

        // 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( Polyhedron_id::Halfedge_iterator eb = P.halfedges_begin()
            , ee = P.halfedges_end()
            ; eb != ee
            ; ++ eb
           )
        {
            eb->id() = index++;
        }

        index = 0 ;
        for( Polyhedron_id::Vertex_iterator vb = P.vertices_begin()
            , ve = P.vertices_end()
            ; vb != ve
            ; ++ vb
           )
        {
            vb->id() = index++;
        }

        length_stop_predicate<Polyhedron_id> stop (0.001);
       
//CGAL::Surface_mesh_simplification::Count_ratio_stop_predicate<Polyhedron_id>
stop(0.99);

        Stats stats ;

        My_visitor vis(&stats) ;

        // The index maps are not explicitetly passed as in the previous
        // example because the surface mesh 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.
        int r = CGAL::Surface_mesh_simplification::edge_collapse (
                                    P
                                    ,stop
                                    ,CGAL::get_cost
(CGAL::Surface_mesh_simplification::Edge_length_cost <Polyhedron_id>())
                                   
.get_placement(CGAL::Surface_mesh_simplification::LindstromTurk_placement<Polyhedron_id>())
                                    .visitor (vis)
                                                                 );

        std::cout << "\nEdges collected: " << stats.collected
                  << "\nEdges processed: " << stats.processed
                  << "\nEdges collapsed: " << stats.collapsed
                  << std::endl
                  << "\nEdges not collapsed due to topological constriants:
" << stats.non_collapsable
                  << "\nEdge not collapsed due to cost computation
constriants: " << stats.cost_uncomputable
                  << "\nEdge not collapsed due to placement computation
constriants: " << stats.placement_uncomputable
                  << std::endl ;

        std::cout << "\nFinished...\n" << r << " edges removed.\n"
                  << (P.size_of_halfedges()/2) << " final edges.\n" ;


        std::vector<double> coords;
        std::vector<int> tris;
        int next_id = 0;
        std::map< Polyhedron_id::Vertex*, int > vid;
        for( Polyhedron_id::Vertex_iterator iter = P.vertices_begin(); iter
!= P.vertices_end(); iter++ )
        {
            coords.push_back( CGAL::to_double( (*iter).point().x() ) );
            coords.push_back( CGAL::to_double( (*iter).point().y() ) );
            coords.push_back( CGAL::to_double( (*iter).point().z() ) );
            vid[ &(*iter) ] = next_id++;
        }

        for( Polyhedron_id::Facet_iterator iter = P.facets_begin(); iter !=
P.facets_end(); iter++ )
        {
            Polyhedron_id::Halfedge_around_facet_circulator j =
iter->facet_begin();
            tris.push_back( CGAL::circulator_size(j) );
            do
            {
                tris.push_back( std::distance(P.vertices_begin(),
j->vertex()) );
            } while ( ++j != iter->facet_begin());
        }

        ret.initialize_load_from_mesh( coords, tris );
    }
    else
    {
        std::cout << "resulting polyhedron is not simple!" << std::endl;
    }
    return ret;
}




This time I triangulated my polygons before passing them into CGAL. Now at
the point where the problem shape is converted I get the following output:


252sqrt aCurrentCost Is 5.10207e-18 _tol is 0.001
252sqrt aCurrentCost Is 8.29476e-18 _tol is 0.001
252sqrt aCurrentCost Is 9.05531e-18 _tol is 0.001
252sqrt aCurrentCost Is 1.0065e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.11633e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.26797e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.36607e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.39187e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.43805e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.47533e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.49587e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.54581e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.59169e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.81504e-17 _tol is 0.001
252sqrt aCurrentCost Is 1.90392e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.21188e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.28058e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.57659e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.59503e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.8387e-17 _tol is 0.001
252sqrt aCurrentCost Is 2.8972e-17 _tol is 0.001
252sqrt aCurrentCost Is 3.00493e-17 _tol is 0.001
252sqrt aCurrentCost Is 3.08919e-17 _tol is 0.001
252sqrt aCurrentCost Is 3.08919e-17 _tol is 0.001
252sqrt aCurrentCost Is 3.16258e-17 _tol is 0.001
252sqrt aCurrentCost Is 3.36404e-17 _tol is 0.001
252sqrt aCurrentCost Is 0.0257483 _tol is 0.001

Edges collected: 252
Edges processed: 27
Edges collapsed: 0

Edges not collapsed due to topological constriants: 5
Edge not collapsed due to cost computation constriants: 0
Edge not collapsed due to placement computation constriants: 0

Finished...
0 edges removed.
252 final edges.


Could you possibly give me some tips here? Why can't CGAL collapse the
edges, and what strategy should I take (or what am I doing
wrong/misunderstanding).

For info, below is the problem polyhedron again with the offending point
marked.

<http://cgal-discuss.949826.n4.nabble.com/file/n4659781/cgalprob.png> 






--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/CGAL-difference-on-Nef-polyhedron-produces-shape-with-duplicate-vertices-tp4659760p4659781.html
Sent from the cgal-discuss mailing list archive at Nabble.com.