Context Navigation

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

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

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

Download in other formats: