Determining if a sphere intersects an object or not

Question

I have a closed object described by a surface representation of triangles (described by three vertices which forms a right hand rule with a normal pointing to the "outside" of the object). I place a sphere of some radius in 3D space somewhere close to the surface of the object. I want to determine if the sphere intersects the object or not.

I have thought of 3 ways to determine this, but each one has their downsides and none of them are ideal.

1) I can determine the "side" on which the sphere is going to be placed, from there i can calculate a grid of distances from a reference plane to the distance where the object is first encountered. I can do the same for the opposite "side" of the sphere and then simply check if the distance to the object is always greater than the distance to the surface of the sphere. If the distance to the object is always greater, the sphere doesn't intersect the object at any of the points on the grid.

The benefit to this is that it is fairly fast, but since i only calculate discrete points, its not absolute. If the resolution of my grid is too course, there is a chance that the sphere will intersect at a point that is in between my grid nodes.

2) I can take all the vertices of all the triangles and check them against the equation of the sphere i placed. If a vertices is detected inside the sphere, the sphere will absolutely be partially inside the object.

The benefit of this is that it is fairly fast but also very prone to failure. The sphere could intersect the object within a triangle and miss all vertices all together.

3) I can calculate cluster of points on the surface of the sphere. I can then check if each point is inside the object or not (using the 3D version of point inside a polygon algorithm). If any one point is inside the object, the part of the sphere is inside the object.

The benefit of this is that it can be very accurate, depending on how many points i use on the surface of my sphere (higher density of points = more accuracy). However, the point inside an object algorithm is fairly expensive, especially when the number of triangles increases. This method would be best (would even tell me exactly where and how much of the sphere intersects the object) but it would be very slow.

Is there any algorithm or method you guys may know to solve such a problem? My foremost goal is accuracy, I need to know if the sphere will or will not touch the object. It would also be nice to know where the sphere touches or at least the general area. Finally speed is always a good thing to have.

Thanks

-Faken

Answer 1

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.