Quantcast

Recent change to ellipse to path conversion method?

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Recent change to ellipse to path conversion method?

mathog
Earlier today I found one small bug related to images written to WMF
files and posted it in launchpad.  But while working on that noticed
that there was also another binary change in the output that didn't
correspond to anything I could see in the images.  A careful byte by
byte comparison of EMF and WMF output from the lp988601 and current
trunk branches showed that outside of my code there has been a change,
where the paths returned on ellipse to path conversions are not as they
once were.  In emf-print.cpp in the print_simple_shape() routine a print
statement was added after the call to
pathv_to_linear_and_cubic_beziers() and the loop which adds up nodes,
lines, and curves.  For the exact same ellipse (long axis aligned with
x, short with y, axis ratio about 2:1) this is what was found:

              nodes   lines   curves
lp988601         5       0        4
trunk            9       0        8

They start at the same point, but differ from there.  Tried it again
with perfect circles and got the same result.

The strange thing is that there is no change at all to the geom.cpp
file, where pathv_to_linear_and_cubic_beziers() is coded.

I also checked to see if anything similar could be seen in the GUI, and
it sort of could be.  Select the ellipse, select "stroke to path", then
edit points.  The points on the ellipse are in different places in the
two branches, and there are different numbers of points.  For lp988602
there is one point on the end of each axis plus one point in roughly the
center of each quadrant. For trunk there are the same points on the ends
of the axis, plus two points within each quadrant, and these are
clustered towards the "sharp" ends of the ellipse.

Is this change intentional???

Thank you,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Markus Engel
Hi,
intentional is the wrong word. This has to do with the change that ellipses
are represented now as true elliptical arcs. These are converted implicitly
to several Bezier segments.
pathv_to_linear_and_cubic_beziers() does this conversion using a certain
"tolerance". Thus, if the elliptical arc and the bezier curve differ too
much, a new node is inserted automatically.
Currently I'm thinking about a solution, as this is not quite user-friendly.
One of my ideas was that we could introduce a new tab in the settings dialog
where you can choose the tolerances for these path conversions yourself.
So the average user could choose a high tolerance and get fewer (at least 4)
nodes, the cad user who needs high precision, could set the tolerance to a
small value.

What do you think?

Regards,
Markus

-----Urspr√ľngliche Nachricht-----
Von: mathog [mailto:[hidden email]]
Gesendet: Freitag, 18. Oktober 2013 23:25
An: Inkscape Devel
Betreff: [Inkscape-devel] Recent change to ellipse to path conversion
method?

Earlier today I found one small bug related to images written to WMF files
and posted it in launchpad.  But while working on that noticed that there
was also another binary change in the output that didn't correspond to
anything I could see in the images.  A careful byte by byte comparison of
EMF and WMF output from the lp988601 and current trunk branches showed that
outside of my code there has been a change, where the paths returned on
ellipse to path conversions are not as they once were.  In emf-print.cpp in
the print_simple_shape() routine a print statement was added after the call
to
pathv_to_linear_and_cubic_beziers() and the loop which adds up nodes, lines,
and curves.  For the exact same ellipse (long axis aligned with x, short
with y, axis ratio about 2:1) this is what was found:

              nodes   lines   curves
lp988601         5       0        4
trunk            9       0        8

They start at the same point, but differ from there.  Tried it again with
perfect circles and got the same result.

The strange thing is that there is no change at all to the geom.cpp file,
where pathv_to_linear_and_cubic_beziers() is coded.

I also checked to see if anything similar could be seen in the GUI, and it
sort of could be.  Select the ellipse, select "stroke to path", then edit
points.  The points on the ellipse are in different places in the two
branches, and there are different numbers of points.  For lp988602 there is
one point on the end of each axis plus one point in roughly the center of
each quadrant. For trunk there are the same points on the ends of the axis,
plus two points within each quadrant, and these are clustered towards the
"sharp" ends of the ellipse.

Is this change intentional???

Thank you,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

----------------------------------------------------------------------------
--
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most
from the latest Intel processors and coprocessors. See abstracts and
register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel


------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

mathog
On 18-Oct-2013 14:58, Markus Engel wrote:
> This has to do with the change that ellipses
> are represented now as true elliptical arcs. These are converted
> implicitly
> to several Bezier segments.

As far as the output to other formats goes this was always the case,
just not to as many segments as now.

> pathv_to_linear_and_cubic_beziers() does this conversion using a
> certain
> "tolerance".

Right, but that code didn't change, so I assume this is the result of
the default tolerance being made smaller.

> Currently I'm thinking about a solution, as this is not quite
> user-friendly.
> One of my ideas was that we could introduce a new tab in the settings
> dialog
> where you can choose the tolerances for these path conversions
> yourself.

That sounds good.  Can the default value please go back to where it was?
  I don't recall hearing a lot of people complaining about a lack of
precision in the representation of ellipses and the tolerance change
resulted in unexpected output differences.

I suppose you also need to make a distinction between what is going on
on the drawing surface and the precision on a forced conversion to
another format.  Lots of graphics drivers have precision settings that
affect what is seen on the display but which do not change the
underlying data representation.  This is super common for "smoothness"
settings on 3D rendering, for instance.  The current change seems to
affect both.  "Screen tolerance" and "Conversion tolerance", if you
will.

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Markus Engel
> As far as the output to other formats goes this was always the case, just not to as many segments as now.
> Right, but that code didn't change, so I assume this is the result of the default tolerance being made smaller.

The default tolerance didn't change but the code in sp-ellipse.cpp did. A few revisions ago the ellipses were created by explicitly calculating four Bezier (!) curves so there was no need for any conversion. Now I changed this to creating elliptical arcs and let 2geom do the calculation. Have a look at this bug report: https://bugs.launchpad.net/inkscape/+bug/1235504 .
Try the patch I attached there (e_to_b.patch). This increases the tolerance to an arbitrary value of 1, so only for quite big ellipses more than four nodes are generated.
Of course this value should be accessible via a settings tab later. Would this be an acceptable solution then?

Regards,
Markus

-----Urspr√ľngliche Nachricht-----
Von: system user for webserver-base [mailto:[hidden email]] Im Auftrag von mathog
Gesendet: Samstag, 19. Oktober 2013 00:19
An: Markus Engel
Cc: 'Inkscape Devel'
Betreff: Re: AW: [Inkscape-devel] Recent change to ellipse to path conversion method?

On 18-Oct-2013 14:58, Markus Engel wrote:
> This has to do with the change that ellipses are represented now as
> true elliptical arcs. These are converted implicitly to several Bezier
> segments.

As far as the output to other formats goes this was always the case, just not to as many segments as now.

> pathv_to_linear_and_cubic_beziers() does this conversion using a
> certain "tolerance".

Right, but that code didn't change, so I assume this is the result of the default tolerance being made smaller.

> Currently I'm thinking about a solution, as this is not quite
> user-friendly.
> One of my ideas was that we could introduce a new tab in the settings
> dialog where you can choose the tolerances for these path conversions
> yourself.

That sounds good.  Can the default value please go back to where it was?
  I don't recall hearing a lot of people complaining about a lack of precision in the representation of ellipses and the tolerance change resulted in unexpected output differences.

I suppose you also need to make a distinction between what is going on on the drawing surface and the precision on a forced conversion to another format.  Lots of graphics drivers have precision settings that affect what is seen on the display but which do not change the underlying data representation.  This is super common for "smoothness"
settings on 3D rendering, for instance.  The current change seems to affect both.  "Screen tolerance" and "Conversion tolerance", if you will.

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech


------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

mathog
On 18-Oct-2013 15:32, Markus Engel wrote:
> The default tolerance didn't change but the code in sp-ellipse.cpp
> did. A few revisions ago the ellipses were created by explicitly
> calculating four Bezier (!) curves so there was no need for any
> conversion. Now I changed this to creating elliptical arcs and let
> 2geom do the calculation. Have a look at this bug report:
> https://bugs.launchpad.net/inkscape/+bug/1235504 .
> Try the patch I attached there (e_to_b.patch).

I see it, but don't understand why:

   Geom::cubicbezierpath_from_sbasis

generates so many beziers for an elliptical arc with a fit parameter of
0.1.

Ellipses are approximated very well by 4 beziers.  Presumably the
EllipticalArcs you use now are perfect segments of an Ellipse.
(Otherwise, why bother with them? How many are you using, 4?)  I would
have assumed that an Elliptical arc perfectly representing 1/4 of an
ellipse should have converted as well to a single Bezier curve as 1/4 of
the ellipse did.  Or was the conversion from some other function and not
cubicbezierpath_from_sbasis()?  The patch changes the fit parameter from
0.1 to 1.0, which seems like an awfully big change to make it do what
you want.  Is it maybe the case that somehow the
cubicbezierpath_from_sbasis() algorithm starts with the assumption that
it must use at least two bezier segments, that is, that it must split
the curve into >=2 Beziers, and only omits the second one with an
extreme parameter change?

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Nathan Hurst
Hi mathog,

On Fri, Oct 18, 2013 at 04:07:16PM -0700, mathog wrote:
> I see it, but don't understand why:
>
>    Geom::cubicbezierpath_from_sbasis
>
> generates so many beziers for an elliptical arc with a fit parameter of
> 0.1.

Because Geom::cubicbezierpath_from_sbasis is fitting the
parameterisation rather than the geometric shape.  That is, we think
of a path as a pair of functions X(t), Y(t) with t in [0,1], but any
function t(u) such that t([0,1]) = [0,1] gives another path X(t(u)),
Y(t(u)) which is the same path.  There is a best path approximation if
we're allowed to change the parameterisation, and for circular arcs
this has been worked out explicitly.  This function, however,
minimises |X(t) - Bezier(t)| over t, rather than |X(t) - Bezier(u)|
over t,u.

There have been papers published on ways to do this efficiently in
general (one search term is geometric interpolation).  Nobody has
implemented a competitive algorithm.  I would recommend modifying the
ellipse code to use the known approximation directly rather than going
via sbasis (or equivalently, generating the approximation in sbasis
form rather than using sin,cos in which case
Geom::cubicbezierpath_from_sbasis should be the identity).

regards,
njh

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

mathog
On 20-Oct-2013 14:35, Nathan Hurst wrote:
> There have been papers published on ways to do this efficiently in
> general (one search term is geometric interpolation).  Nobody has
> implemented a competitive algorithm.  I would recommend modifying the
> ellipse code to use the known approximation directly rather than going
> via sbasis (or equivalently, generating the approximation in sbasis
> form rather than using sin,cos in which case
> Geom::cubicbezierpath_from_sbasis should be the identity).

Recapitulating:

1.  The original ellipse -> bezier conversion used one of the worked out
solutions which are calculated directly from the ellipse parameters.  
Probably something like this:

    http://www.spaceroots.org/documents/ellipse/

It produced four beziers for any ellipse.  These met the needs of most
users.

2.  Higher precision curve drawing of ellipses was required by some end
users for CAD purposes, so the method was changed.  This resulted in the
default bezier representation of an ellipse being more complex (>4
beziers) than needed for general use.  The new method uses a fit
parameter which must be changed in a major way from its default value in
order to return to beziers similar to (1), and there is currently no way
to do this in the GUI.  (Unsure: that same parameter is used for other
curve -> bezier conversions?  Does the end user need to be able to
adjust the fit parameter?)

So far so good?

The issue then is how to allow those who need it to obtain a higher
precision conversion to beziers without requiring that the average user
know anything about it.  I suggest that the usual solution to this sort
of problem, as applied to Inkscape, would be to modify the toolbar for
elliptical drawing to add a "precision" field that normally reads
"Default", with other options perhaps called "CAD Low","CAD Medium","CAD
High".  Each corresponds to a parameter value, but that is not shown to
the end user, in case things need to be changed around again at some
point in future.  Exposing the parameter value is unlikely to be helpful
to most users, since it probably will not correspond in a simple way to
an easily comprehended measure of error.  The bezier generating code
looks at this parameter, and when it sees the one corresponding to
"Default" it uses the original algorithm, for all of the others it uses
Geom::cubicbezierpath_from_sbasis.

In terms of usability that should be fine, and adding the control will
not be hard.  However, algorithmically I am guessing that
Geom::cubicbezierpath_from_sbasis is not as efficient as using some
partially precalculated method which uses the a/b ratio of the ellipse
in question, at least for whole ellipses.  For circles in particular
symmetry suggests that there must be an extremely efficient method of
determining the best set of Beziers for a given measure of fit.

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Markus Engel
> 1.  The original ellipse -> bezier conversion used one of the worked out solutions which are calculated directly from the ellipse parameters.  
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/12550/src/sp-ellipse.cpp#L197

    for (s = this->start; s < this->end; s += M_PI_2) {
        double e = s + M_PI_2;

        if (e > this->end) {
            e = this->end;
        }

        len = 4*tan((e - s)/4)/3;
        double x0 = cos(s);
        double y0 = sin(s);
        double x1 = x0 + len * cos(s + M_PI_2);
        double y1 = y0 + len * sin(s + M_PI_2);
        double x3 = cos(e);
        double y3 = sin(e);
        double x2 = x3 + len * cos(e - M_PI_2);
        double y2 = y3 + len * sin(e - M_PI_2);

        curve->curveto(x1,y1, x2,y2, x3,y3);
    }


> It produced four beziers for any ellipse.  These met the needs of most users.
That's correct.

> 2.  Higher precision curve drawing of ellipses was required by some end users for CAD purposes, so the method was changed.
It wasn't required (it's a nice feature though), but using 2geom for calculation is just so much easier and the preferred way to go:
        Geom::Circle circle(0, 0, 1);
        Geom::PathVector path;

        circle.getPath(path);

        curve = new SPCurve(path);
        curve->closepath();
That's it.

> This resulted in the default bezier representation of an ellipse being more complex (>4 beziers) than needed for general use.
> The new method uses a fit parameter which must be changed in a major way from its default value in order to return to beziers similar to (1),
> and there is currently no way to do this in the GUI.
Right.

 > (Unsure: that same parameter is used for other curve -> bezier conversions?  Does the end user need to be able to adjust the fit parameter?)
As soon as you modify a path using the node tool, all the curves the path consists of are converted to cubic Bezier curves. Currently, for all these conversions the fit parameter is 0.1.

> The issue then is how to allow those who need it to obtain a higher precision conversion to beziers without requiring that the average user know anything about it.  I suggest that the usual solution to this sort of problem, as applied to Inkscape, would be to modify the toolbar for elliptical drawing to add a "precision" field that normally reads "Default", with other options perhaps called "CAD Low","CAD Medium","CAD High".  Each corresponds to a parameter value, but that is not shown to the end user, in case things need to be changed around again at some point in future.  Exposing the parameter value is unlikely to be helpful to most users, since it probably will not correspond in a simple way to an easily comprehended measure of error.  The bezier generating code looks at this parameter, and when it sees the one corresponding to "Default" it uses the original algorithm, for all of the others it uses Geom::cubicbezierpath_from_sbasis.

Putting the precision settting into the settings dialog seems better to me. Either you need to increase it or you don't. Usually, you won't change it all the time. So the average user won't even notice this option exists.

Regards,
Markus


------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

mathog
On 21-Oct-2013 14:34, Markus Engel wrote:
> Putting the precision setting into the settings dialog seems better
> to me.

Do you mean

   edit->preferences->shapes->ellipse #add to existing entry

or

   edit->preferences->behavior->Path conversion  #new entry in menu

or some other place?

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Markus Engel
>   edit->preferences->behavior->Path conversion  #new entry in menu
That'd be the right place I think.

Regards,
Markus


------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

mathog
On 21-Oct-2013 15:32, Markus Engel wrote:
>>   edit->preferences->behavior->Path conversion  #new entry in menu
> That'd be the right place I think.

That would be fine by me.

Regards,

David Mathog
[hidden email]
Manager, Sequence Analysis Facility, Biology Division, Caltech

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

alvinpenner
    after looking a bit at the routine  sbasis-to-bezier.cpp, it appears that the tolerance tol is expressed in absolute units such as pixels, rather than being relative to the size of the object. So it will be more difficult to satisfy for large objects. Is this a case where we could consider a relative tolerance, such as 0.001 of the radius or somesuch?
    as far as I understand it, the conversion of Beziers to sbasis, and vice-versa, is always lossless, so the issue should only arise for arcs, I believe. (If at all humanly possible, I think options in the Preferences to choose this tolerance should be avoided at all costs, on the grounds that no one will know what this means.)

Alvin
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

alvinpenner
    I think one could argue that the current formula for calculating the error, tail_error(B, 2), in build_from_sbasis() in sbasis-to-bezier.cpp is unnecessarily pessimistic, due to recent changes in the code. The tolerance on the error is 0.1. The error is linear in the radius of the arc. The dividing point in switching from 4 beziers to 8, for a full circle, occurs at r = 8.18. The dividing point in switching from 8 beziers to 16, for a full circle, occurs at r = 107.4. This can be confirmed using Path->Object-To-Path.
    Numerical tests at different arc angles have indicated that the tail_error function is roughly given by 0.0026*r*(theta)^4, where theta is in radians. This is consistent with the way in which the Bezier approximation used to be done. Recalling a previous thread on this subject:
http://article.gmane.org/gmane.comp.graphics.inkscape.devel/35435
the arm length of the Bezier approximation to an arc was given by:

d/r = theta/3, where d = Bezier control arm length

The resulting fit will be worst at t=0.5 and the Bezier radius at this point will be:

r(t = 0.5) = cos(theta/2) + (theta/4)*sin(theta/2)

The error, for a unit circle, is roughly given by:

error = -(theta)^4/24/16

which is consistent with the previous numerical tests of tail_error.

    The code in sbasis-to-bezier.cpp has been modifed (lib2geom rev 2122) to use a different approach to the fit, one which fits the sbasis curve at t=0.5. In the case of arcs, this is consistent with a Bezier arm length of:

d/r = 4*tan(theta/4)/3

The Bezier radius will be correct at t = 0, 0.5, and 1. The maximum error in radius will occur at t values which satisfy the equation 6*t*(1-t) = 1. The maximum radius is given by:

r^2 = 1 + (4/27)*(sin(theta/4))^6/(cos(theta/4))^2

The error, for a unit circle, is roughly given by:

error = (2/27)*(theta/4)^6

This is significantly smaller than the previous estimate (about 55 times smaller for an arc of 90 degrees), and would allow larger arc radii to be used without subdivision of the Bezier curves.

Unfortunately, I do not have sufficient math fu to do this type of analysis directly in the sbasis representation, but I think it would be worthwhile to try to perform such an error analysis.

Cheers,
Alvin
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

alvinpenner
    The behaviour of the tail_error(B, n) function in build_from_sbasis() in the file sbasis-to-bezier.cpp has been reevaluated. The term tail_error(B, 2) is too large since it is of order 4 in theta, for an arc, while the error currently produced is of order 6 in theta. For this reason the term tail_error(B, 3) was investigated numerically to see how it behaves. By numerical printouts at different theta, it was found that for a unit circle the tail_error(B, 3) term is roughly given by : 0.000022*(theta)^6.
    This agrees surprisingly well with the formula given above for the case where the sbasis is fit at t = 0.5. The formula given above was: error = (2/27)*(theta/4)^6. The difference between these results is only 20%, which I find surprising given the very different histories of the two calculations.
    In any event, I would like to propose that the term tail_error(B, 3) be used to determine the error estimate when bisecting the sbasis curves to meet the required tolerance. If this is done, numerical tests indicate that the dividing point in switching from 4 Beziers to 8 Beziers for a full circle will occur at r = 407 instead of the current r = 8.18.

cheers,
Alvin
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

Nathan Hurst
On Sat, Nov 30, 2013 at 06:50:06AM -0800, alvinpenner wrote:

>     The behaviour of the tail_error(B, n) function in build_from_sbasis() in
> the file sbasis-to-bezier.cpp has been reevaluated. The term tail_error(B,
> 2) is too large since it is of order 4 in theta, for an arc, while the error
> currently produced is of order 6 in theta. For this reason the term
> tail_error(B, 3) was investigated numerically to see how it behaves. By
> numerical printouts at different theta, it was found that for a unit circle
> the tail_error(B, 3) term is roughly given by : 0.000022*(theta)^6.
>     This agrees surprisingly well with the formula given above for the case
> where the sbasis is fit at t = 0.5. The formula given above was: error =
> (2/27)*(theta/4)^6. The difference between these results is only 20%, which
> I find surprising given the very different histories of the two
> calculations.
>     In any event, I would like to propose that the term tail_error(B, 3) be
> used to determine the error estimate when bisecting the sbasis curves to
> meet the required tolerance. If this is done, numerical tests indicate that
> the dividing point in switching from 4 Beziers to 8 Beziers for a full
> circle will occur at r = 407 instead of the current r = 8.18.

Hi Alvin,

Good sluthing!

This is puzzling, I think it must be due to the fact that you are
using geometric subdivision (putting the new control points on the
circle) rather than parametric (subdividing the higher order splines),
because the tail_error(B, 2) value should be fairly tight.  Can you
check the analysis and see if we didn't make a silly out-by-one error
in the api.

I agree with your assessment though, let's switch to tail_error(B, 3)
and see if anyone complains.

njh

------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349351&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recent change to ellipse to path conversion method?

alvinpenner
thanks, change from (B, 2) to (B, 3) committed to rev 2159 of lib2geom.

- Alvin
Loading...