Context Navigation

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

Revision 2288, 92.1 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: