connectivity_graph.cpp

Go to the documentation of this file.

//
// Copyright (C) 2004 Tanguy Fautré.
// For conditions of distribution and use,
// see copyright notice in tri_stripper.h
//
// SVN: $Id: connectivity_graph.cpp 86 2005-06-08 17:47:27Z gpsnoopy $

#include "detail/connectivity_graph.h"

#include <algorithm>




namespace triangle_stripper {

    namespace detail {




namespace
{

    class tri_edge : public triangle_edge
    {
    public:
        tri_edge(index A, index B, size_t TriPos)
            : triangle_edge(A, B), m_TriPos(TriPos) { }

        size_t TriPos() const { return m_TriPos; }

    private:
        size_t  m_TriPos;
    };


    class cmp_tri_edge_lt
    {
    public:
        bool operator() (const tri_edge & a, const tri_edge & b) const;
    };


    typedef std::vector<tri_edge> edge_map;


    void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge);

}




void make_connectivity_graph(graph_array<triangle> & Triangles, const indices & Indices)
{
    assert(Triangles.size() == (Indices.size() / 3));

    // Fill the triangle data
    for (size_t i = 0; i < Triangles.size(); ++i)
        Triangles[i] = triangle(Indices[i * 3 + 0], Indices[i * 3 + 1], Indices[i * 3 + 2]);

    // Build an edge lookup table
    edge_map EdgeMap;
    EdgeMap.reserve(Triangles.size() * 3);

    for (size_t i = 0; i < Triangles.size(); ++i) {

        const triangle & Tri = * Triangles[i];

        EdgeMap.push_back(tri_edge(Tri.A(), Tri.B(), i)); 
        EdgeMap.push_back(tri_edge(Tri.B(), Tri.C(), i)); 
        EdgeMap.push_back(tri_edge(Tri.C(), Tri.A(), i)); 
    }

    std::sort(EdgeMap.begin(), EdgeMap.end(), cmp_tri_edge_lt());

    // Link neighbour triangles together using the lookup table
    for (size_t i = 0; i < Triangles.size(); ++i) {

        const triangle & Tri = * Triangles[i];

        LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.B(), Tri.A(), i)); 
        LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.C(), Tri.B(), i)); 
        LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.A(), Tri.C(), i)); 
    }
}



namespace
{
    
    inline bool cmp_tri_edge_lt::operator() (const tri_edge & a, const tri_edge & b) const
    {
        const index A1 = a.A();
        const index B1 = a.B();
        const index A2 = b.A();
        const index B2 = b.B();

        if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
            return true;
        else
            return false;
    }


    void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge)
    {
        // Find the first edge equal to Edge
        edge_map::const_iterator it = std::lower_bound(EdgeMap.begin(), EdgeMap.end(), Edge, cmp_tri_edge_lt());

        // See if there are any other edges that are equal
        // (if so, it means that more than 2 triangles are sharing the same edge,
        //  which is unlikely but not impossible)
        for (; (it != EdgeMap.end()) && (Edge == (* it)); ++it)
            Triangles.insert_arc(Edge.TriPos(), it->TriPos());

        // Note: degenerated triangles will also point themselves as neighbour triangles
    }

}




    } // namespace detail

} // namespace detail