Context Navigation

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

Revision 1551, 71.3 KB checked in by mattausch, 18 years ago (diff)
updated view cells loading. probably no optimal for performance

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->mLeaves.push_back(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	ViewCell *outOfBounds = GetOrCreateOutOfBoundsCell();
1859	outOfBounds->GetPvs().AddPvs(viewCell->GetPvs());
1860	DEL_PTR(viewCell);
1861	}
1862	}
1863	else
1864	{
1865	VspInterior interior = dynamic_cast<VspInterior >(node);
1866
1867	nodeStack.push(interior->GetFront());
1868	nodeStack.push(interior->GetBack());
1869	}
1870	}
1871
1872	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1873	#endif
1874	}
1875
1876
1877	void VspTree::CollectRays(VssRayContainer &rays)
1878	{
1879	vector<VspLeaf *> leaves;
1880	CollectLeaves(leaves);
1881
1882	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1883
1884	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1885	{
1886	VspLeaf leaf = lit;
1887	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1888
1889	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1890	rays.push_back(*rit);
1891	}
1892	}
1893
1894
1895	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1896	{
1897	mViewCellsManager = vcm;
1898	}
1899
1900
1901	void VspTree::ValidateTree()
1902	{
1903	if (!mRoot)
1904	return;
1905
1906	mVspStats.invalidLeaves = 0;
1907	stack<VspNode *> nodeStack;
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	if (!root)
1950	return;
1951
1952	stack<VspNode *> nodeStack;
1953	nodeStack.push(root);
1954
1955	while (!nodeStack.empty())
1956	{
1957	VspNode *node = nodeStack.top();
1958	nodeStack.pop();
1959
1960	if (node->IsLeaf())
1961	{
1962	if (!onlyValid \|\| node->TreeValid())
1963	{
1964	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
1965
1966	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
1967
1968	if (!onlyUnmailed \|\| !viewCell->Mailed())
1969	{
1970	viewCell->Mail();
1971	viewCells.push_back(viewCell);
1972	}
1973	}
1974	}
1975	else
1976	{
1977	VspInterior interior = dynamic_cast<VspInterior >(node);
1978
1979	nodeStack.push(interior->GetFront());
1980	nodeStack.push(interior->GetBack());
1981	}
1982	}
1983	}
1984
1985
1986	int VspTree::FindNeighbors(VspLeaf *n,
1987	vector<VspLeaf *> &neighbors,
1988	const bool onlyUnmailed) const
1989	{
1990	stack<VspNode *> nodeStack;
1991	nodeStack.push(mRoot);
1992
1993	const AxisAlignedBox3 box = GetBoundingBox(n);
1994
1995	while (!nodeStack.empty())
1996	{
1997	VspNode *node = nodeStack.top();
1998	nodeStack.pop();
1999
2000	if (node->IsLeaf())
2001	{
2002	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2003
2004	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
2005	neighbors.push_back(leaf);
2006	}
2007	else
2008	{
2009	VspInterior interior = dynamic_cast<VspInterior >(node);
2010
2011	if (interior->GetPosition() > box.Max(interior->GetAxis()))
2012	nodeStack.push(interior->GetBack());
2013	else
2014	{
2015	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2016	nodeStack.push(interior->GetFront());
2017	else
2018	{
2019	// random decision
2020	nodeStack.push(interior->GetBack());
2021	nodeStack.push(interior->GetFront());
2022	}
2023	}
2024	}
2025	}
2026
2027	return (int)neighbors.size();
2028	}
2029
2030
2031	// Find random neighbor which was not mailed
2032	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2033	{
2034	stack<VspNode *> nodeStack;
2035	nodeStack.push(mRoot);
2036
2037	int mask = rand();
2038
2039	while (!nodeStack.empty())
2040	{
2041	VspNode *node = nodeStack.top();
2042
2043	nodeStack.pop();
2044
2045	if (node->IsLeaf())
2046	{
2047	return dynamic_cast<VspLeaf *>(node);
2048	}
2049	else
2050	{
2051	VspInterior interior = dynamic_cast<VspInterior >(node);
2052	VspNode *next;
2053
2054	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2055	{
2056	next = interior->GetFront();
2057	}
2058	else
2059	{
2060	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2061	{
2062	next = interior->GetBack();
2063	}
2064	else
2065	{
2066	// random decision
2067	if (mask & 1)
2068	next = interior->GetBack();
2069	else
2070	next = interior->GetFront();
2071	mask = mask >> 1;
2072	}
2073	}
2074
2075	nodeStack.push(next);
2076	}
2077	}
2078
2079	return NULL;
2080	}
2081
2082
2083	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2084	{
2085	stack<VspNode *> nodeStack;
2086
2087	nodeStack.push(mRoot);
2088
2089	int mask = rand();
2090
2091	while (!nodeStack.empty())
2092	{
2093	VspNode *node = nodeStack.top();
2094	nodeStack.pop();
2095
2096	if (node->IsLeaf())
2097	{
2098	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2099	return dynamic_cast<VspLeaf *>(node);
2100	}
2101	else
2102	{
2103	VspInterior interior = dynamic_cast<VspInterior >(node);
2104
2105	// random decision
2106	if (mask & 1)
2107	nodeStack.push(interior->GetBack());
2108	else
2109	nodeStack.push(interior->GetFront());
2110
2111	mask = mask >> 1;
2112	}
2113	}
2114
2115	return NULL;
2116	}
2117
2118
2119	int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
2120	{
2121	int pvsSize = 0;
2122
2123	Intersectable::NewMail();
2124	KdNode::NewMail();
2125	BvhLeaf::NewMail();
2126
2127	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2128
2129	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2130	{
2131	VssRay ray = (rit).mRay;
2132
2133	pvsSize += EvalContributionToPvs(*ray, true);
2134	pvsSize += EvalContributionToPvs(*ray, false);
2135	}
2136
2137	return pvsSize;
2138	}
2139
2140
2141	float VspTree::GetEpsilon() const
2142	{
2143	return mEpsilon;
2144	}
2145
2146
2147	int VspTree::CastLineSegment(const Vector3 &origin,
2148	const Vector3 &termination,
2149	ViewCellContainer &viewcells,
2150	const bool useMailboxing)
2151	{
2152	int hits = 0;
2153
2154	float mint = 0.0f, maxt = 1.0f;
2155	const Vector3 dir = termination - origin;
2156
2157	stack<LineTraversalData> tStack;
2158
2159	Vector3 entp = origin;
2160	Vector3 extp = termination;
2161
2162	VspNode *node = mRoot;
2163	VspNode *farChild;
2164
2165	float position;
2166	int axis;
2167
2168	while (1)
2169	{
2170	if (!node->IsLeaf())
2171	{
2172	VspInterior in = dynamic_cast<VspInterior >(node);
2173	position = in->GetPosition();
2174	axis = in->GetAxis();
2175
2176	if (entp[axis] <= position)
2177	{
2178	if (extp[axis] <= position)
2179	{
2180	node = in->GetBack();
2181	// cases N1,N2,N3,P5,Z2,Z3
2182	continue;
2183	} else
2184	{
2185	// case N4
2186	node = in->GetBack();
2187	farChild = in->GetFront();
2188	}
2189	}
2190	else
2191	{
2192	if (position <= extp[axis])
2193	{
2194	node = in->GetFront();
2195	// cases P1,P2,P3,N5,Z1
2196	continue;
2197	}
2198	else
2199	{
2200	node = in->GetFront();
2201	farChild = in->GetBack();
2202	// case P4
2203	}
2204	}
2205
2206	// $$ modification 3.5.2004 - hints from Kamil Ghais
2207	// case N4 or P4
2208	const float tdist = (position - origin[axis]) / dir[axis];
2209	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2210
2211	extp = origin + dir * tdist;
2212	maxt = tdist;
2213	}
2214	else
2215	{
2216	// compute intersection with all objects in this leaf
2217	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2218	ViewCell *vc = leaf->GetViewCell();
2219
2220	// don't have to mail if each view cell belongs to exactly one leaf
2221	if (!useMailboxing \|\| !vc->Mailed())
2222	{
2223	if (useMailboxing)
2224	vc->Mail();
2225
2226	viewcells.push_back(vc);
2227	++ hits;
2228	}
2229	#if 0
2230	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2231	#endif
2232	// get the next node from the stack
2233	if (tStack.empty())
2234	break;
2235
2236	entp = extp;
2237	mint = maxt;
2238
2239	LineTraversalData &s = tStack.top();
2240	node = s.mNode;
2241	extp = s.mExitPoint;
2242	maxt = s.mMaxT;
2243	tStack.pop();
2244	}
2245	}
2246
2247	return hits;
2248	}
2249
2250
2251	int VspTree::CastRay(Ray &ray)
2252	{
2253	int hits = 0;
2254
2255	stack<LineTraversalData> tStack;
2256	const Vector3 dir = ray.GetDir();
2257
2258	float maxt, mint;
2259
2260	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2261	return 0;
2262
2263	Intersectable::NewMail();
2264	ViewCell::NewMail();
2265
2266	Vector3 entp = ray.Extrap(mint);
2267	Vector3 extp = ray.Extrap(maxt);
2268
2269	const Vector3 origin = entp;
2270
2271	VspNode *node = mRoot;
2272	VspNode *farChild = NULL;
2273
2274	float position;
2275	int axis;
2276
2277	while (1)
2278	{
2279	if (!node->IsLeaf())
2280	{
2281	VspInterior in = dynamic_cast<VspInterior >(node);
2282	position = in->GetPosition();
2283	axis = in->GetAxis();
2284
2285	if (entp[axis] <= position)
2286	{
2287	if (extp[axis] <= position)
2288	{
2289	node = in->GetBack();
2290	// cases N1,N2,N3,P5,Z2,Z3
2291	continue;
2292	}
2293	else
2294	{
2295	// case N4
2296	node = in->GetBack();
2297	farChild = in->GetFront();
2298	}
2299	}
2300	else
2301	{
2302	if (position <= extp[axis])
2303	{
2304	node = in->GetFront();
2305	// cases P1,P2,P3,N5,Z1
2306	continue;
2307	}
2308	else
2309	{
2310	node = in->GetFront();
2311	farChild = in->GetBack();
2312	// case P4
2313	}
2314	}
2315
2316	// $$ modification 3.5.2004 - hints from Kamil Ghais
2317	// case N4 or P4
2318	const float tdist = (position - origin[axis]) / dir[axis];
2319	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2320	extp = origin + dir * tdist;
2321	maxt = tdist;
2322	}
2323	else
2324	{
2325	// compute intersection with all objects in this leaf
2326	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2327	ViewCell *vc = leaf->GetViewCell();
2328
2329	if (!vc->Mailed())
2330	{
2331	vc->Mail();
2332	// todo: add view cells to ray
2333	++ hits;
2334	}
2335	#if 0
2336	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2337	#endif
2338	// get the next node from the stack
2339	if (tStack.empty())
2340	break;
2341
2342	entp = extp;
2343	mint = maxt;
2344
2345	LineTraversalData &s = tStack.top();
2346	node = s.mNode;
2347	extp = s.mExitPoint;
2348	maxt = s.mMaxT;
2349	tStack.pop();
2350	}
2351	}
2352
2353	return hits;
2354	}
2355
2356
2357	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2358	{
2359	if (mRoot == NULL)
2360	return NULL;
2361
2362	stack<VspNode *> nodeStack;
2363	nodeStack.push(mRoot);
2364
2365	ViewCellLeaf *viewcell = NULL;
2366
2367	while (!nodeStack.empty())
2368	{
2369	VspNode *node = nodeStack.top();
2370	nodeStack.pop();
2371
2372	if (node->IsLeaf())
2373	{
2374	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2375	break;
2376	}
2377	else
2378	{
2379	VspInterior interior = dynamic_cast<VspInterior >(node);
2380
2381	// random decision
2382	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2383	nodeStack.push(interior->GetBack());
2384	else
2385	nodeStack.push(interior->GetFront());
2386	}
2387	}
2388
2389	if (active)
2390	return mViewCellsTree->GetActiveViewCell(viewcell);
2391	else
2392	return viewcell;
2393	}
2394
2395
2396	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2397	{
2398	VspNode *node = mRoot;
2399
2400	while (1)
2401	{
2402	// early exit
2403	if (node->TreeValid())
2404	return true;
2405
2406	if (node->IsLeaf())
2407	return false;
2408
2409	VspInterior in = dynamic_cast<VspInterior >(node);
2410
2411	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2412	{
2413	node = in->GetBack();
2414	}
2415	else
2416	{
2417	node = in->GetFront();
2418	}
2419	}
2420
2421	// should never come here
2422	return false;
2423	}
2424
2425
2426	void VspTree::PropagateUpValidity(VspNode *node)
2427	{
2428	const bool isValid = node->TreeValid();
2429
2430	// propagative up invalid flag until only invalid nodes exist over this node
2431	if (!isValid)
2432	{
2433	while (!node->IsRoot() && node->GetParent()->TreeValid())
2434	{
2435	node = node->GetParent();
2436	node->SetTreeValid(false);
2437	}
2438	}
2439	else
2440	{
2441	// propagative up valid flag until one of the subtrees is invalid
2442	while (!node->IsRoot() && !node->TreeValid())
2443	{
2444	node = node->GetParent();
2445	VspInterior interior = dynamic_cast<VspInterior >(node);
2446
2447	// the parent is valid iff both leaves are valid
2448	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2449	interior->GetFront()->TreeValid());
2450	}
2451	}
2452	}
2453
2454
2455	bool VspTree::Export(OUT_STREAM &stream)
2456	{
2457	ExportNode(mRoot, stream);
2458
2459	return true;
2460	}
2461
2462
2463	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2464	{
2465	if (node->IsLeaf())
2466	{
2467	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2468	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2469
2470	int id = -1;
2471	if (viewCell != mOutOfBoundsCell)
2472	id = viewCell->GetId();
2473
2474	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2475	}
2476	else
2477	{
2478	VspInterior interior = dynamic_cast<VspInterior >(node);
2479
2480	AxisAlignedPlane plane = interior->GetPlane();
2481	stream << "<Interior plane=\"" << plane.mPosition << " "
2482	<< plane.mAxis << "\">" << endl;
2483
2484	ExportNode(interior->GetBack(), stream);
2485	ExportNode(interior->GetFront(), stream);
2486
2487	stream << "</Interior>" << endl;
2488	}
2489	}
2490
2491
2492	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2493	RayInfoContainer &rays,
2494	RayInfoContainer &frontRays,
2495	RayInfoContainer &backRays) const
2496	{
2497	int splits = 0;
2498
2499	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2500
2501	for (rit = rays.begin(); rit != rit_end; ++ rit)
2502	{
2503	RayInfo bRay = *rit;
2504
2505	VssRay *ray = bRay.mRay;
2506	float t;
2507
2508	// get classification and receive new t
2509	// test if start point behind or in front of plane
2510	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2511
2512	if (side == 0)
2513	{
2514	++ splits;
2515
2516	if (ray->HasPosDir(plane.mAxis))
2517	{
2518	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2519	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2520	}
2521	else
2522	{
2523	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2524	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2525	}
2526	}
2527	else if (side == 1)
2528	{
2529	frontRays.push_back(bRay);
2530	}
2531	else
2532	{
2533	backRays.push_back(bRay);
2534	}
2535	}
2536
2537	return splits;
2538	}
2539
2540
2541	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2542	{
2543	if (!node->GetParent())
2544	return mBoundingBox;
2545
2546	if (!node->IsLeaf())
2547	{
2548	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
2549	}
2550
2551	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
2552
2553	AxisAlignedBox3 box(parent->GetBoundingBox());
2554
2555	if (parent->GetFront() == node)
2556	box.SetMin(parent->GetAxis(), parent->GetPosition());
2557	else
2558	box.SetMax(parent->GetAxis(), parent->GetPosition());
2559
2560	return box;
2561	}
2562
2563
2564	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2565	ViewCellContainer &viewCells) const
2566	{
2567	stack<VspNode *> nodeStack;
2568
2569	ViewCell::NewMail();
2570
2571	while (!nodeStack.empty())
2572	{
2573	VspNode *node = nodeStack.top();
2574	nodeStack.pop();
2575
2576	const AxisAlignedBox3 bbox = GetBoundingBox(node);
2577
2578	if (bbox.Includes(box))
2579	{
2580	// node geometry is contained in box
2581	CollectViewCells(node, true, viewCells, true);
2582	}
2583	else if (Overlap(bbox, box))
2584	{
2585	if (node->IsLeaf())
2586	{
2587	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2588
2589	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2590	{
2591	leaf->GetViewCell()->Mail();
2592	viewCells.push_back(leaf->GetViewCell());
2593	}
2594	}
2595	else
2596	{
2597	VspInterior interior = dynamic_cast<VspInterior >(node);
2598
2599	VspNode *first = interior->GetFront();
2600	VspNode *second = interior->GetBack();
2601
2602	nodeStack.push(first);
2603	nodeStack.push(second);
2604	}
2605	}
2606	// default: cull
2607	}
2608
2609	return (int)viewCells.size();
2610	}
2611
2612
2613	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2614	RayInfoContainer &rays)
2615	{
2616	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2617
2618	long startTime = GetTime();
2619
2620	cout << "storing rays ... ";
2621
2622	Intersectable::NewMail();
2623
2624	//-- store rays and objects
2625	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2626	{
2627	VssRay ray = rit;
2628	float minT, maxT;
2629	static Ray hray;
2630
2631	hray.Init(*ray);
2632
2633	// TODO: not very efficient to implictly cast between rays types
2634	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2635	{
2636	float len = ray->Length();
2637
2638	if (!len)
2639	len = Limits::Small;
2640
2641	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2642	}
2643	}
2644
2645	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2646	}
2647
2648
2649	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2650	{
2651	static Ray hray;
2652	hray.Init(ray);
2653
2654	float tmin = 0, tmax = 1.0;
2655
2656	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2657	return;
2658
2659	const Vector3 origin = hray.Extrap(tmin);
2660	const Vector3 termination = hray.Extrap(tmax);
2661
2662	// view cells were not precomputed
2663	// don't mail because we need mailboxing for something else
2664	CastLineSegment(origin, termination, viewCells, false);
2665	}
2666
2667
2668	SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
2669	RayInfoContainer &rays)
2670	{
2671	mVspStats.Reset();
2672	mVspStats.Start();
2673	mVspStats.nodes = 1;
2674
2675	// store pointer to this tree
2676	VspSubdivisionCandidate::sVspTree = this;
2677
2678	// initialise termination criteria
2679	mTermMinProbability *= mBoundingBox.GetVolume();
2680	// get clipped rays
2681	PreprocessRays(sampleRays, rays);
2682
2683	/// collect pvs from rays
2684	const int pvsSize = EvalPvsSize(rays);
2685
2686
2687	//////////
2688	//-- prepare view space partition
2689
2690	const float prop = mBoundingBox.GetVolume();
2691
2692	// we assume that leaf was already created
2693	VspLeaf *leaf = new VspLeaf();
2694	mRoot = leaf;
2695
2696	// first vsp traversal data
2697	VspTraversalData vData(leaf, 0, &rays, pvsSize, prop, mBoundingBox);
2698
2699	// create first view cell
2700	CreateViewCell(vData, false);
2701
2702	#if WORK_WITH_VIEWCELL_PVS
2703	// add first view cell to all the objects view cell pvs
2704	ObjectPvsMap::const_iterator oit,
2705	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2706
2707	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2708	{
2709	Intersectable obj = (oit).first;
2710	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2711	}
2712	#endif
2713
2714	//////////////
2715	//-- create the first split candidate
2716
2717	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2718	EvalSubdivisionCandidate(*splitCandidate);
2719	leaf->SetSubdivisionCandidate(splitCandidate);
2720
2721	mTotalCost = (float)pvsSize;
2722	EvalSubdivisionStats(*splitCandidate);
2723
2724	return splitCandidate;
2725	}
2726
2727
2728	void VspTree::CollectDirtyCandidate(const VssRay &ray,
2729	const bool isTermination,
2730	vector<SubdivisionCandidate *> &dirtyList) const
2731	{
2732
2733	Intersectable *obj;
2734	Vector3 pt;
2735	KdNode *node;
2736
2737	ray.GetSampleData(isTermination, pt, &obj, &node);
2738
2739	if (!obj) return;
2740
2741	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2742	{
2743	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2744	{
2745	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2746
2747	if (!leaf->Mailed())
2748	{
2749	leaf->Mail();
2750	dirtyList.push_back(leaf->mSubdivisionCandidate);
2751	}
2752	break;
2753	}
2754	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2755	{
2756	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2757
2758	if (!leaf->Mailed())
2759	{
2760	leaf->Mail();
2761	// a candidate still attached to this node
2762	if (leaf->GetSubdivisionCandidate())
2763	{
2764	dirtyList.push_back(leaf->GetSubdivisionCandidate());
2765	}
2766	}
2767	break;
2768	}
2769	default:
2770	break;
2771	}
2772	}
2773
2774
2775	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
2776	vector<SubdivisionCandidate *> &dirtyList)
2777	{
2778	VspTraversalData &tData = sc->mParentData;
2779	VspLeaf *node = tData.mNode;
2780
2781	KdLeaf::NewMail();
2782	BvhLeaf::NewMail();
2783
2784	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2785
2786	// add all kd nodes seen by the rays
2787	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2788	{
2789	VssRay ray = (rit).mRay;
2790
2791	CollectDirtyCandidate(*ray, true, dirtyList);
2792	CollectDirtyCandidate(*ray, false, dirtyList);
2793	}
2794	}
2795
2796
2797	int VspTree::EvalMaxEventContribution(const VssRay &ray,
2798	const bool isTermination) const
2799	{
2800	Intersectable *obj;
2801	Vector3 pt;
2802	KdNode *node;
2803
2804	ray.GetSampleData(isTermination, pt, &obj, &node);
2805
2806	if (!obj)
2807	return 0;
2808
2809	int pvs = 0;
2810
2811	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2812	{
2813	case HierarchyManager::NO_OBJ_SUBDIV:
2814	{
2815	if (-- obj->mCounter == 0)
2816	++ pvs;
2817	break;
2818	}
2819	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2820	{
2821	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2822
2823	// add contributions of the kd nodes
2824	pvs += EvalMaxEventContribution(leaf);
2825	break;
2826	}
2827	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2828	{
2829	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2830
2831	if (-- leaf->mCounter == 0)
2832	pvs += (int)leaf->mObjects.size();
2833	break;
2834	}
2835	default:
2836	break;
2837	}
2838
2839	return pvs;
2840	}
2841
2842
2843	int VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
2844	{
2845	int pvsSize = 0;
2846
2847	Intersectable *obj;
2848	Vector3 pt;
2849	KdNode *node;
2850
2851	ray.GetSampleData(isTermination, pt, &obj, &node);
2852
2853	if (!obj)
2854	return 0;
2855
2856	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2857	{
2858	case HierarchyManager::NO_OBJ_SUBDIV:
2859	{
2860	if (!obj->Mailed())
2861	{
2862	obj->Mail();
2863	obj->mCounter = 0;
2864	++ pvsSize;
2865	}
2866
2867	++ obj->mCounter;
2868	break;
2869	}
2870	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2871	{
2872	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2873	pvsSize += PrepareHeuristics(leaf);
2874	break;
2875	}
2876	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2877	{
2878	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2879
2880	if (!leaf->Mailed())
2881	{
2882	leaf->Mail();
2883	leaf->mCounter = 0;
2884	pvsSize += (int)leaf->mObjects.size();
2885	}
2886
2887	++ leaf->mCounter;
2888	break;
2889	}
2890	default:
2891	break;
2892	}
2893
2894	return pvsSize;
2895	}
2896
2897
2898	int VspTree::EvalMinEventContribution(const VssRay &ray,
2899	const bool isTermination) const
2900	{
2901	Intersectable *obj;
2902	Vector3 pt;
2903	KdNode *node;
2904
2905	ray.GetSampleData(isTermination, pt, &obj, &node);
2906
2907	if (!obj) return 0;
2908
2909	int pvs = 0;
2910
2911	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2912	{
2913	case HierarchyManager::NO_OBJ_SUBDIV:
2914	{
2915	if (!obj->Mailed())
2916	{
2917	obj->Mail();
2918	++ pvs;
2919	}
2920	break;
2921	}
2922	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2923	{
2924	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2925	// add contributions of the kd nodes
2926	pvs += EvalMinEventContribution(leaf);
2927	break;
2928	}
2929	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2930	{
2931	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2932	if (!leaf->Mailed())
2933	{
2934	leaf->Mail();
2935	pvs += (int)leaf->mObjects.size();
2936	}
2937	break;
2938	}
2939	default:
2940	break;
2941	}
2942
2943	return pvs;
2944	}
2945
2946
2947	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
2948	const bool isTermination,
2949	const int cf,
2950	float &frontPvs,
2951	float &backPvs,
2952	float &totalPvs) const
2953	{
2954	Intersectable *obj;
2955	Vector3 pt;
2956	KdNode *node;
2957
2958	ray.GetSampleData(isTermination, pt, &obj, &node);
2959
2960	if (!obj) return;
2961
2962	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
2963	{
2964	case HierarchyManager::NO_OBJ_SUBDIV:
2965	{
2966	// find front and back pvs for origing and termination object
2967	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
2968	break;
2969	}
2970	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2971	{
2972	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2973	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2974	break;
2975	}
2976	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2977	{
2978	BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
2979	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
2980	break;
2981	}
2982	}
2983	}
2984
2985
2986	int VspTree::EvalContributionToPvs(const VssRay &ray,
2987	const bool isTermination) const
2988	{
2989	Intersectable *obj;
2990	Vector3 pt;
2991	KdNode *node;
2992
2993	ray.GetSampleData(isTermination, pt, &obj, &node);
2994
2995	if (!obj) return 0;
2996
2997	int pvs = 0;
2998
2999	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
3000	{
3001	case HierarchyManager::NO_OBJ_SUBDIV:
3002	{
3003	if (!obj->Mailed())
3004	{
3005	obj->Mail();
3006	++ pvs;
3007	}
3008	break;
3009	}
3010	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3011	{
3012	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3013
3014	pvs += EvalContributionToPvs(leaf);
3015	break;
3016	}
3017	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3018	{
3019	BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
3020
3021	if (!bvhleaf->Mailed())
3022	{
3023	bvhleaf->Mail();
3024	pvs += (int)bvhleaf->mObjects.size();
3025	}
3026	break;
3027	}
3028	default:
3029	break;
3030	}
3031
3032	return pvs;
3033	}
3034
3035
3036	int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3037	{
3038	if (leaf->Mailed()) // leaf already mailed
3039	return 0;
3040
3041	leaf->Mail();
3042
3043	int pvs = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3044
3045	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3046
3047	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3048	{
3049	Intersectable obj = oit;
3050	if (!obj->Mailed())
3051	{
3052	obj->Mail();
3053	++ pvs;
3054	}
3055	}
3056
3057	return pvs;
3058	}
3059
3060
3061	}

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

Download in other formats: