blob: 943756a97710e4c00453f6eca379e6fce7213074 [file] [log] [blame]
/*
* Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
* THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_GEOMETRY_REGION_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_GEOMETRY_REGION_H_
#include "cc/base/region.h"
#include "third_party/blink/renderer/platform/geometry/int_rect.h"
#include "third_party/blink/renderer/platform/platform_export.h"
#include "third_party/blink/renderer/platform/wtf/allocator.h"
#include "third_party/blink/renderer/platform/wtf/vector.h"
namespace cc {
class Region;
}
namespace blink {
// A region class based on the paper "Scanline Coherent Shape Algebra"
// by Jonathan E. Steinhart from the book "Graphics Gems II".
//
// This implementation uses two vectors instead of linked list, and
// also compresses regions when possible.
class PLATFORM_EXPORT Region {
DISALLOW_NEW();
public:
Region();
Region(const IntRect&);
IntRect Bounds() const { return bounds_; }
bool IsEmpty() const { return bounds_.IsEmpty(); }
bool IsRect() const { return shape_.IsRect(); }
Vector<IntRect> Rects() const;
void Unite(const Region&);
void Intersect(const Region&);
void Subtract(const Region&);
void Translate(const IntSize&);
// Returns true if the query region is a subset of this region.
bool Contains(const Region&) const;
bool Contains(const IntPoint&) const;
// Returns true if the query region intersects any part of this region.
bool Intersects(const Region&) const;
uint64_t Area() const;
#ifndef NDEBUG
void Dump() const;
#endif
private:
struct Span {
DISALLOW_NEW();
Span(int y, wtf_size_t segment_index)
: y(y), segment_index(segment_index) {}
int y;
wtf_size_t segment_index;
};
// Shape composed of non-overlapping rectangles implied by segments [x, max_x)
// within spans [y, max_y).
//
// Segment iteration returns x and max_x for each segment in a span, in order.
// Span iteration returns y via the Span object; spans are adjacent, so max_y
// is the next Span's y value. (The last Span contains no segments.)
class Shape {
DISALLOW_NEW();
public:
Shape();
Shape(const IntRect&);
Shape(wtf_size_t segments_capacity, wtf_size_t spans_capacity);
IntRect Bounds() const;
bool IsEmpty() const { return spans_.IsEmpty(); }
bool IsRect() const { return spans_.size() <= 2 && segments_.size() <= 2; }
typedef const Span* SpanIterator;
SpanIterator SpansBegin() const;
SpanIterator SpansEnd() const;
wtf_size_t SpansSize() const { return spans_.size(); }
typedef const int* SegmentIterator;
SegmentIterator SegmentsBegin(SpanIterator) const;
SegmentIterator SegmentsEnd(SpanIterator) const;
wtf_size_t SegmentsSize() const { return segments_.size(); }
static Shape UnionShapes(const Shape& shape1, const Shape& shape2);
static Shape IntersectShapes(const Shape& shape1, const Shape& shape2);
static Shape SubtractShapes(const Shape& shape1, const Shape& shape2);
void Translate(const IntSize&);
void Swap(Shape&);
struct CompareContainsOperation;
struct CompareIntersectsOperation;
template <typename CompareOperation>
static bool CompareShapes(const Shape& shape1, const Shape& shape2);
void TrimCapacities();
#ifndef NDEBUG
void Dump() const;
#endif
private:
struct UnionOperation;
struct IntersectOperation;
struct SubtractOperation;
template <typename Operation>
static Shape ShapeOperation(const Shape& shape1, const Shape& shape2);
void AppendSegment(int x);
void AppendSpan(int y);
void AppendSpan(int y, SegmentIterator begin, SegmentIterator end);
void AppendSpans(const Shape&, SpanIterator begin, SpanIterator end);
bool CanCoalesce(SegmentIterator begin, SegmentIterator end);
// Stores all segments for all spans, in order. Each Span's segment_index
// identifies the start of its segments within this vector.
Vector<int, 32> segments_;
Vector<Span, 16> spans_;
friend bool operator==(const Shape&, const Shape&);
};
IntRect bounds_;
Shape shape_;
friend bool operator==(const Region&, const Region&);
friend bool operator==(const Shape&, const Shape&);
friend bool operator==(const Span&, const Span&);
};
static inline Region Intersect(const Region& a, const Region& b) {
Region result(a);
result.Intersect(b);
return result;
}
static inline Region Subtract(const Region& a, const Region& b) {
Region result(a);
result.Subtract(b);
return result;
}
static inline Region Translate(const Region& region, const IntSize& offset) {
Region result(region);
result.Translate(offset);
return result;
}
// Creates a cc::Region with the same data as |region|.
static inline cc::Region RegionToCCRegion(const Region& in_region) {
Vector<IntRect> rects = in_region.Rects();
cc::Region out_region;
for (const IntRect& r : rects)
out_region.Union(gfx::Rect(r.X(), r.Y(), r.Width(), r.Height()));
return out_region;
}
inline bool operator==(const Region& a, const Region& b) {
return a.bounds_ == b.bounds_ && a.shape_ == b.shape_;
}
inline bool operator==(const Region::Shape& a, const Region::Shape& b) {
return a.spans_ == b.spans_ && a.segments_ == b.segments_;
}
inline bool operator==(const Region::Span& a, const Region::Span& b) {
return a.y == b.y && a.segment_index == b.segment_index;
}
} // namespace blink
#endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_GEOMETRY_REGION_H_