Context Navigation

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

Revision 1633, 76.1 KB checked in by mattausch, 18 years ago (diff)
worked on gradient method for vsposp

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

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

Download in other formats: