(L) [2009/01/16] [cignox1] [Help with my BIH] Wayback!Ok, i never wrote acceleration structures. I've read many times the BIH paper and the relevant threads on this forum. I used the code from [LINK http://ompf.org/forum/viewtopic.php?f=4&t=718] as a reference and rewrote it for my renderer.
It renders the image, but it is also slower than simply using a list for the shapes.
Since I don't have a scene loader yet, I'm using a hard coded one. Here I have more or less 20 big triangles and a couple of spheres. So I have a few questions:
-Can big tris be so evil to make a bih slower than a list?
-Should I increase the scene complexity to see any improvement over a list?
I'm currently doing some test, here is the bih construction and traversal related code for those willing to give it a look (it is bad code, I know).
Code: [LINK # Select all] class BIHNode
{
public:
BIHNode* left;
BIHNode* right;
int axis;
union
{
unsigned int shapes[2];
real planes[2];
};
enum AXIS {AXIS_X, AXIS_Y, AXIS_Z, AXIS_NONE};
BIHNode() : left(NULL), right(NULL), axis(BIHNode::AXIS_NONE) {}
~BIHNode() { if(left != NULL) delete left; if(right != NULL) delete right; }
};
class QLBIHTree : public QLShapesCollection
{
private:
BIHNode *root;
qlaabox<real> worldbb;
std::list<QLShape*> shapes;
QLShape** shapes_array;
unsigned int shapes_count;
public:
QLBIHTree() : QLShapesCollection("No Name (BIH Tree)") {}
QLBIHTree(const std::string name) : QLShapesCollection(name)
{
shapes_array = NULL;
shapes_count = 0;
root = NULL;
}
//Shape overridden methods
bool Intersect(const ray<vector4<real>> &r, SurfacePoint &hitdesc) const
{
//Check the ray against the world bounding box
real min_t = -100.0, max_t = 100.0;
/*if(worldbb.BoundingHit(r, min_t, max_t) == false)
return false;*/
//Clip ray bounds
real ttmin = qlmath::Max (real(0), min_t);
real ttmax = qlmath::Min(r.maxdistance, max_t);
return IntersectTree(root, r, -qlmath::Min(ttmin, ttmax), qlmath::Max(ttmin, ttmax), hitdesc);
}
void Preprocess()
{
shapes_array = new QLShape*[(unsigned int)shapes.size()];
shapes_count = (unsigned int)shapes.size();
std::list<QLShape*>::iterator iter;
int i = 0;
for (iter = shapes.begin(); iter != shapes.end(); ++iter)
shapes_array[i++] = *iter;
worldbb = GetNodeAABB(0, shapes_count - 1);
root = CreateNode (0, shapes.size() - 1, worldbb.min, worldbb.max, BIHNode::AXIS_X);
}
private:
BIHNode* CreateLeafNode(unsigned int l, unsigned int r)
{
BIHNode *newnode = new BIHNode();
newnode->left = NULL;
newnode->right = NULL;
newnode->shapes[0] = l;
newnode->shapes[1] = r;
newnode->axis = BIHNode::AXIS_NONE;
return newnode;
}
BIHNode* CreateNode(unsigned int l, unsigned int r, const vector4<real> &minValue, const vector4<real> &maxValue, BIHNode::AXIS axis)
{
if(shapes.size() == 0)
return NULL;
if(l == r)
{
return CreateLeafNode(l, r);
}
unsigned int i;
unsigned int j;
bool left_empty = false;
bool right_empty = false;
bool left_doesshrik = false;
bool right_doesshrik = false;
bool both_balanced = false;
unsigned int axisToTest = 3;
real split;
while(axisToTest--)
{
split = EvaluateBounds(l, r, i, j, minValue, maxValue, axis);
unsigned int left_l = l;
unsigned int left_r = j;
unsigned int right_l = i;
unsigned int right_r = r;
if (l == j)
{
left_empty = true;
}
if (left_l > l || left_r < r)
{
left_doesshrik = true;
}
if (i == r)
{
right_empty = true;
}
if (right_l > l || right_r < r)
{
right_doesshrik = true;
}
if (!right_empty && !left_empty)
{
both_balanced = true;
}
if (both_balanced)
{
axisToTest = 0;
}
else
{
switch (axis)
{
case BIHNode::AXIS_X : axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : axis = BIHNode::AXIS_X; break;
}
}
}
//Build nodes
BIHNode *newnode = new BIHNode();
newnode->axis = axis;
newnode->right = newnode->left = NULL;
// NODE LEFT
{
qlaabox<real> bbox = GetNodeAABB(l, i);
newnode->planes[0] = qlmath::Max(bbox.min[axis], bbox.max[axis]); //The left node right border is the plane most right
if ((!right_empty) && ( left_doesshrik ))
{
//Create left node
vector4<real> left_value = minValue;
vector4<real> right_value = maxValue;
right_value[axis] = split;
BIHNode::AXIS new_axis;
switch (axis)
{
case BIHNode::AXIS_X : new_axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : new_axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : new_axis = BIHNode::AXIS_X; break;
}
newnode->left = CreateNode (l, j, left_value, right_value, new_axis); //Recursive call
}
else
{
//Stoprecursion with all those nodes
newnode->left = CreateLeafNode(l, i);
}
}
qlaabox<real> bbox = GetNodeAABB(j, r);
newnode->planes[1] = qlmath::Min(bbox.min[axis], bbox.max[axis]); //The right node left border is the plane most left
// NODE RIGHT
{
if ((!left_empty) && (right_doesshrik))
{
//Create left node
vector4<real> left_value = minValue;
left_value[axis] = split;
vector4<real> right_value = maxValue;
BIHNode::AXIS new_axis;
switch (axis)
{
case BIHNode::AXIS_X : new_axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : new_axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : new_axis = BIHNode::AXIS_X; break;
}
newnode->right = CreateNode(j, r, left_value, right_value, new_axis);
}
else
{
newnode->right = CreateLeafNode(j, r);
}
}
return newnode;
}
real EvaluateBounds(unsigned int l, unsigned int r, unsigned int &i, unsigned int &j, const vector4<real> &minValue, const vector4<real> maxValue, BIHNode::AXIS axis)
{
real split = (maxValue[axis] + minValue[axis]) / real(2);
SortSubVector(shapes_array, l, r, i, j, split, axis);
return split;
}
//Get the closer intersection found with the shapes in the provided node. Note that node must be a leaf, no check will be performed!
bool IntersectNode(const BIHNode* node, const ray<vector4<real>> &r, SurfacePoint &hitdesc) const
{
bool intersected = false;
for(int i = node->shapes[0]; i <= node->shapes[1]; ++i)
intersected = intersected | shapes_array[i]->Intersect(r, hitdesc);
return intersected;
}
bool IntersectTree(const BIHNode* parent, const ray<vector4<real>> &r, real tmin, real tmax, SurfacePoint &hitdesc) const
{
real left_plane = (parent->planes[0] - r.origin[parent->axis]) / r.direction[parent->axis]; //Intersection with the left plane
real right_plane = (parent->planes[1] - r.origin[parent->axis]) / r.direction[parent->axis]; //intersection with the right plane
BIHNode *near_node = NULL;
BIHNode *far_node = NULL;
real near_plane;
real far_plane;
if (r.direction[parent->axis] <= real(0))
{
near_plane = right_plane;
far_plane = left_plane;
near_node = parent->right;
far_node = parent->left;
}
else
{
near_plane = left_plane;
far_plane = right_plane;
near_node = parent->left;
far_node = parent->right;
}
bool hitfound = false;
//Check against split planes
if(near_plane > tmin)
{
if(near_node->axis == BIHNode::AXIS_NONE)
{
//Is a leaf, test against shapes
hitfound = IntersectNode(near_node, r, hitdesc);
}
else
{
//Traverse left tree
hitfound = IntersectTree(near_node, r, tmin, qlmath::Max(tmax, near_plane), hitdesc);
}
}
if(far_plane < tmax)
{
if(far_node->axis == BIHNode::AXIS_NONE)
{
//Is a leaf, test against shapes
hitfound = hitfound | IntersectNode(far_node, r, hitdesc);
}
else
{
//Traverse left tree
hitfound = hitfound | IntersectTree(far_node, r, qlmath::Min(tmin, far_plane), tmax, hitdesc);
}
}
return hitfound;
}
/*
SortSubVector sorts the primitives in the specified range in a quicksort like way. When the function returns, i and j contain the last index
of the left node and the first index of the right node. Indeces can overlap if shapes crossing both partitions are present.
*/
void SortSubVector(QLShape** vector, unsigned int l, unsigned int r, unsigned int &i, unsigned int &j, real split, BIHNode::AXIS axis)
{
//The following algorithm can be made faster by increasing i and decrasing j in two loops as long as the shapes are correctly placed
//i.e. while(CompareShape(vector[i], split, axis) < 0) ++i;
//while(CompareShape(vector[j], split, axis) > 0) --j;
i = l;
j = r;
unsigned int bothi = l + 1; //Indicates the index to swap for the next both shape. Will be incremented with each left and both
do
{
qlaabox<real> ab = vector[i]->GetBoundingBox();
int res = CompareShape(vector[i], split, axis);
if(res > 0)
{
QLShape* tmp = vector[i];
vector[i] = vector[j];
vector[j] = tmp;
--j;
}
else if(res == 0)
{
if(bothi > r)
break;
QLShape* tmp = vector[bothi];
vector[bothi] = vector[i];
vector[i] = tmp;
++bothi;
}
else
{
++i;
++bothi;
}
}while(i < j);
if(j < r) ++j;
//Change i and j to include 'both' shapes
while(CompareShape(vector[i], split, axis) == 0 && i < r) ++i;
while(CompareShape(vector[j], split, axis) == 0 && j > l) --j;
}
/*
GetNodeAABB returns the bounding box of all the shapes in the subvector specified
*/
const qlaabox<real> GetNodeAABB(unsigned int l, unsigned int r) const
{
qlaabox<real> aabb;
for(int i = l; i <= r; ++i)
aabb = aabb.Union(shapes_array[i]->GetBoundingBox());
return aabb;
}
/*
CompareShape checks a Shape against the split plane: it returns -1 if the shape bounding box completely falls left to the plane, 1 if it falls
completely right to the plane and 0 if it intersect the plane.
*/
int CompareShape(QLShape* shape, real split, BIHNode::AXIS axis)
{
qlaabox<real> aabb = shape->GetBoundingBox();
real max = Max(aabb.max[axis],aabb.min[axis]);
real min = Min(aabb.max[axis],aabb.min[axis]);
return (min > split) ? 1 : (max < split) ? -1 : 0;
}
};
(L) [2009/01/23] [cignox1] [Help with my BIH] Wayback!Ok, I've found several errors in my code (both when building and when traversing the tree). I've solved the polys missing problem among others. As far as I can tell, my tree is highly unbalanced: most of the leaveas are built by only 1 shape (and I suspect that my building code still can't distinguish empty leaves from 1 shape ones), and there are a few nodes with more than 500 primitives. This is the new code for the tree build (I hypotize that the sorter works)
Code: [LINK # Select all] BIHNode* CreateLeafNode(unsigned int l, unsigned int r)
{
std::cout<<r-l<<std::endl;
BIHNode *newnode = new BIHNode();
newnode->left = NULL;
newnode->right = NULL;
newnode->shapes[0] = l;
newnode->shapes[1] = r;
newnode->axis = BIHNode::AXIS_NONE;
return newnode;
}
BIHNode* CreateNode(unsigned int l, unsigned int r, const vector4<real> &minValue, const vector4<real> &maxValue, BIHNode::AXIS axis)
{
if(shapes.size() == 0)
return NULL;
if(l == r)
{
return CreateLeafNode(l, r);
}
unsigned int i;
unsigned int j;
bool left_empty = false;
bool right_empty = false;
bool left_doesshrik = false;
bool right_doesshrik = false;
bool both_balanced = false;
unsigned int axisToTest = 3;
real split;
while(axisToTest--)
{
split = EvaluateBounds(l, r, i, j, minValue, maxValue, axis);
unsigned int left_l = l;
unsigned int left_r = j;
unsigned int right_l = i;
unsigned int right_r = r;
if (l == j)
{
left_empty = true;
}
if (left_l > l || left_r < r)
{
left_doesshrik = true;
}
if (i == r)
{
right_empty = true;
}
if (right_l > l || right_r < r)
{
right_doesshrik = true;
}
if (!right_empty && !left_empty)
{
both_balanced = true;
}
if (both_balanced)
{
axisToTest = 0;
}
else
{
switch (axis)
{
case BIHNode::AXIS_X : axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : axis = BIHNode::AXIS_X; break;
}
}
}
//Build nodes
BIHNode *newnode = new BIHNode();
newnode->axis = axis;
newnode->right = newnode->left = NULL;
// NODE LEFT
{
qlaabox<real> bbox = GetNodeAABB(l, j);
newnode->planes[0] = qlmath::Max(bbox.min[axis], bbox.max[axis]); //The left node right border is the plane most right
if ((!right_empty) && ( left_doesshrik ))
{
//Create left node
vector4<real> left_value = minValue;
vector4<real> right_value = maxValue;
right_value[axis] = split;
BIHNode::AXIS new_axis;
switch (axis)
{
case BIHNode::AXIS_X : new_axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : new_axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : new_axis = BIHNode::AXIS_X; break;
}
newnode->left = CreateNode (l, j, left_value, right_value, new_axis); //Recursive call
}
else
{
//Stop recursion with all those nodes
newnode->left = CreateLeafNode(l, j);
}
}
qlaabox<real> bbox = GetNodeAABB(i, r);
newnode->planes[1] = qlmath::Min(bbox.min[axis], bbox.max[axis]); //The right node left border is the plane most left
// NODE RIGHT
{
if ((!left_empty) && (right_doesshrik))
{
//Create left node
vector4<real> left_value = minValue;
left_value[axis] = split;
vector4<real> right_value = maxValue;
BIHNode::AXIS new_axis;
switch (axis)
{
case BIHNode::AXIS_X : new_axis = BIHNode::AXIS_Y; break;
case BIHNode::AXIS_Y : new_axis = BIHNode::AXIS_Z; break;
case BIHNode::AXIS_Z : new_axis = BIHNode::AXIS_X; break;
}
newnode->right = CreateNode(i, r, left_value, right_value, new_axis);
}
else
{
//Stop recursion with all those nodes
newnode->right = CreateLeafNode(i, r);
}
}
return newnode;
}
Does someone spot anything wrong?