Context Navigation

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

Revision 1664, 77.3 KB checked in by mattausch, 18 years ago (diff)
changed priority computation: taking ratio render cost decrease / pvs size increase rather then render cost decrease alone this should rather emphasise object space splits, as they seem to cost less memory.

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

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

Download in other formats: