Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 538

Revision 538, 70.8 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
	20	//-- static members
[508]	21
[482]	22	/** Evaluates split plane classification with respect to the plane's
[463]	23	contribution for a minimum number of ray splits.
	24	*/
	25	const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
[482]	26	/** Evaluates split plane classification with respect to the plane's
[463]	27	contribution for balanced rays.
	28	*/
	29	const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
	30
[535]	31	int BspMergeCandidate::sMaxPvsSize = 0;
[463]	32
[482]	33	int VspBspTree::sFrontId = 0;
[463]	34	int VspBspTree::sBackId = 0;
	35	int VspBspTree::sFrontAndBackId = 0;
	36
[485]	37	float BspMergeCandidate::sOverallCost = 0;
[463]	38
[508]	39	/********************************************************************/
	40	/* class VspBspTree implementation */
	41	/********************************************************************/
[463]	42
[482]	43	VspBspTree::VspBspTree():
[463]	44	mRoot(NULL),
[472]	45	mPvsUseArea(true),
[478]	46	mCostNormalizer(Limits::Small),
	47	mViewCellsManager(NULL),
[497]	48	mOutOfBoundsCell(NULL),
[508]	49	mShowInvalidSpace(false),
	50	mStoreRays(false)
[463]	51	{
[486]	52	bool randomize = false;
	53	environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
	54	if (randomize)
	55	Randomize(); // initialise random generator for heuristics
[463]	56
	57	//-- termination criteria for autopartition
	58	environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
	59	environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
	60	environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
[482]	61	environment->GetFloatValue("VspBspTree.Termination.minArea", mTermMinArea);
[463]	62	environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
	63	environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
[472]	64	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
	65	environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
[463]	66
	67	//-- factors for bsp tree split plane heuristics
	68	environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
	69	environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
	70	environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
	71
[482]	72	//-- max cost ratio for early tree termination
[472]	73	environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[482]	74
[463]	75	//-- partition criteria
	76	environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
	77	environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
	78	environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
	79
	80	environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
	81	environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
	82
[478]	83	// maximum and minimum number of view cells
	84	environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
	85	environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
[480]	86	environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
[463]	87
[485]	88	environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	89	environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
[478]	90
[517]	91	environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
[511]	92
[508]	93	//-- termination criteria for axis aligned split
	94	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
	95	mTermMaxRayContriForAxisAligned);
	96	environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
	97	mTermMinRaysForAxisAligned);
[487]	98
[508]	99	//environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
	100	environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
	101
[478]	102	//-- debug output
[473]	103	Debug << "***** VSP BSP options ****** " << endl;
	104	Debug << "max depth: " << mTermMaxDepth << endl;
	105	Debug << "min PVS: " << mTermMinPvs << endl;
	106	Debug << "min area: " << mTermMinArea << endl;
	107	Debug << "min rays: " << mTermMinRays << endl;
	108	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	109	//Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
	110	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	111	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	112	Debug << "max view cells: " << mMaxViewCells << endl;
	113	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
	114	Debug << "max plane candidates: " << mMaxRayCandidates << endl;
[486]	115	Debug << "randomize: " << randomize << endl;
[482]	116
[463]	117	Debug << "Split plane strategy: ";
	118	if (mSplitPlaneStrategy & RANDOM_POLYGON)
[474]	119	{
[463]	120	Debug << "random polygon ";
[474]	121	}
[463]	122	if (mSplitPlaneStrategy & AXIS_ALIGNED)
[472]	123	{
[463]	124	Debug << "axis aligned ";
[472]	125	}
[463]	126	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
[472]	127	{
[474]	128	mCostNormalizer += mLeastRaySplitsFactor;
[463]	129	Debug << "least ray splits ";
[472]	130	}
[463]	131	if (mSplitPlaneStrategy & BALANCED_RAYS)
[472]	132	{
[474]	133	mCostNormalizer += mBalancedRaysFactor;
[463]	134	Debug << "balanced rays ";
[472]	135	}
[463]	136	if (mSplitPlaneStrategy & PVS)
[472]	137	{
[474]	138	mCostNormalizer += mPvsFactor;
[463]	139	Debug << "pvs";
[472]	140	}
[482]	141
[489]	142
[480]	143	mSplitCandidates = new vector<SortableEntry>;
[463]	144
	145	Debug << endl;
	146	}
	147
[508]	148	BspViewCell *VspBspTree::GetOutOfBoundsCell()
	149	{
	150	return mOutOfBoundsCell;
	151	}
[463]	152
[508]	153
[489]	154	BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
	155	{
	156	if (!mOutOfBoundsCell)
[508]	157	{
[489]	158	mOutOfBoundsCell = new BspViewCell();
[508]	159	mOutOfBoundsCell->SetId(-1);
	160	}
[489]	161	return mOutOfBoundsCell;
	162	}
	163
	164
[482]	165	const BspTreeStatistics &VspBspTree::GetStatistics() const
[463]	166	{
	167	return mStat;
	168	}
	169
	170
	171	VspBspTree::~VspBspTree()
	172	{
	173	DEL_PTR(mRoot);
[480]	174	DEL_PTR(mSplitCandidates);
[463]	175	}
	176
[482]	177	int VspBspTree::AddMeshToPolygons(Mesh *mesh,
	178	PolygonContainer &polys,
[463]	179	MeshInstance *parent)
	180	{
	181	FaceContainer::const_iterator fi;
[482]	182
[463]	183	// copy the face data to polygons
	184	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
	185	{
	186	Polygon3 poly = new Polygon3((fi), mesh);
[482]	187
[463]	188	if (poly->Valid(mEpsilon))
	189	{
	190	poly->mParent = parent; // set parent intersectable
	191	polys.push_back(poly);
	192	}
	193	else
	194	DEL_PTR(poly);
	195	}
	196	return (int)mesh->mFaces.size();
	197	}
	198
[482]	199	int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
	200	PolygonContainer &polys,
[463]	201	int maxObjects)
	202	{
[482]	203	int limit = (maxObjects > 0) ?
[463]	204	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
[482]	205
[463]	206	int polysSize = 0;
	207
	208	for (int i = 0; i < limit; ++ i)
	209	{
	210	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
	211	{
	212	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
[482]	213	polysSize +=
	214	AddMeshToPolygons(viewCells[i]->GetMesh(),
	215	polys,
[463]	216	viewCells[i]);
	217	}
	218	}
	219
	220	return polysSize;
	221	}
	222
[482]	223	int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
	224	PolygonContainer &polys,
[463]	225	int maxObjects)
	226	{
[482]	227	int limit = (maxObjects > 0) ?
[463]	228	Min((int)objects.size(), maxObjects) : (int)objects.size();
[482]	229
[463]	230	for (int i = 0; i < limit; ++i)
	231	{
	232	Intersectable object = objects[i];//it;
	233	Mesh *mesh = NULL;
	234
	235	switch (object->Type()) // extract the meshes
	236	{
	237	case Intersectable::MESH_INSTANCE:
	238	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
	239	break;
	240	case Intersectable::VIEW_CELL:
	241	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
	242	break;
	243	// TODO: handle transformed mesh instances
	244	default:
	245	Debug << "intersectable type not supported" << endl;
	246	break;
	247	}
[482]	248
[463]	249	if (mesh) // copy the mesh data to polygons
	250	{
	251	mBox.Include(object->GetBox()); // add to BSP tree aabb
[485]	252	AddMeshToPolygons(mesh, polys, NULL);
[463]	253	}
	254	}
	255
	256	return (int)polys.size();
	257	}
	258
[483]	259	void VspBspTree::Construct(const VssRayContainer &sampleRays,
	260	AxisAlignedBox3 *forcedBoundingBox)
[463]	261	{
	262	mStat.nodes = 1;
	263	mBox.Initialize(); // initialise BSP tree bounding box
[482]	264
[484]	265	if (forcedBoundingBox)
	266	mBox = *forcedBoundingBox;
	267
[463]	268	PolygonContainer polys;
	269	RayInfoContainer *rays = new RayInfoContainer();
	270
	271	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	272
	273	long startTime = GetTime();
	274
[480]	275	cout << "Extracting polygons from rays ... ";
[463]	276
	277	Intersectable::NewMail();
	278
[511]	279	int numObj = 0;
[463]	280	//-- extract polygons intersected by the rays
	281	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	282	{
	283	VssRay ray = rit;
[482]	284
[484]	285	if ((mBox.IsInside(ray->mTermination) \|\| !forcedBoundingBox) &&
	286	ray->mTerminationObject &&
	287	!ray->mTerminationObject->Mailed())
[463]	288	{
	289	ray->mTerminationObject->Mail();
	290	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mTerminationObject);
	291	AddMeshToPolygons(obj->GetMesh(), polys, obj);
[511]	292	++ numObj;
[484]	293	//-- compute bounding box
	294	if (!forcedBoundingBox)
	295	mBox.Include(ray->mTermination);
[463]	296	}
	297
[484]	298	if ((mBox.IsInside(ray->mOrigin) \|\| !forcedBoundingBox) &&
	299	ray->mOriginObject &&
	300	!ray->mOriginObject->Mailed())
[463]	301	{
	302	ray->mOriginObject->Mail();
	303	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mOriginObject);
	304	AddMeshToPolygons(obj->GetMesh(), polys, obj);
[511]	305	++ numObj;
	306
[484]	307	//-- compute bounding box
	308	if (!forcedBoundingBox)
	309	mBox.Include(ray->mOrigin);
[463]	310	}
	311	}
	312
[511]	313	mMaxPvs = (int)(mMaxPvsRatio * (float)numObj);
[535]	314
	315	Debug << "maximal pvs (i.e., view cell considered as valid: " << mMaxPvs << endl;
[463]	316	//-- store rays
	317	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	318	{
	319	VssRay ray = rit;
[482]	320
[463]	321	float minT, maxT;
	322
[483]	323	// TODO: not very efficient to implictly cast between rays types
[463]	324	if (mBox.GetRaySegment(*ray, minT, maxT))
	325	{
	326	float len = ray->Length();
[482]	327
	328	if (!len)
[463]	329	len = Limits::Small;
[482]	330
[463]	331	rays->push_back(RayInfo(ray, minT / len, maxT / len));
	332	}
	333	}
	334
[474]	335	mTermMinArea *= mBox.SurfaceArea(); // normalize
[463]	336	mStat.polys = (int)polys.size();
	337
[475]	338	cout << "finished" << endl;
[463]	339
[482]	340	Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
[475]	341	<< (int)sampleRays.size() << " rays in "
	342	<< TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
	343
[463]	344	Construct(polys, rays);
	345
	346	// clean up polygons
	347	CLEAR_CONTAINER(polys);
	348	}
	349
[508]	350
	351	// return memory usage in MB
	352	float VspBspTree::GetMemUsage() const
	353	{
	354	return
	355	(sizeof(VspBspTree) +
	356	mStat.Leaves() * sizeof(BspLeaf) +
	357	mStat.Interior() * sizeof(BspInterior) +
	358	mStat.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
	359	}
	360
	361
	362
[463]	363	void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
	364	{
[472]	365	VspBspTraversalStack tStack;
[463]	366
	367	mRoot = new BspLeaf();
	368
	369	// constrruct root node geometry
	370	BspNodeGeometry *geom = new BspNodeGeometry();
	371	ConstructGeometry(mRoot, *geom);
	372
[482]	373	VspBspTraversalData tData(mRoot,
	374	new PolygonContainer(polys),
[463]	375	0,
[482]	376	rays,
	377	ComputePvsSize(*rays),
	378	geom->GetArea(),
[463]	379	geom);
	380
	381	tStack.push(tData);
	382
	383	mStat.Start();
	384	cout << "Contructing vsp bsp tree ... ";
	385
	386	long startTime = GetTime();
[508]	387
	388	bool mOutOfMemory = false;
[482]	389
[478]	390	while (!tStack.empty())
[463]	391	{
	392	tData = tStack.top();
[508]	393	tStack.pop();
[463]	394
[508]	395	if (0 && !mOutOfMemory)
	396	{
	397	float mem = GetMemUsage();
[478]	398
[508]	399	if (mem > mMaxMemory)
	400	{
	401	mOutOfMemory = true;
	402	Debug << "memory limit reached: " << mem << endl;
	403	}
	404	}
	405
[463]	406	// subdivide leaf node
	407	BspNode *r = Subdivide(tStack, tData);
	408
	409	if (r == mRoot)
[482]	410	Debug << "VSP BSP tree construction time spent at root: "
[475]	411	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl << endl;
[463]	412	}
	413
[508]	414	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl;
[463]	415	cout << "finished\n";
	416
	417	mStat.Stop();
	418	}
	419
[508]	420
[478]	421	bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
[463]	422	{
[482]	423	return
[463]	424	(((int)data.mRays->size() <= mTermMinRays) \|\|
[473]	425	(data.mPvs <= mTermMinPvs) \|\|
[463]	426	(data.mArea <= mTermMinArea) \|\|
[485]	427	(mStat.Leaves() >= mMaxViewCells) \|\|
[535]	428	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
[463]	429	(data.mDepth >= mTermMaxDepth));
	430	}
	431
[508]	432
[482]	433	BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
[463]	434	VspBspTraversalData &tData)
	435	{
[473]	436	BspNode *newNode = tData.mNode;
	437
[508]	438	if (!mOutOfMemory \|\| !TerminationCriteriaMet(tData))
[473]	439	{
	440	PolygonContainer coincident;
[482]	441
[473]	442	VspBspTraversalData tFrontData;
	443	VspBspTraversalData tBackData;
	444
	445	// create new interior node and two leaf nodes
	446	// or return leaf as it is (if maxCostRatio missed)
	447	newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
	448
	449	if (!newNode->IsLeaf()) //-- continue subdivision
	450	{
	451	// push the children on the stack
	452	tStack.push(tFrontData);
	453	tStack.push(tBackData);
	454
	455	// delete old leaf node
[482]	456	DEL_PTR(tData.mNode);
[473]	457	}
	458	}
[482]	459
[478]	460	//-- terminate traversal and create new view cell
[473]	461	if (newNode->IsLeaf())
[463]	462	{
[473]	463	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
[489]	464	BspViewCell *viewCell;
[482]	465
[487]	466	if (!CheckValid(tData))
	467	{
	468	leaf->SetTreeValid(false);
	469	PropagateUpValidity(leaf);
[489]	470	// view cell for invalid view space
	471	viewCell = GetOrCreateOutOfBoundsCell();
[490]	472	++ mStat.invalidLeaves;
[487]	473	}
[489]	474	else
[508]	475	{ // create new view cell for this leaf
[489]	476	viewCell = new BspViewCell();
	477	}
	478
[463]	479	leaf->SetViewCell(viewCell);
[487]	480
	481	//-- update pvs
	482	int conSamp = 0, sampCon = 0;
	483	AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
	484
	485	mStat.contributingSamples += conSamp;
	486	mStat.sampleContributions += sampCon;
	487
	488	//-- store additional info
[478]	489	if (mStoreRays)
	490	{
	491	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	492	for (it = tData.mRays->begin(); it != it_end; ++ it)
	493	leaf->mVssRays.push_back((*it).mRay);
	494	}
	495
[469]	496	viewCell->mLeaves.push_back(leaf);
[478]	497	viewCell->SetArea(tData.mArea);
[485]	498	leaf->mArea = tData.mArea;
[463]	499
[487]	500	EvaluateLeafStats(tData);
[463]	501	}
[482]	502
[473]	503	//-- cleanup
[478]	504	tData.Clear();
[463]	505
[472]	506	return newNode;
[463]	507	}
	508
[487]	509
[472]	510	BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
	511	VspBspTraversalData &frontData,
	512	VspBspTraversalData &backData,
	513	PolygonContainer &coincident)
[463]	514	{
	515	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
[508]	516
[463]	517	// select subdivision plane
[472]	518	Plane3 splitPlane;
[508]	519	int maxCostMisses = tData.mMaxCostMisses;
	520	bool success = SelectPlane(splitPlane,
	521	leaf,
	522	tData,
	523	frontData,
	524	backData);
	525	if (!success)
[472]	526	{
	527	++ maxCostMisses;
[463]	528
[480]	529	if (maxCostMisses > mTermMissTolerance)
[473]	530	{
	531	// terminate branch because of max cost
[482]	532	++ mStat.maxCostNodes;
[472]	533	return leaf;
[474]	534	}
[472]	535	}
	536
[473]	537	mStat.nodes += 2;
	538
	539	//-- subdivide further
[482]	540	BspInterior *interior = new BspInterior(splitPlane);
[472]	541
[463]	542	#ifdef _DEBUG
	543	Debug << interior << endl;
	544	#endif
[482]	545
[473]	546	//-- the front and back traversal data is filled with the new values
	547	frontData.mDepth = tData.mDepth + 1;
[508]	548	frontData.mPolygons = new PolygonContainer();
[473]	549	frontData.mRays = new RayInfoContainer();
[508]	550
[473]	551	backData.mDepth = tData.mDepth + 1;
[508]	552	backData.mPolygons = new PolygonContainer();
[473]	553	backData.mRays = new RayInfoContainer();
[508]	554
[473]	555	// subdivide rays
[482]	556	SplitRays(interior->GetPlane(),
	557	*tData.mRays,
	558	*frontData.mRays,
[463]	559	*backData.mRays);
[482]	560
[473]	561	// subdivide polygons
[491]	562	SplitPolygons(interior->GetPlane(),
	563	*tData.mPolygons,
	564	*frontData.mPolygons,
	565	*backData.mPolygons,
	566	coincident);
[463]	567
[482]	568
[473]	569	// how often was max cost ratio missed in this branch?
[472]	570	frontData.mMaxCostMisses = maxCostMisses;
	571	backData.mMaxCostMisses = maxCostMisses;
	572
	573	// compute pvs
[463]	574	frontData.mPvs = ComputePvsSize(*frontData.mRays);
	575	backData.mPvs = ComputePvsSize(*backData.mRays);
	576
[508]	577	// split front and back node geometry and compute area
	578	if (mPvsUseArea)
[463]	579	{
[508]	580	// if not already computed
	581	if (!frontData.mGeometry && !backData.mGeometry)
	582	{
	583	frontData.mGeometry = new BspNodeGeometry();
	584	backData.mGeometry = new BspNodeGeometry();
[482]	585
[508]	586	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
	587	*backData.mGeometry,
	588	interior->GetPlane(),
	589	mBox,
	590	mEpsilon);
	591
	592	frontData.mArea = frontData.mGeometry->GetArea();
	593	backData.mArea = backData.mGeometry->GetArea();
	594	}
[463]	595	}
[508]	596	else
	597	{
	598	frontData.mArea = (float)frontData.mRays->size();
	599	backData.mArea = (float)backData.mRays->size();
	600	}
[463]	601
	602	//-- create front and back leaf
	603
	604	BspInterior *parent = leaf->GetParent();
	605
	606	// replace a link from node's parent
[487]	607	if (parent)
[463]	608	{
	609	parent->ReplaceChildLink(leaf, interior);
	610	interior->SetParent(parent);
	611	}
	612	else // new root
	613	{
	614	mRoot = interior;
	615	}
	616
	617	// and setup child links
	618	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
[482]	619
[463]	620	frontData.mNode = interior->GetFront();
	621	backData.mNode = interior->GetBack();
[473]	622
[463]	623	//DEL_PTR(leaf);
	624	return interior;
	625	}
	626
[508]	627
[463]	628	void VspBspTree::AddToPvs(BspLeaf *leaf,
[482]	629	const RayInfoContainer &rays,
[463]	630	int &sampleContributions,
	631	int &contributingSamples)
	632	{
	633	sampleContributions = 0;
	634	contributingSamples = 0;
	635
	636	RayInfoContainer::const_iterator it, it_end = rays.end();
	637
	638	ViewCell *vc = leaf->GetViewCell();
	639
	640	// add contributions from samples to the PVS
	641	for (it = rays.begin(); it != it_end; ++ it)
	642	{
	643	int contribution = 0;
	644	VssRay ray = (it).mRay;
[482]	645
[463]	646	if (ray->mTerminationObject)
	647	contribution += vc->GetPvs().AddSample(ray->mTerminationObject);
[482]	648
[463]	649	if (ray->mOriginObject)
	650	contribution += vc->GetPvs().AddSample(ray->mOriginObject);
	651
	652	if (contribution)
	653	{
	654	sampleContributions += contribution;
	655	++ contributingSamples;
	656	}
	657	//leaf->mVssRays.push_back(ray);
	658	}
	659	}
	660
[480]	661	void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
[463]	662	{
[480]	663	mSplitCandidates->clear();
[463]	664
[480]	665	int requestedSize = 2 * (int)(rays.size());
	666	// creates a sorted split candidates array
	667	if (mSplitCandidates->capacity() > 500000 &&
	668	requestedSize < (int)(mSplitCandidates->capacity()/10) )
	669	{
[482]	670	delete mSplitCandidates;
[480]	671	mSplitCandidates = new vector<SortableEntry>;
	672	}
[463]	673
[480]	674	mSplitCandidates->reserve(requestedSize);
	675
	676	// insert all queries
	677	for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
[473]	678	{
[480]	679	bool positive = (*ri).mRay->HasPosDir(axis);
	680	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
[482]	681	(ri).ExtrapOrigin(axis), (ri).mRay));
[480]	682
	683	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
[482]	684	(ri).ExtrapTermination(axis), (ri).mRay));
[473]	685	}
[480]	686
	687	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
[463]	688	}
	689
[480]	690	float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
	691	const AxisAlignedBox3 &box,
	692	const int pvsSize,
[481]	693	const int &axis,
[480]	694	float &position)
[463]	695	{
[480]	696	int raysBack;
	697	int raysFront;
	698	int pvsBack;
	699	int pvsFront;
[463]	700
[480]	701	SortSplitCandidates(rays, axis);
	702
[463]	703	// go through the lists, count the number of objects left and right
	704	// and evaluate the following cost funcion:
[480]	705	// C = ct_div_ci + (qlrl + qrrr)/queries
	706
	707	int rl = 0, rr = (int)rays.size();
	708	int pl = 0, pr = pvsSize;
	709
[463]	710	float minBox = box.Min(axis);
	711	float maxBox = box.Max(axis);
[480]	712	float sizeBox = maxBox - minBox;
	713
	714	float minBand = minBox + 0.1f*(maxBox - minBox);
	715	float maxBand = minBox + 0.9f*(maxBox - minBox);
	716
	717	float sum = rr*sizeBox;
[463]	718	float minSum = 1e20f;
	719
[480]	720	Intersectable::NewMail();
	721
	722	// set all object as belonging to the fron pvs
	723	for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
[463]	724	{
[480]	725	if ((*ri).mRay->IsActive())
[463]	726	{
[480]	727	Intersectable object = (ri).mRay->mTerminationObject;
	728
	729	if (object)
[482]	730	{
[480]	731	if (!object->Mailed())
	732	{
	733	object->Mail();
	734	object->mCounter = 1;
	735	}
	736	else
	737	++ object->mCounter;
[482]	738	}
[463]	739	}
[480]	740	}
	741
	742	Intersectable::NewMail();
	743
	744	for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
	745	ci < mSplitCandidates->end(); ++ ci)
	746	{
	747	VssRay *ray;
	748
	749	switch ((*ci).type)
[463]	750	{
[480]	751	case SortableEntry::ERayMin:
	752	{
	753	++ rl;
[482]	754	ray = (VssRay ) (ci).ray;
	755
[480]	756	Intersectable *object = ray->mTerminationObject;
[482]	757
[480]	758	if (object && !object->Mailed())
	759	{
	760	object->Mail();
	761	++ pl;
	762	}
	763	break;
	764	}
	765	case SortableEntry::ERayMax:
	766	{
	767	-- rr;
[482]	768	ray = (VssRay ) (ci).ray;
[463]	769
[480]	770	Intersectable *object = ray->mTerminationObject;
	771
	772	if (object)
	773	{
	774	if (-- object->mCounter == 0)
[482]	775	-- pr;
[480]	776	}
	777
	778	break;
	779	}
	780	}
	781
	782	// Note: sufficient to compare size of bounding boxes of front and back side?
	783	if ((ci).value > minBand && (ci).value < maxBand)
	784	{
	785	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
	786
	787	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
	788	// cout<<"cost= "<<sum<<endl;
	789
	790	if (sum < minSum)
[463]	791	{
	792	minSum = sum;
	793	position = (*ci).value;
	794
[480]	795	raysBack = rl;
	796	raysFront = rr;
	797
	798	pvsBack = pl;
	799	pvsFront = pr;
	800
[463]	801	}
	802	}
	803	}
	804
[480]	805	float oldCost = (float)pvsSize;
	806	float newCost = mCtDivCi + minSum / sizeBox;
	807	float ratio = newCost / oldCost;
[463]	808
[480]	809	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	810	// <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
	811
	812	return ratio;
[463]	813	}
	814
[480]	815
[482]	816	float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
[491]	817	const VspBspTraversalData &tData,
[495]	818	int &axis,
[508]	819	BspNodeGeometry **frontGeom,
	820	BspNodeGeometry **backGeom,
	821	float &frontArea,
	822	float &backArea)
[463]	823	{
[508]	824	const bool useCostHeuristics = false;
	825
	826	//-- regular split
	827	float nPosition[3];
	828	float nCostRatio[3];
	829	float nFrontArea[3];
	830	float nBackArea[3];
	831
	832	BspNodeGeometry *nFrontGeom[3];
	833	BspNodeGeometry *nBackGeom[3];
	834
	835	int bestAxis = -1;
	836
	837	// create bounding box of node extent
[463]	838	AxisAlignedBox3 box;
	839	box.Initialize();
[508]	840
[509]	841	if (1 && mPvsUseArea)
	842	{
	843	PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
[480]	844
[509]	845	for(it = tData.mGeometry->mPolys.begin(); it < it_end; ++ it)
	846	box.Include((it));
	847	}
	848	else
	849	{
	850	RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
[480]	851
[509]	852	for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
	853	box.Include((*ri).ExtrapTermination());
	854	}
[463]	855
[508]	856	int sAxis = box.Size().DrivingAxis();
[480]	857
[495]	858	for (axis = 0; axis < 3; ++ axis)
[480]	859	{
[508]	860	nFrontGeom[axis] = new BspNodeGeometry();
	861	nBackGeom[axis] = new BspNodeGeometry();
	862
[480]	863	if (!mOnlyDrivingAxis \|\| axis == sAxis)
[463]	864	{
[480]	865	if (!useCostHeuristics)
	866	{
	867	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	868	Vector3 normal(0,0,0); normal[axis] = 1;
[508]	869
	870	nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]),
	871	tData, nFrontGeom[axis], nBackGeom[axis],
	872	nFrontArea[axis], nBackArea[axis]);
[480]	873	}
[481]	874	else
	875	{
[482]	876	nCostRatio[axis] =
[481]	877	BestCostRatioHeuristics(*tData.mRays,
	878	box,
	879	tData.mPvs,
	880	axis,
	881	nPosition[axis]);
	882	}
	883
[480]	884	if (bestAxis == -1)
	885	{
	886	bestAxis = axis;
	887	}
	888
	889	else if (nCostRatio[axis] < nCostRatio[bestAxis])
	890	{
	891	bestAxis = axis;
	892	}
	893
[463]	894	}
	895	}
	896
[495]	897	//-- assign values
	898	axis = bestAxis;
[508]	899	frontArea = nFrontArea[bestAxis];
	900	backArea = nBackArea[bestAxis];
[495]	901
[508]	902	// assign best split nodes geometry
	903	*frontGeom = nFrontGeom[bestAxis];
	904	*backGeom = nBackGeom[bestAxis];
	905	// and delete other geometry
	906	delete nFrontGeom[(bestAxis + 1) % 3];
	907	delete nBackGeom[(bestAxis + 2) % 3];
[495]	908
[508]	909	//-- split plane
	910	Vector3 normal(0,0,0); normal[bestAxis] = 1;
[480]	911	plane = Plane3(normal, nPosition[bestAxis]);
[508]	912
[480]	913	return nCostRatio[bestAxis];
[463]	914	}
	915
[480]	916
[508]	917	bool VspBspTree::SelectPlane(Plane3 &bestPlane,
	918	BspLeaf *leaf,
	919	VspBspTraversalData &data,
	920	VspBspTraversalData &frontData,
	921	VspBspTraversalData &backData)
[491]	922	{
[508]	923	// simplest strategy: just take next polygon
	924	if (mSplitPlaneStrategy & RANDOM_POLYGON)
[491]	925	{
[508]	926	if (!data.mPolygons->empty())
	927	{
	928	const int randIdx =
	929	(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
	930	Polygon3 nextPoly = (data.mPolygons)[randIdx];
[491]	931
[508]	932	bestPlane = nextPoly->GetSupportingPlane();
	933	return true;
	934	}
[491]	935	}
	936
[508]	937	//-- use heuristics to find appropriate plane
[491]	938
[508]	939	// intermediate plane
	940	Plane3 plane;
	941	float lowestCost = MAX_FLOAT;
[517]	942
	943	// decides if the first few splits should be only axisAligned
[508]	944	const bool onlyAxisAligned =
	945	(mSplitPlaneStrategy & AXIS_ALIGNED) &&
	946	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
	947	((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
	948
	949	const int limit = onlyAxisAligned ? 0 :
	950	Min((int)data.mPolygons->size(), mMaxPolyCandidates);
[491]	951
[508]	952	float candidateCost;
[491]	953
[508]	954	int maxIdx = (int)data.mPolygons->size();
[491]	955
[508]	956	for (int i = 0; i < limit; ++ i)
[491]	957	{
[508]	958	//-- assure that no index is taken twice
	959	const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
	960	Polygon3 poly = (data.mPolygons)[candidateIdx];
[491]	961
[508]	962	// swap candidate to the end to avoid testing same plane
	963	std::swap((data.mPolygons)[maxIdx], (data.mPolygons)[candidateIdx]);
	964	//Polygon3 poly = (data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
[491]	965
[508]	966	// evaluate current candidate
	967	BspNodeGeometry fGeom, bGeom;
	968	float fArea, bArea;
	969	plane = poly->GetSupportingPlane();
	970	candidateCost = SplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
[491]	971
[508]	972	if (candidateCost < lowestCost)
[491]	973	{
[508]	974	bestPlane = plane;
	975	lowestCost = candidateCost;
[491]	976	}
	977	}
	978
[508]	979	//-- evaluate axis aligned splits
	980	int axis;
	981	BspNodeGeometry fGeom, bGeom;
	982	float fArea, bArea;
[491]	983
[508]	984	candidateCost = SelectAxisAlignedPlane(plane, data, axis,
	985	&fGeom, &bGeom,
	986	fArea, bArea);
[491]	987
[508]	988	if (candidateCost < lowestCost)
	989	{
	990	bestPlane = plane;
	991	lowestCost = candidateCost;
[491]	992
[508]	993	//-- assign already computed values
	994	frontData.mGeometry = fGeom;
	995	backData.mGeometry = bGeom;
	996	frontData.mArea = fArea;
	997	backData.mArea = bArea;
[491]	998
[508]	999	//! error also computed if cost ratio is missed
	1000	++ mStat.splits[axis];
	1001	}
	1002	else
[463]	1003	{
[508]	1004	DEL_PTR(fGeom);
	1005	DEL_PTR(bGeom);
[463]	1006	}
	1007
[508]	1008	#ifdef _DEBUG
	1009	Debug << "plane lowest cost: " << lowestCost << endl;
	1010	#endif
	1011
	1012	// cost ratio miss
	1013	if (lowestCost > mTermMaxCostRatio)
	1014	return false;
	1015
	1016	return true;
[463]	1017	}
	1018
[480]	1019
[473]	1020	Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
[482]	1021	{
[473]	1022	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
[482]	1023
[473]	1024	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
	1025	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
	1026
	1027	const Vector3 pt = (maxPt + minPt) * 0.5;
	1028	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
	1029
	1030	return Plane3(normal, pt);
	1031	}
	1032
[480]	1033
[473]	1034	Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
[482]	1035	{
[473]	1036	Vector3 pt[3];
[482]	1037
[473]	1038	int idx[3];
	1039	int cmaxT = 0;
	1040	int cminT = 0;
	1041	bool chooseMin = false;
	1042
	1043	for (int j = 0; j < 3; ++ j)
	1044	{
	1045	idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
[482]	1046
[473]	1047	if (idx[j] >= (int)rays.size())
	1048	{
	1049	idx[j] -= (int)rays.size();
[482]	1050
[473]	1051	chooseMin = (cminT < 2);
	1052	}
	1053	else
	1054	chooseMin = (cmaxT < 2);
	1055
	1056	RayInfo rayInf = rays[idx[j]];
	1057	pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
[482]	1058	}
[473]	1059
	1060	return Plane3(pt[0], pt[1], pt[2]);
	1061	}
	1062
	1063	Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
[482]	1064	{
[473]	1065	Vector3 pt[3];
[482]	1066
[473]	1067	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
	1068	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
	1069
	1070	// check if rays different
	1071	if (idx1 == idx2)
	1072	idx2 = (idx2 + 1) % (int)rays.size();
	1073
	1074	const RayInfo ray1 = rays[idx1];
	1075	const RayInfo ray2 = rays[idx2];
	1076
	1077	// normal vector of the plane parallel to both lines
	1078	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
	1079
	1080	// vector from line 1 to line 2
[479]	1081	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
[482]	1082
[473]	1083	// project vector on normal to get distance
	1084	const float dist = DotProd(vd, norm);
	1085
	1086	// point on plane lies halfway between the two planes
	1087	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
	1088
	1089	return Plane3(norm, planePt);
	1090	}
	1091
[495]	1092
[463]	1093	inline void VspBspTree::GenerateUniqueIdsForPvs()
	1094	{
	1095	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
	1096	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
	1097	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
	1098	}
	1099
[495]	1100
[482]	1101	float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
[508]	1102	const VspBspTraversalData &data,
	1103	BspNodeGeometry &geomFront,
	1104	BspNodeGeometry &geomBack,
	1105	float &areaFront,
	1106	float &areaBack) const
[463]	1107	{
[472]	1108	float cost = 0;
[463]	1109
	1110	float sumBalancedRays = 0;
	1111	float sumRaySplits = 0;
[482]	1112
[508]	1113	int pvsFront = 0;
	1114	int pvsBack = 0;
[463]	1115
[508]	1116	// probability that view point lies in back / front node
[463]	1117	float pOverall = 0;
	1118	float pFront = 0;
	1119	float pBack = 0;
	1120
[508]	1121	int raysFront = 0;
	1122	int raysBack = 0;
	1123	int totalPvs = 0;
	1124
[463]	1125	if (mSplitPlaneStrategy & PVS)
	1126	{
	1127	// create unique ids for pvs heuristics
[495]	1128	GenerateUniqueIdsForPvs();
[482]	1129
[463]	1130	if (mPvsUseArea) // use front and back cell areas to approximate volume
[482]	1131	{
[463]	1132	// construct child geometry with regard to the candidate split plane
[508]	1133	data.mGeometry->SplitGeometry(geomFront,
	1134	geomBack,
[463]	1135	candidatePlane,
	1136	mBox,
	1137	mEpsilon);
[482]	1138
[508]	1139	areaFront = geomFront.GetArea();
	1140	areaBack = geomBack.GetArea();
[463]	1141
[508]	1142	pBack = areaBack;
	1143	pFront = areaFront;
[463]	1144	pOverall = data.mArea;
	1145	}
[508]	1146	else // use number of rays to approximate volume
	1147	{
	1148	pOverall = (float)data.mRays->size();
	1149	pFront = (float)raysFront;
	1150	pBack = (float)raysBack;
	1151	}
[463]	1152	}
[482]	1153
[463]	1154	int limit;
	1155	bool useRand;
	1156
[491]	1157	// choose test rays randomly if too much
[463]	1158	if ((int)data.mRays->size() > mMaxTests)
	1159	{
	1160	useRand = true;
	1161	limit = mMaxTests;
	1162	}
	1163	else
	1164	{
	1165	useRand = false;
	1166	limit = (int)data.mRays->size();
	1167	}
[508]	1168
[463]	1169	for (int i = 0; i < limit; ++ i)
	1170	{
[508]	1171	const int testIdx = useRand ?
	1172	(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
[463]	1173	RayInfo rayInf = (*data.mRays)[testIdx];
	1174
	1175	float t;
[508]	1176	VssRay *ray = rayInf.mRay;
[463]	1177	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
	1178
[508]	1179	if (cf >= 0)
	1180	++ raysFront;
	1181	if (cf <= 0)
	1182	++ raysBack;
	1183
[463]	1184	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
	1185	{
	1186	sumBalancedRays += cf;
	1187	}
[482]	1188
[463]	1189	if (mSplitPlaneStrategy & BALANCED_RAYS)
	1190	{
	1191	if (cf == 0)
	1192	++ sumRaySplits;
	1193	}
	1194
	1195	if (mSplitPlaneStrategy & PVS)
	1196	{
[508]	1197	// find front and back pvs for origing and termination object
	1198	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
	1199	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
[463]	1200	}
	1201	}
	1202
	1203	const float raysSize = (float)data.mRays->size() + Limits::Small;
[482]	1204
[463]	1205	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
[472]	1206	cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
[463]	1207
	1208	if (mSplitPlaneStrategy & BALANCED_RAYS)
[495]	1209	cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
[482]	1210
[472]	1211	// pvs criterium
[463]	1212	if (mSplitPlaneStrategy & PVS)
	1213	{
[508]	1214	const float oldCost = pOverall * (float)totalPvs + Limits::Small;
	1215	cost += mPvsFactor * (pvsFront * pFront + pvsBack * pBack) / oldCost;
[463]	1216	}
	1217
	1218	#ifdef _DEBUG
[474]	1219	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
[508]	1220	<< " frontpvs: " << pvsFront << " pFront: " << pFront
	1221	<< " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
[463]	1222	#endif
[482]	1223
[474]	1224	// normalize cost by sum of linear factors
	1225	return cost / (float)mCostNormalizer;
[463]	1226	}
	1227
[508]	1228
[463]	1229	void VspBspTree::AddObjToPvs(Intersectable *obj,
	1230	const int cf,
	1231	int &frontPvs,
[508]	1232	int &backPvs,
	1233	int &totalPvs) const
[463]	1234	{
	1235	if (!obj)
	1236	return;
[508]	1237
	1238	if ((obj->mMailbox != sFrontId) &&
	1239	(obj->mMailbox != sBackId) &&
	1240	(obj->mMailbox != sFrontAndBackId))
	1241	{
	1242	++ totalPvs;
	1243	}
	1244
[463]	1245	// TODO: does this really belong to no pvs?
	1246	//if (cf == Ray::COINCIDENT) return;
	1247
	1248	// object belongs to both PVS
	1249	if (cf >= 0)
	1250	{
[482]	1251	if ((obj->mMailbox != sFrontId) &&
[463]	1252	(obj->mMailbox != sFrontAndBackId))
	1253	{
	1254	++ frontPvs;
[508]	1255
[463]	1256	if (obj->mMailbox == sBackId)
[482]	1257	obj->mMailbox = sFrontAndBackId;
[463]	1258	else
[482]	1259	obj->mMailbox = sFrontId;
[463]	1260	}
	1261	}
[482]	1262
[463]	1263	if (cf <= 0)
	1264	{
	1265	if ((obj->mMailbox != sBackId) &&
	1266	(obj->mMailbox != sFrontAndBackId))
	1267	{
	1268	++ backPvs;
[508]	1269
[463]	1270	if (obj->mMailbox == sFrontId)
[482]	1271	obj->mMailbox = sFrontAndBackId;
[463]	1272	else
[482]	1273	obj->mMailbox = sBackId;
[463]	1274	}
	1275	}
	1276	}
	1277
[491]	1278
[503]	1279	void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
	1280	const bool onlyUnmailed,
	1281	const int maxPvsSize) const
[463]	1282	{
	1283	stack<BspNode *> nodeStack;
	1284	nodeStack.push(mRoot);
[482]	1285
	1286	while (!nodeStack.empty())
[463]	1287	{
	1288	BspNode *node = nodeStack.top();
	1289	nodeStack.pop();
[489]	1290
[482]	1291	if (node->IsLeaf())
[463]	1292	{
[490]	1293	// test if this leaf is in valid view space
[503]	1294	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	1295	if (leaf->TreeValid() &&
[508]	1296	(!onlyUnmailed \|\| !leaf->Mailed()) &&
[503]	1297	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
[490]	1298	{
	1299	leaves.push_back(leaf);
	1300	}
[482]	1301	}
	1302	else
[463]	1303	{
	1304	BspInterior interior = dynamic_cast<BspInterior >(node);
	1305
	1306	nodeStack.push(interior->GetBack());
	1307	nodeStack.push(interior->GetFront());
	1308	}
	1309	}
	1310	}
	1311
[489]	1312
[463]	1313	AxisAlignedBox3 VspBspTree::GetBoundingBox() const
	1314	{
	1315	return mBox;
	1316	}
	1317
[489]	1318
[463]	1319	BspNode *VspBspTree::GetRoot() const
	1320	{
	1321	return mRoot;
	1322	}
	1323
[489]	1324
[463]	1325	void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
	1326	{
	1327	// the node became a leaf -> evaluate stats for leafs
	1328	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
	1329
	1330	// store maximal and minimal depth
	1331	if (data.mDepth > mStat.maxDepth)
	1332	mStat.maxDepth = data.mDepth;
	1333
[485]	1334	if (data.mPvs > mStat.maxPvs)
	1335	mStat.maxPvs = data.mPvs;
[508]	1336
[463]	1337	if (data.mDepth < mStat.minDepth)
	1338	mStat.minDepth = data.mDepth;
[508]	1339
[463]	1340	if (data.mDepth >= mTermMaxDepth)
	1341	++ mStat.maxDepthNodes;
[508]	1342	// accumulate rays to compute rays / leaf
	1343	mStat.accumRays += (int)data.mRays->size();
[463]	1344
[437]	1345	if (data.mPvs < mTermMinPvs)
	1346	++ mStat.minPvsNodes;
	1347
	1348	if ((int)data.mRays->size() < mTermMinRays)
	1349	++ mStat.minRaysNodes;
	1350
	1351	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
	1352	++ mStat.maxRayContribNodes;
[482]	1353
	1354	if (data.mArea <= mTermMinArea)
[463]	1355	++ mStat.minAreaNodes;
[508]	1356
[474]	1357	// accumulate depth to compute average depth
	1358	mStat.accumDepth += data.mDepth;
[463]	1359
	1360	#ifdef _DEBUG
	1361	Debug << "BSP stats: "
	1362	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	1363	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	1364	<< "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
[482]	1365	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[463]	1366	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
	1367	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
	1368	#endif
	1369	}
	1370
	1371	int VspBspTree::CastRay(Ray &ray)
	1372	{
	1373	int hits = 0;
[482]	1374
[463]	1375	stack<BspRayTraversalData> tStack;
[482]	1376
[463]	1377	float maxt, mint;
	1378
	1379	if (!mBox.GetRaySegment(ray, mint, maxt))
	1380	return 0;
	1381
	1382	Intersectable::NewMail();
	1383
	1384	Vector3 entp = ray.Extrap(mint);
	1385	Vector3 extp = ray.Extrap(maxt);
[482]	1386
[463]	1387	BspNode *node = mRoot;
	1388	BspNode *farChild = NULL;
[482]	1389
[463]	1390	while (1)
	1391	{
[482]	1392	if (!node->IsLeaf())
[463]	1393	{
	1394	BspInterior in = dynamic_cast<BspInterior >(node);
	1395
	1396	Plane3 splitPlane = in->GetPlane();
	1397	const int entSide = splitPlane.Side(entp);
	1398	const int extSide = splitPlane.Side(extp);
	1399
	1400	if (entSide < 0)
	1401	{
	1402	node = in->GetBack();
	1403
	1404	if(extSide <= 0) // plane does not split ray => no far child
	1405	continue;
[482]	1406
[463]	1407	farChild = in->GetFront(); // plane splits ray
	1408
	1409	} else if (entSide > 0)
	1410	{
	1411	node = in->GetFront();
	1412
	1413	if (extSide >= 0) // plane does not split ray => no far child
	1414	continue;
	1415
[482]	1416	farChild = in->GetBack(); // plane splits ray
[463]	1417	}
	1418	else // ray and plane are coincident
	1419	{
	1420	// WHAT TO DO IN THIS CASE ?
	1421	//break;
	1422	node = in->GetFront();
	1423	continue;
	1424	}
	1425
	1426	// push data for far child
	1427	tStack.push(BspRayTraversalData(farChild, extp, maxt));
	1428
	1429	// find intersection of ray segment with plane
	1430	float t;
	1431	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
	1432	maxt *= t;
[482]	1433
[463]	1434	} else // reached leaf => intersection with view cell
	1435	{
	1436	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
[482]	1437
[463]	1438	if (!leaf->GetViewCell()->Mailed())
	1439	{
	1440	//ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
	1441	leaf->GetViewCell()->Mail();
	1442	++ hits;
	1443	}
[482]	1444
[463]	1445	//-- fetch the next far child from the stack
	1446	if (tStack.empty())
	1447	break;
[482]	1448
[463]	1449	entp = extp;
	1450	mint = maxt; // NOTE: need this?
	1451
	1452	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
	1453	break;
	1454
	1455	BspRayTraversalData &s = tStack.top();
	1456
	1457	node = s.mNode;
	1458	extp = s.mExitPoint;
	1459	maxt = s.mMaxT;
	1460
	1461	tStack.pop();
	1462	}
	1463	}
	1464
	1465	return hits;
	1466	}
	1467
[532]	1468
[463]	1469	void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
	1470	{
[532]	1471	ViewCell::NewMail();
	1472	CollectViewCells(mRoot, viewCells, true);
	1473	}
	1474
	1475
	1476	void VspBspTree::CollectViewCells(BspNode *root,
	1477	ViewCellContainer &viewCells,
	1478	bool onlyUnmailed) const
	1479	{
[498]	1480	stack<BspNode *> nodeStack;
[463]	1481
[538]	1482	if (!root)
[508]	1483	return;
[463]	1484
[538]	1485	nodeStack.push(root);
[498]	1486
	1487	while (!nodeStack.empty())
	1488	{
	1489	BspNode *node = nodeStack.top();
	1490	nodeStack.pop();
	1491
	1492	if (node->IsLeaf())
	1493	{
	1494	if (!mShowInvalidSpace && node->TreeValid())
	1495	{
	1496	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
	1497
[532]	1498	if (!onlyUnmailed \|\| !viewCell->Mailed())
[498]	1499	{
	1500	viewCell->Mail();
	1501	viewCells.push_back(viewCell);
	1502	}
	1503	}
	1504	}
	1505	else
	1506	{
	1507	BspInterior interior = dynamic_cast<BspInterior >(node);
[508]	1508
[498]	1509	nodeStack.push(interior->GetFront());
	1510	nodeStack.push(interior->GetBack());
	1511	}
	1512	}
[463]	1513	}
	1514
	1515
	1516	float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
	1517	{
	1518	float len = 0;
	1519
	1520	RayInfoContainer::const_iterator it, it_end = rays.end();
	1521
	1522	for (it = rays.begin(); it != it_end; ++ it)
	1523	len += (*it).SegmentLength();
	1524
	1525	return len;
	1526	}
	1527
[479]	1528
[463]	1529	int VspBspTree::SplitRays(const Plane3 &plane,
[482]	1530	RayInfoContainer &rays,
	1531	RayInfoContainer &frontRays,
[463]	1532	RayInfoContainer &backRays)
	1533	{
	1534	int splits = 0;
	1535
	1536	while (!rays.empty())
	1537	{
	1538	RayInfo bRay = rays.back();
[473]	1539	rays.pop_back();
	1540
[463]	1541	VssRay *ray = bRay.mRay;
[473]	1542	float t;
[463]	1543
[485]	1544	// get classification and receive new t
[463]	1545	const int cf = bRay.ComputeRayIntersection(plane, t);
[482]	1546
[463]	1547	switch (cf)
	1548	{
	1549	case -1:
	1550	backRays.push_back(bRay);
	1551	break;
	1552	case 1:
	1553	frontRays.push_back(bRay);
	1554	break;
[482]	1555	case 0:
	1556	{
[485]	1557	//-- split ray
	1558	//-- test if start point behind or in front of plane
	1559	const int side = plane.Side(bRay.ExtrapOrigin());
	1560
	1561	if (side <= 0)
	1562	{
	1563	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	1564	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	1565	}
	1566	else
	1567	{
	1568	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	1569	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	1570	}
[463]	1571	}
	1572	break;
	1573	default:
[485]	1574	Debug << "Should not come here" << endl;
[463]	1575	break;
	1576	}
	1577	}
	1578
	1579	return splits;
	1580	}
	1581
[479]	1582
[463]	1583	void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
	1584	{
	1585	BspNode *lastNode;
	1586
	1587	do
	1588	{
	1589	lastNode = n;
	1590
	1591	// want to get planes defining geometry of this node => don't take
	1592	// split plane of node itself
	1593	n = n->GetParent();
[482]	1594
[463]	1595	if (n)
	1596	{
	1597	BspInterior interior = dynamic_cast<BspInterior >(n);
	1598	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
	1599
	1600	if (interior->GetFront() != lastNode)
	1601	halfSpace.ReverseOrientation();
	1602
	1603	halfSpaces.push_back(halfSpace);
	1604	}
	1605	}
	1606	while (n);
	1607	}
	1608
[485]	1609
[482]	1610	void VspBspTree::ConstructGeometry(BspNode *n,
[503]	1611	BspNodeGeometry &geom) const
[463]	1612	{
[437]	1613	vector<Plane3> halfSpaces;
	1614	ExtractHalfSpaces(n, halfSpaces);
	1615
	1616	PolygonContainer candidatePolys;
	1617
	1618	// bounded planes are added to the polygons (reverse polygons
	1619	// as they have to be outfacing
	1620	for (int i = 0; i < (int)halfSpaces.size(); ++ i)
	1621	{
	1622	Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
[482]	1623
[448]	1624	if (p->Valid(mEpsilon))
[437]	1625	{
	1626	candidatePolys.push_back(p->CreateReversePolygon());
	1627	DEL_PTR(p);
	1628	}
	1629	}
	1630
	1631	// add faces of bounding box (also could be faces of the cell)
	1632	for (int i = 0; i < 6; ++ i)
	1633	{
	1634	VertexContainer vertices;
[482]	1635
[437]	1636	for (int j = 0; j < 4; ++ j)
	1637	vertices.push_back(mBox.GetFace(i).mVertices[j]);
	1638
	1639	candidatePolys.push_back(new Polygon3(vertices));
	1640	}
	1641
	1642	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
	1643	{
	1644	// polygon is split by all other planes
	1645	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
	1646	{
	1647	if (i == j) // polygon and plane are coincident
	1648	continue;
	1649
	1650	VertexContainer splitPts;
	1651	Polygon3 frontPoly, backPoly;
	1652
[482]	1653	const int cf =
[448]	1654	candidatePolys[i]->ClassifyPlane(halfSpaces[j],
	1655	mEpsilon);
[482]	1656
[437]	1657	switch (cf)
	1658	{
	1659	case Polygon3::SPLIT:
	1660	frontPoly = new Polygon3();
	1661	backPoly = new Polygon3();
	1662
[482]	1663	candidatePolys[i]->Split(halfSpaces[j],
	1664	*frontPoly,
[448]	1665	*backPoly,
	1666	mEpsilon);
[437]	1667
	1668	DEL_PTR(candidatePolys[i]);
	1669
[448]	1670	if (frontPoly->Valid(mEpsilon))
[437]	1671	candidatePolys[i] = frontPoly;
	1672	else
	1673	DEL_PTR(frontPoly);
	1674
	1675	DEL_PTR(backPoly);
	1676	break;
	1677	case Polygon3::BACK_SIDE:
	1678	DEL_PTR(candidatePolys[i]);
	1679	break;
	1680	// just take polygon as it is
	1681	case Polygon3::FRONT_SIDE:
	1682	case Polygon3::COINCIDENT:
	1683	default:
	1684	break;
	1685	}
	1686	}
[482]	1687
[437]	1688	if (candidatePolys[i])
[503]	1689	geom.mPolys.push_back(candidatePolys[i]);
[437]	1690	}
[463]	1691	}
	1692
[485]	1693
	1694	void VspBspTree::ConstructGeometry(BspViewCell *vc,
[503]	1695	BspNodeGeometry &vcGeom) const
[463]	1696	{
[469]	1697	vector<BspLeaf *> leaves = vc->mLeaves;
[463]	1698	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
	1699
	1700	for (it = leaves.begin(); it != it_end; ++ it)
	1701	ConstructGeometry(*it, vcGeom);
	1702	}
	1703
[485]	1704
[482]	1705	int VspBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
[463]	1706	const bool onlyUnmailed) const
	1707	{
[503]	1708	BspNodeGeometry geom;
[498]	1709	ConstructGeometry(n, geom);
[463]	1710
	1711	stack<BspNode *> nodeStack;
	1712	nodeStack.push(mRoot);
[482]	1713
[500]	1714	// split planes from the root to this node
	1715	// needed to verify that we found neighbor leaf
[463]	1716	vector<Plane3> halfSpaces;
	1717	ExtractHalfSpaces(n, halfSpaces);
	1718
[482]	1719	while (!nodeStack.empty())
[463]	1720	{
	1721	BspNode *node = nodeStack.top();
	1722	nodeStack.pop();
	1723
	1724	if (node->IsLeaf())
[498]	1725
[490]	1726	{ // test if this leaf is in valid view space
	1727	if (node->TreeValid() &&
	1728	node != n &&
	1729	(!onlyUnmailed \|\| !node->Mailed()))
[463]	1730	{
	1731	// test all planes of current node if candidate really
	1732	// is neighbour
[503]	1733	BspNodeGeometry neighborCandidate;
[463]	1734	ConstructGeometry(node, neighborCandidate);
[482]	1735
[463]	1736	bool isAdjacent = true;
	1737	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
	1738	{
[482]	1739	const int cf =
[503]	1740	Polygon3::ClassifyPlane(neighborCandidate.mPolys,
[463]	1741	halfSpaces[i],
	1742	mEpsilon);
	1743
	1744	if (cf == Polygon3::BACK_SIDE)
	1745	isAdjacent = false;
	1746	}
[500]	1747	// neighbor was found
[463]	1748	if (isAdjacent)
	1749	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
	1750	}
	1751	}
[482]	1752	else
[463]	1753	{
	1754	BspInterior interior = dynamic_cast<BspInterior >(node);
[482]	1755
[503]	1756	const int cf = Polygon3::ClassifyPlane(geom.mPolys,
[482]	1757	interior->GetPlane(),
[463]	1758	mEpsilon);
	1759
	1760	if (cf == Polygon3::FRONT_SIDE)
	1761	nodeStack.push(interior->GetFront());
	1762	else
	1763	if (cf == Polygon3::BACK_SIDE)
	1764	nodeStack.push(interior->GetBack());
[482]	1765	else
[463]	1766	{
	1767	// random decision
	1768	nodeStack.push(interior->GetBack());
	1769	nodeStack.push(interior->GetFront());
	1770	}
	1771	}
	1772	}
[482]	1773
[463]	1774	return (int)neighbors.size();
	1775	}
	1776
[489]	1777
[463]	1778	BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
	1779	{
	1780	stack<BspNode *> nodeStack;
	1781	nodeStack.push(mRoot);
[482]	1782
[463]	1783	int mask = rand();
[482]	1784
	1785	while (!nodeStack.empty())
[463]	1786	{
	1787	BspNode *node = nodeStack.top();
	1788	nodeStack.pop();
[482]	1789
	1790	if (node->IsLeaf())
[463]	1791	{
	1792	return dynamic_cast<BspLeaf *>(node);
[482]	1793	}
	1794	else
[463]	1795	{
	1796	BspInterior interior = dynamic_cast<BspInterior >(node);
	1797	BspNode *next;
[503]	1798	BspNodeGeometry geom;
[482]	1799
[463]	1800	// todo: not very efficient: constructs full cell everytime
[498]	1801	ConstructGeometry(interior, geom);
[463]	1802
[503]	1803	const int cf =
	1804	Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
[463]	1805
	1806	if (cf == Polygon3::BACK_SIDE)
	1807	next = interior->GetFront();
	1808	else
	1809	if (cf == Polygon3::FRONT_SIDE)
	1810	next = interior->GetFront();
[482]	1811	else
[463]	1812	{
	1813	// random decision
	1814	if (mask & 1)
	1815	next = interior->GetBack();
	1816	else
	1817	next = interior->GetFront();
	1818	mask = mask >> 1;
	1819	}
	1820
	1821	nodeStack.push(next);
	1822	}
	1823	}
[482]	1824
[463]	1825	return NULL;
	1826	}
	1827
	1828	BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
	1829	{
	1830	stack<BspNode *> nodeStack;
[482]	1831
[463]	1832	nodeStack.push(mRoot);
	1833
	1834	int mask = rand();
[482]	1835
	1836	while (!nodeStack.empty())
[463]	1837	{
	1838	BspNode *node = nodeStack.top();
	1839	nodeStack.pop();
[482]	1840
	1841	if (node->IsLeaf())
[463]	1842	{
	1843	if ( (!onlyUnmailed \|\| !node->Mailed()) )
	1844	return dynamic_cast<BspLeaf *>(node);
	1845	}
[482]	1846	else
[463]	1847	{
	1848	BspInterior interior = dynamic_cast<BspInterior >(node);
	1849
	1850	// random decision
	1851	if (mask & 1)
	1852	nodeStack.push(interior->GetBack());
	1853	else
	1854	nodeStack.push(interior->GetFront());
	1855
	1856	mask = mask >> 1;
	1857	}
	1858	}
[482]	1859
[463]	1860	return NULL;
	1861	}
	1862
	1863	int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
	1864	{
	1865	int pvsSize = 0;
	1866
	1867	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	1868
	1869	Intersectable::NewMail();
	1870
	1871	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	1872	{
	1873	VssRay ray = (rit).mRay;
[482]	1874
[463]	1875	if (ray->mOriginObject)
	1876	{
	1877	if (!ray->mOriginObject->Mailed())
	1878	{
	1879	ray->mOriginObject->Mail();
	1880	++ pvsSize;
	1881	}
	1882	}
	1883	if (ray->mTerminationObject)
	1884	{
	1885	if (!ray->mTerminationObject->Mailed())
	1886	{
	1887	ray->mTerminationObject->Mail();
	1888	++ pvsSize;
	1889	}
	1890	}
	1891	}
	1892
	1893	return pvsSize;
	1894	}
	1895
	1896	float VspBspTree::GetEpsilon() const
	1897	{
	1898	return mEpsilon;
	1899	}
	1900
	1901
	1902	int VspBspTree::SplitPolygons(const Plane3 &plane,
[482]	1903	PolygonContainer &polys,
	1904	PolygonContainer &frontPolys,
	1905	PolygonContainer &backPolys,
[463]	1906	PolygonContainer &coincident) const
	1907	{
	1908	int splits = 0;
	1909
	1910	while (!polys.empty())
	1911	{
	1912	Polygon3 *poly = polys.back();
	1913	polys.pop_back();
	1914
	1915	// classify polygon
	1916	const int cf = poly->ClassifyPlane(plane, mEpsilon);
	1917
	1918	switch (cf)
	1919	{
	1920	case Polygon3::COINCIDENT:
	1921	coincident.push_back(poly);
[482]	1922	break;
	1923	case Polygon3::FRONT_SIDE:
[463]	1924	frontPolys.push_back(poly);
	1925	break;
	1926	case Polygon3::BACK_SIDE:
	1927	backPolys.push_back(poly);
	1928	break;
	1929	case Polygon3::SPLIT:
	1930	backPolys.push_back(poly);
	1931	frontPolys.push_back(poly);
	1932	++ splits;
	1933	break;
	1934	default:
	1935	Debug << "SHOULD NEVER COME HERE\n";
	1936	break;
	1937	}
	1938	}
	1939
	1940	return splits;
	1941	}
[466]	1942
	1943
[469]	1944	int VspBspTree::CastLineSegment(const Vector3 &origin,
	1945	const Vector3 &termination,
	1946	vector<ViewCell *> &viewcells)
[466]	1947	{
[469]	1948	int hits = 0;
	1949	stack<BspRayTraversalData> tStack;
[482]	1950
[469]	1951	float mint = 0.0f, maxt = 1.0f;
[482]	1952
[469]	1953	Intersectable::NewMail();
[482]	1954
[469]	1955	Vector3 entp = origin;
	1956	Vector3 extp = termination;
[482]	1957
[469]	1958	BspNode *node = mRoot;
	1959	BspNode *farChild = NULL;
[482]	1960
[485]	1961	float t;
[482]	1962	while (1)
[469]	1963	{
[482]	1964	if (!node->IsLeaf())
[469]	1965	{
	1966	BspInterior in = dynamic_cast<BspInterior >(node);
[482]	1967
[469]	1968	Plane3 splitPlane = in->GetPlane();
[485]	1969
[469]	1970	const int entSide = splitPlane.Side(entp);
	1971	const int extSide = splitPlane.Side(extp);
[482]	1972
[485]	1973	if (entSide < 0)
[469]	1974	{
	1975	node = in->GetBack();
[485]	1976	// plane does not split ray => no far child
	1977	if (extSide <= 0)
[469]	1978	continue;
[482]	1979
[469]	1980	farChild = in->GetFront(); // plane splits ray
[485]	1981	}
	1982	else if (entSide > 0)
[469]	1983	{
	1984	node = in->GetFront();
[482]	1985
[469]	1986	if (extSide >= 0) // plane does not split ray => no far child
	1987	continue;
[482]	1988
	1989	farChild = in->GetBack(); // plane splits ray
[469]	1990	}
[485]	1991	else // ray end point on plane
	1992	{ // NOTE: what to do if ray is coincident with plane?
	1993	if (extSide < 0)
	1994	node = in->GetBack();
[487]	1995	else
[485]	1996	node = in->GetFront();
[487]	1997
[485]	1998	continue; // no far child
[469]	1999	}
[482]	2000
[469]	2001	// push data for far child
[485]	2002	tStack.push(BspRayTraversalData(farChild, extp));
[482]	2003
[469]	2004	// find intersection of ray segment with plane
	2005	extp = splitPlane.FindIntersection(origin, extp, &t);
[485]	2006	}
	2007	else
[469]	2008	{
	2009	// reached leaf => intersection with view cell
	2010	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
[482]	2011
	2012	if (!leaf->GetViewCell()->Mailed())
[469]	2013	{
	2014	viewcells.push_back(leaf->GetViewCell());
	2015	leaf->GetViewCell()->Mail();
	2016	++ hits;
	2017	}
[482]	2018
[469]	2019	//-- fetch the next far child from the stack
	2020	if (tStack.empty())
	2021	break;
[482]	2022
[469]	2023	entp = extp;
[485]	2024
[469]	2025	BspRayTraversalData &s = tStack.top();
[482]	2026
[469]	2027	node = s.mNode;
	2028	extp = s.mExitPoint;
[482]	2029
[469]	2030	tStack.pop();
	2031	}
[466]	2032	}
[487]	2033
[469]	2034	return hits;
[466]	2035	}
[478]	2036
[485]	2037	int VspBspTree::TreeDistance(BspNode n1, BspNode n2) const
[482]	2038	{
	2039	std::deque<BspNode *> path1;
	2040	BspNode *p1 = n1;
[479]	2041
[482]	2042	// create path from node 1 to root
	2043	while (p1)
	2044	{
	2045	if (p1 == n2) // second node on path
	2046	return (int)path1.size();
	2047
	2048	path1.push_front(p1);
	2049	p1 = p1->GetParent();
	2050	}
	2051
	2052	int depth = n2->GetDepth();
	2053	int d = depth;
	2054
	2055	BspNode *p2 = n2;
	2056
	2057	// compare with same depth
	2058	while (1)
	2059	{
	2060	if ((d < (int)path1.size()) && (p2 == path1[d]))
	2061	return (depth - d) + ((int)path1.size() - 1 - d);
	2062
	2063	-- d;
	2064	p2 = p2->GetParent();
	2065	}
	2066
	2067	return 0; // never come here
	2068	}
	2069
[501]	2070	BspNode VspBspTree::CollapseTree(BspNode node, int &collapsed)
[479]	2071	{
[495]	2072	if (node->IsLeaf())
[479]	2073	return node;
	2074
[492]	2075	BspInterior interior = dynamic_cast<BspInterior >(node);
	2076
[501]	2077	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
	2078	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
[492]	2079
[479]	2080	if (front->IsLeaf() && back->IsLeaf())
	2081	{
	2082	BspLeaf frontLeaf = dynamic_cast<BspLeaf >(front);
	2083	BspLeaf backLeaf = dynamic_cast<BspLeaf >(back);
	2084
	2085	//-- collapse tree
	2086	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
	2087	{
	2088	BspViewCell *vc = frontLeaf->GetViewCell();
	2089
	2090	BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
[489]	2091	leaf->SetTreeValid(frontLeaf->TreeValid());
[482]	2092
[479]	2093	// replace a link from node's parent
	2094	if (leaf->GetParent())
	2095	leaf->GetParent()->ReplaceChildLink(node, leaf);
[517]	2096	else
	2097	mRoot = leaf;
	2098
[501]	2099	++ collapsed;
[479]	2100	delete interior;
	2101
	2102	return leaf;
	2103	}
	2104	}
	2105
[495]	2106	return node;
	2107	}
	2108
	2109
[501]	2110	int VspBspTree::CollapseTree()
[495]	2111	{
[501]	2112	int collapsed = 0;
[517]	2113
[501]	2114	(void)CollapseTree(mRoot, collapsed);
[517]	2115
[485]	2116	// revalidate leaves
[517]	2117	RepairViewCellsLeafLists();
[501]	2118
	2119	return collapsed;
[479]	2120	}
	2121
	2122
[517]	2123	void VspBspTree::RepairViewCellsLeafLists()
[492]	2124	{
[479]	2125	// list not valid anymore => clear
[492]	2126	stack<BspNode *> nodeStack;
	2127	nodeStack.push(mRoot);
	2128
	2129	ViewCell::NewMail();
	2130
	2131	while (!nodeStack.empty())
	2132	{
	2133	BspNode *node = nodeStack.top();
	2134	nodeStack.pop();
	2135
	2136	if (node->IsLeaf())
	2137	{
	2138	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2139
	2140	BspViewCell *viewCell = leaf->GetViewCell();
	2141
	2142	if (!viewCell->Mailed())
	2143	{
	2144	viewCell->mLeaves.clear();
	2145	viewCell->Mail();
	2146	}
	2147
	2148	viewCell->mLeaves.push_back(leaf);
	2149	}
	2150	else
	2151	{
	2152	BspInterior interior = dynamic_cast<BspInterior >(node);
	2153
	2154	nodeStack.push(interior->GetFront());
	2155	nodeStack.push(interior->GetBack());
	2156	}
[479]	2157	}
	2158	}
	2159
	2160
[532]	2161	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
	2162
[535]	2163
[532]	2164	int VspBspTree::CastBeam(Beam &beam)
	2165	{
	2166	stack<bspNodePair> nodeStack;
	2167	BspNodeGeometry *rgeom = new BspNodeGeometry();
	2168	ConstructGeometry(mRoot, *rgeom);
	2169
	2170	nodeStack.push(bspNodePair(mRoot, rgeom));
	2171
	2172	ViewCell::NewMail();
	2173
	2174	while (!nodeStack.empty())
	2175	{
	2176	BspNode *node = nodeStack.top().first;
	2177	BspNodeGeometry *geom = nodeStack.top().second;
	2178	nodeStack.pop();
	2179
	2180	AxisAlignedBox3 box;
[535]	2181	box.Initialize();
	2182	geom->IncludeInBox(box);
[532]	2183
[535]	2184	const int side = beam.ComputeIntersection(box);
[532]	2185
	2186	switch (side)
	2187	{
	2188	case -1:
	2189	CollectViewCells(node, beam.mViewCells, true);
	2190	break;
	2191	case 0:
[535]	2192
[532]	2193	if (node->IsLeaf())
	2194	{
[535]	2195	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2196
[532]	2197	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
[535]	2198	{
	2199	leaf->GetViewCell()->Mail();
[532]	2200	beam.mViewCells.push_back(leaf->GetViewCell());
[535]	2201	}
[532]	2202	}
	2203	else
	2204	{
	2205	BspInterior interior = dynamic_cast<BspInterior >(node);
[535]	2206
[538]	2207	BspNode *first = interior->GetFront();
	2208	BspNode *second = interior->GetBack();
[535]	2209
	2210	BspNodeGeometry *firstGeom = new BspNodeGeometry();
	2211	BspNodeGeometry *secondGeom = new BspNodeGeometry();
	2212
[538]	2213	geom->SplitGeometry(*firstGeom,
	2214	*secondGeom,
	2215	interior->GetPlane(),
	2216	mBox,
	2217	mEpsilon);
[535]	2218
[532]	2219	// decide on the order of the nodes
	2220	if (DotProd(beam.mPlanes[0].mNormal,
	2221	interior->GetPlane().mNormal) > 0)
	2222	{
	2223	swap(first, second);
[535]	2224	swap(firstGeom, secondGeom);
[532]	2225	}
	2226
[535]	2227	nodeStack.push(bspNodePair(first, firstGeom));
	2228	nodeStack.push(bspNodePair(second, secondGeom));
[532]	2229	}
[535]	2230
[532]	2231	break;
[538]	2232	default:
[532]	2233	// default: cull
[538]	2234	break;
[532]	2235	}
[538]	2236
[532]	2237	DEL_PTR(geom);
[535]	2238
[532]	2239	}
	2240
[538]	2241	return (int)beam.mViewCells.size();
[532]	2242	}
	2243
	2244
[492]	2245	bool VspBspTree::MergeViewCells(BspLeaf l1, BspLeaf l2) const
	2246	{
	2247	//-- change pointer to view cells of all leaves associated
	2248	//-- with the previous view cells
	2249	BspViewCell *fVc = l1->GetViewCell();
	2250	BspViewCell *bVc = l2->GetViewCell();
	2251
	2252	BspViewCell vc = dynamic_cast<BspViewCell >(
	2253	mViewCellsManager->MergeViewCells(fVc, bVc));
	2254
	2255	// if merge was unsuccessful
	2256	if (!vc) return false;
	2257
	2258	// set new size of view cell
	2259	vc->SetArea(fVc->GetArea() + bVc->GetArea());
	2260
	2261	vector<BspLeaf *> fLeaves = fVc->mLeaves;
	2262	vector<BspLeaf *> bLeaves = bVc->mLeaves;
	2263
	2264	vector<BspLeaf *>::const_iterator it;
	2265
	2266	//-- change view cells of all the other leaves the view cell belongs to
	2267	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	2268	{
	2269	(*it)->SetViewCell(vc);
	2270	vc->mLeaves.push_back(*it);
	2271	}
	2272
	2273	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	2274	{
	2275	(*it)->SetViewCell(vc);
	2276	vc->mLeaves.push_back(*it);
	2277	}
	2278
[485]	2279	vc->Mail();
[492]	2280
	2281	// clean up old view cells
	2282	DEL_PTR(fVc);
	2283	DEL_PTR(bVc);
	2284
[485]	2285	return true;
	2286	}
	2287
	2288
	2289	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
[478]	2290	{
[485]	2291	mViewCellsManager = vcm;
	2292	}
	2293
	2294
[503]	2295	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
[485]	2296	{
[478]	2297	BspLeaf::NewMail();
[508]	2298
[478]	2299	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
	2300
[509]	2301	int candidates = 0;
	2302
[478]	2303	// find merge candidates and push them into queue
	2304	for (it = leaves.begin(); it != it_end; ++ it)
	2305	{
	2306	BspLeaf leaf = it;
[485]	2307
	2308	/// create leaf pvs (needed for post processing
	2309	leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
[478]	2310
[485]	2311	BspMergeCandidate::sOverallCost +=
	2312	leaf->mArea * leaf->mPvs->GetSize();
	2313
	2314	// the same leaves must not be part of two merge candidates
	2315	leaf->Mail();
	2316	vector<BspLeaf *> neighbors;
	2317	FindNeighbors(leaf, neighbors, true);
	2318
	2319	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
	2320
	2321	// TODO: test if at least one ray goes from one leaf to the other
	2322	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
[508]	2323	{
	2324	if ((*nit)->GetViewCell() != leaf->GetViewCell())
[509]	2325	{
[508]	2326	mMergeQueue.push(BspMergeCandidate(leaf, *nit));
[509]	2327	++ candidates;
	2328	}
[485]	2329	}
	2330	}
	2331
[509]	2332	Debug << "found " << candidates << " new merge candidates" << endl;
[508]	2333
[485]	2334	return (int)leaves.size();
	2335	}
	2336
	2337
	2338	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
	2339	{
	2340	vector<BspRay *> bspRays;
	2341
[503]	2342	long startTime = GetTime();
[485]	2343	ConstructBspRays(bspRays, rays);
[508]	2344	Debug << (int)bspRays.size() << " bsp rays constructed in "
	2345	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
[503]	2346
[485]	2347	map<BspLeaf , vector<BspLeaf> > neighborMap;
	2348	vector<BspIntersection>::const_iterator iit;
	2349
[503]	2350	int numLeaves = 0;
[485]	2351
	2352	BspLeaf::NewMail();
	2353
	2354	for (int i = 0; i < (int)bspRays.size(); ++ i)
	2355	{
	2356	BspRay *ray = bspRays[i];
	2357
	2358	// traverse leaves stored in the rays and compare and
	2359	// merge consecutive leaves (i.e., the neighbors in the tree)
	2360	if (ray->intersections.size() < 2)
	2361	continue;
	2362
	2363	iit = ray->intersections.begin();
[489]	2364	BspLeaf leaf = ((iit ++)).mLeaf;
[485]	2365
	2366	// create leaf pvs (needed for post processing)
[489]	2367	if (!leaf->mPvs)
[478]	2368	{
[489]	2369	leaf->mPvs =
	2370	new ObjectPvs(leaf->GetViewCell()->GetPvs());
[478]	2371
[485]	2372	BspMergeCandidate::sOverallCost +=
[489]	2373	leaf->mArea * leaf->mPvs->GetSize();
[485]	2374
[503]	2375	++ numLeaves;
[485]	2376	}
	2377
	2378	// traverse intersections
[489]	2379	// consecutive leaves are neighbors => add them to queue
[485]	2380	for (; iit != ray->intersections.end(); ++ iit)
	2381	{
[489]	2382	// next pair
	2383	BspLeaf *prevLeaf = leaf;
	2384	leaf = (*iit).mLeaf;
	2385
[508]	2386	// view space not valid or same view cell
	2387	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
	2388	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
[489]	2389	continue;
	2390
	2391	// create leaf pvs (needed for post processing)
[485]	2392	if (!leaf->mPvs)
	2393	{
	2394	leaf->mPvs =
	2395	new ObjectPvs(leaf->GetViewCell()->GetPvs());
	2396
	2397	BspMergeCandidate::sOverallCost +=
	2398	leaf->mArea * leaf->mPvs->GetSize();
[478]	2399
[503]	2400	++ numLeaves;
[485]	2401	}
	2402
	2403	vector<BspLeaf *> &neighbors = neighborMap[leaf];
	2404
	2405	bool found = false;
[478]	2406
[485]	2407	// both leaves inserted in queue already =>
	2408	// look if double pair already exists
	2409	if (leaf->Mailed() && prevLeaf->Mailed())
[478]	2410	{
[485]	2411	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
	2412
	2413	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
	2414	if (*it == prevLeaf)
	2415	found = true; // already in queue
	2416	}
	2417
	2418	if (!found)
	2419	{
	2420	// this pair is not in map already
	2421	// => insert into the neighbor map and the queue
	2422	neighbors.push_back(prevLeaf);
	2423	neighborMap[prevLeaf].push_back(leaf);
[478]	2424
[485]	2425	leaf->Mail();
	2426	prevLeaf->Mail();
	2427
	2428	mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
[478]	2429	}
[485]	2430	}
	2431	}
	2432	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
	2433	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
[503]	2434	Debug << "leaves in queue: " << numLeaves << endl;
[485]	2435	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
	2436
	2437	CLEAR_CONTAINER(bspRays);
	2438
[503]	2439	//-- collect the leaves which haven't been found by ray casting
	2440	vector<BspLeaf *> leaves;
	2441	CollectLeaves(leaves, true, mMaxPvs);
[508]	2442	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
	2443	// TODO
	2444	CollectMergeCandidates(leaves);
[503]	2445
	2446	return numLeaves;
[485]	2447	}
	2448
	2449
	2450	void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
	2451	const VssRayContainer &rays)
	2452	{
	2453	VssRayContainer::const_iterator it, it_end = rays.end();
	2454
	2455	for (it = rays.begin(); it != rays.end(); ++ it)
	2456	{
	2457	VssRay vssRay = it;
	2458	BspRay *ray = new BspRay(vssRay);
	2459
	2460	ViewCellContainer viewCells;
	2461
	2462	Ray hray(*vssRay);
	2463	float tmin = 0, tmax = 1.0;
	2464	// matt TODO: remove this!!
	2465	//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
	2466	if (!mBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
	2467	continue;
	2468
	2469	Vector3 origin = hray.Extrap(tmin);
	2470	Vector3 termination = hray.Extrap(tmax);
	2471
	2472	// cast line segment to get intersections with bsp leaves
	2473	CastLineSegment(origin, termination, viewCells);
	2474
	2475	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	2476	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	2477	{
	2478	BspViewCell vc = dynamic_cast<BspViewCell >(*vit);
	2479	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
	2480	//NOTE: not sorted!
	2481	for (it = vc->mLeaves.begin(); it != it_end; ++ it)
	2482	ray->intersections.push_back(BspIntersection(0, *it));
[478]	2483	}
[485]	2484
	2485	bspRays.push_back(ray);
[478]	2486	}
[485]	2487	}
[478]	2488
	2489
[485]	2490	int VspBspTree::MergeViewCells(const VssRayContainer &rays)
	2491	{
[535]	2492	BspMergeCandidate::sMaxPvsSize = mMaxPvs;
	2493
[485]	2494	MergeStatistics mergeStats;
	2495	mergeStats.Start();
	2496	// TODO: REMOVE LATER for performance!
	2497	const bool showMergeStats = true;
	2498	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
	2499	long startTime = GetTime();
[482]	2500
[485]	2501	if (mUseRaysForMerge)
	2502	mergeStats.nodes = CollectMergeCandidates(rays);
	2503	else
[503]	2504	{
	2505	vector<BspLeaf *> leaves;
	2506	CollectLeaves(leaves);
	2507	mergeStats.nodes = CollectMergeCandidates(leaves);
	2508	}
[485]	2509
	2510	mergeStats.collectTime = TimeDiff(startTime, GetTime());
	2511	mergeStats.candidates = (int)mMergeQueue.size();
	2512	startTime = GetTime();
	2513
[490]	2514	int nViewCells = /mergeStats.nodes/ mStat.Leaves() - mStat.invalidLeaves;
[485]	2515
[480]	2516	//-- use priority queue to merge leaf pairs
[485]	2517	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
	2518	(mMergeQueue.top().GetMergeCost() <
[479]	2519	mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
[478]	2520	{
[485]	2521	//Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
	2522	// << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
	2523	// << " max ratio: " << mMergeMaxCostRatio << endl;
	2524	BspMergeCandidate mc = mMergeQueue.top();
	2525	mMergeQueue.pop();
[478]	2526
	2527	// both view cells equal!
	2528	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
	2529	continue;
	2530
	2531	if (mc.Valid())
	2532	{
	2533	ViewCell::NewMail();
	2534	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
[485]	2535	-- nViewCells;
	2536
	2537	++ mergeStats.merged;
	2538
[478]	2539	// increase absolute merge cost
	2540	BspMergeCandidate::sOverallCost += mc.GetMergeCost();
[482]	2541
[485]	2542	if (showMergeStats)
[482]	2543	{
[485]	2544	if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
	2545	++ mergeStats.siblings;
[482]	2546
[485]	2547	const int dist =
	2548	TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
	2549	if (dist > mergeStats.maxTreeDist)
	2550	mergeStats.maxTreeDist = dist;
	2551	mergeStats.accTreeDist += dist;
[482]	2552	}
[478]	2553	}
	2554	// merge candidate not valid, because one of the leaves was already
[485]	2555	// merged with another one => validate and reinsert into queue
[478]	2556	else
[485]	2557	{
[478]	2558	mc.SetValid();
[485]	2559	mMergeQueue.push(mc);
[478]	2560	}
	2561	}
	2562
[485]	2563	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
	2564	mergeStats.Stop();
[478]	2565
[485]	2566	if (showMergeStats)
	2567	Debug << mergeStats << endl << endl;
	2568
	2569	//TODO: should return sample contributions?
	2570	return mergeStats.merged;
	2571	}
[478]	2572
[485]	2573
[508]	2574	ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
[492]	2575	{
	2576	if (mRoot == NULL)
	2577	return NULL;
	2578
	2579	stack<BspNode *> nodeStack;
	2580	nodeStack.push(mRoot);
	2581
	2582	ViewCell *viewcell = NULL;
	2583
	2584	while (!nodeStack.empty()) {
	2585	BspNode *node = nodeStack.top();
	2586	nodeStack.pop();
	2587
	2588	if (node->IsLeaf()) {
	2589	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
	2590	break;
	2591	} else {
	2592
	2593	BspInterior interior = dynamic_cast<BspInterior >(node);
	2594
	2595	// random decision
	2596	if (interior->GetPlane().Side(point) < 0)
	2597	nodeStack.push(interior->GetBack());
	2598	else
	2599	nodeStack.push(interior->GetFront());
	2600	}
	2601	}
	2602
	2603	return viewcell;
	2604	}
	2605
	2606
[485]	2607	int VspBspTree::RefineViewCells(const VssRayContainer &rays)
	2608	{
	2609	int shuffled = 0;
	2610
	2611	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
	2612	BspLeaf::NewMail();
	2613
	2614	// Use priority queue of remaining leaf pairs
	2615	// These candidates either share the same view cells or
	2616	// are border leaves which share a boundary.
	2617	// We test if they can be shuffled, i.e.,
	2618	// either one leaf is made part of one view cell or the other
	2619	// leaf is made part of the other view cell. It is tested if the
	2620	// remaining view cells are "better" than the old ones.
	2621	while (!mMergeQueue.empty())
[482]	2622	{
[485]	2623	BspMergeCandidate mc = mMergeQueue.top();
	2624	mMergeQueue.pop();
	2625
	2626	// both view cells equal or already shuffled
	2627	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
	2628	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
	2629	continue;
	2630
	2631	// candidate for shuffling
	2632	const bool wasShuffled =
	2633	ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
	2634
	2635	//-- stats
	2636	if (wasShuffled)
	2637	++ shuffled;
[482]	2638	}
	2639
[485]	2640	return shuffled;
[478]	2641	}
	2642
	2643
[485]	2644	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
	2645	{
	2646	return pvs1.AddPvs(pvs2);
[478]	2647	}
	2648
[485]	2649	/inline int SubtractedPvsSize(BspViewCell vc, BspLeaf *l, const ObjectPvs &pvs2)
	2650	{
	2651	ObjectPvs pvs;
	2652	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
	2653	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
	2654	if (*it != l)
	2655	pvs.AddPvs((it)->mPvs);
	2656	return pvs.GetSize();
	2657	}*/
[478]	2658
[485]	2659	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
[478]	2660	{
[485]	2661	return pvs1.SubtractPvs(pvs2);
[478]	2662	}
	2663
[485]	2664
	2665	float GetShuffledVcCost(BspLeaf leaf, BspViewCell vc1, BspViewCell *vc2)
	2666	{
	2667	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
	2668	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
	2669	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
	2670
	2671	const float area1 = vc1->GetArea() - leaf->mArea;
	2672	const float area2 = vc2->GetArea() + leaf->mArea;
	2673
	2674	const float cost1 = pvs1 * area1;
	2675	const float cost2 = pvs2 * area2;
	2676
	2677	return cost1 + cost2;
	2678	}
	2679
	2680
	2681	void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
	2682	BspViewCell *vc1,
	2683	BspViewCell *vc2) const
	2684	{
	2685	// compute new pvs and area
	2686	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
	2687	vc2->GetPvs().AddPvs(*leaf->mPvs);
	2688
	2689	vc1->SetArea(vc1->GetArea() - leaf->mArea);
	2690	vc2->SetArea(vc2->GetArea() + leaf->mArea);
	2691
	2692	/// add to second view cell
	2693	vc2->mLeaves.push_back(leaf);
	2694
	2695	// erase leaf from old view cell
	2696	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
	2697
	2698	for (; *it != leaf; ++ it);
	2699	vc1->mLeaves.erase(it);
	2700
	2701	/*vc1->GetPvs().mEntries.clear();
	2702	for (; it != vc1->mLeaves.end(); ++ it)
	2703	{
	2704	if (*it == leaf)
	2705	vc1->mLeaves.erase(it);
	2706	else
	2707	vc1->GetPvs().AddPvs((it)->mPvs);
	2708	}*/
	2709
[486]	2710	leaf->SetViewCell(vc2); // finally change view cell
[485]	2711
	2712	//Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize()
	2713	// << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
	2714
	2715	}
	2716
	2717
	2718	bool VspBspTree::ShuffleLeaves(BspLeaf leaf1, BspLeaf leaf2) const
	2719	{
	2720	BspViewCell *vc1 = leaf1->GetViewCell();
	2721	BspViewCell *vc2 = leaf2->GetViewCell();
	2722
	2723	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
	2724	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
	2725
	2726	const float oldCost = cost1 + cost2;
	2727
	2728	float shuffledCost1 = Limits::Infinity;
	2729	float shuffledCost2 = Limits::Infinity;
	2730
	2731	// the view cell should not be empty after the shuffle
	2732	if (vc1->mLeaves.size() > 1)
	2733	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
	2734	if (vc2->mLeaves.size() > 1)
	2735	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
	2736
	2737	// shuffling unsuccessful
	2738	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
	2739	return false;
	2740
	2741	if (shuffledCost1 < shuffledCost2)
	2742	{
	2743	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
	2744	ShuffleLeaf(leaf1, vc1, vc2);
	2745	leaf1->Mail();
	2746	}
	2747	else
	2748	{
	2749	//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
	2750	ShuffleLeaf(leaf2, vc2, vc1);
	2751	leaf2->Mail();
	2752	}
	2753
	2754	return true;
	2755	}
	2756
[487]	2757	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
	2758	{
	2759	BspNode *node = mRoot;
[485]	2760
[487]	2761	while (1)
	2762	{
	2763	// early exit
	2764	if (node->TreeValid())
	2765	return true;
	2766
	2767	if (node->IsLeaf())
	2768	return false;
	2769
	2770	BspInterior in = dynamic_cast<BspInterior >(node);
[490]	2771
	2772	if (in->GetPlane().Side(viewPoint) <= 0)
[487]	2773	{
	2774	node = in->GetBack();
	2775	}
	2776	else
	2777	{
	2778	node = in->GetFront();
	2779	}
	2780	}
	2781
	2782	// should never come here
	2783	return false;
	2784	}
	2785
	2786
	2787	bool VspBspTree::CheckValid(const VspBspTraversalData &data) const
	2788	{
	2789	return data.mPvs <= mMaxPvs;
	2790	}
	2791
	2792
	2793	void VspBspTree::PropagateUpValidity(BspNode *node)
	2794	{
[490]	2795	while (!node->IsRoot() && node->GetParent()->TreeValid())
[487]	2796	{
	2797	node = node->GetParent();
	2798	node->SetTreeValid(false);
	2799	}
	2800	}
	2801
[508]	2802
	2803	bool VspBspTree::Export(ofstream &stream)
[503]	2804	{
[508]	2805	ExportNode(mRoot, stream);
[487]	2806
[503]	2807	return true;
	2808	}
	2809
	2810
[508]	2811	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
	2812	{
	2813	if (node->IsLeaf())
[503]	2814	{
[508]	2815	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2816
	2817	int id = -1;
	2818	if (leaf->GetViewCell() != mOutOfBoundsCell)
	2819	id = leaf->GetViewCell()->GetId();
[503]	2820
[508]	2821	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
[503]	2822	}
[508]	2823	else
[503]	2824	{
[508]	2825	BspInterior interior = dynamic_cast<BspInterior >(node);
	2826
	2827	Plane3 plane = interior->GetPlane();
	2828	stream << "<Interior plane=\"" << plane.mNormal.x << " "
	2829	<< plane.mNormal.y << " " << plane.mNormal.z << " "
	2830	<< plane.mD << "\">" << endl;
[503]	2831
[508]	2832	ExportNode(interior->GetBack(), stream);
	2833	ExportNode(interior->GetFront(), stream);
[503]	2834
[508]	2835	stream << "</Interior>" << endl;
[503]	2836	}
	2837	}
	2838
[478]	2839	/************************************************************************/
	2840	/* BspMergeCandidate implementation */
	2841	/************************************************************************/
	2842
	2843
	2844	BspMergeCandidate::BspMergeCandidate(BspLeaf l1, BspLeaf l2):
	2845	mMergeCost(0),
	2846	mLeaf1(l1),
	2847	mLeaf2(l2),
	2848	mLeaf1Id(l1->GetViewCell()->mMailbox),
	2849	mLeaf2Id(l2->GetViewCell()->mMailbox)
	2850	{
	2851	EvalMergeCost();
	2852	}
	2853
[485]	2854	float BspMergeCandidate::GetCost(ViewCell *vc) const
	2855	{
	2856	return vc->GetPvs().GetSize() * vc->GetArea();
	2857	}
	2858
[478]	2859	float BspMergeCandidate::GetLeaf1Cost() const
	2860	{
	2861	BspViewCell *vc = mLeaf1->GetViewCell();
[485]	2862	return GetCost(vc);
[478]	2863	}
	2864
	2865	float BspMergeCandidate::GetLeaf2Cost() const
	2866	{
	2867	BspViewCell *vc = mLeaf2->GetViewCell();
[485]	2868	return GetCost(vc);
[478]	2869	}
	2870
	2871	void BspMergeCandidate::EvalMergeCost()
	2872	{
	2873	//-- compute pvs difference
	2874	BspViewCell *vc1 = mLeaf1->GetViewCell();
	2875	BspViewCell *vc2 = mLeaf2->GetViewCell();
	2876
	2877	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
[485]	2878	const int newPvs = diff1 + vc1->GetPvs().GetSize();
[478]	2879
	2880	//-- compute ratio of old cost
	2881	//-- (added size of left and right view cell times pvs size)
	2882	//-- to new rendering cost (size of merged view cell times pvs size)
	2883	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
[482]	2884
[478]	2885	const float newCost =
[485]	2886	(float)newPvs * (vc1->GetArea() + vc2->GetArea());
[478]	2887
	2888	mMergeCost = newCost - oldCost;
[535]	2889	if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
	2890	mMergeCost += 1.0;
[478]	2891	}
	2892
	2893	void BspMergeCandidate::SetLeaf1(BspLeaf *l)
	2894	{
	2895	mLeaf1 = l;
	2896	}
	2897
	2898	void BspMergeCandidate::SetLeaf2(BspLeaf *l)
	2899	{
	2900	mLeaf2 = l;
	2901	}
	2902
	2903	BspLeaf *BspMergeCandidate::GetLeaf1()
	2904	{
	2905	return mLeaf1;
	2906	}
	2907
	2908	BspLeaf *BspMergeCandidate::GetLeaf2()
	2909	{
	2910	return mLeaf2;
	2911	}
	2912
	2913	bool BspMergeCandidate::Valid() const
	2914	{
	2915	return
	2916	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
	2917	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
	2918	}
	2919
	2920	float BspMergeCandidate::GetMergeCost() const
	2921	{
	2922	return mMergeCost;
	2923	}
	2924
	2925	void BspMergeCandidate::SetValid()
	2926	{
	2927	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
	2928	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
	2929
	2930	EvalMergeCost();
	2931	}
[485]	2932
	2933
	2934	/************************************************************************/
	2935	/* MergeStatistics implementation */
	2936	/************************************************************************/
	2937
	2938
	2939	void MergeStatistics::Print(ostream &app) const
	2940	{
	2941	app << "===== Merge statistics ===============\n";
	2942
	2943	app << setprecision(4);
	2944
	2945	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
	2946
	2947	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
	2948
	2949	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
	2950
	2951	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
	2952
	2953	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
	2954
	2955	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
	2956	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
	2957
	2958	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
	2959
	2960	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
	2961
	2962	app << "===== END OF BspTree statistics ==========\n";
	2963	}

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

Download in other formats: