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-графике.
