Context Navigation

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

Revision 2020, 83.9 KB checked in by bittner, 17 years ago (diff)
power plant updates

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	if (0)
2390	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2391	else
2392	viewCell = leaf->GetViewCell();
2393
2394	// don't have to mail if each view cell belongs to exactly one leaf
2395	if (!useMailboxing \|\| !viewCell->Mailed())
2396	{
2397	if (useMailboxing)
2398	viewCell->Mail();
2399
2400	viewcells.push_back(viewCell);
2401	++ hits;
2402	}
2403
2404	// get the next node from the stack
2405	if (tStack.empty())
2406	break;
2407
2408	entp = extp;
2409	mint = maxt;
2410
2411	LineTraversalData &s = tStack.top();
2412	node = s.mNode;
2413	extp = s.mExitPoint;
2414	maxt = s.mMaxT;
2415
2416	tStack.pop();
2417	}
2418	}
2419
2420	return hits;
2421	}
2422
2423
2424	int VspTree::CastRay(Ray &ray)
2425	{
2426	int hits = 0;
2427
2428	stack<LineTraversalData> tStack;
2429	const Vector3 dir = ray.GetDir();
2430
2431	float maxt, mint;
2432
2433	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2434	return 0;
2435
2436	Intersectable::NewMail();
2437	ViewCell::NewMail();
2438
2439	Vector3 entp = ray.Extrap(mint);
2440	Vector3 extp = ray.Extrap(maxt);
2441
2442	const Vector3 origin = entp;
2443
2444	VspNode *node = mRoot;
2445	VspNode *farChild = NULL;
2446
2447	float position;
2448	int axis;
2449
2450	while (1)
2451	{
2452	if (!node->IsLeaf())
2453	{
2454	VspInterior in = static_cast<VspInterior >(node);
2455	position = in->GetPosition();
2456	axis = in->GetAxis();
2457
2458	if (entp[axis] <= position)
2459	{
2460	if (extp[axis] <= position)
2461	{
2462	node = in->GetBack();
2463	// cases N1,N2,N3,P5,Z2,Z3
2464	continue;
2465	}
2466	else
2467	{
2468	// case N4
2469	node = in->GetBack();
2470	farChild = in->GetFront();
2471	}
2472	}
2473	else
2474	{
2475	if (position <= extp[axis])
2476	{
2477	node = in->GetFront();
2478	// cases P1,P2,P3,N5,Z1
2479	continue;
2480	}
2481	else
2482	{
2483	node = in->GetFront();
2484	farChild = in->GetBack();
2485	// case P4
2486	}
2487	}
2488
2489	// $$ modification 3.5.2004 - hints from Kamil Ghais
2490	// case N4 or P4
2491	const float tdist = (position - origin[axis]) / dir[axis];
2492	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2493	extp = origin + dir * tdist;
2494	maxt = tdist;
2495	}
2496	else
2497	{
2498	// compute intersection with all objects in this leaf
2499	VspLeaf leaf = static_cast<VspLeaf >(node);
2500	ViewCell *vc = leaf->GetViewCell();
2501
2502	if (!vc->Mailed())
2503	{
2504	vc->Mail();
2505	// todo: add view cells to ray
2506	++ hits;
2507	}
2508
2509	// get the next node from the stack
2510	if (tStack.empty())
2511	break;
2512
2513	entp = extp;
2514	mint = maxt;
2515
2516	LineTraversalData &s = tStack.top();
2517	node = s.mNode;
2518	extp = s.mExitPoint;
2519	maxt = s.mMaxT;
2520	tStack.pop();
2521	}
2522	}
2523
2524	return hits;
2525	}
2526
2527
2528	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2529	{
2530	if (mRoot == NULL)
2531	return NULL;
2532
2533	stack<VspNode *> nodeStack;
2534	nodeStack.push(mRoot);
2535
2536	ViewCellLeaf *viewcell = NULL;
2537
2538	while (!nodeStack.empty())
2539	{
2540	VspNode *node = nodeStack.top();
2541	nodeStack.pop();
2542
2543	if (node->IsLeaf())
2544	{
2545	/const AxisAlignedBox3 box = GetBoundingBox(static_cast<VspLeaf >(node));
2546	if (!box.IsInside(point))
2547	cerr << "error, point " << point << " should be in view cell " << box << endl;
2548	*/
2549	viewcell = static_cast<VspLeaf *>(node)->GetViewCell();
2550	break;
2551	}
2552	else
2553	{
2554	VspInterior interior = static_cast<VspInterior >(node);
2555
2556	// random decision
2557	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2558	{
2559	nodeStack.push(interior->GetFront());
2560	}
2561	else
2562	{
2563	nodeStack.push(interior->GetBack());
2564	}
2565	}
2566	}
2567
2568	if (active)
2569	{
2570	return mViewCellsTree->GetActiveViewCell(viewcell);
2571	}
2572	else
2573	{
2574	return viewcell;
2575	}
2576	}
2577
2578
2579	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2580	{
2581	VspNode *node = mRoot;
2582
2583	while (1)
2584	{
2585	// early exit
2586	if (node->TreeValid())
2587	return true;
2588
2589	if (node->IsLeaf())
2590	return false;
2591
2592	VspInterior in = static_cast<VspInterior >(node);
2593
2594	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2595	{
2596	node = in->GetBack();
2597	}
2598	else
2599	{
2600	node = in->GetFront();
2601	}
2602	}
2603
2604	// should never come here
2605	return false;
2606	}
2607
2608
2609	void VspTree::PropagateUpValidity(VspNode *node)
2610	{
2611	const bool isValid = node->TreeValid();
2612
2613	// propagative up invalid flag until only invalid nodes exist over this node
2614	if (!isValid)
2615	{
2616	while (!node->IsRoot() && node->GetParent()->TreeValid())
2617	{
2618	node = node->GetParent();
2619	node->SetTreeValid(false);
2620	}
2621	}
2622	else
2623	{
2624	// propagative up valid flag until one of the subtrees is invalid
2625	while (!node->IsRoot() && !node->TreeValid())
2626	{
2627	node = node->GetParent();
2628	VspInterior interior = static_cast<VspInterior >(node);
2629
2630	// the parent is valid iff both leaves are valid
2631	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2632	interior->GetFront()->TreeValid());
2633	}
2634	}
2635	}
2636
2637
2638	bool VspTree::Export(OUT_STREAM &stream)
2639	{
2640	ExportNode(mRoot, stream);
2641
2642	return true;
2643	}
2644
2645
2646	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2647	{
2648	if (node->IsLeaf())
2649	{
2650	VspLeaf leaf = static_cast<VspLeaf >(node);
2651	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2652
2653	int id = -1;
2654	if (viewCell != mOutOfBoundsCell)
2655	id = viewCell->GetId();
2656
2657	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2658	}
2659	else
2660	{
2661	VspInterior interior = static_cast<VspInterior >(node);
2662
2663	AxisAlignedPlane plane = interior->GetPlane();
2664	stream << "<Interior plane=\"" << plane.mPosition << " "
2665	<< plane.mAxis << "\">" << endl;
2666
2667	ExportNode(interior->GetBack(), stream);
2668	ExportNode(interior->GetFront(), stream);
2669
2670	stream << "</Interior>" << endl;
2671	}
2672	}
2673
2674
2675	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2676	RayInfoContainer &rays,
2677	RayInfoContainer &frontRays,
2678	RayInfoContainer &backRays) const
2679	{
2680	int splits = 0;
2681
2682	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2683
2684	for (rit = rays.begin(); rit != rit_end; ++ rit)
2685	{
2686	RayInfo bRay = *rit;
2687
2688	VssRay *ray = bRay.mRay;
2689	float t;
2690
2691	// get classification and receive new t
2692	// test if start point behind or in front of plane
2693	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2694
2695	if (side == 0)
2696	{
2697	++ splits;
2698
2699	if (ray->HasPosDir(plane.mAxis))
2700	{
2701	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2702	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2703	}
2704	else
2705	{
2706	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2707	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2708	}
2709	}
2710	else if (side == 1)
2711	{
2712	frontRays.push_back(bRay);
2713	}
2714	else
2715	{
2716	backRays.push_back(bRay);
2717	}
2718	}
2719
2720	return splits;
2721	}
2722
2723
2724	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2725	{
2726	if (!node->GetParent())
2727	return mBoundingBox;
2728
2729	if (!node->IsLeaf())
2730	{
2731	return (static_cast<VspInterior *>(node))->GetBoundingBox();
2732	}
2733
2734	VspInterior parent = static_cast<VspInterior >(node->GetParent());
2735
2736	AxisAlignedBox3 box(parent->GetBoundingBox());
2737
2738	if (parent->GetFront() == node)
2739	box.SetMin(parent->GetAxis(), parent->GetPosition());
2740	else
2741	box.SetMax(parent->GetAxis(), parent->GetPosition());
2742
2743	return box;
2744	}
2745
2746
2747	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2748	ViewCellContainer &viewCells) const
2749	{
2750	stack<VspNode *> nodeStack;
2751
2752	ViewCell::NewMail();
2753
2754	nodeStack.push(mRoot);
2755
2756	while (!nodeStack.empty())
2757	{
2758	VspNode *node = nodeStack.top();
2759	nodeStack.pop();
2760
2761	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2762
2763	if (Overlap(bbox, box)) {
2764	if (node->IsLeaf())
2765	{
2766	VspLeaf leaf = static_cast<VspLeaf >(node);
2767
2768	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2769	{
2770	leaf->GetViewCell()->Mail();
2771	viewCells.push_back(leaf->GetViewCell());
2772	}
2773	}
2774	else
2775	{
2776	VspInterior interior = static_cast<VspInterior >(node);
2777
2778	VspNode *first = interior->GetFront();
2779	VspNode *second = interior->GetBack();
2780
2781	nodeStack.push(first);
2782	nodeStack.push(second);
2783	}
2784	}
2785	// default: cull
2786	}
2787
2788	return (int)viewCells.size();
2789	}
2790
2791
2792	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2793	RayInfoContainer &rays)
2794	{
2795	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2796
2797	long startTime = GetTime();
2798
2799	cout << "storing rays ... ";
2800
2801	Intersectable::NewMail();
2802
2803	//-- store rays and objects
2804	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2805	{
2806	VssRay ray = rit;
2807	float minT, maxT;
2808	static Ray hray;
2809
2810	hray.Init(*ray);
2811
2812	// TODO: not very efficient to implictly cast between rays types
2813	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2814	{
2815	float len = ray->Length();
2816
2817	if (!len)
2818	len = Limits::Small;
2819
2820	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2821	}
2822	}
2823
2824	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2825	}
2826
2827
2828	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2829	{
2830	static Ray hray;
2831	hray.Init(ray);
2832
2833	float tmin = 0, tmax = 1.0;
2834
2835	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2836	return;
2837
2838	const Vector3 origin = hray.Extrap(tmin);
2839	const Vector3 termination = hray.Extrap(tmax);
2840
2841	// view cells were not precomputed
2842	// don't mail because we need mailboxing for something else
2843	CastLineSegment(origin, termination, viewCells, false);
2844	}
2845
2846
2847	void VspTree::Initialise(const VssRayContainer &rays,
2848	AxisAlignedBox3 *forcedBoundingBox)
2849	{
2850	ComputeBoundingBox(rays, forcedBoundingBox);
2851
2852	VspLeaf *leaf = new VspLeaf();
2853	mRoot = leaf;
2854
2855	VspViewCell *viewCell = new VspViewCell();
2856	leaf->SetViewCell(viewCell);
2857
2858	// set view cell values
2859	viewCell->mLeaves.push_back(leaf);
2860	viewCell->SetVolume(mBoundingBox.GetVolume());
2861
2862	leaf->mProbability = mBoundingBox.GetVolume();
2863	}
2864
2865
2866	void VspTree::PrepareConstruction(SplitQueue &tQueue,
2867	const VssRayContainer &sampleRays,
2868	RayInfoContainer &rays)
2869	{
2870	mVspStats.Reset();
2871	mVspStats.Start();
2872	mVspStats.nodes = 1;
2873
2874	// store pointer to this tree
2875	VspSubdivisionCandidate::sVspTree = this;
2876
2877	// initialise termination criteria
2878	mTermMinProbability *= mBoundingBox.GetVolume();
2879
2880	// get clipped rays
2881	PreprocessRays(sampleRays, rays);
2882
2883	/// collect pvs from rays
2884	const float pvsCost = EvalPvsCost(rays);
2885
2886	// root and bounding box were already constructed
2887	VspLeaf leaf = static_cast<VspLeaf >(mRoot);
2888
2889	//////////
2890	//-- prepare view space partition
2891
2892	const float prop = mBoundingBox.GetVolume();
2893
2894	// first vsp traversal data
2895	VspTraversalData vData(leaf, 0, &rays, pvsCost, prop, mBoundingBox);
2896
2897	#if WORK_WITH_VIEWCELL_PVS
2898	// add first view cell to all the objects view cell pvs
2899	ObjectPvsEntries::const_iterator oit,
2900	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2901
2902	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2903	{
2904	Intersectable obj = (oit).first;
2905	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2906	}
2907	#endif
2908
2909	mTotalCost = vData.mCorrectedRenderCost = vData.mRenderCost = pvsCost;
2910	mPvsEntries = EvalPvsEntriesSize(rays);
2911	vData.mCorrectedPvs = vData.mPvs = (float)mPvsEntries;
2912
2913	//////////////
2914	//-- create the first split candidate
2915
2916	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2917	EvalSubdivisionCandidate(*splitCandidate);
2918	leaf->SetSubdivisionCandidate(splitCandidate);
2919
2920	EvalSubdivisionStats(*splitCandidate);
2921
2922	tQueue.Push(splitCandidate);
2923	}
2924
2925
2926	void VspTree::CollectDirtyCandidate(const VssRay &ray,
2927	const bool isTermination,
2928	vector<SubdivisionCandidate *> &dirtyList,
2929	const bool onlyUnmailed) const
2930	{
2931
2932	Intersectable *obj;
2933	Vector3 pt;
2934	KdNode *node;
2935
2936	ray.GetSampleData(isTermination, pt, &obj, &node);
2937
2938	if (!obj) return;
2939
2940	SubdivisionCandidate *candidate = NULL;
2941
2942	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2943	{
2944	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2945	{
2946	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2947
2948	if (!leaf->Mailed())
2949	{
2950	leaf->Mail();
2951	candidate = leaf->mSubdivisionCandidate;
2952	}
2953	break;
2954	}
2955	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2956	{
2957	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2958
2959	if (!leaf->Mailed())
2960	{
2961	leaf->Mail();
2962	candidate = leaf->GetSubdivisionCandidate();
2963	}
2964	break;
2965	}
2966	default:
2967	cerr << "not implemented yet" << endl;
2968	candidate = NULL;
2969	break;
2970	}
2971
2972	// is this leaf still a split candidate?
2973	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
2974	{
2975	candidate->Mail();
2976	candidate->SetDirty(true);
2977	dirtyList.push_back(candidate);
2978	}
2979	}
2980
2981
2982	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
2983	vector<SubdivisionCandidate *> &dirtyList,
2984	const bool onlyUnmailed)
2985	{
2986	VspTraversalData &tData = sc->mParentData;
2987	VspLeaf *node = tData.mNode;
2988
2989	KdLeaf::NewMail();
2990	Intersectable::NewMail();
2991
2992	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2993
2994	// add all kd nodes seen by the rays
2995	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2996	{
2997	VssRay ray = (rit).mRay;
2998
2999	CollectDirtyCandidate(*ray, true, dirtyList, onlyUnmailed);
3000	CollectDirtyCandidate(*ray, false, dirtyList, onlyUnmailed);
3001	}
3002	}
3003
3004
3005	int VspTree::EvalMaxEventContribution(const VssRay &ray,
3006	const bool isTermination) const
3007	{
3008	Intersectable *obj;
3009	Vector3 pt;
3010	KdNode *node;
3011
3012	ray.GetSampleData(isTermination, pt, &obj, &node);
3013
3014	if (!obj)
3015	return 0;
3016
3017	int pvs = 0;
3018
3019	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3020	{
3021	case HierarchyManager::NO_OBJ_SUBDIV:
3022	{
3023	if (-- obj->mCounter == 0)
3024	++ pvs;
3025	break;
3026	}
3027	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3028	{
3029	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3030
3031	// add contributions of the kd nodes
3032	pvs += EvalMaxEventContribution(leaf);
3033	break;
3034	}
3035	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3036	{
3037	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3038
3039	if (-- leaf->mCounter == 0)
3040	pvs += (int)leaf->mObjects.size();
3041	break;
3042	}
3043	default:
3044	break;
3045	}
3046
3047	return pvs;
3048	}
3049
3050
3051	float VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
3052	{
3053	float pvsSize = 0;
3054
3055	Intersectable *obj;
3056	Vector3 pt;
3057	KdNode *node;
3058
3059	ray.GetSampleData(isTermination, pt, &obj, &node);
3060
3061	if (!obj)
3062	return 0;
3063
3064	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3065	{
3066	case HierarchyManager::NO_OBJ_SUBDIV:
3067	{
3068	if (!obj->Mailed())
3069	{
3070	obj->Mail();
3071	obj->mCounter = 0;
3072	++ pvsSize;
3073	}
3074
3075	++ obj->mCounter;
3076	break;
3077	}
3078	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3079	{
3080	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3081	pvsSize += PrepareHeuristics(leaf);
3082	break;
3083	}
3084	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3085	{
3086	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3087
3088	if (!leaf->Mailed())
3089	{
3090	leaf->Mail();
3091	leaf->mCounter = 0;
3092	pvsSize += (int)leaf->mObjects.size();
3093	}
3094
3095	++ leaf->mCounter;
3096	break;
3097	}
3098	default:
3099	break;
3100	}
3101
3102	return pvsSize;
3103	}
3104
3105
3106	int VspTree::EvalMinEventContribution(const VssRay &ray,
3107	const bool isTermination) const
3108	{
3109	Intersectable *obj;
3110	Vector3 pt;
3111	KdNode *node;
3112
3113	ray.GetSampleData(isTermination, pt, &obj, &node);
3114
3115	if (!obj) return 0;
3116
3117	int pvs = 0;
3118
3119	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3120	{
3121	case HierarchyManager::NO_OBJ_SUBDIV:
3122	{
3123	if (!obj->Mailed())
3124	{
3125	obj->Mail();
3126	++ pvs;
3127	}
3128	break;
3129	}
3130	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3131	{
3132	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3133	// add contributions of the kd nodes
3134	pvs += EvalMinEventContribution(leaf);
3135	break;
3136	}
3137	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3138	{
3139	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3140	if (!leaf->Mailed())
3141	{
3142	leaf->Mail();
3143	pvs += (int)leaf->mObjects.size();
3144	}
3145	break;
3146	}
3147	default:
3148	break;
3149	}
3150
3151	return pvs;
3152	}
3153
3154
3155	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
3156	const bool isTermination,
3157	const int cf,
3158	float &frontPvs,
3159	float &backPvs,
3160	float &totalPvs) const
3161	{
3162	Intersectable *obj;
3163	Vector3 pt;
3164	KdNode *node;
3165
3166	ray.GetSampleData(isTermination, pt, &obj, &node);
3167
3168	if (!obj) return;
3169
3170	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3171	{
3172	case HierarchyManager::NO_OBJ_SUBDIV:
3173	{
3174	// find front and back pvs for origing and termination object
3175	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
3176	break;
3177	}
3178	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3179	{
3180	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3181	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
3182	break;
3183	}
3184	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3185	{
3186	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3187	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
3188	break;
3189	}
3190	}
3191	}
3192
3193
3194	void VspTree::UpdatePvsEntriesContribution(const VssRay &ray,
3195	const bool isTermination,
3196	const int cf,
3197	float &pvsFront,
3198	float &pvsBack,
3199	float &totalPvs) const
3200	{
3201	Intersectable *obj;
3202	Vector3 pt;
3203	KdNode *node;
3204
3205	ray.GetSampleData(isTermination, pt, &obj, &node);
3206	if (!obj) return;
3207
3208	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3209	{
3210	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3211	// TODO
3212	break;
3213	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3214	{
3215	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3216	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3217	break;
3218	}
3219	default:
3220	UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs);
3221	break;
3222	}
3223	}
3224
3225
3226	int VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
3227	{
3228	Intersectable *obj;
3229	Vector3 pt;
3230	KdNode *node;
3231
3232	ray.GetSampleData(isTermination, pt, &obj, &node);
3233
3234	if (!obj) return 0;
3235
3236	int pvs = 0;
3237
3238	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
3239	{
3240	case HierarchyManager::NO_OBJ_SUBDIV:
3241	{
3242	if (!obj->Mailed())
3243	{
3244	obj->Mail();
3245	++ pvs;
3246	}
3247	break;
3248	}
3249	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3250	{
3251	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3252	pvs += EvalContributionToPvs(leaf);
3253	break;
3254	}
3255	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3256	{
3257	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3258
3259	if (!bvhleaf->Mailed())
3260	{
3261	bvhleaf->Mail();
3262	pvs += (int)bvhleaf->mObjects.size();
3263	}
3264	break;
3265	}
3266	default:
3267	break;
3268	}
3269
3270	return pvs;
3271	}
3272
3273
3274	int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3275	{
3276	if (leaf->Mailed()) // leaf already mailed
3277	return 0;
3278
3279	leaf->Mail();
3280
3281	// this is the pvs which is uniquely part of this kd leaf
3282	int pvs = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3283
3284	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3285
3286	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3287	{
3288	Intersectable obj = oit;
3289	if (!obj->Mailed())
3290	{
3291	obj->Mail();
3292	++ pvs;
3293	}
3294	}
3295
3296	return pvs;
3297	}
3298
3299
3300	VspNode *VspTree::SubdivideAndCopy(SplitQueue &tQueue,
3301	SubdivisionCandidate *splitCandidate)
3302	{
3303	// todo remove dynamic cast
3304	VspSubdivisionCandidate sc = static_cast<VspSubdivisionCandidate >(splitCandidate);
3305
3306	VspTraversalData &tData = sc->mParentData;
3307	VspNode *newNode = tData.mNode;
3308	VspNode oldNode = (VspNode )splitCandidate->mEvaluationHack;
3309
3310	if (!oldNode->IsLeaf())
3311	{
3312	///////////
3313	//-- continue subdivision
3314
3315	VspTraversalData tFrontData;
3316	VspTraversalData tBackData;
3317
3318	VspInterior oldInterior = static_cast<VspInterior >(oldNode);
3319
3320	// create new interior node and two leaf node
3321	const AxisAlignedPlane splitPlane = oldInterior->GetPlane();
3322	sc->mSplitPlane = splitPlane;
3323
3324	// evaluate the changes in render cost and pvs entries
3325	EvalSubdivisionCandidate(*sc, false);
3326
3327	newNode = SubdivideNode(*sc, tFrontData, tBackData);
3328
3329	//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
3330	//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
3331
3332	//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
3333	//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
3334
3335	/////////////
3336	//-- evaluate new split candidates for global greedy cost heuristics
3337
3338	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
3339	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
3340
3341	frontCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
3342	backCandidate->SetPriority((float)-oldInterior->GetBack()->mTimeStamp);
3343
3344	frontCandidate->mEvaluationHack = oldInterior->GetFront();
3345	backCandidate->mEvaluationHack = oldInterior->GetBack();
3346
3347	// cross reference
3348	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
3349	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
3350
3351	tQueue.Push(frontCandidate);
3352	tQueue.Push(backCandidate);
3353
3354	// note: leaf is not destroyed because it is needed to collect
3355	// dirty candidates in hierarchy manager
3356	}
3357
3358	if (newNode->IsLeaf()) // subdivision terminated
3359	{
3360	// detach subdivision candidate: this leaf is no candidate for splitting anymore
3361	tData.mNode->SetSubdivisionCandidate(NULL);
3362	// detach node so it won't get deleted
3363	tData.mNode = NULL;
3364	}
3365
3366	return newNode;
3367	}
3368
3369
3370	int VspTree::CompressObjects(VspLeaf *leaf)
3371	{
3372	bool compressed = true;
3373
3374	while (compressed)
3375	{
3376	BvhNode::NewMail(2);
3377
3378	ObjectPvsIterator oit = leaf->GetViewCell()->GetPvs().GetIterator();
3379	vector<BvhNode *> parents;
3380	ObjectPvs newPvs;
3381
3382	compressed = false;
3383
3384	while (oit.HasMoreEntries())
3385	{
3386	const ObjectPvsEntry &entry = oit.Next();
3387	BvhNode obj = static_cast<BvhNode >(entry.mObject);
3388
3389	if (!obj->IsRoot())
3390	{
3391	BvhNode *parent = obj->GetParent();
3392
3393	if (!parent->Mailed())
3394	{
3395	if (parent->Mailed(1))
3396	cout << "error!!" << endl;
3397	parent->Mail();
3398	}
3399	else
3400	{
3401	// sibling was already found =>
3402	// this entry can be exchanged by the parent
3403	parents.push_back(parent);
3404	parent->Mail(1);
3405
3406	compressed = true;
3407	}
3408	}
3409	}
3410
3411	oit = leaf->GetViewCell()->GetPvs().GetIterator();
3412
3413	while (oit.HasMoreEntries())
3414	{
3415	const ObjectPvsEntry &entry = oit.Next();
3416	BvhNode obj = static_cast<BvhNode >(entry.mObject);
3417
3418	if (!obj->IsRoot())
3419	{
3420	BvhNode *parent = obj->GetParent();
3421
3422	// add only entries that cannot be exchaned with the parent
3423	if (!parent->Mailed(1))
3424	{
3425	newPvs.AddSampleDirty(obj, entry.mData.mSumPdf);
3426	}
3427	}
3428	}
3429
3430	// add parents
3431	vector<BvhNode *>::const_iterator bit, bit_end = parents.end();
3432
3433	for (bit = parents.begin(); bit != bit_end; ++ bit)
3434	{
3435	newPvs.AddSampleDirty(*bit, 1);
3436	}
3437
3438	//cout << "size " << newPvs.GetSize() << endl;
3439	leaf->GetViewCell()->SetPvs(newPvs);
3440	}
3441
3442	return leaf->GetViewCell()->GetPvs().GetSize();
3443	}
3444
3445
3446	int VspTree::CompressObjects()
3447	{
3448	vector<VspLeaf *> leaves;
3449	CollectLeaves(leaves);
3450
3451	int numEntries = 0;
3452
3453	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
3454
3455	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3456	{
3457	numEntries += CompressObjects(*lit);
3458	}
3459
3460	return numEntries;
3461	}
3462
3463
3464	bool VspTree::LineSegmentIntersects(const Vector3 &origin,
3465	const Vector3 &termination,
3466	ViewCell *viewCell)
3467	{
3468	/*float mint = 0.0f, maxt = 1.0f;
3469	const Vector3 dir = termination - origin;
3470
3471	stack<LineTraversalData> tStack;
3472
3473	Vector3 entp = origin;
3474	Vector3 extp = termination;
3475
3476	VspNode *node = mRoot;
3477	VspNode *farChild;
3478
3479	float position;
3480	int axis;
3481
3482	while (1)
3483	{
3484	if (!node->IsLeaf())
3485	{
3486	VspInterior in = static_cast<VspInterior >(node);
3487	position = in->GetPosition();
3488	axis = in->GetAxis();
3489
3490	if (entp[axis] <= position)
3491	{
3492	if (extp[axis] <= position)
3493	{
3494	node = in->GetBack();
3495	// cases N1,N2,N3,P5,Z2,Z3
3496	continue;
3497	} else
3498	{
3499	// case N4
3500	node = in->GetBack();
3501	farChild = in->GetFront();
3502	}
3503	}
3504	else
3505	{
3506	if (position <= extp[axis])
3507	{
3508	node = in->GetFront();
3509	// cases P1,P2,P3,N5,Z1
3510	continue;
3511	}
3512	else
3513	{
3514	node = in->GetFront();
3515	farChild = in->GetBack();
3516	// case P4
3517	}
3518	}
3519
3520	// $$ modification 3.5.2004 - hints from Kamil Ghais
3521	// case N4 or P4
3522	const float tdist = (position - origin[axis]) / dir[axis];
3523	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
3524
3525	extp = origin + dir * tdist;
3526	maxt = tdist;
3527	}
3528	else
3529	{
3530	// compute intersection with all objects in this leaf
3531	VspLeaf leaf = static_cast<VspLeaf >(node);
3532	ViewCell *viewCell;
3533	if (0)
3534	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3535	else
3536	viewCell = leaf->GetViewCell();
3537
3538	if (viewCell == currentViewCell)
3539	return true;
3540
3541	// get the next node from the stack
3542	if (tStack.empty())
3543	break;
3544
3545	entp = extp;
3546	mint = maxt;
3547
3548	LineTraversalData &s = tStack.top();
3549	node = s.mNode;
3550	extp = s.mExitPoint;
3551	maxt = s.mMaxT;
3552
3553	tStack.pop();
3554	}
3555	}
3556	*/
3557	return false;
3558	}
3559
3560
3561	}

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

Download in other formats: