Context Navigation

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

Revision 2170, 82.8 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: