1. Field of the Invention
The present invention relates to a system and method for the generation of images of three-dimensional surfaces on a computer graphics display. More specifically the present invention relates to generating such images without aliasing effects and without the need for special hardware.
2. Description of the Prior Art
Surface data typically consists of a two-dimensional array of values that represent surface heights. For example, this is the standard form of data in a digital terrain model. There are two main classes of techniques for generating an image of such a surface: polygon-based techniques and ray-tracing techniques. Polygon-based techniques divide the surface into shaded polygons, which are then projected to the display screen. Ray-tracing techniques trace rays from the display screen to their intersections with the surface. Ray-tracing techniques produce highly realistic images but, are very slow due to the computational burden of searching for ray-surface intersections. Polygon techniques, on the other hand, are much faster but, they are still slow due the problem of detecting and removing hidden portions of the surface.
Three techniques for hidden surface removal, which are well-known in the art, are the z-buffer (or depth buffer) method, the scan-line method and the depth-sorting method. The z-buffer method tests the visibility of surfaces one point at a time. For each pixel location on the display screen, the polygon that is closest to the screen and projects to that pixel is visible. Scan-line methods generalize this approach by testing the visibility of polygons for each horizontal or vertical scan line of the display screen. The screen is divided into horizontal or vertical lines, and as each line is processed, all polygons intersecting that line are examined to determine which are nearest to the screen. The depth sorting method, on the other hand, sons the polygons in order of nearness to the display screen. The polygons are then projected to the screen in order, beginning with the farthest polygon. The nearer polygons overwrite the farther ones, thereby obscuring them.
Although faster than ray-tracing techniques, polygon techniques are very slow when the surface has many polygons. A surface defined on a 1000.times.1000-element grid, for example, has one million square polygons. Fitting a fewer number of polygons to the surface speeds up the image generation process but, causes the loss of surface detail such as roughness and texture. To speed up the image generation process, many polygon techniques require specialized three-dimensional graphics hardware. Many workstations, personal computers, notebook computers, and personal digital assistants (PDA) however, do not have this specialized hardware. Furthermore, these algorithms generally suffer from aliasing effects due to pixel discretization, which results in jagged lines and edges.
To generate images of surfaces more quickly, a prior art technique has been developed that exploits the gridded structure of a surface to remove hidden surfaces more quickly. This technique is described in "Fast Perspective Views of Images Using One-Dimensional Operations" by P. K. Robertson in the February 1987 issue of IEEE Computer Graphics and Applications. This technique first resamples the surface so that the columns of the grid on which it is defined project to the vertical columns of pixels on the display screen. As a result, any surface point can be occluded only by other points in front of it in the same column. The image is then generated by projecting the surface points to the display screen from back to front, so that the nearer points overwrite the farther ones. Although this method is much faster than previous methods, it suffers from aliasing effects that are caused by pixels overwriting other pixels. For example, the boundary of a portion of the surface that occludes another portion of the surface will appear jagged. A tall, narrow peak will also appear jagged. In addition, if detailed image or texture data is overlaid on the surface, the overlaid image or texture will be severely degraded by the pixel overwriting.
There is a long-felt need in the art for a graphics display technique that can create images of three-dimensional surfaces in real time without aliasing effects. There is also a long-felt need to produce images on a workstation, PC, notebook computer, PDA or other computer system without the need for specialized three-dimensional graphics hardware.