CODING - DITHERING - dithering as it is.

<b>CODING</b> - DITHERING - dithering as it is.

AY-Track: "HAUZ ON THE SUN"
__________________________________________


(C) Max / Cyberax Software / BDA
__________________________________________



                DITHERING

                --------

 Dithering, as it is (AND HOW ITS NO :-)


 + - - - ----====<++>====---- - - - +

    Based on works by D. Rogers



   In Deja Vu # 06 DANIEL suggested calling
this method of graphics output 1 = 4 * 4. Familiar
pisishniki say that all this scientifically
called a word DITHERING. Because pisishniki never lied :-), 
consider the second option. 

   Do not just think that since we are
went on the withdrawal of graphics, so I am now
start scribbling all there procedures such as
"Output image 64 * 48 for 3 frame. No!
After FunTop'a this, in general, passed
stage (but only in general ...).

   It's about texture generation. Applications of these 
textures can think of quite a lot: die faces in 3D-grafix, 
converting images 4 - ... 256-color to black and white, 
grayscale printing, "increase" Spectrum number of colors (what 
was on FT'98), etc. 


             *



   Here I will consider getting
Texture size N * N pixels, where N = 2 ^ Z,
Z = 1, 2, 3 ... Principle of obtaining texture
other sizes, I do not know, but in the end
articles still cite a couple.
-----------------------------------------


   First, some background information,
necessary for the understanding of the article:

 1) For the matrix multiplication by a number, it is necessary
     all the elements necessary to multiply by

     this number.
 2) The sum of two matrices - a matrix whose elements

     which were obtained by adding the corresponding
     sponding elements of the first two matrices.

(Of course, all this is obvious, but ...)
-----------------------------------------


   Texture size N * N, we get
of the matrices of the same size. Each subsequent texture will 
be different from the previous extension of pixels. 

   It is obvious that starting with a blank texture and
at each step, including per-pixel (not yet
fill all of it), all we get (N ^ 2) +1
gradations of brightness (textures). Let's start with 2 * 2:



                                 0 2
The base matrix has the form: D2 =

                                 March 1



Now from the matrix will receive step by step
Texture sprites:

Step 1) Empty Sprite 2 * 2 pixels.

Step 2) Turn in the sprite pixel, which

       in the matrix of D2 corresponds to the number 0.

       (0,0 of a lion. Top. Angle)

Step 3) includes another pixel having

       the same coordinates in the sprite that

       number 1 in the matrix D2.
....


Shag5) Enable pixel number 3.



   Step number 5 corresponds to the maximum brightness of the 
texture (sprite is painted in full). 

   As a result, at each step we got in texture. Here are the 
five grades: 


              k 2

             ~ K 2


   Images derived textures 2 * 2,
look much better than the 4 * 4 - higher resolution (but less 
than "flowers "...). Example - deme Higher State (part of 
Credits'ami). 


   We turn to the texture 4 * 4. For them, the matrix looks 
like this: 



                0 8 2 10


               12 4 14 6

         D4 =

                3 11 1 9


               15 7 13 5



   The question arises: where does it come from?
It's very simple - it is obtained from the basic matrix 2 * 2 
as follows: 



            4 * D2 +0 * U2 4 * D2 +2 * U2

      D4 =

            4 * D2 +3 * U2 4 * D2 +1 * U2



                            January 1

        Here, the matrix U2 =

                            January 1



   Explained in more detail. Take the first
element of D4: 4 * D2 +0 * U2 or simply
4 * D2. Carrying out the calculations:



          0 2 4 * 0 4 * 2 0 8

     4 * =

          3 1 4 * 3 4 * 1 12 4



       matrix D2 Quarter

                            matrix D4


   Received four upper left element
matrix D4. Similarly, we obtain the remaining three quarters. 
Show for the upper-right (4 * D2 +2 * U2): 



    0 2 1 1 0 +2 8 +2 2 10
 4 * + 2 * =

    3 1 1 1 12 +2 4 +2 14 6



    D2 U2 right

                                  Top

                                 quarter

                                  m-particle D4


   Now from the D4 can obtain a set of textures 4 * 4. This is 
done just as well as in Case 2 * 2 (17 steps).


   Here is the result:


    Number in 4

     at 4

     at 4

     at 4

    at 4

      at 4

      at 4

      at 4

    $ In 4

    ) At 4

    . at 4

    3 in 4

    8 in 4

    = In 4


   I think you already understand the general pattern of 
obtaining texture dithering'a N * N. It is expressed by the 
recurrence relation: 



      4 * D (N / 2) +0 * U (N / 2) 4 * D (N / 2) +2 * U (N / 2)
D (N) =

      4 * D (N / 2) +3 * U (N / 2) 4 * D (N / 2) +1 * U (N / 2)



                 January 1 ... 1


                 January 1 ... 1

            U =

                 .........


                 January 1 ... 1



   This expression relates the matrix of order
N from the previous matrix N / 2. That is, for
obtain the matrix 8 * 8 will need to use previously obtained D4.

   Of coz, I can continue to scoff at
readers get the texture of a high order, but I myself have had 
enough writing is so boring article. Therefore

will gradually become round (in the sense already written half 
...). 


             *



   General comments:


   First, why this way?
In general, for the size N * N pixels exist
2 ^ (N * N) different sprites. But not
All of them are suitable for dithering. The most optimal 
configuration is not so a lot. Besides the fact that two 
adjacent (in brightness), texture differ by only one pixel, 
provides the minimum melteshenie points (for example, when a 
large the screen brightness smoothly changes by

change of texture).

   Second, you can easily turn all
texture at 90 degrees. From this personal
will not change.

   Third, in my opinion, juzat texture size more than 16 * 16 
has no special meaning. 

   And fourth, as already mentioned, for
size N * N is obtained by N * N +1 texture. If you're going to 
use them to output Images (plasma or something else), then you

must choose N * N pieces. Why? Yes
simply because the color of a point is activated N bits => 
likely be N ^ 2 different color codes. What is the texture of 
emissions - Your job ...



             *



   Now, about where you can texture prisobachit. Well it, this 
plasma ... Better explain how the picture Envelope! 


   Generally I know the four methods of converting
(Thanks to "Algorithmic foundations of ...").

   The essence of the first - downsampling
pictures of how the conservation of
colors.

   Example: suppose there is a 16-Colorno image, say 256 * 192 
pixels. Divide it into squares of 4 pixels, then

each of these cells averages the color of 16 of its member 
pixels. Obtain image (256 / 4) * (192 / 4) = 64 * 48, and all

even 16-color.

   Then everything is clear: we replace each pixel
texture with the appropriate number.

   The result - B / W 256 * 192.


   The second method is more interesting. Consider its
on the same picture.

   Take the first point of the image. Her kodot 0 to 15. 
Replace it with pixels from the texture with the same code 
(number), and from take the pixel texture coordinates:



        X = (A MOD 4) and Y = (B MOD 4)


 A and B - the coordinates of the reference point in color.

   Repeating such a focus for all points of 16-color images, we 
screen 256 * 192 b / w, without loss of resolution.


   You can not even get textures, and work directly with the 
matrix. That algorithm, deflated, as you can imagine, from the 
book: -----------------------------------------


; Xmin, Xmax, Ymin, Ymax - outside of the raster.
; N - size of the matrix (N * N - number of colors).
; Mod - a function that returns the remainder of the
; Integer division 1 of the argument
2 nd.

for Y = Ymin to Ymax
for X = Xmin to Xmax

    I = (X mod N)

    J = (Y mod N)
if I (X, Y)