Context Navigation

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

Revision 409, 62.6 KB checked in by mattausch, 19 years ago (diff)
worked on kd view space partitioning structure worked on render simulation

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

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

Download in other formats: