gengpro1.d

   1 /* Invisible Vector Library
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, version 3 of the License ONLY.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 // Protractor gesture recognizer, v1
  18 module iv.gengpro1 /*is aliced*/;
  19 private:
  20
  21 import iv.alice;
  22 import iv.vfs;
  23
  24
  25 // ////////////////////////////////////////////////////////////////////////// //
  26 public alias GengFloat = float; ///
  27
  28
  29 // ////////////////////////////////////////////////////////////////////////// //
  30 // DO NOT CHANGE!
  31 enum NormalizedPoints = 16; // the paper says that this is enough for protractor to work ok
  32 static assert(NormalizedPoints > 2 && NormalizedPoints < ushort.max);
  33 alias GengPatternPoints = GengFloat[NormalizedPoints*2];
  34 enum MinPointDistance = 4;
  35
  36
  37 // ////////////////////////////////////////////////////////////////////////// //
  38 ///
  39 public class PTGlyph {
  40   public enum MinMatchScore = 1.5; ///
  41
  42 public:
  43   ///
  44   static struct Point {
  45     GengFloat x, y;
  46     @property bool valid () const pure nothrow @safe @nogc { pragma(inline, true); import std.math : isNaN; return (!x.isNaN && !y.isNaN); }
  47   }
  48
  49 private:
  50   GengPatternPoints patpoints;
  51   GengFloat[] points; // [0]:x, [1]:y, [2]:x, [3]:y, etc...
  52   bool mNormalized; // true: `patpoints` is ok
  53   bool mOriented = true;
  54   string mName;
  55
  56 private:
  57   static void unsafeArrayAppend(T) (ref T[] arr, auto ref T v) {
  58     auto optr = arr.ptr;
  59     arr ~= v;
  60     if (optr !is arr.ptr) {
  61       import core.memory : GC;
  62       optr = arr.ptr;
  63       if (optr !is null && optr is GC.addrOf(optr)) GC.setAttr(optr, GC.BlkAttr.NO_INTERIOR);
  64     }
  65   }
  66
  67   static T[] unsafeArrayDup(T) (const(T)[] arr) {
  68     auto res = arr.dup;
  69     if (res.ptr) {
  70       import core.memory : GC;
  71       if (res.ptr !is null && res.ptr is GC.addrOf(res.ptr)) GC.setAttr(res.ptr, GC.BlkAttr.NO_INTERIOR);
  72     }
  73     return res;
  74   }
  75
  76   static normBlkAttr(T) (T[] arr) {
  77     pragma(inline, true);
  78     import core.memory : GC;
  79     if (arr.ptr !is null && arr.ptr is GC.addrOf(arr.ptr)) GC.setAttr(arr.ptr, GC.BlkAttr.NO_INTERIOR);
  80   }
  81
  82 public:
  83   this () nothrow @safe @nogc {}
  84
  85   this (string aname, bool aoriented=true) nothrow @safe @nogc { mName = aname; mOriented = aoriented; } ///
  86
  87   ///
  88   this (string aname, in GengPatternPoints apat, bool aoriented=true) nothrow @safe @nogc {
  89     mName = aname;
  90     patpoints[] = apat[];
  91     mNormalized = true;
  92     mOriented = aoriented;
  93   }
  94
  95 final:
  96   @property const pure nothrow @safe @nogc {
  97     bool valid () { pragma(inline, true); return (mNormalized || points.length >= 4); } ///
  98     bool normalized () { pragma(inline, true); return mNormalized; } ///
  99     bool oriented () { pragma(inline, true); return mOriented; } ///
 100     string name () { pragma(inline, true); return mName; } ///
 101     bool hasOriginalPoints () { pragma(inline, true); return (points.length != 0); } ///
 102     usize length () { pragma(inline, true); return points.length/2; } /// number of original points
 103     alias opDollar = length;
 104     /// return normalized points
 105     GengPatternPoints normPoints () {
 106       GengPatternPoints res = patpoints[];
 107       if (!mNormalized && points.length >= 4) resample(res, points);
 108       return res;
 109     }
 110     enum normLength = NormalizedPoints;
 111     Point normPoint (usize idx) {
 112       if (!valid || idx >= NormalizedPoints) return Point.init;
 113       if (mNormalized) {
 114         return Point(patpoints[idx*2+0], patpoints[idx*2+1]);
 115       } else {
 116         GengPatternPoints rpt = void;
 117         resample(rpt, points);
 118         return Point(patpoints[idx*2+0], patpoints[idx*2+1]);
 119       }
 120     }
 121     /// return original point
 122     Point opIndex (usize idx) { pragma(inline, true); return (idx < points.length/2 ? Point(points[idx*2], points[idx*2+1]) : Point.init); }
 123   }
 124
 125   /// can't be changed for normalized glyphs with original points dropped
 126   @property void oriented (bool v) pure nothrow @safe @nogc {
 127     if (mNormalized && points.length < 4) return;
 128     if (mOriented != v) {
 129       mOriented = v;
 130       mNormalized = false;
 131     }
 132   }
 133
 134   ///
 135   @property void name(T:const(char)[]) (T v) nothrow @safe {
 136     static if (is(T == typeof(null))) mName = null;
 137     else static if (is(T == string)) mName = v;
 138     else { if (mName != v) mName = v.idup; }
 139   }
 140
 141   /// will not clear orientation
 142   auto clear () nothrow @trusted {
 143     delete points;
 144     mNormalized = false;
 145     mName = null;
 146     return this;
 147   }
 148
 149   ///
 150   auto clone () const @trusted {
 151     auto res = new PTGlyph();
 152     res.mName = mName;
 153     res.mNormalized = mNormalized;
 154     res.mOriented = mOriented;
 155     res.patpoints[] = patpoints[];
 156     res.points = unsafeArrayDup(points);
 157     return res;
 158   }
 159
 160   ///
 161   auto appendPoint (int x, int y) nothrow @trusted {
 162     immutable GengFloat fx = cast(GengFloat)x;
 163     immutable GengFloat fy = cast(GengFloat)y;
 164     if (points.length > 0) {
 165       // check distance and don't add points that are too close to each other
 166       immutable lx = fx-points[$-2], ly = fy-points[$-1];
 167       if (lx*lx+ly*ly < MinPointDistance*MinPointDistance) return this;
 168     }
 169     unsafeArrayAppend(points, cast(GengFloat)fx);
 170     unsafeArrayAppend(points, cast(GengFloat)fy);
 171     mNormalized = false;
 172     return this;
 173   }
 174
 175   ///
 176   auto normalize (bool dropOriginalPoints=true) {
 177     if (!mNormalized) {
 178       if (points.length < 4) throw new Exception("glyph must have at least two points");
 179       buildNormPoints(patpoints, points, mOriented);
 180       mNormalized = true;
 181     }
 182     if (dropOriginalPoints) { assert(mNormalized); delete points; }
 183     return this;
 184   }
 185
 186   ///
 187   static bool isGoodScore (GengFloat score) {
 188     pragma(inline, true);
 189     import std.math : isNaN;
 190     return (!score.isNaN ? score >= MinMatchScore : false);
 191   }
 192
 193   /// this: template; you can use `isGoodScore()` to see if it is a good score to detect a match
 194   GengFloat match (const(PTGlyph) sample) const pure nothrow @safe @nogc {
 195     if (sample is null || !sample.valid || !valid) return -GengFloat.infinity;
 196     GengPatternPoints me = patpoints[];
 197     GengPatternPoints it = sample.patpoints[];
 198     if (!mNormalized) buildNormPoints(me, points, mOriented);
 199     if (!sample.mNormalized) buildNormPoints(it, sample.points, sample.mOriented);
 200     return match(me, it);
 201   }
 202
 203 private:
 204   // ignore possible overflows here
 205   static GengFloat distance (in GengFloat x0, in GengFloat y0, in GengFloat x1, in GengFloat y1) pure nothrow @safe @nogc {
 206     pragma(inline, true);
 207     import std.math : sqrt;
 208     immutable dx = x1-x0, dy = y1-y0;
 209     return sqrt(dx*dx+dy*dy);
 210   }
 211
 212   static GengFloat match (in ref GengPatternPoints tpl, in ref GengPatternPoints v1) pure nothrow @safe @nogc {
 213     pragma(inline, true);
 214     return cast(GengFloat)1.0/optimalCosineDistance(tpl, v1);
 215   }
 216
 217   static GengFloat optimalCosineDistance (in ref GengPatternPoints v0, in ref GengPatternPoints v1) pure nothrow @trusted @nogc {
 218     import std.math : atan, acos, cos, sin;
 219     GengFloat a = 0, b = 0;
 220     foreach (immutable idx; 0..NormalizedPoints) {
 221       a += v0.ptr[idx*2+0]*v1.ptr[idx*2+0]+v0.ptr[idx*2+1]*v1.ptr[idx*2+1];
 222       b += v0.ptr[idx*2+0]*v1.ptr[idx*2+1]-v0.ptr[idx*2+1]*v1.ptr[idx*2+0];
 223     }
 224     immutable GengFloat angle = atan(b/a);
 225     return acos(a*cos(angle)+b*sin(angle));
 226   }
 227
 228   // glyph length (not point counter!)
 229   static GengFloat glyphLength (in GengFloat[] points) pure nothrow @trusted @nogc {
 230     GengFloat res = 0.0;
 231     if (points.length >= 4) {
 232       // don't want to bring std.algo here
 233       GengFloat px = points.ptr[0], py = points.ptr[1];
 234       foreach (immutable idx; 2..points.length/2) {
 235         immutable cx = points.ptr[idx*2+0], cy = points.ptr[idx*2+1];
 236         res += distance(px, py, cx, cy);
 237         px = cx;
 238         py = cy;
 239       }
 240     }
 241     return res;
 242   }
 243
 244   static void resample (ref GengPatternPoints ptres, in GengFloat[] points) pure @trusted nothrow @nogc {
 245     assert(points.length >= 4);
 246     immutable GengFloat I = glyphLength(points)/(NormalizedPoints-1); // interval length
 247     GengFloat D = 0.0;
 248     GengFloat prx = points.ptr[0];
 249     GengFloat pry = points.ptr[1];
 250     // add first point as-is
 251     ptres.ptr[0] = prx;
 252     ptres.ptr[1] = pry;
 253     usize ptpos = 2, oppos = 2;
 254     while (oppos < points.length && points.length-oppos >= 2) {
 255       immutable GengFloat cx = points.ptr[oppos], cy = points.ptr[oppos+1];
 256       immutable d = distance(prx, pry, cx, cy);
 257       if (D+d >= I) {
 258         immutable dd = (I-D)/d;
 259         immutable qx = prx+dd*(cx-prx);
 260         immutable qy = pry+dd*(cy-pry);
 261         assert(ptpos < NormalizedPoints*2);
 262         ptres.ptr[ptpos++] = qx;
 263         ptres.ptr[ptpos++] = qy;
 264         // use 'q' as previous point
 265         prx = qx;
 266         pry = qy;
 267         D = 0.0;
 268       } else {
 269         D += d;
 270         prx = cx;
 271         pry = cy;
 272         oppos += 2;
 273       }
 274     }
 275     // somtimes we fall a rounding-error short of adding the last point, so add it if so
 276     if (ptpos/2 == NormalizedPoints-1) {
 277       ptres.ptr[ptpos++] = points[$-2];
 278       ptres.ptr[ptpos++] = points[$-1];
 279     }
 280     assert(ptpos == NormalizedPoints*2);
 281   }
 282
 283   // stroke is not required to be centered, but it must be resampled
 284   static void vectorize (ref GengPatternPoints vres, in ref GengPatternPoints ptx, bool orientationSensitive) pure nothrow @trusted @nogc {
 285     import std.math : atan2, cos, sin, floor, sqrt, PI;
 286     GengPatternPoints pts = void;
 287     GengFloat cx = 0, cy = 0;
 288     // center it
 289     foreach (immutable idx; 0..NormalizedPoints) {
 290       cx += ptx.ptr[idx*2+0];
 291       cy += ptx.ptr[idx*2+1];
 292     }
 293     cx /= NormalizedPoints;
 294     cy /= NormalizedPoints;
 295     foreach (immutable idx; 0..NormalizedPoints) {
 296       pts.ptr[idx*2+0] = ptx.ptr[idx*2+0]-cx;
 297       pts.ptr[idx*2+1] = ptx.ptr[idx*2+1]-cy;
 298     }
 299     immutable GengFloat indAngle = atan2(pts.ptr[1], pts.ptr[0]); // always must be done for centered stroke
 300     GengFloat delta = indAngle;
 301     if (orientationSensitive) {
 302       immutable baseOrientation = (PI/4.0)*floor((indAngle+PI/8.0)/(PI/4.0));
 303       delta = baseOrientation-indAngle;
 304     }
 305     immutable GengFloat cosd = cos(delta);
 306     immutable GengFloat sind = sin(delta);
 307     GengFloat sum = 0;
 308     foreach (immutable idx; 0..NormalizedPoints) {
 309       immutable nx = pts.ptr[idx*2+0]*cosd-pts.ptr[idx*2+1]*sind;
 310       immutable ny = pts.ptr[idx*2+1]*cosd+pts.ptr[idx*2+0]*sind;
 311       vres.ptr[idx*2+0] = nx;
 312       vres.ptr[idx*2+1] = ny;
 313       sum += nx*nx+ny*ny;
 314     }
 315     immutable GengFloat magnitude = sqrt(sum);
 316     foreach (ref GengFloat v; vres[]) v /= magnitude;
 317   }
 318
 319   static void buildNormPoints (out GengPatternPoints vres, in GengFloat[] points, bool orientationSensitive) pure nothrow @safe @nogc {
 320     assert(points.length >= 4);
 321     GengPatternPoints tmp = void;
 322     resample(tmp, points);
 323     vectorize(vres, tmp, orientationSensitive);
 324   }
 325
 326 public:
 327   // find matching gesture for this one
 328   // outscore is NaN if match wasn't found
 329   const(PTGlyph) findMatch (const(PTGlyph)[] list, GengFloat* outscore=null) const nothrow @trusted @nogc {
 330     GengFloat bestScore = -GengFloat.infinity;
 331     PTGlyph res = null;
 332     if (outscore !is null) *outscore = GengFloat.nan;
 333     if (valid) {
 334       // build normalized `this` glyph in pts
 335       GengPatternPoints pts = patpoints[];
 336       if (!mNormalized) buildNormPoints(pts, points, mOriented);
 337       GengPatternPoints gspts = void;
 338       foreach (const PTGlyph gs; list) {
 339         if (gs is null || !gs.valid) continue;
 340         gspts = gs.patpoints[];
 341         if (!gs.mNormalized) buildNormPoints(gspts, gs.points, gs.mOriented);
 342         GengFloat score = match(gspts, pts);
 343         //{ import core.stdc.stdio; printf("tested: '%.*s'; score=%f\n", cast(int)gs.mName.length, gs.mName.ptr, cast(double)score); }
 344         if (score >= MinMatchScore && score > bestScore) {
 345           bestScore = score;
 346           res = cast(PTGlyph)gs; // sorry
 347         }
 348       }
 349     }
 350     if (res !is null && outscore !is null) *outscore = bestScore;
 351     return res;
 352   }
 353
 354 private:
 355   static void wrXNum (VFile fl, usize n) {
 356     if (n < 254) {
 357       fl.writeNum!ubyte(cast(ubyte)n);
 358     } else {
 359       static if (n.sizeof == 8) {
 360         fl.writeNum!ubyte(254);
 361         fl.writeNum!ulong(n);
 362       } else {
 363         fl.writeNum!ubyte(255);
 364         fl.writeNum!uint(cast(uint)n);
 365       }
 366     }
 367   }
 368
 369   static usize rdXNum (VFile fl) {
 370     ubyte v = fl.readNum!ubyte;
 371     if (v < 254) return cast(usize)v;
 372     if (v == 254) {
 373       ulong nv = fl.readNum!ulong;
 374       if (nv > usize.max) throw new Exception("number too big");
 375       return cast(usize)nv;
 376     } else {
 377       assert(v == 255);
 378       return cast(usize)fl.readNum!uint;
 379     }
 380   }
 381
 382 public:
 383   void save (VFile fl) const {
 384     // name
 385     wrXNum(fl, mName.length);
 386     fl.rawWriteExact(mName);
 387     // "oriented" flag
 388     fl.writeNum!ubyte(mOriented ? 1 : 0);
 389     // normalized points
 390     if (mNormalized) {
 391       static assert(NormalizedPoints > 1 && NormalizedPoints < 254);
 392       fl.writeNum!ubyte(NormalizedPoints);
 393       foreach (immutable pt; patpoints[]) fl.writeNum!float(cast(float)pt);
 394     }
 395     // points
 396     wrXNum(fl, points.length);
 397     foreach (immutable v; points) fl.writeNum!float(cast(float)v);
 398   }
 399
 400   static PTGlyph loadNew (VFile fl, ubyte ver=2) {
 401     GengFloat rdFloat () {
 402       float fv = fl.readNum!float;
 403       if (fv != fv) throw new Exception("invalid floating number"); // nan check
 404       return cast(GengFloat)fv;
 405     }
 406
 407     if (ver == 0 || ver == 1) {
 408       // name
 409       auto len = fl.readNum!uint();
 410       if (len > 1024) throw new Exception("glyph name too long");
 411       auto res = new PTGlyph();
 412       if (len > 0) {
 413         auto buf = new char[](len);
 414         fl.rawReadExact(buf);
 415         res.mName = cast(string)buf; // it is safe to cast here
 416       }
 417       // template
 418       static if (NormalizedPoints == 16) {
 419         foreach (ref pt; res.patpoints[]) pt = rdFloat();
 420       } else {
 421         // load and resample
 422         GengFloat[] opts;
 423         scope(exit) delete opts;
 424         opts.reserve(16*2);
 425         normBlkAttr(opts);
 426         foreach (immutable pidx; 0..nplen*2) opts ~= rdFloat();
 427         resample(res.patpoints, opts);
 428       }
 429       res.mNormalized = true;
 430       res.mOriented = true;
 431       if (ver == 1) res.mOriented = (fl.readNum!ubyte != 0);
 432       return res;
 433     } else if (ver == 2) {
 434       // name
 435       auto nlen = rdXNum(fl);
 436       if (nlen > int.max/4) throw new Exception("glyph name too long");
 437       auto res = new PTGlyph();
 438       if (nlen) {
 439         auto nbuf = new char[](nlen);
 440         fl.rawReadExact(nbuf);
 441         res.mName = cast(string)nbuf; // it is safe to cast here
 442       }
 443       // "oriented" flag
 444       res.mOriented = (fl.readNum!ubyte != 0);
 445       // normalized points
 446       auto nplen = rdXNum(fl);
 447       if (nplen != 0) {
 448         if (nplen < 3 || nplen > ushort.max) throw new Exception("invalid number of resampled points");
 449         if (nplen != NormalizedPoints) {
 450           // load and resample -- this is all we can do
 451           GengFloat[] opts;
 452           scope(exit) delete opts;
 453           opts.reserve(nplen*2);
 454           normBlkAttr(opts);
 455           foreach (immutable pidx; 0..nplen*2) opts ~= rdFloat();
 456           resample(res.patpoints, opts);
 457         } else {
 458           // direct loading
 459           foreach (ref GengFloat fv; res.patpoints[]) fv = rdFloat();
 460         }
 461         res.mNormalized = true;
 462       }
 463       // original points
 464       auto plen = rdXNum(fl);
 465       if (plen) {
 466         if (plen%2 != 0) throw new Exception("invalid number of points");
 467         res.points.reserve(plen);
 468         normBlkAttr(res.points);
 469         foreach (immutable c; 0..plen) res.points ~= rdFloat();
 470       }
 471       return res;
 472     } else {
 473       assert(0, "wtf?!");
 474     }
 475   }
 476 }
 477
 478
 479 // ////////////////////////////////////////////////////////////////////////// //
 480 public void gstLibLoadEx (VFile fl, scope void delegate (PTGlyph) appendGlyph) {
 481   PTGlyph[] res;
 482   char[8] sign;
 483   fl.rawReadExact(sign[]);
 484   if (sign[0..$-1] != "K8PTRDB") throw new Exception("invalid gesture library signature");
 485   ubyte ver = cast(ubyte)sign[$-1];
 486   if (ver < '0' || ver > '9') throw new Exception("invalid gesture library signature");
 487   ver -= '0';
 488   if (ver > 2) throw new Exception("invalid gesture library version");
 489   if (ver == 0 || ver == 1) {
 490     // versions 0 and 1
 491     uint count = fl.readNum!uint;
 492     if (count > uint.max/8) throw new Exception("too many glyphs");
 493     foreach (immutable c; 0..count) {
 494       auto g = PTGlyph.loadNew(fl, ver);
 495       if (appendGlyph !is null) appendGlyph(g);
 496     }
 497   } else {
 498     // version 2
 499     while (fl.tell < fl.size) {
 500       auto g = PTGlyph.loadNew(fl, ver);
 501       if (appendGlyph !is null) appendGlyph(g);
 502     }
 503   }
 504 }
 505
 506
 507 public PTGlyph[] gstLibLoad (VFile fl) {
 508   PTGlyph[] res;
 509   fl.gstLibLoadEx(delegate (PTGlyph g) { res ~= g; });
 510   return res;
 511 }
 512
 513
 514 // ////////////////////////////////////////////////////////////////////////// //
 515 // return `null` from `nextGlyph` to indicate EOF
 516 public void gstLibSaveEx (VFile fl, scope const(PTGlyph) delegate () nextGlyph) {
 517   fl.rawWriteExact("K8PTRDB2");
 518   if (nextGlyph !is null) {
 519     for (;;) {
 520       auto g = nextGlyph();
 521       if (g is null) break;
 522       g.save(fl);
 523     }
 524   }
 525 }
 526
 527
 528 public void gstLibSave (VFile fl, const(PTGlyph)[] list) {
 529   usize pos = 0;
 530   fl.gstLibSaveEx(delegate () => (pos < list.length ? list[pos++] : null));
 531 }