   Efficient Ray-OBB intersection with distance?
  I'm trying to implement a ray-OBB intersection test. Apart from only telling whether there's an intersection, I also need to find the distance to the closest point on the box that the ray intersects.I've already implemented a ray-triangle test which returns distance to intersection. Technically I should be able to create a ray-OBB test by constructing the coordinates of all triangles I can decompose the facets of the OBB into, and perform 12 ray-triangle tests and return failure or the closest intersection distance, but that seems very inefficient.Is there any more efficient method for testing ray-OBB?
Quote:Is there any more efficient method for testing ray-OBB?Yup:template <class T> bool Math3D<T>::IntersectLineOBB(    const Vector3<T>& O, // Line origin    const Vector3<T>& D, // Line direction    const Vector3<T>& C, // Box center    const Vector3<T> A[], // Box axes    const Vector3<T>& e, // Box extents    T t[], // On output, parametric points of intersection    T epsilon) // Tolerance for parallel test{    int parallel = 0;    bool found = false;    T DA[3];    T dA[3];    Vector3<T> d = C - O;    for (int i = 0; i < 3; ++i)    {   DA = D.Dot(A);   dA = d.Dot(A);   if (Math<T>::Fabs(DA) < epsilon)  parallel |= 1 << i;   else   {  T es = (DA > (T)0.0) ? e : -e;  T invDA = (T)1.0 / DA;  if (!found)  { t[0] = (dA - es) * invDA; t[1] = (dA + es) * invDA; found = true;  }  else  { T s = (dA - es) * invDA; if (s > t[0])t[0] = s; s = (dA + es) * invDA; if (s < t[1])t[1] = s; if (t[0] > t[1])return false;  }   }    }   if (parallel)   for (int i = 0; i < 3; ++i)  if (parallel & (1 << i)) if (Math<T>::Fabs(dA - t[0] * DA) > e || Math<T>::Fabs(dA - t[1] * DA) > e)return false;    return true;}This is old code (I'd probably arrange it differently now), but it should give you the general idea.   ;  Thanks, looks promising! I'll plug it into my test app when I get home!;  @jyk: That sort of answer seems to me like the kind that isn't beneficial for learning.@jyk & O.P.: I don't know how exactly your (jyk's) algorithm works (I've not yet taken Algorithm Analysis or whatever that course at my college is called), but I'd think you could do something like this:Pseudocode for ray-rect intersection, the return value should be something like a float, the distance along the ray from the origin of that ray:create variable for minimum distanceoptional: create variable for first rect hitfor each rect:    where does the ray intersect that plane?    what is the distance along each of the rect's axes to that point (normalize to max 1)    if distance a is between 0 and 1   if distance b is between 0 and 1  if distance to point of intersection is less than current minimum distance minimum distance = distance to point of intersection if using first rect hit variable: store this rect in that variable return or store in reference/pointer parameter the relevant output (minimum distance, closest rectangle, or both)This requires half the calculations of 12 ray-tri tests. You can probably even optimize the part "what is the distance ..." by taking into account the fact that the two axes are perpendicular, something you can't always do with tris.   ;  I think jyk's code treats the OBB as an intersection of slabs (the space between two parallel planes some fixed distance apart). The OBB is made of the intersection of three slabs, and the code computes the location where the ray enters and exits each slab, keeping track of the furthest entry point and the closest exit point (t[0] and t[1]). If the ray intersects the OBB then the furthest entry point must be closer than the closest exit point, and those points are where the ray intersects the OBB. If the closest exit point is closer than the furthest entry point, then the ray never passes through the intersection of all three slabs and there is no collision.It's a complex algorithm, but it performs some very efficient calculations and is capable of terminating early when it detects that there is no collision. It's also tricky because it needs to handle the special case of the ray being parallel or nearly parallel to one or two of the slabs, in which case the ray never enters or exits the slab and a different test is done to determine if the entry and exit points are inside of the slab (I guess for numeric robustness).   ;Quote:@jyk: That sort of answer seems to me like the kind that isn't beneficial for learning.mate honestly, who gives a monkeys, its not school. standing on the shoulders etcactually the code looks very good (havent tested it though)   ;  There's one other thing you can do to speed things up in the case where enough of the rays miss your box. Wrap a sphere round the cube (or ideally round the actual object) and test for intersection of that first. You just need to store an extra float for the radius of the sphere as it can share the centre point with the cube.   ;Quote:Original post by Aken H Bosch@jyk: That sort of answer seems to me like the kind that isn't beneficial for learning.I think I was pressed for time when I posted that; I basically had the choice of posting it without an explanation, or not posting it at all. I chose to post it.I could have done better, I suppose, but I don't think it's that big a deal (if you look at my post history, I think you'll see that I generally do a pretty good job of backing up any posted code or pseudocode with detailed, clear explanations).I admit though, I could have at least made mention of the fact that the algorithm in question is a slab-based clipping algorithm (as described very clearly by Vorpy, above). I also could have recommended that the OP search the archives here for further information (as this particular algorithm has been covered in considerable detail many, many times on these forums).I'll try to do better next time.   