1 #ifndef TOPOLOGICALOP_H_
2 #define TOPOLOGICALOP_H_
3
4 /****************************************************************************
5 * Rgb Triangulations Plugin *
6 * *
7 * Author: Daniele Panozzo (daniele.panozzo@gmail.com) *
8 * Copyright(C) 2007 *
9 * DISI - Department of Computer Science *
10 * University of Genova *
11 * *
12 * All rights reserved. *
13 * *
14 * This program is free software; you can redistribute it and/or modify *
15 * it under the terms of the GNU General Public License as published by *
16 * the Free Software Foundation; either version 2 of the License, or *
17 * (at your option) any later version. *
18 * *
19 * This program is distributed in the hope that it will be useful, *
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
22 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
23 * for more details. *
24 ****************************************************************************/
25
26
27 #include <vcg/simplex/face/topology.h>
28 #include <vcg/complex/complex.h>
29 #include <vector>
30 #include <list>
31 #include <vcg/complex/allocate.h>
32 #include <iostream>
33
34 #include <vcg/space/color4.h>
35
36 namespace rgbt
37 {
38
39 using std::list;
40 using namespace vcg;
41 using std::vector;
42
43 /// Identify an Edge by the pair Face, Index on the face
44 template<class FacePointer> class EdgeFI
45 {
46 public:
EdgeFI(FacePointer fp,int i)47 EdgeFI(FacePointer fp, int i)
48 {
49 assert(i>=0 && i<= 2);
50 assert(fp);
51 this->fp = fp;
52 this->i = i;
53 }
54
EdgeFI()55 EdgeFI() {}
56
57 FacePointer fp;
58 int i;
59 };
60
61 /// Contains the operation to update the topological structure of the triangulation
62 /*
63 * Efficiently implement a garbage collect mechanism for vertex and triangle
64 */
65 template <class TRI_MESH_TYPE, class VERTEXC = vector<int>, class FACEC = vector<int> >
66 class TopologicalOp
67 {
68 public:
69
70 /// The tetrahedral mesh type
71 typedef TRI_MESH_TYPE TriMeshType;
72 /// The face type
73 typedef typename TriMeshType::FaceType FaceType;
74 /// The vertex type
75 typedef typename FaceType::VertexType VertexType;
76 /// The vertex type pointer
77 typedef typename FaceType::VertexType* VertexPointer;
78 /// The vertex iterator type
79 typedef typename TriMeshType::VertexIterator VertexIterator;
80 /// The tetra iterator type
81 typedef typename TriMeshType::FaceIterator FaceIterator;
82 /// The coordinate type
83 typedef typename FaceType::VertexType::CoordType CoordType;
84 /// The scalar type
85 typedef typename TriMeshType::VertexType::ScalarType ScalarType;
86 ///the container of tetrahedron type
87 typedef typename TriMeshType::FaceContainer FaceContainer;
88 ///the container of vertex type
89 typedef typename TriMeshType::VertContainer VertContainer;
90 ///half edge type
91 typedef typename TriMeshType::FaceType::EdgeType EdgeType;
92 /// vector of pos
93 typedef typename std::vector<EdgeType> EdgeVec;
94 ///of VFIterator
95 typedef typename vcg::face::VFIterator<FaceType> VFI;
96 /// vector of VFIterator
97 typedef typename std::vector<vcg::face::VFIterator<FaceType> > VFIVec;
98 /// Face Pointer
99 typedef typename TriMeshType::FacePointer FacePointer;
100 /// Edge defined by Face and Index
101 typedef EdgeFI<FacePointer> EdgeFIType;
102
103
104 private:
105 /// Working mesh (needed for the insert and garbage collect of faces and vertexes)
106 TriMeshType& m;
107 /// List of deleted faces that can be reused
108 list<FacePointer> listFp;
109 /// Size of listFp (size() is in O(n))
110 int sizelistFp;
111 /// List of deleted vertexes that can be reused
112 list<VertexPointer> listVp;
113 /// Size of listVp (size() is in O(n))
114 int sizelistVp;
115 /// Additional container that is reallocated if the vertex container is reallocated
116 VERTEXC *vc;
117 /// Additional container that is reallocated if the face container is reallocated
118 FACEC *fc;
119 //! Faces to add when the faces container is reallocated. The number is calculated by growNumberFace * oldNumberOfFace
growNumberFace()120 static const float growNumberFace() { return 2; }
121 //! Vertexes to add when the vertexes container is reallocated. The number is calculated by growNumberVertex * oldNumberOfVertex
growNumberVertex()122 static const float growNumberVertex() { return 2; }
123
124 public:
125 /// Create a new TopologicalOp
126 /**
127 * vc and fc are container for other information linked with the vertex and face container
128 * that need the same resize of the mesh containers
129 */
m(m)130 TopologicalOp(TriMeshType& m, VERTEXC* vc = 0, FACEC* fc = 0) : m(m), vc(vc), fc(fc)
131 {
132 updateLists();
133 }
134
135 //! Perform an edge collapse on the specified edge
136 /*
137 * If vfp is given push on the vector the pointer at the face (in order) f00,f01,f10,f11
138 */
139
140
141 template<bool BOUNDARY>
142 void doCollapse(EdgeFIType Edge, const Point3<ScalarType> *p, vector<FacePointer> *vfp = 0)
143 {
144
145 assert(FaceType::HasFFAdjacency());
146
147 assert(Edge.fp);
148 assert(Edge.i>= 0 && Edge.i <= 2);
149
150 FacePointer f0p = Edge.fp;
151 int f0i = Edge.i;
152
153 std::vector<FacePointer> vec;
154 vec.reserve(6);
155 getAllFacesAroundVertex(f0p,(f0i+1)%3,vec,BOUNDARY);
156
157 FacePointer f00p = 0;
158 int f00i = -1;
159 FacePointer f01p = 0;
160 int f01i = -1;
161
162 FacePointer f1p = 0;
163 int f1i;
164 FacePointer f10p = 0;
165 int f10i = -1;
166 FacePointer f11p = 0;
167 int f11i = -1;
168
169 if (f0p->FFp((f0i+2)%3) != f0p) // it exists a triangle f00
170 {
171 f00p = f0p->FFp((f0i+2)%3);
172 f00i = f0p->FFi((f0i+2)%3);
173 }
174
175 if (f0p->FFp((f0i+1)%3) != f0p) // it exists a triangle f01
176 {
177 f01p = f0p->FFp((f0i+1)%3);
178 f01i = f0p->FFi((f0i+1)%3);
179 }
180
181 if (!BOUNDARY)
182 {
183 assert(f0p->FFp(f0i) != f0p); // it must exists a triangle f1 or this is a boundary configuration
184 f1p = f0p->FFp(f0i);
185 f1i = f0p->FFi(f0i);
186
187 assert(f1p);
188 assert(f1i>= 0 && f1i <= 2);
189
190 if (f1p->FFp((f1i+1)%3) != f1p)
191 {
192 f10p = f1p->FFp((f1i+1)%3);
193 f10i = f1p->FFi((f1i+1)%3);
194 }
195 if (f1p->FFp((f1i+2)%3) != f1p)
196 {
197 f11p = f1p->FFp((f1i+2)%3);
198 f11i = f1p->FFi((f1i+2)%3);
199 }
200 }
201
202 if (f00p)
203 {
204 if (f01p)
205 {
206 f00p->FFp(f00i) = f01p;
207 f00p->FFi(f00i) = f01i;
208 }
209 else
210 {
211 f00p->FFp(f00i) = f00p;
212 f00p->FFi(f00i) = f00i;
213 }
214
215 }
216
217 if (f01p)
218 {
219 if (f00p)
220 {
221 f01p->FFp(f01i) = f00p;
222 f01p->FFi(f01i) = f00i;
223 }
224 else
225 {
226 f01p->FFp(f01i) = f01p;
227 f01p->FFi(f01i) = f01i;
228 }
229
230 }
231
232 if (!BOUNDARY)
233 {
234 if (f10p)
235 {
236 if (f11p)
237 {
238 f10p->FFp(f10i) = f11p;
239 f10p->FFi(f10i) = f11i;
240 }
241 else
242 {
243 f10p->FFp(f10i) = f10p;
244 f10p->FFi(f10i) = f10i;
245 }
246 }
247
248 if (f11p)
249 {
250 if (f10p)
251 {
252 f11p->FFp(f11i) = f10p;
253 f11p->FFi(f11i) = f10i;
254 }
255 else
256 {
257 f11p->FFp(f11i) = f11p;
258 f11p->FFi(f11i) = f11i;
259 }
260
261 }
262 }
263
264 // warning: this update at the relation VF* of the vertex
265 // break the relation VF on the face
266
267 if (VertexType::HasVFAdjacency())
268 {
269 //assert(!FaceType::HasVFAdjacency());
270 assert(f01p||f00p);
271 if (f01p)
272 {
273 assert(f01p);
274 f0p->V((f0i+2)%3)->VFp() = f01p;
275 f0p->V((f0i+2)%3)->VFi() = f01i;
276
277 f0p->V(f0i)->VFp() = f01p;
278 f0p->V(f0i)->VFi() = (f01i+1)%3;
279 }
280 else
281 {
282 assert(f00p);
283 f0p->V((f0i+2)%3)->VFp() = f00p;
284 f0p->V((f0i+2)%3)->VFi() = (f00i+1)%3;
285 f0p->V(f0i)->VFp() = f00p;
286 f0p->V(f0i)->VFi() = f00i;
287 }
288
289 //f0p->V((f0i+1)%3)->VFp() = f11p;
290 //f0p->V((f0i+1)%3)->VFi() = f11i;
291 if (!BOUNDARY)
292 {
293 assert(f11p || f10p);
294 assert(f11p);
295 f1p->V((f1i+2)%3)->VFp() = f11p;
296 f1p->V((f1i+2)%3)->VFi() = (f11i+1)%3;
297 }
298 }
299
300 f0p->SetD();
301 if (!BOUNDARY)
302 f1p->SetD();
303
304 if (!BOUNDARY)
305 m.fn -= 2;
306 else
307 m.fn -= 1;
308
309 if (!BOUNDARY)
310 assert(f0p->V(f0i) == f1p->V((f1i+1)%3));
311
312 VertexPointer v = f0p->V(f0i);
313 VertexPointer v1 = f0p->V((f0i + 1)%3);
314 if (p)
315 v->P() = *p;
316
317 // update all face around vertex v1
318 typedef typename std::vector<FacePointer>::iterator FaceIt;
319 FaceIt iter;
320 for (iter = vec.begin(); iter != vec.end(); ++iter)
321 {
322 for (int j = 0; j < 3; ++j)
323 {
324 if ((*iter)->V(j) == v1)
325 (*iter)->V(j) = v;
326 }
327
328 }
329
330 v1->SetD();
331 --(m.vn);
332
333 if (vfp)
334 {
335 if (f00p)
336 vfp->push_back(f00p);
337 if (f01p)
338 vfp->push_back(f01p);
339
340 if (!BOUNDARY)
341 {
342 vfp->push_back(f10p);
343 vfp->push_back(f11p);
344 }
345 }
346 if (f00p)
347 assert(FFCorrectness(f00p));
348 if (f01p)
349 assert(FFCorrectness(f01p));
350 if (!BOUNDARY)
351 {
352 if (f10p)
353 assert(FFCorrectness(f10p));
354 if (f11p)
355 assert(FFCorrectness(f11p));
356 }
357 if (f00p)
358 assert(VFCorrectness(f00p));
359 if (f01p)
360 assert(VFCorrectness(f01p));
361 if (!BOUNDARY)
362 {
363 if (f10p)
364 assert(VFCorrectness(f10p));
365 if (f11p)
366 assert(VFCorrectness(f11p));
367 }
368 }
369 //! Perform an edge collaps
370 void doCollapse(FacePointer fp, int EdgeIndex, Point3<ScalarType> *p = 0, vector<FacePointer> *vfp = 0)
371 {
372 //const Point3<ScalarType> p2 = p;
373 EdgeFIType e = EdgeFIType(fp,EdgeIndex);
374 doCollapse<false>(e,p,vfp);
375 }
376 //! Perform an edge collaps on the boundary
377 void doCollapseBoundary(FacePointer fp, int EdgeIndex, Point3<ScalarType> *p = 0, vector<FacePointer> *vfp = 0)
378 {
379 //const Point3<ScalarType> p2 = p;
380 EdgeFIType e = EdgeFIType(fp,EdgeIndex);
381 doCollapse<true>(e,p,vfp);
382 }
383
384 //! Extract in v all faces around the specified vertex
385 /// It is necessary to specify if the vertex is on the boundary
getAllFacesAroundVertex(FacePointer fp,int i,std::vector<FacePointer> & v,bool isBoundary)386 void getAllFacesAroundVertex(FacePointer fp, int i,std::vector<FacePointer> &v,bool isBoundary)
387 {
388 v.clear();
389 if (!fp) return;
390 assert(i>= 0 && i<=2);
391 vcg::face::Pos<CMeshO::FaceType> pos(fp,fp->V(i));
392
393 if (isBoundary) // if is border move cw until the border is found
394 {
395 pos.FlipE();
396 pos.FlipF();
397
398 while (!pos.IsBorder())
399 {
400 pos.FlipE();
401 pos.FlipF();
402 }
403
404 pos.FlipE();
405 }
406
407
408 CMeshO::FacePointer first = pos.F();
409 v.push_back(pos.F());
410 pos.FlipF();
411 pos.FlipE();
412 while(pos.F() != first)
413 {
414 v.push_back(pos.F());
415 if (pos.IsBorder())
416 break;
417 pos.FlipF();
418 pos.FlipE();
419 }
420 }
421
422 //! Perform an edge split on the specified edge
423 /*
424 * If vfp is given push on the vector the pointer at the face (in order) f0,f1,f2,f3
425 */
426 template<bool BOUNDARY>
427 void doSplit(EdgeFIType Edge, const Point3<ScalarType> &p, vector<FacePointer> *vfp = 0, vector<VertexPointer> *vvp = 0)
428 {
429 assert(FaceType::HasFFAdjacency());
430
431 assert(Edge.fp);
432 assert(Edge.i>= 0 && Edge.i <= 2);
433
434 int index = Edge.fp->Index();
435
436 FacePointer f2p = getNewFace(1); // This line must allocate the space also for the next call
437 int f2i = 0;
438
439 FacePointer f3p = 0;
440 int f3i = 0;
441
442 if (!BOUNDARY)
443 {
444 f3p = getNewFace(0);
445 f3i = 0;
446 }
447
448 VertexPointer v2 = getNewVertex();
449 v2->P() = p;
450
451 Edge.fp = &m.face[index];
452
453 FacePointer f0p = Edge.fp;
454 int f0i = (Edge.i + 1)%3;
455
456 VertexPointer v1 = f0p->V(f0i);
457
458 FacePointer f00p = f0p->FFp((f0i+1)%3);
459 //int f00i = f0p->FFi((f0i+1)%3);
460
461 FacePointer f01p = f0p->FFp((f0i)%3);
462 int f01i = f0p->FFi((f0i)%3);
463
464 FacePointer f1p = 0;
465 int f1i = 0;
466
467 FacePointer f10p = 0;
468 int f10i = 0;
469
470 FacePointer f11p = 0;
471 int f11i = 0;
472 if (!BOUNDARY)
473 {
474 f1p = f0p->FFp((f0i+2)%3);
475 f1i = f0p->FFi((f0i+2)%3);
476 assert(f1p);
477 assert(f0p->V(f0i) == f1p->V(f1i));
478
479 f10p = f1p->FFp((f1i+1)%3);
480 f10i = f1p->FFi((f1i+1)%3);
481 f11p = f1p->FFp((f1i+2)%3);
482 f11i = f1p->FFi((f1i+2)%3);
483
484 }
485
486 if (!BOUNDARY)
487 {
488 // FF triangle f2
489 f2p->FFp((f2i)%3) = f3p;
490 f2p->FFi((f2i)%3) = (f3i+2)%3;
491 }
492 else
493 {
494 // FF triangle f2
495 f2p->FFp((f2i)%3) = f2p;
496 f2p->FFi((f2i)%3) = f2i;
497 }
498
499
500 if (f0p->FFp(f0i) != f0p) // it exists a face f01
501 {
502 f2p->FFp((f2i+1)%3) = f01p;
503 f2p->FFi((f2i+1)%3) = f01i;
504 }
505 else
506 {
507 f2p->FFp((f2i+1)%3) = f2p;
508 f2p->FFi((f2i+1)%3) = (f2i+1)%3;
509 }
510 f2p->FFp((f2i+2)%3) = f0p;
511 f2p->FFi((f2i+2)%3) = f0i;
512 if (!BOUNDARY)
513 {
514
515 // FF triangle f3
516 f3p->FFp((f3i)%3) = f1p;
517 f3p->FFi((f3i)%3) = (f1i+2)%3;
518
519 if (f1p->FFp((f1i+2)%3) != f1p) // it exists a face f11
520 {
521 f3p->FFp((f3i+1)%3) = f11p;
522 f3p->FFi((f3i+1)%3) = f11i;
523 }
524 else
525 {
526 f3p->FFp((f3i+1)%3) = f3p;
527 f3p->FFi((f3i+1)%3) = (f3i+1)%3;
528 }
529
530 f3p->FFp((f3i+2)%3) = f2p;
531 f3p->FFi((f3i+2)%3) = f2i;
532 }
533 // FF triangle f01
534 f01p->FFp(f01i) = f2p;
535 f01p->FFi(f01i) = (f2i+1)%3;
536
537 if (!BOUNDARY)
538 {
539
540 // FF triangle f11
541 f11p->FFp(f11i) = f3p;
542 f11p->FFi(f11i) = (f3i+1)%3;
543 }
544 // FF triangle f0
545 f0p->FFp(f0i) = f2p;
546 f0p->FFi(f0i) = (f2i+2)%3;
547
548 if (!BOUNDARY)
549 {
550
551 // FF triangle f1
552 f1p->FFp((f1i+2)%3) = f3p;
553 f1p->FFi((f1i+2)%3) = f3i;
554 }
555
556 // FV
557 f0p->V(f0i) = v2;
558 if (!BOUNDARY)
559 {
560 f1p->V(f1i) = v2;
561 }
562
563 f2p->V(f2i) = v2;
564 f2p->V((f2i+1)%3) = v1;
565 f2p->V((f2i+2)%3) = f0p->V((f0i+1)%3);
566
567 assert(f2p->V(f2i) == f0p->V(f0i));
568
569 if (!BOUNDARY)
570 {
571
572 f3p->V(f3i) = v2;
573 f3p->V((f3i+1)%3) = f1p->V((f1i+2)%3);
574 f3p->V((f3i+2)%3) = v1;
575 }
576 // Detach old vertex from f0 and f1
577 f0p->V(f0i) = v2;
578
579 if (!BOUNDARY)
580 {
581 f1p->V(f1i) = v2;
582 }
583
584 if (VertexType::HasVFAdjacency())
585 {
586 //assert(!FaceType::HasVFAdjacency());
587 v2->VFp() = f0p;
588 v2->VFi() = f0i;
589 v1->VFp() = f2p;
590 v1->VFi() = (f2i+1)%3;
591 }
592
593 if (vfp)
594 {
595 vfp->push_back(f0p);
596 if (!BOUNDARY)
597 {
598 vfp->push_back(f1p);
599 }
600 vfp->push_back(f2p);
601 if (!BOUNDARY)
602 {
603 vfp->push_back(f3p);
604 }
605 }
606
607 if (vvp)
608 {
609 vvp->push_back(v2);
610 }
611
612 assert(FFCorrectness(f0p));
613
614 if (!BOUNDARY)
615 {
616 assert(FFCorrectness(f1p));
617 }
618 assert(FFCorrectness(f2p));
619 if (!BOUNDARY)
620 {
621 assert(FFCorrectness(f3p));
622 }
623 assert(FFCorrectness(f00p));
624 assert(FFCorrectness(f01p));
625 if (!BOUNDARY)
626 {
627 assert(FFCorrectness(f10p));
628 assert(FFCorrectness(f11p));
629 }
630
631 assert(VFCorrectness(f0p));
632 if (!BOUNDARY)
633 {
634 assert(VFCorrectness(f1p));
635 }
636 assert(VFCorrectness(f2p));
637 if (!BOUNDARY)
638 {
639 assert(VFCorrectness(f3p));
640 }
641 assert(VFCorrectness(f00p));
642 assert(VFCorrectness(f01p));
643 if (!BOUNDARY)
644 {
645 assert(VFCorrectness(f10p));
646 assert(VFCorrectness(f11p));
647 }
648
649 }
650
651 //! Perform an edge split
652 void doSplit(FacePointer fp, int EdgeIndex, const Point3<ScalarType> &p = 0, vector<FacePointer> *vfp = 0, vector<VertexPointer> *vvp = 0)
653 {
654 //const Point3<ScalarType> p2 = p;
655 EdgeFIType e = EdgeFIType(fp,EdgeIndex);
656 doSplit<false>(e,p,vfp,vvp);
657 }
658
659 //! Perform an edge split
660 void doSplitBoundary(FacePointer fp, int EdgeIndex, const Point3<ScalarType> &p = 0, vector<FacePointer> *vfp = 0, vector<VertexPointer> *vvp = 0)
661 {
662 //const Point3<ScalarType> p2 = p;
663 EdgeFIType e = EdgeFIType(fp,EdgeIndex);
664 doSplit<true>(e,p,vfp,vvp);
665 }
666
667
668
669
670 private:
671 //! Update the list of vertexes and triangles that can be garbage-collected
updateLists()672 void updateLists()
673 {
674 listFp.clear();
675 sizelistFp = 0;
676 listVp.clear();
677 sizelistVp = 0;
678
679 FaceIterator fit = m.face.begin();
680 while(fit != m.face.end())
681 {
682 if (fit->IsD())
683 {
684 listFp.push_back(&*fit);
685 sizelistFp++;
686 }
687 ++fit;
688 }
689
690 VertexIterator vit = m.vert.begin();
691 while(vit != m.vert.end())
692 {
693 if (vit->IsD())
694 {
695 listVp.push_back(&*vit);
696 sizelistVp++;
697 }
698 ++vit;
699 }
700 }
701 //! Return a new face (if necessary the container is reallocated)
702 // The container must be reallocated also if otherneeded is greater than the free face
703 FacePointer getNewFace(int otherneeded = 0)
704 {
705 assert(otherneeded >= 0);
706 if (sizelistFp <= otherneeded)
707 {
708 list<int> l;
709
710 for (typename list<FacePointer>::iterator lit2 = listFp.begin(); lit2 != listFp.end(); ++lit2)
711 {
712 l.push_back((*lit2)->Index());
713 }
714
715 int newFaces = (int)(growNumberFace() * m.face.size()); // (float)fc->size());
716 newFaces += otherneeded + 1;
717 FaceIterator it = vcg::tri::Allocator<TriMeshType>::AddFaces(m,newFaces);
718 if (fc)
719 fc->resize(fc->size()+newFaces);
720
721 listFp.clear();
722 sizelistFp = 0;
723 for (list<int>::iterator lit = l.begin(); lit != l.end(); ++lit)
724 {
725 listFp.push_back(&m.face[*lit]);
726 sizelistFp++;
727 }
728
729 while(it != m.face.end())
730 {
731 listFp.push_back(&*it);
732 sizelistFp++;
733 it->SetD();
734 --(m.fn);
735 ++it;
736 }
737
738 }
739
740 assert(sizelistFp > otherneeded);
741
742 FacePointer fp = listFp.front();
743 listFp.pop_front();
744 sizelistFp--;
745 assert(fp->IsD());
746 fp->ClearD();
747 ++(m.fn);
748 return fp;
749 }
750
751 //! Return a new Vertex (if necessary the container is reallocated)
getNewVertex()752 VertexPointer getNewVertex()
753 {
754 if (sizelistVp <= 0)
755 {
756 int newVertexes = (int)(growNumberVertex() * m.vert.size());//(float)vc->size());
757 ++newVertexes;
758 VertexIterator it = vcg::tri::Allocator<TriMeshType>::AddVertices(m,newVertexes);
759 if (vc)
760 vc->resize(vc->size()+newVertexes);
761 while(it != m.vert.end())
762 {
763 listVp.push_back(&*it);
764 sizelistVp++;
765 it->SetD();
766 --(m.vn);
767 ++it;
768 }
769 }
770
771 assert(sizelistVp > 0);
772
773 VertexPointer vp = listVp.front();
774 listVp.pop_front();
775 sizelistVp--;
776 assert(vp->IsD());
777 vp->ClearD();
778 ++(m.vn);
779 return vp;
780 }
781
782
783
784
785 };
786 //! Test for FFCorrectess the face fp
787 template <class FacePointer>
FFCorrectness(FacePointer fp)788 bool FFCorrectness(FacePointer fp)
789 {
790 return (
791 vcg::face::FFCorrectness(*fp,0) &&
792 vcg::face::FFCorrectness(*fp,1) &&
793 vcg::face::FFCorrectness(*fp,2)
794 );
795 }
796 //! Test for the VF Correctness of a vertex
797 template <class FacePointer>
VFCorrectness(FacePointer fp)798 static bool VFCorrectness(FacePointer fp)
799 {
800 return (VFCorrectnessP(fp->V(0)) && VFCorrectnessP(fp->V(1)) && VFCorrectnessP(fp->V(2)));
801 }
802
803 //! Test for the VF Correctness of a vertex
804 template <class VertexPointer>
VFCorrectnessP(VertexPointer vp)805 static bool VFCorrectnessP(VertexPointer vp)
806 {
807 if (vp->IsD())
808 return false;
809 if (vp->VFp()->IsD())
810 return false;
811 int index = vp->VFi();
812
813 return (vp->VFp()->V(index) == vp);
814 }
815
816
817 /*!
818 * Check if the z-th edge of the face f can be flipped.
819 * \param f pointer to the face
820 * \param z the edge index
821 */
822 template <class FaceType>
CheckFlipEdge(FaceType & f,int z)823 static bool CheckFlipEdge(FaceType &f, int z)
824 {
825 if (z<0 || z>2)
826 return false;
827
828 // boundary edges cannot be flipped
829 if (face::IsBorder(f, z))
830 return false;
831
832 FaceType *g = f.FFp(z);
833 int w = f.FFi(z);
834
835 // check if the vertices of the edge are the same
836 if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
837 return false;
838
839 // check if the flipped edge is already present in the mesh
840 typedef typename FaceType::VertexType VertexType;
841 VertexType *f_v2 = f.V2(z);
842 VertexType *g_v2 = g->V2(w);
843 if (f_v2 == g_v2)
844 return false;
845
846 vcg::face::Pos< FaceType > pos(&f, (z+2)%3, f.V2(z));
847 do
848 {
849 pos.NextE();
850 if (g_v2==pos.f->V1(pos.z))
851 return false;
852 }
853 while (&f!=pos.f);
854
855 return true;
856 }
857
858 /*!
859 * Flip the z-th edge of the face f.
860 * Check for topological correctness first using <CODE>CheckFlipFace()</CODE>.
861 * \param f pointer to the face
862 * \param z the edge index
863 *
864 * Note: For <em>edge flip</em> we intend the swap of the diagonal of the rectangle
865 * formed by the face \a f and the face adjacent to the specified edge.
866 */
867 template <class FaceType>
FlipEdge(FaceType & f,const int z)868 static void FlipEdge(FaceType &f, const int z)
869 {
870 assert(z>=0);
871 assert(z<3);
872 assert( !IsBorder(f,z) );
873 assert( face::IsManifold<FaceType>(f, z));
874
875 FaceType *g = f.FFp(z);
876 int w = f.FFi(z);
877
878 assert( g->V(w) == f.V1(z) );
879 assert( g->V1(w)== f.V(z) );
880 assert( g->V2(w)!= f.V(z) );
881 assert( g->V2(w)!= f.V1(z) );
882 assert( g->V2(w)!= f.V2(z) );
883
884 f.V1(z) = g->V2(w);
885 g->V1(w) = f.V2(z);
886
887 f.FFp(z) = g->FFp((w+1)%3);
888 f.FFi(z) = g->FFi((w+1)%3);
889 g->FFp(w) = f.FFp((z+1)%3);
890 g->FFi(w) = f.FFi((z+1)%3);
891 f.FFp((z+1)%3) = g;
892 f.FFi((z+1)%3) = (w+1)%3;
893 g->FFp((w+1)%3) = &f;
894 g->FFi((w+1)%3) = (z+1)%3;
895
896 if(f.FFp(z)==g)
897 {
898 f.FFp(z) = &f;
899 f.FFi(z) = z;
900 }
901 else
902 {
903 f.FFp(z)->FFp( f.FFi(z) ) = &f;
904 f.FFp(z)->FFi( f.FFi(z) ) = z;
905 }
906 if(g->FFp(w)==&f)
907 {
908 g->FFp(w)=g;
909 g->FFi(w)=w;
910 }
911 else
912 {
913 g->FFp(w)->FFp( g->FFi(w) ) = g;
914 g->FFp(w)->FFi( g->FFi(w) ) = w;
915 }
916
917 if (g->V(0)->HasVFAdjacency()) // Vertex has vf adjacency
918 {
919 //assert(!FaceType::HasVFAdjacency());
920
921 f.V((z+0)%3)->VFp() = &f;
922 f.V((z+0)%3)->VFi() = z;
923
924 g->V((w+0)%3)->VFp() = g;
925 g->V((w+0)%3)->VFi() = w;
926
927 }
928
929
930 assert(FFCorrectness(&f));
931 assert(FFCorrectness(g));
932 assert(VFCorrectness(&f));
933 assert(VFCorrectness(g));
934 }
935
936 }
937
938 #endif /*TOPOLOGICALOP_H_*/
939