[PATCH] input: Introduce light-weight contact tracking

[PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

Some kernel drivers demand the use of contact tracking for proper
filtering and pointer emulation. With one exception, these drivers
are limited to a maximum of four concurrent contacts. This patch adds
a simple matcher for up to four contacts, with these notable properties:

* Fixed-time computation scheme
* Approximately 1.4 times faster than mtdev at 4 fingers [1]
* Approximately 4.0 times faster than mtdev at 2 fingers [1]

The matcher uses a fixed-size, auto-generated table [2], and is
guaranteed to complete within a couple of hundred cycles. This makes
is suitable as an opt-in also for drivers running in interrupt
context.

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

[1] running the mtdev-matching benchmark on a regular 64-bit machine
[2] http://bitmath.org/code/mtdev/
---
Hi Dmitry,

It has been a long time coming, and here is my proposition for
in-kernel multitouch contact tracking. The idea is to use this small,
limited matcher together with the upcoming synaptics and ntrig changes
to make those drivers fully operational. The matcher also bridges a
major gap in the transition to the MT slots protocol; with up to four
contacts tracked in-kernel, we can treat all hid drivers and
two-finger devices the same way. Only bcm5974 then remains, and there
is some hope that it can be made to work with slots as well.

The matcher is about a hundred lines of code and a kilobyte of static
data. I put it in a separate file, in case it would be better
configured as a module.

I imagine you would prefer to get this kind of patch together with
some actual change, but I wanted to check what you think of it
first. One additional patch with pointer emulation support is planned,
but that one seems better bundled with the MT support in input.c.

The synaptics patches are currently cooking at Bagwell's, and we
already discussed the API a bit. Something ntrig-ish is cooking at
Rubin's, and there is also the ntrig driver in Ubuntu 10.10 to
consider. All-in-all, it is my hope that posting this patch will
simplify the synchronization of our efforts.

Cheers,
Henrik

 drivers/input/Makefile    |    2 +-
 drivers/input/input-trk.c |  194 +++++++++++++++++++++++++++++++++++++++++++++
 include/linux/input-trk.h |   30 +++++++
 3 files changed, 225 insertions(+), 1 deletions(-)
 create mode 100644 drivers/input/input-trk.c
 create mode 100644 include/linux/input-trk.h

diff --git a/drivers/input/Makefile b/drivers/input/Makefile
index 7ad212d..eaa663c 100644
--- a/drivers/input/Makefile
+++ b/drivers/input/Makefile
@@ -5,7 +5,7 @@
 # Each configuration option enables a list of files.
 
 obj-$(CONFIG_INPUT)		+= input-core.o
-input-core-objs := input.o input-compat.o ff-core.o
+input-core-objs := input.o input-compat.o ff-core.o input-trk.o
 
 obj-$(CONFIG_INPUT_FF_MEMLESS)	+= ff-memless.o
 obj-$(CONFIG_INPUT_POLLDEV)	+= input-polldev.o
diff --git a/drivers/input/input-trk.c b/drivers/input/input-trk.c
new file mode 100644
index 0000000..ca08cd2
--- /dev/null
+++ b/drivers/input/input-trk.c
@@ -0,0 +1,193 @@
+/*
+ * Input Multitouch Tracking Library
+ *
+ * Copyright (c) 2010 Henrik Rydberg
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ */
+
+#include <linux/input-trk.h>
+
+/* generated by mtdev-kernel - do not edit */
+static const u8 match_data[] = {
+	0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 0, 0, 0, 1, 1,
+	1, 0, 0, 0, 1, 2, 1, 1, 0, 2, 2, 1, 2, 0, 0, 0,
+	1, 2, 3, 1, 1, 0, 2, 3, 2, 1, 2, 0, 3, 3, 1, 2,
+	3, 0, 0, 0, 1, 1, 1, 2, 1, 0, 0, 3, 0, 1, 1, 3,
+	1, 0, 2, 2, 3, 1, 2, 0, 0, 4, 0, 1, 2, 2, 4, 2,
+	1, 0, 0, 5, 0, 2, 1, 1, 5, 2, 0, 1, 1, 4, 1, 0,
+	2, 3, 2, 4, 1, 2, 0, 3, 3, 4, 1, 2, 3, 0, 0, 5,
+	0, 1, 2, 3, 2, 5, 2, 1, 0, 3, 3, 5, 2, 1, 3, 0,
+	0, 6, 0, 2, 1, 3, 1, 6, 2, 0, 1, 3, 3, 6, 2, 3,
+	1, 0, 0, 7, 0, 2, 3, 1, 1, 7, 2, 0, 3, 1, 2, 7,
+	2, 3, 0, 1, 0, 0, 1, 1, 2, 2, 1, 2, 1, 0, 0, 3,
+	0, 1, 1, 4, 2, 0, 3, 4, 2, 1, 0, 5, 0, 2, 2, 5,
+	1, 2, 2, 4, 6, 2, 1, 0, 1, 5, 6, 2, 0, 1, 2, 3,
+	7, 1, 2, 0, 0, 5, 7, 0, 2, 1, 1, 3, 8, 1, 0, 2,
+	0, 4, 8, 0, 1, 2, 2, 5, 8, 2, 1, 0, 3, 3, 5, 8,
+	2, 1, 3, 0, 1, 6, 8, 2, 0, 1, 3, 3, 6, 8, 2, 3,
+	1, 0, 1, 7, 8, 2, 0, 3, 1, 2, 7, 8, 2, 3, 0, 1,
+	2, 4, 9, 1, 2, 0, 3, 3, 4, 9, 1, 2, 3, 0, 0, 6,
+	9, 0, 2, 1, 3, 3, 6, 9, 3, 2, 1, 0, 0, 7, 9, 0,
+	2, 3, 1, 2, 7, 9, 3, 2, 0, 1, 1, 4, 10, 1, 0, 2,
+	3, 3, 4, 10, 1, 3, 2, 0, 0, 5, 10, 0, 1, 2, 3, 3,
+	5, 10, 3, 1, 2, 0, 0, 7, 10, 0, 3, 2, 1, 1, 7, 10,
+	3, 0, 2, 1, 1, 4, 11, 1, 0, 3, 2, 2, 4, 11, 1, 3,
+	0, 2, 0, 5, 11, 0, 1, 3, 2, 2, 5, 11, 3, 1, 0, 2,
+	0, 6, 11, 0, 3, 1, 2, 1, 6, 11, 3, 0, 1, 2, 0, 0,
+	1, 1, 2, 2, 3, 3, 1, 2, 1, 0, 0, 3, 0, 1, 1, 4,
+	2, 0, 3, 4, 2, 1, 0, 5, 0, 2, 2, 5, 1, 2, 1, 6,
+	3, 0, 3, 6, 3, 1, 5, 6, 3, 2, 0, 7, 0, 3, 2, 7,
+	1, 3, 4, 7, 2, 3, 2, 4, 6, 2, 1, 0, 1, 5, 6, 2,
+	0, 1, 2, 3, 7, 1, 2, 0, 0, 5, 7, 0, 2, 1, 1, 3,
+	8, 1, 0, 2, 0, 4, 8, 0, 1, 2, 2, 4, 9, 3, 1, 0,
+	1, 5, 9, 3, 0, 1, 2, 7, 9, 3, 2, 0, 5, 7, 9, 3,
+	2, 1, 1, 8, 9, 3, 0, 2, 4, 8, 9, 3, 1, 2, 2, 3,
+	10, 1, 3, 0, 0, 5, 10, 0, 3, 1, 2, 6, 10, 2, 3, 0,
+	5, 6, 10, 2, 3, 1, 0, 8, 10, 0, 3, 2, 3, 8, 10, 1,
+	3, 2, 1, 3, 11, 1, 0, 3, 0, 4, 11, 0, 1, 3, 1, 6,
+	11, 2, 0, 3, 4, 6, 11, 2, 1, 3, 0, 7, 11, 0, 2, 3,
+	3, 7, 11, 1, 2, 3, 3, 6, 9, 12, 3, 2, 1, 0, 2, 7,
+	9, 12, 3, 2, 0, 1, 3, 5, 10, 12, 3, 1, 2, 0, 1, 7,
+	10, 12, 3, 0, 2, 1, 2, 5, 11, 12, 3, 1, 0, 2, 1, 6,
+	11, 12, 3, 0, 1, 2, 3, 6, 8, 13, 2, 3, 1, 0, 2, 7,
+	8, 13, 2, 3, 0, 1, 3, 4, 10, 13, 1, 3, 2, 0, 0, 7,
+	10, 13, 0, 3, 2, 1, 2, 4, 11, 13, 1, 3, 0, 2, 0, 6,
+	11, 13, 0, 3, 1, 2, 3, 5, 8, 14, 2, 1, 3, 0, 1, 7,
+	8, 14, 2, 0, 3, 1, 3, 4, 9, 14, 1, 2, 3, 0, 0, 7,
+	9, 14, 0, 2, 3, 1, 1, 4, 11, 14, 1, 0, 3, 2, 0, 5,
+	11, 14, 0, 1, 3, 2, 2, 5, 8, 15, 2, 1, 0, 3, 1, 6,
+	8, 15, 2, 0, 1, 3, 2, 4, 9, 15, 1, 2, 0, 3, 0, 6,
+	9, 15, 0, 2, 1, 3, 1, 4, 10, 15, 1, 0, 2, 3, 0, 5,
+	10, 15, 0, 1, 2, 3,
+};
+
+/* generated by mtdev-kernel - do not edit */
+static const int match_index[][5] = {
+	{ 0, 0, 1, 3, 6 },
+	{ 10, 10, 12, 18, 30 },
+	{ 50, 50, 54, 62, 92 },
+	{ 164, 164, 170, 194, 230 },
+	{ 398, 398, 406, 454, 598 },
+	{ 790 }
+};
+
+static void set_dist(u32 *dist,
+		     const struct trk_coord *b1, const struct trk_coord *e1,
+		     const struct trk_coord *b2, const struct trk_coord *e2)
+{
+	const struct trk_coord *p, *q;
+
+	for (p = b1; p != e1; p++)
+		for (q = b2; q != e2; q++)
+			*dist++ = abs(q->x - p->x) + abs(q->y - p->y);
+}
+
+const u8 *match_four(const struct trk_coord *old, int nslot,
+		     const struct trk_coord *pos, int npos)
+{
+	u32 d[16], obj, t;
+	const u8 *p, *b, *e;
+	const int *at;
+
+	set_dist(d, old, old + nslot, pos, pos + npos);
+
+	at = &match_index[nslot][npos];
+	b = &match_data[at[0]];
+	e = &match_data[at[1]];
+
+	obj = UINT_MAX, p = b;
+
+	switch (min(nslot, npos)) {
+	case 1:
+		for (; b != e; b += npos) {
+			t = d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 2:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 3:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 4:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++], t += d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	}
+
+	return p;
+}
+
+static int get_mt_value(const struct input_mt_slot *slot, unsigned code)
+{
+	return slot->abs[code - ABS_MT_FIRST];
+}
+
+/**
+ * input_trk_assign_slots_by_coord() - perform a best-match assignment
+ * @dev: input device with allocated MT slots
+ * @slots: the slot assignment to be filled
+ * @coords: the coordinate array to match
+ * @num_coords: number of coordinates
+ *
+ * Performs a best match against the current contacts and returns
+ * the slot assignment list. New contacts are assigned to unused
+ * slots.
+ *
+ * Returns zero on success, or negative error in case of failure.
+ */
+int input_trk_assign_slots_by_coord(struct input_dev *dev, int *slots,
+				    const struct trk_coord *coords,
+				    int num_coords)
+{
+	struct trk_coord old[4];
+	int old2slot[4], nold, i;
+	const u8 *p;
+
+	if (!dev->mt)
+		return -ENXIO;
+	if (dev->mtsize < 2 || dev->mtsize > 4)
+		return -ENXIO;
+	if (num_coords > dev->mtsize)
+		return -EINVAL;
+	if (num_coords < 1)
+		return 0;
+
+	nold = 0;
+	for (i = 0; i < dev->mtsize; i++) {
+		const struct input_mt_slot *mt = &dev->mt[i];
+		if (get_mt_value(mt, ABS_MT_TRACKING_ID) < 0)
+			continue;
+		old[nold].x = get_mt_value(mt, ABS_MT_POSITION_X);
+		old[nold].y = get_mt_value(mt, ABS_MT_POSITION_Y);
+		old2slot[nold++] = i;
+	}
+
+	p = match_four(old, nold, coords, num_coords);
+
+	for (i = 0; i < dev->mtsize; i++)
+		if (get_mt_value(&dev->mt[i], ABS_MT_TRACKING_ID) < 0)
+			old2slot[nold++] = i;
+
+	for (i = 0; i < num_coords; i++)
+		slots[i] = old2slot[p[i]];
+
+	return 0;
+}
+EXPORT_SYMBOL(input_trk_assign_slots_by_coord);
diff --git a/include/linux/input-trk.h b/include/linux/input-trk.h
new file mode 100644
index 0000000..e10e312
--- /dev/null
+++ b/include/linux/input-trk.h
@@ -0,0 +1,30 @@
+#ifndef _INPUT_TRK_H
+#define _INPUT_TRK_H
+
+/*
+ * Input Multitouch Tracking Library
+ *
+ * Copyright (c) 2010 Henrik Rydberg
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ */
+
+#include <linux/input.h>
+
+/**
+ * struct trk_coord - contact coordinate
+ * @x: horizontal coordinate
+ * @y: vertical coordinate
+ */
+struct trk_coord {
+	int x;
+	int y;
+};
+
+int input_trk_assign_slots_by_coord(struct input_dev *dev, int *slots,
+				    const struct trk_coord *coords,
+				    int num_coords);
+
+#endif
-- 
1.7.1

Re: [PATCH] input: Introduce light-weight contact tracking

[Rafi Rubin]

On 11/07/2010 03:18 PM, Henrik Rydberg wrote:
 > Some kernel drivers demand the use of contact tracking for proper
 > filtering and pointer emulation. With one exception, these drivers
 > are limited to a maximum of four concurrent contacts. This patch adds
 > a simple matcher for up to four contacts, with these notable properties:

Tracking in the ntrig driver needs to support a minimum of 6 fingers.  I have 
also seen press releases claiming 10+ eventually.  I don't know if those devices 
will support tracking in the hardware/firmware.

Rafi

Re: [PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

On 11/07/2010 09:44 PM, Rafi Rubin wrote:

> On 11/07/2010 03:18 PM, Henrik Rydberg wrote:
>> Some kernel drivers demand the use of contact tracking for proper
>> filtering and pointer emulation. With one exception, these drivers
>> are limited to a maximum of four concurrent contacts. This patch adds
>> a simple matcher for up to four contacts, with these notable properties:
> 
> Tracking in the ntrig driver needs to support a minimum of 6 fingers.  I have
> also seen press releases claiming 10+ eventually.  I don't know if those devices
> will support tracking in the hardware/firmware.


This is the exception I was talking about. The thing is, I can very well see a
driver supporting four fingers even if the device claims to support six. After
all, getting those four fingers working well will still be a big improvement.

Henrik

Re: [PATCH] input: Introduce light-weight contact tracking

[Rafi Rubin]

On 11/07/2010 03:18 PM, Henrik Rydberg wrote:
> The synaptics patches are currently cooking at Bagwell's, and we
> already discussed the API a bit. Something ntrig-ish is cooking at
> Rubin's, and there is also the ntrig driver in Ubuntu 10.10 to
> consider. All-in-all, it is my hope that posting this patch will
> simplify the synchronization of our efforts.

Since Henrik brought it up, here's the tracking code I've been working on.  I 
have not run performance tests.  My goals for this code are perhaps a little 
different.

- efficient for the common case where contact ordering stays consistent
- arbitrary number of contacts
- motion estimation to improve tracking
- leveraging tracking for error filtering

Also for fun, I was playing with smoothing in this particular version of the code.

For now, I'm sending this just for review and discussion.

Rafi

---
diff --git a/drivers/hid/hid-ntrig.c b/drivers/hid/hid-ntrig.c
index 69169ef..d163b9b 100644
--- a/drivers/hid/hid-ntrig.c
+++ b/drivers/hid/hid-ntrig.c
@@ -19,10 +19,25 @@
  #include "usbhid/usbhid.h"
  #include <linux/module.h>
  #include <linux/slab.h>
+#include <linux/list.h>

  #include "hid-ids.h"

  #define NTRIG_DUPLICATE_USAGES	0x001
+/**
+ * list_rotate_left - rotate the list to the left
+ * @head: the head of the list
+ */
+static inline void list_rotate_right(struct list_head *head)
+{
+	struct list_head *last;
+
+	if (!list_empty(head)) {
+		last = head->prev;
+		list_move(last, head);
+	}
+}
+

  static unsigned int min_width;
  module_param(min_width, uint, 0644);
@@ -52,10 +67,45 @@ module_param(activation_height, uint, 0644);
  MODULE_PARM_DESC(activation_height, "Height threshold to immediately start "
  		 "processing touch events.");

+struct ntrig_slot {
+	__u16 id;
+	struct list_head list;
+};
+
+struct ntrig_contact {
+	__u16 x, y, w, h;
+	__s16 est_x_min, est_x_max, est_y_min, est_y_max;
+	__s16 dx, dy;
+	__s16 id;
+
+	/* An age factor for counting frames since a track was last seen.
+	 * This enables drop compensation and delayed termination. */
+	__u8 inactive;
+
+	struct ntrig_slot *slot;
+
+	struct list_head list;
+
+	/* List of tracks sorted by first seen order */
+	struct list_head active_tracks;
+};
+
+struct ntrig_frame {
+
+	/* Items that represent physical contacts which have been mapped
+	 * to contacts from previous frames. */
+	struct list_head tracked;
+
+	/* Contacts that have yet to be matched and might be ghosts. */
+	struct list_head pending;
+	struct list_head list;
+};
+
  struct ntrig_data {
  	/* Incoming raw values for a single contact */
  	__u16 x, y, w, h;
  	__u16 id;
+	int slots;

  	bool tipswitch;
  	bool confidence;
@@ -63,6 +113,8 @@ struct ntrig_data {

  	bool reading_mt;

+	__u8 max_contacts;
+
  	__u8 mt_footer[4];
  	__u8 mt_foot_count;

@@ -87,8 +139,24 @@ struct ntrig_data {
  	__u16 sensor_logical_height;
  	__u16 sensor_physical_width;
  	__u16 sensor_physical_height;
-};

+	__u16 r_y;
+	__u16 r_x;
+
+	/* Circular list of frames used to maintain state of contacts */
+	struct list_head frames;
+
+	/* Contacts representing the last input from lost tracks and
+	 * old contacts to be recycled */
+	struct list_head old_contacts;
+
+	struct list_head available_slots;
+	struct list_head active_tracks;
+
+	struct ntrig_frame *first_frame;
+	struct ntrig_slot *first_slot;
+	struct ntrig_contact *first_contact;
+};

  /*
   * This function converts the 4 byte raw firmware code into
@@ -439,6 +507,7 @@ static int ntrig_input_mapping(struct hid_device *hdev, 
struct hid_input *hi,
  	case HID_UP_GENDESK:
  		switch (usage->hid) {
  		case HID_GD_X:
+			nd->max_contacts++;
  			hid_map_usage(hi, usage, bit, max,
  					EV_ABS, ABS_MT_POSITION_X);
  			input_set_abs_params(hi->input, ABS_X,
@@ -505,6 +574,8 @@ static int ntrig_input_mapping(struct hid_device *hdev, 
struct hid_input *hi,
  			input_set_abs_params(hi->input, ABS_MT_ORIENTATION,
  					     0, 1, 0, 0);
  			return 1;
+		case HID_DG_CONTACTCOUNT:
+			break;
  		}
  		return 0;

@@ -531,6 +602,299 @@ static int ntrig_input_mapped(struct hid_device *hdev, 
struct hid_input *hi,
  	return 0;
  }

+static void ntrig_store_contact(struct ntrig_data *nd)
+{
+	struct ntrig_contact *contact;
+	struct ntrig_frame *frame;
+
+	if (list_empty(&nd->old_contacts))
+		printk(KERN_ERR "Ran out of contacts\n");
+
+	if (list_empty(&nd->old_contacts) || list_empty(&nd->frames))
+		return;
+
+	frame = list_first_entry(&nd->frames, struct ntrig_frame, list);
+
+	contact = list_entry(nd->old_contacts.prev, struct ntrig_contact,
+			     list);
+	contact->inactive = 0;
+	contact->x = nd->x;
+	contact->y = nd->y;
+	contact->w = nd->w;
+	contact->h = nd->h;
+	contact->id = nd->max_contacts;
+
+	contact->est_y_min = nd->y - nd->r_y;
+	contact->est_y_max = nd->y + nd->r_y;
+	contact->est_x_min = nd->x - nd->r_x;
+	contact->est_x_max = nd->x + nd->r_x;
+
+	list_move_tail(&contact->list, &frame->pending);
+}
+
+/* Update the state of a track to the most recent matched contact */
+static inline void ntrig_update_track(struct ntrig_data *nd,
+				      struct ntrig_contact *old,
+				      struct ntrig_contact *cur,
+				      struct ntrig_frame *frame)
+{
+	/* Simple motion estimation */
+	cur->dx = cur->x - old->x;
+	cur->dy = cur->y - old->y;
+	cur->est_x_min = cur->x + cur->dx - nd->r_x;
+	cur->est_x_max = cur->x + cur->dx + nd->r_x;
+	cur->est_y_min = cur->y + cur->dy - nd->r_y;
+	cur->est_y_max = cur->y + cur->dy + nd->r_y;
+
+	/* Update the state of the contact in the frame */
+	list_move_tail(&cur->list, &frame->tracked);
+
+	/* Recycle the old contact.  At the moment only the
+	 * most recent contact of a track is used. */
+	old->inactive = nd->deactivate_slack;
+	list_move_tail(&old->list, &nd->old_contacts);
+
+	/* move the slot pointer to the new contact */
+	cur->slot = old->slot;
+	old->slot = NULL;
+
+	/* Update the pointer in the active tracks list to the new
+	 * contact.  If this track doesn't have a slot, assign it one
+	 * and add to the tail of the list.  If we run out of slots
+	 * we can assign one when a slot opens up. */
+	if (cur->slot) {
+		cur->id = cur->slot->id;
+		list_replace(&old->active_tracks, &cur->active_tracks);
+	} else if (!list_empty(&nd->available_slots)) {
+		cur->slot = list_first_entry(&nd->available_slots,
+				struct ntrig_slot, list);
+		nd->slots--;
+		cur->id = cur->slot->id;
+		list_del(&cur->slot->list);
+		list_add_tail(&cur->active_tracks, &nd->active_tracks);
+	}
+}
+
+static inline bool ntrig_match(struct ntrig_data *nd, struct ntrig_contact *a,
+			       struct ntrig_contact *b,
+			       struct ntrig_frame *frame)
+{
+	if (b->y >= a->est_y_min && b->y <= a->est_y_max &&
+		b->x >= a->est_x_min && b->x <= a->est_x_max) {
+		ntrig_update_track(nd, a, b, frame);
+		a->inactive = nd->deactivate_slack;
+		list_move_tail(&a->list, &nd->old_contacts);
+		return true;
+	}
+
+	return false;
+}
+
+static inline bool ntrig_match_three(struct ntrig_data *nd,
+				     struct ntrig_contact *a,
+				     struct ntrig_contact *b,
+				     struct ntrig_contact *c,
+				     struct ntrig_frame *frame)
+{
+	int est_y = b->y * 2 - a->y;
+	int est_x = b->x * 2 - a->x;
+
+	if (c->y >= est_y - nd->r_y && c->y <= est_y + nd->r_y &&
+	    c->x >= est_x - nd->r_x && c->x <= est_x + nd->r_x) {
+		ntrig_update_track(nd, b, c, frame);
+		return true;
+	}
+
+	return false;
+}
+
+static inline void ntrig_terminate_track(struct ntrig_data *nd,
+					 struct ntrig_contact *contact)
+{
+	/* slot should not be NULL here, but checking to be sure */
+	if (contact->slot) {
+		/* return the slot to the available pool */
+		list_add_tail(&contact->slot->list, &nd->available_slots);
+		nd->slots++;
+		contact->slot = NULL;
+		list_del(&contact->active_tracks);
+	}
+
+	/* mark this contact as expired */
+	contact->inactive = nd->deactivate_slack;
+}
+
+/* Shift and increase the size of the region of the estimated position
+ * for a lost track */
+static inline bool ntrig_age_contact(struct ntrig_data *nd,
+				     struct ntrig_contact *contact)
+{
+	contact->inactive++;
+	if (contact->inactive >= nd->deactivate_slack) {
+		contact->inactive++;
+		ntrig_terminate_track(nd, contact);
+		return true;
+	} else {
+		contact->est_x_min += contact->dx -
+				      (nd->r_x >> contact->inactive);
+		contact->est_x_max += contact->dx +
+				      (nd->r_x >> contact->inactive);
+		contact->est_y_min += contact->dy -
+				      (nd->r_y >> contact->inactive);
+		contact->est_y_max += contact->dy +
+				      (nd->r_y >> contact->inactive);
+	}
+	return false;
+}
+
+static void track(struct ntrig_data *nd)
+{
+	struct ntrig_frame *prev_frame, *cur_frame, *older_frame;
+	struct ntrig_contact *old, *old_tmp, *cur, *cur_tmp, *older, *older_tmp;
+
+	if (list_empty(&nd->frames))
+		return;
+
+	older_frame = list_first_entry(nd->frames.next->next,
+				       struct ntrig_frame, list);
+	prev_frame = list_first_entry(nd->frames.next, struct ntrig_frame,
+				      list);
+	cur_frame = list_first_entry(&nd->frames, struct ntrig_frame, list);
+
+	list_for_each_entry_safe(cur, cur_tmp, &cur_frame->pending, list) {
+		/* First look for a match in current active tracks.
+		 * By far the most common case is that this will
+		 * match the first element in the list */
+		list_for_each_entry_safe(old, old_tmp, &prev_frame->tracked,
+					 list) {
+			if (ntrig_match(nd, old, cur, cur_frame))
+				goto found;
+		}
+
+		/* Compare against retiring, but not yet deactivated tracks */
+		list_for_each_entry_safe(old, old_tmp, &nd->old_contacts,
+					 list) {
+			if (old->inactive >= nd->deactivate_slack &&
+			    old->inactive)
+				break;
+
+			if (ntrig_match(nd, old, cur, cur_frame))
+				goto found;
+		}
+
+		/* Search for a match among unmatch contacts in the previous
+		 * frame.  This is where new tracks are found */
+		list_for_each_entry_safe(old, old_tmp, &prev_frame->pending,
+					 list) {
+			if (ntrig_match(nd, old, cur, cur_frame))
+				goto found;
+		}
+
+		list_for_each_entry_safe(old, old_tmp, &prev_frame->pending,
+					 list) {
+			list_for_each_entry_safe(older, older_tmp,
+						 &older_frame->pending,
+						 list) {
+				if (ntrig_match_three(nd, older, old, cur,
+						      cur_frame))
+					goto found;
+			}
+		}
+
+found:;
+	}
+
+	/* Traces that were active last frame but absent from the current frame
+	 * are dropped to the old_contacts list for aging and possible recovery
+	 */
+	list_for_each_entry_safe(old, old_tmp, &prev_frame->tracked, list) {
+		if (nd->deactivate_slack <= 0) {
+			ntrig_terminate_track(nd, old);
+			old->inactive = 1;
+		}
+	}
+	list_splice_init(&prev_frame->tracked, &nd->old_contacts);
+}
+
+static void emit_frame(struct input_dev *input, struct ntrig_data *nd)
+{
+	struct ntrig_contact *contact, *contact_tmp;
+	struct ntrig_frame *frame;
+
+	if (list_empty(&nd->frames))
+		return;
+
+	/* Age old contacts and terminate expired tracks */
+	list_for_each_entry_safe(contact, contact_tmp, &nd->old_contacts,
+				 list) {
+		/* Potentially interesting contacts should be
+		 * sorted by the number of frames since they
+		 * were last seen.  We can stop iterating with the
+		 * first expired contact. */
+		if (contact->inactive >= nd->deactivate_slack &&
+		    contact->inactive)
+			break;
+
+		ntrig_age_contact(nd, contact);
+	}
+
+	frame = list_first_entry(&nd->frames, struct ntrig_frame, list);
+
+	if (!list_empty(&frame->tracked)) {
+		if (!list_empty(&nd->active_tracks)) {
+			/* Emit the position of the oldest active track as
+			 * normal events. */
+			contact = list_first_entry(&nd->active_tracks,
+						   struct ntrig_contact,
+						   active_tracks);
+			input_report_key(input, BTN_TOUCH, 1);
+			input_event(input, EV_ABS, ABS_X,
+				    contact->x - (contact->dx/2));
+			input_event(input, EV_ABS, ABS_Y,
+				    contact->y - (contact->dy/2));
+		}
+	} else if (list_empty(&nd->active_tracks)) {
+		input_report_key(input, BTN_TOUCH, 0);
+	}
+
+	/* Emit MT events */
+	list_for_each_entry(contact, &frame->tracked, list) {
+		input_event(input, EV_ABS, ABS_MT_POSITION_X,
+			    contact->x - (contact->dx/2));
+		input_event(input, EV_ABS, ABS_MT_POSITION_Y,
+			    contact->y - (contact->dy/2));
+		/*
+		 * Translate from height and width to size
+		 * and orientation.
+		 */
+		if (contact->w > contact->h) {
+			input_event(input, EV_ABS, ABS_MT_ORIENTATION, 1);
+			input_event(input, EV_ABS, ABS_MT_TOUCH_MAJOR,
+				    contact->w);
+			input_event(input, EV_ABS, ABS_MT_TOUCH_MINOR,
+				    contact->h);
+		} else {
+			input_event(input, EV_ABS, ABS_MT_ORIENTATION, 0);
+			input_event(input, EV_ABS, ABS_MT_TOUCH_MAJOR,
+				    contact->h);
+			input_event(input, EV_ABS, ABS_MT_TOUCH_MINOR,
+				    contact->w);
+		}
+		input_mt_sync(input);
+	}
+
+	list_rotate_right(&nd->frames);
+	frame = list_first_entry(&nd->frames, struct ntrig_frame, list);
+
+	/* Recycle the old conacts to prepare the frame for reuse */
+	list_splice_init(&frame->tracked, &frame->pending);
+
+	list_for_each_entry(contact, &frame->pending, list) {
+		contact->inactive = nd->deactivate_slack;
+	}
+	list_splice_tail_init(&frame->pending, &nd->old_contacts);
+}
+
  /*
   * this function is called upon all reports
   * so that we can filter contact point information,
@@ -631,87 +995,11 @@ static int ntrig_event (struct hid_device *hid, struct 
hid_field *field,
  			 * The first footer value indicates the presence of a
  			 * finger.
  			 */
-			if (nd->mt_footer[0]) {
-				/*
-				 * We do not want to process contacts under
-				 * the size threshold, but do not want to
-				 * ignore them for activation state
-				 */
-				if (nd->w < nd->min_width ||
-				    nd->h < nd->min_height)
-					nd->confidence = 0;
-			} else
-				break;
-
-			if (nd->act_state > 0) {
-				/*
-				 * Contact meets the activation size threshold
-				 */
-				if (nd->w >= nd->activation_width &&
-				    nd->h >= nd->activation_height) {
-					if (nd->id)
-						/*
-						 * first contact, activate now
-						 */
-						nd->act_state = 0;
-					else {
-						/*
-						 * avoid corrupting this frame
-						 * but ensure next frame will
-						 * be active
-						 */
-						nd->act_state = 1;
-						break;
-					}
-				} else
-					/*
-					 * Defer adjusting the activation state
-					 * until the end of the frame.
-					 */
-					break;
-			}
-
-			/* Discarding this contact */
-			if (!nd->confidence)
+			if (!nd->mt_footer[0])
  				break;

-			/* emit a normal (X, Y) for the first point only */
-			if (nd->id == 0) {
-				/*
-				 * TipSwitch is superfluous in multitouch
-				 * mode.  The footer events tell us
-				 * if there is a finger on the screen or
-				 * not.
-				 */
-				nd->first_contact_touch = nd->confidence;
-				input_event(input, EV_ABS, ABS_X, nd->x);
-				input_event(input, EV_ABS, ABS_Y, nd->y);
-			}
-
-			/* Emit MT events */
-			input_event(input, EV_ABS, ABS_MT_POSITION_X, nd->x);
-			input_event(input, EV_ABS, ABS_MT_POSITION_Y, nd->y);
-
-			/*
-			 * Translate from height and width to size
-			 * and orientation.
-			 */
-			if (nd->w > nd->h) {
-				input_event(input, EV_ABS,
-						ABS_MT_ORIENTATION, 1);
-				input_event(input, EV_ABS,
-						ABS_MT_TOUCH_MAJOR, nd->w);
-				input_event(input, EV_ABS,
-						ABS_MT_TOUCH_MINOR, nd->h);
-			} else {
-				input_event(input, EV_ABS,
-						ABS_MT_ORIENTATION, 0);
-				input_event(input, EV_ABS,
-						ABS_MT_TOUCH_MAJOR, nd->h);
-				input_event(input, EV_ABS,
-						ABS_MT_TOUCH_MINOR, nd->w);
-			}
-			input_mt_sync(field->hidinput->input);
+			if (nd->confidence)
+				ntrig_store_contact(nd);
  			break;

  		case HID_DG_CONTACTCOUNT: /* End of a multitouch group */
@@ -720,89 +1008,9 @@ static int ntrig_event (struct hid_device *hid, struct 
hid_field *field,

  			nd->reading_mt = 0;

+			track(nd);
+			emit_frame(input, nd);

-			/*
-			 * Activation state machine logic:
-			 *
-			 * Fundamental states:
-			 *	state >  0: Inactive
-			 *	state <= 0: Active
-			 *	state <  -deactivate_slack:
-			 *		 Pen termination of touch
-			 *
-			 * Specific values of interest
-			 *	state == activate_slack
-			 *		 no valid input since the last reset
-			 *
-			 *	state == 0
-			 *		 general operational state
-			 *
-			 *	state == -deactivate_slack
-			 *		 read sufficient empty frames to accept
-			 *		 the end of input and reset
-			 */
-
-			if (nd->act_state > 0) { /* Currently inactive */
-				if (value)
-					/*
-					 * Consider each live contact as
-					 * evidence of intentional activity.
-					 */
-					nd->act_state = (nd->act_state > value)
-							? nd->act_state - value
-							: 0;
-				else
-					/*
-					 * Empty frame before we hit the
-					 * activity threshold, reset.
-					 */
-					nd->act_state = nd->activate_slack;
-
-				/*
-				 * Entered this block inactive and no
-				 * coordinates sent this frame, so hold off
-				 * on button state.
-				 */
-				break;
-			} else { /* Currently active */
-				if (value && nd->act_state >=
-					     nd->deactivate_slack)
-					/*
-					 * Live point: clear accumulated
-					 * deactivation count.
-					 */
-					nd->act_state = 0;
-				else if (nd->act_state <= nd->deactivate_slack)
-					/*
-					 * We've consumed the deactivation
-					 * slack, time to deactivate and reset.
-					 */
-					nd->act_state =
-						nd->activate_slack;
-				else { /* Move towards deactivation */
-					nd->act_state--;
-					break;
-				}
-			}
-
-			if (nd->first_contact_touch && nd->act_state <= 0) {
-				/*
-				 * Check to see if we're ready to start
-				 * emitting touch events.
-				 *
-				 * Note: activation slack will decrease over
-				 * the course of the frame, and it will be
-				 * inconsistent from the start to the end of
-				 * the frame.  However if the frame starts
-				 * with slack, first_contact_touch will still
-				 * be 0 and we will not get to this point.
-				 */
-				input_report_key(input, BTN_TOOL_DOUBLETAP, 1);
-				input_report_key(input, BTN_TOUCH, 1);
-			} else {
-				input_report_key(input, BTN_TOOL_DOUBLETAP, 0);
-				input_report_key(input, BTN_TOUCH, 0);
-			}
  			break;

  		default:
@@ -818,33 +1026,93 @@ static int ntrig_event (struct hid_device *hid, struct 
hid_field *field,
  	return 1;
  }

+static int ntrig_alloc_mt_structures(struct ntrig_data *nd, int contact_count)
+{
+	struct ntrig_frame *frames;
+	struct ntrig_slot *slots;
+	struct ntrig_contact *contacts;
+	int i, num_frames, num_slots, num_contacts;
+
+	num_frames = 3;
+	num_slots = contact_count * 2;
+	num_contacts = (num_frames + 1) * contact_count;
+
+	frames = kcalloc(num_frames, sizeof(*frames), GFP_KERNEL);
+	if (!frames)
+		goto err;
+	nd->first_frame = frames;
+
+	contacts = kcalloc(num_contacts, sizeof(*contacts),
+			GFP_KERNEL);
+	if (!contacts)
+		goto err_free_frames;
+	nd->first_contact = contacts;
+
+	slots = kcalloc(num_slots, sizeof(*slots), GFP_KERNEL);
+	if (!slots)
+		goto err_free_contacts;
+	nd->first_slot = slots;
+
+	nd->slots = num_slots;
+
+	/* Stuff the structures into their initial lists */
+	for (i = 0; i < num_frames; i++) {
+		INIT_LIST_HEAD(&frames[i].tracked);
+		INIT_LIST_HEAD(&frames[i].pending);
+		list_add(&frames[i].list, &nd->frames);
+	}
+
+	for (i = 0; i < num_slots; i++) {
+		slots[i].id = i;
+		list_add_tail(&slots[i].list, &nd->available_slots);
+	}
+
+	for (i = 0; i < num_contacts; i++) {
+		/* Tag as expired */
+		contacts[i].inactive = nd->deactivate_slack;
+		list_add(&contacts[i].list, &nd->old_contacts);
+	}
+
+	return 0;
+
+err_free_contacts:
+	kfree(contacts);
+err_free_frames:
+	kfree(frames);
+err:
+	return -ENOMEM;
+}
+
  static int ntrig_probe(struct hid_device *hdev, const struct hid_device_id *id)
  {
-	int ret;
+	int ret, i, j, contacts;
  	struct ntrig_data *nd;
  	struct hid_input *hidinput;
  	struct input_dev *input;
  	struct hid_report *report;
+	struct hid_field *field;

  	if (id->driver_data)
  		hdev->quirks |= HID_QUIRK_MULTI_INPUT;

-	nd = kmalloc(sizeof(struct ntrig_data), GFP_KERNEL);
+	nd = kzalloc(sizeof(*nd), GFP_KERNEL);
  	if (!nd) {
  		dev_err(&hdev->dev, "cannot allocate N-Trig data\n");
  		return -ENOMEM;
  	}

-	nd->reading_mt = 0;
-	nd->min_width = 0;
-	nd->min_height = 0;
  	nd->activate_slack = activate_slack;
  	nd->act_state = activate_slack;
  	nd->deactivate_slack = -deactivate_slack;
-	nd->sensor_logical_width = 0;
-	nd->sensor_logical_height = 0;
-	nd->sensor_physical_width = 0;
-	nd->sensor_physical_height = 0;
+	nd->r_x = 500;
+	nd->r_y = 500;
+
+
+	/* Initialize tracking structures */
+	INIT_LIST_HEAD(&nd->frames);
+	INIT_LIST_HEAD(&nd->old_contacts);
+	INIT_LIST_HEAD(&nd->available_slots);
+	INIT_LIST_HEAD(&nd->active_tracks);

  	hid_set_drvdata(hdev, nd);

@@ -865,8 +1133,9 @@ static int ntrig_probe(struct hid_device *hdev, const 
struct hid_device_id *id)
  		if (hidinput->report->maxfield < 1)
  			continue;

+		report = hidinput->report;
  		input = hidinput->input;
-		switch (hidinput->report->field[0]->application) {
+		switch (report->field[0]->application) {
  		case HID_DG_PEN:
  			input->name = "N-Trig Pen";
  			break;
@@ -877,26 +1146,30 @@ static int ntrig_probe(struct hid_device *hdev, const 
struct hid_device_id *id)
  			__clear_bit(BTN_TOOL_FINGER, input->keybit);
  			__clear_bit(BTN_0, input->keybit);
  			__set_bit(BTN_TOOL_DOUBLETAP, input->keybit);
-			/*
-			 * The physical touchscreen (single touch)
-			 * input has a value for physical, whereas
-			 * the multitouch only has logical input
-			 * fields.
-			 */
-			input->name =
-				(hidinput->report->field[0]
-				 ->physical) ?
-				"N-Trig Touchscreen" :
-				"N-Trig MultiTouch";
+
+			contacts = 0;
+			for (i = 0; i < report->maxfield; i++) {
+				field = report->field[i];
+				for (j = 0; j <= field->maxusage; j++) {
+					if (field->usage[j].hid ==
+					    HID_DG_CONTACTID)
+						contacts++;
+				}
+			}
+
+			/* Only MT devices have contact id */
+			if (contacts) {
+				input->name = "N-Trig MultiTouch";
+				nd->max_contacts = contacts;
+				ret = ntrig_alloc_mt_structures(nd, contacts);
+				if (ret)
+					goto err_free;
+			} else
+				input->name = "N-Trig Touchscreen";
  			break;
  		}
  	}

-	/* This is needed for devices with more recent firmware versions */
-	report = hdev->report_enum[HID_FEATURE_REPORT].report_id_hash[0x0a];
-	if (report)
-		usbhid_submit_report(hdev, report, USB_DIR_OUT);
-
  	ntrig_report_version(hdev);

  	ret = sysfs_create_group(&hdev->dev.kobj,
@@ -910,10 +1183,16 @@ err_free:

  static void ntrig_remove(struct hid_device *hdev)
  {
+	struct ntrig_data *nd = hid_get_drvdata(hdev);
+
  	sysfs_remove_group(&hdev->dev.kobj,
  			   &ntrig_attribute_group);
  	hid_hw_stop(hdev);
-	kfree(hid_get_drvdata(hdev));
+
+	kfree(nd->first_frame);
+	kfree(nd->first_slot);
+	kfree(nd->first_contact);
+	kfree(nd);
  }

  static const struct hid_device_id ntrig_devices[] = {

Re: [PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

On 11/07/2010 11:14 PM, Rafi Rubin wrote:

> On 11/07/2010 03:18 PM, Henrik Rydberg wrote:
>> The synaptics patches are currently cooking at Bagwell's, and we
>> already discussed the API a bit. Something ntrig-ish is cooking at
>> Rubin's, and there is also the ntrig driver in Ubuntu 10.10 to
>> consider. All-in-all, it is my hope that posting this patch will
>> simplify the synchronization of our efforts.
> 
> Since Henrik brought it up, here's the tracking code I've been working on.  I
> have not run performance tests.  My goals for this code are perhaps a little
> different.
> 
> - efficient for the common case where contact ordering stays consistent
> - arbitrary number of contacts
> - motion estimation to improve tracking
> - leveraging tracking for error filtering
> 
> Also for fun, I was playing with smoothing in this particular version of the code.
> 
> For now, I'm sending this just for review and discussion.


Hi Rafi,

what tree does this patch apply to?

I think the situation with this driver is slightly cumbersome. Perhaps there is
a small conflict of interest here, but I hope we will be able to resolve it
quickly. I see little benefit in duplicating the tracking efforts. Since greedy
matching algorithms are not provably suited to the task, I think any such
algorithm should first be tested and benchmarked thoroughly, preferably in the
mtdev context.

Regarding the ntrig driver, fact is it does not work very well. Contacts are
occasionally dropped, and spurious ghosts make multitouch gestures not work
properly. There are also many parameters in the driver, which are difficult to
use in practice. Therefore, in the Ubuntu 10.10 kernel, a rather large ntrig
patch has been applied, improving those issues.

The way the data is extracted in 2.6.36 leads to many dropped contacts. The
ubuntu patch remedies this problem, so no particular logic for drops is needed.
Instead, more effort is put into removing ghost contacts, which greatly improves
the actual experience with multitouch gestures.

In order for ghost removal to work, the contacts need to be tracked. Because of
the deficiencies of the ntrig firmware, this needs to be done in software. The
ubuntu patch contains a simple greedy tracking mechanism, which did not seem
good enough to upstream, so I never upstreamed it.

With the proposed matcher (http://lkml.org/lkml/2010/11/7/122), the situation is
different. The ubuntu patch can be modified to use the matcher, which I believe
will make it ready for upstream. Since the patch also removes all parameters
from the driver, the usability aspect is improved.

With the above said, it seems to me that the simplest way forward is to modify
and upstream the ubuntu patches. Would you agree?

Regarding support for more than four fingers, there is a single device which
reports six contacts from the firmware. Getting four good contacts out of it
will be a major improvement, and IMO good enough. It seems likely that future
firmware will handle tracking properly, so this should all be a stop-gap measure
anyways.

We talked earlier about the possibility to perform automatic calibration of the
driver. This would be the last major step towards a fully functional,
maintenance-free driver.

I hope we will be able to agree on the direction of this driver, such that
duplicated work is minimized and the focus stays with the user experience of the
ntrig devices.

Thanks,
Henrik

Re: [PATCH] input: Introduce light-weight contact tracking

[Rafi Rubin]

On 11/08/2010 09:57 AM, Henrik Rydberg wrote:
> Hi Rafi,
>
> what tree does this patch apply to?

It should apply to the torvalds/linux-2.6 master branch.

> I think the situation with this driver is slightly cumbersome. Perhaps there is
> a small conflict of interest here, but I hope we will be able to resolve it
> quickly. I see little benefit in duplicating the tracking efforts. Since greedy
> matching algorithms are not provably suited to the task, I think any such
> algorithm should first be tested and benchmarked thoroughly, preferably in the
> mtdev context.
>
> Regarding the ntrig driver, fact is it does not work very well. Contacts are
> occasionally dropped, and spurious ghosts make multitouch gestures not work
> properly. There are also many parameters in the driver, which are difficult to
> use in practice. Therefore, in the Ubuntu 10.10 kernel, a rather large ntrig
> patch has been applied, improving those issues.
>
> The way the data is extracted in 2.6.36 leads to many dropped contacts. The
> ubuntu patch remedies this problem, so no particular logic for drops is needed.
> Instead, more effort is put into removing ghost contacts, which greatly improves
> the actual experience with multitouch gestures.
>
> In order for ghost removal to work, the contacts need to be tracked. Because of
> the deficiencies of the ntrig firmware, this needs to be done in software. The
> ubuntu patch contains a simple greedy tracking mechanism, which did not seem
> good enough to upstream, so I never upstreamed it.
>
> With the proposed matcher (http://lkml.org/lkml/2010/11/7/122), the situation is
> different. The ubuntu patch can be modified to use the matcher, which I believe
> will make it ready for upstream. Since the patch also removes all parameters
> from the driver, the usability aspect is improved.
>
> With the above said, it seems to me that the simplest way forward is to modify
> and upstream the ubuntu patches. Would you agree?
>
> Regarding support for more than four fingers, there is a single device which
> reports six contacts from the firmware. Getting four good contacts out of it
> will be a major improvement, and IMO good enough. It seems likely that future
> firmware will handle tracking properly, so this should all be a stop-gap measure
> anyways.
>
> We talked earlier about the possibility to perform automatic calibration of the
> driver. This would be the last major step towards a fully functional,
> maintenance-free driver.
>
> I hope we will be able to agree on the direction of this driver, such that
> duplicated work is minimized and the focus stays with the user experience of the
> ntrig devices.

The "complex" set of parameters was intended for more advanced users to give 
some feedback to help improve the driver.  Though given the lack of feedback, I 
guess you're right that there's little reason to expose them to users.

The ubuntu 10.10 code does do filtering better than without filtering, but in 
trying it I've been seeing ghosts and have needed to calibrate multiple times 
per day (though that may be the result of a new screen being a little off). 
Furthermore while ripping out the filter code, you also ripped out single touch 
support for single touch firmwares, which apparently a few people still use.

Even without the ghost problem, it simply does not track as well.  The ntrig 
only reports every 8-24ms which is a long enough period to move quite a 
distance.  In drawing up corner cases I realized that motion where two fingers 
are co-linear with the vector of motion require quite a bit of care to avoid 
perverting the tracking.  Greedily assigning matches based purely on distance 
can cause a flip.  Even global distance minimization is not reliable when we use 
linear distance as the cost.  A full analysis would require quadric distances 
and the global minimization tends to be an n^3 approach.  I'm sure we could 
reduce that a bit, but it just seems a bit heavy handed.

By contrast just a little bit of extra work to estimate the position based on 
the difference in position of the previous two points (which every algorithm 
discussed seems to do anyway) doesn't seem that egregious.

The style of the code still assumes that we might want to adjust the 
aggressiveness of filtering ghosts and drops.  I agree it would be nice to be 
able to come up with a single value for each and hard code it, but I'm not 
willing to just assume that I can determine that value.  Also, for graceful 
degradation and repair, I would like to be able to code it so that those 
thresholds grow a little bit as a device drifts and then drop them again when 
calibration is run.


Also, if you're going to criticize code for complexity, I would recommend some 
comments that explain your code beyond "this is a generated table, don't change it".

Rafi

Re: [PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

On 11/08/2010 05:54 PM, Rafi Rubin wrote:

> On 11/08/2010 09:57 AM, Henrik Rydberg wrote:
>> Hi Rafi,
>>
>> what tree does this patch apply to?
> 
> It should apply to the torvalds/linux-2.6 master branch.


Odd, seems the patch was damaged somehow. Applies and compiles, thanks.

> The "complex" set of parameters was intended for more advanced users to give
> some feedback to help improve the driver.  Though given the lack of feedback, I
> guess you're right that there's little reason to expose them to users.


Sounds good. Would you agree that applying a modified version of the ubuntu
patch is the simplest way forward?

> The ubuntu 10.10 code does do filtering better than without filtering, but in
> trying it I've been seeing ghosts and have needed to calibrate multiple times
> per day (though that may be the result of a new screen being a little off).
> Furthermore while ripping out the filter code, you also ripped out single touch
> support for single touch firmwares, which apparently a few people still use.


Yes, thanks, I got a report regarding the single touch firmwares and was
planning to include it.


> Even without the ghost problem, it simply does not track as well.  The ntrig
> only reports every 8-24ms which is a long enough period to move quite a
> distance.


True, since it is using a greedy algorithm. This is what the exact in-kernel
tracking code is supposed to remedy. To be precise, the ubuntu version uses the
so-obtained assignment for filtering only - the tracking is still performed in
mtdev in userspace.

> In drawing up corner cases I realized that motion where two fingers
> are co-linear with the vector of motion require quite a bit of care to avoid
> perverting the tracking.


Yes, this is one example of why exact matching is needed.

> Greedily assigning matches based purely on distance
> can cause a flip.  Even global distance minimization is not reliable when we use
> linear distance as the cost.  A full analysis would require quadric distances
> and the global minimization tends to be an n^3 approach.  I'm sure we could
> reduce that a bit, but it just seems a bit heavy handed.


The patch that started this thread implements exact matching, which means
finding the optimal slot assignments that minimizes a measure of the distance of
all movements. The implementation is very fast, but still needs to be cut off at
some arbitrary number. Four seems to be a natural breakpoint. The fact that
matching scales badly is one of the major headaches, and the reason mtdev is
implemented in userspace. The middle-way proposed here is a balance that seems
to cater for existing hardware at the same time as expecting hardware to provide
their own tracking in the future.

> By contrast just a little bit of extra work to estimate the position based on
> the difference in position of the previous two points (which every algorithm
> discussed seems to do anyway) doesn't seem that egregious.


Using exact matching instead of greedy matching is what makes it work well. It
is very robust and parameter-free. On the eclectic side, one can certainly go
beyond that by optimizing for both position differences and speed differences
(maximum smoothness). However, I doubt it makes any difference on the
finger-tracking use case.

> The style of the code still assumes that we might want to adjust the
> aggressiveness of filtering ghosts and drops.  I agree it would be nice to be
> able to come up with a single value for each and hard code it, but I'm not
> willing to just assume that I can determine that value.


The ghost detection in the ubuntu version could probably be improved a bit, but
the biggest experience gain would probably come from automatic calibration.

> Also, for graceful
> degradation and repair, I would like to be able to code it so that those
> thresholds grow a little bit as a device drifts and then drop them again when
> calibration is run.


Tricky - perhaps a measure of the number of filtered ghosts could be used to
determine when it is time to recalibrate.

>
> Also, if you're going to criticize code for complexity, I would recommend some
> comments that explain your code beyond "this is a generated table, don't change
> it".


Hehe, the quote is actually wrong. ;-)

Of course you are right. More documentation is a good thing, and I will add more
of it. The code does at least refer to the generating program, and the commit
message tells where that program can be found. To discuss details, here is a
listing of some of that code:

/*
 * Combinatorial formulation
 *
 * x_ij = 1 if slot i and contact j are connected, zero otherwise
 *
 * sum_i x_ij <= 1 for all j; each contact picks at most one slot
 *
 * sum_j x_ij <= 1 for all i; each slot is picked by at most one contact
 *
 * sum_ij x_ij == min(nslot, npos); assign every contact possible
 *
 * Arrange x_ij as a bitmask; x_00 x_01 x_02.. x_10 x_11 x_12...
 *
 * Up to five slots, this is readily enumerable.
 */

static int illegal(int nslot, int npos, unsigned x)
{
	int i, j, sum;

	for (j = 0; j < npos; j++) {
		sum = 0;
		for (i = 0; i < nslot; i++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}
	for (i = 0; i < nslot; i++) {
		sum = 0;
		for (j = 0; j < npos; j++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}

	sum = bitcount(x);
	return sum != minval(nslot, npos);
}

static int generate_assignments(int nslot, int npos)
{
	static int ncol;
	unsigned x, nx = BITMASK(nslot * npos);
	int slots[SLOT_MAX];
	int i, n = 0;

	for (x = 0; x < nx; x++) {
		if (illegal(nslot, npos, x))
			continue;
		for (i = 0; i < nslot * npos; i++) {
			if (GETBIT(x, i)) {
				if (ncol++ % 16 == 0)
					printf("\n\t%d,", i);
				else
					printf(" %d,", i);
				n++;
			}
		}
		get_slots(slots, nslot, npos, x);
		for (i = 0; i < npos; i++) {
			if (ncol++ % 16 == 0)
				printf("\n\t%d,", slots[i]);
			else
				printf(" %d,", slots[i]);
			n++;
		}
	}

	return n;
}

For every (number of used slots, number of current contacts) pair, two
consecutive arrays of values are generated. The first contains the matrix
indices corresponding to a certain mapping from contacts to slots. The second
contains the actual slot assignment.

To find the optimal matching, one simply scans through the appropriate index
array, extracting the slot assignment corresponding to the minimum sum of matrix
elements. This process is combinatorial and in general scales much worse than
for instance the hungarian algorithm, but for small numbers, it can be
implemented with very good speed.

Cheers,
Henrik

Re: [PATCH] input: Introduce light-weight contact tracking

[Rafi Rubin]

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

> For every (number of used slots, number of current contacts) pair, two
> consecutive arrays of values are generated. The first contains the matrix
> indices corresponding to a certain mapping from contacts to slots. The second
> contains the actual slot assignment.
> 
> To find the optimal matching, one simply scans through the appropriate index
> array, extracting the slot assignment corresponding to the minimum sum of matrix
> elements. This process is combinatorial and in general scales much worse than
> for instance the hungarian algorithm, but for small numbers, it can be
> implemented with very good speed.

It occurs to me that it might be a good idea to restate our goals and assumptions.

Goals:
- - better filtering: ghosts and drops
- - reduced cost:	compute/energy
- - accuracy of tracking
- - maximize functionality
- - durability: I want a routine that will last


Assumptions:
- - contacts in an untracked incoming frame are spatially sorted
- - consistent ordering of contacts from frame to frame is far more common than a
change in ordering
- - typically upsets in ordering are small
- - we can focus matching to reduce the number of comparisons needed
- - we can not trust matching of static positions
- - we should not assume and hard code a limit on the number of contacts
- - the density of contacts is limited.
- - perfection may not be possible and is not necessarily insteresting
- - new tracks are relatively rare and the rate of appearance (particularly in a
small region) is likely to be small
- - new tracks are likely to start slow, but may not

So from my perspective, the first stage should just be a quick sanity check on
the incoming frame.  Where the contacts are in the same order we should pay a
constant time for each contact, so O(n).

The code I sent should consume contacts from two lists.  As long as they match,
it just pops the first element from each.  As long as the two frames have the
same tracks, the worst case ordering will still result in at worst O(n^2), and
with a bit of spatial filtering, that would be an extremely unlikely scenario.


The start of a new track is a bit different.  If we assume 0 starting velocity,
we can use the same regional matching and get the same O(n) in the common case
and O(n^2) when we fail to find a match.  This n is just the unmatched contacts
from the current frame and the remaining tracked contacts and unmatched from the
previous.

When we are concerned about tracks that start with fast moving contacts, we have
a bit more to work out.  We could expand the search area for unmatched contacts
in the previous frame, but that requires dangerous assumptions and may result in
incorrect assignments.  Just imagine a flattened X where the upper corners are
the first frame and the lower corners are the second.  Ignoring motion, you
would find two vertical tracks, even though the two tracks are actually crossing
diagonals.  With velocity compensation, we need to consider all combinations of
vectors from the previous two frames and match against the current.  So that
step is O(n^3).

While that n^3 is undesirable, I asked around and have been told that it would
be a poor choice to ignore fast "swipes".  Moreover its again very unlikely that
we will have to deal with large n since we're only talking about the rate of new
tracks starting.  We can imagine a group of people deliberately trying to make
it behave poorly and synchronizing touching a screen in 60 places all at once.
However, it would be hard to do so with all those fingers moving fast.  And of
course with a bit of filtering, we can easily keep that to localized problems
and treat them as many smaller n^3 problems.  The maximum density can't really
be all that high, and I would think the maximum for moving tracks would be quite
a bit lower.

The last tidbit I included is drop filtering.  When a track is lost, and then
new contacts come in later, we can go back to the list of those lost tracks and
try to find a match.  With assumptions for how far back we're willing to look,
we're still not talking about a lot of comparisons, and we only need to consider
two lists not three, so this step is still only going to be quadratic.  With
increasing uncertainty over time I thought it would be good to increase the
target ranges for aging lost tracks.  My approach there is purely intuitive and
I'd love any better ideas.


So that's why I selected the approach and data structures I used.  Now if you
can tell me the studio 17 is going to be the only device that will ever run
these routines that has more than 4 contacts and is not tracked, then sure,
screw it.  I have no reason to believe that is a good assumption.

Even if we do want to limit the code to 4 contacts, we still need some motion
estimation, particularly for the lower frame rate devices.


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

iQIcBAEBAgAGBQJM23v/AAoJEPILXytRLnK2nOEQAKKVrxP5ovGwm8hGOK5moYEn
XLw+jjHKd0zJIRuPTeKO8pWRY3HfN6OfqUEu38Agfyx0gbPv7QfXazCi8zY+Nihh
nfoQ2fsWFKYqGo+tKKgmijTi/aQ0VLBq6t1IejFbdslyAWLA7c3WDPAS+eiiGsfY
L9kFEvzFbaYrYZA7YmVHi5xp4nuH047mBsC9BxiKvqywPl86ZXPec4tq/yKkWjLu
MCqVW8mw7xJAqd+rie0VRCqYCXPJuciqkU6DFOMkTL6suxymBXPKtNT0kt3Sebcs
dwaCHLzH0AFhdPkb/NUJKJvZe5Qtc4p/Le9uKp0/wDvdnPaX7c8ETsC3TKWP2sQl
dy25litr2tXlbPI8O2q3qJeofqHGD5UyFvy6qgXpSDi+2q/rkbjYtAyWZW41xN+1
YlNHRAWppsrsOTeps7Zq2BkGeNQIgCOh0ErcSpldjYUZUgM0hRmJcGSsZmPS7aDR
XE4vBTpCDjHywN1ejG1rugWelz9Ck82redNNNfHk2IQf5Idf5oZCMvAeqESNGKg/
KJ+06+C4uckEh+PvKiBnekJNfDkBGAnt42XYfhkRhTMQP+BU5IhhWGgY75RMypFT
F5YyMwdKw0vzlC206LwiWim80tDbL4LNhOBOTkErCrB2/vP/YedGTGeItoUbHx3Y
SQ1QZhzUyZFYpWpo5uZB
=tZOo
-----END PGP SIGNATURE-----

Re: [PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

On 11/11/2010 06:15 AM, Rafi Rubin wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
>> For every (number of used slots, number of current contacts) pair, two
>> consecutive arrays of values are generated. The first contains the matrix
>> indices corresponding to a certain mapping from contacts to slots. The second
>> contains the actual slot assignment.
>>
>> To find the optimal matching, one simply scans through the appropriate index
>> array, extracting the slot assignment corresponding to the minimum sum of matrix
>> elements. This process is combinatorial and in general scales much worse than
>> for instance the hungarian algorithm, but for small numbers, it can be
>> implemented with very good speed.
> 
> It occurs to me that it might be a good idea to restate our goals and assumptions.


The main goal of my patch is to device a simple, stable, parameter-free matching
function that can be used in interrupt context. If you have such a function,
about a hundred lines of code, completes in a couple of hundred cycles, tested
and benchmarked in the mtdev framework, and which can do six fingers, I would be
happy to use that instead. Otherwise, I suggest we focus on this patch.

> So that's why I selected the approach and data structures I used.  Now if you
> can tell me the studio 17 is going to be the only device that will ever run
> these routines that has more than 4 contacts and is not tracked, then sure,
> screw it.  I have no reason to believe that is a good assumption.


The N-trig device is the only device in the kernel that requires special ghost
filtering. All other devices send reliable data, and either have fewer contacts,
handle their own tracking, or send all data to userspace. Future devices will
most likely have tracking capabilities, and even if they do not, protocol A and
mtdev handles that case. Thus, the question is really whether a new device would
produce unreliable contact data. I find that unlikely.


> Even if we do want to limit the code to 4 contacts, we still need some motion
> estimation, particularly for the lower frame rate devices.


Second-order methods for a device that does not even produce zeroth-order
contact data? As far as I know, the first-order tracking in mtdev has not
disappointed anyone yet, so your statement seems to need elaboration.

Henrik

Re: [PATCH] input: Introduce light-weight contact tracking

[Dmitry Torokhov]

On Thu, Nov 11, 2010 at 11:53:02AM +0100, Henrik Rydberg wrote:
> On 11/11/2010 06:15 AM, Rafi Rubin wrote:
> 
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> > 
> >> For every (number of used slots, number of current contacts) pair, two
> >> consecutive arrays of values are generated. The first contains the matrix
> >> indices corresponding to a certain mapping from contacts to slots. The second
> >> contains the actual slot assignment.
> >>
> >> To find the optimal matching, one simply scans through the appropriate index
> >> array, extracting the slot assignment corresponding to the minimum sum of matrix
> >> elements. This process is combinatorial and in general scales much worse than
> >> for instance the hungarian algorithm, but for small numbers, it can be
> >> implemented with very good speed.
> > 
> > It occurs to me that it might be a good idea to restate our goals and assumptions.
> 
> 
> The main goal of my patch is to device a simple, stable, parameter-free matching
> function that can be used in interrupt context. If you have such a function,
> about a hundred lines of code, completes in a couple of hundred cycles, tested
> and benchmarked in the mtdev framework, and which can do six fingers, I would be
> happy to use that instead. Otherwise, I suggest we focus on this patch.
> 
> > So that's why I selected the approach and data structures I used.  Now if you
> > can tell me the studio 17 is going to be the only device that will ever run
> > these routines that has more than 4 contacts and is not tracked, then sure,
> > screw it.  I have no reason to believe that is a good assumption.
> 
> 
> The N-trig device is the only device in the kernel that requires special ghost
> filtering. All other devices send reliable data, and either have fewer contacts,
> handle their own tracking, or send all data to userspace. Future devices will
> most likely have tracking capabilities, and even if they do not, protocol A and
> mtdev handles that case. Thus, the question is really whether a new device would
> produce unreliable contact data. I find that unlikely.
> 
> 
> > Even if we do want to limit the code to 4 contacts, we still need some motion
> > estimation, particularly for the lower frame rate devices.
> 
> 
> Second-order methods for a device that does not even produce zeroth-order
> contact data? As far as I know, the first-order tracking in mtdev has not
> disappointed anyone yet, so your statement seems to need elaboration.
> 

Guys, with the filters being purely in-kernel library-like solutions
(i.e they do not export any API/ABI visible to userspace I see no
problem with having several (well a couple, let's not get carried away)
filter algorithms available. Most of the drivers will probably use the
one that is limited to 4(?) fingers if it is indeed faster, and ones
that need to track more fingers and do not have help of the hardware
might employ the slower option. The only concern is that such drivers
might need to offload such tracking to a thread/workqueue.

-- 
Dmitry