www.pudn.com > tristripper-1.1.0-beta-5.zip > connectivity_graph.cpp

// 
// 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  
 
 
 
 
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 edge_map; 
 
 
	void LinkNeighbours(graph_array & Triangles, const edge_map & EdgeMap, const tri_edge Edge); 
 
} 
 
 
 
 
void make_connectivity_graph(graph_array & 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 & 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