Context Navigation

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

Revision 1610, 75.1 KB checked in by mattausch, 18 years ago (diff)
removed vsposp bug

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

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

Download in other formats: