Update: feathering and nodes

Just a little update to let you all know this project has not been abandoned yet :).

I have made some improvements to the feathering code to prevent it from overlapping itself so easily. Even though it now works better than before, it still isn't as robust as having a second bézier shape (like in Nuke). So, I've decided to add a bézier feathering mode to give the user the option of using it when the current method fails.

I have also started working on a dedicated Roto2D compositing node. At the moment Roto2D uses a standard Image node which is less than ideal. The new node will fix the current rendering and undo issues. The next release will probably be a intermediate one with parts of the script moved to the node but not all of it yet. I'm still working on the best way to allow the node and the image editor to interact and right now python gives me a faster turn around.

0.48a release (alpha)

The first public release! A 64-bit x86 linux build and a 32-bit windows build are available as well as the source code. All archives include the user guide and the script.

Warning: 0.48a is an alpha version, this means that it is for testing purposes only!

Installation:
unpack & run blender
Load the startup.blend from the archive to get a Nuke-like interface.

Available downloads (the archives include a copy of Blender 2.59):
Linux x86 64-bit binary (15MB)
Windows 32-bit binary (25MB)
Source (22MB)

Additional downloads:
User guide
Python script

Introduction video:

Let me know if and how it works for you!

Almost there...

I'm currently finishing things up for the first public release. There is still an annoying issue with loading a new or existing .blend while Roto2D is active but as long as you activate Roto2D after loading the .blend it is, dare I say it, useable!
Here's a list of changes since the last post:

• MUCH faster image updates. I've added a couple of functions to Blender that gives me a more direct route to the pixel data. This allows for 15-20x (guesstimated) faster updates. It can now play back filled in animated masks at an acceptable speed.
• Feathering!!! I finally managed to get it to work. There are some issues with large feather distances and sharp corners but since it is intended to be used to match the soft-edge of an in focus image element it is already useable. For bigger blurs you can attach a blur node to the mask's image node.
• The feather distance can be adjusted per point. The feather distance for every curve point between two points is calculated using the logistic function mentioned here. This gives it a nice sigmoid slope.
• Every mask now has a corresponding node in the Node editor. These nodes are fully managed (created/removed/updated) by Roto2D. The nodes can be forced to update by enabling 'Update nodes' in the panel.
• The masks now match the render settings instead of the image size. A dotted line shows the size of the mask in the editor.
• Inverting a mask. Just as fast as a non-inverted mask thanks to the new pixel functions mentioned above.
• Changing the Bézier resolution per mask. range: 10-80
• Translate, rotate & scale a mask or the selected points. Uses the standard Blender 'g', 'r' & 's' keys.

Example of an Inverted, feathered mask showing the variable feather distance. Inset: corresponding alpha mask generated by Roto2D

Most of the desired functionality is there. Now it's a matter of fixing a couple (Fingers crossed, knock on wood, etc.) of bugs and releasing it.

Animation and more

I was planning on adding the soft edge feature but even the most stripped down blur implementation was simply too slow. So, I shifted my focus towards animation and useability for a while. Here's a quick overview of the changes:

• Making changes to a mask now automatically adds/updates a keyframe for the current frame. This means that as you jump back and forth through the footage and make adjustments to the mask(s), you don't have to worry about adding keyframes, etc. Roto2D takes care of all that. Of course, you can also edit the animation using the Graph Editor or Dopesheet.
• All masks are now correctly stored in the .blend file. So, you don't have to worry about saving them seperately. 
• Added selecting a mask by clicking on the outline.
• Adding a point to a mask by double-clicking on the outline.
• Added removing all selected points by pressing 'x' or 'del' or using the 'Remove' button. When drawing a new mask this will remove the last added point (pressing it again removes the point before that, etc.).
• Added smoothing all selected points by pressing 'Shift'+'s' or using the 'Smooth' button.
• Mask names can now be changed.
• Mask color and alpha can now be changed.
• Visibility of the outlines can now be toggled.
• The use of 'Ctrl' and 'Shift' when editing points now matches the Foundry's Nuke. 
• Tested it in Windows for the first time and fixed some strange OpenGL issues. 

And a new screenshot:

Animated mask.

With all that taken care of, it's time to dive back into the pixel buffers. Updating the Image object is still a bit too slow (about 1 sec. for 1920x1080) so I need to find a more direct way to pass the bgl.Buffer data to the Image object's buffer. If only I could get Image.gl_load() to stop causing a segmentation fault, or get direct access to the buffer... I feel another patch coming up! (And this one will be seriously serious :)

Finally a fully functioning rasterizer

In my previous post I expressed my fondness for triangles. Well, the triangles are no more. For every problem I solved, two more appeared. So, I threw out some 350 lines of code, including all the triangulation stuff, and replaced it with a good old scan line bucket rasterizer. It is a modified version of the one described here. This one is so simple that it actually works with any kind of mask I throw at it!
Here is a little example of the rasterizer in action:

The new rasterizer showing 3 masks (including a self-intersecting one)

For every mask a bgl.Buffer is filled, converted into an OpenGL texture, mapped to a 2d quad and displayed on top of the image in the UV/Image editor. It still needs some optimization and the anti-aliasing needs some more work but it is already fast enough for panning, zooming, etc. because OpenGL handles most of the heavy lifting.

I will try to make a video this weekend and post it here.
Next up: gaussian blur madness!

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.