 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] anonymous org> 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
|
|
| |
| |
|
|
|
|
| |
|
|
