Noodlings

I’ve finally gotten around to consolidating most of the bits of code I’ve posted on this blog over the years and put it in a repository. While the real NoodleKit is a much more extensive and cohesive toolkit that I use internally, this one will serve as a place where I put the odd scraps that I decide to open source. I guess I could’ve called it NoodleScraps but it doesn’t quite sound as nice.

If you’ve been following my blog for a while then there’s not much new here, codewise. There are a tweaks here and there plus the stuff should be 64-bit ready so it might be worth re-downloading just for that. It will be the place where I put future code so you should keep an eye on it.

The project is structured to build a framework but also has an examples directory (with corresponding targets) to demonstrate the use of the different classes. The current notion is to keep things compatible with 10.5. And, as usual, all code is released under the MIT license.

NoodleKit (hosted at github)

Enjoy.

Flipped coordinate systems always seem to confuse people, myself included. After working things out with pen and paper or handpuppets, I always feel like they’re not quite correct so I thought I’d resolve things here. If anything, I can refer back to it whenever I forget this stuff (which happens every couple years). First a refresher in case you need it: Cocoa Drawing Guide: Flipped Coordinate Systems.

The main thing to keep in mind is that while a flipped coordinate system is basically translating the origin to the top left and flipping things vertically, semantically it doesn’t mean that everything is upside-down. Images, text and other elements are supposed to render right-side-up. The flipped coordinates should affect where those elements are placed, not how they are rendered. Being flipped is a higher level notion and is separate from the
CTM. While setting something as flipped will flip the CTM, modifying the CTM without setting the graphics context as flipped results in everything being entirely upside-down, which is different. Many of the Cocoa classes and functions take flipped coordinate systems into account and will draw right-side-up for you but it gets tricky with images.

There are two sets of methods in NSImage to render it in a graphics context: the -composite... methods and the -draw... methods. I’ve put together an interactive example app to help illustrate the differences. It might help you to download it now so you can follow along. The figures included in this article are from that app

The -composite... methods actually seem to work in the sense that the image is always right-side-up. The problem is that it draws “upward” from the draw point regardless of the coordinate system. The result is you have to calculate the compositing point at the upper left corner of the image instead of lower left. This is the result of these methods not taking the CTM into account in terms of scaling and rotation. That also means that if you scale your view up, the images won’t scale with it. While you can use this to your advantage in some cases (like rendering resize handles or labels which you want to stay the same size regardless of zoom), it’s usually not the right way to do it.

View scaled at 2x. Notice how the composited version does not scale.

The -draw... methods on the other hand follow the CTM properly. That also means that if the view is flipped, so is the image, so you need to adjust accordingly. So while these methods obey the CTM, they do not take into account the flipped flag of the context which would be the cue to draw things right-side-up.

The draw... routines follow the CTM, but not the flipped flag.

Now, to complicate things even further, NSImage’s themselves can be flipped. The reason for this isn’t to make the images upside-down. It’s there to provide a flipped coordinate system for whenever you draw into it (i.e. lockFocus on it, draw, then unlockFocus). It’s useful for when you want to tell a flipped view to draw into an NSImage, for instance. It’s basically like a flipped view; you don’t expect a flipped view to draw upside down, no matter which view you set as its superview. A subtlety to be aware of is that flipping an image loaded from a bitmap does not make too much conceptual sense (you are changing the coordinate system after the content has already been “drawn”) but it does have the practical effect of flipping the image vertically, which seems to be an implementation detail. Yes, flipping the image will work to “correct” orientation problems in most cases but, depending on where your image gets its data (for instance if it has an NSCustomImageRep like the example app – see below) and whatever implementation-specific details lurk in NSImage, you may end up with undesired or inconsistent results.

As mentioned above, I’ve put together a little interactive example app (Leopard-only) to show how the different methods behave. In addition, I’ve written methods in an NSImage category (-drawAdjusted...) which will render the image correctly regardless of the flipped status of the coordinate system it draws into. As suggested in Apple’s docs, it does a transform reversing the flip, draws the image, then reverts the coordinate system back.

The image itself is drawn by code, not loaded from a bitmap. The reason for this is that I also wanted to illustrate using flipped images. It draws an arrow and some text to indicate the proper orientation. When flipped, the drawing code is exactly the same in that no coordinates are recalculated. The text content is changed to compensate for the new orientation. Notice how the text renders right side up no matter the flip state of the image; an indication that the NSString drawing methods are “flip-aware.” Also, it shows how to check the graphics context to get its flipped status so you can make your own drawing routines flip-aware as well.

Unfortunately, not everyone draws flipped images correctly. One place in particular is NSView’s/NSWindow’s -dragImage:at:offset:event:pasteboard:source:slideBack: method which will draw flipped images upside-down. Since you can’t control how the image is drawn, you can instead draw your flipped image into another non-flipped image and pass that in. I’ve added a method to the NSImage category to do this and you can check out the result in the example app (you can drag the image out of the views though only the last one has the corrected version).

And what if you actually want to draw everything upside-down, you irrepressible nut? Well, apply your own transforms using NSAffineTransform or CGAffineTransform. Just remember to concat the transform and not set it (a good general rule when using affine transforms). As long as you don’t tell any classes that you’re flipped, it should work out.

Hopefully this didn’t make things even more confusing (and also, hopefully, my interpretation of all this is correct). If you are still lost then just follow these rules:

1. Do not set images as flipped unless you know what you are doing.
2. Use the -drawAdjusted... methods in my category (or similar technique) to do all your image drawing.
3. If you didn’t listen to rule #1 and you have a flipped image and it is showing up upside-down even when following rule #2, then use the -unflippedImage method in my category to get an unflipped version of the image and use that instead.
4. Never go in against a Sicilian when death is on the line.

That should handle most cases you run into. And trust me on rule #4.

This has come up a couple times in the past couple months leading me to believe that there are others out there who might benefit from this. I’m overdue for an post anyways.

The question: How do you draw shapes with holes in them? (i.e. How do I draw a donut?)

Short answer: Winding rules.

So what’s a winding rule? A winding rule is a way to determine whether a point is inside or outside a shape, useful for when you want to fill a shape. Quartz (like Postscript) has two different winding rules: even-odd and non-zero.

Non-zero is the default. How does it work? Take the point in question. Follow a line from that point extending out to infinity. Now, maintain a count. Increment the count every time you cross the path with the path going from left to right. Decrement whenever you cross a path going from right to left. In the end, if the count is zero, you are outside the shape, otherwise you are inside.

In the diagram above, the final count is zero. Note that this is a compound path (remember, paths do not have to be contiguous). Our imaginary ray crosses the path twice but does so with the paths going in opposite directions. This means that the point in the middle of both circles is considered outside the shape. Voilà , a donut.

With even-odd, it’s a bit simpler. Draw a line out from the point but just increment every time you cross the path (regardless of direction). If the resulting count is even, you are outside, otherwise you are inside.

Except for the labels on the axes, the pic below is actual output from a Cocoa program showing different combinations. The top two shapes have the outer and inner circles specified going in the same direction. The bottom two have the inner cirlce going in the opposite direction as the outer. The shapes on the left are drawn with non-zero winding while the two on the right are drawn with even-odd. Paths are stroked in white.

Notice how the direction of the paths does not matter for even-odd. Also notice how in the case of non-zero with the paths going in the same direction (top-left donut), the inner circle is considered a part of the shape’s interior. This shows that non-zero gives you more control (you can control what parts of the shape are considered inside by adjusting the direction of the paths). It is also more tedious to deal with for the more simple cases. To draw donuts using non-zero, I did the outer circle, created another path for the inner circle, reversed it and added it to the outer circle’s path. Using even-odd, all I had to do is set the winding rule on the path. For more complex cases, the control of non-zero winding may be required but for simple shapes like donuts, use even-odd. Why you’d ever want to draw anything else besides donuts is beyond me; donuts are delicious. While this knowledge can be applied to other less worthy shapes, I cannot be held responsible for the jeers you will undoubtedly receive for even daring to allow to cross one’s mind the slightest notion of contemplating considering drawing anything non-donut-like.

I’m too lazy busy to clean up the code for you to download but play with it yourself. It can all be done via NSBezierPath (key methods are -bezierPathByReversingPath and -setWindingRule:). Also, the winding rules can apply to clipping as indicated by the following pic:

For extra credit, play with self-intersecting paths.

Enjoy.

For the past couple weeks on and off (mostly off), I’ve been working on this gradient code. In my previous post, I mentioned my attempts at vectorizing it which resulted in no performance gain in the end. Here, I recount a tale of writing a generic gradient method in a NSBezierPath category. Yes, a tedious story, but this is a blog after all, plus you stand to get some actually-useful, free source code in the end so bear with me. Or, like a kid pouring all the cereal out of the box to get the glow-in-the-dark prize inside, you could, through the power of the scrollbar, skip all this and just grab the code.

So yes, I wanted to write a category to provide a method to fill the path with a gradient. Of course, you need to provide a start and end color but I also thought, why not also provide an angle? I didn’t need to do gradients at arbitrary angles (the only gradients I need right now are vertical) but when writing this stuff, I like to make it generic. When Apple starts using -23.728° angle gradients all over the place, I’ll be ready.

Now, the issue is figuring out the starting and ending points for the gradient given an angle. You want the gradient to fully fill the path. Let’s take filling a rectangle at a specific angle:

In the figure, with an angle α and a starting point A, you’d want the gradient to end at B to maintain the angle and also fill in the opposite corner of the rectangle. Recalling the trig and geometry from the deep recesses of my mind, I came up with the following equation (using known quantities w, h and α):

x = sqrt(h2 + w2) * cos(α - atan(h/w)) * cos(α)

I was a little disappointed that this didn’t reduce down to something a bit more tidy (makes you appreciate E = mc²) but it did seem to work. The problem: not every path is a rectangle. While using the above does cover whatever path may be bound by that box, it is not optimal. Another diagram is in order.

In this example, there’s slop at the start and end. Imagine pulling a squeegee from point A to point B. There’s a gap before you hit the shape starting from A and then a gap after the shape before you hit B. How does this affect the gradient? Why is Mr. Sun sad? See below:

All these diagrams were done in OmniGraffle (except for Mr. Sun which obviously required more sophisticated software). You can see that the “L” shape on the left has a truncated gradient (the black is somewhere where the upper right corner should be). As a user, I’d expect that if I had specified a gradient from white to black, that I would get that range within the shape, otherwise, I would have specified gray as the darker color. It appears OmniGraffle is shading according to the bounding box. Here’s another picture:

The first shape I freehanded with the correct orientation. The second is the “L” shape from the previous diagram rotated. Notice the difference in gradients. It seems to me the user should not need to care how the shape was originally created. The gradient should be white to black in both cases. By the way, I’m not picking on OmniGraffle; I was using it for these diagrams and decided to test it’s behavior in this regard since I had it running. My guess is that this is the common behavior for software implementing gradients with rotation.

If someone specifies an angle and start and end colors, then the final result should be at that angle and have those start and end colors visible in the gradient and not cut off, dag gummit! I feel in the ideal case, you should really be filling the shape with a gradient, not just providing a window to what ever portion of the gradient happens to be lined up under the shape.

The problem here is that we are using the bounding box in the original coordinate system. What would be ideal is to calculate the bounding box in a rotated coordinate system so we can get the minimum span along the axis of the gradient (the line going through A to B in the first two diagrams).

In the case above, we want the bounding box on the right.

My initial approach was to apply the path to the current state, transform the coordinate space to the rotated space and get the bounding box there. The problem with this is that I was getting the bounding box of the bounding box in the original coordinate system. In a sense, I was getting what I originally calculated above. The solution was to transform the path and not the coordinate system.

After some futzing and some stupid mistakes which sent me down some dead-ends, I got it working. Rotate the path, calculate the bounding box and set the start and end points to the edge of the bounding box that corresponds to the gradient axis, then do an inverse transform back on those two points to get them back into the original coordinate system.

What does this get me? Well, for me personally, not much as I mentioned before I only needed to do a vertical gradient. But you, gentle reader, get to enjoy the fruits of my labor. This code is provided under MIT license. If you use it then just mention me and the Noodlesoft site wherever you put your attributions. And of course, if you have any bug reports, fixes, suggestions or whatever, send them my way so I can address/incorporate them.

Noodle Gradient Test + NSBezierPath-NoodleGradient category

I was writing some gradient code and while writing the gradient function it occurred to me that it could be vectorized. I was doing the same operation in a loop to two sets of 4 floats (the red, green, blue and alpha values that need to be calculated for the gradient). The 4 floats fit perfectly into a 128 bit vector. My reason for doing this was not because of any bottleneck observed in Shark; it was just a flimsy excuse to play with Altivec for the first time. Nonetheless, if there was a noticeable performance increase, all the better.

In between a wedding, entertaining friends who were staying with me and getting a beta release of Hazel out the door, I read a little on Altivec and cooked up a little test program. You can download the source below. It’s PowerPC with Altivec only. I was sloppy with the #ifdefs but compiling the test without Altivec support is a bit pointless. I don’t have an Intel machine so I didn’t write an SSE version. For you Intel readers at home, feel free to add the appropriate SSE code (and let me know what you come up with). You’ll find my guess at what the SSE version is supposed to look like commented out in the code (but don’t trust it; I don’t exactly know what I’m doing here).

What does the test show? Well, at least on the G4 and G5 machines I have available, performance is roughly the same.

Of course, there are two ways to interpret this:

My test sucks
(obligatory remarks: “I didn’t know they taught programming at clown college.”, “My [insert feeble relative] can code better than you”)

A very likely possibility. This is my first foray into Altivec and I just started delving into Core Graphics gradient functions last week. As far as my Altivec code goes, I am still quite fuzzy on whether I should have used something like vec_ld or vec_splat to turn the multiplier into a vector though I’m pretty sure that using the float[]/vFloat union fulfills the byte alignment requirements (though it’s possible that it’s slower). I’m guessing it’s the difference between sticking it in a register and having it in memory. If any SIMD experts could educate me on this, I’d appreciate it.

Vectorization is not effective in this scenario

I’m sure those much more experienced with Altivec can explain this without resorting to a tactic that we like to call “making stuff up”. Me, I am going make stuff up. So here goes: I’m only computing one vector at a time and I’m doing all these scalar to vector (and back) conversions. My guess is that the overhead outweighs the reduced instruction count in the computation. If the CoreGraphics functions were structured such that it gave you all the values at once (or at least in chunks) instead of at each step of the gradient, then I could see an argument for vectorization made here.

So for now the result is inconclusive until I can get someone who knows what they’re doing to either verify or refute my test. Try it for yourself and let me know (especially if your results differ from mine). And please point out any deficiencies in my implementation (though comments on coding style can go to /dev/hell).

GradientTest (PowerPC with Altivec only)