env_generator.hpp 28.5 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2
#include "Algo/Modelisation/subdivision.h"
#include "Geometry/inclusion.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
3
#include "Topology/generic/traversorCell.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
4
#include <algorithm>
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11

namespace CGoGN
{

namespace CityGenerator
{

David Cazier's avatar
David Cazier committed
12
template <typename PFP>
David Cazier's avatar
David Cazier committed
13
bool notAdjacentToAnObstacle(typename PFP::MAP& map, Dart d, CellMarker<FACE>& buildingMark)
Pierre Kraemer's avatar
Pierre Kraemer committed
14
{
David Cazier's avatar
David Cazier committed
15
	Dart dd = d ;
David Cazier's avatar
David Cazier committed
16 17
	do
	{
David Cazier's avatar
David Cazier committed
18 19 20
		if (buildingMark.isMarked(dd)) return false ;
		dd = map.phi1(dd) ;
	} while (dd != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
21

David Cazier's avatar
David Cazier committed
22
	return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
23 24
}

David Cazier's avatar
David Cazier committed
25
template <typename PFP>
David Cazier's avatar
David Cazier committed
26
bool notDiagonalAdjacentToAnObstacle(typename PFP::MAP& map, Dart d, CellMarker<FACE>& buildingMark)
Pierre Kraemer's avatar
Pierre Kraemer committed
27
{
David Cazier's avatar
David Cazier committed
28
	Dart dd = d ;
David Cazier's avatar
David Cazier committed
29 30
	do
	{
David Cazier's avatar
David Cazier committed
31 32 33
		if (buildingMark.isMarked(map.alpha1(map.alpha1(dd)))) return false ;
		dd = map.phi1(dd) ;
	} while (dd != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
34

David Cazier's avatar
David Cazier committed
35
	return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
36 37
}

David Cazier's avatar
David Cazier committed
38
template <typename PFP>
39
Algo::Modelisation::Polyhedron<PFP> generateGrid(EnvMap& envMap)
Pierre Kraemer's avatar
Pierre Kraemer committed
40
{
41 42
	unsigned int nx = envMap.geometry.size(0) / envMap.maxCellSize ;
	unsigned int ny = envMap.geometry.size(1) / envMap.maxCellSize ;
David Cazier's avatar
David Cazier committed
43 44
	if (nx < 1) nx = 1 ;
	if (ny < 1) ny = 1 ;
45

David Cazier's avatar
David Cazier committed
46
	std::cout << " - Generate Grid : " << nx << " x " << ny << std::endl ;
47 48 49 50

	Algo::Modelisation::Polyhedron<PFP> prim(envMap.map, envMap.position) ;
	Dart d = prim.grid_topo(nx, ny) ;
	prim.embedGrid(envMap.geometry.size(0), envMap.geometry.size(1), 0.0f) ;
51

52 53
	Dart boundary = envMap.map.phi2(d) ;
	envMap.buildingMark.mark(boundary) ;
David Cazier's avatar
David Cazier committed
54 55

	Dart e = boundary ;
David Cazier's avatar
David Cazier committed
56 57
	do
	{
58 59
		envMap.obstacleMark.mark(e) ;
		e = envMap.map.phi1(e) ;
David Cazier's avatar
David Cazier committed
60
	} while (e != boundary) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
61

David Cazier's avatar
David Cazier committed
62
	return prim ;
Pierre Kraemer's avatar
Pierre Kraemer committed
63 64
}

David Cazier's avatar
David Cazier committed
65
template <typename PFP>
pitiot's avatar
merging  
pitiot committed
66
void generateCity(EnvMap& envMap, unsigned int nbBuildings)
67
{
pitiot's avatar
merging  
pitiot committed
68
	unsigned int nbBuilding = nbBuildings ;
David Cazier's avatar
David Cazier committed
69
	std::cout << " - Generate City : " << nbBuilding << " buildings" << std::endl ;
70 71 72 73

	generateGrid<PFP>(envMap) ;

	Dart dEnd = envMap.map.end() ;
David Cazier's avatar
David Cazier committed
74 75 76 77 78
	for (Dart d = envMap.map.begin(); d != dEnd && nbBuilding > 0; envMap.map.next(d))
	{
		if (!envMap.buildingMark.isMarked(d) && (rand() % 12 == 0)
		    && notDiagonalAdjacentToAnObstacle<PFP>(envMap.map, d, envMap.buildingMark))
		{
pitiot's avatar
merging  
pitiot committed
79
			generateBuilding<PFP>(envMap, d, (1 + (rand() % 3)) * 50.0f, rand() % 4) ;
80 81 82 83 84
			--nbBuilding ;
		}
	}
}

David Cazier's avatar
David Cazier committed
85
template <typename PFP>
David Cazier's avatar
David Cazier committed
86
Algo::Modelisation::Polyhedron<PFP> generateTrianGrid(typename PFP::MAP& map,
David Cazier's avatar
David Cazier committed
87 88
                                                      typename PFP::TVEC3& position,
                                                      unsigned int cX, unsigned int cY,
David Cazier's avatar
David Cazier committed
89 90
                                                      float sideLength, CellMarker<EDGE>& obstacleMark,
                                                      CellMarker<FACE>& buildingMark)
91
{
David Cazier's avatar
David Cazier committed
92 93
	Algo::Modelisation::Polyhedron<PFP> prim(map, position) ;
	prim.grid_topo(cX, cY) ;
94

David Cazier's avatar
David Cazier committed
95
	prim.embedGrid(sideLength * cX, sqrt(sideLength * sideLength * 3.0f / 4.0f) * cY) ;
96

David Cazier's avatar
David Cazier committed
97 98 99
	Dart dY = prim.getDart() ; //remind the first quad of the line
	Dart dX = prim.getDart() ; //goes through the line
	bool odd = true ; //odd line or not
David Cazier's avatar
David Cazier committed
100 101
	for (unsigned int i = 0; i < cX * cY;)
	{
David Cazier's avatar
David Cazier committed
102
		Dart dNext = map.phi1(map.phi2(map.phi1(dX))) ;
103

David Cazier's avatar
David Cazier committed
104
		Dart toCut = dX ;
David Cazier's avatar
David Cazier committed
105 106
		if (odd)
		{
David Cazier's avatar
David Cazier committed
107 108
			toCut = map.phi1(toCut) ; //change the side of the split face
			position[toCut][0] -= sideLength / 2.0f ; //move vertices for equilateral triangles
109 110
		}

David Cazier's avatar
David Cazier committed
111
		map.splitFace(toCut, map.phi1(map.phi1(toCut))) ;
112

David Cazier's avatar
David Cazier committed
113
		++i ;
114

David Cazier's avatar
David Cazier committed
115
		if (i % cX == 0 && i > 0) //goes up and change side of split
David Cazier's avatar
David Cazier committed
116
		{
David Cazier's avatar
David Cazier committed
117 118
			Dart endSquare = map.newOrientedFace(3) ; //add triangle add end of lines to make a square
			Dart dN ;
David Cazier's avatar
David Cazier committed
119 120
			if (odd)
			{
David Cazier's avatar
David Cazier committed
121 122 123 124
				dN = map.phi1(map.phi2(map.phi1(dX))) ;
				map.sewFaces(dN, endSquare) ;
				position[map.phi_1(endSquare)] = position[map.phi1(endSquare)] ;
				position[map.phi_1(endSquare)][0] += sideLength / 2.0f ;
125
			}
David Cazier's avatar
David Cazier committed
126 127
			else
			{
David Cazier's avatar
David Cazier committed
128 129 130
				dN = map.phi1(dX) ;
				map.sewFaces(dN, endSquare) ;
				position[map.phi_1(endSquare)] = position[endSquare] ;
131 132
			}

David Cazier's avatar
David Cazier committed
133 134 135 136
			if (odd)
				dY = map.phi2(map.phi_1(map.phi2(map.phi1(dY)))) ;
			else
				dY = map.phi2(map.phi1(map.phi2(map.phi_1(dY)))) ;
137

David Cazier's avatar
David Cazier committed
138 139
			dX = dY ;
			odd = !odd ;
140
		}
David Cazier's avatar
David Cazier committed
141 142
		else
			dX = dNext ;
143 144
	}

David Cazier's avatar
David Cazier committed
145
	Dart boundary ;
David Cazier's avatar
David Cazier committed
146 147 148 149
	for (Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if (map.phi2(d) == d)
		{
David Cazier's avatar
David Cazier committed
150 151
			Dart dA = map.alpha1(map.phi1(d)) ;
			if (map.phi2(dA) == dA && position[dA] == position[map.phi1(d)]
David Cazier's avatar
David Cazier committed
152 153 154 155
			    && position[map.phi1(dA)] == position[d])
				map.sewFaces(dA, d) ;
			else
			{
David Cazier's avatar
David Cazier committed
156 157
				obstacleMark.mark(d) ;
				boundary = d ;
158 159 160 161
			}
		}
	}

David Cazier's avatar
David Cazier committed
162 163
	map.closeHole(boundary) ;
	buildingMark.mark(map.phi2(boundary)) ;
164

David Cazier's avatar
David Cazier committed
165
	if (odd) //last top line if odd
166
	{
David Cazier's avatar
David Cazier committed
167 168
		for (unsigned int i = 0; i < cX; ++i)
		{
David Cazier's avatar
David Cazier committed
169 170
			dX = map.phi1(dX) ;
			position[dX][0] -= sideLength / 2.0f ;
171 172 173 174 175 176 177 178 179 180 181 182
		}
	}

	//add hexagons
//	for(Dart d = map.begin(); d != map.end(); map.next(d))
//	{
//		if(map.vertexDegree(d)==6)
//		{
//			map.deleteVertex(d);
//		}
//	}

David Cazier's avatar
David Cazier committed
183
	return prim ;
184 185
}

David Cazier's avatar
David Cazier committed
186
template <typename PFP>
David Cazier's avatar
David Cazier committed
187
Dart extrudeFaceAndMark(typename PFP::MAP& map, typename PFP::TVEC3& position, Dart d,
David Cazier's avatar
David Cazier committed
188
                        CellMarker<FACE>& buildingMark, float height)
Pierre Kraemer's avatar
Pierre Kraemer committed
189
{
David Cazier's avatar
David Cazier committed
190 191 192
	Dart dRoof = Algo::Modelisation::extrudeFace<PFP>(map, position, d, height) ;
	buildingMark.mark(dRoof) ;
	Dart dd = dRoof ;
David Cazier's avatar
David Cazier committed
193 194
	do
	{
David Cazier's avatar
David Cazier committed
195 196 197 198
		buildingMark.mark(map.phi2(dd)) ;
		dd = map.phi1(dd) ;
	} while (dd != dRoof) ;
	return dRoof ;
Pierre Kraemer's avatar
Pierre Kraemer committed
199 200
}

Jund Thomas's avatar
Jund Thomas committed
201 202 203 204
template <typename PFP>
Dart extrudeBuilding(typename PFP::MAP& map, typename PFP::TVEC3& position, Dart d, unsigned int buildingType, float height)
{
	Dart dRoof ;
Jund Thomas's avatar
Jund Thomas committed
205 206 207 208 209
//	VEC3 sky(0,0,1.0f);
	VEC3 v1(position[map.phi1(d)]-position[d]);
	VEC3 v2(position[map.template phi<11>(d)]-position[d]);
	VEC3 sky = (v1^v2);
	sky.normalize();
Jund Thomas's avatar
Jund Thomas committed
210
	dRoof = Algo::Modelisation::extrudeFace<PFP>(map, position, d, height) ;
Jund Thomas's avatar
Jund Thomas committed
211 212 213 214 215 216 217 218 219

	switch (buildingType)
	{
		case 0 : //basic
		{
			break ;
		}
		case 1 : //with roof 1 slope
		{
Jund Thomas's avatar
Jund Thomas committed
220
			dRoof = Algo::Modelisation::extrudeFace<PFP>(map, position, dRoof, height/3.0f) ;
Jund Thomas's avatar
Jund Thomas committed
221 222 223 224 225 226 227 228
			Dart dNext = map.phi1(dRoof) ;
			Dart dPrev = map.phi2(map.phi_1(dRoof)) ;
			map.collapseEdge(dNext) ;
			map.collapseEdge(dPrev) ;
			break ;
		}
		case 2 : //with roof 2 slopes
		{
Jund Thomas's avatar
Jund Thomas committed
229
			dRoof = Algo::Modelisation::extrudeFace<PFP>(map, position, dRoof, height/3.0f) ;
Jund Thomas's avatar
Jund Thomas committed
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
			Dart dNext = map.phi1(dRoof) ;
			Dart dPrev = map.phi2(map.phi_1(dRoof)) ;
			typename PFP::VEC3 mid1 = (position[dNext] + position[map.phi1(dNext)]) / 2.0f ;
			typename PFP::VEC3 mid2 = (position[dPrev] + position[map.phi1(dPrev)]) / 2.0f ;
			map.collapseEdge(dNext) ;
			map.collapseEdge(dPrev) ;
			position[dRoof] = mid2 ;
			position[map.phi1(dRoof)] = mid1 ;
			break ;
		}
		case 3 : //with multiple stairs
		{
			unsigned int nbStairs = rand() % 5 ;
			for (unsigned int i = 0; i < nbStairs; ++i)
			{
				typename PFP::VEC3 c = Algo::Geometry::faceCentroid<PFP>(map, dRoof, position) ;
				Dart dRoofSmall = Algo::Modelisation::extrudeFace<PFP>(map, position, dRoof, 0.0f) ;
				Dart dd = dRoofSmall ;
				do
				{
					position[dd] = position[dd] + (c - position[dd]) / 3.0f ;
					dd = map.phi1(dd) ;
				} while (dd != dRoofSmall) ;
Jund Thomas's avatar
Jund Thomas committed
253
				dRoof = Algo::Modelisation::extrudeFace<PFP>(map, position, dRoofSmall, height/2.0f) ;
Jund Thomas's avatar
Jund Thomas committed
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
			}
			bool spike = rand() % 2 ;
			if (spike)
			{
				typename PFP::VEC3 c = Algo::Geometry::faceCentroid<PFP>(map, dRoof, position) ;
				c[2] += height / 1.5f ;
				dRoof = Algo::Modelisation::trianguleFace<PFP>(map, dRoof) ;
				position[dRoof] = c ;
			}
			break ;
		}
	}

	return dRoof;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
270
#ifndef SPATIAL_HASHING
David Cazier's avatar
David Cazier committed
271
template <typename PFP>
272
bool animateCity(EnvMap* envMap)
Pierre Kraemer's avatar
Pierre Kraemer committed
273
{
David Cazier's avatar
David Cazier committed
274 275 276 277
	typename PFP::MAP& map = envMap->map ;
	typename PFP::TVEC3& position = envMap->position ;
	typename PFP::TAB_AGENTVECT& agents = envMap->agentvect ;
	typename PFP::TAB_AGENTVECT& agentNeighbors = envMap->neighborAgentvect ;
David Cazier's avatar
David Cazier committed
278 279
	CellMarker<EDGE>& obstacleMark = envMap->obstacleMark ;
	CellMarker<FACE>& buildingMark = envMap->buildingMark ;
David Cazier's avatar
David Cazier committed
280 281 282
	std::vector<Dart>& newBuildings = envMap->newBuildings ;

	unsigned int state = rand() % 10 ;
David Cazier's avatar
David Cazier committed
283 284
	if (state < 2)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
285 286
		map.setCurrentLevel(0) ;

287
		//generate new building
David Cazier's avatar
David Cazier committed
288
		Dart d(rand() % map.getNbDarts()) ;
David Cazier's avatar
David Cazier committed
289
		if (!map.isDartValid(d)) map.next(d) ;
David Cazier's avatar
David Cazier committed
290 291 292
		while (d != map.end() && map.getDartLevel(d) > 0)
			map.next(d) ;

David Cazier's avatar
David Cazier committed
293 294 295 296 297 298 299
		if (d != map.end())
		{
			if (!buildingMark.isMarked(d) && agents[d].size() == 0 && agentNeighbors[d].size() == 0
			    && !map.faceIsSubdivided(d)
			    && notAdjacentToAnObstacle<PFP>(map, d, obstacleMark)
			    && notDiagonalAdjacentToAnObstacle<PFP>(map, d, obstacleMark))
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
300
				map.setCurrentLevel(map.getMaxLevel()) ;
David Cazier's avatar
David Cazier committed
301 302 303
				d = generateBuilding<PFP>(envMap, d, 2.0f, 0) ;
				newBuildings.push_back(d) ;
				return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
304
			}
305
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
306 307

		map.setCurrentLevel(map.getMaxLevel()) ;
308
	}
David Cazier's avatar
David Cazier committed
309 310
	else if (state < 6 && newBuildings.size() > 0)
	{
David Cazier's avatar
David Cazier committed
311 312 313
		//take a newBuilding and make it higher
		state = rand() % newBuildings.size() ;
		Dart d = newBuildings[state] ;
314
		//decide if we create a new floor, or just make it higher
David Cazier's avatar
David Cazier committed
315
		unsigned int typeOfUpdate = rand() % 10 ;
David Cazier's avatar
David Cazier committed
316 317
		if (typeOfUpdate < 9)
		{
David Cazier's avatar
David Cazier committed
318
			Dart dd = d ;
David Cazier's avatar
David Cazier committed
319 320
			do
			{
David Cazier's avatar
David Cazier committed
321 322 323 324
				position[dd][2] += 2.0f ;
				dd = map.phi1(dd) ;
			} while (dd != d) ;

David Cazier's avatar
David Cazier committed
325 326
			if (position[dd][2] > ((10 + rand() % 10) * 10.0f)) newBuildings.erase(
			    newBuildings.begin() + state) ;
327
		}
David Cazier's avatar
David Cazier committed
328 329
		else
		{
David Cazier's avatar
David Cazier committed
330 331 332
			typename PFP::VEC3 c = Algo::Geometry::faceCentroid<PFP>(map, d, position) ;
			Dart dRoofSmall = Algo::Modelisation::extrudeFace<PFP>(map, position, d, 0.0f) ;
			Dart dd = dRoofSmall ;
David Cazier's avatar
David Cazier committed
333 334
			do
			{
David Cazier's avatar
David Cazier committed
335 336 337
				position[dd] = position[dd] + (c - position[dd]) / 3.0f ;
				dd = map.phi1(dd) ;
			} while (dd != dRoofSmall) ;
338
//			Dart dRoof = Algo::Modelisation::extrudeFace<PFP>(map,position,dRoofSmall,2.0f);
David Cazier's avatar
David Cazier committed
339
			Dart dRoof = extrudeFaceAndMark<PFP>(map, position, dRoofSmall, buildingMark, 2.0f) ;
340

David Cazier's avatar
David Cazier committed
341 342
			newBuildings.erase(newBuildings.begin() + state) ;
			newBuildings.push_back(dRoof) ;
343 344 345
		}
	}

David Cazier's avatar
David Cazier committed
346
	return false ;
347
}
Pierre Kraemer's avatar
Pierre Kraemer committed
348
#endif
349 350

//template <typename PFP>
pitiot's avatar
pitiot committed
351
//Dart generateBuilding(typename PFP::MAP& map, VertexAttribute<typename PFP::VEC3>& position, Dart d, float height, unsigned int buildingType, CellMarker<EDGE>& obstacleMark, CellMarker<FACE>& buildingMark)
352 353

//template <typename PFP>
pitiot's avatar
pitiot committed
354
//void generateCity(typename PFP::MAP& map, VertexAttribute<typename PFP::VEC3>& position, CellMarker<EDGE>& obstacleMark, CellMarker<FACE>& buildingMark, float sideSize, unsigned int nbSquares)
355

David Cazier's avatar
David Cazier committed
356
template <typename PFP>
357
Dart generateBuilding(EnvMap& envMap, Dart d, float height, unsigned int buildingType)
Pierre Kraemer's avatar
Pierre Kraemer committed
358
{
359 360
	typename PFP::MAP& map = envMap.map ;
	typename PFP::TVEC3& position = envMap.position ;
David Cazier's avatar
David Cazier committed
361 362
	CellMarker<EDGE>& obstacleMark = envMap.obstacleMark ;
	CellMarker<FACE>& buildingMark = envMap.buildingMark ;
363

Pierre Kraemer's avatar
Pierre Kraemer committed
364
	// mark the face as obstacle before extrusion
David Cazier's avatar
David Cazier committed
365 366
	Dart dd = d ;
	buildingMark.mark(dd) ;
David Cazier's avatar
David Cazier committed
367 368
	do
	{
David Cazier's avatar
David Cazier committed
369
		obstacleMark.mark(dd) ;
370

David Cazier's avatar
David Cazier committed
371 372
		Dart next = map.phi1(dd) ;
		Dart previous = map.phi_1(dd) ;
373
		Obstacle* o = new Obstacle(position[dd], position[next], position[previous],
374
		                           position[map.phi1(next)], NULL, 0);
375

Pierre Kraemer's avatar
Pierre Kraemer committed
376 377
#ifdef SPATIAL_HASHING
		VEC3 ov = o->p2 - o->p1 ;
378
		unsigned int nbsteps = ov.norm() / envMap.obstacleDistance + 1 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
379
		ov.normalize() ;
380
		VEC3 step = ov * envMap.obstacleDistance ;
Pierre Kraemer's avatar
Pierre Kraemer committed
381
		VEC3 pos = o->p1 ;
382
		for(unsigned int i = 0 ; i < nbsteps ; ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
383
		{
384 385
			Geom::Vec2ui c = envMap.obstaclePositionCell(pos) ;
			for(int ii = -1 ; ii <= 1 ; ++ii)
Pierre Kraemer's avatar
Pierre Kraemer committed
386
			{
387
				for(int jj = -1 ; jj <= 1 ; ++jj)
Pierre Kraemer's avatar
Pierre Kraemer committed
388 389 390 391
				{
					if(!(ii == 0 && jj == 0))
					{
						Geom::Vec2ui cc = c + Geom::Vec2ui(ii, jj) ;
392
						std::vector<Obstacle*>& ovect = envMap.ht_obstacles[cc] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
393
						if(std::find(ovect.begin(), ovect.end(), o) == ovect.end())
394
						ovect.push_back(o) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
395 396 397 398 399 400
					}
				}
			}
			pos += step ;
		}
#else
401 402 403 404
		// David
		// envMap.pushObstacleInCells(o, map.phi2(dd)) ;

		// Thomas's team
pitiot's avatar
pitiot committed
405 406 407
		Dart x =map.phi2(dd);
		if(!map.isBoundaryMarked(x))
		{
pitiot's avatar
pitiot committed
408
			addElementToVector<Obstacle*>(envMap.obstvect[x],o);
409 410 411 412 413

			if(!map.isBoundaryMarked(map.phi2(map.phi1(x))))
				addElementToVector<Obstacle*>(envMap.obstvect[map.phi2(map.phi1(x))],o);
			if(!map.isBoundaryMarked(map.phi2(map.phi_1(x))))
				addElementToVector<Obstacle*>(envMap.obstvect[map.phi2(map.phi_1(x))],o);
pitiot's avatar
pitiot committed
414 415
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
416
#endif
417

David Cazier's avatar
David Cazier committed
418 419
		dd = map.phi1(dd) ;
	} while (dd != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
420

David Cazier's avatar
David Cazier committed
421 422
	Dart dRoof ;
	dRoof = extrudeFaceAndMark<PFP>(map, position, d, buildingMark, height) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
423

David Cazier's avatar
David Cazier committed
424 425
	switch (buildingType)
	{
Jund Thomas's avatar
Jund Thomas committed
426
		case 0 :
David Cazier's avatar
David Cazier committed
427
		{
Jund Thomas's avatar
Jund Thomas committed
428
			break ;
Pierre Kraemer's avatar
Pierre Kraemer committed
429
		}
Jund Thomas's avatar
Jund Thomas committed
430
		case 1 :
David Cazier's avatar
David Cazier committed
431
		{
Jund Thomas's avatar
Jund Thomas committed
432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
			dRoof = extrudeFaceAndMark<PFP>(map, position, dRoof, buildingMark, height / 3) ;
			Dart dNext = map.phi1(dRoof) ;
			Dart dPrev = map.phi2(map.phi_1(dRoof)) ;
			map.collapseEdge(dNext) ;
			map.collapseEdge(dPrev) ;
			break ;
		}
		case 2 :
		{
			dRoof = extrudeFaceAndMark<PFP>(map, position, dRoof, buildingMark, height / 3) ;
			Dart dNext = map.phi1(dRoof) ;
			Dart dPrev = map.phi2(map.phi_1(dRoof)) ;
			typename PFP::VEC3 mid1 = (position[dNext] + position[map.phi1(dNext)]) / 2.0f ;
			typename PFP::VEC3 mid2 = (position[dPrev] + position[map.phi1(dPrev)]) / 2.0f ;
			map.collapseEdge(dNext) ;
			map.collapseEdge(dPrev) ;
			position[dRoof] = mid2 ;
			position[map.phi1(dRoof)] = mid1 ;
			break ;
		}
		case 3 :
		{
			unsigned int nbStairs = rand() % 5 ;
			for (unsigned int i = 0; i < nbStairs; ++i)
			{
				typename PFP::VEC3 c = Algo::Geometry::faceCentroid<PFP>(map, dRoof, position) ;
				Dart dRoofSmall = extrudeFaceAndMark<PFP>(map, position, dRoof, buildingMark, 0.0f) ;
				Dart dd = dRoofSmall ;
				do
				{
					position[dd] = position[dd] + (c - position[dd]) / 3.0f ;
					dd = map.phi1(dd) ;
				} while (dd != dRoofSmall) ;
				dRoof = extrudeFaceAndMark<PFP>(map, position, dRoofSmall, buildingMark,
												height / 2.0f) ;
			}
			bool spike = rand() % 2 ;
			if (spike)
			{
				typename PFP::VEC3 c = Algo::Geometry::faceCentroid<PFP>(map, dRoof, position) ;
				c[2] += height / 1.5f ;
				dRoof = Algo::Modelisation::trianguleFace<PFP>(map, dRoof) ;
				position[dRoof] = c ;
			}
			break ;
Pierre Kraemer's avatar
Pierre Kraemer committed
477 478
		}
	}
479

David Cazier's avatar
David Cazier committed
480
	return dRoof ;
Pierre Kraemer's avatar
Pierre Kraemer committed
481 482
}

David Cazier's avatar
David Cazier committed
483
template <typename PFP>
David Cazier's avatar
David Cazier committed
484 485
void generateMall(typename PFP::MAP& map, typename PFP::TVEC3& position, CellMarker<EDGE>& obstacleMark,
                  CellMarker<FACE>& buildingMark, float sideSize)
486
{
David Cazier's avatar
David Cazier committed
487 488
	unsigned int side = 5 ;
	std::vector<Algo::Modelisation::Polyhedron<PFP> > floors ;
489

David Cazier's avatar
David Cazier committed
490 491
	Algo::Modelisation::Polyhedron<PFP> * floor2 = new Algo::Modelisation::Polyhedron<PFP>(
	    map, position) ;
David Cazier's avatar
David Cazier committed
492
	floor2->grid_topo(side, side) ;
493

David Cazier's avatar
David Cazier committed
494
	floor2->embedGrid(sideSize * side, sideSize * side) ;
495

David Cazier's avatar
David Cazier committed
496 497
	for (unsigned int i = 0; i < 3; ++i)
	{
David Cazier's avatar
David Cazier committed
498 499
		float floorHeight = 100 ;
		typename PFP::VEC3 transl(0, 0, floorHeight) ;
David Cazier's avatar
David Cazier committed
500
		CellMarker<VERTEX> m(map) ;
501

David Cazier's avatar
David Cazier committed
502 503 504 505
		for (Dart d = map.begin(); d != map.end(); map.next(d))
		{
			if (!m.isMarked(d))
			{
David Cazier's avatar
David Cazier committed
506 507
				m.mark(d) ;
				position[d] += transl ;
508 509 510
			}
		}

511
		Algo::Modelisation::Polyhedron<PFP> * floor1 = new Algo::Modelisation::Polyhedron<PFP>(
David Cazier's avatar
David Cazier committed
512
		    map, position) ;
David Cazier's avatar
David Cazier committed
513 514
		floor1->grid_topo(side, side) ;
		floor1->embedGrid(sideSize * side, sideSize * side) ;
515

David Cazier's avatar
David Cazier committed
516 517
		Dart d1 = map.template phi<121>(floor1->getDart()) ;
		Dart d2 = map.template phi<121121121>(floor2->getDart()) ;
518

David Cazier's avatar
David Cazier committed
519
		generatePathToUpperStair<PFP>(map, position, d1, d2) ;
520

David Cazier's avatar
David Cazier committed
521
		floor2 = floor1 ;
522 523
	}

David Cazier's avatar
David Cazier committed
524
	Dart boundary ;
David Cazier's avatar
David Cazier committed
525 526 527 528
	for (Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if (map.phi2(d) == d)
		{
David Cazier's avatar
David Cazier committed
529 530
			obstacleMark.mark(d) ;
			boundary = d ;
531 532 533
		}
	}

David Cazier's avatar
David Cazier committed
534 535
	map.closeHole(boundary) ;
	buildingMark.mark(map.phi2(boundary)) ;
536

David Cazier's avatar
David Cazier committed
537
	installGuardRail<PFP>(map, position, obstacleMark, buildingMark, sideSize / 10.0f) ;
538 539
}

David Cazier's avatar
David Cazier committed
540 541 542
template <typename PFP>
void generatePathToUpperStair(typename PFP::MAP& map, typename PFP::TVEC3& position, Dart dLower,
                              Dart dUpper)
543
{
David Cazier's avatar
David Cazier committed
544 545
	if (dLower != map.phi2(dLower) || dUpper != map.phi2(dUpper))
	{
David Cazier's avatar
David Cazier committed
546
		std::cout
David Cazier's avatar
David Cazier committed
547 548
		    << "generatePathToUpperStair : lower and upper stair darts must be fixpoint in phi2"
		    << std::endl ;
David Cazier's avatar
David Cazier committed
549
		return ;
550 551 552
	}

	//create the path
David Cazier's avatar
David Cazier committed
553 554 555 556 557
	Dart dPathUp = map.newFace(4) ;
	Dart dInBetweenUp = map.newFace(4) ;
	Dart dInBetweenDown = map.newFace(4) ;
	Dart dInBetweenMid = map.newFace(4) ;
	Dart dPathDown = map.newFace(4) ;
558 559

	//sew the path
David Cazier's avatar
David Cazier committed
560 561 562 563
	map.sewFaces(dUpper, map.phi1(map.phi1(dPathUp))) ;
	map.sewFaces(dPathUp, map.phi1(map.phi1(dInBetweenUp))) ;
	map.sewFaces(dLower, map.phi1(map.phi1(dPathDown))) ;
	map.sewFaces(dPathDown, map.phi1(map.phi1(dInBetweenDown))) ;
564

David Cazier's avatar
David Cazier committed
565 566
	map.sewFaces(map.phi1(dInBetweenDown), map.phi_1(dInBetweenMid)) ;
	map.sewFaces(map.phi_1(dInBetweenUp), map.phi1(dInBetweenMid)) ;
567 568

	//embed the inBetween floor
David Cazier's avatar
David Cazier committed
569
	float z = (position[dLower][2] + position[dUpper][2]) / 2.0f ;
570 571

	//from lower path
David Cazier's avatar
David Cazier committed
572
	typename PFP::VEC3 vDown = position[map.phi1(dLower)] - position[map.phi1(map.phi1(dLower))] ;
573

David Cazier's avatar
David Cazier committed
574 575
	position[map.phi1(map.phi1(dInBetweenDown))] = position[map.phi1(dLower)] + vDown ;
	position[map.phi_1(dInBetweenDown)] = position[dLower] + vDown ;
576

David Cazier's avatar
David Cazier committed
577 578
	position[dInBetweenDown] = position[map.phi_1(dInBetweenDown)] + vDown ;
	position[map.phi1(dInBetweenDown)] = position[map.phi1(map.phi1(dInBetweenDown))] + vDown ;
579 580

	//from upper path
David Cazier's avatar
David Cazier committed
581 582 583 584 585 586 587
	position[map.phi1(map.phi1(dInBetweenUp))] = position[map.phi1(dUpper)] + vDown ;
	position[map.phi_1(dInBetweenUp)] = position[dUpper] + vDown ;

	position[dInBetweenUp] = position[map.phi_1(dInBetweenUp)] + vDown ;
	position[map.phi1(dInBetweenUp)] = position[map.phi1(map.phi1(dInBetweenUp))] + vDown ;

	Dart dd = dInBetweenUp ;
David Cazier's avatar
David Cazier committed
588 589
	do
	{
David Cazier's avatar
David Cazier committed
590 591 592 593 594
		position[dd][2] = z ;
		dd = map.phi1(dd) ;
	} while (dd != dInBetweenUp) ;

	dd = dInBetweenDown ;
David Cazier's avatar
David Cazier committed
595 596
	do
	{
David Cazier's avatar
David Cazier committed
597 598 599
		position[dd][2] = z ;
		dd = map.phi1(dd) ;
	} while (dd != dInBetweenDown) ;
600 601
}

David Cazier's avatar
David Cazier committed
602
template <typename PFP>
David Cazier's avatar
David Cazier committed
603
void generatePlanet(EnvMap& envMap)
Thomas's avatar
Thomas committed
604
{
David Cazier's avatar
David Cazier committed
605 606 607 608 609 610 611 612 613 614 615
	unsigned int nx = envMap.geometry.size(0) / envMap.maxCellSize ;
	unsigned int ny = envMap.geometry.size(1) / envMap.maxCellSize ;
	if (nx < 1) nx = 1 ;
	if (ny < 1) ny = 1 ;

	Algo::Modelisation::Polyhedron<PFP> prim(envMap.map, envMap.position) ;
	prim.cylinder_topo(nx, ny, true, true) ;

	double pi = 3.14159265358979323846f ;
	double xRadius = envMap.geometry.size(0) / 2 * pi ;
	double yRadius = envMap.geometry.size(1) / 2 * pi ;
Thomas's avatar
Thomas committed
616

David Cazier's avatar
David Cazier committed
617
	prim.embedSphere((xRadius+yRadius)/2.0f) ;
Thomas's avatar
Thomas committed
618 619
}

Jund Thomas's avatar
Jund Thomas committed
620
template <typename PFP>
Jund Thomas's avatar
Jund Thomas committed
621
typename PFP::VEC3 parametrization(typename PFP::VEC3 p, float r,const Geom::BoundingBox<typename PFP::VEC3>& bb)
Jund Thomas's avatar
Jund Thomas committed
622 623 624 625 626 627 628 629 630
{
	p[0] = 2.0f*M_PI*(p[0]-bb.min()[0])/bb.size(0);
	p[1] = ((2.0f*M_PI*(p[1]-bb.min()[1])/bb.size(1))-M_PI)/2.0f;

	return typename PFP::VEC3(2.0f*r*cos(p[0])*cos(p[1]),
								2.0f*r*sin(p[0])*cos(p[1]),
								2.0f*r*sin(p[1]));
}

Jund Thomas's avatar
Jund Thomas committed
631 632 633 634 635 636 637 638 639 640 641 642
template <typename PFP>
void planetify(typename PFP::MAP& map, typename PFP::TVEC3& position, float r)
{
	Geom::BoundingBox<typename PFP::VEC3> bb ;
	bb = Algo::Geometry::computeBoundingBox<PFP>(map, position) ;

	typedef typename PFP::VEC3 VEC3 ;
	TraversorV<typename PFP::MAP> tv(map);

	//apply inverted transformation to build a sphere from planar coordinates (not working)
	for(Dart d = tv.begin() ; d != tv.end() ; d = tv.next())
	{
Jund Thomas's avatar
Jund Thomas committed
643
		position[d] = parametrization<PFP>(position[d], r, bb);
Jund Thomas's avatar
Jund Thomas committed
644 645 646
	}
}

Jund Thomas's avatar
Jund Thomas committed
647
template <typename PFP>
Jund Thomas's avatar
Jund Thomas committed
648
void planetify(typename PFP::MAP& map, typename PFP::TVEC3& position, float r,const Geom::BoundingBox<typename PFP::VEC3>& bb)
Jund Thomas's avatar
Jund Thomas committed
649 650 651 652 653 654 655 656 657
{
	TraversorV<typename PFP::MAP> tv(map);
	for(Dart d = tv.begin() ; d != tv.end() ; d = tv.next())
	{
		position[d] = parametrization<PFP>(position[d], r, bb);
	}
}


David Cazier's avatar
David Cazier committed
658
template <typename PFP>
David Cazier's avatar
David Cazier committed
659
void simplifyFreeSpace(typename PFP::MAP& map, typename PFP::TVEC3& position,
David Cazier's avatar
David Cazier committed
660
                       CellMarker<EDGE>& obstacleMark, CellMarker<FACE>& buildingMark)
Pierre Kraemer's avatar
Pierre Kraemer committed
661
{
David Cazier's avatar
David Cazier committed
662 663 664
	typedef typename PFP::VEC3 VEC3 ;
	typedef std::multimap<float, Dart> VEC_D_A ;

David Cazier's avatar
David Cazier committed
665 666
	FaceAutoAttribute<float> tableArea(map) ;
	EdgeAutoAttribute<CGoGN::NoMathIONameAttribute<VEC_D_A::iterator> > tableIt(map) ;
David Cazier's avatar
David Cazier committed
667 668 669

	VEC_D_A orderedD ;

Pierre Kraemer's avatar
Pierre Kraemer committed
670
	// compute all heuristic and construct multimap
David Cazier's avatar
David Cazier committed
671
	Algo::Geometry::computeAreaFaces<PFP>(map, position, tableArea) ;
David Cazier's avatar
David Cazier committed
672
	CellMarker<EDGE> eM(map) ;
David Cazier's avatar
David Cazier committed
673 674 675 676
	for (Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if (!eM.isMarked(d) && !obstacleMark.isMarked(d) && !buildingMark.isMarked(d))
		{
David Cazier's avatar
David Cazier committed
677
			eM.mark(d) ;
David Cazier's avatar
David Cazier committed
678
			tableIt[d] = orderedD.insert(std::make_pair(tableArea[d] + tableArea[map.phi2(d)], d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
679 680
		}
	}
David Cazier's avatar
David Cazier committed
681 682 683 684 685 686
	eM.unmarkAll() ;

	bool stillSimplif = true ;
	VEC_D_A::iterator it = orderedD.begin() ;
	if (it == orderedD.end()) stillSimplif = false ;

David Cazier's avatar
David Cazier committed
687 688
	while (stillSimplif)
	{
David Cazier's avatar
David Cazier committed
689
		Dart d = it->second ;
David Cazier's avatar
David Cazier committed
690 691
		if (!map.sameFace(d, map.phi2(d)))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
692
			// remove selected edge
David Cazier's avatar
David Cazier committed
693 694 695 696 697 698
			float sumArea = it->first ;
			orderedD.erase(it) ;
			Dart dd = map.phi1(d) ;
			map.mergeFaces(d) ;
			tableArea[dd] = sumArea ;

Pierre Kraemer's avatar
Pierre Kraemer committed
699 700
			// erase all edges of new face from multimap
			Dart ddd = dd ;
David Cazier's avatar
David Cazier committed
701 702 703 704
			do
			{
				if (!eM.isMarked(ddd) && !obstacleMark.isMarked(ddd))
				{
David Cazier's avatar
David Cazier committed
705 706
					eM.mark(ddd) ;
					orderedD.erase(tableIt[ddd]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
707
				}
David Cazier's avatar
David Cazier committed
708 709
				ddd = map.phi1(ddd) ;
			} while (ddd != dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
710 711

			// collapse edges in faces if possible
David Cazier's avatar
David Cazier committed
712
			ddd = dd ;
David Cazier's avatar
David Cazier committed
713 714
			do
			{
David Cazier's avatar
David Cazier committed
715 716
				Dart dN = map.phi1(ddd) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
717
				// remove pending edges
David Cazier's avatar
David Cazier committed
718 719
				if (map.phi2(dN) == map.phi1(dN))
				{
David Cazier's avatar
David Cazier committed
720
					if (dN == dd || map.phi1(dN) == dd) dd = map.phi1(map.phi1(dN)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
721
//					VEC3 p = position[dN];
David Cazier's avatar
David Cazier committed
722 723
					map.collapseEdge(dN) ;
					dN = map.phi1(ddd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
724 725 726 727
//					position[dN] = p;
				}

				// simplify vertices of valence 2 -> check if no intersection is created
David Cazier's avatar
David Cazier committed
728 729
				if (map.alpha1(map.alpha1(dN)) == dN && !obstacleMark.isMarked(dN))
				{
David Cazier's avatar
David Cazier committed
730 731 732 733 734 735 736
					if (dN == dd || dN == map.phi2(dd)) dd = map.phi1(dd) ;
					VEC3 p = position[map.phi1(dN)] ;

					bool intersect = false ;
					Dart dI = map.phi1(map.phi1(dN)) ;
					VEC3 pA = position[map.phi_1(dN)] ;
					VEC3 pB = position[map.phi1(dN)] ;
David Cazier's avatar
David Cazier committed
737 738
					do
					{
David Cazier's avatar
David Cazier committed
739 740 741
						VEC3 p1 = position[dI] ;
						VEC3 p2 = position[map.phi1(dI)] ;
						if (Geom::testOrientation2D(p1, pA, pB)
David Cazier's avatar
David Cazier committed
742 743 744 745 746 747 748
						    != Geom::testOrientation2D(p2, pA, pB)
						    && Geom::testOrientation2D(pA, p1, p2)
						       != Geom::testOrientation2D(pB, p1, p2))
						{
							if (!Geom::arePointsEquals(p1, pA) && !Geom::arePointsEquals(p1, pB)
							    && !Geom::arePointsEquals(p2, pA)
							    && !Geom::arePointsEquals(p2, pB)) intersect = true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
749
						}
David Cazier's avatar
David Cazier committed
750 751 752
						dI = map.phi1(dI) ;
					} while (dI != map.phi_1(dN)) ;

David Cazier's avatar
David Cazier committed
753 754
					if (!intersect)
					{
David Cazier's avatar
David Cazier committed
755 756
						dN = map.phi2(dN) ;
						Dart dI = map.phi1(map.phi1(dN)) ;
David Cazier's avatar
David Cazier committed
757 758
						do
						{
David Cazier's avatar
David Cazier committed
759 760 761 762
							VEC3 v ;
							VEC3 p1 = position[dI] ;
							VEC3 p2 = position[map.phi1(dI)] ;
							if (Geom::testOrientation2D(p1, pA, pB)
David Cazier's avatar
David Cazier committed
763 764 765 766 767 768 769
							    != Geom::testOrientation2D(p2, pA, pB)
							    && Geom::testOrientation2D(pA, p1, p2)
							       != Geom::testOrientation2D(pB, p1, p2))
							{
								if (!Geom::arePointsEquals(p1, pA) && !Geom::arePointsEquals(p1, pB)
								    && !Geom::arePointsEquals(p2, pA)
								    && !Geom::arePointsEquals(p2, pB)) intersect = true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
770
							}
David Cazier's avatar
David Cazier committed
771 772
							dI = map.phi1(dI) ;
						} while (dI != map.phi_1(dN)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
773 774
					}

David Cazier's avatar
David Cazier committed
775 776
					if (!intersect)
					{
David Cazier's avatar
David Cazier committed
777 778
						map.collapseEdge(dN) ;
						position[map.phi1(ddd)] = p ;
Pierre Kraemer's avatar
Pierre Kraemer committed
779 780 781
					}
				}

David Cazier's avatar
David Cazier committed
782 783
				ddd = map.phi1(ddd) ;
			} while (ddd != dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
784

David Cazier's avatar
David Cazier committed
785
			ddd = dd ;
David Cazier's avatar
David Cazier committed
786 787 788 789
			do
			{
				if (eM.isMarked(ddd))
				{
David Cazier's avatar
David Cazier committed
790
					eM.unmark(ddd) ;
791
					tableIt[ddd] = orderedD.insert(
David Cazier's avatar
David Cazier committed
792
					    std::make_pair(tableArea[ddd] + tableArea[map.phi2(ddd)], ddd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
793
				}
David Cazier's avatar
David Cazier committed
794 795 796 797
				ddd = map.phi1(ddd) ;
			} while (ddd != dd) ;

			it = orderedD.begin() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
798
		}
David Cazier's avatar
David Cazier committed
799 800
		else
		{
David Cazier's avatar
David Cazier committed
801
			++it ;
Pierre Kraemer's avatar
Pierre Kraemer committed
802
		}
David Cazier's avatar
David Cazier committed
803 804

		if (it == orderedD.end()) stillSimplif = false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
805 806
	}

David Cazier's avatar
David Cazier committed
807
	convexifyFreeSpace<PFP>(map, position, obstacleMark, buildingMark) ;
808

David Cazier's avatar
David Cazier committed
809 810 811 812
	for (Dart d = map.begin(); d != map.end(); map.next(d))
	{
		if (buildingMark.isMarked(d) && !buildingMark.isMarked(map.phi2(d)))
		{
David Cazier's avatar
David Cazier committed
813
			if (map.alpha1(map.alpha1(map.phi1(d))) == map.phi1(d)
David Cazier's avatar
David Cazier committed
814 815 816
			    && Geom::testOrientation2D(position[d], position[map.phi1(d)],
			                               position[map.phi1(map.phi1(d))])
			       == Geom::ALIGNED)
817

David Cazier's avatar
David Cazier committed
818
			{
David Cazier's avatar
David Cazier committed
819
				VEC3 p = position[map.phi1(map.phi1(d))] ;
820
//				Dart dN = map.phi1(d);
David Cazier's avatar
David Cazier committed
821 822
				map.collapseEdge(map.phi1(d)) ;
				position[map.phi1(d)] = p ;
823 824 825 826
			}
		}
	}

David Cazier's avatar
David Cazier committed
827
	map.check() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
828 829
}

David Cazier's avatar
David Cazier committed
830
template <typename PFP>
pitiot's avatar
pitiot committed
831
bool isAnEar(typename PFP::MAP& map, VertexAttribute<typename PFP::VEC3>& position, Dart dd, float& area)
Pierre Kraemer's avatar