Context Navigation

VspBspTree.cpp @ 612

Revision 612, 74.2 KB checked in by mattausch, 19 years ago (diff)
really last checkin before svn change

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

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

Context Navigation

source: obsolete/trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 612

Download in other formats: