17 Visible Surface Detection

T. Raghuveera

Objectives:

• Understand the need for Visible Surface Detection in Computer Graphics
• Learn the techniques behind the common visible surface detection methods

Discussion:

Imagine a 3D scene with a huge collection of objects, modelled using Mesh, spline or other techniques. Specifically if we assume mesh model, then the data about each of the polygonal faces that make up the mesh for a single object needs to be stored efficiently for manipulation at a later stage. If the scene has too many objects, imagine the amount of data to be stored and processed. It is therefore important that we handle this more efficiently and effectively. Visible Surface Detection algorithms help us achieve this goal. There are two fundamental steps in Visible Surface Detection process. The first step is to ‘identify the faces that are either visible or hidden from a given viewing position’, and the second step is ‘either to select the visible faces or discard the back faces as required’. In literature these techniques are referred to as Visible Surface Detection (VSD) methods / Hidden Surface removal (HSR) or Hidden Line Elimination (HLE) / Back face culling methods. Elimination of unwanted faces from the scene, given a viewing position, saves processing time and resources.

VSD methods are classified as either of the following: Object Space Methods, Image Space Methods and Mixed Methods. The Object Space Methods compare objects and parts of objects to each other within the scene definition to determine which surfaces as a whole we should label as visible. Ex: Back-Face detection, A-Buffer, BSP Tree, Octree and so on. In the Image Space Methods, visibility is decided point by point at each pixel position on the projection plane. Ex: Depth-Buffer / Z-Buffer, Scan-Line, Ray Casting. The Mixed Methods use both the techniques for deciding on the visibility. Ex: Depth Sorting, Area Sub-division. Irrespective of their class, all these methods are based on two underlying principles: Sorting and Coherence. Sorting is used to compare depths and order individual surfaces in a scene according to the distance from the view plane. Coherence is used to take advantage of regularities in a scene.

As we can see from figure below, a cube has 6 faces of which a maximum of three faces are only visible from any given viewing direction or position. Thus given a viewing position, three faces of the cube can be conveniently removed from view so that we can save processing time and resources. If we happen to view the cube from top or front or sides, only one face is visible and the rest of the five faces can be completely eliminated.

Sometimes, two objects might be positioned such that, one obscures the other, either fully or partially. In this case, and given a viewing direction, we may not be able to decide at the first instance, the faces that are visible or hidden. Let’s discuss VSD techniques with one example for each of the Object Space and Image Space classes.

Simple Back Face Detection (Object Space Method):

This is an Object Space Method, where we compare objects and parts of objects within the 3D scene definition to determine visible faces. A polygonal face in 3D is identified with the equation Ax+By+Cz+D = 0.

If the viewing vector is along the normal vector direction to a face, then we are seeing the backside of it. The concept is demonstrated in the figure above. A point P(x,y) is an inside point of a polygonal face, if Ax+By+Cz+D <0. When an inside point is along the line of sight to the surface, the polygon must be a back face.

If we assume that the viewing direction is along the –ve Zv direction, then, V=(0,0,Vz) and let N=(A,B,C), where N is the normal vector to the face. The polygon is a back face if V·N>0. The value of dot product between the vectors V and N will help us decide if the face is a back face. We know that, V·N = Vz.C. Since the viewing direction is along the -ve zv-direction, the polygon face is a back face if C≤0. Thus the simple back face detection method can be used to identify back faces with simple checks.

Z-Buffer / Depth Buffer Method (Image Space):

This is an Image Space method, where object depth is measured from the view plane along the negative z-axis of a viewing system (assuming Right Handed System for viewing coordinate system). Each surface of a scene is processed separately one point at a time across the surface. For the same pixel position if more than one face is aligned, then the color of the face with the least depth is selected for that pixel. This method can be applied to both planar and non-planar polygon surfaces. Two buffers are used, Depth buffer and Refresh buffer. Depth buffer is used to store depth values for each (x,y) position as surfaces are processed, and the refresh buffer stores the intensity values for each position.

Before we start we should initialize the depth and color values as given in the steps above. Now, to calculate the depth (z) of a polygonal face, we can use the equation of a face in 3D as Ax+By+Cz+D=0, where any point P(x,y,z) that satisfies the equation of the plane lies on the plane with z as the depth. Therefore,

For the next position on the view plane along the same scan line, i.e. at (x+1,y) we can calculate depth using the above equation by replacing x with x+1

Thus we can compute depths recursively along the same scan line and also we can compute depths along an edge of a face recursively. As shown in the figure below, once we know the

Y-extents of the polygon, we can start at a top vertex and recursively calculate x-positions down a left edge of the polygon as

Let’s look at the advantages and disadvantages of the above method.

Advantages:

• Easy to implement
• No sorting of surfaces is required
• Polygons may be processed in any order Disadvantages:
• Requires two buffers , depth and refresh
• It can only find one visible surface at each pixel position.
• It deals with only opaque surfaces

A-Buffer method (Image Space):

This method is an extension of the Depth Buffer method, where A stands for anti-aliased, area-averaged, accumulation-buffer. This method expands the depth-buffer so that each position in the buffer can reference a linked list of surfaces i.e., more than one surface intensity can be taken into consideration. It is sometimes the case that a face is semi-transparent and so the color at a given pixel position is an integral combination of colors of a collection of faces.

Each position in the A-Buffer has two fields, Depth field: Stores a depth value and Intensity field (stores surface data): The surface data may have multiple attributes like, RGB intensity components, Opacity parameter (percent of transparency), Depth, Percent of area coverage, Surface identifier, other surface rendering parameters, pointer to next surface.

Scan-Line Method (Image Space):

This is an extension of the scan-Line algorithm for filling polygon interiors. With the Depth Buffer / A-Buffer method, we can process only one surface at a time, but using this, we can process more than one surface at a time. For all polygons intersecting a scan line, the faces are processed from left to right. If there are overlapping faces, we should determine the depth so that the nearest face to the view-plane is identified and the intensity of that face is entered into the refresh buffer.

For each scan line an Active list of edges of faces is maintained, and they are sorted in the order of increasing x. In the above figure, there are two polygonal faces ABCD and EFGH and there is a partial overlap between them. For scan-line 1, the active list of edges can be written as AB, BC, EH, FG. Scan-lines 2, 3 have the same list of active edges AD, EH, BC, FG . For each surface, a flag is either set or reset to indicate whether on or outside of the surface. At the leftmost boundary of a surface, the surface flag is turned ON, and at the rightmost boundary of a surface, the surface flag is turned OFF.

For scan-line 1, the active edge list, AB, BC, EH, FG is processed from left to right. Between edges AB and BC, only the flag for surface S1 is ON and Intensity for surface S1 is entered into the refresh buffer. Between BC and EH, both the flags for S1 and S2 are OFF and so no intensity information needs to be stored. Between EH and FG, only the flag for surface S2 is ON and intensity for surface S2 is entered into the refresh buffer. No depth calculations are necessary for this scan-line, since there are no overlapping regions.

Scan-Lines 2 and 3, have the same active edge list, given as AD, EH, BC, and FG. Now to start with scan-line 2, between AD and EH, the flag for surface S1 is only ON. Between EH and BC, the flags for both S 1 and S2 are ON, since both of them overlap in this zone. Now Depth calculation is needed and if we assume at this point that, depth of surface S1 is lesser than that of S2, we need to store only the intensity of S1 into the refresh buffer until BC. Later S1 is OFF and intensity of S2 is stored, until FG. Since scan-lines 2 and 3 have the same active edge list and the processing steps being the same, we can take advantage of coherence. So it becomes unnecessary to make depth calculations between EH and BC for scan-line 3 explicitly.

Let’s note the advantages and disadvantages of this method.

Advantages:

• Any number of overlapping surfaces can be processed
• Takes advantage of coherence principle

Disadvantages:

• Does not work for surfaces that cut through or cyclically overlap each other.

BSP Tree Method (Object Space):

BSP stands for Binary Space Partitioning. This is an object space method of VSD. Here an imaginary infinitely extended plane divides the 3D space into two regions; say the front and the back. Here the front is the part of the 3D space on the front side of the infinitely extended dividing plane and so is the back, i.e., the region on the back side of it. Sometimes, outside and inside are used respectively in place of front and back. Now the space is again subdivided by other imaginary planes. This continues till all the objects in the scene are identified with respect to the dividing planes. The planes are generally identified as the infinitely extended versions of the surfaces of objects in the 3D scene. This division of space is done relative to a given viewing direction to identify which of the faces are on the inside or outside of the partitioning plane as shown in the figure below. A tree is formed and the terminal nodes of the tree are the objects in the scene.

In the figure above, plane P1 divides the space into two, so that we get two sets of objects. One set of objects are to the front of plane P1 (indicated by an arrow mark at one end) relative to the viewing direction, and the other set is on the back of plane P1. As shown in the figure above, since the triangle like object is intersected by plane P1, we divide that object into two separate objects and label them as say A and B. Now the objects A and C are in the front of P1 and objects B and D are in the back of P 1. We then partition the space again with another imaginary plane P2 as shown and we go on to construct the binary tree as shown. The left branch represents objects in the front and right branch, the objects in the back and the objects are represented as terminal nodes. When the BSP tree is complete, we process the tree by selecting the surfaces for display in the order back to front, so that foreground objects are painted over the background objects.

Summary:

• Understood the importance of VSD in Computer Graphics
• Learnt the most common methods available in the literature for achieving VSD.