Квадратный корень, который ускорил игры в сто раз

Квадратный корень, который ускорил игры в сто раз

Математика, которая дала нам современные игры

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

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

Исторический контекст

В девяностых уже были трёхмерные игры: Doom, Duke Nukem 3D, System Shock, Turok, Unreal, Wolfenstein, Half-Life и другие. 

Трёхмерными эти игры были с разными ограничениями: например, в части из них трёхмерными были только коридоры, а враги и объекты были двумерными «спрайтами». В других была трёхмерная геометрия, но статичный свет. В третьих нельзя было посмотреть дальше условных 50 метров — геометрия уходила в «туман». Наконец, для игр с реально хорошей графикой нужны были 3D-ускорители типа 3Dfx. 

Прорыв в оптимизации

В 1999 году вышла игра Quake III Arena — трёхмерная стрелялка с красивой графикой и динамическим освещением. Она оказалась на голову выше всего, что было в тот момент на рынке:

  • выглядела красиво: эффекты, взрывы, красивые текстуры, прозрачности;
  • имела динамическое освещение объектов: если у тебя в руках была цилиндрическая пушка и ты поворачивался в разные стороны, эта пушка освещалась по-разному;
  • рисовала больше геометрии, поддерживала большие залы с большим числом противников;
  • работала без тормозов даже на слабом оборудовании того времени.

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

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

Квадратный корень, который ускорил игры в сто раз
Отражение выстрела на оружии и отражение света на стенах от источников внизу в Quake 3 Arena. Скриншот из Википедии.

Алгоритм освещения трёхмерных моделей

Если совсем упростить, то логика у освещения такая:

  1. У нас есть трёхмерная модель, которая составлена из виртуальных треугольников — полигонов. Каждый полигон как-то ориентирован в пространстве. 
  2. Есть источник света с координатами относительно нашего полигона.
  3. В зависимости от взаимного расположения полигонов и света каждый полигон имеет разную степень освещённости. Если полигон «смотрит» на свет, то он освещён ярче. Если полигон «отвёрнут» от света, то он освещён более тускло. 
  4. Чтобы понять степень отвёрнутости полигона от света, из его центра проводят виртуальную перпендикулярную линию — «нормаль». Нормаль — это вектор, то есть палка с каким-то направлением. Направление выражается координатами. 
  5. Наконец, нужно рассчитать, насколько нормаль «смотрит» на источник света. Это даст нам степень освещённости этого полигона. Останется только его покрасить в нужную степень яркости. 

Квадратный корень, который ускорил игры в сто раз
Вот пример простейшей трёхмерной сцены: куб и источник света
Квадратный корень, который ускорил игры в сто раз
Из каждой грани куба торчат «нормали». Это векторы
Квадратный корень, который ускорил игры в сто раз
С помощью линейной алгебры нам нужно понять, какой из этих векторов наиболее прямо смотрит на источник света. Чтобы не перегружать картинку, показываем только две нормали из трёх

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

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

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

В чём сложность алгоритма

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

Квадратный корень, который ускорил игры в сто раз

В этой формуле — ключ к оптимизации. Но сначала расскажем о том, как всё считалось до оптимизации.

Классический подход

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

  1. Возведение в квадрат.
  2. Сложение.
  3. Извлечение квадратного корня.

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

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

Трюк с волшебной константой

Разработчики Quake III Arena подсмотрели у коллег особенный трюк, который давал достаточно точный результат за одну сотую времени от исходного алгоритма. Трюк довольно сложный, но соль вот в чём: 

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

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

Джон Кармак, основатель ID Software, тоже не разобрался, как работает эта магия (потому что алгоритм был где-то подсмотрен и никто не знал, как именно он работал). Своё недоумение логикой работы он выразил своим знаменитым комментарием в коде:

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

Почему это важно

Сейчас подобная оптимизация применяется во многих стандартных библиотеках и игровых движках, но для того времени это был гигантский шаг вперёд. По уровню оптимизации это можно сравнить с тем, как если бы сейчас в «Киберпанк 2077» можно было бы поиграть на простом рабочем компьютере с двухъядерным процессором и встроенной видеокартой. 

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

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

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Алина Грызлова

Любите математику? Это для вас
Попробуйте бесплатный тренажер «Основы математики для цифровых профессий». Это все необходимые знания, чтобы закрыть пробелы в математике для айтишника.
Попробовать бесплатно
Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
medium