aboutsummaryrefslogtreecommitdiff
path: root/Lib/fontTools/qu2cu/qu2cu.py
diff options
context:
space:
mode:
Diffstat (limited to 'Lib/fontTools/qu2cu/qu2cu.py')
-rw-r--r--Lib/fontTools/qu2cu/qu2cu.py408
1 files changed, 408 insertions, 0 deletions
diff --git a/Lib/fontTools/qu2cu/qu2cu.py b/Lib/fontTools/qu2cu/qu2cu.py
new file mode 100644
index 00000000..97a665f6
--- /dev/null
+++ b/Lib/fontTools/qu2cu/qu2cu.py
@@ -0,0 +1,408 @@
+# cython: language_level=3
+# distutils: define_macros=CYTHON_TRACE_NOGIL=1
+
+# Copyright 2023 Google Inc. All Rights Reserved.
+# Copyright 2023 Behdad Esfahbod. All Rights Reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+try:
+ import cython
+
+ COMPILED = cython.compiled
+except (AttributeError, ImportError):
+ # if cython not installed, use mock module with no-op decorators and types
+ from fontTools.misc import cython
+
+ COMPILED = False
+
+from fontTools.misc.bezierTools import splitCubicAtTC
+from collections import namedtuple
+import math
+from typing import (
+ List,
+ Tuple,
+ Union,
+)
+
+
+__all__ = ["quadratic_to_curves"]
+
+
+# Copied from cu2qu
+@cython.cfunc
+@cython.returns(cython.int)
+@cython.locals(
+ tolerance=cython.double,
+ p0=cython.complex,
+ p1=cython.complex,
+ p2=cython.complex,
+ p3=cython.complex,
+)
+@cython.locals(mid=cython.complex, deriv3=cython.complex)
+def cubic_farthest_fit_inside(p0, p1, p2, p3, tolerance):
+ """Check if a cubic Bezier lies within a given distance of the origin.
+
+ "Origin" means *the* origin (0,0), not the start of the curve. Note that no
+ checks are made on the start and end positions of the curve; this function
+ only checks the inside of the curve.
+
+ Args:
+ p0 (complex): Start point of curve.
+ p1 (complex): First handle of curve.
+ p2 (complex): Second handle of curve.
+ p3 (complex): End point of curve.
+ tolerance (double): Distance from origin.
+
+ Returns:
+ bool: True if the cubic Bezier ``p`` entirely lies within a distance
+ ``tolerance`` of the origin, False otherwise.
+ """
+ # First check p2 then p1, as p2 has higher error early on.
+ if abs(p2) <= tolerance and abs(p1) <= tolerance:
+ return True
+
+ # Split.
+ mid = (p0 + 3 * (p1 + p2) + p3) * 0.125
+ if abs(mid) > tolerance:
+ return False
+ deriv3 = (p3 + p2 - p1 - p0) * 0.125
+ return cubic_farthest_fit_inside(
+ p0, (p0 + p1) * 0.5, mid - deriv3, mid, tolerance
+ ) and cubic_farthest_fit_inside(mid, mid + deriv3, (p2 + p3) * 0.5, p3, tolerance)
+
+
+@cython.locals(
+ p0=cython.complex,
+ p1=cython.complex,
+ p2=cython.complex,
+ p1_2_3=cython.complex,
+)
+def elevate_quadratic(p0, p1, p2):
+ """Given a quadratic bezier curve, return its degree-elevated cubic."""
+
+ # https://pomax.github.io/bezierinfo/#reordering
+ p1_2_3 = p1 * (2 / 3)
+ return (
+ p0,
+ (p0 * (1 / 3) + p1_2_3),
+ (p2 * (1 / 3) + p1_2_3),
+ p2,
+ )
+
+
+@cython.cfunc
+@cython.locals(
+ start=cython.int,
+ n=cython.int,
+ k=cython.int,
+ prod_ratio=cython.double,
+ sum_ratio=cython.double,
+ ratio=cython.double,
+ t=cython.double,
+ p0=cython.complex,
+ p1=cython.complex,
+ p2=cython.complex,
+ p3=cython.complex,
+)
+def merge_curves(curves, start, n):
+ """Give a cubic-Bezier spline, reconstruct one cubic-Bezier
+ that has the same endpoints and tangents and approxmates
+ the spline."""
+
+ # Reconstruct the t values of the cut segments
+ prod_ratio = 1.0
+ sum_ratio = 1.0
+ ts = [1]
+ for k in range(1, n):
+ ck = curves[start + k]
+ c_before = curves[start + k - 1]
+
+ # |t_(k+1) - t_k| / |t_k - t_(k - 1)| = ratio
+ assert ck[0] == c_before[3]
+ ratio = abs(ck[1] - ck[0]) / abs(c_before[3] - c_before[2])
+
+ prod_ratio *= ratio
+ sum_ratio += prod_ratio
+ ts.append(sum_ratio)
+
+ # (t(n) - t(n - 1)) / (t_(1) - t(0)) = prod_ratio
+
+ ts = [t / sum_ratio for t in ts[:-1]]
+
+ p0 = curves[start][0]
+ p1 = curves[start][1]
+ p2 = curves[start + n - 1][2]
+ p3 = curves[start + n - 1][3]
+
+ # Build the curve by scaling the control-points.
+ p1 = p0 + (p1 - p0) / (ts[0] if ts else 1)
+ p2 = p3 + (p2 - p3) / ((1 - ts[-1]) if ts else 1)
+
+ curve = (p0, p1, p2, p3)
+
+ return curve, ts
+
+
+@cython.locals(
+ count=cython.int,
+ num_offcurves=cython.int,
+ i=cython.int,
+ off1=cython.complex,
+ off2=cython.complex,
+ on=cython.complex,
+)
+def add_implicit_on_curves(p):
+ q = list(p)
+ count = 0
+ num_offcurves = len(p) - 2
+ for i in range(1, num_offcurves):
+ off1 = p[i]
+ off2 = p[i + 1]
+ on = off1 + (off2 - off1) * 0.5
+ q.insert(i + 1 + count, on)
+ count += 1
+ return q
+
+
+Point = Union[Tuple[float, float], complex]
+
+
+@cython.locals(
+ cost=cython.int,
+ is_complex=cython.int,
+)
+def quadratic_to_curves(
+ quads: List[List[Point]],
+ max_err: float = 0.5,
+ all_cubic: bool = False,
+) -> List[Tuple[Point, ...]]:
+ """Converts a connecting list of quadratic splines to a list of quadratic
+ and cubic curves.
+
+ A quadratic spline is specified as a list of points. Either each point is
+ a 2-tuple of X,Y coordinates, or each point is a complex number with
+ real/imaginary components representing X,Y coordinates.
+
+ The first and last points are on-curve points and the rest are off-curve
+ points, with an implied on-curve point in the middle between every two
+ consequtive off-curve points.
+
+ Returns:
+ The output is a list of tuples of points. Points are represented
+ in the same format as the input, either as 2-tuples or complex numbers.
+
+ Each tuple is either of length three, for a quadratic curve, or four,
+ for a cubic curve. Each curve's last point is the same as the next
+ curve's first point.
+
+ Args:
+ quads: quadratic splines
+
+ max_err: absolute error tolerance; defaults to 0.5
+
+ all_cubic: if True, only cubic curves are generated; defaults to False
+ """
+ is_complex = type(quads[0][0]) is complex
+ if not is_complex:
+ quads = [[complex(x, y) for (x, y) in p] for p in quads]
+
+ q = [quads[0][0]]
+ costs = [1]
+ cost = 1
+ for p in quads:
+ assert q[-1] == p[0]
+ for i in range(len(p) - 2):
+ cost += 1
+ costs.append(cost)
+ costs.append(cost)
+ qq = add_implicit_on_curves(p)[1:]
+ costs.pop()
+ q.extend(qq)
+ cost += 1
+ costs.append(cost)
+
+ curves = spline_to_curves(q, costs, max_err, all_cubic)
+
+ if not is_complex:
+ curves = [tuple((c.real, c.imag) for c in curve) for curve in curves]
+ return curves
+
+
+Solution = namedtuple("Solution", ["num_points", "error", "start_index", "is_cubic"])
+
+
+@cython.locals(
+ i=cython.int,
+ j=cython.int,
+ k=cython.int,
+ start=cython.int,
+ i_sol_count=cython.int,
+ j_sol_count=cython.int,
+ this_sol_count=cython.int,
+ tolerance=cython.double,
+ err=cython.double,
+ error=cython.double,
+ i_sol_error=cython.double,
+ j_sol_error=cython.double,
+ all_cubic=cython.int,
+ is_cubic=cython.int,
+ count=cython.int,
+ p0=cython.complex,
+ p1=cython.complex,
+ p2=cython.complex,
+ p3=cython.complex,
+ v=cython.complex,
+ u=cython.complex,
+)
+def spline_to_curves(q, costs, tolerance=0.5, all_cubic=False):
+ """
+ q: quadratic spline with alternating on-curve / off-curve points.
+
+ costs: cumulative list of encoding cost of q in terms of number of
+ points that need to be encoded. Implied on-curve points do not
+ contribute to the cost. If all points need to be encoded, then
+ costs will be range(1, len(q)+1).
+ """
+
+ assert len(q) >= 3, "quadratic spline requires at least 3 points"
+
+ # Elevate quadratic segments to cubic
+ elevated_quadratics = [
+ elevate_quadratic(*q[i : i + 3]) for i in range(0, len(q) - 2, 2)
+ ]
+
+ # Find sharp corners; they have to be oncurves for sure.
+ forced = set()
+ for i in range(1, len(elevated_quadratics)):
+ p0 = elevated_quadratics[i - 1][2]
+ p1 = elevated_quadratics[i][0]
+ p2 = elevated_quadratics[i][1]
+ if abs(p1 - p0) + abs(p2 - p1) > tolerance + abs(p2 - p0):
+ forced.add(i)
+
+ # Dynamic-Programming to find the solution with fewest number of
+ # cubic curves, and within those the one with smallest error.
+ sols = [Solution(0, 0, 0, False)]
+ impossible = Solution(len(elevated_quadratics) * 3 + 1, 0, 1, False)
+ start = 0
+ for i in range(1, len(elevated_quadratics) + 1):
+ best_sol = impossible
+ for j in range(start, i):
+ j_sol_count, j_sol_error = sols[j].num_points, sols[j].error
+
+ if not all_cubic:
+ # Solution with quadratics between j:i
+ this_count = costs[2 * i - 1] - costs[2 * j] + 1
+ i_sol_count = j_sol_count + this_count
+ i_sol_error = j_sol_error
+ i_sol = Solution(i_sol_count, i_sol_error, i - j, False)
+ if i_sol < best_sol:
+ best_sol = i_sol
+
+ if this_count <= 3:
+ # Can't get any better than this in the path below
+ continue
+
+ # Fit elevated_quadratics[j:i] into one cubic
+ try:
+ curve, ts = merge_curves(elevated_quadratics, j, i - j)
+ except ZeroDivisionError:
+ continue
+
+ # Now reconstruct the segments from the fitted curve
+ reconstructed_iter = splitCubicAtTC(*curve, *ts)
+ reconstructed = []
+
+ # Knot errors
+ error = 0
+ for k, reconst in enumerate(reconstructed_iter):
+ orig = elevated_quadratics[j + k]
+ err = abs(reconst[3] - orig[3])
+ error = max(error, err)
+ if error > tolerance:
+ break
+ reconstructed.append(reconst)
+ if error > tolerance:
+ # Not feasible
+ continue
+
+ # Interior errors
+ for k, reconst in enumerate(reconstructed):
+ orig = elevated_quadratics[j + k]
+ p0, p1, p2, p3 = tuple(v - u for v, u in zip(reconst, orig))
+
+ if not cubic_farthest_fit_inside(p0, p1, p2, p3, tolerance):
+ error = tolerance + 1
+ break
+ if error > tolerance:
+ # Not feasible
+ continue
+
+ # Save best solution
+ i_sol_count = j_sol_count + 3
+ i_sol_error = max(j_sol_error, error)
+ i_sol = Solution(i_sol_count, i_sol_error, i - j, True)
+ if i_sol < best_sol:
+ best_sol = i_sol
+
+ if i_sol_count == 3:
+ # Can't get any better than this
+ break
+
+ sols.append(best_sol)
+ if i in forced:
+ start = i
+
+ # Reconstruct solution
+ splits = []
+ cubic = []
+ i = len(sols) - 1
+ while i:
+ count, is_cubic = sols[i].start_index, sols[i].is_cubic
+ splits.append(i)
+ cubic.append(is_cubic)
+ i -= count
+ curves = []
+ j = 0
+ for i, is_cubic in reversed(list(zip(splits, cubic))):
+ if is_cubic:
+ curves.append(merge_curves(elevated_quadratics, j, i - j)[0])
+ else:
+ for k in range(j, i):
+ curves.append(q[k * 2 : k * 2 + 3])
+ j = i
+
+ return curves
+
+
+def main():
+ from fontTools.cu2qu.benchmark import generate_curve
+ from fontTools.cu2qu import curve_to_quadratic
+
+ tolerance = 0.05
+ reconstruct_tolerance = tolerance * 1
+ curve = generate_curve()
+ quadratics = curve_to_quadratic(curve, tolerance)
+ print(
+ "cu2qu tolerance %g. qu2cu tolerance %g." % (tolerance, reconstruct_tolerance)
+ )
+ print("One random cubic turned into %d quadratics." % len(quadratics))
+ curves = quadratic_to_curves([quadratics], reconstruct_tolerance)
+ print("Those quadratics turned back into %d cubics. " % len(curves))
+ print("Original curve:", curve)
+ print("Reconstructed curve(s):", curves)
+
+
+if __name__ == "__main__":
+ main()
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-29 09:08:02 +0000