3 * Copyright 2012 Google Inc.
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
9 #include "SkTileGrid.h"
11 SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info,
12 SkTileGridNextDatumFunctionPtr nextDatumFunction) {
13 fXTileCount = xTileCount;
14 fYTileCount = yTileCount;
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;
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);
28 SkTileGrid::~SkTileGrid() {
29 SkDELETE_ARRAY(fTileData);
32 int SkTileGrid::tileCount(int x, int y) {
33 return this->tile(x, y).count();
36 SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
37 return fTileData[y * fXTileCount + x];
40 void 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)) {
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(),
53 int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
55 int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
57 int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
60 for (int x = minTileX; x <= maxTileX; x++) {
61 for (int y = minTileY; y <= maxTileY; y++) {
62 this->tile(x, y).push(data);
68 void 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();
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);
91 int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
92 SkASSERT(queryTileCount);
93 if (queryTileCount == 1) {
94 *results = this->tile(tileStartX, tileStartY);
97 SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount);
98 SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount);
99 SkTDArray<void *>** tileRange = storage.get();
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;
109 while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
110 results->push(nextElement);
115 void SkTileGrid::clear() {
116 for (int i = 0; i < fTileCount; i++) {
117 fTileData[i].reset();
121 int SkTileGrid::getCount() const {
122 return fInsertionCount;
125 void SkTileGrid::rewindInserts() {
127 for (int i = 0; i < fTileCount; ++i) {
128 while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {