Split glyph contours in up/down segments for skylines (issue 569700043 by address@hidden)

[hanwenn]

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++)