include/mesht.hh

Go to the documentation of this file.

#ifndef A48_MESHT_HH
#define A48_MESHT_HH

//== INCLUDES =================================================================

#include <set>
#include <map>
#include <vector>

#include <vertext.hh>
#include <halfedget.hh>
#include <facet.hh>

//== NAMESPACES ===============================================================

namespace a48 {

//== CLASS DEFINITION =========================================================

class DefaultTraits {
public:
    typedef VertexT< DefaultTraits > vertex_type; 
    typedef HalfedgeT< DefaultTraits > halfedge_type; 
    typedef FaceT< DefaultTraits > face_type; 
};
//== CLASS DEFINITION =========================================================

template< class Traits = DefaultTraits >
class BaseItemsPolicy {

    typedef typename Traits::vertex_type vertex_type; 
    typedef typename Traits::halfedge_type halfedge_type; 
    typedef typename Traits::face_type face_type; 

public:

    virtual void set_vertex_attributes( vertex_type *v1, const vertex_type *v0 ) = 0;

    virtual void set_vertex_attributes( const unsigned int& i, vertex_type *v ) = 0;

    virtual void set_halfedge_attributes( halfedge_type *h1, const halfedge_type *h0 ) = 0;

    virtual void set_halfedge_attributes( halfedge_type *h, halfedge_type *o ) = 0;

    virtual void set_halfedge_attributes( const unsigned int& i, const unsigned int& j, const unsigned int& hi, halfedge_type *h ) = 0;

    virtual void set_face_attributes( face_type *f1, const face_type *f0 ) = 0;

    virtual void set_face_attributes( const unsigned int& i, face_type *f ) = 0;

};
//== CLASS DEFINITION =========================================================

template< class Traits = DefaultTraits >
class MeshT {

public:

    typedef BaseItemsPolicy< Traits > items_policy; 

    typedef typename Traits::vertex_type vertex_type; 
    typedef typename Traits::halfedge_type halfedge_type; 
    typedef typename Traits::face_type face_type; 

    typedef typename halfedge_type::edge_type edge_type; 

    typedef typename std::set< vertex_type* > vertex_container; 
    typedef typename std::set< halfedge_type* > halfedge_container; 
    typedef typename std::set< face_type* > face_container; 

    typedef typename vertex_container::iterator vertex_iterator; 
    typedef typename vertex_container::const_iterator vertex_const_iterator; 

    typedef typename halfedge_container::iterator halfedge_iterator; 
    typedef typename halfedge_container::const_iterator halfedge_const_iterator; 

    typedef typename face_container::iterator face_iterator; 
    typedef typename face_container::const_iterator face_const_iterator; 

    MeshT() : vc(), hc(), fc(), ip(0) { }

    MeshT( items_policy *_ip ) : vc(), hc(), fc(), ip(_ip) { }

    MeshT( const MeshT< Traits >& _m ) { *this = _m; }

    ~MeshT() { this->clear(); }

    void clear( void ) {
        for (vertex_iterator vit = vc.begin(); vit != vc.end(); ++vit) delete *vit;
        for (halfedge_iterator hit = hc.begin(); hit != hc.end(); ++hit) delete *hit;
        for (face_iterator fit = fc.begin(); fit != fc.end(); ++fit) delete *fit;
        vc.clear(); hc.clear(); fc.clear();
    }

    MeshT< Traits >& operator = ( const MeshT< Traits >& _m ) {
        this->ip = _m.get_items_policy();
        std::map< vertex_type*, vertex_type* > vmap; // vertex map
        std::map< halfedge_type*, halfedge_type* > hmap; // halfedge map
        std::map< face_type*, face_type* > fmap; // face map
        this->clear(); // clear this mesh
        // Map copy mesh to this mesh
        for (vertex_iterator vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit) {
            vertex_type *v = this->add_vertex();
            // Verify if the vertex type is adaptive and has a level value
            if( AdaptiveVertexT< Traits > *av = dynamic_cast< AdaptiveVertexT< Traits >* >(v) )
                av->set_level( (*vit)->level() );
            vmap[ *vit ] = v;
        }
        for (halfedge_iterator hit = _m.halfedges_begin(); hit != _m.halfedges_end(); ++hit)
            hmap[ *hit ] = this->add_halfedge();
        for (face_iterator fit = _m.faces_begin(); fit != _m.faces_end(); ++fit)
            fmap[ *fit ] = this->add_face();
        // Build this mesh filtering copy mesh inner structure
        for (vertex_iterator vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit)
            vmap[ *vit ]->set_halfedge( hmap[ (*vit)->halfedge() ] );
        for (halfedge_iterator hit = _m.halfedges_begin(); hit != _m.halfedges_end(); ++hit)
            hmap[ *hit ]->set( vmap[ (*hit)->vertex() ], hmap[ (*hit)->next() ],
                       hmap[ (*hit)->opposite() ], fmap[ (*hit)->face() ] );
        for (face_iterator fit = _m.faces_begin(); fit != _m.faces_end(); ++fit)
            fmap[ *fit ]->set_halfedge( hmap[ (*fit)->halfedge() ] );
        if( this->ip ) { // Set data structure attributes
            for (vertex_iterator vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit)
                this->ip->set_vertex_attributes( vmap[ *vit ], *vit );
            for (halfedge_iterator hit = _m.halfedges_begin(); hit != _m.halfedges_end(); ++hit)
                this->ip->set_halfedge_attributes( hmap[ *hit ], *hit );
            for (face_iterator fit = _m.faces_begin(); fit != _m.faces_end(); ++fit)
                this->ip->set_face_attributes( fmap[ *fit ], *fit );
        }
        return *this;
    }

    void fix_vertices_stars( void ) {
        for (halfedge_iterator hit = hc.begin(); hit != hc.end(); ++hit)
            if( (*hit)->is_boundary() )
                (*hit)->vertex()->set_halfedge( *hit );
    }

    // @name Basic add and delete functions

    vertex_type* add_vertex( void ) { return *vc.insert( new vertex_type() ).first; }

    halfedge_type* add_halfedge( void ) { return *hc.insert( new halfedge_type() ).first; }

    face_type* add_face( void ) { return *fc.insert( new face_type() ).first; }

    void delete_vertex( vertex_type *_v ) { vc.erase( _v ); delete _v; }

    void delete_halfedge( halfedge_type *_h ) { hc.erase( _h ); delete _h; }

    void delete_face( face_type *_f ) { fc.erase( _f ); delete _f; }
 

    // @name Query functions

    bool is_closed( void ) const {
        for (halfedge_const_iterator hit = hc.begin(); hit != hc.end(); ++hit)
            if( (*hit)->is_boundary() ) return false;
        return true;
    }

    bool is_consistent( void ) const {
        for (halfedge_const_iterator hit = hc.begin(); hit != hc.end(); ++hit)
            if( !(*hit)->is_consistent() ) return false;
        return true;
    }

    bool is_manifold( void ) const {
        // First, verifies if there is an isolated vertex not
        // connected to any face
        for (vertex_const_iterator vit = vc.begin(); vit != vc.end(); ++vit)
            if( !(*vit)->on_manifold() ) return false;
        // Second, verifies if there is more than two
        // halfedges representing the same edge
        std::map< edge_type, std::vector< halfedge_type* > > emap; // edge map
        edge_type e; // edge
        for (halfedge_const_iterator hit = hc.begin(); hit != hc.end(); ++hit) {
            (*hit)->edge(e);
            emap[e].push_back( *hit );
            if( emap[e].size() > 2 ) return false;
        }
        emap.clear();
        // Third, vertifies if there is a face juxtaposed with
        // another face
        std::map< edge_type, halfedge_type* > hmap; // halfedge map
        std::vector< vertex_type* > fv, hv; // face and halfedges vertices
        halfedge_type *h, *oh; // current and other halfedge
        bool eq; // equal flag (true if there is two faces juxtaposed)
        for (face_const_iterator fit = fc.begin(); fit != fc.end(); ++fit) {
            h = (*fit)->halfedge();
            do {
                fv.push_back( h->vertex() );
                h = h->next();
            } while( h != (*fit)->halfedge() );
            std::sort( fv.begin(), fv.end() );
            h = (*fit)->halfedge();
            do {
                h->edge(e);
                if( hmap.find( e ) == hmap.end() ) hmap[e] = h;
                else {
                    oh = hmap[e];
                    do {
                        hv.push_back( oh->vertex() );
                        oh = oh->next();
                    } while( oh != hmap[e] );
                    std::sort( hv.begin(), hv.end() );
                    eq = true;
                    for (unsigned int i = 0; i < hv.size() or i < fv.size(); ++i)
                        eq &= (hv[i] == fv[i]);
                    if( eq ) return false;
                    hv.clear();
                }
                h = h->next();
            } while( h != (*fit)->halfedge() );
            fv.clear();
        }
        hmap.clear();
        return true;
    }

    bool is_valid( void ) const {
        // First, verify for each vertex if it has a halfedge
        // and all subsequent points to it
        halfedge_type *fhe, *che;
        unsigned int n;
        for (vertex_const_iterator vit = vc.begin(); vit != vc.end(); ++vit) {
            che = fhe = (*vit)->halfedge();
            n = 0;
            do {
                ++n;
                if( !che ) return false;
                if( che->vertex() != (*vit) ) return false;
                if( che->next()->is_boundary() ) break;
                if( n >= hc.size() ) return false;
                che = che->next()->opposite();
            } while( che != fhe );
        }
        // Second, verify for each halfedge if the next ones
        // and opposite return to it
        for (halfedge_const_iterator hit = hc.begin(); hit != hc.end(); ++hit) {
            che = fhe = (*hit);
            n = 0;
            do {
                ++n;
                if( !che->is_boundary() and che->opposite()->opposite() != che ) return false;
                if( n >= hc.size() ) return false;
                che = che->next();
            } while( che != fhe );
        }
        // Third, verify for each face, if all interior
        // halfedges point to it
        for (face_const_iterator fit = fc.begin(); fit != fc.end(); ++fit) {
            che = fhe = (*fit)->halfedge();
            do {
                if( che->face() != (*fit) ) return false;
                che = che->next();
            } while( che != fhe );
        }
        return true;
    }


    // @name Set functions

    void set_base( const unsigned int& nv,
                   const unsigned int& nf,
                   const unsigned int *conn,
                   const unsigned int& nvf = 3 ) {
        this->clear(); // Clear all containers
        unsigned int i = 0; // Generic index i
        vertex_type **tvc = new vertex_type*[ nv ]; // Temporary vertex containter
        for (i = 0; i < nv; ++i) { // For each mesh vertex
            // The order inside vc is not guaranteed to complain
            // with the input order set by the conn array
            tvc[i] = this->add_vertex(); // Create new vertex
            if( ip ) ip->set_vertex_attributes( i, tvc[i] ); // @see BaseItemsPolicy
        }
        this->set_base( tvc, conn, nf, nvf );
        delete [] tvc; // Clear temporary vertex container
    }

    void set_base( vertex_type **verts,
                   const unsigned int *conn,
                   const unsigned int& nf,
                   const unsigned int& nvf = 3 ) {
        unsigned int i, j, nj, hi; // Generic index i, j, next j and halfedge i
        halfedge_type *fhe, *che, *nhe; // Halfedge pointers: first, current and next
        face_type *f; // Face pointer
        typedef typename std::pair< unsigned int, unsigned int > edge_uint;
        std::map< edge_uint, halfedge_type* > hmap; // Halfedge map (B+-tree)
        edge_uint e; // Edge is two ordered vertex indices
        for (i = 0; i < nf; ++i) { // For each mesh face
            hi = i * nvf; // First halfedge index
            fhe = this->add_halfedge(); // Create first halfedge
            f = this->add_face(); // Create face
            if( ip ) ip->set_face_attributes( i, f ); // @see BaseItemsPolicy
            f->set_halfedge(fhe); // The face's halfedge is the first
            nhe = fhe; // Initialize the next halfedge as the first
            for (j = 0; j < nvf; ++j) { // For each halfedge of the current face
                nj = (j < (nvf-1) ? j+1 : 0); // Next j index
                che = nhe; // Update current halfedge as next halfedge
                if( j == nvf-1 ) nhe = fhe; // In the last iteration the next halfedge is the first
                else nhe = this->add_halfedge(); // Create next halfedge
                verts[ conn[hi+nj] ]->set_halfedge( che ); // The next vertex is pointed by the current halfedge
                // Set halfedge properties
                che->set_vertex( verts[ conn[hi+nj] ] );
                che->set_next( nhe );
                che->set_face( f );
                // Find the other-side halfedge
                if( conn[hi+j] < conn[hi+nj] ) e = std::make_pair( conn[hi+j], conn[hi+nj] );
                else e = std::make_pair( conn[hi+nj], conn[hi+j] );
                if( hmap.find( e ) == hmap.end() ) {
                    // If not found insert it in the B+-tree
                    hmap[e] = che;
                    if( ip ) ip->set_halfedge_attributes( conn[hi+j], conn[hi+nj], j, che ); // @see BaseItemsPolicy
                } else { // If found set both opposite halfedges
                    che->set_opposite( hmap[e] );
                    hmap[e]->set_opposite( che );
                    if( ip ) {
                        ip->set_halfedge_attributes( conn[hi+j], conn[hi+nj], j, che ); // @see BaseItemsPolicy
                        ip->set_halfedge_attributes( che, hmap[e] ); // @see BaseItemsPolicy
                    }
                }
            }
            // If all faces are given in the same
            // orientation there is no need to check if
            // two opposed halfedges are going in the same
            // direction @see is_consistent
        }
        this->fix_vertices_stars();
    }

    void set_items_policy( items_policy *_ip ) { ip = _ip; }


    // @name Get functions

    unsigned int size_of_vertices( void ) const { return vc.size(); }

    unsigned int size_of_halfedges( void ) const { return hc.size(); }

    unsigned int size_of_faces( void ) const { return fc.size(); }

    const vertex_container& set_of_vertices( void ) const { return vc; }

    const halfedge_container& set_of_halfedges( void ) const { return hc; }

    const face_container& set_of_faces( void ) const { return fc; }

    items_policy* get_items_policy( void ) { return ip; }

    const items_policy* get_items_policy( void ) const { return ip; }


    // @name Iterators to access mesh vertices, halfedges and faces

    vertex_iterator vertices_begin( void ) { return vc.begin(); }
    vertex_const_iterator vertices_begin( void ) const { return vc.begin(); }

    vertex_iterator vertices_end( void ) { return vc.end(); }
    vertex_const_iterator vertices_end( void ) const { return vc.end(); }

    halfedge_iterator halfedges_begin( void ) { return hc.begin(); }
    halfedge_const_iterator halfedges_begin( void ) const { return hc.begin(); }

    halfedge_iterator halfedges_end( void ) { return hc.end(); }
    halfedge_const_iterator halfedges_end( void ) const { return hc.end(); }

    face_iterator faces_begin( void ) { return fc.begin(); }
    face_const_iterator faces_begin( void ) const { return fc.begin(); }

    face_iterator faces_end( void ) { return fc.end(); }
    face_const_iterator faces_end( void ) const { return fc.end(); }


private:

    vertex_container vc; 
    halfedge_container hc; 
    face_container fc; 
    items_policy *ip; 

};
//=============================================================================
} // namespace a48
//=============================================================================
#endif // A48_MESHT_HH
//=============================================================================