Context Navigation

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

Revision 1845, 81.2 KB checked in by mattausch, 18 years ago (diff)
improved object pvs

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

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

Download in other formats: