Hi,
neota@softhome.net (2005-03-01 at 1108.08 -0500):

Maybe it would be best if someone could come up with a reasonable example what supersampling might be useful for in gradient blend code

"GSR" (?) already gave such an example. It might be worth considering only supersampling when the end of a segment is a different color than the start of the next one.

Supersampling is to avoid aliasing, which is not caused only by those discontinuities but high frequency data (IIRC abrupt change is like infinite frequency). You can have aliasing with a square wave (segments that do not match) but also with a sine wave (segments that match).

GSR

Maybe it would be best if someone could come up with a reasonable example what supersampling might be useful for in gradient blend code

"GSR" (?) already gave such an example. It might be worth considering only supersampling when the end of a segment is a different color than the start of the next one.

Hi,
de@axiros.com (2005-03-01 at 2248.36 +0100):

Supersampling is to avoid aliasing, which is not caused only by those discontinuities but high frequency data (IIRC abrupt change is like infinite frequency). You can have aliasing with a square wave (segments that do not match) but also with a sine wave (segments that match).

Right. But where in reality can this happen using a gradient blend?

Yes, "radial rainbow hoop" gradient (linear 6 pixel to right sawtooth) without supersampling it paints mostly red and with it shows the muddy colour mix you would get if you render big and scale down: http://www.infernal-iceberg.com/gimp/tmp/gradient-supersampling-03-crop.png

I just played around with the blend tool on a 100x100px image and looked very closely for any artifacts with and without supersampling. The result was that I couldn't produce any visible aliasing effects no matter how hard I try other than by using a sawtooth repeat pattern. That seems like a *huge* price to pay for something that can be easily done by accident.

The price is an user decision, and default is supersampling off, right? If it is removed, the price you impose is not so low: render into a big version then scale down and copy. Which means fucked up workflow and no adaptive algorithm, so even slower computing and user working a lot more.

What does the commercial counterpart offer here?

Dunno... but should GIMP care and target a worse solution cos someone else is behind? What I know is those other commercial apps implement better things in other fronts, like dithering in some operations to avoid histrogram holes or 16/32 bit buffers to edit high dynamic range images or whatever, and we are talking about giving crappy results always cos the computer takes some seconds more when asked to be more precise.

GSR

On Tue, 2005-03-01 at 22:48 +0100, Daniel Egger wrote:

On 01.03.2005, at 16:42, GSR - FR wrote:

"GSR" (?) already gave such an example. It might be worth considering only supersampling when the end of a segment is
a different color than the start of the next one.

Supersampling is to avoid aliasing, which is not caused only by those discontinuities but high frequency data (IIRC abrupt change is like infinite frequency). You can have aliasing with a square wave (segments that do not match) but also with a sine wave (segments that match).

Right. But where in reality can this happen using a gradient blend?

I just played around with the blend tool on a 100x100px image and looked very closely for any artifacts with and without supersampling. The result was that I couldn't produce any visible aliasing effects no matter how hard I try other than by using a sawtooth repeat pattern. That seems like a *huge* price to pay for something that can be easily done by accident.

What does the commercial counterpart offer here?

Photoshop does not do antialiasing. It also does not offer as many gradient types that are likely to need it (for example spiral).

It ought to be easy enough to detect when antialiasing will be needed and automagically turn it on.

I havnt looked at the supersampling code yet, but I think it might be much faster to do the supersampling in a second pass since such a small percentage of pixels actually need it.

Jay Cox jaycox@gimp.org

Hi,

Daniel Egger writes:

I just played around with the blend tool on a 100x100px image and looked very closely for any artifacts with and without supersampling. The result was that I couldn't produce any visible aliasing effects no matter how hard I try other than by using a sawtooth repeat pattern. That seems like a *huge* price to pay for something that can be easily done by accident.

Sorry, but I don't see your point. It has been show that supersampling makes sense for some corner cases. It is off by default and users can activate it in case they run into one of the corner cases. Of course it could be faster but where's your problem?

Sven

Hi,

Daniel Egger writes:

No problem on this side of the wire other then that is feature is counterintuitive, slow, undocumented and pretty much useless for the blend tool except for deliberate cases.

I agree that it is slow, but it is certainly not counterintuitive, it is documented and it is useful. The fact that it is not generally useful is reasonably reflected by the fact that it is off by default.

Sven

Hi,
jaycox@gimp.org (2005-03-01 at 2059.06 -0800):

It ought to be easy enough to detect when antialiasing will be needed and automagically turn it on.

I havnt looked at the supersampling code yet, but I think it might be much faster to do the supersampling in a second pass since such a small percentage of pixels actually need it.

That is what adaptive means, it computes extra samples in the pixels that change too much. But instead of checking at the end, it checks at the same time it calculates the gradient, and does not compute more samples than needed. IIRC, exactly what POVRay does.

If you make it auto, it is going to go always slower due the forced extra checks, instead of letting the user decide if the result is poor or not for what he wants: checking a gradient that is ultra smooth is a waste, a poor result that is later processed with noise or blur is not so "poor"....

IOW, supersampling is nice for the small set of cases in which it really matters, otherwise it is going to be slower always. Of course, it is going to be faster in many cases than full sampling and scaling down. If anybody figures a better method than user selectable adaptive (best case as fast as no oversampling, worst case as slow as adaptive), I guess POVRay Team will like to hear too. :]

Or maybe GIMP could also do the background trickery as reported in other mails, do not compute composition stack when it is not needed (areas out of image window, zoom not 1:1, fully opaque normal pixels...) and many other things to make it feel fast.

GSR

Hi,
de@axiros.com (2005-03-02 at 2158.27 +0100):

My assumption here is that if the adaptive supersampling code takes magnitudes longer to render than without supersampling it could be benefitial to simply use the common code to the render x times the amount of tiles to fill and simply do some weighting on this data to fill the final tile. Very easy, reuses existing code, runs multithreaded and is likely quite a bit faster than the stuff now is.

With your idea, calculating the full 3000*3000 with a depth of 3 is like calculating 9000*9000 (81 million pixels in RGB, 243*10^6 bytes plus overhead) and in time it should be 9 times the 3000*3000 non adaptive version plus the scale operation. To avoid absurd memory usage, the code will have to be more complex than just render big and then scale down. It could sample multiple planes and average (9 stacked tiles, each with a small offset for the gradient sampling).

Current adaptive is not paralel but the algorithm, at the logic level, is paralelizable in tiles, or groups of tiles to not waste so much in edges. The other gradient methods were non paralel in older versions anyway.

So I did some rough tests, 2000*2000 with adaptive vs 6000*6000 without adaptive (9000 was too much for my computer, so tried 2 and 6, same 1:3 ratio and still big). Small with adaptive was 10.3 sec and big without adaptive was 9.6 sec for linear black to white from one corner to another or side to side.

Using the rainbow gradient of my other post, 60 pixels sawtooth (or 180 pixel for the big version) side to side or up down, times were 27.9 (*) and 32.1 sec. With distance 400 (or equivalent 1200) they were 13.2 and 32.2 sec. With 1200 (or 3600) I got 13.0 and 32.1 sec.

[* Interesting detail: the progress bar changed speeds constantly when doing the gradient vertically but not horizontally. My guess is that I was seeing how the system computed the changing parts with more samples and went faster with flat parts.]

Same gradient again, but doing with pointer a diagonal reported in status bar as 21 21 (or 63 63) times were 65.2 and 32.2 sec. For diagonal 10 10 (or 30 30) times were 85.2s and 32.1 sec. Diagonal 5 5 (or 15 15) 112.7 and 32.2 sec (this is the case where the rainbow ends as muddy lines).

Then you have to add scaling time to the big version, around 4 sec with linear or cubic and 9 sec with lanczos in my computer (I did not put a timer around that call, sorry, used a wrist chrono). So render big and scale down seems to be a fixed time of 36 or 41 sec.

Your idea does not seem to be always faster, not approaching the 10x magical "order of magnitude" in many cases but 3x in extreme ones and a big memory hog if done naively. Only cases in which it is faster are when adaptive has to calculate all the samples, due the test overhead being a complete waste.

===

Update after letting the mail rest for some hours:

I decided to read again the oversampling code, and try to understand the real meaning of "max level", to see if what my long memory was saying about being a power factor not a multiplier, like in POVRay, was true (Quartic notes it was his inspiration). I needed a fresh recheck of the algorithm.

I see "sub_pixel_size = 1 << max_depth;" which means level 3 can do 9 * 9 = 81 samples for each pixel, of which the bottom row and right column are shared with neighbor pixels. Your idea, to match this, is not 3 * 3 but more, in the order of 8 * 8 = 64 (remember this adaptive code reuses results, so lets stay below 9*9 to be fair). Max level is the level of recursion, not the number of subsamples per axis. http://www.povray.org/documentation/view/3.6.1/223/ has a graph about how this adaptive recursive sampling is performed (the +AM2 switch method).

I am not going to explain quantization errors, antialiasing or anything again in this thread, it seems to only waste my time to demostrate again and again things people have been doing for some years in other programs. "Adaptive" or "recursive" are not something people just put there to have buzzwords, but as time savers for when only a small (or even medium, that is: most of the times) set of pixels really require oversampling. In Gimp, and in POVRay, it is nice to be able to disable it when you can go with the normal sampling (smooth gradients, test renders, etc), it is faster without doubts as it avoid checks. When you want oversampling, adaptive one is faster in many cases than full sampling, otherwise it would have been silly to design and code it in first instance.

Now, to finish it and confirm the absurdity of full sampling, lets do a "quick" test with 16000 * 16000... better no, dialog asked for 1.91 GB. So 8000*8000 and multiply by four, it seems to be linear when not using adaptive anyway. 55.1 sec for gradients and 6 or 10 for scaling. By four that is over 240 sec.

Slow test would be repeating all the tests of 2000*2000 with adaptive using max level of 1 or 2 (which is when the quality is going to be similar, 1 will be less, 2 will be more than your 3*3 sampling) and keep the 6000*6000 results. In which of course I am not going to invest time.

So please, apples to apples and oranges to oranges.

GSR