Context Navigation

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

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

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

Download in other formats: