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 "RasterShape.h"
32
33#include <wtf/MathExtras.h>
34
35namespace WebCore {
36
37class MarginIntervalGenerator {
38public:
39    MarginIntervalGenerator(unsigned radius);
40    void set(int y, const IntShapeInterval&);
41    IntShapeInterval intervalAt(int y) const;
42
43private:
44    Vector<int> m_xIntercepts;
45    int m_y;
46    int m_x1;
47    int m_x2;
48};
49
50MarginIntervalGenerator::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
61void 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
69IntShapeInterval 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
76std::unique_ptr<RasterShapeIntervals> RasterShapeIntervals::computeShapeMarginIntervals(int shapeMargin) const
77{
78    int marginIntervalsSize = (offset() > shapeMargin) ? size() : size() - offset() * 2 + shapeMargin * 2;
79    auto result = std::make_unique<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;
108}
109
110void 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
121void RasterShapeIntervals::buildBoundsPath(Path& path) const
122{
123    for (int y = bounds().y(); y < bounds().maxY(); y++) {
124        if (intervalAt(y).isEmpty())
125            continue;
126
127        IntShapeInterval extent = intervalAt(y);
128        int endY = y + 1;
129        for (; endY < bounds().maxY(); endY++) {
130            if (intervalAt(endY).isEmpty() || intervalAt(endY) != extent)
131                break;
132        }
133        path.addRect(FloatRect(extent.x1(), y, extent.width(), endY - y));
134        y = endY - 1;
135    }
136}
137
138const RasterShapeIntervals& RasterShape::marginIntervals() const
139{
140    ASSERT(shapeMargin() >= 0);
141    if (!shapeMargin())
142        return *m_intervals;
143
144    int shapeMarginInt = clampToPositiveInteger(ceil(shapeMargin()));
145    int maxShapeMarginInt = std::max(m_marginRectSize.width(), m_marginRectSize.height()) * sqrt(2);
146    if (!m_marginIntervals)
147        m_marginIntervals = m_intervals->computeShapeMarginIntervals(std::min(shapeMarginInt, maxShapeMarginInt));
148
149    return *m_marginIntervals;
150}
151
152void RasterShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
153{
154    const RasterShapeIntervals& intervals = marginIntervals();
155    if (intervals.isEmpty())
156        return;
157
158    int y1 = logicalTop;
159    int y2 = logicalTop + logicalHeight;
160    ASSERT(y2 >= y1);
161    if (y2 < intervals.bounds().y() || y1 >= intervals.bounds().maxY())
162        return;
163
164    y1 = std::max(y1, intervals.bounds().y());
165    y2 = std::min(y2, intervals.bounds().maxY());
166    IntShapeInterval excludedInterval;
167
168    for (int y = y1; y < y2;  y++)
169        excludedInterval.unite(intervals.intervalAt(y));
170
171    result.append(LineSegment(excludedInterval.x1(), excludedInterval.x2()));
172}
173
174} // namespace WebCore
175