Context Navigation

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

Revision 603, 71.7 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: