Made code which determines which side of contours to fill more robust

using new outgoing "ambiguous" parameter added to Skia XRay queries.
Rolled forward Skia dependency to latest revision. With these changes
the SVG butterfly renders correctly in O3D. Boosted polygon offsets
again to avoid pixel dropouts.

Also tested O3D canvas demos to verify no breakage with Skia
roll-forward.

BUG=none
TEST=none


Review URL: http://codereview.chromium.org/2813049

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@51791 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 83 insertions, 59 deletions

diff --git a/o3d/DEPS b/o3d/DEPS
index e4054c8..76db5bc 100644
--- a/o3d/DEPS
+++ b/o3d/DEPS
@@ -6,7 +6,7 @@ vars = {
   "chromium_rev": "37758",
   "chromium_breakpad_rev": "47985",
   "o3d_code_rev": "207",
-  "skia_rev": "488",
+  "skia_rev": "586",
   "gyp_rev": "820",
   "gtest_rev": "359",
   "gflags_rev": "30",
diff --git a/o3d/core/cross/gpu2d/path_processor.cc b/o3d/core/cross/gpu2d/path_processor.cc
index d49fef5..756ae48 100644
--- a/o3d/core/cross/gpu2d/path_processor.cc
+++ b/o3d/core/cross/gpu2d/path_processor.cc
@@ -292,13 +292,16 @@ class Segment {
   }
 
   // Computes the number of times a query line starting at the given
-  // point and extending to x=+infinity crosses this segment.
-  int NumCrossingsForXRay(SkPoint pt) const {
+  // point and extending to x=+infinity crosses this segment. Outgoing
+  // "ambiguous" argument indicates whether the query intersected an
+  // endpoint or tangent point of the segment, indicating that another
+  // query point is preferred.
+  int NumCrossingsForXRay(SkPoint pt, bool* ambiguous) const {
     if (kind_ == kCubic) {
       // Should consider caching the monotonic cubics.
-      return SkNumXRayCrossingsForCubic(pt, points_);
+      return SkNumXRayCrossingsForCubic(pt, points_, ambiguous);
     } else {
-      return SkXRayCrossesLine(pt, points_) ? 1 : 0;
+      return SkXRayCrossesLine(pt, points_, ambiguous) ? 1 : 0;
     }
   }
 
@@ -847,70 +850,93 @@ void PathProcessor::DetermineSidesToFill() {
        iter != contours_.end();
        iter++) {
     Contour* cur = *iter;
-    Segment* seg = cur->begin();
 
+    bool ambiguous = true;
     int num_crossings = 0;
 
-    // We use a zero-sized vertical interval for the query
-    std::vector<IntervalType> overlaps =
-        tree.AllOverlaps(IntervalType(SkScalarToFloat(seg->get_point(0).fY),
-                                      SkScalarToFloat(seg->get_point(0).fY),
-                                      NULL));
+    // For each contour, attempt to find a point on the contour which,
+    // when we cast an XRay, does not intersect the other contours at
+    // an ambiguous point (the junction between two curves or at a
+    // tangent point). Ambiguous points make the determination of
+    // whether this contour is contained within another fragile. Note
+    // that this loop is only an approximation to the selection of a
+    // good casting point. We could as well evaluate a segment to
+    // determine a point upon it.
+    for (Segment* seg = cur->begin();
+         ambiguous && seg != cur->end();
+         seg = seg->next()) {
+      num_crossings = 0;
+      // We use a zero-sized vertical interval for the query.
+      std::vector<IntervalType> overlaps =
+          tree.AllOverlaps(IntervalType(SkScalarToFloat(seg->get_point(0).fY),
+                                        SkScalarToFloat(seg->get_point(0).fY),
+                                        NULL));
 #if !defined(O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION)
-    for (std::vector<IntervalType>::iterator iter = overlaps.begin();
-         iter != overlaps.end();
-         iter++) {
-      const IntervalType& interval = *iter;
-      Segment* query_seg = interval.data();
-      // Ignore segments coming from the same contour.
-      if (query_seg->contour() != cur) {
-        // Only perform queries that can affect the computation.
-        // TODO(kbr): make the XRay queries more robust; handle
-        // intersections with the endpoints of segments by choosing
-        // another query point.
-        const BBox& bbox = query_seg->contour()->bbox();
-        if (seg->get_point(0).fX >= bbox.min_x() &&
-            seg->get_point(0).fX <= bbox.max_x()) {
-          num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0));
+      for (std::vector<IntervalType>::iterator iter = overlaps.begin();
+           iter != overlaps.end();
+           iter++) {
+        const IntervalType& interval = *iter;
+        Segment* query_seg = interval.data();
+        // Ignore segments coming from the same contour.
+        if (query_seg->contour() != cur) {
+          // Only perform queries that can affect the computation.
+          const BBox& bbox = query_seg->contour()->bbox();
+          if (seg->get_point(0).fX >= bbox.min_x() &&
+              seg->get_point(0).fX <= bbox.max_x()) {
+            num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0),
+                                                            &ambiguous);
+            if (ambiguous) {
+              DLOG(INFO) << "Ambiguous intersection query at point ("
+                         << seg->get_point(0).fX << ", "
+                         << seg->get_point(0).fY << ")";
+              DLOG(INFO) << "Query segment: " << *query_seg;
+              break;  // Abort iteration over overlaps.
+            }
+          }
         }
       }
-    }
 #endif  // !defined(O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION)
 
 #ifdef O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION
-    // For debugging
-    std::vector<Segment*> slow_overlaps =
-        AllSegmentsOverlappingY(seg->get_point(0).fY);
-    if (overlaps.size() != slow_overlaps.size()) {
-      DLOG(ERROR) << "for query point " << seg->get_point(0).fY << ":";
-      DLOG(ERROR) << " overlaps:";
-      for (size_t i = 0; i < overlaps.size(); i++) {
-        DLOG(ERROR) << "  " << (i+1) << ": " << *overlaps[i].data();
-      }
-      DLOG(ERROR) << " slow_overlaps:";
-      for (size_t i = 0; i < slow_overlaps.size(); i++) {
-        DLOG(ERROR) << "  " << (i+1) << ": " << *slow_overlaps[i];
+      // For debugging
+      std::vector<Segment*> slow_overlaps =
+          AllSegmentsOverlappingY(seg->get_point(0).fY);
+      if (overlaps.size() != slow_overlaps.size()) {
+        DLOG(ERROR) << "for query point " << seg->get_point(0).fY << ":";
+        DLOG(ERROR) << " overlaps:";
+        for (size_t i = 0; i < overlaps.size(); i++) {
+          DLOG(ERROR) << "  " << (i+1) << ": " << *overlaps[i].data();
+        }
+        DLOG(ERROR) << " slow_overlaps:";
+        for (size_t i = 0; i < slow_overlaps.size(); i++) {
+          DLOG(ERROR) << "  " << (i+1) << ": " << *slow_overlaps[i];
+        }
       }
-    }
-    DCHECK(overlaps.size() == slow_overlaps.size());
-    for (std::vector<Segment*>::iterator iter = slow_overlaps.begin();
-         iter != slow_overlaps.end();
-         iter++) {
-      Segment* query_seg = *iter;
-      // Ignore segments coming from the same contour.
-      if (query_seg->contour() != cur) {
-        // Only perform queries that can affect the computation.
-        // TODO(kbr): make the XRay queries more robust; handle
-        // intersections with the endpoints of segments by choosing
-        // another query point.
-        const BBox& bbox = query_seg->contour()->bbox();
-        if (seg->get_point(0).fX >= bbox.min_x() &&
-            seg->get_point(0).fX <= bbox.max_x()) {
-          num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0));
+      DCHECK(overlaps.size() == slow_overlaps.size());
+      for (std::vector<Segment*>::iterator iter = slow_overlaps.begin();
+           iter != slow_overlaps.end();
+           iter++) {
+        Segment* query_seg = *iter;
+        // Ignore segments coming from the same contour.
+        if (query_seg->contour() != cur) {
+          // Only perform queries that can affect the computation.
+          const BBox& bbox = query_seg->contour()->bbox();
+          if (seg->get_point(0).fX >= bbox.min_x() &&
+              seg->get_point(0).fX <= bbox.max_x()) {
+            num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0),
+                                                            &ambiguous);
+            if (ambiguous) {
+              DLOG(INFO) << "Ambiguous intersection query at point ("
+                         << seg->get_point(0).fX << ", "
+                         << seg->get_point(0).fY << ")";
+              DLOG(INFO) << "Query segment: " << *query_seg;
+              break;  // Abort iteration over overlaps.
+            }
+          }
         }
       }
-    }
 #endif  // O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION
+    }  // for (Segment* seg = cur->begin(); ...
 
     if (cur->ccw()) {
       if (num_crossings & 1) {
diff --git a/o3d/samples/gpu2d/svg_butterfly.html b/o3d/samples/gpu2d/svg_butterfly.html
index b473e38..0cd4182 100644
--- a/o3d/samples/gpu2d/svg_butterfly.html
+++ b/o3d/samples/gpu2d/svg_butterfly.html
@@ -48,7 +48,5 @@ SVG Butterfly
 <div id="o3d" style="width: 1280px; height: 1024px;"></div>
 <!-- End of O3D plugin -->
 
-(There are currently still rendering errors in the above.)
-
 </body>
 </html>
diff --git a/o3d/samples/gpu2d/svgloader.js b/o3d/samples/gpu2d/svgloader.js
index b01352c..46e4506 100644
--- a/o3d/samples/gpu2d/svgloader.js
+++ b/o3d/samples/gpu2d/svgloader.js
@@ -335,7 +335,7 @@ SVGLoader.prototype.parsePath_ = function(pathData,
   if (this.fill_) {
     path.setFill(this.fill_);
   }
-  path.setPolygonOffset(-2 * this.polygonOffset_, -3 * this.polygonOffset_);
+  path.setPolygonOffset(-3 * this.polygonOffset_, -4 * this.polygonOffset_);
   ++this.polygonOffset_;
   this.currentTransform_().addShape(path.shape);
 };