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 centered at a point in 3D and having radius is the set of all points in 3D having distance from ”:

Of course this is equivalent to

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

.

Next let’s look at the ray. A ray starting at point and pointing in the direction is the set of all point: . (note that 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:

with unknown .

Setting , and using as is a unit-vector we get:

a simple quadratic equation in .

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

The normal of a point on the sphere is just the direction of to the point (just the vector from 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 . 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