Context Navigation

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

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

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

Download in other formats: