VCG Library
halfedge_indexed.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 __VCGLIB_HALFEDGE_
25 #define __VCGLIB_HALFEDGE_
26 
27 #include <vcg/complex/algorithms/clean.h>
28 #include <vcg/complex/algorithms/update/topology.h>
29 #include <vcg/complex/algorithms/update/halfedge_topology.h>
30 
31 namespace vcg
32 {
33  namespace tri{
36 
39  template <class MeshType >
41  public:
42  typedef typename MeshType::VertexType VertexType;
43  typedef typename MeshType::VertexPointer VertexPointer;
44  typedef typename MeshType::VertexIterator VertexIterator;
45  typedef typename MeshType::HEdgePointer HEdgePointer;
46  typedef typename MeshType::HEdgeType HEdgeType;
47  typedef typename MeshType::EdgePointer EdgePointer;
48  typedef typename MeshType::EdgeType EdgeType;
49  typedef typename MeshType::EdgeIterator EdgeIterator;
50  typedef typename MeshType::HEdgeIterator HEdgeIterator;
51  typedef typename MeshType::FaceIterator FaceIterator;
52  typedef typename MeshType::FaceType FaceType;
53 
54  struct VertexPairEdgePtr{
55  VertexPairEdgePtr(VertexPointer _v0,VertexPointer _v1,HEdgePointer _ep):v0(_v0),v1(_v1),ep(_ep){if(v0>v1) std::swap(v0,v1);}
56  bool operator <(const VertexPairEdgePtr &o) const {return (v0 == o.v0)? (v1<o.v1):(v0<o.v0);}
57  bool operator ==(const VertexPairEdgePtr &o) const {return (v0 == o.v0)&& (v1==o.v1);}
58 
59  VertexPointer v0,v1;
60  HEdgePointer ep;
61  };
62  struct FacePtrInt{
63  FacePtrInt ( FaceType * _f,int _i):f(_f),i(_i){}
64  FaceType * f;
65  int i;
66  };
67 
68  typedef std::vector<bool> BitVector;
69 
75  static void FromIndexed(MeshType & m){
76  assert(HasFVAdjacency(m));
77  assert(HasHOppAdjacency(m));
78  assert(HasHNextAdjacency(m));
79 
80  typename MeshType::template PerFaceAttributeHandle<BitVector> flagVisited =
81  vcg::tri::Allocator<MeshType>::template AddPerFaceAttribute<BitVector>(m,"");
82  std::vector<FacePtrInt > borderEdges;
83 
84  // allocate all new half edges
85  FaceIterator fi;
86  unsigned int n_edges = 0;
87 
88  // count how many half edge to allocate
89  for(fi = m.face.begin(); fi != m.face.end(); ++fi) if(! (*fi).IsD())
90  {n_edges+=(*fi).VN();
91  for(int i = 0; i < (*fi).VN(); ++i)
92  if(vcg::face::IsBorder<FaceType>((*fi),(i)))
93  ++n_edges;
94  }
95 
96  m.hedge.clear();
97  m.hn = 0;
98 
99  // allocate the half edges
100  typename MeshType::HEdgeIterator ei = vcg::tri::Allocator<MeshType>::AddHEdges(m,n_edges);
101 
102 
103  std::vector<VertexPairEdgePtr> all;
104  int firstEdge = 0;
105  for(fi = m.face.begin(); fi != m.face.end(); ++fi)if(!(*fi).IsD()){
106  assert((*fi).VN()>2);
107  if(flagVisited[*fi].empty()) {flagVisited[*fi].resize((*fi).VN());}
108 
109  for(int i = 0; i < (*fi).VN(); ++i,++ei)
110  {
111  (*ei).HVp() = (*fi).V(i);
112  (*ei).HNp() = &m.hedge[firstEdge + (i +1) % (*fi).VN()];
113  if(MeshType::HEdgeType::HasHFAdjacency())
114  (*ei).HFp() = &(*fi);
115  if( MeshType::FaceType::HasFHAdjacency())
116  (*fi).FHp() = &(*ei);
117  if(MeshType::HEdgeType::HasHPrevAdjacency())
118  (*ei).HPp() = &m.hedge[firstEdge + (i +(*fi).VN()-1) % (*fi).VN()];
119  if(HasVHAdjacency(m))
120  (*ei).HVp()->VHp() = &(*ei);
121  all.push_back(VertexPairEdgePtr((*fi).V(i), (*fi).V((*fi).Next(i)),&(*ei)));// it will be used to link the hedges
122 
123  if( vcg::face::IsBorder<FaceType>((*fi),(i)))
124  borderEdges.push_back(FacePtrInt(&(*fi),i));
125  }
126  firstEdge += (*fi).VN();
127  }
128 
129  // add all the border hedges
130  int borderLength;
131  typename std::vector<FacePtrInt >::iterator ebi;
132  for( ebi = borderEdges.begin(); ebi != borderEdges.end(); ++ebi)
133  if( !flagVisited[(*ebi).f][(*ebi).i])// not already inserted
134  {
135 
136  borderLength = 0;
137  vcg::face::Pos<FaceType> bp((*ebi).f,(*ebi).i);
138 
139  //FaceType * start = (*ebi).f;
140  VertexType * start = ((*ebi).f)->V((*ebi).i);
141  do{
142  all.push_back( VertexPairEdgePtr ( bp.f->V( bp.f->Next(bp.z) ),bp.f->V( bp.z ),&(*ei)));
143  (*ei).HVp() = bp.f->V(bp.f->Next(bp.z)) ;
144  flagVisited[bp.f][bp.z] = true;
145  ++ei;
146  bp.NextB();
147  ++borderLength;
148  }while (bp.v != start);
149  //}while (bp.f != start);
150 
151 
152  // run over the border edges to link the adjacencies
153  for(int be = 0; be < borderLength; ++be)
154  {
155  if(MeshType::HEdgeType::HasHFAdjacency())
156  m.hedge[firstEdge + be].HFp() = NULL;
157 
158  if(MeshType::HEdgeType::HasHPrevAdjacency())
159  m.hedge[firstEdge + be].HPp() = &m.hedge[firstEdge + (be +borderLength-1) % borderLength];
160 
161  m.hedge[firstEdge + be].HNp() = &m.hedge[firstEdge + (be +1) % borderLength];
162  }
163  firstEdge+=borderLength;
164  }
165 
166  vcg::tri::Allocator<MeshType>:: template DeletePerFaceAttribute<BitVector>(m,flagVisited );
167 
168  std::sort(all.begin(),all.end());
169  assert(all.size() == n_edges);
170 
171  for(unsigned int i = 0 ; i < all.size(); )
172  if(all[i] == all[i+1])
173  {
174  all[i].ep->HOp() = all[i+1].ep;
175  all[i+1].ep->HOp() = all[i].ep;
176  i+=2;
177  }
178  else
179  {
180  all[i].ep->HOp() = all[i].ep;
181  i+=1;
182  }
183 
184  if(HasEHAdjacency(m) && HasHEAdjacency(m))
185  {
186  assert(m.edge.size() == 0 || m.edge.size() == n_edges/2);
187 
188  if ( m.edge.size() == 0 )
189  {
190  m.en = 0;
191  // allocate the edges
192  typename MeshType::EdgeIterator edge_i = vcg::tri::Allocator<MeshType>::AddEdges(m,n_edges/2);
193 
194  for(ei = m.hedge.begin(); ei != m.hedge.end(); ++ei)
195  {
196  if((*ei).HEp() == NULL)
197  {
198  (*ei).HEp() = &(*edge_i);
199  (*ei).HOp()->HEp() = &(*edge_i);
200 
201  (*edge_i).EHp() = &(*ei);
202 
203  ++edge_i;
204  }
205  }
206 
207  }
208  else
209  {
210 
211  if(HasEVAdjacency(m) && HasHEAdjacency(m) && HasEHAdjacency(m))
212  {
213  //update edge relations
214 
215  for(typename MeshType::EdgeIterator ei1 = m.edge.begin(); ei1 != m.edge.end(); ++ei1 )
216  {
217  vector<HEdgePointer> hedges = HalfEdgeTopology<MeshType>::get_incident_hedges((*ei1).V(0));
218 
219  for(typename vector<HEdgePointer>::iterator hi = hedges.begin(); hi != hedges.end(); ++hi)
220  {
221  if((*hi)->HOp()->HVp() == (*ei1).V(1))
222  {
223 
224  assert((*hi)->HEp() == NULL);
225  assert((*hi)->HOp()->HEp() == NULL);
226 
227  // EH
228  (*ei1).EHp() = *hi;
229 
230  // HE
231  (*hi)->HEp() = &(*ei1);
232  (*hi)->HOp()->HEp() = &(*ei1);
233 
234  break;
235  }
236  }
237  }
238  }
239  }
240 
241  }
242 
243  }
244 
248  static bool CheckConsistency_FHp(MeshType & m){
249  assert(MeshType::FaceType::HasFHAdjacency());
250  FaceIterator fi;
251  for(fi = m.face.begin(); fi != m.face.end(); ++fi)
252  if(!(*fi).IsD()){
253  if((*fi).FHp() < &(*m.hedge.begin())) return false;
254  if((*fi).FHp() > &(m.hedge.back())) return false;
255  }
256  return true;
257  }
258 
262  static bool CheckConsistency(MeshType & m){
263  assert(MeshType::HEdgeType::HasHNextAdjacency());
264  assert(MeshType::HEdgeType::HasHOppAdjacency());
265  assert(MeshType::HEdgeType::HasHVAdjacency());
266  assert(MeshType::FaceType::HasFHAdjacency());
267 
268  //bool hasHEF = ( MeshType::HEdgeType::HasHFAdjacency());
269  bool hasHP = ( MeshType::HEdgeType::HasHPrevAdjacency());
270 
271  FaceIterator fi;
272  HEdgePointer ep,ep1;
273  int cnt = 0;
274 
275  if( MeshType::HEdgeType::HasHFAdjacency() )
276  {
277  int iDb = 0;
278  for(fi = m.face.begin(); fi != m.face.end(); ++fi,++iDb)
279  if(!(*fi).IsD())
280  {
281  ep = ep1 = (*fi).FHp();
282 
283  do{
284  if(ep->IsD())
285  return false; // the hedge should not be connected, it has been deleted
286  if( ! ep->HFp())
287  return false;
288  if(ep->HFp() != &(*fi))
289  return false;// hedge is not pointing to the rigth face
290  ep = ep->HNp();
291  if(cnt++ > m.hn)
292  return false; // hedges are ill connected (HENp())
293 
294  }while(ep!=ep1);
295 
296  }
297  }
298 
299  HEdgePointer epPrev;
300  HEdgeIterator hi;
301  //bool extEdge ;
302  for( hi = m.hedge.begin(); hi != m.hedge.end(); ++hi)
303  if(!(*hi).IsD())
304  {
305  //cnt = 0;
306  epPrev = ep = ep1 = &(*hi);
307  //do{
308  //extEdge = (ep->HFp()==NULL);
309  if(hasHP)
310  {
311  if( !ep->HPp())
312  return false;
313  if( ep->HPp() == ep)
314  return false; // the previous of an edge cannot be the edge itself
315  if( ep->HNp()->HPp() != ep)
316  return false; // next and prev relation are not mutual
317  if( ep->HPp()->IsD())
318  return false; //
319  }
320 
321  if( ! ep->HOp() )
322  return false;
323 
324  if( ep->HOp() == ep)
325  return false; // opposite relation is not mutual
326 
327  if( ep->HOp()->IsD())
328  return false;
329 
330  if( ep->HOp()->HOp() != ep)
331  return false; // opposite relation is not mutual
332 
333  if( HasHFAdjacency(m) )
334  {
335  if(ep->HFp())
336  {
337  if( ep->HFp()->IsD())
338  return false; // pointed face must not be deleted
339  }
340  }
341 
342  if( HasHEAdjacency(m) && (m.en!=0))
343  {
344  if( ! ep->HEp())
345  return false; //halfedge must point to an edge
346 
347  if( ep->HEp()->IsD())
348  return false; // pointed edge must not be deleted
349 
350  if(ep->HEp() != ep->HOp()->HEp())
351  return false; // he and opposite he must point to the same edge
352 
353  if(ep->HEp()->EHp() != ep && ep->HEp()->EHp() != ep->HOp() )
354  return false; // halfedge points to an edge not pointing it or its opposite
355 
356  }
357 
358 
359  if( !ep->HNp() )
360  return false;
361 
362  if( ep->HNp() == ep )
363  return false; // the next of an hedge cannot be the hedge itself
364 
365  if( ep->HNp()->IsD())
366  return false; //
367 
368  if(hasHP)
369  if( ep->HNp()->HPp() != ep)
370  return false; //
371 
372  if( HasHVAdjacency(m) )
373  {
374  if( ! ep->HVp() )
375  return false; // halfedge must point to a vertex
376 
377  if( ep->HVp()->IsD() )
378  return false; // pointed vertex must not be deleted
379 
380  if( HasVHAdjacency(m) )
381  if( ! (ep->HVp()->VHp()) )
382  return false; // halfedge points to a vertex pointing NULL
383 
384  }
385 
386 
387  ep = ep->HNp();
388  if( ep->HVp() != epPrev->HOp()->HVp())
389  return false;
390 
391  epPrev = ep;
392 
393  // if(cnt++ > m.hn)
394  // return false; // edges are ill connected (HENp())
395 
396  //}while(ep!=ep1);
397  }
398 
399  if(HasEHAdjacency(m) && HasHEAdjacency(m))
400  for(EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
401  {
402  if(!(*ei).IsD())
403  {
404  if( !(*ei).EHp())
405  return false; //edge must have a valid pointer to his halfedge
406 
407  if( (*ei).EHp()->HEp() != &(*ei) )
408  return false; // edge's halfedge must point to the edge itself
409 
410  if( (*ei).EHp()->IsD())
411  return false;
412  }
413  }
414 
415  if(HasVHAdjacency(m))
416  for(VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
417  {
418  if( !(*vi).IsD() )
419  if( (*vi).VHp() )
420  {
421  if( (*vi).VHp()->HVp() != &(*vi) )
422  return false;
423  if( (*vi).VHp()->IsD())
424  return false;
425  }
426  }
427 
428 
429  return true;
430  }
431 
434  private:
435  static void SetRelationsLoopFace(HEdgeType * e0, FaceType * f){
436  assert(HEdgeType::HasHNextAdjacency());
437  assert(FaceType::HasFHAdjacency());
438 
439  HEdgeType *e = e0;
440  assert(e!=NULL);
441  do{ e->HFp() = f; e = e->HNp(); } while(e != e0);
442  f->FHp() = e0;
443  }
444 
448  static void MergeFaces(FaceType *, FaceType *){}
449 
453  static HEdgeType * PreviousEdge(HEdgeType * e0){
454  HEdgeType * ep = e0;
455  do{
456  if(ep->HNp() == e0) return ep;
457  ep = ep->HNp();
458  }while(ep!=e0);
459  assert(0); // degenerate loop
460  return 0;
461  }
462 
463  public:
474  static void AddHEdge(MeshType &m, HEdgeType * e0, HEdgeType * e1){
475  assert(e1!=e0->HNp());
476  assert(e0!=e1->HNp());
477  bool hasP = MeshType::HEdgeType::HasHPrevAdjacency();
478  assert(e0->HOp() != e1); // the hedge already exists
479  assert(e0!=e1->HNp());
480 
481  std::vector<typename MeshType::HEdgePointer* > toUpdate;
482  toUpdate.push_back(&e0);
483  toUpdate.push_back(&e1);
484  HEdgeIterator ei0 = vcg::tri::Allocator<MeshType>::AddHEdges(m,2,toUpdate);
485 
486  HEdgeIterator ei1 = ei0; ++ei1;
487  (*ei0).HNp() = e1;(*ei0).HVp() = e0->HVp();
488  (*ei1).HNp() = e0;(*ei1).HVp() = e1->HVp();
489 
490  HEdgePointer e0_HEPp = 0,e1_HEPp = 0,ep =0;
491  if(hasP){
492  e0_HEPp = e0->HPp();
493  e1_HEPp = e1->HPp();
494  }else{// does not have pointer to previous, it must be computed
495  ep = e0;
496  do{
497  if(ep->HNp() == e0) e0_HEPp = ep;
498  if(ep->HNp() == e1) e1_HEPp = ep;
499  ep = ep->HNp();
500  }while(ep!=e0);
501  }
502  if(hasP){
503  (*ei0).HPp() = e0->HPp();
504  (*ei1).HPp() = e1->HPp();
505  e0->HPp() = &(*ei1);
506  e1->HPp() = &(*ei0);
507  }
508  e0_HEPp -> HNp() = &(*ei0);
509  e1_HEPp -> HNp() = &(*ei1);
510 
511  (*ei0).HOp() = &(*ei1);
512  (*ei1).HOp() = &(*ei0);
513 
514 
515  if( HEdgeType::HasHFAdjacency() && FaceType::HasFHAdjacency()){
517  m.face.back().ImportData(*e0->HFp());
518  SetRelationsLoopFace(&(*ei0),e1->HFp()); // one loop to the old face
519  SetRelationsLoopFace(&(*ei1),&m.face.back()); // the other to the new face
520  }
521  }
522 
533  static void RemoveHEdge(MeshType &m, HEdgeType * e){
534  assert(MeshType::HEdgeType::HasHNextAdjacency());
535  assert(MeshType::HEdgeType::HasHOppAdjacency());
536  assert(MeshType::FaceType::HasFHAdjacency());
537 
538  bool hasP = MeshType::HEdgeType::HasHPrevAdjacency();
539  HEdgePointer e_HEPp,eO_HEPp;
540 
541  if(hasP){
542  e_HEPp = e->HPp();
543  eO_HEPp = e->HOp()->HPp();
544  }else{
545  e_HEPp = PreviousEdge(e);
546  eO_HEPp = PreviousEdge(e->HOp());
547  }
548 
549  assert(e_HEPp->HNp() == e);
550  assert(eO_HEPp->HNp() == e->HOp());
551  e_HEPp->HNp() = e->HOp()->HNp();
552  eO_HEPp->HNp() = e-> HNp();
553 
554  if(hasP) {
555  e->HOp()->HNp()->HPp() = e_HEPp;
556  e->HNp()->HPp() = eO_HEPp;
557 
558  e->HPp() = NULL;
559  e-> HOp()->HPp() = NULL;
560  }
561 
562 
563  // take care of the faces
564  if(MeshType::HEdgeType::HasHFAdjacency()){
565  MergeFaces(e_HEPp->HFp(),eO_HEPp->HFp());
567  SetRelationsLoopFace(e_HEPp,e_HEPp->HFp());
568 
569  }
572 
573  }
574 
575  };// end class
576  template <class MeshType >
577  struct UpdateIndexed{
578  typedef typename MeshType::VertexType VertexType;
579  typedef typename MeshType::VertexPointer VertexPointer;
580  typedef typename MeshType::HEdgePointer HEdgePointer;
581  typedef typename MeshType::HEdgeType HEdgeType;
582  typedef typename MeshType::HEdgeIterator HEdgeIterator;
583  typedef typename MeshType::FaceIterator FaceIterator;
584  typedef typename MeshType::FaceType FaceType;
585 
586  struct VertexPairEdgePtr{
587  VertexPairEdgePtr(VertexPointer _v0,VertexPointer _v1,HEdgePointer _ep):v0(_v0),v1(_v1),ep(_ep){if(v0>v1) std::swap(v0,v1);}
588  bool operator <(const VertexPairEdgePtr &o) const {return (v0 == o.v0)? (v1<o.v1):(v0<o.v0);}
589  bool operator ==(const VertexPairEdgePtr &o) const {return (v0 == o.v0)&& (v1==o.v1);}
590 
591  VertexPointer v0,v1;
592  HEdgePointer ep;
593  };
594 
601  static void FromHalfEdges( MeshType & m ){
602  assert(HasFVAdjacency(m));
603  assert(MeshType::HEdgeType::HasHNextAdjacency());
604  assert(MeshType::HEdgeType::HasHVAdjacency());
605  assert(MeshType::HEdgeType::HasHOppAdjacency());
606  assert(MeshType::FaceType::HasFHAdjacency());
607  bool hasHEF;
608  //bool createFace,hasHEF,hasFHE;
609 
610  // typename MeshType::template PerHEdgeAttributeHandle<bool> hV = Allocator<MeshType>::template AddPerHEdgeAttribute<bool>(m,"");
611 
612 
613  typename MeshType::HEdgeIterator ei;
614  typename MeshType::FacePointer fp;
615  typename MeshType::FaceIterator fi;
616  typename MeshType::HEdgePointer ep,epF;
617  //int vi = 0;
618  vcg::SimpleTempData<typename MeshType::HEdgeContainer,bool> hV(m.hedge);
619 
620  hasHEF = (MeshType::HEdgeType::HasHFAdjacency());
621  assert( !hasHEF || (hasHEF && m.fn>0));
622 
623  // if the edgetype has the pointer to face
624  // it is assumed the the edget2face pointer (HEFp) are correct
625  // and the faces are allocated
626  for ( ei = m.hedge.begin(); ei != m.hedge.end(); ++ei)
627  if(!(*ei).IsD()) // it has not been deleted
628  if(!hasHEF || ( hasHEF && (*ei).HFp()!=NULL)) // if it has a pointer to the face it is
629  // not null (i.e. it is not a border edge)
630  if(!hV[(*ei)] ) // it has not be visited yet
631  {
632  if(!hasHEF)// if it has
633  fp = &(* Allocator<MeshType>::AddFaces(m,1));
634  else
635  fp = (*ei).HFp();
636 
637  ep = epF = &(*ei);
638  std::vector<VertexPointer> vpts;
639  do{vpts.push_back((*ep).HVp()); ep=ep->HNp();}while(ep!=epF);
640  //int idbg =fp->VN();
641  if(size_t(fp->VN()) != vpts.size()){
642  fp->Dealloc();
643  fp ->Alloc(vpts.size());
644  }
645  //int idbg1 =fp->VN();
646  for(size_t i = 0; i < vpts.size();++i) fp ->V(i) = vpts[i];// set the pointer from face to vertex
647 
648  hV[(*ei)] = true;
649  }
650  //Allocator<MeshType>::DeletePerHEdgeAttribute(m,hV);
651  }
652 
653  };
654  } // end namespace vcg
655 }
656 #endif // __VCGLIB_EDGE_SUPPORT