Region.cpp revision 6fbefbbd8edc9953041289fbd77bb18c4964dce5
1edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 2edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 4edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * you may not use this file except in compliance with the License. 6edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * You may obtain a copy of the License at 7edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 8edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 10edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * See the License for the specific language governing permissions and 14edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * limitations under the License. 15edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 16edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 17edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define LOG_TAG "Region" 18edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 1992dc3fc52cf097bd105460cf377779bdcf146d62Mark Salyzyn#include <inttypes.h> 2072b0ffe4c3776b33844bb00b9be5693bddd391f9Mathias Agopian#include <limits.h> 2172b0ffe4c3776b33844bb00b9be5693bddd391f9Mathias Agopian 2220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#include <utils/Log.h> 23edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/String8.h> 24068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian#include <utils/CallStack.h> 2520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 2620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#include <ui/Rect.h> 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <ui/Region.h> 2820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#include <ui/Point.h> 2920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 3020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#include <private/ui/RegionHelper.h> 3120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 3220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 3320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#define VALIDATE_REGIONS (false) 3420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#define VALIDATE_WITH_CORECG (false) 3520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 3620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 3720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_WITH_CORECG 3820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#include <core/SkRegion.h> 3920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 40edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 41edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectnamespace android { 4220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 4320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 4420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianenum { 4520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian op_nand = region_operator<Rect>::op_nand, 4620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian op_and = region_operator<Rect>::op_and, 4720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian op_or = region_operator<Rect>::op_or, 4820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian op_xor = region_operator<Rect>::op_xor 4920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian}; 50edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 513e010f3138593cc6953039ee0e3db8ee31881296Chris Craikenum { 523e010f3138593cc6953039ee0e3db8ee31881296Chris Craik direction_LTR, 533e010f3138593cc6953039ee0e3db8ee31881296Chris Craik direction_RTL 543e010f3138593cc6953039ee0e3db8ee31881296Chris Craik}; 553e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 56edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 57edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 583ab68558fa5a4b8f792a54965a010f03385bd271Mathias AgopianRegion::Region() { 593ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.add(Rect(0,0)); 60edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 61edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 62edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion::Region(const Region& rhs) 633ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian : mStorage(rhs.mStorage) 64edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 65d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian#if VALIDATE_REGIONS 66d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(rhs, "rhs copy-ctor"); 67d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian#endif 68edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 69edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 703ab68558fa5a4b8f792a54965a010f03385bd271Mathias AgopianRegion::Region(const Rect& rhs) { 713ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.add(rhs); 72edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 73edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 7420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion::~Region() 75edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 76edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 77edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 783e010f3138593cc6953039ee0e3db8ee31881296Chris Craik/** 793e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Copy rects from the src vector into the dst vector, resolving vertical T-Junctions along the way 803e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 813e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * First pass through, divideSpanRTL will be set because the 'previous span' (indexing into the dst 823e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * vector) will be reversed. Each rectangle in the original list, starting from the bottom, will be 833e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * compared with the span directly below, and subdivided as needed to resolve T-junctions. 843e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 853e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * The resulting temporary vector will be a completely reversed copy of the original, without any 863e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * bottom-up T-junctions. 873e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 883e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Second pass through, divideSpanRTL will be false since the previous span will index into the 893e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * final, correctly ordered region buffer. Each rectangle will be compared with the span directly 903e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * above it, and subdivided to resolve any remaining T-junctions. 913e010f3138593cc6953039ee0e3db8ee31881296Chris Craik */ 923e010f3138593cc6953039ee0e3db8ee31881296Chris Craikstatic void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end, 933e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Vector<Rect>& dst, int spanDirection) { 943e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.clear(); 953e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 963e010f3138593cc6953039ee0e3db8ee31881296Chris Craik const Rect* current = end - 1; 973e010f3138593cc6953039ee0e3db8ee31881296Chris Craik int lastTop = current->top; 983e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 993e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // add first span immediately 1003e010f3138593cc6953039ee0e3db8ee31881296Chris Craik do { 1013e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(*current); 1023e010f3138593cc6953039ee0e3db8ee31881296Chris Craik current--; 1033e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } while (current->top == lastTop && current >= begin); 1043e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 105d31824004277f554000417cea349d69f18655e95Dan Stoza int beginLastSpan = -1; 106d31824004277f554000417cea349d69f18655e95Dan Stoza int endLastSpan = -1; 1073e010f3138593cc6953039ee0e3db8ee31881296Chris Craik int top = -1; 1083e010f3138593cc6953039ee0e3db8ee31881296Chris Craik int bottom = -1; 1093e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1103e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // for all other spans, split if a t-junction exists in the span directly above 1113e010f3138593cc6953039ee0e3db8ee31881296Chris Craik while (current >= begin) { 1123e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (current->top != (current + 1)->top) { 1133e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // new span 1143e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if ((spanDirection == direction_RTL && current->bottom != (current + 1)->top) || 1153e010f3138593cc6953039ee0e3db8ee31881296Chris Craik (spanDirection == direction_LTR && current->top != (current + 1)->bottom)) { 1163e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // previous span not directly adjacent, don't check for T junctions 1173e010f3138593cc6953039ee0e3db8ee31881296Chris Craik beginLastSpan = INT_MAX; 1183e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } else { 1193e010f3138593cc6953039ee0e3db8ee31881296Chris Craik beginLastSpan = endLastSpan + 1; 1203e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 121d31824004277f554000417cea349d69f18655e95Dan Stoza endLastSpan = static_cast<int>(dst.size()) - 1; 1223e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1233e010f3138593cc6953039ee0e3db8ee31881296Chris Craik top = current->top; 1243e010f3138593cc6953039ee0e3db8ee31881296Chris Craik bottom = current->bottom; 1253e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1263e010f3138593cc6953039ee0e3db8ee31881296Chris Craik int left = current->left; 1273e010f3138593cc6953039ee0e3db8ee31881296Chris Craik int right = current->right; 1283e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 129d31824004277f554000417cea349d69f18655e95Dan Stoza for (int prevIndex = beginLastSpan; prevIndex <= endLastSpan; prevIndex++) { 130d31824004277f554000417cea349d69f18655e95Dan Stoza // prevIndex can't be -1 here because if endLastSpan is set to a 131d31824004277f554000417cea349d69f18655e95Dan Stoza // value greater than -1 (allowing the loop to execute), 132d31824004277f554000417cea349d69f18655e95Dan Stoza // beginLastSpan (and therefore prevIndex) will also be increased 133d31824004277f554000417cea349d69f18655e95Dan Stoza const Rect* prev = &dst[static_cast<size_t>(prevIndex)]; 134d31824004277f554000417cea349d69f18655e95Dan Stoza 1353e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (spanDirection == direction_RTL) { 1363e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // iterating over previous span RTL, quit if it's too far left 1373e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->right <= left) break; 1383e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1393e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->right > left && prev->right < right) { 1403e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(Rect(prev->right, top, right, bottom)); 1413e010f3138593cc6953039ee0e3db8ee31881296Chris Craik right = prev->right; 1423e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1433e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1443e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->left > left && prev->left < right) { 1453e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(Rect(prev->left, top, right, bottom)); 1463e010f3138593cc6953039ee0e3db8ee31881296Chris Craik right = prev->left; 1473e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1483e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1493e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // if an entry in the previous span is too far right, nothing further left in the 1503e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // current span will need it 1513e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->left >= right) { 1523e010f3138593cc6953039ee0e3db8ee31881296Chris Craik beginLastSpan = prevIndex; 1533e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1543e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } else { 1553e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // iterating over previous span LTR, quit if it's too far right 1563e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->left >= right) break; 1573e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1583e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->left > left && prev->left < right) { 1593e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(Rect(left, top, prev->left, bottom)); 1603e010f3138593cc6953039ee0e3db8ee31881296Chris Craik left = prev->left; 1613e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1623e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1633e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->right > left && prev->right < right) { 1643e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(Rect(left, top, prev->right, bottom)); 1653e010f3138593cc6953039ee0e3db8ee31881296Chris Craik left = prev->right; 1663e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1673e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // if an entry in the previous span is too far left, nothing further right in the 1683e010f3138593cc6953039ee0e3db8ee31881296Chris Craik // current span will need it 1693e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (prev->right <= left) { 1703e010f3138593cc6953039ee0e3db8ee31881296Chris Craik beginLastSpan = prevIndex; 1713e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1723e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1733e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1743e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1753e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (left < right) { 1763e010f3138593cc6953039ee0e3db8ee31881296Chris Craik dst.add(Rect(left, top, right, bottom)); 1773e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1783e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1793e010f3138593cc6953039ee0e3db8ee31881296Chris Craik current--; 1803e010f3138593cc6953039ee0e3db8ee31881296Chris Craik } 1813e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 1823e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1833e010f3138593cc6953039ee0e3db8ee31881296Chris Craik/** 1843e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Creates a new region with the same data as the argument, but divides rectangles as necessary to 1853e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * remove T-Junctions 1863e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * 1873e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * Note: the output will not necessarily be a very efficient representation of the region, since it 1883e010f3138593cc6953039ee0e3db8ee31881296Chris Craik * may be that a triangle-based approach would generate significantly simpler geometry 1893e010f3138593cc6953039ee0e3db8ee31881296Chris Craik */ 1903e010f3138593cc6953039ee0e3db8ee31881296Chris CraikRegion Region::createTJunctionFreeRegion(const Region& r) { 1913e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (r.isEmpty()) return r; 1923e010f3138593cc6953039ee0e3db8ee31881296Chris Craik if (r.isRect()) return r; 1933e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1943e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Vector<Rect> reversed; 1953e010f3138593cc6953039ee0e3db8ee31881296Chris Craik reverseRectsResolvingJunctions(r.begin(), r.end(), reversed, direction_RTL); 1963e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 1973e010f3138593cc6953039ee0e3db8ee31881296Chris Craik Region outputRegion; 1983e010f3138593cc6953039ee0e3db8ee31881296Chris Craik reverseRectsResolvingJunctions(reversed.begin(), reversed.end(), 1993e010f3138593cc6953039ee0e3db8ee31881296Chris Craik outputRegion.mStorage, direction_LTR); 2003e010f3138593cc6953039ee0e3db8ee31881296Chris Craik outputRegion.mStorage.add(r.getBounds()); // to make region valid, mStorage must end with bounds 2013e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 2023e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#if VALIDATE_REGIONS 2033e010f3138593cc6953039ee0e3db8ee31881296Chris Craik validate(outputRegion, "T-Junction free region"); 2043e010f3138593cc6953039ee0e3db8ee31881296Chris Craik#endif 2053e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 2063e010f3138593cc6953039ee0e3db8ee31881296Chris Craik return outputRegion; 2073e010f3138593cc6953039ee0e3db8ee31881296Chris Craik} 2083e010f3138593cc6953039ee0e3db8ee31881296Chris Craik 20920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::operator = (const Region& rhs) 210edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 21120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_REGIONS 212d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(*this, "this->operator="); 213d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(rhs, "rhs.operator="); 21420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 21520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian mStorage = rhs.mStorage; 21620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return *this; 217edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 218edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 2199f96145725ff3f265712d607d19078fb91a5c8ecMathias AgopianRegion& Region::makeBoundsSelf() 2209f96145725ff3f265712d607d19078fb91a5c8ecMathias Agopian{ 2213ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian if (mStorage.size() >= 2) { 2223ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian const Rect bounds(getBounds()); 2233ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.clear(); 2243ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.add(bounds); 2253ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian } 2269f96145725ff3f265712d607d19078fb91a5c8ecMathias Agopian return *this; 2279f96145725ff3f265712d607d19078fb91a5c8ecMathias Agopian} 2289f96145725ff3f265712d607d19078fb91a5c8ecMathias Agopian 2291c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wrightbool Region::contains(const Point& point) const { 2301c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright return contains(point.x, point.y); 2311c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright} 2321c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright 2331c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wrightbool Region::contains(int x, int y) const { 2341c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright const_iterator cur = begin(); 2351c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright const_iterator const tail = end(); 2361c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright while (cur != tail) { 2371c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright if (y >= cur->top && y < cur->bottom && x >= cur->left && x < cur->right) { 2381c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright return true; 2391c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright } 2401c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright cur++; 2411c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright } 2421c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright return false; 2431c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright} 2441c284a9431f98bbefd27a30c3368bbf7366dff3aMichael Wright 245edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid Region::clear() 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 24720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian mStorage.clear(); 2483ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.add(Rect(0,0)); 249edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 250edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 251edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid Region::set(const Rect& r) 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 25320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian mStorage.clear(); 2543ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.add(r); 255edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 256edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 257d31824004277f554000417cea349d69f18655e95Dan Stozavoid Region::set(int32_t w, int32_t h) 2580926f50664c739eaee60341f8e8c694dc9a4f3ebMathias Agopian{ 25920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian mStorage.clear(); 260d31824004277f554000417cea349d69f18655e95Dan Stoza mStorage.add(Rect(w, h)); 2610926f50664c739eaee60341f8e8c694dc9a4f3ebMathias Agopian} 2620926f50664c739eaee60341f8e8c694dc9a4f3ebMathias Agopian 263fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzervoid Region::set(uint32_t w, uint32_t h) 264fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzer{ 265fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzer mStorage.clear(); 266fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzer mStorage.add(Rect(w, h)); 267fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzer} 268fe4966d59b31ae6fd6dd4d81dd73d2f4f7be33feBernhard Rosenkraenzer 2692ca79399b933935eb1b6c0ec1f746f8c4475369cMathias Agopianbool Region::isTriviallyEqual(const Region& region) const { 2702ca79399b933935eb1b6c0ec1f746f8c4475369cMathias Agopian return begin() == region.begin(); 2712ca79399b933935eb1b6c0ec1f746f8c4475369cMathias Agopian} 2722ca79399b933935eb1b6c0ec1f746f8c4475369cMathias Agopian 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 274edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 27520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::addRectUnchecked(int l, int t, int r, int b) 276edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 2773ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian Rect rect(l,t,r,b); 2783ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian size_t where = mStorage.size() - 1; 2793ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian mStorage.insertAt(rect, where, 1); 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 281edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 28220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 28320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 28420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::orSelf(const Rect& r) { 28520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(r, op_or); 28620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 287b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain GuyRegion& Region::xorSelf(const Rect& r) { 288b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operationSelf(r, op_xor); 289b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 29020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::andSelf(const Rect& r) { 29120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(r, op_and); 29220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 29320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::subtractSelf(const Rect& r) { 29420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(r, op_nand); 29520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 29620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::operationSelf(const Rect& r, int op) { 29720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Region lhs(*this); 29820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, *this, lhs, r); 299edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 300edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 301edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 302edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 303edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 304edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::orSelf(const Region& rhs) { 30520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, op_or); 306edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 307b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain GuyRegion& Region::xorSelf(const Region& rhs) { 308b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operationSelf(rhs, op_xor); 309b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 310edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::andSelf(const Region& rhs) { 31120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, op_and); 312edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 313edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::subtractSelf(const Region& rhs) { 31420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, op_nand); 31520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 31620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::operationSelf(const Region& rhs, int op) { 31720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Region lhs(*this); 31820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, *this, lhs, rhs); 319edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 320edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 321edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 322edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::translateSelf(int x, int y) { 32320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if (x|y) translate(*this, x, y); 324edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 325edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 326edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 32720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 32820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 329bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::merge(const Rect& rhs) const { 33020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_or); 33120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 332b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guyconst Region Region::mergeExclusive(const Rect& rhs) const { 333b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operation(rhs, op_xor); 334b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 335bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::intersect(const Rect& rhs) const { 33620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_and); 33720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 338bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::subtract(const Rect& rhs) const { 33920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_nand); 34020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 341bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::operation(const Rect& rhs, int op) const { 342edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Region result; 34320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, result, *this, rhs); 344edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return result; 345edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 346edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 34720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 34820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 349bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::merge(const Region& rhs) const { 35020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_or); 35120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 352b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guyconst Region Region::mergeExclusive(const Region& rhs) const { 353b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operation(rhs, op_xor); 354b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 355bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::intersect(const Region& rhs) const { 35620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_and); 357edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 358bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::subtract(const Region& rhs) const { 35920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, op_nand); 36020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 361bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::operation(const Region& rhs, int op) const { 362edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Region result; 36320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, result, *this, rhs); 364edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return result; 365edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 366edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 367bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::translate(int x, int y) const { 368edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Region result; 36920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian translate(result, *this, x, y); 370edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return result; 371edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 372edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 373edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 374edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 375edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::orSelf(const Region& rhs, int dx, int dy) { 37620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, dx, dy, op_or); 377edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 378b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain GuyRegion& Region::xorSelf(const Region& rhs, int dx, int dy) { 379b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operationSelf(rhs, dx, dy, op_xor); 380b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 381edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::andSelf(const Region& rhs, int dx, int dy) { 38220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, dx, dy, op_and); 383edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 384edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectRegion& Region::subtractSelf(const Region& rhs, int dx, int dy) { 38520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operationSelf(rhs, dx, dy, op_nand); 38620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 38720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion& Region::operationSelf(const Region& rhs, int dx, int dy, int op) { 38820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Region lhs(*this); 38920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, *this, lhs, rhs, dx, dy); 390edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 391edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 392edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 39320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 39420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 395bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::merge(const Region& rhs, int dx, int dy) const { 39620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, dx, dy, op_or); 397edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 398b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guyconst Region Region::mergeExclusive(const Region& rhs, int dx, int dy) const { 399b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy return operation(rhs, dx, dy, op_xor); 400b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy} 401bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::intersect(const Region& rhs, int dx, int dy) const { 40220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, dx, dy, op_and); 403edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 404bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::subtract(const Region& rhs, int dx, int dy) const { 40520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return operation(rhs, dx, dy, op_nand); 40620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 407bed9dd128dfbdc7d9dbca005078536dadc0b9359Mathias Agopianconst Region Region::operation(const Region& rhs, int dx, int dy, int op) const { 408edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Region result; 40920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, result, *this, rhs, dx, dy); 410edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return result; 411edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 412edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 413edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 414edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 41520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// This is our region rasterizer, which merges rects and spans together 41620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// to obtain an optimal region. 417d31824004277f554000417cea349d69f18655e95Dan Stozaclass Region::rasterizer : public region_operator<Rect>::region_rasterizer 41820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 4193ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian Rect bounds; 42020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Vector<Rect>& storage; 42120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect* head; 42220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect* tail; 42320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Vector<Rect> span; 42420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect* cur; 42520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianpublic: 426d31824004277f554000417cea349d69f18655e95Dan Stoza rasterizer(Region& reg) 4273ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian : bounds(INT_MAX, 0, INT_MIN, 0), storage(reg.mStorage), head(), tail(), cur() { 42820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian storage.clear(); 42920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 43020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 431d31824004277f554000417cea349d69f18655e95Dan Stoza virtual ~rasterizer(); 432d31824004277f554000417cea349d69f18655e95Dan Stoza 433d31824004277f554000417cea349d69f18655e95Dan Stoza virtual void operator()(const Rect& rect); 434d31824004277f554000417cea349d69f18655e95Dan Stoza 435d31824004277f554000417cea349d69f18655e95Dan Stozaprivate: 436d31824004277f554000417cea349d69f18655e95Dan Stoza template<typename T> 437d31824004277f554000417cea349d69f18655e95Dan Stoza static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; } 438d31824004277f554000417cea349d69f18655e95Dan Stoza template<typename T> 439d31824004277f554000417cea349d69f18655e95Dan Stoza static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; } 440d31824004277f554000417cea349d69f18655e95Dan Stoza 441d31824004277f554000417cea349d69f18655e95Dan Stoza void flushSpan(); 442d31824004277f554000417cea349d69f18655e95Dan Stoza}; 443d31824004277f554000417cea349d69f18655e95Dan Stoza 444d31824004277f554000417cea349d69f18655e95Dan StozaRegion::rasterizer::~rasterizer() 445d31824004277f554000417cea349d69f18655e95Dan Stoza{ 446d31824004277f554000417cea349d69f18655e95Dan Stoza if (span.size()) { 447d31824004277f554000417cea349d69f18655e95Dan Stoza flushSpan(); 448d31824004277f554000417cea349d69f18655e95Dan Stoza } 449d31824004277f554000417cea349d69f18655e95Dan Stoza if (storage.size()) { 450d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.top = storage.itemAt(0).top; 451d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.bottom = storage.top().bottom; 452d31824004277f554000417cea349d69f18655e95Dan Stoza if (storage.size() == 1) { 453d31824004277f554000417cea349d69f18655e95Dan Stoza storage.clear(); 45420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 455d31824004277f554000417cea349d69f18655e95Dan Stoza } else { 456d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.left = 0; 457d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.right = 0; 45820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 459d31824004277f554000417cea349d69f18655e95Dan Stoza storage.add(bounds); 460d31824004277f554000417cea349d69f18655e95Dan Stoza} 461d31824004277f554000417cea349d69f18655e95Dan Stoza 462d31824004277f554000417cea349d69f18655e95Dan Stozavoid Region::rasterizer::operator()(const Rect& rect) 463d31824004277f554000417cea349d69f18655e95Dan Stoza{ 464d31824004277f554000417cea349d69f18655e95Dan Stoza //ALOGD(">>> %3d, %3d, %3d, %3d", 465d31824004277f554000417cea349d69f18655e95Dan Stoza // rect.left, rect.top, rect.right, rect.bottom); 466d31824004277f554000417cea349d69f18655e95Dan Stoza if (span.size()) { 467d31824004277f554000417cea349d69f18655e95Dan Stoza if (cur->top != rect.top) { 468d31824004277f554000417cea349d69f18655e95Dan Stoza flushSpan(); 469d31824004277f554000417cea349d69f18655e95Dan Stoza } else if (cur->right == rect.left) { 470d31824004277f554000417cea349d69f18655e95Dan Stoza cur->right = rect.right; 471d31824004277f554000417cea349d69f18655e95Dan Stoza return; 47220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 47320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 474d31824004277f554000417cea349d69f18655e95Dan Stoza span.add(rect); 475d31824004277f554000417cea349d69f18655e95Dan Stoza cur = span.editArray() + (span.size() - 1); 476d31824004277f554000417cea349d69f18655e95Dan Stoza} 477d31824004277f554000417cea349d69f18655e95Dan Stoza 478d31824004277f554000417cea349d69f18655e95Dan Stozavoid Region::rasterizer::flushSpan() 479d31824004277f554000417cea349d69f18655e95Dan Stoza{ 480d31824004277f554000417cea349d69f18655e95Dan Stoza bool merge = false; 481d31824004277f554000417cea349d69f18655e95Dan Stoza if (tail-head == ssize_t(span.size())) { 482d31824004277f554000417cea349d69f18655e95Dan Stoza Rect const* p = span.editArray(); 483d31824004277f554000417cea349d69f18655e95Dan Stoza Rect const* q = head; 484d31824004277f554000417cea349d69f18655e95Dan Stoza if (p->top == q->bottom) { 485d31824004277f554000417cea349d69f18655e95Dan Stoza merge = true; 486d31824004277f554000417cea349d69f18655e95Dan Stoza while (q != tail) { 487d31824004277f554000417cea349d69f18655e95Dan Stoza if ((p->left != q->left) || (p->right != q->right)) { 488d31824004277f554000417cea349d69f18655e95Dan Stoza merge = false; 489d31824004277f554000417cea349d69f18655e95Dan Stoza break; 49020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 491d31824004277f554000417cea349d69f18655e95Dan Stoza p++, q++; 49220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 49320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 494d31824004277f554000417cea349d69f18655e95Dan Stoza } 495d31824004277f554000417cea349d69f18655e95Dan Stoza if (merge) { 496d31824004277f554000417cea349d69f18655e95Dan Stoza const int bottom = span[0].bottom; 497d31824004277f554000417cea349d69f18655e95Dan Stoza Rect* r = head; 498d31824004277f554000417cea349d69f18655e95Dan Stoza while (r != tail) { 499d31824004277f554000417cea349d69f18655e95Dan Stoza r->bottom = bottom; 500d31824004277f554000417cea349d69f18655e95Dan Stoza r++; 50120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 502d31824004277f554000417cea349d69f18655e95Dan Stoza } else { 503d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.left = min(span.itemAt(0).left, bounds.left); 504d31824004277f554000417cea349d69f18655e95Dan Stoza bounds.right = max(span.top().right, bounds.right); 505d31824004277f554000417cea349d69f18655e95Dan Stoza storage.appendVector(span); 506d31824004277f554000417cea349d69f18655e95Dan Stoza tail = storage.editArray() + storage.size(); 507d31824004277f554000417cea349d69f18655e95Dan Stoza head = tail - span.size(); 50820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 509d31824004277f554000417cea349d69f18655e95Dan Stoza span.clear(); 510d31824004277f554000417cea349d69f18655e95Dan Stoza} 51120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 512068d47f29dfead847999a7b33b4217ee9514152bMathias Agopianbool Region::validate(const Region& reg, const char* name, bool silent) 513edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 51420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian bool result = true; 51520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator cur = reg.begin(); 51620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator const tail = reg.end(); 517068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian const_iterator prev = cur; 51820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect b(*prev); 51920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (cur != tail) { 520068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (cur->isValid() == false) { 521068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: region contains an invalid Rect", name); 522068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 523068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 524068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (cur->right > region_operator<Rect>::max_value) { 525068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: rect->right > max_value", name); 526068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 527068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 528068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (cur->bottom > region_operator<Rect>::max_value) { 529068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: rect->right > max_value", name); 530068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 531068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 532068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (prev != cur) { 533068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian b.left = b.left < cur->left ? b.left : cur->left; 534068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian b.top = b.top < cur->top ? b.top : cur->top; 535068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian b.right = b.right > cur->right ? b.right : cur->right; 536068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom; 537068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if ((*prev < *cur) == false) { 538068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: region's Rects not sorted", name); 53920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian result = false; 540068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 541068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (cur->top == prev->top) { 542068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (cur->bottom != prev->bottom) { 543068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: invalid span %p", name, cur); 544068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 545068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } else if (cur->left < prev->right) { 546068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, 547068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian "%s: spans overlap horizontally prev=%p, cur=%p", 548068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian name, prev, cur); 549068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 550068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 551068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } else if (cur->top < prev->bottom) { 552068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, 553068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian "%s: spans overlap vertically prev=%p, cur=%p", 55420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian name, prev, cur); 55520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian result = false; 55620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 557068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian prev = cur; 55820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 55920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian cur++; 56020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 56120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if (b != reg.getBounds()) { 56220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian result = false; 563068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, 564068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian "%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name, 56520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian b.left, b.top, b.right, b.bottom, 56620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian reg.getBounds().left, reg.getBounds().top, 56720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian reg.getBounds().right, reg.getBounds().bottom); 56820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 5693ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian if (reg.mStorage.size() == 2) { 570068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian result = false; 571068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE_IF(!silent, "%s: mStorage size is 2, which is never valid", name); 5723ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian } 573068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (result == false && !silent) { 57420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian reg.dump(name); 575cab25d680e644d962041d05a319e485b96136a5dMathias Agopian CallStack stack(LOG_TAG); 57620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 57720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return result; 578edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 579edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 58020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::boolean_operation(int op, Region& dst, 58120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Region& lhs, 58220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Region& rhs, int dx, int dy) 583edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 584d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian#if VALIDATE_REGIONS 585d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(lhs, "boolean_operation (before): lhs"); 586d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(rhs, "boolean_operation (before): rhs"); 587d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian validate(dst, "boolean_operation (before): dst"); 588d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian#endif 589d0b55c011a311b677493ba72804bf1bc4df68224Mathias Agopian 59020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian size_t lhs_count; 59120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect const * const lhs_rects = lhs.getArray(&lhs_count); 59220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 59320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian size_t rhs_count; 59420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect const * const rhs_rects = rhs.getArray(&rhs_count); 59520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 59620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 59720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy); 59820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect> operation(op, lhs_region, rhs_region); 59920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian { // scope for rasterizer (dtor has side effects) 60020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rasterizer r(dst); 60120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian operation(r); 60220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 60320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 60420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_REGIONS 60520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian validate(lhs, "boolean_operation: lhs"); 60620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian validate(rhs, "boolean_operation: rhs"); 60720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian validate(dst, "boolean_operation: dst"); 60820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 60920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 61020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_WITH_CORECG 61120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion sk_lhs; 61220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion sk_rhs; 61320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion sk_dst; 61420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 61520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian for (size_t i=0 ; i<lhs_count ; i++) 61620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian sk_lhs.op( 61720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian lhs_rects[i].left + dx, 61820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian lhs_rects[i].top + dy, 61920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian lhs_rects[i].right + dx, 62020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian lhs_rects[i].bottom + dy, 62120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion::kUnion_Op); 62220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 62320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian for (size_t i=0 ; i<rhs_count ; i++) 62420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian sk_rhs.op( 62520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rhs_rects[i].left + dx, 62620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rhs_rects[i].top + dy, 62720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rhs_rects[i].right + dx, 62820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rhs_rects[i].bottom + dy, 62920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion::kUnion_Op); 63020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 63120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const char* name = "---"; 63220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion::Op sk_op; 63320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian switch (op) { 63420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break; 635b8a2e98cd7edbe7513543670c94f6b5efa74462fRomain Guy case op_xor: sk_op = SkRegion::kUnion_XOR; name="XOR"; break; 63620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break; 63720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break; 63820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 63920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian sk_dst.op(sk_lhs, sk_rhs, sk_op); 64020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 64120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if (sk_dst.isEmpty() && dst.isEmpty()) 64220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian return; 64320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 64420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian bool same = true; 64520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Region::const_iterator head = dst.begin(); 64620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Region::const_iterator const tail = dst.end(); 64720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion::Iterator it(sk_dst); 64820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (!it.done()) { 64920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if (head != tail) { 65020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if ( 65120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head->left != it.rect().fLeft || 65220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head->top != it.rect().fTop || 65320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head->right != it.rect().fRight || 65420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head->bottom != it.rect().fBottom 65520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian ) { 65620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian same = false; 65720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian break; 65820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 65920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } else { 66020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian same = false; 66120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian break; 66220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 66320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head++; 66420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.next(); 66520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 66620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 66720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if (head != tail) { 66820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian same = false; 66920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 67020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 67120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian if(!same) { 6729d4536835248525f32f1504a3d28d5bbfa0a2910Steve Block ALOGD("---\nregion boolean %s failed", name); 67320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian lhs.dump("lhs"); 67420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rhs.dump("rhs"); 67520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian dst.dump("dst"); 6769d4536835248525f32f1504a3d28d5bbfa0a2910Steve Block ALOGD("should be"); 67720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian SkRegion::Iterator it(sk_dst); 67820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (!it.done()) { 6799d4536835248525f32f1504a3d28d5bbfa0a2910Steve Block ALOGD(" [%3d, %3d, %3d, %3d]", 68020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.rect().fLeft, 68120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.rect().fTop, 68220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.rect().fRight, 68320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.rect().fBottom); 68420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian it.next(); 68520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 68620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 68720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 688edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 689edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 69020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::boolean_operation(int op, Region& dst, 69120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Region& lhs, 69220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Rect& rhs, int dx, int dy) 69320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 6940450452e8c6ea48341d57d8bc51d56252e9806b8Mathias Agopian if (!rhs.isValid()) { 695e6f43ddce78d6846af12550ff9193c5c6fe5844bSteve Block ALOGE("Region::boolean_operation(op=%d) invalid Rect={%d,%d,%d,%d}", 6960450452e8c6ea48341d57d8bc51d56252e9806b8Mathias Agopian op, rhs.left, rhs.top, rhs.right, rhs.bottom); 6970857c8f7f1905008b285a5473c906639fdd0288bMathias Agopian return; 6980450452e8c6ea48341d57d8bc51d56252e9806b8Mathias Agopian } 6990450452e8c6ea48341d57d8bc51d56252e9806b8Mathias Agopian 70020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS 70120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, dst, lhs, Region(rhs), dx, dy); 70220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#else 70320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian size_t lhs_count; 70420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect const * const lhs_rects = lhs.getArray(&lhs_count); 70520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 70620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 70720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy); 70820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian region_operator<Rect> operation(op, lhs_region, rhs_region); 70920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian { // scope for rasterizer (dtor has side effects) 71020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rasterizer r(dst); 71120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian operation(r); 71220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 713edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 71420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 71520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 71620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 71720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::boolean_operation(int op, Region& dst, 71820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Region& lhs, const Region& rhs) 71920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 72020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, dst, lhs, rhs, 0, 0); 72120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 72220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 72320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::boolean_operation(int op, Region& dst, 72420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const Region& lhs, const Rect& rhs) 72520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 72620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian boolean_operation(op, dst, lhs, rhs, 0, 0); 72720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 72820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 72920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::translate(Region& reg, int dx, int dy) 73020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 7314c0a170585d5c8a1f3508ac55f799ebaf86e91dbMathias Agopian if ((dx || dy) && !reg.isEmpty()) { 73220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_REGIONS 73320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian validate(reg, "translate (before)"); 73420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 73520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian size_t count = reg.mStorage.size(); 73620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian Rect* rects = reg.mStorage.editArray(); 73720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (count) { 7386c7f25afb75ac155bad0b3bc17c0089d0337d060Mathias Agopian rects->offsetBy(dx, dy); 73920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian rects++; 74020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian count--; 74120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 74220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#if VALIDATE_REGIONS 74320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian validate(reg, "translate (after)"); 74420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian#endif 74520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian } 74620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 74720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 74820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopianvoid Region::translate(Region& dst, const Region& reg, int dx, int dy) 74920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian{ 75020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian dst = reg; 75120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian translate(dst, dx, dy); 75220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 75320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 75420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 755edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 756e142428a9c8b9d2380032cd4d7b55ee440fe8770Mathias Agopiansize_t Region::getFlattenedSize() const { 7576fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza return sizeof(uint32_t) + mStorage.size() * sizeof(Rect); 758edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 759edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 760e142428a9c8b9d2380032cd4d7b55ee440fe8770Mathias Agopianstatus_t Region::flatten(void* buffer, size_t size) const { 761068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian#if VALIDATE_REGIONS 762068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian validate(*this, "Region::flatten"); 763068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian#endif 7646fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza if (size < getFlattenedSize()) { 765e142428a9c8b9d2380032cd4d7b55ee440fe8770Mathias Agopian return NO_MEMORY; 766e142428a9c8b9d2380032cd4d7b55ee440fe8770Mathias Agopian } 7676fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza // Cast to uint32_t since the size of a size_t can vary between 32- and 7686fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza // 64-bit processes 7696fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza FlattenableUtils::write(buffer, size, static_cast<uint32_t>(mStorage.size())); 7706fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza for (auto rect : mStorage) { 7716fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza status_t result = rect.flatten(buffer, size); 7726fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza if (result != NO_ERROR) { 7736fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza return result; 7746fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza } 7756fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza FlattenableUtils::advance(buffer, size, sizeof(rect)); 7766fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza } 7778683fca395d01734ec7946e9f0595ec5d7b754c6Mathias Agopian return NO_ERROR; 778edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 779edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 7808683fca395d01734ec7946e9f0595ec5d7b754c6Mathias Agopianstatus_t Region::unflatten(void const* buffer, size_t size) { 7816fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza if (size < sizeof(uint32_t)) { 7826fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza return NO_MEMORY; 7836fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza } 7846fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza 7856fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza uint32_t numRects = 0; 7866fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza FlattenableUtils::read(buffer, size, numRects); 7876fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza if (size < numRects * sizeof(Rect)) { 7886fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza return NO_MEMORY; 7896fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza } 7906fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza 791068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian Region result; 7926fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza result.mStorage.clear(); 7936fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza for (size_t r = 0; r < numRects; ++r) { 7946fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza Rect rect; 7956fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza status_t status = rect.unflatten(buffer, size); 7966fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza if (status != NO_ERROR) { 7976fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza return status; 7988683fca395d01734ec7946e9f0595ec5d7b754c6Mathias Agopian } 7996fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza FlattenableUtils::advance(buffer, size, sizeof(rect)); 8006fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza result.mStorage.push_back(rect); 8018683fca395d01734ec7946e9f0595ec5d7b754c6Mathias Agopian } 8026fbefbbd8edc9953041289fbd77bb18c4964dce5Dan Stoza 8033ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian#if VALIDATE_REGIONS 804068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian validate(result, "Region::unflatten"); 8053ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian#endif 806068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian 807068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian if (!result.validate(result, "Region::unflatten", true)) { 808068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian ALOGE("Region::unflatten() failed, invalid region"); 809068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian return BAD_VALUE; 810068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian } 811068d47f29dfead847999a7b33b4217ee9514152bMathias Agopian mStorage = result.mStorage; 8128683fca395d01734ec7946e9f0595ec5d7b754c6Mathias Agopian return NO_ERROR; 81320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 81420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 81520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 81620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 81720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion::const_iterator Region::begin() const { 8183ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian return mStorage.array(); 81920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 82020f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 82120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRegion::const_iterator Region::end() const { 8223ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian size_t numRects = isRect() ? 1 : mStorage.size() - 1; 8233ab68558fa5a4b8f792a54965a010f03385bd271Mathias Agopian return mStorage.array() + numRects; 82420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian} 82520f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 82620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias AgopianRect const* Region::getArray(size_t* count) const { 827d31824004277f554000417cea349d69f18655e95Dan Stoza if (count) *count = static_cast<size_t>(end() - begin()); 828d31824004277f554000417cea349d69f18655e95Dan Stoza return begin(); 829edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 830edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 8312401ead70099c982796ecc3ec63ec8a5570948fcMathias AgopianSharedBuffer const* Region::getSharedBuffer(size_t* count) const { 8322401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian // We can get to the SharedBuffer of a Vector<Rect> because Rect has 8332401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian // a trivial destructor. 8342401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian SharedBuffer const* sb = SharedBuffer::bufferFromData(mStorage.array()); 8352401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian if (count) { 8362401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian size_t numRects = isRect() ? 1 : mStorage.size() - 1; 8372401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian count[0] = numRects; 8382401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian } 8392401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian sb->acquire(); 8402401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian return sb; 8412401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian} 8422401ead70099c982796ecc3ec63ec8a5570948fcMathias Agopian 84320f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian// ---------------------------------------------------------------------------- 84420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 845d31824004277f554000417cea349d69f18655e95Dan Stozavoid Region::dump(String8& out, const char* what, uint32_t /* flags */) const 846edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 84720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator head = begin(); 84820f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator const tail = end(); 84920f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian 850d31824004277f554000417cea349d69f18655e95Dan Stoza out.appendFormat(" Region %s (this=%p, count=%" PRIdPTR ")\n", 851d31824004277f554000417cea349d69f18655e95Dan Stoza what, this, tail - head); 85220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (head != tail) { 853d31824004277f554000417cea349d69f18655e95Dan Stoza out.appendFormat(" [%3d, %3d, %3d, %3d]\n", head->left, head->top, 854d31824004277f554000417cea349d69f18655e95Dan Stoza head->right, head->bottom); 855d31824004277f554000417cea349d69f18655e95Dan Stoza ++head; 856edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 857edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 858edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 859d31824004277f554000417cea349d69f18655e95Dan Stozavoid Region::dump(const char* what, uint32_t /* flags */) const 860edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 86120f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator head = begin(); 86220f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian const_iterator const tail = end(); 86392dc3fc52cf097bd105460cf377779bdcf146d62Mark Salyzyn ALOGD(" Region %s (this=%p, count=%" PRIdPTR ")\n", what, this, tail-head); 86420f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian while (head != tail) { 8659d4536835248525f32f1504a3d28d5bbfa0a2910Steve Block ALOGD(" [%3d, %3d, %3d, %3d]\n", 86620f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head->left, head->top, head->right, head->bottom); 86720f68782a4ea71c6a977d7f87d8288d3daa265ecMathias Agopian head++; 868edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 869edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 870edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 871edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 872edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 873edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 874