pyrit: comparison src/kdtree.cc

equal deleted inserted replaced

-:f22952603f29
+:79b516a3803d
 class SplitList: public vector<SplitPos>
 {
 };
 // stack element for kd-tree traversal
-struct StackElem
+class StackElem
 {
+public:
 	KdNode* node; /* pointer to far child */
 	float t; /* the entry/exit signed distance */
 	Vector3 pb; /* the coordinates of entry/exit point */
+	StackElem(KdNode *anode, const float &at, const Vector3 &apb):
+		node(anode), t(at), pb(apb) {};
 };
 // ----------------------------------------
 void Container::addShape(Shape* aShape)
 		delete shapes;
 	else
 		delete[] children;
 }
-void KdNode::subdivide(BBox bbox, int depth)
+void KdNode::subdivide(BBox bbox, int maxdepth)
 {
-	if (depth >= 20 || shapes->size() <= 4)
+	if (maxdepth <= 0 || shapes->size() <= 2)
 	{
 		setLeaf();
 		return;
 	}
 	}
 	lbb.H.cell[axis] = split;
 	rbb.L.cell[axis] = split;
-	children[0].subdivide(lbb, depth+1);
+	children[0].subdivide(lbb, maxdepth-1);
-	children[1].subdivide(rbb, depth+1);
+	children[1].subdivide(rbb, maxdepth-1);
 }
 void KdTree::build()
 {
 	infomsg("* building kd-tree\n");
 	root = new KdNode();
 	ShapeList::iterator shape;
 	for (shape = shapes.begin(); shape != shapes.end(); shape++)
 		root->addShape(*shape);
-	root->subdivide(bbox, 0);
+	root->subdivide(bbox, max_depth);
 	built = true;
 }
 /* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */
 Shape *KdTree::nearest_intersection(const Shape *origin_shape, const Ray &ray,
 	/* pointers to the far child node and current node */
 	KdNode *farchild, *node;
 	node = root; /* start from the kd-tree root node */
-	stack<StackElem*> st;
+	/* std vector is much faster than stack */
+	vector<StackElem*> st;
-	StackElem *enPt = new StackElem();
-	enPt->t = a; /* set the signed distance */
+	StackElem *enPt = new StackElem(NULL, a,
-	enPt->node = NULL;
+		/* distinguish between internal and external origin of a ray*/
+		a >= 0.0 ?
-	/* distinguish between internal and external origin */
+			ray.o + ray.dir * a : /* external */
-	if (a >= 0.0) /* a ray with external origin */
+			ray.o);               /* internal */
-		enPt->pb = ray.o + ray.dir * a;
-	else /* a ray with internal origin */
-		enPt->pb = ray.o;
 	/* setup initial exit point in the stack */
-	StackElem *exPt = new StackElem();
+	StackElem *exPt = new StackElem(NULL, b, ray.o + ray.dir * b);
-	exPt->t = b;
+	st.push_back(exPt);
-	exPt->pb = ray.o + ray.dir * b;
-	exPt->node = NULL; /* set termination ﬂag */
-	st.push(exPt);
 	/* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */
 	while (node)
 	{
-		exPt = st.top();
+		exPt = st.back();
 		/* loop until a leaf is found */
 		while (!node->isLeaf())
 		{
 			/* retrieve position of splitting plane */
 			float splitVal = node->getSplit();
 			/* signed distance to the splitting plane */
 			t = (splitVal - ray.o.cell[axis]) / ray.dir.cell[axis];
 			/* setup the new exit point and push it onto stack */
-			exPt = new StackElem();
+			exPt = new StackElem(farchild, t, Vector3());
-			exPt->t = t;
-			exPt->node = farchild;
 			exPt->pb[axis] = splitVal;
 			exPt->pb[(axis+1)%3] = ray.o.cell[(axis+1)%3] + t * ray.dir.cell[(axis+1)%3];
 			exPt->pb[(axis+2)%3] = ray.o.cell[(axis+2)%3] + t * ray.dir.cell[(axis+2)%3];
-			st.push(exPt);
+			st.push_back(exPt);
 		} /* while */
 		/* current node is the leaf . . . empty or full */
 		/* "intersect ray with each object in the object list, discarding "
 		"those lying before stack[enPt].t or farther than stack[exPt].t" */
 		if (nearest_shape)
 		{
 			while (!st.empty())
 			{
-				delete st.top();
+				delete st.back();
-				st.pop();
+				st.pop_back();
 			}
 			nearest_distance = dist;
 			return nearest_shape;
 		}
 		enPt = exPt;
 		/* retrieve the pointer to the next node, it is possible that ray traversal terminates */
 		node = enPt->node;
-		st.pop();
+		st.pop_back();
 	} /* while */
 	delete enPt;
 	/* ray leaves the scene */

branch	pyrit
changeset 21	79b516a3803d
parent 20	f22952603f29
child 22	76b7bd51d64a