Context Navigation

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

Revision 560, 81.3 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: