Context Navigation

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

Revision 2199, 85.3 KB checked in by mattausch, 17 years ago (diff)
using mutationsamples for evaluation

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

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

Download in other formats: