tree a284b8df04fbbbaae35a276d05484f3259e7620e
parent 90508f02dc599ccec1319bfd54617d3548293668
author Michael Ludwig <michaelludwig@google.com> 1620741612 -0400
committer Skia Commit-Bot <skia-commit-bot@chromium.org> 1620844413 +0000

Use Wang's formula for quadratic and cubic point counts

 - most of the small diffs are because I moved GrWangsFormula.h out
   of the tessellate/ directory and into the geometry/ directory since
   it's more general than HW tessellation.

The previous implementation was based on the heuristic that the distance
from the true curve to the line segment would be divided by 4 every time
the curve was recursively subdivided. This was a reasonable
approximation if the curve had balanced curvature on both sides of the
split. However, in the case of the new GM's curve, the left half was
already very linear and the right half had much higher curves.

This lead to the approximation reporting fewer points than required.
Theoretically, those few points that weren't utilized by the left half
of the curve could have been made available to the right half, but the
implementation of that would be tricky.

Instead, it now uses Wang's formula to compute the number of points.
Since recursive subdivision leads to linearly spaced samples assuming it
can't stop early, this point count represents a valid upper bound on
what's needed. It also then ensures both left and right halves of a
curve have the point counts they might need w/o updating the
generation implementations. However, since the recursive point
generation exits once each section has reached the error tolerance, in
scenarios where the prior approximation was reasonable, we'll end up
using fewer points than reported by Wang's. Hopefully that means there
is negligible performance regression since we won't be increasing
vertex counts by that much (except where needed for correctness).

Bug: skia:11886
Change-Id: Iba39dbe4de82011775524583efd461b10c9259fe
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/405197
Reviewed-by: Chris Dalton <csmartdalton@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Michael Ludwig <michaelludwig@google.com>