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