Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp @ 1074

Revision 1074, 96.8 KB checked in by mattausch, 19 years ago (diff)
wked on view space object space partition

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
[863]	20	namespace GtpVisibilityPreprocessor {
[860]	21
[639]	22	#define USE_FIXEDPOINT_T 0
[1020]	23	#define COUNT_ORIGIN_OBJECTS 1
[590]	24
[1020]	25
[463]	26	//-- static members
[508]	27
[482]	28	int VspBspTree::sFrontId = 0;
[463]	29	int VspBspTree::sBackId = 0;
	30	int VspBspTree::sFrontAndBackId = 0;
	31
[1020]	32
	33
[697]	34	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
[463]	35
[557]	36
[579]	37	// pvs penalty can be different from pvs size
[882]	38	inline static float EvalPvsPenalty(const int pvs,
	39	const int lower,
	40	const int upper)
[579]	41	{
	42	// clamp to minmax values
	43	if (pvs < lower)
	44	return (float)lower;
	45	if (pvs > upper)
	46	return (float)upper;
[578]	47
[579]	48	return (float)pvs;
	49	}
[463]	50
[557]	51
[579]	52
	53
[601]	54	/******************************************************************************/
	55	/* class VspBspTree implementation */
	56	/******************************************************************************/
[579]	57
	58
[1004]	59	VspBspTree::VspBspTree():
[463]	60	mRoot(NULL),
[547]	61	mUseAreaForPvs(false),
[478]	62	mCostNormalizer(Limits::Small),
	63	mViewCellsManager(NULL),
[497]	64	mOutOfBoundsCell(NULL),
[643]	65	mStoreRays(false),
[605]	66	mRenderCostWeight(0.5),
[610]	67	mUseRandomAxis(false),
[650]	68	mTimeStamp(1)
[463]	69	{
[486]	70	bool randomize = false;
[1004]	71	Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.randomize", randomize);
[1011]	72	if (randomize) Randomize(); // initialise random generator for heuristics
[463]	73
	74	//-- termination criteria for autopartition
[1004]	75	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
	76	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
	77	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
	78	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
	79	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
	80	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
[1023]	81
[1004]	82	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
	83	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
[666]	84
[564]	85	//-- max cost ratio for early tree termination
[1004]	86	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[610]	87
[1004]	88	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	89	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[610]	90
[463]	91	//-- factors for bsp tree split plane heuristics
[1004]	92	Environment::GetSingleton()->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
	93	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
[463]	94
[482]	95
[463]	96	//-- partition criteria
[1004]	97	Environment::GetSingleton()->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
	98	Environment::GetSingleton()->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
	99	Environment::GetSingleton()->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
[463]	100
[1004]	101	Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
	102	Environment::GetSingleton()->GetIntValue("VspBspTree.maxTests", mMaxTests);
[463]	103
[564]	104	// if only the driving axis is used for axis aligned split
[1004]	105	Environment::GetSingleton()->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[580]	106
[508]	107	//-- termination criteria for axis aligned split
[1004]	108	Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
[665]	109	mTermMaxRayContriForAxisAligned);
[1004]	110	Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
[665]	111	mTermMinRaysForAxisAligned);
[487]	112
[1004]	113	//Environment::GetSingleton()->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
	114	Environment::GetSingleton()->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
[508]	115
[1004]	116	Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
[1020]	117	Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
[1004]	118	Environment::GetSingleton()->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
[547]	119
[1004]	120	Environment::GetSingleton()->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics);
	121	Environment::GetSingleton()->GetBoolValue("VspBspTree.useSplitCostQueue", mUseSplitCostQueue);
	122	Environment::GetSingleton()->GetBoolValue("VspBspTree.simulateOctree", mCirculatingAxis);
	123	Environment::GetSingleton()->GetBoolValue("VspBspTree.useRandomAxis", mUseRandomAxis);
	124	Environment::GetSingleton()->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType);
[580]	125
[676]	126
[660]	127	char subdivisionStatsLog[100];
[1004]	128	Environment::GetSingleton()->GetStringValue("VspBspTree.subdivisionStats", subdivisionStatsLog);
[660]	129	mSubdivisionStats.open(subdivisionStatsLog);
[612]	130
[1004]	131	Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.minBand", mMinBand);
	132	Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand);
[1006]	133	Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisIfMaxCostViolated);
[801]	134
[478]	135	//-- debug output
[580]	136
[473]	137	Debug << "***** VSP BSP options ****** " << endl;
	138	Debug << "max depth: " << mTermMaxDepth << endl;
	139	Debug << "min PVS: " << mTermMinPvs << endl;
[547]	140	Debug << "min probabiliy: " << mTermMinProbability << endl;
[473]	141	Debug << "min rays: " << mTermMinRays << endl;
	142	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	143	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	144	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	145	Debug << "max view cells: " << mMaxViewCells << endl;
	146	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
[663]	147	//Debug << "max plane candidates: " << mMaxRayCandidates << endl;
[486]	148	Debug << "randomize: " << randomize << endl;
[582]	149
[551]	150	Debug << "using area for pvs: " << mUseAreaForPvs << endl;
[580]	151	Debug << "render cost weight: " << mRenderCostWeight << endl;
[663]	152	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	153	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	154	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	155	Debug << "max memory: " << mMaxMemory << endl;
	156	Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl;
	157	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	158	Debug << "use split cost queue: " << mUseSplitCostQueue << endl;
	159	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[664]	160	Debug << "use random axis: " << mUseRandomAxis << endl;
[735]	161	Debug << "priority queue type: " << mNodePriorityQueueType << endl;
[822]	162	Debug << "circulating axis: " << mCirculatingAxis << endl;
[801]	163	Debug << "minband: " << mMinBand << endl;
	164	Debug << "maxband: " << mMaxBand << endl;
[1006]	165	Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl;
[1020]	166	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
[663]	167
[463]	168	Debug << "Split plane strategy: ";
[564]	169
[463]	170	if (mSplitPlaneStrategy & RANDOM_POLYGON)
[474]	171	{
[463]	172	Debug << "random polygon ";
[474]	173	}
[463]	174	if (mSplitPlaneStrategy & AXIS_ALIGNED)
[472]	175	{
[463]	176	Debug << "axis aligned ";
[472]	177	}
[665]	178	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
[472]	179	{
[474]	180	mCostNormalizer += mLeastRaySplitsFactor;
[463]	181	Debug << "least ray splits ";
[472]	182	}
[463]	183	if (mSplitPlaneStrategy & BALANCED_RAYS)
[472]	184	{
[474]	185	mCostNormalizer += mBalancedRaysFactor;
[463]	186	Debug << "balanced rays ";
[472]	187	}
[463]	188	if (mSplitPlaneStrategy & PVS)
[472]	189	{
[474]	190	mCostNormalizer += mPvsFactor;
[463]	191	Debug << "pvs";
[665]	192	}
[482]	193
[489]	194
[1020]	195	mLocalSplitCandidates = new vector<SortableEntry>;
[463]	196
	197	Debug << endl;
	198	}
[580]	199
[1027]	200
[508]	201	BspViewCell *VspBspTree::GetOutOfBoundsCell()
	202	{
	203	return mOutOfBoundsCell;
	204	}
[463]	205
[508]	206
[489]	207	BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
	208	{
	209	if (!mOutOfBoundsCell)
[508]	210	{
[489]	211	mOutOfBoundsCell = new BspViewCell();
[508]	212	mOutOfBoundsCell->SetId(-1);
[547]	213	mOutOfBoundsCell->SetValid(false);
[508]	214	}
[547]	215
[489]	216	return mOutOfBoundsCell;
	217	}
	218
	219
[482]	220	const BspTreeStatistics &VspBspTree::GetStatistics() const
[463]	221	{
[574]	222	return mBspStats;
[463]	223	}
	224
	225
	226	VspBspTree::~VspBspTree()
	227	{
	228	DEL_PTR(mRoot);
[1020]	229	DEL_PTR(mLocalSplitCandidates);
[463]	230	}
	231
[579]	232
[482]	233	int VspBspTree::AddMeshToPolygons(Mesh *mesh,
	234	PolygonContainer &polys,
[463]	235	MeshInstance *parent)
	236	{
	237	FaceContainer::const_iterator fi;
[482]	238
[463]	239	// copy the face data to polygons
	240	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
	241	{
	242	Polygon3 poly = new Polygon3((fi), mesh);
[482]	243
[463]	244	if (poly->Valid(mEpsilon))
	245	{
	246	poly->mParent = parent; // set parent intersectable
	247	polys.push_back(poly);
	248	}
	249	else
	250	DEL_PTR(poly);
	251	}
	252	return (int)mesh->mFaces.size();
	253	}
	254
[580]	255
[482]	256	int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
[882]	257	PolygonContainer &polys,
	258	int maxObjects)
[463]	259	{
[482]	260	int limit = (maxObjects > 0) ?
[463]	261	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
[482]	262
[463]	263	int polysSize = 0;
	264
	265	for (int i = 0; i < limit; ++ i)
	266	{
	267	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
	268	{
	269	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
[482]	270	polysSize +=
	271	AddMeshToPolygons(viewCells[i]->GetMesh(),
	272	polys,
[463]	273	viewCells[i]);
	274	}
	275	}
	276
	277	return polysSize;
	278	}
	279
[580]	280
[482]	281	int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
	282	PolygonContainer &polys,
[463]	283	int maxObjects)
	284	{
[482]	285	int limit = (maxObjects > 0) ?
[463]	286	Min((int)objects.size(), maxObjects) : (int)objects.size();
[482]	287
[463]	288	for (int i = 0; i < limit; ++i)
	289	{
	290	Intersectable object = objects[i];//it;
	291	Mesh *mesh = NULL;
	292
	293	switch (object->Type()) // extract the meshes
	294	{
	295	case Intersectable::MESH_INSTANCE:
	296	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
	297	break;
	298	case Intersectable::VIEW_CELL:
	299	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
	300	break;
[1001]	301	case Intersectable::TRANSFORMED_MESH_INSTANCE:
	302	{
	303	TransformedMeshInstance mi = dynamic_cast<TransformedMeshInstance >(object);
	304
[1002]	305	if (!mi->GetMesh())
[1001]	306	break;
[1002]	307	mesh = new Mesh();
	308	mi->GetTransformedMesh(*mesh);
	309
[1001]	310	break;
	311	}
[463]	312	default:
	313	Debug << "intersectable type not supported" << endl;
	314	break;
	315	}
[482]	316
[463]	317	if (mesh) // copy the mesh data to polygons
	318	{
	319	mBox.Include(object->GetBox()); // add to BSP tree aabb
[485]	320	AddMeshToPolygons(mesh, polys, NULL);
[1001]	321
	322	// cleanup
	323	if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
	324	DEL_PTR(mesh);
[463]	325	}
	326	}
	327
	328	return (int)polys.size();
	329	}
	330
[580]	331
[1027]	332	void VspBspTree::ComputeBoundingBox(const VssRayContainer &sampleRays,
	333	AxisAlignedBox3 *forcedBoundingBox)
	334	{
	335	if (forcedBoundingBox)
	336	{
	337	mBox = *forcedBoundingBox;
	338	}
	339	else // compute vsp tree bounding box
	340	{
	341	mBox.Initialize();
	342
	343	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	344
	345	//-- compute bounding box
	346	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	347	{
	348	VssRay ray = rit;
	349
	350	// compute bounding box of view space
	351	mBox.Include(ray->GetTermination());
	352	mBox.Include(ray->GetOrigin());
	353	}
	354	}
	355	}
	356
	357
[483]	358	void VspBspTree::Construct(const VssRayContainer &sampleRays,
	359	AxisAlignedBox3 *forcedBoundingBox)
[463]	360	{
[1027]	361	// Compute the bounding box from the rays
	362	ComputeBoundingBox(sampleRays, forcedBoundingBox);
[484]	363
[463]	364	PolygonContainer polys;
	365	RayInfoContainer *rays = new RayInfoContainer();
	366
[1027]	367	//-- extract polygons from rays if there are polygon candidates
	368	if (mMaxPolyCandidates)
	369	{
	370	int numObj = 0;
[463]	371
[1027]	372	Intersectable::NewMail();
[463]	373
[1027]	374	cout << "Extracting polygons from rays ... ";
[463]	375
[1027]	376	long startTime = GetTime();
[463]	377
[1027]	378	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[542]	379
[1027]	380	//-- extract polygons intersected by the rays
	381	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
[463]	382	{
[1027]	383	VssRay ray = rit;
	384	Intersectable *obj = ray->mTerminationObject;
[1002]	385
[1027]	386	if ((mBox.IsInside(ray->mTermination) \|\| !forcedBoundingBox) &&
	387	obj && !obj->Mailed())
[1002]	388	{
[1027]	389	obj->Mail();
	390
	391	// transformed mesh instance and mesh instance handle mesh differently
	392	if (obj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
	393	{
	394	Mesh mesh;
[1002]	395
[1027]	396	TransformedMeshInstance *tmobj =
	397	dynamic_cast<TransformedMeshInstance *>(obj);
[1002]	398
[1027]	399	tmobj->GetTransformedMesh(mesh);
	400	AddMeshToPolygons(&mesh, polys, tmobj);
	401	}
	402	else // MeshInstance
	403	{
	404	MeshInstance mobj = dynamic_cast<MeshInstance >(obj);
	405	AddMeshToPolygons(mobj->GetMesh(), polys, mobj);
	406	}
	407
	408	++ numObj;
	409
	410	//-- compute bounding box
	411	if (!forcedBoundingBox)
	412	mBox.Include(ray->mTermination);
[1002]	413	}
[1027]	414
	415	if ((mBox.IsInside(ray->mOrigin) \|\| !forcedBoundingBox) &&
	416	ray->mOriginObject &&
	417	!ray->mOriginObject->Mailed())
	418	{
	419	ray->mOriginObject->Mail();
	420	MeshInstance obj = dynamic_cast<MeshInstance >(ray->mOriginObject);
	421	AddMeshToPolygons(obj->GetMesh(), polys, obj);
	422
	423	++ numObj;
[1002]	424	}
[1027]	425	}
[1002]	426
[1027]	427	// throw out unnecessary polygons
	428	PreprocessPolygons(polys);
[648]	429
[1027]	430	cout << "finished" << endl;
[463]	431
[1027]	432	Debug << "\n" << (int)polys.size() << " polys extracted from "
	433	<< (int)sampleRays.size() << " rays in "
	434	<< TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
[463]	435	}
[535]	436
[1027]	437	Debug << "maximal pvs (i.e., pvs still considered as valid): "
[653]	438	<< mViewCellsManager->GetMaxPvsSize() << endl;
[580]	439
[1027]	440	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	441
[463]	442	//-- store rays
	443	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	444	{
	445	VssRay ray = rit;
[482]	446
[463]	447	float minT, maxT;
	448
[564]	449	static Ray hray;
	450	hray.Init(*ray);
[562]	451
[483]	452	// TODO: not very efficient to implictly cast between rays types
[564]	453	if (mBox.GetRaySegment(hray, minT, maxT))
[463]	454	{
	455	float len = ray->Length();
[482]	456
	457	if (!len)
[463]	458	len = Limits::Small;
[482]	459
[463]	460	rays->push_back(RayInfo(ray, minT / len, maxT / len));
	461	}
	462	}
	463
[587]	464	// normalize
[547]	465	if (mUseAreaForPvs)
[587]	466	mTermMinProbability *= mBox.SurfaceArea();
[547]	467	else
	468	mTermMinProbability *= mBox.GetVolume();
	469
[648]	470
[1027]	471	mBspStats.nodes = 1;
[574]	472	mBspStats.polys = (int)polys.size();
[654]	473	mGlobalCostMisses = 0;
	474
[463]	475
[655]	476	// use split cost priority queue
	477	if (mUseSplitCostQueue)
	478	{
[654]	479	ConstructWithSplitQueue(polys, rays);
[655]	480	}
[654]	481	else
[655]	482	{
[654]	483	Construct(polys, rays);
[655]	484	}
[463]	485
	486	// clean up polygons
	487	CLEAR_CONTAINER(polys);
	488	}
	489
[508]	490
[612]	491	// TODO: return memory usage in MB
[656]	492	float VspBspTree::GetMemUsage() const
[508]	493	{
[656]	494	return (float)
	495	(sizeof(VspBspTree) +
	496	mBspStats.Leaves() * sizeof(BspLeaf) +
	497	mCreatedViewCells * sizeof(BspViewCell) +
	498	mBspStats.pvs * sizeof(ObjectPvsData) +
	499	mBspStats.Interior() * sizeof(BspInterior) +
	500	mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
[508]	501	}
	502
	503
[463]	504	void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
	505	{
[600]	506	VspBspTraversalQueue tQueue;
[463]	507
[1016]	508	/// create new vsp tree
[463]	509	mRoot = new BspLeaf();
	510
	511	// constrruct root node geometry
	512	BspNodeGeometry *geom = new BspNodeGeometry();
	513	ConstructGeometry(mRoot, *geom);
	514
[1016]	515	/// we use the overall probability as normalizer
	516	/// either the overall area or the volume
[547]	517	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
	518
[1020]	519	/// first traversal data
[482]	520	VspBspTraversalData tData(mRoot,
	521	new PolygonContainer(polys),
[463]	522	0,
[482]	523	rays,
	524	ComputePvsSize(*rays),
[547]	525	prop,
[463]	526	geom);
[663]	527
[664]	528	EvalPriority(tData);
[663]	529
	530
[578]	531	// first node is kd node, i.e. an axis aligned box
[710]	532	if (1)
[578]	533	tData.mIsKdNode = true;
	534	else
	535	tData.mIsKdNode = false;
[562]	536
[600]	537	tQueue.push(tData);
[463]	538
[609]	539
[605]	540	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
[607]	541	mTotalPvsSize = tData.mPvs;
	542
[1020]	543	// first subdivison statistics
	544	AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
	545
[574]	546	mBspStats.Start();
[667]	547	cout << "Constructing vsp bsp tree ... \n";
[463]	548
[1016]	549	const long startTime = GetTime();
	550	// used for intermediate time measurements and progress
	551	long interTime = GetTime();
	552
[664]	553	int nLeaves = 500;
	554	int nViewCells = 500;
[587]	555
[542]	556	mOutOfMemory = false;
[612]	557	mCreatedViewCells = 0;
	558
[600]	559	while (!tQueue.empty())
[463]	560	{
[600]	561	tData = tQueue.top();
	562	tQueue.pop();
[463]	563
[508]	564	if (0 && !mOutOfMemory)
	565	{
	566	float mem = GetMemUsage();
[478]	567
[508]	568	if (mem > mMaxMemory)
	569	{
	570	mOutOfMemory = true;
	571	Debug << "memory limit reached: " << mem << endl;
	572	}
	573	}
	574
[587]	575	// subdivide leaf node
[1016]	576	const BspNode *r = Subdivide(tQueue, tData);
[463]	577
	578	if (r == mRoot)
[482]	579	Debug << "VSP BSP tree construction time spent at root: "
[542]	580	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
	581
[654]	582	if (mBspStats.Leaves() >= nLeaves)
[542]	583	{
[612]	584	nLeaves += 500;
	585
[574]	586	cout << "leaves=" << mBspStats.Leaves() << endl;
[542]	587	Debug << "needed "
[587]	588	<< TimeDiff(interTime, GetTime())*1e-3
[612]	589	<< " secs to create 500 view cells" << endl;
[542]	590	interTime = GetTime();
	591	}
[612]	592
[664]	593	if (mCreatedViewCells >= nViewCells)
[612]	594	{
	595	nViewCells += 500;
	596
	597	cout << "generated " << mCreatedViewCells << " viewcells" << endl;
	598	}
[463]	599	}
	600
[542]	601	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
[1020]	602	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
[463]	603
[574]	604	mBspStats.Stop();
[463]	605	}
	606
[508]	607
[653]	608
[654]	609	void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys,
[653]	610	RayInfoContainer *rays)
	611	{
	612	VspBspSplitQueue tQueue;
	613
	614	mRoot = new BspLeaf();
	615
	616	// constrruct root node geometry
	617	BspNodeGeometry *geom = new BspNodeGeometry();
	618	ConstructGeometry(mRoot, *geom);
	619
	620	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
	621
	622	VspBspTraversalData tData(mRoot,
	623	new PolygonContainer(polys),
	624	0,
	625	rays,
	626	ComputePvsSize(*rays),
	627	prop,
	628	geom);
	629
[663]	630
[660]	631	// compute first split candidate
[653]	632	VspBspSplitCandidate splitCandidate;
	633	EvalSplitCandidate(tData, splitCandidate);
	634
	635	tQueue.push(splitCandidate);
	636
	637	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
	638	mTotalPvsSize = tData.mPvs;
	639
[1020]	640	// first subdivison statistics
	641	AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
	642
	643	mBspStats.Start();
[667]	644	cout << "Constructing vsp bsp tree ... \n";
[653]	645
	646	long startTime = GetTime();
[666]	647	int nLeaves = 500;
	648	int nViewCells = 500;
[653]	649
	650	// used for intermediate time measurements and progress
	651	long interTime = GetTime();
	652
	653	mOutOfMemory = false;
	654
	655	mCreatedViewCells = 0;
	656
	657	while (!tQueue.empty())
	658	{
	659	splitCandidate = tQueue.top();
	660	tQueue.pop();
	661
[654]	662	// cost ratio of cost decrease / totalCost
[1020]	663	float costRatio = splitCandidate.GetPriority() / mTotalCost;
[654]	664
[655]	665	//Debug << "cost ratio: " << costRatio << endl;
[654]	666
	667	if (costRatio < mTermMinGlobalCostRatio)
	668	++ mGlobalCostMisses;
[655]	669
[653]	670	if (0 && !mOutOfMemory)
	671	{
	672	float mem = GetMemUsage();
	673
	674	if (mem > mMaxMemory)
	675	{
	676	mOutOfMemory = true;
	677	Debug << "memory limit reached: " << mem << endl;
	678	}
	679	}
	680
	681	// subdivide leaf node
	682	BspNode *r = Subdivide(tQueue, splitCandidate);
	683
	684	if (r == mRoot)
	685	Debug << "VSP BSP tree construction time spent at root: "
	686	<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
	687
[654]	688	if (mBspStats.Leaves() >= nLeaves)
[653]	689	{
	690	nLeaves += 500;
	691
	692	cout << "leaves=" << mBspStats.Leaves() << endl;
	693	Debug << "needed "
	694	<< TimeDiff(interTime, GetTime())*1e-3
	695	<< " secs to create 500 view cells" << endl;
	696	interTime = GetTime();
	697	}
	698
	699	if (mCreatedViewCells == nViewCells)
	700	{
	701	nViewCells += 500;
	702	cout << "generated " << mCreatedViewCells << " viewcells" << endl;
	703	}
	704	}
	705
	706	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
	707	cout << "finished\n";
	708
	709	mBspStats.Stop();
	710	}
	711
	712
[654]	713	bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
[463]	714	{
[482]	715	return
[463]	716	(((int)data.mRays->size() <= mTermMinRays) \|\|
[473]	717	(data.mPvs <= mTermMinPvs) \|\|
[547]	718	(data.mProbability <= mTermMinProbability) \|\|
[535]	719	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
[463]	720	(data.mDepth >= mTermMaxDepth));
	721	}
	722
[508]	723
[1020]	724	void VspBspTree::AddSubdivisionStats(const int viewCells,
	725	const float renderCostDecr,
	726	const float splitCandidateCost,
	727	const float totalRenderCost,
	728	const float avgRenderCost)
	729	{
	730	mSubdivisionStats
	731	<< "#ViewCells\n" << viewCells << endl
	732	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	733	<< "#SplitCandidateCost\n" << splitCandidateCost << endl
	734	<< "#TotalRenderCost\n" << totalRenderCost << endl
	735	<< "#AvgRenderCost\n" << avgRenderCost << endl;
	736	}
	737
	738
[654]	739	bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
	740	{
	741	return
	742	(mOutOfMemory
	743	\|\| (mBspStats.Leaves() >= mMaxViewCells)
	744	\|\| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
	745	);
	746	}
	747
	748
[600]	749	BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
[463]	750	VspBspTraversalData &tData)
	751	{
[473]	752	BspNode *newNode = tData.mNode;
	753
[654]	754	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
[473]	755	{
	756	PolygonContainer coincident;
[482]	757
[473]	758	VspBspTraversalData tFrontData;
	759	VspBspTraversalData tBackData;
[612]	760
[473]	761	// create new interior node and two leaf nodes
	762	// or return leaf as it is (if maxCostRatio missed)
[653]	763	int splitAxis;
	764	bool splitFurther = true;
	765	int maxCostMisses = tData.mMaxCostMisses;
	766
	767	Plane3 splitPlane;
	768	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
[726]	769
	770	// choose next split plane
[653]	771	if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
[473]	772	{
[653]	773	++ maxCostMisses;
	774
	775	if (maxCostMisses > mTermMissTolerance)
	776	{
	777	// terminate branch because of max cost
	778	++ mBspStats.maxCostNodes;
	779	splitFurther = false;
	780	}
	781	}
	782
[726]	783	// if this a valid split => subdivide this node further
[653]	784	if (splitFurther) //-- continue subdivision
	785	{
	786	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
	787
	788	if (splitAxis < 3)
	789	++ mBspStats.splits[splitAxis];
	790	else
	791	++ mBspStats.polySplits;
	792
[822]	793	// if it was a kd node (i.e., a box) and the split axis is axis aligned, it is still a kd node
[710]	794	tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
[726]	795	tFrontData.mAxis = tBackData.mAxis = splitAxis;
[663]	796
[653]	797	// how often was max cost ratio missed in this branch?
	798	tFrontData.mMaxCostMisses = maxCostMisses;
	799	tBackData.mMaxCostMisses = maxCostMisses;
	800
[664]	801	EvalPriority(tFrontData);
	802	EvalPriority(tBackData);
[663]	803
[726]	804	// evaluate subdivision stats
[600]	805	if (1)
	806	{
[1020]	807	const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
	808	const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
	809	const float cData = (float)tData.mPvs * tData.mProbability;;
[605]	810
[1020]	811	const float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
[607]	812
[600]	813	mTotalCost += costDecr;
[607]	814	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
[600]	815
[1020]	816	AddSubdivisionStats(mBspStats.Leaves(),
	817	-costDecr,
	818	0,
	819	mTotalCost,
	820	(float)mTotalPvsSize / (float)mBspStats.Leaves());
[600]	821	}
	822
[473]	823	// push the children on the stack
[600]	824	tQueue.push(tFrontData);
	825	tQueue.push(tBackData);
[473]	826
	827	// delete old leaf node
[482]	828	DEL_PTR(tData.mNode);
[473]	829	}
	830	}
[482]	831
[478]	832	//-- terminate traversal and create new view cell
[473]	833	if (newNode->IsLeaf())
[463]	834	{
[473]	835	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
[1020]	836
[547]	837	BspViewCell *viewCell = new BspViewCell();
[463]	838	leaf->SetViewCell(viewCell);
[487]	839
	840	//-- update pvs
[556]	841	int conSamp = 0;
	842	float sampCon = 0.0f;
	843	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
[487]	844
[1002]	845	// update scalar pvs size lookup
	846	mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
	847
[752]	848
[574]	849	mBspStats.contributingSamples += conSamp;
[1047]	850	mBspStats.sampleContributions += (int)sampCon;
[487]	851
	852	//-- store additional info
[478]	853	if (mStoreRays)
	854	{
	855	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	856	for (it = tData.mRays->begin(); it != it_end; ++ it)
[639]	857	{
	858	(*it).mRay->Ref();
[478]	859	leaf->mVssRays.push_back((*it).mRay);
[639]	860	}
[478]	861	}
[612]	862
[564]	863	// should I check here?
[1027]	864	if (0 && !mViewCellsManager->CheckValidity(viewCell, 0,
	865	mViewCellsManager->GetMaxPvsSize()))
[547]	866	{
	867	viewCell->SetValid(false);
	868	leaf->SetTreeValid(false);
	869	PropagateUpValidity(leaf);
[463]	870
[574]	871	++ mBspStats.invalidLeaves;
[547]	872	}
	873
[580]	874	viewCell->mLeaf = leaf;
[547]	875
	876	if (mUseAreaForPvs)
	877	viewCell->SetArea(tData.mProbability);
	878	else
	879	viewCell->SetVolume(tData.mProbability);
	880
	881	leaf->mProbability = tData.mProbability;
	882
[1020]	883	// finally evaluate stats until this leaf
[1027]	884	if (0)
	885	EvaluateLeafStats(tData);
[463]	886	}
[482]	887
[473]	888	//-- cleanup
[478]	889	tData.Clear();
[463]	890
[472]	891	return newNode;
[463]	892	}
	893
[1027]	894
	895	// subdivide node using a split plane queue
[653]	896	BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
	897	VspBspSplitCandidate &splitCandidate)
	898	{
	899	VspBspTraversalData &tData = splitCandidate.mParentData;
	900
	901	BspNode *newNode = tData.mNode;
	902
[654]	903	if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
[666]	904	{
[653]	905	PolygonContainer coincident;
	906
	907	VspBspTraversalData tFrontData;
	908	VspBspTraversalData tBackData;
	909
	910	//-- continue subdivision
[726]	911
[653]	912	// create new interior node and two leaf node
	913	const Plane3 splitPlane = splitCandidate.mSplitPlane;
[654]	914
[653]	915	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
[666]	916
[660]	917	const int splitAxis = splitCandidate.mSplitAxis;
	918	const int maxCostMisses = splitCandidate.mMaxCostMisses;
	919
[654]	920	if (splitAxis < 3)
	921	++ mBspStats.splits[splitAxis];
	922	else
	923	++ mBspStats.polySplits;
[653]	924
[710]	925	tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
[726]	926	tFrontData.mAxis = tBackData.mAxis = splitAxis;
	927
[654]	928	// how often was max cost ratio missed in this branch?
	929	tFrontData.mMaxCostMisses = maxCostMisses;
	930	tBackData.mMaxCostMisses = maxCostMisses;
[664]	931
[1020]	932	// statistics
[653]	933	if (1)
	934	{
	935	float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
	936	float cBack = (float)tBackData.mPvs * tBackData.mProbability;
[675]	937	float cData = (float)tData.mPvs * tData.mProbability;
[653]	938
[675]	939
[653]	940	float costDecr =
	941	(cFront + cBack - cData) / mBox.GetVolume();
	942
	943	mTotalCost += costDecr;
	944	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	945
[1020]	946	AddSubdivisionStats(mBspStats.Leaves(),
	947	-costDecr,
	948	splitCandidate.GetPriority(),
	949	mTotalCost,
	950	(float)mTotalPvsSize / (float)mBspStats.Leaves());
[653]	951	}
	952
[666]	953
[653]	954	//-- push the new split candidates on the stack
	955	VspBspSplitCandidate frontCandidate;
	956	VspBspSplitCandidate backCandidate;
	957
[654]	958	EvalSplitCandidate(tFrontData, frontCandidate);
	959	EvalSplitCandidate(tBackData, backCandidate);
	960
[653]	961	tQueue.push(frontCandidate);
	962	tQueue.push(backCandidate);
[666]	963
[653]	964	// delete old leaf node
	965	DEL_PTR(tData.mNode);
	966	}
	967
[654]	968
[653]	969	//-- terminate traversal and create new view cell
	970	if (newNode->IsLeaf())
	971	{
	972	BspLeaf leaf = dynamic_cast<BspLeaf >(newNode);
[1020]	973
[653]	974	BspViewCell *viewCell = new BspViewCell();
[710]	975	leaf->SetViewCell(viewCell);
[653]	976
	977	//-- update pvs
	978	int conSamp = 0;
	979	float sampCon = 0.0f;
	980	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
	981
[1002]	982	// update scalar pvs size value
	983	mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
[752]	984
[653]	985	mBspStats.contributingSamples += conSamp;
	986	mBspStats.sampleContributions +=(int) sampCon;
	987
	988	//-- store additional info
	989	if (mStoreRays)
	990	{
	991	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	992	for (it = tData.mRays->begin(); it != it_end; ++ it)
	993	{
	994	(*it).mRay->Ref();
	995	leaf->mVssRays.push_back((*it).mRay);
	996	}
	997	}
	998
[1020]	999
[653]	1000	viewCell->mLeaf = leaf;
	1001
	1002	if (mUseAreaForPvs)
	1003	viewCell->SetArea(tData.mProbability);
	1004	else
	1005	viewCell->SetVolume(tData.mProbability);
	1006
[675]	1007	leaf->mProbability = tData.mProbability;
[653]	1008
[1020]	1009	// finally evaluate stats until this leaf
[1027]	1010	if (0)
	1011	EvaluateLeafStats(tData);
[653]	1012	}
	1013
	1014	//-- cleanup
	1015	tData.Clear();
	1016
	1017	return newNode;
	1018	}
	1019
	1020
[664]	1021	void VspBspTree::EvalPriority(VspBspTraversalData &tData) const
	1022	{
[735]	1023	switch (mNodePriorityQueueType)
	1024	{
	1025	case BREATH_FIRST:
[734]	1026	tData.mPriority = (float)-tData.mDepth;
[735]	1027	break;
	1028	case DEPTH_FIRST:
[734]	1029	tData.mPriority = (float)tData.mDepth;
[735]	1030	break;
	1031	default:
[734]	1032	tData.mPriority = tData.mPvs * tData.mProbability;
[735]	1033	//Debug << "priority: " << tData.mPriority << endl;
	1034	break;
	1035	}
[664]	1036	}
	1037
	1038
[652]	1039	void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData,
	1040	VspBspSplitCandidate &splitData)
	1041	{
	1042	VspBspTraversalData frontData;
	1043	VspBspTraversalData backData;
	1044
	1045	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
[654]	1046
	1047	// compute locally best split plane
[726]	1048	bool success = SelectPlane(splitData.mSplitPlane, leaf, tData,
[666]	1049	frontData, backData, splitData.mSplitAxis);
[652]	1050
	1051	// TODO: reuse
[1027]	1052	delete frontData.mGeometry;
	1053	delete backData.mGeometry;
[652]	1054
[654]	1055	// compute global decrease in render cost
[1020]	1056	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
[652]	1057	splitData.mParentData = tData;
[660]	1058	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
[652]	1059	}
	1060
	1061
[653]	1062	BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
	1063	VspBspTraversalData &tData,
	1064	VspBspTraversalData &frontData,
	1065	VspBspTraversalData &backData,
	1066	PolygonContainer &coincident)
[463]	1067	{
	1068	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
[508]	1069
[473]	1070	//-- the front and back traversal data is filled with the new values
	1071	frontData.mDepth = tData.mDepth + 1;
[508]	1072	frontData.mPolygons = new PolygonContainer();
[473]	1073	frontData.mRays = new RayInfoContainer();
[508]	1074
[473]	1075	backData.mDepth = tData.mDepth + 1;
[508]	1076	backData.mPolygons = new PolygonContainer();
[473]	1077	backData.mRays = new RayInfoContainer();
[508]	1078
[653]	1079
	1080	//-- subdivide rays
[652]	1081	SplitRays(splitPlane,
[482]	1082	*tData.mRays,
	1083	*frontData.mRays,
[463]	1084	*backData.mRays);
[482]	1085
[463]	1086
[472]	1087	// compute pvs
[463]	1088	frontData.mPvs = ComputePvsSize(*frontData.mRays);
	1089	backData.mPvs = ComputePvsSize(*backData.mRays);
	1090
[508]	1091	// split front and back node geometry and compute area
[547]	1092
	1093	// if geometry was not already computed
[602]	1094	if (!frontData.mGeometry && !backData.mGeometry)
[463]	1095	{
[547]	1096	frontData.mGeometry = new BspNodeGeometry();
	1097	backData.mGeometry = new BspNodeGeometry();
[482]	1098
[547]	1099	tData.mGeometry->SplitGeometry(*frontData.mGeometry,
	1100	*backData.mGeometry,
[652]	1101	splitPlane,
[547]	1102	mBox,
[679]	1103	//0.0f);
	1104	mEpsilon);
[508]	1105
[547]	1106	if (mUseAreaForPvs)
	1107	{
	1108	frontData.mProbability = frontData.mGeometry->GetArea();
	1109	backData.mProbability = backData.mGeometry->GetArea();
[508]	1110	}
[547]	1111	else
	1112	{
	1113	frontData.mProbability = frontData.mGeometry->GetVolume();
[654]	1114	backData.mProbability = tData.mProbability - frontData.mProbability;
[676]	1115
[744]	1116	// should never come here: wrong volume !!!
[676]	1117	if (0)
	1118	{
[744]	1119	if (frontData.mProbability < -0.00001)
	1120	Debug << "fatal error f: " << frontData.mProbability << endl;
	1121	if (backData.mProbability < -0.00001)
	1122	Debug << "fatal error b: " << backData.mProbability << endl;
	1123
	1124	// clamp because of precision issues
[676]	1125	if (frontData.mProbability < 0) frontData.mProbability = 0;
	1126	if (backData.mProbability < 0) backData.mProbability = 0;
	1127	}
[547]	1128	}
[463]	1129	}
[663]	1130
[547]	1131
[652]	1132	// subdivide polygons
	1133	SplitPolygons(splitPlane,
	1134	*tData.mPolygons,
	1135	*frontData.mPolygons,
	1136	*backData.mPolygons,
	1137	coincident);
[463]	1138
[652]	1139
	1140
[653]	1141	///////////////////////////////////////
	1142	// subdivide further
[652]	1143
[711]	1144	// store maximal and minimal depth
	1145	if (tData.mDepth > mBspStats.maxDepth)
	1146	{
	1147	Debug << "max depth increases to " << tData.mDepth << " at " << mBspStats.Leaves() << " leaves" << endl;
	1148	mBspStats.maxDepth = tData.mDepth;
	1149	}
	1150
[652]	1151	mBspStats.nodes += 2;
	1152
[711]	1153
[652]	1154	BspInterior *interior = new BspInterior(splitPlane);
	1155
	1156	#ifdef _DEBUG
	1157	Debug << interior << endl;
	1158	#endif
	1159
[711]	1160
[463]	1161	//-- create front and back leaf
	1162
	1163	BspInterior *parent = leaf->GetParent();
	1164
	1165	// replace a link from node's parent
[487]	1166	if (parent)
[463]	1167	{
	1168	parent->ReplaceChildLink(leaf, interior);
	1169	interior->SetParent(parent);
	1170	}
	1171	else // new root
	1172	{
	1173	mRoot = interior;
	1174	}
	1175
	1176	// and setup child links
	1177	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
[482]	1178
[463]	1179	frontData.mNode = interior->GetFront();
	1180	backData.mNode = interior->GetBack();
[473]	1181
[650]	1182	interior->mTimeStamp = mTimeStamp ++;
[652]	1183
[711]	1184
[463]	1185	//DEL_PTR(leaf);
	1186	return interior;
	1187	}
	1188
[508]	1189
[463]	1190	void VspBspTree::AddToPvs(BspLeaf *leaf,
[482]	1191	const RayInfoContainer &rays,
[556]	1192	float &sampleContributions,
[463]	1193	int &contributingSamples)
	1194	{
[1002]	1195	sampleContributions = 0;
	1196	contributingSamples = 0;
[556]	1197
[1002]	1198	RayInfoContainer::const_iterator it, it_end = rays.end();
[556]	1199
[1002]	1200	ViewCellLeaf *vc = leaf->GetViewCell();
[556]	1201
[1002]	1202	// add contributions from samples to the PVS
	1203	for (it = rays.begin(); it != it_end; ++ it)
[463]	1204	{
[1002]	1205	float sc = 0.0f;
	1206	VssRay ray = (it).mRay;
	1207
	1208	bool madeContrib = false;
	1209	float contribution;
	1210
	1211	if (ray->mTerminationObject)
	1212	{
	1213	if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
	1214	madeContrib = true;
	1215	sc += contribution;
	1216	}
[556]	1217
[1006]	1218	// only count termination objects?
[1020]	1219	if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
[1002]	1220	{
	1221	if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
	1222	madeContrib = true;
[1020]	1223
[1002]	1224	sc += contribution;
	1225	}
[556]	1226
[1047]	1227	sampleContributions += sc;
	1228
	1229	if (madeContrib)
	1230	++ contributingSamples;
	1231
[1072]	1232	// note: vss rays are never deleted
[1047]	1233	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
[463]	1234	}
	1235	}
	1236
[580]	1237
[710]	1238	void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays,
	1239	const int axis,
	1240	float minBand,
	1241	float maxBand)
[463]	1242	{
[1020]	1243	mLocalSplitCandidates->clear();
[463]	1244
[480]	1245	int requestedSize = 2 * (int)(rays.size());
	1246	// creates a sorted split candidates array
[1020]	1247	if (mLocalSplitCandidates->capacity() > 500000 &&
	1248	requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) )
[480]	1249	{
[1020]	1250	delete mLocalSplitCandidates;
	1251	mLocalSplitCandidates = new vector<SortableEntry>;
[480]	1252	}
[463]	1253
[1020]	1254	mLocalSplitCandidates->reserve(requestedSize);
[480]	1255
[710]	1256	float pos;
	1257
	1258	// float values => don't compare with exact values
	1259	if (0)
	1260	{
	1261	minBand += Limits::Small;
	1262	maxBand -= Limits::Small;
	1263	}
	1264
[480]	1265	// insert all queries
[612]	1266	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
[473]	1267	{
[612]	1268	const bool positive = (*ri).mRay->HasPosDir(axis);
[710]	1269
	1270	pos = (*ri).ExtrapOrigin(axis);
	1271	// clamp to min / max band
	1272	if (0) ClipValue(pos, minBand, maxBand);
	1273
[1020]	1274	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
[810]	1275	pos, (*ri).mRay));
[480]	1276
[710]	1277	pos = (*ri).ExtrapTermination(axis);
	1278	// clamp to min / max band
	1279	if (0) ClipValue(pos, minBand, maxBand);
	1280
[1020]	1281	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
[810]	1282	pos, (*ri).mRay));
[473]	1283	}
[480]	1284
[1020]	1285	stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end());
[463]	1286	}
	1287
[580]	1288
[480]	1289	float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
	1290	const AxisAlignedBox3 &box,
	1291	const int pvsSize,
[710]	1292	const int axis,
[480]	1293	float &position)
[463]	1294	{
[710]	1295	const float minBox = box.Min(axis);
	1296	const float maxBox = box.Max(axis);
[822]	1297
[710]	1298	const float sizeBox = maxBox - minBox;
[480]	1299
[801]	1300	const float minBand = minBox + mMinBand * sizeBox;
	1301	const float maxBand = minBox + mMaxBand * sizeBox;
[710]	1302
	1303	SortSplitCandidates(rays, axis, minBand, maxBand);
	1304
[463]	1305	// go through the lists, count the number of objects left and right
	1306	// and evaluate the following cost funcion:
[480]	1307	// C = ct_div_ci + (qlrl + qrrr)/queries
	1308
[810]	1309	int pvsl = 0;
	1310	int pvsr = pvsSize;
[480]	1311
[612]	1312	int pvsBack = pvsl;
	1313	int pvsFront = pvsr;
	1314
	1315	float sum = (float)pvsSize * sizeBox;
[463]	1316	float minSum = 1e20f;
	1317
[822]	1318
[710]	1319	// if no border can be found, take mid split
	1320	position = minBox + 0.5f * sizeBox;
[822]	1321
	1322	// the relative cost ratio
[1074]	1323	float ratio = 99999999.0f;
[822]	1324	bool splitPlaneFound = false;
[710]	1325
[480]	1326	Intersectable::NewMail();
	1327
[612]	1328	RayInfoContainer::const_iterator ri, ri_end = rays.end();
	1329
	1330	// set all object as belonging to the front pvs
	1331	for(ri = rays.begin(); ri != ri_end; ++ ri)
[463]	1332	{
[612]	1333	Intersectable oObject = (ri).mRay->mOriginObject;
	1334	Intersectable tObject = (ri).mRay->mTerminationObject;
	1335
[1020]	1336	if (COUNT_ORIGIN_OBJECTS && oObject)
[463]	1337	{
[612]	1338	if (!oObject->Mailed())
[482]	1339	{
[612]	1340	oObject->Mail();
	1341	oObject->mCounter = 1;
[482]	1342	}
[612]	1343	else
	1344	{
	1345	++ oObject->mCounter;
	1346	}
[463]	1347	}
[1020]	1348
[612]	1349	if (tObject)
	1350	{
	1351	if (!tObject->Mailed())
	1352	{
	1353	tObject->Mail();
	1354	tObject->mCounter = 1;
	1355	}
	1356	else
	1357	{
	1358	++ tObject->mCounter;
	1359	}
	1360	}
[480]	1361	}
	1362
	1363	Intersectable::NewMail();
	1364
[1020]	1365	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end();
[612]	1366
[1020]	1367	for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci)
[480]	1368	{
	1369	VssRay *ray;
[612]	1370	ray = (*ci).ray;
	1371
	1372	Intersectable *oObject = ray->mOriginObject;
	1373	Intersectable *tObject = ray->mTerminationObject;
	1374
[480]	1375
	1376	switch ((*ci).type)
[463]	1377	{
[480]	1378	case SortableEntry::ERayMin:
	1379	{
[1020]	1380	if (COUNT_ORIGIN_OBJECTS && oObject && !oObject->Mailed())
[480]	1381	{
[612]	1382	oObject->Mail();
	1383	++ pvsl;
[480]	1384	}
[1020]	1385
[612]	1386	if (tObject && !tObject->Mailed())
	1387	{
	1388	tObject->Mail();
	1389	++ pvsl;
	1390	}
[1020]	1391
[480]	1392	break;
	1393	}
	1394	case SortableEntry::ERayMax:
	1395	{
[1020]	1396	if (COUNT_ORIGIN_OBJECTS && oObject)
[612]	1397	{
	1398	if (-- oObject->mCounter == 0)
	1399	-- pvsr;
	1400	}
[463]	1401
[612]	1402	if (tObject)
[480]	1403	{
[612]	1404	if (-- tObject->mCounter == 0)
	1405	-- pvsr;
[480]	1406	}
	1407
	1408	break;
	1409	}
	1410	}
[822]	1411
	1412
[1020]	1413	// Note: we compare size of bounding boxes of front and back side because
	1414	// of efficiency reasons (otherwise a new geometry would have to be computed
	1415	// in each step and incremential evaluation would be difficult.
	1416	// but then errors happen if the geometry is not an axis aligned box
	1417	// (i.e., if a geometry aligned split was taken before)
	1418	// question: is it sufficient to make this approximation?
[710]	1419	if (((ci).value >= minBand) && ((ci).value <= maxBand))
[480]	1420	{
[612]	1421	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
[480]	1422
[822]	1423	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
	1424	//Debug << "cost= " << sum << endl;
[480]	1425
	1426	if (sum < minSum)
[463]	1427	{
[822]	1428	splitPlaneFound = true;
	1429
[463]	1430	minSum = sum;
	1431	position = (*ci).value;
[710]	1432
[612]	1433	pvsBack = pvsl;
	1434	pvsFront = pvsr;
[463]	1435	}
	1436	}
	1437	}
[710]	1438
[822]	1439
[612]	1440	// -- compute cost
	1441	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1442	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1443
	1444	const float pOverall = sizeBox;
	1445
	1446	const float pBack = position - minBox;
	1447	const float pFront = maxBox - position;
	1448
	1449	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1450	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1451	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1452
	1453	const float oldRenderCost = penaltyOld * pOverall;
	1454	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1455
[822]	1456	if (splitPlaneFound)
	1457	{
	1458	ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
	1459	}
	1460	//if (axis != 1)
	1461	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1462	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
[612]	1463
[480]	1464	return ratio;
[463]	1465	}
	1466
[480]	1467
[482]	1468	float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
[491]	1469	const VspBspTraversalData &tData,
[495]	1470	int &axis,
[508]	1471	BspNodeGeometry **frontGeom,
	1472	BspNodeGeometry **backGeom,
[547]	1473	float &pFront,
	1474	float &pBack,
[710]	1475	const bool isKdNode)
[463]	1476	{
[508]	1477	float nPosition[3];
	1478	float nCostRatio[3];
[547]	1479	float nProbFront[3];
	1480	float nProbBack[3];
[508]	1481
	1482	BspNodeGeometry *nFrontGeom[3];
	1483	BspNodeGeometry *nBackGeom[3];
	1484
[822]	1485	// set to NULL, so I can find out which gemetry was stored
[612]	1486	for (int i = 0; i < 3; ++ i)
	1487	{
	1488	nFrontGeom[i] = NULL;
	1489	nBackGeom[i] = NULL;
	1490	}
	1491
[545]	1492	// create bounding box of node geometry
[463]	1493	AxisAlignedBox3 box;
[710]	1494
[562]	1495	//TODO: for kd split geometry already is box => only take minmax vertices
[551]	1496	if (1)
[509]	1497	{
[822]	1498	// get bounding box from geometry
[710]	1499	tData.mGeometry->GetBoundingBox(box);
[509]	1500	}
	1501	else
	1502	{
[710]	1503	box.Initialize();
[509]	1504	RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
[480]	1505
[509]	1506	for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
	1507	box.Include((*ri).ExtrapTermination());
	1508	}
[663]	1509
	1510	int sAxis = 0;
[822]	1511	int bestAxis;
	1512
[837]	1513	// if max cost ratio is exceeded, take split along longest axis instead
	1514	const float maxCostRatioForArbitraryAxis = 0.9f;
	1515
[1006]	1516	if (mUseDrivingAxisIfMaxCostViolated)
[822]	1517	bestAxis = box.Size().DrivingAxis();
	1518	else
	1519	bestAxis = -1;
	1520
[978]	1521	#if 0
	1522	// maximum cost ratio for axis to be valid:
[822]	1523	// if exceeded, spatial mid split is used instead
[978]	1524	const maxCostRatioForHeur = 0.99f;
	1525	#endif
[822]	1526
[978]	1527	// if we use some kind of specialised fixed axis
[837]	1528	const bool useSpecialAxis =
	1529	mOnlyDrivingAxis \|\| mUseRandomAxis \|\| mCirculatingAxis;
[663]	1530
[801]	1531	if (mUseRandomAxis)
[663]	1532	sAxis = Random(3);
[801]	1533	else if (mCirculatingAxis)
[726]	1534	sAxis = (tData.mAxis + 1) % 3;
[822]	1535	else if (mOnlyDrivingAxis)
[801]	1536	sAxis = box.Size().DrivingAxis();
	1537
[664]	1538
[670]	1539	//Debug << "use special axis: " << useSpecialAxis << endl;
	1540	//Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
[663]	1541
[822]	1542	for (axis = 0; axis < 3 ; ++ axis)
[480]	1543	{
[663]	1544	if (!useSpecialAxis \|\| (axis == sAxis))
[463]	1545	{
[822]	1546	//-- place split plane using heuristics
	1547
	1548	if (mUseCostHeuristics)
[480]	1549	{
[822]	1550	nCostRatio[axis] =
	1551	BestCostRatioHeuristics(*tData.mRays,
	1552	box,
	1553	tData.mPvs,
	1554	axis,
	1555	nPosition[axis]);
	1556	}
[1006]	1557	else //-- split plane position is spatial median
[822]	1558	{
	1559
[480]	1560	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[543]	1561	Vector3 normal(0,0,0); normal[axis] = 1.0f;
[547]	1562
	1563	// allows faster split because we have axis aligned kd tree boxes
[822]	1564	if (isKdNode)
[542]	1565	{
	1566	nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
	1567	box,
	1568	axis,
[547]	1569	nPosition[axis],
	1570	nProbFront[axis],
	1571	nProbBack[axis]);
[542]	1572
[543]	1573	Vector3 pos;
[542]	1574
[710]	1575	// create back geometry from box
[1047]	1576	// NOTE: the geometry is returned from the function so we
	1577	// don't have to recompute it when possible
[543]	1578	pos = box.Max(); pos[axis] = nPosition[axis];
[547]	1579	AxisAlignedBox3 bBox(box.Min(), pos);
[710]	1580	PolygonContainer fPolys;
	1581	bBox.ExtractPolys(fPolys);
	1582
	1583	nBackGeom[axis] = new BspNodeGeometry(fPolys);
	1584
[822]	1585	//-- create front geometry from box
[542]	1586	pos = box.Min(); pos[axis] = nPosition[axis];
[547]	1587	AxisAlignedBox3 fBox(pos, box.Max());
[710]	1588
	1589	PolygonContainer bPolys;
	1590	fBox.ExtractPolys(bPolys);
	1591	nFrontGeom[axis] = new BspNodeGeometry(bPolys);
[542]	1592	}
	1593	else
	1594	{
[710]	1595	nFrontGeom[axis] = new BspNodeGeometry();
	1596	nBackGeom[axis] = new BspNodeGeometry();
	1597
[573]	1598	nCostRatio[axis] =
	1599	EvalSplitPlaneCost(Plane3(normal, nPosition[axis]),
	1600	tData, nFrontGeom[axis], nBackGeom[axis],
	1601	nProbFront[axis], nProbBack[axis]);
[542]	1602	}
[480]	1603	}
[822]	1604
[978]	1605
[1006]	1606	if (mUseDrivingAxisIfMaxCostViolated)
[480]	1607	{
[978]	1608	// we take longest axis split if cost ratio exceeds threshold
	1609	if (nCostRatio[axis] < min(maxCostRatioForArbitraryAxis, nCostRatio[bestAxis]))
[822]	1610	{
	1611	bestAxis = axis;
	1612	}
[1072]	1613	/*else if (nCostRatio[axis] < nCostRatio[bestAxis])
	1614	{
[978]	1615	Debug << "taking split along longest axis (" << bestAxis << ") instead of (" << axis << ")" << endl;
[1072]	1616	}*/
	1617
[978]	1618	}
	1619	else
	1620	{
	1621	if (bestAxis == -1)
[822]	1622	{
	1623	bestAxis = axis;
	1624	}
[978]	1625	else if (nCostRatio[axis] < nCostRatio[bestAxis])
[822]	1626	{
	1627	bestAxis = axis;
	1628	}
[978]	1629	}
[463]	1630	}
	1631	}
	1632
[495]	1633	//-- assign values
[1072]	1634
[495]	1635	axis = bestAxis;
[547]	1636	pFront = nProbFront[bestAxis];
	1637	pBack = nProbBack[bestAxis];
[495]	1638
[508]	1639	// assign best split nodes geometry
	1640	*frontGeom = nFrontGeom[bestAxis];
	1641	*backGeom = nBackGeom[bestAxis];
[542]	1642
[508]	1643	// and delete other geometry
[612]	1644	DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
	1645	DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
[495]	1646
[508]	1647	//-- split plane
	1648	Vector3 normal(0,0,0); normal[bestAxis] = 1;
[480]	1649	plane = Plane3(normal, nPosition[bestAxis]);
[508]	1650
[822]	1651	//Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
[1072]	1652
[480]	1653	return nCostRatio[bestAxis];
[463]	1654	}
	1655
[480]	1656
[508]	1657	bool VspBspTree::SelectPlane(Plane3 &bestPlane,
	1658	BspLeaf *leaf,
[652]	1659	VspBspTraversalData &data,
[508]	1660	VspBspTraversalData &frontData,
[612]	1661	VspBspTraversalData &backData,
	1662	int &splitAxis)
[491]	1663	{
[810]	1664	// HACK matt: subdivide regularily to certain depth
[1072]	1665	if (data.mDepth < 0) // question matt: why depth < 0 ?
[801]	1666	{
[1072]	1667	cout << "depth: " << data.mDepth << endl;
	1668
[801]	1669	// return axis aligned split
	1670	AxisAlignedBox3 box;
	1671	box.Initialize();
	1672
	1673	// create bounding box of region
	1674	data.mGeometry->GetBoundingBox(box);
	1675
	1676	const int axis = box.Size().DrivingAxis();
	1677	const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	1678
	1679	Vector3 norm(0,0,0); norm[axis] = 1.0f;
	1680	bestPlane = Plane3(norm, position);
	1681	splitAxis = axis;
[1072]	1682
[801]	1683	return true;
	1684	}
	1685
[508]	1686	// simplest strategy: just take next polygon
	1687	if (mSplitPlaneStrategy & RANDOM_POLYGON)
[491]	1688	{
[508]	1689	if (!data.mPolygons->empty())
	1690	{
	1691	const int randIdx =
	1692	(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
	1693	Polygon3 nextPoly = (data.mPolygons)[randIdx];
[491]	1694
[508]	1695	bestPlane = nextPoly->GetSupportingPlane();
	1696	return true;
	1697	}
[491]	1698	}
	1699
[508]	1700	//-- use heuristics to find appropriate plane
[491]	1701
[508]	1702	// intermediate plane
	1703	Plane3 plane;
	1704	float lowestCost = MAX_FLOAT;
[517]	1705
	1706	// decides if the first few splits should be only axisAligned
[508]	1707	const bool onlyAxisAligned =
	1708	(mSplitPlaneStrategy & AXIS_ALIGNED) &&
	1709	((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
	1710	((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
	1711
	1712	const int limit = onlyAxisAligned ? 0 :
	1713	Min((int)data.mPolygons->size(), mMaxPolyCandidates);
[491]	1714
[508]	1715	float candidateCost;
[491]	1716
[508]	1717	int maxIdx = (int)data.mPolygons->size();
[491]	1718
[508]	1719	for (int i = 0; i < limit; ++ i)
[491]	1720	{
[562]	1721	// the already taken candidates are stored behind maxIdx
	1722	// => assure that no index is taken twice
[508]	1723	const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
	1724	Polygon3 poly = (data.mPolygons)[candidateIdx];
[491]	1725
[508]	1726	// swap candidate to the end to avoid testing same plane
	1727	std::swap((data.mPolygons)[maxIdx], (data.mPolygons)[candidateIdx]);
	1728	//Polygon3 poly = (data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
[491]	1729
[508]	1730	// evaluate current candidate
	1731	BspNodeGeometry fGeom, bGeom;
	1732	float fArea, bArea;
	1733	plane = poly->GetSupportingPlane();
[573]	1734	candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
[491]	1735
[508]	1736	if (candidateCost < lowestCost)
[491]	1737	{
[508]	1738	bestPlane = plane;
	1739	lowestCost = candidateCost;
[491]	1740	}
	1741	}
	1742
[1006]	1743
[508]	1744	//-- evaluate axis aligned splits
[1006]	1745
[508]	1746	int axis;
	1747	BspNodeGeometry fGeom, bGeom;
[547]	1748	float pFront, pBack;
[491]	1749
[653]	1750	candidateCost = 99999999.0f;
[491]	1751
[1006]	1752	// as a variant, we take axis aligned split only if there is
	1753	// more polygon available to guide the split
[653]	1754	if (!mUsePolygonSplitIfAvailable \|\| data.mPolygons->empty())
	1755	{
	1756	candidateCost = SelectAxisAlignedPlane(plane,
	1757	data,
	1758	axis,
	1759	&fGeom,
	1760	&bGeom,
	1761	pFront,
	1762	pBack,
	1763	data.mIsKdNode);
	1764	}
	1765
[612]	1766	splitAxis = 3;
[562]	1767
[508]	1768	if (candidateCost < lowestCost)
	1769	{
	1770	bestPlane = plane;
	1771	lowestCost = candidateCost;
[612]	1772	splitAxis = axis;
[653]	1773
[542]	1774	// assign already computed values
	1775	// we can do this because we always save the
[562]	1776	// computed values from the axis aligned splits
[653]	1777
[612]	1778	if (fGeom && bGeom)
	1779	{
	1780	frontData.mGeometry = fGeom;
	1781	backData.mGeometry = bGeom;
[547]	1782
[612]	1783	frontData.mProbability = pFront;
	1784	backData.mProbability = pBack;
	1785	}
[508]	1786	}
	1787	else
[463]	1788	{
[508]	1789	DEL_PTR(fGeom);
	1790	DEL_PTR(bGeom);
[463]	1791	}
[678]	1792
[679]	1793	#ifdef _DEBUG
[508]	1794	Debug << "plane lowest cost: " << lowestCost << endl;
[679]	1795	#endif
[508]	1796
[801]	1797	// exeeded relative max cost ratio
[508]	1798	if (lowestCost > mTermMaxCostRatio)
[611]	1799	{
[508]	1800	return false;
[611]	1801	}
[508]	1802
	1803	return true;
[463]	1804	}
	1805
[480]	1806
[473]	1807	Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
[482]	1808	{
[473]	1809	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
[482]	1810
[473]	1811	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
	1812	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
	1813
	1814	const Vector3 pt = (maxPt + minPt) * 0.5;
	1815	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
	1816
	1817	return Plane3(normal, pt);
	1818	}
	1819
[480]	1820
[473]	1821	Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
[482]	1822	{
[473]	1823	Vector3 pt[3];
[482]	1824
[473]	1825	int idx[3];
	1826	int cmaxT = 0;
	1827	int cminT = 0;
	1828	bool chooseMin = false;
	1829
	1830	for (int j = 0; j < 3; ++ j)
	1831	{
	1832	idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
[482]	1833
[473]	1834	if (idx[j] >= (int)rays.size())
	1835	{
	1836	idx[j] -= (int)rays.size();
[482]	1837
[473]	1838	chooseMin = (cminT < 2);
	1839	}
	1840	else
	1841	chooseMin = (cmaxT < 2);
	1842
	1843	RayInfo rayInf = rays[idx[j]];
	1844	pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
[482]	1845	}
[473]	1846
	1847	return Plane3(pt[0], pt[1], pt[2]);
	1848	}
	1849
[580]	1850
[473]	1851	Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
[482]	1852	{
[473]	1853	Vector3 pt[3];
[482]	1854
[473]	1855	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
	1856	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
	1857
	1858	// check if rays different
	1859	if (idx1 == idx2)
	1860	idx2 = (idx2 + 1) % (int)rays.size();
	1861
	1862	const RayInfo ray1 = rays[idx1];
	1863	const RayInfo ray2 = rays[idx2];
	1864
	1865	// normal vector of the plane parallel to both lines
	1866	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
	1867
	1868	// vector from line 1 to line 2
[479]	1869	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
[482]	1870
[473]	1871	// project vector on normal to get distance
	1872	const float dist = DotProd(vd, norm);
	1873
	1874	// point on plane lies halfway between the two planes
	1875	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
	1876
	1877	return Plane3(norm, planePt);
	1878	}
	1879
[495]	1880
[463]	1881	inline void VspBspTree::GenerateUniqueIdsForPvs()
	1882	{
[580]	1883	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
	1884	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
	1885	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
[463]	1886	}
	1887
[495]	1888
[652]	1889	float VspBspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
	1890	const VspBspTraversalData &data) const
	1891	{
[729]	1892	float pvsFront = 0;
	1893	float pvsBack = 0;
	1894	float totalPvs = 0;
[652]	1895
	1896	// probability that view point lies in back / front node
	1897	float pOverall = data.mProbability;
	1898	float pFront = 0;
	1899	float pBack = 0;
	1900
	1901
	1902	// create unique ids for pvs heuristics
	1903	GenerateUniqueIdsForPvs();
	1904
	1905	for (int i = 0; i < data.mRays->size(); ++ i)
	1906	{
	1907	RayInfo rayInf = (*data.mRays)[i];
	1908
	1909	float t;
	1910	VssRay *ray = rayInf.mRay;
	1911	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
	1912
	1913	// find front and back pvs for origing and termination object
	1914	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
[1020]	1915
	1916	if (COUNT_ORIGIN_OBJECTS)
	1917	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
[652]	1918	}
	1919
	1920
	1921	BspNodeGeometry geomFront;
	1922	BspNodeGeometry geomBack;
	1923
	1924	// construct child geometry with regard to the candidate split plane
	1925	data.mGeometry->SplitGeometry(geomFront,
	1926	geomBack,
	1927	candidatePlane,
	1928	mBox,
[679]	1929	//0.0f);
	1930	mEpsilon);
[652]	1931
	1932	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
	1933	{
	1934	pFront = geomFront.GetVolume();
	1935	pBack = pOverall - pFront;
[675]	1936
[729]	1937	// something is wrong with the volume
[1027]	1938	if (0 && ((pFront < 0.0) \|\| (pBack < 0.0)))
[676]	1939	{
[752]	1940	Debug << "ERROR in volume:\n"
	1941	<< "volume f :" << pFront << " b: " << pBack << " p: " << pOverall
	1942	<< ", real volume f: " << pFront << " b: " << geomBack.GetVolume()
	1943	<< ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl;
[676]	1944	}
[652]	1945	}
	1946	else
	1947	{
	1948	pFront = geomFront.GetArea();
	1949	pBack = geomBack.GetArea();
	1950	}
	1951
	1952
	1953	// -- pvs rendering heuristics
[1020]	1954
	1955	// upper and lower bounds
[652]	1956	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1957	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1958
[1020]	1959	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	1960	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	1961	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[652]	1962
	1963	const float oldRenderCost = pOverall * penaltyOld;
	1964	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1965
[654]	1966	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
[752]	1967	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
	1968
[1020]	1969	const float weight = mRenderCostDecreaseWeight;
[1006]	1970	// take render cost of node into account to avoid being stuck in a local minimum
[752]	1971	const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
[1006]	1972
[1020]	1973	//Debug << "rendercostdecr: " << weight * renderCostDecrease << " old render cost: " << (1.0f - weight) * normalizedOldRenderCost << endl;
	1974	return weight * renderCostDecrease + (1.0f - weight) * normalizedOldRenderCost;
[652]	1975	}
	1976
	1977
[573]	1978	float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
	1979	const VspBspTraversalData &data,
	1980	BspNodeGeometry &geomFront,
	1981	BspNodeGeometry &geomBack,
	1982	float &pFront,
	1983	float &pBack) const
[463]	1984	{
[729]	1985	float totalPvs = 0;
	1986	float pvsFront = 0;
	1987	float pvsBack = 0;
[652]	1988
[1006]	1989	// overall probability is used as normalizer
[463]	1990	float pOverall = 0;
[1006]	1991
	1992	// probability that view point lies in back / front node
[547]	1993	pFront = 0;
	1994	pBack = 0;
[463]	1995
[1020]	1996	int numTests; // the number of tests
[508]	1997
[1020]	1998	// if random samples shold be taken instead of testing all the rays
	1999	bool useRand;
[463]	2000
	2001	if ((int)data.mRays->size() > mMaxTests)
	2002	{
	2003	useRand = true;
[1020]	2004	numTests = mMaxTests;
[463]	2005	}
	2006	else
	2007	{
	2008	useRand = false;
[1020]	2009	numTests = (int)data.mRays->size();
[463]	2010	}
[508]	2011
[1020]	2012	// create unique ids for pvs heuristics
	2013	GenerateUniqueIdsForPvs();
	2014
	2015	for (int i = 0; i < numTests; ++ i)
[463]	2016	{
[508]	2017	const int testIdx = useRand ?
	2018	(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
[463]	2019	RayInfo rayInf = (*data.mRays)[testIdx];
	2020
	2021	float t;
[508]	2022	VssRay *ray = rayInf.mRay;
[463]	2023	const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
	2024
[652]	2025	// find front and back pvs for origing and termination object
	2026	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
[1020]	2027
	2028	if (COUNT_ORIGIN_OBJECTS)
	2029	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
[652]	2030	}
[508]	2031
[652]	2032	// construct child geometry with regard to the candidate split plane
[679]	2033	bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront,
	2034	geomBack,
	2035	candidatePlane,
	2036	mBox,
	2037	//0.0f);
	2038	mEpsilon);
[675]	2039
[652]	2040	pOverall = data.mProbability;
[463]	2041
[652]	2042	if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
	2043	{
	2044	pFront = geomFront.GetVolume();
	2045	pBack = pOverall - pFront;
[675]	2046
[729]	2047	// HACK: precision issues possible for unbalanced split => don't take this split!
[685]	2048	if (1 &&
[682]	2049	(!splitSuccessFull \|\| (pFront <= 0) \|\| (pBack <= 0) \|\|
	2050	!geomFront.Valid() \|\| !geomBack.Valid()))
[676]	2051	{
[752]	2052	//Debug << "error f: " << pFront << " b: " << pBack << endl;
[1027]	2053
	2054	// high penalty for degenerated / wrong split
[711]	2055	return 99999.9f;
[676]	2056	}
[463]	2057	}
[652]	2058	else
[542]	2059	{
[652]	2060	pFront = geomFront.GetArea();
	2061	pBack = geomBack.GetArea();
[542]	2062	}
[652]	2063
[542]	2064
[580]	2065	// -- pvs rendering heuristics
[652]	2066	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	2067	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
[580]	2068
[652]	2069	// only render cost heuristics or combined with standard deviation
[752]	2070	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	2071	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	2072	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[579]	2073
[652]	2074	const float oldRenderCost = pOverall * penaltyOld;
	2075	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
[579]	2076
[652]	2077	float oldCost, newCost;
[580]	2078
[652]	2079	// only render cost
	2080	if (1)
	2081	{
	2082	oldCost = oldRenderCost;
	2083	newCost = newRenderCost;
	2084	}
	2085	else // also considering standard deviation
	2086	{
	2087	// standard deviation is difference of back and front pvs
	2088	const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
[580]	2089
[652]	2090	const float newDeviation = 0.5f *
	2091	fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
[580]	2092
[652]	2093	const float oldDeviation = penaltyOld;
[580]	2094
[652]	2095	newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
	2096	oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
	2097	}
[580]	2098
[1020]	2099	const float cost = mPvsFactor * newCost / (oldCost + Limits::Small);
[607]	2100
[463]	2101
	2102	#ifdef _DEBUG
[474]	2103	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
[508]	2104	<< " frontpvs: " << pvsFront << " pFront: " << pFront
	2105	<< " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
[600]	2106	Debug << "cost: " << cost << endl;
[463]	2107	#endif
[482]	2108
[652]	2109	return cost;
[463]	2110	}
	2111
[508]	2112
[697]	2113	int VspBspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
	2114	ViewCellContainer &viewCells) const
	2115	{
	2116	stack<bspNodePair> nodeStack;
	2117	BspNodeGeometry *rgeom = new BspNodeGeometry();
	2118
	2119	ConstructGeometry(mRoot, *rgeom);
	2120
	2121	nodeStack.push(bspNodePair(mRoot, rgeom));
	2122
	2123	ViewCell::NewMail();
	2124
	2125	while (!nodeStack.empty())
	2126	{
	2127	BspNode *node = nodeStack.top().first;
	2128	BspNodeGeometry *geom = nodeStack.top().second;
	2129	nodeStack.pop();
	2130
	2131	const int side = geom->ComputeIntersection(box);
	2132
	2133	switch (side)
	2134	{
	2135	case -1:
	2136	// node geometry is contained in box
	2137	CollectViewCells(node, true, viewCells, true);
	2138	break;
	2139
	2140	case 0:
	2141	if (node->IsLeaf())
	2142	{
	2143	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2144
	2145	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
	2146	{
	2147	leaf->GetViewCell()->Mail();
	2148	viewCells.push_back(leaf->GetViewCell());
	2149	}
	2150	}
	2151	else
	2152	{
	2153	BspInterior interior = dynamic_cast<BspInterior >(node);
	2154
	2155	BspNode *first = interior->GetFront();
	2156	BspNode *second = interior->GetBack();
	2157
	2158	BspNodeGeometry *firstGeom = new BspNodeGeometry();
	2159	BspNodeGeometry *secondGeom = new BspNodeGeometry();
	2160
	2161	geom->SplitGeometry(*firstGeom,
	2162	*secondGeom,
	2163	interior->GetPlane(),
	2164	mBox,
	2165	//0.0000001f);
	2166	mEpsilon);
	2167
	2168	nodeStack.push(bspNodePair(first, firstGeom));
	2169	nodeStack.push(bspNodePair(second, secondGeom));
	2170	}
	2171
	2172	break;
	2173	default:
	2174	// default: cull
	2175	break;
	2176	}
	2177
	2178	DEL_PTR(geom);
	2179
	2180	}
	2181
	2182	return (int)viewCells.size();
	2183	}
	2184
	2185
[580]	2186	float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
	2187	const AxisAlignedBox3 &box,
	2188	const int axis,
	2189	const float &position,
	2190	float &pFront,
	2191	float &pBack) const
	2192	{
[729]	2193	float pvsTotal = 0;
	2194	float pvsFront = 0;
	2195	float pvsBack = 0;
[580]	2196
	2197	// create unique ids for pvs heuristics
	2198	GenerateUniqueIdsForPvs();
	2199
	2200	const int pvsSize = data.mPvs;
[726]	2201
[580]	2202	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
	2203
	2204	// this is the main ray classification loop!
	2205	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	2206	{
	2207	// determine the side of this ray with respect to the plane
	2208	float t;
	2209	const int side = (*rit).ComputeRayIntersection(axis, position, t);
	2210
	2211	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
[1020]	2212
	2213	if (COUNT_ORIGIN_OBJECTS)
	2214	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
[580]	2215	}
	2216
[1020]	2217
[580]	2218	//-- pvs heuristics
	2219
[1020]	2220	float pOverall = data.mProbability;
[580]	2221
[1020]	2222	// note: we use a simplified computation assuming that we always do a
	2223	// spatial mid split
	2224
[580]	2225	if (!mUseAreaForPvs)
[1020]	2226	{
	2227	// volume
[580]	2228	pBack = pFront = pOverall * 0.5f;
	2229	#if 0
	2230	// box length substitute for probability
	2231	const float minBox = box.Min(axis);
	2232	const float maxBox = box.Max(axis);
	2233
	2234	pBack = position - minBox;
	2235	pFront = maxBox - position;
	2236	pOverall = maxBox - minBox;
	2237	#endif
	2238	}
	2239	else //-- area substitute for probability
	2240	{
	2241	const int axis2 = (axis + 1) % 3;
	2242	const int axis3 = (axis + 2) % 3;
	2243
	2244	const float faceArea =
	2245	(box.Max(axis2) - box.Min(axis2)) *
	2246	(box.Max(axis3) - box.Min(axis3));
	2247
	2248	pBack = pFront = pOverall * 0.5f + faceArea;
	2249	}
	2250
	2251	#ifdef _DEBUG
	2252	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	2253	Debug << pFront << " " << pBack << " " << pOverall << endl;
	2254	#endif
	2255
	2256
	2257	const float newCost = pvsBack * pBack + pvsFront * pFront;
	2258	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
	2259
	2260	return (mCtDivCi + newCost) / oldCost;
	2261	}
	2262
	2263
[463]	2264	void VspBspTree::AddObjToPvs(Intersectable *obj,
	2265	const int cf,
[729]	2266	float &frontPvs,
	2267	float &backPvs,
	2268	float &totalPvs) const
[463]	2269	{
	2270	if (!obj)
	2271	return;
[728]	2272
[744]	2273	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
	2274
[654]	2275	// new object
[508]	2276	if ((obj->mMailbox != sFrontId) &&
	2277	(obj->mMailbox != sBackId) &&
	2278	(obj->mMailbox != sFrontAndBackId))
	2279	{
[744]	2280	totalPvs += renderCost;
[508]	2281	}
	2282
[463]	2283	// TODO: does this really belong to no pvs?
	2284	//if (cf == Ray::COINCIDENT) return;
	2285
	2286	// object belongs to both PVS
	2287	if (cf >= 0)
	2288	{
[482]	2289	if ((obj->mMailbox != sFrontId) &&
[463]	2290	(obj->mMailbox != sFrontAndBackId))
	2291	{
[744]	2292	frontPvs += renderCost;
[508]	2293
[463]	2294	if (obj->mMailbox == sBackId)
[482]	2295	obj->mMailbox = sFrontAndBackId;
[463]	2296	else
[482]	2297	obj->mMailbox = sFrontId;
[463]	2298	}
	2299	}
[482]	2300
[463]	2301	if (cf <= 0)
	2302	{
	2303	if ((obj->mMailbox != sBackId) &&
	2304	(obj->mMailbox != sFrontAndBackId))
	2305	{
[744]	2306	backPvs += renderCost;
[508]	2307
[463]	2308	if (obj->mMailbox == sFrontId)
[482]	2309	obj->mMailbox = sFrontAndBackId;
[463]	2310	else
[482]	2311	obj->mMailbox = sBackId;
[463]	2312	}
	2313	}
	2314	}
	2315
[491]	2316
[503]	2317	void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
	2318	const bool onlyUnmailed,
	2319	const int maxPvsSize) const
[463]	2320	{
	2321	stack<BspNode *> nodeStack;
	2322	nodeStack.push(mRoot);
[482]	2323
	2324	while (!nodeStack.empty())
[463]	2325	{
	2326	BspNode *node = nodeStack.top();
	2327	nodeStack.pop();
[489]	2328
[482]	2329	if (node->IsLeaf())
[463]	2330	{
[490]	2331	// test if this leaf is in valid view space
[503]	2332	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2333	if (leaf->TreeValid() &&
[508]	2334	(!onlyUnmailed \|\| !leaf->Mailed()) &&
[503]	2335	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
[490]	2336	{
	2337	leaves.push_back(leaf);
	2338	}
[482]	2339	}
	2340	else
[463]	2341	{
	2342	BspInterior interior = dynamic_cast<BspInterior >(node);
	2343
	2344	nodeStack.push(interior->GetBack());
	2345	nodeStack.push(interior->GetFront());
	2346	}
	2347	}
	2348	}
	2349
[489]	2350
[463]	2351	AxisAlignedBox3 VspBspTree::GetBoundingBox() const
	2352	{
	2353	return mBox;
	2354	}
	2355
[489]	2356
[463]	2357	BspNode *VspBspTree::GetRoot() const
	2358	{
	2359	return mRoot;
	2360	}
	2361
[489]	2362
[463]	2363	void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
	2364	{
	2365	// the node became a leaf -> evaluate stats for leafs
	2366	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
	2367
	2368
[574]	2369	if (data.mPvs > mBspStats.maxPvs)
[711]	2370	{
[574]	2371	mBspStats.maxPvs = data.mPvs;
[711]	2372	}
	2373
[656]	2374	mBspStats.pvs += data.mPvs;
	2375
[574]	2376	if (data.mDepth < mBspStats.minDepth)
[711]	2377	{
[574]	2378	mBspStats.minDepth = data.mDepth;
[711]	2379	}
[656]	2380
[463]	2381	if (data.mDepth >= mTermMaxDepth)
[711]	2382	{
[744]	2383	++ mBspStats.maxDepthNodes;
	2384	//Debug << "new max depth: " << mBspStats.maxDepthNodes << endl;
[711]	2385	}
[611]	2386
[508]	2387	// accumulate rays to compute rays / leaf
[574]	2388	mBspStats.accumRays += (int)data.mRays->size();
[463]	2389
[437]	2390	if (data.mPvs < mTermMinPvs)
[574]	2391	++ mBspStats.minPvsNodes;
[437]	2392
	2393	if ((int)data.mRays->size() < mTermMinRays)
[574]	2394	++ mBspStats.minRaysNodes;
[437]	2395
	2396	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[574]	2397	++ mBspStats.maxRayContribNodes;
[482]	2398
[547]	2399	if (data.mProbability <= mTermMinProbability)
[574]	2400	++ mBspStats.minProbabilityNodes;
[508]	2401
[474]	2402	// accumulate depth to compute average depth
[574]	2403	mBspStats.accumDepth += data.mDepth;
[463]	2404
[612]	2405	++ mCreatedViewCells;
[656]	2406
[463]	2407	#ifdef _DEBUG
	2408	Debug << "BSP stats: "
	2409	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	2410	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
[1027]	2411	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
	2412	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[463]	2413	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
	2414	#endif
	2415	}
	2416
[612]	2417
[463]	2418	int VspBspTree::CastRay(Ray &ray)
	2419	{
	2420	int hits = 0;
[482]	2421
[600]	2422	stack<BspRayTraversalData> tQueue;
[482]	2423
[463]	2424	float maxt, mint;
	2425
	2426	if (!mBox.GetRaySegment(ray, mint, maxt))
	2427	return 0;
	2428
	2429	Intersectable::NewMail();
[600]	2430	ViewCell::NewMail();
[1012]	2431
[463]	2432	Vector3 entp = ray.Extrap(mint);
	2433	Vector3 extp = ray.Extrap(maxt);
[482]	2434
[463]	2435	BspNode *node = mRoot;
	2436	BspNode *farChild = NULL;
[482]	2437
[463]	2438	while (1)
	2439	{
[482]	2440	if (!node->IsLeaf())
[463]	2441	{
	2442	BspInterior in = dynamic_cast<BspInterior >(node);
	2443
	2444	Plane3 splitPlane = in->GetPlane();
	2445	const int entSide = splitPlane.Side(entp);
	2446	const int extSide = splitPlane.Side(extp);
	2447
	2448	if (entSide < 0)
	2449	{
	2450	node = in->GetBack();
	2451
	2452	if(extSide <= 0) // plane does not split ray => no far child
	2453	continue;
[482]	2454
[463]	2455	farChild = in->GetFront(); // plane splits ray
	2456
	2457	} else if (entSide > 0)
	2458	{
	2459	node = in->GetFront();
	2460
	2461	if (extSide >= 0) // plane does not split ray => no far child
	2462	continue;
	2463
[482]	2464	farChild = in->GetBack(); // plane splits ray
[463]	2465	}
	2466	else // ray and plane are coincident
	2467	{
[1012]	2468	// matt: WHAT TO DO IN THIS CASE ?
[463]	2469	//break;
	2470	node = in->GetFront();
	2471	continue;
	2472	}
	2473
	2474	// push data for far child
[600]	2475	tQueue.push(BspRayTraversalData(farChild, extp, maxt));
[463]	2476
	2477	// find intersection of ray segment with plane
	2478	float t;
	2479	extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
	2480	maxt *= t;
[1047]	2481	}
	2482	else // reached leaf => intersection with view cell
[463]	2483	{
	2484	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
[482]	2485
[463]	2486	if (!leaf->GetViewCell()->Mailed())
	2487	{
	2488	//ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
	2489	leaf->GetViewCell()->Mail();
	2490	++ hits;
	2491	}
[482]	2492
[463]	2493	//-- fetch the next far child from the stack
[600]	2494	if (tQueue.empty())
[463]	2495	break;
[482]	2496
[463]	2497	entp = extp;
	2498	mint = maxt; // NOTE: need this?
	2499
	2500	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
	2501	break;
	2502
[600]	2503	BspRayTraversalData &s = tQueue.top();
[463]	2504
	2505	node = s.mNode;
	2506	extp = s.mExitPoint;
	2507	maxt = s.mMaxT;
	2508
[600]	2509	tQueue.pop();
[463]	2510	}
	2511	}
	2512
	2513	return hits;
	2514	}
	2515
[532]	2516
[1072]	2517	void VspBspTree::CollectViewCells(ViewCellContainer &viewCells,
	2518	bool onlyValid) const
[463]	2519	{
[532]	2520	ViewCell::NewMail();
[551]	2521
	2522	CollectViewCells(mRoot, onlyValid, viewCells, true);
[532]	2523	}
	2524
	2525
[574]	2526	void VspBspTree::CollapseViewCells()
[542]	2527	{
[590]	2528	// TODO
[728]	2529	#if HAS_TO_BE_REDONE
[542]	2530	stack<BspNode *> nodeStack;
	2531
	2532	if (!mRoot)
	2533	return;
	2534
	2535	nodeStack.push(mRoot);
	2536
	2537	while (!nodeStack.empty())
	2538	{
	2539	BspNode *node = nodeStack.top();
	2540	nodeStack.pop();
	2541
	2542	if (node->IsLeaf())
[574]	2543	{
	2544	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
[542]	2545
[574]	2546	if (!viewCell->GetValid())
[542]	2547	{
	2548	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->GetViewCell();
[580]	2549
	2550	ViewCellContainer leaves;
[590]	2551	mViewCellsTree->CollectLeaves(viewCell, leaves);
[580]	2552
	2553	ViewCellContainer::const_iterator it, it_end = leaves.end();
	2554
	2555	for (it = leaves.begin(); it != it_end; ++ it)
[542]	2556	{
[580]	2557	BspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[574]	2558	l->SetViewCell(GetOrCreateOutOfBoundsCell());
	2559	++ mBspStats.invalidLeaves;
	2560	}
[542]	2561
[574]	2562	// add to unbounded view cell
	2563	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
	2564	DEL_PTR(viewCell);
	2565	}
	2566	}
	2567	else
	2568	{
	2569	BspInterior interior = dynamic_cast<BspInterior >(node);
	2570
	2571	nodeStack.push(interior->GetFront());
	2572	nodeStack.push(interior->GetBack());
	2573	}
	2574	}
[542]	2575
[574]	2576	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
[590]	2577	#endif
[574]	2578	}
	2579
	2580
[639]	2581	void VspBspTree::CollectRays(VssRayContainer &rays)
	2582	{
	2583	vector<BspLeaf *> leaves;
	2584
	2585	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
	2586
	2587	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	2588	{
	2589	BspLeaf leaf = lit;
	2590	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	2591
	2592	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	2593	rays.push_back(*rit);
	2594	}
	2595	}
	2596
	2597
[574]	2598	void VspBspTree::ValidateTree()
	2599	{
	2600	stack<BspNode *> nodeStack;
	2601
	2602	if (!mRoot)
	2603	return;
	2604
	2605	nodeStack.push(mRoot);
	2606
	2607	mBspStats.invalidLeaves = 0;
	2608	while (!nodeStack.empty())
	2609	{
	2610	BspNode *node = nodeStack.top();
	2611	nodeStack.pop();
	2612
	2613	if (node->IsLeaf())
	2614	{
	2615	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2616
	2617	if (!leaf->GetViewCell()->GetValid())
	2618	++ mBspStats.invalidLeaves;
	2619
	2620	// validity flags don't match => repair
	2621	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
	2622	{
	2623	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
	2624	PropagateUpValidity(leaf);
[542]	2625	}
	2626	}
	2627	else
	2628	{
	2629	BspInterior interior = dynamic_cast<BspInterior >(node);
	2630
	2631	nodeStack.push(interior->GetFront());
	2632	nodeStack.push(interior->GetBack());
	2633	}
	2634	}
[562]	2635
[574]	2636	Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
[542]	2637	}
	2638
[547]	2639
[574]	2640
[547]	2641	void VspBspTree::CollectViewCells(BspNode *root,
	2642	bool onlyValid,
[532]	2643	ViewCellContainer &viewCells,
	2644	bool onlyUnmailed) const
	2645	{
[498]	2646	stack<BspNode *> nodeStack;
[463]	2647
[538]	2648	if (!root)
[508]	2649	return;
[463]	2650
[538]	2651	nodeStack.push(root);
[498]	2652
	2653	while (!nodeStack.empty())
	2654	{
	2655	BspNode *node = nodeStack.top();
	2656	nodeStack.pop();
	2657
	2658	if (node->IsLeaf())
	2659	{
[564]	2660	if (!onlyValid \|\| node->TreeValid())
[498]	2661	{
[882]	2662	ViewCellLeaf leafVc = dynamic_cast<BspLeaf >(node)->GetViewCell();
[727]	2663
	2664	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
[590]	2665
[532]	2666	if (!onlyUnmailed \|\| !viewCell->Mailed())
[498]	2667	{
	2668	viewCell->Mail();
	2669	viewCells.push_back(viewCell);
	2670	}
	2671	}
	2672	}
	2673	else
	2674	{
	2675	BspInterior interior = dynamic_cast<BspInterior >(node);
[508]	2676
[498]	2677	nodeStack.push(interior->GetFront());
	2678	nodeStack.push(interior->GetBack());
	2679	}
	2680	}
[590]	2681
[463]	2682	}
	2683
	2684
[648]	2685	void VspBspTree::PreprocessPolygons(PolygonContainer &polys)
	2686	{
	2687	// preprocess: throw out polygons coincident to the view space box (not needed)
	2688	PolygonContainer boxPolys;
[1027]	2689
	2690	mBox.ExtractPolys(boxPolys);
[648]	2691	vector<Plane3> boxPlanes;
	2692
	2693	PolygonContainer::iterator pit, pit_end = boxPolys.end();
	2694
	2695	// extract planes of box
	2696	// TODO: can be done more elegantly than first extracting polygons
	2697	// and take their planes
	2698	for (pit = boxPolys.begin(); pit != pit_end; ++ pit)
	2699	{
	2700	boxPlanes.push_back((*pit)->GetSupportingPlane());
	2701	}
	2702
	2703	pit_end = polys.end();
	2704
	2705	for (pit = polys.begin(); pit != pit_end; ++ pit)
	2706	{
	2707	vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end();
	2708
	2709	for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit)
	2710	{
	2711	const int cf = (pit)->ClassifyPlane(bit, mEpsilon);
	2712
	2713	if (cf == Polygon3::COINCIDENT)
	2714	{
	2715	DEL_PTR(*pit);
	2716	//Debug << "coincident!!" << endl;
	2717	}
	2718	}
	2719	}
	2720
[1002]	2721	// remove deleted entries after swapping them to end of vector
[648]	2722	for (int i = 0; i < (int)polys.size(); ++ i)
	2723	{
	2724	while (!polys[i] && (i < (int)polys.size()))
	2725	{
	2726	swap(polys[i], polys.back());
	2727	polys.pop_back();
	2728	}
[1027]	2729	}
[648]	2730	}
	2731
	2732
[463]	2733	float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
	2734	{
	2735	float len = 0;
	2736
	2737	RayInfoContainer::const_iterator it, it_end = rays.end();
	2738
	2739	for (it = rays.begin(); it != it_end; ++ it)
	2740	len += (*it).SegmentLength();
	2741
	2742	return len;
	2743	}
	2744
[479]	2745
[463]	2746	int VspBspTree::SplitRays(const Plane3 &plane,
[482]	2747	RayInfoContainer &rays,
	2748	RayInfoContainer &frontRays,
[639]	2749	RayInfoContainer &backRays) const
[463]	2750	{
	2751	int splits = 0;
	2752
[574]	2753	RayInfoContainer::const_iterator it, it_end = rays.end();
	2754
	2755	for (it = rays.begin(); it != it_end; ++ it)
[463]	2756	{
[574]	2757	RayInfo bRay = *it;
	2758
[463]	2759	VssRay *ray = bRay.mRay;
[473]	2760	float t;
[463]	2761
[485]	2762	// get classification and receive new t
[463]	2763	const int cf = bRay.ComputeRayIntersection(plane, t);
[482]	2764
[463]	2765	switch (cf)
	2766	{
	2767	case -1:
	2768	backRays.push_back(bRay);
	2769	break;
	2770	case 1:
	2771	frontRays.push_back(bRay);
	2772	break;
[482]	2773	case 0:
	2774	{
[485]	2775	//-- split ray
[639]	2776	// test if start point behind or in front of plane
[485]	2777	const int side = plane.Side(bRay.ExtrapOrigin());
	2778
[1011]	2779	++ splits;
	2780
[485]	2781	if (side <= 0)
	2782	{
	2783	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2784	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2785	}
	2786	else
	2787	{
	2788	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2789	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2790	}
[463]	2791	}
	2792	break;
	2793	default:
[485]	2794	Debug << "Should not come here" << endl;
[463]	2795	break;
	2796	}
	2797	}
	2798
	2799	return splits;
	2800	}
	2801
[479]	2802
[463]	2803	void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
	2804	{
	2805	BspNode *lastNode;
	2806
	2807	do
	2808	{
	2809	lastNode = n;
	2810
	2811	// want to get planes defining geometry of this node => don't take
	2812	// split plane of node itself
	2813	n = n->GetParent();
[482]	2814
[463]	2815	if (n)
	2816	{
	2817	BspInterior interior = dynamic_cast<BspInterior >(n);
	2818	Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
	2819
[683]	2820	if (interior->GetBack() != lastNode)
[463]	2821	halfSpace.ReverseOrientation();
	2822
	2823	halfSpaces.push_back(halfSpace);
	2824	}
	2825	}
	2826	while (n);
	2827	}
	2828
[485]	2829
[482]	2830	void VspBspTree::ConstructGeometry(BspNode *n,
[503]	2831	BspNodeGeometry &geom) const
[463]	2832	{
[437]	2833	vector<Plane3> halfSpaces;
	2834	ExtractHalfSpaces(n, halfSpaces);
	2835
	2836	PolygonContainer candidatePolys;
[678]	2837	vector<Plane3> candidatePlanes;
[437]	2838
[719]	2839	vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end();
	2840
[683]	2841	// bounded planes are added to the polygons
[719]	2842	for (pit = halfSpaces.begin(); pit != pit_end; ++ pit)
[437]	2843	{
[719]	2844	Polygon3 p = GetBoundingBox().CrossSection(pit);
[482]	2845
[448]	2846	if (p->Valid(mEpsilon))
[437]	2847	{
[683]	2848	candidatePolys.push_back(p);
[719]	2849	candidatePlanes.push_back(*pit);
[437]	2850	}
	2851	}
	2852
	2853	// add faces of bounding box (also could be faces of the cell)
	2854	for (int i = 0; i < 6; ++ i)
	2855	{
	2856	VertexContainer vertices;
[482]	2857
[437]	2858	for (int j = 0; j < 4; ++ j)
	2859	vertices.push_back(mBox.GetFace(i).mVertices[j]);
	2860
[678]	2861	Polygon3 *poly = new Polygon3(vertices);
	2862
	2863	candidatePolys.push_back(poly);
	2864	candidatePlanes.push_back(poly->GetSupportingPlane());
[437]	2865	}
	2866
	2867	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
	2868	{
	2869	// polygon is split by all other planes
	2870	for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
	2871	{
	2872	if (i == j) // polygon and plane are coincident
	2873	continue;
	2874
	2875	VertexContainer splitPts;
	2876	Polygon3 frontPoly, backPoly;
	2877
[482]	2878	const int cf =
[448]	2879	candidatePolys[i]->ClassifyPlane(halfSpaces[j],
	2880	mEpsilon);
[482]	2881
[437]	2882	switch (cf)
	2883	{
	2884	case Polygon3::SPLIT:
	2885	frontPoly = new Polygon3();
	2886	backPoly = new Polygon3();
	2887
[482]	2888	candidatePolys[i]->Split(halfSpaces[j],
	2889	*frontPoly,
[448]	2890	*backPoly,
	2891	mEpsilon);
[437]	2892
	2893	DEL_PTR(candidatePolys[i]);
	2894
[683]	2895	if (backPoly->Valid(mEpsilon))
	2896	candidatePolys[i] = backPoly;
[437]	2897	else
[683]	2898	DEL_PTR(backPoly);
[437]	2899
[683]	2900	// outside, don't need this
	2901	DEL_PTR(frontPoly);
[437]	2902	break;
[683]	2903	// polygon outside of halfspace
	2904	case Polygon3::FRONT_SIDE:
[437]	2905	DEL_PTR(candidatePolys[i]);
	2906	break;
	2907	// just take polygon as it is
[683]	2908	case Polygon3::BACK_SIDE:
[437]	2909	case Polygon3::COINCIDENT:
	2910	default:
	2911	break;
	2912	}
	2913	}
[482]	2914
[437]	2915	if (candidatePolys[i])
[678]	2916	{
	2917	geom.Add(candidatePolys[i], candidatePlanes[i]);
	2918	// geom.mPolys.push_back(candidates[i]);
	2919	}
[437]	2920	}
[463]	2921	}
	2922
[485]	2923
[582]	2924	void VspBspTree::ConstructGeometry(ViewCell *vc,
[503]	2925	BspNodeGeometry &vcGeom) const
[589]	2926	{
[580]	2927	ViewCellContainer leaves;
[590]	2928
	2929	mViewCellsTree->CollectLeaves(vc, leaves);
[463]	2930
[580]	2931	ViewCellContainer::const_iterator it, it_end = leaves.end();
	2932
[463]	2933	for (it = leaves.begin(); it != it_end; ++ it)
[580]	2934	{
	2935	BspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[590]	2936
[580]	2937	ConstructGeometry(l, vcGeom);
	2938	}
[463]	2939	}
	2940
[485]	2941
[482]	2942	int VspBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
[562]	2943	const bool onlyUnmailed) const
[463]	2944	{
[551]	2945	stack<bspNodePair> nodeStack;
	2946
	2947	BspNodeGeometry nodeGeom;
	2948	ConstructGeometry(n, nodeGeom);
[801]	2949	// const float eps = 0.5f;
[752]	2950	const float eps = 0.01f;
[500]	2951	// split planes from the root to this node
	2952	// needed to verify that we found neighbor leaf
[557]	2953	// TODO: really needed?
[463]	2954	vector<Plane3> halfSpaces;
	2955	ExtractHalfSpaces(n, halfSpaces);
	2956
[551]	2957
	2958	BspNodeGeometry *rgeom = new BspNodeGeometry();
	2959	ConstructGeometry(mRoot, *rgeom);
	2960
	2961	nodeStack.push(bspNodePair(mRoot, rgeom));
	2962
[482]	2963	while (!nodeStack.empty())
[463]	2964	{
[551]	2965	BspNode *node = nodeStack.top().first;
	2966	BspNodeGeometry *geom = nodeStack.top().second;
[562]	2967
[463]	2968	nodeStack.pop();
	2969
[557]	2970	if (node->IsLeaf())
[562]	2971	{
[557]	2972	// test if this leaf is in valid view space
	2973	if (node->TreeValid() &&
	2974	(node != n) &&
	2975	(!onlyUnmailed \|\| !node->Mailed()))
	2976	{
	2977	bool isAdjacent = true;
[551]	2978
[570]	2979	if (1)
[557]	2980	{
[562]	2981	// test all planes of current node if still adjacent
	2982	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
	2983	{
	2984	const int cf =
[678]	2985	Polygon3::ClassifyPlane(geom->GetPolys(),
[562]	2986	halfSpaces[i],
[752]	2987	eps);
[482]	2988
[683]	2989	if (cf == Polygon3::FRONT_SIDE)
[562]	2990	{
	2991	isAdjacent = false;
	2992	}
[557]	2993	}
	2994	}
[562]	2995	else
[557]	2996	{
[562]	2997	// TODO: why is this wrong??
	2998	// test all planes of current node if still adjacent
[678]	2999	for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
[562]	3000	{
[678]	3001	Polygon3 *poly = nodeGeom.GetPolys()[i];
[555]	3002
[562]	3003	const int cf =
[678]	3004	Polygon3::ClassifyPlane(geom->GetPolys(),
[562]	3005	poly->GetSupportingPlane(),
[752]	3006	eps);
[557]	3007
[683]	3008	if (cf == Polygon3::FRONT_SIDE)
[562]	3009	{
	3010	isAdjacent = false;
	3011	}
[557]	3012	}
[570]	3013	}
[557]	3014	// neighbor was found
	3015	if (isAdjacent)
[562]	3016	{
[551]	3017	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
[562]	3018	}
[463]	3019	}
[562]	3020	}
	3021	else
	3022	{
	3023	BspInterior interior = dynamic_cast<BspInterior >(node);
[482]	3024
[678]	3025	const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
[562]	3026	interior->GetPlane(),
[752]	3027	eps);
[551]	3028
[562]	3029	BspNode *front = interior->GetFront();
	3030	BspNode *back = interior->GetBack();
[551]	3031
[562]	3032	BspNodeGeometry *fGeom = new BspNodeGeometry();
	3033	BspNodeGeometry *bGeom = new BspNodeGeometry();
[463]	3034
[562]	3035	geom->SplitGeometry(*fGeom,
	3036	*bGeom,
	3037	interior->GetPlane(),
	3038	mBox,
[675]	3039	//0.0000001f);
[752]	3040	eps);
[551]	3041
[683]	3042	if (cf == Polygon3::BACK_SIDE)
[562]	3043	{
[683]	3044	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
	3045	DEL_PTR(fGeom);
[562]	3046	}
	3047	else
	3048	{
[683]	3049	if (cf == Polygon3::FRONT_SIDE)
[551]	3050	{
[683]	3051	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
	3052	DEL_PTR(bGeom);
[551]	3053	}
[482]	3054	else
[562]	3055	{ // random decision
	3056	nodeStack.push(bspNodePair(front, fGeom));
	3057	nodeStack.push(bspNodePair(back, bGeom));
[463]	3058	}
[551]	3059	}
[463]	3060	}
[562]	3061
[551]	3062	DEL_PTR(geom);
[463]	3063	}
[482]	3064
[463]	3065	return (int)neighbors.size();
	3066	}
	3067
[489]	3068
[600]	3069
[710]	3070	int VspBspTree::FindApproximateNeighbors(BspNode *n,
	3071	vector<BspLeaf *> &neighbors,
[600]	3072	const bool onlyUnmailed) const
	3073	{
	3074	stack<bspNodePair> nodeStack;
	3075
	3076	BspNodeGeometry nodeGeom;
	3077	ConstructGeometry(n, nodeGeom);
	3078
[752]	3079	float eps = 0.01f;
[600]	3080	// split planes from the root to this node
	3081	// needed to verify that we found neighbor leaf
	3082	// TODO: really needed?
	3083	vector<Plane3> halfSpaces;
	3084	ExtractHalfSpaces(n, halfSpaces);
	3085
	3086
	3087	BspNodeGeometry *rgeom = new BspNodeGeometry();
	3088	ConstructGeometry(mRoot, *rgeom);
	3089
	3090	nodeStack.push(bspNodePair(mRoot, rgeom));
	3091
	3092	while (!nodeStack.empty())
	3093	{
	3094	BspNode *node = nodeStack.top().first;
	3095	BspNodeGeometry *geom = nodeStack.top().second;
	3096
	3097	nodeStack.pop();
	3098
	3099	if (node->IsLeaf())
	3100	{
	3101	// test if this leaf is in valid view space
	3102	if (node->TreeValid() &&
	3103	(node != n) &&
	3104	(!onlyUnmailed \|\| !node->Mailed()))
	3105	{
	3106	bool isAdjacent = true;
	3107
	3108	// neighbor was found
	3109	if (isAdjacent)
	3110	{
	3111	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
	3112	}
	3113	}
	3114	}
	3115	else
	3116	{
	3117	BspInterior interior = dynamic_cast<BspInterior >(node);
	3118
[678]	3119	const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
[600]	3120	interior->GetPlane(),
[752]	3121	eps);
[600]	3122
	3123	BspNode *front = interior->GetFront();
	3124	BspNode *back = interior->GetBack();
	3125
	3126	BspNodeGeometry *fGeom = new BspNodeGeometry();
	3127	BspNodeGeometry *bGeom = new BspNodeGeometry();
	3128
	3129	geom->SplitGeometry(*fGeom,
	3130	*bGeom,
	3131	interior->GetPlane(),
	3132	mBox,
[675]	3133	//0.0000001f);
[752]	3134	eps);
[600]	3135
[683]	3136	if (cf == Polygon3::BACK_SIDE)
[600]	3137	{
[683]	3138	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
	3139	DEL_PTR(fGeom);
[710]	3140	}
[600]	3141	else
	3142	{
[683]	3143	if (cf == Polygon3::FRONT_SIDE)
[600]	3144	{
[683]	3145	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
	3146	DEL_PTR(bGeom);
[600]	3147	}
	3148	else
	3149	{ // random decision
	3150	nodeStack.push(bspNodePair(front, fGeom));
	3151	nodeStack.push(bspNodePair(back, bGeom));
	3152	}
	3153	}
	3154	}
	3155
	3156	DEL_PTR(geom);
	3157	}
	3158
	3159	return (int)neighbors.size();
	3160	}
	3161
	3162
	3163
[463]	3164	BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
	3165	{
	3166	stack<BspNode *> nodeStack;
	3167	nodeStack.push(mRoot);
[482]	3168
[463]	3169	int mask = rand();
[482]	3170
	3171	while (!nodeStack.empty())
[463]	3172	{
	3173	BspNode *node = nodeStack.top();
	3174	nodeStack.pop();
[482]	3175
	3176	if (node->IsLeaf())
[463]	3177	{
	3178	return dynamic_cast<BspLeaf *>(node);
[482]	3179	}
	3180	else
[463]	3181	{
	3182	BspInterior interior = dynamic_cast<BspInterior >(node);
	3183	BspNode *next;
[503]	3184	BspNodeGeometry geom;
[482]	3185
[463]	3186	// todo: not very efficient: constructs full cell everytime
[498]	3187	ConstructGeometry(interior, geom);
[463]	3188
[503]	3189	const int cf =
[678]	3190	Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
[463]	3191
	3192	if (cf == Polygon3::BACK_SIDE)
	3193	next = interior->GetFront();
	3194	else
	3195	if (cf == Polygon3::FRONT_SIDE)
	3196	next = interior->GetFront();
[482]	3197	else
[463]	3198	{
	3199	// random decision
	3200	if (mask & 1)
	3201	next = interior->GetBack();
	3202	else
	3203	next = interior->GetFront();
	3204	mask = mask >> 1;
	3205	}
	3206
	3207	nodeStack.push(next);
	3208	}
	3209	}
[482]	3210
[463]	3211	return NULL;
	3212	}
	3213
[694]	3214
[463]	3215	BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
	3216	{
	3217	stack<BspNode *> nodeStack;
[482]	3218
[463]	3219	nodeStack.push(mRoot);
	3220
	3221	int mask = rand();
[482]	3222
	3223	while (!nodeStack.empty())
[463]	3224	{
	3225	BspNode *node = nodeStack.top();
	3226	nodeStack.pop();
[482]	3227
	3228	if (node->IsLeaf())
[463]	3229	{
	3230	if ( (!onlyUnmailed \|\| !node->Mailed()) )
	3231	return dynamic_cast<BspLeaf *>(node);
	3232	}
[482]	3233	else
[463]	3234	{
	3235	BspInterior interior = dynamic_cast<BspInterior >(node);
	3236
	3237	// random decision
	3238	if (mask & 1)
	3239	nodeStack.push(interior->GetBack());
	3240	else
	3241	nodeStack.push(interior->GetFront());
	3242
	3243	mask = mask >> 1;
	3244	}
	3245	}
[482]	3246
[463]	3247	return NULL;
	3248	}
	3249
[694]	3250
[463]	3251	int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
	3252	{
	3253	int pvsSize = 0;
	3254
	3255	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	3256
	3257	Intersectable::NewMail();
	3258
	3259	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	3260	{
	3261	VssRay ray = (rit).mRay;
[482]	3262
[1020]	3263	if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
[463]	3264	{
	3265	if (!ray->mOriginObject->Mailed())
	3266	{
	3267	ray->mOriginObject->Mail();
	3268	++ pvsSize;
	3269	}
	3270	}
[1020]	3271
[463]	3272	if (ray->mTerminationObject)
	3273	{
	3274	if (!ray->mTerminationObject->Mailed())
	3275	{
	3276	ray->mTerminationObject->Mail();
	3277	++ pvsSize;
	3278	}
	3279	}
	3280	}
	3281
	3282	return pvsSize;
	3283	}
	3284
[694]	3285
[463]	3286	float VspBspTree::GetEpsilon() const
	3287	{
	3288	return mEpsilon;
	3289	}
	3290
	3291
	3292	int VspBspTree::SplitPolygons(const Plane3 &plane,
[482]	3293	PolygonContainer &polys,
	3294	PolygonContainer &frontPolys,
	3295	PolygonContainer &backPolys,
[463]	3296	PolygonContainer &coincident) const
	3297	{
	3298	int splits = 0;
	3299
[574]	3300	PolygonContainer::const_iterator it, it_end = polys.end();
	3301
	3302	for (it = polys.begin(); it != polys.end(); ++ it)
[463]	3303	{
[574]	3304	Polygon3 poly = it;
[463]	3305
	3306	// classify polygon
	3307	const int cf = poly->ClassifyPlane(plane, mEpsilon);
	3308
	3309	switch (cf)
	3310	{
	3311	case Polygon3::COINCIDENT:
	3312	coincident.push_back(poly);
[482]	3313	break;
	3314	case Polygon3::FRONT_SIDE:
[463]	3315	frontPolys.push_back(poly);
	3316	break;
	3317	case Polygon3::BACK_SIDE:
	3318	backPolys.push_back(poly);
	3319	break;
	3320	case Polygon3::SPLIT:
	3321	backPolys.push_back(poly);
	3322	frontPolys.push_back(poly);
	3323	++ splits;
	3324	break;
	3325	default:
	3326	Debug << "SHOULD NEVER COME HERE\n";
	3327	break;
	3328	}
	3329	}
	3330
	3331	return splits;
	3332	}
[466]	3333
	3334
[469]	3335	int VspBspTree::CastLineSegment(const Vector3 &origin,
	3336	const Vector3 &termination,
[882]	3337	ViewCellContainer &viewcells)
[466]	3338	{
[469]	3339	int hits = 0;
[719]	3340	stack<BspRayTraversalData> tStack;
[482]	3341
[469]	3342	float mint = 0.0f, maxt = 1.0f;
[482]	3343
[469]	3344	Intersectable::NewMail();
[600]	3345	ViewCell::NewMail();
[482]	3346
[469]	3347	Vector3 entp = origin;
	3348	Vector3 extp = termination;
[482]	3349
[469]	3350	BspNode *node = mRoot;
	3351	BspNode *farChild = NULL;
[482]	3352
[485]	3353	float t;
[752]	3354	const float thresh = 1e-6f; // matt: change this to adjustable value
[694]	3355
[482]	3356	while (1)
[469]	3357	{
[482]	3358	if (!node->IsLeaf())
[469]	3359	{
	3360	BspInterior in = dynamic_cast<BspInterior >(node);
[482]	3361
[469]	3362	Plane3 splitPlane = in->GetPlane();
[485]	3363
[666]	3364	const int entSide = splitPlane.Side(entp, thresh);
	3365	const int extSide = splitPlane.Side(extp, thresh);
[482]	3366
[485]	3367	if (entSide < 0)
[469]	3368	{
[666]	3369	node = in->GetBack();
	3370
	3371	// plane does not split ray => no far child
	3372	if (extSide <= 0)
	3373	continue;
	3374
	3375	farChild = in->GetFront(); // plane splits ray
[485]	3376	}
	3377	else if (entSide > 0)
[469]	3378	{
[666]	3379	node = in->GetFront();
[482]	3380
[666]	3381	if (extSide >= 0) // plane does not split ray => no far child
	3382	continue;
[482]	3383
	3384	farChild = in->GetBack(); // plane splits ray
[469]	3385	}
[694]	3386	else // one of the ray end points is on the plane
[1020]	3387	{
	3388	// NOTE: what to do if ray is coincident with plane?
[485]	3389	if (extSide < 0)
	3390	node = in->GetBack();
[694]	3391	else //if (extSide > 0)
[485]	3392	node = in->GetFront();
[694]	3393	//else break; // coincident => count no intersections
	3394
[485]	3395	continue; // no far child
[469]	3396	}
[482]	3397
[469]	3398	// push data for far child
[719]	3399	tStack.push(BspRayTraversalData(farChild, extp));
[482]	3400
[469]	3401	// find intersection of ray segment with plane
	3402	extp = splitPlane.FindIntersection(origin, extp, &t);
[485]	3403	}
	3404	else
[469]	3405	{
	3406	// reached leaf => intersection with view cell
	3407	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
[666]	3408	ViewCell *viewCell;
	3409
[1020]	3410	// question: always contribute to leaf or to currently active view cell?
[708]	3411	if (0)
	3412	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	3413	else
	3414	viewCell = leaf->GetViewCell();
[482]	3415
[590]	3416	if (!viewCell->Mailed())
[469]	3417	{
[590]	3418	viewcells.push_back(viewCell);
	3419	viewCell->Mail();
[469]	3420	++ hits;
	3421	}
[482]	3422
[469]	3423	//-- fetch the next far child from the stack
[719]	3424	if (tStack.empty())
[469]	3425	break;
[482]	3426
[469]	3427	entp = extp;
[485]	3428
[719]	3429	const BspRayTraversalData &s = tStack.top();
[482]	3430
[469]	3431	node = s.mNode;
	3432	extp = s.mExitPoint;
[482]	3433
[719]	3434	tStack.pop();
[469]	3435	}
[466]	3436	}
[487]	3437
[469]	3438	return hits;
[466]	3439	}
[478]	3440
[576]	3441
	3442
	3443
[485]	3444	int VspBspTree::TreeDistance(BspNode n1, BspNode n2) const
[482]	3445	{
	3446	std::deque<BspNode *> path1;
	3447	BspNode *p1 = n1;
[479]	3448
[482]	3449	// create path from node 1 to root
	3450	while (p1)
	3451	{
	3452	if (p1 == n2) // second node on path
	3453	return (int)path1.size();
	3454
	3455	path1.push_front(p1);
	3456	p1 = p1->GetParent();
	3457	}
	3458
	3459	int depth = n2->GetDepth();
	3460	int d = depth;
	3461
	3462	BspNode *p2 = n2;
	3463
	3464	// compare with same depth
	3465	while (1)
	3466	{
	3467	if ((d < (int)path1.size()) && (p2 == path1[d]))
	3468	return (depth - d) + ((int)path1.size() - 1 - d);
	3469
	3470	-- d;
	3471	p2 = p2->GetParent();
	3472	}
	3473
	3474	return 0; // never come here
	3475	}
	3476
[580]	3477
[501]	3478	BspNode VspBspTree::CollapseTree(BspNode node, int &collapsed)
[479]	3479	{
[590]	3480	// TODO
[728]	3481	#if HAS_TO_BE_REDONE
[495]	3482	if (node->IsLeaf())
[479]	3483	return node;
	3484
[492]	3485	BspInterior interior = dynamic_cast<BspInterior >(node);
	3486
[501]	3487	BspNode *front = CollapseTree(interior->GetFront(), collapsed);
	3488	BspNode *back = CollapseTree(interior->GetBack(), collapsed);
[492]	3489
[479]	3490	if (front->IsLeaf() && back->IsLeaf())
	3491	{
	3492	BspLeaf frontLeaf = dynamic_cast<BspLeaf >(front);
	3493	BspLeaf backLeaf = dynamic_cast<BspLeaf >(back);
	3494
	3495	//-- collapse tree
	3496	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
	3497	{
	3498	BspViewCell *vc = frontLeaf->GetViewCell();
	3499
	3500	BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
[489]	3501	leaf->SetTreeValid(frontLeaf->TreeValid());
[482]	3502
[479]	3503	// replace a link from node's parent
	3504	if (leaf->GetParent())
	3505	leaf->GetParent()->ReplaceChildLink(node, leaf);
[517]	3506	else
	3507	mRoot = leaf;
	3508
[501]	3509	++ collapsed;
[479]	3510	delete interior;
	3511
	3512	return leaf;
	3513	}
	3514	}
[590]	3515	#endif
[495]	3516	return node;
	3517	}
	3518
	3519
[501]	3520	int VspBspTree::CollapseTree()
[495]	3521	{
[501]	3522	int collapsed = 0;
[580]	3523	//TODO
[728]	3524	#if HAS_TO_BE_REDONE
[501]	3525	(void)CollapseTree(mRoot, collapsed);
[517]	3526
[485]	3527	// revalidate leaves
[517]	3528	RepairViewCellsLeafLists();
[580]	3529	#endif
[501]	3530	return collapsed;
[479]	3531	}
	3532
	3533
[517]	3534	void VspBspTree::RepairViewCellsLeafLists()
[492]	3535	{
[590]	3536	// TODO
[728]	3537	#if HAS_TO_BE_REDONE
[479]	3538	// list not valid anymore => clear
[492]	3539	stack<BspNode *> nodeStack;
	3540	nodeStack.push(mRoot);
	3541
	3542	ViewCell::NewMail();
	3543
	3544	while (!nodeStack.empty())
	3545	{
	3546	BspNode *node = nodeStack.top();
	3547	nodeStack.pop();
	3548
	3549	if (node->IsLeaf())
	3550	{
	3551	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	3552
	3553	BspViewCell *viewCell = leaf->GetViewCell();
[590]	3554
[492]	3555	if (!viewCell->Mailed())
	3556	{
	3557	viewCell->mLeaves.clear();
	3558	viewCell->Mail();
	3559	}
[580]	3560
[492]	3561	viewCell->mLeaves.push_back(leaf);
[590]	3562
[492]	3563	}
	3564	else
	3565	{
	3566	BspInterior interior = dynamic_cast<BspInterior >(node);
	3567
	3568	nodeStack.push(interior->GetFront());
	3569	nodeStack.push(interior->GetBack());
	3570	}
[479]	3571	}
[590]	3572	// TODO
	3573	#endif
[479]	3574	}
	3575
	3576
[532]	3577	int VspBspTree::CastBeam(Beam &beam)
	3578	{
	3579	stack<bspNodePair> nodeStack;
	3580	BspNodeGeometry *rgeom = new BspNodeGeometry();
	3581	ConstructGeometry(mRoot, *rgeom);
	3582
	3583	nodeStack.push(bspNodePair(mRoot, rgeom));
	3584
	3585	ViewCell::NewMail();
	3586
	3587	while (!nodeStack.empty())
	3588	{
	3589	BspNode *node = nodeStack.top().first;
	3590	BspNodeGeometry *geom = nodeStack.top().second;
	3591	nodeStack.pop();
	3592
	3593	AxisAlignedBox3 box;
[697]	3594	geom->GetBoundingBox(box);
[532]	3595
[535]	3596	const int side = beam.ComputeIntersection(box);
[532]	3597
	3598	switch (side)
	3599	{
	3600	case -1:
[547]	3601	CollectViewCells(node, true, beam.mViewCells, true);
[532]	3602	break;
	3603	case 0:
[535]	3604
[532]	3605	if (node->IsLeaf())
	3606	{
[535]	3607	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	3608
[532]	3609	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
[535]	3610	{
	3611	leaf->GetViewCell()->Mail();
[532]	3612	beam.mViewCells.push_back(leaf->GetViewCell());
[535]	3613	}
[532]	3614	}
	3615	else
	3616	{
	3617	BspInterior interior = dynamic_cast<BspInterior >(node);
[535]	3618
[538]	3619	BspNode *first = interior->GetFront();
	3620	BspNode *second = interior->GetBack();
[535]	3621
	3622	BspNodeGeometry *firstGeom = new BspNodeGeometry();
	3623	BspNodeGeometry *secondGeom = new BspNodeGeometry();
	3624
[538]	3625	geom->SplitGeometry(*firstGeom,
	3626	*secondGeom,
	3627	interior->GetPlane(),
	3628	mBox,
[675]	3629	//0.0000001f);
[538]	3630	mEpsilon);
[535]	3631
[532]	3632	// decide on the order of the nodes
	3633	if (DotProd(beam.mPlanes[0].mNormal,
	3634	interior->GetPlane().mNormal) > 0)
	3635	{
	3636	swap(first, second);
[535]	3637	swap(firstGeom, secondGeom);
[532]	3638	}
	3639
[535]	3640	nodeStack.push(bspNodePair(first, firstGeom));
	3641	nodeStack.push(bspNodePair(second, secondGeom));
[532]	3642	}
[535]	3643
[532]	3644	break;
[538]	3645	default:
[532]	3646	// default: cull
[538]	3647	break;
[532]	3648	}
[538]	3649
[532]	3650	DEL_PTR(geom);
[535]	3651
[532]	3652	}
	3653
[538]	3654	return (int)beam.mViewCells.size();
[532]	3655	}
	3656
	3657
[485]	3658	void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
[478]	3659	{
[485]	3660	mViewCellsManager = vcm;
	3661	}
	3662
	3663
[580]	3664	int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
	3665	vector<MergeCandidate> &candidates)
[485]	3666	{
[478]	3667	BspLeaf::NewMail();
[508]	3668
[478]	3669	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
	3670
[580]	3671	int numCandidates = 0;
[509]	3672
[478]	3673	// find merge candidates and push them into queue
	3674	for (it = leaves.begin(); it != it_end; ++ it)
	3675	{
	3676	BspLeaf leaf = it;
[485]	3677
	3678	// the same leaves must not be part of two merge candidates
	3679	leaf->Mail();
[650]	3680
[485]	3681	vector<BspLeaf *> neighbors;
[710]	3682
	3683	// appoximate neighbor search has slightl relaxed constraints
[694]	3684	if (1)
[650]	3685	FindNeighbors(leaf, neighbors, true);
	3686	else
	3687	FindApproximateNeighbors(leaf, neighbors, true);
[710]	3688
[485]	3689	vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
	3690
	3691	// TODO: test if at least one ray goes from one leaf to the other
	3692	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
[508]	3693	{
	3694	if ((*nit)->GetViewCell() != leaf->GetViewCell())
[509]	3695	{
[580]	3696	MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
[564]	3697
[1006]	3698	if (!leaf->GetViewCell()->GetPvs().Empty() \|\|
[710]	3699	!(*nit)->GetViewCell()->GetPvs().Empty() \|\|
[676]	3700	leaf->IsSibling(*nit))
	3701	{
	3702	candidates.push_back(mc);
	3703	}
	3704
[580]	3705	++ numCandidates;
	3706	if ((numCandidates % 1000) == 0)
[566]	3707	{
[580]	3708	cout << "collected " << numCandidates << " merge candidates" << endl;
[566]	3709	}
[509]	3710	}
[485]	3711	}
	3712	}
	3713
[580]	3714	Debug << "merge queue: " << (int)candidates.size() << endl;
	3715	Debug << "leaves in queue: " << numCandidates << endl;
	3716
[508]	3717
[485]	3718	return (int)leaves.size();
	3719	}
	3720
	3721
[580]	3722	int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays,
	3723	vector<MergeCandidate> &candidates)
[485]	3724	{
[547]	3725	ViewCell::NewMail();
[503]	3726	long startTime = GetTime();
[574]	3727
[485]	3728	map<BspLeaf , vector<BspLeaf> > neighborMap;
[574]	3729	ViewCellContainer::const_iterator iit;
[485]	3730
[503]	3731	int numLeaves = 0;
[485]	3732
	3733	BspLeaf::NewMail();
	3734
[574]	3735	for (int i = 0; i < (int)rays.size(); ++ i)
[485]	3736	{
[574]	3737	VssRay *ray = rays[i];
[547]	3738
[485]	3739	// traverse leaves stored in the rays and compare and
	3740	// merge consecutive leaves (i.e., the neighbors in the tree)
[574]	3741	if (ray->mViewCells.size() < 2)
[485]	3742	continue;
[580]	3743	//TODO viewcellhierarchy
[574]	3744	iit = ray->mViewCells.begin();
	3745	BspViewCell bspVc = dynamic_cast<BspViewCell >(*(iit ++));
[580]	3746	BspLeaf *leaf = bspVc->mLeaf;
[485]	3747
	3748	// traverse intersections
[489]	3749	// consecutive leaves are neighbors => add them to queue
[574]	3750	for (; iit != ray->mViewCells.end(); ++ iit)
[485]	3751	{
[489]	3752	// next pair
	3753	BspLeaf *prevLeaf = leaf;
[574]	3754	bspVc = dynamic_cast<BspViewCell >(iit);
[580]	3755	leaf = bspVc->mLeaf;
[489]	3756
[508]	3757	// view space not valid or same view cell
	3758	if (!leaf->TreeValid() \|\| !prevLeaf->TreeValid() \|\|
	3759	(leaf->GetViewCell() == prevLeaf->GetViewCell()))
[489]	3760	continue;
	3761
[580]	3762	vector<BspLeaf *> &neighbors = neighborMap[leaf];
[485]	3763
	3764	bool found = false;
[478]	3765
[485]	3766	// both leaves inserted in queue already =>
	3767	// look if double pair already exists
	3768	if (leaf->Mailed() && prevLeaf->Mailed())
[478]	3769	{
[485]	3770	vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
	3771
	3772	for (it = neighbors.begin(); !found && (it != it_end); ++ it)
	3773	if (*it == prevLeaf)
	3774	found = true; // already in queue
	3775	}
[547]	3776
[485]	3777	if (!found)
	3778	{
[564]	3779	// this pair is not in map yet
[485]	3780	// => insert into the neighbor map and the queue
	3781	neighbors.push_back(prevLeaf);
	3782	neighborMap[prevLeaf].push_back(leaf);
[478]	3783
[485]	3784	leaf->Mail();
	3785	prevLeaf->Mail();
[547]	3786
[580]	3787	MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
	3788
	3789	candidates.push_back(mc);
[564]	3790
[580]	3791	if (((int)candidates.size() % 1000) == 0)
[564]	3792	{
[580]	3793	cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
[564]	3794	}
[478]	3795	}
[485]	3796	}
	3797	}
[564]	3798
[485]	3799	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
[580]	3800	Debug << "merge queue: " << (int)candidates.size() << endl;
[503]	3801	Debug << "leaves in queue: " << numLeaves << endl;
[485]	3802
[580]	3803
[503]	3804	//-- collect the leaves which haven't been found by ray casting
[542]	3805	if (0)
	3806	{
[551]	3807	cout << "finding additional merge candidates using geometry" << endl;
[542]	3808	vector<BspLeaf *> leaves;
[547]	3809	CollectLeaves(leaves, true);
[542]	3810	Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
[580]	3811	CollectMergeCandidates(leaves, candidates);
[542]	3812	}
[503]	3813
	3814	return numLeaves;
[485]	3815	}
	3816
	3817
	3818
	3819
[879]	3820	ViewCell *VspBspTree::GetViewCell(const Vector3 &point, const bool active)
[492]	3821	{
[879]	3822	if (mRoot == NULL)
	3823	return NULL;
	3824
	3825	stack<BspNode *> nodeStack;
	3826	nodeStack.push(mRoot);
[492]	3827
[882]	3828	ViewCellLeaf *viewcell = NULL;
[492]	3829
[879]	3830	while (!nodeStack.empty())
	3831	{
	3832	BspNode *node = nodeStack.top();
	3833	nodeStack.pop();
[492]	3834
[879]	3835	if (node->IsLeaf())
	3836	{
	3837	viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
	3838	break;
	3839	}
	3840	else
	3841	{
	3842	BspInterior interior = dynamic_cast<BspInterior >(node);
	3843
	3844	// random decision
	3845	if (interior->GetPlane().Side(point) < 0)
	3846	nodeStack.push(interior->GetBack());
	3847	else
	3848	nodeStack.push(interior->GetFront());
	3849	}
[492]	3850	}
	3851
[879]	3852	if (active)
	3853	return mViewCellsTree->GetActiveViewCell(viewcell);
	3854	else
	3855	return viewcell;
[492]	3856	}
	3857
	3858
[487]	3859	bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
	3860	{
	3861	BspNode *node = mRoot;
[485]	3862
[487]	3863	while (1)
	3864	{
	3865	// early exit
	3866	if (node->TreeValid())
	3867	return true;
	3868
	3869	if (node->IsLeaf())
	3870	return false;
	3871
	3872	BspInterior in = dynamic_cast<BspInterior >(node);
[490]	3873
	3874	if (in->GetPlane().Side(viewPoint) <= 0)
[487]	3875	{
	3876	node = in->GetBack();
	3877	}
	3878	else
	3879	{
	3880	node = in->GetFront();
	3881	}
	3882	}
	3883
	3884	// should never come here
	3885	return false;
	3886	}
	3887
	3888
	3889	void VspBspTree::PropagateUpValidity(BspNode *node)
	3890	{
[574]	3891	const bool isValid = node->TreeValid();
	3892
	3893	// propagative up invalid flag until only invalid nodes exist over this node
	3894	if (!isValid)
[487]	3895	{
[574]	3896	while (!node->IsRoot() && node->GetParent()->TreeValid())
	3897	{
	3898	node = node->GetParent();
	3899	node->SetTreeValid(false);
	3900	}
[487]	3901	}
[574]	3902	else
	3903	{
	3904	// propagative up valid flag until one of the subtrees is invalid
	3905	while (!node->IsRoot() && !node->TreeValid())
	3906	{
	3907	node = node->GetParent();
	3908	BspInterior interior = dynamic_cast<BspInterior >(node);
	3909
	3910	// the parent is valid iff both leaves are valid
	3911	node->SetTreeValid(interior->GetBack()->TreeValid() &&
	3912	interior->GetFront()->TreeValid());
	3913	}
	3914	}
[487]	3915	}
	3916
[971]	3917	#if ZIPPED_VIEWCELLS
	3918	bool VspBspTree::Export(ogzstream &stream)
	3919	#else
[508]	3920	bool VspBspTree::Export(ofstream &stream)
[971]	3921	#endif
[503]	3922	{
[508]	3923	ExportNode(mRoot, stream);
[487]	3924
[503]	3925	return true;
	3926	}
	3927
[971]	3928	#if ZIPPED_VIEWCELLS
	3929	void VspBspTree::ExportNode(BspNode *node, ogzstream &stream)
	3930	#else
[508]	3931	void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
[971]	3932	#endif
[508]	3933	{
	3934	if (node->IsLeaf())
[503]	3935	{
[508]	3936	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
[590]	3937	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	3938
[508]	3939	int id = -1;
[590]	3940	if (viewCell != mOutOfBoundsCell)
	3941	id = viewCell->GetId();
[503]	3942
[508]	3943	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
[503]	3944	}
[508]	3945	else
[503]	3946	{
[508]	3947	BspInterior interior = dynamic_cast<BspInterior >(node);
	3948
	3949	Plane3 plane = interior->GetPlane();
	3950	stream << "<Interior plane=\"" << plane.mNormal.x << " "
	3951	<< plane.mNormal.y << " " << plane.mNormal.z << " "
	3952	<< plane.mD << "\">" << endl;
[503]	3953
[508]	3954	ExportNode(interior->GetBack(), stream);
	3955	ExportNode(interior->GetFront(), stream);
[503]	3956
[508]	3957	stream << "</Interior>" << endl;
[503]	3958	}
	3959	}
[860]	3960
	3961	}

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

Download in other formats: