Efficient Triangle and Quadrilateral Clipping
within Shaders

Abstract

Clipping a triangle or a convex quadrilateral to a plane is a common operation in computer graphics. This clipping is implemented by fixed-function units within the graphics pipeline under most rasterization APIs. It is increasingly interesting to perform clipping in programmable stages as well. For example, to clip bounding volumes generated in the Geometry unit to the near plane, or to clip an area light source to the tangent plane of a surface in a Pixel unit.

While clipping a convex polygon is algorithmically trivial, doing so efficiently on vector architectures like GPUs can be tricky. This article presents an efficient implementation of Sutherland-Hodgman clipping for vector processors. It has high branch coherence, uses only register storage (i.e., it does not require a move-relative memory operation), leverages both data and instruction parallelism, and has a peak register count of only two 4-vectors (7 scalars).

I found it to be about five times faster than direct Sutherland-Hodgman and yield a 45% increase in net throughput when applied in the algorithm from a previous publication on two different GPU architectures. The principles of optimization presented for this class of parallel algorithm extend to other algorithms and architectures.

Results

Source Code and Demo

clip.glsl is the GLSL 1.20 source for the triangle and quadrilateral clipping routine. You can directly include it in your own shaders. I release it to the Public Domain, but appreciate acknowledgement.

You can also download code.zip containing a Windows executable and full Visual Studio C++ source code giving an example of an application using the shader in a simple context. That demo requires the G3D Innovation Engine to re-build from source.

BibTex


@article{McGuireClipping11,
 author = {Morgan Mc{G}uire},
 title = {Efficient Triangle and Quadrilateral Clipping within Shaders},
 journal = {Journal of Graphics, GPU, and Game Tools},
 volume = {15},
 number = {To appear},
 pages = {TBD},
 year = {2011},
 URL = {http://graphics.cs.williams.edu/papers/ClipJGT11/}
}