Cubic v. Quadratic

After the past couple of days I can now honestly say that the triangle is by far my favorite geometric shape. Once I got my head around drawing a quadratic curve by mapping the barycentric (texture) coordinates to cartesian (image) coordinates, using Blender's mathutils.geometry.barycentric_transform(), i saw the beauty that is the triangle.
Unfortunately, by adding just one more point to the equation it all gets a lot more complicated. First and second derivatives, Inflection points, etc. (check out the stuff here and here to get the idea). So, I figured, I already have the function to fill in a quadratic curve and I know you can approximate a cubic curve by using 4 (or more for better results) quadratic curves; why not draw them that way? It's a masking tool so it doesn't matter if the cubics aren't exactly cubic. I gave it a go and in most cases it produced acceptable results, with the notable exception of the loop:

The problem with approximating a cubic with quadratics...

It's pretty obvious that the yellow bits should be drawn inside out. However, figuring out what the yellow bits are is a bit tricky. I could subdivide the curves at the intersection. But that would require determining or calculating the intersection in the first place. I'm wondering if it wouldn't be better to take the cubic road after all...

Generating the raster image

What I'm working on at the moment is turning the vector mask into an image that can be used in the node editor. I have tried a couple of different simple techniques, like a scan line fill, but none of them really worked. Then I found this great article: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html. Based on this article I have decided to divide it into a series of steps:

1. Triangulate the polygon consisting of only the points (no handles).
2. Fill these triangles with a simple scan line fill.
3. Form a triangle (two points with one handle between them) or a quad (two points with two handles between them) for every connected pair of points.
1. If it's a quad divide it into two triangles.
4. For every triangle:
1. Determine if it contains a concave or a convex curve.
2. If it's convex then set all pixels that lie within the curve to 1.
3. If it's concave then set all pixels that lie within the curve to 0.

For the triangulation I found a great example here: http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml. It was pretty easy to translate the code to Python and, lo and behold, it worked right away! That's something I'm not used to :)
The scan line fill is a simplified version of the technique described here: http://www.cs.fit.edu/~wds/classes/graphics/Rasterize/rasterize/rasterize.html. Because it only has to fill triangles it doesn't have to check and sort multiple scan line intersections. It simply uses Bresenham's line algorithm to determine x for the left and the right edge for every line y. These are stored in a list and used afterwards  to fill the pixels.
Figuring out if a curve is concave or convex is simple since the triangulation function already requires all points to be sorted counter-clockwise. That means that if the handle point lies to the left of the line between the two points the curve is concave, else it's convex.

So, steps 1,2,3 & 4.1 are covered and implemented but steps 4.2 & 4.3 are the tricky ones. To be continued...

Progress so far

Here's a screenshot of a newly created mask in the UV/Image Editor:

Roto2D in action

It shows the panel on the left which features a list of masks. The mask itself shows the different types of points that are available: a simple point, a point with one handle or a point with two handles. A point with two handles can have an angle between the handles or the handles can be symmetrical.

All the points and handles can be moved around individually or, using the shift key or a rectangle selection to select multiple points, as a group. With the shift key you can also change the angle between handles or pull a new handle from a simple point or a point with one handle.

So, the mask editor is pretty much functional. The next step is to generate the raster image mask.

What to expect

The finished add-on will have the following features:

• Integration into the UV/Image Editor
• Ability to create and edit 2D Bézier masks in the UV/Image Editor
• Key frame animation 
• Soft edges 
• Generated masks available in the Node Editor
• Updated dynamically on a frame change

Basically, it will allow you to open a movie or image sequence in the UV/Image Editor, create one or more vector masks, animate them and use them for your composite.

What's going on here?

Blender, the open source 3D graphics software, has a lot of cool and useful features for a vfx guy like me. Especially with the new 2.5 release. 3D modeling, rendering, fluid sim., smoke sim. (very cool) and even node-based compositing. From a vfx perspective, however, there is one important tool missing: rotoscoping. So, I have taken it upon myself to write an add-on that will add this missing functionality. After much deliberation I have decided to call it Roto2D and this blog will chronicle its development.