Ray tracing is a simple way to create images of 3D scenes. The method casts rays from the camera into the 3D scene and determines which object the ray intersects first. This approach makes some problems easy to solve:
-
Shadows can be simulated by casting a ray from the intersection point towards the light to see if the intersection point has line-of-sight to the light.
-
Reflections can be simulated by casting a second ray off the surface in the reflected direction.
Read more about ray tracing in the current Wikipedia article
This ray tracer generates a scene composed of a floor with a procedural texture and a set of recursively nested spheres:
This example program is freely available in two forms:
The program has several interesting aspects:
Types
The main types used by the program are defined succinctly and elegantly in F# as records and variants:
type material = { color: vector; shininess: float }
type sphere = { center: vector; radius: float }
type obj = Sphere of sphere * material | Group of sphere * obj list
type ray = { origin: vector; direction: vector }
These types actually become .NET objects but the programmer is freed from having to define constructors, members and so on.
Intersection
The core of this ray tracer is a recursive intersection function that hierarchically decomposes the sphereflake into its constituent parts:
let rec intersect_spheres ray (lambda, _, _ as hit) = function
| Sphere (sphere, material) ->
let lambda' = ray_sphere ray sphere in
if lambda' >= lambda then hit else
let normal = unitise (ray.origin + (lambda' $* ray.direction) - sphere.center) in
lambda', normal, material
| Group (bound, scenes) ->
let lambda' = ray_sphere ray bound in
if lambda' >= lambda then hit else List.fold_left (intersect_spheres ray) hit scenes
This function leverages the benefits of functional programming in several ways:
- Recursion is used to implement the core algorithm.
- Pattern matching is used to decompose data structures and name their parts, e.g.
lambda and hit.
- Pattern matching is used to perform the equivalent of virtual function dispatch, e.g. handling
Sphere or Group.
- A higher-order function
List.fold_left is used to apply the intersect_spheres function to the child spheres of a Group.
This design also leverages features seen in imperative languages:
- Vector and matrix routines are provided by the standard library.
- Operator overloading allows conventionally-named arithmetic operators to be applied to vectors and matrices.
Functional programming makes it easy to perform computations in parallel, on different CPUs.
Parallel processing
All of the rays used to trace the scene can be treated individually. This makes ray tracing ideally suited to parallel processing.
This ray tracer breaks the image down into horizontal runs of pixels called rasters. The set of rasters that make up the image are dispatched to a .NET threadpool which transparently farms out the work to any available CPUs.
As the image appears in a window that can be resized, it is important to quit computations early when their results will no longer be used because the image has been resized. This is achieved by having a list of completed rasters stored as a reference to a reference to a list:
let rasters = ref (ref [])
The first reference is used to replace the list of completed rasters with a new list and the second reference is used to prepend a new raster when it is completed.
A function raster computes a raster and pushes its result onto r but bails early if the current list of rasters rasters is no longer the one it is building:
let raster r w h y =
try
let data = Array.init w (fun x -> if !rasters != r then raise Exit; pixel w h x y) in
Idioms.lock !rasters (fun () -> r := (h - 1 - y, data) :: !r)
with Exit -> ()
This is an easy way to avoid wasted computation in the absence of an abort function for threads in a thread pool.
GUI
The object oriented parts of the F# language are mostly made redundant by the ability to do functional programming. However, interoperability with the rest of .NET is an important capability that is well suited to object oriented programming.
The GUI is created by deriving a class Form1 from the WinForms class Form:
type Form1 = class
inherit Form
...
end
The Form1 class contains a bitmap for the current image and overrides the OnPaint and OnResize members.
The OnPaint member is made to copy all completed rasters into the form’s bitmap and then draw the bitmap into the window:
override form.OnPaint e =
Idioms.lock !rasters (fun () ->
let draw(y, data) = Array.iteri (fun x c -> try form.bitmap.SetPixel(x, y, c) with _ -> ()) data in
List.iter draw (! !rasters);
!rasters := []);
let r = new Rectangle(0, 0, form.Width, form.Height) in
e.Graphics.DrawImage(form.bitmap, form.ClientRectangle, r, GraphicsUnit.Pixel)
The OnResize member is made to replace the list of completed rasters with a new one (causing all outstanding threads to quit after their next pixel completes) and replaces the form’s bitmap with a new one before invalidating the form to force a redraw.
override form.OnResize e =
rasters := ref [];
form.bitmap
Despite the sophistication of this application, the entire program is tiny thanks to the expressiveness of the F# programming language
