How do I render thick 2D lines as polygons?

A simple method off the top of my head.

Bisect the angle of each 2d Vertex, this will create a nice miter line. Then move along that line, both inward and outward, the amount of your "thickness" (or thickness divided by two?), you now have your inner and outer polygon points. Move to the next point, repeat the same process, building your new polygon points along the way. Then apply a triangualtion to get your render-ready vertexes.

I just found this amazing work:

http://www.codeproject.com/Articles/226569/Drawing-polylines-by-tessellation

It seems to do exactly what you want, and its licence allows to use it even in commercial applications. Plus, the author did a truly great job to detail his method. I'll probably give it a shot at some point to replace my own not-nearly-as-perfect implementation.

Oh well - I've tried to solve that problem myself. I wasted two month on a solution that tried to solve the zero overdraw problem. As you've already found out you can't deal with all degenerated cases and have zero overdraw at the same time.

You can however use a hybrid approach:

Write yourself a routine that checks if the joins can be constructed from simple geometry without problems. To do so you have to check the join-angle, the width of the line and the length of the joined line-segments (line-segments that are shorter than their width are a PITA). With some heuristics you should be able to sort out all the trivial cases.

I don't know how your average line-data looks like, but in my case more than 90% of the wide lines had no degenerated cases.

For all other lines:

You've most probably already found out that if you tolerate overdraw, generating the geometry is a lot easier. Do so, and let a polygon CSG algorithm and a tesselation algorithm do the hard job.

I've evaluated most of the available tesselation packages, and I ended up with the GLU tesselator. It was fast, robust, never crashed (unlike most other algorithms). It was free and the license allowed me to include it in a commercial program. The quality and speed of the tesselation is okay. You will not get delaunay triangulation quality, but since you just need the triangles for rendering that's not a problem.

Since I disliked the tesselator API I lifted the tesselation code from the free SGI OpenGL reference implementation, rewrote the entire front-end and added memory pools to get the number of allocations down. It took two days to do this, but it was well worth it (like factor five performance improvement). The solution ended up in a commercial OpenVG implementation btw :-)

If you're rendering with OpenGL on a PC, you may want to move the tesselation/CSG-job from the CPU to the GPU and use stencil-buffer or z-buffer tricks to remove the overdraw. That's a lot easier and may be even faster than CPU tesselation.