Hey guys and gals,
Started playing with vectors on the GPU last year but it sort of ground to a halt really, I didn’t like the ugly aliasing and let face it vectors should look smooth as a peach. Anyway, skip forward until flash player 11.6 beta was released supporting new shader op codes (namely ddx and ddy) woo, now I had the ability to add in that sweet sweet anti aliasing by leveraging the screen space derivatives!
Cool so now that I was able to render filled triangles and bezier curves (and soooooo close to cubic curves too – need help on this one though), I thought it should be easy to tie it in to the new readGraphicsData command as seen here:
Query Graphics Data
Sadly not quite as straight forward as you might think!
The readGraphicsData method returns all the information to serialize the graphics of any object with graphics in it in flash! But there are still a few difficulties with parsing this data for use on the GPU.
Here are some of the issues:
- Determining if a bezier curve is concave or convex (this depends on what side of the closed region the curve is on)
- Determining if two curves overlap (i.e. in long sweeping thin curves… in this case the curve may need to be broken down into smaller curves)
- Gradients fills! A couple of problems here, 1 is reversing the gradient matrix and the other is to replicate it on the GPU. Simple gradient fills are possible but can get complex easily as you start added more than two colours (maybe at this point a 1×256 pixel texture could be used as a lookup) . That said I have not got round to this yet so might not be to bad.
- TRIANGULATION!!!!!! This is the real problem here… (at least to me it is). So from the output of the readGraphicsData we have extracted all the curves and along the way we have collected a series of points. These points make up the triangles that we use to fill the solid sections of the shape. Things get tricky however because these points do NOT automatically make up a nice sequence of triangles, you will get overlapping issues and a whole host of other problems. So this is where the triangulation comes in. At first I tried Delaunay triangulation but it was too greedy making triangles outside of the actual shape, so no good. Then I tried some ear clipping examples that I found but only 1 of the 3 I tried kind of worked and I say “kind of” because it goes into a number of infinite loops that I had to hardcode exceptions for and as such it misses a few triangles. (Also every now and again it would reject a complete path for no apparent reason). Not only that but the ear clipping algorithm is SLOW and doesn’t scale very well.
True vector graphics are great, they are something we love about the platform and will miss when the next major release of actionscript comes about. This is the reason why I though it would be great if we could emulate it on the GPU and I am sure it’s possible. It would however be 100 times easier if Adobe could extend their api to expose the result of the internal triangulation that they have already implemented in the player. That way they are still leaving it up to us to handle the rendering but we won’t have to spend an AGE trying to do work that they already have done a long time ago.
Anyway am bored of typing so I will post a small demo video (best viewed @ high resolution + full screen):
..Interactive demo coming soon.
If anyone wants to know more, discuss the topic, contribute, point me at an awesome triangulation library for as3, or anything else.. just drop me a message or reply to this post.
Related link(s) of justice:
Use edge lists to enable anti aliasing on straight edges of standard (non curve) triangles.
Use edges to also determine if curve is convex or concave.
Look into cubic curve - quadratic bezier curve conversion
In an ideal world I would like this to become a small Open Source project. One that is not geared to any specific engine or renderer just a simple tool that can be used to generate the required data from any flash display object. If anyone is interested get in touch, I will be more than happy so share the code once its a bit more optimized and would love to see this become something useful not just for the developers of a particular engine but for all flash devs