Efficient Calculation of Subdivision Surfaces for Visualization

A subdivision surface is defined by a polygonal mesh which is iteratively refined into an infinite sequence of meshes converging to the desired smooth surface. Classical subdivision schemes are those described and analysed by Catmull—Clark and Doo—Sabin. A graphical representation can be obtained by stopping the iteration on a level of refinement sufficient to yield a smooth representation when drawing the mesh on that level. However, the storage requirements of the finest mesh and those on the previous levels can be considerable, that is exponential in the number of iterations, since the number of mesh elements grows by a constant factor from level to level. We overcome this problem by deviating from level-wise breadth-first subdivision by subdividing the mesh locally in a depth-first manner over all levels of iteration. This results in a front of subdivision which moves over the surface and successively reports the elements of the finest mesh. Only the front of subdivision must be held in main memory, and it needs only about square-root of the space required by the standard method, at about the same time of computation.