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=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 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 37310BC0B for ; Thu, 18 Jan 2007 00:01:39 +0100 (CET) Received: from nz-out-0506.google.com (nz-out-0506.google.com [64.233.162.236]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0HN1cq6031947 for ; Thu, 18 Jan 2007 00:01:38 +0100 Received: by nz-out-0506.google.com with SMTP id i11so11820nzh for ; Wed, 17 Jan 2007 15:01:32 -0800 (PST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=aY1pRuSdN4yZlbQLpV8YWfDcGyqXkoVzI1d0OTWRnXJ4NBUjyRLPC97IfSS0c/bI07Y0A0ujm+lQShwsPSPYN8lNnUnFHG9sONC073pAV9V8POYBwbXcoXQfHMonAZ4h1buNnl3PMvhMCz1uXZJq6SEPSqDGcss9S/BVgBCAQ3o= Received: by 10.78.178.5 with SMTP id a5mr71004huf.1169074890834; Wed, 17 Jan 2007 15:01:30 -0800 (PST) Received: by 10.78.198.14 with HTTP; Wed, 17 Jan 2007 15:01:30 -0800 (PST) Message-ID: Date: Wed, 17 Jan 2007 15:01:30 -0800 From: "Nathaniel Gray" To: "Jim Snow" Subject: Re: [Caml-list] Announce: glome-0.2 (ocaml-based raytracer) Cc: "Jon Harrop" , caml-list@yquem.inria.fr In-Reply-To: <45AB57B3.8050800@cs.pdx.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <45A6E34A.6040007@cs.pdx.edu> <200701121216.40859.jon@ffconsultancy.com> <45AB57B3.8050800@cs.pdx.edu> X-j-chkmail-Score: MSGID : 45AEAAD2.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 45AEAAD2.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 compiler:01 recursive:01 defines:01 triangles:01 triangles:01 semantically:01 partitioning:01 recursion:01 recursion:01 recursive:01 iter:01 cheers:01 closures:01 closures:01 On 1/15/07, Jim Snow wrote: > Jon Harrop wrote: > > > > 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. > > [snip] > > > 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 wonder if you really need the mutual recursion. You can often avoid mutual recursion by using closures. Instead of, say, a list of objects with an isect (intersect) method you can use a list of closures. Here's my silly example (you'll have to pardon my ignorance of the domain): (* Some "isectables" *) type sphere = point3 * float * color let isect_sphere sphere ray = ... type triangle = point3 * point3 * point3 * color let isect_triangle tri ray = ... (* A group is just a list of closures that, when applied to a ray, isect their contained geometry *) type group = (ray -> unit) list let isect_group group ray = List.iter (fun x -> x ray) group let s = make_ray ... in let t1 = make_triangle ... in let s1 = make_sphere ... in let group1 = [(isect_sphere s1); (isect_triangle t1)] in isect_group group ray I haven't benchmarked, but I think you should get better results than if you were using virtual method dispatch in an inner loop. Cheers, -n8 -- >>>-- Nathaniel Gray -- Caltech Computer Science ------> >>>-- Mojave Project -- http://mojave.cs.caltech.edu -->