Context Navigation

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

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

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

Download in other formats: