mdk

Vector drawing: OpenGL polygon tessellation

16 Aug 2007 » permalink

After having looked into the hardware-accelerated bezier curve computations I checked something more difficult and closer to the reality: hardware-accelerated arbitrary polygon tessellation with OpenGL. This topic has been covered by Zack some time ago, spawning a lot of flame (as most of the GNOME vs. KDE performance comparisons do). All benchmarks are flawed, of course.

Test case

I used same setup as with my previous experiment. This time I measured the real framerate to make sure that no anomaly occurs due to GL async API. Each frame of the test consists of random flowers being drawn to screen with random parameters. Each flower is a polygon outlined by eight bezier curves. The flower shape is not special/optimized in any way. Any closed polygon made out of any number of curves could be used for this purpose. Summarizing:

• Thinkpad t43 with ATI mobility x300 card (fglrx proprietary driver with GL support)
• 200 flowers being drawn in each frame
• Each flower has a random position, rotation, scale and fill
• Fill is a linear gradient from a random RGBA color to another random RGBA color
• 640x480 space is used
• Same set of random data was used in both examples
• Anti-aliasing was turned on
• cairo 1.4.10-1 was used in the cairo version
• Source code for the programs

 

The OpenGL rendering seems to be a pixel “fatter” than the cairo version (prolly a bug in my code). The GL output seems to be slightly brighter blended. I guess the significant difference between cairo x surface performance and cairo image surface performance also comes from the intensive blending.

Optimizations

Some optimizations in the GL code could be made to speed up the code even further:

• Computed bezier vertices could be stored (even as compiled vertices, if available) to skip the need to generate them twice for the anti-aliasing run.
• As in my prev example, vertex shader could be used to generate bezier points. That would require a different way to get the polygon extents though.
• The quality of the curve approximation (detail level) doesn’t seem to affect performance much and could be increased.

Algorithm

To render the polygons I'm using a variation of the stencil-based algorithm described in the OpenGL Red Book. It relies on a 1bit stencil buffer, which is commonly available. The basic method is:

• Disable framebuffer, enable stencil buffer & stencil testing.
• Draw triangle fans for every vertex in the polygon with an odd-even stencil flip rule.
• Enable framebuffer, disable stencil writes, keep stencil testing.
• Draw anti-aliased outline of the polygon but only where the stencil bit is not set (those are the anti-aliasing artifact pixels that theoretically doesn’t belong to the shape).
• Switch stencil test rule to pass only when stencil bit is set.
• Switch stencil write to zero the bit when passed (spares us a separate stencil clear call later on).
• Render the actual polygon shape with ie. quad.

Worthy benefit of this approach is that it fits (works with) all the standard OpenGL matrix transformations, depth buffer testing, texturing model etc. It can be easily extended with 2d boolean operations. The CPU is not performing any calculations (except the original path calculation which can be offset to the GPU with a vertex shader).

Once in a while I'm getting questions how did I implement hardware-accelerated video color space conversions in Diva. I'm going to write a bit about that soon along with some boolean operations coverage.