Context Navigation

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

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

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

Download in other formats: