Context Navigation

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

Revision 589, 74.1 KB checked in by bittner, 18 years ago (diff)
unix2dos on all sources

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 "Triangle3.h"
11	#include "Tetrahedron3.h"
12	#include "ViewCellsManager.h"
13	#include "Exporter.h"
14	#include "Plane3.h"
15	#include <stack>
16
17	//-- static members
18
19	int BspNode::sMailId = 1;
20
21	/** Evaluates split plane classification with respect to the plane's
22	contribution for a minimum number splits in the tree.
23	*/
24	const float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
25	/** Evaluates split plane classification with respect to the plane's
26	contribution for a balanced tree.
27	*/
28	const float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
29
30	/** Evaluates split plane classification with respect to the plane's
31	contribution for a minimum number of ray splits.
32	*/
33	const float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
34	/** Evaluates split plane classification with respect to the plane's
35	contribution for balanced rays.
36	*/
37	const float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
38
39	int BspTree::sFrontId = 0;
40	int BspTree::sBackId = 0;
41	int BspTree::sFrontAndBackId = 0;
42
43
44	/****************************************************************/
45	/* class BspNode implementation */
46	/****************************************************************/
47
48
49	BspNode::BspNode():
50	mParent(NULL), mTreeValid(true)
51	{}
52
53	BspNode::BspNode(BspInterior *parent):
54	mParent(parent), mTreeValid(true)
55	{}
56
57
58	bool BspNode::IsRoot() const
59	{
60	return mParent == NULL;
61	}
62
63
64	BspInterior *BspNode::GetParent()
65	{
66	return mParent;
67	}
68
69
70	void BspNode::SetParent(BspInterior *parent)
71	{
72	mParent = parent;
73	}
74
75
76	bool BspNode::IsSibling(BspNode *n) const
77	{
78	return ((this != n) && mParent &&
79	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
80	}
81
82
83	int BspNode::GetDepth() const
84	{
85	int depth = 0;
86	BspNode *p = mParent;
87
88	while (p)
89	{
90	p = p->mParent;
91	++ depth;
92	}
93
94	return depth;
95	}
96
97
98	bool BspNode::TreeValid() const
99	{
100	return mTreeValid;
101	}
102
103
104	void BspNode::SetTreeValid(const bool v)
105	{
106	mTreeValid = v;
107	}
108
109
110	/****************************************************************/
111	/* class BspInterior implementation */
112	/****************************************************************/
113
114
115	BspInterior::BspInterior(const Plane3 &plane):
116	mPlane(plane), mFront(NULL), mBack(NULL)
117	{}
118
119	BspInterior::~BspInterior()
120	{
121	DEL_PTR(mFront);
122	DEL_PTR(mBack);
123	}
124
125	bool BspInterior::IsLeaf() const
126	{
127	return false;
128	}
129
130	BspNode *BspInterior::GetBack()
131	{
132	return mBack;
133	}
134
135	BspNode *BspInterior::GetFront()
136	{
137	return mFront;
138	}
139
140	Plane3 BspInterior::GetPlane() const
141	{
142	return mPlane;
143	}
144
145	void BspInterior::ReplaceChildLink(BspNode oldChild, BspNode newChild)
146	{
147	if (mBack == oldChild)
148	mBack = newChild;
149	else
150	mFront = newChild;
151	}
152
153	void BspInterior::SetupChildLinks(BspNode b, BspNode f)
154	{
155	mBack = b;
156	mFront = f;
157	}
158
159	/****************************************************************/
160	/* class BspLeaf implementation */
161	/****************************************************************/
162
163
164	BspLeaf::BspLeaf(): mViewCell(NULL), mPvs(NULL)
165	{
166	}
167
168
169	BspLeaf::~BspLeaf()
170	{
171	DEL_PTR(mPvs);
172	}
173
174
175	BspLeaf::BspLeaf(BspViewCell *viewCell):
176	mViewCell(viewCell)
177	{
178	}
179
180
181	BspLeaf::BspLeaf(BspInterior *parent):
182	BspNode(parent), mViewCell(NULL), mPvs(NULL)
183	{}
184
185
186
187	BspLeaf::BspLeaf(BspInterior parent, BspViewCell viewCell):
188	BspNode(parent), mViewCell(viewCell), mPvs(NULL)
189	{
190	}
191
192	BspViewCell *BspLeaf::GetViewCell() const
193	{
194	return mViewCell;
195	}
196
197	void BspLeaf::SetViewCell(BspViewCell *viewCell)
198	{
199	mViewCell = viewCell;
200	}
201
202
203	bool BspLeaf::IsLeaf() const
204	{
205	return true;
206	}
207
208
209	/*********************************************************************/
210	/* class BspTree implementation */
211	/*********************************************************************/
212
213	BspTree::BspTree():
214	mRoot(NULL),
215	mUseAreaForPvs(false),
216	mGenerateViewCells(true)
217	{
218	Randomize(); // initialise random generator for heuristics
219
220	// the view cell corresponding to unbounded space
221	mRootCell = new BspViewCell();
222
223	//-- termination criteria for autopartition
224	environment->GetIntValue("BspTree.Termination.maxDepth", mTermMaxDepth);
225	environment->GetIntValue("BspTree.Termination.minPvs", mTermMinPvs);
226	environment->GetIntValue("BspTree.Termination.minPolygons", mTermMinPolys);
227	environment->GetIntValue("BspTree.Termination.minRays", mTermMinRays);
228	environment->GetFloatValue("BspTree.Termination.minProbability", mTermMinProbability);
229	environment->GetFloatValue("BspTree.Termination.maxRayContribution", mTermMaxRayContribution);
230	environment->GetFloatValue("BspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
231
232	//-- factors for bsp tree split plane heuristics
233	environment->GetFloatValue("BspTree.Factor.verticalSplits", mVerticalSplitsFactor);
234	environment->GetFloatValue("BspTree.Factor.largestPolyArea", mLargestPolyAreaFactor);
235	environment->GetFloatValue("BspTree.Factor.blockedRays", mBlockedRaysFactor);
236	environment->GetFloatValue("BspTree.Factor.leastRaySplits", mLeastRaySplitsFactor);
237	environment->GetFloatValue("BspTree.Factor.balancedRays", mBalancedRaysFactor);
238	environment->GetFloatValue("BspTree.Factor.pvs", mPvsFactor);
239	environment->GetFloatValue("BspTree.Factor.leastSplits" , mLeastSplitsFactor);
240	environment->GetFloatValue("BspTree.Factor.balancedPolys", mBalancedPolysFactor);
241	environment->GetFloatValue("BspTree.Factor.balancedViewCells", mBalancedViewCellsFactor);
242	environment->GetFloatValue("BspTree.Termination.ct_div_ci", mCtDivCi);
243
244	//-- termination criteria for axis aligned split
245	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
246	environment->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio);
247	environment->GetIntValue("BspTree.Termination.AxisAligned.minPolys",
248	mTermMinPolysForAxisAligned);
249	environment->GetIntValue("BspTree.Termination.AxisAligned.minRays",
250	mTermMinRaysForAxisAligned);
251	environment->GetIntValue("BspTree.Termination.AxisAligned.minObjects",
252	mTermMinObjectsForAxisAligned);
253	//-- partition criteria
254	environment->GetIntValue("BspTree.maxPolyCandidates", mMaxPolyCandidates);
255	environment->GetIntValue("BspTree.maxRayCandidates", mMaxRayCandidates);
256	environment->GetIntValue("BspTree.splitPlaneStrategy", mSplitPlaneStrategy);
257	environment->GetFloatValue("BspTree.AxisAligned.splitBorder", mSplitBorder);
258	environment->GetIntValue("BspTree.maxTests", mMaxTests);
259	environment->GetIntValue("BspTree.Termination.maxViewCells", mMaxViewCells);
260
261	environment->GetFloatValue("BspTree.Construction.epsilon", mEpsilon);
262
263	Debug << "BSP max depth: " << mTermMaxDepth << endl;
264	Debug << "BSP min PVS: " << mTermMinPvs << endl;
265	Debug << "BSP min probability: " << mTermMinProbability << endl;
266	Debug << "BSP max polys: " << mTermMinPolys << endl;
267	Debug << "BSP max rays: " << mTermMinRays << endl;
268	Debug << "BSP max polygon candidates: " << mMaxPolyCandidates << endl;
269	Debug << "BSP max plane candidates: " << mMaxRayCandidates << endl;
270
271	Debug << "Split plane strategy: ";
272	if (mSplitPlaneStrategy & RANDOM_POLYGON)
273	Debug << "random polygon ";
274	if (mSplitPlaneStrategy & AXIS_ALIGNED)
275	Debug << "axis aligned ";
276	if (mSplitPlaneStrategy & LEAST_SPLITS)
277	Debug << "least splits ";
278	if (mSplitPlaneStrategy & BALANCED_POLYS)
279	Debug << "balanced polygons ";
280	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
281	Debug << "balanced view cells ";
282	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
283	Debug << "largest polygon area ";
284	if (mSplitPlaneStrategy & VERTICAL_AXIS)
285	Debug << "vertical axis ";
286	if (mSplitPlaneStrategy & BLOCKED_RAYS)
287	Debug << "blocked rays ";
288	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
289	Debug << "least ray splits ";
290	if (mSplitPlaneStrategy & BALANCED_RAYS)
291	Debug << "balanced rays ";
292	if (mSplitPlaneStrategy & PVS)
293	Debug << "pvs";
294
295	Debug << endl;
296	}
297
298
299	const BspTreeStatistics &BspTree::GetStatistics() const
300	{
301	return mStat;
302	}
303
304
305	int BspTree::SplitPolygons(const Plane3 &plane,
306	PolygonContainer &polys,
307	PolygonContainer &frontPolys,
308	PolygonContainer &backPolys,
309	PolygonContainer &coincident) const
310	{
311	int splits = 0;
312
313	#ifdef _Debug
314	Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
315	#endif
316	PolygonContainer::const_iterator it, it_end = polys.end();
317
318	for (it = polys.begin(); it != polys.end(); ++ it)
319	{
320	Polygon3 poly = it;
321
322	//-- classify polygon
323	const int cf = poly->ClassifyPlane(plane, mEpsilon);
324
325	switch (cf)
326	{
327	case Polygon3::COINCIDENT:
328	coincident.push_back(poly);
329	break;
330	case Polygon3::FRONT_SIDE:
331	frontPolys.push_back(poly);
332	break;
333	case Polygon3::BACK_SIDE:
334	backPolys.push_back(poly);
335	break;
336	case Polygon3::SPLIT:
337	{
338	Polygon3 *front_piece = new Polygon3(poly->mParent);
339	Polygon3 *back_piece = new Polygon3(poly->mParent);
340
341	//-- split polygon into front and back part
342	poly->Split(plane,
343	*front_piece,
344	*back_piece,
345	mEpsilon);
346
347	++ splits; // increase number of splits
348
349	//-- inherit rays from parent polygon for blocked ray criterium
350	poly->InheritRays(front_piece, back_piece);
351
352	// check if polygons still valid
353	if (front_piece->Valid(mEpsilon))
354	frontPolys.push_back(front_piece);
355	else
356	DEL_PTR(front_piece);
357
358	if (back_piece->Valid(mEpsilon))
359	backPolys.push_back(back_piece);
360	else
361	DEL_PTR(back_piece);
362
363	#ifdef _DEBUG
364	Debug << "split " << poly << endl << front_piece << endl << *back_piece << endl;
365	#endif
366	DEL_PTR(poly);
367	}
368	break;
369	default:
370	Debug << "SHOULD NEVER COME HERE\n";
371	break;
372	}
373	}
374
375	return splits;
376	}
377
378
379	void BspTreeStatistics::Print(ostream &app) const
380	{
381	app << "===== BspTree statistics ===============\n";
382
383	app << setprecision(4);
384
385	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
386
387	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
388
389	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
390
391	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
392
393	app << "#N_POLYSPLITS ( Number of polygon splits )\n" << polySplits << "\n";
394
395	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
396
397	app << "#N_SPLITS ( Number of splits in axes x y z\n";
398
399	for (int i = 0; i < 3; ++ i)
400	app << splits[i] << " ";
401	app << endl;
402
403	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
404	<< maxDepthNodes * 100 / (double)Leaves() << endl;
405
406	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
407	<< minPvsNodes * 100 / (double)Leaves() << endl;
408
409	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
410	<< minRaysNodes * 100 / (double)Leaves() << endl;
411
412	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
413	<< maxCostNodes * 100 / (double)Leaves() << endl;
414
415	app << "#N_PMINPROBABILITYAREALEAVES ( Percentage of leaves with mininum probability )\n"
416	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
417
418	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
419	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
420
421	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
422
423	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
424
425	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
426
427	app << "#N_INPUTPOLYGONS (number of input polygons )\n" << polys << endl;
428
429	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
430
431	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
432	//app << "#N_PVS: " << pvs << endl;
433
434	app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
435	(polys + polySplits) / (double)polys << endl;
436
437	app << "===== END OF BspTree statistics ==========\n";
438	}
439
440
441	BspTree::~BspTree()
442	{
443	DEL_PTR(mRoot);
444
445	// HACK: view cells not generated => root cell not used
446	if (mGenerateViewCells)
447	DEL_PTR(mRootCell);
448	}
449
450	BspViewCell *BspTree::GetRootCell() const
451	{
452	return mRootCell;
453	}
454
455	void BspTree::InsertViewCell(ViewCell *viewCell)
456	{
457	PolygonContainer *polys = new PolygonContainer();
458
459	// don't generate new view cell, insert this one
460	mGenerateViewCells = false;
461	// extract polygons that guide the split process
462	mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
463	mBox.Include(viewCell->GetBox()); // add to BSP aabb
464
465	InsertPolygons(polys);
466	}
467
468	void BspTree::InsertPolygons(PolygonContainer *polys)
469	{
470	BspTraversalStack tStack;
471
472	// traverse existing tree or create new tree
473	if (!mRoot)
474	mRoot = new BspLeaf();
475
476	tStack.push(BspTraversalData(mRoot,
477	polys,
478	0,
479	mRootCell,
480	new BoundedRayContainer(),
481	0,
482	mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(),
483	new BspNodeGeometry()));
484
485	while (!tStack.empty())
486	{
487	// filter polygons donw the tree
488	BspTraversalData tData = tStack.top();
489	tStack.pop();
490
491	if (!tData.mNode->IsLeaf())
492	{
493	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
494
495	//-- filter view cell polygons down the tree until a leaf is reached
496	if (!tData.mPolygons->empty())
497	{
498	PolygonContainer *frontPolys = new PolygonContainer();
499	PolygonContainer *backPolys = new PolygonContainer();
500	PolygonContainer coincident;
501
502	int splits = 0;
503
504	// split viewcell polygons with respect to split plane
505	splits += SplitPolygons(interior->GetPlane(),
506	*tData.mPolygons,
507	*frontPolys,
508	*backPolys,
509	coincident);
510
511	// extract view cells associated with the split polygons
512	ViewCell *frontViewCell = mRootCell;
513	ViewCell *backViewCell = mRootCell;
514
515	BspTraversalData frontData(interior->GetFront(),
516	frontPolys,
517	tData.mDepth + 1,
518	mRootCell,
519	tData.mRays,
520	tData.mPvs,
521	mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(),
522	new BspNodeGeometry());
523
524	BspTraversalData backData(interior->GetBack(),
525	backPolys,
526	tData.mDepth + 1,
527	mRootCell,
528	tData.mRays,
529	tData.mPvs,
530	mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(),
531	new BspNodeGeometry());
532
533	if (!mGenerateViewCells)
534	{
535	ExtractViewCells(frontData,
536	backData,
537	coincident,
538	interior->mPlane);
539	}
540
541	// don't need coincident polygons anymore
542	CLEAR_CONTAINER(coincident);
543
544	mStat.polySplits += splits;
545
546	// push the children on the stack
547	tStack.push(frontData);
548	tStack.push(backData);
549	}
550
551	// cleanup
552	DEL_PTR(tData.mPolygons);
553	DEL_PTR(tData.mRays);
554	}
555	else
556	{
557	// reached leaf => subdivide current viewcell
558	BspNode *subRoot = Subdivide(tStack, tData);
559	}
560	}
561	}
562
563	int BspTree::AddMeshToPolygons(Mesh *mesh,
564	PolygonContainer &polys,
565	MeshInstance *parent)
566	{
567	FaceContainer::const_iterator fi;
568
569	// copy the face data to polygons
570	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
571	{
572	Polygon3 poly = new Polygon3((fi), mesh);
573
574	if (poly->Valid(mEpsilon))
575	{
576	poly->mParent = parent; // set parent intersectable
577	polys.push_back(poly);
578	}
579	else
580	DEL_PTR(poly);
581	}
582	return (int)mesh->mFaces.size();
583	}
584
585
586	int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
587	PolygonContainer &polys,
588	int maxObjects)
589	{
590	int limit = (maxObjects > 0) ?
591	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
592
593	int polysSize = 0;
594
595	for (int i = 0; i < limit; ++ i)
596	{
597	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
598	{
599	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
600	polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
601	}
602	}
603
604	return polysSize;
605	}
606
607
608	int BspTree::AddToPolygonSoup(const ObjectContainer &objects,
609	PolygonContainer &polys,
610	int maxObjects,
611	bool addToBbox)
612	{
613	int limit = (maxObjects > 0) ?
614	Min((int)objects.size(), maxObjects) : (int)objects.size();
615
616	for (int i = 0; i < limit; ++i)
617	{
618	Intersectable object = objects[i];//it;
619	Mesh *mesh = NULL;
620
621	switch (object->Type()) // extract the meshes
622	{
623	case Intersectable::MESH_INSTANCE:
624	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
625	break;
626	case Intersectable::VIEW_CELL:
627	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
628	break;
629	// TODO: handle transformed mesh instances
630	default:
631	Debug << "intersectable type not supported" << endl;
632	break;
633	}
634
635	if (mesh) // copy the mesh data to polygons
636	{
637	if (addToBbox)
638	{
639	mBox.Include(object->GetBox()); // add to BSP tree aabb
640	}
641
642	AddMeshToPolygons(mesh, polys, mRootCell);
643	}
644	}
645
646	return (int)polys.size();
647	}
648
649
650	void BspTree::Construct(const ViewCellContainer &viewCells)
651	{
652	mStat.nodes = 1;
653	mBox.Initialize(); // initialise bsp tree bounding box
654
655	// copy view cell meshes into one big polygon soup
656	PolygonContainer *polys = new PolygonContainer();
657	mStat.polys = AddToPolygonSoup(viewCells, *polys);
658
659	// view cells are given
660	mGenerateViewCells = false;
661	// construct tree from the view cell polygons
662	Construct(polys, new BoundedRayContainer());
663	}
664
665
666	void BspTree::Construct(const ObjectContainer &objects)
667	{
668	mStat.nodes = 1;
669	mBox.Initialize(); // initialise bsp tree bounding box
670
671	PolygonContainer *polys = new PolygonContainer();
672
673	mGenerateViewCells = true;
674	// copy mesh instance polygons into one big polygon soup
675	mStat.polys = AddToPolygonSoup(objects, *polys);
676
677	// construct tree from polygon soup
678	Construct(polys, new BoundedRayContainer());
679	}
680
681
682	void BspTree::Construct(const RayContainer &sampleRays,
683	AxisAlignedBox3 *forcedBoundingBox)
684	{
685	mStat.nodes = 1;
686	mBox.Initialize(); // initialise BSP tree bounding box
687
688	if (forcedBoundingBox)
689	mBox = *forcedBoundingBox;
690
691	PolygonContainer *polys = new PolygonContainer();
692	BoundedRayContainer *rays = new BoundedRayContainer();
693
694	RayContainer::const_iterator rit, rit_end = sampleRays.end();
695
696	// generate view cells
697	mGenerateViewCells = true;
698
699	long startTime = GetTime();
700
701	Debug << "** Extracting polygons from rays **\n";
702
703	std::map<Face , Polygon3 > facePolyMap;
704
705	//-- extract polygons intersected by the rays
706	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
707	{
708	Ray ray = rit;
709
710	// get ray-face intersection. Store polygon representing the rays together
711	// with rays intersecting the face.
712	if (!ray->intersections.empty())
713	{
714	MeshInstance obj = dynamic_cast<MeshInstance >(ray->intersections[0].mObject);
715	Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
716
717	std::map<Face , Polygon3 >::iterator it = facePolyMap.find(face);
718
719	if (it != facePolyMap.end())
720	{
721	//store rays if needed for heuristics
722	if (mSplitPlaneStrategy & BLOCKED_RAYS)
723	(*it).second->mPiercingRays.push_back(ray);
724	}
725	else
726	{ //store rays if needed for heuristics
727	Polygon3 *poly = new Polygon3(face, obj->GetMesh());
728	poly->mParent = obj;
729	polys->push_back(poly);
730
731	if (mSplitPlaneStrategy & BLOCKED_RAYS)
732	poly->mPiercingRays.push_back(ray);
733
734	facePolyMap[face] = poly;
735	}
736	}
737	}
738
739	facePolyMap.clear();
740
741	// compute bounding box
742	if (!forcedBoundingBox)
743	Polygon3::IncludeInBox(*polys, mBox);
744
745	//-- store rays
746	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
747	{
748	Ray ray = rit;
749	ray->SetId(-1); // reset id
750
751	float minT, maxT;
752	if (mBox.GetRaySegment(*ray, minT, maxT))
753	rays->push_back(new BoundedRay(ray, minT, maxT));
754	}
755
756	mStat.polys = (int)polys->size();
757
758	Debug << "** Finished polygon extraction **" << endl;
759	Debug << (int)polys->size() << " polys extracted from " << (int)sampleRays.size() << " rays" << endl;
760	Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
761
762	Construct(polys, rays);
763	}
764
765
766	void BspTree::Construct(const ObjectContainer &objects,
767	const RayContainer &sampleRays,
768	AxisAlignedBox3 *forcedBoundingBox)
769	{
770	mStat.nodes = 1;
771	mBox.Initialize(); // initialise BSP tree bounding box
772
773	if (forcedBoundingBox)
774	mBox = *forcedBoundingBox;
775
776	BoundedRayContainer *rays = new BoundedRayContainer();
777	PolygonContainer *polys = new PolygonContainer();
778
779	mGenerateViewCells = true;
780
781	// copy mesh instance polygons into one big polygon soup
782	mStat.polys = AddToPolygonSoup(objects, *polys, 0, !forcedBoundingBox);
783
784
785	RayContainer::const_iterator rit, rit_end = sampleRays.end();
786
787	//-- store rays
788	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
789	{
790	Ray ray = rit;
791	ray->SetId(-1); // reset id
792
793	float minT, maxT;
794	if (mBox.GetRaySegment(*ray, minT, maxT))
795	rays->push_back(new BoundedRay(ray, minT, maxT));
796	}
797
798	Debug << "tree has " << (int)polys->size() << " polys, " << (int)sampleRays.size() << " rays" << endl;
799	Construct(polys, rays);
800	}
801
802
803	void BspTree::Construct(PolygonContainer polys, BoundedRayContainer rays)
804	{
805	BspTraversalStack tStack;
806
807	mRoot = new BspLeaf();
808
809	// constrruct root node geometry
810	BspNodeGeometry *geom = new BspNodeGeometry();
811	ConstructGeometry(mRoot, *geom);
812
813	BspTraversalData tData(mRoot,
814	polys,
815	0,
816	mRootCell,
817	rays,
818	ComputePvsSize(*rays),
819	mUseAreaForPvs ? geom->GetArea() : geom->GetVolume(),
820	geom);
821
822	tStack.push(tData);
823
824	mStat.Start();
825	cout << "Contructing bsp tree ... ";
826	long startTime = GetTime();
827	while (!tStack.empty())
828	{
829	tData = tStack.top();
830
831	tStack.pop();
832
833	// subdivide leaf node
834	BspNode *r = Subdivide(tStack, tData);
835
836	if (r == mRoot)
837	Debug << "BSP tree construction time spent at root: "
838	<< TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
839	}
840
841	cout << "finished\n";
842
843	mStat.Stop();
844	}
845
846	bool BspTree::TerminationCriteriaMet(const BspTraversalData &data) const
847	{
848	return
849	(((int)data.mPolygons->size() <= mTermMinPolys) \|\|
850	((int)data.mRays->size() <= mTermMinRays) \|\|
851	(data.mPvs <= mTermMinPvs) \|\|
852	(data.mProbability <= mTermMinProbability) \|\|
853	(data.mDepth >= mTermMaxDepth) \|\|
854	(mStat.Leaves() >= mMaxViewCells) \|\|
855	(data.GetAvgRayContribution() > mTermMaxRayContribution));
856	}
857
858	BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
859	{
860	//-- terminate traversal
861	if (TerminationCriteriaMet(tData))
862	{
863	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
864
865	BspViewCell *viewCell;
866
867	// generate new view cell for each leaf
868	if (mGenerateViewCells)
869	viewCell = new BspViewCell();
870	else
871	// add view cell to leaf
872	viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
873
874	leaf->SetViewCell(viewCell);
875	viewCell->mLeaf = leaf;
876
877	if (mUseAreaForPvs)
878	viewCell->SetArea(tData.mProbability);
879	else
880	viewCell->SetVolume(tData.mProbability);
881
882	//-- add pvs
883	if (viewCell != mRootCell)
884	{
885	int conSamp = 0, sampCon = 0;
886	AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
887
888	mStat.contributingSamples += conSamp;
889	mStat.sampleContributions += sampCon;
890	}
891
892	EvaluateLeafStats(tData);
893
894	//-- clean up
895
896	// discard polygons
897	CLEAR_CONTAINER(*tData.mPolygons);
898	// discard rays
899	CLEAR_CONTAINER(*tData.mRays);
900
901	DEL_PTR(tData.mPolygons);
902	DEL_PTR(tData.mRays);
903	DEL_PTR(tData.mGeometry);
904
905	return leaf;
906	}
907
908	//-- continue subdivision
909	PolygonContainer coincident;
910
911	BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
912	new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
913	BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
914	new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
915
916	// create new interior node and two leaf nodes
917	BspInterior *interior =
918	SubdivideNode(tData, tFrontData, tBackData, coincident);
919
920
921	// extract view cells from coincident polygons according to plane normal
922	// only if front or back polygons are empty
923	if (!mGenerateViewCells)
924	{
925	ExtractViewCells(tFrontData,
926	tBackData,
927	coincident,
928	interior->mPlane);
929	}
930
931	// don't need coincident polygons anymory
932	CLEAR_CONTAINER(coincident);
933
934	// push the children on the stack
935	tStack.push(tFrontData);
936	tStack.push(tBackData);
937
938	// cleanup
939	DEL_PTR(tData.mNode);
940
941	DEL_PTR(tData.mPolygons);
942	DEL_PTR(tData.mRays);
943	DEL_PTR(tData.mGeometry);
944
945	return interior;
946	}
947
948	void BspTree::ExtractViewCells(BspTraversalData &frontData,
949	BspTraversalData &backData,
950	const PolygonContainer &coincident,
951	const Plane3 &splitPlane) const
952	{
953	// if not empty, tree is further subdivided => don't have to find view cell
954	bool foundFront = !frontData.mPolygons->empty();
955	bool foundBack = !frontData.mPolygons->empty();
956
957	PolygonContainer::const_iterator it =
958	coincident.begin(), it_end = coincident.end();
959
960	//-- find first view cells in front and back leafs
961	for (; !(foundFront && foundBack) && (it != it_end); ++ it)
962	{
963	if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
964	{
965	backData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
966	foundBack = true;
967	}
968	else
969	{
970	frontData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
971	foundFront = true;
972	}
973	}
974	}
975
976	BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
977	BspTraversalData &frontData,
978	BspTraversalData &backData,
979	PolygonContainer &coincident)
980	{
981	mStat.nodes += 2;
982
983	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
984
985	long startTime;
986	if (0)
987	{
988	Debug << "*********************" << endl;
989	startTime = GetTime();
990	}
991
992	// select subdivision plane
993	BspInterior *interior =
994	new BspInterior(SelectPlane(leaf, tData));
995
996	if (0)
997	{
998	Debug << "time used for split plane selection: "
999	<< TimeDiff(startTime, GetTime()) * 1e-3 << "s" << endl;
1000	}
1001	#ifdef _DEBUG
1002	Debug << interior << endl;
1003	#endif
1004
1005
1006	if (0)
1007	{
1008	Debug << "number of rays: " << (int)tData.mRays->size() << endl;
1009	Debug << "number of polys: " << (int)tData.mPolygons->size() << endl;
1010
1011	startTime = GetTime();
1012	}
1013
1014	// subdivide rays into front and back rays
1015	SplitRays(interior->mPlane, tData.mRays, frontData.mRays, *backData.mRays);
1016
1017	if (0)
1018	{
1019	Debug << "time used for rays splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
1020	startTime = GetTime();
1021	}
1022
1023	// subdivide polygons with plane
1024	mStat.polySplits += SplitPolygons(interior->GetPlane(),
1025	*tData.mPolygons,
1026	*frontData.mPolygons,
1027	*backData.mPolygons,
1028	coincident);
1029
1030	if (0)
1031	{
1032	Debug << "time used for polygon splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
1033	}
1034
1035	// compute pvs
1036	frontData.mPvs = ComputePvsSize(*frontData.mRays);
1037	backData.mPvs = ComputePvsSize(*backData.mRays);
1038
1039	// split geometry and compute area
1040	if (1)
1041	{
1042	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
1043	*backData.mGeometry,
1044	interior->mPlane,
1045	mBox,
1046	mEpsilon);
1047
1048
1049	frontData.mProbability = frontData.mGeometry->GetVolume();
1050	backData.mProbability = backData.mGeometry->GetVolume();
1051	}
1052
1053	// compute accumulated ray length
1054	//frontData.mAccRayLength = AccumulatedRayLength(*frontData.mRays);
1055	//backData.mAccRayLength = AccumulatedRayLength(*backData.mRays);
1056
1057	//-- create front and back leaf
1058
1059	BspInterior *parent = leaf->GetParent();
1060
1061	// replace a link from node's parent
1062	if (!leaf->IsRoot())
1063	{
1064	parent->ReplaceChildLink(leaf, interior);
1065	interior->SetParent(parent);
1066	}
1067	else // new root
1068	{
1069	mRoot = interior;
1070	}
1071
1072	// and setup child links
1073	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
1074
1075	frontData.mNode = interior->GetFront();
1076	backData.mNode = interior->GetBack();
1077
1078	//DEL_PTR(leaf);
1079	return interior;
1080	}
1081
1082
1083	void BspTree::SortSplitCandidates(const PolygonContainer &polys,
1084	const int axis,
1085	vector<SortableEntry> &splitCandidates) const
1086	{
1087	splitCandidates.clear();
1088
1089	int requestedSize = 2 * (int)polys.size();
1090	// creates a sorted split candidates array
1091	splitCandidates.reserve(requestedSize);
1092
1093	PolygonContainer::const_iterator it, it_end = polys.end();
1094
1095	AxisAlignedBox3 box;
1096
1097	// insert all queries
1098	for(it = polys.begin(); it != it_end; ++ it)
1099	{
1100	box.Initialize();
1101	box.Include((it));
1102
1103	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
1104	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
1105	}
1106
1107	stable_sort(splitCandidates.begin(), splitCandidates.end());
1108	}
1109
1110
1111	float BspTree::BestCostRatio(const PolygonContainer &polys,
1112	const AxisAlignedBox3 &box,
1113	const int axis,
1114	float &position,
1115	int &objectsBack,
1116	int &objectsFront) const
1117	{
1118	vector<SortableEntry> splitCandidates;
1119
1120	SortSplitCandidates(polys, axis, splitCandidates);
1121
1122	// go through the lists, count the number of objects left and right
1123	// and evaluate the following cost funcion:
1124	// C = ct_div_ci + (ol + or)/queries
1125
1126	int objectsLeft = 0, objectsRight = (int)polys.size();
1127
1128	float minBox = box.Min(axis);
1129	float maxBox = box.Max(axis);
1130	float boxArea = box.SurfaceArea();
1131
1132	float minBand = minBox + mSplitBorder * (maxBox - minBox);
1133	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
1134
1135	float minSum = 1e20f;
1136	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
1137
1138	for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
1139	{
1140	switch ((*ci).type)
1141	{
1142	case SortableEntry::POLY_MIN:
1143	++ objectsLeft;
1144	break;
1145	case SortableEntry::POLY_MAX:
1146	-- objectsRight;
1147	break;
1148	default:
1149	break;
1150	}
1151
1152	if ((ci).value > minBand && (ci).value < maxBand)
1153	{
1154	AxisAlignedBox3 lbox = box;
1155	AxisAlignedBox3 rbox = box;
1156	lbox.SetMax(axis, (*ci).value);
1157	rbox.SetMin(axis, (*ci).value);
1158
1159	const float sum = objectsLeft * lbox.SurfaceArea() +
1160	objectsRight * rbox.SurfaceArea();
1161
1162	if (sum < minSum)
1163	{
1164	minSum = sum;
1165	position = (*ci).value;
1166
1167	objectsBack = objectsLeft;
1168	objectsFront = objectsRight;
1169	}
1170	}
1171	}
1172
1173	const float oldCost = (float)polys.size();
1174	const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
1175	const float ratio = newCost / oldCost;
1176
1177
1178	#if 0
1179	Debug << "====================" << endl;
1180	Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
1181	<< "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
1182	#endif
1183	return ratio;
1184	}
1185
1186	bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
1187	const PolygonContainer &polys) const
1188	{
1189	AxisAlignedBox3 box;
1190	box.Initialize();
1191
1192	// create bounding box of region
1193	Polygon3::IncludeInBox(polys, box);
1194
1195	int objectsBack = 0, objectsFront = 0;
1196	int axis = 0;
1197	float costRatio = MAX_FLOAT;
1198	Vector3 position;
1199
1200	//-- area subdivision
1201	for (int i = 0; i < 3; ++ i)
1202	{
1203	float p = 0;
1204	float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
1205
1206	if (r < costRatio)
1207	{
1208	costRatio = r;
1209	axis = i;
1210	position = p;
1211	}
1212	}
1213
1214	if (costRatio >= mMaxCostRatio)
1215	return false;
1216
1217	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1218	plane = Plane3(norm, position);
1219
1220	return true;
1221	}
1222
1223
1224	Plane3 BspTree::SelectPlane(BspLeaf *leaf, BspTraversalData &data)
1225	{
1226	if (data.mPolygons->empty() && data.mRays->empty())
1227	{
1228	Debug << "Warning: No autopartition polygon candidate available\n";
1229
1230	// return axis aligned split
1231	AxisAlignedBox3 box;
1232	box.Initialize();
1233
1234	// create bounding box of region
1235	Polygon3::IncludeInBox(*data.mPolygons, box);
1236
1237	const int axis = box.Size().DrivingAxis();
1238	const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1239
1240	Vector3 norm(0,0,0); norm[axis] = 1.0f;
1241	return Plane3(norm, position);
1242	}
1243
1244	if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&
1245	((int)data.mPolygons->size() > mTermMinPolysForAxisAligned) &&
1246	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1247	((mTermMinObjectsForAxisAligned < 0) \|\|
1248	(Polygon3::ParentObjectsSize(*data.mPolygons) > mTermMinObjectsForAxisAligned)))
1249	{
1250	Plane3 plane;
1251	if (SelectAxisAlignedPlane(plane, *data.mPolygons))
1252	return plane;
1253	}
1254
1255	// simplest strategy: just take next polygon
1256	if (mSplitPlaneStrategy & RANDOM_POLYGON)
1257	{
1258	if (!data.mPolygons->empty())
1259	{
1260	Polygon3 *nextPoly =
1261	(*data.mPolygons)[(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1))];
1262	return nextPoly->GetSupportingPlane();
1263	}
1264	else
1265	{
1266	const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
1267	BoundedRay bRay = (data.mRays)[candidateIdx];
1268
1269	Ray *ray = bRay->mRay;
1270
1271	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1272	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1273
1274	const Vector3 pt = (maxPt + minPt) * 0.5;
1275
1276	const Vector3 normal = ray->GetDir();
1277
1278	return Plane3(normal, pt);
1279	}
1280
1281	return Plane3();
1282	}
1283
1284	// use heuristics to find appropriate plane
1285	return SelectPlaneHeuristics(leaf, data);
1286	}
1287
1288
1289	Plane3 BspTree::ChooseCandidatePlane(const BoundedRayContainer &rays) const
1290	{
1291	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1292	BoundedRay *bRay = rays[candidateIdx];
1293	Ray *ray = bRay->mRay;
1294
1295	const Vector3 minPt = ray->Extrap(bRay->mMinT);
1296	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
1297
1298	const Vector3 pt = (maxPt + minPt) * 0.5;
1299
1300	const Vector3 normal = ray->GetDir();
1301
1302	return Plane3(normal, pt);
1303	}
1304
1305	Plane3 BspTree::ChooseCandidatePlane2(const BoundedRayContainer &rays) const
1306	{
1307	Vector3 pt[3];
1308	int idx[3];
1309	int cmaxT = 0;
1310	int cminT = 0;
1311	bool chooseMin = false;
1312
1313	for (int j = 0; j < 3; j ++)
1314	{
1315	idx[j] = (int)RandomValue(0, Real((int)rays.size() * 2 - 1));
1316
1317	if (idx[j] >= (int)rays.size())
1318	{
1319	idx[j] -= (int)rays.size();
1320	chooseMin = (cminT < 2);
1321	}
1322	else
1323	chooseMin = (cmaxT < 2);
1324
1325	BoundedRay *bRay = rays[idx[j]];
1326	pt[j] = chooseMin ? bRay->mRay->Extrap(bRay->mMinT) :
1327	bRay->mRay->Extrap(bRay->mMaxT);
1328	}
1329
1330	return Plane3(pt[0], pt[1], pt[2]);
1331	}
1332
1333	Plane3 BspTree::ChooseCandidatePlane3(const BoundedRayContainer &rays) const
1334	{
1335	Vector3 pt[3];
1336
1337	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1338	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1339
1340	// check if rays different
1341	if (idx1 == idx2)
1342	idx2 = (idx2 + 1) % (int)rays.size();
1343
1344	const BoundedRay *ray1 = rays[idx1];
1345	const BoundedRay *ray2 = rays[idx2];
1346
1347	// normal vector of the plane parallel to both lines
1348	const Vector3 norm =
1349	Normalize(CrossProd(ray1->mRay->GetDir(), ray2->mRay->GetDir()));
1350
1351	const Vector3 orig1 = ray1->mRay->Extrap(ray1->mMinT);
1352	const Vector3 orig2 = ray2->mRay->Extrap(ray2->mMinT);
1353
1354	// vector from line 1 to line 2
1355	const Vector3 vd = orig1 - orig2;
1356
1357	// project vector on normal to get distance
1358	const float dist = DotProd(vd, norm);
1359
1360	// point on plane lies halfway between the two planes
1361	const Vector3 planePt = orig1 + norm * dist * 0.5;
1362
1363	return Plane3(norm, planePt);
1364	}
1365
1366
1367	Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf, BspTraversalData &data)
1368	{
1369	float lowestCost = MAX_FLOAT;
1370	Plane3 bestPlane;
1371	// intermediate plane
1372	Plane3 plane;
1373
1374	const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1375	int maxIdx = (int)data.mPolygons->size();
1376
1377	for (int i = 0; i < limit; ++ i)
1378	{
1379	// assure that no index is taken twice
1380	const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1381
1382	Polygon3 poly = (data.mPolygons)[candidateIdx];
1383
1384	// swap candidate to the end to avoid testing same plane
1385	std::swap((data.mPolygons)[maxIdx], (data.mPolygons)[candidateIdx]);
1386	//Polygon3 poly = (data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1387
1388	// evaluate current candidate
1389	const float candidateCost =
1390	SplitPlaneCost(poly->GetSupportingPlane(), data);
1391
1392	if (candidateCost < lowestCost)
1393	{
1394	bestPlane = poly->GetSupportingPlane();
1395	lowestCost = candidateCost;
1396	}
1397	}
1398
1399	//-- choose candidate planes extracted from rays
1400	for (int i = 0; i < mMaxRayCandidates; ++ i)
1401	{
1402	plane = ChooseCandidatePlane3(*data.mRays);
1403	const float candidateCost = SplitPlaneCost(plane, data);
1404
1405	if (candidateCost < lowestCost)
1406	{
1407	bestPlane = plane;
1408	lowestCost = candidateCost;
1409	}
1410	}
1411
1412	#ifdef _DEBUG
1413	Debug << "plane lowest cost: " << lowestCost << endl;
1414	#endif
1415
1416	return bestPlane;
1417	}
1418
1419
1420	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1421	const PolygonContainer &polys) const
1422	{
1423	float val = 0;
1424
1425	float sumBalancedPolys = 0;
1426	float sumSplits = 0;
1427	float sumPolyArea = 0;
1428	float sumBalancedViewCells = 0;
1429	float sumBlockedRays = 0;
1430	float totalBlockedRays = 0;
1431	//float totalArea = 0;
1432	int totalViewCells = 0;
1433
1434	// need three unique ids for each type of view cell
1435	// for balanced view cells criterium
1436	ViewCell::NewMail();
1437	const int backId = ViewCell::sMailId;
1438	ViewCell::NewMail();
1439	const int frontId = ViewCell::sMailId;
1440	ViewCell::NewMail();
1441	const int frontAndBackId = ViewCell::sMailId;
1442
1443	bool useRand;;
1444	int limit;
1445
1446	// choose test polyongs randomly if over threshold
1447	if ((int)polys.size() > mMaxTests)
1448	{
1449	useRand = true;
1450	limit = mMaxTests;
1451	}
1452	else
1453	{
1454	useRand = false;
1455	limit = (int)polys.size();
1456	}
1457
1458	for (int i = 0; i < limit; ++ i)
1459	{
1460	const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
1461
1462	Polygon3 *poly = polys[testIdx];
1463
1464	const int classification =
1465	poly->ClassifyPlane(candidatePlane, mEpsilon);
1466
1467	if (mSplitPlaneStrategy & BALANCED_POLYS)
1468	sumBalancedPolys += sBalancedPolysTable[classification];
1469
1470	if (mSplitPlaneStrategy & LEAST_SPLITS)
1471	sumSplits += sLeastPolySplitsTable[classification];
1472
1473	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1474	{
1475	if (classification == Polygon3::COINCIDENT)
1476	sumPolyArea += poly->GetArea();
1477	//totalArea += area;
1478	}
1479
1480	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1481	{
1482	const float blockedRays = (float)poly->mPiercingRays.size();
1483
1484	if (classification == Polygon3::COINCIDENT)
1485	sumBlockedRays += blockedRays;
1486
1487	totalBlockedRays += blockedRays;
1488	}
1489
1490	// assign view cells to back or front according to classificaion
1491	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1492	{
1493	MeshInstance *viewCell = poly->mParent;
1494
1495	// assure that we only count a view cell
1496	// once for the front and once for the back side of the plane
1497	if (classification == Polygon3::FRONT_SIDE)
1498	{
1499	if ((viewCell->mMailbox != frontId) &&
1500	(viewCell->mMailbox != frontAndBackId))
1501	{
1502	sumBalancedViewCells += 1.0;
1503
1504	if (viewCell->mMailbox != backId)
1505	viewCell->mMailbox = frontId;
1506	else
1507	viewCell->mMailbox = frontAndBackId;
1508
1509	++ totalViewCells;
1510	}
1511	}
1512	else if (classification == Polygon3::BACK_SIDE)
1513	{
1514	if ((viewCell->mMailbox != backId) &&
1515	(viewCell->mMailbox != frontAndBackId))
1516	{
1517	sumBalancedViewCells -= 1.0;
1518
1519	if (viewCell->mMailbox != frontId)
1520	viewCell->mMailbox = backId;
1521	else
1522	viewCell->mMailbox = frontAndBackId;
1523
1524	++ totalViewCells;
1525	}
1526	}
1527	}
1528	}
1529
1530	const float polysSize = (float)polys.size() + Limits::Small;
1531
1532	// all values should be approx. between 0 and 1 so they can be combined
1533	// and scaled with the factors according to their importance
1534	if (mSplitPlaneStrategy & BALANCED_POLYS)
1535	val += mBalancedPolysFactor * fabs(sumBalancedPolys) / polysSize;
1536
1537	if (mSplitPlaneStrategy & LEAST_SPLITS)
1538	val += mLeastSplitsFactor * sumSplits / polysSize;
1539
1540	if (mSplitPlaneStrategy & LARGEST_POLY_AREA)
1541	// HACK: polys.size should be total area so scaling is between 0 and 1
1542	val += mLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
1543
1544	if (mSplitPlaneStrategy & BLOCKED_RAYS)
1545	if (totalBlockedRays != 0)
1546	val += mBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
1547
1548	if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
1549	val += mBalancedViewCellsFactor * fabs(sumBalancedViewCells) /
1550	((float)totalViewCells + Limits::Small);
1551
1552	return val;
1553	}
1554
1555
1556	inline void BspTree::GenerateUniqueIdsForPvs()
1557	{
1558	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1559	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1560	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1561	}
1562
1563
1564	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1565	const BoundedRayContainer &rays,
1566	const int pvs,
1567	const float probability,
1568	const BspNodeGeometry &cell) const
1569	{
1570	float val = 0;
1571
1572	float sumBalancedRays = 0;
1573	float sumRaySplits = 0;
1574
1575	int frontPvs = 0;
1576	int backPvs = 0;
1577
1578	// probability that view point lies in child
1579	float pOverall = 0;
1580	float pFront = 0;
1581	float pBack = 0;
1582
1583	const bool pvsUseLen = false;
1584
1585	if (mSplitPlaneStrategy & PVS)
1586	{
1587	// create unique ids for pvs heuristics
1588	GenerateUniqueIdsForPvs();
1589
1590	// construct child geometry with regard to the candidate split plane
1591	BspNodeGeometry frontCell;
1592	BspNodeGeometry backCell;
1593
1594	cell.SplitGeometry(frontCell,
1595	backCell,
1596	candidatePlane,
1597	mBox,
1598	mEpsilon);
1599
1600	if (mUseAreaForPvs)
1601	{
1602	pFront = frontCell.GetArea();
1603	pBack = backCell.GetArea();
1604	}
1605	else
1606	{
1607	pFront = frontCell.GetVolume();
1608	pBack = backCell.GetVolume();
1609	}
1610
1611
1612	pOverall = probability;
1613	}
1614
1615	bool useRand;
1616	int limit;
1617
1618	// choose test polyongs randomly if over threshold
1619	if ((int)rays.size() > mMaxTests)
1620	{
1621	useRand = true;
1622	limit = mMaxTests;
1623	}
1624	else
1625	{
1626	useRand = false;
1627	limit = (int)rays.size();
1628	}
1629
1630	for (int i = 0; i < limit; ++ i)
1631	{
1632	const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
1633
1634	BoundedRay *bRay = rays[testIdx];
1635
1636	Ray *ray = bRay->mRay;
1637	const float minT = bRay->mMinT;
1638	const float maxT = bRay->mMaxT;
1639
1640	Vector3 entP, extP;
1641
1642	const int cf =
1643	ray->ClassifyPlane(candidatePlane, minT, maxT, entP, extP);
1644
1645	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1646	{
1647	sumBalancedRays += sBalancedRaysTable[cf];
1648	}
1649
1650	if (mSplitPlaneStrategy & BALANCED_RAYS)
1651	{
1652	sumRaySplits += sLeastRaySplitsTable[cf];
1653	}
1654
1655	if (mSplitPlaneStrategy & PVS)
1656	{
1657	// in case the ray intersects an object
1658	// assure that we only count the object
1659	// once for the front and once for the back side of the plane
1660
1661	// add the termination object
1662	if (!ray->intersections.empty())
1663	AddObjToPvs(ray->intersections[0].mObject, cf, frontPvs, backPvs);
1664
1665	// add the source object
1666	AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
1667	}
1668	}
1669
1670	const float raysSize = (float)rays.size() + Limits::Small;
1671
1672	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1673	val += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1674
1675	if (mSplitPlaneStrategy & BALANCED_RAYS)
1676	val += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1677
1678	const float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
1679
1680	if (mSplitPlaneStrategy & PVS)
1681	{
1682	val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
1683
1684	// give penalty to unbalanced split
1685	if (0)
1686	if (((pFront * 0.2 + Limits::Small) > pBack) \|\|
1687	(pFront < (pBack * 0.2 + Limits::Small)))
1688	val += 0.5;
1689	}
1690
1691
1692	#ifdef _DEBUG
1693	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
1694	<< " frontpvs: " << frontPvs << " pFront: " << pFront
1695	<< " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
1696	#endif
1697
1698	return val;
1699	}
1700
1701	void BspTree::AddObjToPvs(Intersectable *obj,
1702	const int cf,
1703	int &frontPvs,
1704	int &backPvs) const
1705	{
1706	if (!obj)
1707	return;
1708	// TODO: does this really belong to no pvs?
1709	//if (cf == Ray::COINCIDENT) return;
1710
1711	// object belongs to both PVS
1712	const bool bothSides = (cf == Ray::FRONT_BACK) \|\|
1713	(cf == Ray::BACK_FRONT) \|\|
1714	(cf == Ray::COINCIDENT);
1715
1716	if ((cf == Ray::FRONT) \|\| bothSides)
1717	{
1718	if ((obj->mMailbox != sFrontId) &&
1719	(obj->mMailbox != sFrontAndBackId))
1720	{
1721	++ frontPvs;
1722
1723	if (obj->mMailbox == sBackId)
1724	obj->mMailbox = sFrontAndBackId;
1725	else
1726	obj->mMailbox = sFrontId;
1727	}
1728	}
1729
1730	if ((cf == Ray::BACK) \|\| bothSides)
1731	{
1732	if ((obj->mMailbox != sBackId) &&
1733	(obj->mMailbox != sFrontAndBackId))
1734	{
1735	++ backPvs;
1736
1737	if (obj->mMailbox == sFrontId)
1738	obj->mMailbox = sFrontAndBackId;
1739	else
1740	obj->mMailbox = sBackId;
1741	}
1742	}
1743	}
1744
1745	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1746	BspTraversalData &data) const
1747	{
1748	float val = 0;
1749
1750	if (mSplitPlaneStrategy & VERTICAL_AXIS)
1751	{
1752	Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
1753	// we put a penalty on the dot product between the "tiny" vertical axis
1754	// and the split plane axis
1755	val += mVerticalSplitsFactor *
1756	fabs(DotProd(candidatePlane.mNormal, tinyAxis));
1757	}
1758
1759	// the following criteria loop over all polygons to find the cost value
1760	if ((mSplitPlaneStrategy & BALANCED_POLYS) \|\|
1761	(mSplitPlaneStrategy & LEAST_SPLITS) \|\|
1762	(mSplitPlaneStrategy & LARGEST_POLY_AREA) \|\|
1763	(mSplitPlaneStrategy & BALANCED_VIEW_CELLS) \|\|
1764	(mSplitPlaneStrategy & BLOCKED_RAYS))
1765	{
1766	val += SplitPlaneCost(candidatePlane, *data.mPolygons);
1767	}
1768
1769	// the following criteria loop over all rays to find the cost value
1770	if ((mSplitPlaneStrategy & BALANCED_RAYS) \|\|
1771	(mSplitPlaneStrategy & LEAST_RAY_SPLITS) \|\|
1772	(mSplitPlaneStrategy & PVS))
1773	{
1774	val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
1775	data.mProbability, *data.mGeometry);
1776	}
1777
1778	// return linear combination of the sums
1779	return val;
1780	}
1781
1782	void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
1783	{
1784	stack<BspNode *> nodeStack;
1785	nodeStack.push(mRoot);
1786
1787	while (!nodeStack.empty())
1788	{
1789	BspNode *node = nodeStack.top();
1790
1791	nodeStack.pop();
1792
1793	if (node->IsLeaf())
1794	{
1795	BspLeaf leaf = (BspLeaf )node;
1796	leaves.push_back(leaf);
1797	}
1798	else
1799	{
1800	BspInterior interior = dynamic_cast<BspInterior >(node);
1801
1802	nodeStack.push(interior->GetBack());
1803	nodeStack.push(interior->GetFront());
1804	}
1805	}
1806	}
1807
1808
1809	AxisAlignedBox3 BspTree::GetBoundingBox() const
1810	{
1811	return mBox;
1812	}
1813
1814
1815	BspNode *BspTree::GetRoot() const
1816	{
1817	return mRoot;
1818	}
1819
1820	void BspTree::EvaluateLeafStats(const BspTraversalData &data)
1821	{
1822	// the node became a leaf -> evaluate stats for leafs
1823	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
1824
1825	// store maximal and minimal depth
1826	if (data.mDepth > mStat.maxDepth)
1827	mStat.maxDepth = data.mDepth;
1828
1829	if (data.mDepth < mStat.minDepth)
1830	mStat.minDepth = data.mDepth;
1831
1832	// accumulate depth to compute average depth
1833	mStat.accumDepth += data.mDepth;
1834	// accumulate rays to compute rays / leaf
1835	mStat.accumRays += (int)data.mRays->size();
1836
1837	if (data.mDepth >= mTermMaxDepth)
1838	++ mStat.maxDepthNodes;
1839
1840	if (data.mPvs < mTermMinPvs)
1841	++ mStat.minPvsNodes;
1842
1843	if ((int)data.mRays->size() < mTermMinRays)
1844	++ mStat.minRaysNodes;
1845
1846	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1847	++ mStat.maxRayContribNodes;
1848
1849	if (data.mProbability <= mTermMinProbability)
1850	++ mStat.minProbabilityNodes;
1851
1852	#ifdef _DEBUG
1853	Debug << "BSP stats: "
1854	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1855	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1856	<< "Probability: " << data.mProbability << " (min: " << mTermMinProbability << "), "
1857	<< "#polygons: " << (int)data.mPolygons->size() << " (max: " << mTermMinPolys << "), "
1858	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1859	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1860	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1861	#endif
1862	}
1863
1864	int
1865	BspTree::_CastRay(Ray &ray)
1866	{
1867	int hits = 0;
1868
1869	stack<BspRayTraversalData> tStack;
1870
1871	float maxt, mint;
1872
1873	if (!mBox.GetRaySegment(ray, mint, maxt))
1874	return 0;
1875
1876	Intersectable::NewMail();
1877
1878	Vector3 entp = ray.Extrap(mint);
1879	Vector3 extp = ray.Extrap(maxt);
1880
1881	BspNode *node = mRoot;
1882	BspNode *farChild = NULL;
1883
1884	while (1)
1885	{
1886	if (!node->IsLeaf())
1887	{
1888	BspInterior in = dynamic_cast<BspInterior >(node);
1889
1890	Plane3 splitPlane = in->GetPlane();
1891	const int entSide = splitPlane.Side(entp);
1892	const int extSide = splitPlane.Side(extp);
1893
1894	if (entSide < 0)
1895	{
1896	node = in->GetBack();
1897
1898	if(extSide <= 0) // plane does not split ray => no far child
1899	continue;
1900
1901	farChild = in->GetFront(); // plane splits ray
1902
1903	} else if (entSide > 0)
1904	{
1905	node = in->GetFront();
1906
1907	if (extSide >= 0) // plane does not split ray => no far child
1908	continue;
1909
1910	farChild = in->GetBack(); // plane splits ray
1911	}
1912	else // ray and plane are coincident
1913	{
1914	// WHAT TO DO IN THIS CASE ?
1915	//break;
1916	node = in->GetFront();
1917	continue;
1918	}
1919
1920	// push data for far child
1921	tStack.push(BspRayTraversalData(farChild, extp, maxt));
1922
1923	// find intersection of ray segment with plane
1924	float t;
1925	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1926	maxt *= t;
1927
1928	} else // reached leaf => intersection with view cell
1929	{
1930	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1931
1932	if (!leaf->mViewCell->Mailed())
1933	{
1934	// ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
1935	leaf->mViewCell->Mail();
1936	++ hits;
1937	}
1938
1939	//-- fetch the next far child from the stack
1940	if (tStack.empty())
1941	break;
1942
1943	entp = extp;
1944	mint = maxt; // NOTE: need this?
1945
1946	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1947	break;
1948
1949	BspRayTraversalData &s = tStack.top();
1950
1951	node = s.mNode;
1952	extp = s.mExitPoint;
1953	maxt = s.mMaxT;
1954
1955	tStack.pop();
1956	}
1957	}
1958
1959	return hits;
1960	}
1961
1962
1963	int BspTree::CastLineSegment(const Vector3 &origin,
1964	const Vector3 &termination,
1965	vector<ViewCell *> &viewcells)
1966	{
1967	int hits = 0;
1968	stack<BspRayTraversalData> tStack;
1969
1970	float mint = 0.0f, maxt = 1.0f;
1971
1972	Intersectable::NewMail();
1973
1974	Vector3 entp = origin;
1975	Vector3 extp = termination;
1976
1977	BspNode *node = mRoot;
1978	BspNode *farChild = NULL;
1979
1980	while (1)
1981	{
1982	if (!node->IsLeaf())
1983	{
1984	BspInterior in = dynamic_cast<BspInterior >(node);
1985
1986	Plane3 splitPlane = in->GetPlane();
1987
1988	const int entSide = splitPlane.Side(entp);
1989	const int extSide = splitPlane.Side(extp);
1990
1991	if (entSide < 0)
1992	{
1993	node = in->GetBack();
1994
1995	if(extSide <= 0) // plane does not split ray => no far child
1996	continue;
1997
1998	farChild = in->GetFront(); // plane splits ray
1999
2000	}
2001	else if (entSide > 0)
2002	{
2003	node = in->GetFront();
2004
2005	if (extSide >= 0) // plane does not split ray => no far child
2006	continue;
2007
2008	farChild = in->GetBack(); // plane splits ray
2009	}
2010	else // ray and plane are coincident
2011	{
2012	// WHAT TO DO IN THIS CASE ?
2013	//break;
2014	node = in->GetFront();
2015	continue;
2016	}
2017
2018	// push data for far child
2019	tStack.push(BspRayTraversalData(farChild, extp, maxt));
2020
2021	// find intersection of ray segment with plane
2022	float t;
2023	extp = splitPlane.FindIntersection(origin, extp, &t);
2024	maxt *= t;
2025	}
2026	else
2027	{
2028	// reached leaf => intersection with view cell
2029	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2030
2031	if (!leaf->mViewCell->Mailed())
2032	{
2033	viewcells.push_back(leaf->mViewCell);
2034	leaf->mViewCell->Mail();
2035	hits++;
2036	}
2037
2038	//-- fetch the next far child from the stack
2039	if (tStack.empty())
2040	break;
2041
2042	entp = extp;
2043	mint = maxt; // NOTE: need this?
2044
2045	BspRayTraversalData &s = tStack.top();
2046
2047	node = s.mNode;
2048	extp = s.mExitPoint;
2049	maxt = s.mMaxT;
2050
2051	tStack.pop();
2052	}
2053	}
2054	return hits;
2055	}
2056
2057	bool BspTree::Export(const string filename)
2058	{
2059	Exporter *exporter = Exporter::GetExporter(filename);
2060
2061	if (exporter)
2062	{
2063	exporter->ExportBspTree(*this);
2064	return true;
2065	}
2066
2067	return false;
2068	}
2069
2070	void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
2071	{
2072	stack<BspNode *> nodeStack;
2073	nodeStack.push(mRoot);
2074
2075	ViewCell::NewMail();
2076
2077	while (!nodeStack.empty())
2078	{
2079	BspNode *node = nodeStack.top();
2080	nodeStack.pop();
2081
2082	if (node->IsLeaf())
2083	{
2084	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
2085
2086	if (!viewCell->Mailed())
2087	{
2088	viewCell->Mail();
2089	viewCells.push_back(viewCell);
2090	}
2091	}
2092	else
2093	{
2094	BspInterior interior = dynamic_cast<BspInterior >(node);
2095
2096	nodeStack.push(interior->GetFront());
2097	nodeStack.push(interior->GetBack());
2098	}
2099	}
2100	}
2101
2102
2103	BspTreeStatistics &BspTree::GetStat()
2104	{
2105	return mStat;
2106	}
2107
2108
2109	float BspTree::AccumulatedRayLength(BoundedRayContainer &rays) const
2110	{
2111	float len = 0;
2112
2113	BoundedRayContainer::const_iterator it, it_end = rays.end();
2114
2115	for (it = rays.begin(); it != it_end; ++ it)
2116	{
2117	len += SqrDistance((it)->mRay->Extrap((it)->mMinT),
2118	(it)->mRay->Extrap((it)->mMaxT));
2119	}
2120
2121	return len;
2122	}
2123
2124
2125	int BspTree::SplitRays(const Plane3 &plane,
2126	BoundedRayContainer &rays,
2127	BoundedRayContainer &frontRays,
2128	BoundedRayContainer &backRays)
2129	{
2130	int splits = 0;
2131
2132	while (!rays.empty())
2133	{
2134	BoundedRay *bRay = rays.back();
2135	Ray *ray = bRay->mRay;
2136	float minT = bRay->mMinT;
2137	float maxT = bRay->mMaxT;
2138
2139	rays.pop_back();
2140
2141	Vector3 entP, extP;
2142
2143	const int cf =
2144	ray->ClassifyPlane(plane, minT, maxT, entP, extP);
2145
2146	// set id to ray classification
2147	ray->SetId(cf);
2148
2149	switch (cf)
2150	{
2151	case Ray::COINCIDENT: // TODO: should really discard ray?
2152	frontRays.push_back(bRay);
2153	//DEL_PTR(bRay);
2154	break;
2155	case Ray::BACK:
2156	backRays.push_back(bRay);
2157	break;
2158	case Ray::FRONT:
2159	frontRays.push_back(bRay);
2160	break;
2161	case Ray::FRONT_BACK:
2162	{
2163	// find intersection of ray segment with plane
2164	const float t = plane.FindT(ray->GetLoc(), extP);
2165
2166	const float newT = t * maxT;
2167
2168	frontRays.push_back(new BoundedRay(ray, minT, newT));
2169	backRays.push_back(new BoundedRay(ray, newT, maxT));
2170
2171	DEL_PTR(bRay);
2172	}
2173	break;
2174	case Ray::BACK_FRONT:
2175	{
2176	// find intersection of ray segment with plane
2177	const float t = plane.FindT(ray->GetLoc(), extP);
2178	const float newT = t * bRay->mMaxT;
2179
2180	backRays.push_back(new BoundedRay(ray, minT, newT));
2181	frontRays.push_back(new BoundedRay(ray, newT, maxT));
2182
2183	DEL_PTR(bRay);
2184
2185	++ splits;
2186	}
2187	break;
2188	default:
2189	Debug << "Should not come here 4" << endl;
2190	break;
2191	}
2192	}
2193
2194	return splits;
2195	}
2196
2197	void BspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2198	{
2199	BspNode *lastNode;
2200	do
2201	{
2202	lastNode = n;
2203
2204	// want to get planes defining geometry of this node => don't take
2205	// split plane of node itself
2206	n = n->GetParent();
2207
2208	if (n)
2209	{
2210	BspInterior interior = dynamic_cast<BspInterior >(n);
2211	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
2212
2213	if (interior->GetFront() != lastNode)
2214	halfSpace.ReverseOrientation();
2215
2216	halfSpaces.push_back(halfSpace);
2217	}
2218	}
2219	while (n);
2220	}
2221
2222
2223
2224	void BspTree::ConstructGeometry(ViewCell *vc,
2225	BspNodeGeometry &vcGeom) const
2226	{
2227	ViewCellContainer leaves;
2228	mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
2229
2230	ViewCellContainer::const_iterator it, it_end = leaves.end();
2231
2232	for (it = leaves.begin(); it != it_end; ++ it)
2233	{
2234	BspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
2235	ConstructGeometry(l, vcGeom);
2236	}
2237	}
2238
2239
2240	void BspTree::SetViewCellsManager(ViewCellsManager *vcm)
2241	{
2242	mViewCellsManager = vcm;
2243	}
2244
2245
2246	void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const
2247	{
2248	vector<Plane3> halfSpaces;
2249	ExtractHalfSpaces(n, halfSpaces);
2250
2251	PolygonContainer candidates;
2252
2253	// bounded planes are added to the polygons (reverse polygons
2254	// as they have to be outfacing
2255	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
2256	{
2257	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
2258
2259	if (p->Valid(mEpsilon))
2260	{
2261	candidates.push_back(p->CreateReversePolygon());
2262	DEL_PTR(p);
2263	}
2264	}
2265
2266	// add faces of bounding box (also could be faces of the cell)
2267	for (int i = 0; i < 6; ++ i)
2268	{
2269	VertexContainer vertices;
2270
2271	for (int j = 0; j < 4; ++ j)
2272	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2273
2274	candidates.push_back(new Polygon3(vertices));
2275	}
2276
2277	for (int i = 0; i < (int)candidates.size(); ++ i)
2278	{
2279	// polygon is split by all other planes
2280	for (int j = 0; (j < (int)halfSpaces.size()) && candidates[i]; ++ j)
2281	{
2282	if (i == j) // polygon and plane are coincident
2283	continue;
2284
2285	VertexContainer splitPts;
2286	Polygon3 frontPoly, backPoly;
2287
2288	const int cf = candidates[i]->
2289	ClassifyPlane(halfSpaces[j], mEpsilon);
2290
2291	switch (cf)
2292	{
2293	case Polygon3::SPLIT:
2294	frontPoly = new Polygon3();
2295	backPoly = new Polygon3();
2296
2297	candidates[i]->Split(halfSpaces[j],
2298	*frontPoly,
2299	*backPoly,
2300	mEpsilon);
2301
2302	DEL_PTR(candidates[i]);
2303
2304	if (frontPoly->Valid(mEpsilon))
2305	candidates[i] = frontPoly;
2306	else
2307	DEL_PTR(frontPoly);
2308
2309	DEL_PTR(backPoly);
2310	break;
2311	case Polygon3::BACK_SIDE:
2312	DEL_PTR(candidates[i]);
2313	break;
2314	// just take polygon as it is
2315	case Polygon3::FRONT_SIDE:
2316	case Polygon3::COINCIDENT:
2317	default:
2318	break;
2319	}
2320	}
2321
2322	if (candidates[i])
2323	geom.mPolys.push_back(candidates[i]);
2324	}
2325	}
2326
2327
2328	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
2329
2330
2331	int BspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
2332	const bool onlyUnmailed) const
2333	{
2334	stack<bspNodePair> nodeStack;
2335
2336	BspNodeGeometry nodeGeom;
2337	ConstructGeometry(n, nodeGeom);
2338
2339	// split planes from the root to this node
2340	// needed to verify that we found neighbor leaf
2341	// TODO: really needed?
2342	vector<Plane3> halfSpaces;
2343	ExtractHalfSpaces(n, halfSpaces);
2344
2345
2346	BspNodeGeometry *rgeom = new BspNodeGeometry();
2347	ConstructGeometry(mRoot, *rgeom);
2348
2349	nodeStack.push(bspNodePair(mRoot, rgeom));
2350
2351	while (!nodeStack.empty())
2352	{
2353	BspNode *node = nodeStack.top().first;
2354	BspNodeGeometry *geom = nodeStack.top().second;
2355
2356	nodeStack.pop();
2357
2358	if (node->IsLeaf())
2359	{
2360	// test if this leaf is in valid view space
2361	if (node->TreeValid() &&
2362	(node != n) &&
2363	(!onlyUnmailed \|\| !node->Mailed()))
2364	{
2365	bool isAdjacent = true;
2366
2367	if (1)
2368	{
2369	// test all planes of current node if still adjacent
2370	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2371	{
2372	const int cf =
2373	Polygon3::ClassifyPlane(geom->mPolys,
2374	halfSpaces[i],
2375	mEpsilon);
2376
2377	if (cf == Polygon3::BACK_SIDE)
2378	{
2379	isAdjacent = false;
2380	}
2381	}
2382	}
2383	else
2384	{
2385	// TODO: why is this wrong??
2386	// test all planes of current node if still adjacent
2387	for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i)
2388	{
2389	Polygon3 *poly = nodeGeom.mPolys[i];
2390
2391	const int cf =
2392	Polygon3::ClassifyPlane(geom->mPolys,
2393	poly->GetSupportingPlane(),
2394	mEpsilon);
2395
2396	if (cf == Polygon3::BACK_SIDE)
2397	{
2398	isAdjacent = false;
2399	}
2400	}
2401	}
2402	// neighbor was found
2403	if (isAdjacent)
2404	{
2405	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2406	}
2407	}
2408	}
2409	else
2410	{
2411	BspInterior interior = dynamic_cast<BspInterior >(node);
2412
2413	const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
2414	interior->GetPlane(),
2415	mEpsilon);
2416
2417	BspNode *front = interior->GetFront();
2418	BspNode *back = interior->GetBack();
2419
2420	BspNodeGeometry *fGeom = new BspNodeGeometry();
2421	BspNodeGeometry *bGeom = new BspNodeGeometry();
2422
2423	geom->SplitGeometry(*fGeom,
2424	*bGeom,
2425	interior->GetPlane(),
2426	mBox,
2427	mEpsilon);
2428
2429	if (cf == Polygon3::FRONT_SIDE)
2430	{
2431	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2432	DEL_PTR(bGeom);
2433	}
2434	else
2435	{
2436	if (cf == Polygon3::BACK_SIDE)
2437	{
2438	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2439	DEL_PTR(fGeom);
2440	}
2441	else
2442	{ // random decision
2443	nodeStack.push(bspNodePair(front, fGeom));
2444	nodeStack.push(bspNodePair(back, bGeom));
2445	}
2446	}
2447	}
2448
2449	DEL_PTR(geom);
2450	}
2451
2452	return (int)neighbors.size();
2453	}
2454
2455
2456	BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
2457	{
2458	stack<BspNode *> nodeStack;
2459	nodeStack.push(mRoot);
2460
2461	int mask = rand();
2462
2463	while (!nodeStack.empty())
2464	{
2465	BspNode *node = nodeStack.top();
2466	nodeStack.pop();
2467
2468	if (node->IsLeaf())
2469	{
2470	return dynamic_cast<BspLeaf *>(node);
2471	}
2472	else
2473	{
2474	BspInterior interior = dynamic_cast<BspInterior >(node);
2475	BspNode *next;
2476
2477	BspNodeGeometry geom;
2478	// todo: not very efficient: constructs full cell everytime
2479	ConstructGeometry(interior, geom);
2480
2481	const int cf = Polygon3::ClassifyPlane(geom.mPolys,
2482	halfspace,
2483	mEpsilon);
2484
2485	if (cf == Polygon3::BACK_SIDE)
2486	next = interior->GetFront();
2487	else
2488	if (cf == Polygon3::FRONT_SIDE)
2489	next = interior->GetFront();
2490	else
2491	{
2492	// random decision
2493	if (mask & 1)
2494	next = interior->GetBack();
2495	else
2496	next = interior->GetFront();
2497	mask = mask >> 1;
2498	}
2499
2500	nodeStack.push(next);
2501	}
2502	}
2503
2504	return NULL;
2505	}
2506
2507
2508	BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
2509	{
2510	stack<BspNode *> nodeStack;
2511
2512	nodeStack.push(mRoot);
2513
2514	int mask = rand();
2515
2516	while (!nodeStack.empty())
2517	{
2518	BspNode *node = nodeStack.top();
2519	nodeStack.pop();
2520
2521	if (node->IsLeaf())
2522	{
2523	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2524	return dynamic_cast<BspLeaf *>(node);
2525	}
2526	else
2527	{
2528	BspInterior interior = dynamic_cast<BspInterior >(node);
2529
2530	// random decision
2531	if (mask & 1)
2532	nodeStack.push(interior->GetBack());
2533	else
2534	nodeStack.push(interior->GetFront());
2535
2536	mask = mask >> 1;
2537	}
2538	}
2539
2540	return NULL;
2541	}
2542
2543
2544	void BspTree::AddToPvs(BspLeaf *leaf,
2545	const BoundedRayContainer &rays,
2546	int &sampleContributions,
2547	int &contributingSamples)
2548	{
2549	sampleContributions = 0;
2550	contributingSamples = 0;
2551
2552	BoundedRayContainer::const_iterator it, it_end = rays.end();
2553
2554	ViewCell *vc = leaf->GetViewCell();
2555
2556	// add contributions from samples to the PVS
2557	for (it = rays.begin(); it != it_end; ++ it)
2558	{
2559	int contribution = 0;
2560	Ray ray = (it)->mRay;
2561	float relContribution;
2562	if (!ray->intersections.empty())
2563	contribution += vc->GetPvs().AddSample(ray->intersections[0].mObject,
2564	1.0f,
2565	relContribution);
2566
2567	if (ray->sourceObject.mObject)
2568	contribution += vc->GetPvs().AddSample(ray->sourceObject.mObject,
2569	1.0f,
2570	relContribution);
2571
2572	if (contribution)
2573	{
2574	sampleContributions += contribution;
2575	++ contributingSamples;
2576	}
2577
2578	//if (ray->mFlags & Ray::STORE_BSP_INTERSECTIONS)
2579	// ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
2580	}
2581	}
2582
2583
2584	int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
2585	{
2586	int pvsSize = 0;
2587
2588	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
2589
2590	Intersectable::NewMail();
2591
2592	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2593	{
2594	Ray ray = (rit)->mRay;
2595
2596	if (!ray->intersections.empty())
2597	{
2598	if (!ray->intersections[0].mObject->Mailed())
2599	{
2600	ray->intersections[0].mObject->Mail();
2601	++ pvsSize;
2602	}
2603	}
2604	if (ray->sourceObject.mObject)
2605	{
2606	if (!ray->sourceObject.mObject->Mailed())
2607	{
2608	ray->sourceObject.mObject->Mail();
2609	++ pvsSize;
2610	}
2611	}
2612	}
2613
2614	return pvsSize;
2615	}
2616
2617
2618	float BspTree::GetEpsilon() const
2619	{
2620	return mEpsilon;
2621	}
2622
2623
2624	int BspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
2625	vector<MergeCandidate> &candidates)
2626	{
2627	BspLeaf::NewMail();
2628
2629	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2630
2631	int numCandidates = 0;
2632
2633	// find merge candidates and push them into queue
2634	for (it = leaves.begin(); it != it_end; ++ it)
2635	{
2636	BspLeaf leaf = it;
2637
2638	// the same leaves must not be part of two merge candidates
2639	leaf->Mail();
2640	vector<BspLeaf *> neighbors;
2641	FindNeighbors(leaf, neighbors, true);
2642
2643	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2644
2645	// TODO: test if at least one ray goes from one leaf to the other
2646	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2647	{
2648	if ((*nit)->GetViewCell() != leaf->GetViewCell())
2649	{
2650	MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
2651	candidates.push_back(mc);
2652
2653	++ numCandidates;
2654	if ((numCandidates % 1000) == 0)
2655	{
2656	cout << "collected " << numCandidates << " merge candidates" << endl;
2657	}
2658	}
2659	}
2660	}
2661
2662	Debug << "merge queue: " << (int)candidates.size() << endl;
2663	Debug << "leaves in queue: " << numCandidates << endl;
2664
2665
2666	return (int)leaves.size();
2667	}
2668
2669
2670	int BspTree::CollectMergeCandidates(const VssRayContainer &rays,
2671	vector<MergeCandidate> &candidates)
2672	{
2673	ViewCell::NewMail();
2674	long startTime = GetTime();
2675
2676	map<BspLeaf , vector<BspLeaf> > neighborMap;
2677	ViewCellContainer::const_iterator iit;
2678
2679	int numLeaves = 0;
2680
2681	BspLeaf::NewMail();
2682
2683	for (int i = 0; i < (int)rays.size(); ++ i)
2684	{
2685	VssRay *ray = rays[i];
2686
2687	// traverse leaves stored in the rays and compare and
2688	// merge consecutive leaves (i.e., the neighbors in the tree)
2689	if (ray->mViewCells.size() < 2)
2690	continue;
2691	//TODO viewcellhierarchy
2692	iit = ray->mViewCells.begin();
2693	BspViewCell bspVc = dynamic_cast<BspViewCell >(*(iit ++));
2694	BspLeaf *leaf = bspVc->mLeaf;
2695
2696	// traverse intersections
2697	// consecutive leaves are neighbors => add them to queue
2698	for (; iit != ray->mViewCells.end(); ++ iit)
2699	{
2700	// next pair
2701	BspLeaf *prevLeaf = leaf;
2702	bspVc = dynamic_cast<BspViewCell >(iit);
2703	leaf = bspVc->mLeaf;
2704
2705	// view space not valid or same view cell
2706	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
2707	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
2708	continue;
2709
2710	vector<BspLeaf *> &neighbors = neighborMap[leaf];
2711
2712	bool found = false;
2713
2714	// both leaves inserted in queue already =>
2715	// look if double pair already exists
2716	if (leaf->Mailed() && prevLeaf->Mailed())
2717	{
2718	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2719
2720	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2721	if (*it == prevLeaf)
2722	found = true; // already in queue
2723	}
2724
2725	if (!found)
2726	{
2727	// this pair is not in map yet
2728	// => insert into the neighbor map and the queue
2729	neighbors.push_back(prevLeaf);
2730	neighborMap[prevLeaf].push_back(leaf);
2731
2732	leaf->Mail();
2733	prevLeaf->Mail();
2734
2735	MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
2736
2737	candidates.push_back(mc);
2738
2739	if (((int)candidates.size() % 1000) == 0)
2740	{
2741	cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
2742	}
2743	}
2744	}
2745	}
2746
2747	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2748	Debug << "merge queue: " << (int)candidates.size() << endl;
2749	Debug << "leaves in queue: " << numLeaves << endl;
2750
2751
2752	//-- collect the leaves which haven't been found by ray casting
2753	#if 0
2754	cout << "finding additional merge candidates using geometry" << endl;
2755	vector<BspLeaf *> leaves;
2756	CollectLeaves(leaves, true);
2757	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2758	CollectMergeCandidates(leaves, candidates);
2759	#endif
2760
2761	return numLeaves;
2762	}
2763
2764
2765
2766
2767	/***************************************************************/
2768	/* BspNodeGeometry Implementation */
2769	/***************************************************************/
2770
2771
2772	BspNodeGeometry::BspNodeGeometry(const BspNodeGeometry &rhs)
2773	{
2774	mPolys.reserve(rhs.mPolys.size());
2775
2776	PolygonContainer::const_iterator it, it_end = rhs.mPolys.end();
2777	for (it = rhs.mPolys.begin(); it != it_end; ++ it)
2778	{
2779	Polygon3 poly = it;
2780	mPolys.push_back(new Polygon3(*poly));
2781	}
2782	}
2783
2784
2785	BspNodeGeometry::~BspNodeGeometry()
2786	{
2787	CLEAR_CONTAINER(mPolys);
2788	}
2789
2790
2791	float BspNodeGeometry::GetArea() const
2792	{
2793	return Polygon3::GetArea(mPolys);
2794	}
2795
2796
2797	float BspNodeGeometry::GetVolume() const
2798	{
2799	//-- compute volume using tetrahedralization of the geometry
2800	// and adding the volume of the single tetrahedrons
2801	float volume = 0;
2802	const float f = 1.0f / 6.0f;
2803
2804	PolygonContainer::const_iterator pit, pit_end = mPolys.end();
2805
2806	// note: can take arbitrary point, e.g., the origin. However,
2807	// we rather take the center of mass to prevents precision errors
2808	const Vector3 center = CenterOfMass();
2809
2810	for (pit = mPolys.begin(); pit != pit_end; ++ pit)
2811	{
2812	Polygon3 poly = pit;
2813	const Vector3 v0 = poly->mVertices[0] - center;
2814
2815	for (int i = 1; i < (int)poly->mVertices.size() - 1; ++ i)
2816	{
2817	const Vector3 v1 = poly->mVertices[i] - center;
2818	const Vector3 v2 = poly->mVertices[i + 1] - center;
2819
2820	volume += f * (DotProd(v0, CrossProd(v1, v2)));
2821	}
2822	}
2823
2824	return volume;
2825	}
2826
2827
2828	Vector3 BspNodeGeometry::CenterOfMass() const
2829	{
2830	int n = 0;
2831
2832	Vector3 center(0,0,0);
2833
2834	PolygonContainer::const_iterator pit, pit_end = mPolys.end();
2835
2836	for (pit = mPolys.begin(); pit != pit_end; ++ pit)
2837	{
2838	Polygon3 poly = pit;
2839
2840	VertexContainer::const_iterator vit, vit_end = poly->mVertices.end();
2841
2842	for(vit = poly->mVertices.begin(); vit != vit_end; ++ vit)
2843	{
2844	center += *vit;
2845	++ n;
2846	}
2847	}
2848
2849	return center / (float)n;
2850	}
2851
2852
2853	void BspNodeGeometry::AddToMesh(Mesh &mesh)
2854	{
2855	PolygonContainer::const_iterator it, it_end = mPolys.end();
2856
2857	for (it = mPolys.begin(); it != mPolys.end(); ++ it)
2858	{
2859	(*it)->AddToMesh(mesh);
2860	}
2861	}
2862
2863
2864	void BspNodeGeometry::SplitGeometry(BspNodeGeometry &front,
2865	BspNodeGeometry &back,
2866	const Plane3 &splitPlane,
2867	const AxisAlignedBox3 &box,
2868	const float epsilon) const
2869	{
2870	// get cross section of new polygon
2871	Polygon3 *planePoly = box.CrossSection(splitPlane);
2872
2873	// split polygon with all other polygons
2874	planePoly = SplitPolygon(planePoly, epsilon);
2875
2876	//-- new polygon splits all other polygons
2877	for (int i = 0; i < (int)mPolys.size(); ++ i)
2878	{
2879	/// don't use epsilon here to get exact split planes
2880	const int cf =
2881	mPolys[i]->ClassifyPlane(splitPlane, Limits::Small);
2882
2883	switch (cf)
2884	{
2885	case Polygon3::SPLIT:
2886	{
2887	Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
2888
2889	Polygon3 *frontPoly = new Polygon3();
2890	Polygon3 *backPoly = new Polygon3();
2891
2892	poly->Split(splitPlane,
2893	*frontPoly,
2894	*backPoly,
2895	epsilon);
2896
2897	DEL_PTR(poly);
2898
2899	if (frontPoly->Valid(epsilon))
2900	front.mPolys.push_back(frontPoly);
2901	else
2902	DEL_PTR(frontPoly);
2903
2904	if (backPoly->Valid(epsilon))
2905	back.mPolys.push_back(backPoly);
2906	else
2907	DEL_PTR(backPoly);
2908	}
2909
2910	break;
2911	case Polygon3::BACK_SIDE:
2912	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2913	break;
2914	case Polygon3::FRONT_SIDE:
2915	front.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2916	break;
2917	case Polygon3::COINCIDENT:
2918	//front.mPolys.push_back(CreateReversePolygon(mPolys[i]));
2919	back.mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
2920	break;
2921	default:
2922	break;
2923	}
2924	}
2925
2926	//-- finally add the new polygon to the child node geometries
2927	if (planePoly)
2928	{
2929	// add polygon with normal pointing into positive half space to back cell
2930	back.mPolys.push_back(planePoly);
2931	// add polygon with reverse orientation to front cell
2932	front.mPolys.push_back(planePoly->CreateReversePolygon());
2933	}
2934	}
2935
2936
2937	Polygon3 BspNodeGeometry::SplitPolygon(Polygon3 planePoly,
2938	const float epsilon) const
2939	{
2940	if (!planePoly->Valid(epsilon))
2941	DEL_PTR(planePoly);
2942
2943	// polygon is split by all other planes
2944	for (int i = 0; (i < (int)mPolys.size()) && planePoly; ++ i)
2945	{
2946	Plane3 plane = mPolys[i]->GetSupportingPlane();
2947
2948	/// don't use epsilon here to get exact split planes
2949	const int cf =
2950	planePoly->ClassifyPlane(plane, Limits::Small);
2951
2952	// split new polygon with all previous planes
2953	switch (cf)
2954	{
2955	case Polygon3::SPLIT:
2956	{
2957	Polygon3 *frontPoly = new Polygon3();
2958	Polygon3 *backPoly = new Polygon3();
2959
2960	planePoly->Split(plane,
2961	*frontPoly,
2962	*backPoly,
2963	epsilon);
2964
2965	// don't need anymore
2966	DEL_PTR(planePoly);
2967	DEL_PTR(frontPoly);
2968
2969	// back polygon is belonging to geometry
2970	if (backPoly->Valid(epsilon))
2971	planePoly = backPoly;
2972	else
2973	DEL_PTR(backPoly);
2974	}
2975	break;
2976	case Polygon3::FRONT_SIDE:
2977	DEL_PTR(planePoly);
2978	break;
2979	// polygon is taken as it is
2980	case Polygon3::BACK_SIDE:
2981	case Polygon3::COINCIDENT:
2982	default:
2983	break;
2984	}
2985	}
2986
2987	return planePoly;
2988	}
2989
2990
2991	ViewCell *
2992	BspTree::GetViewCell(const Vector3 &point)
2993	{
2994	if (mRoot == NULL)
2995	return NULL;
2996
2997
2998	stack<BspNode *> nodeStack;
2999	nodeStack.push(mRoot);
3000
3001	ViewCell *viewcell = NULL;
3002
3003	while (!nodeStack.empty()) {
3004	BspNode *node = nodeStack.top();
3005	nodeStack.pop();
3006
3007	if (node->IsLeaf()) {
3008	viewcell = dynamic_cast<BspLeaf *>(node)->mViewCell;
3009	break;
3010	} else {
3011
3012	BspInterior interior = dynamic_cast<BspInterior >(node);
3013
3014	// random decision
3015	if (interior->GetPlane().Side(point) < 0)
3016	nodeStack.push(interior->GetBack());
3017	else
3018	nodeStack.push(interior->GetFront());
3019	}
3020	}
3021
3022	return viewcell;
3023	}
3024
3025	void BspNodeGeometry::IncludeInBox(AxisAlignedBox3 &box)
3026	{
3027	Polygon3::IncludeInBox(mPolys, box);
3028	}

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

Download in other formats: