Context Navigation

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

Revision 2176, 85.6 KB checked in by mattausch, 18 years ago (diff)
removed using namespace std from .h

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

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

Download in other formats: