Context Navigation

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

Revision 1233, 146.3 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: