Context Navigation

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

Revision 1686, 79.5 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: