Re: [matplotlib-devel] Problem with Agg Ellipses

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

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...@jp...> 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
>> Mat...@li...
>> https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
> 
> Ted Drain     Jet Propulsion Laboratory   ted...@jp...    
> 
> 
> 
> -------------------------------------------------------------------------
> 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
> Mat...@li...
> 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