Visible Surface Determination (Introduction to Computer Graphics Using Java 2D and 3D) Part 2

Spatial Partitioning

Back-face culling reduces the computational effort for visibility considerations. Spatial partitioning also tries to remove the computational effort further. The clipping volume is subdivided into disjoint regions, for instance into eight boxes of equal size. The objects are assigned to the corresponding box or boxes with which they have a nonempty intersection. An object that crosses the boundary of a box will be assigned to more than one box.

Fig. 7.4 Partitioning of the clipping volume for image-precision (left) and object-precision algorithms (right)

In case of an object-precision algorithm, only the objects within the same box have to be checked for visibility considerations for visible surface determination. If one box is behind another, all its objects will be projected before the objects from the box in front. In this way, objects from the front box will automatically overwrite objects from the box behind it that are hidden from view. For a partition of the clipping volume into k boxes, the n objects in the scene will be equally distributed over the boxes in the ideal case. This means that the computational complexity is reduced from n2 to k · (f)2 = γ. This is, however, only true if no object crosses the border of a box and the objects are equally distributed over the boxes, i.e., each box contains | objects. This assumption will definitely not be valid anymore when the partition contains a larger number of boxes and the boxes become too small.

For image-precision algorithms it is better to partition the clipping volume into boxes as is shown on the left of Fig. 7.4. The clipping rectangle on the projection plane is partitioned into smaller rectangles and each smaller rectangle induces a box in the clipping volume. For each pixel only those objects have to be considered that lie within the box that is associated with the smaller rectangle in which the pixel lies.

Recursive subdivision algorithms divide the clipping region farther and further until a region is small enough to decide which object is visible in it. An upper bound for the maximum depth of such recursive partitioning is given by the resolution of the image. Area subdivision algorithms partition the clipping rectangle on the projection plane recursively so that they are image-precision methods. Octree algorithms partition the clipping volume and are therefore object-precision methods.

Image-Precision Techniques

Three image-precision techniques will be introduced in this section. The most popular and important one is the z-buffer or depth-buffer algorithm.

The z-Buffer Algorithm

The z-buffer or depth-buffer algorithm is the most often applied technique for determining visible surfaces. The z-buffer algorithm is an image-precision technique which is based on the following principle. It uses a frame buffer for the colours of the pixels in the image and a z- or depth-buffer in which a z-value is entered for each pixel. The z-buffer is initialised with the distance or z-coordinate of the back clipping plane. The frame buffer is initialised with the background image or background colour. The objects are projected in an arbitrary order and the projections are stored in the frame buffer. If all objects were entered in this way into the frame buffer, then objects projected later would overwrite earlier projected objects when their projections overlap. Since the order of projection is not fixed, this could lead to the wrong result that objects farther away from the viewer hide objects from view that are closer to the viewer. Therefore, before a pixel of a projected object is entered into the frame buffer, its z-value, i.e., its distance to the projection plane, is compared to the value entered for the corresponding pixel so far in the z-buffer. If the value in the z-buffer is larger than the z-value of the point of the object that led to the projected pixel, then the new pixel colour is entered into the frame buffer and the z-value is also updated. If, on the other hand, the z-value corresponding to the projected pixel is larger than the value in the z-buffer, then neither the frame buffer nor the z-buffer is changed.

The principle of the z-buffer algorithm is illustrated in Fig. 7.5. There are two objects to be projected, a rectangle and an ellipse. The viewer looks at the scene from below the projection plane or the frame buffer. The frame buffer is initialised with the background colour—in this case white—and the z-buffer is initialised with the z-value of the back clipping plane. The values are not shown here. They could be —œ here, i.e., the back clipping plane could be moved to infinity. The rectangle is projected first. Since the rectangle lies within the clipping volume and its z-values are smaller than the z-values of the back clipping plane, the rectangle is projected to the frame buffer and its z-coordinates are entered in the z-buffer. When the ellipse is projected afterwards, it turns out that its z-values are even smaller where the ellipse and the rectangle overlap. Therefore, the ellipse overwrites the projection of the rectangle partly in the frame buffer and its z-values are also entered in the z-buffer.

