697645 - Consider using per-pixel shaders for CSS border rendering (maybe even on the CPU)

Status: NEW

(Core :: Layout, defect)

Description

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The structure of our current border-rendering code leaves much to be desired. It's complicated, and it's also quite slow when combining complex features. In bug 696248, we see GMail combining border-radius and -moz-border-colors, as well as varying the colors by border side. It's slow because we use groups and paths and operator ADD, and try to get antialiasing right. There's a lot of overhead because these operations require graphics memory allocation and context state changes. However, a lot of the borders we draw are very thin and we're not actually rendering many pixels.

So an alternative would be to use a shader-like approach, where we directly compute for each pixel in the border what the rendered color should be. Here's an outline of how that might work:
https://wiki.mozilla.org/Gecko:CSSBorderRenderingWithShaders
My hope is that that approach could be fast and accurate when using GPU rendering. It might even be fast(er) for our non-fast-path cases when using the CPU, especially if we specialize well for the sides. For the CPU case we would run the shader to generate a gfxImageSurface (or maybe four gfxImageSurfaces, to avoid allocating and filling a surface for the interior of a large element) and then draw those surfaces.

Comment 1

[Michael Ventnor]

Attachment: WIP 1

Here's what I have so far, some parts of it don't work and is not optimised yet (I use thebes to draw each pixel individually in corners!). Mostly what I want is feedback on the overall approach. The interesting code starts in nsCSSBorderShader.cpp under debugDrawDot().

You'll also notice that all borders have been hardcoded as solid red-blue in this patch for easy testing.

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 582803 [details] [diff] [review]
WIP 1

Review of attachment 582803 [details] [diff] [review]:
-----------------------------------------------------------------

The solid-color code looks like it's going in the right direction. Of course the dotted/dashed masking code has to be added, because the code you have only handles solid. The dotted/dashed masking computation should be cleanly separable.

It's probably worth ripping out all the parts of the old code that you aren't going to need.

::: layout/base/nsCSSBorderShader.cpp
@@ +88,5 @@
> + *            |- DrawBorderSides with one side
> + *         |- PopGroup
> + *      |- for each side
> + *         |- DoSideClipWithoutCornersSubPath
> + *         |- DrawDashedSide || DrawBorderSides with one side

This comment is bogus, remove it.

It might have been better to not start by copying nsCSSBorderRendering. There's stuff in here that you don't need :-(.

@@ +274,5 @@
> +  return true;
> +}
> +
> +gfxRect
> +nsCSSBorderShader::GetCornerBounds(mozilla::css::Corner aCorner)

Put "using namespace mozilla::css;" somewhere to avoid all this prefixing.

@@ +372,5 @@
> +
> +
> +static gfxRGBA
> +RGBAFromTexture(const gfxImageSurface* aSurface,
> +                const PRInt32 aPixel)

I suggest working in ARGB PRUint32s instead of gfxRGBAs (which are expensive 4-doubles).

@@ +375,5 @@
> +RGBAFromTexture(const gfxImageSurface* aSurface,
> +                const PRInt32 aPixel)
> +{
> +  if (aSurface->GetDataSize() == 0)
> +    return gfxRGBA(0, 0, 0, 0);

This special case should not be needed. If necessary create a length-1 array with RGBA(0,0,0,0) in it and use that for zero-width borders.

@@ +379,5 @@
> +    return gfxRGBA(0, 0, 0, 0);
> +
> +  // We need to handle out-of-bounds pixels in this way,
> +  // rather than simply returning transparent black, otherwise
> +  // if we interpolate this color then we will move towards black.

Why would we interpolate the returned color? I would think that returning RGBA(0,0,0,0) for out-of-bounds colors is fine.

@@ +391,5 @@
> +    return closestPixel;
> +  }
> +
> +  const PRUint32* packedData = (PRUint32*)aSurface->Data();
> +  return gfxRGBA(packedData[aPixel], gfxRGBA::PACKED_ARGB_PREMULTIPLIED);

With the above changes this function can just be a very simple array lookup with bounds checks that return RGBA(0,0,0,0) for out of bounds. In fact you can optimize that by doing something like
  PRUint32 index = PRUint32(aPixel);
  return index < arrayLength ? array[index] : RGBA(0,0,0,0);

@@ +414,5 @@
> +
> +  result.r = floorCol.r + (ceilCol.r - floorCol.r) * difference;
> +  result.g = floorCol.g + (ceilCol.g - floorCol.g) * difference;
> +  result.b = floorCol.b + (ceilCol.b - floorCol.b) * difference;
> +  result.a = floorCol.a + (ceilCol.a - floorCol.a) * difference;

Right idea, but as above I think you should work in PRUint32s here instead of gfxRGBAs.

@@ +427,5 @@
> +                                        const gfxRect& aCurvedBounds,
> +                                        const gfxRect& aPixel)
> +{
> +  // Convert our pixel coords to cartesian coords.
> +  // The ellipse origin is the corner of aCurvedBounds closest to the inner rect.

I haven't checked the math in this function but the structure seems like the right idea.

@@ +439,5 @@
> +  if (mInnerRadii[aCorner].width > 0.0f && mInnerRadii[aCorner].height > 0.0f) {
> +    innerE = (offsetFromOrigin.x * offsetFromOrigin.x) /
> +               (mInnerRadii[aCorner].width * mInnerRadii[aCorner].width) +
> +             (offsetFromOrigin.y * offsetFromOrigin.y) / 
> +               (mInnerRadii[aCorner].height * mInnerRadii[aCorner].height);

There are common subexpressions here independent of aPixel, so eventually we'll be able to speed this up by factoring them out of the per-pixel loop. For now, factoring them out in this function would simplify code as well as speeding things up, so do that too.

@@ +488,5 @@
> +                                      (mBorderRadii[aCorner].width * mBorderRadii[aCorner].width) +
> +                                    (innerIntersect.y * innerIntersect.y) /
> +                                      (mBorderRadii[aCorner].height * mBorderRadii[aCorner].height);
> +
> +    // We can now get a value within [0.0, 1.0] representing where the pixel is

It's not guaranteed to be within 0.0/1.0 right?

@@ +546,5 @@
> +    // number of pixels apart and should stay that way after
> +    // rounding. We don't do this if there's a scale in the current transform
> +    // since this loses information that might be relevant when we're scaling.
> +    mOuterRect.Round();
> +    mInnerRect.Round();

I don't know that you really need to do this anymore...

@@ +563,5 @@
> +    imgCtx->Fill();
> +    imgCtx->NewPath();
> +    imgCtx->SetColor(gfxRGBA(0.0, 0.0, 1.0));
> +    imgCtx->Rectangle(gfxRect(mBorderWidths[side] / 2, 0, mBorderWidths[side] / 2, 1));
> +    imgCtx->Fill();

You don't need to use image surfaces to sample here. You could just use an array of PRUint32s. I recommend nsAutoTArray<PRUint32,3> say. And you shouldn't need to use Thebes to fill them.

@@ +566,5 @@
> +    imgCtx->Rectangle(gfxRect(mBorderWidths[side] / 2, 0, mBorderWidths[side] / 2, 1));
> +    imgCtx->Fill();
> +  }
> +
> +  NS_FOR_CSS_SIDES (side) {

It might be a good idea to put this entire loop body into a helper member function which is templated using the side value as a template parameter, and just call it four times. The compiler will probably be able to generate much better code that way.

@@ +573,5 @@
> +
> +    // Begin painting from the inner edge, wherever that is
> +    // TODO optimize this so we don't draw 1 pixel row at a time
> +    gfxRect paintRect = GetSideBounds(side);
> +    gfxFloat offsetCoefficient = 1; // Either 1 or -1, representing which direction we are going

Document what this actually means

@@ +607,5 @@
> +      mContext->Fill();
> +
> +      *offsetToChange += (1 * offsetCoefficient);
> +
> +      mContext->Restore();

Don't need the save/restore pair.

This is heading in the right direction. One thing is that you can just loop over the border colors filling a rect for each one (as I'm sure you're aware). You don't need to use the texture image for that, just pull the color from a border colors array (see below for suggested interface changes).

@@ +612,5 @@
> +    }
> +  }
> +
> +  NS_FOR_CSS_CORNERS (corner) {
> +    // Draw corners pixel-by-pixel.

It might be a good idea to put this entire loop body into a templated member function and call it four times. That will let the compiler generate better code.

@@ +656,5 @@
> +        // (x1, y1) = separatorOuter, (x2, y2) = separatorInner, (x3, y3) = current pixel
> +        triangleMatrix._32 = pixelRect.x;
> +        triangleMatrix._33 = pixelRect.y;
> +        mozilla::css::Side samplerSide;
> +        if (triangleMatrix.Determinant() < 0) {

You can (and should) optimize this since you know what some of the entries are.

@@ +662,5 @@
> +          samplerSide = (mozilla::css::Side)corner;
> +        } else {
> +          // Go counter-clockwise (ie, in the top-left corner, look at the left side)
> +          samplerSide = (mozilla::css::Side)((corner + 3) % 4);
> +        }

You'll need to do something here to handle cases on the edge where we want to sample both sides and mix them (to get the antialising right where two sides have different colors). It probably makes sense to put the rest of this loop body into a helper function to which you can pass samplerSide as a parameter. Then when you're right in the middle you can call that function twice and average the values.

Or, you can always call it twice and interpolate based on how far around the corner we are, to get a nice gradient effect.

@@ +676,5 @@
> +          // looking at.
> +          switch (samplerSide) {
> +            case NS_SIDE_TOP:
> +              if (y >= mBorderWidths[samplerSide])
> +                continue;

Might be better to skip this early-exit check. RGBAFromTexture should quickly return RGBA(0,0,0,0) which gets cheaply stored in the output image (see below).

@@ +700,5 @@
> +
> +        mContext->NewPath();
> +        mContext->Rectangle(pixelRect);
> +        mContext->SetColor(pixelResult);
> +        mContext->Fill();

Don't do this, doing cairo operations per pixel will be incredibly slow for any non-tiny corners. Instead, outside the per-corner loop create a gfxImageSurface that's big enough for each of the four corners, and in the per-pixel loop just set the image surface data value for that pixel. Then for each corner, draw the gfxImageSurface to mContext.

::: layout/base/nsCSSBorderShader.h
@@ +73,5 @@
> + *
> + * For any parameter where an array of side values is passed in,
> + * they are in top, right, bottom, left order.
> + *
> + * borderStyles -- one border style enum per side

You'll want to document that this can only be one of SOLID, DOTTED or DASHED. The other styles can be converted to SOLID style with multiple border colors.

@@ +105,5 @@
> +                      const gfxFloat* aBorderWidths,
> +                      gfxCornerSizes& aBorderRadii,
> +                      const nscolor* aBorderColors,
> +                      nsBorderColors* const* aCompositeColors,
> +                      PRIntn aSkipSides,

I think aSkipSides can be removed and we can just use a zero width on the sides that are to be skipped.

I think aBorderColors and aCompositeColors should be combined into a single array of 4 structs, each of which is a pair of nscolor* mColors, PRUint32* mWidths, PRUint32 mColorCount. We do need a width to be specified separately for each border color. These widths will always be integer device pixels.

@@ +106,5 @@
> +                      gfxCornerSizes& aBorderRadii,
> +                      const nscolor* aBorderColors,
> +                      nsBorderColors* const* aCompositeColors,
> +                      PRIntn aSkipSides,
> +                      nscolor aBackgroundColor);

Not sure why the background color is needed. It shouldn't be. Styles that depend on the background color should adjust the colors that get passed into nsCSSBorderShader. Basically we want to simplify the interface to nsCSSBorderShader as much as possible (and no more!).

Comment 3

[Michael Ventnor]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #2)
> @@ +372,5 @@
> > +
> > +
> > +static gfxRGBA
> > +RGBAFromTexture(const gfxImageSurface* aSurface,
> > +                const PRInt32 aPixel)
> 
> I suggest working in ARGB PRUint32s instead of gfxRGBAs (which are expensive
> 4-doubles).

Won't this cause endianness problems? Cairo may use BGRA instead of ARGB. I use gfxRGBA because it deals with endianness and because that's also what thebes uses.

> @@ +379,5 @@
> > +    return gfxRGBA(0, 0, 0, 0);
> > +
> > +  // We need to handle out-of-bounds pixels in this way,
> > +  // rather than simply returning transparent black, otherwise
> > +  // if we interpolate this color then we will move towards black.
> 
> Why would we interpolate the returned color? I would think that returning
> RGBA(0,0,0,0) for out-of-bounds colors is fine.

This is how we do texture sampling and is also how we get antialiasing along the edges. We do need to interpolate in this way otherwise the antialiased pixels on the edges will be darker than they should (because they are being interpolated towards black).

> @@ +566,5 @@
> > +    imgCtx->Rectangle(gfxRect(mBorderWidths[side] / 2, 0, mBorderWidths[side] / 2, 1));
> > +    imgCtx->Fill();
> > +  }
> > +
> > +  NS_FOR_CSS_SIDES (side) {
> 
> It might be a good idea to put this entire loop body into a helper member
> function which is templated using the side value as a template parameter,
> and just call it four times. The compiler will probably be able to generate
> much better code that way.

Templated? You mean passing in the side as a parameter, right? Because side values are the same type.

Also, I used to have an array of gfxRGBAs but I changed it to a texture because I thought that's what you wanted. I can go back to an array but using a custom struct for colours might cause endianness problems as I mentioned before.

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #3)
> (In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #2)
> > I suggest working in ARGB PRUint32s instead of gfxRGBAs (which are expensive
> > 4-doubles).
> 
> Won't this cause endianness problems? Cairo may use BGRA instead of ARGB. I
> use gfxRGBA because it deals with endianness and because that's also what
> thebes uses.

No, gfxImageSurface pixel buffers are always ARGB PRUint32s. Endianness isn't a problem, v >> 24 is always the alpha value etc.

> > @@ +379,5 @@
> > > +    return gfxRGBA(0, 0, 0, 0);
> > > +
> > > +  // We need to handle out-of-bounds pixels in this way,
> > > +  // rather than simply returning transparent black, otherwise
> > > +  // if we interpolate this color then we will move towards black.
> > 
> > Why would we interpolate the returned color? I would think that returning
> > RGBA(0,0,0,0) for out-of-bounds colors is fine.
> 
> This is how we do texture sampling and is also how we get antialiasing along
> the edges.

OK.

> > @@ +566,5 @@
> > > +    imgCtx->Rectangle(gfxRect(mBorderWidths[side] / 2, 0, mBorderWidths[side] / 2, 1));
> > > +    imgCtx->Fill();
> > > +  }
> > > +
> > > +  NS_FOR_CSS_SIDES (side) {
> > 
> > It might be a good idea to put this entire loop body into a helper member
> > function which is templated using the side value as a template parameter,
> > and just call it four times. The compiler will probably be able to generate
> > much better code that way.
> 
> Templated? You mean passing in the side as a parameter, right? Because side
> values are the same type.

I mean like this:
template <Side aSide> DoStuff(...)
{
  ...
  if (aSide == NS_SIDE_TOP)
    ...
  ...
}
...
DoStuff<NS_SIDE_TOP>(...);
DoStuff<NS_SIDE_RIGHT>(...);
DoStuff<NS_SIDE_BOTTOM>(...);
DoStuff<NS_SIDE_LEFT>(...);

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #3)
> Also, I used to have an array of gfxRGBAs but I changed it to a texture
> because I thought that's what you wanted.

I want to use the *idea* of texture sampling, but the implementation should be whatever is simple and fast :-).

Comment 6

[Michael Ventnor]

Attachment: WIP2

Comment 7

[Michael Ventnor]

OK, status update!

I've fixed some of your comments, however I want to make the patch feature-complete before I start on the optimizations.
I've got support for "perfect" dotted borders. This means that dotted border sides will fit within whatever space they have, dots are painted in a corner, and in a rectangular box you'll end up with a symmetrical border. However, if a corner has a border-radius I fall back to solid corners like before.
I'm now starting on making dashed borders "perfect", this might be a bit harder but I'm thinking we should make the corners solid, and fit the dashes on each side.

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #7)
> I've got support for "perfect" dotted borders. This means that dotted border
> sides will fit within whatever space they have, dots are painted in a
> corner, and in a rectangular box you'll end up with a symmetrical border.
> However, if a corner has a border-radius I fall back to solid corners like
> before.

Great! When are you planning to fix that? Fixing that is an important part of this bug. (And a hard part.) I'd encourage you to fix that early since it's risky.

> I'm now starting on making dashed borders "perfect", this might be a bit
> harder but I'm thinking we should make the corners solid, and fit the dashes
> on each side.

The middle of a dash should go in the corner. We don't want to have a single square sitting in the corner.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Basically I would say: put a dash centered in each corner (in other words, with the line defining the boundary between the two sides going straight through it). If a side doesn't have enough room for a reasonable-sized gap between those two dashes, just draw it solid. Otherwise make all dashes on the side the same length, and calculate how many dashes will fit with a minimum gap between each one. Then allow the gap between dashes to grow a bit if necessary to make the dashes evenly spaced.

Having dashes and dots centered on the side boundary is important if the style changes between dashed/dotted/solid at a corner. It means you'll get a half-dash/half-dot combination instead of a lone half-dot or half-dash, for example.

Comment 10

[Michael Ventnor]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #8)
> (In reply to Michael Ventnor from comment #7)
> > I've got support for "perfect" dotted borders. This means that dotted border
> > sides will fit within whatever space they have, dots are painted in a
> > corner, and in a rectangular box you'll end up with a symmetrical border.
> > However, if a corner has a border-radius I fall back to solid corners like
> > before.
> 
> Great! When are you planning to fix that? Fixing that is an important part
> of this bug. (And a hard part.) I'd encourage you to fix that early since
> it's risky.

Admittedly I wasn't planning on fixing it at first because in order to do so I'd need to juggle:
1) Laying dots on the border curve
2) Making sure a dot is on the border boundary
3) And still make sure the dots are spaced pleasingly

and I didn't think it'd be possible to do so with my current approach in a performant way. But, I'm thinking about it some more now. I'm getting somewhere, but not enough to get anything working yet.

> > I'm now starting on making dashed borders "perfect", this might be a bit
> > harder but I'm thinking we should make the corners solid, and fit the dashes
> > on each side.
> 
> The middle of a dash should go in the corner. We don't want to have a single
> square sitting in the corner.

Yeah, that's what I was going to do. But I'll think about the dotted problem some more.

Comment 11

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #10)
> Admittedly I wasn't planning on fixing it at first because in order to do so
> I'd need to juggle:
> 1) Laying dots on the border curve
> 2) Making sure a dot is on the border boundary
> 3) And still make sure the dots are spaced pleasingly
> and I didn't think it'd be possible to do so with my current approach in a
> performant way. But, I'm thinking about it some more now. I'm getting
> somewhere, but not enough to get anything working yet.

You need to calculate for a given point, "how far along" the centerline of the border the pixel is, starting from the line that separates the two sides. That shouldn't be too hard to do. Then, assuming you've precalculated the distance between dot centers, you can figure out which dot the pixel is closest to, compute the center point for that dot, and check whether the pixel is inside it (or on the edge, for antialiasing).

Comment 12

[Michael Ventnor]

I forgot to mention, there's also the case where the two border sides are of different widths. I was planning on having a mid-sized dot centered on the border boundary.
Currently, I calculate a separate space size for each border side, and therefore I don't think every space in the corner can be uniform like your approach suggests AFAICT.

Comment 13

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #12)
> I forgot to mention, there's also the case where the two border sides are of
> different widths. I was planning on having a mid-sized dot centered on the
> border boundary.

I'd just make half the dot bigger than the other half.

Comment 14

[Michael Ventnor]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #13)
> (In reply to Michael Ventnor from comment #12)
> > I forgot to mention, there's also the case where the two border sides are of
> > different widths. I was planning on having a mid-sized dot centered on the
> > border boundary.
> 
> I'd just make half the dot bigger than the other half.

That probably wouldn't look very nice, but I guess it's easier so I'll do that.
Another situation is where you have a corner with high width but small height, so the line boundary would be very close to the edge of the corner's temporary surface. The corner surface already been created by the time we realize this, so I don't think we can just change the size of the surface.

Comment 15

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Hmm yeah, we don't want the border to stick out of the border-box! So we do want different sizes for the dots in the corner, and maybe you're right that we need per-dot sizes and spacing.

One way to do this would be to create a 1D-texture/array that maps "distance along the border" to the index of the nearest dot, and an extra 1D-texture/array that maps from the dot index to its center and radius. Then you can do an array lookup to find which dot the pixel belongs to, and another array lookup to find its center and radius.

Comment 16

[Michael Ventnor]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #15)
> Hmm yeah, we don't want the border to stick out of the border-box! So we do
> want different sizes for the dots in the corner, and maybe you're right that
> we need per-dot sizes and spacing.
> 
> One way to do this would be to create a 1D-texture/array that maps "distance
> along the border" to the index of the nearest dot, and an extra
> 1D-texture/array that maps from the dot index to its center and radius. Then
> you can do an array lookup to find which dot the pixel belongs to, and
> another array lookup to find its center and radius.

What is this trying to solve? This seems awfully complicated and slow.
One solution i thought up: first precalculate the position of each dot. Then, for each pixel, test the distance between the pixel and the dot center is within the radius (this can be fast if we square the radius instead of using sqrt), if so then simply use that dot.

Comment 17

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #16)
> What is this trying to solve? This seems awfully complicated and slow.
> One solution i thought up: first precalculate the position of each dot.
> Then, for each pixel, test the distance between the pixel and the dot center
> is within the radius (this can be fast if we square the radius instead of
> using sqrt), if so then simply use that dot.

Right. But how do you calculate which dot to check, and what the radius and center of that dot is? With variable spacing etc it's going to be tricky. Hence I'm suggesting using array lookups to figure out which dot you're closest to and what its center and radius are.

Comment 18

[Michael Ventnor]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #17)
> (In reply to Michael Ventnor from comment #16)
> > What is this trying to solve? This seems awfully complicated and slow.
> > One solution i thought up: first precalculate the position of each dot.
> > Then, for each pixel, test the distance between the pixel and the dot center
> > is within the radius (this can be fast if we square the radius instead of
> > using sqrt), if so then simply use that dot.
> 
> Right. But how do you calculate which dot to check, and what the radius and
> center of that dot is? With variable spacing etc it's going to be tricky.
> Hence I'm suggesting using array lookups to figure out which dot you're
> closest to and what its center and radius are.

But I read your comment again and I don't understand how your approach solves those problems either.

Comment 19

[Michael Ventnor]

(In reply to Michael Ventnor from comment #18)
> (In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #17)
> > (In reply to Michael Ventnor from comment #16)
> > > What is this trying to solve? This seems awfully complicated and slow.
> > > One solution i thought up: first precalculate the position of each dot.
> > > Then, for each pixel, test the distance between the pixel and the dot center
> > > is within the radius (this can be fast if we square the radius instead of
> > > using sqrt), if so then simply use that dot.
> > 
> > Right. But how do you calculate which dot to check, and what the radius and
> > center of that dot is? With variable spacing etc it's going to be tricky.
> > Hence I'm suggesting using array lookups to figure out which dot you're
> > closest to and what its center and radius are.
> 
> But I read your comment again and I don't understand how your approach
> solves those problems either.

(I mean in a way that my approach doesn't solve. What I do is precalculate where the dots should go, then test each pixel against every dot (optimizing this test as much as I can), and the first dot that the pixel falls within is the dot that is used to draw that pixel)

Comment 20

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Michael Ventnor from comment #19)
> (I mean in a way that my approach doesn't solve. What I do is precalculate
> where the dots should go, then test each pixel against every dot (optimizing
> this test as much as I can)

How? If there are 20 dots, comparing each pixel against each dot sounds bad.

Comment 21

[Michael Ventnor]

OK, I've been spending many days now trying to get a good approach for "distance-along-curve" going that I can use for dots and I still can't get it quite right.

- To get a curve of a specified length, in order to place the dots, I use the elliptical integral, and approximate using a binary search. But it doesn't seem to measure length in a linear way, at least with curves that have a huge width and tiny height or vice-versa. It's tough to explain.

- To find out how far along the curve a pixel is, I extrapolate the line from the corner point to the pixel, and see where that intersects the curve. That falls apart with pixels close to the corner, due to the angles between them being very wide and thus extrapolating to a point on the ellipse too far away. I haven't yet thought of a better approach.

This is taking far longer than even my pessimistic estimates. There are so many bugs and edge cases to deal with.

Comment 22

[Robert O'Callahan (:roc) (email my personal email if necessary)]

How can I help?

Comment 23

[Michael Ventnor]

The biggest help would be more time ;) but what I need is a more foolproof way of approximating how far any pixel is along a given curve (even if said pixel doesn't lie on the curve), if the ellipse center is known.

An easier way would be to do what I said before, which is simply test against each dot's radius (which, looking at the code I have, may arguably be faster).

But then there's the problem with the dashes, where having this measure-distance-of-a-pixel function would be useful to determine whether a pixel is within a dash or space.

Comment 24

[Michael Ventnor]

Attachment: WIP3

This really is frustrating, because once again it's the situation where what I have works fine for circular borders but not for elliptical borders with non-equal axes.

Comment 25

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I've made a canvas-based prototype in JS that handles all the features. It behaves poorly in a few cases; one of them is fixable with some more computational geometry, and I think the other issues are tolerable. I think it can be implemented fairly efficiently. We should have done this sort of prototype at the beginning :-(.

Comment 26

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: the prototype

Have a play with this.

Comment 27

[Robert O'Callahan (:roc) (email my personal email if necessary)]

BTW I realize that for some cases (e.g. groove) we want an abrupt transition between the colors for each side, instead of the smooth transition that the prototype does. That's easy to change (or make optional).

Comment 28

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: updated again

Add some comments, simplify some testcases, and fix some antialiasing failures.

Comment 29

[Michael Ventnor]

roc, I have made some progress since I made that last comment, sorry if I gave off the impression otherwise. I'll talk with you about this when you're available over email or IRC.

Comment 30

[Michael Ventnor]

Ok, so an update. Sorry about the lack of communication, I've been really busy.
I FINALLY fixed a crucial and difficult bug in my code, which has then allowed me to progress very rapidly. Dotted borders work, dashed borders work, and they are all calculated to fit within the sides and corners perfectly.

We're at the stage where we could ship this if we really wanted to. We're down to bug-hunting and polish and optimisations.

Sorry roc, I didn't use your prototype, it fell apart in too many areas (for example, straight sides within corner boundaries). Your prototype uses trigonometry whereas mine uses calculus, so I guess mine is a little slower however it seems much more robust from my testing.

Comment 31

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Can you put the code up so we can discuss it?

Comment 32

[Michael Ventnor]

Attachment: WIP 4

I didn't upload it last night because it was spread over two queue patches in a non-sensical way, I've merged it now.

Comment 33

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: simple page for playing with borders

This is a simple page that lets you edit border styles interactively.

Comment 34

[Robert O'Callahan (:roc) (email my personal email if necessary)]

With
#d { border-radius:100px/200px; border-width:10px; border-style:dotted; border-color:black; }
only the top and bottom sides are dotted, for me.

Comment 35

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Oops, that was me using the wrong build.

Comment 36

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: comprehensive testcase

I wrote this as a testcase to systematically test various combinations of border-width, border-radius, and border-style. When I load it with the patch, I get some kind of memory corruption. On Windows, in a debug build, I get alerts from the VC++ runtime about memory being modified beyond the end of the allocated block when it frees the pixel data block for one of the corner surfaces.

Comment 37

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: reduced testcase

The error reproduces with this testcase.

Comment 38

[Michael Ventnor]

Is this a crash or just a warning? Because I get no problems on Linux (and I don't have VC++ on Windows...)

Comment 39

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It's a warning, but it blocks my debug build, and maybe would crash anyway. Writing out of bounds is bad. Try using valgrind?

Comment 40

[Michael Ventnor]

Attachment: WIP5

I think I know what was causing this. I'm comparing an int to a float in the for loops, but there could be some float errors that causes us to have one extra looping, and an out of bounds error.

I used the same fix that I used for the 0-pixel corner surfaces on bugzilla.

Comment 41

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Thanks, that seems to fix the memory corruption.

Looking at the testcase in comment #36, some quick observations by section:

width:100px; height:100px; border-width:18px; border-radius:0
These look great.

width:100px; height:100px; border-width:18px; border-radius:40px
These look great, except for "dotted none" where there are half-dots.

width:100px; height:100px; border-width:18px; border-radius:10px/50px
width:100px; height:100px; border-width:18px; border-radius:0/50px
width:100px; height:100px; border-width:18px; border-radius:50px/10px
width:100px; height:100px; border-width:12px 48px; border-radius:0
width:100px; height:100px; border-width:12px 48px; border-radius:40px
width:100px; height:100px; border-width:12px 48px; border-radius:10px/50px
width:100px; height:100px; border-width:12px 48px; border-radius:0/50px
width:100px; height:100px; border-width:12px 48px; border-radius:50px/10px
width:100px; height:100px; border-width:12px 48px; border-radius:0/10px
Unfortunately, these mostly look terrible.

Comment 42

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: add 5px border-radius case

Adding a 5px border-radius. On the most recent patch, the radius looks more like 2px, and doesn't get antialiased. There are also some glitches in the corners with some of the border-style combinations.

Comment 43

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: add 4px border-width case

The 4px cases where the border-radii are greater than the width are not too bad. For highly elliptic radii, the boundary line between the colors is placed in a strange place.

Comment 44

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: add border-width:4px 8px case

For width:100px; height:100px; border-width:4px 8px; border-radius:0, the junctions between solid and dashed sides aren't right.

Comment 45

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 594921 [details] [diff] [review]
WIP5

Review of attachment 594921 [details] [diff] [review]:
-----------------------------------------------------------------

Some thought spew (I've written it out of order so hopefully it makes some sense)

I'd be very interested to see some performance numbers for this code.

It looks like one of the tricky bits is the lack of a parametrization of the ellipse by arc length. It's possible we can come up with a performant version of that runs well on the gpu (I've talked with bjacob about it), but if we can't I'm not sure the current approach is a good one. For example, with dotted borders, if we know all of the positions of the dots we are probably better of just drawing them explicitly instead of implicitly with a complicated pixel shader.

That being said, there's still value in a reference implementation of the border drawing that's easy to understand and show correct. If this code becomes that, I expect there are different tradeoffs that would be made. I think having good reference code would be a good place to start. Designing code like this to run in a GPU style looks pretty hard, so having a reference implementation would also make it easier to plan out the specifics of how it could run faster on the gpu. For example, the current approach of testing each pixel against each dash/dot doesn't map to a GPU very well and doesn't scale very well. I'm not sure if this would be a problem in practice but it's a bit scary.

I realize the code is researchy so structuring the code well is likely pretty difficult. Anwways, I wasn't able to follow everything but I've added a couple additional comments inline.

::: layout/base/nsCSSBorderShader.cpp
@@ +446,5 @@
> +
> +  NS_NOTREACHED("Not a valid intersection type");
> +  return gfxPoint(0, 0);
> +}
> +

Returning the color makes more sense.

@@ +733,5 @@
> +    return 0;
> +
> +  return mSideSamples[aSide][aPixel];
> +}
> +

This also not a great name.
ComputeSideColorAtPoint might be better?

@@ +738,5 @@
> +gfxPackedARGB
> +nsCSSBorderShader::RGBAFromTextureCoord(const Side aSide,
> +                                        const gfxFloat aCoord)
> +{
> +  // Given a texture coord (normally between [0.0, 1.0] but not always),

when not?

@@ +787,5 @@
> +// The only way we can get a curve of a certain length is to approximate it.
> +// In the field of maths, we do this by approximating with smaller segments
> +// of known lengths.
> +// In computing, we use a binary search, finding the parameter t which
> +// gives us the length we want.

I know this part isn't currently meant to run on the gpu but I didn't realize that immediately. Anyways, recursion is not well supported on GPUs (AFAIK only CUDA with Fermi hardware)

@@ +1482,5 @@
> +    *offsetWidth += currentColorWidth;
> +  }
> +}
> +
> +

Solve what?

Comment 46

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Thanks Jeff!

None of this is meant to run on a GPU. At least, not immediately.

> For example, with dotted borders, if we know all of the positions of the dots we
> are probably better of just drawing them explicitly instead of implicitly with a
> complicated pixel shader.

Maybe, maybe not. We've had awful cairo performance in the past tesselating lots of tiny rectangles, and tiny dots would be even worse. And there are complicating factors here, like if we need to draw half a dot, or the dot needs to have multiple border colors in it, or different-colored sides meet in the dot and need to have a few antialiased pixels.

Comment 47

[Jeff Muizelaar [:jrmuizel]]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #46)
> Thanks Jeff!
> 
> None of this is meant to run on a GPU. At least, not immediately.
> 
> > For example, with dotted borders, if we know all of the positions of the dots we
> > are probably better of just drawing them explicitly instead of implicitly with a
> > complicated pixel shader.
> 
> Maybe, maybe not. We've had awful cairo performance in the past tesselating
> lots of tiny rectangles, and tiny dots would be even worse. And there are
> complicating factors here, like if we need to draw half a dot, or the dot
> needs to have multiple border colors in it, or different-colored sides meet
> in the dot and need to have a few antialiased pixels.

We don't need to tesselate these paths though because we can guarantee that there will be no intersections. i.e. a purpose built rasterizer should be able to do very at this kind of thing. Plus, if we did have such a thing we could probably build a texture that would let us draw the border with D2D using 4 draw image calls which could be coalesced into a single gpu draw call.

Comment 48

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I'm not really sure what the boundary is between what we're doing here and a purpose-built rasterizer, or how the latter would integrate into Thebes or Azure API.

I think this per-pixel color computation approach is a good way to structure the problem even if we end up taking shortcuts for speed.

Comment 49

[Jeff Muizelaar [:jrmuizel]]

(In reply to Jeff Muizelaar [:jrmuizel] from comment #45)
> It looks like one of the tricky bits is the lack of a parametrization of the
> ellipse by arc length. 

Benoit and I looked at this a bit more. Benoit came up with http://people.mozilla.org/~bjacob/ellipse.html.

There's also code here http://code.google.com/p/elliptic/source/browse/trunk/inverselliptic2.m which implements "J. P. Boyd, "Numerical, Perturbative and Chebyshev Inversion of the Incomplete Elliptic Integral of the Second Kind", Applied Mathematics and Computation (January 2012)"

Comment 50

[Boris Zbarsky [:bzbarsky]]

A question.  Would this approach help with seaming issues like the one on http://jsfiddle.net/tpDyA/ ?

Comment 51

[Jeff Muizelaar [:jrmuizel]]

(In reply to Boris Zbarsky (:bz) from comment #50)
> A question.  Would this approach help with seaming issues like the one on
> http://jsfiddle.net/tpDyA/ ?

We should be able to fix the seaming issues there without needing this.

Comment 52

[Boris Zbarsky [:bzbarsky]]

Sure, for the single-color case.  We already do for the same-border-widths case....

Worth filing a separate bug on it?

Comment 53

[Jeff Muizelaar [:jrmuizel]]

(In reply to Boris Zbarsky (:bz) from comment #52)
> Sure, for the single-color case.  We already do for the same-border-widths
> case....
> 
> Worth filing a separate bug on it?

Sure.

Comment 54

[Boris Zbarsky [:bzbarsky]]

OK, filed bug 760358.

Comment 55

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee didn't login in Bugzilla in the last 7 months, so the assignee is being reset.