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