Context Navigation

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

Revision 1749, 79.2 KB checked in by mattausch, 18 years ago (diff)
removed bug from exportviewcells

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

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

Download in other formats: