map3.cpp 26.2 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
178
	assert(d != e && sameOrientedFace(d, e)) ;
	Map2::splitFace(d, e);
Pierre Kraemer's avatar
Pierre Kraemer committed
179

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

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(!isBoundaryFace(d))
280
	{
untereiner's avatar
untereiner committed
281
		Dart e = phi3(d);
282
283
284
285
286
287
		Map2::mergeVolumes(d, e); // merge the two volumes along common face
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
288
289
290
291
292
293
294
295
296
void Map3::splitVolume(std::vector<Dart>& vd)
{
	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
297
298
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
299

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

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

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

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

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

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

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

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

untereiner's avatar
untereiner committed
346
347
348
	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
349
350
	mv.mark(d);

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

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

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

	return count;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

493
bool Map3::check()
494
{
495
496
497
498
499
500
501
502
503
504
    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;
        }
505

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

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

519
520
521
522
523
524
        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;
        }
525

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

533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
        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 ?
549
		{
550
551
552
553
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
554

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

557
558
559
    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
560
561
562
563
564
565
566
567
568
    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 ;

569
    return true;
570
571
}

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

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

untereiner's avatar
untereiner committed
581
582
583
	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
584
585
	mv.mark(d);

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

untereiner's avatar
untereiner committed
593
594
595
596
597
598
599
600
601
		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
602
603
		}

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

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

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

untereiner's avatar
untereiner committed
626
627
628
	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
629
630
	mv.mark(d);

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

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

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

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

untereiner's avatar
untereiner committed
661
662
663
/*! @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
664

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

untereiner's avatar
untereiner committed
669
670
671
	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
672

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

untereiner's avatar
untereiner committed
675
676
	// 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
677
	{
untereiner's avatar
untereiner committed
678
679
680
681
		Dart f = *it ;
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
682

untereiner's avatar
untereiner committed
683
684
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
685
		{
untereiner's avatar
untereiner committed
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
			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
708
709
	}

untereiner's avatar
untereiner committed
710
711
712
713
714
715
716
717
718
719
720
	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
721
722
723
724
725
726
727
728
729
}

//bool Map3::foreach_connex_volume(Dart d, int degree, FunctorType& f, FunctorSelect<Dart>& s)
//{
//	Marker m = this->getNewMarker();
//	bool found = false;
//	std::list<Dart> darts_list;
//	std::list<Dart> neighbours_list;
//	darts_list.push_back(d);
730
//	this->markOrbit(DART,d,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
731
732
733
734
735
736
737
738
739
740
741
742
//
//	std::list<Dart>::iterator prem = darts_list.begin();
//
//	while (!found && prem != darts_list.end()) {
//		Dart d1 = *prem;
//		Dart dd;
//		switch(degree) {
//			case 0 : //vertex connexity
//				{
//					dd=d1;
//					std::list<Dart> darts_list2;
//					darts_list2.push_back(dd);
743
//					this->markOrbit(DART,dd,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
744
745
746
747
748
749
750
751
752
753
754
755
756
757
//					neighbours_list.push_back(dd);
//					std::list<Dart>::iterator prem2 = darts_list2.begin();
//
//					while (!found && prem2 != darts_list2.end()) {
//						Dart dd1 = *prem2;
//						Dart d3 = phi2(dd1);
//						Dart d2 = phi1(d3); // turn in volume
//						Dart d4 = phi3(d3); // change volume
//
//						if(s(dd1))
//							found =  f(dd1);
//
//						if(!this->isMarkedDart(d2,m)) {
//							darts_list2.push_back(d2);
758
//							markOrbit(DART,d2,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
759
760
761
762
//						}
//
//						if(!this->isMarkedDart(d4,m)) {
//							darts_list2.push_back(d4);
763
//							markOrbit(DART,d4,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
764
765
766
767
768
769
770
771
772
773
774
//						}
//
//						++prem2;
//					}
//				}
//				break;
//			case 1 : //edge connexity
//				dd=d1;
//				neighbours_list.push_back(dd);
//				do {
//					if(!this->isMarkedDart(dd,m)) {
775
//						markOrbit(DART,dd,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
//						if(s(dd))
//							found =  f(dd);
//					}
//					dd = alpha2(dd);
//				} while(!found && dd!=d1);
//				break;
//			default : //face connexity
//				dd = phi3(d1);
//				if(!this->isMarkedDart(dd,m)) {
//					neighbours_list.push_back(dd);
//					markOrbit(2,dd,m);
//					if(s(dd)) {
//						found =  f(dd);
//					}
//				}
//		} //end switch
//
//		//test rest of the volume
//		// add phi1 and phi2 successor of they are not yet marked
//		Dart d2 = phi1(d1); // turn in face
//		Dart d3 = phi2(d1); // change volume
//
//		if (!this->isMarkedDart(d2,m)) {
//			darts_list.push_back(d2);
800
//			this->markOrbit(DART,d2,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
801
802
803
//		}
//		if (!this->isMarkedDart(d3,m)) {
//			darts_list.push_back(d3);
804
//			this->markOrbit(DART,d3,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
805
806
807
808
809
810
811
//		}
//
//		++prem;
//	}
//
//	//unmark current volume
//	for (std::list<Dart>::iterator it = darts_list.begin(); it != darts_list.end(); ++it) {
812
//		this->unmarkOrbit(DART,(*it),m);
Pierre Kraemer's avatar
Pierre Kraemer committed
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
//	}
//
//	//unmark connex volumes checked
//	FunctorUnmark<Map3 > fum(*this,m);
//	for (std::list<Dart>::iterator it = neighbours_list.begin(); it != neighbours_list.end(); ++it) {
//		switch(degree) {
//			case 0 :
//				foreach_dart_of_vertex((*it),fum);
//				break;
//			case 1 :
//				foreach_dart_of_edge((*it),fum);
//				break;
//			default :
//				foreach_dart_of_face((*it),fum);
//		}
//	}
829
//	this->releaseMarker(DART,m);
Pierre Kraemer's avatar
Pierre Kraemer committed
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
//	return found;
//}

//// template <typename DART>
//// void Map3::foreach_volume(FunctorType<Dart>* funct)
//// {
//// 	// lock a marker
//// 	int markOV = this->getMarkerIndex();
//// 	for(Dart d = this->begin(); d != this->end(); this->next(d))
//// 	{
//// 		if (!this->isMarkedDart(d,markOV))  // if not yet treated
//// 		{
//// 			(*funct)(d);			// call the functor and
//// 			this->markVolume(d,markOV);  // mark all dart of the vol
//// 		}
//// 	}
846
//// 	this->releaseMarker(DART,markOV);
Pierre Kraemer's avatar
Pierre Kraemer committed
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
//// }



//void Map3::reverseOrientation()
//{
//	Marker mf2 = this->getNewMarker();
//	Marker mf3 = this->getNewMarker();
//
//	// reverse all faces (only phi1 is modified)
//	for (Dart d= this->begin(); d != this->end(); this->next(d))
//	{
//		if (!isMarkedDart(d,mf2))
//		{
//			reverseFace(d);
//
//			Dart e=d;
//			do
//			{
866
867
//				markOrbit(DART,e,mf2);
//				markOrbit(DART,e,mf3);
Pierre Kraemer's avatar
Pierre Kraemer committed
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
//				e=phi1(e);
//			}
//			while (e!=d);
//		}
//	}
//
//	// store all new phi2 and phi3
//	std::vector<Dart> vdphi2;
//	std::vector<Dart> vdphi3;
//	vdphi2.reserve(this->getNbDarts());
//	vdphi3.reserve(this->getNbDarts());
//	for (Dart d= this->begin(); d != this->end(); this->next(d))
//	{
//		Dart e = phi_1(phi2(phi1(d)));
//		vdphi2.push_back(e);
//		Dart f = phi_1(phi3(phi1(d)));
//		vdphi3.push_back(f);
//	}
//
//	// apply the phi2sew with stored phi2 on all darts
//	std::vector<Dart>::iterator id2 = vdphi2.begin();
//	std::vector<Dart>::iterator id3 = vdphi3.begin();
//	for (Dart d= this->begin(); d != this->end(); this->next(d),++id2,++id3)
//	{
//		if (isMarkedDart(d,mf2))
//		{
894
895
//			unmarkOrbit(DART,d,mf2); // unmark the two darts
//			unmarkOrbit(DART,*id2,mf2);
Pierre Kraemer's avatar
Pierre Kraemer committed
896
897
898
899
900
901
902
903
904
905
//
//			if (phi2(d) != d)
//				phi2unsew(d);	// unsew the two darts if necessary
//			if (phi2(*id2) != *id2)
//				phi2unsew(*id2);
//			phi2sew(d,*id2); // sew the darts
//		}
//
//		if (isMarkedDart(d,mf3))
//		{
906
907
//			unmarkOrbit(DART,d,mf3); // unmark the two darts
//			unmarkOrbit(DART,*id3,mf3);
Pierre Kraemer's avatar
Pierre Kraemer committed
908
909
910
911
912
913
914
915
916
917
//
//			if (phi3(d) != d)
//				phi3unsew(d);	// unsew the two darts if necessary
//			if (phi3(*id3) != *id3)
//				phi3unsew(*id3);
//			phi3sew(d,*id3); // sew the darts
//		}
//	}
//
//	// no need to clear marker second pass do it
918
919
//	this->releaseMarker(DART,mf2);
//	this->releaseMarker(DART,mf3);
Pierre Kraemer's avatar
Pierre Kraemer committed
920
921
//}
//
untereiner's avatar
untereiner committed
922
923


Pierre Kraemer's avatar
Pierre Kraemer committed
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974

//void Map3::deleteEdge(Dart d)
//{
//	Dart e = d;
//	std::list<Dart> tmp;
//	do
//	{
//		tmp.push_back(e);
//		e=phi3(phi2(e));
//	}
//	while (e!=d);
//
//	for (std::list<Dart>::iterator it=tmp.begin();it!=tmp.end();++it)
//	{
//		Map2::deleteEdge(*it);
//	}
//
//}
//
//
//void Map3::removeEdge(Dart d)
//{
//
//	Dart e = d;
//	std::list<Dart> tmp;
//	do
//	{
//		tmp.push_back(e);
//		e=phi3(phi2(e));
//	}
//	while (e!=d);
//
//	for (std::list<Dart>::iterator it=tmp.begin();it!=tmp.end();++it)
//	{
//		removeFace(*it);
//	}
//}
//
//
//void Map3::removeVertex(Dart d)
//{
//	std::vector<Dart> store;
//	FunctorStore<Dart> fs(store);
//	foreach_dart_of_vertex(d,fs);
//
//	Marker toMerge = this->getNewMarker();
//
//	for (std::vector<Dart>::iterator it = store.begin() ; it!=store.end() ; ++it)
//	{
//		if (!this->isMarkedDart(*it,toMerge))
//		{
975
//			this->markOrbit(DART,this->phi3(this->phi_1(*it)),toMerge);
Pierre Kraemer's avatar
Pierre Kraemer committed
976
977
978
979
980
981
//		}
//		else
//		{
//			this->removeFace(*it);
//		}
//	}
982
//	this->releaseMarker(DART,toMerge);
Pierre Kraemer's avatar
Pierre Kraemer committed
983
984
985
986
987
988
989
990
991
992
993
994
995
//}
//
//
//
//

//
//Dart Map3::trianguleFace(Dart d0)
//{
//	Dart d1 = phi1(d0);		// Begin with d1 to avoid looking for the dart before d0
//	Dart d = d1;			// Dart d is used to turn around the face
//
//	if (d1 == d0)
996
//		CGoGNout << "Warning: triangulation of a face with only one edge" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
997
998
//
//	if (phi1(d1) == d0)
999
//		CGoGNout << "Warning: triangulation of a face with only two edges" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
1000
1001
1002
1003
1004
1005
1006
//
//	Dart n = newEdge(2); 	// Create the first edge with n in the central vertex
//	Dart first = phi2(n); 	// Store the opposite of the first edge
//	Dart prec = phi3(n);
//	Dart next = phi1(d); 	// Get the next edge in the face of d
//	phi1sew(n,d); 			// Insert the edge in the face of d (between d and next)
//
1007
//	AttributeHandler<Marker> dmarkers( VERTEX<<24 ,*this); // a modifier pour virer <<24
Pierre Kraemer's avatar
Pierre Kraemer committed
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
//
//	dmarkers[n] = dmarkers[d]; //	n->setMarkerVal(d->getMarkerVal());
//	dmarkers[phi2(n)] = dmarkers[d]; //	phi2(n)->setMarkerVal(d->getMarkerVal());
//
//	phi1sew(phi1(phi3(n)),phi3(next));
//
//	dmarkers[phi3(n)] = dmarkers[phi3(d)]; //	phi3(n)->setMarkerVal(phi3(d)->getMarkerVal());
//	dmarkers[phi1(phi3(n))] = dmarkers[phi3(d)]; //	phi1(phi3(n))->setMarkerVal(phi3(d)->getMarkerVal());
//
//	d = next; 				// Go to the next edge
//
//	while (d != d1)
//	{
//		n = newEdge(2); 		// Create an edge
//		next = phi1(d); 	// Get the next edge in the face of d
//		phi1sew(n,d); 		// Insert the edge in the face of d (between d and next)
//
//		dmarkers[n] = dmarkers[d];//	n->setMarkerVal(d->getMarkerVal());
//		dmarkers[phi2(n)] = dmarkers[d]; //	phi2(n)->setMarkerVal(d->getMarkerVal());
//
//		phi1sew(phi1(phi3(n)),phi3(next));
//
//		dmarkers[phi3(n)] = dmarkers[phi3(d)]; //	phi3(n)->setMarkerVal(phi3(d)->getMarkerVal());
//		dmarkers[phi1(phi3(n))] = dmarkers[phi3(d)]; //	phi1(phi3(n))->setMarkerVal(phi3(d)->getMarkerVal());
//
//		phi1sew(phi2(n),first); // Sew the edge with the first one around central vertex
//		phi1sew(prec,phi3(n));
//		prec = phi3(n);
//		d = next; 			// Go to next edge
//	}
//
//	return n; // Return the last created edge
//}
//
//
//
//
//
//Dart Map3::cutSpike(Dart d)
//{
//  Dart e=d;
//  int nb=0;
//  Dart dNew;
//
//  //count the valence of the vertex
//  do {
//    nb++;
//    e=phi1(phi2(e));
//  } while (e!=d);
//
//  if(nb<3)
//  {
1060
//	CGoGNout << "Warning : cannot cut 2 volumes without creating a degenerated face " << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
//	return d;
//  }
//  else
//  {
//	//triangulate around the vertex
//	do {
//		if(phi1(phi1(phi1(e)))!=e)
// 			cutFace(phi_1(e),phi1(e));
//		e=phi1(phi2(e));
//	} while (e!=d);
//
//	dNew=newFace(nb);
//
//	//sew a face following the triangles
//	Dart dTurn=dNew;
//	do {
//		Dart d1 = phi1(e);
//		Dart dSym = phi2(d1);
//		phi2unsew(d1);
//		phi2sew(dTurn,d1);
//		phi2sew(phi3(dTurn),dSym);
//		dTurn = phi1(dTurn);
//		e=phi1(phi2(e));
//	}while(e!=d);
//  }
//
//  return dNew;
//}
//
//
//Dart Map3::tetrahedrizeVolume(Dart d)
//{
//	// store all the dart of the volume
//	std::vector<Dart> vStore;
//	FunctorStore<Dart> fs(vStore);
//	foreach_dart_of_volume(d,fs);
//
//	//get a new marker
//	Marker traite = this->getNewMarker();
//
//	//the dart that will be returned
//	Dart ret;
//	//for each dart of the volume
//	for (std::vector<Dart>::iterator it = vStore.begin() ; it != vStore.end() ; ++it )
//	{
//		Dart dc=*it;
//		//if not processed
//		if (!isMarkedDart(dc,traite))
//		{
//			Dart dc2 = phi2(dc);
//
//			//mark the dart
1113
1114
//			markOrbit(DART,dc,traite);
//			markOrbit(DART,dc2,traite);
Pierre Kraemer's avatar
Pierre Kraemer committed
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
//
//			//create the new triangles
//			Dart dd=this->newFace(3);
//			Dart ee=phi3(dd);
//
//			//and sew them
//			phi2unsew(dc);
//			phi2unsew(dc2);
//			phi2sew(dc,dd);
//			phi2sew(dc2,ee);
//
//			//prepare the returned dart
//			ret=phi_1(dd);
//		}
//	}
//
//	//for each dart
//	for (std::vector<Dart>::iterator it = vStore.begin() ; it != vStore.end() ; ++it)
//	{
//		Dart dc=*it;
//		//if processed
//		if (isMarkedDart(dc,traite))
//		{
//			//get the previous dart in the face
//			Dart dc2 = phi_1(dc);
//
//			//unmark them
1142
//			unmarkOrbit(DART,dc,traite);
Pierre Kraemer's avatar
Pierre Kraemer committed
1143
1144
1145
1146
1147
1148
//
//			//and sew them to create the tetra
//			phi2sew(phi1(phi2(dc)),phi_1(phi2(dc2)));
//		}
//	}
//
1149
1150
//	this->unmarkAll(DART,traite);
//	this->releaseMarker(DART,traite);
Pierre Kraemer's avatar
Pierre Kraemer committed
1151
1152
1153
1154
1155
1156
1157
1158
//
//	return ret;
//
//}
//
//

} // namespace CGoGN