Learning F# — Writing A Ray Tracer
- 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 therec
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 theRaytracer.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:
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!