pyrit: src/kdtree.cc@f4fcabf05785 (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>
12 f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	2	#include <stack>
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	3
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	4	#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	5
12 f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	6	class SortableShape
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	7	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	8	public:
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	9	Shape *shape;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	10	BBox bbox;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	11	short axis;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	12	short mark;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	13
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	14	SortableShape(Shape *aShape, short &aAxis): shape(aShape), axis(aAxis), mark(0)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	15	{ bbox = shape->get_bbox(); };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	16	friend bool operator<(const SortableShape& a, const SortableShape& b)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	17	{ return a.bbox.L.cell[a.axis] < b.bbox.L.cell[b.axis]; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	18	void setAxis(short aAxis) { axis = aAxis; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	19	void setMark() { mark = 1; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	20	short hasMark() { return mark; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	21	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	22
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	23	class SortableShapeList: public vector<SortableShape>
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	24	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	25	public:
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	26	SortableShapeList(ShapeList &shapes, short axis)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	27	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	28	ShapeList::iterator shape;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	29	for (shape = shapes.begin(); shape != shapes.end(); shape++)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	30	push_back(SortableShape(*shape, axis));
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	31	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	32	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	33
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	34	class SplitPos
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	35	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	36	public:
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	37	float pos;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	38	int lnum, rnum;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	39	SplitPos(): pos(0.0), lnum(0), rnum(0) {};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	40	SplitPos(float &aPos): pos(aPos), lnum(0), rnum(0) {};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	41	friend bool operator<(const SplitPos& a, const SplitPos& b)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	42	{ return a.pos < b.pos; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	43	friend bool operator==(const SplitPos& a, const SplitPos& b)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	44	{ return a.pos == b.pos; };
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	45	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	46
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	47	class SplitList: public vector<SplitPos>
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	48	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	49	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	50
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	51	// stack element for kd-tree traversal
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	52	struct StackElem
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	53	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	54	KdNode* node; /* pointer to far child */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	55	float t; /* the entry/exit signed distance */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	56	Vector3 pb; /* the coordinates of entry/exit point */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	57	};
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	58
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	59	// ----------------------------------------
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	60
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	61	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	62	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	63	shapes.push_back(aShape);
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	64	if (shapes.size() == 0) {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	65	/* initialize bounding box */
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	66	bbox = aShape->get_bbox();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	67	} else {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	68	/* adjust bounding box */
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	69	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	70	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	71	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	72	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	73	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	74	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	75	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	76	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	77	};
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	78
11 4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	79	Shape Container::nearest_intersection(const Shape origin_shape, const Ray &ray,
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	80	float &nearest_distance)
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	81	{
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	82	Shape *nearest_shape = NULL;
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	83	ShapeList::iterator shape;
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	84	for (shape = shapes.begin(); shape != shapes.end(); shape++)
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	85	if (shape != origin_shape && (shape)->intersect(ray, nearest_distance))
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	86	nearest_shape = *shape;
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	87	return nearest_shape;
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	88	}
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	89
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	90	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	91	{
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	92	if (depth >= 10 \|\| shapes.size() <= 2)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	93	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	94	leaf = true;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	95	return;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	96	}
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	97
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	98	// choose split axis
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	99	axis = 0;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	100	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	101	axis = 1;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	102	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	103	axis = 2;
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	// *** find optimal split position
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	106	SortableShapeList sslist(shapes, axis);
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	107	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	108
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	109	SplitList splitlist;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	110
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	111	SortableShapeList::iterator sh;
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	112	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	113	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	114	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	115	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	116	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	117	sort(splitlist.begin(), splitlist.end());
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	118	// remove duplicate splits
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	119	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	120
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	121	// find all posible splits
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	122	SplitList::iterator spl;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	123	int rest;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	124	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	125	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	126	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	127	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	128	if (sh->hasMark())
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	129	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	130	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	131	continue;
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	132	}
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	133	// 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	134	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	135	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	136	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	137	{
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	138	// 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	139	if (spl->lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	140	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	141	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	142	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	143	} else {
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	144	// right subcell is smaller
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	145	if (spl->rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	146	spl->rnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	147	else
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	148	spl->lnum++;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	149	}
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	150	sh->setMark();
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	151	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	152	// 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	153	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	154	{
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	155	spl->lnum++;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	156	sh->setMark();
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	157	} else
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	158	// 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	159	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	160	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	161	spl->lnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	162	spl->rnum++;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	163	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	164	// 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	165	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	166	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	167	spl->rnum += rest;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	168	break;
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	169	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	170	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	171	}
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	172
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	173	// choose best split pos
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	174	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	175	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	176	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	177	SplitPos *splitpos = NULL;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	178	leaf = true;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	179	BBox lbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	180	BBox rbb = bbox;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	181	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	182	{
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	183	// calculate SAH cost of this split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	184	lbb.R.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	185	rbb.L.cell[axis] = spl->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	186	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	187	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	188	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	189
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	190	if (splitcost < cost)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	191	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	192	leaf = false;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	193	cost = splitcost;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	194	splitpos = &*spl;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	195	}
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	196	}
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	197
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	198	if (leaf)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	199	return;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	200
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	201	#if 1
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	202	// 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	203	// 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	204	static ofstream F("kdtree.obj");
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	205	Vector3 v;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	206	static int f=0;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	207	v.cell[axis] = splitpos->pos;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	208	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	209	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	210	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	211	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	212	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	213	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	214	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	215	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	216	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	217	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	218	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	219	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	220	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	221	f += 4;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	222	#endif
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	223
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	224	split = splitpos->pos;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	225	float lnum = splitpos->lnum;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	226	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	227
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	228	// split this node
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	229	children = new KdNode[2];
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	230	int state = 0;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	231	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	232	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	233	// 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	234	if (state == 1)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	235	{ // only right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	236	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	237	continue;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	238	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	239	if (state == 0)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	240	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	241	if (sh->bbox.R.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	242	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	243	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	244	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	245	if (sh->bbox.R.cell[axis] > split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	246	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	247	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	248	{ // both
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	249	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	250	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	251	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	252	{ // right
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	253	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	254	state = 1;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	255	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	256	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	257	{ // R == split
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	258	if (sh->bbox.L.cell[axis] < split)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	259	{ // left
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	260	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	261	} else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	262	{ // contained
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	263	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	264	{
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	265	// 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	266	if (lnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	267	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	268	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	269	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	270	} else {
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	271	// right subcell is smaller
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	272	if (rnum)
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	273	children[1].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	274	else
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	275	children[0].addShape(sh->shape);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	276	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	277	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	278	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	279	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	280	}
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	281
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	282	lbb.R.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	283	rbb.L.cell[axis] = split;
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	284
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	285	children[0].subdivide(lbb, depth+1);
3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	286	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	287	}
3547b885df7e initial commit, raytracer source as written year ago and unchanged since 2007-03-25 Radek Brich <radek.brich@devl.cz> parents: diff changeset	288
11 4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	289	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	290	{
7 bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	291	root = new KdNode();
bf17f9f84c91 kd-tree: build algorithm - searching for all posible splits Radek Brich <radek.brich@devl.cz> parents: 0 diff changeset	292	root->shapes = shapes;
9 3239f749e394 kd-tree: build algorithm - completed, untested Radek Brich <radek.brich@devl.cz> parents: 7 diff changeset	293	root->subdivide(bbox, 0);
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	294	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	295	}
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	296
12 f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	297	/* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	298	Shape KdTree::nearest_intersection(const Shape origin_shape, const Ray &ray,
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	299	float &nearest_distance)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	300	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	301	float a, b; /* entry/exit signed distance */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	302	float t; /* signed distance to the splitting plane */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	303
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	304	/* if we have no tree, fall back to naive test */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	305	if (!built)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	306	return Container::nearest_intersection(origin_shape, ray, nearest_distance);
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	307
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	308	if (!bbox.intersect(ray, a, b))
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	309	return NULL;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	310
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	311	stack<StackElem*> st;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	312
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	313	/* pointers to the far child node and current node */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	314	KdNode farchild, node;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	315	node = root; /* start from the kd-tree root node */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	316
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	317	StackElem *enPt = new StackElem();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	318	enPt->t = a; /* set the signed distance */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	319	enPt->node = NULL;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	320
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	321	/* distinguish between internal and external origin */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	322	if (a >= 0.0) /* a ray with external origin */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	323	enPt->pb = ray.a + ray.dir * a;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	324	else /* a ray with internal origin */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	325	enPt->pb = ray.a;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	326
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	327	/* setup initial exit point in the stack */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	328	StackElem *exPt = new StackElem();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	329	exPt->t = b;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	330	exPt->pb = ray.a + ray.dir * b;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	331	exPt->node = NULL; /* set termination ﬂag */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	332
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	333	st.push(enPt);
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	334
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	335	/* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	336	while (node)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	337	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	338	/* loop until a leaf is found */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	339	while (!node->isLeaf())
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	340	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	341	/* retrieve position of splitting plane */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	342	float splitVal = node->getSplit();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	343	short axis = node->getAxis();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	344
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	345	if (enPt->pb[axis] <= splitVal)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	346	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	347	if (exPt->pb[axis] <= splitVal)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	348	{ /* case N1, N2, N3, P5, Z2, and Z3 */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	349	node = node->getLeftChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	350	continue;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	351	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	352	if (exPt->pb[axis] == splitVal)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	353	{ /* case Z1 */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	354	node = node->getRightChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	355	continue;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	356	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	357	/* case N4 */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	358	farchild = node->getRightChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	359	node = node->getLeftChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	360	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	361	else
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	362	{ /* (enPt->pb[axis] > splitVal) */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	363	if (splitVal < exPt->pb[axis])
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	364	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	365	/* case P1, P2, P3, and N5 */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	366	node = node->getRightChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	367	continue;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	368	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	369	/* case P4*/
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	370	farchild = node->getLeftChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	371	node = node->getRightChild();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	372	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	373
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	374	/* case P4 or N4 . . . traverse both children */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	375
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	376	/* signed distance to the splitting plane */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	377	t = (splitVal - ray.a.cell[axis]) / ray.dir.cell[axis];
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	378
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	379	/* setup the new exit point */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	380	st.push(exPt);
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	381	exPt = new StackElem();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	382
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	383	/* push values onto the stack */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	384	exPt->t = t;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	385	exPt->node = farchild;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	386	exPt->pb[axis] = splitVal;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	387	exPt->pb[(axis+1)%3] = ray.a.cell[(axis+1)%3] + t * ray.dir.cell[(axis+1)%3];
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	388	exPt->pb[(axis+2)%3] = ray.a.cell[(axis+2)%3] + t * ray.dir.cell[(axis+2)%3];
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	389	} /* while */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	390
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	391	/* current node is the leaf . . . empty or full */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	392	/* "intersect ray with each object in the object list, discarding "
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	393	"those lying before stack[enPt].t or farther than stack[exPt].t" */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	394	Shape *nearest_shape = NULL;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	395	float dist = exPt->t;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	396	ShapeList::iterator shape;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	397	for (shape = node->shapes.begin(); shape != node->shapes.end(); shape++)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	398	if (shape != origin_shape && (shape)->intersect(ray, dist)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	399	&& dist >= enPt->t)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	400	nearest_shape = *shape;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	401
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	402	if (nearest_shape)
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	403	{
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	404	nearest_distance = dist;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	405	return nearest_shape;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	406	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	407
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	408	/* pop from the stack */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	409	enPt = exPt; /* the signed distance intervals are adjacent */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	410
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	411	/* retrieve the pointer to the next node, it is possible that ray traversal terminates */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	412	node = enPt->node;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	413
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	414	// pop
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	415	exPt = st.top();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	416	st.pop();
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	417	} /* while */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	418
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	419	/* ray leaves the scene */
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	420	return NULL;
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	421	}
f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	422
11 4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	423	// this should save whole kd-tree with triangles distributed into leaves
10 f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	424	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	425	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	426	if (!built)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	427	return;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	428	if (node == NULL)
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	429	node = root;
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	430	if (node->isLeaf())
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	431	str << "(leaf: " << node->shapes.size() << " shapes)";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	432	else
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	433	{
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	434	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	435	save(str, node->getLeftChild());
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	436	str << "; R=";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	437	save(str, node->getRightChild());
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	438	str << ";)";
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	439	}
f9fad94cd0cc kd-tree: build algorithm tested and fixed Radek Brich <radek.brich@devl.cz> parents: 9 diff changeset	440	}
11 4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	441
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	442	// load kd-tree from file/stream
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	443	void KdTree::load(istream &str, KdNode *node)
4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	444	{
12 f4fcabf05785 kd-tree: traversal algorithm (KdTree::nearest_intersection) Radek Brich <radek.brich@devl.cz> parents: 11 diff changeset	445
11 4d192e13ee84 move nearest_intersection() to Container, add dummy KdTree.load(), plus small fixes Radek Brich <radek.brich@devl.cz> parents: 10 diff changeset	446	}

author	Radek Brich <radek.brich@devl.cz>
	Sat, 24 Nov 2007 21:55:41 +0100
branch	pyrit
changeset 12	f4fcabf05785
parent 11	4d192e13ee84
child 13	fbd1d2f7d94e
permissions	-rw-r--r--