Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp @ 392

Revision 392, 61.7 KB checked in by mattausch, 19 years ago (diff)

Line
1	#include "Plane3.h"
2	#include "ViewCellBsp.h"
3	#include "Mesh.h"
4	#include "common.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "Polygon3.h"
8	#include "Ray.h"
9	#include "AxisAlignedBox3.h"
10	#include <stack>
11	#include <time.h>
12	#include <iomanip>
13	#include "Exporter.h"
14	#include "Plane3.h"
15
16	int BspTree::sTermMaxPolygons = 10;
17	int BspTree::sTermMinPvs = 20;
18	int BspTree::sTermMaxDepth = 20;
19	int BspTree::sMaxPolyCandidates = 10;
20	int BspTree::sMaxRayCandidates = 10;
21	int BspTree::sSplitPlaneStrategy = BALANCED_POLYS;
22	int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
23	int BspTree::sTermMaxPolysForAxisAligned = 50;
24	int BspTree::sTermMaxObjectsForAxisAligned = 50;
25	int BspTree::sTermMaxRaysForAxisAligned = -1;
26	int BspTree::sTermMaxRays = -1;
27	int BspTree::sMinPvsDif = 10;
28	int BspTree::sMinPvs = 10;
29	int BspTree::sMaxPvs = 500;
30
31	float BspTree::sCt_div_ci = 1.0f;
32	float BspTree::sSplitBorder = 1.0f;
33	float BspTree::sMaxCostRatio = 0.9f;
34
35	//-- factors for bsp tree split plane heuristics
36
37	float BspTree::sLeastSplitsFactor = 1.0f;
38	float BspTree::sBalancedPolysFactor = 1.0f;
39	float BspTree::sBalancedViewCellsFactor = 1.0f;
40
41	// NOTE: very important criterium for 2.5d scenes
42	float BspTree::sVerticalSplitsFactor = 1.0f;
43	float BspTree::sLargestPolyAreaFactor = 1.0f;
44	float BspTree::sBlockedRaysFactor = 1.0f;
45	float BspTree::sLeastRaySplitsFactor = 1.0f;
46	float BspTree::sBalancedRaysFactor = 1.0f;
47	float BspTree::sPvsFactor = 1.0f;
48
49	int BspNode::mailID = 1;
50
51	/** Evaluates split plane classification with respect to the plane's
52	contribution for a minimum number splits in the tree.
53	*/
54	float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
55	/** Evaluates split plane classification with respect to the plane's
56	contribution for a balanced tree.
57	*/
58	float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
59
60	/** Evaluates split plane classification with respect to the plane's
61	contribution for a minimum number of ray splits.
62	*/
63	float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
64	/** Evaluates split plane classification with respect to the plane's
65	contribution for balanced rays.
66	*/
67	float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
68
69	/****************************************************************/
70	/* class BspNode implementation */
71	/****************************************************************/
72
73	BspNode::BspNode():
74	mParent(NULL)
75	{}
76
77	BspNode::BspNode(BspInterior *parent):
78	mParent(parent)
79	{}
80
81
82	bool BspNode::IsRoot() const
83	{
84	return mParent == NULL;
85	}
86
87	BspInterior *BspNode::GetParent()
88	{
89	return mParent;
90	}
91
92	void BspNode::SetParent(BspInterior *parent)
93	{
94	mParent = parent;
95	}
96
97	/****************************************************************/
98	/* class BspInterior implementation */
99	/****************************************************************/
100
101
102	BspInterior::BspInterior(const Plane3 &plane):
103	mPlane(plane), mFront(NULL), mBack(NULL)
104	{}
105
106	bool BspInterior::IsLeaf() const
107	{
108	return false;
109	}
110
111	BspNode *BspInterior::GetBack()
112	{
113	return mBack;
114	}
115
116	BspNode *BspInterior::GetFront()
117	{
118	return mFront;
119	}
120
121	Plane3 *BspInterior::GetPlane()
122	{
123	return &mPlane;
124	}
125
126	void BspInterior::ReplaceChildLink(BspNode oldChild, BspNode newChild)
127	{
128	if (mBack == oldChild)
129	mBack = newChild;
130	else
131	mFront = newChild;
132	}
133
134	void BspInterior::SetupChildLinks(BspNode b, BspNode f)
135	{
136	mBack = b;
137	mFront = f;
138	}
139
140	int BspInterior::SplitPolygons(PolygonContainer &polys,
141	PolygonContainer &frontPolys,
142	PolygonContainer &backPolys,
143	PolygonContainer &coincident)
144	{
145	Polygon3 *splitPoly = NULL;
146
147	int splits = 0;
148
149	#ifdef _Debug
150	Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
151	#endif
152	while (!polys.empty())
153	{
154	Polygon3 *poly = polys.back();
155	polys.pop_back();
156
157	//Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
158
159	// classify polygon
160	const int cf = poly->ClassifyPlane(mPlane);
161
162	Polygon3 *front_piece = NULL;
163	Polygon3 *back_piece = NULL;
164
165	VertexContainer splitVertices;
166
167	switch (cf)
168	{
169	case Polygon3::COINCIDENT:
170	coincident.push_back(poly);
171	break;
172	case Polygon3::FRONT_SIDE:
173	frontPolys.push_back(poly);
174	break;
175	case Polygon3::BACK_SIDE:
176	backPolys.push_back(poly);
177	break;
178	case Polygon3::SPLIT:
179	front_piece = new Polygon3(poly->mParent);
180	back_piece = new Polygon3(poly->mParent);
181
182	//-- split polygon into front and back part
183	poly->Split(mPlane,
184	*front_piece,
185	*back_piece,
186	splitVertices);
187
188	++ splits; // increase number of splits
189
190	//-- inherit rays from parent polygon for blocked ray criterium
191	poly->InheritRays(front_piece, back_piece);
192	//Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
193
194	// check if polygons still valid
195	if (front_piece->Valid())
196	frontPolys.push_back(front_piece);
197	else
198	DEL_PTR(front_piece);
199
200	if (back_piece->Valid())
201	backPolys.push_back(back_piece);
202	else
203	DEL_PTR(back_piece);
204
205	#ifdef _DEBUG
206	Debug << "split " << poly << endl << front_piece << endl << *back_piece << endl;
207	#endif
208	DEL_PTR(poly);
209	break;
210	default:
211	Debug << "SHOULD NEVER COME HERE\n";
212	break;
213	}
214	}
215
216	return splits;
217	}
218
219	/****************************************************************/
220	/* class BspLeaf implementation */
221	/****************************************************************/
222	BspLeaf::BspLeaf(): mViewCell(NULL)
223	{
224	}
225
226	BspLeaf::BspLeaf(BspViewCell *viewCell):
227	mViewCell(viewCell)
228	{
229	}
230
231	BspLeaf::BspLeaf(BspInterior *parent):
232	BspNode(parent), mViewCell(NULL)
233	{}
234
235	BspLeaf::BspLeaf(BspInterior parent, BspViewCell viewCell):
236	BspNode(parent), mViewCell(viewCell)
237	{
238	}
239
240	BspViewCell *BspLeaf::GetViewCell() const
241	{
242	return mViewCell;
243	}
244
245	void BspLeaf::SetViewCell(BspViewCell *viewCell)
246	{
247	mViewCell = viewCell;
248	}
249
250	bool BspLeaf::IsLeaf() const
251	{
252	return true;
253	}
254
255	void BspLeaf::AddToPvs(const BoundedRayContainer &rays,
256	int &sampleContributions,
257	int &contributingSamples)
258	{
259	sampleContributions = 0;
260	contributingSamples = 0;
261
262	BoundedRayContainer::const_iterator it, it_end = rays.end();
263
264	// add contributions from samples to the PVS
265	for (it = rays.begin(); it != it_end; ++ it)
266	{
267	int contribution = 0;
268	Ray ray = (it)->mRay;
269
270	if (!ray->intersections.empty())
271	{
272	//contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
273	}
274
275	//contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
276
277	if (contribution > 0)
278	{
279	sampleContributions += contribution;
280	++ contributingSamples;
281	}
282
283	// warning: not ordered
284	ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
285	}
286	}
287
288
289	/****************************************************************/
290	/* class BspTree implementation */
291	/****************************************************************/
292
293	BspTree::BspTree(BspViewCell *viewCell):
294	mRootCell(viewCell), mRoot(NULL), mGenerateViewCells(false),
295	mStorePiercingRays(true)
296	{
297	Randomize(); // initialise random generator for heuristics
298	}
299
300	const BspTreeStatistics &BspTree::GetStatistics() const
301	{
302	return mStat;
303	}
304
305	void BspViewCellsStatistics::Print(ostream &app) const
306	{
307	app << "===== BspViewCells statistics ===============\n";
308
309	app << setprecision(4);
310
311	app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
312
313	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
314
315	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
316
317	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
318
319	app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
320
321	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
322
323	app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;
324
325	app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;
326
327	app << "===== END OF BspViewCells statistics ==========\n";
328	}
329
330	void BspTreeStatistics::Print(ostream &app) const
331	{
332	app << "===== BspTree statistics ===============\n";
333
334	app << setprecision(4);
335
336	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
337
338	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
339
340	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
341
342	app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
343
344	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
345	maxDepthNodes * 100 / (double)Leaves() << endl;
346
347	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
348
349	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
350
351	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
352
353	app << "#N_INPUT_POLYGONS (number of input polygons )\n" << polys << endl;
354
355	//app << "#N_PVS: " << pvs << endl;
356
357	app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
358	(polys + splits) / (double)polys << endl;
359
360	app << "===== END OF BspTree statistics ==========\n";
361	}
362
363
364	BspTree::~BspTree()
365	{
366	std::stack<BspNode *> tStack;
367
368	tStack.push(mRoot);
369
370	while (!tStack.empty())
371	{
372	BspNode *node = tStack.top();
373
374	tStack.pop();
375
376	if (!node->IsLeaf())
377	{
378	BspInterior interior = dynamic_cast<BspInterior >(node);
379
380	// push the children on the stack (there are always two children)
381	tStack.push(interior->GetBack());
382	tStack.push(interior->GetFront());
383	}
384
385	DEL_PTR(node);
386	}
387	}
388
389	void BspTree::InsertViewCell(ViewCell *viewCell)
390	{
391	PolygonContainer *polys = new PolygonContainer();
392
393	// extract polygons that guide the split process
394	mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
395	mBox.Include(viewCell->GetBox()); // add to BSP aabb
396
397	InsertPolygons(polys);
398	}
399
400	void BspTree::InsertPolygons(PolygonContainer *polys)
401	{
402	std::stack<BspTraversalData> tStack;
403
404	// traverse existing tree or create new tree
405	if (!mRoot)
406	mRoot = new BspLeaf();
407
408	tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,
409	mBox.SurfaceArea(), new BspNodeGeometry()));
410
411	while (!tStack.empty())
412	{
413	// filter polygons donw the tree
414	BspTraversalData tData = tStack.top();
415	tStack.pop();
416
417	if (!tData.mNode->IsLeaf())
418	{
419	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
420
421	//-- filter view cell polygons down the tree until a leaf is reached
422	if (!tData.mPolygons->empty())
423	{
424	PolygonContainer *frontPolys = new PolygonContainer();
425	PolygonContainer *backPolys = new PolygonContainer();
426	PolygonContainer coincident;
427
428	int splits = 0;
429
430	// split viewcell polygons with respect to split plane
431	splits += interior->SplitPolygons(*tData.mPolygons,
432	*frontPolys,
433	*backPolys,
434	coincident);
435
436	// extract view cells associated with the split polygons
437	ViewCell *frontViewCell = mRootCell;
438	ViewCell *backViewCell = mRootCell;
439
440	BspTraversalData frontData(interior->GetFront(),
441	frontPolys,
442	tData.mDepth + 1,
443	mRootCell,
444	tData.mRays,
445	tData.mPvs,
446	mBox.SurfaceArea(),
447	new BspNodeGeometry());
448
449	BspTraversalData backData(interior->GetBack(),
450	backPolys,
451	tData.mDepth + 1,
452	mRootCell,
453	tData.mRays,
454	tData.mPvs,
455	mBox.SurfaceArea(),
456	new BspNodeGeometry());
457
458	if (!mGenerateViewCells)
459	{
460	ExtractViewCells(frontData,
461	backData,
462	coincident,
463	interior->mPlane);
464	}
465
466	// don't need coincident polygons anymore
467	CLEAR_CONTAINER(coincident);
468
469	mStat.splits += splits;
470
471	// push the children on the stack
472	tStack.push(frontData);
473	tStack.push(backData);
474	}
475
476	// cleanup
477	DEL_PTR(tData.mPolygons);
478	}
479	else
480	{
481	// reached leaf => subdivide current viewcell
482	BspNode *subRoot = Subdivide(tStack, tData);
483	}
484	}
485	}
486
487	int BspTree::AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent)
488	{
489	FaceContainer::const_iterator fi;
490
491	// copy the face data to polygons
492	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
493	{
494	Polygon3 poly = new Polygon3((fi), mesh);
495
496	if (poly->Valid())
497	{
498	poly->mParent = parent; // set parent intersectable
499	polys.push_back(poly);
500	}
501	else
502	DEL_PTR(poly);
503	}
504	return (int)mesh->mFaces.size();
505	}
506
507	int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
508	PolygonContainer &polys,
509	int maxObjects)
510	{
511	int limit = (maxObjects > 0) ?
512	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
513
514	int polysSize = 0;
515
516	for (int i = 0; i < limit; ++ i)
517	{
518	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
519	{
520	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
521	polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
522	}
523	}
524
525	return polysSize;
526	}
527
528	int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
529	{
530	int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
531
532	for (int i = 0; i < limit; ++i)
533	{
534	Intersectable object = objects[i];//it;
535	Mesh *mesh = NULL;
536
537	switch (object->Type()) // extract the meshes
538	{
539	case Intersectable::MESH_INSTANCE:
540	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
541	break;
542	case Intersectable::VIEW_CELL:
543	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
544	break;
545	// TODO: handle transformed mesh instances
546	default:
547	Debug << "intersectable type not supported" << endl;
548	break;
549	}
550
551	if (mesh) // copy the mesh data to polygons
552	{
553	mBox.Include(object->GetBox()); // add to BSP tree aabb
554	AddMeshToPolygons(mesh, polys, mRootCell);
555	}
556	}
557
558	return (int)polys.size();
559	}
560
561	void BspTree::Construct(const ViewCellContainer &viewCells)
562	{
563	mStat.nodes = 1;
564	mBox.Initialize(); // initialise bsp tree bounding box
565
566	// copy view cell meshes into one big polygon soup
567	PolygonContainer *polys = new PolygonContainer();
568	mStat.polys = AddToPolygonSoup(viewCells, *polys);
569
570	// construct tree from the view cell polygons
571	Construct(polys, new BoundedRayContainer());
572	}
573
574
575	void BspTree::Construct(const ObjectContainer &objects)
576	{
577	mStat.nodes = 1;
578	mBox.Initialize(); // initialise bsp tree bounding box
579
580	PolygonContainer *polys = new PolygonContainer();
581
582	// copy mesh instance polygons into one big polygon soup
583	mStat.polys = AddToPolygonSoup(objects, *polys);
584
585	// construct tree from polygon soup
586	Construct(polys, new BoundedRayContainer());
587	}
588
589	void BspTree::Construct(const RayContainer &sampleRays)
590	{
591	mStat.nodes = 1;
592	mBox.Initialize(); // initialise BSP tree bounding box
593
594	PolygonContainer *polys = new PolygonContainer();
595	BoundedRayContainer *rays = new BoundedRayContainer();
596
597	RayContainer::const_iterator rit, rit_end = sampleRays.end();
598
599	long startTime = GetTime();
600
601	Debug << "** Extracting polygons from rays **\n";
602
603	std::map<Face , Polygon3 > facePolyMap;
604
605	//-- extract polygons intersected by the rays
606	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
607	{
608	Ray ray = rit;
609
610	// get ray-face intersection. Store polygon representing the rays together
611	// with rays intersecting the face.
612	if (!ray->intersections.empty())
613	{
614	MeshInstance obj = dynamic_cast<MeshInstance >(ray->intersections[0].mObject);
615	Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
616
617	std::map<Face , Polygon3 >::iterator it = facePolyMap.find(face);
618
619	if (it != facePolyMap.end())
620	{
621	//store rays if needed for heuristics
622	if (sSplitPlaneStrategy & BLOCKED_RAYS)
623	(*it).second->mPiercingRays.push_back(ray);
624	}
625	else
626	{ //store rays if needed for heuristics
627	Polygon3 *poly = new Polygon3(face, obj->GetMesh());
628	poly->mParent = obj;
629	polys->push_back(poly);
630
631	if (sSplitPlaneStrategy & BLOCKED_RAYS)
632	poly->mPiercingRays.push_back(ray);
633
634	facePolyMap[face] = poly;
635	}
636	}
637	}
638
639	facePolyMap.clear();
640
641	// compue bounding box
642	Polygon3::IncludeInBox(*polys, mBox);
643
644	//-- store rays
645	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
646	{
647	Ray ray = rit;
648	ray->SetId(-1); // reset id
649
650	float minT, maxT;
651	if (BoundRay(*ray, minT, maxT))
652	rays->push_back(new BoundedRay(ray, minT, maxT));
653	}
654
655	mStat.polys = (int)polys->size();
656
657	Debug << "** Finished polygon extraction **" << endl;
658	Debug << (int)polys->size() << " polys extracted from " << (int)sampleRays.size() << " rays" << endl;
659	Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
660
661	Construct(polys, rays);
662	}
663
664	void BspTree::Construct(PolygonContainer polys, BoundedRayContainer rays)
665	{
666	std::stack<BspTraversalData> tStack;
667
668	mRoot = new BspLeaf();
669
670	BspNodeGeometry *cell = new BspNodeGeometry();
671	ConstructGeometry(mRoot, *cell);
672
673	BspTraversalData tData(mRoot, polys, 0, mRootCell, rays,
674	ComputePvsSize(*rays), cell->GetArea(), cell);
675
676	tStack.push(tData);
677
678	long startTime = GetTime();
679	cout << "** Contructing bsp tree **\n";
680
681	while (!tStack.empty())
682	{
683	tData = tStack.top();
684	tStack.pop();
685
686	// subdivide leaf node
687	BspNode *subRoot = Subdivide(tStack, tData);
688	}
689
690	cout << "** Finished tree construction **\n";
691	Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
692	}
693
694
695	BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
696	{
697	//-- terminate traversal
698	if (((int)tData.mPolygons->size() <= sTermMaxPolygons) \|\|
699	((int)tData.mRays->size() <= sTermMaxRays) \|\|
700	((int)tData.mPvs <= sTermMinPvs) \|\|
701	(tData.mDepth >= sTermMaxDepth))
702
703	{
704	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
705
706	BspViewCell *viewCell;
707
708	// generate new view cell for each leaf
709	if (mGenerateViewCells)
710	{
711	viewCell = dynamic_cast<BspViewCell *>(ViewCell::Generate());
712	}
713	else
714	{
715	// add view cell to leaf
716	viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
717	}
718
719	leaf->SetViewCell(viewCell);
720	viewCell->mBspLeaves.push_back(leaf);
721
722	//-- add pvs
723	if (viewCell != mRootCell)
724	{
725	int conSamp = 0, sampCon = 0;
726	leaf->AddToPvs(*tData.mRays, conSamp, sampCon);
727
728	mStat.contributingSamples += conSamp;
729	mStat.sampleContributions += sampCon;
730	}
731
732	EvaluateLeafStats(tData);
733
734	//-- clean up
735
736	// discard polygons
737	CLEAR_CONTAINER(*tData.mPolygons);
738	// discard rays
739	CLEAR_CONTAINER(*tData.mRays);
740
741	DEL_PTR(tData.mPolygons);
742	DEL_PTR(tData.mRays);
743	DEL_PTR(tData.mCell);
744
745	return leaf;
746	}
747
748	//-- continue subdivision
749
750	PolygonContainer coincident;
751
752	PolygonContainer *frontPolys = new PolygonContainer();
753	PolygonContainer *backPolys = new PolygonContainer();
754
755	BoundedRayContainer *frontRays = new BoundedRayContainer();
756	BoundedRayContainer *backRays = new BoundedRayContainer();
757
758	BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
759	new BoundedRayContainer(), 0, NULL, 0);
760	BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
761	new BoundedRayContainer(), 0, NULL, 0);
762
763	// create new interior node and two leaf nodes
764	BspInterior *interior = SubdivideNode(tData,
765	tFrontData,
766	tBackData,
767	coincident);
768
769	#ifdef _DEBUG
770	if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
771	{ for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
772	Debug << (it) << " " << (it)->GetArea() << " " << (*it)->mParent << endl ;
773	Debug << endl;}
774	#endif
775
776	// extract view cells from coincident polygons according to plane normal
777	// only if front or back polygons are empty
778	if (!mGenerateViewCells)
779	{
780	ExtractViewCells(tFrontData,
781	tBackData,
782	coincident,
783	interior->mPlane);
784
785	}
786
787	// don't need coincident polygons anymory
788	CLEAR_CONTAINER(coincident);
789
790	// push the children on the stack
791	tStack.push(tFrontData);
792	tStack.push(tBackData);
793
794	// cleanup
795	DEL_PTR(tData.mNode);
796	DEL_PTR(tData.mPolygons);
797	DEL_PTR(tData.mRays);
798	DEL_PTR(tData.mCell);
799
800	return interior;
801	}
802
803	void BspTree::ExtractViewCells(BspTraversalData &frontData,
804	BspTraversalData &backData,
805	const PolygonContainer &coincident,
806	const Plane3 splitPlane) const
807	{
808	// if not empty, tree is further subdivided => don't have to find view cell
809	bool foundFront = !frontData.mPolygons->empty();
810	bool foundBack = !frontData.mPolygons->empty();
811
812	PolygonContainer::const_iterator it =
813	coincident.begin(), it_end = coincident.end();
814
815	//-- find first view cells in front and back leafs
816	for (; !(foundFront && foundBack) && (it != it_end); ++ it)
817	{
818	if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
819	{
820	backData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
821	foundBack = true;
822	}
823	else
824	{
825	frontData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
826	foundFront = true;
827	}
828	}
829	}
830
831	BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
832	BspTraversalData &frontData,
833	BspTraversalData &backData,
834	PolygonContainer &coincident)
835	{
836	mStat.nodes += 2;
837
838	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
839	// select subdivision plane
840	BspInterior *interior =
841	new BspInterior(SelectPlane(leaf, tData, frontData, backData));
842
843	#ifdef _DEBUG
844	Debug << interior << endl;
845	#endif
846
847	// subdivide rays into front and back rays
848	SplitRays(interior->mPlane, tData.mRays, frontData.mRays, *backData.mRays);
849
850	// subdivide polygons with plane
851	mStat.splits += interior->SplitPolygons(*tData.mPolygons,
852	*frontData.mPolygons,
853	*backData.mPolygons,
854	coincident);
855
856	BspInterior *parent = leaf->GetParent();
857
858	// replace a link from node's parent
859	if (!leaf->IsRoot())
860	{
861	parent->ReplaceChildLink(leaf, interior);
862	interior->SetParent(parent);
863	}
864	else // new root
865	{
866	mRoot = interior;
867	}
868
869	// and setup child links
870	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
871
872	frontData.mNode = interior->mFront;
873	backData.mNode = interior->mBack;
874
875	return interior;
876	}
877
878	void BspTree::SortSplitCandidates(const PolygonContainer &polys,
879	const int axis,
880	vector<SortableEntry> &splitCandidates) const
881	{
882	splitCandidates.clear();
883
884	int requestedSize = 2 * (int)polys.size();
885	// creates a sorted split candidates array
886	splitCandidates.reserve(requestedSize);
887
888	PolygonContainer::const_iterator it, it_end = polys.end();
889
890	AxisAlignedBox3 box;
891
892	// insert all queries
893	for(it = polys.begin(); it != it_end; ++ it)
894	{
895	box.Initialize();
896	box.Include((it));
897
898	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
899	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
900	}
901
902	stable_sort(splitCandidates.begin(), splitCandidates.end());
903	}
904
905
906	float BspTree::BestCostRatio(const PolygonContainer &polys,
907	const AxisAlignedBox3 &box,
908	const int axis,
909	float &position,
910	int &objectsBack,
911	int &objectsFront) const
912	{
913	vector<SortableEntry> splitCandidates;
914
915	SortSplitCandidates(polys, axis, splitCandidates);
916
917	// go through the lists, count the number of objects left and right
918	// and evaluate the following cost funcion:
919	// C = ct_div_ci + (ol + or)/queries
920
921	int objectsLeft = 0, objectsRight = (int)polys.size();
922
923	float minBox = box.Min(axis);
924	float maxBox = box.Max(axis);
925	float boxArea = box.SurfaceArea();
926
927	float minBand = minBox + sSplitBorder * (maxBox - minBox);
928	float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
929
930	float minSum = 1e20f;
931	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
932
933	for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
934	{
935	switch ((*ci).type)
936	{
937	case SortableEntry::POLY_MIN:
938	++ objectsLeft;
939	break;
940	case SortableEntry::POLY_MAX:
941	-- objectsRight;
942	break;
943	default:
944	break;
945	}
946
947	if ((ci).value > minBand && (ci).value < maxBand)
948	{
949	AxisAlignedBox3 lbox = box;
950	AxisAlignedBox3 rbox = box;
951	lbox.SetMax(axis, (*ci).value);
952	rbox.SetMin(axis, (*ci).value);
953
954	float sum = objectsLeft * lbox.SurfaceArea() +
955	objectsRight * rbox.SurfaceArea();
956
957	if (sum < minSum)
958	{
959	minSum = sum;
960	position = (*ci).value;
961
962	objectsBack = objectsLeft;
963	objectsFront = objectsRight;
964	}
965	}
966	}
967
968	float oldCost = (float)polys.size();
969	float newCost = sCt_div_ci + minSum / boxArea;
970	float ratio = newCost / oldCost;
971
972
973	#if 0
974	Debug << "====================" << endl;
975	Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
976	<< "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
977	#endif
978	return ratio;
979	}
980
981	bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
982	const PolygonContainer &polys) const
983	{
984	AxisAlignedBox3 box;
985	box.Initialize();
986
987	// create bounding box of region
988	Polygon3::IncludeInBox(polys, box);
989
990	int objectsBack = 0, objectsFront = 0;
991	int axis = 0;
992	float costRatio = MAX_FLOAT;
993	Vector3 position;
994
995	//-- area subdivision
996	for (int i = 0; i < 3; ++ i)
997	{
998	float p = 0;
999	float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1000
1001	if (r < costRatio)
1002	{
1003	costRatio = r;
1004	axis = i;
1005	position = p;
1006	}
1007	}
1008
1009	if (costRatio >= sMaxCostRatio)
1010	return false;
1011
1012	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1013	plane = Plane3(norm, position);
1014
1015	return true;
1016	}
1017
1018	Plane3 BspTree::SelectPlane(BspLeaf *leaf,
1019	BspTraversalData &data,
1020	BspTraversalData &frontData,
1021	BspTraversalData &backData)
1022	{
1023	if (data.mPolygons->empty() && data.mRays->empty())
1024	{
1025	Debug << "Warning: No autopartition polygon candidate available\n";
1026
1027	// return axis aligned split
1028	AxisAlignedBox3 box;
1029	box.Initialize();
1030
1031	// create bounding box of region
1032	Polygon3::IncludeInBox(*data.mPolygons, box);
1033
1034	const int axis = box.Size().DrivingAxis();
1035	const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
1036
1037	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1038	return Plane3(norm, position);
1039	}
1040
1041	if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
1042	((int)data.mPolygons->size() > sTermMaxPolysForAxisAligned) &&
1043	((int)data.mRays->size() > sTermMaxRaysForAxisAligned) &&
1044	((sTermMaxObjectsForAxisAligned < 0) \|\|
1045	(Polygon3::ParentObjectsSize(*data.mPolygons) > sTermMaxObjectsForAxisAligned)))
1046	{
1047	Plane3 plane;
1048	if (SelectAxisAlignedPlane(plane, *data.mPolygons))
1049	return plane;
1050	}
1051
1052	// simplest strategy: just take next polygon
1053	if (sSplitPlaneStrategy & RANDOM_POLYGON)
1054	{
1055	Polygon3 nextPoly = (data.mPolygons)[Random((int)data.mPolygons->size())];
1056	return nextPoly->GetSupportingPlane();
1057	}
1058
1059	// use heuristics to find appropriate plane
1060	return SelectPlaneHeuristics(leaf, data, frontData, backData);
1061	}
1062
1063	Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf,
1064	BspTraversalData &data,
1065	BspTraversalData &frontData,
1066	BspTraversalData &backData)
1067	{
1068	float lowestCost = MAX_FLOAT;
1069	Plane3 bestPlane;
1070
1071	int limit = sMaxPolyCandidates > 0 ?
1072	Min((int)data.mPolygons->size(), sMaxPolyCandidates) : (int)data.mPolygons->size();
1073
1074	int candidateIdx = limit;
1075
1076	for (int i = 0; i < limit; ++ i)
1077	{
1078	candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
1079
1080	Polygon3 poly = (data.mPolygons)[candidateIdx];
1081	// evaluate current candidate
1082	const float candidateCost =
1083	SplitPlaneCost(poly->GetSupportingPlane(), data, frontData, backData);
1084
1085	Debug << "cost: " << candidateCost << ", lowest: " << lowestCost << endl;
1086
1087	if (candidateCost < lowestCost)
1088	{
1089	bestPlane = poly->GetSupportingPlane();
1090	lowestCost = candidateCost;
1091	}
1092	}
1093
1094	//limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();
1095	const BoundedRayContainer *rays = data.mRays;
1096
1097	for (int i = 0; i < sMaxRayCandidates; ++ i)
1098	{
1099	Plane3 plane;
1100
1101	if (1)
1102	{
1103	Vector3 pt[3];
1104	int idx[3];
1105
1106	for (int j = 0; j < 3; j ++)
1107	{
1108	idx[j] = Random((int)rays->size() * 2);
1109
1110	BoundedRay bRay = (rays)[idx[j]];
1111	Ray *ray = bRay->mRay;
1112
1113	if (idx[j] < (int)rays->size())
1114	pt[j] = ray->Extrap(bRay->mMinT);
1115	else
1116	{
1117	idx[j] -= (int)rays->size();
1118	pt[j] = ray->Extrap(bRay->mMaxT);
1119	}
1120	}
1121
1122	plane = Plane3(pt[0], pt[1], pt[2]);
1123	}
1124	else
1125	{
1126	candidateIdx = Random((int)rays->size());
1127	BoundedRay bRay = (rays)[candidateIdx];
1128
1129	Ray *ray = bRay->mRay;
1130
1131	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1132	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1133
1134	const Vector3 pt = (maxPt + minPt) * 0.5;
1135
1136	const Vector3 normal = ray->GetDir();
1137
1138	plane = Plane3(normal, pt);
1139	}
1140
1141	const float candidateCost =
1142	SplitPlaneCost(plane, data, frontData, backData);
1143
1144	if (candidateCost < lowestCost)
1145	{
1146	Debug << "choose ray plane: " << lowestCost << endl;
1147	bestPlane = plane;
1148
1149	lowestCost = candidateCost;
1150	}
1151	else
1152	Debug << "ray cost: " << candidateCost << ", lowest: " << lowestCost << endl;
1153	}
1154
1155	//Debug << "Plane lowest cost: " << lowestCost << endl;
1156	return bestPlane;
1157	}
1158
1159	int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
1160	{
1161	const int candidateIdx = Random(currentIdx --);
1162
1163	// swap candidates to avoid testing same plane 2 times
1164	std::swap(polys[currentIdx], polys[candidateIdx]);
1165
1166	return currentIdx;
1167	//return Random((int)polys.size());
1168	}
1169
1170	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1171	const PolygonContainer &polys) const
1172	{
1173	float val = 0;
1174
1175	float sumBalancedPolys = 0;
1176	float sumSplits = 0;
1177	float sumPolyArea = 0;
1178	float sumBalancedViewCells = 0;
1179	float sumBlockedRays = 0;
1180	float totalBlockedRays = 0;
1181	//float totalArea = 0;
1182	int totalViewCells = 0;
1183
1184	// need three unique ids for each type of view cell
1185	// for balanced view cells criterium
1186	ViewCell::NewMail();
1187	const int backId = ViewCell::sMailId;
1188	ViewCell::NewMail();
1189	const int frontId = ViewCell::sMailId;
1190	ViewCell::NewMail();
1191	const int frontAndBackId = ViewCell::sMailId;
1192
1193	PolygonContainer::const_iterator it, it_end = polys.end();
1194
1195	for (it = polys.begin(); it != it_end; ++ it)
1196	{
1197	const int classification = (*it)->ClassifyPlane(candidatePlane);
1198
1199	if (sSplitPlaneStrategy & BALANCED_POLYS)
1200	sumBalancedPolys += sBalancedPolysTable[classification];
1201
1202	if (sSplitPlaneStrategy & LEAST_SPLITS)
1203	sumSplits += sLeastPolySplitsTable[classification];
1204
1205	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1206	{
1207	if (classification == Polygon3::COINCIDENT)
1208	sumPolyArea += (*it)->GetArea();
1209	//totalArea += area;
1210	}
1211
1212	if (sSplitPlaneStrategy & BLOCKED_RAYS)
1213	{
1214	const float blockedRays = (float)(*it)->mPiercingRays.size();
1215
1216	if (classification == Polygon3::COINCIDENT)
1217	sumBlockedRays += blockedRays;
1218
1219	totalBlockedRays += blockedRays;
1220	}
1221
1222	// assign view cells to back or front according to classificaion
1223	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1224	{
1225	MeshInstance viewCell = (it)->mParent;
1226
1227	// assure that we only count a view cell
1228	// once for the front and once for the back side of the plane
1229	if (classification == Polygon3::FRONT_SIDE)
1230	{
1231	if ((viewCell->mMailbox != frontId) &&
1232	(viewCell->mMailbox != frontAndBackId))
1233	{
1234	sumBalancedViewCells += 1.0;
1235
1236	if (viewCell->mMailbox != backId)
1237	viewCell->mMailbox = frontId;
1238	else
1239	viewCell->mMailbox = frontAndBackId;
1240
1241	++ totalViewCells;
1242	}
1243	}
1244	else if (classification == Polygon3::BACK_SIDE)
1245	{
1246	if ((viewCell->mMailbox != backId) &&
1247	(viewCell->mMailbox != frontAndBackId))
1248	{
1249	sumBalancedViewCells -= 1.0;
1250
1251	if (viewCell->mMailbox != frontId)
1252	viewCell->mMailbox = backId;
1253	else
1254	viewCell->mMailbox = frontAndBackId;
1255
1256	++ totalViewCells;
1257	}
1258	}
1259	}
1260	}
1261
1262	// all values should be approx. between 0 and 1 so they can be combined
1263	// and scaled with the factors according to their importance
1264	if (sSplitPlaneStrategy & BALANCED_POLYS)
1265	val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
1266
1267	if (sSplitPlaneStrategy & LEAST_SPLITS)
1268	val += sLeastSplitsFactor * sumSplits / (float)polys.size();
1269
1270	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1271	// HACK: polys.size should be total area so scaling is between 0 and 1
1272	val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1273
1274	if (sSplitPlaneStrategy & BLOCKED_RAYS)
1275	if (totalBlockedRays != 0)
1276	val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1277
1278	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1279	if (totalViewCells != 0)
1280	val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / (float)totalViewCells;
1281
1282	return val;
1283	}
1284
1285	bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
1286	{
1287	maxT = 1e6;
1288	minT = 0;
1289
1290	// test with tree bounding box
1291	if (!mBox.GetMinMaxT(ray, &minT, &maxT))
1292	return false;
1293
1294	if (minT < 0) // start ray from origin
1295	minT = 0;
1296
1297	// bound ray or line segment
1298	if ((ray.GetType() == Ray::LOCAL_RAY) &&
1299	!ray.intersections.empty() &&
1300	(ray.intersections[0].mT <= maxT))
1301	{
1302	maxT = ray.intersections[0].mT;
1303	}
1304
1305	return true;
1306	}
1307
1308	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1309	const BoundedRayContainer &rays,
1310	const int pvs,
1311	const float area,
1312	const BspNodeGeometry &cell,
1313	BspTraversalData &frontData,
1314	BspTraversalData &backData) const
1315	{
1316	float val = 0;
1317
1318	float sumBalancedRays = 0;
1319	float sumRaySplits = 0;
1320
1321	int backId = 0;
1322	int frontId = 0;
1323	int frontAndBackId = 0;
1324
1325	frontData.mPvs = 0;
1326	backData.mPvs = 0;
1327	frontData.mArea = 0;
1328	backData.mArea = 0;
1329
1330	// probability that view point lies in child
1331	float pOverall = 0;
1332	float pFront = 0;
1333	float pBack = 0;
1334
1335	if (sSplitPlaneStrategy & PVS)
1336	{
1337	// create three unique ids for pvs heuristics
1338	Intersectable::NewMail(); backId = ViewCell::sMailId;
1339	Intersectable::NewMail(); frontId = ViewCell::sMailId;
1340	Intersectable::NewMail(); frontAndBackId = ViewCell::sMailId;
1341
1342	if (1) // use front and back cell areas to approximate volume
1343	{
1344	// construct child geometry with regard to the candidate split plane
1345	frontData.mCell = cell.ConstructChild(*this, candidatePlane, true);
1346	backData.mCell = cell.ConstructChild(*this, candidatePlane, false);
1347
1348	pFront = frontData.mArea = frontData.mCell->GetArea();
1349	pBack = backData.mArea = backData.mCell->GetArea();
1350
1351	pOverall = area;
1352	}
1353	else
1354	{
1355	pOverall = (float)rays.size();
1356	}
1357	}
1358
1359	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
1360
1361	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1362	{
1363	Ray ray = (rit)->mRay;
1364	const float minT = (*rit)->mMinT;
1365	const float maxT = (*rit)->mMaxT;
1366
1367	const int cf =
1368	ray->ClassifyPlane(candidatePlane, minT, maxT);
1369
1370	if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1371	{
1372	sumBalancedRays += sBalancedRaysTable[cf];
1373	}
1374
1375	if (sSplitPlaneStrategy & BALANCED_RAYS)
1376	{
1377	sumRaySplits += sLeastRaySplitsTable[cf];
1378	}
1379
1380	if (sSplitPlaneStrategy & PVS)
1381	{
1382	if (!ray->intersections.empty())
1383	{
1384	// in case the ray intersects an objcrs
1385	// assure that we only count a object
1386	// once for the front and once for the back side of the plane
1387	AddToPvs(*ray->intersections[0].mObject, frontData.mPvs, backData.mPvs,
1388	cf, frontId, backId, frontAndBackId);
1389	}
1390
1391	// the source object in the origin of the ray
1392	AddToPvs(*ray->sourceObject.mObject, frontData.mPvs, backData.mPvs,
1393	cf, frontId, backId, frontAndBackId);
1394
1395	// use #rays to approximate volume
1396	if (0)
1397	{
1398	if ((cf == Ray::BACK) \|\| (cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
1399	++ pFront;
1400	if ((cf == Ray::FRONT) \|\| (cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
1401	++ pBack;
1402	}
1403	}
1404	}
1405
1406	if ((sSplitPlaneStrategy & LEAST_RAY_SPLITS) && !rays.empty())
1407	val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
1408
1409	if ((sSplitPlaneStrategy & BALANCED_RAYS) && !rays.empty())
1410	val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
1411
1412	if ((sSplitPlaneStrategy & PVS) && area && pvs)
1413	val += sPvsFactor * (frontData.mPvs * pFront + (backData.mPvs * pBack)) /
1414	(pOverall * (float)pvs * 2);
1415
1416	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
1417	<< " frontpvs: " << frontData.mPvs << " pFront: " << pFront
1418	<< " backpvs: " << backData.mPvs << " pBack: " << pBack
1419	<< " val " << val << endl;
1420
1421	return val;
1422	}
1423
1424	void BspTree::AddToPvs(Intersectable &obj,
1425	int &frontPvs,
1426	int &backPvs,
1427	const int cf,
1428	const int frontId,
1429	const int backId,
1430	const int frontAndBackId) const
1431	{
1432	if (cf == Ray::COINCIDENT) //TODO: really belongs to no pvs?
1433	return;
1434
1435	if (cf == Ray::FRONT)
1436	{
1437	if ((obj.mMailbox != frontId) &&
1438	(obj.mMailbox != frontAndBackId))
1439	{
1440	++ frontPvs;
1441
1442	if (obj.mMailbox != backId)
1443	obj.mMailbox = frontId;
1444	else
1445	obj.mMailbox = frontAndBackId;
1446	}
1447	}
1448	else if (cf == Ray::BACK)
1449	{
1450	if ((obj.mMailbox != backId) &&
1451	(obj.mMailbox != frontAndBackId))
1452	{
1453	++ backPvs;
1454
1455	if (obj.mMailbox != frontId)
1456	obj.mMailbox = backId;
1457	else
1458	obj.mMailbox = frontAndBackId;
1459	}
1460	}
1461	// object belongs to both pvs
1462	else if ((cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
1463	{
1464	if (obj.mMailbox != frontAndBackId)
1465	{
1466	if (obj.mMailbox != frontId)
1467	++ frontPvs;
1468	if (obj.mMailbox != backId)
1469	++ backPvs;
1470
1471	obj.mMailbox = frontAndBackId;
1472	}
1473	}
1474	}
1475
1476	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1477	BspTraversalData &data,
1478	BspTraversalData &frontData,
1479	BspTraversalData &backData) const
1480	{
1481	float val = 0;
1482
1483	if (sSplitPlaneStrategy & VERTICAL_AXIS)
1484	{
1485	Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1486	// we put a penalty on the dot product between the "tiny" vertical axis
1487	// and the split plane axis
1488	val += sVerticalSplitsFactor *
1489	fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1490	}
1491
1492	// the following criteria loop over all polygons to find the cost value
1493	if ((sSplitPlaneStrategy & BALANCED_POLYS) \|\|
1494	(sSplitPlaneStrategy & LEAST_SPLITS) \|\|
1495	(sSplitPlaneStrategy & LARGEST_POLY_AREA) \|\|
1496	(sSplitPlaneStrategy & BALANCED_VIEW_CELLS) \|\|
1497	(sSplitPlaneStrategy & BLOCKED_RAYS))
1498	{
1499	val += SplitPlaneCost(candidatePlane, *data.mPolygons);
1500	}
1501
1502	// the following criteria loop over all rays to find the cost value
1503	if ((sSplitPlaneStrategy & BALANCED_RAYS) \|\|
1504	(sSplitPlaneStrategy & LEAST_RAY_SPLITS) \|\|
1505	(sSplitPlaneStrategy & PVS))
1506	{
1507	val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
1508	data.mArea, *data.mCell, frontData, backData);
1509	}
1510
1511	// return linear combination of the sums
1512	return val;
1513	}
1514
1515	void BspTree::ParseEnvironment()
1516	{
1517	//-- parse bsp cell tree construction method
1518	char constructionMethodStr[60];
1519
1520	environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
1521
1522	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1523
1524	if (strcmp(constructionMethodStr, "fromViewCells") == 0)
1525	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
1526	else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
1527	sConstructionMethod = FROM_SCENE_GEOMETRY;
1528	else if (strcmp(constructionMethodStr, "fromRays") == 0)
1529	sConstructionMethod = FROM_RAYS;
1530	else
1531	{
1532	cerr << "Wrong construction method " << constructionMethodStr << endl;
1533	exit(1);
1534	}
1535
1536	Debug << "Construction method: " << constructionMethodStr << endl;
1537
1538	//-- termination criteria for autopartition
1539	environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
1540	environment->GetIntValue("BspTree.Termination.minPvs", sTermMinPvs);
1541	environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
1542	environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
1543
1544	//-- termination criteria for axis aligned split
1545	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
1546	environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
1547	environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",
1548	sTermMaxPolysForAxisAligned);
1549	environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",
1550	sTermMaxRaysForAxisAligned);
1551	environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",
1552	sTermMaxObjectsForAxisAligned);
1553	//-- partition criteria
1554	environment->GetIntValue("BspTree.maxPolyCandidates", sMaxPolyCandidates);
1555	environment->GetIntValue("BspTree.maxRayCandidates", sMaxRayCandidates);
1556	environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
1557	environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
1558
1559	environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
1560	Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
1561
1562	// post processing stuff
1563	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", sMinPvsDif);
1564	environment->GetIntValue("ViewCells.PostProcessing.minPvs", sMinPvs);
1565	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", sMaxPvs);
1566
1567	Debug << "BSP max depth: " << sTermMaxDepth << endl;
1568	Debug << "BSP min PVS: " << sTermMinPvs << endl;
1569	Debug << "BSP max polys: " << sTermMaxPolygons << endl;
1570	Debug << "BSP max rays: " << sTermMaxRays << endl;
1571	Debug << "BSP max polygon candidates: " << sMaxPolyCandidates << endl;
1572	Debug << "BSP max plane candidates: " << sMaxRayCandidates << endl;
1573
1574	Debug << "Split plane strategy: ";
1575	if (sSplitPlaneStrategy & RANDOM_POLYGON)
1576	Debug << "random polygon ";
1577	if (sSplitPlaneStrategy & AXIS_ALIGNED)
1578	Debug << "axis aligned ";
1579	if (sSplitPlaneStrategy & LEAST_SPLITS)
1580	Debug << "least splits ";
1581	if (sSplitPlaneStrategy & BALANCED_POLYS)
1582	Debug << "balanced polygons ";
1583	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1584	Debug << "balanced view cells ";
1585	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
1586	Debug << "largest polygon area ";
1587	if (sSplitPlaneStrategy & VERTICAL_AXIS)
1588	Debug << "vertical axis ";
1589	if (sSplitPlaneStrategy & BLOCKED_RAYS)
1590	Debug << "blocked rays ";
1591	if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
1592	Debug << "least ray splits ";
1593	if (sSplitPlaneStrategy & BALANCED_RAYS)
1594	Debug << "balanced rays ";
1595	if (sSplitPlaneStrategy & PVS)
1596	Debug << "pvs";
1597	Debug << endl;
1598	}
1599
1600	void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1601	{
1602	stack<BspNode *> nodeStack;
1603	nodeStack.push(mRoot);
1604
1605	while (!nodeStack.empty())
1606	{
1607	BspNode *node = nodeStack.top();
1608
1609	nodeStack.pop();
1610
1611	if (node->IsLeaf())
1612	{
1613	BspLeaf leaf = (BspLeaf )node;
1614	leaves.push_back(leaf);
1615	}
1616	else
1617	{
1618	BspInterior interior = dynamic_cast<BspInterior >(node);
1619
1620	nodeStack.push(interior->GetBack());
1621	nodeStack.push(interior->GetFront());
1622	}
1623	}
1624	}
1625
1626	AxisAlignedBox3 BspTree::GetBoundingBox() const
1627	{
1628	return mBox;
1629	}
1630
1631	BspNode *BspTree::GetRoot() const
1632	{
1633	return mRoot;
1634	}
1635
1636	void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1637	{
1638	// the node became a leaf -> evaluate stats for leafs
1639	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
1640
1641	if (data.mDepth >= sTermMaxDepth)
1642	++ mStat.maxDepthNodes;
1643
1644	// store maximal and minimal depth
1645	if (data.mDepth > mStat.maxDepth)
1646	mStat.maxDepth = data.mDepth;
1647
1648	if (data.mDepth < mStat.minDepth)
1649	mStat.minDepth = data.mDepth;
1650
1651	// store minimal and maximal pvs
1652	/*if (data.mPvs > mStat.pvs)
1653	mStat.pvs = data.mPvs;
1654
1655	if (data.mPvs < mStat.pvs)
1656	mStat.pvs = data.mPvs;*/
1657
1658	// accumulate depth to compute average
1659	mStat.accumDepth += data.mDepth;
1660
1661	//#ifdef _DEBUG
1662	Debug << "BSP stats: "
1663	<< "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
1664	<< "PVS: " << data.mPvs << " (max: " << sTermMinPvs << "), "
1665	<< "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
1666	<< "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << "), "
1667	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << endl;
1668	//#endif
1669	}
1670
1671	int BspTree::CastRay(Ray &ray)
1672	{
1673	int hits = 0;
1674
1675	stack<BspRayTraversalData> tStack;
1676
1677	float maxt, mint;
1678
1679	if (!BoundRay(ray, mint, maxt))
1680	return 0;
1681
1682	Intersectable::NewMail();
1683
1684	Vector3 entp = ray.Extrap(mint);
1685	Vector3 extp = ray.Extrap(maxt);
1686
1687	BspNode *node = mRoot;
1688	BspNode *farChild = NULL;
1689
1690	while (1)
1691	{
1692	if (!node->IsLeaf())
1693	{
1694	BspInterior in = (BspInterior ) node;
1695
1696	Plane3 *splitPlane = in->GetPlane();
1697
1698	int entSide = splitPlane->Side(entp);
1699	int extSide = splitPlane->Side(extp);
1700
1701	Vector3 intersection;
1702
1703	if (entSide < 0)
1704	{
1705	node = in->GetBack();
1706
1707	if(extSide <= 0) // plane does not split ray => no far child
1708	continue;
1709
1710	farChild = in->GetFront(); // plane splits ray
1711
1712	} else if (entSide > 0)
1713	{
1714	node = in->GetFront();
1715
1716	if (extSide >= 0) // plane does not split ray => no far child
1717	continue;
1718
1719	farChild = in->GetBack(); // plane splits ray
1720	}
1721	else // ray and plane are coincident
1722	// WHAT TO DO IN THIS CASE ?
1723	{
1724	break;
1725	//node = in->GetFront();
1726	//continue;
1727	}
1728
1729	// push data for far child
1730	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1731
1732	// find intersection of ray segment with plane
1733	float t;
1734	extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
1735	maxt *= t;
1736
1737	} else // reached leaf => intersection with view cell
1738	{
1739	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1740
1741	if (!leaf->mViewCell->Mailed())
1742	{
1743	ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1744	leaf->mViewCell->Mail();
1745	++ hits;
1746	}
1747
1748	//-- fetch the next far child from the stack
1749	if (tStack.empty())
1750	break;
1751
1752	entp = extp;
1753	mint = maxt; // NOTE: need this?
1754
1755	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1756	break;
1757
1758	BspRayTraversalData &s = tStack.top();
1759
1760	node = s.mNode;
1761	extp = s.mExitPoint;
1762	maxt = s.mMaxT;
1763
1764	tStack.pop();
1765	}
1766	}
1767
1768	return hits;
1769	}
1770
1771	bool BspTree::Export(const string filename)
1772	{
1773	Exporter *exporter = Exporter::GetExporter(filename);
1774
1775	if (exporter)
1776	{
1777	exporter->ExportBspTree(*this);
1778	return true;
1779	}
1780
1781	return false;
1782	}
1783
1784	void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
1785	{
1786	stack<BspNode *> nodeStack;
1787	nodeStack.push(mRoot);
1788
1789	ViewCell::NewMail();
1790
1791	while (!nodeStack.empty())
1792	{
1793	BspNode *node = nodeStack.top();
1794	nodeStack.pop();
1795
1796	if (node->IsLeaf())
1797	{
1798	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
1799
1800	if (!viewCell->Mailed())
1801	{
1802	viewCell->Mail();
1803	viewCells.push_back(viewCell);
1804	}
1805	}
1806	else
1807	{
1808	BspInterior interior = dynamic_cast<BspInterior >(node);
1809
1810	nodeStack.push(interior->mFront);
1811	nodeStack.push(interior->mBack);
1812	}
1813	}
1814	}
1815
1816	void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
1817	{
1818	stat.Reset();
1819
1820	stack<BspNode *> nodeStack;
1821	nodeStack.push(mRoot);
1822
1823	ViewCell::NewMail();
1824
1825	// exclude root cell
1826	mRootCell->Mail();
1827
1828	while (!nodeStack.empty())
1829	{
1830	BspNode *node = nodeStack.top();
1831	nodeStack.pop();
1832
1833	if (node->IsLeaf())
1834	{
1835	++ stat.bspLeaves;
1836
1837	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
1838
1839	if (!viewCell->Mailed())
1840	{
1841	viewCell->Mail();
1842
1843	++ stat.viewCells;
1844	int pvsSize = viewCell->GetPvs().GetSize();
1845
1846	stat.pvs += pvsSize;
1847
1848	if (pvsSize < 2)
1849	++ stat.emptyPvs;
1850
1851	if (pvsSize > stat.maxPvs)
1852	stat.maxPvs = pvsSize;
1853
1854	if (pvsSize < stat.minPvs)
1855	stat.minPvs = pvsSize;
1856
1857	if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
1858	stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();
1859	}
1860	}
1861	else
1862	{
1863	BspInterior interior = dynamic_cast<BspInterior >(node);
1864
1865	nodeStack.push(interior->mFront);
1866	nodeStack.push(interior->mBack);
1867	}
1868	}
1869	}
1870
1871	bool BspTree::MergeViewCells(BspLeaf front, BspLeaf back) const
1872	{
1873	BspViewCell *viewCell =
1874	dynamic_cast<BspViewCell >(ViewCell::Merge(front->mViewCell, *back->mViewCell));
1875
1876	if (!viewCell)
1877	return false;
1878
1879	// change view cells of all leaves associated with the
1880	// previous view cells
1881
1882	BspViewCell *fVc = front->mViewCell;
1883	BspViewCell *bVc = back->mViewCell;
1884
1885	vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
1886	vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
1887
1888	vector<BspLeaf *>::const_iterator it;
1889
1890	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
1891	{
1892	(*it)->SetViewCell(viewCell);
1893	viewCell->mBspLeaves.push_back(*it);
1894	}
1895	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
1896	{
1897	(*it)->SetViewCell(viewCell);
1898	viewCell->mBspLeaves.push_back(*it);
1899	}
1900
1901	DEL_PTR(fVc);
1902	DEL_PTR(bVc);
1903
1904	return true;
1905	}
1906
1907	bool BspTree::ShouldMerge(BspLeaf front, BspLeaf back) const
1908	{
1909	ViewCell *fvc = front->mViewCell;
1910	ViewCell *bvc = back->mViewCell;
1911
1912	if ((fvc == mRootCell) \|\| (bvc == mRootCell) \|\| (fvc == bvc))
1913	return false;
1914
1915	int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
1916
1917	if (fvc->GetPvs().GetSize() + fdiff < sMaxPvs)
1918	{
1919	if ((fvc->GetPvs().GetSize() < sMinPvs) \|\|
1920	(bvc->GetPvs().GetSize() < sMinPvs) \|\|
1921	((fdiff < sMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < sMinPvsDif)))
1922	{
1923	return true;
1924	}
1925	}
1926
1927	return false;
1928	}
1929
1930	void BspTree::SetGenerateViewCells(int generateViewCells)
1931	{
1932	mGenerateViewCells = generateViewCells;
1933	}
1934
1935	BspTreeStatistics &BspTree::GetStat()
1936	{
1937	return mStat;
1938	}
1939
1940	int BspTree::SplitRays(const Plane3 &plane,
1941	BoundedRayContainer &rays,
1942	BoundedRayContainer &frontRays,
1943	BoundedRayContainer &backRays)
1944	{
1945	int splits = 0;
1946
1947	while (!rays.empty())
1948	{
1949	BoundedRay *bRay = rays.back();
1950	Ray *ray = bRay->mRay;
1951	rays.pop_back();
1952
1953	const int cf =
1954	ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
1955
1956	ray->SetId(cf);
1957
1958	switch (cf)
1959	{
1960	case Ray::COINCIDENT:
1961	//frontRays.push_back(bRay);
1962	DEL_PTR(bRay);
1963	break;
1964	case Ray::BACK:
1965	backRays.push_back(bRay);
1966	break;
1967	case Ray::FRONT:
1968	frontRays.push_back(bRay);
1969	break;
1970	case Ray::FRONT_BACK:
1971	{
1972	// find intersection of ray segment with plane
1973	const Vector3 extp = ray->Extrap(bRay->mMaxT);
1974	const float t = plane.FindT(ray->GetLoc(), extp);
1975
1976	const float newT = t * bRay->mMaxT;
1977
1978	frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1979	backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1980
1981	DEL_PTR(bRay);
1982
1983	++ splits;
1984	}
1985	break;
1986	case Ray::BACK_FRONT:
1987	{
1988	// find intersection of ray segment with plane
1989	const Vector3 extp = ray->Extrap(bRay->mMaxT);
1990	const float t = plane.FindT(ray->GetLoc(), extp);
1991	const float newT = t * bRay->mMaxT;
1992
1993	backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
1994	frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
1995
1996	DEL_PTR(bRay);
1997
1998	++ splits;
1999	}
2000	break;
2001	default:
2002	Debug << "Should not come here" << endl;
2003	break;
2004	}
2005	}
2006
2007	return splits;
2008	}
2009
2010	void BspTree::ExtractSplitPlanes(BspNode *n,
2011	vector<Plane3> &planes,
2012	vector<bool> &sides) const
2013	{
2014	BspNode *lastNode;
2015	do
2016	{
2017	lastNode = n;
2018
2019	// want to get planes defining geometry of this node => don't take
2020	// split plane of node itself
2021	n = n->GetParent();
2022
2023	if (n)
2024	{
2025	BspInterior interior = dynamic_cast<BspInterior >(n);
2026
2027	planes.push_back(* dynamic_cast<BspInterior *>(interior)->GetPlane());
2028	sides.push_back(interior->mFront == lastNode);
2029	}
2030	}
2031	while (n);
2032	}
2033
2034	void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
2035	{
2036	stack<BspNode *> tStack;
2037
2038	vector<Plane3> planes;
2039	vector<bool> sides;
2040
2041	ExtractSplitPlanes(n, cell.mPlanes, cell.mSides);
2042
2043	PolygonContainer candidatePolys;
2044
2045	// bounded planes are added to the polygons
2046	for (int i = 0; i < (int)cell.mPlanes.size(); ++ i)
2047	{
2048	candidatePolys.push_back(GetBoundingBox().CrossSection(cell.mPlanes[i]));
2049	}
2050
2051	// add faces of bounding box (also could be faces of the cell)
2052	for (int i = 0; i < 6; ++ i)
2053	{
2054	VertexContainer vertices;
2055
2056	for (int j = 0; j < 4; ++ j)
2057	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2058
2059	candidatePolys.push_back(new Polygon3(vertices));
2060	}
2061
2062	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2063	{
2064	bool inside = true;
2065
2066	// polygon is split by all other planes
2067	for (int j = 0; (j < cell.mPlanes.size()) && inside; ++ j)
2068	{
2069	if (i == j) // same plane
2070	continue;
2071
2072	VertexContainer splitPts;
2073	Polygon3 frontPoly, backPoly;
2074
2075	const int cf = candidatePolys[i]->ClassifyPlane(cell.mPlanes[j]);
2076
2077	switch (cf)
2078	{
2079	case Polygon3::SPLIT:
2080	frontPoly = new Polygon3();
2081	backPoly = new Polygon3();
2082
2083	candidatePolys[i]->Split(cell.mPlanes[j], *frontPoly,
2084	*backPoly, splitPts);
2085	DEL_PTR(candidatePolys[i]);
2086
2087	if(sides[j] == true)
2088	{
2089	candidatePolys[i] = frontPoly;
2090	DEL_PTR(backPoly);
2091	}
2092	else
2093	{
2094	candidatePolys[i] = backPoly;
2095	DEL_PTR(frontPoly);
2096	}
2097
2098	break;
2099
2100	case Polygon3::BACK_SIDE:
2101	if (cell.mSides[j])
2102	inside = false;
2103	break;
2104	case Polygon3::FRONT_SIDE:
2105	if (!cell.mSides[j])
2106	inside = false;
2107	break;
2108	case Polygon3::COINCIDENT:
2109	break;
2110	default:
2111	break;
2112	}
2113	}
2114
2115	if (inside)
2116	cell.mPolys.push_back(candidatePolys[i]);
2117	else
2118	DEL_PTR(candidatePolys[i]);
2119	}
2120	}
2121
2122	void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
2123	{
2124	stack<BspNode *> tStack;
2125
2126	vector<Plane3> planes;
2127	vector<bool> sides;
2128
2129	ExtractSplitPlanes(n, planes, sides);
2130
2131	PolygonContainer candidatePolys;
2132
2133	// bounded planes are added to the polygons
2134	for (int i = 0; i < (int)planes.size(); ++ i)
2135	{
2136	candidatePolys.push_back(GetBoundingBox().CrossSection(planes[i]));
2137	}
2138
2139	// add faces of bounding box (also could be faces of the cell)
2140	for (int i = 0; i < 6; ++ i)
2141	{
2142	VertexContainer vertices;
2143
2144	for (int j = 0; j < 4; ++ j)
2145	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2146
2147	candidatePolys.push_back(new Polygon3(vertices));
2148	}
2149
2150	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2151	{
2152	bool inside = true;
2153
2154	// polygon is split by all other planes
2155	for (int j = 0; (j < planes.size()) && inside; ++ j)
2156	{
2157	if (i == j) // same plane
2158	continue;
2159
2160	VertexContainer splitPts;
2161	Polygon3 frontPoly, backPoly;
2162
2163	const int cf = candidatePolys[i]->ClassifyPlane(planes[j]);
2164
2165	switch (cf)
2166	{
2167	case Polygon3::SPLIT:
2168	frontPoly = new Polygon3();
2169	backPoly = new Polygon3();
2170
2171	candidatePolys[i]->Split(planes[j], *frontPoly,
2172	*backPoly, splitPts);
2173	DEL_PTR(candidatePolys[i]);
2174
2175	if(sides[j] == true)
2176	{
2177	candidatePolys[i] = frontPoly;
2178	DEL_PTR(backPoly);
2179	}
2180	else
2181	{
2182	candidatePolys[i] = backPoly;
2183	DEL_PTR(frontPoly);
2184	}
2185
2186	break;
2187
2188	case Polygon3::BACK_SIDE:
2189	if (sides[j])
2190	inside = false;
2191	break;
2192	case Polygon3::FRONT_SIDE:
2193	if (!sides[j])
2194	inside = false;
2195	break;
2196	case Polygon3::COINCIDENT:
2197	break;
2198	default:
2199	break;
2200	}
2201	}
2202
2203	if (inside)
2204	cell.push_back(candidatePolys[i]);
2205	else
2206	DEL_PTR(candidatePolys[i]);
2207	}
2208	}
2209
2210	void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
2211	{
2212	vector<BspLeaf *> leaves = vc->mBspLeaves;
2213
2214	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2215
2216	for (it = leaves.begin(); it != it_end; ++ it)
2217	ConstructGeometry(*it, cell);
2218	}
2219
2220	int BspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
2221	const bool onlyUnmailed) const
2222	{
2223	PolygonContainer cell;
2224
2225	ConstructGeometry(n, cell);
2226
2227	stack<BspNode *> nodeStack;
2228	nodeStack.push(mRoot);
2229
2230	// planes needed to verify that we found neighbor leaf.
2231	vector<Plane3> planes;
2232	vector<bool> sides;
2233
2234	ExtractSplitPlanes(n, planes, sides);
2235
2236	while (!nodeStack.empty())
2237	{
2238	BspNode *node = nodeStack.top();
2239	nodeStack.pop();
2240
2241	if (node->IsLeaf())
2242	{
2243	if (node != n && (!onlyUnmailed \|\| !node->Mailed()))
2244	{
2245	// test all planes of current node on neighbour
2246	PolygonContainer neighborCandidate;
2247	ConstructGeometry(node, neighborCandidate);
2248
2249	bool isAdjacent = true;
2250	for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
2251	{
2252	const int cf =
2253	Polygon3::ClassifyPlane(neighborCandidate, planes[i]);
2254
2255	if ((cf == Polygon3::BACK_SIDE) && sides[i])
2256	isAdjacent = false;
2257	else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
2258	isAdjacent = false;
2259	}
2260
2261	if (isAdjacent)
2262	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2263
2264	CLEAR_CONTAINER(neighborCandidate);
2265	}
2266	}
2267	else
2268	{
2269	BspInterior interior = dynamic_cast<BspInterior >(node);
2270
2271	const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
2272
2273	if (cf == Polygon3::FRONT_SIDE)
2274	nodeStack.push(interior->mFront);
2275	else
2276	if (cf == Polygon3::BACK_SIDE)
2277	nodeStack.push(interior->mBack);
2278	else
2279	{
2280	// random decision
2281	nodeStack.push(interior->mBack);
2282	nodeStack.push(interior->mFront);
2283	}
2284	}
2285	}
2286
2287	CLEAR_CONTAINER(cell);
2288	return (int)neighbors.size();
2289	}
2290
2291	BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2292	{
2293	stack<BspNode *> nodeStack;
2294	nodeStack.push(mRoot);
2295
2296	int mask = rand();
2297
2298	while (!nodeStack.empty())
2299	{
2300	BspNode *node = nodeStack.top();
2301	nodeStack.pop();
2302
2303	if (node->IsLeaf())
2304	{
2305	return dynamic_cast<BspLeaf *>(node);
2306	}
2307	else
2308	{
2309	BspInterior interior = dynamic_cast<BspInterior >(node);
2310
2311	BspNode *next;
2312
2313	PolygonContainer cell;
2314
2315	// todo: not very efficient: constructs full cell everytime
2316	ConstructGeometry(interior, cell);
2317
2318	const int cf = Polygon3::ClassifyPlane(cell, halfspace);
2319
2320	if (cf == Polygon3::BACK_SIDE)
2321	next = interior->mFront;
2322	else
2323	if (cf == Polygon3::FRONT_SIDE)
2324	next = interior->mFront;
2325	else
2326	{
2327	// random decision
2328	if (mask & 1)
2329	next = interior->mBack;
2330	else
2331	next = interior->mFront;
2332	mask = mask >> 1;
2333	}
2334
2335	nodeStack.push(next);
2336	}
2337	}
2338
2339	return NULL;
2340	}
2341
2342	BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2343	{
2344	stack<BspNode *> nodeStack;
2345
2346	nodeStack.push(mRoot);
2347
2348	int mask = rand();
2349
2350	while (!nodeStack.empty())
2351	{
2352	BspNode *node = nodeStack.top();
2353	nodeStack.pop();
2354
2355	if (node->IsLeaf())
2356	{
2357	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2358	return dynamic_cast<BspLeaf *>(node);
2359	}
2360	else
2361	{
2362	BspInterior interior = dynamic_cast<BspInterior >(node);
2363
2364	// random decision
2365	if (mask & 1)
2366	nodeStack.push(interior->mBack);
2367	else
2368	nodeStack.push(interior->mFront);
2369
2370	mask = mask >> 1;
2371	}
2372	}
2373
2374	return NULL;
2375	}
2376
2377	int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2378	{
2379	int pvsSize = 0;
2380
2381	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2382
2383	Intersectable::NewMail();
2384
2385	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2386	{
2387	Ray ray = (rit)->mRay;
2388
2389	if (!ray->intersections.empty())
2390	{
2391	if (!ray->intersections[0].mObject->Mailed())
2392	{
2393	ray->intersections[0].mObject->Mail();
2394	++ pvsSize;
2395	}
2396	}
2397	if (!ray->sourceObject.mObject->Mailed())
2398	{
2399	ray->sourceObject.mObject->Mail();
2400	++ pvsSize;
2401	}
2402	}
2403
2404	return pvsSize;
2405	}
2406
2407	/*************************************************************
2408	* BspNodeGeometry Implementation *
2409	*************************************************************/
2410
2411	BspNodeGeometry::BspNodeGeometry(const PolygonContainer &polys,
2412	const vector<Plane3> &planes,
2413	const vector<bool> &sides):
2414	mPolys(polys), mPlanes(planes), mSides(sides)
2415	{}
2416
2417	BspNodeGeometry::BspNodeGeometry(const vector<Plane3> &planes,
2418	const vector<bool> &sides):
2419	mPlanes(planes), mSides(sides)
2420	{}
2421
2422	BspNodeGeometry::~BspNodeGeometry()
2423	{
2424	CLEAR_CONTAINER(mPolys);
2425	}
2426
2427	float BspNodeGeometry::GetArea() const
2428	{
2429	return Polygon3::GetArea(mPolys);
2430	}
2431
2432	BspNodeGeometry *BspNodeGeometry::ConstructChild(const BspTree &tree,
2433	const Plane3 &splitPlane,
2434	const bool side) const
2435	{
2436	BspNodeGeometry *childCell = new BspNodeGeometry(mPlanes, mSides);
2437
2438	// get cross section of new polygon
2439	Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(splitPlane);
2440
2441	// polygon is split by all other planes
2442	for (int i = 0; (i < (int)mPlanes.size()) && planePoly; ++ i)
2443	{
2444	const int cf = planePoly->ClassifyPlane(mPlanes[i]);
2445
2446	// split new polygon with all previous planes
2447	switch (cf)
2448	{
2449	case Polygon3::SPLIT:
2450	{
2451	VertexContainer splitPts;
2452
2453	Polygon3 *frontPoly = new Polygon3();
2454	Polygon3 *backPoly = new Polygon3();
2455
2456	planePoly->Split(mPlanes[i], frontPoly, backPoly, splitPts);
2457	DEL_PTR(planePoly);
2458
2459	if(mSides[i] == true)
2460	{
2461	planePoly = frontPoly;
2462	DEL_PTR(backPoly);
2463	}
2464	else
2465	{
2466	planePoly = backPoly;
2467	DEL_PTR(frontPoly);
2468	}
2469
2470	if (!planePoly->Valid())
2471	DEL_PTR(planePoly);
2472	}
2473	break;
2474	case Polygon3::BACK_SIDE:
2475	if (mSides[i])
2476	DEL_PTR(planePoly);
2477	break;
2478	case Polygon3::FRONT_SIDE:
2479	if (!mSides[i])
2480	DEL_PTR(planePoly);
2481	break;
2482	case Polygon3::COINCIDENT:
2483	break;
2484	default:
2485	break;
2486	}
2487	}
2488
2489	if (!planePoly)
2490	{
2491	//geometry is not changed at all, hence just copy polygons
2492	PolygonContainer::const_iterator it, it_end = mPolys.end();
2493
2494	for (it = mPolys.begin(); it != it_end; ++ it)
2495	childCell->mPolys.push_back(new Polygon3((*it)->mVertices));
2496
2497	return childCell;
2498	}
2499
2500	//-- plane poly splits all other cell polygons
2501	for (int i = 0; i < (int)mPolys.size(); ++ i)
2502	{
2503	const int cf = mPolys[i]->ClassifyPlane(splitPlane);
2504
2505	// split new polygon with all previous planes
2506	switch (cf)
2507	{
2508	case Polygon3::SPLIT:
2509	{
2510	Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
2511
2512	Polygon3 *frontPoly = new Polygon3();
2513	Polygon3 *backPoly = new Polygon3();
2514
2515	VertexContainer splitPts;
2516
2517	poly->Split(splitPlane, frontPoly, backPoly, splitPts);
2518
2519	DEL_PTR(poly);
2520
2521	if (side == true)
2522	{
2523	poly = frontPoly;
2524	DEL_PTR(backPoly);
2525	}
2526	else
2527	{
2528	poly = backPoly;
2529	DEL_PTR(frontPoly);
2530	}
2531	if (!poly->Valid())
2532	DEL_PTR(poly);
2533	else
2534	childCell->mPolys.push_back(poly);
2535	}
2536
2537	break;
2538	case Polygon3::BACK_SIDE:
2539	if (!side)
2540	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2541	break;
2542	case Polygon3::FRONT_SIDE:
2543	if (side)
2544	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2545	break;
2546	case Polygon3::COINCIDENT:
2547	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2548	break;
2549	default:
2550
2551	break;
2552	}
2553	}
2554
2555	//-- finally add the new polygon
2556	childCell->mPolys.push_back(planePoly);
2557	childCell->mPlanes.push_back(splitPlane);
2558	childCell->mSides.push_back(side);
2559
2560	Debug << "returning new geometry " << mPolys.size() << " CHILD: " << childCell->mPolys.size() << endl;
2561
2562	Debug << "old area " << this->GetArea() << " new: " << childCell->GetArea() << endl;
2563	return childCell;
2564	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: