Light Tables (световые таблицы)

Пробовали ли Вы когда-нибудь эмулировать освещение на компьютере?
Существует бесконечное множество разных алгоритмов, которые прорисовывают 3D поверхности, создают эффект сглаживания, накладывают текстуру и т.д. А вы когда-нибудь задумывались, как они работают?

Уже написано немало демонстрационных программ, которые отображают трёхмерные объекты. Hо почему эти объекты обычно бывают одного цвета, лишь с градациями яркости его, или же с довольно простой текстурой, в то время, как 3D Studio Max создаёт полноцветные 3D мультфильмы в тех же 256 цветах? Конечно, если вы работаете в режиме TrueColor, вам ничего не стоит вычислить освещение и визуализировать объект в полном цвете. Hо дело в том, что TrueColor режимы обычно недоступны на дешёвых видеокартах или же настолько сложны в программировании, что автор той или иной демонстрационной программы не решается использовать его, тем самым увеличив размер своего творения.

Однако существует другой весьма элегантный способ создавать полноцветные изображения, затратив минимум компьютерного времени для вычислений в реальном времени. Он основывается на старом методе заранее вычисленных таблиц. Вы спросите: "А как это решает проблему многоцветности?" Вспомним программу 3D Studio. Она оптимально подбирала палитру для определённого мультфильма, а затем для каждого RGB пиксела в кадре подбирала ближайший цвет в оптимальной палитре. Hо сколько работает 3D Studio над каждым кадром? Hам желательно всё это делать в реальном времени. Hу ладно, поговорили, теперь переходим к сути дела.

Пусть у нас имеется некоторая текстура, у которой, скажем, нейтральный уровень освещённости. Как нам говорили в книге "Секреты Программирования Игр" и других книгах такого типа, вы помните? Автор утверждает, что идеальный вариант - палитра, которая для каждого цвета включает несколько уровней яркости. Это, конечно, неплохо, но всё упирается в размер палитры - 256 цветов. Если у нас в текстуре используется 64 цвета, то, по утверждению автора книги, а также некоторых программистов, мы будем иметь только 256/64 = 4 уровня яркости для каждого цвета. Естественно, что демонстрационная программа с таким качеством будет сплошным издевательством над зрителем. Кроме того, 64 цвета наверняка в себя включают несколько одинаковых цветов с разным уровнем яркости, например, тёмно-красный и светло-красный. Я вам предлагаю другой метод - двумерный байтовый массив в N*256 элементов (N - количество уровней яркости), один индекс которого - цвет в палитре, другой индекс - интенсивность цвета, результатом является также цвет в той же палитре. Малый размер палитры даже сыграл нам наруку, т.к. 256 цветов * 256 уровней яркости * 1 байт = 65536 байт, т.е. один сегмент реальной памяти, что особенно важно для тех, кто пишет в реальном режиме. Это слишком универсальный вариант - 256 уровней яркости, и, скорее, годится для режима TrueColor. Hо стандартные видеоадаптеры в режиме 256 цветов обычно поддерживают меньше градаций цвета, поэтому обычно хватает всего 32-х уровней. А 32*256 = 8192, даже в реальном режиме не представляет трудности создать такой массив. А как делать выборку из массива? А очень просто:

      MOV ES,LTSegment        ;сегмент с световой таблицей
      MOV BL,Color            ;заносим исходный цвет в BL
      MOV BH,Lightness        ;заносим яркость в BH
      MOV AL,ES:[BX]          ;теперь у нас в AL результат
    

Hу что, китайская грамота? А теперь я вам покажу, как считать эту таблицу.

Для того, чтобы создать универсальную палитру для вашей программы, поместите в редакторе TVPaint несколько текстур на одну картинку, затем примените фильтр так, чтобы освещение картинки распределялось неравномерно. Затем запишите всё это в файл PCX с цветовым разрешением 8 бит, используя global quantized (или так, как у вас называется в редакторе оптимальная палитра). Собственно, сама картинка нам не нужна. Hам нужна только палитра от неё. Преобразуйте ваши текстуры к этой палитре.

Если вы пишете какую-нибудь компьютерную игру, размер которой не критичен, то посчитайте таблицу один раз и сохраните этот сегмент в файле данных. Если вы пишете демонстрационную программу 4K или 64K - естественно, что таблицу нужно считать. Для простоты понимания я напишу процедуру формирования таблицы на Watcom C/C++. Если вы хотите просто использовать этот текст - используйте. Если вам нужны объяснения, то я всё объясню после этой программы:

tbldemo.cpp , часть #1

А теперь будем заниматься объяснениями. Согласитесь, что три компоненты (R,G,B) цвета чем-то напоминают координатные оси. Тогда сам цвет можно представить в виде точки в пространстве R,G,B.

Пусть A,B,C,D - некоторые цвета. Тогда, если A(rA,gA,bA), B(rB,gB,bB), то формула для расстояния от A до B:

dist = v( (rA-rB)^2 + (gA-gB)^2 + (bA-bB)^2 )

Аналогично можно найти "расстояние" между любыми двумя цветами. Как работает программа? Она поочереди находит расстояние от полученного по формуле яркости цвета RGB до каждого цвета в палитре. Очевидно, что цвет с наименьшим расстоянием до искомого - это и есть нужный нам цвет.

Зачем в программе используется функция абсолютного значения? Дело в том, что разности (xA-xB) могут принимать отрицательные значения, но таблица квадратов определена только для положительных. Тут использовано свойство: x^2 = (-x)^2.

Почему в программе не извлекается квадратный корень в соотв. с оригинальной формулой? Дело в том, что само значение расстояния для нас не играет роли. Hам важно знать, какое расстояние будет меньше. Тут опять на помощь приходит математика. Согласитесь, что для любых двух целых неотрицательных чисел будет выполняться:

если x > y, то x^2 > y^2,
если x < y, то x^2 < y^2,
если x = y, то x^2 = y^2,

т.е. логические операции сравнения , совершённые над самими числами будут давать тот же результат, что и те же логические операции, совершённые над их квадратами.

Давайте дополним картину процедурой вывода точки с указанной освещённостью. Хочу, чтобы вы прочитали эту процедуру, даже если уже разобрались в технологии вычисленной таблицы освещения, т.к. вы, вероятно, не сталкивались с такого рода оптимизацией умножения на 5. Я напишу эту процедуру для режима 320x200x8bit.

tbldemo.cpp , часть #2

Softening (сглаживание)

Теперь я вам постараюсь доступно объяснить, как избавиться от "лестничного эффекта" в режимах с низкой разрешающей способностью, что делать с interpolated picture и немного про прозрачные слои. Вы уже знаете технологию создания световых таблиц. В этой части используется подобная технология.

1. Вычисление таблицы

Для работы нам нужна опять же таблица (назовём её таблицей среднего цвета). Увы, здесь уже ничего сделать нельзя, чтобы уменьшить размер таблицы. Она будет строго 256*256. Элемент в таблице будет содержать индекс цвета в палитре, который является средним не по своему индексу, а по своей окраске от двух цветов той же палитры, которые, кстати, являются индексами для доступа к таблице. Выборка из таблицы ничем не отличается от выборки из таблицы освещения (см. предыдущую часть). Теперь я вам покажу, как считать эту таблицу. Я не буду переписывать полностью весь исходный текст, общий для этой части и предыдущей. Дополните просто вашу программу этими строчками:

tbldemo.cpp , часть #3

А теперь объяснение. Я, может быть, немного запоздал с объяснением, т.к. текст программы вполне ясен. Hо, всё-таки, я позволю себе рассказать вам это словами. Для простоты сделаем предположение, что видеоадаптер имеет линейное распределение интенсивности для каждого компонента цвета. Тогда очевидно, что найти среднюю интенсивность для двух данных можно по формуле среднего арифметического, т.е. (x+y)/2. Компьютер выполняет деление гораздо дольше, чем сдвиг, поэтому лучше воспользоваться сдвигом на один двоичный разряд вправо вместо деления на 2. Конечно, компилятор Watcom C/C++ сам заменит деление на 2 сдвигом, но кто знает, где ещё вы будете использовать этот пример, поэтому я решил перестраховаться и написать операцию сдвига (это я насчёт программы...)

2. Softening, Anti-aliasing

Что такое anti-aliasing? Это процесс вывода изображения с более высоким разрешением в более низком разрешении. Я не буду приводить пример для настоящего anti-aliasing'а, а приведу пример "подделки". Т.е., нам не нужно изображение с более высоким разрешением, а вполне хватит уже готового для режима с низкой разрешающей способностью. Для того, чтобы убрать лестничный эффект, мы сдвинем изображение на пол-пиксела по диагонали и наложим на исходное. Сейчас я приведу функцию, которая из double-buffer'а выводит изображение на экран, используя только что описанный мной эффект. Для нахождения среднего цвета используется таблица c_midc, которую мы уже вычислили.

tbldemo.cpp , часть #4

3. Interlaced picture

В некоторых методах сжатия видео предусмотрена возможность сжимать только чётные или только нечётные строки. Это реализовано для уменьшения дискового пространства, требуемого для видео. Во многих играх, например, The 11th Hour или Diablo, видео крутится именно таким образом. Т.е., чередуются строки - заполненная и чёрная. Как избавиться от чёрных строк в реальном времени? Можно, конечно, просто скопировать в неё предыдущую строку, но тогда мы, получается, зачем-то уменьшаем разрешающую способность по вертикали. А как использовать преимущества режима, не уменьшая его разрешающую способность? А очень просто - достаточно найти средний цвет для точки чёрной строки, находящейся сверху и снизу от неё. А теперь я напишу простую процедуру для удаления таких линий. Предположим, что изображение уже находится в scrbuf, нечётные строки - чёрные.

tbldemo.cpp , часть #5

4. Прозрачные слои

Hу здесь совсем всё просто. Я думаю, что даже обойдётся без объяснений. Я просто приведу процедуру, которая выводит на экран изображение, полученное в результате смешивания двух изображений, находящихся соответственно в буферах scr1 и scr2, адреса которых передаются в параметрах.

tbldemo.cpp , часть #6

Hу вот, вроде бы, и всё.

Если будут какие-нибудь вопросы или предложения - пишите. Со мной можно связаться по телефону +7 +375-162-256225, либо чеpез pедакцию.