Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp @ 1181

Revision 1181, 121.7 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 "VspOspTree.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
21
22	namespace GtpVisibilityPreprocessor {
23
24	#define USE_FIXEDPOINT_T 0
25
26
27	//-- static members
28
29	VspTree *VspTree::VspSplitCandidate::sVspTree = NULL;
30	OspTree *OspTree::OspSplitCandidate::sOspTree = NULL;
31
32	// variable for debugging volume contribution for heuristics
33	static float debugVol;
34
35	// pvs penalty can be different from pvs size
36	inline static float EvalPvsPenalty(const int pvs,
37	const int lower,
38	const int upper)
39	{
40	// clamp to minmax values
41	if (pvs < lower)
42	return (float)lower;
43	else if (pvs > upper)
44	return (float)upper;
45
46	return (float)pvs;
47	}
48
49
50	int VspNode::sMailId = 1;
51
52
53	void VspTreeStatistics::Print(ostream &app) const
54	{
55	app << "=========== VspTree statistics ===============\n";
56
57	app << setprecision(4);
58
59	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
60
61	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
62
63	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
64
65	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
66
67	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
68
69	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
70
71	for (int i = 0; i < 3; ++ i)
72	app << splits[i] << " ";
73	app << endl;
74
75	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
76	<< maxDepthNodes * 100 / (double)Leaves() << endl;
77
78	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
79	<< minPvsNodes * 100 / (double)Leaves() << endl;
80
81	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
82	<< minRaysNodes * 100 / (double)Leaves() << endl;
83
84	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
85	<< maxCostNodes * 100 / (double)Leaves() << endl;
86
87	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
88	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
89
90	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
91	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
92
93	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
94
95	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
96
97	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
98
99	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
100
101	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
102	//app << "#N_PVS: " << pvs << endl;
103
104	app << "========== END OF VspTree statistics ==========\n";
105	}
106
107
108	void OspTreeStatistics::Print(ostream &app) const
109	{
110	app << "=========== OspTree statistics ===============\n";
111
112	app << setprecision(4);
113
114	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
115
116	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
117
118	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
119
120	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
121
122	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
123
124	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
125
126	for (int i = 0; i < 3; ++ i)
127	app << splits[i] << " ";
128	app << endl;
129
130	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
131	<< maxDepthNodes * 100 / (double)Leaves() << endl;
132
133	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
134	<< minPvsNodes * 100 / (double)Leaves() << endl;
135
136	//app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
137	// << minRaysNodes * 100 / (double)Leaves() << endl;
138
139	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
140	<< maxCostNodes * 100 / (double)Leaves() << endl;
141
142	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
143	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
144
145	// app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
146	// << maxRayContribNodes * 100 / (double)Leaves() << endl;
147
148	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
149
150	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
151
152	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
153
154	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
155
156	// app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
157	//app << "#N_PVS: " << pvs << endl;
158
159	app << "========== END OF VspTree statistics ==========\n";
160	}
161
162
163	/******************************************************************/
164	/* class VspNode implementation */
165	/******************************************************************/
166
167
168	VspNode::VspNode():
169	mParent(NULL), mTreeValid(true), mTimeStamp(0)
170	{}
171
172
173	VspNode::VspNode(VspInterior *parent):
174	mParent(parent), mTreeValid(true)
175	{}
176
177
178	bool VspNode::IsRoot() const
179	{
180	return mParent == NULL;
181	}
182
183
184	VspInterior *VspNode::GetParent()
185	{
186	return mParent;
187	}
188
189
190	void VspNode::SetParent(VspInterior *parent)
191	{
192	mParent = parent;
193	}
194
195
196	bool VspNode::IsSibling(VspNode *n) const
197	{
198	return ((this != n) && mParent &&
199	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
200	}
201
202
203	int VspNode::GetDepth() const
204	{
205	int depth = 0;
206	VspNode *p = mParent;
207
208	while (p)
209	{
210	p = p->mParent;
211	++ depth;
212	}
213
214	return depth;
215	}
216
217
218	bool VspNode::TreeValid() const
219	{
220	return mTreeValid;
221	}
222
223
224	void VspNode::SetTreeValid(const bool v)
225	{
226	mTreeValid = v;
227	}
228
229
230	/****************************************************************/
231	/* class VspInterior implementation */
232	/****************************************************************/
233
234
235	VspInterior::VspInterior(const AxisAlignedPlane &plane):
236	mPlane(plane), mFront(NULL), mBack(NULL)
237	{}
238
239
240	VspInterior::~VspInterior()
241	{
242	DEL_PTR(mFront);
243	DEL_PTR(mBack);
244	}
245
246
247	bool VspInterior::IsLeaf() const
248	{
249	return false;
250	}
251
252
253	VspNode *VspInterior::GetBack()
254	{
255	return mBack;
256	}
257
258
259	VspNode *VspInterior::GetFront()
260	{
261	return mFront;
262	}
263
264
265	AxisAlignedPlane VspInterior::GetPlane() const
266	{
267	return mPlane;
268	}
269
270
271	float VspInterior::GetPosition() const
272	{
273	return mPlane.mPosition;
274	}
275
276
277	int VspInterior::GetAxis() const
278	{
279	return mPlane.mAxis;
280	}
281
282
283	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
284	{
285	if (mBack == oldChild)
286	mBack = newChild;
287	else
288	mFront = newChild;
289	}
290
291
292	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
293	{
294	mBack = back;
295	mFront = front;
296	}
297
298
299	AxisAlignedBox3 VspInterior::GetBoundingBox() const
300	{
301	return mBoundingBox;
302	}
303
304
305	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
306	{
307	mBoundingBox = box;
308	}
309
310
311	int VspInterior::Type() const
312	{
313	return Interior;
314	}
315
316
317
318	/****************************************************************/
319	/* class VspLeaf implementation */
320	/****************************************************************/
321
322
323	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
324	{
325	}
326
327
328	VspLeaf::~VspLeaf()
329	{
330	DEL_PTR(mPvs);
331	CLEAR_CONTAINER(mVssRays);
332	}
333
334
335	int VspLeaf::Type() const
336	{
337	return Leaf;
338	}
339
340
341	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
342	mViewCell(viewCell)
343	{
344	}
345
346
347	VspLeaf::VspLeaf(VspInterior *parent):
348	VspNode(parent), mViewCell(NULL), mPvs(NULL)
349	{}
350
351
352
353	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
354	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
355	{
356	}
357
358	ViewCellLeaf *VspLeaf::GetViewCell() const
359	{
360	return mViewCell;
361	}
362
363	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
364	{
365	mViewCell = viewCell;
366	}
367
368
369	bool VspLeaf::IsLeaf() const
370	{
371	return true;
372	}
373
374
375	/*************************************************************************/
376	/* class VspTree implementation */
377	/*************************************************************************/
378
379
380	VspTree::VspTree():
381	mRoot(NULL),
382	mOutOfBoundsCell(NULL),
383	mStoreRays(false),
384	mTimeStamp(1),
385	mOspTree(NULL)
386	{
387	bool randomize = false;
388	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
389	if (randomize)
390	Randomize(); // initialise random generator for heuristics
391
392	//-- termination criteria for autopartition
393	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
394	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
395	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
396	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
397	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
398
399	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
400	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
401
402	//-- max cost ratio for early tree termination
403	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
404
405	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
406	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
407
408	//-- factors for bsp tree split plane heuristics
409	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
410
411	//-- partition criteria
412	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
413	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
414
415	// if only the driving axis is used for axis aligned split
416	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
417
418	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
419	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
420
421	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
422	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
423
424	Environment::GetSingleton()->GetBoolValue("VspTree.useKdPvsForHeuristics", mUseKdPvsForHeuristics);
425
426	char subdivisionStatsLog[100];
427	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
428	mSubdivisionStats.open(subdivisionStatsLog);
429
430	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
431	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
432
433
434	//-- debug output
435
436	Debug << "***** VSP options ****** " << endl;
437
438	Debug << "max depth: " << mTermMaxDepth << endl;
439	Debug << "min PVS: " << mTermMinPvs << endl;
440	Debug << "min probabiliy: " << mTermMinProbability << endl;
441	Debug << "min rays: " << mTermMinRays << endl;
442	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
443	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
444	Debug << "miss tolerance: " << mTermMissTolerance << endl;
445	Debug << "max view cells: " << mMaxViewCells << endl;
446	Debug << "randomize: " << randomize << endl;
447
448	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
449	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
450	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
451	Debug << "max memory: " << mMaxMemory << endl;
452	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
453	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
454	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
455
456	Debug << "circulating axis: " << mCirculatingAxis << endl;
457	Debug << "minband: " << mMinBand << endl;
458	Debug << "maxband: " << mMaxBand << endl;
459
460	if (!mUseKdPvsForHeuristics)
461	Debug << "pvs heuristics: per object" << endl;
462	else
463	Debug << "pvs heuristics: per kd node" << endl;
464
465	mLocalSplitCandidates = new vector<SortableEntry>;
466
467	Debug << endl;
468	}
469
470
471	VspViewCell *VspTree::GetOutOfBoundsCell()
472	{
473	return mOutOfBoundsCell;
474	}
475
476
477	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
478	{
479	if (!mOutOfBoundsCell)
480	{
481	mOutOfBoundsCell = new VspViewCell();
482	mOutOfBoundsCell->SetId(-1);
483	mOutOfBoundsCell->SetValid(false);
484	}
485
486	return mOutOfBoundsCell;
487	}
488
489
490	const VspTreeStatistics &VspTree::GetStatistics() const
491	{
492	return mVspStats;
493	}
494
495
496	VspTree::~VspTree()
497	{
498	DEL_PTR(mRoot);
499	DEL_PTR(mLocalSplitCandidates);
500	}
501
502
503	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
504	AxisAlignedBox3 *forcedBoundingBox)
505	{
506	if (forcedBoundingBox)
507	{
508	mBoundingBox = *forcedBoundingBox;
509	}
510	else // compute vsp tree bounding box
511	{
512	mBoundingBox.Initialize();
513	VssRayContainer::const_iterator rit, rit_end = rays.end();
514
515	//-- compute bounding box
516	for (rit = rays.begin(); rit != rit_end; ++ rit)
517	{
518	VssRay ray = rit;
519
520	// compute bounding box of view space
521	mBoundingBox.Include(ray->GetTermination());
522	mBoundingBox.Include(ray->GetOrigin());
523	}
524	}
525	}
526
527
528	void VspTree::AddSubdivisionStats(const int viewCells,
529	const float renderCostDecr,
530	const float totalRenderCost,
531	const float avgRenderCost)
532	{
533	mSubdivisionStats
534	<< "#ViewCells\n" << viewCells << endl
535	<< "#RenderCostDecrease\n" << renderCostDecr << endl
536	<< "#TotalRenderCost\n" << totalRenderCost << endl
537	<< "#AvgRenderCost\n" << avgRenderCost << endl;
538	}
539
540
541	// TODO: return memory usage in MB
542	float VspTree::GetMemUsage() const
543	{
544	return (float)
545	(sizeof(VspTree) +
546	mVspStats.Leaves() * sizeof(VspLeaf) +
547	mCreatedViewCells * sizeof(VspViewCell) +
548	mVspStats.pvs * sizeof(ObjectPvsData) +
549	mVspStats.Interior() * sizeof(VspInterior) +
550	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
551	}
552
553
554	bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
555	{
556	const bool localTerminationCriteriaMet = (
557	((int)data.mRays->size() <= mTermMinRays) \|\|
558	(data.mPvs <= mTermMinPvs) \|\|
559	(data.mProbability <= mTermMinProbability) \|\|
560	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
561	(data.mDepth >= mTermMaxDepth)
562	);
563
564	if (0 && localTerminationCriteriaMet)
565	{
566	Debug << "******local termination *******" << endl;
567	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
568	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
569	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
570	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
571	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
572	}
573
574	return localTerminationCriteriaMet;
575
576	}
577
578
579	bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
580	{
581	const bool terminationCriteriaMet = (
582	// mOutOfMemory \|\|
583	(mVspStats.Leaves() >= mMaxViewCells) \|\|
584	(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
585	);
586
587	if (0 && terminationCriteriaMet)
588	{
589	Debug << "******* terminationCriteriaMet *******" << endl;
590	Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
591	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
592	}
593	return terminationCriteriaMet;
594	}
595
596
597	void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
598	{
599	//-- create new view cell
600	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
601
602	VspViewCell *viewCell = new VspViewCell();
603	leaf->SetViewCell(viewCell);
604
605	int conSamp = 0;
606	float sampCon = 0.0f;
607
608	if (updatePvs)
609	{
610	//-- update pvs of view cell
611	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
612
613	// update scalar pvs size value
614	ObjectPvs &pvs = viewCell->GetPvs();
615	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
616
617	mVspStats.contributingSamples += conSamp;
618	mVspStats.sampleContributions += (int)sampCon;
619	}
620
621
622	//-- store additional info
623	if (mStoreRays)
624	{
625	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
626
627	for (it = tData.mRays->begin(); it != it_end; ++ it)
628	{
629	(*it).mRay->Ref();
630	leaf->mVssRays.push_back((*it).mRay);
631	}
632	}
633
634	//
635	viewCell->mLeaf = leaf;
636
637	viewCell->SetVolume(tData.mProbability);
638	leaf->mProbability = tData.mProbability;
639	}
640
641
642	void VspTree::EvalSubdivisionStats(const SplitCandidate &sc)
643	{
644	const float costDecr = sc.GetRenderCostDecrease();
645
646	AddSubdivisionStats(mVspStats.Leaves(),
647	costDecr,
648	mTotalCost,
649	(float)mTotalPvsSize / (float)mVspStats.Leaves());
650	}
651
652
653	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
654	SplitCandidate *splitCandidate,
655	const bool globalCriteriaMet)
656	{
657	// todo remove dynamic cast
658	VspSplitCandidate sc = dynamic_cast<VspSplitCandidate >(splitCandidate);
659	VspTraversalData &tData = sc->mParentData;
660
661	VspNode *newNode = tData.mNode;
662
663
664	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
665	{
666	VspTraversalData tFrontData;
667	VspTraversalData tBackData;
668
669	//-- continue subdivision
670
671	// create new interior node and two leaf node
672	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
673	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
674
675	const int maxCostMisses = sc->mMaxCostMisses;
676
677
678	// how often was max cost ratio missed in this branch?
679	tFrontData.mMaxCostMisses = maxCostMisses;
680	tBackData.mMaxCostMisses = maxCostMisses;
681
682	mTotalCost -= sc->GetRenderCostDecrease();
683	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
684
685	// subdivision statistics
686	if (1) EvalSubdivisionStats(*sc);
687
688	//-- evaluate new split candidates for global greedy cost heuristics
689
690	VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData);
691	VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData);
692
693	EvalSplitCandidate(*frontCandidate);
694	EvalSplitCandidate(*backCandidate);
695
696	tQueue.Push(frontCandidate);
697	tQueue.Push(backCandidate);
698
699	// delete old view cell
700	delete tData.mNode->mViewCell;
701
702	// delete old leaf node
703	DEL_PTR(tData.mNode);
704	}
705
706	if (newNode->IsLeaf()) // subdivision terminated
707	{
708	// view cell is created during subdivision
709	//CreateViewCell(tData);
710
711	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
712	ViewCell *viewCell = leaf->GetViewCell();
713
714	int conSamp = 0;
715	float sampCon = 0.0f;
716
717	#if 0
718	//-- store pvs optained from rays
719
720	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
721
722	// update scalar pvs size value
723	ObjectPvs &pvs = viewCell->GetPvs();
724	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
725
726	mVspStats.contributingSamples += conSamp;
727	mVspStats.sampleContributions += (int)sampCon;
728	#endif
729	//-- store additional info
730	if (mStoreRays)
731	{
732	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
733	for (it = tData.mRays->begin(); it != it_end; ++ it)
734	{
735	(*it).mRay->Ref();
736	dynamic_cast<VspLeaf >(newNode)->mVssRays.push_back((it).mRay);
737	}
738	}
739
740	// finally evaluate statistics for this leaf
741	EvaluateLeafStats(tData);
742	}
743
744	//-- cleanup
745	tData.Clear();
746
747	return newNode;
748	}
749
750
751	void VspTree::EvalSplitCandidate(VspSplitCandidate &splitCandidate)
752	{
753	float frontProb;
754	float backProb;
755
756	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
757
758	// compute locally best split plane
759	const bool success =
760	SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
761
762	float oldRenderCost;
763
764	// compute global decrease in render cost
765	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
766	splitCandidate.mParentData,
767	oldRenderCost);
768
769	splitCandidate.SetRenderCostDecrease(renderCostDecr);
770
771	#if 0
772	const float priority = (float)-data.mDepth;
773	#else
774
775	// take render cost of node into account
776	// otherwise danger of being stuck in a local minimum!!
777	const float factor = mRenderCostDecreaseWeight;
778	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
779	#endif
780
781	splitCandidate.SetPriority(priority);
782
783	// max cost threshold violated?
784	splitCandidate.mMaxCostMisses =
785	success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
786	//Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
787	}
788
789
790	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
791	VspTraversalData &tData,
792	VspTraversalData &frontData,
793	VspTraversalData &backData)
794	{
795	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
796
797	//-- the front and back traversal data is filled with the new values
798
799	frontData.mDepth = tData.mDepth + 1;
800	backData.mDepth = tData.mDepth + 1;
801
802	frontData.mRays = new RayInfoContainer();
803	backData.mRays = new RayInfoContainer();
804
805	//-- subdivide rays
806	SplitRays(splitPlane,
807	*tData.mRays,
808	*frontData.mRays,
809	*backData.mRays);
810
811	//Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
812
813	//-- compute pvs
814	frontData.mPvs = EvalPvsSize(*frontData.mRays);
815	backData.mPvs = EvalPvsSize(*backData.mRays);
816
817	// split front and back node geometry and compute area
818	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
819	frontData.mBoundingBox, backData.mBoundingBox);
820
821
822	frontData.mProbability = frontData.mBoundingBox.GetVolume();
823	backData.mProbability = tData.mProbability - frontData.mProbability;
824
825
826	///////////////////////////////////////////
827	// subdivide further
828
829	// store maximal and minimal depth
830	if (tData.mDepth > mVspStats.maxDepth)
831	{
832	Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
833	mVspStats.maxDepth = tData.mDepth;
834	}
835
836	// two more leaves
837	mVspStats.nodes += 2;
838
839	VspInterior *interior = new VspInterior(splitPlane);
840
841	#ifdef _DEBUG
842	Debug << interior << endl;
843	#endif+
844
845
846	//-- create front and back leaf
847
848	VspInterior *parent = leaf->GetParent();
849
850	// replace a link from node's parent
851	if (parent)
852	{
853	parent->ReplaceChildLink(leaf, interior);
854	interior->SetParent(parent);
855
856	// remove "parent" view cell from pvs of all objects (traverse trough rays)
857	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
858	}
859	else // new root
860	{
861	mRoot = interior;
862	}
863
864	VspLeaf *frontLeaf = new VspLeaf(interior);
865	VspLeaf *backLeaf = new VspLeaf(interior);
866
867	// and setup child links
868	interior->SetupChildLinks(frontLeaf, backLeaf);
869
870	// add bounding box
871	interior->SetBoundingBox(tData.mBoundingBox);
872
873	// set front and back leaf
874	frontData.mNode = frontLeaf;
875	backData.mNode = backLeaf;
876
877	// explicitely create front and back view cell
878	CreateViewCell(frontData, false);
879	CreateViewCell(backData, false);
880
881
882	#if WORK_WITH_VIEWCELL_PVS
883	// create front and back view cell
884	// add front and back view cell to "Potentially Visbilie View Cells"
885	// of the objects in front and back pvs
886
887	AddViewCellReferences(frontLeaf->GetViewCell());
888	AddViewCellReferences(backLeaf->GetViewCell());
889	#endif
890
891	interior->mTimeStamp = mTimeStamp ++;
892
893	return interior;
894	}
895
896
897	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
898	{
899	KdLeaf::NewMail();
900
901	// remove the parents from the object pvss
902	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
903
904	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
905	{
906	Intersectable object = (oit).first;
907	// HACK: make sure that the view cell is removed from the pvs
908	const float high_contri = 9999999;
909
910	// remove reference count of view cells
911	object->mViewCellPvs.RemoveSample(parent, high_contri);
912	}
913	}
914
915
916	void VspTree::AddViewCellReferences(ViewCell *vc) const
917	{
918	KdLeaf::NewMail();
919
920	// Add front view cell to the object pvsss
921	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
922
923	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
924	{
925	Intersectable object = (oit).first;
926
927	// increase reference count of view cells
928	object->mViewCellPvs.AddSample(vc, 1);
929	}
930	}
931
932
933	bool VspTree::AddKdLeafToPvs(KdLeaf *leaf,
934	ViewCell *vc,
935	float &pdf,
936	float &contribution)
937	{
938	bool contri = false;
939
940	#if 1 // add kd intersecable to pvs
941	KdIntersectable *kdObj = mOspTree->GetOrCreateKdIntersectable(leaf);
942
943	if (vc->AddPvsSample(kdObj, pdf, contribution))
944	{
945	return true;
946	}
947
948	#else // add all objects of kd node
949
950	pdf = 0;
951	contribution = 0;
952
953	ObjectContainer::const_iterator it, it_end = leaf->mObjects.end();
954
955	for (it = leaf->mObjects.begin(); it != it_end; ++ it)
956	{
957	Intersectable object = it;
958
959	float newpdf;
960	float newcontri;
961
962	if (vc->AddPvsSample(object, newpdf, newcontri))
963	{
964	contri = true;
965	}
966
967	pdf += newPdf;
968	newContri += contribution;
969	}
970
971	#endif
972
973	return contri;
974	}
975
976	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
977	const RayInfoContainer &rays,
978	float &sampleContributions,
979	int &contributingSamples)
980	{
981	sampleContributions = 0;
982	contributingSamples = 0;
983
984	RayInfoContainer::const_iterator it, it_end = rays.end();
985
986	ViewCellLeaf *vc = leaf->GetViewCell();
987
988	// add contributions from samples to the PVS
989	for (it = rays.begin(); it != it_end; ++ it)
990	{
991	float sc = 0.0f;
992	VssRay ray = (it).mRay;
993
994	bool madeContrib = false;
995	float contribution;
996
997	Intersectable *obj = ray->mTerminationObject;
998
999	if (obj)
1000	{
1001	if (mStoreKdPvs)
1002	{
1003	// potentially visible kd cells
1004	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1005	AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
1006	}
1007	else
1008	{
1009	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
1010	{
1011	madeContrib = true;
1012	}
1013	}
1014
1015	sc += contribution;
1016	}
1017
1018	obj = ray->mOriginObject;
1019
1020	if (obj)
1021	{
1022	// potentially visible kd cells
1023	if (!mStoreKdPvs) // matt Todo: remove storekdpvs!!
1024	{
1025	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
1026	{
1027	madeContrib = true;
1028	}
1029	}
1030	else
1031	{
1032	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1033	AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
1034	}
1035
1036
1037
1038	sc += contribution;
1039	}
1040
1041	if (madeContrib)
1042	{
1043	++ contributingSamples;
1044	}
1045
1046	// store rays for visualization
1047	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
1048	}
1049	}
1050
1051
1052	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
1053	const int axis,
1054	float minBand,
1055	float maxBand)
1056	{
1057	mLocalSplitCandidates->clear();
1058
1059	int requestedSize = 2 * (int)(rays.size());
1060
1061	// creates a sorted split candidates array
1062	if (mLocalSplitCandidates->capacity() > 500000 &&
1063	requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) )
1064	{
1065	delete mLocalSplitCandidates;
1066	mLocalSplitCandidates = new vector<SortableEntry>;
1067	}
1068
1069	mLocalSplitCandidates->reserve(requestedSize);
1070
1071
1072	float pos;
1073
1074	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1075
1076	//-- insert all queries
1077	for (rit = rays.begin(); rit != rit_end; ++ rit)
1078	{
1079	const bool positive = (*rit).mRay->HasPosDir(axis);
1080
1081	pos = (*rit).ExtrapOrigin(axis);
1082
1083	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
1084	pos, (*rit).mRay));
1085
1086	pos = (*rit).ExtrapTermination(axis);
1087
1088	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1089	pos, (*rit).mRay));
1090	}
1091
1092	stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end());
1093	}
1094
1095
1096	int VspTree::GetPvsContribution(Intersectable *object) const
1097	{
1098	int pvsContri = 0;
1099
1100	KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
1101
1102	Intersectable::NewMail();
1103
1104	// Search kd leaves this object is attached to
1105	for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
1106	{
1107	KdNode l = (kit).first;
1108
1109	// new object found during sweep
1110	// => increase pvs contribution of this kd node
1111	if (!l->Mailed())
1112	{
1113	l->Mail();
1114	++ pvsContri;
1115	}
1116	}
1117
1118	return pvsContri;
1119	}
1120
1121
1122	int VspTree::PrepareHeuristics(KdLeaf *leaf)
1123	{
1124	int pvsSize = 0;
1125
1126	if (!leaf->Mailed())
1127	{
1128	leaf->Mail();
1129	leaf->mCounter = 1;
1130
1131	// add objects without the objects which are in several kd leaves
1132	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1133	//Debug << "adding " << (int)leaf->mObjects.size() << " " << leaf->mMultipleObjects.size() << endl;
1134	}
1135	else
1136	{
1137	++ leaf->mCounter;
1138	}
1139
1140	//-- the objects belonging to several leaves must be handled seperately
1141
1142	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1143
1144	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1145	{
1146	Intersectable object = oit;
1147
1148	if (!object->Mailed())
1149	{
1150	object->Mail();
1151	object->mCounter = 1;
1152
1153	++ pvsSize;
1154	}
1155	else
1156	{
1157	++ object->mCounter;
1158	}
1159	}
1160
1161	return pvsSize;
1162	}
1163
1164
1165	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1166	{
1167	Intersectable::NewMail();
1168	KdNode::NewMail();
1169
1170	int pvsSize = 0;
1171
1172	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1173
1174	//-- set all kd nodes / objects as belonging to the front pvs
1175
1176	for (ri = rays.begin(); ri != ri_end; ++ ri)
1177	{
1178	VssRay ray = (ri).mRay;
1179	Intersectable *oObject = ray->mOriginObject;
1180
1181	if (oObject)
1182	{
1183	if (!mUseKdPvsForHeuristics)
1184	{
1185	if (!oObject->Mailed())
1186	{
1187	oObject->Mail();
1188	oObject->mCounter = 1;
1189
1190	++ pvsSize;
1191	}
1192	else
1193	{
1194	++ oObject->mCounter;
1195	}
1196	}
1197	else
1198	{
1199	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1200	pvsSize += PrepareHeuristics(leaf);
1201	}
1202	}
1203
1204	Intersectable tObject = (ri).mRay->mTerminationObject;
1205
1206	if (tObject)
1207	{
1208	if (!mUseKdPvsForHeuristics)
1209	{
1210	if (!tObject->Mailed())
1211	{
1212	tObject->Mail();
1213	tObject->mCounter = 1;
1214	++ pvsSize;
1215	}
1216	else
1217	{
1218	++ tObject->mCounter;
1219	}
1220	}
1221	else
1222	{
1223	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1224	pvsSize += PrepareHeuristics(leaf);
1225	}
1226	}
1227	}
1228
1229	return pvsSize;
1230	}
1231
1232
1233	void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
1234	{
1235	// leaf falls out of right pvs
1236	if (-- leaf->mCounter == 0)
1237	{
1238	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1239	}
1240
1241	//-- handle objects which are in several kd leaves separately
1242	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1243
1244	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1245	{
1246	Intersectable object = oit;
1247
1248	if (-- object->mCounter == 0)
1249	{
1250	-- pvs;
1251	}
1252	}
1253	}
1254
1255
1256	void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const
1257	{
1258	if (leaf->Mailed())
1259	return;
1260
1261	leaf->Mail();
1262
1263	// add objects without those which are part of several kd leaves
1264	pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1265
1266	//-- handle objects of several kd leaves separately
1267	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1268
1269	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1270	{
1271	Intersectable object = oit;
1272
1273	// object not previously in pvs
1274	if (!object->Mailed())
1275	{
1276	object->Mail();
1277	++ pvs;
1278	}
1279	}
1280	}
1281
1282
1283	void VspTree::EvalPvsIncr(const SortableEntry &ci,
1284	int &pvsLeft,
1285	int &pvsRight) const
1286	{
1287	VssRay *ray = ci.ray;
1288
1289	Intersectable *oObject = ray->mOriginObject;
1290	Intersectable *tObject = ray->mTerminationObject;
1291
1292	if (oObject)
1293	{
1294	if (!mUseKdPvsForHeuristics)
1295	{
1296	if (ci.type == SortableEntry::ERayMin)
1297	{
1298	if (!oObject->Mailed())
1299	{
1300	oObject->Mail();
1301	++ pvsLeft;
1302	}
1303	}
1304	else if (ci.type == SortableEntry::ERayMax)
1305	{
1306	if (-- oObject->mCounter == 0)
1307	-- pvsRight;
1308	}
1309	}
1310	else // per kd node
1311	{
1312	KdLeaf *node = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1313
1314	// add contributions of the kd nodes
1315	if (ci.type == SortableEntry::ERayMin)
1316	{
1317	AddContriToPvs(node, pvsLeft);
1318	}
1319	else if (ci.type == SortableEntry::ERayMax)
1320	{
1321	RemoveContriFromPvs(node, pvsRight);
1322	}
1323	}
1324	}
1325
1326	if (tObject)
1327	{
1328	if (!mUseKdPvsForHeuristics)
1329	{
1330	if (ci.type == SortableEntry::ERayMin)
1331	{
1332	if (!tObject->Mailed())
1333	{
1334	tObject->Mail();
1335	++ pvsLeft;
1336	}
1337	}
1338	else if (ci.type == SortableEntry::ERayMax)
1339	{
1340	if (-- tObject->mCounter == 0)
1341	-- pvsRight;
1342	}
1343	}
1344	else // per kd node
1345	{
1346	KdLeaf *node = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1347
1348	if (ci.type == SortableEntry::ERayMin)
1349	{
1350	AddContriToPvs(node, pvsLeft);
1351	}
1352	else if (ci.type == SortableEntry::ERayMax)
1353	{
1354	RemoveContriFromPvs(node, pvsRight);
1355	}
1356	}
1357	}
1358	}
1359
1360
1361	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1362	const AxisAlignedBox3 &box,
1363	const int axis,
1364	float &position)
1365	{
1366	RayInfoContainer usedRays;
1367
1368	if (mMaxTests < (int)tData.mRays->size())
1369	{
1370	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
1371	}
1372	else
1373	{
1374	usedRays = *tData.mRays;
1375	}
1376
1377	int pvsSize = tData.mPvs;
1378
1379	const float minBox = box.Min(axis);
1380	const float maxBox = box.Max(axis);
1381
1382	const float sizeBox = maxBox - minBox;
1383
1384	const float minBand = minBox + mMinBand * sizeBox;
1385	const float maxBand = minBox + mMaxBand * sizeBox;
1386
1387	SortSplitCandidates(usedRays, axis, minBand, maxBand);
1388
1389	// prepare the sweep
1390	// (note: returns pvs size, so there would be no need
1391	// to give pvs size as argument)
1392	pvsSize = PrepareHeuristics(usedRays);
1393
1394	// go through the lists, count the number of objects left and right
1395	// and evaluate the following cost funcion:
1396	// C = ct_div_ci + (qlrl + qrrr)/queries
1397
1398	int pvsl = 0;
1399	int pvsr = pvsSize;
1400
1401	int pvsBack = pvsl;
1402	int pvsFront = pvsr;
1403
1404	float sum = (float)pvsSize * sizeBox;
1405	float minSum = 1e20f;
1406
1407
1408	// if no good split can be found, take mid split
1409	position = minBox + 0.5f * sizeBox;
1410
1411	// the relative cost ratio
1412	float ratio = 99999999.0f;
1413	bool splitPlaneFound = false;
1414
1415	Intersectable::NewMail();
1416	KdLeaf::NewMail();
1417
1418
1419	//-- traverse through visibility events
1420
1421	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end();
1422
1423	for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci)
1424	{
1425	EvalPvsIncr(*ci, pvsl, pvsr);
1426
1427	// Note: sufficient to compare size of bounding boxes of front and back side?
1428	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1429	{
1430
1431	float currentPos;
1432
1433	// HACK: current positition is BETWEEN visibility events
1434	if (0 && ((ci + 1) != ci_end))
1435	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1436	else
1437	currentPos = (*ci).value;
1438
1439	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1440	//Debug << "pos=" << (*ci).value << "\t newpos=" << currentPos << "\t pvs=(" << pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
1441
1442	if (sum < minSum)
1443	{
1444	splitPlaneFound = true;
1445
1446	minSum = sum;
1447	position = currentPos;
1448
1449	pvsBack = pvsl;
1450	pvsFront = pvsr;
1451	}
1452	}
1453	}
1454
1455
1456	//-- compute cost
1457
1458	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1459	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1460
1461	const float pOverall = sizeBox;
1462	const float pBack = position - minBox;
1463	const float pFront = maxBox - position;
1464
1465	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1466	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1467	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1468
1469	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1470	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1471
1472	if (splitPlaneFound)
1473	{
1474	ratio = newRenderCost / oldRenderCost;
1475	}
1476
1477	const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1478
1479	/*
1480	//if (axis != 1)
1481	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1482	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
1483
1484	Debug << "\n§§§§ eval local cost §§§§" << endl
1485	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1486	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1487	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1488	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1489	*/
1490	return ratio;
1491	}
1492
1493
1494	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1495	AxisAlignedPlane &plane,
1496	float &pFront,
1497	float &pBack)
1498	{
1499	float nPosition[3];
1500	float nCostRatio[3];
1501	float nProbFront[3];
1502	float nProbBack[3];
1503
1504	// create bounding box of node geometry
1505	AxisAlignedBox3 box = tData.mBoundingBox;
1506
1507	int sAxis = 0;
1508	int bestAxis = -1;
1509
1510	// if we use some kind of specialised fixed axis
1511	const bool useSpecialAxis =
1512	mOnlyDrivingAxis \|\| mCirculatingAxis;
1513	//Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
1514	if (mCirculatingAxis)
1515	{
1516	int parentAxis = 0;
1517	VspNode *parent = tData.mNode->GetParent();
1518
1519	if (parent)
1520	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1521
1522	sAxis = (parentAxis + 1) % 3;
1523	}
1524	else if (mOnlyDrivingAxis)
1525	{
1526	sAxis = box.Size().DrivingAxis();
1527	}
1528
1529	for (int axis = 0; axis < 3; ++ axis)
1530	{
1531	if (!useSpecialAxis \|\| (axis == sAxis))
1532	{
1533	if (mUseCostHeuristics)
1534	{
1535	//-- place split plane using heuristics
1536	nCostRatio[axis] =
1537	EvalLocalCostHeuristics(tData,
1538	box,
1539	axis,
1540	nPosition[axis]);
1541	}
1542	else
1543	{
1544	//-- split plane position is spatial median
1545	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1546	nCostRatio[axis] = EvalLocalSplitCost(tData,
1547	box,
1548	axis,
1549	nPosition[axis],
1550	nProbFront[axis],
1551	nProbBack[axis]);
1552	}
1553
1554	if (bestAxis == -1)
1555	{
1556	bestAxis = axis;
1557	}
1558	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1559	{
1560	bestAxis = axis;
1561	}
1562	}
1563	}
1564
1565
1566	//-- assign values of best split
1567
1568	plane.mAxis = bestAxis;
1569	plane.mPosition = nPosition[bestAxis]; // split plane position
1570
1571	pFront = nProbFront[bestAxis];
1572	pBack = nProbBack[bestAxis];
1573
1574	//Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1575	return nCostRatio[bestAxis];
1576	}
1577
1578
1579	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1580	const VspTraversalData &data,
1581	float &normalizedOldRenderCost) const
1582	{
1583	float pvsFront = 0;
1584	float pvsBack = 0;
1585	float totalPvs = 0;
1586
1587	// probability that view point lies in back / front node
1588	float pOverall = data.mProbability;
1589	float pFront = 0;
1590	float pBack = 0;
1591
1592	const float viewSpaceVol = mBoundingBox.GetVolume();
1593
1594	// create unique ids for pvs heuristics
1595	Intersectable::NewMail(3);
1596	KdLeaf::NewMail(3);
1597
1598	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1599
1600	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1601	{
1602	RayInfo rayInf = *rit;
1603
1604	float t;
1605	VssRay *ray = rayInf.mRay;
1606
1607	const int cf =
1608	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1609	candidatePlane.mPosition, t);
1610
1611	if (!mUseKdPvsForHeuristics)
1612	{
1613	// find front and back pvs for origing and termination object
1614	UpdateObjPvsContri(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1615	UpdateObjPvsContri(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1616	}
1617	else
1618	{
1619	if (ray->mTerminationObject)
1620	{
1621	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1622	UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
1623	}
1624
1625	if (ray->mOriginObject)
1626	{
1627	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1628	UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
1629	}
1630	}
1631	}
1632
1633
1634	AxisAlignedBox3 frontBox;
1635	AxisAlignedBox3 backBox;
1636
1637	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1638
1639	pFront = frontBox.GetVolume();
1640	pBack = pOverall - pFront;
1641
1642
1643	//-- pvs rendering heuristics
1644	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1645	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1646
1647	//-- only render cost heuristics or combined with standard deviation
1648	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1649	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1650	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1651
1652	const float oldRenderCost = pOverall * penaltyOld;
1653	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1654
1655	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1656
1657	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1658	/*
1659	Debug << "\n==== eval render cost decrease ===" << endl
1660	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1661	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1662	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1663	<< "render cost decrease: " << renderCostDecrease << endl;
1664	*/
1665	return renderCostDecrease;
1666	}
1667
1668
1669	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1670	const AxisAlignedBox3 &box,
1671	const int axis,
1672	const float &position,
1673	float &pFront,
1674	float &pBack) const
1675	{
1676	float pvsTotal = 0;
1677	float pvsFront = 0;
1678	float pvsBack = 0;
1679
1680	// create unique ids for pvs heuristics
1681	Intersectable::NewMail(3);
1682
1683	const int pvsSize = data.mPvs;
1684
1685	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1686
1687	// this is the main ray classification loop!
1688	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1689	{
1690	// determine the side of this ray with respect to the plane
1691	float t;
1692	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1693
1694	UpdateObjPvsContri((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1695	UpdateObjPvsContri((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1696	}
1697
1698	//-- evaluate cost heuristics
1699
1700	float pOverall;
1701
1702	pOverall = data.mProbability;
1703
1704	// we use spatial mid split => simplified computation
1705	pBack = pFront = pOverall * 0.5f;
1706
1707	const float newCost = pvsBack * pBack + pvsFront * pFront;
1708	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1709
1710	#ifdef _DEBUG
1711	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1712	Debug << pFront << " " << pBack << " " << pOverall << endl;
1713	#endif
1714
1715	return (mCtDivCi + newCost) / oldCost;
1716	}
1717
1718
1719	void VspTree::UpdateObjPvsContri(Intersectable *obj,
1720	const int cf,
1721	float &frontPvs,
1722	float &backPvs,
1723	float &totalPvs) const
1724	{
1725	if (!obj) return;
1726
1727	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1728	const int renderCost = 1;
1729
1730	// object in no pvs => new
1731	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1732	{
1733	totalPvs += renderCost;
1734	}
1735
1736	// QUESTION matt: is it safe to assume that
1737	// the object belongs to no pvs in this case?
1738	//if (cf == Ray::COINCIDENT) return;
1739
1740	if (cf >= 0) // front pvs
1741	{
1742	if (!obj->Mailed() && !obj->Mailed(2))
1743	{
1744	frontPvs += renderCost;
1745
1746	// already in back pvs => in both pvss
1747	if (obj->Mailed(1))
1748	obj->Mail(2);
1749	else
1750	obj->Mail();
1751	}
1752	}
1753
1754	if (cf <= 0) // back pvs
1755	{
1756	if (!obj->Mailed(1) && !obj->Mailed(2))
1757	{
1758	backPvs += renderCost;
1759
1760	// already in front pvs => in both pvss
1761	if (obj->Mailed())
1762	obj->Mail(2);
1763	else
1764	obj->Mail(1);
1765	}
1766	}
1767	}
1768
1769
1770	void VspTree::UpdateKdLeafPvsContri(KdLeaf *leaf,
1771	const int cf,
1772	float &frontPvs,
1773	float &backPvs,
1774	float &totalPvs) const
1775	{
1776	if (!leaf) return;
1777
1778	// the objects which are referenced in this and only this leaf
1779	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1780
1781	// newly found leaf
1782	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1783	{
1784	totalPvs += contri;
1785	}
1786
1787	// compute contribution of yet unclassified objects
1788	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1789
1790	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1791	{
1792	UpdateObjPvsContri(*oit, cf, frontPvs, backPvs, totalPvs);
1793	}
1794
1795	// QUESTION matt: is it safe to assume that
1796	// the object belongs to no pvs in this case?
1797	//if (cf == Ray::COINCIDENT) return;
1798
1799	if (cf >= 0) // front pvs
1800	{
1801	if (!leaf->Mailed() && !leaf->Mailed(2))
1802	{
1803	frontPvs += contri;
1804
1805	// already in back pvs => in both pvss
1806	if (leaf->Mailed(1))
1807	leaf->Mail(2);
1808	else
1809	leaf->Mail();
1810	}
1811	}
1812
1813	if (cf <= 0) // back pvs
1814	{
1815	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1816	{
1817	backPvs += contri;
1818
1819	// already in front pvs => in both pvss
1820	if (leaf->Mailed())
1821	leaf->Mail(2);
1822	else
1823	leaf->Mail(1);
1824	}
1825	}
1826	}
1827
1828
1829	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1830	const bool onlyUnmailed,
1831	const int maxPvsSize) const
1832	{
1833	stack<VspNode *> nodeStack;
1834	nodeStack.push(mRoot);
1835
1836	while (!nodeStack.empty())
1837	{
1838	VspNode *node = nodeStack.top();
1839	nodeStack.pop();
1840
1841	if (node->IsLeaf())
1842	{
1843	// test if this leaf is in valid view space
1844	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1845	if (leaf->TreeValid() &&
1846	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1847	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
1848	{
1849	leaves.push_back(leaf);
1850	}
1851	}
1852	else
1853	{
1854	VspInterior interior = dynamic_cast<VspInterior >(node);
1855
1856	nodeStack.push(interior->GetBack());
1857	nodeStack.push(interior->GetFront());
1858	}
1859	}
1860	}
1861
1862
1863	AxisAlignedBox3 VspTree::GetBoundingBox() const
1864	{
1865	return mBoundingBox;
1866	}
1867
1868
1869	VspNode *VspTree::GetRoot() const
1870	{
1871	return mRoot;
1872	}
1873
1874
1875	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1876	{
1877	// the node became a leaf -> evaluate stats for leafs
1878	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
1879
1880
1881	if (data.mPvs > mVspStats.maxPvs)
1882	{
1883	mVspStats.maxPvs = data.mPvs;
1884	}
1885
1886	mVspStats.pvs += data.mPvs;
1887
1888	if (data.mDepth < mVspStats.minDepth)
1889	{
1890	mVspStats.minDepth = data.mDepth;
1891	}
1892
1893	if (data.mDepth >= mTermMaxDepth)
1894	{
1895	++ mVspStats.maxDepthNodes;
1896	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1897	}
1898
1899	// accumulate rays to compute rays / leaf
1900	mVspStats.accumRays += (int)data.mRays->size();
1901
1902	if (data.mPvs < mTermMinPvs)
1903	++ mVspStats.minPvsNodes;
1904
1905	if ((int)data.mRays->size() < mTermMinRays)
1906	++ mVspStats.minRaysNodes;
1907
1908	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1909	++ mVspStats.maxRayContribNodes;
1910
1911	if (data.mProbability <= mTermMinProbability)
1912	++ mVspStats.minProbabilityNodes;
1913
1914	// accumulate depth to compute average depth
1915	mVspStats.accumDepth += data.mDepth;
1916
1917	++ mCreatedViewCells;
1918
1919	#ifdef _DEBUG
1920	Debug << "BSP stats: "
1921	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1922	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1923	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1924	<< "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
1925	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1926	#endif
1927	}
1928
1929
1930	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1931	{
1932	ViewCell::NewMail();
1933	CollectViewCells(mRoot, onlyValid, viewCells, true);
1934	}
1935
1936
1937	void VspTree::CollapseViewCells()
1938	{
1939	// TODO matt
1940	#if HAS_TO_BE_REDONE
1941	stack<VspNode *> nodeStack;
1942
1943	if (!mRoot)
1944	return;
1945
1946	nodeStack.push(mRoot);
1947
1948	while (!nodeStack.empty())
1949	{
1950	VspNode *node = nodeStack.top();
1951	nodeStack.pop();
1952
1953	if (node->IsLeaf())
1954	{
1955	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1956
1957	if (!viewCell->GetValid())
1958	{
1959	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1960
1961	ViewCellContainer leaves;
1962	mViewCellsTree->CollectLeaves(viewCell, leaves);
1963
1964	ViewCellContainer::const_iterator it, it_end = leaves.end();
1965
1966	for (it = leaves.begin(); it != it_end; ++ it)
1967	{
1968	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
1969	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1970	++ mVspStats.invalidLeaves;
1971	}
1972
1973	// add to unbounded view cell
1974	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1975	DEL_PTR(viewCell);
1976	}
1977	}
1978	else
1979	{
1980	VspInterior interior = dynamic_cast<VspInterior >(node);
1981
1982	nodeStack.push(interior->GetFront());
1983	nodeStack.push(interior->GetBack());
1984	}
1985	}
1986
1987	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1988	#endif
1989	}
1990
1991
1992	void VspTree::CollectRays(VssRayContainer &rays)
1993	{
1994	vector<VspLeaf *> leaves;
1995	CollectLeaves(leaves);
1996
1997	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1998
1999	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2000	{
2001	VspLeaf leaf = lit;
2002	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2003
2004	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2005	rays.push_back(*rit);
2006	}
2007	}
2008
2009
2010	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
2011	{
2012	mViewCellsManager = vcm;
2013	}
2014
2015
2016	void VspTree::ValidateTree()
2017	{
2018	mVspStats.invalidLeaves = 0;
2019
2020	stack<VspNode *> nodeStack;
2021
2022	if (!mRoot)
2023	return;
2024
2025	nodeStack.push(mRoot);
2026
2027	while (!nodeStack.empty())
2028	{
2029	VspNode *node = nodeStack.top();
2030	nodeStack.pop();
2031
2032	if (node->IsLeaf())
2033	{
2034	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2035
2036	if (!leaf->GetViewCell()->GetValid())
2037	++ mVspStats.invalidLeaves;
2038
2039	// validity flags don't match => repair
2040	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2041	{
2042	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2043	PropagateUpValidity(leaf);
2044	}
2045	}
2046	else
2047	{
2048	VspInterior interior = dynamic_cast<VspInterior >(node);
2049
2050	nodeStack.push(interior->GetFront());
2051	nodeStack.push(interior->GetBack());
2052	}
2053	}
2054
2055	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
2056	}
2057
2058
2059
2060	void VspTree::CollectViewCells(VspNode *root,
2061	bool onlyValid,
2062	ViewCellContainer &viewCells,
2063	bool onlyUnmailed) const
2064	{
2065	stack<VspNode *> nodeStack;
2066
2067	if (!root)
2068	return;
2069
2070	nodeStack.push(root);
2071
2072	while (!nodeStack.empty())
2073	{
2074	VspNode *node = nodeStack.top();
2075	nodeStack.pop();
2076
2077	if (node->IsLeaf())
2078	{
2079	if (!onlyValid \|\| node->TreeValid())
2080	{
2081	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
2082
2083	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2084
2085	if (!onlyUnmailed \|\| !viewCell->Mailed())
2086	{
2087	viewCell->Mail();
2088	viewCells.push_back(viewCell);
2089	}
2090	}
2091	}
2092	else
2093	{
2094	VspInterior interior = dynamic_cast<VspInterior >(node);
2095
2096	nodeStack.push(interior->GetFront());
2097	nodeStack.push(interior->GetBack());
2098	}
2099	}
2100	}
2101
2102
2103	int VspTree::FindNeighbors(VspLeaf *n,
2104	vector<VspLeaf *> &neighbors,
2105	const bool onlyUnmailed) const
2106	{
2107	stack<VspNode *> nodeStack;
2108	nodeStack.push(mRoot);
2109
2110	const AxisAlignedBox3 box = GetBoundingBox(n);
2111
2112	while (!nodeStack.empty())
2113	{
2114	VspNode *node = nodeStack.top();
2115	nodeStack.pop();
2116
2117	if (node->IsLeaf())
2118	{
2119	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2120
2121	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
2122	neighbors.push_back(leaf);
2123	}
2124	else
2125	{
2126	VspInterior interior = dynamic_cast<VspInterior >(node);
2127
2128	if (interior->GetPosition() > box.Max(interior->GetAxis()))
2129	nodeStack.push(interior->GetBack());
2130	else
2131	{
2132	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2133	nodeStack.push(interior->GetFront());
2134	else
2135	{
2136	// random decision
2137	nodeStack.push(interior->GetBack());
2138	nodeStack.push(interior->GetFront());
2139	}
2140	}
2141	}
2142	}
2143
2144	return (int)neighbors.size();
2145	}
2146
2147
2148	// Find random neighbor which was not mailed
2149	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2150	{
2151	stack<VspNode *> nodeStack;
2152	nodeStack.push(mRoot);
2153
2154	int mask = rand();
2155
2156	while (!nodeStack.empty())
2157	{
2158	VspNode *node = nodeStack.top();
2159
2160	nodeStack.pop();
2161
2162	if (node->IsLeaf())
2163	{
2164	return dynamic_cast<VspLeaf *>(node);
2165	}
2166	else
2167	{
2168	VspInterior interior = dynamic_cast<VspInterior >(node);
2169	VspNode *next;
2170
2171	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2172	{
2173	next = interior->GetFront();
2174	}
2175	else
2176	{
2177	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2178	{
2179	next = interior->GetBack();
2180	}
2181	else
2182	{
2183	// random decision
2184	if (mask & 1)
2185	next = interior->GetBack();
2186	else
2187	next = interior->GetFront();
2188	mask = mask >> 1;
2189	}
2190	}
2191
2192	nodeStack.push(next);
2193	}
2194	}
2195
2196	return NULL;
2197	}
2198
2199
2200	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2201	{
2202	stack<VspNode *> nodeStack;
2203
2204	nodeStack.push(mRoot);
2205
2206	int mask = rand();
2207
2208	while (!nodeStack.empty())
2209	{
2210	VspNode *node = nodeStack.top();
2211	nodeStack.pop();
2212
2213	if (node->IsLeaf())
2214	{
2215	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2216	return dynamic_cast<VspLeaf *>(node);
2217	}
2218	else
2219	{
2220	VspInterior interior = dynamic_cast<VspInterior >(node);
2221
2222	// random decision
2223	if (mask & 1)
2224	nodeStack.push(interior->GetBack());
2225	else
2226	nodeStack.push(interior->GetFront());
2227
2228	mask = mask >> 1;
2229	}
2230	}
2231
2232	return NULL;
2233	}
2234
2235
2236	void VspTree::CollectPvs(const RayInfoContainer &rays,
2237	ObjectContainer &objects) const
2238	{
2239	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2240
2241	Intersectable::NewMail();
2242
2243	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2244	{
2245	VssRay ray = (rit).mRay;
2246
2247	Intersectable *object;
2248	object = ray->mOriginObject;
2249
2250	if (object)
2251	{
2252	if (!object->Mailed())
2253	{
2254	object->Mail();
2255	objects.push_back(object);
2256	}
2257	}
2258
2259	object = ray->mTerminationObject;
2260
2261	if (object)
2262	{
2263	if (!object->Mailed())
2264	{
2265	object->Mail();
2266	objects.push_back(object);
2267	}
2268	}
2269	}
2270	}
2271
2272
2273	int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
2274	{
2275	int pvsSize = 0;
2276	Intersectable::NewMail();
2277
2278	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2279
2280	if (!mUseKdPvsForHeuristics)
2281	{
2282	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2283	{
2284	VssRay ray = (rit).mRay;
2285
2286	if (ray->mOriginObject)
2287	{
2288	if (!ray->mOriginObject->Mailed())
2289	{
2290	ray->mOriginObject->Mail();
2291	++ pvsSize;
2292	}
2293	}
2294	if (ray->mTerminationObject)
2295	{
2296	if (!ray->mTerminationObject->Mailed())
2297	{
2298	ray->mTerminationObject->Mail();
2299	++ pvsSize;
2300	}
2301	}
2302	}
2303	}
2304	else // compute pvs from kd nodes
2305	{
2306	KdNode::NewMail();
2307
2308	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2309	{
2310	VssRay ray = (rit).mRay;
2311
2312	if (ray->mTerminationObject)
2313	{
2314	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
2315
2316	if (!leaf->Mailed())
2317	{
2318	leaf->Mail();
2319	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
2320
2321	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
2322	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
2323	{
2324	Intersectable obj = oit;
2325
2326	if (!obj->Mailed())
2327	{
2328	obj->Mail();
2329	++ pvsSize;
2330	}
2331	}
2332	}
2333	}
2334
2335	if (ray->mOriginObject)
2336	{
2337	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
2338
2339	if (!leaf->Mailed())
2340	{
2341	leaf->Mail();
2342	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
2343
2344	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
2345	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
2346	{
2347	Intersectable obj = oit;
2348
2349	if (!obj->Mailed())
2350	{
2351	obj->Mail();
2352	++ pvsSize;
2353	}
2354	}
2355	}
2356	}
2357	}
2358	}
2359
2360	return pvsSize;
2361	}
2362
2363
2364	float VspTree::GetEpsilon() const
2365	{
2366	return mEpsilon;
2367	}
2368
2369
2370	int VspTree::CastLineSegment(const Vector3 &origin,
2371	const Vector3 &termination,
2372	ViewCellContainer &viewcells)
2373	{
2374	int hits = 0;
2375
2376	float mint = 0.0f, maxt = 1.0f;
2377	const Vector3 dir = termination - origin;
2378
2379	stack<LineTraversalData> tStack;
2380
2381	Intersectable::NewMail();
2382	//ViewCell::NewMail();
2383
2384	Vector3 entp = origin;
2385	Vector3 extp = termination;
2386
2387	VspNode *node = mRoot;
2388	VspNode *farChild;
2389
2390	float position;
2391	int axis;
2392
2393	while (1)
2394	{
2395	if (!node->IsLeaf())
2396	{
2397	VspInterior in = dynamic_cast<VspInterior >(node);
2398	position = in->GetPosition();
2399	axis = in->GetAxis();
2400
2401	if (entp[axis] <= position)
2402	{
2403	if (extp[axis] <= position)
2404	{
2405	node = in->GetBack();
2406	// cases N1,N2,N3,P5,Z2,Z3
2407	continue;
2408	} else
2409	{
2410	// case N4
2411	node = in->GetBack();
2412	farChild = in->GetFront();
2413	}
2414	}
2415	else
2416	{
2417	if (position <= extp[axis])
2418	{
2419	node = in->GetFront();
2420	// cases P1,P2,P3,N5,Z1
2421	continue;
2422	}
2423	else
2424	{
2425	node = in->GetFront();
2426	farChild = in->GetBack();
2427	// case P4
2428	}
2429	}
2430
2431	// $$ modification 3.5.2004 - hints from Kamil Ghais
2432	// case N4 or P4
2433	const float tdist = (position - origin[axis]) / dir[axis];
2434	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2435
2436	extp = origin + dir * tdist;
2437	maxt = tdist;
2438	}
2439	else
2440	{
2441	// compute intersection with all objects in this leaf
2442	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2443	ViewCell *vc = leaf->GetViewCell();
2444
2445	// don't have to mail because each view cell belongs to exactly one leaf
2446	//if (!vc->Mailed())
2447	//{
2448	// vc->Mail();
2449	viewcells.push_back(vc);
2450	++ hits;
2451	//}
2452	#if 0
2453	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2454	#endif
2455	// get the next node from the stack
2456	if (tStack.empty())
2457	break;
2458
2459	entp = extp;
2460	mint = maxt;
2461
2462	LineTraversalData &s = tStack.top();
2463	node = s.mNode;
2464	extp = s.mExitPoint;
2465	maxt = s.mMaxT;
2466	tStack.pop();
2467	}
2468	}
2469
2470	return hits;
2471	}
2472
2473
2474	int VspTree::CastRay(Ray &ray)
2475	{
2476	int hits = 0;
2477
2478	stack<LineTraversalData> tStack;
2479	const Vector3 dir = ray.GetDir();
2480
2481	float maxt, mint;
2482
2483	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2484	return 0;
2485
2486	Intersectable::NewMail();
2487	ViewCell::NewMail();
2488
2489	Vector3 entp = ray.Extrap(mint);
2490	Vector3 extp = ray.Extrap(maxt);
2491
2492	const Vector3 origin = entp;
2493
2494	VspNode *node = mRoot;
2495	VspNode *farChild = NULL;
2496
2497	float position;
2498	int axis;
2499
2500	while (1)
2501	{
2502	if (!node->IsLeaf())
2503	{
2504	VspInterior in = dynamic_cast<VspInterior >(node);
2505	position = in->GetPosition();
2506	axis = in->GetAxis();
2507
2508	if (entp[axis] <= position)
2509	{
2510	if (extp[axis] <= position)
2511	{
2512	node = in->GetBack();
2513	// cases N1,N2,N3,P5,Z2,Z3
2514	continue;
2515	}
2516	else
2517	{
2518	// case N4
2519	node = in->GetBack();
2520	farChild = in->GetFront();
2521	}
2522	}
2523	else
2524	{
2525	if (position <= extp[axis])
2526	{
2527	node = in->GetFront();
2528	// cases P1,P2,P3,N5,Z1
2529	continue;
2530	}
2531	else
2532	{
2533	node = in->GetFront();
2534	farChild = in->GetBack();
2535	// case P4
2536	}
2537	}
2538
2539	// $$ modification 3.5.2004 - hints from Kamil Ghais
2540	// case N4 or P4
2541	const float tdist = (position - origin[axis]) / dir[axis];
2542	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2543	extp = origin + dir * tdist;
2544	maxt = tdist;
2545	}
2546	else
2547	{
2548	// compute intersection with all objects in this leaf
2549	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2550	ViewCell *vc = leaf->GetViewCell();
2551
2552	if (!vc->Mailed())
2553	{
2554	vc->Mail();
2555	// todo: add view cells to ray
2556	++ hits;
2557	}
2558	#if 0
2559	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2560	#endif
2561	// get the next node from the stack
2562	if (tStack.empty())
2563	break;
2564
2565	entp = extp;
2566	mint = maxt;
2567
2568	LineTraversalData &s = tStack.top();
2569	node = s.mNode;
2570	extp = s.mExitPoint;
2571	maxt = s.mMaxT;
2572	tStack.pop();
2573	}
2574	}
2575
2576	return hits;
2577	}
2578
2579
2580	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2581	{
2582	if (mRoot == NULL)
2583	return NULL;
2584
2585	stack<VspNode *> nodeStack;
2586	nodeStack.push(mRoot);
2587
2588	ViewCellLeaf *viewcell = NULL;
2589
2590	while (!nodeStack.empty())
2591	{
2592	VspNode *node = nodeStack.top();
2593	nodeStack.pop();
2594
2595	if (node->IsLeaf())
2596	{
2597	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2598	break;
2599	}
2600	else
2601	{
2602	VspInterior interior = dynamic_cast<VspInterior >(node);
2603
2604	// random decision
2605	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2606	nodeStack.push(interior->GetBack());
2607	else
2608	nodeStack.push(interior->GetFront());
2609	}
2610	}
2611
2612	if (active)
2613	return mViewCellsTree->GetActiveViewCell(viewcell);
2614	else
2615	return viewcell;
2616	}
2617
2618
2619	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2620	{
2621	VspNode *node = mRoot;
2622
2623	while (1)
2624	{
2625	// early exit
2626	if (node->TreeValid())
2627	return true;
2628
2629	if (node->IsLeaf())
2630	return false;
2631
2632	VspInterior in = dynamic_cast<VspInterior >(node);
2633
2634	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2635	{
2636	node = in->GetBack();
2637	}
2638	else
2639	{
2640	node = in->GetFront();
2641	}
2642	}
2643
2644	// should never come here
2645	return false;
2646	}
2647
2648
2649	void VspTree::PropagateUpValidity(VspNode *node)
2650	{
2651	const bool isValid = node->TreeValid();
2652
2653	// propagative up invalid flag until only invalid nodes exist over this node
2654	if (!isValid)
2655	{
2656	while (!node->IsRoot() && node->GetParent()->TreeValid())
2657	{
2658	node = node->GetParent();
2659	node->SetTreeValid(false);
2660	}
2661	}
2662	else
2663	{
2664	// propagative up valid flag until one of the subtrees is invalid
2665	while (!node->IsRoot() && !node->TreeValid())
2666	{
2667	node = node->GetParent();
2668	VspInterior interior = dynamic_cast<VspInterior >(node);
2669
2670	// the parent is valid iff both leaves are valid
2671	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2672	interior->GetFront()->TreeValid());
2673	}
2674	}
2675	}
2676
2677	#if ZIPPED_VIEWCELLS
2678	bool VspTree::Export(ogzstream &stream)
2679	#else
2680	bool VspTree::Export(ofstream &stream)
2681	#endif
2682	{
2683	ExportNode(mRoot, stream);
2684
2685	return true;
2686	}
2687
2688
2689	#if ZIPPED_VIEWCELLS
2690	void VspTree::ExportNode(VspNode *node, ogzstream &stream)
2691	#else
2692	void VspTree::ExportNode(VspNode *node, ofstream &stream)
2693	#endif
2694	{
2695	if (node->IsLeaf())
2696	{
2697	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2698	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2699
2700	int id = -1;
2701	if (viewCell != mOutOfBoundsCell)
2702	id = viewCell->GetId();
2703
2704	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2705	}
2706	else
2707	{
2708	VspInterior interior = dynamic_cast<VspInterior >(node);
2709
2710	AxisAlignedPlane plane = interior->GetPlane();
2711	stream << "<Interior plane=\"" << plane.mPosition << " "
2712	<< plane.mAxis << "\">" << endl;
2713
2714	ExportNode(interior->GetBack(), stream);
2715	ExportNode(interior->GetFront(), stream);
2716
2717	stream << "</Interior>" << endl;
2718	}
2719	}
2720
2721
2722	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2723	RayInfoContainer &rays,
2724	RayInfoContainer &frontRays,
2725	RayInfoContainer &backRays) const
2726	{
2727	int splits = 0;
2728
2729	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2730
2731	for (rit = rays.begin(); rit != rit_end; ++ rit)
2732	{
2733	RayInfo bRay = *rit;
2734
2735	VssRay *ray = bRay.mRay;
2736	float t;
2737
2738	// get classification and receive new t
2739	//-- test if start point behind or in front of plane
2740	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2741
2742	if (side == 0)
2743	{
2744	++ splits;
2745
2746	if (ray->HasPosDir(plane.mAxis))
2747	{
2748	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2749	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2750	}
2751	else
2752	{
2753	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2754	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2755	}
2756	}
2757	else if (side == 1)
2758	{
2759	frontRays.push_back(bRay);
2760	}
2761	else
2762	{
2763	backRays.push_back(bRay);
2764	}
2765	}
2766
2767	return splits;
2768	}
2769
2770
2771	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2772	{
2773	if (!node->GetParent())
2774	return mBoundingBox;
2775
2776	if (!node->IsLeaf())
2777	{
2778	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
2779	}
2780
2781	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
2782
2783	AxisAlignedBox3 box(parent->GetBoundingBox());
2784
2785	if (parent->GetFront() == node)
2786	box.SetMin(parent->GetAxis(), parent->GetPosition());
2787	else
2788	box.SetMax(parent->GetAxis(), parent->GetPosition());
2789
2790	return box;
2791	}
2792
2793
2794	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2795	ViewCellContainer &viewCells) const
2796	{
2797	stack<VspNode *> nodeStack;
2798
2799	ViewCell::NewMail();
2800
2801	while (!nodeStack.empty())
2802	{
2803	VspNode *node = nodeStack.top();
2804	nodeStack.pop();
2805
2806	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2807
2808	if (bbox.Includes(box))
2809	{
2810	// node geometry is contained in box
2811	CollectViewCells(node, true, viewCells, true);
2812	}
2813	else if (Overlap(bbox, box))
2814	{
2815	if (node->IsLeaf())
2816	{
2817	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2818
2819	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2820	{
2821	leaf->GetViewCell()->Mail();
2822	viewCells.push_back(leaf->GetViewCell());
2823	}
2824	}
2825	else
2826	{
2827	VspInterior interior = dynamic_cast<VspInterior >(node);
2828
2829	VspNode *first = interior->GetFront();
2830	VspNode *second = interior->GetBack();
2831
2832	nodeStack.push(first);
2833	nodeStack.push(second);
2834	}
2835	}
2836	// default: cull
2837	}
2838
2839	return (int)viewCells.size();
2840	}
2841
2842
2843	void VspTree::CollectDirtyCandidates(VspSplitCandidate *sc,
2844	vector<SplitCandidate *> &dirtyList)
2845	{
2846	VspTraversalData &tData = sc->mParentData;
2847	VspLeaf *node = tData.mNode;
2848
2849	KdLeaf::NewMail();
2850
2851	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2852
2853	// add all kd nodes seen by the rays
2854	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2855	{
2856	VssRay ray = (rit).mRay;
2857
2858	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
2859
2860	if (!leaf->Mailed())
2861	{
2862	leaf->Mail();
2863	dirtyList.push_back(leaf->mSplitCandidate);
2864	}
2865
2866	leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
2867
2868	if (!leaf->Mailed())
2869	{
2870	leaf->Mail();
2871	dirtyList.push_back(leaf->mSplitCandidate);
2872	}
2873	}
2874	}
2875
2876
2877	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2878	RayInfoContainer &rays)
2879	{
2880	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2881
2882	long startTime = GetTime();
2883
2884	cout << "storing rays ... ";
2885
2886	Intersectable::NewMail();
2887
2888	//-- store rays and objects
2889	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2890	{
2891	VssRay ray = rit;
2892	float minT, maxT;
2893	static Ray hray;
2894
2895	hray.Init(*ray);
2896
2897	// TODO: not very efficient to implictly cast between rays types
2898	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2899	{
2900	float len = ray->Length();
2901
2902	if (!len)
2903	len = Limits::Small;
2904
2905	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2906	}
2907	}
2908
2909	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2910	}
2911
2912
2913	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2914	{
2915	// if no precomputation of view cells
2916	CastLineSegment(ray.mOrigin, ray.mTermination, viewCells);
2917	}
2918
2919
2920	/*******************************************************************/
2921	/* class OspTree implementation */
2922	/*******************************************************************/
2923
2924
2925	OspTree::OspTree():
2926	mRoot(NULL),
2927	mTimeStamp(1),
2928	mCopyFromKdTree(false)
2929	{
2930	ReadEnvironment();
2931	mSplitCandidates = new vector<SortableEntry>;
2932	}
2933
2934
2935	OspTree::OspTree(const KdTree &kdTree)
2936	{
2937	ReadEnvironment();
2938
2939	// copy values from kd tree
2940	mCopyFromKdTree = true;
2941	mBoundingBox = kdTree.GetBox();
2942	mRoot = kdTree.GetRoot();
2943
2944	mSplitCandidates = new vector<SortableEntry>;
2945	}
2946
2947
2948	OspTree::~OspTree()
2949	{
2950	// delete kd intersectables
2951	KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
2952
2953	for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
2954	{
2955	DEL_PTR((*it).second);
2956	}
2957
2958	// if not using kd tree root, delete tree (otherwise mKdTree has to do the job)
2959	if (!mCopyFromKdTree)
2960	DEL_PTR(mRoot);
2961
2962	DEL_PTR(mSplitCandidates);
2963	mSubdivisionStats.close();
2964	}
2965
2966
2967	void OspTree::ReadEnvironment()
2968	{
2969	bool randomize = false;
2970	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
2971	if (randomize)
2972	Randomize(); // initialise random generator for heuristics
2973
2974	//-- termination criteria for autopartition
2975	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
2976	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
2977	Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
2978	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
2979
2980	Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
2981
2982	//-- max cost ratio for early tree termination
2983	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
2984
2985	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio",
2986	mTermMinGlobalCostRatio);
2987
2988
2989	//-- factors for bsp tree split plane heuristics
2990	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
2991
2992	//-- partition criteria
2993	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
2994
2995	// if only the driving axis is used for axis aligned split
2996	Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
2997	Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
2998	Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
2999
3000
3001	char subdivisionStatsLog[100];
3002	Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
3003	mSubdivisionStats.open(subdivisionStatsLog);
3004
3005	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
3006	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
3007
3008
3009	//-- debug output
3010
3011	Debug << "***** OSP tree options ****** " << endl;
3012
3013	Debug << "max depth: " << mTermMaxDepth << endl;
3014	Debug << "min probabiliy: " << mTermMinProbability << endl;
3015	Debug << "min objects: " << mTermMinObjects << endl;
3016	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
3017	Debug << "miss tolerance: " << mTermMissTolerance << endl;
3018	Debug << "max leaves: " << mTermMaxLeaves << endl;
3019
3020	Debug << "randomize: " << randomize << endl;
3021
3022	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
3023	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
3024	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
3025	Debug << "max memory: " << mMaxMemory << endl;
3026	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
3027	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
3028
3029	Debug << "split borders: " << mSplitBorder << endl;
3030	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
3031	Debug << endl;
3032	}
3033
3034
3035	void OspTree::SplitObjects(KdLeaf *parent,
3036	const AxisAlignedPlane& splitPlane,
3037	const ObjectContainer &objects,
3038	ObjectContainer &front,
3039	ObjectContainer &back)
3040	{
3041	ObjectContainer::const_iterator oit, oit_end = objects.end();
3042
3043	for (oit = objects.begin(); oit != oit_end; ++ oit)
3044	{
3045	Intersectable object = oit;
3046
3047	// initialise leaf references of objects
3048	if (parent->IsRoot())
3049	{
3050	object->mReferences = 1;
3051	}
3052
3053	// remove parent ref
3054	-- object->mReferences;
3055
3056	// determine the side of this ray with respect to the plane
3057	const AxisAlignedBox3 box = object->GetBox();
3058
3059	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
3060	{
3061	front.push_back(object);
3062	++ object->mReferences;
3063	}
3064
3065	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
3066	{
3067	back.push_back(object);
3068	++ object->mReferences;
3069	}
3070	}
3071
3072	mOspStats.objectRefs -= (int)objects.size();
3073	mOspStats.objectRefs += (int)(back.size() + front.size());
3074	}
3075
3076
3077	KdInterior *OspTree::SubdivideNode(
3078	const AxisAlignedPlane &splitPlane,
3079	const OspTraversalData &tData,
3080	OspTraversalData &frontData,
3081	OspTraversalData &backData
3082	)
3083	{
3084	KdLeaf *leaf = tData.mNode;
3085
3086	// two new leaves
3087	mOspStats.nodes += 2;
3088
3089	// add the new nodes to the tree
3090	KdInterior *node = new KdInterior(leaf->mParent);
3091
3092	const int axis = splitPlane.mAxis;
3093	const float position = splitPlane.mPosition;
3094
3095	node->mAxis = axis;
3096	node->mPosition = position;
3097	node->mBox = tData.mBoundingBox;
3098
3099
3100	//-- the front and back traversal data is filled with the new values
3101
3102	// bounding boxes: split front and back node geometry
3103	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
3104	frontData.mBoundingBox, backData.mBoundingBox);
3105
3106	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
3107
3108	//-- subdivide rays
3109	frontData.mRays = new RayInfoContainer();
3110	backData.mRays = new RayInfoContainer();
3111
3112	SplitRays(splitPlane,
3113	*tData.mRays,
3114	*frontData.mRays,
3115	*backData.mRays);
3116
3117
3118	//-- classify objects
3119	int objectsBack = 0;
3120	int objectsFront = 0;
3121
3122	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
3123
3124	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
3125	{
3126	// determine the side of this ray with respect to the plane
3127	const AxisAlignedBox3 box = (*mi)->GetBox();
3128
3129	if (box.Max(axis) > position + mEpsilon)
3130	++ objectsFront;
3131
3132	if (box.Min(axis) < position - mEpsilon)
3133	++ objectsBack;
3134	}
3135
3136	// TODO matt: compute pvs
3137	frontData.mPvs = objectsFront;
3138	backData.mPvs = objectsBack;
3139
3140	KdLeaf *back = new KdLeaf(node, objectsBack);
3141	KdLeaf *front = new KdLeaf(node, objectsFront);
3142
3143	/////////////
3144	//-- create front and back leaf
3145
3146	KdInterior *parent = leaf->mParent;
3147
3148	// replace a link from node's parent
3149	if (parent)
3150	{
3151	parent->ReplaceChildLink(leaf, node);
3152	node->mParent = parent;
3153	}
3154	else // new root
3155	{
3156	mRoot = node;
3157	}
3158
3159	// and setup child links
3160	node->SetupChildLinks(back, front);
3161
3162	SplitObjects(leaf, splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
3163
3164	ProcessMultipleRefs(front);
3165	ProcessMultipleRefs(back);
3166
3167	frontData.mNode = front;
3168	backData.mNode = back;
3169
3170
3171	// compute probability, i.e., volume of seen view cells
3172	frontData.mProbability = EvalViewCellsVolume(front, *frontData.mRays);
3173	backData.mProbability = EvalViewCellsVolume(back, *backData.mRays);
3174
3175
3176	//delete leaf;
3177	return node;
3178	}
3179
3180
3181	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
3182	SplitCandidate *splitCandidate,
3183	const bool globalCriteriaMet)
3184	{
3185	OspSplitCandidate sc = dynamic_cast<OspSplitCandidate >(splitCandidate);
3186	OspTraversalData &tData = sc->mParentData;
3187
3188	KdNode *newNode = tData.mNode;
3189
3190	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
3191	{
3192	OspTraversalData tFrontData;
3193	OspTraversalData tBackData;
3194
3195	//-- continue subdivision
3196
3197	// create new interior node and two leaf node
3198	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
3199
3200	newNode = SubdivideNode(splitPlane,
3201	tData,
3202	tFrontData,
3203	tBackData);
3204
3205	const int maxCostMisses = sc->mMaxCostMisses;
3206
3207	// how often was max cost ratio missed in this branch?
3208	tFrontData.mMaxCostMisses = maxCostMisses;
3209	tBackData.mMaxCostMisses = maxCostMisses;
3210
3211	mTotalCost -= sc->GetRenderCostDecrease();
3212
3213	// subdivision statistics
3214	if (1) EvalSubdivisionStats(*sc);
3215
3216	//-- push the new split candidates on the queue
3217
3218	OspSplitCandidate *frontCandidate = new OspSplitCandidate(tFrontData);
3219	OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData);
3220
3221	EvalSplitCandidate(*frontCandidate);
3222	EvalSplitCandidate(*backCandidate);
3223
3224	tQueue.Push(frontCandidate);
3225	tQueue.Push(backCandidate);
3226
3227	// delete old leaf node
3228	DEL_PTR(tData.mNode);
3229	}
3230
3231
3232	//-- terminate traversal
3233	if (newNode->IsLeaf())
3234	{
3235	EvaluateLeafStats(tData);
3236	}
3237
3238	//-- cleanup
3239	tData.Clear();
3240
3241	return newNode;
3242	}
3243
3244
3245	void OspTree::EvalSplitCandidate(OspSplitCandidate &splitCandidate)
3246	{
3247	float frontProb;
3248	float backProb;
3249
3250	// compute locally best split plane
3251	const bool success =
3252	SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
3253
3254	float oldRenderCost;
3255
3256	// compute global decrease in render cost
3257	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
3258	splitCandidate.mParentData,
3259	oldRenderCost);
3260
3261	splitCandidate.SetRenderCostDecrease(renderCostDecr);
3262
3263	#if 0
3264	const float priority = (float)-data.mDepth;
3265	#else
3266	// take render cost of node into account
3267	// otherwise danger of being stuck in a local minimum!!
3268	const float factor = mRenderCostDecreaseWeight;
3269	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
3270
3271	#endif
3272
3273	// compute global decrease in render cost
3274	splitCandidate.SetPriority(priority);
3275
3276	splitCandidate.mMaxCostMisses =
3277	success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
3278	}
3279
3280
3281	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
3282	{
3283	// matt: TODO
3284	return (
3285	//(data.mNode->mObjects.size() < mTermMinObjects) \|\|
3286	//(data.mProbability <= mTermMinProbability) \|\|
3287	(data.mDepth >= mTermMaxDepth)
3288	);
3289	}
3290
3291
3292	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
3293	{
3294	// matt: TODO
3295	return (
3296	(mOspStats.Leaves() >= mTermMaxLeaves)
3297	//mOutOfMemory \|\|
3298	//(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
3299	);
3300	}
3301
3302
3303	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
3304	{
3305	// the node became a leaf -> evaluate stats for leafs
3306	KdLeaf *leaf = data.mNode;
3307
3308	if (data.mPvs > mOspStats.maxPvs)
3309	{
3310	mOspStats.maxPvs = data.mPvs;
3311	}
3312
3313	mOspStats.pvs += data.mPvs;
3314
3315	if (data.mDepth < mOspStats.minDepth)
3316	{
3317	mOspStats.minDepth = data.mDepth;
3318	}
3319
3320	if (data.mDepth >= mTermMaxDepth)
3321	{
3322	++ mOspStats.maxDepthNodes;
3323	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
3324	}
3325
3326	// if (data.mPvs < mTermMinPvs)
3327	// ++ mOspStats.minPvsNodes;
3328
3329	if (data.mProbability <= mTermMinProbability)
3330	++ mOspStats.minProbabilityNodes;
3331
3332	// accumulate depth to compute average depth
3333	mOspStats.accumDepth += data.mDepth;
3334
3335	++ mCreatedLeaves;
3336
3337	#ifdef _DEBUG
3338	Debug << "BSP stats: "
3339	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
3340	// << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
3341	<< "Prob: " << data.mProbability << " (min: " << mTermMinProbability << "), "
3342	<< "#pvs: " << data.mPvs << ")\n";
3343	#endif
3344	}
3345
3346
3347	float OspTree::EvalLocalCostHeuristics(const OspTraversalData &tData,
3348	const AxisAlignedBox3 &box,
3349	const int axis,
3350	float &position,
3351	int &objectsFront,
3352	int &objectsBack)
3353	{
3354	RayInfoContainer usedRays;
3355	int mMaxTests = 500000; // HACK
3356
3357	if (mMaxTests < (int)tData.mRays->size())
3358	{
3359	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
3360	}
3361	else
3362	{
3363	usedRays = *tData.mRays;
3364	}
3365
3366	// go through the lists, count the number of objects left and right
3367	// and evaluate the following cost funcion:
3368	// C = ct_div_ci + (ol + or)/queries
3369
3370	const float minBox = box.Min(axis);
3371	const float maxBox = box.Max(axis);
3372
3373	const float sizeBox = maxBox - minBox;
3374
3375	float minBand = minBox + mSplitBorder * (maxBox - minBox);
3376	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
3377
3378	//-- sort so we can use a sweep
3379	SortSplitCandidates(tData, axis, minBand, maxBand);
3380
3381	int numViewCells;
3382
3383	float totalVol = PrepareHeuristics(tData, numViewCells);
3384	float voll = 0;
3385	float volr = totalVol;
3386
3387	int vcl = 0;
3388	int vcr = numViewCells;
3389
3390	/// this is kind of a reverse pvs
3391	const int totalPvs = (int)tData.mNode->mObjects.size();
3392
3393	int pvsl = 0;
3394	int pvsr = totalPvs;
3395
3396	float sum = (float)totalVol * sizeBox;
3397
3398	/////////////////////////////////
3399
3400	// note: initialised to take mid split
3401	// if no good split can be found,
3402	position = minBox + 0.5f * sizeBox;
3403
3404	// the relative cost ratio
3405	float ratio = 99999999.0f;
3406	bool splitPlaneFound = false;
3407
3408	float volBack = voll;
3409	float volFront = volr;
3410
3411	int pvsBack = pvsl;
3412	int pvsFront = pvsr;
3413
3414	float minSum = 1e20f;
3415
3416	debugVol = 0;
3417	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
3418
3419	/////////////////////////////
3420	// the sweep heuristics
3421
3422
3423	Intersectable::NewMail();
3424	ViewCell::NewMail();
3425
3426
3427	//-- traverse through events and find best split plane
3428
3429	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
3430
3431	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
3432	{
3433	Intersectable object = (ci).mObject;
3434
3435	EvalHeuristicsContribution(tData.mNode,
3436	*ci,
3437	voll, volr,
3438	pvsl, pvsr
3439	);
3440
3441	// Note: sufficient to compare size of bounding boxes of front and back side?
3442
3443	if (((ci).mPos >= minBand) && ((ci).mPos <= maxBand))
3444	{
3445	// voll = view cells that see only left node (i.e., left pvs)
3446	// volr = view cells that see only right node (i.e., right pvs)
3447	// rest = view cells that see both nodes (i.e., total pvs)
3448	sum = voll * pvsl + volr * pvsr + (totalVol - voll - volr) * totalPvs;
3449
3450	float currentPos;
3451
3452	// HACK: current positition is BETWEEN visibility events
3453	if (1 && ((*ci).mType == SortableEntry::BOX_INTERSECT) && ((ci + 1) != ci_end))
3454	currentPos = ((ci).mPos + ((ci + 1)).mPos) * 0.5f;
3455	else
3456	currentPos = (*ci).mPos;
3457
3458	/*if ((totalVol - voll - volr - debugVol) / viewSpaceVol > 0.0001)
3459	Debug << "front and back volume: " << (totalVol - voll - volr) / viewSpaceVol << " error: " << (totalVol - voll - volr - debugVol) / viewSpaceVol << endl;
3460	Debug << "pos: " << currentPos
3461	<< "\t (pvsl: " << pvsl << ", pvsr: " << pvsr << ")"
3462	<< "\t (voll: " << voll << ", volr: " << volr << ")"
3463	<< "\t (vcl: " << vcl << ", vcr: " << vcr << ", nvc: " << numViewCells << ")"
3464	<< "\t sum: " << sum << endl;
3465	*/
3466
3467	if (sum < minSum)
3468	{
3469	splitPlaneFound = true;
3470
3471	minSum = sum;
3472
3473	pvsBack = pvsl;
3474	pvsFront = pvsr;
3475
3476	volBack = voll;
3477	volFront = volr;
3478
3479	position = currentPos;
3480	}
3481	}
3482	}
3483
3484	//-- compute cost
3485	const float frontAndBackVol = totalVol - volFront - volBack;
3486
3487	const float oldRenderCost = (float)totalPvs * totalVol + Limits::Small;
3488	const float newRenderCost = (float)pvsFront * volFront +
3489	(float)pvsBack * volBack +
3490	(float)totalPvs * frontAndBackVol;
3491
3492
3493	if (splitPlaneFound)
3494	{
3495	ratio = newRenderCost / oldRenderCost;
3496	}
3497
3498	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos="
3499	// << position << " t=" << (position - minBox) / (maxBox - minBox)
3500	// << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
3501
3502	Debug << "\n§§§§ eval local cost §§§§" << endl
3503	<< "back pvs: " << pvsBack << " front pvs: " << pvsFront << " total pvs: " << totalPvs << endl
3504	<< "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
3505	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
3506	<< "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
3507
3508	if (oldRenderCost < newRenderCost)
3509	Debug << "\nwarning!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
3510
3511
3512	return ratio;
3513	}
3514
3515
3516	void OspTree::SortSplitCandidates(const OspTraversalData &tData,
3517	const int axis,
3518	float minBand,
3519	float maxBand)
3520
3521	{
3522	mSplitCandidates->clear();
3523
3524	RayInfoContainer *rays = tData.mRays;
3525	KdLeaf *leaf = tData.mNode;
3526
3527	int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
3528
3529	// creates a sorted split candidates array
3530	if (mSplitCandidates->capacity() > 500000 &&
3531	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
3532	{
3533	delete mSplitCandidates;
3534	mSplitCandidates = new vector<SortableEntry>;
3535	}
3536
3537	mSplitCandidates->reserve(requestedSize);
3538
3539	float pos;
3540
3541	//-- insert ray queries
3542	//-- we are intersested only in rays which intersect an object that
3543	//-- is part of the kd node because they can induce a change in view cell
3544	//-- volume on the left and the right part.
3545	//-- Note that they cannot induce a change in pvs size!!
3546
3547	RayInfoContainer::const_iterator rit, rit_end = rays->end();
3548
3549	for (rit = rays->begin(); rit < rit_end; ++ rit)
3550	{
3551	VssRay ray = (rit).mRay;
3552
3553	const bool positive = ray->HasPosDir(axis);
3554
3555	// if hitpoint with object is inside this node
3556	if (ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf))
3557	{
3558	pos = ray->mOrigin[axis];
3559
3560	mSplitCandidates->push_back(
3561	SortableEntry(SortableEntry::BOX_INTERSECT,
3562	pos,
3563	ray->mOriginObject,
3564	ray)
3565	);
3566	}
3567
3568	if (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
3569	{
3570	pos = ray->mTermination[axis];
3571
3572	mSplitCandidates->push_back(
3573	SortableEntry(SortableEntry::BOX_INTERSECT,
3574	pos,
3575	ray->mTerminationObject,
3576	ray)
3577	);
3578	}
3579	}
3580
3581
3582	//-- insert object queries
3583	//-- These queries can induce a change in pvs size.
3584	//-- Note that they cannot induce a change in view cell volume, as
3585	//-- there is no ray associated with these events!!
3586
3587	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
3588
3589	for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit )
3590	{
3591	Intersectable object = oit;
3592	const AxisAlignedBox3 box = object->GetBox();
3593
3594	mSplitCandidates->push_back(
3595	SortableEntry(SortableEntry::BOX_MIN,
3596	box.Min(axis),
3597	object,
3598	NULL)
3599	);
3600
3601
3602	mSplitCandidates->push_back(
3603	SortableEntry(SortableEntry::BOX_MAX,
3604	box.Max(axis),
3605	object,
3606	NULL)
3607	);
3608	}
3609
3610	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
3611	}
3612
3613
3614	const OspTreeStatistics &OspTree::GetStatistics() const
3615	{
3616	return mOspStats;
3617	}
3618
3619
3620	float OspTree::PrepareHeuristics(const VssRay &ray, int &numViewCells)
3621	{
3622	float vol = 0;
3623	numViewCells = 0;
3624
3625	ViewCellContainer viewCells;
3626
3627	mVspTree->GetViewCells(ray, viewCells);
3628
3629	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
3630
3631	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
3632	{
3633	ViewCell vc = (vit);
3634
3635	if (!vc->Mailed())
3636	{
3637	//Debug << "single vol: "<< vc->GetVolume() << endl;
3638	vc->Mail();
3639	vc->mCounter = 0;
3640	vol += vc->GetVolume();
3641	++ numViewCells;
3642	}
3643
3644	// view cell volume already added => just increase counter
3645	++ vc->mCounter;
3646	}
3647
3648	return vol;
3649	}
3650
3651
3652	float OspTree::PrepareHeuristics(const OspTraversalData &tData, int &numViewCells)
3653	{
3654	float vol = 0;
3655
3656	Intersectable::NewMail();
3657	ViewCell::NewMail();
3658	numViewCells = 0;
3659
3660	KdLeaf *leaf = tData.mNode;
3661
3662	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
3663
3664	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
3665	{
3666	VssRay ray = (rit).mRay;
3667
3668	int newViewCells;
3669
3670	// if hitpoint with one of the objects is inside this node, we
3671	// evaluate the volume of the view cells seen by this ray
3672	if (ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf))
3673	{
3674	vol += PrepareHeuristics(*ray, newViewCells);
3675	numViewCells += newViewCells;
3676	}
3677
3678	// count double if both hit points are within the kd node
3679	if (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
3680	{
3681	vol += PrepareHeuristics(*ray, newViewCells);
3682	numViewCells += newViewCells;
3683	}
3684	}
3685
3686	//Debug << "vol: " << vol << endl;
3687	return vol;
3688	}
3689
3690
3691	void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
3692	const SortableEntry &ci,
3693	float &volLeft,
3694	float &volRight,
3695	int &pvsLeft,
3696	int &pvsRight
3697	)
3698	{
3699	Intersectable *obj = ci.mObject;
3700	VssRay *ray = ci.mRay;
3701
3702	// switch between different types of events
3703	switch (ci.mType)
3704	{
3705	// add reverse pvs to left side of split plane
3706	case SortableEntry::BOX_MIN:
3707	++ pvsLeft;
3708	break;
3709
3710	case SortableEntry::BOX_MAX:
3711	-- pvsRight;
3712	break;
3713
3714	// compute volume contribution from view cells
3715	case SortableEntry::BOX_INTERSECT:
3716	// process ray if the hit point with termination / origin object
3717	// is inside this kd leaf
3718	if ((ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)) \|\|
3719	(ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)))
3720	{
3721	EvalVolumeContribution(*ray, volLeft, volRight);
3722	}
3723	break;
3724	default:
3725	cout << "should not come here" << endl;
3726	break;
3727	}
3728
3729	//cout << "vol left: " << volLeft << " vol right " << volRight << endl;
3730	}
3731
3732
3733	void OspTree::EvalVolumeContribution(const VssRay &ray,
3734	float &volLeft,
3735	float &volRight)
3736	{
3737	ViewCellContainer viewCells;
3738
3739	mVspTree->GetViewCells(ray, viewCells);
3740
3741	/// classify view cells and compute volume contri accordingly
3742	/// possible view cell classifications:
3743	/// view cell mailed => view cell can be seen from left child node
3744	/// view cell counter > 0 view cell can be seen from right child node
3745	/// combined: view cell volume belongs to both nodes
3746	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
3747
3748	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
3749	{
3750	// view cells can also be seen from left child node
3751	ViewCell viewCell = vit;
3752
3753	const float vol = viewCell->GetVolume();
3754
3755	if (!viewCell->Mailed())
3756	{
3757	viewCell->Mail();
3758
3759	// we now see view cell from both nodes
3760	// => remove ref to right child node
3761	volRight -= vol;
3762
3763	debugVol += vol;
3764	}
3765
3766	// last reference into the right node
3767	if (-- viewCell->mCounter == 0)
3768	{
3769	#if 0
3770	// view cell was previousy seen from right node only
3771	// => remove from right node (matt: need this?)
3772	if (!viewCell->Mailed())
3773	volRight -= vol;
3774	else
3775	#endif
3776	// view cell was previously seen from both nodes =>
3777	// contributes only to left node now
3778	volLeft += vol;
3779	debugVol -= vol;
3780	}
3781	}
3782	}
3783
3784
3785	void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
3786	{
3787	mViewCellsManager = vcm;
3788	}
3789
3790
3791	AxisAlignedBox3 OspTree::GetBoundingBox() const
3792	{
3793	return mBoundingBox;
3794	}
3795
3796
3797	float OspTree::SelectSplitPlane(const OspTraversalData &tData,
3798	AxisAlignedPlane &plane,
3799	float &pFront,
3800	float &pBack)
3801	{
3802	float nPosition[3];
3803	float nCostRatio[3];
3804	float nProbFront[3];
3805	float nProbBack[3];
3806
3807	// create bounding box of node geometry
3808	AxisAlignedBox3 box = tData.mBoundingBox;
3809
3810	int sAxis = 0;
3811	int bestAxis = -1;
3812
3813	if (mOnlyDrivingAxis)
3814	{
3815	sAxis = box.Size().DrivingAxis();
3816	}
3817
3818
3819	// -- evaluate split cost for all three axis
3820	for (int axis = 0; axis < 3; ++ axis)
3821	{
3822	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
3823	{
3824	if (1 \|\| mUseCostHeuristics)
3825	{
3826	//-- place split plane using heuristics
3827	int objectsFront, objectsBack;
3828
3829	nCostRatio[axis] =
3830	EvalLocalCostHeuristics(tData,
3831	tData.mBoundingBox,
3832	axis,
3833	nPosition[axis],
3834	objectsFront,
3835	objectsBack);
3836	}
3837	/* else
3838	{
3839	//-- split plane position is spatial median
3840
3841	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
3842
3843	nCostRatio[axis] = EvalLocalSplitCost(tData,
3844	box,
3845	axis,
3846	nPosition[axis],
3847	nProbFront[axis],
3848	nProbBack[axis]);
3849	}*/
3850
3851	if (bestAxis == -1)
3852	{
3853	bestAxis = axis;
3854	}
3855	else if (nCostRatio[axis] < nCostRatio[bestAxis])
3856	{
3857	bestAxis = axis;
3858	}
3859	}
3860	}
3861
3862	//-- assign values
3863
3864	plane.mAxis = bestAxis;
3865	// split plane position
3866	plane.mPosition = nPosition[bestAxis];
3867
3868	pFront = nProbFront[bestAxis];
3869	pBack = nProbBack[bestAxis];
3870
3871	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
3872	return nCostRatio[bestAxis];
3873	}
3874
3875
3876	bool OspTree::EndPointInsideNode(KdLeaf *leaf,
3877	VssRay &ray,
3878	bool isTermination) const
3879	{
3880	// test if the leaf where the hitpoint is located is the current leaf
3881	if (isTermination)
3882	{
3883	return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mOriginNode) == leaf);
3884	}
3885	else
3886	{
3887	return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
3888	}
3889	}
3890
3891
3892	void OspTree::EvalSubdivisionStats(const SplitCandidate &sc)
3893	{
3894	const float costDecr = sc.GetRenderCostDecrease();
3895
3896	AddSubdivisionStats(mOspStats.Leaves(),
3897	costDecr,
3898	mTotalCost
3899	);
3900	}
3901
3902
3903
3904	void OspTree::AddSubdivisionStats(const int leaves,
3905	const float renderCostDecr,
3906	const float totalRenderCost)
3907	{
3908	mSubdivisionStats
3909	<< "#Leaves\n" << leaves << endl
3910	<< "#RenderCostDecrease\n" << renderCostDecr << endl
3911	<< "#TotalRenderCost\n" << totalRenderCost << endl;
3912	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
3913	}
3914
3915
3916	int OspTree::ClassifyRay(VssRay *ray,
3917	KdLeaf *leaf,
3918	const AxisAlignedPlane &plane) const
3919	{
3920	const bool originInside = EndPointInsideNode(leaf, *ray, false);
3921	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
3922
3923	const bool originGt =
3924	ray->mOrigin[plane.mAxis] > plane.mPosition;
3925
3926	const bool terminationGt =
3927	ray->mTermination[plane.mAxis] > plane.mPosition;
3928
3929	// add view cell volume to front volume
3930	const bool addToFront = ((originInside && originGt) \|\| (terminationInside && terminationGt));
3931
3932	// add view cell volume to back volume
3933	const bool addToBack = ((originInside && !originGt) \|\| (terminationInside && !terminationGt));
3934
3935	// classify ray with respect to the child nodes the view cells contribute
3936	if (addToFront && addToBack)
3937	return 0;
3938	else if (addToBack)
3939	return -1;
3940	else if (addToFront)
3941	return 1;
3942
3943	return -2;
3944	}
3945
3946
3947	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
3948	const OspTraversalData &tData,
3949	float &normalizedOldRenderCost) const
3950	{
3951	float pvsFront = 0;
3952	float pvsBack = 0;
3953
3954	// probability that view point lies in back / front node
3955	float pOverall = 0;//data.mProbability; // todo matt§: value ok?
3956	float pFront = 0;
3957	float pBack = 0;
3958	float pFrontAndBack = 0;
3959
3960
3961	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
3962
3963	//Intersectable::NewMail();
3964	KdLeaf::NewMail();
3965	ViewCell::NewMail();
3966
3967	KdLeaf *leaf = tData.mNode;
3968	const int totalPvs = (int)leaf->mObjects.size();
3969
3970	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
3971
3972	// evaluate reverse pvs and view cell volume on left and right cell
3973	// note: should I take all leaf objects or rather the objects hit by rays?
3974	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
3975	{
3976	int pvsContri = 0;
3977
3978	Intersectable obj = oit;
3979	const AxisAlignedBox3 box = obj->GetBox();
3980
3981	// test if box falls in left / right child node
3982	if (box.Max(candidatePlane.mAxis) >= candidatePlane.mPosition)
3983	{
3984	++ pvsFront;
3985	}
3986
3987	if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
3988	{
3989	++ pvsBack;
3990	}
3991	}
3992
3993	// sum up volume seen from the objects of left and right children
3994	// => the volume is the weight for the render cost equation
3995	ViewCell::NewMail(3);
3996
3997	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
3998
3999	ViewCellContainer collectedViewCells;
4000
4001	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
4002	{
4003	VssRay ray = (rit).mRay;
4004
4005	// test if intersection point with one of the objects is inside this node
4006	const bool originInside = EndPointInsideNode(leaf, *ray, false);
4007	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
4008
4009	if (originInside \|\| terminationInside)
4010	{
4011	// add volume to volumes of left and / or right children
4012	// if one of the ray end points is inside
4013	const int classification = ClassifyRay(ray, leaf, candidatePlane);
4014
4015	ViewCellContainer viewCells;
4016	mVspTree->GetViewCells(*ray, viewCells);
4017
4018	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
4019
4020	// traverse through view cells and classify them according
4021	// to them being seen from to back / front / front and back node
4022	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
4023	{
4024	ViewCell vc = vit;
4025
4026	// if not previously mailed
4027	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
4028	collectedViewCells.push_back(vc);
4029
4030	// classify / mail the view cell
4031	MailViewCell(*vit, classification);
4032	}
4033	}
4034	}
4035
4036
4037	// evaluate view cells volume contribution with respect to the mail box classification
4038	ViewCellContainer::const_iterator vit, vit_end = collectedViewCells.end();
4039
4040	for (vit = collectedViewCells.begin(); vit != vit_end; ++ vit)
4041	{
4042	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
4043	}
4044
4045
4046	// these are non-overlapping sets
4047	pOverall = pFront + pBack + pFrontAndBack;
4048
4049
4050	//-- pvs rendering heuristics
4051
4052	const float oldRenderCost = pOverall * totalPvs;
4053
4054	// sum up the terms:
4055	// the view cells seeing
4056	// a) the left node are weighted by the #left node objects
4057	// b) the right node are weighted by the #right node objects
4058	// c) both nodes are weighted by the #parent node objects
4059	const float newRenderCost = pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack;
4060
4061	// normalize volume with view space volume
4062	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
4063
4064	Debug << "\n(((( eval render cost decrease ))))" << endl
4065	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
4066	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
4067	<< " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << tData.mProbability / viewSpaceVol << endl
4068	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
4069	<< "render cost decrease: " << renderCostDecrease << endl;
4070
4071	//if ((((pOverall - tData.mProbability) / viewSpaceVol) > 0.00001))
4072	// Debug << "ERROR!!"<<endl;
4073
4074	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
4075
4076
4077	return renderCostDecrease;
4078	}
4079
4080
4081	void OspTree::ComputeBoundingBox(const ObjectContainer &objects,
4082	AxisAlignedBox3 *forcedBoundingBox)
4083	{
4084	if (forcedBoundingBox)
4085	{
4086	mBoundingBox = *forcedBoundingBox;
4087	}
4088	else // compute vsp tree bounding box
4089	{
4090	mBoundingBox.Initialize();
4091
4092	ObjectContainer::const_iterator oit, oit_end = objects.end();
4093
4094	//-- compute bounding box
4095	for (oit = objects.begin(); oit != oit_end; ++ oit)
4096	{
4097	Intersectable obj = oit;
4098
4099	// compute bounding box of view space
4100	mBoundingBox.Include(obj->GetBox());
4101	mBoundingBox.Include(obj->GetBox());
4102	}
4103	}
4104	}
4105
4106
4107	void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
4108	{
4109	// find objects from multiple kd-leaves
4110	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
4111
4112	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
4113	{
4114	Intersectable object = oit;
4115
4116	if (object->mReferences > 1)
4117	{
4118	leaf->mMultipleObjects.push_back(object);
4119	}
4120	}
4121	}
4122
4123
4124	void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
4125	{
4126	stack<KdNode *> nodeStack;
4127	nodeStack.push(mRoot);
4128
4129	while (!nodeStack.empty())
4130	{
4131	KdNode *node = nodeStack.top();
4132	nodeStack.pop();
4133	if (node->IsLeaf())
4134	{
4135	KdLeaf leaf = (KdLeaf )node;
4136	leaves.push_back(leaf);
4137	}
4138	else
4139	{
4140	KdInterior interior = (KdInterior )node;
4141	nodeStack.push(interior->mBack);
4142	nodeStack.push(interior->mFront);
4143	}
4144	}
4145	}
4146
4147
4148	AxisAlignedBox3 OspTree::GetBoundingBox(KdNode *node) const
4149	{
4150	if (!node->mParent)
4151	return mBoundingBox;
4152
4153	if (!node->IsLeaf())
4154	{
4155	return (dynamic_cast<KdInterior *>(node))->mBox;
4156	}
4157
4158	KdInterior parent = dynamic_cast<KdInterior >(node->mParent);
4159
4160	AxisAlignedBox3 box(parent->mBox);
4161
4162	if (parent->mFront == node)
4163	box.SetMin(parent->mAxis, parent->mPosition);
4164	else
4165	box.SetMax(parent->mAxis, parent->mPosition);
4166
4167	return box;
4168	}
4169
4170
4171	void OspTree::CollectViewCells(KdLeaf *leaf, ViewCellContainer &viewCells)
4172	{
4173	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
4174
4175	ViewCell::NewMail();
4176
4177	// loop through all object and collect view cell pvs of this node
4178	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
4179	{
4180	Intersectable obj = oit;
4181
4182	ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
4183
4184	for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
4185	{
4186	ViewCell vc = (vit).first;
4187
4188	if (!vc->Mailed())
4189	{
4190	vc->Mail();
4191	viewCells.push_back(vc);
4192	}
4193	}
4194	}
4195	}
4196
4197
4198	void OspTree::CollectDirtyCandidates(OspSplitCandidate *sc,
4199	vector<SplitCandidate *> &dirtyList)
4200	{
4201	OspTraversalData &tData = sc->mParentData;
4202	KdLeaf *node = tData.mNode;
4203
4204	ViewCell::NewMail();
4205	ViewCellContainer viewCells;
4206	ViewCellContainer tmpViewCells;
4207
4208	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
4209
4210	// find all view cells associated with the rays, add them to view cells
4211	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
4212	{
4213	VssRay ray = (rit).mRay;
4214	mVspTree->GetViewCells(*ray, tmpViewCells);
4215
4216	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
4217
4218	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
4219	{
4220	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
4221
4222	if (!vc->Mailed())
4223	{
4224	vc->Mail();
4225	viewCells.push_back(vc);
4226	}
4227	}
4228	}
4229
4230
4231	// split candidates holding this view cells
4232	// are thrown into dirty list
4233	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
4234
4235	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
4236	{
4237	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
4238
4239	VspLeaf *leaf = vc->mLeaf;
4240	dirtyList.push_back(leaf->GetSplitCandidate());
4241	}
4242	}
4243
4244
4245	KdNode *OspTree::GetRoot() const
4246	{
4247	return mRoot;
4248	}
4249
4250
4251	KdLeaf OspTree::GetLeaf(const Vector3 &pt, KdNode node) const
4252	{
4253	// start from root of tree
4254	if (node == NULL)
4255	{
4256	node = mRoot;
4257	}
4258
4259	stack<KdNode *> nodeStack;
4260	nodeStack.push(node);
4261
4262	KdLeaf *leaf = NULL;
4263
4264	while (!nodeStack.empty())
4265	{
4266	KdNode *node = nodeStack.top();
4267	nodeStack.pop();
4268
4269	if (node->IsLeaf())
4270	{
4271	leaf = dynamic_cast<KdLeaf *>(node);
4272	}
4273	else
4274	{
4275	// find point
4276	KdInterior interior = dynamic_cast<KdInterior >(node);
4277
4278	if (interior->mPosition > pt[interior->mAxis])
4279	{
4280	nodeStack.push(interior->mBack);
4281	}
4282	else
4283	{
4284	nodeStack.push(interior->mFront);
4285	}
4286	}
4287	}
4288
4289	return leaf;
4290	}
4291
4292
4293	void OspTree::PreprocessRays(const VssRayContainer &sampleRays,
4294	RayInfoContainer &rays)
4295	{
4296	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
4297
4298	long startTime = GetTime();
4299
4300	cout << "storing rays ... ";
4301
4302	Intersectable::NewMail();
4303
4304	//-- store rays and objects
4305	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
4306	{
4307	VssRay ray = rit;
4308
4309	float minT, maxT;
4310	static Ray hray;
4311
4312	hray.Init(*ray);
4313
4314	// TODO: not very efficient to implictly cast between rays types
4315	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
4316	{
4317	float len = ray->Length();
4318
4319	if (!len)
4320	len = Limits::Small;
4321
4322	rays.push_back(RayInfo(ray, minT / len, maxT / len));
4323
4324	// HACK: reset nodes for the case we have used object kd tree for
4325	// tree building.
4326	ray->mOrigin = NULL;
4327	ray->mTerminationNode = NULL;
4328	}
4329	}
4330
4331	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4332	}
4333
4334
4335
4336	int OspTree::SplitRays(const AxisAlignedPlane &plane,
4337	RayInfoContainer &rays,
4338	RayInfoContainer &frontRays,
4339	RayInfoContainer &backRays) const
4340	{
4341	int splits = 0;
4342
4343	RayInfoContainer::const_iterator rit, rit_end = rays.end();
4344
4345	for (rit = rays.begin(); rit != rit_end; ++ rit)
4346	{
4347	RayInfo bRay = *rit;
4348
4349	VssRay *ray = bRay.mRay;
4350	float t;
4351
4352	// get classification and receive new t
4353	//-- test if start point behind or in front of plane
4354	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
4355
4356	if (side == 0)
4357	{
4358	++ splits;
4359
4360	if (ray->HasPosDir(plane.mAxis))
4361	{
4362	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
4363	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
4364	}
4365	else
4366	{
4367	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
4368	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
4369	}
4370	}
4371	else if (side == 1)
4372	{
4373	frontRays.push_back(bRay);
4374	}
4375	else
4376	{
4377	backRays.push_back(bRay);
4378	}
4379	}
4380
4381	return splits;
4382	}
4383
4384
4385	KdIntersectable OspTree::GetOrCreateKdIntersectable(KdNode node)
4386	{
4387	// search nodes
4388	std::map<KdNode , KdIntersectable >::
4389	const_iterator it = mKdIntersectables.find(node);
4390
4391	if (it != mKdIntersectables.end())
4392	{
4393	return (*it).second;
4394	}
4395
4396	// not in map => create new entry
4397	KdIntersectable *kdObj= new KdIntersectable(node);
4398
4399	mKdIntersectables[node] = kdObj;
4400
4401	return kdObj;
4402	}
4403
4404
4405	/*
4406	void OspTree::AddViewCellVolume(ViewCell *vc,
4407	const int cf,
4408	float &frontVol,
4409	float &backVol,
4410	float &totalVol) const
4411	{
4412	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
4413	const float vol = vc->GetVolume();
4414
4415	// view cell not found yet => new
4416	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
4417	{
4418	totalVol += vol;
4419	}
4420
4421	if (cf >= 0) // front volume
4422	{
4423	if (!vc->Mailed() && !vc->Mailed(2))
4424	{
4425	frontVol += vol;
4426
4427	// already in back volume => in both volumes
4428	if (vc->Mailed(1))
4429	vc->Mail(2);
4430	else
4431	vc->Mail();
4432	}
4433	}
4434
4435	if (cf <= 0) // back volume
4436	{
4437	if (!vc->Mailed(1) && !vc->Mailed(2))
4438	{
4439	backVol += vol;
4440
4441	// already in front volume => in both volume
4442	if (vc->Mailed())
4443	vc->Mail(2);
4444	else
4445	vc->Mail(1);
4446	}
4447	}
4448	}
4449	*/
4450	void OspTree::MailViewCell(ViewCell *vc, const int cf) const
4451	{
4452	if (vc->Mailed(2)) // already classified
4453	return;
4454
4455	if (cf >= 0) // front volume
4456	{
4457	// already in back volume => in both volumes
4458	if (vc->Mailed(1))
4459	{
4460	vc->Mail(2);
4461	}
4462	else
4463	{
4464	vc->Mail();
4465	}
4466	}
4467
4468	if (cf <= 0) // back volume
4469	{
4470	// already in front volume => in both volume
4471	if (vc->Mailed())
4472	{
4473	vc->Mail(2);
4474	}
4475	else
4476	{
4477	vc->Mail(1);
4478	}
4479	}
4480	}
4481
4482
4483	void OspTree::AddViewCellVolumeContri(ViewCell *vc,
4484	float &frontVol,
4485	float &backVol,
4486	float &frontAndBackVol) const
4487	{
4488	if (vc->Mailed())
4489	{
4490	frontVol += vc->GetVolume();
4491	}
4492	else if (vc->Mailed(1))
4493	{
4494	backVol += vc->GetVolume();
4495	}
4496	else if (vc->Mailed(2))
4497	{
4498	frontAndBackVol += vc->GetVolume();
4499	}
4500	}
4501
4502
4503	float OspTree::EvalViewCellsVolume(KdLeaf *leaf, const RayInfoContainer &rays) const
4504	{
4505	float vol = 0;
4506	ViewCell::NewMail();
4507
4508	RayInfoContainer::const_iterator rit, rit_end = rays.end();
4509
4510	for (rit = rays.begin(); rit != rays.end(); ++ rit)
4511	{
4512	VssRay ray = (rit).mRay;
4513
4514	// process ray if the hit point with termination / origin object
4515	// is inside this kd leaf
4516	if (!((ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)) \|\|
4517	(ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))))
4518	continue;
4519
4520	ViewCellContainer viewCells;
4521	mVspTree->CastLineSegment(ray->mOrigin, ray->mTermination, viewCells);
4522
4523	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
4524
4525	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
4526	{
4527	ViewCell vc = vit;
4528
4529	if (!vc->Mailed())
4530	{
4531	vc->Mail();
4532	vol += vc->GetVolume();
4533	}
4534	}
4535	}
4536
4537	return vol;
4538	}
4539
4540
4541	/********************************************************************/
4542	/* class HierarchyManager implementation */
4543	/********************************************************************/
4544
4545
4546	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
4547	mVspTree(vspTree), mOspTree(ospTree)
4548	{
4549	// cross references
4550	mVspTree.mOspTree = &ospTree;
4551	mOspTree.mVspTree = &vspTree;
4552
4553	char subdivisionStatsLog[100];
4554	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
4555	mSubdivisionStats.open(subdivisionStatsLog);
4556	}
4557
4558
4559	SplitCandidate *HierarchyManager::NextSplitCandidate()
4560	{
4561	SplitCandidate *splitCandidate = mTQueue.Top();
4562	mTQueue.Pop();
4563
4564	return splitCandidate;
4565	}
4566
4567
4568	VspTree::VspSplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
4569	AxisAlignedBox3 *forcedViewSpace,
4570	RayInfoContainer &rays)
4571	{
4572	// store pointer to this tree
4573	VspTree::VspSplitCandidate::sVspTree = &mVspTree;
4574	mVspTree.mVspStats.nodes = 1;
4575
4576	// compute view space bounding box
4577	mVspTree.ComputeBoundingBox(sampleRays, forcedViewSpace);
4578
4579	// initialise termination criteria
4580	mVspTree.mTermMinProbability *= mBoundingBox.GetVolume();
4581	mVspTree.mGlobalCostMisses = 0;
4582
4583	// get clipped rays
4584	mVspTree.PreprocessRays(sampleRays, rays);
4585
4586	const int pvsSize = mVspTree.EvalPvsSize(rays);
4587
4588	Debug << "pvs size: " << (int)pvsSize << endl;
4589	Debug << "rays size: " << (int)rays.size() << endl;
4590
4591	//-- prepare view space partition
4592
4593	// add first candidate for view space partition
4594	VspLeaf *leaf = new VspLeaf();
4595	mVspTree.mRoot = leaf;
4596
4597	const float prop = mVspTree.mBoundingBox.GetVolume();
4598
4599	// first vsp traversal data
4600	VspTree::VspTraversalData vData(leaf,
4601	0,
4602	&rays,
4603	pvsSize,
4604	prop,
4605	mVspTree.mBoundingBox);
4606
4607	// create first view cell
4608	mVspTree.CreateViewCell(vData, false);
4609
4610	#if WORK_WITH_VIEWCELL_PVS
4611
4612	// add first view cell to all the objects view cell pvs
4613	ObjectPvsMap::const_iterator oit,
4614	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
4615
4616
4617	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
4618	{
4619	Intersectable obj = (oit).first;
4620	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
4621	}
4622	#endif
4623
4624	// compute first split candidate
4625	VspTree::VspSplitCandidate *splitCandidate =
4626	new VspTree::VspSplitCandidate(vData);
4627	mVspTree.EvalSplitCandidate(*splitCandidate);
4628
4629	mVspTree.mTotalCost = (float)pvsSize;
4630	mVspTree.EvalSubdivisionStats(*splitCandidate);
4631
4632	return splitCandidate;
4633	}
4634
4635
4636	OspTree::OspSplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
4637	const ObjectContainer &objects,
4638	AxisAlignedBox3 *forcedObjectSpace,
4639	RayInfoContainer &rays)
4640	{
4641	// store pointer to this tree
4642	OspTree::OspSplitCandidate::sOspTree = &mOspTree;
4643	mOspTree.mOspStats.nodes = 1;
4644
4645	// compute bounding box from objects
4646	mOspTree.ComputeBoundingBox(objects, forcedObjectSpace);
4647
4648	mOspTree.mTermMinProbability *= mBoundingBox.GetVolume();
4649	mGlobalCostMisses = 0;
4650
4651	// get clipped rays
4652	mOspTree.PreprocessRays(sampleRays, rays);
4653
4654	// create new root
4655	KdLeaf *kdleaf = new KdLeaf(NULL, 0);
4656	kdleaf->mObjects = objects;
4657	mOspTree.mRoot = kdleaf;
4658
4659	const float prop = mOspTree.EvalViewCellsVolume(kdleaf, rays);
4660
4661	//-- add first candidate for view space partition
4662
4663	// first osp traversal data
4664	OspTree::OspTraversalData oData(kdleaf,
4665	0,
4666	&rays,
4667	(int)objects.size(),
4668	prop,
4669	mOspTree.mBoundingBox);
4670
4671
4672	// compute first split candidate
4673	OspTree::OspSplitCandidate *oSplitCandidate =
4674	new OspTree::OspSplitCandidate(oData);
4675
4676	mOspTree.EvalSplitCandidate(*oSplitCandidate);
4677
4678	mOspTree.mTotalCost = (float)objects.size() * prop / mVspTree.GetBoundingBox().GetVolume();
4679	mOspTree.EvalSubdivisionStats(*oSplitCandidate);
4680
4681	return oSplitCandidate;
4682	}
4683
4684
4685	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
4686	const ObjectContainer &objects,
4687	AxisAlignedBox3 *forcedViewSpace,
4688	RayInfoContainer &viewSpaceRays,
4689	RayInfoContainer &objectSpaceRays)
4690	{
4691	SplitCandidate *vsc =
4692	PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
4693	mTQueue.Push(vsc);
4694
4695	SplitCandidate *osc =
4696	PrepareOsp(sampleRays, objects, forcedViewSpace, objectSpaceRays);
4697
4698	mTQueue.Push(osc);
4699	}
4700
4701
4702	void HierarchyManager::EvalSubdivisionStats(const SplitCandidate &tData)
4703	{
4704	const float costDecr = tData.GetRenderCostDecrease();
4705
4706	//mTotalCost -= costDecr;
4707	// mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
4708
4709	AddSubdivisionStats(mOspTree.mOspStats.Leaves() + mVspTree.mVspStats.Leaves(),
4710	costDecr,
4711	mTotalCost
4712	);
4713	}
4714
4715
4716	void HierarchyManager::AddSubdivisionStats(const int splits,
4717	const float renderCostDecr,
4718	const float totalRenderCost)
4719	{
4720	mSubdivisionStats
4721	<< "#Splits\n" << splits << endl
4722	<< "#RenderCostDecrease\n" << renderCostDecr << endl
4723	<< "#TotalRenderCost\n" << totalRenderCost << endl;
4724	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
4725	}
4726
4727
4728	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
4729	{
4730	// TODO matt: make virtual by creating superclasss for traveral data
4731	return candidate->GlobalTerminationCriteriaMet();
4732	}
4733
4734
4735	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
4736	const ObjectContainer &objects,
4737	AxisAlignedBox3 *forcedViewSpace)
4738	{
4739	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
4740	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
4741
4742	// prepare vsp and osp trees for traversal
4743	PrepareConstruction(sampleRays, objects, forcedViewSpace, viewSpaceRays, objectSpaceRays);
4744
4745	mVspTree.mVspStats.Reset();
4746	mVspTree.mVspStats.Start();
4747
4748	cout << "Constructing view space / object space tree ... \n";
4749	const long startTime = GetTime();
4750
4751	RunConstruction(true);
4752
4753	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
4754
4755	mVspTree.mVspStats.Stop();
4756	}
4757
4758
4759	bool HierarchyManager::SubdivideSplitCandidate(SplitCandidate *sc)
4760	{
4761	const bool globalTerminationCriteriaMet =
4762	GlobalTerminationCriteriaMet(sc);
4763
4764	const bool vspSplit = (sc->Type() == SplitCandidate::VIEW_SPACE);
4765
4766	if (vspSplit)
4767	{
4768	VspNode *n = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
4769	}
4770	else
4771	{
4772	KdNode *n = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
4773	}
4774
4775	return !globalTerminationCriteriaMet;
4776	}
4777
4778
4779	void HierarchyManager::RunConstruction(const bool repair)
4780	{
4781	int numNodes = 0;
4782
4783	while (!FinishedConstruction())
4784	{
4785	SplitCandidate *splitCandidate = NextSplitCandidate();
4786
4787	mTotalCost -= splitCandidate->GetRenderCostDecrease();
4788
4789	// cost ratio of cost decrease / totalCost
4790	const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
4791
4792	if (costRatio < mTermMinGlobalCostRatio)
4793	++ mGlobalCostMisses;
4794
4795	Debug << "\n**********" << endl
4796	<< "total cost: " << mTotalCost << " render cost decr: "
4797	<< splitCandidate->GetRenderCostDecrease()
4798	<< " cost ratio: " << costRatio << endl << endl;
4799
4800	//-- subdivide leaf node
4801
4802	if (SubdivideSplitCandidate(splitCandidate))
4803	{
4804	// subdivision successful
4805	EvalSubdivisionStats(*splitCandidate);
4806
4807	// reevaluate candidates affected by the split
4808	// for view space splits, this would be object space splits
4809	// and other way round
4810	if (repair)
4811	RepairQueue();
4812
4813	cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
4814	}
4815
4816	DEL_PTR(splitCandidate);
4817	}
4818	}
4819
4820
4821	void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
4822	const ObjectContainer &objects,
4823	AxisAlignedBox3 *forcedViewSpace)
4824	{
4825	// rays clipped in view space and in object space
4826	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
4827	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
4828
4829
4830	/////////////////////////////////////////////////////////////
4831	// view space space partition
4832	/////////////////////////////////////////////////////////////
4833
4834	#if 0
4835	// makes no sense otherwise because only one kd cell available
4836	// during view space partition
4837	const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
4838	const bool savedStoreMethod = mVspTree.mStoreKdPvs;
4839
4840	mVspTree.mUseKdPvsForHeuristics = false;
4841	mVspTree.mStoreKdPvs = false;
4842	#endif
4843
4844	VspTree::VspSplitCandidate *vsc =
4845	PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
4846
4847	// add to queue
4848	mTQueue.Push(vsc);
4849
4850	long startTime = GetTime();
4851	cout << "starting vsp contruction ... " << endl;
4852
4853	mVspTree.mVspStats.Reset();
4854	mVspTree.mVspStats.Start();
4855
4856	int i = 0;
4857
4858	// all objects can be seen from everywhere
4859	mTotalCost = (float)vsc->mParentData.mPvs;
4860
4861	const bool repairQueue = false;
4862
4863	// process view space candidates
4864	RunConstruction(repairQueue);
4865
4866	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
4867	mVspTree.mVspStats.Stop();
4868
4869
4870
4871	/////////////////////////////////////////////////////////////
4872	// object space partition
4873	/////////////////////////////////////////////////////////////
4874
4875	Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
4876	cout << "starting osp contruction ... " << endl;
4877
4878	// compute first candidate
4879	OspTree::OspSplitCandidate *osc =
4880	PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
4881
4882	mTQueue.Push(osc);
4883
4884	mOspTree.mOspStats.Reset();
4885	mOspTree.mOspStats.Start();
4886
4887	startTime = GetTime();
4888
4889	// reset cost
4890	// start with one big kd cell - all objects can be seen from everywhere
4891	// note: only true for view space = object space
4892	mTotalCost = (float)osc->mParentData.mNode->mObjects.size();//(float)sc->mParentData.mPvs;
4893
4894	Debug << "reseting cost, new total cost: " << mTotalCost << endl;
4895
4896	// process object space candidates
4897	RunConstruction(repairQueue);
4898
4899	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4900
4901	mOspTree.mOspStats.Stop();
4902
4903	#if 0
4904	// reset parameters
4905	mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
4906	mVspTree.mStoreKdPvs = savedStoreMethod;
4907	#endif
4908	}
4909
4910
4911	void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
4912	const ObjectContainer &objects,
4913	AxisAlignedBox3 *forcedViewSpace)
4914	{
4915	// only view space partition
4916	// object kd tree is taken for osp
4917
4918	mVspTree.mVspStats.Reset();
4919	mVspTree.mVspStats.Start();
4920
4921	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
4922
4923	SplitCandidate sc = PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
4924	mTQueue.Push(sc);
4925
4926	cout << "starting vsp contruction ... " << endl;
4927
4928	long startTime = GetTime();
4929
4930	RunConstruction(false);
4931
4932	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
4933	mVspTree.mVspStats.Stop();
4934	}
4935
4936
4937	bool HierarchyManager::FinishedConstruction() const
4938	{
4939	return mTQueue.Empty();
4940	}
4941
4942
4943	void HierarchyManager::CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList)
4944	{
4945	// we have either a object space or view space split
4946	if (mCurrentCandidate->Type() == SplitCandidate::VIEW_SPACE)
4947	{
4948	VspTree::VspSplitCandidate *sc =
4949	dynamic_cast<VspTree::VspSplitCandidate *>(mCurrentCandidate);
4950
4951	mVspTree.CollectDirtyCandidates(sc, dirtyList);
4952	}
4953	else // object space split
4954	{
4955	OspTree::OspSplitCandidate *sc =
4956	dynamic_cast<OspTree::OspSplitCandidate *>(mCurrentCandidate);
4957
4958	mOspTree.CollectDirtyCandidates(sc, dirtyList);
4959	}
4960	}
4961
4962
4963	void HierarchyManager::RepairQueue()
4964	{
4965	// TODO
4966	// for each update of the view space partition:
4967	// the candidates from object space partition which
4968	// have been afected by the view space split (the kd split candidates
4969	// which saw the view cell which was split) must be reevaluated
4970	// (maybe not locally, just reinsert them into the queue)
4971	//
4972	// vice versa for the view cells
4973	// for each update of the object space partition
4974	// reevaluate split candidate for view cells which saw the split kd cell
4975	//
4976	// the priority queue update can be solved by implementing a binary heap
4977	// (explicit data structure, binary tree)
4978	// *) inserting and removal is efficient
4979	// *) search is not efficient => store queue position with each
4980	// split candidate
4981
4982	// collect list of "dirty" candidates
4983	vector<SplitCandidate *> dirtyList;
4984	CollectDirtyCandidates(dirtyList);
4985
4986	//-- reevaluate the dirty list
4987	vector<SplitCandidate *>::const_iterator sit, sit_end = dirtyList.end();
4988
4989	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
4990	{
4991	SplitCandidate* sc = *sit;
4992
4993	mTQueue.Erase(sc);
4994
4995	// reevaluate
4996	sc->EvalPriority();
4997
4998	// reinsert
4999	mTQueue.Push(sc);
5000	}
5001	}
5002
5003	}

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

Download in other formats: