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

2 files changed, 14 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);
       }
     }