On May 21st, 2010, I successfully defended my thesis, completing my Master's degree in Computer Science at DigiPen. The full title was "Non-Photorealistic Real-Time Edge Rendering using Non-Duplicate Parallel Detection and Capping", or more succinctly, "Edge Detection and Rendering with OpenCL." At the time, OpenCL, the massive data parallelism API for GPUs and other processors, was brand new. I had originally been researching non-photorealistic rendering (NPR) techniques in general when I realized that OpenCL could be used for graphics calculations not otherwise possible using normal shader capabilities. I narrowed my NPR studies down to just the edge detection and rendering aspects. I focused my thesis research on making a better edge rendering system.
My work was heavily influenced by Morgan McGuire's paper on GPU-accelerated edge detection. I believed I could use the different memory capabilities of OpenCL to improve upon his edge cap generation. In addition to occasionally rendering edge caps on top of edges, his technique had a failure case that would cause gaps to occur under certain conditions. My OpenCL-based caps, and the associated shader code, visually dealt with the problem by rendering "perfect" caps that exactly filled the gap between each set of two edges.
My technique produced better visual results, and was theoretically faster, though much more complicated. However, in practice, the technique was actually much slower when implemented in OpenCL itself, as opposed to simulating the technique on the CPU. The slowdown was most likely due to the unintentional overproduction of end caps, one for each possible combination of two edges, which could easily be greater than McGuire's purely shader technique. There might have also been issues related to sub-optimal parallel arithmetic operations, the overall newness of OpenCL and its drivers, and the lock-stepped nature of GPUs. That final reason was probably why my technique was faster when simulated on the CPU, which allows for real short-circuiting.
As an aside, I found a simple technique for creating distance-relative edge widths. This allows edges to appear bigger as they get closer to the camera, and smaller as they get further away. They also maintained a width of at least one pixel, ensuring that an edge always appeared no matter how far away it was. This technique allowed the edges to appear more "attached" to the object they were outlining than the traditional fixed size versions. These edges would also not completely overpower their objects as they got further away.
Downloads
- Thesis - the whole paper and addendums
- Conference Paper - compressed version of the technique in 6 pages
- Thesis Defense Slides - from the original thesis defense at DigiPen
- LSUS Slides - from a simplified defense given to the students of LSUS
