On 1/15/07, Jim Snow <jsnow@cs.pdx.edu> 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 -->