Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 1370

Revision 1370, 71.1 KB checked in by mattausch, 18 years ago (diff)
debugged global sorting, worked on object-viewspace subdivision

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "VspTree.h"
8	#include "Mesh.h"
9	#include "common.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 "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "KdTree.h"
19	#include "IntersectableWrapper.h"
20	#include "HierarchyManager.h"
21	#include "BvHierarchy.h"
22	#include "OspTree.h"
23
24
25
26	namespace GtpVisibilityPreprocessor {
27
28
29	#define USE_FIXEDPOINT_T 0
30
31
32	//-- static members
33
34	VspTree *VspTree::VspSubdivisionCandidate::sVspTree = NULL;
35	int VspNode::sMailId = 1;
36
37	// variable for debugging volume contribution for heuristics
38	static float debugVol;
39
40
41	// pvs penalty can be different from pvs size
42	inline static float EvalPvsPenalty(const int pvs,
43	const int lower,
44	const int upper)
45	{
46	// clamp to minmax values
47	if (pvs < lower)
48	{
49	return (float)lower;
50	}
51	else if (pvs > upper)
52	{
53	return (float)upper;
54	}
55	return (float)pvs;
56	}
57
58
59	static bool ViewCellHasMultipleReferences(Intersectable *obj,
60	ViewCell *vc,
61	bool checkOnlyMailed)
62	{
63	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
64	//return false;
65	if (vdata)
66	{
67	// more than one view cell sees this object inside different kd cells
68	if (!checkOnlyMailed \|\| !vdata->Mailed())
69	{
70	if (checkOnlyMailed)
71	vdata->Mail();
72	//Debug << "sumpdf: " << vdata->mSumPdf << endl;
73	if (vdata->mSumPdf > 1.5f)
74	return true;
75	}
76	}
77
78	return false;
79	}
80
81
82	void VspTreeStatistics::Print(ostream &app) const
83	{
84	app << "=========== VspTree statistics ===============\n";
85
86	app << setprecision(4);
87
88	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
89
90	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
91
92	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
93
94	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
95
96	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
97
98	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
99
100	for (int i = 0; i < 3; ++ i)
101	app << splits[i] << " ";
102	app << endl;
103
104	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
105	<< maxDepthNodes * 100 / (double)Leaves() << endl;
106
107	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
108	<< minPvsNodes * 100 / (double)Leaves() << endl;
109
110	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
111	<< minRaysNodes * 100 / (double)Leaves() << endl;
112
113	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
114	<< maxCostNodes * 100 / (double)Leaves() << endl;
115
116	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
117	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
118
119	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
120	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
121
122	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
123
124	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
125
126	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
127
128	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
129
130	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
131	//app << "#N_PVS: " << pvs << endl;
132
133	//app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
134
135	app << "========== END OF VspTree statistics ==========\n";
136	}
137
138
139
140	/******************************************************************/
141	/* class VspNode implementation */
142	/******************************************************************/
143
144
145	VspNode::VspNode():
146	mParent(NULL), mTreeValid(true), mTimeStamp(0)
147	{}
148
149
150	VspNode::VspNode(VspInterior *parent):
151	mParent(parent), mTreeValid(true)
152	{}
153
154
155	bool VspNode::IsRoot() const
156	{
157	return mParent == NULL;
158	}
159
160
161	VspInterior *VspNode::GetParent()
162	{
163	return mParent;
164	}
165
166
167	void VspNode::SetParent(VspInterior *parent)
168	{
169	mParent = parent;
170	}
171
172
173	bool VspNode::IsSibling(VspNode *n) const
174	{
175	return ((this != n) && mParent &&
176	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
177	}
178
179
180	int VspNode::GetDepth() const
181	{
182	int depth = 0;
183	VspNode *p = mParent;
184
185	while (p)
186	{
187	p = p->mParent;
188	++ depth;
189	}
190
191	return depth;
192	}
193
194
195	bool VspNode::TreeValid() const
196	{
197	return mTreeValid;
198	}
199
200
201	void VspNode::SetTreeValid(const bool v)
202	{
203	mTreeValid = v;
204	}
205
206
207	/****************************************************************/
208	/* class VspInterior implementation */
209	/****************************************************************/
210
211
212	VspInterior::VspInterior(const AxisAlignedPlane &plane):
213	mPlane(plane), mFront(NULL), mBack(NULL)
214	{}
215
216
217	VspInterior::~VspInterior()
218	{
219	DEL_PTR(mFront);
220	DEL_PTR(mBack);
221	}
222
223
224	bool VspInterior::IsLeaf() const
225	{
226	return false;
227	}
228
229
230	VspNode *VspInterior::GetBack()
231	{
232	return mBack;
233	}
234
235
236	VspNode *VspInterior::GetFront()
237	{
238	return mFront;
239	}
240
241
242	AxisAlignedPlane VspInterior::GetPlane() const
243	{
244	return mPlane;
245	}
246
247
248	float VspInterior::GetPosition() const
249	{
250	return mPlane.mPosition;
251	}
252
253
254	int VspInterior::GetAxis() const
255	{
256	return mPlane.mAxis;
257	}
258
259
260	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
261	{
262	if (mBack == oldChild)
263	mBack = newChild;
264	else
265	mFront = newChild;
266	}
267
268
269	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
270	{
271	mBack = back;
272	mFront = front;
273	}
274
275
276	AxisAlignedBox3 VspInterior::GetBoundingBox() const
277	{
278	return mBoundingBox;
279	}
280
281
282	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
283	{
284	mBoundingBox = box;
285	}
286
287
288	int VspInterior::Type() const
289	{
290	return Interior;
291	}
292
293
294
295	/****************************************************************/
296	/* class VspLeaf implementation */
297	/****************************************************************/
298
299
300	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL), mSubdivisionCandidate(NULL)
301	{
302	}
303
304
305	VspLeaf::~VspLeaf()
306	{
307	DEL_PTR(mPvs);
308	CLEAR_CONTAINER(mVssRays);
309	}
310
311
312	int VspLeaf::Type() const
313	{
314	return Leaf;
315	}
316
317
318	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
319	mViewCell(viewCell)
320	{
321	}
322
323
324	VspLeaf::VspLeaf(VspInterior *parent):
325	VspNode(parent), mViewCell(NULL), mPvs(NULL)
326	{}
327
328
329
330	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
331	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
332	{
333	}
334
335	ViewCellLeaf *VspLeaf::GetViewCell() const
336	{
337	return mViewCell;
338	}
339
340	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
341	{
342	mViewCell = viewCell;
343	}
344
345
346	bool VspLeaf::IsLeaf() const
347	{
348	return true;
349	}
350
351
352	/*************************************************************************/
353	/* class VspTree implementation */
354	/*************************************************************************/
355
356
357	VspTree::VspTree():
358	mRoot(NULL),
359	mOutOfBoundsCell(NULL),
360	mStoreRays(false),
361	mTimeStamp(1),
362	mHierarchyManager(NULL)
363	{
364	bool randomize = false;
365	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
366	if (randomize)
367	Randomize(); // initialise random generator for heuristics
368
369	//-- termination criteria for autopartition
370	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
371	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
372	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
373	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
374	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
375
376	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
377	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
378
379	//-- max cost ratio for early tree termination
380	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
381
382	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
383	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
384
385	//-- factors for bsp tree split plane heuristics
386	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
387
388	//-- partition criteria
389	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
390	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
391
392	// if only the driving axis is used for axis aligned split
393	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
394
395	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
396	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
397
398	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
399	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
400
401	//Environment::GetSingleton()->GetBoolValue("VspTree.useKdPvsForHeuristics", mUseKdPvsForHeuristics);
402
403	char subdivisionStatsLog[100];
404	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
405	mSubdivisionStats.open(subdivisionStatsLog);
406
407	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
408	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
409
410
411	//-- debug output
412
413	Debug << "***** VSP options ****** " << endl;
414
415	Debug << "max depth: " << mTermMaxDepth << endl;
416	Debug << "min PVS: " << mTermMinPvs << endl;
417	Debug << "min probabiliy: " << mTermMinProbability << endl;
418	Debug << "min rays: " << mTermMinRays << endl;
419	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
420	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
421	Debug << "miss tolerance: " << mTermMissTolerance << endl;
422	Debug << "max view cells: " << mMaxViewCells << endl;
423	Debug << "randomize: " << randomize << endl;
424
425	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
426	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
427	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
428	Debug << "max memory: " << mMaxMemory << endl;
429	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
430	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
431	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
432
433	Debug << "circulating axis: " << mCirculatingAxis << endl;
434	Debug << "minband: " << mMinBand << endl;
435	Debug << "maxband: " << mMaxBand << endl;
436
437	mLocalSubdivisionCandidates = new vector<SortableEntry>;
438
439	Debug << endl;
440	}
441
442
443	VspViewCell *VspTree::GetOutOfBoundsCell()
444	{
445	return mOutOfBoundsCell;
446	}
447
448
449	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
450	{
451	if (!mOutOfBoundsCell)
452	{
453	mOutOfBoundsCell = new VspViewCell();
454	mOutOfBoundsCell->SetId(-1);
455	mOutOfBoundsCell->SetValid(false);
456	}
457
458	return mOutOfBoundsCell;
459	}
460
461
462	const VspTreeStatistics &VspTree::GetStatistics() const
463	{
464	return mVspStats;
465	}
466
467
468	VspTree::~VspTree()
469	{
470	DEL_PTR(mRoot);
471	DEL_PTR(mLocalSubdivisionCandidates);
472	}
473
474
475	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
476	AxisAlignedBox3 *forcedBoundingBox)
477	{
478	if (forcedBoundingBox)
479	{
480	mBoundingBox = *forcedBoundingBox;
481	}
482	else // compute vsp tree bounding box
483	{
484	mBoundingBox.Initialize();
485	VssRayContainer::const_iterator rit, rit_end = rays.end();
486
487	//-- compute bounding box
488	for (rit = rays.begin(); rit != rit_end; ++ rit)
489	{
490	VssRay ray = rit;
491
492	// compute bounding box of view space
493	mBoundingBox.Include(ray->GetTermination());
494	mBoundingBox.Include(ray->GetOrigin());
495	}
496	}
497	}
498
499
500	void VspTree::AddSubdivisionStats(const int viewCells,
501	const float renderCostDecr,
502	const float totalRenderCost,
503	const float avgRenderCost)
504	{
505	mSubdivisionStats
506	<< "#ViewCells\n" << viewCells << endl
507	<< "#RenderCostDecrease\n" << renderCostDecr << endl
508	<< "#TotalRenderCost\n" << totalRenderCost << endl
509	<< "#AvgRenderCost\n" << avgRenderCost << endl;
510	}
511
512
513	// TODO: return memory usage in MB
514	float VspTree::GetMemUsage() const
515	{
516	return (float)
517	(sizeof(VspTree) +
518	mVspStats.Leaves() * sizeof(VspLeaf) +
519	mCreatedViewCells * sizeof(VspViewCell) +
520	mVspStats.pvs * sizeof(PvsData) +
521	mVspStats.Interior() * sizeof(VspInterior) +
522	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
523	}
524
525
526	inline bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
527	{
528	const bool localTerminationCriteriaMet = (0
529	\|\| ((int)data.mRays->size() <= mTermMinRays)
530	\|\| (data.mPvs <= mTermMinPvs)
531	\|\| (data.mProbability <= mTermMinProbability)
532	\|\| (data.GetAvgRayContribution() > mTermMaxRayContribution)
533	\|\| (data.mDepth >= mTermMaxDepth)
534	);
535
536	if (1 && localTerminationCriteriaMet)
537	{
538	Debug << "******local termination *******" << endl;
539	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
540	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
541	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
542	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
543	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
544	}
545
546	return localTerminationCriteriaMet;
547	}
548
549
550	inline bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
551	{
552	const bool terminationCriteriaMet = (0
553	// \|\| mOutOfMemory
554	\|\| (mVspStats.Leaves() >= mMaxViewCells)
555	//\|\| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
556	);
557
558	if (0 && terminationCriteriaMet)
559	{
560	Debug << "******* terminationCriteriaMet *******" << endl;
561	Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
562	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
563	}
564	return terminationCriteriaMet;
565	}
566
567
568	void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
569	{
570	//-- create new view cell
571	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
572
573	VspViewCell *viewCell = new VspViewCell();
574	leaf->SetViewCell(viewCell);
575
576	int conSamp = 0;
577	float sampCon = 0.0f;
578
579	if (updatePvs)
580	{
581	//-- update pvs of view cell
582	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
583
584	// update scalar pvs size value
585	ObjectPvs &pvs = viewCell->GetPvs();
586	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
587
588	mVspStats.contributingSamples += conSamp;
589	mVspStats.sampleContributions += (int)sampCon;
590	}
591
592
593	//-- store additional info
594	if (mStoreRays)
595	{
596	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
597
598	for (it = tData.mRays->begin(); it != it_end; ++ it)
599	{
600	(*it).mRay->Ref();
601	leaf->mVssRays.push_back((*it).mRay);
602	}
603	}
604
605	// set view cell values
606	viewCell->mLeaf = leaf;
607
608	viewCell->SetVolume(tData.mProbability);
609	leaf->mProbability = tData.mProbability;
610	}
611
612
613	void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
614	{
615	const float costDecr = sc.GetRenderCostDecrease();
616
617	AddSubdivisionStats(mVspStats.Leaves(),
618	costDecr,
619	mTotalCost,
620	(float)mTotalPvsSize / (float)mVspStats.Leaves());
621	}
622
623
624	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
625	SubdivisionCandidate *splitCandidate,
626	const bool globalCriteriaMet)
627	{
628	// todo remove dynamic cast
629	VspSubdivisionCandidate *sc =
630	dynamic_cast<VspSubdivisionCandidate *>(splitCandidate);
631
632	VspTraversalData &tData = sc->mParentData;
633	VspNode *newNode = tData.mNode;
634
635	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
636	{
637	//-- continue subdivision
638	VspTraversalData tFrontData;
639	VspTraversalData tBackData;
640
641	// create new interior node and two leaf node
642	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
643	const int maxCostMisses = sc->mMaxCostMisses;
644
645	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
646
647	// how often was max cost ratio missed in this branch?
648	tFrontData.mMaxCostMisses = maxCostMisses;
649	tBackData.mMaxCostMisses = maxCostMisses;
650
651	mTotalCost -= sc->GetRenderCostDecrease();
652	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
653
654	// subdivision statistics
655	if (1) EvalSubdivisionStats(*sc);
656
657	//-- evaluate new split candidates for global greedy cost heuristics
658
659	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
660	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
661
662	EvalSubdivisionCandidate(*frontCandidate);
663	EvalSubdivisionCandidate(*backCandidate);
664
665	// cross reference
666	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
667	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
668
669	tQueue.Push(frontCandidate);
670	tQueue.Push(backCandidate);
671
672	// delete old leaf node
673	//DEL_PTR(tData.mNode);
674	}
675
676	if (newNode->IsLeaf()) // subdivision terminated
677	{
678	// view cell is created during subdivision
679	//CreateViewCell(tData);
680
681	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
682	ViewCell *viewCell = leaf->GetViewCell();
683
684	int conSamp = 0;
685	float sampCon = 0.0f;
686
687	#if 0
688	//-- store pvs optained from rays
689	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
690
691	// update scalar pvs size value
692	ObjectPvs &pvs = viewCell->GetPvs();
693	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
694
695	mVspStats.contributingSamples += conSamp;
696	mVspStats.sampleContributions += (int)sampCon;
697	#endif
698	//-- store additional info
699	if (mStoreRays)
700	{
701	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
702	for (it = tData.mRays->begin(); it != it_end; ++ it)
703	{
704	(*it).mRay->Ref();
705	leaf->mVssRays.push_back((*it).mRay);
706	}
707	}
708
709	// finally evaluate statistics for this leaf
710	EvaluateLeafStats(tData);
711	// detach subdivision candidate: this leaf is no candidate for
712	// splitting anymore
713	tData.mNode->SetSubdivisionCandidate(NULL);
714	// detach node so it won't get deleted
715	tData.mNode = NULL;
716	}
717
718	return newNode;
719	}
720
721
722	void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate)
723	{
724	float frontProb;
725	float backProb;
726
727	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
728
729	// compute locally best split plane
730	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
731	splitCandidate.mSplitPlane,
732	frontProb,
733	backProb);
734
735	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
736
737	// max cost threshold violated?
738	splitCandidate.mMaxCostMisses = maxCostRatioViolated ?
739	splitCandidate.mParentData.mMaxCostMisses + 1:
740	splitCandidate.mParentData.mMaxCostMisses;
741
742	float oldRenderCost;
743
744	// compute global decrease in render cost
745	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
746	splitCandidate.mParentData,
747	oldRenderCost);
748
749	splitCandidate.SetRenderCostDecrease(renderCostDecr);
750
751	#if 0
752	const float priority = (float)-splitCandidate.mParentData.mDepth;
753	#else
754	// take render cost of node into account
755	// otherwise danger of being stuck in a local minimum!!
756	const float factor = mRenderCostDecreaseWeight;
757	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
758	#endif
759
760	splitCandidate.SetPriority(priority);
761	}
762
763
764	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
765	VspTraversalData &tData,
766	VspTraversalData &frontData,
767	VspTraversalData &backData)
768	{
769	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
770
771	//-- the front and back traversal data is filled with the new values
772
773	frontData.mDepth = tData.mDepth + 1;
774	backData.mDepth = tData.mDepth + 1;
775
776	frontData.mRays = new RayInfoContainer();
777	backData.mRays = new RayInfoContainer();
778
779	//-- subdivide rays
780	SplitRays(splitPlane,
781	*tData.mRays,
782	*frontData.mRays,
783	*backData.mRays);
784
785	//-- compute pvs
786
787	frontData.mPvs = EvalPvsSize(*frontData.mRays);
788	backData.mPvs = EvalPvsSize(*backData.mRays);
789
790	Debug << "f pvs: " << frontData.mPvs << " b pvs: " << backData.mPvs << " pvs " << tData.mPvs << endl;
791
792	// split front and back node geometry and compute area
793	tData.mBoundingBox.Split(splitPlane.mAxis,
794	splitPlane.mPosition,
795	frontData.mBoundingBox,
796	backData.mBoundingBox);
797
798	frontData.mProbability = frontData.mBoundingBox.GetVolume();
799	backData.mProbability = tData.mProbability - frontData.mProbability;
800
801
802	///////////////////////////////////////////
803	// subdivide further
804
805	// store maximal and minimal depth
806	if (tData.mDepth > mVspStats.maxDepth)
807	{
808	Debug << "max depth increases to " << tData.mDepth
809	<< " at " << mVspStats.Leaves() << " leaves" << endl;
810	mVspStats.maxDepth = tData.mDepth;
811	}
812
813	// two more leaves
814	mVspStats.nodes += 2;
815
816	VspInterior *interior = new VspInterior(splitPlane);
817
818
819	//-- create front and back leaf
820
821	VspInterior *parent = leaf->GetParent();
822
823	// replace a link from node's parent
824	if (parent)
825	{
826	parent->ReplaceChildLink(leaf, interior);
827	interior->SetParent(parent);
828
829	// remove "parent" view cell from pvs of all objects (traverse trough rays)
830	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
831	}
832	else // new root
833	{
834	mRoot = interior;
835	}
836
837	VspLeaf *frontLeaf = new VspLeaf(interior);
838	VspLeaf *backLeaf = new VspLeaf(interior);
839
840	// and setup child links
841	interior->SetupChildLinks(frontLeaf, backLeaf);
842
843	// add bounding box
844	interior->SetBoundingBox(tData.mBoundingBox);
845
846	// set front and back leaf
847	frontData.mNode = frontLeaf;
848	backData.mNode = backLeaf;
849
850	// explicitely create front and back view cell
851	CreateViewCell(frontData, false);
852	CreateViewCell(backData, false);
853
854
855	#if WORK_WITH_VIEWCELL_PVS
856	// create front and back view cell
857	// add front and back view cell to "Potentially Visbilie View Cells"
858	// of the objects in front and back pvs
859
860	AddViewCellReferences(frontLeaf->GetViewCell());
861	AddViewCellReferences(backLeaf->GetViewCell());
862	#endif
863
864	interior->mTimeStamp = mTimeStamp ++;
865
866	return interior;
867	}
868
869
870	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
871	{
872	KdLeaf::NewMail();
873
874	// remove the parents from the object pvss
875	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
876
877	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
878	{
879	Intersectable object = (oit).first;
880	// HACK: make sure that the view cell is removed from the pvs
881	const float high_contri = 9999999;
882
883	// remove reference count of view cells
884	object->mViewCellPvs.RemoveSample(parent, high_contri);
885	}
886	}
887
888
889	void VspTree::AddViewCellReferences(ViewCell *vc) const
890	{
891	KdLeaf::NewMail();
892
893	// Add front view cell to the object pvsss
894	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
895
896	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
897	{
898	Intersectable object = (oit).first;
899
900	// increase reference count of view cells
901	object->mViewCellPvs.AddSample(vc, 1);
902	}
903	}
904
905
906	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
907	const RayInfoContainer &rays,
908	float &sampleContributions,
909	int &contributingSamples)
910	{
911	sampleContributions = 0;
912	contributingSamples = 0;
913
914	RayInfoContainer::const_iterator it, it_end = rays.end();
915
916	ViewCellLeaf *vc = leaf->GetViewCell();
917
918	// add contributions from samples to the PVS
919	for (it = rays.begin(); it != it_end; ++ it)
920	{
921	float sc = 0.0f;
922	VssRay ray = (it).mRay;
923
924	bool madeContrib = false;
925	float contribution;
926
927	Intersectable *obj = ray->mTerminationObject;
928
929	if (obj)
930	{
931	madeContrib =
932	mViewCellsManager->AddSampleToPvs(
933	obj,
934	ray->mTermination,
935	vc,
936	ray->mPdf,
937	contribution);
938
939	sc += contribution;
940	}
941
942	obj = ray->mOriginObject;
943
944	if (obj)
945	{
946	madeContrib =
947	mViewCellsManager->AddSampleToPvs(
948	obj,
949	ray->mOrigin,
950	vc,
951	ray->mPdf,
952	contribution);
953
954	sc += contribution;
955	}
956
957	if (madeContrib)
958	{
959	++ contributingSamples;
960	}
961
962	// store rays for visualization
963	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
964	}
965	}
966
967
968	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
969	const int axis,
970	float minBand,
971	float maxBand)
972	{
973	mLocalSubdivisionCandidates->clear();
974
975	const int requestedSize = 2 * (int)(rays.size());
976
977	// creates a sorted split candidates array
978	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
979	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
980	{
981	delete mLocalSubdivisionCandidates;
982	mLocalSubdivisionCandidates = new vector<SortableEntry>;
983	}
984
985	mLocalSubdivisionCandidates->reserve(requestedSize);
986
987	float pos;
988	RayInfoContainer::const_iterator rit, rit_end = rays.end();
989
990	//-- insert all queries
991	for (rit = rays.begin(); rit != rit_end; ++ rit)
992	{
993	const bool positive = (*rit).mRay->HasPosDir(axis);
994	const bool delayMinEvent = false;
995
996	// origin point
997	pos = (*rit).ExtrapOrigin(axis);
998	const int oType = positive ? SortableEntry::ERayMin : SortableEntry::ERayMax;
999
1000	if (delayMinEvent && oType == SortableEntry::ERayMin)
1001	pos += mEpsilon; // for walls
1002
1003	mLocalSubdivisionCandidates->push_back(SortableEntry(oType, pos, (*rit).mRay));
1004
1005	// termination point
1006	pos = (*rit).ExtrapTermination(axis);
1007	const int tType = positive ? SortableEntry::ERayMax : SortableEntry::ERayMin;
1008
1009	if (delayMinEvent && tType == SortableEntry::ERayMin)
1010	pos += mEpsilon; // for walls
1011
1012	mLocalSubdivisionCandidates->push_back(SortableEntry(tType, pos, (*rit).mRay));
1013	}
1014
1015	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1016	}
1017
1018
1019	int VspTree::PrepareHeuristics(KdLeaf *leaf)
1020	{
1021	int pvsSize = 0;
1022
1023	if (!leaf->Mailed())
1024	{
1025	leaf->Mail();
1026	leaf->mCounter = 1;
1027	// add objects without the objects which are in several kd leaves
1028	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1029	}
1030	else
1031	{
1032	++ leaf->mCounter;
1033	}
1034
1035	//-- the objects belonging to several leaves must be handled seperately
1036	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1037
1038	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1039	{
1040	Intersectable object = oit;
1041
1042	if (!object->Mailed())
1043	{
1044	object->Mail();
1045	object->mCounter = 1;
1046
1047	++ pvsSize;
1048	}
1049	else
1050	{
1051	++ object->mCounter;
1052	}
1053	}
1054
1055	return pvsSize;
1056	}
1057
1058
1059	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1060	{
1061	Intersectable::NewMail();
1062	KdNode::NewMail();
1063	BvhLeaf::NewMail();
1064
1065	int pvsSize = 0;
1066
1067	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1068
1069	// set all kd nodes / objects as belonging to the front pvs
1070	for (ri = rays.begin(); ri != ri_end; ++ ri)
1071	{
1072	VssRay ray = (ri).mRay;
1073
1074	pvsSize += PrepareHeuristics(*ray, true);
1075	pvsSize += PrepareHeuristics(*ray, false);
1076	}
1077
1078	return pvsSize;
1079	}
1080
1081
1082	int VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1083	{
1084	int pvs = 0;
1085
1086	// leaf falls out of right pvs
1087	if (-- leaf->mCounter == 0)
1088	{
1089	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1090	}
1091
1092	//-- separately handle objects which are in several kd leaves
1093
1094	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1095
1096	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1097	{
1098	Intersectable object = oit;
1099
1100	if (-- object->mCounter == 0)
1101	{
1102	++ pvs;
1103	}
1104	}
1105
1106	return pvs;
1107	}
1108
1109
1110	int VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1111	{
1112	if (leaf->Mailed())
1113	return 0;
1114
1115	leaf->Mail();
1116
1117	// add objects without those which are part of several kd leaves
1118	int pvs = ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1119
1120	// separately handle objects which are part of several kd leaves
1121	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1122
1123	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1124	{
1125	Intersectable object = oit;
1126
1127	// object not previously in pvs
1128	if (!object->Mailed())
1129	{
1130	object->Mail();
1131	++ pvs;
1132	}
1133	}
1134
1135	return pvs;
1136	}
1137
1138
1139	void VspTree::EvalHeuristics(const SortableEntry &ci,
1140	int &pvsLeft,
1141	int &pvsRight) const
1142	{
1143	VssRay *ray = ci.ray;
1144
1145	// eval changes in pvs causes by min event
1146	if (ci.type == SortableEntry::ERayMin)
1147	{
1148	pvsLeft += EvalMinEventContribution(*ray, true);
1149	pvsLeft += EvalMinEventContribution(*ray, false);
1150	}
1151	else // eval changes in pvs causes by max event
1152	{
1153	pvsRight -= EvalMaxEventContribution(*ray, true);
1154	pvsRight -= EvalMaxEventContribution(*ray, false);
1155	}
1156	}
1157
1158
1159	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1160	const AxisAlignedBox3 &box,
1161	const int axis,
1162	float &position)
1163	{
1164	// get subset of rays
1165	RayInfoContainer usedRays;
1166
1167	if (mMaxTests < (int)tData.mRays->size())
1168	{
1169	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
1170	}
1171	else
1172	{
1173	usedRays = *tData.mRays;
1174	}
1175
1176	const float minBox = box.Min(axis);
1177	const float maxBox = box.Max(axis);
1178
1179	const float sizeBox = maxBox - minBox;
1180
1181	const float minBand = minBox + mMinBand * sizeBox;
1182	const float maxBand = minBox + mMaxBand * sizeBox;
1183
1184	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1185
1186	// prepare the sweep
1187	// note: returns pvs size => no need t give pvs size as function parameter
1188	const int pvsSize = PrepareHeuristics(usedRays);
1189
1190	// go through the lists, count the number of objects left and right
1191	// and evaluate the following cost funcion:
1192	// C = ct_div_ci + (qlrl + qrrr)/queries
1193
1194	int pvsl = 0;
1195	int pvsr = pvsSize;
1196
1197	int pvsBack = pvsl;
1198	int pvsFront = pvsr;
1199
1200	float sum = (float)pvsSize * sizeBox;
1201	float minSum = 1e20f;
1202
1203	// if no good split can be found, take mid split
1204	position = minBox + 0.5f * sizeBox;
1205
1206	// the relative cost ratio
1207	float ratio = 99999999.0f;
1208	bool splitPlaneFound = false;
1209
1210	Intersectable::NewMail();
1211	KdLeaf::NewMail();
1212	BvhLeaf::NewMail();
1213
1214	//-- traverse through visibility events
1215	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSubdivisionCandidates->end();
1216
1217	#ifdef _DEBUG
1218	const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1219	const int leaves = mVspStats.Leaves();
1220	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
1221
1222	ofstream sumStats;
1223	ofstream pvslStats;
1224	ofstream pvsrStats;
1225
1226	if (printStats)
1227	{
1228	char str[64];
1229
1230	sprintf(str, "tmp/vsp_heur_sum-%04d.log", leaves);
1231	sumStats.open(str);
1232	sprintf(str, "tmp/vsp_heur_pvsl-%04d.log", leaves);
1233	pvslStats.open(str);
1234	sprintf(str, "tmp/vsp_heur_pvsr-%04d.log", leaves);
1235	pvsrStats.open(str);
1236	}
1237
1238	#endif
1239	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1240	{
1241	// compute changes to front and back pvs
1242	EvalHeuristics(*ci, pvsl, pvsr);
1243
1244	// Note: sufficient to compare size of bounding boxes of front and back side?
1245	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1246	{
1247	float currentPos;
1248
1249	// HACK: current positition is BETWEEN visibility events
1250	if (0 && ((ci + 1) != ci_end))
1251	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1252	else
1253	currentPos = (*ci).value;
1254
1255	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1256
1257	#ifdef _DEBUG
1258	if (printStats)
1259	{
1260	sumStats
1261	<< "#Position\n" << currentPos << endl
1262	<< "#Sum\n" << sum * volRatio << endl
1263	<< "#Pvs\n" << pvsl + pvsr << endl;
1264
1265	pvslStats
1266	<< "#Position\n" << currentPos << endl
1267	<< "#Pvsl\n" << pvsl << endl;
1268
1269	pvsrStats
1270	<< "#Position\n" << currentPos << endl
1271	<< "#Pvsr\n" << pvsr << endl;
1272	}
1273	#endif
1274
1275	if (sum < minSum)
1276	{
1277	splitPlaneFound = true;
1278
1279	minSum = sum;
1280	position = currentPos;
1281
1282	pvsBack = pvsl;
1283	pvsFront = pvsr;
1284	}
1285	}
1286	}
1287
1288
1289	//-- compute cost
1290
1291	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1292	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1293
1294	const float pOverall = sizeBox;
1295	const float pBack = position - minBox;
1296	const float pFront = maxBox - position;
1297
1298	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1299	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1300	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1301
1302	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1303	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1304
1305	if (splitPlaneFound)
1306	{
1307	ratio = newRenderCost / oldRenderCost;
1308	}
1309
1310	#ifdef _DEBUG
1311	Debug << "\n§§§§ eval local cost §§§§" << endl
1312	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1313	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1314	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1315	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1316	#endif
1317	return ratio;
1318	}
1319
1320
1321	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1322	AxisAlignedPlane &plane,
1323	float &pFront,
1324	float &pBack)
1325	{
1326	float nPosition[3];
1327	float nCostRatio[3];
1328	float nProbFront[3];
1329	float nProbBack[3];
1330
1331	// create bounding box of node geometry
1332	AxisAlignedBox3 box = tData.mBoundingBox;
1333
1334	int sAxis = 0;
1335	int bestAxis = -1;
1336
1337	// do we use some kind of specialised "fixed" axis?
1338	const bool useSpecialAxis =
1339	mOnlyDrivingAxis \|\| mCirculatingAxis;
1340
1341	if (mCirculatingAxis)
1342	{
1343	int parentAxis = 0;
1344	VspNode *parent = tData.mNode->GetParent();
1345
1346	if (parent)
1347	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1348
1349	sAxis = (parentAxis + 1) % 3;
1350	}
1351	else if (mOnlyDrivingAxis)
1352	{
1353	sAxis = box.Size().DrivingAxis();
1354	}
1355
1356	for (int axis = 0; axis < 3; ++ axis)
1357	{
1358	if (!useSpecialAxis \|\| (axis == sAxis))
1359	{
1360	if (mUseCostHeuristics)
1361	{
1362	//-- place split plane using heuristics
1363	nCostRatio[axis] =
1364	EvalLocalCostHeuristics(tData,
1365	box,
1366	axis,
1367	nPosition[axis]);
1368	}
1369	else
1370	{
1371	//-- split plane position is spatial median
1372	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1373	nCostRatio[axis] = EvalLocalSplitCost(tData,
1374	box,
1375	axis,
1376	nPosition[axis],
1377	nProbFront[axis],
1378	nProbBack[axis]);
1379	}
1380
1381	if (bestAxis == -1)
1382	{
1383	bestAxis = axis;
1384	}
1385	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1386	{
1387	bestAxis = axis;
1388	}
1389	}
1390	}
1391
1392	////////////////////////////////
1393	//-- assign values of best split
1394
1395	plane.mAxis = bestAxis;
1396	// best split plane position
1397	plane.mPosition = nPosition[bestAxis];
1398
1399	pFront = nProbFront[bestAxis];
1400	pBack = nProbBack[bestAxis];
1401
1402	return nCostRatio[bestAxis];
1403	}
1404
1405
1406	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1407	const VspTraversalData &data,
1408	float &normalizedOldRenderCost) const
1409	{
1410	float pvsFront = 0;
1411	float pvsBack = 0;
1412	float totalPvs = 0;
1413
1414	const float viewSpaceVol = mBoundingBox.GetVolume();
1415
1416	// create unique ids for pvs heuristics
1417	Intersectable::NewMail(3);
1418	KdLeaf::NewMail(3);
1419	BvhLeaf::NewMail(3);
1420
1421	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1422
1423	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1424	{
1425	RayInfo rayInf = *rit;
1426
1427	float t;
1428	VssRay *ray = rayInf.mRay;
1429
1430	// classify ray
1431	const int cf =
1432	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1433	candidatePlane.mPosition, t);
1434
1435	// evaluate contribution of ray endpoint to front and back pvs
1436	// with respect to the classification
1437	UpdateContributionsToPvs(*ray, true, cf, pvsFront, pvsBack, totalPvs);
1438	UpdateContributionsToPvs(*ray, false, cf, pvsFront, pvsBack, totalPvs);
1439	}
1440
1441	AxisAlignedBox3 frontBox;
1442	AxisAlignedBox3 backBox;
1443
1444	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1445
1446	// probability that view point lies in back / front node
1447	float pOverall = data.mProbability;
1448	float pFront = pFront = frontBox.GetVolume();
1449	float pBack = pOverall - pFront;
1450
1451
1452	//-- pvs rendering heuristics
1453
1454	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1455	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1456
1457	// only render cost heuristics or combined with standard deviation
1458	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1459	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1460	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1461
1462	const float oldRenderCost = pOverall * penaltyOld;
1463	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1464
1465	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1466
1467	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1468
1469	Debug << "\neval vsp render cost decrease" << endl
1470	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1471	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1472	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1473	<< "render cost decrease: " << renderCostDecrease << endl;
1474
1475	return renderCostDecrease;
1476	}
1477
1478
1479
1480	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1481	const AxisAlignedBox3 &box,
1482	const int axis,
1483	const float &position,
1484	float &pFront,
1485	float &pBack) const
1486	{
1487	float pvsTotal = 0;
1488	float pvsFront = 0;
1489	float pvsBack = 0;
1490
1491	// create unique ids for pvs heuristics
1492	Intersectable::NewMail(3);
1493	BvhLeaf::NewMail(3);
1494	KdLeaf::NewMail(3);
1495
1496	const int pvsSize = data.mPvs;
1497
1498	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1499
1500	// this is the main ray classification loop!
1501	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1502	{
1503	VssRay ray = (rit).mRay;
1504
1505	// determine the side of this ray with respect to the plane
1506	float t;
1507	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1508
1509	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1510	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1511	}
1512
1513
1514	//-- evaluate cost heuristics
1515
1516	float pOverall = data.mProbability;
1517
1518	// we use spatial mid split => simplified computation
1519	pBack = pFront = pOverall * 0.5f;
1520
1521	const float newCost = pvsBack * pBack + pvsFront * pFront;
1522	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1523
1524	#ifdef _DEBUG
1525	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1526	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1527	#endif
1528
1529	return (mCtDivCi + newCost) / oldCost;
1530	}
1531
1532
1533	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1534	const int cf,
1535	float &frontPvs,
1536	float &backPvs,
1537	float &totalPvs) const
1538	{
1539	if (!obj) return;
1540
1541	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1542	const int renderCost = 1;
1543
1544	// object in no pvs => new
1545	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1546	{
1547	totalPvs += renderCost;
1548	}
1549
1550	// QUESTION matt: is it safe to assume that
1551	// the object belongs to no pvs in this case?
1552	//if (cf == Ray::COINCIDENT) return;
1553
1554	if (cf >= 0) // front pvs
1555	{
1556	if (!obj->Mailed() && !obj->Mailed(2))
1557	{
1558	frontPvs += renderCost;
1559
1560	// already in back pvs => in both pvss
1561	if (obj->Mailed(1))
1562	obj->Mail(2);
1563	else
1564	obj->Mail();
1565	}
1566	}
1567
1568	if (cf <= 0) // back pvs
1569	{
1570	if (!obj->Mailed(1) && !obj->Mailed(2))
1571	{
1572	backPvs += renderCost;
1573
1574	// already in front pvs => in both pvss
1575	if (obj->Mailed())
1576	obj->Mail(2);
1577	else
1578	obj->Mail(1);
1579	}
1580	}
1581	}
1582
1583
1584	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1585	const int cf,
1586	float &frontPvs,
1587	float &backPvs,
1588	float &totalPvs) const
1589	{
1590	if (!leaf) return;
1591
1592	const int renderCost = (int)leaf->mObjects.size();
1593
1594	// leaf in no pvs => new
1595	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1596	{
1597	totalPvs += renderCost;
1598	}
1599
1600	// QUESTION matt: is it safe to assume that
1601	// the leaf belongs to no pvs in this case?
1602	//if (cf == Ray::COINCIDENT) return;
1603
1604	if (cf >= 0) // front pvs
1605	{
1606	if (!leaf->Mailed() && !leaf->Mailed(2))
1607	{
1608	frontPvs += renderCost;
1609
1610	// already in back pvs => in both pvss
1611	if (leaf->Mailed(1))
1612	leaf->Mail(2);
1613	else
1614	leaf->Mail();
1615	}
1616	}
1617
1618	if (cf <= 0) // back pvs
1619	{
1620	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1621	{
1622	backPvs += renderCost;
1623
1624	// already in front pvs => in both pvss
1625	if (leaf->Mailed())
1626	{
1627	leaf->Mail(2);
1628	}
1629	else
1630	leaf->Mail(1);
1631	}
1632	}
1633	}
1634
1635
1636
1637	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1638	const int cf,
1639	float &frontPvs,
1640	float &backPvs,
1641	float &totalPvs) const
1642	{
1643	if (!leaf) return;
1644
1645	// the objects which are referenced in this and only this leaf
1646	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1647
1648	// newly found leaf
1649	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1650	{
1651	totalPvs += contri;
1652	}
1653
1654	// recursivly update contributions of yet unclassified objects
1655	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1656
1657	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1658	{
1659	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1660	}
1661
1662	// QUESTION matt: is it safe to assume that
1663	// the object belongs to no pvs in this case?
1664	//if (cf == Ray::COINCIDENT) return;
1665
1666	if (cf >= 0) // front pvs
1667	{
1668	if (!leaf->Mailed() && !leaf->Mailed(2))
1669	{
1670	frontPvs += contri;
1671
1672	// already in back pvs => in both pvss
1673	if (leaf->Mailed(1))
1674	leaf->Mail(2);
1675	else
1676	leaf->Mail();
1677	}
1678	}
1679
1680	if (cf <= 0) // back pvs
1681	{
1682	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1683	{
1684	backPvs += contri;
1685
1686	// already in front pvs => in both pvss
1687	if (leaf->Mailed())
1688	leaf->Mail(2);
1689	else
1690	leaf->Mail(1);
1691	}
1692	}
1693	}
1694
1695
1696	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1697	const bool onlyUnmailed,
1698	const int maxPvsSize) const
1699	{
1700	stack<VspNode *> nodeStack;
1701	nodeStack.push(mRoot);
1702
1703	while (!nodeStack.empty())
1704	{
1705	VspNode *node = nodeStack.top();
1706	nodeStack.pop();
1707
1708	if (node->IsLeaf())
1709	{
1710	// test if this leaf is in valid view space
1711	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1712	if (leaf->TreeValid() &&
1713	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1714	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
1715	{
1716	leaves.push_back(leaf);
1717	}
1718	}
1719	else
1720	{
1721	VspInterior interior = dynamic_cast<VspInterior >(node);
1722
1723	nodeStack.push(interior->GetBack());
1724	nodeStack.push(interior->GetFront());
1725	}
1726	}
1727	}
1728
1729
1730	AxisAlignedBox3 VspTree::GetBoundingBox() const
1731	{
1732	return mBoundingBox;
1733	}
1734
1735
1736	VspNode *VspTree::GetRoot() const
1737	{
1738	return mRoot;
1739	}
1740
1741
1742	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1743	{
1744	// the node became a leaf -> evaluate stats for leafs
1745	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
1746
1747
1748	if (data.mPvs > mVspStats.maxPvs)
1749	{
1750	mVspStats.maxPvs = data.mPvs;
1751	}
1752
1753	mVspStats.pvs += data.mPvs;
1754
1755	if (data.mDepth < mVspStats.minDepth)
1756	{
1757	mVspStats.minDepth = data.mDepth;
1758	}
1759
1760	if (data.mDepth >= mTermMaxDepth)
1761	{
1762	++ mVspStats.maxDepthNodes;
1763	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1764	}
1765
1766	// accumulate rays to compute rays / leaf
1767	mVspStats.accumRays += (int)data.mRays->size();
1768
1769	if (data.mPvs < mTermMinPvs)
1770	++ mVspStats.minPvsNodes;
1771
1772	if ((int)data.mRays->size() < mTermMinRays)
1773	++ mVspStats.minRaysNodes;
1774
1775	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1776	++ mVspStats.maxRayContribNodes;
1777
1778	if (data.mProbability <= mTermMinProbability)
1779	++ mVspStats.minProbabilityNodes;
1780
1781	// accumulate depth to compute average depth
1782	mVspStats.accumDepth += data.mDepth;
1783
1784	++ mCreatedViewCells;
1785
1786	#ifdef _DEBUG
1787	Debug << "BSP stats: "
1788	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1789	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1790	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1791	<< "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
1792	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1793	#endif
1794	}
1795
1796
1797	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1798	{
1799	ViewCell::NewMail();
1800	CollectViewCells(mRoot, onlyValid, viewCells, true);
1801	}
1802
1803
1804	void VspTree::CollapseViewCells()
1805	{
1806	// TODO matt
1807	#if HAS_TO_BE_REDONE
1808	stack<VspNode *> nodeStack;
1809
1810	if (!mRoot)
1811	return;
1812
1813	nodeStack.push(mRoot);
1814
1815	while (!nodeStack.empty())
1816	{
1817	VspNode *node = nodeStack.top();
1818	nodeStack.pop();
1819
1820	if (node->IsLeaf())
1821	{
1822	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1823
1824	if (!viewCell->GetValid())
1825	{
1826	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1827
1828	ViewCellContainer leaves;
1829	mViewCellsTree->CollectLeaves(viewCell, leaves);
1830
1831	ViewCellContainer::const_iterator it, it_end = leaves.end();
1832
1833	for (it = leaves.begin(); it != it_end; ++ it)
1834	{
1835	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
1836	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1837	++ mVspStats.invalidLeaves;
1838	}
1839
1840	// add to unbounded view cell
1841	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1842	DEL_PTR(viewCell);
1843	}
1844	}
1845	else
1846	{
1847	VspInterior interior = dynamic_cast<VspInterior >(node);
1848
1849	nodeStack.push(interior->GetFront());
1850	nodeStack.push(interior->GetBack());
1851	}
1852	}
1853
1854	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1855	#endif
1856	}
1857
1858
1859	void VspTree::CollectRays(VssRayContainer &rays)
1860	{
1861	vector<VspLeaf *> leaves;
1862	CollectLeaves(leaves);
1863
1864	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1865
1866	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1867	{
1868	VspLeaf leaf = lit;
1869	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1870
1871	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1872	rays.push_back(*rit);
1873	}
1874	}
1875
1876
1877	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1878	{
1879	mViewCellsManager = vcm;
1880	}
1881
1882
1883	void VspTree::ValidateTree()
1884	{
1885	mVspStats.invalidLeaves = 0;
1886
1887	stack<VspNode *> nodeStack;
1888
1889	if (!mRoot)
1890	return;
1891
1892	nodeStack.push(mRoot);
1893
1894	while (!nodeStack.empty())
1895	{
1896	VspNode *node = nodeStack.top();
1897	nodeStack.pop();
1898
1899	if (node->IsLeaf())
1900	{
1901	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1902
1903	if (!leaf->GetViewCell()->GetValid())
1904	++ mVspStats.invalidLeaves;
1905
1906	// validity flags don't match => repair
1907	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1908	{
1909	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1910	PropagateUpValidity(leaf);
1911	}
1912	}
1913	else
1914	{
1915	VspInterior interior = dynamic_cast<VspInterior >(node);
1916
1917	nodeStack.push(interior->GetFront());
1918	nodeStack.push(interior->GetBack());
1919	}
1920	}
1921
1922	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1923	}
1924
1925
1926
1927	void VspTree::CollectViewCells(VspNode *root,
1928	bool onlyValid,
1929	ViewCellContainer &viewCells,
1930	bool onlyUnmailed) const
1931	{
1932	stack<VspNode *> nodeStack;
1933
1934	if (!root)
1935	return;
1936
1937	nodeStack.push(root);
1938
1939	while (!nodeStack.empty())
1940	{
1941	VspNode *node = nodeStack.top();
1942	nodeStack.pop();
1943
1944	if (node->IsLeaf())
1945	{
1946	if (!onlyValid \|\| node->TreeValid())
1947	{
1948	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
1949
1950	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
1951
1952	if (!onlyUnmailed \|\| !viewCell->Mailed())
1953	{
1954	viewCell->Mail();
1955	viewCells.push_back(viewCell);
1956	}
1957	}
1958	}
1959	else
1960	{
1961	VspInterior interior = dynamic_cast<VspInterior >(node);
1962
1963	nodeStack.push(interior->GetFront());
1964	nodeStack.push(interior->GetBack());
1965	}
1966	}
1967	}
1968
1969
1970	int VspTree::FindNeighbors(VspLeaf *n,
1971	vector<VspLeaf *> &neighbors,
1972	const bool onlyUnmailed) const
1973	{
1974	stack<VspNode *> nodeStack;
1975	nodeStack.push(mRoot);
1976
1977	const AxisAlignedBox3 box = GetBoundingBox(n);
1978
1979	while (!nodeStack.empty())
1980	{
1981	VspNode *node = nodeStack.top();
1982	nodeStack.pop();
1983
1984	if (node->IsLeaf())
1985	{
1986	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1987
1988	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
1989	neighbors.push_back(leaf);
1990	}
1991	else
1992	{
1993	VspInterior interior = dynamic_cast<VspInterior >(node);
1994
1995	if (interior->GetPosition() > box.Max(interior->GetAxis()))
1996	nodeStack.push(interior->GetBack());
1997	else
1998	{
1999	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2000	nodeStack.push(interior->GetFront());
2001	else
2002	{
2003	// random decision
2004	nodeStack.push(interior->GetBack());
2005	nodeStack.push(interior->GetFront());
2006	}
2007	}
2008	}
2009	}
2010
2011	return (int)neighbors.size();
2012	}
2013
2014
2015	// Find random neighbor which was not mailed
2016	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2017	{
2018	stack<VspNode *> nodeStack;
2019	nodeStack.push(mRoot);
2020
2021	int mask = rand();
2022
2023	while (!nodeStack.empty())
2024	{
2025	VspNode *node = nodeStack.top();
2026
2027	nodeStack.pop();
2028
2029	if (node->IsLeaf())
2030	{
2031	return dynamic_cast<VspLeaf *>(node);
2032	}
2033	else
2034	{
2035	VspInterior interior = dynamic_cast<VspInterior >(node);
2036	VspNode *next;
2037
2038	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2039	{
2040	next = interior->GetFront();
2041	}
2042	else
2043	{
2044	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2045	{
2046	next = interior->GetBack();
2047	}
2048	else
2049	{
2050	// random decision
2051	if (mask & 1)
2052	next = interior->GetBack();
2053	else
2054	next = interior->GetFront();
2055	mask = mask >> 1;
2056	}
2057	}
2058
2059	nodeStack.push(next);
2060	}
2061	}
2062
2063	return NULL;
2064	}
2065
2066
2067	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2068	{
2069	stack<VspNode *> nodeStack;
2070
2071	nodeStack.push(mRoot);
2072
2073	int mask = rand();
2074
2075	while (!nodeStack.empty())
2076	{
2077	VspNode *node = nodeStack.top();
2078	nodeStack.pop();
2079
2080	if (node->IsLeaf())
2081	{
2082	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2083	return dynamic_cast<VspLeaf *>(node);
2084	}
2085	else
2086	{
2087	VspInterior interior = dynamic_cast<VspInterior >(node);
2088
2089	// random decision
2090	if (mask & 1)
2091	nodeStack.push(interior->GetBack());
2092	else
2093	nodeStack.push(interior->GetFront());
2094
2095	mask = mask >> 1;
2096	}
2097	}
2098
2099	return NULL;
2100	}
2101
2102
2103	int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
2104	{
2105	int pvsSize = 0;
2106
2107	Intersectable::NewMail();
2108	KdNode::NewMail();
2109	BvhLeaf::NewMail();
2110
2111	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2112
2113	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2114	{
2115	VssRay ray = (rit).mRay;
2116
2117	pvsSize += EvalContributionToPvs(*ray, true);
2118	pvsSize += EvalContributionToPvs(*ray, false);
2119	}
2120
2121	return pvsSize;
2122	}
2123
2124
2125	float VspTree::GetEpsilon() const
2126	{
2127	return mEpsilon;
2128	}
2129
2130
2131	int VspTree::CastLineSegment(const Vector3 &origin,
2132	const Vector3 &termination,
2133	ViewCellContainer &viewcells,
2134	const bool useMailboxing)
2135	{
2136	int hits = 0;
2137
2138	float mint = 0.0f, maxt = 1.0f;
2139	const Vector3 dir = termination - origin;
2140
2141	stack<LineTraversalData> tStack;
2142
2143	Vector3 entp = origin;
2144	Vector3 extp = termination;
2145
2146	VspNode *node = mRoot;
2147	VspNode *farChild;
2148
2149	float position;
2150	int axis;
2151
2152	while (1)
2153	{
2154	if (!node->IsLeaf())
2155	{
2156	VspInterior in = dynamic_cast<VspInterior >(node);
2157	position = in->GetPosition();
2158	axis = in->GetAxis();
2159
2160	if (entp[axis] <= position)
2161	{
2162	if (extp[axis] <= position)
2163	{
2164	node = in->GetBack();
2165	// cases N1,N2,N3,P5,Z2,Z3
2166	continue;
2167	} else
2168	{
2169	// case N4
2170	node = in->GetBack();
2171	farChild = in->GetFront();
2172	}
2173	}
2174	else
2175	{
2176	if (position <= extp[axis])
2177	{
2178	node = in->GetFront();
2179	// cases P1,P2,P3,N5,Z1
2180	continue;
2181	}
2182	else
2183	{
2184	node = in->GetFront();
2185	farChild = in->GetBack();
2186	// case P4
2187	}
2188	}
2189
2190	// $$ modification 3.5.2004 - hints from Kamil Ghais
2191	// case N4 or P4
2192	const float tdist = (position - origin[axis]) / dir[axis];
2193	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2194
2195	extp = origin + dir * tdist;
2196	maxt = tdist;
2197	}
2198	else
2199	{
2200	// compute intersection with all objects in this leaf
2201	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2202	ViewCell *vc = leaf->GetViewCell();
2203
2204	// don't have to mail if each view cell belongs to exactly one leaf
2205	if (!useMailboxing \|\| !vc->Mailed())
2206	{
2207	if (useMailboxing)
2208	vc->Mail();
2209
2210	viewcells.push_back(vc);
2211	++ hits;
2212	}
2213	#if 0
2214	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2215	#endif
2216	// get the next node from the stack
2217	if (tStack.empty())
2218	break;
2219
2220	entp = extp;
2221	mint = maxt;
2222
2223	LineTraversalData &s = tStack.top();
2224	node = s.mNode;
2225	extp = s.mExitPoint;
2226	maxt = s.mMaxT;
2227	tStack.pop();
2228	}
2229	}
2230
2231	return hits;
2232	}
2233
2234
2235	int VspTree::CastRay(Ray &ray)
2236	{
2237	int hits = 0;
2238
2239	stack<LineTraversalData> tStack;
2240	const Vector3 dir = ray.GetDir();
2241
2242	float maxt, mint;
2243
2244	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2245	return 0;
2246
2247	Intersectable::NewMail();
2248	ViewCell::NewMail();
2249
2250	Vector3 entp = ray.Extrap(mint);
2251	Vector3 extp = ray.Extrap(maxt);
2252
2253	const Vector3 origin = entp;
2254
2255	VspNode *node = mRoot;
2256	VspNode *farChild = NULL;
2257
2258	float position;
2259	int axis;
2260
2261	while (1)
2262	{
2263	if (!node->IsLeaf())
2264	{
2265	VspInterior in = dynamic_cast<VspInterior >(node);
2266	position = in->GetPosition();
2267	axis = in->GetAxis();
2268
2269	if (entp[axis] <= position)
2270	{
2271	if (extp[axis] <= position)
2272	{
2273	node = in->GetBack();
2274	// cases N1,N2,N3,P5,Z2,Z3
2275	continue;
2276	}
2277	else
2278	{
2279	// case N4
2280	node = in->GetBack();
2281	farChild = in->GetFront();
2282	}
2283	}
2284	else
2285	{
2286	if (position <= extp[axis])
2287	{
2288	node = in->GetFront();
2289	// cases P1,P2,P3,N5,Z1
2290	continue;
2291	}
2292	else
2293	{
2294	node = in->GetFront();
2295	farChild = in->GetBack();
2296	// case P4
2297	}
2298	}
2299
2300	// $$ modification 3.5.2004 - hints from Kamil Ghais
2301	// case N4 or P4
2302	const float tdist = (position - origin[axis]) / dir[axis];
2303	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2304	extp = origin + dir * tdist;
2305	maxt = tdist;
2306	}
2307	else
2308	{
2309	// compute intersection with all objects in this leaf
2310	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2311	ViewCell *vc = leaf->GetViewCell();
2312
2313	if (!vc->Mailed())
2314	{
2315	vc->Mail();
2316	// todo: add view cells to ray
2317	++ hits;
2318	}
2319	#if 0
2320	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2321	#endif
2322	// get the next node from the stack
2323	if (tStack.empty())
2324	break;
2325
2326	entp = extp;
2327	mint = maxt;
2328
2329	LineTraversalData &s = tStack.top();
2330	node = s.mNode;
2331	extp = s.mExitPoint;
2332	maxt = s.mMaxT;
2333	tStack.pop();
2334	}
2335	}
2336
2337	return hits;
2338	}
2339
2340
2341	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2342	{
2343	if (mRoot == NULL)
2344	return NULL;
2345
2346	stack<VspNode *> nodeStack;
2347	nodeStack.push(mRoot);
2348
2349	ViewCellLeaf *viewcell = NULL;
2350
2351	while (!nodeStack.empty())
2352	{
2353	VspNode *node = nodeStack.top();
2354	nodeStack.pop();
2355
2356	if (node->IsLeaf())
2357	{
2358	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2359	break;
2360	}
2361	else
2362	{
2363	VspInterior interior = dynamic_cast<VspInterior >(node);
2364
2365	// random decision
2366	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2367	nodeStack.push(interior->GetBack());
2368	else
2369	nodeStack.push(interior->GetFront());
2370	}
2371	}
2372
2373	if (active)
2374	return mViewCellsTree->GetActiveViewCell(viewcell);
2375	else
2376	return viewcell;
2377	}
2378
2379
2380	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2381	{
2382	VspNode *node = mRoot;
2383
2384	while (1)
2385	{
2386	// early exit
2387	if (node->TreeValid())
2388	return true;
2389
2390	if (node->IsLeaf())
2391	return false;
2392
2393	VspInterior in = dynamic_cast<VspInterior >(node);
2394
2395	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2396	{
2397	node = in->GetBack();
2398	}
2399	else
2400	{
2401	node = in->GetFront();
2402	}
2403	}
2404
2405	// should never come here
2406	return false;
2407	}
2408
2409
2410	void VspTree::PropagateUpValidity(VspNode *node)
2411	{
2412	const bool isValid = node->TreeValid();
2413
2414	// propagative up invalid flag until only invalid nodes exist over this node
2415	if (!isValid)
2416	{
2417	while (!node->IsRoot() && node->GetParent()->TreeValid())
2418	{
2419	node = node->GetParent();
2420	node->SetTreeValid(false);
2421	}
2422	}
2423	else
2424	{
2425	// propagative up valid flag until one of the subtrees is invalid
2426	while (!node->IsRoot() && !node->TreeValid())
2427	{
2428	node = node->GetParent();
2429	VspInterior interior = dynamic_cast<VspInterior >(node);
2430
2431	// the parent is valid iff both leaves are valid
2432	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2433	interior->GetFront()->TreeValid());
2434	}
2435	}
2436	}
2437
2438
2439	bool VspTree::Export(OUT_STREAM &stream)
2440	{
2441	ExportNode(mRoot, stream);
2442
2443	return true;
2444	}
2445
2446
2447	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2448	{
2449	if (node->IsLeaf())
2450	{
2451	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2452	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2453
2454	int id = -1;
2455	if (viewCell != mOutOfBoundsCell)
2456	id = viewCell->GetId();
2457
2458	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2459	}
2460	else
2461	{
2462	VspInterior interior = dynamic_cast<VspInterior >(node);
2463
2464	AxisAlignedPlane plane = interior->GetPlane();
2465	stream << "<Interior plane=\"" << plane.mPosition << " "
2466	<< plane.mAxis << "\">" << endl;
2467
2468	ExportNode(interior->GetBack(), stream);
2469	ExportNode(interior->GetFront(), stream);
2470
2471	stream << "</Interior>" << endl;
2472	}
2473	}
2474
2475
2476	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2477	RayInfoContainer &rays,
2478	RayInfoContainer &frontRays,
2479	RayInfoContainer &backRays) const
2480	{
2481	int splits = 0;
2482
2483	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2484
2485	for (rit = rays.begin(); rit != rit_end; ++ rit)
2486	{
2487	RayInfo bRay = *rit;
2488
2489	VssRay *ray = bRay.mRay;
2490	float t;
2491
2492	// get classification and receive new t
2493	// test if start point behind or in front of plane
2494	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2495
2496	if (side == 0)
2497	{
2498	++ splits;
2499
2500	if (ray->HasPosDir(plane.mAxis))
2501	{
2502	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2503	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2504	}
2505	else
2506	{
2507	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2508	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2509	}
2510	}
2511	else if (side == 1)
2512	{
2513	frontRays.push_back(bRay);
2514	}
2515	else
2516	{
2517	backRays.push_back(bRay);
2518	}
2519	}
2520
2521	return splits;
2522	}
2523
2524
2525	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2526	{
2527	if (!node->GetParent())
2528	return mBoundingBox;
2529
2530	if (!node->IsLeaf())
2531	{
2532	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
2533	}
2534
2535	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
2536
2537	AxisAlignedBox3 box(parent->GetBoundingBox());
2538
2539	if (parent->GetFront() == node)
2540	box.SetMin(parent->GetAxis(), parent->GetPosition());
2541	else
2542	box.SetMax(parent->GetAxis(), parent->GetPosition());
2543
2544	return box;
2545	}
2546
2547
2548	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2549	ViewCellContainer &viewCells) const
2550	{
2551	stack<VspNode *> nodeStack;
2552
2553	ViewCell::NewMail();
2554
2555	while (!nodeStack.empty())
2556	{
2557	VspNode *node = nodeStack.top();
2558	nodeStack.pop();
2559
2560	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2561
2562	if (bbox.Includes(box))
2563	{
2564	// node geometry is contained in box
2565	CollectViewCells(node, true, viewCells, true);
2566	}
2567	else if (Overlap(bbox, box))
2568	{
2569	if (node->IsLeaf())
2570	{
2571	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2572
2573	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2574	{
2575	leaf->GetViewCell()->Mail();
2576	viewCells.push_back(leaf->GetViewCell());
2577	}
2578	}
2579	else
2580	{
2581	VspInterior interior = dynamic_cast<VspInterior >(node);
2582
2583	VspNode *first = interior->GetFront();
2584	VspNode *second = interior->GetBack();
2585
2586	nodeStack.push(first);
2587	nodeStack.push(second);
2588	}
2589	}
2590	// default: cull
2591	}
2592
2593	return (int)viewCells.size();
2594	}
2595
2596
2597	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2598	RayInfoContainer &rays)
2599	{
2600	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2601
2602	long startTime = GetTime();
2603
2604	cout << "storing rays ... ";
2605
2606	Intersectable::NewMail();
2607
2608	//-- store rays and objects
2609	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2610	{
2611	VssRay ray = rit;
2612	float minT, maxT;
2613	static Ray hray;
2614
2615	hray.Init(*ray);
2616
2617	// TODO: not very efficient to implictly cast between rays types
2618	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2619	{
2620	float len = ray->Length();
2621
2622	if (!len)
2623	len = Limits::Small;
2624
2625	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2626	}
2627	}
2628
2629	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2630	}
2631
2632
2633	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2634	{
2635	static Ray hray;
2636	hray.Init(ray);
2637
2638	float tmin = 0, tmax = 1.0;
2639
2640	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2641	return;
2642
2643	const Vector3 origin = hray.Extrap(tmin);
2644	const Vector3 termination = hray.Extrap(tmax);
2645
2646	// view cells were not precomputed
2647	// don't mail because we need mailboxing for something else
2648	CastLineSegment(origin, termination, viewCells, false);
2649	}
2650
2651
2652	SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
2653	AxisAlignedBox3 *forcedViewSpace,
2654	RayInfoContainer &rays)
2655	{
2656	mVspStats.Reset();
2657	mVspStats.Start();
2658	mVspStats.nodes = 1;
2659
2660	// store pointer to this tree
2661	VspSubdivisionCandidate::sVspTree = this;
2662
2663	// compute view space bounding box
2664	ComputeBoundingBox(sampleRays, forcedViewSpace);
2665
2666	// initialise termination criteria
2667	mTermMinProbability *= mBoundingBox.GetVolume();
2668	mGlobalCostMisses = 0;
2669
2670	// get clipped rays
2671	PreprocessRays(sampleRays, rays);
2672
2673	const int pvsSize = EvalPvsSize(rays);
2674
2675	Debug << "pvs size: " << (int)pvsSize << endl;
2676	Debug << "rays size: " << (int)rays.size() << endl;
2677
2678	//-- prepare view space partition
2679	const float prop = mBoundingBox.GetVolume();
2680
2681	// we assume that leaf was already created
2682	VspLeaf *leaf = new VspLeaf();
2683	mRoot = leaf;
2684
2685	// first vsp traversal data
2686	VspTraversalData vData(leaf, 0, &rays, pvsSize, prop, mBoundingBox);
2687
2688	// create first view cell
2689	CreateViewCell(vData, false);
2690
2691	#if WORK_WITH_VIEWCELL_PVS
2692	// add first view cell to all the objects view cell pvs
2693	ObjectPvsMap::const_iterator oit,
2694	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2695
2696	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2697	{
2698	Intersectable obj = (oit).first;
2699	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2700	}
2701	#endif
2702
2703	//-- compute first split candidate
2704
2705	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2706	EvalSubdivisionCandidate(*splitCandidate);
2707	leaf->SetSubdivisionCandidate(splitCandidate);
2708
2709	mTotalCost = (float)pvsSize;
2710	EvalSubdivisionStats(*splitCandidate);
2711
2712	return splitCandidate;
2713	}
2714
2715
2716	void VspTree::CollectDirtyCandidate(const VssRay &ray,
2717	const bool isTermination,
2718	vector<SubdivisionCandidate *> &dirtyList) const
2719	{
2720
2721	Intersectable *obj;
2722	Vector3 pt;
2723	KdNode *node;
2724
2725	ray.GetSampleData(isTermination, pt, &obj, &node);
2726
2727	if (!obj) return;
2728
2729	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2730	{
2731	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2732	{
2733	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2734
2735	if (!leaf->Mailed())
2736	{
2737	leaf->Mail();
2738	dirtyList.push_back(leaf->mSubdivisionCandidate);
2739	}
2740	break;
2741	}
2742	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2743	{
2744	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2745
2746	if (!leaf->Mailed())
2747	{
2748	leaf->Mail();
2749	if (leaf->GetSubdivisionCandidate()) // a candidate still attached to this node
2750	{
2751	dirtyList.push_back(leaf->GetSubdivisionCandidate());
2752	}
2753	}
2754	break;
2755	}
2756	default:
2757	break;
2758	}
2759	}
2760
2761
2762	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
2763	vector<SubdivisionCandidate *> &dirtyList)
2764	{
2765	VspTraversalData &tData = sc->mParentData;
2766	VspLeaf *node = tData.mNode;
2767
2768	KdLeaf::NewMail();
2769	BvhLeaf::NewMail();
2770
2771	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2772
2773	// add all kd nodes seen by the rays
2774	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2775	{
2776	VssRay ray = (rit).mRay;
2777
2778	CollectDirtyCandidate(*ray, true, dirtyList);
2779	CollectDirtyCandidate(*ray, false, dirtyList);
2780	}
2781	}
2782
2783
2784	int VspTree::EvalMaxEventContribution(const VssRay &ray,
2785	const bool isTermination) const
2786	{
2787	Intersectable *obj;
2788	Vector3 pt;
2789	KdNode *node;
2790
2791	ray.GetSampleData(isTermination, pt, &obj, &node);
2792
2793	if (!obj)
2794	return 0;
2795
2796	int pvs = 0;
2797
2798	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2799	{
2800	case HierarchyManager::NO_OBJ_SUBDIV:
2801	{
2802	if (-- obj->mCounter == 0)
2803	++ pvs;
2804	break;
2805	}
2806	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2807	{
2808	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2809
2810	// add contributions of the kd nodes
2811	pvs += EvalMaxEventContribution(leaf);
2812	break;
2813	}
2814	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2815	{
2816	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2817
2818	if (-- leaf->mCounter == 0)
2819	pvs += (int)leaf->mObjects.size();
2820	break;
2821	}
2822	default:
2823	break;
2824	}
2825
2826	return pvs;
2827	}
2828
2829
2830	int VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
2831	{
2832	int pvsSize = 0;
2833
2834	Intersectable *obj;
2835	Vector3 pt;
2836	KdNode *node;
2837
2838	ray.GetSampleData(isTermination, pt, &obj, &node);
2839
2840	if (!obj)
2841	return 0;
2842
2843	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2844	{
2845	case HierarchyManager::NO_OBJ_SUBDIV:
2846	{
2847	if (!obj->Mailed())
2848	{
2849	obj->Mail();
2850	obj->mCounter = 0;
2851	++ pvsSize;
2852	}
2853	++ obj->mCounter;
2854	break;
2855	}
2856	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2857	{
2858	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2859	pvsSize += PrepareHeuristics(leaf);
2860	break;
2861	}
2862	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2863	{
2864	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2865
2866	if (!leaf->Mailed())
2867	{
2868	leaf->Mail();
2869	leaf->mCounter = 0;
2870	pvsSize += (int)leaf->mObjects.size();
2871	}
2872	++ leaf->mCounter;
2873	break;
2874	}
2875	default:
2876	break;
2877	}
2878
2879	return pvsSize;
2880	}
2881
2882
2883	int VspTree::EvalMinEventContribution(const VssRay &ray,
2884	const bool isTermination) const
2885	{
2886	Intersectable *obj;
2887	Vector3 pt;
2888	KdNode *node;
2889
2890	ray.GetSampleData(isTermination, pt, &obj, &node);
2891
2892	if (!obj) return 0;
2893
2894	int pvs = 0;
2895
2896	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2897	{
2898	case HierarchyManager::NO_OBJ_SUBDIV:
2899	{
2900	if (!obj->Mailed())
2901	{
2902	obj->Mail();
2903	++ pvs;
2904	}
2905	break;
2906	}
2907	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2908	{
2909	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2910	// add contributions of the kd nodes
2911	pvs += EvalMinEventContribution(leaf);
2912	break;
2913	}
2914	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2915	{
2916	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2917	if (!leaf->Mailed())
2918	{
2919	leaf->Mail();
2920	pvs += (int)leaf->mObjects.size();
2921	}
2922	break;
2923	}
2924	default:
2925	break;
2926	}
2927
2928	return pvs;
2929	}
2930
2931
2932	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
2933	const bool isTermination,
2934	const int cf,
2935	float &frontPvs,
2936	float &backPvs,
2937	float &totalPvs) const
2938	{
2939	Intersectable *obj;
2940	Vector3 pt;
2941	KdNode *node;
2942
2943	ray.GetSampleData(isTermination, pt, &obj, &node);
2944
2945	if (!obj) return;
2946
2947	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2948	{
2949	case HierarchyManager::NO_OBJ_SUBDIV:
2950	{
2951	// find front and back pvs for origing and termination object
2952	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
2953	break;
2954	}
2955	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2956	{
2957	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2958	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2959	break;
2960	}
2961	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2962	{
2963	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2964	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2965	break;
2966	}
2967	}
2968	}
2969
2970
2971	int VspTree::EvalContributionToPvs(const VssRay &ray,
2972	const bool isTermination) const
2973	{
2974	Intersectable *obj;
2975	Vector3 pt;
2976	KdNode *node;
2977
2978	ray.GetSampleData(isTermination, pt, &obj, &node);
2979
2980	if (!obj) return 0;
2981
2982	int pvs = 0;
2983
2984	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
2985	{
2986	case HierarchyManager::NO_OBJ_SUBDIV:
2987	{
2988	if (!obj->Mailed())
2989	{
2990	obj->Mail();
2991	++ pvs;
2992	}
2993	break;
2994	}
2995	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2996	{
2997	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2998
2999	pvs += EvalContributionToPvs(leaf);
3000	break;
3001	}
3002	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3003	{
3004	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3005
3006	if (!bvhleaf->Mailed())
3007	{
3008	bvhleaf->Mail();
3009	pvs += (int)bvhleaf->mObjects.size();
3010	}
3011	break;
3012	}
3013	default:
3014	break;
3015	}
3016
3017	return pvs;
3018	}
3019
3020
3021	int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3022	{
3023	if (leaf->Mailed()) // leaf already mailed
3024	return 0;
3025
3026	leaf->Mail();
3027
3028	int pvs = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3029
3030	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3031
3032	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3033	{
3034	Intersectable obj = oit;
3035	if (!obj->Mailed())
3036	{
3037	obj->Mail();
3038	++ pvs;
3039	}
3040	}
3041
3042	return pvs;
3043	}
3044
3045
3046	}

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

Download in other formats: