Context Navigation

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

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

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

Download in other formats: