Archived

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

Intersection of sphere and cylinder

This topic is 5133 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

Hi. I have found algorithm which calculates intersection of sphere and infinite cylinder. However I have not found solution for intersection of sphere and finite cylinder. Does somebody know a general formula/algorithm for calculating sphere and finite cylinder intersection? Floru

Share this post


Link to post
Share on other sites
Hm... how about a collision between a sphere and a capsule? Will that suit your purposes? The problem with the finite cylinder test is how to test against the edges.

The capsule is exactly like the finite cylinder but is rounded at the ends. Here, I will show you how to do a capsule-sphere test. Calculate your parametric t along your capsule (t will range from 0..1 if it lies along your capsule)

t = dotproduct(linedirection, (spherepos - lineorigin)) / dotproduct(linedirection, linedirection)

line direction is the vector from your cylinder''s origin point to your cylinder''s end point.

You clamp t to the range 0..1. ie.

if (t < 0.0f) then t = 0.0f
else if (t > 1.0f) then t = 1.0f;

Now calculate your closest point on the cylinder

cylinderpoint = lineorigin + t.linedirection;

now calculate the vector from the cylinder point to the spheres point
vectortosphere = spherepos - cylinderpoint;

if the vectortosphere''s length is greater than the radius of the sphere plus the radius of the cylinder then there is no collision

if (dotproduct(vectortosphere,vectortosphere) > (sphereradius + cylinderradius) * (sphereradius * cylinderradius)) then
{
return FALSE;
}
else
{
return TRUE;
}

The capsule test is a reasonable approximation to a cylinder (except in the case of very short cylinders).

I hope this is okay for your purposes.
FReY

Share this post


Link to post
Share on other sites

Thanks for a very clear answer FReY!

Just to make sure...
cylinderpoint = lineorigin + t.linedirection;
=>
cylinderpoint = lineorigin + t * linedirection; ?

Approximation is good but the problem with sphere and finite cylinder has bothered me for over a week now and I''d like to get answer also to that problem. You know... When some problem bothers you, you really want to get the answer.

Floru

Share this post


Link to post
Share on other sites
well, you know how to get the shortest distance between a point and a line right?

just do that, if the shortest distance lies outside the ends of the line then assume no intersection until you do the following test:

check if the sphere intersects with the circle at the end of the cylinder...

to do that:

Lets call A the closest distance between the infinite line and the point at the center of the sphere
Lets call B the distance between that closest point on the infinite line and the end of the finite line... still with me? i''m bad at explaining stuff...

Lets say r1 is the radius of your sphere, r2 is the radius of your cylinder...

if (A-r2 < 0)
{
if (B < r1)
// Intersection
else
// No intersection
}
else
{
if (sqrt((A-r2)^2+(B)^2)) < r1)
// Intersection
else
// No intersection
}

Share this post


Link to post
Share on other sites
How about doing the line to point distance stuff first.

Then define 2 planes that define the extends of your cylinder.
Should be easy because for the plane equation you can use the line direction, and line-start/end-vertex.

Then do point (for sphere) to plane distance for both planes. Distance - Sphere < 0 means not intersecting with cylinder

Share this post


Link to post
Share on other sites
Thanks baskuenen. Your solution is very understandable but I think it does not work for all cases. Correct me if I'm wrong. For example (sorry about the bad picture):


| |/--\
| | | (sphere)
| |\ /
--- - - - - - - - - (plane1)
| |
| |
| | (cylinder)
| |
| |
--- - - - - - - - - (plane2)
| |
| |


If in example the sphere would intersect infinite cylinder and plane1 there is no collision with finite cylinder.

Floru

[edited by - floru on November 13, 2003 4:32:21 AM]

[edited by - floru on November 13, 2003 4:33:25 AM]

Share this post


Link to post
Share on other sites

Hi!

Sorry about the delay. I have been busy, but now I think I got the algorithm working. I''ll put the code (Lua) of my solution here if somebody want''s to check it or somebody finds it useful. Thanks for help and suggestions are welcome.


function VectorNormalize(v)
local m = math.sqrt(v[1]^2 + v[2]^2 + v[3]^2)

if m <= 0 then
m = 1
end

return { v[1] / m, v[2] / m, v[3] / m }
end

function VectorSum(v1, v2)
return { v1[1] + v2[1], v1[2] + v2[2], v1[3] + v2[3] }
end

function VectorSub(v1, v2)
return { v1[1] - v2[1], v1[2] - v2[2], v1[3] - v2[3] }
end

function VectorScale(v, s)
return { v[1] *s, v[2] *s, v[3] * s}
end

function DotProduct(v1, v2)
return (v1[1] * v2[1]) + (v1[2] * v2[2]) + (v1[3] * v2[3])
end

function Distance(v1, v2)
return math.sqrt((v1[1] - v2[1])^2 + (v1[2] - v2[2])^2 + (v1[3] - v2[3])^2)
end

-- vp = point in vector
-- v = vector
-- p = point
function ClosestPoint(vp, v, p)
local v = VectorNormalize(v)
return VectorSum(vp, VectorScale(v, (DotProduct(VectorSub(p, vp), v))))
end

function ClosestPoint2(vp, v, p)
local t = (DotProduct(v, (VectorSub(p, vp))) / DotProduct(v, v))

return {vp[1] + v[1] * t, vp[2] + v[2] * t, vp[3] + v[3] * t}
end


function Test(Cylinder, Sphere)
-- Closest point between point and line.
local cp = ClosestPoint(Cylinder.pos, Cylinder.dir, Sphere.pos)

-- A = Closest distance between infinite line and center of sphere.
local A = Distance(cp, Sphere.pos)

-- End of finite lines (cylinder).
local p1 = Cylinder.pos
local p2 = VectorSum(Cylinder.pos, VectorScale(VectorNormalize(Cylinder.dir), Cylinder.h))

-- Distance between end of infinite line end points.
local pdist = Distance(p1, p2)

-- Check if closest point is between ininite line end points.
if (Distance(p1, cp) < pdist) and (Distance(p2, cp) < pdist) then
print(''Between'')

if A <= Sphere.r + Cylinder.r then
return true
else
return false
end
end

-- B = Distance between closest point on the infinite line and
-- the end of the finite line.
local b1 = Distance(cp, p1)
local b2 = Distance(cp, p2)

local B

if b1 < b2 then
B = b1
else
B = b2
end

if A - Cylinder.r < 0 then
print(''If'')

if B < Sphere.r then
return true
else
return false
end
else
print(''Else'')

if math.sqrt((A - Cylinder.r )^2 + B^2) < Sphere.r then
return true
else
return false
end
end
end

local Cylinder =
{
pos = {1, 1, 0},
dir = {0, 1, 0},
r = 0.5,
h = 9,
}

local Sphere =
{
pos = {2, 5, 0},
r = 0.5,
}

print(''Test1:'')
print(''->'', Test(Cylinder, Sphere))

Sphere.pos = {1, 5, 1},

print(''Test2:'')
print(''->'', Test(Cylinder, Sphere))

Cylinder.dir = {1, 1, 0}
Sphere.pos = {0, 0, 0},

print(''Test3:'')
print(''->'', Test(Cylinder, Sphere))

Sphere.r = 1.42

print(''Test4:'')
print(''->'', Test(Cylinder, Sphere))

Sphere.pos = {0, 2, 0}
Sphere.r = 0.92

print(''Test5:'')
print(''->'', Test(Cylinder, Sphere))



Floru

Share this post


Link to post
Share on other sites