zhu@philabs.philips.com (Benjamin Zhu) (08/30/90)
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 // ///////////////////////////////////////////////////////////////
zhu@philabs.philips.com (Benjamin Zhu) (08/31/90)
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