0
101 May 11, 2007 at 12:03

Hi,
I’m curently trying to develop a software renderer.
For now i’m using a 256 color palette and it’s fine for rendering flat triangles.
Now i’m adding gouraud shading and i face a new problem :

I have one color per vertex in my triangles.
But as the color is just an index in the palette, how can i interpolate these colors across the triangle ?
Can i interpolate the indices ?
Do i need to setup a special palette ?
Or is it just impossible ?

I hope someone can enlight me on this.

Thanks.

PS: If you know some good tutorials/resources about software rendering i’m interested too.

#### 24 Replies

0
139 May 11, 2007 at 13:59

You can’t really do Gouraud shading with a palette.

Why are you working with a palette, anyway? Today’s computers have more than enough memory, bandwidth, etc to work in full 32-bit color with no trouble. Honestly, palettes are kind of a throwback to 20 years ago.

0
101 May 11, 2007 at 14:08

I’m developing under DOS ;-)
Lol, i’m kidding of course.

In fact i’m developing the renderer for an embedded device.
I probably could use a 16, 24 or 32 bits true color format but i don’t really need so much colors in my application. And as the memory capacity of the hardware is pretty low, i’d be happy if i could work with 8 bit color palettes.

Also, i would like to know if it’s possible or not, just for my personnal knowledge.
It seems to me that even in the old DOS days shading was possible. And in these old days, palette colors were frequently used. So there must be a way to do it.

Thanks.

0
101 May 11, 2007 at 14:22

You can load a special palette and treat your 8 bit per pixel as a color in packed 323 format. Exactly in the same way as you pack colors with 16 bit in the 565 format.

It will look ugly unless you add some dithering though.

0
101 May 11, 2007 at 14:30

You typically use specialized pallettes that allow a few steps of gourard shading. An example would be Q1’s palette (see http://www.gamers.org/dEngine/quake/wad_conv/palette.html)). In the ol’days a few demos would do everything greyscaled to get good looking vertex lighting and gourard shading.

0
101 May 11, 2007 at 14:31

Hi nils.
I’m going to give your solution a try. As you say i fear the result will look ugly.
I’ll have to read about dithering to see if it’s practical because i don’t really know what it is.

Thanks.

0
101 May 11, 2007 at 15:02

Hi SigKILL,
I don’t really see how the Q1’s palette can be used for shading.
Imagine i want to interpolate between green and red, how can the Q1’s palette let me do this ? Could you elaborate a little bit please ?

Thanks.

0
139 May 11, 2007 at 15:11

You clearly can’t interpolate between red and green with that palette. What you can do is interpolate between different shades of the same hue. As you see, there are enough colors to allow sort-of-decent interpolation from black to any of the basic hues in the palette. So, you can do white lights and give those hues to your triangles, but you probably can’t really do colored lights, unless you pick a different palette.

0
101 May 11, 2007 at 15:29

Ooops, sorry I was mistaking gouraud shading with smooth shades of the same color. My bad, just a freudian slip. The original message reminded me of a chat I had with an old demo-coder a few weeks ago…

0
101 May 11, 2007 at 18:57

Hi again.
Now i’m back home, i reread this again and i have an idea :-)

Well, in fact my problem is not directly related to lighting.
I just want to interpolate between two random colors.
What is interesting in the Q1’s palette method is that it precomputes the transition from an indexed color to the black color.
It’s just what i want but only for 1 color, the black one.
Now, if i precompute 256 of these maps, i have the shading transitions for all the pairs of colors.
Generating the tables is easy with the fitting color algorithm, it’s not fast but it’s done only once at initialization.
After that i just have a fixed steps of indexes for each pair of colors suposed to be shading nicely.
Of course it’s expensive. 1 meg of memory for just 16 transition steps for each pair of color…
But with a 256 color palette, 16 is probably already too much.

Anyway, thanks for the great help.
I don’t know if i have the best method for doing what i wanted but at least now i have one ;-)

0
101 May 12, 2007 at 16:12

You should probably do what Nils sugested. But use a 332 palette instead of a 323, since the bit-depth really matters when you have so few colors.

I took the time to make a little comparision of the different palette options. Note how a 332 palette looks considerably better than the other options:

0
101 May 14, 2007 at 10:09

Hi geon.
Thanks, i didn’t think about that.
I implemented the three formats (233, 323, and 332) and can’t really decide wich one is better.
It seems that the 332 format produces less “patterning”, but the lack of precision in blue colors is uncomfortable to the eye.
The 323 format is more comfortable to the eye, but it produces a lot of patterns.

Here are three pictures, one for each format :
RGB 233 : http://img511.imageshack.us/my.php?image=rgb233ux3.png
RGB 323 : http://img291.imageshack.us/my.php?image=rgb323dx8.png
RGB 332 : http://img142.imageshack.us/my.php?image=rgb332oa2.png

The result is not bad, but it’s a color cube, so it’s tha best case for all faces, if i pick random colors for each vertex, the result is worse.

One question, at the moment, i propagate the color conversion error along the horyzontal spans from left to right.
Would it be better to propagate it from top to bottom (or bottom to top) also ? Is it dithering ?

Once again, thanks.

0
117 May 14, 2007 at 10:39

The way I did it Back In The Day would be to generate a (more or less) optimal palette for the target usage (for instance by rendering truecolor images and deriving the palette using median cut from those images), and then use a 64k lookup table to find the desired color in the palette from a ‘virtual’ truecolor value.

And yes, this was in DOS. http://iki.fi/sol/zip/qmedian.zip is the color reducer, should still work =)

0
103 May 14, 2007 at 11:00

what he said.

0
101 May 14, 2007 at 11:26

Ok, so basicly it’s a table transforming colors from something like a color in RGB 656 format (64k -> 16 bits colors) into a color index in my palette, right ?

Sounds great, 64k of memory is not a problem, dithering is easy, and i can use any palette i want.
I wonder how it will look when trying to interpolate between too rare colors in the palette though. Especially with dithering..

Thanks.

0
101 May 14, 2007 at 14:33

Another option is to use only 16 main colours in your textures. You can make a single palette that then crossfades to all the other 16 colours just by addressing source colour as the first nibble nad dest colour as the second nibble.

Limits the source textures, but you’ll get lovely fades. I guess it depends on where you want your fidelity. Working with a palette isn’t going to give you much anywhere!

Look at older games such as speedball. The artists went with about 3 or 4 main colours and relied on nice fades for shading and it worked very well.

0
101 May 14, 2007 at 19:27

It looks like you’re using some kind of error diffusion dithering. Try out ordered dithering with a 4x4 dither-kernel instead.

It’ll look better. You get less weird patterns that way.

0
101 May 16, 2007 at 09:36

The method you use with the propagated error is indeed dithering. It’s commonly known as error diffusion.

You can try 4x4 ordered ditherig also, like Nils sugests. I don’t like the regular patterns it produces, but it might work better for you. (It’s supposed to be faster, too.)

Also, make sure you you use realistic test-cases, and optimize for them.

0
101 May 16, 2007 at 09:41

You can find the nice 4x4 bayer-matrix here:

0
101 May 16, 2007 at 11:19

While we’re at dithering: I’d like to share my 16x16 optimized pseudo error diffusion dither-tables. I’ve calculated them with simulated annealing some years ago, and they are optimized for a flat frequency spectrum (e.g they make sure the dithered result has as least repeatable patterns as possible).

If you want an overkill of quality use a different one for each color channel :-)

