I'm currently trying to implement a fast algorithm for KD-Tree construction using SAH, as described in this paper:
On building fast KD-trees for ray tracing, and on doing that in O(N log N)
I found one already working implementation by Miguel Granados and Richard Socher from the University of Saarland (even though this code does not implement the final O(N log N) algorithm, but a slightly slower O(N log^2 N), which is also described in the paper). The implementation can be found here.
However, I'm not entirely certain their implementation is correct. What makes me particularly unsure is this part:
// get primitives's clipped bounding box
Box clipTriangleToBox(Primitive* t, const Box& V) const {
Box b = t->CalcBounds(); // calculates the triangle's AABB
for(int k=0; k<3; k++) {
if(V.min[k] > b.min[k])
b.min[k] = V.min[k];
if(V.max[k] < b.max[k])
b.max[k] = V.max[k];
}
assert(V.contains(b));
return b;
}
This code should return a conservative Axis-Aligned Bounding Box of the given triangle, which is clipped by the given box/voxel, but I'm certain this code will not compute these AABBs correctly, since this case, which is correctly evaluated:
( Source of the image here )
will be incorrectly evaluated as this:
The output seems to be only a conjunction of AABBs, rather than a real conservative AABB. This, of course, makes the algorithm either crash at deeper levels of KD-Tree construction (with small voxels compared to sizes of the scene triangles) or, in most cases, halt prematurely. I've been trying to find an algorithm that evaluates these cases correctly, but I do not seem to be successful.
Are my assumptions correct? And if yes, would anyone happen to know of an algorithm which would correctly evaluate the conservative AABB, given the triangle and the voxel?
