1 /*
2 * Copyright © 2023 Behdad Esfahbod
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 */
24
25 #include "hb-subset-instancer-solver.hh"
26
27 /* This file is a straight port of the following:
28 *
29 * https://github.com/fonttools/fonttools/blob/f73220816264fc383b8a75f2146e8d69e455d398/Lib/fontTools/varLib/instancer/solver.py
30 *
31 * Where that file returns None for a triple, we return Triple{}.
32 * This should be safe.
33 */
34
35 constexpr static double EPSILON = 1.0 / (1 << 14);
36 constexpr static double MAX_F2DOT14 = double (0x7FFF) / (1 << 14);
37
_reverse_negate(const Triple & v)38 static inline Triple _reverse_negate(const Triple &v)
39 { return {-v.maximum, -v.middle, -v.minimum}; }
40
41
supportScalar(double coord,const Triple & tent)42 static inline double supportScalar (double coord, const Triple &tent)
43 {
44 /* Copied from VarRegionAxis::evaluate() */
45 double start = tent.minimum, peak = tent.middle, end = tent.maximum;
46
47 if (unlikely (start > peak || peak > end))
48 return 1.;
49 if (unlikely (start < 0 && end > 0 && peak != 0))
50 return 1.;
51
52 if (peak == 0 || coord == peak)
53 return 1.;
54
55 if (coord <= start || end <= coord)
56 return 0.;
57
58 /* Interpolate */
59 if (coord < peak)
60 return (coord - start) / (peak - start);
61 else
62 return (end - coord) / (end - peak);
63 }
64
65 static inline rebase_tent_result_t
_solve(Triple tent,Triple axisLimit,bool negative=false)66 _solve (Triple tent, Triple axisLimit, bool negative = false)
67 {
68 double axisMin = axisLimit.minimum;
69 double axisDef = axisLimit.middle;
70 double axisMax = axisLimit.maximum;
71 double lower = tent.minimum;
72 double peak = tent.middle;
73 double upper = tent.maximum;
74
75 // Mirror the problem such that axisDef <= peak
76 if (axisDef > peak)
77 {
78 rebase_tent_result_t vec = _solve (_reverse_negate (tent),
79 _reverse_negate (axisLimit),
80 !negative);
81
82 for (auto &p : vec)
83 p = hb_pair (p.first, _reverse_negate (p.second));
84
85 return vec;
86 }
87 // axisDef <= peak
88
89 /* case 1: The whole deltaset falls outside the new limit; we can drop it
90 *
91 * peak
92 * 1.........................................o..........
93 * / \
94 * / \
95 * / \
96 * / \
97 * 0---|-----------|----------|-------- o o----1
98 * axisMin axisDef axisMax lower upper
99 */
100 if (axisMax <= lower && axisMax < peak)
101 return rebase_tent_result_t{}; // No overlap
102
103 /* case 2: Only the peak and outermost bound fall outside the new limit;
104 * we keep the deltaset, update peak and outermost bound and scale deltas
105 * by the scalar value for the restricted axis at the new limit, and solve
106 * recursively.
107 *
108 * |peak
109 * 1...............................|.o..........
110 * |/ \
111 * / \
112 * /| \
113 * / | \
114 * 0--------------------------- o | o----1
115 * lower | upper
116 * |
117 * axisMax
118 *
119 * Convert to:
120 *
121 * 1............................................
122 * |
123 * o peak
124 * /|
125 * /x|
126 * 0--------------------------- o o upper ----1
127 * lower |
128 * |
129 * axisMax
130 */
131 if (axisMax < peak)
132 {
133 double mult = supportScalar (axisMax, tent);
134 tent = Triple{lower, axisMax, axisMax};
135
136 rebase_tent_result_t vec = _solve (tent, axisLimit);
137
138 for (auto &p : vec)
139 p = hb_pair (p.first * mult, p.second);
140
141 return vec;
142 }
143
144 // lower <= axisDef <= peak <= axisMax
145
146 double gain = supportScalar (axisDef, tent);
147 rebase_tent_result_t out {hb_pair (gain, Triple{})};
148
149 // First, the positive side
150
151 // outGain is the scalar of axisMax at the tent.
152 double outGain = supportScalar (axisMax, tent);
153
154 /* Case 3a: Gain is more than outGain. The tent down-slope crosses
155 * the axis into negative. We have to split it into multiples.
156 *
157 * | peak |
158 * 1...................|.o.....|..............
159 * |/x\_ |
160 * gain................+....+_.|..............
161 * /| |y\|
162 * ................../.|....|..+_......outGain
163 * / | | | \
164 * 0---|-----------o | | | o----------1
165 * axisMin lower | | | upper
166 * | | |
167 * axisDef | axisMax
168 * |
169 * crossing
170 */
171 if (gain >= outGain)
172 {
173 // Note that this is the branch taken if both gain and outGain are 0.
174
175 // Crossing point on the axis.
176 double crossing = peak + (1 - gain) * (upper - peak);
177
178 Triple loc{hb_max (lower, axisDef), peak, crossing};
179 double scalar = 1.0;
180
181 // The part before the crossing point.
182 out.push (hb_pair (scalar - gain, loc));
183
184 /* The part after the crossing point may use one or two tents,
185 * depending on whether upper is before axisMax or not, in one
186 * case we need to keep it down to eternity.
187 *
188 * Case 3a1, similar to case 1neg; just one tent needed, as in
189 * the drawing above.
190 */
191 if (upper >= axisMax)
192 {
193 Triple loc {crossing, axisMax, axisMax};
194 double scalar = outGain;
195
196 out.push (hb_pair (scalar - gain, loc));
197 }
198
199 /* Case 3a2: Similar to case 2neg; two tents needed, to keep
200 * down to eternity.
201 *
202 * | peak |
203 * 1...................|.o................|...
204 * |/ \_ |
205 * gain................+....+_............|...
206 * /| | \xxxxxxxxxxy|
207 * / | | \_xxxxxyyyy|
208 * / | | \xxyyyyyy|
209 * 0---|-----------o | | o-------|--1
210 * axisMin lower | | upper |
211 * | | |
212 * axisDef | axisMax
213 * |
214 * crossing
215 */
216 else
217 {
218 // A tent's peak cannot fall on axis default. Nudge it.
219 if (upper == axisDef)
220 upper += EPSILON;
221
222 // Downslope.
223 Triple loc1 {crossing, upper, axisMax};
224 double scalar1 = 0.0;
225
226 // Eternity justify.
227 Triple loc2 {upper, axisMax, axisMax};
228 double scalar2 = 0.0;
229
230 out.push (hb_pair (scalar1 - gain, loc1));
231 out.push (hb_pair (scalar2 - gain, loc2));
232 }
233 }
234
235 else
236 {
237 // Special-case if peak is at axisMax.
238 if (axisMax == peak)
239 upper = peak;
240
241 /* Case 3:
242 * we keep deltas as is and only scale the axis upper to achieve
243 * the desired new tent if feasible.
244 *
245 * peak
246 * 1.....................o....................
247 * / \_|
248 * ..................../....+_.........outGain
249 * / | \
250 * gain..............+......|..+_.............
251 * /| | | \
252 * 0---|-----------o | | | o----------1
253 * axisMin lower| | | upper
254 * | | newUpper
255 * axisDef axisMax
256 */
257 double newUpper = peak + (1 - gain) * (upper - peak);
258 assert (axisMax <= newUpper); // Because outGain > gain
259 /* Disabled because ots doesn't like us:
260 * https://github.com/fonttools/fonttools/issues/3350 */
261
262 if (false && (newUpper <= axisDef + (axisMax - axisDef) * 2))
263 {
264 upper = newUpper;
265 if (!negative && axisDef + (axisMax - axisDef) * MAX_F2DOT14 < upper)
266 {
267 // we clamp +2.0 to the max F2Dot14 (~1.99994) for convenience
268 upper = axisDef + (axisMax - axisDef) * MAX_F2DOT14;
269 assert (peak < upper);
270 }
271
272 Triple loc {hb_max (axisDef, lower), peak, upper};
273 double scalar = 1.0;
274
275 out.push (hb_pair (scalar - gain, loc));
276 }
277
278 /* Case 4: New limit doesn't fit; we need to chop into two tents,
279 * because the shape of a triangle with part of one side cut off
280 * cannot be represented as a triangle itself.
281 *
282 * | peak |
283 * 1.........|......o.|....................
284 * ..........|...../x\|.............outGain
285 * | |xxy|\_
286 * | /xxxy| \_
287 * | |xxxxy| \_
288 * | /xxxxy| \_
289 * 0---|-----|-oxxxxxx| o----------1
290 * axisMin | lower | upper
291 * | |
292 * axisDef axisMax
293 */
294 else
295 {
296 Triple loc1 {hb_max (axisDef, lower), peak, axisMax};
297 double scalar1 = 1.0;
298
299 Triple loc2 {peak, axisMax, axisMax};
300 double scalar2 = outGain;
301
302 out.push (hb_pair (scalar1 - gain, loc1));
303 // Don't add a dirac delta!
304 if (peak < axisMax)
305 out.push (hb_pair (scalar2 - gain, loc2));
306 }
307 }
308
309 /* Now, the negative side
310 *
311 * Case 1neg: Lower extends beyond axisMin: we chop. Simple.
312 *
313 * | |peak
314 * 1..................|...|.o.................
315 * | |/ \
316 * gain...............|...+...\...............
317 * |x_/| \
318 * |/ | \
319 * _/| | \
320 * 0---------------o | | o----------1
321 * lower | | upper
322 * | |
323 * axisMin axisDef
324 */
325 if (lower <= axisMin)
326 {
327 Triple loc {axisMin, axisMin, axisDef};
328 double scalar = supportScalar (axisMin, tent);
329
330 out.push (hb_pair (scalar - gain, loc));
331 }
332
333 /* Case 2neg: Lower is betwen axisMin and axisDef: we add two
334 * tents to keep it down all the way to eternity.
335 *
336 * | |peak
337 * 1...|...............|.o.................
338 * | |/ \
339 * gain|...............+...\...............
340 * |yxxxxxxxxxxxxx/| \
341 * |yyyyyyxxxxxxx/ | \
342 * |yyyyyyyyyyyx/ | \
343 * 0---|-----------o | o----------1
344 * axisMin lower | upper
345 * |
346 * axisDef
347 */
348 else
349 {
350 // A tent's peak cannot fall on axis default. Nudge it.
351 if (lower == axisDef)
352 lower -= EPSILON;
353
354 // Downslope.
355 Triple loc1 {axisMin, lower, axisDef};
356 double scalar1 = 0.0;
357
358 // Eternity justify.
359 Triple loc2 {axisMin, axisMin, lower};
360 double scalar2 = 0.0;
361
362 out.push (hb_pair (scalar1 - gain, loc1));
363 out.push (hb_pair (scalar2 - gain, loc2));
364 }
365
366 return out;
367 }
368
_reverse_triple_distances(const TripleDistances & v)369 static inline TripleDistances _reverse_triple_distances (const TripleDistances &v)
370 { return TripleDistances (v.positive, v.negative); }
371
renormalizeValue(double v,const Triple & triple,const TripleDistances & triple_distances,bool extrapolate)372 double renormalizeValue (double v, const Triple &triple,
373 const TripleDistances &triple_distances, bool extrapolate)
374 {
375 double lower = triple.minimum, def = triple.middle, upper = triple.maximum;
376 assert (lower <= def && def <= upper);
377
378 if (!extrapolate)
379 v = hb_clamp (v, lower, upper);
380
381 if (v == def)
382 return 0.0;
383
384 if (def < 0.0)
385 return -renormalizeValue (-v, _reverse_negate (triple),
386 _reverse_triple_distances (triple_distances), extrapolate);
387
388 /* default >= 0 and v != default */
389 if (v > def)
390 return (v - def) / (upper - def);
391
392 /* v < def */
393 if (lower >= 0.0)
394 return (v - def) / (def - lower);
395
396 /* lower < 0 and v < default */
397 double total_distance = triple_distances.negative * (-lower) + triple_distances.positive * def;
398
399 double v_distance;
400 if (v >= 0.0)
401 v_distance = (def - v) * triple_distances.positive;
402 else
403 v_distance = (-v) * triple_distances.negative + triple_distances.positive * def;
404
405 return (-v_distance) /total_distance;
406 }
407
408 rebase_tent_result_t
rebase_tent(Triple tent,Triple axisLimit,TripleDistances axis_triple_distances)409 rebase_tent (Triple tent, Triple axisLimit, TripleDistances axis_triple_distances)
410 {
411 assert (-1.0 <= axisLimit.minimum && axisLimit.minimum <= axisLimit.middle && axisLimit.middle <= axisLimit.maximum && axisLimit.maximum <= +1.0);
412 assert (-2.0 <= tent.minimum && tent.minimum <= tent.middle && tent.middle <= tent.maximum && tent.maximum <= +2.0);
413 assert (tent.middle != 0.0);
414
415 rebase_tent_result_t sols = _solve (tent, axisLimit);
416
417 auto n = [&axisLimit, &axis_triple_distances] (double v) { return renormalizeValue (v, axisLimit, axis_triple_distances); };
418
419 rebase_tent_result_t out;
420 for (auto &p : sols)
421 {
422 if (!p.first) continue;
423 if (p.second == Triple{})
424 {
425 out.push (p);
426 continue;
427 }
428 Triple t = p.second;
429 out.push (hb_pair (p.first,
430 Triple{n (t.minimum), n (t.middle), n (t.maximum)}));
431 }
432
433 return out;
434 }
435