Context Navigation

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

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

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

Download in other formats: