1 /*
2 * Copyright (C) 2013 Adobe Systems Incorporated. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above
9 * copyright notice, this list of conditions and the following
10 * disclaimer.
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials
14 * provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
21 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
25 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
27 * OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #include "config.h"
31 #include "core/rendering/shapes/RasterShape.h"
32
33 #include "wtf/MathExtras.h"
34
35 namespace WebCore {
36
37 class MarginIntervalGenerator {
38 public:
39 MarginIntervalGenerator(unsigned radius);
40 void set(int y, const IntShapeInterval&);
41 IntShapeInterval intervalAt(int y) const;
42
43 private:
44 Vector<int> m_xIntercepts;
45 int m_y;
46 int m_x1;
47 int m_x2;
48 };
49
MarginIntervalGenerator(unsigned radius)50 MarginIntervalGenerator::MarginIntervalGenerator(unsigned radius)
51 : m_y(0)
52 , m_x1(0)
53 , m_x2(0)
54 {
55 m_xIntercepts.resize(radius + 1);
56 unsigned radiusSquared = radius * radius;
57 for (unsigned y = 0; y <= radius; y++)
58 m_xIntercepts[y] = sqrt(static_cast<double>(radiusSquared - y * y));
59 }
60
set(int y,const IntShapeInterval & interval)61 void MarginIntervalGenerator::set(int y, const IntShapeInterval& interval)
62 {
63 ASSERT(y >= 0 && interval.x1() >= 0);
64 m_y = y;
65 m_x1 = interval.x1();
66 m_x2 = interval.x2();
67 }
68
intervalAt(int y) const69 IntShapeInterval MarginIntervalGenerator::intervalAt(int y) const
70 {
71 unsigned xInterceptsIndex = abs(y - m_y);
72 int dx = (xInterceptsIndex >= m_xIntercepts.size()) ? 0 : m_xIntercepts[xInterceptsIndex];
73 return IntShapeInterval(m_x1 - dx, m_x2 + dx);
74 }
75
computeShapeMarginIntervals(int shapeMargin) const76 PassOwnPtr<RasterShapeIntervals> RasterShapeIntervals::computeShapeMarginIntervals(int shapeMargin) const
77 {
78 int marginIntervalsSize = (offset() > shapeMargin) ? size() : size() - offset() * 2 + shapeMargin * 2;
79 OwnPtr<RasterShapeIntervals> result = adoptPtr(new RasterShapeIntervals(marginIntervalsSize, std::max(shapeMargin, offset())));
80 MarginIntervalGenerator marginIntervalGenerator(shapeMargin);
81
82 for (int y = bounds().y(); y < bounds().maxY(); ++y) {
83 const IntShapeInterval& intervalAtY = intervalAt(y);
84 if (intervalAtY.isEmpty())
85 continue;
86
87 marginIntervalGenerator.set(y, intervalAtY);
88 int marginY0 = std::max(minY(), y - shapeMargin);
89 int marginY1 = std::min(maxY(), y + shapeMargin + 1);
90
91 for (int marginY = y - 1; marginY >= marginY0; --marginY) {
92 if (marginY > bounds().y() && intervalAt(marginY).contains(intervalAtY))
93 break;
94 result->intervalAt(marginY).unite(marginIntervalGenerator.intervalAt(marginY));
95 }
96
97 result->intervalAt(y).unite(marginIntervalGenerator.intervalAt(y));
98
99 for (int marginY = y + 1; marginY < marginY1; ++marginY) {
100 if (marginY < bounds().maxY() && intervalAt(marginY).contains(intervalAtY))
101 break;
102 result->intervalAt(marginY).unite(marginIntervalGenerator.intervalAt(marginY));
103 }
104 }
105
106 result->initializeBounds();
107 return result.release();
108 }
109
initializeBounds()110 void RasterShapeIntervals::initializeBounds()
111 {
112 m_bounds = IntRect();
113 for (int y = minY(); y < maxY(); ++y) {
114 const IntShapeInterval& intervalAtY = intervalAt(y);
115 if (intervalAtY.isEmpty())
116 continue;
117 m_bounds.unite(IntRect(intervalAtY.x1(), y, intervalAtY.width(), 1));
118 }
119 }
120
buildBoundsPath(Path & path) const121 void RasterShapeIntervals::buildBoundsPath(Path& path) const
122 {
123 int maxY = bounds().maxY();
124 for (int y = bounds().y(); y < maxY; y++) {
125 if (intervalAt(y).isEmpty())
126 continue;
127
128 IntShapeInterval extent = intervalAt(y);
129 int endY = y + 1;
130 for (; endY < maxY; endY++) {
131 if (intervalAt(endY).isEmpty() || intervalAt(endY) != extent)
132 break;
133 }
134 path.addRect(FloatRect(extent.x1(), y, extent.width(), endY - y));
135 y = endY - 1;
136 }
137 }
138
marginIntervals() const139 const RasterShapeIntervals& RasterShape::marginIntervals() const
140 {
141 ASSERT(shapeMargin() >= 0);
142 if (!shapeMargin())
143 return *m_intervals;
144
145 int shapeMarginInt = clampToPositiveInteger(ceil(shapeMargin()));
146 int maxShapeMarginInt = std::max(m_marginRectSize.width(), m_marginRectSize.height()) * sqrtf(2);
147 if (!m_marginIntervals)
148 m_marginIntervals = m_intervals->computeShapeMarginIntervals(std::min(shapeMarginInt, maxShapeMarginInt));
149
150 return *m_marginIntervals;
151 }
152
getExcludedIntervals(LayoutUnit logicalTop,LayoutUnit logicalHeight,SegmentList & result) const153 void RasterShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
154 {
155 const RasterShapeIntervals& intervals = marginIntervals();
156 if (intervals.isEmpty())
157 return;
158
159 int y1 = logicalTop;
160 int y2 = logicalTop + logicalHeight;
161 ASSERT(y2 >= y1);
162 if (y2 < intervals.bounds().y() || y1 >= intervals.bounds().maxY())
163 return;
164
165 y1 = std::max(y1, intervals.bounds().y());
166 y2 = std::min(y2, intervals.bounds().maxY());
167 IntShapeInterval excludedInterval;
168
169 for (int y = y1; y < y2; y++)
170 excludedInterval.unite(intervals.intervalAt(y));
171
172 // Note: |marginIntervals()| returns end-point exclusive
173 // intervals. |excludedInterval.x2()| contains the left-most pixel
174 // offset to the right of the calculated union.
175 result.append(LineSegment(excludedInterval.x1(), excludedInterval.x2()));
176 }
177
178 } // namespace WebCore
179