Context Navigation

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

Revision 495, 67.9 KB checked in by mattausch, 19 years ago (diff)
fixed bug in tree collapse

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

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

Download in other formats: