Changed definition of IntervalTree to contain closed, rather than

open, intervals, and changed back PathProcessor's
AllSegmentsOverlappingY debug routine to report closed intervals. This
fixes more rendering issues with the SVG butterfly.

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

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

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

4 files changed, 82 insertions, 12 deletions

diff --git a/o3d/core/cross/gpu2d/interval_tree.h b/o3d/core/cross/gpu2d/interval_tree.h
index 71a7ca1..ec4bb2a 100644
--- a/o3d/core/cross/gpu2d/interval_tree.h
+++ b/o3d/core/cross/gpu2d/interval_tree.h
@@ -42,13 +42,13 @@
 namespace o3d {
 namespace gpu2d {
 
-// Interval class which can hold an arbitrary type as its endpoints
-// and a piece of user data. An important characteristic for the
-// algorithms we use is that if two intervals have identical endpoints
-// but different user data, they are not considered to be equal. This
-// situation can arise when representing the vertical extents of
-// bounding boxes of overlapping triangles, where the pointer to the
-// triangle is the user data of the interval.
+// Class representing a closed interval which can hold an arbitrary
+// type as its endpoints and a piece of user data. An important
+// characteristic for the algorithms we use is that if two intervals
+// have identical endpoints but different user data, they are not
+// considered to be equal. This situation can arise when representing
+// the vertical extents of bounding boxes of overlapping triangles,
+// where the pointer to the triangle is the user data of the interval.
 //
 // The following constructors and operators must be implemented on
 // type T:
@@ -107,8 +107,6 @@ class Interval {
       return false;
     if (high < this->low())
       return false;
-    if (this->high() == low || this->low() == high)
-      return false;
     return true;
   }
 
@@ -232,7 +230,9 @@ class IntervalTree : public RedBlackTree<Interval<T, UserData> > {
     // See whether we need to traverse the left subtree.
     IntervalNode* left = node->left();
     if (left != NULL &&
-        interval.low() < left->data().max_high()) {
+        // This is equivalent to:
+        // interval.low() <= left->data().max_high()
+        !(left->data().max_high() < interval.low())) {
       SearchForOverlapsFrom(left, interval, res);
     }
 
@@ -242,7 +242,9 @@ class IntervalTree : public RedBlackTree<Interval<T, UserData> > {
     }
 
     // See whether we need to traverse the right subtree.
-    if (node->data().low() < interval.high()) {
+    // This is equivalent to:
+    // node->data().low() <= interval.high()
+    if (!(interval.high() < node->data().low())) {
       SearchForOverlapsFrom(node->right(), interval, res);
     }
   }
diff --git a/o3d/core/cross/gpu2d/path_processor.cc b/o3d/core/cross/gpu2d/path_processor.cc
index f99a3d3..d49fef5 100644
--- a/o3d/core/cross/gpu2d/path_processor.cc
+++ b/o3d/core/cross/gpu2d/path_processor.cc
@@ -800,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);
       }
     }
diff --git a/o3d/samples/gpu2d/regression-tests/orientation-bug-3.html b/o3d/samples/gpu2d/regression-tests/orientation-bug-3.html
new file mode 100644
index 0000000..d8e1e7b
--- /dev/null
+++ b/o3d/samples/gpu2d/regression-tests/orientation-bug-3.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 3 (Butterfly's Black Region)
+</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-3.svg');" onunload="unload();">
+<h1>Orientation Bug 3 (Butterfly's Black Region)</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-3.svg b/o3d/samples/gpu2d/regression-tests/orientation-bug-3.svg
new file mode 100644
index 0000000..fec711c
--- /dev/null
+++ b/o3d/samples/gpu2d/regression-tests/orientation-bug-3.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="svg3670">
+  <defs
+     id="defs3682" />
+  <path
+     d="M 610.86,418.86 C 586.86,399.36 617.88,397.8 617.61,397.11 574.86,290.61 505.92,243.6 500.61,241.11 484.23,233.43 476.31,234.15 479.19,230.28 482.07,226.41 501.03,238.53 503.61,240.36 579.36,294.36 620.61,396.36 620.61,396.36 620.61,396.36 625.86,399.36 626.61,397.11 656.61,308.61 716.61,262.11 736.86,243.36 757.11,224.61 767.76,222.78 739.86,244.11 653.61,310.11 628.89,396.03 630.36,396.36 664.86,403.86 631.86,420.36 633.36,418.86 642.42,409.8 642.36,436.86 642.36,436.86 642.36,436.86 693.36,331.86 892.86,198.36 905.13,190.14 1335.36,-44.64 1185.36,241.86 1177.59,256.71 1125.36,316.86 1125.36,316.86 1125.36,316.86 1129.86,342.36 1111.86,363.36 1108.77,366.96 1101.36,402.36 1083.36,421.86 1078.29,427.38 1083.27,417.12 1083.36,421.86 1084.86,511.86 1011.15,509.88 1015.86,510.36 1044.36,513.36 1048.41,550.35 1048.86,550.86 1065.36,570.36 1059.36,574.86 1065.36,583.86 1097.73,632.43 1063.59,629.52 1068.36,637.86 1080.36,658.86 1065.84,667.53 1069.86,673.86 1080.36,690.36 1062.09,700.86 1062.36,705.36 1063.86,730.86 1046.88,721.56 1047.36,732.36 1048.86,765.36 1036.86,751.86 1029.36,763.86 1006.86,799.86 998.22,786.51 996.36,790.86 987.36,811.86 975.27,806.82 970.86,811.86 960.36,823.86 949.86,823.86 945.36,828.36 924.36,849.36 912.45,834.51 909.36,835.86 861.36,856.86 838.86,839.85 831.36,840.36 808.86,841.86 812.31,838.38 805.86,832.86 711.36,751.86 655.86,634.86 645.36,619.86 641.07,613.71 631.89,578.73 634.86,586.86 640.86,603.36 637.86,750.36 621.36,750.36 574.44968,710.77679 648.61944,539.97251 603.24,619.86 586.86,639.36 536.37,751.86 440.64,832.86 434.13,838.38 437.61,841.86 414.81,840.36 407.25,839.85 384.42,856.86 335.82,835.86 332.7,834.51 320.61,849.36 299.34,828.36 294.78,823.86 284.16,823.86 273.51,811.86 269.04,806.82 256.8,811.86 247.68,790.86 245.79,786.51 237.03,799.86 214.26,763.86 206.64,751.86 194.49,765.36 196.02,732.36 196.53,721.56 179.31,730.86 180.81,705.36 181.08,700.86 162.6,690.36 173.22,673.86 177.3,667.53 162.6,658.86 174.75,637.86 179.58,629.52 144.99,632.43 177.78,583.86 183.87,574.86 177.78,570.36 194.49,550.86 194.94,550.35 199.05,513.36 227.94,510.36 232.71,509.88 158.04,511.86 159.54,421.86 159.63,417.12 164.7,427.38 159.54,421.86 141.33,402.36 133.8,366.96 130.68,363.36 112.44,342.36 117,316.86 117,316.86 117,316.86 64.11,256.71 56.22,241.86 -95.7,-44.64 340.08,190.14 352.53,198.36 554.61,331.86 603.87,436.86 603.87,436.86 603.87,436.86 604.95,429.21 606.87,424.86 608.79,420.54 611.55,419.43 610.86,418.86 z M 253.77,228.36 C 317.58,243.36 290.22,265.86 282.63,264.36 223.59,252.72 240.45,225.24 253.77,228.36 z M 230.97,240.36 C 240.66,243.09 214.26,228.36 192.99,226.86 185.25,226.32 150.78,204.6 127.65,238.86 124.59,243.36 110.25,239.52 88.14,261.36 83.58,265.86 110.55,239.61 135.24,249.36 142.83,252.36 157.23,271.17 192.99,235.86 197.55,231.36 220.32,237.36 230.97,240.36 z"
+     id="path3676"
+     style="fill:#000000;stroke:none" />
+</svg>