Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp @ 393

Revision 393, 61.4 KB checked in by mattausch, 19 years ago (diff)

Rev	Line
[375]	1	#include "Plane3.h"
	2	#include "ViewCellBsp.h"
	3	#include "Mesh.h"
	4	#include "common.h"
	5	#include "ViewCell.h"
	6	#include "Environment.h"
	7	#include "Polygon3.h"
	8	#include "Ray.h"
	9	#include "AxisAlignedBox3.h"
	10	#include <stack>
	11	#include <time.h>
	12	#include <iomanip>
	13	#include "Exporter.h"
	14	#include "Plane3.h"
	15
	16	int BspTree::sTermMaxPolygons = 10;
[390]	17	int BspTree::sTermMinPvs = 20;
[375]	18	int BspTree::sTermMaxDepth = 20;
[379]	19	int BspTree::sMaxPolyCandidates = 10;
	20	int BspTree::sMaxRayCandidates = 10;
[375]	21	int BspTree::sSplitPlaneStrategy = BALANCED_POLYS;
	22	int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
	23	int BspTree::sTermMaxPolysForAxisAligned = 50;
	24	int BspTree::sTermMaxObjectsForAxisAligned = 50;
	25	int BspTree::sTermMaxRaysForAxisAligned = -1;
	26	int BspTree::sTermMaxRays = -1;
	27	int BspTree::sMinPvsDif = 10;
[378]	28	int BspTree::sMinPvs = 10;
	29	int BspTree::sMaxPvs = 500;
[375]	30
	31	float BspTree::sCt_div_ci = 1.0f;
	32	float BspTree::sSplitBorder = 1.0f;
	33	float BspTree::sMaxCostRatio = 0.9f;
	34
	35	//-- factors for bsp tree split plane heuristics
	36
	37	float BspTree::sLeastSplitsFactor = 1.0f;
	38	float BspTree::sBalancedPolysFactor = 1.0f;
	39	float BspTree::sBalancedViewCellsFactor = 1.0f;
	40
	41	// NOTE: very important criterium for 2.5d scenes
	42	float BspTree::sVerticalSplitsFactor = 1.0f;
	43	float BspTree::sLargestPolyAreaFactor = 1.0f;
	44	float BspTree::sBlockedRaysFactor = 1.0f;
	45	float BspTree::sLeastRaySplitsFactor = 1.0f;
	46	float BspTree::sBalancedRaysFactor = 1.0f;
	47	float BspTree::sPvsFactor = 1.0f;
	48
	49	int BspNode::mailID = 1;
	50
	51	/** Evaluates split plane classification with respect to the plane's
	52	contribution for a minimum number splits in the tree.
	53	*/
	54	float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
	55	/** Evaluates split plane classification with respect to the plane's
	56	contribution for a balanced tree.
	57	*/
	58	float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
	59
	60	/** Evaluates split plane classification with respect to the plane's
	61	contribution for a minimum number of ray splits.
	62	*/
	63	float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
	64	/** Evaluates split plane classification with respect to the plane's
	65	contribution for balanced rays.
	66	*/
	67	float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
	68
	69	/****************************************************************/
	70	/* class BspNode implementation */
	71	/****************************************************************/
	72
	73	BspNode::BspNode():
[390]	74	mParent(NULL)
[375]	75	{}
	76
	77	BspNode::BspNode(BspInterior *parent):
[390]	78	mParent(parent)
[375]	79	{}
	80
	81
	82	bool BspNode::IsRoot() const
	83	{
	84	return mParent == NULL;
	85	}
	86
	87	BspInterior *BspNode::GetParent()
	88	{
	89	return mParent;
	90	}
	91
	92	void BspNode::SetParent(BspInterior *parent)
	93	{
	94	mParent = parent;
	95	}
	96
	97	/****************************************************************/
	98	/* class BspInterior implementation */
	99	/****************************************************************/
	100
	101
	102	BspInterior::BspInterior(const Plane3 &plane):
	103	mPlane(plane), mFront(NULL), mBack(NULL)
	104	{}
	105
	106	bool BspInterior::IsLeaf() const
	107	{
	108	return false;
	109	}
	110
	111	BspNode *BspInterior::GetBack()
	112	{
	113	return mBack;
	114	}
	115
	116	BspNode *BspInterior::GetFront()
	117	{
	118	return mFront;
	119	}
	120
	121	Plane3 *BspInterior::GetPlane()
	122	{
	123	return &mPlane;
	124	}
	125
	126	void BspInterior::ReplaceChildLink(BspNode oldChild, BspNode newChild)
	127	{
	128	if (mBack == oldChild)
	129	mBack = newChild;
	130	else
	131	mFront = newChild;
	132	}
	133
	134	void BspInterior::SetupChildLinks(BspNode b, BspNode f)
	135	{
	136	mBack = b;
	137	mFront = f;
	138	}
	139
	140	int BspInterior::SplitPolygons(PolygonContainer &polys,
	141	PolygonContainer &frontPolys,
	142	PolygonContainer &backPolys,
[390]	143	PolygonContainer &coincident)
[375]	144	{
	145	Polygon3 *splitPoly = NULL;
	146
	147	int splits = 0;
	148
	149	#ifdef _Debug
	150	Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
	151	#endif
	152	while (!polys.empty())
	153	{
	154	Polygon3 *poly = polys.back();
	155	polys.pop_back();
	156
	157	//Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
	158
	159	// classify polygon
	160	const int cf = poly->ClassifyPlane(mPlane);
	161
	162	Polygon3 *front_piece = NULL;
	163	Polygon3 *back_piece = NULL;
	164
	165	VertexContainer splitVertices;
	166
	167	switch (cf)
	168	{
	169	case Polygon3::COINCIDENT:
	170	coincident.push_back(poly);
	171	break;
	172	case Polygon3::FRONT_SIDE:
	173	frontPolys.push_back(poly);
	174	break;
	175	case Polygon3::BACK_SIDE:
	176	backPolys.push_back(poly);
	177	break;
	178	case Polygon3::SPLIT:
	179	front_piece = new Polygon3(poly->mParent);
	180	back_piece = new Polygon3(poly->mParent);
	181
	182	//-- split polygon into front and back part
	183	poly->Split(mPlane,
	184	*front_piece,
	185	*back_piece,
	186	splitVertices);
	187
	188	++ splits; // increase number of splits
	189
	190	//-- inherit rays from parent polygon for blocked ray criterium
	191	poly->InheritRays(front_piece, back_piece);
	192	//Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
	193
	194	// check if polygons still valid
	195	if (front_piece->Valid())
	196	frontPolys.push_back(front_piece);
	197	else
	198	DEL_PTR(front_piece);
	199
	200	if (back_piece->Valid())
	201	backPolys.push_back(back_piece);
	202	else
	203	DEL_PTR(back_piece);
	204
	205	#ifdef _DEBUG
	206	Debug << "split " << poly << endl << front_piece << endl << *back_piece << endl;
	207	#endif
[390]	208	DEL_PTR(poly);
[375]	209	break;
	210	default:
	211	Debug << "SHOULD NEVER COME HERE\n";
	212	break;
	213	}
	214	}
	215
	216	return splits;
	217	}
	218
	219	/****************************************************************/
	220	/* class BspLeaf implementation */
	221	/****************************************************************/
	222	BspLeaf::BspLeaf(): mViewCell(NULL)
	223	{
	224	}
	225
	226	BspLeaf::BspLeaf(BspViewCell *viewCell):
	227	mViewCell(viewCell)
	228	{
	229	}
	230
	231	BspLeaf::BspLeaf(BspInterior *parent):
	232	BspNode(parent), mViewCell(NULL)
	233	{}
	234
	235	BspLeaf::BspLeaf(BspInterior parent, BspViewCell viewCell):
	236	BspNode(parent), mViewCell(viewCell)
	237	{
	238	}
	239
	240	BspViewCell *BspLeaf::GetViewCell() const
	241	{
	242	return mViewCell;
	243	}
	244
	245	void BspLeaf::SetViewCell(BspViewCell *viewCell)
	246	{
	247	mViewCell = viewCell;
	248	}
	249
	250	bool BspLeaf::IsLeaf() const
	251	{
	252	return true;
	253	}
	254
[392]	255	void BspLeaf::AddToPvs(const BoundedRayContainer &rays,
	256	int &sampleContributions,
	257	int &contributingSamples)
[375]	258	{
	259	sampleContributions = 0;
	260	contributingSamples = 0;
	261
	262	BoundedRayContainer::const_iterator it, it_end = rays.end();
	263
	264	// add contributions from samples to the PVS
	265	for (it = rays.begin(); it != it_end; ++ it)
	266	{
	267	int contribution = 0;
	268	Ray ray = (it)->mRay;
	269
	270	if (!ray->intersections.empty())
	271	{
[392]	272	//contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
[375]	273	}
	274
[392]	275	//contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
[375]	276
	277	if (contribution > 0)
	278	{
	279	sampleContributions += contribution;
	280	++ contributingSamples;
	281	}
	282
	283	// warning: not ordered
	284	ray->bspIntersections.push_back(Ray::BspIntersection((*it)->mMinT, this));
	285	}
	286	}
	287
	288
	289	/****************************************************************/
	290	/* class BspTree implementation */
	291	/****************************************************************/
	292
[392]	293	BspTree::BspTree(BspViewCell *viewCell):
[375]	294	mRootCell(viewCell), mRoot(NULL), mGenerateViewCells(false),
	295	mStorePiercingRays(true)
	296	{
	297	Randomize(); // initialise random generator for heuristics
	298	}
	299
	300	const BspTreeStatistics &BspTree::GetStatistics() const
	301	{
	302	return mStat;
	303	}
	304
	305	void BspViewCellsStatistics::Print(ostream &app) const
	306	{
	307	app << "===== BspViewCells statistics ===============\n";
	308
	309	app << setprecision(4);
	310
[378]	311	app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
	312
[375]	313	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
	314
	315	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
	316
	317	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
	318
	319	app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
	320
	321	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
	322
	323	app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;
	324
	325	app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;
	326
	327	app << "===== END OF BspViewCells statistics ==========\n";
	328	}
	329
	330	void BspTreeStatistics::Print(ostream &app) const
	331	{
	332	app << "===== BspTree statistics ===============\n";
	333
	334	app << setprecision(4);
	335
	336	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
	337
	338	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	339
	340	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	341
	342	app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
	343
	344	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
	345	maxDepthNodes * 100 / (double)Leaves() << endl;
	346
	347	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
	348
	349	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
	350
	351	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
	352
	353	app << "#N_INPUT_POLYGONS (number of input polygons )\n" << polys << endl;
	354
	355	//app << "#N_PVS: " << pvs << endl;
	356
	357	app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
	358	(polys + splits) / (double)polys << endl;
	359
	360	app << "===== END OF BspTree statistics ==========\n";
	361	}
	362
	363
	364	BspTree::~BspTree()
	365	{
	366	std::stack<BspNode *> tStack;
	367
	368	tStack.push(mRoot);
	369
	370	while (!tStack.empty())
	371	{
	372	BspNode *node = tStack.top();
	373
	374	tStack.pop();
	375
	376	if (!node->IsLeaf())
	377	{
	378	BspInterior interior = dynamic_cast<BspInterior >(node);
	379
	380	// push the children on the stack (there are always two children)
	381	tStack.push(interior->GetBack());
	382	tStack.push(interior->GetFront());
	383	}
	384
	385	DEL_PTR(node);
	386	}
	387	}
	388
	389	void BspTree::InsertViewCell(ViewCell *viewCell)
	390	{
	391	PolygonContainer *polys = new PolygonContainer();
	392
	393	// extract polygons that guide the split process
	394	mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
	395	mBox.Include(viewCell->GetBox()); // add to BSP aabb
	396
	397	InsertPolygons(polys);
	398	}
	399
	400	void BspTree::InsertPolygons(PolygonContainer *polys)
	401	{
	402	std::stack<BspTraversalData> tStack;
	403
	404	// traverse existing tree or create new tree
	405	if (!mRoot)
	406	mRoot = new BspLeaf();
	407
[390]	408	tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,
	409	mBox.SurfaceArea(), new BspNodeGeometry()));
[375]	410
	411	while (!tStack.empty())
	412	{
	413	// filter polygons donw the tree
	414	BspTraversalData tData = tStack.top();
	415	tStack.pop();
	416
	417	if (!tData.mNode->IsLeaf())
	418	{
	419	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
	420
	421	//-- filter view cell polygons down the tree until a leaf is reached
	422	if (!tData.mPolygons->empty())
	423	{
	424	PolygonContainer *frontPolys = new PolygonContainer();
	425	PolygonContainer *backPolys = new PolygonContainer();
	426	PolygonContainer coincident;
	427
	428	int splits = 0;
	429
	430	// split viewcell polygons with respect to split plane
[390]	431	splits += interior->SplitPolygons(*tData.mPolygons,
[375]	432	*frontPolys,
	433	*backPolys,
[390]	434	coincident);
[375]	435
	436	// extract view cells associated with the split polygons
	437	ViewCell *frontViewCell = mRootCell;
	438	ViewCell *backViewCell = mRootCell;
[390]	439
	440	BspTraversalData frontData(interior->GetFront(),
	441	frontPolys,
	442	tData.mDepth + 1,
	443	mRootCell,
	444	tData.mRays,
	445	tData.mPvs,
	446	mBox.SurfaceArea(),
	447	new BspNodeGeometry());
	448
	449	BspTraversalData backData(interior->GetBack(),
	450	backPolys,
	451	tData.mDepth + 1,
	452	mRootCell,
	453	tData.mRays,
	454	tData.mPvs,
	455	mBox.SurfaceArea(),
	456	new BspNodeGeometry());
	457
[375]	458	if (!mGenerateViewCells)
	459	{
[390]	460	ExtractViewCells(frontData,
	461	backData,
	462	coincident,
	463	interior->mPlane);
[375]	464	}
	465
	466	// don't need coincident polygons anymore
[390]	467	CLEAR_CONTAINER(coincident);
[375]	468
	469	mStat.splits += splits;
	470
	471	// push the children on the stack
[390]	472	tStack.push(frontData);
	473	tStack.push(backData);
[375]	474	}
	475
	476	// cleanup
	477	DEL_PTR(tData.mPolygons);
	478	}
	479	else
	480	{
	481	// reached leaf => subdivide current viewcell
	482	BspNode *subRoot = Subdivide(tStack, tData);
	483	}
	484	}
	485	}
	486
	487	int BspTree::AddMeshToPolygons(Mesh mesh, PolygonContainer &polys, MeshInstance parent)
	488	{
	489	FaceContainer::const_iterator fi;
	490
	491	// copy the face data to polygons
	492	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
	493	{
	494	Polygon3 poly = new Polygon3((fi), mesh);
	495
	496	if (poly->Valid())
	497	{
	498	poly->mParent = parent; // set parent intersectable
	499	polys.push_back(poly);
	500	}
	501	else
	502	DEL_PTR(poly);
	503	}
	504	return (int)mesh->mFaces.size();
	505	}
	506
	507	int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
	508	PolygonContainer &polys,
	509	int maxObjects)
	510	{
	511	int limit = (maxObjects > 0) ?
	512	Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
	513
	514	int polysSize = 0;
	515
	516	for (int i = 0; i < limit; ++ i)
	517	{
	518	if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
	519	{
	520	mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
	521	polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
	522	}
	523	}
	524
	525	return polysSize;
	526	}
	527
	528	int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
	529	{
	530	int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
	531
	532	for (int i = 0; i < limit; ++i)
	533	{
	534	Intersectable object = objects[i];//it;
	535	Mesh *mesh = NULL;
	536
	537	switch (object->Type()) // extract the meshes
	538	{
	539	case Intersectable::MESH_INSTANCE:
	540	mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
	541	break;
	542	case Intersectable::VIEW_CELL:
	543	mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
	544	break;
	545	// TODO: handle transformed mesh instances
	546	default:
	547	Debug << "intersectable type not supported" << endl;
	548	break;
	549	}
	550
	551	if (mesh) // copy the mesh data to polygons
	552	{
	553	mBox.Include(object->GetBox()); // add to BSP tree aabb
	554	AddMeshToPolygons(mesh, polys, mRootCell);
	555	}
	556	}
	557
	558	return (int)polys.size();
	559	}
	560
	561	void BspTree::Construct(const ViewCellContainer &viewCells)
	562	{
	563	mStat.nodes = 1;
	564	mBox.Initialize(); // initialise bsp tree bounding box
	565
	566	// copy view cell meshes into one big polygon soup
	567	PolygonContainer *polys = new PolygonContainer();
	568	mStat.polys = AddToPolygonSoup(viewCells, *polys);
	569
	570	// construct tree from the view cell polygons
	571	Construct(polys, new BoundedRayContainer());
	572	}
	573
	574
	575	void BspTree::Construct(const ObjectContainer &objects)
	576	{
	577	mStat.nodes = 1;
	578	mBox.Initialize(); // initialise bsp tree bounding box
	579
	580	PolygonContainer *polys = new PolygonContainer();
	581
	582	// copy mesh instance polygons into one big polygon soup
	583	mStat.polys = AddToPolygonSoup(objects, *polys);
	584
	585	// construct tree from polygon soup
	586	Construct(polys, new BoundedRayContainer());
	587	}
	588
	589	void BspTree::Construct(const RayContainer &sampleRays)
	590	{
	591	mStat.nodes = 1;
	592	mBox.Initialize(); // initialise BSP tree bounding box
	593
	594	PolygonContainer *polys = new PolygonContainer();
	595	BoundedRayContainer *rays = new BoundedRayContainer();
	596
	597	RayContainer::const_iterator rit, rit_end = sampleRays.end();
	598
	599	long startTime = GetTime();
	600
	601	Debug << "** Extracting polygons from rays **\n";
	602
	603	std::map<Face , Polygon3 > facePolyMap;
	604
	605	//-- extract polygons intersected by the rays
	606	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	607	{
	608	Ray ray = rit;
	609
	610	// get ray-face intersection. Store polygon representing the rays together
	611	// with rays intersecting the face.
	612	if (!ray->intersections.empty())
	613	{
	614	MeshInstance obj = dynamic_cast<MeshInstance >(ray->intersections[0].mObject);
	615	Face *face = obj->GetMesh()->mFaces[ray->intersections[0].mFace];
	616
	617	std::map<Face , Polygon3 >::iterator it = facePolyMap.find(face);
	618
	619	if (it != facePolyMap.end())
	620	{
	621	//store rays if needed for heuristics
	622	if (sSplitPlaneStrategy & BLOCKED_RAYS)
	623	(*it).second->mPiercingRays.push_back(ray);
	624	}
	625	else
	626	{ //store rays if needed for heuristics
	627	Polygon3 *poly = new Polygon3(face, obj->GetMesh());
	628	poly->mParent = obj;
	629	polys->push_back(poly);
	630
	631	if (sSplitPlaneStrategy & BLOCKED_RAYS)
	632	poly->mPiercingRays.push_back(ray);
	633
	634	facePolyMap[face] = poly;
	635	}
	636	}
	637	}
	638
	639	facePolyMap.clear();
	640
	641	// compue bounding box
	642	Polygon3::IncludeInBox(*polys, mBox);
	643
	644	//-- store rays
	645	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	646	{
	647	Ray ray = rit;
	648	ray->SetId(-1); // reset id
	649
	650	float minT, maxT;
	651	if (BoundRay(*ray, minT, maxT))
	652	rays->push_back(new BoundedRay(ray, minT, maxT));
	653	}
	654
	655	mStat.polys = (int)polys->size();
	656
	657	Debug << "** Finished polygon extraction **" << endl;
[380]	658	Debug << (int)polys->size() << " polys extracted from " << (int)sampleRays.size() << " rays" << endl;
[375]	659	Debug << "extraction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
	660
	661	Construct(polys, rays);
	662	}
	663
	664	void BspTree::Construct(PolygonContainer polys, BoundedRayContainer rays)
	665	{
	666	std::stack<BspTraversalData> tStack;
	667
	668	mRoot = new BspLeaf();
	669
[390]	670	BspNodeGeometry *cell = new BspNodeGeometry();
	671	ConstructGeometry(mRoot, *cell);
	672
	673	BspTraversalData tData(mRoot, polys, 0, mRootCell, rays,
	674	ComputePvsSize(*rays), cell->GetArea(), cell);
	675
[375]	676	tStack.push(tData);
	677
	678	long startTime = GetTime();
	679	cout << "** Contructing bsp tree **\n";
	680
	681	while (!tStack.empty())
	682	{
	683	tData = tStack.top();
	684	tStack.pop();
	685
	686	// subdivide leaf node
	687	BspNode *subRoot = Subdivide(tStack, tData);
	688	}
	689
	690	cout << "** Finished tree construction **\n";
	691	Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
	692	}
	693
	694
	695	BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
	696	{
	697	//-- terminate traversal
	698	if (((int)tData.mPolygons->size() <= sTermMaxPolygons) \|\|
[390]	699	((int)tData.mRays->size() <= sTermMaxRays) \|\|
	700	((int)tData.mPvs <= sTermMinPvs) \|\|
	701	(tData.mDepth >= sTermMaxDepth))
[375]	702
	703	{
	704	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
	705
[392]	706	BspViewCell *viewCell;
	707
[375]	708	// generate new view cell for each leaf
	709	if (mGenerateViewCells)
	710	{
[392]	711	viewCell = dynamic_cast<BspViewCell *>(ViewCell::Generate());
[375]	712	}
	713	else
	714	{
	715	// add view cell to leaf
[392]	716	viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
[375]	717	}
	718
[392]	719	leaf->SetViewCell(viewCell);
	720	viewCell->mBspLeaves.push_back(leaf);
	721
	722	//-- add pvs
	723	if (viewCell != mRootCell)
	724	{
	725	int conSamp = 0, sampCon = 0;
	726	leaf->AddToPvs(*tData.mRays, conSamp, sampCon);
	727
	728	mStat.contributingSamples += conSamp;
	729	mStat.sampleContributions += sampCon;
	730	}
	731
[375]	732	EvaluateLeafStats(tData);
	733
	734	//-- clean up
	735
[390]	736	// discard polygons
	737	CLEAR_CONTAINER(*tData.mPolygons);
[375]	738	// discard rays
	739	CLEAR_CONTAINER(*tData.mRays);
[390]	740
	741	DEL_PTR(tData.mPolygons);
[375]	742	DEL_PTR(tData.mRays);
[390]	743	DEL_PTR(tData.mCell);
	744
[375]	745	return leaf;
	746	}
	747
	748	//-- continue subdivision
	749
	750	PolygonContainer coincident;
	751
	752	PolygonContainer *frontPolys = new PolygonContainer();
	753	PolygonContainer *backPolys = new PolygonContainer();
	754
	755	BoundedRayContainer *frontRays = new BoundedRayContainer();
	756	BoundedRayContainer *backRays = new BoundedRayContainer();
	757
[390]	758	BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
	759	new BoundedRayContainer(), 0, NULL, 0);
	760	BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,
	761	new BoundedRayContainer(), 0, NULL, 0);
	762
[375]	763	// create new interior node and two leaf nodes
[390]	764	BspInterior *interior = SubdivideNode(tData,
	765	tFrontData,
	766	tBackData,
	767	coincident);
[375]	768
	769	#ifdef _DEBUG
	770	if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
	771	{ for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
	772	Debug << (it) << " " << (it)->GetArea() << " " << (*it)->mParent << endl ;
	773	Debug << endl;}
	774	#endif
	775
	776	// extract view cells from coincident polygons according to plane normal
	777	// only if front or back polygons are empty
	778	if (!mGenerateViewCells)
	779	{
[390]	780	ExtractViewCells(tFrontData,
	781	tBackData,
[375]	782	coincident,
[390]	783	interior->mPlane);
	784
[375]	785	}
	786
[390]	787	// don't need coincident polygons anymory
	788	CLEAR_CONTAINER(coincident);
	789
[375]	790	// push the children on the stack
[390]	791	tStack.push(tFrontData);
	792	tStack.push(tBackData);
[375]	793
	794	// cleanup
	795	DEL_PTR(tData.mNode);
	796	DEL_PTR(tData.mPolygons);
	797	DEL_PTR(tData.mRays);
[390]	798	DEL_PTR(tData.mCell);
[375]	799
	800	return interior;
	801	}
	802
[390]	803	void BspTree::ExtractViewCells(BspTraversalData &frontData,
	804	BspTraversalData &backData,
[375]	805	const PolygonContainer &coincident,
[390]	806	const Plane3 splitPlane) const
[375]	807	{
[390]	808	// if not empty, tree is further subdivided => don't have to find view cell
	809	bool foundFront = !frontData.mPolygons->empty();
	810	bool foundBack = !frontData.mPolygons->empty();
[375]	811
	812	PolygonContainer::const_iterator it =
	813	coincident.begin(), it_end = coincident.end();
	814
	815	//-- find first view cells in front and back leafs
	816	for (; !(foundFront && foundBack) && (it != it_end); ++ it)
	817	{
	818	if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
	819	{
[390]	820	backData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
[375]	821	foundBack = true;
	822	}
	823	else
	824	{
[390]	825	frontData.mViewCell = dynamic_cast<ViewCell >((it)->mParent);
[375]	826	foundFront = true;
	827	}
	828	}
	829	}
	830
[390]	831	BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
	832	BspTraversalData &frontData,
	833	BspTraversalData &backData,
	834	PolygonContainer &coincident)
[375]	835	{
	836	mStat.nodes += 2;
	837
[390]	838	BspLeaf leaf = dynamic_cast<BspLeaf >(tData.mNode);
[375]	839	// select subdivision plane
	840	BspInterior *interior =
[390]	841	new BspInterior(SelectPlane(leaf, tData, frontData, backData));
[375]	842
	843	#ifdef _DEBUG
	844	Debug << interior << endl;
	845	#endif
	846
	847	// subdivide rays into front and back rays
[390]	848	SplitRays(interior->mPlane, tData.mRays, frontData.mRays, *backData.mRays);
[375]	849
	850	// subdivide polygons with plane
[390]	851	mStat.splits += interior->SplitPolygons(*tData.mPolygons,
	852	*frontData.mPolygons,
	853	*backData.mPolygons,
	854	coincident);
[375]	855
	856	BspInterior *parent = leaf->GetParent();
	857
	858	// replace a link from node's parent
	859	if (!leaf->IsRoot())
	860	{
	861	parent->ReplaceChildLink(leaf, interior);
	862	interior->SetParent(parent);
	863	}
	864	else // new root
	865	{
	866	mRoot = interior;
	867	}
	868
	869	// and setup child links
	870	interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
	871
[390]	872	frontData.mNode = interior->mFront;
	873	backData.mNode = interior->mBack;
	874
[375]	875	return interior;
	876	}
	877
	878	void BspTree::SortSplitCandidates(const PolygonContainer &polys,
	879	const int axis,
	880	vector<SortableEntry> &splitCandidates) const
	881	{
	882	splitCandidates.clear();
	883
	884	int requestedSize = 2 * (int)polys.size();
	885	// creates a sorted split candidates array
	886	splitCandidates.reserve(requestedSize);
	887
	888	PolygonContainer::const_iterator it, it_end = polys.end();
	889
	890	AxisAlignedBox3 box;
	891
	892	// insert all queries
	893	for(it = polys.begin(); it != it_end; ++ it)
	894	{
	895	box.Initialize();
	896	box.Include((it));
	897
	898	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
	899	splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
	900	}
	901
	902	stable_sort(splitCandidates.begin(), splitCandidates.end());
	903	}
	904
	905
	906	float BspTree::BestCostRatio(const PolygonContainer &polys,
	907	const AxisAlignedBox3 &box,
	908	const int axis,
	909	float &position,
	910	int &objectsBack,
	911	int &objectsFront) const
	912	{
	913	vector<SortableEntry> splitCandidates;
	914
	915	SortSplitCandidates(polys, axis, splitCandidates);
	916
	917	// go through the lists, count the number of objects left and right
	918	// and evaluate the following cost funcion:
	919	// C = ct_div_ci + (ol + or)/queries
	920
	921	int objectsLeft = 0, objectsRight = (int)polys.size();
	922
	923	float minBox = box.Min(axis);
	924	float maxBox = box.Max(axis);
	925	float boxArea = box.SurfaceArea();
	926
	927	float minBand = minBox + sSplitBorder * (maxBox - minBox);
	928	float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
	929
	930	float minSum = 1e20f;
	931	vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
	932
	933	for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)
	934	{
	935	switch ((*ci).type)
	936	{
	937	case SortableEntry::POLY_MIN:
	938	++ objectsLeft;
	939	break;
	940	case SortableEntry::POLY_MAX:
	941	-- objectsRight;
	942	break;
	943	default:
	944	break;
	945	}
	946
	947	if ((ci).value > minBand && (ci).value < maxBand)
	948	{
	949	AxisAlignedBox3 lbox = box;
	950	AxisAlignedBox3 rbox = box;
	951	lbox.SetMax(axis, (*ci).value);
	952	rbox.SetMin(axis, (*ci).value);
	953
	954	float sum = objectsLeft * lbox.SurfaceArea() +
	955	objectsRight * rbox.SurfaceArea();
	956
	957	if (sum < minSum)
	958	{
	959	minSum = sum;
	960	position = (*ci).value;
	961
	962	objectsBack = objectsLeft;
	963	objectsFront = objectsRight;
	964	}
	965	}
	966	}
	967
	968	float oldCost = (float)polys.size();
	969	float newCost = sCt_div_ci + minSum / boxArea;
	970	float ratio = newCost / oldCost;
	971
	972
	973	#if 0
	974	Debug << "====================" << endl;
	975	Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
	976	<< "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
	977	#endif
	978	return ratio;
	979	}
	980
	981	bool BspTree::SelectAxisAlignedPlane(Plane3 &plane,
	982	const PolygonContainer &polys) const
	983	{
	984	AxisAlignedBox3 box;
	985	box.Initialize();
	986
	987	// create bounding box of region
	988	Polygon3::IncludeInBox(polys, box);
	989
	990	int objectsBack = 0, objectsFront = 0;
	991	int axis = 0;
	992	float costRatio = MAX_FLOAT;
	993	Vector3 position;
	994
	995	//-- area subdivision
	996	for (int i = 0; i < 3; ++ i)
	997	{
	998	float p = 0;
	999	float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
	1000
	1001	if (r < costRatio)
	1002	{
	1003	costRatio = r;
	1004	axis = i;
	1005	position = p;
	1006	}
	1007	}
	1008
	1009	if (costRatio >= sMaxCostRatio)
	1010	return false;
	1011
	1012	Vector3 norm(0,0,0); norm[axis] = 1.0f;
	1013	plane = Plane3(norm, position);
	1014
	1015	return true;
	1016	}
	1017
	1018	Plane3 BspTree::SelectPlane(BspLeaf *leaf,
[390]	1019	BspTraversalData &data,
	1020	BspTraversalData &frontData,
	1021	BspTraversalData &backData)
