[Haskell-cafe] announce: Glome.hs-0.3 (ray tracing digression, glome tutorial)

[Jim Snow]

David48 wrote:
> On Sat, Apr 26, 2008 at 9:33 AM, Andrew Coppin
> <andrewcoppin at btinternet.com> wrote:
>
>   
>> >  Personally, I don't see the point in rendering a couple of million
>> > mathematically flat surfaces,
>>     
>
> What about speed ?
That is a good point.  Ray tracing may give you a better image 
approximation than rasterizing triangles, but unless you're tracing an 
infinite number of rays, it is still just an approximation.  Some shapes 
(like spheres) can be rendered more quickly in a ray tracer than 
triangles, and they use less memory as well, so if you really want a 
sphere, there's no reason to approximate it with triangles.  For other 
objects, the trade-offs are more complex.
> ...
>
>> Unfortunately, the SDL is so complex it's well-nigh impossible to 
>> support in other third-party applications.
>
> I don't think it would be "impossible" to support in 3rd party apps. A 
> lot of work, certainly! Especially the way the parser does parsing and 
> macro expansion in the same pass, so a macro body need not contain a 
> syntactically-complete code fragment. I think if somebody sat down and 
> wrote something that would do all the macro expansion, variable 
> substitution and so forth to leave just few geometry descriptions, 
> *those* would be quite easy to parse and manipulate for 3rd parties.
>
I guess a pov importer wouldn't necessarily be all that difficult, or an 
exporter, for that matter.  (Supporting every single primitive type, 
texture, and rendering feature would be a daunting challenge, but just 
supporting the basics might be relatively simple.)  The problem comes 
when you want to import a nice short hand-edited script, and then do a 
few things to it and export it again: suddenly the file turns into a 
multi-megabyte monstrosity with all the loops unrolled and all the 
recursive macros expanded and you lose the ability to hand-edit the 
scene.  Depending on what you're doing, this might not be a problem.

>
>>> Personally, I'd quite like to write my own ray tracer to address 
>>> some of these limitations. But every time I try, I end up hitting 
>>> design issues [Haskell works very differently to Java] or 
>>> performance issues [which I don't even know how to begin debugging]. 
>>> Not to mention that POV-Ray uses sophisticated techniques like 
>>> volume bounding that I know nothing about. (There's nothing like 
>>> using an inherantly superior algorithm to make your code orders of 
>>> magnitude faster...)
>>>
>> I haven't really run into any issues where Haskell didn't let me do 
>> what I want, except for the performance counters thing mentioned way 
>> back at the beginning of this thread (and which I've more or less 
>> given up on for now, since the acceleration structure seems to be 
>> working okay and I have other things to work on).
>
> Well, for example, Haskell doesn't have hetrogenous lists - which are 
> trivial in any OOP language. That's quite awkward to get around. Also, 
> both spheres and cylinders have a "radius" property, but then you end 
> up with name clashes. Again, a non-issue in OOP languages. [I gather 
> there's some new GHC language extension to partially solve this one - 
> but only when types are statically known. In the general case, you'd 
> have to write a "radius class" and define instances... yuck!]
>
It's funny you mention that, those are actually problems I ran into, but 
(having learned my lesson the hard way in Ocaml), I decided not to try 
and force the language to do things my way, but instead try to do things 
in a way that Haskell makes easy. 

For instance, I started out by making each primitive a separate type 
(Sphere, Triangle, etc...), and then made a type class that defines a 
ray intersection method (and a few other odds and ends), but then I 
realized that I can't do something as simple as store a list of 
primitives (or if there is in fact a way, I'm not aware of it). 

Instead, I made a single large sum type with all my primitives:

data Solid =  Sphere {center :: Vec,
                      radius, invradius :: Flt}
            | Triangle {v1, v2, v3 :: Vec}
            | TriangleNorm {v1, v2, v3, n1, n2, n3 :: Vec}
            | Disc Vec Vec Flt  -- position, normal, r*r
            | Cylinder Flt Flt Flt -- radius height1 height2
            | Cone Flt Flt Flt Flt -- r clip1 clip2 height
            | Plane Vec Flt -- normal, offset from origin
            | Box Bbox
            | Group [Solid]
            | Intersection [Solid]
            | Bound Solid Solid
            | Difference Solid Solid
            | Bih {bihbb :: Bbox, bihroot :: BihNode}
            | Instance Solid Xfm
            | Tex Solid Texture
            | Nothing deriving Show
etc...

(strictness annotations and a few broken primitives omitted for brevity)

so that now I can easily make a list of primitives.  (In fact, that's 
what a Group is.)  I also gave up on using named fields, since coming up 
with a separate name for each one gets ugly:  instead of radius, you 
have sphere_radius, cylinder_radius, cone_radius disc_radius, etc...

>> Cones and spheres and boxes and the like can be made into some fairly 
>> elaborate scenes, but you can't really make, say, a realistic human 
>> figure out of those sorts of primitives.
>
> No, but with things like isosurfaces and parametric surfaces, the 
> world is your oyster. And you can do a surprising amount of things 
> with blobs. I understand that all those curved surfaces which are 
> currently popular in consumer electronics are done with splines, not 
> triangles...
>
That world is a very slow oyster.  I've used blobs and isosurfaces in 
POV-Ray, and they're wonderfully expressive but also incredibly slow.  
(The water in this scene, for instance, is an isosurface, and the boat 
hull is a blob and some CSG: http://syn.cs.pdx.edu/~jsnow/castle-crop.jpg)

There are also other problems: the isosurface solvers are sometimes 
wrong, leading to ugly artifacts (and a lot of manual tweaking to make 
them go away), and applying a texture to an isosurface or blob isn't 
necessarily straightforward. 

Another issue is that isosurfaces are great for filling the scene with 
procedurally-generated complexity, but sometimes you need to do actual 
physics computations in order to make the object do the right thing.  
For instance, in the image I linked above, the water looks pretty good, 
but the waves should really be reflecting off of the castle when they 
hit it, and there's no way I know of to do that without actually doing 
some sort of finite-element fluid simulation.  And since that's already 
an approximation, and it's already taking up a lot of memory, you might 
as well just represent it as a triangle mesh (or whatever happens to be 
the easiest representation to render efficiently).

There's really a trade-off here between quality, time, and space.  Any 
blob or isosurface can be approximated with triangles, and if the 
triangles are smaller than a pixel (or sometimes even if they're quite a 
bit bigger) the difference isn't going to be noticeable.  However, using 
huge numbers of triangles consumes a ridiculous amount of memory, so you 
often have to use a coarser representation.  (Here's an interesting 
paper about doing this sort of thing in a clever way: 
http://www.llnl.gov/graphics/ROAM/roam.pdf)

Isosurfaces and blobs
(http://povray.org/documentation/view/3.6.1/71/, 
http://povray.org/documentation/view/3.6.1/73/) are two features I 
really like about POV-Ray, but they're very CPU intensive.


In other news, I have the beginnings of a tutorial up on the Haskell 
wiki that describes how to write your own scene with Glome: 
http://www.haskell.org/haskellwiki/Glome_tutorial

-jim