Клиппер как синдром аутизма двухмерной графики

Истинный 2D движок без клипера, все равно что машина без мотора - поедет лишь если в нее засадить Флинстоуна. Для тех, для кого слово клиппинг ни о чем не говорит, поясним что произошло оно от древне забугорского clip - "обрезать". И как не сложно догадаться это техника обрезки изображения, что является основой оптимизации любого более менее серьезного истинного 2D движка (в отличии от ложного, что использует силу Вуду (то бишь аппаратного ускорения)). Ведь очевидно, что скорость отрисовки зависит от числа обрабатываемых пикселей, даже если тупо идет копирование картинки - чем меньше пикселей, тем меньше надо копировать из одной области памяти в другую, а значит тем меньше это времени займет. Ну а в случае к примеру 3х мерного рельефа, где идет приходиться попиксельно обрабатывать данные это дает куда больший выигрыш. Для чего оно нужно на практике? Допустим у нас персонаж делает шаг и нам надо перерисовать спрайт, а значит и все что под ним, но зачем ради этого перерисовывать весь экран, если достаточно обновить небольшую область 60х28 пикселей? Конечно можно возразить, что в реальной жизни у нас на экране куча спрайтов и все двигается, но так ли это? Одни спрайты обновляются раз в 0.4 секунды, другие раз в 0.3, третьи раз в 0.7 и в итоге мы получаем что для обновления экрана нам все равно не нужно перерисовывать абсолютно все, а это позволяет сократить нагрузку в десятки раз. В случае с картой задачка усложняется тем что надо не только отбрасывать пиксели рисуемых тайлов, что не попадают в область, но и сделать предварительно выборку самой этой области, ибо проверка каждого тайла тоже не малая работа и когда их тысячи это сильно бьет по производительности. В нашем случае все вышло немного сложнее, т.к. мало того что у нас ромбики так еще и карта не квадратная, в зависимости от строки и столбца число тайлов в ней\нем скачет, вместе с положением (а ведь так как рисовка идет по диагоналям, нужно определить начало и конец каждой). Кроме того так как карта у нас 3х мерная пришлось увеличить область поиска по оси Y на предмет возможных высоких "гор" снизу и "впадин" сверху, что могут попасть в нашу область. В итоге вышло вот что (слева показан первый клипер, что делает предварительную выборку по тайлам, что могут попасть в область отрисовки, справа результат после применения второго клипера что отсекает отрисовку вне заданной области, желтая рамка просто для наглядности показывает границы области что должна быть отрисованно):

Как видно между делом изменились текстуры, все стало куда более красочно. К сожалению они как и прошлые в наглую позаимствованы на этот раз из другой игры. Но так как пока проект не распространяется и находиться в глубокой разработке будем надеяться правообладатели сего чудного контента нас простят. Но собственно я же обещал поделиться о том как все это работает...

3D Рельеф своими руками

Чтобы отобразить, что-то 3х мерное без магии OpenGL и\или DirectX потребуется:

1. Спроецировать изображение на плоскость, определив координаты вершин на экране.
2. Нарисовать примитивы по известным координатам (с точками и линиями все и так понятно, так что можно сказать тут речь идет лишь о полигонах (трехмерные объекты принято представлять в виде набора треугольников или реже четырехугольников))
3. Обработать освещение сцены (конечно на деле это следует делать одновременно с предыдущем пунктом, но для простоты изложения разделим их). Красивое освещение конечно всегда радует глаз, но надо понимать, что оно еще попросту необходимо для ощущения объема - на примере чайника справа отчетливо видно отличие результата с расчетом освещения и без. Так же освещение позволяет сгладить острые углы мало полигональных объектов.

В трехмерной графике, как и в жизни расстояния зависят от положения камеры и возня с координатами удобно сводиться к операциям над матрицами и векторами, оперируя с которыми можно легко вращать, масштабировать или проецировать объекты. В нашем случае двухмерной "изометрической" проекции с эти все намного проще - координаты XY сами по себе являются проекциями на экран, а координата Z проецируется на ось Y c выбранным коэффициентом. Таким образом нам остается лишь растянуть изображение полигонов. Я не хочу вдаваться в подробности механизмов 3D рендера, так как тема сия объёмна и мало относиться к нашему случаю.

Если вкратце, то полигон помимо вершинных координат, определяющих его положение в пространстве имеет также и текстурные координаты связывающие часть текстуры отображаемой на нем. Таким образом задачка наложения текстуры сводиться к трансформированию текстурных координат, самый простой вариант - заключается в том, что для полигона определяется наиболее длинная сторона по Y, затем из уравнения прямой интерполируются координаты начала и конца строк, после чего изображение рисуется построчно с линейной интерполяцией текстурных координат.

Но, так как я не пишу полноценный 3D движок задача сильно упрощается, тем фактом что размеры всех тайлов по оси X постоянны, а высота по Z влияет лишь на координаты вершин по Y. Так что нужно это лишь заранее сделать поворот текстуры на 45 градусов и сжать ее по оси X (ну или как вариант подготовить таблицы трансформирования координат). После чего все сводиться к простой линейной интерполяции столбцов изображения. Таким образом как видно в нашем случае отрисовка 3D рельефа осуществляется очень легко и быстро, конечно интерполяция и попиксельная отрисовка не так эффективная как построчный блиттинг, но тем не менее не является слишком уж тяжелой.

Да будет свет!

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

Но не будем сильно углубляться в физику и больше сконцентрируемся на прикладном применении теории. Во первых в случае 2D графики зеркальной составляющей можно и даже нужно пренебречь. Дело в том, что она зависит от угла падения света, что в свою очередь зависит от расстояния от поверхности до источника света.

Следуя традициям изометрического представления мы должны принять угол падения света на поверхность постоянным для любой горизонтальной поверхности вне зависимости от ее удаления и положения. Это вполне логичное допущение если вспомнить что суть любых изометрических двухмерных проекций это обеспечение условия независимости от расстояния между проецируемым предметом и наблюдателем, тогда как в реальности размеры зависят от удаленности от наблюдателя.

Отличие можно легко оценить на примере кубика слева в изометрической проекции и перспективе. Потребность в подобном правиле диктуется здравым смыслом - иначе при движении камеры пришлось бы перерисовывать все что есть и не просто перерисовывать, но еще и трансформировать как-то, а это слишком уж накладно.

Таким образом мы будем рассматривать только диффузное отражение, что не зависит от положения наблюдателя, а яркость которой зависит от угла между нормалью и источником света, или если быть точнее то от cos(θ), так как поверхность перпендикулярная направлению света лучше освещена, чем аналогичная поверхность под углом. В общем случае интенсивность отраженного света от пикселя определяется формулой:

I_diff = K_d • I_p • cos(θ), где I_p - интенсивность света, K_d - коэффициент диффузной отражательной способности поверхности (от 0 до 1). N - вектор нормали к поверхности. L - вектор задающий направление источника света. Если вспомнить, что скалярное произведение векторов N•L = |N|•|L|•cos(θ), то в случае если вектора N и L единичные получим, что I_diff = K_d • I_p • (N•L)

Для полного счастья введем еще рассеянное освещение, интенсивность которого определяется по формуле I_amb = K_a • I_a, где I_a - интенсивность рассеянного света, K_a - коэффициент рассеянного отражения. Учитывая оба источника света получим результирующую интенсивность: I = I_diff + I_amb = K_d • I_p • (N•L) + K_a • I_a. Однако в нашем случае двухмерной графики рассеянное освещение уже определяется спрайтами и тайлами, а в случае если мы захотим например сделать ночь эта составляющая будет определяться яркостью. Теперь нам надо разобраться с векторами L и N. Опять же исходя из двухмерности использование точечных источников света помимо солнца не является целесообразным, во первых по причине малого влияния, во вторых из-за черезмерного возрастания нагрузки на процессор.

Но настало время перейти от теории к практике, для чего сначала объявим тип вектора:

1

struct Vector3f { float x, y, z; }

где x, y, z длинны проекций вектора на соответствующие оси. Тогда получение вектор L для солнца в зависимости от угла (angle) можно представить как:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Vector3f GetLightVector(float angle)
{
	Vector3f L;
	L.y = 1f;
	L.x = (float)(y*tan(angle)*pi/180f);
	L.z = 0.5f;
	float vlen = sqrt(x*x+y*y) / sqrt(0.75);
	L.x /= vlen;
	L.y /= vlen;
	return L;
}

Мы задаем вектор направленный по оси Y составляющей с ней угол angle. Затем осуществляем его нормализацию в плоскости XY, положив составляющую Z равную 0.5. Так как в случае изометрии освещенность любой поверхности в плоскости XY не должна зависеть от вектора освещенности это означает что dot ( Vector3f(0f,0f,1f), L ) должен быть равен константе, а это условие будет выполняться лишь в том случае если L.z = const. В данном случае для удобства было выбрано значение 0.5.

Теперь нам остается получить нормаль к поверхности, для задания который как известно достаточно трех точек. И так:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Vector3f GetNormal(Vector3f a, Vector3f b, Vector3f c)
{
	Vector3f n, v1, v2;
	v1.x = a.x - b.x;
	v1.y = a.y - b.y;
	v1.z = a.z - b.z;
	v2.x = b.x - c.x;
	v2.y = b.y - c.y;
	v2.z = b.z - c.z;
	n.x = v1.y * v2.z - v1.z * v2.y;
	n.y = v1.z * v2.x - v1.x * v2.z;
	n.z = v1.x * v2.y - v1.y * v2.x;
	return n;
}

Нормаль направлена от лицевой стороны, что определяться порядком перечисления вершин (по часовой стрелки или против), в нашем случае используется перечисление по часовой стрелке.

Ну и финальный аккорд это нормализация, сложение векторов и скалярное произведение:

1
2
3
4
5
6
7

Normilize(ref Vector3f v)
{
	float vlen = (float)sqrt(x * x + y * y + z * z);
	v.x /= vlen;
	v.y /= vlen;
	v.z /= vlen;
}

1
2
3
4
5
6
7
8

Vector3f Sum (Vector3f l, Vector3f r)
{
	Vector3f v;
	v.x = l.x + r.x;
	v.y = l.y + r.y;
	v.z = l.z + r.z;
	return v;
}

1
2
3
4
5

float CalcIntensity(Vector3f v1, Vector3f v2)
{
	float dot = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
	return 32f * min(max(0.1875f, dot), 0.6875f);
}

Последнее наверное стоит пояснить для облегчения расчетов мы будем считать скалярное произведение только для единичный векторов, и только для определения интенсивности света. По этой причине мы и умножаем результат на 32, таким образом для поверхностей в плоскости XY интенсивность света будет равна 16.0, в случае если поверхность повернута к источнику света ее интенсивность будет от 16 до 22, а если повернута от источника света то от 6 до 16. Дополнительные граничные условия позволяют избежать через мерной засветки и затемнения. Почему были выбранны такие странные на первый взгляд значения, расскажу когда дойдем до расчета результирующего цвета пикселя.

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

Плоская модель затенения

И так теория позади, с математикой разобрались настало дело практики. Для простоты положим K_d и I_p равными 1, до тех пор пока у нас всего один источник света его яркость не играет роли, а коэффициент диффузного отражения имеет смысл лишь в случае если хотите подчеркнуть различие в интенсивности освещения различных поверхностей. Это конечно хороши и интересно, но вспомним из-за чего весь сыр бор - свет нам необходим для улучшения восприятия объема рельефа, подчеркивания склонов а не выпендрежа. Таким образом интенсивность света будет равна произведению единичных векторов N и L. А результирующий цвет будет равен c_a = min( max(0f, c_a • I • I_a), 1f), где c_a составляющая компонент R,G,B цвета пикселя от 0 до 1, а I_a - составляющая компонента цвета источника света. В случае бесцветного цвета I_a = 1.

Однако если помните, то я нормализовал вектор освещения так, что для плоского тайла cos(θ) = 0.5, а результат умножал на 32. Про магическое значение числа 32 будет пояснено ниже, а пока отмечу лишь, что это позволило слегка смухлевать и в нашем случае освещенность превратилась в коэффициентом засветки и затемнения поверхности.

В идеале нам остается найти нормаль и интенсивность в каждой точке, но расчет нормалей к каждому пикселю дело чрезвычайно муторное и накладное, к тому же в условиях низкой полигональнности надо как-то апроксиммирвать значения, для сглаживания угловатостей. Но обо все по порядку, начнем с самого простого варианта - плоской модели затенения (Flat shading), согласно которой мы просто считаем нормаль к каждой поверхности и применяем ее к любой точке на ней. Стоит добавить, что данная модель дает приемлемый результат лишь в случаях когда источник света достаточно удален от граней и произведение векторов N•L=const. Тут правда ждет небольшой сюрприз, так как тайл у нас определяется 4мя вершинами, тут можно или вручную поделить его пополам по горизонтали или вертикали или же ввести 5ю вершину по центру в плоскости XY и усредненными значениями координаты Z вершин.

Результат можно лицезреть справа, тут солнце двигается от -45 до + 45 градусов относительно оси Y, яркая монотонная текстура была выбрана специально для более наглядной демонстрации процесса затемнения и осветления

Магия Гуро

Как видно результат радует своей угловатостью, с этим можно бороться или увеличением числа полигонов или воспользовавшись моделями затенения с сглаживанием. Наиболее распространенна модель освещение по Гуро и пришедшая ей на замену модель по Фонгу. Последняя дает более лучшее качества и хоть существуют быстрые варианты данной модели она остается слишком тяжелой для процессора, поэтому оставим ее за кадром и сконцентрируемся на модели Гуро, что традиционно применялась в старых играх, по причине легко оптимизируемой линейной интерполяции используемой в ней.

В рамках этой модели мы должны оперировать не с нормалями к плоскостям а с нормалями к вершинам. Нормаль вершины определяется как N_v = ∑_k N_k / | ∑_k N_k |, где N_k - нормаль смежной грани. Аналогично можно ввести определение нормали ребра N_e. Теперь аналогично определяем интенсивность света в каждой вершине I₁, I₂, I₃. После чего задача сводиться к уже хорошо нам знакомой линейной интерполяции при обработке рисуемой строки (scan line), для чего предварительно надо найти граничные значения интенсивностей определяемые по формулам (кстати по большому счету процесс наложения текстур ничем не отличается, кроме того что там текстурные координаты вместо интенсивности освещения):

I₄ = I₁ •(y₄ - y₂) / (y₁ - y₂) + I₂ •(y₁ - y₄) / (y₁ - y₂)
I₅ = I₃ •(y₅ - y₂) / (y₃ - y₂) + I₂ •(y₃ - y₅) / (y₃ - y₂)
I_p = I₄ •(x₅ - x_p) / (x₅ - x₄) + I₅ •(x_p - x₄) / (x₅ - x₄)

Конечно в нашем случае удобнее будет вести обработку вертикальных линий совместив ее с наложением текстуры. Использование априорных знаний о размерах тайлов так же позволит сильно сэкономить на вычислениях и даже избавиться от делений, даже более того поскольку вектора N и L у нас постоянны мы можем заранее рассчитать значения интенсивностей света для вершин. Результат этого безобразия представлен слева (сильно выделяющиеся тайлы по центру являются следствием, того что для оптимизации отрисовка плоских тайлов идет другим образом и на данном этапе там не учитывалось освещение).

Как видно стало гораздо лучше, но тем не менее полученный результат хоть и дает сглаживание, но все еще далек от идеала. Проблема отчетливо наблюдается при малополигональности в случае острых углов образуемых соприкасаемыми поверхностями. Проблема в том, что в ряде случаев правильные нормали вершин дают завышенную или заниженную интенсивность света на гранях.

Очевидное решение, что само напрашивается - ввести дополнительные условия для интерполяции, добавив посередине каждого ребра дополнительную точку с интенсивностью равной интенсивности света нормали данного ребра. Это и правда помогло решить проблему (результат представлен справа), однако качества сглаживания все еще оставляет желать лучшего. Это также легко объясняется, дело в том что для идеального результата при линейной интерполяции должно выполняться условия перпендикулярности осей. А в нашем случае при изменении координаты Z меняется и угол между диагоналями, а значит для получения более точного результата мы должны или как-то предварительно экстраполировать значения или разбить тайл на еще более мелкие примитивы или отказаться от линейной интерполяции и\или модели Гуро. Но так как данная проблема бросается в глаза лишь при большом контрасте, т.е. сильном затемнении на очень ярких текстурах, я решил пока остановиться на достигнутом. Возможно позже я еще вернусь к этому вопросу когда станет более ясно каким запасом быстродействия обладает движок.

Преобразование цвета

Давно пора бы было поставить точку и начать раздавать призы тем, кто осилил эту писанину и добрался почти до самого конца, но за кадром осталось еще один не мало важный аспект а именно применение освещенности. Что в этом такого? Все же просто:

1
2
3
4
5
6
7
8
9

var i = (byte)(intensity >> 9);
var b = (int)(*(byte*)line & 0x1F);
var g = (int)(*(ushort*)line & 0x3E0);
var r = (int)(*(ushort*)line & 0x7C00);
b = Math.Min(b * i, 0x3E0) & 0x3E0;
g = Math.Min(g * i, 0x7C00) & 0x7C00;
r = Math.Min(r * i, 0xF8000) & 0xF8000;
*dest = (ushort)((r | g | b) >> 5);
intensity += intensity_inc;

Но в результате мы наблюдаем проседание FPS с 130 до 70-75, несмотря на микро-оптимизации (я сэкономил на битовых сдвигах при извлечении и упаковки компонент цветов). Тут же становиться понятен мистический смысл умножения интенсивности (intensity) на 32, таким образом я избавился от преобразования не целочисленного значения и получил возможность оптимизации путем махинаций с битовыми сдвигами (о чем именно я говорю станет понятно в последнем варианте). Конечно тут сразу же смущает Math.Min попытка замены данной функции на так мною любимую битовую магию

1
2
3
4
5
6
7
8
9

var i = (byte)(intensity >> 9);
var b = (*(byte*)line & 0x1F) * i; 
b += ((0x3E0 - b) & ((0x3E0 - b) >> 31));
var g = (*(ushort*)line & 0x3E0) * i; 
g += ((0x7C00 - g) & ((0x7C00 - g) >> 31));
var r = (*(ushort*)line & 0x7C00) * i; 
r += ((0xF8000 - r) & ((0xF8000 - r) >> 31));
*dest = (ushort)(((r & 0xF8000) | (g & 0x7C00) | (b & 0x3E0)) >> 5);
intensity += intensity_inc;

На деле дало проигрыш в 10 FPS, что странно так как бенчмарк показал прирост битовой магии (val1 + ((val2 - val1) & ((val2 - val1) >> 31)) ) по сравнению с Math.Min в полтора-два раза, но как известно бенчмаркам никогда не стоит слепо верить. А вот его замена на ветвления, как ни странно дало прирост в 5 FPS:

1
2
3
4
5
6
7
8
9

var i = (byte)(intensity >> 9);
var b = (int)(*(byte*)line & 0x1F);
var g = (int)(*(ushort*)line & 0x3E0);
var r = (int)(*(ushort*)line & 0x7C00);
b *= i; b = (b <= 0x3E0) ? (b & 0x3E0) : 0x3E0;  
g *= i; g = (g <= 0x7C00) ? (g & 0x7C00) : 0x7C00;
r *= i; r = (r <= 0xF8000) ? (r & 0xF8000) : 0xF8000;
*dest = (ushort)((r | g | b) >> 5);
intensity += intensity_inc;

Подумав, как еще над оптимизацией данной задачи я в результате пришел к следующему варианту, что дал прирост в 15 FPS:

1
2
3
4
5
6
7

uint cl = (uint)(*line);
cl = ((cl | (cl << 16))) & 0x03E07C1Fu;
cl = (((cl * (byte)(intensity >> 9)) >> 4));
cl |= 0x1Fu * ((cl & 0x4008020u) >> 5);
cl &= 0x83E07C1Fu;
*dest = (ushort)(cl | (cl >> 16));
intensity += intensity_inc;

А что бы не заменяться каждый раз преобразованием цвета исходного тайла я решил перенести это преобразование в загрузку спрайта, да конечно это увеличит объем памяти, но сегодня она давно перестала быть дефицитом, а вот выигрыш еще в 5 FPS стоит пары лишних мегабайт. Таким образом оптимизация пары строк кода позволило увеличить производительность отрисовки фактически на 50%.

Ну а на этом пока все, до новых встреч!