17b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 27b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org/* 37b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org * Copyright 2012 Google Inc. 47b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org * 57b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org * Use of this source code is governed by a BSD-style license that can be 67b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org * found in the LICENSE file. 77b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org */ 87b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 97b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org#include "SkTileGrid.h" 107b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 115fb2ce38b3dcb8e60e9e112df23c9d42456d7069commit-bot@chromium.orgSkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info, 125fb2ce38b3dcb8e60e9e112df23c9d42456d7069commit-bot@chromium.org SkTileGridNextDatumFunctionPtr nextDatumFunction) { 137b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fXTileCount = xTileCount; 147b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fYTileCount = yTileCount; 1529b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo = info; 1629b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org // Margin is offset by 1 as a provision for AA and 17f507c410e3a2a7ef7dab84152d836da5e5a8a5e9junov@chromium.org // to cancel-out the outset applied by getClipDeviceBounds. 1829b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo.fMargin.fHeight++; 1929b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo.fMargin.fWidth++; 207b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fTileCount = fXTileCount * fYTileCount; 217b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fInsertionCount = 0; 2229b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount, 2329b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo.fTileInterval.height() * fYTileCount); 243cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org fNextDatumFunction = nextDatumFunction; 257b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount); 267b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 277b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 287b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgSkTileGrid::~SkTileGrid() { 297b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org SkDELETE_ARRAY(fTileData); 307b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 317b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 329f9d5829c29d8934fa0d4d348173d5ae39bed4e9tfarina@chromium.orgint SkTileGrid::tileCount(int x, int y) { 339f9d5829c29d8934fa0d4d348173d5ae39bed4e9tfarina@chromium.org return this->tile(x, y).count(); 349f9d5829c29d8934fa0d4d348173d5ae39bed4e9tfarina@chromium.org} 359f9d5829c29d8934fa0d4d348173d5ae39bed4e9tfarina@chromium.org 367b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgSkTDArray<void *>& SkTileGrid::tile(int x, int y) { 377b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org return fTileData[y * fXTileCount + x]; 387b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 397b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 407b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgvoid SkTileGrid::insert(void* data, const SkIRect& bounds, bool) { 417b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org SkASSERT(!bounds.isEmpty()); 427b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org SkIRect dilatedBounds = bounds; 4329b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height()); 4429b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org dilatedBounds.offset(fInfo.fOffset); 45adc58e4f485a24a3f28587bdcd3b90e5cbd09659junov@chromium.org if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) { 46adc58e4f485a24a3f28587bdcd3b90e5cbd09659junov@chromium.org return; 47adc58e4f485a24a3f28587bdcd3b90e5cbd09659junov@chromium.org } 48adc58e4f485a24a3f28587bdcd3b90e5cbd09659junov@chromium.org 4929b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org // Note: SkIRects are non-inclusive of the right() column and bottom() row, 5029b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org // hence the "-1"s in the computations of maxTileX and maxTileY. 51631cdcb4a6b926b6447f328b81911a4499fb3698skia.committer@gmail.com int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(), 5229b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fXTileCount - 1), 0); 5329b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(), 5429b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fXTileCount - 1), 0); 5529b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(), 5629b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fYTileCount -1), 0); 5729b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(), 5829b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fYTileCount -1), 0); 597b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 607b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org for (int x = minTileX; x <= maxTileX; x++) { 617b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org for (int y = minTileY; y <= maxTileY; y++) { 627b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org this->tile(x, y).push(data); 637b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org } 647b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org } 657b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fInsertionCount++; 667b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 677b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 687b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgvoid SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) { 6929b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org SkIRect adjustedQuery = query; 70ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org // The inset is to counteract the outset that was applied in 'insert' 71ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org // The outset/inset is to optimize for lookups of size 72ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org // 'tileInterval + 2 * margin' that are aligned with the tile grid. 7329b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height()); 7429b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org adjustedQuery.offset(fInfo.fOffset); 75ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org adjustedQuery.sort(); // in case the inset inverted the rectangle 768d84b8f4207b72d0e54af039fcce1a633f0a7c9ajunov@chromium.org // Convert the query rectangle from device coordinates to tile coordinates 778d84b8f4207b72d0e54af039fcce1a633f0a7c9ajunov@chromium.org // by rounding outwards to the nearest tile boundary so that the resulting tile 788d84b8f4207b72d0e54af039fcce1a633f0a7c9ajunov@chromium.org // region includes the query rectangle. (using truncating division to "floor") 7929b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width(); 8029b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) / 8129b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo.fTileInterval.width(); 8229b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height(); 8329b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) / 8429b19e53cfac5af4f9bd5d361436d1097f349a34junov@chromium.org fInfo.fTileInterval.height(); 85ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org 86ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1); 87d5cfdfffc8c63c6f1cceb46a9bcd5c555a7baa28junov@chromium.org tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount); 88ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1); 89d5cfdfffc8c63c6f1cceb46a9bcd5c555a7baa28junov@chromium.org tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount); 903cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org 913cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY); 92ef5b81142600510b89184fd6f69202ecb92be724junov@chromium.org SkASSERT(queryTileCount); 933cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org if (queryTileCount == 1) { 943cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org *results = this->tile(tileStartX, tileStartY); 953cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } else { 963cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org results->reset(); 97ac90d1d0b1a02e3dfdc8780f0a35e0e6855d6ce1commit-bot@chromium.org SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount); 98ac90d1d0b1a02e3dfdc8780f0a35e0e6855d6ce1commit-bot@chromium.org SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount); 99d4a1567c179311a457283185a65f7a8aeb8fef80junov@chromium.org SkTDArray<void *>** tileRange = storage.get(); 1003cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org int tile = 0; 1013cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org for (int x = tileStartX; x < tileEndX; ++x) { 1023cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org for (int y = tileStartY; y < tileEndY; ++y) { 1033cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org tileRange[tile] = &this->tile(x, y); 1043cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished; 1053cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org ++tile; 1063cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } 1073cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } 1083cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org void *nextElement; 1093cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) { 1103cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org results->push(nextElement); 1113cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } 1123cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } 1137b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 1147b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 1157b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgvoid SkTileGrid::clear() { 1167b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org for (int i = 0; i < fTileCount; i++) { 1177b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org fTileData[i].reset(); 1187b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org } 1197b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org} 1207b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org 1217b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.orgint SkTileGrid::getCount() const { 1227b53706a7d596a2d8dce6cfe5b543264e5a37239junov@chromium.org return fInsertionCount; 12361b05dcc7ebe48663c3ba84b7bd7449d6c887ac1skia.committer@gmail.com} 1244b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 1254b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.orgvoid SkTileGrid::rewindInserts() { 1264b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org SkASSERT(fClient); 1274b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org for (int i = 0; i < fTileCount; ++i) { 1284b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) { 1294b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org fTileData[i].pop(); 1304b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org } 1314b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org } 1324b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org} 133