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 namespace vcg {
28 namespace face {
31 
36 template <class FaceType>
37 inline bool IsManifold( FaceType const & f, const int j )
38 {
39  assert(f.cFFp(j) != 0); // never try to use this on uncomputed topology
40  if(FaceType::HasFFAdjacency())
41  return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
42  else
43  return true;
44 }
45 
50 template <class FaceType>
51 inline bool IsBorder(FaceType const & f, const int j )
52 {
53  if(FaceType::HasFFAdjacency())
54  return f.cFFp(j)==&f;
55  //return f.IsBorder(j);
56 
57  assert(0);
58  return true;
59 }
60 
79 template <class FaceType>
80 inline typename FaceType::ScalarType DihedralAngleRad(FaceType & f, const int i )
81 {
82  typedef typename FaceType::ScalarType ScalarType;
83  typedef typename FaceType::CoordType CoordType;
84  typedef typename FaceType::VertexType VertexType;
85 
86  FaceType *f0 = &f;
87  FaceType *f1 = f.FFp(i);
88  int i0=i;
89  int i1=f.FFi(i);
90  VertexType *vf0 = f0->V2(i0);
91  VertexType *vf1 = f1->V2(i1);
92 
93  CoordType n0 = TriangleNormal(*f0).Normalize();
94  CoordType n1 = TriangleNormal(*f1).Normalize();
95  ScalarType off0 = n0*vf0->P();
96  ScalarType off1 = n1*vf1->P();
97 
98  ScalarType dist01 = off0 - n0*vf1->P();
99  ScalarType dist10 = off1 - n1*vf0->P();
100 
101  // just to be sure use the sign of the largest in absolute value;
102  ScalarType sign;
103  if(fabs(dist01) > fabs(dist10)) sign = dist01;
104  else sign=dist10;
105 
106  ScalarType angleRad=AngleN(n0,n1);
107 
108  if(sign > 0 ) return angleRad;
109  else return -angleRad;
110 }
111 
113 template <class FaceType>
114 inline typename FaceType::ScalarType WedgeAngleRad(FaceType & f, const int i )
115 {
116  auto &P0=f.P(i);
117  auto &P1=f.P(f.Next(i));
118  auto &P2=f.P(f.Prev(i));
119  return vcg::Angle(P2 - P0,P1 - P0);
120 }
121 
123 template <class FaceType>
124 inline int BorderCount(FaceType const & f)
125 {
126  if(FaceType::HasFFAdjacency())
127  {
128  int t = 0;
129  if( IsBorder(f,0) ) ++t;
130  if( IsBorder(f,1) ) ++t;
131  if( IsBorder(f,2) ) ++t;
132  return t;
133  }
134  else return 3;
135 }
136 
137 
139 template <class FaceType>
140 inline int ComplexSize(FaceType & f, const int e)
141 {
142  if(FaceType::HasFFAdjacency())
143  {
144  if(face::IsBorder<FaceType>(f,e)) return 1;
145  if(face::IsManifold<FaceType>(f,e)) return 2;
146 
147  // Non manifold case
148  Pos< FaceType > fpos(&f,e);
149  int cnt=0;
150  do
151  {
152  fpos.NextF();
153  assert(!fpos.IsBorder());
154  assert(!fpos.IsManifold());
155  ++cnt;
156  }
157  while(fpos.f!=&f);
158  assert (cnt>2);
159  return cnt;
160  }
161  assert(0);
162  return 2;
163 }
164 
165 
172 template <class FaceType>
173 bool FFCorrectness(FaceType & f, const int e)
174 {
175  if(f.FFp(e)==0) return false; // Not computed or inconsistent topology
176 
177  if(f.FFp(e)==&f) // Border
178  {
179  if(f.FFi(e)==e) return true;
180  else return false;
181  }
182 
183  if(f.FFp(e)->FFp(f.FFi(e))==&f) // plain two manifold
184  {
185  if(f.FFp(e)->FFi(f.FFi(e))==e) return true;
186  else return false;
187  }
188 
189  // Non Manifold Case
190  // all the faces must be connected in a loop.
191 
192  Pos< FaceType > curFace(&f,e); // Build the half edge
193  int cnt=0;
194  do
195  {
196  if(curFace.IsManifold()) return false;
197  if(curFace.IsBorder()) return false;
198  curFace.NextF();
199  cnt++;
200  assert(cnt<100);
201  }
202  while ( curFace.f != &f);
203  return true;
204 }
205 
206 
214 template <class FaceType>
215 void FFDetachManifold(FaceType & f, const int e)
216 {
217  assert(FFCorrectness<FaceType>(f,e));
218  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
219  FaceType *ffp = f.FFp(e);
220  //int ffi=f.FFp(e);
221  int ffi=f.FFi(e);
222 
223  f.FFp(e)=&f;
224  f.FFi(e)=e;
225  ffp->FFp(ffi)=ffp;
226  ffp->FFi(ffi)=ffi;
227 
228  f.SetB(e);
229  f.ClearF(e);
230  ffp->SetB(ffi);
231  ffp->ClearF(ffi);
232 
233  assert(FFCorrectness<FaceType>(f,e));
234  assert(FFCorrectness<FaceType>(*ffp,ffi));
235 }
236 
244 template <class FaceType>
245 void FFDetach(FaceType & f, const int e)
246 {
247  assert(FFCorrectness<FaceType>(f,e));
248  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
249  int complexity=ComplexSize(f,e);
250  (void) complexity;
251  assert(complexity>0);
252 
253  Pos< FaceType > FirstFace(&f,e); // Build the half edge
254  Pos< FaceType > LastFace(&f,e); // Build the half edge
255  FirstFace.NextF();
256  LastFace.NextF();
257  int cnt=0;
258 
259  // then in case of non manifold face continue to advance LastFace
260  // until I find it become the one that
261  // preceed the face I want to erase
262 
263  while ( LastFace.f->FFp(LastFace.z) != &f)
264  {
265  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity);
266  assert(!LastFace.IsManifold()); // We enter in this loop only if we are on a non manifold edge
267  assert(!LastFace.IsBorder());
268  LastFace.NextF();
269  cnt++;
270  assert(cnt<100);
271  }
272 
273  assert(LastFace.f->FFp(LastFace.z)==&f);
274  assert(f.FFp(e)== FirstFace.f);
275 
276  // Now we link the last one to the first one, skipping the face to be detached;
277  LastFace.f->FFp(LastFace.z) = FirstFace.f;
278  LastFace.f->FFi(LastFace.z) = FirstFace.z;
279  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
280 
281  // At the end selfconnect the chosen edge to make a border.
282  f.FFp(e) = &f;
283  f.FFi(e) = e;
284  assert(ComplexSize(f,e)==1);
285 
286  assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
287  assert(FFCorrectness<FaceType>(f,e));
288 }
289 
290 
297 template <class FaceType>
298 void FFAttach(FaceType * &f, int z1, FaceType *&f2, int z2)
299 {
300  //typedef FEdgePosB< FACE_TYPE > ETYPE;
301  Pos< FaceType > EPB(f2,z2);
302  Pos< FaceType > TEPB;
303  TEPB = EPB;
304  EPB.NextF();
305  while( EPB.f != f2) //Alla fine del ciclo TEPB contiene la faccia che precede f2
306  {
307  TEPB = EPB;
308  EPB.NextF();
309  }
310  //Salvo i dati di f1 prima di sovrascrivere
311  FaceType *f1prec = f->FFp(z1);
312  int z1prec = f->FFi(z1);
313  //Aggiorno f1
314  f->FFp(z1) = TEPB.f->FFp(TEPB.z);
315  f->FFi(z1) = TEPB.f->FFi(TEPB.z);
316  //Aggiorno la faccia che precede f2
317  TEPB.f->FFp(TEPB.z) = f1prec;
318  TEPB.f->FFi(TEPB.z) = z1prec;
319 }
320 
328 template <class FaceType>
329 void FFAttachManifold(FaceType * &f1, int z1, FaceType *&f2, int z2)
330 {
331  assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
332  assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
333  assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
334  assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
335  f1->FFp(z1) = f2;
336  f1->FFi(z1) = z2;
337  f2->FFp(z2) = f1;
338  f2->FFi(z2) = z1;
339 }
340 
341 // This one should be called only on uniitialized faces.
342 template <class FaceType>
343 void FFSetBorder(FaceType * &f1, int z1)
344 {
345  assert(f1->FFp(z1)==0 || IsBorder(*f1,z1));
346 
347  f1->FFp(z1)=f1;
348  f1->FFi(z1)=z1;
349 }
350 
351 template <class FaceType>
352 void AssertAdj(FaceType & f)
353 {
354  (void)f;
355  assert(f.FFp(0)->FFp(f.FFi(0))==&f);
356  assert(f.FFp(1)->FFp(f.FFi(1))==&f);
357  assert(f.FFp(2)->FFp(f.FFi(2))==&f);
358 
359  assert(f.FFp(0)->FFi(f.FFi(0))==0);
360  assert(f.FFp(1)->FFi(f.FFi(1))==1);
361  assert(f.FFp(2)->FFi(f.FFi(2))==2);
362 }
363 
369 template <class FaceType>
370 bool CheckOrientation(FaceType &f, int z)
371 {
372  if (IsBorder(f, z))
373  return true;
374  else
375  {
376  FaceType *g = f.FFp(z);
377  int gi = f.FFi(z);
378  if (f.V0(z) == g->V1(gi))
379  return true;
380  else
381  return false;
382  }
383 }
384 
385 
390 template <class FaceType>
391 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
392 
393 template <class FaceType, bool UpdateTopology>
394 void SwapEdge(FaceType &f, const int z)
395 {
396  // swap V0(z) with V1(z)
397  std::swap(f.V0(z), f.V1(z));
398 
399  // Managemnt of faux edge information (edge z is not affected)
400  bool Faux1 = f.IsF((z+1)%3);
401  bool Faux2 = f.IsF((z+2)%3);
402  if(Faux1) f.SetF((z+2)%3); else f.ClearF((z+2)%3);
403  if(Faux2) f.SetF((z+1)%3); else f.ClearF((z+1)%3);
404 
405  if(f.HasFFAdjacency() && UpdateTopology)
406  {
407  // store information to preserve topology
408  int z1 = (z+1)%3;
409  int z2 = (z+2)%3;
410  FaceType *g1p = f.FFp(z1);
411  FaceType *g2p = f.FFp(z2);
412  int g1i = f.FFi(z1);
413  int g2i = f.FFi(z2);
414 
415  // g0 face topology is not affected by the swap
416 
417  if (g1p != &f)
418  {
419  g1p->FFi(g1i) = z2;
420  f.FFi(z2) = g1i;
421  }
422  else
423  {
424  f.FFi(z2) = z2;
425  }
426 
427  if (g2p != &f)
428  {
429  g2p->FFi(g2i) = z1;
430  f.FFi(z1) = g2i;
431  }
432  else
433  {
434  f.FFi(z1) = z1;
435  }
436 
437  // finalize swap
438  f.FFp(z1) = g2p;
439  f.FFp(z2) = g1p;
440  }
441 }
442 
447 template <class FaceType>
448 bool FFLinkCondition(FaceType &f, const int z)
449 {
450  typedef typename FaceType::VertexType VertexType;
451  typedef typename vcg::face::Pos< FaceType > PosType;
452 
453  VertexType *v0=f.V0(z);
454  VertexType *v1=f.V1(z);
455 
456  PosType p0(&f,v0);
457  PosType p1(&f,v1);
458  std::vector<VertexType *>v0Vec;
459  std::vector<VertexType *>v1Vec;
460  VVOrderedStarFF(p0,v0Vec);
461  VVOrderedStarFF(p1,v1Vec);
462  std::set<VertexType *> v0set;
463  v0set.insert(v0Vec.begin(),v0Vec.end());
464  assert(v0set.size() == v0Vec.size());
465  int cnt =0;
466  for(size_t i=0;i<v1Vec.size();++i)
467  if(v0set.find(v1Vec[i]) != v0set.end())
468  cnt++;
469 
470  if(face::IsBorder(f,z) && (cnt==1)) return true;
471  if(!face::IsBorder(f,z) && (cnt==2)) return true;
472  //assert(0);
473  return false;
474 }
475 
492 template <class MeshType>
493 void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
494 {
495  typedef typename MeshType::FaceType FaceType;
496  typedef typename MeshType::VertexType VertexType;
497  typedef typename vcg::face::Pos< FaceType > PosType;
498  FaceType *f0 = &f;
499  int z0=z;
500  FaceType *f1 = f.FFp(z);
501  int z1=f.FFi(z);
502 
503  VertexType *delV=f.V0(z);
504  VertexType *surV=f.V1(z);
505 
506  // Collect faces that have to be updated
507  PosType delPos(f0,delV);
508  std::vector<PosType> faceToBeChanged;
509  VFOrderedStarFF(delPos,faceToBeChanged);
510 
511  // Topology Stitching
512  FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
513  int i01=-1, i02=-1, i11=-1, i12=-1;
514  // Note that the faux bit is preserved only if both of the edges to be stiched are faux.
515  bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
516  bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
517 
518  if(!face::IsBorder(*f0,(z0+1)%3)) { f01 = f0->FFp((z0+1)%3); i01=f0->FFi((z0+1)%3); FFDetachManifold(*f0,(z0+1)%3);}
519  if(!face::IsBorder(*f0,(z0+2)%3)) { f02 = f0->FFp((z0+2)%3); i02=f0->FFi((z0+2)%3); FFDetachManifold(*f0,(z0+2)%3);}
520  if(!face::IsBorder(*f1,(z1+1)%3)) { f11 = f1->FFp((z1+1)%3); i11=f1->FFi((z1+1)%3); FFDetachManifold(*f1,(z1+1)%3);}
521  if(!face::IsBorder(*f1,(z1+2)%3)) { f12 = f1->FFp((z1+2)%3); i12=f1->FFi((z1+2)%3); FFDetachManifold(*f1,(z1+2)%3);}
522 
523  // Final Pass to update the vertex ptrs in all the involved faces
524  for(size_t i=0;i<faceToBeChanged.size();++i) {
525  assert(faceToBeChanged[i].V() == delV);
526  faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
527  }
528 
529  if(f01 && f02)
530  {
531  FFAttachManifold(f01,i01,f02,i02);
532  if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
533  }
534  if(f11 && f12) {
535  FFAttachManifold(f11,i11,f12,i12);
536  if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
537  }
538  tri::Allocator<MeshType>::DeleteFace(m,*f0);
539  if(f1!=f0) tri::Allocator<MeshType>::DeleteFace(m,*f1);
540  tri::Allocator<MeshType>::DeleteVertex(m,*delV);
541 }
542 
562 template <class FaceType>
563 bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
564 {
565  typedef typename FaceType::VertexType VertexType;
566  typedef typename VertexType::CoordType CoordType;
567 
568  VertexType *OldDiag0 = f.V0(z);
569  VertexType *OldDiag1 = f.V1(z);
570 
571  VertexType *NewDiag0 = f.V2(z);
572  VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
573 
574  assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
575 
576  CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
577  CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
578  CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
579  CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
580  if(AngleN(oldN0,newN0) > angleRad) return false;
581  if(AngleN(oldN0,newN1) > angleRad) return false;
582  if(AngleN(oldN1,newN0) > angleRad) return false;
583  if(AngleN(oldN1,newN1) > angleRad) return false;
584 
585  return true;
586 }
587 
594 template <class FaceType>
595 bool CheckFlipEdge(FaceType &f, int z)
596 {
597  typedef typename FaceType::VertexType VertexType;
598  typedef typename vcg::face::Pos< FaceType > PosType;
599 
600  if (z<0 || z>2) return false;
601 
602  // boundary edges cannot be flipped
603  if (face::IsBorder(f, z)) return false;
604 
605  FaceType *g = f.FFp(z);
606  int w = f.FFi(z);
607 
608  // check if the vertices of the edge are the same
609  // e.g. the mesh has to be well oriented
610  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
611  return false;
612 
613  // check if the flipped edge is already present in the mesh
614  // f_v2 and g_v2 are the vertices of the new edge
615  VertexType *f_v2 = f.V2(z);
616  VertexType *g_v2 = g->V2(w);
617 
618  // just a sanity check. If this happens the mesh is not manifold.
619  if (f_v2 == g_v2) return false;
620 
621  // Now walk around f_v2, one of the two vertexes of the new edge
622  // and check that it does not already exists.
623 
624  PosType pos(&f, (z+2)%3, f_v2);
625  PosType startPos=pos;
626  do
627  {
628  pos.NextE();
629  if (g_v2 == pos.VFlip())
630  return false;
631  }
632  while (pos != startPos);
633 
634  return true;
635 }
636 
661 template <class FaceType>
662 void FlipEdge(FaceType &f, const int z)
663 {
664  assert(z>=0);
665  assert(z<3);
666  assert( !IsBorder(f,z) );
667  assert( face::IsManifold<FaceType>(f, z));
668 
669  FaceType *g = f.FFp(z); // The other face
670  int w = f.FFi(z); // and other side
671 
672  assert( g->V0(w) == f.V1(z) );
673  assert( g->V1(w) == f.V0(z) );
674  assert( g->V2(w) != f.V0(z) );
675  assert( g->V2(w) != f.V1(z) );
676  assert( g->V2(w) != f.V2(z) );
677 
678  f.V1(z) = g->V2(w);
679  g->V1(w) = f.V2(z);
680 
681  f.FFp(z) = g->FFp((w+1)%3);
682  f.FFi(z) = g->FFi((w+1)%3);
683  g->FFp(w) = f.FFp((z+1)%3);
684  g->FFi(w) = f.FFi((z+1)%3);
685  f.FFp((z+1)%3) = g;
686  f.FFi((z+1)%3) = (w+1)%3;
687  g->FFp((w+1)%3) = &f;
688  g->FFi((w+1)%3) = (z+1)%3;
689 
690  if(f.FFp(z)==g)
691  {
692  f.FFp(z) = &f;
693  f.FFi(z) = z;
694  }
695  else
696  {
697  f.FFp(z)->FFp( f.FFi(z) ) = &f;
698  f.FFp(z)->FFi( f.FFi(z) ) = z;
699  }
700  if(g->FFp(w)==&f)
701  {
702  g->FFp(w)=g;
703  g->FFi(w)=w;
704  }
705  else
706  {
707  g->FFp(w)->FFp( g->FFi(w) ) = g;
708  g->FFp(w)->FFi( g->FFi(w) ) = w;
709  }
710 
711 }
712 
713 template <class FaceType>
714 void TriSplit(FaceType *fToSplit, FaceType *newf0, FaceType *newf1, typename FaceType::VertexType *newVert)
715 {
716  typedef typename FaceType::VertexType VertexType;
717 
718  VertexType *vp0 = fToSplit->V(0);
719  VertexType *vp1 = fToSplit->V(1);
720  VertexType *vp2 = fToSplit->V(2);
721 
722  fToSplit->V(0) = vp0; fToSplit->V(1) = vp1; fToSplit->V(2) = newVert;
723  newf0->V(0) = vp1; newf0->V(1) = vp2; newf0->V(2) = newVert;
724  newf1->V(0) = vp2; newf1->V(1) = vp0; newf1->V(2) = newVert;
725 }
726 
727 
728 
729 template <class FaceType>
730 void VFDetach(FaceType & f)
731 {
732  VFDetach(f,0);
733  VFDetach(f,1);
734  VFDetach(f,2);
735 }
736 
737 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z,
738 // NOTA funziona SOLO per la topologia VF!!!
739 // usata nelle classi di collapse
740 template <class FaceType>
741 void VFDetach(FaceType & f, int z)
742 {
743  if(f.V(z)->VFp()==&f ) //if it is the first face detach from the begin
744  {
745  int fz = f.V(z)->VFi();
746  f.V(z)->VFp() = f.VFp(fz);
747  f.V(z)->VFi() = f.VFi(fz);
748  }
749  else // scan the list of faces in order to finde the current face f to be detached
750  {
751  VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
752  VFIterator<FaceType> y;
753 
754  for(;;)
755  {
756  y = x;
757  ++x;
758  assert(x.f!=0);
759  if(x.f==&f) // found!
760  {
761  y.f->VFp(y.z) = f.VFp(z);
762  y.f->VFi(y.z) = f.VFi(z);
763  break;
764  }
765  }
766  }
767 }
768 
770 template <class FaceType>
771 void VFAppend(FaceType* & f, int z)
772 {
773  typename FaceType::VertexType *v = f->V(z);
774  if (v->VFp()!=0)
775  {
776  FaceType *f0=v->VFp();
777  int z0=v->VFi();
778  //append
779  f->VFp(z)=f0;
780  f->VFi(z)=z0;
781  }
782  v->VFp()=f;
783  v->VFi()=z;
784 }
785 
794 template <class FaceType>
795 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
796 {
797  typedef typename FaceType::VertexType* VertexPointer;
798  starVec.clear();
799  face::VFIterator<FaceType> vfi(vp);
800  while(!vfi.End())
801  {
802  const int vn = vfi.F()->VN();
803  starVec.push_back(vfi.F()->V1(vfi.I()));
804  starVec.push_back(vfi.F()->V((vfi.I()+vn-1)%vn));
805  ++vfi;
806  }
807 
808  std::sort(starVec.begin(),starVec.end());
809  typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
810  starVec.resize(new_end-starVec.begin());
811 }
812 
821 template <class FaceType>
822 void VVExtendedStarVF(typename FaceType::VertexType* vp,
823  const int num_step,
824  std::vector<typename FaceType::VertexType *> &vertVec)
825  {
826  typedef typename FaceType::VertexType VertexType;
828  vertVec.clear();
829  vcg::face::VVStarVF<FaceType>(vp,vertVec);
832  for (int step=0;step<num_step-1;step++)
833  {
834  std::vector<VertexType *> toAdd;
835  for (unsigned int i=0;i<vertVec.size();i++)
836  {
837  std::vector<VertexType *> Vtemp;
838  vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
839  toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
840  }
841  vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
842  std::sort(vertVec.begin(),vertVec.end());
843  typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
844  int dist=distance(vertVec.begin(),new_end);
845  vertVec.resize(dist);
846  }
847  }
848 
856 template <class FaceType>
857 void VFStarVF( typename FaceType::VertexType* vp,
858  std::vector<FaceType *> &faceVec,
859  std::vector<int> &indexes)
860 {
861  faceVec.clear();
862  indexes.clear();
863  face::VFIterator<FaceType> vfi(vp);
864  while(!vfi.End())
865  {
866  faceVec.push_back(vfi.F());
867  indexes.push_back(vfi.I());
868  ++vfi;
869  }
870 }
871 
872 
881 template <class FaceType>
882 void EFStarFF( FaceType* fp, int ei,
883  std::vector<FaceType *> &faceVec,
884  std::vector<int> &indVed)
885 {
886  assert(fp->FFp(ei)!=0);
887  faceVec.clear();
888  indVed.clear();
889  FaceType* fpit=fp;
890  int eit=ei;
891  do
892  {
893  faceVec.push_back(fpit);
894  indVed.push_back(eit);
895  FaceType *new_fpit = fpit->FFp(eit);
896  int new_eit = fpit->FFi(eit);
897  fpit=new_fpit;
898  eit=new_eit;
899  } while(fpit != fp);
900 }
901 
902 
903  /* Compute the set of faces adjacent to a given face using FF adjacency.
904  * The set is faces is extended of a given number of step
905  * \param fp pointer to the face whose star has to be computed.
906  * \param num_step the number of step to extend the star
907  * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
908  */
909  template <class FaceType>
910  static void FFExtendedStarFF(FaceType *fp,
911  const int num_step,
912  std::vector<FaceType*> &faceVec)
913  {
915  faceVec.push_back(fp);
918  for (int step=0;step<num_step;step++)
919  {
920  std::vector<FaceType*> toAdd;
921  for (unsigned int i=0;i<faceVec.size();i++)
922  {
923  FaceType *f=faceVec[i];
924  for (int k=0;k<3;k++)
925  {
926  FaceType *f1=f->FFp(k);
927  if (f1==f)continue;
928  toAdd.push_back(f1);
929  }
930  }
931  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
932  std::sort(faceVec.begin(),faceVec.end());
933  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
934  int dist=distance(faceVec.begin(),new_end);
935  faceVec.resize(dist);
936  }
937  }
938 
947 template <class FaceType>
948 void VFExtendedStarVF(typename FaceType::VertexType* vp,
949  const int num_step,
950  std::vector<FaceType*> &faceVec)
951  {
953  faceVec.clear();
954  std::vector<int> indexes;
955  vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
958  for (int step=0;step<num_step;step++)
959  {
960  std::vector<FaceType*> toAdd;
961  for (unsigned int i=0;i<faceVec.size();i++)
962  {
963  FaceType *f=faceVec[i];
964  for (int k=0;k<3;k++)
965  {
966  FaceType *f1=f->FFp(k);
967  if (f1==f)continue;
968  toAdd.push_back(f1);
969  }
970  }
971  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
972  std::sort(faceVec.begin(),faceVec.end());
973  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
974  int dist=distance(faceVec.begin(),new_end);
975  faceVec.resize(dist);
976  }
977  }
978 
986 template <class FaceType>
987 void VVOrderedStarFF(Pos<FaceType> &startPos,
988  std::vector<typename FaceType::VertexType *> &vertexVec)
989 {
990  vertexVec.clear();
991  std::vector<Pos<FaceType> > posVec;
992  VFOrderedStarFF(startPos,posVec);
993  for(size_t i=0;i<posVec.size();++i)
994  vertexVec.push_back(posVec[i].VFlip());
995 }
996 
1004 template <class FaceType>
1005 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1006  std::vector<Pos<FaceType> > &posVec)
1007 {
1008  posVec.clear();
1009  bool foundBorder=false;
1010  size_t firstBorderInd;
1011  Pos<FaceType> curPos=startPos;
1012  do
1013  {
1014  assert(curPos.IsManifold());
1015  if(curPos.IsBorder() && !foundBorder) {
1016  foundBorder=true;
1017  firstBorderInd = posVec.size();
1018  }
1019  posVec.push_back(curPos);
1020  curPos.FlipF();
1021  curPos.FlipE();
1022  } while(curPos!=startPos);
1023  // if we found a border we visited each face exactly twice,
1024  // and we have to extract the border-to-border pos sequence
1025  if(foundBorder)
1026  {
1027  size_t halfSize=posVec.size()/2;
1028  assert((posVec.size()%2)==0);
1029  posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1030  posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1031  assert(posVec.size()==halfSize);
1032  }
1033 }
1034 
1044 template <class FaceType>
1045 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1046  std::vector<FaceType*> &faceVec,
1047  std::vector<int> &edgeVec)
1048 {
1049  std::vector<Pos<FaceType> > posVec;
1050  VFOrderedStarFF(startPos,posVec);
1051  faceVec.clear();
1052  edgeVec.clear();
1053  for(size_t i=0;i<posVec.size();++i)
1054  {
1055  faceVec.push_back(posVec[i].F());
1056  edgeVec.push_back(posVec[i].E());
1057  }
1058 }
1059 
1066 template <class FaceType>
1067 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
1068 {
1069  assert((!f0->IsD())&&(!f1->IsD()));
1070  for (int i=0;i<3;i++)
1071  if (f0->FFp(i)==f1)
1072  {
1073  if((i0!=0) && (i1!=0)) {
1074  *i0=i;
1075  *i1=f0->FFi(i);
1076  }
1077  return true;
1078  }
1079  return false;
1080 }
1081 
1087 template <class FaceType>
1088 int CountSharedVertex(FaceType *f0,FaceType *f1)
1089 {
1090  int sharedCnt=0;
1091  for (int i=0;i<3;i++)
1092  for (int j=0;j<3;j++)
1093  if (f0->V(i)==f1->V(j)) {
1094  sharedCnt++;
1095  }
1096  return sharedCnt;
1097 }
1098 
1105 template <class FaceType>
1106 bool FindSharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
1107 {
1108  for (i=0;i<3;i++)
1109  for (j=0;j<3;j++)
1110  if (f0->V(i)==f1->V(j)) return true;
1111 
1112  i=-1;j=-1;
1113  return false;
1114 }
1115 
1122 template <class FaceType>
1123 bool FindSharedEdge(FaceType *f0,FaceType *f1, int &i, int &j)
1124 {
1125  for (i=0;i<3;i++)
1126  for (j=0;j<3;j++)
1127  if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1128  ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1129  return true;
1130  i=-1;j=-1;
1131  return false;
1132 }
1133 
1140 template <class FaceType>
1141 bool FindSharedFaces(typename FaceType::VertexType *v0,
1142  typename FaceType::VertexType *v1,
1143  FaceType *&f0,
1144  FaceType *&f1,
1145  int &e0,
1146  int &e1)
1147 {
1148  std::vector<FaceType*> faces0;
1149  std::vector<FaceType*> faces1;
1150  std::vector<int> index0;
1151  std::vector<int> index1;
1152  VFStarVF<FaceType>(v0,faces0,index0);
1153  VFStarVF<FaceType>(v1,faces1,index1);
1155  std::sort(faces0.begin(),faces0.end());
1156  std::sort(faces1.begin(),faces1.end());
1157  std::vector<FaceType*> Intersection;
1158  std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1159  if (Intersection.size()<2)return false;
1160  assert(Intersection.size()==2);//otherwhise non manifoldess
1161  f0=Intersection[0];
1162  f1=Intersection[1];
1163  FindSharedEdge(f0,f1,e0,e1);
1165  if (f0->V(e0)!=v0)
1166  {
1167  std::swap(f0,f1);
1168  std::swap(e0,e1);
1169  }
1170  return true;
1171 }
1172 
1174 } // end namespace
1175 } // end namespace
1176 
1177 #endif
1178 
Generated on Wed Nov 20 2019 09:00:10 for VCG Library by   doxygen 1.8.2