Jump to content
  • Advertisement

Archived

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

Grain

Box - Line intersection.

This topic is 5165 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!