Hidden Line Elimination in Projected Grid Surfaces

Abstract

The graph of a function defined on a rectangle is a surface in three-space and can be represented in a two-dimensional medium by a contour map or a projected image. While a contour map contains more exact information about the function, a projected image is more helpful in visualizing the surface's shape. In practice, a function is often presented as a set of values on ~.:v points of a grid. Its graph can then be approximated by a "grid surface" consisting of straight-edged regions. The task of generating images of grid surfaces can be performed by general hidden line algorithms [3, 5]. However, the relative slowness of these algorithms has prompted the development of methods specifically designed for grid surfaces [2, 4, 6, 7]. Previous methods for drawing grid surfaces have achieved speed at the expense of exactness and generality. Butland's algorithm [2] is exact and linear-time, but it is restricted to parallel projection using a viewing direction whose projection on the x-y plane makes an angle with the x-axis which is a multiple of 45 degrees. The algorithm of Kubert, Szabo, and Gulieri [4] uses time of the order n 1.~ and is not exact because segments which are partially hidden are not drawn at all. Williamson's algorithm [6] can be used to draw either x- or y-direction lines in the grid exactly, but not both. Furthermore, it is based on the assumption that the perimeter of the image of a grid surface can be divided into upper and lower