[375]	1022	{
[390]	1023	if (data.mPolygons->empty() && data.mRays->empty())
[375]	1024	{
	1025	Debug << "Warning: No autopartition polygon candidate available\n";
	1026
	1027	// return axis aligned split
	1028	AxisAlignedBox3 box;
	1029	box.Initialize();
	1030
	1031	// create bounding box of region
[390]	1032	Polygon3::IncludeInBox(*data.mPolygons, box);
[375]	1033
	1034	const int axis = box.Size().DrivingAxis();
	1035	const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
	1036
	1037	Vector3 norm(0,0,0); norm[axis] = 1.0f;
	1038	return Plane3(norm, position);
	1039	}
	1040
	1041	if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
[390]	1042	((int)data.mPolygons->size() > sTermMaxPolysForAxisAligned) &&
	1043	((int)data.mRays->size() > sTermMaxRaysForAxisAligned) &&
[375]	1044	((sTermMaxObjectsForAxisAligned < 0) \|\|
[390]	1045	(Polygon3::ParentObjectsSize(*data.mPolygons) > sTermMaxObjectsForAxisAligned)))
[375]	1046	{
	1047	Plane3 plane;
[390]	1048	if (SelectAxisAlignedPlane(plane, *data.mPolygons))
[375]	1049	return plane;
	1050	}
	1051
	1052	// simplest strategy: just take next polygon
	1053	if (sSplitPlaneStrategy & RANDOM_POLYGON)
	1054	{
[390]	1055	Polygon3 nextPoly = (data.mPolygons)[Random((int)data.mPolygons->size())];
	1056	return nextPoly->GetSupportingPlane();
[375]	1057	}
	1058
	1059	// use heuristics to find appropriate plane
[390]	1060	return SelectPlaneHeuristics(leaf, data, frontData, backData);
[375]	1061	}
	1062
[383]	1063	Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf,
[390]	1064	BspTraversalData &data,
	1065	BspTraversalData &frontData,
	1066	BspTraversalData &backData)
[375]	1067	{
	1068	float lowestCost = MAX_FLOAT;
[390]	1069	Plane3 bestPlane;
[375]	1070
[390]	1071	int limit = sMaxPolyCandidates > 0 ?
	1072	Min((int)data.mPolygons->size(), sMaxPolyCandidates) : (int)data.mPolygons->size();
[375]	1073
	1074	int candidateIdx = limit;
[379]	1075
[383]	1076	for (int i = 0; i < limit; ++ i)
[375]	1077	{
[390]	1078	candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
[383]	1079
[390]	1080	Polygon3 poly = (data.mPolygons)[candidateIdx];
[383]	1081	// evaluate current candidate
	1082	const float candidateCost =
[390]	1083	SplitPlaneCost(poly->GetSupportingPlane(), data, frontData, backData);
[375]	1084
[390]	1085	Debug << "cost: " << candidateCost << ", lowest: " << lowestCost << endl;
	1086
[375]	1087	if (candidateCost < lowestCost)
	1088	{
[390]	1089	bestPlane = poly->GetSupportingPlane();
[375]	1090	lowestCost = candidateCost;
	1091	}
[383]	1092	}
[379]	1093
[390]	1094	//limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();
	1095	const BoundedRayContainer *rays = data.mRays;
[379]	1096
[390]	1097	for (int i = 0; i < sMaxRayCandidates; ++ i)
[379]	1098	{
[390]	1099	Plane3 plane;
[379]	1100
[390]	1101	if (1)
[379]	1102	{
[390]	1103	Vector3 pt[3];
	1104	int idx[3];
	1105
	1106	for (int j = 0; j < 3; j ++)
	1107	{
	1108	idx[j] = Random((int)rays->size() * 2);
[383]	1109
[390]	1110	BoundedRay bRay = (rays)[idx[j]];
	1111	Ray *ray = bRay->mRay;
	1112
	1113	if (idx[j] < (int)rays->size())
	1114	pt[j] = ray->Extrap(bRay->mMinT);
	1115	else
	1116	{
	1117	idx[j] -= (int)rays->size();
	1118	pt[j] = ray->Extrap(bRay->mMaxT);
	1119	}
	1120	}
	1121
	1122	plane = Plane3(pt[0], pt[1], pt[2]);
[379]	1123	}
[390]	1124	else
	1125	{
	1126	candidateIdx = Random((int)rays->size());
	1127	BoundedRay bRay = (rays)[candidateIdx];
[379]	1128
[390]	1129	Ray *ray = bRay->mRay;
	1130
	1131	const Vector3 minPt = ray->Extrap(bRay->mMinT);
	1132	const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
[379]	1133
[390]	1134	const Vector3 pt = (maxPt + minPt) * 0.5;
	1135
	1136	const Vector3 normal = ray->GetDir();
	1137
	1138	plane = Plane3(normal, pt);
	1139	}
	1140
	1141	const float candidateCost =
	1142	SplitPlaneCost(plane, data, frontData, backData);
	1143
[379]	1144	if (candidateCost < lowestCost)
	1145	{
[390]	1146	Debug << "choose ray plane: " << lowestCost << endl;
	1147	bestPlane = plane;
[379]	1148
	1149	lowestCost = candidateCost;
	1150	}
[390]	1151	else
	1152	Debug << "ray cost: " << candidateCost << ", lowest: " << lowestCost << endl;
[375]	1153	}
[379]	1154
[375]	1155	//Debug << "Plane lowest cost: " << lowestCost << endl;
[390]	1156	return bestPlane;
[375]	1157	}
	1158
	1159	int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
	1160	{
	1161	const int candidateIdx = Random(currentIdx --);
	1162
	1163	// swap candidates to avoid testing same plane 2 times
	1164	std::swap(polys[currentIdx], polys[candidateIdx]);
	1165
	1166	return currentIdx;
	1167	//return Random((int)polys.size());
	1168	}
	1169
[384]	1170	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
[375]	1171	const PolygonContainer &polys) const
	1172	{
	1173	float val = 0;
	1174
	1175	float sumBalancedPolys = 0;
	1176	float sumSplits = 0;
	1177	float sumPolyArea = 0;
	1178	float sumBalancedViewCells = 0;
	1179	float sumBlockedRays = 0;
	1180	float totalBlockedRays = 0;
	1181	//float totalArea = 0;
	1182	int totalViewCells = 0;
	1183
	1184	// need three unique ids for each type of view cell
	1185	// for balanced view cells criterium
	1186	ViewCell::NewMail();
	1187	const int backId = ViewCell::sMailId;
	1188	ViewCell::NewMail();
	1189	const int frontId = ViewCell::sMailId;
	1190	ViewCell::NewMail();
	1191	const int frontAndBackId = ViewCell::sMailId;
	1192
	1193	PolygonContainer::const_iterator it, it_end = polys.end();
	1194
	1195	for (it = polys.begin(); it != it_end; ++ it)
	1196	{
	1197	const int classification = (*it)->ClassifyPlane(candidatePlane);
	1198
	1199	if (sSplitPlaneStrategy & BALANCED_POLYS)
	1200	sumBalancedPolys += sBalancedPolysTable[classification];
	1201
	1202	if (sSplitPlaneStrategy & LEAST_SPLITS)
	1203	sumSplits += sLeastPolySplitsTable[classification];
	1204
	1205	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
	1206	{
	1207	if (classification == Polygon3::COINCIDENT)
	1208	sumPolyArea += (*it)->GetArea();
	1209	//totalArea += area;
	1210	}
	1211
	1212	if (sSplitPlaneStrategy & BLOCKED_RAYS)
	1213	{
	1214	const float blockedRays = (float)(*it)->mPiercingRays.size();
	1215
	1216	if (classification == Polygon3::COINCIDENT)
	1217	sumBlockedRays += blockedRays;
	1218
	1219	totalBlockedRays += blockedRays;
	1220	}
	1221
	1222	// assign view cells to back or front according to classificaion
	1223	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
	1224	{
	1225	MeshInstance viewCell = (it)->mParent;
	1226
	1227	// assure that we only count a view cell
	1228	// once for the front and once for the back side of the plane
	1229	if (classification == Polygon3::FRONT_SIDE)
	1230	{
	1231	if ((viewCell->mMailbox != frontId) &&
	1232	(viewCell->mMailbox != frontAndBackId))
	1233	{
	1234	sumBalancedViewCells += 1.0;
	1235
	1236	if (viewCell->mMailbox != backId)
	1237	viewCell->mMailbox = frontId;
	1238	else
	1239	viewCell->mMailbox = frontAndBackId;
	1240
	1241	++ totalViewCells;
	1242	}
	1243	}
	1244	else if (classification == Polygon3::BACK_SIDE)
	1245	{
	1246	if ((viewCell->mMailbox != backId) &&
	1247	(viewCell->mMailbox != frontAndBackId))
	1248	{
	1249	sumBalancedViewCells -= 1.0;
	1250
	1251	if (viewCell->mMailbox != frontId)
	1252	viewCell->mMailbox = backId;
	1253	else
	1254	viewCell->mMailbox = frontAndBackId;
	1255
	1256	++ totalViewCells;
	1257	}
	1258	}
	1259	}
	1260	}
	1261
	1262	// all values should be approx. between 0 and 1 so they can be combined
	1263	// and scaled with the factors according to their importance
	1264	if (sSplitPlaneStrategy & BALANCED_POLYS)
	1265	val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
[384]	1266
[375]	1267	if (sSplitPlaneStrategy & LEAST_SPLITS)
	1268	val += sLeastSplitsFactor * sumSplits / (float)polys.size();
	1269
	1270	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
	1271	// HACK: polys.size should be total area so scaling is between 0 and 1
	1272	val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea;
	1273
	1274	if (sSplitPlaneStrategy & BLOCKED_RAYS)
	1275	if (totalBlockedRays != 0)
	1276	val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
	1277
	1278	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
	1279	if (totalViewCells != 0)
[384]	1280	val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / (float)totalViewCells;
[375]	1281
	1282	return val;
	1283	}
	1284
	1285	bool BspTree::BoundRay(const Ray &ray, float &minT, float &maxT) const
	1286	{
	1287	maxT = 1e6;
	1288	minT = 0;
	1289
	1290	// test with tree bounding box
	1291	if (!mBox.GetMinMaxT(ray, &minT, &maxT))
	1292	return false;
	1293
	1294	if (minT < 0) // start ray from origin
	1295	minT = 0;
	1296
	1297	// bound ray or line segment
	1298	if ((ray.GetType() == Ray::LOCAL_RAY) &&
	1299	!ray.intersections.empty() &&
	1300	(ray.intersections[0].mT <= maxT))
	1301	{
	1302	maxT = ray.intersections[0].mT;
	1303	}
	1304
	1305	return true;
	1306	}
	1307
