Alex Rivera | Logout

Determining if a sphere intersects an object or not

Asked 2010-02-08T06:36:35.587
10

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 th

algorithm 3d theory
Edit
Report

1 Answer

5

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:

answered 2010-02-08T18:39:34.583

Your Answer