The Importance of a Stable Clipping Algorithm

I recently started working on a new project involving a software renderer while at the same time trying out rendering techniques that I never got around to learning before. One such technique is the binary space partitioning tree. While the concept of BSP trees are fairly straightforward it surfaced an error in some old code that I imported into the project, namely the code that clips polygons against a single plane and outputs two polygons; one polygon wholly in front of the clipping plane, and one polygon wholly behind the clipping plane.

The general idea behind the creation of a BSP tree is to recursively subdivide the geometry by picking a an existing polygon hyperplane to split the geometry by and sorting them in three lists; a list for geometry in front of the hyperplane, a list for geometry behind the hyperplane, and a list for geometry that is coplanar in relation to the hyperplane. This process then recursively repeats for each of the newly created lists, except for the coplanar list which is already sorted. The exact stopping condition is determined by the programmer, although common stopping conditions include lists that only contain a single polygon, or lists that only contain a certain minimum amount of polygons. Care has to be taken when choosing the hyperplane to split by so as to avoid the tree from becoming too deep, or unbalanced. This is a science of its own and will be discussed in some other context.

When determining which list a polygon should be sorted in there can be four separate cases; a polygon is entirely in front of the hyperplane, a polygon is entirely behind the hyperplane, a polygon is coplanar in relation to the hyperplane, or a polygon intersects the hyperplane. For this last case a clipping algorithm is used. This algorithm literally splits a polygon into two parts; one part wholly in front of the hyperplane, and one part wholly behind the hyperplane, and then sorts the resulting polygons into their respective lists for further processing. This is the situation where a stable clipping algorithm becomes very important.

A stable clipping algorithm should never clip a polygon by a plane that it has already been clipped by once. More precisely, it should not generate a polygon on the opposite side of the plane, since that part has already been clipped away from the input polygon. An unstable clipping algorithm might generate two polygons despite the fact that such a polygon should not exist. For view frustum clipping a stable algorithm is not all too important since the polygons behind the clipping planes are discarded. As such, I was never able to identify the error earlier. For BSP tree generation an unstable clipping algorithm will almost certainly cause an infinite loop by constantly clipping the polygons that share an edge with the hyperplane.

The code I eventually came up with an algorithm that looks like the following:

The basic rundown of the algorithm is as follows. First, make room for the output polygon. Then pre-calculate all of the input vertices' signed distances to the plane. If all vertices are either behind the plane, or coinciding with the plane, then return an empty output polygon. The next part is the actual clipping. This requires comparing two connected vertices' distances. If the first vertex is in front of the plane, and the other is behind or coinciding with it, or if the first vertex is behind or coinciding with the plane, and the other is in front of it, then linearly project the first vertex to coincide with the plane. Additionally, if the first vertex is in front or coinciding with the plane then add it to the array of output vertices. A counter keeps track of the number of output vertices generated so far. Outside of the loop this counter will be used to re-size the output vertex array to correspond to the number of generated vertices. In order to get the polygon on the opposite side of the clipping plane, simply negate the plane normal and apply the algorithm to the original input data.

Remember that the output polygon has to be able to hold room for one more vertex than the number of input vertices since clipping against a single plane can logically only output that many vertices at most. Alternatively, you could use a list as the output data structure to avoid preallocation and resizing of data. If your algorithm potentially outputs more than one extra vertex then your algorithm is unstable and you should reconsider using it.

While the algorithm now ideally should work as expected, we are working with a finite amount of bits for out floating point types. This means that in practice the algorithm will not work reliably for anything but axis-aligned planes. This is where numerical stability becomes important. Implementing numerical stability in this case usually means nothing more than allowing some leeway in the classification of points as being either behind, in front, or coinciding. Therefore, the general algorithm remains exactly the same, with only a few adjustments in the implementation:

I wish to express some degree of caution. While the code works as expected for any input that I have given it I can not guarantee it to work for all possible inputs. Even I can err. As such, there may yet be come classes of cases that the above algorithm does not handle properly. If so, my apologies.

Resources

BSP Tree Frequently Asked Questions (FAQ) - Question 8 
Clipping a Convex Polygon Against a Plane