Deja Vu #07 31 декабря 1997

Программирование

CODING - DITHERING - дизеринг как он есть.

AY-Track:  "HAUZ ON THE SUN"              
__________________________________________


(C) Max/Cyberax Software/BDA
__________________________________________


                DITHERING
                ---------


 ДИЗЕРИНГ, КАК ОН ЕСТЬ (И КАК ЕГО НЕТ :-)


 +-   -  - ----====<++>====---- -  -   -+
    По мотивам произведений Д.Роджерса


   В Deja Vu #06 DANIEL предложил называть
такой метод вывода графики 1=4*4. Знакомые
писишники говорят, что по научному все это
называется словом DITHERING. Т.к. писишни-
ки никогда не врут:-), остановимся на вто-
ром варианте.
   Не подумайте только, что  раз  уж  речь
зашла о выводе  графики, значит  я  сейчас
начну  строчить  всякие там процедуры типа
"вывод картинки 64*48 за  3  фрейма". Нет!
После FunTop'a это, в общем-то, пройденный
этап (но это только в общем...).
   Речь пойдет о генерации текстур. Приме-
нений этих текстур можно придумать доволь-
но много: заливка граней в 3D-grafix, кон-
вертация картинок 4- ...  256-color в чер-
но-белые, полутоновая печать, "увеличение"
количества цветов Спектрума (то, что и бы-
ло на FT'98) и т.п.

             *      *      *


   Здесь я  буду  рассматривать  получение
текстур размером N*N пикселов, где  N=2^Z,
Z=1, 2, 3 ... Принципа  получения  текстур
других  размеров  я  не  знаю, но  в конце
статьи все же приведу парочку.
------------------------------------------


   Для начала  немного базовой информации,
необходимой для понимания статьи:

 1)  Для умножения матрицы на число, необ-
     ходимо все ее  элементы  умножить  на
     это число.
 2)  Сумма двух матриц - матрица, элементы
     которой получены сложением соответст-
     вующих элементов первых двух матриц.

(Конечно, все это очевидно, но...)
------------------------------------------


   Текстуры размером N*N мы будем получать
из матриц таких же размеров. Каждая после-
дующая текстура будет отличаться от преды-
дущей добавочным включенным пикселом.
   Очевидно, что начав с пустой текстуры и
на каждом шаге включая по пикселу (пока не
заполним ее всю), мы всего получим (N^2)+1
градаций яркости (текстур). Начнем с 2*2:

                                ┌    ┐
                                │0  2│
Базовая матрица имеет вид: D2 = │    │
                                │3  1│
                                └    ┘


Теперь из матрицы  будем пошагово получать
спрайты текстур:

Шаг1)  Пустой спрайт 2*2 пиксела.

Шаг2)  Включаем в спрайте пиксел, которому
       в матрице D2 соответствует число 0.
       (координаты 0,0 от лев. верх. угла)

Шаг3)  Включаем  еще один пиксел,  имеющий
       те же координаты в спрайте,  что  и
       число 1 в матрице D2.
....


Шаг5)  Включаем пиксел с номером 3.


   Шагу номер 5 соответствует текстура ма-
ксимальной  яркости (спрайт  закрашен пол-
ностью).
   В результате, на каждом шаге мы получи-
ли по текстуре. Вот все пять градаций:

            └k      2
            ~└k      2

   Картинки,  выведенные  текстурами  2*2,
смотрятся гораздо лучше,чем 4*4 - выше ра-
зрешение (но меньше "цветов"...). Пример -
дема  Higher State (часть с Credits'ами).

   Перейдем к текстурам 4*4. Для  них мат-
рица выглядит так:

              ┌            ┐
              │ 0  8  2 10 │
              │            │
              │12  4 14  6 │
         D4 = │            │
              │ 3 11  1  9 │
              │            │
              │15  7 13  5 │
              └            ┘


   Возникает вопрос: откуда  она  взялась?
Все очень просто - она получилась из базо-
вой матрицы 2*2 по следующей формуле:

           ┌                    ┐
           │4*D2+0*U2 4*D2+2*U2 │
      D4 = │                    │
           │4*D2+3*U2 4*D2+1*U2 │
           └                    ┘
                           ┌   ┐
                           │1 1│
        Здесь матрица U2 = │   │
                           │1 1│
                           └   ┘


   Поясняю  более  подробно. Берем  первый
элемент матрицы D4: 4*D2+0*U2  или  просто
4*D2. Проводим вычисления:

         ┌   ┐   ┌       ┐   ┌     ┐
         │0 2│   │4*0 4*2│   │ 0  8│
     4 * │   │ = │       │ = │     │
         │3 1│   │4*3 4*1│   │12  4│
         └   ┘   └       ┘   └     ┘
        └─────┘             └───────┘
       матрица D2            четверть
                            матрицы D4

   Получили четыре левых верхних  элемента
матрицы D4. Аналогично  получаются осталь-
ные три четверти. Покажу  для правой верх-
ней (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                  правая
                                  верхняя
                                 четверть
                                  м-цы D4

   Теперь из D4 можно получить набор текс-
тур 4*4. Делается это точно также, как и в
случае 2*2 (всего 17 шагов).
   Привожу результат:

   №└у     4
   ┬у     4
   ├у     4
   ─у     4
   у     4
   ╞у     4
   ╟у     4
   ╚у     4
   $╔у     4
   )╩у     4
   .╦у     4
   3╠у     4
   8═у     4
   =╬у     4

   Думаю, вы уже  поняли общую  закономер-
ность получения  текстур  dithering'а N*N.
Она выражается рекуррентным соотношением:

     ┌                                   ┐
     │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)│
     └                                   ┘


                ┌         ┐
                │1 1 ... 1│
                │         │
                │1 1 ... 1│
            U = │         │
                │.........│
                │         │
                │1 1 ... 1│
                └         ┘


   Это выражение связывает матрицу порядка
N с предыдущей матрицей N/2. То  есть, для
получения матрицы 8*8 необходимо будет ис-
пользовать полученную ранее D4.
   Of coz, я  могу и дальше издеваться над
читателями, получая  текстуры  более высо-
ких порядков, но  меня самого уже  достало
написание настолько нудной  статьи. Посему
буду постепенно закругляться (в смысле по-
ловину уже написал...).

             *      *      *


   Общие замечания:

   Во-первых, почему именно такой  способ?
Вообще для размера N*N пикселов существует
2^(N*N) различных спрайтов. Но  далеко  не
все из них подходят для  дизеринга. Наибо-
лее  оптимальных  конфигураций не так уж и
много. К  тому же тот факт, что две сосед-
ние (по яркости) текстуры отличаются всего
одним  пикселом, обеспечивает  минимальное
мельтешение точек (например, когда большая
часть  экрана плавно  меняет яркость путем
смены текстур).
   Во-вторых, можно запросто повернуть все
текстуры на 90  градусов. От  этого ничего
не изменится.
   В-третьих, на мой взгляд, юзать тексту-
ры размером больше чем 16*16 не имеет осо-
бого смысла.
   И в-четвертых, как  уже говорилось, для
размера N*N получается N*N+1 текстура. Ес-
ли Вы собираетесь применять их для  вывода
картинок (плазмы или чего-то еще), то  Вам
необходимо  выбрать  N*N  штук. Почему? Да
просто потому, что под цвет точки задейст-
вуется N бит  => всего будет N^2 различных
кодов  цвета. Какую  текстуру  выбросить -
Ваше дело...

             *      *      *


   Теперь о том,  куда можно текстуры при-
собачить. Ну ее, эту плазму... Лучше  рас-
скажу, как картинки конвертить!

   Вообще я знаю четыре метода конвертации
(спасибо "Алгоритмическим основам...").
   Суть первого  -  уменьшение  разрешения
картинки  с как бы сохранением  количества
цветов.
   Пример: пусть есть 16-ти колорное изоб-
