Document the gesture frame logic

Add some notes on the math of the gesture frame computations.

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>

2 files changed, 204 insertions, 0 deletions

diff --git a/docs/gestures.txt b/docs/gestures.txt
new file mode 100644
index 0000000..5a1eb45
--- /dev/null
+++ b/docs/gestures.txt
@@ -0,0 +1,58 @@
+Introduction
+------------
+
+This document describes how the gestures are extracted from multi-finger
+actions. The process is divided into gestural transformations, gesture
+recognition, and gesture instantiation.
+
+Gestural Transformations
+------------------------
+
+All two-finger transformations are extracted. These are all exact, in the
+sense that continuously transforming the original finger positions, frame
+per frame, will exactly follow the actual finger positions.
+
+In addition to two-finger transformations, a global gesture is also
+extracted. The rotation and scaling is taken from the contact pair with the
+longest distance between contacts. This approximates the behavior of a
+region, such that complex transformations could, in principle, be happening
+inside the region, but at a distance, the transformation will look like it
+was performed with two fingers.
+
+At each time step, a gestural transformation is goverened by rotation,
+scaling and translation. The point around which rotation and scaling is
+performed is called the pivot. To form as natural gestures as possible,
+this point always lies within the area formed by the contacts themselves.
+It is placed at the point which, after rotation and scaling, leaves the
+transformed contacts as close to the actual positions as possible.  The
+translation, or drag, is always a fraction of the movement of the center
+point. The fraction is called moveness, and is related to the distance
+between the pivot and the center point. When the pivot is at the center
+point, the moveness is one and the drag is the same as the center movement.
+When the pivot is at one of the contacts, as in rotation around a finger,
+the moveness is zero, and consequently the drag is zero.  The relations
+between the pivot, the moveness and the drag are detailed in the document
+pivot.txt.
+
+Gesture Recognition
+-------------------
+
+Each gestural transformation can give rise to one or several gesture
+primitives. Based on the rotation, scaling, moveness and drag values, the
+gesture primitives drag, pinch and rotate are recognized. The onset of a
+gesture primitive is governed by a threshold and a timeout. Basically, if
+performed distinctly enough, the gesture will be triggered, and will remain
+active until a finger is lifted or added.
+
+Gesture Instantiation
+---------------------
+
+Given a set of detected gesture primitives, only some will trigger actual
+gesture events. First, the set of available primitives are matched against
+available listeners. Primitives not listened for are dropped. The remaining
+set is arranged according to priority. A pointer gesture has lower priority
+than a two-finger gesture, which has lower priority than a tap, for
+instance. As long as the gesture primitives of higher priority are expected
+but not activated, all gestures are held back. Once one of the highest
+priority primitives are activated, all primitives of lower priority are
+cancelled, and events are emitted.
diff --git a/docs/pivot.txt b/docs/pivot.txt
new file mode 100644
index 0000000..b945dd6
--- /dev/null
+++ b/docs/pivot.txt
@@ -0,0 +1,146 @@
+The pivot, p, is defined as the point, within the convex hull of the
+contacts, which, after rotation and scaling, leaves the transformed
+contacts as close to the actual positions as possible.
+
+Let r_i be the starting points and s_i the actual ending points in a
+transformation. Let D be the scaling, and R the rotation. Then, minimizing
+
+L(p) = sum_i |D R (r_i - p) + p - s_i|^2 / N
+
+yields the pivot. Let
+
+rm = sum_i r_i / N,
+p = rm + u,
+q_i = s_i - rm - D R (r_i - rm),
+
+and we get
+
+L(p) = sum_i |(1 - D R) u - q_i|^2 / N.
+
+With
+
+L0 = sum_i norm2(q_i) / N,
+T = (1 - D R)' (1 - D R),
+m = sum_i q_i / N,
+
+we can write this as
+
+L(p) = L0 + u' T u - 2 m' (1 - D R) u.
+
+To handle the constraint, we can approximate the hull with a circle
+centered at rm. If we pick the average radius, P, the constraint becomes
+
+|u| < P.
+
+Relaxing [1] the expression (h >= 0) yields
+
+L(p, h) = L0 + u' T u - 2 m' (1 - D R) u + h (|u|^2 - P^2),
+
+leading to the linear equation
+
+(T + h) u = (1 - D R)' m.
+
+Further,
+
+sm = sum_i s_i / N,
+m = sum_i (s_i - rm - D R (r_i - rm)) / N = sm - rm,
+
+thus m is the average displacement. In words, the pivot is the average
+position plus a correction depending on the average displacement.
+
+*
+
+Some algebra solves the equation,
+
+D' = D,
+[D, R] = 0,
+R = S + C,
+S' = -S,
+C' = C,
+R + R' = 2 C,
+T = (1 - D R)' (1 - D R) = 1 + D^2 - 2 D C,
+
+which is a simple diagonal scaling operator. With
+
+a = 1 - D C,
+b = D S,
+
+we can write this as
+
+T = (1 - DC)^2 + D^2(1 - C^2) = (1 - DC)^2 + D^2 S^2 = a^2 + b^2.
+
+Similarly, we can write
+
+(1 - D R)' = ((a, b), (-b, a)),
+
+and thusly,
+
+u = Q(h) m,
+
+with
+
+Q(h) = ((a, b), (-b, a)) / (a^2 + b^2 + h).
+
+When D R = 1, it follows that a^2 + b^2 = 0, and the relaxation ensures
+that u is finite.
+
+*
+
+The drag is found by minimizing
+
+E(d) = sum_i | D R (r_i - p) + p + d - s_i |^2 / N,
+E(d) = d^2 + 2 d' ((1 - D R) u - m) + E0,
+
+which leads to the linear equation
+
+d = m - (1 - D R) u.
+
+Explicitly,
+
+d = m - (a ux - b uy, a uy + b ux).
+
+Inserting the expression for u yields, after some algebra,
+
+d = m (1 - (a^2 + b^2) / (a^2 + b^2 + h)).
+
+When h = 0, d = 0, as expected.
+
+When a^2 + b^2 = 0, d = m, also as expected.
+
+For constrained cases, the drag is a fraction of the average displacement.
+
+*
+
+Time to look at measures for the relaxation parameter. Since d depends on
+h, we can write the correction u(h) in terms of d instead. After som
+algebra,
+
+|u(h)| = (|m| - |d|) / sqrt(a^2 + b^2).
+
+Conversely, d(h) can be written in terms of the constrained u(h) as
+
+d(h) = m (1 - sqrt(a^2 + b^2) |u(h)| / |m|).
+
+Since |u(0)| = |m| / sqrt(a^2 + b^2), we obtain
+
+d(h) = m (1 - |u(h)| / |u(0)|).
+
+*
+
+We can now write down an explicit recipe for determining the pivot (p) and
+drag (d), given the transformation parameters a and b.
+
+w = (a mx + b my, a my - b mx).
+
+If |w| = 0, then u = 0. Consequently p = rm, d = m, and we are done. Else,
+
+u = w |m|^2 / |w|^2,
+
+t = P / |u|.
+
+If t >= 1, then p = rm + u, d = 0, and we are done. Else,
+
+p = rm + t u,
+d = (1 - t) m.
+
+[1] See Lagrange relaxation