Previous Up Next

5  Ray tracing and its parallelization

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.

type t = { file : string ; wid : int ; ht ; int ; obj : Obj.t ; ... }

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.

val render : Scene.t -> unit

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.

let render sc = let oc = open_out_bin sc.file in (* open output, ppm, file *) Printf.fprintf oc "P6\n%d %d\n255\n" sc.wid sc.ht; (* Ppm header *) for j = sc.ht - 1 downto 0 do for i = 0 to sc.wid-1 do let color = Ray.render_pxl sc i j in ouput_color oc color done done ; close_out oc

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.

  1. The Gml program is parsed.
  2. The resulting abstract syntax tree is evaluated by an interpreter (module Eval), with the following peculiarities:
    1. To execute the instruction render that commands the production of an image, the interpreter calls 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.
    2. Other instructions are Constructive Solid Geometry operations, 3d-transforms, arithmetics, if instructions, function calls, etc.
  3. The ray tracer ends once the interpreter has returned.

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
  1. Parse the Gml file and make the abstract syntax tree available to slaves.
  2. Interpret the Gml program. Instruction render starts the concurrent process of allocating subimages to slaves and of collecting their results. When all subimages are present, the image is saved.
  3. End when all the images have been saved.
    
Slave
  1. Connect to the master, register as a potential worker, and retrieve the Gml abstract syntax tree.
  2. Interpret the Gml program. Instruction render starts accepting subimages descriptions from the master, computing subimages, and sending them back to the master.
  3. End when the master is done.

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.


Figure 1: Original source files for Eval
Implementation, file eval.ml
type 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 [] [] code
Interface, file eval.mli
val 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.


Figure 2: New source files for Eval
Implementation, file eval.ml
module Make (Render : sig val render : Scene.t -> unit end) = struct ⋯ Original code ⋯ end
Interface, file eval.mli
module 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.


4
color is the type of colors, in practice a color is an integer of which 24 bits are used.

Previous Up Next