pyrit: src/kdtree.cc@f9fad94cd0cc (annotated)

7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	1	#include <algorithm>
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	2
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	3	#include "kdtree.h"
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	4
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	5	void Container::addShape(Shape* aShape)
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	6	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	7	shapes.push_back(aShape);
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	8	if (shapes.size() == 0) {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	9	/* initialize bounding box */
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	10	bbox = aShape->get_bbox();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	11	} else {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	12	/* adjust bounding box */
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	13	BBox shapebb = aShape->get_bbox();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	14	if (shapebb.L.x < bbox.L.x) bbox.L.x = shapebb.L.x;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	15	if (shapebb.L.y < bbox.L.y) bbox.L.y = shapebb.L.y;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	16	if (shapebb.L.z < bbox.L.z) bbox.L.z = shapebb.L.z;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	17	if (shapebb.R.x > bbox.R.x) bbox.R.x = shapebb.R.x;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	18	if (shapebb.R.y > bbox.R.y) bbox.R.y = shapebb.R.y;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	19	if (shapebb.R.z > bbox.R.z) bbox.R.z = shapebb.R.z;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	20	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	21	};
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	22
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	23	void KdNode::subdivide(BBox bbox, int depth)
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	24	{
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	25	if (depth >= 10 \|\| shapes.size() <= 2)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	26	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	27	leaf = true;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	28	return;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	29	}
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	30
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	31	// choose split axis
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	32	axis = 0;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	33	if (bbox.h() > bbox.w() && bbox.h() > bbox.d())
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	34	axis = 1;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	35	if (bbox.d() > bbox.w() && bbox.d() > bbox.h())
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	36	axis = 2;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	37
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	38	// *** find optimal split position
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	39	SortableShapeList sslist(shapes, axis);
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	40	sort(sslist.begin(), sslist.end());
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	41
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	42	SplitList splitlist;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	43
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	44	SortableShapeList::iterator sh;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	45	for (sh = sslist.begin(); sh != sslist.end(); sh++)
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	46	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	47	splitlist.push_back(SplitPos(sh->bbox.L.cell[axis]));
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	48	splitlist.push_back(SplitPos(sh->bbox.R.cell[axis]));
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	49	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	50	sort(splitlist.begin(), splitlist.end());
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	51	// remove duplicate splits
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	52	splitlist.resize(unique(splitlist.begin(), splitlist.end()) - splitlist.begin());
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	53
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	54	// find all posible splits
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	55	SplitList::iterator spl;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	56	int rest;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	57	for (spl = splitlist.begin(); spl != splitlist.end(); spl++)
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	58	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	59	for (sh = sslist.begin(), rest = sslist.size(); sh != sslist.end(); sh++, rest--)
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	60	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	61	if (sh->hasMark())
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	62	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	63	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	64	continue;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	65	}
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	66	// if shape is completely contained in split plane
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	67	if (spl->pos == sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis])
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	68	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	69	if (spl->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - spl->pos)
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	70	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	71	// left subcell is smaller -> if not empty, put shape here
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	72	if (spl->lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	73	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	74	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	75	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	76	} else {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	77	// right subcell is smaller
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	78	if (spl->rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	79	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	80	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	81	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	82	}
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	83	sh->setMark();
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	84	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	85	// if shape is on left side of split plane
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	86	if (sh->bbox.R.cell[axis] <= spl->pos)
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	87	{
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	88	spl->lnum++;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	89	sh->setMark();
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	90	} else
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	91	// if shape occupies both sides of split plane
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	92	if (sh->bbox.L.cell[axis] < spl->pos && sh->bbox.R.cell[axis] > spl->pos)
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	93	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	94	spl->lnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	95	spl->rnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	96	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	97	// if shape is on right side of split plane
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	98	if (sh->bbox.L.cell[axis] >= spl->pos)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	99	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	100	spl->rnum += rest;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	101	break;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	102	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	103	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	104	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	105
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	106	// choose best split pos
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	107	const float K = 1.4; // constant, K = cost of traversal / cost of ray-triangle intersection
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	108	float SAV = 2(bbox.w()bbox.h() + bbox.w()bbox.d() + bbox.h()bbox.d()); // surface area of node
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	109	float cost = SAV * (K + shapes.size()); // initial cost = non-split cost
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	110	SplitPos *splitpos = NULL;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	111	leaf = true;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	112	BBox lbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	113	BBox rbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	114	for (spl = splitlist.begin(); spl != splitlist.end(); spl++)
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	115	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	116	// calculate SAH cost of this split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	117	lbb.R.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	118	rbb.L.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	119	float SAL = 2(lbb.w()lbb.h() + lbb.w()lbb.d() + lbb.h()lbb.d());
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	120	float SAR = 2(rbb.w()rbb.h() + rbb.w()rbb.d() + rbb.h()rbb.d());
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	121	float splitcost = K + SAL/SAV(K+spl->lnum) + SAR/SAV(K+spl->rnum);
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	122
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	123	if (splitcost < cost)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	124	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	125	leaf = false;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	126	cost = splitcost;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	127	splitpos = &*spl;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	128	}
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	129	}
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	130
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	131	if (leaf)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	132	return;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	133
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	134	#if 1
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	135	// export kd-tree as .obj for visualization
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	136	// this would be hard to reconstruct later
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	137	static ofstream F("kdtree.obj");
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	138	Vector3 v;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	139	static int f=0;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	140	v.cell[axis] = splitpos->pos;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	141	v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	142	v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	143	F << "v " << v.x << " " << v.y << " " << v.z << endl;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	144	v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	145	v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	146	F << "v " << v.x << " " << v.y << " " << v.z << endl;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	147	v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	148	v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	149	F << "v " << v.x << " " << v.y << " " << v.z << endl;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	150	v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	151	v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3];
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	152	F << "v " << v.x << " " << v.y << " " << v.z << endl;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	153	F << "f " << f+1 << " " << f+2 << " " << f+3 << " " << f+4 << endl;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	154	f += 4;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	155	#endif
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	156
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	157	split = splitpos->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	158	float lnum = splitpos->lnum;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	159	float rnum = splitpos->rnum;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	160
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	161	// split this node
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	162	children = new KdNode[2];
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	163	int state = 0;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	164	for (sh = sslist.begin(); sh != sslist.end(); sh++)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	165	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	166	// if shape is on left side of split plane
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	167	if (state == 1)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	168	{ // only right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	169	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	170	continue;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	171	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	172	if (state == 0)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	173	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	174	if (sh->bbox.R.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	175	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	176	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	177	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	178	if (sh->bbox.R.cell[axis] > split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	179	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	180	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	181	{ // both
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	182	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	183	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	184	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	185	{ // right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	186	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	187	state = 1;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	188	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	189	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	190	{ // R == split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	191	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	192	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	193	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	194	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	195	{ // contained
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	196	if (split - bbox.L.cell[axis] < bbox.R.cell[axis] - split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	197	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	198	// left subcell is smaller -> if not empty, put shape here
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	199	if (lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	200	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	201	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	202	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	203	} else {
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	204	// right subcell is smaller
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	205	if (rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	206	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	207	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	208	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	209	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	210	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	211	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	212	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	213	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	214
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	215	lbb.R.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	216	rbb.L.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	217
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	218	children[0].subdivide(lbb, depth+1);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	219	children[1].subdivide(rbb, depth+1);
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	220	}
3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	221
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	222	void KdTree::optimize()
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	223	{
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	224	root = new KdNode();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	225	root->shapes = shapes;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	226	root->subdivide(bbox, 0);
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	227	built = true;
0 3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	228	}
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	229
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	230	void KdTree::save(ostream &str, KdNode *node)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	231	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	232	if (!built)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	233	return;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	234	if (node == NULL)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	235	node = root;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	236	if (node->isLeaf())
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	237	str << "(leaf: " << node->shapes.size() << " shapes)";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	238	else
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	239	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	240	str << "(split " << (char)('x'+node->getAxis()) << " at " << node->getSplit() << "; L=";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	241	save(str, node->getLeftChild());
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	242	str << "; R=";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	243	save(str, node->getRightChild());
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	244	str << ";)";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	245	}
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	246	}

author	Radek Brich <radek.brich@devl.cz>
	Fri, 23 Nov 2007 01:24:33 +0100
branch	pyrit
changeset 10	f9fad94cd0cc
parent 9	3239f749e394
child 11	4d192e13ee84
permissions	-rw-r--r--