Original contents of the thread starting post:
When I was starting this project several I thought that when (and if) the RELEASE moment would come I would start a new thread with the phrase "What bothers me most in current OpenTTD is the way it handles zooming out." At that time I hadn't been aware about the existence of the patch available here: viewtopic.php?f=33&t=35311
Well, time passes by but some things doesn't get better than they were in old good nineties and not so old but still good 00ies
When the forum search had finally brought me to the topic above my implementation of the same "sprite-based SSAA" technique was already mostly done so for me it was more of a geek interest to took a lot at the sources of the patch TheBlasphemer posted there. Approaches we took in implementing basically the same thing turned out to be rather different, with his blitter being pretty simple (and, as a side results, code being pretty short and easily readable) and doing most of the work at draw time, while my implementation does as much work as it could at sprite loading (encoding) time. Another thing that my implementation does differently is that it supports palette animation and even is capable of doing SSAA for palette animated pixels. That comes with a price of reduced rendering speed and much more complicated code. Lastly, my implementation is capable of handling correctly 32bpp and "semi-transparent" sprites, while initial implementation of TheBlasphemer's blitter simply throws out any transparency it encounters on the way; later implementation tries to deal with the non-opaque sub-samples in a more gentle way but as far as I could tell basing on my knowledge of the topic, it should suffer from "visible seams at the edges of the ground sprites" problem. In any case, a lot of time had passed since 2007 and one would have next to none success in trying to use later implementation (Blitter_32bppOptimized internal encoding format for sprites storage had been changed in an incompatible way) and would suffer various transparency-related bugs with initial implementation.
Enough about past, let's get back to nowadays. What have I got to share for OpenTTD fans? As the topic SUBJ says it's yet another blitter for OpenTTD that uses sprite-based anti-aliasing technique for eye-candy purposes. What's sprite-based anti-aliasing? Well, it's the technique that tries to approximate the result of doing sprite-based rendering to Nx resolution and then linearly interpolating it down to the original resolution by offloading "linear interpolate down" step from the draw time to the sprite load time and performing it on individual sprites instead of entire image. De-facto it roughly_ the same as providing a separate version of the sprite for each existing zoom level (there are 6 zoom levels in OTTD now) with downsampling done by graphics designer in a way other than "nearest neighbour". Essentially almost everything that proposed blitter implementations does could be done by manipulating sprites in baseset and other used GRFs, but that would require a lot of hand-work to be done. SB AA blitter does this work for you in realtime but you pay for it with reduced rendering speed and enlarged memory footprint.
Let's dive deep into the gory details and implementation difficulties.
Why is it not possible to simply implement something more fancy than "nearest neighbour like" algo in engine if it in any case resize sprites down on load internally when GRF don't supply a version of the sprite for each existing zoom level? The answer is "it is possible in general but would only work for unmasked 32bpp sprites"
(link points to a thread containing another path that implements exactly that).
Main problem with 8bpp spites is that they have to be converted into RGBA representation before performing linear-interpolated downsampling and that's not generally possible due to some legacy concerns. First of all, there are some palette indexes that are used for palette-animation stuff. There's no correct way to downsample 2x2 matrix of such pixels into one target pixel retaining its "palette-animated" nature. Secondly, any GRF could introduce a thing known as "recolour sprite". It is a thing that allows to change the colour of some pixels at Draw() time. It's feature used to "paint" vehicles into the company colour. It is a thing that is used to draw the same city buildings or bridges in a differing colours. It is a thing that is used to draw catchment area (while choosing a place for a station) with a cyan rectangles while original sprite is grayish white. Most recolour sprites in the game are defined by the baseset but nothing stops clever GRF designer to introduce yet another recolouring map in the NewGRF he/she creates. As color remapping happens at the draw time there's nothing to do about when doing downsampling at sprite load time. And as the engine sets almost no limits on color indexes that could be remapped we have to assume that any colour index is a remapped one to be on a safe side.
To a greater extent it is possible to step on a slim ice and assume that it's enough to only correctly handle recolour sprites introduced by the baseset but the truth is that this assumption won't help: some recolour maps in the baseset cover the entire pallete range. But it had turned out that properly handling only a part of the recolour sprites from the baseset could still result in a pretty close to correct behavior. Recolour ranges that are being recognized by current blitter implementation are: palette ranges used for "company colouring" and "buildings colouring" (leaving behind proper support for "bare land", "church" recolouring), "catchment area colouring" and "secondary company colours". Same ranges had been used in "downsampling done properly" patch and it is able to produce not so bad results for some sprites but yet some other sprites wouldn't benefit from this and in the end they would be even more "eye hurting" by the contrast they would made to the sprites that had been handled well. Example of sprites that can't be handled in this way which you would encounter most are any water sprites with palette-animate capable blitter (32bpp-anim).
Thus the summary is: to be able to apply linear-interpolated downsampling to all pixels of the sprite one would have to do it at draw time.
Second challenge on the way to implementing sprite-based anti-aliasing is to find a method to deal with seams at the tile sprite "edges" that are introduced as a natural consequence of performing linear-interpolated downsampling. To help you get an idea of what's is this buzz about here is an illustrational picture (click on thumb to get full-sized 147KB PNG):
When the engine is downsizing sprite using nearest neighbour alike approach each target pixel is based on one and only one source pixel. It means that in case when source sprite consists of only fully transparent and/or entirely opaque pixels - same would stand for downsized version of the sprite. There won't be semi-transparent pixels introduced as a product of the resizing sprite down. Tile sprite shapes were designed in a way so downsized sprites produced by original resize algo would opaquely cover the entire target area when laid out correctly (as demonstrated by the left column on the pix above). With linear-interpolation things are different: some pixels in the downsized sprite would be semi-transparent due to being blended from a number of opaque and a number of transparent pixels. The more sprite gets shrink the more severe the problem is. Click on the pic above and zoom in to the "full size" (browsers tend to downscale the pic so its width would fit into the client area of the window) and take a close look on the bottom part of the central column. You would easily notice that the checkerboard-like background patter "shines through" pixels comprising the downscaled sprite.
How could this problem be dealt with? Real answer is: there's no entirely correct way to do it automatically with current tile draw infrastructure.
What we want is to warrant that for sprites representing ground tiles (I would call sprites like this "basement sprites" from here on) downsized image would have exactly the same "form of the fully opaque and fully transparent parts" with the exact shape of the parts being specific to on the target zoom level and tile slope. For non-basement sprites this goal could be bypassed. Trouble is that there's no easy way at engine level to distinguish basement sprites from non basement ones (check this
thread for discussion). Thus we have to treat all sprites as "basement".
Another problem on a way to "entirely correct" behavior is that we would have to hardcode in the engine a set of the "masks" representing the shape of the transparent/opaque parts for each tile slope direction and zoom level and then perform checks at draw time against this mask and alter the target pixels we produce basing on this mask. It would complicate and slow down the blitter greatly.
But there's a "clever hack" method to achieve virtually the same effect at downsample time without the need to use "shape masks": let's perform downsampling using the original algo as a first pass and temporarily store the result, then proceed with linear interpolated downsampling and the produce the resulting image using colour values of the second pass and the value of the alpha channel of the first pass. It's roughly the same as if we would create a layered image in the photo editing software of our choice and place as a "bottom layer" a sprite image that had been downsampled using nearest neighbour approach and then place on the top layer the same image downsized with the linear-interpolation. Take a look onto the third column on the picture above - it's done just like this. You could notice that using such technique produces "seamless ground sprite layout" and retain more details of the original picture - like linear downsampling does - at the same time.
If you're curios if there are any real visible in-game problems with the "straight linear-interpolated approach without the clever trick" above - here is the screenshot illustrating the problem:
It was captured with a special build of the engine that fill out every area it redraws with a magenta colour prior to drawing sprites. It could be seen that "seams between tiles" are easily visible here. Without the "development magenta floodfill" you would get "remains" of any colour that was at that place before as soon as you try to scroll the viewport, thy to zoom in or out, e.t.c. It might seem not to be "that visible" at a first glance but as soon as you would run into a green grid slipping between water tiles or a blue grid shining through the green land tiles you would be convinced that this is a real problem you have to deal with when implementing sprite-based anti-aliasing.
Let's move on to the next problem, the performance.
To characterize it in short: it sucks.
As a significant part of the downsampling process is had to be done in blitter due to reasons detailed above you might get the same (if not worse) performance you'd get with the direct per-pixel super-sampling approach (i.e. render viewport into Nx sized offscreen buffer using original_zoom-N zoom level and then downscale this buffer into screen resolution and blit it into the front buffer). Thus one might ask if there's any point in implementing SB AA blitter. Actually there is: the more 32bpp sprites we'd get the more performance SB AA blitter would gain. With the entire baseset made of 32bpp sprites and a minimum amount of "masked" sprites among them SB AA blitter would perform almost at the same speed as original 32bpp-anim blitter (but still would use a lot more memory for palette-animation tasks - anti-aliasing always come with a price). With the implementation attached to the first post of this thread it could be easily "felt on your own skin" by trying to scroll around with 32x zoom out using bare 8bpp baseset and then trying to do the same with installed/activated "Ben Robbins Ground with lines" and "Ben Robbins Fields Ground with lines" 32bpp NewGRFs (or with zBase baseset). You'd feel the difference especially if configure blitter to use higher level of AA for non-animated sprites (set "blitter-32bpp-aa-level" to 8, 16 or 32 in openttd.cfg in section "[misc]"; don't forget to increase "sprite_cache_size_px" to at least 128 while being there).
And coupled with the linear interpolated downsampling used for resizing down 32bpp sprites at load time it could cut AA costs to a negligible amount: you'd be able to set AA level to as low as 2xSSAA + 4 anim AA slots and still get pretty decent results.
Let's illustrate this theory with some screenshots. First of all, what are the gains for SB AA if the used baseset is 32bpp and mostly consists of unmasked sprites?
Take a look and judge:
This screenshot had been captured with a special development version of the blitter that highlight (with the red colour) pixels blended at Draw() time - i.e. not at the sprite load time. Blitter had been configured to use 4x AA for non-animated sprites which translates into 16 sub-samples max per one target pixel. In case the blitter had to blend together 16 possible sumsamples at Draw() time you'd get pure red in place of that pixel. If the blitter hadn't been forced to do any blending (i.e. required processing had been done at sprite load/encoding time) - a pixel is drawn as is without overlaying red. Draw-time blending for sub-samples count between 2 and 15 results in overlaying red in direct proportion to the sub-samples amount (dst = AlphaBlend[alpha = 255 * subsamples / 16, bright_red, dst]). Top part of the picture above was captured with "base 8bpp baseset" (i.e. no 32bpp GRFs active). You could see that for the most of the picture blitter had been performing downsampling at the draw time dropping the performance down to the unplayable level. Bottom part of the picture was captured during the same game session (i.e. without exiting the game and then starting it up back) but there I had activated 32bpp NewGRF based on the well-known "32bpp megapack" that was available for use with OpenTTD "extra zoom patch". As could be seen most pixels hadn't been blended by blitter at draw time making the performance sufficiently high for general gameplay while keeping the output quality at the very high level.
OK, but what is the general picture then? What you gain in quality by using higher AA levels? And would 2x AA be enough if using 32bpp baseset and "improved" resizing is in place? Here are the answers, they "speak" for themselves (pics are clickable as usual in this post):
And here are thumbs/links to the screenshots used to compose the above collage if you want to take a look at fullsized lossless-compressed originals:
What could be told by analyzing these? They prove the theories written above.
Let me summarize it here:
- 8x AA do not offer significantly better visuals compared to 4x AA (as expected: 16 subsamples vs. 64 is a cool thing but even 16 is enough for most uses).
- Downsampling sprites using linear-interpolation at load time (to a possible extent) isn't effective with 8bpp sprites.
- Downsampling sprites using linear-interpolation at load time is extremely effective for 32bpp unmasked sprites and even original 32bpp-anim "non anti-aliased" blitter produces wonderful results when coupled with it.
- Using higher AA levels for 32bpp sprites coupled with the load-time linear-interpolated downsampling is a useless waste of performance (while my implementation does its best to reduce draw-time performance costs for that case). Sticking with 2xAA + 2 or 4 anim AA slots or 4xAA + 4, 8 or 16 anim AA slots (if you have decent multicore CPU and enable multithreading for palette animation) is enough. And you could even don't use anti-aliased blitter at all for this case and still get pretty-enough rendering with original 32bpp-optimized or 32bpp-anim blitters. It could be useful if you have a slow single-core CPU or are short on RAM.
Last thing I want to write about in this post are the consequences of the "hack" the blitter have to use to overcome "visible seams between tiles" problem. If you're patient enough to read up to this point (take a candy, drink a beer, make anything to make yourself feel as a wonderful person you really are) and had been following the text closely you could wonder if are there any negative impacts on the quality of the rendered picture related to "clever hack". I have the bad news to share: there are some bad consequences and they are visible.
Here, take a look:
Left part of the picture was composed from screenshots of the game when using unmodified 8bpp baseset. Take a close look on how does the radio tower and oil refinety flame torch look like at 32x zoom out level. Pretty pixelated and aliased, aren't they?
On the right side of the picture you could see the same places/objects rendered with a special NewGRF activated that contains a small "trick" to effectively turn "fix seams hack" off for these particular sprites. I would attach this NewGRF to the second post of the thread so you could decode it with grfcodec and take a look into internals. Trick used is extremely simple: 8bpp base sprite had been converted into masked 32bpp sprite with mask being filled with 0 color index except for pixels that should be palette-animated and/or color remapped. Base sprite has its alpha channel modified in a way that all pixels with alpha == 0 are made "almost entirely" transparent (alpha changed to 1) and all pixels that had been opaque (alpha == 255) had been made "almost" opaque (alpha changed to 254). My blitter implementation is aware of this trick and treat any pixel with alpha <= 1 or >= 254 as transparent or opaque resp, but does not apply "clever hack" for pixels having alpha other than 0 or 255. Blitters that are unaware of this "trick" would suffer with a (major in case of the most screen being filled with sprites utilizing this trick) performance loss and next to none visual glitches. Sprite designers could made a special version of their sprite packs utilizing this transpareny trick in case blitter derived from my implementation (or any other using the same technique) would land into OpenTTD trunk. It could easily be scripted in the GIMP to scale alpha channel of the entire sprite into 1..254 range and then scale it back to 0..255 range using the selection mask appropriate for that case if any. Mask should exclude "top part" of the sprite and operate only on the "bottom" side of the sprite (where the line serving for division between "top" and "bottom" should pass through west and east corners of the ground tile).
That's more than enough text IMO so here are "closing words":
Testing is needed. Suggestions are welcome. Bug reports are welcome to go as repplies to this thread and PMs would serve as well for this purpose.
Thanks for spending your time reading this and trying this blitter.