src/events/SDL_gesture.c
author Jim Grandpre <jim.tla@gmail.com>
Fri, 09 Jul 2010 00:50:40 -0700
changeset 4658 454385d76845
parent 4657 eed063a0bf5b
child 4659 063b9455bd1a
permissions -rw-r--r--
Moved $1 Gestures into the SDL Library
jim@4657
     1
/*
jim@4657
     2
    SDL - Simple DirectMedia Layer
jim@4657
     3
    Copyright (C) 1997-2010 Sam Lantinga
jim@4657
     4
jim@4657
     5
    This library is free software; you can redistribute it and/or
jim@4657
     6
    modify it under the terms of the GNU Lesser General Public
jim@4657
     7
    License as published by the Free Software Foundation; either
jim@4657
     8
    version 2.1 of the License, or (at your option) any later version.
jim@4657
     9
jim@4657
    10
    This library is distributed in the hope that it will be useful,
jim@4657
    11
    but WITHOUT ANY WARRANTY; without even the implied warranty of
jim@4657
    12
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
jim@4657
    13
    Lesser General Public License for more details.
jim@4657
    14
jim@4657
    15
    You should have received a copy of the GNU Lesser General Public
jim@4657
    16
    License along with this library; if not, write to the Free Software
jim@4657
    17
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
jim@4657
    18
jim@4657
    19
    Sam Lantinga
jim@4657
    20
    slouken@libsdl.org
jim@4657
    21
*/
jim@4657
    22
#include "SDL_config.h"
jim@4657
    23
jim@4657
    24
/* General mouse handling code for SDL */
jim@4657
    25
jim@4657
    26
#include "SDL_events.h"
jim@4657
    27
#include "SDL_events_c.h"
jim@4657
    28
#include "SDL_gesture_c.h"
jim@4657
    29
jim@4657
    30
//TODO: Replace with malloc
jim@4657
    31
#define MAXFINGERS 3
jim@4657
    32
#define MAXTOUCHES 2
jim@4658
    33
#define MAXTEMPLATES 4
jim@4658
    34
#define MAXPATHSIZE 1024
jim@4658
    35
jim@4658
    36
#define DOLLARNPOINTS 64
jim@4658
    37
#define DOLLARSIZE 256
jim@4658
    38
jim@4658
    39
//PHI = ((sqrt(5)-1)/2)
jim@4658
    40
#define PHI 0.618033989 
jim@4657
    41
jim@4657
    42
typedef struct {
jim@4657
    43
  float x,y;
jim@4657
    44
} Point;
jim@4657
    45
jim@4657
    46
jim@4657
    47
typedef struct {
jim@4657
    48
  Point p;
jim@4657
    49
  float pressure;
jim@4657
    50
  int id;
jim@4657
    51
} Finger;
jim@4657
    52
jim@4658
    53
jim@4658
    54
typedef struct {
jim@4658
    55
  float length;
jim@4658
    56
  
jim@4658
    57
  int numPoints;
jim@4658
    58
  Point p[MAXPATHSIZE];
jim@4658
    59
} DollarPath;
jim@4658
    60
jim@4658
    61
jim@4657
    62
typedef struct {
jim@4657
    63
  Finger f;
jim@4657
    64
  Point cv;
jim@4657
    65
  float dtheta,dDist;
jim@4658
    66
  DollarPath dollarPath;
jim@4657
    67
} TouchPoint;
jim@4657
    68
jim@4657
    69
jim@4657
    70
typedef struct {
jim@4657
    71
  int id;
jim@4657
    72
  Point res;
jim@4657
    73
  Point centroid;
jim@4657
    74
  TouchPoint gestureLast[MAXFINGERS];
jim@4657
    75
  int numDownFingers;
jim@4658
    76
jim@4658
    77
  int numDollarTemplates;
jim@4658
    78
  Point dollarTemplate[MAXTEMPLATES][DOLLARNPOINTS];
jim@4657
    79
} GestureTouch;
jim@4657
    80
jim@4657
    81
GestureTouch gestureTouch[MAXTOUCHES];
jim@4657
    82
int numGestureTouches = 0;
jim@4658
    83
jim@4658
    84
float dollarDifference(Point* points,Point* templ,float ang) {
jim@4658
    85
  //  Point p[DOLLARNPOINTS];
jim@4658
    86
  float dist = 0;
jim@4658
    87
  Point p;
jim@4658
    88
  int i;
jim@4658
    89
  for(i = 0; i < DOLLARNPOINTS; i++) {
jim@4658
    90
    p.x = points[i].x * cos(ang) - points[i].y * sin(ang);
jim@4658
    91
    p.y = points[i].x * sin(ang) + points[i].y * cos(ang);
jim@4658
    92
    dist += sqrt((p.x-templ[i].x)*(p.x-templ[i].x)+
jim@4658
    93
		 (p.y-templ[i].y)*(p.y-templ[i].y));
jim@4658
    94
  }
jim@4658
    95
  return dist/DOLLARNPOINTS;
jim@4658
    96
  
jim@4658
    97
}
jim@4658
    98
jim@4658
    99
float bestDollarDifference(Point* points,Point* templ) {
jim@4658
   100
  //------------BEGIN DOLLAR BLACKBOX----------------//
jim@4658
   101
  //-TRANSLATED DIRECTLY FROM PSUDEO-CODE AVAILABLE AT-//
jim@4658
   102
  //-"http://depts.washington.edu/aimgroup/proj/dollar/"-//
jim@4658
   103
  float ta = -M_PI/4;
jim@4658
   104
  float tb = M_PI/4;
jim@4658
   105
  float dt = M_PI/90;
jim@4658
   106
  float x1 = PHI*ta + (1-PHI)*tb;
jim@4658
   107
  float f1 = dollarDifference(points,templ,x1);
jim@4658
   108
  float x2 = (1-PHI)*ta + PHI*tb;
jim@4658
   109
  float f2 = dollarDifference(points,templ,x2);
jim@4658
   110
  while(abs(ta-tb) > dt) {
jim@4658
   111
    if(f1 < f2) {
jim@4658
   112
      tb = x2;
jim@4658
   113
      x2 = x1;
jim@4658
   114
      f2 = f1;
jim@4658
   115
      x1 = PHI*ta + (1-PHI)*tb;
jim@4658
   116
      f1 = dollarDifference(points,templ,x1);
jim@4658
   117
    }
jim@4658
   118
    else {
jim@4658
   119
      ta = x1;
jim@4658
   120
      x1 = x2;
jim@4658
   121
      f1 = f2;
jim@4658
   122
      x2 = (1-PHI)*ta + PHI*tb;
jim@4658
   123
      f2 = dollarDifference(points,templ,x2);
jim@4658
   124
    }
jim@4658
   125
  }
jim@4658
   126
  /*
jim@4658
   127
  if(f1 <= f2)
jim@4658
   128
    printf("Min angle (x1): %f\n",x1);
jim@4658
   129
  else if(f1 >  f2)
jim@4658
   130
    printf("Min angle (x2): %f\n",x2);
jim@4658
   131
  */
jim@4658
   132
  return SDL_min(f1,f2);  
jim@4658
   133
}
jim@4658
   134
jim@4658
   135
float dollarRecognize(DollarPath path,int *bestTempl,GestureTouch* touch) {
jim@4658
   136
jim@4658
   137
  Point points[DOLLARNPOINTS];
jim@4658
   138
  int numPoints = dollarNormalize(path,points);
jim@4658
   139
  int i;
jim@4658
   140
 
jim@4658
   141
  int bestDiff = 10000;
jim@4658
   142
  *bestTempl = -1;
jim@4658
   143
  for(i = 0;i < touch->numDollarTemplates;i++) {
jim@4658
   144
    int diff = bestDollarDifference(points,touch->dollarTemplate[i]);
jim@4658
   145
    if(diff < bestDiff) {bestDiff = diff; *bestTempl = i;}
jim@4658
   146
  }
jim@4658
   147
  return bestDiff;
jim@4658
   148
}
jim@4658
   149
jim@4658
   150
//DollarPath contains raw points, plus (possibly) the calculated length
jim@4658
   151
int dollarNormalize(DollarPath path,Point *points) {
jim@4658
   152
  int i;
jim@4658
   153
  //Calculate length if it hasn't already been done
jim@4658
   154
  if(path.length <= 0) {
jim@4658
   155
    for(i=1;i<path.numPoints;i++) {
jim@4658
   156
      float dx = path.p[i  ].x - 
jim@4658
   157
	         path.p[i-1].x;
jim@4658
   158
      float dy = path.p[i  ].y - 
jim@4658
   159
	         path.p[i-1].y;
jim@4658
   160
      path.length += sqrt(dx*dx+dy*dy);
jim@4658
   161
    }
jim@4658
   162
  }
jim@4658
   163
jim@4658
   164
jim@4658
   165
  //Resample
jim@4658
   166
  float interval = path.length/(DOLLARNPOINTS - 1);
jim@4658
   167
  float dist = 0;
jim@4658
   168
jim@4658
   169
  int numPoints = 0;
jim@4658
   170
  Point centroid; centroid.x = 0;centroid.y = 0;
jim@4658
   171
  //printf("(%f,%f)\n",path.p[path.numPoints-1].x,path.p[path.numPoints-1].y);
jim@4658
   172
  for(i = 1;i < path.numPoints;i++) {
jim@4658
   173
    float d = sqrt((path.p[i-1].x-path.p[i].x)*(path.p[i-1].x-path.p[i].x)+
jim@4658
   174
		   (path.p[i-1].y-path.p[i].y)*(path.p[i-1].y-path.p[i].y));
jim@4658
   175
    //printf("d = %f dist = %f/%f\n",d,dist,interval);
jim@4658
   176
    while(dist + d > interval) {
jim@4658
   177
      points[numPoints].x = path.p[i-1].x + 
jim@4658
   178
	((interval-dist)/d)*(path.p[i].x-path.p[i-1].x);
jim@4658
   179
      points[numPoints].y = path.p[i-1].y + 
jim@4658
   180
	((interval-dist)/d)*(path.p[i].y-path.p[i-1].y);
jim@4658
   181
      centroid.x += points[numPoints].x;
jim@4658
   182
      centroid.y += points[numPoints].y;
jim@4658
   183
      numPoints++;
jim@4658
   184
jim@4658
   185
      dist -= interval;
jim@4658
   186
    }
jim@4658
   187
    dist += d;
jim@4658
   188
  }
jim@4658
   189
  if(numPoints < 1) return 0;
jim@4658
   190
  centroid.x /= numPoints;
jim@4658
   191
  centroid.y /= numPoints;
jim@4658
   192
 
jim@4658
   193
  //printf("Centroid (%f,%f)",centroid.x,centroid.y);
jim@4658
   194
  //Rotate Points so point 0 is left of centroid and solve for the bounding box
jim@4658
   195
  float xmin,xmax,ymin,ymax;
jim@4658
   196
  xmin = centroid.x;
jim@4658
   197
  xmax = centroid.x;
jim@4658
   198
  ymin = centroid.y;
jim@4658
   199
  ymax = centroid.y;
jim@4658
   200
  
jim@4658
   201
  float ang = atan2(centroid.y - points[0].y,
jim@4658
   202
		    centroid.x - points[0].x);
jim@4658
   203
jim@4658
   204
  for(i = 0;i<numPoints;i++) {					       
jim@4658
   205
    float px = points[i].x;
jim@4658
   206
    float py = points[i].y;
jim@4658
   207
    points[i].x = (px - centroid.x)*cos(ang) - 
jim@4658
   208
                  (py - centroid.y)*sin(ang) + centroid.x;
jim@4658
   209
    points[i].y = (px - centroid.x)*sin(ang) + 
jim@4658
   210
                  (py - centroid.y)*cos(ang) + centroid.y;
jim@4658
   211
jim@4658
   212
jim@4658
   213
    if(points[i].x < xmin) xmin = points[i].x;
jim@4658
   214
    if(points[i].x > xmax) xmax = points[i].x; 
jim@4658
   215
    if(points[i].y < ymin) ymin = points[i].y;
jim@4658
   216
    if(points[i].y > ymax) ymax = points[i].y;
jim@4658
   217
  }
jim@4658
   218
jim@4658
   219
  //Scale points to DOLLARSIZE, and translate to the origin
jim@4658
   220
  float w = xmax-xmin;
jim@4658
   221
  float h = ymax-ymin;
jim@4658
   222
jim@4658
   223
  for(i=0;i<numPoints;i++) {
jim@4658
   224
    points[i].x = (points[i].x - centroid.x)*DOLLARSIZE/w;
jim@4658
   225
    points[i].y = (points[i].y - centroid.y)*DOLLARSIZE/h;
jim@4658
   226
  }  
jim@4658
   227
  return numPoints;
jim@4658
   228
}
jim@4658
   229
jim@4657
   230
int SDL_GestureAddTouch(SDL_Touch* touch) { 
jim@4657
   231
  if(numGestureTouches >= MAXTOUCHES) return -1;
jim@4657
   232
  
jim@4657
   233
  gestureTouch[numGestureTouches].res.x = touch->xres;
jim@4657
   234
  gestureTouch[numGestureTouches].res.y = touch->yres;
jim@4657
   235
  gestureTouch[numGestureTouches].numDownFingers = 0;
jim@4657
   236
jim@4657
   237
  gestureTouch[numGestureTouches].res.x = touch->xres;
jim@4657
   238
  gestureTouch[numGestureTouches].id = touch->id;
jim@4657
   239
jim@4658
   240
  gestureTouch[numGestureTouches].numDollarTemplates = 0;
jim@4658
   241
jim@4657
   242
  numGestureTouches++;
jim@4657
   243
  return 0;
jim@4657
   244
}
jim@4657
   245
jim@4657
   246
GestureTouch * SDL_GetGestureTouch(int id) {
jim@4657
   247
  int i;
jim@4657
   248
  for(i = 0;i < numGestureTouches; i++) {
jim@4657
   249
    //printf("%i ?= %i\n",gestureTouch[i].id,id);
jim@4657
   250
    if(gestureTouch[i].id == id) return &gestureTouch[i];
jim@4657
   251
  }
jim@4657
   252
  return NULL;
jim@4657
   253
}
jim@4657
   254
jim@4657
   255
int SDL_SendGestureMulti(GestureTouch* touch,float dTheta,float dDist) {
jim@4657
   256
  SDL_Event event;
jim@4657
   257
  event.mgesture.type = SDL_MULTIGESTURE;
jim@4657
   258
  event.mgesture.touchId = touch->id;
jim@4657
   259
  event.mgesture.x = touch->centroid.x;
jim@4657
   260
  event.mgesture.y = touch->centroid.y;
jim@4657
   261
  event.mgesture.dTheta = dTheta;
jim@4657
   262
  event.mgesture.dDist = dDist;  
jim@4657
   263
  return SDL_PushEvent(&event) > 0;
jim@4657
   264
}
jim@4657
   265
jim@4658
   266
int SDL_SendGestureDollar(GestureTouch* touch,int gestureId,float error) {
jim@4658
   267
  SDL_Event event;
jim@4658
   268
  event.dgesture.type = SDL_DOLLARGESTURE;
jim@4658
   269
  event.dgesture.touchId = touch->id;
jim@4658
   270
  /*
jim@4658
   271
    //TODO: Add this to give location of gesture?
jim@4658
   272
  event.mgesture.x = touch->centroid.x;
jim@4658
   273
  event.mgesture.y = touch->centroid.y;
jim@4658
   274
  */
jim@4658
   275
  event.dgesture.gestureId = gestureId;
jim@4658
   276
  event.dgesture.error = error;  
jim@4658
   277
  return SDL_PushEvent(&event) > 0;
jim@4658
   278
}
jim@4658
   279
jim@4657
   280
void SDL_GestureProcessEvent(SDL_Event* event)
jim@4657
   281
{
jim@4657
   282
  if(event->type == SDL_FINGERMOTION || 
jim@4657
   283
     event->type == SDL_FINGERDOWN ||
jim@4657
   284
     event->type == SDL_FINGERUP) {
jim@4657
   285
    GestureTouch* inTouch = SDL_GetGestureTouch(event->tfinger.touchId);
jim@4657
   286
jim@4657
   287
    //Shouldn't be possible
jim@4657
   288
    if(inTouch == NULL) return;
jim@4657
   289
    
jim@4657
   290
    
jim@4657
   291
    float x = ((float)event->tfinger.x)/inTouch->res.x;
jim@4657
   292
    float y = ((float)event->tfinger.y)/inTouch->res.y;
jim@4657
   293
    int j,empty = -1;
jim@4657
   294
    
jim@4657
   295
    for(j = 0;j<inTouch->numDownFingers;j++) {
jim@4657
   296
      if(inTouch->gestureLast[j].f.id != event->tfinger.fingerId) continue;
jim@4657
   297
jim@4657
   298
      if(event->type == SDL_FINGERUP) {
jim@4657
   299
	inTouch->numDownFingers--;
jim@4658
   300
jim@4658
   301
	int bestTempl;
jim@4658
   302
	float error;
jim@4658
   303
	error = dollarRecognize(inTouch->gestureLast[j].dollarPath,
jim@4658
   304
				&bestTempl,inTouch);
jim@4658
   305
	if(bestTempl >= 0){
jim@4658
   306
	  //Send Event
jim@4658
   307
	  int gestureId = 0; //?
jim@4658
   308
	  SDL_SendGestureDollar(inTouch->id,gestureId,error);
jim@4658
   309
jim@4658
   310
jim@4658
   311
	  printf("Dollar error: %f\n",error);
jim@4658
   312
	}
jim@4658
   313
jim@4657
   314
	inTouch->gestureLast[j] = inTouch->gestureLast[inTouch->numDownFingers];
jim@4657
   315
	break;
jim@4657
   316
      }
jim@4657
   317
      else {
jim@4657
   318
	float dx = x - inTouch->gestureLast[j].f.p.x;
jim@4657
   319
	float dy = y - inTouch->gestureLast[j].f.p.y;
jim@4658
   320
	DollarPath* path = &inTouch->gestureLast[j].dollarPath;
jim@4658
   321
	if(path->numPoints < MAXPATHSIZE) {
jim@4658
   322
	  path->p[path->numPoints].x = x;
jim@4658
   323
	  path->p[path->numPoints].y = y;
jim@4658
   324
	  path->length += sqrt(dx*dx + dy*dy);
jim@4658
   325
	  path->numPoints++;
jim@4658
   326
	}
jim@4658
   327
jim@4658
   328
jim@4657
   329
	inTouch->centroid.x += dx/inTouch->numDownFingers;
jim@4657
   330
	inTouch->centroid.y += dy/inTouch->numDownFingers;    
jim@4657
   331
	if(inTouch->numDownFingers > 1) {
jim@4657
   332
	  Point lv; //Vector from centroid to last x,y position
jim@4657
   333
	  Point v; //Vector from centroid to current x,y position
jim@4657
   334
	  lv = inTouch->gestureLast[j].cv;
jim@4657
   335
	  float lDist = sqrt(lv.x*lv.x + lv.y*lv.y);
jim@4657
   336
	  //printf("lDist = %f\n",lDist);
jim@4657
   337
	  v.x = x - inTouch->centroid.x;
jim@4657
   338
	  v.y = y - inTouch->centroid.y;
jim@4657
   339
	  inTouch->gestureLast[j].cv = v;
jim@4657
   340
	  float Dist = sqrt(v.x*v.x+v.y*v.y);
jim@4657
   341
	  // cos(dTheta) = (v . lv)/(|v| * |lv|)
jim@4657
   342
	  
jim@4657
   343
	  //Normalize Vectors to simplify angle calculation
jim@4657
   344
	  lv.x/=lDist;
jim@4657
   345
	  lv.y/=lDist;
jim@4657
   346
	  v.x/=Dist;
jim@4657
   347
	  v.y/=Dist;
jim@4657
   348
	  float dtheta = atan2(lv.x*v.y - lv.y*v.x,lv.x*v.x + lv.y*v.y);
jim@4657
   349
	  
jim@4657
   350
	  float dDist = (Dist - lDist);
jim@4657
   351
	  if(lDist == 0) {dDist = 0;dtheta = 0;} //To avoid impossible values
jim@4657
   352
	  inTouch->gestureLast[j].dDist = dDist;
jim@4657
   353
	  inTouch->gestureLast[j].dtheta = dtheta;
jim@4657
   354
	  
jim@4657
   355
	  //printf("dDist = %f, dTheta = %f\n",dDist,dtheta);
jim@4657
   356
	  //gdtheta = gdtheta*.9 + dtheta*.1;
jim@4657
   357
	  //gdDist  =  gdDist*.9 +  dDist*.1
jim@4657
   358
	  //knob.r += dDist/numDownFingers;
jim@4657
   359
	  //knob.ang += dtheta;
jim@4657
   360
	  //printf("thetaSum = %f, distSum = %f\n",gdtheta,gdDist);
jim@4657
   361
	  //printf("id: %i dTheta = %f, dDist = %f\n",j,dtheta,dDist);
jim@4657
   362
	  SDL_SendGestureMulti(inTouch,dtheta,dDist);
jim@4657
   363
	}
jim@4657
   364
	else {
jim@4657
   365
	  inTouch->gestureLast[j].dDist = 0;
jim@4657
   366
	  inTouch->gestureLast[j].dtheta = 0;
jim@4657
   367
	  inTouch->gestureLast[j].cv.x = 0;
jim@4657
   368
	  inTouch->gestureLast[j].cv.y = 0;
jim@4657
   369
	}
jim@4657
   370
	inTouch->gestureLast[j].f.p.x = x;
jim@4657
   371
	inTouch->gestureLast[j].f.p.y = y;
jim@4657
   372
	break;
jim@4657
   373
	//pressure?
jim@4657
   374
      }      
jim@4657
   375
    }
jim@4657
   376
    
jim@4657
   377
    if(j == inTouch->numDownFingers) {
jim@4657
   378
      //printf("Finger Down!!!\n");
jim@4657
   379
      inTouch->numDownFingers++;
jim@4657
   380
      inTouch->centroid.x = (inTouch->centroid.x*(inTouch->numDownFingers - 1)+ 
jim@4657
   381
			     x)/inTouch->numDownFingers;
jim@4657
   382
      inTouch->centroid.y = (inTouch->centroid.y*(inTouch->numDownFingers - 1)+
jim@4657
   383
			     y)/inTouch->numDownFingers;
jim@4657
   384
      
jim@4657
   385
      inTouch->gestureLast[j].f.id = event->tfinger.fingerId;
jim@4657
   386
      inTouch->gestureLast[j].f.p.x  = x;
jim@4657
   387
      inTouch->gestureLast[j].f.p.y  = y;	
jim@4657
   388
      inTouch->gestureLast[j].cv.x = 0;
jim@4657
   389
      inTouch->gestureLast[j].cv.y = 0;
jim@4658
   390
jim@4658
   391
      inTouch->gestureLast[j].dollarPath.length = 0;
jim@4658
   392
      inTouch->gestureLast[j].dollarPath.p[0].x = x;
jim@4658
   393
      inTouch->gestureLast[j].dollarPath.p[0].y = y;
jim@4658
   394
      inTouch->gestureLast[j].dollarPath.numPoints = 1;
jim@4657
   395
    }
jim@4657
   396
  }
jim@4657
   397
}  
jim@4657
   398
  
jim@4657
   399
  /* vi: set ts=4 sw=4 expandtab: */
jim@4657
   400