Parallel pipelined merge engines

Details Parallel pipelined merge engines Parallel pipelined merge engines

1999-03-08

2004-06-22

Luu, Matthew (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

C345S619000, C345S630000, C345S632000, C345S634000

Reexamination Certificate

active

06753878

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to image generation in general and in particular to rendering engines for generating images that might be needed to be generated in real-time response to an input of objects in a scene.
Rendering is the process of computing a two-dimensional viewpoint dependent image of a three-dimensional geometric model. Rendering is computationally intensive, since a typical geometric model might contain objects that collectively comprise millions of polygons. In the typical rendering engine, a geometry stage first converts mathematical descriptions of arbitrarily complex objects into a collection of polygons, typically triangles, so that subsequent rendering stages only need to deal with simply polygons. The rendering stages then need to simulate the transport of light at various wavelengths emitted from numerous light sources in the geometric model and scattered by surfaces of objects in the geometric model.
Two common methods of handing light-object interactions are known as “ray tracing” and “radiosity” methods. If those methods are implemented in software, the software can take from minutes to days to produce a single high quality “photorealistic” image of a large geometric model. A typical photorealistic image might require a resolution of 2000 pixels by 1000 pixels and contain a million or more separately specified scene elements (i.e., objects or light sources). While days might be available for rendering some images, many applications require real-time rendering of video frames, such as computer games, flight simulators, scientific visualizers, computer-aided designcomputer-aided engineering (CAD/CAE) applications and medical data visualizers.
With real-time rendering of video frames, the delay allowed between the receipt of a geometric model and the output of the corresponding image is determined, in part, by the frame rate. In some applications, the frame rate can be as low as one frame per minute, so a viable rendering system for that application must produce at least one image per minute if it is to run at an acceptable rate. In many applications, such as computer animation or flight simulation, the rendering system is expected to run at thirty frames or more per second. In some thirty framesecond applications, the delay might need to be even less, as might be the case for a flight simulator or computer game having feedback. With such a system, an operator of the system provides inputs, such as commands to move up, down or sideways, and the corresponding changes to the geometric model are provided to a rendering engine. To avoid the feeling of “sea-sickness” that occurs when an image is out of sync with other stimuli, the rendering engine might have to generate an image from a geometry model in even less time than a frame period.
Existing software rendering engines are generally unable to meet such performance requirements, but some hardware rendering engines have been able to approach these performance requirements, although not always for a practical cost. Generally, in order to generate images of reasonable resolution in {fraction (1/30)}
th
of a second or less, a hardware approach known as a “graphics pipeline” is used to achieve real-time image generation.
A graphics pipeline comprises a few well-understood stages: the geometry stage, the rendering stage and the composition stage. In a rendering engine with a graphics pipeline, some or all of these stages are implemented in parallel.
In the geometry stage, a database of geometric objects (usually triangles) is read from host memory and transformed from a world coordinate system (“object space”) into a view dependent coordinate system (“screen space”). In some cases, the geometry stage might also perform the conversion of complex objects into simplified objects comprising polygons. Because all polygons can be represented as triangles, and processing triangles is simpler than processing polygons with more than three sides, nearly all existing rendering engines limit geometric objects to triangles. With triangles, each vertex is defined by a coordinate (x, y, z) and a surface normal vector (dx, dy, dz) and might also be defined by surface material properties (such as a coefficient of reflectivity and transmissivity) and the surface may be bound to textures. The geometry stage converts the vertex coordinates and normals from object space representations into their screen space counterparts (with a resolution being a function of the resolution of the output image) and discards objects that fall entirely outside the perimeter of the screen (the “view surface”). The geometry stage also performs lighting calculations, as needed, at the vertices for use by later stages that will interpolate these results at individual pixels.
Once the geometric model is represented as polygons in screen space, the rendering stage calculates the pixel color values that correspond to those polygons. Where the rendering stage is performed by a plurality of rendering engines, the composition stage combines the results from the parallel rendering engines to form the final image. With parallel processing, there are several considerations, such as load balancing and thread independence. The goal of load balancing is to ensure that the work to be done is evenly distributed over all of the parallel threads, to avoid having some threads idle while others are still processing. Thread independence is desirable, since independent threads will not be held up waiting for other threads to reach a certain point in their processing. Some thread dependence might be unavoidable, but such dependence might not always result in additional delays.
One approach to dividing up the work among a plurality of threads is known as the “sort-middle” architecture. In a “sort-middle” approach, the screen space is divided into tiles and each tile is assigned a bin, where the bin corresponds to the work one rendering thread will perform. The objects comprising the geometric stage's output are then allocated to the bins, with each object only being allocated to the bins of the tiles that the object intersects. Within each bin, a Z-comparison (depth comparison) is performed to determine which object is closest to the screen within each pixel of that bin's tile. Shading and blending calculations are then performed to compute the amount of light reflected at each wavelength (typically the three wavelengths r, g and b) by the closest object in each pixel, after textures have been taken into account. The result of this calculation is the color value (e.g., r, g and b values) of the pixel.
Another approach is the “sort-last” architecture wherein, instead of subdividing the screen, the objects are allocated randomly to the bins and each thread does a Z-comparison on the objects-in its bin. Each thread computes an entire screen image, albeit an incorrect one containing less than all of the objects in the geometric model. The Z (depth) information is stored along with the pixel color values.
The composition stage in a sort-middle architecture simply combines the subimages for each tile into the final image. The composition stage in a “sort-last” architecture uses the Z information to merge all of the part (“incorrect”) images to produce a single correct image. With a sort-last composition stage, a merge engine is used to combine the part images by identifying which objects in which part images overlap which objects in other part images. In some cases, where there are many parallel threads, the composition stage might be done in parallel. Sort-last architectures typically provide better load balancing than sort-middle architectures, since some sort-middle threads might be allocated tiles that contain few or no objects.
The actual process of rendering, in a single thread, using hardware is highly developed and many products are available that can quickly render objects into images. Such products often support standard command sets, such as the OpenGL API (application programming interface), a low-level programming interface th

Affiliated with

Also associated with

Rating

Parallel pipelined merge engines does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel pipelined merge engines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel pipelined merge engines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3317638