A sample image (mtest7.gml).
The input to the ray tracer was 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. The feature set of GML was organized into three tiers, all of which were implemented by the Mercury entry.
GML has primitives for defining simple geometric objects (e.g., planes, spheres, and cubes) and lighting sources. The surface properties of the geometric objects used to render the objects are specified as functions in GML itself. GML also defined operators for combining the simple geometric objects to create more complex objects. 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 colour. Conceptually, this colour 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.
The contest rules stated that a team had 72 hours to implement a ray tracer. The ray tracer could be implemented in any language, and the team could consist of any size. The short time frame of the contest meant that programming languages that help programmers to build complex systems quickly should give an advantage. (see the report on the 1999 programming contest for more information).
Ralph Becket <rbeck@microsoft.com>
Tyson Dowd <trd@cs.mu.OZ.AU>
Fergus Henderson <fjh@cs.mu.OZ.AU>
Simon Taylor <stayl@cs.mu.OZ.AU>
Peter Ross <peter.ross@miscrit.be>
David Glen Jeffery <dgj@cs.mu.OZ.AU>
Tennessee Leeuwenburg <tjleeuw@students.cs.mu.OZ.AU>
Thomas Conway <conway@cs.mu.OZ.AU>
Rob Jeschofnik <rejj@students.cs.mu.OZ.AU>
Mark Brown <dougl@cs.mu.OZ.AU>
Mike Liddell <mjl@cs.mu.OZ.AU>
David Overton <dmo@cs.mu.OZ.AU>
Peter Eckersley <pde@cs.mu.OZ.AU>
The Mercury entry was produced by a team of 13 members (at least 10 of
which contributed code to the ray tracer). The team was also distributed
over three countries (Australia (11 members), England (1 member) and
Belgium (1 member)). Both the members of the team in England and
Belgium contributed significant amounts of code. Nearly all the
communication between distrubuted team members took place via email (the
England and Belgium team members spoke occasionally by phone).
It should be remembered that Europe and Australia are nearly 12 hours apart in time-zones, so for nearly the entire 72 hours of the contest there was someone, somewhere in the world working on our entry. However, given the preferred working habits of some of the Mercury team members, this might have happened regardless of geography.
The rankings were largely determined by correctness (only 4 teams produced approximately the right results for all the images). After that we were ranked on speed, and that's where our entry didn't fare so well. The full contest results are available here.
Unfortunately, we had to turn off one of our key optimizations (bounding spheres) because we found it caused a few pixels of error in one of the images when we submitted. On the small sample images this gave us a speedup of 50%, however on more complex images it may have been even higher.
This was unlikely to have even moved us up a place, however, because the Mercury implementation of floating point is fairly slow on the x86 processor. At this point in the contest, our competition consisted of compilers with very good floating point support. This is a weakness in the Mercury implementation that we'd love to fix.
Between these two efficiency problems, we quickly fell off the pace when the contest images became large and complex.
One of the frustrating parts of the competition was that we encountered quite a few bugs in the specification and the sample images. Many hours were spent trying to figure out why our correct ray tracer refused to produce the wrong image. This isn't meant to be a criticism of the organizers -- they have a tough job, but keeping 13 people around the world up to date with task descriptions, image updates, food and caffeine was a tough job.
Of our own bugs, two of the most common were incorrect signs, and using non-unit vectors when unit-vectors were expected. We recommend using the type system to prevent the unit vector error if anyone wants to write a ray-tracer in Mercury in the future.
Number of types: 64
Number of insts: 2
Number of predicates: 162
Number of functions: 133
Number of predmodes: 102
Number of funcmodes: 0
Number of separate modes: 66
Number of implicit function modes: ?
Total number of modes: >= 168
=< 301
- det: 122 ( 72.62%)
- semidet: 40 ( 23.81%)
- nondet: 0 ( 0.00%)
- multi: 0 ( 0.00%)
- cc_nondet: 0 ( 0.00%)
- cc_multi: 2 ( 1.19%)
- erroneous: 8 ( 4.76%)
- failure: 0 ( 0.00%)
Average modes per predicate: >= 1.037
=< 1.037
Blank lines: 1263 ( 20.57%)
Comment lines: 537 ( 8.74%)
Total whitespace/comment lines: 1800 ( 29.31%)
Function declaration lines: 147 ( 2.39%)
Predicate declaration lines: 260 ( 4.23%)
Mode declaration lines: 67 ( 1.09%)
Type declaration lines: 308 ( 5.02%)
Inst declaration lines: 13 ( 0.21%)
Other declaration lines: 223 ( 3.63%)
Total declaration lines: 1018 ( 16.58%)
Code lines: 3323 ( 54.11%)
Total number of lines: 6141 (100.00%)
Mercury provides an interface to the C language. This interface was
used once to do an efficient ray-box intersection test. The C code for
this was located from the web, and rather then recoding the algorithm in
Mercury we used the C code verbatim.
Functional programmers often ask whether any of Mercury's logic features were useful in this contest (as many of the other features of Mercury are very similar to functional languages). We didn't end up using any non-deterministic search in our final entry. However, we certainly used them during the early coding of the project. Our original implementation of finding the nearest intersection point of a ray simply found all the intersections using a call to `solutions' and a nondeterministic search through all the available objects. We eventually removed this code as we started using different algorithms to find the intersecting objects.
cvs -d:pserver:guest@hydra.cs.mu.oz.au:/home/mercury1/repository login (password is guest) cvs -z6 -d:pserver:guest@hydra.cs.mu.oz.au:/home/mercury1/repository co icfp2000
You will need a recent daily release of the Mercury system to compile and build the code (The current 0.9.1 release lacks a few features that we have used in the ray tracer). You can download Mercury from the snapshots section of the Mercury homepage.
The Mercury Team
http://www.cs.mu.oz.au/research/mercury/
mercury@cs.mu.oz.au