Context Navigation

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

Revision 1915, 82.6 KB checked in by mattausch, 18 years ago (diff)
implemented pvs correction (debug version)

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

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

Download in other formats: