Context Navigation

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

Revision 1603, 99.7 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: