<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[186976] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/186976">186976</a></dd>
<dt>Author</dt> <dd>timothy_horton@apple.com</dd>
<dt>Date</dt> <dd>2015-07-17 16:55:59 -0700 (Fri, 17 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Improve rect shrink-wrapping algorithm
https://bugs.webkit.org/show_bug.cgi?id=147037
<rdar://problem/21643094>
Reviewed by Simon Fraser.
* platform/graphics/FloatPoint.h:
(WebCore::areEssentiallyEqual):
Added; implementation is the same as FloatSize's.
* platform/graphics/PathUtilities.cpp:
(WebCore::FloatPointGraph::FloatPointGraph):
(WebCore::FloatPointGraph::~FloatPointGraph):
(WebCore::FloatPointGraph::Node::Node):
(WebCore::FloatPointGraph::Node::nextPoints):
(WebCore::FloatPointGraph::Node::addNextPoint):
(WebCore::FloatPointGraph::Node::isVisited):
(WebCore::FloatPointGraph::Node::visit):
(WebCore::FloatPointGraph::Node::reset):
(WebCore::FloatPointGraph::reset):
(WebCore::FloatPointGraph::findOrCreateNode):
(WebCore::findLineSegmentIntersection):
(WebCore::addIntersectionPoints):
(WebCore::walkGraphAndExtractPolygon):
(WebCore::findUnvisitedPolygonStartPoint):
(WebCore::unitePolygons):
(WebCore::edgesForRect):
(WebCore::PathUtilities::pathWithShrinkWrappedRects):
(WebCore::addShrinkWrapRightCorner): Deleted.
(WebCore::addShrinkWrapLeftCorner): Deleted.
(WebCore::addShrinkWrappedPathForRects): Deleted.
(WebCore::rectsIntersectOrTouch): Deleted.
(WebCore::findSetContainingRect): Deleted.
Add a new implementation of shrink-wrap, which is significantly more
generic than the old one, which assumed a top-down progression of rects.
This version uses polygon intersection to find the path around the
set of rects, and then follows said path and adds appropriately-sized
arcs for the corners.
The polygon intersection algorithm first finds all the intersection points
between all of the rects, then builds a graph of edges outward from one point.
It then traverses the graph, choosing at each point the next edge which
has not been visited and has the greatest interior angle, recording the polygon as it goes.
If at the end of the traversal we have not returned to the initial node,
we give up on shrink-wrapping and just use a bounding box around the rects.
If any of the original rects have not been visited at all, we repeat the traversal
starting with that rect, making an additional polygon (since we removed completely contained
rects before we started, having not visited the rect at all means that it's not connected
to the others).
Once we have a set of united polygons, we follow each one, determining the ideal (always
equal in width and height, never more than half the length of either edge, so that we always
have a smooth curve) arc radius and projecting it onto the edge, and then
adding an arc between the end of the previous path and beginning of the next.
Because the shrink-wrap algorithm is fairly expensive, if there are more than 20 rects,
we fall back to a bounding box. Given the current use cases, this is more than enough
rects, but can certainly be adjusted in the future if needed.
* testing/Internals.cpp:
(WebCore::Internals::pathWithShrinkWrappedRects):
* testing/Internals.h:
* testing/Internals.idl:
Add a radius parameter.
* fast/shrink-wrap/rect-shrink-wrap-expected.png:
* fast/shrink-wrap/rect-shrink-wrap.html:
Add a radius parameter to testRects, defaulting to 8.
Add an offset parameter to testRects, making it easier to slide
the rect sets around.
Add some more test cases.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkLayoutTestsfastshrinkwraprectshrinkwrapexpectedpng">trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap-expected.png</a></li>
<li><a href="#trunkLayoutTestsfastshrinkwraprectshrinkwraphtml">trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreplatformgraphicsFloatPointh">trunk/Source/WebCore/platform/graphics/FloatPoint.h</a></li>
<li><a href="#trunkSourceWebCoreplatformgraphicsPathUtilitiescpp">trunk/Source/WebCore/platform/graphics/PathUtilities.cpp</a></li>
<li><a href="#trunkSourceWebCoretestingInternalscpp">trunk/Source/WebCore/testing/Internals.cpp</a></li>
<li><a href="#trunkSourceWebCoretestingInternalsh">trunk/Source/WebCore/testing/Internals.h</a></li>
<li><a href="#trunkSourceWebCoretestingInternalsidl">trunk/Source/WebCore/testing/Internals.idl</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/LayoutTests/ChangeLog 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -1,3 +1,20 @@
</span><ins>+2015-07-17 Tim Horton <timothy_horton@apple.com>
+
+ Improve rect shrink-wrapping algorithm
+ https://bugs.webkit.org/show_bug.cgi?id=147037
+ <rdar://problem/21643094>
+
+ Reviewed by Simon Fraser.
+
+ * fast/shrink-wrap/rect-shrink-wrap-expected.png:
+ * fast/shrink-wrap/rect-shrink-wrap.html:
+ Add a radius parameter to testRects, defaulting to 8.
+
+ Add an offset parameter to testRects, making it easier to slide
+ the rect sets around.
+
+ Add some more test cases.
+
</ins><span class="cx"> 2015-07-17 Nan Wang <n_wang@apple.com>
</span><span class="cx">
</span><span class="cx"> AX: iframe within table cell is inaccessible to VoiceOver
</span></span></pre></div>
<a id="trunkLayoutTestsfastshrinkwraprectshrinkwrapexpectedpng"></a>
<div class="binary"><h4>Modified: trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap-expected.png</h4>
<pre class="diff"><span>
<span class="cx">(Binary files differ)
</span></span></pre></div>
<a id="trunkLayoutTestsfastshrinkwraprectshrinkwraphtml"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -1,20 +1,27 @@
</span><span class="cx"> <script>
</span><span class="cx">
</span><del>-function testRects(rects) {
</del><ins>+function testRects(offset, rects, radius) {
</ins><span class="cx"> if (!window.internals)
</span><span class="cx"> document.write("This test must be run in a test runner.")
</span><span class="cx">
</span><ins>+ if (radius == undefined)
+ radius = 8;
+
</ins><span class="cx"> var concatRects = [];
</span><span class="cx"> for (var i in rects)
</span><span class="cx"> Array.prototype.push.apply(concatRects, rects[i]);
</span><span class="cx">
</span><span class="cx"> var path = undefined;
</span><span class="cx"> if (window.internals)
</span><del>- path = window.internals.pathWithShrinkWrappedRects(concatRects);
</del><ins>+ path = window.internals.pathWithShrinkWrappedRects(concatRects, radius);
</ins><span class="cx">
</span><span class="cx"> var canvas = document.getElementById("shrink");
</span><span class="cx"> var ctx = canvas.getContext("2d");
</span><span class="cx">
</span><ins>+ ctx.save();
+
+ ctx.translate.apply(ctx, offset);
+
</ins><span class="cx"> ctx.fillStyle = "rgba(0,0,0,0.2)";
</span><span class="cx">
</span><span class="cx"> for (var i in rects)
</span><span class="lines">@@ -29,118 +36,203 @@
</span><span class="cx"> ctx.lineWidth = 3;
</span><span class="cx"> if (path)
</span><span class="cx"> ctx.stroke(path);
</span><ins>+
+ ctx.restore();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> window.onload = function () {
</span><span class="cx"> // Right and left aligned, touching:
</span><span class="cx">
</span><del>- testRects([
- [20, 20, 50, 20],
- [20, 40, 35, 20],
- [20, 60, 20, 20]]);
</del><ins>+ testRects([20, 20], [
+ [0, 0, 50, 20],
+ [0, 20, 35, 20],
+ [0, 40, 20, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [20, 90, 20, 20],
- [20, 110, 35, 20],
- [20, 130, 50, 20]]);
</del><ins>+ testRects([20, 90], [
+ [0, 0, 20, 20],
+ [0, 20, 35, 20],
+ [0, 40, 50, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [80, 20, 50, 20],
- [95, 40, 35, 20],
- [110, 60, 20, 20]]);
</del><ins>+ testRects([80, 20], [
+ [0, 0, 50, 20],
+ [15, 20, 35, 20],
+ [30, 40, 20, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [110, 90, 20, 20],
- [95, 110, 35, 20],
- [80, 130, 50, 20]]);
</del><ins>+ testRects([80, 90], [
+ [30, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]]);
</ins><span class="cx">
</span><span class="cx"> // Center aligned, touching:
</span><span class="cx">
</span><del>- testRects([
- [170, 20, 100, 40],
- [190, 60, 60, 40],
- [205, 100, 30, 40]]);
</del><ins>+ testRects([170, 20], [
+ [0, 0, 100, 40],
+ [20, 40, 60, 40],
+ [35, 80, 30, 40]]);
</ins><span class="cx">
</span><del>- testRects([
- [305, 20, 30, 40],
- [290, 60, 60, 40],
- [270, 100, 100, 40]]);
</del><ins>+ testRects([270, 20], [
+ [35, 0, 30, 40],
+ [20, 40, 60, 40],
+ [0, 80, 100, 40]]);
</ins><span class="cx">
</span><del>- testRects([
- [370, 20, 100, 40],
- [405, 60, 30, 40],
- [390, 100, 60, 40]]);
</del><ins>+ testRects([370, 20], [
+ [0, 0, 100, 40],
+ [35, 40, 30, 40],
+ [20, 80, 60, 40]]);
</ins><span class="cx">
</span><span class="cx"> // Other:
</span><span class="cx">
</span><del>- testRects([
- [20, 200, 40, 40],
- [40, 220, 40, 40],
- [60, 240, 40, 40]]);
</del><ins>+ testRects([20, 200], [
+ [0, 0, 40, 40],
+ [20, 20, 40, 40],
+ [40, 40, 40, 40]]);
</ins><span class="cx">
</span><del>- testRects([
- [120, 200, 40, 40],
- [120, 240, 40, 40],
- [120, 280, 40, 40]]);
</del><ins>+ testRects([120, 200], [
+ [0, 40, 40, 40],
+ [20, 20, 40, 40],
+ [40, 0, 40, 40]]);
</ins><span class="cx">
</span><ins>+ testRects([220, 200], [
+ [0, 0, 40, 40],
+ [0, 40, 40, 40],
+ [0, 80, 40, 40]]);
+
+ testRects([200, 350], [
+ [0, 0, 100, 50],
+ [0, 25, 50, 50]]);
+
</ins><span class="cx"> // Non-touching:
</span><span class="cx">
</span><del>- testRects([
- [180, 200, 40, 60],
- [180, 280, 40, 40]]);
</del><ins>+ testRects([20, 300], [
+ [0, 0, 40, 60],
+ [0, 80, 40, 40]]);
</ins><span class="cx">
</span><span class="cx"> // Combination of touching and non-touching:
</span><span class="cx">
</span><del>- testRects([
- [280, 200, 30, 40],
- [280, 280, 50, 40],
- [340, 200, 40, 40],
- [360, 240, 80, 40],
- [380, 280, 40, 40],
- [430, 200, 40, 20],
- [450, 215, 40, 20],
- [470, 230, 40, 20]]);
</del><ins>+ testRects([280, 200], [
+ [0, 0, 30, 40],
+ [0, 80, 50, 40],
+ [60, 0, 40, 40],
+ [80, 40, 80, 40],
+ [100, 80, 40, 40],
+ [150, 0, 40, 20],
+ [170, 15, 40, 20],
+ [190, 30, 40, 20]]);
</ins><span class="cx">
</span><del>- // Incorrectly sorted:
</del><ins>+ // Enclosing:
</ins><span class="cx">
</span><del>- testRects([
- [20, 380, 40, 40],
- [40, 360, 40, 40],
- [60, 340, 40, 40]]);
</del><ins>+ testRects([100, 300], [
+ [0, 0, 50, 50],
+ [10, 10, 20, 20]]);
</ins><span class="cx">
</span><del>- // Broken:
</del><ins>+ testRects([100, 370], [
+ [0, 0, 50, 50],
+ [10, 10, 20, 20],
+ [20, 20, 20, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [600+100, 90, 20, 20],
- [600+95, 110, 35, 20],
- [600+80, 130, 50, 20]]);
</del><ins>+ // Harder (widths less than the radius, horizontally arranged, etc.):
</ins><span class="cx">
</span><del>- testRects([
- [230+340, 20, 40, 40],
- [230+360, 60, 65, 40],
- [230+380, 100, 40, 40]]);
</del><ins>+ testRects([500, 20], [
+ [0, 0, 40, 40],
+ [20, 40, 65, 40],
+ [40, 80, 40, 40]]);
</ins><span class="cx">
</span><del>- // These should fallback to a rounded bounding rect:
</del><ins>+ testRects([600, 20], [
+ [20, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [600+100, 190, 20, 20],
- [600+95, 210, 35, 20],
- [600+80, 210, 50, 20]]);
</del><ins>+ testRects([650, 100], [
+ [0, 0, 40, 40],
+ [40, 0, 40, 40],
+ [80, 0, 40, 40]]);
</ins><span class="cx">
</span><del>- testRects([
- [600+0, 250, 40, 40],
- [600+40, 250, 40, 40],
- [600+80, 250, 40, 40]]);
</del><ins>+ testRects([700, 20], [
+ [20, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 20, 50, 20]]);
</ins><span class="cx">
</span><del>- testRects([
- [600, 300, 20, 40],
- [600+20, 320, 20, 40],
- [600, 340, 20, 40]]);
</del><ins>+ testRects([600, 200], [
+ [0, 0, 20, 40],
+ [20, 20, 20, 40],
+ [40, 0, 20, 40]]);
</ins><span class="cx">
</span><del>- testRects([
- [700, 300, 20, 40],
- [700+20, 320, 20, 40],
- [700+40, 300, 20, 40]]);
</del><ins>+ testRects([700, 200], [
+ [0, 0, 20, 40],
+ [20, 25, 20, 40],
+ [0, 50, 20, 40]]);
+
+ // Huge radius:
+
+ testRects([20, 450], [
+ [0, 0, 50, 20],
+ [0, 20, 35, 20],
+ [0, 40, 20, 20]], 100);
+
+ testRects([20, 520], [
+ [0, 0, 20, 20],
+ [0, 20, 35, 20],
+ [0, 40, 50, 20]], 100);
+
+ testRects([80, 450], [
+ [0, 0, 50, 20],
+ [15, 20, 35, 20],
+ [30, 40, 20, 20]], 100);
+
+ testRects([80, 520], [
+ [30, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]], 100);
+
+ testRects([170, 450], [
+ [0, 0, 100, 40],
+ [20, 40, 60, 40],
+ [35, 80, 30, 40]], 100);
+
+ testRects([270, 450], [
+ [35, 0, 30, 40],
+ [20, 40, 60, 40],
+ [0, 80, 100, 40]], 100);
+
+ testRects([370, 450], [
+ [0, 0, 100, 40],
+ [35, 40, 30, 40],
+ [20, 80, 60, 40]], 100);
+
+ testRects([750, 500], [
+ [0, 0, 20, 40],
+ [20, 20, 20, 40],
+ [0, 40, 20, 40]]);
+
+ // Holes:
+
+ testRects([400, 300], [
+ [30, 0, 40, 40],
+ [60, 40, 40, 40],
+ [30, 80, 40, 40],
+ [0, 40, 40, 40]]);
+
+ // Lines with overlap:
+
+ testRects([520, 450], [
+ [0, 0, 50, 20],
+ [0, 15, 35, 20],
+ [0, 30, 20, 20]]);
+
+ testRects([520, 520], [
+ [0, 0, 20, 20],
+ [0, 15, 35, 20],
+ [0, 30, 50, 20]]);
+
+ testRects([580, 450], [
+ [0, 0, 50, 20],
+ [15, 15, 35, 20],
+ [30, 30, 20, 20]]);
+
+ testRects([580, 520], [
+ [30, 0, 20, 20],
+ [15, 15, 35, 20],
+ [0, 30, 50, 20]]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> </script>
</span></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/ChangeLog 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -1,3 +1,73 @@
</span><ins>+2015-07-17 Tim Horton <timothy_horton@apple.com>
+
+ Improve rect shrink-wrapping algorithm
+ https://bugs.webkit.org/show_bug.cgi?id=147037
+ <rdar://problem/21643094>
+
+ Reviewed by Simon Fraser.
+
+ * platform/graphics/FloatPoint.h:
+ (WebCore::areEssentiallyEqual):
+ Added; implementation is the same as FloatSize's.
+
+ * platform/graphics/PathUtilities.cpp:
+ (WebCore::FloatPointGraph::FloatPointGraph):
+ (WebCore::FloatPointGraph::~FloatPointGraph):
+ (WebCore::FloatPointGraph::Node::Node):
+ (WebCore::FloatPointGraph::Node::nextPoints):
+ (WebCore::FloatPointGraph::Node::addNextPoint):
+ (WebCore::FloatPointGraph::Node::isVisited):
+ (WebCore::FloatPointGraph::Node::visit):
+ (WebCore::FloatPointGraph::Node::reset):
+ (WebCore::FloatPointGraph::reset):
+ (WebCore::FloatPointGraph::findOrCreateNode):
+ (WebCore::findLineSegmentIntersection):
+ (WebCore::addIntersectionPoints):
+ (WebCore::walkGraphAndExtractPolygon):
+ (WebCore::findUnvisitedPolygonStartPoint):
+ (WebCore::unitePolygons):
+ (WebCore::edgesForRect):
+ (WebCore::PathUtilities::pathWithShrinkWrappedRects):
+ (WebCore::addShrinkWrapRightCorner): Deleted.
+ (WebCore::addShrinkWrapLeftCorner): Deleted.
+ (WebCore::addShrinkWrappedPathForRects): Deleted.
+ (WebCore::rectsIntersectOrTouch): Deleted.
+ (WebCore::findSetContainingRect): Deleted.
+ Add a new implementation of shrink-wrap, which is significantly more
+ generic than the old one, which assumed a top-down progression of rects.
+
+ This version uses polygon intersection to find the path around the
+ set of rects, and then follows said path and adds appropriately-sized
+ arcs for the corners.
+
+ The polygon intersection algorithm first finds all the intersection points
+ between all of the rects, then builds a graph of edges outward from one point.
+ It then traverses the graph, choosing at each point the next edge which
+ has not been visited and has the greatest interior angle, recording the polygon as it goes.
+
+ If at the end of the traversal we have not returned to the initial node,
+ we give up on shrink-wrapping and just use a bounding box around the rects.
+
+ If any of the original rects have not been visited at all, we repeat the traversal
+ starting with that rect, making an additional polygon (since we removed completely contained
+ rects before we started, having not visited the rect at all means that it's not connected
+ to the others).
+
+ Once we have a set of united polygons, we follow each one, determining the ideal (always
+ equal in width and height, never more than half the length of either edge, so that we always
+ have a smooth curve) arc radius and projecting it onto the edge, and then
+ adding an arc between the end of the previous path and beginning of the next.
+
+ Because the shrink-wrap algorithm is fairly expensive, if there are more than 20 rects,
+ we fall back to a bounding box. Given the current use cases, this is more than enough
+ rects, but can certainly be adjusted in the future if needed.
+
+ * testing/Internals.cpp:
+ (WebCore::Internals::pathWithShrinkWrappedRects):
+ * testing/Internals.h:
+ * testing/Internals.idl:
+ Add a radius parameter.
+
</ins><span class="cx"> 2015-07-17 Nan Wang <n_wang@apple.com>
</span><span class="cx">
</span><span class="cx"> AX: iframe within table cell is inaccessible to VoiceOver
</span></span></pre></div>
<a id="trunkSourceWebCoreplatformgraphicsFloatPointh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/platform/graphics/FloatPoint.h (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/platform/graphics/FloatPoint.h 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/platform/graphics/FloatPoint.h 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -254,6 +254,11 @@
</span><span class="cx"> return FloatPoint(a.width(), a.height());
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+inline bool areEssentiallyEqual(const FloatPoint& a, const FloatPoint& b)
+{
+ return WTF::areEssentiallyEqual(a.x(), b.x()) && WTF::areEssentiallyEqual(a.y(), b.y());
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+}
+
</ins><span class="cx"> #endif
</span></span></pre></div>
<a id="trunkSourceWebCoreplatformgraphicsPathUtilitiescpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/platform/graphics/PathUtilities.cpp (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/platform/graphics/PathUtilities.cpp 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/platform/graphics/PathUtilities.cpp 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -29,234 +29,305 @@
</span><span class="cx">
</span><span class="cx"> #include "FloatPoint.h"
</span><span class="cx"> #include "FloatRect.h"
</span><ins>+#include "GeometryUtilities.h"
</ins><span class="cx"> #include <math.h>
</span><span class="cx">
</span><span class="cx"> namespace WebCore {
</span><span class="cx">
</span><del>-static void addShrinkWrapRightCorner(Path& path, const FloatRect* fromRect, const FloatRect* toRect, float radius)
-{
- FloatSize horizontalRadius(radius, 0);
- FloatSize verticalRadius(0, radius);
</del><ins>+class FloatPointGraph {
+ WTF_MAKE_NONCOPYABLE(FloatPointGraph);
+public:
+ FloatPointGraph() { }
</ins><span class="cx">
</span><del>- if (!fromRect) {
- // For the first (top) rect:
</del><ins>+ class Node : public FloatPoint {
+ WTF_MAKE_NONCOPYABLE(Node);
+ public:
+ Node(FloatPoint point)
+ : FloatPoint(point)
+ { }
</ins><span class="cx">
</span><del>- path.moveTo(toRect->minXMinYCorner() + horizontalRadius);
</del><ins>+ const Vector<Node*>& nextPoints() const { return m_nextPoints; }
+ void addNextPoint(Node* node)
+ {
+ if (!m_nextPoints.contains(node))
+ m_nextPoints.append(node);
+ }
</ins><span class="cx">
</span><del>- // Across the top, towards the right.
- path.addLineTo(toRect->maxXMinYCorner() - horizontalRadius);
</del><ins>+ bool isVisited() const { return m_visited; }
+ void visit() { m_visited = true; }
</ins><span class="cx">
</span><del>- // Arc the top corner.
- path.addArcTo(toRect->maxXMinYCorner(), toRect->maxXMinYCorner() + verticalRadius, radius);
- } else if (!toRect) {
- // For the last rect:
</del><ins>+ void reset() { m_visited = false; m_nextPoints.clear(); }
</ins><span class="cx">
</span><del>- // Down the right.
- path.addLineTo(fromRect->maxXMaxYCorner() - verticalRadius);
</del><ins>+ private:
+ Vector<Node*> m_nextPoints;
+ bool m_visited { false };
+ };
</ins><span class="cx">
</span><del>- // Arc the bottom corner.
- path.addArcTo(fromRect->maxXMaxYCorner(), fromRect->maxXMaxYCorner() - horizontalRadius, radius);
- } else {
- // For middle rects:
</del><ins>+ typedef std::pair<Node*, Node*> Edge;
+ typedef Vector<Edge> Polygon;
</ins><span class="cx">
</span><del>- float rightEdgeDifference = toRect->maxX() - fromRect->maxX();
</del><ins>+ Node* findOrCreateNode(FloatPoint);
</ins><span class="cx">
</span><del>- // Skip over rects with equal edges, because we can't make
- // sensible curves between them.
- if (fabsf(rightEdgeDifference) < std::numeric_limits<float>::epsilon())
- return;
</del><ins>+ void reset()
+ {
+ for (auto& node : m_allNodes)
+ node->reset();
+ }
</ins><span class="cx">
</span><del>- if (rightEdgeDifference < 0) {
- float effectiveY = std::max(toRect->y(), fromRect->maxY());
- FloatPoint toRectMaxXMinYCorner = FloatPoint(toRect->maxX(), effectiveY);
</del><ins>+private:
+ Vector<std::unique_ptr<Node>> m_allNodes;
+};
</ins><span class="cx">
</span><del>- // Down the right.
- path.addLineTo(FloatPoint(fromRect->maxX(), effectiveY) - verticalRadius);
</del><ins>+FloatPointGraph::Node* FloatPointGraph::findOrCreateNode(FloatPoint point)
+{
+ for (auto& testNode : m_allNodes) {
+ if (areEssentiallyEqual(*testNode, point))
+ return testNode.get();
+ }
</ins><span class="cx">
</span><del>- // Arc the outer corner.
- path.addArcTo(FloatPoint(fromRect->maxX(), effectiveY), FloatPoint(fromRect->maxX(), effectiveY) - horizontalRadius, radius);
</del><ins>+ m_allNodes.append(std::make_unique<FloatPointGraph::Node>(point));
+ return m_allNodes.last().get();
+}
</ins><span class="cx">
</span><del>- // Across the bottom, towards the left.
- path.addLineTo(toRectMaxXMinYCorner + horizontalRadius);
</del><ins>+static bool findLineSegmentIntersection(const FloatPointGraph::Edge& edgeA, const FloatPointGraph::Edge& edgeB, FloatPoint& intersectionPoint)
+{
+ if (!findIntersection(*edgeA.first, *edgeA.second, *edgeB.first, *edgeB.second, intersectionPoint))
+ return false;
</ins><span class="cx">
</span><del>- // Arc the inner corner.
- path.addArcTo(toRectMaxXMinYCorner, toRectMaxXMinYCorner + verticalRadius, radius);
- } else {
- float effectiveY = std::min(toRect->y(), fromRect->maxY());
- FloatPoint toRectMaxXMinYCorner = FloatPoint(toRect->maxX(), effectiveY);
</del><ins>+ FloatPoint edgeAVec(*edgeA.second - *edgeA.first);
+ FloatPoint edgeBVec(*edgeB.second - *edgeB.first);
</ins><span class="cx">
</span><del>- // Down the right.
- path.addLineTo(FloatPoint(fromRect->maxX(), effectiveY) - verticalRadius);
</del><ins>+ float dotA = edgeAVec.dot(toFloatPoint(intersectionPoint - *edgeA.first));
+ if (dotA < 0 || dotA > edgeAVec.lengthSquared())
+ return false;
</ins><span class="cx">
</span><del>- // Arc the inner corner.
- path.addArcTo(FloatPoint(fromRect->maxX(), effectiveY), FloatPoint(fromRect->maxX(), effectiveY) + horizontalRadius, radius);
</del><ins>+ float dotB = edgeBVec.dot(toFloatPoint(intersectionPoint - *edgeB.first));
+ if (dotB < 0 || dotB > edgeBVec.lengthSquared())
+ return false;
</ins><span class="cx">
</span><del>- // Across the bottom, towards the right.
- path.addLineTo(toRectMaxXMinYCorner - horizontalRadius);
</del><ins>+ return true;
+}
</ins><span class="cx">
</span><del>- // Arc the outer corner.
- path.addArcTo(toRectMaxXMinYCorner, toRectMaxXMinYCorner + verticalRadius, radius);
</del><ins>+static bool addIntersectionPoints(Vector<FloatPointGraph::Polygon>& polys, FloatPointGraph& graph)
+{
+ bool foundAnyIntersections = false;
+
+ Vector<FloatPointGraph::Edge> allEdges;
+ for (auto& poly : polys)
+ allEdges.appendVector(poly);
+
+ for (const FloatPointGraph::Edge& edgeA : allEdges) {
+ Vector<FloatPointGraph::Node*> intersectionPoints({edgeA.first, edgeA.second});
+
+ for (const FloatPointGraph::Edge& edgeB : allEdges) {
+ if (&edgeA == &edgeB)
+ continue;
+
+ FloatPoint intersectionPoint;
+ if (!findLineSegmentIntersection(edgeA, edgeB, intersectionPoint))
+ continue;
+ foundAnyIntersections = true;
+ intersectionPoints.append(graph.findOrCreateNode(intersectionPoint));
</ins><span class="cx"> }
</span><ins>+
+ std::sort(intersectionPoints.begin(), intersectionPoints.end(), [edgeA] (FloatPointGraph::Node* a, FloatPointGraph::Node* b) {
+ return FloatPoint(*edgeA.first - *b).lengthSquared() > FloatPoint(*edgeA.first - *a).lengthSquared();
+ });
+
+ for (unsigned pointIndex = 1; pointIndex < intersectionPoints.size(); pointIndex++)
+ intersectionPoints[pointIndex - 1]->addNextPoint(intersectionPoints[pointIndex]);
</ins><span class="cx"> }
</span><ins>+
+ return foundAnyIntersections;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static void addShrinkWrapLeftCorner(Path& path, const FloatRect* fromRect, const FloatRect* toRect, float radius)
</del><ins>+static FloatPointGraph::Polygon walkGraphAndExtractPolygon(FloatPointGraph::Node* startNode)
</ins><span class="cx"> {
</span><del>- FloatSize horizontalRadius(radius, 0);
- FloatSize verticalRadius(0, radius);
</del><ins>+ FloatPointGraph::Polygon outPoly;
</ins><span class="cx">
</span><del>- if (!fromRect) {
- // For the first (bottom) rect:
</del><ins>+ FloatPointGraph::Node* currentNode = startNode;
+ FloatPointGraph::Node* previousNode = startNode;
</ins><span class="cx">
</span><del>- // Across the bottom, towards the left.
- path.addLineTo(toRect->minXMaxYCorner() + horizontalRadius);
</del><ins>+ do {
+ currentNode->visit();
</ins><span class="cx">
</span><del>- // Arc the bottom corner.
- path.addArcTo(toRect->minXMaxYCorner(), toRect->minXMaxYCorner() - verticalRadius, radius);
</del><ins>+ FloatPoint currentVec(*previousNode - *currentNode);
+ currentVec.normalize();
</ins><span class="cx">
</span><del>- } else if (!toRect) {
- // For the last (top) rect:
</del><ins>+ // Walk the graph, at each node choosing the next non-visited
+ // point with the greatest internal angle.
+ FloatPointGraph::Node* nextNode = nullptr;
+ float nextNodeAngle = 0;
+ for (auto potentialNextNode : currentNode->nextPoints()) {
+ if (potentialNextNode == currentNode)
+ continue;
</ins><span class="cx">
</span><del>- // Up the left.
- path.addLineTo(fromRect->minXMinYCorner() + verticalRadius);
</del><ins>+ // If we can get back to the start, we should, ignoring the fact that we already visited it.
+ // Otherwise we'll head inside the shape.
+ if (potentialNextNode == startNode) {
+ nextNode = startNode;
+ break;
+ }
</ins><span class="cx">
</span><del>- // Arc the top corner.
- path.addArcTo(fromRect->minXMinYCorner(), fromRect->minXMinYCorner() + horizontalRadius, radius);
- } else {
- // For middle rects:
- float leftEdgeDifference = fromRect->x() - toRect->x();
</del><ins>+ if (potentialNextNode->isVisited())
+ continue;
</ins><span class="cx">
</span><del>- // Skip over rects with equal edges, because we can't make
- // sensible curves between them.
- if (fabsf(leftEdgeDifference) < std::numeric_limits<float>::epsilon())
- return;
</del><ins>+ FloatPoint nextVec(*potentialNextNode - *currentNode);
+ nextVec.normalize();
</ins><span class="cx">
</span><del>- if (leftEdgeDifference < 0) {
- float effectiveY = std::min(toRect->maxY(), fromRect->y());
- FloatPoint toRectMinXMaxYCorner = FloatPoint(toRect->x(), effectiveY);
</del><ins>+ float angle = acos(nextVec.dot(currentVec));
+ float crossZ = nextVec.x() * currentVec.y() - nextVec.y() * currentVec.x();
</ins><span class="cx">
</span><del>- // Up the right.
- path.addLineTo(FloatPoint(fromRect->x(), effectiveY) + verticalRadius);
</del><ins>+ if (crossZ < 0)
+ angle = (2 * M_PI) - angle;
</ins><span class="cx">
</span><del>- // Arc the inner corner.
- path.addArcTo(FloatPoint(fromRect->x(), effectiveY), FloatPoint(fromRect->x(), effectiveY) + horizontalRadius, radius);
</del><ins>+ if (!nextNode || angle > nextNodeAngle) {
+ nextNode = potentialNextNode;
+ nextNodeAngle = angle;
+ }
+ }
</ins><span class="cx">
</span><del>- // Across the bottom, towards the right.
- path.addLineTo(toRectMinXMaxYCorner - horizontalRadius);
</del><ins>+ // If we don't end up at a node adjacent to the starting node,
+ // something went wrong (there's probably a hole in the shape),
+ // so bail out. We'll use a bounding box instead.
+ if (!nextNode)
+ return FloatPointGraph::Polygon();
</ins><span class="cx">
</span><del>- // Arc the outer corner.
- path.addArcTo(toRectMinXMaxYCorner, toRectMinXMaxYCorner - verticalRadius, radius);
- } else {
- float effectiveY = std::max(toRect->maxY(), fromRect->y());
- FloatPoint toRectMinXMaxYCorner = FloatPoint(toRect->x(), effectiveY);
</del><ins>+ outPoly.append(std::make_pair(currentNode, nextNode));
</ins><span class="cx">
</span><del>- // Up the right.
- path.addLineTo(FloatPoint(fromRect->x(), effectiveY) + verticalRadius);
</del><ins>+ previousNode = currentNode;
+ currentNode = nextNode;
+ } while (currentNode != startNode);
</ins><span class="cx">
</span><del>- // Arc the outer corner.
- path.addArcTo(FloatPoint(fromRect->x(), effectiveY), FloatPoint(fromRect->x(), effectiveY) - horizontalRadius, radius);
</del><ins>+ return outPoly;
+}
</ins><span class="cx">
</span><del>- // Across the bottom, towards the left.
- path.addLineTo(toRectMinXMaxYCorner + horizontalRadius);
</del><ins>+static FloatPointGraph::Node* findUnvisitedPolygonStartPoint(Vector<FloatPointGraph::Polygon>& polys)
+{
+ for (auto& poly : polys) {
+ for (auto& edge : poly) {
+ if (edge.first->isVisited() || edge.second->isVisited())
+ goto nextPolygon;
+ }
</ins><span class="cx">
</span><del>- // Arc the inner corner.
- path.addArcTo(toRectMinXMaxYCorner, toRectMinXMaxYCorner - verticalRadius, radius);
- }
</del><ins>+ // FIXME: We should make sure we find an outside edge to start with.
+ return poly[0].first;
+ nextPolygon:
+ continue;
</ins><span class="cx"> }
</span><ins>+ return nullptr;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static void addShrinkWrappedPathForRects(Path& path, Vector<FloatRect>& rects, float radius)
</del><ins>+static Vector<FloatPointGraph::Polygon> unitePolygons(Vector<FloatPointGraph::Polygon>& polys, FloatPointGraph& graph)
</ins><span class="cx"> {
</span><del>- size_t rectCount = rects.size();
</del><ins>+ graph.reset();
</ins><span class="cx">
</span><del>- std::sort(rects.begin(), rects.end(), [](FloatRect a, FloatRect b) { return b.y() > a.y(); });
</del><ins>+ // There are no intersections, so the polygons are disjoint (we already removed wholly-contained rects in an earlier step).
+ if (!addIntersectionPoints(polys, graph))
+ return polys;
</ins><span class="cx">
</span><del>- for (size_t i = 0; i <= rectCount; ++i)
- addShrinkWrapRightCorner(path, i ? &rects[i - 1] : nullptr, i < rectCount ? &rects[i] : nullptr, radius);
</del><ins>+ Vector<FloatPointGraph::Polygon> unitedPolygons;
</ins><span class="cx">
</span><del>- for (size_t i = 0; i <= rectCount; ++i) {
- size_t reverseIndex = rectCount - i;
- addShrinkWrapLeftCorner(path, reverseIndex < rectCount ? &rects[reverseIndex] : nullptr, reverseIndex ? &rects[reverseIndex - 1] : nullptr, radius);
</del><ins>+ while (FloatPointGraph::Node* startNode = findUnvisitedPolygonStartPoint(polys)) {
+ FloatPointGraph::Polygon unitedPolygon = walkGraphAndExtractPolygon(startNode);
+ if (unitedPolygon.isEmpty())
+ return Vector<FloatPointGraph::Polygon>();
+ unitedPolygons.append(unitedPolygon);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- path.closeSubpath();
</del><ins>+ return unitedPolygons;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static bool rectsIntersectOrTouch(const FloatRect& a, const FloatRect& b)
</del><ins>+static FloatPointGraph::Polygon edgesForRect(FloatRect rect, FloatPointGraph& graph)
</ins><span class="cx"> {
</span><del>- return !a.isEmpty() && !b.isEmpty()
- && a.x() <= b.maxX() && b.x() <= a.maxX()
- && a.y() <= b.maxY() && b.y() <= a.maxY();
</del><ins>+ auto minMin = graph.findOrCreateNode(rect.minXMinYCorner());
+ auto minMax = graph.findOrCreateNode(rect.minXMaxYCorner());
+ auto maxMax = graph.findOrCreateNode(rect.maxXMaxYCorner());
+ auto maxMin = graph.findOrCreateNode(rect.maxXMinYCorner());
+
+ return FloatPointGraph::Polygon({
+ std::make_pair(minMin, maxMin),
+ std::make_pair(maxMin, maxMax),
+ std::make_pair(maxMax, minMax),
+ std::make_pair(minMax, minMin)
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-static Vector<FloatRect>* findSetContainingRect(Vector<Vector<FloatRect>>& sets, FloatRect rect)
</del><ins>+Path PathUtilities::pathWithShrinkWrappedRects(const Vector<FloatRect>& rects, float radius)
</ins><span class="cx"> {
</span><del>- for (auto& set : sets) {
- if (set.contains(rect))
- return &set;
</del><ins>+ Path path;
+
+ if (rects.isEmpty())
+ return path;
+
+ if (rects.size() > 20) {
+ path.addRoundedRect(unionRect(rects), FloatSize(radius, radius));
+ return path;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- return nullptr;
-}
</del><ins>+ Vector<FloatRect> sortedRects = rects;
</ins><span class="cx">
</span><del>-static Vector<Vector<FloatRect>> contiguousRectGroupsFromRects(const Vector<FloatRect>& rects)
-{
- Vector<std::pair<FloatRect, FloatRect>> intersections;
- Vector<FloatRect> soloRects = rects;
</del><ins>+ std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) { return b.y() > a.y(); });
</ins><span class="cx">
</span><del>- for (auto& rectA : rects) {
- for (auto& rectB : rects) {
- if (rectA == rectB)
</del><ins>+ FloatPointGraph graph;
+ Vector<FloatPointGraph::Polygon> rectPolygons;
+ rectPolygons.reserveInitialCapacity(sortedRects.size());
+
+ for (auto& rect : sortedRects) {
+ bool isContained = false;
+ for (auto& otherRect : sortedRects) {
+ if (&rect == &otherRect)
</ins><span class="cx"> continue;
</span><del>-
- if (rectsIntersectOrTouch(rectA, rectB)) {
- intersections.append(std::make_pair(rectA, rectB));
- soloRects.removeAllMatching([rectA, rectB](FloatRect q) { return q == rectA || q == rectB; });
</del><ins>+ if (otherRect.contains(rect)) {
+ isContained = true;
+ break;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><ins>+
+ if (!isContained)
+ rectPolygons.append(edgesForRect(rect, graph));
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Vector<Vector<FloatRect>> rectSets;
</del><ins>+ Vector<FloatPointGraph::Polygon> polys = unitePolygons(rectPolygons, graph);
</ins><span class="cx">
</span><del>- for (auto& intersectingPair : intersections) {
- if (Vector<FloatRect>* rectContainingFirst = findSetContainingRect(rectSets, intersectingPair.first)) {
- if (!rectContainingFirst->contains(intersectingPair.second))
- rectContainingFirst->append(intersectingPair.second);
- continue;
- }
</del><ins>+ if (polys.isEmpty()) {
+ path.addRoundedRect(unionRect(sortedRects), FloatSize(radius, radius));
+ return path;
+ }
</ins><span class="cx">
</span><del>- if (Vector<FloatRect>* rectContainingSecond = findSetContainingRect(rectSets, intersectingPair.second)) {
- if (!rectContainingSecond->contains(intersectingPair.first))
- rectContainingSecond->append(intersectingPair.first);
- continue;
- }
</del><ins>+ for (auto& poly : polys) {
+ for (unsigned i = 0; i < poly.size(); i++) {
+ FloatPointGraph::Edge& toEdge = poly[i];
+ // Connect the first edge to the last.
+ FloatPointGraph::Edge& fromEdge = (i > 0) ? poly[i - 1] : poly[poly.size() - 1];
</ins><span class="cx">
</span><del>- // We didn't find a set including either of our rects, so start a new one.
- rectSets.append(Vector<FloatRect>({intersectingPair.first, intersectingPair.second}));
</del><ins>+ FloatPoint fromEdgeVec = toFloatPoint(*fromEdge.second - *fromEdge.first);
+ FloatPoint toEdgeVec = toFloatPoint(*toEdge.second - *toEdge.first);
</ins><span class="cx">
</span><del>- continue;
- }
</del><ins>+ // Clamp the radius to no more than half the length of either adjacent edge,
+ // because we want a smooth curve and don't want unequal radii.
+ float clampedRadius = std::min(radius, fabsf(fromEdgeVec.x() ? fromEdgeVec.x() : fromEdgeVec.y()) / 2);
+ clampedRadius = std::min(clampedRadius, fabsf(toEdgeVec.x() ? toEdgeVec.x() : toEdgeVec.y()) / 2);
</ins><span class="cx">
</span><del>- for (auto& rect : soloRects) {
- ASSERT(!findSetContainingRect(rectSets, rect));
- rectSets.append(Vector<FloatRect>({rect}));
- }
</del><ins>+ FloatPoint fromEdgeNorm = fromEdgeVec;
+ fromEdgeNorm.normalize();
+ FloatPoint toEdgeNorm = toEdgeVec;
+ toEdgeNorm.normalize();
</ins><span class="cx">
</span><del>- return rectSets;
-}
</del><ins>+ // Project the radius along the incoming and outgoing edge.
+ FloatSize fromOffset = clampedRadius * toFloatSize(fromEdgeNorm);
+ FloatSize toOffset = clampedRadius * toFloatSize(toEdgeNorm);
</ins><span class="cx">
</span><del>-Path PathUtilities::pathWithShrinkWrappedRects(const Vector<FloatRect>& rects, float radius)
-{
- Path path;
</del><ins>+ if (!i)
+ path.moveTo(*fromEdge.second - fromOffset);
+ else
+ path.addLineTo(*fromEdge.second - fromOffset);
+ path.addArcTo(*fromEdge.second, *toEdge.first + toOffset, clampedRadius);
+ }
</ins><span class="cx">
</span><del>- if (rects.isEmpty())
- return path;
</del><ins>+ path.closeSubpath();
+ }
</ins><span class="cx">
</span><del>- Vector<Vector<FloatRect>> rectSets = contiguousRectGroupsFromRects(rects);
-
- for (auto& set : rectSets)
- addShrinkWrappedPathForRects(path, set, radius);
-
</del><span class="cx"> return path;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCoretestingInternalscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/testing/Internals.cpp (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/testing/Internals.cpp 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/testing/Internals.cpp 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -2942,7 +2942,7 @@
</span><span class="cx"> return testPreloadScannerViewportSupport(contextDocument());
</span><span class="cx"> }
</span><span class="cx">
</span><del>-PassRefPtr<DOMPath> Internals::pathWithShrinkWrappedRects(Vector<double> rectComponents, ExceptionCode& ec)
</del><ins>+PassRefPtr<DOMPath> Internals::pathWithShrinkWrappedRects(Vector<double> rectComponents, double radius, ExceptionCode& ec)
</ins><span class="cx"> {
</span><span class="cx"> if (rectComponents.size() % 4) {
</span><span class="cx"> ec = INVALID_ACCESS_ERR;
</span><span class="lines">@@ -2961,8 +2961,7 @@
</span><span class="cx">
</span><span class="cx"> rects.reverse();
</span><span class="cx">
</span><del>- // FIXME: radius should be a parameter instead of fixed as 8.
- Path path = PathUtilities::pathWithShrinkWrappedRects(rects, 8);
</del><ins>+ Path path = PathUtilities::pathWithShrinkWrappedRects(rects, radius);
</ins><span class="cx"> return DOMPath::create(path);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCoretestingInternalsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/testing/Internals.h (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/testing/Internals.h 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/testing/Internals.h 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -417,7 +417,7 @@
</span><span class="cx"> String scrollSnapOffsets(Element*, ExceptionCode&);
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- PassRefPtr<DOMPath> pathWithShrinkWrappedRects(Vector<double>, ExceptionCode&);
</del><ins>+ PassRefPtr<DOMPath> pathWithShrinkWrappedRects(Vector<double> rectComponents, double radius, ExceptionCode&);
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> explicit Internals(Document*);
</span></span></pre></div>
<a id="trunkSourceWebCoretestingInternalsidl"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/testing/Internals.idl (186975 => 186976)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/testing/Internals.idl 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/testing/Internals.idl 2015-07-17 23:55:59 UTC (rev 186976)
</span><span class="lines">@@ -378,5 +378,5 @@
</span><span class="cx"> [RaisesException] DOMString scrollSnapOffsets(Element element);
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- [RaisesException] DOMPath pathWithShrinkWrappedRects(sequence<double> rectComponents);
</del><ins>+ [RaisesException] DOMPath pathWithShrinkWrappedRects(sequence<double> rectComponents, double radius);
</ins><span class="cx"> };
</span></span></pre>
</div>
</div>
</body>
</html>