Context Navigation

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

Revision 1449, 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	return terminationCriteriaMet;
574	}
575
576
577	void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
578	{
579	//-- create new view cell
580	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
581
582	VspViewCell *viewCell = new VspViewCell();
583	leaf->SetViewCell(viewCell);
584
585	int conSamp = 0;
586	float sampCon = 0.0f;
587
588	if (updatePvs)
589	{
590	//-- update pvs of view cell
591	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
592
593	// update scalar pvs size value
594	ObjectPvs &pvs = viewCell->GetPvs();
595	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
596
597	mVspStats.contributingSamples += conSamp;
598	mVspStats.sampleContributions += (int)sampCon;
599	}
600
601	if (mStoreRays)
602	{
603	///////////
604	//-- store sampling rays
605	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
606
607	for (it = tData.mRays->begin(); it != it_end; ++ it)
608	{
609	(*it).mRay->Ref();
610	leaf->mVssRays.push_back((*it).mRay);
611	}
612	}
613
614	// set view cell values
615	viewCell->mLeaf = leaf;
616
617	viewCell->SetVolume(tData.mProbability);
618	leaf->mProbability = tData.mProbability;
619	}
620
621
622	void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
623	{
624	const float costDecr = sc.GetRenderCostDecrease();
625
626	AddSubdivisionStats(mVspStats.Leaves(),
627	costDecr,
628	mTotalCost,
629	(float)mTotalPvsSize / (float)mVspStats.Leaves());
630	}
631
632
633	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
634	SubdivisionCandidate *splitCandidate,
635	const bool globalCriteriaMet)
636	{
637	// todo remove dynamic cast
638	VspSubdivisionCandidate *sc =
639	dynamic_cast<VspSubdivisionCandidate *>(splitCandidate);
640
641	VspTraversalData &tData = sc->mParentData;
642	VspNode *newNode = tData.mNode;
643
644	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
645	{
646	//-- continue subdivision
647	VspTraversalData tFrontData;
648	VspTraversalData tBackData;
649
650	// create new interior node and two leaf node
651	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
652	const int maxCostMisses = sc->mMaxCostMisses;
653
654	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
655
656	// how often was max cost ratio missed in this branch?
657	tFrontData.mMaxCostMisses = maxCostMisses;
658	tBackData.mMaxCostMisses = maxCostMisses;
659
660	mTotalCost -= sc->GetRenderCostDecrease();
661	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
662
663	// subdivision statistics
664	if (1) EvalSubdivisionStats(*sc);
665
666	//-- evaluate new split candidates for global greedy cost heuristics
667
668	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
669	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
670
671	EvalSubdivisionCandidate(*frontCandidate);
672	EvalSubdivisionCandidate(*backCandidate);
673
674	// cross reference
675	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
676	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
677
678	tQueue.Push(frontCandidate);
679	tQueue.Push(backCandidate);
680
681	// delete old leaf node
682	//DEL_PTR(tData.mNode);
683	}
684
685	if (newNode->IsLeaf()) // subdivision terminated
686	{
687	// view cell is created during subdivision
688	//CreateViewCell(tData);
689
690	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
691	ViewCell *viewCell = leaf->GetViewCell();
692
693	int conSamp = 0;
694	float sampCon = 0.0f;
695
696	#if 0
697	/////////////
698	//-- store pvs optained from rays
699
700	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
701
702	// update scalar pvs size value
703	ObjectPvs &pvs = viewCell->GetPvs();
704	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
705
706	mVspStats.contributingSamples += conSamp;
707	mVspStats.sampleContributions += (int)sampCon;
708	#endif
709	if (mStoreRays)
710	{
711	//////////
712	//-- store rays piercing this view cell
713	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
714	for (it = tData.mRays->begin(); it != it_end; ++ it)
715	{
716	(*it).mRay->Ref();
717	leaf->mVssRays.push_back((*it).mRay);
718	//leaf->mVssRays.push_back(new VssRay((it).mRay));
719	}
720	}
721
722	// finally evaluate statistics for this leaf
723	EvaluateLeafStats(tData);
724	// detach subdivision candidate: this leaf is no candidate for
725	// splitting anymore
726	tData.mNode->SetSubdivisionCandidate(NULL);
727	// detach node so it won't get deleted
728	tData.mNode = NULL;
729	}
730
731	return newNode;
732	}
733
734
735	void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate)
736	{
737	float frontProb;
738	float backProb;
739
740	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
741
742	// compute locally best split plane
743	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
744	splitCandidate.mSplitPlane,
745	frontProb,
746	backProb);
747
748	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
749
750	// max cost threshold violated?
751	splitCandidate.mMaxCostMisses = maxCostRatioViolated ?
752	splitCandidate.mParentData.mMaxCostMisses + 1:
753	splitCandidate.mParentData.mMaxCostMisses;
754
755	float oldRenderCost;
756
757	// compute global decrease in render cost
758	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
759	splitCandidate.mParentData,
760	oldRenderCost);
761
762	splitCandidate.SetRenderCostDecrease(renderCostDecr);
763
764	#if 0
765	const float priority = (float)-splitCandidate.mParentData.mDepth;
766	#else
767	// take render cost of node into account
768	// otherwise danger of being stuck in a local minimum!!
769	const float factor = mRenderCostDecreaseWeight;
770	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
771	#endif
772
773	splitCandidate.SetPriority(priority);
774	}
775
776
777	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
778	VspTraversalData &tData,
779	VspTraversalData &frontData,
780	VspTraversalData &backData)
781	{
782	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
783
784	///////////////
785	//-- new traversal values
786
787	frontData.mDepth = tData.mDepth + 1;
788	backData.mDepth = tData.mDepth + 1;
789
790	frontData.mRays = new RayInfoContainer();
791	backData.mRays = new RayInfoContainer();
792
793	//-- subdivide rays
794	SplitRays(splitPlane,
795	*tData.mRays,
796	*frontData.mRays,
797	*backData.mRays);
798
799	/////////////
800	//-- compute pvs
801	frontData.mPvs = EvalPvsSize(*frontData.mRays);
802	backData.mPvs = EvalPvsSize(*backData.mRays);
803	//Debug << "f pvs: " << frontData.mPvs << " b pvs: " << backData.mPvs << " pvs " << tData.mPvs << endl;
804
805	//-- split front and back node geometry and compute area
806	tData.mBoundingBox.Split(splitPlane.mAxis,
807	splitPlane.mPosition,
808	frontData.mBoundingBox,
809	backData.mBoundingBox);
810
811	frontData.mProbability = frontData.mBoundingBox.GetVolume();
812	backData.mProbability = tData.mProbability - frontData.mProbability;
813
814	// update some stats
815	// store maximal depth
816	if (tData.mDepth > mVspStats.maxDepth)
817	{
818	//Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
819	mVspStats.maxDepth = tData.mDepth;
820	}
821
822	// two more leaves
823	mVspStats.nodes += 2;
824	/// and a new split
825	++ mVspStats.splits[splitPlane.mAxis];
826
827	///////////////////////////////////////////
828	//-- create front and back and subdivide further
829
830	VspInterior *interior = new VspInterior(splitPlane);
831	VspInterior *parent = leaf->GetParent();
832
833	// replace a link from node's parent
834	if (parent)
835	{
836	parent->ReplaceChildLink(leaf, interior);
837	interior->SetParent(parent);
838
839	// remove "parent" view cell from pvs of all objects (traverse trough rays)
840	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
841	}
842	else // new root
843	{
844	mRoot = interior;
845	}
846
847	VspLeaf *frontLeaf = new VspLeaf(interior);
848	VspLeaf *backLeaf = new VspLeaf(interior);
849
850	// and setup child links
851	interior->SetupChildLinks(frontLeaf, backLeaf);
852
853	// add bounding box
854	interior->SetBoundingBox(tData.mBoundingBox);
855
856	// set front and back leaf
857	frontData.mNode = frontLeaf;
858	backData.mNode = backLeaf;
859
860	// explicitely create front and back view cell
861	CreateViewCell(frontData, false);
862	CreateViewCell(backData, false);
863
864
865	#if WORK_WITH_VIEWCELL_PVS
866	// create front and back view cell
867	// add front and back view cell to "Potentially Visbilie View Cells"
868	// of the objects in front and back pvs
869
870	AddViewCellReferences(frontLeaf->GetViewCell());
871	AddViewCellReferences(backLeaf->GetViewCell());
872	#endif
873
874	// set the time stamp so the order of traversal can be reconstructed
875	interior->mTimeStamp = mTimeStamp ++;
876
877	return interior;
878	}
879
880
881	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
882	{
883	KdLeaf::NewMail();
884
885	// remove the parents from the object pvss
886	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
887
888	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
889	{
890	Intersectable object = (oit).first;
891	// HACK: make sure that the view cell is removed from the pvs
892	const float high_contri = 9999999;
893
894	// remove reference count of view cells
895	object->mViewCellPvs.RemoveSample(parent, high_contri);
896	}
897	}
898
899
900	void VspTree::AddViewCellReferences(ViewCell *vc) const
901	{
902	KdLeaf::NewMail();
903
904	// Add front view cell to the object pvsss
905	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
906
907	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
908	{
909	Intersectable object = (oit).first;
910
911	// increase reference count of view cells
912	object->mViewCellPvs.AddSample(vc, 1);
913	}
914	}
915
916
917	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
918	const RayInfoContainer &rays,
919	float &sampleContributions,
920	int &contributingSamples)
921	{
922	sampleContributions = 0;
923	contributingSamples = 0;
924
925	RayInfoContainer::const_iterator it, it_end = rays.end();
926
927	ViewCellLeaf *vc = leaf->GetViewCell();
928
929	// add contributions from samples to the PVS
930	for (it = rays.begin(); it != it_end; ++ it)
931	{
932	float sc = 0.0f;
933	VssRay ray = (it).mRay;
934
935	bool madeContrib = false;
936	float contribution;
937
938	Intersectable *obj = ray->mTerminationObject;
939
940	if (obj)
941	{
942	madeContrib =
943	mViewCellsManager->AddSampleToPvs(
944	obj,
945	ray->mTermination,
946	vc,
947	ray->mPdf,
948	contribution);
949
950	sc += contribution;
951	}
952
953	obj = ray->mOriginObject;
954
955	if (obj)
956	{
957	madeContrib =
958	mViewCellsManager->AddSampleToPvs(
959	obj,
960	ray->mOrigin,
961	vc,
962	ray->mPdf,
963	contribution);
964
965	sc += contribution;
966	}
967
968	if (madeContrib)
969	{
970	++ contributingSamples;
971	}
972
973	// store rays for visualization
974	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
975	}
976	}
977
978
979	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
980	const int axis,
981	float minBand,
982	float maxBand)
983	{
984	mLocalSubdivisionCandidates->clear();
985
986	const int requestedSize = 2 * (int)(rays.size());
987
988	// creates a sorted split candidates array
989	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
990	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
991	{
992	delete mLocalSubdivisionCandidates;
993	mLocalSubdivisionCandidates = new vector<SortableEntry>;
994	}
995
996	mLocalSubdivisionCandidates->reserve(requestedSize);
997
998	float pos;
999	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1000
1001	//-- insert all queries
1002	for (rit = rays.begin(); rit != rit_end; ++ rit)
1003	{
1004	const bool positive = (*rit).mRay->HasPosDir(axis);
1005	const bool delayMinEvent = false;
1006
1007	// origin point
1008	pos = (*rit).ExtrapOrigin(axis);
1009	const int oType = positive ? SortableEntry::ERayMin : SortableEntry::ERayMax;
1010
1011	if (delayMinEvent && oType == SortableEntry::ERayMin)
1012	pos += mEpsilon; // for walls
1013
1014	mLocalSubdivisionCandidates->push_back(SortableEntry(oType, pos, (*rit).mRay));
1015
1016	// termination point
1017	pos = (*rit).ExtrapTermination(axis);
1018	const int tType = positive ? SortableEntry::ERayMax : SortableEntry::ERayMin;
1019
1020	if (delayMinEvent && tType == SortableEntry::ERayMin)
1021	pos += mEpsilon; // for walls
1022
1023	mLocalSubdivisionCandidates->push_back(SortableEntry(tType, pos, (*rit).mRay));
1024	}
1025
1026	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1027	}
1028
1029
1030	int VspTree::PrepareHeuristics(KdLeaf *leaf)
1031	{
1032	int pvsSize = 0;
1033
1034	if (!leaf->Mailed())
1035	{
1036	leaf->Mail();
1037	leaf->mCounter = 1;
1038	// add objects without the objects which are in several kd leaves
1039	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1040	}
1041	else
1042	{
1043	++ leaf->mCounter;
1044	}
1045
1046	//-- the objects belonging to several leaves must be handled seperately
1047	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1048
1049	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1050	{
1051	Intersectable object = oit;
1052
1053	if (!object->Mailed())
1054	{
1055	object->Mail();
1056	object->mCounter = 1;
1057
1058	++ pvsSize;
1059	}
1060	else
1061	{
1062	++ object->mCounter;
1063	}
1064	}
1065
1066	return pvsSize;
1067	}
1068
1069
1070	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1071	{
1072	Intersectable::NewMail();
1073	KdNode::NewMail();
1074	BvhLeaf::NewMail();
1075
1076	int pvsSize = 0;
1077
1078	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1079
1080	// set all kd nodes / objects as belonging to the front pvs
1081	for (ri = rays.begin(); ri != ri_end; ++ ri)
1082	{
1083	VssRay ray = (ri).mRay;
1084
1085	pvsSize += PrepareHeuristics(*ray, true);
1086	pvsSize += PrepareHeuristics(*ray, false);
1087	}
1088
1089	return pvsSize;
1090	}
1091
1092
1093	int VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1094	{
1095	int pvs = 0;
1096
1097	// leaf falls out of right pvs
1098	if (-- leaf->mCounter == 0)
1099	{
1100	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1101	}
1102
1103	//-- separately handle objects which are in several kd leaves
1104
1105	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1106
1107	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1108	{
1109	Intersectable object = oit;
1110
1111	if (-- object->mCounter == 0)
1112	{
1113	++ pvs;
1114	}
1115	}
1116
1117	return pvs;
1118	}
1119
1120
1121	int VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1122	{
1123	if (leaf->Mailed())
1124	return 0;
1125
1126	leaf->Mail();
1127
1128	// add objects without those which are part of several kd leaves
1129	int pvs = ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1130
1131	// separately handle objects which are part of several kd leaves
1132	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1133
1134	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1135	{
1136	Intersectable object = oit;
1137
1138	// object not previously in pvs
1139	if (!object->Mailed())
1140	{
1141	object->Mail();
1142	++ pvs;
1143	}
1144	}
1145
1146	return pvs;
1147	}
1148
1149
1150	void VspTree::EvalHeuristics(const SortableEntry &ci,
1151	int &pvsLeft,
1152	int &pvsRight) const
1153	{
1154	VssRay *ray = ci.ray;
1155
1156	// eval changes in pvs causes by min event
1157	if (ci.type == SortableEntry::ERayMin)
1158	{
1159	pvsLeft += EvalMinEventContribution(*ray, true);
1160	pvsLeft += EvalMinEventContribution(*ray, false);
1161	}
1162	else // eval changes in pvs causes by max event
1163	{
1164	pvsRight -= EvalMaxEventContribution(*ray, true);
1165	pvsRight -= EvalMaxEventContribution(*ray, false);
1166	}
1167	}
1168
1169
1170	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1171	const AxisAlignedBox3 &box,
1172	const int axis,
1173	float &position)
1174	{
1175	// get subset of rays
1176	RayInfoContainer usedRays;
1177
1178	if (mMaxTests < (int)tData.mRays->size())
1179	{
1180	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
1181	}
1182	else
1183	{
1184	usedRays = *tData.mRays;
1185	}
1186
1187	const float minBox = box.Min(axis);
1188	const float maxBox = box.Max(axis);
1189
1190	const float sizeBox = maxBox - minBox;
1191
1192	const float minBand = minBox + mMinBand * sizeBox;
1193	const float maxBand = minBox + mMaxBand * sizeBox;
1194
1195	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1196
1197	// prepare the sweep
1198	// note: returns pvs size => no need t give pvs size as function parameter
1199	const int pvsSize = PrepareHeuristics(usedRays);
1200
1201	// go through the lists, count the number of objects left and right
1202	// and evaluate the following cost funcion:
1203	// C = ct_div_ci + (qlrl + qrrr)/queries
1204
1205	int pvsl = 0;
1206	int pvsr = pvsSize;
1207
1208	int pvsBack = pvsl;
1209	int pvsFront = pvsr;
1210
1211	float sum = (float)pvsSize * sizeBox;
1212	float minSum = 1e20f;
1213
1214	// if no good split can be found, take mid split
1215	position = minBox + 0.5f * sizeBox;
1216
1217	// the relative cost ratio
1218	float ratio = 99999999.0f;
1219	bool splitPlaneFound = false;
1220
1221	Intersectable::NewMail();
1222	KdLeaf::NewMail();
1223	BvhLeaf::NewMail();
1224
1225	//-- traverse through visibility events
1226	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSubdivisionCandidates->end();
1227
1228	#ifdef _DEBUG
1229	const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1230	const int leaves = mVspStats.Leaves();
1231	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
1232
1233	ofstream sumStats;
1234	ofstream pvslStats;
1235	ofstream pvsrStats;
1236
1237	if (printStats)
1238	{
1239	char str[64];
1240
1241	sprintf(str, "tmp/vsp_heur_sum-%04d.log", leaves);
1242	sumStats.open(str);
1243	sprintf(str, "tmp/vsp_heur_pvsl-%04d.log", leaves);
1244	pvslStats.open(str);
1245	sprintf(str, "tmp/vsp_heur_pvsr-%04d.log", leaves);
1246	pvsrStats.open(str);
1247	}
1248
1249	#endif
1250	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1251	{
1252	// compute changes to front and back pvs
1253	EvalHeuristics(*ci, pvsl, pvsr);
1254
1255	// Note: sufficient to compare size of bounding boxes of front and back side?
1256	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1257	{
1258	float currentPos;
1259
1260	// HACK: current positition is BETWEEN visibility events
1261	if (0 && ((ci + 1) != ci_end))
1262	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1263	else
1264	currentPos = (*ci).value;
1265
1266	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1267
1268	#ifdef _DEBUG
1269	if (printStats)
1270	{
1271	sumStats
1272	<< "#Position\n" << currentPos << endl
1273	<< "#Sum\n" << sum * volRatio << endl
1274	<< "#Pvs\n" << pvsl + pvsr << endl;
1275
1276	pvslStats
1277	<< "#Position\n" << currentPos << endl
1278	<< "#Pvsl\n" << pvsl << endl;
1279
1280	pvsrStats
1281	<< "#Position\n" << currentPos << endl
1282	<< "#Pvsr\n" << pvsr << endl;
1283	}
1284	#endif
1285
1286	if (sum < minSum)
1287	{
1288	splitPlaneFound = true;
1289
1290	minSum = sum;
1291	position = currentPos;
1292
1293	pvsBack = pvsl;
1294	pvsFront = pvsr;
1295	}
1296	}
1297	}
1298
1299	/////////
1300	//-- compute cost
1301
1302	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1303	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1304
1305	const float pOverall = sizeBox;
1306	const float pBack = position - minBox;
1307	const float pFront = maxBox - position;
1308
1309	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1310	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1311	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1312
1313	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1314	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1315
1316	if (splitPlaneFound)
1317	{
1318	ratio = newRenderCost / oldRenderCost;
1319	}
1320
1321	#ifdef _DEBUG
1322	Debug << "\n§§§§ eval local cost §§§§" << endl
1323	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1324	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1325	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1326	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1327	#endif
1328	return ratio;
1329	}
1330
1331
1332	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1333	AxisAlignedPlane &plane,
1334	float &pFront,
1335	float &pBack)
1336	{
1337	float nPosition[3];
1338	float nCostRatio[3];
1339	float nProbFront[3];
1340	float nProbBack[3];
1341
1342	// create bounding box of node geometry
1343	AxisAlignedBox3 box = tData.mBoundingBox;
1344
1345	int sAxis = 0;
1346	int bestAxis = -1;
1347
1348	// do we use some kind of specialised "fixed" axis?
1349	const bool useSpecialAxis =
1350	mOnlyDrivingAxis \|\| mCirculatingAxis;
1351
1352	if (mCirculatingAxis)
1353	{
1354	int parentAxis = 0;
1355	VspNode *parent = tData.mNode->GetParent();
1356
1357	if (parent)
1358	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1359
1360	sAxis = (parentAxis + 1) % 3;
1361	}
1362	else if (mOnlyDrivingAxis)
1363	{
1364	sAxis = box.Size().DrivingAxis();
1365	}
1366
1367	for (int axis = 0; axis < 3; ++ axis)
1368	{
1369	if (!useSpecialAxis \|\| (axis == sAxis))
1370	{
1371	if (mUseCostHeuristics)
1372	{
1373	//-- place split plane using heuristics
1374	nCostRatio[axis] =
1375	EvalLocalCostHeuristics(tData,
1376	box,
1377	axis,
1378	nPosition[axis]);
1379	}
1380	else
1381	{
1382	//-- split plane position is spatial median
1383	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1384	nCostRatio[axis] = EvalLocalSplitCost(tData,
1385	box,
1386	axis,
1387	nPosition[axis],
1388	nProbFront[axis],
1389	nProbBack[axis]);
1390	}
1391
1392	if (bestAxis == -1)
1393	{
1394	bestAxis = axis;
1395	}
1396	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1397	{
1398	bestAxis = axis;
1399	}
1400	}
1401	}
1402
1403	////////////////////////////////
1404	//-- assign values of best split
1405
1406	plane.mAxis = bestAxis;
1407	// best split plane position
1408	plane.mPosition = nPosition[bestAxis];
1409
1410	pFront = nProbFront[bestAxis];
1411	pBack = nProbBack[bestAxis];
1412
1413	return nCostRatio[bestAxis];
1414	}
1415
1416
1417	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1418	const VspTraversalData &data,
1419	float &normalizedOldRenderCost) const
1420	{
1421	float pvsFront = 0;
1422	float pvsBack = 0;
1423	float totalPvs = 0;
1424
1425	const float viewSpaceVol = mBoundingBox.GetVolume();
1426
1427	//////////////////////////////////////////////
1428	// mark objects in the front / back / both using mailboxing
1429	// then count pvs sizes
1430	Intersectable::NewMail(3);
1431	KdLeaf::NewMail(3);
1432	BvhLeaf::NewMail(3);
1433
1434	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1435
1436	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1437	{
1438	RayInfo rayInf = *rit;
1439
1440	float t;
1441	VssRay *ray = rayInf.mRay;
1442
1443	// classify ray
1444	const int cf =
1445	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1446	candidatePlane.mPosition, t);
1447
1448	// evaluate contribution of ray endpoint to front and back pvs
1449	// with respect to the classification
1450	UpdateContributionsToPvs(*ray, true, cf, pvsFront, pvsBack, totalPvs);
1451	UpdateContributionsToPvs(*ray, false, cf, pvsFront, pvsBack, totalPvs);
1452	}
1453
1454	AxisAlignedBox3 frontBox;
1455	AxisAlignedBox3 backBox;
1456
1457	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1458
1459	// probability that view point lies in back / front node
1460	float pOverall = data.mProbability;
1461	float pFront = pFront = frontBox.GetVolume();
1462	float pBack = pOverall - pFront;
1463
1464
1465	////////////////////////////////////
1466	//-- evaluate render cost heuristics
1467
1468	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1469	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1470
1471	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1472	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1473	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1474
1475	const float oldRenderCost = pOverall * penaltyOld;
1476	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1477
1478	// we also return the old render cost
1479	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1480
1481	// the render cost decrase for this split
1482	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1483
1484	//#ifdef _DEBUG
1485	Debug << "\nvsp render cost decrease" << endl
1486	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1487	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1488	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1489	<< "render cost decrease: " << renderCostDecrease << endl;
1490	//#endif
1491	return renderCostDecrease;
1492	}
1493
1494
1495
1496	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1497	const AxisAlignedBox3 &box,
1498	const int axis,
1499	const float &position,
1500	float &pFront,
1501	float &pBack) const
1502	{
1503	float pvsTotal = 0;
1504	float pvsFront = 0;
1505	float pvsBack = 0;
1506
1507	// create unique ids for pvs heuristics
1508	Intersectable::NewMail(3);
1509	BvhLeaf::NewMail(3);
1510	KdLeaf::NewMail(3);
1511
1512	const int pvsSize = data.mPvs;
1513
1514	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1515
1516	// this is the main ray classification loop!
1517	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1518	{
1519	VssRay ray = (rit).mRay;
1520
1521	// determine the side of this ray with respect to the plane
1522	float t;
1523	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1524
1525	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1526	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1527	}
1528
1529
1530	//-- evaluate cost heuristics
1531
1532	float pOverall = data.mProbability;
1533
1534	// we use spatial mid split => simplified computation
1535	pBack = pFront = pOverall * 0.5f;
1536
1537	const float newCost = pvsBack * pBack + pvsFront * pFront;
1538	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1539
1540	#ifdef _DEBUG
1541	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1542	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1543	#endif
1544
1545	return (mCtDivCi + newCost) / oldCost;
1546	}
1547
1548
1549	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1550	const int cf,
1551	float &frontPvs,
1552	float &backPvs,
1553	float &totalPvs) const
1554	{
1555	if (!obj) return;
1556
1557	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1558	const int renderCost = 1;
1559
1560	// object in no pvs => new
1561	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1562	{
1563	totalPvs += renderCost;
1564	}
1565
1566	// QUESTION matt: is it safe to assume that
1567	// the object belongs to no pvs in this case?
1568	//if (cf == Ray::COINCIDENT) return;
1569
1570	if (cf >= 0) // front pvs
1571	{
1572	if (!obj->Mailed() && !obj->Mailed(2))
1573	{
1574	frontPvs += renderCost;
1575
1576	// already in back pvs => in both pvss
1577	if (obj->Mailed(1))
1578	obj->Mail(2);
1579	else
1580	obj->Mail();
1581	}
1582	}
1583
1584	if (cf <= 0) // back pvs
1585	{
1586	if (!obj->Mailed(1) && !obj->Mailed(2))
1587	{
1588	backPvs += renderCost;
1589
1590	// already in front pvs => in both pvss
1591	if (obj->Mailed())
1592	obj->Mail(2);
1593	else
1594	obj->Mail(1);
1595	}
1596	}
1597	}
1598
1599
1600	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1601	const int cf,
1602	float &frontPvs,
1603	float &backPvs,
1604	float &totalPvs) const
1605	{
1606	if (!leaf) return;
1607
1608	const int renderCost = (int)leaf->mObjects.size();
1609
1610	// leaf in no pvs => new
1611	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1612	{
1613	totalPvs += renderCost;
1614	}
1615
1616	// QUESTION matt: is it safe to assume that
1617	// the leaf belongs to no pvs in this case?
1618	//if (cf == Ray::COINCIDENT) return;
1619
1620	if (cf >= 0) // front pvs
1621	{
1622	if (!leaf->Mailed() && !leaf->Mailed(2))
1623	{
1624	frontPvs += renderCost;
1625
1626	// already in back pvs => in both pvss
1627	if (leaf->Mailed(1))
1628	leaf->Mail(2);
1629	else
1630	leaf->Mail();
1631	}
1632	}
1633
1634	if (cf <= 0) // back pvs
1635	{
1636	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1637	{
1638	backPvs += renderCost;
1639
1640	// already in front pvs => in both pvss
1641	if (leaf->Mailed())
1642	{
1643	leaf->Mail(2);
1644	}
1645	else
1646	leaf->Mail(1);
1647	}
1648	}
1649	}
1650
1651
1652
1653	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1654	const int cf,
1655	float &frontPvs,
1656	float &backPvs,
1657	float &totalPvs) const
1658	{
1659	if (!leaf) return;
1660
1661	// the objects which are referenced in this and only this leaf
1662	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1663
1664	// newly found leaf
1665	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1666	{
1667	totalPvs += contri;
1668	}
1669
1670	// recursivly update contributions of yet unclassified objects
1671	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1672
1673	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1674	{
1675	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1676	}
1677
1678	// QUESTION matt: is it safe to assume that
1679	// the object belongs to no pvs in this case?
1680	//if (cf == Ray::COINCIDENT) return;
1681
1682	if (cf >= 0) // front pvs
1683	{
1684	if (!leaf->Mailed() && !leaf->Mailed(2))
1685	{
1686	frontPvs += contri;
1687
1688	// already in back pvs => in both pvss
1689	if (leaf->Mailed(1))
1690	leaf->Mail(2);
1691	else
1692	leaf->Mail();
1693	}
1694	}
1695
1696	if (cf <= 0) // back pvs
1697	{
1698	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1699	{
1700	backPvs += contri;
1701
1702	// already in front pvs => in both pvss
1703	if (leaf->Mailed())
1704	leaf->Mail(2);
1705	else
1706	leaf->Mail(1);
1707	}
1708	}
1709	}
1710
1711
1712	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1713	const bool onlyUnmailed,
1714	const int maxPvsSize) const
1715	{
1716	stack<VspNode *> nodeStack;
1717	nodeStack.push(mRoot);
1718
1719	while (!nodeStack.empty())
1720	{
1721	VspNode *node = nodeStack.top();
1722	nodeStack.pop();
1723
1724	if (node->IsLeaf())
1725	{
1726	// test if this leaf is in valid view space
1727	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1728	if (leaf->TreeValid() &&
1729	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1730	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
1731	{
1732	leaves.push_back(leaf);
1733	}
1734	}
1735	else
1736	{
1737	VspInterior interior = dynamic_cast<VspInterior >(node);
1738
1739	nodeStack.push(interior->GetBack());
1740	nodeStack.push(interior->GetFront());
1741	}
1742	}
1743	}
1744
1745
1746	AxisAlignedBox3 VspTree::GetBoundingBox() const
1747	{
1748	return mBoundingBox;
1749	}
1750
1751
1752	VspNode *VspTree::GetRoot() const
1753	{
1754	return mRoot;
1755	}
1756
1757
1758	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1759	{
1760	// the node became a leaf -> evaluate stats for leafs
1761	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
1762
1763
1764	if (data.mPvs > mVspStats.maxPvs)
1765	{
1766	mVspStats.maxPvs = data.mPvs;
1767	}
1768
1769	mVspStats.pvs += data.mPvs;
1770
1771	if (data.mDepth < mVspStats.minDepth)
1772	{
1773	mVspStats.minDepth = data.mDepth;
1774	}
1775
1776	if (data.mDepth >= mTermMaxDepth)
1777	{
1778	++ mVspStats.maxDepthNodes;
1779	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1780	}
1781
1782	// accumulate rays to compute rays / leaf
1783	mVspStats.accumRays += (int)data.mRays->size();
1784
1785	if (data.mPvs < mTermMinPvs)
1786	++ mVspStats.minPvsNodes;
1787
1788	if ((int)data.mRays->size() < mTermMinRays)
1789	++ mVspStats.minRaysNodes;
1790
1791	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1792	++ mVspStats.maxRayContribNodes;
1793
1794	if (data.mProbability <= mTermMinProbability)
1795	++ mVspStats.minProbabilityNodes;
1796
1797	// accumulate depth to compute average depth
1798	mVspStats.accumDepth += data.mDepth;
1799
1800	++ mCreatedViewCells;
1801
1802	#ifdef _DEBUG
1803	Debug << "BSP stats: "
1804	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1805	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1806	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1807	<< "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
1808	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1809	#endif
1810	}
1811
1812
1813	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1814	{
1815	ViewCell::NewMail();
1816	CollectViewCells(mRoot, onlyValid, viewCells, true);
1817	}
1818
1819
1820	void VspTree::CollapseViewCells()
1821	{
1822	// TODO matt
1823	#if HAS_TO_BE_REDONE
1824	stack<VspNode *> nodeStack;
1825
1826	if (!mRoot)
1827	return;
1828
1829	nodeStack.push(mRoot);
1830
1831	while (!nodeStack.empty())
1832	{
1833	VspNode *node = nodeStack.top();
1834	nodeStack.pop();
1835
1836	if (node->IsLeaf())
1837	{
1838	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1839
1840	if (!viewCell->GetValid())
1841	{
1842	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1843
1844	ViewCellContainer leaves;
1845	mViewCellsTree->CollectLeaves(viewCell, leaves);
1846
1847	ViewCellContainer::const_iterator it, it_end = leaves.end();
1848
1849	for (it = leaves.begin(); it != it_end; ++ it)
1850	{
1851	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
1852	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1853	++ mVspStats.invalidLeaves;
1854	}
1855
1856	// add to unbounded view cell
1857	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1858	DEL_PTR(viewCell);
1859	}
1860	}
1861	else
1862	{
1863	VspInterior interior = dynamic_cast<VspInterior >(node);
1864
1865	nodeStack.push(interior->GetFront());
1866	nodeStack.push(interior->GetBack());
1867	}
1868	}
1869
1870	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1871	#endif
1872	}
1873
1874
1875	void VspTree::CollectRays(VssRayContainer &rays)
1876	{
1877	vector<VspLeaf *> leaves;
1878	CollectLeaves(leaves);
1879
1880	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1881
1882	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1883	{
1884	VspLeaf leaf = lit;
1885	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1886
1887	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1888	rays.push_back(*rit);
1889	}
1890	}
1891
1892
1893	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1894	{
1895	mViewCellsManager = vcm;
1896	}
1897
1898
1899	void VspTree::ValidateTree()
1900	{
1901	mVspStats.invalidLeaves = 0;
1902
1903	stack<VspNode *> nodeStack;
1904
1905	if (!mRoot)
1906	return;
1907
1908	nodeStack.push(mRoot);
1909
1910	while (!nodeStack.empty())
1911	{
1912	VspNode *node = nodeStack.top();
1913	nodeStack.pop();
1914
1915	if (node->IsLeaf())
1916	{
1917	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1918
1919	if (!leaf->GetViewCell()->GetValid())
1920	++ mVspStats.invalidLeaves;
1921
1922	// validity flags don't match => repair
1923	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1924	{
1925	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1926	PropagateUpValidity(leaf);
1927	}
1928	}
1929	else
1930	{
1931	VspInterior interior = dynamic_cast<VspInterior >(node);
1932
1933	nodeStack.push(interior->GetFront());
1934	nodeStack.push(interior->GetBack());
1935	}
1936	}
1937
1938	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1939	}
1940
1941
1942
1943	void VspTree::CollectViewCells(VspNode *root,
1944	bool onlyValid,
1945	ViewCellContainer &viewCells,
1946	bool onlyUnmailed) const
1947	{
1948	stack<VspNode *> nodeStack;
1949
1950	if (!root)
1951	return;
1952
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: