Context Navigation

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

Revision 2543, 92.4 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: