Context Navigation

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

Revision 1733, 79.3 KB checked in by mattausch, 18 years ago (diff)
removed bug from dirtycandidates

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

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

Download in other formats: