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.

Selected Images

Ambient occlusion test scenes used in experiments (AO is exaggerated for visibility when printed small in the journal):

The performance table is also available for download.

Source Code and Dem

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{McGuire2011Clipping, 
  author = {Morgan McGuire}, 
  title = {Efficient Triangle and Quadrilateral Clipping within Shaders}, 
  journal = {The Journal of Graphics, {GPU}, and Game Tools},
  note = {Journal of Graphics, GPU, and Game Tools},
  year = {2011}, 
  pages = {TBD},
  number = {To appear},
  url = {https://casual-effects.com/research/McGuire2011Clipping/index.html}, 
  volume = {15},
}