Re: [matplotlib-devel] Delaunay code: future directions?
Hi Amit, I am with you 100% of the way. We should use an existing open source Delaunay triangulator, and my preference is for QHull as well. "Improved Delaunay triangulator" is on my matplotlib todo list, albeit it quite a long way from the top. I don't tend to use the existing code as I usually specify my own triangulations, so I have never seen anything quite as embarrassing as issue #1809. Perhaps I need to bump it up my priority list. If I come up with a possible solution as a PR, would you be prepared to help test it? You seem to have quite a few examples that don't work under the existing code and would be very useful for demonstrating if the improved code is indeed an improvement. Ian On 5 March 2013 23:08, Amit Aronovitch wrote: > Dear MPL-devs, > > Currently, matplotlib does Delaunay triangulation using a special > purpose module written in C++ (if I'm not mistaken, it was originally > forked off from some SciKit and wrapped into a Python module). > Some people (here and on github issues) had suggested it might need some > rewrites/modification. > In particular I was wondering if we should continue maintaining it here > or maybe switch to using some external library. > > Since triangulation is not a plotting-specific problem, and some free > libraries are available for solving it, we might actually benefit in > terms of efficiency and robustness. > > Specifically, I had suggested QHull, which is used by scipy (note that > now there is also a stand-alone python interface: > https://pypi.python.org/pypi/pyhull - I did not check that out yet). > @dmcdougall had suggested Jonathan Shewchuk's triangle library (we > should check the license though - I think it is "for non-commercial > use", unlike mpl). There are also other alternatives. > > On the other hand, there's the issue of minimizing external > dependencies. I think @ianthomas23 had once mentioned that he is happy > with having Delaunay code reside in mpl (and, of course, "maintainable" > is whatever is most convenient for the maintainers). > > I apologize for suggesting more tasks without contributing time to work > on them. Just thought that since I finally sat down to report issue > #1809 (which seems to be a particularly slippery bug in the code > mentioned above), it might be a good time to discuss this topic again. > > thanks, > > Amit Aronovitch > -- Symantec Endpoint Protection 12 positioned as A LEADER in The Forrester Wave(TM): Endpoint Security, Q1 2013 and "remains a good choice" in the endpoint security space. For insight on selecting the right partner to tackle endpoint security challenges, access the full report. http://p.sf.net/sfu/symantec-dev2dev___ Matplotlib-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
[matplotlib-devel] "Flash" rendering in the Agg backend
Smart rendering of adjacent, anti-aliased patches is a question which has
come up a couple of times in various guises in the past.
It is my understanding that the lack of this functionality led us to
disable anti-aliasing for contouring and is the reason the following image
has a white stripe around the circle where there should be just a nice
blend of the two colors:
import matplotlib.pyplot as plt
import numpy as np
import matplotlib.patches as mpatches
import matplotlib.path as mpath
import matplotlib.collections as mcol
# create two paths. One a circle, the other
# a square with the same circle cut out.
x = np.linspace(0, np.pi * 2, 1000)
circle_coords = np.array(zip(*[np.sin(x) * 0.8, np.cos(x) * 0.8]))
pth_circle = mpath.Path(circle_coords)
sqr_codes = np.repeat(mpath.Path.MOVETO, len(circle_coords) + 5)
sqr_codes[1:5] = mpath.Path.LINETO
sqr_codes[6:] = mpath.Path.LINETO
sqr_coords = np.concatenate([[[-1, -1], [-1, 1], [1, 1], [1, -1], [-1,
-1]],
circle_coords[::-1]], axis=0)
sqr_path = mpath.Path(sqr_coords, sqr_codes)
ax = plt.axes()
patches = [mpatches.PathPatch(pth_circle), mpatches.PathPatch(sqr_path)]
col = mcol.PatchCollection(patches,
antialiaseds=True,
edgecolors='none',
facecolors=[(0, 0.0, 0.0, 0.9), (0.1, 0.1, 0.02,
0.9)])
ax.add_collection(col)
ax.set_xlim([-1, 1])
ax.set_ylim([-1, 1])
plt.show()
I know of lots of the workarounds for this (turn off AA, turn on lines,
extend the path slightly, set a dark background color) all of which have
down-sides, so I'm keen to find a final solution to the problem.
When the two patches marry up perfectly with full anti-aliasing, the
antigrain (AGG) community call this "flash" or compound rendering, and this
capability was added to Agg 2.4 (which we already ship with mpl).
In order to make full use of the compound rendering technique I believe the
drawing pipeline in "_backend_agg.cpp" would need to change, which could be
problematic. A less wide-impacting alternative would be to draw all
"patches" of a single Collection in the same rasterization step (i.e. just
change _draw_path_collection_generic), though this does mean that, as it
stands, the result of plt.contourf would not be able to make use of this
new functionality - a MEP which changes the return type of plt.contourf to
a single Collection might be able to fix that.
I've put together a simple example similar to this in C++ using agg (no mpl
changes yet), showing the differences in the code needed between the old
technique vs the "new" compound renderer (attached).
Ok, so the question to those that have knowledge of the _backend_agg.cpp
code (Mike, Eric, JJ + others?):
- Have you already looked at doing this and determined that this is a
non-starter?
- Do you support adding the ability for the agg backend to draw compound
artists (i.e. Collections) in this way rather than treating them as
individual primitives in the canvas?
- Since many of the other backends can't do flash rendering, would we
even want to make this change?
- SVG in Firefox 10.0.2 has the same problem, it is discussed
slightly more in
http://www.svgopen.org/2002/papers/sorotokin__svg_secrets/
- Acroread has the same problem with PDFs, only to a much lesser
extent than in the PNG attached
Thoughts?
<>#include
#include
#include
#include
#include "agg_rendering_buffer.h"
#include "agg_rasterizer_scanline_aa.h"
#include "agg_pixfmt_rgb.h"
#include "agg_scanline_p.h"
#include "agg_renderer_scanline.h"
#include "agg_color_rgba.h"
#include "agg_array.h"
#include "util/agg_color_conv_rgb8.h"
#include "agg_path_storage.h"
#define PI 3.14159265
bool save_image_file (agg::rendering_buffer& rbuf, const char *fn)
{
FILE* fd = fopen(fn, "wb");
if(fd == 0) return false;
unsigned w = rbuf.width();
unsigned h = rbuf.height();
fprintf(fd, "P6\n%d %d\n255\n", w, h);
unsigned y;
agg::pod_array row_buf(w * 3);
unsigned char *tmp_buf = row_buf.data();
for(y = 0; y < rbuf.height(); y++)
{
const unsigned char* src = rbuf.row_ptr(h - 1 - y);
agg::color_conv_row(tmp_buf, src, w, agg::color_conv_bgr24_to_rgb24());
fwrite(tmp_buf, 1, w * 3, fd);
}
fclose(fd);
return true;
}
int main()
{
typedef agg::pixfmt_bgr24 pixel_type;
const unsigned w = 500, h = 300;
int i;
int x_radius = 240, y_radius = 280, x_offset = 250, y_offset = 5;
unsigned row_size = pixel_type::pix_width * w;
unsigned buf_size = row_size * h;
agg::pod_array img_buf(buf_size);
agg::rendering_buffer rendering_buffer(img_buf.data(), w, h, -row_size);
pixel_type pixf(rendering_buffer);
typedef agg::renderer_base renderer_base_type;
typedef agg::renderer_scanline_aa_solid renderer_solid_type;
renderer_base_type renderer_base(pixf);
renderer_solid_type renderer_solid(renderer_bas
Re: [matplotlib-devel] "Flash" rendering in the Agg backend
On 2013/03/06 7:06 AM, Phil Elson wrote: > Smart rendering of adjacent, anti-aliased patches is a question which > has come up a couple of times in various guises in the past. > It is my understanding that the lack of this functionality led us to > disable anti-aliasing for contouring and is the reason the following > image has a white stripe around the circle where there should be just a > nice blend of the two colors: > > > import matplotlib.pyplot as plt > import numpy as np > import matplotlib.patches as mpatches > import matplotlib.path as mpath > import matplotlib.collections as mcol > > > # create two paths. One a circle, the other > # a square with the same circle cut out. > x = np.linspace(0, np.pi * 2, 1000) > > circle_coords = np.array(zip(*[np.sin(x) * 0.8, np.cos(x) * 0.8])) > pth_circle = mpath.Path(circle_coords) > > sqr_codes = np.repeat(mpath.Path.MOVETO, len(circle_coords) + 5) > sqr_codes[1:5] = mpath.Path.LINETO > sqr_codes[6:] = mpath.Path.LINETO > sqr_coords = np.concatenate([[[-1, -1], [-1, 1], [1, 1], [1, -1], [-1, > -1]], > circle_coords[::-1]], axis=0) > sqr_path = mpath.Path(sqr_coords, sqr_codes) > > > ax = plt.axes() > patches = [mpatches.PathPatch(pth_circle), mpatches.PathPatch(sqr_path)] > col = mcol.PatchCollection(patches, > antialiaseds=True, > edgecolors='none', > facecolors=[(0, 0.0, 0.0, 0.9), (0.1, 0.1, > 0.02, 0.9)]) > ax.add_collection(col) > ax.set_xlim([-1, 1]) > ax.set_ylim([-1, 1]) > plt.show() > > > > I know of lots of the workarounds for this (turn off AA, turn on lines, > extend the path slightly, set a dark background color) all of which have > down-sides, so I'm keen to find a final solution to the problem. > > When the two patches marry up perfectly with full anti-aliasing, the > antigrain (AGG) community call this "flash" or compound rendering, and > this capability was added to Agg 2.4 (which we already ship with mpl). > > In order to make full use of the compound rendering technique I believe > the drawing pipeline in "_backend_agg.cpp" would need to change, which > could be problematic. A less wide-impacting alternative would be to draw > all "patches" of a single Collection in the same rasterization step > (i.e. just change _draw_path_collection_generic), though this does mean > that, as it stands, the result of plt.contourf would not be able to make > use of this new functionality - a MEP which changes the return type of > plt.contourf to a single Collection might be able to fix that. > > I've put together a simple example similar to this in C++ using agg (no > mpl changes yet), showing the differences in the code needed between the > old technique vs the "new" compound renderer (attached). > > > Ok, so the question to those that have knowledge of the _backend_agg.cpp > code (Mike, Eric, JJ + others?): > > * Have you already looked at doing this and determined that this is a > non-starter? > * Do you support adding the ability for the agg backend to draw > compound artists (i.e. Collections) in this way rather than treating > them as individual primitives in the canvas? > * Since many of the other backends can't do flash rendering, would we > even want to make this change? > o SVG in Firefox 10.0.2 has the same problem, it is discussed > slightly more in > http://www.svgopen.org/2002/papers/sorotokin__svg_secrets/ > o Acroread has the same problem with PDFs, only to a much lesser > extent than in the PNG attached > > > Thoughts? Phil, Would this greatly slow down the rendering? Does it work with alpha < 1? I'm initially not enthusiastic about having contourf return a single Collection, but maybe in practice it would not make much difference. The drawback, apart from code brakeage, is that it would remove the ability to pick out a level for additional customization. Could this be handled at a subsequent level, by having the renderer able to treat an arbitrary collection of artists as a group? It seems that contourf is where this "flash" capability would be most important; if it can't be made to work there, I think it might not be worth the trouble to add. Eric -- Symantec Endpoint Protection 12 positioned as A LEADER in The Forrester Wave(TM): Endpoint Security, Q1 2013 and "remains a good choice" in the endpoint security space. For insight on selecting the right partner to tackle endpoint security challenges, access the full report. http://p.sf.net/sfu/symantec-dev2dev ___ Matplotlib-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
Re: [matplotlib-devel] Delaunay code: future directions?
Thanks Ian. These examples occured when I processed large propriatary datasets. So far, scipy's triangulation worked whenever matplotlib failed. When we have a new implementation, it should be quite simple to check if it works where it had previously failed. Certainly easier than slicing the data to small chunks and trying to distill a failing example of reasonable size as I did in this case. So, "working"/"not working" test (possibly including some time measurements) I can do on a fairly short notice. Producing some more examples that fail with the current code might require several hours of work, so would probably get delayed for a few weeks. Amit On Wed, Mar 6, 2013 at 10:53 AM, Ian Thomas wrote: > Hi Amit, > > I am with you 100% of the way. We should use an existing open source > Delaunay triangulator, and my preference is for QHull as well. > > "Improved Delaunay triangulator" is on my matplotlib todo list, albeit it > quite a long way from the top. I don't tend to use the existing code as I > usually specify my own triangulations, so I have never seen anything quite > as embarrassing as issue #1809. Perhaps I need to bump it up my priority > list. > > If I come up with a possible solution as a PR, would you be prepared to > help test it? You seem to have quite a few examples that don't work under > the existing code and would be very useful for demonstrating if the > improved code is indeed an improvement. > > Ian > > > On 5 March 2013 23:08, Amit Aronovitch wrote: > >> Dear MPL-devs, >> >> Currently, matplotlib does Delaunay triangulation using a special >> purpose module written in C++ (if I'm not mistaken, it was originally >> forked off from some SciKit and wrapped into a Python module). >> Some people (here and on github issues) had suggested it might need some >> rewrites/modification. >> In particular I was wondering if we should continue maintaining it here >> or maybe switch to using some external library. >> >> Since triangulation is not a plotting-specific problem, and some free >> libraries are available for solving it, we might actually benefit in >> terms of efficiency and robustness. >> >> Specifically, I had suggested QHull, which is used by scipy (note that >> now there is also a stand-alone python interface: >> https://pypi.python.org/pypi/pyhull - I did not check that out yet). >> @dmcdougall had suggested Jonathan Shewchuk's triangle library (we >> should check the license though - I think it is "for non-commercial >> use", unlike mpl). There are also other alternatives. >> >> On the other hand, there's the issue of minimizing external >> dependencies. I think @ianthomas23 had once mentioned that he is happy >> with having Delaunay code reside in mpl (and, of course, "maintainable" >> is whatever is most convenient for the maintainers). >> >> I apologize for suggesting more tasks without contributing time to work >> on them. Just thought that since I finally sat down to report issue >> #1809 (which seems to be a particularly slippery bug in the code >> mentioned above), it might be a good time to discuss this topic again. >> >> thanks, >> >> Amit Aronovitch >> > -- Symantec Endpoint Protection 12 positioned as A LEADER in The Forrester Wave(TM): Endpoint Security, Q1 2013 and "remains a good choice" in the endpoint security space. For insight on selecting the right partner to tackle endpoint security challenges, access the full report. http://p.sf.net/sfu/symantec-dev2dev___ Matplotlib-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
Re: [matplotlib-devel] "Flash" rendering in the Agg backend
I'm trying to compile your examples, but it seems perhaps you forget to include a file -- pixel_formats.hpp? It's not in the agg24 source tree. Mike On 03/06/2013 12:06 PM, Phil Elson wrote: Smart rendering of adjacent, anti-aliased patches is a question which has come up a couple of times in various guises in the past. It is my understanding that the lack of this functionality led us to disable anti-aliasing for contouring and is the reason the following image has a white stripe around the circle where there should be just a nice blend of the two colors: import matplotlib.pyplot as plt import numpy as np import matplotlib.patches as mpatches import matplotlib.path as mpath import matplotlib.collections as mcol # create two paths. One a circle, the other # a square with the same circle cut out. x = np.linspace(0, np.pi * 2, 1000) circle_coords = np.array(zip(*[np.sin(x) * 0.8, np.cos(x) * 0.8])) pth_circle = mpath.Path(circle_coords) sqr_codes = np.repeat(mpath.Path.MOVETO, len(circle_coords) + 5) sqr_codes[1:5] = mpath.Path.LINETO sqr_codes[6:] = mpath.Path.LINETO sqr_coords = np.concatenate([[[-1, -1], [-1, 1], [1, 1], [1, -1], [-1, -1]], circle_coords[::-1]], axis=0) sqr_path = mpath.Path(sqr_coords, sqr_codes) ax = plt.axes() patches = [mpatches.PathPatch(pth_circle), mpatches.PathPatch(sqr_path)] col = mcol.PatchCollection(patches, antialiaseds=True, edgecolors='none', facecolors=[(0, 0.0, 0.0, 0.9), (0.1, 0.1, 0.02, 0.9)]) ax.add_collection(col) ax.set_xlim([-1, 1]) ax.set_ylim([-1, 1]) plt.show() I know of lots of the workarounds for this (turn off AA, turn on lines, extend the path slightly, set a dark background color) all of which have down-sides, so I'm keen to find a final solution to the problem. When the two patches marry up perfectly with full anti-aliasing, the antigrain (AGG) community call this "flash" or compound rendering, and this capability was added to Agg 2.4 (which we already ship with mpl). In order to make full use of the compound rendering technique I believe the drawing pipeline in "_backend_agg.cpp" would need to change, which could be problematic. A less wide-impacting alternative would be to draw all "patches" of a single Collection in the same rasterization step (i.e. just change _draw_path_collection_generic), though this does mean that, as it stands, the result of plt.contourf would not be able to make use of this new functionality - a MEP which changes the return type of plt.contourf to a single Collection might be able to fix that. I've put together a simple example similar to this in C++ using agg (no mpl changes yet), showing the differences in the code needed between the old technique vs the "new" compound renderer (attached). Ok, so the question to those that have knowledge of the _backend_agg.cpp code (Mike, Eric, JJ + others?): Have you already looked at doing this and determined that this is a non-starter? Do you support adding the ability for the agg backend to draw compound artists (i.e. Collections) in this way rather than treating them as individual primitives in the canvas? Since many of the other backends can't do flash rendering, would we even want to make this change? SVG in Firefox 10.0.2 has the same problem, it is discussed slightly more in http://www.svgopen.org/2002/papers/soroto
Re: [matplotlib-devel] "Flash" rendering in the Agg backend
While I cannot say much about the "compound renderering" in Agg as I know little about it, but the upsampling method that Mike mentioned seems quite robust. Just a quick question, will it affect the rendered quality of AA'ed artists, like texts? What I mean is, drawing texts w/ AA on (in the upsampled canvas) and downsampling the result may give poor quality? But maybe there is a way to adjust how AA is done in the first place. Maybe what we can try is to upsample only selected artists, similar to rasterization in vector backends or agg_filter. This will likely consume more memory and maybe more CPU, but may give minimal side effects. While it is not directly related to the current issue, I thought it would be good to have, within a backend, multiple layers to render and the final result is a composite of those layers. And we may upsample some layers or apply effects selectively. And do the alpha compositing of layers in the end. This will be also useful for animations as we can only update selected layers. Back to the original issue, I am inclined to play with Mike's upsamping method to see if it solves the problem without significant side effects. Regards, -JJ On Thu, Mar 7, 2013 at 6:54 AM, Michael Droettboom wrote: > Thanks for bringing this up -- I was just looking at the test images the > other day and was reminded how filled contouring doesn't look as good as it > could be. > > I had played with the "compound renderer" example in Agg some years ago, > but couldn't really understand how it worked, so ultimately gave up on it. > I appreciate the research you've done here, because it illustrates pretty > clearly what is required. I guess in the actual Agg draw_path_collection > renderer, we would have to build a style_handler table dynamically based on > the collection and then iterate through it as we draw... At least it's > clear now how that could be accomplished. > > I wonder, though, and the SVG article you link to hints at this, if we > wouldn't be better off just upsampling our Agg rendering instead. The > advantage of such an approach would be that the structure or ordering of > the drawing wouldn't matter at all -- allaying most of Eric's concerns. It > seems like it just overall be "easier" to do the right thing. And it > should benefit all things, including other tricky things like quadmeshes, > "automatically". > > Of course, the downside is a performance hit. Assuming 2x oversampling, > it means the screen buffer will be 4x the size, rendering will take "up to" > four times as long, and then you have to downsample again (which in the > best case would happen in hardware). Compound rendering has a memory > penalty, too, of course, since the scanlines for all of the paths have to > be stored until finally rendered out simultaneously. Estimating what that > overhead is much harder, of course, and is more content dependent, whereas > the performance hit upsampling is straightforward and has an obvious upper > bound. > > I put together a very quick hack on my agg-upsampling branch, which > hardcodes the upsampling to 2x in each direction. It currently only works > with the GtkAgg backend (even file saving won't work correctly), and I only > fixed things up for contour plotting, so images (and probably other things) > will be misplaced. But it should give an idea for the performance hit and > quality benefit enough to play around with. > > Mike > > > On 03/06/2013 03:27 PM, Michael Droettboom wrote: > > I'm trying to compile your examples, but it seems perhaps you forget to > include a file -- pixel_formats.hpp? It's not in the agg24 source tree. > > Mike > > On 03/06/2013 12:06 PM, Phil Elson wrote: > > Smart rendering of adjacent, anti-aliased patches is a question which > has come up a couple of times in various guises in the past. > It is my understanding that the lack of this functionality led us to > disable anti-aliasing for contouring and is the reason the following image > has a white stripe around the circle where there should be just a nice > blend of the two colors: > > > import matplotlib.pyplot as plt > import numpy as np > import matplotlib.patches as mpatches > import matplotlib.path as mpath > import matplotlib.collections as mcol > > > # create two paths. One a circle, the other > # a square with the same circle cut out. > x = np.linspace(0, np.pi * 2, 1000) > > circle_coords = np.array(zip(*[np.sin(x) * 0.8, np.cos(x) * 0.8])) > pth_circle = mpath.Path(circle_coords) > > sqr_codes = np.repeat(mpath.Path.MOVETO, len(circle_coords) + 5) > sqr_codes[1:5] = mpath.Path.LINETO > sqr_codes[6:] = mpath.Path.LINETO > sqr_coords = np.concatenate([[[-1, -1], [-1, 1], [1, 1], [1, -1], [-1, > -1]], > circle_coords[::-1]], axis=0) > sqr_path = mpath.Path(sqr_coords, sqr_codes) > > > ax = plt.axes() > patches = [mpatches.PathPatch(pth_circle), mpatches.PathPatch(sqr_path)] > col = mcol.PatchCollection(patches, >a
