Context Navigation

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

Revision 1707, 78.4 KB checked in by mattausch, 18 years ago (diff)
worked on full render cost evaluation warning: some change sin render cost evaluation for pvs which could have bugs

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

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

Download in other formats: