The Third Annual ICFP Programming Contest (Version 1.18)
<7>The Third Annual ICFP Programming Contest
(Version 1.18)7>
If you are viewing this document using Netscape, you may need to configure
your browser to see the symbols properly.
See http://para.inria.fr/~maranget/hevea/doc/browser.html
for details.
This document is also available in pdf
and postscript formats.
<6>1 The problem6>
This year's ICFP programming challenge is to implement a
ray tracer.
The input to the ray tracer is a scene description written in a
simple functional language, called GML.
Execution of a GML program produces zero, or more, image files,
which are in PPM format.
A web page of sample images, along with the GML inputs that were used
to produce them, is linked off of the
contest home page.
The feature set of GML is organized into
three tiers.
Submissions must implement
the first tier of features and extra credit will be given to
submissions that implement the second or third tiers.
Submissions will be evaluated on three scales: correctness of the
produced images, run-time performance, and the
tier of implemented GML features.
GML has primitives for defining
simple geometric objects (e.g., planes, spheres,
and cubes) and lighting sources.
The surface properties used to render the objects
are specified as functions in GML itself.
In addition to supporting scene description, GML also has a
render operator that renders a scene to an
image file.
For each pixel in the output image, the render command
must compute a color.
Conceptually, this color is computed by tracing the path of the
light backwards from the eye of the viewer, to where it bounced off an
object, and ultimately back to the light sources.
This document is organized as follows.
Section 2 describes the syntax and general semantics of the
modeling language.
It is followed by Section 3, which describes those aspects of
the language that are specific to ray tracing.
Section 4 specifies the submission requirements
and Section 5 provides hints about algorithms and pointers
to online resources to get you started.
The Appendix gives a summary of the operators in the
modeling language.
This document is a bit on the long side because we have tried to make it
complete and self-contained.
(In fact, the LATEX source for this document is longer than our
sample implementation!)
<6>2 The modeling language6>
The input to the ray tracer is a scene description (or model)
written in a functional modeling language called GML.
The language has a syntax and execution model that is similar to
PostScript (and Forth), but GML is lexically scoped and
does not have side effects.
<5>2.1 Syntax5>
A GML program is written using a subset of the printable ASCII
character set (including space), plus tab, return, linefeed and vertical
tab characters.
The space, tab, return, linefeed and vertical
tab characters are called whitespace.
The characters %, [,
], {, } are special
characters.
Any occurrence of the character ``%'' not inside a string
literal (see below) starts a comment, which runs to the end of the
current line.
Comments are treated as whitespace when tokenizing the input file.
The syntax of GML is given in Figure 1 (an opt
superscript means an optional item and a * superscript means
a sequence of zero or more items).
TokenList
::=
TokenGroup<2>*2>
TokenGroup
::=
Token
|
{ TokenList }
|
[ TokenList ]
Token
::=
Operator
|
Identifier
|
Binder
|
Boolean
|
Number
|
String
Figure 1: GML grammar
A GML program is a token list, which is a sequence of
zero or more token groups.
A token group is either a single token, a function (a token
list enclosed in `{' `}'), or an array (a token
list enclosed in `[' `]').
Tokens do not have to be separated by white space when it is
unambiguous.
Whitespace is not allowed in numbers, identifiers, or binders.
Identifiers must start with an letter and can contain letters, digits,
dashes (`-'), and underscores (`_').
A subset of the identifiers are used as predefined operators, which
may not be rebound.
A list of the operators can be found in the appendix.
A binder is an identifier prefixed with a `/' character.
Booleans are either the literal true or the literal false.
Like operators, true and false may not be rebound.
Numbers are either integers or reals.
The syntax of numbers is given by the following grammar:
Number
::=
Integer
|
Real
Integer
::=
-<2>opt2> DecimalNumber
Real
::=
-<2>opt2> DecimalNumber . DecimalNumber
Exponent<2>opt2>
|
-<2>opt2> DecimalNumber Exponent
Exponent
::=
e -<2>opt2> DecimalNumber
|
E -<2>opt2> DecimalNumber
where a DecimalNumber is a sequence of one or more decimal digits.
Integers should have at least 24-bits of precision and reals should
be represented by double-precision IEEE floating-point values.
Strings are written enclosed in double quotes (`"') and may contain
any printable character other than the double quote (but including the
space character).
There are no escape sequences.
<5>2.2 Evaluation5>
We define the evaluation semantics of a GML program using an abstract machine.
The state of the machine is a triple <ENV; a; c>, where
ENV is an environment mapping identifiers to values, a is a stack of
values, and c is a sequence of token groups.
More formally, we use the following semantic definitions:
i in
Int
i in
BaseValue = Boolean E Int E Real E String
v in
Value = BaseValue E Closure E Array
E Point E Object E Light
(ENV, c)
in
Closure = Env # Code
a,[v<2>12> ... v<2>n2>]
in
Array = Value<2>*2>
ENV in
Env = Id --> Value
a,b in
Stack = Value<2>*2>
c in
Code = TokenList
Evaluation from one state to another is written as
<ENV; a; c> = <ENV'; a'; c'>
.
We define =<2>*2> to be the transitive closure of =.
Figure 2 gives the GML evaluation rules.
<ENV; a; i c> = <ENV; a i; c>
(1)
<ENV; a v; /x c> = <ENV{x := v}; a; c>
(2)
<ENV; a; x c> = <ENV; a ENV(x); c>
(3)
<ENV; a; {c'} c> = <ENV; a (ENV, c'); c>
(4)
<ENV'; a; c'> =<2>*2> <ENV''; b; >
<ENV; a (ENV', c'); apply c> = <ENV; b; c>
(5)
<ENV; ; c'> =<2>*2> <ENV'; v<2>12> ... v<2>n2>; >
<ENV; a; [c'] c> = <ENV; a [v<2>12> ... v<2>n2>]; c>
(6)
<ENV<2>12>; a; c<2>12>> =<2>*2> <ENV''; b; >
<ENV; a true (ENV<2>12>, c<2>12>) (ENV<2>22>, c<2>22>); if c> = <ENV; b; c>
(7)
<ENV<2>22>; a; c<2>22>> =<2>*2> <ENV''; b; >
< ENV; a false (ENV<2>12>, c<2>12>) (ENV<2>22>, c<2>22>); if c> = <ENV; b; c>
(8)
a OPERATOR a'
<ENV; b a; OPERATOR c> = <ENV; b a'; c>
(9)
Figure 2: Evaluation rules for GML
In these rules, we write stacks with the top to the right (e.g.;
a x is a stack with x as its top element) and token
sequences are written with the first token on the left.
We use to signify the empty stack and the empty code sequence.
Rule 1 describes the evaluation of a literal token, which is
pushed on the stack.
The next two rules describe the semantics of variable binding and
reference.
Rules 4 and 5 describe function-closure
creation and the apply operator.
Rule 6 describes the evaluation of an array expression; note
that body of the array expression is evaluated on an initially empty
stack.
The semantics of the if operator are given by
Rules 7
and 8.
The last evaluation rule (Rule 9) describes how an
operator (other than one of the control operators) is evaluated.
We write
a OPERATOR a'
to mean that the
operator OPERATOR transforms the stack a to the stack a'.
This notation is used below to specify the GML operators.
We write
Eval(c, v<2>12>, ..., v<2>n2>) = (v'<2>12>, ..., v'<2>n2>)
for when a program c yields (v'<2>12>, ..., v'<2>n2>) when applied
to the values v<2>12>, ..., v<2>n2>; i.e., when
<{}; v<2>12> v<2>n2>; c> =<2>*2> <ENV; v'<2>12> ,v'<2>n2>; >
.
There is no direct support for recursion in GML, but one can program
recursive functions by explicitly passing the function as an
extra argument to itself (see Section 2.7 for an example).
<5>2.3 Control operators5>
GML contains two control operators that can be used to
implement control structures.
These operators are formally defined in Figure 2, but we
provide an informal description here.
The apply operator takes a function closure,
(ENV, c), off the stack and evaluates c using the
environment ENV and the current stack.
When evaluation of c is complete (i.e., there are no more
instructions left), the previous environment is restored and
execution continues with the instruction after the apply.
Argument and result passing is done via the stack.
For example:
1 { /x x x } apply addi
will evaluate to 2.
Note that functions bind their variables according to the environment where
they are defined; not where they are applied.
For example the following code evaluates to 3:
1 /x % bind x to 1
{ x } /f % the function f pushes the value of x
2 /x % rebind x to 2
f apply x addi
The if operator takes two closures and a boolean off the
stack and evaluates the first closure if the boolean is true, and
the second if the boolean is false.
For example,
b { 1 } { 2 } if
will result in 1 on the top of the stack if b is true, and 2
if it is false
<5>2.4 Numbers5>
GML supports both integer and real numbers (which are represented by
IEEE double-precision floating-point numbers).
Many of the numeric operators have both integer and real versions, so
we combine their descriptions in the following:
n<2>12> n<2>22> addi/addf n<2>32>
computes the sum n<2>32> of the numbers n<2>12> and n<2>22>.
r<2>12> acos r<2>22>
computes the arc cosine r<2>22> in degrees of r<2>12>.
The result is undefined if r<2>12> < -1 or 1 < r<2>12>.
r<2>12> asin r<2>22>
computes the arc sine r<2>22> in degrees of r<2>12>.
The result is undefined if r<2>12> < -1 or 1 < r<2>12>.
r<2>12> clampf r<2>22>
computes r<2>22> =
i
0.0
r<2>12> < 0.0
1.0
r<2>12> > 1.0
r<2>12>
otherwise
.
r<2>12> cos r<2>22>
computes the cosine r<2>22> of r<2>12> in degrees.
n<2>12> n<2>22> divi/divf n<2>32>
computes the quotient n<2>32> of dividing the number n<2>12> by n<2>22>.
The divi operator rounds its result towards 0.
For the divi operator, if n<2>22> is zero, then the program
halts.
For divf, the effect of division by zero is undefined.
n<2>12> n<2>22> eqi/eqf b
compares the numbers n<2>12> and n<2>22> and pushes true if n<2>12>
is equal to n<2>22>; otherwise false is pushed.
r floor i
converts the real r to the greatest integer i that is less than or
equal to r.
r<2>12> frac r<2>22>
computes the fractional part r<2>22> of the real number r<2>12>.
The result r<2>22> will always have the same sign as the argument r<2>12>.
n<2>12> n<2>22> lessi/lessf b
compares the numbers n<2>12> and n<2>22> and pushes true if n<2>12>
is less than n<2>22>; otherwise false is pushed.
i<2>12> i<2>22> modi i<2>32>
computes the remainder i<2>32> of dividing i<2>12> by i<2>22>.
The following relation holds between divi and modi:
i2 (i1 divi i2) + (i1 mod i2) = i1
n<2>12> n<2>22> muli/mulf n<2>32>
computes the product n<2>32> of the numbers n<2>12> and n<2>22>.
n<2>12> negi/negf n<2>22>
computes the negation n<2>22> of the number n<2>12>.
i real r
converts the integer i to its real representation r.
r<2>12> sin r<2>22>
computes the sine r<2>22> of r<2>12> in degrees.
r<2>12> sqrt r<2>22>
computes the square root r<2>22> of r<2>12>.
If r<2>12> is negative, then the interpreter should halt.
n<2>12> n<2>22> subi/subf n<2>32>
computes the difference n<2>32> of subtracting the number n<2>22> from n<2>12>.
<5>2.5 Points5>
A point is comprised of three real numbers.
Points are used to represent positions, vectors, and colors (in the latter
case, the range of the components is restricted to [0.0, 1.0]).
There are four operations on points:
p getx x
gets the first component x of the point p.
p gety y
gets the second component y of the point p.
p getz z
gets the third component z of the point p.
x y z point p
creates a point p from the reals x, y, and z.
<5>2.6 Arrays5>
There are two operations on arrays:
arr i get v<2>i2>
gets the ith element of the array arr.
Array indexing is zero based in GML.
If i is out of bounds, the GML interpreter should terminate.
arr length n
gets the number of elements in the array arr.
The elements of an array do not have to have the same type and
arrays can be used to construct data structures.
For example, we can implement lists using two-element arrays for
cons cells and the zero-length array for nil.
[] /nil
{ /cdr /car [ car cdr ] } /cons
We can also write a function that ``pattern matches'' on the head
of a list.
{ /if-cons /if-nil /lst
lst length 0 eqi
if-nil
{ lst 0 get lst 1 get if-cons apply }
if
}
<5>2.7 Examples5>
Some simple function definitions written in GML:
{ } /id % the identity function
{ 1 addi } /inc % the increment function
{ /x /y x y } /swap % swap the top two stack locations
{ /x x x } /dup % duplicate the top of the stack
{ dup apply muli } /sq % the squaring function
{ /a /b a { true } { b } if } /or % logical-or function
{ /p % negate a point value
p getx negf
p gety negf
p getz negf point
} /negp
A more substantial example is the GML version of the recursive
factorial function:
{ /self /n
n 2 lessi
{ 1 }
{ n 1 subi self self apply n muli }
if
} /fact
Notice that this function follows the convention of passing itself as
the top-most argument on the stack.
We can compute the factorial of 12 with the expression
12 fact fact apply
<6>3 Ray tracing6>
In this section, we describe how the GML interpreter supports ray tracing.
<5>3.1 Coordinate systems5>
GML models are defined in terms of two coordinate systems:
world coordinates and object coordinates.
World coordinates are used to specify the position of lights
while object coordinates are used to specify primitive objects.
There are six transformation operators (described in
Section 3.3) that are used to map
object space to world space.
The world-coordinate system is left-handed.
The X-axis goes to the right, the Y-axis goes up, and the Z-axis
goes away from the viewer.
<5>3.2 Geometric primitives5>
There are five operations in GML for constructing primitive
solids: sphere, cube, cylinder, cone, and
plane.
Each of these operations takes a single function as an argument, which defines
the primitive's surface properties (see Section 3.6).
surface sphere obj
creates a sphere of radius 1 centered at the origin with surface
properties specified by the function surface.
Formally, the sphere is defined by x<2>22> + y<2>22> + z<2>22> 1.
surface cube obj
creates a unit cube with opposite corners (0,0,0) and (1,1,1).
The function surface specifies the cube's surface properties.
Formally, the cube is defined by 0 x 1,
0 y 1, and 0 z 1.
Cubes are a Tier-2 feature.
surface cylinder obj
creates a cylinder of radius 1 and height 1 with surface properties
specified by the function surface.
The base of the cylinder is centered at (0, 0, 0) and the top is centered
at (0, 1, 0) (i.e., the axis of the cylinder is the Y-axis).
Formally, the cylinder is defined by x<2>22> + z<2>22> 1 and
0 y 1.
Cylinders are a Tier-2 feature.
surface cone obj
creates a cone with base radius 1 and height 1 with surface
properties specified by the function surface.
The apex of the cone is at (0, 0, 0) and the base of the cone
is centered at (0, 1, 0).
Formally, the cone is defined by x<2>22> + z<2>22> - y<2>22> 0 and
0 y 1.
Cones are a Tier-2 feature.
surface plane obj
creates a plane object with the equation y = 0 with surface
properties specified by the function surface.
Formally, the plane is the half-space y 0.
<5>3.3 Transformations5>
Fixed size objects at the origin are not very interesting, so GML provides
transformation operations to place objects in world space.
Each transformation operator takes an object and one or more reals as arguments
and returns the transformed object.
The operations are:
obj r<2>tx2> r<2>ty2> r<2>tz2> translate obj'
translates obj by the vector
(r<2>tx2>, r<2>ty2>, r<2>tz2>).
I.e., if obj is at position (p<2>x2>, p<2>y2>, p<2>z2>), then
obj' is at position
(p<2>x2>+r<2>tx2>, p<2>y2>+r<2>ty2>, p<2>z2>+r<2>tz2>).
obj r<2>sx2> r<2>sy2> r<2>sz2> scale obj'
scales obj by r<2>sx2> in the X-dimension,
r<2>sy2> in the
Y-dimension, and r<2>sz2> in the Z dimension.
obj r<2>s2> uscale obj'
uniformly scales obj by r<2>s2> in each dimension.
This operation is called Isotropic scaling.
obj q rotatex obj'
rotates obj around the X-axis by q degrees.
Rotation is measured counterclockwise when looking along the X-axis
from the origin towards +.
obj q rotatey obj'
rotates obj around the Y-axis by q degrees.
Rotation is measured counterclockwise when looking along the Y-axis
from the origin towards +.
obj q rotatez obj'
rotates obj around the Z-axis by q degrees.
Rotation is measured counterclockwise when looking along the Z-axis
from the origin towards +.
For example, if we want to put a sphere of radius 2.0 at (5.0, 5.0, 5.0),
we can use the following GML code:
{ ... } sphere
2.0 uscale
5.0 5.0 5.0 translate
The first line creates the sphere (as described in Section 3.2,
the sphere operator takes a single function argument).
The second line uniformly scales the sphere by a factor of 2.0, and the
third line translates the sphere to (5.0, 5.0, 5.0).
These transformations are all affine transformations and they
have the property of preserving the straightness of lines and parallelism
between lines, but they can alter the distance between points and the
angle between lines.
Using homogeneous coordinates, these transformations can be
expressed as multiplication by a 4#4 matrix.
Figure 3 describes the matrices that correspond to
each of the transformation operators.
e
e
e
e
e
1
0
0
r<2>tx2>
0
1
0
r<2>ty2>
0
0
1
r<2>tz2>
0
0
0
1
u
e
e
e
e
e
r<2>sx2>
0
0
0
0
r<2>sy2>
0
0
0
0
r<2>sz2>
0
0
0
0
1
u
e
e
e
e
e
r<2>s2>
0
0
0
0
r<2>s2>
0
0
0
0
r<2>s2>
0
0
0
0
1
u
Translation
Scale matrix
Isotropic scale matrix
e
e
e
e
e
1
0
0
0
0
cos(q)
-sin(q)
0
0
sin(q)
cos(q)
0
0
0
0
1
u
e
e
e
e
e
cos(q)
0
sin(q)
0
0
1
0
0
-sin(q)
0
cos(q)
0
0
0
0
1
u
e
e
e
e
e
cos(q)
-sin(q)
0
0
sin(q)
cos(q)
0
0
0
0
1
0
0
0
0
1
u
Rotation (X-axis)
Rotation (Y-axis)
Rotation (Z-axis)
Figure 3: Transformation matrices
For example, translating the point (2.6, 3.0, -5.0) by (-1.6, -2.0, 6.0) is
expressed as the following multiplication:
e
e
e
e
e
1.0
0.0
0.0
-1.6
0.0
1.0
0.0
-2.0
0.0
0.0
1.0
6.0
0.0
0.0
0.0
1.0
u
e
e
e
e
e
2.6
3.0
-5.0
1.0
u
=
e
e
e
e
e
1.0
1.0
1.0
1.0
u
Observe that points have a fourth coordinate of 1, whereas vectors
have a fourth coordinate of 0.
Thus, translation has no effect on vectors.
<5>3.4 Illumination model5>
When the ray that shoots from the eye position through a pixel hits a surface,
we need to apply the illumination equation to determine what color the
pixel should have.
Figure 4 shows a situation where a ray from the viewer has
hit a surface.
Figure 4: A ray intersecting a surface
The illumination at this point is given by the following equation:
I = k<2>d2> I<2>a2> C
+ k<2>d2> <2>ls
j=12>
(NL
<2>j2>) I<2>j2> C
+ k<2>s2> <2>ls
j=12>
(NH<2>j2>)<2>n2> I<2>j2> C
+ k<2>s2> I<2>s2> C
(10)
where
C =
surface color
I<2>a2> =
intensity of ambient lighting
k<2>d2> =
diffuse reflection coefficient
N =
unit surface normal
L<2>j2> =
unit vector in direction of jth light source
I<2>j2> =
intensity of jth light source
k<2>s2> =
specular reflection coefficient
H<2>j2> =
unit vector in the direction halfway between the viewer
and L<2>j2>
n =
Phong exponent
I<2>s2> =
intensity of light from direction S
The view vector, N, and S all lie in the same plane.
The vector S is called the
reflection vector and forms same angle with N as the
vector to the viewer does (this angle is labeled q
in Figure 4).
Light intensity is represented as point in GML and multiplication of
points is component wise.
The values of C, k<2>d2>, k<2>s2>, and n are the surface properties
of the object at the point of reflection.
Section 3.6 describes the mechanism for specifying these values
for an object.
Computing the contribution of lights (the I<2>j2> part of the above equation)
requires casting a shadow ray from the
intersection point to the light's position.
If the ray hits an object that is closer than the light, then the light
does not contribute to the illumination of the intersection point.
Ray tracing is a recursive process.
Computing the value of I<2>s2> requires shooting a ray in the direction of S
and seeing what object (if any) it intersects.
To avoid infinite recursion, we limit the tracing to some depth.
The depth limit is given as an argument to the render
operator (see Section 3.8).
<5>3.5 Lights5>
GML supports three types of light sources: directional lights,
point lights and spotlights.
Directional lights are assumed to be infinitely far away and have only
a direction.
Point lights have a position and an intensity (specified as a color triple),
and they emit light uniformly in all directions.
Spotlights emit a cone of light in a given direction.
The light cone is specified by three parameters: the light's direction,
the light's cutoff angle, and an attenuation exponent (see Figure 5).
Figure 5: Spotlight
Unlike geometric objects, lights are defined in terms of world
coordinates.
dir color light l
creates a directional light source at infinity with direction dir
and intensity color.
Both dir and color are specified as point values.
pos color pointlight l
creates a point-light source at the world coordinate position pos
with intensity color.
Both pos and color are specified as point values.
Pointlights are a Tier-2 feature.
pos at color cutoff exp spotlight l
creates a spotlight source at the world coordinate position pos
pointing towards the position at.
The light's color is given by color.
The spotlight's cutoff angle is given in degrees by cutoff and
the attenuation exponent is given by exp (these are real
numbers).
The intensity of the light from a spotlight at a point Q is determined
by the angle between the light's direction vector (i.e., the vector from
pos to at) and the vector from pos to Q.
If the angle is greater than the cutoff angle, then intensity is zero;
otherwise the intensity is given by the equation
I =
c
c
e
at-pos
|at-pos|
Q-pos
|Q-pos|
<2>exp2>
color
(11)
Spotlights are a Tier-3 feature.
The light from point lights and spotlights is attenuated by the distance
from the light to the surface.
The attenuation equation is:
I<2>surface2> = 100 I
99 + d<2>22>
(12)
where d is the distance from the light to the surface and I is the
intensity of the light.
Thus at a distance of 5 units the strength of the light will be about
85% and at 10 units it will be about 50%.
Note that the light reflected from surfaces (the k<2>s2> I<2>s2> C term in
Equation 10) is not attenuated; nor is the light
from directional sources.
<5>3.6 Surface functions5>
GML uses procedural texturing to describe the surface properties
of objects.
The basic idea is that the model provides a function for each object, which maps
positions on the object to the surface properties that determine
how the object is illuminated (see Section 3.4).
A surface function takes three arguments: an integer
specifying an object's face and two texture coordinates.
For all objects, except planes, the texture coordinates are restricted to the
range 0 u,v 1.
The Table 1 specifies how these coordinates map to
points in object-space for the various builtin graphical objects.
Table 1: Texture coordinates for primitives
SPHERE
(0, u, v)
(sqrt(1 - y<2>22>)sin(360 u), y, sqrt(1 - y<2>22>)cos(360 u)),
where y = 2 v - 1
CUBE
(0, u, v) (u, v, 0)
front
(1, u, v) (u, v, 1)
back
(2, u, v) (0, v, u)
left
(3, u, v) (1, v, u)
right
(4, u, v) (u, 1, v)
top
(5, u, v) (u, 0, v)
bottom
CYLINDER
(0, u, v) (sin(360 u), v, cos(360 u))
side
(1, u, v) (2 u - 1, 1, 2 v - 1)
top
(2, u, v) (2 u - 1, 0, 2 v - 1)
bottom
CONE
(0, u, v) (v sin(360 u), v, v cos(360 u))
side
(1, u, v) (2 u - 1, 1, 2 v - 1)
base
PLANE
(0, u, v) (u, 0, v)
Note that (as always in GML), the arguments to the sin and cos functions
are in degrees.
The GML implementation is responsible for the inverse mapping; i.e.,
given a point on a solid, compute the texture coordinates.
A surface function returns a point representing the
surface color (C), and three real numbers: the diffuse reflection
coefficient (k<2>d2>), the specular reflection
coefficient (k<2>s2>), and the Phong exponent (n).
For example, the code in Figure 6 defines a cube with a
matte 3#3 black and white checked pattern on each face.
0.0 0.0 0.0 point /black
1.0 1.0 1.0 point /white
[ % 3x3 pattern
[ black white black ]
[ white black white ]
[ black white black ]
] /texture
{ /v /u /face % bind parameters
{ % toIntCoord : float -> int
3.0 mulf floor /i % i = floor(3.0*r)
i 3 eqi { 2 } { i } if % make sure i is not 3
} /toIntCoord
texture u toIntCoord apply get % color = texture[u][v]
v toIntCoord apply get
1.0 % kd = 1.0
0.0 % ks = 0.0
1.0 % n = 1.0
} cube
Figure 6: A checked pattern on a cube
<5>3.7 Constructive solid geometry5>
Solid objects may be combined using boolean set operations
to form more complex solids.
There are three composition operations:
obj<2>12> obj<2>22> union obj<2>32>
forms the union obj<2>32> of the two solids obj<2>12>
and obj<2>22>.
obj<2>12> obj<2>22> intersect obj<2>32>
forms the intersection obj<2>32> of the two solids obj<2>12>
and obj<2>22>.
The intersect operator is a Tier-3 feature.
obj<2>12> obj<2>22> difference obj<2>32>
forms the solid obj<2>32> that is the solid obj<2>12>
minus the solid obj<2>22>.
The difference operator is a Tier-3 feature.
We can determine the intersection of a ray and a compound solid by
recursively computing the intersections of the ray and the solid's pieces (both entries and exits) and then merging the information
according to the boolean composition operator.
Figure 7 illustrates this process for two objects (this picture is
called a Roth diagram).
Figure 7: Tracing a ray through a compound solid
When rendering a composite object, the surface properties are determined by the
primitive that defines the surface.
If the surfaces of two primitives coincide, then which primitive defines
the surface properties is unspecified.
<5>3.8 Rendering5>
The render operator causes the scene to be rendered to a file.
amb lights obj depth fov wid ht file
render ---
The render operator renders a scene to a file.
It takes eight arguments:
amb the intensity of ambient light (a point).
lights is an array of lights used to illuminate the scene.
obj is the scene to render.
depth is an integer limit on the recursive depth of the
ray tracing owing to specular reflection.
I.e., when depth = 0, we do not recursively compute
the contribution from the direction of reflection (S in
Figure 4).
fov is the horizontal field of view in
degrees (a real number).
wid is the width of the rendered image in
pixels (an integer).
ht is the height of the rendered image in
pixels (an integer).
file is a string specifying output file for
the rendered image.
The render operator is the only GML operator with side effects
(i.e., it modifies the host file system).
A GML program may contain multiple render operators (for
animation effects), but the order in which the output files are generated
is implementation dependent.
The results of evaluating the render operator during the evaluation
of a surface function are undefined (i.e., your program may choose to exit
with an error, or execute the operation, or do something else).
When rendering a scene, the eye position is fixed at (0, 0, -1) looking
down the Z-axis and the image plane is the XY-plane (see
Figure 8).
The horizontal field of view (fov) determines the width of the
image in world space (i.e., it is 2 tan(0.5 fov)), and the
height is determined from the aspect ratio.
If the upper-left corner of the image is at (x, y, 0) and the width of
a pixel is D, then the ray through the jth pixel in the ith row
has a direction of (x + (j+0.5)D, y - (i+0.5)D, 1).
Figure 8: View coordinate system
When the render operation detects that a ray has intersected the surface of
an object, it must compute the texture coordinates at the point of
intersection and apply the surface function to them.
Let (face, u, v) be the texture coordinates and surf be the
surface function at the point of intersection, and let
Eval(surf apply, face, u, v) = (C, k<2>d2>, k<2>s2>, n)
Then the surface properties for the illumination equation (see
Section 3.4) are C, k<2>d2>, k<2>s2>, and n.
<5>3.9 The output format5>
The output format is the Portable Pixmap (PPM) file format.<2>12>
The format consists of a ASCII header followed by the pixel data in binary form.
The format of the header is
The magic number, which are the two characters ``P6.''
A width, formatted as ASCII characters in decimal.
A height, again in ASCII decimal.
The ASCII text ``255,'' which is the maximum color-component value.
These items are separated by whitespace (blanks, TABs, CRs, and LFs).
After the maximum color value, there is a single whitespace character
(usually a newline), which is followed by the pixel data.
The pixel data is a sequence of three-byte pixel values (red, green, blue)
in row-major order.
Light intensity values (represented as
GML points) are converted to RGB format by clamping the range and scaling.
In the header, characters from a ``#'' to the next end-of-line are
ignored (comments).
This comment mechanism should be used to include the group's name immediately
following the line with the magic number.
For example, the sample implementation produces the following header:
P6
# GML Sample Implementation
256 256
255
<6>4 Requirements6>
Your program should take its input from standard input (i.e., UNIX file
descriptor 0).
Execution of the input specification will result in zero or more images being
rendered to files.
If your implementation detects an error, it should return a non-zero exit
status; otherwise it should return a zero exit status upon successful
termination.
Our test harness relies on this error status being set correctly, so be sure
to get them right!
Your program should detect syntactically incorrect input and run-time type
errors (the latter may be detected statically, if you wish).
It should also catch array accesses that are out of range.
Other errors, such as integer overflows and division by zero,
may be detected and reported, but it is not necessary.
In particular, implementations are free to generate NaNs and Infs
when doing floating-point computations.
The submission requirements are described in detail
at http://www.cs.cornell.edu/icfp/submission.htm,
but we summarize them here.
Your submission should include a README file
containing a brief description of the submission, programming
language(s) used, and anything else that you want to bring to the
attention of the judges.
Submissions will be evaluated on their correctness, speed of execution,
and set of implemented GML features.
For the latter metric, we have grouped the features of GML into
three tiers as follows:
Tier 1
The first tier consists of the operations described in Section 2, plus
planes, spheres, and directional lights. All GML operators except cone, cube,
cylinder, difference, intersect,
pointlight, and spotlight should be implemented.
Tier 2
This tier adds more primitive solids and additional lighting to Tier 1.
The additional operators are: cone, cube,
cylinder, and pointlight.
Tier 3
This tier adds constructive solid geometry and additional lighting to Tier 2.
The additional operators are:
difference, intersect, and spotlight.
Your README file should specify which tier
your submission implements.
Judging of the contest entries will proceed in three phases.
First, we will evaluate each submission for basic correctness
using very simple Tier-1 test cases.
Programs that fail to run, dump core, etc. will be disqualified
at the end of this phase.
The second phase tests the basic correctness of submissions (without
regards to performance).
We will use a selection of Tier-1 test cases and compare the output
with that generated by our sample implementations.
Submissions that deviate significantly from the the reference outputs
will be disqualified.
The third phase will compare the performance and implemented features
of the submissions.
When comparing submissions, a program that implements Tier-1 will have to
be significantly faster than a Tier-2 program to beat it.
Likewise, a Tier-2 program will have to be significantly faster than
a Tier-3 program to beat it.
Image quality also matters; for example, a program that has
surface acne will be penalized.
Consideration will be given for interesting sample images.
<6>5 Hints6>
<5>5.1 Basic facts5>
The dot product of two vectors v<2>12> = (x<2>12>, y<2>12>, z<2>12>) and
v<2>22> = (x<2>22>, y<2>22>, z<2>22>)
is v<2>12>v<2>22> = (x<2>12> x<2>22> + y<2>12> y<2>22> + z<2>12> z<2>22>).
When v<2>12> and v<2>22> are unit vectors, then v<2>12>v<2>22>
is the cosine of the angle formed by the two vectors.
More generally, v<2>12>v<2>22> = |v<2>12>| |v<2>22>| cos(q), where
q is the angle between the vectors.
<5>5.2 Intersection testing5>
A plane P can be defined by its unit normal P<2>n2> and the distance d
from the plane to the origin.
The half-space that P = (P<2>n2>, d) defines are those points Q such that
QP<2>n2> + d 0.
Given this definition,
the intersection of a ray R(t) = (R<2>o2> + t R<2>d2>) and
a plane (P<2>n2>, d) is given by the equation
t<2>intersection2> = -(P<2>n2> R<2>o2> + d)
P<2>n2>R<2>d2>
(13)
If P<2>n2>R<2>d2> = 0, then the ray is parallel to the plane
(it might lie in the plane, but we can ignore that case for our purposes).
If t<2>intersection2> < 0, then the line defined by the ray
intersects the plane behind the ray's origin; otherwise the point of
intersection is R(t<2>intersection2>).
We can tell which side of the plane R<2>o2> lies by examining the sign of
P<2>n2>R<2>d2>; if it is positive, then R<2>o2> is in the half-space defined
by P.
Computing the intersection of a ray R(t) = (R<2>o2> + t R<2>d2>) and
a sphere S centered at S<2>c2> with radius r is more complicated.
Let l<2>oc2> be the length of the vector from the ray's origin
to the center of the sphere; then if l<2>oc2> < r, the ray
originates inside the sphere.
We can compute the distance along the ray from the ray's origin
to the closest approach to the sphere's center by the equation
t<2>ca2> = (S<2>c2> - R<2>o2>)R<2>d2> (see
Figure 9).
If t<2>ca2> < 0, then the ray is pointing away from the
sphere's center, which means that if the ray's origin is outside the sphere
then there is no intersection.
Once we have computed t<2>ca2>, we can compute the square of
the distance from the ray to the center at the point of closest approach
by the d<2>22> = l<2>oc2><2>22> - t<2>ca2><2>22>.
From this, we can compute the square of the half chord
distance
t<2>hc2><2>22> = r<2>22> - d<2>22> = r<2>22> - l<2>oc2><2>22> + t<2>ca2><2>22>.
As can be seen in Figure 9, if t<2>hc2><0, then
the ray does not intersect the sphere, otherwise the points of intersection
are given by R(t<2>ca2>t<2>hc2>) (assuming the ray
originates outside the sphere).
Figure 9: Ray/sphere intersection
The intersection of a ray and a cube can be determined by using the
technique given for planes (test against the planes containing the
faces of the cube).
Intersections for cones and cylinders can be determined by plugging the
ray equation (R(t) = R<2>o2> + t R<2>d2>) into the equations for the
surface.
In both cases (as for spheres) the solution requires pluggin values into the
quadratic formula.
One approach to ray tracing with a modeling language that supports affine
transformations (such as GML) is to transform the rays into object space
and do the intersection tests there.
This approach allows the intersection tests to be specialized to the
standard objects, which can greatly simplify the tests.
Remember, however, that affine transformations do not preserve lengths ---
applying an affine transformation to a unit vector will not yield a unit
vector in general.
<5>5.3 Surface acne5>
One problem that you are likely to encounter is called surface acne
and results from precision errors.
The problem arises from when the origin of a shadow ray is
on the wrong side of its originating surface, and thus intersets the surface.
The visual result is usually a black dot at that pixel.
The sample images
include an example that illustrates this problem.
One solution is to offset the shadow ray's origin by a small amount in the ray's
direction.
Another solution is not to test intersection's against the originating surface.
<5>5.4 Optimizations5>
There are opportunities for performance improvements both in the the
implementation of the GML interpreter and in the ray tracing engine.
While the time spent to compute the objects in a scene is typically
small compared to the rendering time, the GML functions that define
the surface properties get evaluated for every ray intersection.
You may find it useful to analyse surface functions for the common
case where they are constant.
The resources listed below include information on techniques for improving
the efficiency of ray tracing.
Most of these techniques focus on reducing the cost or number of ray/solid
intersection tests.
For example, if you precompute a bounding volume for a complex object,
then a quick test against the bounding volume may allow you to avoid a
more expensive test against the object.
If your implementation supports the Tier-3 CSG operators, then you probably
want to have a version of your intersection testing code that is
specialized for shadow rays.
<5>5.5 Resources5>
Here are a few pointers to on-line sources of information about graphical
algorithms and ray tracing.
http://www.cs.cornell.edu/icfp/
is the ICFP'00 contest home page.
http://www.cs.bell-labs.com/~jhr/icfp/examples.html
is a page of example GML specifications with the expected images.
http://www.cs.bell-labs.com/~jhr/icfp/operators.txt
is a text file that lists all of the GML operators.
http://www.realtimerendering.com/int/
is the 3D Object Intersection page with pointers to papers and code
describing various intersection algorithms.
http://www.acm.org/tog/resources/RTNews/html/
is the home page of the Ray Tracing News, which is an online
journal about ray tracing techniques.
http://www.cs.utah.edu/~bes/papers/fastRT/
is a paper by Brian Smits on efficiency issues in implementing ray tracers.
http://www.acm.org/pubs/tog/GraphicsGems/
is the source-code repository for the Graphics Gems series.
http://www.exaflop.org/docs/cgafaq/
is the FAQ for the comp.graphics.algorithms news group.
http://www.magic-software.com
has source code for various graphical algorithms.
<6>Operator summary6>
The following is an alphabetical listing of the GML operators
with brief descriptions.
The third column lists the section where the operator is defined and the
fourth column specifies which implementation tier the operator belongs to.
Name
Description
Section
Tier
acos
arc cosine function
2.4
*
addi
integer addition
2.4
*
addf
real addition
2.4
*
apply
function application operator
2.3
*
asin
arc sine function
2.4
*
clampf
clamp the range of a real number
2.4
*
cone
a unit cone
3.2
**
cos
cosine function
2.4
*
cube
a unit cube
3.2
**
cylinder
a unit cylinder
3.2
**
difference
difference of two solids
3.7
***
divi
integer division
2.4
*
divf
real division
2.4
*
eqi
integer equality comparison
2.4
*
eqf
real equality comparison
2.4
*
floor
real to integer conversion
2.4
*
frac
fractional part of real number
2.4
*
get
get an array element
2.6
*
getx
get x component of point
2.5
*
gety
get y component of point
2.5
*
getz
get z component of point
2.5
*
if
conditional control operator
2.3
*
intersect
intersection of two solids
3.7
***
length
array length
2.6
*
lessi
integer less-than comparison
2.4
*
lessf
real less-than comparison
2.4
*
light
defines a directional light source
3.5
*
modi
integer remainder
2.4
*
muli
integer multiplication
2.4
*
mulf
real multiplication
2.4
*
negi
integer negation
2.4
*
negf
real negation
2.4
*
plane
the XZ-plane
3.2
*
point
create a point value
2.5
*
pointlight
defines a point-light source
3.5
**
real
convert an integer to a real number
2.4
*
render
render a scene to a file
3.8
*
rotatex
rotation around the X-axis
3.3
*
rotatey
rotation around the Y-axis
3.3
*
rotatez
rotation around the Z-axis
3.3
*
scale
scaling transform
3.3
*
sin
sine function
2.4
*
sphere
a unit sphere
3.2
*
spotlight
defines a spotlight source
3.5
***
sqrt
square root
2.4
*
subi
integer subtraction
2.4
*
subf
real subtraction
2.4
*
translate
translation transform
3.3
*
union
union of two solids
3.7
*
uscale
uniform scaling transform
3.3
*
<6>Change history6>
1.18 A bunch of HTML rendering workarounds.
1.17 Description of how surface functions are applied was missing the
face argument.
1.16 Corrected sloppy language about illumination vectors.
1.15 Clarified who rendering depth limit works; corrected
text about light attenuation; and fixed texture equations for cone
and cylinder end caps.
1.14 Got the attenuation equation fix into the document this time.
1.13 Clarified definition of modi; fixed typo in
description of initial ray direction; clarified types of light
operators; corrected typo in attenuation equation (should be d<2>22>,
not d<2>32>); and added note about conversion to RGB format.
1.12 Added note about number sizes and fixed texture coordinates
of planes.
1.11 Many fixes:
added specification of the render operation's types;
fixed typo in definition of dot product; added clarification about
illumination equation and vector
multiplication; fixed typo in equation for square of half-chord distance;
and fixed texture coordinate equations for spheres and cones.
1.10 Clarified definition of frac operator.
1.9 Added note about rebinding true and false.
1.8 Added discussion about applying render in a surface
function.
1.7 Fixed inc example.
1.6 Fixed swap example.
1.5 Fixed typo in divi/divf description; added text
to clarify syntax.
1.4 Fixed mistake in factorial example.
1.3 Added version number and change history.
1.2 Fixed rule cross references in HTML version.
1.1 Fixed bug in example; sub should have been get.
1.0 First release.
<5>15>
The xv program, available on most Unix systems,
and the IrfanView viewer for Microsoft Windows (available from
http://www.irfanview.com/) both understand the PPM format.
This document was translated from LATEX by
H<2>E2>V<2>E2>A.