src/third_party/WebKit/Source/core/rendering/shapes/RasterShape.cpp

   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
  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
  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
  69 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
  76 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);
  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
 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
 121 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
 139 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
 153 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