Context Navigation

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

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

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

Download in other formats: