Xref: utzoo comp.graphics:8843 sci.math.num-analysis:359
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!princeton!phoenix!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics,sci.math.num-analysis
Subject: Sci Vi Newsletter, v00.00
Message-ID: <11939@phoenix.Princeton.EDU>
Date: 5 Dec 89 00:40:50 GMT
Sender: news@phoenix.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU ()
Followup-To: comp.graphics
Organization: Princeton University
Lines: 226

========================================================================

      ()           _    _     _ __                _
      /\          ' )  /     ' )  )              //   _/_ _/_
     /  )  _. 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.

========================================================================


Brought to you by Super Global Mega Corp .com