Context Navigation

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

Revision 2064, 83.9 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: