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.

Post a reply to this message

Attachments:
Download 't40kx.jpg' (108 KB)

Preview of image 't40kx.jpg'

"Lars R." <rou### [at] gmxnet> 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.

I don't have the maths for you but the general concept is this:

When testing for the intersection of spheres, you are really testing if the
centers of the spheres are at least 'x' distance from each other where 'x' = the
sum of the two radii.  Now you can extend this to cubes, but the difficulty is
deterning the 'x' value as it is not constant.

You need to:
1) determine the direction vector between the two cubes
2) determine the local rotations of the cubes relative to the direction vector
from 1)
3) determine the distances to the surfaces of the two cubes from their centers
along that direction vector.
4) ensure the sum of these two lengths is less than the total distance between
the centers.

Yes it's that simple!

-tgq

Post a reply to this message

"Trevor G Quayle" <Tin### [at] hotmailcom> wrote:
> "Lars R." <rou### [at] gmxnet> 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.
>
> I don't have the maths for you but the general concept is this:
>
> When testing for the intersection of spheres, you are really testing if the
> centers of the spheres are at least 'x' distance from each other where 'x' = the
> sum of the two radii.  Now you can extend this to cubes, but the difficulty is
> deterning the 'x' value as it is not constant.
>
> You need to:
> 1) determine the direction vector between the two cubes
> 2) determine the local rotations of the cubes relative to the direction vector
> from 1)
> 3) determine the distances to the surfaces of the two cubes from their centers
> along that direction vector.
> 4) ensure the sum of these two lengths is less than the total distance between
> the centers.
>
> Yes it's that simple!
>
> -tgq

I have had some more thought to this, and it isn't entirely true.  I'll have to
put some more think into it.

(The simple comment was intended as a joke, but turns out even more so...)

-tgq

Post a reply to this message

Lars R. wrote:

> But it is possible that 2 cubes intersects even if none of the corners
> is inside of the other cube. :-(

I haven't really thought this through, but I think most of these
cases could be avoided by also checking the center points.

Post a reply to this message

On 01/25/2013 10:00 PM, Christian Froeschlin wrote:
> Lars R. wrote:
>
>> But it is possible that 2 cubes intersects even if none of the corners
>> is inside of the other cube. :-(
>
> I haven't really thought this through, but I think most of these
> cases could be avoided by also checking the center points.

Also thinking aloud, if you are not after the best "packing" of 
arbitrarily rotated cubes, what Christian suggests should work I think 
as any given rotated cube would fit inside a sphere with a radius of 
magnitude equal to the distance from the cube's center to one of its 
corners. In other words, you could put arbitrarily rotated cubes inside 
each of your placed spheres and they would not intersect, so long as 
your spheres did not intersect.

That said, it is not apparent from your cube intersection pseudo code 
whether you are handling the inverse rotation adjustments into each 
adjacent cubes coordinate space - something at which Trevor was hinting 
in his outline.

Supposing you are handling rotations, I suspect the issue is your test 
needs to be symmetrical on each placement of a cube. Meaning it is not 
enough to test the current cubes corners are not inside adjacent cubes. 
It is also necessary to test that corners of all "adjacent" cubes are 
not inside the cube being placed.

Here "adjacent" cubes would be something like all those cubes with 
smallest containing spheres intersecting the smallest containing sphere 
of the cube you are placing.

Bill P.

Post a reply to this message

Am 25.01.2013 14:52, schrieb Lars R.:
> 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?

Not a formula, but an algorithm:

(0) [optional, just for speed] If the cubes' bounding boxes don't 
intersect, the cubes don't intersect.

(1) If any corner of the smaller cube is inside the larger cube, they 
intersect. (No need to test the other way round.)

(2) If any edge of the smaller cube intersects any surface of the larger 
cube, they intersect. (Again no need to test the other way round.)

(3) In any other case, they don't intersect.


Note that this only works for cubes, not for generic boxes.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 25.01.2013 14:52, schrieb Lars R.:
> > 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?
>
> Not a formula, but an algorithm:
>
> (0) [optional, just for speed] If the cubes' bounding boxes don't
> intersect, the cubes don't intersect.
>
> (1) If any corner of the smaller cube is inside the larger cube, they
> intersect. (No need to test the other way round.)
>
> (2) If any edge of the smaller cube intersects any surface of the larger
> cube, they intersect. (Again no need to test the other way round.)
>
> (3) In any other case, they don't intersect.
>
>
> Note that this only works for cubes, not for generic boxes.

#2 is the key.  if #1 is true then #2 is true as well.

Based on this, the long way is to:
- check all 12 edges of one cube, extend to lines (determine 3d line equation)
- check for the intersection point with the plane associated with each of the 6
faces of the other cube (determine 3d plane equation)
- if intersection point lies on edge segment of line AND with the face boundary
of the plane, then the cubes intersect
- you only have to do this one way (not check edges of one against faces of
other then vice versa)

This adds quite a bit of computation so you can try to find simplifiers:
- as clipka mentions, find length from center of cube to a corner and treat as
spheres, if spheres don't intersect, cubes don't
- find a way to determine which edges and faces are on facing sides and only
check those ones
- checking for corner intersection may help if it is simpler

-tgq

Post a reply to this message

On 01/26/2013 08:56 AM, clipka wrote:
>
> Not a formula, but an algorithm:
>
> (0) [optional, just for speed] If the cubes' bounding boxes don't
> intersect, the cubes don't intersect.
>
> (1) If any corner of the smaller cube is inside the larger cube, they
> intersect. (No need to test the other way round.)
>
> (2) If any edge of the smaller cube intersects any surface of the larger
> cube, they intersect. (Again no need to test the other way round.)
>
> (3) In any other case, they don't intersect.
>
>
> Note that this only works for cubes, not for generic boxes.
>
Hi Christoph,
I'm likely missing some detail here as I do not follow the reason for 
larger and smaller naming. In any case, I am wondering in your outline 
about the case where a corner of the "larger" cube pokes through the 
surface of the smaller cube?
Bill P.

Post a reply to this message

Am 26.01.2013 15:43, schrieb Trevor G Quayle:
> clipka <ano### [at] anonymousorg> wrote:

>> (0) [optional, just for speed] If the cubes' bounding boxes don't
>> intersect, the cubes don't intersect.
>>
>> (1) If any corner of the smaller cube is inside the larger cube, they
>> intersect. (No need to test the other way round.)
>>
>> (2) If any edge of the smaller cube intersects any surface of the larger
>> cube, they intersect. (Again no need to test the other way round.)
>>
>> (3) In any other case, they don't intersect.
>>
>>
>> Note that this only works for cubes, not for generic boxes.
>
> #2 is the key.  if #1 is true then #2 is true as well.

Not necessarily: The smaller cube could be entirely contained in the 
larger one.

Post a reply to this message

Am 26.01.2013 16:10, schrieb William F Pokorny:
> On 01/26/2013 08:56 AM, clipka wrote:
>>
>> Not a formula, but an algorithm:
>>
>> (0) [optional, just for speed] If the cubes' bounding boxes don't
>> intersect, the cubes don't intersect.
>>
>> (1) If any corner of the smaller cube is inside the larger cube, they
>> intersect. (No need to test the other way round.)
>>
>> (2) If any edge of the smaller cube intersects any surface of the larger
>> cube, they intersect. (Again no need to test the other way round.)
>>
>> (3) In any other case, they don't intersect.
>>
>>
>> Note that this only works for cubes, not for generic boxes.
>>
> Hi Christoph,
> I'm likely missing some detail here as I do not follow the reason for
> larger and smaller naming. In any case, I am wondering in your outline
> about the case where a corner of the "larger" cube pokes through the
> surface of the smaller cube?

Damn, you're bloody well right - I didn't think of that.

The reasoning for the larger/smaller cube thing was primarily for the 
case that one cube is contained entirely within the other, which is the 
only reason (or so I thought) to include test (1) at all. Obviously, 
only the smaller cube can be contained entirely within the larger, not 
vice versa. I just took the same naming for (2) as well, rather than use 
"cube A" and "cube B" there.

But yes, we need a 2.5:

(2.5a) If any corner of the larger cube is inside the smaller cube, they 
intersect.

-or-

(2.5b) If any edge of the larger cube intersects any surface of the 
smaller cube, they intersect.

Post a reply to this message