Context Navigation

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

Revision 1909, 80.7 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: