1# cython: language_level=3 2# distutils: define_macros=CYTHON_TRACE_NOGIL=1 3 4# Copyright 2023 Google Inc. All Rights Reserved. 5# Copyright 2023 Behdad Esfahbod. All Rights Reserved. 6# 7# Licensed under the Apache License, Version 2.0 (the "License"); 8# you may not use this file except in compliance with the License. 9# You may obtain a copy of the License at 10# 11# http://www.apache.org/licenses/LICENSE-2.0 12# 13# Unless required by applicable law or agreed to in writing, software 14# distributed under the License is distributed on an "AS IS" BASIS, 15# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16# See the License for the specific language governing permissions and 17# limitations under the License. 18 19try: 20 import cython 21 22 COMPILED = cython.compiled 23except (AttributeError, ImportError): 24 # if cython not installed, use mock module with no-op decorators and types 25 from fontTools.misc import cython 26 27 COMPILED = False 28 29from fontTools.misc.bezierTools import splitCubicAtTC 30from collections import namedtuple 31import math 32from typing import ( 33 List, 34 Tuple, 35 Union, 36) 37 38 39__all__ = ["quadratic_to_curves"] 40 41 42# Copied from cu2qu 43@cython.cfunc 44@cython.returns(cython.int) 45@cython.locals( 46 tolerance=cython.double, 47 p0=cython.complex, 48 p1=cython.complex, 49 p2=cython.complex, 50 p3=cython.complex, 51) 52@cython.locals(mid=cython.complex, deriv3=cython.complex) 53def cubic_farthest_fit_inside(p0, p1, p2, p3, tolerance): 54 """Check if a cubic Bezier lies within a given distance of the origin. 55 56 "Origin" means *the* origin (0,0), not the start of the curve. Note that no 57 checks are made on the start and end positions of the curve; this function 58 only checks the inside of the curve. 59 60 Args: 61 p0 (complex): Start point of curve. 62 p1 (complex): First handle of curve. 63 p2 (complex): Second handle of curve. 64 p3 (complex): End point of curve. 65 tolerance (double): Distance from origin. 66 67 Returns: 68 bool: True if the cubic Bezier ``p`` entirely lies within a distance 69 ``tolerance`` of the origin, False otherwise. 70 """ 71 # First check p2 then p1, as p2 has higher error early on. 72 if abs(p2) <= tolerance and abs(p1) <= tolerance: 73 return True 74 75 # Split. 76 mid = (p0 + 3 * (p1 + p2) + p3) * 0.125 77 if abs(mid) > tolerance: 78 return False 79 deriv3 = (p3 + p2 - p1 - p0) * 0.125 80 return cubic_farthest_fit_inside( 81 p0, (p0 + p1) * 0.5, mid - deriv3, mid, tolerance 82 ) and cubic_farthest_fit_inside(mid, mid + deriv3, (p2 + p3) * 0.5, p3, tolerance) 83 84 85@cython.locals( 86 p0=cython.complex, 87 p1=cython.complex, 88 p2=cython.complex, 89 p1_2_3=cython.complex, 90) 91def elevate_quadratic(p0, p1, p2): 92 """Given a quadratic bezier curve, return its degree-elevated cubic.""" 93 94 # https://pomax.github.io/bezierinfo/#reordering 95 p1_2_3 = p1 * (2 / 3) 96 return ( 97 p0, 98 (p0 * (1 / 3) + p1_2_3), 99 (p2 * (1 / 3) + p1_2_3), 100 p2, 101 ) 102 103 104@cython.cfunc 105@cython.locals( 106 start=cython.int, 107 n=cython.int, 108 k=cython.int, 109 prod_ratio=cython.double, 110 sum_ratio=cython.double, 111 ratio=cython.double, 112 t=cython.double, 113 p0=cython.complex, 114 p1=cython.complex, 115 p2=cython.complex, 116 p3=cython.complex, 117) 118def merge_curves(curves, start, n): 119 """Give a cubic-Bezier spline, reconstruct one cubic-Bezier 120 that has the same endpoints and tangents and approxmates 121 the spline.""" 122 123 # Reconstruct the t values of the cut segments 124 prod_ratio = 1.0 125 sum_ratio = 1.0 126 ts = [1] 127 for k in range(1, n): 128 ck = curves[start + k] 129 c_before = curves[start + k - 1] 130 131 # |t_(k+1) - t_k| / |t_k - t_(k - 1)| = ratio 132 assert ck[0] == c_before[3] 133 ratio = abs(ck[1] - ck[0]) / abs(c_before[3] - c_before[2]) 134 135 prod_ratio *= ratio 136 sum_ratio += prod_ratio 137 ts.append(sum_ratio) 138 139 # (t(n) - t(n - 1)) / (t_(1) - t(0)) = prod_ratio 140 141 ts = [t / sum_ratio for t in ts[:-1]] 142 143 p0 = curves[start][0] 144 p1 = curves[start][1] 145 p2 = curves[start + n - 1][2] 146 p3 = curves[start + n - 1][3] 147 148 # Build the curve by scaling the control-points. 149 p1 = p0 + (p1 - p0) / (ts[0] if ts else 1) 150 p2 = p3 + (p2 - p3) / ((1 - ts[-1]) if ts else 1) 151 152 curve = (p0, p1, p2, p3) 153 154 return curve, ts 155 156 157@cython.locals( 158 count=cython.int, 159 num_offcurves=cython.int, 160 i=cython.int, 161 off1=cython.complex, 162 off2=cython.complex, 163 on=cython.complex, 164) 165def add_implicit_on_curves(p): 166 q = list(p) 167 count = 0 168 num_offcurves = len(p) - 2 169 for i in range(1, num_offcurves): 170 off1 = p[i] 171 off2 = p[i + 1] 172 on = off1 + (off2 - off1) * 0.5 173 q.insert(i + 1 + count, on) 174 count += 1 175 return q 176 177 178Point = Union[Tuple[float, float], complex] 179 180 181@cython.locals( 182 cost=cython.int, 183 is_complex=cython.int, 184) 185def quadratic_to_curves( 186 quads: List[List[Point]], 187 max_err: float = 0.5, 188 all_cubic: bool = False, 189) -> List[Tuple[Point, ...]]: 190 """Converts a connecting list of quadratic splines to a list of quadratic 191 and cubic curves. 192 193 A quadratic spline is specified as a list of points. Either each point is 194 a 2-tuple of X,Y coordinates, or each point is a complex number with 195 real/imaginary components representing X,Y coordinates. 196 197 The first and last points are on-curve points and the rest are off-curve 198 points, with an implied on-curve point in the middle between every two 199 consequtive off-curve points. 200 201 Returns: 202 The output is a list of tuples of points. Points are represented 203 in the same format as the input, either as 2-tuples or complex numbers. 204 205 Each tuple is either of length three, for a quadratic curve, or four, 206 for a cubic curve. Each curve's last point is the same as the next 207 curve's first point. 208 209 Args: 210 quads: quadratic splines 211 212 max_err: absolute error tolerance; defaults to 0.5 213 214 all_cubic: if True, only cubic curves are generated; defaults to False 215 """ 216 is_complex = type(quads[0][0]) is complex 217 if not is_complex: 218 quads = [[complex(x, y) for (x, y) in p] for p in quads] 219 220 q = [quads[0][0]] 221 costs = [1] 222 cost = 1 223 for p in quads: 224 assert q[-1] == p[0] 225 for i in range(len(p) - 2): 226 cost += 1 227 costs.append(cost) 228 costs.append(cost) 229 qq = add_implicit_on_curves(p)[1:] 230 costs.pop() 231 q.extend(qq) 232 cost += 1 233 costs.append(cost) 234 235 curves = spline_to_curves(q, costs, max_err, all_cubic) 236 237 if not is_complex: 238 curves = [tuple((c.real, c.imag) for c in curve) for curve in curves] 239 return curves 240 241 242Solution = namedtuple("Solution", ["num_points", "error", "start_index", "is_cubic"]) 243 244 245@cython.locals( 246 i=cython.int, 247 j=cython.int, 248 k=cython.int, 249 start=cython.int, 250 i_sol_count=cython.int, 251 j_sol_count=cython.int, 252 this_sol_count=cython.int, 253 tolerance=cython.double, 254 err=cython.double, 255 error=cython.double, 256 i_sol_error=cython.double, 257 j_sol_error=cython.double, 258 all_cubic=cython.int, 259 is_cubic=cython.int, 260 count=cython.int, 261 p0=cython.complex, 262 p1=cython.complex, 263 p2=cython.complex, 264 p3=cython.complex, 265 v=cython.complex, 266 u=cython.complex, 267) 268def spline_to_curves(q, costs, tolerance=0.5, all_cubic=False): 269 """ 270 q: quadratic spline with alternating on-curve / off-curve points. 271 272 costs: cumulative list of encoding cost of q in terms of number of 273 points that need to be encoded. Implied on-curve points do not 274 contribute to the cost. If all points need to be encoded, then 275 costs will be range(1, len(q)+1). 276 """ 277 278 assert len(q) >= 3, "quadratic spline requires at least 3 points" 279 280 # Elevate quadratic segments to cubic 281 elevated_quadratics = [ 282 elevate_quadratic(*q[i : i + 3]) for i in range(0, len(q) - 2, 2) 283 ] 284 285 # Find sharp corners; they have to be oncurves for sure. 286 forced = set() 287 for i in range(1, len(elevated_quadratics)): 288 p0 = elevated_quadratics[i - 1][2] 289 p1 = elevated_quadratics[i][0] 290 p2 = elevated_quadratics[i][1] 291 if abs(p1 - p0) + abs(p2 - p1) > tolerance + abs(p2 - p0): 292 forced.add(i) 293 294 # Dynamic-Programming to find the solution with fewest number of 295 # cubic curves, and within those the one with smallest error. 296 sols = [Solution(0, 0, 0, False)] 297 impossible = Solution(len(elevated_quadratics) * 3 + 1, 0, 1, False) 298 start = 0 299 for i in range(1, len(elevated_quadratics) + 1): 300 best_sol = impossible 301 for j in range(start, i): 302 j_sol_count, j_sol_error = sols[j].num_points, sols[j].error 303 304 if not all_cubic: 305 # Solution with quadratics between j:i 306 this_count = costs[2 * i - 1] - costs[2 * j] + 1 307 i_sol_count = j_sol_count + this_count 308 i_sol_error = j_sol_error 309 i_sol = Solution(i_sol_count, i_sol_error, i - j, False) 310 if i_sol < best_sol: 311 best_sol = i_sol 312 313 if this_count <= 3: 314 # Can't get any better than this in the path below 315 continue 316 317 # Fit elevated_quadratics[j:i] into one cubic 318 try: 319 curve, ts = merge_curves(elevated_quadratics, j, i - j) 320 except ZeroDivisionError: 321 continue 322 323 # Now reconstruct the segments from the fitted curve 324 reconstructed_iter = splitCubicAtTC(*curve, *ts) 325 reconstructed = [] 326 327 # Knot errors 328 error = 0 329 for k, reconst in enumerate(reconstructed_iter): 330 orig = elevated_quadratics[j + k] 331 err = abs(reconst[3] - orig[3]) 332 error = max(error, err) 333 if error > tolerance: 334 break 335 reconstructed.append(reconst) 336 if error > tolerance: 337 # Not feasible 338 continue 339 340 # Interior errors 341 for k, reconst in enumerate(reconstructed): 342 orig = elevated_quadratics[j + k] 343 p0, p1, p2, p3 = tuple(v - u for v, u in zip(reconst, orig)) 344 345 if not cubic_farthest_fit_inside(p0, p1, p2, p3, tolerance): 346 error = tolerance + 1 347 break 348 if error > tolerance: 349 # Not feasible 350 continue 351 352 # Save best solution 353 i_sol_count = j_sol_count + 3 354 i_sol_error = max(j_sol_error, error) 355 i_sol = Solution(i_sol_count, i_sol_error, i - j, True) 356 if i_sol < best_sol: 357 best_sol = i_sol 358 359 if i_sol_count == 3: 360 # Can't get any better than this 361 break 362 363 sols.append(best_sol) 364 if i in forced: 365 start = i 366 367 # Reconstruct solution 368 splits = [] 369 cubic = [] 370 i = len(sols) - 1 371 while i: 372 count, is_cubic = sols[i].start_index, sols[i].is_cubic 373 splits.append(i) 374 cubic.append(is_cubic) 375 i -= count 376 curves = [] 377 j = 0 378 for i, is_cubic in reversed(list(zip(splits, cubic))): 379 if is_cubic: 380 curves.append(merge_curves(elevated_quadratics, j, i - j)[0]) 381 else: 382 for k in range(j, i): 383 curves.append(q[k * 2 : k * 2 + 3]) 384 j = i 385 386 return curves 387 388 389def main(): 390 from fontTools.cu2qu.benchmark import generate_curve 391 from fontTools.cu2qu import curve_to_quadratic 392 393 tolerance = 0.05 394 reconstruct_tolerance = tolerance * 1 395 curve = generate_curve() 396 quadratics = curve_to_quadratic(curve, tolerance) 397 print( 398 "cu2qu tolerance %g. qu2cu tolerance %g." % (tolerance, reconstruct_tolerance) 399 ) 400 print("One random cubic turned into %d quadratics." % len(quadratics)) 401 curves = quadratic_to_curves([quadratics], reconstruct_tolerance) 402 print("Those quadratics turned back into %d cubics. " % len(curves)) 403 print("Original curve:", curve) 404 print("Reconstructed curve(s):", curves) 405 406 407if __name__ == "__main__": 408 main() 409