[384]	1308	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
	1309	const BoundedRayContainer &rays,
[390]	1310	const int pvs,
	1311	const float area,
	1312	const BspNodeGeometry &cell,
	1313	BspTraversalData &frontData,
	1314	BspTraversalData &backData) const
[375]	1315	{
	1316	float val = 0;
	1317
	1318	float sumBalancedRays = 0;
	1319	float sumRaySplits = 0;
[379]	1320
[390]	1321	int backId = 0;
	1322	int frontId = 0;
	1323	int frontAndBackId = 0;
[375]	1324
[390]	1325	frontData.mPvs = 0;
	1326	backData.mPvs = 0;
	1327	frontData.mArea = 0;
	1328	backData.mArea = 0;
	1329
	1330	// probability that view point lies in child
	1331	float pOverall = 0;
	1332	float pFront = 0;
	1333	float pBack = 0;
	1334
	1335	if (sSplitPlaneStrategy & PVS)
	1336	{
	1337	// create three unique ids for pvs heuristics
	1338	Intersectable::NewMail(); backId = ViewCell::sMailId;
	1339	Intersectable::NewMail(); frontId = ViewCell::sMailId;
	1340	Intersectable::NewMail(); frontAndBackId = ViewCell::sMailId;
	1341
	1342	if (1) // use front and back cell areas to approximate volume
[392]	1343	{
[390]	1344	// construct child geometry with regard to the candidate split plane
	1345	frontData.mCell = cell.ConstructChild(*this, candidatePlane, true);
	1346	backData.mCell = cell.ConstructChild(*this, candidatePlane, false);
	1347
[392]	1348	pFront = frontData.mArea = frontData.mCell->GetArea();
	1349	pBack = backData.mArea = backData.mCell->GetArea();
[390]	1350
	1351	pOverall = area;
	1352	}
	1353	else
	1354	{
	1355	pOverall = (float)rays.size();
	1356	}
	1357	}
	1358
[375]	1359	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
	1360
	1361	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	1362	{
	1363	Ray ray = (rit)->mRay;
	1364	const float minT = (*rit)->mMinT;
	1365	const float maxT = (*rit)->mMaxT;
	1366
	1367	const int cf =
	1368	ray->ClassifyPlane(candidatePlane, minT, maxT);
	1369
	1370	if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
	1371	{
	1372	sumBalancedRays += sBalancedRaysTable[cf];
	1373	}
	1374
	1375	if (sSplitPlaneStrategy & BALANCED_RAYS)
	1376	{
	1377	sumRaySplits += sLeastRaySplitsTable[cf];
	1378	}
	1379
	1380	if (sSplitPlaneStrategy & PVS)
	1381	{
	1382	if (!ray->intersections.empty())
	1383	{
[379]	1384	// in case the ray intersects an objcrs
[375]	1385	// assure that we only count a object
	1386	// once for the front and once for the back side of the plane
[390]	1387	AddToPvs(*ray->intersections[0].mObject, frontData.mPvs, backData.mPvs,
	1388	cf, frontId, backId, frontAndBackId);
[379]	1389	}
[375]	1390
[379]	1391	// the source object in the origin of the ray
[390]	1392	AddToPvs(*ray->sourceObject.mObject, frontData.mPvs, backData.mPvs,
	1393	cf, frontId, backId, frontAndBackId);
[379]	1394
[390]	1395	// use #rays to approximate volume
[384]	1396	if (0)
	1397	{
	1398	if ((cf == Ray::BACK) \|\| (cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
[390]	1399	++ pFront;
[384]	1400	if ((cf == Ray::FRONT) \|\| (cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
[390]	1401	++ pBack;
[384]	1402	}
[375]	1403	}
	1404	}
	1405
[390]	1406	if ((sSplitPlaneStrategy & LEAST_RAY_SPLITS) && !rays.empty())
[375]	1407	val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
	1408
[390]	1409	if ((sSplitPlaneStrategy & BALANCED_RAYS) && !rays.empty())
[375]	1410	val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
	1411
[390]	1412	if ((sSplitPlaneStrategy & PVS) && area && pvs)
[392]	1413	val += sPvsFactor * (frontData.mPvs * pFront + (backData.mPvs * pBack)) /
	1414	(pOverall * (float)pvs * 2);
[375]	1415
[392]	1416	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
[390]	1417	<< " frontpvs: " << frontData.mPvs << " pFront: " << pFront
	1418	<< " backpvs: " << backData.mPvs << " pBack: " << pBack
	1419	<< " val " << val << endl;
	1420
[375]	1421	return val;
	1422	}
	1423
[384]	1424	void BspTree::AddToPvs(Intersectable &obj,
[390]	1425	int &frontPvs,
	1426	int &backPvs,
[384]	1427	const int cf,
	1428	const int frontId,
	1429	const int backId,
	1430	const int frontAndBackId) const
[375]	1431	{
[384]	1432	if (cf == Ray::COINCIDENT) //TODO: really belongs to no pvs?
[379]	1433	return;
[375]	1434
	1435	if (cf == Ray::FRONT)
	1436	{
	1437	if ((obj.mMailbox != frontId) &&
	1438	(obj.mMailbox != frontAndBackId))
[384]	1439	{
[390]	1440	++ frontPvs;
[375]	1441
[384]	1442	if (obj.mMailbox != backId)
	1443	obj.mMailbox = frontId;
	1444	else
	1445	obj.mMailbox = frontAndBackId;
	1446	}
[375]	1447	}
	1448	else if (cf == Ray::BACK)
	1449	{
	1450	if ((obj.mMailbox != backId) &&
	1451	(obj.mMailbox != frontAndBackId))
	1452	{
[390]	1453	++ backPvs;
[375]	1454
	1455	if (obj.mMailbox != frontId)
	1456	obj.mMailbox = backId;
	1457	else
	1458	obj.mMailbox = frontAndBackId;
	1459	}
	1460	}
[384]	1461	// object belongs to both pvs
[375]	1462	else if ((cf == Ray::FRONT_BACK) \|\| (cf == Ray::BACK_FRONT))
	1463	{
[384]	1464	if (obj.mMailbox != frontAndBackId)
[379]	1465	{
[384]	1466	if (obj.mMailbox != frontId)
[390]	1467	++ frontPvs;
[384]	1468	if (obj.mMailbox != backId)
[390]	1469	++ backPvs;
[384]	1470
	1471	obj.mMailbox = frontAndBackId;
[379]	1472	}
[375]	1473	}
	1474	}
	1475
[390]	1476	float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
	1477	BspTraversalData &data,
	1478	BspTraversalData &frontData,
	1479	BspTraversalData &backData) const
[375]	1480	{
	1481	float val = 0;
	1482
	1483	if (sSplitPlaneStrategy & VERTICAL_AXIS)
	1484	{
	1485	Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
	1486	// we put a penalty on the dot product between the "tiny" vertical axis
	1487	// and the split plane axis
	1488	val += sVerticalSplitsFactor *
	1489	fabs(DotProd(candidatePlane.mNormal, tinyAxis));
	1490	}
	1491
	1492	// the following criteria loop over all polygons to find the cost value
	1493	if ((sSplitPlaneStrategy & BALANCED_POLYS) \|\|
	1494	(sSplitPlaneStrategy & LEAST_SPLITS) \|\|
	1495	(sSplitPlaneStrategy & LARGEST_POLY_AREA) \|\|
	1496	(sSplitPlaneStrategy & BALANCED_VIEW_CELLS) \|\|
	1497	(sSplitPlaneStrategy & BLOCKED_RAYS))
	1498	{
[390]	1499	val += SplitPlaneCost(candidatePlane, *data.mPolygons);
[375]	1500	}
	1501
	1502	// the following criteria loop over all rays to find the cost value
	1503	if ((sSplitPlaneStrategy & BALANCED_RAYS) \|\|
	1504	(sSplitPlaneStrategy & LEAST_RAY_SPLITS) \|\|
	1505	(sSplitPlaneStrategy & PVS))
	1506	{
[390]	1507	val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs,
	1508	data.mArea, *data.mCell, frontData, backData);
[375]	1509	}
	1510
	1511	// return linear combination of the sums
	1512	return val;
	1513	}
	1514
	1515	void BspTree::ParseEnvironment()
	1516	{
	1517	//-- parse bsp cell tree construction method
	1518	char constructionMethodStr[60];
	1519
	1520	environment->GetStringValue("BspTree.Construction.input", constructionMethodStr);
	1521
	1522	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
	1523
	1524	if (strcmp(constructionMethodStr, "fromViewCells") == 0)
	1525	sConstructionMethod = FROM_INPUT_VIEW_CELLS;
	1526	else if (strcmp(constructionMethodStr, "fromSceneGeometry") == 0)
	1527	sConstructionMethod = FROM_SCENE_GEOMETRY;
	1528	else if (strcmp(constructionMethodStr, "fromRays") == 0)
	1529	sConstructionMethod = FROM_RAYS;
	1530	else
	1531	{
	1532	cerr << "Wrong construction method " << constructionMethodStr << endl;
	1533	exit(1);
	1534	}
	1535
	1536	Debug << "Construction method: " << constructionMethodStr << endl;
	1537
	1538	//-- termination criteria for autopartition
	1539	environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
[390]	1540	environment->GetIntValue("BspTree.Termination.minPvs", sTermMinPvs);
[375]	1541	environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
	1542	environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
	1543
	1544	//-- termination criteria for axis aligned split
	1545	environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
	1546	environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
	1547	environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",
	1548	sTermMaxPolysForAxisAligned);
	1549	environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",
	1550	sTermMaxRaysForAxisAligned);
	1551	environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",
	1552	sTermMaxObjectsForAxisAligned);
	1553	//-- partition criteria
[379]	1554	environment->GetIntValue("BspTree.maxPolyCandidates", sMaxPolyCandidates);
	1555	environment->GetIntValue("BspTree.maxRayCandidates", sMaxRayCandidates);
[375]	1556	environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
	1557	environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
	1558
	1559	environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
	1560	Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
	1561
[378]	1562	// post processing stuff
	1563	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", sMinPvsDif);
	1564	environment->GetIntValue("ViewCells.PostProcessing.minPvs", sMinPvs);
	1565	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", sMaxPvs);
[375]	1566
	1567	Debug << "BSP max depth: " << sTermMaxDepth << endl;
