Ray tracing [21, 7] is a now classical technique for computing 2d-images from 3d-scenes. The general principle of ray tracing is to cast light rays from the viewpoint of an observer into the scene. To render a scene as a w × h bitmap image, one casts the w × h rays defined by the observer viewpoint and the position of the w × h picture elements (pixels) of the image plane, which stands in front of the observer. One then computes the intersection of this primary ray with the scene. Reflections on object and the computation of illumination imply casting more rays. The whole process involves much computation.
This simple introduction should be sufficient to grasp the basic structure of a ray tracer. Our sequential ray tracer has not been written by us, but by the team “Camls R’Us” as an entry [1] for the ICFP programming contest of year 2000. Although written in three days, the program is of significant size (1729 lines, disregarding comments and empty lines).
Scenes are represented internally as the following (OCaml) record
type, a field of module Scene
.
In the type above, file
is the name of the file where to save the image,
wid
and ht
are the image width and height respectively.
The obj
field holds the internal representation of the scene.
We omit some of the fields in the scene record, such as the
definition of lights, observer field of view, etc.
Bitmap images are Ppm images, a simple image format, where an image
file basically is a sequence of colors encoded as
three eight-bits values.
In the original ray tracer, rendering operations are performed by the
module Render
that exports only one function render
,
as shown by its interface file.
Notice that Render.render
returns ()
because it saves the
bitmap it computes. Let us assume a function Ray.render_pxl
of
type Scene.t -> int -> int ->
color
that performs the
casting of a primary ray and all subsequent operations, finally
returning the color4 of the pixel of the image plane of which coordinates are
given as arguments. Then, one easily writes Render.render
by
two nested for
loops.
The problem statement of the contest [16] defines a language, Gml, for both describing the scene and the rendering conditions. This specification naturally impacts the design of the Camls’R Us ray tracer.
Eval
), with the following peculiarities:
Render.render
, all scene components being
retrieved from the interpreter stack.
It is to be noticed that there can be several render
instructions in a given program.
Our strategy for distributed execution is straightforward: all programs involved will execute the same Gml program, however they will react to the render instruction differently. A distinguished program, the master, controls the work of others. All other programs are slaves and they perform the rendering operations. For the master to distribute the work to the slaves, we need to define an unit of work smaller than the image. We call this unit a subimage. A simple choice for the subimage is a line (or several lines), since images are easily encoded as arrays of lines. More precisely master and slaves behave as follow
Master
| Slave
|
Observe that master and slaves agree on the scenes because they execute the same Gml program, Gml being a deterministic language.
Our design has the merit of simplicity:
alterations to the original, sequential, ray tracer are minimized.
In particular, the source of the sequential ray tracer includes the
compilation unit Eval
of which idealized code is as follows:
a definition of the values of Gml (type value
),
a recursive function that
implements a stack-based interpreter (function eval
), and a function
that starts the evaluation (function eval_program
) — see
Figure 1 for the original implementation and signature file.
Implementation, file eval.mltype value = | … | I of integer | S of string | O of Obj.t (* 3d object *) | … let rec eval env stack code = match code, stack with | ... (* Example of an instruction: integer addition *) | Op_addi::code, I i2::I i1::stack -> eval env (I (i1+i2)::stack) code (* Render instruction *) | Op_render::code, S file::I ht::I wid::O obj::…::stack -> let sc = { file=file ; wid=wid ; ht=ht ; obj=obj ; ... } in Render.render sc ; eval env stack code | … (* Entry point *) let eval_program code = eval [] [] codeInterface, file eval.mlival eval_program : Gml.tok list -> unit
The new implementation of Eval
simply abstracts out module Render
,
that is, it defines a functor — see Figure 2.
Implementation, file eval.mlmodule Make (Render : sig val render : Scene.t -> unit end) = struct ⋯ Original code ⋯ endInterface, file eval.mlimodule Make : functor (Render : sig val render : Scene.t -> unit end) -> sig val eval_program : Gml.tok list -> unit end
Master and slave apply the functor Eval.Make
to different modules,
RenderMaster
and RenderSlave
respectively,
yielding two different interpreters.
Another modification is worth signaling: as subimages are made of
lines, we separate the nested loops of the sequential render
.
The inner loop goes into the Ray
module, yielding a new
Ray.render_line
function of type Scene.t ->
int
-> string
that takes a scene and a line number as arguments, and that returns a compact
representation of the colors of the pixels in the line.
color
is the type of
colors, in practice a color is an integer of which 24 bits are
used.