Problem with Agg Ellipses

There appears to be an issue with the agg backend with how
it is drawing ellipses (or maybe it is how matplotlib uses agg), but the
attached script shows how a point, which should be coincident with the center
circle, but it is not. The second plot shows the same data, but using a
custom (and much slower) algorithm for drawing the ellipses, where the point is
properly coincident.

The problem appears to be with the way that agg discretizes
its Bezier curves before drawing. It does not take into account the scale
of the curve on in the viewable region of the rendering device.

I think that ideally this would be fixed in the agg side
since then there would be the smallest of performance hits but matplotlib could
attempt to work around it by specifying more points on the ellipse curve…

ellipseResolution.py (3.01 KB)

Thanks for the test case James -- I will try and sort this out ASAP.
Michael, do you see the same on the transforms branch? The branch is
on a newer version of agg so if not, perhaps it is a simple matter of
upgrading agg on the trunk. I'm travelling currently bt will be back
omorrow and ill look at this ASAP.

JDH

···

On Dec 7, 2007 6:02 PM, James Evans <jrevans1@...310...> wrote:

There appears to be an issue with the agg backend with how it is drawing
ellipses (or maybe it is how matplotlib uses agg), but the attached script
shows how a point, which should be coincident with the center circle, but it
is not. The second plot shows the same data, but using a custom (and much
slower) algorithm for drawing the ellipses, where the point is properly
coincident.

I found a great doc I am linking. The 4 spline method we are using
has an error tolerance of 2.7*10^-4, which I am pretty sure is coming
into play here. If we move to an 8 spline approach, it would reduce
the error a few orders of magnitude.

- Charlie

···

On Dec 8, 2007 9:09 AM, John Hunter <jdh2358@...149...> wrote:

On Dec 7, 2007 6:02 PM, James Evans <jrevans1@...310...> wrote:

> There appears to be an issue with the agg backend with how it is drawing
> ellipses (or maybe it is how matplotlib uses agg), but the attached script
> shows how a point, which should be coincident with the center circle, but it
> is not. The second plot shows the same data, but using a custom (and much
> slower) algorithm for drawing the ellipses, where the point is properly
> coincident.

Thanks for the test case James -- I will try and sort this out ASAP.
Michael, do you see the same on the transforms branch? The branch is
on a newer version of agg so if not, perhaps it is a simple matter of
upgrading agg on the trunk. I'm travelling currently bt will be back
omorrow and ill look at this ASAP.

JDH

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

I did some more digging and it looks like this changed with the
transforms. curve4 is now being called instead of arc_to, which uses
beziers.

···

On Dec 9, 2007 10:11 AM, Charlie Moad <cwmoad@...149...> wrote:

I found a great doc I am linking. The 4 spline method we are using
has an error tolerance of 2.7*10^-4, which I am pretty sure is coming
into play here. If we move to an 8 spline approach, it would reduce
the error a few orders of magnitude.

http://www.tinaja.com/glib/ellipse4.pdf

- Charlie

On Dec 8, 2007 9:09 AM, John Hunter <jdh2358@...149...> wrote:
> On Dec 7, 2007 6:02 PM, James Evans <jrevans1@...310...> wrote:
>
> > There appears to be an issue with the agg backend with how it is drawing
> > ellipses (or maybe it is how matplotlib uses agg), but the attached script
> > shows how a point, which should be coincident with the center circle, but it
> > is not. The second plot shows the same data, but using a custom (and much
> > slower) algorithm for drawing the ellipses, where the point is properly
> > coincident.
>
> Thanks for the test case James -- I will try and sort this out ASAP.
> Michael, do you see the same on the transforms branch? The branch is
> on a newer version of agg so if not, perhaps it is a simple matter of
> upgrading agg on the trunk. I'm travelling currently bt will be back
> omorrow and ill look at this ASAP.
>
> JDH
>
> -------------------------------------------------------------------------
> SF.Net email is sponsored by:
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> Matplotlib-devel mailing list
> Matplotlib-devel@lists.sourceforge.net
> matplotlib-devel List Signup and Options
>

Charlie Moad wrote:

I did some more digging and it looks like this changed with the
transforms. curve4 is now being called instead of arc_to, which uses
beziers.

curve4 is the way to specify a cubic bezier curve, so it is functionally equivalent to the old arc_to approach (but easier to be consistent across backends, which is why the change was made).

I'm attempting to implement the 8-spline approximation and I'll let you know how that goes. In any case, I think we should add James' example to our unit tests, since it illustrates a case where my assumptions about how ellipses would be used breaks down.

Cheers,
Mike

···

On Dec 9, 2007 10:11 AM, Charlie Moad <cwmoad@...149...> wrote:

I found a great doc I am linking. The 4 spline method we are using
has an error tolerance of 2.7*10^-4, which I am pretty sure is coming
into play here. If we move to an 8 spline approach, it would reduce
the error a few orders of magnitude.

http://www.tinaja.com/glib/ellipse4.pdf

- Charlie

On Dec 8, 2007 9:09 AM, John Hunter <jdh2358@...149...> wrote:

On Dec 7, 2007 6:02 PM, James Evans <jrevans1@...310...> wrote:

There appears to be an issue with the agg backend with how it is drawing
ellipses (or maybe it is how matplotlib uses agg), but the attached script
shows how a point, which should be coincident with the center circle, but it
is not. The second plot shows the same data, but using a custom (and much
slower) algorithm for drawing the ellipses, where the point is properly
coincident.

Thanks for the test case James -- I will try and sort this out ASAP.
Michael, do you see the same on the transforms branch? The branch is
on a newer version of agg so if not, perhaps it is a simple matter of
upgrading agg on the trunk. I'm travelling currently bt will be back
omorrow and ill look at this ASAP.

JDH

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

Michael Droettboom wrote:

Charlie Moad wrote:

I did some more digging and it looks like this changed with the
transforms. curve4 is now being called instead of arc_to, which uses
beziers.

curve4 is the way to specify a cubic bezier curve, so it is functionally equivalent to the old arc_to approach (but easier to be consistent across backends, which is why the change was made).

Sorry, I was confused... John recently fixed the ellipse drawing on the trunk (which was broken wrt rotated ellipses), to use bezier curves instead of agg's arc_to. Agg's arc_to itself isn't broken wrt to James' problem -- in fact it does provide sufficient accuracy -- it was the way mpl used arc_to in previous incarnations that was broken wrt rotated ellipses. Unfortunately, the fix for that reduced accuracy to noticable levels on these really large ellipses. So, in order to have the best of both worlds, I agree the 8-spline approximation seems like the way to go.

(But the changes on the transforms branch are irrelevant here -- they do essentially the same thing the trunk currently does: that is 4 spline approximation of the circle).

I'm attempting to implement the 8-spline approximation and I'll let you know how that goes.

I have 8-spline approximation working on the trunk and on the transforms branch. (r4679)

In the process, I uncovered another bug (which I suppose should have been obvious when ellipses were updated last time, but went right by me) -- ellipses don't work at all in the pdf, svg or cairo backends, since they don't implement draw_path. I'll file a placeholder bug for this, and hopefully get to it, time permitting.

In any case, I think we should add James' example to our unit tests, since it illustrates a case where my assumptions about how ellipses would be used breaks down.

Also done.

Cheers,
Mike

···

On Dec 9, 2007 10:11 AM, Charlie Moad <cwmoad@...149...> wrote:

I found a great doc I am linking. The 4 spline method we are using
has an error tolerance of 2.7*10^-4, which I am pretty sure is coming
into play here. If we move to an 8 spline approach, it would reduce
the error a few orders of magnitude.

http://www.tinaja.com/glib/ellipse4.pdf

- Charlie

On Dec 8, 2007 9:09 AM, John Hunter <jdh2358@...149...> wrote:

On Dec 7, 2007 6:02 PM, James Evans <jrevans1@...310...> wrote:

There appears to be an issue with the agg backend with how it is drawing
ellipses (or maybe it is how matplotlib uses agg), but the attached script
shows how a point, which should be coincident with the center circle, but it
is not. The second plot shows the same data, but using a custom (and much
slower) algorithm for drawing the ellipses, where the point is properly
coincident.

Thanks for the test case James -- I will try and sort this out ASAP.
Michael, do you see the same on the transforms branch? The branch is
on a newer version of agg so if not, perhaps it is a simple matter of
upgrading agg on the trunk. I'm travelling currently bt will be back
omorrow and ill look at this ASAP.

JDH

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

Thanks Michael, I was working on this myself but it is hard for me to
keep up with you :slight_smile:

In reading the paper Charlie sent and links therein
(http://www.tinaja.com/glib/ellipse4.pdf and
http://itc.ktu.lt/itc354/Riskus354.pdf), one comment was that the
usual magic number

offset = 4.0 * (npy.sqrt(2) - 1) / 3.0

is not ideal. When I tested the JPLs test script with one of the
suggested magic numbers which minimize the SS errors with 4 points on
the ellipse, the error was smaller than what we were getting with the
one above (I used k=0.55191496 from the Rivus paper). I see you are
using a different formula for the magic number in the trunk. Do you
think we could see additional accuracy with a different magic number
as discussed in these papers?

JDH

···

On Dec 10, 2007 8:51 AM, Michael Droettboom <mdroe@...31...> wrote:

I have 8-spline approximation working on the trunk and on the transforms
branch. (r4679)

John Hunter wrote:

I have 8-spline approximation working on the trunk and on the transforms
branch. (r4679)

Thanks Michael, I was working on this myself but it is hard for me to
keep up with you :slight_smile:

No problem. I wasn't sure if you were still on vacation... Feel free to replace mine with whatever you came up with if you see further benefit.

In reading the paper Charlie sent and links therein
(http://www.tinaja.com/glib/ellipse4.pdf and
http://itc.ktu.lt/itc354/Riskus354.pdf), one comment was that the
usual magic number

offset = 4.0 * (npy.sqrt(2) - 1) / 3.0

is not ideal. When I tested the JPLs test script with one of the
suggested magic numbers which minimize the SS errors with 4 points on
the ellipse, the error was smaller than what we were getting with the
one above (I used k=0.55191496 from the Rivus paper).

The first thing I tried when I saw Lancaster's paper (from Charlie's e-mail) was to leave it as four splines and use his suggested number of 0.551784. That improved things for James' example, but not nearly enough. There were still around 10 pixels between where the ellipses should be and where they were. It's possible that an even better magic number exists (I gather Lancaster's was arrived at by experimentation), but I was doubtful that one could be found that would be as good as just going to 8 splines.

I see you are
using a different formula for the magic number in the trunk. Do you
think we could see additional accuracy with a different magic number
as discussed in these papers?

For the 8 spline approximation I put in the trunk this morning, I used Lancaster's suggested magic number of 0.2652031. (MAGIC45 is just the rectilinear distance of the MAGIC number at a 45 degree angle). Again, feel free to tinker, but that number seemed "good enough" on James' example.

Cheers,
Mike

···

On Dec 10, 2007 8:51 AM, Michael Droettboom <mdroe@...31...> wrote:

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

Everyone,
Before someone spends a lot of time re-working the ellipse code to add more splines, I think we should talk about the problem and maybe consider another approach.

The real problem w/ this for us is that we plot a lot of things at interplanetary scales (millions of kilometers). Even 1e-6 accuracy is still a miss of a kilometer (assuming that error tolerance is related to r).

What we really need is something that is viewport (i.e. the data range being currently viewed) dependent. The errors for the 4 spline case are fine as long as it's a spline through 4 points that are in the viewport window. So if I have an ellipse that's 3 million by 5 million and I'm viewing the whole thing on a plot, 1e-4 of 3e6 is fine. However, if I've zoomed in to a portion of the ellipse and my current axes bounds are 10 km x 10 km, then 1e-4 isn't fine AND 1e-6 isn't fine either. If we could recompute the curve based on the current zoom level, then 1e-4 is fine again.

One way to think about this is as error in pixels (since that's what the user is actually looking at). It would be nice if the pixel error could be held constant. Let's say that one pixel is the error we're going for. Any system that gives a one pixel error at arbitrary zoom levels is the way to go. A system with an error expressed in data coordinates will always have problems at some arbitrary zoom level.

I don't know if the current MPL architecture can support this but it would be nice if it worked that way. We have people making decisions based on what these plots show that affect spacecraft worth hundreds of millions of dollars so it's important that we're plotting things accurately.

Ted

···

At 07:26 AM 12/10/2007, Michael Droettboom wrote:

John Hunter wrote:
> On Dec 10, 2007 8:51 AM, Michael Droettboom <mdroe@...31...> wrote:
>
>> I have 8-spline approximation working on the trunk and on the transforms
>> branch. (r4679)
>
> Thanks Michael, I was working on this myself but it is hard for me to
> keep up with you :slight_smile:

No problem. I wasn't sure if you were still on vacation... Feel free
to replace mine with whatever you came up with if you see further benefit.

> In reading the paper Charlie sent and links therein
> (<http://www.tinaja.com/glib/ellipse4.pdf >http://www.tinaja.com/glib/ellipse4.pdf and
> http://itc.ktu.lt/itc354/Riskus354.pdf), one comment was that the
> usual magic number
>
> offset = 4.0 * (npy.sqrt(2) - 1) / 3.0
>
> is not ideal. When I tested the JPLs test script with one of the
> suggested magic numbers which minimize the SS errors with 4 points on
> the ellipse, the error was smaller than what we were getting with the
> one above (I used k=0.55191496 from the Rivus paper).

The first thing I tried when I saw Lancaster's paper (from Charlie's
e-mail) was to leave it as four splines and use his suggested number of
0.551784. That improved things for James' example, but not nearly
enough. There were still around 10 pixels between where the ellipses
should be and where they were. It's possible that an even better magic
number exists (I gather Lancaster's was arrived at by experimentation),
but I was doubtful that one could be found that would be as good as just
going to 8 splines.

> I see you are
> using a different formula for the magic number in the trunk. Do you
> think we could see additional accuracy with a different magic number
> as discussed in these papers?

For the 8 spline approximation I put in the trunk this morning, I used
Lancaster's suggested magic number of 0.2652031. (MAGIC45 is just the
rectilinear distance of the MAGIC number at a 45 degree angle). Again,
feel free to tinker, but that number seemed "good enough" on James' example.

Cheers,
Mike

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

Ted Drain Jet Propulsion Laboratory ted.drain@...179...

We can support this, but I think we would do this with an arc class
rather than an ellipse class, and write a special case class that is
viewlim aware. A simple example of a line that has analogous
behavior is examples/clippedline.py, which clips the points outside
the viewport and draws in a different style according to the
resolution of the viewlim. The reason I think it would be preferable
to use an arc here is because we won't have to worry about filling the
thing when we only approximate a section of it. You could feed in a
360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class that
does 4 or 8 point approximation within the zoom limits, should that
serve your requirements?

JDH

···

On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:

I don't know if the current MPL architecture can support this but it
would be nice if it worked that way. We have people making decisions
based on what these plots show that affect spacecraft worth hundreds
of millions of dollars so it's important that we're plotting things accurately.

John Hunter wrote:

I don't know if the current MPL architecture can support this but it
would be nice if it worked that way. We have people making decisions
based on what these plots show that affect spacecraft worth hundreds
of millions of dollars so it's important that we're plotting things accurately.

We can support this, but I think we would do this with an arc class
rather than an ellipse class, and write a special case class that is
viewlim aware.

I agree -- I think there are two uses cases for ellipse that are in conflict here. One is these large ellipses, the other is for things like scatter plots, where speed and file size is more important than accuracy. My mind was probably stuck on the latter as I've worked along the transforms branch.

A simple example of a line that has analogous
behavior is examples/clippedline.py, which clips the points outside
the viewport and draws in a different style according to the
resolution of the viewlim. The reason I think it would be preferable
to use an arc here is because we won't have to worry about filling the
thing when we only approximate a section of it. You could feed in a
360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class that
does 4 or 8 point approximation within the zoom limits, should that
serve your requirements?

As a possible starting point, the transforms branch already has arc-approximation-by-cubic-bezier-spline code. It determines the number of splines to use based on the radians included in the arc, which is clearly not what we want here. But it should be reasonably straightforward to make that some fixed number and draw the arc between the edges of the axes. Or, alternatively, (and maybe this is what John is suggesting), the arc could be approximated by line segments (with the number of segments something like the number of pixels across the axes). To my naive mind, that seems more verifiable -- or at least it puts the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of pushing curve rendering deeper into the backends for speed and file size improvements. But obviously there needs to be a way around it when it matters.

Cheers,
Mike

···

On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

All of these sound like good ideas to me. Just for some history: the original reason we worked w/ John to get an Ellipse primitive in (vs a normal line plot of sampled points) were to:
- improve ellipse plotting speeds (we plot a LOT of them at once)
- improve post script output

Ted

···

At 08:53 AM 12/10/2007, Michael Droettboom wrote:

John Hunter wrote:
> On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:
>
>> I don't know if the current MPL architecture can support this but it
>> would be nice if it worked that way. We have people making decisions
>> based on what these plots show that affect spacecraft worth hundreds
>> of millions of dollars so it's important that we're plotting things accurately.
>
> We can support this, but I think we would do this with an arc class
> rather than an ellipse class, and write a special case class that is
> viewlim aware.

I agree -- I think there are two uses cases for ellipse that are in
conflict here. One is these large ellipses, the other is for things
like scatter plots, where speed and file size is more important than
accuracy. My mind was probably stuck on the latter as I've worked along
the transforms branch.

> A simple example of a line that has analogous
> behavior is examples/clippedline.py, which clips the points outside
> the viewport and draws in a different style according to the
> resolution of the viewlim. The reason I think it would be preferable
> to use an arc here is because we won't have to worry about filling the
> thing when we only approximate a section of it. You could feed in a
> 360 degree elliptical arc and then zoom into a portion of it.
>
> With the 8 point ellipse as is, and the addition of an arc class that
> does 4 or 8 point approximation within the zoom limits, should that
> serve your requirements?

As a possible starting point, the transforms branch already has
arc-approximation-by-cubic-bezier-spline code. It determines the number
of splines to use based on the radians included in the arc, which is
clearly not what we want here. But it should be reasonably
straightforward to make that some fixed number and draw the arc between
the edges of the axes. Or, alternatively, (and maybe this is what John
is suggesting), the arc could be approximated by line segments (with the
number of segments something like the number of pixels across the axes).
  To my naive mind, that seems more verifiable -- or at least it puts
the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of
pushing curve rendering deeper into the backends for speed and file size
improvements. But obviously there needs to be a way around it when it
matters.

Cheers,
Mike

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

Ted Drain Jet Propulsion Laboratory ted.drain@...179...

I have a working draft of something that may work for this problem on the transforms branch. I am happy to backport this to the trunk, but that will require some effort, as the implementation relies on many of the new geometric utilities on the branch that would also have to be brought over. It may be some time until the branch is ready for production use, but if you are able to use it to experiment with this approach to this specific problem, that would certainly make my life easier, so I don't have to do the backporting work more than once.

Attached is a plot comparing the new approach (above) vs. a 750-edge polygonal approximation for the ellipses (based directly on James Evans' example). Here's a description of what it does:

         Ellipses are normally drawn using an approximation that uses
         eight cubic bezier splines. The error of this approximation
         is 1.89818e-6, according to this unverified source:

           Lancaster, Don. Approximating a Circle or an Ellipse Using
           Four Bezier Cubic Splines.

           http://www.tinaja.com/glib/ellipse4.pdf

         There is a use case where very large ellipses must be drawn
         with very high accuracy, and it is too expensive to render the
         entire ellipse with enough segments (either splines or line
         segments). Therefore, in the case where either radius of the
         ellipse is large enough that the error of the spline
         approximation will be visible (greater than one pixel offset
         from the ideal), a different technique is used.

         In that case, only the visible parts of the ellipse are drawn,
         with each visible arc using a fixed number of spline segments
         (8). The algorithm proceeds as follows:

           1. The points where the ellipse intersects the axes bounding
           box are located. (This is done be performing an inverse
           transformation on the axes bbox such that it is relative to
           the unit circle -- this makes the intersection calculation
           much easier than doing rotated ellipse intersection
           directly).

           This uses the "line intersecting a circle" algorithm from:

             Vince, John. Geometry for Computer Graphics: Formulae,
             Examples & Proofs. London: Springer-Verlag, 2005.

           2. The angles of each of the intersection points are
           calculated.

           3. Proceeding counterclockwise starting in the positive
           x-direction, each of the visible arc-segments between the
           pairs of vertices are drawn using the bezier arc
           approximation technique implemented in Path.arc().

Cheers,
Mike

Ted Drain wrote:

···

All of these sound like good ideas to me. Just for some history: the original reason we worked w/ John to get an Ellipse primitive in (vs a normal line plot of sampled points) were to:
- improve ellipse plotting speeds (we plot a LOT of them at once)
- improve post script output

Ted

At 08:53 AM 12/10/2007, Michael Droettboom wrote:

John Hunter wrote:

On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:

I don't know if the current MPL architecture can support this but it
would be nice if it worked that way. We have people making decisions
based on what these plots show that affect spacecraft worth hundreds
of millions of dollars so it's important that we're plotting

things accurately.

We can support this, but I think we would do this with an arc class
rather than an ellipse class, and write a special case class that is
viewlim aware.

I agree -- I think there are two uses cases for ellipse that are in
conflict here. One is these large ellipses, the other is for things
like scatter plots, where speed and file size is more important than
accuracy. My mind was probably stuck on the latter as I've worked along
the transforms branch.

A simple example of a line that has analogous
behavior is examples/clippedline.py, which clips the points outside
the viewport and draws in a different style according to the
resolution of the viewlim. The reason I think it would be preferable
to use an arc here is because we won't have to worry about filling the
thing when we only approximate a section of it. You could feed in a
360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class that
does 4 or 8 point approximation within the zoom limits, should that
serve your requirements?

As a possible starting point, the transforms branch already has
arc-approximation-by-cubic-bezier-spline code. It determines the number
of splines to use based on the radians included in the arc, which is
clearly not what we want here. But it should be reasonably
straightforward to make that some fixed number and draw the arc between
the edges of the axes. Or, alternatively, (and maybe this is what John
is suggesting), the arc could be approximated by line segments (with the
number of segments something like the number of pixels across the axes).
  To my naive mind, that seems more verifiable -- or at least it puts
the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of
pushing curve rendering deeper into the backends for speed and file size
improvements. But obviously there needs to be a way around it when it
matters.

Cheers,
Mike

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

Ted Drain Jet Propulsion Laboratory ted.drain@...179...

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

Sorry -- correct attachment this time.

Michael Droettboom wrote:

···

I have a working draft of something that may work for this problem on the transforms branch. I am happy to backport this to the trunk, but that will require some effort, as the implementation relies on many of the new geometric utilities on the branch that would also have to be brought over. It may be some time until the branch is ready for production use, but if you are able to use it to experiment with this approach to this specific problem, that would certainly make my life easier, so I don't have to do the backporting work more than once.

Attached is a plot comparing the new approach (above) vs. a 750-edge polygonal approximation for the ellipses (based directly on James Evans' example). Here's a description of what it does:

        Ellipses are normally drawn using an approximation that uses
        eight cubic bezier splines. The error of this approximation
        is 1.89818e-6, according to this unverified source:

          Lancaster, Don. Approximating a Circle or an Ellipse Using
          Four Bezier Cubic Splines.

          http://www.tinaja.com/glib/ellipse4.pdf

        There is a use case where very large ellipses must be drawn
        with very high accuracy, and it is too expensive to render the
        entire ellipse with enough segments (either splines or line
        segments). Therefore, in the case where either radius of the
        ellipse is large enough that the error of the spline
        approximation will be visible (greater than one pixel offset
        from the ideal), a different technique is used.

        In that case, only the visible parts of the ellipse are drawn,
        with each visible arc using a fixed number of spline segments
        (8). The algorithm proceeds as follows:

          1. The points where the ellipse intersects the axes bounding
          box are located. (This is done be performing an inverse
          transformation on the axes bbox such that it is relative to
          the unit circle -- this makes the intersection calculation
          much easier than doing rotated ellipse intersection
          directly).

          This uses the "line intersecting a circle" algorithm from:

            Vince, John. Geometry for Computer Graphics: Formulae,
            Examples & Proofs. London: Springer-Verlag, 2005.

          2. The angles of each of the intersection points are
          calculated.

          3. Proceeding counterclockwise starting in the positive
          x-direction, each of the visible arc-segments between the
          pairs of vertices are drawn using the bezier arc
          approximation technique implemented in Path.arc().

Cheers,
Mike

Ted Drain wrote:

All of these sound like good ideas to me. Just for some history: the original reason we worked w/ John to get an Ellipse primitive in (vs a normal line plot of sampled points) were to:
- improve ellipse plotting speeds (we plot a LOT of them at once)
- improve post script output

Ted

At 08:53 AM 12/10/2007, Michael Droettboom wrote:

John Hunter wrote:

On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:

I don't know if the current MPL architecture can support this but it
would be nice if it worked that way. We have people making decisions
based on what these plots show that affect spacecraft worth hundreds
of millions of dollars so it's important that we're plotting

things accurately.

We can support this, but I think we would do this with an arc class
rather than an ellipse class, and write a special case class that is
viewlim aware.

I agree -- I think there are two uses cases for ellipse that are in
conflict here. One is these large ellipses, the other is for things
like scatter plots, where speed and file size is more important than
accuracy. My mind was probably stuck on the latter as I've worked along
the transforms branch.

A simple example of a line that has analogous
behavior is examples/clippedline.py, which clips the points outside
the viewport and draws in a different style according to the
resolution of the viewlim. The reason I think it would be preferable
to use an arc here is because we won't have to worry about filling the
thing when we only approximate a section of it. You could feed in a
360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class that
does 4 or 8 point approximation within the zoom limits, should that
serve your requirements?

As a possible starting point, the transforms branch already has
arc-approximation-by-cubic-bezier-spline code. It determines the number
of splines to use based on the radians included in the arc, which is
clearly not what we want here. But it should be reasonably
straightforward to make that some fixed number and draw the arc between
the edges of the axes. Or, alternatively, (and maybe this is what John
is suggesting), the arc could be approximated by line segments (with the
number of segments something like the number of pixels across the axes).
  To my naive mind, that seems more verifiable -- or at least it puts
the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of
pushing curve rendering deeper into the backends for speed and file size
improvements. But obviously there needs to be a way around it when it
matters.

Cheers,
Mike

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

-------------------------------------------------------------------------

SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

Ted Drain Jet Propulsion Laboratory ted.drain@...179...

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

------------------------------------------------------------------------

------------------------------------------------------------------------

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

------------------------------------------------------------------------

_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

And an actually interesting part of the plot... :wink:

Michael Droettboom wrote:

···

Sorry -- correct attachment this time.

Michael Droettboom wrote:

I have a working draft of something that may work for this problem on the transforms branch. I am happy to backport this to the trunk, but that will require some effort, as the implementation relies on many of the new geometric utilities on the branch that would also have to be brought over. It may be some time until the branch is ready for production use, but if you are able to use it to experiment with this approach to this specific problem, that would certainly make my life easier, so I don't have to do the backporting work more than once.

Attached is a plot comparing the new approach (above) vs. a 750-edge polygonal approximation for the ellipses (based directly on James Evans' example). Here's a description of what it does:

        Ellipses are normally drawn using an approximation that uses
        eight cubic bezier splines. The error of this approximation
        is 1.89818e-6, according to this unverified source:

          Lancaster, Don. Approximating a Circle or an Ellipse Using
          Four Bezier Cubic Splines.

          http://www.tinaja.com/glib/ellipse4.pdf

        There is a use case where very large ellipses must be drawn
        with very high accuracy, and it is too expensive to render the
        entire ellipse with enough segments (either splines or line
        segments). Therefore, in the case where either radius of the
        ellipse is large enough that the error of the spline
        approximation will be visible (greater than one pixel offset
        from the ideal), a different technique is used.

        In that case, only the visible parts of the ellipse are drawn,
        with each visible arc using a fixed number of spline segments
        (8). The algorithm proceeds as follows:

          1. The points where the ellipse intersects the axes bounding
          box are located. (This is done be performing an inverse
          transformation on the axes bbox such that it is relative to
          the unit circle -- this makes the intersection calculation
          much easier than doing rotated ellipse intersection
          directly).

          This uses the "line intersecting a circle" algorithm from:

            Vince, John. Geometry for Computer Graphics: Formulae,
            Examples & Proofs. London: Springer-Verlag, 2005.

          2. The angles of each of the intersection points are
          calculated.

          3. Proceeding counterclockwise starting in the positive
          x-direction, each of the visible arc-segments between the
          pairs of vertices are drawn using the bezier arc
          approximation technique implemented in Path.arc().

Cheers,
Mike

Ted Drain wrote:

All of these sound like good ideas to me. Just for some history: the original reason we worked w/ John to get an Ellipse primitive in (vs a normal line plot of sampled points) were to:
- improve ellipse plotting speeds (we plot a LOT of them at once)
- improve post script output

Ted

At 08:53 AM 12/10/2007, Michael Droettboom wrote:

John Hunter wrote:

On Dec 10, 2007 10:25 AM, Ted Drain <ted.drain@...179...> wrote:

I don't know if the current MPL architecture can support this but it
would be nice if it worked that way. We have people making decisions
based on what these plots show that affect spacecraft worth hundreds
of millions of dollars so it's important that we're plotting

things accurately.

We can support this, but I think we would do this with an arc class
rather than an ellipse class, and write a special case class that is
viewlim aware.

I agree -- I think there are two uses cases for ellipse that are in
conflict here. One is these large ellipses, the other is for things
like scatter plots, where speed and file size is more important than
accuracy. My mind was probably stuck on the latter as I've worked along
the transforms branch.

A simple example of a line that has analogous
behavior is examples/clippedline.py, which clips the points outside
the viewport and draws in a different style according to the
resolution of the viewlim. The reason I think it would be preferable
to use an arc here is because we won't have to worry about filling the
thing when we only approximate a section of it. You could feed in a
360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class that
does 4 or 8 point approximation within the zoom limits, should that
serve your requirements?

As a possible starting point, the transforms branch already has
arc-approximation-by-cubic-bezier-spline code. It determines the number
of splines to use based on the radians included in the arc, which is
clearly not what we want here. But it should be reasonably
straightforward to make that some fixed number and draw the arc between
the edges of the axes. Or, alternatively, (and maybe this is what John
is suggesting), the arc could be approximated by line segments (with the
number of segments something like the number of pixels across the axes).
  To my naive mind, that seems more verifiable -- or at least it puts
the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of
pushing curve rendering deeper into the backends for speed and file size
improvements. But obviously there needs to be a way around it when it
matters.

Cheers,
Mike

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

-------------------------------------------------------------------------

SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

Ted Drain Jet Propulsion Laboratory ted.drain@...179...

-------------------------------------------------------------------------

SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

------------------------------------------------------------------------

------------------------------------------------------------------------

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

------------------------------------------------------------------------

_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

------------------------------------------------------------------------

------------------------------------------------------------------------

-------------------------------------------------------------------------
SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php

------------------------------------------------------------------------

_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA

Sorry – correct attachment this
time.

Michael Droettboom wrote:

I have a working draft of
something that may work for this problem on the transforms branch.
I am happy to backport this to the trunk, but that will require some
effort, as the implementation relies on many of the new geometric
utilities on the branch that would also have to be brought over. It
may be some time until the branch is ready for production use, but if you
are able to use it to experiment with this approach to this specific
problem, that would certainly make my life easier, so I don’t have to do
the backporting work more than once.

Attached is a plot comparing the new approach (above) vs. a 750-edge
polygonal approximation for the ellipses (based directly on James Evans’
example). Here’s a description of what it does:

    Ellipses are normally drawn

using an approximation that uses

    eight cubic bezier

splines. The error of this approximation

    is 1.89818e-6, according to

this unverified source:

      Lancaster,

Don. Approximating a Circle or an Ellipse Using

      Four Bezier Cubic

Splines.


http://www.tinaja.com/glib/ellipse4.pdf

    There is a use case where very

large ellipses must be drawn

    with very high accuracy, and

it is too expensive to render the

    entire ellipse with enough

segments (either splines or line

    segments).  Therefore, in

the case where either radius of the

    ellipse is large enough that

the error of the spline

    approximation will be visible

(greater than one pixel offset

    from the ideal), a different

technique is used.

    In that case, only the visible

parts of the ellipse are drawn,

    with each visible arc using a

fixed number of spline segments

    (8).  The algorithm

proceeds as follows:

      1. The points

where the ellipse intersects the axes bounding

      box are

located. (This is done be performing an inverse

      transformation on

the axes bbox such that it is relative to

      the unit circle --

this makes the intersection calculation

      much easier than

doing rotated ellipse intersection

      directly).

      This uses the

“line intersecting a circle” algorithm from:

        Vince,

John. Geometry for Computer Graphics: Formulae,

Examples & Proofs. London: Springer-Verlag, 2005.

      2. The angles of

each of the intersection points are

      calculated.

      3. Proceeding

counterclockwise starting in the positive

      x-direction, each

of the visible arc-segments between the

      pairs of vertices

are drawn using the bezier arc

      approximation

technique implemented in Path.arc().

Cheers,

Mike

Ted Drain wrote:

All of these sound like good
ideas to me. Just for some history: the original reason we worked
w/ John to get an Ellipse primitive in (vs a normal line plot of sampled
points) were to:

  • improve ellipse plotting speeds (we plot a LOT of them at once)

  • improve post script output

Ted

John Hunter wrote:

I don’t know if the current MPL
architecture can support this but it

would be nice if it worked that way. We have people making
decisions

based on what these plots show that affect spacecraft worth hundreds

of millions of dollars so it’s important that we’re plotting
things accurately.
We can support this, but I think
we would do this with an arc class

rather than an ellipse class, and write a special case class that is

viewlim aware.
I agree – I think there are two uses cases
for ellipse that are in

conflict here. One is these large ellipses, the other is for
things

like scatter plots, where speed and file size is more important than

accuracy. My mind was probably stuck on the latter as I’ve worked
along

the transforms branch.

A simple example of a line that
has analogous

behavior is examples/clippedline.py, which clips the points outside

the viewport and draws in a different style according to the

resolution of the viewlim. The reason I think it would be
preferable

to use an arc here is because we won’t have to worry about filling
the

thing when we only approximate a section of it. You could feed in
a

360 degree elliptical arc and then zoom into a portion of it.

With the 8 point ellipse as is, and the addition of an arc class
that

does 4 or 8 point approximation within the zoom limits, should that

serve your requirements?
As a possible starting point, the
transforms branch already has

arc-approximation-by-cubic-bezier-spline code. It determines the
number

of splines to use based on the radians included in the arc, which is

clearly not what we want here. But it should be reasonably

straightforward to make that some fixed number and draw the arc
between

the edges of the axes. Or, alternatively, (and maybe this is what
John

is suggesting), the arc could be approximated by line segments (with
the

number of segments something like the number of pixels across the
axes).

To my naive mind, that seems more verifiable – or at least it
puts

the responsibility of getting this right all in one place.

IMHO, these spline approximation tricks are all just with the aim of

pushing curve rendering deeper into the backends for speed and file
size

improvements. But obviously there needs to be a way around it when
it

matters.

Cheers,

Mike

Michael Droettboom

Science Software Branch

Operations and Engineering Division

Space Telescope Science Institute

Operated by AURA for NASA


SF.Net email is sponsored by:

Check out the new SourceForge.net Marketplace.

It’s the best place to buy or sell services for

just about anything Open Source.


http://sourceforge.net/services/buy/index.php


Matplotlib-devel mailing list

Matplotlib-devel@lists.sourceforge.net


https://lists.sourceforge.net/lists/listinfo/matplotlib-devel

Ted Drain Jet Propulsion Laboratory
ted.drain@…179…


SF.Net email is sponsored by: Check out the new SourceForge.net
Marketplace.

It’s the best place to buy or sell services for

just about anything Open Source.


http://sourceforge.net/services/buy/index.php


Matplotlib-devel mailing list

Matplotlib-devel@lists.sourceforge.net


https://lists.sourceforge.net/lists/listinfo/matplotlib-devel




SF.Net email is sponsored by: Check out the new SourceForge.net
Marketplace.

It’s the best place to buy or sell services for

just about anything Open Source.


http://sourceforge.net/services/buy/index.php



Matplotlib-devel mailing list

Matplotlib-devel@lists.sourceforge.net


https://lists.sourceforge.net/lists/listinfo/matplotlib-devel

Michael Droettboom

Science Software Branch

Operations and Engineering Division

Space Telescope Science Institute

Operated by AURA for NASA

Michael,

Thanks! That looks like a great solution. We’ll take a look
at it this week and try to beat on it w/ some more test cases.

Ted

···

At 08:53 AM 12/10/2007, Michael Droettboom wrote:

On Dec 10, 2007 10:25 AM, Ted > > > > > Drain <ted.drain@…179…> wrote:

At 12:46 PM 12/11/2007, Michael Droettboom wrote:

Very nice work Michael -- I tried updating from your branch but it
looks like maybe you haven't committed yet, as the last log entry I am
seeing is:

  r4694 | mdboom | 2007-12-10 13:53:12 -0600 (Mon, 10 Dec 2007) | 2 lines

  Simplify even more

JDH

···

On Dec 11, 2007 3:24 PM, Ted Drain <ted.drain@...179...> wrote:

Thanks! That looks like a great solution. We'll take a look at it this
week and try to beat on it w/ some more test cases.