Context Navigation

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

Revision 487, 64.4 KB checked in by mattausch, 19 years ago (diff)
fixed bug in raycasting added valid view point regions, get view point only from valid regions

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

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

Download in other formats: