gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Tom N. <to...@ar...>]

The problem you're referring to is commonly called quantization. Doing
a web search on that might glean some results.

The two main algorithms people often use are called 'Median Cut' and
'Octree Quantization'. Both of these are efficient, and produce good
results.

Get hold of a copy of Graphics Gems 1... this has a paper describing
how to implement Octree Quantization, and also (i think) source code,
though there may be some bugs in it.

Tom Nettleship

P.S. I turned this mail into plain text from the HTML you sent... please
don't
send HTML posts to mailing lists; people using some mail readers can't
decipher
them.

> From: Matthew Davies [mailto:MD...@ac...]
> 
> Hi,
> 
> Can any of you guys give me some hints on choosing a decent 256 colour
> palette so that I can get a nice > spread of colours.  I need it for a
simple
> 3d game so basically I need to cover common colours and shades thereof.  
>  
> Do any of you have experience in this area.  I've had it so easy with
24-bit graphics up until now!  :-)

RE: [Algorithms] 256 colour palette

[Matthew D. <MD...@ac...>]

Hi,

Sorry, I may have not been clear.

I don't need to convert a 24-bit image to 256 colours using quantisation.  I
need to have a consistent single palette which doesn't restrict me too much
to the colours I can have in my textures.  For example, DOOM used a 256
colour palette to display all its graphics.

One idea is to have 32 different colours and 8 shades of them.  I could
design my textures in those 32 colours and 32 of a darker shade.

But I just wondered if anyone had a generic palette that they knew worked
well.

Best regards,
Matt.

> -----Original Message-----
> From: Tom Nettleship [mailto:to...@ar...]
> Sent: Wednesday, August 30, 2000 10:47
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> The problem you're referring to is commonly called quantization. Doing
> a web search on that might glean some results.
> 
> The two main algorithms people often use are called 'Median Cut' and
> 'Octree Quantization'. Both of these are efficient, and produce good
> results.
> 
> Get hold of a copy of Graphics Gems 1... this has a paper describing
> how to implement Octree Quantization, and also (i think) source code,
> though there may be some bugs in it.
> 
> Tom Nettleship
> 
> P.S. I turned this mail into plain text from the HTML you 
> sent... please
> don't
> send HTML posts to mailing lists; people using some mail readers can't
> decipher
> them.
> 
> > From: Matthew Davies [mailto:MD...@ac...]
> > 
> > Hi,
> > 
> > Can any of you guys give me some hints on choosing a decent 
> 256 colour
> > palette so that I can get a nice > spread of colours.  I 
> need it for a
> simple
> > 3d game so basically I need to cover common colours and 
> shades thereof.  
> >  
> > Do any of you have experience in this area.  I've had it so 
> easy with
> 24-bit graphics up until now!  :-)
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] 256 colour palette

[Giovanni B. <ba...@pr...>]

I don't know if this works well or if there is a better way, I've no
experience here.

I'd think about drawing each texture normally, then putting all them
together in a big 24bit image and quantize them all in a single pass.
After that, when you have your final palette, you can manually retouch the
textures that suffered too much from the quantization, if needed.

---
Giovanni Bajo
Lead Programmer

Protonic Interactive
www.protonic.net

a brand of Prograph Research S.r.l.
www.prograph.it


> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of
> Matthew Davies
> Sent: Wednesday, August 30, 2000 12:12 PM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
>
>
> Hi,
>
> Sorry, I may have not been clear.
>
> I don't need to convert a 24-bit image to 256 colours using
> quantisation.  I
> need to have a consistent single palette which doesn't restrict
> me too much
> to the colours I can have in my textures.  For example, DOOM used a 256
> colour palette to display all its graphics.
>
> One idea is to have 32 different colours and 8 shades of them.  I could
> design my textures in those 32 colours and 32 of a darker shade.
>
> But I just wondered if anyone had a generic palette that they knew worked
> well.
>
> Best regards,
> Matt.
>
> > -----Original Message-----
> > From: Tom Nettleship [mailto:to...@ar...]
> > Sent: Wednesday, August 30, 2000 10:47
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > The problem you're referring to is commonly called quantization. Doing
> > a web search on that might glean some results.
> >
> > The two main algorithms people often use are called 'Median Cut' and
> > 'Octree Quantization'. Both of these are efficient, and produce good
> > results.
> >
> > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > how to implement Octree Quantization, and also (i think) source code,
> > though there may be some bugs in it.
> >
> > Tom Nettleship
> >
> > P.S. I turned this mail into plain text from the HTML you
> > sent... please
> > don't
> > send HTML posts to mailing lists; people using some mail readers can't
> > decipher
> > them.
> >
> > > From: Matthew Davies [mailto:MD...@ac...]
> > >
> > > Hi,
> > >
> > > Can any of you guys give me some hints on choosing a decent
> > 256 colour
> > > palette so that I can get a nice > spread of colours.  I
> > need it for a
> > simple
> > > 3d game so basically I need to cover common colours and
> > shades thereof.
> > >
> > > Do any of you have experience in this area.  I've had it so
> > easy with
> > 24-bit graphics up until now!  :-)
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>

Re: [Algorithms] 256 colour palette

[Kent Q. <ken...@co...>]

You can't get good looking colors AND a wide range of colors in 256
colors. You have to decide what tradeoffs you're willing to make.

The Quake 1 palette had, IIRC, about 16 shades each of brown, green, and
grey, and many fewer of other colors. That's partly why the game was so
effective -- they did "dark" very well.

I have to echo the thoughts of someone else in this thread -- if you
know in advance you need one palette for the whole game, build the
palette first and give it to your artists. They'll do a much better job
than if you try to cut 24-bit art down after the fact.

	Kent


Matthew Davies wrote:
> 
> Hi,
> 
> Sorry, I may have not been clear.
> 
> I don't need to convert a 24-bit image to 256 colours using quantisation.  I
> need to have a consistent single palette which doesn't restrict me too much
> to the colours I can have in my textures.  For example, DOOM used a 256
> colour palette to display all its graphics.
> 
> One idea is to have 32 different colours and 8 shades of them.  I could
> design my textures in those 32 colours and 32 of a darker shade.
> 
> But I just wondered if anyone had a generic palette that they knew worked
> well.
> 
> Best regards,
> Matt.
> 
> > -----Original Message-----
> > From: Tom Nettleship [mailto:to...@ar...]
> > Sent: Wednesday, August 30, 2000 10:47
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > The problem you're referring to is commonly called quantization. Doing
> > a web search on that might glean some results.
> >
> > The two main algorithms people often use are called 'Median Cut' and
> > 'Octree Quantization'. Both of these are efficient, and produce good
> > results.
> >
> > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > how to implement Octree Quantization, and also (i think) source code,
> > though there may be some bugs in it.
> >
> > Tom Nettleship
> >
> > P.S. I turned this mail into plain text from the HTML you
> > sent... please
> > don't
> > send HTML posts to mailing lists; people using some mail readers can't
> > decipher
> > them.
> >
> > > From: Matthew Davies [mailto:MD...@ac...]
> > >
> > > Hi,
> > >
> > > Can any of you guys give me some hints on choosing a decent
> > 256 colour
> > > palette so that I can get a nice > spread of colours.  I
> > need it for a
> > simple
> > > 3d game so basically I need to cover common colours and
> > shades thereof.
> > >
> > > Do any of you have experience in this area.  I've had it so
> > easy with
> > 24-bit graphics up until now!  :-)
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Architect               |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________

Re: [Algorithms] 256 colour palette

[Gil G. <gg...@ma...>]

> build the palette first and give it to your artists.

Our artists would kill us. Have the artists make the palette. Thankfully we
will never use palettes again....they just suck.

-Gil



> You can't get good looking colors AND a wide range of colors in 256
> colors. You have to decide what tradeoffs you're willing to make.
>
> The Quake 1 palette had, IIRC, about 16 shades each of brown, green, and
> grey, and many fewer of other colors. That's partly why the game was so
> effective -- they did "dark" very well.
>
> I have to echo the thoughts of someone else in this thread -- if you
> know in advance you need one palette for the whole game, build the
> palette first and give it to your artists. They'll do a much better job
> than if you try to cut 24-bit art down after the fact.
>
> Kent
>
>
> Matthew Davies wrote:
> >
> > Hi,
> >
> > Sorry, I may have not been clear.
> >
> > I don't need to convert a 24-bit image to 256 colours using
quantisation.  I
> > need to have a consistent single palette which doesn't restrict me too
much
> > to the colours I can have in my textures.  For example, DOOM used a 256
> > colour palette to display all its graphics.
> >
> > One idea is to have 32 different colours and 8 shades of them.  I could
> > design my textures in those 32 colours and 32 of a darker shade.
> >
> > But I just wondered if anyone had a generic palette that they knew
worked
> > well.
> >
> > Best regards,
> > Matt.
> >
> > > -----Original Message-----
> > > From: Tom Nettleship [mailto:to...@ar...]
> > > Sent: Wednesday, August 30, 2000 10:47
> > > To: 'gda...@li...'
> > > Subject: RE: [Algorithms] 256 colour palette
> > >
> > >
> > > The problem you're referring to is commonly called quantization. Doing
> > > a web search on that might glean some results.
> > >
> > > The two main algorithms people often use are called 'Median Cut' and
> > > 'Octree Quantization'. Both of these are efficient, and produce good
> > > results.
> > >
> > > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > > how to implement Octree Quantization, and also (i think) source code,
> > > though there may be some bugs in it.
> > >
> > > Tom Nettleship
> > >
> > > P.S. I turned this mail into plain text from the HTML you
> > > sent... please
> > > don't
> > > send HTML posts to mailing lists; people using some mail readers can't
> > > decipher
> > > them.
> > >
> > > > From: Matthew Davies [mailto:MD...@ac...]
> > > >
> > > > Hi,
> > > >
> > > > Can any of you guys give me some hints on choosing a decent
> > > 256 colour
> > > > palette so that I can get a nice > spread of colours.  I
> > > need it for a
> > > simple
> > > > 3d game so basically I need to cover common colours and
> > > shades thereof.
> > > >
> > > > Do any of you have experience in this area.  I've had it so
> > > easy with
> > > 24-bit graphics up until now!  :-)
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> --
> -----------------------------------------------------------------------
> Kent Quirk                   | CogniToy: Intelligent toys...
> Game Architect               |           for intelligent minds.
> ken...@co...      | http://www.cognitoy.com/
> _____________________________|_________________________________________
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Brian M. <bma...@ra...>]

	One trick if you are using a palette and generating shades in order to
light the graphics is to use human assistance. For Privateer 2 a piece of
code did an initial color match to try get the nearest color from the
palette for that color at that intensity. The results from this we're that
great though. What I did next was to save this shade table out as a bitmap.
This let you see what the ramps for each color. Then came the clever bit. I
got the texture artist, Phil, to touch up the shade table bitmap to produce
shades that were better to him. The results weren't the correct shades - but
the final output looked much better. Phil didn't mind doing the table
either - to him being able to see how his textures were mangled was great.
	All that matters with graphics is getting the effect you want.
-Brian.

Re: [Algorithms] 256 colour palette

[Kent Q. <ken...@co...>]

Gil Gribb wrote:
> 
> > build the palette first and give it to your artists.
> 
> Our artists would kill us. Have the artists make the palette. Thankfully we
> will never use palettes again....they just suck.

Good point...

But sometimes you may want to cooperate with them on it. For example, if
you're doing some sort of lighting effects or palette cycling, you may
want to (for examples) arrange the palette with certain colors in
certain locations, or make sure that you have 16 shades of grey.

However, it's always a good idea to tell the artists your technical
constraints, and then leave them as much freedom as possible.

	Kent

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Architect               |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________

RE: [Algorithms] 256 colour palette

[Sasha P. <sa...@pr...>]

Hi Matt,

One way to go is to use so-called "6-6-6" palette, which gives you 6 shades
of red, green and blue color. You basically divide 255 by 6, and ~42 is your
shade step. This means, colors in your palette are:

0, 0, 0
0, 0, 42
0, 0, 85 (I rounded up here)
...
0, 42, 0
0, 42, 42
0, 42, 85
...
255, 255, 255

6-6-6 palette takes 216 colors, this is good for Windows as you still have
room for standard Windows colors. If you don't care about this, you can use
6-7-6 palette, having 7 shades for green, this takes 252 colors.

Such palettes are good because when you need to find nearest palette index
for a given 24-bit RGB color, you don't search for the nearest color,
instead you calculate it using trivial math:
Rindex = R / (255 / 6);
Gindex = G / (255 / 6);
Bindex = B / (255 / 6);

And then something like (Rindex * 6 * 6) + Gindex * 6 + Bindex gives you the
palette index. I hope I didn't make any mistakes in math here, but anyway
you should get the idea! :)

Regards,

Sasha Prokhorov.
(sa...@pr.../ICQ 4772797)

-----Original Message-----
From: Matthew Davies [mailto:MD...@ac...]
Sent: Wednesday, August 30, 2000 10:40 AM
To: Algorithms List (E-mail)
Subject: [Algorithms] 256 colour palette


Hi,
 
Can any of you guys give me some hints on choosing a decent 256 colour
palette so that I can get a nice spread of colours.  I need it for a simple
3d game so basically I need to cover common colours and shades thereof.  
 
Do any of you have experience in this area.  I've had it so easy with 24-bit
graphics up until now!  :-)
 
Thanks in advance for any help that you might provide.
 
Cheers!
Matt Davies
Programmer
Acclaim Studios, Cheltenham
+44 (0) 1242 533682
ICQ: 78711743

RE: [Algorithms] 256 colour palette

[Jason B. <jba...@ig...>]

> I don't need to convert a 24-bit image to 256 colours using 
> quantisation.  I
> need to have a consistent single palette which doesn't 
> restrict me too much
> to the colours I can have in my textures.

This is the same thing isn't it - imagine all your 24bit art as one image;
find the best fit palette for that.

In the past I worked on a game that need to support 8,16 and 24bit;
all the art was designed at 24bit and then I batch calculated a fixed
8bit palette at the end and pre-converted 8bit versions of all the art.

Actually, I had an 8bit palette per game level.

This works well where you start with 24bit art;
but if your final game is 8bit only then, as you say, it might be better
to specify a fixed palette to prevent the artists getting carried away.

If you do need to calc a palette I can recommend a useful freeware DOS
graphic utility
called Display that will do the palette calculation for a number of
high-colour images. Has user selectable methods too - median, neural, oct
etc.

regards,
Jason Barstow

RE: [Algorithms] 256 colour palette

[Martin F. <mf...@ac...>]

Doom used 16 shades of 16 colours if I remember correctly. IMO this was a
good balance. You could see each shade but it was a payoff for the number of
colours. I'd be tempted to do some sort of dynamic palette changing. For
example given a PVS:

ROOM A can see ROOM B <> ROOM B can see ROOM A
ROOM B can see ROOM C <> ROOM C can see ROOM B

(Note ROOM A and C cannot see eachother and you cannot be stood in ROOM B
and see both ROOM A and ROOM C)

ROOM B referenced 208 pallete entries
ROOM A has a different remaining 48 pallete entires to ROOM C.

So while the number of colours you need to reference never exceeds 256 you
can have more colours than that on the map. You have to have low colour
'insulating' Rooms / corridors. It also means that agents / fx can only
reference the bottom 208 pallete entires. Makes building your maps a little
more tricky but might be worth it. 

What platform is this for?
Cheers,
Martin



-----Original Message-----
From: Matthew Davies [mailto:MD...@ac...]
Sent: 30 August 2000 03:12
To: 'gda...@li...'
Subject: RE: [Algorithms] 256 colour palette


Hi,

Sorry, I may have not been clear.

I don't need to convert a 24-bit image to 256 colours using quantisation.  I
need to have a consistent single palette which doesn't restrict me too much
to the colours I can have in my textures.  For example, DOOM used a 256
colour palette to display all its graphics.

One idea is to have 32 different colours and 8 shades of them.  I could
design my textures in those 32 colours and 32 of a darker shade.

But I just wondered if anyone had a generic palette that they knew worked
well.

Best regards,
Matt.

> -----Original Message-----
> From: Tom Nettleship [mailto:to...@ar...]
> Sent: Wednesday, August 30, 2000 10:47
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> The problem you're referring to is commonly called quantization. Doing
> a web search on that might glean some results.
> 
> The two main algorithms people often use are called 'Median Cut' and
> 'Octree Quantization'. Both of these are efficient, and produce good
> results.
> 
> Get hold of a copy of Graphics Gems 1... this has a paper describing
> how to implement Octree Quantization, and also (i think) source code,
> though there may be some bugs in it.
> 
> Tom Nettleship
> 
> P.S. I turned this mail into plain text from the HTML you 
> sent... please
> don't
> send HTML posts to mailing lists; people using some mail readers can't
> decipher
> them.
> 
> > From: Matthew Davies [mailto:MD...@ac...]
> > 
> > Hi,
> > 
> > Can any of you guys give me some hints on choosing a decent 
> 256 colour
> > palette so that I can get a nice > spread of colours.  I 
> need it for a
> simple
> > 3d game so basically I need to cover common colours and 
> shades thereof.  
> >  
> > Do any of you have experience in this area.  I've had it so 
> easy with
> 24-bit graphics up until now!  :-)
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] 256 colour palette

[Lionel F. <li...@mi...>]

Another thing, you can give more importance to Red and Green components,
since the human eye see R & G better than Blue.

LiF.

RE: [Algorithms] 256 colour palette

[Tom N. <to...@ar...>]

> From: Jason Barstow [mailto:jba...@ig...]
> This works well where you start with 24bit art;
> but if your final game is 8bit only then, as you say, it 
> might be better
> to specify a fixed palette to prevent the artists getting 
> carried away.

I would add that it is also a good idea to provide the artists with
a palette up-front, as they can produce FAR better results using
that palette than you ever will quantising 24bit art after-the-fact.
(It is amazing what a talented old-skool texture artist can do with
very few colours.)

Another issue... if you decide to go for a regular palette, make sure
you use equal numbers of bits for each gun (such as the 666 scheme
mentioned in another post). Its tempting to use the extra palette entries
to slightly improve resolution on one axis (e.g. 676) but this means you
don't get a 'pure' greyscale ramp... you get a bunch of almost-greys
instead, and this can look very ugly, especially when lighting gets factored
in ontop of the base textures.

TomN

Re: [Algorithms] 256 colour palette

[Martin G. <bz...@wi...>]

NeuQuant works in two passes (as every image quantizer). First it generates
the target palette (this is what you need) and then it quantizes the image
with it. The palettes NeuQuant produces are far, far better than Median Cut or
Octree's best results. The algorithm itself is not at all slow, Ivan :), and
with a proper implementation it can match the standard schemes. I've tried it
myself.

Martin

-----Original Message-----
From: Ivan-Assen Ivanov <as...@ha...>
To: gda...@li...
<gda...@li...>
Date: 30 Àâãóñò 2000 ã. 13:05
Subject: Re: [Algorithms] 256 colour palette


>Try Neuquant - a simple Kohonen NN based method.
>http://www.ozemail.com.au/~dekker/NEUQUANT.HTML
>there you will find sources (ANSI C, yuck), the paper itself is not available
on the
>Web, but the source is pretty straightforward and easy to rewrite in a
simpler
>manner. A bit slow, but perfectly passable for offline use. Produces much,
much
>better results than the other two methods I tried - Heckbert quantization and
>a simple elimination of the closest colors.
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] 256 colour palette

[Matthew D. <MD...@ac...>]

Doing a ray-casting engine for the Gameboy Advance in my spare time.  I'm
using its 256 colour bitmap mode.

Matt.


> -----Original Message-----
> From: Martin Fuller [mailto:mf...@ac...]
> Sent: Wednesday, August 30, 2000 11:50
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> Doom used 16 shades of 16 colours if I remember correctly. 
> IMO this was a
> good balance. You could see each shade but it was a payoff 
> for the number of
> colours. I'd be tempted to do some sort of dynamic palette 
> changing. For
> example given a PVS:
> 
> ROOM A can see ROOM B <> ROOM B can see ROOM A
> ROOM B can see ROOM C <> ROOM C can see ROOM B
> 
> (Note ROOM A and C cannot see eachother and you cannot be 
> stood in ROOM B
> and see both ROOM A and ROOM C)
> 
> ROOM B referenced 208 pallete entries
> ROOM A has a different remaining 48 pallete entires to ROOM C.
> 
> So while the number of colours you need to reference never 
> exceeds 256 you
> can have more colours than that on the map. You have to have 
> low colour
> 'insulating' Rooms / corridors. It also means that agents / 
> fx can only
> reference the bottom 208 pallete entires. Makes building your 
> maps a little
> more tricky but might be worth it. 
> 
> What platform is this for?
> Cheers,
> Martin
> 
> 
> 
> -----Original Message-----
> From: Matthew Davies [mailto:MD...@ac...]
> Sent: 30 August 2000 03:12
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> Hi,
> 
> Sorry, I may have not been clear.
> 
> I don't need to convert a 24-bit image to 256 colours using 
> quantisation.  I
> need to have a consistent single palette which doesn't 
> restrict me too much
> to the colours I can have in my textures.  For example, DOOM 
> used a 256
> colour palette to display all its graphics.
> 
> One idea is to have 32 different colours and 8 shades of 
> them.  I could
> design my textures in those 32 colours and 32 of a darker shade.
> 
> But I just wondered if anyone had a generic palette that they 
> knew worked
> well.
> 
> Best regards,
> Matt.
> 
> > -----Original Message-----
> > From: Tom Nettleship [mailto:to...@ar...]
> > Sent: Wednesday, August 30, 2000 10:47
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> > 
> > 
> > The problem you're referring to is commonly called 
> quantization. Doing
> > a web search on that might glean some results.
> > 
> > The two main algorithms people often use are called 'Median Cut' and
> > 'Octree Quantization'. Both of these are efficient, and produce good
> > results.
> > 
> > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > how to implement Octree Quantization, and also (i think) 
> source code,
> > though there may be some bugs in it.
> > 
> > Tom Nettleship
> > 
> > P.S. I turned this mail into plain text from the HTML you 
> > sent... please
> > don't
> > send HTML posts to mailing lists; people using some mail 
> readers can't
> > decipher
> > them.
> > 
> > > From: Matthew Davies [mailto:MD...@ac...]
> > > 
> > > Hi,
> > > 
> > > Can any of you guys give me some hints on choosing a decent 
> > 256 colour
> > > palette so that I can get a nice > spread of colours.  I 
> > need it for a
> > simple
> > > 3d game so basically I need to cover common colours and 
> > shades thereof.  
> > >  
> > > Do any of you have experience in this area.  I've had it so 
> > easy with
> > 24-bit graphics up until now!  :-)
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] 256 colour palette

[Jason Z. <zi...@n-...>]

Very cool.  :)  What we did for a previous game was let the artists make all
the artwork in 24bit then use Debabilizer to create a 64-shade
"superpalette" and map them all to it.  It worked out nicely because this
game had very little artwork overall (probably not even 100 textures, and
most were similiar in color because of the theme).  The rest of the palette
entries were just shades of those 64.  Things that were not going to be
shaded could use the full palette for quantization.  And seperate levels
could use entirely different palettes and we'd swap them in.

Obviously using less base colors gets you more shades but we found 4 shades
of each color to be enough for our purposes.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Matthew Davies" <MD...@ac...>
To: <gda...@li...>
Sent: Wednesday, August 30, 2000 7:28 AM
Subject: RE: [Algorithms] 256 colour palette


> Doing a ray-casting engine for the Gameboy Advance in my spare time.  I'm
> using its 256 colour bitmap mode.
>
> Matt.
>
>
> > -----Original Message-----
> > From: Martin Fuller [mailto:mf...@ac...]
> > Sent: Wednesday, August 30, 2000 11:50
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > Doom used 16 shades of 16 colours if I remember correctly.
> > IMO this was a
> > good balance. You could see each shade but it was a payoff
> > for the number of
> > colours. I'd be tempted to do some sort of dynamic palette
> > changing. For
> > example given a PVS:
> >
> > ROOM A can see ROOM B <> ROOM B can see ROOM A
> > ROOM B can see ROOM C <> ROOM C can see ROOM B
> >
> > (Note ROOM A and C cannot see eachother and you cannot be
> > stood in ROOM B
> > and see both ROOM A and ROOM C)
> >
> > ROOM B referenced 208 pallete entries
> > ROOM A has a different remaining 48 pallete entires to ROOM C.
> >
> > So while the number of colours you need to reference never
> > exceeds 256 you
> > can have more colours than that on the map. You have to have
> > low colour
> > 'insulating' Rooms / corridors. It also means that agents /
> > fx can only
> > reference the bottom 208 pallete entires. Makes building your
> > maps a little
> > more tricky but might be worth it.
> >
> > What platform is this for?
> > Cheers,
> > Martin
> >
> >
> >
> > -----Original Message-----
> > From: Matthew Davies [mailto:MD...@ac...]
> > Sent: 30 August 2000 03:12
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > Hi,
> >
> > Sorry, I may have not been clear.
> >
> > I don't need to convert a 24-bit image to 256 colours using
> > quantisation.  I
> > need to have a consistent single palette which doesn't
> > restrict me too much
> > to the colours I can have in my textures.  For example, DOOM
> > used a 256
> > colour palette to display all its graphics.
> >
> > One idea is to have 32 different colours and 8 shades of
> > them.  I could
> > design my textures in those 32 colours and 32 of a darker shade.
> >
> > But I just wondered if anyone had a generic palette that they
> > knew worked
> > well.
> >
> > Best regards,
> > Matt.
> >
> > > -----Original Message-----
> > > From: Tom Nettleship [mailto:to...@ar...]
> > > Sent: Wednesday, August 30, 2000 10:47
> > > To: 'gda...@li...'
> > > Subject: RE: [Algorithms] 256 colour palette
> > >
> > >
> > > The problem you're referring to is commonly called
> > quantization. Doing
> > > a web search on that might glean some results.
> > >
> > > The two main algorithms people often use are called 'Median Cut' and
> > > 'Octree Quantization'. Both of these are efficient, and produce good
> > > results.
> > >
> > > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > > how to implement Octree Quantization, and also (i think)
> > source code,
> > > though there may be some bugs in it.
> > >
> > > Tom Nettleship
> > >
> > > P.S. I turned this mail into plain text from the HTML you
> > > sent... please
> > > don't
> > > send HTML posts to mailing lists; people using some mail
> > readers can't
> > > decipher
> > > them.
> > >
> > > > From: Matthew Davies [mailto:MD...@ac...]
> > > >
> > > > Hi,
> > > >
> > > > Can any of you guys give me some hints on choosing a decent
> > > 256 colour
> > > > palette so that I can get a nice > spread of colours.  I
> > > need it for a
> > > simple
> > > > 3d game so basically I need to cover common colours and
> > > shades thereof.
> > > >
> > > > Do any of you have experience in this area.  I've had it so
> > > easy with
> > > 24-bit graphics up until now!  :-)
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Sasha P. <sa...@pr...>]

Hi everybody,

I thought maybe somebody can clarify the terms "quantization" and
"dithering", I often see them used as synonyms, while I always understood
them as quite different things. I want to know what other people think...

For me, quantization is just a replacement of one color (N-bit, e.g. 16 or
24-bit) with another color, from a smaller set (e.g. from 256 colors).
Dithering is a much more complex process, which, in addition to replacing a
pixel with nearest color, also performs _modifications_ of nearby pixels, to
give you smooth image.

For example, if you take the same 6-6-6 palette and do a quantization and,
say, error diffusion dithering, you will get different images, in first
image you will see the bad results of decreased number of colors, while the
dithered image will look much, much better.

Comments on these two terms, anyone?

Sasha.

> -----Original Message-----
> From: Tom Nettleship [mailto:to...@ar...]
> Sent: Wednesday, August 30, 2000 11:47 AM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> The problem you're referring to is commonly called quantization. Doing
> a web search on that might glean some results.
> 
> The two main algorithms people often use are called 'Median Cut' and
> 'Octree Quantization'. Both of these are efficient, and produce good
> results.
> 
> Get hold of a copy of Graphics Gems 1... this has a paper describing
> how to implement Octree Quantization, and also (i think) source code,
> though there may be some bugs in it.
> 
> Tom Nettleship
> 
> P.S. I turned this mail into plain text from the HTML you 
> sent... please
> don't
> send HTML posts to mailing lists; people using some mail readers can't
> decipher
> them.
> 
> > From: Matthew Davies [mailto:MD...@ac...]
> > 
> > Hi,
> > 
> > Can any of you guys give me some hints on choosing a decent 
> 256 colour
> > palette so that I can get a nice > spread of colours.  I 
> need it for a
> simple
> > 3d game so basically I need to cover common colours and 
> shades thereof.  
> >  
> > Do any of you have experience in this area.  I've had it so 
> easy with
> 24-bit graphics up until now!  :-)
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] 256 colour palette

[Akbar A. <sye...@ea...>]

>Can any of you guys give me some hints on choosing a decent 256 colour
palette so that I >can get a nice spread of colours.  I need it for a simple
3d game so basically I need to >over common colours and shades thereof.


what's up with the fancy html e-mail ;)
someone body from ensemble studios wrote about there problems and how they
got around the color restriction they had.
check there web site. there's a ppt up.
also gdmag had an article written by an ensemble guy as well.

i'm not sure how a 3d pallete/game versus a 2d pallete/game is going to work
out. imho your going to more worreid about getting your shading right
instead of showing the "vibrance" of the few colors you have ;)


peace.
akbar A.


isn't it ironic, in the paper "A Characterization of Ten Hidden-Surface
Algorithms", by sutherland, sproull and schumacker that we use the eleventh
algorithm ;)
makes you really think

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Brian
Marshall
Sent: Wednesday, August 30, 2000 4:36 AM
To: gda...@li...
Subject: RE: [Algorithms] 256 colour palette


    This is going to depend on how you are going to use the colors - match
offline, or generate shading etc at runtime.
For runtime you should find examples in the Windows OpenGL code (in the
Visual C++ docs) for producing a palette for effectively 3/3/2 color depth
from a palette. This does leave a few free entries (normally used for
Windows) that you can use for huds etc. The results are pretty horrible
though....
    If you can generate a big 24 bit image containing the colors you know
you are going to need then I'd suggest doing that and generating a palette
from that to use. (I'd recommend Wu's version from Graphics Gems. Much
better IMHO than Octree etc.)
    Could be worse - I still have memories from color clash on the
Spectrum... getting to 16 colors in bitplanes on the Atari ST was heaven :-)

-Brian.
-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Matthew
Davies
Sent: Wednesday, August 30, 2000 9:40 AM
To: Algorithms List (E-mail)
Subject: [Algorithms] 256 colour palette


Hi,

Can any of you guys give me some hints on choosing a decent 256 colour
palette so that I can get a nice spread of colours.  I need it for a simple
3d game so basically I need to cover common colours and shades thereof.

Do any of you have experience in this area.  I've had it so easy with 24-bit
graphics up until now!  :-)

Thanks in advance for any help that you might provide.

Cheers!
Matt Davies
Programmer
Acclaim Studios, Cheltenham
+44 (0) 1242 533682
ICQ: 78711743

RE: [Algorithms] 256 colour palette

[Akbar A. <sye...@ea...>]

>since the human eye see R & G better than Blue.
more at green


peace.
akbar A.


isn't it ironic, in the paper "A Characterization of Ten Hidden-Surface
Algorithms", by sutherland, sproull and schumacker that we use the eleventh
algorithm ;)
makes you really think


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Lionel Fumery
Sent: Wednesday, August 30, 2000 6:37 AM
To: gda...@li...
Subject: Re: [Algorithms] 256 colour palette


Another thing, you can give more importance to Red and Green components,
since the human eye see R & G better than Blue.

LiF.


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Akbar A. <sye...@ea...>]

>And seperate levels
>could use entirely different palettes and we'd swap them in.
that's one thing i hate about consoles :|
you are stuck to *themes*
i'm sure all to many of you have run into these problems.



peace.
akbar A.


isn't it ironic, in the paper "A Characterization of Ten Hidden-Surface
Algorithms", by sutherland, sproull and schumacker that we use the eleventh
algorithm ;)
makes you really think


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Jason
Zisk
Sent: Wednesday, August 30, 2000 9:45 AM
To: gda...@li...
Subject: Re: [Algorithms] 256 colour palette


Very cool.  :)  What we did for a previous game was let the artists make all
the artwork in 24bit then use Debabilizer to create a 64-shade
"superpalette" and map them all to it.  It worked out nicely because this
game had very little artwork overall (probably not even 100 textures, and
most were similiar in color because of the theme).  The rest of the palette
entries were just shades of those 64.  Things that were not going to be
shaded could use the full palette for quantization.  And seperate levels
could use entirely different palettes and we'd swap them in.

Obviously using less base colors gets you more shades but we found 4 shades
of each color to be enough for our purposes.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Matthew Davies" <MD...@ac...>
To: <gda...@li...>
Sent: Wednesday, August 30, 2000 7:28 AM
Subject: RE: [Algorithms] 256 colour palette


> Doing a ray-casting engine for the Gameboy Advance in my spare time.  I'm
> using its 256 colour bitmap mode.
>
> Matt.
>
>
> > -----Original Message-----
> > From: Martin Fuller [mailto:mf...@ac...]
> > Sent: Wednesday, August 30, 2000 11:50
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > Doom used 16 shades of 16 colours if I remember correctly.
> > IMO this was a
> > good balance. You could see each shade but it was a payoff
> > for the number of
> > colours. I'd be tempted to do some sort of dynamic palette
> > changing. For
> > example given a PVS:
> >
> > ROOM A can see ROOM B <> ROOM B can see ROOM A
> > ROOM B can see ROOM C <> ROOM C can see ROOM B
> >
> > (Note ROOM A and C cannot see eachother and you cannot be
> > stood in ROOM B
> > and see both ROOM A and ROOM C)
> >
> > ROOM B referenced 208 pallete entries
> > ROOM A has a different remaining 48 pallete entires to ROOM C.
> >
> > So while the number of colours you need to reference never
> > exceeds 256 you
> > can have more colours than that on the map. You have to have
> > low colour
> > 'insulating' Rooms / corridors. It also means that agents /
> > fx can only
> > reference the bottom 208 pallete entires. Makes building your
> > maps a little
> > more tricky but might be worth it.
> >
> > What platform is this for?
> > Cheers,
> > Martin
> >
> >
> >
> > -----Original Message-----
> > From: Matthew Davies [mailto:MD...@ac...]
> > Sent: 30 August 2000 03:12
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] 256 colour palette
> >
> >
> > Hi,
> >
> > Sorry, I may have not been clear.
> >
> > I don't need to convert a 24-bit image to 256 colours using
> > quantisation.  I
> > need to have a consistent single palette which doesn't
> > restrict me too much
> > to the colours I can have in my textures.  For example, DOOM
> > used a 256
> > colour palette to display all its graphics.
> >
> > One idea is to have 32 different colours and 8 shades of
> > them.  I could
> > design my textures in those 32 colours and 32 of a darker shade.
> >
> > But I just wondered if anyone had a generic palette that they
> > knew worked
> > well.
> >
> > Best regards,
> > Matt.
> >
> > > -----Original Message-----
> > > From: Tom Nettleship [mailto:to...@ar...]
> > > Sent: Wednesday, August 30, 2000 10:47
> > > To: 'gda...@li...'
> > > Subject: RE: [Algorithms] 256 colour palette
> > >
> > >
> > > The problem you're referring to is commonly called
> > quantization. Doing
> > > a web search on that might glean some results.
> > >
> > > The two main algorithms people often use are called 'Median Cut' and
> > > 'Octree Quantization'. Both of these are efficient, and produce good
> > > results.
> > >
> > > Get hold of a copy of Graphics Gems 1... this has a paper describing
> > > how to implement Octree Quantization, and also (i think)
> > source code,
> > > though there may be some bugs in it.
> > >
> > > Tom Nettleship
> > >
> > > P.S. I turned this mail into plain text from the HTML you
> > > sent... please
> > > don't
> > > send HTML posts to mailing lists; people using some mail
> > readers can't
> > > decipher
> > > them.
> > >
> > > > From: Matthew Davies [mailto:MD...@ac...]
> > > >
> > > > Hi,
> > > >
> > > > Can any of you guys give me some hints on choosing a decent
> > > 256 colour
> > > > palette so that I can get a nice > spread of colours.  I
> > > need it for a
> > > simple
> > > > 3d game so basically I need to cover common colours and
> > > shades thereof.
> > > >
> > > > Do any of you have experience in this area.  I've had it so
> > > easy with
> > > 24-bit graphics up until now!  :-)
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Tom N. <to...@ar...>]

> From: Akbar A. [mailto:sye...@ea...]
> 
> >since the human eye see R & G better than Blue.
> more at green

True. But, as I stated earlier, this can be a bad thing (tm) as
you don't get a pure grey ramp... just lots of icky slightly
off greys in your palette, so its worth avoiding.

TomN

RE: [Algorithms] 256 colour palette

[Stephen J B. <sj...@li...>]

On Wed, 30 Aug 2000, Tom Nettleship wrote:

> > From: Akbar A. [mailto:sye...@ea...]
> > 
> > >since the human eye see R & G better than Blue.
> > more at green
> 
> True. But, as I stated earlier, this can be a bad thing (tm) as
> you don't get a pure grey ramp... just lots of icky slightly
> off greys in your palette, so its worth avoiding.

Suppose you have one extra bit of Green - compared to
Red and Blue....you just have to set up the colour
lookup table such that even numbered green inputs
have the same output as the corresponding R and B
entries.

Hence, R=8, G=16, B=8 would be an exact grey, but
       R=8, G=15, B=8 would be a purplish grey and
       R=8, G=17, B=8 would be a greenish grey.

Then, so long as your greys have identical numbers for
Red and Blue and even numbered Greens, you'll get perfect
greys with the in between green values used for non-grey-scale
colours.

The (slight) lossage here is that you can't quite get
maximum brightness Red or Blue entries.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] 256 colour palette

[Gil G. <gg...@ma...>]

This isn't right steve. RGB(8,16,8) = (8/31,16/63,8/31) in 565. Oddly, the
divisor is not a power of two, because 31, not 32 is the maximum value that
can be stored in 5 bits.
-Gil

> > True. But, as I stated earlier, this can be a bad thing (tm) as
> > you don't get a pure grey ramp... just lots of icky slightly
> > off greys in your palette, so its worth avoiding.
>
> Suppose you have one extra bit of Green - compared to
> Red and Blue....you just have to set up the colour
> lookup table such that even numbered green inputs
> have the same output as the corresponding R and B
> entries.
>
> Hence, R=8, G=16, B=8 would be an exact grey, but
>        R=8, G=15, B=8 would be a purplish grey and
>        R=8, G=17, B=8 would be a greenish grey.
>
> Then, so long as your greys have identical numbers for
> Red and Blue and even numbered Greens, you'll get perfect
> greys with the in between green values used for non-grey-scale
> colours.
>
> The (slight) lossage here is that you can't quite get
> maximum brightness Red or Blue entries.
>
> Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sj...@li...           http://www.link.com
> Home: sjb...@ai...       http://web2.airmail.net/sjbaker1
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] 256 colour palette

[Stephen J B. <sj...@li...>]

On Wed, 30 Aug 2000, Gil Gribb wrote:

> This isn't right steve. RGB(8,16,8) = (8/31,16/63,8/31) in 565. Oddly, the
> divisor is not a power of two, because 31, not 32 is the maximum value that
> can be stored in 5 bits.

Yes - but if you can set up your own palette, you can still arrange
that the even numbered values for G have the same brightnesses as
the equivelent R's and B's.  Admittedly, this will mean that
"White" will be 1/31 == ~3% dimmer than you might expect...but
that's a small price to pay for nice greys.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1