cosmetix
[iv.d.git] / gengpro1.d
blob4c42e0de176f0e926fe1a5b48fb601a1f7fd2238
1 /* Invisible Vector Library
2 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
3 * Understanding is not required. Only obedience.
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.
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.
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/>.
18 // Protractor gesture recognizer, v1
19 module iv.gengpro1 /*is aliced*/;
20 private:
22 import iv.alice;
23 import iv.vfs;
26 // ////////////////////////////////////////////////////////////////////////// //
27 public alias GengFloat = float; ///
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;
38 // ////////////////////////////////////////////////////////////////////////// //
39 ///
40 public class PTGlyph {
41 public enum MinMatchScore = 1.5; ///
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); }
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;
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);
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);
74 return res;
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);
83 public:
84 this () nothrow @safe @nogc {}
86 this (string aname, bool aoriented=true) nothrow @safe @nogc { mName = aname; mOriented = aoriented; } ///
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;
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;
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]);
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); }
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;
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; }
142 /// will not clear orientation
143 auto clear () nothrow @trusted {
144 delete points;
145 mNormalized = false;
146 mName = null;
147 return this;
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;
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;
170 unsafeArrayAppend(points, cast(GengFloat)fx);
171 unsafeArrayAppend(points, cast(GengFloat)fy);
172 mNormalized = false;
173 return this;
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;
183 if (dropOriginalPoints) { assert(mNormalized); delete points; }
184 return this;
188 static bool isGoodScore (GengFloat score) {
189 pragma(inline, true);
190 import std.math : isNaN;
191 return (!score.isNaN ? score >= MinMatchScore : false);
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);
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);
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);
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];
225 immutable GengFloat angle = atan(b/a);
226 return acos(a*cos(angle)+b*sin(angle));
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;
242 return res;
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;
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];
281 assert(ptpos == NormalizedPoints*2);
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];
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;
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;
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;
316 immutable GengFloat magnitude = sqrt(sum);
317 foreach (ref GengFloat v; vres[]) v /= magnitude;
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);
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
351 if (res !is null && outscore !is null) *outscore = bestScore;
352 return res;
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);
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;
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);
396 // points
397 wrXNum(fl, points.length);
398 foreach (immutable v; points) fl.writeNum!float(cast(float)v);
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;
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
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);
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
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();
462 res.mNormalized = true;
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();
472 return res;
473 } else {
474 assert(0, "wtf?!");
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);
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);
508 public PTGlyph[] gstLibLoad (VFile fl) {
509 PTGlyph[] res;
510 fl.gstLibLoadEx(delegate (PTGlyph g) { res ~= g; });
511 return res;
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);
529 public void gstLibSave (VFile fl, const(PTGlyph)[] list) {
530 usize pos = 0;
531 fl.gstLibSaveEx(delegate () => (pos < list.length ? list[pos++] : null));