Context Navigation

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

Revision 1727, 78.6 KB checked in by mattausch, 18 years ago (diff)
implemented several accelleration svhemes for the gradient method

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

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

Download in other formats: