Разбираем алгоритмы компьютерной графики. Часть 3 – анимация «Пламя»

Рассмотрим алгоритм рисования простейшего пламени. Придуман он довольно давно и использовался в огромном количестве демо и игр. Например:

Из игр стоит упомянуть знаменитый первый "Unreal" 1998 года выпуска. На заставке зеленое пламя сделано именно этим алгоритмом. Визуально его можно отличить сразу.

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

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

Что из себя представляет палитра: это массив, с заранее просчитанными цветами Т.е. мы сначала генерируем нужные нам цвета в нужной последовательности, записываем их в список, где номер в списке, это номер в палитре. Потом работаем уже не с цветовыми компонентами, а с порядковыми номерами из палитры. Это сильно "упрощает жизнь", если цвета нужны специфические, для отражения ситуации на экране.

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

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

Алгоритм формирования пламени построен именно на таком принципе - вычисления среднего цвета точек. И хотя глядя на анимацию, можно подумать, что его реализация довольно сложна, но как раз наоборот. Алгоритм предельно прост.

Представим, что у нас есть квадратная табличка размером 128 точек на 128.

Размер не принципиален. Просто 128 это одна из степеней 2 (зачастую это будет просто быстрее работать).

У нас есть палитра состоящая из 64 цветов. В ней цвет плавно меняется от черного к красному, а затем от красного к ярко-желтому.

Несколько утрированные цвета пламени. Черный цвет находится в начале, яркий в конце. Возрастание яркости цвета происходит с возрастанием его порядкового номера в палитре.

Заполним две нижние строки нашей таблички случайными значениями цветов. Самого яркого цвета и самого темного цвета. Т.е. или 0 для черного или 63 для яркого.

Все что выше этих двух строк заполнено черным цветом - 0 по палитре.

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

У нас получается некий средний цвет (X средний). По палитре он будет более тусклым чем те яркие случайные цвета, что были первоначально.

Полученный цвет мы уменьшаем на единицу. Это делается для того, чтобы яркость цвета убывала, тогда пламя у нас будет затухать поднимаясь вверх. Естественно, проверяем, что итоговый индекс не становится меньше нуля, иначе просто оставляем 0.

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

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

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

Чтобы избавиться от этой проблемы создаются две таблицы с точками пламени. Таблица 1 и 2. Одна из них назначается "активной" - из нее берутся точки для расчета, а вторая назначается таблицей "результатом". Например таблица 1 "активная". В нее мы генерируем два нижних ряда случайных значений яркости. И по ней начинаем просчет средних значений цвета точек. Но результат записываем не в неё же, а в таблицу 2.

На экране показываем таблицу "результат".

Это нам позволяет корректно высчитать цвета точек и они друг друга постоянно не перезаписывают.

Когда мы просчитали по активной таблице 1 все точки и записали результат в таблицу 2. Мы меняем назначение таблиц местами. Теперь "активная" таблица 2, а таблица "результат" - 1. И цикл снова повторяется. мы постоянно меняем таблицы местами.

В итоге получим анимацию похожую на пламя.

Несколько уточнений:

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

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

• Размер таблицы задали 128 на 128. Если задавать больше, например 800 на 800, чтобы совпало с размерами окна, то программа будет сильно тормозить. Поэтому просто увеличим масштаб наших точек при выводе на экран (в программе задан масштаб увеличения в 6 раз).

• Можно добиться более интересных эффектов, если по другому считать среднее значение. Например, если брать левую точку два раза, а правую не брать, то пламя будет "сносить ветром" влево. Или брать в расчет не четыре, а восемь окружающих точек. Вариантов расчета может быть множество.

Давайте взглянем на код:

import pygame
import random
import copy

MX = MY = 128           # Размер массива пламени
S_FIRE = 6              # Размер ячейки пламени на экране - для масштабирования

SX = MX * S_FIRE
SY = MX * S_FIRE

scr = []

line = [0] * MX         # Создаем список из нулей длиной MX
x_y = []                # Создаем список списков из нулей длиной MY, в итоге получится квадратная таблица из нулей.
for y in range(0, MY):
    x_y.append(copy.deepcopy(line))

scr = []                # Создаем список из двух квадратных таблиц
for i in range(0, 2):
    scr.append(copy.deepcopy(x_y))

iout = 0                # Номер текущей активной страницы

pygame.init()
screen = pygame.display.set_mode((SX, SY))
running = True

pal = []                # Палитра для пламени
                        # Задаем плавный переход от черного к красному, а затем от красного к желтому.
for i in range(0, 32):
    pal.append([i*8, 0, 0])
for i in range(63, 31, -1):
    pal.append([255, 255 - (i-32)*8, 0])

# -------------------------------------------------------------------------------------------------------
# Отрисовка закрашенного квадрата в нужных координатах, определенного размера.
# -------------------------------------------------------------------------------------------------------
def drawBox(x, y, size, color):
    pygame.draw.rect(screen, pal[color], (x, y, size, size))

# -------------------------------------------------------------------------------------------------------
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    # Две нижние стоки в массиве заполняем случайными значениями или 0 или 63, это минимальный и максимальный цвета из палитры пламени.

    for x in range(0, MX-1, 2):
        scr[iout][MY-1][x] = scr[iout][MY-2][x] = scr[iout][MY-1][x+1] = scr[iout][MY-2][x+1] = random.randint(0, 1) * 63

    # Проходим по всей нашей квадратной таблице, не трогая крайние точки по бокам.

    for x in range(1, MX-1):
        for y in range(MY-2, -1, -1):
            # получаем среднее значение цвета точки и окружающих ее точек.
            mid = round((scr[iout][y][x] + scr[iout][y][x-1] + scr[iout][y][x+1] + scr[iout][y+1][x]) / 4)
            if mid > 1:     # если цвет не нулевой, то уменьшаем его яркость
                mid -= 1

            scr[1-iout][y-1][x] = mid       # записываем полученное значение обратно в массив, но в другую плоскость.

    iout = 1 - iout                         # меняем текущую плоскость на противоположную

    for y in range(0, MY-3):                # Текущую плоскость выводим на экран, но не выводим несколько нижних строк по Y, в них случайный "мусор" для генерации пламени
        for x in range(0, MX):
            drawBox(x * S_FIRE, y * S_FIRE, S_FIRE, scr[iout][y][x])

    pygame.display.flip()

pygame.quit()

В следующий раз попробуем реализовать эффект визуализации взрыва (салюта) основанном на похожем алгоритме усреднения цвета по палитре.

Ссылка на 1 часть - алгоритм "Starfield Simulation"

Ссылка на 2 часть - туннель из демо "Second Reality"