1// SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later
2// Copyright 2010, SIL International, All rights reserved.
3
4#include <algorithm>
5#include <limits>
6#include <cmath>
7#include <string>
8#include <functional>
9#include "inc/Collider.h"
10#include "inc/Segment.h"
11#include "inc/Slot.h"
12#include "inc/GlyphCache.h"
13#include "inc/Sparse.h"
14
15#define ISQRT2 0.707106781f
16
17// Possible rounding error for subbox boundaries: 0.016 = 1/64 = 1/256 * 4
18// (values in font range from 0..256)
19// #define SUBBOX_RND_ERR 0.016
20
21using namespace graphite2;
22
23//// SHIFT-COLLIDER ////
24
25// Initialize the Collider to hold the basic movement limits for the
26// target slot, the one we are focusing on fixing.
27bool ShiftCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin, float marginWeight,
28 const Position &currShift, const Position &currOffset, int dir, GR_MAYBE_UNUSED json * const dbgout)
29{
30 int i;
31 float mx, mn;
32 float a, shift;
33 const GlyphCache &gc = seg->getFace()->glyphs();
34 unsigned short gid = aSlot->gid();
35 if (!gc.check(gid))
36 return false;
37 const BBox &bb = gc.getBoundingBBox(gid);
38 const SlantBox &sb = gc.getBoundingSlantBox(gid);
39 //float sx = aSlot->origin().x + currShift.x;
40 //float sy = aSlot->origin().y + currShift.y;
41 if (currOffset.x != 0.f || currOffset.y != 0.f)
42 _limit = Rect(limit.bl - currOffset, limit.tr - currOffset);
43 else
44 _limit = limit;
45 // For a ShiftCollider, these indices indicate which vector we are moving by:
46 // each _ranges represents absolute space with respect to the origin of the slot. Thus take into account true origins but subtract the vmin for the slot
47 for (i = 0; i < 4; ++i)
48 {
49 switch (i) {
50 case 0 : // x direction
51 mn = _limit.bl.x + currOffset.x;
52 mx = _limit.tr.x + currOffset.x;
53 _len[i] = bb.xa - bb.xi;
54 a = currOffset.y + currShift.y;
55 _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);
56 break;
57 case 1 : // y direction
58 mn = _limit.bl.y + currOffset.y;
59 mx = _limit.tr.y + currOffset.y;
60 _len[i] = bb.ya - bb.yi;
61 a = currOffset.x + currShift.x;
62 _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);
63 break;
64 case 2 : // sum (negatively sloped diagonal boundaries)
65 // pick closest x,y limit boundaries in s direction
66 shift = currOffset.x + currOffset.y + currShift.x + currShift.y;
67 mn = -2 * min(currShift.x - _limit.bl.x, currShift.y - _limit.bl.y) + shift;
68 mx = 2 * min(_limit.tr.x - currShift.x, _limit.tr.y - currShift.y) + shift;
69 _len[i] = sb.sa - sb.si;
70 a = currOffset.x - currOffset.y + currShift.x - currShift.y;
71 _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);
72 break;
73 case 3 : // diff (positively sloped diagonal boundaries)
74 // pick closest x,y limit boundaries in d direction
75 shift = currOffset.x - currOffset.y + currShift.x - currShift.y;
76 mn = -2 * min(currShift.x - _limit.bl.x, _limit.tr.y - currShift.y) + shift;
77 mx = 2 * min(_limit.tr.x - currShift.x, currShift.y - _limit.bl.y) + shift;
78 _len[i] = sb.da - sb.di;
79 a = currOffset.x + currOffset.y + currShift.x + currShift.y;
80 _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);
81 break;
82 }
83 }
84
85 _target = aSlot;
86 if ((dir & 1) == 0)
87 {
88 // For LTR, switch and negate x limits.
89 _limit.bl.x = -1 * limit.tr.x;
90 //_limit.tr.x = -1 * limit.bl.x;
91 }
92 _currOffset = currOffset;
93 _currShift = currShift;
94 _origin = aSlot->origin() - currOffset; // the original anchor position of the glyph
95
96 _margin = margin;
97 _marginWt = marginWeight;
98
99 SlotCollision *c = seg->collisionInfo(aSlot);
100 _seqClass = c->seqClass();
101 _seqProxClass = c->seqProxClass();
102 _seqOrder = c->seqOrder();
103 return true;
104}
105
106template <class O>
107float sdm(float vi, float va, float mx, float my, O op)
108{
109 float res = 2 * mx - vi;
110 if (op(res, vi + 2 * my))
111 {
112 res = va + 2 * my;
113 if (op(res, 2 * mx - va))
114 res = mx + my;
115 }
116 return res;
117}
118
119// Mark an area with a cost that can vary along the x or y axis. The region is expressed in terms of the centre of the target glyph in each axis
120void ShiftCollider::addBox_slope(bool isx, const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, float weight, float m, bool minright, int axis)
121{
122 float a, c;
123 switch (axis) {
124 case 0 :
125 if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)
126 {
127 a = org.y + 0.5f * (bb.yi + bb.ya);
128 c = 0.5f * (bb.xi + bb.xa);
129 if (isx)
130 _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, m,
131 (minright ? box.tr.x : box.bl.x) - c, a, 0, false);
132 else
133 _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, 0, 0, org.y,
134 m * (a * a + sqr((minright ? box.tr.y : box.bl.y) - 0.5f * (bb.yi + bb.ya))), false);
135 }
136 break;
137 case 1 :
138 if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)
139 {
140 a = org.x + 0.5f * (bb.xi + bb.xa);
141 c = 0.5f * (bb.yi + bb.ya);
142 if (isx)
143 _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, 0, 0, org.x,
144 m * (a * a + sqr((minright ? box.tr.x : box.bl.x) - 0.5f * (bb.xi + bb.xa))), false);
145 else
146 _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, m,
147 (minright ? box.tr.y : box.bl.y) - c, a, 0, false);
148 }
149 break;
150 case 2 :
151 if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di)
152 {
153 float d = org.x - org.y + 0.5f * (sb.di + sb.da);
154 c = 0.5f * (sb.si + sb.sa);
155 float smax = min(2 * box.tr.x - d, 2 * box.tr.y + d);
156 float smin = max(2 * box.bl.x - d, 2 * box.bl.y + d);
157 if (smin > smax) return;
158 float si;
159 a = d;
160 if (isx)
161 si = 2 * (minright ? box.tr.x : box.bl.x) - a;
162 else
163 si = 2 * (minright ? box.tr.y : box.bl.y) + a;
164 _ranges[axis].weighted<SD>(smin - c, smax - c, weight / 2, a, m / 2, si, 0, 0, isx);
165 }
166 break;
167 case 3 :
168 if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si)
169 {
170 float s = org.x + org.y + 0.5f * (sb.si + sb.sa);
171 c = 0.5f * (sb.di + sb.da);
172 float dmax = min(2 * box.tr.x - s, s - 2 * box.bl.y);
173 float dmin = max(2 * box.bl.x - s, s - 2 * box.tr.y);
174 if (dmin > dmax) return;
175 float di;
176 a = s;
177 if (isx)
178 di = 2 * (minright ? box.tr.x : box.bl.x) - a;
179 else
180 di = 2 * (minright ? box.tr.y : box.bl.y) + a;
181 _ranges[axis].weighted<SD>(dmin - c, dmax - c, weight / 2, a, m / 2, di, 0, 0, !isx);
182 }
183 break;
184 default :
185 break;
186 }
187 return;
188}
189
190// Mark an area with an absolute cost, making it completely inaccessible.
191inline void ShiftCollider::removeBox(const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, int axis)
192{
193 float c;
194 switch (axis) {
195 case 0 :
196 if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)
197 {
198 c = 0.5f * (bb.xi + bb.xa);
199 _ranges[axis].exclude(box.bl.x - c, box.tr.x - c);
200 }
201 break;
202 case 1 :
203 if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)
204 {
205 c = 0.5f * (bb.yi + bb.ya);
206 _ranges[axis].exclude(box.bl.y - c, box.tr.y - c);
207 }
208 break;
209 case 2 :
210 if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di
211 && box.width() > 0 && box.height() > 0)
212 {
213 float di = org.x - org.y + sb.di;
214 float da = org.x - org.y + sb.da;
215 float smax = sdm(di, da, box.tr.x, box.tr.y, std::greater<float>());
216 float smin = sdm(da, di, box.bl.x, box.bl.y, std::less<float>());
217 c = 0.5f * (sb.si + sb.sa);
218 _ranges[axis].exclude(smin - c, smax - c);
219 }
220 break;
221 case 3 :
222 if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si
223 && box.width() > 0 && box.height() > 0)
224 {
225 float si = org.x + org.y + sb.si;
226 float sa = org.x + org.y + sb.sa;
227 float dmax = sdm(si, sa, box.tr.x, -box.bl.y, std::greater<float>());
228 float dmin = sdm(sa, si, box.bl.x, -box.tr.y, std::less<float>());
229 c = 0.5f * (sb.di + sb.da);
230 _ranges[axis].exclude(dmin - c, dmax - c);
231 }
232 break;
233 default :
234 break;
235 }
236 return;
237}
238
239// Adjust the movement limits for the target to avoid having it collide
240// with the given neighbor slot. Also determine if there is in fact a collision
241// between the target and the given slot.
242bool ShiftCollider::mergeSlot(Segment *seg, Slot *slot, const SlotCollision *cslot, const Position &currShift,
243 bool isAfter, // slot is logically after _target
244 bool sameCluster, bool &hasCol, bool isExclusion,
245 GR_MAYBE_UNUSED json * const dbgout )
246{
247 bool isCol = false;
248 const float sx = slot->origin().x - _origin.x + currShift.x;
249 const float sy = slot->origin().y - _origin.y + currShift.y;
250 const float sd = sx - sy;
251 const float ss = sx + sy;
252 float vmin, vmax;
253 float omin, omax, otmin, otmax;
254 float cmin, cmax; // target limits
255 float torg;
256 const GlyphCache &gc = seg->getFace()->glyphs();
257 const unsigned short gid = slot->gid();
258 if (!gc.check(gid))
259 return false;
260 const BBox &bb = gc.getBoundingBBox(gid);
261
262 // SlotCollision * cslot = seg->collisionInfo(slot);
263 int orderFlags = 0;
264 bool sameClass = _seqProxClass == 0 && cslot->seqClass() == _seqClass;
265 if (sameCluster && _seqClass
266 && (sameClass || (_seqProxClass != 0 && cslot->seqClass() == _seqProxClass)))
267 // Force the target glyph to be in the specified direction from the slot we're testing.
268 orderFlags = _seqOrder;
269
270 // short circuit if only interested in direct collision and we are out of range
271 if (orderFlags || (sx + bb.xa + _margin >= _limit.bl.x && sx + bb.xi - _margin <= _limit.tr.x)
272 || (sy + bb.ya + _margin >= _limit.bl.y && sy + bb.yi - _margin <= _limit.tr.y))
273
274 {
275 const float tx = _currOffset.x + _currShift.x;
276 const float ty = _currOffset.y + _currShift.y;
277 const float td = tx - ty;
278 const float ts = tx + ty;
279 const SlantBox &sb = gc.getBoundingSlantBox(gid);
280 const unsigned short tgid = _target->gid();
281 const BBox &tbb = gc.getBoundingBBox(tgid);
282 const SlantBox &tsb = gc.getBoundingSlantBox(tgid);
283 float seq_above_wt = cslot->seqAboveWt();
284 float seq_below_wt = cslot->seqBelowWt();
285 float seq_valign_wt = cslot->seqValignWt();
286 float lmargin;
287 // if isAfter, invert orderFlags for diagonal orders.
288 if (isAfter)
289 {
290 // invert appropriate bits
291 orderFlags ^= (sameClass ? 0x3F : 0x3);
292 // consider 2 bits at a time, non overlapping. If both bits set, clear them
293 orderFlags = orderFlags ^ ((((orderFlags >> 1) & orderFlags) & 0x15) * 3);
294 }
295
296#if !defined GRAPHITE2_NTRACING
297 if (dbgout)
298 dbgout->setenv(0, slot);
299#endif
300
301 // Process main bounding octabox.
302 for (int i = 0; i < 4; ++i)
303 {
304 switch (i) {
305 case 0 : // x direction
306 vmin = max(max(bb.xi - tbb.xa + sx, sb.di - tsb.da + ty + sd), sb.si - tsb.sa - ty + ss);
307 vmax = min(min(bb.xa - tbb.xi + sx, sb.da - tsb.di + ty + sd), sb.sa - tsb.si - ty + ss);
308 otmin = tbb.yi + ty;
309 otmax = tbb.ya + ty;
310 omin = bb.yi + sy;
311 omax = bb.ya + sy;
312 torg = _currOffset.x;
313 cmin = _limit.bl.x + torg;
314 cmax = _limit.tr.x - tbb.xi + tbb.xa + torg;
315 lmargin = _margin;
316 break;
317 case 1 : // y direction
318 vmin = max(max(bb.yi - tbb.ya + sy, tsb.di - sb.da + tx - sd), sb.si - tsb.sa - tx + ss);
319 vmax = min(min(bb.ya - tbb.yi + sy, tsb.da - sb.di + tx - sd), sb.sa - tsb.si - tx + ss);
320 otmin = tbb.xi + tx;
321 otmax = tbb.xa + tx;
322 omin = bb.xi + sx;
323 omax = bb.xa + sx;
324 torg = _currOffset.y;
325 cmin = _limit.bl.y + torg;
326 cmax = _limit.tr.y - tbb.yi + tbb.ya + torg;
327 lmargin = _margin;
328 break;
329 case 2 : // sum - moving along the positively-sloped vector, so the boundaries are the
330 // negatively-sloped boundaries.
331 vmin = max(max(sb.si - tsb.sa + ss, 2 * (bb.yi - tbb.ya + sy) + td), 2 * (bb.xi - tbb.xa + sx) - td);
332 vmax = min(min(sb.sa - tsb.si + ss, 2 * (bb.ya - tbb.yi + sy) + td), 2 * (bb.xa - tbb.xi + sx) - td);
333 otmin = tsb.di + td;
334 otmax = tsb.da + td;
335 omin = sb.di + sd;
336 omax = sb.da + sd;
337 torg = _currOffset.x + _currOffset.y;
338 cmin = _limit.bl.x + _limit.bl.y + torg;
339 cmax = _limit.tr.x + _limit.tr.y - tsb.si + tsb.sa + torg;
340 lmargin = _margin / ISQRT2;
341 break;
342 case 3 : // diff - moving along the negatively-sloped vector, so the boundaries are the
343 // positively-sloped boundaries.
344 vmin = max(max(sb.di - tsb.da + sd, 2 * (bb.xi - tbb.xa + sx) - ts), -2 * (bb.ya - tbb.yi + sy) + ts);
345 vmax = min(min(sb.da - tsb.di + sd, 2 * (bb.xa - tbb.xi + sx) - ts), -2 * (bb.yi - tbb.ya + sy) + ts);
346 otmin = tsb.si + ts;
347 otmax = tsb.sa + ts;
348 omin = sb.si + ss;
349 omax = sb.sa + ss;
350 torg = _currOffset.x - _currOffset.y;
351 cmin = _limit.bl.x - _limit.tr.y + torg;
352 cmax = _limit.tr.x - _limit.bl.y - tsb.di + tsb.da + torg;
353 lmargin = _margin / ISQRT2;
354 break;
355 default :
356 continue;
357 }
358
359#if !defined GRAPHITE2_NTRACING
360 if (dbgout)
361 dbgout->setenv(1, reinterpret_cast<void *>(-1));
362#define DBGTAG(x) if (dbgout) dbgout->setenv(1, reinterpret_cast<void *>(-x));
363#else
364#define DBGTAG(x)
365#endif
366
367 if (orderFlags)
368 {
369 Position org(tx, ty);
370 float xminf = _limit.bl.x + _currOffset.x + tbb.xi;
371 float xpinf = _limit.tr.x + _currOffset.x + tbb.xa;
372 float ypinf = _limit.tr.y + _currOffset.y + tbb.ya;
373 float yminf = _limit.bl.y + _currOffset.y + tbb.yi;
374 switch (orderFlags) {
375 case SlotCollision::SEQ_ORDER_RIGHTUP :
376 {
377 float r1Xedge = cslot->seqAboveXoff() + 0.5f * (bb.xi + bb.xa) + sx;
378 float r3Xedge = cslot->seqBelowXlim() + bb.xa + sx + 0.5f * (tbb.xa - tbb.xi);
379 float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;
380
381 // DBGTAG(1x) means the regions are up and right
382 // region 1
383 DBGTAG(11)
384 addBox_slope(true, Rect(Position(xminf, r2Yedge), Position(r1Xedge, ypinf)),
385 tbb, tsb, org, 0, seq_above_wt, true, i);
386 // region 2
387 DBGTAG(12)
388 removeBox(Rect(Position(xminf, yminf), Position(r3Xedge, r2Yedge)), tbb, tsb, org, i);
389 // region 3, which end is zero is irrelevant since m weight is 0
390 DBGTAG(13)
391 addBox_slope(true, Rect(Position(r3Xedge, yminf), Position(xpinf, r2Yedge - cslot->seqValignHt())),
392 tbb, tsb, org, seq_below_wt, 0, true, i);
393 // region 4
394 DBGTAG(14)
395 addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge), Position(xpinf, r2Yedge + cslot->seqValignHt())),
396 tbb, tsb, org, 0, seq_valign_wt, true, i);
397 // region 5
398 DBGTAG(15)
399 addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge - cslot->seqValignHt()), Position(xpinf, r2Yedge)),
400 tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);
401 break;
402 }
403 case SlotCollision::SEQ_ORDER_LEFTDOWN :
404 {
405 float r1Xedge = 0.5f * (bb.xi + bb.xa) + cslot->seqAboveXoff() + sx;
406 float r3Xedge = bb.xi - cslot->seqBelowXlim() + sx - 0.5f * (tbb.xa - tbb.xi);
407 float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;
408 // DBGTAG(2x) means the regions are up and right
409 // region 1
410 DBGTAG(21)
411 addBox_slope(true, Rect(Position(r1Xedge, yminf), Position(xpinf, r2Yedge)),
412 tbb, tsb, org, 0, seq_above_wt, false, i);
413 // region 2
414 DBGTAG(22)
415 removeBox(Rect(Position(r3Xedge, r2Yedge), Position(xpinf, ypinf)), tbb, tsb, org, i);
416 // region 3
417 DBGTAG(23)
418 addBox_slope(true, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()), Position(r3Xedge, ypinf)),
419 tbb, tsb, org, seq_below_wt, 0, false, i);
420 // region 4
421 DBGTAG(24)
422 addBox_slope(false, Rect(Position(xminf, r2Yedge), Position(sx + bb.xa, r2Yedge + cslot->seqValignHt())),
423 tbb, tsb, org, 0, seq_valign_wt, true, i);
424 // region 5
425 DBGTAG(25)
426 addBox_slope(false, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()),
427 Position(sx + bb.xa, r2Yedge)), tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);
428 break;
429 }
430 case SlotCollision::SEQ_ORDER_NOABOVE : // enforce neighboring glyph being above
431 DBGTAG(31);
432 removeBox(Rect(Position(bb.xi - tbb.xa + sx, sy + bb.ya),
433 Position(bb.xa - tbb.xi + sx, ypinf)), tbb, tsb, org, i);
434 break;
435 case SlotCollision::SEQ_ORDER_NOBELOW : // enforce neighboring glyph being below
436 DBGTAG(32);
437 removeBox(Rect(Position(bb.xi - tbb.xa + sx, yminf),
438 Position(bb.xa - tbb.xi + sx, sy + bb.yi)), tbb, tsb, org, i);
439 break;
440 case SlotCollision::SEQ_ORDER_NOLEFT : // enforce neighboring glyph being to the left
441 DBGTAG(33)
442 removeBox(Rect(Position(xminf, bb.yi - tbb.ya + sy),
443 Position(bb.xi - tbb.xa + sx, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);
444 break;
445 case SlotCollision::SEQ_ORDER_NORIGHT : // enforce neighboring glyph being to the right
446 DBGTAG(34)
447 removeBox(Rect(Position(bb.xa - tbb.xi + sx, bb.yi - tbb.ya + sy),
448 Position(xpinf, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);
449 break;
450 default :
451 break;
452 }
453 }
454
455 if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)
456 continue;
457
458 // Process sub-boxes that are defined for this glyph.
459 // We only need to do this if there was in fact a collision with the main octabox.
460 uint8 numsub = gc.numSubBounds(gid);
461 if (numsub > 0)
462 {
463 bool anyhits = false;
464 for (int j = 0; j < numsub; ++j)
465 {
466 const BBox &sbb = gc.getSubBoundingBBox(gid, j);
467 const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, j);
468 switch (i) {
469 case 0 : // x
470 vmin = max(max(sbb.xi-tbb.xa+sx, ssb.di-tsb.da+sd+ty), ssb.si-tsb.sa+ss-ty);
471 vmax = min(min(sbb.xa-tbb.xi+sx, ssb.da-tsb.di+sd+ty), ssb.sa-tsb.si+ss-ty);
472 omin = sbb.yi + sy;
473 omax = sbb.ya + sy;
474 break;
475 case 1 : // y
476 vmin = max(max(sbb.yi-tbb.ya+sy, tsb.di-ssb.da-sd+tx), ssb.si-tsb.sa+ss-tx);
477 vmax = min(min(sbb.ya-tbb.yi+sy, tsb.da-ssb.di-sd+tx), ssb.sa-tsb.si+ss-tx);
478 omin = sbb.xi + sx;
479 omax = sbb.xa + sx;
480 break;
481 case 2 : // sum
482 vmin = max(max(ssb.si-tsb.sa+ss, 2*(sbb.yi-tbb.ya+sy)+td), 2*(sbb.xi-tbb.xa+sx)-td);
483 vmax = min(min(ssb.sa-tsb.si+ss, 2*(sbb.ya-tbb.yi+sy)+td), 2*(sbb.xa-tbb.xi+sx)-td);
484 omin = ssb.di + sd;
485 omax = ssb.da + sd;
486 break;
487 case 3 : // diff
488 vmin = max(max(ssb.di-tsb.da+sd, 2*(sbb.xi-tbb.xa+sx)-ts), -2*(sbb.ya-tbb.yi+sy)+ts);
489 vmax = min(min(ssb.da-tsb.di+sd, 2*(sbb.xa-tbb.xi+sx)-ts), -2*(sbb.yi-tbb.ya+sy)+ts);
490 omin = ssb.si + ss;
491 omax = ssb.sa + ss;
492 break;
493 }
494 if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)
495 continue;
496
497#if !defined GRAPHITE2_NTRACING
498 if (dbgout)
499 dbgout->setenv(1, reinterpret_cast<void *>(j));
500#endif
501 if (omin > otmax)
502 _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
503 sqr(lmargin - omin + otmax) * _marginWt, false);
504 else if (omax < otmin)
505 _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
506 sqr(lmargin - otmin + omax) * _marginWt, false);
507 else
508 _ranges[i].exclude_with_margins(vmin, vmax, i);
509 anyhits = true;
510 }
511 if (anyhits)
512 isCol = true;
513 }
514 else // no sub-boxes
515 {
516#if !defined GRAPHITE2_NTRACING
517 if (dbgout)
518 dbgout->setenv(1, reinterpret_cast<void *>(-1));
519#endif
520 isCol = true;
521 if (omin > otmax)
522 _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
523 sqr(lmargin - omin + otmax) * _marginWt, false);
524 else if (omax < otmin)
525 _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
526 sqr(lmargin - otmin + omax) * _marginWt, false);
527 else
528 _ranges[i].exclude_with_margins(vmin, vmax, i);
529
530 }
531 }
532 }
533 bool res = true;
534 if (cslot->exclGlyph() > 0 && gc.check(cslot->exclGlyph()) && !isExclusion)
535 {
536 // Set up the bogus slot representing the exclusion glyph.
537 Slot *exclSlot = seg->newSlot();
538 if (!exclSlot)
539 return res;
540 exclSlot->setGlyph(seg, cslot->exclGlyph());
541 Position exclOrigin(slot->origin() + cslot->exclOffset());
542 exclSlot->origin(exclOrigin);
543 SlotCollision exclInfo(seg, exclSlot);
544 res &= mergeSlot(seg, exclSlot, &exclInfo, currShift, isAfter, sameCluster, isCol, true, dbgout );
545 seg->freeSlot(exclSlot);
546 }
547 hasCol |= isCol;
548 return res;
549
550} // end of ShiftCollider::mergeSlot
551
552
553// Figure out where to move the target glyph to, and return the amount to shift by.
554Position ShiftCollider::resolve(GR_MAYBE_UNUSED Segment *seg, bool &isCol, GR_MAYBE_UNUSED json * const dbgout)
555{
556 float tbase;
557 float totalCost = (float)(std::numeric_limits<float>::max() / 2);
558 Position resultPos = Position(0, 0);
559#if !defined GRAPHITE2_NTRACING
560 int bestAxis = -1;
561 if (dbgout)
562 {
563 outputJsonDbgStartSlot(dbgout, seg);
564 *dbgout << "vectors" << json::array;
565 }
566#endif
567 isCol = true;
568 for (int i = 0; i < 4; ++i)
569 {
570 float bestCost = -1;
571 float bestPos;
572 // Calculate the margin depending on whether we are moving diagonally or not:
573 switch (i) {
574 case 0 : // x direction
575 tbase = _currOffset.x;
576 break;
577 case 1 : // y direction
578 tbase = _currOffset.y;
579 break;
580 case 2 : // sum (negatively-sloped diagonals)
581 tbase = _currOffset.x + _currOffset.y;
582 break;
583 case 3 : // diff (positively-sloped diagonals)
584 tbase = _currOffset.x - _currOffset.y;
585 break;
586 }
587 Position testp;
588 bestPos = _ranges[i].closest(0, bestCost) - tbase; // Get the best relative position
589#if !defined GRAPHITE2_NTRACING
590 if (dbgout)
591 outputJsonDbgOneVector(dbgout, seg, i, tbase, bestCost, bestPos) ;
592#endif
593 if (bestCost >= 0.0f)
594 {
595 isCol = false;
596 switch (i) {
597 case 0 : testp = Position(bestPos, _currShift.y); break;
598 case 1 : testp = Position(_currShift.x, bestPos); break;
599 case 2 : testp = Position(0.5f * (_currShift.x - _currShift.y + bestPos), 0.5f * (_currShift.y - _currShift.x + bestPos)); break;
600 case 3 : testp = Position(0.5f * (_currShift.x + _currShift.y + bestPos), 0.5f * (_currShift.x + _currShift.y - bestPos)); break;
601 }
602 if (bestCost < totalCost - 0.01f)
603 {
604 totalCost = bestCost;
605 resultPos = testp;
606#if !defined GRAPHITE2_NTRACING
607 bestAxis = i;
608#endif
609 }
610 }
611 } // end of loop over 4 directions
612
613#if !defined GRAPHITE2_NTRACING
614 if (dbgout)
615 outputJsonDbgEndSlot(dbgout, resultPos, bestAxis, isCol);
616#endif
617
618 return resultPos;
619
620} // end of ShiftCollider::resolve
621
622
623#if !defined GRAPHITE2_NTRACING
624
625void ShiftCollider::outputJsonDbg(json * const dbgout, Segment *seg, int axis)
626{
627 int axisMax = axis;
628 if (axis < 0) // output all axes
629 {
630 *dbgout << "gid" << _target->gid()
631 << "limit" << _limit
632 << "target" << json::object
633 << "origin" << _target->origin()
634 << "margin" << _margin
635 << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
636 << "slantbox" << seg->getFace()->glyphs().slant(_target->gid())
637 << json::close; // target object
638 *dbgout << "ranges" << json::array;
639 axis = 0;
640 axisMax = 3;
641 }
642 for (int iAxis = axis; iAxis <= axisMax; ++iAxis)
643 {
644 *dbgout << json::flat << json::array << _ranges[iAxis].position();
645 for (Zones::const_iterator s = _ranges[iAxis].begin(), e = _ranges[iAxis].end(); s != e; ++s)
646 *dbgout << json::flat << json::array
647 << Position(s->x, s->xm) << s->sm << s->smx << s->c
648 << json::close;
649 *dbgout << json::close;
650 }
651 if (axis < axisMax) // looped through the _ranges array for all axes
652 *dbgout << json::close; // ranges array
653}
654
655void ShiftCollider::outputJsonDbgStartSlot(json * const dbgout, Segment *seg)
656{
657 *dbgout << json::object // slot - not closed till the end of the caller method
658 << "slot" << objectid(dslot(seg, _target))
659 << "gid" << _target->gid()
660 << "limit" << _limit
661 << "target" << json::object
662 << "origin" << _origin
663 << "currShift" << _currShift
664 << "currOffset" << seg->collisionInfo(_target)->offset()
665 << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
666 << "slantBox" << seg->getFace()->glyphs().slant(_target->gid())
667 << "fix" << "shift";
668 *dbgout << json::close; // target object
669}
670
671void ShiftCollider::outputJsonDbgEndSlot(GR_MAYBE_UNUSED json * const dbgout,
672 Position resultPos, int bestAxis, bool isCol)
673{
674 *dbgout << json::close // vectors array
675 << "result" << resultPos
676 //<< "scraping" << _scraping[bestAxis]
677 << "bestAxis" << bestAxis
678 << "stillBad" << isCol
679 << json::close; // slot object
680}
681
682void ShiftCollider::outputJsonDbgOneVector(json * const dbgout, Segment *seg, int axis,
683 float tleft, float bestCost, float bestVal)
684{
685 const char * label;
686 switch (axis)
687 {
688 case 0: label = "x"; break;
689 case 1: label = "y"; break;
690 case 2: label = "sum (NE-SW)"; break;
691 case 3: label = "diff (NW-SE)"; break;
692 default: label = "???"; break;
693 }
694
695 *dbgout << json::object // vector
696 << "direction" << label
697 << "targetMin" << tleft;
698
699 outputJsonDbgRemovals(dbgout, axis, seg);
700
701 *dbgout << "ranges";
702 outputJsonDbg(dbgout, seg, axis);
703
704 *dbgout << "bestCost" << bestCost
705 << "bestVal" << bestVal + tleft
706 << json::close; // vectors object
707}
708
709void ShiftCollider::outputJsonDbgRemovals(json * const dbgout, int axis, Segment *seg)
710{
711 *dbgout << "removals" << json::array;
712 _ranges[axis].jsonDbgOut(seg);
713 *dbgout << json::close; // removals array
714}
715
716#endif // !defined GRAPHITE2_NTRACING
717
718
719//// KERN-COLLIDER ////
720
721inline
722static float localmax (float al, float au, float bl, float bu, float x)
723{
724 if (al < bl)
725 { if (au < bu) return au < x ? au : x; }
726 else if (au > bu) return bl < x ? bl : x;
727 return x;
728}
729
730inline
731static float localmin(float al, float au, float bl, float bu, float x)
732{
733 if (bl > al)
734 { if (bu > au) return bl > x ? bl : x; }
735 else if (au > bu) return al > x ? al : x;
736 return x;
737}
738
739// Return the given edge of the glyph at height y, taking any slant box into account.
740static float get_edge(Segment *seg, const Slot *s, const Position &shift, float y, float width, float margin, bool isRight)
741{
742 const GlyphCache &gc = seg->getFace()->glyphs();
743 unsigned short gid = s->gid();
744 float sx = s->origin().x + shift.x;
745 float sy = s->origin().y + shift.y;
746 uint8 numsub = gc.numSubBounds(gid);
747 float res = isRight ? (float)-1e38 : (float)1e38;
748
749 if (numsub > 0)
750 {
751 for (int i = 0; i < numsub; ++i)
752 {
753 const BBox &sbb = gc.getSubBoundingBBox(gid, i);
754 const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, i);
755 if (sy + sbb.yi - margin > y + width / 2 || sy + sbb.ya + margin < y - width / 2)
756 continue;
757 if (isRight)
758 {
759 float x = sx + sbb.xa + margin;
760 if (x > res)
761 {
762 float td = sx - sy + ssb.da + margin + y;
763 float ts = sx + sy + ssb.sa + margin - y;
764 x = localmax(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x);
765 if (x > res)
766 res = x;
767 }
768 }
769 else
770 {
771 float x = sx + sbb.xi - margin;
772 if (x < res)
773 {
774 float td = sx - sy + ssb.di - margin + y;
775 float ts = sx + sy + ssb.si - margin - y;
776 x = localmin(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x);
777 if (x < res)
778 res = x;
779 }
780 }
781 }
782 }
783 else
784 {
785 const BBox &bb = gc.getBoundingBBox(gid);
786 const SlantBox &sb = gc.getBoundingSlantBox(gid);
787 if (sy + bb.yi - margin > y + width / 2 || sy + bb.ya + margin < y - width / 2)
788 return res;
789 float td = sx - sy + y;
790 float ts = sx + sy - y;
791 if (isRight)
792 res = localmax(td + sb.da - width / 2, td + sb.da + width / 2, ts + sb.sa - width / 2, ts + sb.sa + width / 2, sx + bb.xa) + margin;
793 else
794 res = localmin(td + sb.di - width / 2, td + sb.di + width / 2, ts + sb.si - width / 2, ts + sb.si + width / 2, sx + bb.xi) - margin;
795 }
796 return res;
797}
798
799
800bool KernCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin,
801 const Position &currShift, const Position &offsetPrev, int dir,
802 float ymin, float ymax, GR_MAYBE_UNUSED json * const dbgout)
803{
804 const GlyphCache &gc = seg->getFace()->glyphs();
805 const Slot *base = aSlot;
806 // const Slot *last = aSlot;
807 const Slot *s;
808 int numSlices;
809 while (base->attachedTo())
810 base = base->attachedTo();
811 if (margin < 10) margin = 10;
812
813 _limit = limit;
814 _offsetPrev = offsetPrev; // kern from a previous pass
815
816 // Calculate the height of the glyph and how many horizontal slices to use.
817 if (_maxy >= 1e37f)
818 {
819 _sliceWidth = margin / 1.5f;
820 _maxy = ymax + margin;
821 _miny = ymin - margin;
822 numSlices = int((_maxy - _miny + 2) / (_sliceWidth / 1.5f) + 1.f); // +2 helps with rounding errors
823 _edges.clear();
824 _edges.insert(_edges.begin(), numSlices, (dir & 1) ? 1e38f : -1e38f);
825 _xbound = (dir & 1) ? (float)1e38f : (float)-1e38f;
826 }
827 else if (_maxy != ymax || _miny != ymin)
828 {
829 if (_miny != ymin)
830 {
831 numSlices = int((ymin - margin - _miny) / _sliceWidth - 1);
832 _miny += numSlices * _sliceWidth;
833 if (numSlices < 0)
834 _edges.insert(_edges.begin(), -numSlices, (dir & 1) ? 1e38f : -1e38f);
835 else if ((unsigned)numSlices < _edges.size()) // this shouldn't fire since we always grow the range
836 {
837 Vector<float>::iterator e = _edges.begin();
838 while (numSlices--)
839 ++e;
840 _edges.erase(_edges.begin(), e);
841 }
842 }
843 if (_maxy != ymax)
844 {
845 numSlices = int((ymax + margin - _miny) / _sliceWidth + 1);
846 _maxy = numSlices * _sliceWidth + _miny;
847 if (numSlices > (int)_edges.size())
848 _edges.insert(_edges.end(), numSlices - _edges.size(), (dir & 1) ? 1e38f : -1e38f);
849 else if (numSlices < (int)_edges.size()) // this shouldn't fire since we always grow the range
850 {
851 while ((int)_edges.size() > numSlices)
852 _edges.pop_back();
853 }
854 }
855 goto done;
856 }
857 numSlices = int(_edges.size());
858
859#if !defined GRAPHITE2_NTRACING
860 // Debugging
861 _seg = seg;
862 _slotNear.clear();
863 _slotNear.insert(_slotNear.begin(), numSlices, NULL);
864 _nearEdges.clear();
865 _nearEdges.insert(_nearEdges.begin(), numSlices, (dir & 1) ? -1e38f : +1e38f);
866#endif
867
868 // Determine the trailing edge of each slice (ie, left edge for a RTL glyph).
869 for (s = base; s; s = s->nextInCluster(s))
870 {
871 SlotCollision *c = seg->collisionInfo(s);
872 if (!gc.check(s->gid()))
873 return false;
874 const BBox &bs = gc.getBoundingBBox(s->gid());
875 float x = s->origin().x + c->shift().x + ((dir & 1) ? bs.xi : bs.xa);
876 // Loop over slices.
877 // Note smin might not be zero if glyph s is not at the bottom of the cluster; similarly for smax.
878 float toffset = c->shift().y - _miny + 1 + s->origin().y;
879 int smin = max(0, int((bs.yi + toffset) / _sliceWidth));
880 int smax = min(numSlices - 1, int((bs.ya + toffset) / _sliceWidth + 1));
881 for (int i = smin; i <= smax; ++i)
882 {
883 float t;
884 float y = _miny - 1 + (i + .5f) * _sliceWidth; // vertical center of slice
885 if ((dir & 1) && x < _edges[i])
886 {
887 t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, false);
888 if (t < _edges[i])
889 {
890 _edges[i] = t;
891 if (t < _xbound)
892 _xbound = t;
893 }
894 }
895 else if (!(dir & 1) && x > _edges[i])
896 {
897 t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, true);
898 if (t > _edges[i])
899 {
900 _edges[i] = t;
901 if (t > _xbound)
902 _xbound = t;
903 }
904 }
905 }
906 }
907 done:
908 _mingap = (float)1e37; // less than 1e38 s.t. 1e38-_mingap is really big
909 _target = aSlot;
910 _margin = margin;
911 _currShift = currShift;
912 return true;
913} // end of KernCollider::initSlot
914
915
916// Determine how much the target slot needs to kern away from the given slot.
917// In other words, merge information from given slot's position with what the target slot knows
918// about how it can kern.
919// Return false if we know there is no collision, true if we think there might be one.
920bool KernCollider::mergeSlot(Segment *seg, Slot *slot, const Position &currShift, float currSpace, int dir, GR_MAYBE_UNUSED json * const dbgout)
921{
922 int rtl = (dir & 1) * 2 - 1;
923 if (!seg->getFace()->glyphs().check(slot->gid()))
924 return false;
925 const Rect &bb = seg->theGlyphBBoxTemporary(slot->gid());
926 const float sx = slot->origin().x + currShift.x;
927 float x = (sx + (rtl > 0 ? bb.tr.x : bb.bl.x)) * rtl;
928 // this isn't going to reduce _mingap so skip
929 if (_hit && x < rtl * (_xbound - _mingap - currSpace))
930 return false;
931
932 const float sy = slot->origin().y + currShift.y;
933 int smin = max(1, int((bb.bl.y + (1 - _miny + sy)) / _sliceWidth + 1)) - 1;
934 int smax = min((int)_edges.size() - 2, int((bb.tr.y + (1 - _miny + sy)) / _sliceWidth + 1)) + 1;
935 if (smin > smax)
936 return false;
937 bool collides = false;
938 bool nooverlap = true;
939
940 for (int i = smin; i <= smax; ++i)
941 {
942 float here = _edges[i] * rtl;
943 if (here > (float)9e37)
944 continue;
945 if (!_hit || x > here - _mingap - currSpace)
946 {
947 float y = (float)(_miny - 1 + (i + .5f) * _sliceWidth); // vertical center of slice
948 // 2 * currSpace to account for the space that is already separating them and the space we want to add
949 float m = get_edge(seg, slot, currShift, y, _sliceWidth, 0., rtl > 0) * rtl + 2 * currSpace;
950 if (m < (float)-8e37) // only true if the glyph has a gap in it
951 continue;
952 nooverlap = false;
953 float t = here - m;
954 // _mingap is positive to shrink
955 if (t < _mingap || (!_hit && !collides))
956 {
957 _mingap = t;
958 collides = true;
959 }
960#if !defined GRAPHITE2_NTRACING
961 // Debugging - remember the closest neighboring edge for this slice.
962 if (m > rtl * _nearEdges[i])
963 {
964 _slotNear[i] = slot;
965 _nearEdges[i] = m * rtl;
966 }
967#endif
968 }
969 else
970 nooverlap = false;
971 }
972 if (nooverlap)
973 _mingap = max(_mingap, _xbound - rtl * (currSpace + _margin + x));
974 if (collides && !nooverlap)
975 _hit = true;
976 return collides | nooverlap; // note that true is not a necessarily reliable value
977
978} // end of KernCollider::mergeSlot
979
980
981// Return the amount to kern by.
982Position KernCollider::resolve(GR_MAYBE_UNUSED Segment *seg, GR_MAYBE_UNUSED Slot *slot,
983 int dir, GR_MAYBE_UNUSED json * const dbgout)
984{
985 float resultNeeded = (1 - 2 * (dir & 1)) * _mingap;
986 // float resultNeeded = (1 - 2 * (dir & 1)) * (_mingap - margin);
987 float result = min(_limit.tr.x - _offsetPrev.x, max(resultNeeded, _limit.bl.x - _offsetPrev.x));
988
989#if !defined GRAPHITE2_NTRACING
990 if (dbgout)
991 {
992 *dbgout << json::object // slot
993 << "slot" << objectid(dslot(seg, _target))
994 << "gid" << _target->gid()
995 << "limit" << _limit
996 << "miny" << _miny
997 << "maxy" << _maxy
998 << "slicewidth" << _sliceWidth
999 << "target" << json::object
1000 << "origin" << _target->origin()
1001 //<< "currShift" << _currShift
1002 << "offsetPrev" << _offsetPrev
1003 << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
1004 << "slantBox" << seg->getFace()->glyphs().slant(_target->gid())
1005 << "fix" << "kern"
1006 << json::close; // target object
1007
1008 *dbgout << "slices" << json::array;
1009 for (int is = 0; is < (int)_edges.size(); is++)
1010 {
1011 *dbgout << json::flat << json::object
1012 << "i" << is
1013 << "targetEdge" << _edges[is]
1014 << "neighbor" << objectid(dslot(seg, _slotNear[is]))
1015 << "nearEdge" << _nearEdges[is]
1016 << json::close;
1017 }
1018 *dbgout << json::close; // slices array
1019
1020 *dbgout
1021 << "xbound" << _xbound
1022 << "minGap" << _mingap
1023 << "needed" << resultNeeded
1024 << "result" << result
1025 << "stillBad" << (result != resultNeeded)
1026 << json::close; // slot object
1027 }
1028#endif
1029
1030 return Position(result, 0.);
1031
1032} // end of KernCollider::resolve
1033
1034void KernCollider::shift(const Position &mv, int dir)
1035{
1036 for (Vector<float>::iterator e = _edges.begin(); e != _edges.end(); ++e)
1037 *e += mv.x;
1038 _xbound += (1 - 2 * (dir & 1)) * mv.x;
1039}
1040
1041//// SLOT-COLLISION ////
1042
1043// Initialize the collision attributes for the given slot.
1044SlotCollision::SlotCollision(Segment *seg, Slot *slot)
1045{
1046 initFromSlot(seg, slot);
1047}
1048
1049void SlotCollision::initFromSlot(Segment *seg, Slot *slot)
1050{
1051 // Initialize slot attributes from glyph attributes.
1052 // The order here must match the order in the grcompiler code,
1053 // GrcSymbolTable::AssignInternalGlyphAttrIDs.
1054 uint16 gid = slot->gid();
1055 uint16 aCol = seg->silf()->aCollision(); // flags attr ID
1056 const GlyphFace * glyphFace = seg->getFace()->glyphs().glyphSafe(gid);
1057 if (!glyphFace)
1058 return;
1059 const sparse &p = glyphFace->attrs();
1060 _flags = p[aCol];
1061 _limit = Rect(Position(int16(p[aCol+1]), int16(p[aCol+2])),
1062 Position(int16(p[aCol+3]), int16(p[aCol+4])));
1063 _margin = p[aCol+5];
1064 _marginWt = p[aCol+6];
1065
1066 _seqClass = p[aCol+7];
1067 _seqProxClass = p[aCol+8];
1068 _seqOrder = p[aCol+9];
1069 _seqAboveXoff = p[aCol+10];
1070 _seqAboveWt = p[aCol+11];
1071 _seqBelowXlim = p[aCol+12];
1072 _seqBelowWt = p[aCol+13];
1073 _seqValignHt = p[aCol+14];
1074 _seqValignWt = p[aCol+15];
1075
1076 // These attributes do not have corresponding glyph attribute:
1077 _exclGlyph = 0;
1078 _exclOffset = Position(0, 0);
1079}
1080
1081float SlotCollision::getKern(int dir) const
1082{
1083 if ((_flags & SlotCollision::COLL_KERN) != 0)
1084 return float(_shift.x * ((dir & 1) ? -1 : 1));
1085 else
1086 return 0;
1087}
1088
1089bool SlotCollision::ignore() const
1090{
1091 return ((flags() & SlotCollision::COLL_IGNORE) || (flags() & SlotCollision::COLL_ISSPACE));
1092}
1093