Context Navigation

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

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

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

Download in other formats: