diff options
-rw-r--r-- | third_party/fontcrunch/LICENSE | 202 | ||||
-rw-r--r-- | third_party/fontcrunch/Makefile | 31 | ||||
-rw-r--r-- | third_party/fontcrunch/README.md | 26 | ||||
-rw-r--r-- | third_party/fontcrunch/README.third_party | 10 | ||||
-rw-r--r-- | third_party/fontcrunch/fontcrunch.py | 412 | ||||
-rw-r--r-- | third_party/fontcrunch/quadopt.cc | 484 |
6 files changed, 1165 insertions, 0 deletions
diff --git a/third_party/fontcrunch/LICENSE b/third_party/fontcrunch/LICENSE new file mode 100644 index 0000000..ef51da2 --- /dev/null +++ b/third_party/fontcrunch/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +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. diff --git a/third_party/fontcrunch/Makefile b/third_party/fontcrunch/Makefile new file mode 100644 index 0000000..e73ca38 --- /dev/null +++ b/third_party/fontcrunch/Makefile @@ -0,0 +1,31 @@ +# Copyright 2014 Google Inc. 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. +# +# Contributor: Raph Levien + +SRC = $(wildcard */*.bz) +OPT = $(patsubst %.bz, %.bzopt, $(SRC)) + +dummy: $(OPT) + +quadopt: quadopt.cc + $(CXX) $< -O3 -o $@ + +%.bzopt: %.bz quadopt + ./quadopt $< $@ + +clean: + rm -f quadopt + find . -name '*.bz' -delete + find . -name '*.bzopt' -delete
\ No newline at end of file diff --git a/third_party/fontcrunch/README.md b/third_party/fontcrunch/README.md new file mode 100644 index 0000000..98f3981 --- /dev/null +++ b/third_party/fontcrunch/README.md @@ -0,0 +1,26 @@ +# Fontcrunch + +By Raph Levien, Google + +This is a tool for TrueType font spline optimization - a "simplify" command. +It tries to create a visual match for the spline using the smallest number of TrueType points. +It is notable for counting on-curve points interpolated between two off-curve points as "free," making useful filesize savings. + +It depends on fonttools, and has some legacy dependencies on [spiro-0.01](http://www.levien.com/spiro/spiro-0.01.tar.gz) +This code is available under the Apache v2 license. Spiro code is GNU GPL v2 or later, and Spiro curves are subject to a US patent. + +Create 256 directories named 00 .. ff, and populate them with lots of files with .bz extension. +Each of these is a nontrivial segment of quad beziers cut from the font, stored as a `x0 y0 x1 y1 x2 y2` line per bezier. +Lines are represented with `(x1, y1)` at the midpoint of the two endpoints. + +`python fontcrunch.py gen yourfont.ttf` + +Runs the optimizer on each of the .bz files, producing a .bzopt. +You can control the level of precision by editing "penalty" in the code (should of course be a parameter). +On a fast computer, it should go through about 5 glyphs a second, depending on complexity. + +`make -j16 # or whatever level of parallelism makes sense on your computer` + +Regenerate a new TrueType font. You can look at the outlines to check the quality of the result. + +`python fontcrunch.py pack yourfont.ttf > /tmp/outlines.ps newfont.ttf` diff --git a/third_party/fontcrunch/README.third_party b/third_party/fontcrunch/README.third_party new file mode 100644 index 0000000..7680eae --- /dev/null +++ b/third_party/fontcrunch/README.third_party @@ -0,0 +1,10 @@ +URL: https://github.com/googlefonts/fontbakery/archive/182512a19071f38f5fe1e26a67c69a671fdad2d8.zip +Version: 182512a19071f38f5fe1e26a67c69a671fdad2d8 +License: Apache 2.0 +License File: LICENSE + +Description: +Fontcrunch is a TrueType outline simplification tool. + +Local Modifications: +Only the fontcrunch directory is included from fontbakery. diff --git a/third_party/fontcrunch/fontcrunch.py b/third_party/fontcrunch/fontcrunch.py new file mode 100644 index 0000000..d129452 --- /dev/null +++ b/third_party/fontcrunch/fontcrunch.py @@ -0,0 +1,412 @@ +# Copyright 2014 Google Inc. 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. +# +# Contributor: Raph Levien + +from fontTools import ttLib +from fontTools.ttLib.tables import _g_l_y_f +import fromcubic +import tocubic +import pcorn +import math +import md5 + +import sys +import os + +def lerppt(t, p0, p1): + return (p0[0] + t * (p1[0] - p0[0]), p0[1] + t * (p1[1] - p0[1])) + +def glyph_to_bzs(g): + bzs = [] + for i in range(g.numberOfContours): + beg = 0 if i == 0 else g.endPtsOfContours[i - 1] + 1 + end = g.endPtsOfContours[i] + 1 + n = end - beg + pts = g.coordinates[beg:end] + flags = g.flags[beg:end] + bz = [] + for j in range(n): + x1, y1 = pts[(j+1) % n] + if flags[j] and flags[(j+1) % n]: + bz.append((pts[j], (x1, y1))) + elif not flags[j]: + if flags[j - 1]: + x0, y0 = pts[j - 1] + else: + x0, y0 = lerppt(0.5, pts[j - 1], pts[j]) + if not flags[(j+1) % n]: + x1, y1 = lerppt(0.5, (x1, y1), pts[j]) + if pts[j] == (x0, y0) or pts[j] == (x1, y1): + # degenerate quad, treat as line + bz.append(((x0, y0), (x1, y1))) + else: + bz.append(((x0, y0), pts[j], (x1, y1))) + bzs.append(bz) + return bzs + +# convert all quadratics to cubics +def raise_to_cubic(bzs): + result = [] + for sp in bzs: + r = [] + for bz in sp: + if len(bz) == 3: + r.append((bz[0], lerppt(2./3, bz[0], bz[1]), lerppt(2./3, bz[2], bz[1]), bz[2])) + else: + r.append(bz) + result.append(r) + return result + +def plot(bzs): + tocubic.plot_prolog() + print '/ss 1.5 def' + print '/circle { ss 0 moveto currentpoint exch ss sub exch ss 0 360 arc } bind def' + fromcubic.plot_bzs(bzs, (100, 100), 0.25, fancy = True) + print 'showpage' + +def getbreaks(curve): + extrema = curve.find_extrema() + extrema.extend(curve.find_breaks()) + extrema.append(0) + extrema.append(curve.arclen) + extrema.sort() + result = [] + for i in range(len(extrema)): + if i == 0 or extrema[i] > extrema[i-1] + 0.1: + result.append(extrema[i]) + print result + return result + +class Pt: + def __init__(self, curve, s): + self.s = s + x, y = curve.xy(s) + self.xy = (round(x), round(y)) + self.th = curve.th(s) + +class MiniState: + def __init__(self, score, sp): + self.score = score + self.sp = sp + def combine(self, score, bz): + newscore = self.score + score + penalty * (len(bz) - 1) + if len(bz) == 3 and len(self.sp): + lastbz = self.sp[-1] + if len(lastbz) == 3: + if lerppt(0.5, lastbz[1], bz[1]) == bz[0]: + newscore -= penalty + return MiniState(newscore, self.sp + [bz]) + +class State: + def __init__(self, base): + self.base = base # a MiniState + self.map = {} + +penalty = 0.05 + +def measure_bz(curve, s0, s1, bz): + bz_arclen = tocubic.bz_arclength_rk4(bz) + if bz_arclen == 0: return 1e9 + arclen_scale = (s1 - s0) / bz_arclen + def th_fn(s): + return curve.th(s0 + arclen_scale * s, s == 0) + return tocubic.measure_bz_rk4(bz, bz_arclen, th_fn) + +def measure_line(curve, st, pt0, pt1): + bz = (pt0.xy, pt1.xy) + return st.combine(measure_bz(curve, pt0.s, pt1.s, bz), bz) + +def intersect(xy0, th0, xy1, th1): + x0, y0 = xy0 + x1, y1 = xy1 + dx0 = math.cos(th0) + dy0 = math.sin(th0) + dx1 = math.cos(th1) + dy1 = math.sin(th1) + det = dx0 * dy1 - dy0 * dx1 + if abs(det) < 1e-6: return None + det = 1 / det + a = y0 * dx0 - x0 * dy0 + b = y1 * dx1 - x1 * dy1 + x = (a * dx1 - b * dx0) * det + y = (a * dy1 - b * dy0) * det + return (x, y) + +def measure_quad(curve, st, pt0, pt1): + xy = intersect(pt0.xy, pt0.th, pt1.xy, pt1.th) + if xy is None: return None + x, y = xy + x = round(x) + y = round(y) + bz = (pt0.xy, (x, y), pt1.xy) + return st.combine(measure_bz(curve, pt0.s, pt1.s, bz), bz) + +class Thcache: + mult = 1 + def __init__(self, curve, s0, s1): + self.s0 = s0 + self.s1 = s1 + self.ths1 = curve.th(s1, False) + self.vals = [] + scale = 1.0 / self.mult + for i in range(int(self.mult * (s1 - s0)) + 2): + s = min(s1, s0 + i * scale) + self.vals.append(curve.th(s, i == 0)) + def th(self, s, ds): + if s > self.s1: return self.ths1 + s = self.mult * (s - self.s0) + bucket = int(s) + v0 = self.vals[bucket] + v1 = self.vals[bucket + 1] + return v0 + (s - bucket) * (v1 - v0) + +# produce an optimized sequence of quadratics from s0 to s1 of the curve +def optimize_run(curve, s0, s1): + print s0, s1 + n = int(round(1 * (s1 - s0))) + pts = [] + for i in range(n + 1): + pts.append(Pt(curve, s0 + (s1 - s0) * i / n)) + cache = Thcache(curve, s0, s1) + states = [MiniState(0, [])] + newst = measure_line(cache, states[0], pts[0], pts[n]) + bestst = newst + newst = measure_quad(cache, states[0], pts[0], pts[n]) + if newst and newst.score < bestst.score: + bestst = newst + if bestst.score <= 3 * penalty: + return bestst.sp + # Quick scan for two-quad sections + # Note, could do line+quad and quad+line too, but less likely to win + for i in range(1, n): + st1 = measure_quad(cache, states[0], pts[0], pts[i]) + if st1: + st2 = measure_quad(cache, st1, pts[i], pts[n]) + if st2 and st2.score < bestst.score: + bestst = st2 + if bestst.score <= 4 * penalty: + return bestst.sp + for i in range(1, n + 1): + best = 1e9 + badcount = 0 + for j in range(i - 1, -1, -1): + newst = measure_line(cache, states[j], pts[j], pts[i]) + if newst and newst.score < best: + best, bestst = newst.score, newst + newst = measure_quad(cache, states[j], pts[j], pts[i]) + if newst and newst.score < best: + best, bestst = newst.score, newst + if newst is None or newst.score - states[j].score > 10 * penalty: + badcount += 1 + if badcount == 20: + break + else: + badcount = 0 + states.append(bestst) + return states[n].sp + +def optimize(bzs): + result = [] + for sp in fromcubic.bzs_to_pcorn(bzs): + r = [] + curve = pcorn.Curve(sp) + breaks = getbreaks(curve) + for i in range(len(breaks) - 1): + r.extend(optimize_run(curve, breaks[i], breaks[i + 1])) + result.append(r) + return result + +def plot_tt_raw(bzs, fancy = True): + x0 = 100 + y0 = 100 + scale = 0.25 + fromcubic.plot_bzs(raise_to_cubic(bzs), (x0, y0), scale) + if fancy: + for sp in bzs: + for i in range(len(sp)): + lastbz = sp[i - 1] + bz = sp[i] + if len(bz) != 3 or len(lastbz) != 3 or lerppt(0.5, lastbz[1], bz[1]) != bz[0]: + x, y = bz[0] + print 'gsave %f %f translate circle fill grestore' % (x * scale + x0, y * scale + y0) + if len(bz) == 3: + x, y = bz[1] + print 'gsave %f %f translate circle stroke grestore' % (x * scale + x0, y * scale + y0) + +def plot_tt(bzs, orig = None, style = 'redcyan'): + tocubic.plot_prolog() + print '/ss 2 def' + print '/circle { ss 0 moveto currentpoint exch ss sub exch ss 0 360 arc } bind def' + if style == 'redcyan': + print 'true setoverprint true setoverprintmode' + x0 = 100 + y0 = 100 + scale = 0.25 + if orig: + print '0 1 1 0 setcmykcolor' + fancy = (style == 'redcyan') + plot_tt_raw(orig, fancy) + if style == 'redcyan': + print '1 0 0 0 setcmykcolor' + elif style == 'redblack': + print '0 0 0 1 setcmykcolor' + plot_tt_raw(bzs) + print 'showpage' + +def segment_sp(sp): + bks = set() + + # direction changes + xsg = 0 + ysg = 0 + for i in range(2 * len(sp)): + imod = i % len(sp) + xsg1 = sp[imod][-1][0] - sp[imod][0][0] + ysg1 = sp[imod][-1][1] - sp[imod][0][1] + if xsg * xsg1 < 0 or ysg * ysg1 < 0: + bks.add(imod) + xsg = xsg1 + ysg = ysg1 + else: + if xsg == 0: xsg = xsg1 + if ysg == 0: ysg = ysg1 + + # angle breaks + for i in range(len(sp)): + dx0 = sp[i-1][-1][0] - sp[i-1][-2][0] + dy0 = sp[i-1][-1][1] - sp[i-1][-2][1] + dx1 = sp[i][1][0] - sp[i][0][0] + dy1 = sp[i][1][1] - sp[i][0][1] + bend = dx1 * dy0 - dx0 * dy1 + if (dx0 == 0 and dy0 == 0) or (dx1 == 0 and dy1 == 0): + bks.add(i) + else: + bend = bend / (math.hypot(dx0, dy0) * math.hypot(dx1, dy1)) + # for small angles, bend is in units of radians + if abs(bend) > 0.02: + bks.add(i) + + return sorted(bks) + +def seg_to_string(sp, bk0, bk1): + if bk1 < bk0: + bk1 += len(sp) + res = [] + for i in range(bk0, bk1): + bz = sp[i % len(sp)] + if len(bz) == 2: + # just represent lines as quads + bz = (bz[0], lerppt(0.5, bz[0], bz[1]), bz[1]) + res.append(' '.join(['%g' % z for xy in bz for z in xy]) + '\n') + return ''.join(res) + +USE_SUBDIRS = True + +# get filename, ensuring directory exists +def seg_fn(segstr): + fn = md5.new(segstr).hexdigest()[:16] + if USE_SUBDIRS: + dirname = fn[:2] + if not os.path.exists(dirname): + os.mkdir(dirname) + fn = dirname + '/' + fn[2:] + fn += '.bz' + return fn + +def gen_segs(glyph): + bzs = glyph_to_bzs(glyph) + for sp in bzs: + bks = segment_sp(sp) + for i in range(len(bks)): + bk0, bk1 = bks[i], bks[(i + 1) % len(bks)] + if bk1 != (bk0 + 1) % len(sp) or len(sp[bk0]) != 2: + segstr = seg_to_string(sp, bk0, bk1) + fn = seg_fn(segstr) + file(fn, 'w').write(segstr) + +def generate(fn): + f = ttLib.TTFont(fn) + glyf = f['glyf'] + for name, g in glyf.glyphs.iteritems(): + print 'generating', name + gen_segs(g) + +def read_bzs(fn): + result = [] + for l in file(fn): + z = [float(z) for z in l.split()] + bz = ((z[0], z[1]), (z[2], z[3]), (z[4], z[5])) + if bz[1] == lerppt(0.5, bz[0], bz[2]): + bz = (bz[0], bz[2]) + result.append(bz) + return result + +def pt_to_int(pt): + # todo: should investigate non-int points + return (int(round(pt[0])), int(round(pt[1]))) + +def bzs_to_glyph(bzs, glyph): + coordinates = [] + flags = [] + endPtsOfContours = [] + for sp in bzs: + for i in range(len(sp)): + lastbz = sp[i - 1] + bz = sp[i] + if len(bz) != 3 or len(lastbz) != 3 or lerppt(0.5, lastbz[1], bz[1]) != bz[0]: + coordinates.append(pt_to_int(bz[0])) + flags.append(1) + if len(bz) == 3: + coordinates.append(pt_to_int(bz[1])) + flags.append(0) + endPtsOfContours.append(len(coordinates) - 1) + glyph.coordinates = _g_l_y_f.GlyphCoordinates(coordinates) + glyph.flags = flags + glyph.endPtsOfContours = endPtsOfContours + +def repack_glyph(glyph): + bzs = glyph_to_bzs(glyph) + newbzs = [] + for sp in bzs: + bks = segment_sp(sp) + newsp = [] + for i in range(len(bks)): + bk0, bk1 = bks[i], bks[(i + 1) % len(bks)] + if bk1 != (bk0 + 1) % len(sp) or len(sp[bk0]) != 2: + segstr = seg_to_string(sp, bk0, bk1) + fn = seg_fn(segstr) + 'opt' + newsp.extend(read_bzs(fn)) + else: + newsp.append(sp[bk0]) + newbzs.append(newsp) + bzs_to_glyph(newbzs, glyph) + plot_tt(newbzs, bzs, style = 'redblack') + +def repack(fn, newfn): + f = ttLib.TTFont(fn) + glyf = f['glyf'] + for name, g in glyf.glyphs.iteritems(): + if not g.isComposite(): + repack_glyph(g) + if newfn: + f.save(newfn) + +def main(argv): + if argv[1] == 'gen': + generate(sys.argv[2]) + elif argv[1] == 'pack': + repack(sys.argv[2], sys.argv[3] if len(argv) >= 3 else None) + +main(sys.argv) diff --git a/third_party/fontcrunch/quadopt.cc b/third_party/fontcrunch/quadopt.cc new file mode 100644 index 0000000..59f3523 --- /dev/null +++ b/third_party/fontcrunch/quadopt.cc @@ -0,0 +1,484 @@ +/* + * Copyright 2014 Google Inc. 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. + * + * Contributor: Raph Levien + */ + +#include <iostream> +#include <fstream> +#include <cmath> +#include <vector> +#include <algorithm> + +using std::vector; + +#define HALF_STEP 1 + +class Point { +public: + Point() : x(0), y(0) { } + Point(double x, double y) : x(x), y(y) { } + double x, y; +}; + +bool operator==(const Point& p0, const Point& p1) { + return p0.x == p1.x && p0.y == p1.y; +} + +std::ostream& operator<<(std::ostream& os, const Point& p) { + os << "(" << p.x << ", " << p.y << ")"; + return os; +} + +double dist(Point p0, Point p1) { + return std::hypot(p0.x - p1.x, p0.y - p1.y); +} + +double dist2(Point p0, Point p1) { + double dx = p0.x - p1.x; + double dy = p0.y - p1.y; + return dx * dx + dy * dy; +} + +Point lerp(double t, Point p0, Point p1) { + return Point(p0.x + t * (p1.x - p0.x), p0.y + t * (p1.y - p0.y)); +} + +Point unitize(Point p) { + double scale = 1/std::hypot(p.x, p.y); + return Point(p.x * scale, p.y * scale); +} + +Point round(Point p) { + return Point(std::round(p.x), std::round(p.y)); +} + +class Quad { +public: + Quad() : p() { } + Quad(Point p0, Point p1, Point p2) : p() { + p[0] = p0; + p[1] = p1; + p[2] = p2; + } + Point p[3]; + double arclen() const; + Point eval(double t) const; + bool isLine() const; + void print(std::ostream& o) const { + o << p[0].x << " " << p[0].y << " " << p[1].x << " " << p[1].y << " " + << p[2].x << " " << p[2].y << std::endl; + } +}; + +bool Quad::isLine() const { + return p[1] == lerp(0.5, p[0], p[2]); +} + +// One step of a 4th-order Runge-Kutta numerical integration +template <size_t n, typename F> +void rk4(double y[n], double x, double h, F& derivs) { + double dydx[n]; + double dyt[n]; + double dym[n]; + double yt[n]; + derivs(dydx, x, y); + double hh = h * .5; + double h6 = h * (1./6); + for (size_t i = 0; i < n; i++) { + yt[i] = y[i] + hh * dydx[i]; + } + derivs(dyt, x + hh, yt); + for (size_t i = 0; i < n; i++) { + yt[i] = y[i] + hh * dyt[i]; + } + derivs(dym, x + hh, yt); + for (size_t i = 0; i < n; i++) { + yt[i] = y[i] + h * dym[i]; + dym[i] += dyt[i]; + } + derivs(dyt, x + h, yt); + for (size_t i = 0; i < n; i++) { + y[i] += h6 * (dydx[i] + dyt[i] + 2 * dym[i]); + } +} + +class ArclenFunctor { +public: + ArclenFunctor(const Quad& q) + : dx0(2 * (q.p[1].x - q.p[0].x)) + , dx1(2 * (q.p[2].x - q.p[1].x)) + , dy0(2 * (q.p[1].y - q.p[0].y)) + , dy1(2 * (q.p[2].y - q.p[1].y)) { } + void operator()(double dydx[1], double t, const double y[1]) { + Point p(deriv(t)); + dydx[0] = std::hypot(p.x, p.y); + } + Point deriv(double t) const { + return Point(dx0 + t * (dx1 - dx0), dy0 + t * (dy1 - dy0)); + } +private: + double dx0, dy0, dx1, dy1; +}; + +double Quad::arclen() const { + ArclenFunctor derivs(*this); + const int n = 10; + double dt = 1./n; + double t = 0; + double y[1] = { 0 }; + for (int i = 0; i < n; i++) { + rk4<1>(y, t, dt, derivs); + t += dt; + } + return y[0]; +} + +Point Quad::eval(double t) const { + Point p01(lerp(t, p[0], p[1])); + Point p12(lerp(t, p[1], p[2])); + return lerp(t, p01, p12); +} + +class Thetas { +public: + void init(const vector<Quad>& qs); + Point xy(double s) const; + Point dir(double s) const; + double arclen; +private: + vector<Point> xys; + vector<Point> dirs; +}; + +void Thetas::init(const vector<Quad>& qs) { + xys.clear(); + dirs.clear(); + double s = 0; + int ix = 0; + Point lastxy; + Point lastd; + double lasts = -1; + for (size_t i = 0; i < qs.size(); i++) { + const Quad& q = qs[i]; + ArclenFunctor derivs(q); + const int n = 100; + double dt = 1./n; + double t = 0; + double y[1]; + y[0] = s; + for (int j = 0; j < n; j++) { + Point thisxy(q.eval(t)); + Point thisd(derivs.deriv(t)); + while (ix <= y[0]) { + double u = (ix - lasts) / (y[0] - lasts); + xys.push_back(lerp(u, lastxy, thisxy)); + dirs.push_back(unitize(lerp(u, lastd, thisd))); + ix++; + } + lasts = y[0]; + rk4<1>(y, t, dt, derivs); + t += dt; + lastxy = thisxy; + lastd = thisd; + } + s = y[0]; + } + const Quad& q = qs[qs.size() - 1]; + Point thisxy(q.p[2]); + Point thisd(ArclenFunctor(q).deriv(1)); + while (ix <= s + 1) { + double u = (ix - lasts) / (s - lasts); + xys.push_back(lerp(u, lastxy, thisxy)); + dirs.push_back(unitize(lerp(u, lastd, thisd))); + ix++; + } + arclen = s; +} + +Point Thetas::xy(double s) const { + int bucket = (int)s; + double frac = s - bucket; + return lerp(frac, xys[bucket], xys[bucket + 1]); +} + +Point Thetas::dir(double s) const { + int bucket = (int)s; + double frac = s - bucket; + return lerp(frac, dirs[bucket], dirs[bucket + 1]); +} + +#define NORM_LEVEL 2 + +// L1 angle norm, 2, L2 angle norm, 0.05 +// L1 distance norm, 200 +double penalty = 1; +double dist_factor = .005; +double angle_factor = 5; + + +class MeasureFunctor { +public: + MeasureFunctor(const Thetas& curve, double s0, double ss, const ArclenFunctor& af, + Quad q) + : curve(curve), s0(s0), ss(ss), af(af), q(q) { } + void operator()(double dydx[2], double t, const double y[2]) { + Point dxy(af.deriv(t)); + dydx[0] = std::hypot(dxy.x, dxy.y); + + // distance error + Point curvexy = curve.xy(s0 + y[0] * ss); +#if NORM_LEVEL == 1 + double disterr = dist(q.eval(t), curvexy); +#endif +#if NORM_LEVEL == 2 + double disterr = dist2(q.eval(t), curvexy); +#endif + disterr *= dydx[0]; + + // angle error + Point dir = curve.dir(s0 + y[0] * ss); + double angleerr = dir.x * dxy.y - dir.y * dxy.x; +#if NORM_LEVEL == 1 + angleerr = std::abs(angleerr); +#endif +#if NORM_LEVEL == 2 + angleerr = (angleerr * angleerr) / dydx[0]; +#endif + + dydx[1] = dist_factor * disterr + angle_factor * angleerr; + } +private: + const Thetas& curve; + double s0; + double ss; + const ArclenFunctor& af; + Quad q; +}; + +// measure how closely the quad fits the section of curve, using L1 norm +// of angle mismatch +double measureQuad(const Thetas& curve, double s0, double s1, const Quad& q) { + ArclenFunctor derivs(q); + double ss = (s1 - s0) / q.arclen(); + MeasureFunctor err(curve, s0, ss, derivs, q); + const int n = 10; + double dt = 1./n; + double t = 0; + double y[2] = { 0, 0 }; + for (int i = 0; i < n; i++) { + rk4<2>(y, t, dt, err); + t += dt; + } + return y[1]; +} + +struct Break { + Break(double s, Point xy, Point dir) : s(s), xy(xy), dir(dir) { } + double s; + Point xy; + Point dir; +}; + +struct Statelet { + void combine(const Statelet* prev, double score, Quad q); + const Statelet* prev; + double score; + Quad q; +}; + +void Statelet::combine(const Statelet* newprev, double newscore, Quad newq) { + prev = newprev; + double pmul = 2; + if (newq.isLine()) { + pmul = 1; + } else if (newprev != 0 && !newprev->q.isLine() + && lerp(0.5, newprev->q.p[1], newq.p[1]) == newq.p[0]) { + pmul = 1; + } + score = (newprev == 0 ? 0 : newprev->score) + penalty * pmul + newscore; + q = newq; +} + +struct State { + void combine(const State* prev, double score, Quad q); + vector<Statelet> sts; + bool init; +}; + +void State::combine(const State* prev, double score, Quad q) { + const Statelet* prevsl = prev->sts.empty() ? 0 : &prev->sts[0]; + if (prevsl == 0 && !prev->init) { + return; + } + Statelet sl; + sl.combine(prevsl, score, q); + if (sts.empty()) { + sts.push_back(sl); + } else { + if (sl.score < sts[0].score) { + sts[0] = sl; + } + } +} + +bool isInt(double x) { + return x == (int) x; +} + +bool okForHalf(const State* prev, Quad q) { + if (isInt(q.p[0].x) && isInt(q.p[0].y)) { + return true; + } + if (q.isLine()) { + return false; + } + const Statelet* prevsl = prev->sts.empty() ? 0 : &prev->sts[0]; + + if (prevsl == 0 || prevsl->q.isLine()) { + return false; + } + return lerp(0.5, prevsl->q.p[1], q.p[1]) == q.p[0]; +} + +void findBreaks(vector<Break>* breaks, const Thetas& curve) { + breaks->clear(); + double lastd; + int n = round(10 * curve.arclen); + for (int i = 0; i <= n; i++) { + double s = curve.arclen * i / n; + Point origp = curve.xy(s); +#if HALF_STEP + Point p(.5 * std::round(2 * origp.x), .5 * std::round(2 * origp.y)); +#else + Point p = round(origp); +#endif + double d = dist(p, origp); + if (i == 0 || !(p == (*breaks)[breaks->size() - 1].xy)) { + Break bk(s, p, curve.dir(s)); + breaks->push_back(bk); + lastd = d; + } else if (d < lastd) { + (*breaks)[breaks->size() - 1] = Break(s, p, curve.dir(s)); + lastd = d; + } + } +} + +bool intersect(Point* result, Point p0, Point dir0, Point p1, Point dir1) { + double det = dir0.x * dir1.y - dir0.y * dir1.x; + if (std::abs(det) < 1e-6) return false; + det = 1 / det; + double a = p0.y * dir0.x - p0.x * dir0.y; + double b = p1.y * dir1.x - p1.x * dir1.y; + result->x = (a * dir1.x - b * dir0.x) * det; + result->y = (a * dir1.y - b * dir0.y) * det; + return true; +} + +void tryQuad(const State* prev, State* st, const Thetas& curve, + const Break& bk0, const Break& bk1, const Quad& q) { + double score = measureQuad(curve, bk0.s, bk1.s, q); + st->combine(prev, score, q); +} + +void tryLineQuad(const State* prev, State* st, const Thetas& curve, + const Break& bk0, const Break& bk1) { + if (isInt(bk0.xy.x) && isInt(bk0.xy.y)) { + Quad line(bk0.xy, lerp(0.5, bk0.xy, bk1.xy), bk1.xy); + tryQuad(prev, st, curve, bk0, bk1, line); + } + Point pmid; + if (intersect(&pmid, bk0.xy, bk0.dir, bk1.xy, bk1.dir)) { + Quad q(bk0.xy, round(pmid), bk1.xy); + if (okForHalf(prev, q)) { + tryQuad(prev, st, curve, bk0, bk1, q); + } + } +} + +vector<Quad> optimize(const Thetas& curve) { + vector<Break> breaks; + findBreaks(&breaks, curve); + int n = breaks.size() - 1; + vector<State> states; + states.resize(n + 1); + states[0].init = true; + tryLineQuad(&states[0], &states[n], curve, breaks[0], breaks[n]); + if (states[n].sts[0].score <= 3 * penalty) { + goto done; + } + for (int i = 1; i < n; i++) { + tryLineQuad(&states[0], &states[i], curve, breaks[0], breaks[i]); + tryLineQuad(&states[i], &states[n], curve, breaks[i], breaks[n]); + } + if (states[n].sts[0].score <= 4 * penalty) { + goto done; + } + for (int i = 1; i <= n; i++) { + for (int j = i - 1; j >= 0; j--) { + tryLineQuad(&states[j], &states[i], curve, breaks[j], breaks[i]); + } + } +done: + vector<Quad> result; + for (const Statelet* sl = &states[n].sts[0]; sl != 0; sl = sl->prev) { + result.push_back(sl->q); + } + std::reverse(result.begin(), result.end()); + return result; +} + +void readBzs(vector<Quad>* result, std::istream& is) { + double x0, y0, x1, y1, x2, y2; + while (is >> x0 >> y0 >> x1 >> y1 >> x2 >> y2) { + result->push_back(Quad(Point(x0, y0), Point(x1, y1), Point(x2, y2))); + } + // Round the endpoints, they must be on integers + (*result)[0].p[0] = round((*result)[0].p[0]); + Quad* lastq = &(*result)[(*result).size()]; + lastq->p[2] = round(lastq->p[2]); +} + +int main(int argc, char** argv) { + if (argc != 3) { + std::cerr << "usage: quadopt in out\n"; + return 1; + } +#if 0 + Quad q(Point(100, 0), Point(0, 0), Point(0, 100)); + std::cout.precision(8); + std::cout << q.arclen() << "\n"; +#endif + vector<Quad> bzs; + std::ifstream is; + is.open(argv[1]); + readBzs(&bzs, is); + Thetas thetas; + thetas.init(bzs); +#if 0 + for (int i = 0; i < thetas.arclen; i++) { + Point xy = thetas.dir(i); + std::cout << xy.x << " " << xy.y << std::endl; + } +#endif + vector<Quad> optbzs = optimize(thetas); + std::ofstream os; + os.open(argv[2]); + for (size_t i = 0; i < optbzs.size(); i++) { + optbzs[i].print(os); + } + return 0; +} |