Gradients: a Halftone Gradient

So much to do: so little time! I have 3 other fun subjects to blog about... all of them in varying states of completion. But this is the most finished, so it's the first to write up.

Halftone Gradients

I don't know why, but I've always wanted a gradient that looked like halftoning.

But for some reason whenever I thought of tackling it: I always envisioned myself writing a PaintContext and coming up with some ugly code that involved lots of varying radii, and antialiasing things by hand, and doing clever things with AffineTransforms and dot products that I'm not really well-versed in. And maybe that is the better/more efficient way to approach this subject... but there's a much easier way.

My last blog entry used transformed tiles to achieve a multiple-color gradient. If you look at a halftone gradient as a tiling pattern, then suddenly it becomes a piece of cake. I just need to create a tall, skinny tile that transitions from one color to another.

If I were a better blog author, I might try inserting a diagram here. I'd demonstrate exactly what the tile looks like, and maybe discuss the concept of halftoning a little bit more.

However I'm not a better author. I'm much too lazy. Plus (and I'm not *entirely* bs-ing here): I really do believe a hands-on interactive model will explain this project more thoroughly than diagrams ever will. So... here's a demo applet showing off the HalftoneGradient class:



The jar (source included) is available here.

Your Basic Options

Although I started with circles, it's even easier to make a tiled pattern using diamonds or isosceles triangles. The size of each shape scales in proportion to the width of the tile, and where in the gradient that shape is drawn.

I'm unsure, though, if the circles are done correctly. I didn't find an exact algorithm for describing how halftoning should work -- but I admit I didn't look too closely. If a gradient is expressed in terms of t=[0,1]: does the gradient at t = .5 really look correct? Is that a half-way point between the two colors? For the circles I made the radius related to t^.8 to try to improve the balance. There is surely a more scientific way to approach this subject, but I didn't have the interest or patience. Does anyone have any experience with this subject? Basically the proportion of color1 to color2 should increase linearly with t.

Oh, and as an afterthought I added the "offset" property, and the "animate" checkbox. How could I resist? (Have you seen my art? I love animating things.)

Making a Tiled Pattern Not Tile

This paint delegates all the hard work to a transformed TexturePaint, so it should be tiling like mad when the "Cycle" checkbox is unselected, right? This was probably the hardest part of the project: if a point lies outside of the strip created between P1 and P2: how do I make it a solid color?

Originally I went to Sun's website and downloaded the source for the TexturePaintContext. I was determined to roll up my sleeves and make an adaptation that solved this. It didn't take me long to realize I was waaaaaaay over my head, though, as I looked through their source code. Aside from subtle problems (like referencing non-public classes to manipulate rasters), they somehow eliminated floats/doubles. Everything was int-based, on a scale of [0, Integer.MAX_VALUE]. While probably more efficient: this hurt my head. If you locked me in a dark prison cell with just bagels and a laptop: maybe in a few days I could figure this out. But I wanted to figure this out in a few hours, so I moved on to plan B:

Instead I just rewrote the raster the TexturePaintContext returns. Is it the most efficient response? No. Does it work? Yes. The class is called CoveredContext. (It's non-public, although it's included in the jar mentioned above.) In its original draft the hard work looked like this:

public Raster getRaster(int x, int y, int w, int h) {
     WritableRaster raster = (WritableRaster)context.getRaster(x, y, w, h);
     ...
     double[] matrix = new double[6];
     transform.getMatrix(matrix);
     for(int y2 = 0; y2 < h; y2++) {
         raster.getDataElements(0, y2, w, 1, data);
    
         for(int x2 = 0; x2 < data.length; x2++) {
             double x3 = x2+x;
             double y3 = y2+y;

             // apply the transform manually:
             y3 = matrix[1]*x3+matrix[3]*y3+matrix[5];

             if(y3 < 1) {
                 data[x2] = color1;
             } else if(y3 >= distance-1) {
                 data[x2] = color2;
             }
         }
    
         raster.setDataElements(0, y2, w, 1, data);
      }
      return raster;
}

The final draft, though, is much more mathematically clever. (It calculates the two x-points in a row of pixels that mark the beginning and end of the gradient, and flood fills everything beyond those points.) But it's basically the same approach in spirit. It involves many more special cases, though.

Conclusion

So there you have it. Very painless. The code, including comments and javadoc, probably comes to less than 500 lines of code. Eventually I plan to integrate this into some other projects I'm working on, but that will have to wait.

I haven't tried to break this down and scrutinize performance yet. This class first needs to demonstrate that it, in fact, useful...

Gradients: a Boring Discussion

This really is a boring entry. In most of my articles I tried to include some sexy snippets of code, but this article is just an exploration of gradients and paints. There are no exciting conclusions. But I learned a lot, and in case you find yourself researching the same topic: here's what I found.

The catalyst that started all this was when I started studying some old code at work. A few years ago we devised a series of complicated mechanisms to help optimize rendering gradients. (Most of them were somehow based on Vincent Hardy's Java 2D API Graphics book.) Did our tricks work? And if they did: do they still?

In this entry when I say "gradient" I'm referring to what is now known as a MultipleGradientPaint. This is now standard in Java 1.6, but in earlier versions the only official Paint that came standard with Java is the GradientPaint (a 2-color gradient).

One problem here is that there are, to my knowledge, only a couple of gradients to work with. There are the linear and radial gradients in Hardy's book. Then later on Batik came along with linear and radial gradients designed for SVG. Funny thing is: Vincent Hardy helped write these, too. (Along with Nicholas Talian, Jim Graham, and Jerry Evans.) Which makes sense, but for the sake of this article I'd like to have some really distinct classes to compare.

A Simple Java 1.4-friendly Linear Gradient

So my first priority was to make a really simple alternative gradient to test against.

A few years ago Romain Guy pointed out you could improve performance with horizontal and vertical gradients if you used a TexturePaint instead of an actual gradient. And last year I combined TexturePaints with AffineTransforms in this article. So if you consider a linear gradient as basically a repeating tiled image... and you can transform that tile... then voila! You can make a GradientTexturePaint.

This paint creates a 1-pixel tall tiled image, and then finds the appropriate AffineTransform to make that tile stretch the two control points you provide. Here is a demo. Use the slider at the top to control the colors, and the two white circles adjust the endpoints of the gradient:

(You can download this demo, source included, here.)

You can right-click the preview area to change the rendering hints. Using Sun's pipeline there is a visible difference when the interpolation hints are set to BILINEAR or BICUBIC. For convenience I also made the ANTIALIASING key affect the interpolation, too.

Under Quartz, however, you have to set the INTERPOLATION, and define the COLOR_RENDERING. It doesn't matter what it is (SPEED or QUALITY), but it has to be defined. But the code I added to intercept the ANTIALIAS hint doesn't work... ugh. It's a wreck. Quartz is forever a mystery.

Meanwhile, here is a screenshot contrasting the difference RenderingHints make:

The biggest downside to this gradient is that it has to tile. (Unlike the GradientPaint class, which shows only one color beyond the two control points.) Also, as we see later: it's performance isn't great.

But the advantages are:

• It's Java 1.4 compatible. (Java 1.3, probably?)


• It requires no other classes. It's very lightweight to add to your project.

So. Problem #1 solved: I have at least one more gradient to compare.

Comparing Gradients

Let's focus on linear gradients. Here are the classes we can test against:

1. com.sun.glf.goodies.GradientPaintExt from Hardy's book.


2. com.bric.awt.GradientTexturePaint mentioned above.


3. org.apache.batik.ext.awt.LinearGradientPaint from Batik.


4. java.awt.LinearGradientPaint in Java 1.6+.


5. DelegatePaint: this is a small shell wrapped around the java.awt.LinearGradientPaint. I wanted to see if the LinearGradientPaint was receiving special optimized treatment under-the-hood in the graphics pipeline.

I put together several tests -- each test measures the median time and memory allocation required for an operation. The tests include:

• Creating PaintContexts.


• Calling Graphics2D.fillRect().


• Calling Graphics2D.fill(Ellipse2D).


• Performing these operations through a small AffineTransform.


• Also compare what it costs to recycle a gradient vs constructing it from scratch.

The test I used is here (source included). Here are the results after running it in a variety of environments.

There's a lot of data. Oiyee. What does it mean?

Creating Rasters vs Blitting

For starters: look at the first two lines. This involves getting a PaintContext and calling PaintContext.getRaster(). Notice that these are considerably faster than the next couple of lines that involve calling Graphics2D.fillRect() for the same number of pixels. This brought me to my first sad realization about Paint objects: the bottleneck in performance is deep in the graphics pipeline. This makes sense, but it is frustrating because it's harder to modify that behavior. Werner has taken on the task of creating a new Graphics2D pipeline, but it's a big undertaking.

Where does the rest of the time go? In the Sun pipeline (that is, when Quartz is not active), the time may look like this:

The vast majority of the time is spent blitting. This seems especially unfortunate for simple calls to fillRect() (because the "hard" work is already done, right?). But it is what it is.

Using Small AffineTransforms

What about those lines that usually take 1-3 milliseconds? The tests with "reduced" in the name? These paint both rectangles and ellipses through a transform that scales the x and y coordinates by 0.2.

The catch here is when Quartz is active: it doesn't do too well. This is where the "optimized" keyword comes in. Based on this research -- and some of the old code we had lying around work -- I added another method to the OptimizedGraphics2D class. Basically when using Quartz, and painting with anything other than a java.awt.Color, we get the raster from a PaintContext and then paint that as a BufferedImage. It looks something like this:

PaintContext context = currentPaint.createContext(ColorModel.getRGBdefault(), 
    rect, rect, getTransform(), oldHints);
BufferedImage scratchImage = getScratchImage(rect.width, rect.height);
WritableRaster paintRaster = (WritableRaster)context.getRaster(rect.x, rect.y, rect.width, rect.height);
BufferedImage newImage = new BufferedImage(context.getColorModel(), paintRaster, false, null);
Graphics2D g = scratchImage.createGraphics();
g.setComposite(AlphaComposite.Clear);
g.fillRect(0, 0, rect.width, rect.height);
g.translate(-rect.x, -rect.y);
g.transform( myTransform );
g.setColor(Color.black);
g.setComposite(AlphaComposite.SrcOver);
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, 
    RenderingHints.VALUE_ANTIALIAS_ON);
g.fill(s);
g.setTransform(identityTransform);
g.setComposite(AlphaComposite.SrcIn);
g.drawImage(newImage, 0, 0, null);
g.dispose();
drawImage(scratchImage, 
    rect.x, rect.y, rect.x+rect.width, rect.y+rect.height, 
    0, 0, rect.width, rect.height, 
    null, null);
newImage.flush();

So we're painting the mask in black, and then using a SrcIn composite to render the fill of our paint.

I'd recommend avoiding Quartz if you can. This is one of a handful of surprises we've found over the years, and Apple has been steadily pushing the Sun pipeline for some time now.

Note that in these tests (in the GradientTest app), there is a crucial line involved in testing:

OptimizedGraphics2D.testingOptimizations = true;

This means the code I mentioned above is always being called. But in regular usage that method will only be called when Quartz is active. (The OptimizedGraphics2D is very careful about when it employs its special tricks.)

What About the Delegates?

Good news! The delegates are worthless. In Java 1.6 I wrapped the awt.LinearGradientPaint in a custom Paint object (and also wrapped their PaintContext, too). I know java.awt.Colors and java.awt.BasicStroke used to get special optimized treatment in Quartz (and maybe in Sun's pipeline?)... so I wanted to see if that was the case here. It isn't. This is great: it means what we see is what we get. And it means we can ignore those columns of data.

What About Sharing?

Here "sharing" refers to using a static gradient, instead of constructing a new gradient object in each test.

In the "Java 1.5" and "Java 1.6" tabs, there is practically no difference in the time it takes between sharing and non-sharing tests. This is also welcome news. It means the Paint objects aren't doing any clever caching of their own, and it makes developers' lives easier.

However. When Quartz is active, there's a speed improvement gained by sharing the gradient object. And the memory allocation? Wow. 0 bytes in some cases? Something special is going on here. And I have no idea what it is. Moving on. (Seriously, how am I supposed to cover all this material?)

The Gradient Classes

One of the most obvious comparisons is to look at the columns side-by-side. What stands out?

The first thing that pops out at me: the GradientTexturePaint loses. It's not horrible, but it's always behind the other classes in terms of speed.

Surprisingly in Java 1.6 the Batik class slightly outperform the awt class. I assumed the awt class was, well, based-on the Batik model. The code should be the same, right? Apparently not. Calling fillRect() is 25% faster when you use Batik.

I find the memory allocation results are looking pretty shady here. The GradientTexturePaint takes 0 bytes to run some of these tests? I wouldn't be surprised if the tests/measured are somehow flawed. This doesn't make sense.

Managing Memory

Usually when I measure memory allocation, I add lines that call garbage collection before a sensitive block of code. But it turns out this can dramatically skew some results in this case: because of how some gradients are cached. (WeakReferences can get involved! Calling garbage collection unnecessarily destroys the cached raster they refer to.)

The more I look at this, the more is looks like the Java2D architecture for Paints was poorly thought out. A Paint has one real method of interest: createContext(). (Already I'm scratching my head: why not make the method called getContext()? The distinction is that create() requires making a new object, and get() might simply return an existing object. This could have huge implications if you paint thousands of lines at varying transforms. But this is trivial compared to the next part...)

A PaintContext has a magic method called getRaster(). It returns a Raster object. It looks simple enough, until you consider how it is used: you might be painting millions of shapes! Is each call to this method creating a new Raster? Rasters are huge; this can really affect how fast memory is burned through. Instead the method should accept a destination WritableRaster as an argument. This avoids the cost of creating new objects constantly. Also it clearly defines the role of the method. With the existing signature: I don't know what happens to a raster object when I hand it to the caller. Am I free to reuse it? Am I responsible for disposing it? The graphics pipeline may want to hang on to it until a certain number of rasters queue up, and then process it. (This would be especially useful if opaque shapes were rendering on top of each other: it may be the case that the first shape is completely obscured by latter shapes, so its raster is irrelevant. I'm not saying this is done: just that it's possible.)

However "good" paints do not create rasters constantly. Batik paints, for example, have a static method: getCachedRaster(ColorModel cm,int w,int h). As long as you're asking for a width and height greater than 32 pixels: one static raster will be continuously recycled. They've been doing this for years and the world doesn't fall apart, so apparently it's a safe thing to do. So if you're writing your own PaintContext: recycle your rasters. Look at Batik's example. (They also dispose/release rasters in a clever way.) Their example is important because it's efficient, and because it obviously works with the Sun pipeline.

Conclusions

I don't really have any conclusions; I just felt like this article should end with a "Conclusions" section. :)

The only useful things to come out of this are:

• I added a new trick to the OptimizedGraphics2D class. However as I phase out Quartz more and more, it doesn't seem that important.


• I made a light multiple-color gradient for Java 1.4. Since I strive to maintain backwards compatibility in most of my projects: this may quickly end up in my custom UI components.

If you aren't worried about backwards compatibility: Java 1.6's gradient paints look perfectly sound. The Batik classes outperformed them in some cases, but overall I think they're a perfectly good choice if you're shopping around.

I apologize for the haphazard way material was presented here, but there really is so much ground to cover. I could spent hours (and pages) studying the subtleties of the numbers I collected; it's hard to figure out exactly what is important and how to present it.

If you'd like to see me add more tests, or have insight into the results already mentioned here: please be in touch. If you have specific questions that might be hard to answer through comments please email me directly.