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

William F Pokorny wrote:

"...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."

Yeah, this was part of my own attack on the general problem, in my recent
'meteor' animation. It's the only way I could think of to deal with the constant
(and random) rotations of all the meteors. I didn't fully work out the details,
though...

And Clipka wrote:

"Not a formula, but an algorithm:... [clip]
Note that this only works for cubes, not for generic boxes."

It's the *randomly-scaled* meteors in my scene that (I think) are the root cause
of the problem I ran into. Had all the meteors been the same size, my algorithm
would probably have worked. I need to re-write how/when my code performs its
intersection comparisons. It's beginning to look not-too-difficult.

I'm following this thread with great interest!

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> 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.

OK, you are right about that, didn't think of that.  The way to check that is to
check for intersecting spheres based on the inner boundary (distance from cube
center to face).

So:
1) check outer boundary spheres (radius = cube center to cube vertex), if they
don't intersect, cubes don't intersect.
2) check inner boundary spheres (radius = cube center to face), if they
intersect, cubes intersect or are nested.
3) for remaining cases, check edge line/face plane intersection points.


-tgq

Post a reply to this message

Am 26.01.2013 23:11, schrieb Trevor G Quayle:
> clipka <ano### [at] anonymousorg> wrote:
>> 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.
>
> OK, you are right about that, didn't think of that.  The way to check that is to
> check for intersecting spheres based on the inner boundary (distance from cube
> center to face).

That's insufficient if the smaller cube is /very/ small and embedded in 
the larger cube close to one of its corners.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 26.01.2013 23:11, schrieb Trevor G Quayle:
> > clipka <ano### [at] anonymousorg> wrote:
> >> 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.
> >
> > OK, you are right about that, didn't think of that.  The way to check that is to
> > check for intersecting spheres based on the inner boundary (distance from cube
> > center to face).
>
> That's insufficient if the smaller cube is /very/ small and embedded in
> the larger cube close to one of its corners.

Stop thinking of everything!

OK one more think at this:

1) check outer boundary sphere intersection (radius = center to vertex).  If no
intersection (distance > r1 + r2), cubes don't intersect,

else

2) check inner boundary sphere intersection (radius = center to face).  If
intersection (distance < r1 + r2), cubes intersect or nest.

else

3) determine closest vertex for each cube to the center of other (don't need to
check each vertex). if either vertex is inside other cube, intersected or nested

else

4) for one cube, check each edge from closest vertex for intersection with each
face from each vertex of other cube, if intersect, cubes intersect. (don't need
to check every single one, only 3 edges from 1 and 3 faces from other)

else

5) cubes don't intersect!

Does that cover it all?  Or is there some other scenario that falls outside
these rules?

-tgq

Post a reply to this message

Am 27.01.2013 21:00, schrieb Trevor G Quayle:

> Stop thinking of everything!

Sorry, but I just can't help it ;-)

> OK one more think at this:
>
> 1) check outer boundary sphere intersection (radius = center to vertex).  If no
> intersection (distance > r1 + r2), cubes don't intersect,
>
> else
>
> 2) check inner boundary sphere intersection (radius = center to face).  If
> intersection (distance < r1 + r2), cubes intersect or nest.
>
> else
>
> 3) determine closest vertex for each cube to the center of other (don't need to
> check each vertex). if either vertex is inside other cube, intersected or nested
>
> else
>
> 4) for one cube, check each edge from closest vertex for intersection with each
> face from each vertex of other cube, if intersect, cubes intersect. (don't need
> to check every single one, only 3 edges from 1 and 3 faces from other)
>
> else
>
> 5) cubes don't intersect!
>
> Does that cover it all?  Or is there some other scenario that falls outside
> these rules?

You're forgetting that the vertex of cube A closest to the /center/ of 
cube B isn't necessarily the one closest to the /surface/ of the other.

Post a reply to this message