Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!srhqla!quad1!ttidca!philabs!zhu
From: zhu@philabs.philips.com (Benjamin  Zhu)
Newsgroups: comp.graphics
Subject: How to determine a surface with the required threshold value?
Message-ID: <107152@philabs.Philips.Com>
Date: 29 Aug 90 20:54:42 GMT
Sender: news@philabs.Philips.Com
Organization: Philips Laboratories, Briarcliff Manor, NY
Lines: 48

I have the following problem:

We are given a huge cube (axbxc, a = 1000, b = 1000, c = 1000).
The node values for the cube vertices are also known. I want
to find the surface consisting of many 1x1x1 voxels whose values
are the same as the pre-defined threshold. Without loss of
generality, assume some cube vertices have values greater
than the threshold, whereas the other have values less than
the threshold. In other words, the surface we are looking for
intersects this huge cube. I want to find the surface really
fast by tri-linear interpolation. 

1) The naive way would be to tri-linearly interpolate node
   values for vertices of each 1x1x1 voxel. Then scan each
   voxel to determine whether it is on the surface or not.

2) A smarter way is to pick two planes (say z = 0 and z = c),
   and linearly interpolate a value for each pixel on these
   two planes. Then use a scheme similar to a scanline algorithm
   to determine where the scanline from a pixel on the z = 0
   plane to the corresponding pixel on the z = c plane
   intersects the surface.

The second method is ok, but it still has not sufficiently 
utilized the spatial coherence. For example, we might find
places on the z planes which are impossible to generate the
required surface voxels by tri-linear interpolation. Moreover,
by selecting planes other than the z planes as our starting
point, it is possible to speed up the surface-rendering
process (details are omitted).

I am not trying to answer this question by myself. I just want
to know if there is already some algorithm to deal this (or
similar) problem. If there is, I would not bother to waste
my time on this matter. Otherwise, I need to do some detailed
case study. If appropriate, I will summerize the result. By
the way, it is trivial to see that the surface is non-planar
except the extreme cases.

Ben

Philips Laboratories			zhu@philabs.philips.com

///////////////////////////////////////////////////////////////
//
//                    standard disclaimer
//
///////////////////////////////////////////////////////////////