Context Navigation

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

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

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

Download in other formats: