1 #ifndef RGBPRIMITIVES_H_
2 #define RGBPRIMITIVES_H_
3
4 /****************************************************************************
5 * Rgb Triangulations Plugin *
6 * *
7 * Author: Daniele Panozzo (daniele.panozzo@gmail.com) *
8 * Copyright(C) 2007 *
9 * DISI - Department of Computer Science *
10 * University of Genova *
11 * *
12 * All rights reserved. *
13 * *
14 * This program is free software; you can redistribute it and/or modify *
15 * it under the terms of the GNU General Public License as published by *
16 * the Free Software Foundation; either version 2 of the License, or *
17 * (at your option) any later version. *
18 * *
19 * This program is distributed in the hope that it will be useful, *
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
22 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
23 * for more details. *
24 ****************************************************************************/
25
26 #include "rgbInfo.h"
27 #include <common/meshmodel.h>
28 #include "topologicalOp.h"
29 #include "controlPoint.h"
30 #include "modButterfly.h"
31
32 namespace rgbt
33 {
34
35
36 /// Class that contain static functions for coarsening and refining operations on rgb triangulation
37 class RgbPrimitives
38 {
39 /// RGB Triangle
40 typedef RgbTriangle<CMeshO> RgbTriangleC;
41 /// RGB Vertex
42 typedef RgbVertex<CMeshO> RgbVertexC;
43
44 /// The tetrahedral mesh type
45 typedef CMeshO TriMeshType;
46 /// The face type
47 typedef TriMeshType::FaceType FaceType;
48 /// The vertex type
49 typedef FaceType::VertexType VertexType;
50 /// The vertex type pointer
51 typedef FaceType::VertexType* VertexPointer;
52 /// The vertex iterator type
53 typedef TriMeshType::VertexIterator VertexIterator;
54 /// The tetra iterator type
55 typedef TriMeshType::FaceIterator FaceIterator;
56 /// The coordinate type
57 typedef FaceType::VertexType::CoordType CoordType;
58 /// The scalar type
59 typedef TriMeshType::VertexType::ScalarType ScalarType;
60 ///the container of tetrahedron type
61 typedef TriMeshType::FaceContainer FaceContainer;
62 ///the container of vertex type
63 typedef TriMeshType::VertContainer VertContainer;
64 ///half edge type
65 typedef TriMeshType::FaceType::EdgeType EdgeType;
66 /// vector of pos
67 typedef std::vector<EdgeType> EdgeVec;
68 ///of VFIterator
69 typedef vcg::face::VFIterator<FaceType> VFI;
70 /// vector of VFIterator
71 typedef std::vector<vcg::face::VFIterator<FaceType> > VFIVec;
72 /// Face Pointer
73 typedef TriMeshType::FacePointer FacePointer;
74 /// Topological Operation Class
75 typedef TopologicalOp<CMeshO,RgbInfo::VERTEXC,RgbInfo::FACEC > TopologicalOpC;
76 /// Vector of FaceColor
77 typedef vector<FaceInfo::FaceColor> vectorFaceColor;
78 /// Vector of RgbTriangle
79 typedef vector<RgbTriangleC> vectorRgbTriangle;
80 /// Pos
81 typedef vcg::face::Pos<FaceType> Pos;
82
83
84
85 public:
86
87 typedef enum {
88 LOOP,
89 MODBUTFLY
90 } subtype;
91
92 /// Test a triangle for correctness in level of its vertexes
93 static bool triangleVertexCorrectness(RgbTriangleC& t);
94 /// Test a triangle for correctness in respect with adjacent triangle
95 static bool triangleAdjCorrectness(RgbTriangleC& t);
96 /// Globally test the correctess of a triangle
97 static bool triangleCorrectness(RgbTriangleC& t);
98 /// Test a triangle correctness in respect to the angles around its vertexes
99 static bool triangleVertexAngleCorrectness(RgbTriangleC& t);
100 /// Test if it's possible to perform a gg-split
101 static bool gg_Split_Possible(RgbTriangleC& t, int EdgeIndex);
102 /// Test if it's possible to perform a rg-split
103 static bool rg_Split_Possible(RgbTriangleC& t, int EdgeIndex);
104 /// Test if it's possible to perform a rr-split
105 static bool rr_Split_Possible(RgbTriangleC& t, int EdgeIndex);
106 /// Test if it's possible to perfomr an edge split
107 static bool edgeSplit_Possible(RgbTriangleC& t, int EdgeIndex);
108 /// Perform a gg-split using to for topology operation (do not check if the split is valid)
109 static void gg_Split(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
110 /// Perform a rg-split using to for topology operation (do not check if the split is valid)
111 static void rg_Split(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
112 /// Perform a rr-split using to for topology operation (do not check if the split is valid)
113 static void rr_Split(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
114 /// Perform an edge split using to for topology operation (check if the split is possible, if not the call has no effect)
115 static bool edgeSplit(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
116 /// If possible perform an edge split on a green edge, eventually causing other split (if the edge is red the call has no effect)
117 /**
118 * vtr (optional) contain all the triangle involved in the operation
119 */
120 static bool recursiveEdgeSplitVV(RgbVertexC& v1,RgbVertexC& v2, TopologicalOpC& to, vector<RgbTriangleC>* vtr = 0);
121 /// Wrapper for recursiveEdgeSplitVV
122 static bool recursiveEdgeSplit(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vtr = 0);
123
124 /// Test if it's possible to perform a bb-swap
125 static bool bb_Swap_Possible(RgbTriangleC& t, int EdgeIndex);
126 /// Perform a bb-swap (do not check if the edge is valid)
127 static void bb_Swap(RgbTriangleC& t, int EdgeIndex, vector<RgbTriangleC>* vt = 0);
128 /// Perform a bb-swap only if some triangle in the FF relation form a valid configuration
129 static void bb_Swap_If_Needed(RgbTriangleC& t, vector<RgbTriangleC>* vt = 0);
130
131 /// Basic operation: perform a g-bisection assigning color and level at rgg and ggr
132 static void g_Bisection(int level, RgbTriangleC& rgg, RgbTriangleC& ggr);
133 /// Basic operation: perform a r-bisection assigning color and level at t1 and t2
134 /*
135 * t1 and t2 are the involved triangle in any order
136 * color: is the color type of red requested
137 * vp: is the red edge
138 */
139 static void r_Bisection(int level,FaceInfo::FaceColor color , RgbTriangleC& t1, RgbTriangleC& t2, VertexPair vp);
140
141 /// Test if it's possible to perform a r4-merge
142 static bool r4_Merge_Possible(RgbTriangleC& t, int VertexIndex);
143 /// Test if it's possible to perform a r2gb-merge
144 static bool r2gb_Merge_Possible(RgbTriangleC& t, int VertexIndex);
145 /// Test if it's possible to perform a gbgb-merge
146 static bool gbgb_Merge_Possible(RgbTriangleC& t, int VertexIndex);
147 /// Test if it's possible to perform a g2b2-merge
148 static bool g2b2_Merge_Possible(RgbTriangleC& t, int VertexIndex);
149 /// Test if around the vertex specified is possible to perform some gg-swap to obtain a legal configuration for the removal of the vertex
150 static bool gg_Swap_Possible(RgbTriangleC& t, int VertexIndex);
151 /// Test if it's possible to remove the specified vertex
152 static bool vertexRemoval_Possible(RgbTriangleC& t, int VertexIndex);
153 /// Perform a gb merge: set the correct color and level at triangle t
154 static void gb_Merge(int level, FaceInfo::FaceColor color , RgbTriangleC& t);
155 /// Perform a r4 merge (do not check if the merge is valid)
156 static void r4_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
157 /// Perform a r2gb merge (do not check if the merge is valid)
158 static void r2gb_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
159 /// Perform a gbgb merge (do not check if the merge is valid)
160 static void gbgb_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
161 /// Perform a g2b2 merge (do not check if the merge is valid)
162 static void g2b2_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
163 /// Perform a vertex removal using a gg_Swap (check if the removal is possible, if not the call has no effect)
164 static void gg_Swap(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
165 /// Utilities that perform a gg_swap (without any check)
166 static void gg_SwapAux(RgbTriangleC& t, int EdgeIndex, vector<RgbTriangleC>* vt = 0);
167 /// Utilities that test if a gg_swap is possible (without any check)
168 static bool gg_SwapAuxPossible(RgbTriangleC& t, int EdgeIndex);
169 /// Perform a vertex removal (check if the removal is possible, if not the call has no effect)
170 static void vertexRemoval(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
171 /// Perform a single r4_Merge
172
173 /// Auxiliary function for case gg-swap 4g1b
174 static void gg_Swap_4g1b(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
175 /// Auxiliary function for case gg-swap 3g2r
176 static void gg_Swap_3g2r(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
177 /// Auxiliary function for case gg-swap 6g
178 static void gg_Swap_6g(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
179
180 /// Test if the configuration is valid for the case gg_swap_4g1b
181 static bool gg_Swap_4g1b_Possible(RgbTriangleC& t, int VertexIndex);
182 /// Test if the configuration is valid for the case gg_swap_3g2r
183 static bool gg_Swap_3g2r_Possible(RgbTriangleC& t, int VertexIndex);
184 /// Test if the configuration is valid for the case gg_swap_6g
185 static bool gg_Swap_6g_Possible(RgbTriangleC& t, int VertexIndex);
186 /// Extract the vf relation (in ccw order) starting from t around vertexIndex
187 /**
188 * the relation is stored in fc
189 */
190 static void vf(RgbTriangleC& t, int VertexIndex, vectorRgbTriangle& fc);
191 /// Check if level are correct in respect at case gg_swap_4g1b
192 static bool check_4g1b_LevelCorrectness(vectorRgbTriangle& fc, int l);
193 /// Check if level are correct in respect at case gg_swap_3g2r
194 static bool check_3g2r_LevelCorrectness(vectorRgbTriangle& fc, int l);
195
196 /// Test if it's possible to perform a 2gbrb-swap
197 static bool brb2g_Swap_Possible(RgbTriangleC& t, int VertexIndex);
198 /// Perform a r2gb merge (do not check if the merge is valid)
199 static void brb2g_Swap(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
200
201 /// Check if the vertex is an internal vertex (the link is a closed chain of edge)
202 static bool isVertexInternal(RgbTriangleC& t, int VertexIndex);
203 /// Check if the vertex is an internal vertex (the link is a closed chain of edge)
204 static bool isVertexInternal(RgbVertexC& v);
205 /// Check if the 2 vertexes form an edge of some triangles
206 /**
207 * t (optional) contain an incident triangle of the edge v1,v2
208 * ti (optional) contain the index of the edge v1,v2 in t
209 */
210 static bool IsValidEdge(RgbVertexC& v1,RgbVertexC& v2, RgbTriangleC* t = 0, int* ti = 0);
211
212 /// Check if a boundary g-bisection is possible
213 static bool b_g_Bisection_Possible(RgbTriangleC& t, int EdgeIndex);
214 /// Perform a boundary g-bisection
215 static void b_g_Bisection(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
216
217 /// Check if a boundary r-bisection is possible
218 static bool b_r_Bisection_Possible(RgbTriangleC& t, int EdgeIndex);
219 /// Perform a boundary r-bisection
220 static void b_r_Bisection(RgbTriangleC& t, int EdgeIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
221
222 /// Test if it's possible to perform a b_r2_Merge
223 static bool b_r2_Merge_Possible(RgbTriangleC& t, int VertexIndex);
224 /// Perform a b_r2_Merge (do not check if the merge is valid)
225 static void b_r2_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
226
227 /// Test if it's possible to perform a b_gb_Merge
228 static bool b_gb_Merge_Possible(RgbTriangleC& t, int VertexIndex);
229 /// Perform a b_gb_Merge (do not check if the merge is valid)
230 static void b_gb_Merge(RgbTriangleC& t, int VertexIndex, TopologicalOpC& to, vector<RgbTriangleC>* vt = 0);
231
232 /// Find the 3 vertexes of the same level of the corresponding triangle
233 static RgbVertexC findOppositeVertex(RgbTriangleC& t, int EdgeIndex, vector<RgbVertexC>* firstVertexes);
234
235 /// Split all the green edges incident in v if they have a level < of the parameter level - 1
236 static void splitGreenEdgeIfNeeded(RgbVertexC& v, int level, TopologicalOpC& to);
237
238 /// Split all the red edges incident in v if they have a level < of the parameter level - 1
239 static void splitRedEdgeIfNeeded(RgbVertexC& v, int level, TopologicalOpC& to);
240
241 /// Extract the face in ccw order around the vertex v
242 static void VF(RgbVertexC& v,vector<FacePointer>& vfp);
243
244 /// Update the normal of v
245 static void updateNormal(RgbVertexC& v);
246
247 //! Return the VV relation
248 static void VV(RgbVertexC& v, vector<RgbVertexC>& vv, bool onlyGreenEdge = false);
249
250 //! Return the number of incident edges in the base mesh (the BaseArity fields in RgbVertex must have been initialized)
251 static unsigned int baseIncidentEdges(RgbVertexC& v);
252
253 /// Type of Subdivision Surface
254 static subtype stype;
255
256 private:
257
258 //! Wrapper for the true edgeSplit. This function choose the type of subdivision surface to use
259 /* Return true if on the current edge was performed only a topological split
260 * return false if a complete split (with update on rgb Info) was performed.
261 */
262 static bool doSplit(RgbTriangleC& fp, int EdgeIndex, int level, TopologicalOpC& to , vector<FacePointer> *vfp = 0, RgbVertexC* vNewInserted = 0, vector<RgbVertexC>* vcont = 0, vector<RgbVertexC>* vupd = 0);
263 //! Wrapper for the edge collapse. This function choose the type of subdivision surface to use
264 static void doCollapse(RgbTriangleC& fp, int EdgeIndex, TopologicalOpC& to, Point3<ScalarType> *p = 0, vector<FacePointer> *vfp = 0);
265
266 /// Extract colors from a vector of RgbTriangle
267 static void extractColor(vectorRgbTriangle& f,vectorFaceColor& c);
268 /// Find the index of the first face that has its color equal to color
269 static int findColorIndex(vectorFaceColor& vc,FaceInfo::FaceColor color);
270 /// Auxiliary function for EdgeSplit, split the passed triangle recursively
271 static void recursiveEdgeSplitAux(RgbVertexC& v1, RgbVertexC& v2, TopologicalOpC& to, vector<RgbTriangleC>* vt);
272 /// Auxiliary function used after every split
273 static void distributeContribute(vector<RgbVertexC>& vCont,RgbVertexC& vNew,vector<RgbVertexC>& vUpd);
274 /// Color Pattern
275 static vector<FaceInfo::FaceColor>* r4p;
276 /// Color Pattern
277 static vector<FaceInfo::FaceColor>* r2gb1p;
278 /// Color Pattern
279 static vector<FaceInfo::FaceColor>* r2gb2p;
280 /// Color Pattern
281 static vector<FaceInfo::FaceColor>* gbgb1p;
282 /// Color Pattern
283 static vector<FaceInfo::FaceColor>* gbgb2p;
284 /// Color Pattern
285 static vector<FaceInfo::FaceColor>* g2b21p;
286 /// Color Pattern
287 static vector<FaceInfo::FaceColor>* g2b22p;
288
289 /// Color Pattern
290 static vector<FaceInfo::FaceColor>* s6gp;
291 /// Color Pattern
292 static vector<FaceInfo::FaceColor>* s4g1bggr;
293 /// Color Pattern
294 static vector<FaceInfo::FaceColor>* s4g1brgg;
295 /// Color Pattern
296 static vector<FaceInfo::FaceColor>* s3g2rp;
297
298 };
299
300 /// Check if the second vector is equal to the first (the 2 vectors can be not aligned)
301 template<class CONTAINER>
isMatch(CONTAINER & cont,CONTAINER & pattern)302 static bool isMatch(CONTAINER& cont, CONTAINER& pattern)
303 {
304 if (cont.size() != pattern.size())
305 return false;
306 int size = cont.size();
307 for(int i=0; i<size;++i)
308 {
309 bool match = true;
310 for(int z=0; z<size;++z)
311 {
312 if (cont[(i+z)%size] != pattern[z])
313 match = false;
314 }
315 if (match) return true;
316 }
317 return false;
318 }
319
320 }
321
322 #endif /*RGBPRIMITIVES_H_*/
323