team
helikopter.

Welcome to the submission home page of team "Helikopter", formed for participation at the ICFP 2000 Functional Programming Contest.

In this year's contest the task was to write a raytracing engine together with an interpreter for its Postscript-like description language within 72 hours. With the resulting program you are able to model and render arbitrary 3D sceneries. A special feature of the rendering language was its procedural texturing where you pass higher-order functions to describe the surface of each individual object.

We are astonished to see that we've been declared winner of the Judge's Prize for one of our demo sceneries! It's a complete chess board and makes use of almost all features of the rendering language GML. Another demo scenery we submitted was the animated helikopter you see above.

members _________________________________

Our team just consisted of two people:

• Leif Kornstaedt
• Andreas Rossberg

Originally, we were a team of four, but one member dropped out after seeing the task spec, and the last member didn't bother to give any sign of life at all until monday evening...

In case you wonder: our team has been named after the famous "Helikopter-Streichquartett" by Karlheinz Stockhausen, for reasons you can find out below.

sources _________________________________

You can take a look at our submission (with the bug fixes mentioned below):

• SML source of our renderer.
• GML source of the chess board.
• GML source of the animated helikopter.

description _____________________________

Although we won the Judge's Prize for our chess scenery, you still might be interested in our renderer, written in Standard ML.

Originally we planned to participate with our own evolving implementation of an SML dialect, codenamed Stockhausen. It provides all sorts of nice features not found in SML, but unfortunately none of them would have been of much use for this particular task. And our floating point performance is lousy... :-( So we had to stick to SML/NJ.

Our submission in general:

• We implemented all three tiers. Most stuff works fine, but there are some stupid bugs (see below).
• We tried to do a clean (modular, strongly typed & functional) design, efficiency was only of secondary concern. We did not have the time for any serious optimizations and our rendering algorithm seems to be suboptimal - we are slooow compared to some other entries. :-(
• Error messages are simplistic. Error positions during parsing are only given in absolute character positions.
• Total LOC is around 1300 (not counting generated files) which seems pretty short compared to the other entries we have seen (even the Haskell one...).

Modularization:

• Of course, the renderer kernel is completely independent of the abstract machine (actually the machine could be functorized over the renderer). Surface functions are passed as ordinary SML functions.
• Likewise, the Machine completely encapsulates knowledge of the renderer.
• The set of builtin operations (including names) is encapsulated in the machine. The parser does not know about it.
• Toplevel control loop for rendering is factored out of the renderer (would allow future optimizations of the rendering process by recalculating bounding boxes for example).

Frontend and GML Machine:

• Parser and lexer have been generated with ML-Yacc/ML-Lex.
• The parser does complete static binding analysis.
• Most primitive operations are encoded in a datatype carrying the corresponding SML implementations as higher-order functions, the actual evaluator is therefore very short and simple. False, true, if, and apply are treated as ordinary operators.
• Constant surface functions are recognized and optimized. Strangely enough though, this does not seem to have any positive effect on runtime whatsoever. :-(

Renderer:

• Cubes, cones, and cylinders are decomposed into intersections of simpler objects (planes, infinite cones & cylinders).
• All rotational objects are treated uniformingly by parameterization.
• Dealing with rounding errors:
  • Intersection ignores objects closer than some eps.
  • Difference ignores eps sized slices.
• Optimizations:
  • Illumination equation simplified for kd=0 or ks=0.
  • Intersection and difference perform shortcut evaluation.

Bugs (The Embarassing Part):

• In the submitted version, the trigonometric operators did not work correctly - because we accidently deleted the conversion from degrees to radiant during some code restructuring 8-} (who chose degrees for GML anyway?). This is fixed.
• There was a bug with shadow rays in the submitted version, caused by using a wrong signed epsilon for tolerance against rounding errors. Caused strange shadows with pointlights sometimes. Fixed.
• Cones seemed to produce a mysterious ghost circle at some distance below - as a workaround for the submission we avoided this bug by intersecting all cones with a surrounding sphere ;-) We still don't know what the cause is...
• And then this stupid Domain exception that is thrown under obscure circumstances... Obviously, at some boundary conditions, we get a NaN somewhere - no idea. And out of false pride we did not wrap the renderer into some exception handler to sneak out of such conditions...
• Last but not least: we are way too slow!