Hi. To improve the performance of my raytracer, I decided to use Uniform Space Partitioning. Basically, I divide the world into 3D boxes, and put objects (**Surface**s) inside them. When tracing a ray, I check first with the boxes and if there is a hit, I check with the Surfaces it contains.

The problem is, from 11 seconds I dropped to only 8 seconds. Another thing I noticed is that when the world is divided into more boxes, it takes more time to render. So this means there is a problem with my AABB-Ray collision function.

bool intersects(const ref Ray r) const { Vector3 n = void, // normal v = void, u = void; // vectors float t = void; // plane 0 (front) v = Vector3(max.x, min.y, min.z) - min; u = Vector3(min.x, max.y, min.z) - min; n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t0 = ", t); if( t > 0 ) writeln("plane 0 intersected"); else writeln("plane 0 not intersected");++/ Vector3 temp = min - r.e; Vector3 p = r.e + r.d * dot(temp, n) / t; //writeln("p0 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 0\n"); return true; } /++else writeln("NO 0\n");++/ // plane 1 (right) v = Vector3(max.x, max.y, min.z) - Vector3(max.x, min.y, min.z); u = Vector3(max.x, min.y, max.z) - Vector3(max.x, min.y, min.z); n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t1 = ", t); if( t > 0 ) writeln("plane 1 intersected"); else writeln("plane 1 not intersected");++/ temp = Vector3(max.x, min.y, min.z) - r.e; p = r.e + r.d * dot(temp, n) / t; //writeln("p1 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 1\n"); return true; } /++else writeln("NO 1\n");++/ // plane 2 (left) v = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z); u = Vector3(min.x, max.y, min.z) - Vector3(min.x, min.y, min.z); n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t2 = ", t); if( t > 0 ) writeln("plane 2 intersected"); else writeln("plane 2 not intersected");++/ temp = Vector3(min.x, min.y, min.z) - r.e; p = r.e + r.d * dot(temp, n) / t; //writeln("p2 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 2\n"); return true; } /++else writeln("NO 2\n");++/ // plane 3 (back) v = Vector3(max.x, min.y, max.z) - Vector3(min.x, min.y, max.z); u = Vector3(min.x, max.y, max.z) - Vector3(min.x, min.y, max.z); n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t3 = ", t); if( t > 0 ) writeln("plane 3 intersected"); else writeln("plane 3 not intersected");++/ temp = Vector3(min.x, min.y, max.z) - r.e; p = r.e + r.d * dot(temp, n) / t; //writeln("p3 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 3\n"); return true; } /++else writeln("NO 3\n");++/ // plane 4 (top) v = Vector3(min.x, max.y, max.z) - Vector3(min.x, max.y, min.z); u = Vector3(max.x, max.y, min.z) - Vector3(min.x, max.y, min.z); n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t4 = ", t); if( t > 0 ) writeln("plane 4 intersected"); else writeln("plane 4 not intersected");++/ temp = Vector3(min.x, max.y, min.z) - r.e; p = r.e + r.d * dot(temp, n) / t; //writeln("p4 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 4\n"); return true; } else /++writeln("NO 4\n");++/ // plane 5 (bottom) v = Vector3(max.x, min.y, min.z) - Vector3(min.x, min.y, min.z); u = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z); n = cross(v, u); n.normalize(); t = dot(r.d, n); /++writeln("t5 = ", t); if( t > 0 ) writeln("plane 5 intersected"); else writeln("plane 5 not intersected");++/ temp = Vector3(min.x, min.y, min.z) - r.e; p = r.e + r.d * dot(temp, n) / t; //writeln("p5 = ", p); if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z ) { //writeln("YES 5\n"); return true; } /++else writeln("NO 5\n");++/ return false; }

What I do is check all six planes and then if the hit point is inside the boundaries. I know this is the worst method. What's a better way to do this?

Please, if you suggest something, provide an explanation why it works, as that's the important thing here - I want to learn this stuff.

Thank you