Зачем нужна математика в компьютерных играх? [часть 1]
Привет-привет.
Почти 200 дней назад я написал комментарий под одним из постов, в котором немножко популярно объяснил, зачем в компьютерных играх (и компьютерной графике вообще) нужна линейная алгебра. Тот самый линал, что любой студент-технарь изучает на 1 курсе универа.
О том, что пост мне пилить лень, я предупредил сразу, но пикабушников это не убедило, у меня прибавилось over 100 подписчиков (с одного коммента-то!), так что почему бы и нет.
Примечание: рассказывать я буду с расчётом на людей, понимающих, что такое матрица, вектор и cross product, но, несмотря на это, постараюсь всё объяснить и расписать понятно даже для гуманитария (в идеале, линал для понимания поста изучать не нужно).
Как говорил Стивен Хокинг, «Любая формула уменьшает количество моих читателей вдвое». Пока, ребят).
Чуть-чуть школьной геометрии. Что такое вектор? Это стрелка. У неё есть длина и направление. Есть двумерные векторы (у которых направление — от 0 до 360 градусов), есть трёхмерные (у них есть два направления, оба от 0 до 360).
В абстрактной алгебре есть даже бесконечномерные векторы, но это нам не нужно)
Вот эта красная стрелка — и есть вектор. Линии, обозначенные буквами x, y, z, — называются умным словом координатные прямые.
Давайте запихнём наш вектор в коробку (оранжевые пунктирные прямые) и померяем её длину, ширину и высоту. Эти значения называются координатами вектора. В частности, здесь это (10, 2, 10). [именно в таком порядке, (x, y, z)]
Теперь если мы кому-нибудь скажем «вектор (10, 2, 10)», он сразу сможет его нарисовать, и это окажется в точности тот же вектор.
В школе на геометрии обычно изучают скалярное произведение двух векторов. Вот оно:
А ещё его изучают в универе, на линейной алгебре.
А теперь главное: применение! Давайте представим, что мы хотим нарисовать на экране 3D-модель. Любая 3D-модель состоит из треугольников, и, в общем, нарисовать кучу треугольников рандомным цветом — достаточно лёгкая задача.
Не слишком привлекательно, да? Давайте попробуем сделать нормальные тени.
Нужно узнать, каким цветом заливать каждый треугольник.
Итак, для начала введём вектор, который начинается в центре модели, а заканчивается там, где и будет источник освещения. А именно — вектор (0, 0, 1).
Так получается потому что ось z направлена на нас, а координаты — что-то вроде процентов, например, точка (0, 0, 0.5) — это точка ровно посередине между центром модели (которая, как мы считаем, находится «позади экрана») и экраном компьютера :)
А теперь давайте проведём из каждого треугольника перпендикулярный ему вектор (причём длины 1) и скалярно перемножим с нашим вектором источника освещения.
Это и будет коэффициент освещённости треугольника:
— если 0, то совсем не освещён, рисуем чёрным.
— если 0.5, то освещён наполовину, рисуем серым 50%.
— если 1, то полностью освещён, рисуем белым.
— и тому подобное.
И наша модель обретает жизнь!
Есть и более продвинутые модели освещения (например, Фонга), про них, возможно, напишу в будущем, но вряд ли.
И небольшое примечание про перпендикулярные векторы.
Перпендикуляр треугольника находится с помощью векторного произведения: берём любые 3 точки треугольника и составляем из них 2 вектора. Векторное умножение выглядит так:
Как видно, скалярное произведение — число, а векторное произведение — вектор.
Нужно ещё сделать, чтобы перпендикуляр был длиной 1, а это операция нормирования вектора:
С кодом модели можно поиграться тут: http://jsfiddle.net/2wvyga24/24/ .
Также можно почитать статьи хабраюзера haqreu: https://habrahabr.ru/post/248153/ .
Матрицы — это главная причина, по которой всё, что в играх должно вращаться или двигаться, вращается или двигается. И это именно то, как работает Free Transform в фотошопе.
Матрица — это обычная табличка с числами. Их даже можно складывать и умножать.
Если сложение — достаточно очевидная вещь, то вот умножение...
Запоминается простым правилом «строка на столбец». Берём 2 строку первой матрицы и скалярно умножаем на 1 столбец второй. Это и будет элемент, стоящий во 2 строке 1 столбца произведения.
Казалось бы, зачем так усложнять? Почему не умножать обычным образом?
Разгадка проста: изначально матрицы были придуманы, чтобы решать уравнения. Но это мы не будем затрагивать...
Ведь вдруг оказалось, что матричное умножение — это то, что делает матрицы столь полезными для компьютерной графики!
А ещё можно матрицы умножать на векторы. По обычному правилу: по сути, вектор — и есть матрица, просто с одним столбцом (или одной строкой, но это совсем отдельная тема).
Давайте возьмём плоскость и засунем любую картинку в нулевые координаты (т.е. левый нижний угол квадратика с кексом имеет координаты 0,0).
Как её теперь повернуть на 45 градусов? Картинка ведь состоит из точек (пикселей), и нужно найти новые координаты для каждой точки. Нужна какая-нибудь формула.
И она есть!
Итак, любая точка с координатами (x, y) — по сути, вектор с координатами (x, y) же. Умножение на матрицу 2×2 — это преобразования пространства (сжатие, поворот и тому подобное).
И поворот выглядит вот так:
Координаты x', y' — это и есть новые координаты после поворота.
А вот масштабирование (увеличение / уменьшение) — на λ по x и на η по y.
И наконец, «cкос», также известный как Skew / Shear. Фотошоперы поймут).
Поскольку ничего не понятно, вот утащенная из интернета картинка:
Например, мы повернули картинку на 30 градусов, а затем увеличили в 3 раза по вертикали и в 2 по горизонтали.
Тогда пиксель с координатами (50,30) перейдёт в пиксель с координатами (2, 175):
Я же ничего не перепутал, да?
Все наши преобразования происходят вокруг начала координат — точки (0, 0). Если мы хотим повернуть картинку вокруг центра, нужно вставлять её так, чтобы центр картинки оказался в точке (0, 0).
Увы, перемещения с помощью матрицы выразить нельзя. Так что был придуман небольшой хак: давайте перейдём к матрицам и векторам 3×3:
Все предыдущие преобразования остаются в силе:
Но теперь мы можем выразить перемещения!
Ну что ж, теперь несколько хороших моментов:
— Умножение матриц не перестановочно, т.е. обычно A × B ≠ B × A. От перестановки множителей меняется произведение. Например, [переместить на x,y и повернуть на φ] — не то же самое, что [повернуть на φ и переместить на x,y].
— Однако ассоциативно, т.е. (A × B) × C = A × (B × C).
— А значит, перемножение матриц даёт суммарное преобразование. Например: A — поворот, B — перенос, C — масштаб. Тогда матрица A × B × C — это всё сразу. И произведение матрицы (A × B × C) на вектор — это преобразование вектора всеми тремя способами на все те же координаты.
— Обратная матрица — обратное преобразование. Например, поворот на 30 градусов — поворот на -30. Увеличение вдвое — увеличение в 0.5.
И самое важное:
— Всё это переносится практически без изменений в трёхмерное пространство. Векторы и матрицы становятся четырёхмерными (чтобы выражать перемещения), появляется несколько видов поворотов... ну и всё.
P. S. вероятно, следующие посты не будут публиковаться в сообщество.
P. P. S. поскольку мне лень, ждать продолжения бывает долго х)
Вопросы в комментарии :D
В Питере шаверма и мосты, в Казани эчпочмаки и казан. А что в других городах?
Мы постарались сделать каждый город, с которого начинается еженедельный заед в нашей новой игре, по-настоящему уникальным. Оценить можно на странице совместной игры Torero и Пикабу.
Реклама АО «Кордиант», ИНН 7601001509
Конкурс для мемоделов: с вас мем — с нас приз
Конкурс мемов объявляется открытым!
Выкручивайте остроумие на максимум и придумайте надпись для стикера из шаблонов ниже. Лучшие идеи войдут в стикерпак, а их авторы получат полугодовую подписку на сервис «Пакет».
Кто сделал и отправил мемас на конкурс — молодец! Результаты конкурса мы объявим уже 3 мая, поделимся лучшими шутками по мнению жюри и ссылкой на стикерпак в телеграме. Полные правила конкурса.
А пока предлагаем посмотреть видео, из которых мы сделали шаблоны для мемов. В главной роли Валентин Выгодный и «Пакет» от Х5 — сервис для выгодных покупок в «Пятёрочке» и «Перекрёстке».
Реклама ООО «Корпоративный центр ИКС 5», ИНН: 7728632689