Context Navigation

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

Revision 2187, 85.8 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: