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];
    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:

correctly clipped AABB

( Source of the image here )

will be incorrectly evaluated as this:

wrong case

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?

  • $\begingroup$ Are you sure that the algorithm needs a tight exact AABB rather than just being satisfied with an approximation of triangles by boxes? I only gave it a short glimpse, but it seem that function is only used for finding the optimal splitting plane. It might not necessarily require a perfectly tight triangle box for that when the worst that could happen would just be a less than optimal splitting plane. $\endgroup$ Commented Oct 1, 2017 at 16:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.