unsigned char Table_HqDither_red[256] =
{ // 16*16 dither kernel for high quality dithering
192, 11,183,125, 26,145, 44,244,  8,168,139, 38,174, 27,141, 43,
115,211,150, 68,194, 88,177,131, 61,222, 87,238, 74,224,100,235,
59, 33, 96,239, 51,232, 16,210,117, 32,187,  1,157,121, 14,165,
248,128,217,  2,163,105,154, 81,247,149, 97,205, 52,182,209, 84,
20,172, 80,140,202, 41,185, 55, 24,197, 65,129,252, 35, 70,147,
201, 63,189, 28, 90,254,116,219,137,107,231, 17,144,119,228,109,
46,245,103,229,134, 13, 67,162,  6,170, 47,178, 76,193,  4,167,
133,  9,159, 54,175,124,225, 93,242, 79,214, 99,241, 56,221, 92,
186,218, 78,208, 37,196, 25,188, 42,142, 29,158, 21,130,156, 40,
102, 31,148,111,234, 85,151,120,207,113,255, 86,184,212, 69,236,
176, 73,253,  0,138, 58,249, 71, 10,173, 62,200, 50,114, 12,123,
23,204,118,191, 91,181, 19,164,216,101,233,  3,135,169,246,152,
223, 60,143, 48,240, 34,220, 82,132, 36,146,106,227, 30, 95, 49,
83,166, 18,199, 98,155,122, 53,237,179, 57,190, 77,195,127,180,
230,108,215, 64,171,  5,206,161, 22, 94,251, 15,153, 45,243,  7,
72,136, 39,250,104,226, 75,112,198,126, 66,213,110,203, 89,160
};

unsigned char Table_HqDither_green[256] =
{ // 16*16 dither kernel for high quality dithering
184, 63,169, 99,204, 70,111,179, 62,231,101,206,132, 85,237,109,
125,226, 27,246, 42,163, 31,251,140, 21,174, 35,223, 43,143,  8,
200, 40,113,137,191, 86,198,124, 79,215,105,151, 93,192,168, 75,
90,149,182, 69, 11,238, 58,  4,167, 50,242, 12,253, 59, 24,232,
54,248, 16,220,157, 96,130,227, 88,186,126, 73,162,118,216,138,
175,102,205,117, 47,209,172, 37,202, 18,146,211, 32,194, 82,  7,
131, 38, 78,144,254, 25, 71,150,114,236, 64,107,228, 49,156,240,
197,110,187,  1,161,106,180,247, 92, 44,183,  2,127,177, 95, 28,
67,234, 56,218, 83,229, 52, 14,139,222, 81,160,249, 61,208,123,
152, 19,165,128, 30,135,195,116,171, 23,201,100, 34,141, 15,244,
46,224, 72,207, 98,243, 66,214, 57,255, 68,190,119,217,166, 89,
136,115,178,  9,189, 36,158,  6,103,148,129, 10,233, 41, 74,185,
230, 33, 94,252,142,122, 76,239,181, 29,219, 87,153,112,203,  5,
104,196,154, 60, 48,212,164, 45,108,199, 53,170, 26,250, 55,145,
241, 22, 84,221,173, 20, 91,225,134, 80,245,121,188, 97,176, 77,
51,210,133,  3,120,235,147, 13,193, 39,155,  0, 65,213, 17,159
};

unsigned char Table_HqDither_blue[256] =
{ // 16*16 dither kernel for high quality dithering
23,233,121,159, 89,149, 46, 82,157,122, 24,150, 52,226, 61,143,
170, 49,205, 32,215, 20,248,169, 37,232, 98,245,128, 33,182,102,
200,131, 93,176,109,183,132, 14,197, 66,190,  5,209, 79,238, 13,
69,250,  7, 71,229, 53, 96,237,116,145, 87,165, 44,141,120,160,
38,114,189,153, 29,139,191, 76, 31,224, 55,254,104,204, 28,223,
138,231, 60,208, 84,253,  2,162,211,123,179, 17,152, 67,174, 97,
78, 19,167,126,103, 47,203,108, 62, 10,134,218, 81,241,  1,213,
196,148,246, 12,220,173, 73,155,243,185,100, 50,194,110,156, 56,
119, 88, 43,112,144, 34,234, 22, 91, 36,249,140, 21,228, 40,181,
26,217,127,236, 59,201,135,117,193,124,166, 63,177, 74,133,251,
161, 51,186,  4,178, 94, 15,225, 48,214,  6,235, 95,206,  8, 86,
99,199, 68,151, 80,255,164, 70,147, 85,158,107, 30,146,221,171,
227, 16,242,115,210, 39,105,188, 27,202, 58,180,240,118, 35, 64,
106,154, 41,175, 25,142,239, 65,230,130,252, 42,136, 72,192,129,
45,212,137, 75,195,101,  0,172,113, 11, 92,168, 18,216,  3,247,
187, 83,  9,244, 57,222,125,207, 54,219,184, 77,198,111,163, 90
};


Hope these are helpfull for the one or the other..
Nils

0
101 May 16, 2007 at 14:46

Thanks all.
I’ve read a bit about dithering, and basicaly have seen three “types” of dithering : error diffusion, ordered, and floyd steinberg.

I know i use a kind of error diffusion but i’m not sure if use it correctly.
What i do for now is propagating the error while i’m drawing a scan line.

As i draw from left to right, i convert current pixel color from normalized rgb values to RGB332 format.
Then i calculate the difference between the normalized rgb values of the obtained color with the real normalized rgb values.
Finally i add these errors to the next pixel (the one on the right of the current pixel).

I’ve read that it’s better to also propagate the error in the vertical direction too (from top to bottom or bottom to top).
I’ll give that a try, maybe it will improve the quality a little bit.

Anyway, i’m not sure if it’s correct to do it like that.
Should i do it in a post process phase instead ?

Doing it in post process doen’t seem correct to me, because it will dither across polygon boundaries and will “wash” the edges of my polygons.
Doing it in the polygon filling phase ensures that i dither colors only for the pixels inside the polygon i’m drawing.

As i’m at it, i have another question that is probably stupid, but i have to ask.
If i switch to a N*N dither matrix, i will be forced to do it in a post process phase, right ?
Also, if i do it this way, can i use the same image as input and output ? or do i must have separate input and output images ?

Thanks a lots nils, be sure i’ll try your tables as soon as i know how to use them ;-)

Sol, i quickly tried the 64k lookup table thing, but the quality was quite poor. At least compared with an 8 bits true color format.
I hoped it would have worked better. I’ll make some more tests later because i still think i should have had better results.

Rubicon, you mean that i use the palette like this : palette[src][dest] = (src_color + dest_color / 2) ?
It gives me only one step for shading between two colors.. sounds very bad.. or did u mean something else ?

Anyway, thanks you all for your valuable help.

0
117 May 16, 2007 at 15:14

As far as I know, floyd-steinberg is a form of error diffusion.

re: bad results with optimized palette - sounds like your palette isn’t too optimal then =)

0
101 May 16, 2007 at 15:41

yeah, that’s what i think too.
i’m not sure how to create an optimal palette in fact.
what would be perfect would be to be able to favor some colors in the palette without loosing too much quality for the other colors.

what i did in my test was to create a palette with 32 shades going from black to the 7 other points of the color cube (red, green, blue, yellow, cyan, purple, and white).
that gave me 7 * 32 = 224 colors.

that way, i favor these 7 colors.

now, going from black to any of these colors was smooth, but going from yellow to cyan for exemple was bad.

i hoped error diffusion could have helped to keep the quality acceptable even when working with colors poorly represented in the palette.

i’ve had other ideas. like creating the palette with the edges of the color cube instead of the corner points for exemple.
12 edges -> 21 shades for each edge.

0
117 May 17, 2007 at 07:16

@EddyCharly

i’m not sure how to create an optimal palette in fact.

Like I mentioned before.. since you seem to be able to render truecolor images somehow, render a few “representative” frames, and feed all the colors from those frames to, for example, the median cut color reducer I mentioned above.

0
101 May 18, 2007 at 09:33

I found with Floyd Steinberg that you get better results alternating between left-to-right and right-to-left on alternate scanlines, rather than plain left-to-right top-to-bottom scanning.