ражение, скажем 256*192 пиксела. Разбиваем
его на квадратики  по 4  пиксела, затем  в
каждой из полученных клеток усредняем цве-
та 16-ти входящих в нее пикселов. Получаем
картинку (256/4)*(192/4)=64*48, причем,все
еще 16-цветную.
   Дальше все ясно: заменяем каждый пиксел
текстурой с соответствующим номером.
   Результат - ч/б изображение 256*192.

   Второй метод интереснее. Рассмотрим его
на той же картинке.
   Берем первую точку изображения. Ее код-
от 0 до 15. Заменяем  ее на пиксел из тек-
стуры с тем же кодом (номером), причем  из
текстуры берем пиксел с координатами:

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


 A и B - координаты исходной точки в цвет-
ном изображении.
   Повторив такой фокус для всех точек 16-
-цветной картинки, получим  скрин  256*192
ч/б, без потери разрешения.
   Можно даже не получать текстур, а рабо-
тать сразу с матрицей. Вот  алгоритм, сду-
тый, как вы сами понимаете, с книжки:
------------------------------------------


;Xmin, Xmax, Ymin, Ymax - пределы растра.
;N - размер матрицы (N*N - число цветов).
;Mod - функция, возвращающая остаток от
;целочисленного деления 1-го аргумента на
;2-й.

for Y=Ymin to Ymax
for X=Xmin to Xmax
    I=(X mod N)
    J=(Y mod N)
if I(X,Y)<D(I,J)  then
   Пиксел(X,Y)=Черный
else
   Пиксел(X,Y)=Белый
endif
Display Пиксел(X,Y); изображаем пиксел.
next X
next Y
finish
------------------------------------------


   Здесь массив I(X,Y)  -  исходный растр,
массив D(I,J) - наша матрица.
   Координаты I,J в матрице - от 0 до N-1.

   Третий  метод  тривиален: если  яркость
точки больше некоторого  порогового значе-
ния - пиксел белый, иначе - черный.

   Четвертый  метод я вообще  описывать не
собираюсь - кому надо, могут посмотреть...

   Да, чуть не  забыл! Конвертить-то  надо
не просто цветные картинки, а те,у которых
меньшему коду  цвета  точки  соответствует
меньшая яркость этой самой точки.
   Т.к. коды цвета определяются через R, G
и B компоненты, то  возникает задача опре-
деления яркости точки по трем байтам RGB.
   Но это выходит за рамки статьи...

             *      *      *


   Идем дальше. Поскольку  статья все-таки
по кодингу, привожу  здесь листинг генери-
ловки текстур 8*8:

        ORG   #6000
        ENT
;Written by Max/CBX/BDA, 27.10.98.
;      XAS Assembler v7.447.
;---------------------------------
DIT_GEN LD    E,64
DIT_GN1 LD    HL,MATRIX
        LD    D,D_TAB
        LD    B,8
DIT_GN2 LD    C,1
        LD    A,64
        SUB   E
DIT_GN3 CP    (HL)
        INC   HL
        RL    C
        JP    NC,DIT_GN3
        LD    A,C
        LD    (DE),A
        INC   D
        DJNZ  DIT_GN2
        DEC   E
        JP    P,DIT_GN1
        RET


D_TAB   EQU   #80; 2K size.

MATRIX  DB    1,33,9,41,3,35,11,43
        DB    49,17,57,25,51,19,59,27
        DB    13,45,5,37,15,47,7,39
        DB    61,29,53,21,63,31,55,23
        DB    4,36,12,44,2,34,10,42
        DB    52,20,60,28,50,18,58,26
        DB    16,48,8,40,14,46,6,38
        DB    64,32,56,24,62,30,54,22


Пример использования:

        LD    H,#80
        LD    L,XX
;L -номер текстуры от 0 до 64.
        LD    A,(HL); берем 1-й байт.
        INC   H
        ...
        LD    A,(HL); 2-й байт.
        INC H
        ...
;и т.д. всего 8 раз.

   Конкретное применение - скажем, заливка
граней в 3D-графике.