johnston@lbl-csam.arpa (Bill Johnston [csr]) (02/17/89)
The medical imaging folks have developed a very nice algorithm called ``Marching Cubes'' for tessellating complex 3D surfaces: .ds [A W. Lorensen .as [A ", H. Cline .ds [T Marching Cubes: A High Resolution 3D Surface Construction Algorithm .ds [J Computer Graphics .ds [V 21 .ds [N 4 .ds [D 1987 .ds [O (Proceedings ACM SIGGRAPH, 1987.) This algorithm works locally, seeking to fit a surface through each elemental cube (voxel) (as defined by the the grid intersections) that intersects the surface. The result is a large number of small polygons that completely cover the surface f=C. For ``blobby molecules'' you might contour the electric field strength using Marching Cubes to tessellate the surface |E|=C. We have made an interesting movie of methane molecules trapped in a crystal lattice by just tessellating the Van der Waal's radii about the collection of atomic centers for methane. We did nothing more complex than tessellating a contour of the field f=x**2+y**2+z**2 about every atomic center, and let the hidden surface processing worry about the intersecting shperes. This, of course, does not give quite the blobbly appearence of |E| = C taken over the whole molecule. Be cautioned that the algorithm as presented at SIGGRAPH 87 has an error that causes small holes to appear in the tessellation at some saddle points on the surface. I talked to Bill Lorensen at SIGGRAPH last year and he said that he was going to publish a correction in the SIGGRAPH Quarterly. I don't know if he has done that yet, or not. We have an implementation of this algorithm that we will make available when we distribute our video movie making system software in a few months. See: .ds [A W. E. Johnston .as [A ", D. E. Hall .as [A ", J. Huang .as [A ", M. Rible .as [A ", D. Robertson .ds [T Distributed Scientific Video Movie Making .ds [J Proceedings of the Supercomputing Conference .ds [D 1988 .ds [O (The Computer Society of the IEEE.) Bill Johnston and David Robertson Lawrence Berkeley Laboratory (wejohnston@lbl.gov, ...ucbvax!lbl-csam.arpa!johnston) (dwrobertson@lbl.gov, ...ucbvax!lbl-csam.arpa!davidr)