How would I find all the cubes a ray intersects in a 3d grid?

I need to cast a ray from the ground to the sun and want to find if an object is in the shadow. I plan on doing this by tracing a line from a ground开发者_JAVA百科 cube to the sun and finding if any object is in the way. However I'm not familiar with the math to find all the cubes that a line intersects so I can test if they are filled. Can anyone shed some light on this?

You want to perform a (or in this case, lots of) ray-box intersections. An example algorithm is here: http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm

Alternatively, if your cubes are all axis-aligned and tightly-packed, you might want to try a 3D version of Bresenham's algorithm (used for drawing lines through pixels).

The brute force way is to check each and every cube is on your line. There's some non-trivial geometry involved IIRC.

Ah. Googling "line cube collision" turned up quite a few hits. This one looks quite promising.

http://www.devmaster.net/forums/archive/index.php/t-371.html

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 ...

It goes on in that vein for several more paragraphs.

One thing you can do that might speed things along a bit is to determine how close the cube is to the line in question. More math to find the nearest point on a line from a given point (the center of the cube).

http://www.gamedev.net/community/forums/topic.asp?topic_id=185204

You needn't go into all the surface tests until you know whether or not there will be collisions at all.

Quick collision detection trick: The distance between two points in 2d: sqrt (x^2 + y^2). Basic. But if you just want to know the RELATIVE distance between two things, you can skip the SQRT.

if ((x1^2 + y1^2) > (x2^2 + y2^2)) { //x1, y1 is longer than x2, y2. }

Square roots are expensive, and avoiding them is A Good Thing, particularly in inner loops like collision detection.

Hey, here's a thought. Build a plane that is an extension of your line (say straight vertical, y's never change... whatever). Take the dot product of all the cube's points. If all of them are on one side or the other (all positive or all negative), the cube isn't "cut" by the plane and cant therefore intersect the line.

Dot products are cheap.

Now build another plane, perpendicular to the first one, and get your dot products again. If your cube is also cut by this second plane... crud, it's still possible to be cut twice in this case and not be on the line.

The first and only plane needs to be perpendicular to the line between the center of the cube and the nearest point on the line (cross product time). If THAT plane cuts the cube (dot products that are both positive and negative for your cube's vertexes) then the cube intersects the line.