Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-03-02
2001-07-24
Nguyen, Phu (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06266065
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer graphics and, more particularly, to an improved method for rendering three dimensional triangle primitives.
2. Description of Related Art
Computer graphics have many applications. Improvements in computer graphics displays are desirable.
FIG. 1
depicts a conventional computer system
100
. The computer system
100
has a processor
102
comprising one or more CPUs, a main memory
104
, a disk memory
106
, and an input device
108
, such as a keyboard and mouse. These devices
102
-
108
are connected to a bus
120
which transfers data, i.e., instructions and information, between the devices
102
-
108
. A graphics controller
130
is also connected to the bus
120
. As shown, the graphics controller
130
includes a drawing processor
132
. The drawing processor
132
is also connected to an address generator
134
and a data input of a frame buffer
136
and a Z buffer
138
. The address generator
134
, in turn, is connected to RAS (row address select) (not shown), CAS (column address select) (not shown), and chip select inputs (not shown) of the frame buffer
136
and Z buffer
138
. Illustratively, the frame and Z buffers
136
,
138
are implemented with plural VRAMs (video random access memories) or DRAMs (dynamic random access memories). The frame buffer
136
is connected to a display device
140
, such as a cathode ray tube (CRT) or liquid crystal display (LCD) monitor.
The drawing processor
132
receives instructions from the processor
102
for drawing objects. For instance, in the case of a computer aided design (CAD) application, the processor
102
may receive user input regarding creating and locating objects in three dimensional (3D) space. The processor
102
, in turn, transfers instructions regarding the size, location, texture, translucence, etc. of such objects to the drawing processor
132
. In response, the drawing processor
132
creates a picture element (pixel) image representation of a plane of view of such objects in 3D space. The pixels of the image of each plane of view form part of a frame that is stored by the drawing processor
132
in the frame buffer
136
. In 3D graphics applications, each pixel has color data (e.g., data for the red, green, and blue values of the pixel), and Z-values, relating to the Z-coordinate, or depth, of a graphical image. The pixel color data is stored in the frame buffer
136
. The pixel Z-values are stored in the Z buffer
138
. In two dimensional (2-D) applications, the Z-buffer
138
may be used as an additional frame buffer to hold pixel color data. Drawing processors
132
are known, such as is disclosed in U.S. Pat. Nos. 5,046,023 and 5,185,856. The latter reference discloses a drawing processor that is specifically adapted for rendering 3D objects. The contents of these patents are incorporated herein by reference.
One way of drawing 3D representations of polygons is to decompose each polygon into a number of “primitive” shapes, such as lines, polygons, circles, and ellipses. One common primitive is a triangle. Current three 3D computer graphic methods for rendering triangles do not provide high quality images. There are several problems in rendering high quality triangles.
One problem in drawing a triangle is due to the structure of the display device
140
on which graphics are displayed. As seen in
FIG. 2
, a display device
140
comprises a number of horizontal rows
202
of pixels
204
. The display device may be thought of, in effect, as a cartesian coordinate plane wherein the pixels
204
are located at the intersections between lines in the x and y planes (the x and y planes are illustrated with dashed lines).
Excellent quality straight lines may be displayed if the lines are horizontal, vertical, or at a 45° angle with respect to the x-y plane. Difficulties in displaying excellent lines occurs when a line is at an angle other than 45°. (This invention does not involve curved lines or circles, and the difficulties in drawing such lines are not discussed.) As seen in
FIG. 3
, a line
300
has a slope in which few points fall at intersections (points
302
,
304
). This means that in many locations along the line, the line does not fall on the screen where there are pixels.
Many methods exist for drawing lines approximating the correct line (these methods are called “edge walking” when drawing a polygon), and are not described in detail. See, for example, Foley, Van Dam, Feiner & Hughes,
Computer Graphics Principles and Practice
, Chapter 3, Addison-Wesley Publishing Co., 1992. Typically, each time the line increases one unit in either the x or y direction (for example, the y direction), the computer determines the nearest pixel in the perpendicular direction (i.e., the x direction) that is located on that line (i.e., the y plane). For example, when the line
300
crosses line
306
in the y plane, the computer determines that the nearest pixel in the x plane is the pixel
308
directly above. Thus, that pixel is illuminated according to the color, luminescence, etc. of the line being drawn. A second problem with rendering high quality triangles is the drawbacks of existing triangle rendering methods. There are three well known methods for computer graphic rendering of triangles. These methods are (1) span line rendering; (2) triangle drawing; and (3) trapezoid rendering. Span line rendering is performed by drawing a number of lines of varying length. The starting and ending point for each span-line is separately calculated. The edges of each triangle are iterated to produce a set of point-sampled spans. The slopes and starting vertex are used to iterate the pixels forming the span. The large number of calculations results in poor performance (e.g., is slow).
Triangle drawing is performed by sending to the drawing processor the value of each of the three vertices and edge slope. This method is used by many 3D graphics accelerator ASICs currently found in personal computers.
In trapezoid rendering, a polygon is decomposed into a number of trapezoid primitives. Once decomposed, the trapezoids are formed from the two scan lines (a “top” and a “bottom” of the trapezoid) and two line segments (the “sides”). Trapezoids are drawn by stepping down the line segments with two vector generators and filling in all the pixels between them for each scan line.
Each of these methods has drawbacks. Span line rendering has poor performance (e.g., is slow) and without Z error correction, the image quality is poor. If Z error correction is used, the image quality is acceptable, but the performance is further reduced because an error correction value is calculated for each span. The triangle rendering method has a greater performance than the span line method, but has poor image quality because it does not support Z error correction. Trapezoid rendering is difficult because it is difficult to divide a complex polygon into a number of trapezoids. (On the other hand, a complex polygon is easily divided into a number of triangles by simply connecting vertices.) The trapezoid rendering method performs about as well as the triangle drawing method, but has good image quality and performance if used with Z error correction.
Several problems rendering high quality triangles is described with references to one well known method of rendering a 3D triangle are. A triangle typically has one dominant side and two subordinate sides. The dominant side is the side having the greatest range of y values. The triangle
400
shown in
FIG. 4A
has its dominant side
402
on the left side, and the two subordinate sides
404
,
406
to the right. The triangle
450
in
FIG. 4B
has its dominant side
452
on the right, and the two subordinate sides
454
,
456
to the left. Triangles are drawn from the subordinate side to the dominant side. A starting point on the subordinant side and the ending point on the dominant side of each scan line may be calculated.
The vertices on the top and bottom of the dominant side are designated as P1 and P3. T
Chia Wei-Kuo
Hwang Shu-Fang
Yang Yea-Yun
Industrial Technology Research Institute
Nguyen Phu
Proskauer Rose LLP
LandOfFree
Method for rendering 3D triangle primitives does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for rendering 3D triangle primitives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rendering 3D triangle primitives will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452740