Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp @ 752

Revision 752, 91.3 KB checked in by mattausch, 18 years ago (diff)
after rendering workshop submissioin x3dparser can use def - use constructs implemented improved evaluation (samples are only stored in leaves, only propagate pvs size)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "Plane3.h"
6	#include "VspBspTree.h"
7	#include "Mesh.h"
8	#include "common.h"
9	#include "ViewCell.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellBsp.h"
17	#include "ViewCellsManager.h"
18	#include "Beam.h"
19
20	#define USE_FIXEDPOINT_T 0
21
22
23	//-- static members
24
25
26	int VspBspTree::sFrontId = 0;
27	int VspBspTree::sBackId = 0;
28	int VspBspTree::sFrontAndBackId = 0;
29
30	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
31
32
33	// pvs penalty can be different from pvs size
34	inline float EvalPvsPenalty(const int pvs,
35	const int lower,
36	const int upper)
37	{
38	// clamp to minmax values
39	if (pvs < lower)
40	return (float)lower;
41	if (pvs > upper)
42	return (float)upper;
43
44	return (float)pvs;
45	}
46
47
48
49
50	/******************************************************************************/
51	/* class VspBspTree implementation */
52	/******************************************************************************/
53
54
55	VspBspTree::VspBspTree():
56	mRoot(NULL),
57	mUseAreaForPvs(false),
58	mCostNormalizer(Limits::Small),
59	mViewCellsManager(NULL),
60	mOutOfBoundsCell(NULL),
61	mStoreRays(false),
62	mRenderCostWeight(0.5),
63	mUseRandomAxis(false),
64	mTimeStamp(1)
65	{
66	bool randomize = false;
67	environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
68	if (randomize)
69	Randomize(); // initialise random generator for heuristics
70
71	//-- termination criteria for autopartition
72	environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
73	environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
74	environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
75	environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
76	environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
77	environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
78	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
79	environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
80	environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
81
82	//-- max cost ratio for early tree termination
83	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
84
85	environment->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
86	environment->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
87
88	// HACK//mTermMinPolygons = 25;
89
90	//-- factors for bsp tree split plane heuristics
91	environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
92	environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
93
94
95	//-- partition criteria
96	environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
97	environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
98	environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
99
100	environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
101	environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
102
103	// if only the driving axis is used for axis aligned split
104	environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
105
106	//-- termination criteria for axis aligned split
107	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
108	mTermMaxRayContriForAxisAligned);
109	environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
110	mTermMinRaysForAxisAligned);
111
112	//environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
113	environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
114
115	environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
116	environment->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
117
118	environment->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics);
119	environment->GetBoolValue("VspBspTree.useSplitCostQueue", mUseSplitCostQueue);
120	environment->GetBoolValue("VspBspTree.simulateOctree", mSimulateOctree);
121	environment->GetBoolValue("VspBspTree.useRandomAxis", mUseRandomAxis);
122	environment->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType);
123
124	environment->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed);
125
126	char subdivisionStatsLog[100];
127	environment->GetStringValue("VspBspTree.subdivisionStats", subdivisionStatsLog);
128	mSubdivisionStats.open(subdivisionStatsLog);
129
130	//-- debug output
131
132	Debug << "***** VSP BSP options ****** " << endl;
133	Debug << "max depth: " << mTermMaxDepth << endl;
134	Debug << "min PVS: " << mTermMinPvs << endl;
135	Debug << "min probabiliy: " << mTermMinProbability << endl;
136	Debug << "min rays: " << mTermMinRays << endl;
137	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
138	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
139	Debug << "miss tolerance: " << mTermMissTolerance << endl;
140	Debug << "max view cells: " << mMaxViewCells << endl;
141	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
142	//Debug << "max plane candidates: " << mMaxRayCandidates << endl;
143	Debug << "randomize: " << randomize << endl;
144
145	Debug << "using area for pvs: " << mUseAreaForPvs << endl;
146	Debug << "render cost weight: " << mRenderCostWeight << endl;
147	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
148	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
149	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
150	Debug << "max memory: " << mMaxMemory << endl;
151	Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl;
152	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
153	Debug << "use split cost queue: " << mUseSplitCostQueue << endl;
154	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
155	Debug << "use random axis: " << mUseRandomAxis << endl;
156	Debug << "priority queue type: " << mNodePriorityQueueType << endl;
157	Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl;
158	Debug << "octree: " << mSimulateOctree << endl;
159
160	Debug << "Split plane strategy: ";
161
162	if (mSplitPlaneStrategy & RANDOM_POLYGON)
163	{
164	Debug << "random polygon ";
165	}
166	if (mSplitPlaneStrategy & AXIS_ALIGNED)
167	{
168	Debug << "axis aligned ";
169	}
170	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
171	{
172	mCostNormalizer += mLeastRaySplitsFactor;
173	Debug << "least ray splits ";
174	}
175	if (mSplitPlaneStrategy & BALANCED_RAYS)
176	{
177	mCostNormalizer += mBalancedRaysFactor;
178	Debug << "balanced rays ";
179	}
180	if (mSplitPlaneStrategy & PVS)
181	{
182	mCostNormalizer += mPvsFactor;
183	Debug << "pvs";
184	}
185
186
187	mSplitCandidates = new vector<SortableEntry>;
188
189	Debug << endl;
190	}
191
192
193	BspViewCell *VspBspTree::GetOutOfBoundsCell()
194	{
195	return mOutOfBoundsCell;
196	}
197
198
199	BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
200	{
201	if (!mOutOfBoundsCell)
202	{
203	mOutOfBoundsCell = new BspViewCell();
204	mOutOfBoundsCell->SetId(-1);
205	mOutOfBoundsCell->SetValid(false);
206	}
207
208	return mOutOfBoundsCell;
209	}
210
211
212	const BspTreeStatistics &VspBspTree::GetStatistics() const
213	{
214	return mBspStats;
215	}
216
217
218	VspBspTree::~VspBspTree()
219	{
220	DEL_PTR(mRoot);
221	DEL_PTR(mSplitCandidates);
222	}
223
224
225	int VspBspTree::AddMeshToPolygons(Mesh *mesh,
226	PolygonContainer &polys,
227	MeshInstance *parent)
228	{
229	FaceContainer::const_iterator fi;
230
231	// copy the face data to polygons
232	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
233	{
234	Polygon3 poly = new Polygon3((fi), mesh);
235
236	if (poly->Valid(mEpsilon))
237	{
238	poly->mParent = parent; // set parent intersectable
239	polys.push_back(poly);
240	}
241	else
242	DEL_PTR(poly);
243	}
244	return (int)mesh->mFaces.size();
245	}
246
247
248	int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
249	PolygonContainer &polys,
250	int maxObjects)
251	{
252	int limit = (maxObjects > 0) ?
253	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
254
255	int polysSize = 0;
256
257	for (int i = 0; i < limit; ++ i)
258	{
259	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
260	{
261	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
262	polysSize +=
263	AddMeshToPolygons(viewCells[i]->GetMesh(),
264	polys,
265	viewCells[i]);
266	}
267	}
268
269	return polysSize;
270	}
271
272
273	int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
274	PolygonContainer &polys,
275	int maxObjects)
276	{
277	int limit = (maxObjects > 0) ?
278	Min((int)objects.size(), maxObjects) : (int)objects.size();
279
280	for (int i = 0; i < limit; ++i)
281	{
282	Intersectable object = objects[i];//it;
283	Mesh *mesh = NULL;
284
285	switch (object->Type()) // extract the meshes
286	{
287	case Intersectable::MESH_INSTANCE:
288	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
289	break;
290	case Intersectable::VIEW_CELL:
291	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
292	break;
293	// TODO: handle transformed mesh instances
294	default:
295	Debug << "intersectable type not supported" << endl;
296	break;
297	}
298
299	if (mesh) // copy the mesh data to polygons
300	{
301	mBox.Include(object->GetBox()); // add to BSP tree aabb
302	AddMeshToPolygons(mesh, polys, NULL);
303	}
304	}
305
306	return (int)polys.size();
307	}
308
309
310	void VspBspTree::Construct(const VssRayContainer &sampleRays,
311	AxisAlignedBox3 *forcedBoundingBox)
312	{
313	mBspStats.nodes = 1;
314	mBox.Initialize(); // initialise BSP tree bounding box
315
316	if (forcedBoundingBox)
317	mBox = *forcedBoundingBox;
318
319	PolygonContainer polys;
320	RayInfoContainer *rays = new RayInfoContainer();
321
322	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
323
324	long startTime = GetTime();
325
326	cout << "Extracting polygons from rays ... ";
327
328	Intersectable::NewMail();
329
330	int numObj = 0;
331
332	//-- extract polygons intersected by the rays
333	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
334	{
335	VssRay ray = rit;
336
337	if ((mBox.IsInside(ray->mTermination) \|\| !forcedBoundingBox) &&
338	ray->mTerminationObject &&
339	!ray->mTerminationObject->Mailed())
340	{
341	ray->mTerminationObject->Mail();
342	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mTerminationObject);
343	AddMeshToPolygons(obj->GetMesh(), polys, obj);
344	++ numObj;
345
346	//-- compute bounding box
347	if (!forcedBoundingBox)
348	mBox.Include(ray->mTermination);
349	}
350
351	if ((mBox.IsInside(ray->mOrigin) \|\| !forcedBoundingBox) &&
352	ray->mOriginObject &&
353	!ray->mOriginObject->Mailed())
354	{
355	ray->mOriginObject->Mail();
356	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mOriginObject);
357	AddMeshToPolygons(obj->GetMesh(), polys, obj);
358	++ numObj;
359
360	//-- compute bounding box
361	if (!forcedBoundingBox)
362	mBox.Include(ray->mOrigin);
363	}
364	}
365
366	Debug << "maximal pvs (i.e., pvs still considered as valid) : "
367	<< mViewCellsManager->GetMaxPvsSize() << endl;
368
369	//-- store rays
370	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
371	{
372	VssRay ray = rit;
373
374	float minT, maxT;
375
376	static Ray hray;
377	hray.Init(*ray);
378
379	// TODO: not very efficient to implictly cast between rays types
380	if (mBox.GetRaySegment(hray, minT, maxT))
381	{
382	float len = ray->Length();
383
384	if (!len)
385	len = Limits::Small;
386
387	rays->push_back(RayInfo(ray, minT / len, maxT / len));
388	}
389	}
390
391	// normalize
392	if (mUseAreaForPvs)
393	mTermMinProbability *= mBox.SurfaceArea();
394	else
395	mTermMinProbability *= mBox.GetVolume();
396
397	// throw out unnecessary polygons
398	PreprocessPolygons(polys);
399
400	mBspStats.polys = (int)polys.size();
401	mGlobalCostMisses = 0;
402
403	cout << "finished" << endl;
404
405	Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
406	<< (int)sampleRays.size() << " rays in "
407	<< TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
408
409	// use split cost priority queue
410	if (mUseSplitCostQueue)
411	{
412	ConstructWithSplitQueue(polys, rays);
413	}
414	else
415	{
416	Construct(polys, rays);
417	}
418
419	// clean up polygons
420	CLEAR_CONTAINER(polys);
421	}
422
423
424	// TODO: return memory usage in MB
425	float VspBspTree::GetMemUsage() const
426	{
427	return (float)
428	(sizeof(VspBspTree) +
429	mBspStats.Leaves() * sizeof(BspLeaf) +
430	mCreatedViewCells * sizeof(BspViewCell) +
431	mBspStats.pvs * sizeof(ObjectPvsData) +
432	mBspStats.Interior() * sizeof(BspInterior) +
433	mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
434	}
435
436
437
438	void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
439	{
440	VspBspTraversalQueue tQueue;
441
442	mRoot = new BspLeaf();
443
444	// constrruct root node geometry
445	BspNodeGeometry *geom = new BspNodeGeometry();
446	ConstructGeometry(mRoot, *geom);
447
448	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
449
450	VspBspTraversalData tData(mRoot,
451	new PolygonContainer(polys),
452	0,
453	rays,
454	ComputePvsSize(*rays),
455	prop,
456	geom);
457
458	EvalPriority(tData);
459
460
461	// first node is kd node, i.e. an axis aligned box
462	if (1)
463	tData.mIsKdNode = true;
464	else
465	tData.mIsKdNode = false;
466
467	tQueue.push(tData);
468
469
470	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
471	mTotalPvsSize = tData.mPvs;
472
473	mSubdivisionStats
474	<< "#ViewCells\n1" << endl
475	<< "#RenderCostDecrease\n0" << endl
476	<< "#TotalRenderCost\n" << mTotalCost << endl
477	<< "#AvgRenderCost\n" << mTotalPvsSize << endl;
478
479	Debug << "total cost: " << mTotalCost << endl;
480
481
482	mBspStats.Start();
483	cout << "Constructing vsp bsp tree ... \n";
484
485	long startTime = GetTime();
486	int nLeaves = 500;
487	int nViewCells = 500;
488
489	// used for intermediate time measurements and progress
490	long interTime = GetTime();
491
492	mOutOfMemory = false;
493
494	mCreatedViewCells = 0;
495
496	while (!tQueue.empty())
497	{
498	tData = tQueue.top();
499	tQueue.pop();
500
501	if (0 && !mOutOfMemory)
502	{
503	float mem = GetMemUsage();
504
505	if (mem > mMaxMemory)
506	{
507	mOutOfMemory = true;
508	Debug << "memory limit reached: " << mem << endl;
509	}
510	}
511
512	// subdivide leaf node
513	BspNode *r = Subdivide(tQueue, tData);
514
515	if (r == mRoot)
516	Debug << "VSP BSP tree construction time spent at root: "
517	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
518
519	if (mBspStats.Leaves() >= nLeaves)
520	{
521	nLeaves += 500;
522
523	cout << "leaves=" << mBspStats.Leaves() << endl;
524	Debug << "needed "
525	<< TimeDiff(interTime, GetTime())*1e-3
526	<< " secs to create 500 view cells" << endl;
527	interTime = GetTime();
528	}
529
530	if (mCreatedViewCells >= nViewCells)
531	{
532	nViewCells += 500;
533
534	cout << "generated " << mCreatedViewCells << " viewcells" << endl;
535	}
536	}
537
538	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
539	cout << "finished\n";
540
541	mBspStats.Stop();
542	}
543
544
545
546	void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys,
547	RayInfoContainer *rays)
548	{
549	VspBspSplitQueue tQueue;
550
551	mRoot = new BspLeaf();
552
553	// constrruct root node geometry
554	BspNodeGeometry *geom = new BspNodeGeometry();
555	ConstructGeometry(mRoot, *geom);
556
557	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
558
559	VspBspTraversalData tData(mRoot,
560	new PolygonContainer(polys),
561	0,
562	rays,
563	ComputePvsSize(*rays),
564	prop,
565	geom);
566
567
568	// compute first split candidate
569	VspBspSplitCandidate splitCandidate;
570	EvalSplitCandidate(tData, splitCandidate);
571
572	tQueue.push(splitCandidate);
573
574	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
575	mTotalPvsSize = tData.mPvs;
576
577	mSubdivisionStats
578	<< "#ViewCells\n1\n" << endl
579	<< "#RenderCostDecrease\n0\n" << endl
580	<< "#SplitCandidateCost\n0\n" << endl
581	<< "#TotalRenderCost\n" << mTotalCost << endl
582	<< "#AvgRenderCost\n" << mTotalPvsSize << endl;
583
584	Debug << "total cost: " << mTotalCost << endl;
585
586
587	mBspStats.Start();
588	cout << "Constructing vsp bsp tree ... \n";
589
590	long startTime = GetTime();
591	int nLeaves = 500;
592	int nViewCells = 500;
593
594	// used for intermediate time measurements and progress
595	long interTime = GetTime();
596
597	mOutOfMemory = false;
598
599	mCreatedViewCells = 0;
600
601	while (!tQueue.empty())
602	{
603	splitCandidate = tQueue.top();
604	tQueue.pop();
605
606	// cost ratio of cost decrease / totalCost
607	float costRatio = splitCandidate.GetCost() / mTotalCost;
608
609	//Debug << "cost ratio: " << costRatio << endl;
610
611	if (costRatio < mTermMinGlobalCostRatio)
612	++ mGlobalCostMisses;
613
614	if (0 && !mOutOfMemory)
615	{
616	float mem = GetMemUsage();
617
618	if (mem > mMaxMemory)
619	{
620	mOutOfMemory = true;
621	Debug << "memory limit reached: " << mem << endl;
622	}
623	}
624
625	// subdivide leaf node
626	BspNode *r = Subdivide(tQueue, splitCandidate);
627
628	if (r == mRoot)
629	Debug << "VSP BSP tree construction time spent at root: "
630	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
631
632	if (mBspStats.Leaves() >= nLeaves)
633	{
634	nLeaves += 500;
635
636	cout << "leaves=" << mBspStats.Leaves() << endl;
637	Debug << "needed "
638	<< TimeDiff(interTime, GetTime())*1e-3
639	<< " secs to create 500 view cells" << endl;
640	interTime = GetTime();
641	}
642
643	if (mCreatedViewCells == nViewCells)
644	{
645	nViewCells += 500;
646
647	cout << "generated " << mCreatedViewCells << " viewcells" << endl;
648	}
649	}
650
651	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
652	cout << "finished\n";
653
654	mBspStats.Stop();
655	}
656
657
658	bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
659	{
660	return
661	(((int)data.mRays->size() <= mTermMinRays) \|\|
662	(data.mPvs <= mTermMinPvs) \|\|
663	(data.mProbability <= mTermMinProbability) \|\|
664	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
665	(data.mDepth >= mTermMaxDepth));
666	}
667
668
669	bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
670	{
671	return
672	(mOutOfMemory
673	\|\| (mBspStats.Leaves() >= mMaxViewCells)
674	\|\| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
675	);
676	}
677
678
679
680	BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
681	VspBspTraversalData &tData)
682	{
683	BspNode *newNode = tData.mNode;
684
685	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
686	{
687	PolygonContainer coincident;
688
689	VspBspTraversalData tFrontData;
690	VspBspTraversalData tBackData;
691
692	// create new interior node and two leaf nodes
693	// or return leaf as it is (if maxCostRatio missed)
694	int splitAxis;
695	bool splitFurther = true;
696	int maxCostMisses = tData.mMaxCostMisses;
697
698	Plane3 splitPlane;
699	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
700
701	// choose next split plane
702	if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
703	{
704	++ maxCostMisses;
705
706	if (maxCostMisses > mTermMissTolerance)
707	{
708	// terminate branch because of max cost
709	++ mBspStats.maxCostNodes;
710	splitFurther = false;
711	}
712	}
713
714	// if this a valid split => subdivide this node further
715	if (splitFurther) //-- continue subdivision
716	{
717	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
718
719	if (splitAxis < 3)
720	++ mBspStats.splits[splitAxis];
721	else
722	++ mBspStats.polySplits;
723
724	tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
725	tFrontData.mAxis = tBackData.mAxis = splitAxis;
726
727	// how often was max cost ratio missed in this branch?
728	tFrontData.mMaxCostMisses = maxCostMisses;
729	tBackData.mMaxCostMisses = maxCostMisses;
730
731	EvalPriority(tFrontData);
732	EvalPriority(tBackData);
733
734	// evaluate subdivision stats
735	if (1)
736	{
737	float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
738	float cBack = (float)tBackData.mPvs * tBackData.mProbability;
739	float cData = (float)tData.mPvs * tData.mProbability;;
740
741	float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
742
743	mTotalCost += costDecr;
744	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
745
746	mSubdivisionStats
747	<< "#ViewCells\n" << mBspStats.Leaves() << endl
748	<< "#RenderCostDecrease\n" << -costDecr << endl
749	<< "#TotalRenderCost\n" << mTotalCost << endl
750	<< "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
751	}
752
753	// push the children on the stack
754	tQueue.push(tFrontData);
755	tQueue.push(tBackData);
756
757	// delete old leaf node
758	DEL_PTR(tData.mNode);
759	}
760	}
761
762	//-- terminate traversal and create new view cell
763	if (newNode->IsLeaf())
764	{
765	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
766	BspViewCell *viewCell = new BspViewCell();
767
768	leaf->SetViewCell(viewCell);
769
770	//-- update pvs
771	int conSamp = 0;
772	float sampCon = 0.0f;
773	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
774
775	// update single pvs parameter
776	viewCell->mPvsSize = viewCell->GetPvs().GetSize();
777	viewCell->mPvsSizeValid = true;
778
779
780	mBspStats.contributingSamples += conSamp;
781	mBspStats.sampleContributions +=(int) sampCon;
782
783	//-- store additional info
784	if (mStoreRays)
785	{
786	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
787	for (it = tData.mRays->begin(); it != it_end; ++ it)
788	{
789	(*it).mRay->Ref();
790	leaf->mVssRays.push_back((*it).mRay);
791	}
792	}
793
794	// should I check here?
795	if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
796	{
797	viewCell->SetValid(false);
798	leaf->SetTreeValid(false);
799	PropagateUpValidity(leaf);
800
801	++ mBspStats.invalidLeaves;
802	}
803
804	viewCell->mLeaf = leaf;
805
806	if (mUseAreaForPvs)
807	viewCell->SetArea(tData.mProbability);
808	else
809	viewCell->SetVolume(tData.mProbability);
810
811	leaf->mProbability = tData.mProbability;
812
813	EvaluateLeafStats(tData);
814	}
815
816	//-- cleanup
817	tData.Clear();
818
819	return newNode;
820	}
821
822	// subdivide using a split plane queue
823	BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
824	VspBspSplitCandidate &splitCandidate)
825	{
826	VspBspTraversalData &tData = splitCandidate.mParentData;
827
828	BspNode *newNode = tData.mNode;
829
830	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
831	{
832	PolygonContainer coincident;
833
834	VspBspTraversalData tFrontData;
835	VspBspTraversalData tBackData;
836
837	//-- continue subdivision
838
839	// create new interior node and two leaf node
840	const Plane3 splitPlane = splitCandidate.mSplitPlane;
841
842	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
843
844	const int splitAxis = splitCandidate.mSplitAxis;
845	const int maxCostMisses = splitCandidate.mMaxCostMisses;
846
847	if (splitAxis < 3)
848	++ mBspStats.splits[splitAxis];
849	else
850	++ mBspStats.polySplits;
851
852	tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
853	tFrontData.mAxis = tBackData.mAxis = splitAxis;
854
855	// how often was max cost ratio missed in this branch?
856	tFrontData.mMaxCostMisses = maxCostMisses;
857	tBackData.mMaxCostMisses = maxCostMisses;
858
859
860	if (1)
861	{
862	float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
863	float cBack = (float)tBackData.mPvs * tBackData.mProbability;
864	float cData = (float)tData.mPvs * tData.mProbability;
865
866
867	float costDecr =
868	(cFront + cBack - cData) / mBox.GetVolume();
869
870	mTotalCost += costDecr;
871	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
872
873	mSubdivisionStats
874	<< "#ViewCells\n" << mBspStats.Leaves() << endl
875	<< "#RenderCostDecrease\n" << -costDecr << endl
876	<< "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl
877	<< "#TotalRenderCost\n" << mTotalCost << endl
878	<< "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
879	}
880
881
882	//-- push the new split candidates on the stack
883	VspBspSplitCandidate frontCandidate;
884	VspBspSplitCandidate backCandidate;
885
886	EvalSplitCandidate(tFrontData, frontCandidate);
887	EvalSplitCandidate(tBackData, backCandidate);
888
889	tQueue.push(frontCandidate);
890	tQueue.push(backCandidate);
891
892	// delete old leaf node
893	DEL_PTR(tData.mNode);
894	}
895
896
897	//-- terminate traversal and create new view cell
898	if (newNode->IsLeaf())
899	{
900	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
901	BspViewCell *viewCell = new BspViewCell();
902
903	leaf->SetViewCell(viewCell);
904
905	//-- update pvs
906	int conSamp = 0;
907	float sampCon = 0.0f;
908	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
909
910	viewCell->mPvsSize = viewCell->GetPvs().GetSize();
911	viewCell->mPvsSizeValid = true;
912
913	mBspStats.contributingSamples += conSamp;
914	mBspStats.sampleContributions +=(int) sampCon;
915
916	//-- store additional info
917	if (mStoreRays)
918	{
919	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
920	for (it = tData.mRays->begin(); it != it_end; ++ it)
921	{
922	(*it).mRay->Ref();
923	leaf->mVssRays.push_back((*it).mRay);
924	}
925	}
926
927	// should I check here?
928	viewCell->mLeaf = leaf;
929
930	if (mUseAreaForPvs)
931	viewCell->SetArea(tData.mProbability);
932	else
933	viewCell->SetVolume(tData.mProbability);
934
935	leaf->mProbability = tData.mProbability;
936
937	EvaluateLeafStats(tData);
938	}
939
940	//-- cleanup
941	tData.Clear();
942
943	return newNode;
944	}
945
946
947	void VspBspTree::EvalPriority(VspBspTraversalData &tData) const
948	{
949	switch (mNodePriorityQueueType)
950	{
951	case BREATH_FIRST:
952	tData.mPriority = (float)-tData.mDepth;
953	break;
954	case DEPTH_FIRST:
955	tData.mPriority = (float)tData.mDepth;
956	break;
957	default:
958	tData.mPriority = tData.mPvs * tData.mProbability;
959	//Debug << "priority: " << tData.mPriority << endl;
960	break;
961	}
962	}
963
964
965	void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData,
966	VspBspSplitCandidate &splitData)
967	{
968	VspBspTraversalData frontData;
969	VspBspTraversalData backData;
970
971	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
972
973	// compute locally best split plane
974	bool success = SelectPlane(splitData.mSplitPlane, leaf, tData,
975	frontData, backData, splitData.mSplitAxis);
976
977	// TODO: reuse
978	DEL_PTR(frontData.mGeometry);
979	DEL_PTR(backData.mGeometry);
980
981	// compute global decrease in render cost
982	splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
983	splitData.mParentData = tData;
984	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
985	}
986
987
988	BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
989	VspBspTraversalData &tData,
990	VspBspTraversalData &frontData,
991	VspBspTraversalData &backData,
992	PolygonContainer &coincident)
993	{
994	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
995
996	//-- the front and back traversal data is filled with the new values
997	frontData.mDepth = tData.mDepth + 1;
998	frontData.mPolygons = new PolygonContainer();
999	frontData.mRays = new RayInfoContainer();
1000
1001	backData.mDepth = tData.mDepth + 1;
1002	backData.mPolygons = new PolygonContainer();
1003	backData.mRays = new RayInfoContainer();
1004
1005
1006	//-- subdivide rays
1007	SplitRays(splitPlane,
1008	*tData.mRays,
1009	*frontData.mRays,
1010	*backData.mRays);
1011
1012
1013	// compute pvs
1014	frontData.mPvs = ComputePvsSize(*frontData.mRays);
1015	backData.mPvs = ComputePvsSize(*backData.mRays);
1016
1017	// split front and back node geometry and compute area
1018
1019	// if geometry was not already computed
1020	if (!frontData.mGeometry && !backData.mGeometry)
1021	{
1022	frontData.mGeometry = new BspNodeGeometry();
1023	backData.mGeometry = new BspNodeGeometry();
1024
1025	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
1026	*backData.mGeometry,
1027	splitPlane,
1028	mBox,
1029	//0.0f);
1030	mEpsilon);
1031
1032	if (mUseAreaForPvs)
1033	{
1034	frontData.mProbability = frontData.mGeometry->GetArea();
1035	backData.mProbability = backData.mGeometry->GetArea();
1036	}
1037	else
1038	{
1039	frontData.mProbability = frontData.mGeometry->GetVolume();
1040	backData.mProbability = tData.mProbability - frontData.mProbability;
1041
1042	// should never come here: wrong volume !!!
1043	if (0)
1044	{
1045	if (frontData.mProbability < -0.00001)
1046	Debug << "fatal error f: " << frontData.mProbability << endl;
1047	if (backData.mProbability < -0.00001)
1048	Debug << "fatal error b: " << backData.mProbability << endl;
1049
1050	// clamp because of precision issues
1051	if (frontData.mProbability < 0) frontData.mProbability = 0;
1052	if (backData.mProbability < 0) backData.mProbability = 0;
1053	}
1054	}
1055	}
1056
1057
1058	// subdivide polygons
1059	SplitPolygons(splitPlane,
1060	*tData.mPolygons,
1061	*frontData.mPolygons,
1062	*backData.mPolygons,
1063	coincident);
1064
1065
1066
1067	///////////////////////////////////////
1068	// subdivide further
1069
1070	// store maximal and minimal depth
1071	if (tData.mDepth > mBspStats.maxDepth)
1072	{
1073	Debug << "max depth increases to " << tData.mDepth << " at " << mBspStats.Leaves() << " leaves" << endl;
1074	mBspStats.maxDepth = tData.mDepth;
1075	}
1076
1077	mBspStats.nodes += 2;
1078
1079
1080	BspInterior *interior = new BspInterior(splitPlane);
1081
1082	#ifdef _DEBUG
1083	Debug << interior << endl;
1084	#endif
1085
1086
1087	//-- create front and back leaf
1088
1089	BspInterior *parent = leaf->GetParent();
1090
1091	// replace a link from node's parent
1092	if (parent)
1093	{
1094	parent->ReplaceChildLink(leaf, interior);
1095	interior->SetParent(parent);
1096	}
1097	else // new root
1098	{
1099	mRoot = interior;
1100	}
1101
1102	// and setup child links
1103	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
1104
1105	frontData.mNode = interior->GetFront();
1106	backData.mNode = interior->GetBack();
1107
1108	interior->mTimeStamp = mTimeStamp ++;
1109
1110
1111	//DEL_PTR(leaf);
1112	return interior;
1113	}
1114
1115
1116	void VspBspTree::AddToPvs(BspLeaf *leaf,
1117	const RayInfoContainer &rays,
1118	float &sampleContributions,
1119	int &contributingSamples)
1120	{
1121	sampleContributions = 0;
1122	contributingSamples = 0;
1123
1124	RayInfoContainer::const_iterator it, it_end = rays.end();
1125
1126	ViewCell *vc = leaf->GetViewCell();
1127
1128	// add contributions from samples to the PVS
1129	for (it = rays.begin(); it != it_end; ++ it)
1130	{
1131	float sc = 0.0f;
1132	VssRay ray = (it).mRay;
1133	bool madeContrib = false;
1134	float contribution;
1135	if (ray->mTerminationObject) {
1136	if (vc->GetPvs().AddSample(ray->mTerminationObject, ray->mPdf, contribution))
1137	madeContrib = true;
1138	sc += contribution;
1139	}
1140
1141	if (ray->mOriginObject) {
1142	if (vc->GetPvs().AddSample(ray->mOriginObject, ray->mPdf, contribution))
1143	madeContrib = true;
1144	sc += contribution;
1145	}
1146
1147	sampleContributions += sc;
1148	if (madeContrib)
1149	++ contributingSamples;
1150
1151	//leaf->mVssRays.push_back(ray);
1152	}
1153	}
1154
1155
1156	void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays,
1157	const int axis,
1158	float minBand,
1159	float maxBand)
1160	{
1161	mSplitCandidates->clear();
1162
1163	int requestedSize = 2 * (int)(rays.size());
1164	// creates a sorted split candidates array
1165	if (mSplitCandidates->capacity() > 500000 &&
1166	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
1167	{
1168	delete mSplitCandidates;
1169	mSplitCandidates = new vector<SortableEntry>;
1170	}
1171
1172	mSplitCandidates->reserve(requestedSize);
1173
1174	float pos;
1175
1176	// float values => don't compare with exact values
1177	if (0)
1178	{
1179	minBand += Limits::Small;
1180	maxBand -= Limits::Small;
1181	}
1182
1183	// insert all queries
1184	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
1185	{
1186	const bool positive = (*ri).mRay->HasPosDir(axis);
1187
1188	pos = (*ri).ExtrapOrigin(axis);
1189	// clamp to min / max band
1190	if (0) ClipValue(pos, minBand, maxBand);
1191
1192	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
1193	pos, (*ri).mRay));
1194
1195	pos = (*ri).ExtrapTermination(axis);
1196	// clamp to min / max band
1197	if (0) ClipValue(pos, minBand, maxBand);
1198
1199	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1200	pos, (*ri).mRay));
1201	}
1202
1203	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
1204	}
1205
1206
1207	float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
1208	const AxisAlignedBox3 &box,
1209	const int pvsSize,
1210	const int axis,
1211	float &position)
1212	{
1213	const float minBox = box.Min(axis);
1214	const float maxBox = box.Max(axis);
1215	const float sizeBox = maxBox - minBox;
1216
1217	const float minBand = minBox + 0.1f * sizeBox;
1218	const float maxBand = minBox + 0.9f * sizeBox;
1219
1220	SortSplitCandidates(rays, axis, minBand, maxBand);
1221
1222	// go through the lists, count the number of objects left and right
1223	// and evaluate the following cost funcion:
1224	// C = ct_div_ci + (qlrl + qrrr)/queries
1225
1226	int pvsl = 0, pvsr = pvsSize;
1227
1228	int pvsBack = pvsl;
1229	int pvsFront = pvsr;
1230
1231	float sum = (float)pvsSize * sizeBox;
1232	float minSum = 1e20f;
1233
1234	// if no border can be found, take mid split
1235	position = minBox + 0.5f * sizeBox;
1236
1237	Intersectable::NewMail();
1238
1239	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1240
1241	// set all object as belonging to the front pvs
1242	for(ri = rays.begin(); ri != ri_end; ++ ri)
1243	{
1244	Intersectable oObject = (ri).mRay->mOriginObject;
1245	Intersectable tObject = (ri).mRay->mTerminationObject;
1246
1247	if (oObject)
1248	{
1249	if (!oObject->Mailed())
1250	{
1251	oObject->Mail();
1252	oObject->mCounter = 1;
1253	}
1254	else
1255	{
1256	++ oObject->mCounter;
1257	}
1258	}
1259	if (tObject)
1260	{
1261	if (!tObject->Mailed())
1262	{
1263	tObject->Mail();
1264	tObject->mCounter = 1;
1265	}
1266	else
1267	{
1268	++ tObject->mCounter;
1269	}
1270	}
1271	}
1272
1273	Intersectable::NewMail();
1274
1275	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
1276
1277	for (ci = mSplitCandidates->begin(); ci < ci_end; ++ ci)
1278	{
1279	VssRay *ray;
1280	ray = (*ci).ray;
1281
1282	Intersectable *oObject = ray->mOriginObject;
1283	Intersectable *tObject = ray->mTerminationObject;
1284
1285
1286	switch ((*ci).type)
1287	{
1288	case SortableEntry::ERayMin:
1289	{
1290	if (oObject && !oObject->Mailed())
1291	{
1292	oObject->Mail();
1293	++ pvsl;
1294	}
1295	if (tObject && !tObject->Mailed())
1296	{
1297	tObject->Mail();
1298	++ pvsl;
1299	}
1300	break;
1301	}
1302	case SortableEntry::ERayMax:
1303	{
1304	if (oObject)
1305	{
1306	if (-- oObject->mCounter == 0)
1307	-- pvsr;
1308	}
1309
1310	if (tObject)
1311	{
1312	if (-- tObject->mCounter == 0)
1313	-- pvsr;
1314	}
1315
1316	break;
1317	}
1318	}
1319
1320	// Note: sufficient to compare size of bounding boxes of front and back side?
1321	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1322	{
1323	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1324
1325	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
1326	// cout<<"cost= "<<sum<<endl;
1327
1328	if (sum < minSum)
1329	{
1330	minSum = sum;
1331	position = (*ci).value;
1332
1333	pvsBack = pvsl;
1334	pvsFront = pvsr;
1335	}
1336	}
1337	}
1338
1339	//Debug << "pos: " << position << " sizebox: " << sizeBox << " pvs: " << pvsSize << endl;
1340
1341	// -- compute cost
1342	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1343	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1344
1345	const float pOverall = sizeBox;
1346
1347	const float pBack = position - minBox;
1348	const float pFront = maxBox - position;
1349
1350	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1351	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1352	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1353
1354	const float oldRenderCost = penaltyOld * pOverall;
1355	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1356
1357	float ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
1358
1359	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1360	// <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
1361
1362	return ratio;
1363	}
1364
1365
1366	float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
1367	const VspBspTraversalData &tData,
1368	int &axis,
1369	BspNodeGeometry **frontGeom,
1370	BspNodeGeometry **backGeom,
1371	float &pFront,
1372	float &pBack,
1373	const bool isKdNode)
1374	{
1375	float nPosition[3];
1376	float nCostRatio[3];
1377	float nProbFront[3];
1378	float nProbBack[3];
1379
1380	BspNodeGeometry *nFrontGeom[3];
1381	BspNodeGeometry *nBackGeom[3];
1382
1383	for (int i = 0; i < 3; ++ i)
1384	{
1385	nFrontGeom[i] = NULL;
1386	nBackGeom[i] = NULL;
1387	}
1388
1389	int bestAxis = -1;
1390
1391	// create bounding box of node geometry
1392	AxisAlignedBox3 box;
1393
1394	//TODO: for kd split geometry already is box => only take minmax vertices
1395	if (1)
1396	{
1397	tData.mGeometry->GetBoundingBox(box);
1398	}
1399	else
1400	{
1401	box.Initialize();
1402	RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
1403
1404	for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
1405	box.Include((*ri).ExtrapTermination());
1406	}
1407
1408	int sAxis = 0;
1409
1410	bool useSpecialAxis = mOnlyDrivingAxis \|\| mUseRandomAxis \|\| mSimulateOctree;
1411
1412	// use some kind of specialised fixed axis
1413	if (mOnlyDrivingAxis)
1414	sAxis = box.Size().DrivingAxis();
1415	else if (mUseRandomAxis)
1416	sAxis = Random(3);
1417	else if (mSimulateOctree)
1418	sAxis = (tData.mAxis + 1) % 3;
1419
1420	//Debug << "use special axis: " << useSpecialAxis << endl;
1421	//Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
1422
1423	for (axis = 0; axis < 3; ++ axis)
1424	{
1425	if (!useSpecialAxis \|\| (axis == sAxis))
1426	{
1427	if (!mUseCostHeuristics)
1428	{
1429	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1430	Vector3 normal(0,0,0); normal[axis] = 1.0f;
1431
1432	// allows faster split because we have axis aligned kd tree boxes
1433	if (0 && isKdNode)
1434	{
1435	nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
1436	box,
1437	axis,
1438	nPosition[axis],
1439	nProbFront[axis],
1440	nProbBack[axis]);
1441
1442	Vector3 pos;
1443
1444	// create back geometry from box
1445	pos = box.Max(); pos[axis] = nPosition[axis];
1446	AxisAlignedBox3 bBox(box.Min(), pos);
1447	PolygonContainer fPolys;
1448	bBox.ExtractPolys(fPolys);
1449
1450	nBackGeom[axis] = new BspNodeGeometry(fPolys);
1451
1452	// create front geometry from box
1453	pos = box.Min(); pos[axis] = nPosition[axis];
1454	AxisAlignedBox3 fBox(pos, box.Max());
1455
1456	PolygonContainer bPolys;
1457	fBox.ExtractPolys(bPolys);
1458	nFrontGeom[axis] = new BspNodeGeometry(bPolys);
1459	}
1460	else
1461	{
1462	nFrontGeom[axis] = new BspNodeGeometry();
1463	nBackGeom[axis] = new BspNodeGeometry();
1464
1465	nCostRatio[axis] =
1466	EvalSplitPlaneCost(Plane3(normal, nPosition[axis]),
1467	tData, nFrontGeom[axis], nBackGeom[axis],
1468	nProbFront[axis], nProbBack[axis]);
1469	}
1470	}
1471	else
1472	{
1473	nCostRatio[axis] =
1474	BestCostRatioHeuristics(*tData.mRays,
1475	box,
1476	tData.mPvs,
1477	axis,
1478	nPosition[axis]);
1479	}
1480
1481	if (bestAxis == -1)
1482	{
1483	bestAxis = axis;
1484	}
1485	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1486	{
1487	bestAxis = axis;
1488	}
1489
1490	}
1491	}
1492
1493	//-- assign values
1494	axis = bestAxis;
1495	pFront = nProbFront[bestAxis];
1496	pBack = nProbBack[bestAxis];
1497
1498	// assign best split nodes geometry
1499	*frontGeom = nFrontGeom[bestAxis];
1500	*backGeom = nBackGeom[bestAxis];
1501
1502	// and delete other geometry
1503	DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
1504	DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
1505
1506	//-- split plane
1507	Vector3 normal(0,0,0); normal[bestAxis] = 1;
1508	plane = Plane3(normal, nPosition[bestAxis]);
1509
1510	return nCostRatio[bestAxis];
1511	}
1512
1513
1514	bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1515	BspLeaf *leaf,
1516	VspBspTraversalData &data,
1517	VspBspTraversalData &frontData,
1518	VspBspTraversalData &backData,
1519	int &splitAxis)
1520	{
1521	// simplest strategy: just take next polygon
1522	if (mSplitPlaneStrategy & RANDOM_POLYGON)
1523	{
1524	if (!data.mPolygons->empty())
1525	{
1526	const int randIdx =
1527	(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1528	Polygon3 nextPoly = (data.mPolygons)[randIdx];
1529
1530	bestPlane = nextPoly->GetSupportingPlane();
1531	return true;
1532	}
1533	}
1534
1535	//-- use heuristics to find appropriate plane
1536
1537	// intermediate plane
1538	Plane3 plane;
1539	float lowestCost = MAX_FLOAT;
1540
1541	// decides if the first few splits should be only axisAligned
1542	const bool onlyAxisAligned =
1543	(mSplitPlaneStrategy & AXIS_ALIGNED) &&
1544	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1545	((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1546
1547	const int limit = onlyAxisAligned ? 0 :
1548	Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1549
1550	float candidateCost;
1551
1552	int maxIdx = (int)data.mPolygons->size();
1553
1554	for (int i = 0; i < limit; ++ i)
1555	{
1556	// the already taken candidates are stored behind maxIdx
1557	// => assure that no index is taken twice
1558	const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1559	Polygon3 poly = (data.mPolygons)[candidateIdx];
1560
1561	// swap candidate to the end to avoid testing same plane
1562	std::swap((data.mPolygons)[maxIdx], (data.mPolygons)[candidateIdx]);
1563	//Polygon3 poly = (data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1564
1565	// evaluate current candidate
1566	BspNodeGeometry fGeom, bGeom;
1567	float fArea, bArea;
1568	plane = poly->GetSupportingPlane();
1569	candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
1570
1571	if (candidateCost < lowestCost)
1572	{
1573	bestPlane = plane;
1574	lowestCost = candidateCost;
1575	}
1576	}
1577
1578	//-- evaluate axis aligned splits
1579	int axis;
1580	BspNodeGeometry fGeom, bGeom;
1581	float pFront, pBack;
1582
1583	candidateCost = 99999999.0f;
1584
1585	// option: axis aligned split only if no polygon available
1586	if (!mUsePolygonSplitIfAvailable \|\| data.mPolygons->empty())
1587	{
1588	candidateCost = SelectAxisAlignedPlane(plane,
1589	data,
1590	axis,
1591	&fGeom,
1592	&bGeom,
1593	pFront,
1594	pBack,
1595	data.mIsKdNode);
1596	}
1597
1598	splitAxis = 3;
1599
1600	if (candidateCost < lowestCost)
1601	{
1602	bestPlane = plane;
1603	lowestCost = candidateCost;
1604	splitAxis = axis;
1605
1606	// assign already computed values
1607	// we can do this because we always save the
1608	// computed values from the axis aligned splits
1609
1610	if (fGeom && bGeom)
1611	{
1612	frontData.mGeometry = fGeom;
1613	backData.mGeometry = bGeom;
1614
1615	frontData.mProbability = pFront;
1616	backData.mProbability = pBack;
1617	}
1618	}
1619	else
1620	{
1621	DEL_PTR(fGeom);
1622	DEL_PTR(bGeom);
1623	}
1624
1625
1626	// if (lowestCost > 10)
1627	// Debug << "warning!! lowest cost: " << lowestCost << endl;
1628
1629	#ifdef _DEBUG
1630	Debug << "plane lowest cost: " << lowestCost << endl;
1631	#endif
1632
1633	if (lowestCost > mTermMaxCostRatio)
1634	{
1635	return false;
1636	}
1637
1638	return true;
1639	}
1640
1641
1642	Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
1643	{
1644	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1645
1646	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1647	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1648
1649	const Vector3 pt = (maxPt + minPt) * 0.5;
1650	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1651
1652	return Plane3(normal, pt);
1653	}
1654
1655
1656	Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
1657	{
1658	Vector3 pt[3];
1659
1660	int idx[3];
1661	int cmaxT = 0;
1662	int cminT = 0;
1663	bool chooseMin = false;
1664
1665	for (int j = 0; j < 3; ++ j)
1666	{
1667	idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
1668
1669	if (idx[j] >= (int)rays.size())
1670	{
1671	idx[j] -= (int)rays.size();
1672
1673	chooseMin = (cminT < 2);
1674	}
1675	else
1676	chooseMin = (cmaxT < 2);
1677
1678	RayInfo rayInf = rays[idx[j]];
1679	pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
1680	}
1681
1682	return Plane3(pt[0], pt[1], pt[2]);
1683	}
1684
1685
1686	Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
1687	{
1688	Vector3 pt[3];
1689
1690	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1691	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1692
1693	// check if rays different
1694	if (idx1 == idx2)
1695	idx2 = (idx2 + 1) % (int)rays.size();
1696
1697	const RayInfo ray1 = rays[idx1];
1698	const RayInfo ray2 = rays[idx2];
1699
1700	// normal vector of the plane parallel to both lines
1701	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1702
1703	// vector from line 1 to line 2
1704	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
1705
1706	// project vector on normal to get distance
1707	const float dist = DotProd(vd, norm);
1708
1709	// point on plane lies halfway between the two planes
1710	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1711
1712	return Plane3(norm, planePt);
1713	}
1714
1715
1716	inline void VspBspTree::GenerateUniqueIdsForPvs()
1717	{
1718	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
1719	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
1720	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
1721	}
1722
1723
1724	float VspBspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
1725	const VspBspTraversalData &data) const
1726	{
1727	float pvsFront = 0;
1728	float pvsBack = 0;
1729	float totalPvs = 0;
1730
1731	// probability that view point lies in back / front node
1732	float pOverall = data.mProbability;
1733	float pFront = 0;
1734	float pBack = 0;
1735
1736
1737	// create unique ids for pvs heuristics
1738	GenerateUniqueIdsForPvs();
1739
1740	for (int i = 0; i < data.mRays->size(); ++ i)
1741	{
1742	RayInfo rayInf = (*data.mRays)[i];
1743
1744	float t;
1745	VssRay *ray = rayInf.mRay;
1746	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1747
1748	// find front and back pvs for origing and termination object
1749	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1750	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1751	}
1752
1753
1754	BspNodeGeometry geomFront;
1755	BspNodeGeometry geomBack;
1756
1757	// construct child geometry with regard to the candidate split plane
1758	data.mGeometry->SplitGeometry(geomFront,
1759	geomBack,
1760	candidatePlane,
1761	mBox,
1762	//0.0f);
1763	mEpsilon);
1764
1765	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1766	{
1767	pFront = geomFront.GetVolume();
1768	pBack = pOverall - pFront;
1769
1770	// something is wrong with the volume
1771	if ((pFront < 0.0) \|\| (pBack < 0.0))
1772	{
1773	Debug << "ERROR in volume:\n"
1774	<< "volume f :" << pFront << " b: " << pBack << " p: " << pOverall
1775	<< ", real volume f: " << pFront << " b: " << geomBack.GetVolume()
1776	<< ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl;
1777	}
1778	}
1779	else
1780	{
1781	pFront = geomFront.GetArea();
1782	pBack = geomBack.GetArea();
1783	}
1784
1785
1786	// -- pvs rendering heuristics
1787	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1788	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1789
1790	// only render cost heuristics or combined with standard deviation
1791	const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
1792	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1793	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1794
1795	const float oldRenderCost = pOverall * penaltyOld;
1796	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1797
1798	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
1799	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
1800
1801
1802	#if 1
1803	// take render cost of node into account
1804	const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
1805	//Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl;
1806	//return 0.5f * renderCostDecrease + 0.5f * normalizedOldRenderCost;
1807	return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
1808	#else
1809	return renderCostDecrease;
1810	#endif
1811	}
1812
1813
1814	float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
1815	const VspBspTraversalData &data,
1816	BspNodeGeometry &geomFront,
1817	BspNodeGeometry &geomBack,
1818	float &pFront,
1819	float &pBack) const
1820	{
1821	float cost = 0;
1822
1823	float totalPvs = 0;
1824	float pvsFront = 0;
1825	float pvsBack = 0;
1826
1827	// probability that view point lies in back / front node
1828	float pOverall = 0;
1829	pFront = 0;
1830	pBack = 0;
1831
1832
1833	int limit;
1834	bool useRand;
1835
1836	// create unique ids for pvs heuristics
1837	GenerateUniqueIdsForPvs();
1838
1839	// choose test rays randomly if too much
1840	if ((int)data.mRays->size() > mMaxTests)
1841	{
1842	useRand = true;
1843	limit = mMaxTests;
1844	}
1845	else
1846	{
1847	useRand = false;
1848	limit = (int)data.mRays->size();
1849	}
1850
1851	for (int i = 0; i < limit; ++ i)
1852	{
1853	const int testIdx = useRand ?
1854	(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
1855	RayInfo rayInf = (*data.mRays)[testIdx];
1856
1857	float t;
1858	VssRay *ray = rayInf.mRay;
1859	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1860
1861	// find front and back pvs for origing and termination object
1862	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1863	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1864	}
1865
1866	// construct child geometry with regard to the candidate split plane
1867	bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront,
1868	geomBack,
1869	candidatePlane,
1870	mBox,
1871	//0.0f);
1872	mEpsilon);
1873
1874	pOverall = data.mProbability;
1875
1876	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1877	{
1878	pFront = geomFront.GetVolume();
1879	pBack = pOverall - pFront;
1880
1881	// HACK: precision issues possible for unbalanced split => don't take this split!
1882	if (1 &&
1883	(!splitSuccessFull \|\| (pFront <= 0) \|\| (pBack <= 0) \|\|
1884	!geomFront.Valid() \|\| !geomBack.Valid()))
1885	{
1886	//Debug << "error f: " << pFront << " b: " << pBack << endl;
1887	// high penalty for this split
1888	return 99999.9f;
1889	}
1890	}
1891	else
1892	{
1893	pFront = geomFront.GetArea();
1894	pBack = geomBack.GetArea();
1895	}
1896
1897
1898	// -- pvs rendering heuristics
1899	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1900	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1901
1902	// only render cost heuristics or combined with standard deviation
1903	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1904	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1905	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1906
1907	const float oldRenderCost = pOverall * penaltyOld;
1908	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1909
1910	float oldCost, newCost;
1911
1912	// only render cost
1913	if (1)
1914	{
1915	oldCost = oldRenderCost;
1916	newCost = newRenderCost;
1917	}
1918	else // also considering standard deviation
1919	{
1920	// standard deviation is difference of back and front pvs
1921	const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
1922
1923	const float newDeviation = 0.5f *
1924	fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
1925
1926	const float oldDeviation = penaltyOld;
1927
1928	newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
1929	oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
1930	}
1931
1932	cost += mPvsFactor * newCost / (oldCost + Limits::Small);
1933
1934
1935	#ifdef _DEBUG
1936	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1937	<< " frontpvs: " << pvsFront << " pFront: " << pFront
1938	<< " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
1939	Debug << "cost: " << cost << endl;
1940	#endif
1941
1942	return cost;
1943	}
1944
1945
1946	int VspBspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
1947	ViewCellContainer &viewCells) const
1948	{
1949	stack<bspNodePair> nodeStack;
1950	BspNodeGeometry *rgeom = new BspNodeGeometry();
1951
1952	ConstructGeometry(mRoot, *rgeom);
1953
1954	nodeStack.push(bspNodePair(mRoot, rgeom));
1955
1956	ViewCell::NewMail();
1957
1958	while (!nodeStack.empty())
1959	{
1960	BspNode *node = nodeStack.top().first;
1961	BspNodeGeometry *geom = nodeStack.top().second;
1962	nodeStack.pop();
1963
1964	const int side = geom->ComputeIntersection(box);
1965
1966	switch (side)
1967	{
1968	case -1:
1969	// node geometry is contained in box
1970	CollectViewCells(node, true, viewCells, true);
1971	break;
1972
1973	case 0:
1974	if (node->IsLeaf())
1975	{
1976	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
1977
1978	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
1979	{
1980	leaf->GetViewCell()->Mail();
1981	viewCells.push_back(leaf->GetViewCell());
1982	}
1983	}
1984	else
1985	{
1986	BspInterior interior = dynamic_cast<BspInterior >(node);
1987
1988	BspNode *first = interior->GetFront();
1989	BspNode *second = interior->GetBack();
1990
1991	BspNodeGeometry *firstGeom = new BspNodeGeometry();
1992	BspNodeGeometry *secondGeom = new BspNodeGeometry();
1993
1994	geom->SplitGeometry(*firstGeom,
1995	*secondGeom,
1996	interior->GetPlane(),
1997	mBox,
1998	//0.0000001f);
1999	mEpsilon);
2000
2001	nodeStack.push(bspNodePair(first, firstGeom));
2002	nodeStack.push(bspNodePair(second, secondGeom));
2003	}
2004
2005	break;
2006	default:
2007	// default: cull
2008	break;
2009	}
2010
2011	DEL_PTR(geom);
2012
2013	}
2014
2015	return (int)viewCells.size();
2016	}
2017
2018
2019	float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
2020	const AxisAlignedBox3 &box,
2021	const int axis,
2022	const float &position,
2023	float &pFront,
2024	float &pBack) const
2025	{
2026	float pvsTotal = 0;
2027	float pvsFront = 0;
2028	float pvsBack = 0;
2029
2030	// create unique ids for pvs heuristics
2031	GenerateUniqueIdsForPvs();
2032
2033	const int pvsSize = data.mPvs;
2034
2035	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
2036
2037	// this is the main ray classification loop!
2038	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
2039	{
2040	//if (!(*rit).mRay->IsActive()) continue;
2041
2042	// determine the side of this ray with respect to the plane
2043	float t;
2044	const int side = (*rit).ComputeRayIntersection(axis, position, t);
2045
2046	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
2047	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
2048	}
2049
2050	//-- pvs heuristics
2051	float pOverall;
2052
2053	//-- compute heurstics
2054	// we take simplified computation for mid split
2055
2056	pOverall = data.mProbability;
2057
2058	if (!mUseAreaForPvs)
2059	{ // volume
2060	pBack = pFront = pOverall * 0.5f;
2061
2062	#if 0
2063	// box length substitute for probability
2064	const float minBox = box.Min(axis);
2065	const float maxBox = box.Max(axis);
2066
2067	pBack = position - minBox;
2068	pFront = maxBox - position;
2069	pOverall = maxBox - minBox;
2070	#endif
2071	}
2072	else //-- area substitute for probability
2073	{
2074	const int axis2 = (axis + 1) % 3;
2075	const int axis3 = (axis + 2) % 3;
2076
2077	const float faceArea =
2078	(box.Max(axis2) - box.Min(axis2)) *
2079	(box.Max(axis3) - box.Min(axis3));
2080
2081	pBack = pFront = pOverall * 0.5f + faceArea;
2082	}
2083
2084	#ifdef _DEBUG
2085	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
2086	Debug << pFront << " " << pBack << " " << pOverall << endl;
2087	#endif
2088
2089
2090	const float newCost = pvsBack * pBack + pvsFront * pFront;
2091	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
2092
2093	return (mCtDivCi + newCost) / oldCost;
2094	}
2095
2096
2097	void VspBspTree::AddObjToPvs(Intersectable *obj,
2098	const int cf,
2099	float &frontPvs,
2100	float &backPvs,
2101	float &totalPvs) const
2102	{
2103	if (!obj)
2104	return;
2105
2106	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
2107
2108	// new object
2109	if ((obj->mMailbox != sFrontId) &&
2110	(obj->mMailbox != sBackId) &&
2111	(obj->mMailbox != sFrontAndBackId))
2112	{
2113	totalPvs += renderCost;
2114	}
2115
2116	// TODO: does this really belong to no pvs?
2117	//if (cf == Ray::COINCIDENT) return;
2118
2119	// object belongs to both PVS
2120	if (cf >= 0)
2121	{
2122	if ((obj->mMailbox != sFrontId) &&
2123	(obj->mMailbox != sFrontAndBackId))
2124	{
2125	frontPvs += renderCost;
2126
2127	if (obj->mMailbox == sBackId)
2128	obj->mMailbox = sFrontAndBackId;
2129	else
2130	obj->mMailbox = sFrontId;
2131	}
2132	}
2133
2134	if (cf <= 0)
2135	{
2136	if ((obj->mMailbox != sBackId) &&
2137	(obj->mMailbox != sFrontAndBackId))
2138	{
2139	backPvs += renderCost;
2140
2141	if (obj->mMailbox == sFrontId)
2142	obj->mMailbox = sFrontAndBackId;
2143	else
2144	obj->mMailbox = sBackId;
2145	}
2146	}
2147	}
2148
2149
2150	void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
2151	const bool onlyUnmailed,
2152	const int maxPvsSize) const
2153	{
2154	stack<BspNode *> nodeStack;
2155	nodeStack.push(mRoot);
2156
2157	while (!nodeStack.empty())
2158	{
2159	BspNode *node = nodeStack.top();
2160	nodeStack.pop();
2161
2162	if (node->IsLeaf())
2163	{
2164	// test if this leaf is in valid view space
2165	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2166	if (leaf->TreeValid() &&
2167	(!onlyUnmailed \|\| !leaf->Mailed()) &&
2168	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
2169	{
2170	leaves.push_back(leaf);
2171	}
2172	}
2173	else
2174	{
2175	BspInterior interior = dynamic_cast<BspInterior >(node);
2176
2177	nodeStack.push(interior->GetBack());
2178	nodeStack.push(interior->GetFront());
2179	}
2180	}
2181	}
2182
2183
2184	AxisAlignedBox3 VspBspTree::GetBoundingBox() const
2185	{
2186	return mBox;
2187	}
2188
2189
2190	BspNode *VspBspTree::GetRoot() const
2191	{
2192	return mRoot;
2193	}
2194
2195
2196	void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
2197	{
2198	// the node became a leaf -> evaluate stats for leafs
2199	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
2200
2201
2202	if (data.mPvs > mBspStats.maxPvs)
2203	{
2204	mBspStats.maxPvs = data.mPvs;
2205	}
2206
2207	mBspStats.pvs += data.mPvs;
2208
2209	if (data.mDepth < mBspStats.minDepth)
2210	{
2211	mBspStats.minDepth = data.mDepth;
2212	}
2213
2214	if (data.mDepth >= mTermMaxDepth)
2215	{
2216	++ mBspStats.maxDepthNodes;
2217	//Debug << "new max depth: " << mBspStats.maxDepthNodes << endl;
2218	}
2219
2220	// accumulate rays to compute rays / leaf
2221	mBspStats.accumRays += (int)data.mRays->size();
2222
2223	if (data.mPvs < mTermMinPvs)
2224	++ mBspStats.minPvsNodes;
2225
2226	if ((int)data.mRays->size() < mTermMinRays)
2227	++ mBspStats.minRaysNodes;
2228
2229	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
2230	++ mBspStats.maxRayContribNodes;
2231
2232	if (data.mProbability <= mTermMinProbability)
2233	++ mBspStats.minProbabilityNodes;
2234
2235	// accumulate depth to compute average depth
2236	mBspStats.accumDepth += data.mDepth;
2237
2238	++ mCreatedViewCells;
2239
2240	#ifdef _DEBUG
2241	Debug << "BSP stats: "
2242	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
2243	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
2244	// << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
2245	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
2246	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
2247	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
2248	#endif
2249	}
2250
2251
2252	int VspBspTree::CastRay(Ray &ray)
2253	{
2254	int hits = 0;
2255
2256	stack<BspRayTraversalData> tQueue;
2257
2258	float maxt, mint;
2259
2260	if (!mBox.GetRaySegment(ray, mint, maxt))
2261	return 0;
2262
2263	Intersectable::NewMail();
2264	ViewCell::NewMail();
2265	Vector3 entp = ray.Extrap(mint);
2266	Vector3 extp = ray.Extrap(maxt);
2267
2268	BspNode *node = mRoot;
2269	BspNode *farChild = NULL;
2270
2271	while (1)
2272	{
2273	if (!node->IsLeaf())
2274	{
2275	BspInterior in = dynamic_cast<BspInterior >(node);
2276
2277	Plane3 splitPlane = in->GetPlane();
2278	const int entSide = splitPlane.Side(entp);
2279	const int extSide = splitPlane.Side(extp);
2280
2281	if (entSide < 0)
2282	{
2283	node = in->GetBack();
2284
2285	if(extSide <= 0) // plane does not split ray => no far child
2286	continue;
2287
2288	farChild = in->GetFront(); // plane splits ray
2289
2290	} else if (entSide > 0)
2291	{
2292	node = in->GetFront();
2293
2294	if (extSide >= 0) // plane does not split ray => no far child
2295	continue;
2296
2297	farChild = in->GetBack(); // plane splits ray
2298	}
2299	else // ray and plane are coincident
2300	{
2301	// WHAT TO DO IN THIS CASE ?
2302	//break;
2303	node = in->GetFront();
2304	continue;
2305	}
2306
2307	// push data for far child
2308	tQueue.push(BspRayTraversalData(farChild, extp, maxt));
2309
2310	// find intersection of ray segment with plane
2311	float t;
2312	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
2313	maxt *= t;
2314
2315	} else // reached leaf => intersection with view cell
2316	{
2317	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2318
2319	if (!leaf->GetViewCell()->Mailed())
2320	{
2321	//ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
2322	leaf->GetViewCell()->Mail();
2323	++ hits;
2324	}
2325
2326	//-- fetch the next far child from the stack
2327	if (tQueue.empty())
2328	break;
2329
2330	entp = extp;
2331	mint = maxt; // NOTE: need this?
2332
2333	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
2334	break;
2335
2336	BspRayTraversalData &s = tQueue.top();
2337
2338	node = s.mNode;
2339	extp = s.mExitPoint;
2340	maxt = s.mMaxT;
2341
2342	tQueue.pop();
2343	}
2344	}
2345
2346	return hits;
2347	}
2348
2349
2350	void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
2351	{
2352	ViewCell::NewMail();
2353
2354	CollectViewCells(mRoot, onlyValid, viewCells, true);
2355	}
2356
2357
2358	void VspBspTree::CollapseViewCells()
2359	{
2360	// TODO
2361	#if HAS_TO_BE_REDONE
2362	stack<BspNode *> nodeStack;
2363
2364	if (!mRoot)
2365	return;
2366
2367	nodeStack.push(mRoot);
2368
2369	while (!nodeStack.empty())
2370	{
2371	BspNode *node = nodeStack.top();
2372	nodeStack.pop();
2373
2374	if (node->IsLeaf())
2375	{
2376	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
2377
2378	if (!viewCell->GetValid())
2379	{
2380	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
2381
2382	ViewCellContainer leaves;
2383	mViewCellsTree->CollectLeaves(viewCell, leaves);
2384
2385	ViewCellContainer::const_iterator it, it_end = leaves.end();
2386
2387	for (it = leaves.begin(); it != it_end; ++ it)
2388	{
2389	BspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
2390	l->SetViewCell(GetOrCreateOutOfBoundsCell());
2391	++ mBspStats.invalidLeaves;
2392	}
2393
2394	// add to unbounded view cell
2395	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
2396	DEL_PTR(viewCell);
2397	}
2398	}
2399	else
2400	{
2401	BspInterior interior = dynamic_cast<BspInterior >(node);
2402
2403	nodeStack.push(interior->GetFront());
2404	nodeStack.push(interior->GetBack());
2405	}
2406	}
2407
2408	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
2409	#endif
2410	}
2411
2412
2413	void VspBspTree::CollectRays(VssRayContainer &rays)
2414	{
2415	vector<BspLeaf *> leaves;
2416
2417	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
2418
2419	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2420	{
2421	BspLeaf leaf = lit;
2422	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2423
2424	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2425	rays.push_back(*rit);
2426	}
2427	}
2428
2429
2430	void VspBspTree::ValidateTree()
2431	{
2432	stack<BspNode *> nodeStack;
2433
2434	if (!mRoot)
2435	return;
2436
2437	nodeStack.push(mRoot);
2438
2439	mBspStats.invalidLeaves = 0;
2440	while (!nodeStack.empty())
2441	{
2442	BspNode *node = nodeStack.top();
2443	nodeStack.pop();
2444
2445	if (node->IsLeaf())
2446	{
2447	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2448
2449	if (!leaf->GetViewCell()->GetValid())
2450	++ mBspStats.invalidLeaves;
2451
2452	// validity flags don't match => repair
2453	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2454	{
2455	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2456	PropagateUpValidity(leaf);
2457	}
2458	}
2459	else
2460	{
2461	BspInterior interior = dynamic_cast<BspInterior >(node);
2462
2463	nodeStack.push(interior->GetFront());
2464	nodeStack.push(interior->GetBack());
2465	}
2466	}
2467
2468	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
2469	}
2470
2471
2472
2473	void VspBspTree::CollectViewCells(BspNode *root,
2474	bool onlyValid,
2475	ViewCellContainer &viewCells,
2476	bool onlyUnmailed) const
2477	{
2478	stack<BspNode *> nodeStack;
2479
2480	if (!root)
2481	return;
2482
2483	nodeStack.push(root);
2484
2485	while (!nodeStack.empty())
2486	{
2487	BspNode *node = nodeStack.top();
2488	nodeStack.pop();
2489
2490	if (node->IsLeaf())
2491	{
2492	if (!onlyValid \|\| node->TreeValid())
2493	{
2494	ViewCell leafVc = dynamic_cast<BspLeaf >(node)->GetViewCell();
2495
2496	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2497
2498	if (!onlyUnmailed \|\| !viewCell->Mailed())
2499	{
2500	viewCell->Mail();
2501	viewCells.push_back(viewCell);
2502	}
2503	}
2504	}
2505	else
2506	{
2507	BspInterior interior = dynamic_cast<BspInterior >(node);
2508
2509	nodeStack.push(interior->GetFront());
2510	nodeStack.push(interior->GetBack());
2511	}
2512	}
2513
2514	}
2515
2516
2517	void VspBspTree::PreprocessPolygons(PolygonContainer &polys)
2518	{
2519	// preprocess: throw out polygons coincident to the view space box (not needed)
2520	PolygonContainer boxPolys;
2521	mBox.ExtractPolys(boxPolys);
2522	vector<Plane3> boxPlanes;
2523
2524	PolygonContainer::iterator pit, pit_end = boxPolys.end();
2525
2526	// extract planes of box
2527	// TODO: can be done more elegantly than first extracting polygons
2528	// and take their planes
2529	for (pit = boxPolys.begin(); pit != pit_end; ++ pit)
2530	{
2531	boxPlanes.push_back((*pit)->GetSupportingPlane());
2532	}
2533
2534	pit_end = polys.end();
2535
2536	for (pit = polys.begin(); pit != pit_end; ++ pit)
2537	{
2538	vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end();
2539
2540	for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit)
2541	{
2542	const int cf = (pit)->ClassifyPlane(bit, mEpsilon);
2543
2544	if (cf == Polygon3::COINCIDENT)
2545	{
2546	DEL_PTR(*pit);
2547	//Debug << "coincident!!" << endl;
2548	}
2549	}
2550	}
2551
2552	// remove deleted entries
2553	for (int i = 0; i < (int)polys.size(); ++ i)
2554	{
2555	while (!polys[i] && (i < (int)polys.size()))
2556	{
2557	swap(polys[i], polys.back());
2558	polys.pop_back();
2559	}
2560	}
2561	}
2562
2563
2564	float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
2565	{
2566	float len = 0;
2567
2568	RayInfoContainer::const_iterator it, it_end = rays.end();
2569
2570	for (it = rays.begin(); it != it_end; ++ it)
2571	len += (*it).SegmentLength();
2572
2573	return len;
2574	}
2575
2576
2577	int VspBspTree::SplitRays(const Plane3 &plane,
2578	RayInfoContainer &rays,
2579	RayInfoContainer &frontRays,
2580	RayInfoContainer &backRays) const
2581	{
2582	int splits = 0;
2583
2584	RayInfoContainer::const_iterator it, it_end = rays.end();
2585
2586	for (it = rays.begin(); it != it_end; ++ it)
2587	{
2588	RayInfo bRay = *it;
2589
2590	VssRay *ray = bRay.mRay;
2591	float t;
2592
2593	// get classification and receive new t
2594	const int cf = bRay.ComputeRayIntersection(plane, t);
2595
2596	switch (cf)
2597	{
2598	case -1:
2599	backRays.push_back(bRay);
2600	break;
2601	case 1:
2602	frontRays.push_back(bRay);
2603	break;
2604	case 0:
2605	{
2606	//-- split ray
2607	// test if start point behind or in front of plane
2608	const int side = plane.Side(bRay.ExtrapOrigin());
2609
2610	if (side <= 0)
2611	{
2612	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2613	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2614	}
2615	else
2616	{
2617	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2618	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2619	}
2620	}
2621	break;
2622	default:
2623	Debug << "Should not come here" << endl;
2624	break;
2625	}
2626	}
2627
2628	return splits;
2629	}
2630
2631
2632	void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2633	{
2634	BspNode *lastNode;
2635
2636	do
2637	{
2638	lastNode = n;
2639
2640	// want to get planes defining geometry of this node => don't take
2641	// split plane of node itself
2642	n = n->GetParent();
2643
2644	if (n)
2645	{
2646	BspInterior interior = dynamic_cast<BspInterior >(n);
2647	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
2648
2649	if (interior->GetBack() != lastNode)
2650	halfSpace.ReverseOrientation();
2651
2652	halfSpaces.push_back(halfSpace);
2653	}
2654	}
2655	while (n);
2656	}
2657
2658
2659	void VspBspTree::ConstructGeometry(BspNode *n,
2660	BspNodeGeometry &geom) const
2661	{
2662	vector<Plane3> halfSpaces;
2663	ExtractHalfSpaces(n, halfSpaces);
2664
2665	PolygonContainer candidatePolys;
2666	vector<Plane3> candidatePlanes;
2667
2668	vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end();
2669
2670	// bounded planes are added to the polygons
2671	for (pit = halfSpaces.begin(); pit != pit_end; ++ pit)
2672	{
2673	Polygon3 p = GetBoundingBox().CrossSection(pit);
2674
2675	if (p->Valid(mEpsilon))
2676	{
2677	candidatePolys.push_back(p);
2678	candidatePlanes.push_back(*pit);
2679	}
2680	}
2681
2682	// add faces of bounding box (also could be faces of the cell)
2683	for (int i = 0; i < 6; ++ i)
2684	{
2685	VertexContainer vertices;
2686
2687	for (int j = 0; j < 4; ++ j)
2688	vertices.push_back(mBox.GetFace(i).mVertices[j]);
2689
2690	Polygon3 *poly = new Polygon3(vertices);
2691
2692	candidatePolys.push_back(poly);
2693	candidatePlanes.push_back(poly->GetSupportingPlane());
2694	}
2695
2696	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2697	{
2698	// polygon is split by all other planes
2699	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
2700	{
2701	if (i == j) // polygon and plane are coincident
2702	continue;
2703
2704	VertexContainer splitPts;
2705	Polygon3 frontPoly, backPoly;
2706
2707	const int cf =
2708	candidatePolys[i]->ClassifyPlane(halfSpaces[j],
2709	mEpsilon);
2710
2711	switch (cf)
2712	{
2713	case Polygon3::SPLIT:
2714	frontPoly = new Polygon3();
2715	backPoly = new Polygon3();
2716
2717	candidatePolys[i]->Split(halfSpaces[j],
2718	*frontPoly,
2719	*backPoly,
2720	mEpsilon);
2721
2722	DEL_PTR(candidatePolys[i]);
2723
2724	if (backPoly->Valid(mEpsilon))
2725	candidatePolys[i] = backPoly;
2726	else
2727	DEL_PTR(backPoly);
2728
2729	// outside, don't need this
2730	DEL_PTR(frontPoly);
2731	break;
2732	// polygon outside of halfspace
2733	case Polygon3::FRONT_SIDE:
2734	DEL_PTR(candidatePolys[i]);
2735	break;
2736	// just take polygon as it is
2737	case Polygon3::BACK_SIDE:
2738	case Polygon3::COINCIDENT:
2739	default:
2740	break;
2741	}
2742	}
2743
2744	if (candidatePolys[i])
2745	{
2746	geom.Add(candidatePolys[i], candidatePlanes[i]);
2747	// geom.mPolys.push_back(candidates[i]);
2748	}
2749	}
2750	}
2751
2752
2753	void VspBspTree::ConstructGeometry(ViewCell *vc,
2754	BspNodeGeometry &vcGeom) const
2755	{
2756	ViewCellContainer leaves;
2757
2758	mViewCellsTree->CollectLeaves(vc, leaves);
2759
2760	ViewCellContainer::const_iterator it, it_end = leaves.end();
2761
2762	for (it = leaves.begin(); it != it_end; ++ it)
2763	{
2764	BspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
2765
2766	ConstructGeometry(l, vcGeom);
2767	}
2768	}
2769
2770
2771	int VspBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
2772	const bool onlyUnmailed) const
2773	{
2774	stack<bspNodePair> nodeStack;
2775
2776	BspNodeGeometry nodeGeom;
2777	ConstructGeometry(n, nodeGeom);
2778	const float eps = 0.01f;
2779
2780	// split planes from the root to this node
2781	// needed to verify that we found neighbor leaf
2782	// TODO: really needed?
2783	vector<Plane3> halfSpaces;
2784	ExtractHalfSpaces(n, halfSpaces);
2785
2786
2787	BspNodeGeometry *rgeom = new BspNodeGeometry();
2788	ConstructGeometry(mRoot, *rgeom);
2789
2790	nodeStack.push(bspNodePair(mRoot, rgeom));
2791
2792	while (!nodeStack.empty())
2793	{
2794	BspNode *node = nodeStack.top().first;
2795	BspNodeGeometry *geom = nodeStack.top().second;
2796
2797	nodeStack.pop();
2798
2799	if (node->IsLeaf())
2800	{
2801	// test if this leaf is in valid view space
2802	if (node->TreeValid() &&
2803	(node != n) &&
2804	(!onlyUnmailed \|\| !node->Mailed()))
2805	{
2806	bool isAdjacent = true;
2807
2808	if (1)
2809	{
2810	// test all planes of current node if still adjacent
2811	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2812	{
2813	const int cf =
2814	Polygon3::ClassifyPlane(geom->GetPolys(),
2815	halfSpaces[i],
2816	eps);
2817
2818	if (cf == Polygon3::FRONT_SIDE)
2819	{
2820	isAdjacent = false;
2821	}
2822	}
2823	}
2824	else
2825	{
2826	// TODO: why is this wrong??
2827	// test all planes of current node if still adjacent
2828	for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
2829	{
2830	Polygon3 *poly = nodeGeom.GetPolys()[i];
2831
2832	const int cf =
2833	Polygon3::ClassifyPlane(geom->GetPolys(),
2834	poly->GetSupportingPlane(),
2835	eps);
2836
2837	if (cf == Polygon3::FRONT_SIDE)
2838	{
2839	isAdjacent = false;
2840	}
2841	}
2842	}
2843	// neighbor was found
2844	if (isAdjacent)
2845	{
2846	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2847	}
2848	}
2849	}
2850	else
2851	{
2852	BspInterior interior = dynamic_cast<BspInterior >(node);
2853
2854	const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
2855	interior->GetPlane(),
2856	eps);
2857
2858	BspNode *front = interior->GetFront();
2859	BspNode *back = interior->GetBack();
2860
2861	BspNodeGeometry *fGeom = new BspNodeGeometry();
2862	BspNodeGeometry *bGeom = new BspNodeGeometry();
2863
2864	geom->SplitGeometry(*fGeom,
2865	*bGeom,
2866	interior->GetPlane(),
2867	mBox,
2868	//0.0000001f);
2869	eps);
2870
2871	if (cf == Polygon3::BACK_SIDE)
2872	{
2873	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2874	DEL_PTR(fGeom);
2875	}
2876	else
2877	{
2878	if (cf == Polygon3::FRONT_SIDE)
2879	{
2880	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2881	DEL_PTR(bGeom);
2882	}
2883	else
2884	{ // random decision
2885	nodeStack.push(bspNodePair(front, fGeom));
2886	nodeStack.push(bspNodePair(back, bGeom));
2887	}
2888	}
2889	}
2890
2891	DEL_PTR(geom);
2892	}
2893
2894	return (int)neighbors.size();
2895	}
2896
2897
2898
2899	int VspBspTree::FindApproximateNeighbors(BspNode *n,
2900	vector<BspLeaf *> &neighbors,
2901	const bool onlyUnmailed) const
2902	{
2903	stack<bspNodePair> nodeStack;
2904
2905	BspNodeGeometry nodeGeom;
2906	ConstructGeometry(n, nodeGeom);
2907
2908	float eps = 0.01f;
2909	// split planes from the root to this node
2910	// needed to verify that we found neighbor leaf
2911	// TODO: really needed?
2912	vector<Plane3> halfSpaces;
2913	ExtractHalfSpaces(n, halfSpaces);
2914
2915
2916	BspNodeGeometry *rgeom = new BspNodeGeometry();
2917	ConstructGeometry(mRoot, *rgeom);
2918
2919	nodeStack.push(bspNodePair(mRoot, rgeom));
2920
2921	while (!nodeStack.empty())
2922	{
2923	BspNode *node = nodeStack.top().first;
2924	BspNodeGeometry *geom = nodeStack.top().second;
2925
2926	nodeStack.pop();
2927
2928	if (node->IsLeaf())
2929	{
2930	// test if this leaf is in valid view space
2931	if (node->TreeValid() &&
2932	(node != n) &&
2933	(!onlyUnmailed \|\| !node->Mailed()))
2934	{
2935	bool isAdjacent = true;
2936
2937	// neighbor was found
2938	if (isAdjacent)
2939	{
2940	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2941	}
2942	}
2943	}
2944	else
2945	{
2946	BspInterior interior = dynamic_cast<BspInterior >(node);
2947
2948	const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
2949	interior->GetPlane(),
2950	eps);
2951
2952	BspNode *front = interior->GetFront();
2953	BspNode *back = interior->GetBack();
2954
2955	BspNodeGeometry *fGeom = new BspNodeGeometry();
2956	BspNodeGeometry *bGeom = new BspNodeGeometry();
2957
2958	geom->SplitGeometry(*fGeom,
2959	*bGeom,
2960	interior->GetPlane(),
2961	mBox,
2962	//0.0000001f);
2963	eps);
2964
2965	if (cf == Polygon3::BACK_SIDE)
2966	{
2967	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2968	DEL_PTR(fGeom);
2969	}
2970	else
2971	{
2972	if (cf == Polygon3::FRONT_SIDE)
2973	{
2974	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2975	DEL_PTR(bGeom);
2976	}
2977	else
2978	{ // random decision
2979	nodeStack.push(bspNodePair(front, fGeom));
2980	nodeStack.push(bspNodePair(back, bGeom));
2981	}
2982	}
2983	}
2984
2985	DEL_PTR(geom);
2986	}
2987
2988	return (int)neighbors.size();
2989	}
2990
2991
2992
2993	BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
2994	{
2995	stack<BspNode *> nodeStack;
2996	nodeStack.push(mRoot);
2997
2998	int mask = rand();
2999
3000	while (!nodeStack.empty())
3001	{
3002	BspNode *node = nodeStack.top();
3003	nodeStack.pop();
3004
3005	if (node->IsLeaf())
3006	{
3007	return dynamic_cast<BspLeaf *>(node);
3008	}
3009	else
3010	{
3011	BspInterior interior = dynamic_cast<BspInterior >(node);
3012	BspNode *next;
3013	BspNodeGeometry geom;
3014
3015	// todo: not very efficient: constructs full cell everytime
3016	ConstructGeometry(interior, geom);
3017
3018	const int cf =
3019	Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
3020
3021	if (cf == Polygon3::BACK_SIDE)
3022	next = interior->GetFront();
3023	else
3024	if (cf == Polygon3::FRONT_SIDE)
3025	next = interior->GetFront();
3026	else
3027	{
3028	// random decision
3029	if (mask & 1)
3030	next = interior->GetBack();
3031	else
3032	next = interior->GetFront();
3033	mask = mask >> 1;
3034	}
3035
3036	nodeStack.push(next);
3037	}
3038	}
3039
3040	return NULL;
3041	}
3042
3043
3044	BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
3045	{
3046	stack<BspNode *> nodeStack;
3047
3048	nodeStack.push(mRoot);
3049
3050	int mask = rand();
3051
3052	while (!nodeStack.empty())
3053	{
3054	BspNode *node = nodeStack.top();
3055	nodeStack.pop();
3056
3057	if (node->IsLeaf())
3058	{
3059	if ( (!onlyUnmailed \|\| !node->Mailed()) )
3060	return dynamic_cast<BspLeaf *>(node);
3061	}
3062	else
3063	{
3064	BspInterior interior = dynamic_cast<BspInterior >(node);
3065
3066	// random decision
3067	if (mask & 1)
3068	nodeStack.push(interior->GetBack());
3069	else
3070	nodeStack.push(interior->GetFront());
3071
3072	mask = mask >> 1;
3073	}
3074	}
3075
3076	return NULL;
3077	}
3078
3079
3080	int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
3081	{
3082	int pvsSize = 0;
3083
3084	RayInfoContainer::const_iterator rit, rit_end = rays.end();
3085
3086	Intersectable::NewMail();
3087
3088	for (rit = rays.begin(); rit != rays.end(); ++ rit)
3089	{
3090	VssRay ray = (rit).mRay;
3091
3092	if (ray->mOriginObject)
3093	{
3094	if (!ray->mOriginObject->Mailed())
3095	{
3096	ray->mOriginObject->Mail();
3097	++ pvsSize;
3098	}
3099	}
3100	if (ray->mTerminationObject)
3101	{
3102	if (!ray->mTerminationObject->Mailed())
3103	{
3104	ray->mTerminationObject->Mail();
3105	++ pvsSize;
3106	}
3107	}
3108	}
3109
3110	return pvsSize;
3111	}
3112
3113
3114	float VspBspTree::GetEpsilon() const
3115	{
3116	return mEpsilon;
3117	}
3118
3119
3120	int VspBspTree::SplitPolygons(const Plane3 &plane,
3121	PolygonContainer &polys,
3122	PolygonContainer &frontPolys,
3123	PolygonContainer &backPolys,
3124	PolygonContainer &coincident) const
3125	{
3126	int splits = 0;
3127
3128	PolygonContainer::const_iterator it, it_end = polys.end();
3129
3130	for (it = polys.begin(); it != polys.end(); ++ it)
3131	{
3132	Polygon3 poly = it;
3133
3134	// classify polygon
3135	const int cf = poly->ClassifyPlane(plane, mEpsilon);
3136
3137	switch (cf)
3138	{
3139	case Polygon3::COINCIDENT:
3140	coincident.push_back(poly);
3141	break;
3142	case Polygon3::FRONT_SIDE:
3143	frontPolys.push_back(poly);
3144	break;
3145	case Polygon3::BACK_SIDE:
3146	backPolys.push_back(poly);
3147	break;
3148	case Polygon3::SPLIT:
3149	backPolys.push_back(poly);
3150	frontPolys.push_back(poly);
3151	++ splits;
3152	break;
3153	default:
3154	Debug << "SHOULD NEVER COME HERE\n";
3155	break;
3156	}
3157	}
3158
3159	return splits;
3160	}
3161
3162
3163	int VspBspTree::CastLineSegment(const Vector3 &origin,
3164	const Vector3 &termination,
3165	vector<ViewCell *> &viewcells)
3166	{
3167	int hits = 0;
3168	stack<BspRayTraversalData> tStack;
3169
3170	float mint = 0.0f, maxt = 1.0f;
3171
3172	Intersectable::NewMail();
3173	ViewCell::NewMail();
3174
3175	Vector3 entp = origin;
3176	Vector3 extp = termination;
3177
3178	BspNode *node = mRoot;
3179	BspNode *farChild = NULL;
3180
3181	float t;
3182	const float thresh = 1e-6f; // matt: change this to adjustable value
3183
3184	while (1)
3185	{
3186	if (!node->IsLeaf())
3187	{
3188	BspInterior in = dynamic_cast<BspInterior >(node);
3189
3190	Plane3 splitPlane = in->GetPlane();
3191
3192	const int entSide = splitPlane.Side(entp, thresh);
3193	const int extSide = splitPlane.Side(extp, thresh);
3194
3195	if (entSide < 0)
3196	{
3197	node = in->GetBack();
3198
3199	// plane does not split ray => no far child
3200	if (extSide <= 0)
3201	continue;
3202
3203	farChild = in->GetFront(); // plane splits ray
3204	}
3205	else if (entSide > 0)
3206	{
3207	node = in->GetFront();
3208
3209	if (extSide >= 0) // plane does not split ray => no far child
3210	continue;
3211
3212	farChild = in->GetBack(); // plane splits ray
3213	}
3214	else // one of the ray end points is on the plane
3215	{ // NOTE: what to do if ray is coincident with plane?
3216	if (extSide < 0)
3217	node = in->GetBack();
3218	else //if (extSide > 0)
3219	node = in->GetFront();
3220	//else break; // coincident => count no intersections
3221
3222	continue; // no far child
3223	}
3224
3225	// push data for far child
3226	tStack.push(BspRayTraversalData(farChild, extp));
3227
3228	// find intersection of ray segment with plane
3229	extp = splitPlane.FindIntersection(origin, extp, &t);
3230	}
3231	else
3232	{
3233	// reached leaf => intersection with view cell
3234	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
3235	ViewCell *viewCell;
3236
3237	if (0)
3238	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3239	else
3240	viewCell = leaf->GetViewCell();
3241
3242	if (!viewCell->Mailed())
3243	{
3244	viewcells.push_back(viewCell);
3245	viewCell->Mail();
3246	++ hits;
3247	}
3248
3249	//-- fetch the next far child from the stack
3250	if (tStack.empty())
3251	break;
3252
3253	entp = extp;
3254
3255	const BspRayTraversalData &s = tStack.top();
3256
3257	node = s.mNode;
3258	extp = s.mExitPoint;
3259
3260	tStack.pop();
3261	}
3262	}
3263
3264	return hits;
3265	}
3266
3267
3268
3269
3270	int VspBspTree::TreeDistance(BspNode n1, BspNode n2) const
3271	{
3272	std::deque<BspNode *> path1;
3273	BspNode *p1 = n1;
3274
3275	// create path from node 1 to root
3276	while (p1)
3277	{
3278	if (p1 == n2) // second node on path
3279	return (int)path1.size();
3280
3281	path1.push_front(p1);
3282	p1 = p1->GetParent();
3283	}
3284
3285	int depth = n2->GetDepth();
3286	int d = depth;
3287
3288	BspNode *p2 = n2;
3289
3290	// compare with same depth
3291	while (1)
3292	{
3293	if ((d < (int)path1.size()) && (p2 == path1[d]))
3294	return (depth - d) + ((int)path1.size() - 1 - d);
3295
3296	-- d;
3297	p2 = p2->GetParent();
3298	}
3299
3300	return 0; // never come here
3301	}
3302
3303
3304	BspNode VspBspTree::CollapseTree(BspNode node, int &collapsed)
3305	{
3306	// TODO
3307	#if HAS_TO_BE_REDONE
3308	if (node->IsLeaf())
3309	return node;
3310
3311	BspInterior interior = dynamic_cast<BspInterior >(node);
3312
3313	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
3314	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
3315
3316	if (front->IsLeaf() && back->IsLeaf())
3317	{
3318	BspLeaf frontLeaf = dynamic_cast<BspLeaf >(front);
3319	BspLeaf backLeaf = dynamic_cast<BspLeaf >(back);
3320
3321	//-- collapse tree
3322	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
3323	{
3324	BspViewCell *vc = frontLeaf->GetViewCell();
3325
3326	BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
3327	leaf->SetTreeValid(frontLeaf->TreeValid());
3328
3329	// replace a link from node's parent
3330	if (leaf->GetParent())
3331	leaf->GetParent()->ReplaceChildLink(node, leaf);
3332	else
3333	mRoot = leaf;
3334
3335	++ collapsed;
3336	delete interior;
3337
3338	return leaf;
3339	}
3340	}
3341	#endif
3342	return node;
3343	}
3344
3345
3346	int VspBspTree::CollapseTree()
3347	{
3348	int collapsed = 0;
3349	//TODO
3350	#if HAS_TO_BE_REDONE
3351	(void)CollapseTree(mRoot, collapsed);
3352
3353	// revalidate leaves
3354	RepairViewCellsLeafLists();
3355	#endif
3356	return collapsed;
3357	}
3358
3359
3360	void VspBspTree::RepairViewCellsLeafLists()
3361	{
3362	// TODO
3363	#if HAS_TO_BE_REDONE
3364	// list not valid anymore => clear
3365	stack<BspNode *> nodeStack;
3366	nodeStack.push(mRoot);
3367
3368	ViewCell::NewMail();
3369
3370	while (!nodeStack.empty())
3371	{
3372	BspNode *node = nodeStack.top();
3373	nodeStack.pop();
3374
3375	if (node->IsLeaf())
3376	{
3377	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
3378
3379	BspViewCell *viewCell = leaf->GetViewCell();
3380
3381	if (!viewCell->Mailed())
3382	{
3383	viewCell->mLeaves.clear();
3384	viewCell->Mail();
3385	}
3386
3387	viewCell->mLeaves.push_back(leaf);
3388
3389	}
3390	else
3391	{
3392	BspInterior interior = dynamic_cast<BspInterior >(node);
3393
3394	nodeStack.push(interior->GetFront());
3395	nodeStack.push(interior->GetBack());
3396	}
3397	}
3398	// TODO
3399	#endif
3400	}
3401
3402
3403	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
3404
3405
3406	int VspBspTree::CastBeam(Beam &beam)
3407	{
3408	stack<bspNodePair> nodeStack;
3409	BspNodeGeometry *rgeom = new BspNodeGeometry();
3410	ConstructGeometry(mRoot, *rgeom);
3411
3412	nodeStack.push(bspNodePair(mRoot, rgeom));
3413
3414	ViewCell::NewMail();
3415
3416	while (!nodeStack.empty())
3417	{
3418	BspNode *node = nodeStack.top().first;
3419	BspNodeGeometry *geom = nodeStack.top().second;
3420	nodeStack.pop();
3421
3422	AxisAlignedBox3 box;
3423	geom->GetBoundingBox(box);
3424
3425	const int side = beam.ComputeIntersection(box);
3426
3427	switch (side)
3428	{
3429	case -1:
3430	CollectViewCells(node, true, beam.mViewCells, true);
3431	break;
3432	case 0:
3433
3434	if (node->IsLeaf())
3435	{
3436	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
3437
3438	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
3439	{
3440	leaf->GetViewCell()->Mail();
3441	beam.mViewCells.push_back(leaf->GetViewCell());
3442	}
3443	}
3444	else
3445	{
3446	BspInterior interior = dynamic_cast<BspInterior >(node);
3447
3448	BspNode *first = interior->GetFront();
3449	BspNode *second = interior->GetBack();
3450
3451	BspNodeGeometry *firstGeom = new BspNodeGeometry();
3452	BspNodeGeometry *secondGeom = new BspNodeGeometry();
3453
3454	geom->SplitGeometry(*firstGeom,
3455	*secondGeom,
3456	interior->GetPlane(),
3457	mBox,
3458	//0.0000001f);
3459	mEpsilon);
3460
3461	// decide on the order of the nodes
3462	if (DotProd(beam.mPlanes[0].mNormal,
3463	interior->GetPlane().mNormal) > 0)
3464	{
3465	swap(first, second);
3466	swap(firstGeom, secondGeom);
3467	}
3468
3469	nodeStack.push(bspNodePair(first, firstGeom));
3470	nodeStack.push(bspNodePair(second, secondGeom));
3471	}
3472
3473	break;
3474	default:
3475	// default: cull
3476	break;
3477	}
3478
3479	DEL_PTR(geom);
3480
3481	}
3482
3483	return (int)beam.mViewCells.size();
3484	}
3485
3486
3487	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
3488	{
3489	mViewCellsManager = vcm;
3490	}
3491
3492
3493	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
3494	vector<MergeCandidate> &candidates)
3495	{
3496	BspLeaf::NewMail();
3497
3498	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
3499
3500	int numCandidates = 0;
3501
3502	// find merge candidates and push them into queue
3503	for (it = leaves.begin(); it != it_end; ++ it)
3504	{
3505	BspLeaf leaf = it;
3506
3507	// the same leaves must not be part of two merge candidates
3508	leaf->Mail();
3509
3510	vector<BspLeaf *> neighbors;
3511
3512	// appoximate neighbor search has slightl relaxed constraints
3513	if (1)
3514	FindNeighbors(leaf, neighbors, true);
3515	else
3516	FindApproximateNeighbors(leaf, neighbors, true);
3517
3518	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
3519
3520	// TODO: test if at least one ray goes from one leaf to the other
3521	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
3522	{
3523	if ((*nit)->GetViewCell() != leaf->GetViewCell())
3524	{
3525	MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
3526
3527	// dont't merge view cells if they are empty and not front and back leaf of the same parent
3528	// in the tree?
3529	if (mEmptyViewCellsMergeAllowed \|\|
3530	!leaf->GetViewCell()->GetPvs().Empty() \|\|
3531	!(*nit)->GetViewCell()->GetPvs().Empty() \|\|
3532	leaf->IsSibling(*nit))
3533	{
3534	candidates.push_back(mc);
3535	}
3536
3537	++ numCandidates;
3538	if ((numCandidates % 1000) == 0)
3539	{
3540	cout << "collected " << numCandidates << " merge candidates" << endl;
3541	}
3542	}
3543	}
3544	}
3545
3546	Debug << "merge queue: " << (int)candidates.size() << endl;
3547	Debug << "leaves in queue: " << numCandidates << endl;
3548
3549
3550	return (int)leaves.size();
3551	}
3552
3553
3554	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays,
3555	vector<MergeCandidate> &candidates)
3556	{
3557	ViewCell::NewMail();
3558	long startTime = GetTime();
3559
3560	map<BspLeaf , vector<BspLeaf> > neighborMap;
3561	ViewCellContainer::const_iterator iit;
3562
3563	int numLeaves = 0;
3564
3565	BspLeaf::NewMail();
3566
3567	for (int i = 0; i < (int)rays.size(); ++ i)
3568	{
3569	VssRay *ray = rays[i];
3570
3571	// traverse leaves stored in the rays and compare and
3572	// merge consecutive leaves (i.e., the neighbors in the tree)
3573	if (ray->mViewCells.size() < 2)
3574	continue;
3575	//TODO viewcellhierarchy
3576	iit = ray->mViewCells.begin();
3577	BspViewCell bspVc = dynamic_cast<BspViewCell >(*(iit ++));
3578	BspLeaf *leaf = bspVc->mLeaf;
3579
3580	// traverse intersections
3581	// consecutive leaves are neighbors => add them to queue
3582	for (; iit != ray->mViewCells.end(); ++ iit)
3583	{
3584	// next pair
3585	BspLeaf *prevLeaf = leaf;
3586	bspVc = dynamic_cast<BspViewCell >(iit);
3587	leaf = bspVc->mLeaf;
3588
3589	// view space not valid or same view cell
3590	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
3591	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
3592	continue;
3593
3594	vector<BspLeaf *> &neighbors = neighborMap[leaf];
3595
3596	bool found = false;
3597
3598	// both leaves inserted in queue already =>
3599	// look if double pair already exists
3600	if (leaf->Mailed() && prevLeaf->Mailed())
3601	{
3602	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
3603
3604	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
3605	if (*it == prevLeaf)
3606	found = true; // already in queue
3607	}
3608
3609	if (!found)
3610	{
3611	// this pair is not in map yet
3612	// => insert into the neighbor map and the queue
3613	neighbors.push_back(prevLeaf);
3614	neighborMap[prevLeaf].push_back(leaf);
3615
3616	leaf->Mail();
3617	prevLeaf->Mail();
3618
3619	MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
3620
3621	candidates.push_back(mc);
3622
3623	if (((int)candidates.size() % 1000) == 0)
3624	{
3625	cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
3626	}
3627	}
3628	}
3629	}
3630
3631	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
3632	Debug << "merge queue: " << (int)candidates.size() << endl;
3633	Debug << "leaves in queue: " << numLeaves << endl;
3634
3635
3636	//-- collect the leaves which haven't been found by ray casting
3637	if (0)
3638	{
3639	cout << "finding additional merge candidates using geometry" << endl;
3640	vector<BspLeaf *> leaves;
3641	CollectLeaves(leaves, true);
3642	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
3643	CollectMergeCandidates(leaves, candidates);
3644	}
3645
3646	return numLeaves;
3647	}
3648
3649
3650
3651
3652	ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
3653	{
3654	if (mRoot == NULL)
3655	return NULL;
3656
3657	stack<BspNode *> nodeStack;
3658	nodeStack.push(mRoot);
3659
3660	ViewCell *viewcell = NULL;
3661
3662	while (!nodeStack.empty()) {
3663	BspNode *node = nodeStack.top();
3664	nodeStack.pop();
3665
3666	if (node->IsLeaf()) {
3667	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
3668	break;
3669	} else {
3670
3671	BspInterior interior = dynamic_cast<BspInterior >(node);
3672
3673	// random decision
3674	if (interior->GetPlane().Side(point) < 0)
3675	nodeStack.push(interior->GetBack());
3676	else
3677	nodeStack.push(interior->GetFront());
3678	}
3679	}
3680
3681	return viewcell;
3682	}
3683
3684
3685	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
3686	{
3687	BspNode *node = mRoot;
3688
3689	while (1)
3690	{
3691	// early exit
3692	if (node->TreeValid())
3693	return true;
3694
3695	if (node->IsLeaf())
3696	return false;
3697
3698	BspInterior in = dynamic_cast<BspInterior >(node);
3699
3700	if (in->GetPlane().Side(viewPoint) <= 0)
3701	{
3702	node = in->GetBack();
3703	}
3704	else
3705	{
3706	node = in->GetFront();
3707	}
3708	}
3709
3710	// should never come here
3711	return false;
3712	}
3713
3714
3715	void VspBspTree::PropagateUpValidity(BspNode *node)
3716	{
3717	const bool isValid = node->TreeValid();
3718
3719	// propagative up invalid flag until only invalid nodes exist over this node
3720	if (!isValid)
3721	{
3722	while (!node->IsRoot() && node->GetParent()->TreeValid())
3723	{
3724	node = node->GetParent();
3725	node->SetTreeValid(false);
3726	}
3727	}
3728	else
3729	{
3730	// propagative up valid flag until one of the subtrees is invalid
3731	while (!node->IsRoot() && !node->TreeValid())
3732	{
3733	node = node->GetParent();
3734	BspInterior interior = dynamic_cast<BspInterior >(node);
3735
3736	// the parent is valid iff both leaves are valid
3737	node->SetTreeValid(interior->GetBack()->TreeValid() &&
3738	interior->GetFront()->TreeValid());
3739	}
3740	}
3741	}
3742
3743
3744	bool VspBspTree::Export(ofstream &stream)
3745	{
3746	ExportNode(mRoot, stream);
3747
3748	return true;
3749	}
3750
3751
3752	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
3753	{
3754	if (node->IsLeaf())
3755	{
3756	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
3757	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3758
3759	int id = -1;
3760	if (viewCell != mOutOfBoundsCell)
3761	id = viewCell->GetId();
3762
3763	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
3764	}
3765	else
3766	{
3767	BspInterior interior = dynamic_cast<BspInterior >(node);
3768
3769	Plane3 plane = interior->GetPlane();
3770	stream << "<Interior plane=\"" << plane.mNormal.x << " "
3771	<< plane.mNormal.y << " " << plane.mNormal.z << " "
3772	<< plane.mD << "\">" << endl;
3773
3774	ExportNode(interior->GetBack(), stream);
3775	ExportNode(interior->GetFront(), stream);
3776
3777	stream << "</Interior>" << endl;
3778	}
3779	}

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

Download in other formats: