Tuesday, 9 June 2009

Butt stroking and other stuff

Well that was a long wet dreary weekend. I managed to avoid leaving the house (getting through some old stuff in the cupboard and freezer at last) ... and of course spent an inordinate amount of time hacking away.

OpenVG needs a lot of scaffolding to get started - so I spent a lot of time doing that. Lots of code for getting and setting attributes and whatnot. And the path type. So I had to brush up on splines and geometric algorithms again, and I was back in the land of vectors and splines and whatnot - again. I wrote a nice little non-recursive adaptive spline tessellator I could use for implementing some of the features required like path length.

I originally wrote a vgpath that worked the same way as the reference implementation ... but just about the time I got most of it finished I got sick of writing yet-another-loop that parsed the data in slightly different ways, so I decided to change it around a bit, focussing on simplifying the code. So basically now I only have to canonicalise the data once, and the other functions can work on a simplified data stream, and not have to calculate relative or partial coordinates or smooth control points or arcs (although I haven't done them yet) or even data conversion every time they run. e.g. VLINE/HLINE are converted to LINE, all _RELs are converted to _ABSs, SCUBIC/SQUAD converted to QUAD, ARC's into QUAD's. I think doing that will still honour the API and it simplifies other bits of code. But since this is only the 2nd attempt I've probably got this wrong too - always seems to take 3 goes to get something right (as I write this I'm already thinking of some things I did wrong).

A few short lines of code later and I had it hooked up to the FreeType renderer and discovered the headline bug above. Butt line endings wasn't implemented, although it took a while to discover that since I just assumed it must be my code since the enumeration existed. I've submitted a patch which has already been applied (I must've been a bit tired as it took me a while to realise why 'butt stroking bug freetype' didn't find anything relevant, but seemed to probe the darker regions of the internets instead). I played around with the stroker a bit more and found other issues, and ended up delving into the source code more deeply - now I'm not sure I will use the FreeType stroker and renderer as I'd hoped to. To start with, a couple of features are missing or different. And it is, as they say on the box 'optimised for small sizes'. The algorithm is quite interesting though - basically it renders a band (ideally the whole image) into a 'sparse' bitmap, and then just steps through that to produce runs of filled pixels by keep track of edge crossings. So unlike a normal scan-line renderer it doesn't need to keep track of active lists and so forth, or update the lines piecemeal. Unfortunately I don't have a real handle on how scalable the algorithm is to screen-size resolutions. I may have to 'suck it and see', otherwise I'll get no where ...

... Since, to cut a long story short I've started delving into the mysterious and dark corridors of writing my own AA renderer. I orignally looked at FreeType because 1. I intend to use it anyway for font glyphs, and 2. It has few dependencies, and 3. It's easy to use. I'd also considered libart, but I thought was more closely tied to glib than it is, but it also no longer seems to be maintained, and apart from that it looks a bit over-engineered for my taste. And well, writing my own could be interesting - until you hit all the weird edge cases and numerical stability issues that throw it under a bridge. I still have at the back of my mind the idea of making this run well on a Cell BE too, so that's another reason to investigate since I need to know how it works, even if I just adapt another bit of code.

No comments: