--- a/src/kdtree.cc Sun Nov 25 15:50:01 2007 +0100
+++ b/src/kdtree.cc Sun Nov 25 17:58:29 2007 +0100
@@ -23,10 +23,10 @@
class SortableShapeList: public vector<SortableShape>
{
public:
- SortableShapeList(ShapeList &shapes, short axis)
+ SortableShapeList(ShapeList *shapes, short axis)
{
ShapeList::iterator shape;
- for (shape = shapes.begin(); shape != shapes.end(); shape++)
+ for (shape = shapes->begin(); shape != shapes->end(); shape++)
push_back(SortableShape(*shape, axis));
};
};
@@ -89,9 +89,9 @@
void KdNode::subdivide(BBox bbox, int depth)
{
- if (depth >= 20 || shapes.size() <= 4)
+ if (depth >= 20 || shapes->size() <= 4)
{
- leaf = true;
+ setLeaf();
return;
}
@@ -173,9 +173,9 @@
// choose best split pos
const float K = 1.4; // constant, K = cost of traversal / cost of ray-triangle intersection
float SAV = 2*(bbox.w()*bbox.h() + bbox.w()*bbox.d() + bbox.h()*bbox.d()); // surface area of node
- float cost = SAV * (K + shapes.size()); // initial cost = non-split cost
+ float cost = SAV * (K + shapes->size()); // initial cost = non-split cost
SplitPos *splitpos = NULL;
- leaf = true;
+ bool leaf = true;
BBox lbb = bbox;
BBox rbb = bbox;
for (spl = splitlist.begin(); spl != splitlist.end(); spl++)
@@ -196,9 +196,12 @@
}
if (leaf)
+ {
+ setLeaf();
return;
+ }
-#if 1
+#if 0
// export kd-tree as .obj for visualization
// this would be hard to reconstruct later
static ofstream F("kdtree.obj");
@@ -289,7 +292,7 @@
void KdTree::build()
{
root = new KdNode();
- root->shapes = shapes;
+ root->shapes = &shapes;
root->subdivide(bbox, 0);
built = true;
}
@@ -320,14 +323,14 @@
/* distinguish between internal and external origin */
if (a >= 0.0) /* a ray with external origin */
- enPt->pb = ray.a + ray.dir * a;
+ enPt->pb = ray.o + ray.dir * a;
else /* a ray with internal origin */
- enPt->pb = ray.a;
+ enPt->pb = ray.o;
/* setup initial exit point in the stack */
StackElem *exPt = new StackElem();
exPt->t = b;
- exPt->pb = ray.a + ray.dir * b;
+ exPt->pb = ray.o + ray.dir * b;
exPt->node = NULL; /* set termination flag */
st.push(enPt);
@@ -374,7 +377,7 @@
/* case P4 or N4 . . . traverse both children */
/* signed distance to the splitting plane */
- t = (splitVal - ray.a.cell[axis]) / ray.dir.cell[axis];
+ t = (splitVal - ray.o.cell[axis]) / ray.dir.cell[axis];
/* setup the new exit point */
st.push(exPt);
@@ -384,8 +387,8 @@
exPt->t = t;
exPt->node = farchild;
exPt->pb[axis] = splitVal;
- exPt->pb[(axis+1)%3] = ray.a.cell[(axis+1)%3] + t * ray.dir.cell[(axis+1)%3];
- exPt->pb[(axis+2)%3] = ray.a.cell[(axis+2)%3] + t * ray.dir.cell[(axis+2)%3];
+ 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];
} /* while */
/* current node is the leaf . . . empty or full */
@@ -394,7 +397,7 @@
Shape *nearest_shape = NULL;
float dist = exPt->t;
ShapeList::iterator shape;
- for (shape = node->shapes.begin(); shape != node->shapes.end(); shape++)
+ for (shape = node->shapes->begin(); shape != node->shapes->end(); shape++)
if (*shape != origin_shape && (*shape)->intersect(ray, dist)
&& dist >= enPt->t)
nearest_shape = *shape;
@@ -431,7 +434,7 @@
if (node == NULL)
node = root;
if (node->isLeaf())
- str << "(leaf: " << node->shapes.size() << " shapes)";
+ str << "(leaf: " << node->shapes->size() << " shapes)";
else
{
str << "(split " << (char)('x'+node->getAxis()) << " at " << node->getSplit() << "; L=";