Antialiasing method for computer graphics

[0002] This application relates generally to systems for computer graphics. More specifically, the present invention includes a method and apparatus for improving the quality of images that include aliased pixels.

[0003] Computer systems (and related devices) typically create three-dimensional images using a sequence of stages known as a graphics pipeline. During early pipeline stages, images are modeled using a mosaic-like approach where each image is composed of a collection of individual points, lines and polygons. These points, lines and polygons are know as primitives and a single image may require thousands, or even millions, of primitives. Each primitive is defined in terms of its shape and location as well as other attributes, such as color and texture.

[0004] The primitives used in early pipeline stages are transformed, during a rasterization stage, into collections of pixels. The rasterization stage is often performed by a specialized graphics processor (in low-end systems, rasterization may be performed directly by the host processor) and the resulting pixels are stored in a device known as a frame buffer. A frame buffer is a memory device that includes individual memory locations for each pixel.

[0005] During the rasterization stage, the graphics processor renders each primitive into the frame buffer. The graphics processor accomplishes this task by determining which frame buffer memory locations are included within the bounds of each primitive. The included memory locations are then initialized to reflect the attributes of the primitive, including color and texture.

[0006] Textures are the visual or tactile surface characteristics and appearance of an object. Depicting texture in a realistic manner is an important part of making three-dimensional images believable and is usually done by mapping texture images onto the primitives within an image. This process is known as texture mapping.

[0007] To be realistic, the texture mapping process must be configured to account for varying distances within an image. Textures that appear realistic when applied to nearby objects must be adjusted before they are applied to more distant objects. In many cases, this is done by precomputing a series of images to represent a single texture at different distances. The first image has the highest resolution and covers the greatest pixel area. Each succeeding image has a lower resolution and covers a smaller pixel area. The graphics system dynamically selects the correct image from the series based on the distance to the eye point and viewing angle. The entire series is typically stored in a data structure known as a mipmap.

[0008] While effective, the use of mipmaps and other pre-filtered texture images does not entirely solve the problem of applying textures to represent varying distances. This follows because mipmaps are typically generated isotropically. Each succeeding image is a square that is half as tall and half as wide as the preceding image. Unfortunately, objects within images don't scale isotropically. Instead, objects both narrow and lengthen as they move from near to far. An object that is square when viewed in the foreground will appear rectangular when it is viewed at a distance. This causes problems when textures are applied to distant objects. Textures that are chosen to match an object's width may fall short of matching the object's height. Conversely, textures that match an object's height are often too wide for the object's width.

[0009] This type of mismatch means that the texturing process must be reconfigured to avoid pixel aliasing. This is typically accomplished by using lower resolution textures that are correctly dimensioned for one direction. Unfortunately, this causes the textures to blur along a second, orthogonal direction. This blurring is the visual result of information that is lost during the texturing process.

[0010] Texturing is not the only time at which pixel aliasing is a cause for concern. In fact, pixel aliasing occurs for many reasons. Aliasing can occur, for example, wherever two primitives overlap or at the edge of a primitive. Within regions of overlap, pixels can be split between multiple primitives. Rendering a pixel based on the attributes of one of these primitives can cause the pixel to be incorrectly rendered for remaining primitives. Aliasing of this type often results in stair step or otherwise jagged boundaries between overlapping primitives.

[0011] The overall effect of pixel aliasing is a reduction in image quality. As a result, a number of antialiasing methods have been developed. These methods attempt to reduce the number of aliased pixels or render them in a way that hides their aliased nature. Unfortunately, most of these methods require specialized hardware support to execute efficiently. This makes these methods unavailable in systems that do not include the required hardware support. Most antialiasing methods are also applied on an whole image basis. This means that antialiasing is applied to an entire image, even where it is only required for a small portion. This can be inefficient and increase the time required to render complex images.

[0012] For these reasons, a need exists for improving the quality of images that include aliased pixels. This need is particularly important where mipmaps are constructed using isotropic scaling and particularly important for systems that do not provide specialized antialiasing hardware.

[0013] An embodiment of the present invention includes a method and apparatus for improving the quality of images that include aliased pixels. For the method of the present invention, one or more portions of an image are selected for antialiasing. The selection process is preferably tailored to choose the image portions where highly accurate rendering is most important. In a flight simulator, these image portions might include the depictions of other aircraft or targets. In other cases, it may be practical to select the entire image for processing.

[0014] Each selected portion is rendered into the frame buffer. The resolution used for this rendering is higher than the original resolution of the selected image portion. For example, an image portion that normally would occupy a sixteen by sixteen pixel grid might be rendered as a forty-eight by forty-eight grid of pixels.

[0015] After rendering each image portion is read back from the frame buffer into a texture memory or texture cache. The image portions are now treated as textures. Each textures is applied to a quadrilateral that is drawn orthogonally to the viewer in the frame buffer. The quadrilaterals are sized to match the normal resolution of the image portions. As a result, the textures (which are created at a higher resolution) must be filtered to fit their quadrilaterals. The texturing hardware performs this process using weighted averages of the pixels included in the textures. The overall result is that the quadrilaterals are supersampled from the original image. This improves antialiasing and ensures that the textures applied to the quadrilaterals are anisotropic to a degree that matches the image resize.

[0016] Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.

[0017] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate several embodiments of the invention and, together with the description, serve to explain the principles of the invention.

[0018] FIG. 1 is a block diagram of a host computer system shown as an exemplary environment for an embodiment of the present invention.

[0019] FIG. 2 is a sample image shown as a potential application for the present invention.

[0020] FIG. 3 is a flowchart showing the steps associated with an embodiment of the antialiasing method of the present invention.

[0021] FIG. 4 is a portion of the image of FIG. 2 as selected by the method of FIG. 3.

[0022] FIG. 5 shows the image portion of FIG. 4 as rendered by the method of FIG. 3.

[0023] FIG. 6 is a block diagram showing the relationship between pixels before and after filtering.

[0024] Reference will now by made in detail to preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever convenient, the same reference numbers will be used throughout the drawings to refer to the same of like parts.

[0025] In FIG. 1, a computer system 100 is shown as a representative environment for the present invention. Structurally, computer system 100 includes a processor, or processors 102, and a memory 104. An input device 106 and an output device 108 are connected to processor 102 and memory 104. Input device 106 and output device 108 represent a wide range of varying I/O devices such as disk drives, keyboards, modems, network adapters, printers and displays. Each node 102 may also includes a disk drive 110 of any suitable disk drive type (equivalently, disk drive 110 may be any non-volatile mass storage system such as “flash” memory). Computer system 100 also preferably includes a graphics processor 112 of any suitable type. Graphics processor 112 implements all of the tasks required to translate graphics primitives and attributes to displayable output.

[0026] An embodiment of the present invention includes a method and apparatus for improving the quality of images that include aliased pixels. The method and apparatus of the present invention are better understood by reference to FIG. 2 where a representative image is shown and generally designated 200. Image 200 depicts a runway 202 surrounded by a series of runway lights, of which runway lights 204athrough 204eare representative. Image 200 also includes aircraft 206aand 206b. Image 200 is shown with an eye point 208. Eye point 208 represents the position at which image 200 is viewed. Eye point 208 is intended to be movable relative to image 200. This means that components of image 200, including runway 202, runway lights 204 and aircraft 206 may be viewed from a range of positions.

[0027] An embodiment of the antialiasing method is shown is designated 300 in FIG. 3. Method 300 begins, symbolically, with start placeholder 302. In step 304, computer system 100 selects an image portion to be antialiased. In general, any portion of an image may be selected, including the entire image. In many cases, however, it will be preferably to apply the method to one or more image portions. These portions may be areas where pixel aliasing is likely to be present. Alternatively, the selected image portions may be areas where realistic rendering is highly important. For the example of FIG. 2, aircraft 206 represent regions where realistic rendering may be highly important. Based on this, FIG. 4 shows aircraft 206aas an image portion selected for antialiasing.

[0028] In step 306, computer system 100 renders the selected image portion into its frame buffer. The selected image portion is rendered at a size that exceeds the original size of the selected image portion. Typically, the magnification will be a power of two, such as two, four or sixteen. This is shown in FIG. 5, where magnification by a factor of two has been used to create a rendered image that is twice as wide and twice as high and the selected portion of FIG. 4.

[0029] In step 308, computer system 100 retrieves the rendered image portion from the frame buffer. The rendered image portion is treated as a texture having the magnified dimensions of the rendered image portion. Computer system 100 stores this texture in a texture cache or other memory.

[0030] In step 310, computer system 100 minifies the texture retrieved in the previous step so that it matches the size of the image portion selected in step 304. In many cases, computer system 100 will include specialized hardware to perform this type of filtering. Where specialized hardware is not provided, the texture may be filtered by software. Method 300 shows minification as a separate step. It should be appreciated that this is representative, and that minification can be performed any time between step 308 and step 312, inclusive. Thus, minification may be performed as part of image readback (step 308) or image rendering (step 312).

[0031] In general, a wide range of methods may be used to filter the texture. One method is to form pixels within the filtered texture using weighted averages of adjacent pixels in the unfiltered texture. This can be better understood by reference to FIG. 6 where a series of pixels from an unfiltered texture are shown as unfilled circles. Corresponding pixels from a filtered texture are shown as filled circles. Each pixel from the filtered texture is formed as a weighted average of the four surrounding pixels from the unfiltered texture. In this method, often referred to as bilinear filtering, each pixel in the filtered texture replaces four pixels in the unfiltered texture. This four to one reduction in pixels creates a filtered texture that is half as high, and half as wide, and the unfiltered texture.

[0032] Regardless of the filtering method used, the overall effect is to supersample pixels in the unfiltered texture. Each pixel in the filtered texture is formed as blend of multiple pixels in the unfiltered texture. This improves antialiasing within the filtered texture. In particular, it ensures that the filtered texture is anisotropic to a degree that matches the reduction in image size between the unfiltered texture and the filtered texture.

[0033] In step 312, computer system 100 applies the minified texture to a quadrilateral within the frame buffer. The quadrilateral is dimensioned to replicate the size of the image portion selected in step 304. It should be noted that step 310 (minification) and step 312 (application to the quadrilateral) are described separately only for the purposes of description. In many environments, these steps may be performed as part of a single atomic operation.

[0034] The application performed in step 312 is preferably configured to correctly model the visibility of the image portion within the scene being rendered. One way to accomplish this goal is to use alpha or transparency blending. The use of alpha or transparency blending in step 312 is enhanced if step 306 (rendering of the selected image portion in the frame buffer) is modified to use a black background. This prevents the background from contributing to the appearance of any non-opaque regions of the selected image portion. A second way to model visibility is to use depth information (i.e., Z-buffer values). To use depth information, step 312 is modified to draw the textured quadrilateral at a constant depth within the frame buffer. The constant depth defines which portions of the scene being rendered lie in front of the textured quadrilateral and which portions of the image being rendered lie behind the textured quadrilateral.

[0035] As discussed, the selected image portion is magnified and the resulting texture is minified (see steps 306 and 310). In the described embodiment the degree of magnification matches the degree of minification and is typically an even power of two, such as two, four or sixteen. The actual degree chosen depends on several factors. One of these is the amount of antialiasing needed. Higher degrees of magnification and minification yield more complete antialiasing. The degree of magnification and minification chosen also depends on the hardware support provided by computer system 100. In many cases, computer systems will include specialized hardware that performs the minification required by step 310. Most environments that provide this type of support do so only for predefined degrees of minification. In these cases, it is preferable to configured the antialiasing process to use the degree of minification for which hardware support is provided.

[0036] In some cases, the minification process (step 310) may be repeated in cascaded fashion. For example, a single texture may be minified twice using the same four-to-one reduction. This would provide a sixteen-to-one reduction and may be used in environments where direct support for sixteen-to-one reductions is not provided. In the context of Method 300, the overall minification (i.e., the result of the cascaded filtering) would match the magnification factor used in step 306.

[0037] Other embodiments be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope of the invention being indicated by the following claims and equivalents.