mapRender.hpp 15.1 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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
300
		std::cout << "non triangle face" << std::endl ;
Sylvain Thery's avatar
MAJ MC  
Sylvain Thery committed
301
		addEarTri<PFP>(map, d, tableIndices);
302 303 304
		return;
	}

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

309
	// loop to cut a polygon in triangle on the fly (works only with convex faces)
Sylvain Thery's avatar
MAJ MC  
Sylvain Thery committed
310 311 312 313 314 315 316 317 318
//	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);

319 320 321 322 323 324
}


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
325
//	DartMarker m(map, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
326 327 328 329 330 331 332 333
	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);
	}
334 335 336 337 338 339
}

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
340
	DartMarker m(map, thread);
341 342 343
	// 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
344
	tableIndices.reserve(4 * map.getNbDarts() / 3);
345 346 347 348 349 350 351

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

352
			if (good(dd) && !map.isBoundaryMarked(dd))
Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
353
				addTri<PFP>(map, dd, tableIndices);
354
			m.markOrbit(FACE, dd);
355 356 357 358 359 360 361 362 363 364 365 366 367
			bound.push_back(dd);
			int nb = 1;
			do
			{
				Dart e = bound.back();
				Dart ee = e;
				do
				{
					Dart f = ee;
					do
					{
						if (!m.isMarked(f))
						{
368
							if (good(f) && !map.isBoundaryMarked(dd))
369
								addTri<PFP>(map, f, tableIndices);
370
							m.markOrbit(FACE, f);
371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
							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)
{
395
//	DartMarker m(map, thread);
396 397
	tableIndices.reserve(map.getNbDarts());

398 399 400 401 402 403 404 405 406 407 408 409
//	for(Dart d = map.begin(); d != map.end(); map.next(d))
//	{
//		if(!m.isMarked(d) && good(d))
//		{
//			tableIndices.push_back(map.getEmbedding(VERTEX, d));
//			tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(d)));
//			m.markOrbit(EDGE, d);
//		}
//	}

	TraversorE<typename PFP::MAP> trav(map);
	for (Dart d = trav.begin(); d!= trav.end(); d = trav.next())
410
	{
411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427
		if (good(d) && map.isBoundaryEdge(d))
		{
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
			tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(d)));
		}
	}
}

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

	for (Dart d = trav.begin(); d!= trav.end(); d = trav.next())
	{
		if (good(d) && map.isBoundaryEdge(d))
428
		{
429
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
430
			tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(d)));
431 432 433 434 435 436 437 438
		}
	}
}

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
439
	DartMarker m(map, thread);
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460

	// 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))
461
							tableIndices.push_back(map.getEmbedding(VERTEX, ee));
462
						if(good(f))
463 464
							tableIndices.push_back(map.getEmbedding(VERTEX, map.phi1(ee)));
						m.markOrbit(EDGE, f);
465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486

						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)
{
487
	CellMarker m(map, VERTEX, thread) ;
Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
488
	tableIndices.reserve(map.getNbDarts() / 5);
489 490 491 492 493

	for(Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if(!m.isMarked(d) && good(d))
		{
494
			tableIndices.push_back(map.getEmbedding(VERTEX, d));
495 496 497 498 499
			m.mark(d) ;
		}
	}
}

500

Sylvain Thery's avatar
Sylvain Thery committed
501

Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
502 503 504 505
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
506

Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
507 508
	// indice du VBO a utiliser
	int vbo_ind = 0;
Sylvain Thery's avatar
Sylvain Thery committed
509

Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
	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;
535 536 537 538 539
		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
540 541 542 543 544
		default:
			CGoGNerr << "problem initializing VBO indices" << CGoGNendl;
			break;
	}
	unsigned int size = tableIndices.size();
Sylvain Thery's avatar
Sylvain Thery committed
545

Pierre Kraemer's avatar
merge..  
Pierre Kraemer committed
546 547 548 549
	// 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
550 551

} // namespace GL2
552 553 554 555 556 557

} // namespace Render

} // namespace Algo

} // namespace CGoGN