CPS 713

PARALLEL RENDERING

Paul Coddington and Alvin Leung Northeast Parallel Architectures Center

October 1994

COMPUTER GRAPHICS BACKGROUND

CPS 713 Parallel rendering  Computer graphics background

Introduction

The goal of computer graphics is to see a virtual world. This virtual world is composed of one of many different objects. The virtual world in this talk consists of two milk cartons.

Object representation

How the objects are represented in the object database have serious impact on the rendering performance, quality of the generated image and the time needed to construct the virtual world database.

The milk cartons can represented in two ways. The first method, the milk cartons are represented as a milk carton object. The scene designer only need to specified the dimension, the texture map and the color. Each object in turns are composed of number of rectangular and triangular 3D subobjects. These objects are analytically defined, so there is no limit on resolving the details of the object. The resolution of the object is bounded by the surface texture map, instead. Also, the subobject is position relatively to a anchor point of the object.

The second method on modeling the milk cartons is by polygons. Generally, 3 or 4 vertex polygons are used. Triangle is more often used because all vertices of a triangle are coplanar. Hence, the polygon will have only one normal. The scene designer will need to construct a milk carton one polygon at a time. Then define the surface texture and the color for each of the polygon. The motivation of defining an object by polygons is literary flexibility of the object. Each polygon is represented by a fixed set of point and edges. These point can be arbitrary in 3D space and the edges joins the points. Consequently, deforming an object is relative simple task. In this case, a filled milk carton’s side slightly warped.

A high quality scene rendering program uses a combination of two methods. In addition, polygons usually be replaced by surface patches, which use control points to define the surface. As a result, the warped side of a fill milk carton can have a smoother curvature. This is important because the accurate shadow computation requires accurate representation.

Transformation

Once the scene designer defined all the objects. The objects will be place at a specific location. In this example, the two objects is placed side by side. The placement of the object can be done by transformation. The transformation process includes translation, rotation and scaling, etc. Transformation is represented as 4x4 matrices. These matrices can be multiplied together to form one 4x4 matrix. Then the finally matrix is applied to transform the objects.

Transformation also used to place the virtual world in a viewer’s perspective, so that the image can be generated in the viewer’s perspective.

Back to the previous examples, an analytically defined object is placed by transforming the anchor point of the object. As a result, transformation can be done to the object as a whole. As a result, transformation process can be done in O(object).

However, Transformation of a polygon based object requires computation at each vertex. The transformation process requires O(all vertices).

Finally, window to viewport transformation is used to correctly scale and place the generated image on screen.

\underline{clipping}

Clipping is done to eliminated some of the objects or part of a object base on some user defined view volume.

The purpose of clipping are

• eliminate of some objects, so that the resulting image will be more pleasing. This is generally done to prevent a viewer, who is located too close or inside an object, to see a very uninteresting picture after a ”long” wait.

• reduce computation need. Clipping speed up the rendering process by eliminating object, which is outside the field of view. The object that are eliminated do not need any further processing. For example, A person resided in a close environment will not be able to see every object within the environment. Clipping, for example, can eliminate the objects behind the viewer.

hidden surface or object removal

Even when a object is located within the field of view, the object may still not be visible to the viewer, for example, a object located behind a closed door. This object have to be eliminated form the object rendering list, in order for the image to be correctly rendered. In addition, rendering an object requires considerable of computation effort. As a result, further speed up can be realized, if an object can be eliminated form the rendering list with considerable low cost. Hidden surface removal can also be done during rasterization. However, this process incurs considerable computing resources.

Rasterization

Rasterization is done to transform the data represented by the object database into a image. Texture mapping, color computation and anti-aliasing are done at this stage. For a polygon based object, scanline algorithm is commonly used to render the finial image.

TERRAIN RENDERING

CPS 713 Parallel rendering  Terrain rendering

Introduction

A terrain object is defined by a height field and a image. A height field, as the name suggest, encode information as height for a specific (x, y) coordinate. The image is the additional information for the specific (x, y) coordinate and is rendered by color. For example, a digital evaluation model and a settlate image of a land landscape shows the relationship between the land use and terrain evaluation. Since height field of a terrain surface is closed (ie no disjointed section), a terrain object can be manipulated as a 2D object with third dimension as special case.

Terrain object representation

The terrain data set is stored as two dimensional data grids. Each grid element contains a subsection of the terrain data set. A grid element can further subdivided to employ locality for better cache performance. A triangle is formed by three adjacent data points as show in figure. We choose polygon representation because interpolation of the evaluation and color within the polygon can provide more realistic landscape during close examination.

The terrain object will also have multi resolution data. This is motivated by further reducing the computational requirement, so that real time fly through can be done.

The terrain data can have four or more resolutions.

• Quart the number of evaluation data by interpolation (as show in figure). This will achieve the best resolution on polygon based terrain renderer. This data set is only use to very close

Paul Coddington, NPAC, paulc@npac.syr.edu  Oct 94, CPS-PR-13

examination. This may employ under special saturation.

• evaluation data at off the self accuracy.

The number of pixel covered by a line drop off linearly with respect to the distance. Hence, the area of a polygon on screen is reduce proportional to distance square. As show in the table, at a distance of 20000 feet, a triangle at most occupied 48 pixel, where 1 square in on the screen have approximate 10 000 pixel. As a result, when rendering terrain data further than 30000 with this data resolution is a complete waste of computational power.

CPS 713 Parallel rendering  Terrain rendering
Distance (ft) number of pixel  length on screen
1000  193.8  approx 2 in
5000  39.0  approx 1/3 in
5280 (1 mi)  37.0  apporx 1/3 in
10000  19.5  less than a 1/4 in
20000  9.8  approx 1/10 in
40000  4.8  aprrox 1/20 in (a big dust on screen)
80000  2.4  aprrox 1/40 in (a medium dust on screen)

• Evaluation data at medium accuracy. The resolution of the data is reduced, but higher resolution is maintained for special terrain features.

• Evaluation data at course accuracy. The resolution of the data is further reduced, but maintained accuracy representation of large terrain features.

CPS 713 Parallel rendering  Terrain rendering

The terrain rednering process

• Clipping (course)

Paul Coddington, NPAC, paulc@npac.syr.edu  Oct 94, CPS-PR-19

CPS 713 Parallel rendering  Terrain rendering

• Transformation

• Clipping (fine)

• Hidden surface removal (back facing cull)

• rasterization (scanline, Zbuffer, anti-aliasing)

PARALLEL TERRAIN REDNERING

CPS 713 Parallel rendering  Parallel terrain rednering

The grid data structure will be scatter decomposed across all processors. The redering pipeline remains the same as