Search code examples
mathcollision-detection

Testing Axis Aligned Boxes (AAB) in frustum intersection

I read this tutorial for aabb-plane test, and I'm having trouble understanding the "optimized" aabb-plane test described.

Under "Geometric Approach - Testing Boxes II", I understand everything until this line:

Assume a AAB that has its components x,y,and z varying between xmin and xmax; ymin and ymax; and zmin and zmax. The components of the positive vertex p are selected as follows: ...

I also don't get the code that comes afterwards. My AABB objects are defined by their minVertex, maxVertex parameters.

Can you explain me what did the author mean?

Solution

  • Consider the following picture where the diagonal PS is (supposedly) parallel to the normal vector (BTW, this is what the tutorial calls the AAB case). This picture represents the 2D version of the problem where the idea is easier to explain and understand.

    2D version of the problem

    The p-vertex is, by definition, the one that is further aligned with the direction of the normal. This means that you have to decide which one of the following four vectors is further aligned with the normal:

    R - Q, Q - R, P - S or S - P                        (1)

    In this case the answer is S - P, which means that S is the p-vertex and P the n-vertex. But the problem is how to detect this programmatically.

    Well, the dot product between two vectors measures the projection of one of them onto the other, so the problem can be restated as: which of the vectors in (1) has the maximum dot product with the normal (xn, yn)?

    Here are the four dot products:

    (xn, yn).(R - Q) = xn(x1 - x2) + yn(y1 - y2)
(xn, yn).(Q - R) = xn(x2 - x1) + yn(y2 - y1)
(xn, yn).(P - S) = xn(x1 - x2) + yn(y2 - y1)
(xn, yn).(S - P) = xn(x2 - x1) + yn(y1 - y2)

    So, the one we are looking for is the one that makes both terms of the sum positive, this is

    • if xn > 0 select x2 - x1 (>0) otherwise x1 - x2 (<0)
    • if yn > 0 select y2 - y1 (>0) otherwise y1 - y2 (<0)

    The reason being the rule of signs (+ times + = + and - times - = +.)

    All of this translates into

    1. start with p-vertex = (x1, y1)
    2. if xn > 0, change x1 with x2 (effectively leaving p-vertex = (x2, y1))
    3. if yn > 0, change y1 with y2 (effectively leaving p-vertex = (x*, y2))

    (In step 3, x* is x1 or x2 depending on the result of setp 2)

    These arguments remain valid if you are in 3 dimensions. The only difference is that you have to add z coordinates everywhere.