Из журнала Deja Vu #07, Кемерово, 1999
(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 соответствует текстура ма-
ксимальной яркости (спрайт закрашен пол-
ностью).
В результате, на каждом шаге мы получи-
ли по текстуре. Вот все пять градаций:
Картинки, выведенные текстурами 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 шагов).
Привожу результат:
Думаю, вы уже поняли общую закономер-
ность получения текстур 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-графике.
* * *
В заключение привожу (как и обещал) на-
боры текстур 3*3 и 3*2:
Можете поэкспериментировать с тексту-
рами на двух битпланах.
Если битпланы имеют один цвет но разную
яркость, то для каждой точки получается 4
градации интенсивности:
+-------------+--------------+-----------+
|1-st, bright1|2-nd, bright0 | result br.|
+-------------+--------------+-----------+
| 0 | 0 | 0 |
+-------------+--------------+-----------+
| 0 | 1 | 1 |
+-------------+--------------+-----------+
| 1 | 0 | 2 |
+-------------+--------------+-----------+
| 1 | 1 | 3 |
+-------------+--------------+-----------+
Первая и вторая колонки показывают сос-
тояния пикселa на 1-ом (яркость вкл.) и
2-ом (яркость выкл.) битпланах. Третья -
визуальную яркость пиксела при flashing'e
битпланов.
Если теперь (фактически при двух битах
на пиксел) еще и использовать текстуры,
скажем 2*2, то при снижении разрешения
всего в два раза, получаем 13 уровней яр-
кости для квадрата 2 на 2 пиксела!
Из рисунка очевиден принцип получения
двубитплановых текстур из обычных.
---====< The END >====---