Grab my balls

So, I have started cross-engine 3D primitives project at github. Just like as3dmod, it plugs seamlessly into your favorite engine to help you out whenever you feel limited by it. Initial commit supports Alternativa3D 8.12, Away3D 4 Alpha, Minko 1 and contains two spheric primitives: UniformSphere and Globe.

UniformSphere is a mesh built from the spiral of vertices uniformly distributed across the sphere. You have two options here: Rakhmanov formula (default, the spiral joins sphere poles) or Bauer formula (the spiral does not contain poles). This primitive was ported from my 3D metaballs code.

Globe is a mesh that minimizes texture distortions for classic plate carré projection. It does so by placing equilateral triangles along the equator and gradually compressing triangles towards each pole (where high triangle density is actually good property in terms of texture distortions). This primitive was ported from my globe component for FP9, which is now also hosted at github.

I plan to add few more primitives over time, both useful and not really, and maybe more engine proxies if there will be any interest.

Matching colors in RGB

I decided that this blog needs another post, preferably on subject with some real applications. Unlike my Mandelbrot log-map experiments or allRGB mini “game”. Because why would anyone read about those boring  useless things… And, since I am cooking real application here that tracks real colored blobs, the subject today will be color matching.

If you have been searching for this stuff before ending up here, you could notice that cool guys never do color matching in RGB, but instead go with HSV or similar hue-based color space. The idea here is, probably, that when you pull all color information into one coordinate, you can forget about other two. Unfortunately you can’t :( It’s not to say that there is some kind of a problem here, not at all. With tools like pixel bender on your belt, you just write a shader that converts to HSV and applies thresholds in one breath, and voila – you get your blobs to track. But, for some reason, this kind of blind belief in hue dogma just doesn’t sit well with me.

Solving polynomials, complex arithmetics and code inlining

Yeah, this is what I’ve been doing in my spare time these last days. Basically, I needed to find all roots of 4th power polynomial and, after quick search, I’ve found great wiki article on new Durand-Kerner method that makes Newton-Raphson look outdated: using only simple arithmetics it simultaneously finds all polynomial roots no matter how wrong your initial guess is. The only problem is that it needs complex numbers.

So, I had to implement complex numbers in some way. Obviously, since AS3 does not support operator overloading, we end up with a bunch of function calls. The problem here is that even these short formulas require quite a lot of them, and you need to keep evaluating that over and over before solution is found, which, as you might guess, is not so CPU-friendly. So I decided to inline them all. To this end, I downloaded and installed apparat by Joa Ebert. This actually went much easier than I expected, the only problem I ran into was that it does not work with current version of scala. Any way, getting your code inlined with this tool is as easy as extending special class. However, checking my resulting SWF with AS3 decompiler, I have found that apparat does not remove neither its own nor my custom classes which were inlined and so are no longer used anywhere. Since this is not something Joa would be willing to fix, I turned to GPP, a tool pre-processing macros in source rather than post-processing bytecode in SWF. As a result of these adventures, I have these two FlashDevelop projects for grabs in svn (view).

The other problem with complex numbers implementation in AS3 is readability. Endless lines of similar function calls separated by semicolons look pretty much like some old code in asm, if you ever seen one. In order to somewhat ease the pain, I decided to at least make it possible to chain function calls into formulas. This normally implies another performance penalty because you need to create new temporary variables in the process; however, it can be avoided by pooling those variables. This implementation can be found (and forked :) at wonderfl.

Well, that’s it for today, I’m off to enjoy my sunday.

Inverse homography using drawTriangles()

Flash player version 10+ native drawTriangles() method is perfect for programming homography (2D transformation that preserves lines) because of its support for UVT data. In general case, however, homography requires solving 8×8 linear equations system, so noone can be arsed to code that. Instead they implement one of two special cases - mapping rectangle to or from quadrilateral. So far, only 1st case was implemented using drawTriangles, while 2nd case was done using filters. Well, no longer so – it turned out, inverting T values in Zeh code was sufficient to make it work backwards:

One interesting thing about this code is that noone really knows exactly how it works :) I didn’t have to study all the math behind Zeh code in order to “invert” it, and Zeh… well, let me quote:

I was lucky enough to get what I wanted working after a good amount of crazy trial and error (and beer)

Improving marching squares

Right. Today is the day of improving 2×2 marching squares flavor described in wikipedia. A year ago Sakri Rosenstrom found that it is flawed:

As you can see, two checkerboard-like patterns are ambiguous, but the algorithm ignores it, causing random deadlocks as a side effect. So I tried to find some solution to this by posting the problem at wonderfl; and then I just couldn’t wait :) Well, my solution uses 2 to 4 pixels out of 2×2 window and seems to work on crazy images, so I’m happy. But if you suddenly find some better way, let me know.