On 2013-01-25 14:52, Lars R. wrote:
> I wrote a C++ program that generates the scene you see in the attached
> image. (40k non-intersecting spheres)
>
> Now I'd like to change it to use many,many small cubes (randomly
> rotated, of course), so I need an intersection formula for cubes.
>
> I tried something like this: If one of the 8 corners of a cube is inside
> the other one than the cubes intersect:
>
> |  for corner = cubeA.corner0 … cubeA.corner7:
> |     if( corner is_inside_of cubeB ) return true;
> |
> |  for corner = cubeB.corner0 … cubeB.corner7:
> |     if( corner is_inside_of cubeA ) return true;
>
> But it is possible that 2 cubes intersects even if none of the corners
> is inside of the other cube. :-(
>
> Has anyone a better formula for me?
>
> 					Lars R.
>

Here's an algorithm I think covers all cases:

1. Transform both cubes so that the bigger cube (called A) is aligned
    with the coordinate axes.
2. For each face of cube A:
  A. Check all vertices of cube B against the plane of the face.
     This is a simple B.x > A.x type of test.
  B. If all are outside then the cubes are not overlapping, you're done!
  C. If all are inside then remember that and continue to the next face.
  D. For each edge that have one vertex inside and one outside:
   a. Calculate the intersection with the plane of the face.
      The math should be fairly simple since the plane is like X=C
   b. Test the intersection point against the face boundary.
      Again, simple p.y < y_min type of tests.
   c. If the intersection point is inside the face then the cubes
      intersect and you're done!
   d. If the point is outside the face, continue to the next edge.
  E. Continue to the next face
3. If the test 2.C was true for all faces then cube B is inside cube A
    and you are done!
4. No intersection!

Optimization: Do 2.A-C & 3 first in a separate loop to catch trivial 
cases, then do 2.D if still needed.

-- 
Daniel

Post a reply to this message