• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1"""Helpers for manipulating 2D points and vectors in COLR table."""
2
3from math import copysign, cos, hypot, pi
4from fontTools.misc.roundTools import otRound
5
6
7def _vector_between(origin, target):
8    return (target[0] - origin[0], target[1] - origin[1])
9
10
11def _round_point(pt):
12    return (otRound(pt[0]), otRound(pt[1]))
13
14
15def _unit_vector(vec):
16    length = hypot(*vec)
17    if length == 0:
18        return None
19    return (vec[0] / length, vec[1] / length)
20
21
22# This is the same tolerance used by Skia's SkTwoPointConicalGradient.cpp to detect
23# when a radial gradient's focal point lies on the end circle.
24_NEARLY_ZERO = 1 / (1 << 12)  # 0.000244140625
25
26
27# The unit vector's X and Y components are respectively
28#   U = (cos(α), sin(α))
29# where α is the angle between the unit vector and the positive x axis.
30_UNIT_VECTOR_THRESHOLD = cos(3 / 8 * pi)  # == sin(1/8 * pi) == 0.38268343236508984
31
32
33def _rounding_offset(direction):
34    # Return 2-tuple of -/+ 1.0 or 0.0 approximately based on the direction vector.
35    # We divide the unit circle in 8 equal slices oriented towards the cardinal
36    # (N, E, S, W) and intermediate (NE, SE, SW, NW) directions. To each slice we
37    # map one of the possible cases: -1, 0, +1 for either X and Y coordinate.
38    # E.g. Return (+1.0, -1.0) if unit vector is oriented towards SE, or
39    # (-1.0, 0.0) if it's pointing West, etc.
40    uv = _unit_vector(direction)
41    if not uv:
42        return (0, 0)
43
44    result = []
45    for uv_component in uv:
46        if -_UNIT_VECTOR_THRESHOLD <= uv_component < _UNIT_VECTOR_THRESHOLD:
47            # unit vector component near 0: direction almost orthogonal to the
48            # direction of the current axis, thus keep coordinate unchanged
49            result.append(0)
50        else:
51            # nudge coord by +/- 1.0 in direction of unit vector
52            result.append(copysign(1.0, uv_component))
53    return tuple(result)
54
55
56class Circle:
57    def __init__(self, centre, radius):
58        self.centre = centre
59        self.radius = radius
60
61    def __repr__(self):
62        return f"Circle(centre={self.centre}, radius={self.radius})"
63
64    def round(self):
65        return Circle(_round_point(self.centre), otRound(self.radius))
66
67    def inside(self, outer_circle):
68        dist = self.radius + hypot(*_vector_between(self.centre, outer_circle.centre))
69        return (
70            abs(outer_circle.radius - dist) <= _NEARLY_ZERO
71            or outer_circle.radius > dist
72        )
73
74    def concentric(self, other):
75        return self.centre == other.centre
76
77    def move(self, dx, dy):
78        self.centre = (self.centre[0] + dx, self.centre[1] + dy)
79
80
81def round_start_circle_stable_containment(c0, r0, c1, r1):
82    """Round start circle so that it stays inside/outside end circle after rounding.
83
84    The rounding of circle coordinates to integers may cause an abrupt change
85    if the start circle c0 is so close to the end circle c1's perimiter that
86    it ends up falling outside (or inside) as a result of the rounding.
87    To keep the gradient unchanged, we nudge it in the right direction.
88
89    See:
90    https://github.com/googlefonts/colr-gradients-spec/issues/204
91    https://github.com/googlefonts/picosvg/issues/158
92    """
93    start, end = Circle(c0, r0), Circle(c1, r1)
94
95    inside_before_round = start.inside(end)
96
97    round_start = start.round()
98    round_end = end.round()
99    inside_after_round = round_start.inside(round_end)
100
101    if inside_before_round == inside_after_round:
102        return round_start
103    elif inside_after_round:
104        # start was outside before rounding: we need to push start away from end
105        direction = _vector_between(round_end.centre, round_start.centre)
106        radius_delta = +1.0
107    else:
108        # start was inside before rounding: we need to push start towards end
109        direction = _vector_between(round_start.centre, round_end.centre)
110        radius_delta = -1.0
111    dx, dy = _rounding_offset(direction)
112
113    # At most 2 iterations ought to be enough to converge. Before the loop, we
114    # know the start circle didn't keep containment after normal rounding; thus
115    # we continue adjusting by -/+ 1.0 until containment is restored.
116    # Normal rounding can at most move each coordinates -/+0.5; in the worst case
117    # both the start and end circle's centres and radii will be rounded in opposite
118    # directions, e.g. when they move along a 45 degree diagonal:
119    #   c0 = (1.5, 1.5) ===> (2.0, 2.0)
120    #   r0 = 0.5 ===> 1.0
121    #   c1 = (0.499, 0.499) ===> (0.0, 0.0)
122    #   r1 = 2.499 ===> 2.0
123    # In this example, the relative distance between the circles, calculated
124    # as r1 - (r0 + distance(c0, c1)) is initially 0.57437 (c0 is inside c1), and
125    # -1.82842 after rounding (c0 is now outside c1). Nudging c0 by -1.0 on both
126    # x and y axes moves it towards c1 by hypot(-1.0, -1.0) = 1.41421. Two of these
127    # moves cover twice that distance, which is enough to restore containment.
128    max_attempts = 2
129    for _ in range(max_attempts):
130        if round_start.concentric(round_end):
131            # can't move c0 towards c1 (they are the same), so we change the radius
132            round_start.radius += radius_delta
133            assert round_start.radius >= 0
134        else:
135            round_start.move(dx, dy)
136        if inside_before_round == round_start.inside(round_end):
137            break
138    else:  # likely a bug
139        raise AssertionError(
140            f"Rounding circle {start} "
141            f"{'inside' if inside_before_round else 'outside'} "
142            f"{end} failed after {max_attempts} attempts!"
143        )
144
145    return round_start
146