/* 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 = _margin;
// 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();
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);
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 = _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)1e38;
_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 (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;
for (int i = smin; i <= smax; ++i)
{
float t;
float here = _edges[i] * rtl;
float y = (float)(_miny - 1 + (i + .5f) * _sliceWidth); // vertical center of slice
if ( (x > here - _mingap - currSpace) )
{
// 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;
t = here - m;
// _mingap is positive to shrink
if (t < _mingap)
{
_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
}
}
return collides; // 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(p[aCol+1], p[aCol+2]),
Position(p[aCol+3], 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));
}