1 /****************************************************************************
2 * VCGLib                                                            o o     *
3 * Visual and Computer Graphics Library                            o     o   *
4 *                                                                _   O  _   *
5 * Copyright(C) 2004                                                \/)\/    *
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 HOLE_H
25 #define HOLE_H
26 
27 #include <utility>
28 #include <vector>
29 #include <qstring.h>
30 #include <float.h>
31 #include <GL/glew.h>
32 #include "vcg/simplex/face/pos.h"
33 #include "vcg/space/point3.h"
34 #include "vcg/complex/algorithms/clean.h"
35 #include "vcg/complex/algorithms/hole.h"
36 #include <vcg/complex/algorithms/closest.h>
37 #include <vcg/space/index/grid_static_ptr.h>
38 #include "vcg/space/color4.h"
39 #include "holeSetManager.h"
40 
41 /** An hole type, extends vcg::tri::Hole<MESH>::Info adding more information
42  *  as filling, selection, filing autocompenetration and non manifoldness.
43  *  This class also allows one to fill (and restore) an hole using different criteria.
44  *
45  *  FgtHole uses meshe's additional data to mark interesting face, so surfing
46  *  the hole faces is driven by face-face ajacency and mark meaning.
47  *  Additional data are accessible for an hole by parentManager (HoleSetManager)
48  *  which links hole to a mesh.
49  *  Characteristic faces for an hole are marked as:
50  *    - HoleBorderFace: face which initially (before filling) have 1 or 2 border edge.
51  *    - HolePatchFace: faces added to fill the hole
52  *    - PatchCompFace: patch faces which are selfintersected with mesh.
53  *    - BridgeFace: faces added to edit hole (unify 2 holes, subdivide an hole, partitioning a
54  *      non-manifold hole in more manifold ones)
55  *    - BridgeFace + HolePatchFace: this combo is used to individuate faces added to subdivide
56  *      a non manifold hole and also close a non manifold hole, ie an hole made up from only 3 edge
57  *
58  *        --------+-------+----+-----|     --------+-------+----+------|
59  *         hole   /\ hole /\  hole   |       hole  /\  f0  /\ f1| hole |  f0: BridgeFace + PatchFace
60  *           A   /  \  A /  \   A    |         A  /  \    /  \  |   B  |  f1: BridgeFace
61  *              /    \  /    \       |           /    \  /    \ |      |
62  *       ______/      \/      \______|    ______/      \/      \|______|
63  */
64 template <class MESH>
65 class FgtHole : public vcg::tri::Hole<MESH>::Info
66 {
67 public:
68 
69 private:
70   enum State
71   {
72     NONE      = 0x0000,
73     SELECTED  = 0x0001,
74     FILLED    = 0x0002,
75     ACCEPTED  = 0x0004,
76     COMPENET  = 0x0008,
77     NONMANIF  = 0x0010,
78     BRIDGED   = 0x0020
79   };
80 
81 public:
82 	enum FillerMode
83 	{
84 		Trivial, MinimumWeight, SelfIntersection
85 	};
86 
87 	typedef typename MESH::FaceType												FaceType;
88 	typedef typename MESH::FacePointer										FacePointer;
89 	typedef typename std::vector<FacePointer>							FacePointerVector;
90 	typedef typename MESH::VertexType											VertexType;
91 	typedef typename MESH::ScalarType											ScalarType;
92 	typedef typename vcg::face::Pos<FaceType>							PosType;
93 	typedef typename std::vector< PosType >								PosVector;
94 	typedef typename vcg::tri::Hole<MESH>									vcgHole;
95 	typedef typename vcgHole::Info												HoleInfo;
96 	typedef typename std::vector< FgtHole<MESH> >					HoleVector;
97 	typedef typename HoleVector::iterator									HoleIterator;
98 	typedef typename vcg::tri::TrivialEar<MESH>						TrivialEar;
99 	typedef typename vcg::tri::MinimumWeightEar<MESH>			MinimumWeightEar;
100 	typedef typename vcg::tri::SelfIntersectionEar<MESH>	SelfIntersectionEar;
101 
FgtHole(HoleInfo & hi,QString holeName,HoleSetManager<MESH> * parent)102 	FgtHole(HoleInfo &hi, QString holeName, HoleSetManager<MESH> *parent) :
103 		HoleInfo(hi.p, hi.size, hi.bb)
104 	{
105 		parentManager = parent;
106 		name = holeName;
107 		_state = ACCEPTED;
108 		perimeter = HoleInfo::Perimeter();
109 		findNonManifoldness();
110 	};
111 
FgtHole(PosType startPos,QString holeName,HoleSetManager<MESH> * parent)112 	FgtHole(PosType startPos, QString holeName, HoleSetManager<MESH> *parent)
113 	{
114 		assert(startPos.IsBorder());
115 		parentManager = parent;
116 		name = holeName;
117 		_state = ACCEPTED;
118 		this->p = startPos;
119 		updateInfo();
120 	};
121 
~FgtHole()122 	~FgtHole() {};
123 
Size()124 	inline int Size() const { return this->size; };
Perimeter()125 	inline ScalarType Perimeter() const	{ return this->perimeter; };
IsFilled()126 	inline bool IsFilled() const { return (_state & FILLED) != 0; };
IsSelected()127 	inline bool IsSelected() const { return (_state & SELECTED) != 0; };
IsCompenetrating()128 	inline bool IsCompenetrating() const { return IsFilled() && (_state & COMPENET) != 0; };
IsAccepted()129 	inline bool IsAccepted() const { return !IsFilled() || ( (_state & ACCEPTED) != 0); };
IsNonManifold()130 	inline bool IsNonManifold() const { return (_state & NONMANIF) != 0; };
IsBridged()131 	inline bool IsBridged() const { return (_state & BRIDGED) != 0;; };
SetBridged(bool val)132 	inline void SetBridged(bool val)
133 	{
134 	  if(val) _state |= BRIDGED;
135 	  else _state &= (~BRIDGED);
136   };
137 
SetSelect(bool val)138 	void SetSelect(bool val)
139 	{
140 		bool oldVal = IsSelected();
141 	  if(val) _state |= SELECTED;
142 	  else _state &= (~SELECTED);
143 		if(oldVal != val)
144 		{
145 			if(val) parentManager->nSelected++;
146 			else parentManager->nSelected--;
147 		}
148   };
149 
SetAccepted(bool val)150 	void SetAccepted(bool val)
151 	{
152 		bool oldVal = IsAccepted();
153 	  if(val) _state |= ACCEPTED;
154 	  else _state &= (~ACCEPTED);
155 		if(oldVal != val)
156 		{
157 			if(val) parentManager->nAccepted++;
158 			else parentManager->nAccepted--;
159 		}
160   };
161 
SetStartPos(PosType initP)162 	inline void SetStartPos(PosType initP)
163 	{
164 		assert(!IsFilled());
165 		this->p = initP;
166 		assert(this->p.IsBorder());
167 		updateInfo();
168 	};
169 
Draw()170 	void Draw() const
171 	{
172 		typename PosVector::const_iterator it = borderPos.begin();
173 		glBegin(GL_LINE_LOOP);
174 		for( ; it != borderPos.end(); it++)
175 			glVertex( it->v->P() );
176 		glEnd();
177 	};
178 
DrawCompenetratingFace(GLenum glmode)179 	void DrawCompenetratingFace(GLenum glmode) const
180 	{
181 		assert(IsCompenetrating());
182 
183 		typename std::vector<FacePointer>::const_iterator it;
184 
185 		glBegin(glmode);
186 		for( it=patches.begin(); it != patches.end(); it++)
187 			if( parentManager->IsCompFace(*it) )
188 			{
189 				glVertex( (*it)->V(0)->P() );
190 				glVertex( (*it)->V(1)->P() );
191 				glVertex( (*it)->V(2)->P() );
192 			}
193 
194 		glEnd();
195 	}
196 
197 	/*  Reset flags used by this plugin (holeBorder and patch) to unmark this hole and its patch.
198 	 */
ResetFlag()199 	void ResetFlag()
200 	{
201 		std::vector<FacePointer> bridgesFaces;
202 		if( IsFilled() )
203 		{
204 			typename std::vector<FacePointer>::iterator it;
205 
206 			while(patches.size()>0)
207 			{
208 			  FacePointer f = patches.back();
209         patches.pop_back();
210 				parentManager->ClearPatchAttr(f);
211 				parentManager->ClearCompAttr(f);
212 
213 				for(int i=0; i<3; i++)
214 				{
215 					FacePointer adjF = f->FFp(i);
216 					parentManager->ClearHoleBorderAttr(adjF);
217 				}
218 			}
219 		}
220 		else
221 		{
222 			// we can walk the border to find hole's faces added by bridges
223 			PosType curPos = this->p;
224 			do{
225 				parentManager->ClearHoleBorderAttr(curPos.f);
226 				curPos.NextB();
227 			}while( curPos != this->p );
228 		}
229 	};
230 
231 
232 	/* Restore hole, remove patch faces applied to mesh to fill this hole. */
RestoreHole()233 	void RestoreHole()
234 	{
235 		assert( IsFilled() );
236 		_state &= (~FILLED);
237 
238 		typename std::vector<FacePointer>::iterator it;
239 		for(it = patches.begin(); it!=patches.end(); it++)
240 		{
241 			// PathcHoleFlag+BridgeFaceFlag is special case
242 			if(parentManager->IsBridgeFace(*it)) continue;
243 
244 			assert(parentManager->IsPatchFace(*it));
245 			for(int e=0; e<3; e++)
246 			{
247 				if(!IsBorder(**it, e))
248 				{
249 					FacePointer adjF = (*it)->FFp(e);
250 					if(!parentManager->IsPatchFace(adjF))
251 					{
252 						int adjEI = (*it)->FFi(e);
253 						adjF->FFp( adjEI ) = adjF;
254 						adjF->FFi( adjEI ) = adjEI;
255 						assert(IsBorder(*adjF, adjEI));
256 					}
257 				}
258 			}
259 			if(!(**it).IsD())
260 				vcg::tri::Allocator<MESH>::DeleteFace(*parentManager->mesh, **it);
261 		}
262 		patches.clear();
263 	};
264 
Fill(FillerMode mode,MESH & mesh,std::vector<FacePointer * > & local_facePointer)265 	void Fill(FillerMode mode, MESH &mesh, std::vector<FacePointer * > &local_facePointer)
266 	{
267 		assert(!IsFilled());
268 		assert(this->p.IsBorder());
269 		switch(mode)
270 		{
271 		case FgtHole<MESH>::Trivial:
272 				vcgHole::template FillHoleEar< TrivialEar >(mesh, this->p, local_facePointer);
273 			break;
274 		case FgtHole<MESH>::MinimumWeight:
275 				vcgHole::template FillHoleEar< MinimumWeightEar >(mesh, this->p, local_facePointer);
276 			break;
277 		case FgtHole<MESH>::SelfIntersection:
278 				std::vector<FacePointer * > vfp = local_facePointer;
279 				SelfIntersectionEar::AdjacencyRing().clear();
280 				PosType ip = this->p;
281 				do
282 				{
283 					PosType inp = ip;
284 					do
285 					{
286 						inp.FlipE();
287 						inp.FlipF();
288 						SelfIntersectionEar::AdjacencyRing().push_back(inp.f);
289 					} while(!inp.IsBorder());
290 					ip.NextB();
291 				}while(ip != this->p);
292 
293 				typename std::vector<FacePointer>::iterator fpi = SelfIntersectionEar::AdjacencyRing().begin();
294         for( ; fpi != SelfIntersectionEar::AdjacencyRing().end(); ++fpi)
295 					vfp.push_back( &*fpi );
296 
297 				vcgHole::template FillHoleEar< SelfIntersectionEar >(mesh, this->p, vfp);
298 				SelfIntersectionEar::AdjacencyRing().clear();
299 			break;
300 		}
301 
302 		// hole filling leaves V flag to border vertex... resetting!
303 		typename PosVector::const_iterator it = borderPos.begin();
304 		for( ;it!=borderPos.end(); it++)
305 				it->v->ClearV();
306 
307 		parentManager->faceAttr->UpdateSize();
308 
309 		_state |= FILLED;
310 		_state |= ACCEPTED;
311 		_state &= (~COMPENET);
312 	}
313 
314 	/* Check if face is a border face of this hole */
HaveBorderFace(FacePointer bFace)315 	bool HaveBorderFace(FacePointer bFace) const
316 	{
317 		assert(parentManager->IsHoleBorderFace(bFace));
318 		typename PosVector::const_iterator it;
319 		for(it=borderPos.begin(); it!= borderPos.end(); it++)
320 			if( bFace == it->f )
321 				return true;
322 		return false;
323 	}
324 
325 	/* Check if pFace is a patch face of this hole */
HavePatchFace(FacePointer pFace)326 	bool HavePatchFace(FacePointer pFace) const
327 	{
328 		assert( parentManager->IsPatchFace(pFace) );
329 		if( !IsFilled() )
330 			return false;
331 
332 		typename std::vector<FacePointer>::const_iterator it;
333 		for(it = patches.begin(); it!=patches.end(); it++)
334 			if(pFace == *it)
335 				return true;
336 		return false;
337 	};
338 
339 	/*  walk over hole border, watching each adiacent faces to its vertex
340 	 *  looking for bridge faces.
341 	 */
UpdateBridgingStatus()342 	void UpdateBridgingStatus()
343 	{
344 		assert(!IsFilled());
345 		PosType curPos = this->p;
346 		do{
347 			do{
348 				if( parentManager->IsBridgeFace(curPos.f) )
349 				{
350 					SetBridged(true);
351 					return;
352 				}
353 				curPos.FlipE();
354 				curPos.FlipF();
355 			}while(!curPos.IsBorder());
356 			curPos.FlipV();
357 		}while(curPos != this->p);
358 		SetBridged(false);
359 	};
360 
361 	// concats its face reference to a vector
AddFaceReference(std::vector<FacePointer * > & facesReferences)362 	void AddFaceReference(std::vector<FacePointer*> &facesReferences)
363 	{
364 	  facesReferences.push_back(&this->p.f);
365 
366 		typename PosVector::iterator pit;
367 		for(pit=borderPos.begin(); pit != borderPos.end(); pit++)
368 			facesReferences.push_back( &pit->f );
369 
370 	  typename std::vector<FacePointer>::iterator fit;
371 	  for(fit=patches.begin(); fit!=patches.end(); fit++)
372       facesReferences.push_back(&*fit);
373 	};
374 
375 private:
376 
377 	/*  Walking the hole computing vcgHole::Info data and other info */
updateInfo()378 	void updateInfo()
379 	{
380 		assert(!IsFilled());
381 		borderPos.clear();
382 		_state &= (~NONMANIF);
383 		this->bb.SetNull();
384 		this->size = 0;
385 
386 		PosType curPos = this->p;
387 		do{
388 			assert(!curPos.f->IsD());
389 			borderPos.push_back(curPos);
390 			parentManager->SetHoleBorderAttr(curPos.f);
391 			this->bb.Add(curPos.v->cP());
392 			++this->size;
393 			if(curPos.v->IsV())
394 				_state |= NONMANIF;
395 			else
396 				curPos.v->SetV();
397 			curPos.NextB();
398 			assert(curPos.IsBorder());
399 		}while( curPos != this->p );
400 
401 		curPos = this->p;
402 		do{
403 			curPos.v->ClearV();
404 			curPos.NextB();
405 		}while( curPos != this->p );
406 
407 		perimeter = HoleInfo::Perimeter();
408 	};
409 
410 	/*  Walking the hole storing vertices and finding non manifold one */
findNonManifoldness()411 	void findNonManifoldness()
412 	{
413 		assert(!IsFilled());
414 		_state &= (~NONMANIF);
415 		PosType curPos = this->p;
416 		do{
417 			borderPos.push_back(curPos);
418 			if(curPos.v->IsV())
419 				_state |= NONMANIF;
420 			else
421 				curPos.v->SetV();
422 			curPos.NextB();
423 		}while( curPos != this->p );
424 
425 		curPos = this->p;
426 		do{
427 			curPos.v->ClearV();
428 			curPos.NextB();
429 		}while( curPos != this->p );
430 	};
431 
432 	/* set patch flag and auto-compenetration	flag when needed */
updatePatchState(int patchFlag)433 	void updatePatchState(int patchFlag)
434 	{
435 		assert( IsFilled() );
436 		_state &= (~COMPENET);
437 		vcg::GridStaticPtr<FaceType, ScalarType > gM;
438 		gM.Set(parentManager->mesh->face.begin(),parentManager->mesh->face.end());
439 
440 		std::vector<FaceType*> inBox;
441 		vcg::Box3< ScalarType> bbox;
442 	  getPatchFaces(patchFlag);
443 		typename FacePointerVector::iterator pi = patches.begin();
444 		for( ; pi!=patches.end(); ++pi)
445 		{
446 			FacePointer f = *pi;
447 			if(TestFaceMeshCompenetration(*parentManager->mesh, gM, f))
448 			{
449 				_state |= COMPENET;
450 				parentManager->SetCompAttr(f);
451 			}
452 			(*pi)->ClearUserBit(patchFlag);
453 			parentManager->SetPatchAttr(*pi);
454 		}
455 	};
456 
457 
458 	/* First patch face is the adjacent one to initial Pos ("p" field of Hole::Info)
459 	 * Other patch face are found looking adjacent face on each vertex of known patch faces.
460 	 * NB: looking adjacent faces to vertices it can find patches also for non manifold hole.
461 	 */
getPatchFaces(int patchFlag)462 	void getPatchFaces(int patchFlag)
463 	{
464 		assert( IsFilled() );
465 		patches.clear();
466 		std::vector<FacePointer> stack;
467 		PosType pos = this->p;
468 		pos.FlipF();
469 		assert(pos.f->IsUserBit(patchFlag));
470 		pos.f->SetV();
471 		stack.push_back(pos.f);
472 		while(stack.size()>0)
473 		{
474 			FacePointer f = stack.back();
475 			stack.pop_back();
476 			patches.push_back(f);
477 
478 			// visit faces adjacent to f's vertices
479 			for(int v=0; v<3; v++)
480 			{
481 				pos = PosType(f, v);
482 				do{
483 					pos.FlipF();
484 					pos.FlipE();
485 					if(pos.f->IsUserBit(patchFlag) && !pos.f->IsV())
486 					{
487 						pos.f->SetV();
488 						stack.push_back(pos.f);
489 					}
490 				}while(pos.f != f);
491 			}
492 		}
493 
494 		typename std::vector<FacePointer>::iterator it;
495 		for(it=patches.begin(); it!=patches.end(); ++it)
496 			(*it)->ClearV();
497 	};
498 
499 	/********* Static functions **********/
500 public:
501 
TestFaceMeshCompenetration(MESH & mesh,vcg::GridStaticPtr<FaceType,ScalarType> & gM,const FacePointer f)502 	static bool TestFaceMeshCompenetration(MESH &mesh, vcg::GridStaticPtr<FaceType, ScalarType > &gM,
503 			const FacePointer f)
504 	{
505 		std::vector<FaceType*> inBox;
506 		vcg::Box3< ScalarType> bbox;
507 
508 		f->GetBBox(bbox);
509 		vcg::tri::GetInBoxFace(mesh, gM, bbox,inBox);
510 
511 		typename std::vector<FaceType*>::iterator fib;
512 		for(fib=inBox.begin();fib!=inBox.end();++fib)
513 		{
514 			if (f != *fib)
515 			{
516 				if(vcg::tri::Clean<MESH>::TestFaceFaceIntersection( *fib, f ))
517 					return true;
518 			}
519 		}
520 		return false;
521 	};
522 
523 
524 public:
HoleId()525 	static int &HoleId(){static int _holeId=0; return _holeId;};
ResetHoleId()526 	static void ResetHoleId() { HoleId()=0; };
GetHoleId()527 	static int GetHoleId() { return ++HoleId(); };
528 	QString name;
529 
530 public:
531 	HoleSetManager<MESH>* parentManager;
532 	std::vector<FacePointer> patches;
533 
534 private:
535 	int _state;
536 	ScalarType perimeter;
537 
538 	std::vector<PosType> borderPos;
539 
540 };
541 
542 #endif
543