Context Navigation

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

Revision 1303, 69.9 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "VspTree.h"
8	#include "Mesh.h"
9	#include "common.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "KdTree.h"
19	#include "KdIntersectable.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 int pvs,
43	const int lower,
44	const int 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
59	static bool ViewCellHasMultipleReferences(Intersectable *obj,
60	ViewCell *vc,
61	bool checkOnlyMailed)
62	{
63	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
64	//return false;
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 VspTreeStatistics::Print(ostream &app) const
83	{
84	app << "=========== VspTree statistics ===============\n";
85
86	app << setprecision(4);
87
88	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
89
90	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
91
92	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
93
94	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
95
96	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
97
98	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
99
100	for (int i = 0; i < 3; ++ i)
101	app << splits[i] << " ";
102	app << endl;
103
104	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
105	<< maxDepthNodes * 100 / (double)Leaves() << endl;
106
107	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
108	<< minPvsNodes * 100 / (double)Leaves() << endl;
109
110	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
111	<< minRaysNodes * 100 / (double)Leaves() << endl;
112
113	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
114	<< maxCostNodes * 100 / (double)Leaves() << endl;
115
116	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
117	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
118
119	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
120	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
121
122	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
123
124	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
125
126	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
127
128	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
129
130	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
131	//app << "#N_PVS: " << pvs << endl;
132
133	//app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
134
135	app << "========== END OF VspTree statistics ==========\n";
136	}
137
138
139
140	/******************************************************************/
141	/* class VspNode implementation */
142	/******************************************************************/
143
144
145	VspNode::VspNode():
146	mParent(NULL), mTreeValid(true), mTimeStamp(0)
147	{}
148
149
150	VspNode::VspNode(VspInterior *parent):
151	mParent(parent), mTreeValid(true)
152	{}
153
154
155	bool VspNode::IsRoot() const
156	{
157	return mParent == NULL;
158	}
159
160
161	VspInterior *VspNode::GetParent()
162	{
163	return mParent;
164	}
165
166
167	void VspNode::SetParent(VspInterior *parent)
168	{
169	mParent = parent;
170	}
171
172
173	bool VspNode::IsSibling(VspNode *n) const
174	{
175	return ((this != n) && mParent &&
176	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
177	}
178
179
180	int VspNode::GetDepth() const
181	{
182	int depth = 0;
183	VspNode *p = mParent;
184
185	while (p)
186	{
187	p = p->mParent;
188	++ depth;
189	}
190
191	return depth;
192	}
193
194
195	bool VspNode::TreeValid() const
196	{
197	return mTreeValid;
198	}
199
200
201	void VspNode::SetTreeValid(const bool v)
202	{
203	mTreeValid = v;
204	}
205
206
207	/****************************************************************/
208	/* class VspInterior implementation */
209	/****************************************************************/
210
211
212	VspInterior::VspInterior(const AxisAlignedPlane &plane):
213	mPlane(plane), mFront(NULL), mBack(NULL)
214	{}
215
216
217	VspInterior::~VspInterior()
218	{
219	DEL_PTR(mFront);
220	DEL_PTR(mBack);
221	}
222
223
224	bool VspInterior::IsLeaf() const
225	{
226	return false;
227	}
228
229
230	VspNode *VspInterior::GetBack()
231	{
232	return mBack;
233	}
234
235
236	VspNode *VspInterior::GetFront()
237	{
238	return mFront;
239	}
240
241
242	AxisAlignedPlane VspInterior::GetPlane() const
243	{
244	return mPlane;
245	}
246
247
248	float VspInterior::GetPosition() const
249	{
250	return mPlane.mPosition;
251	}
252
253
254	int VspInterior::GetAxis() const
255	{
256	return mPlane.mAxis;
257	}
258
259
260	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
261	{
262	if (mBack == oldChild)
263	mBack = newChild;
264	else
265	mFront = newChild;
266	}
267
268
269	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
270	{
271	mBack = back;
272	mFront = front;
273	}
274
275
276	AxisAlignedBox3 VspInterior::GetBoundingBox() const
277	{
278	return mBoundingBox;
279	}
280
281
282	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
283	{
284	mBoundingBox = box;
285	}
286
287
288	int VspInterior::Type() const
289	{
290	return Interior;
291	}
292
293
294
295	/****************************************************************/
296	/* class VspLeaf implementation */
297	/****************************************************************/
298
299
300	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL), mSubdivisionCandidate(NULL)
301	{
302	}
303
304
305	VspLeaf::~VspLeaf()
306	{
307	DEL_PTR(mPvs);
308	CLEAR_CONTAINER(mVssRays);
309	}
310
311
312	int VspLeaf::Type() const
313	{
314	return Leaf;
315	}
316
317
318	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
319	mViewCell(viewCell)
320	{
321	}
322
323
324	VspLeaf::VspLeaf(VspInterior *parent):
325	VspNode(parent), mViewCell(NULL), mPvs(NULL)
326	{}
327
328
329
330	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
331	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
332	{
333	}
334
335	ViewCellLeaf *VspLeaf::GetViewCell() const
336	{
337	return mViewCell;
338	}
339
340	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
341	{
342	mViewCell = viewCell;
343	}
344
345
346	bool VspLeaf::IsLeaf() const
347	{
348	return true;
349	}
350
351
352	/*************************************************************************/
353	/* class VspTree implementation */
354	/*************************************************************************/
355
356
357	VspTree::VspTree():
358	mRoot(NULL),
359	mOutOfBoundsCell(NULL),
360	mStoreRays(false),
361	mTimeStamp(1),
362	mHierarchyManager(NULL)
363	{
364	bool randomize = false;
365	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
366	if (randomize)
367	Randomize(); // initialise random generator for heuristics
368
369	//-- termination criteria for autopartition
370	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
371	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
372	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
373	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
374	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
375
376	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
377	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
378
379	//-- max cost ratio for early tree termination
380	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
381
382	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
383	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
384
385	//-- factors for bsp tree split plane heuristics
386	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
387
388	//-- partition criteria
389	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
390	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
391
392	// if only the driving axis is used for axis aligned split
393	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
394
395	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
396	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
397
398	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
399	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
400
401	//Environment::GetSingleton()->GetBoolValue("VspTree.useKdPvsForHeuristics", mUseKdPvsForHeuristics);
402
403	char subdivisionStatsLog[100];
404	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
405	mSubdivisionStats.open(subdivisionStatsLog);
406
407	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
408	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
409
410
411	//-- debug output
412
413	Debug << "***** VSP options ****** " << endl;
414
415	Debug << "max depth: " << mTermMaxDepth << endl;
416	Debug << "min PVS: " << mTermMinPvs << endl;
417	Debug << "min probabiliy: " << mTermMinProbability << endl;
418	Debug << "min rays: " << mTermMinRays << endl;
419	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
420	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
421	Debug << "miss tolerance: " << mTermMissTolerance << endl;
422	Debug << "max view cells: " << mMaxViewCells << endl;
423	Debug << "randomize: " << randomize << endl;
424
425	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
426	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
427	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
428	Debug << "max memory: " << mMaxMemory << endl;
429	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
430	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
431	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
432
433	Debug << "circulating axis: " << mCirculatingAxis << endl;
434	Debug << "minband: " << mMinBand << endl;
435	Debug << "maxband: " << mMaxBand << endl;
436
437	mLocalSubdivisionCandidates = new vector<SortableEntry>;
438
439	Debug << endl;
440	}
441
442
443	VspViewCell *VspTree::GetOutOfBoundsCell()
444	{
445	return mOutOfBoundsCell;
446	}
447
448
449	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
450	{
451	if (!mOutOfBoundsCell)
452	{
453	mOutOfBoundsCell = new VspViewCell();
454	mOutOfBoundsCell->SetId(-1);
455	mOutOfBoundsCell->SetValid(false);
456	}
457
458	return mOutOfBoundsCell;
459	}
460
461
462	const VspTreeStatistics &VspTree::GetStatistics() const
463	{
464	return mVspStats;
465	}
466
467
468	VspTree::~VspTree()
469	{
470	DEL_PTR(mRoot);
471	DEL_PTR(mLocalSubdivisionCandidates);
472	}
473
474
475	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
476	AxisAlignedBox3 *forcedBoundingBox)
477	{
478	if (forcedBoundingBox)
479	{
480	mBoundingBox = *forcedBoundingBox;
481	}
482	else // compute vsp tree bounding box
483	{
484	mBoundingBox.Initialize();
485	VssRayContainer::const_iterator rit, rit_end = rays.end();
486
487	//-- compute bounding box
488	for (rit = rays.begin(); rit != rit_end; ++ rit)
489	{
490	VssRay ray = rit;
491
492	// compute bounding box of view space
493	mBoundingBox.Include(ray->GetTermination());
494	mBoundingBox.Include(ray->GetOrigin());
495	}
496	}
497	}
498
499
500	void VspTree::AddSubdivisionStats(const int viewCells,
501	const float renderCostDecr,
502	const float totalRenderCost,
503	const float avgRenderCost)
504	{
505	mSubdivisionStats
506	<< "#ViewCells\n" << viewCells << endl
507	<< "#RenderCostDecrease\n" << renderCostDecr << endl
508	<< "#TotalRenderCost\n" << totalRenderCost << endl
509	<< "#AvgRenderCost\n" << avgRenderCost << endl;
510	}
511
512
513	// TODO: return memory usage in MB
514	float VspTree::GetMemUsage() const
515	{
516	return (float)
517	(sizeof(VspTree) +
518	mVspStats.Leaves() * sizeof(VspLeaf) +
519	mCreatedViewCells * sizeof(VspViewCell) +
520	mVspStats.pvs * sizeof(PvsData) +
521	mVspStats.Interior() * sizeof(VspInterior) +
522	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
523	}
524
525
526	inline bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
527	{
528	const bool localTerminationCriteriaMet = (0
529	//\|\| ((int)data.mRays->size() <= mTermMinRays)
530	//\|\| (data.mPvs <= mTermMinPvs)
531	//\|\| (data.mProbability <= mTermMinProbability)
532	//\|\| (data.GetAvgRayContribution() > mTermMaxRayContribution)
533	//\|\| (data.mDepth >= mTermMaxDepth)
534	);
535
536	if (1 && localTerminationCriteriaMet)
537	{
538	Debug << "******local termination *******" << endl;
539	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
540	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
541	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
542	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
543	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
544	}
545
546	return localTerminationCriteriaMet;
547	}
548
549
550	inline bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
551	{
552	const bool terminationCriteriaMet = (0
553	// \|\| mOutOfMemory
554	\|\| (mVspStats.Leaves() >= mMaxViewCells)
555	//\|\| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
556	);
557
558	if (0 && terminationCriteriaMet)
559	{
560	Debug << "******* terminationCriteriaMet *******" << endl;
561	Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
562	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
563	}
564	return terminationCriteriaMet;
565	}
566
567
568	void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
569	{
570	//-- create new view cell
571	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
572
573	VspViewCell *viewCell = new VspViewCell();
574	leaf->SetViewCell(viewCell);
575
576	int conSamp = 0;
577	float sampCon = 0.0f;
578
579	if (updatePvs)
580	{
581	//-- update pvs of view cell
582	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
583
584	// update scalar pvs size value
585	ObjectPvs &pvs = viewCell->GetPvs();
586	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
587
588	mVspStats.contributingSamples += conSamp;
589	mVspStats.sampleContributions += (int)sampCon;
590	}
591
592
593	//-- store additional info
594	if (mStoreRays)
595	{
596	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
597
598	for (it = tData.mRays->begin(); it != it_end; ++ it)
599	{
600	(*it).mRay->Ref();
601	leaf->mVssRays.push_back((*it).mRay);
602	}
603	}
604
605	// set view cell values
606	viewCell->mLeaf = leaf;
607
608	viewCell->SetVolume(tData.mProbability);
609	leaf->mProbability = tData.mProbability;
610	}
611
612
613	void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
614	{
615	const float costDecr = sc.GetRenderCostDecrease();
616
617	AddSubdivisionStats(mVspStats.Leaves(),
618	costDecr,
619	mTotalCost,
620	(float)mTotalPvsSize / (float)mVspStats.Leaves());
621	}
622
623
624	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
625	SubdivisionCandidate *splitCandidate,
626	const bool globalCriteriaMet)
627	{
628	// todo remove dynamic cast
629	VspSubdivisionCandidate *sc =
630	dynamic_cast<VspSubdivisionCandidate *>(splitCandidate);
631
632	VspTraversalData &tData = sc->mParentData;
633	VspNode *newNode = tData.mNode;
634
635	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
636	{
637	//-- continue subdivision
638	VspTraversalData tFrontData;
639	VspTraversalData tBackData;
640
641	// create new interior node and two leaf node
642	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
643	const int maxCostMisses = sc->mMaxCostMisses;
644
645	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
646
647	// how often was max cost ratio missed in this branch?
648	tFrontData.mMaxCostMisses = maxCostMisses;
649	tBackData.mMaxCostMisses = maxCostMisses;
650
651	mTotalCost -= sc->GetRenderCostDecrease();
652	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
653
654	// subdivision statistics
655	if (1) EvalSubdivisionStats(*sc);
656
657	//-- evaluate new split candidates for global greedy cost heuristics
658
659	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
660	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
661
662	EvalSubdivisionCandidate(*frontCandidate);
663	EvalSubdivisionCandidate(*backCandidate);
664
665	// cross reference
666	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
667	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
668
669	tQueue.Push(frontCandidate);
670	tQueue.Push(backCandidate);
671
672	// delete old leaf node
673	//DEL_PTR(tData.mNode);
674	}
675
676	if (newNode->IsLeaf()) // subdivision terminated
677	{
678	// view cell is created during subdivision
679	//CreateViewCell(tData);
680
681	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
682	ViewCell *viewCell = leaf->GetViewCell();
683
684	int conSamp = 0;
685	float sampCon = 0.0f;
686
687	#if 0
688	//-- store pvs optained from rays
689	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
690
691	// update scalar pvs size value
692	ObjectPvs &pvs = viewCell->GetPvs();
693	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
694
695	mVspStats.contributingSamples += conSamp;
696	mVspStats.sampleContributions += (int)sampCon;
697	#endif
698	//-- store additional info
699	if (mStoreRays)
700	{
701	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
702	for (it = tData.mRays->begin(); it != it_end; ++ it)
703	{
704	(*it).mRay->Ref();
705	leaf->mVssRays.push_back((*it).mRay);
706	}
707	}
708
709	// finally evaluate statistics for this leaf
710	EvaluateLeafStats(tData);
711
712	// detach node so it won't get deleted
713	tData.mNode = NULL;
714	}
715
716	return newNode;
717	}
718
719
720	void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate)
721	{
722	float frontProb;
723	float backProb;
724
725	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
726
727	// compute locally best split plane
728	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
729	splitCandidate.mSplitPlane,
730	frontProb,
731	backProb);
732
733	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
734
735	// max cost threshold violated?
736	splitCandidate.mMaxCostMisses = maxCostRatioViolated ?
737	splitCandidate.mParentData.mMaxCostMisses + 1:
738	splitCandidate.mParentData.mMaxCostMisses;
739
740	float oldRenderCost;
741
742	// compute global decrease in render cost
743	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
744	splitCandidate.mParentData,
745	oldRenderCost);
746
747	splitCandidate.SetRenderCostDecrease(renderCostDecr);
748
749	#if 1
750	const float priority = (float)-splitCandidate.mParentData.mDepth;
751	#else
752	// take render cost of node into account
753	// otherwise danger of being stuck in a local minimum!!
754	const float factor = mRenderCostDecreaseWeight;
755	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
756	#endif
757
758	splitCandidate.SetPriority(priority);
759	}
760
761
762	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
763	VspTraversalData &tData,
764	VspTraversalData &frontData,
765	VspTraversalData &backData)
766	{
767	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
768
769	//-- the front and back traversal data is filled with the new values
770
771	frontData.mDepth = tData.mDepth + 1;
772	backData.mDepth = tData.mDepth + 1;
773
774	frontData.mRays = new RayInfoContainer();
775	backData.mRays = new RayInfoContainer();
776
777	//-- subdivide rays
778	SplitRays(splitPlane,
779	*tData.mRays,
780	*frontData.mRays,
781	*backData.mRays);
782
783	//-- compute pvs
784
785	frontData.mPvs = EvalPvsSize(*frontData.mRays);
786	backData.mPvs = EvalPvsSize(*backData.mRays);
787
788	Debug << "f pvs: " << frontData.mPvs << " b pvs: " << backData.mPvs << " pvs " << tData.mPvs << endl;
789
790	// split front and back node geometry and compute area
791	tData.mBoundingBox.Split(splitPlane.mAxis,
792	splitPlane.mPosition,
793	frontData.mBoundingBox,
794	backData.mBoundingBox);
795
796	frontData.mProbability = frontData.mBoundingBox.GetVolume();
797	backData.mProbability = tData.mProbability - frontData.mProbability;
798
799
800	///////////////////////////////////////////
801	// subdivide further
802
803	// store maximal and minimal depth
804	if (tData.mDepth > mVspStats.maxDepth)
805	{
806	Debug << "max depth increases to " << tData.mDepth
807	<< " at " << mVspStats.Leaves() << " leaves" << endl;
808	mVspStats.maxDepth = tData.mDepth;
809	}
810
811	// two more leaves
812	mVspStats.nodes += 2;
813
814	VspInterior *interior = new VspInterior(splitPlane);
815
816
817	//-- create front and back leaf
818
819	VspInterior *parent = leaf->GetParent();
820
821	// replace a link from node's parent
822	if (parent)
823	{
824	parent->ReplaceChildLink(leaf, interior);
825	interior->SetParent(parent);
826
827	// remove "parent" view cell from pvs of all objects (traverse trough rays)
828	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
829	}
830	else // new root
831	{
832	mRoot = interior;
833	}
834
835	VspLeaf *frontLeaf = new VspLeaf(interior);
836	VspLeaf *backLeaf = new VspLeaf(interior);
837
838	// and setup child links
839	interior->SetupChildLinks(frontLeaf, backLeaf);
840
841	// add bounding box
842	interior->SetBoundingBox(tData.mBoundingBox);
843
844	// set front and back leaf
845	frontData.mNode = frontLeaf;
846	backData.mNode = backLeaf;
847
848	// explicitely create front and back view cell
849	CreateViewCell(frontData, false);
850	CreateViewCell(backData, false);
851
852
853	#if WORK_WITH_VIEWCELL_PVS
854	// create front and back view cell
855	// add front and back view cell to "Potentially Visbilie View Cells"
856	// of the objects in front and back pvs
857
858	AddViewCellReferences(frontLeaf->GetViewCell());
859	AddViewCellReferences(backLeaf->GetViewCell());
860	#endif
861
862	interior->mTimeStamp = mTimeStamp ++;
863
864	return interior;
865	}
866
867
868	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
869	{
870	KdLeaf::NewMail();
871
872	// remove the parents from the object pvss
873	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
874
875	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
876	{
877	Intersectable object = (oit).first;
878	// HACK: make sure that the view cell is removed from the pvs
879	const float high_contri = 9999999;
880
881	// remove reference count of view cells
882	object->mViewCellPvs.RemoveSample(parent, high_contri);
883	}
884	}
885
886
887	void VspTree::AddViewCellReferences(ViewCell *vc) const
888	{
889	KdLeaf::NewMail();
890
891	// Add front view cell to the object pvsss
892	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
893
894	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
895	{
896	Intersectable object = (oit).first;
897
898	// increase reference count of view cells
899	object->mViewCellPvs.AddSample(vc, 1);
900	}
901	}
902
903
904	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
905	const RayInfoContainer &rays,
906	float &sampleContributions,
907	int &contributingSamples)
908	{
909	sampleContributions = 0;
910	contributingSamples = 0;
911
912	RayInfoContainer::const_iterator it, it_end = rays.end();
913
914	ViewCellLeaf *vc = leaf->GetViewCell();
915
916	// add contributions from samples to the PVS
917	for (it = rays.begin(); it != it_end; ++ it)
918	{
919	float sc = 0.0f;
920	VssRay ray = (it).mRay;
921
922	bool madeContrib = false;
923	float contribution;
924
925	Intersectable *obj = ray->mTerminationObject;
926
927	if (obj)
928	{
929	madeContrib =
930	mViewCellsManager->AddSampleToPvs(
931	obj,
932	ray->mTermination,
933	vc,
934	ray->mPdf,
935	contribution);
936
937	sc += contribution;
938	}
939
940	obj = ray->mOriginObject;
941
942	if (obj)
943	{
944	madeContrib =
945	mViewCellsManager->AddSampleToPvs(
946	obj,
947	ray->mOrigin,
948	vc,
949	ray->mPdf,
950	contribution);
951
952	sc += contribution;
953	}
954
955	if (madeContrib)
956	{
957	++ contributingSamples;
958	}
959
960	// store rays for visualization
961	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
962	}
963	}
964
965
966	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
967	const int axis,
968	float minBand,
969	float maxBand)
970	{
971	mLocalSubdivisionCandidates->clear();
972
973	int requestedSize = 2 * (int)(rays.size());
974
975	// creates a sorted split candidates array
976	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
977	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
978	{
979	delete mLocalSubdivisionCandidates;
980	mLocalSubdivisionCandidates = new vector<SortableEntry>;
981	}
982
983	mLocalSubdivisionCandidates->reserve(requestedSize);
984
985	float pos;
986	RayInfoContainer::const_iterator rit, rit_end = rays.end();
987
988	//-- insert all queries
989	for (rit = rays.begin(); rit != rit_end; ++ rit)
990	{
991	const bool positive = (*rit).mRay->HasPosDir(axis);
992
993	pos = (*rit).ExtrapOrigin(axis);
994
995	mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
996	pos, (*rit).mRay));
997
998	pos = (*rit).ExtrapTermination(axis);
999
1000	mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1001	pos, (*rit).mRay));
1002	}
1003
1004	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1005	}
1006
1007
1008	int VspTree::PrepareHeuristics(KdLeaf *leaf)
1009	{
1010	int pvsSize = 0;
1011
1012	if (!leaf->Mailed())
1013	{
1014	leaf->Mail();
1015	leaf->mCounter = 1;
1016	// add objects without the objects which are in several kd leaves
1017	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1018	}
1019	else
1020	{
1021	++ leaf->mCounter;
1022	}
1023
1024	//-- the objects belonging to several leaves must be handled seperately
1025	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1026
1027	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1028	{
1029	Intersectable object = oit;
1030
1031	if (!object->Mailed())
1032	{
1033	object->Mail();
1034	object->mCounter = 1;
1035
1036	++ pvsSize;
1037	}
1038	else
1039	{
1040	++ object->mCounter;
1041	}
1042	}
1043
1044	return pvsSize;
1045	}
1046
1047
1048	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1049	{
1050	Intersectable::NewMail();
1051	KdNode::NewMail();
1052	BvhLeaf::NewMail();
1053
1054	int pvsSize = 0;
1055
1056	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1057
1058	// set all kd nodes / objects as belonging to the front pvs
1059	for (ri = rays.begin(); ri != ri_end; ++ ri)
1060	{
1061	VssRay ray = (ri).mRay;
1062
1063	pvsSize += PrepareHeuristics(*ray, true);
1064	pvsSize += PrepareHeuristics(*ray, false);
1065	}
1066
1067	return pvsSize;
1068	}
1069
1070
1071	int VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1072	{
1073	int pvs = 0;
1074
1075	// leaf falls out of right pvs
1076	if (-- leaf->mCounter == 0)
1077	{
1078	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1079	}
1080
1081	//-- separately handle objects which are in several kd leaves
1082
1083	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1084
1085	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1086	{
1087	Intersectable object = oit;
1088
1089	if (-- object->mCounter == 0)
1090	{
1091	++ pvs;
1092	}
1093	}
1094
1095	return pvs;
1096	}
1097
1098
1099	int VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1100	{
1101	if (leaf->Mailed())
1102	return 0;
1103
1104	leaf->Mail();
1105
1106	// add objects without those which are part of several kd leaves
1107	int pvs = ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1108
1109	// separately handle objects which are part of several kd leaves
1110	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1111
1112	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1113	{
1114	Intersectable object = oit;
1115
1116	// object not previously in pvs
1117	if (!object->Mailed())
1118	{
1119	object->Mail();
1120	++ pvs;
1121	}
1122	}
1123
1124	return pvs;
1125	}
1126
1127
1128	void VspTree::EvalHeuristics(const SortableEntry &ci,
1129	int &pvsLeft,
1130	int &pvsRight) const
1131	{
1132	VssRay *ray = ci.ray;
1133
1134	// eval changes in pvs causes by min event
1135	if (ci.type == SortableEntry::ERayMin)
1136	{
1137	pvsLeft += EvalMinEventContribution(*ray, true);
1138	pvsLeft += EvalMinEventContribution(*ray, false);
1139	}
1140	else // eval changes in pvs causes by max event
1141	{
1142	pvsRight -= EvalMaxEventContribution(*ray, true);
1143	pvsRight -= EvalMaxEventContribution(*ray, false);
1144	}
1145	}
1146
1147
1148	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1149	const AxisAlignedBox3 &box,
1150	const int axis,
1151	float &position)
1152	{
1153	// get subset of rays
1154	RayInfoContainer usedRays;
1155
1156	if (mMaxTests < (int)tData.mRays->size())
1157	{
1158	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
1159	}
1160	else
1161	{
1162	usedRays = *tData.mRays;
1163	}
1164
1165	const float minBox = box.Min(axis);
1166	const float maxBox = box.Max(axis);
1167
1168	const float sizeBox = maxBox - minBox;
1169
1170	const float minBand = minBox + mMinBand * sizeBox;
1171	const float maxBand = minBox + mMaxBand * sizeBox;
1172
1173	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1174
1175	// prepare the sweep
1176	// note: returns pvs size => no need t give pvs size as function parameter
1177	const int pvsSize = PrepareHeuristics(usedRays);
1178
1179	// go through the lists, count the number of objects left and right
1180	// and evaluate the following cost funcion:
1181	// C = ct_div_ci + (qlrl + qrrr)/queries
1182
1183	int pvsl = 0;
1184	int pvsr = pvsSize;
1185
1186	int pvsBack = pvsl;
1187	int pvsFront = pvsr;
1188
1189	float sum = (float)pvsSize * sizeBox;
1190	float minSum = 1e20f;
1191
1192	// if no good split can be found, take mid split
1193	position = minBox + 0.5f * sizeBox;
1194
1195	// the relative cost ratio
1196	float ratio = 99999999.0f;
1197	bool splitPlaneFound = false;
1198
1199	Intersectable::NewMail();
1200	KdLeaf::NewMail();
1201	BvhLeaf::NewMail();
1202
1203	//-- traverse through visibility events
1204	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSubdivisionCandidates->end();
1205
1206	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1207	{
1208	// compute changes to front and back pvs
1209	EvalHeuristics(*ci, pvsl, pvsr);
1210
1211	// Note: sufficient to compare size of bounding boxes of front and back side?
1212	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1213	{
1214	float currentPos;
1215
1216	// HACK: current positition is BETWEEN visibility events
1217	if (0 && ((ci + 1) != ci_end))
1218	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1219	else
1220	currentPos = (*ci).value;
1221
1222	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1223
1224
1225	if (sum < minSum)
1226	{
1227	splitPlaneFound = true;
1228
1229	minSum = sum;
1230	position = currentPos;
1231
1232	pvsBack = pvsl;
1233	pvsFront = pvsr;
1234	}
1235	}
1236	}
1237
1238
1239	//-- compute cost
1240
1241	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1242	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1243
1244	const float pOverall = sizeBox;
1245	const float pBack = position - minBox;
1246	const float pFront = maxBox - position;
1247
1248	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1249	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1250	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1251
1252	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1253	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1254
1255	if (splitPlaneFound)
1256	{
1257	ratio = newRenderCost / oldRenderCost;
1258	}
1259
1260	const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1261
1262	Debug << "\n§§§§ eval local cost §§§§" << endl
1263	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1264	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1265	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1266	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1267
1268	return ratio;
1269	}
1270
1271
1272	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1273	AxisAlignedPlane &plane,
1274	float &pFront,
1275	float &pBack)
1276	{
1277	float nPosition[3];
1278	float nCostRatio[3];
1279	float nProbFront[3];
1280	float nProbBack[3];
1281
1282	// create bounding box of node geometry
1283	AxisAlignedBox3 box = tData.mBoundingBox;
1284
1285	int sAxis = 0;
1286	int bestAxis = -1;
1287
1288	// if we use some kind of specialised fixed axis
1289	const bool useSpecialAxis =
1290	mOnlyDrivingAxis \|\| mCirculatingAxis;
1291
1292	if (mCirculatingAxis)
1293	{
1294	int parentAxis = 0;
1295	VspNode *parent = tData.mNode->GetParent();
1296
1297	if (parent)
1298	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1299
1300	sAxis = (parentAxis + 1) % 3;
1301	}
1302	else if (mOnlyDrivingAxis)
1303	{
1304	sAxis = box.Size().DrivingAxis();
1305	}
1306
1307	for (int axis = 0; axis < 3; ++ axis)
1308	{
1309	if (!useSpecialAxis \|\| (axis == sAxis))
1310	{
1311	if (mUseCostHeuristics)
1312	{
1313	//-- place split plane using heuristics
1314	nCostRatio[axis] =
1315	EvalLocalCostHeuristics(tData,
1316	box,
1317	axis,
1318	nPosition[axis]);
1319	}
1320	else
1321	{
1322	//-- split plane position is spatial median
1323	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1324	nCostRatio[axis] = EvalLocalSplitCost(tData,
1325	box,
1326	axis,
1327	nPosition[axis],
1328	nProbFront[axis],
1329	nProbBack[axis]);
1330	}
1331
1332	if (bestAxis == -1)
1333	{
1334	bestAxis = axis;
1335	}
1336	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1337	{
1338	bestAxis = axis;
1339	}
1340	}
1341	}
1342
1343	//-- assign values of best split
1344	plane.mAxis = bestAxis;
1345	plane.mPosition = nPosition[bestAxis]; // split plane position
1346
1347	pFront = nProbFront[bestAxis];
1348	pBack = nProbBack[bestAxis];
1349
1350	return nCostRatio[bestAxis];
1351	}
1352
1353
1354	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1355	const VspTraversalData &data,
1356	float &normalizedOldRenderCost) const
1357	{
1358	float pvsFront = 0;
1359	float pvsBack = 0;
1360	float totalPvs = 0;
1361
1362	const float viewSpaceVol = mBoundingBox.GetVolume();
1363
1364	// create unique ids for pvs heuristics
1365	Intersectable::NewMail(3);
1366	KdLeaf::NewMail(3);
1367	BvhLeaf::NewMail(3);
1368
1369	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1370
1371	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1372	{
1373	RayInfo rayInf = *rit;
1374
1375	float t;
1376	VssRay *ray = rayInf.mRay;
1377
1378	// classify ray
1379	const int cf =
1380	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1381	candidatePlane.mPosition, t);
1382
1383	// evaluate contribution of ray endpoint to front and back pvs
1384	// with respect to the classification
1385	UpdateContributionsToPvs(*ray, true, cf, pvsFront, pvsBack, totalPvs);
1386	UpdateContributionsToPvs(*ray, false, cf, pvsFront, pvsBack, totalPvs);
1387	}
1388
1389	AxisAlignedBox3 frontBox;
1390	AxisAlignedBox3 backBox;
1391
1392	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1393
1394	// probability that view point lies in back / front node
1395	float pOverall = data.mProbability;
1396	float pFront = pFront = frontBox.GetVolume();
1397	float pBack = pOverall - pFront;
1398
1399
1400	//-- pvs rendering heuristics
1401
1402	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1403	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1404
1405	// only render cost heuristics or combined with standard deviation
1406	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1407	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1408	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1409
1410	const float oldRenderCost = pOverall * penaltyOld;
1411	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1412
1413	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1414
1415	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1416
1417	Debug << "\neval vsp render cost decrease" << endl
1418	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1419	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1420	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1421	<< "render cost decrease: " << renderCostDecrease << endl;
1422
1423	return renderCostDecrease;
1424	}
1425
1426
1427
1428	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1429	const AxisAlignedBox3 &box,
1430	const int axis,
1431	const float &position,
1432	float &pFront,
1433	float &pBack) const
1434	{
1435	float pvsTotal = 0;
1436	float pvsFront = 0;
1437	float pvsBack = 0;
1438
1439	// create unique ids for pvs heuristics
1440	Intersectable::NewMail(3);
1441	BvhLeaf::NewMail(3);
1442	KdLeaf::NewMail(3);
1443
1444	const int pvsSize = data.mPvs;
1445
1446	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1447
1448	// this is the main ray classification loop!
1449	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1450	{
1451	VssRay ray = (rit).mRay;
1452
1453	// determine the side of this ray with respect to the plane
1454	float t;
1455	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1456
1457	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1458	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1459	}
1460
1461
1462	//-- evaluate cost heuristics
1463
1464	float pOverall = data.mProbability;
1465
1466	// we use spatial mid split => simplified computation
1467	pBack = pFront = pOverall * 0.5f;
1468
1469	const float newCost = pvsBack * pBack + pvsFront * pFront;
1470	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1471
1472	#ifdef _DEBUG
1473	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1474	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1475	#endif
1476
1477	return (mCtDivCi + newCost) / oldCost;
1478	}
1479
1480
1481	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1482	const int cf,
1483	float &frontPvs,
1484	float &backPvs,
1485	float &totalPvs) const
1486	{
1487	if (!obj) return;
1488
1489	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1490	const int renderCost = 1;
1491
1492	// object in no pvs => new
1493	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1494	{
1495	totalPvs += renderCost;
1496	}
1497
1498	// QUESTION matt: is it safe to assume that
1499	// the object belongs to no pvs in this case?
1500	//if (cf == Ray::COINCIDENT) return;
1501
1502	if (cf >= 0) // front pvs
1503	{
1504	if (!obj->Mailed() && !obj->Mailed(2))
1505	{
1506	frontPvs += renderCost;
1507
1508	// already in back pvs => in both pvss
1509	if (obj->Mailed(1))
1510	obj->Mail(2);
1511	else
1512	obj->Mail();
1513	}
1514	}
1515
1516	if (cf <= 0) // back pvs
1517	{
1518	if (!obj->Mailed(1) && !obj->Mailed(2))
1519	{
1520	backPvs += renderCost;
1521
1522	// already in front pvs => in both pvss
1523	if (obj->Mailed())
1524	obj->Mail(2);
1525	else
1526	obj->Mail(1);
1527	}
1528	}
1529	}
1530
1531
1532	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1533	const int cf,
1534	float &frontPvs,
1535	float &backPvs,
1536	float &totalPvs) const
1537	{
1538	if (!leaf) return;
1539
1540	const int renderCost = (int)leaf->mObjects.size();
1541
1542	// leaf in no pvs => new
1543	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1544	{
1545	totalPvs += renderCost;
1546	}
1547
1548	// QUESTION matt: is it safe to assume that
1549	// the leaf belongs to no pvs in this case?
1550	//if (cf == Ray::COINCIDENT) return;
1551
1552	if (cf >= 0) // front pvs
1553	{
1554	if (!leaf->Mailed() && !leaf->Mailed(2))
1555	{
1556	frontPvs += renderCost;
1557
1558	// already in back pvs => in both pvss
1559	if (leaf->Mailed(1))
1560	leaf->Mail(2);
1561	else
1562	leaf->Mail();
1563	}
1564	}
1565
1566	if (cf <= 0) // back pvs
1567	{
1568	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1569	{
1570	backPvs += renderCost;
1571
1572	// already in front pvs => in both pvss
1573	if (leaf->Mailed())
1574	{
1575	leaf->Mail(2);
1576	}
1577	else
1578	leaf->Mail(1);
1579	}
1580	}
1581	}
1582
1583
1584
1585	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1586	const int cf,
1587	float &frontPvs,
1588	float &backPvs,
1589	float &totalPvs) const
1590	{
1591	if (!leaf) return;
1592
1593	// the objects which are referenced in this and only this leaf
1594	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1595
1596	// newly found leaf
1597	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1598	{
1599	totalPvs += contri;
1600	}
1601
1602	// recursivly update contributions of yet unclassified objects
1603	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1604
1605	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1606	{
1607	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1608	}
1609
1610	// QUESTION matt: is it safe to assume that
1611	// the object belongs to no pvs in this case?
1612	//if (cf == Ray::COINCIDENT) return;
1613
1614	if (cf >= 0) // front pvs
1615	{
1616	if (!leaf->Mailed() && !leaf->Mailed(2))
1617	{
1618	frontPvs += contri;
1619
1620	// already in back pvs => in both pvss
1621	if (leaf->Mailed(1))
1622	leaf->Mail(2);
1623	else
1624	leaf->Mail();
1625	}
1626	}
1627
1628	if (cf <= 0) // back pvs
1629	{
1630	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1631	{
1632	backPvs += contri;
1633
1634	// already in front pvs => in both pvss
1635	if (leaf->Mailed())
1636	leaf->Mail(2);
1637	else
1638	leaf->Mail(1);
1639	}
1640	}
1641	}
1642
1643
1644	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1645	const bool onlyUnmailed,
1646	const int maxPvsSize) const
1647	{
1648	stack<VspNode *> nodeStack;
1649	nodeStack.push(mRoot);
1650
1651	while (!nodeStack.empty())
1652	{
1653	VspNode *node = nodeStack.top();
1654	nodeStack.pop();
1655
1656	if (node->IsLeaf())
1657	{
1658	// test if this leaf is in valid view space
1659	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1660	if (leaf->TreeValid() &&
1661	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1662	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
1663	{
1664	leaves.push_back(leaf);
1665	}
1666	}
1667	else
1668	{
1669	VspInterior interior = dynamic_cast<VspInterior >(node);
1670
1671	nodeStack.push(interior->GetBack());
1672	nodeStack.push(interior->GetFront());
1673	}
1674	}
1675	}
1676
1677
1678	AxisAlignedBox3 VspTree::GetBoundingBox() const
1679	{
1680	return mBoundingBox;
1681	}
1682
1683
1684	VspNode *VspTree::GetRoot() const
1685	{
1686	return mRoot;
1687	}
1688
1689
1690	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1691	{
1692	// the node became a leaf -> evaluate stats for leafs
1693	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
1694
1695
1696	if (data.mPvs > mVspStats.maxPvs)
1697	{
1698	mVspStats.maxPvs = data.mPvs;
1699	}
1700
1701	mVspStats.pvs += data.mPvs;
1702
1703	if (data.mDepth < mVspStats.minDepth)
1704	{
1705	mVspStats.minDepth = data.mDepth;
1706	}
1707
1708	if (data.mDepth >= mTermMaxDepth)
1709	{
1710	++ mVspStats.maxDepthNodes;
1711	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1712	}
1713
1714	// accumulate rays to compute rays / leaf
1715	mVspStats.accumRays += (int)data.mRays->size();
1716
1717	if (data.mPvs < mTermMinPvs)
1718	++ mVspStats.minPvsNodes;
1719
1720	if ((int)data.mRays->size() < mTermMinRays)
1721	++ mVspStats.minRaysNodes;
1722
1723	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1724	++ mVspStats.maxRayContribNodes;
1725
1726	if (data.mProbability <= mTermMinProbability)
1727	++ mVspStats.minProbabilityNodes;
1728
1729	// accumulate depth to compute average depth
1730	mVspStats.accumDepth += data.mDepth;
1731
1732	++ mCreatedViewCells;
1733
1734	#ifdef _DEBUG
1735	Debug << "BSP stats: "
1736	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1737	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1738	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1739	<< "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
1740	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1741	#endif
1742	}
1743
1744
1745	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1746	{
1747	ViewCell::NewMail();
1748	CollectViewCells(mRoot, onlyValid, viewCells, true);
1749	}
1750
1751
1752	void VspTree::CollapseViewCells()
1753	{
1754	// TODO matt
1755	#if HAS_TO_BE_REDONE
1756	stack<VspNode *> nodeStack;
1757
1758	if (!mRoot)
1759	return;
1760
1761	nodeStack.push(mRoot);
1762
1763	while (!nodeStack.empty())
1764	{
1765	VspNode *node = nodeStack.top();
1766	nodeStack.pop();
1767
1768	if (node->IsLeaf())
1769	{
1770	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1771
1772	if (!viewCell->GetValid())
1773	{
1774	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1775
1776	ViewCellContainer leaves;
1777	mViewCellsTree->CollectLeaves(viewCell, leaves);
1778
1779	ViewCellContainer::const_iterator it, it_end = leaves.end();
1780
1781	for (it = leaves.begin(); it != it_end; ++ it)
1782	{
1783	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
1784	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1785	++ mVspStats.invalidLeaves;
1786	}
1787
1788	// add to unbounded view cell
1789	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1790	DEL_PTR(viewCell);
1791	}
1792	}
1793	else
1794	{
1795	VspInterior interior = dynamic_cast<VspInterior >(node);
1796
1797	nodeStack.push(interior->GetFront());
1798	nodeStack.push(interior->GetBack());
1799	}
1800	}
1801
1802	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1803	#endif
1804	}
1805
1806
1807	void VspTree::CollectRays(VssRayContainer &rays)
1808	{
1809	vector<VspLeaf *> leaves;
1810	CollectLeaves(leaves);
1811
1812	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1813
1814	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1815	{
1816	VspLeaf leaf = lit;
1817	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1818
1819	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1820	rays.push_back(*rit);
1821	}
1822	}
1823
1824
1825	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1826	{
1827	mViewCellsManager = vcm;
1828	}
1829
1830
1831	void VspTree::ValidateTree()
1832	{
1833	mVspStats.invalidLeaves = 0;
1834
1835	stack<VspNode *> nodeStack;
1836
1837	if (!mRoot)
1838	return;
1839
1840	nodeStack.push(mRoot);
1841
1842	while (!nodeStack.empty())
1843	{
1844	VspNode *node = nodeStack.top();
1845	nodeStack.pop();
1846
1847	if (node->IsLeaf())
1848	{
1849	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1850
1851	if (!leaf->GetViewCell()->GetValid())
1852	++ mVspStats.invalidLeaves;
1853
1854	// validity flags don't match => repair
1855	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1856	{
1857	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1858	PropagateUpValidity(leaf);
1859	}
1860	}
1861	else
1862	{
1863	VspInterior interior = dynamic_cast<VspInterior >(node);
1864
1865	nodeStack.push(interior->GetFront());
1866	nodeStack.push(interior->GetBack());
1867	}
1868	}
1869
1870	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1871	}
1872
1873
1874
1875	void VspTree::CollectViewCells(VspNode *root,
1876	bool onlyValid,
1877	ViewCellContainer &viewCells,
1878	bool onlyUnmailed) const
1879	{
1880	stack<VspNode *> nodeStack;
1881
1882	if (!root)
1883	return;
1884
1885	nodeStack.push(root);
1886
1887	while (!nodeStack.empty())
1888	{
1889	VspNode *node = nodeStack.top();
1890	nodeStack.pop();
1891
1892	if (node->IsLeaf())
1893	{
1894	if (!onlyValid \|\| node->TreeValid())
1895	{
1896	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
1897
1898	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
1899
1900	if (!onlyUnmailed \|\| !viewCell->Mailed())
1901	{
1902	viewCell->Mail();
1903	viewCells.push_back(viewCell);
1904	}
1905	}
1906	}
1907	else
1908	{
1909	VspInterior interior = dynamic_cast<VspInterior >(node);
1910
1911	nodeStack.push(interior->GetFront());
1912	nodeStack.push(interior->GetBack());
1913	}
1914	}
1915	}
1916
1917
1918	int VspTree::FindNeighbors(VspLeaf *n,
1919	vector<VspLeaf *> &neighbors,
1920	const bool onlyUnmailed) const
1921	{
1922	stack<VspNode *> nodeStack;
1923	nodeStack.push(mRoot);
1924
1925	const AxisAlignedBox3 box = GetBoundingBox(n);
1926
1927	while (!nodeStack.empty())
1928	{
1929	VspNode *node = nodeStack.top();
1930	nodeStack.pop();
1931
1932	if (node->IsLeaf())
1933	{
1934	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1935
1936	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
1937	neighbors.push_back(leaf);
1938	}
1939	else
1940	{
1941	VspInterior interior = dynamic_cast<VspInterior >(node);
1942
1943	if (interior->GetPosition() > box.Max(interior->GetAxis()))
1944	nodeStack.push(interior->GetBack());
1945	else
1946	{
1947	if (interior->GetPosition() < box.Min(interior->GetAxis()))
1948	nodeStack.push(interior->GetFront());
1949	else
1950	{
1951	// random decision
1952	nodeStack.push(interior->GetBack());
1953	nodeStack.push(interior->GetFront());
1954	}
1955	}
1956	}
1957	}
1958
1959	return (int)neighbors.size();
1960	}
1961
1962
1963	// Find random neighbor which was not mailed
1964	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
1965	{
1966	stack<VspNode *> nodeStack;
1967	nodeStack.push(mRoot);
1968
1969	int mask = rand();
1970
1971	while (!nodeStack.empty())
1972	{
1973	VspNode *node = nodeStack.top();
1974
1975	nodeStack.pop();
1976
1977	if (node->IsLeaf())
1978	{
1979	return dynamic_cast<VspLeaf *>(node);
1980	}
1981	else
1982	{
1983	VspInterior interior = dynamic_cast<VspInterior >(node);
1984	VspNode *next;
1985
1986	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
1987	{
1988	next = interior->GetFront();
1989	}
1990	else
1991	{
1992	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
1993	{
1994	next = interior->GetBack();
1995	}
1996	else
1997	{
1998	// random decision
1999	if (mask & 1)
2000	next = interior->GetBack();
2001	else
2002	next = interior->GetFront();
2003	mask = mask >> 1;
2004	}
2005	}
2006
2007	nodeStack.push(next);
2008	}
2009	}
2010
2011	return NULL;
2012	}
2013
2014
2015	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2016	{
2017	stack<VspNode *> nodeStack;
2018
2019	nodeStack.push(mRoot);
2020
2021	int mask = rand();
2022
2023	while (!nodeStack.empty())
2024	{
2025	VspNode *node = nodeStack.top();
2026	nodeStack.pop();
2027
2028	if (node->IsLeaf())
2029	{
2030	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2031	return dynamic_cast<VspLeaf *>(node);
2032	}
2033	else
2034	{
2035	VspInterior interior = dynamic_cast<VspInterior >(node);
2036
2037	// random decision
2038	if (mask & 1)
2039	nodeStack.push(interior->GetBack());
2040	else
2041	nodeStack.push(interior->GetFront());
2042
2043	mask = mask >> 1;
2044	}
2045	}
2046
2047	return NULL;
2048	}
2049
2050
2051	int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
2052	{
2053	int pvsSize = 0;
2054
2055	Intersectable::NewMail();
2056	KdNode::NewMail();
2057	BvhLeaf::NewMail();
2058
2059	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2060
2061	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2062	{
2063	VssRay ray = (rit).mRay;
2064
2065	pvsSize += EvalContributionToPvs(*ray, true);
2066	pvsSize += EvalContributionToPvs(*ray, false);
2067	}
2068
2069	return pvsSize;
2070	}
2071
2072
2073	float VspTree::GetEpsilon() const
2074	{
2075	return mEpsilon;
2076	}
2077
2078
2079	int VspTree::CastLineSegment(const Vector3 &origin,
2080	const Vector3 &termination,
2081	ViewCellContainer &viewcells,
2082	const bool useMailboxing)
2083	{
2084	int hits = 0;
2085
2086	float mint = 0.0f, maxt = 1.0f;
2087	const Vector3 dir = termination - origin;
2088
2089	stack<LineTraversalData> tStack;
2090
2091	Vector3 entp = origin;
2092	Vector3 extp = termination;
2093
2094	VspNode *node = mRoot;
2095	VspNode *farChild;
2096
2097	float position;
2098	int axis;
2099
2100	while (1)
2101	{
2102	if (!node->IsLeaf())
2103	{
2104	VspInterior in = dynamic_cast<VspInterior >(node);
2105	position = in->GetPosition();
2106	axis = in->GetAxis();
2107
2108	if (entp[axis] <= position)
2109	{
2110	if (extp[axis] <= position)
2111	{
2112	node = in->GetBack();
2113	// cases N1,N2,N3,P5,Z2,Z3
2114	continue;
2115	} else
2116	{
2117	// case N4
2118	node = in->GetBack();
2119	farChild = in->GetFront();
2120	}
2121	}
2122	else
2123	{
2124	if (position <= extp[axis])
2125	{
2126	node = in->GetFront();
2127	// cases P1,P2,P3,N5,Z1
2128	continue;
2129	}
2130	else
2131	{
2132	node = in->GetFront();
2133	farChild = in->GetBack();
2134	// case P4
2135	}
2136	}
2137
2138	// $$ modification 3.5.2004 - hints from Kamil Ghais
2139	// case N4 or P4
2140	const float tdist = (position - origin[axis]) / dir[axis];
2141	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2142
2143	extp = origin + dir * tdist;
2144	maxt = tdist;
2145	}
2146	else
2147	{
2148	// compute intersection with all objects in this leaf
2149	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2150	ViewCell *vc = leaf->GetViewCell();
2151
2152	// don't have to mail if each view cell belongs to exactly one leaf
2153	if (!useMailboxing \|\| !vc->Mailed())
2154	{
2155	if (useMailboxing)
2156	vc->Mail();
2157
2158	viewcells.push_back(vc);
2159	++ hits;
2160	}
2161	#if 0
2162	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2163	#endif
2164	// get the next node from the stack
2165	if (tStack.empty())
2166	break;
2167
2168	entp = extp;
2169	mint = maxt;
2170
2171	LineTraversalData &s = tStack.top();
2172	node = s.mNode;
2173	extp = s.mExitPoint;
2174	maxt = s.mMaxT;
2175	tStack.pop();
2176	}
2177	}
2178
2179	return hits;
2180	}
2181
2182
2183	int VspTree::CastRay(Ray &ray)
2184	{
2185	int hits = 0;
2186
2187	stack<LineTraversalData> tStack;
2188	const Vector3 dir = ray.GetDir();
2189
2190	float maxt, mint;
2191
2192	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2193	return 0;
2194
2195	Intersectable::NewMail();
2196	ViewCell::NewMail();
2197
2198	Vector3 entp = ray.Extrap(mint);
2199	Vector3 extp = ray.Extrap(maxt);
2200
2201	const Vector3 origin = entp;
2202
2203	VspNode *node = mRoot;
2204	VspNode *farChild = NULL;
2205
2206	float position;
2207	int axis;
2208
2209	while (1)
2210	{
2211	if (!node->IsLeaf())
2212	{
2213	VspInterior in = dynamic_cast<VspInterior >(node);
2214	position = in->GetPosition();
2215	axis = in->GetAxis();
2216
2217	if (entp[axis] <= position)
2218	{
2219	if (extp[axis] <= position)
2220	{
2221	node = in->GetBack();
2222	// cases N1,N2,N3,P5,Z2,Z3
2223	continue;
2224	}
2225	else
2226	{
2227	// case N4
2228	node = in->GetBack();
2229	farChild = in->GetFront();
2230	}
2231	}
2232	else
2233	{
2234	if (position <= extp[axis])
2235	{
2236	node = in->GetFront();
2237	// cases P1,P2,P3,N5,Z1
2238	continue;
2239	}
2240	else
2241	{
2242	node = in->GetFront();
2243	farChild = in->GetBack();
2244	// case P4
2245	}
2246	}
2247
2248	// $$ modification 3.5.2004 - hints from Kamil Ghais
2249	// case N4 or P4
2250	const float tdist = (position - origin[axis]) / dir[axis];
2251	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2252	extp = origin + dir * tdist;
2253	maxt = tdist;
2254	}
2255	else
2256	{
2257	// compute intersection with all objects in this leaf
2258	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2259	ViewCell *vc = leaf->GetViewCell();
2260
2261	if (!vc->Mailed())
2262	{
2263	vc->Mail();
2264	// todo: add view cells to ray
2265	++ hits;
2266	}
2267	#if 0
2268	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2269	#endif
2270	// get the next node from the stack
2271	if (tStack.empty())
2272	break;
2273
2274	entp = extp;
2275	mint = maxt;
2276
2277	LineTraversalData &s = tStack.top();
2278	node = s.mNode;
2279	extp = s.mExitPoint;
2280	maxt = s.mMaxT;
2281	tStack.pop();
2282	}
2283	}
2284
2285	return hits;
2286	}
2287
2288
2289	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2290	{
2291	if (mRoot == NULL)
2292	return NULL;
2293
2294	stack<VspNode *> nodeStack;
2295	nodeStack.push(mRoot);
2296
2297	ViewCellLeaf *viewcell = NULL;
2298
2299	while (!nodeStack.empty())
2300	{
2301	VspNode *node = nodeStack.top();
2302	nodeStack.pop();
2303
2304	if (node->IsLeaf())
2305	{
2306	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2307	break;
2308	}
2309	else
2310	{
2311	VspInterior interior = dynamic_cast<VspInterior >(node);
2312
2313	// random decision
2314	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2315	nodeStack.push(interior->GetBack());
2316	else
2317	nodeStack.push(interior->GetFront());
2318	}
2319	}
2320
2321	if (active)
2322	return mViewCellsTree->GetActiveViewCell(viewcell);
2323	else
2324	return viewcell;
2325	}
2326
2327
2328	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2329	{
2330	VspNode *node = mRoot;
2331
2332	while (1)
2333	{
2334	// early exit
2335	if (node->TreeValid())
2336	return true;
2337
2338	if (node->IsLeaf())
2339	return false;
2340
2341	VspInterior in = dynamic_cast<VspInterior >(node);
2342
2343	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2344	{
2345	node = in->GetBack();
2346	}
2347	else
2348	{
2349	node = in->GetFront();
2350	}
2351	}
2352
2353	// should never come here
2354	return false;
2355	}
2356
2357
2358	void VspTree::PropagateUpValidity(VspNode *node)
2359	{
2360	const bool isValid = node->TreeValid();
2361
2362	// propagative up invalid flag until only invalid nodes exist over this node
2363	if (!isValid)
2364	{
2365	while (!node->IsRoot() && node->GetParent()->TreeValid())
2366	{
2367	node = node->GetParent();
2368	node->SetTreeValid(false);
2369	}
2370	}
2371	else
2372	{
2373	// propagative up valid flag until one of the subtrees is invalid
2374	while (!node->IsRoot() && !node->TreeValid())
2375	{
2376	node = node->GetParent();
2377	VspInterior interior = dynamic_cast<VspInterior >(node);
2378
2379	// the parent is valid iff both leaves are valid
2380	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2381	interior->GetFront()->TreeValid());
2382	}
2383	}
2384	}
2385
2386
2387	bool VspTree::Export(OUT_STREAM &stream)
2388	{
2389	ExportNode(mRoot, stream);
2390
2391	return true;
2392	}
2393
2394
2395	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2396	{
2397	if (node->IsLeaf())
2398	{
2399	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2400	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2401
2402	int id = -1;
2403	if (viewCell != mOutOfBoundsCell)
2404	id = viewCell->GetId();
2405
2406	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2407	}
2408	else
2409	{
2410	VspInterior interior = dynamic_cast<VspInterior >(node);
2411
2412	AxisAlignedPlane plane = interior->GetPlane();
2413	stream << "<Interior plane=\"" << plane.mPosition << " "
2414	<< plane.mAxis << "\">" << endl;
2415
2416	ExportNode(interior->GetBack(), stream);
2417	ExportNode(interior->GetFront(), stream);
2418
2419	stream << "</Interior>" << endl;
2420	}
2421	}
2422
2423
2424	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2425	RayInfoContainer &rays,
2426	RayInfoContainer &frontRays,
2427	RayInfoContainer &backRays) const
2428	{
2429	int splits = 0;
2430
2431	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2432
2433	for (rit = rays.begin(); rit != rit_end; ++ rit)
2434	{
2435	RayInfo bRay = *rit;
2436
2437	VssRay *ray = bRay.mRay;
2438	float t;
2439
2440	// get classification and receive new t
2441	// test if start point behind or in front of plane
2442	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2443
2444	if (side == 0)
2445	{
2446	++ splits;
2447
2448	if (ray->HasPosDir(plane.mAxis))
2449	{
2450	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2451	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2452	}
2453	else
2454	{
2455	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2456	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2457	}
2458	}
2459	else if (side == 1)
2460	{
2461	frontRays.push_back(bRay);
2462	}
2463	else
2464	{
2465	backRays.push_back(bRay);
2466	}
2467	}
2468
2469	return splits;
2470	}
2471
2472
2473	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2474	{
2475	if (!node->GetParent())
2476	return mBoundingBox;
2477
2478	if (!node->IsLeaf())
2479	{
2480	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
2481	}
2482
2483	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
2484
2485	AxisAlignedBox3 box(parent->GetBoundingBox());
2486
2487	if (parent->GetFront() == node)
2488	box.SetMin(parent->GetAxis(), parent->GetPosition());
2489	else
2490	box.SetMax(parent->GetAxis(), parent->GetPosition());
2491
2492	return box;
2493	}
2494
2495
2496	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2497	ViewCellContainer &viewCells) const
2498	{
2499	stack<VspNode *> nodeStack;
2500
2501	ViewCell::NewMail();
2502
2503	while (!nodeStack.empty())
2504	{
2505	VspNode *node = nodeStack.top();
2506	nodeStack.pop();
2507
2508	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2509
2510	if (bbox.Includes(box))
2511	{
2512	// node geometry is contained in box
2513	CollectViewCells(node, true, viewCells, true);
2514	}
2515	else if (Overlap(bbox, box))
2516	{
2517	if (node->IsLeaf())
2518	{
2519	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2520
2521	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2522	{
2523	leaf->GetViewCell()->Mail();
2524	viewCells.push_back(leaf->GetViewCell());
2525	}
2526	}
2527	else
2528	{
2529	VspInterior interior = dynamic_cast<VspInterior >(node);
2530
2531	VspNode *first = interior->GetFront();
2532	VspNode *second = interior->GetBack();
2533
2534	nodeStack.push(first);
2535	nodeStack.push(second);
2536	}
2537	}
2538	// default: cull
2539	}
2540
2541	return (int)viewCells.size();
2542	}
2543
2544
2545	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2546	RayInfoContainer &rays)
2547	{
2548	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2549
2550	long startTime = GetTime();
2551
2552	cout << "storing rays ... ";
2553
2554	Intersectable::NewMail();
2555
2556	//-- store rays and objects
2557	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2558	{
2559	VssRay ray = rit;
2560	float minT, maxT;
2561	static Ray hray;
2562
2563	hray.Init(*ray);
2564
2565	// TODO: not very efficient to implictly cast between rays types
2566	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2567	{
2568	float len = ray->Length();
2569
2570	if (!len)
2571	len = Limits::Small;
2572
2573	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2574	}
2575	}
2576
2577	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2578	}
2579
2580
2581	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2582	{
2583	static Ray hray;
2584	hray.Init(ray);
2585
2586	float tmin = 0, tmax = 1.0;
2587
2588	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2589	return;
2590
2591	const Vector3 origin = hray.Extrap(tmin);
2592	const Vector3 termination = hray.Extrap(tmax);
2593
2594	// view cells were not precomputed
2595	// don't mail because we need mailboxing for something else
2596	CastLineSegment(origin, termination, viewCells, false);
2597	}
2598
2599
2600	SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
2601	AxisAlignedBox3 *forcedViewSpace,
2602	RayInfoContainer &rays)
2603	{
2604	// store pointer to this tree
2605	VspSubdivisionCandidate::sVspTree = this;
2606	mVspStats.nodes = 1;
2607
2608	// compute view space bounding box
2609	ComputeBoundingBox(sampleRays, forcedViewSpace);
2610
2611	// initialise termination criteria
2612	mTermMinProbability *= mBoundingBox.GetVolume();
2613	mGlobalCostMisses = 0;
2614
2615	// get clipped rays
2616	PreprocessRays(sampleRays, rays);
2617
2618	const int pvsSize = EvalPvsSize(rays);
2619
2620	Debug << "pvs size: " << (int)pvsSize << endl;
2621	Debug << "rays size: " << (int)rays.size() << endl;
2622
2623	//-- prepare view space partition
2624	const float prop = mBoundingBox.GetVolume();
2625
2626	// we assume that leaf was already created
2627	VspLeaf *leaf = new VspLeaf();
2628	mRoot = leaf;
2629
2630	// first vsp traversal data
2631	VspTraversalData vData(leaf, 0, &rays, pvsSize, prop, mBoundingBox);
2632
2633	// create first view cell
2634	CreateViewCell(vData, false);
2635
2636	#if WORK_WITH_VIEWCELL_PVS
2637	// add first view cell to all the objects view cell pvs
2638	ObjectPvsMap::const_iterator oit,
2639	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2640
2641	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2642	{
2643	Intersectable obj = (oit).first;
2644	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2645	}
2646	#endif
2647
2648	//-- compute first split candidate
2649	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2650	EvalSubdivisionCandidate(*splitCandidate);
2651	leaf->SetSubdivisionCandidate(splitCandidate);
2652
2653	mTotalCost = (float)pvsSize;
2654	EvalSubdivisionStats(*splitCandidate);
2655
2656	return splitCandidate;
2657	}
2658
2659
2660	void VspTree::CollectDirtyCandidate(const VssRay &ray,
2661	const bool isTermination,
2662	vector<SubdivisionCandidate *> &dirtyList) const
2663	{
2664
2665	Intersectable *obj;
2666	Vector3 pt;
2667	KdNode *node;
2668
2669	ray.GetSampleData(isTermination, pt, &obj, &node);
2670
2671	if (!obj) return;
2672
2673	switch (mHierarchyManager->GetObjectSpaceSubdivisonType())
2674	{
2675	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2676	{
2677	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2678
2679	if (!leaf->Mailed())
2680	{
2681	leaf->Mail();
2682	dirtyList.push_back(leaf->mSubdivisionCandidate);
2683	}
2684	break;
2685	}
2686	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2687	{
2688	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2689
2690	if (!leaf->Mailed())
2691	{
2692	leaf->Mail();
2693	dirtyList.push_back(leaf->GetSubdivisionCandidate());Debug << "here87700" << endl;
2694	Debug << "here166 candidate: " << leaf->GetSubdivisionCandidate() << endl;
2695	Debug << "here120 candidate: " << leaf->GetSubdivisionCandidate() << " type: " << leaf->GetSubdivisionCandidate()->Type() << endl;
2696	Debug << "here877" << endl;
2697	}
2698	break;
2699	}
2700	break;
2701	default:
2702	break;
2703	}
2704	}
2705
2706
2707	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
2708	vector<SubdivisionCandidate *> &dirtyList)
2709	{
2710	VspTraversalData &tData = sc->mParentData;
2711	VspLeaf *node = tData.mNode;
2712
2713	KdLeaf::NewMail();
2714	BvhLeaf::NewMail();
2715
2716	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2717
2718	// add all kd nodes seen by the rays
2719	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2720	{
2721	VssRay ray = (rit).mRay;
2722
2723	CollectDirtyCandidate(*ray, true, dirtyList);
2724	CollectDirtyCandidate(*ray, false, dirtyList);
2725	}
2726	}
2727
2728
2729	int VspTree::EvalMaxEventContribution(const VssRay &ray,
2730	const bool isTermination) const
2731	{
2732	Intersectable *obj;
2733	Vector3 pt;
2734	KdNode *node;
2735
2736	ray.GetSampleData(isTermination, pt, &obj, &node);
2737
2738	if (!obj)
2739	return 0;
2740
2741	int pvs = 0;
2742
2743	switch (mHierarchyManager->GetObjectSpaceSubdivisonType())
2744	{
2745	case HierarchyManager::NO_OBJ_SUBDIV:
2746	{
2747	if (-- obj->mCounter == 0)
2748	++ pvs;
2749	break;
2750	}
2751	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2752	{
2753	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2754
2755	// add contributions of the kd nodes
2756	pvs += EvalMaxEventContribution(leaf);
2757	break;
2758	}
2759	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2760	{
2761	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2762
2763	if (-- leaf->mCounter == 0)
2764	pvs += (int)leaf->mObjects.size();
2765	break;
2766	}
2767	default:
2768	break;
2769	}
2770
2771	return pvs;
2772	}
2773
2774
2775	int VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
2776	{
2777	int pvsSize = 0;
2778
2779	Intersectable *obj;
2780	Vector3 pt;
2781	KdNode *node;
2782
2783	ray.GetSampleData(isTermination, pt, &obj, &node);
2784
2785	if (!obj)
2786	return 0;
2787
2788	switch (mHierarchyManager->GetObjectSpaceSubdivisonType())
2789	{
2790	case HierarchyManager::NO_OBJ_SUBDIV:
2791	{
2792	if (!obj->Mailed())
2793	{
2794	obj->Mail();
2795	obj->mCounter = 0;
2796
2797	++ pvsSize;
2798	}
2799
2800	++ obj->mCounter;
2801	break;
2802	}
2803	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2804	{
2805	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2806	pvsSize += PrepareHeuristics(leaf);
2807	break;
2808	}
2809	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2810	{
2811	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2812
2813	if (!leaf->Mailed())
2814	{
2815	leaf->Mail();
2816	leaf->mCounter = 0;
2817
2818	pvsSize += (int)leaf->mObjects.size();
2819	}
2820
2821	++ leaf->mCounter;
2822	break;
2823	}
2824	default:
2825	break;
2826	}
2827
2828	return pvsSize;
2829	}
2830
2831
2832	int VspTree::EvalMinEventContribution(const VssRay &ray,
2833	const bool isTermination) const
2834	{
2835	Intersectable *obj;
2836	Vector3 pt;
2837	KdNode *node;
2838
2839	ray.GetSampleData(isTermination, pt, &obj, &node);
2840
2841	if (!obj) return 0;
2842
2843	int pvs = 0;
2844
2845	switch (mHierarchyManager->GetObjectSpaceSubdivisonType())
2846	{
2847	case HierarchyManager::NO_OBJ_SUBDIV:
2848	{
2849	if (!obj->Mailed())
2850	{
2851	obj->Mail();
2852	++ pvs;
2853	}
2854	break;
2855	}
2856	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2857	{
2858	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2859	// add contributions of the kd nodes
2860	pvs += EvalMinEventContribution(leaf);
2861	break;
2862	}
2863	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2864	{
2865	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2866
2867	if (!leaf->Mailed())
2868	{
2869	leaf->Mail();
2870	pvs += (int)leaf->mObjects.size();
2871	}
2872	break;
2873	}
2874	default:
2875	break;
2876	}
2877
2878	return pvs;
2879	}
2880
2881
2882	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
2883	const bool isTermination,
2884	const int cf,
2885	float &frontPvs,
2886	float &backPvs,
2887	float &totalPvs) const
2888	{
2889	Intersectable *obj;
2890	Vector3 pt;
2891	KdNode *node;
2892
2893	ray.GetSampleData(isTermination, pt, &obj, &node);
2894
2895	if (!obj) return;
2896
2897	switch (mHierarchyManager->GetObjectSpaceSubdivisonType())
2898	{
2899	case HierarchyManager::NO_OBJ_SUBDIV:
2900	{
2901	// find front and back pvs for origing and termination object
2902	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
2903	break;
2904	}
2905	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2906	{
2907	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2908	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2909	break;
2910	}
2911	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2912	{
2913	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2914	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2915	break;
2916	}
2917	}
2918	}
2919
2920
2921	int VspTree::EvalContributionToPvs(const VssRay &ray,
2922	const bool isTermination) const
2923	{
2924	Intersectable *obj;
2925	Vector3 pt;
2926	KdNode *node;
2927
2928	ray.GetSampleData(isTermination, pt, &obj, &node);
2929
2930	if (!obj)
2931	return 0;
2932
2933	int pvs = 0;
2934
2935	switch(mHierarchyManager->GetObjectSpaceSubdivisonType())
2936	{
2937	case HierarchyManager::NO_OBJ_SUBDIV:
2938	{
2939	if (!obj->Mailed())
2940	{
2941	obj->Mail();
2942	++ pvs;
2943	}
2944	break;
2945	}
2946	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2947	{
2948	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2949
2950	pvs += EvalContributionToPvs(leaf);
2951	break;
2952	}
2953	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2954	{
2955	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2956
2957	if (!bvhleaf->Mailed())
2958	{
2959	bvhleaf->Mail();
2960	pvs += (int)bvhleaf->mObjects.size();
2961	}
2962	break;
2963	}
2964	default:
2965	break;
2966	}
2967
2968	return pvs;
2969	}
2970
2971
2972	int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
2973	{
2974	if (leaf->Mailed()) // leaf already mailed
2975	return 0;
2976
2977	leaf->Mail();
2978
2979	int pvs = 0;
2980	pvs += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
2981
2982	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
2983
2984	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
2985	{
2986	Intersectable obj = oit;
2987
2988	if (!obj->Mailed())
2989	{
2990	obj->Mail();
2991	++ pvs;
2992	}
2993	}
2994
2995	return pvs;
2996	}
2997
2998	}

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

Download in other formats: