2
\$\begingroup\$

How do I check which bounding boxes (of different types) a ray, sent from the camera through the mouse-click coordinates, intersects with first in Java (and where)? I have arrays (box_X, box_Y, box_Z, box_X2, box_Y2, box_Z2) that store the coordinates and size of each box.

I don't understand very complex math (matrices, definitely nope). I am doing this from scratch so that I can better understand it and because there is a certain priority I want to use when picking objects (UI > Entities > Items > Objects > Terrain).

Thank you for your help!

Edit #1: So, I finished the code. Pasted it below so you guys can point out obvious errors in it for me. Or possibly, ways to do this easier. I have a feeling that there's something I'm missing, so...

private static int[] getIntersect(Vector3f ray) {       
    int coords[] = new int[4];
    boolean planes[] = new boolean[6];
    Vector3f norm = null;

    Vector3f origin = new Vector3f(Disp.camX, Disp.camY, Disp.camZ);

    // Check which direction the ray is going.
    for (int plane = 0; plane < 6; plane++) {
        if (plane == posxy) {
            norm = new Vector3f(0f, 0f, -1f);
        } else if (plane == posxz) {
            norm = new Vector3f(0f, -1f, 0f);
        } else if (plane == posyz) {
            norm = new Vector3f(-1f, 0f, 0f);
        } else if (plane == negxy) {
            norm = new Vector3f(0f, 0f, 1f);
        } else if (plane == negxz) {
            norm = new Vector3f(0f, 1f, 0f);
        } else if (plane == negyz) {
            norm = new Vector3f(1f, 0f, 0f);
        }

        if (Vector3f.dot(ray, norm) < 0) {
            planes[plane] = true;
        }
    }

    norm = null;
    boolean solved;

    // Calculate intersections

    // First, choose the type of object to find collisions with.
    for (int type = 0; type < 5; type++) {
        solved = false;
        // Next, loop through layers.
        for (int dist = 0; dist < 70; dist++) {
            int pos[] = new int[3];
            float t = 0f;

            // Check for intersections on the planes
            for (int plane = 0; plane < 6; dist++) {

                // Skips calculation if the plane is not in the right direction.
                if (planes[plane] == true) {
                    int axis = 0;

                    // Set the normal to be correct.
                    if (plane == posxy ) {
                        norm = new Vector3f(0f, 0f, -1f);
                        axis = 2;
                    } else if (plane == posxz) {
                        norm = new Vector3f(0f, -1f, 0f);
                        axis = 1;
                    } else if (plane == posyz) {
                        norm = new Vector3f(-1f, 0f, 0f);
                        axis = 0;
                    } else if (plane == negxy) {
                        norm = new Vector3f(0f, 0f, 1f);
                        axis = 2;
                    } else if (plane == negxz) {
                        norm = new Vector3f(0f, 1f, 0f);
                        axis = 1;
                    } else if (plane == negyz) {
                        norm = new Vector3f(1f, 0f, 0f);
                        axis = 0;
                    }

                    // Calculate the point of intersection
                    t = ( dist - Vector3f.dot(origin, norm) ) / Vector3f.dot(ray, norm);
                    ray.setX(t * ray.getX());
                    ray.setY(t * ray.getY());
                    ray.setZ(t * ray.getZ());
                    pos[0] = (int) ray.getX(); 
                    pos[1] = (int) ray.getY();
                    pos[2] = (int) ray.getZ();

                    // Check if there is a collidable item of the type in the coordinates. If is, save the type and coordinates, then break out of the loop.
                    if (isCollidable(pos, type)) {
                        coords[0] = pos[0];
                        coords[1] = pos[1];
                        coords[2] = pos[2];
                        coords[3] = type;
                        solved = true;

                        break;
                    }
                }
            }

            if (solved) {
                break;
            }

        }
        if (solved) {
            break;
        }
    }

    return coords;
}

Edit #2: I actually found something myself. That t needs to be converted to coordinates via p(t)... And it's corrected.

\$\endgroup\$
2
\$\begingroup\$

We'll, to do that your going to need a basic understanding of Vectors. I'm not going to be able to provide a decent explanation of those, but there should be sources online for you so I'll leave you to your own devices there.

But first, in the fallowing equations:

  1. Bold face text represents vectors (x, y, z, w)
  2. non-bold face text represents scalars

So, on to the math, first we need to cover the intersection of a plane:

Consider a ray defined as: p(t) = p.origin + t d

where p(t) is a new point given the parametric distance t, p.origin is where the ray starts, d is the vector representing the ray's direction, and t is a parametric distance along the ray.

Now consider a plane defined as: p . n = d

Where p is a point on the plane, n is the planes normal, d is the offset from the origin (much like the c in y = mx + c), and the '.' is a dot product. Note: The p in the equation of the plane is not the same as the rays p, but they can be substituted.

So, we're looking for the point on the ray is a point on the plane. if an arbitrary point on the ray is p(t), and the p is an arbitrary point on a plane, then we are looking for:

p(t) . n = d

p(t) could be found if we knew what t was. so if we substitute the p(t) for "p.origin + t d", you get:

(p.origin + t d) . n = d

Which becomes:

t = ( d - (p.origin . n) ) / ( d . n )

If there is no intersection, then "d . n" will result in 0. So that's where you check if you want to see if they actually intersect.

so then your intersection point is, p(t), that's it. You can find t with the above equation. And that's how you find the intersecting point of a plane.

So, now we move to box. It's really just 6 different planes, right? Each planes normal goes along one of the axis (x+, y+, z+, x-, y-, z-), and you can find a corner point for each side, so you have the planes all-ready. That mean's, you can test each plane, and wherever t is the smallest is the closest intersection.

Once you have where the ray intersects with the AABB, you can test to see if that "intersection" point on the plane is actually inside or on the AABB. ( eg. p(t).x <= AABB.max.x and p(t).x >= AABB.min.x ) If that checks out for the X, Y, and Z, axis on any given plane, you have an intersection.

So, that's how you find if an cube intersects a ray, and where it intersects. To see if one AABB intersection is closer than another, you can compare 't' in each intersection. The closer t is to zero, the closer the AABB.

\$\endgroup\$
  • \$\begingroup\$ This is what I was looking for, thank you. Now I just have to review it again when I'm fully awake. But, for a cube intersection, don't I only need to check the three camera-facing sides of each cube? \$\endgroup\$ – user39208 Dec 10 '13 at 23:35
  • \$\begingroup\$ If your ray-casting from the camera, then yes. I think d . n would be a good indicator for that. The sides of the cube that are facing the camera should have a normal that goes in the opposite direction of the ray, which will give you a negative result when checking d . n \$\endgroup\$ – Wolfgang Skyler Dec 11 '13 at 0:54
  • \$\begingroup\$ Question: is the d in p . n = d the shortest distance from the plane to the origin? That is, in this case, the offset along the axis. \$\endgroup\$ – user39208 Dec 11 '13 at 12:24
  • \$\begingroup\$ Yes. It could also be described as the distance along n to the plane. \$\endgroup\$ – Wolfgang Skyler Dec 11 '13 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy