Context Navigation

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

Revision 1911, 80.9 KB checked in by mattausch, 17 years ago (diff)
added support for pvs correction (warning: does not yet compile)

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

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

Download in other formats: