Determining if a sphere intersects an object or not

I think you can do this with CGAL. First calculate the Minkowski sum of the sphere and the object, then you can just test if the center of the sphere (as a reference point) is inside or outside the object. This can be done in arbitrary precision arithmetic, so you can be exact if you need to be.

OK, I'll try again. ;)

If you need accuracy, and if you know the vertices accurately, then you can use the shortest distance to a plane to see if the sphere touches any of the planes defined by any set of three vertices which give you your triangles. For those that do, you see if the point of closest approach actually lies within the triangle.

This should be a full answer to your question. I haven't given an implementation, so it might require thought to avoid unnecessary divisions etc. Please ask for clarification is anything is unclear. I am building off of John at CashCommons's ideas.

Let c be the center of a sphere with radius r. What we really need to know is: is any point of the triangle T (NOT just the three vertices) closer to c than r units?

There are three cases to consider:

1. The point in T which is closest to c is a vertex of T. This is easy!
2. The point in T which is closest to c is inside of T.
3. The point in T which is closest to c is on one of T's edges.

We define some variables:

• c: the center of the sphere
• r: the radius of the sphere
• T: our triangle
• v1,v2,v3: the vertices of T
• t: the point in T that is closest to c
• P: the unique plane that contains v1, v2, v3
• p: the point in P that is closest to c

STEP 1: Check all the triangle vertices, in case we are in Case 1.

STEP 2: find p, the point in P that is closest to c. This can be done by projecting c onto P.

STEP 3: If we are in case 2, we are basically done. So check if p is in T. (Checking if a point is in a given triangle is relatively easy, but I don't know the BEST way to do it, so I'll leave that out.) If it is, check whether dist(p,c) > r, and that gives you your answer.

This leaves only case 3. So, assume we have p, and that p is not in T. Now, we actually know something specific about p from the geometry: the line c-->p is perpendicular to P. (If it wasn't, we could find a point p' that is closer to c than p.) Because of this perpendicularity, we can use the Pythagorean theorem:

Dist(c, z)^2 = Dist(c, z)^2 + D(p, z)^2

for any z in P. In particular this is true for z=t.

So now we just need to find t and check whether:

D(p,t)^2 <= r^2 - D(c,p)^2

This is a very similar problem, now in 2 dimensions. The thing to do is to find the t in T which is closest to p, and thus to c. We have already checked that t is not inside of T, or one of the vertices of T. Therefore, it must be on one of the edges. So, we can just try to find it on each edge. If t is not at a vertex, then the line t-->p will be perpendicular to the side, so it is reasonably straightforward to do.

STEP 4: For each side v1-->v2 of the triangle, do the following:

4.1. The line segment from v1 to v2 is given by

(x,y,z) = (v1x, v1y, v1z) + s * (v2x - v1x, v2y - v1y, v2z - v1z), 0 <= s <= 1

4.2 We want a line that lies in plane P, is perpendicular to v1-->v2, and contains p. This line will have the form

(px, py, pz) + s * (qx, qy, qz)

so we just have to pick a vector q that is parallel to plane P and perpendicular to v1-->v2. Taking

q = (p-->c) x (v1-->v2)

(i.e., the cross product) should do it, since this will be perpendicular to the normal of P, and thus parallel to P, and perpendicular to v1-->v2.

4.3 Solve the system of equations

(tx,ty,tz) = (v1x, v1y, v1z) + s1 * (v2x - v1x, v2y - v1y, v2z - v1z)
(tx,ty,tz) = (px, py, pz) + s2 * (qx, qy, qz)

to find t that lies on both lines. This really just means solving

v1x + s1 * (v2x - v1x) = px + s2 * qx
v1y + s1 * (v2y - v1y) = py + s2 * qy
v1z + s1 * (v2z - v1z) = pz + s2 * qz

for s1 and s2.

4.4. If s1 is between 0 and 1, then we found a point t that is between v1 and v2, and it should be checked.

4.5. If s1 is not between 0 and 1, then one of v1 or v2 was the closest to p, so we already checked it.