1 /****************************************************************************
2 * VCGLib o o *
3 * Visual and Computer Graphics Library o o *
4 * _ O _ *
5 * Copyright(C) 2004-2016 \/)\/ *
6 * Visual Computing Lab /\/| *
7 * ISTI - Italian National Research Council | *
8 * \ *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
20 * for more details. *
21 * *
22 ****************************************************************************/
23
24 #ifndef _VCG_FACE_TOPOLOGY
25 #define _VCG_FACE_TOPOLOGY
26
27 #include <vcg/simplex/face/pos.h>
28 #include <set>
29
30 namespace vcg {
31 namespace face {
32 /** \addtogroup face */
33 /*@{*/
34
35 /** Return a boolean that indicate if the face is complex.
36 @param j Index of the edge
37 @return true se la faccia e' manifold, false altrimenti
38 */
39 template <class FaceType>
IsManifold(FaceType const & f,const int j)40 inline bool IsManifold( FaceType const & f, const int j )
41 {
42 assert(f.cFFp(j) != 0); // never try to use this on uncomputed topology
43 if(FaceType::HasFFAdjacency())
44 return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
45 else
46 return true;
47 }
48
49 /** Return a boolean that indicate if the j-th edge of the face is a border.
50 @param j Index of the edge
51 @return true if j is an edge of border, false otherwise
52 */
53 template <class FaceType>
IsBorder(FaceType const & f,const int j)54 inline bool IsBorder(FaceType const & f, const int j )
55 {
56 if(FaceType::HasFFAdjacency())
57 return f.cFFp(j)==&f;
58 //return f.IsBorder(j);
59
60 assert(0);
61 return true;
62 }
63
64 /*! \brief Compute the signed dihedral angle between the normals of two adjacent faces
65 *
66 * The angle between the normal is signed according to the concavity/convexity of the
67 * dihedral angle: negative if the edge shared between the two faces is concave, positive otherwise.
68 * The surface it is assumend to be oriented.
69 * It simply use the projection of the opposite vertex onto the plane of the other one.
70 * It does not assume anything on face normals.
71 *
72 * v0 ___________ vf1
73 * |\ |
74 * | \i1 f1 |
75 * | \ |
76 * |f0 i0\ |
77 * | \ |
78 * |__________\|
79 * vf0 v1
80 */
81
82 template <class FaceType>
DihedralAngleRad(FaceType & f,const int i)83 inline typename FaceType::ScalarType DihedralAngleRad(FaceType & f, const int i )
84 {
85 typedef typename FaceType::ScalarType ScalarType;
86 typedef typename FaceType::CoordType CoordType;
87 typedef typename FaceType::VertexType VertexType;
88
89 FaceType *f0 = &f;
90 FaceType *f1 = f.FFp(i);
91 int i0=i;
92 int i1=f.FFi(i);
93 VertexType *vf0 = f0->V2(i0);
94 VertexType *vf1 = f1->V2(i1);
95
96 CoordType n0 = TriangleNormal(*f0).Normalize();
97 CoordType n1 = TriangleNormal(*f1).Normalize();
98 ScalarType off0 = n0*vf0->P();
99 ScalarType off1 = n1*vf1->P();
100
101 ScalarType dist01 = off0 - n0*vf1->P();
102 ScalarType dist10 = off1 - n1*vf0->P();
103
104 // just to be sure use the sign of the largest in absolute value;
105 ScalarType sign;
106 if(fabs(dist01) > fabs(dist10)) sign = dist01;
107 else sign=dist10;
108
109 ScalarType angleRad=AngleN(n0,n1);
110
111 if(sign > 0 ) return angleRad;
112 else return -angleRad;
113 }
114
115 /// Count border edges of the face
116 template <class FaceType>
BorderCount(FaceType const & f)117 inline int BorderCount(FaceType const & f)
118 {
119 if(FaceType::HasFFAdjacency())
120 {
121 int t = 0;
122 if( IsBorder(f,0) ) ++t;
123 if( IsBorder(f,1) ) ++t;
124 if( IsBorder(f,2) ) ++t;
125 return t;
126 }
127 else return 3;
128 }
129
130
131 /// Counts the number of incident faces in a complex edge
132 template <class FaceType>
ComplexSize(FaceType & f,const int e)133 inline int ComplexSize(FaceType & f, const int e)
134 {
135 if(FaceType::HasFFAdjacency())
136 {
137 if(face::IsBorder<FaceType>(f,e)) return 1;
138 if(face::IsManifold<FaceType>(f,e)) return 2;
139
140 // Non manifold case
141 Pos< FaceType > fpos(&f,e);
142 int cnt=0;
143 do
144 {
145 fpos.NextF();
146 assert(!fpos.IsBorder());
147 assert(!fpos.IsManifold());
148 ++cnt;
149 }
150 while(fpos.f!=&f);
151 assert (cnt>2);
152 return cnt;
153 }
154 assert(0);
155 return 2;
156 }
157
158
159 /** This function check the FF topology correctness for an edge of a face.
160 It's possible to use it also in non-two manifold situation.
161 The function cannot be applicated if the adjacencies among faces aren't defined.
162 @param f the face to be checked
163 @param e Index of the edge to be checked
164 */
165 template <class FaceType>
FFCorrectness(FaceType & f,const int e)166 bool FFCorrectness(FaceType & f, const int e)
167 {
168 if(f.FFp(e)==0) return false; // Not computed or inconsistent topology
169
170 if(f.FFp(e)==&f) // Border
171 {
172 if(f.FFi(e)==e) return true;
173 else return false;
174 }
175
176 if(f.FFp(e)->FFp(f.FFi(e))==&f) // plain two manifold
177 {
178 if(f.FFp(e)->FFi(f.FFi(e))==e) return true;
179 else return false;
180 }
181
182 // Non Manifold Case
183 // all the faces must be connected in a loop.
184
185 Pos< FaceType > curFace(&f,e); // Build the half edge
186 int cnt=0;
187 do
188 {
189 if(curFace.IsManifold()) return false;
190 if(curFace.IsBorder()) return false;
191 curFace.NextF();
192 cnt++;
193 assert(cnt<100);
194 }
195 while ( curFace.f != &f);
196 return true;
197 }
198
199
200 /** This function detach the face from the adjacent face via the edge e.
201 It's possible to use this function it ONLY in non-two manifold situation.
202 The function cannot be applicated if the adjacencies among faces aren't defined.
203 @param f the face to be detached
204 @param e Index of the edge to be detached
205 \note it updates border flag and faux flags (the detached edge has it border bit flagged and faux bit cleared)
206 */
207 template <class FaceType>
FFDetachManifold(FaceType & f,const int e)208 void FFDetachManifold(FaceType & f, const int e)
209 {
210 assert(FFCorrectness<FaceType>(f,e));
211 assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
212 FaceType *ffp = f.FFp(e);
213 //int ffi=f.FFp(e);
214 int ffi=f.FFi(e);
215
216 f.FFp(e)=&f;
217 f.FFi(e)=e;
218 ffp->FFp(ffi)=ffp;
219 ffp->FFi(ffi)=ffi;
220
221 f.SetB(e);
222 f.ClearF(e);
223 ffp->SetB(ffi);
224 ffp->ClearF(ffi);
225
226 assert(FFCorrectness<FaceType>(f,e));
227 assert(FFCorrectness<FaceType>(*ffp,ffi));
228 }
229
230 /** This function detach the face from the adjacent face via the edge e.
231 It's possible to use it also in non-two manifold situation.
232 The function cannot be applicated if the adjacencies among faces aren't defined.
233 @param f the face to be detached
234 @param e Index of the edge to be detached
235 */
236
237 template <class FaceType>
FFDetach(FaceType & f,const int e)238 void FFDetach(FaceType & f, const int e)
239 {
240 assert(FFCorrectness<FaceType>(f,e));
241 assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
242 int complexity=ComplexSize(f,e);
243 (void) complexity;
244 assert(complexity>0);
245
246 Pos< FaceType > FirstFace(&f,e); // Build the half edge
247 Pos< FaceType > LastFace(&f,e); // Build the half edge
248 FirstFace.NextF();
249 LastFace.NextF();
250 int cnt=0;
251
252 // then in case of non manifold face continue to advance LastFace
253 // until I find it become the one that
254 // preceed the face I want to erase
255
256 while ( LastFace.f->FFp(LastFace.z) != &f)
257 {
258 assert(ComplexSize(*LastFace.f,LastFace.z)==complexity);
259 assert(!LastFace.IsManifold()); // We enter in this loop only if we are on a non manifold edge
260 assert(!LastFace.IsBorder());
261 LastFace.NextF();
262 cnt++;
263 assert(cnt<100);
264 }
265
266 assert(LastFace.f->FFp(LastFace.z)==&f);
267 assert(f.FFp(e)== FirstFace.f);
268
269 // Now we link the last one to the first one, skipping the face to be detached;
270 LastFace.f->FFp(LastFace.z) = FirstFace.f;
271 LastFace.f->FFi(LastFace.z) = FirstFace.z;
272 assert(ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
273
274 // At the end selfconnect the chosen edge to make a border.
275 f.FFp(e) = &f;
276 f.FFi(e) = e;
277 assert(ComplexSize(f,e)==1);
278
279 assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
280 assert(FFCorrectness<FaceType>(f,e));
281 }
282
283
284 /** This function attach the face (via the edge z1) to another face (via the edge z2). It's possible to use it also in non-two manifold situation.
285 The function cannot be applicated if the adjacencies among faces aren't define.
286 @param z1 Index of the edge
287 @param f2 Pointer to the face
288 @param z2 The edge of the face f2
289 */
290 template <class FaceType>
FFAttach(FaceType * & f,int z1,FaceType * & f2,int z2)291 void FFAttach(FaceType * &f, int z1, FaceType *&f2, int z2)
292 {
293 //typedef FEdgePosB< FACE_TYPE > ETYPE;
294 Pos< FaceType > EPB(f2,z2);
295 Pos< FaceType > TEPB;
296 TEPB = EPB;
297 EPB.NextF();
298 while( EPB.f != f2) //Alla fine del ciclo TEPB contiene la faccia che precede f2
299 {
300 TEPB = EPB;
301 EPB.NextF();
302 }
303 //Salvo i dati di f1 prima di sovrascrivere
304 FaceType *f1prec = f->FFp(z1);
305 int z1prec = f->FFi(z1);
306 //Aggiorno f1
307 f->FFp(z1) = TEPB.f->FFp(TEPB.z);
308 f->FFi(z1) = TEPB.f->FFi(TEPB.z);
309 //Aggiorno la faccia che precede f2
310 TEPB.f->FFp(TEPB.z) = f1prec;
311 TEPB.f->FFi(TEPB.z) = z1prec;
312 }
313
314 /** This function attach the face (via the edge z1) to another face (via the edge z2).
315 It is not possible to use it also in non-two manifold situation.
316 The function cannot be applicated if the adjacencies among faces aren't define.
317 @param z1 Index of the edge
318 @param f2 Pointer to the face
319 @param z2 The edge of the face f2
320 */
321 template <class FaceType>
FFAttachManifold(FaceType * & f1,int z1,FaceType * & f2,int z2)322 void FFAttachManifold(FaceType * &f1, int z1, FaceType *&f2, int z2)
323 {
324 assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
325 assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
326 assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
327 assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
328 f1->FFp(z1) = f2;
329 f1->FFi(z1) = z2;
330 f2->FFp(z2) = f1;
331 f2->FFi(z2) = z1;
332 }
333
334 // This one should be called only on uniitialized faces.
335 template <class FaceType>
FFSetBorder(FaceType * & f1,int z1)336 void FFSetBorder(FaceType * &f1, int z1)
337 {
338 assert(f1->FFp(z1)==0 || IsBorder(*f1,z1));
339
340 f1->FFp(z1)=f1;
341 f1->FFi(z1)=z1;
342 }
343
344 template <class FaceType>
AssertAdj(FaceType & f)345 void AssertAdj(FaceType & f)
346 {
347 (void)f;
348 assert(f.FFp(0)->FFp(f.FFi(0))==&f);
349 assert(f.FFp(1)->FFp(f.FFi(1))==&f);
350 assert(f.FFp(2)->FFp(f.FFi(2))==&f);
351
352 assert(f.FFp(0)->FFi(f.FFi(0))==0);
353 assert(f.FFp(1)->FFi(f.FFi(1))==1);
354 assert(f.FFp(2)->FFi(f.FFi(2))==2);
355 }
356
357 /**
358 * Check if the given face is oriented as the one adjacent to the specified edge.
359 * @param f Face to check the orientation
360 * @param z Index of the edge
361 */
362 template <class FaceType>
CheckOrientation(FaceType & f,int z)363 bool CheckOrientation(FaceType &f, int z)
364 {
365 if (IsBorder(f, z))
366 return true;
367 else
368 {
369 FaceType *g = f.FFp(z);
370 int gi = f.FFi(z);
371 if (f.V0(z) == g->V1(gi))
372 return true;
373 else
374 return false;
375 }
376 }
377
378
379 /**
380 * This function change the orientation of the face by inverting the index of two vertex.
381 * @param z Index of the edge
382 */
383 template <class FaceType>
SwapEdge(FaceType & f,const int z)384 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
385
386 template <class FaceType, bool UpdateTopology>
SwapEdge(FaceType & f,const int z)387 void SwapEdge(FaceType &f, const int z)
388 {
389 // swap V0(z) with V1(z)
390 std::swap(f.V0(z), f.V1(z));
391
392 // Managemnt of faux edge information (edge z is not affected)
393 bool Faux1 = f.IsF((z+1)%3);
394 bool Faux2 = f.IsF((z+2)%3);
395 if(Faux1) f.SetF((z+2)%3); else f.ClearF((z+2)%3);
396 if(Faux2) f.SetF((z+1)%3); else f.ClearF((z+1)%3);
397
398 if(f.HasFFAdjacency() && UpdateTopology)
399 {
400 // store information to preserve topology
401 int z1 = (z+1)%3;
402 int z2 = (z+2)%3;
403 FaceType *g1p = f.FFp(z1);
404 FaceType *g2p = f.FFp(z2);
405 int g1i = f.FFi(z1);
406 int g2i = f.FFi(z2);
407
408 // g0 face topology is not affected by the swap
409
410 if (g1p != &f)
411 {
412 g1p->FFi(g1i) = z2;
413 f.FFi(z2) = g1i;
414 }
415 else
416 {
417 f.FFi(z2) = z2;
418 }
419
420 if (g2p != &f)
421 {
422 g2p->FFi(g2i) = z1;
423 f.FFi(z1) = g2i;
424 }
425 else
426 {
427 f.FFi(z1) = z1;
428 }
429
430 // finalize swap
431 f.FFp(z1) = g2p;
432 f.FFp(z2) = g1p;
433 }
434 }
435
436 /*! Perform a simple edge collapse
437 * Basic link conditions
438 *
439 */
440 template <class FaceType>
FFLinkCondition(FaceType & f,const int z)441 bool FFLinkCondition(FaceType &f, const int z)
442 {
443 typedef typename FaceType::VertexType VertexType;
444 typedef typename vcg::face::Pos< FaceType > PosType;
445
446 VertexType *v0=f.V0(z);
447 VertexType *v1=f.V1(z);
448
449 PosType p0(&f,v0);
450 PosType p1(&f,v1);
451 std::vector<VertexType *>v0Vec;
452 std::vector<VertexType *>v1Vec;
453 VVOrderedStarFF(p0,v0Vec);
454 VVOrderedStarFF(p1,v1Vec);
455 std::set<VertexType *> v0set;
456 v0set.insert(v0Vec.begin(),v0Vec.end());
457 assert(v0set.size() == v0Vec.size());
458 int cnt =0;
459 for(size_t i=0;i<v1Vec.size();++i)
460 if(v0set.find(v1Vec[i]) != v0set.end())
461 cnt++;
462
463 if(face::IsBorder(f,z) && (cnt==1)) return true;
464 if(!face::IsBorder(f,z) && (cnt==2)) return true;
465 //assert(0);
466 return false;
467 }
468
469 /*! Perform a simple edge collapse
470 * The edge z is collapsed and the vertex V(z) is collapsed onto the vertex V1(Z)
471 * vertex V(z) is deleted and vertex V1(z) survives.
472 * It assumes that the mesh is Manifold.
473 * Note that it preserves manifoldness only if FFLinkConditions are satisfied
474 * If the mesh is not manifold it will crash (there will be faces with deleted vertexes around)
475 * f12
476 * surV ___________
477 * |\ |
478 * | \ f1 |
479 * f01 | \ z1 | f11
480 * | f0 z0\ |
481 * | \ |
482 * |__________\|
483 * f02 delV
484 */
485 template <class MeshType>
FFEdgeCollapse(MeshType & m,typename MeshType::FaceType & f,const int z)486 void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
487 {
488 typedef typename MeshType::FaceType FaceType;
489 typedef typename MeshType::VertexType VertexType;
490 typedef typename vcg::face::Pos< FaceType > PosType;
491 FaceType *f0 = &f;
492 int z0=z;
493 FaceType *f1 = f.FFp(z);
494 int z1=f.FFi(z);
495
496 VertexType *delV=f.V0(z);
497 VertexType *surV=f.V1(z);
498
499 // Collect faces that have to be updated
500 PosType delPos(f0,delV);
501 std::vector<PosType> faceToBeChanged;
502 VFOrderedStarFF(delPos,faceToBeChanged);
503
504 // Topology Stitching
505 FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
506 int i01=-1, i02=-1, i11=-1, i12=-1;
507 // Note that the faux bit is preserved only if both of the edges to be stiched are faux.
508 bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
509 bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
510
511 if(!face::IsBorder(*f0,(z0+1)%3)) { f01 = f0->FFp((z0+1)%3); i01=f0->FFi((z0+1)%3); FFDetachManifold(*f0,(z0+1)%3);}
512 if(!face::IsBorder(*f0,(z0+2)%3)) { f02 = f0->FFp((z0+2)%3); i02=f0->FFi((z0+2)%3); FFDetachManifold(*f0,(z0+2)%3);}
513 if(!face::IsBorder(*f1,(z1+1)%3)) { f11 = f1->FFp((z1+1)%3); i11=f1->FFi((z1+1)%3); FFDetachManifold(*f1,(z1+1)%3);}
514 if(!face::IsBorder(*f1,(z1+2)%3)) { f12 = f1->FFp((z1+2)%3); i12=f1->FFi((z1+2)%3); FFDetachManifold(*f1,(z1+2)%3);}
515
516 // Final Pass to update the vertex ptrs in all the involved faces
517 for(size_t i=0;i<faceToBeChanged.size();++i) {
518 assert(faceToBeChanged[i].V() == delV);
519 faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
520 }
521
522 if(f01 && f02)
523 {
524 FFAttachManifold(f01,i01,f02,i02);
525 if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
526 }
527 if(f11 && f12) {
528 FFAttachManifold(f11,i11,f12,i12);
529 if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
530 }
531 tri::Allocator<MeshType>::DeleteFace(m,*f0);
532 if(f1!=f0) tri::Allocator<MeshType>::DeleteFace(m,*f1);
533 tri::Allocator<MeshType>::DeleteVertex(m,*delV);
534 }
535
536 /*!
537 * Perform a Geometric Check about the normals of a edge flip.
538 * return trues if after the flip the normals does not change more than the given threshold angle;
539 * it assumes that the flip is topologically correct.
540 *
541 * \param f the face
542 * \param z the edge index
543 * \param angleRad the threshold angle
544 *
545 * oldD1 ___________ newD1
546 * |\ |
547 * | \ |
548 * | \ |
549 * | f z\ |
550 * | \ |
551 * |__________\|
552 * newD0 oldD0
553 */
554
555 template <class FaceType>
CheckFlipEdgeNormal(FaceType & f,const int z,const float angleRad)556 bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
557 {
558 typedef typename FaceType::VertexType VertexType;
559 typedef typename VertexType::CoordType CoordType;
560
561 VertexType *OldDiag0 = f.V0(z);
562 VertexType *OldDiag1 = f.V1(z);
563
564 VertexType *NewDiag0 = f.V2(z);
565 VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
566
567 assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
568
569 CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
570 CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
571 CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
572 CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
573 if(AngleN(oldN0,newN0) > angleRad) return false;
574 if(AngleN(oldN0,newN1) > angleRad) return false;
575 if(AngleN(oldN1,newN0) > angleRad) return false;
576 if(AngleN(oldN1,newN1) > angleRad) return false;
577
578 return true;
579 }
580
581 /*!
582 * Perform a Topological check to see if the z-th edge of the face f can be flipped.
583 * No Geometric test are done. (see CheckFlipEdgeNormal)
584 * \param f pointer to the face
585 * \param z the edge index
586 */
587 template <class FaceType>
CheckFlipEdge(FaceType & f,int z)588 bool CheckFlipEdge(FaceType &f, int z)
589 {
590 typedef typename FaceType::VertexType VertexType;
591 typedef typename vcg::face::Pos< FaceType > PosType;
592
593 if (z<0 || z>2) return false;
594
595 // boundary edges cannot be flipped
596 if (face::IsBorder(f, z)) return false;
597
598 FaceType *g = f.FFp(z);
599 int w = f.FFi(z);
600
601 // check if the vertices of the edge are the same
602 // e.g. the mesh has to be well oriented
603 if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
604 return false;
605
606 // check if the flipped edge is already present in the mesh
607 // f_v2 and g_v2 are the vertices of the new edge
608 VertexType *f_v2 = f.V2(z);
609 VertexType *g_v2 = g->V2(w);
610
611 // just a sanity check. If this happens the mesh is not manifold.
612 if (f_v2 == g_v2) return false;
613
614 // Now walk around f_v2, one of the two vertexes of the new edge
615 // and check that it does not already exists.
616
617 PosType pos(&f, (z+2)%3, f_v2);
618 PosType startPos=pos;
619 do
620 {
621 pos.NextE();
622 if (g_v2 == pos.VFlip())
623 return false;
624 }
625 while (pos != startPos);
626
627 return true;
628 }
629
630 /*!
631 * Flip the z-th edge of the face f.
632 * Check for topological correctness first using <CODE>CheckFlipEdge()</CODE>.
633 * \param f pointer to the face
634 * \param z the edge index
635 *
636 * Note: For <em>edge flip</em> we intend the swap of the diagonal of the quadrilater
637 * formed by the face \a f and the face adjacent to the specified edge.
638 *
639 * 0__________ 2 0__________2
640 * -> 1|\ | | /|1
641 * | \ g | | g / |
642 * | \ | |w / |
643 * | f z\w | | / f z|
644 * | \ | | / |
645 * |__________\|1 <- 1|/__________|
646 * 2 0 2 0
647 *
648 * Note that, after an operation FlipEdge(f,z)
649 * to topologically revert it should be sufficient to do FlipEdge(f,z+1)
650 * (even if the mesh is actually different: f and g will be swapped)
651 *
652 */
653
654 template <class FaceType>
FlipEdge(FaceType & f,const int z)655 void FlipEdge(FaceType &f, const int z)
656 {
657 assert(z>=0);
658 assert(z<3);
659 assert( !IsBorder(f,z) );
660 assert( face::IsManifold<FaceType>(f, z));
661
662 FaceType *g = f.FFp(z); // The other face
663 int w = f.FFi(z); // and other side
664
665 assert( g->V0(w) == f.V1(z) );
666 assert( g->V1(w) == f.V0(z) );
667 assert( g->V2(w) != f.V0(z) );
668 assert( g->V2(w) != f.V1(z) );
669 assert( g->V2(w) != f.V2(z) );
670
671 f.V1(z) = g->V2(w);
672 g->V1(w) = f.V2(z);
673
674 f.FFp(z) = g->FFp((w+1)%3);
675 f.FFi(z) = g->FFi((w+1)%3);
676 g->FFp(w) = f.FFp((z+1)%3);
677 g->FFi(w) = f.FFi((z+1)%3);
678 f.FFp((z+1)%3) = g;
679 f.FFi((z+1)%3) = (w+1)%3;
680 g->FFp((w+1)%3) = &f;
681 g->FFi((w+1)%3) = (z+1)%3;
682
683 if(f.FFp(z)==g)
684 {
685 f.FFp(z) = &f;
686 f.FFi(z) = z;
687 }
688 else
689 {
690 f.FFp(z)->FFp( f.FFi(z) ) = &f;
691 f.FFp(z)->FFi( f.FFi(z) ) = z;
692 }
693 if(g->FFp(w)==&f)
694 {
695 g->FFp(w)=g;
696 g->FFi(w)=w;
697 }
698 else
699 {
700 g->FFp(w)->FFp( g->FFi(w) ) = g;
701 g->FFp(w)->FFi( g->FFi(w) ) = w;
702 }
703
704 }
705
706 template <class FaceType>
VFDetach(FaceType & f)707 void VFDetach(FaceType & f)
708 {
709 VFDetach(f,0);
710 VFDetach(f,1);
711 VFDetach(f,2);
712 }
713
714 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z,
715 // NOTA funziona SOLO per la topologia VF!!!
716 // usata nelle classi di collapse
717 template <class FaceType>
VFDetach(FaceType & f,int z)718 void VFDetach(FaceType & f, int z)
719 {
720 if(f.V(z)->VFp()==&f ) //if it is the first face detach from the begin
721 {
722 int fz = f.V(z)->VFi();
723 f.V(z)->VFp() = f.VFp(fz);
724 f.V(z)->VFi() = f.VFi(fz);
725 }
726 else // scan the list of faces in order to finde the current face f to be detached
727 {
728 VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
729 VFIterator<FaceType> y;
730
731 for(;;)
732 {
733 y = x;
734 ++x;
735 assert(x.f!=0);
736 if(x.f==&f) // found!
737 {
738 y.f->VFp(y.z) = f.VFp(z);
739 y.f->VFi(y.z) = f.VFi(z);
740 break;
741 }
742 }
743 }
744 }
745
746 /// Append a face in VF list of vertex f->V(z)
747 template <class FaceType>
VFAppend(FaceType * & f,int z)748 void VFAppend(FaceType* & f, int z)
749 {
750 typename FaceType::VertexType *v = f->V(z);
751 if (v->VFp()!=0)
752 {
753 FaceType *f0=v->VFp();
754 int z0=v->VFi();
755 //append
756 f->VFp(z)=f0;
757 f->VFi(z)=z0;
758 }
759 v->VFp()=f;
760 v->VFi()=z;
761 }
762
763 /*!
764 * \brief Compute the set of vertices adjacent to a given vertex using VF adjacency
765 *
766 * \param vp pointer to the vertex whose star has to be computed.
767 * \param starVec a std::vector of Vertex pointer that is filled with the adjacent vertices.
768 *
769 */
770
771 template <class FaceType>
VVStarVF(typename FaceType::VertexType * vp,std::vector<typename FaceType::VertexType * > & starVec)772 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
773 {
774 typedef typename FaceType::VertexType* VertexPointer;
775 starVec.clear();
776 face::VFIterator<FaceType> vfi(vp);
777 while(!vfi.End())
778 {
779 starVec.push_back(vfi.F()->V1(vfi.I()));
780 starVec.push_back(vfi.F()->V2(vfi.I()));
781 ++vfi;
782 }
783
784 std::sort(starVec.begin(),starVec.end());
785 typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
786 starVec.resize(new_end-starVec.begin());
787 }
788
789 /*!
790 * \brief Compute the set of vertices adjacent to a given vertex using VF adjacency.
791 *
792 * The set is faces is extended of a given number of step
793 * \param vp pointer to the vertex whose star has to be computed.
794 * \param num_step the number of step to extend the star
795 * \param vertVec a std::vector of Ve pointer that is filled with the adjacent faces.
796 */
797 template <class FaceType>
VVExtendedStarVF(typename FaceType::VertexType * vp,const int num_step,std::vector<typename FaceType::VertexType * > & vertVec)798 void VVExtendedStarVF(typename FaceType::VertexType* vp,
799 const int num_step,
800 std::vector<typename FaceType::VertexType *> &vertVec)
801 {
802 typedef typename FaceType::VertexType VertexType;
803 ///initialize front
804 vertVec.clear();
805 vcg::face::VVStarVF<FaceType>(vp,vertVec);
806 ///then dilate front
807 ///for each step
808 for (int step=0;step<num_step-1;step++)
809 {
810 std::vector<VertexType *> toAdd;
811 for (unsigned int i=0;i<vertVec.size();i++)
812 {
813 std::vector<VertexType *> Vtemp;
814 vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
815 toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
816 }
817 vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
818 std::sort(vertVec.begin(),vertVec.end());
819 typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
820 int dist=distance(vertVec.begin(),new_end);
821 vertVec.resize(dist);
822 }
823 }
824
825 /*!
826 * \brief Compute the set of faces adjacent to a given vertex using VF adjacency.
827 *
828 * \param vp pointer to the vertex whose star has to be computed.
829 * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
830 * \param indexes a std::vector of integer of the vertex as it is seen from the faces
831 */
832 template <class FaceType>
VFStarVF(typename FaceType::VertexType * vp,std::vector<FaceType * > & faceVec,std::vector<int> & indexes)833 void VFStarVF( typename FaceType::VertexType* vp,
834 std::vector<FaceType *> &faceVec,
835 std::vector<int> &indexes)
836 {
837 faceVec.clear();
838 indexes.clear();
839 face::VFIterator<FaceType> vfi(vp);
840 while(!vfi.End())
841 {
842 faceVec.push_back(vfi.F());
843 indexes.push_back(vfi.I());
844 ++vfi;
845 }
846 }
847
848
849 /*!
850 * \brief Compute the set of faces incident onto a given edge using FF adjacency.
851 *
852 * \param fp pointer to the face whose star has to be computed
853 * \param ei the index of the edge
854 * \param faceVec a std::vector of Face pointer that is filled with the faces incident on that edge.
855 * \param indexes a std::vector of integer of the edge position as it is seen from the faces
856 */
857 template <class FaceType>
EFStarFF(FaceType * fp,int ei,std::vector<FaceType * > & faceVec,std::vector<int> & indVed)858 void EFStarFF( FaceType* fp, int ei,
859 std::vector<FaceType *> &faceVec,
860 std::vector<int> &indVed)
861 {
862 assert(fp->FFp(ei)!=0);
863 faceVec.clear();
864 indVed.clear();
865 FaceType* fpit=fp;
866 int eit=ei;
867 do
868 {
869 faceVec.push_back(fpit);
870 indVed.push_back(eit);
871 FaceType *new_fpit = fpit->FFp(eit);
872 int new_eit = fpit->FFi(eit);
873 fpit=new_fpit;
874 eit=new_eit;
875 } while(fpit != fp);
876 }
877
878
879 /* Compute the set of faces adjacent to a given face using FF adjacency.
880 * The set is faces is extended of a given number of step
881 * \param fp pointer to the face whose star has to be computed.
882 * \param num_step the number of step to extend the star
883 * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
884 */
885 template <class FaceType>
FFExtendedStarFF(FaceType * fp,const int num_step,std::vector<FaceType * > & faceVec)886 static void FFExtendedStarFF(FaceType *fp,
887 const int num_step,
888 std::vector<FaceType*> &faceVec)
889 {
890 ///initialize front
891 faceVec.push_back(fp);
892 ///then dilate front
893 ///for each step
894 for (int step=0;step<num_step;step++)
895 {
896 std::vector<FaceType*> toAdd;
897 for (unsigned int i=0;i<faceVec.size();i++)
898 {
899 FaceType *f=faceVec[i];
900 for (int k=0;k<3;k++)
901 {
902 FaceType *f1=f->FFp(k);
903 if (f1==f)continue;
904 toAdd.push_back(f1);
905 }
906 }
907 faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
908 std::sort(faceVec.begin(),faceVec.end());
909 typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
910 int dist=distance(faceVec.begin(),new_end);
911 faceVec.resize(dist);
912 }
913 }
914
915 /*!
916 * \brief Compute the set of faces adjacent to a given vertex using VF adjacency.
917 *
918 * The set is faces is extended of a given number of step
919 * \param vp pointer to the vertex whose star has to be computed.
920 * \param num_step the number of step to extend the star
921 * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
922 */
923 template <class FaceType>
VFExtendedStarVF(typename FaceType::VertexType * vp,const int num_step,std::vector<FaceType * > & faceVec)924 void VFExtendedStarVF(typename FaceType::VertexType* vp,
925 const int num_step,
926 std::vector<FaceType*> &faceVec)
927 {
928 ///initialize front
929 faceVec.clear();
930 std::vector<int> indexes;
931 vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
932 ///then dilate front
933 ///for each step
934 for (int step=0;step<num_step;step++)
935 {
936 std::vector<FaceType*> toAdd;
937 for (unsigned int i=0;i<faceVec.size();i++)
938 {
939 FaceType *f=faceVec[i];
940 for (int k=0;k<3;k++)
941 {
942 FaceType *f1=f->FFp(k);
943 if (f1==f)continue;
944 toAdd.push_back(f1);
945 }
946 }
947 faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
948 std::sort(faceVec.begin(),faceVec.end());
949 typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
950 int dist=distance(faceVec.begin(),new_end);
951 faceVec.resize(dist);
952 }
953 }
954
955 /*!
956 * \brief Compute the ordered set of vertices adjacent to a given vertex using FF adiacency
957 *
958 * \param startPos a Pos<FaceType> indicating the vertex whose star has to be computed.
959 * \param vertexVec a std::vector of VertexPtr filled vertices around the given vertex.
960 *
961 */
962 template <class FaceType>
VVOrderedStarFF(Pos<FaceType> & startPos,std::vector<typename FaceType::VertexType * > & vertexVec)963 void VVOrderedStarFF(Pos<FaceType> &startPos,
964 std::vector<typename FaceType::VertexType *> &vertexVec)
965 {
966 vertexVec.clear();
967 std::vector<Pos<FaceType> > posVec;
968 VFOrderedStarFF(startPos,posVec);
969 for(size_t i=0;i<posVec.size();++i)
970 vertexVec.push_back(posVec[i].VFlip());
971 }
972
973 /*!
974 * \brief Compute the ordered set of faces adjacent to a given vertex using FF adiacency
975 *
976 * \param startPos a Pos<FaceType> indicating the vertex whose star has to be computed.
977 * \param posVec a std::vector of Pos filled with Pos arranged around the passed vertex.
978 *
979 */
980 template <class FaceType>
VFOrderedStarFF(const Pos<FaceType> & startPos,std::vector<Pos<FaceType>> & posVec)981 void VFOrderedStarFF(const Pos<FaceType> &startPos,
982 std::vector<Pos<FaceType> > &posVec)
983 {
984 posVec.clear();
985 bool foundBorder=false;
986 size_t firstBorderInd;
987 Pos<FaceType> curPos=startPos;
988 do
989 {
990 assert(curPos.IsManifold());
991 if(curPos.IsBorder() && !foundBorder) {
992 foundBorder=true;
993 firstBorderInd = posVec.size();
994 }
995 posVec.push_back(curPos);
996 curPos.FlipF();
997 curPos.FlipE();
998 } while(curPos!=startPos);
999 // if we found a border we visited each face exactly twice,
1000 // and we have to extract the border-to-border pos sequence
1001 if(foundBorder)
1002 {
1003 size_t halfSize=posVec.size()/2;
1004 assert((posVec.size()%2)==0);
1005 posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1006 posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1007 assert(posVec.size()==halfSize);
1008 }
1009 }
1010
1011 /*!
1012 * \brief Compute the ordered set of faces adjacent to a given vertex using FF adiacency
1013 *
1014 * \param startPos a Pos<FaceType> indicating the vertex whose star has to be computed.
1015 * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
1016 * \param edgeVec a std::vector of indexes filled with the indexes of the corresponding edges shared between the faces.
1017 *
1018 */
1019
1020 template <class FaceType>
VFOrderedStarFF(const Pos<FaceType> & startPos,std::vector<FaceType * > & faceVec,std::vector<int> & edgeVec)1021 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1022 std::vector<FaceType*> &faceVec,
1023 std::vector<int> &edgeVec)
1024 {
1025 std::vector<Pos<FaceType> > posVec;
1026 VFOrderedStarFF(startPos,posVec);
1027 faceVec.clear();
1028 edgeVec.clear();
1029 for(size_t i=0;i<posVec.size();++i)
1030 {
1031 faceVec.push_back(posVec[i].F());
1032 edgeVec.push_back(posVec[i].E());
1033 }
1034 }
1035
1036 /*!
1037 * Check if two faces share and edge through the FF topology.
1038 * \param f0,f1 the two face to be checked
1039 * \param i0,i1 the index of the shared edge;
1040 */
1041
1042 template <class FaceType>
1043 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
1044 {
1045 assert((!f0->IsD())&&(!f1->IsD()));
1046 for (int i=0;i<3;i++)
1047 if (f0->FFp(i)==f1)
1048 {
1049 if((i0!=0) && (i1!=0)) {
1050 *i0=i;
1051 *i1=f0->FFi(i);
1052 }
1053 return true;
1054 }
1055 return false;
1056 }
1057
1058 /*!
1059 * Count the number of vertices shared between two faces.
1060 * \param f0,f1 the two face to be checked
1061 * ;
1062 */
1063 template <class FaceType>
CountSharedVertex(FaceType * f0,FaceType * f1)1064 int CountSharedVertex(FaceType *f0,FaceType *f1)
1065 {
1066 int sharedCnt=0;
1067 for (int i=0;i<3;i++)
1068 for (int j=0;j<3;j++)
1069 if (f0->V(i)==f1->V(j)) {
1070 sharedCnt++;
1071 }
1072 return sharedCnt;
1073 }
1074
1075 /*!
1076 * find the first shared vertex between two faces.
1077 * \param f0,f1 the two face to be checked
1078 * \param i,j the indexes of the shared vertex in the two faces. Meaningful only if there is one single shared vertex
1079 * ;
1080 */
1081 template <class FaceType>
FindSharedVertex(FaceType * f0,FaceType * f1,int & i,int & j)1082 bool FindSharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
1083 {
1084 for (i=0;i<3;i++)
1085 for (j=0;j<3;j++)
1086 if (f0->V(i)==f1->V(j)) return true;
1087
1088 i=-1;j=-1;
1089 return false;
1090 }
1091
1092 /*!
1093 * find the first shared edge between two faces.
1094 * \param f0,f1 the two face to be checked
1095 * \param i,j the indexes of the shared edge in the two faces. Meaningful only if there is a shared edge
1096 *
1097 */
1098 template <class FaceType>
FindSharedEdge(FaceType * f0,FaceType * f1,int & i,int & j)1099 bool FindSharedEdge(FaceType *f0,FaceType *f1, int &i, int &j)
1100 {
1101 for (i=0;i<3;i++)
1102 for (j=0;j<3;j++)
1103 if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1104 ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1105 return true;
1106 i=-1;j=-1;
1107 return false;
1108 }
1109
1110 /*!
1111 * find the faces that shares the two vertices
1112 * \param v0,v1 the two vertices
1113 * \param f0,f1 the two faces , counterclokwise order
1114 *
1115 */
1116 template <class FaceType>
FindSharedFaces(typename FaceType::VertexType * v0,typename FaceType::VertexType * v1,FaceType * & f0,FaceType * & f1,int & e0,int & e1)1117 bool FindSharedFaces(typename FaceType::VertexType *v0,
1118 typename FaceType::VertexType *v1,
1119 FaceType *&f0,
1120 FaceType *&f1,
1121 int &e0,
1122 int &e1)
1123 {
1124 std::vector<FaceType*> faces0;
1125 std::vector<FaceType*> faces1;
1126 std::vector<int> index0;
1127 std::vector<int> index1;
1128 VFStarVF<FaceType>(v0,faces0,index0);
1129 VFStarVF<FaceType>(v1,faces1,index1);
1130 ///then find the intersection
1131 std::sort(faces0.begin(),faces0.end());
1132 std::sort(faces1.begin(),faces1.end());
1133 std::vector<FaceType*> Intersection;
1134 std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1135 if (Intersection.size()<2)return false; ///no pair of faces share the 2 vertices
1136 assert(Intersection.size()==2);//otherwhise non manifoldess
1137 f0=Intersection[0];
1138 f1=Intersection[1];
1139 FindSharedEdge(f0,f1,e0,e1);
1140 ///and finally check if the order is right
1141 if (f0->V(e0)!=v0)
1142 {
1143 std::swap(f0,f1);
1144 std::swap(e0,e1);
1145 }
1146 return true;
1147 }
1148
1149 /*@}*/
1150 } // end namespace
1151 } // end namespace
1152
1153 #endif
1154
1155