SkTileGrid.cpp revision f507c410e3a2a7ef7dab84152d836da5e5a8a5e9 
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 tileWidth, int tileHeight, int xTileCount, int yTileCount,
12    int borderPixels, SkTileGridNextDatumFunctionPtr nextDatumFunction)
13{
14    fTileWidth = tileWidth;
15    fTileHeight = tileHeight;
16    fXTileCount = xTileCount;
17    fYTileCount = yTileCount;
18    // Border padding is offset by 1 as a provision for AA and
19    // to cancel-out the outset applied by getClipDeviceBounds.
20    fBorderPixels = borderPixels + 1;
21    fTileCount = fXTileCount * fYTileCount;
22    fInsertionCount = 0;
23    fGridBounds = SkIRect::MakeXYWH(0, 0, fTileWidth * fXTileCount, fTileHeight * fYTileCount);
24    fNextDatumFunction = nextDatumFunction;
25    fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
26}
27
28SkTileGrid::~SkTileGrid() {
29    SkDELETE_ARRAY(fTileData);
30}
31
32SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
33    return fTileData[y * fXTileCount + x];
34}
35
36void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
37    SkASSERT(!bounds.isEmpty());
38    SkIRect dilatedBounds = bounds;
39    dilatedBounds.outset(fBorderPixels, fBorderPixels);
40
41    if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
42        return;
43    }
44
45    int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fTileWidth, fXTileCount - 1), 0);
46    int maxTileX = SkMax32(SkMin32(dilatedBounds.right() / fTileWidth, fXTileCount - 1), 0);
47    int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fTileHeight, fYTileCount -1), 0);
48    int maxTileY = SkMax32(SkMin32(dilatedBounds.bottom() / fTileHeight, fYTileCount -1), 0);
49
50    for (int x = minTileX; x <= maxTileX; x++) {
51        for (int y = minTileY; y <= maxTileY; y++) {
52            this->tile(x, y).push(data);
53        }
54    }
55    fInsertionCount++;
56}
57
58void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
59    int tileStartX = (query.left() + fBorderPixels) / fTileWidth;
60    int tileEndX = (query.right() + fTileWidth - fBorderPixels) / fTileWidth;
61    int tileStartY = (query.top() + fBorderPixels) / fTileHeight;
62    int tileEndY = (query.bottom() + fTileHeight - fBorderPixels) / fTileHeight;
63    if (tileStartX >= fXTileCount || tileStartY >= fYTileCount || tileEndX <= 0 || tileEndY <= 0) {
64        return; // query does not intersect the grid
65    }
66    // clamp to grid
67    if (tileStartX < 0) tileStartX = 0;
68    if (tileStartY < 0) tileStartY = 0;
69    if (tileEndX > fXTileCount) tileEndX = fXTileCount;
70    if (tileEndY > fYTileCount) tileEndY = fYTileCount;
71
72    int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
73    if (queryTileCount == 1) {
74        *results = this->tile(tileStartX, tileStartY);
75    } else {
76        results->reset();
77        SkTDArray<int> curPositions;
78        curPositions.setCount(queryTileCount);
79        // Note: Reserving space for 1024 tile pointers on the stack. If the
80        // malloc becomes a bottleneck, we may consider increasing that number.
81        // Typical large web page, say 2k x 16k, would require 512 tiles of
82        // size 256 x 256 pixels.
83        SkAutoSTArray<1024, SkTDArray<void *>*> storage(queryTileCount);
84        SkTDArray<void *>** tileRange = storage.get();
85        int tile = 0;
86        for (int x = tileStartX; x < tileEndX; ++x) {
87            for (int y = tileStartY; y < tileEndY; ++y) {
88                tileRange[tile] = &this->tile(x, y);
89                curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
90                ++tile;
91            }
92        }
93        void *nextElement;
94        while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
95            results->push(nextElement);
96        }
97    }
98}
99
100void SkTileGrid::clear() {
101    for (int i = 0; i < fTileCount; i++) {
102        fTileData[i].reset();
103    }
104}
105
106int SkTileGrid::getCount() const {
107    return fInsertionCount;
108}
109