| /* | |
| * Copyright © 2023 Behdad Esfahbod | |
| * | |
| * This is part of HarfBuzz, a text shaping library. | |
| * | |
| * Permission is hereby granted, without written agreement and without | |
| * license or royalty fees, to use, copy, modify, and distribute this | |
| * software and its documentation for any purpose, provided that the | |
| * above copyright notice and the following two paragraphs appear in | |
| * all copies of this software. | |
| * | |
| * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR | |
| * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES | |
| * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN | |
| * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH | |
| * DAMAGE. | |
| * | |
| * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, | |
| * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND | |
| * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS | |
| * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO | |
| * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. | |
| */ | |
| #include "hb-subset-instancer-solver.hh" | |
| /* This file is a straight port of the following: | |
| * | |
| * https://github.com/fonttools/fonttools/blob/f73220816264fc383b8a75f2146e8d69e455d398/Lib/fontTools/varLib/instancer/solver.py | |
| * | |
| * Where that file returns None for a triple, we return Triple{}. | |
| * This should be safe. | |
| */ | |
| constexpr static double EPSILON = 1.0 / (1 << 14); | |
| constexpr static double MAX_F2DOT14 = double (0x7FFF) / (1 << 14); | |
| static inline Triple _reverse_negate(const Triple &v) | |
| { return {-v.maximum, -v.middle, -v.minimum}; } | |
| static inline double supportScalar (double coord, const Triple &tent) | |
| { | |
| /* Copied from VarRegionAxis::evaluate() */ | |
| double start = tent.minimum, peak = tent.middle, end = tent.maximum; | |
| if (unlikely (start > peak || peak > end)) | |
| return 1.; | |
| if (unlikely (start < 0 && end > 0 && peak != 0)) | |
| return 1.; | |
| if (peak == 0 || coord == peak) | |
| return 1.; | |
| if (coord <= start || end <= coord) | |
| return 0.; | |
| /* Interpolate */ | |
| if (coord < peak) | |
| return (coord - start) / (peak - start); | |
| else | |
| return (end - coord) / (end - peak); | |
| } | |
| static inline void | |
| _solve (Triple tent, Triple axisLimit, rebase_tent_result_t &out, bool negative = false) | |
| { | |
| out.reset(); | |
| double axisMin = axisLimit.minimum; | |
| double axisDef = axisLimit.middle; | |
| double axisMax = axisLimit.maximum; | |
| double lower = tent.minimum; | |
| double peak = tent.middle; | |
| double upper = tent.maximum; | |
| // Mirror the problem such that axisDef <= peak | |
| if (axisDef > peak) | |
| { | |
| _solve (_reverse_negate (tent), _reverse_negate (axisLimit), out, !negative); | |
| for (auto &p : out) | |
| p = hb_pair (p.first, _reverse_negate (p.second)); | |
| return; | |
| } | |
| // axisDef <= peak | |
| /* case 1: The whole deltaset falls outside the new limit; we can drop it | |
| * | |
| * peak | |
| * 1.........................................o.......... | |
| * / \ | |
| * / \ | |
| * / \ | |
| * / \ | |
| * 0---|-----------|----------|-------- o o----1 | |
| * axisMin axisDef axisMax lower upper | |
| */ | |
| if (axisMax <= lower && axisMax < peak) | |
| return; // No overlap | |
| /* case 2: Only the peak and outermost bound fall outside the new limit; | |
| * we keep the deltaset, update peak and outermost bound and scale deltas | |
| * by the scalar value for the restricted axis at the new limit, and solve | |
| * recursively. | |
| * | |
| * |peak | |
| * 1...............................|.o.......... | |
| * |/ \ | |
| * / \ | |
| * /| \ | |
| * / | \ | |
| * 0--------------------------- o | o----1 | |
| * lower | upper | |
| * | | |
| * axisMax | |
| * | |
| * Convert to: | |
| * | |
| * 1............................................ | |
| * | | |
| * o peak | |
| * /| | |
| * /x| | |
| * 0--------------------------- o o upper ----1 | |
| * lower | | |
| * | | |
| * axisMax | |
| */ | |
| if (axisMax < peak) | |
| { | |
| double mult = supportScalar (axisMax, tent); | |
| tent = Triple{lower, axisMax, axisMax}; | |
| _solve (tent, axisLimit, out); | |
| for (auto &p : out) | |
| p = hb_pair (p.first * mult, p.second); | |
| return; | |
| } | |
| // lower <= axisDef <= peak <= axisMax | |
| double gain = supportScalar (axisDef, tent); | |
| out.push(hb_pair (gain, Triple{})); | |
| // First, the positive side | |
| // outGain is the scalar of axisMax at the tent. | |
| double outGain = supportScalar (axisMax, tent); | |
| /* Case 3a: Gain is more than outGain. The tent down-slope crosses | |
| * the axis into negative. We have to split it into multiples. | |
| * | |
| * | peak | | |
| * 1...................|.o.....|.............. | |
| * |/x\_ | | |
| * gain................+....+_.|.............. | |
| * /| |y\| | |
| * ................../.|....|..+_......outGain | |
| * / | | | \ | |
| * 0---|-----------o | | | o----------1 | |
| * axisMin lower | | | upper | |
| * | | | | |
| * axisDef | axisMax | |
| * | | |
| * crossing | |
| */ | |
| if (gain >= outGain) | |
| { | |
| // Note that this is the branch taken if both gain and outGain are 0. | |
| // Crossing point on the axis. | |
| double crossing = peak + (1 - gain) * (upper - peak); | |
| Triple loc{hb_max (lower, axisDef), peak, crossing}; | |
| double scalar = 1.0; | |
| // The part before the crossing point. | |
| out.push (hb_pair (scalar - gain, loc)); | |
| /* The part after the crossing point may use one or two tents, | |
| * depending on whether upper is before axisMax or not, in one | |
| * case we need to keep it down to eternity. | |
| * | |
| * Case 3a1, similar to case 1neg; just one tent needed, as in | |
| * the drawing above. | |
| */ | |
| if (upper >= axisMax) | |
| { | |
| Triple loc {crossing, axisMax, axisMax}; | |
| double scalar = outGain; | |
| out.push (hb_pair (scalar - gain, loc)); | |
| } | |
| /* Case 3a2: Similar to case 2neg; two tents needed, to keep | |
| * down to eternity. | |
| * | |
| * | peak | | |
| * 1...................|.o................|... | |
| * |/ \_ | | |
| * gain................+....+_............|... | |
| * /| | \xxxxxxxxxxy| | |
| * / | | \_xxxxxyyyy| | |
| * / | | \xxyyyyyy| | |
| * 0---|-----------o | | o-------|--1 | |
| * axisMin lower | | upper | | |
| * | | | | |
| * axisDef | axisMax | |
| * | | |
| * crossing | |
| */ | |
| else | |
| { | |
| // A tent's peak cannot fall on axis default. Nudge it. | |
| if (upper == axisDef) | |
| upper += EPSILON; | |
| // Downslope. | |
| Triple loc1 {crossing, upper, axisMax}; | |
| double scalar1 = 0.0; | |
| // Eternity justify. | |
| Triple loc2 {upper, axisMax, axisMax}; | |
| double scalar2 = 0.0; | |
| out.push (hb_pair (scalar1 - gain, loc1)); | |
| out.push (hb_pair (scalar2 - gain, loc2)); | |
| } | |
| } | |
| else | |
| { | |
| // Special-case if peak is at axisMax. | |
| if (axisMax == peak) | |
| upper = peak; | |
| /* Case 3: | |
| * we keep deltas as is and only scale the axis upper to achieve | |
| * the desired new tent if feasible. | |
| * | |
| * peak | |
| * 1.....................o.................... | |
| * / \_| | |
| * ..................../....+_.........outGain | |
| * / | \ | |
| * gain..............+......|..+_............. | |
| * /| | | \ | |
| * 0---|-----------o | | | o----------1 | |
| * axisMin lower| | | upper | |
| * | | newUpper | |
| * axisDef axisMax | |
| */ | |
| double newUpper = peak + (1 - gain) * (upper - peak); | |
| assert (axisMax <= newUpper); // Because outGain > gain | |
| /* Disabled because ots doesn't like us: | |
| * https://github.com/fonttools/fonttools/issues/3350 */ | |
| if (false && (newUpper <= axisDef + (axisMax - axisDef) * 2)) | |
| { | |
| upper = newUpper; | |
| if (!negative && axisDef + (axisMax - axisDef) * MAX_F2DOT14 < upper) | |
| { | |
| // we clamp +2.0 to the max F2Dot14 (~1.99994) for convenience | |
| upper = axisDef + (axisMax - axisDef) * MAX_F2DOT14; | |
| assert (peak < upper); | |
| } | |
| Triple loc {hb_max (axisDef, lower), peak, upper}; | |
| double scalar = 1.0; | |
| out.push (hb_pair (scalar - gain, loc)); | |
| } | |
| /* Case 4: New limit doesn't fit; we need to chop into two tents, | |
| * because the shape of a triangle with part of one side cut off | |
| * cannot be represented as a triangle itself. | |
| * | |
| * | peak | | |
| * 1.........|......o.|.................... | |
| * ..........|...../x\|.............outGain | |
| * | |xxy|\_ | |
| * | /xxxy| \_ | |
| * | |xxxxy| \_ | |
| * | /xxxxy| \_ | |
| * 0---|-----|-oxxxxxx| o----------1 | |
| * axisMin | lower | upper | |
| * | | | |
| * axisDef axisMax | |
| */ | |
| else | |
| { | |
| Triple loc1 {hb_max (axisDef, lower), peak, axisMax}; | |
| double scalar1 = 1.0; | |
| Triple loc2 {peak, axisMax, axisMax}; | |
| double scalar2 = outGain; | |
| out.push (hb_pair (scalar1 - gain, loc1)); | |
| // Don't add a dirac delta! | |
| if (peak < axisMax) | |
| out.push (hb_pair (scalar2 - gain, loc2)); | |
| } | |
| } | |
| /* Now, the negative side | |
| * | |
| * Case 1neg: Lower extends beyond axisMin: we chop. Simple. | |
| * | |
| * | |peak | |
| * 1..................|...|.o................. | |
| * | |/ \ | |
| * gain...............|...+...\............... | |
| * |x_/| \ | |
| * |/ | \ | |
| * _/| | \ | |
| * 0---------------o | | o----------1 | |
| * lower | | upper | |
| * | | | |
| * axisMin axisDef | |
| */ | |
| if (lower <= axisMin) | |
| { | |
| Triple loc {axisMin, axisMin, axisDef}; | |
| double scalar = supportScalar (axisMin, tent); | |
| out.push (hb_pair (scalar - gain, loc)); | |
| } | |
| /* Case 2neg: Lower is betwen axisMin and axisDef: we add two | |
| * tents to keep it down all the way to eternity. | |
| * | |
| * | |peak | |
| * 1...|...............|.o................. | |
| * | |/ \ | |
| * gain|...............+...\............... | |
| * |yxxxxxxxxxxxxx/| \ | |
| * |yyyyyyxxxxxxx/ | \ | |
| * |yyyyyyyyyyyx/ | \ | |
| * 0---|-----------o | o----------1 | |
| * axisMin lower | upper | |
| * | | |
| * axisDef | |
| */ | |
| else | |
| { | |
| // A tent's peak cannot fall on axis default. Nudge it. | |
| if (lower == axisDef) | |
| lower -= EPSILON; | |
| // Downslope. | |
| Triple loc1 {axisMin, lower, axisDef}; | |
| double scalar1 = 0.0; | |
| // Eternity justify. | |
| Triple loc2 {axisMin, axisMin, lower}; | |
| double scalar2 = 0.0; | |
| out.push (hb_pair (scalar1 - gain, loc1)); | |
| out.push (hb_pair (scalar2 - gain, loc2)); | |
| } | |
| } | |
| static inline TripleDistances _reverse_triple_distances (const TripleDistances &v) | |
| { return TripleDistances (v.positive, v.negative); } | |
| double renormalizeValue (double v, const Triple &triple, | |
| const TripleDistances &triple_distances, bool extrapolate) | |
| { | |
| double lower = triple.minimum, def = triple.middle, upper = triple.maximum; | |
| if (unlikely (!(lower <= def && def <= upper))) | |
| return hb_clamp (v, -1.0, +1.0); | |
| if (!extrapolate) | |
| v = hb_clamp (v, lower, upper); | |
| if (v == def) | |
| return 0.0; | |
| if (def < 0.0) | |
| return -renormalizeValue (-v, _reverse_negate (triple), | |
| _reverse_triple_distances (triple_distances), extrapolate); | |
| /* default >= 0 and v != default */ | |
| if (v > def) | |
| { | |
| double positive_range = upper - def; | |
| if (unlikely (!positive_range)) | |
| return +1.0; | |
| return (v - def) / positive_range; | |
| } | |
| /* v < def */ | |
| if (lower >= 0.0) | |
| { | |
| double negative_range = def - lower; | |
| if (unlikely (!negative_range)) | |
| return -1.0; | |
| return (v - def) / negative_range; | |
| } | |
| /* lower < 0 and v < default */ | |
| double total_distance = triple_distances.negative * (-lower) + triple_distances.positive * def; | |
| if (unlikely (!total_distance)) | |
| return 0.0; | |
| double v_distance; | |
| if (v >= 0.0) | |
| v_distance = (def - v) * triple_distances.positive; | |
| else | |
| v_distance = (-v) * triple_distances.negative + triple_distances.positive * def; | |
| return (-v_distance) /total_distance; | |
| } | |
| void | |
| rebase_tent (Triple tent, Triple axisLimit, TripleDistances axis_triple_distances, | |
| rebase_tent_result_t &out, | |
| rebase_tent_result_t &scratch) | |
| { | |
| if (unlikely (!(-1.0 <= axisLimit.minimum && | |
| axisLimit.minimum <= axisLimit.middle && | |
| axisLimit.middle <= axisLimit.maximum && | |
| axisLimit.maximum <= +1.0) || | |
| !(-2.0 <= tent.minimum && | |
| tent.minimum <= tent.middle && | |
| tent.middle <= tent.maximum && | |
| tent.maximum <= +2.0) || | |
| tent.middle == 0.0)) | |
| { | |
| out.reset (); | |
| return; | |
| } | |
| rebase_tent_result_t &sols = scratch; | |
| _solve (tent, axisLimit, sols); | |
| auto n = [&axisLimit, &axis_triple_distances] (double v) { return renormalizeValue (v, axisLimit, axis_triple_distances); }; | |
| out.reset(); | |
| for (auto &p : sols) | |
| { | |
| if (!p.first) continue; | |
| if (p.second == Triple{}) | |
| { | |
| out.push (p); | |
| continue; | |
| } | |
| Triple t = p.second; | |
| out.push (hb_pair (p.first, | |
| Triple{n (t.minimum), n (t.middle), n (t.maximum)})); | |
| } | |
| } |