Is there any particular reason that the morphology filter uses something called a "surface synthesizer" (or something along those lines)? Its time complexity currently depends on the structuring element size, and I wanted to fix that, but to do that I need to be able to keep some history, as well as delaying the output until enough data has been gathered. Is this possible at all within this scheme? If not, is it okay if I just copy-paste ink_cairo_surface_synthesize - gut it - and write a few simple loops? (Or am I missing something?)
W dniu 8 marca 2012 19:42 użytkownik Jasper van de Gronde <th.v.d.gronde@...528...> napisał:
Is there any particular reason that the morphology filter uses something called a "surface synthesizer" (or something along those lines)? Its time complexity currently depends on the structuring element size, and I wanted to fix that, but to do that I need to be able to keep some history, as well as delaying the output until enough data has been gathered. Is this possible at all within this scheme? If not, is it okay if I just copy-paste ink_cairo_surface_synthesize - gut it - and write a few simple loops? (Or am I missing something?)
I used this approach to abstract away the OpenMP multithreading support. It works well for the majority of filters, but I admit it's not optimal for morphology. You can ignore ink_cairo_surface_synthesize if you implement multithreading yourself. For example, Gaussian blur does not use these templates at all.
You can also try implementing the triple box blur approximation for Gaussian blur, which should be a lot faster than the current approach. The details are in the SVG filter specification. I tried doing this some time ago, but the result was all wrong and I couldn't figure out why.
Regards, Krzysztof
On 2012-03-09 21:58, Krzysztof Kosiński wrote:
W dniu 8 marca 2012 19:42 użytkownik Jasper van de Gronde <th.v.d.gronde@...528...> napisał: I used this approach to abstract away the OpenMP multithreading support. It works well for the majority of filters, but I admit it's not optimal for morphology. You can ignore ink_cairo_surface_synthesize if you implement multithreading yourself. For example, Gaussian blur does not use these templates at all.
Okay, will do.
You can also try implementing the triple box blur approximation for Gaussian blur, which should be a lot faster than the current approach. The details are in the SVG filter specification. I tried doing this some time ago, but the result was all wrong and I couldn't figure out why.
It is faster, but not so much faster that it's worth the decrease in quality. The current scheme also requires a small fixed amount of operations per pixel, the main difference is that it really needs doubles, while repeated boxblurring can get away with integers. When both approaches are fully accelerated using SSE and such I actually doubt that apart from the increased memory bandwidth needed for doubles there would be much of a difference. Having said that, I have some ideas for getting rid of the current code in favor of something more similar to repeated boxblurring, but I still have to work out some issues (even with boxblurring it is not entirely trivial to handle boundaries properly, which the current scheme does do).
On 2012-03-09 21:58, Krzysztof Kosiński wrote:
W dniu 8 marca 2012 19:42 użytkownik Jasper van de Gronde <th.v.d.gronde@...528...> napisał:
Is there any particular reason that the morphology filter uses something called a "surface synthesizer" (or something along those lines)? Its time complexity currently depends on the structuring element size, and I wanted to fix that, but to do that I need to be able to keep some history, as well as delaying the output until enough data has been gathered. Is this possible at all within this scheme? If not, is it okay if I just copy-paste ink_cairo_surface_synthesize - gut it - and write a few simple loops? (Or am I missing something?)
I used this approach to abstract away the OpenMP multithreading support. It works well for the majority of filters, but I admit it's not optimal for morphology. You can ignore ink_cairo_surface_synthesize if you implement multithreading yourself. For example, Gaussian blur does not use these templates at all.
Done. The main problem currently is the slicing/tiling that Inkscape does. This is similar for Gaussian blur. In principle these algorithms do not need to have overlapping tiles, as they "summarize" their history in a relatively small data structure, but we currently have no way to store these. Also, if we did, it would either complicate the implementation quite a bit, or we would have to always draw the tiles in the same order. But it would be a worthwhile endeavour to solve this, as essentially the current method transforms these O(n) (with n the size of the output) algorithms into O(n*m) algorithms (with m the size of the kernel).
participants (2)
-
Jasper van de Gronde -
Krzysztof Kosiński