Fixed mismatch in fast and slow queries in overlap tests during

orientation determination which was causing assertion failures on some
inputs. Avoided ray casting tests where results will not change
decision of which side to fill. SVG butterfly is closer to rendering
correctly with these changes but is still not 100% correct.

BUG=none
TEST=samples/gpu2d/regression-tests/orientation-bug-2.html
TBR=apatrick

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

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

4 files changed, 168 insertions, 7 deletions

diff --git a/o3d/core/cross/gpu2d/path_processor.cc b/o3d/core/cross/gpu2d/path_processor.cc
index 39f9065..f99a3d3 100644
--- a/o3d/core/cross/gpu2d/path_processor.cc
+++ b/o3d/core/cross/gpu2d/path_processor.cc
@@ -89,7 +89,7 @@ T max4(const T& v1, const T& v2, const T& v3, const T& v4) {
 // BBox
 //
 
-// Extremely simple bounding box class for Segments.
+// Extremely simple bounding box class for Segments and Contours.
 class BBox {
  public:
   BBox()
@@ -126,6 +126,22 @@ class BBox {
                triangle->get_vertex(2)->y()));
   }
 
+  // Initializes this bounding box to the contents of the other.
+  void Setup(const BBox& bbox) {
+    min_x_ = bbox.min_x();
+    min_y_ = bbox.min_y();
+    max_x_ = bbox.max_x();
+    max_y_ = bbox.max_y();
+  }
+
+  // Extends this bounding box to surround itself and the other.
+  void Extend(const BBox& other) {
+    Setup(min2(min_x(), other.min_x()),
+          min2(min_y(), other.min_y()),
+          max2(max_x(), other.max_x()),
+          max2(max_y(), other.max_y()));
+  }
+
   float min_x() const { return min_x_; }
   float min_y() const { return min_y_; }
   float max_x() const { return max_x_; }
@@ -139,6 +155,17 @@ class BBox {
   DISALLOW_COPY_AND_ASSIGN(BBox);
 };
 
+// Suppport for logging BBoxes.
+std::ostream& operator<<(std::ostream& ostr,  // NOLINT
+                         const BBox& arg) {
+  ostr << "[BBox min_x=" << arg.min_x()
+       << " min_y=" << arg.min_y()
+       << " max_x=" << arg.max_x()
+       << " max_y=" << arg.max_y()
+       << "]";
+  return ostr;
+}
+
 //----------------------------------------------------------------------
 // Segment
 //
@@ -389,6 +416,19 @@ class Segment {
   DISALLOW_COPY_AND_ASSIGN(Segment);
 };
 
+// Suppport for logging Segments.
+std::ostream& operator<<(std::ostream& ostr,  // NOLINT
+                         const Segment& arg) {
+  ostr << "[Segment kind=";
+  if (arg.kind() == Segment::kLine) {
+    ostr << "line";
+  } else {
+    ostr << "cubic";
+  }
+  ostr << " bbox=" << arg.bbox() << "]";
+  return ostr;
+}
+
 //----------------------------------------------------------------------
 // Contour
 //
@@ -401,6 +441,7 @@ class Contour {
     first_->set_next(first_);
     first_->set_prev(first_);
     ccw_ = true;
+    bbox_dirty_ = false;
     fill_right_side_ = true;
   }
 
@@ -423,6 +464,7 @@ class Contour {
       segment->set_next(sentinel);
       sentinel->set_prev(segment);
     }
+    bbox_dirty_ = true;
   }
 
   // Subdivides the given segment at the given parametric value.
@@ -470,6 +512,24 @@ class Contour {
     ccw_ = ccw;
   }
 
+  // Returns the bounding box of this contour.
+  const BBox& bbox() const {
+    if (bbox_dirty_) {
+      bool first = true;
+      for (Segment* cur = begin(); cur != end(); cur = cur->next()) {
+        if (first) {
+          bbox_.Setup(cur->bbox());
+        } else {
+          bbox_.Extend(cur->bbox());
+        }
+        first = false;
+      }
+
+      bbox_dirty_ = false;
+    }
+    return bbox_;
+  }
+
   // Returns whether the right side of this contour is filled.
   bool fill_right_side() const { return fill_right_side_; }
 
@@ -490,6 +550,12 @@ class Contour {
   // Whether this contour is oriented counterclockwise.
   bool ccw_;
 
+  // This contour's bounding box.
+  mutable BBox bbox_;
+
+  // Whether this contour's bounding box is dirty.
+  mutable bool bbox_dirty_;
+
   // Whether we should fill the right (or left) side of this contour.
   bool fill_right_side_;
 
@@ -734,7 +800,7 @@ std::vector<Segment*> PathProcessor::AllSegmentsOverlappingY(float y) {
     Contour* cur = *iter;
     for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
       const BBox& bbox = seg->bbox();
-      if (bbox.min_y() <= y && y <= bbox.max_y()) {
+      if (bbox.min_y() < y && y < bbox.max_y()) {
         res.push_back(seg);
       }
     }
@@ -796,9 +862,17 @@ void PathProcessor::DetermineSidesToFill() {
          iter++) {
       const IntervalType& interval = *iter;
       Segment* query_seg = interval.data();
-      // Ignore segments coming from the same contour
+      // Ignore segments coming from the same contour.
       if (query_seg->contour() != cur) {
-        num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0));
+        // 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));
+        }
       }
     }
 #endif  // !defined(O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION)
