Context Navigation

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

Revision 2210, 85.5 KB checked in by mattausch, 17 years ago (diff)
improved performance of osp

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

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

Download in other formats: