Anti-Aliasing in 256 Colours
English translation by GrosQuick (cbouthor@dtr.fr)
Originally published in DefCoN #2
Corrected and Extended Version for Hugi #13
Introduction
Sometimes we want to apply a blur effect to a colour image but cannot necessarily access a truecolour mode or a linear 256 colors palette.
Moreover, it's sometimes possible to apply a blur to a 256-colours image which doesn't have a linear palette (palette composed with only one shade, like grayscaled image for example).
If you still don't understand what I'm talking about, please watch the demo "Reve" by Pulse - it's a good example. Most 3d scenes in this demo are anti-aliased.
The Principle
Instead of having big differences between 2 colour zones, we apply a little blur to these two zones in order to avoid the famous "stairs effect", you'll understand this better after having taken a look at this picture:
- non anti-aliased line (this is true in ASCII too) -
ÛÛ
ÛÛ
ÛÛ
ÛÛ
ÛÛ
- anti-aliased line -
°²Û
°²Û°
°²Û°
°²Û°
²Û°
Anti-aliasing with a linear palette
With this linear palette, anti-aliasing is really easy to do. We only have to read all pixels of the image from left to right and from up to down. Then we calculate the average of the adjacent pixels.
This is the "fast" method, it's "powerful" but it doesn't always give the wished result. We usually call it "blur".
In the following diagram, we use the next formula to guess the color of pixel X:
X=(A+B+C+D)/4
Ú---¿
³ A ³
À----
Ú---¿Ú---¿Ú---¿
³ B ³³ X ³³ C ³
À----À----À----
Ú---¿
³ D ³
À----
The new value of the pixel can be found by a better method. I found it in the Zed3D doc by Sebastien Loisel. We still have the A, B, C, D and X pixels.
First of all, we have to calculate the average of the pixels A, B, C and D:
avrg_ABCD=(A+B+C+D)/4
Then, we calculate the average of avrg_ABCD with the X pixel:
X = (avrg_ABCD + X) /2
The final formula is:
X = [(A + B + C + D)/4 + X] /2
Anti-aliasing with a non-linear palette
A colour in a non-linear palette doesn't represent an intensity/luminosity as it does in grayscale. Moreover, the colours aren't structured in any way (apart from the random order of course) ... The index of the colour in the palette has no meaning, we can't use it to calculate the wished effect.
Because of this, we'll create a table which will contain the combination of pixels.
A colour in the palette is constitued of three values, the Red, Green and the Blue (RGB). The whole colours declared in the palette can be summarize in a cube where each axis corresponds to a coponent of red, green and blue. Let's look at the picture:
64,64,64 = wight
*------------------------+
/³ /³
/ ³ / ³
/ ³ / ³ green
+------------------------+ ³ ³ /blue
³ ³ ³ ³ ³/
³ ³ ³ ³ +-----> red
³ ³ ³ ³
³ ³ ³ ³
³ ³ ³ ³
³ *--------------------³---+
³ / ³ /
³ / ³ /
³/ ³/
+------------------------+
0,0,0 = black
For each combination of pixels, we need to determine the best value of red, green and blue in order to reach the best result. We'll never reach the optimal colour but only an approximate one (the best fit).
For example, we've got 2 colours defined by their RGB values:
color 1 = 10;40;20 (R,G,B)
color 2 = 30;10;20
result = (10+30)/2; (40+10)/2; (20+20)/2 = 20;25;20
We've simply calculated the average of each value of the colour. This is the optimal colour, it's probably not in the 256-colours palette but a colour close to it will do the job. The color (20;25;20) is the nearest color in the palette. At this step, our cube will be useful. In fact, the colours are defined like 3D coordinates so it's not hard to find the distance between these 2 colours. This makes a vector appear, its origin is the first colour:
distance = sqrt[(R2-R1)^2 + (G2-G1)^2 + (B2-B1)^2]
The square root is useless in this case, we can simplify it:
distance = [(R2-R1)^2 + (G2-G1)^2 + (B2-B1)^2]
The closer the distance is to 0, the closer we are to the optimal color.
Creating the colour table
Now we are able to create our table. This will be 65536 bytes long because we have 256 colours in a 2D array. We can't create a 3D or 4D array because it would be too large... We'll call this "precalc" :)
BTW, don't forget to recreate a new table if the palette has changed.
The loop to create this table would look like this:
precalc[256][256]
for yc = 0 to 255
{
for xc = 0 to 255
{
1. load the RGB components of the XC color
2. '' '' '' '' '' '' YC ''
3. find the average of the XC and YC components
4. look for the best approximation of this color in the palette
5. place the best approximation in the array precalc[xc][yc]
}
}
The steps 1 and 2 are easy, we've got 2*3 = 6 variables : R1, G1, B1 for the XC color and R2, G2, B2 for YC.
In step 3, we have to calculate the average of this components, in order to find the averages called R3, G3, B3.
R3=(R1+R2)/2
G3=(G1+G2)/2
B3=(B1+B2)/2
This is the optimal colour, we'll have to find the best colour in the palette in step 4:
We'll search through the palette from colour 0 to colour 255 in order to find the colour closest to the perfect one. This would look like this:
old_distance = 70000 <== a number that is big enough
for C=0 to 255
{
1. load the RGB components of the C color into R4;G4;B4
2. calculate the shortest distance between R4;G4;B4 and R4;G4;B4 and
place it into "new_list"
3. if new_dist=0 then we've found the perfect color ! we exit the loop
4. if new_dist < old_distance then new_dist is better
old_distance = new_dist
}
The colour table has been created!
Using the colour table
Now we can apply the anti-aliasing effect. Remember, the formula were:
avrg_ABCD = (A + B +C + D)/4
X = [(A + B + C + D) /4 + X] /2
But we can't make the average of the colours because we aren't using a linear palette. It's easy, we need to access the table many times per pixel. 1st, we have to find the average colour for A and B:
AB = precalc[A][B]
Then we've to find the combination for C and D:
CD = precalc[C][D]
And now, the mix between AB and CD:
ABCD = precalc[AB][CD]
We finally have to mix that pixel with the X pixel:
COLOR = precalc[X][ABCD]
And that's all, you've got an antialiased pixel with a non-linear palette.
Let's optimize
If you haven't noticed yet, the formula only use divisions by 2, 4 or 8. With this, we'll gain a lot of time by shr value, 1 or value >> 1. However, we can further optimise the colour table precalculations.
Eclipse/Knights suggested a solution to me. We can half the time needed by this calculation because the values in the array are symmetrical in relation to the diagonal. For example, the pair 2;10 and 10;2 have the same value. So we only have to calculate one half of the array.
We can access the 2 entries array with a word. In order to calculate the position of a pair, we use the next formula:
color1+color2*256
With ASM, we can deduce the position like this :
mov bh,color2 ; put color2 into BH and multiying it by 256
mov bl,color1 ; BX=position
The colour table used for anti-aliasing can be used for transparency, it's nearly the same principle: we take color1 and color2 in the table and stop here. =) that makes the average between the 2 colors..
There we are, I hope that this doc will help you to do something, and that it is clear enough.
Dake/Calodox! - dake@omedia.ch
http://www.omedia.ch/pages/dake/
http://www.space.ch/scene/calodox