Display Of Three-Dimensional Discrete Surfaces

AbstractThe currently-existing 3-D imaging technologies provide 3-D digital images of scenes in the form of 3-D arrays of numbers. In the representation of an object as a set of voxels, a boundary surface of the object is a set of faces of voxels. In spite of the large number of faces that form a boundary surface of a typical object/ fast algorithms for hidden part suppression and shading of such surfaces are made possible by the simplicity of the geometry of the 3-D voxel environment. However/ because of the very limited number (only three) of orientations of the faces/ the shading rule based on the direction cosine of the face normals and distance of the faces from the observer sometimes produces rough display images of originally smooth surfaces. This causes an undesirable change of smoothness of the display image from one view to another in a dynamic mode of display. We propose a contextual shading scheme which assigns shading to a face based on the local shape of the surface in the neighborhood of the face. The number of computations required per face is kept to a minimum by precomputing and storing all the possible direction cosines used for shading. The new shading algorithm has speeds comparable to that of the algorithm based on three face orientations/ and produces far better display images.IntroductionWith the advent of a number of 3-D imaging technologies/ 3-D digital images have become quite common in many scientific fields. The presence of enormous amounts of information inherent in such images calls for computationally efficient modalities of presenting such information to a human observer. One such recent and popular modality/ particularly in the area of computerized tomography/ has been the shaded-surface display1' 2' of the objects present in a given 3-D image.There are essentially two approaches to the shaded-surface display problem. The difference in the approaches stems from the difference in the methods of representing objects in the 3-D image. In the first approach/ a set of contours is used to define the object regions in a sequence of slices. The boundary surfaces of the object are produced either by tiling contours in successive slices with triangular patches2 or by fitting surface elements to the contours by the method of lofting using cardinal splines.3 In the second approach/ a set of volume elements (voxels) represents an object in the 3-D image. A boundary surface of the object is a set of faces of voxels. The set of voxels representing the object is determined through a segmentation of the 3-D image. A specified boundary surface of the object is determined by tracking through the connected set of faces comprising the boundary surface.1* Alternatively/ if the object region is specified by a set of contours on a sequence of slices/ the boundary surfaces of the object can be formed as a collection of faces of those voxels lying "just adjacent" to the given contours.5 The representation in the second approach can handle objects of very complex shape. Such complex objects are commonly encountered in medical applications.1'**Having represented a boundary surface by the first approach as a mosaic of polygons/ conventional techniques of hidden surface suppression and shading6 along with other techniques of providing depth cues/ can be applied to the mosaic to produce the display picture. A boundary surface produced by the second approach (called the cuberille approach7 ) consists of square faces in one of three possible orientations. This greatly simplifies the hidden surface removal and shading algorithms7 making them efficiently executable for surfaces consisting of a very large number of faces/ often of the order of 106 . However/ the very limited number of face orientations sometimes causes the originally smooth surfaces to appear jagged in the display image. Besides/ in a dynamic mode of display, there is sometimes an unnatural change of the pattern of shade from one view to another. To overcome these undesirable effects/ we propose a contextual shading scheme which determines the shading associated with a face from the direction cosines of the normals of the faces in its neighborhood. The information regarding the faces in the neighborhood of a given face is gathered during boundary surface detection and incorporated into its description. This makes it possible to keep the additional computations required in assigning shading to a face to a minimum. We include a number of illustrations derived from computerized tomography data.