markv@gauss.Princeton.EDU (Mark VandeWettering) (12/05/89)
========================================================================
() _ _ _ __ _
/\ ' ) / ' ) ) // _/_ _/_
/ ) _. o ( / o / / _ , , , _ // _ / / _ __
/__/__(__<_ \/ <_ / (_</_(_(_/_/_)_</_</_<___<__</_/ (_
========================================================================
Moderator: Mark T. VandeWettering (markv@acm.princeton.edu)
Volume: 00.00
Date: Dec 04, 1989
Postings can be submitted by sending mail to sci-vi@acm.princeton.edu.
Requests for addition and deletion should be sent to
sci-vi-request@acm.princeton.edu. Requests for addition should be
accompanied by a short bibliographic sketch, including a short
description of your interest and current projects. An archive of back
issues of this digest is available by anonymous ftp from acm.princeton.edu.
========================================================================
Subject: Administration
Hopefully everybody who has sent me mail is currently on the list.
If you send me a bibliography of yourself, I will compile these and
post them in a future addition. This lets you know who else is on
the list, and what they are up to.
Submissions to the mailing list should go to sci-vi@acm.princeton.edu.
Requests for address changes, additions or deletions should go to
sci-vi-request@acm.princeton.edu.
Right now I have no real ideas about what relevant topics for discussion
are, so send me everything you think about that has anything to do with
the topic. If volume gets high and/or vacuous, I will consider rethinking
this policy. Until then, jabber away.
========================================================================
Welcome to the Sci-Vi Newsletter. I decided to form this mailing list
for several (almost selfish) reasons.
o to meet other people working in the field
o to have a forum to discuss new ideas, algorithms and projects
o to find out about new hardware and software that is
applicable to the field.
o to compile a bibliography of relevant papers and books
I hope that this newsletter will meet these goals, but remember, if you
would like this mailing list to be fun and exciting, then join in and
make some submissions.
========================================================================
Subject: Your Moderator
In a word, it's me. Mark VandeWettering, markv@acm.princeton.edu. Use this
mail address in cases of emergency only. sci-vi-request@acm.princeton.edu
is a much better choice for suggestions, additions and deletions.
I am currently employed by the Program in Applied and Computational
Mathematics at Princeton University. Whatever the official title of my
job is, my main area of concentration has been the creation of software
tools for examining the output of various computational fluid dynamics
simulations. I will detail a couple of my projects later.
In a previous graduate student life, I was the author a public domain
raytracer, and much interested in the fields of graphics, programming
languages and parallelism. I am also interested in astronomy and physics
of various flavors.
========================================================================
This volume is not really a volume at all. I merely thought that I would
toss out some topics that have come up in my recent work. The problems
raises range from trivial to deep, but hopefully they are relatively
thought provoking.
========================================================================
Subject: Volume Visualization
The major question that I have about volume visualization is:
How can I do it in real time?
or alternatively:
How can I almost do it in almost real time?
In more detail, I have an application which generates data volumes of
approximately 100^3 data points, with a scalar value defined at each grid
point. I would like to generate volume views of this data interactively
in real time. I have tried to develop several solutions, each of which
seems to give different combinations of speed/quality.
o "Pixar" style compositing of 2-d slices. This seems to work okay,
but generates images that have some artifacts because of the lack
of filtering done on individual slices as well as between slices.
One possible solution is to filter & composite them myself, using
a two-pass filtering algorithm. Has anybody done this? Can you
tell me what speeds you obtained? It takes the SGI ~1second to
draw a single 100x100 slice, or around 100 seconds for a whole
data volume. Can anyone do better?
o "Splatting", which was developed by Westover and Whitted
and discovered by myself as well. The idea is that a gridpoint
represents not just a point of data, but a "bump" of data. If that
distribution is symmetric in 3-d, then it forms a circle in 2-d.
Hence for each gridpoint, you draw a filtered "bump" of color,
which are composited either back to front or front to back.
I have had reasonably good luck doing this in a simpler way. Merely
plot lots of points with a gaussian distribution about the gridpoints
final 2-d screen coordinates, and then filter in a post process.
I can draw a 100^3 volume in ~10 seconds using this approach. The
quality isn't the greatest, but it does give a quick view of the
data with minimal programming problems.
o Raytracing, which is hardly interactive but which generates
the nicest quality images. Raytracing also has the nice property
that it can be done on irregular volumes in a relatively simple
way, and can integrate other kinds of primitives as well.
What are other people's experience with the above techniques. Any big wins
in efficiency to be gained in the above? Share your hints.
Note that splatting doesn't work at all well when you have an irregular grid
and that pixar style rendering essentially requires resampling. Since
many of my applications have irregular grids, this seems to be a serious
limitation.
========================================================================
Subject: Irregular Volumes and Interpolation
One of the typically used programs around our dept is a finite element
code called NEKTON. NEKTON generates output which consists of a number
of adjoining elements, each divided into several nodes. (A typical
model has 300 elements, each having 5x5x5 nodes). An output field
contains the scalars of interest at each node point. In order to determine
the value inside an element, 3-d Lagrangian interpolation is performed
on all the elements. Note that a simple interpolation like linear
interpolation is NOT meaningful. The reason the divisions were originally
chosen were precisely because linear interpolations aren't meaningful.
Problem: speed. Lagrangian interpolation in 1-d takes O(N) multiplies.
For 3-d, it takes O(N^3). N could be as large as 10 or 20, which is
lots of multiplies, especially since we are probably doing this interpolation
as part of an inner loop (raytracing, or contour finding). Anybody have
hints on efficient implementation of 3-D Lagrangian interpolations?
If you aren't doing volume rendering, but only surface-finding, you can
then use methods like Kalra's and Barr's use of Lipschitz constants to
assist in the raytracing of an explicit surface. More details are in
their Siggraph 89 paper. I am willing to discuss this in more detail if
people are interested.
Anyway, solutions to the lagrangian interpolation are:
o Accept it. Possible for 2-d cases, as well as non-interactive
3-d cases.
o Use a piecewise approximation to the surface. Not bad, although
I would like to be able to determine some quantitative error
estimates in order to have some idea about the relative accuracy
and precision of the interpolation. Suggestions on reading folks?
o Resample the original grid at a higher density, using the
Lagrangian interpolation formula. Store this data, and then use
linear (or some other low order) interpolation.
Ideas? Experience?
========================================================================
Subject: Color Spaces and Contour Plotting
One interesting way to make "quickie" contour plots is to use the gouraud
shading capabilities of modern workstation. For instance, if you have
a regular grid, you merely draw a whole bunch of grid squares, coloring
the vertices by the color map from your data values to colors. Voila!
Instant contour maps.
Well, almost. The problem is that linear interpolation of color doesn't
mean the same thing as interpolation in your color map. For example consider
your color map which has a black-white sine wave replicated five times
from your low to high value. If adjacent grid values are the min and max
of the field, then one might wish to have five "beats" in between the
grid points. What happens is simply a smooth linear interpolation between
the two.
This doesn't sound too bad, but it keeps you from having very discriminating
color maps, because they cause irritating aliasing artifacts.
A cure? Well, the SGI can gouraud shade in color map mode (although possibly
not for long). A more flexible rendering pipeline would allow you to
interpolate the actual scalar values over the triangle, and then map color.
This is one of several problems that I have had lately that could be
solved with a slightly more flexible graphics system than is typically
provided. Does anyone else have any items like this?
========================================================================
Subject: Bibliography
If you have a bibliography, or papers that are relavent to the field,
send the information to sci-vi@acm.princeton.edu. I will collate them,
and make them available for anonymous ftp and also announce them in
special editions of the newsletter.
========================================================================
Subject: Tell Me About Software
If you have software that is used for scientific visualization that you
have found useful (hopefully freely distributable) then send mail and
let the rest of us know about it. I am aware of the following systems:
apE Animation Production Environment (ftp from oscsuna.osc.edu)
xds X Data Slice (ftp from ftp.ncsa.uiuc.edu)
hdf UIUC's data format for data sets (same site as above)
cdf another data format, I like this one (ftp from unidata.ucar.edu)
I am preparing more in depth information about each of these, and will
include it in the next issue. Get your info in before then if you have
found some software that is useful.
========================================================================