Had the ellipse been projected before the rectangle, then the following would happen. When the rectangle is projected, there are already values in the z-buffer that are smaller than the z-values of the rectangle. Therefore, the rectangle will not be projected into the frame buffer where already smaller z-values coming from the ellipse are entered in the z-buffer. So even in this order of projection, the final result would be the same as in Fig. 7.5.

It should be noted that the z-values of an object are usually not constant. It must be decided individually for each pixel whether it should be entered into the frame and the z-buffer or not.

The z-buffer algorithm can be applied in a very efficient manner for animated scenes with moving objects when the viewer does not change his position. All objects that do not move form the background of the image. They need to be entered into the frame and the z-buffer just once. So each time a new image for the animated scene is generated, the frame and z-buffer are initialised with the static part of the scene. Only the moving objects have to be re-entered into the buffers. If a moving object is hidden from another static object in the scene, then this will be noticed since the z-value has been initialised with a corresponding lower value. The moving object will not be entered into the buffers in this case.

Fig. 7.5 Principle of the z-buffer algorithm

In order to enter polygons into the frame and the z-buffer, a scan line technique is applied to each pixel row in the projection plane. Let the plane induced by the polygon be given by the equation

The z-value along a scan line can be computed in the following form:

since the z-values of a plane change in a linear fashion when they are sampled along a line. Let zold be the z-coordinate of the projected polygon at pixel (x, y). The new z-coordinate znew for the following pixel (x + 1,y) must satisfy (7.2) for the plane as well as the previous point (x,y,zold) since both points lie in the plane. We have

Therefore, the change of the z-coordinate along the scan line is

Scan Line Technique for Edges

For the z-buffer algorithm, the projection of single polygons can be carried out on the basis of a scan line technique. As an alternative it is also possible to project the edges of all polygons and to apply a scan line technique to determine which polygons should be drawn.

The coordinate axes of the rectangular clipping area on the projection plane are denoted by u and v. This scan line technique is based on three tables. The edge table contains all nonhorizontal edges and has the following structure:

vmin is the smallest v-value of the projected edge, u(vmn) the u-value corresponding to vmin. vmax denotes the largest v-value of the edge. Au is the slope of the projected edge. The column polygon numbers contains the list of all polygons to which the edge belongs. The edges are sorted in increasing order with respect to their vmin-values. For identical vmin-values, edges with a smaller u(vmjn)-value come first.

The second table of this scan line technique is the polygon table, containing information about the polygons in the following form:

The polygon number serves as a key or identifier for the polygon. The coefficients A, B, C, D define the plane corresponding to the polygon in terms of the equation

The column colour contains the colour or information about the shading of the polygon. If only a single value can be entered there, the possibilities for realistic shading are very restricted. In-flag indicates whether the actual position on the scan line lies within or outside the polygon.

The last table contains the list of all active edges. Active edges are those edges which intersect the actual scan line. These edges are sorted by the u -components of the intersection points in increasing order. The number of rows of the table of active edges can be different for each scan line. The number of rows and the entries of the other two tables remain constant except for the entries in the column with the In-flag.

Fig. 7.6 Determining the active edges for the scan lines V1, V2, V3, V4

For the configuration shown in Fig. 7.6, the following edges are active for the scan lines vi, v2, v3, v4, respectively:

When a single scan line is considered, the active edges are determined first and all In-flags are set to zero. When the line is scanned, each time an edge is crossed, the In-flags of the associated polygons have to be inverted from 0 to 1 or from 1 back to 0 since crossing an edge means that one enters or leaves the polygon. At each pixel, the visible polygon among those with In-flag = 1 has to be determined. For this purpose, the z-value of each polygon with In-flag = 1 is computed based on the equation for the plane. The polygon with the smallest z-value is the one that is visible at the considered pixel. The corresponding z-value of the polygon can be determined in an incremental fashion in the same way as in the z-buffer algorithm.