Re: [Caml-list] Announce: glome-0.2 (ocaml-based raytracer)

[Jim Snow <jsnow@cs.pdx.edu>]

Jon Harrop wrote:
> On Friday 12 January 2007 01:24, Jim Snow wrote:
>   
>> I've been working on a raytracer for awhile, and recently decided to
>> remove a lot of experimental code that doesn't work well anyways and
>> release the rest under the gpl version 2.  Currently, glome renders some
>> of the scenes from the standard procedural database
>> (http://www.acm.org/tog/resources/SPD/).  I thought that, aside from the
>> practical utility of generating pretty pictures, some people on this
>> list might be interested in using it to benchmark the quality of code
>> generated by various versions of the ocaml compiler.
>>     
>
> I have altered the code to be more idiomatic OCaml, although it is still very 
> not-OCaml. I've removed OOP from the hot path and virtual function dispatch 
> has been replaced with pattern matches.
>
>   http://www.ffconsultancy.com/temp/glome.tar.bz2
>
> The code is now 1390LOC instead of 1746 (20% shorter). Performance is also 
> better. Building the Kd-tree is down from 7.0s to 6.3s.
>
>   
Sorry I'm a bit slow about replying; I was off trying to implement an 
nlogn kd-tree compiler.  Your version seems to have sped up the 
raytracing by about 10%.  However, I think I am going to stick with my 
approach for the time being for the sake of maintainability; I don't 
think putting all the ray-intersection code together in one 
mutually-recursive is going to make the program easy to modify in the 
future.  I am tempted though.  I might also give recursive modules a try.

(For those just joining us, my dilemma is thus: my raytracer defines 
ray-intersection tests for a number of types of geometry.  Aside from my 
conventional primitives, triangles and spheres, I also have a number of 
more abstract primitives like groups (a container for primitives, so I 
can treat, say, a collection of triangles as if it were one triangle) 
and kdtrees (semantically similar to a group, but with an axis-aligned 
binary space partitioning scheme).  In order for this latter type to 
work correctly, they need to have a ray-intersection function that calls 
the ray-intersection functions of their contained objects.  Contained 
objects may also be groups or kdtrees, hence the necessity of mutual 
recursion.  Due to the lack of mutual recursion across source files, I 
had resorted to using objects; all primitives inherit from a base type 
that supports a ray-intersection test.  Unfortunately, this incurs 
noticeable overhead.  Jon Harrop's solution was to write one big 
recursive ray-intersection test that pattern matches on the type of 
supplied primitve, and evaluates the proper test.)
> I have many suggestions for what to do next:
>
> 1. Use records instead of float arrays: stronger type inference, more concise, 
> purely functional.
>   
I did try this after looking at your ray tracer; however, this did not 
significantly affect performance, except in cases where I needed to 
access vectors like an array (with an integer index), and none of the 
tricks I could think of to do that were as fast as plain array access.  
This created a bottleneck in my kd-tree traversal code (where 
high-performance ray tracers tend to a significant portion, if not most, 
of their time).

See http://ompf.org/forum/viewtopic.php?p=2709&highlight=#2709
> 2. Get rid of almost all mutation. The core ray tracer has no reason to use 
> mutation and all those refs and assignments are confusing and probably slow.
>
>   
If you mean the place where I pass a "traceresult" record into each 
rayintersection test, I agree that that is definitely ugly, but at the 
time it gained me a noticeable performance increase (I think it was 
around 5% or so.).  However, that was under a different workload; that 
was before I implemented the kdtree and I was doing many more ray-object 
intersections.  I was also optimizing for a different set of 
ray-intersection tests that returned more information, and I was keeping 
the results around much longer (I couldn't throw them away until the 
whole image was done rendering).  I didn't want them to sit around so 
long they get promoted to the major heap, only to get garbage collected 
much later.  It's possible those concerns aren't valid for the way the 
raytracer currently works.  I might try reverting that optimization one 
of these days and seeing what happens.

If assignment to mutable fields bothers you, I suggest you avert your 
eyes from the clr.ml file.  I don't really have a good excuse for that 
code, other than it seemed like a good idea at the time and I haven't 
gotten around to re-writing it.
> 3. Restructure the program again: put independent definitions related to 
> triangles in Triangle, put related definitions like the intersection routine 
> in Intersect.
>
> Primarily, the program is far too verbose and convoluted. As an algorithm, ray 
> tracing is very functional in nature. I think the functionality provided by 
> this program could be achieved in half as many lines of code. It could also 
> be a lot faster.
>   
You're right that the program could be cleaner and much shorter, but I'm 
relatively new to functional programming, and I haven't figured out all 
the shortcuts.  When I'm feeling lazy and I see something that seems 
like it should be a loop I'll usually use a loop, whereas I could have 
used recursion and saved myself some typing.  I like that ocaml doesn't 
force you to program in a particular way.

I also don't think "lines of code" is always a good way of measuring 
code quality.  Oop, for instance, adds a lot of cruft (which is one 
reason I dislike java; I don't like being forced to do all that typing), 
but I used it because it gave me mutual recursion without having to 
stick all my mutually recursive functions together in one file, and 
therefore I can group my code into smaller, more manageable units.  (I 
won't dispute that your version is faster.)
>> Supported primitives are spheres and triangles.  It uses a kd-tree as an
>> acceleration structure.  There is limited joystick support (moving works
>> fine, but turning can have unexpected results) for those patient enough
>> to tolerate the low framerates.
>>
>> I use lablgl for screen output, but there aren't any other libraries
>> required outside of the standard ocaml distribution.
>>     
>
> Rather than rendering dots, you could generate a polygon mesh. To make things 
> more interesting, you could include the depth value in the mesh, so when you 
> rotate the scene it gets distorted by OpenGL without needing to ray trace 
> anything.
>
>   
Hm, I'll bet you'd like to know what the 2/3 of the code I didn't 
publicly release does :)
(It doesn't do quite what you suggest, but I do draw the final image to 
the screen as an adaptive triangle mesh (using the ROAM algorithm).)

Your bunny renderer looks interesting.  It's been on my to-do list to 
contrive some way to load more interesting datasets than the standard 
procedural database.