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 _______________________________________________ [email protected]: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel
