Culling API

Culling API

*** SKP format breaking change ***

Adding a couple of culling primitives: pushCull(SkRect) & popCull().

These are currently only plumbed for SKP playback quickreject.

At record time, we perform a couple of optimizations to trim down the
number of redundant culls:

  * collapse empty pushCull/popCull pairs
  * skip pushCull/popCull pairs nested within an identical cull rect

Things still missing/to consider:

  * use an inlineable, simplified quickreject (Mike's old prototype)
  * debugger visualization for cull boxes
  * BBH integration: the initial prototype had some minimal BBH support,
    but since the optimizations required expensive rewinds and culling
    is expected to be a BBH alternative, it got dropped.

R=reed@google.com,robertphillips@google.com,bsalomon@google.com

Committed: http://code.google.com/p/skia/source/detail?r=13611

[reed1, 2014-02-14 14:39:05]

public api lgtm -- not reviewed impl per-se

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h#...
include/core/SkCanvas.h:914: }
I wonder if we'll want similar helpers to what save/restore offers...

int pushCull returns its count
popCullToCount(int count) -- to pop all the way back to a specific count

Not asking for it, but just noticing

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h#...
include/core/SkCanvas.h:1091: unsigned    fCullCount;         // number of
active culls
nit: int so we can notice negatives easier, and to match other counters

[caryclark, 2014-02-14 14:54:34]

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h#...
include/core/SkCanvas.h:910: if (fCullCount > 0) {
since you have the assert, do you also need the test?
(I assume that we're not trying to make Skia fault-resistant, but maybe I assume
incorrectly)

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
File src/core/SkPicturePlayback.cpp (right):

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
src/core/SkPicturePlayback.cpp:711: unsigned opCount = 0;
nit : this is fine, but seeing unsigned instead of int makes me think that
there's something more tricky going on, not just that it is counting positive
integers.

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
src/core/SkPicturePlayback.cpp:878: // FIXME: use inlineable
quickRejectNoCheck()
is there a bug associated with this FIXME?

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPictureRecord...
src/core/SkPictureRecord.h:119: SkTDArray<uint32_t> fCullOffsetStack;
Since the restore offset stack is int and the cull offset stack is uint, I'm
going to assume that they use their offsets differently.

[f(malita), 2014-02-20 02:37:26]

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h#...
include/core/SkCanvas.h:910: if (fCullCount > 0) {
On 2014/02/14 14:54:35, caryclark wrote:
> since you have the assert, do you also need the test?
> (I assume that we're not trying to make Skia fault-resistant, but maybe I
assume
> incorrectly)

We guard against underflow for restore(), so I figured we should do the same
here. OTOH underflow is a client error, maybe there's value in signaling the
condition for debug builds?

It does seem inconsistent though, so I should probably remove the assert.

https://codereview.chromium.org/138013009/diff/70001/include/core/SkCanvas.h#...
include/core/SkCanvas.h:1091: unsigned    fCullCount;         // number of
active culls
On 2014/02/14 14:39:06, reed1 wrote:
> nit: int so we can notice negatives easier, and to match other counters

Will do.

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
File src/core/SkPicturePlayback.cpp (right):

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
src/core/SkPicturePlayback.cpp:711: unsigned opCount = 0;
On 2014/02/14 14:54:35, caryclark wrote:
> nit : this is fine, but seeing unsigned instead of int makes me think that
> there's something more tricky going on, not just that it is counting positive
> integers.

Will update.

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPicturePlayba...
src/core/SkPicturePlayback.cpp:878: // FIXME: use inlineable
quickRejectNoCheck()
On 2014/02/14 14:54:35, caryclark wrote:
> is there a bug associated with this FIXME?

Not yet. I recall that at some point quickReject() was showing up in the
profile, and Mike put up a CL for prototyping - but it's quite intrusive and I
don't think we've measured the actual benefit.

So maybe it's better to drop the fixme and revisit when/if this turns out to be
a problem.

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPictureRecord.h
File src/core/SkPictureRecord.h (right):

https://codereview.chromium.org/138013009/diff/70001/src/core/SkPictureRecord...
src/core/SkPictureRecord.h:119: SkTDArray<uint32_t> fCullOffsetStack;
On 2014/02/14 14:54:35, caryclark wrote:
> Since the restore offset stack is int and the cull offset stack is uint, I'm
> going to assume that they use their offsets differently.

Indeed: we store negative values in fRestoreOffsetStack (-offset) to distinguish
between save and clip skip offsets, whereas fCullOffsetStack only stores
actual/positive offsets.

[f(malita), 2014-02-24 20:34:52]

Bump.

[reed1, 2014-02-24 21:21:56]

robert/cary/brian -- speak now or forever ... have to change the impl yourself
:)

[caryclark, 2014-02-24 21:31:09]

lgtm

[bsalomon, 2014-02-24 21:53:25]

On 2014/02/24 21:31:09, caryclark wrote:
> lgtm

lgtm

[tomhudson, 2014-02-25 13:27:15]

I'm probably missing something deep - why is SkPictureRecord::fCullOffsetStack
only defined #ifndef SK_COLLAPSE_MATRIX_CLIP_STATE?

The actual function code doesn't seem to be guarded; I'm surprised this
compiles?

[f(malita), 2014-02-25 13:52:36]

On 2014/02/25 13:27:15, tomhudson wrote:
> I'm probably missing something deep - why is SkPictureRecord::fCullOffsetStack
> only defined #ifndef SK_COLLAPSE_MATRIX_CLIP_STATE?

Ah, probably an auto merge issue - SK_COLLAPSE_MATRIX_CLIP_STATE was added
recently.

> The actual function code doesn't seem to be guarded; I'm surprised this
> compiles?

It only compiles because SK_COLLAPSE_MATRIX_CLIP_STATE is off currently. But
good catch, we do need to fix the other case.

[robertphillips, 2014-02-25 15:58:40]

https://codereview.chromium.org/138013009/diff/380001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/380001/include/core/SkCanvas.h...
include/core/SkCanvas.h:944: void pushCull(const SkRect& cullRect) {
++fCullCount?

https://codereview.chromium.org/138013009/diff/380001/include/core/SkCanvas.h...
include/core/SkCanvas.h:952: void popCull() {
Maybe and "SkASSERT(fCullCount > 0);" to assist debugging?

https://codereview.chromium.org/138013009/diff/380001/include/core/SkCanvas.h...
include/core/SkCanvas.h:953: if (fCullCount > 0) {
--fCullCount?

https://codereview.chromium.org/138013009/diff/380001/include/utils/SkDumpCan...
File include/utils/SkDumpCanvas.h (right):

https://codereview.chromium.org/138013009/diff/380001/include/utils/SkDumpCan...
include/utils/SkDumpCanvas.h:36: kClip_Verb,
Will this mess up the ordering anywhere else (esp. in the skp)?

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureFlat.h
File src/core/SkPictureFlat.h (right):

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureFlat....
src/core/SkPictureFlat.h:29: CLIP_RRECT,
Move to end so old skps will remain valid?!

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPicturePlayb...
File src/core/SkPicturePlayback.cpp (right):

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPicturePlayb...
src/core/SkPicturePlayback.cpp:876: const SkRect& cullRect =
reader.skipT<SkRect>();
offsetToRestore to match other sites?

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPicturePlayb...
src/core/SkPicturePlayback.cpp:1151: skipPath.fCount, skipRegion.fCount,
skipCull.fCount);
Draw ops -> Total ops?

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
File src/core/SkPictureRecord.cpp (right):

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:78: 0,  // CLIP_RRECT - no paint
move to match other moves?

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:1555: void SkPictureRecord::onPushCull(const
SkRect& cullRect) {
Don't we also want to assert that the current cull rect is contained inside the
cull rect on the top of the stack (if there is one)?

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:1570: 
this->

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:1572:
fCullOffsetStack.push(fWriter.bytesWritten());
this->

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:1590: SkASSERT(fWriter.bytesWritten() >=
kPushCullOpSize);
can we have a peek_op static function for this?

https://codereview.chromium.org/138013009/diff/380001/src/utils/debugger/SkDr...
File src/utils/debugger/SkDrawCommand.cpp (right):

https://codereview.chromium.org/138013009/diff/380001/src/utils/debugger/SkDr...
src/utils/debugger/SkDrawCommand.cpp:35: case CLIP_RRECT: return "Clip RRect";
order?

[f(malita), 2014-02-25 16:50:28]

https://codereview.chromium.org/138013009/diff/380001/include/utils/SkDumpCan...
File include/utils/SkDumpCanvas.h (right):

https://codereview.chromium.org/138013009/diff/380001/include/utils/SkDumpCan...
include/utils/SkDumpCanvas.h:36: kClip_Verb,
On 2014/02/25 15:58:41, robertphillips wrote:
> Will this mess up the ordering anywhere else (esp. in the skp)?

This enum is only used in SkDumpCanvas, so I don't think it interferes with
anything else. Will reorder for consistency though.

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureFlat.h
File src/core/SkPictureFlat.h (right):

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureFlat....
src/core/SkPictureFlat.h:29: CLIP_RRECT,
On 2014/02/25 15:58:41, robertphillips wrote:
> Move to end so old skps will remain valid?!

Will do.

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
File src/core/SkPictureRecord.cpp (right):

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:78: 0,  // CLIP_RRECT - no paint
On 2014/02/25 15:58:41, robertphillips wrote:
> move to match other moves?

Will do.

https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
src/core/SkPictureRecord.cpp:1555: void SkPictureRecord::onPushCull(const
SkRect& cullRect) {
On 2014/02/25 15:58:41, robertphillips wrote:
> Don't we also want to assert that the current cull rect is contained inside
the
> cull rect on the top of the stack (if there is one)?

At a high level it surely makes sense (and my initial thought was to do exactly
that), but it comes at a cost: either the client (blink) or the API will need to
keep a cull rect stack and intersect against its top.

Here's a common Blink pattern (think ads or pictures strip): one small-size
clipping div with a whole bunch of children, only a few of them visible at a
time. The parent div pushes its cull bounds, but then its children are
blissfully unaware of their parent clipping and would naturally push culls
outside their parent's.

Options:

1) Blink tracks cull rects and only pushes the intersection
2) Skia tracks cull rects and always intersects against the last one
3) do nothing and allow overflowing culls - the end result (as far as playback
skipping is concerned) is still correct, but maybe there are other implications
down the line where this would cause issues

What do you guys think?

I guess we can attain #2 with minimal overhead in SkPictureRecord::onPushCull
(we are tracking cull rects for optimizations, etc), but that wouldn't help with
an assert in the non-virtual entry point.

https://codereview.chromium.org/138013009/diff/380001/src/utils/debugger/SkDr...
File src/utils/debugger/SkDrawCommand.cpp (right):

https://codereview.chromium.org/138013009/diff/380001/src/utils/debugger/SkDr...
src/utils/debugger/SkDrawCommand.cpp:35: case CLIP_RRECT: return "Clip RRect";
On 2014/02/25 15:58:41, robertphillips wrote:
> order?

Will do.

[iancottrell, 2014-02-26 10:36:06]

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h...
include/core/SkCanvas.h:943: */
Forgive me if I am misunderstanding something, I am still learning the ways of
Skia.
It seems to me like this is the wrong contract to offer. If all we are doing is
promising all nested draw calls are fully contained, why are we not just working
out the box automatically.
If instead we are adding a clipping stack, I can see that being a big win, but
if so this comment is not quite right.
Also, if we are adding a clipping stack, why not go all the way and treat it as
such, keep track of the current clip box, do intersecting test with clips as the
get pushed, and then use the extra information you get (results that don't
change the clip are redundant, results of zero size can drop all nested writes
etc)
You can even do this right down to the draw operation clips.

[tomhudson, 2014-02-26 10:36:32]

From the patch description:

* use an inlineable, simplified quickreject (Mike's old prototype)

What about Justin's old prototype (possibly
https://codereview.chromium.org/12545009/?) of culling bounds that were written
into the SkPicture, which Manfred profiled and found wanting? Do we have some
understanding of what failed there and how this approach will do better?

[robertphillips, 2014-02-26 13:52:01]

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h...
include/core/SkCanvas.h:943: */
This is more of a contract on the caller's side. With this call they are
promising not to draw outside of the provided box (or accept the consequences if
they do). The motivation here is that it can be somewhat expensive to determine
the bounds for a given chunk of text. Blink already has that information so it
can just hand it to us via this interface. We can then use the cull box
information with the existing clip information to eliminate draw calls.

[f(malita), 2014-02-26 14:23:54]

On 2014/02/26 10:36:32, tomhudson wrote:
> What about Justin's old prototype (possibly
> https://codereview.chromium.org/12545009/?) of culling bounds that were
written
> into the SkPicture, which Manfred profiled and found wanting? Do we have some
> understanding of what failed there and how this approach will do better?

The main difference (from a quick glance at that cl) is that instead of
recording bounds for individual draw commands, the current approach allows the
caller to choose an optimal grouping/nesting strategy. The idea being that Blink
already has *hierarchical* bounding box information, which (if communicated
effectively) would enable Skia to skip draw commands for whole Blink *subtrees*.

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/420001/include/core/SkCanvas.h...
include/core/SkCanvas.h:943: */
On 2014/02/26 10:36:07, iancottrell wrote:
> Forgive me if I am misunderstanding something, I am still learning the ways of
> Skia.
> It seems to me like this is the wrong contract to offer. If all we are doing
is
> promising all nested draw calls are fully contained, why are we not just
working
> out the box automatically.

We are currently quick-rejecting individual draw ops, but this offers the
opportunity of (hierarchical) *grouping* and quick-rejecting much larger chunks
at a time - which is critical in tiled playback mode.

You can think of it as an alternative to the bbox hierarchy built by tile
grid/r-tree/q-tree recorders, with bounds information coming directly from Blink
instead being recomputed at record time (which is expensive since it requires
re-measuring each op - particularly text, as Robert mentioned).


> If instead we are adding a clipping stack, I can see that being a big win, but
> if so this comment is not quite right.

Clipping would be just as useful for quick-reject purposes, but much more
expensive (maintaining the raster clip up to date, and also for the GPU IIRC).

This is just a cheap way for clients to assert content bounds that Skia can then
use for playback optimizations.

Does that make sense/answer your question?

[bsalomon, 2014-02-26 14:27:31]

On 2014/02/26 14:23:54, Florin Malita wrote:

> > If instead we are adding a clipping stack, I can see that being a big win,
but
> > if so this comment is not quite right.
> 
> Clipping would be just as useful for quick-reject purposes, but much more
> expensive (maintaining the raster clip up to date, and also for the GPU IIRC).
> 

Yes, when the clip is of a type that has a cheap contains test the cull rects
allow us to ignore the clip for individual draws or write the clip out of the
skp entirely if the all the draw calls through the clip are contained.

[f(malita), 2014-02-26 15:03:50]

On 2014/02/25 16:50:28, Florin Malita wrote:
>
https://codereview.chromium.org/138013009/diff/380001/src/core/SkPictureRecor...
> src/core/SkPictureRecord.cpp:1555: void SkPictureRecord::onPushCull(const
> SkRect& cullRect) {
> On 2014/02/25 15:58:41, robertphillips wrote:
> > Don't we also want to assert that the current cull rect is contained inside
> the
> > cull rect on the top of the stack (if there is one)?
> 
> At a high level it surely makes sense (and my initial thought was to do
exactly
> that), but it comes at a cost: either the client (blink) or the API will need
to
> keep a cull rect stack and intersect against its top.
> 
> Here's a common Blink pattern (think ads or pictures strip): one small-size
> clipping div with a whole bunch of children, only a few of them visible at a
> time. The parent div pushes its cull bounds, but then its children are
> blissfully unaware of their parent clipping and would naturally push culls
> outside their parent's.
> 
> Options:
> 
> 1) Blink tracks cull rects and only pushes the intersection
> 2) Skia tracks cull rects and always intersects against the last one
> 3) do nothing and allow overflowing culls - the end result (as far as playback
> skipping is concerned) is still correct, but maybe there are other
implications
> down the line where this would cause issues
> 
> What do you guys think?

Circling back to this question.

After chatting with Mike yesterday, it seems the root of the problem is Blink
conflating clipping/culling information when the two primitives have different
contracts in Skia. Stated differently: the bounding box information cached and
easily accessible in Blink takes clips into account.

For example:

<div id="div1" style="width: 100px; height: 100px; overflow: hidden;">
  <div id="div2" style="width: 500px; height: 50px;>...</div>
<div>

Because overflow:hidden triggers an implicit clip, div1's bounds (as computed by
RenderBox::overflowRectForPaintRejection/RenderBox::visualOverflowRect) are [0 0
100 100]. If we are to simply pass these as culls, we end up with

