$darkmode
VCG Library
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 "pos.h"
28 
29 #include <vcg/complex/allocate.h>
30 
31 namespace vcg {
32 namespace face {
35 
40 template <class FaceType>
41 inline bool IsManifold( FaceType const & f, const int j )
42 {
43  assert(f.cFFp(j) != 0); // never try to use this on uncomputed topology
44  if(FaceType::HasFFAdjacency())
45  return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
46  else
47  return true;
48 }
49 
54 template <class FaceType>
55 inline bool IsBorder(FaceType const & f, const int j )
56 {
57  if(FaceType::HasFFAdjacency())
58  return f.cFFp(j)==&f;
59  //return f.IsBorder(j);
60 
61  assert(0);
62  return true;
63 }
64 
83 template <class FaceType>
84 inline typename FaceType::ScalarType DihedralAngleRad(FaceType & f, const int i )
85 {
86  typedef typename FaceType::ScalarType ScalarType;
87  typedef typename FaceType::CoordType CoordType;
88  typedef typename FaceType::VertexType VertexType;
89 
90  FaceType *f0 = &f;
91  FaceType *f1 = f.FFp(i);
92  int i0=i;
93  int i1=f.FFi(i);
94  VertexType *vf0 = f0->V2(i0);
95  VertexType *vf1 = f1->V2(i1);
96 
97  CoordType n0 = TriangleNormal(*f0).Normalize();
98  CoordType n1 = TriangleNormal(*f1).Normalize();
99  ScalarType off0 = n0*vf0->P();
100  ScalarType off1 = n1*vf1->P();
101 
102  ScalarType dist01 = off0 - n0*vf1->P();
103  ScalarType dist10 = off1 - n1*vf0->P();
104 
105  // just to be sure use the sign of the largest in absolute value;
106  ScalarType sign;
107  if(fabs(dist01) > fabs(dist10)) sign = dist01;
108  else sign=dist10;
109 
110  ScalarType angleRad=AngleN(n0,n1);
111 
112  if(sign > 0 ) return angleRad;
113  else return -angleRad;
114 }
115 
117 template <class FaceType>
118 inline typename FaceType::ScalarType WedgeAngleRad(FaceType & f, const int i )
119 {
120  auto &P0=f.P(i);
121  auto &P1=f.P(f.Next(i));
122  auto &P2=f.P(f.Prev(i));
123  return vcg::Angle(P2 - P0,P1 - P0);
124 }
125 
127 template <class FaceType>
128 inline int BorderCount(FaceType const & f)
129 {
130  if(FaceType::HasFFAdjacency())
131  {
132  int t = 0;
133  if( IsBorder(f,0) ) ++t;
134  if( IsBorder(f,1) ) ++t;
135  if( IsBorder(f,2) ) ++t;
136  return t;
137  }
138  else return 3;
139 }
140 
141 
143 template <class FaceType>
144 inline int ComplexSize(FaceType & f, const int e)
145 {
146  if(FaceType::HasFFAdjacency())
147  {
148  if(face::IsBorder<FaceType>(f,e)) return 1;
149  if(face::IsManifold<FaceType>(f,e)) return 2;
150 
151  // Non manifold case
152  Pos< FaceType > fpos(&f,e);
153  int cnt=0;
154  do
155  {
156  fpos.NextF();
157  assert(!fpos.IsBorder());
158  assert(!fpos.IsManifold());
159  ++cnt;
160  }
161  while(fpos.f!=&f);
162  assert (cnt>2);
163  return cnt;
164  }
165  assert(0);
166  return 2;
167 }
168 
169 
176 template <class FaceType>
177 bool FFCorrectness(FaceType & f, const int e)
178 {
179  if(f.FFp(e)==0) return false; // Not computed or inconsistent topology
180 
181  if(f.FFp(e)==&f) // Border
182  {
183  if(f.FFi(e)==e) return true;
184  else return false;
185  }
186 
187  if(f.FFp(e)->FFp(f.FFi(e))==&f) // plain two manifold
188  {
189  if(f.FFp(e)->FFi(f.FFi(e))==e) return true;
190  else return false;
191  }
192 
193  // Non Manifold Case
194  // all the faces must be connected in a loop.
195 
196  Pos< FaceType > curFace(&f,e); // Build the half edge
197  int cnt=0;
198  do
199  {
200  if(curFace.IsManifold()) return false;
201  if(curFace.IsBorder()) return false;
202  curFace.NextF();
203  cnt++;
204  assert(cnt<100);
205  }
206  while ( curFace.f != &f);
207  return true;
208 }
209 
210 
218 template <class FaceType>
219 void FFDetachManifold(FaceType & f, const int e)
220 {
221  assert(FFCorrectness<FaceType>(f,e));
222  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
223  FaceType *ffp = f.FFp(e);
224  //int ffi=f.FFp(e);
225  int ffi=f.FFi(e);
226 
227  f.FFp(e)=&f;
228  f.FFi(e)=e;
229  ffp->FFp(ffi)=ffp;
230  ffp->FFi(ffi)=ffi;
231 
232  f.SetB(e);
233  f.ClearF(e);
234  ffp->SetB(ffi);
235  ffp->ClearF(ffi);
236 
237  assert(FFCorrectness<FaceType>(f,e));
238  assert(FFCorrectness<FaceType>(*ffp,ffi));
239 }
240 
248 template <class FaceType>
249 void FFDetach(FaceType & f, const int e)
250 {
251  assert(FFCorrectness<FaceType>(f,e));
252  assert(!IsBorder<FaceType>(f,e)); // Never try to detach a border edge!
253  int complexity=ComplexSize(f,e);
254  (void) complexity;
255  assert(complexity>0);
256  vcg::face::Pos<FaceType> FirstFace(&f,e); // Build the half edge
257  vcg::face::Pos<FaceType> LastFace(&f,e); // Build the half edge
258  FirstFace.NextF();
259  LastFace.NextF();
260  int cnt=0;
261 
262 // then in case of non manifold face continue to advance LastFace
263 // until I find it become the one that
264 // preceed the face I want to erase
265 
266  while ( LastFace.f->FFp(LastFace.z) != &f)
267  {
268  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity);
269  assert(!LastFace.IsManifold()); // We enter in this loop only if we are on a non manifold edge
270  assert(!LastFace.IsBorder());
271  LastFace.NextF();
272  cnt++;
273  assert(cnt<100);
274  }
275 
276  assert(LastFace.f->FFp(LastFace.z)==&f);
277  assert(f.FFp(e)== FirstFace.f);
278 
279  // Now we link the last one to the first one, skipping the face to be detached;
280  LastFace.f->FFp(LastFace.z) = FirstFace.f;
281  LastFace.f->FFi(LastFace.z) = FirstFace.z;
282  assert(ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
283 
284  // At the end selfconnect the chosen edge to make a border.
285  f.FFp(e) = &f;
286  f.FFi(e) = e;
287  assert(ComplexSize(f,e)==1);
288 
289  assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
290  assert(FFCorrectness<FaceType>(f,e));
291 }
292 
293 
294 // TODO: deprecate the signature of the functions below and use references
301 template <class FaceType>
302 void FFAttach(FaceType * f, int z1, FaceType * f2, int z2)
303 {
304  //typedef FEdgePosB< FACE_TYPE > ETYPE;
305  vcg::face::Pos< FaceType > EPB(f2,z2);
306  vcg::face::Pos< FaceType > TEPB;
307  TEPB = EPB;
308  EPB.NextF();
309  while( EPB.f != f2) //Alla fine del ciclo TEPB contiene la faccia che precede f2
310  {
311  TEPB = EPB;
312  EPB.NextF();
313  }
314  //Salvo i dati di f1 prima di sovrascrivere
315  FaceType *f1prec = f->FFp(z1);
316  int z1prec = f->FFi(z1);
317 
318  //Aggiorno f1
319  assert(f1prec == f);
320  assert(TEPB.f->FFp(TEPB.z) == f2);
321 
322  f->FFp(z1) = TEPB.f->FFp(TEPB.z);
323  f->FFi(z1) = TEPB.f->FFi(TEPB.z);
324 
325  //Aggiorno la faccia che precede f2
326  TEPB.f->FFp(TEPB.z) = f1prec;
327  TEPB.f->FFi(TEPB.z) = z1prec;
328 
329  assert(FFCorrectness<FaceType>(*f,z1));
330  assert(FFCorrectness<FaceType>(*TEPB.f, TEPB.z));
331 
332 }
333 
341 template <class FaceType>
342 void FFAttachManifold(FaceType * f1, int z1, FaceType * f2, int z2)
343 {
344  assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
345  assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
346  assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
347  assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
348  f1->FFp(z1) = f2;
349  f1->FFi(z1) = z2;
350  f2->FFp(z2) = f1;
351  f2->FFi(z2) = z1;
352 }
353 
354 // This one should be called only on uniitialized faces.
355 template <class FaceType>
356 void FFSetBorder(FaceType * f1, int z1)
357 {
358  assert(f1->FFp(z1)==0 || IsBorder(*f1,z1));
359 
360  f1->FFp(z1)=f1;
361  f1->FFi(z1)=z1;
362 }
363 
364 template <class FaceType>
365 void AssertAdj(FaceType & f)
366 {
367  (void)f;
368  assert(f.FFp(0)->FFp(f.FFi(0))==&f);
369  assert(f.FFp(1)->FFp(f.FFi(1))==&f);
370  assert(f.FFp(2)->FFp(f.FFi(2))==&f);
371 
372  assert(f.FFp(0)->FFi(f.FFi(0))==0);
373  assert(f.FFp(1)->FFi(f.FFi(1))==1);
374  assert(f.FFp(2)->FFi(f.FFi(2))==2);
375 }
376 
382 template <class FaceType>
383 bool CheckOrientation(FaceType &f, int z)
384 {
385  if (IsBorder(f, z))
386  return true;
387  else
388  {
389  FaceType *g = f.FFp(z);
390  int gi = f.FFi(z);
391  if (f.V0(z) == g->V1(gi))
392  return true;
393  else
394  return false;
395  }
396 }
397 
398 
403 template <class FaceType>
404 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
405 
406 template <class FaceType, bool UpdateTopology>
407 void SwapEdge(FaceType &f, const int z)
408 {
409  // swap V0(z) with V1(z)
410  std::swap(f.V0(z), f.V1(z));
411 
412  // Managemnt of faux edge information (edge z is not affected)
413  bool Faux1 = f.IsF((z+1)%3);
414  bool Faux2 = f.IsF((z+2)%3);
415  if(Faux1) f.SetF((z+2)%3); else f.ClearF((z+2)%3);
416  if(Faux2) f.SetF((z+1)%3); else f.ClearF((z+1)%3);
417 
418  if(f.HasFFAdjacency() && UpdateTopology)
419  {
420  // store information to preserve topology
421  int z1 = (z+1)%3;
422  int z2 = (z+2)%3;
423  FaceType *g1p = f.FFp(z1);
424  FaceType *g2p = f.FFp(z2);
425  int g1i = f.FFi(z1);
426  int g2i = f.FFi(z2);
427 
428  // g0 face topology is not affected by the swap
429 
430  if (g1p != &f)
431  {
432  g1p->FFi(g1i) = z2;
433  f.FFi(z2) = g1i;
434  }
435  else
436  {
437  f.FFi(z2) = z2;
438  }
439 
440  if (g2p != &f)
441  {
442  g2p->FFi(g2i) = z1;
443  f.FFi(z1) = g2i;
444  }
445  else
446  {
447  f.FFi(z1) = z1;
448  }
449 
450  // finalize swap
451  f.FFp(z1) = g2p;
452  f.FFp(z2) = g1p;
453  }
454 }
455 
460 template <class FaceType>
461 bool FFLinkCondition(FaceType &f, const int z)
462 {
463  typedef typename FaceType::VertexType VertexType;
464  typedef typename vcg::face::Pos< FaceType > PosType;
465 
466  VertexType *v0=f.V0(z);
467  VertexType *v1=f.V1(z);
468 
469  PosType p0(&f,v0);
470  PosType p1(&f,v1);
471  std::vector<VertexType *>v0Vec;
472  std::vector<VertexType *>v1Vec;
473  VVOrderedStarFF(p0,v0Vec);
474  VVOrderedStarFF(p1,v1Vec);
475  std::set<VertexType *> v0set;
476  v0set.insert(v0Vec.begin(),v0Vec.end());
477  assert(v0set.size() == v0Vec.size());
478  int cnt =0;
479  for(size_t i=0;i<v1Vec.size();++i)
480  if(v0set.find(v1Vec[i]) != v0set.end())
481  cnt++;
482 
483  if(face::IsBorder(f,z) && (cnt==1)) return true;
484  if(!face::IsBorder(f,z) && (cnt==2)) return true;
485  //assert(0);
486  return false;
487 }
488 
505 template <class MeshType>
506 void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
507 {
508  typedef typename MeshType::FaceType FaceType;
509  typedef typename MeshType::VertexType VertexType;
510  typedef typename vcg::face::Pos< FaceType > PosType;
511  FaceType *f0 = &f;
512  int z0=z;
513  FaceType *f1 = f.FFp(z);
514  int z1=f.FFi(z);
515 
516  VertexType *delV=f.V0(z);
517  VertexType *surV=f.V1(z);
518 
519  // Collect faces that have to be updated
520  PosType delPos(f0,delV);
521  std::vector<PosType> faceToBeChanged;
522  VFOrderedStarFF(delPos,faceToBeChanged);
523 
524  // Topology Stitching
525  FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
526  int i01=-1, i02=-1, i11=-1, i12=-1;
527  // Note that the faux bit is preserved only if both of the edges to be stiched are faux.
528  bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
529  bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
530 
531  if(!face::IsBorder(*f0,(z0+1)%3)) { f01 = f0->FFp((z0+1)%3); i01=f0->FFi((z0+1)%3); FFDetachManifold(*f0,(z0+1)%3);}
532  if(!face::IsBorder(*f0,(z0+2)%3)) { f02 = f0->FFp((z0+2)%3); i02=f0->FFi((z0+2)%3); FFDetachManifold(*f0,(z0+2)%3);}
533  if(!face::IsBorder(*f1,(z1+1)%3)) { f11 = f1->FFp((z1+1)%3); i11=f1->FFi((z1+1)%3); FFDetachManifold(*f1,(z1+1)%3);}
534  if(!face::IsBorder(*f1,(z1+2)%3)) { f12 = f1->FFp((z1+2)%3); i12=f1->FFi((z1+2)%3); FFDetachManifold(*f1,(z1+2)%3);}
535 
536  // Final Pass to update the vertex ptrs in all the involved faces
537  for(size_t i=0;i<faceToBeChanged.size();++i) {
538  assert(faceToBeChanged[i].V() == delV);
539  faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
540  }
541 
542  if(f01 && f02)
543  {
544  FFAttachManifold(f01,i01,f02,i02);
545  if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
546  }
547  if(f11 && f12) {
548  FFAttachManifold(f11,i11,f12,i12);
549  if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
550  }
552  if(f1!=f0) tri::Allocator<MeshType>::DeleteFace(m,*f1);
554 }
555 
575 template <class FaceType>
576 bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
577 {
578  typedef typename FaceType::VertexType VertexType;
579  typedef typename VertexType::CoordType CoordType;
580 
581  VertexType *OldDiag0 = f.V0(z);
582  VertexType *OldDiag1 = f.V1(z);
583 
584  VertexType *NewDiag0 = f.V2(z);
585  VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
586 
587  assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
588 
589  CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
590  CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
591  CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
592  CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
593  if(AngleN(oldN0,newN0) > angleRad) return false;
594  if(AngleN(oldN0,newN1) > angleRad) return false;
595  if(AngleN(oldN1,newN0) > angleRad) return false;
596  if(AngleN(oldN1,newN1) > angleRad) return false;
597 
598  return true;
599 }
600 
607 template <class FaceType>
608 bool CheckFlipEdge(FaceType &f, int z)
609 {
610  typedef typename FaceType::VertexType VertexType;
611  typedef typename vcg::face::Pos< FaceType > PosType;
612 
613  if (z<0 || z>2) return false;
614 
615  // boundary edges cannot be flipped
616  if (face::IsBorder(f, z)) return false;
617 
618  FaceType *g = f.FFp(z);
619  int w = f.FFi(z);
620 
621  // check if the vertices of the edge are the same
622  // e.g. the mesh has to be well oriented
623  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
624  return false;
625 
626  // check if the flipped edge is already present in the mesh
627  // f_v2 and g_v2 are the vertices of the new edge
628  VertexType *f_v2 = f.V2(z);
629  VertexType *g_v2 = g->V2(w);
630 
631  // just a sanity check. If this happens the mesh is not manifold.
632  if (f_v2 == g_v2) return false;
633 
634  // Now walk around f_v2, one of the two vertexes of the new edge
635  // and check that it does not already exists.
636 
637  PosType pos(&f, (z+2)%3, f_v2);
638  PosType startPos=pos;
639  do
640  {
641  pos.NextE();
642  if (g_v2 == pos.VFlip())
643  return false;
644  }
645  while (pos != startPos);
646 
647  return true;
648 }
649 
650 template <class FaceType>
651 bool checkFlipEdgeNotManifold (FaceType &f, const int z)
652 {
653  typedef typename FaceType::VertexType VertexType;
654  typedef typename vcg::face::Pos< FaceType > PosType;
655  if (z<0 || z>2) return false;
656 
657  // boundary edges cannot be flipped
658  if (vcg::face::IsBorder(f, z)) return false;
659 
660  FaceType *g = f.FFp(z);
661  int w = f.FFi(z);
662 
663  // check if the vertices of the edge are the same
664  // e.g. the mesh has to be well oriented
665  if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
666  return false;
667 
668  // check if the flipped edge is already present in the mesh
669  // f_v2 and g_v2 are the vertices of the new edge
670  VertexType *f_v2 = f.V2(z);
671  VertexType *g_v2 = g->V2(w);
672 
673  PosType pos(&f, (z+2)%3, f_v2);
674  PosType startPos=pos;
675  do
676  {
677  pos.FlipE();
678  pos.NextF();
679 // if (g_v2 == pos.F()->V((pos.E()+1) % 3))
680  if (g_v2 == pos.VFlip())
681  return false;
682  }
683  while (pos != startPos);
684 
685  return true;
686 
687 }
688 
713 template <class FaceType>
714 void FlipEdge(FaceType &f, const int z)
715 {
716  assert(z>=0);
717  assert(z<3);
718  assert( !IsBorder(f,z) );
719  assert( face::IsManifold<FaceType>(f, z));
720 
721  FaceType *g = f.FFp(z); // The other face
722  int w = f.FFi(z); // and other side
723 
724  assert( g->V0(w) == f.V1(z) );
725  assert( g->V1(w) == f.V0(z) );
726  assert( g->V2(w) != f.V0(z) );
727  assert( g->V2(w) != f.V1(z) );
728  assert( g->V2(w) != f.V2(z) );
729 
730  f.V1(z) = g->V2(w);
731  g->V1(w) = f.V2(z);
732 
733  //topology update
734 
735 
736  f.FFp(z) = g->FFp((w+1)%3);
737  f.FFi(z) = g->FFi((w+1)%3);
738  g->FFp(w) = f.FFp((z+1)%3);
739  g->FFi(w) = f.FFi((z+1)%3);
740 
741  f.FFp((z+1)%3) = g;
742  f.FFi((z+1)%3) = (w+1)%3;
743  g->FFp((w+1)%3) = &f;
744  g->FFi((w+1)%3) = (z+1)%3;
745 
746  if(f.FFp(z)==g)
747  {
748  f.FFp(z) = &f;
749  f.FFi(z) = z;
750  }
751  else
752  {
753  f.FFp(z)->FFp( f.FFi(z) ) = &f;
754  f.FFp(z)->FFi( f.FFi(z) ) = z;
755  }
756  if(g->FFp(w)==&f)
757  {
758  g->FFp(w)=g;
759  g->FFi(w)=w;
760  }
761  else
762  {
763  g->FFp(w)->FFp( g->FFi(w) ) = g;
764  g->FFp(w)->FFi( g->FFi(w) ) = w;
765  }
766 
767 }
768 
792 template <class FaceType>
793 void FlipEdgeNotManifold(FaceType &f, const int z)
794 {
795  assert(z>=0);
796  assert(z<3);
797  assert( !IsBorder(f,z) );
798  assert( face::IsManifold<FaceType>(f, z));
799 
800  FaceType *g = f.FFp(z); // The other face
801  int w = f.FFi(z); // and other side
802 
803  assert( g->V0(w) == f.V1(z) );
804  assert( g->V1(w) == f.V0(z) );
805  assert( g->V2(w) != f.V0(z) );
806  assert( g->V2(w) != f.V1(z) );
807  assert( g->V2(w) != f.V2(z) );
808 
809  int fi1 = f.FFi(f.Next(z));
810  FaceType* fp1 = f.FFp(f.Next(z));
811 
812  int gi1 = g->FFi(g->Next(w));
813  FaceType* gp1 = g->FFp(g->Next(w));
814 
815 
816  FFDetach(f, z);
817  if (!IsBorder(f, (z+1)%3))
818  FFDetach(f, (z+1)%3);
819  if (!IsBorder(*g, (w+1)%3))
820  FFDetach(*g, (w+1)%3);
821 
822  f.V1(z) = g->V2(w);
823  g->V1(w) = f.V2(z);
824 
825  //topology update
826  FaceType* ftmp = &f;
827 
828  if (gp1 != g)
829  FFAttach(ftmp, z, gp1, gi1);
830  if (fp1 != &f)
831  FFAttach(g, w, fp1, fi1);
832 
833  FFAttachManifold(ftmp, (z+1)%3, g, (w+1)%3);
834 }
835 
836 template <class FaceType>
837 void TriSplit(FaceType *fToSplit, FaceType *newf0, FaceType *newf1, typename FaceType::VertexType *newVert)
838 {
839  typedef typename FaceType::VertexType VertexType;
840 
841  VertexType *vp0 = fToSplit->V(0);
842  VertexType *vp1 = fToSplit->V(1);
843  VertexType *vp2 = fToSplit->V(2);
844 
845  fToSplit->V(0) = vp0; fToSplit->V(1) = vp1; fToSplit->V(2) = newVert;
846  newf0->V(0) = vp1; newf0->V(1) = vp2; newf0->V(2) = newVert;
847  newf1->V(0) = vp2; newf1->V(1) = vp0; newf1->V(2) = newVert;
848 }
849 
850 
851 
852 template <class FaceType>
853 void VFDetach(FaceType & f)
854 {
855  VFDetach(f,0);
856  VFDetach(f,1);
857  VFDetach(f,2);
858 }
859 
860 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z,
861 // NOTA funziona SOLO per la topologia VF!!!
862 // usata nelle classi di collapse
863 template <class FaceType>
864 void VFDetach(FaceType & f, int z)
865 {
866  if(f.V(z)->VFp()==&f ) //if it is the first face detach from the begin
867  {
868  int fz = f.V(z)->VFi();
869  f.V(z)->VFp() = f.VFp(fz);
870  f.V(z)->VFi() = f.VFi(fz);
871  }
872  else // scan the list of faces in order to finde the current face f to be detached
873  {
874  VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
875  VFIterator<FaceType> y;
876 
877  for(;;)
878  {
879  y = x;
880  ++x;
881  assert(x.f!=0);
882  if(x.f==&f) // found!
883  {
884  y.f->VFp(y.z) = f.VFp(z);
885  y.f->VFi(y.z) = f.VFi(z);
886  break;
887  }
888  }
889  }
890 }
891 
893 template <class FaceType>
894 void VFAppend(FaceType * f, int z)
895 {
896  typename FaceType::VertexType *v = f->V(z);
897  if (v->VFp()!=0)
898  {
899  FaceType *f0=v->VFp();
900  int z0=v->VFi();
901  //append
902  f->VFp(z)=f0;
903  f->VFi(z)=z0;
904  }
905  v->VFp()=f;
906  v->VFi()=z;
907 }
908 
917 template <class FaceType>
918 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
919 {
920  typedef typename FaceType::VertexType* VertexPointer;
921  starVec.clear();
922  starVec.reserve(16);
923  face::VFIterator<FaceType> vfi(vp);
924  while(!vfi.End())
925  {
926  const int vn = vfi.F()->VN();
927  starVec.push_back(vfi.F()->V1(vfi.I()));
928  starVec.push_back(vfi.F()->V((vfi.I()+vn-1)%vn));
929  ++vfi;
930  }
931 
932  std::sort(starVec.begin(),starVec.end());
933  typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
934  starVec.resize(new_end-starVec.begin());
935 }
936 
945 template <class FaceType>
946 void VVExtendedStarVF(typename FaceType::VertexType* vp,
947  const int num_step,
948  std::vector<typename FaceType::VertexType *> &vertVec)
949  {
950  typedef typename FaceType::VertexType VertexType;
952  vertVec.clear();
953  vcg::face::VVStarVF<FaceType>(vp,vertVec);
956  for (int step=0;step<num_step-1;step++)
957  {
958  std::vector<VertexType *> toAdd;
959  for (unsigned int i=0;i<vertVec.size();i++)
960  {
961  std::vector<VertexType *> Vtemp;
962  vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
963  toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
964  }
965  vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
966  std::sort(vertVec.begin(),vertVec.end());
967  typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
968  int dist=distance(vertVec.begin(),new_end);
969  vertVec.resize(dist);
970  }
971  }
972 
980 template <class FaceType>
981 void VFStarVF( typename FaceType::VertexType* vp,
982  std::vector<FaceType *> &faceVec,
983  std::vector<int> &indexes)
984 {
985  faceVec.clear();
986  indexes.clear();
987  faceVec.reserve(16);
988  indexes.reserve(16);
989  face::VFIterator<FaceType> vfi(vp);
990  while(!vfi.End())
991  {
992  faceVec.push_back(vfi.F());
993  indexes.push_back(vfi.I());
994  ++vfi;
995  }
996 }
997 
998 
1007 template <class FaceType>
1008 void EFStarFF( FaceType* fp, int ei,
1009  std::vector<FaceType *> &faceVec,
1010  std::vector<int> &indVed)
1011 {
1012  assert(fp->FFp(ei)!=0);
1013  faceVec.clear();
1014  indVed.clear();
1015  FaceType* fpit=fp;
1016  int eit=ei;
1017  do
1018  {
1019  faceVec.push_back(fpit);
1020  indVed.push_back(eit);
1021  FaceType *new_fpit = fpit->FFp(eit);
1022  int new_eit = fpit->FFi(eit);
1023  fpit=new_fpit;
1024  eit=new_eit;
1025  } while(fpit != fp);
1026 }
1027 
1028 
1029  /* Compute the set of faces adjacent to a given face using FF adjacency.
1030  * The set is faces is extended of a given number of step
1031  * \param fp pointer to the face whose star has to be computed.
1032  * \param num_step the number of step to extend the star
1033  * \param faceVec a std::vector of Face pointer that is filled with the adjacent faces.
1034  */
1035  template <class FaceType>
1036  static void FFExtendedStarFF(FaceType *fp,
1037  const int num_step,
1038  std::vector<FaceType*> &faceVec)
1039  {
1041  faceVec.push_back(fp);
1044  for (int step=0;step<num_step;step++)
1045  {
1046  std::vector<FaceType*> toAdd;
1047  for (unsigned int i=0;i<faceVec.size();i++)
1048  {
1049  FaceType *f=faceVec[i];
1050  for (int k=0;k<3;k++)
1051  {
1052  FaceType *f1=f->FFp(k);
1053  if (f1==f)continue;
1054  toAdd.push_back(f1);
1055  }
1056  }
1057  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1058  std::sort(faceVec.begin(),faceVec.end());
1059  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1060  int dist=distance(faceVec.begin(),new_end);
1061  faceVec.resize(dist);
1062  }
1063  }
1064 
1073 template <class FaceType>
1074 void VFExtendedStarVF(typename FaceType::VertexType* vp,
1075  const int num_step,
1076  std::vector<FaceType*> &faceVec)
1077  {
1079  faceVec.clear();
1080  std::vector<int> indexes;
1081  vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
1084  for (int step=0;step<num_step;step++)
1085  {
1086  std::vector<FaceType*> toAdd;
1087  for (unsigned int i=0;i<faceVec.size();i++)
1088  {
1089  FaceType *f=faceVec[i];
1090  for (int k=0;k<3;k++)
1091  {
1092  FaceType *f1=f->FFp(k);
1093  if (f1==f)continue;
1094  toAdd.push_back(f1);
1095  }
1096  }
1097  faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1098  std::sort(faceVec.begin(),faceVec.end());
1099  typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1100  int dist=distance(faceVec.begin(),new_end);
1101  faceVec.resize(dist);
1102  }
1103  }
1104 
1112 template <class FaceType>
1113 void VVOrderedStarFF(const Pos<FaceType> &startPos,
1114  std::vector<typename FaceType::VertexType *> &vertexVec)
1115 {
1116  vertexVec.clear();
1117  vertexVec.reserve(16);
1118  std::vector<Pos<FaceType> > posVec;
1119  VFOrderedStarFF(startPos,posVec);
1120  for(size_t i=0;i<posVec.size();++i)
1121  vertexVec.push_back(posVec[i].VFlip());
1122 }
1123 
1132 template <class FaceType>
1133 void VVOrderedStarFF(const Pos<FaceType> &startPos,
1134  std::vector<typename FaceType::VertexType *> &vertexVec,
1135  const bool ccw)
1136 {
1137  vertexVec.clear();
1138  vertexVec.reserve(16);
1139  std::vector<Pos<FaceType> > posVec;
1140  VFOrderedStarFF(startPos,posVec,ccw);
1141  for(size_t i=0;i<posVec.size();++i)
1142  vertexVec.push_back(posVec[i].VFlip());
1143 }
1144 
1152 template <class FaceType>
1153 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1154  std::vector<Pos<FaceType> > &posVec)
1155 {
1156  posVec.clear();
1157  posVec.reserve(16);
1158  bool foundBorder=false;
1159  size_t firstBorderInd;
1160  Pos<FaceType> curPos=startPos;
1161  do
1162  {
1163  assert(curPos.IsManifold());
1164  if(curPos.IsBorder() && !foundBorder) {
1165  foundBorder=true;
1166  firstBorderInd = posVec.size();
1167  }
1168  posVec.push_back(curPos);
1169  curPos.FlipF();
1170  curPos.FlipE();
1171  } while(curPos!=startPos);
1172  // if we found a border we visited each face exactly twice,
1173  // and we have to extract the border-to-border pos sequence
1174  if(foundBorder)
1175  {
1176  size_t halfSize=posVec.size()/2;
1177  assert((posVec.size()%2)==0);
1178  posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1179  posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1180  assert(posVec.size()==halfSize);
1181  }
1182 }
1183 
1192 template <class FaceType>
1193 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1194  std::vector<Pos<FaceType> > &posVec,
1195  const bool ccw)
1196 {
1197  VFOrderedStarFF(startPos, posVec);
1198  const auto & pos = posVec[0];
1199  //if (ccw != (pos.VFlip() == pos.F()->V(pos.F()->Prev(pos.VInd()))))
1200  if ((ccw) == (pos.V()!=pos.F()->V(pos.E())))
1201  {
1202  std::reverse(posVec.begin(), posVec.end());
1203  }
1204 }
1205 
1215 template <class FaceType>
1216 void VFOrderedStarFF(const Pos<FaceType> &startPos,
1217  std::vector<FaceType*> &faceVec,
1218  std::vector<int> &edgeVec)
1219 {
1220  std::vector<Pos<FaceType> > posVec;
1221  VFOrderedStarFF(startPos,posVec);
1222  faceVec.clear();
1223  edgeVec.clear();
1224  faceVec.reserve(16);
1225  edgeVec.reserve(16);
1226  for(size_t i=0;i<posVec.size();++i)
1227  {
1228  faceVec.push_back(posVec[i].F());
1229  edgeVec.push_back(posVec[i].E());
1230  }
1231 }
1232 
1239 template <class FaceType>
1240 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
1241 {
1242  assert((!f0->IsD())&&(!f1->IsD()));
1243  for (int i=0;i<3;i++)
1244  if (f0->FFp(i)==f1)
1245  {
1246  if((i0!=0) && (i1!=0)) {
1247  *i0=i;
1248  *i1=f0->FFi(i);
1249  }
1250  return true;
1251  }
1252  return false;
1253 }
1254 
1260 template <class FaceType>
1261 int CountSharedVertex(FaceType *f0,FaceType *f1)
1262 {
1263  int sharedCnt=0;
1264  for (int i=0;i<3;i++)
1265  for (int j=0;j<3;j++)
1266  if (f0->V(i)==f1->V(j)) {
1267  sharedCnt++;
1268  }
1269  return sharedCnt;
1270 }
1271 
1278 template <class FaceType>
1279 bool FindSharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
1280 {
1281  for (i=0;i<3;i++)
1282  for (j=0;j<3;j++)
1283  if (f0->V(i)==f1->V(j)) return true;
1284 
1285  i=-1;j=-1;
1286  return false;
1287 }
1288 
1295 template <class FaceType>
1296 bool FindSharedEdge(FaceType *f0,FaceType *f1, int &i, int &j)
1297 {
1298  for (i=0;i<3;i++)
1299  for (j=0;j<3;j++)
1300  if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1301  ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1302  return true;
1303  i=-1;j=-1;
1304  return false;
1305 }
1306 
1313 template <class FaceType>
1314 bool FindSharedFaces(typename FaceType::VertexType *v0,
1315  typename FaceType::VertexType *v1,
1316  FaceType *&f0,
1317  FaceType *&f1,
1318  int &e0,
1319  int &e1)
1320 {
1321  std::vector<FaceType*> faces0;
1322  std::vector<FaceType*> faces1;
1323  std::vector<int> index0;
1324  std::vector<int> index1;
1325  VFStarVF<FaceType>(v0,faces0,index0);
1326  VFStarVF<FaceType>(v1,faces1,index1);
1328  std::sort(faces0.begin(),faces0.end());
1329  std::sort(faces1.begin(),faces1.end());
1330  std::vector<FaceType*> Intersection;
1331  std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1332  if (Intersection.size()<2)return false;
1333  assert(Intersection.size()==2);//otherwhise non manifoldess
1334  f0=Intersection[0];
1335  f1=Intersection[1];
1336  FindSharedEdge(f0,f1,e0,e1);
1338  if (f0->V(e0)!=v0)
1339  {
1340  std::swap(f0,f1);
1341  std::swap(e0,e1);
1342  }
1343  return true;
1344 }
1345 
1347 } // end namespace
1348 } // end namespace
1349 
1350 #endif
1351 
static void DeleteFace(MeshType &m, FaceType &f)
Definition: allocate.h:923
static void DeleteVertex(MeshType &m, VertexType &v)
Definition: allocate.h:935
int ComplexSize(FaceType &f, const int e)
Counts the number of incident faces in a complex edge.
Definition: topology.h:144
void FlipEdgeNotManifold(FaceType &f, const int z)
Definition: topology.h:793
FaceType::ScalarType WedgeAngleRad(FaceType &f, const int i)
Return the internal angle (in radians) of the i-th wedge of the triangle.
Definition: topology.h:118
bool IsManifold(FaceType const &f, const int j)
Definition: topology.h:41
void FFAttachManifold(FaceType *f1, int z1, FaceType *f2, int z2)
Definition: topology.h:342
void VFExtendedStarVF(typename FaceType::VertexType *vp, const int num_step, std::vector< FaceType * > &faceVec)
Compute the set of faces adjacent to a given vertex using VF adjacency.
Definition: topology.h:1074
void EFStarFF(FaceType *fp, int ei, std::vector< FaceType * > &faceVec, std::vector< int > &indVed)
Compute the set of faces incident onto a given edge using FF adjacency.
Definition: topology.h:1008
int CountSharedVertex(FaceType *f0, FaceType *f1)
Definition: topology.h:1261
bool IsBorder(FaceType const &f, const int j)
Definition: topology.h:55
FaceType::ScalarType DihedralAngleRad(FaceType &f, const int i)
Compute the signed dihedral angle between the normals of two adjacent faces.
Definition: topology.h:84
void VVOrderedStarFF(const Pos< FaceType > &startPos, std::vector< typename FaceType::VertexType * > &vertexVec)
Compute the ordered set of vertices adjacent to a given vertex using FF adiacency.
Definition: topology.h:1113
bool CheckOrientation(FaceType &f, int z)
Definition: topology.h:383
void VVStarVF(typename FaceType::VertexType *vp, std::vector< typename FaceType::VertexType * > &starVec)
Compute the set of vertices adjacent to a given vertex using VF adjacency.
Definition: topology.h:918
void FFDetachManifold(FaceType &f, const int e)
Definition: topology.h:219
void SwapEdge(FaceType &f, const int z)
Definition: topology.h:404
bool CheckFlipEdge(FaceType &f, int z)
Definition: topology.h:608
bool FFCorrectness(FaceType &f, const int e)
Definition: topology.h:177
bool FindSharedFaces(typename FaceType::VertexType *v0, typename FaceType::VertexType *v1, FaceType *&f0, FaceType *&f1, int &e0, int &e1)
Definition: topology.h:1314
bool ShareEdgeFF(FaceType *f0, FaceType *f1, int *i0=0, int *i1=0)
Definition: topology.h:1240
void FlipEdge(FaceType &f, const int z)
Definition: topology.h:714
void VFAppend(FaceType *f, int z)
Append a face in VF list of vertex f->V(z)
Definition: topology.h:894
bool FindSharedEdge(FaceType *f0, FaceType *f1, int &i, int &j)
Definition: topology.h:1296
void VVExtendedStarVF(typename FaceType::VertexType *vp, const int num_step, std::vector< typename FaceType::VertexType * > &vertVec)
Compute the set of vertices adjacent to a given vertex using VF adjacency.
Definition: topology.h:946
bool FindSharedVertex(FaceType *f0, FaceType *f1, int &i, int &j)
Definition: topology.h:1279
void FFEdgeCollapse(MeshType &m, typename MeshType::FaceType &f, const int z)
Definition: topology.h:506
void FFDetach(FaceType &f, const int e)
Definition: topology.h:249
bool CheckFlipEdgeNormal(FaceType &f, const int z, const float angleRad)
Definition: topology.h:576
void VFStarVF(typename FaceType::VertexType *vp, std::vector< FaceType * > &faceVec, std::vector< int > &indexes)
Compute the set of faces adjacent to a given vertex using VF adjacency.
Definition: topology.h:981
void FFAttach(FaceType *f, int z1, FaceType *f2, int z2)
Definition: topology.h:302
int BorderCount(FaceType const &f)
Count border edges of the face.
Definition: topology.h:128
void VFOrderedStarFF(const Pos< FaceType > &startPos, std::vector< Pos< FaceType > > &posVec)
Compute the ordered set of faces adjacent to a given vertex using FF adiacency.
Definition: topology.h:1153
bool FFLinkCondition(FaceType &f, const int z)
Definition: topology.h:461
Definition: namespaces.dox:6