diff options
Diffstat (limited to 'Build/source/libs/graphite2/graphite2-src/src/Collider.cpp')
| -rw-r--r-- | Build/source/libs/graphite2/graphite2-src/src/Collider.cpp | 1115 |
1 files changed, 0 insertions, 1115 deletions
diff --git a/Build/source/libs/graphite2/graphite2-src/src/Collider.cpp b/Build/source/libs/graphite2/graphite2-src/src/Collider.cpp deleted file mode 100644 index 1929b39a58e..00000000000 --- a/Build/source/libs/graphite2/graphite2-src/src/Collider.cpp +++ /dev/null @@ -1,1115 +0,0 @@ -/* GRAPHITE2 LICENSING - - Copyright 2010, SIL International - All rights reserved. - - This library is free software; you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published - by the Free Software Foundation; either version 2.1 of License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should also have received a copy of the GNU Lesser General Public - License along with this library in the file named "LICENSE". - If not, write to the Free Software Foundation, 51 Franklin Street, - Suite 500, Boston, MA 02110-1335, USA or visit their web page on the - internet at http://www.fsf.org/licenses/lgpl.html. - -Alternatively, the contents of this file may be used under the terms of the -Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public -License, as published by the Free Software Foundation, either version 2 -of the License or (at your option) any later version. -*/ -#include <algorithm> -#include <limits> -#include <cmath> -#include <string> -#include <functional> -#include "inc/Collider.h" -#include "inc/Segment.h" -#include "inc/Slot.h" -#include "inc/GlyphCache.h" -#include "inc/Sparse.h" - -#define ISQRT2 0.707106781f - -// Possible rounding error for subbox boundaries: 0.016 = 1/64 = 1/256 * 4 -// (values in font range from 0..256) -// #define SUBBOX_RND_ERR 0.016 - -using namespace graphite2; - -//// SHIFT-COLLIDER //// - -// Initialize the Collider to hold the basic movement limits for the -// target slot, the one we are focusing on fixing. -bool ShiftCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin, float marginWeight, - const Position &currShift, const Position &currOffset, int dir, GR_MAYBE_UNUSED json * const dbgout) -{ - int i; - float mx, mn; - float a, shift; - const GlyphCache &gc = seg->getFace()->glyphs(); - unsigned short gid = aSlot->gid(); - if (!gc.check(gid)) - return false; - const BBox &bb = gc.getBoundingBBox(gid); - const SlantBox &sb = gc.getBoundingSlantBox(gid); - //float sx = aSlot->origin().x + currShift.x; - //float sy = aSlot->origin().y + currShift.y; - if (currOffset.x != 0.f || currOffset.y != 0.f) - _limit = Rect(limit.bl - currOffset, limit.tr - currOffset); - else - _limit = limit; - // For a ShiftCollider, these indices indicate which vector we are moving by: - // 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 - for (i = 0; i < 4; ++i) - { - switch (i) { - case 0 : // x direction - mn = _limit.bl.x + currOffset.x; - mx = _limit.tr.x + currOffset.x; - _len[i] = bb.xa - bb.xi; - a = currOffset.y + currShift.y; - _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a); - break; - case 1 : // y direction - mn = _limit.bl.y + currOffset.y; - mx = _limit.tr.y + currOffset.y; - _len[i] = bb.ya - bb.yi; - a = currOffset.x + currShift.x; - _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a); - break; - case 2 : // sum (negatively sloped diagonal boundaries) - // pick closest x,y limit boundaries in s direction - shift = currOffset.x + currOffset.y + currShift.x + currShift.y; - mn = -2 * min(currShift.x - _limit.bl.x, currShift.y - _limit.bl.y) + shift; - mx = 2 * min(_limit.tr.x - currShift.x, _limit.tr.y - currShift.y) + shift; - _len[i] = sb.sa - sb.si; - a = currOffset.x - currOffset.y + currShift.x - currShift.y; - _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a); - break; - case 3 : // diff (positively sloped diagonal boundaries) - // pick closest x,y limit boundaries in d direction - shift = currOffset.x - currOffset.y + currShift.x - currShift.y; - mn = -2 * min(currShift.x - _limit.bl.x, _limit.tr.y - currShift.y) + shift; - mx = 2 * min(_limit.tr.x - currShift.x, currShift.y - _limit.bl.y) + shift; - _len[i] = sb.da - sb.di; - a = currOffset.x + currOffset.y + currShift.x + currShift.y; - _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a); - break; - } - } - - _target = aSlot; - if ((dir & 1) == 0) - { - // For LTR, switch and negate x limits. - _limit.bl.x = -1 * limit.tr.x; - //_limit.tr.x = -1 * limit.bl.x; - } - _currOffset = currOffset; - _currShift = currShift; - _origin = aSlot->origin() - currOffset; // the original anchor position of the glyph - - _margin = margin; - _marginWt = marginWeight; - - SlotCollision *c = seg->collisionInfo(aSlot); - _seqClass = c->seqClass(); - _seqProxClass = c->seqProxClass(); - _seqOrder = c->seqOrder(); - return true; -} - -template <class O> -float sdm(float vi, float va, float mx, float my, O op) -{ - float res = 2 * mx - vi; - if (op(res, vi + 2 * my)) - { - res = va + 2 * my; - if (op(res, 2 * mx - va)) - res = mx + my; - } - return res; -} - -// 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 -void 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) -{ - float a, c; - switch (axis) { - case 0 : - if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0) - { - a = org.y + 0.5f * (bb.yi + bb.ya); - c = 0.5f * (bb.xi + bb.xa); - if (isx) - _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, m, - (minright ? box.tr.x : box.bl.x) - c, a, 0, false); - else - _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, 0, 0, org.y, - m * (a * a + sqr((minright ? box.tr.y : box.bl.y) - 0.5f * (bb.yi + bb.ya))), false); - } - break; - case 1 : - if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0) - { - a = org.x + 0.5f * (bb.xi + bb.xa); - c = 0.5f * (bb.yi + bb.ya); - if (isx) - _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, 0, 0, org.x, - m * (a * a + sqr((minright ? box.tr.x : box.bl.x) - 0.5f * (bb.xi + bb.xa))), false); - else - _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, m, - (minright ? box.tr.y : box.bl.y) - c, a, 0, false); - } - break; - case 2 : - 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) - { - float d = org.x - org.y + 0.5f * (sb.di + sb.da); - c = 0.5f * (sb.si + sb.sa); - float smax = min(2 * box.tr.x - d, 2 * box.tr.y + d); - float smin = max(2 * box.bl.x - d, 2 * box.bl.y + d); - if (smin > smax) return; - float si; - a = d; - if (isx) - si = 2 * (minright ? box.tr.x : box.bl.x) - a; - else - si = 2 * (minright ? box.tr.y : box.bl.y) + a; - _ranges[axis].weighted<SD>(smin - c, smax - c, weight / 2, a, m / 2, si, 0, 0, isx); - } - break; - case 3 : - 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) - { - float s = org.x + org.y + 0.5f * (sb.si + sb.sa); - c = 0.5f * (sb.di + sb.da); - float dmax = min(2 * box.tr.x - s, s - 2 * box.bl.y); - float dmin = max(2 * box.bl.x - s, s - 2 * box.tr.y); - if (dmin > dmax) return; - float di; - a = s; - if (isx) - di = 2 * (minright ? box.tr.x : box.bl.x) - a; - else - di = 2 * (minright ? box.tr.y : box.bl.y) + a; - _ranges[axis].weighted<SD>(dmin - c, dmax - c, weight / 2, a, m / 2, di, 0, 0, !isx); - } - break; - default : - break; - } - return; -} - -// Mark an area with an absolute cost, making it completely inaccessible. -inline void ShiftCollider::removeBox(const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, int axis) -{ - float c; - switch (axis) { - case 0 : - if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0) - { - c = 0.5f * (bb.xi + bb.xa); - _ranges[axis].exclude(box.bl.x - c, box.tr.x - c); - } - break; - case 1 : - if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0) - { - c = 0.5f * (bb.yi + bb.ya); - _ranges[axis].exclude(box.bl.y - c, box.tr.y - c); - } - break; - case 2 : - 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 - && box.width() > 0 && box.height() > 0) - { - float di = org.x - org.y + sb.di; - float da = org.x - org.y + sb.da; - float smax = sdm(di, da, box.tr.x, box.tr.y, std::greater<float>()); - float smin = sdm(da, di, box.bl.x, box.bl.y, std::less<float>()); - c = 0.5f * (sb.si + sb.sa); - _ranges[axis].exclude(smin - c, smax - c); - } - break; - case 3 : - 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 - && box.width() > 0 && box.height() > 0) - { - float si = org.x + org.y + sb.si; - float sa = org.x + org.y + sb.sa; - float dmax = sdm(si, sa, box.tr.x, -box.bl.y, std::greater<float>()); - float dmin = sdm(sa, si, box.bl.x, -box.tr.y, std::less<float>()); - c = 0.5f * (sb.di + sb.da); - _ranges[axis].exclude(dmin - c, dmax - c); - } - break; - default : - break; - } - return; -} - -// Adjust the movement limits for the target to avoid having it collide -// with the given neighbor slot. Also determine if there is in fact a collision -// between the target and the given slot. -bool ShiftCollider::mergeSlot(Segment *seg, Slot *slot, const SlotCollision *cslot, const Position &currShift, - bool isAfter, // slot is logically after _target - bool sameCluster, bool &hasCol, bool isExclusion, - GR_MAYBE_UNUSED json * const dbgout ) -{ - bool isCol = false; - const float sx = slot->origin().x - _origin.x + currShift.x; - const float sy = slot->origin().y - _origin.y + currShift.y; - const float sd = sx - sy; - const float ss = sx + sy; - float vmin, vmax; - float omin, omax, otmin, otmax; - float cmin, cmax; // target limits - float torg; - const GlyphCache &gc = seg->getFace()->glyphs(); - const unsigned short gid = slot->gid(); - if (!gc.check(gid)) - return false; - const BBox &bb = gc.getBoundingBBox(gid); - - // SlotCollision * cslot = seg->collisionInfo(slot); - int orderFlags = 0; - bool sameClass = _seqProxClass == 0 && cslot->seqClass() == _seqClass; - if (sameCluster && _seqClass - && (sameClass || (_seqProxClass != 0 && cslot->seqClass() == _seqProxClass))) - // Force the target glyph to be in the specified direction from the slot we're testing. - orderFlags = _seqOrder; - - // short circuit if only interested in direct collision and we are out of range - if (orderFlags || (sx + bb.xa + _margin >= _limit.bl.x && sx + bb.xi - _margin <= _limit.tr.x) - || (sy + bb.ya + _margin >= _limit.bl.y && sy + bb.yi - _margin <= _limit.tr.y)) - - { - const float tx = _currOffset.x + _currShift.x; - const float ty = _currOffset.y + _currShift.y; - const float td = tx - ty; - const float ts = tx + ty; - const SlantBox &sb = gc.getBoundingSlantBox(gid); - const unsigned short tgid = _target->gid(); - const BBox &tbb = gc.getBoundingBBox(tgid); - const SlantBox &tsb = gc.getBoundingSlantBox(tgid); - float seq_above_wt = cslot->seqAboveWt(); - float seq_below_wt = cslot->seqBelowWt(); - float seq_valign_wt = cslot->seqValignWt(); - float lmargin; - // if isAfter, invert orderFlags for diagonal orders. - if (isAfter) - { - // invert appropriate bits - orderFlags ^= (sameClass ? 0x3F : 0x3); - // consider 2 bits at a time, non overlapping. If both bits set, clear them - orderFlags = orderFlags ^ ((((orderFlags >> 1) & orderFlags) & 0x15) * 3); - } - -#if !defined GRAPHITE2_NTRACING - if (dbgout) - dbgout->setenv(0, slot); -#endif - - // Process main bounding octabox. - for (int i = 0; i < 4; ++i) - { - switch (i) { - case 0 : // x direction - vmin = max(max(bb.xi - tbb.xa + sx, sb.di - tsb.da + ty + sd), sb.si - tsb.sa - ty + ss); - vmax = min(min(bb.xa - tbb.xi + sx, sb.da - tsb.di + ty + sd), sb.sa - tsb.si - ty + ss); - otmin = tbb.yi + ty; - otmax = tbb.ya + ty; - omin = bb.yi + sy; - omax = bb.ya + sy; - torg = _currOffset.x; - cmin = _limit.bl.x + torg; - cmax = _limit.tr.x - tbb.xi + tbb.xa + torg; - lmargin = _margin; - break; - case 1 : // y direction - vmin = max(max(bb.yi - tbb.ya + sy, tsb.di - sb.da + tx - sd), sb.si - tsb.sa - tx + ss); - vmax = min(min(bb.ya - tbb.yi + sy, tsb.da - sb.di + tx - sd), sb.sa - tsb.si - tx + ss); - otmin = tbb.xi + tx; - otmax = tbb.xa + tx; - omin = bb.xi + sx; - omax = bb.xa + sx; - torg = _currOffset.y; - cmin = _limit.bl.y + torg; - cmax = _limit.tr.y - tbb.yi + tbb.ya + torg; - lmargin = _margin; - break; - case 2 : // sum - moving along the positively-sloped vector, so the boundaries are the - // negatively-sloped boundaries. - vmin = max(max(sb.si - tsb.sa + ss, 2 * (bb.yi - tbb.ya + sy) + td), 2 * (bb.xi - tbb.xa + sx) - td); - vmax = min(min(sb.sa - tsb.si + ss, 2 * (bb.ya - tbb.yi + sy) + td), 2 * (bb.xa - tbb.xi + sx) - td); - otmin = tsb.di + td; - otmax = tsb.da + td; - omin = sb.di + sd; - omax = sb.da + sd; - torg = _currOffset.x + _currOffset.y; - cmin = _limit.bl.x + _limit.bl.y + torg; - cmax = _limit.tr.x + _limit.tr.y - tsb.si + tsb.sa + torg; - lmargin = _margin / ISQRT2; - break; - case 3 : // diff - moving along the negatively-sloped vector, so the boundaries are the - // positively-sloped boundaries. - vmin = max(max(sb.di - tsb.da + sd, 2 * (bb.xi - tbb.xa + sx) - ts), -2 * (bb.ya - tbb.yi + sy) + ts); - vmax = min(min(sb.da - tsb.di + sd, 2 * (bb.xa - tbb.xi + sx) - ts), -2 * (bb.yi - tbb.ya + sy) + ts); - otmin = tsb.si + ts; - otmax = tsb.sa + ts; - omin = sb.si + ss; - omax = sb.sa + ss; - torg = _currOffset.x - _currOffset.y; - cmin = _limit.bl.x - _limit.tr.y + torg; - cmax = _limit.tr.x - _limit.bl.y - tsb.di + tsb.da + torg; - lmargin = _margin / ISQRT2; - break; - default : - continue; - } - -#if !defined GRAPHITE2_NTRACING - if (dbgout) - dbgout->setenv(1, reinterpret_cast<void *>(-1)); -#define DBGTAG(x) if (dbgout) dbgout->setenv(1, reinterpret_cast<void *>(-x)); -#else -#define DBGTAG(x) -#endif - - if (orderFlags) - { - Position org(tx, ty); - float xminf = _limit.bl.x + _currOffset.x + tbb.xi; - float xpinf = _limit.tr.x + _currOffset.x + tbb.xa; - float ypinf = _limit.tr.y + _currOffset.y + tbb.ya; - float yminf = _limit.bl.y + _currOffset.y + tbb.yi; - switch (orderFlags) { - case SlotCollision::SEQ_ORDER_RIGHTUP : - { - float r1Xedge = cslot->seqAboveXoff() + 0.5f * (bb.xi + bb.xa) + sx; - float r3Xedge = cslot->seqBelowXlim() + bb.xa + sx + 0.5f * (tbb.xa - tbb.xi); - float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy; - - // DBGTAG(1x) means the regions are up and right - // region 1 - DBGTAG(11) - addBox_slope(true, Rect(Position(xminf, r2Yedge), Position(r1Xedge, ypinf)), - tbb, tsb, org, 0, seq_above_wt, true, i); - // region 2 - DBGTAG(12) - removeBox(Rect(Position(xminf, yminf), Position(r3Xedge, r2Yedge)), tbb, tsb, org, i); - // region 3, which end is zero is irrelevant since m weight is 0 - DBGTAG(13) - addBox_slope(true, Rect(Position(r3Xedge, yminf), Position(xpinf, r2Yedge - cslot->seqValignHt())), - tbb, tsb, org, seq_below_wt, 0, true, i); - // region 4 - DBGTAG(14) - addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge), Position(xpinf, r2Yedge + cslot->seqValignHt())), - tbb, tsb, org, 0, seq_valign_wt, true, i); - // region 5 - DBGTAG(15) - addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge - cslot->seqValignHt()), Position(xpinf, r2Yedge)), - tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i); - break; - } - case SlotCollision::SEQ_ORDER_LEFTDOWN : - { - float r1Xedge = 0.5f * (bb.xi + bb.xa) + cslot->seqAboveXoff() + sx; - float r3Xedge = bb.xi - cslot->seqBelowXlim() + sx - 0.5f * (tbb.xa - tbb.xi); - float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy; - // DBGTAG(2x) means the regions are up and right - // region 1 - DBGTAG(21) - addBox_slope(true, Rect(Position(r1Xedge, yminf), Position(xpinf, r2Yedge)), - tbb, tsb, org, 0, seq_above_wt, false, i); - // region 2 - DBGTAG(22) - removeBox(Rect(Position(r3Xedge, r2Yedge), Position(xpinf, ypinf)), tbb, tsb, org, i); - // region 3 - DBGTAG(23) - addBox_slope(true, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()), Position(r3Xedge, ypinf)), - tbb, tsb, org, seq_below_wt, 0, false, i); - // region 4 - DBGTAG(24) - addBox_slope(false, Rect(Position(xminf, r2Yedge), Position(sx + bb.xa, r2Yedge + cslot->seqValignHt())), - tbb, tsb, org, 0, seq_valign_wt, true, i); - // region 5 - DBGTAG(25) - addBox_slope(false, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()), - Position(sx + bb.xa, r2Yedge)), tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i); - break; - } - case SlotCollision::SEQ_ORDER_NOABOVE : // enforce neighboring glyph being above - DBGTAG(31); - removeBox(Rect(Position(bb.xi - tbb.xa + sx, sy + bb.ya), - Position(bb.xa - tbb.xi + sx, ypinf)), tbb, tsb, org, i); - break; - case SlotCollision::SEQ_ORDER_NOBELOW : // enforce neighboring glyph being below - DBGTAG(32); - removeBox(Rect(Position(bb.xi - tbb.xa + sx, yminf), - Position(bb.xa - tbb.xi + sx, sy + bb.yi)), tbb, tsb, org, i); - break; - case SlotCollision::SEQ_ORDER_NOLEFT : // enforce neighboring glyph being to the left - DBGTAG(33) - removeBox(Rect(Position(xminf, bb.yi - tbb.ya + sy), - Position(bb.xi - tbb.xa + sx, bb.ya - tbb.yi + sy)), tbb, tsb, org, i); - break; - case SlotCollision::SEQ_ORDER_NORIGHT : // enforce neighboring glyph being to the right - DBGTAG(34) - removeBox(Rect(Position(bb.xa - tbb.xi + sx, bb.yi - tbb.ya + sy), - Position(xpinf, bb.ya - tbb.yi + sy)), tbb, tsb, org, i); - break; - default : - break; - } - } - - if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin) - continue; - - // Process sub-boxes that are defined for this glyph. - // We only need to do this if there was in fact a collision with the main octabox. - uint8 numsub = gc.numSubBounds(gid); - if (numsub > 0) - { - bool anyhits = false; - for (int j = 0; j < numsub; ++j) - { - const BBox &sbb = gc.getSubBoundingBBox(gid, j); - const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, j); - switch (i) { - case 0 : // x - vmin = max(max(sbb.xi-tbb.xa+sx, ssb.di-tsb.da+sd+ty), ssb.si-tsb.sa+ss-ty); - vmax = min(min(sbb.xa-tbb.xi+sx, ssb.da-tsb.di+sd+ty), ssb.sa-tsb.si+ss-ty); - omin = sbb.yi + sy; - omax = sbb.ya + sy; - break; - case 1 : // y - vmin = max(max(sbb.yi-tbb.ya+sy, tsb.di-ssb.da-sd+tx), ssb.si-tsb.sa+ss-tx); - vmax = min(min(sbb.ya-tbb.yi+sy, tsb.da-ssb.di-sd+tx), ssb.sa-tsb.si+ss-tx); - omin = sbb.xi + sx; - omax = sbb.xa + sx; - break; - case 2 : // sum - vmin = max(max(ssb.si-tsb.sa+ss, 2*(sbb.yi-tbb.ya+sy)+td), 2*(sbb.xi-tbb.xa+sx)-td); - vmax = min(min(ssb.sa-tsb.si+ss, 2*(sbb.ya-tbb.yi+sy)+td), 2*(sbb.xa-tbb.xi+sx)-td); - omin = ssb.di + sd; - omax = ssb.da + sd; - break; - case 3 : // diff - vmin = max(max(ssb.di-tsb.da+sd, 2*(sbb.xi-tbb.xa+sx)-ts), -2*(sbb.ya-tbb.yi+sy)+ts); - vmax = min(min(ssb.da-tsb.di+sd, 2*(sbb.xa-tbb.xi+sx)-ts), -2*(sbb.yi-tbb.ya+sy)+ts); - omin = ssb.si + ss; - omax = ssb.sa + ss; - break; - } - if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin) - continue; - -#if !defined GRAPHITE2_NTRACING - if (dbgout) - dbgout->setenv(1, reinterpret_cast<void *>(j)); -#endif - if (omin > otmax) - _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0, - sqr(lmargin - omin + otmax) * _marginWt, false); - else if (omax < otmin) - _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0, - sqr(lmargin - otmin + omax) * _marginWt, false); - else - _ranges[i].exclude_with_margins(vmin, vmax, i); - anyhits = true; - } - if (anyhits) - isCol = true; - } - else // no sub-boxes - { -#if !defined GRAPHITE2_NTRACING - if (dbgout) - dbgout->setenv(1, reinterpret_cast<void *>(-1)); -#endif - isCol = true; - if (omin > otmax) - _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0, - sqr(lmargin - omin + otmax) * _marginWt, false); - else if (omax < otmin) - _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0, - sqr(lmargin - otmin + omax) * _marginWt, false); - else - _ranges[i].exclude_with_margins(vmin, vmax, i); - - } - } - } - bool res = true; - if (cslot->exclGlyph() > 0 && gc.check(cslot->exclGlyph()) && !isExclusion) - { - // Set up the bogus slot representing the exclusion glyph. - Slot *exclSlot = seg->newSlot(); - if (!exclSlot) - return res; - exclSlot->setGlyph(seg, cslot->exclGlyph()); - Position exclOrigin(slot->origin() + cslot->exclOffset()); - exclSlot->origin(exclOrigin); - SlotCollision exclInfo(seg, exclSlot); - res &= mergeSlot(seg, exclSlot, &exclInfo, currShift, isAfter, sameCluster, isCol, true, dbgout ); - seg->freeSlot(exclSlot); - } - hasCol |= isCol; - return res; - -} // end of ShiftCollider::mergeSlot - - -// Figure out where to move the target glyph to, and return the amount to shift by. -Position ShiftCollider::resolve(GR_MAYBE_UNUSED Segment *seg, bool &isCol, GR_MAYBE_UNUSED json * const dbgout) -{ - float tbase; - float totalCost = (float)(std::numeric_limits<float>::max() / 2); - Position resultPos = Position(0, 0); -#if !defined GRAPHITE2_NTRACING - int bestAxis = -1; - if (dbgout) - { - outputJsonDbgStartSlot(dbgout, seg); - *dbgout << "vectors" << json::array; - } -#endif - isCol = true; - for (int i = 0; i < 4; ++i) - { - float bestCost = -1; - float bestPos; - // Calculate the margin depending on whether we are moving diagonally or not: - switch (i) { - case 0 : // x direction - tbase = _currOffset.x; - break; - case 1 : // y direction - tbase = _currOffset.y; - break; - case 2 : // sum (negatively-sloped diagonals) - tbase = _currOffset.x + _currOffset.y; - break; - case 3 : // diff (positively-sloped diagonals) - tbase = _currOffset.x - _currOffset.y; - break; - } - Position testp; - bestPos = _ranges[i].closest(0, bestCost) - tbase; // Get the best relative position -#if !defined GRAPHITE2_NTRACING - if (dbgout) - outputJsonDbgOneVector(dbgout, seg, i, tbase, bestCost, bestPos) ; -#endif - if (bestCost >= 0.0f) - { - isCol = false; - switch (i) { - case 0 : testp = Position(bestPos, _currShift.y); break; - case 1 : testp = Position(_currShift.x, bestPos); break; - case 2 : testp = Position(0.5f * (_currShift.x - _currShift.y + bestPos), 0.5f * (_currShift.y - _currShift.x + bestPos)); break; - case 3 : testp = Position(0.5f * (_currShift.x + _currShift.y + bestPos), 0.5f * (_currShift.x + _currShift.y - bestPos)); break; - } - if (bestCost < totalCost - 0.01f) - { - totalCost = bestCost; - resultPos = testp; -#if !defined GRAPHITE2_NTRACING - bestAxis = i; -#endif - } - } - } // end of loop over 4 directions - -#if !defined GRAPHITE2_NTRACING - if (dbgout) - outputJsonDbgEndSlot(dbgout, resultPos, bestAxis, isCol); -#endif - - return resultPos; - -} // end of ShiftCollider::resolve - - -#if !defined GRAPHITE2_NTRACING - -void ShiftCollider::outputJsonDbg(json * const dbgout, Segment *seg, int axis) -{ - int axisMax = axis; - if (axis < 0) // output all axes - { - *dbgout << "gid" << _target->gid() - << "limit" << _limit - << "target" << json::object - << "origin" << _target->origin() - << "margin" << _margin - << "bbox" << seg->theGlyphBBoxTemporary(_target->gid()) - << "slantbox" << seg->getFace()->glyphs().slant(_target->gid()) - << json::close; // target object - *dbgout << "ranges" << json::array; - axis = 0; - axisMax = 3; - } - for (int iAxis = axis; iAxis <= axisMax; ++iAxis) - { - *dbgout << json::flat << json::array << _ranges[iAxis].position(); - for (Zones::const_iterator s = _ranges[iAxis].begin(), e = _ranges[iAxis].end(); s != e; ++s) - *dbgout << json::flat << json::array - << Position(s->x, s->xm) << s->sm << s->smx << s->c - << json::close; - *dbgout << json::close; - } - if (axis < axisMax) // looped through the _ranges array for all axes - *dbgout << json::close; // ranges array -} - -void ShiftCollider::outputJsonDbgStartSlot(json * const dbgout, Segment *seg) -{ - *dbgout << json::object // slot - not closed till the end of the caller method - << "slot" << objectid(dslot(seg, _target)) - << "gid" << _target->gid() - << "limit" << _limit - << "target" << json::object - << "origin" << _origin - << "currShift" << _currShift - << "currOffset" << seg->collisionInfo(_target)->offset() - << "bbox" << seg->theGlyphBBoxTemporary(_target->gid()) - << "slantBox" << seg->getFace()->glyphs().slant(_target->gid()) - << "fix" << "shift"; - *dbgout << json::close; // target object -} - -void ShiftCollider::outputJsonDbgEndSlot(GR_MAYBE_UNUSED json * const dbgout, - Position resultPos, int bestAxis, bool isCol) -{ - *dbgout << json::close // vectors array - << "result" << resultPos - //<< "scraping" << _scraping[bestAxis] - << "bestAxis" << bestAxis - << "stillBad" << isCol - << json::close; // slot object -} - -void ShiftCollider::outputJsonDbgOneVector(json * const dbgout, Segment *seg, int axis, - float tleft, float bestCost, float bestVal) -{ - const char * label; - switch (axis) - { - case 0: label = "x"; break; - case 1: label = "y"; break; - case 2: label = "sum (NE-SW)"; break; - case 3: label = "diff (NW-SE)"; break; - default: label = "???"; break; - } - - *dbgout << json::object // vector - << "direction" << label - << "targetMin" << tleft; - - outputJsonDbgRemovals(dbgout, axis, seg); - - *dbgout << "ranges"; - outputJsonDbg(dbgout, seg, axis); - - *dbgout << "bestCost" << bestCost - << "bestVal" << bestVal + tleft - << json::close; // vectors object -} - -void ShiftCollider::outputJsonDbgRemovals(json * const dbgout, int axis, Segment *seg) -{ - *dbgout << "removals" << json::array; - _ranges[axis].jsonDbgOut(seg); - *dbgout << json::close; // removals array -} - -#endif // !defined GRAPHITE2_NTRACING - - -//// KERN-COLLIDER //// - -inline -static float localmax (float al, float au, float bl, float bu, float x) -{ - if (al < bl) - { if (au < bu) return au < x ? au : x; } - else if (au > bu) return bl < x ? bl : x; - return x; -} - -inline -static float localmin(float al, float au, float bl, float bu, float x) -{ - if (bl > al) - { if (bu > au) return bl > x ? bl : x; } - else if (au > bu) return al > x ? al : x; - return x; -} - -// Return the given edge of the glyph at height y, taking any slant box into account. -static float get_edge(Segment *seg, const Slot *s, const Position &shift, float y, float width, float margin, bool isRight) -{ - const GlyphCache &gc = seg->getFace()->glyphs(); - unsigned short gid = s->gid(); - float sx = s->origin().x + shift.x; - float sy = s->origin().y + shift.y; - uint8 numsub = gc.numSubBounds(gid); - float res = isRight ? (float)-1e38 : (float)1e38; - - if (numsub > 0) - { - for (int i = 0; i < numsub; ++i) - { - const BBox &sbb = gc.getSubBoundingBBox(gid, i); - const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, i); - if (sy + sbb.yi - margin > y + width / 2 || sy + sbb.ya + margin < y - width / 2) - continue; - if (isRight) - { - float x = sx + sbb.xa + margin; - if (x > res) - { - float td = sx - sy + ssb.da + margin + y; - float ts = sx + sy + ssb.sa + margin - y; - x = localmax(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x); - if (x > res) - res = x; - } - } - else - { - float x = sx + sbb.xi - margin; - if (x < res) - { - float td = sx - sy + ssb.di - margin + y; - float ts = sx + sy + ssb.si - margin - y; - x = localmin(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x); - if (x < res) - res = x; - } - } - } - } - else - { - const BBox &bb = gc.getBoundingBBox(gid); - const SlantBox &sb = gc.getBoundingSlantBox(gid); - if (sy + bb.yi - margin > y + width / 2 || sy + bb.ya + margin < y - width / 2) - return res; - float td = sx - sy + y; - float ts = sx + sy - y; - if (isRight) - 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; - else - 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; - } - return res; -} - - -bool KernCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin, - const Position &currShift, const Position &offsetPrev, int dir, - float ymin, float ymax, GR_MAYBE_UNUSED json * const dbgout) -{ - const GlyphCache &gc = seg->getFace()->glyphs(); - const Slot *base = aSlot; - // const Slot *last = aSlot; - const Slot *s; - int numSlices; - while (base->attachedTo()) - base = base->attachedTo(); - if (margin < 10) margin = 10; - - _limit = limit; - _offsetPrev = offsetPrev; // kern from a previous pass - - // Calculate the height of the glyph and how many horizontal slices to use. - if (_maxy >= 1e37f) - { - _sliceWidth = margin / 1.5f; - _maxy = ymax + margin; - _miny = ymin - margin; - numSlices = int((_maxy - _miny + 2) / (_sliceWidth / 1.5f) + 1.f); // +2 helps with rounding errors - _edges.clear(); - _edges.insert(_edges.begin(), numSlices, (dir & 1) ? 1e38f : -1e38f); - _xbound = (dir & 1) ? (float)1e38f : (float)-1e38f; - } - else if (_maxy != ymax || _miny != ymin) - { - if (_miny != ymin) - { - numSlices = int((ymin - margin - _miny) / _sliceWidth - 1); - _miny += numSlices * _sliceWidth; - if (numSlices < 0) - _edges.insert(_edges.begin(), -numSlices, (dir & 1) ? 1e38f : -1e38f); - else if ((unsigned)numSlices < _edges.size()) // this shouldn't fire since we always grow the range - { - Vector<float>::iterator e = _edges.begin(); - while (numSlices--) - ++e; - _edges.erase(_edges.begin(), e); - } - } - if (_maxy != ymax) - { - numSlices = int((ymax + margin - _miny) / _sliceWidth + 1); - _maxy = numSlices * _sliceWidth + _miny; - if (numSlices > (int)_edges.size()) - _edges.insert(_edges.end(), numSlices - _edges.size(), (dir & 1) ? 1e38f : -1e38f); - else if (numSlices < (int)_edges.size()) // this shouldn't fire since we always grow the range - { - while ((int)_edges.size() > numSlices) - _edges.pop_back(); - } - } - goto done; - } - numSlices = int(_edges.size()); - -#if !defined GRAPHITE2_NTRACING - // Debugging - _seg = seg; - _slotNear.clear(); - _slotNear.insert(_slotNear.begin(), numSlices, NULL); - _nearEdges.clear(); - _nearEdges.insert(_nearEdges.begin(), numSlices, (dir & 1) ? -1e38f : +1e38f); -#endif - - // Determine the trailing edge of each slice (ie, left edge for a RTL glyph). - for (s = base; s; s = s->nextInCluster(s)) - { - SlotCollision *c = seg->collisionInfo(s); - if (!gc.check(s->gid())) - return false; - const BBox &bs = gc.getBoundingBBox(s->gid()); - float x = s->origin().x + c->shift().x + ((dir & 1) ? bs.xi : bs.xa); - // Loop over slices. - // Note smin might not be zero if glyph s is not at the bottom of the cluster; similarly for smax. - float toffset = c->shift().y - _miny + 1 + s->origin().y; - int smin = max(0, int((bs.yi + toffset) / _sliceWidth)); - int smax = min(numSlices - 1, int((bs.ya + toffset) / _sliceWidth + 1)); - for (int i = smin; i <= smax; ++i) - { - float t; - float y = _miny - 1 + (i + .5f) * _sliceWidth; // vertical center of slice - if ((dir & 1) && x < _edges[i]) - { - t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, false); - if (t < _edges[i]) - { - _edges[i] = t; - if (t < _xbound) - _xbound = t; - } - } - else if (!(dir & 1) && x > _edges[i]) - { - t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, true); - if (t > _edges[i]) - { - _edges[i] = t; - if (t > _xbound) - _xbound = t; - } - } - } - } - done: - _mingap = (float)1e37; // less than 1e38 s.t. 1e38-_mingap is really big - _target = aSlot; - _margin = margin; - _currShift = currShift; - return true; -} // end of KernCollider::initSlot - - -// Determine how much the target slot needs to kern away from the given slot. -// In other words, merge information from given slot's position with what the target slot knows -// about how it can kern. -// Return false if we know there is no collision, true if we think there might be one. -bool KernCollider::mergeSlot(Segment *seg, Slot *slot, const Position &currShift, float currSpace, int dir, GR_MAYBE_UNUSED json * const dbgout) -{ - int rtl = (dir & 1) * 2 - 1; - if (!seg->getFace()->glyphs().check(slot->gid())) - return false; - const Rect &bb = seg->theGlyphBBoxTemporary(slot->gid()); - const float sx = slot->origin().x + currShift.x; - float x = (sx + (rtl > 0 ? bb.tr.x : bb.bl.x)) * rtl; - // this isn't going to reduce _mingap so skip - if (_hit && x < rtl * (_xbound - _mingap - currSpace)) - return false; - - const float sy = slot->origin().y + currShift.y; - int smin = max(1, int((bb.bl.y + (1 - _miny + sy)) / _sliceWidth + 1)) - 1; - int smax = min((int)_edges.size() - 2, int((bb.tr.y + (1 - _miny + sy)) / _sliceWidth + 1)) + 1; - if (smin > smax) - return false; - bool collides = false; - bool nooverlap = true; - - for (int i = smin; i <= smax; ++i) - { - float here = _edges[i] * rtl; - if (here > (float)9e37) - continue; - if (!_hit || x > here - _mingap - currSpace) - { - float y = (float)(_miny - 1 + (i + .5f) * _sliceWidth); // vertical center of slice - // 2 * currSpace to account for the space that is already separating them and the space we want to add - float m = get_edge(seg, slot, currShift, y, _sliceWidth, 0., rtl > 0) * rtl + 2 * currSpace; - if (m < (float)-8e37) // only true if the glyph has a gap in it - continue; - nooverlap = false; - float t = here - m; - // _mingap is positive to shrink - if (t < _mingap || (!_hit && !collides)) - { - _mingap = t; - collides = true; - } -#if !defined GRAPHITE2_NTRACING - // Debugging - remember the closest neighboring edge for this slice. - if (m > rtl * _nearEdges[i]) - { - _slotNear[i] = slot; - _nearEdges[i] = m * rtl; - } -#endif - } - else - nooverlap = false; - } - if (nooverlap) - _mingap = max(_mingap, _xbound - rtl * (currSpace + _margin + x)); - if (collides && !nooverlap) - _hit = true; - return collides | nooverlap; // note that true is not a necessarily reliable value - -} // end of KernCollider::mergeSlot - - -// Return the amount to kern by. -Position KernCollider::resolve(GR_MAYBE_UNUSED Segment *seg, GR_MAYBE_UNUSED Slot *slot, - int dir, GR_MAYBE_UNUSED json * const dbgout) -{ - float resultNeeded = (1 - 2 * (dir & 1)) * _mingap; - // float resultNeeded = (1 - 2 * (dir & 1)) * (_mingap - margin); - float result = min(_limit.tr.x - _offsetPrev.x, max(resultNeeded, _limit.bl.x - _offsetPrev.x)); - -#if !defined GRAPHITE2_NTRACING - if (dbgout) - { - *dbgout << json::object // slot - << "slot" << objectid(dslot(seg, _target)) - << "gid" << _target->gid() - << "limit" << _limit - << "miny" << _miny - << "maxy" << _maxy - << "slicewidth" << _sliceWidth - << "target" << json::object - << "origin" << _target->origin() - //<< "currShift" << _currShift - << "offsetPrev" << _offsetPrev - << "bbox" << seg->theGlyphBBoxTemporary(_target->gid()) - << "slantBox" << seg->getFace()->glyphs().slant(_target->gid()) - << "fix" << "kern" - << json::close; // target object - - *dbgout << "slices" << json::array; - for (int is = 0; is < (int)_edges.size(); is++) - { - *dbgout << json::flat << json::object - << "i" << is - << "targetEdge" << _edges[is] - << "neighbor" << objectid(dslot(seg, _slotNear[is])) - << "nearEdge" << _nearEdges[is] - << json::close; - } - *dbgout << json::close; // slices array - - *dbgout - << "xbound" << _xbound - << "minGap" << _mingap - << "needed" << resultNeeded - << "result" << result - << "stillBad" << (result != resultNeeded) - << json::close; // slot object - } -#endif - - return Position(result, 0.); - -} // end of KernCollider::resolve - -void KernCollider::shift(const Position &mv, int dir) -{ - for (Vector<float>::iterator e = _edges.begin(); e != _edges.end(); ++e) - *e += mv.x; - _xbound += (1 - 2 * (dir & 1)) * mv.x; -} - -//// SLOT-COLLISION //// - -// Initialize the collision attributes for the given slot. -SlotCollision::SlotCollision(Segment *seg, Slot *slot) -{ - initFromSlot(seg, slot); -} - -void SlotCollision::initFromSlot(Segment *seg, Slot *slot) -{ - // Initialize slot attributes from glyph attributes. - // The order here must match the order in the grcompiler code, - // GrcSymbolTable::AssignInternalGlyphAttrIDs. - uint16 gid = slot->gid(); - uint16 aCol = seg->silf()->aCollision(); // flags attr ID - const GlyphFace * glyphFace = seg->getFace()->glyphs().glyphSafe(gid); - if (!glyphFace) - return; - const sparse &p = glyphFace->attrs(); - _flags = p[aCol]; - _limit = Rect(Position(int16(p[aCol+1]), int16(p[aCol+2])), - Position(int16(p[aCol+3]), int16(p[aCol+4]))); - _margin = p[aCol+5]; - _marginWt = p[aCol+6]; - - _seqClass = p[aCol+7]; - _seqProxClass = p[aCol+8]; - _seqOrder = p[aCol+9]; - _seqAboveXoff = p[aCol+10]; - _seqAboveWt = p[aCol+11]; - _seqBelowXlim = p[aCol+12]; - _seqBelowWt = p[aCol+13]; - _seqValignHt = p[aCol+14]; - _seqValignWt = p[aCol+15]; - - // These attributes do not have corresponding glyph attribute: - _exclGlyph = 0; - _exclOffset = Position(0, 0); -} - -float SlotCollision::getKern(int dir) const -{ - if ((_flags & SlotCollision::COLL_KERN) != 0) - return float(_shift.x * ((dir & 1) ? -1 : 1)); - else - return 0; -} - -bool SlotCollision::ignore() const -{ - return ((flags() & SlotCollision::COLL_IGNORE) || (flags() & SlotCollision::COLL_ISSPACE)); -} |