mapRender.hpp 15.3 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
500
501
502
503
504
505
506
507
508
509
510
	switch(prim)
	{
		case POINTS:
			initPoints<PFP>(map, good, tableIndices, thread);
			break;
		case LINES:
			if(optimized)
				initLinesOptimized<PFP>(map, good, tableIndices, thread);
			else
				initLines<PFP>(map, good, tableIndices, thread) ;
			break;
		case TRIANGLES:
			if(optimized)
511
				initTrianglesOptimized<PFP>(map, good, tableIndices, position, thread);
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
512
			else
513
				initTriangles<PFP>(map, good, tableIndices, position, thread) ;
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
514
515
516
			break;
		case FLAT_TRIANGLES:
			break;
517
518
519
		case BOUNDARY:
			initBoundaries<PFP>(map, good, tableIndices, thread) ;
			break;
Pierre Kraemer's avatar
merge..    
Pierre Kraemer committed
520
521
522
523
		default:
			CGoGNerr << "problem initializing VBO indices" << CGoGNendl;
			break;
	}
524
525
526

	m_nbIndices[prim] = tableIndices.size();
	m_indexBufferUpToDate[prim] = true;
Sylvain Thery's avatar
Sylvain Thery committed
527

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

} // namespace GL2
534
535
536
537
538
539

} // namespace Render

} // namespace Algo

} // namespace CGoGN