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