markv@phoenix.Princeton.EDU (Mark T Vandewettering) (08/17/89)
I have been working on a program for volumetric rendering. Anybody have any ideas how to structure data to minimize thrashing on a virtual memory system when accessing data along more than one axis? Seems like somebody must have done something like this before. mark vandewettering (markv@acm.princeton.edu)
halazar@mit-amt.MEDIA.MIT.EDU (Michael Halle) (08/17/89)
Well, I can give you an answer that applies particular subset of volume rendering... If you are computing multiple views of a data set non-interactively, (as opposed to rendering one view "interactively", or rather, as fast as possible), it makes sense to othogonalize your data so that the transformation that you are performing from view to view to view never forces more data to be read from disk. For example, if you are spinning around a center axis, compute the entire sequence a scanline at a time, because no extra data will have to be read from disk during the calculation of all views of that scanline. Most "flyby"s can be othogonalized in such a way. It seems to be general experience that an image is most meaningful when it can be seen from several viewpoints (either a loop sequence or, in our case, a holographic stereogram), so rendering many images is ideally the rule, not the exception. In a virtual memory environment, this operation can be done implicitly by sorting rays (using Levoy-like "ray tracing" volume rendering approach) or by sorting or resampling data planes (for the Pixar-like composite-rows-of-voxels approach). The image sequence can then be rendered in strips of some size such that the working set is smaller than the machine's physical memory size. If the sorting step is done correctly, data will not be swapped in except when a new strip is being rendered. A special added bonus of this approach, known as sequence-based rendering, is that large data sets that won't fit into memory at once can be rendered. Also, depending on the complexity of the light model that you are using, many of the calculations are redundant from view to view, so calculation of these parameters need be done only once. For example, if the viewer is flying around an object, and the light sources are fixed in space and located at infinity, the ambient and diffuse calculations performed for the first view can be used for all subsequent views...only the ray projection/compositing needs to be redone. Specular highlights, however, need to be recomputed for each view because they depend on the viewer's location in space. If a subsampled (in some space) rendition of the object exists, the sequence can be previewed interactively at low resolution (maybe without specular highlights), then batch rendered in "high quality mode". Similarly, if the transparency of any non-opaque parts of the object can be reduced, more voxels can be "culled" from the calculation (fully transparent voxels and any voxels always behind completely opaque elements never have to be read into memory except once to identify them). In general, compression is only possible at the expense of something. If you want to be ably to examine a highly transparent, complex data set from any angle interactively with a high quality light model, you are going to have to pay the disk access piper. Constrain any of the above degrees of freedom, and you can save some costs. Of course, new and different algorithms and faster machines may rework the cost equation somewhat. Hope this helps a little. --Michael Halle Spatial Imaging Group MIT Media Laboratory
hutch@celerity.uucp (Jim Hutchison) (08/19/89)
With 2 axis, I presume that you mean looking at the same locale in
the "volumetric data" from 2 different view points. As pointed out by
Mr. Halle in <503@mit-amt.MEDIA.MIT.EDU> this is a pretty common problem.
The notion of "thrashing" relates to excessive paging activity in a
virtual memory system. Thrashing is the condition in which too high of
a percentage of time is spent paging.
So, it would be nice to have the data for a locale located close together.
I would *like* to suggest a 3 dimensional space filling curve. Unfortunately
this yields very complicated algorithms. It is also perhaps excessively
complicated to organize the data that way. Instead, the small subtrees at
the bottom of the tree (presuming voxel or oct-tree arrangement) could be
grouped with each contiguous in a span of memory. For example of take each
subtree and put it in a memory page. When the same locale is viewed from
several angles, a lesser percentage of unviewed data is paged in. With a
higher percentage of the proper data in memory, less thrashing.
This is data structure is conceptually similar to tiling in rasters, which
provides similiar benefits. This data model has a problem when the data
size of the views exceeds available physical memory. This algorithm is
very similar to what I've heard of the Pixar "row" algorithm referred to
by Mr. Halle in <503>. It might be possible to get around this limitation
by having the views begin the "viewing" at a common point and scanning in
a 3D common direction.
/* Jim Hutchison {dcdwest,ucbvax}!ucsd!celerity!hutch */
/* Disclaimer: I am not an official spokesman for FPS computing */