# 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 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
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)
| Negative -> []
| NearZero -> [ k0 ]


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