src/core/SkTileGrid.cpp

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkTileGrid.h"

SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info)
    : fXTiles(xTiles)
    , fYTiles(yTiles)
    , fInvWidth( SkScalarInvert(info.fTileInterval.width()))
    , fInvHeight(SkScalarInvert(info.fTileInterval.height()))
    , fMarginWidth (info.fMargin.fWidth +1)  // Margin is offset by 1 as a provision for AA and
    , fMarginHeight(info.fMargin.fHeight+1)  // to cancel the outset applied by getClipDeviceBounds.
    , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY))
    , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(),
                                 yTiles * info.fTileInterval.height()))
    , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {}

SkTileGrid::~SkTileGrid() {
    SkDELETE_ARRAY(fTiles);
}

// Adjustments to user-provided bounds common to both insert() and search().
// Call this after making insert- or search- specific adjustments.
void SkTileGrid::commonAdjust(SkRect* rect) const {
    // Apply our offset.
    rect->offset(fOffset);

    // Scrunch the bounds in just a little to make the right and bottom edges
    // exclusive.  We want bounds of exactly one tile to hit exactly one tile.
    rect->fRight  -= SK_ScalarNearlyZero;
    rect->fBottom -= SK_ScalarNearlyZero;
}

// Convert user-space bounds to grid tiles they cover (LT inclusive, RB exclusive).
void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const {
    grid->fLeft   = SkPin32(user.left()   * fInvWidth , 0, fXTiles - 1);
    grid->fTop    = SkPin32(user.top()    * fInvHeight, 0, fYTiles - 1);
    grid->fRight  = SkPin32(user.right()  * fInvWidth , 0, fXTiles - 1) + 1;
    grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1) + 1;
}

void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) {
    SkRect bounds = originalBounds;
    bounds.outset(fMarginWidth, fMarginHeight);
    this->commonAdjust(&bounds);

    // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
    // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
    if (!SkRect::Intersects(bounds, fGridBounds)) {
        return;
    }

    SkIRect grid;
    this->userToGrid(bounds, &grid);

    for (int y = grid.fTop; y < grid.fBottom; y++) {
        for (int x = grid.fLeft; x < grid.fRight; x++) {
            fTiles[y * fXTiles + x].push(opIndex);
        }
    }
}

// Number of tiles for which data is allocated on the stack in
// SkTileGrid::search. If malloc becomes a bottleneck, we may consider
// increasing this number. Typical large web page, say 2k x 16k, would
// require 512 tiles of size 256 x 256 pixels.
static const int kStackAllocationTileCount = 1024;

void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* results) const {
    // The inset counteracts the outset that applied in 'insert', which optimizes
    // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile grid).
    SkRect query = originalQuery;
    query.inset(fMarginWidth, fMarginHeight);
    this->commonAdjust(&query);

    // The inset may have inverted the rectangle, so sort().
    // TODO(mtklein): It looks like we only end up with inverted bounds in unit tests
    // that make explicitly inverted queries, not from insetting.  If we can drop support for
    // unsorted bounds (i.e. we don't see them outside unit tests), I think we can drop this.
    query.sort();

    // No intersection check.  We optimize for queries that are in bounds.
    // We're safe anyway: userToGrid() will clamp out-of-bounds queries to nearest tile.
    SkIRect grid;
    this->userToGrid(query, &grid);

    const int tilesHit = (grid.fRight - grid.fLeft) * (grid.fBottom - grid.fTop);
    SkASSERT(tilesHit > 0);

    if (tilesHit == 1) {
        // A performance shortcut.  The merging code below would work fine here too.
        *results = fTiles[grid.fTop * fXTiles + grid.fLeft];
        return;
    }

    // We've got to merge the data in many tiles into a single sorted and deduplicated stream.
    // We do a simple k-way merge based on the value of opIndex.

    // Gather pointers to the starts and ends of the tiles to merge.
    SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit);
    int i = 0;
    for (int y = grid.fTop; y < grid.fBottom; y++) {
        for (int x = grid.fLeft; x < grid.fRight; x++) {
            starts[i] = fTiles[y * fXTiles + x].begin();
            ends[i]   = fTiles[y * fXTiles + x].end();
            i++;
        }
    }

    // Merge tiles into results until they're fully consumed.
    results->reset();
    while (true) {
        // The tiles themselves are already ordered, so the earliest op is at the front of some
        // tile. It may be at the front of several, even all, tiles.
        unsigned earliest = SK_MaxU32;
        for (int i = 0; i < starts.count(); i++) {
            if (starts[i] < ends[i]) {
                earliest = SkTMin(earliest, *starts[i]);
            }
        }

        // If we didn't find an earliest op, there isn't anything left to merge.
        if (SK_MaxU32 == earliest) {
            return;
        }

        // We did find an earliest op. Output it, and step forward every tile that contains it.
        results->push(earliest);
        for (int i = 0; i < starts.count(); i++) {
            if (starts[i] < ends[i] && *starts[i] == earliest) {
                starts[i]++;
            }
        }
    }
}