Context Navigation

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

Revision 2237, 92.3 KB checked in by mattausch, 17 years ago (diff)
worked on optimization. warning: not tested yet

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

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

Download in other formats: