Context Navigation

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

Revision 2003, 84.5 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: