trimesh.h

#ifndef __trimesh_h__
#define __trimesh_h__

#include <vector>
#include <map>

namespace trimesh {
    typedef long index_t;

    struct edge_t {
        index_t v[2];
        
        index_t& start() { return v[0]; }
        const index_t& start() const { return v[0]; }
        
        index_t& end() { return v[1]; }
        const index_t& end() const { return v[1]; }
        
        edge_t() {
            v[0] = v[1] = -1;
        }
    };
    
    struct triangle_t {
        index_t v[3];
        
        index_t& i() { return v[0]; }
        const index_t& i() const { return v[0]; }
        
        index_t& j() { return v[1]; }
        const index_t& j() const { return v[1]; }
        
        index_t& k() { return v[2]; }
        const index_t& k() const { return v[2]; }
        
        triangle_t() {
            v[0] = v[1] = v[2] = -1;
        }
    };

    // trimesh_t:: build() needs the unordered edges of the mesh. If you don't have them, call this first.
    void unordered_edges_from_triangles( const unsigned long num_triangles, const trimesh::triangle_t* triangles, std::vector< trimesh::edge_t>& edges_out);

    class trimesh_t {
    public:
        // I need positive and negative numbers so that I can use -1 for an invalid index.
        typedef long index_t;
        
        struct halfedge_t {
            // Index into the vertex array.
            index_t to_vertex;
            // Index into the face array.
            index_t face;
            // Index into the edges array.
            index_t edge;
            // Index into the halfedges array.
            index_t opposite_he;
            // Index into the halfedges array.
            index_t next_he;
            
            halfedge_t():
                to_vertex( -1 ),
                face( -1 ),
                edge( -1 ),
                opposite_he( -1 ),
                next_he( -1 ) {
            }
        };
        
        // Builds the half-edge data structures from the given triangles and edges.
        // NOTE: 'edges' can be derived from 'triangles' by calling
        //       unordered_edges_from_triangles(), above.  build() does not
        //       but could do this for callers who do not already have edges.
        // NOTE: 'triangles' and 'edges' are not needed after the call to build()
        //       completes and may be destroyed.
        void build(const unsigned long num_vertices, const unsigned long num_triangles, const triangle_t* triangles, const unsigned long num_edges, const edge_t* edges);
        
        void clear() {
            _halfedges.clear();
            _vertex_halfedges.clear();
            _face_halfedges.clear();
            _edge_halfedges.clear();
            _directed_edge2he_index.clear();
        }
        
        const halfedge_t& halfedge(const index_t i) const { return _halfedges.at( i ); }
        
        std::pair< index_t, index_t > he_index2directed_edge( const index_t he_index ) const {
            // Given the index of a halfedge_t, returns the corresponding directed edge (i,j).
            const halfedge_t& he = _halfedges[ he_index ];

            return std::make_pair( _halfedges[ he.opposite_he ].to_vertex, he.to_vertex );
        }
        
        index_t directed_edge2he_index( const index_t i, const index_t j ) const {
            // Given a directed edge (i,j), returns the index of the 'halfedge_t' in halfedges().
            
            // This isn't const, and doesn't handle the case where (i,j) isn't known:
            // return _directed_edge2he_index[ std::make_pair( i,j ) ];
            
            directed_edge2index_map_t::const_iterator result = _directed_edge2he_index.find(std::make_pair( i,j ));

            if (result == _directed_edge2he_index.end()) {
                return -1;
            }
            
            return result->second;
        }
        
        void vertex_vertex_neighbors( const index_t vertex_index, std::vector< index_t >& result ) const {
            // Returns in 'result' the vertex neighbors (as indices) of the vertex 'vertex_index'.                
            result.clear();
            
            const index_t start_hei = _vertex_halfedges[vertex_index];
            index_t hei = start_hei;
            while(true) {
                const halfedge_t& he = _halfedges[hei];
                result.push_back(he.to_vertex);
                
                hei = _halfedges[he.opposite_he].next_he;
                if (hei == start_hei) {
                    break;
                }
            }
        }

        std::vector<index_t> vertex_vertex_neighbors( const index_t vertex_index ) const {
            std::vector<index_t> result;
            vertex_vertex_neighbors(vertex_index, result);

            return result;
        }
        
        int vertex_valence( const index_t vertex_index ) const {
            // Returns the valence (number of vertex neighbors) of vertex with index 'vertex_index'.
            std::vector<index_t> neighbors;
            vertex_vertex_neighbors(vertex_index, neighbors);

            return neighbors.size();
        }
        
        void vertex_face_neighbors( const index_t vertex_index, std::vector< index_t >& result ) const {
            // Returns in 'result' the face neighbors (as indices) of the vertex 'vertex_index'.
            result.clear();
            
            const index_t start_hei = _vertex_halfedges[ vertex_index ];
            index_t hei = start_hei;
            while(true) {
                const halfedge_t& he = _halfedges[ hei ];
                if (-1 != he.face) {
                    result.push_back( he.face );
                }
                
                hei = _halfedges[ he.opposite_he ].next_he;
                if (hei == start_hei) {
                    break;
                }
            }
        }
        std::vector<index_t> vertex_face_neighbors( const index_t vertex_index ) const {
            std::vector<index_t> result;
            vertex_face_neighbors(vertex_index, result);
            
            return result;
        }
        
        bool vertex_is_boundary( const index_t vertex_index ) const {
            // Returns whether the vertex with given index is on the boundary.
            return (-1 == _halfedges[_vertex_halfedges[vertex_index]].face);
        }
        
        std::vector<index_t> boundary_vertices() const;
        std::vector<std::pair<index_t, index_t>> boundary_edges() const;
        
    private:
        std::vector<halfedge_t> _halfedges;
        // Offsets into the 'halfedges' sequence, one per vertex.
        std::vector<index_t> _vertex_halfedges;
        // Offset into the 'halfedges' sequence, one per face.
        std::vector<index_t> _face_halfedges;
        // Offset into the 'halfedges' sequence, one per edge (unordered pair of vertex indices).
        std::vector<index_t> _edge_halfedges;
        // A map from an ordered edge (an std::pair of index_t's) to an offset into the 'halfedge' sequence.
        typedef std::map<std::pair<index_t, index_t>, index_t> directed_edge2index_map_t;
        directed_edge2index_map_t _directed_edge2he_index;
    };
}

#endif