add helper to create fancy underlines

add helper to create fancy underlines

Add a couple of utility functions to SkPaint that return the bounds
of glyphs between a pair of lines.

The common use case envisioned generates the edges of descenders
between the top and bottom bounds of an underline to allow computing
a stroke that skips those descenders.

The implementation stores a linked list in each glyph containing
the bounds of the lines parallel to the advance and the outermost
intersections within those bounds.

When the glyph cache is constructed, the glyph path is intersected
with the bounds and the extreme min and max values within the bounds
is added to an intercept.

Share the text to path iter to construct the data.

Make a half-hearted attempt to support vertical text; while the
vertical implementation is complete; surrounding code (e.g. paint
align) has short-comings with vertical.

R=fmalita@chromium.org, reed@google.com

GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1654883003

Committed: https://skia.googlesource.com/skia/+/0449bcfb2fa1dd33cb3a4c0c8b17960d17edf01a

[caryclark, 2016-02-01 19:15:59]

Description was changed from

==========
wip; underline

BUG=skia:
==========

to

==========
wip; underline

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
==========

[caryclark, 2016-02-02 20:51:49]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-02 20:51:57]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/60001

[commit-bot: I haz the power, 2016-02-02 20:53:42]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-02 20:53:42]

Dry run: Try jobs failed on following builders:
  Build-Ubuntu-GCC-x86_64-Release-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-GCC-x86...)

[caryclark, 2016-02-02 21:29:45]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-02 21:30:21]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/80001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/80001

[commit-bot: I haz the power, 2016-02-02 22:02:01]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-02 22:02:02]

Dry run: This issue passed the CQ dry run.

[caryclark, 2016-02-03 17:09:17]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-03 17:09:27]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/160001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/160001

[commit-bot: I haz the power, 2016-02-03 17:10:42]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-03 17:10:42]

Dry run: Try jobs failed on following builders:
  Build-Mac10.8-Clang-x86_64-Release-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Mac10.8-Clang-...)
  Build-Ubuntu-Clang-x86_64-Debug-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-Clang-x...)

[caryclark, 2016-02-03 17:24:08]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-03 17:24:18]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/180001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/180001

[commit-bot: I haz the power, 2016-02-03 17:52:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-03 17:52:25]

Dry run: This issue passed the CQ dry run.

[caryclark, 2016-02-05 16:08:59]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 16:09:05]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/300001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/300001

[commit-bot: I haz the power, 2016-02-05 16:10:18]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-05 16:10:19]

Dry run: Try jobs failed on following builders:
  Build-Ubuntu-GCC-x86_64-Release-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-GCC-x86...)

[caryclark, 2016-02-05 16:25:33]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 16:25:43]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/320001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/320001

[caryclark, 2016-02-05 16:42:10]

Description was changed from

==========
wip; underline

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
==========

to

==========
add helper to create fancy underlines

Add a couple of utility functions to SkPaint that return the bounds
of glyphs between a pair of lines.

The common use case envisioned generates the edges of descenders
between the top and bottom bounds of an underline to allow computing
a stroke that skips those descenders.

The implementation stores a linked list in each glyph containing
the bounds of the lines parallel to the advance and the outermost
intersections within those bounds.

When the glyph cache is constructed, the glyph path is intersected
with the bounds and the extreme min and max values within the bounds
is added to an intercept.

Share the text to path iter to construct the data.

Make a half-hearted attempt to support vertical text; while the
vertical implementation is complete; surrounding code (e.g. paint
align) has short-comings with vertical.

R=fmalita@chromium.org, reed@google.com

GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
==========

[caryclark, 2016-02-05 16:42:10]

caryclark@google.com changed reviewers:
+ fmalita@chromium.org, reed@google.com

[commit-bot: I haz the power, 2016-02-05 16:56:39]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-05 16:56:40]

Dry run: This issue passed the CQ dry run.

[reed1, 2016-02-05 18:56:58]

reed@google.com changed reviewers:
+ herb@google.com, mtklein@google.com

[reed1, 2016-02-05 18:56:59]

herb, mike, are we sensitive to the size/density of SkGlyph?

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h
File include/core/SkPaint.h (right):

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h...
include/core/SkPaint.h:922: int getTextIntercepts(const void* text, size_t
length, SkScalar x, SkScalar y,
If there is any extra burden, we can decide to not offer this variant, and just
force clients to construct the positions and call getPosTextIntercepts.

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h...
include/core/SkPaint.h:937: SkScalar bounds[2], SkScalar* array) const;
const SkScalar bounds[2] ?

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h...
include/core/SkPaint.h:937: SkScalar bounds[2], SkScalar* array) const;
SkScalar intervals[] ?

Is an upper-bound on the size of this array 2 * number of glyphs? Is that the
exact size?

https://codereview.chromium.org/1654883003/diff/320001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/320001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:54: Intercept*  fIntercept;
Hmmm, we already have too much stored in Glyphs, since we typically never have
both a path and an image-ptr. This adds another ptr that will almost always be
null. I wonder if we can find a different way to cache this information (e.g.
separate key, so that the value need not be SkGlyph per-se.)

[caryclark, 2016-02-05 19:43:36]

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h
File include/core/SkPaint.h (right):

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h...
include/core/SkPaint.h:922: int getTextIntercepts(const void* text, size_t
length, SkScalar x, SkScalar y,
On 2016/02/05 18:56:59, reed1 wrote:
> If there is any extra burden, we can decide to not offer this variant, and
just
> force clients to construct the positions and call getPosTextIntercepts.

The burden is very slight; nearly all of the code is shared with the pos
variant.
If you prefer, I'll remove it anyway.

https://codereview.chromium.org/1654883003/diff/320001/include/core/SkPaint.h...
include/core/SkPaint.h:937: SkScalar bounds[2], SkScalar* array) const;
On 2016/02/05 18:56:59, reed1 wrote:
> SkScalar intervals[] ?
> 
> Is an upper-bound on the size of this array 2 * number of glyphs? Is that the
> exact size?

If the string has no descenders at all, the size returned is zero. 
In the current implementation, the upper bounds is 2x # of glyphs. If we choose
that returning the interior of a glyph is also important, that would of course
increase.

Make bounds const (done)

https://codereview.chromium.org/1654883003/diff/320001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/320001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:54: Intercept*  fIntercept;
On 2016/02/05 18:56:59, reed1 wrote:
> Hmmm, we already have too much stored in Glyphs, since we typically never have
> both a path and an image-ptr. This adds another ptr that will almost always be
> null. I wonder if we can find a different way to cache this information (e.g.
> separate key, so that the value need not be SkGlyph per-se.)

I can imagine something that looks like

struct GlyphData {
   Type fType;
   union {
      void* fImage;
      SkPath* fPath;
      Intercept* fIntercept;
   };
};

and either the struct or a pointer to it resides in the struct.

Would you like that remedied in this CL or a separate CL?

[caryclark, 2016-02-05 20:11:20]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 20:11:29]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/360001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/360001

[commit-bot: I haz the power, 2016-02-05 20:43:53]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-05 20:43:54]

Dry run: This issue passed the CQ dry run.

[herb_g, 2016-02-05 21:09:37]

https://codereview.chromium.org/1654883003/diff/360001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/360001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:47: };
Can this struct  and fIntercept go in the private part? SkGlyphCache is already
a friend.

[caryclark, 2016-02-05 21:25:34]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 21:25:44]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/380001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/380001

[caryclark, 2016-02-05 21:26:00]

https://codereview.chromium.org/1654883003/diff/360001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/360001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:47: };
On 2016/02/05 21:09:37, herb_g wrote:
> Can this struct  and fIntercept go in the private part? SkGlyphCache is
already
> a friend.

Done.

[commit-bot: I haz the power, 2016-02-05 21:27:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-05 21:27:21]

Dry run: Try jobs failed on following builders:
  Build-Mac-Clang-x86_64-Release-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Mac-Clang-x86_...)

[caryclark, 2016-02-05 21:34:00]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 21:34:11]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/400001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/400001

[caryclark, 2016-02-05 21:43:43]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-05 21:43:48]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/440001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/440001

[commit-bot: I haz the power, 2016-02-05 22:47:28]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-05 22:47:29]

Dry run: This issue passed the CQ dry run.

[caryclark, 2016-02-06 13:19:49]

Any other issues I can address? By the way, you can see the output by looking at
Gold. There's one test for regular text, one for pos text, and one for glyphs
that partially or fully fit inside the underline.

[reed1, 2016-02-08 14:03:12]

Questions about API

- can the returned count be zero?
- can the returned count be odd?
- is the "array" parameter the "intervals"? why is it named array?
- can we document a safe max allocation for the array parameter?

[f(malita), 2016-02-08 14:20:28]

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

https://codereview.chromium.org/1654883003/diff/440001/include/core/SkPaint.h...
include/core/SkPaint.h:923: const SkScalar bounds[2], SkScalar* array) const;
It's a bit unclear how to size 'array' effectively: should clients call this
method twice (once with a nullptr to count the intercepts and the second time
with an allocated array - assumed to be sufficiently large to hold all
intercepts)?  Maybe you can clarify with more comments.

https://codereview.chromium.org/1654883003/diff/440001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/440001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:48: Intercept*  fIntercept;
Caching this is nice, but may be overkill at this stage.  Since we don't know
how widely this feature is going to be used in Blink, is this something we can
defer for later (if needed)?

[caryclark, 2016-02-09 19:07:49]

The CQ bit was checked by caryclark@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-09 19:07:56]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/460001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/460001

[caryclark, 2016-02-09 19:10:45]

On 2016/02/08 14:03:12, reed1 wrote:
> Questions about API
> 
> - can the returned count be zero?
> - can the returned count be odd?
> - is the "array" parameter the "intervals"? why is it named array?
> - can we document a safe max allocation for the array parameter?

Add documentation to address these.

[caryclark, 2016-02-09 19:10:57]

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

https://codereview.chromium.org/1654883003/diff/440001/include/core/SkPaint.h...
include/core/SkPaint.h:923: const SkScalar bounds[2], SkScalar* array) const;
On 2016/02/08 14:20:27, f(malita) wrote:
> It's a bit unclear how to size 'array' effectively: should clients call this
> method twice (once with a nullptr to count the intercepts and the second time
> with an allocated array - assumed to be sufficiently large to hold all
> intercepts)?  Maybe you can clarify with more comments.

Done.

https://codereview.chromium.org/1654883003/diff/440001/src/core/SkGlyph.h
File src/core/SkGlyph.h (right):

https://codereview.chromium.org/1654883003/diff/440001/src/core/SkGlyph.h#new...
src/core/SkGlyph.h:48: Intercept*  fIntercept;
On 2016/02/08 14:20:27, f(malita) wrote:
> Caching this is nice, but may be overkill at this stage.  Since we don't know
> how widely this feature is going to be used in Blink, is this something we can
> defer for later (if needed)?

If the same glyphs are underlined widely by the caller, the cache could make an
enormous performance difference. To mitigate the concerns about increasing the
size of the cache, I restructured the CL so that the same slot contains the
cached path and the cached underline.

[commit-bot: I haz the power, 2016-02-09 19:32:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-09 19:32:42]

Dry run: This issue passed the CQ dry run.

[reed1, 2016-02-09 20:31:55]

lgtm w/ clarification in dox:

max intervals will be 2 * number of characters/glyphs.

[caryclark, 2016-02-09 20:47:46]

The CQ bit was checked by caryclark@google.com

[caryclark, 2016-02-09 20:47:46]

The patchset sent to the CQ was uploaded after l-g-t-m from reed@google.com
Link to the patchset: https://codereview.chromium.org/1654883003/#ps480001
(title: "correct comment to multiply by two")

[commit-bot: I haz the power, 2016-02-09 20:47:51]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1654883003/480001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1654883003/480001

[commit-bot: I haz the power, 2016-02-09 21:25:48]

Description was changed from

==========
add helper to create fancy underlines

Add a couple of utility functions to SkPaint that return the bounds
of glyphs between a pair of lines.

The common use case envisioned generates the edges of descenders
between the top and bottom bounds of an underline to allow computing
a stroke that skips those descenders.

The implementation stores a linked list in each glyph containing
the bounds of the lines parallel to the advance and the outermost
intersections within those bounds.

When the glyph cache is constructed, the glyph path is intersected
with the bounds and the extreme min and max values within the bounds
is added to an intercept.

Share the text to path iter to construct the data.

Make a half-hearted attempt to support vertical text; while the
vertical implementation is complete; surrounding code (e.g. paint
align) has short-comings with vertical.

R=fmalita@chromium.org, reed@google.com

GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
==========

to

==========
add helper to create fancy underlines

Add a couple of utility functions to SkPaint that return the bounds
of glyphs between a pair of lines.

The common use case envisioned generates the edges of descenders
between the top and bottom bounds of an underline to allow computing
a stroke that skips those descenders.

The implementation stores a linked list in each glyph containing
the bounds of the lines parallel to the advance and the outermost
intersections within those bounds.

When the glyph cache is constructed, the glyph path is intersected
with the bounds and the extreme min and max values within the bounds
is added to an intercept.

Share the text to path iter to construct the data.

Make a half-hearted attempt to support vertical text; while the
vertical implementation is complete; surrounding code (e.g. paint
align) has short-comings with vertical.

R=fmalita@chromium.org, reed@google.com

GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...

Committed:
https://skia.googlesource.com/skia/+/0449bcfb2fa1dd33cb3a4c0c8b17960d17edf01a
==========

[commit-bot: I haz the power, 2016-02-09 21:25:49]

Committed patchset #25 (id:480001) as
https://skia.googlesource.com/skia/+/0449bcfb2fa1dd33cb3a4c0c8b17960d17edf01a