news.shamcode.ru | Разбираем алгоритмы компьютерной графики. Часть 4

Еще немного в копилку красивых эффектов и алгоритмов.

Вы в своей жизни наверняка видели салют, когда в ночном небе взрывает огненный шар и от него во все стороны медленно разлетаются огни.

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

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

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

Итак, что мы знаем о каждой нашей частичке?

У нее есть некие координаты x, y, и первоначально они совпадает к координатой места взрыва салюта.
Каждая частица летит в своем направлении, т.е. у нее есть скорости по осям координат dx и dy.
Каждая частица имеет свой цвет - color, который угасает по мере полет частицы.

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

Как нам описать сам взрыв заряда салюта и разлет частиц?

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

Место взрыва салюта и траектории разлета частиц

Из центральной точки разлетаются частицы в различных направлениях с различными скоростями.

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

Получить случайные скорости по X и Y, также легко - просто некие небольшие случайные числа. Но красивые эффекты так просто не рождаются и есть несколько тонкостей.

Будем генерировать случайные скорости разлета точек в некотором диапазоне, например от -30 до 30. Полученное число поделим на 10, и получим скорость в диапазоне от -3.0 до 3.0, со значениями после запятой. Пока вроде ничего подозрительного. Но давайте представим попробуем это изобразить графически:

Красными линиями обозначен диапазон возможных скоростей разлета частиц

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

Для нас желательно получить нечто вроде этого:

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

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

Звучит вроде не очень сложно, но как это сделать на практике?

Нам пригодятся знания по школьному курсу геометрии. Использовать будем две теоремы:

1. Теорема Пифагора. А именно то, что квадрат гипотенузы равен сумме квадратов катетов треугольника.

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

Давайте разбираться:

Точка С, это центральная точка нашего взрыва. Точка A это точка, в которую направлен вектор разлета частицы при генерации его случайными числами.

Через датчик случайных чисел мы получаем значения Xa и Yа. С помощью теоремы Пифагора мы можем вычислить длину отрезка CA:

$CA = \sqrt{X_a^2 + Y_a^2}$

Нам нужно увеличить длину отрезка CA до величины CB. Это происходит когда мы умножаем длину CA на некое случайное число в диапазоне от 0 до R (напоминаю, что R это радиус окружности, в которую должен вписаться взрыв).

Длина CB нам известна, остается лишь вычислить величины Xb и Yb. Они и будут теми нужными нам скоростями движения по оси X и Y, чтобы у нас получился красивый салют, с шарообразными взрывами.

Здесь нам на помощь приходит теорема подобия. Она сообщает, что для подобных треугольников верны соотношения:

$\frac{CB}{CA}=\frac{X_b}{X_a} и \frac{CB}{CA}=\frac{Y_b}{Y_a}$

а из этого мы можем вычислить:

$X_b = \frac{X_a * CB}{CA}$ $Y_b = \frac{Y_a*CB}{CA}$

Вот таким необычным способом нам и пригодилась теорема подобия треугольников.

Что мы имеем к этому моменту: координаты точки из которой произойдет взрыв салюта и скорости разлета частиц, которые построены так, чтобы формировался круговой взрыв.

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

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

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

Немного напомню суть алгоритма: цвет точки на экране будет являться средним арифметическим из четырех соседних точек.

Цвета точек сверху, снизу, справа и слева складываются, а затем результат делится на 4 и записывается обратно на экран. Таким образом у нас уже не будет отдельных точек, а каждая из них окажется окружена ореолом света.

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

Здесь тоже ничего особо сложного. Конечно реалистичную физику у нас нет причин программировать, а сделать что-то похожее довольно просто.

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

На каждом шаге движения частицы, будем прибавлять коэффициент гравитации к значению скорости движения dY по оси Y. Это нам даст то, что точки летящие вверх будут замедляться, а вниз ускоряться. Поскольку значение dX мы не трогаем, то частицы полетят по дуге.

И для "совсем красоты", давайте сделаем так, чтобы при падении на землю они отскакивали.

Для этого если координата по Y достигла нижней части окна, то мы умножим скорость dY на -1, т.е. изменим ее направление на противоположное, а также уменьшим ее в 2 раза, т.е. поделим на 2. Это даст эффект отскока от поверхности, с уменьшением скорости после отскока.

Ну и собственно сам код, он конечно уже получается уже более сложный, чем в предыдущих примерах:

import pygame
import random
import math
import copy

MX = MY = 128		# Размер массива для взрыва

scale = 5               # Масштаб точек для вывода на экран

SX = MX * scale         # Размер экрана исходя из размера плазмы и ее масштаба
SY = MX * scale

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

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

pal = []                # Палитра для графического эффекта
                        # Палитра почти как для пламени, но немного больше.
for i in range(0, 64):
    pal.append([i*4, 0, 0])
for i in range(64, 128):
    pal.append([255, i*4 - 255, 0])
for i in range(128, 255):
    pal.append([255, 255, round((i*4-128)/4)])

numParticle = 500       # Общее количество частиц

gravity = 0.08          # Коэффициент гравитации

particles = []                          # Список с частицами
for i in range(0, numParticle):         # Инициализируем список пустыми значениями
    particles.append([0, 0, 0, 0, 0])

# Для простоты ориентации в списке частиц, сделаем отдельные переменные для номеров ячеек отдельной частицы:
_x = 0              # номер координаты X
_y = 1              # номер координаты Y
_dirx = 2           # номер направления по X
_diry = 3           # номер направления по Y
_color = 4          # номер цвета

time = 0            # Счетчик времени существования взрыва на экране

# -------------------------------------------------------------------------------------------------------
# Генерация нового взрыва в указанных координатах.
# -------------------------------------------------------------------------------------------------------
def Boom(x, y):
    for i in range(0, numParticle):
        particles[i][_x] = x                # Задаем точку, откуда взорветса салют
        particles[i][_y] = y
                                            # Генерируем случайные скорости разлета частицы в диапазоне от -3.0 до 3.0
        particles[i][_dirx] = random.randint(-30, 30)/10.0
        particles[i][_diry] = random.randint(-30, 30)/10.0
                                            # Генерируем случайное число внутри радиуса от 0 до 5.0, для придания сферической формы взрыву
        dist = random.randint(0, 50)/10.0
                                            # Вычисляем диагональ треугольника верктора скорости до увеличения.
        mlen = math.sqrt(particles[i][_dirx]**2 + particles[i][_diry]**2)
        if mlen != 0:
            mlen = 1.0 / mlen
                                            # Используя теорему подобия вычисляем новые значения скоростей.
        particles[i][_dirx] *= mlen * dist
        particles[i][_diry] *= mlen * dist
                                            # Задаем начальный цвет точки - он самый яркий, т.к. это только начало взрыва
        particles[i][_color] = 254

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

# -------------------------------------------------------------------------------------------------------

Boom(MX/2, MY/2)

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

    for i in range(0, numParticle):             # Перебираем все частицы
        x = round(particles[i][_x])
        y = round(particles[i][_y])
                                                # Если координаты входят в экран - выводим
        if (x in range(1, MX-1)) and (y in range(1, MY-1)):
            scr[y][x] = particles[i][_color]
                                                # Изменяем координаты частицы в зависимости от скорости
        particles[i][_x] += particles[i][_dirx]
        particles[i][_y] += particles[i][_diry]

                                                # Реализуем отскок от земли
        if particles[i][_y] > MY:
            particles[i][_y] = MY
            particles[i][_diry] = -particles[i][_diry] / 2.0
        else:
            particles[i][_diry] += gravity      # Применяем к скрости частицы - гравитацию

    # Осуществляем размытие экрана по 4 соседним точкам
    for y in range(1, MY-1):
        for x in range(1, MX-1):
            color = round(((scr[y][x+1] + scr[y][x-1] + scr[y+1][x] + scr[y-1][x]) / 4.0) - 2)
            if color < 0:
                color = 0
            scr[y][x] = color
            drawBox(x*scale, y*scale, scale, color)

    # Для генерации нового взрыва используем счетчик, как только он превышен, новый взрыв и
    # перестартуем счетчик
    time += 1
    if time > 70:
        time = 0
        Boom(random.randint(1, MX), random.randint(1, MY))

    pygame.display.flip()

pygame.quit()

Итоговая анимация салюта (гиф сделан через кадр, для уменьшения размера)

Если бы мы не делали взрыв салюта по окружности, умножая на некий радиус скорости разлета частиц, то получили бы такую картинку:

В следующий раз попробуем разобрать алгоритм генерации простейшей "плазмы" - алгоритм "shade bob"

Ссылка на 3 часть - анимация "Пламя"

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