8 replies to this topic

[cdgray]

What's the quickest way to test if a ray goes through a cube (or stops in the middle somewhere)? I was thinking ok just testing if the ray intersects one of the cube's sides. Anything better? Thanks.

Well, that was a waste of 2 minutes of my life. Now I have to code faster to get 'em back...

[Julio]

well, the easiest method would just to use some sort of bounding sphere collision detection. if you test a side (a ray-plane intersection) you would have to take into account rotations and such. ray-plane intersection itself isn't too difficult, but I think bounding sphere might be your best bet.

[Smokey97]

Be more specific, do you want to know if a ray intersects a cube or a box? is the cube/box axis aligned or not? all these things matter if you want the fastest intersection algorithm.

[Ed Mack]

Basically, it goes like this (I'm bound to make a mistake):

Take the 8 vertexes that make up the cube's corners. We will work in quads for the working of it out.

The first task is to work out all 6 face normals, and store them in an array somewhere. To work out the normal you must use the cross product of two of the vectors parralel to the face. From that normal you can use the plane equation to make sure that the end point of the ray is outside (result > 0) all of the planes.

Ok, some math:

The four vertexes (x, y, z) that make up a face ABCD are used to make two vectors.
To get these two vectors, it's a simple matter of B-A and C-A (that means B.x - A.x, B.y - A.y ect..)

We have our two parallel vectors, A and B I'll call them for clarity

Now, take these two vectors and work out the normal (the order of this whole thing is important, which means I probably got it the wrong way around :) If so, the normal points inside instead, not life threatening) using the cross product as follows:

c.x = a.y*b.z - a.z*b.y;
c.y = a.z*b.x - a.x*b.z;
c.z = a.x*b.y - a.y*b.x;

C is our normal. This can be used for lighting and so on. All these values can be stored if you're keeping the plane the same.

The next thing is to find out the plane's distance from the origin, which we will put back into the plane equation later on.

The plane equation is

result = Ax + By + Cz + D

Now I'll explain the bits of it. result is the distance the point x, y, z, is from the plane. It is 0 if the point is on it, a negitive number if it is behind the plane and positive if infront.

A, B and C are the x, y and z of the plane's normal, as it would be far too confusing to use x, y and z :) As I said x,y and z is a point. D is the distance our plane is from the origin (as the normal vector doesn't show this). Note, a plane is infinite in size and has no bounderies. Just a flat plane surface.

Anyway, we need to know D so we can test points. So, rearrange the formula like so:

-D = Ax + By + Cz - result
D = -(Ax + By + Cz) + result

We know the normal, so that's sorted. D is what we will try to find. But, how do we know the result? We know a point on the plane gives a result of 0, so once of the vertexes we used to get the normal will do fine for a point on the plane, and then result no longer matters as it is 0.

So, do this:

vertex is some one that we used earlier. Normal, well I hope you have that :)

D = -(Normal.x * vertex.x + Normal.y * vertex.y + Normal.z * vertex.z)

Keep D too now.

This is a the useful bit now, finding out if our ray has went into the plane. Now, this is a simplier version of testing a whole line. This is only testing a point, so you may want to test both points or something dependinh upon your engine. Note that your ray, if moving very fast could "skip" the cube.

Anyway, here's our test for our arbitary point:

result = (Normal.x * Ray.x + Normal.y * Ray.y + Normal.z * Ray.z + D)

Do this for all 6 faces of the cube, and if ALL of the planes return that the point is beneth them (a negitive result), then the point is definately inside the cube, thus at least part of the ray is inside. You could try the start point of the ray aswell, and make sure it is outside of the cube (at least one plane returns > 0) and if so the ray definately intersects the cube).

If the cube doesn't move around, you should pre-calculate the Normal and D. If it moves but doesn't rotate, then you could precalculate the normal and work out D at run time.

I hope this is useful, near correct and not a stupid approach :)

[Ed Mack]

Oh, and as smokey said if your cubes are aligned to all 3 axiises then you can just use simple < statements. I hope I spelt that right as a big green corrupted looking box has appreaded in my screen after starting a second X with weird config file :)

[Dia]

Hey Ed Mack!

Very nice detailed post. I'm sure that was very helpful for cdgray. That could be made into a small article, btw.

[Ed Mack]

Hi, thanks :) I'm currently trying to learn a good bit of colision detection math, so I thought I may as well reguritate it in a way I would have liked it. Once I get some demos done using this stuff, I'll make a short (or maybe not so by then) article on collision, and post it on this nice central resource.

Anyway, I'm off to think how reaction forces will fit into my scheme of things.

[davepermen]

for bounding spheres see here

and, ed, how about writing the actual ray-box intersection code and add it to the Algorithm & Code Snippets? would be useful i think..

[frankhevans]

Ed Mack,

Been struggling with the ray/plane issue for several days now. Thanx for the best explanation I've ever read!!! Lots of material out there, but you nailed it!!!


Bookmarking this explanation is insufficient...
Saving it to my local hardrive is insufficient...
Printing it to paper is insufficient...

It must be forged into a colossal adamantiam monument, and preserved so that no matter what happens, if civilization ends, future generations of humans (or perhaps the cockroaches) will retain this knowledge...

Were it anatomically possible I would have your baby... hehe...

seriously, thanks....