TECHNIQUES FOR EFFICIENT SURFACE RENDERING IN VOLUME VISUALIZATION

Abstract

Marching Cubes (MC) is a widely used surface rendering algorithm. But there are still some problems with it: (1) The data structure for MC is not adequately efficient. (2) The number of triangles representing the surface generated by MC from a large sized data set is too big which leads to a long rendering time and a large storage requirement. (3) Small features could be handled more efficiently and reasonably. (4) The triangulated surface is not in the form of true meshes which results very poor rendering performance. This is because graphics hardware of today's workstation renders more efficiently if the triangle data is in the form of meshes. The solutions to the four problems with MC will be briefly presented in the sequence listed above. A new octree design called Mixture Octree (MO) has been proposed to reduce the space requirement when using the octree technique in MC. For typical examples, the amount of space saved is 20%. This new octree technique is especially useful for large gray-scale volumes with different powers of two in each dimension, which form non-full octrees. This technique can be used in the octree application areas, where data sets are gray-scale images and all of the volume is potentially interesting. As octree is a 30 generalization of the 2D quadtree, the same idea can also be employed for the quadtree. A new high resolution 3D surface construction algorithm called Adaptive Marching Cubes (AMC) has been presented to reduce the number of triangles representing a given surface. It significantly reduces the number of triangles by adapting the size of the triangles to the shape of the surface. This dramatically improves the performance of the manipulation of the 3D surfaces. A typical example shows that the number of triangles is reduced by 55%. The quality of images produced by AMC is similar to that of MC. One of the fundamental problems encountered with AMC is the crack problem. Cracks may be created between two neighboring processing units with different levels of subdivision. A proved simple but complete solution to the crack problem is proposed, and it requires only O(n2) working memory. A better approach has been proposed to represent small features whose size is less than a voxel, which is much more simpler and more efficient than the previous ones. This is based on the philosophy that small features at the same level of detail should be represented with equal accuracy. Another new algorithm has been designed to give the surface a mesh representation, which can take the advantages of graphics hardware to improve the rendering speed. We utilize a MC-like (Marching Cubes) approach to calculate the intersection points and their normals for each cube, but dynamically link the intersection points to form triangles within the cube according to the locations of the last and the next visited neighboring cubes so that a better meshed surface could be generated. Much of the difficulty is with the thousands of cases which need to be considered to produce the meshed surface. The idea of selectively meshing the surface leads to a few hundred cases, which makes the algorithm much simpler. Test results show that for the same surface the rendering time is almost halved compared to the time required for the rendering of a non-meshed representation generated by MC.