Viewport clipping is one of the essential stages within the 3D geometry pipeline. Since 3D hardware cannot accept position values outside the viewing frustum, we have to look for vertices that are outside this boundary and remove them from further processing steps. Any polygons which are only partially on-screen must be clipped by the screen volume boundaries. In this article I’ll show some techniques for speeding up the process of clipping polygons, using Intel’s Streaming SIMD Extension instructions.

The Sutherland-Hodgeman Clipping Algorithm

The most used algorithm for clipping convex polygons is the Sutherland-Hodgeman algorithm. Here are the functions used by the algorithm, in pseudo code:

state(Clip plane C, Vertex v)
//This function returns "inside" if v is
// inside clip plane C.

next(Vertex v)
//This function returns the next vertex
// after v in the polygon.

interpolate(Vertex v, Vertex v’, Clip plane C)
//This function returns an interpolated
// vertex v’’ interpolated from v and v’
// according to the C plane.

Pseudo code for the algorithm looks like this:

S0 = initial polygon
For each clip plane C

S1 = empty set

For each vertex v in S0 do:

If state(C,v) = "inside" then

S1 = S1 + {v}

v’ = next(v)

If state(C,v) <> state(C,v1) then

S1=S1 + interpolate(v,v’,C)

S0 = S1

Result = S0

Because of its iterative nature, optimizing the entire algorithm using Streaming SIMD Extensions is difficult. However, two of its critical functions can easily be optimized: the generation of clip flags, and the interpolation of two vertices into a new vertex.

Generating Clip Flags

Most applications implement the state function as a bit array assigned to each vertex, where each bit represents the state for a specific clip plane (where a value of ‘1’ indicates the vertex is outside the plane), and these bit arrays are usually called "clip flags". Clip flags are usually calculated before or during the transformation part of the geometry pipeline, and by using Boolean operations on these clip flags we can determine whether we need to enter the clipping algorithm itself or dump the entire polygon from further processing steps.

If the AND of all the clip flags is a value other than 0, it means the all of the polygon’s vertices are outside of at least one of the clip planes, indicating that the entire polygon is outside the view volume and therefore it can be dumped. On the other hand, if the OR of all the clip flags is equal to 0, it means that the entire polygon is inside the view volume and it can be submitted to the rasterizer without further processing.

Clip flags are usually generated in object space (before transformation) or in screen space (after transformation), and there are several Streaming SIMD Extension techniques for each one of these options.