Context Navigation

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

Revision 1919, 82.6 KB checked in by mattausch, 18 years ago (diff)
added mechanism for histogram on certain MB in hierarchymanager no more bug in undersampling estimation added sampling strategy to spatial box based (also for eval) added testing scripts

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

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

Download in other formats: