From d44b4794c679141a08fd802475bb542ecf5b7c51 Mon Sep 17 00:00:00 2001 From: Henrik Rydberg Date: Thu, 6 Nov 2008 23:01:41 +0100 Subject: ok, fast (but not fastest) matcher in place, no check output... Signed-off-by: Henrik Rydberg --- Makefile | 15 ++- match/match.c | 326 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ match/match.h | 25 +++++ match/test.c | 40 +++++++ src/common.h | 3 +- src/hwdata.h | 1 - src/multitouch.c | 2 +- src/state.c | 72 +++++++++++- src/state.h | 3 +- 9 files changed, 473 insertions(+), 14 deletions(-) create mode 100644 match/match.c create mode 100644 match/match.h create mode 100644 match/test.c diff --git a/Makefile b/Makefile index bc5cc02..c805140 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,8 @@ LIBRARY = multitouch.so FDIS = 11-multitouch.fdi -MODULES = src +MODULES = match src + +o_match = match o_src = capabilities \ iobuffer \ @@ -31,13 +33,11 @@ OPTS = -O3 .PHONY: all clean .PRECIOUS: obj/%.o -all: $(OBJS) $(TLIB) $(TOBJ) - -test: $(TBIN) +all: $(OBJS) $(TLIB) $(TOBJ) $(TBIN) bin/%: obj/%.o @mkdir -p $(@D) - gcc $< $(OBJS) $(LIBS) -o $@ + gcc $< -o $@ $(TLIB): $(OBJS) @rm -f $(TLIB) @@ -62,3 +62,8 @@ install: $(TLIB) $(TFDI) install -d "$(DESTDIR)/$(DFDI)" install -m 755 $(TLIB) "$(DESTDIR)/$(DLIB)" install -m 644 $(TFDI) "$(DESTDIR)/$(DFDI)" + +test: + gcc $< $(OBJS) -o LINKTEST + +obj/match/test.o: match/match.c diff --git a/match/match.c b/match/match.c new file mode 100644 index 0000000..604faaf --- /dev/null +++ b/match/match.c @@ -0,0 +1,326 @@ +#include "match.h" +#include +#include + +/** + * MATLAB implementation of the hungarian algorithm (2008) + * + * modified by Henrik Rydberg (2008) + */ + +const float BIG_VALUE = 1e20; + +typedef unsigned short col_t; + +#define GETBIT2(m, row, col) ((m[col]>>row)&1U) +#define SETBIT2(m, row, col) (m[col]|=(1U<>x)&1U) +#define SETBIT(m, x) (m|=(1U< ncols) */ + { + dmin = ncols; + + for(col=0; col +#include +#include "match.c" + +#define ITS 1000000 + +int main(int argc,char* argv[]) +{ + // column-by-column matrix + float A[DIM2_FINGER]; + float x1[DIM_FINGER]={1,5,2,3,4,5,6,7,8}; + float y1[DIM_FINGER]={1,5,2,3,4,5.1,6,7,8}; + float x2[DIM_FINGER]={1.1,3,2,4,5,6,7,8}; + float y2[DIM_FINGER]={1,3,2,4,5,6,7,8}; + int index[DIM_FINGER]; + int n1 = 4; + int n2 = 7; + + int i, j; + + for (i = 0; i < n1; i++) { + for (j = 0; j < n2; j++) { + A[i + n1 * j] = + (x1[i] - x2[j]) * (x1[i] - x2[j]) + + (y1[i] - y2[j]) * (y1[i] - y2[j]); + } + } + + clock_t t1 = clock(); + for (i = 0; i < ITS; i++) + match_fingers(index, A, n1, n2); + clock_t t2 = clock(); + + printf("%lf matches per second\n", ITS * ((float)CLOCKS_PER_SEC / (t2 - t1))); + + for (i = 0; i < n1; i++) + printf("match[%d] = %d\n", i, index[i]); + + return 0; +} diff --git a/src/common.h b/src/common.h index 5a83f95..c57ae1a 100644 --- a/src/common.h +++ b/src/common.h @@ -7,6 +7,7 @@ #include #include #include +#include //#include //////////////////////////////////////////////////////// @@ -27,8 +28,6 @@ #define ABS_MT_POSITION_X 0x35 #define ABS_MT_POSITION_Y 0x36 -typedef int bool; - #define SYSCALL(call) while (((call) == -1) && (errno == EINTR)) //////////////////////////////////////////////////////// diff --git a/src/hwdata.h b/src/hwdata.h index 239e022..59cff0d 100644 --- a/src/hwdata.h +++ b/src/hwdata.h @@ -3,7 +3,6 @@ #include "common.h" -#define DIM_FINGER 16 #define DIM_BUTTON 3 #define MT_BUTTON_LEFT 0 diff --git a/src/multitouch.c b/src/multitouch.c index f6e3d05..21f3e1e 100644 --- a/src/multitouch.c +++ b/src/multitouch.c @@ -82,7 +82,7 @@ static void read_input(LocalDevicePtr local) if (local->fd >= 0) { while (read_synchronized_event(mt, local->fd)) { modify_state(&mt->ns, &mt->hw); - // and something in between here + output_state(&mt->ns); mt->os = mt->ns; } } diff --git a/src/state.c b/src/state.c index 46b7fef..fc3580d 100644 --- a/src/state.c +++ b/src/state.c @@ -1,4 +1,5 @@ #include "state.h" +#include /******************************************************/ @@ -9,11 +10,58 @@ void init_state(struct State *s) /******************************************************/ +inline int fincomp(const struct FingerState* a,const struct FingerState* b) +{ + return a->id - b->id; +} + +inline float dist2(const struct FingerData* a,const struct FingerData* b) +{ + float dx = a->position_x - b->position_x; + float dy = a->position_y - b->position_y; + + return dx * dx + dy * dy; +} + void modify_state(struct State *s, const struct HWData* hw) { - int i; - if (s->button[0] != hw->button[0]) - xf86Msg(X_INFO, "multitouch: button changed\n"); + float A[DIM2_FINGER], *row; + int id[DIM_FINGER], index[DIM_FINGER], i, j; + + for (j = 0; j < s->nfinger; j++) { + id[j] = s->finger[j].id; + row = A + hw->nfinger * j; + for (i = 0; i < hw->nfinger; i++) + row[i] = dist2(&hw->finger[i], &s->finger[j].hw); + } + + match_fingers(index, A, hw->nfinger, s->nfinger); + + s->nfinger = 0; + + /* update matched fingers */ + for (i = 0; i < hw->nfinger; i++) { + if ((j = index[i]) >= 0) { + s->finger[s->nfinger].id = id[j]; + s->finger[s->nfinger].hw = hw->finger[i]; + s->nfinger++; + } + } + + /* create new fingers */ + for (i = 0; i < hw->nfinger; i++) { + if (index[i] < 0) { + s->finger[s->nfinger].id = ++s->lastid; + s->finger[s->nfinger].hw = hw->finger[i]; + s->nfinger++; + } + } + + /* sort fingers in touching order */ + qsort(s->finger, s->nfinger, sizeof(struct FingerState), + (int (*)(const void*,const void*))fincomp); + + /* copy buttons */ for (i = 0; i < DIM_BUTTON; i++) s->button[i] = hw->button[i]; } @@ -23,9 +71,11 @@ void modify_state(struct State *s, const struct HWData* hw) const struct FingerState *find_finger(const struct State *s, int id) { int i; + for (i = 0; i < s->nfinger; i++) if (s->finger[i].id == id) - return s->finger+i; + return s->finger + i; + return NULL; } @@ -33,6 +83,20 @@ const struct FingerState *find_finger(const struct State *s, int id) void output_state(const struct State *s) { + int i; + printf("buttons: %d%d%d\n", s->button[0], s->button[1], s->button[2]); + printf("fingers: %d\n", s->nfinger); + for (i = 0; i < s->nfinger; i++) { + printf(" %+02d %+05d:%+05d +%05d:%+05d %+05d %+05d:%+05d\n", + s->finger[i].id, + s->finger[i].hw.touch_major, + s->finger[i].hw.touch_minor, + s->finger[i].hw.width_major, + s->finger[i].hw.width_minor, + s->finger[i].hw.orientation, + s->finger[i].hw.position_x, + s->finger[i].hw.position_y); + } } /******************************************************/ diff --git a/src/state.h b/src/state.h index 9c36617..8b41920 100644 --- a/src/state.h +++ b/src/state.h @@ -14,7 +14,8 @@ struct FingerState { struct State { struct FingerState finger[DIM_FINGER]; - int nfinger, button[DIM_BUTTON]; + int button[DIM_BUTTON]; + int nfinger, lastid; }; //////////////////////////////////////////////////////// -- cgit v1.2.3