| Message ID | 1421956345-1546-1-git-send-email-rydberg@bitmath.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, Jan 22, 2015 at 08:52:25PM +0100, Henrik Rydberg wrote: > int input_mt_assign_slots(struct input_dev *dev, int *slots, > - const struct input_mt_pos *pos, int num_pos) > + const struct input_mt_pos *pos, int num_pos, > + int dmax) Should dmax be unsigned and do we really need to treat 0 specially or we could use UNIT_MAX as "don't care" value? > { > struct input_mt *mt = dev->mt; > + int mu = 2 * dmax * dmax; For my education, what does "mu" stand for? Ideally, if someone could create a write-up on the contact matching that would be most awesome. Thanks.
Hi Dmitry, On 01/22/2015 09:02 PM, Dmitry Torokhov wrote: > On Thu, Jan 22, 2015 at 08:52:25PM +0100, Henrik Rydberg wrote: >> int input_mt_assign_slots(struct input_dev *dev, int *slots, >> - const struct input_mt_pos *pos, int num_pos) >> + const struct input_mt_pos *pos, int num_pos, >> + int dmax) > > Should dmax be unsigned and do we really need to treat 0 specially or we > could use UNIT_MAX as "don't care" value? We could have dmax unsigned, but it does not have to be from a branching perspective, since the square is what gets used anyways. >> { >> struct input_mt *mt = dev->mt; >> + int mu = 2 * dmax * dmax; > > For my education, what does "mu" stand for? I chose mu because of the mathematical similarity to the chemical potential in statistical mechanics, where it denotes the energy per particle. Here, it denotes the energy per contact assignment. > Ideally, if someone could create a > write-up on the contact matching that would be most awesome. Heh, I guess I will have to write something at some point, without requiring prior knowledge of Lagrange relaxation or the like. Time is a luxury these days... Henrik -- To unsubscribe from this list: send the line "unsubscribe linux-input" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Jan 22, 2015 at 09:24:01PM +0100, Henrik Rydberg wrote: > Hi Dmitry, > > On 01/22/2015 09:02 PM, Dmitry Torokhov wrote: > > On Thu, Jan 22, 2015 at 08:52:25PM +0100, Henrik Rydberg wrote: > >> int input_mt_assign_slots(struct input_dev *dev, int *slots, > >> - const struct input_mt_pos *pos, int num_pos) > >> + const struct input_mt_pos *pos, int num_pos, > >> + int dmax) > > > > Should dmax be unsigned and do we really need to treat 0 specially or we > > could use UNIT_MAX as "don't care" value? > > We could have dmax unsigned, but it does not have to be from a branching > perspective, since the square is what gets used anyways. > > >> { > >> struct input_mt *mt = dev->mt; > >> + int mu = 2 * dmax * dmax; > > > > For my education, what does "mu" stand for? > > I chose mu because of the mathematical similarity to the chemical potential in > statistical mechanics, where it denotes the energy per particle. Here, it > denotes the energy per contact assignment. can we please choose something that doesn't require the reviewer to have familarity of statistical mechanics to make sense of a variable in the multitouch tracking code? > > Ideally, if someone could create a > > write-up on the contact matching that would be most awesome. > > Heh, I guess I will have to write something at some point, without requiring > prior knowledge of Lagrange relaxation or the like. Time is a luxury these days... yes please. the current code is pretty much inpenetrable for me. for all I know it's sending a postcard to santa. judging by Benjamin's comment "can someone tell what this function actually does" comment in the doc patchset I'm not the only one. this link here seems to explain the algorithm for mere mortals http://www.troodon-software.com/algorithms/android/2010/06/20/euclidean-bipartite-matching-multi-touch-and-android/ whether that's what is implemented I don't know, I'm assuming this because Documentation/multi-touch-protocol.txt mentions this algorithm. there is no reference in the code what "adjust_dual" could mean, and right now I have several wikipedia pages open for Lagrange Relaxation, positive-definite matrix, Euclidean Bipartite Matching and it doesn't make code review any easier. I failed to find what "overcover" means and what a reduced matrix is took me about 20 minutes to find. Turns out it's not the Row Echelon Form (most google hits for "reduced matrix") but a "reduced cost matrix" (says input-mt.h) which has something to do with the travelling salesman problem. Which makes sense since EBM is a graph problem but at that point I gave up and went back to fixing a segfault which was much more rewarding than this rabbit hole. I'm not arguing against the code, it clearly does in 40 lines what would otherwise be a lot longer and I appreciate that you added the fix for the cursor jump (well, I assume so, it's not like I can decipher the algorithm :). but the approach limits the number of eyes that can review it for correctness. meanwhile, for people without a higher degree in mathematics can we at least add references so there are some starting points to understanding this code? And little things like naming variables so there's no guesswork necessary what they can mean. Thanks Cheers, Peter -- To unsubscribe from this list: send the line "unsubscribe linux-input" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Jan 22, 2015 at 2:52 PM, Henrik Rydberg <rydberg@bitmath.org> wrote: > Some devices are not fast enough to differentiate between a > fast-moving contact and a new contact. This problem cannot be fully > resolved because information is truly missing, but it is possible > to safe-guard against obvious mistakes by restricting movement with > a maximum displacement. > > The new problem formulation for dmax > 0 cannot benefit from the > speedup for positive definite matrices, but since the convergence is > faster, the result is about the same. For a handful of contacts, the > latency difference is truly negligible. > > Suggested-by: Benjamin Tissoires <benjamin.tissoires@redhat.com> > Not-yet-signed-off-by: Henrik Rydberg <rydberg@bitmath.org> > --- > Hi Dmitry, Benjamin, > > This patch incorporates the notion of a speed limit in the slot > assignment function, without changing the behavior for existing code. > > There are multi-touch movement cases where the difference between this > algorithm and a simple deassign-overspeeding-contacts algorithm which > warrants this approach. One example is when a whole array of contacts > are moved one step to the right in one frame. With the simple > algorithm, all contacts will be deassigned, whereas with this > algorithm, the leftmost contact is deassigned and a new contact > created on the right. This is the interpretation of smallest change, > and is consistent with the behavior one would get from two contacts, > for both algorithms. > > I have tested this on a number of testcases in my tree, and I am > running the patch with a speed limit on my device as I write this. If > this patch solves Benjamin's problem, I think we are ok. > Tested this morning, and yes, it solves the problem. I assumed that the dmax was in mm, and used "10 * priv->x_res", which seemed to do the trick: - tapping with two fingers side by side triggered the jumps - in the general case (switching from the index to the thumb to click), the jumps disappeared. Maybe we should also add a doc telling which units the dmax should be. When you'll sign this, you can add my tested-by. Cheers, Benjamin -- To unsubscribe from this list: send the line "unsubscribe linux-input" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/drivers/input/input-mt.c b/drivers/input/input-mt.c index fbe29fc..990509e 100644 --- a/drivers/input/input-mt.c +++ b/drivers/input/input-mt.c @@ -293,7 +293,7 @@ void input_mt_sync_frame(struct input_dev *dev) } EXPORT_SYMBOL(input_mt_sync_frame); -static int adjust_dual(int *begin, int step, int *end, int eq) +static int adjust_dual(int *begin, int step, int *end, int eq, int mu) { int f, *p, s, c; @@ -311,9 +311,10 @@ static int adjust_dual(int *begin, int step, int *end, int eq) s = *p; c = (f + s + 1) / 2; - if (c == 0 || (c > 0 && !eq)) + if (c == 0 || (c > mu && (!eq || mu > 0))) return 0; - if (s < 0) + /* Improve convergence for positive matrices by penalizing overcovers */ + if (s < 0 && mu <= 0) c *= 2; for (p = begin; p != end; p += step) @@ -322,23 +323,24 @@ static int adjust_dual(int *begin, int step, int *end, int eq) return (c < s && s <= 0) || (f >= 0 && f < c); } -static void find_reduced_matrix(int *w, int nr, int nc, int nrc) +static void find_reduced_matrix(int *w, int nr, int nc, int nrc, int mu) { int i, k, sum; for (k = 0; k < nrc; k++) { for (i = 0; i < nr; i++) - adjust_dual(w + i, nr, w + i + nrc, nr <= nc); + adjust_dual(w + i, nr, w + i + nrc, nr <= nc, mu); sum = 0; for (i = 0; i < nrc; i += nr) - sum += adjust_dual(w + i, 1, w + i + nr, nc <= nr); + sum += adjust_dual(w + i, 1, w + i + nr, nc <= nr, mu); if (!sum) break; } } static int input_mt_set_matrix(struct input_mt *mt, - const struct input_mt_pos *pos, int num_pos) + const struct input_mt_pos *pos, int num_pos, + int mu) { const struct input_mt_pos *p; struct input_mt_slot *s; @@ -352,7 +354,7 @@ static int input_mt_set_matrix(struct input_mt *mt, y = input_mt_get_value(s, ABS_MT_POSITION_Y); for (p = pos; p != pos + num_pos; p++) { int dx = x - p->x, dy = y - p->y; - *w++ = dx * dx + dy * dy; + *w++ = dx * dx + dy * dy - mu; } } @@ -393,17 +395,24 @@ static void input_mt_set_slots(struct input_mt *mt, * @slots: the slot assignment to be filled * @pos: the position array to match * @num_pos: number of positions + * @dmax: maximum sensor displacement (zero for infinite) * * Performs a best match against the current contacts and returns * the slot assignment list. New contacts are assigned to unused * slots. * + * The assignments are balanced so that all displacements are below + * dmax. If no such assignment can be found, some contacts are + * assigned to unused slots. + * * Returns zero on success, or negative error in case of failure. */ int input_mt_assign_slots(struct input_dev *dev, int *slots, - const struct input_mt_pos *pos, int num_pos) + const struct input_mt_pos *pos, int num_pos, + int dmax) { struct input_mt *mt = dev->mt; + int mu = 2 * dmax * dmax; int nrc; if (!mt || !mt->red) @@ -413,8 +422,8 @@ int input_mt_assign_slots(struct input_dev *dev, int *slots, if (num_pos < 1) return 0; - nrc = input_mt_set_matrix(mt, pos, num_pos); - find_reduced_matrix(mt->red, num_pos, nrc / num_pos, nrc); + nrc = input_mt_set_matrix(mt, pos, num_pos, mu); + find_reduced_matrix(mt->red, num_pos, nrc / num_pos, nrc, mu); input_mt_set_slots(mt, slots, num_pos); return 0; diff --git a/drivers/input/mouse/alps.c b/drivers/input/mouse/alps.c index 54ff0379..6c64fb2 100644 --- a/drivers/input/mouse/alps.c +++ b/drivers/input/mouse/alps.c @@ -435,7 +435,7 @@ static void alps_report_mt_data(struct psmouse *psmouse, int n) struct alps_fields *f = &priv->f; int i, slot[MAX_TOUCHES]; - input_mt_assign_slots(dev, slot, f->mt, n); + input_mt_assign_slots(dev, slot, f->mt, n, 0); for (i = 0; i < n; i++) alps_set_slot(dev, slot[i], f->mt[i].x, f->mt[i].y); diff --git a/drivers/input/mouse/bcm5974.c b/drivers/input/mouse/bcm5974.c index c329cdb..b10709f 100644 --- a/drivers/input/mouse/bcm5974.c +++ b/drivers/input/mouse/bcm5974.c @@ -564,7 +564,7 @@ static int report_tp_state(struct bcm5974 *dev, int size) dev->index[n++] = &f[i]; } - input_mt_assign_slots(input, dev->slots, dev->pos, n); + input_mt_assign_slots(input, dev->slots, dev->pos, n, 0); for (i = 0; i < n; i++) report_finger_data(input, dev->slots[i], diff --git a/drivers/input/mouse/cypress_ps2.c b/drivers/input/mouse/cypress_ps2.c index 8af34ff..9118a18 100644 --- a/drivers/input/mouse/cypress_ps2.c +++ b/drivers/input/mouse/cypress_ps2.c @@ -538,7 +538,7 @@ static void cypress_process_packet(struct psmouse *psmouse, bool zero_pkt) pos[i].y = contact->y; } - input_mt_assign_slots(input, slots, pos, n); + input_mt_assign_slots(input, slots, pos, n, 0); for (i = 0; i < n; i++) { contact = &report_data.contacts[i]; diff --git a/drivers/input/mouse/synaptics.c b/drivers/input/mouse/synaptics.c index f947292..84d0401 100644 --- a/drivers/input/mouse/synaptics.c +++ b/drivers/input/mouse/synaptics.c @@ -1204,7 +1204,7 @@ static void synaptics_profile_sensor_process(struct psmouse *psmouse, pos[i].y = synaptics_invert_y(hw[i]->y); } - input_mt_assign_slots(dev, slot, pos, nsemi); + input_mt_assign_slots(dev, slot, pos, nsemi, 0); for (i = 0; i < nsemi; i++) { input_mt_slot(dev, slot[i]); diff --git a/drivers/input/touchscreen/pixcir_i2c_ts.c b/drivers/input/touchscreen/pixcir_i2c_ts.c index fc49c75..ccdf654 100644 --- a/drivers/input/touchscreen/pixcir_i2c_ts.c +++ b/drivers/input/touchscreen/pixcir_i2c_ts.c @@ -126,7 +126,7 @@ static void pixcir_ts_report(struct pixcir_i2c_ts_data *ts, pos[i].y = touch->y; } - input_mt_assign_slots(ts->input, slots, pos, n); + input_mt_assign_slots(ts->input, slots, pos, n, 0); } for (i = 0; i < n; i++) { diff --git a/include/linux/input/mt.h b/include/linux/input/mt.h index f583ff6..d7188de 100644 --- a/include/linux/input/mt.h +++ b/include/linux/input/mt.h @@ -119,7 +119,8 @@ struct input_mt_pos { }; int input_mt_assign_slots(struct input_dev *dev, int *slots, - const struct input_mt_pos *pos, int num_pos); + const struct input_mt_pos *pos, int num_pos, + int dmax); int input_mt_get_slot_by_key(struct input_dev *dev, int key);