Création d'un compte pour un collaborateur extérieur au laboratoire depuis l'intranet ICube : https://intranet.icube.unistra.fr/fr/labs/member/profile

mapRender.hpp 14.3 KB
Newer Older
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           *
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/                                         *
21
22
23
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/
24

25
26
#include "Topology/generic/dartmarker.h"
#include "Topology/generic/cellmarker.h"
27
#include "Utils/vbo.h"
28

29
30
31
32
#include "Topology/generic/attributeHandler.h"
#include "Geometry/intersection.h"
#include "Algo/Geometry/normal.h"

Sylvain Thery's avatar
Sylvain Thery committed
33
34
#include "Topology/generic/traversorCell.h"

35
36
37
38
39
40
41
42
43
namespace CGoGN
{

namespace Algo
{

namespace Render
{

Sylvain Thery's avatar
Sylvain Thery committed
44
namespace GL2
45
46
{

47

48
49
inline bool MapRender::cmpVP(VertexPoly* lhs, VertexPoly* rhs)
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//	 return lhs->value < rhs->value;

	if (fabs(lhs->value - rhs->value)<0.2f)
			return lhs->length < rhs->length;
	return lhs->value < rhs->value;
}


template<typename VEC3>
bool MapRender::inTriangle(const VEC3& P, const VEC3& normal, const VEC3& Ta,  const VEC3& Tb, const VEC3& Tc)
{
	typedef typename VEC3::DATA_TYPE T ;

	if (Geom::tripleProduct(P-Ta, (Tb-Ta), normal) >= T(0))
		return false;

	if (Geom::tripleProduct(P-Tb, (Tc-Tb), normal) >= T(0))
		return false;

	if (Geom::tripleProduct(P-Tc, (Ta-Tc), normal) >= T(0))
		return false;

	return true;
73
74
}

75

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
76

77
template<typename PFP>
78
void MapRender::recompute2Ears( AttributeHandler<typename PFP::VEC3>& position, VertexPoly* vp, const typename PFP::VEC3& normalPoly, VPMS& ears, bool convex)
79
80
81
82
83
84
85
86
87
88
89
90
91
{
	VertexPoly* vprev = vp->prev;
	VertexPoly* vp2 = vp->next;
	VertexPoly* vnext = vp2->next;
	const typename PFP::VEC3& Ta = position[vp->id];
	const typename PFP::VEC3& Tb = position[vp2->id];
	const typename PFP::VEC3& Tc = position[vprev->id];
	const typename PFP::VEC3& Td = position[vnext->id];

	// compute angle
	typename PFP::VEC3 v1= Tb - Ta;
	typename PFP::VEC3 v2= Tc - Ta;
	typename PFP::VEC3 v3= Td - Tb;
92

93
94
95
96
	v1.normalize();
	v2.normalize();
	v3.normalize();

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
97
98
99
100
101
//	float dotpr1 = 1.0f - (v1*v2);
//	float dotpr2 = 1.0f + (v1*v3);
	float dotpr1 = acos(v1*v2) / (M_PI/2.0f);
	float dotpr2 = acos(-(v1*v3)) / (M_PI/2.0f);

102

103
	if (!convex)	// if convex no need to test if vertex is an ear (yes)
104
	{
105
106
107
108
109
110
111
		typename PFP::VEC3 nv1 = v1^v2;
		typename PFP::VEC3 nv2 = v1^v3;

		if (nv1*normalPoly < 0.0)
			dotpr1 = 10.0f - dotpr1;// not an ears  (concave)
		if (nv2*normalPoly < 0.0)
			dotpr2 = 10.0f - dotpr2;// not an ears  (concave)
112

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
113
		bool finished = (dotpr1>=5.0f) && (dotpr2>=5.0f);
114
		for (VPMS::reverse_iterator it = ears.rbegin(); (!finished)&&(it != ears.rend())&&((*it)->value > 5.0f); ++it)
115
		{
116
117
			int id = (*it)->id;
			const typename PFP::VEC3& P = position[id];
118

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
119
120
			if ((dotpr1 < 5.0f) && (id !=vprev->id))
				if (inTriangle<typename PFP::VEC3>(P, normalPoly,Tb,Tc,Ta))
121
					dotpr1 = 5.0f;// not an ears !
122

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
123
124
			if ((dotpr2 < 5.0f) && (id !=vnext->id) )
				if (inTriangle<typename PFP::VEC3>(P, normalPoly,Td,Ta,Tb))
125
126
					dotpr2 = 5.0f;// not an ears !

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
127
			finished = ((dotpr1 >= 5.0f)&&(dotpr2 >= 5.0f));
128
129
		}
	}
130
131

	vp->value  = dotpr1;
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
132
	vp->length = (Tb-Tc).norm2();
133
	vp->ear = ears.insert(vp);
134
	vp2->value = dotpr2;
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
135
	vp->length = (Td-Ta).norm2();
136
	vp2->ear = ears.insert(vp2);
137
138
139
140
}


template<typename PFP>
141
float MapRender::computeEarAngle(const typename PFP::VEC3& P1, const typename PFP::VEC3& P2,  const typename PFP::VEC3& P3, const typename PFP::VEC3& normalPoly)
142
{
143
144
	typename PFP::VEC3 v1 = P1-P2;
	typename PFP::VEC3 v2 = P3-P2;
145
146
	v1.normalize();
	v2.normalize();
147

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
148
149
//	float dotpr = 1.0f - (v1*v2);
	float dotpr = acos(v1*v2) / (M_PI/2.0f);
150

151
152
153
	typename PFP::VEC3 vn = v1^v2;
	if (vn*normalPoly > 0.0f)
		dotpr = 10.0f - dotpr; 		// not an ears  (concave, store at the end for optimized use for intersections)
154
155
156
157

	return dotpr;
}

158

159
160
161
template<typename PFP>
bool MapRender::computeEarIntersection(AttributeHandler<typename PFP::VEC3>& position, VertexPoly* vp, const typename PFP::VEC3& normalPoly)
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
162

163
164
165
166
167
168
169
170
171
	VertexPoly* endV = vp->prev;
	VertexPoly* curr = vp->next;
	const typename PFP::VEC3& Ta = position[vp->id];
	const typename PFP::VEC3& Tb = position[curr->id];
	const typename PFP::VEC3& Tc = position[endV->id];
	curr = curr->next;

	while (curr != endV)
	{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
172
		if (inTriangle<typename PFP::VEC3>(position[curr->id], normalPoly,Tb,Tc,Ta))
173
174
175
176
177
178
179
180
181
182
183
		{
			vp->value = 5.0f;// not an ears !
			return false;
		}
		curr = curr->next;
	}

	return true;
}


Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
184

185
186
187
template<typename PFP>
inline void MapRender::addEarTri(typename PFP::MAP& map, Dart d, std::vector<GLuint>& tableIndices)
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
188
189
	bool(*fn_pt1)(VertexPoly*,VertexPoly*) = &(MapRender::cmpVP);
	VPMS ears(fn_pt1);
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206


	AttributeHandler<typename PFP::VEC3> position = map.template getAttribute<typename PFP::VEC3>(VERTEX,"position");

	// compute normal to polygon
	typename PFP::VEC3 normalPoly = Algo::Geometry::newellNormal<PFP>(map, d, position);

	// first pass create polygon in chained list witht angle computation
	VertexPoly* vpp=NULL;
	VertexPoly* prem=NULL;
	unsigned int nbv = 0;
	unsigned int nbe = 0;
	Dart a = d;
	Dart b = map.phi1(a);
	Dart c = map.phi1(b);
	do
	{
207
208
209
210
211
		typename PFP::VEC3 P1= position[map.getEmbedding(VERTEX,a)];
		typename PFP::VEC3 P2= position[map.getEmbedding(VERTEX,b)];
		typename PFP::VEC3 P3= position[map.getEmbedding(VERTEX,c)];

		float val = computeEarAngle<PFP>(P1,P2,P3,normalPoly);
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
212
213
		VertexPoly* vp = new VertexPoly(map.getEmbedding(VERTEX,b),val,(P3-P1).norm2(),vpp);

214
215
216
217
218
219
220
221
222
223
224
225
226
		if (vp->value <5.0f)
			nbe++;
		if (vpp==NULL)
			prem = vp;
		vpp = vp;
		a = b;
		b = c;
		c = map.phi1(c);
		nbv++;
	}while (a!=d);

	VertexPoly::close(prem,vpp);

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
227
	bool convex = nbe==nbv;
228
229
	if (convex)
	{
230
		// second pass with no test of intersections with polygons
231
232
233
		vpp = prem;
		for (unsigned int i=0; i< nbv; ++i)
		{
234
			vpp->ear = ears.insert(vpp);
235
236
237
238
239
			vpp = vpp->next;
		}
	}
	else
	{
240
		// second pass test intersections with polygons
241
242
243
244
245
		vpp = prem;
		for (unsigned int i=0; i< nbv; ++i)
		{
			if (vpp->value <5.0f)
				computeEarIntersection<PFP>(position,vpp,normalPoly);
246
			vpp->ear = ears.insert(vpp);
247
248
249
250
251
252
253
254
255
			vpp = vpp->next;
		}
	}

	// NO WE HAVE THE POLYGON AND EARS
	// LET'S REMOVE THEM
	while (nbv>3)
	{
		// take best (and valid!) ear
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
256
		VPMS::iterator be_it = ears.begin(); // best ear
257
		VertexPoly* be = *be_it;
258
259
260
261
262
263
264

		tableIndices.push_back(be->id);
		tableIndices.push_back(be->next->id);
		tableIndices.push_back(be->prev->id);
		nbv--;

		if (nbv>3)	// do not recompute if only one triangle left
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
265
266
267
268
269
270
		{
			//remove ears and two sided ears
			ears.erase(be_it);					// from map of ears
			ears.erase(be->next->ear);
			ears.erase(be->prev->ear);
			be = VertexPoly::erase(be); 	// and remove ear vertex from polygon
271
			recompute2Ears<PFP>(position,be,normalPoly,ears,convex);
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
272
273
274
			convex = (*(ears.rbegin()))->value < 5.0f;
		}
		else		// finish (no need to update ears)
275
		{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
276
277
278
			// remove ear from polygon
			be = VertexPoly::erase(be);
			// last triangle
279
			tableIndices.push_back(be->id);
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
280
			tableIndices.push_back(be->next->id);
281
			tableIndices.push_back(be->prev->id);
282
283
284
285
			// release memory of last triangle in polygon
			delete be->next;
			delete be->prev;
			delete be;
286
287
288
289
290
		}
	}
}


291
292
293
294
295
296
297
template<typename PFP>
inline void MapRender::addTri(typename PFP::MAP& map, Dart d, std::vector<GLuint>& tableIndices)
{
	Dart a = d;
	Dart b = map.phi1(a);
	Dart c = map.phi1(b);

298
299
	if (map.phi1(c) != a)
	{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
300
		addEarTri<PFP>(map, d, tableIndices);
301
302
303
		return;
	}

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
304
305
306
307
	tableIndices.push_back(map.getEmbedding(VERTEX, d));
	tableIndices.push_back(map.getEmbedding(VERTEX, b));
	tableIndices.push_back(map.getEmbedding(VERTEX, c));

308
	// loop to cut a polygon in triangle on the fly (works only with convex faces)
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
309
310
311
312
313
314
315
316
317
//	do
//	{
//		tableIndices.push_back(map.getEmbedding(VERTEX, d));
//		tableIndices.push_back(map.getEmbedding(VERTEX, b));
//		tableIndices.push_back(map.getEmbedding(VERTEX, c));
//		b = c;
//		c = map.phi1(b);
//	} while (c != d);

318
319
320
321
322
323
}


template<typename PFP>
void MapRender::initTriangles(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
Sylvain Thery's avatar
Sylvain Thery committed
324
325
326
//	DartMarker m(map, thread);
//	tableIndices.reserve(4 * map.getNbDarts() / 3);
//
Pierre Kraemer's avatar
Pierre Kraemer committed
327
//	for(Dart dd = map.begin(); dd != map.end(); map.next(dd))
Sylvain Thery's avatar
Sylvain Thery committed
328
//	{
Pierre Kraemer's avatar
Pierre Kraemer committed
329
330
331
332
333
//		if(!m.isMarked(dd) && good(dd))
//		{
//			addTri<PFP>(map, dd, tableIndices);
//			m.markOrbit(FACE, dd);
//		}
Sylvain Thery's avatar
Sylvain Thery committed
334
//	}
Pierre Kraemer's avatar
Pierre Kraemer committed
335
336
337
338
339
340
341
342
343
344

	DartMarker m(map, thread);
	tableIndices.reserve(4 * map.getNbDarts() / 3);

	TraversorF<typename PFP::MAP> trav(map);
	for (Dart d = trav.begin(); d!= trav.end(); d = trav.next())
	{
		if (good(d))
			addTri<PFP>(map, d, tableIndices);
	}
345
346
347
348
349
350
}

template<typename PFP>
void MapRender::initTrianglesOptimized(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
#define LIST_SIZE 20
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
351
	DartMarker m(map, thread);
352
353
354
	// reserve memory for triangles ( nb indices == nb darts )
	// and a little bit more
	// if lots of polygonal faces, realloc is done by vector
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
355
	tableIndices.reserve(4 * map.getNbDarts() / 3);
356
357
358
359
360
361
362

	for (Dart dd = map.begin(); dd != map.end(); map.next(dd))
	{
		if (!m.isMarked(dd))
		{
			std::list<Dart> bound;

Sylvain Thery's avatar
Sylvain Thery committed
363
			if (good(dd))
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
364
				addTri<PFP>(map, dd, tableIndices);
365
			m.markOrbit(FACE, dd);
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
			bound.push_back(dd);
			int nb = 1;
			do
			{
				Dart e = bound.back();
				Dart ee = e;
				do
				{
					Dart f = ee;
					do
					{
						if (!m.isMarked(f))
						{
							if(good(f))
								addTri<PFP>(map, f, tableIndices);
381
							m.markOrbit(FACE, f);
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
							bound.push_back(map.phi1(f));
							++nb;
							if (nb > LIST_SIZE)
							{
								bound.pop_front();
								--nb;
							}
						}
						f = map.phi1(map.phi2(f));
					} while (f != ee);
					ee = map.phi1(ee);
				} while (ee != e);

				bound.pop_back();
				--nb;
			} while (!bound.empty());
		}
	}
#undef LIST_SIZE
}

template<typename PFP>
void MapRender::initLines(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
406
	DartMarker m(map, thread);
407
408
409
410
411
412
	tableIndices.reserve(map.getNbDarts());

	for(Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if(!m.isMarked(d) && good(d))
		{
413
414
415
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
			tableIndices.push_back(map.getEmbedding(VERTEX, map.phi2(d)));
			m.markOrbit(EDGE, d);
416
417
418
419
420
421
422
423
		}
	}
}

template<typename PFP>
void MapRender::initLinesOptimized(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
#define LIST_SIZE 20
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
424
	DartMarker m(map, thread);
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445

	// reserve memory for edges indices ( nb indices == nb darts)
	tableIndices.reserve(map.getNbDarts());

	for (Dart dd = map.begin(); dd != map.end(); map.next(dd))
	{
		if (!m.isMarked(dd))
		{
			std::list<Dart> bound;
			bound.push_back(dd);
			int nb = 1;
			do
			{
				Dart e = bound.back();
				Dart ee = e;
				do
				{
					Dart f = map.phi2(ee);
					if (!m.isMarked(ee))
					{
						if(good(ee))
446
							tableIndices.push_back(map.getEmbedding(VERTEX, ee));
447
						if(good(f))
448
449
							tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(ee)));
						m.markOrbit(EDGE, f);
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471

						bound.push_back(f);
						++nb;
						if (nb > LIST_SIZE)
						{
							bound.pop_front();
							--nb;
						}
					}
					ee = map.phi1(f);
				} while (ee != e);
				bound.pop_back();
				--nb;
			} while (!bound.empty());
		}
	}
#undef LIST_SIZE
}

template<typename PFP>
void MapRender::initPoints(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
472
	CellMarker m(map, VERTEX, thread) ;
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
473
	tableIndices.reserve(map.getNbDarts() / 5);
474
475
476
477
478

	for(Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if(!m.isMarked(d) && good(d))
		{
479
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
480
481
482
483
484
			m.mark(d) ;
		}
	}
}

485

Sylvain Thery's avatar
Sylvain Thery committed
486

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
487
488
489
490
template<typename PFP>
void MapRender::initPrimitives(typename PFP::MAP& map, const FunctorSelect& good, int prim, bool optimized, unsigned int thread)
{
	std::vector<GLuint> tableIndices;
Sylvain Thery's avatar
Sylvain Thery committed
491

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
492
493
	// indice du VBO a utiliser
	int vbo_ind = 0;
Sylvain Thery's avatar
Sylvain Thery committed
494

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
	switch(prim)
	{
		case POINTS:
			initPoints<PFP>(map, good, tableIndices, thread);
			m_nbIndices[POINT_INDICES] = tableIndices.size();
			vbo_ind = m_indexBuffers[POINT_INDICES];
			break;
		case LINES:
			if(optimized)
				initLinesOptimized<PFP>(map, good, tableIndices, thread);
			else
				initLines<PFP>(map, good, tableIndices, thread) ;
			m_nbIndices[LINE_INDICES] = tableIndices.size();
			vbo_ind = m_indexBuffers[LINE_INDICES];
			break;
		case TRIANGLES:
			if(optimized)
				initTrianglesOptimized<PFP>(map, good, tableIndices, thread);
			else
				initTriangles<PFP>(map, good, tableIndices, thread) ;
			m_nbIndices[TRIANGLE_INDICES] = tableIndices.size();
			vbo_ind = m_indexBuffers[TRIANGLE_INDICES];
			break;
		case FLAT_TRIANGLES:
			break;
		default:
			CGoGNerr << "problem initializing VBO indices" << CGoGNendl;
			break;
	}
	unsigned int size = tableIndices.size();
Sylvain Thery's avatar
Sylvain Thery committed
525

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
526
527
528
529
	// setup du buffer d'indices
	glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER, vbo_ind);
	glBufferDataARB(GL_ELEMENT_ARRAY_BUFFER, size * sizeof(GLuint), &(tableIndices[0]), GL_STREAM_DRAW);
}
Sylvain Thery's avatar
Sylvain Thery committed
530
531

} // namespace GL2
532
533
534
535
536
537

} // namespace Render

} // namespace Algo

} // namespace CGoGN