Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp @ 682

Revision 682, 87.6 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: