Context Navigation

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

Revision 2353, 86.7 KB checked in by mattausch, 18 years ago (diff)
cleaned up project files

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

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

Download in other formats: