Context Navigation

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

Revision 1379, 71.3 KB checked in by mattausch, 18 years ago (diff)
fixed sah for objeect partition loader for single triangles also for x3d

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

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

Download in other formats: