diff -r fc18ac4833f2 -r a0a3e334744f src/kdtree.cc --- 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 { 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=";