VCG Library
simplex/face/topology.h
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 
29 namespace vcg {
30 namespace face {
33 
38 template <class FaceType>
39 inline bool IsManifold( FaceType const & f, const int j )
40 {
41  assert(f.cFFp(j) != 0); // never try to use this on uncomputed topology
42  if(FaceType::HasFFAdjacency())
43  return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
44  else
45  return true;
46 }
47 
52 template <class FaceType>
53 inline bool IsBorder(FaceType const & f, const int j )
54 {
55  if(FaceType::HasFFAdjacency())
56  return f.cFFp(j)==&f;
57  //return f.IsBorder(j);
58 
59  assert(0);
60  return true;
61 }
62 
81 template <class FaceType>
82 inline typename FaceType::ScalarType DihedralAngleRad(FaceType & f, const int i )
83 {
84  typedef typename FaceType::ScalarType ScalarType;
85  typedef typename FaceType::CoordType CoordType;
86  typedef typename FaceType::VertexType VertexType;
87 
88  FaceType *f0 = &f;
89  FaceType *f1 = f.FFp(i);
90  int i0=i;
91  int i1=f.FFi(i);
92  VertexType *vf0 = f0->V2(i0);
93  VertexType *vf1 = f1->V2(i1);
94 
95  CoordType n0 = TriangleNormal(*f0).Normalize();
96  CoordType n1 = TriangleNormal(*f1).Normalize();
97  ScalarType off0 = n0*vf0->P();
98  ScalarType off1 = n1*vf1->P();
99 
100  ScalarType dist01 = off0 - n0*vf1->P();
101  ScalarType dist10 = off1 - n1*vf0->P();
102 
103  // just to be sure use the sign of the largest in absolute value;
104  ScalarType sign;
105  if(fabs(dist01) > fabs(dist10)) sign = dist01;
106  else sign=dist10;
107 
108  ScalarType angleRad=AngleN(n0,n1);
109 
110  if(sign > 0 ) return angleRad;
111  else return -angleRad;
112 }
113 
115 template <class FaceType>
116 inline typename FaceType::ScalarType WedgeAngleRad(FaceType & f, const int i )
117 {
118  auto &P0=f.P(i);
119  auto &P1=f.P(f.Next(i));
120  auto &P2=f.P(f.Prev(i));
121  return vcg::Angle(P2 - P0,P1 - P0);
122 }
123 
125 template <class FaceType>
126 inline int BorderCount(FaceType const & f)
127 {
128  if(FaceType::HasFFAdjacency())
129  {
130  int t = 0;
131  if( IsBorder(f,0) ) ++t;
132  if( IsBorder(f,1) ) ++t;
133  if( IsBorder(f,2) ) ++t;
134  return t;
135  }
136  else return 3;
137 }
138 
139 
141 template <class FaceType>
142 inline int ComplexSize(FaceType & f, const int e)
143 {
144  if(FaceType::HasFFAdjacency())
145  {
146  if(face::IsBorder<FaceType>(f,e)) return 1;
147  if(face::IsManifold<FaceType>(f,e)) return 2;
148 
149  // Non manifold case
150  Pos< FaceType > fpos(&f,e);
151  int cnt=0;
152  do
153  {
154  fpos.NextF();
155  assert(!fpos.IsBorder());
156  assert(!fpos.IsManifold());
157  ++cnt;
158  }
159  while(fpos.f!=&f);
160  assert (cnt>2);
161  return cnt;
162  }
163  assert(0);
164  return 2;
165 }
166 
167 
174 template <class FaceType>
175 bool FFCorrectness(FaceType & f, const int e)
176 {
177  if(f.FFp(e)==0) return false; // Not computed or inconsistent topology
178 
179  if(f.FFp(e)==&f) // Border
180  {
181  if(f.FFi(e)==e) return true;
182  else return false;
183  }
184 
185  if(f.FFp(e)->FFp(f.FFi(e))==&f) // plain two manifold
186  {
187  if(f.FFp(e)->FFi(f.FFi(e))==e) return true;
188  else return false;
189  }
190 
191  // Non Manifold Case
192  // all the faces must be connected in a loop.
193 
194  Pos< FaceType > curFace(&f,e); // Build the half edge
195  int cnt=0;
196  do
197  {
198  if(curFace.IsManifold()) return false;
199  if(curFace.IsBorder()) return false;
200  curFace.NextF();
201  cnt++;
202  assert(cnt<100);
203  }
204  while ( curFace.f != &f);
205  return true;
206 }
207 
208 
216 template <class FaceType>
217 void FFDetachManifold(FaceType & f, const int e)
218 {
219  assert(FFCorrectness<FaceType>(f,e));
220  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
221  FaceType *ffp = f.FFp(e);
222  //int ffi=f.FFp(e);
223  int ffi=f.FFi(e);
224 
225  f.FFp(e)=&f;
226  f.FFi(e)=e;
227  ffp->FFp(ffi)=ffp;
228  ffp->FFi(ffi)=ffi;
229 
230  f.SetB(e);
231  f.ClearF(e);
232  ffp->SetB(ffi);
233  ffp->ClearF(ffi);
234 
235  assert(FFCorrectness<FaceType>(f,e));
236  assert(FFCorrectness<FaceType>(*ffp,ffi));
237 }
238 
246 template <class FaceType>
247 void FFDetach(FaceType & f, const int e)
248 {
249  assert(FFCorrectness<FaceType>(f,e));
250  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
251  int complexity=ComplexSize(f,e);
252  (void) complexity;
253  assert(complexity>0);
254  vcg::face::Pos<FaceType> FirstFace(&f,e); // Build the half edge
255  vcg::face::Pos<FaceType> LastFace(&f,e); // Build the half edge
256  FirstFace.NextF();
257  LastFace.NextF();
258  int cnt=0;
259 
260 // then in case of non manifold face continue to advance LastFace
261 // until I find it become the one that
262 // preceed the face I want to erase
263 
264  while ( LastFace.f->FFp(LastFace.z) != &f)
265  {
266  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity);
267  assert(!LastFace.IsManifold()); // We enter in this loop only if we are on a non manifold edge
268  assert(!LastFace.IsBorder());
269  LastFace.NextF();
270  cnt++;
271  assert(cnt<100);
272  }
273 
274  assert(LastFace.f->FFp(LastFace.z)==&f);
275  assert(f.FFp(e)== FirstFace.f);
276 
277  // Now we link the last one to the first one, skipping the face to be detached;
278  LastFace.f->FFp(LastFace.z) = FirstFace.f;
279  LastFace.f->FFi(LastFace.z) = FirstFace.z;
280  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
281 
282  // At the end selfconnect the chosen edge to make a border.
283  f.FFp(e) = &f;
284  f.FFi(e) = e;
285  assert(ComplexSize(f,e)==1);
286 
287  assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
288  assert(FFCorrectness<FaceType>(f,e));
289 }
290 
291 
298 template <class FaceType>
299 void FFAttach(FaceType * &f, int z1, FaceType *&f2, int z2)
300 {
301  //typedef FEdgePosB< FACE_TYPE > ETYPE;
302  vcg::face::Pos< FaceType > EPB(f2,z2);
303  vcg::face::Pos< FaceType > TEPB;
304  TEPB = EPB;
305  EPB.NextF();
306  while( EPB.f != f2) //Alla fine del ciclo TEPB contiene la faccia che precede f2
307  {
308  TEPB = EPB;
309  EPB.NextF();
310  }
311  //Salvo i dati di f1 prima di sovrascrivere
312  FaceType *f1prec = f->FFp(z1);
313  int z1prec = f->FFi(z1);
314 
315  //Aggiorno f1
316  assert(f1prec == f);
317  assert(TEPB.f->FFp(TEPB.z) == f2);
318 
319  f->FFp(z1) = TEPB.f->FFp(TEPB.z);
320  f->FFi(z1) = TEPB.f->FFi(TEPB.z);
321 
322  //Aggiorno la faccia che precede f2
323  TEPB.f->FFp(TEPB.z) = f1prec;
324  TEPB.f->FFi(TEPB.z) = z1prec;
325 
326  assert(FFCorrectness<FaceType>(*f,z1));
327  assert(FFCorrectness<FaceType>(*TEPB.f, TEPB.z));
328 
329 }
330 
338 template <class FaceType>
339 void FFAttachManifold(FaceType * &f1, int z1, FaceType *&f2, int z2)
340 {
341  assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
342  assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
343  assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
344  assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
345  f1->FFp(z1) = f2;
346  f1->FFi(z1) = z2;
347  f2->FFp(z2) = f1;
348  f2->FFi(z2) = z1;
349 }
350 
351 // This one should be called only on uniitialized faces.
352 template <class FaceType>
353 void FFSetBorder(FaceType * &f1, int z1)
354 {
355  assert(f1->FFp(z1)==0 || IsBorder(*f1,z1));
356 
357  f1->FFp(z1)=f1;
358  f1->FFi(z1)=z1;
359 }
360 
361 template <class FaceType>
362 void AssertAdj(FaceType & f)
363 {
364  (void)f;
365  assert(f.FFp(0)->FFp(f.FFi(0))==&f);
366  assert(f.FFp(1)->FFp(f.FFi(1))==&f);
367  assert(f.FFp(2)->FFp(f.FFi(2))==&f);
368 
369  assert(f.FFp(0)->FFi(f.FFi(0))==0);
370  assert(f.FFp(1)->FFi(f.FFi(1))==1);
371  assert(f.FFp(2)->FFi(f.FFi(2))==2);
372 }
373 
379 template <class FaceType>
380 bool CheckOrientation(FaceType &f, int z)
381 {
382  if (IsBorder(f, z))
383  return true;
384  else
385  {
386  FaceType *g = f.FFp(z);
387  int gi = f.FFi(z);
388  if (f.V0(z) == g->V1(gi))
389  return true;
390  else
391  return false;
392  }
393 }
394 
395 
400 template <class FaceType>
401 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
402 
403 template <class FaceType, bool UpdateTopology>
404 void SwapEdge(FaceType &f, const int z)
405 {
406  // swap V0(z) with V1(z)
407  std::swap(f.V0(z), f.V1(z));
408 
409  // Managemnt of faux edge information (edge z is not affected)
410  bool Faux1 = f.IsF((z+1)%3);
411  bool Faux2 = f.IsF((z+2)%3);
412  if(Faux1) f.SetF((z+2)%3); else f.ClearF((z+2)%3);
413  if(Faux2) f.SetF((z+1)%3); else f.ClearF((z+1)%3);
414 
415  if(f.HasFFAdjacency() && UpdateTopology)
416  {
417  // store information to preserve topology
418  int z1 = (z+1)%3;
419  int z2 = (z+2)%3;
420  FaceType *g1p = f.FFp(z1);
421  FaceType *g2p = f.FFp(z2);
422  int g1i = f.FFi(z1);
423  int g2i = f.FFi(z2);
424 
425  // g0 face topology is not affected by the swap
426 
427  if (g1p != &f)
428  {
429  g1p->FFi(g1i) = z2;
430  f.FFi(z2) = g1i;
431  }
432  else
433  {
434  f.FFi(z2) = z2;
435  }
436 
437  if (g2p != &f)
438  {
439  g2p->FFi(g2i) = z1;
440  f.FFi(z1) = g2i;
441  }
442  else
443  {
444  f.FFi(z1) = z1;
445  }
446 
447  // finalize swap
448  f.FFp(z1) = g2p;
449  f.FFp(z2) = g1p;
450  }
451 }
452 
457 template <class FaceType>
458 bool FFLinkCondition(FaceType &f, const int z)
459 {
460  typedef typename FaceType::VertexType VertexType;
461  typedef typename vcg::face::Pos< FaceType > PosType;
462 
463  VertexType *v0=f.V0(z);
464  VertexType *v1=f.V1(z);
465 
466  PosType p0(&f,v0);
467  PosType p1(&f,v1);
468  std::vector<VertexType *>v0Vec;
469  std::vector<VertexType *>v1Vec;
470  VVOrderedStarFF(p0,v0Vec);
471  VVOrderedStarFF(p1,v1Vec);
472  std::set<VertexType *> v0set;
473  v0set.insert(v0Vec.begin(),v0Vec.end());
474  assert(v0set.size() == v0Vec.size());
475  int cnt =0;
476  for(size_t i=0;i<v1Vec.size();++i)
477  if(v0set.find(v1Vec[i]) != v0set.end())
478  cnt++;
479 
480  if(face::IsBorder(f,z) && (cnt==1)) return true;
481  if(!face::IsBorder(f,z) && (cnt==2)) return true;
482  //assert(0);
483  return false;
484 }
485 
502 template <class MeshType>
503 void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
504 {
505  typedef typename MeshType::FaceType FaceType;
506  typedef typename MeshType::VertexType VertexType;
507  typedef typename vcg::face::Pos< FaceType > PosType;
508  FaceType *f0 = &f;
509  int z0=z;
510  FaceType *f1 = f.FFp(z);
511  int z1=f.FFi(z);
512 
513  VertexType *delV=f.V0(z);
514  VertexType *surV=f.V1(z);
515 
516  // Collect faces that have to be updated
517  PosType delPos(f0,delV);
518  std::vector<PosType> faceToBeChanged;
519  VFOrderedStarFF(delPos,faceToBeChanged);
520 
521  // Topology Stitching
522  FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
523  int i01=-1, i02=-1, i11=-1, i12=-1;
524  // Note that the faux bit is preserved only if both of the edges to be stiched are faux.
525  bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
526  bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
527 
528  if(!face::IsBorder(*f0,(z0+1)%3)) { f01 = f0->FFp((z0+1)%3); i01=f0->FFi((z0+1)%3); FFDetachManifold(*f0,(z0+1)%3);}
529  if(!face::IsBorder(*f0,(z0+2)%3)) { f02 = f0->FFp((z0+2)%3); i02=f0->FFi((z0+2)%3); FFDetachManifold(*f0,(z0+2)%3);}
530  if(!face::IsBorder(*f1,(z1+1)%3)) { f11 = f1->FFp((z1+1)%3); i11=f1->FFi((z1+1)%3); FFDetachManifold(*f1,(z1+1)%3);}
531  if(!face::IsBorder(*f1,(z1+2)%3)) { f12 = f1->FFp((z1+2)%3); i12=f1->FFi((z1+2)%3); FFDetachManifold(*f1,(z1+2)%3);}
532 
533  // Final Pass to update the vertex ptrs in all the involved faces
534  for(size_t i=0;i<faceToBeChanged.size();++i) {
535  assert(faceToBeChanged[i].V() == delV);
536  faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
537  }
538 
539  if(f01 && f02)
540  {
541  FFAttachManifold(f01,i01,f02,i02);
542  if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
543  }
544  if(f11 && f12) {
545  FFAttachManifold(f11,i11,f12,i12);
546  if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
547  }
548  tri::Allocator<MeshType>::DeleteFace(m,*f0);
549  if(f1!=f0) tri::Allocator<MeshType>::DeleteFace(m,*f1);
550  tri::Allocator<MeshType>::DeleteVertex(m,*delV);
551 }
552 
572 template <class FaceType>
573 bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
574 {
575  typedef typename FaceType::VertexType VertexType;
576  typedef typename VertexType::CoordType CoordType;
577 
578  VertexType *OldDiag0 = f.V0(z);
579  VertexType *OldDiag1 = f.V1(z);
580 
581  VertexType *NewDiag0 = f.V2(z);
582  VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
583 
584  assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
585 
586  CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
587  CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
588  CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
589  CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
590  if(AngleN(oldN0,newN0) > angleRad) return false;
591  if(AngleN(oldN0,newN1) > angleRad) return false;
592  if(AngleN(oldN1,newN0) > angleRad) return false;
593  if(AngleN(oldN1,newN1) > angleRad) return false;
594 
595  return true;
596 }
597 
604 template <class FaceType>
605 bool CheckFlipEdge(FaceType &f, int z)
606 {
607  typedef typename FaceType::VertexType VertexType;
608  typedef typename vcg::face::Pos< FaceType > PosType;
609 
610  if (z<0 || z>2) return false;
611 
612  // boundary edges cannot be flipped
613  if (face::IsBorder(f, z)) return false;
614 
615  FaceType *g = f.FFp(z);
616  int w = f.FFi(z);
617 
618  // check if the vertices of the edge are the same
619  // e.g. the mesh has to be well oriented
620  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
621  return false;
622 
623  // check if the flipped edge is already present in the mesh
624  // f_v2 and g_v2 are the vertices of the new edge
625  VertexType *f_v2 = f.V2(z);
626  VertexType *g_v2 = g->V2(w);
627 
628  // just a sanity check. If this happens the mesh is not manifold.
629  if (f_v2 == g_v2) return false;
630 
631  // Now walk around f_v2, one of the two vertexes of the new edge
632  // and check that it does not already exists.
633 
634  PosType pos(&f, (z+2)%3, f_v2);
635  PosType startPos=pos;
636  do
637  {
638  pos.NextE();
639  if (g_v2 == pos.VFlip())
640  return false;
641  }
642  while (pos != startPos);
643 
644  return true;
645 }
646 
647 template <class FaceType>
648 bool checkFlipEdgeNotManifold (FaceType &f, const int z)
649 {
650  typedef typename FaceType::VertexType VertexType;
651  typedef typename vcg::face::Pos< FaceType > PosType;
652  if (z<0 || z>2) return false;
653 
654  // boundary edges cannot be flipped
655  if (vcg::face::IsBorder(f, z)) return false;
656 
657  FaceType *g = f.FFp(z);
658  int w = f.FFi(z);
659 
660  // check if the vertices of the edge are the same
661  // e.g. the mesh has to be well oriented
662  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
663  return false;
664 
665  // check if the flipped edge is already present in the mesh
666  // f_v2 and g_v2 are the vertices of the new edge
667  VertexType *f_v2 = f.V2(z);
668  VertexType *g_v2 = g->V2(w);
669 
670  PosType pos(&f, (z+2)%3, f_v2);
671  PosType startPos=pos;
672  do
673  {
674  pos.FlipE();
675  pos.NextF();
676 // if (g_v2 == pos.F()->V((pos.E()+1) % 3))
677  if (g_v2 == pos.VFlip())
678  return false;
679  }
680  while (pos != startPos);
681 
682  return true;
683 
684 }
685 
710 template <class FaceType>
711 void FlipEdge(FaceType &f, const int z)
712 {
713  assert(z>=0);
714  assert(z<3);
715  assert( !IsBorder(f,z) );
716  assert( face::IsManifold<FaceType>(f, z));
717 
718  FaceType *g = f.FFp(z); // The other face
719  int w = f.FFi(z); // and other side
720 
721  assert( g->V0(w) == f.V1(z) );
722  assert( g->V1(w) == f.V0(z) );
723  assert( g->V2(w) != f.V0(z) );
724  assert( g->V2(w) != f.V1(z) );
725  assert( g->V2(w) != f.V2(z) );
726 
727  int fi1 = f.FFi(f.Next(z));
728  FaceType* fp1 = f.FFp(f.Next(z));
729 
730  int gi1 = g->FFi(g->Next(w));
731  FaceType* gp1 = g->FFp(g->Next(w));
732 
733 // FaceType* fp2 = f.FFp(f.Next(z));
734 
735 
736  f.V1(z) = g->V2(w);
737  g->V1(w) = f.V2(z);
738 
739  //topology update
740 
741 
742  f.FFp(z) = g->FFp((w+1)%3);
743  f.FFi(z) = g->FFi((w+1)%3);
744  g->FFp(w) = f.FFp((z+1)%3);
745  g->FFi(w) = f.FFi((z+1)%3);
746 
747  f.FFp((z+1)%3) = g;
748  f.FFi((z+1)%3) = (w+1)%3;
749  g->FFp((w+1)%3) = &f;
750  g->FFi((w+1)%3) = (z+1)%3;
751 
752  if(f.FFp(z)==g)
753  {
754  f.FFp(z) = &f;
755  f.FFi(z) = z;
756  }
757  else
758  {
759  f.FFp(z)->FFp( f.FFi(z) ) = &f;
760  f.FFp(z)->FFi( f.FFi(z) ) = z;
761  }
762  if(g->FFp(w)==&f)
763  {
764  g->FFp(w)=g;
765  g->FFi(w)=w;
766  }
767  else
768  {
769  g->FFp(w)->FFp( g->FFi(w) ) = g;
770  g->FFp(w)->FFi( g->FFi(w) ) = w;
771  }
772 
773 }
774 
798 template <class FaceType>
799 void FlipEdgeNotManifold(FaceType &f, const int z)
800 {
801  assert(z>=0);
802  assert(z<3);
803  assert( !IsBorder(f,z) );
804  assert( face::IsManifold<FaceType>(f, z));
805 
806  FaceType *g = f.FFp(z); // The other face
807  int w = f.FFi(z); // and other side
808 
809  assert( g->V0(w) == f.V1(z) );
810  assert( g->V1(w) == f.V0(z) );
811  assert( g->V2(w) != f.V0(z) );
812  assert( g->V2(w) != f.V1(z) );
813  assert( g->V2(w) != f.V2(z) );
814 
815  int fi1 = f.FFi(f.Next(z));
816  FaceType* fp1 = f.FFp(f.Next(z));
817 
818  int gi1 = g->FFi(g->Next(w));
819  FaceType* gp1 = g->FFp(g->Next(w));
820 
821 
822  FFDetach(f, z);
823  if (!IsBorder(f, (z+1)%3))
824  FFDetach(f, (z+1)%3);
825  if (!IsBorder(*g, (w+1)%3))
826  FFDetach(*g, (w+1)%3);
827 
828  f.V1(z) = g->V2(w);
829  g->V1(w) = f.V2(z);
830 
831  //topology update
832  FaceType* ftmp = &f;
833 
834  if (gp1 != g)
835  FFAttach(ftmp, z, gp1, gi1);
836  if (fp1 != &f)
837  FFAttach(g, w, fp1, fi1);
838 
839  FFAttachManifold(ftmp, (z+1)%3, g, (w+1)%3);
840 }
841 
842 template <class FaceType>
843 void TriSplit(FaceType *fToSplit, FaceType *newf0, FaceType *newf1, typename FaceType::VertexType *newVert)
844 {
845  typedef typename FaceType::VertexType VertexType;
846 
847  VertexType *vp0 = fToSplit->V(0);
848  VertexType *vp1 = fToSplit->V(1);
849  VertexType *vp2 = fToSplit->V(2);
850 
851  fToSplit->V(0) = vp0; fToSplit->V(1) = vp1; fToSplit->V(2) = newVert;
852  newf0->V(0) = vp1; newf0->V(1) = vp2; newf0->V(2) = newVert;
853  newf1->V(0) = vp2; newf1->V(1) = vp0; newf1->V(2) = newVert;
854 }
855 
856 
857 
858 template <class FaceType>
859 void VFDetach(FaceType & f)
860 {
861  VFDetach(f,0);
862  VFDetach(f,1);
863  VFDetach(f,2);
864 }
865 
866 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z,
867 // NOTA funziona SOLO per la topologia VF!!!
868 // usata nelle classi di collapse
869 template <class FaceType>
870 void VFDetach(FaceType & f, int z)
871 {
872  if(f.V(z)->VFp()==&f ) //if it is the first face detach from the begin
873  {
874  int fz = f.V(z)->VFi();
875  f.V(z)->VFp() = f.VFp(fz);
876  f.V(z)->VFi() = f.VFi(fz);
877  }
878  else // scan the list of faces in order to finde the current face f to be detached
879  {
880  VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
881  VFIterator<FaceType> y;
882 
883  for(;;)
884  {
885  y = x;
886  ++x;
887  assert(x.f!=0);
888  if(x.f==&f) // found!
889  {
890  y.f->VFp(y.z) = f.VFp(z);
891  y.f->VFi(y.z) = f.VFi(z);
892  break;
893  }
894  }
895  }
896 }
897 
899 template <class FaceType>
900 void VFAppend(FaceType* & f, int z)
901 {
902  typename FaceType::VertexType *v = f->V(z);
903  if (v->VFp()!=0)
904  {
905  FaceType *f0=v->VFp();
906  int z0=v->VFi();
907  //append
908  f->VFp(z)=f0;
909  f->VFi(z)=z0;
910  }
911  v->VFp()=f;
912  v->VFi()=z;
913 }
914 
923 template <class FaceType>
924 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
925 {
926  typedef typename FaceType::VertexType* VertexPointer;
927  starVec.clear();
928  starVec.reserve(16);
929  face::VFIterator<FaceType> vfi(vp);
930  while(!vfi.End())
931  {
932  const int vn = vfi.F()->VN();
933  starVec.push_back(vfi.F()->V1(vfi.I()));
934  starVec.push_back(vfi.F()->V((vfi.I()+vn-1)%vn));
935  ++vfi;
936  }
937 
938  std::sort(starVec.begin(),starVec.end());
939  typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
940  starVec.resize(new_end-starVec.begin());
941 }
942 
951 template <class FaceType>
952 void VVExtendedStarVF(typename FaceType::VertexType* vp,
953  const int num_step,
954  std::vector<typename FaceType::VertexType *> &vertVec)
955  {
956  typedef typename FaceType::VertexType VertexType;
958  vertVec.clear();
959  vcg::face::VVStarVF<FaceType>(vp,vertVec);
962  for (int step=0;step<num_step-1;step++)
963  {
964  std::vector<VertexType *> toAdd;
965  for (unsigned int i=0;i<vertVec.size();i++)
966  {
967  std::vector<VertexType *> Vtemp;
968  vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
969  toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
970  }
971  vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
972  std::sort(vertVec.begin(),vertVec.end());
973  typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
974  int dist=distance(vertVec.begin(),new_end);
975  vertVec.resize(dist);
976  }
977  }
978 
986 template <class FaceType>
987 void VFStarVF( typename FaceType::VertexType* vp,
988  std::vector<FaceType *> &faceVec,
989  std::vector<int> &indexes)
990 {
991  faceVec.clear();
992  indexes.clear();
993  faceVec.reserve(16);
994  indexes.reserve(16);
995  face::VFIterator<FaceType> vfi(vp);
996  while(!vfi.End())
997  {
998  faceVec.push_back(vfi.F());
999  indexes.push_back(vfi.I());
1000  ++vfi;
1001  }
1002 }
1003 
1004 
1013 template <class FaceType>
1014 void EFStarFF( FaceType* fp, int ei,
1015  std::vector<FaceType *> &faceVec,
1016  std::vector<int> &indVed)
1017 {
1018  assert(fp->FFp(ei)!=0);
1019  faceVec.clear();
1020  indVed.clear();
1021  FaceType* fpit=fp;
1022  int eit=ei;
1023  do
1024  {
1025  faceVec.push_back(fpit);
1026  indVed.push_back(eit);
1027  FaceType *new_fpit = fpit->FFp(eit);
1028  int new_eit = fpit->FFi(eit);
1029  fpit=new_fpit;
1030  eit=new_eit;
1031  } while(fpit != fp);
1032 }
1033 
1034 
1035  /* Compute the set of faces adjacent to a given face using FF adjacency.
1036  * The set is faces is extended of a given number of step
1037  * \param fp pointer to the face whose star has to be computed.
1038  * \param num_step the number of step to extend the star
1039  * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
1040  */
1041  template <class FaceType>
1042  static void FFExtendedStarFF(FaceType *fp,
1043  const int num_step,
1044  std::vector<FaceType*> &faceVec)
1045  {
1047  faceVec.push_back(fp);
1050  for (int step=0;step<num_step;step++)
1051  {
1052  std::vector<FaceType*> toAdd;
1053  for (unsigned int i=0;i<faceVec.size();i++)
1054  {
1055  FaceType *f=faceVec[i];
1056  for (int k=0;k<3;k++)
1057  {
1058  FaceType *f1=f->FFp(k);
1059  if (f1==f)continue;
1060  toAdd.push_back(f1);
1061  }
1062  }
1063  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1064  std::sort(faceVec.begin(),faceVec.end());
1065  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1066  int dist=distance(faceVec.begin(),new_end);
1067  faceVec.resize(dist);
1068  }
1069  }
1070 
1079 template <class FaceType>
1080 void VFExtendedStarVF(typename FaceType::VertexType* vp,
1081  const int num_step,
1082  std::vector<FaceType*> &faceVec)
1083  {
1085  faceVec.clear();
1086  std::vector<int> indexes;
1087  vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
1090  for (int step=0;step<num_step;step++)
1091  {
1092  std::vector<FaceType*> toAdd;
1093  for (unsigned int i=0;i<faceVec.size();i++)
1094  {
1095  FaceType *f=faceVec[i];
1096  for (int k=0;k<3;k++)
1097  {
1098  FaceType *f1=f->FFp(k);
1099  if (f1==f)continue;
1100  toAdd.push_back(f1);
1101  }
1102  }
1103  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1104  std::sort(faceVec.begin(),faceVec.end());
1105  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1106  int dist=distance(faceVec.begin(),new_end);
1107  faceVec.resize(dist);
1108  }
1109  }
1110 
1118 template <class FaceType>
1119 void VVOrderedStarFF(Pos<FaceType> &startPos,
1120  std::vector<typename FaceType::VertexType *> &vertexVec)
1121 {
1122  vertexVec.clear();
1123  vertexVec.reserve(16);
1124  std::vector<Pos<FaceType> > posVec;
1125  VFOrderedStarFF(startPos,posVec);
1126  for(size_t i=0;i<posVec.size();++i)
1127  vertexVec.push_back(posVec[i].VFlip());
1128 }
1129 
1137 template <class FaceType>
1138 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1139  std::vector<Pos<FaceType> > &posVec)
1140 {
1141  posVec.clear();
1142  posVec.reserve(16);
1143  bool foundBorder=false;
1144  size_t firstBorderInd;
1145  Pos<FaceType> curPos=startPos;
1146  do
1147  {
1148  assert(curPos.IsManifold());
1149  if(curPos.IsBorder() && !foundBorder) {
1150  foundBorder=true;
1151  firstBorderInd = posVec.size();
1152  }
1153  posVec.push_back(curPos);
1154  curPos.FlipF();
1155  curPos.FlipE();
1156  } while(curPos!=startPos);
1157  // if we found a border we visited each face exactly twice,
1158  // and we have to extract the border-to-border pos sequence
1159  if(foundBorder)
1160  {
1161  size_t halfSize=posVec.size()/2;
1162  assert((posVec.size()%2)==0);
1163  posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1164  posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1165  assert(posVec.size()==halfSize);
1166  }
1167 }
1168 
1178 template <class FaceType>
1179 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1180  std::vector<FaceType*> &faceVec,
1181  std::vector<int> &edgeVec)
1182 {
1183  std::vector<Pos<FaceType> > posVec;
1184  VFOrderedStarFF(startPos,posVec);
1185  faceVec.clear();
1186  edgeVec.clear();
1187  faceVec.reserve(16);
1188  edgeVec.reserve(16);
1189  for(size_t i=0;i<posVec.size();++i)
1190  {
1191  faceVec.push_back(posVec[i].F());
1192  edgeVec.push_back(posVec[i].E());
1193  }
1194 }
1195 
1202 template <class FaceType>
1203 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
1204 {
1205  assert((!f0->IsD())&&(!f1->IsD()));
1206  for (int i=0;i<3;i++)
1207  if (f0->FFp(i)==f1)
1208  {
1209  if((i0!=0) && (i1!=0)) {
1210  *i0=i;
1211  *i1=f0->FFi(i);
1212  }
1213  return true;
1214  }
1215  return false;
1216 }
1217 
1223 template <class FaceType>
1224 int CountSharedVertex(FaceType *f0,FaceType *f1)
1225 {
1226  int sharedCnt=0;
1227  for (int i=0;i<3;i++)
1228  for (int j=0;j<3;j++)
1229  if (f0->V(i)==f1->V(j)) {
1230  sharedCnt++;
1231  }
1232  return sharedCnt;
1233 }
1234 
1241 template <class FaceType>
1242 bool FindSharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
1243 {
1244  for (i=0;i<3;i++)
1245  for (j=0;j<3;j++)
1246  if (f0->V(i)==f1->V(j)) return true;
1247 
1248  i=-1;j=-1;
1249  return false;
1250 }
1251 
1258 template <class FaceType>
1259 bool FindSharedEdge(FaceType *f0,FaceType *f1, int &i, int &j)
1260 {
1261  for (i=0;i<3;i++)
1262  for (j=0;j<3;j++)
1263  if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1264  ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1265  return true;
1266  i=-1;j=-1;
1267  return false;
1268 }
1269 
1276 template <class FaceType>
1277 bool FindSharedFaces(typename FaceType::VertexType *v0,
1278  typename FaceType::VertexType *v1,
1279  FaceType *&f0,
1280  FaceType *&f1,
1281  int &e0,
1282  int &e1)
1283 {
1284  std::vector<FaceType*> faces0;
1285  std::vector<FaceType*> faces1;
1286  std::vector<int> index0;
1287  std::vector<int> index1;
1288  VFStarVF<FaceType>(v0,faces0,index0);
1289  VFStarVF<FaceType>(v1,faces1,index1);
1291  std::sort(faces0.begin(),faces0.end());
1292  std::sort(faces1.begin(),faces1.end());
1293  std::vector<FaceType*> Intersection;
1294  std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1295  if (Intersection.size()<2)return false;
1296  assert(Intersection.size()==2);//otherwhise non manifoldess
1297  f0=Intersection[0];
1298  f1=Intersection[1];
1299  FindSharedEdge(f0,f1,e0,e1);
1301  if (f0->V(e0)!=v0)
1302  {
1303  std::swap(f0,f1);
1304  std::swap(e0,e1);
1305  }
1306  return true;
1307 }
1308 
1310 } // end namespace
1311 } // end namespace
1312 
1313 #endif
1314 
Generated on Fri Jan 24 2020 09:00:03 for VCG Library by   doxygen 1.8.2