Trouble with mesh simplification

Moderator
Posts: 3,570
Joined: 2003.06
Post: #16
TomorrowPlusX Wrote:And let me say, looking over CGAL, I finally understand why so many people hate C++. Holy Moses!

LOL ... got a good chuckle out of that post! (except for the emergency of course -- hope all is well there...)
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #17
AnotherJake Wrote:LOL ... got a good chuckle out of that post! (except for the emergency of course -- hope all is well there...)

Thank you; regarding the emergency, all is not well. My GF and I are simply waiting for the inevitable now.

So in the meantime I keep myself occupied with work, and with this CGAL stuff, which I've finally managed to make work. And the good news is that CGAL's mesh simplification algorithm is really excellent.

[Image: geometrysimplification-2008-11-19-01.png]

No holes, no weird degenerate triangles, and best of all, the remaining triangles are really well distributed. So while I groused about CGAL's C++, it turns out to be worth it.

Also, I'm posting my code below in case anybody here ever searches on CGAL and can't figure out how the holy hell they're supposed to populate a Polyhedron_3 or how to extract triangles from one later.

Fortunately, with a dogpile of typedefs, the code becomes readable.
Code:
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Polyhedron_incremental_builder_3.h>

// Adaptor for Polyhedron_3
#include <CGAL/Surface_mesh_simplification/HalfedgeGraph_Polyhedron_3.h>

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

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

typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Polyhedron_3<Kernel> Surface;
typedef Surface::HalfedgeDS HalfedgeDS;
typedef Kernel::Point_3 Point;

namespace SMS = CGAL::Surface_mesh_simplification ;

using namespace sgf;
namespace sre {
namespace mesh {

namespace {

    const bool NOISY = true;

    template < class HDS>
    class geometry_to_surface_op :  public CGAL::Modifier_base<HDS>
    {
        protected:
        
            GeometryRef _geometry;
    
        public:

            typedef HDS Halfedge_data_structure;

        public:
        
            geometry_to_surface_op( const GeometryRef &g ): _geometry( g )
            {}

            void operator()( HDS& hds)
            {
                vec3 *vertices = _geometry->vertices();
                Triangle *triangles = _geometry->triangles();
                int numVertices = _geometry->numVertices(),
                    numTriangles = _geometry->numTriangles(),
                    numEdges = _geometry->numEdges();

                CGAL::Polyhedron_incremental_builder_3<HalfedgeDS> builder( hds, true );
                builder.begin_surface( numVertices,
                                       numTriangles,
                                       numEdges * 2 );

                for ( int i = 0; i < numVertices; i++ )
                {
                    vec3 v = vertices[i];
                    builder.add_vertex( Point( v.x, v.y, v.z ));
                }

                for ( int i = 0; i < numTriangles; i++ )
                {
                    builder.begin_facet();
                    
                    for ( int j = 0; j < 3; j++ )
                    {
                        builder.add_vertex_to_facet( triangles[i].indices[j] );
                    }
                    
                    builder.end_facet();
                }

                if ( builder.check_unconnected_vertices() )
                {
                    builder.remove_unconnected_vertices();
                }
                
                builder.end_surface();          
            }

    };


    void geometry_to_surface( const GeometryRef &g, Surface &s )
    {
        typedef Surface::HalfedgeDS HalfedgeDS;
        typedef geometry_to_surface_op<HalfedgeDS> GTSO;

        GTSO gen( g );
        s.delegate(gen);
    }
    
    GeometryRef surface_to_geometry( Surface &s, Geometry::StorageMode storageMode, int vertexSnapPrecision )
    {
        GeometryRef g( new Geometry );
        g->generatorStart( storageMode, vertexSnapPrecision );
        
        int tris = 0;
        for ( Surface::Facet_iterator fit( s.facets_begin() ), fend( s.facets_end() ); fit != fend; ++fit )
        {
            if ( fit->is_triangle() )
            {
                vec3 verts[3];
                int tick = 0;          

                Surface::Halfedge_around_facet_circulator hit( fit->facet_begin() ), hend( hit );
                do
                {
                    Point p = hit->vertex()->point();
                                        
                    if ( tick < 3 )
                    {
                        verts[tick++] = vec3( p.x(), p.y(), p.z() );
                    }
                    else
                    {
                        lerr << "We've got facets with more than 3 vertices even though the facet reported to be trianglular..." << std::endl;
                    }
                
                } while( ++hit != hend );
                
                g->triangle( verts[0], verts[1], verts[2] );
            }
            else
            {
                lerr << "Skipping non-trianglular facet" << std::endl;
            }
                    
            tris++;
        }
                
        g->generatorFinished();
        return g;
    }
    
    float savings( int original, int compacted )
    {
        return 100.0f * ( 1.0f - float( compacted ) / float( original ) );
    }

}

GeometryRef
compact_cgal( const GeometryRef &geometry, float targetCompression, int vertexSnapPrecision )
{
    Surface surface;
    geometry_to_surface( geometry, surface );
    
    SMS::Count_ratio_stop_predicate<Surface> stop(clamp( targetCompression, 0.0f, 1.0f ));

    SMS::edge_collapse( surface,
                        stop,
                        CGAL::vertex_index_map( boost::get(CGAL::vertex_external_index,surface))
                               .edge_index_map( boost::get(CGAL::edge_external_index,surface  )));
                                      

    GeometryRef compacted = surface_to_geometry( surface, geometry->storageMode(), vertexSnapPrecision );

    if ( NOISY )
    {
        std::cout << "Original geometry has " << geometry->numVertices() << " vertices and " << geometry->numTriangles() << " triangles" << std::endl
            << "Compacted geometry has: " << compacted->numVertices() << " vertices and " << compacted->numTriangles() << " triangles" << std::endl
            << "\tvertex savings: " << str( savings( geometry->numVertices(), compacted->numVertices() ), 1 ) << "%"
            << " triangle savings: " << str( savings( geometry->numTriangles(), compacted->numTriangles() ), 1 ) << "%" << std::endl;      
    }

    return compacted;
}
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #18
Wow, that does look really good. It looks much better than what Maya outputs. Mesh simplification is notoriously ugly.

And thanks for that CGAL simplification too! I'm trying to grasp the irony of a code simplification for a mesh simplification. Sneaky
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #19
Be careful of the CGAL license.
Quote this message in a reply
Member
Posts: 268
Joined: 2005.04
Post: #20
That looks a lot better than the first screenshot, even if you don't count the fixing of the holes. The first screenshot looked like it had mixed in some 4 and 5 sided polygons as well as a few concave polygons. Nothing but evenly spaced triangles in the second. Nifty.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #21
Bachus Wrote:That looks a lot better than the first screenshot, even if you don't count the fixing of the holes. The first screenshot looked like it had mixed in some 4 and 5 sided polygons as well as a few concave polygons. Nothing but evenly spaced triangles in the second. Nifty.

Well, to apply blame where it's due, the four & five sided faces were actually triangles with missing edges for the wireframe render. I'd used a bad hashing algorithm to uniquely identify edges...

But those first two approaches still were pretty poor. CGAL's fantastic.

Also, OSC: regarding the license, CGAL's licence seemed to be pretty liberal so long as the work is noncommercial & you credit them. Since this isn't anything I'm ever going to sell, but rather just a plaform for self-education, I think I'm in the clear.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Creating Triangular mesh from vertex mahmoodnh 1 2,769 Oct 31, 2005 02:54 AM
Last Post: aarku