Learning F# — Writing A Ray Tracer

Dec 30, 2019 - fsharp

Coming to F# with almost no prior .NET experience can be a bit daunting, since one doesn’t only have to learn the language, but its entire huge ecosystem. So to get some experience on a bigger project I got myself a copy Jamis Buck’s excellent book The Ray Tracer Challenge and am slowly working my way through it. Due to the holidays, I didn’t get quite as far as I hoped yet, but you can follow along with development on the GitLab repository. Here’s what I learned/implemented so far.

Project Layout

This is one of the things that’s probably obvious for seasoned .NET developers, but it took me a while to figure out the difference between projects and solutions. I settled on two projects, one for the main code (Raytracer), one for the tests (Raytracer.Tests, using FsUnit.Xunit).

├── LICENSE
├── README.md
├── Raytracer
│   ├── Canvas.fs
│   ├── Color.fs
│   ├── Constants.fs
│   ├── Matrix.fs
│   ├── Program.fs
│   ├── Raytracer.fsproj
│   ├── Tuples.fs
│   ├── bin
│   └── obj
├── Raytracer.Tests
│   ├── CanvasTests.fs
│   ├── ColorTests.fs
│   ├── MatrixTests.fs
│   ├── Program.fs
│   ├── Raytracer.Tests.fsproj
│   ├── Scripts
│   ├── TestUtilities.fs
│   ├── TuplesTests.fs
│   ├── bin
│   └── obj
├── Raytracer.sln
└── img
    └── ch02-projectile.ppm

Note: you may have noticed the Scripts folder within the test project. The first two chapters of the book finish with writing little scripts for exercising the code written up to that point. I considered adding a third project for them, but decided that’d be overkill so just added them to the existing test project:

Types

Vectors and Points

The book starts off by defining a single tuple type and using them for both points and vectors. I didn’t like this approach since functions like magnitude only make sense for vectors, not points. I went back and forth on the implementation a few times, even using classes in F# for the first time, but in the end, I decided that a little duplication is less harmful than the wrong abstraction. This way I could potentially change the implementation of one type (e.g. with Vector4 for performance reasons) without affecting the other.

namespace Raytracer.Types

open Raytracer.Constants

module rec Tuples =
    module Point =
        type T =
            { X : float
              Y : float
              Z : float
              W : float }

            static member (+) (p, v : Vector.T) =
                { X = p.X + v.X
                  Y = p.Y + v.Y
                  Z = p.Z + v.Z
                  W = p.W + v.W }

            static member (-) (p, v : Vector.T) =
                { X = p.X - v.X
                  Y = p.Y - v.Y
                  Z = p.Z - v.Z
                  W = p.W - v.W }

            static member (-) (p1, p2) : Vector.T =
                { X = p1.X - p2.X
                  Y = p1.Y - p2.Y
                  Z = p1.Z - p2.Z
                  W = p1.W - p2.W }

            static member (.=) (p1, p2) =
                abs (p1.X - p2.X) < epsilon && abs (p1.Y - p2.Y) < epsilon
                && abs (p1.Z - p2.Z) < epsilon && abs (p1.W - p2.W) < epsilon

        let make x y z =
            { X = x
              Y = y
              Z = z
              W = 1.0 }

    module Vector =
        type T =
            { X : float
              Y : float
              Z : float
              W : float }

            static member (+) (v1, v2) =
                { X = v1.X + v2.X
                  Y = v1.Y + v2.Y
                  Z = v1.Z + v2.Z
                  W = v1.W + v2.W }

            static member (-) (v1, v2) =
                { X = v1.X - v2.X
                  Y = v1.Y - v2.Y
                  Z = v1.Z - v2.Z
                  W = v1.W - v2.W }

            static member (~-) (v) =
                { X = -v.X
                  Y = -v.Y
                  Z = -v.Z
                  W = -v.W }

            static member ( * ) (v, scalar) =
                make (v.X * scalar) (v.Y * scalar) (v.Z * scalar)

            static member (/) (v, scalar) =
                { X = v.X / scalar
                  Y = v.Y / scalar
                  Z = v.Z / scalar
                  W = v.W / scalar }

            static member (.=) (v1, v2) =
                abs (v1.X - v2.X) < epsilon && abs (v1.Y - v2.Y) < epsilon
                && abs (v1.Z - v2.Z) < epsilon && abs (v1.W - v2.W) < epsilon

        let make x y z =
            { X = x
              Y = y
              Z = z
              W = 0.0 }

        let magnitude v = sqrt (v.X * v.X + v.Y * v.Y + v.Z * v.Z)

        let normalize v =
            let mag = magnitude v
            make (v.X / mag) (v.Y / mag) (v.Z / mag)

        let dot v1 v2 = v1.X * v2.X + v1.Y * v2.Y + v1.Z * v2.Z

        let cross v1 v2 =
            make (v1.Y * v2.Z - v1.Z * v2.Y) (v1.Z * v2.X - v1.X * v2.Z)
                (v1.X * v2.Y - v1.Y * v2.X)

This is all pretty standard, but some things may be worth pointing out:

The Tuples module needs the rec keyword, so the two contained types can reference each other.
I didn’t want to define too many custom operators and module functions can be clunky, so I used static methods for providing overrides for the arithmetic operations.
Floating-point arithmetic can become messy, so there’s a custom equality operator (.=) to check that values are equal to each other within a given epsilon (defined as 0.0001 in the Raytracer.Constants module).

Color

This simple module represents an RGB color and follows a very similar approach to Point and Vector:

namespace Raytracer.Types

module rec Color =
    type T =
        { Red : float
          Green : float
          Blue : float }

        static member (+) (c1, c2) =
            make (c1.Red + c2.Red) (c1.Green + c2.Green) (c1.Blue + c2.Blue)

        static member (-) (c1, c2) =
            make (c1.Red - c2.Red) (c1.Green - c2.Green) (c1.Blue - c2.Blue)

        static member ( * ) (c, scalar) =
            make (c.Red * scalar) (c.Green * scalar) (c.Blue * scalar)

        static member ( * ) (c1, c2) =
            make (c1.Red * c2.Red) (c1.Green * c2.Green) (c1.Blue * c2.Blue)

    let make r g b =
        { Red = r
          Green = g
          Blue = b }

    let black = make 0.0 0.0 0.0
    let red = make 1.0 0.0 0.0

Canvas

Now that we have points, vectors, and colors, we are almost ready to draw things, but for that, we need a canvas first. The following module represents one and allows us to save it as PPM image.

namespace Raytracer.Types

open System
open System.Text.RegularExpressions

module Canvas =
    type T =
        { Width : int
          Height : int
          Pixels : Color.T [,] }

    let make width height =
        { Width = width
          Height = height
          Pixels = Array2D.create height width Color.black }

    let writePixel canvas x y color = Array2D.set canvas.Pixels y x color

    let pixelAt canvas x y = Array2D.get canvas.Pixels y x

    let toPpm canvas =
        let clamp f =
            let rgbVal = 255.0 * f |> round
            Math.Clamp(int rgbVal, 0, 255)

        let colorToRgb (c : Color.T) =
            sprintf "%d %d %d" (clamp c.Red) (clamp c.Green) (clamp c.Blue)

        let splitLongLines (rgbs : seq<string>) =
            let row = String.Join(" ", rgbs)
            Regex.Replace(row, "[\s\S]{1,69}(?!\S)",
                          (fun m -> m.Value.TrimStart(' ') + "\n"))
                 .TrimEnd('\n')

        let pixelsToString canvas =
            canvas.Pixels
            |> Array2D.map colorToRgb
            |> Seq.cast<string>
            |> Seq.chunkBySize canvas.Width
            |> Seq.map splitLongLines
            |> String.concat "\n"

        let header =
            sprintf "P3\n%d %d\n255" canvas.Width canvas.Height

        let pixels = pixelsToString canvas
        sprintf "%s\n%s\n" header pixels

The builtin Array2D class is convenient, but surprisingly lacks many higher-order functions, which results in more imperative code or casts to a sequence via Seq.cast. I’m still considering whether or not jagged arrays (string[][]) would be preferable over multidimensional arrays (string[,]) here, but decided to leave it as-is for now.

Matrix

