1
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "SkTileGrid.h"
10
11SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info,
12                       SkTileGridNextDatumFunctionPtr nextDatumFunction) {
13    fXTileCount = xTileCount;
14    fYTileCount = yTileCount;
15    fInfo = info;
16    // Margin is offset by 1 as a provision for AA and
17    // to cancel-out the outset applied by getClipDeviceBounds.
18    fInfo.fMargin.fHeight++;
19    fInfo.fMargin.fWidth++;
20    fTileCount = fXTileCount * fYTileCount;
21    fInsertionCount = 0;
22    fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount,
23        fInfo.fTileInterval.height() * fYTileCount);
24    fNextDatumFunction = nextDatumFunction;
25    fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
26}
27
28SkTileGrid::~SkTileGrid() {
29    SkDELETE_ARRAY(fTileData);
30}
31
32int SkTileGrid::tileCount(int x, int y) {
33    return this->tile(x, y).count();
34}
35
36SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
37    return fTileData[y * fXTileCount + x];
38}
39
40void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
41    SkASSERT(!bounds.isEmpty());
42    SkIRect dilatedBounds = bounds;
43    dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
44    dilatedBounds.offset(fInfo.fOffset);
45    if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
46        return;
47    }
48
49    // Note: SkIRects are non-inclusive of the right() column and bottom() row,
50    // hence the "-1"s in the computations of maxTileX and maxTileY.
51    int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(),
52        fXTileCount - 1), 0);
53    int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
54        fXTileCount - 1), 0);
55    int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
56        fYTileCount -1), 0);
57    int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
58        fYTileCount -1), 0);
59
60    for (int x = minTileX; x <= maxTileX; x++) {
61        for (int y = minTileY; y <= maxTileY; y++) {
62            this->tile(x, y).push(data);
63        }
64    }
65    fInsertionCount++;
66}
67
68void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
69    SkIRect adjustedQuery = query;
70    // The inset is to counteract the outset that was applied in 'insert'
71    // The outset/inset is to optimize for lookups of size
72    // 'tileInterval + 2 * margin' that are aligned with the tile grid.
73    adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
74    adjustedQuery.offset(fInfo.fOffset);
75    adjustedQuery.sort();  // in case the inset inverted the rectangle
76    // Convert the query rectangle from device coordinates to tile coordinates
77    // by rounding outwards to the nearest tile boundary so that the resulting tile
78    // region includes the query rectangle. (using truncating division to "floor")
79    int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width();
80    int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) /
81        fInfo.fTileInterval.width();
82    int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height();
83    int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) /
84        fInfo.fTileInterval.height();
85
86    tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1);
87    tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount);
88    tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1);
89    tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount);
90
91    int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
92    SkASSERT(queryTileCount);
93    if (queryTileCount == 1) {
94        *results = this->tile(tileStartX, tileStartY);
95    } else {
96        results->reset();
97        SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount);
98        SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount);
99        SkTDArray<void *>** tileRange = storage.get();
100        int tile = 0;
101        for (int x = tileStartX; x < tileEndX; ++x) {
102            for (int y = tileStartY; y < tileEndY; ++y) {
103                tileRange[tile] = &this->tile(x, y);
104                curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
105                ++tile;
106            }
107        }
108        void *nextElement;
109        while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
110            results->push(nextElement);
111        }
112    }
113}
114
115void SkTileGrid::clear() {
116    for (int i = 0; i < fTileCount; i++) {
117        fTileData[i].reset();
118    }
119}
120
121int SkTileGrid::getCount() const {
122    return fInsertionCount;
123}
124
125void SkTileGrid::rewindInserts() {
126    SkASSERT(fClient);
127    for (int i = 0; i < fTileCount; ++i) {
128        while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
129            fTileData[i].pop();
130        }
131    }
132}
133