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