FunTracer: hitting a sphere

In order to trace a ray we have to decide if a given ray hits a object in our scene. In this post I want to show you how to do this for the classic case of a sphere.

Indeed – for now – a object in a scene will be nothing other than a way to get a intersection of a ray with this object, together with some additional data helping us to shade the point. To be precise if a ray hits a object we will need:

  • the point where the ray hits the object
  • the distance from the start of the ray
  • the normal on the surface of the object at this point (a vector perpendicular to the surface at the hit-point) and
  • the color of the object at this point.

All this directly translates to the following types:

type HitResult = { Ray : Ray; Distance : float; Pos : Point; Normal : Direction; Color : Color }
type SceneObj = { HitTest : Ray -> HitResult option }

In the remainder of this post I will talk about how to get all this from a sphere.

Defining a sphere in 3D

So what is a sphere – well Wikipedia explains it really nice and we will use just this:

“A sphere S(m,r) centered at a point m in 3D and having radius r is the set of all points p in 3D having distance r from m”:

 S(m,r) = \left\{ p : \left| m-p \right| = r \right\}

Of course this is equivalent to

 S(m,r) = \left\{ p : {\left| m-p \right|}^{2} = r^{2} \right\}

and for this we already know a nice interpretation using the dot-product:

 S(m,r) = \left\{ p : ( m-p) \cdot (m-p) = r^{2} \right\} .

Next let’s look at the ray. A ray starting at point s and pointing in the direction d is the set of all point:  \left\{ p = s + td : t \geq 0 \right\} . (note that t should be non-negative as we are only interested in points in “front” of the start).

Of course we now combine those two equations into:

 (m-s-td) \cdot (m-s-td) = r^{2}

with unknown t.

Setting  m_{0} := (m-s)\cdot(m-s) ,  m_{1} := -2(m-s)\cdot d and using  d \cdot d = 1 as d is a unit-vector we get:

 0 = (m-s-td) \cdot (m-s-td)-r^{2}  = (m-s)\cdot(m-s)-2t(m-s) \cdot d + t^{2} d \cdot d-r^{2}  = m_{0}-r^{2} + m_{1}t + t^{2}

a simple quadratic equation in t.

As we want to trace a ray and get the first hit-point we are only interested in the minimum of the positive t’s.

The normal of a point on the sphere is just the direction of m to the point (just the vector from m to that point normalized) so this all translates into:

    let Create (m : Vector3, radius : float, color : Color) : SceneObj =
        let r2 = radius * radius
        let hitTest (ray : Ray) =
            let getPt t = ray.Start + t*ray.Direction
            let getResult t =
                let pos = getPt t
                let normal = Vector.Normalize (pos - m)
                { Ray = ray; Distance = t; Pos = pos; Normal = normal; Color = color }
            let ts =
                let v0 = m - ray.Start
                let b = -2.0*(v0<*>ray.Direction)
                let c = (v0 <*> v0) - r2
                solveQuadEquation (1.0, b, c)
            match ts |> List.filter IsPositive with
            | [t]    -> t |> getResult |> Some
            | [a; b] -> (min a b) |> getResult |> Some
            | _      -> None
        { HitTest = hitTest }

using the helper function

    let private solveQuadEquation (a : float,  b : float, c : float) =
        let rad = b*b - 4.0*a*c
        let k0 = b / (-2.0*a)
        match rad with
        | Negative -> []
        | NearZero -> [ k0 ]
        | Positive -> let sqrtRad = (sqrt rad)/(2.0 * a)
                      [ k0 + sqrtRad; k0 - sqrtRad ]

to solve quadratic equations together with the helpers we defined in here to handle floats-near zero:

[< AutoOpen >]
module FloatHelpers =

    let ZeroThreshold = 0.0000000001

    let IsNearZero (f : float) =
        abs f <= ZeroThreshold

    let IsPositive (f : float) =
        f > ZeroThreshold

    let IsNegative (f : float) =
        f < -ZeroThreshold

    let (|NotNearZero|_|) (f : float) =
        if IsNearZero f
        then None
        else Some f

    let (|Negative|NearZero|Positive|) (f : float) =
        if f |> IsNegative then Negative
        elif f |> IsPositive then Positive
        else NearZero

Performance remarks:

I did not spent to much time on performance as I think at this point clarity rules. There are a lot improvements to be found here – for example in the solving of the quadratic equation as we would only need the form with a=1. As this isn’t going to get a real-time ray tracer anyhow I don’t think that this really matter at all but there might be some tweaking at the end of the series.

That’s it for now – next time we will put all of this together to render a simple sphere – finally Zwinkerndes Smiley