Archived

This topic is now archived and is closed to further replies.

Grain

Box - Line intersection.

Recommended Posts

Grain    500
There is probably a really simple solution I am just not seeing it. If I have a 3D box whose dimensions are from 1>x>-1, 1>y>-1, 1>z>-1 And I have two arbitrary points that are connected by a line how I can find the point or points, if any where that line intersects the sides of the box. This is for a clipping algorithm I am righting and needs to be done many times per frame so speed & efficiency are an issue. Ideally I am looking for a formula that I can just plug my numbers in to and get an answer, pretty much in the same way you would do with a sphere and a ray.

Share this post


Link to post
Share on other sites
jyk    2094
If you just need a boolean result, there are very fast algorithms based on the separating axis test.

If you need the actual points of intersection, I think you''ll have to carry out the ray/plane intersection tests. However, due to the unit box and axis-aligned planes, I imagine this could be optimized quite a bit.

I''m not positive about this though - there may be a faster algorithm I''m not aware of.

Share this post


Link to post
Share on other sites
oliii    2196
clip the ray between the two planes of each axes, and for the three axes of the box. Once you can''t clip the ray/segment, you have no collisions.

Share this post


Link to post
Share on other sites
Grain    500
Here is what I came up with but its not working.
I think the problem, is when i solve for the ClipedPoints.




int ClipProject(Point3d A,Point3d B ,Point3d& C ,Point3d& D)
{
double n = 1.0;
double f = 5000.0;
double a =(n+f)/(f-n) ;
double b =(2.0*n*f)/(n-f);
double Mx,My,Mz,bx,by,bz;
Point3d ClipedPoint[6];
if(A.z == 0.0) A.z=0.00000000001;
if(B.z == 0.0) B.z=0.00000000001;
int i;
A.y /= A.z;
A.x /= A.z;
A.z = -(a+b/A.z);
B.y /= B.z;
B.x /= B.z;
B.z = -(a+b/B.z);

if(A.y == B.y) My = 9999999999999999.9;
else My = (A.x-B.x)/(A.y-B.y);
if(A.z == B.z) Mz = 9999999999999999.9;
else Mz = (A.x-B.x)/(A.z-B.z);

by = A.y -(My*A.x);
bz = A.z -(Mz*A.x);
ClipedPoint[0].x = 1; ClipedPoint[0].y = My + by; ClipedPoint[0].z = Mz + bz; // X = 1

ClipedPoint[1].x =-1; ClipedPoint[1].y =-My + by; ClipedPoint[1].z =-Mz + bz; // X = -1


if(A.x == B.x) My = 9999999999999999.9;
else Mx = (A.y-B.y)/(A.x-B.x);
if(A.z == B.z) My = 9999999999999999.9;
else Mz = (A.y-B.y)/(A.z-B.z);
bx = A.x -(Mx*A.y);
bz = A.z -(Mz*A.y);
ClipedPoint[2].x = Mx + bx; ClipedPoint[2].y = 1; ClipedPoint[2].z = Mz + bz; // Y = 1

ClipedPoint[3].x =-Mx + bx; ClipedPoint[3].y =-1; ClipedPoint[3].z =-Mz + bz; // Y = -1


if(A.y == B.y) My = 9999999999999999.9;
else My = (A.z-B.z)/(A.y-B.y);
if(A.x == B.x) My = 9999999999999999.9;
else Mx = (A.z-B.z)/(A.x-B.x);
by = A.y -(My*A.z);
bx = A.x -(Mx*A.z);
ClipedPoint[4].x = Mx + bx; ClipedPoint[4].y = My + by; ClipedPoint[4].z = 1; // Z = 1

ClipedPoint[5].x =-Mx + bx; ClipedPoint[5].y =-My + by; ClipedPoint[5].z =-1; // Z = -1




if(B.z<1 && B.z > -1 && B.y <1 && B.y > -1 && B.x <1 && B.x > -1)
{
D = B;
D.y -= 0.75;
D.x += 1.0;
D.y *= -640.0/2;
D.x *= 640.0/2;
if(A.z<1 && A.z > -1 && A.y <1 && A.y > -1 && A.x <1 && A.x > -1)
{
C = A;
C.y -= 0.75;
C.x += 1.0;
C.y *= -640.0/2;
C.x *= 640.0/2;
return 1;
}
else
{
for(i=0;i<6;i++)
{
C = ClipedPoint[i];
if( ( (A.x <= C.x && C.x <= B.x && A.y <= C.y && C.y <= B.y && A.z <= C.z && C.z <= B.z)||
(A.x >= C.x && C.x >= B.x && A.y >= C.y && C.y >= B.y && A.z >= C.z && C.z >= B.z)
)&& (C.z<=1 && C.z >= -1 && C.y <=1 && C.y >= -1 && C.x <=1 && C.x >= -1)
){
C.y -= 0.75;
C.x += 1.0;
C.y *= -640.0/2;
C.x *= 640.0/2;
return 1;
}
}
}
}
else
{
//D = clip B

if(A.z<1 && A.z > -1 && A.y <1 && A.y > -1 && A.x <1 && A.x > -1)
{
C = A;
C.y -= 0.75;
C.x += 1.0;
C.y *= -640.0/2;
C.x *= 640.0/2;
for(i=0;i<6;i++)
{
D = ClipedPoint[i];
if( ( (A.x <= D.x && D.x <= B.x && A.y <= D.y && D.y <= B.y && A.z <= D.z && D.z <= B.z)||
(A.x >= D.x && D.x >= B.x && A.y >= D.y && D.y >= B.y && A.z >= D.z && D.z >= B.z)
)&& (D.z<=1 && D.z >= -1 && D.y <=1 && D.y >= -1 && D.x <=1 && D.x >= -1)
){
D.y -= 0.75;
D.x += 1.0;
D.y *= -640.0/2;
D.x *= 640.0/2;
return 1;
}
}
}
else
{
//clip both, not done yet.

//D = cliped B

//C = cliped A


if(C.z<=1 && C.z >= -1 && C.y <=1 && C.y >= -1 && C.x <=1 && C.x >= -1 &&
D.z<=1 && D.z >= -1 && D.y <=1 && D.y >= -1 && D.x <=1 && D.x >= -1)
{

return 1;
}
else return 0;
}
}
return 0;
}

Share this post


Link to post
Share on other sites
oliii    2196
lol quite intricate!


bool ClipAxis(float min, float max, float a, float b, float &t0, float& t1)
{
float d = (b - a);

if (fabs(d) < 0.0000001f)
{
if (d > 0.0f)
return !(b < min || a > max);

return !(a < min || b > max);
}

float u0, u1;

u0 = (min - a) / (d);
u1 = (max - a) / (d);

if (u0 > u1) swapf(u0, u1);

if (u1 < t0 || u0 > t1)
return false;

t0 = max(u0, t0);
t1 = min(u1, t1);

return true;
}


bool Intersect(Vector Min, Vector Max, Vector A, Vector B)
{
float t0 = 0.0f, t1 = 1.0f;
if (!ClipAxis(Min.x, Max.x, A.x, B.x, t0, t1)) return false;
if (!ClipAxis(Min.y, Max.y, A.y, B.y, t0, t1)) return false;
if (!ClipAxis(Min.z, Max.z, A.z, B.z, t0, t1)) return false;

return true;
}



typo

[edited by - oliii on May 28, 2004 4:46:16 AM]

Share this post


Link to post
Share on other sites