Find if a line intersects a sphere

Question

Trying to make a very simple boolean function that will find whether a line intersects a sphere.

This did not seem to be what I want, even though the question was similar: http://stackoverflow.com/questions/910565/intersection-of-a-line-and-a-sphere

Also I have tried the algorithms listed at:

http://www.docstoc.com/docs/7747820/Intersection-of-a-Line-and-a-Sphere

and

http://www.ccs.neu.edu/home/fell/CSU540/programs/RayTracingFormulas.htm

with no real luck.

My most recent code (in Haskell) looks like:

data Point = Point { x :: Float, y :: Float, z :: Float} deriving (Eq, Show, Read)
data Sphere = Sphere { center :: Point, radius :: Float } deriving (Eq, Show, Read)

inView :: Point -> Point -> Sphere -> Bool
inView (Point x1 y1 z1) (Point x2 y2 z2) (Sphere (Point x3 y3 z3) r)
  | result > 0 && result < r = False
  | otherwise                = True
  where result = top/bot
        top = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1) + (z3 - z1) * (z2 - z1)
        bot = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1)

Where it returns true if 2 points have a direct line-of-site. This works for some simple cases, but fails for others that should work, such as:

inView (Point {x = 43.64, y = -183.20, z = 187.37}) (Point {x = 42.04, y = -183.58, z = 187.37}) (Sphere (Point 0 0 0) 5)

Any help would be appreciated.

Answer 1

This is a lazy answer, but the following page should have the information you want: http://www.devmaster.net/wiki/Ray-sphere_intersection

More generally, googling for ray sphere intersection rather than line sphere intersection should yield a wealth of straightforward information.

Also, I think this is essentially a duplicate of this question: http://stackoverflow.com/questions/2062286/testing-for-ray-sphere-intersection

Answer 2

It looks to me like you want instead to use

inView :: Point -> Point -> Sphere -> Bool
inView (Point x1 y1 z1) (Point x2 y2 z2) (Sphere (Point x3 y3 z3) r)
  | result > 0 && result < r^2 = False // is this correct? I know nothing about Haskell, but seems like this should be True
  | otherwise                  = True
  where result = -t1^2/t2 + t3
        t1 = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1) + (z3 - z1) * (z2 - z1)
        t2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1)
        t3 = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1) + (z3 - z1) * (z3 - z1)

NB. I don't know what Haskell's notation for square is, so I used ^2 above.

e: working here and here

Answer 3

You are using the wrong equation. If your line is represented like:

p1 + u (p2 - p1)

(where u is a scalar), then top/bot finds the u that makes that expression as close as possible to the center of the sphere.

So I would amend your code:

where u = top/bot
      nearestPoint = {- p1 + u (p2 - p1) -}
      result = {- distance between nearestPoint and p3 -}

Fill in that pseudocode and you should be golden. You were just misinterpreting the meaning of result.

By the way, you could probably clean up your code a lot by using Data.VectorSpace. I can write out my amendment in full easily using it:

import Data.VectorSpace

type Point = (Double, Double, Double)
inView :: Point -> Point -> Sphere -> Bool
inView p1 p2 (Sphere p3 r) = result < r
    where u = top/bot
          top = ...
          bot = ...
          nearestPoint = p1 ^+^ u *^ (p2 ^-^ p1)
          result = magnitude (p3 ^-^ nearestPoint)

Answer 4

I don't know if this is the most efficient way to do things, but one thing to consider is:

A line intersects a sphere if the perpendicular distance from the line to the center of the sphere is less than or equal to the radius of the sphere.

Your question then becomes: How do I calculate the distance from a point to a line?