mapRender.hpp 15.6 KB
Newer Older
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, 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.unistra.fr/                                           *
21
22
23
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/
24

25
#include "Topology/generic/attributeHandler.h"
26
27
#include "Topology/generic/dartmarker.h"
#include "Topology/generic/cellmarker.h"
28
29
#include "Topology/generic/traversorCell.h"

Thery Sylvain's avatar
Thery Sylvain committed
30
//#include "Utils/vbo.h"
31

32
33
34
#include "Geometry/intersection.h"
#include "Algo/Geometry/normal.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
inline bool MapRender::cmpVP(VertexPoly* lhs, VertexPoly* rhs)
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//	 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;
71
72
}

73
template<typename PFP>
74
void MapRender::recompute2Ears(const VertexAttribute<typename PFP::VEC3>& position, VertexPoly* vp, const typename PFP::VEC3& normalPoly, VPMS& ears, bool convex)
75
76
77
78
79
80
81
82
83
84
85
86
87
{
	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;
88

89
90
91
92
	v1.normalize();
	v2.normalize();
	v3.normalize();

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
93
94
95
96
97
//	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);

98

99
	if (!convex)	// if convex no need to test if vertex is an ear (yes)
100
	{
101
102
103
104
105
106
107
		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)
108

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

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

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

Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
123
			finished = ((dotpr1 >= 5.0f)&&(dotpr2 >= 5.0f));
124
125
		}
	}
126
127

	vp->value  = dotpr1;
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
128
	vp->length = (Tb-Tc).norm2();
129
	vp->ear = ears.insert(vp);
130
	vp2->value = dotpr2;
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
131
	vp->length = (Td-Ta).norm2();
132
	vp2->ear = ears.insert(vp2);
133
134
135
}

template<typename PFP>
136
float MapRender::computeEarAngle(const typename PFP::VEC3& P1, const typename PFP::VEC3& P2,  const typename PFP::VEC3& P3, const typename PFP::VEC3& normalPoly)
137
{
138
139
	typename PFP::VEC3 v1 = P1-P2;
	typename PFP::VEC3 v2 = P3-P2;
140
141
	v1.normalize();
	v2.normalize();
142

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

146
147
148
	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)
149
150
151
152
153

	return dotpr;
}

template<typename PFP>
154
bool MapRender::computeEarIntersection(const VertexAttribute<typename PFP::VEC3>& position, VertexPoly* vp, const typename PFP::VEC3& normalPoly)
155
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
156

157
158
159
160
161
162
163
164
165
	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
166
		if (inTriangle<typename PFP::VEC3>(position[curr->id], normalPoly,Tb,Tc,Ta))
167
168
169
170
171
172
173
174
175
176
177
		{
			vp->value = 5.0f;// not an ears !
			return false;
		}
		curr = curr->next;
	}

	return true;
}

template<typename PFP>
178
inline void MapRender::addEarTri(typename PFP::MAP& map, Dart d, std::vector<GLuint>& tableIndices, const VertexAttribute<typename PFP::VEC3>* pos)
179
{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
180
181
	bool(*fn_pt1)(VertexPoly*,VertexPoly*) = &(MapRender::cmpVP);
	VPMS ears(fn_pt1);
182

183
	const VertexAttribute<typename PFP::VEC3>& position = *pos ;
184
185

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

188
	// first pass create polygon in chained list with angle computation
189
190
	VertexPoly* vpp = NULL;
	VertexPoly* prem = NULL;
191
192
193
194
195
196
197
	unsigned int nbv = 0;
	unsigned int nbe = 0;
	Dart a = d;
	Dart b = map.phi1(a);
	Dart c = map.phi1(b);
	do
	{
198
199
200
		typename PFP::VEC3 P1 = position[map.template getEmbedding<VERTEX>(a)];
		typename PFP::VEC3 P2 = position[map.template getEmbedding<VERTEX>(b)];
		typename PFP::VEC3 P3 = position[map.template getEmbedding<VERTEX>(c)];
201

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

205
		if (vp->value < 5.0f)
206
			nbe++;
207
		if (vpp == NULL)
208
209
210
211
212
213
			prem = vp;
		vpp = vp;
		a = b;
		b = c;
		c = map.phi1(c);
		nbv++;
214
	}while (a != d);
215

216
	VertexPoly::close(prem, vpp);
217

218
	bool convex = nbe == nbv;
219
220
	if (convex)
	{
221
		// second pass with no test of intersections with polygons
222
223
224
		vpp = prem;
		for (unsigned int i=0; i< nbv; ++i)
		{
225
			vpp->ear = ears.insert(vpp);
226
227
228
229
230
			vpp = vpp->next;
		}
	}
	else
	{
231
		// second pass test intersections with polygons
232
233
234
235
		vpp = prem;
		for (unsigned int i=0; i< nbv; ++i)
		{
			if (vpp->value <5.0f)
236
				computeEarIntersection<PFP>(position, vpp, normalPoly);
237
			vpp->ear = ears.insert(vpp);
238
239
240
241
			vpp = vpp->next;
		}
	}

242
	// NOW WE HAVE THE POLYGON AND EARS
243
244
245
246
	// LET'S REMOVE THEM
	while (nbv>3)
	{
		// take best (and valid!) ear
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
247
		VPMS::iterator be_it = ears.begin(); // best ear
248
		VertexPoly* be = *be_it;
249
250
251
252
253
254
255

		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
256
257
258
259
260
261
		{
			//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
262
			recompute2Ears<PFP>(position,be,normalPoly,ears,convex);
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
263
264
265
			convex = (*(ears.rbegin()))->value < 5.0f;
		}
		else		// finish (no need to update ears)
266
		{
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
267
268
269
			// remove ear from polygon
			be = VertexPoly::erase(be);
			// last triangle
270
			tableIndices.push_back(be->id);
Sylvain Thery's avatar
MAJ MC    
Sylvain Thery committed
271
			tableIndices.push_back(be->next->id);
272
			tableIndices.push_back(be->prev->id);
273
274
275
276
			// release memory of last triangle in polygon
			delete be->next;
			delete be->prev;
			delete be;
277
278
279
280
		}
	}
}

281
282
283
284
285
286
287
288
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);

	// loop to cut a polygon in triangle on the fly (works only with convex faces)
289
290
	do
	{
291
292
293
		tableIndices.push_back(map.template getEmbedding<VERTEX>(d));
		tableIndices.push_back(map.template getEmbedding<VERTEX>(b));
		tableIndices.push_back(map.template getEmbedding<VERTEX>(c));
294
295
296
		b = c;
		c = map.phi1(b);
	} while (c != d);
297
298
299
}

template<typename PFP>
300
void MapRender::initTriangles(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, const VertexAttribute<typename PFP::VEC3>* position, unsigned int thread)
301
{
Pierre Kraemer's avatar
Pierre Kraemer committed
302
303
	tableIndices.reserve(4 * map.getNbDarts() / 3);

Pierre Kraemer's avatar
Pierre Kraemer committed
304
	TraversorF<typename PFP::MAP> trav(map, good, thread);
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320

	if(position == NULL)
	{
		for (Dart d = trav.begin(); d != trav.end(); d = trav.next())
			addTri<PFP>(map, d, tableIndices);
	}
	else
	{
		for (Dart d = trav.begin(); d != trav.end(); d = trav.next())
		{
			if(map.faceDegree(d) == 3)
				addTri<PFP>(map, d, tableIndices);
			else
				addEarTri<PFP>(map, d, tableIndices, position);
		}
	}
321
322
323
}

template<typename PFP>
324
void MapRender::initTrianglesOptimized(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, const VertexAttribute<typename PFP::VEC3>* position, unsigned int thread)
325
326
{
#define LIST_SIZE 20
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
327
	DartMarker m(map, thread);
328
329
330
	// 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
331
	tableIndices.reserve(4 * map.getNbDarts() / 3);
332
333
334
335
336
337
338

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

339
			if (good(dd) && !map.template isBoundaryMarked<PFP::MAP::DIMENSION>(dd))
340
341
342
343
344
345
346
347
348
349
350
			{
				if(position == NULL)
					addTri<PFP>(map, dd, tableIndices);
				else
				{
					if(map.faceDegree(dd) == 3)
						addTri<PFP>(map, dd, tableIndices);
					else
						addEarTri<PFP>(map, dd, tableIndices, position);
				}
			}
Pierre Kraemer's avatar
Pierre Kraemer committed
351
			m.markOrbit<FACE>(dd);
352
353
354
355
356
357
358
359
360
361
362
363
364
			bound.push_back(dd);
			int nb = 1;
			do
			{
				Dart e = bound.back();
				Dart ee = e;
				do
				{
					Dart f = ee;
					do
					{
						if (!m.isMarked(f))
						{
365
							if (good(f) && !map.template isBoundaryMarked<PFP::MAP::DIMENSION>(f))
366
367
368
369
370
371
372
373
374
375
376
							{
								if(position == NULL)
									addTri<PFP>(map, f, tableIndices);
								else
								{
									if(map.faceDegree(f) == 3)
										addTri<PFP>(map, f, tableIndices);
									else
										addEarTri<PFP>(map, f, tableIndices, position);
								}
							}
Pierre Kraemer's avatar
Pierre Kraemer committed
377
							m.markOrbit<FACE>(f);
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
							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)
{
	tableIndices.reserve(map.getNbDarts());

Pierre Kraemer's avatar
Pierre Kraemer committed
404
	TraversorE<typename PFP::MAP> trav(map, good, thread);
405
	for (Dart d = trav.begin(); d != trav.end(); d = trav.next())
406
	{
407
408
		tableIndices.push_back(map.template getEmbedding<VERTEX>(d));
		tableIndices.push_back(map.template getEmbedding<VERTEX>(map.phi1(d)));
409
410
411
412
413
414
415
416
	}
}

template<typename PFP>
void MapRender::initBoundaries(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, unsigned int thread)
{
	tableIndices.reserve(map.getNbDarts()); //TODO optimisation ?

Pierre Kraemer's avatar
Pierre Kraemer committed
417
	TraversorE<typename PFP::MAP> trav(map, good, thread);
418
	for (Dart d = trav.begin(); d != trav.end(); d = trav.next())
419
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
420
		if (map.isBoundaryEdge(d))
421
		{
422
423
			tableIndices.push_back(map.template getEmbedding<VERTEX>(d));
			tableIndices.push_back(map.template getEmbedding<VERTEX>(map.phi1(d)));
424
425
426
427
428
429
430
431
		}
	}
}

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
432
	DartMarker m(map, thread);
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453

	// 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))
454
							tableIndices.push_back(map.template getEmbedding<VERTEX>(ee));
455
						if(good(f))
456
							tableIndices.push_back(map.template getEmbedding<VERTEX>(map.phi1(ee)));
Pierre Kraemer's avatar
Pierre Kraemer committed
457
						m.markOrbit<EDGE>(f);
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479

						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)
{
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
480
	tableIndices.reserve(map.getNbDarts() / 5);
481

Pierre Kraemer's avatar
Pierre Kraemer committed
482
	TraversorV<typename PFP::MAP> trav(map, good, thread);
483
	for (Dart d = trav.begin(); d != trav.end(); d = trav.next())
484
		tableIndices.push_back(map.template getEmbedding<VERTEX>(d));
485
486
}

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
487
488
template<typename PFP>
void MapRender::initPrimitives(typename PFP::MAP& map, const FunctorSelect& good, int prim, bool optimized, unsigned int thread)
489
490
491
492
493
{
	initPrimitives<PFP>(map, good, prim, NULL, optimized, thread) ;
}

template <typename PFP>
494
void MapRender::initPrimitives(typename PFP::MAP& map, const FunctorSelect& good, int prim, const VertexAttribute<typename PFP::VEC3>* position, bool optimized, unsigned int thread)
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
495
496
{
	std::vector<GLuint> tableIndices;
Sylvain Thery's avatar
Sylvain Thery committed
497

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
498
499
	// indice du VBO a utiliser
	int vbo_ind = 0;
Sylvain Thery's avatar
Sylvain Thery committed
500

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
	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)
518
				initTrianglesOptimized<PFP>(map, good, tableIndices, position, thread);
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
519
			else
520
				initTriangles<PFP>(map, good, tableIndices, position, thread) ;
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
521
522
523
524
525
			m_nbIndices[TRIANGLE_INDICES] = tableIndices.size();
			vbo_ind = m_indexBuffers[TRIANGLE_INDICES];
			break;
		case FLAT_TRIANGLES:
			break;
526
527
528
529
530
		case BOUNDARY:
			initBoundaries<PFP>(map, good, tableIndices, thread) ;
			m_nbIndices[BOUNDARY_INDICES] = tableIndices.size();
			vbo_ind = m_indexBuffers[BOUNDARY_INDICES];
			break;
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
531
532
533
534
535
		default:
			CGoGNerr << "problem initializing VBO indices" << CGoGNendl;
			break;
	}
	unsigned int size = tableIndices.size();
Sylvain Thery's avatar
Sylvain Thery committed
536

Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
537
538
539
540
	// 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
541
542

} // namespace GL2
543
544
545
546
547
548

} // namespace Render

} // namespace Algo

} // namespace CGoGN