3D ray-box intersection (right rectangular cuboid)

This is a class i made after looking for some fine looking ray-box collision in 3d code and not finding any.
Or just some 2d code that could be nicely extended to 3d, but i don’t really like Tmin and Tmax.
So far it looks foolproof to me. Please report bugs to me in PM after you’ve verified they’re not yours.

Yes I’m guilty of testing all six faces. It doesn’t care how long the ray is just whether if extended long enough that it would hit the boundaries and will accurately return the hit position even when the origin is inside the bounds. No need to normalize any rays. The hit position isn’t relative to anything and the test return type is boolean.
Here’s an example in use:

RlPWjK_BoTQ

Overall it’s used like this:

Boxen box=new Boxen(4,6,8,5,10,0);//(4,6,8) is pointA. (5,10,0) is pointB. They only have to be opposite corners.
box.pointA(0,0,0);//you can change the corners
box.pointB(-1,-1,-1);//at any time to any size
if(box.test(0,0,0,6,2,5)){//(0,0,0) is ray origin. (6,2,5) is ray direction.
	distance(0,0,0,box.getx(),box.gety(),box.getz())//doing something with the hit point x,y,z
}

Finally the bacon

public class Boxen{
	double ax,ay,az;double x0,y0,z0;double x1,y1,z1;
	public Boxen(double x,double y,double z,double a,double b,double c){
		x0=x;y0=y;z0=z;x1=a;y1=b;z1=c;
	}
	public void pointA(double x,double y,double z){x0=x;y0=y;z0=z;}
	public void pointB(double x,double y,double z){x1=x;y1=y;z1=z;}
	public boolean test(double a,double b,double c,double x,double y,double z){
		double x0=this.x0-a,y0=this.y0-b,z0=this.z0-c,x1=this.x1-a,y1=this.y1-b,z1=this.z1-c,
		Adx,Ady,Adz,var,xx=Double.MAX_VALUE,tt;boolean hit=false;x-=a;y-=b;z-=c;//.000000000000002 the original difference
		if(x0*x>0){
			var=x0/x;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adz<z0&&Adz>z1)||(Adz>z0&&Adz<z1))&&((Ady<y0&&Ady>y1)||(Ady>y0&&Ady<y1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		if(x1*x>0){
			var=x1/x;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adz<z0&&Adz>z1)||(Adz>z0&&Adz<z1))&&((Ady<y0&&Ady>y1)||(Ady>y0&&Ady<y1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		if(z0*z>0){
			var=z0/z;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adx<x0&&Adx>x1)||(Adx>x0&&Adx<x1))&&((Ady<y0&&Ady>y1)||(Ady>y0&&Ady<y1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		if(z1*z>0){
			var=z1/z;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adx<x0&&Adx>x1)||(Adx>x0&&Adx<x1))&&((Ady<y0&&Ady>y1)||(Ady>y0&&Ady<y1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		if(y0*y>0){
			var=y0/y;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adx<x0&&Adx>x1)||(Adx>x0&&Adx<x1))&&((Adz<z0&&Adz>z1)||(Adz>z0&&Adz<z1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		if(y1*y>0){
			var=y1/y;Adx=x*var;Ady=y*var;Adz=z*var;
			if(((Adx<x0&&Adx>x1)||(Adx>x0&&Adx<x1))&&((Adz<z0&&Adz>z1)||(Adz>z0&&Adz<z1))){
				tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
			}
		}
		return hit;
	}
	private static double sdist(double x1,double y1,double z1){return StrictMath.sqrt(Math.pow(x1,2)+Math.pow(y1,2)+Math.pow(z1,2));}
	public double getx(){return ax;}public double gety(){return ay;}public double getz(){return az;}
}

There are a bit too many magic numbers and square roots and Math.pow’s in there, I feel.
What’s wrong with the classic min/max algorithm? If you want to also just use opposite corners, then:


public static boolean testOppositeCorners(
        float aX, float aY, float aZ,
        float bX, float bY, float bZ,
        float originX, float originY, float originZ,
        float dirX, float dirY, float dirZ) {
    float tMinX = (aX - originX) / dirX;
    float tMinY = (aY - originY) / dirY;
    float tMinZ = (aZ - originZ) / dirZ;
    float tMaxX = (bX - originX) / dirX;
    float tMaxY = (bY - originY) / dirY;
    float tMaxZ = (bZ - originZ) / dirZ;
    float t1X = Math.min(tMinX, tMaxX);
    float t1Y = Math.min(tMinY, tMaxY);
    float t1Z = Math.min(tMinZ, tMaxZ);
    float t2X = Math.max(tMinX, tMaxX);
    float t2Y = Math.max(tMinY, tMaxY);
    float t2Z = Math.max(tMinZ, tMaxZ);
    float tNear = Math.max(Math.max(t1X, t1Y), t1Z);
    float tFar = Math.min(Math.min(t2X, t2Y), t2Z);
    return tNear < tFar && tFar >= 0.0f;
}

This is the classic min/max algorithm, but since the first it does is to apply Math.min/Math.max to the (originally) min/max input coordinates, we don’t actually need to give the actual min/max coordinates to this algorithm. Turns out it’ll also work with any corner coordinates.

My computer has exploded. Search for ray slope.

You mean this: http://www.cg.cs.tu-bs.de/media/publications/fast-rayaxis-aligned-bounding-box-overlap-tests-using-ray-slopes.pdf ?
That looks really nice! Thanks for mentioning. Of course, how come no one else came up with a solution that uses precomputation to make subsequent ray/box tests faster.

You’re right about Math.pow. sdist(just a distance test) should only execute at most 4 times in this instance for two faces. i can replace
if(sdist(Adx,Ady,Adz)<xx){xx=sdist(Adx,Ady,Adz);ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
with
tt=sdist(Adx,Ady,Adz);if(tt<xx){xx=tt;ax=Adx+a;ay=Ady+b;az=Adz+c;hit=true;}
Now it may only execute twice. Come to think of it i’m going to make another optimization by removing the redundant if(value>+.00000000000002) statements. They were safeguards but i’m sure it’s fine.
Finalizing main post.
The code you’ve showed does look coherent enough for me. i do like :persecutioncomplex:

There are a fair number of methods similar to the ray slope paper. Classifing a ray by direction has been around forever.

Those TU Braunschweig people have a bug in their paper…

In code listing at page 7 line 18 and 19 it should be:


18: r->s_xz = r->k * r->ii;
19: r->s_zx = r->i * r->ik;

Then it is also consistent with how all other previous values were computed. And with that fix this method then also produces the exact same intersection results as does the min/max algorithm for a very large number of random rays and axis-aligned boxes.
Let’s see whether it is faster.

Okay, it is faster. Here is a preliminary implementation using MethodHandle to dispatch to the different ray direction cases:
http://pastebin.java-gaming.org/395d61f094f16