From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id BE5AABC0B for ; Mon, 15 Jan 2007 11:30:21 +0100 (CET) Received: from ehlo.cat.pdx.edu (ehlo.cat.pdx.edu [131.252.208.106]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0FAUIe4005042 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 15 Jan 2007 11:30:20 +0100 Received: from [192.168.0.3] (c-24-20-143-105.hsd1.mn.comcast.net [24.20.143.105]) (authenticated bits=0) by ehlo.cat.pdx.edu (8.13.5/8.13.5/Debian-3ubuntu1.1) with ESMTP id l0FAU3L9000589 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 15 Jan 2007 02:30:04 -0800 Message-ID: <45AB57B3.8050800@cs.pdx.edu> Date: Mon, 15 Jan 2007 02:30:11 -0800 From: Jim Snow User-Agent: Thunderbird 1.5.0.9 (X11/20070103) MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Announce: glome-0.2 (ocaml-based raytracer) References: <45A6E34A.6040007@cs.pdx.edu> <200701121216.40859.jon@ffconsultancy.com> In-Reply-To: <200701121216.40859.jon@ffconsultancy.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Greylist: Sender succeeded SMTP AUTH authentication, not delayed by milter-greylist-2.0.2 (ehlo.cat.pdx.edu [131.252.208.106]); Mon, 15 Jan 2007 02:30:04 -0800 (PST) X-Virus-Scanned: ClamAV version 0.90RC1.1, clamav-milter version devel-131006 on ehlo.cat.pdx.edu X-Virus-Status: Clean X-Miltered: at discorde with ID 45AB57BA.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; renders:01 tog:01 ocaml:01 compiler:01 ocaml:01 compiler:01 recursive:01 defines:01 triangles:01 triangles:01 semantically:01 partitioning:01 recursion:01 recursion:01 recursive:01 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.