Reviewers: , Message: goes on top of https://codereview.appspot.com/561730043/
Description: Split glyph contours in up/down segments for skylines This reduces the amount of skyline input coming from glyph outlines by 2x. benchmark for arguments: input/regression/mozart-hrn-3 raw data: {'ff2061b518': [2.72, 2.69, 2.71], 'e8212e15e2': [2.7, 2.68, 2.69]} Version ff2061b518: Create skylines directly from glyph outlines. e8212e15e2 - Split glyph contours in up/down segments for skylines med diff -0.020000 med diff -0.738007 % (e8212e15e2 is faster) benchmark for arguments: -I carver MSDM raw data: {'ff2061b518': [51.83, 51.99, 52.05], 'e8212e15e2': [51.27, 51.2, 51.48]} ff2061b518: Create skylines directly from glyph outlines. e8212e15e2 - Split glyph contours in up/down segments for skylines med diff -0.720000 med diff -1.384882 % (e8212e15e2 is faster) Please review this at https://codereview.appspot.com/569700043/ Affected files (+60, -14 lines): M lily/freetype.cc M lily/include/lazy-skyline-pair.hh M lily/stencil-integral.cc Index: lily/freetype.cc diff --git a/lily/freetype.cc b/lily/freetype.cc index 920078763676e42a9bce2af3fb72735af49bf8b0..4cb69039b41adc5c66eaf947b9aff1964c3a077d 100644 --- a/lily/freetype.cc +++ b/lily/freetype.cc @@ -18,6 +18,7 @@ */ #include "freetype.hh" +#include "bezier.hh" #include "lazy-skyline-pair.hh" #include "stencil-integral.hh" #include "transform.hh" @@ -25,6 +26,10 @@ #include FT_OUTLINE_H #include FT_BBOX_H +#include FT_DRIVER_H +#include FT_TRUETYPE_TAGS_H +#include FT_TRUETYPE_TABLES_H +#include FT_FONT_FORMATS_H FT_Library freetype2_library; @@ -113,6 +118,13 @@ ly_FT_add_outline_to_skyline (Lazy_skyline_pair *lazy, return; } + // TrueType style fonts have a 'glyf' table. If they, don't we'll + // assume they are CFF/Type1, and use CCW contours. + FT_ULong unused_table_len; + Orientation orientation + = FT_Load_Sfnt_Table (face, TTAG_glyf, 0, NULL, &unused_table_len) ? CCW + : CW; + FT_Outline *outline = &(face->glyph->outline); Offset lastpos; Offset firstpos; @@ -131,22 +143,37 @@ ly_FT_add_outline_to_skyline (Lazy_skyline_pair *lazy, // it is a line Offset p (static_cast<Real> (outline->points[j].x), static_cast<Real> (outline->points[j].y)); - lazy->add_segment (transform, lastpos, p); + lazy->add_contour_segment (transform, orientation, lastpos, p); lastpos = p; j++; } else if (outline->tags[j] & 2) { - // it is a third order bezier - Offset ps[4] = {lastpos}; + // it is a third order bezier. + Bezier curve; + curve.control_[0] = {lastpos}; for (int i = 0; i < 3; i++) { - ps[i + 1] = Offset (static_cast<Real> (outline->points[j + i].x), - static_cast<Real> (outline->points[j + i].y)); + curve.control_[i + 1] + = Offset (static_cast<Real> (outline->points[j + i].x), + static_cast<Real> (outline->points[j + i].y)); } - lastpos = ps[3]; - make_draw_bezier_boxes (lazy, transform, 0.0, ps); + lastpos = curve.control_[3]; j += 3; + + Offset start = transform (curve.control_[0]); + Offset end = transform (curve.control_[3]); + size_t quantization + = std::max (2, int ((end - start).length () / 0.2)); + + Offset last; + for (vsize i = 0; i <= quantization; i++) + { + Offset pt = curve.curve_point ( + static_cast<Real> (i) / static_cast<Real> (quantization)); + lazy->add_contour_segment (transform, orientation, last, pt); + last = pt; + } } else { @@ -154,7 +181,7 @@ ly_FT_add_outline_to_skyline (Lazy_skyline_pair *lazy, // we don't have code to handle these. Substitute a line segment instead. Offset p (static_cast<Real> (outline->points[j + 1].x), static_cast<Real> (outline->points[j + 1].y)); - lazy->add_segment (transform, lastpos, p); + lazy->add_contour_segment (transform, orientation, lastpos, p); lastpos = p; j += 2; } Index: lily/include/lazy-skyline-pair.hh diff --git a/lily/include/lazy-skyline-pair.hh b/lily/include/lazy-skyline-pair.hh index 726aaa14a53714e797d2888c8516b18ccde61cd1..18a69e1861a22157271149ec1e12b427fa06a39f 100644 --- a/lily/include/lazy-skyline-pair.hh +++ b/lily/include/lazy-skyline-pair.hh @@ -25,10 +25,16 @@ #include "skyline-pair.hh" #include "transform.hh" +enum Orientation { + CCW = DOWN, + CW = UP, +}; + class Lazy_skyline_pair { Axis a_; std::vector<Drul_array<Offset>> todo_; + Drul_array<std::vector<Drul_array<Offset>>> per_dir_todo_; Skyline_pair skylines_; public: @@ -38,6 +44,17 @@ public: { todo_.push_back (Drul_array<Offset> (tr (p1), tr (p2))); } + /* add segment, assuming it is a contour in some direction. */ + void add_contour_segment (Transform const &tr, Orientation orientation, + Offset p1, Offset p2) + { + Drul_array<Offset> seg(tr (p1), tr (p2)); + if ((seg[LEFT][a_] > seg[RIGHT][a_]) == (orientation==CCW)) { + per_dir_todo_[(a_ == X_AXIS) ? UP : LEFT].push_back (seg); + } else { + per_dir_todo_[(a_ == X_AXIS) ? DOWN : RIGHT].push_back (seg); + } + } void add_segment (Transform const &tr, Offset p1, Offset p2, Real thickness) { Real radius = 0.0; @@ -78,12 +95,15 @@ public: void merge () { - if (todo_.empty ()) - return; + for (DOWN_and_UP(d)) { + if (todo_.empty () && per_dir_todo_[d].empty()) + continue; - Skyline_pair p (todo_, a_); - skylines_.merge (p); - todo_.clear (); + per_dir_todo_[d].insert(per_dir_todo_[d].end(), todo_.begin(), todo_.end()); + skylines_[d].merge(Skyline(per_dir_todo_[d], a_, d)); + per_dir_todo_[d].clear (); + } + todo_.clear(); } Skyline_pair to_pair () Index: lily/stencil-integral.cc diff --git a/lily/stencil-integral.cc b/lily/stencil-integral.cc index 1ae194737327f86308f8042ac27d39f8a7a39a46..7ee7e69e0079619eccea3f89890083f33f4615a4 100644 --- a/lily/stencil-integral.cc +++ b/lily/stencil-integral.cc @@ -338,7 +338,6 @@ make_draw_bezier_boxes (Lazy_skyline_pair *skyline, Transform const &transform, Real pt = static_cast<Real> (i) / quantization; points.push_back (curve.curve_point (pt)); } - points.push_back (curve.control_[3]); for (vsize i = 0; i < points.size () - 1; i++)