From f32ac186addb85c49b9bc41c4e84d4ec700a03a5 Mon Sep 17 00:00:00 2001 From: "kbr@google.com" Date: Tue, 6 Jul 2010 16:55:25 +0000 Subject: 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 --- o3d/core/cross/gpu2d/interval_tree.h | 24 +++++----- o3d/core/cross/gpu2d/path_processor.cc | 2 +- .../gpu2d/regression-tests/orientation-bug-3.html | 51 ++++++++++++++++++++++ .../gpu2d/regression-tests/orientation-bug-3.svg | 17 ++++++++ 4 files changed, 82 insertions(+), 12 deletions(-) create mode 100644 o3d/samples/gpu2d/regression-tests/orientation-bug-3.html create mode 100644 o3d/samples/gpu2d/regression-tests/orientation-bug-3.svg (limited to 'o3d') 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 > { // 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 > { } // 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 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 @@ + + + + + +Orientation Bug 3 (Butterfly's Black Region) + + + + + + + + + +

Orientation Bug 3 (Butterfly's Black Region)

+
+ +
+ + + 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 @@ + + + + + + + -- cgit v1.1