Context Navigation

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

Revision 654, 83.9 KB checked in by mattausch, 18 years ago (diff)
removed bug in split queue

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

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

Download in other formats: