Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!pt.cs.cmu.edu!cadre.dsl.pitt.edu!pitt!hobbes!planting
From: planting@hobbes.cs.pittsburgh.edu (Dr. Harry Plantinga)
Newsgroups: comp.graphics
Subject: Re: help with quick color map search
Summary: Apple's approach
Message-ID: <6060@pitt.UUCP>
Date: 23 Oct 89 13:09:04 GMT
References: <67563@tut.cis.ohio-state.edu> <8126@microsoft.UUCP> <8134@microsoft.UUCP>
Sender: news@pitt.UUCP
Reply-To: planting@cs.pitt.edu
Organization: Computer Science Dept., Univ. of Pittsburgh
Lines: 19

In article <8134@microsoft.UUCP> kensy@microsoft.UUCP (Ken Sykes) writes:

>The real problem here is searching (I assume) 256 entries for each pixel.
>Paul Heckbert used a local search technique in his paper on color
>reduction to reduce the list size...
>
>If anyone knows of other methods that are faster or use less memory, please
>post!

I don't know if this is Paul Heckbert's technique, but in the
Macintosh toolbox Apple uses the following technique:

They construct an inverse color table based on the first 3-, 4-, or 5-
bits each of R, G, and B.  Thus, in order to find the best match for a
given color, you concatenate the first few bits of the R, G, and B
components and look up the best match in the inverse table.  If there
is more than one possibility, they are all stored and searched
sequentially.  This technique uses a table with 512, 4096, or 32768
entries.