[RFC] Multitouch support, step one

[Rafi Rubin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



On 03/19/10 06:28, Henrik Rydberg wrote:
> 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 :-)

Consider a group of 'm' contacts with the highest id among them being 'n-1'.

I the receiver is aware that we are tracking, send the contacts as either 'm'
contacts with tracking ids, or as 'n' contacts with place holders sent for "not
a contact" but no tracking ids on the 'm' real contacts.

With tracking ids, we send 'm' tracking id events.  Without them, we need to
send 'n-m' events for the ghost contacts.

So if we're looking at bandwidth minimization, we can ask which is smaller 'm'
or 'n-m'.  As long as the glass is half full sending tracking ids is more
expensive than emitting ghosts.

Of course this is all predicated on the receiver knowing the sender is sending
tracked points.  Also the potential bandwidth reduction is probably
insignificant compared to waiting to send events until there's enough change to
be interesting.

>> 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.

I agree not worth changing the API, but possibly worth adding if you change the
API for other reasons.

>> 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

Sorry about the jumbled explanations, I will clarify the rest later.

Rafi
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkujhF8ACgkQwuRiAT9o609PuACgmep9iPXOZ0oi/CxuLbfNw/0v
KqQAmQEYZmRQ7U5kM18Fm/vjfkT0fjVf
=cMVz
-----END PGP SIGNATURE-----