$darkmode
VCG Library
halfedge_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 #ifndef VCG_HEDGE_TOPOLOGY
24 #define VCG_HEDGE_TOPOLOGY
25 
26 #include <vcg/connectors/halfedge_pos.h>
27 
28 namespace vcg
29 {
30  namespace tri
31  {
32 
37  template <class MeshType> class HalfEdgeTopology
38  {
39  public:
40 
41  typedef typename MeshType::VertexPointer VertexPointer;
42  typedef typename MeshType::EdgePointer EdgePointer;
43  typedef typename MeshType::HEdgePointer HEdgePointer;
44  typedef typename MeshType::FacePointer FacePointer;
45 
46  typedef typename MeshType::VertexIterator VertexIterator;
47  typedef typename MeshType::EdgeIterator EdgeIterator;
48  typedef typename MeshType::HEdgeIterator HEdgeIterator;
49  typedef typename MeshType::FaceIterator FaceIterator;
50 
51 
62  static VertexPointer edge_collapse_quad(MeshType &m, HEdgePointer hp, VertexPointer vp)
63  {
64  assert(vp);
65  assert(hp);
66  assert(MeshType::HEdgeType::HasHVAdjacency());
67  assert(hp->HVp() == vp || hp->HOp()->HVp() == vp);
68  assert(hp->HFp()->VN() == 4);
69  assert(hp->HOp()->HFp()->VN() == 4);
70 
71 
72  VertexPointer vp_opp;
73  FacePointer fp;
74 
75  if( hp->HVp() == vp )
76  hp = hp->HOp();
77 
78  //retrieve opposite vertex and right face for diagonal collapse
79  vp_opp = hp->HVp();
80  fp = hp->HFp();
81 
82  VertexPointer vp_rot = vertex_rotate_quad( vp );
83 
84  assert(vp_rot == vp);
85 
86  return diagonal_collapse_quad( m, fp, vp );
87  }
88 
99  static VertexPointer diagonal_collapse_quad(MeshType &m, FacePointer fp, VertexPointer vp)
100  {
101 
102  assert(MeshType::VertexType::HasVHAdjacency());
103  assert(MeshType::FaceType::HasFHAdjacency());
104  assert(MeshType::HEdgeType::HasHVAdjacency());
105  assert(MeshType::HEdgeType::HasHFAdjacency());
106  assert(MeshType::HEdgeType::HasHOppAdjacency());
107  assert(MeshType::HEdgeType::HasHPrevAdjacency());
108 
109  assert(fp);
110  assert(fp->FHp());
111  assert(fp->VN() == 4);
112  assert(!fp->IsD());
113 
114  assert( !has_doublet_quad(fp) );
115  assert(!is_singlet_quad(fp));
116 
117  bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
118  bool HasEH = MeshType::EdgeType::HasEHAdjacency();
119 
120  HEdgePointer hp;
121 
122  std::vector<VertexPointer> vps = getVertices(fp);
123 
124  assert(vps.size()==4);
125 
126  for(unsigned int i = 0; i< vps.size(); i++)
127  {
128  // all vertices must be different
129  assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
130  }
131 
132  hp = fp->FHp();
133 
134  while(hp->HVp() != vp)
135  hp= hp->HNp();
136 
137  std::vector<HEdgePointer> hps = getHEdges(fp,hp);
138 
139  assert(vp == hps[0]->HVp());
140 
141  VertexPointer opposite_vertex = hps[2]->HVp();
142 
143  vp->P() = (vp->P() + opposite_vertex->P() )/2;
144  change_vertex(opposite_vertex, vp);
145 
146  hps[0]->HOp()->HOp()=hps[1]->HOp();
147  hps[1]->HOp()->HOp()=hps[0]->HOp();
148 
149  hps[2]->HOp()->HOp()=hps[3]->HOp();
150  hps[3]->HOp()->HOp()=hps[2]->HOp();
151 
152  for(int i=0; i<4; i++)
153  {
154  if(hps[i]->HVp()->VHp() == hps[i])
155  hps[i]->HVp()->VHp() = hps[(i+4-1)%4]->HOp();
156  }
157 
158  if(HasHE)
159  {
160  hps[1]->HOp()->HEp()=hps[0]->HEp();
161  hps[3]->HOp()->HEp()=hps[2]->HEp();
162  }
163 
164  if(HasEH && HasHE)
165  {
166  for(int i=0; i<3; i+=2)
167  {
168  if(hps[i]->HEp()->EHp() == hps[i])
169  hps[i]->HEp()->EHp() = hps[i]->HOp();
170  }
171  }
172 
173  // there are no faces, remove hedges and edge
174  /*
175  /\
176  hps[1]->HOp() / \ hps[0]->HOp()
177  / \
178  ------ ------
179  | \ / |
180  | \ / |
181  |_______\/_______|
182  */
183 
184  bool b[2];
185 
186  b[0] = (hps[0]->HOp()->HFp() == NULL && hps[1]->HOp()->HFp() == NULL);
187  b[1] = (hps[2]->HOp()->HFp() == NULL && hps[3]->HOp()->HFp() == NULL);
188 
189  for( int i=0, j=0; i < 4; i+=2, j++ )
190  {
191  if(b[j])
192  {
193  if(HasHE)
194  vcg::tri::Allocator<MeshType>::DeleteEdge(m, *(hps[i]->HEp()) );
195 
196  vcg::tri::Allocator<MeshType>::DeleteHEdge(m, *(hps[i]->HOp()) );
197  vcg::tri::Allocator<MeshType>::DeleteHEdge(m, *(hps[i+1]->HOp()) );
198 
199  hps[i+1]->HVp()->VHp() = NULL;
200 
201  if(!b[(j+1)%2])
202  {
203  hps[i]->HOp()->HNp()->HPp() = hps[i+1]->HOp()->HPp();
204  hps[i+1]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
205 
206  if(vp->VHp() == hps[i+1]->HOp())
207  vp->VHp() = hps[(i+3)%4]->HOp();
208  }
209 
210  else
211  vp->VHp() = NULL;
212 
213  }
214  }
215 
216 
218  vcg::tri::Allocator<MeshType>::DeleteVertex(m, *(opposite_vertex) );
219  if(HasHE)
220  {
221  vcg::tri::Allocator<MeshType>::DeleteEdge(m, *(hps[1]->HEp()) );
222  vcg::tri::Allocator<MeshType>::DeleteEdge(m, *(hps[3]->HEp()) );
223  }
228 
229  return vp;
230 
231  }
232 
241  static FacePointer doublet_remove_quad(MeshType &m, VertexPointer vp)
242  {
243  assert(vp);
244 
245  HEdgePointer hp = vp->VHp();
246 
247  assert(hp);
248 
249  FacePointer fp1 = hp->HFp();
250  FacePointer fp2 = hp->HOp()->HFp();
251 
252  assert(!is_singlet_quad(fp1));
253  assert(!is_singlet_quad(fp2));
254 
255 
256  assert( fp1 );
257  assert( fp2 );
258 
259  assert( hp->HOp()->HNp()->HOp() == hp->HPp() );
260 
261  assert( fp1->VN() == 4);
262  assert( fp2->VN() == 4);
263 
264  // end of check
265 
266  hp->HNp()->HPp() = hp->HOp()->HPp();
267  hp->HOp()->HPp()->HNp() = hp->HNp();
268 
269  hp->HPp()->HPp()->HNp() = hp->HOp()->HNp()->HNp();
270  hp->HOp()->HNp()->HNp()->HPp() = hp->HPp()->HPp();
271 
272 
273  if( hp->HOp()->HVp()->VHp() == hp->HOp() )
274  hp->HOp()->HVp()->VHp() = hp->HNp();
275 
276  if( hp->HPp()->HVp()->VHp() == hp->HPp() )
277  hp->HPp()->HVp()->VHp() = hp->HPp()->HPp()->HNp();
278 
279 
280  hp->HNp()->HPp()->HFp() = fp1;
281  hp->HOp()->HNp()->HNp()->HFp() = fp1;
282 
283  if(fp1->FHp() == hp || fp1->FHp() == hp->HPp())
284  fp1->FHp() = hp->HNp();
285 
286 
288  if(MeshType::HEdgeType::HasHEAdjacency())
289  {
291  vcg::tri::Allocator<MeshType>::DeleteEdge(m, *(hp->HPp()->HEp()) );
292  }
296  vcg::tri::Allocator<MeshType>::DeleteHEdge(m, *(hp->HPp()->HOp()) );
298 
299 
300  return fp1;
301 
302 
303  }
304 
305 
314  static HEdgePointer singlet_remove_quad(MeshType &m, FacePointer fp)
315  {
316  /*
317  2
318  / \
319  / \
320  | |
321  | |
322  | 1 |
323  | /\ |
324  \ | | /
325  \ \/ /
326  3
327  */
328 
329  assert( is_singlet_quad(fp) );
330 
331  bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
332  bool HasEH = MeshType::EdgeType::HasEHAdjacency();
333 
334  std::vector<HEdgePointer> ext_hedges;
335 
336  std::vector<HEdgePointer> int_hedges = getHEdges(fp);
337 
339 
340  for(typename std::vector<HEdgePointer>::iterator hi = int_hedges.begin(); hi != int_hedges.end();++hi)
341  {
342 
343  if((*hi)->HOp()->HFp() != fp)
344  ext_hedges.push_back((*hi)->HOp());
345 
346  else if(vertex_valence((*hi)->HVp()) == 1)
347  {
348  vcg::tri::Allocator<MeshType>::DeleteVertex( m, *((*hi)->HVp()) );
349  if(HasHE)
350  vcg::tri::Allocator<MeshType>::DeleteEdge( m, *((*hi)->HEp()) );
351  }
352 
353  }
354 
355  for(typename std::vector<HEdgePointer>::iterator hi = int_hedges.begin(); hi != int_hedges.end();++hi)
357 
358  assert(ext_hedges.size() == 2);
359 
360 
361  if(ext_hedges[0]->HFp() || ext_hedges[1]->HFp())
362  {
363  ext_hedges[0]->HOp() = ext_hedges[1];
364  ext_hedges[1]->HOp() = ext_hedges[0];
365 
366  if(HasHE)
367  {
368  vcg::tri::Allocator<MeshType>::DeleteEdge( m, *(ext_hedges[1]->HEp()) );
369 
370  ext_hedges[1]->HEp() = ext_hedges[0]->HEp();
371 
372  if(HasEH)
373  ext_hedges[0]->HEp()->EHp() = ext_hedges[0];
374  }
375 
376  ext_hedges[0]->HVp()->VHp() = ext_hedges[0];
377  ext_hedges[1]->HVp()->VHp() = ext_hedges[1];
378 
379  return ext_hedges[0];
380  }
381 
382  else
383  {
384  ext_hedges[0]->HVp()->VHp() = NULL;
385  ext_hedges[1]->HVp()->VHp() = NULL;
386 
387  if(HasHE)
388  {
389  vcg::tri::Allocator<MeshType>::DeleteEdge( m, *( ext_hedges[0]->HEp()) );
390  vcg::tri::Allocator<MeshType>::DeleteEdge( m, *( ext_hedges[1]->HEp()) );
391  }
392  vcg::tri::Allocator<MeshType>::DeleteHEdge( m, *( ext_hedges[0]) );
393  vcg::tri::Allocator<MeshType>::DeleteHEdge( m, *( ext_hedges[1]) );
394 
395  return NULL;
396  }
397 
398  }
399 
400 
409  static HEdgePointer edge_rotate_quad(HEdgePointer hp, bool cw)
410  {
411 
412  assert( MeshType::HEdgeType::HasHFAdjacency() );
413  assert( MeshType::HEdgeType::HasHOppAdjacency() );
414  assert( MeshType::FaceType::HasFHAdjacency() );
415 
416 
417  FacePointer fp1 = hp->HFp();
418  FacePointer fp2 = hp->HOp()->HFp();
419 
420 
421  assert( fp1 );
422  assert( fp1->VN() == 4 );
423 
424  assert( fp2 );
425  assert( fp2->VN() == 4 );
426 
427  assert(!is_singlet_quad(fp1));
428  assert(!is_singlet_quad(fp2));
429 
430  assert(!has_doublet_quad(fp1));
431  assert(!has_doublet_quad(fp2));
432 
433  std::vector<FacePointer> fps;
434  typedef std::vector<HEdgePointer> hedge_vect;
435  std::vector<hedge_vect> hps;
436 
437  fps.push_back(fp1);
438  fps.push_back(fp2);
439 
440 
441  hps.push_back( getHEdges( fp1, hp ) );
442  hps.push_back( getHEdges( fp2, hp->HOp() ) );
443 
444 
445  for(int i=0; i< 2; i++)
446  {
447 
448  int j = (i+1)%2;
449 
450  // uguali sia per cw che per ccw
451  hps[i][1]->HPp() = hps[j][3];
452  hps[j][3]->HNp() = hps[i][1];
453 
454  if(hps[j][0]->HVp()->VHp() == hps[j][0])
455  hps[j][0]->HVp()->VHp() = hps[i][1];
456 
457  if(cw)
458  {
459  hps[i][0]->HNp() = hps[j][3];
460  hps[j][3]->HPp() = hps[i][0];
461 
462  hps[j][2]->HNp() = hps[j][0];
463  hps[j][0]->HPp() = hps[j][2];
464 
465  hps[j][0]->HVp() = hps[j][3]->HVp();
466 
467  hps[j][3]->HFp() = fps[i];
468 
469  if(fps[j]->FHp() == hps[j][3])
470  fps[j]->FHp() = hps[j][0];
471  }
472  else
473  {
474  hps[i][0]->HNp() = hps[i][2];
475  hps[i][2]->HPp() = hps[i][0];
476 
477  hps[i][1]->HNp() = hps[j][0];
478  hps[j][0]->HPp() = hps[i][1];
479 
480  hps[j][0]->HVp() = hps[i][2]->HVp();
481 
482  hps[i][1]->HFp() = fps[j];
483 
484  if(fps[i]->FHp() == hps[i][1])
485  fps[i]->FHp() = hps[i][0];
486  }
487 
488  }
489 
490  return hp;
491 
492  }
493 
494 
495 
503  static VertexPointer vertex_rotate_quad(VertexPointer vp)
504  {
505 
506  assert(MeshType::VertexType::HasVHAdjacency());
507  assert( vp->VHp() );
508 
509  vcg::hedge::Pos<MeshType> p(vp->VHp(), true);
510 
511  HEdgePointer hep = p.HE();
512 
513  typedef std::vector<HEdgePointer> hedge_vect;
514  std::vector<hedge_vect> hedges;
515 
516  do
517  {
518  assert( p.F() );
519  assert( p.F()->VN() == 4);
520 
521  hedges.push_back(getHEdges(p.F(), p.HE()));
522 
523  p.FlipE();
524  p.FlipF();
525 
526  }while(p.HE() != hep);
527 
528 
529  int size = hedges.size();
530 
531  for(int i=0; i< size; i++)
532  {
533  hedges[i][0]->HNp() = hedges[i][2];
534  hedges[i][2]->HPp() = hedges[i][0];
535 
536  assert(hedges[i][0]->HOp() == hedges[(i+size-1)%size][3]);
537 
538  hedges[i][2]->HNp() = hedges[(i+1)%size][1];
539  hedges[(i+1)%size][1]->HPp() = hedges[i][2];
540 
541  hedges[(i+1)%size][1]->HNp() = hedges[i][3];
542  hedges[i][3]->HPp() = hedges[(i+1)%size][1];
543 
544  hedges[(i+1)%size][1]->HFp() = hedges[i][3]->HFp();
545 
546  if(hedges[i][3]->HVp()->VHp() == hedges[i][3])
547  hedges[i][3]->HVp()->VHp() = hedges[(i+1)%size][1];
548 
549  hedges[i][3]->HVp() = hedges[(i+1)%size][2]->HVp();
550 
551  if(hedges[i][0]->HFp()->FHp() == hedges[i][1])
552  hedges[i][0]->HFp()->FHp() = hedges[i][0];
553 
554  }
555  return vp;
556 
557  }
558 
559 
569  static VertexPointer edge_collapse(MeshType &m, HEdgePointer hp, VertexPointer vp)
570  {
571 
572  assert(MeshType::VertexType::HasVHAdjacency());
573  assert(MeshType::HEdgeType::HasHOppAdjacency());
574  assert(MeshType::HEdgeType::HasHVAdjacency());
575  assert(MeshType::HEdgeType::HasHPrevAdjacency());
576 
577  if( hp->HFp() )
578  assert(hp->HFp()->VN() > 3);
579 
580  if( hp->HOp()->HFp())
581  assert(hp->HOp()->HFp()->VN() > 3);
582 
583  assert(hp->HFp() || hp->HOp()->HFp());
584  assert(hp->HVp() == vp || hp->HOp()->HVp() == vp);
585 
586 
587  HEdgePointer hopp = hp->HOp();
588 
589  VertexPointer vp1;
590 
591  if( hp->HVp() == vp )
592  vp1 = hopp->HVp();
593  else
594  vp1 = hp->HVp();
595 
596  change_vertex( vp, vp1);
597 
598  //HP
599  hp->HNp()->HPp() = hp->HPp();
600  hopp->HNp()->HPp() = hopp->HPp();
601 
602  //HN
603  hp->HPp()->HNp() = hp->HNp();
604  hopp->HPp()->HNp() = hopp->HNp();
605 
606  //FH
607  if( hp->HFp() )
608  if( hp->HFp()->FHp() == hp )
609  hp->HFp()->FHp() = hp->HNp();
610 
611  if( hopp->HFp() )
612  if( hopp->HFp()->FHp() == hopp )
613  hopp->HFp()->FHp() = hopp->HNp();
614 
615  // VH
616  if( vp1->VHp() == hopp )
617  vp1->VHp() = hopp->HNp();
618 
619  if(HasHEAdjacency(m))
624 
625  return vp1;
626 
627  }
628 
637  static FacePointer add_face(MeshType &m, std::vector<VertexPointer> &vps)
638  {
639 
640  assert(MeshType::VertexType::HasVHAdjacency());
641  assert(MeshType::HEdgeType::HasHVAdjacency());
642  assert(MeshType::HEdgeType::HasHFAdjacency());
643  assert(MeshType::HEdgeType::HasHOppAdjacency());
644  assert(MeshType::HEdgeType::HasHPrevAdjacency());
645 
646  unsigned int size = vps.size();
647 
648  assert(size >= 3); //there must be at least 3 vertices
649 
650  for(unsigned int i = 0; i< size; i++)
651  {
652  // all vertices must be different
653  assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
654  }
655 
656  std::vector<HEdgePointer> hps;
657 
658  while(hps.size() < size)
659  if( !can_add_hedge(vps, hps) )
660  return NULL;
661 
662  std::vector<bool> non_manifold_vertices(size, false);
663 
664  return add_face_unsafe( m,vps, hps, non_manifold_vertices);
665 
666  }
667 
677  static bool remove_face(MeshType &m, FacePointer fp)
678  {
679 
680  assert(MeshType::VertexType::HasVHAdjacency());
681  assert(MeshType::FaceType::HasFHAdjacency());
682  assert(MeshType::HEdgeType::HasHVAdjacency());
683  assert(MeshType::HEdgeType::HasHFAdjacency());
684  assert(MeshType::HEdgeType::HasHOppAdjacency());
685  assert(MeshType::HEdgeType::HasHPrevAdjacency());
686 
687  if( can_remove_face(fp) )
688  {
689  remove_face_unsafe(m, fp);
690  return true;
691  }
692 
693  return false;
694  }
695 
696  protected:
697 
706  static FacePointer add_face_unsafe(MeshType &m, std::vector<VertexPointer> &vps)
707  {
708  unsigned int size = vps.size();
709 
710  std::vector<HEdgePointer> hps;
711  std::vector<bool> non_manifold_vertices;
712 
713  while(hps.size() < size)
714  {
715  if( can_add_hedge(vps, hps) )
716  non_manifold_vertices.push_back( false );
717  else
718  non_manifold_vertices.push_back( hps.back() == NULL );
719  }
720 
721  return add_face_unsafe(m,vps,hps, non_manifold_vertices);
722  }
723 
724 
735  static FacePointer add_face_unsafe(MeshType &m, std::vector<VertexPointer> &vps, std::vector<HEdgePointer> &hps, std::vector<bool> &non_manifold_vertices)
736  {
737 
738  assert(MeshType::VertexType::HasVHAdjacency());
739  assert(MeshType::HEdgeType::HasHVAdjacency());
740  assert(MeshType::HEdgeType::HasHFAdjacency());
741  assert(MeshType::HEdgeType::HasHOppAdjacency());
742  assert(MeshType::HEdgeType::HasHPrevAdjacency());
743 
744  unsigned int size = vps.size();
745 
746  assert(size >= 3); //there must be at least 3 vertices
747 
748 // for(unsigned int i = 0; i< size; i++)
749 // {
750 // // all vertices must be different
751 // assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
752 // }
753 
754  bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
755  bool HasEH = MeshType::EdgeType::HasEHAdjacency();
756 
757  HEdgeIterator hi;
758 
759  assert(hps.size() == size);
760 
761  HEdgePointer nullPointer = NULL;
762  int edge_n = count(hps.begin(), hps.end(), nullPointer);
763 
764  FacePointer fp;
765 
766  FaceIterator fi = vcg::tri::Allocator<MeshType>::AddFaces(m,1);
767  (*fi).Alloc( size );
768  fp = &(*fi);
769 
770  if(edge_n > 0)
771  {
772 
773  EdgeIterator ei;
774 
775  fp->SetD();
776 
777  if(HasEH || HasHE)
778  {
780  for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
781  (*ei1).SetD();
782  }
783 
784  typename vcg::tri::Allocator<MeshType>::template PointerUpdater<HEdgePointer> pu;
785 
786  if(m.hedge.empty())
787  pu.oldBase = 0;
788  else
789  {
790  pu.oldBase = &*(m.hedge.begin());
791  pu.oldEnd = &m.hedge.back()+1;
792  }
793 
795 
796  pu.newBase = &*(m.hedge.begin());
797  pu.newEnd = &m.hedge.back()+1;
798 
799  //undelete face
800  fp->ClearD();
801 
802  //undelete edges
803  for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
804  (*ei1).ClearD();
805 
806  // update hedge pointers (if needed)
807  if( pu.NeedUpdate() )
808  for(typename std::vector<HEdgePointer>::iterator hpsi = hps.begin(); hpsi != hps.end(); ++hpsi)
809  {
810  if((*hpsi))
811  pu.Update(*hpsi);
812  }
813 
814 
815  HEdgeIterator hi1 = hi;
816  HEdgeIterator hi2 = hi;
817 
818  ++hi2;
819 
820  EdgeIterator ei1 = ei;
821 
822  for(; hi2 != m.hedge.end(); ++hi1, ++hi2)
823  {
824  // EH
825  if(HasEH)
826  (*ei1).EHp() = &(*hi1);
827 
828  // HE
829  if(HasHE)
830  {
831  (*hi1).HEp() = &(*ei1);
832  (*hi2).HEp() = &(*ei1);
833  }
834 
835  //HO
836  (*hi1).HOp() = &(*hi2);
837  (*hi2).HOp() = &(*hi1);
838 
839  // HF
840  (*hi1).HFp() = fp;
841 
842  ++hi1;
843  ++hi2;
844  }
845  }
846 
847  std::vector<HEdgePointer> hps1;
848 
849  for(unsigned int i = 0; i < size; i++)
850  {
851  if(hps[i] == NULL)
852  {
853  hps1.push_back(&(*hi));
854  ++hi;
855  ++hi;
856  }
857  else
858  hps1.push_back(hps[i]);
859  }
860 
861  assert( hps1.size() == size );
862 
863  for(unsigned int i = 0; i < size; i++)
864  {
865 
866  int next = (i+1)%size;
867 
868  // hedge already exisitng
869  if(hps[i])
870  {
871  hps1[i]->HFp() = fp;
872 
873  // next hedge was disconnected
874  if(!hps[next])
875  {
876 
877  hps1[next]->HOp()->HNp() = hps1[i]->HNp();
878 
879  hps1[i]->HNp()->HPp() = hps1[next]->HOp();
880 
881  hps1[i]->HNp() = hps1[next];
882 
883  hps1[next]->HPp() = hps1[i];
884  }
885  }
886 
887  // hedge wasn't existing, vertex was disconnected
888  else
889  {
890  //HV
891  hps1[i]->HVp() = vps[i];
892  hps1[i]->HOp()->HVp() = vps[next];
893 
894 
895  hps1[i]->HNp() = hps1[next];
896 
897  // next hedge was existing (vertex was disconnected)
898  if(hps[next])
899  {
900  hps1[i]->HOp()->HPp() = hps1[next]->HPp();
901  hps1[next]->HPp()->HNp() = hps1[i]->HOp();
902  }
903 
904  //vertex was detached
905  else
906  {
907  // after face insertion vertex will become non-manifold
908  if(non_manifold_vertices[next])
909  {
910  vcg::hedge::Pos<MeshType> p(vps[next]->VHp(), true);
911 
912  while(p.F())
913  {
914 
915  p.FlipE();
916  p.FlipF();
917 
918  if(p.HE() == vps[next]->VHp())
919  assert(0); //can't add a connection, there is no space
920  }
921 
922 
923  p.HE()->HPp()->HNp() = hps1[i]->HOp();
924  hps1[i]->HOp()->HPp() = p.HE()->HPp();
925 
926  p.HE()->HPp() = hps1[next]->HOp();
927  hps1[next]->HOp()->HNp() = p.HE();
928 
929  }
930  else
931  {
932  hps1[i]->HOp()->HPp() = hps1[next]->HOp();
933  hps1[next]->HOp()->HNp() = hps1[i]->HOp();
934  }
935 
936  }
937 
938 
939  hps1[next]->HPp() = hps1[i];
940 
941  //VH
942  if( !vps[i]->VHp())
943  vps[i]->VHp() = hps1[i];
944  }
945  }
946 
947  //FH
948  fp->FHp() = hps1.front();
949 
950  return fp;
951 
952  }
953 
961  static void remove_face_unsafe (MeshType &m, FacePointer fp)
962  {
963 
964  std::vector<HEdgePointer> hps = getHEdges(fp);
965 
966  int size = hps.size();
967 
968  for( int i = 0; i< size; i++ )
969  {
970  if( hps[i]->HOp()->HFp() )
971  {
972  hps[i]->HFp() = NULL;
973 
974  if( !hps[(i+size-1)%size]->HOp()->HFp() )
975  {
976  // HP
977  hps[i]->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
978  hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i];
979  }
980 
981  if( !hps[(i+1)%size]->HOp()->HFp() )
982  {
983  // HN
984  hps[i]->HNp() = hps[(i+1)%size]->HOp()->HNp();
985  hps[(i+1)%size]->HOp()->HNp()->HPp() = hps[i];
986  }
987  }
988  else
989  {
991  vcg::tri::Allocator<MeshType>::DeleteHEdge( m, *(hps[i]->HOp()) );
992 
993  if(MeshType::HEdgeType::HasHEAdjacency())
994  vcg::tri::Allocator<MeshType>::DeleteEdge( m, *(hps[i]->HEp()) );
995 
996  if( !hps[(i+size-1)%size]->HOp()->HFp() )
997  {
998  hps[i]->HOp()->HNp()->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
999  hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
1000  }
1001 
1002  }
1003 
1004  }
1005 
1006  for( int i = 0; i< size; i++ )
1007  {
1008  if( hps[i]->HVp()->VHp()->IsD() )
1009  {
1010  if( !hps[i]->IsD() )
1011  hps[i]->HVp()->VHp() = hps[i];
1012 
1013  else if( !hps[(i+size-1)%size]->IsD() )
1014  hps[i]->HVp()->VHp() = hps[(i+size-1)%size]->HOp();
1015 
1016  else //search for a hedge (hedge can be found only if the vertex is non-manifold)
1017  {
1018  bool manifold = true;
1019 
1020  vcg::hedge::Pos<MeshType> p(hps[i]->HVp()->VHp(), true);
1021 
1022  p.HE()->SetV();
1023 
1024  p.FlipE();
1025  p.FlipF();
1026 
1027  while( !p.HE()->IsV() )
1028  {
1029  if( !p.HE()->IsD() )
1030  {
1031  manifold = false;
1032  hps[i]->HVp()->VHp() = p.HE();
1033  break;
1034  }
1035 
1036  p.FlipE();
1037  p.FlipF();
1038  }
1039 
1040  p.HE()->ClearV();
1041 
1042  if(manifold)
1043  hps[i]->HVp()->VHp() = NULL;
1044 
1045  }
1046  }
1047 
1048  }
1049 
1051 
1052  }
1053 
1064  static bool can_add_hedge( std::vector<VertexPointer> &vps, std::vector<HEdgePointer> &hps )
1065  {
1066 
1067  unsigned int i = hps.size();
1068 
1069  assert( i < vps.size() );
1070 
1071  HEdgePointer he = vps[i]->VHp();
1072 
1073  if(!he) //vertex is detached
1074  {
1075  hps.push_back(NULL);
1076  return true;
1077  }
1078  else
1079  {
1080  bool disconnected = false;
1081 
1082  bool hasEdge = false;
1083 
1084  unsigned int size = vps.size();
1085 
1086  vcg::hedge::Pos<MeshType> p(he, false);
1087 
1088  he->SetV();
1089 
1090  while(p.V() != vps[(i+1)%size])
1091  {
1092  if(!hasEdge)
1093  hasEdge= ( find( vps.begin(), vps.end(), p.V()) != (vps.end() ) );
1094 
1095  p.FlipV();
1096 
1097  p.FlipE();
1098  p.FlipF();
1099 
1100  p.FlipV();
1101 
1102  if(p.HE()->IsV())
1103  {
1104  disconnected = true;
1105  break;
1106  }
1107 
1108  }
1109 
1110  he->ClearV();
1111 
1112  if(disconnected) // edge does not exist
1113  {
1114  hps.push_back(NULL);
1115 
1116  // if hasEdge is false after inserting the face there will be a non-manifold vertex
1117  return hasEdge;
1118  }
1119 
1120  else //edge already existing
1121  {
1122  // try to insert consecutve hedges if they will belong to the new face
1123  while( (p.V() == vps[(i+1)%size]) && (i < size) )
1124  {
1125  hps.push_back( p.HE() );
1126 
1127  if(p.HE()->HFp() != NULL)
1128  return false;
1129 
1130  i++;
1131  p.FlipE();
1132  p.FlipV();
1133  }
1134  return true;
1135  }
1136  }
1137  }
1138 
1139  public:
1148  static bool can_remove_face(FacePointer fp)
1149  {
1150 
1151  assert(fp);
1152  assert(!fp->IsD());
1153 
1154  vcg::hedge::Pos<MeshType> p(fp->FHp(), true);
1155 
1156  do
1157  {
1158  std::vector<FacePointer> incident_faces = get_incident_faces( p.V() );
1159 
1160  unsigned int size = incident_faces.size();
1161 
1162  if(size > 2)
1163  {
1164  for(unsigned int i = 0; i < size; i++)
1165  {
1166  if(incident_faces[i] == NULL)
1167  if(incident_faces[(i+1)%size] != fp && incident_faces[((i+size)-1)%size] != fp )
1168  return false;
1169  }
1170  }
1171 
1172  p.FlipV();
1173  p.FlipE();
1174 
1175  }while( p.HE() != fp->FHp() );
1176 
1177  return true;
1178  }
1179 
1188  static bool check_diagonal_collapse_quad(HEdgePointer hp)
1189  {
1190 
1191  assert(hp);
1192  assert(hp->HFp());
1193  assert(hp->HFp()->VN() == 4);
1194  assert(!hp->IsD());
1195 
1196  std::vector<FacePointer> faces;
1197 
1198  HEdgePointer hopp = hp->HNp()->HNp();
1199  std::vector<FacePointer> faces1 = get_incident_faces(hp->HVp(), hp);
1200  std::vector<FacePointer> faces2 = get_incident_faces(hp->HNp()->HNp()->HVp(), hopp);
1201 
1202  faces.assign(faces1.begin()+1, faces1.end());
1203  faces.assign(faces2.begin()+1, faces2.end());
1204 
1205 
1206  // First check:
1207 
1208  unsigned int size = faces.size();
1209  bool null_face = false;
1210 
1211 
1212  // if size <=2 check is ok
1213  if(size > 2)
1214  {
1215  for(unsigned int i = 0; i < size; i++)
1216  {
1217  if(faces[i] == NULL)
1218  {
1219  if(faces[(i+1)%size] != NULL && faces[((i+size)-1)%size] != NULL )
1220  {
1221  if(null_face)
1222  return false;
1223 
1224  null_face=true;
1225  }
1226  }
1227  }
1228  }
1229 
1230  // End of first check
1231 
1232 
1233  // Second check
1234 
1235  std::set<VertexPointer> set1;
1236  std::set<VertexPointer> set2;
1237 
1238  std::vector<VertexPointer> vect1 = getVertices(hp->HVp());
1239  std::vector<VertexPointer> vect2 = getVertices(hp->HNp()->HNp()->HVp());
1240 
1241  set1.insert(vect1.begin(), vect1.end());
1242  set2.insert(vect2.begin(), vect2.end());
1243 
1244  size = vect1.size();
1245  if(vect2.size() < size)
1246  size = vect2.size();
1247 
1248  std::vector<VertexPointer> intersection(size);
1249 
1250  typename std::vector<VertexPointer>::iterator it;
1251  it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), intersection.begin());
1252 
1253  size = it- intersection.begin();
1254 
1255  assert( size >= 2 );
1256 
1257  return (size==2);
1258 
1259  // End of second check
1260 
1261  }
1262 
1272  static bool is_nonManifold_vertex(MeshType &m, VertexPointer vp)
1273  {
1274  assert(vp);
1275  assert(!vp->IsD());
1276 
1277  std::set<HEdgePointer> set1;
1278  for(HEdgeIterator hi = m.hedge.begin(); hi != m.hedge.end(); ++hi)
1279  {
1280  if(!(*hi).IsD() && (*hi).HVp() == vp)
1281  set1.insert(&(*hi));
1282  }
1283 
1284 
1285  std::vector<HEdgePointer> vect2 = get_incident_hedges(vp);
1286 
1287  std::set<HEdgePointer> set2;
1288  set2.insert(vect2.begin(), vect2.end());
1289 
1290  return !equal(set1.begin(), set1.end(), set2.begin());
1291 
1292  }
1293 
1302  static bool is_nonManifold_vertex(VertexPointer vp)
1303  {
1304  assert(vp);
1305  assert(!vp->IsD());
1306 
1307  std::vector<FacePointer> faces = get_incident_faces(vp);
1308 
1309  unsigned int size = faces.size();
1310  int null_count = 0;
1311 
1312  if(size > 2)
1313  {
1314  for(unsigned int i = 0; i < size; i++)
1315  {
1316  if(faces[i] == NULL)
1317  {
1318  if(null_count > 0)
1319  return true;
1320  else
1321  null_count++;
1322  }
1323  }
1324  }
1325 
1326  return false;
1327 
1328  }
1329 
1337  static VertexPointer opp_vert(HEdgePointer hp)
1338  {
1339  return hp->HOp()->HVp();
1340  }
1341 
1349  static std::vector<VertexPointer> getVertices(VertexPointer vp)
1350  {
1351  assert(vp);
1352  assert(!vp->IsD());
1353 
1354  HEdgePointer hp = vp->VHp();
1355 
1356  std::vector<VertexPointer> ret;
1357 
1358  if( !hp )
1359  return ret;
1360 
1361  vcg::hedge::Pos<MeshType> p(hp);
1362 
1363  do
1364  {
1365  if(p.F())
1366  {
1367  assert(!p.F()->IsD());
1368 
1369  ret.push_back( opp_vert( p.HE() ) );
1370 
1371  ret.push_back( opp_vert( p.HE()->HNp() ) );
1372 
1373 
1374  }
1375  p.FlipE();
1376  p.FlipF();
1377 
1378  }while( p.HE() != hp);
1379 
1380  return ret;
1381  }
1382 
1383 
1391  static std::set<FacePointer> getFaces(VertexPointer vp)
1392  {
1393  assert(vp);
1394  assert(!vp->IsD());
1395 
1396  std::set<FacePointer> ret;
1397 
1398  std::vector<VertexPointer> vertices = getVertices(vp);
1399 
1400  for(typename std::vector<VertexPointer>::iterator vi = vertices.begin(); vi!= vertices.end(); ++vi)
1401  {
1402  std::vector<FacePointer> incident_faces = get_incident_faces(*vi);
1403  ret.insert(incident_faces.begin(), incident_faces.end());
1404  }
1405 
1406  return ret;
1407 
1408  }
1409 
1410 
1419  static bool is_singlet_quad(FacePointer fp)
1420  {
1421  assert(fp);
1422  assert(fp->FHp());
1423  assert(!fp->IsD());
1424 
1425  vcg::hedge::Pos<MeshType> p( fp->FHp() );
1426 
1427  do
1428  {
1429  if( vertex_valence(p.V()) == 1 )
1430  return true;
1431 
1432  p.FlipV();
1433  p.FlipE();
1434 
1435  }while(p.HE() != fp->FHp());
1436 
1437  return false;
1438 
1439  }
1440 
1449  static std::vector<VertexPointer> getVertices(FacePointer fp, HEdgePointer starting_he = NULL)
1450  {
1451  assert(fp);
1452  assert(!fp->IsD());
1453 
1454  if(!starting_he)
1455  starting_he = fp->FHp();
1456 
1457  assert( starting_he->HFp() == fp );
1458 
1459  vcg::hedge::Pos<MeshType> p( starting_he, true );
1460 
1461  std::vector<VertexPointer> ret;
1462 
1463 
1464  do
1465  {
1466  assert(!(p.V()->IsD()));
1467 
1468  ret.push_back( p.V() );
1469 
1470  p.FlipV();
1471  p.FlipE();
1472 
1473  assert(ret.size() <= (unsigned int)(fp->VN()));
1474 
1475  }while(p.HE() != starting_he);
1476 
1477  return ret;
1478 
1479  }
1480 
1481  protected:
1490  static std::vector<HEdgePointer> getHEdges(FacePointer fp, HEdgePointer starting_he = NULL)
1491  {
1492  assert(fp);
1493  assert(!fp->IsD());
1494 
1495  if(starting_he)
1496  assert( starting_he->HFp() == fp );
1497  else
1498  starting_he = fp->FHp();
1499 
1500  vcg::hedge::Pos<MeshType> p( starting_he, true );
1501 
1502  std::vector<HEdgePointer> ret;
1503 
1504  do
1505  {
1506  ret.push_back( p.HE() );
1507 
1508  p.FlipV();
1509  p.FlipE();
1510 
1511  assert(ret.size() <= (unsigned int) (fp->VN()));
1512 
1513  }while(p.HE() != starting_he);
1514 
1515  return ret;
1516 
1517  }
1518 
1519  public:
1520 
1529  static std::vector<FacePointer> get_incident_faces(VertexPointer vp, HEdgePointer starting_he = NULL)
1530  {
1531  assert(vp);
1532  assert(!vp->IsD());
1533 
1534  if(starting_he)
1535  assert( starting_he->HVp() == vp );
1536  else
1537  starting_he = vp->VHp();
1538 
1539  std::vector<FacePointer> ret;
1540 
1541  if(!starting_he)
1542  return ret;
1543 
1544  vcg::hedge::Pos<MeshType> p( starting_he, true );
1545 
1546  do
1547  {
1548  ret.push_back( p.F() );
1549 
1550  p.FlipE();
1551  p.FlipF();
1552 
1553  }while(p.HE() != starting_he);
1554 
1555  return ret;
1556 
1557  }
1558 
1559 
1560  static std::vector<FacePointer> get_adjacent_faces(FacePointer fp)
1561  {
1562  assert(fp);
1563  assert(!fp->IsD());
1564 
1565  std::vector<FacePointer> ret;
1566 
1567  vcg::hedge::Pos<MeshType> p( fp->FHp() );
1568  assert(p.F() == fp);
1569 
1570  do
1571  {
1572  p.FlipF();
1573  ret.push_back( p.F() );
1574  p.FlipF();
1575 
1576  p.FlipV();
1577  p.FlipE();
1578 
1579  } while(p.HE() != fp->FHp());
1580 
1581  return ret;
1582 
1583  }
1584 
1593  static std::vector<HEdgePointer> get_incident_hedges(VertexPointer vp, HEdgePointer starting_he = NULL)
1594  {
1595  assert(vp);
1596  assert(!vp->IsD());
1597 
1598  if(starting_he)
1599  assert( starting_he->HVp() == vp );
1600  else
1601  starting_he = vp->VHp();
1602 
1603  std::vector<HEdgePointer> ret;
1604 
1605  if(!starting_he)
1606  return ret;
1607 
1608  vcg::hedge::Pos<MeshType> p( starting_he, true );
1609 
1610  do
1611  {
1612  assert(!p.HE()->IsD());
1613 
1614  ret.push_back( p.HE() );
1615 
1616  p.FlipE();
1617  p.FlipF();
1618 
1619 
1620  }while(p.HE() != starting_he);
1621 
1622  return ret;
1623 
1624  }
1625 
1634  static bool has_doublet_quad(FacePointer fp)
1635  {
1636  return ( !find_doublet_hedges_quad(fp).empty() );
1637  }
1638 
1646  static std::vector<HEdgePointer> find_doublet_hedges_quad(FacePointer fp)
1647  {
1648  assert(fp);
1649  assert(fp->FHp());
1650  assert(!fp->IsD());
1651 
1652  std::vector<HEdgePointer> ret;
1653 
1654  vcg::hedge::Pos<MeshType> p( fp->FHp(), true );
1655 
1656  do
1657  {
1658 
1659  if(vertex_valence(p.V()) == 2 && !isBorderVertex(p.V()))
1660  ret.push_back(p.HE());
1661 
1662  assert(ret.size() <= 4);
1663 
1664  p.FlipV();
1665  p.FlipE();
1666 
1667  }while(p.HE() != fp->FHp());
1668 
1669  return ret;
1670 
1671  }
1672 
1681  static bool isBorderVertex(VertexPointer vp)
1682  {
1683  assert(vp);
1684  assert(!vp->IsD());
1685 
1686  if( !(vp->VHp()) )
1687  return true;
1688 
1689  vcg::hedge::Pos<MeshType> p( vp->VHp() );
1690 
1691  do
1692  {
1693  if(!p.F())
1694  return true;
1695 
1696  p.FlipE();
1697  p.FlipF();
1698 
1699  }while(p.HE() != vp->VHp());
1700 
1701  return false;
1702  }
1703 
1711  static int vertex_valence(VertexPointer vp)
1712  {
1713  assert(vp);
1714  assert(!vp->IsD());
1715 
1716  if( !(vp->VHp()) )
1717  return 0;
1718 
1719  int ret = 0;
1720 
1721  vcg::hedge::Pos<MeshType> p( vp->VHp() );
1722 
1723  do
1724  {
1725  assert(!p.HE()->IsD());
1726  ret++;
1727 
1728  p.FlipE();
1729  p.FlipF();
1730 
1731  }while(p.HE() != vp->VHp());
1732 
1733  return ret;
1734  }
1735 
1743  protected:
1744  static void change_vertex(VertexPointer old_vp, VertexPointer new_vp)
1745  {
1746  assert(old_vp);
1747  assert(new_vp);
1748  assert(old_vp != new_vp);
1749  assert(!old_vp->IsD());
1750 
1751  vcg::hedge::Pos<MeshType> p(old_vp->VHp(),true);
1752 
1753  p.HE()->SetV();
1754 
1755  do
1756  {
1757  p.HE()->HVp() = new_vp;
1758 
1759  p.FlipE();
1760  p.FlipF();
1761 
1762  }while( !p.HE()->IsV() );
1763 
1764  p.HE()->ClearV();
1765 
1766  if( !new_vp->VHp() )
1767  new_vp->VHp() = old_vp->VHp();
1768 
1769  }
1770 
1771  };
1772 
1773  }
1774 }
1775 
1776 #endif // VCG_HEDGE_TOPOLOGY
1777 
Class to safely add and delete elements in a mesh.
Definition: allocate.h:97
static EdgeIterator AddEdges(MeshType &m, size_t n, PointerUpdater< EdgePointer > &pu)
Add n edges to the mesh. Function to add n edges to the mesh. The elements are added always to the en...
Definition: allocate.h:333
static void DeleteFace(MeshType &m, FaceType &f)
Definition: allocate.h:923
static void DeleteVertex(MeshType &m, VertexType &v)
Definition: allocate.h:935
static void DeleteHEdge(MeshType &m, HEdgeType &h)
Definition: allocate.h:957
static FaceIterator AddFaces(MeshType &m, size_t n)
Function to add n faces to the mesh. First wrapper, with no parameters.
Definition: allocate.h:615
static void DeleteEdge(MeshType &m, EdgeType &e)
Definition: allocate.h:946
static HEdgeIterator AddHEdges(MeshType &m, size_t n, PointerUpdater< HEdgePointer > &pu)
Definition: allocate.h:453
Class containing functions to modify the topology of a halfedge based mesh.
Definition: halfedge_topology.h:38
static std::vector< HEdgePointer > get_incident_hedges(VertexPointer vp, HEdgePointer starting_he=NULL)
Definition: halfedge_topology.h:1593
static bool remove_face(MeshType &m, FacePointer fp)
Definition: halfedge_topology.h:677
static std::vector< HEdgePointer > getHEdges(FacePointer fp, HEdgePointer starting_he=NULL)
Definition: halfedge_topology.h:1490
static std::set< FacePointer > getFaces(VertexPointer vp)
Definition: halfedge_topology.h:1391
static bool is_singlet_quad(FacePointer fp)
Definition: halfedge_topology.h:1419
static bool isBorderVertex(VertexPointer vp)
Definition: halfedge_topology.h:1681
static bool can_remove_face(FacePointer fp)
Definition: halfedge_topology.h:1148
static bool check_diagonal_collapse_quad(HEdgePointer hp)
Definition: halfedge_topology.h:1188
static HEdgePointer singlet_remove_quad(MeshType &m, FacePointer fp)
Definition: halfedge_topology.h:314
static std::vector< VertexPointer > getVertices(VertexPointer vp)
Definition: halfedge_topology.h:1349
static VertexPointer vertex_rotate_quad(VertexPointer vp)
Definition: halfedge_topology.h:503
static std::vector< VertexPointer > getVertices(FacePointer fp, HEdgePointer starting_he=NULL)
Definition: halfedge_topology.h:1449
static FacePointer add_face_unsafe(MeshType &m, std::vector< VertexPointer > &vps, std::vector< HEdgePointer > &hps, std::vector< bool > &non_manifold_vertices)
Definition: halfedge_topology.h:735
static bool can_add_hedge(std::vector< VertexPointer > &vps, std::vector< HEdgePointer > &hps)
Definition: halfedge_topology.h:1064
static bool is_nonManifold_vertex(MeshType &m, VertexPointer vp)
Definition: halfedge_topology.h:1272
static bool has_doublet_quad(FacePointer fp)
Definition: halfedge_topology.h:1634
static void change_vertex(VertexPointer old_vp, VertexPointer new_vp)
Definition: halfedge_topology.h:1744
static VertexPointer opp_vert(HEdgePointer hp)
Definition: halfedge_topology.h:1337
static FacePointer add_face(MeshType &m, std::vector< VertexPointer > &vps)
Definition: halfedge_topology.h:637
static HEdgePointer edge_rotate_quad(HEdgePointer hp, bool cw)
Definition: halfedge_topology.h:409
static bool is_nonManifold_vertex(VertexPointer vp)
Definition: halfedge_topology.h:1302
static void remove_face_unsafe(MeshType &m, FacePointer fp)
Definition: halfedge_topology.h:961
static VertexPointer edge_collapse_quad(MeshType &m, HEdgePointer hp, VertexPointer vp)
Definition: halfedge_topology.h:62
static VertexPointer edge_collapse(MeshType &m, HEdgePointer hp, VertexPointer vp)
Definition: halfedge_topology.h:569
static FacePointer add_face_unsafe(MeshType &m, std::vector< VertexPointer > &vps)
Definition: halfedge_topology.h:706
static std::vector< HEdgePointer > find_doublet_hedges_quad(FacePointer fp)
Definition: halfedge_topology.h:1646
static FacePointer doublet_remove_quad(MeshType &m, VertexPointer vp)
Definition: halfedge_topology.h:241
static std::vector< FacePointer > get_incident_faces(VertexPointer vp, HEdgePointer starting_he=NULL)
Definition: halfedge_topology.h:1529
static VertexPointer diagonal_collapse_quad(MeshType &m, FacePointer fp, VertexPointer vp)
Definition: halfedge_topology.h:99
static int vertex_valence(VertexPointer vp)
Definition: halfedge_topology.h:1711
Definition: namespaces.dox:6