Context Navigation

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

Revision 1189, 143.1 KB checked in by mattausch, 18 years ago (diff)
changed osp partition to something taking mult references into account

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

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

Download in other formats: