[RFC] Multitouch support, step one

[Henrik Rydberg]

Rafi Rubin wrote:
[...]
> Just to stir things up a little more, I'd argue that tracking can be seen as
> just one of several spatial reporting strategies.  As Henrik pointed out, it
> mostly just serves to reduce the computational burden of the tracking code.
> There are several other reporting methods that if known could also be used to
> improve the efficiency of the tracking code.

True. The tracking problem is a Euclidian Bipartite Matching problem, which is
much easier than the full Bipartite Matching problem. The complexity of the
latter is O(n^3), whereas there are known approximations to the former with O(n
log(n)) complexity. The matching code implemented in the multitouch X driver is
a bitmapped hungarian algorithm. It has complexity O(n^3), but the low number of
fingers matched and the efficient implementation makes it reasonable fast.

In short: yes, the matching code can definitely be made (even) faster, it is
just a matter of someone dropping a patch with a faster implementation.

> For example my screen reports contacts from bottom to top.  So we know that to
> track a contact we don't have to do a full N^2 Euclidean distance computation to
> determine if two contacts have swapped order in the list.

For the reason above, I do not think there is any reason to impose additional
assumptions on the contacts from an efficiency stand point.


> If we can identify a set of strategies or scan patterns, it might make more
> sense to just report the contacts in the order they come in and let the tracker
> use that knowledge.  In that scheme dense reporting of tracked contacts with
> tracking id makes sense if the common case is a sparsity of over 50%.  We emit
> no more events if we report holes with a single event instead of id on active
> contacts.  The magic mouse example (crazy or not), clearly demonstrates a device
> where the common case is considerably more than 50% sparsity and therefore
> justifies including the hardware tracking ids (what use is it to remember which
> finger was in that spot, 15 minutes after you walk away from the computer).

I believe I could use a rephrasing of this paragraph in order to understand it :-)


> Of course this doesn't make as much sense if we follow Henrik's argument about
> suppressing motion until the current values have changed enough.  But there
> again, do we emit just the one contact or the whole group?  If the whole group,
> then my argument stands.  As for reporting only subsets of the contacts as
> needed, we would either have to move tracking to the kernel, or be pretty
> careful about the conditions for "enough".

The reporting is always for the whole group, since the contacts are
interdependent. I do not see what argument stands because of this, nor the
rationale behind it. Could you clarify, please?


> Also from a pure efficiency argument, it would seem to make most sense to reduce
> bandwidth as early as possible, which also suggests moving tracking to the
> kernel.  Though I definitely do not think each driver should be responsible for
> the code, more of putting the contact manager in the kernel, if efficiency is
> the priority.

Hm. There really are some arguments for putting this in the kernel. I will bring
it up.


> In another dependent argument, any approach that holds while motion is bellow a
> threshold needs some way to keep the unmoving contact alive to the higher
> levels.  The solution is likely dependent on the approach.  If all contacts are
> reported whenever a change occurs, a simple "all contacts gone" event should
> suffice.  In the case where all contacts are constantly reporting, we can
> continue to get away without anything, but it still might be nice to have that
> "all contacts gone" event.  In the more sparse protocols, heart beats would
> work, but so would a "contact changed" event.  Much of that would simply be
> covered by the addition of a "contact count" event (though clearly in some cases
> that value needs double checking from what the hardware reports).

I have thought about adding the contact count to the MT event stream for said
reasons, but I really, really, do not want to change the API unless it is
extremely necessary.


> One final thought about the emit only after enough has changed.  If we consider
> three values: last emitted by the kernel, previous hardware position, and
> current hardware position, we can use the previous and current to determine if a
> contact is consistent.  With that, the kernel can save the tracker some work
> even on the sloppiest hardware.  We just have to keep a map of currently used
> id's and assign one that has been cleared if the kernel has any doubts.

I had a bit of trouble following this one.

Cheers,
Henrik