Context Navigation

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

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

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

Download in other formats: