Context Navigation

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

Revision 1586, 74.8 KB checked in by mattausch, 18 years ago (diff)
resolved bug for object space distribution using triangles fixed biasing bug for mesh::GetRandomSurfacePoint? method and GetRandomVisibleSurfacePoint?.

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

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

Download in other formats: