459148 - SVG curves are drawn differently than curves drawn by the CSS system

Status: VERIFIED FIXED

(Core :: Layout: Block and Inline, defect)

Description

[cmtalbert]

Attachment: A patch of reftests that demonstrate the issue

When drawing curves, SVG and CSS are using two different drawing mechanisms, causing reftest to fail when you are testing that a curve defined from CSS properties is equivalent to the same curve drawn by SVG.

This is needed for many types of testing, but first, it's needed for border-radius reftests.

The patch I'm attaching will demonstrate the issue.

border-html.html and border-svg.xhtml draw the same area using rectangular borders and they match.

border-tinyradius-html.html and border-tinyradius-svg.xhtml draw the same area, but they use border radius measurements, and there is a tiny pixel difference on each corner (zoom in on the reftest analyzer to see the highlighted differences.

Comment 1

[Robert Longson [:longsonr]]

SVG rounded rectangles are fairly simple in comparison to borders. All the line widths and colours must be the same. SVG just creates some arcs for the curves in nsSVGRectElement::ConstructPath. 

CSS needs to do something far more complicated.

I don't think SVG should pay for something it doesn't need so I don't think it should be using the CSS drawing mechanism.

Comment 2

[Zack Weinberg (:zwol)]

Attachment: (rev 1) use thebes primitives for SVG ellipses and rounded rects

(In reply to comment #1)
> SVG rounded rectangles are fairly simple in comparison to borders. All the line
> widths and colours must be the same. SVG just creates some arcs for the curves
> in nsSVGRectElement::ConstructPath. 
> 
> CSS needs to do something far more complicated.

The "different drawing mechanism" that's causing problems for us is at a lower level than you're thinking of.  What we want right now is for SVG and CSS to use the same Bezier curve approximation for rounded rects and ellipses.  As the Thebes layer now exposes ->Ellipse() and ->RoundedRectangle() methods, this is a straightforward patch that mostly deletes code.

(It would be nice to unify the Thebes ellipse approximation with the general elliptical arc code currently in nsSVGPathDataParser and maybe shove the whole thing all the way down into cairo, but that is more than we need right now, I think.)

ctalbert: Your tinyradius test case still fails for me with this patch, but I think the remaining problem is due to a higher-level drawing difference; further discussion in bug 458131.

Comment 3

[Robert Longson [:longsonr]]

Comment on attachment 342460 [details] [diff] [review]
(rev 1) use thebes primitives for SVG ellipses and rounded rects

Ellipses have shrunk in the wash :-) Thebes wants the width/height and you are passing the major axis radius and minor axis radius.

http://www.w3.org/Graphics/SVG/Test/20061213/htmlObjectHarness/full-shapes-ellipse-01-t.html

The other thing is that the rect algorithm is specified explicitly in the SVG specification. http://www.w3.org/TR/SVG/shapes.html#RectElement

As far as I can tell the reason you get differences is that the values of alpha are different.

SVG
alpha = 4*(sqrt(2.)-1)/3 = 0.55228474983079

RoundedRectangle

alpha = 0.54858377035486361

A search for "bezier circle approximation" on the web shows rather articles with the SVG number so you're going to have to convince me the RoundedRectangle implementation is a better approximation i.e. has a lower error than the SVG implementation.

btw I couldn't give you an sr even if it was right. You want roc for that.

Comment 4

[Zack Weinberg (:zwol)]

(In reply to comment #3)
> (From update of attachment 342460 [details] [diff] [review])
> Ellipses have shrunk in the wash :-) Thebes wants the width/height and you are
> passing the major axis radius and minor axis radius.

Doh.  Will fix.  (Nothing in SVG reftests caught this ...)

> The other thing is that the rect algorithm is specified explicitly in the SVG
> specification. http://www.w3.org/TR/SVG/shapes.html#RectElement
> 
> As far as I can tell the reason you get differences is that the values of
> alpha are different.
[...]
> so you're going to have to convince me the RoundedRectangle
> implementation is a better approximation i.e. has a lower error than the SVG
> implementation.

I'll look at this in more detail when I get home.  The RoundedRectangle implementation is by no means sacred, but vlad did research it thoroughly.
The code points to http://www.spaceroots.org/documents/ellipse/elliptical-arc.pdf
as a key reference.

> btw I couldn't give you an sr even if it was right. You want roc for that.

noted.

Comment 5

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Interestingly, I didn't manage to find any better references other than the document at spaceroots, at least none showing the derivation of the alpha value.  However, with that search, I came across http://graphics.stanford.edu/courses/cs248-98-fall/Final/q1.html, which ends up with the 4*(sqrt(2)-1)/3 value.  Would be interesting to compare the errors of both.

Comment 6

[Zack Weinberg (:zwol)]

Attachment: comparison of alpha parameters

I did a numerical analysis of the two candidates for 'alpha' - the results are in the attached .pdf file.  (It's a large graph, so scalable is good, but R's SVG writer is not very good yet.)  You need to look at it in color.

All of the little subplots are to the same scale.  Each one shows the error in the Bezier approximation to a quarter-ellipse for a different ellipse aspect ratio (shown above each plot) - the x-axis is position along the Bezier curve, and the y-axis is the distance from the Bezier point to the nearest point on the true ellipse, as a percentage of the shorter of the two ellipse semi-axes.  (This somewhat odd choice of units is how I got all the plots to be to the same y-scale.)  The pink line is for Thebes' current choice of 'alpha', (sqrt(7)-1)/3; the blue line is for the SVG renderer's choice, 4*(sqrt(2)-1)/3.

Take-home observations:

 - Both values are pretty damn close.
 - However, the SVG renderer's alpha is clearly better at all aspect ratios.
 - That value is also better at distributing the error evenly along the curve.
 - In this fairly abstract analysis, the error curve is strictly a function
   of the aspect ratio; not of the absolute size of the ellipse, or its
   orientation.  That might not be true for a more realistic analysis that
   knew about things like pixel granularity.

I would've liked to run this out to much flatter ellipses but I ran into numerical stability problems, probably with R's polynomial root-finder.

I'll next attach the source code for the analysis, in case anyone wants to play with it.

Comment 7

[Zack Weinberg (:zwol)]

Attachment: ellipse error analyzer

This is the analysis that produced the graph in attachment 342978 [details].  Y'all probably haven't seen this language before; it's for the 'R' statistics system (http://www.r-project.org/)  I was considering doing some actual *statistics* on the errors but the graphical results were so obviously in favor of the SVG renderer's alpha that I didn't bother.

Comment 8

[Zack Weinberg (:zwol)]

Attachment: derivation of error polynomial

and, just in case anyone really wants to know, this is the derivation of the polynomial used in the 'ellipse.dist' function in attachment 342978 [details].

Comment 9

[Zack Weinberg (:zwol)]

er, that last should have been attachment 342980 [details].

Comment 10

[Zack Weinberg (:zwol)]

additional tidbit: this document <http://www.tinaja.com/glib/ellipse4.pdf> although short on details, proposes that one can get about 25% less average error than the usual alpha=4*(sqrt(2)-1)/3 by using a slightly smaller value (only given numerically) that constrains the points at 30° and 60° to be exact matches, rather than just the point at 45°.  The catch is, this means the curve is not convex everywhere; it's dented inward at 45°.  Before I go to a lot of trouble to derive an exact value for the adjusted alpha and confirm the assertions about average error, is that a fatal flaw?

Comment 11

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

(In reply to comment #10)
> additional tidbit: this document <http://www.tinaja.com/glib/ellipse4.pdf>
> although short on details, proposes that one can get about 25% less average
> error than the usual alpha=4*(sqrt(2)-1)/3 by using a slightly smaller value
> (only given numerically) that constrains the points at 30° and 60° to be exact
> matches, rather than just the point at 45°.  The catch is, this means the curve
> is not convex everywhere; it's dented inward at 45°.  Before I go to a lot of
> trouble to derive an exact value for the adjusted alpha and confirm the
> assertions about average error, is that a fatal flaw?

I don't think so -- honestly, noone is going to notice any of these differences, given that they are so far below the dpi of displays :)

Though I do wonder why the paper that I read's derivation of alpha results in a worse value... but I think that paper was solving for the general case for partial arcs as well as rotations, and the value of alpha falls out only after considering only 0..90 degrees in the equation, so that's entirely possible.

I'm happy with switching everything to use the SVG value if that's likely to be consistent with what other renderers are doing.

Comment 12

[Zack Weinberg (:zwol)]

(In reply to comment #11)
> Though I do wonder why the paper that I read's derivation of alpha results in a
> worse value... but I think that paper was solving for the general case for
> partial arcs as well as rotations, and the value of alpha falls out only after
> considering only 0..90 degrees in the equation, so that's entirely possible.

Yeah.  As I mentioned upthread, I'd like to see general elliptical arc code in the Thebes or maybe even Cairo layer eventually, and maybe we should revisit these questions then.  I would think, though, that the right way to do a partial arc is to calculate a spline for the entire ellipse that it's a subsegment of, and then use the usual algorithm for subdividing a bezier curve to cut them at the desired endpoints.  And I suspect that one could get better results for non-circular ellipses by *not* using the same factor for both intermediate control points.

But for right now I think the sanest thing to do is my patch + the radius fix + change the Thebes code to use what we've been calling the "svg value".  Then, if we figure out a better way to draw ellipses later, there will be fewer places to change.

By the way, the SVG implementation notes don't seem to contain any discussion of this part of the algorithm - just the center/endpoint parametrization conversion stuff.

Comment 13

[Robert Longson [:longsonr]]

The SVG code does say "See comp.graphics.algorithms FAQ 4.04" The FAQ contains references to other materials on the algorithm.

Comment 14

[cmtalbert]

Adding blocking ? because we need this to do better testing for border-radius which has landed in 1.9.1.

Comment 15

[Zack Weinberg (:zwol)]

Attachment: (rev 2) better alpha, fixed ellipse size

Here's a revised patch; the only differences are that I fixed the ellipses-are-half-the-size-they-should-be bug, and I substituted a new value for the 'alpha' parameter in the Thebes ellipse code after some research, updating the big long comment to match.

The author of the paper Vlad originally cited used a different set of constraints on the Bezier approximation than is standard.  The standard technique (as e.g. seen in the Stanford graphics course final, quoted above) is to force the curve to pass through the point halfway along the arc; that's how you get 4/3 (sqrt(2)-1) as seen in the c.g.a FAQ.  Maisonobe instead constrains the curvature at the endpoints to match the true curvature.  It doesn't appear that he tried the standard parametrization, because his own approach to estimating the maximum error (as reduplicated in my R analysis) gives much smaller error for the standard technique.

But you can do even better; both of the papers cited in the c.g.a FAQ (see patch for exact references) give a different 'alpha' that approximately halves the error, relative to the standard technique.  They use the same tactic as I mentioned in comment 10, i.e. noticing that the standard technique gives a curve that lies entirely outside the true ellipse, and so adjusting the parametrization to allow the curve to dip inside the true ellipse a bit.  Unlike the paper in comment 10, though, they give analytic expressions for the adjusted 'alpha'.  The numeric values come out the same, so I picked the analytic form that was simplest for the commentary in the patch.

I have yet to find anything other than the Maisonobe paper that discusses the error for a general ellipse, but it seems at least plausible that this value of alpha is also the best choice for an ellipse, because of the way Bezier curves scale (i.e. scaling the control points scales the curve).  Anyway, we can revisit that when we get around to pushing the general SVG elliptical arc code down into cairo.

Comment 16

[Zack Weinberg (:zwol)]

Comment on attachment 346972 [details] [diff] [review]
(rev 2) better alpha, fixed ellipse size

*sigh* review requestee fixed.

Comment 17

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 346972 [details] [diff] [review]
(rev 2) better alpha, fixed ellipse size

Looks good to me, fwiw!

Comment 18

[Robert Longson [:longsonr]]

Comment on attachment 346972 [details] [diff] [review]
(rev 2) better alpha, fixed ellipse size


This is fine, although I believe you're going to need tests to land it for firefox 3.1.

Comment 19

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

Comment on attachment 346972 [details] [diff] [review]
(rev 2) better alpha, fixed ellipse size

If you can write a test now that compares an SVG ellipse to a CSS rounded-rect, let's do it!

Comment 20

[Zack Weinberg (:zwol)]

roc: I tried to write a simple reftest, but failed.  We do now have exactly the same curve, but the antialiasing along the arc is still different.  I'll attach my attempt at a reftest in case someone who's better at SVG than me can fix it.

Comment 21

[Zack Weinberg (:zwol)]

Attachment: attempted reftest

Comment 22

[Zack Weinberg (:zwol)]

Attachment: attempted reftest reference

Comment 23

[cmtalbert]

I saw this new patch this morning.  I checked it with my sets of border-radius reftests and I'm still getting the same antiailiasing errors that you're getting with this test attempt.  It seems closer than without the patch, but we're still not there.  Can SVG do super small-scale dithering?  I'm scratching the bottom of the idea barrel on these border-radius tests.

Comment 24

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

What platform are you two testing on?  If OSX, you may be hitting two different renderers in use by apple, one pure software and one somewhat accelerated..

Comment 25

[Zack Weinberg (:zwol)]

I'm on Linux.  I'm going to instrument gfxContext::RoundedRectangle() tomorrow and see whether the arguments match.

Comment 26

[Martijn Wargers (dead)]

Related to bug 458985?

Comment 27

[cmtalbert]

I tested it on Mac OS X.  I'll try it this morning on Windows.

Comment 28

[cmtalbert]

Same results on Windows Vista with a debug pulled from today + this patch. (Tested using Zack's test above).

Comment 29

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 346972 [details] [diff] [review]
(rev 2) better alpha, fixed ellipse size

as per comments that the patch doesn't fix the bug, we can get this after beta2

Comment 30

[Zack Weinberg (:zwol)]

Attachment: (rev 3) with working test case

I figured out the test failures.  The code is correct as is, it just has to be tested a little more carefully than it appeared, because of an interaction with the background drawing code.

With the patch, an SVG <rect> element with fill and no stroke turns into a single Cairo path, which is filled.  The arguments to gfxContext::RoundedRectangle are what one would expect.  An HTML <div> element styled to be identical, however, fills the border area twice: once as part of the background, and then again as part of the border.  Because of the aliasing issues discussed in bug 456219, the border fill uses the same corner radii as SVG, but the background fill uses outer corner radii that are one pixel larger, and that's what's causing the reftest failures.

(For avoidance of confusion: this is *discussed* in bug 456219, but it isn't actually what that bug is aiming to solve.)

This can be worked around in the test case; we just need to not give the <div> element a background style at all; instead I nest another <div> inside it to fill in the padding-box.

I hope we can land this finally?

Comment 31

[Robert Longson [:longsonr]]

See bug 465996 which is relevant to the Arc->Ellipse change. I think we should drop the Arc->Ellipse change from this bug as it seems only tangentially related. We can then do the Arc->Ellipse work in bug 45996 if the consensus is in that bug that that's the way to go.

Comment 32

[Zack Weinberg (:zwol)]

(In reply to comment #31)
> See bug 465996 which is relevant to the Arc->Ellipse change. I think we should
> drop the Arc->Ellipse change from this bug as it seems only tangentially
> related.

I assume you're referring to the changes to nsSVGEllipseElement?  Sure, whatever.

Comment 33

[Zack Weinberg (:zwol)]

Attachment: (rev 4) leaving nsSVGEllipseElement alone

as requested by longsonr, this revision only changes the behavior of SVG rounded rects, not SVG ellipses.

Comment 34

[Mike Beltzner [:beltzner, not reading bugmail]]

Does this patch need a new review, if it's doing something different, or is it a direct subset of the reviewed patch?

Comment 35

[Robert Longson [:longsonr]]

Functionally it is a direct subset of the rev2 reviewed patch, except that this version has some lovely bonus tests included too.

Comment 36

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 349868 [details] [diff] [review]
(rev 4) leaving nsSVGEllipseElement alone

a191=beltzner

Comment 37

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Landed on mozilla-central:
http://hg.mozilla.org/mozilla-central/rev/002d3e5ba80f

(Still needs to land on 1.9.1.)


Marking bug as fixed, although it's not 100% clear to me that this bug is fully fixed by the patch.  Please reopen or file additional bugs as necessary if that's not the case.

Comment 38

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Landed on 1.9.1: http://hg.mozilla.org/releases/mozilla-1.9.1/rev/925390eb6aff

Comment 39

[Zack Weinberg (:zwol)]

dbaron: I think any remaining work is covered by bug 465996.

Comment 40

[cmtalbert]

Verified on Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.2a1pre) Gecko/20081212 Minefield/3.2a1pre