pushCull([0 0 100 100])
  pushCull([0 0 500 50])
    ...
  popCull()
popCull()

which breaks the nested culls assertion. This is easily solvable locally (we can
skip pushing div1's cull since it is also going to actually *clip*), but not
globally: we could also have a div0 (wrapping div1) with overflow:visible, for
which Blink computes [0 0 100 100] bounds even though the node itself is not
clipped.

But this is a client issue, so we should probably go ahead and add the assert in
Skia.

To make this work in Blink I'm thinking:

* always intersect with the parent cull before passing down to Skia (short term)
* teach the render tree about unclipped bounds (speculative/long term)

[robertphillips, 2014-02-27 14:12:36]

lgtm + a comment suggestion & nits

https://codereview.chromium.org/138013009/diff/440001/include/core/SkCanvas.h
File include/core/SkCanvas.h (right):

https://codereview.chromium.org/138013009/diff/440001/include/core/SkCanvas.h...
include/core/SkCanvas.h:938: /**
Maybe "With this call the client asserts ..." to emphasize that it is a client
side contract?

https://codereview.chromium.org/138013009/diff/440001/src/utils/debugger/SkDe...
File src/utils/debugger/SkDebugCanvas.cpp (right):

https://codereview.chromium.org/138013009/diff/440001/src/utils/debugger/SkDe...
src/utils/debugger/SkDebugCanvas.cpp:433: void SkDebugCanvas::onPushCull(const
SkRect& cullRect) {
this->

https://codereview.chromium.org/138013009/diff/440001/src/utils/debugger/SkDe...
src/utils/debugger/SkDebugCanvas.cpp:437: void SkDebugCanvas::onPopCull() {
this->

[f(malita), 2014-02-27 16:45:15]

The CQ bit was checked by fmalita@chromium.org

[commit-bot: I haz the power, 2014-02-27 16:45:17]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/fmalita@chromium.org/138013009/460001

[commit-bot: I haz the power, 2014-02-27 17:40:18]

Change committed as 13611