Strange, downloading lmr.tgz gives a demo.lmr which seems to be a corrupted copy or something of lmr.arc.
What is the file format, anyway? It looks like Arc readable format but I can't figure out the structure.
Regarding the intersect code: generally most systems work with shapes that are just the basic triangle plane. This also generally means that the intersect code would really just return one point, not many - currently, your code seems to return a list of points for each shape. Even if your "shape" becomes an entire tree of shapes (say a BSP tree), I would assume that only one intersection - the one nearest to the ray source - would "win", so intersections on shape trees should (I think) return just one intersection.
Returning just one intersection saves memory - you don't need to store several lists. In particular, all you have to do is to get the intersection with the least distance:
(def gen-intersection (ray)
(= intersection nil)
(each sh shape
(aif (intersect ray sh)
(when (or (no intersection) (< (car it) (car intersection)))
(= intersection it))))
intersection)
Can you give your reasons why you chose to retain multiple intersections?
If you really think retaining multiple intersections is better, I would suggest you also study lib/tconc.arc, which includes a somewhat-fast list concatenate function (but you need a transparent wrapper around the list you are building).
Depending on how motivated you are at studying the list structure and advanced stuff, you might prefer to use explicit head+tail catenations, although head+tail tends to be better used on continuation passing style, especially in languages (e.g. Arc) which don't naturally support multiple-value-returns (lists don't count, you have to destructure them, which takes time).
Also: avoid using nested maps - each map reallocates memory:
(of course, cross3 doesn't seem to be used anyway)
Finally: avoid using 't as a variable name.
I think the greatest consumer of time would probably be 'map. 'map is nice but it creates a structure, and the implementation is not written in tail-recursive-modulo-cons ^^. If you're just going to work with individual lists, you can use map1, which is like map but only works on one list, but is slightly faster.
The other thing I think that the time is being consumed in might be with the use of 'alref. It might be better to use map 'listtab on your shapes, so that you don't have to use alref, which always does linear search.
First off, thanks for the pointers! I'll certainly look into those when I have a chance.
I have no idea why the file was corrupted. I'll re-archive and update the file on the server.
You're right about the multiple intersections I indeed sort them by distance. But I forgot to return only the first two elements (needed for entering and exiting a shape for refraction). I'll fix that.
Ugh - I used t as a var? I should have known better than that. Must be remnants of my terse C coding style :)
> But I forgot to return only the first two elements (needed for entering and exiting a shape for refraction).
Strange; I would have thought you needed only one intersection, because my mental model for refraction would be:
|
-----+-------
\
\ <-----new ray
--------+----
|
|
viewer
So you really need only one intersection - the nearest, because the second intersection wouldn't really be aligned to the refraction ray. But then I haven't read the book you are reading.
Basically at each intersection point I'd expect to split into three rays: a reflection ray (cross product to the normal), a refraction ray (if at least partially transparent) and a shadow ray (towards any source(s) of light).
