Gesture recognition, the basic kind

GestureRecognition.swf, draw the symbols

How it works

This gesture recognition method is done in three steps:

• Capture user input
• Homogenize and normalize input
• Match to a predefined pattern

The first step is trivial and won’t be discussed. The second step is best described with a diagram. I chose to use an approach relying on a line segment/circle intersection algorithm. The goal is to get a path defined by equally distanced points, scaled to fit a 1×1 square. We can obtain this by iterating through the initial path, and finding intersections with a circle of radius r. This radius is very simply determined by dividing the length of the initial path by the number of points desired in the resulting path.

Note that the simplified path is most certainly going to be shorter than the initial path as a result of the process (see the diagram). In some occasions, the final path will effectively “miss” points. In this implementation we stop as soon as there is no intersection left with the next circle. We could think of lots of complicated and/or “expensive” ways to get that done more accurately. But really, as will show the next diagram, this does not affect the recognition itself.

Processing user input

Once we have a normalized path, we can find a matching pattern in the dictionary. Comparing the data sets is now simply a matter of comparing where the points are relatively to each other within this 1×1 square.

Finding a match

Since the points are ordered (there is a first point and a last point, and the order matters) we can find the average distance between the paths. We can expect the best matching pattern to have the lower average distance between its points and the normalized user generated path, as pictured on the diagram.

Note that the implementation I propose shows no optimization whatsoever. It will bluntly go through each and every pattern in the dictionary. There is also a total lack of quality control (or threshold value) regarding the “best match”. Whatever you draw, a match will be found. I personally think it is the way it should work, but well, you can disagree and add some extra checks yourself (see in the source, there are a couple hints on where to look).

I can see two very easy ways to optimize the search though. The relative position of the first points is absolutely important. Should you draw one of these symbols backwards, matching exactly the shape, well… it’s very unlikely it’ll be the best match. We can easily extrapolate that too great of a distance between the first points should discard the pattern (let’s say something like >=.5). What is also meaningful is the length of these paths, which should be “close enough”. A very first check combining a comparison in length and relative position of first points could discard a good number of irrelevant patterns. Then… we can look for the best match in whatever remains. Writing this, I suddenly feel like implementing it. Well. I certainly will if this gets used, as I hope, in a real project. Which, yes, is still up in the air.

Useful links

Github repo (includes rough gesture creation tool)
Paul Bourke’s line/sphere intersection algorithm

A Wonderwall-like thingy with Traer AS3

What this little experiment is focusing on is the deformation of the grid when interacting. The underlying grid pattern is not stretched and deformed as in the original (which I do realize is absolutely part of the awesomeness of it). This experiment solely focuses on the use of physics simulation to recreate the effect, and yes, there’s way more to it in the real thing. Anyways, here’s the quick experiment, in just shy of 370 lines of non-engine code:

WonderwallLikeRefined.swf, hover the grid

The differences with the original

As previously mentioned, the grid pattern is regular. Rollovers are basic (lines connecting the particles). There’s no text, just images.
But from a code perspective, the main difference is probably that there’s springiness in this experiment, while THA’s original piece shows none. The reason is (I’m guessing) that another integration method was used to set the constraints: Verlet integration. Traer uses a Runge-Kutta integrator which is less suitable for stiff joints, usually approximated by infinite stiffness springs. Well, no need to hide it. I kept the springiness in.

How this is done

Using two sets of particles

I believe this diagram is pretty self explanatory. Two sets of particles are in use, linked together in a one-to-one relation (in our case using a Spring). Attached to the mouse is an Attractor (with negative strength) that repulses the free particles. A face of the final and deformed grid is defined by four free particles. Now, if we were to use this as-is, we would get an awful amount of distortion within each image.

Subdividing the faces

Given these four points, some subdivision is necessary to minimize distortion showing the triangles used to draw the faces. In the bin/ directory, you will find one .swf without face subdivision: not so pretty. In the source code (WonderwallLikeRefined.as), I’m using 6 subdivisions (72 triangles) for each face.
There’s a lot of room for improvement there, the number of subdivisions required to draw a nice face depends on its dimensions and the amount of deformation applied. One possible improvement could be to check the difference in slope between the top and bottom edges: the greater the difference, the greater the number of subdivisions necessary. I am inclined to think that in THA’s piece some system is in place: their grid is huge, runs real smooth, with minimal distortion.

Where is the mouse?

Another problem arise. How do we handle rollovers? One simple way is to check if the mouse position is within a given polygon (here, a face defined by 4 free particles). Luckily, Paul Bourke’s line-to-line intersection algorithm comes in handy, as illustrated in the diagram above. If we take half a line starting from the current mouse position and passing through an arbitrary point, the mouse is inside the polygon if the number of intersections is an odd number (or just 1 or 3 in our case). Yup. It’s that simple!

Again, in this piece of code, I am performing the check for every single face every time the physics simulation advances. A variety of techniques could be used to improve this. One way to do this could be to perform this test on the polygon encompassing half the particles. If the test yields a true, divide it in half. And again, until we get a false. Or the subset is a face. Yup, even a good old divide and conquer would be a real improvement.

A disclaimer

I don’t pretend I know for sure how the original Wonderwall was built by THA. They may have taken a totally different approach and the only way to make sure would be to ask them. But I’m too shy. Or to decompile the .swf, which would be totally sacrilegious given how much I respect these guys and their work. So really, I have no clue. This is simply an exploration of how one could have done something a bit similar with the Traer physics engine for AS3. And this was only driven by my admiration for the studio’s work, and sheer curiosity (how did they do it??! this is sooo cool!!).

Useful links

Github repo for TraerAs3 (includes the Wonderwall-like effect files)
The gorgeous original Wonderwall
Paul Bourke’s line-to-line intersection algorithm
Tha, Yugo Nakamura’s studio: an absolute must-see
And of course, Yugop

ClothTriangles.swf, drag handles to move

The source code for this is part of my Traer.physics port to ActionScript3, and is available at Github. There really isn’t much to it, but if you haven’t yet used GraphicsTrianglePath or this little physics package, then it’s probably an okay-ish place to start.

Useful links

Github repo for TraerAS3
Livedocs about GraphicsTrianglePath

]]> http://blog.sqrtof5.com/?feed=rss2&p=44 11 http://blog.sqrtof5.com/?p=53 http://blog.sqrtof5.com/?p=53#comments Tue, 24 Nov 2009 16:17:04 +0000 Arnaud http://blog.sqrtof5.com/?p=53

Port to AS3 of the venerable Traer.physics Java library. Source code available at Github.

Before looking at the extremely simple math behind it, here’s the use I made of it: Randomly generated grass stands, in a billboarding fashion.

GrassPatch.swf, click and drag to rotate

Again, way better results would be obtained with GraphicsTrianglePath. Oh, yup, and the code -you will soon realize- is quite messy, this is really only a quick and dirty proof of concept. Alright. Enough disclaimers, how is this little thing done? Since we know the planes will be aligned along X, all we need to do is to find the correct y and z positions, as shown in this diagram:

How to stitch planes together in Flash

Assuming the registration point of our sprites is at their center, and that we want to align these planes vertically, then we really want to translate C1 to C0. P0 is known to us. P1 is an arbitrary position (we’ll use the sprite’s local coordinates to find C1). The orientation of the planes along one axis is known as well (in that case, along Z). The dimensions before any transformation, is also known for both sprites (segment length).
So really, all we’ve got to do is to find C0 and C1, and translate C1 to C0.

C0.y = P0.y + Math.sin(theta) *(length*.5);
C0.z = P0.z + Math.cos(theta)*(length*.5);
C1.y = P1.y + Math.sin(omega+Math.PI)*(length*.5);
C1.z = P1.z + Math.cos(omega+Math.PI)*(length*.5);

We can now translate P1 to C1. There are many ways to do this. In the provided code, y is first set to -i*length then the difference between C0 and C1 is added to this (effectively translating from an incorrect guessed position to the correct position):