@@ -807,14 +881,33 @@ void PathProcessor::DetermineSidesToFill() {
     // 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
+      // Ignore segments coming from the same contour.
       if (query_seg->contour() != cur) {
-        num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0));
+        // 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));
+        }
       }
     }
 #endif  // O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION
diff --git a/o3d/samples/gpu2d/regression-tests/orientation-bug-2.html b/o3d/samples/gpu2d/regression-tests/orientation-bug-2.html
new file mode 100644
index 0000000..4838178
--- /dev/null
+++ b/o3d/samples/gpu2d/regression-tests/orientation-bug-2.html
@@ -0,0 +1,51 @@
+<!--
+Copyright 2010, Google Inc.
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    * Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above
+copyright notice, this list of conditions and the following disclaimer
+in the documentation and/or other materials provided with the
+distribution.
+    * Neither the name of Google Inc. nor the names of its
+contributors may be used to endorse or promote products derived from
+this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+-->
+
+<html>
+<head>
+<title>
+Orientation Bug 2 (Butterfly Spots)
+</title>
+<!-- Include sample javascript library functions-->
+<script type="text/javascript" src="../../o3djs/base.js"></script>
+<!-- Include SVG sample and dependencies -->
+<script type="text/javascript" src="../../third_party/xmljs/tinyxmlsax.js"></script>
+<script type="text/javascript" src="../svgloader.js"></script>
+<script type="text/javascript" src="../svgsample.js"></script>
+</head>
+<body onload="init('orientation-bug-2.svg');" onunload="unload();">
+<h1>Orientation Bug 2 (Butterfly Spots)</h1>
+<br/>
+<!-- Start of O3D plugin -->
+<div id="o3d" style="width: 1024px; height: 768px;"></div>
+<!-- End of O3D plugin -->
+</body>
+</html>
diff --git a/o3d/samples/gpu2d/regression-tests/orientation-bug-2.svg b/o3d/samples/gpu2d/regression-tests/orientation-bug-2.svg
new file mode 100644
index 0000000..8611b43
--- /dev/null
+++ b/o3d/samples/gpu2d/regression-tests/orientation-bug-2.svg
@@ -0,0 +1,17 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+
+<svg
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   version="1.1"
+   width="100%"
+   height="100%"
+   id="svg3331">
+  <defs
+     id="defs3343" />
+  <path
+     d="M 1127.0498,42.514488 C 1101.9998,37.504488 1103.0498,23.014488 1130.0498,17.014488 1134.4598,16.054488 1142.0498,45.514488 1127.0498,42.514488 z M 1142.0498,42.514488 C 1149.5498,41.014488 1161.5498,44.014488 1163.0498,54.514488 1164.5498,65.014488 1152.5498,71.014488 1145.0498,65.014488 1137.5498,59.014488 1134.5498,44.014488 1142.0498,42.514488 z M 1161.5498,17.014488 C 1161.5498,17.014488 1173.5498,17.014488 1170.5498,21.514488 1167.5498,26.014488 1158.5498,26.014488 1158.5498,26.014488 L 1161.5498,17.014488 z M 1179.5498,44.014488 C 1179.5498,44.014488 1191.5498,44.014488 1188.5498,48.514488 1185.5498,53.014488 1176.5498,53.014488 1176.5498,53.014488 L 1179.5498,44.014488 z M 1067.0498,23.014488 C 1074.5498,24.514488 1097.0498,15.514488 1086.5498,12.514488 1076.0498,9.5144883 1059.1298,21.454488 1067.0498,23.014488 z M 69.54982,40.024488 C 94.59982,35.014488 93.54982,20.524488 66.54982,14.524488 62.16982,13.534488 54.54982,43.024488 69.54982,40.024488 z M 54.54982,40.024488 C 47.04982,38.524488 35.04982,41.524488 33.54982,52.024488 32.04982,62.524488 44.04982,68.524488 51.54982,62.524488 59.04982,56.524488 62.04982,41.524488 54.54982,40.024488 z M 35.04982,14.524488 C 35.04982,14.524488 23.04982,14.524488 26.04982,19.024488 29.04982,23.524488 38.04982,23.524488 38.04982,23.524488 L 35.04982,14.524488 z M 17.04982,41.524488 C 17.04982,41.524488 5.0498197,41.524488 8.0498197,46.024488 11.04982,50.524488 20.04982,50.524488 20.04982,50.524488 L 17.04982,41.524488 z M 129.54982,20.524488 C 122.04982,22.024488 99.54982,13.024488 110.04982,10.024488 120.54982,7.0244883 137.46982,18.934488 129.54982,20.524488 z"
+     id="path3339"
+     style="fill:#fff6e3;stroke:none" />
+</svg>
diff --git a/o3d/samples/gpu2d/svg_butterfly.html b/o3d/samples/gpu2d/svg_butterfly.html
index 618b299..b473e38 100644
--- a/o3d/samples/gpu2d/svg_butterfly.html
+++ b/o3d/samples/gpu2d/svg_butterfly.html
@@ -45,7 +45,7 @@ SVG Butterfly
 <h1>SVG Butterfly</h1>
 <br/>
 <!-- Start of O3D plugin -->
-<div id="o3d" style="width: 800px; height: 600px;"></div>
+<div id="o3d" style="width: 1280px; height: 1024px;"></div>
 <!-- End of O3D plugin -->
 
 (There are currently still rendering errors in the above.)