Multi-touch tracking
A method of tracking multiple touches over time on a touch sensor, for example a capacitive touch screen. The method analyzes first and second touch data sets from adjacent first and second time frames. First, the touch data sets are analyzed to determine the closest touch in the second time frame to each of the touches in the first time frame, and calculating the separation between each such pair of touches. Then, starting with the pair of touches having the smallest separation, each pair is validated until a pairing is attempted between touches for which the touch in the second time frame has already been paired. At this point, the as-yet unpaired touches from the first and second touch data sets are re-processed by re-applying the computations but only including the as-yet unpaired touches. This re-processing is iterated until no further pairings need to be made. The method avoids complex algebra and floating point operations, and has little memory requirement. As such it is ideally suited to implementation on a microcontroller.
1. A method comprising:
determining, using one or more circuits, a first set of provisional pairings, each provisional pairing of the first set of provisional pairings comprising coordinates from a first set of coordinates and coordinates from a second set of coordinates, the first set of coordinates and the second set of coordinates corresponding to a plurality of touches detected by a touch sensor;
calculating a plurality of distances, each distance corresponding to a provisional pairing of the first set of provisional pairings;
validating, using the one or more circuits, a first provisional pairing of the first set of provisional pairings based on calculating the plurality of distances, the first provisional pairing comprising a first coordinate of the second set of coordinates;
determining, using the one or more circuits, that a second provisional pairing of the first set of provisional pairings is not valid in response to determining that:
the second provisional pairing comprises the same first coordinate as the first provisional pairing; and
the first provisional pairing has been validated; and
in response to determining that the second provisional pairing of the first set of provisional pairings is not valid, determining, using the one or more circuits, a second set of provisional pairings, each provisional pairing of the second set of provisional pairings comprising coordinates from the first set of coordinates and coordinates from the second set of coordinates.
2. The method of claim 1 , wherein validating the first provisional pairing comprises determining that a distance of the plurality of distances associated with the coordinates comprised by the first provisional pairing is less than a threshold.
3. The method of claim 1 , wherein the first set of coordinates correspond to a first time frame and the second set of coordinates correspond to a second time frame, the second time frame occurring after the first time frame.
4. The method of claim 1 , wherein each of the one or more circuits comprises one or more of the following:
a processor; and
a controller.
5. The method of claim 1 , wherein determining the second set of provisional pairings comprises determining the second set of provisional pairings such that the second set of provisional pairings do not include coordinates from the first provisional pairing.
6. The method of claim 1 , further comprising:
validating a third provisional pairing, the third provisional pairing included in the second set of provisional pairings;
identifying a gesture in response to validating the first provisional pairing and validating the third provisional pairing.
7. A system comprising:
a substrate;
a touch sensor disposed underneath the substrate, the touch sensor comprising a plurality of electrodes;
one or more circuits configured to:
determine a first set of provisional pairings, each provisional pairing of the first set of provisional pairings comprising coordinates from a first set of coordinates and coordinates from a second set of coordinates, the first set of coordinates and the second set of coordinates corresponding to a plurality of touches detected by the touch sensor;
calculate a plurality of distances, each distance corresponding to a provisional pairing, of the first set of provisional pairings;
validate a first provisional pairing of the first set of provisional pairings based on calculating the plurality of distances, the first provisional pairing comprising a first coordinate of the second set of coordinates;
determine that a second provisional pairing of the first set of provisional pairings is not valid in response to determining that:
the second provisional pairing comprises the same first coordinate as the first provisional pairing; and
the first provisional pairing has been validated; and
in response to determining that the second provisional pairing of the first set of provisional pairings is not valid, determine a second set of provisional pairings, each provisional pairing of the second set of provisional pairings comprising coordinates from the first set of coordinates and coordinates from the second set of coordinates.
8. The system of claim 7 , wherein the one or more circuits are configured to validate the first provisional pairing by determining that a distance of the plurality of distances associated with the coordinates comprised by the first provisional pairing is less than a threshold.
9. The system of claim 7 , wherein the first set of coordinates correspond to a first time frame and the second set of coordinates correspond to a second time frame, the second time frame occurring after the first time frame.
10. The system of claim 7 , wherein each of the one or more circuits comprises one or more of the following:
a processor; and
a controller.
11. The system of claim 7 , wherein the one or more circuits are configured to determine the second set of provisional pairings such that the second set of provisional pairings do not include coordinates from the first provisional pairing.
12. The system of claim 7 :
wherein the one or more circuits are further configured to validate a third provisional pairing, the third provisional pairing included in the second set of provisional pairings; and
further comprising a processor configured to identify a gesture in response to the one or more circuits validating the first provisional pairing and validating the third provisional pairing.
13. One or more circuits configured to:
determine a first set of provisional pairings, each provisional pairing of the first set of provisional pairings comprising coordinates from a first set of coordinates and coordinates from a second set of coordinates, the first set of coordinates and the second set of coordinates corresponding to a plurality of touches detected by a touch sensor;
calculate a plurality of distances, each distance corresponding to a provisional pairing of the first set of provisional pairings;
validate a first provisional pairing of the first set of provisional pairings based on calculating the plurality of distances, the first provisional pairing comprising a first coordinate of the second set of coordinates;
determine that a second provisional pairing of the first set of provisional pairings is not valid in response to determining that:
the second provisional pairing comprises the same first coordinate as the first provisional pairing; and
the first provisional pairing has been validated; and
in response to determining that the second provisional pairing of the first set of provisional pairings is not valid, determine a second set of provisional pairings, each provisional pairing of the second set of provisional pairings comprising coordinates from the first set of coordinates and coordinates from the second set of coordinates.
14. The one or more circuits of claim 13 , wherein the one or more circuits are configured to validate the first provisional pairing by determining that a distance of the plurality of distances associated with the coordinates comprised by the first provisional pairing is less than a threshold.
15. The one or more circuits of claim 13 , wherein the first set of coordinates correspond to a first time frame and the second set of coordinates correspond to a second time frame, the second time frame occurring after the first time frame.
16. The one or more circuits of claim 13 , wherein the one or more circuits are configured to determine second set of provisional pairings such that the second set of provisional pairings do not include coordinates from the first provisional pairing.
17. The one or more circuits of claim 13 , wherein the one or more circuits are further configured to:
validate a third provisional pairing, the third provisional pairing included in the second set of provisional pairings; and
identify a gesture in response to validating the first provisional pairing and validating the third provisional pairing.