loading...

Learning F# — Writing A Ray Tracer

citizen428 profile image Michael Kohl Originally published at citizen428.net ・8 min read

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!

Posted on by:

citizen428 profile

Michael Kohl

@citizen428

I dev @ DEV. Your friendly neighborhood anarcho-cynicalist. ¯\_(ツ)_/¯ and (╯°□°)╯︵ ┻━┻) are my two natural states. Tag mod for #ruby, #fsharp, #ocaml

Discussion

markdown guide
 

This is great idea for a first project in F#. Congrats for getting it to work. I have a bunch of comments, starting with:

The Tuples module needs the rec keyword, so the two contained types can reference each other.

This is a cool feature that I didn't know about, but do you really need it in this case? It looks to me like Vector doesn't depend on Point at all, but I could be missing something. In general, I think it's a good idea to avoid circular references in F# where at all possible. Sometimes it can be frustrating, but it usually leads to clearer, simpler code. In this case, for example, I think you would no longer need a top-level Tuples module at all.

Also, I'm curious about your decision to nest all your types as .T under the corresponding module. I've seen this before, but I don't really see the benefit now that you can define both type and module at the top level and give them the same name (e.g. type Vector and module Vector). That way the name of the type is just Vector instead of Vector.T.

I'll stop there for now. Again, nice work!

 

This is great idea for a first project in F#. Congrats for getting it to work.

Thanks. I've finished the Exercism track for F#, lots of other challenges and also was part of the last round of the F# Foundation's mentorship program, so I'm not new to the language itself, "just" to building bigger projects in it.

This is a cool feature that I didn't know about

This is where my knowledge of OCaml comes in handy, the module systems are quite similars, though OCaml's is more full featured. For example F# has no support for functor modules, i.e. modules parameterized by another, but instead relies on OOP mechanisms to achieve similar results.

do you really need it in this case?

In fact, no. As I said, I rewrote these types a couple of times, this was an artifact of those attempts. I separated them now and made sure Vector gets compiled before Point. Note that Vector itself still needs the rec keyword, so the static members can access the module level make function which is defined further down the file.

I think it's a good idea to avoid circular references in F#

Recursive modules are not necessarily circular dependencies, they just make lexical bindings available in the inner scope, where they usually wouldn't be. Same as with functions:

let fact = function
| 1 -> 1
| n -> n * fact (n - 1)

This won't work since the binding fact is not available inside the scope of the function, but adding rec fixes that. The same was true for my Tuples module.

I think you would no longer need a top-level Tuples module

That is correct and the module is now history, thanks!

Also, I'm curious about your decision to nest all your types as .T under the corresponding module.

Another habit from OCaml 😃 But also it allows hiding the implementation of the type from consumers through .fsi files.

Say for example you have type Vector and module Vector. By having the type public, you've now committed to an implementation, since people may be using the type directly. On the other hand, a nested type can easily be made abstract via a signature file:

module Vector =
    type T

    // Instantiate a new vector by specifying x, y, and z coordinates
    val make : float -> float -> float -> T

    ...

This gives you all the benefits of the type system, but people are no longer able to manually construct vectors, which means you're free to change the implementation whenever you want. I don't know good F# documentation for this, but Real World OCaml has a section on it:

Signatures and Abstract Types

I guess in F# you could also achieve something similar via standard .NET access modifiers (private etc), but I'm much more familiar with the OCaml way. To quote Scott Wlaschin:

The [nested type] approach is more common for those used to other functional languages.

Anyway, thanks for the feedback and happy New Year 🎉

 

I see. Thanks for the detailed response.

Note that Vector itself still needs the rec keyword, so the static members can access the module level make function which is defined further down the file.

You might want to consider using type extensions to achieve this without the need for a forward reference:

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

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

a nested type can easily be made abstract via a signature file

Ah, that's interesting, but would prevent access to the individual X, Y, Z, W values of the vector as well, right? That seems like it would be too limiting in your case.

Here are some additional thoughts on your implementation:

[Matrix] is also based on Array2D so the code ended up quite imperative in places

You're referring to for loops that generate sequences? IMHO, this approach is actually quite elegant and fully consistent with functional programming, so I would hope you keep it. However, for clarity, I would change this:

if abs (m1.[r, c] - m2.[r, c]) > epsilon then
    yield false

To this:

yield abs (m1.[r, c] - m2.[r, c]) <= epsilon

You can also simplify this:

seq {
   // code
}
|> Seq.toArray

To this:

[|
    // code
|]

I would also consider rewriting your final while loop to avoid the need for a mutable projectile. I suggest generating a sequence of immutable projectiles instead. Something like this:

let rec fly projectile =
    seq {
        if projectile.position.Y > 0.0 then
            yield projectile
            yield! projectile |> tick env |> fly
    }
for projectile in fly { position = ...; velocity = ... } do
    if onCanvas ... then
       Cavas.writePixel ...

I hope this is helpful. Happy New Year!

Thanks for the detailed response.

Likewise 😃

You might want to consider using type extensions to achieve this without the need for a forward reference

I could do that. I don't see any problem with having the module be recursive, but it's certainly not necessary. I'll consider it.

Ah, that's interesting, but would prevent access to the individual X, Y, Z, W values of the vector as well, right?

There are people in the OCaml community who would consider that a good thing. They'd instead go for module level accessors when dealing with abstract types, so something like Vector.x v instead of v.X. Directly exposing a record type can lead to pretty strong coupling, but that's probably more of a concern when publishing a library than when writing a toy ray tracer. Maybe I'll just embrace a more .NET approach (type + module of the same name, as you suggested) and drop the nested T. Though at this point I'd rather build more features than spending time on refactoring my types.

You're referring to for loops that generate sequences? IMHO, this approach is actually quite elegant and fully consistent with functional programming

I was more talking about things like Array2D.set, which mutates and returns (). Good suggestion regarding the changed yield statement though, I'll incorporate that, thanks!

You can also simplify this

Somehow I always forget that F# has list and array comprehensions, which is weird because I frequently use them in other languages 🤷🏻‍♂️

I suggest generating a sequence of immutable projectiles instead.

I had something similar at first, but saw no real benefit in it. One of the nice things about F# is that it's very pragmatic, and sometimes a while loop is all you need, especially in a throwaway script.

I hope this is helpful.

Very helpful, thanks again! Happy New Year to you too.

I ended up incorporating all of your feedback in some way or another, so thanks again!

 

What a fun project you've got going here 😀

As for multidimensional arrays vs jagged arrays, you will supposedly get better performance with jagged arrays: Here and Jon Skeet's comment to his own answer here.

This is the first time I see slicing in actions. I did not know you could do this. Very cool.

let row = m.Entries.[r, *] 

Well done. I am looking forward to the sequel.

 

What a fun project you've got going here 😀

It is indeed, I highly recommend the book!

As for multidimensional arrays vs jagged arrays, you will supposedly get better performance with jagged arrays: Here and Jon Skeet's comment to his own answer here.

I was reading up on this before, and the consensus seems to support your view, though there are some conflicting opinions. Be that as it may, semantically a rectangular array is closer to a matrix than a jagged array and there's something to be said for that.

This is the first time I see slicing in actions. I did not know you could do this.

I got it from here. This specific form was added in F# 3.1, so has been around for quite a while.

Well done. I am looking forward to the sequel.

Thank you! 😀 In the meantime I finished the basic matrix implementation (determinant, cofactor, minor and inversion), it's on GitLab if you're interested:

gitlab.com/citizen428/Raytracer/bl...