[390]	1568	Debug << "BSP min PVS: " << sTermMinPvs << endl;
[375]	1569	Debug << "BSP max polys: " << sTermMaxPolygons << endl;
[379]	1570	Debug << "BSP max rays: " << sTermMaxRays << endl;
	1571	Debug << "BSP max polygon candidates: " << sMaxPolyCandidates << endl;
	1572	Debug << "BSP max plane candidates: " << sMaxRayCandidates << endl;
	1573
[375]	1574	Debug << "Split plane strategy: ";
	1575	if (sSplitPlaneStrategy & RANDOM_POLYGON)
	1576	Debug << "random polygon ";
	1577	if (sSplitPlaneStrategy & AXIS_ALIGNED)
	1578	Debug << "axis aligned ";
	1579	if (sSplitPlaneStrategy & LEAST_SPLITS)
	1580	Debug << "least splits ";
	1581	if (sSplitPlaneStrategy & BALANCED_POLYS)
	1582	Debug << "balanced polygons ";
	1583	if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
	1584	Debug << "balanced view cells ";
	1585	if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
	1586	Debug << "largest polygon area ";
	1587	if (sSplitPlaneStrategy & VERTICAL_AXIS)
	1588	Debug << "vertical axis ";
	1589	if (sSplitPlaneStrategy & BLOCKED_RAYS)
	1590	Debug << "blocked rays ";
[379]	1591	if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
	1592	Debug << "least ray splits ";
	1593	if (sSplitPlaneStrategy & BALANCED_RAYS)
	1594	Debug << "balanced rays ";
[375]	1595	if (sSplitPlaneStrategy & PVS)
	1596	Debug << "pvs";
	1597	Debug << endl;
	1598	}
	1599
	1600	void BspTree::CollectLeaves(vector<BspLeaf *> &leaves) const
	1601	{
	1602	stack<BspNode *> nodeStack;
	1603	nodeStack.push(mRoot);
	1604
	1605	while (!nodeStack.empty())
	1606	{
	1607	BspNode *node = nodeStack.top();
	1608
	1609	nodeStack.pop();
	1610
	1611	if (node->IsLeaf())
	1612	{
	1613	BspLeaf leaf = (BspLeaf )node;
	1614	leaves.push_back(leaf);
	1615	}
	1616	else
	1617	{
	1618	BspInterior interior = dynamic_cast<BspInterior >(node);
	1619
	1620	nodeStack.push(interior->GetBack());
	1621	nodeStack.push(interior->GetFront());
	1622	}
	1623	}
	1624	}
	1625
	1626	AxisAlignedBox3 BspTree::GetBoundingBox() const
	1627	{
	1628	return mBox;
	1629	}
	1630
	1631	BspNode *BspTree::GetRoot() const
	1632	{
	1633	return mRoot;
	1634	}
	1635
	1636	void BspTree::EvaluateLeafStats(const BspTraversalData &data)
	1637	{
	1638	// the node became a leaf -> evaluate stats for leafs
	1639	BspLeaf leaf = dynamic_cast<BspLeaf >(data.mNode);
	1640
	1641	if (data.mDepth >= sTermMaxDepth)
	1642	++ mStat.maxDepthNodes;
	1643
	1644	// store maximal and minimal depth
	1645	if (data.mDepth > mStat.maxDepth)
	1646	mStat.maxDepth = data.mDepth;
	1647
	1648	if (data.mDepth < mStat.minDepth)
	1649	mStat.minDepth = data.mDepth;
	1650
[390]	1651	// store minimal and maximal pvs
	1652	/*if (data.mPvs > mStat.pvs)
	1653	mStat.pvs = data.mPvs;
	1654
	1655	if (data.mPvs < mStat.pvs)
	1656	mStat.pvs = data.mPvs;*/
	1657
[375]	1658	// accumulate depth to compute average
	1659	mStat.accumDepth += data.mDepth;
	1660
[380]	1661	//#ifdef _DEBUG
[375]	1662	Debug << "BSP stats: "
	1663	<< "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
[390]	1664	<< "PVS: " << data.mPvs << " (max: " << sTermMinPvs << "), "
[375]	1665	<< "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
[385]	1666	<< "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << "), "
	1667	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << endl;
[380]	1668	//#endif
[375]	1669	}
	1670
	1671	int BspTree::CastRay(Ray &ray)
	1672	{
	1673	int hits = 0;
	1674
	1675	stack<BspRayTraversalData> tStack;
	1676
	1677	float maxt, mint;
	1678
	1679	if (!BoundRay(ray, mint, maxt))
	1680	return 0;
	1681
	1682	Intersectable::NewMail();
	1683
	1684	Vector3 entp = ray.Extrap(mint);
	1685	Vector3 extp = ray.Extrap(maxt);
	1686
	1687	BspNode *node = mRoot;
	1688	BspNode *farChild = NULL;
	1689
	1690	while (1)
	1691	{
	1692	if (!node->IsLeaf())
	1693	{
	1694	BspInterior in = (BspInterior ) node;
	1695
	1696	Plane3 *splitPlane = in->GetPlane();
	1697
	1698	int entSide = splitPlane->Side(entp);
	1699	int extSide = splitPlane->Side(extp);
	1700
	1701	Vector3 intersection;
	1702
	1703	if (entSide < 0)
	1704	{
	1705	node = in->GetBack();
	1706
	1707	if(extSide <= 0) // plane does not split ray => no far child
	1708	continue;
	1709
	1710	farChild = in->GetFront(); // plane splits ray
	1711
	1712	} else if (entSide > 0)
	1713	{
	1714	node = in->GetFront();
	1715
	1716	if (extSide >= 0) // plane does not split ray => no far child
	1717	continue;
	1718
	1719	farChild = in->GetBack(); // plane splits ray
	1720	}
[389]	1721	else // ray and plane are coincident
	1722	// WHAT TO DO IN THIS CASE ?
[375]	1723	{
[389]	1724	break;
	1725	//node = in->GetFront();
	1726	//continue;
[375]	1727	}
	1728
	1729	// push data for far child
	1730	tStack.push(BspRayTraversalData(farChild, extp, maxt));
	1731
	1732	// find intersection of ray segment with plane
	1733	float t;
	1734	extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
	1735	maxt *= t;
	1736
	1737	} else // reached leaf => intersection with view cell
	1738	{
	1739	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	1740
	1741	if (!leaf->mViewCell->Mailed())
	1742	{
	1743	ray.bspIntersections.push_back(Ray::BspIntersection(maxt, leaf));
	1744	leaf->mViewCell->Mail();
	1745	++ hits;
	1746	}
	1747
	1748	//-- fetch the next far child from the stack
	1749	if (tStack.empty())
	1750	break;
	1751
	1752	entp = extp;
	1753	mint = maxt; // NOTE: need this?
	1754
	1755	if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
	1756	break;
	1757
	1758	BspRayTraversalData &s = tStack.top();
	1759
	1760	node = s.mNode;
	1761	extp = s.mExitPoint;
	1762	maxt = s.mMaxT;
	1763
	1764	tStack.pop();
	1765	}
	1766	}
	1767
	1768	return hits;
	1769	}
	1770
	1771	bool BspTree::Export(const string filename)
	1772	{
	1773	Exporter *exporter = Exporter::GetExporter(filename);
	1774
	1775	if (exporter)
	1776	{
	1777	exporter->ExportBspTree(*this);
	1778	return true;
	1779	}
	1780
	1781	return false;
	1782	}
	1783
	1784	void BspTree::CollectViewCells(ViewCellContainer &viewCells) const
	1785	{
	1786	stack<BspNode *> nodeStack;
	1787	nodeStack.push(mRoot);
	1788
	1789	ViewCell::NewMail();
	1790
	1791	while (!nodeStack.empty())
	1792	{
	1793	BspNode *node = nodeStack.top();
	1794	nodeStack.pop();
	1795
	1796	if (node->IsLeaf())
	1797	{
	1798	ViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
	1799
	1800	if (!viewCell->Mailed())
	1801	{
	1802	viewCell->Mail();
	1803	viewCells.push_back(viewCell);
	1804	}
	1805	}
	1806	else
	1807	{
	1808	BspInterior interior = dynamic_cast<BspInterior >(node);
	1809
	1810	nodeStack.push(interior->mFront);
	1811	nodeStack.push(interior->mBack);
	1812	}
	1813	}
	1814	}
	1815
	1816	void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
	1817	{
	1818	stat.Reset();
	1819
	1820	stack<BspNode *> nodeStack;
	1821	nodeStack.push(mRoot);
	1822
	1823	ViewCell::NewMail();
	1824
	1825	// exclude root cell
	1826	mRootCell->Mail();
	1827
	1828	while (!nodeStack.empty())
	1829	{
	1830	BspNode *node = nodeStack.top();
	1831	nodeStack.pop();
	1832
	1833	if (node->IsLeaf())
	1834	{
	1835	++ stat.bspLeaves;
	1836
	1837	BspViewCell viewCell = dynamic_cast<BspLeaf >(node)->mViewCell;
	1838
	1839	if (!viewCell->Mailed())
	1840	{
	1841	viewCell->Mail();
	1842
	1843	++ stat.viewCells;
	1844	int pvsSize = viewCell->GetPvs().GetSize();
	1845
	1846	stat.pvs += pvsSize;
	1847
	1848	if (pvsSize < 2)
	1849	++ stat.emptyPvs;
	1850
	1851	if (pvsSize > stat.maxPvs)
	1852	stat.maxPvs = pvsSize;
	1853
	1854	if (pvsSize < stat.minPvs)
	1855	stat.minPvs = pvsSize;
	1856
	1857	if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
	1858	stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();
	1859	}
	1860	}
	1861	else
	1862	{
	1863	BspInterior interior = dynamic_cast<BspInterior >(node);
	1864
	1865	nodeStack.push(interior->mFront);
	1866	nodeStack.push(interior->mBack);
	1867	}
	1868	}
	1869	}
	1870
	1871	bool BspTree::MergeViewCells(BspLeaf front, BspLeaf back) const
	1872	{
	1873	BspViewCell *viewCell =
	1874	dynamic_cast<BspViewCell >(ViewCell::Merge(front->mViewCell, *back->mViewCell));
	1875
	1876	if (!viewCell)
	1877	return false;
	1878
	1879	// change view cells of all leaves associated with the
	1880	// previous view cells
	1881
	1882	BspViewCell *fVc = front->mViewCell;
	1883	BspViewCell *bVc = back->mViewCell;
	1884
	1885	vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
	1886	vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
	1887
	1888	vector<BspLeaf *>::const_iterator it;
	1889
	1890	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	1891	{
	1892	(*it)->SetViewCell(viewCell);
	1893	viewCell->mBspLeaves.push_back(*it);
	1894	}
	1895	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	1896	{
	1897	(*it)->SetViewCell(viewCell);
	1898	viewCell->mBspLeaves.push_back(*it);
	1899	}
	1900
	1901	DEL_PTR(fVc);
	1902	DEL_PTR(bVc);
	1903
	1904	return true;
	1905	}
	1906
	1907	bool BspTree::ShouldMerge(BspLeaf front, BspLeaf back) const
	1908	{
	1909	ViewCell *fvc = front->mViewCell;
	1910	ViewCell *bvc = back->mViewCell;
	1911
	1912	if ((fvc == mRootCell) \|\| (bvc == mRootCell) \|\| (fvc == bvc))
	1913	return false;
	1914
[378]	1915	int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
	1916
	1917	if (fvc->GetPvs().GetSize() + fdiff < sMaxPvs)
	1918	{
	1919	if ((fvc->GetPvs().GetSize() < sMinPvs) \|\|
	1920	(bvc->GetPvs().GetSize() < sMinPvs) \|\|
	1921	((fdiff < sMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < sMinPvsDif)))
	1922	{
	1923	return true;
	1924	}
	1925	}
[375]	1926
	1927	return false;
	1928	}
	1929
	1930	void BspTree::SetGenerateViewCells(int generateViewCells)
	1931	{
	1932	mGenerateViewCells = generateViewCells;
	1933	}
	1934
	1935	BspTreeStatistics &BspTree::GetStat()
	1936	{
	1937	return mStat;
	1938	}
	1939
	1940	int BspTree::SplitRays(const Plane3 &plane,
	1941	BoundedRayContainer &rays,
	1942	BoundedRayContainer &frontRays,
	1943	BoundedRayContainer &backRays)
	1944	{
	1945	int splits = 0;
	1946
	1947	while (!rays.empty())
	1948	{
	1949	BoundedRay *bRay = rays.back();
	1950	Ray *ray = bRay->mRay;
	1951	rays.pop_back();
	1952
	1953	const int cf =
	1954	ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
	1955
	1956	ray->SetId(cf);
	1957
	1958	switch (cf)
	1959	{
	1960	case Ray::COINCIDENT:
[390]	1961	//frontRays.push_back(bRay);
[391]	1962	DEL_PTR(bRay);
[375]	1963	break;
	1964	case Ray::BACK:
	1965	backRays.push_back(bRay);
	1966	break;
	1967	case Ray::FRONT:
	1968	frontRays.push_back(bRay);
	1969	break;
	1970	case Ray::FRONT_BACK:
	1971	{
	1972	// find intersection of ray segment with plane
	1973	const Vector3 extp = ray->Extrap(bRay->mMaxT);
	1974	const float t = plane.FindT(ray->GetLoc(), extp);
	1975
	1976	const float newT = t * bRay->mMaxT;
	1977
	1978	frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
	1979	backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
	1980
	1981	DEL_PTR(bRay);
	1982
	1983	++ splits;
	1984	}
	1985	break;
	1986	case Ray::BACK_FRONT:
	1987	{
	1988	// find intersection of ray segment with plane
	1989	const Vector3 extp = ray->Extrap(bRay->mMaxT);
	1990	const float t = plane.FindT(ray->GetLoc(), extp);
	1991	const float newT = t * bRay->mMaxT;
	1992
	1993	backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
	1994	frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
	1995
	1996	DEL_PTR(bRay);
	1997
	1998	++ splits;
	1999	}
	2000	break;
	2001	default:
	2002	Debug << "Should not come here" << endl;
	2003	break;
	2004	}
	2005	}
	2006
	2007	return splits;
	2008	}
	2009
	2010	void BspTree::ExtractSplitPlanes(BspNode *n,
[390]	2011	vector<Plane3> &planes,
[375]	2012	vector<bool> &sides) const
	2013	{
	2014	BspNode *lastNode;
	2015	do
	2016	{
	2017	lastNode = n;
	2018
	2019	// want to get planes defining geometry of this node => don't take
	2020	// split plane of node itself
	2021	n = n->GetParent();
	2022
	2023	if (n)
	2024	{
	2025	BspInterior interior = dynamic_cast<BspInterior >(n);
	2026
[390]	2027	planes.push_back(* dynamic_cast<BspInterior *>(interior)->GetPlane());
[375]	2028	sides.push_back(interior->mFront == lastNode);
	2029	}
	2030	}
	2031	while (n);
	2032	}
	2033
