pyrit: src/kdtree.cc@3239f749e394 (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	{
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	25	// choose split axis
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	26	axis = 0;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	27	if (bbox.R.y - bbox.L.y > bbox.R.x - bbox.L.x)
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	28	axis = 1;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	29	if (bbox.R.z - bbox.L.z > bbox.R.y - bbox.L.y)
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	30	axis = 2;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	31
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	32	// *** find optimal split position
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	33	SortableShapeList sslist(shapes, axis);
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	34	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	35
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	36	SplitList splitlist = SplitList();
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	SortableShapeList::iterator sh;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	39	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	40	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	41	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	42	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	43	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	44	sort(splitlist.begin(), splitlist.end());
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	45
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	46	// find all posible splits
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	47	SplitList::iterator spl;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	48	int rest;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	49	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	50	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	51	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	52	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	53	if (sh->hasMark())
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	54	continue;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	55	// 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	56	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	57	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	58	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	59	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	60	// 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	61	if (spl->lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	62	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	63	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	64	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	65	} else {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	66	// right subcell is smaller
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	67	if (spl->rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	68	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	69	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	70	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	71	}
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	72	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	73	// 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	74	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	75	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	76	sh->setMark();
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	77	spl->lnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	78	} else
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	79	// 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	80	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	81	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	82	spl->lnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	83	spl->rnum++;
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 right 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.L.cell[axis] >= spl->pos)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	87	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	88	spl->rnum += rest;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	89	break;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	90	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	91	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	92	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	93
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	94	// choose best split pos
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	95	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	96	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	97	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	98	SplitPos *splitpos = NULL;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	99	leaf = true;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	100	BBox lbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	101	BBox rbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	102	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	103	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	104	// calculate SAH cost of this split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	105	lbb.R.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	106	rbb.L.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	107	float SAL = 2(lbb.w()lbb.h() + lbb.w()lbb.d() + lbb.h()lbb.d());
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	108	float SAR = 2(rbb.w()rbb.h() + rbb.w()rbb.d() + rbb.h()rbb.d());
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	109	float splitcost = K + SAL/SAV(K+spl->lnum) + SAR/SAV(K+spl->rnum);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	110
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	111	if (splitcost < cost)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	112	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	113	leaf = false;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	114	cost = splitcost;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	115	splitpos = &*spl;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	116	}
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	117	}
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	118
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	119	if (leaf)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	120	return;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	121
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	122	split = splitpos->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	123	float lnum = splitpos->lnum;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	124	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	125
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	126	// split this node
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	127	children = new KdNode[2];
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	128	int state = 0;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	129	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	130	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	131	// 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	132	if (state == 1)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	133	{ // only right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	134	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	135	continue;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	136	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	137	if (state == 0)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	138	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	139	if (sh->bbox.R.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	140	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	141	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	142	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	143	if (sh->bbox.R.cell[axis] > split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	144	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	145	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	146	{ // both
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	147	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	148	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	149	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	150	{ // right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	151	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	152	state = 1;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	153	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	154	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	155	{ // R == split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	156	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	157	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	158	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	159	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	160	{ // contained
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	161	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	162	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	163	// 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	164	if (lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	165	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	166	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	167	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	168	} else {
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	169	// right subcell is smaller
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	170	if (rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	171	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	172	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	173	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	174	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	175	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	176	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	177	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	178	}
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	lbb.R.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	181	rbb.L.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	182
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	183	children[0].subdivide(lbb, depth+1);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	184	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	185	}
3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	186
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	187	void KdTree::build()
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	188	{
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	189	root = new KdNode();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	190	root->shapes = shapes;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	191	root->subdivide(bbox, 0);
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	192	}

author	Radek Brich <radek.brich@devl.cz>
	Thu, 22 Nov 2007 21:46:09 +0100
branch	pyrit
changeset 9	3239f749e394
parent 7	bf17f9f84c91
child 10	f9fad94cd0cc
permissions	-rw-r--r--