NLM Home Page VHP Home Page


Next: Color Dipping Up: Title Page Previous: Color Segmentation Index: Full Text Index Contents: Conference Page 

Color Alligator Algorithm

     We present a modification to a marching cubes based algorithm [17], the alligator algorithm [13] that uses color to create 3D surface rendered objects with photo-realistic color. We developed the  color alligator algorithm in order to provide color 3D surface renderings of human anatomical structures. Its initial output provided bronchial tree, lung and heart renderings [10]. We also produced a number of 3D anatomic models for the pelvic anatomy lesson [27].

     The alligator algorithm was developed by Alan Kalvin and presented in his thesis at NYU in 1991. It is a 3D based surface construction algorithm that uses a beveled form boundary representation. It provides a surface that is both view and object orientation invariant. Two possible surface representations were considered by Kalvin, block form and beveled form. Block form uses voxels as cuboids and the voxel represents the face of the cuboid. Beveled form uses the voxels as lattice points on the grid.

     The beveled form boundary representation has the following properties. The faces of the object are not necessarily planar, each face contains 3 to 7 vertices, and each vertex lies on 4 edges and 4 faces. The beveled form was considered to be superior to a block form in that the block form could mistakenly have a common edge that is considered part of two adjacent surfaces. The beveled form would physically separate the edges. It was also felt by Kalvin that this representation was better for visualization, manipulation and mensuration since it was not restricted to planes parallel to the x, y or z-axis.

     Kalvin decided to used Baumgart's winged-edge representation as the main data structure in the algorithm [3]. It was chosen  since it was topologically consistent. Each edge in the representation has two distinct faces. Four adjacent edges are supplied to traverse the objects structure.The alligator algorithm uses all 255 cases of a super voxel in order to build a surface. It doesn't use the symmetry that the marching cubes algorithm does to reduce the number of cases. Because of this it doesn't have the problems with holes that the marching cubes algorithm has. We choose this algorithm over the standard marching cubes because of the lack of holes. Its sequential scanning of the input data was also considered an efficient use of memory.
 


Next: Color Dipping Up: Title Page Previous: Color Segmentation Index: Full Text Index Contents: Conference Page