Repository: flutter
Issue: [Impeller] Optimize draw order to minimize overdraw
Labels: engine,P2,e: impeller,team-engine,triaged-engine

To minimize overdraw (computing pixels that end up getting entirely replaced by subsequent draw calls), we can record a unique depth value for all entities in a pass, draw backdrop-independent entities in reverse order, and then draw backdrop-reliant entities in forward order.

# Backdrop independence vs reliance

Backdrop independent entities are entities that produce draw calls which are unaffected by the backdrop contents.

Examples of draw calls that are backdrop-reliant:
* SourceOver blend mode + translucent source pixels.
* Most other blend modes. For example, kMultiply multiplies the source color with the backdrop color.

Examples of draw calls that are backdrop-independent:
* Source blend mode.
* SourceOver blend mode, but with source pixels known to be opaque.

# Clips

For the draw order optimization to produce correct results, a clip itself must be considered backdrop-reliant if _any_ of the draw calls that occur within it (i.e. the clip's "children") are backdrop-reliant. Meaning, the clip must be be drawn after all of the backdrop-independent entities within its parent clip.

Consider the following sequence of draw calls, which contains a clip with three children:
```
IndependentA() => depth=0, clip=0
Clip() => increment clip height to 1
  IndependentB() => depth=1, clip=1
  ReliantC() => depth=2, clip=1
  IndependentD() => depth=3, clip=1
Restore() => set the clip height to 0
IndependentE() => depth=4, clip=0
```

With draw order optimization applied, these draws should execute in the following order:
```
IndependentE() => depth=4, clip=0
IndependentA() => depth=0, clip=0
Clip() => increment clip height to 1
  IndependentD() => depth=3, clip=1
  IndependentB() => depth=1, clip=1
  ReliantC() => depth=2, clip=1
Restore() => set the clip height to 0
```

This ensures that `ReliantC()` will:
1. Respect the clip
2. have a backdrop that correctly includes both `IndependentA()` and `IndependentB()`, and
3. get properly occluded by `IndependentE()` and `IndependentD()`.

Note that this does reintroduce some possibility of overdraw between backdrop-independent entities drawn before and within the clip. In this case, if `IndependentA()` overlaps with `IndependentD()` or `IndependentB()`, in areas that are not occluded by either the clip or `IndependentE()`, some of the pixels output by `IndependentA()` will be replaced.

# Tracking both the clip and depth in the stencil buffer

We already use a stencil buffer for tracking the clip height. Would it be possible to use e.g. half the bits in the stencil buffer to keep track of the depth?

Yes!

## Drawing regular entities

When performing a regular entity draw call (i.e. not a clip), we need to incorporate both the depth and clip height (lest we draw outside the clip or in the wrong order), and so the stencil read mask must be maxed out.

But, what should the stencil ref and compare op be? Well, since we're respecting both the clip and depth in the check, the ref must encode both, otherwise either the clip or depth won't be respected when deciding to draw or not. Ok, so what about the stencil compare function? Since we're drawing the new depth to the stencil, inequality is necessary -- we must choose either `backdrop > ref` or `backdrop < ref`, otherwise we could end up overdrawing, which will draw backend-independent things in the wrong order due to the reversed draw order. We can control the ordering of both the clip and depth parts, so either option would suffice.
Let's just assume we'll keep our current incremental clipping order (where clips increment the stencil) and choose `backdrop < ref` as the stencil compare, which means that the stencil test passes when the backdrop is less than the ref. This means that greater stencil ref values are less restrictive and more "in front" than smaller ones, which in turn means that the depth must match the original display list draw order (i.e. drawing "after" another object means it draws "on top", and so it gets a larger depth value in order to retain the stencil's ordering).

So in summary, every non-clip entity in the entity pass is assigned a unique depth that increments in the display list draw order. And each entity also gets a clip height (which plays the same role as the stencil height stored today based on the clip stack). These values are combined to produce the correct stencil ref value.
We could technically set the stencil write mask so that we only write the depth part when drawing the entity, but this doesn't actually matter, as the written clip height will always end up matching the height of the clip we're drawing within anyways.

## Drawing clip increments and restores

For clip increments/restores, we need to be careful to not overwrite the depth information for subsequent draws. For this, we can simply set the stencil write mask to only affect the clip part of the stencil when managing the clip.

When incrementing the clip, we need to only do so when the the backdrop matches the current clip height. This allows us to build up our clip height map such that it can be easily restored by flattening any height value greater than the value being restored (compare function: `backdrop > ref`, operation: `replace with ref`).

To accomplish this, the clip draw needs a stencil ref that matches the clip height prior to incrementing; the compare function must be either `backdrop == ref` or `backdrop >= ref`.

Recall that clips (along with their "children" entities) need to be treated like a single "backdrop reliant" entity and drawn after all of the "backdrop independent" entities in the root clip. This means that entities with both a lower depth or higher depth may have already been drawn to the buffer prior to this clip draw.
For all backends, using `backdrop == ref` or `backdrop >= ref` is no problem: We can simply set the stencil read mask to only include the lower bits containing the clip height.