1 /* -*-c++-*-
2  *
3  * Copyright (C) 2006-2007 Mathias Froehlich
4  *
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.
9  *
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.
14  *
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,
18  * MA 02110-1301, USA.
19  *
20  */
21 
22 #ifndef SG_TRIANGLE_BIN_HXX
23 #define SG_TRIANGLE_BIN_HXX
24 
25 #include <vector>
26 #include <map>
27 #include "SGVertexArrayBin.hxx"
28 
29 template<typename T>
30 class SGTriangleBin : public SGVertexArrayBin<T> {
31 public:
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;
40 
insert(const value_type & v0,const value_type & v1,const value_type & v2)41   void insert(const value_type& v0, const value_type& v1, const value_type& v2)
42   {
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));
48 #ifdef BUILD_EDGE_MAP
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);
52 #endif
53   }
54 
getNumTriangles() const55   unsigned getNumTriangles() const
56   { return _triangleVector.size(); }
getTriangleRef(index_type i) const57   const triangle_ref& getTriangleRef(index_type i) const
58   { return _triangleVector[i]; }
getTriangles() const59   const TriangleVector& getTriangles() const
60   { return _triangleVector; }
61 
62 #ifdef BUILD_EDGE_MAP
63 // protected: //FIXME
getConnectedSets(std::list<TriangleVector> & connectSets) const64   void getConnectedSets(std::list<TriangleVector>& connectSets) const
65   {
66     std::vector<bool> processedTriangles(getNumTriangles(), false);
67     for (index_type i = 0; i < getNumTriangles(); ++i) {
68       if (processedTriangles[i])
69         continue;
70 
71       TriangleVector currentSet;
72       std::vector<edge_ref> edgeStack;
73 
74       {
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;
81       }
82 
83       while (!edgeStack.empty()) {
84         edge_ref edge = edgeStack.back();
85         edgeStack.pop_back();
86 
87         typename EdgeMap::const_iterator emiList[2] = {
88           _edgeMap.find(edge),
89           _edgeMap.find(edge_ref(edge[1], edge[0]))
90         };
91         for (unsigned ei = 0; ei < 2; ++ei) {
92           typename EdgeMap::const_iterator emi = emiList[ei];
93           if (emi == _edgeMap.end())
94             continue;
95 
96           for (unsigned ti = 0; ti < emi->second.size(); ++ti) {
97             index_type triangleIndex = emi->second[ti];
98             if (processedTriangles[triangleIndex])
99               continue;
100 
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;
107           }
108         }
109       }
110 
111       connectSets.push_back(currentSet);
112     }
113   }
114 #endif
115 
116 private:
117   TriangleVector _triangleVector;
118 #ifdef BUILD_EDGE_MAP
119   EdgeMap _edgeMap;
120 #endif
121 };
122 
123 #endif
124