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-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
#include "Topology/generic/attributeHandler.h"
26 27
#include "Topology/generic/dartmarker.h"
#include "Topology/generic/cellmarker.h"
28 29
#include "Topology/generic/traversorCell.h"

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 typename PFP::TVEC3& 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 typename PFP::TVEC3& 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 typename PFP::TVEC3* 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 typename PFP::TVEC3& position = *pos ;
184 185 186 187 188

	// 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
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.getEmbedding(VERTEX, a)];
		typename PFP::VEC3 P2 = position[map.getEmbedding(VERTEX, b)];
		typename PFP::VEC3 P3 = position[map.getEmbedding(VERTEX, c)];
201

202 203
		float val = computeEarAngle<PFP>(P1, P2, P3, normalPoly);
		VertexPoly* vp = new VertexPoly(map.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 242 243 244 245 246
			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
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 291 292 293 294 295 296
	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);
297 298 299
}

template<typename PFP>
300
void MapRender::initTriangles(typename PFP::MAP& map, const FunctorSelect& good, std::vector<GLuint>& tableIndices, const typename PFP::TVEC3* 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 typename PFP::TVEC3* 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.isBoundaryMarked(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);
				}
			}
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.isBoundaryMarked(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);
								}
							}
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
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
407 408
		tableIndices.push_back(map.getEmbedding(VERTEX, d));
		tableIndices.push_back(map.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
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
423
			tableIndices.push_back(map.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.getEmbedding(VERTEX, ee));
455
						if(good(f))
456 457
							tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(ee)));
						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())
Pierre Kraemer's avatar
Pierre Kraemer committed
484
		tableIndices.push_back(map.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 494
{
	initPrimitives<PFP>(map, good, prim, NULL, optimized, thread) ;
}

template <typename PFP>
void MapRender::initPrimitives(typename PFP::MAP& map, const FunctorSelect& good, int prim, const typename PFP::TVEC3* 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