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 
292 // TODO: deprecate the signature of the functions below and use references
299 template <class FaceType>
300 void FFAttach(FaceType * f, int z1, FaceType * f2, int z2)
301 {
302  //typedef FEdgePosB< FACE_TYPE > ETYPE;
303  vcg::face::Pos< FaceType > EPB(f2,z2);
304  vcg::face::Pos< FaceType > TEPB;
305  TEPB = EPB;
306  EPB.NextF();
307  while( EPB.f != f2) //Alla fine del ciclo TEPB contiene la faccia che precede f2
308  {
309  TEPB = EPB;
310  EPB.NextF();
311  }
312  //Salvo i dati di f1 prima di sovrascrivere
313  FaceType *f1prec = f->FFp(z1);
314  int z1prec = f->FFi(z1);
315 
316  //Aggiorno f1
317  assert(f1prec == f);
318  assert(TEPB.f->FFp(TEPB.z) == f2);
319 
320  f->FFp(z1) = TEPB.f->FFp(TEPB.z);
321  f->FFi(z1) = TEPB.f->FFi(TEPB.z);
322 
323  //Aggiorno la faccia che precede f2
324  TEPB.f->FFp(TEPB.z) = f1prec;
325  TEPB.f->FFi(TEPB.z) = z1prec;
326 
327  assert(FFCorrectness<FaceType>(*f,z1));
328  assert(FFCorrectness<FaceType>(*TEPB.f, TEPB.z));
329 
330 }
331 
339 template <class FaceType>
340 void FFAttachManifold(FaceType * f1, int z1, FaceType * f2, int z2)
341 {
342  assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
343  assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
344  assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
345  assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
346  f1->FFp(z1) = f2;
347  f1->FFi(z1) = z2;
348  f2->FFp(z2) = f1;
349  f2->FFi(z2) = z1;
350 }
351 
352 // This one should be called only on uniitialized faces.
353 template <class FaceType>
354 void FFSetBorder(FaceType * f1, int z1)
355 {
356  assert(f1->FFp(z1)==0 || IsBorder(*f1,z1));
357 
358  f1->FFp(z1)=f1;
359  f1->FFi(z1)=z1;
360 }
361 
362 template <class FaceType>
363 void AssertAdj(FaceType & f)
364 {
365  (void)f;
366  assert(f.FFp(0)->FFp(f.FFi(0))==&f);
367  assert(f.FFp(1)->FFp(f.FFi(1))==&f);
368  assert(f.FFp(2)->FFp(f.FFi(2))==&f);
369 
370  assert(f.FFp(0)->FFi(f.FFi(0))==0);
371  assert(f.FFp(1)->FFi(f.FFi(1))==1);
372  assert(f.FFp(2)->FFi(f.FFi(2))==2);
373 }
374 
380 template <class FaceType>
381 bool CheckOrientation(FaceType &f, int z)
382 {
383  if (IsBorder(f, z))
384  return true;
385  else
386  {
387  FaceType *g = f.FFp(z);
388  int gi = f.FFi(z);
389  if (f.V0(z) == g->V1(gi))
390  return true;
391  else
392  return false;
393  }
394 }
395 
396 
401 template <class FaceType>
402 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
403 
404 template <class FaceType, bool UpdateTopology>
405 void SwapEdge(FaceType &f, const int z)
406 {
407  // swap V0(z) with V1(z)
408  std::swap(f.V0(z), f.V1(z));
409 
410  // Managemnt of faux edge information (edge z is not affected)
411  bool Faux1 = f.IsF((z+1)%3);
412  bool Faux2 = f.IsF((z+2)%3);
413  if(Faux1) f.SetF((z+2)%3); else f.ClearF((z+2)%3);
414  if(Faux2) f.SetF((z+1)%3); else f.ClearF((z+1)%3);
415 
416  if(f.HasFFAdjacency() && UpdateTopology)
417  {
418  // store information to preserve topology
419  int z1 = (z+1)%3;
420  int z2 = (z+2)%3;
421  FaceType *g1p = f.FFp(z1);
422  FaceType *g2p = f.FFp(z2);
423  int g1i = f.FFi(z1);
424  int g2i = f.FFi(z2);
425 
426  // g0 face topology is not affected by the swap
427 
428  if (g1p != &f)
429  {
430  g1p->FFi(g1i) = z2;
431  f.FFi(z2) = g1i;
432  }
433  else
434  {
435  f.FFi(z2) = z2;
436  }
437 
438  if (g2p != &f)
439  {
440  g2p->FFi(g2i) = z1;
441  f.FFi(z1) = g2i;
442  }
443  else
444  {
445  f.FFi(z1) = z1;
446  }
447 
448  // finalize swap
449  f.FFp(z1) = g2p;
450  f.FFp(z2) = g1p;
451  }
452 }
453 
458 template <class FaceType>
459 bool FFLinkCondition(FaceType &f, const int z)
460 {
461  typedef typename FaceType::VertexType VertexType;
462  typedef typename vcg::face::Pos< FaceType > PosType;
463 
464  VertexType *v0=f.V0(z);
465  VertexType *v1=f.V1(z);
466 
467  PosType p0(&f,v0);
468  PosType p1(&f,v1);
469  std::vector<VertexType *>v0Vec;
470  std::vector<VertexType *>v1Vec;
471  VVOrderedStarFF(p0,v0Vec);
472  VVOrderedStarFF(p1,v1Vec);
473  std::set<VertexType *> v0set;
474  v0set.insert(v0Vec.begin(),v0Vec.end());
475  assert(v0set.size() == v0Vec.size());
476  int cnt =0;
477  for(size_t i=0;i<v1Vec.size();++i)
478  if(v0set.find(v1Vec[i]) != v0set.end())
479  cnt++;
480 
481  if(face::IsBorder(f,z) && (cnt==1)) return true;
482  if(!face::IsBorder(f,z) && (cnt==2)) return true;
483  //assert(0);
484  return false;
485 }
486 
503 template <class MeshType>
504 void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
505 {
506  typedef typename MeshType::FaceType FaceType;
507  typedef typename MeshType::VertexType VertexType;
508  typedef typename vcg::face::Pos< FaceType > PosType;
509  FaceType *f0 = &f;
510  int z0=z;
511  FaceType *f1 = f.FFp(z);
512  int z1=f.FFi(z);
513 
514  VertexType *delV=f.V0(z);
515  VertexType *surV=f.V1(z);
516 
517  // Collect faces that have to be updated
518  PosType delPos(f0,delV);
519  std::vector<PosType> faceToBeChanged;
520  VFOrderedStarFF(delPos,faceToBeChanged);
521 
522  // Topology Stitching
523  FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
524  int i01=-1, i02=-1, i11=-1, i12=-1;
525  // Note that the faux bit is preserved only if both of the edges to be stiched are faux.
526  bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
527  bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
528 
529  if(!face::IsBorder(*f0,(z0+1)%3)) { f01 = f0->FFp((z0+1)%3); i01=f0->FFi((z0+1)%3); FFDetachManifold(*f0,(z0+1)%3);}
530  if(!face::IsBorder(*f0,(z0+2)%3)) { f02 = f0->FFp((z0+2)%3); i02=f0->FFi((z0+2)%3); FFDetachManifold(*f0,(z0+2)%3);}
531  if(!face::IsBorder(*f1,(z1+1)%3)) { f11 = f1->FFp((z1+1)%3); i11=f1->FFi((z1+1)%3); FFDetachManifold(*f1,(z1+1)%3);}
532  if(!face::IsBorder(*f1,(z1+2)%3)) { f12 = f1->FFp((z1+2)%3); i12=f1->FFi((z1+2)%3); FFDetachManifold(*f1,(z1+2)%3);}
533 
534  // Final Pass to update the vertex ptrs in all the involved faces
535  for(size_t i=0;i<faceToBeChanged.size();++i) {
536  assert(faceToBeChanged[i].V() == delV);
537  faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
538  }
539 
540  if(f01 && f02)
541  {
542  FFAttachManifold(f01,i01,f02,i02);
543  if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
544  }
545  if(f11 && f12) {
546  FFAttachManifold(f11,i11,f12,i12);
547  if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
548  }
549  tri::Allocator<MeshType>::DeleteFace(m,*f0);
550  if(f1!=f0) tri::Allocator<MeshType>::DeleteFace(m,*f1);
551  tri::Allocator<MeshType>::DeleteVertex(m,*delV);
552 }
553 
573 template <class FaceType>
574 bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
575 {
576  typedef typename FaceType::VertexType VertexType;
577  typedef typename VertexType::CoordType CoordType;
578 
579  VertexType *OldDiag0 = f.V0(z);
580  VertexType *OldDiag1 = f.V1(z);
581 
582  VertexType *NewDiag0 = f.V2(z);
583  VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
584 
585  assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
586 
587  CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
588  CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
589  CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
590  CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
591  if(AngleN(oldN0,newN0) > angleRad) return false;
592  if(AngleN(oldN0,newN1) > angleRad) return false;
593  if(AngleN(oldN1,newN0) > angleRad) return false;
594  if(AngleN(oldN1,newN1) > angleRad) return false;
595 
596  return true;
597 }
598 
605 template <class FaceType>
606 bool CheckFlipEdge(FaceType &f, int z)
607 {
608  typedef typename FaceType::VertexType VertexType;
609  typedef typename vcg::face::Pos< FaceType > PosType;
610 
611  if (z<0 || z>2) return false;
612 
613  // boundary edges cannot be flipped
614  if (face::IsBorder(f, z)) return false;
615 
616  FaceType *g = f.FFp(z);
617  int w = f.FFi(z);
618 
619  // check if the vertices of the edge are the same
620  // e.g. the mesh has to be well oriented
621  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
622  return false;
623 
624  // check if the flipped edge is already present in the mesh
625  // f_v2 and g_v2 are the vertices of the new edge
626  VertexType *f_v2 = f.V2(z);
627  VertexType *g_v2 = g->V2(w);
628 
629  // just a sanity check. If this happens the mesh is not manifold.
630  if (f_v2 == g_v2) return false;
631 
632  // Now walk around f_v2, one of the two vertexes of the new edge
633  // and check that it does not already exists.
634 
635  PosType pos(&f, (z+2)%3, f_v2);
636  PosType startPos=pos;
637  do
638  {
639  pos.NextE();
640  if (g_v2 == pos.VFlip())
641  return false;
642  }
643  while (pos != startPos);
644 
645  return true;
646 }
647 
648 template <class FaceType>
649 bool checkFlipEdgeNotManifold (FaceType &f, const int z)
650 {
651  typedef typename FaceType::VertexType VertexType;
652  typedef typename vcg::face::Pos< FaceType > PosType;
653  if (z<0 || z>2) return false;
654 
655  // boundary edges cannot be flipped
656  if (vcg::face::IsBorder(f, z)) return false;
657 
658  FaceType *g = f.FFp(z);
659  int w = f.FFi(z);
660 
661  // check if the vertices of the edge are the same
662  // e.g. the mesh has to be well oriented
663  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
664  return false;
665 
666  // check if the flipped edge is already present in the mesh
667  // f_v2 and g_v2 are the vertices of the new edge
668  VertexType *f_v2 = f.V2(z);
669  VertexType *g_v2 = g->V2(w);
670 
671  PosType pos(&f, (z+2)%3, f_v2);
672  PosType startPos=pos;
673  do
674  {
675  pos.FlipE();
676  pos.NextF();
677 // if (g_v2 == pos.F()->V((pos.E()+1) % 3))
678  if (g_v2 == pos.VFlip())
679  return false;
680  }
681  while (pos != startPos);
682 
683  return true;
684 
685 }
686 
711 template <class FaceType>
712 void FlipEdge(FaceType &f, const int z)
713 {
714  assert(z>=0);
715  assert(z<3);
716  assert( !IsBorder(f,z) );
717  assert( face::IsManifold<FaceType>(f, z));
718 
719  FaceType *g = f.FFp(z); // The other face
720  int w = f.FFi(z); // and other side
721 
722  assert( g->V0(w) == f.V1(z) );
723  assert( g->V1(w) == f.V0(z) );
724  assert( g->V2(w) != f.V0(z) );
725  assert( g->V2(w) != f.V1(z) );
726  assert( g->V2(w) != f.V2(z) );
727 
728  f.V1(z) = g->V2(w);
729  g->V1(w) = f.V2(z);
730 
731  //topology update
732 
733 
734  f.FFp(z) = g->FFp((w+1)%3);
735  f.FFi(z) = g->FFi((w+1)%3);
736  g->FFp(w) = f.FFp((z+1)%3);
737  g->FFi(w) = f.FFi((z+1)%3);
738 
739  f.FFp((z+1)%3) = g;
740  f.FFi((z+1)%3) = (w+1)%3;
741  g->FFp((w+1)%3) = &f;
742  g->FFi((w+1)%3) = (z+1)%3;
743 
744  if(f.FFp(z)==g)
745  {
746  f.FFp(z) = &f;
747  f.FFi(z) = z;
748  }
749  else
750  {
751  f.FFp(z)->FFp( f.FFi(z) ) = &f;
752  f.FFp(z)->FFi( f.FFi(z) ) = z;
753  }
754  if(g->FFp(w)==&f)
755  {
756  g->FFp(w)=g;
757  g->FFi(w)=w;
758  }
759  else
760  {
761  g->FFp(w)->FFp( g->FFi(w) ) = g;
762  g->FFp(w)->FFi( g->FFi(w) ) = w;
763  }
764 
765 }
766 
790 template <class FaceType>
791 void FlipEdgeNotManifold(FaceType &f, const int z)
792 {
793  assert(z>=0);
794  assert(z<3);
795  assert( !IsBorder(f,z) );
796  assert( face::IsManifold<FaceType>(f, z));
797 
798  FaceType *g = f.FFp(z); // The other face
799  int w = f.FFi(z); // and other side
800 
801  assert( g->V0(w) == f.V1(z) );
802  assert( g->V1(w) == f.V0(z) );
803  assert( g->V2(w) != f.V0(z) );
804  assert( g->V2(w) != f.V1(z) );
805  assert( g->V2(w) != f.V2(z) );
806 
807  int fi1 = f.FFi(f.Next(z));
808  FaceType* fp1 = f.FFp(f.Next(z));
809 
810  int gi1 = g->FFi(g->Next(w));
811  FaceType* gp1 = g->FFp(g->Next(w));
812 
813 
814  FFDetach(f, z);
815  if (!IsBorder(f, (z+1)%3))
816  FFDetach(f, (z+1)%3);
817  if (!IsBorder(*g, (w+1)%3))
818  FFDetach(*g, (w+1)%3);
819 
820  f.V1(z) = g->V2(w);
821  g->V1(w) = f.V2(z);
822 
823  //topology update
824  FaceType* ftmp = &f;
825 
826  if (gp1 != g)
827  FFAttach(ftmp, z, gp1, gi1);
828  if (fp1 != &f)
829  FFAttach(g, w, fp1, fi1);
830 
831  FFAttachManifold(ftmp, (z+1)%3, g, (w+1)%3);
832 }
833 
834 template <class FaceType>
835 void TriSplit(FaceType *fToSplit, FaceType *newf0, FaceType *newf1, typename FaceType::VertexType *newVert)
836 {
837  typedef typename FaceType::VertexType VertexType;
838 
839  VertexType *vp0 = fToSplit->V(0);
840  VertexType *vp1 = fToSplit->V(1);
841  VertexType *vp2 = fToSplit->V(2);
842 
843  fToSplit->V(0) = vp0; fToSplit->V(1) = vp1; fToSplit->V(2) = newVert;
844  newf0->V(0) = vp1; newf0->V(1) = vp2; newf0->V(2) = newVert;
845  newf1->V(0) = vp2; newf1->V(1) = vp0; newf1->V(2) = newVert;
846 }
847 
848 
849 
850 template <class FaceType>
851 void VFDetach(FaceType & f)
852 {
853  VFDetach(f,0);
854  VFDetach(f,1);
855  VFDetach(f,2);
856 }
857 
858 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z,
859 // NOTA funziona SOLO per la topologia VF!!!
860 // usata nelle classi di collapse
861 template <class FaceType>
862 void VFDetach(FaceType & f, int z)
863 {
864  if(f.V(z)->VFp()==&f ) //if it is the first face detach from the begin
865  {
866  int fz = f.V(z)->VFi();
867  f.V(z)->VFp() = f.VFp(fz);
868  f.V(z)->VFi() = f.VFi(fz);
869  }
870  else // scan the list of faces in order to finde the current face f to be detached
871  {
872  VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
873  VFIterator<FaceType> y;
874 
875  for(;;)
876  {
877  y = x;
878  ++x;
879  assert(x.f!=0);
880  if(x.f==&f) // found!
881  {
882  y.f->VFp(y.z) = f.VFp(z);
883  y.f->VFi(y.z) = f.VFi(z);
884  break;
885  }
886  }
887  }
888 }
889 
891 template <class FaceType>
892 void VFAppend(FaceType * f, int z)
893 {
894  typename FaceType::VertexType *v = f->V(z);
895  if (v->VFp()!=0)
896  {
897  FaceType *f0=v->VFp();
898  int z0=v->VFi();
899  //append
900  f->VFp(z)=f0;
901  f->VFi(z)=z0;
902  }
903  v->VFp()=f;
904  v->VFi()=z;
905 }
906 
915 template <class FaceType>
916 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
917 {
918  typedef typename FaceType::VertexType* VertexPointer;
919  starVec.clear();
920  starVec.reserve(16);
921  face::VFIterator<FaceType> vfi(vp);
922  while(!vfi.End())
923  {
924  const int vn = vfi.F()->VN();
925  starVec.push_back(vfi.F()->V1(vfi.I()));
926  starVec.push_back(vfi.F()->V((vfi.I()+vn-1)%vn));
927  ++vfi;
928  }
929 
930  std::sort(starVec.begin(),starVec.end());
931  typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
932  starVec.resize(new_end-starVec.begin());
933 }
934 
943 template <class FaceType>
944 void VVExtendedStarVF(typename FaceType::VertexType* vp,
945  const int num_step,
946  std::vector<typename FaceType::VertexType *> &vertVec)
947  {
948  typedef typename FaceType::VertexType VertexType;
950  vertVec.clear();
951  vcg::face::VVStarVF<FaceType>(vp,vertVec);
954  for (int step=0;step<num_step-1;step++)
955  {
956  std::vector<VertexType *> toAdd;
957  for (unsigned int i=0;i<vertVec.size();i++)
958  {
959  std::vector<VertexType *> Vtemp;
960  vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
961  toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
962  }
963  vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
964  std::sort(vertVec.begin(),vertVec.end());
965  typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
966  int dist=distance(vertVec.begin(),new_end);
967  vertVec.resize(dist);
968  }
969  }
970 
978 template <class FaceType>
979 void VFStarVF( typename FaceType::VertexType* vp,
980  std::vector<FaceType *> &faceVec,
981  std::vector<int> &indexes)
982 {
983  faceVec.clear();
984  indexes.clear();
985  faceVec.reserve(16);
986  indexes.reserve(16);
987  face::VFIterator<FaceType> vfi(vp);
988  while(!vfi.End())
989  {
990  faceVec.push_back(vfi.F());
991  indexes.push_back(vfi.I());
992  ++vfi;
993  }
994 }
995 
996 
1005 template <class FaceType>
1006 void EFStarFF( FaceType* fp, int ei,
1007  std::vector<FaceType *> &faceVec,
1008  std::vector<int> &indVed)
1009 {
1010  assert(fp->FFp(ei)!=0);
1011  faceVec.clear();
1012  indVed.clear();
1013  FaceType* fpit=fp;
1014  int eit=ei;
1015  do
1016  {
1017  faceVec.push_back(fpit);
1018  indVed.push_back(eit);
1019  FaceType *new_fpit = fpit->FFp(eit);
1020  int new_eit = fpit->FFi(eit);
1021  fpit=new_fpit;
1022  eit=new_eit;
1023  } while(fpit != fp);
1024 }
1025 
1026 
1027  /* Compute the set of faces adjacent to a given face using FF adjacency.
1028  * The set is faces is extended of a given number of step
1029  * \param fp pointer to the face whose star has to be computed.
1030  * \param num_step the number of step to extend the star
1031  * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
1032  */
1033  template <class FaceType>
1034  static void FFExtendedStarFF(FaceType *fp,
1035  const int num_step,
1036  std::vector<FaceType*> &faceVec)
1037  {
1039  faceVec.push_back(fp);
1042  for (int step=0;step<num_step;step++)
1043  {
1044  std::vector<FaceType*> toAdd;
1045  for (unsigned int i=0;i<faceVec.size();i++)
1046  {
1047  FaceType *f=faceVec[i];
1048  for (int k=0;k<3;k++)
1049  {
1050  FaceType *f1=f->FFp(k);
1051  if (f1==f)continue;
1052  toAdd.push_back(f1);
1053  }
1054  }
1055  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1056  std::sort(faceVec.begin(),faceVec.end());
1057  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1058  int dist=distance(faceVec.begin(),new_end);
1059  faceVec.resize(dist);
1060  }
1061  }
1062 
1071 template <class FaceType>
1072 void VFExtendedStarVF(typename FaceType::VertexType* vp,
1073  const int num_step,
1074  std::vector<FaceType*> &faceVec)
1075  {
1077  faceVec.clear();
1078  std::vector<int> indexes;
1079  vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
1082  for (int step=0;step<num_step;step++)
1083  {
1084  std::vector<FaceType*> toAdd;
1085  for (unsigned int i=0;i<faceVec.size();i++)
1086  {
1087  FaceType *f=faceVec[i];
1088  for (int k=0;k<3;k++)
1089  {
1090  FaceType *f1=f->FFp(k);
1091  if (f1==f)continue;
1092  toAdd.push_back(f1);
1093  }
1094  }
1095  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1096  std::sort(faceVec.begin(),faceVec.end());
1097  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1098  int dist=distance(faceVec.begin(),new_end);
1099  faceVec.resize(dist);
1100  }
1101  }
1102 
1110 template <class FaceType>
1111 void VVOrderedStarFF(const Pos<FaceType> &startPos,
1112  std::vector<typename FaceType::VertexType *> &vertexVec)
1113 {
1114  vertexVec.clear();
1115  vertexVec.reserve(16);
1116  std::vector<Pos<FaceType> > posVec;
1117  VFOrderedStarFF(startPos,posVec);
1118  for(size_t i=0;i<posVec.size();++i)
1119  vertexVec.push_back(posVec[i].VFlip());
1120 }
1121 
1130 template <class FaceType>
1131 void VVOrderedStarFF(const Pos<FaceType> &startPos,
1132  std::vector<typename FaceType::VertexType *> &vertexVec,
1133  const bool ccw)
1134 {
1135  vertexVec.clear();
1136  vertexVec.reserve(16);
1137  std::vector<Pos<FaceType> > posVec;
1138  VFOrderedStarFF(startPos,posVec,ccw);
1139  for(size_t i=0;i<posVec.size();++i)
1140  vertexVec.push_back(posVec[i].VFlip());
1141 }
1142 
1150 template <class FaceType>
1151 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1152  std::vector<Pos<FaceType> > &posVec)
1153 {
1154  posVec.clear();
1155  posVec.reserve(16);
1156  bool foundBorder=false;
1157  size_t firstBorderInd;
1158  Pos<FaceType> curPos=startPos;
1159  do
1160  {
1161  assert(curPos.IsManifold());
1162  if(curPos.IsBorder() && !foundBorder) {
1163  foundBorder=true;
1164  firstBorderInd = posVec.size();
1165  }
1166  posVec.push_back(curPos);
1167  curPos.FlipF();
1168  curPos.FlipE();
1169  } while(curPos!=startPos);
1170  // if we found a border we visited each face exactly twice,
1171  // and we have to extract the border-to-border pos sequence
1172  if(foundBorder)
1173  {
1174  size_t halfSize=posVec.size()/2;
1175  assert((posVec.size()%2)==0);
1176  posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1177  posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1178  assert(posVec.size()==halfSize);
1179  }
1180 }
1181 
1190 template <class FaceType>
1191 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1192  std::vector<Pos<FaceType> > &posVec,
1193  const bool ccw)
1194 {
1195  VFOrderedStarFF(startPos, posVec);
1196  const auto & pos = posVec[0];
1197  if (ccw != (pos.VFlip() == pos.F()->V(pos.F()->Prev(pos.VInd()))))
1198  {
1199  std::reverse(posVec.begin(), posVec.end());
1200  }
1201 }
1202 
1212 template <class FaceType>
1213 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1214  std::vector<FaceType*> &faceVec,
1215  std::vector<int> &edgeVec)
1216 {
1217  std::vector<Pos<FaceType> > posVec;
1218  VFOrderedStarFF(startPos,posVec);
1219  faceVec.clear();
1220  edgeVec.clear();
1221  faceVec.reserve(16);
1222  edgeVec.reserve(16);
1223  for(size_t i=0;i<posVec.size();++i)
1224  {
1225  faceVec.push_back(posVec[i].F());
1226  edgeVec.push_back(posVec[i].E());
1227  }
1228 }
1229 
1236 template <class FaceType>
1237 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
1238 {
1239  assert((!f0->IsD())&&(!f1->IsD()));
1240  for (int i=0;i<3;i++)
1241  if (f0->FFp(i)==f1)
1242  {
1243  if((i0!=0) && (i1!=0)) {
1244  *i0=i;
1245  *i1=f0->FFi(i);
1246  }
1247  return true;
1248  }
1249  return false;
1250 }
1251 
1257 template <class FaceType>
1258 int CountSharedVertex(FaceType *f0,FaceType *f1)
1259 {
1260  int sharedCnt=0;
1261  for (int i=0;i<3;i++)
1262  for (int j=0;j<3;j++)
1263  if (f0->V(i)==f1->V(j)) {
1264  sharedCnt++;
1265  }
1266  return sharedCnt;
1267 }
1268 
1275 template <class FaceType>
1276 bool FindSharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
1277 {
1278  for (i=0;i<3;i++)
1279  for (j=0;j<3;j++)
1280  if (f0->V(i)==f1->V(j)) return true;
1281 
1282  i=-1;j=-1;
1283  return false;
1284 }
1285 
1292 template <class FaceType>
1293 bool FindSharedEdge(FaceType *f0,FaceType *f1, int &i, int &j)
1294 {
1295  for (i=0;i<3;i++)
1296  for (j=0;j<3;j++)
1297  if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1298  ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1299  return true;
1300  i=-1;j=-1;
1301  return false;
1302 }
1303 
1310 template <class FaceType>
1311 bool FindSharedFaces(typename FaceType::VertexType *v0,
1312  typename FaceType::VertexType *v1,
1313  FaceType *&f0,
1314  FaceType *&f1,
1315  int &e0,
1316  int &e1)
1317 {
1318  std::vector<FaceType*> faces0;
1319  std::vector<FaceType*> faces1;
1320  std::vector<int> index0;
1321  std::vector<int> index1;
1322  VFStarVF<FaceType>(v0,faces0,index0);
1323  VFStarVF<FaceType>(v1,faces1,index1);
1325  std::sort(faces0.begin(),faces0.end());
1326  std::sort(faces1.begin(),faces1.end());
1327  std::vector<FaceType*> Intersection;
1328  std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1329  if (Intersection.size()<2)return false;
1330  assert(Intersection.size()==2);//otherwhise non manifoldess
1331  f0=Intersection[0];
1332  f1=Intersection[1];
1333  FindSharedEdge(f0,f1,e0,e1);
1335  if (f0->V(e0)!=v0)
1336  {
1337  std::swap(f0,f1);
1338  std::swap(e0,e1);
1339  }
1340  return true;
1341 }
1342 
1344 } // end namespace
1345 } // end namespace
1346 
1347 #endif
1348 
Generated on Fri Dec 9 2022 09:00:05 for VCG Library by   doxygen 1.8.2