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 float EPSILON = 1.f / (1 << 14);
36 constexpr static float MAX_F2DOT14 = float (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(float coord,const Triple & tent)42 static inline float supportScalar (float coord, const Triple &tent)
43 {
44 /* Copied from VarRegionAxis::evaluate() */
45 float 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 result_t
_solve(Triple tent,Triple axisLimit,bool negative=false)66 _solve (Triple tent, Triple axisLimit, bool negative = false)
67 {
68 float axisMin = axisLimit.minimum;
69 float axisDef = axisLimit.middle;
70 float axisMax = axisLimit.maximum;
71 float lower = tent.minimum;
72 float peak = tent.middle;
73 float upper = tent.maximum;
74
75 // Mirror the problem such that axisDef <= peak
76 if (axisDef > peak)
77 {
78 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 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 float mult = supportScalar (axisMax, tent);
134 tent = Triple{lower, axisMax, axisMax};
135
136 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 float gain = supportScalar (axisDef, tent);
147 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 float 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 // Crossing point on the axis.
174 float crossing = peak + (1 - gain) * (upper - peak);
175
176 Triple loc{axisDef, peak, crossing};
177 float scalar = 1.f;
178
179 // The part before the crossing point.
180 out.push (hb_pair (scalar - gain, loc));
181
182 /* The part after the crossing point may use one or two tents,
183 * depending on whether upper is before axisMax or not, in one
184 * case we need to keep it down to eternity.
185 *
186 * Case 3a1, similar to case 1neg; just one tent needed, as in
187 * the drawing above.
188 */
189 if (upper >= axisMax)
190 {
191 Triple loc {crossing, axisMax, axisMax};
192 float scalar = outGain;
193
194 out.push (hb_pair (scalar - gain, loc));
195 }
196
197 /* Case 3a2: Similar to case 2neg; two tents needed, to keep
198 * down to eternity.
199 *
200 * | peak |
201 * 1...................|.o................|...
202 * |/ \_ |
203 * gain................+....+_............|...
204 * /| | \xxxxxxxxxxy|
205 * / | | \_xxxxxyyyy|
206 * / | | \xxyyyyyy|
207 * 0---|-----------o | | o-------|--1
208 * axisMin lower | | upper |
209 * | | |
210 * axisDef | axisMax
211 * |
212 * crossing
213 */
214 else
215 {
216 // A tent's peak cannot fall on axis default. Nudge it.
217 if (upper == axisDef)
218 upper += EPSILON;
219
220 // Downslope.
221 Triple loc1 {crossing, upper, axisMax};
222 float scalar1 = 0.f;
223
224 // Eternity justify.
225 Triple loc2 {upper, axisMax, axisMax};
226 float scalar2 = 0.f;
227
228 out.push (hb_pair (scalar1 - gain, loc1));
229 out.push (hb_pair (scalar2 - gain, loc2));
230 }
231 }
232
233 else
234 {
235 // Special-case if peak is at axisMax.
236 if (axisMax == peak)
237 upper = peak;
238
239 /* Case 3:
240 * we keep deltas as is and only scale the axis upper to achieve
241 * the desired new tent if feasible.
242 *
243 * peak
244 * 1.....................o....................
245 * / \_|
246 * ..................../....+_.........outGain
247 * / | \
248 * gain..............+......|..+_.............
249 * /| | | \
250 * 0---|-----------o | | | o----------1
251 * axisMin lower| | | upper
252 * | | newUpper
253 * axisDef axisMax
254 */
255 float newUpper = peak + (1 - gain) * (upper - peak);
256 assert (axisMax <= newUpper); // Because outGain >= gain
257 if (newUpper <= axisDef + (axisMax - axisDef) * 2)
258 {
259 upper = newUpper;
260 if (!negative && axisDef + (axisMax - axisDef) * MAX_F2DOT14 < upper)
261 {
262 // we clamp +2.0 to the max F2Dot14 (~1.99994) for convenience
263 upper = axisDef + (axisMax - axisDef) * MAX_F2DOT14;
264 assert (peak < upper);
265 }
266
267 Triple loc {hb_max (axisDef, lower), peak, upper};
268 float scalar = 1.f;
269
270 out.push (hb_pair (scalar - gain, loc));
271 }
272
273 /* Case 4: New limit doesn't fit; we need to chop into two tents,
274 * because the shape of a triangle with part of one side cut off
275 * cannot be represented as a triangle itself.
276 *
277 * | peak |
278 * 1.........|......o.|....................
279 * ..........|...../x\|.............outGain
280 * | |xxy|\_
281 * | /xxxy| \_
282 * | |xxxxy| \_
283 * | /xxxxy| \_
284 * 0---|-----|-oxxxxxx| o----------1
285 * axisMin | lower | upper
286 * | |
287 * axisDef axisMax
288 */
289 else
290 {
291 Triple loc1 {hb_max (axisDef, lower), peak, axisMax};
292 float scalar1 = 1.f;
293
294 Triple loc2 {peak, axisMax, axisMax};
295 float scalar2 = outGain;
296
297 out.push (hb_pair (scalar1 - gain, loc1));
298 // Don't add a dirac delta!
299 if (peak < axisMax)
300 out.push (hb_pair (scalar2 - gain, loc2));
301 }
302 }
303
304 /* Now, the negative side
305 *
306 * Case 1neg: Lower extends beyond axisMin: we chop. Simple.
307 *
308 * | |peak
309 * 1..................|...|.o.................
310 * | |/ \
311 * gain...............|...+...\...............
312 * |x_/| \
313 * |/ | \
314 * _/| | \
315 * 0---------------o | | o----------1
316 * lower | | upper
317 * | |
318 * axisMin axisDef
319 */
320 if (lower <= axisMin)
321 {
322 Triple loc {axisMin, axisMin, axisDef};
323 float scalar = supportScalar (axisMin, tent);
324
325 out.push (hb_pair (scalar - gain, loc));
326 }
327
328 /* Case 2neg: Lower is betwen axisMin and axisDef: we add two
329 * tents to keep it down all the way to eternity.
330 *
331 * | |peak
332 * 1...|...............|.o.................
333 * | |/ \
334 * gain|...............+...\...............
335 * |yxxxxxxxxxxxxx/| \
336 * |yyyyyyxxxxxxx/ | \
337 * |yyyyyyyyyyyx/ | \
338 * 0---|-----------o | o----------1
339 * axisMin lower | upper
340 * |
341 * axisDef
342 */
343 else
344 {
345 // A tent's peak cannot fall on axis default. Nudge it.
346 if (lower == axisDef)
347 lower -= EPSILON;
348
349 // Downslope.
350 Triple loc1 {axisMin, lower, axisDef};
351 float scalar1 = 0.f;
352
353 // Eternity justify.
354 Triple loc2 {axisMin, axisMin, lower};
355 float scalar2 = 0.f;
356
357 out.push (hb_pair (scalar1 - gain, loc1));
358 out.push (hb_pair (scalar2 - gain, loc2));
359 }
360
361 return out;
362 }
363
_reverse_triple_distances(const TripleDistances & v)364 static inline TripleDistances _reverse_triple_distances (const TripleDistances &v)
365 { return TripleDistances (v.positive, v.negative); }
366
renormalizeValue(float v,const Triple & triple,const TripleDistances & triple_distances,bool extrapolate)367 float renormalizeValue (float v, const Triple &triple,
368 const TripleDistances &triple_distances, bool extrapolate)
369 {
370 float lower = triple.minimum, def = triple.middle, upper = triple.maximum;
371 assert (lower <= def && def <= upper);
372
373 if (!extrapolate)
374 v = hb_max (hb_min (v, upper), lower);
375
376 if (v == def)
377 return 0.f;
378
379 if (def < 0.f)
380 return -renormalizeValue (-v, _reverse_negate (triple),
381 _reverse_triple_distances (triple_distances), extrapolate);
382
383 /* default >= 0 and v != default */
384 if (v > def)
385 return (v - def) / (upper - def);
386
387 /* v < def */
388 if (lower >= 0.f)
389 return (v - def) / (def - lower);
390
391 /* lower < 0 and v < default */
392 float total_distance = triple_distances.negative * (-lower) + triple_distances.positive * def;
393
394 float v_distance;
395 if (v >= 0.f)
396 v_distance = (def - v) * triple_distances.positive;
397 else
398 v_distance = (-v) * triple_distances.negative + triple_distances.positive * def;
399
400 return (-v_distance) /total_distance;
401 }
402
403 result_t
rebase_tent(Triple tent,Triple axisLimit,TripleDistances axis_triple_distances)404 rebase_tent (Triple tent, Triple axisLimit, TripleDistances axis_triple_distances)
405 {
406 assert (-1.f <= axisLimit.minimum && axisLimit.minimum <= axisLimit.middle && axisLimit.middle <= axisLimit.maximum && axisLimit.maximum <= +1.f);
407 assert (-2.f <= tent.minimum && tent.minimum <= tent.middle && tent.middle <= tent.maximum && tent.maximum <= +2.f);
408 assert (tent.middle != 0.f);
409
410 result_t sols = _solve (tent, axisLimit);
411
412 auto n = [&axisLimit, &axis_triple_distances] (float v) { return renormalizeValue (v, axisLimit, axis_triple_distances); };
413
414 result_t out;
415 for (auto &p : sols)
416 {
417 if (!p.first) continue;
418 if (p.second == Triple{})
419 {
420 out.push (p);
421 continue;
422 }
423 Triple t = p.second;
424 out.push (hb_pair (p.first,
425 Triple{n (t.minimum), n (t.middle), n (t.maximum)}));
426 }
427
428 return out;
429 }
430