On Tue, 04 Jan 2000, Jerzy Karczmarczuk wrote:
> Brett disagrees with my statement that
>
> > > ... Concretely, you generate pixel by pixel, and you have to
> > > operate upon an *updateable* frame buffer.
Not for a ray-tracer. Yes, it is pixel-major, as opposed to object-major like
z-buffering. But because it is pixel-major, once you've generated a pixel, you
never need to touch it again.
Procedurally, the canonical pseudocode is
for each row
for each column
fire a ray through that pixel, checking for intersection against every
object. Closest object determines the pixel color.
Add in calculations for shading, shadows, etc. in the inner statement to get
fancy stuff (e.g., call a RenderMan shader).
> > I was planning on just writing the resultant image to a file.
> > I'm not sure what I would gain by accessing an updateable frame
> > buffer, as displaying the resultant image would be accomplished by
> > some other program.
>
> If you wish so...
> Of course, you might produce a stream of pixels, and this is as
> functional as any stream generation.
Yeah - that's a straight-forward functional way to do the procedure above. In
Haskell, of course, a list works just fine. Brute force:
type Target = (Float, Float) -- film-plane coordinate
type Targets = [ Target ]
type Pixel = ( Target, Color )
type Image = [ Pixel ] -- non-optimized , possibly random-order list of pixels
targets :: Targets
data targets = foo -- some grotty list comprehension and flattening to get a
-- list of x,y coords
data listOfObjects = parseObjectFile "foo.pov" -- read it in and turn it into a
-- list of ray-intersectable objects
-- rayIntersect :: [ Object ] -> Target -> Pixel
data intersectAllObjs = ( rayIntersect listOfObjects )
data :: Image
data resultImage = map intersectAllObjs targets
> But I cannot stop thinking about a *serious* tracer with all
> kind of standard optimizations, for example being able to
> undersample the rendering and fill the holes by interpolation.
That kind of trick is easy with the above formulation. For example, let's say
we want a 1k by 1k output image. We'd like to stochastically sample the image.
data resultImage = map intersectAllObjs
(poissonDistribution xrange yrange numberofSamples)
Of course, what you'd really like to do is decide whether to sample further
based on how similar the current pixels are. typically, you'd use a quad tree
over the image. I'm tired, so I'm not going to write it right now, but clearly,
it's recursive, and straight-forward to implement, especially when
intersectAllObjs expects to be passed the screen-space coordinate to fire the
ray through.
> This
> doesn't need a full-fledged framebuffer either, but doing it while
> generating a stream seems a bit clumsy.
A literal stream, perhaps, but a lazily produced stream seems pretty clear. You
let the compiler figure out what order to do things in.
> And anyway, dumping this pixel stream into an output file will
> be *much, much* more expensive than putting everything in an array.
Yeah, sure. RAM access < disk access < net access.
> I mentioned the shader language of Renderman-compatible packages.
> Brett:
>
> > The RT I am familiar with (Pov-Ray) also has its own specific language.
> > This was also part of my motivation, as haskell seems like a very good
> > replacement for it.
>
> I don't think so. The POV language, as the Renderman RIB (and VRML,
> etc.)
> are *scene description languages*. Of course, Haskell is sufficiently
> powerful to represent 3D objects, no problem. But this is very far
> from the Ray Tracing engine. The external, linguistic descriptions of
> objects and scenes are massaged quite a lot before becoming *fast*
> representations, adapted to the RT algorithm. So Haskell "data" will
> help the human user, but it should not be used as the object implemen-
> tation language for the rendering. (IMHO)
Not the rep the user reads of course, but having declarative lazy functions to
turn those simple reps into highly optimized reps seems to make a lot of sense.
This works really well with a sphere - list of transforms like scale and
translate humans can grok. Accumulate those in a 4x4 matrix, invert it, and
apply the result to the ray. Now feed the ray to a unit-sphere intersection.
Ray tracer innards get a good rep, and the human does too.
Categorizing the objects by likelyhood of intersection (e.g., using a
zz-buffer) works the same way - as you read in the human-format objects, they
get transformed to the fast format, but the programmer got to write it neatly
and succinctly, much closer to a description of the characteristics of the
format rather than some obtuse recipe.
> On the other hand, the shaders are dynamical procedures, and here we
> may play with the power of a higher-order FL as we really like it!
Sure. And if you're really clever, you can apply that across the board, and for
optimizations, too. For example, dynamically construct a function that
intersects a ray with the one particular object in this scene. You *will* call
it repeatedly :-) Kind of like the FFTW library's creation of custom FFT
routines, or Self's dynamic compilation.
Graphics problems, oddly, have a lot of the same solutions as programming
language and compilation problems. Most graphics people don't quite grok that.
Most PL people don't know enough about the graphics algorithms to apply the PL
solutions. IMNSHO, YMMV, etc. etc.
Every time graphics people start talking about 3D file formats, they get into
an argument about lexical scope, but don't realize it, because they're talking
about lights, not "variables".
Brook
----------------
Klactovedestene!
