Context Navigation

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

Revision 1665, 77.2 KB checked in by mattausch, 18 years ago (diff)
improved ratio method for vsposp subdivision

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

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

Download in other formats: