Context Navigation

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

Revision 1990, 84.4 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: