Context Navigation

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

Revision 2198, 86.0 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	mPlaneTimer.Entry();
778
779	if (computeSplitPlane)
780	{
781	float frontProb;
782	float backProb;
783
784	// compute locally best split plane
785	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
786	splitCandidate.mSplitPlane,
787	frontProb,
788	backProb);
789
790	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
791
792	const int maxCostMisses = splitCandidate.mParentData.mMaxCostMisses;
793	// max cost threshold violated?
794	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
795	maxCostMisses + 1: maxCostMisses);
796	}
797
798	mPlaneTimer.Exit();
799
800	mEvalTimer.Entry();
801
802	VspLeaf leaf = static_cast<VspLeaf >(splitCandidate.mParentData.mNode);
803
804	/////////////
805	// avg ray contri
806
807	const int pvs = EvalPvsEntriesSize(*splitCandidate.mParentData.mRays);
808
809	const float avgRayContri = (float)pvs /
810	((float)splitCandidate.mParentData.mRays->size() + Limits::Small);
811
812	splitCandidate.SetAvgRayContribution(avgRayContri);
813
814	// compute global decrease in render cost
815	float oldRenderCost;
816	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate, oldRenderCost);
817	splitCandidate.SetRenderCostDecrease(renderCostDecr);
818
819	// the increase in pvs entries num induced by this split
820	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
821	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
822
823	// take render cost of node into account
824	// otherwise danger of being stuck in a local minimum!
825	const float factor = mRenderCostDecreaseWeight;
826
827	float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
828
829	if (mHierarchyManager->mConsiderMemory)
830	{
831	priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
832	}
833
834	splitCandidate.SetPriority(priority);
835
836	mEvalTimer.Exit();
837	}
838
839
840	int VspTree::EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const
841	{
842	float oldPvsSize = 0;
843	float fPvsSize = 0;
844	float bPvsSize = 0;
845
846	const AxisAlignedPlane candidatePlane = splitCandidate.mSplitPlane;
847
848	Intersectable::NewMail(3);
849	KdLeaf::NewMail(3);
850
851	RayInfoContainer::const_iterator rit, rit_end = splitCandidate.mParentData.mRays->end();
852
853	// this is the main ray classification loop!
854	for(rit = splitCandidate.mParentData.mRays->begin(); rit != rit_end; ++ rit)
855	{
856	VssRay ray = (rit).mRay;
857	RayInfo rayInf = *rit;
858
859	float t;
860	// classify ray
861	const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis,
862	candidatePlane.mPosition, t);
863
864	UpdatePvsEntriesContribution(*ray, true, cf, fPvsSize, bPvsSize, oldPvsSize);
865	#if COUNT_ORIGIN_OBJECTS
866	UpdatePvsEntriesContribution(*ray, false, cf, fPvsSize, bPvsSize, oldPvsSize);
867	#endif
868	}
869
870	const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ?
871	oldPvsSize / splitCandidate.mParentData.mPvs : 1;
872	const float correctedOldPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
873
874	splitCandidate.mCorrectedFrontPvs =
875	mHierarchyManager->EvalCorrectedPvs(fPvsSize,
876	correctedOldPvs,
877	splitCandidate.GetAvgRayContribution());
878	splitCandidate.mCorrectedBackPvs =
879	mHierarchyManager->EvalCorrectedPvs(bPvsSize,
880	correctedOldPvs,
881	splitCandidate.GetAvgRayContribution());
882
883	if (0)
884	cout << "vsp pvs"
885	<< " avg ray contri: " << splitCandidate.GetAvgRayContribution() << " ratio: " << oldPvsRatio
886	<< " parent: " << correctedOldPvs << " " << " old vol: " << oldPvsSize
887	<< " frontpvs: " << fPvsSize << " corr. " << splitCandidate.mCorrectedFrontPvs
888	<< " backpvs: " << bPvsSize << " corr. " << splitCandidate.mCorrectedBackPvs << endl;
889
890
891	return (int)(splitCandidate.mCorrectedFrontPvs + splitCandidate.mCorrectedBackPvs - correctedOldPvs);
892	}
893
894
895	VspInterior *VspTree::SubdivideNode(const VspSubdivisionCandidate &sc,
896	VspTraversalData &frontData,
897	VspTraversalData &backData)
898	{
899	mNodeTimer.Entry();
900
901	VspLeaf leaf = static_cast<VspLeaf >(sc.mParentData.mNode);
902
903	const VspTraversalData &tData = sc.mParentData;
904	const AxisAlignedPlane splitPlane = sc.mSplitPlane;
905
906	///////////////
907	//-- new traversal values
908
909	frontData.mDepth = tData.mDepth + 1;
910	backData.mDepth = tData.mDepth + 1;
911
912	frontData.mRays = new RayInfoContainer();
913	backData.mRays = new RayInfoContainer();
914
915	//-- subdivide rays
916	SplitRays(splitPlane, tData.mRays, frontData.mRays, *backData.mRays);
917
918	//-- compute pvs
919	frontData.mPvs = (float)EvalPvsEntriesSize(*frontData.mRays);
920	backData.mPvs = (float)EvalPvsEntriesSize(*backData.mRays);
921
922	//-- compute pvs correction for coping with undersampling
923	frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
924	backData.mCorrectedPvs = sc.mCorrectedBackPvs;
925
926	//-- split front and back node geometry and compute area
927	tData.mBoundingBox.Split(splitPlane.mAxis,
928	splitPlane.mPosition,
929	frontData.mBoundingBox,
930	backData.mBoundingBox);
931
932	frontData.mProbability = frontData.mBoundingBox.GetVolume();
933	backData.mProbability = tData.mProbability - frontData.mProbability;
934
935	//-- compute render cost
936	frontData.mRenderCost = (float)EvalPvsCost(*frontData.mRays);
937	backData.mRenderCost = (float)EvalPvsCost(*backData.mRays);
938
939	frontData.mCorrectedRenderCost = sc.mCorrectedFrontRenderCost;
940	backData.mCorrectedRenderCost = sc.mCorrectedBackRenderCost;
941
942	////////
943	//-- update some stats
944
945	if (tData.mDepth > mVspStats.maxDepth)
946	{
947	mVspStats.maxDepth = tData.mDepth;
948	}
949
950	// two more leaves per split
951	mVspStats.nodes += 2;
952	// and a new split
953	++ mVspStats.splits[splitPlane.mAxis];
954
955
956	////////////////
957	//-- create front and back and subdivide further
958
959	VspInterior *interior = new VspInterior(splitPlane);
960	VspInterior *parent = leaf->GetParent();
961
962	// replace a link from node's parent
963	if (parent)
964	{
965	parent->ReplaceChildLink(leaf, interior);
966	interior->SetParent(parent);
967
968	#if WORK_WITH_VIEWCELLS
969	// remove "parent" view cell from pvs of all objects (traverse through rays)
970	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
971	#endif
972	}
973	else // new root
974	{
975	mRoot = interior;
976	}
977
978	VspLeaf *frontLeaf = new VspLeaf(interior);
979	VspLeaf *backLeaf = new VspLeaf(interior);
980
981	// and setup child links
982	interior->SetupChildLinks(frontLeaf, backLeaf);
983
984	// add bounding box
985	interior->SetBoundingBox(tData.mBoundingBox);
986
987	// set front and back leaf
988	frontData.mNode = frontLeaf;
989	backData.mNode = backLeaf;
990
991	// create front and back view cell for the new leaves
992	CreateViewCell(frontData, false);
993	CreateViewCell(backData, false);
994
995	// set the time stamp so the order of traversal can be reconstructed
996	interior->mTimeStamp = mHierarchyManager->mTimeStamp ++;
997
998	#if WORK_WITH_VIEWCELL_PVS
999	// create front and back view cell
1000	// add front and back view cell to
1001	// "potentially visible view cells"
1002	// of the objects in front and back pvs
1003
1004	AddViewCellReferences(frontLeaf->GetViewCell());
1005	AddViewCellReferences(backLeaf->GetViewCell());
1006	#endif
1007
1008	mNodeTimer.Exit();
1009
1010	return interior;
1011	}
1012
1013
1014	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
1015	const RayInfoContainer &rays,
1016	float &sampleContributions,
1017	int &contributingSamples)
1018	{
1019	sampleContributions = 0;
1020	contributingSamples = 0;
1021
1022	RayInfoContainer::const_iterator it, it_end = rays.end();
1023
1024	ViewCellLeaf *vc = leaf->GetViewCell();
1025
1026	// add contributions from samples to the pvs
1027	for (it = rays.begin(); it != it_end; ++ it)
1028	{
1029	float sc = 0.0f;
1030	VssRay ray = (it).mRay;
1031
1032	bool madeContrib = false;
1033	float contribution = 1;
1034
1035	Intersectable *entry =
1036	mHierarchyManager->GetIntersectable(ray->mTerminationObject, true);
1037
1038	if (entry)
1039	{
1040	madeContrib =
1041	vc->GetPvs().AddSample(entry, ray->mPdf);
1042
1043	sc += contribution;
1044	}
1045	#if COUNT_ORIGIN_OBJECTS
1046	entry = mHierarchyManager->GetIntersectable(ray->mOriginObject, true);
1047
1048	if (entry)
1049	{
1050	madeContrib =
1051	vc->GetPvs().AddSample(entry, ray->mPdf);
1052
1053	sc += contribution;
1054	}
1055	#endif
1056	if (madeContrib)
1057	{
1058	++ contributingSamples;
1059	}
1060
1061	// store rays for visualization
1062	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
1063	}
1064	}
1065
1066
1067	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
1068	const int axis,
1069	float minBand,
1070	float maxBand)
1071	{
1072	mSortTimer.Entry();
1073
1074	mLocalSubdivisionCandidates->clear();
1075
1076	const int requestedSize = 2 * (int)(rays.size());
1077
1078	// creates a sorted split candidates array
1079	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
1080	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
1081	{
1082	delete mLocalSubdivisionCandidates;
1083	mLocalSubdivisionCandidates = new vector<SortableEntry>;
1084	}
1085
1086	mLocalSubdivisionCandidates->reserve(requestedSize);
1087
1088	float pos;
1089	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1090
1091	const bool delayMinEvent = false;
1092
1093	////////////
1094	//-- insert all queries
1095	for (rit = rays.begin(); rit != rit_end; ++ rit)
1096	{
1097	const bool positive = (*rit).mRay->HasPosDir(axis);
1098
1099	// origin point
1100	pos = (*rit).ExtrapOrigin(axis);
1101	const int oType = positive ? SortableEntry::ERayMin : SortableEntry::ERayMax;
1102
1103	if (delayMinEvent && oType == SortableEntry::ERayMin)
1104	pos += mEpsilon; // could be useful feature for walls
1105
1106	mLocalSubdivisionCandidates->push_back(SortableEntry(oType, pos, (*rit).mRay));
1107
1108	// termination point
1109	pos = (*rit).ExtrapTermination(axis);
1110	const int tType = positive ? SortableEntry::ERayMax : SortableEntry::ERayMin;
1111
1112	if (delayMinEvent && tType == SortableEntry::ERayMin)
1113	pos += mEpsilon; // could be useful feature for walls
1114
1115	mLocalSubdivisionCandidates->push_back(SortableEntry(tType, pos, (*rit).mRay));
1116	}
1117
1118	if (1)
1119	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1120	else
1121	sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1122
1123	mSortTimer.Exit();
1124	}
1125
1126
1127	float VspTree::PrepareHeuristics(KdLeaf *leaf)
1128	{
1129	float pvsSize = 0;
1130
1131	if (!leaf->Mailed())
1132	{
1133	leaf->Mail();
1134	leaf->mCounter = 1;
1135	// add objects without the objects which are in several kd leaves
1136	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1137	}
1138	else
1139	{
1140	++ leaf->mCounter;
1141	}
1142
1143	//-- the objects belonging to several leaves must be handled seperately
1144	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1145
1146	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1147	{
1148	Intersectable object = oit;
1149
1150	if (!object->Mailed())
1151	{
1152	object->Mail();
1153	object->mCounter = 1;
1154
1155	++ pvsSize;
1156	}
1157	else
1158	{
1159	++ object->mCounter;
1160	}
1161	}
1162
1163	return pvsSize;
1164	}
1165
1166
1167	float VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1168	{
1169	Intersectable::NewMail();
1170	KdNode::NewMail();
1171
1172	float pvsSize = 0;
1173
1174	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1175
1176	// set all kd nodes / objects as belonging to the front pvs
1177	for (ri = rays.begin(); ri != ri_end; ++ ri)
1178	{
1179	VssRay ray = (ri).mRay;
1180
1181	pvsSize += PrepareHeuristics(*ray, true);
1182	#if COUNT_ORIGIN_OBJECTS
1183	pvsSize += PrepareHeuristics(*ray, false);
1184	#endif
1185	}
1186
1187	return pvsSize;
1188	}
1189
1190
1191	int VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1192	{
1193	int pvs = 0;
1194
1195	// leaf falls out of right pvs
1196	if (-- leaf->mCounter == 0)
1197	{
1198	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1199	}
1200
1201	//////
1202	//-- separately handle objects which are in several kd leaves
1203
1204	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1205
1206	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1207	{
1208	Intersectable object = oit;
1209
1210	if (-- object->mCounter == 0)
1211	{
1212	++ pvs;
1213	}
1214	}
1215
1216	return pvs;
1217	}
1218
1219
1220	int VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1221	{
1222	if (leaf->Mailed())
1223	return 0;
1224
1225	leaf->Mail();
1226
1227	// add objects without those which are part of several kd leaves
1228	int pvs = ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1229
1230	// separately handle objects which are part of several kd leaves
1231	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1232
1233	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1234	{
1235	Intersectable object = oit;
1236
1237	// object not previously in pvs
1238	if (!object->Mailed())
1239	{
1240	object->Mail();
1241	++ pvs;
1242	}
1243	}
1244
1245	return pvs;
1246	}
1247
1248
1249	void VspTree::EvalHeuristics(const SortableEntry &ci,
1250	float &pvsLeft,
1251	float &pvsRight) const
1252	{
1253	VssRay *ray = ci.ray;
1254
1255	// eval changes in pvs causes by min event
1256	if (ci.type == SortableEntry::ERayMin)
1257	{
1258	pvsLeft += EvalMinEventContribution(*ray, true);
1259	#if COUNT_ORIGIN_OBJECTS
1260	pvsLeft += EvalMinEventContribution(*ray, false);
1261	#endif
1262	}
1263	else // eval changes in pvs causes by max event
1264	{
1265	pvsRight -= EvalMaxEventContribution(*ray, true);
1266	#if COUNT_ORIGIN_OBJECTS
1267	pvsRight -= EvalMaxEventContribution(*ray, false);
1268	#endif
1269	}
1270	}
1271
1272
1273	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1274	const AxisAlignedBox3 &box,
1275	const int axis,
1276	float &position,
1277	const RayInfoContainer &usedRays)
1278	{
1279	const float minBox = box.Min(axis);
1280	const float maxBox = box.Max(axis);
1281
1282	const float sizeBox = maxBox - minBox;
1283
1284	const float minBand = minBox + mMinBand * sizeBox;
1285	const float maxBand = minBox + mMaxBand * sizeBox;
1286
1287	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1288
1289	// prepare the sweep
1290	// note: returns pvs size => no need t give pvs size as function parameter
1291	const float pvsCost = PrepareHeuristics(usedRays);
1292
1293	// go through the lists, count the number of objects left and right
1294	// and evaluate the following cost funcion:
1295	// C = ct_div_ci + (qlrl + qrrr)/queries
1296
1297	float pvsl = 0;
1298	float pvsr = pvsCost;
1299
1300	float pvsBack = pvsl;
1301	float pvsFront = pvsr;
1302
1303	float sum = pvsCost * sizeBox;
1304	float minSum = 1e20f;
1305
1306	// if no good split can be found, take mid split
1307	position = minBox + 0.5f * sizeBox;
1308
1309	// the relative cost ratio
1310	float ratio = 99999999.0f;
1311	bool splitPlaneFound = false;
1312
1313	Intersectable::NewMail();
1314	KdLeaf::NewMail();
1315
1316	const float volRatio =
1317	tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1318
1319	////////
1320	//-- iterate through visibility events
1321
1322	vector<SortableEntry>::const_iterator ci,
1323	ci_end = mLocalSubdivisionCandidates->end();
1324
1325	#ifdef GTP_DEBUG
1326	const int leaves = mVspStats.Leaves();
1327	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
1328
1329	ofstream sumStats;
1330	ofstream pvslStats;
1331	ofstream pvsrStats;
1332
1333	if (printStats)
1334	{
1335	char str[64];
1336
1337	sprintf(str, "tmp/vsp_heur_sum-%04d.log", leaves);
1338	sumStats.open(str);
1339	sprintf(str, "tmp/vsp_heur_pvsl-%04d.log", leaves);
1340	pvslStats.open(str);
1341	sprintf(str, "tmp/vsp_heur_pvsr-%04d.log", leaves);
1342	pvsrStats.open(str);
1343	}
1344
1345	#endif
1346	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1347	{
1348	// compute changes to front and back pvs
1349	EvalHeuristics(*ci, pvsl, pvsr);
1350
1351	// Note: sufficient to compare size of bounding boxes of front and back side?
1352	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1353	{
1354	float currentPos;
1355
1356	// HACK: current positition is BETWEEN visibility events
1357	if (0 && ((ci + 1) != ci_end))
1358	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1359	else
1360	currentPos = (*ci).value;
1361
1362	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1363
1364	#ifdef GTP_DEBUG
1365	if (printStats)
1366	{
1367	sumStats
1368	<< "#Position\n" << currentPos << endl
1369	<< "#Sum\n" << sum * volRatio << endl
1370	<< "#Pvs\n" << pvsl + pvsr << endl;
1371
1372	pvslStats
1373	<< "#Position\n" << currentPos << endl
1374	<< "#Pvsl\n" << pvsl << endl;
1375
1376	pvsrStats
1377	<< "#Position\n" << currentPos << endl
1378	<< "#Pvsr\n" << pvsr << endl;
1379	}
1380	#endif
1381
1382	if (sum < minSum)
1383	{
1384	splitPlaneFound = true;
1385
1386	minSum = sum;
1387	position = currentPos;
1388
1389	pvsBack = pvsl;
1390	pvsFront = pvsr;
1391	}
1392	}
1393	}
1394
1395	/////////
1396	//-- compute cost
1397
1398	const float pOverall = sizeBox;
1399	const float pBack = position - minBox;
1400	const float pFront = maxBox - position;
1401
1402	const float penaltyOld = pvsCost;
1403	const float penaltyFront = pvsFront;
1404	const float penaltyBack = pvsBack;
1405
1406	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1407	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1408
1409	if (splitPlaneFound)
1410	{
1411	ratio = newRenderCost / oldRenderCost;
1412	}
1413
1414	#ifdef GTP_DEBUG
1415	cout << "\n((((( eval local cost )))))" << endl
1416	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1417	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1418	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1419	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1420	#endif
1421	return ratio;
1422	}
1423
1424
1425	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1426	AxisAlignedPlane &plane,
1427	float &pFront,
1428	float &pBack)
1429	{
1430	mSplitTimer.Entry();
1431
1432	float nPosition[3];
1433	float nCostRatio[3];
1434	float nProbFront[3];
1435	float nProbBack[3];
1436
1437	// create bounding box of node geometry
1438	AxisAlignedBox3 box = tData.mBoundingBox;
1439
1440	int sAxis = 0;
1441	int bestAxis = -1;
1442
1443	// do we use some kind of specialised "fixed" axis?
1444	const bool useSpecialAxis =
1445	mOnlyDrivingAxis \|\| mCirculatingAxis;
1446
1447	// get subset of rays
1448	RayInfoContainer randomRays;
1449	randomRays.reserve(min(mMaxTests, (int)tData.mRays->size()));
1450
1451	RayInfoContainer *usedRays;
1452
1453	if (mMaxTests < (int)tData.mRays->size())
1454	{
1455	GetRayInfoSets(*tData.mRays, mMaxTests, randomRays);
1456	usedRays = &randomRays;
1457	}
1458	else
1459	{
1460	usedRays = tData.mRays;
1461	}
1462
1463	if (mCirculatingAxis)
1464	{
1465	int parentAxis = 0;
1466	VspNode *parent = tData.mNode->GetParent();
1467
1468	if (parent)
1469	{
1470	parentAxis = static_cast<VspInterior *>(parent)->GetAxis();
1471	}
1472
1473	sAxis = (parentAxis + 1) % 3;
1474	}
1475	else if (mOnlyDrivingAxis)
1476	{
1477	sAxis = box.Size().DrivingAxis();
1478	}
1479
1480	for (int axis = 0; axis < 3; ++ axis)
1481	{
1482	if (!useSpecialAxis \|\| (axis == sAxis))
1483	{
1484	if (mUseCostHeuristics)
1485	{
1486	//-- place split plane using heuristics
1487	nCostRatio[axis] =
1488	EvalLocalCostHeuristics(tData,
1489	box,
1490	axis,
1491	nPosition[axis],
1492	*usedRays);
1493	}
1494	else
1495	{
1496	//-- split plane position is spatial median
1497	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1498	nCostRatio[axis] = EvalLocalSplitCost(tData,
1499	box,
1500	axis,
1501	nPosition[axis],
1502	nProbFront[axis],
1503	nProbBack[axis]);
1504	}
1505
1506	if (bestAxis == -1)
1507	{
1508	bestAxis = axis;
1509	}
1510	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1511	{
1512	bestAxis = axis;
1513	}
1514	}
1515	}
1516
1517	/////////////////////////
1518	//-- assign values of best split
1519
1520	plane.mAxis = bestAxis;
1521	// best split plane position
1522	plane.mPosition = nPosition[bestAxis];
1523
1524	pFront = nProbFront[bestAxis];
1525	pBack = nProbBack[bestAxis];
1526
1527	mSplitTimer.Exit();
1528
1529	return nCostRatio[bestAxis];
1530	}
1531
1532
1533	float VspTree::EvalRenderCostDecrease(VspSubdivisionCandidate &sc,
1534	float &normalizedOldRenderCost) const
1535	{
1536	float pvsFront = 0;
1537	float pvsBack = 0;
1538	float totalPvs = 0;
1539
1540	const float viewSpaceVol = mBoundingBox.GetVolume();
1541	const VspTraversalData &tData = sc.mParentData;
1542
1543	const AxisAlignedPlane &candidatePlane = sc.mSplitPlane;
1544	const float avgRayContri = sc.GetAvgRayContribution();
1545
1546	//////////////////////////////////////////////
1547	// mark objects in the front / back / both using mailboxing
1548	// then count pvs sizes
1549
1550	Intersectable::NewMail(3);
1551	KdLeaf::NewMail(3);
1552
1553	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1554
1555	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1556	{
1557	RayInfo rayInf = *rit;
1558
1559	float t;
1560
1561	// classify ray
1562	const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1563	candidatePlane.mPosition,
1564	t);
1565
1566	VssRay *ray = rayInf.mRay;
1567
1568	// evaluate contribution of ray endpoint to front
1569	// and back pvs with respect to the classification
1570	UpdateContributionsToPvs(*ray, true, cf, pvsFront, pvsBack, totalPvs);
1571	#if COUNT_ORIGIN_OBJECTS
1572	UpdateContributionsToPvs(*ray, false, cf, pvsFront, pvsBack, totalPvs);
1573	#endif
1574	}
1575
1576	AxisAlignedBox3 frontBox;
1577	AxisAlignedBox3 backBox;
1578
1579	tData.mBoundingBox.Split(candidatePlane.mAxis,
1580	candidatePlane.mPosition,
1581	frontBox,
1582	backBox);
1583
1584	// probability that view point lies in back / front node
1585	float pOverall = tData.mProbability;
1586	float pFront = frontBox.GetVolume();
1587	float pBack = pOverall - pFront;
1588
1589
1590	///////////////////
1591	//-- evaluate render cost heuristics
1592
1593	const float oldRenderCostRatio = (tData.mRenderCost > 0)?
1594	(totalPvs / tData.mRenderCost) : 1;
1595
1596	const float penaltyOld = tData.mCorrectedRenderCost * oldRenderCostRatio;
1597
1598	sc.mCorrectedFrontRenderCost = mHierarchyManager->EvalCorrectedPvs(pvsFront, penaltyOld, avgRayContri);
1599	sc.mCorrectedBackRenderCost = mHierarchyManager->EvalCorrectedPvs(pvsBack, penaltyOld, avgRayContri);
1600
1601	const float oldRenderCost = pOverall * penaltyOld;
1602	const float newRenderCost = sc.mCorrectedFrontRenderCost * pFront +
1603	sc.mCorrectedBackRenderCost * pBack;
1604
1605	// we also return the old render cost
1606	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1607
1608	// the render cost decrase for this split
1609	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1610
1611	if (0)
1612	cout << "vsp render cost"
1613	<< " avg ray contri: " << avgRayContri << " ratio: " << oldRenderCostRatio
1614	<< " parent: " << penaltyOld << " " << " old vol: " << totalPvs
1615	<< " front cost: " << sc.mCorrectedFrontRenderCost << " corr. " << sc.mCorrectedFrontRenderCost
1616	<< " back cost: " << sc.mCorrectedBackRenderCost << " corr. " << sc.mCorrectedBackRenderCost << endl;
1617
1618	#ifdef GTP_DEBUG
1619	Debug << "\nvsp render cost decrease" << endl
1620	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1621	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1622	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1623	<< "render cost decrease: " << renderCostDecrease << endl;
1624	#endif
1625
1626	return renderCostDecrease;
1627	}
1628
1629
1630	float VspTree::EvalLocalSplitCost(const VspTraversalData &tData,
1631	const AxisAlignedBox3 &box,
1632	const int axis,
1633	const float &position,
1634	float &pFront,
1635	float &pBack) const
1636	{
1637	float pvsTotal = 0;
1638	float pvsFront = 0;
1639	float pvsBack = 0;
1640
1641	// create unique ids for pvs heuristics
1642	Intersectable::NewMail(3);
1643	KdLeaf::NewMail(3);
1644
1645	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1646
1647	// this is the main ray classification loop!
1648	for(rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1649	{
1650	VssRay ray = (rit).mRay;
1651
1652	// determine the side of this ray with respect to the plane
1653	float t;
1654	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1655
1656	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1657	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1658	}
1659
1660	//////////////
1661	//-- evaluate cost heuristics
1662
1663	float pOverall = tData.mProbability;
1664
1665	// we use spatial mid split => simplified computation
1666	pBack = pFront = pOverall * 0.5f;
1667
1668	const float newCost = pvsBack * pBack + pvsFront * pFront;
1669	const float oldCost = (float)pvsTotal * pOverall + Limits::Small;
1670
1671	#ifdef GTPGTP_DEBUG
1672	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1673	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1674	#endif
1675
1676	return (mCtDivCi + newCost) / oldCost;
1677	}
1678
1679
1680	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1681	const int cf,
1682	float &frontPvs,
1683	float &backPvs,
1684	float &totalPvs) const
1685	{
1686	if (!obj) return;
1687
1688	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1689
1690	// object in no pvs => new
1691	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1692	{
1693	totalPvs += renderCost;
1694	}
1695
1696	// QUESTION matt: is it safe to assume that
1697	// the object belongs to no pvs in this case?
1698	//if (cf == Ray::COINCIDENT) return;
1699	if (cf >= 0) // front pvs
1700	{
1701	if (!obj->Mailed() && !obj->Mailed(2))
1702	{
1703	frontPvs += renderCost;
1704
1705	// already in back pvs => in both pvss
1706	if (obj->Mailed(1))
1707	obj->Mail(2);
1708	else
1709	obj->Mail();
1710	}
1711	}
1712
1713	if (cf <= 0) // back pvs
1714	{
1715	if (!obj->Mailed(1) && !obj->Mailed(2))
1716	{
1717	backPvs += renderCost;
1718
1719	// already in front pvs => in both pvss
1720	if (obj->Mailed())
1721	obj->Mail(2);
1722	else
1723	obj->Mail(1);
1724	}
1725	}
1726	}
1727
1728
1729	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1730	const int cf,
1731	float &frontPvs,
1732	float &backPvs,
1733	float &totalPvs,
1734	const bool countEntries) const
1735	{
1736	if (!leaf) return;
1737
1738	const float renderCost = countEntries ? 1 :
1739	mHierarchyManager->mBvHierarchy->EvalAbsCost(leaf->mObjects);
1740
1741	// leaf in no pvs => new
1742	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1743	{
1744	totalPvs += renderCost;
1745	}
1746
1747	if (cf >= 0) // front pvs
1748	{
1749	if (!leaf->Mailed() && !leaf->Mailed(2))
1750	{
1751	frontPvs += renderCost;
1752
1753	// already in back pvs => in both pvss
1754	if (leaf->Mailed(1))
1755	leaf->Mail(2);
1756	else
1757	leaf->Mail();
1758	}
1759	}
1760
1761	if (cf <= 0) // back pvs
1762	{
1763	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1764	{
1765	backPvs += renderCost;
1766
1767	// already in front pvs => in both pvss
1768	if (leaf->Mailed())
1769	leaf->Mail(2);
1770	else
1771	leaf->Mail(1);
1772	}
1773	}
1774	}
1775
1776
1777	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1778	const int cf,
1779	float &frontPvs,
1780	float &backPvs,
1781	float &totalPvs) const
1782	{
1783	if (!leaf) return;
1784
1785	// the objects which are referenced in this and only this leaf
1786	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1787
1788	// newly found leaf
1789	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1790	{
1791	totalPvs += contri;
1792	}
1793
1794	// recursivly update contributions of yet unclassified objects
1795	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1796
1797	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1798	{
1799	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1800	}
1801
1802	if (cf >= 0) // front pvs
1803	{
1804	if (!leaf->Mailed() && !leaf->Mailed(2))
1805	{
1806	frontPvs += contri;
1807
1808	// already in back pvs => in both pvss
1809	if (leaf->Mailed(1))
1810	leaf->Mail(2);
1811	else
1812	leaf->Mail();
1813	}
1814	}
1815
1816	if (cf <= 0) // back pvs
1817	{
1818	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1819	{
1820	backPvs += contri;
1821
1822	// already in front pvs => in both pvss
1823	if (leaf->Mailed())
1824	leaf->Mail(2);
1825	else
1826	leaf->Mail(1);
1827	}
1828	}
1829	}
1830
1831
1832	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1833	const bool onlyUnmailed,
1834	const int maxPvsSize) const
1835	{
1836	stack<VspNode *> nodeStack;
1837	nodeStack.push(mRoot);
1838
1839	while (!nodeStack.empty())
1840	{
1841	VspNode *node = nodeStack.top();
1842	nodeStack.pop();
1843
1844	if (node->IsLeaf())
1845	{
1846	// test if this leaf is in valid view space
1847	VspLeaf leaf = static_cast<VspLeaf >(node);
1848
1849	if (leaf->TreeValid() &&
1850	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1851	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().EvalPvsCost() <= maxPvsSize)))
1852	{
1853	leaves.push_back(leaf);
1854	}
1855	}
1856	else
1857	{
1858	VspInterior interior = static_cast<VspInterior >(node);
1859
1860	nodeStack.push(interior->GetBack());
1861	nodeStack.push(interior->GetFront());
1862	}
1863	}
1864	}
1865
1866
1867	AxisAlignedBox3 VspTree::GetBoundingBox() const
1868	{
1869	return mBoundingBox;
1870	}
1871
1872
1873	VspNode *VspTree::GetRoot() const
1874	{
1875	return mRoot;
1876	}
1877
1878
1879	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1880	{
1881	// the node became a leaf -> evaluate stats for leafs
1882	VspLeaf leaf = static_cast<VspLeaf >(data.mNode);
1883
1884	if (data.mPvs > mVspStats.maxPvs)
1885	{
1886	mVspStats.maxPvs = (int)data.mPvs;
1887	}
1888
1889	mVspStats.pvs += (int)data.mPvs;
1890
1891	if (data.mDepth < mVspStats.minDepth)
1892	{
1893	mVspStats.minDepth = data.mDepth;
1894	}
1895
1896	if (data.mDepth >= mTermMaxDepth)
1897	{
1898	++ mVspStats.maxDepthNodes;
1899	}
1900
1901	// accumulate rays to compute rays / leaf
1902	mVspStats.rayRefs += (int)data.mRays->size();
1903
1904	if (data.mPvs < mTermMinPvs)
1905	++ mVspStats.minPvsNodes;
1906
1907	if ((int)data.mRays->size() < mTermMinRays)
1908	++ mVspStats.minRaysNodes;
1909
1910	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1911	++ mVspStats.maxRayContribNodes;
1912
1913	if (data.mProbability <= mTermMinProbability)
1914	++ mVspStats.minProbabilityNodes;
1915
1916	// accumulate depth to compute average depth
1917	mVspStats.accumDepth += data.mDepth;
1918
1919	++ mCreatedViewCells;
1920
1921	#ifdef GTP_DEBUG
1922	Debug << "BSP stats: "
1923	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1924	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1925	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1926	<< "#pvs: " << leaf->GetViewCell()->GetPvs().EvalPvsCost() << "), "
1927	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1928	#endif
1929	}
1930
1931
1932	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1933	{
1934	ViewCell::NewMail();
1935	CollectViewCells(mRoot, onlyValid, viewCells, true);
1936	}
1937
1938
1939	void VspTree::CollapseViewCells()
1940	{
1941	// TODO matt
1942	#if HAS_TO_BE_REDONE
1943	stack<VspNode *> nodeStack;
1944
1945	if (!mRoot)
1946	return;
1947
1948	nodeStack.push(mRoot);
1949
1950	while (!nodeStack.empty())
1951	{
1952	VspNode *node = nodeStack.top();
1953	nodeStack.pop();
1954
1955	if (node->IsLeaf())
1956	{
1957	BspViewCell viewCell = static_cast<VspLeaf >(node)->GetViewCell();
1958
1959	if (!viewCell->GetValid())
1960	{
1961	BspViewCell viewCell = static_cast<VspLeaf >(node)->GetViewCell();
1962
1963	ViewCellContainer leaves;
1964	mViewCellsTree->CollectLeaves(viewCell, leaves);
1965
1966	ViewCellContainer::const_iterator it, it_end = leaves.end();
1967
1968	for (it = leaves.begin(); it != it_end; ++ it)
1969	{
1970	VspLeaf l = static_cast<BspViewCell >(*it)->mLeaf;
1971	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1972	++ mVspStats.invalidLeaves;
1973	}
1974
1975	// add to unbounded view cell
1976	ViewCell *outOfBounds = GetOrCreateOutOfBoundsCell();
1977	outOfBounds->GetPvs().AddPvs(viewCell->GetPvs());
1978	DEL_PTR(viewCell);
1979	}
1980	}
1981	else
1982	{
1983	VspInterior interior = static_cast<VspInterior >(node);
1984
1985	nodeStack.push(interior->GetFront());
1986	nodeStack.push(interior->GetBack());
1987	}
1988	}
1989
1990	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1991	#endif
1992	}
1993
1994
1995	void VspTree::CollectRays(VssRayContainer &rays)
1996	{
1997	vector<VspLeaf *> leaves;
1998	CollectLeaves(leaves);
1999
2000	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
2001
2002	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2003	{
2004	VspLeaf leaf = lit;
2005	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2006
2007	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2008	rays.push_back(*rit);
2009	}
2010	}
2011
2012
2013	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
2014	{
2015	mViewCellsManager = vcm;
2016	}
2017
2018
2019	void VspTree::ValidateTree()
2020	{
2021	if (!mRoot)
2022	return;
2023
2024	mVspStats.invalidLeaves = 0;
2025	stack<VspNode *> nodeStack;
2026
2027	nodeStack.push(mRoot);
2028
2029	while (!nodeStack.empty())
2030	{
2031	VspNode *node = nodeStack.top();
2032	nodeStack.pop();
2033
2034	if (node->IsLeaf())
2035	{
2036	VspLeaf leaf = static_cast<VspLeaf >(node);
2037
2038	if (!leaf->GetViewCell()->GetValid())
2039	++ mVspStats.invalidLeaves;
2040
2041	// validity flags don't match => repair
2042	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2043	{
2044	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2045	PropagateUpValidity(leaf);
2046	}
2047	}
2048	else
2049	{
2050	VspInterior interior = static_cast<VspInterior >(node);
2051
2052	nodeStack.push(interior->GetFront());
2053	nodeStack.push(interior->GetBack());
2054	}
2055	}
2056
2057	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
2058	}
2059
2060
2061
2062	void VspTree::CollectViewCells(VspNode *root,
2063	bool onlyValid,
2064	ViewCellContainer &viewCells,
2065	bool onlyUnmailed) const
2066	{
2067	if (!root)
2068	return;
2069
2070	stack<VspNode *> nodeStack;
2071	nodeStack.push(root);
2072
2073	while (!nodeStack.empty())
2074	{
2075	VspNode *node = nodeStack.top();
2076	nodeStack.pop();
2077
2078	if (node->IsLeaf())
2079	{
2080	if (!onlyValid \|\| node->TreeValid())
2081	{
2082	ViewCellLeaf leafVc = static_cast<VspLeaf >(node)->GetViewCell();
2083
2084	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2085
2086	if (!onlyUnmailed \|\| !viewCell->Mailed())
2087	{
2088	viewCell->Mail();
2089	viewCells.push_back(viewCell);
2090	}
2091	}
2092	}
2093	else
2094	{
2095	VspInterior interior = static_cast<VspInterior >(node);
2096
2097	nodeStack.push(interior->GetFront());
2098	nodeStack.push(interior->GetBack());
2099	}
2100	}
2101	}
2102
2103
2104	int VspTree::FindNeighbors(VspLeaf *n,
2105	vector<VspLeaf *> &neighbors,
2106	const bool onlyUnmailed) const
2107	{
2108	stack<VspNode *> nodeStack;
2109	nodeStack.push(mRoot);
2110
2111	const AxisAlignedBox3 box = GetBoundingBox(n);
2112
2113	while (!nodeStack.empty())
2114	{
2115	VspNode *node = nodeStack.top();
2116	nodeStack.pop();
2117
2118	if (node->IsLeaf())
2119	{
2120	VspLeaf leaf = static_cast<VspLeaf >(node);
2121
2122	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
2123	neighbors.push_back(leaf);
2124	}
2125	else
2126	{
2127	VspInterior interior = static_cast<VspInterior >(node);
2128
2129	if (interior->GetPosition() > box.Max(interior->GetAxis()))
2130	nodeStack.push(interior->GetBack());
2131	else
2132	{
2133	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2134	nodeStack.push(interior->GetFront());
2135	else
2136	{
2137	// random decision
2138	nodeStack.push(interior->GetBack());
2139	nodeStack.push(interior->GetFront());
2140	}
2141	}
2142	}
2143	}
2144
2145	return (int)neighbors.size();
2146	}
2147
2148
2149	// Find random neighbor which was not mailed
2150	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2151	{
2152	stack<VspNode *> nodeStack;
2153	nodeStack.push(mRoot);
2154
2155	int mask = rand();
2156
2157	while (!nodeStack.empty())
2158	{
2159	VspNode *node = nodeStack.top();
2160
2161	nodeStack.pop();
2162
2163	if (node->IsLeaf())
2164	{
2165	return static_cast<VspLeaf *>(node);
2166	}
2167	else
2168	{
2169	VspInterior interior = static_cast<VspInterior >(node);
2170	VspNode *next;
2171
2172	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2173	{
2174	next = interior->GetFront();
2175	}
2176	else
2177	{
2178	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2179	{
2180	next = interior->GetBack();
2181	}
2182	else
2183	{
2184	// random decision
2185	if (mask & 1)
2186	next = interior->GetBack();
2187	else
2188	next = interior->GetFront();
2189	mask = mask >> 1;
2190	}
2191	}
2192
2193	nodeStack.push(next);
2194	}
2195	}
2196
2197	return NULL;
2198	}
2199
2200
2201	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2202	{
2203	stack<VspNode *> nodeStack;
2204
2205	nodeStack.push(mRoot);
2206
2207	int mask = rand();
2208
2209	while (!nodeStack.empty())
2210	{
2211	VspNode *node = nodeStack.top();
2212	nodeStack.pop();
2213
2214	if (node->IsLeaf())
2215	{
2216	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2217	return static_cast<VspLeaf *>(node);
2218	}
2219	else
2220	{
2221	VspInterior interior = static_cast<VspInterior >(node);
2222
2223	// random decision
2224	if (mask & 1)
2225	nodeStack.push(interior->GetBack());
2226	else
2227	nodeStack.push(interior->GetFront());
2228
2229	mask = mask >> 1;
2230	}
2231	}
2232
2233	return NULL;
2234	}
2235
2236
2237	float VspTree::EvalPvsCost(const RayInfoContainer &rays) const
2238	{
2239	float pvsCost = 0;
2240
2241	Intersectable::NewMail();
2242	KdNode::NewMail();
2243
2244	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2245
2246	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2247	{
2248	VssRay ray = (rit).mRay;
2249
2250	pvsCost += EvalContributionToPvs(*ray, true);
2251
2252	#if COUNT_ORIGIN_OBJECTS
2253	pvsCost += EvalContributionToPvs(*ray, false);
2254	#endif
2255	}
2256
2257	return pvsCost;
2258	}
2259
2260
2261	int VspTree::EvalPvsEntriesContribution(const VssRay &ray,
2262	const bool isTermination) const
2263
2264	{
2265	Intersectable *obj;
2266	Vector3 pt;
2267	KdNode *node;
2268
2269	ray.GetSampleData(isTermination, pt, &obj, &node);
2270	if (!obj) return 0;
2271
2272	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
2273	{
2274	case HierarchyManager::NO_OBJ_SUBDIV:
2275	{
2276	if (!obj->Mailed())
2277	{
2278	obj->Mail();
2279	return 1;
2280	}
2281
2282	return 0;
2283	}
2284
2285	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2286	{
2287	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2288	if (!leaf->Mailed())
2289	{
2290	leaf->Mail();
2291	return 1;
2292	}
2293
2294	return 0;
2295	}
2296	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2297	{
2298	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2299
2300	if (!bvhleaf->Mailed())
2301	{
2302	bvhleaf->Mail();
2303	return 1;
2304	}
2305
2306	return 0;
2307	}
2308	default:
2309	break;
2310	}
2311
2312	return 0;
2313	}
2314
2315
2316	int VspTree::EvalPvsEntriesSize(const RayInfoContainer &rays) const
2317	{
2318	int pvsSize = 0;
2319
2320	Intersectable::NewMail();
2321	KdNode::NewMail();
2322
2323	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2324
2325	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2326	{
2327	VssRay ray = (rit).mRay;
2328
2329	pvsSize += EvalPvsEntriesContribution(*ray, true);
2330
2331	#if COUNT_ORIGIN_OBJECTS
2332	pvsSize += EvalPvsEntriesContribution(*ray, false);
2333	#endif
2334	}
2335
2336	return pvsSize;
2337	}
2338
2339
2340	float VspTree::GetEpsilon() const
2341	{
2342	return mEpsilon;
2343	}
2344
2345
2346	int VspTree::CastLineSegment(const Vector3 &origin,
2347	const Vector3 &termination,
2348	ViewCellContainer &viewcells,
2349	const bool useMailboxing)
2350	{
2351	int hits = 0;
2352
2353	float mint = 0.0f, maxt = 1.0f;
2354	const Vector3 dir = termination - origin;
2355
2356	stack<LineTraversalData> tStack;
2357
2358	Vector3 entp = origin;
2359	Vector3 extp = termination;
2360
2361	VspNode *node = mRoot;
2362	VspNode *farChild;
2363
2364	float position;
2365	int axis;
2366
2367	while (1)
2368	{
2369	if (!node->IsLeaf())
2370	{
2371	VspInterior in = static_cast<VspInterior >(node);
2372	position = in->GetPosition();
2373	axis = in->GetAxis();
2374
2375	if (entp[axis] <= position)
2376	{
2377	if (extp[axis] <= position)
2378	{
2379	node = in->GetBack();
2380	// cases N1,N2,N3,P5,Z2,Z3
2381	continue;
2382	} else
2383	{
2384	// case N4
2385	node = in->GetBack();
2386	farChild = in->GetFront();
2387	}
2388	}
2389	else
2390	{
2391	if (position <= extp[axis])
2392	{
2393	node = in->GetFront();
2394	// cases P1,P2,P3,N5,Z1
2395	continue;
2396	}
2397	else
2398	{
2399	node = in->GetFront();
2400	farChild = in->GetBack();
2401	// case P4
2402	}
2403	}
2404
2405	// $$ modification 3.5.2004 - hints from Kamil Ghais
2406	// case N4 or P4
2407	const float tdist = (position - origin[axis]) / dir[axis];
2408	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2409
2410	extp = origin + dir * tdist;
2411	maxt = tdist;
2412	}
2413	else
2414	{
2415	// compute intersection with all objects in this leaf
2416	VspLeaf leaf = static_cast<VspLeaf >(node);
2417	ViewCell *viewCell;
2418
2419	if (0)
2420	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2421	else
2422	viewCell = leaf->GetViewCell();
2423
2424	// don't have to mail if each view cell belongs to exactly one leaf
2425	if (!useMailboxing \|\| !viewCell->Mailed())
2426	{
2427	if (useMailboxing)
2428	viewCell->Mail();
2429
2430	viewcells.push_back(viewCell);
2431	++ hits;
2432	}
2433
2434	// get the next node from the stack
2435	if (tStack.empty())
2436	break;
2437
2438	entp = extp;
2439	mint = maxt;
2440
2441	LineTraversalData &s = tStack.top();
2442	node = s.mNode;
2443	extp = s.mExitPoint;
2444	maxt = s.mMaxT;
2445
2446	tStack.pop();
2447	}
2448	}
2449
2450	return hits;
2451	}
2452
2453
2454	int VspTree::CastRay(Ray &ray)
2455	{
2456	int hits = 0;
2457
2458	stack<LineTraversalData> tStack;
2459	const Vector3 dir = ray.GetDir();
2460
2461	float maxt, mint;
2462
2463	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2464	return 0;
2465
2466	Intersectable::NewMail();
2467	ViewCell::NewMail();
2468
2469	Vector3 entp = ray.Extrap(mint);
2470	Vector3 extp = ray.Extrap(maxt);
2471
2472	const Vector3 origin = entp;
2473
2474	VspNode *node = mRoot;
2475	VspNode *farChild = NULL;
2476
2477	float position;
2478	int axis;
2479
2480	while (1)
2481	{
2482	if (!node->IsLeaf())
2483	{
2484	VspInterior in = static_cast<VspInterior >(node);
2485	position = in->GetPosition();
2486	axis = in->GetAxis();
2487
2488	if (entp[axis] <= position)
2489	{
2490	if (extp[axis] <= position)
2491	{
2492	node = in->GetBack();
2493	// cases N1,N2,N3,P5,Z2,Z3
2494	continue;
2495	}
2496	else
2497	{
2498	// case N4
2499	node = in->GetBack();
2500	farChild = in->GetFront();
2501	}
2502	}
2503	else
2504	{
2505	if (position <= extp[axis])
2506	{
2507	node = in->GetFront();
2508	// cases P1,P2,P3,N5,Z1
2509	continue;
2510	}
2511	else
2512	{
2513	node = in->GetFront();
2514	farChild = in->GetBack();
2515	// case P4
2516	}
2517	}
2518
2519	// $$ modification 3.5.2004 - hints from Kamil Ghais
2520	// case N4 or P4
2521	const float tdist = (position - origin[axis]) / dir[axis];
2522	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2523	extp = origin + dir * tdist;
2524	maxt = tdist;
2525	}
2526	else
2527	{
2528	// compute intersection with all objects in this leaf
2529	VspLeaf leaf = static_cast<VspLeaf >(node);
2530	ViewCell *vc = leaf->GetViewCell();
2531
2532	if (!vc->Mailed())
2533	{
2534	vc->Mail();
2535	// todo: add view cells to ray
2536	++ hits;
2537	}
2538
2539	// get the next node from the stack
2540	if (tStack.empty())
2541	break;
2542
2543	entp = extp;
2544	mint = maxt;
2545
2546	LineTraversalData &s = tStack.top();
2547	node = s.mNode;
2548	extp = s.mExitPoint;
2549	maxt = s.mMaxT;
2550	tStack.pop();
2551	}
2552	}
2553
2554	return hits;
2555	}
2556
2557
2558	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2559	{
2560	if (!mRoot)
2561	return NULL;
2562
2563	stack<VspNode *> nodeStack;
2564	nodeStack.push(mRoot);
2565
2566	ViewCellLeaf *viewcell = NULL;
2567
2568	while (!nodeStack.empty())
2569	{
2570	VspNode *node = nodeStack.top();
2571	nodeStack.pop();
2572
2573	if (node->IsLeaf())
2574	{
2575	/const AxisAlignedBox3 box = GetBoundingBox(static_cast<VspLeaf >(node));
2576	if (!box.IsInside(point))
2577	cerr << "error, point " << point << " should be in view cell " << box << endl;
2578	*/
2579	viewcell = static_cast<VspLeaf *>(node)->GetViewCell();
2580	break;
2581	}
2582	else
2583	{
2584	VspInterior interior = static_cast<VspInterior >(node);
2585
2586	// random decision
2587	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2588	{
2589	nodeStack.push(interior->GetFront());
2590	}
2591	else
2592	{
2593	nodeStack.push(interior->GetBack());
2594	}
2595	}
2596	}
2597
2598	// return active or leaf view cell
2599	if (active)
2600	{
2601	return mViewCellsTree->GetActiveViewCell(viewcell);
2602	}
2603	else
2604	{
2605	return viewcell;
2606	}
2607	}
2608
2609
2610	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2611	{
2612	VspNode *node = mRoot;
2613
2614	while (1)
2615	{
2616	// early exit
2617	if (node->TreeValid())
2618	return true;
2619
2620	if (node->IsLeaf())
2621	return false;
2622
2623	VspInterior in = static_cast<VspInterior >(node);
2624
2625	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2626	{
2627	node = in->GetBack();
2628	}
2629	else
2630	{
2631	node = in->GetFront();
2632	}
2633	}
2634
2635	// should never come here
2636	return false;
2637	}
2638
2639
2640	void VspTree::PropagateUpValidity(VspNode *node)
2641	{
2642	const bool isValid = node->TreeValid();
2643
2644	// propagative up invalid flag until only invalid nodes exist over this node
2645	if (!isValid)
2646	{
2647	while (!node->IsRoot() && node->GetParent()->TreeValid())
2648	{
2649	node = node->GetParent();
2650	node->SetTreeValid(false);
2651	}
2652	}
2653	else
2654	{
2655	// propagative up valid flag until one of the subtrees is invalid
2656	while (!node->IsRoot() && !node->TreeValid())
2657	{
2658	node = node->GetParent();
2659	VspInterior interior = static_cast<VspInterior >(node);
2660
2661	// the parent is valid iff both leaves are valid
2662	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2663	interior->GetFront()->TreeValid());
2664	}
2665	}
2666	}
2667
2668
2669	bool VspTree::Export(OUT_STREAM &stream)
2670	{
2671	ExportNode(mRoot, stream);
2672
2673	return true;
2674	}
2675
2676
2677	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2678	{
2679	if (node->IsLeaf())
2680	{
2681	VspLeaf leaf = static_cast<VspLeaf >(node);
2682	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2683
2684	int id = -1;
2685	if (viewCell != mOutOfBoundsCell)
2686	id = viewCell->GetId();
2687
2688	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2689	}
2690	else
2691	{
2692	VspInterior interior = static_cast<VspInterior >(node);
2693
2694	AxisAlignedPlane plane = interior->GetPlane();
2695	stream << "<Interior plane=\"" << plane.mPosition << " "
2696	<< plane.mAxis << "\">" << endl;
2697
2698	ExportNode(interior->GetBack(), stream);
2699	ExportNode(interior->GetFront(), stream);
2700
2701	stream << "</Interior>" << endl;
2702	}
2703	}
2704
2705
2706	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2707	RayInfoContainer &rays,
2708	RayInfoContainer &frontRays,
2709	RayInfoContainer &backRays) const
2710	{
2711	int splits = 0;
2712
2713	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2714
2715	for (rit = rays.begin(); rit != rit_end; ++ rit)
2716	{
2717	RayInfo bRay = *rit;
2718
2719	VssRay *ray = bRay.mRay;
2720	float t;
2721
2722	// get classification and receive new t
2723	// test if start point behind or in front of plane
2724	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2725
2726	if (side == 0)
2727	{
2728	++ splits;
2729
2730	if (ray->HasPosDir(plane.mAxis))
2731	{
2732	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2733	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2734	}
2735	else
2736	{
2737	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2738	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2739	}
2740	}
2741	else if (side == 1)
2742	{
2743	frontRays.push_back(bRay);
2744	}
2745	else
2746	{
2747	backRays.push_back(bRay);
2748	}
2749	}
2750
2751	return splits;
2752	}
2753
2754
2755	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2756	{
2757	if (!node->GetParent())
2758	return mBoundingBox;
2759
2760	if (!node->IsLeaf())
2761	{
2762	return (static_cast<VspInterior *>(node))->GetBoundingBox();
2763	}
2764
2765	VspInterior parent = static_cast<VspInterior >(node->GetParent());
2766
2767	AxisAlignedBox3 box(parent->GetBoundingBox());
2768
2769	if (parent->GetFront() == node)
2770	box.SetMin(parent->GetAxis(), parent->GetPosition());
2771	else
2772	box.SetMax(parent->GetAxis(), parent->GetPosition());
2773
2774	return box;
2775	}
2776
2777
2778	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2779	ViewCellContainer &viewCells) const
2780	{
2781	stack<VspNode *> nodeStack;
2782
2783	ViewCell::NewMail();
2784
2785	nodeStack.push(mRoot);
2786
2787	while (!nodeStack.empty())
2788	{
2789	VspNode *node = nodeStack.top();
2790	nodeStack.pop();
2791
2792	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2793
2794	if (Overlap(bbox, box))
2795	{
2796	if (node->IsLeaf())
2797	{
2798	VspLeaf leaf = static_cast<VspLeaf >(node);
2799
2800	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2801	{
2802	leaf->GetViewCell()->Mail();
2803	viewCells.push_back(leaf->GetViewCell());
2804	}
2805	}
2806	else
2807	{
2808	VspInterior interior = static_cast<VspInterior >(node);
2809
2810	VspNode *first = interior->GetFront();
2811	VspNode *second = interior->GetBack();
2812
2813	nodeStack.push(first);
2814	nodeStack.push(second);
2815	}
2816	}
2817	// default: cull
2818	}
2819
2820	return (int)viewCells.size();
2821	}
2822
2823
2824	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2825	RayInfoContainer &rays)
2826	{
2827	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2828
2829	long startTime = GetTime();
2830
2831	cout << "storing rays ... ";
2832
2833	Intersectable::NewMail();
2834
2835	//-- store rays and objects
2836	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2837	{
2838	VssRay ray = rit;
2839	float minT, maxT;
2840	static Ray hray;
2841
2842	hray.Init(*ray);
2843
2844	// TODO: not very efficient to implictly cast between rays types
2845	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2846	{
2847	float len = ray->Length();
2848
2849	if (!len)
2850	len = Limits::Small;
2851
2852	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2853	}
2854	}
2855
2856	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2857	}
2858
2859
2860	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2861	{
2862	mViewCellsTimer.Entry();
2863
2864	static Ray hray;
2865	hray.Init(ray);
2866
2867	float tmin = 0, tmax = 1.0;
2868
2869	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2870	return;
2871
2872	const Vector3 origin = hray.Extrap(tmin);
2873	const Vector3 termination = hray.Extrap(tmax);
2874
2875	// view cells were not precomputed and are extracted on the fly
2876	// don't mail because the same view cells can be found for different rays
2877	CastLineSegment(origin, termination, viewCells, false);
2878
2879	mViewCellsTimer.Exit();
2880	}
2881
2882
2883	void VspTree::Initialise(const VssRayContainer &rays,
2884	AxisAlignedBox3 *forcedBoundingBox)
2885	{
2886	ComputeBoundingBox(rays, forcedBoundingBox);
2887
2888	VspLeaf *leaf = new VspLeaf();
2889	mRoot = leaf;
2890
2891	VspViewCell *viewCell = new VspViewCell();
2892	leaf->SetViewCell(viewCell);
2893
2894	// set view cell values
2895	viewCell->mLeaves.push_back(leaf);
2896	viewCell->SetVolume(mBoundingBox.GetVolume());
2897
2898	leaf->mProbability = mBoundingBox.GetVolume();
2899	}
2900
2901
2902	void VspTree::PrepareConstruction(SplitQueue &tQueue,
2903	const VssRayContainer &sampleRays,
2904	RayInfoContainer &rays)
2905	{
2906	mVspStats.Reset();
2907	mVspStats.Start();
2908	mVspStats.nodes = 1;
2909
2910	// store pointer to this tree
2911	VspSubdivisionCandidate::sVspTree = this;
2912
2913	// initialise termination criteria
2914	mTermMinProbability *= mBoundingBox.GetVolume();
2915
2916	// get clipped rays
2917	PreprocessRays(sampleRays, rays);
2918
2919	/// collect pvs from rays
2920	const float pvsCost = EvalPvsCost(rays);
2921
2922	// root and bounding box were already constructed
2923	VspLeaf leaf = static_cast<VspLeaf >(mRoot);
2924
2925	//////////
2926	//-- prepare view space partition
2927
2928	const float prop = mBoundingBox.GetVolume();
2929
2930	// first vsp traversal data
2931	VspTraversalData vData(leaf, 0, &rays, pvsCost, prop, mBoundingBox);
2932
2933	#if WORK_WITH_VIEWCELL_PVS
2934	// add first view cell to all the objects view cell pvs
2935	ObjectPvsEntries::const_iterator oit,
2936	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2937
2938	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2939	{
2940	Intersectable obj = (oit).first;
2941	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2942	}
2943	#endif
2944
2945	mTotalCost = vData.mCorrectedRenderCost = vData.mRenderCost = pvsCost;
2946	mPvsEntries = EvalPvsEntriesSize(rays);
2947	vData.mCorrectedPvs = vData.mPvs = (float)mPvsEntries;
2948
2949	//////////////
2950	//-- create the first split candidate
2951
2952	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2953	EvalSubdivisionCandidate(*splitCandidate);
2954	leaf->SetSubdivisionCandidate(splitCandidate);
2955
2956	EvalSubdivisionStats(*splitCandidate);
2957
2958	tQueue.Push(splitCandidate);
2959	}
2960
2961
2962	void VspTree::CollectDirtyCandidate(const VssRay &ray,
2963	const bool isTermination,
2964	vector<SubdivisionCandidate *> &dirtyList,
2965	const bool onlyUnmailed) const
2966	{
2967
2968	Intersectable *obj;
2969	Vector3 pt;
2970	KdNode *node;
2971
2972	ray.GetSampleData(isTermination, pt, &obj, &node);
2973
2974	if (!obj) return;
2975
2976	SubdivisionCandidate *candidate = NULL;
2977
2978	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2979	{
2980	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2981	{
2982	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2983
2984	if (!leaf->Mailed())
2985	{
2986	leaf->Mail();
2987	candidate = leaf->mSubdivisionCandidate;
2988	}
2989	break;
2990	}
2991	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2992	{
2993	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2994
2995	if (!leaf->Mailed())
2996	{
2997	leaf->Mail();
2998	candidate = leaf->GetSubdivisionCandidate();
2999	}
3000	break;
3001	}
3002	default:
3003	cerr << "not implemented yet" << endl;
3004	candidate = NULL;
3005	break;
3006	}
3007
3008	// is this leaf still a split candidate?
3009	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
3010	{
3011	candidate->Mail();
3012	candidate->SetDirty(true);
3013	dirtyList.push_back(candidate);
3014	}
3015	}
3016
3017
3018	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
3019	vector<SubdivisionCandidate *> &dirtyList,
3020	const bool onlyUnmailed)
3021	{
3022	VspTraversalData &tData = sc->mParentData;
3023	VspLeaf *node = tData.mNode;
3024
3025	KdLeaf::NewMail();
3026	Intersectable::NewMail();
3027
3028	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
3029
3030	// add all kd nodes seen by the rays
3031	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
3032	{
3033	VssRay ray = (rit).mRay;
3034
3035	CollectDirtyCandidate(*ray, true, dirtyList, onlyUnmailed);
3036	CollectDirtyCandidate(*ray, false, dirtyList, onlyUnmailed);
3037	}
3038	}
3039
3040
3041	int VspTree::EvalMaxEventContribution(const VssRay &ray,
3042	const bool isTermination) const
3043	{
3044	Intersectable *obj;
3045	Vector3 pt;
3046	KdNode *node;
3047
3048	ray.GetSampleData(isTermination, pt, &obj, &node);
3049
3050	if (!obj)
3051	return 0;
3052
3053	int pvs = 0;
3054
3055	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3056	{
3057	case HierarchyManager::NO_OBJ_SUBDIV:
3058	{
3059	if (-- obj->mCounter == 0)
3060	++ pvs;
3061	break;
3062	}
3063	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3064	{
3065	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3066
3067	// add contributions of the kd nodes
3068	pvs += EvalMaxEventContribution(leaf);
3069	break;
3070	}
3071	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3072	{
3073	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3074
3075	if (-- leaf->mCounter == 0)
3076	pvs += (int)leaf->mObjects.size();
3077	break;
3078	}
3079	default:
3080	break;
3081	}
3082
3083	return pvs;
3084	}
3085
3086
3087	float VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
3088	{
3089	float pvsSize = 0;
3090
3091	Intersectable *obj;
3092	Vector3 pt;
3093	KdNode *node;
3094
3095	ray.GetSampleData(isTermination, pt, &obj, &node);
3096
3097	if (!obj)
3098	return 0;
3099
3100	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3101	{
3102	case HierarchyManager::NO_OBJ_SUBDIV:
3103	{
3104	if (!obj->Mailed())
3105	{
3106	obj->Mail();
3107	obj->mCounter = 0;
3108	++ pvsSize;
3109	}
3110
3111	++ obj->mCounter;
3112	break;
3113	}
3114	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3115	{
3116	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3117	pvsSize += PrepareHeuristics(leaf);
3118	break;
3119	}
3120	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3121	{
3122	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3123
3124	if (!leaf->Mailed())
3125	{
3126	leaf->Mail();
3127	leaf->mCounter = 0;
3128	pvsSize += (int)leaf->mObjects.size();
3129	}
3130
3131	++ leaf->mCounter;
3132	break;
3133	}
3134	default:
3135	break;
3136	}
3137
3138	return pvsSize;
3139	}
3140
3141
3142	int VspTree::EvalMinEventContribution(const VssRay &ray,
3143	const bool isTermination) const
3144	{
3145	Intersectable *obj;
3146	Vector3 pt;
3147	KdNode *node;
3148
3149	ray.GetSampleData(isTermination, pt, &obj, &node);
3150
3151	if (!obj) return 0;
3152
3153	int pvs = 0;
3154
3155	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3156	{
3157	case HierarchyManager::NO_OBJ_SUBDIV:
3158	{
3159	if (!obj->Mailed())
3160	{
3161	obj->Mail();
3162	++ pvs;
3163	}
3164	break;
3165	}
3166	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3167	{
3168	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3169	// add contributions of the kd nodes
3170	pvs += EvalMinEventContribution(leaf);
3171	break;
3172	}
3173	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3174	{
3175	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3176	if (!leaf->Mailed())
3177	{
3178	leaf->Mail();
3179	pvs += (int)leaf->mObjects.size();
3180	}
3181	break;
3182	}
3183	default:
3184	break;
3185	}
3186
3187	return pvs;
3188	}
3189
3190
3191	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
3192	const bool isTermination,
3193	const int cf,
3194	float &frontPvs,
3195	float &backPvs,
3196	float &totalPvs) const
3197	{
3198	Intersectable *obj;
3199	Vector3 pt;
3200	KdNode *node;
3201
3202	ray.GetSampleData(isTermination, pt, &obj, &node);
3203
3204	if (!obj) return;
3205
3206	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3207	{
3208	case HierarchyManager::NO_OBJ_SUBDIV:
3209	{
3210	// find front and back pvs for origing and termination object
3211	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
3212	break;
3213	}
3214	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3215	{
3216	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3217	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
3218	break;
3219	}
3220	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3221	{
3222	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3223	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
3224	break;
3225	}
3226	}
3227	}
3228
3229
3230	void VspTree::UpdatePvsEntriesContribution(const VssRay &ray,
3231	const bool isTermination,
3232	const int cf,
3233	float &pvsFront,
3234	float &pvsBack,
3235	float &totalPvs) const
3236	{
3237	Intersectable *obj;
3238	Vector3 pt;
3239	KdNode *node;
3240
3241	ray.GetSampleData(isTermination, pt, &obj, &node);
3242	if (!obj) return;
3243
3244	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3245	{
3246	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3247	// TODO
3248	break;
3249	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3250	{
3251	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3252	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3253	break;
3254	}
3255	default:
3256	UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs);
3257	break;
3258	}
3259	}
3260
3261
3262	int VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
3263	{
3264	Intersectable *obj;
3265	Vector3 pt;
3266	KdNode *node;
3267
3268	ray.GetSampleData(isTermination, pt, &obj, &node);
3269
3270	if (!obj) return 0;
3271
3272	int pvs = 0;
3273
3274	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3275	{
3276	case HierarchyManager::NO_OBJ_SUBDIV:
3277	{
3278	if (!obj->Mailed())
3279	{
3280	obj->Mail();
3281	++ pvs;
3282	}
3283	break;
3284	}
3285	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3286	{
3287	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3288	pvs += EvalContributionToPvs(leaf);
3289	break;
3290	}
3291	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3292	{
3293	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3294
3295	if (!bvhleaf->Mailed())
3296	{
3297	bvhleaf->Mail();
3298	pvs += (int)bvhleaf->mObjects.size();
3299	}
3300	break;
3301	}
3302	default:
3303	break;
3304	}
3305
3306	return pvs;
3307	}
3308
3309
3310	int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3311	{
3312	if (leaf->Mailed()) // leaf already mailed
3313	return 0;
3314
3315	leaf->Mail();
3316
3317	// this is the pvs which is uniquely part of this kd leaf
3318	int pvs = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3319
3320	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3321
3322	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3323	{
3324	Intersectable obj = oit;
3325	if (!obj->Mailed())
3326	{
3327	obj->Mail();
3328	++ pvs;
3329	}
3330	}
3331
3332	return pvs;
3333	}
3334
3335
3336	VspNode *VspTree::SubdivideAndCopy(SplitQueue &tQueue,
3337	SubdivisionCandidate *splitCandidate)
3338	{
3339	// todo remove dynamic cast
3340	VspSubdivisionCandidate sc = static_cast<VspSubdivisionCandidate >(splitCandidate);
3341
3342	VspTraversalData &tData = sc->mParentData;
3343	VspNode *newNode = tData.mNode;
3344	VspNode oldNode = (VspNode )splitCandidate->mEvaluationHack;
3345
3346	if (!oldNode->IsLeaf())
3347	{
3348	///////////
3349	//-- continue subdivision
3350
3351	VspTraversalData tFrontData;
3352	VspTraversalData tBackData;
3353
3354	VspInterior oldInterior = static_cast<VspInterior >(oldNode);
3355
3356	// create new interior node and two leaf node
3357	const AxisAlignedPlane splitPlane = oldInterior->GetPlane();
3358	sc->mSplitPlane = splitPlane;
3359
3360	// evaluate the changes in render cost and pvs entries
3361	EvalSubdivisionCandidate(*sc, false);
3362
3363	newNode = SubdivideNode(*sc, tFrontData, tBackData);
3364
3365	//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
3366	//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
3367
3368	//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
3369	//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
3370
3371	/////////////
3372	//-- evaluate new split candidates for global greedy cost heuristics
3373
3374	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
3375	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
3376
3377	frontCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
3378	backCandidate->SetPriority((float)-oldInterior->GetBack()->mTimeStamp);
3379
3380	frontCandidate->mEvaluationHack = oldInterior->GetFront();
3381	backCandidate->mEvaluationHack = oldInterior->GetBack();
3382
3383	// cross reference
3384	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
3385	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
3386
3387	tQueue.Push(frontCandidate);
3388	tQueue.Push(backCandidate);
3389
3390	// note: leaf is not destroyed because it is needed to collect
3391	// dirty candidates in hierarchy manager
3392	}
3393
3394	if (newNode->IsLeaf()) // subdivision terminated
3395	{
3396	// detach subdivision candidate: this leaf is no candidate for splitting anymore
3397	tData.mNode->SetSubdivisionCandidate(NULL);
3398	// detach node so it won't get deleted
3399	tData.mNode = NULL;
3400	}
3401
3402	return newNode;
3403	}
3404
3405
3406	int VspTree::CompressObjects(VspLeaf *leaf)
3407	{
3408	bool compressed = true;
3409
3410	while (compressed)
3411	{
3412	BvhNode::NewMail(2);
3413
3414	ObjectPvsIterator oit = leaf->GetViewCell()->GetPvs().GetIterator();
3415	vector<BvhNode *> parents;
3416	ObjectPvs newPvs;
3417
3418	compressed = false;
3419
3420	while (oit.HasMoreEntries())
3421	{
3422	BvhNode obj = static_cast<BvhNode >(oit.Next());
3423
3424	if (!obj->IsRoot())
3425	{
3426	BvhNode *parent = obj->GetParent();
3427
3428	if (!parent->Mailed())
3429	{
3430	if (parent->Mailed(1))
3431	cout << "error!!" << endl;
3432	parent->Mail();
3433	}
3434	else
3435	{
3436	// sibling was already found =>
3437	// this entry can be exchanged by the parent
3438	parents.push_back(parent);
3439	parent->Mail(1);
3440
3441	compressed = true;
3442	}
3443	}
3444	}
3445
3446	PvsData pvsData;
3447	oit = leaf->GetViewCell()->GetPvs().GetIterator();
3448
3449	while (oit.HasMoreEntries())
3450	{
3451	BvhNode obj = static_cast<BvhNode >(oit.Next(pvsData));
3452
3453	if (!obj->IsRoot())
3454	{
3455	BvhNode *parent = obj->GetParent();
3456
3457	// add only entries that cannot be exchaned with the parent
3458	if (!parent->Mailed(1))
3459	{
3460	newPvs.AddSampleDirty(obj, pvsData.mSumPdf);
3461	}
3462	}
3463	}
3464
3465	// add parents
3466	vector<BvhNode *>::const_iterator bit, bit_end = parents.end();
3467
3468	for (bit = parents.begin(); bit != bit_end; ++ bit)
3469	{
3470	newPvs.AddSampleDirty(*bit, 1);
3471	}
3472
3473	//cout << "size " << newPvs.GetSize() << endl;
3474	leaf->GetViewCell()->SetPvs(newPvs);
3475	}
3476
3477	return leaf->GetViewCell()->GetPvs().GetSize();
3478	}
3479
3480
3481	int VspTree::CompressObjects()
3482	{
3483	vector<VspLeaf *> leaves;
3484	CollectLeaves(leaves);
3485
3486	int numEntries = 0;
3487
3488	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
3489
3490	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3491	{
3492	numEntries += CompressObjects(*lit);
3493	}
3494
3495	return numEntries;
3496	}
3497
3498
3499	void VspTree::EvalMinMaxDepth(int &minDepth, int &maxDepth)
3500	{
3501	stack<pair<VspNode *, int> > nodeStack;
3502	nodeStack.push(pair<VspNode *, int>(mRoot, 0));
3503
3504	minDepth = 999999;
3505	maxDepth = 0;
3506
3507	while (!nodeStack.empty())
3508	{
3509	VspNode *node = nodeStack.top().first;
3510	const int depth = nodeStack.top().second;
3511
3512	nodeStack.pop();
3513
3514	if (node->IsLeaf())
3515	{
3516	// test if this leaf is in valid view space
3517	VspLeaf leaf = static_cast<VspLeaf >(node);
3518
3519	if (depth < minDepth)
3520	minDepth = depth;
3521
3522	if (depth > maxDepth)
3523	maxDepth = depth;
3524	}
3525	else
3526	{
3527	VspInterior interior = static_cast<VspInterior >(node);
3528
3529	nodeStack.push(pair<VspNode *, int>(interior->GetBack(), depth + 1));
3530	nodeStack.push(pair<VspNode *, int>(interior->GetFront(), depth + 1));
3531	}
3532	}
3533	}
3534
3535	#if 0
3536	void VspTree::TraverseRayPacket(RayBundle &rays);
3537	{
3538	float splitPos [3];
3539	float dist[3];
3540
3541	const int allValid = 1xf;
3542	int mask = all_valid;
3543
3544	int comparisonResult = 0;
3545
3546	while (!node->IsLeaf())
3547	{
3548	comparisonResult = 0;
3549
3550	for (int i = 0; i < 4; ++ i)
3551	{
3552	splitPos[i] = node->splitPos;
3553	dist[i] = (splitpos[i] rp.origin[i][axis]) / (rp.dir[i][axis]);
3554
3555	comparisonresult \|= ((dist[i] <= tnear[i]) << i);
3556	}
3557
3558	comparisonresult &= mask;
3559
3560	if (comparisonresult == allValid)
3561	{
3562	node = node->far;
3563	continue
3564	}
3565
3566	comparisonresult = 0;
3567
3568	for (int i = 0; i < 4; ++ i){
3569
3570	comparisonresult \|= (dist[i] >= tfar[i]);
3571	}
3572
3573	comparisonresult &= mask;
3574
3575	if (comparisonresult == allValid)
3576	{
3577	node = node->near;
3578	continue;
3579	}
3580
3581	if (comparisonresult)
3582	{
3583
3584	Push( node->far, dist[0...3], tfar[0...3] )
3585
3586	node = node->near;
3587
3588	mask = 0;
3589
3590	for (int i = 0; i < 4; ++ i)
3591	{
3592	bool b = (tnear[i] < tfar[i]);
3593	mask \|= b;
3594
3595	if (b)
3596	{
3597	tfar[i] = dist[i];
3598	}
3599
3600	}
3601
3602	}
3603	}
3604	#endif
3605	/*
3606	struct RayPacket
3607	{
3608	union { float ox[4]; __m128 ox4; };
3609	union { float oy[4]; __m128 oy4; };
3610	union { float oz[4]; __m128 oz4; };
3611	union { float dx[4]; __m128 dx4; };
3612	union { float dy[4]; __m128 dy4; };
3613	union { float dz[4]; __m128 dz4; };
3614	};
3615	*/
3616	void VspTree::TraverseRayPacket()//RayBundle &rays)
3617	{
3618	#if USE_SSE
3619	VspNode *node;
3620
3621	RayPacket rp;
3622
3623	__m128 mask;
3624	__m128 tf4;
3625	__m128 tn4;
3626	//const int offs[4] = { (RP->dcell[0] >= 0)?1:0, (RP->dcell[4] >= 0)?1:0, (RP->dcell[8] >= 0)?1:0, 0 };
3627
3628	const int offs[4] = { 0, 0, 0, 0 };
3629
3630	while (!node->IsLeaf())
3631	{
3632	VspInterior interior = static_cast<VspInterior >(node);
3633
3634	float pos = interior->GetPosition();
3635	const __m128 spos = _mm_load_ps(&pos);
3636
3637	const int aidx = interior->GetAxis();
3638	const __m128 d4;// = _mm_mul_ps( _mm_sub_ps( spos, RP->oc4[aidx] ), RP->rdc4[aidx] );
3639
3640	VspNode* ln = interior->GetBack();// + offs[aidx];
3641
3642	if (!_mm_movemask_ps( _mm_and_ps( _mm_cmpgt_ps( d4, tn4 ), mask ) ))
3643	{
3644	node = ln;
3645	continue;
3646	}
3647
3648	node = interior->GetBack();// + (offs[aidx]^1);
3649
3650	if (_mm_movemask_ps( _mm_and_ps( _mm_cmplt_ps( d4, tf4 ), mask ) ))
3651	{
3652	const __m128 mask2 = _mm_cmpgt_ps( d4, tn4 );
3653	const __m128 mask3 = _mm_cmplt_ps( d4, tf4 );
3654
3655	//m_Stack[stackptr].tf4 = tf4;
3656
3657	tf4 = _mm_or_ps( _mm_and_ps( mask3, d4 ), _mm_andnot_ps( mask3, tf4 ) );
3658
3659	//m_Stack[stackptr].node = (KdTreeNode*)ln;
3660	//m_Stack[stackptr].mask = mask;
3661	//m_Stack[stackptr++].tn4 = _mm_or_ps( _mm_and_ps( mask2, d4 ), _mm_andnot_ps( mask2, tn4 ) );
3662	mask = _mm_cmplt_ps( tn4, tf4 );
3663	}
3664	}
3665	#endif
3666
3667	}
3668
3669	}

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

Download in other formats: