title: Determining if a sphere intersects an object or not
body: <p>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.</p>
  
  <p>I have thought of 3 ways to determine this, but each one has their downsides and none of them are ideal.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Thanks</p>
  
  <p>-Faken</p>