Noise in game art

If you look at the artwork in old 2D 8-bit games, you see a lot of
noise and dithering in the hand-drawn bitmap art. For an example, take
a look at the grass or concrete in this Transport Tycoon screenshot:

When the gaming world moved to 3D 32-bit vector art, we lost some of
that level of detail. We got lots of smooth areas. Eventually we mostly got the detail back by applying
textures to the polgons. However, it often looks worse to
me than the old hand-drawn art.

With my Flash experiments, I've been playing with 2D procedural vector
art, and I've been trying to figure out how to make it look nicer
without drawing textures by hand. The simplest thing I found has been
to apply noise to the art. On the left is some terrain without noise
and on the right is some with noise:

I like the noisy version much better.

The noise layer is fairly easy to apply; I use BitmapData.noise() to
generate it, and then use BlendMode.ADD to add it to the original layer.

  var noiseTexture:BitmapData = new BitmapData(128, 128);
  noiseTexture.noise(Math.round(Math.random()*65536), 
                     0, 8, 7, true);
  var noise:Shape = new Shape();
  noise.graphics.beginBitmapFill(noiseTexture);
  noise.graphics.drawRect(0, 0, size, size);
  noise.graphics.endFill();
  layer.draw(noise, null, null, BlendMode.ADD);
  noiseTexture.dispose();

It's nice in that it inherits the color already there; the noise
doesn't impose its own colors. However, this only works nicely on my
background terrain, and it feels somewhat slow on my low-end machine.

For foreground sprites, the noise layer doesn't move when those
sprites move or rotate. An alternative would be to draw the noise on
top of my sprites, using Graphics.beginBitmapFill(), but that would
require that I have a way to compute the outline of my procedural art,
so that I can draw the noise on top as a polygon. Another alternative
would be to use bitmap fills for every polygon, but that requires that
I have a noise bitmap for each color. And yet another alternative is
to draw every polygon twice, once for the color and once for the
noise.

With Flash 10 I had hoped that the pixel
shaders would allow
me to apply noise to anything. I played around with them a bit. The shader
receives the output coordinates in a function outCoord(), and can
compute a color for that location. It can optionally include
parameters (like a noise bitmap). The big problem is that the output
coordinates are in screen space. This means that when the sprite
moves or rotates, or if you zoom in, the noise would stay fixed
relative to the screen. I tried both using shaders for fills and
shaders for filters, and neither gave me what I wanted.

That's a serious problem for my use. To address this problem, I can
pass in additional parameters like rotation and offset. However, I
have to re-fill the shape every time I change the shader
parameters. Even worse, the pixel shader is recompiled every time you
fill.

So it looks like pixel shaders in Flash 10 just don't do what I want.
I want a way to get the pixel's location in the sprite's coordinate
system, after transforms are applied, but instead I only get the screen's
coordinate system.

I think my best bet for performance is to not apply noise to vector
backgrounds (applying noise to a bitmap won't impact
performance). This will make me sad but smoothness matters a great
deal. I should also try using tiles to see if that is any faster. For
foreground objects, it's probably not too bad to draw everything
twice, but I'll have to test this. It may not matter if I switch to
bitmap sprites eventually; they'd let me draw a lot more details.