3 * Copyright (C) 2006-2007 Mathias Froehlich
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
22 #ifndef SG_TRIANGLE_BIN_HXX
23 #define SG_TRIANGLE_BIN_HXX
27 #include "SGVertexArrayBin.hxx"
30 class SGTriangleBin : public SGVertexArrayBin<T> {
32 #define BUILD_EDGE_MAP
33 typedef typename SGVertexArrayBin<T>::value_type value_type;
34 typedef typename SGVertexArrayBin<T>::index_type index_type;
35 typedef SGVec2<index_type> edge_ref;
36 typedef SGVec3<index_type> triangle_ref;
37 typedef std::vector<triangle_ref> TriangleVector;
38 typedef std::vector<index_type> TriangleList;
39 typedef std::map<edge_ref,TriangleList> EdgeMap;
41 void insert(const value_type& v0, const value_type& v1, const value_type& v2)
43 index_type i0 = SGVertexArrayBin<T>::insert(v0);
44 index_type i1 = SGVertexArrayBin<T>::insert(v1);
45 index_type i2 = SGVertexArrayBin<T>::insert(v2);
46 index_type triangleIndex = _triangleVector.size();
47 _triangleVector.push_back(triangle_ref(i0, i1, i2));
49 _edgeMap[edge_ref(i0, i1)].push_back(triangleIndex);
50 _edgeMap[edge_ref(i1, i2)].push_back(triangleIndex);
51 _edgeMap[edge_ref(i2, i0)].push_back(triangleIndex);
55 unsigned getNumTriangles() const
56 { return _triangleVector.size(); }
57 const triangle_ref& getTriangleRef(index_type i) const
58 { return _triangleVector[i]; }
59 const TriangleVector& getTriangles() const
60 { return _triangleVector; }
64 void getConnectedSets(std::list<TriangleVector>& connectSets) const
66 std::vector<bool> processedTriangles(getNumTriangles(), false);
67 for (index_type i = 0; i < getNumTriangles(); ++i) {
68 if (processedTriangles[i])
71 TriangleVector currentSet;
72 std::vector<edge_ref> edgeStack;
75 triangle_ref triangleRef = getTriangleRef(i);
76 edgeStack.push_back(edge_ref(triangleRef[0], triangleRef[1]));
77 edgeStack.push_back(edge_ref(triangleRef[1], triangleRef[2]));
78 edgeStack.push_back(edge_ref(triangleRef[2], triangleRef[0]));
79 currentSet.push_back(triangleRef);
80 processedTriangles[i] = true;
83 while (!edgeStack.empty()) {
84 edge_ref edge = edgeStack.back();
87 typename EdgeMap::const_iterator emiList[2] = {
89 _edgeMap.find(edge_ref(edge[1], edge[0]))
91 for (unsigned ei = 0; ei < 2; ++ei) {
92 typename EdgeMap::const_iterator emi = emiList[ei];
93 if (emi == _edgeMap.end())
96 for (unsigned ti = 0; ti < emi->second.size(); ++ti) {
97 index_type triangleIndex = emi->second[ti];
98 if (processedTriangles[triangleIndex])
101 triangle_ref triangleRef = getTriangleRef(triangleIndex);
102 edgeStack.push_back(edge_ref(triangleRef[0], triangleRef[1]));
103 edgeStack.push_back(edge_ref(triangleRef[1], triangleRef[2]));
104 edgeStack.push_back(edge_ref(triangleRef[2], triangleRef[0]));
105 currentSet.push_back(triangleRef);
106 processedTriangles[triangleIndex] = true;
111 connectSets.push_back(currentSet);
117 TriangleVector _triangleVector;
118 #ifdef BUILD_EDGE_MAP