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