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

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

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

Perhaps, but it will be on the other end of one of the edges that get tested (if
not the same vertex, the vertex closet the center should be on the other end of
an edge shared with the vertex closet to the surface) and should still be valid
for detecting the intersection.  I can't envision any scenarios that don't get
captured with this process.

-tgq

Post a reply to this message

Am 28.01.2013 02:21, schrieb Trevor G Quayle:
> clipka <ano### [at] anonymousorg> wrote:
>> 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.
>
> Perhaps, but it will be on the other end of one of the edges that get tested (if
> not the same vertex, the vertex closet the center should be on the other end of
> an edge shared with the vertex closet to the surface) and should still be valid
> for detecting the intersection.  I can't envision any scenarios that don't get
> captured with this process.

I'm sorry to say it, but you're /still/ missing a scenario:

Small cube, close to the corner of a large one, with all surfaces almost 
- but not quite - parallel to the large one, tilted slightly so that the 
corner closest to the large cube (corner A) is moved slightly away from 
the large cube's surface. In that case, it may be the corner 
/diagonally/ (across the face, not the volume) from corner A that's 
closest to the large cube's surface.

Post a reply to this message

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

Hm, just a stupid thought. If two cubes intersect (and not the first contains
the second) then at least one edge of the first cube should intersect a face
from the second. So why not trace the second cube from the vertices of the first
along the edges with POV? May be one must trace from the hit point again in the
same direction to determine if one is inside the second cube already (that way
POV determines points inside a mesh, odd count inside, even count outside).

Best regards,
Michael

Post a reply to this message

On 2013-01-28 18:57, Daniel Nilsson wrote:
> 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.
>

I realized soon after I posted that it's not complete, it misses some 
intersections. I was tricked by doing all my thinking on 2D paper :)
This should work (fingers crossed):

0. Call one cube A, the other B
1. Transform both cubes so that A is axis-aligned.
2. (As above)
3. (As above)
4. Repeat 1-3 with A and B swapped
5. No intersection!

This should actually work for any rectangular cuboid and not just cubes.
If you skip the optimizations for axis aligned planes it should work for 
any convex polytopes (the convex hull of a rock in space, maybe?).

-- 
Daniel

Post a reply to this message

Thanks for all your answers and algorithms and suggestions.


> 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?

Only use the circumspheres for intersection testing would left over a
lot of free space around each cube that is never filled with cubes. So
it can only be an optimization for cubes that "clearly do not intersect"
(=if their circumspheres don't intersect), as step 0 before my corner
testing algorithm from above starts.

I want to avoid to check all 12 edges of cube A for intersection with
all 6 faces of cube B (not only with the planes of the faces!). But
costly pre-computions to avoid some of these checks wouldn't speed-up
the whole intersection test, I think. :-/


A completely different approach might be the 3D version of the following
calculus:

The 3D space is subdivided into 27 sub-spaces (9 in this 2D variant):

    A |  B | C
  ----+====+----
    D #  E # F
  ----+====+----
    G |  H | J


E is the interior of a cube. Now I can make simple distinction:

if the two points of an edge are in sectors A and B -> no intersection
possible; same for A and C, A and D, A and G.

Problematic are the cases A-H, A-J, A-F, B-D, B-F, B-G, B-J. :-/

Would this be an easier/simpler way?


Lars R.

Post a reply to this message

Am 29.01.2013 13:12, schrieb Lars R.:

> Only use the circumspheres for intersection testing would left over a
> lot of free space around each cube that is never filled with cubes. So
> it can only be an optimization for cubes that "clearly do not intersect"
> (=if their circumspheres don't intersect), as step 0 before my corner
> testing algorithm from above starts.
>
> I want to avoid to check all 12 edges of cube A for intersection with
> all 6 faces of cube B (not only with the planes of the faces!). But
> costly pre-computions to avoid some of these checks wouldn't speed-up
> the whole intersection test, I think. :-/

I suspect that the fastest way to do what you want is to just use a 
braindead brute-force attack, but let trace() do the actual math, as SDL 
parsing speed is probably the limiting factor far and large. Note that 
with just one single trace() call you can check one edge against /all/ 
faces of the other cube at once, so for checking all edges of one cube 
against all edges of the other you need at most 12 calls to trace():

     #macro EdgeIntersectsObject(P,V,B)
       #local N = 0;
       #local I = trace(B,P,V,N);
       ( (vlength(N) != 0) & (vlength(I-P) < vlength(V)) )
     #end

     #macro BoxIntersectsBox_Sub(P1,P2,T,PB1,PB2,TB)
       #local B = box { PB1, PB2 transform { TB } }
       #local PO = vtransform(P1,T);
       #local PX = vtransform(<P2.x, P1.y, P1.z>,T);
       #local PY = vtransform(<P1.x, P2.y, P1.z>,T);
       #local PZ = vtransform(<P1.x, P1.y, P2.z>,T);
       #local PXY = vtransform(<P2.x, P2.y, P1.z>,T);
       #local PXZ = vtransform(<P2.x, P1.y, P2.z>,T);
       #local PYZ = vtransform(<P1.x, P2.y, P2.z>,T);
       #local PXYZ = vtransform(P2,T);
       #local VX = PX-PO;
       #local VY = PY-PO;
       #local VZ = PZ-PO;
       #if (EdgeIntersectsObject(PO,VX,B)) // PO to PX
         yes
       #elseif (EdgeIntersectsObject(PO,VY,B)) // PO to PY
         yes
       #elseif (EdgeIntersectsObject(PO,VZ,B)) // PO to PZ
         yes
       #elseif (EdgeIntersectsObject(PX,VY,B)) // PX to PXY
         yes
       #elseif (EdgeIntersectsObject(PX,VZ,B)) // PX to PXZ
         yes
       #elseif (EdgeIntersectsObject(PY,VX,B)) // PY to PXY
         yes
       #elseif (EdgeIntersectsObject(PY,VZ,B)) // PY to PYZ
         yes
       #elseif (EdgeIntersectsObject(PZ,VX,B)) // PZ to PXZ
         yes
       #elseif (EdgeIntersectsObject(PZ,VY,B)) // PZ to PYZ
         yes
       #elseif (EdgeIntersectsObject(PXY,VZ,B)) // PXY to PXYZ
         yes
       #elseif (EdgeIntersectsObject(PXZ,VY,B)) // PXZ to PXYZ
         yes
       #elseif (EdgeIntersectsObject(PYZ,VX,B)) // PYZ to PXYZ
         yes
       #else
         // if we have no intersections, either all points are
         // inside or all points are outside, so we only need to
         // check a single one
         (inside(B,PO))
       #end
     #end

     #macro BoxIntersectsBox(PA1,PA2,TA,PB1,PB2,TB)
       #local CA = vtransform(0.5*(PA1+PA2));
       #local CB = vtransform(0.5*(PB1+PB2));
       #local RA = vlength(CA-vtransform(PA1));
       #local RB = vlength(CA-vtransform(PB1));
       #local L = vlength(CA-CB);
       #if (L > RA + RB)
         no
       #elseif (BoxIntersectsBox_Sub(PA1,PA2,TA,PB1,PB2,TB))
         yes
       #elseif (BoxIntersectsBox_Sub(PB1,PB2,TB,PA1,PA2,TA))
         yes
       #else
         no
       #end
     #end

where the cubes would be instantiated with:

     box {PA1,PA2 transform {TA}}
     box {PB1,PB2 transform {TB}}

Note how this approach avoids complicated math in SDL, offloading the 
major work to trace() instead. It also uses just one single inside() 
test, rather than calling that function a lot to avoid trace(), because 
the speed gain would probably be insignificant compared to the SDL 
overhead required for the special-case handling logic behind it.

Just make sure to place the sub-macros in the same file as the main 
macro - preferably in the same file as your main loop.

(BTW, the algorithm works for generic boxes with arbitrary 
transformation, not just cubes. Maybe the cube special case could be 
improved here and there a bit.)

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 29.01.2013 13:12, schrieb Lars R.:
>
> > Only use the circumspheres for intersection testing would left over a
> > lot of free space around each cube that is never filled with cubes. So
> > it can only be an optimization for cubes that "clearly do not intersect"
> > (=if their circumspheres don't intersect), as step 0 before my corner
> > testing algorithm from above starts.
> >
> > I want to avoid to check all 12 edges of cube A for intersection with
> > all 6 faces of cube B (not only with the planes of the faces!). But
> > costly pre-computions to avoid some of these checks wouldn't speed-up
> > the whole intersection test, I think. :-/
>
> I suspect that the fastest way to do what you want is to just use a
> braindead brute-force attack, but let trace() do the actual math, as SDL
> parsing speed is probably the limiting factor far and large. Note that
> with just one single trace() call you can check one edge against /all/
> faces of the other cube at once, so for checking all edges of one cube
> against all edges of the other you need at most 12 calls to trace():
>
>      #macro EdgeIntersectsObject(P,V,B)
>        #local N = 0;
>        #local I = trace(B,P,V,N);
>        ( (vlength(N) != 0) & (vlength(I-P) < vlength(V)) )
>      #end
>
>      #macro BoxIntersectsBox_Sub(P1,P2,T,PB1,PB2,TB)
>        #local B = box { PB1, PB2 transform { TB } }
>        #local PO = vtransform(P1,T);
>        #local PX = vtransform(<P2.x, P1.y, P1.z>,T);
>        #local PY = vtransform(<P1.x, P2.y, P1.z>,T);
>        #local PZ = vtransform(<P1.x, P1.y, P2.z>,T);
>        #local PXY = vtransform(<P2.x, P2.y, P1.z>,T);
>        #local PXZ = vtransform(<P2.x, P1.y, P2.z>,T);
>        #local PYZ = vtransform(<P1.x, P2.y, P2.z>,T);
>        #local PXYZ = vtransform(P2,T);
>        #local VX = PX-PO;
>        #local VY = PY-PO;
>        #local VZ = PZ-PO;
>        #if (EdgeIntersectsObject(PO,VX,B)) // PO to PX
>          yes
>        #elseif (EdgeIntersectsObject(PO,VY,B)) // PO to PY
>          yes
>        #elseif (EdgeIntersectsObject(PO,VZ,B)) // PO to PZ
>          yes
>        #elseif (EdgeIntersectsObject(PX,VY,B)) // PX to PXY
>          yes
>        #elseif (EdgeIntersectsObject(PX,VZ,B)) // PX to PXZ
>          yes
>        #elseif (EdgeIntersectsObject(PY,VX,B)) // PY to PXY
>          yes
>        #elseif (EdgeIntersectsObject(PY,VZ,B)) // PY to PYZ
>          yes
>        #elseif (EdgeIntersectsObject(PZ,VX,B)) // PZ to PXZ
>          yes
>        #elseif (EdgeIntersectsObject(PZ,VY,B)) // PZ to PYZ
>          yes
>        #elseif (EdgeIntersectsObject(PXY,VZ,B)) // PXY to PXYZ
>          yes
>        #elseif (EdgeIntersectsObject(PXZ,VY,B)) // PXZ to PXYZ
>          yes
>        #elseif (EdgeIntersectsObject(PYZ,VX,B)) // PYZ to PXYZ
>          yes
>        #else
>          // if we have no intersections, either all points are
>          // inside or all points are outside, so we only need to
>          // check a single one
>          (inside(B,PO))
>        #end
>      #end
>
>      #macro BoxIntersectsBox(PA1,PA2,TA,PB1,PB2,TB)
>        #local CA = vtransform(0.5*(PA1+PA2));
>        #local CB = vtransform(0.5*(PB1+PB2));
>        #local RA = vlength(CA-vtransform(PA1));
>        #local RB = vlength(CA-vtransform(PB1));
>        #local L = vlength(CA-CB);
>        #if (L > RA + RB)
>          no
>        #elseif (BoxIntersectsBox_Sub(PA1,PA2,TA,PB1,PB2,TB))
>          yes
>        #elseif (BoxIntersectsBox_Sub(PB1,PB2,TB,PA1,PA2,TA))
>          yes
>        #else
>          no
>        #end
>      #end
>
> where the cubes would be instantiated with:
>
>      box {PA1,PA2 transform {TA}}
>      box {PB1,PB2 transform {TB}}
>
> Note how this approach avoids complicated math in SDL, offloading the
> major work to trace() instead. It also uses just one single inside()
> test, rather than calling that function a lot to avoid trace(), because
> the speed gain would probably be insignificant compared to the SDL
> overhead required for the special-case handling logic behind it.
>
> Just make sure to place the sub-macros in the same file as the main
> macro - preferably in the same file as your main loop.
>
> (BTW, the algorithm works for generic boxes with arbitrary
> transformation, not just cubes. Maybe the cube special case could be
> improved here and there a bit.)

The original request was to have a C++ routine to do the job. I - unfortunatelly
implicitally - suggested to do the job with POV itself using the
trace()-function (Personally I would never came up with an other idea). Since
POV itself is implemented with C++ - as I learned - it must be possible to
translate trace() to back to its roots. A test for an intersection of a line
segment and a face should not be difficult with C++. To shorten the tests to
only cubes with intersecting spheres is certainly a fine idea. With many cubes
one can divide space in regions, store all cubes which are (most likely) within
a region (that must not be completelly precise and cubes can be in more than one
region) and then perform the tests region after region and avoid testing all
cubes against each other. I have seen POV-code to do this job but cannot
remember where at the moment.

Best regards,
Michael

Post a reply to this message

I have seen POV-code to do this job but cannot
> remember where at the moment.
>
I cannot prove his program so fast, but the result are magnificient. Jonathan
Hunt's "pebbles", look into the HoF, there's a link to the code.

Best regards,
Michael

Post a reply to this message

> clipka <ano### [at] anonymousorg> wrote:
>
> The original request was to have a C++ routine to do the job. I -
> unfortunatelly implicitally - suggested to do the job with POV itself
> using the trace()-function (Personally I would never came up with an
> other idea).

Just because my knowledge of C++ is far better than my knowledge of
Povray's Scene Description Language, I create all my "random object
scenes" via a C++ program that generates (large) stupid POV files.

I'll try to write such generators in SDL directly. I think, Povray's
trace() function can be used for all types of collision checks in such
SDL-generated scenes.

If I get it working you'll see the results here. :-)


			Lars R.

Post a reply to this message