map3.cpp 16.1 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27 28 29 30 31 32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"

namespace CGoGN
{

/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
33 34

void Map3::deleteVolume(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
35 36 37 38
{
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
39
	visitedFaces.reserve(512);
Pierre Kraemer's avatar
Pierre Kraemer committed
40 41
	visitedFaces.push_back(d);			// Start with the face of d

untereiner's avatar
untereiner committed
42
	mark.markOrbitInParent(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43

44
	for(std::vector<Dart>::iterator face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
45 46 47 48 49 50 51 52 53 54 55
	{
		Dart e = *face ;

		unsewVolumes(e);

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
untereiner's avatar
untereiner committed
56
				mark.markOrbitInParent(FACE, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
57 58 59 60 61
			}
			e = phi1(e) ;
		} while(e != *face) ;
	}

untereiner's avatar
untereiner committed
62 63 64
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
65 66
}

67 68 69 70 71 72
void Map3::fillHole(Dart d)
{
	assert(isBoundaryMarked(d)) ;
	boundaryUnmarkOrbit(VOLUME, d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
73 74 75 76
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

77
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
78
{
79 80 81
	if(isBoundaryVertex(d))
		return NIL ;

untereiner's avatar
untereiner committed
82 83 84
	//Save the darts around the vertex
	//(one dart per face should be enough)
	std::vector<Dart> fstoretmp;
85
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
86 87 88 89 90
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

	//just one dart per face
	std::vector<Dart> fstore;
91
	fstore.reserve(128);
untereiner's avatar
untereiner committed
92 93
	DartMarker mf(*this);
	for(std::vector<Dart>::iterator it = fstoretmp.begin() ; it != fstoretmp.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
94
	{
untereiner's avatar
untereiner committed
95
		if(!mf.isMarked(*it))
96
		{
untereiner's avatar
untereiner committed
97 98 99
			mf.markOrbit(FACE, *it);
			fstore.push_back(*it);
		}
100
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
101

102
	Dart res = NIL ;
untereiner's avatar
untereiner committed
103 104
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
		Dart fit = *it ;
		Dart end = phi_1(fit) ;
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
			if(res == NIL)
				res = d2 ;
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
		}
untereiner's avatar
untereiner committed
120
	}
121
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
122

123
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
124 125 126 127 128 129 130 131
}

void Map3::cutEdge(Dart d)
{
	Dart prev = d;
	Dart dd = alpha2(d);
	Map2::cutEdge(d);

132
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
133 134 135 136 137 138
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

139 140 141 142
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
143 144
	}

145 146 147 148
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
149 150
}

Pierre Kraemer's avatar
Pierre Kraemer committed
151
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
152
{
Pierre Kraemer's avatar
Pierre Kraemer committed
153 154
	if(vertexDegree(phi1(d)) == 2)
	{
155 156
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
157

158 159
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
160 161 162
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
163

164 165
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
166 167
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
168 169
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
170
		return true;
untereiner's avatar
untereiner committed
171
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
172
	return false;
untereiner's avatar
untereiner committed
173 174
}

175
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
176
{
177
	assert(d != e && sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
178

179 180
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
181

untereiner's avatar
untereiner committed
182
	Map2::splitFace(d, e);
183
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
184

185 186
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
187 188
}

189
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
190 191 192
{
	assert(faceDegree(d) == faceDegree(e));

193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(phi3(d) == d && phi3(e) == e) ;
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
			phi3sew(fitD, fitE) ;
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

	Dart dd = phi3(d) ;
	Dart ee = phi3(e) ;

	Dart fitD = dd ;
	Dart fitE = ee ;
	do
	{
		Dart fitD2 = phi2(fitD) ;
		Dart fitE2 = phi2(fitE) ;
		if(fitD2 != fitE)
		{
			phi2unsew(fitD) ;
			phi2unsew(fitE) ;
			phi2sew(fitD2, fitE2) ;
			phi2sew(fitD, fitE) ;
		}
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
	Map2::deleteCC(dd) ;

229 230 231 232
	Dart fitD = d ;
	Dart fitE = e ;
	do
	{
233
		phi3sew(fitD, fitE) ;
234 235 236 237 238 239 240
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
241 242 243 244 245 246 247 248 249 250 251 252
	assert(!isBoundaryFace(d)) ;

	unsigned int nbE = faceDegree(d) ;
	Dart d3 = phi3(d);

	Dart b1 = newBoundaryCycle(nbE) ;
	Dart b2 = newBoundaryCycle(nbE) ;

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
253 254
	do
	{
untereiner's avatar
untereiner committed
255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
			phi2unsew(f) ;
			phi2sew(fitB1, f) ;
			phi2sew(fitB2, f2) ;
		}
		else
			phi2sew(fitB1, fitB2) ;

		phi3unsew(fit1) ;
		phi3sew(fit1, fitB1) ;
		phi3sew(fit2, fitB2) ;

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
275 276 277 278
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
279
	if(!Map3::isBoundaryFace(d))
280
	{
untereiner's avatar
untereiner committed
281
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
282 283 284 285 286
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
287 288
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
289 290
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
291 292 293 294 295 296 297
	Dart e = vd.front();
	Dart e2 = phi2(e);

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		Map2::unsewFaces(*it);

untereiner's avatar
untereiner committed
298 299
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
300

untereiner's avatar
untereiner committed
301 302
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
303 304
}

305 306 307 308
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

309
bool Map3::sameVertex(Dart d, Dart e)
310 311 312
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
313 314 315
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
316 317
	mv.mark(d);

untereiner's avatar
untereiner committed
318
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
319
	{
untereiner's avatar
untereiner committed
320
		if(*it == e)
321 322 323
			return true;

		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
324 325 326
		Dart d2 = phi2(*it);
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
327

untereiner's avatar
untereiner committed
328 329 330 331 332 333 334 335 336
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
337 338 339 340 341
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
342 343
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
344
	unsigned int count = 0;
untereiner's avatar
untereiner committed
345 346
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
347 348 349
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
untereiner's avatar
untereiner committed
350 351
	mv.mark(d);

untereiner's avatar
untereiner committed
352
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
353 354
	{
		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
355
		Dart d2 = phi2(*it);
untereiner's avatar
untereiner committed
356 357 358 359 360
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
361
			darts.push_back(d21);
untereiner's avatar
untereiner committed
362 363
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
364
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
365
		{
untereiner's avatar
untereiner committed
366
			darts.push_back(d23);
untereiner's avatar
untereiner committed
367 368 369 370 371
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
372
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
373
	{
untereiner's avatar
untereiner committed
374
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
375 376
		{
			++count;
untereiner's avatar
untereiner committed
377
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
378 379 380 381 382 383
		}
	}

	return count;
}

384 385
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
386
	DartMarkerStore mv(*this);	// Lock a marker
387

untereiner's avatar
untereiner committed
388 389 390
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
391 392
	mv.mark(d);

untereiner's avatar
untereiner committed
393
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
394
	{
untereiner's avatar
untereiner committed
395 396
		if(isBoundaryMarked(*it))
			return true ;
397 398

		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
399
		Dart d2 = phi2(*it);
400 401 402 403 404
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
405
			darts.push_back(d21);
406 407
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
408
		if(!mv.isMarked(d23))
409
		{
untereiner's avatar
untereiner committed
410
			darts.push_back(d23);
411 412 413
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
414
	return false ;
415 416 417 418
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
419
	Dart it = d;
420 421
	do
	{
untereiner's avatar
untereiner committed
422
		if(it == e)
423
			return true;
untereiner's avatar
untereiner committed
424 425
		it = alpha2(it);
	} while (it != d);
426 427 428
	return false;
}

untereiner's avatar
untereiner committed
429
unsigned int Map3::edgeDegree(Dart d)
430
{
untereiner's avatar
untereiner committed
431
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
432
	Dart it = d;
433 434
	do
	{
untereiner's avatar
untereiner committed
435 436 437
		++deg;
		it = alpha2(it);
	} while(it != d);
438 439 440
	return deg;
}

untereiner's avatar
untereiner committed
441
bool Map3::isBoundaryEdge(Dart d)
442
{
untereiner's avatar
untereiner committed
443 444 445 446 447 448 449 450
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
451 452
}

untereiner's avatar
untereiner committed
453
Dart Map3::findBoundaryFaceOfEdge(Dart d)
454
{
untereiner's avatar
untereiner committed
455 456 457 458 459 460 461 462
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
463 464
}

Pierre Kraemer's avatar
Pierre Kraemer committed
465 466
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
467
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
468 469

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
470
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
471
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
472
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
473

untereiner's avatar
untereiner committed
474
	for(std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
475
	{
untereiner's avatar
untereiner committed
476 477
		if (isBoundaryMarked(phi3(*it)))
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
478

untereiner's avatar
untereiner committed
479 480
		Dart e = *it ;
		do	// add all face neighbours to the table
Pierre Kraemer's avatar
Pierre Kraemer committed
481
		{
untereiner's avatar
untereiner committed
482 483
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
484
			{
untereiner's avatar
untereiner committed
485 486 487 488 489
				visitedFaces.push_back(ee) ;
				mark.markOrbit(ORIENTED_FACE, ee) ;
			}
			e = phi1(e) ;
		} while(e != *it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
490
	}
untereiner's avatar
untereiner committed
491
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
492 493
}

494
bool Map3::check()
495
{
496 497 498 499 500 501 502 503 504 505
    std::cout << "Check: topology begin" << std::endl;
    DartMarker m(*this);
    for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
    {
        Dart d3 = phi3(d);
        if (phi3(d3) != d) // phi3 involution ?
		{
            std::cout << "Check: phi3 is not an involution" << std::endl;
            return false;
        }
506

untereiner's avatar
untereiner committed
507 508 509 510 511
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
512

513 514 515 516 517 518
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
519

520 521 522 523 524 525
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
526

527
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
528
		{
529 530 531 532
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
533

534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
        if (d1 == d)
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;

        if (phi1(d1) == d)
            std::cout << "Check: (warning) face with only two edges" << std::endl;

        if (phi2(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;

        if (phi3(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
550
		{
551 552 553 554
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
555

556
    std::cout << "Check: topology ok" << std::endl;
557

558 559 560
    std::cout << "nb vertex orbits" << getNbOrbits(VERTEX) << std::endl ;
    std::cout << "nb vertex cells" << m_attribs[VERTEX].size() << std::endl ;

untereiner's avatar
untereiner committed
561 562 563 564 565 566 567 568 569
    std::cout << "nb edge orbits" << getNbOrbits(EDGE) << std::endl ;
    std::cout << "nb edge cells" << m_attribs[EDGE].size() << std::endl ;

    std::cout << "nb face orbits" << getNbOrbits(FACE) << std::endl ;
    std::cout << "nb face cells" << m_attribs[FACE].size() << std::endl ;

    std::cout << "nb volume orbits" << getNbOrbits(VOLUME) << std::endl ;
    std::cout << "nb volume cells" << m_attribs[VOLUME].size() << std::endl ;

570
    return true;
571 572
}

Pierre Kraemer's avatar
Pierre Kraemer committed
573 574 575 576
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
577
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
578
{
untereiner's avatar
untereiner committed
579
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
580 581
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
582 583 584
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
585 586
	mv.mark(d);

untereiner's avatar
untereiner committed
587
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
588 589
	{
		//add phi21 and phi23 successor if they are not marked yet
untereiner's avatar
untereiner committed
590 591 592
		Dart d2 = phi2(*it);
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
593

untereiner's avatar
untereiner committed
594 595 596 597 598 599 600 601 602
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
Pierre Kraemer's avatar
Pierre Kraemer committed
603 604
		}

untereiner's avatar
untereiner committed
605
		found = f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
606 607 608 609
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
610
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
611
{
untereiner's avatar
untereiner committed
612
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
613 614
	do
	{
untereiner's avatar
untereiner committed
615
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
616
			return true;
untereiner's avatar
untereiner committed
617 618
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
619 620 621
	return false;
}

untereiner's avatar
untereiner committed
622
bool Map3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
623
{
Sylvain Thery's avatar
Sylvain Thery committed
624
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
625 626
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
627 628 629
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(1024);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
630 631
	mv.mark(d);

untereiner's avatar
untereiner committed
632
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
633
	{
untereiner's avatar
untereiner committed
634
		Dart d1 = *it;
Pierre Kraemer's avatar
Pierre Kraemer committed
635

untereiner's avatar
untereiner committed
636 637
		// add all successors if they are not marked yet
		Dart d2 = phi1(d1); // turn in face
Pierre Kraemer's avatar
Pierre Kraemer committed
638 639 640
		Dart d3 = phi2(d1); // change face
		Dart d4 = phi3(d1); // change volume

untereiner's avatar
untereiner committed
641 642 643 644 645
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
646 647
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
648 649
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
650 651 652
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
653
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
654 655 656 657 658 659 660 661
			mv.mark(d4);
		}

		found = f(d1);
	}
	return found;
}

untereiner's avatar
untereiner committed
662 663 664
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
665

untereiner's avatar
untereiner committed
666
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
667
{
untereiner's avatar
untereiner committed
668
	assert(phi3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
669

untereiner's avatar
untereiner committed
670 671 672
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
Pierre Kraemer's avatar
Pierre Kraemer committed
673

untereiner's avatar
untereiner committed
674
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
675

untereiner's avatar
untereiner committed
676 677
	// For every face added to the list
	for (std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
678
	{
untereiner's avatar
untereiner committed
679 680 681 682
		Dart f = *it ;
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
683

untereiner's avatar
untereiner committed
684 685
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
686
		{
untereiner's avatar
untereiner committed
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
					visitedFaces.push_back(e) ;
				}
				else if(isBoundaryMarked(phi3(e)))
				{
					found = true ;
					phi2sew(phi3(e), bit) ;
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
		} while(f != *it);
Pierre Kraemer's avatar
Pierre Kraemer committed
709 710
	}

untereiner's avatar
untereiner committed
711 712 713 714 715 716 717 718 719 720 721
	return count ;
}

void Map3::closeMap()
{
	// Search the map for topological holes (fix points of phi3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
			closeHole(d);
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
722 723 724
}

} // namespace CGoGN