A hidden-line algorithm for displaying curved surfaces by line drawing is presented. The algorithm divides the screen plane into small rectangles, unlike Ohno's algorithm, which divides the screen space into small 3D boxes and exploits quadrilateral coherence and depth coherence. The present algorithm is better than Ohno ' s in both speed and main memory requirements. Quantitative comparisons are given and examples shown.
algorithm, curved surfaces, hidden-line elimination
For displaying curved surfaces, hidden-line elimination techniques have received relatively little attention. Published papers on hidden-line techniques include those of Ohno 1, Griffiths 2, and Appel 3'4. Appel's algorithm is a complete brute force method; Griffiths discusses how to find the critical boundary. Ohno's algorithm is an improvement over Appel's, its main point being the use of the 3D subdivision method, which makes the algorithm about 10 times faster than Appel's, which did not exploit subdivision.
The idea of subdivision was originally mentioned by Griffiths 5. Griffiths used the 2D subdivision method to handle complex objects with polygonal faces. Ohno did not use the 2D subdivision method but rather the 3D one to handle parametrically defined curved surfaces. The reason might be that the 3D subdivision method is a little faster than the 2D one. But Ohno neglected the superiority of the 2D subdivision method over the 3D subdivision method in reducing the main memory requirement. Ohno also neglected quadrilateral coherence of parametrically defined curved surfaces. In Ohno's program, the number of subdivisions Ix, /y, and / z has a considerable effect on the efficiency of the program, but as the number of subdivisions /~, ly, and /z increases, the amount of memory used to store 3D screen boxes increases exponentially and the amount of memory used to store quadrilaterals also becomes too large.
The algorithm proposed here pays attention to exploiting quadrilateral coherence of parametrically defined curved surfaces. The proposed algorithm uses the 2D subdivision method, because quadrilateral coherence cooperates better with the 2D subdivision method than with the 3D subdivision method. In the proposed algorithm, both the 2D subdivision method and quadrilateral coherence are used to save memory.