[390]	2034	void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
[375]	2035	{
[390]	2036	stack<BspNode *> tStack;
[375]	2037
[390]	2038	vector<Plane3> planes;
	2039	vector<bool> sides;
[375]	2040
[390]	2041	ExtractSplitPlanes(n, cell.mPlanes, cell.mSides);
[375]	2042
[390]	2043	PolygonContainer candidatePolys;
	2044
	2045	// bounded planes are added to the polygons
	2046	for (int i = 0; i < (int)cell.mPlanes.size(); ++ i)
	2047	{
	2048	candidatePolys.push_back(GetBoundingBox().CrossSection(cell.mPlanes[i]));
[375]	2049	}
[390]	2050
	2051	// add faces of bounding box (also could be faces of the cell)
	2052	for (int i = 0; i < 6; ++ i)
	2053	{
	2054	VertexContainer vertices;
[379]	2055
[390]	2056	for (int j = 0; j < 4; ++ j)
	2057	vertices.push_back(mBox.GetFace(i).mVertices[j]);
[375]	2058
[390]	2059	candidatePolys.push_back(new Polygon3(vertices));
[379]	2060	}
	2061
[390]	2062	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
[375]	2063	{
[390]	2064	bool inside = true;
	2065
	2066	// polygon is split by all other planes
	2067	for (int j = 0; (j < cell.mPlanes.size()) && inside; ++ j)
[375]	2068	{
[390]	2069	if (i == j) // same plane
	2070	continue;
[375]	2071
[390]	2072	VertexContainer splitPts;
	2073	Polygon3 frontPoly, backPoly;
	2074
	2075	const int cf = candidatePolys[i]->ClassifyPlane(cell.mPlanes[j]);
	2076
	2077	switch (cf)
	2078	{
	2079	case Polygon3::SPLIT:
	2080	frontPoly = new Polygon3();
	2081	backPoly = new Polygon3();
[379]	2082
[390]	2083	candidatePolys[i]->Split(cell.mPlanes[j], *frontPoly,
	2084	*backPoly, splitPts);
	2085	DEL_PTR(candidatePolys[i]);
[375]	2086
[390]	2087	if(sides[j] == true)
[379]	2088	{
[390]	2089	candidatePolys[i] = frontPoly;
[379]	2090	DEL_PTR(backPoly);
	2091	}
	2092	else
	2093	{
[390]	2094	candidatePolys[i] = backPoly;
[379]	2095	DEL_PTR(frontPoly);
	2096	}
[390]	2097
	2098	break;
	2099
	2100	case Polygon3::BACK_SIDE:
	2101	if (cell.mSides[j])
	2102	inside = false;
	2103	break;
	2104	case Polygon3::FRONT_SIDE:
	2105	if (!cell.mSides[j])
	2106	inside = false;
	2107	break;
	2108	case Polygon3::COINCIDENT:
	2109	break;
	2110	default:
	2111	break;
	2112	}
[375]	2113	}
[390]	2114
	2115	if (inside)
	2116	cell.mPolys.push_back(candidatePolys[i]);
	2117	else
	2118	DEL_PTR(candidatePolys[i]);
[375]	2119	}
	2120	}
	2121
	2122	void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
	2123	{
	2124	stack<BspNode *> tStack;
	2125
[390]	2126	vector<Plane3> planes;
[375]	2127	vector<bool> sides;
	2128
	2129	ExtractSplitPlanes(n, planes, sides);
	2130
	2131	PolygonContainer candidatePolys;
	2132
	2133	// bounded planes are added to the polygons
	2134	for (int i = 0; i < (int)planes.size(); ++ i)
	2135	{
[390]	2136	candidatePolys.push_back(GetBoundingBox().CrossSection(planes[i]));
[375]	2137	}
	2138
	2139	// add faces of bounding box (also could be faces of the cell)
	2140	for (int i = 0; i < 6; ++ i)
	2141	{
	2142	VertexContainer vertices;
	2143
	2144	for (int j = 0; j < 4; ++ j)
	2145	vertices.push_back(mBox.GetFace(i).mVertices[j]);
	2146
	2147	candidatePolys.push_back(new Polygon3(vertices));
	2148	}
	2149
	2150	for (int i = 0; i < (int)candidatePolys.size(); ++ i)
	2151	{
	2152	bool inside = true;
	2153
	2154	// polygon is split by all other planes
	2155	for (int j = 0; (j < planes.size()) && inside; ++ j)
	2156	{
	2157	if (i == j) // same plane
	2158	continue;
	2159
	2160	VertexContainer splitPts;
	2161	Polygon3 frontPoly, backPoly;
	2162
[390]	2163	const int cf = candidatePolys[i]->ClassifyPlane(planes[j]);
[375]	2164
	2165	switch (cf)
	2166	{
	2167	case Polygon3::SPLIT:
	2168	frontPoly = new Polygon3();
	2169	backPoly = new Polygon3();
	2170
[390]	2171	candidatePolys[i]->Split(planes[j], *frontPoly,
[375]	2172	*backPoly, splitPts);
	2173	DEL_PTR(candidatePolys[i]);
	2174
	2175	if(sides[j] == true)
	2176	{
	2177	candidatePolys[i] = frontPoly;
	2178	DEL_PTR(backPoly);
	2179	}
	2180	else
	2181	{
	2182	candidatePolys[i] = backPoly;
	2183	DEL_PTR(frontPoly);
	2184	}
[384]	2185
[375]	2186	break;
	2187
	2188	case Polygon3::BACK_SIDE:
	2189	if (sides[j])
	2190	inside = false;
	2191	break;
	2192	case Polygon3::FRONT_SIDE:
	2193	if (!sides[j])
	2194	inside = false;
	2195	break;
[384]	2196	case Polygon3::COINCIDENT:
	2197	break;
[375]	2198	default:
	2199	break;
	2200	}
	2201	}
	2202
	2203	if (inside)
	2204	cell.push_back(candidatePolys[i]);
	2205	else
	2206	DEL_PTR(candidatePolys[i]);
	2207	}
	2208	}
	2209
	2210	void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
	2211	{
	2212	vector<BspLeaf *> leaves = vc->mBspLeaves;
	2213
	2214	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
	2215
	2216	for (it = leaves.begin(); it != it_end; ++ it)
	2217	ConstructGeometry(*it, cell);
	2218	}
	2219
	2220	int BspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
	2221	const bool onlyUnmailed) const
	2222	{
	2223	PolygonContainer cell;
	2224
	2225	ConstructGeometry(n, cell);
	2226
	2227	stack<BspNode *> nodeStack;
	2228	nodeStack.push(mRoot);
	2229
	2230	// planes needed to verify that we found neighbor leaf.
[390]	2231	vector<Plane3> planes;
[375]	2232	vector<bool> sides;
	2233
	2234	ExtractSplitPlanes(n, planes, sides);
	2235
	2236	while (!nodeStack.empty())
	2237	{
	2238	BspNode *node = nodeStack.top();
	2239	nodeStack.pop();
	2240
	2241	if (node->IsLeaf())
	2242	{
	2243	if (node != n && (!onlyUnmailed \|\| !node->Mailed()))
	2244	{
	2245	// test all planes of current node on neighbour
	2246	PolygonContainer neighborCandidate;
	2247	ConstructGeometry(node, neighborCandidate);
	2248
	2249	bool isAdjacent = true;
	2250	for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
	2251	{
	2252	const int cf =
[390]	2253	Polygon3::ClassifyPlane(neighborCandidate, planes[i]);
[375]	2254
	2255	if ((cf == Polygon3::BACK_SIDE) && sides[i])
	2256	isAdjacent = false;
	2257	else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
	2258	isAdjacent = false;
	2259	}
	2260
	2261	if (isAdjacent)
	2262	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
	2263
	2264	CLEAR_CONTAINER(neighborCandidate);
	2265	}
	2266	}
	2267	else
	2268	{
	2269	BspInterior interior = dynamic_cast<BspInterior >(node);
	2270
	2271	const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
	2272
	2273	if (cf == Polygon3::FRONT_SIDE)
	2274	nodeStack.push(interior->mFront);
	2275	else
	2276	if (cf == Polygon3::BACK_SIDE)
	2277	nodeStack.push(interior->mBack);
	2278	else
	2279	{
	2280	// random decision
	2281	nodeStack.push(interior->mBack);
	2282	nodeStack.push(interior->mFront);
	2283	}
	2284	}
	2285	}
	2286
	2287	CLEAR_CONTAINER(cell);
	2288	return (int)neighbors.size();
	2289	}
	2290
	2291	BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
	2292	{
	2293	stack<BspNode *> nodeStack;
	2294	nodeStack.push(mRoot);
	2295
	2296	int mask = rand();
	2297
	2298	while (!nodeStack.empty())
	2299	{
	2300	BspNode *node = nodeStack.top();
	2301	nodeStack.pop();
	2302
	2303	if (node->IsLeaf())
	2304	{
	2305	return dynamic_cast<BspLeaf *>(node);
	2306	}
	2307	else
	2308	{
	2309	BspInterior interior = dynamic_cast<BspInterior >(node);
	2310
	2311	BspNode *next;
	2312
	2313	PolygonContainer cell;
	2314
	2315	// todo: not very efficient: constructs full cell everytime
	2316	ConstructGeometry(interior, cell);
	2317
	2318	const int cf = Polygon3::ClassifyPlane(cell, halfspace);
	2319
	2320	if (cf == Polygon3::BACK_SIDE)
	2321	next = interior->mFront;
	2322	else
	2323	if (cf == Polygon3::FRONT_SIDE)
	2324	next = interior->mFront;
	2325	else
	2326	{
	2327	// random decision
	2328	if (mask & 1)
	2329	next = interior->mBack;
	2330	else
	2331	next = interior->mFront;
	2332	mask = mask >> 1;
	2333	}
	2334
	2335	nodeStack.push(next);
	2336	}
	2337	}
	2338
	2339	return NULL;
	2340	}
	2341
	2342	BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
	2343	{
	2344	stack<BspNode *> nodeStack;
	2345
	2346	nodeStack.push(mRoot);
	2347
	2348	int mask = rand();
	2349
	2350	while (!nodeStack.empty())
	2351	{
	2352	BspNode *node = nodeStack.top();
	2353	nodeStack.pop();
	2354
	2355	if (node->IsLeaf())
	2356	{
	2357	if ( (!onlyUnmailed \|\| !node->Mailed()) )
	2358	return dynamic_cast<BspLeaf *>(node);
	2359	}
	2360	else
	2361	{
	2362	BspInterior interior = dynamic_cast<BspInterior >(node);
	2363
	2364	// random decision
	2365	if (mask & 1)
	2366	nodeStack.push(interior->mBack);
	2367	else
	2368	nodeStack.push(interior->mFront);
	2369
	2370	mask = mask >> 1;
	2371	}
	2372	}
	2373
	2374	return NULL;
	2375	}
