src/events/SDL_gesture.c
author Jim Grandpre <jim.tla@gmail.com>
Fri, 16 Jul 2010 20:53:44 -0400
changeset 4665 c2493813a2f4
parent 4664 317a151b79ad
parent 4663 56a2d70de945
child 4678 f8431f66613d
permissions -rw-r--r--
Merged changes
     1 /*
     2     SDL - Simple DirectMedia Layer
     3     Copyright (C) 1997-2010 Sam Lantinga
     4 
     5     This library is free software; you can redistribute it and/or
     6     modify it under the terms of the GNU Lesser General Public
     7     License as published by the Free Software Foundation; either
     8     version 2.1 of the License, or (at your option) any later version.
     9 
    10     This library is distributed in the hope that it will be useful,
    11     but WITHOUT ANY WARRANTY; without even the implied warranty of
    12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    13     Lesser General Public License for more details.
    14 
    15     You should have received a copy of the GNU Lesser General Public
    16     License along with this library; if not, write to the Free Software    Founation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
    17 
    18     Sam Lantinga
    19     slouken@libsdl.org
    20 */
    21 #include "SDL_config.h"
    22 
    23 /* General mouse handling code for SDL */
    24 
    25 #include "SDL_events.h"
    26 #include "SDL_events_c.h"
    27 #include "SDL_gesture_c.h"
    28 
    29 //TODO: Replace with malloc
    30 #define MAXFINGERS 3
    31 #define MAXTOUCHES 2
    32 #define MAXTEMPLATES 4
    33 #define MAXPATHSIZE 1024
    34 
    35 #define DOLLARNPOINTS 64
    36 #define DOLLARSIZE 256
    37 
    38 //PHI = ((sqrt(5)-1)/2)
    39 #define PHI 0.618033989 
    40 
    41 typedef struct {
    42   float x,y;
    43 } Point;
    44 
    45 
    46 typedef struct {
    47   Point p;
    48   float pressure;
    49   int id;
    50 } Finger;
    51 
    52 
    53 typedef struct {
    54   float length;
    55   
    56   int numPoints;
    57   Point p[MAXPATHSIZE];
    58 } DollarPath;
    59 
    60 
    61 typedef struct {
    62   Finger f;
    63   Point cv;
    64   float dtheta,dDist;
    65   DollarPath dollarPath;
    66 } TouchPoint;
    67 
    68 typedef struct {
    69   Point path[DOLLARNPOINTS];
    70   unsigned long hash;
    71 } DollarTemplate;
    72 
    73 typedef struct {
    74   int id;
    75   Point res;
    76   Point centroid;
    77   TouchPoint gestureLast[MAXFINGERS];
    78   int numDownFingers;
    79 
    80   int numDollarTemplates;
    81   DollarTemplate dollarTemplate[MAXTEMPLATES];
    82 
    83   SDL_bool recording;
    84 } GestureTouch;
    85 
    86 GestureTouch gestureTouch[MAXTOUCHES];
    87 int numGestureTouches = 0;
    88 SDL_bool recordAll;
    89 
    90 int SDL_RecordGesture(int touchId) {
    91   int i;
    92   if(touchId < 0) recordAll = SDL_TRUE;
    93   for(i = 0;i < numGestureTouches; i++) {
    94     if((touchId < 0) || (gestureTouch[i].id == touchId)) {
    95       gestureTouch[i].recording = SDL_TRUE;
    96       if(touchId >= 0)
    97 	return 1;
    98     }      
    99   }
   100   return (touchId < 0);
   101 }
   102 
   103 unsigned long SDL_HashDollar(Point* points) {
   104   unsigned long hash = 5381;
   105   int i;
   106   for(i = 0;i < DOLLARNPOINTS; i++) { 
   107     hash = ((hash<<5) + hash) + points[i].x;
   108     hash = ((hash<<5) + hash) + points[i].y;
   109   }
   110   return hash;
   111 }
   112 
   113 
   114 static int SaveTemplate(DollarTemplate *templ, SDL_RWops * src) {
   115   if(src == NULL) return 0;
   116 
   117   int i;
   118   
   119   //No Longer storing the Hash, rehash on load
   120   //fprintf(fp,"%lu ",templ->hash);
   121   //if(SDL_RWops.write(src,&(templ->hash),sizeof(templ->hash),1) != 1) return 0;
   122   
   123   /*
   124   for(i = 0;i < DOLLARNPOINTS;i++) {
   125     fprintf(fp,"%i %i ",(int)templ->path[i].x,(int)templ->path[i].y);
   126   }
   127   fprintf(fp,"\n");
   128 
   129   */
   130   if(SDL_RWwrite(src,templ->path,sizeof(templ->path[0]),DOLLARNPOINTS) != DOLLARNPOINTS) return 0;
   131   return 1;
   132 }
   133 
   134 
   135 int SDL_SaveAllDollarTemplates(SDL_RWops *src) {  
   136   int i,j,rtrn = 0;
   137   for(i = 0; i < numGestureTouches; i++) {
   138     GestureTouch* touch = &gestureTouch[i];
   139     for(j = 0;j < touch->numDollarTemplates; j++) {
   140 	rtrn += SaveTemplate(&touch->dollarTemplate[i],src);
   141     }
   142   }
   143   return rtrn;  
   144 }
   145 
   146 int SDL_SaveDollarTemplate(unsigned long gestureId, SDL_RWops *src) {
   147   int i,j;
   148   for(i = 0; i < numGestureTouches; i++) {
   149     GestureTouch* touch = &gestureTouch[i];
   150     for(j = 0;j < touch->numDollarTemplates; j++) {
   151       if(touch->dollarTemplate[i].hash == gestureId) {
   152 	return SaveTemplate(&touch->dollarTemplate[i],src);
   153       }
   154     }
   155   }
   156   SDL_SetError("Unknown gestureId");
   157   return -1;
   158 }
   159 
   160 //path is an already sampled set of points
   161 //Returns the index of the gesture on success, or -1
   162 static int SDL_AddDollarGesture(GestureTouch* inTouch,Point* path) {
   163   if(inTouch == NULL) {
   164     if(numGestureTouches == 0) return -1;
   165     int i = 0;
   166     for(i = 0;i < numGestureTouches; i++) {
   167       inTouch = &gestureTouch[i];
   168       if(inTouch->numDollarTemplates < MAXTEMPLATES) {
   169 	DollarTemplate *templ = 
   170 	  &inTouch->dollarTemplate[inTouch->numDollarTemplates];
   171 	memcpy(templ->path,path,DOLLARNPOINTS*sizeof(Point));
   172 	templ->hash = SDL_HashDollar(templ->path);
   173 	inTouch->numDollarTemplates++;
   174       }
   175     }
   176     return inTouch->numDollarTemplates - 1;
   177   }else if(inTouch->numDollarTemplates < MAXTEMPLATES) {
   178     DollarTemplate *templ = 
   179       &inTouch->dollarTemplate[inTouch->numDollarTemplates];
   180     memcpy(templ->path,path,DOLLARNPOINTS*sizeof(Point));
   181     templ->hash = SDL_HashDollar(templ->path);
   182     inTouch->numDollarTemplates++;
   183     return inTouch->numDollarTemplates - 1;
   184   }
   185   return -1;
   186 }
   187 
   188 int SDL_LoadDollarTemplates(int touchId, SDL_RWops *src) {
   189   if(src == NULL) return 0;
   190   int i,loaded = 0;
   191   GestureTouch *touch = NULL;
   192   if(touchId >= 0) {
   193     for(i = 0;i < numGestureTouches; i++)
   194       if(gestureTouch[i].id == touchId)
   195 	touch = &gestureTouch[i];
   196     if(touch == NULL) return -1;
   197   }
   198 
   199   while(1) {
   200     DollarTemplate templ;
   201     //fscanf(fp,"%lu ",&templ.hash);
   202     /*
   203     for(i = 0;i < DOLLARNPOINTS; i++) {		
   204       int x,y;
   205       if(fscanf(fp,"%i %i ",&x,&y) != 2) break;
   206       templ.path[i].x = x;
   207       templ.path[i].y = y;
   208     }
   209     fscanf(fp,"\n");
   210     */
   211     if(SDL_RWread(src,templ.path,sizeof(templ.path[0]),DOLLARNPOINTS) < DOLLARNPOINTS) break;
   212 
   213     if(touchId >= 0) {
   214       printf("Adding loaded gesture to 1 touch\n");
   215       if(SDL_AddDollarGesture(touch,templ.path)) loaded++;
   216     }
   217     else {
   218       printf("Adding to: %i touches\n",numGestureTouches);
   219       for(i = 0;i < numGestureTouches; i++) {
   220 	touch = &gestureTouch[i];
   221 	printf("Adding loaded gesture to + touches\n");
   222 	//TODO: What if this fails?
   223 	SDL_AddDollarGesture(touch,templ.path);	
   224       }
   225       loaded++;
   226     }
   227   }
   228 
   229   return loaded; 
   230 }
   231 
   232 
   233 float dollarDifference(Point* points,Point* templ,float ang) {
   234   //  Point p[DOLLARNPOINTS];
   235   float dist = 0;
   236   Point p;
   237   int i;
   238   for(i = 0; i < DOLLARNPOINTS; i++) {
   239     p.x = points[i].x * cos(ang) - points[i].y * sin(ang);
   240     p.y = points[i].x * sin(ang) + points[i].y * cos(ang);
   241     dist += sqrt((p.x-templ[i].x)*(p.x-templ[i].x)+
   242 		 (p.y-templ[i].y)*(p.y-templ[i].y));
   243   }
   244   return dist/DOLLARNPOINTS;
   245   
   246 }
   247 
   248 float bestDollarDifference(Point* points,Point* templ) {
   249   //------------BEGIN DOLLAR BLACKBOX----------------//
   250   //-TRANSLATED DIRECTLY FROM PSUDEO-CODE AVAILABLE AT-//
   251   //-"http://depts.washington.edu/aimgroup/proj/dollar/"-//
   252   float ta = -M_PI/4;
   253   float tb = M_PI/4;
   254   float dt = M_PI/90;
   255   float x1 = PHI*ta + (1-PHI)*tb;
   256   float f1 = dollarDifference(points,templ,x1);
   257   float x2 = (1-PHI)*ta + PHI*tb;
   258   float f2 = dollarDifference(points,templ,x2);
   259   while(abs(ta-tb) > dt) {
   260     if(f1 < f2) {
   261       tb = x2;
   262       x2 = x1;
   263       f2 = f1;
   264       x1 = PHI*ta + (1-PHI)*tb;
   265       f1 = dollarDifference(points,templ,x1);
   266     }
   267     else {
   268       ta = x1;
   269       x1 = x2;
   270       f1 = f2;
   271       x2 = (1-PHI)*ta + PHI*tb;
   272       f2 = dollarDifference(points,templ,x2);
   273     }
   274   }
   275   /*
   276   if(f1 <= f2)
   277     printf("Min angle (x1): %f\n",x1);
   278   else if(f1 >  f2)
   279     printf("Min angle (x2): %f\n",x2);
   280   */
   281   return SDL_min(f1,f2);  
   282 }
   283 
   284 //DollarPath contains raw points, plus (possibly) the calculated length
   285 int dollarNormalize(DollarPath path,Point *points) {
   286   int i;
   287   //Calculate length if it hasn't already been done
   288   if(path.length <= 0) {
   289     for(i=1;i<path.numPoints;i++) {
   290       float dx = path.p[i  ].x - 
   291 	         path.p[i-1].x;
   292       float dy = path.p[i  ].y - 
   293 	         path.p[i-1].y;
   294       path.length += sqrt(dx*dx+dy*dy);
   295     }
   296   }
   297 
   298 
   299   //Resample
   300   float interval = path.length/(DOLLARNPOINTS - 1);
   301   float dist = 0;
   302 
   303   int numPoints = 0;
   304   Point centroid; centroid.x = 0;centroid.y = 0;
   305   //printf("(%f,%f)\n",path.p[path.numPoints-1].x,path.p[path.numPoints-1].y);
   306   for(i = 1;i < path.numPoints;i++) {
   307     float d = sqrt((path.p[i-1].x-path.p[i].x)*(path.p[i-1].x-path.p[i].x)+
   308 		   (path.p[i-1].y-path.p[i].y)*(path.p[i-1].y-path.p[i].y));
   309     //printf("d = %f dist = %f/%f\n",d,dist,interval);
   310     while(dist + d > interval) {
   311       points[numPoints].x = path.p[i-1].x + 
   312 	((interval-dist)/d)*(path.p[i].x-path.p[i-1].x);
   313       points[numPoints].y = path.p[i-1].y + 
   314 	((interval-dist)/d)*(path.p[i].y-path.p[i-1].y);
   315       centroid.x += points[numPoints].x;
   316       centroid.y += points[numPoints].y;
   317       numPoints++;
   318 
   319       dist -= interval;
   320     }
   321     dist += d;
   322   }
   323   if(numPoints < 1) return 0;
   324   centroid.x /= numPoints;
   325   centroid.y /= numPoints;
   326  
   327   //printf("Centroid (%f,%f)",centroid.x,centroid.y);
   328   //Rotate Points so point 0 is left of centroid and solve for the bounding box
   329   float xmin,xmax,ymin,ymax;
   330   xmin = centroid.x;
   331   xmax = centroid.x;
   332   ymin = centroid.y;
   333   ymax = centroid.y;
   334   
   335   float ang = atan2(centroid.y - points[0].y,
   336 		    centroid.x - points[0].x);
   337 
   338   for(i = 0;i<numPoints;i++) {					       
   339     float px = points[i].x;
   340     float py = points[i].y;
   341     points[i].x = (px - centroid.x)*cos(ang) - 
   342                   (py - centroid.y)*sin(ang) + centroid.x;
   343     points[i].y = (px - centroid.x)*sin(ang) + 
   344                   (py - centroid.y)*cos(ang) + centroid.y;
   345 
   346 
   347     if(points[i].x < xmin) xmin = points[i].x;
   348     if(points[i].x > xmax) xmax = points[i].x; 
   349     if(points[i].y < ymin) ymin = points[i].y;
   350     if(points[i].y > ymax) ymax = points[i].y;
   351   }
   352 
   353   //Scale points to DOLLARSIZE, and translate to the origin
   354   float w = xmax-xmin;
   355   float h = ymax-ymin;
   356 
   357   for(i=0;i<numPoints;i++) {
   358     points[i].x = (points[i].x - centroid.x)*DOLLARSIZE/w;
   359     points[i].y = (points[i].y - centroid.y)*DOLLARSIZE/h;
   360   }  
   361   return numPoints;
   362 }
   363 
   364 float dollarRecognize(DollarPath path,int *bestTempl,GestureTouch* touch) {
   365 	
   366 	Point points[DOLLARNPOINTS];
   367 	int numPoints = dollarNormalize(path,points);
   368 	int i;
   369 	
   370 	int bestDiff = 10000;
   371 	*bestTempl = -1;
   372 	for(i = 0;i < touch->numDollarTemplates;i++) {
   373 		int diff = bestDollarDifference(points,touch->dollarTemplate[i].path);
   374 		if(diff < bestDiff) {bestDiff = diff; *bestTempl = i;}
   375 	}
   376 	return bestDiff;
   377 }
   378 
   379 int SDL_GestureAddTouch(SDL_Touch* touch) { 
   380   if(numGestureTouches >= MAXTOUCHES) return -1;
   381   
   382   gestureTouch[numGestureTouches].res.x = touch->xres;
   383   gestureTouch[numGestureTouches].res.y = touch->yres;
   384   gestureTouch[numGestureTouches].numDownFingers = 0;
   385 
   386   gestureTouch[numGestureTouches].res.x = touch->xres;
   387   gestureTouch[numGestureTouches].id = touch->id;
   388 
   389   gestureTouch[numGestureTouches].numDollarTemplates = 0;
   390 
   391   gestureTouch[numGestureTouches].recording = SDL_FALSE;
   392 
   393   numGestureTouches++;
   394   return 0;
   395 }
   396 
   397 GestureTouch * SDL_GetGestureTouch(int id) {
   398   int i;
   399   for(i = 0;i < numGestureTouches; i++) {
   400     //printf("%i ?= %i\n",gestureTouch[i].id,id);
   401     if(gestureTouch[i].id == id) return &gestureTouch[i];
   402   }
   403   return NULL;
   404 }
   405 
   406 int SDL_SendGestureMulti(GestureTouch* touch,float dTheta,float dDist) {
   407   SDL_Event event;
   408   event.mgesture.type = SDL_MULTIGESTURE;
   409   event.mgesture.touchId = touch->id;
   410   event.mgesture.x = touch->centroid.x;
   411   event.mgesture.y = touch->centroid.y;
   412   event.mgesture.dTheta = dTheta;
   413   event.mgesture.dDist = dDist;  
   414   return SDL_PushEvent(&event) > 0;
   415 }
   416 
   417 int SDL_SendGestureDollar(GestureTouch* touch,int gestureId,float error) {
   418   SDL_Event event;
   419   event.dgesture.type = SDL_DOLLARGESTURE;
   420   event.dgesture.touchId = touch->id;
   421   /*
   422     //TODO: Add this to give location of gesture?
   423   event.mgesture.x = touch->centroid.x;
   424   event.mgesture.y = touch->centroid.y;
   425   */
   426   event.dgesture.gestureId = gestureId;
   427   event.dgesture.error = error;  
   428   return SDL_PushEvent(&event) > 0;
   429 }
   430 
   431 
   432 int SDL_SendDollarRecord(GestureTouch* touch,int gestureId) {
   433   SDL_Event event;
   434   event.dgesture.type = SDL_DOLLARRECORD;
   435   event.dgesture.touchId = touch->id;
   436   event.dgesture.gestureId = gestureId;
   437 
   438   return SDL_PushEvent(&event) > 0;
   439 }
   440 
   441 
   442 void SDL_GestureProcessEvent(SDL_Event* event)
   443 {
   444   if(event->type == SDL_FINGERMOTION || 
   445      event->type == SDL_FINGERDOWN ||
   446      event->type == SDL_FINGERUP) {
   447     GestureTouch* inTouch = SDL_GetGestureTouch(event->tfinger.touchId);
   448 
   449     //Shouldn't be possible
   450     if(inTouch == NULL) return;
   451     
   452     
   453     float x = ((float)event->tfinger.x)/inTouch->res.x;
   454     float y = ((float)event->tfinger.y)/inTouch->res.y;
   455     int j,empty = -1;
   456     
   457     for(j = 0;j<inTouch->numDownFingers;j++) {
   458       if(inTouch->gestureLast[j].f.id != event->tfinger.fingerId) continue;
   459       //Finger Up
   460       if(event->type == SDL_FINGERUP) {
   461 	inTouch->numDownFingers--;
   462 
   463 	if(inTouch->recording) {
   464 	  inTouch->recording = SDL_FALSE;
   465 	  Point path[DOLLARNPOINTS];
   466 	  dollarNormalize(inTouch->gestureLast[j].dollarPath,path);
   467 	  int index;
   468 	  if(recordAll) {
   469 	    index = SDL_AddDollarGesture(NULL,path);
   470 	    int i;
   471 	    for(i = 0;i < numGestureTouches; i++)
   472 	      gestureTouch[i].recording = SDL_FALSE;
   473 	  }
   474 	  else {
   475 	    index = SDL_AddDollarGesture(inTouch,path);
   476 	  }
   477 	  
   478 	  if(index >= 0) {
   479 	    SDL_SendDollarRecord(inTouch,inTouch->dollarTemplate[index].hash);
   480 	  }
   481 	  else {
   482 	    SDL_SendDollarRecord(inTouch,-1);
   483 	  }
   484 	}
   485 	else {	
   486 	  int bestTempl;
   487 	  float error;
   488 	  error = dollarRecognize(inTouch->gestureLast[j].dollarPath,
   489 				  &bestTempl,inTouch);
   490 	  if(bestTempl >= 0){
   491 	    //Send Event
   492 	    int gestureId = inTouch->dollarTemplate[bestTempl].hash;
   493 	    SDL_SendGestureDollar(inTouch,gestureId,error);
   494 	    printf("Dollar error: %f\n",error);
   495 	  }
   496 	} 
   497 	inTouch->gestureLast[j] = inTouch->gestureLast[inTouch->numDownFingers];
   498 	break;
   499       }
   500       else {
   501 	float dx = x - inTouch->gestureLast[j].f.p.x;
   502 	float dy = y - inTouch->gestureLast[j].f.p.y;
   503 	DollarPath* path = &inTouch->gestureLast[j].dollarPath;
   504 	if(path->numPoints < MAXPATHSIZE) {
   505 	  path->p[path->numPoints].x = x;
   506 	  path->p[path->numPoints].y = y;
   507 	  path->length += sqrt(dx*dx + dy*dy);
   508 	  path->numPoints++;
   509 	}
   510 
   511 
   512 	inTouch->centroid.x += dx/inTouch->numDownFingers;
   513 	inTouch->centroid.y += dy/inTouch->numDownFingers;    
   514 	if(inTouch->numDownFingers > 1) {
   515 	  Point lv; //Vector from centroid to last x,y position
   516 	  Point v; //Vector from centroid to current x,y position
   517 	  lv = inTouch->gestureLast[j].cv;
   518 	  float lDist = sqrt(lv.x*lv.x + lv.y*lv.y);
   519 	  //printf("lDist = %f\n",lDist);
   520 	  v.x = x - inTouch->centroid.x;
   521 	  v.y = y - inTouch->centroid.y;
   522 	  inTouch->gestureLast[j].cv = v;
   523 	  float Dist = sqrt(v.x*v.x+v.y*v.y);
   524 	  // cos(dTheta) = (v . lv)/(|v| * |lv|)
   525 	  
   526 	  //Normalize Vectors to simplify angle calculation
   527 	  lv.x/=lDist;
   528 	  lv.y/=lDist;
   529 	  v.x/=Dist;
   530 	  v.y/=Dist;
   531 	  float dtheta = atan2(lv.x*v.y - lv.y*v.x,lv.x*v.x + lv.y*v.y);
   532 	  
   533 	  float dDist = (Dist - lDist);
   534 	  if(lDist == 0) {dDist = 0;dtheta = 0;} //To avoid impossible values
   535 	  inTouch->gestureLast[j].dDist = dDist;
   536 	  inTouch->gestureLast[j].dtheta = dtheta;
   537 	  
   538 	  //printf("dDist = %f, dTheta = %f\n",dDist,dtheta);
   539 	  //gdtheta = gdtheta*.9 + dtheta*.1;
   540 	  //gdDist  =  gdDist*.9 +  dDist*.1
   541 	  //knob.r += dDist/numDownFingers;
   542 	  //knob.ang += dtheta;
   543 	  //printf("thetaSum = %f, distSum = %f\n",gdtheta,gdDist);
   544 	  //printf("id: %i dTheta = %f, dDist = %f\n",j,dtheta,dDist);
   545 	  SDL_SendGestureMulti(inTouch,dtheta,dDist);
   546 	}
   547 	else {
   548 	  inTouch->gestureLast[j].dDist = 0;
   549 	  inTouch->gestureLast[j].dtheta = 0;
   550 	  inTouch->gestureLast[j].cv.x = 0;
   551 	  inTouch->gestureLast[j].cv.y = 0;
   552 	}
   553 	inTouch->gestureLast[j].f.p.x = x;
   554 	inTouch->gestureLast[j].f.p.y = y;
   555 	break;
   556 	//pressure?
   557       }      
   558     }
   559     
   560     if(j == inTouch->numDownFingers) {
   561       //printf("Finger Down!!!\n");
   562       inTouch->numDownFingers++;
   563       inTouch->centroid.x = (inTouch->centroid.x*(inTouch->numDownFingers - 1)+ 
   564 			     x)/inTouch->numDownFingers;
   565       inTouch->centroid.y = (inTouch->centroid.y*(inTouch->numDownFingers - 1)+
   566 			     y)/inTouch->numDownFingers;
   567       
   568       inTouch->gestureLast[j].f.id = event->tfinger.fingerId;
   569       inTouch->gestureLast[j].f.p.x  = x;
   570       inTouch->gestureLast[j].f.p.y  = y;	
   571       inTouch->gestureLast[j].cv.x = 0;
   572       inTouch->gestureLast[j].cv.y = 0;
   573 
   574       inTouch->gestureLast[j].dollarPath.length = 0;
   575       inTouch->gestureLast[j].dollarPath.p[0].x = x;
   576       inTouch->gestureLast[j].dollarPath.p[0].y = y;
   577       inTouch->gestureLast[j].dollarPath.numPoints = 1;
   578     }
   579   }
   580 }  
   581   
   582   /* vi: set ts=4 sw=4 expandtab: */
   583