Context Navigation

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

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

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

Download in other formats: