Re: MMX speedup for Floyd Steinberg error diffusion

rep_movsd wrote:
> The thing is Floyd-Steinberg dithering works serially one pixel at a
> time... Each pixel processed affects the pixel to its right and the
> pixels on the next scanline.

Interesting algorithm, very serially dependent. :-(

How does it handle the corner/edge cases?

I.e. the last pixel on a scan line has no down-right neighbor, the first 
pixel has no down-left and the last scanline has nothing below at all!

> So the best I can hope for is to handle one pixels R, G and B byte
> values in one go.
> 
> Let me clarify with actual code ( highly unoptimal C++ , for clarities
> sake )

It seems to me like the getNearestPalColor() function could easily 
dominate the processing time here!

I guess a 3D space partition would be a good way to go, using an initial 
lookup table based on something like 3:3:3 bits to start in the proper 
subvolume, or simply use that table to point to lists of possible 
palColor candidates for each starting point.

(Due to truncation effects, several pal entries might belong to multiple 
lists, depending upon the value of the rounded/truncated RGB bits, but 
with a good set of palette colors, the number of values to test against 
should be (on average) pretty low.

Anyway, to speed up the dithering stage I would use MMX/SSE and work on 
multiple lines in parallel, keeping the intermediate results in 
registers until we're finished with them.

Terje

-- 
- <Terje.Mathisen@[EMAIL PROTECTED]
>
"almost all programming can be viewed as an exercise in caching"