Render optimization using page alignment techniques

Details Render optimization using page alignment techniques Render optimization using page alignment techniques

1998-09-17

2001-04-24

Tung, Kee M. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphic processing system

C345S504000

Reexamination Certificate

active

06222561

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to rendering in data processing system displays and in particular to rendering primitives processed as multiple, parallel horizontal or vertical scan lines. Still more particularly, the present invention relates to optimizing frame buffer utilization during rendering by minimizing page boundary crossings.
2. Description of the Related Art
Rendering within data processing systems is the process of generating two dimensional images of data for display on a monitor. Typically, rendering includes processing geometric primitives (e.g., points, lines and polygons) to determine component pixel values for the monitor display, a process often referred to specifically as rasterization.
The pixels for the display area of a data processing system monitor are conventionally viewed as a matrix. The pixel matrix and/or the frame buffer, which stores rendered pixel information from which the display is refreshed, are typically partitioned for manageability. Pixel information may be partitioned in a contiguous fashion as illustrated in
FIG. 5A
, with all data within a frame buffer or frame buffer partition corresponding to a contiguous region of adjacent pixels, or in an interleaved fashion as illustrated in
FIG. 5B
, with each frame buffer containing every nth pixel of every mth line in the matrix. A 4×1 interleaved partitioning of display pixels to frame buffers is depicted in FIG.
5
B.
Rendering primitives to generate frame buffer data typically involves dividing the primitive into scan lines, single-pixel thick horizontal or vertical regions of the primitive. Scan lines are also referred to as spans, a term used interchangeably to refer to a scan line or the series of adjacent pixels which make up a scan line.
FIG. 5C
depicts two horizontal scan lines defined by endpoint pixels P
0
(i)-P
n
(i) and P
0
(i+1)-P
n
(i+1) within a primitive defined by vertices V
1
, V
2
, and V
3
. Although the primitive in the example shown in
FIG. 5C
is divided into horizontal scan lines, vertical scan lines may be utilized with no greater complexity, and frequently are employed.
When rendering, conventionally a scan line is started from an initial point P
0
(i) and rendered along the scan line until the end of the span is reached at P
n
(i). The next scan line is then begun at an initial point P
0
(i+1) at the same end as the point at which the previous scan line was started, and the next scan line is rendered in the same direction as the previous scan line. Scan lines may be rendered a single pixel at a time, or multiple adjacent pixels may be rendered concurrently so that the scan line is rendered in unit of m pixels. Additionally, multiple scan lines may be rendered in parallel, so that m pixels of n scan lines are processed concurrently, then the next m pixels of the same n scan lines are rendered, and so forth until the end of the scan line is reached, when the next n adjacent scan lines are started. Thus, the primitive is effectively rendered in as many blocks of n×m pixels as is required.
One problem in rendering primitives as described above is that the fill rate for the primitive is directly associated with frame buffer utilization. Each frame buffer or frame buffer partition may contain multiple memory pages. If the pixel information for pixels within a scan line bridges a page boundary within the frame buffer or frame buffer partition, rendering a primitive may require multiple frame buffer page-ins and page-outs per scan line. Each time a page boundary is crossed and frame buffer pages must be paged-in or paged-out of the cache, a substantial performance penalty is incurred. The greater the number of memory page crossings, the lower the performance of the rendering system and the lower the primitive fill rate.
Cache techniques may improve rendering performance by delay frame buffer memory accesses. However, the cache itself is typically mapped directly to the frame buffer(s) in a tiled fashion (that is, where each cache segment containing pixel information for multiple pixel segments, where scan lines are rendered a pixel segment at a time), and is not dynamically resizable for rendering individual primitives.
It would be desirable, therefore, to provide a mechanism for rendering primitives which minimized page crossing during rendering of primitive scan lines.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method and apparatus for rendering in data processing system displays.
It is another object of the present invention to provide an improved method and apparatus for rendering primitives processed in data processing systems as multiple, parallel horizontal or vertical scan lines.
It is yet another object of the present invention to provide a method and apparatus for optimizing frame buffer utilization during rendering by minimizing page boundary crossings.
The foregoing objects are achieved as is now described. To reduce the performance penalty associated with frame buffer memory access times for each page when rendering a primitive having scan lines which cross page boundaries, rendering is constrained to a single page at a time. All pixels mapping to a currently-cached frame buffer page are rendered before loading a different frame buffer page into the cache in order to render other pixels within the primitive. Any pixels within a scan region which map to a different page than the active page are temporarily skipped until all pixels mapping to the current page are completed. only when no more pixels require rendering within the primitive which map to the currently active frame buffer page is another frame buffer page loaded and all pixels mapping to that page are rendered. In processing a scan region which crosses a page boundary, the next pixel or pixel group to be rendered is examined to determine if it maps to the currently active frame buffer page. If so, it is rendered; if not, however, the position is latched, together with any other necessary state information, and rendering proceeds with the next scan region. Once all pixels for a currently active page are rendered, the latched position is loaded, together with the frame buffer page necessary to render the corresponding pixels, and rendering of the primitive proceeds until complete. The reduction in page change performance penalty more than offsets any increase in rendering complexity required to completely render one side of a page boundary before beginning the other side.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.


REFERENCES:
patent: 5056044 (1991-10-01), Frederickson et al.
patent: 5371514 (1994-12-01), Lawless et al.
patent: 5548709 (1996-08-01), Hannah et al.
patent: 5602984 (1997-02-01), Mieras
patent: 5706481 (1998-01-01), Hannah et al.
patent: 6088018 (2000-07-01), DeLeeuw et al.

Affiliated with

Also associated with

Rating

Render optimization using page alignment techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Render optimization using page alignment techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Render optimization using page alignment techniques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2470397