Line - Circle intersection test in 3d world?

Question

i have a 3d world where i have several 2d circles laying on the ground facing to the sky.

how can i check if a line will intersect one of those circles frop top-to-down?

i tried to search but all i get is this kind of intersection test: http://mathworld.wolfram.com/Circle-LineIntersection.html

but its not what i need, here is image what i mean: http://imageshack.us/m/192/8343/linecircleintersect.png

Answer 1

If you are in a coordinate system, where the ground is given by z = c for c some constant, then you could simply calculate the x, y coordinates of the line for z = c. Now for a circle of origin x0, y0 and radius R, you would simply check if

(x - x0)^2 + (y - y0)^2 <= R^2.

If this is true, the line intersects the circle.

Answer 2

In a 3D sense you are first concerned with not with a circle but with the plane where the circle lies on. Then you can find the point of intersection between the ray (line) and the plane (disk).

I like to use homogeneous coordinates for point, planes and lines and I hope you are familiar with vector dot · and cross products ×. Here is the method:

Plane (disk) is defined by a point vector r=[rx,ry,rz] and a normal direction vector n=[nx,ny,nz]. Together they form a plane W=[W1,W2]=[n,-r·n].

Line (ray) is defined by two point vectors r_A=[rAx,rAy,rAz] and r_B=[rBx,rBy,rBz]. Together they form the line L=[L1,L2]=[r_B-r_A, r_A×r_B]

The intersecting Point is defined by P=[P1,P2]=[L1×W1-W2*L2, -L2·W1], or expanded out as

P=[ (r_B-r_A)×n-(r·n)*(r_A×r_B), -(r_A×r_B)·n ]

The coordinates for the point are found by r_P = P1/P2 where P1 has three elements and P2 is scalar.

Once you have the coordinates you check the distance with the center of the circle by d=sqrt((r_p-r)·(r_p-r)) and checking d<=R where R is the radius of the circle. Note the difference in notation between a scalar multiplication * and a dot product ·

If you know for sure that the circles lie on the ground (r=[0,0,0]) and face up (n=[0,0,1]) then you can make a lot of simplifications to the above general case.

[ref: Plucker Coordinates]

Update:

When using the ground (with +Z up) as the plane (where circles lie), then use r=[rx,ry,0] and n=[0,0,1] and the above intersection point simplifies to

r_p = [ rBy-rAy, rAx-rBx, 0] / (rAy*rBx-rAx*rBy)

of which you can check the distance to the circle center.