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

Make hybrid. Find the closed triangle/point whith method 2 and check all combinations of intersections with all triangles near the triangle.

Answer 2

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.

Answer 3

The intersection between a sphere and a plane is a connected set.

Hence taking John's "closest approach to the plane" idea, if the sphere and the triangle intersect, and if both are closed, then either:

• the closest point on the plane lies inside the triangle
• the sphere intersects at least one of the edges of the triangle (because by connectedness there exists a continuous path within the plane/sphere intersection from some point inside the triangle, to some point outside the triangle. This path must cross the boundary, and the point at which it does so lies in the sphere).

The intersection between a sphere and a line is a connected set.

So extend the edge to a line the same way we extended the triangle to a plane. If the sphere intersects the edge, then either:

• the closest point on the line lies inside the edge
• the sphere intersects at least one of the vertices of the triangle.

So, if any of the 4 closest points (1 plane, three lines) lies in the sphere and the triangle then of course they intersect. Otherwise: if all four are outside the sphere then the two don't intersect, and if any of them is inside the sphere, then they intersect iff any of the vertices of the triangle lies in the sphere.

Unfortunately, doing this for each triangle only tells you whether the sphere and the surface of the solid intersect. It doesn't consider the case where the sphere is entirely inside the solid. So finally (or perhaps first), you must also check whether the centre of the sphere is inside the solid.

This may not be efficient, of course - I am no expert in programming geometry. And as Andrew McGregor points out, floating-point calculations don't necessarily give consistent results.

Answer 4

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.

Answer 5

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.

Answer 6

Intersection check using Bounding Volume might interest you. Please check this.

Here is a page which surveys algorithms on surface intersection algorithms.

cheers

Answer 7

Would combining (2) and also testing the center of the triangular face as another vertex work for you?