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