Adding SkTileGrid: a new subclass of BBoxHierarchy, optimized for tiled playback.

Adding SkTileGrid: a new subclass of BBoxHierarchy, optimized for tiled playback.
Committed: https://code.google.com/p/skia/source/detail?r=6314

[reed1, 2012-11-05 18:07:54]

is this just a check-point, or do you have new benches or tests that exercise
this?

https://codereview.appspot.com/6820093/diff/1/include/core/SkTDArray.h
File include/core/SkTDArray.h (right):

https://codereview.appspot.com/6820093/diff/1/include/core/SkTDArray.h#newcod...
include/core/SkTDArray.h:331: 
Why this change? realloc is defined to behave like malloc if the first parameter
is null.

[junov, 2012-11-05 18:22:23]

On 2012/11/05 18:07:54, reed1 wrote:
> is this just a check-point, or do you have new benches or tests that exercise
> this?

Yes, it is a checkpoint.  bench_pictures shows that tileGrid is significantly
faster that rtree for recording and playback conversion in the tiled case.  No
difference was measured as far as raw playback is concerned, but in theory it is
O(1), while rtree is O(log(N)). 
Anyways, bench_picture alone makes the case for this new class.

In follow-up CLs I intend to add:
- unit tests
- bench tests
- new mode in gm (rtree and tilegrid)


> 
> https://codereview.appspot.com/6820093/diff/1/include/core/SkTDArray.h
> File include/core/SkTDArray.h (right):
> 
>
https://codereview.appspot.com/6820093/diff/1/include/core/SkTDArray.h#newcod...
> include/core/SkTDArray.h:331: 
> Why this change? realloc is defined to behave like malloc if the first
parameter
> is null.

Oops. Just something I was testing... will revert.

[Leon, 2012-11-05 18:28:04]

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp
File src/core/SkTileGrid.cpp (right):

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp#newcode21
src/core/SkTileGrid.cpp:21: new (&fTileData[i]) SkTDArray<SkTDArray<void *>>();
SkNEW_PLACEMENT

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp#newcode24
src/core/SkTileGrid.cpp:24: new (&fTileData[i][j]) SkTDArray<void *>();
SkNEW_PLACEMENT

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp#newcode48
src/core/SkTileGrid.cpp:48: if (maxTileX >= fXTileCount) maxTileX = fXTileCount
- 1;
SkMax32

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp#newcode50
src/core/SkTileGrid.cpp:50: if (maxTileX < 0) maxTileX = 0;
SkMin32

https://codereview.appspot.com/6820093/diff/1/src/core/SkTileGrid.cpp#newcode62
src/core/SkTileGrid.cpp:62: SkASSERT(query.width() == fTileWidth + 2 &&
query.height() == fTileHeight + 2);
Should all these assumptions be stated in the header file?

https://codereview.appspot.com/6820093/diff/1/tools/PictureRenderer.cpp
File tools/PictureRenderer.cpp (right):

https://codereview.appspot.com/6820093/diff/1/tools/PictureRenderer.cpp#newco...
tools/PictureRenderer.cpp:591: return SkNEW_ARGS(TileGridPicture, (fGridWidth,
fGridHeight, xTileCount, yTileCount));
100 columns

https://codereview.appspot.com/6820093/diff/1/tools/bench_pictures_main.cpp
File tools/bench_pictures_main.cpp (right):

https://codereview.appspot.com/6820093/diff/1/tools/bench_pictures_main.cpp#n...
tools/bench_pictures_main.cpp:171: int gridWidth = NULL;
Should we set these to zero, since they are not pointers?

https://codereview.appspot.com/6820093/diff/1/tools/bench_pictures_main.cpp#n...
tools/bench_pictures_main.cpp:237: exit(-1);
I added a macro so we make sure to do both:

PRINT_USAGE_AND_EXIT;

https://codereview.appspot.com/6820093/diff/1/tools/bench_pictures_main.cpp#n...
tools/bench_pictures_main.cpp:244: exit(-1);
PRINT_USAGE_AND_EXIT;

https://codereview.appspot.com/6820093/diff/1/tools/bench_pictures_main.cpp#n...
tools/bench_pictures_main.cpp:393: usage(argv0);
PRINT_USAGE_AND_EXIT;

[junov1, 2012-11-05 20:05:14]

Patch

[Leon, 2012-11-05 20:17:38]

lgtm

[reed1, 2012-11-05 20:27:49]

did you mean to revert the change to SkTDArray?

https://codereview.appspot.com/6820093/diff/16/src/core/SkTileGrid.h
File src/core/SkTileGrid.h (right):

https://codereview.appspot.com/6820093/diff/16/src/core/SkTileGrid.h#newcode50
src/core/SkTileGrid.h:50: int fTileWidth, fTileHeight, fXTileCount, fYTileCount;
Not sure we can handle a compound type inside SkTDArray. It is not written to
support assignment or copy-constructor (or destructor) semantics as it resizes
the array.

[junov1, 2012-11-05 20:33:16]

> https://codereview.appspot.com/6820093/diff/16/src/core/SkTileGrid.h#newcode50
> src/core/SkTileGrid.h:50: int fTileWidth, fTileHeight, fXTileCount,
fYTileCount;
> Not sure we can handle a compound type inside SkTDArray. It is not written to
> support assignment or copy-constructor (or destructor) semantics as it resizes
> the array.

The call to setReserve addresses that.  Of the three nested levels of array, the
two first levels have fixed sizes, only the last level grows during recording.

[junov1, 2012-11-05 20:36:16]

Patch 3 reverts SkTDArray.

Also, I could just use a dynamically allocated C-style array for the top 2 array
levels. Since they don't grow anyways, they don't need any of the smarts of
SkTDArray.  I'll do that.

[junov1, 2012-11-05 20:56:26]

Patch!

Got rid of nested SkTDArrays. Result: simpler code, fewer malloc calls.

[reed1, 2012-11-06 18:21:35]

as per chat, lets make it very very clear that this subclass *only* works if the
query rect matches only 1 tile, and is suboptimal if the query is smaller than
one tile.

other than that, lgtm.

I still am hopeful for a robust competitor to rtree (KD tree?) in the future...