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.