Improve PictureLayerTiling::CoverageIterator to handle rounding more precisely

cc/tiles/picture_layer_tiling.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/tiles/picture_layer_tiling.h"
 
 #include <stddef.h>
 
 #include <algorithm>
 #include <cmath>
@@ skipping 382 matching lines @@
       dest_rect_(dest_rect),
       dest_to_content_scale_(0),
       current_tile_(NULL),
       tile_i_(0),
       tile_j_(0),
       left_(0),
       top_(0),
       right_(-1),
       bottom_(-1) {
   DCHECK(tiling_);
+  DCHECK_GE(dest_scale, tiling_->contents_scale_);
+
+  // Clamp dest_rect_ to the bounds of the layer.

[enne (OOO), 2016/09/09 21:46:34]

What code was passing in a larger dest rect than the bounds of the layer? This
is kind of surprising that you couldn't just DCHECK this.

[trchen, 2016/09/09 23:39:19]

I don't know if we ever do that in real code, but
PictureLayerTilingIteratorTest::VerifyTilesCoverNonContainedRect does test that.

Maybe we can make it a DCHECK and update those tests as a separate CL if you
prefer?

[enne (OOO), 2016/09/15 18:06:23]

This is fine.  The code before was intersecting to the tiling size, so I guess
there's nothing different here.

+  gfx::Size dest_content_bounds =
+      gfx::ScaleToCeiledSize(tiling->raster_source_->GetSize(), dest_scale);
+  dest_rect_.Intersect(gfx::Rect(dest_content_bounds));
   if (dest_rect_.IsEmpty())
     return;
 
   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 
-  gfx::Rect content_rect =
-      gfx::ScaleToEnclosingRect(dest_rect_,
-                                dest_to_content_scale_,
-                                dest_to_content_scale_);
-  // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
-  // check for non-intersection first.
-  content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
-  if (content_rect.IsEmpty())
-    return;
+  // Find the indices of the texel samples that enclose the rect we want to
+  // cover.
+  // Without MSAA, the sample point of a texel is at the center of that texel.
+  // For example, texel (12, 34) has sample point at (12.5, 34.5).

[enne (OOO), 2016/09/09 21:46:34]

This isn't true when the layer is not aligned with its target pixels though,
right? I think I don't quite understand how this bit works without knowing the
target transform.

[trchen, 2016/09/09 23:39:19]

It is referring to texels in the texture space. Each texel has a (or more with
MSAA) sample point too.

Because we don't know the target transform at this point, we have to be
pessimistic, i.e. assume every point (a pair of real number, not necessary
snapped to a pixel sample) inside of the content rect may be sampled. This code
basically maps the boundary points into contents space, then find out the
enclosing texture samples.

For example, if we have
dest_scale/content_scale = 1.23 
dest rect = (l=123, t=234, r=345, b=345),
Then the
content_rect = (l=100.00, t=190.24, r=280.49, b=370.73)
So we would need these sample points to guarantee coverage:
wanted_texels(unshifted) = (l=99.5, t=189.5, r=280.5, b=371.5)
Or 
wanted_texels(integer index) = (l=99, t=189, r=280, b=371), note that
bottom&right edges are inclusive.

[enne (OOO), 2016/09/15 18:06:23]

Your description makes sense to me, but I don't feel like the comment reflects
that extra bit of information and is ambiguous in its use of the phrase "sample
point".

I think you could just copy and paste your "Because we don't know..." paragraph
with some additional example.  I think the numeric example above is much more
clear than the "// Instead comment" below.

+  // Instead of trying to snapping to (i+0.5, j+0.5) half grids, just shift
+  // everything by (-0.5, -0.5).
+  gfx::RectF content_rect =
+      gfx::ScaleRect(gfx::RectF(dest_rect_), dest_to_content_scale_);
+  content_rect.Offset(-0.5f, -0.5f);
+  gfx::Rect wanted_texels = gfx::ToEnclosingRect(content_rect);
 
-  left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
-  top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
-  right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
-      content_rect.right() - 1);
-  bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
-      content_rect.bottom() - 1);
+  const TilingData& data = tiling_->tiling_data_;
+  left_ = data.LastBorderTileXIndexFromSrcCoord(wanted_texels.x());
+  top_ = data.LastBorderTileYIndexFromSrcCoord(wanted_texels.y());
+  right_ = std::max(
+      left_, data.FirstBorderTileXIndexFromSrcCoord(wanted_texels.right()));
+  bottom_ = std::max(
+      top_, data.FirstBorderTileYIndexFromSrcCoord(wanted_texels.bottom()));
 
   tile_i_ = left_ - 1;
   tile_j_ = top_;
   ++(*this);
 }
 
 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 }
 
 PictureLayerTiling::CoverageIterator&
 PictureLayerTiling::CoverageIterator::operator++() {
   if (tile_j_ > bottom_)
     return *this;
 
   bool first_time = tile_i_ < left_;
   bool new_row = false;
   tile_i_++;
   if (tile_i_ > right_) {
     tile_i_ = left_;
     tile_j_++;
     new_row = true;
     if (tile_j_ > bottom_) {
       current_tile_ = NULL;
       return *this;
     }
   }
 
   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 
-  // Calculate the current geometry rect.  Due to floating point rounding
-  // and ToEnclosingRect, tiles might overlap in destination space on the
+  // Calculate the current geometry rect. As we reserved 2px overlap between

[enne (OOO), 2016/09/09 21:46:34]

I thought we reserved an extra border texel for bilinear filtering reasons, not
for margin of error?

[trchen, 2016/09/09 23:39:19]

Actually both... I don't know how to word this more concisely & clearly... Any
suggestion?

When I say reserved 2px overlap, I actually mean an overlap of 2 rows/cols of
texel samples.

Overlap of 2 sample points --> overlap of 1px sample extent
Overlap of 1 sample points --> No overlap (tight) sample extent
No overlap --> 1px of gap unsample-able between tiles

And we need to have 1px overlap of sample extent for margin of error (due to
rounding in dest space).

[enne (OOO), 2016/09/15 18:06:23]

Maybe just say "due to border texels and floating point error, tiles might
overlap"

+  // tiles for error margin, tiles might overlap in destination space on the
   // edges.
   gfx::Rect last_geometry_rect = current_geometry_rect_;
 
-  gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
-
-  current_geometry_rect_ =
-      gfx::ScaleToEnclosingRect(content_rect, 1 / dest_to_content_scale_);
+  gfx::RectF texel_extent = tiling_->tiling_data_.TexelExtent(tile_i_, tile_j_);
+  {
+    // Adjust tile extent to accommodate numerical errors.
+    //
+    // For internal edges,  allow the tile to overreach by 1/1024 texels to
+    // avoid seams between tiles. The constant 1/1024 is picked by the fact

[enne (OOO), 2016/09/09 21:46:34]

This is really because scaling from texture coordinates back into geometry space
might round incorrectly due to floating point, causing seams, right?

I *really* appreciate your discussion of why you picked 1024, but I think I'd
also like just a tiny bit more reasoning about why there might be seams in the
first place.

Is it possible that this would cause geometric overlap? I'm guessing the answer
is no, because of the VerifyTilesExactlyCoverRect check?

[trchen, 2016/09/09 23:39:19]

It could happen due to FP error.

right_edge_of_tile_ij = floor(right[i,j] * content_to_dest)
left_edge_of_tile_i1j = ceil(left[i+1,j] * content_to_dest)

In theory right[i,j] == left[i+1,j] + 1, thus provably there can be no gap
between rounded edges. But because we use XYWH rects, the actual computation
becomes:
right_edge_of_tile_ij = floor(x[i,j] * content_to_dest + size[i,j] *
content_to_dest)
It could flip over a rounding boundary of both multiplication gets rounded down.

Besides that, we could fail to cover the whole dest rect due to ulp errors
between dest <---> content space conversion. e.g at line #428 we thought "tile
12 ought to be enough to cover x=345", then at here we realized "sorry, tile 12
only covered up to x=344.99999999".
The overlap is eliminated below at line #504~510.

+    // that with bilinear filtering, the maximum error in color value
+    // introduced by clamping error in both u/v axis can't exceed
+    // 255 * (1 - (1 - 1/1024) * (1 - 1/1024)) ~= 0.498
+    // i.e. The color value can never flip over a rounding threshold.
+    //
+    // For external edges, extend tile bound by 1.5 texels. This is needed to
+    // fully cover the dest space. The number 1.5 came from the fact that the
+    // sample extent doesn't cover the last 0.5 texel to layer edge, and the
+    // dest space can be rounded up for up to 1 pixel. This overhang will never
+    // be sampled as the AA fragment shader clamps sample coordinate and apply
+    // antialiasing itself.
+    const TilingData& data = tiling_->tiling_data_;
+    constexpr float epsilon = 1.f / 1024.f;
+    texel_extent.Inset(tile_i_ ? -epsilon : -1.5,

[enne (OOO), 2016/09/09 21:46:34]

Can you set the texel_extent to be 0 if it's the left/top edge and to be tile
bounds if it's the right/bottom edge, rather than using this magical 1.5?
Depending on the AA shader to fix up texture coordinates seems like something
that will come back to bite later.

[trchen, 2016/09/09 23:39:19]

Yes I've considered that. That's more correct. However the scaled layer bounds
need to be computed. Plugging 1.5 here allows compiler vectorization.

[enne (OOO), 2016/09/15 18:06:23]

I'd rather be simple first and optimize later, sorry.  Can you set this to be
zero if it's the left/top edge?

+                       tile_j_ ? -epsilon : -1.5,
+                       (tile_i_ != data.num_tiles_x() - 1) ? -epsilon : -1.5,
+                       (tile_j_ != data.num_tiles_y() - 1) ? -epsilon : -1.5);
+  }
+  current_geometry_rect_ = gfx::ToEnclosedRect(
+      gfx::ScaleRect(texel_extent, 1 / dest_to_content_scale_));
 
   current_geometry_rect_.Intersect(dest_rect_);
   DCHECK(!current_geometry_rect_.IsEmpty());
 
   if (first_time)
     return *this;
 
   // Iteration happens left->right, top->bottom.  Running off the bottom-right
   // edge is handled by the intersection above with dest_rect_.  Here we make
   // sure that the new current geometry rect doesn't overlap with the last.
@@ skipping 407 matching lines @@
 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
   size_t amount = 0;
   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
     const Tile* tile = it->second.get();
     amount += tile->GPUMemoryUsageInBytes();
   }
   return amount;
 }
 
 }  // namespace cc