Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!voder!pyramid!prls!philabs!zhu
From: zhu@philabs.philips.com (Benjamin  Zhu)
Newsgroups: comp.graphics
Subject: Re: How to determine a surface with the required threshold value?
Message-ID: <107307@philabs.Philips.Com>
Date: 31 Aug 90 12:53:58 GMT
References: <107152@philabs.Philips.Com>
Sender: news@philabs.Philips.Com
Organization: Philips Laboratories, Briarcliff Manor, NY
Lines: 51

I get damned. Two of my previous messages did not seem to get posted.
One more, folks.

In article <107152@philabs.Philips.Com> zhu@philabs.philips.com (Benjamin  Zhu) writes:
>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.

  I guess I have not made my objective clear enough. It is different
from what the marching-cube algorithm achieves. The marching-cube
algorithm finds triangle patches which contruct the surface in a
cube.  Mine is to find the surface voxels in the cube each of which
is of size 1x1x1. Marching-cube accomplishes its work without dividing
the cube, whereas mine requires at least partially dividing the cube
by tri-linear interpolation (otherwise, there is no way to justify
whether a voxel is on the surface or not). OK, it is possible to modify
the marching-cube algorithm to suit my application by dividing the cube
into axbxc voxels first. This is just the naive way I mentioned here.
 
>2)...

  Another alternative is to use an incremental algorithm by
finding an initial voxel on the surface, which is trivial.
Then find more and more surface voxels by walking on the
surface (similar to the Bresenham algorithm). However, the
computation and efforts involved to maintain the coherence 
information are far more expensive than the second method.

>Ben
>
>Philips Laboratories			zhu@philabs.philips.com
>
>///////////////////////////////////////////////////////////////
>//
>//                    standard disclaimer
>//
>///////////////////////////////////////////////////////////////

Ben