While I’m not quite finished with my matrix implementation yet, it currently looks like this is also based on Array2D so the code ended up quite imperative in places :-(

namespace Raytracer.Types

open Raytracer.Constants
open Raytracer.Types.Tuples

module Matrix =
    type T =
        { Dimension : int
          Entries : float [,] }

        static member (.=) (m1, m2 : T) =
            let allWithinEpsilon =
                let len = m1.Dimension - 1
                seq {
                    for r in 0 .. len do
                        for c in 0 .. len do
                            if abs (m1.[r, c] - m2.[r, c]) > epsilon then
                                yield false
                }
                |> Seq.forall id

            m1.Dimension = m2.Dimension && allWithinEpsilon

        static member ( * ) (m1, m2) =
            let len = m1.Dimension - 1
            let result = Array2D.zeroCreate m1.Dimension m1.Dimension

            for r in 0 .. len do
                for c in 0 .. len do
                    let row = m1.Entries.[r, *]
                    let col = m2.Entries.[*, c]
                    Array.fold2 (fun sum r c -> sum + r * c) 0.0 row col
                    |> Array2D.set result r c

            { Dimension = m1.Dimension
              Entries = result }

        static member ( * ) (m, v : Vector.T) : Vector.T =
            let len = m.Dimension - 1

            let result =
                seq {
                    for r in 0 .. len ->
                        let row = m.Entries.[r, *]
                        let vArray = [| v.X; v.Y; v.Z; v.W |]
                        Array.fold2 (fun sum r c -> sum + r * c) 0.0 row vArray
                }
                |> Seq.toArray

            Vector.make result.[0] result.[1] result.[2]

        member x.Item
            with get (r, c) = x.Entries.[r, c]

    let make rows =
        let dim = List.length rows

        if dim >= 2 && dim <= 4
           && List.forall (fun l -> List.length l = dim) rows then
            { Dimension = dim
              Entries = array2D rows }
        else
            failwith "Matrix must be square with dimension 2, 3 or 4"

    let identity =
        make
            [ [ 1.; 0.; 0.; 0. ]
              [ 0.; 1.; 0.; 0. ]
              [ 0.; 0.; 1.; 0. ]
              [ 0.; 0.; 0.; 1. ] ]

    let transpose m =
        [ for c in [ 0 .. m.Dimension - 1 ] do
            yield m.Entries.[*, c] |> List.ofArray ]
        |> make

I briefly considered using the SIMD-enabled Matrix4x4 type, but that doesn’t accommodate the 2x2 and 3x3 matrices the book requires. Of course, I could also have used some external matrix library, but I thought it’d be more fun and a better learning experience to implement everything by myself.

The First Image

The first chapter finishes with writing a little script for calculating the flight path of a projectile given a starting position and velocity, as well as an environment consisting of gravity and wind. At the end of the second chapter, this script gets enhanced to plot the trajectory onto a canvas and store it as PPM image.

#load "../../Raytracer/Color.fs"
#load "../../Raytracer/Canvas.fs"
#load "../../Raytracer/Tuples.fs"

open System.IO
open Raytracer.Types
open Raytracer.Types.Tuples

type Projectile =
    { position : Point.T
      velocity : Vector.T }

type Environment =
    { gravity : Vector.T
      wind : Vector.T }

let tick env p =
    { position = p.position + p.velocity
      velocity = p.velocity + env.gravity + env.wind }

// Projectile starts one unit above the origin.
// Velocity is normalized and multiplied to increase its magnitude.
let mutable projectile =
    { position = Point.make 0.0 1.0 0.0
      velocity = (Vector.make 1.0 1.8 0.0 |> Vector.normalize) * 11.25 }

// gravity -0.1 unit/tick, and wind is -0.01 unit/tick.
let env =
    { gravity = Vector.make 0.0 -0.1 0.0
      wind = Vector.make -0.01 0.0 0.0 }

let canvas = Canvas.make 900 550
let color = Color.make 1.0 0.7 0.7

while projectile.position.Y > 0.0 do
    let canvasX =
        projectile.position.X
        |> round
        |> int

    let canvasY = canvas.Height - (int <| round projectile.position.Y)
    if canvasX >= 0 && canvasX < canvas.Width && canvasY >= 0
       && canvasY < canvas.Height then
        Canvas.writePixel canvas canvasX canvasY color
    projectile <- tick env projectile

File.WriteAllText("img/ch02-projectile.ppm", Canvas.toPpm canvas)

Here’s the result:

projectile trajectory

While it’s admittedly not much to look at, it was immensely satisfying to see an image generated from my code.

It’s A Wrap

So far this has been a really fun challenge and a good learning experience. If you have any questions or suggestions please let me know, I’m sure the code could be improved in various places. It would also be great to compare solutions, so if you’re working on a ray tracer in F# I’d love to see the code!