[384]	2376
	2377	int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
	2378	{
	2379	int pvsSize = 0;
	2380
	2381	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
	2382
	2383	Intersectable::NewMail();
	2384
	2385	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2386	{
	2387	Ray ray = (rit)->mRay;
	2388
	2389	if (!ray->intersections.empty())
	2390	{
	2391	if (!ray->intersections[0].mObject->Mailed())
	2392	{
	2393	ray->intersections[0].mObject->Mail();
	2394	++ pvsSize;
	2395	}
	2396	}
	2397	if (!ray->sourceObject.mObject->Mailed())
	2398	{
	2399	ray->sourceObject.mObject->Mail();
	2400	++ pvsSize;
	2401	}
	2402	}
	2403
	2404	return pvsSize;
[390]	2405	}
	2406
	2407	/*************************************************************
	2408	* BspNodeGeometry Implementation *
	2409	*************************************************************/
	2410
	2411	BspNodeGeometry::BspNodeGeometry(const PolygonContainer &polys,
	2412	const vector<Plane3> &planes,
	2413	const vector<bool> &sides):
	2414	mPolys(polys), mPlanes(planes), mSides(sides)
	2415	{}
	2416
	2417	BspNodeGeometry::BspNodeGeometry(const vector<Plane3> &planes,
	2418	const vector<bool> &sides):
	2419	mPlanes(planes), mSides(sides)
	2420	{}
	2421
	2422	BspNodeGeometry::~BspNodeGeometry()
	2423	{
	2424	CLEAR_CONTAINER(mPolys);
	2425	}
	2426
	2427	float BspNodeGeometry::GetArea() const
	2428	{
	2429	return Polygon3::GetArea(mPolys);
	2430	}
	2431
	2432	BspNodeGeometry *BspNodeGeometry::ConstructChild(const BspTree &tree,
	2433	const Plane3 &splitPlane,
	2434	const bool side) const
	2435	{
	2436	BspNodeGeometry *childCell = new BspNodeGeometry(mPlanes, mSides);
	2437
	2438	// get cross section of new polygon
	2439	Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(splitPlane);
	2440
	2441	// polygon is split by all other planes
	2442	for (int i = 0; (i < (int)mPlanes.size()) && planePoly; ++ i)
	2443	{
	2444	const int cf = planePoly->ClassifyPlane(mPlanes[i]);
	2445
	2446	// split new polygon with all previous planes
	2447	switch (cf)
	2448	{
	2449	case Polygon3::SPLIT:
	2450	{
	2451	VertexContainer splitPts;
	2452
	2453	Polygon3 *frontPoly = new Polygon3();
	2454	Polygon3 *backPoly = new Polygon3();
	2455
	2456	planePoly->Split(mPlanes[i], frontPoly, backPoly, splitPts);
	2457	DEL_PTR(planePoly);
	2458
	2459	if(mSides[i] == true)
	2460	{
	2461	planePoly = frontPoly;
	2462	DEL_PTR(backPoly);
	2463	}
	2464	else
	2465	{
	2466	planePoly = backPoly;
	2467	DEL_PTR(frontPoly);
	2468	}
	2469
	2470	if (!planePoly->Valid())
	2471	DEL_PTR(planePoly);
	2472	}
	2473	break;
	2474	case Polygon3::BACK_SIDE:
	2475	if (mSides[i])
	2476	DEL_PTR(planePoly);
	2477	break;
	2478	case Polygon3::FRONT_SIDE:
	2479	if (!mSides[i])
	2480	DEL_PTR(planePoly);
	2481	break;
	2482	case Polygon3::COINCIDENT:
	2483	break;
	2484	default:
	2485	break;
	2486	}
	2487	}
	2488
	2489	//-- plane poly splits all other cell polygons
	2490	for (int i = 0; i < (int)mPolys.size(); ++ i)
	2491	{
	2492	const int cf = mPolys[i]->ClassifyPlane(splitPlane);
	2493
	2494	// split new polygon with all previous planes
	2495	switch (cf)
	2496	{
	2497	case Polygon3::SPLIT:
	2498	{
	2499	Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
	2500
	2501	Polygon3 *frontPoly = new Polygon3();
	2502	Polygon3 *backPoly = new Polygon3();
	2503
	2504	VertexContainer splitPts;
	2505
	2506	poly->Split(splitPlane, frontPoly, backPoly, splitPts);
[392]	2507
[390]	2508	DEL_PTR(poly);
	2509
	2510	if (side == true)
	2511	{
	2512	poly = frontPoly;
	2513	DEL_PTR(backPoly);
	2514	}
	2515	else
	2516	{
	2517	poly = backPoly;
	2518	DEL_PTR(frontPoly);
	2519	}
	2520	if (!poly->Valid())
	2521	DEL_PTR(poly);
	2522	else
	2523	childCell->mPolys.push_back(poly);
	2524	}
	2525
	2526	break;
	2527	case Polygon3::BACK_SIDE:
	2528	if (!side)
	2529	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
	2530	break;
	2531	case Polygon3::FRONT_SIDE:
	2532	if (side)
	2533	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
	2534	break;
	2535	case Polygon3::COINCIDENT:
	2536	childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
	2537	break;
	2538	default:
	2539
	2540	break;
	2541	}
	2542	}
	2543
	2544	//-- finally add the new polygon
[393]	2545	if (planePoly)
	2546	{
	2547	childCell->mPolys.push_back(planePoly);
	2548	childCell->mPlanes.push_back(splitPlane);
	2549	childCell->mSides.push_back(side);
	2550	}
[390]	2551
[392]	2552	Debug << "returning new geometry " << mPolys.size() << " CHILD: " << childCell->mPolys.size() << endl;
[391]	2553
[392]	2554	Debug << "old area " << this->GetArea() << " new: " << childCell->GetArea() << endl;
[390]	2555	return childCell;
[384]	2556	}

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

Download in other formats: