Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!batcomputer!sun.soe.clarkson.edu!valdis
From: valdis@alchemy.mcs.clarkson.edu (& Kletnieks)
Newsgroups: comp.graphics
Subject: Re: QRT 1.5 problems? (long)
Message-ID: <VALDIS.89Apr5170542@alchemy.mcs.clarkson.edu>
Date: 5 Apr 89 21:05:42 GMT
References: <YYCDWDy00WB800z0ZX@andrew.cmu.edu>
Sender: news@sun.soe.clarkson.edu
Organization: Clarkson University, Postdam NY
Lines: 72
In-reply-to: nl0s+@andrew.cmu.edu's message of 4 Apr 89 17:17:03 GMT

After much jumping up and down, I finally found something that
*seems* to fix my problems with qrt 1.5.

Something to note here is that I was using 'qrt2gif' to dither the 24-bit
color down to black&white.  I suspect that people dithering down to 256
or even 16 colors probably would not notice this, as they would be
getting 1/16 or 1/256 the dither error on each pixel and not get bit
by this...

In the qrt2gif program, there is kept a pair of 'error arrays' (cerr and lerr).
Now, I must admit that I speak out of ignorance as to EXACTLY how the
Floyd-Steinberg code works, but it seemed "morally wrong" that the
arrays keep getting added into and never cleared.  What would happen is
it would descend down the image, totalling (for instance) all the errors
from a 'green' ball to the 'gray' it was outputting.  Then, having passed
over that area, it would hit (for instance) a yellow area, and try to
re-compensate for the totalled up errors.

The reason it seemed to act like 'blotter paper' was simply that it would
tend to exhibit this backlash when moving from one object to another (or
actually when moving from one color area to another).  The 'streamer'
effect was because once ONE pixel got warped, the i+1 and i+2 terms would
tend to propagate it left and right on suceeding raster lines.  Eventually,
the error would have been 'expended' and it would fade out at some  pixel,
and then the correct value would be propagated left and right.

The basic fix was to apply an exponential decay, so that it would tend to
'forget' the error values more than a few pixels away (It only looks one
or two pixels left or right, having memory of 300 pixels above sounds
fishy to me).

Now, having discussed this, here's how I fixed it:

Original code (near line 826 of qrt2gif.c):

 Bitmap_Plot( bit, i, j, idx );
                }


                if( floyd ) {
                        /* Swap error vectors */
                        terr = lerr; lerr = cerr; cerr = terr;
                }

                }
                if( feof( fp ) )

New code:

 Bitmap_Plot( bit, i, j, idx );
                }


                if( floyd ) {
                        int jello;
                        /* Swap error vectors */
                        for (jello=0;jello<xres+2;jello++) {
                                cerr[RD][jello] >>= 1;
                                cerr[GR][jello] >>= 1;
                                cerr[BL][jello] >>= 1;
                        }
                        terr = lerr; lerr = cerr; cerr = terr;
                }

                }
                if( feof( fp ) )


Hope this helps, feel free to flame me if I totally mis-understood what
was going on...

				Valdis Kletnieks