Context Navigation

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

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

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

Download in other formats: