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