Быстрый инверсный квадратный корень

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

Быстрый инверсный квадратный корень (иногда называемый Быстрый InvSqrt() или по шестнадцатеричной константе 0x5f3759df) — это метод вычисления обратного квадратного корня $\frac{1}{\sqrt{x}}$ для 32-битных чисел с плавающей запятой. Алгоритм был, вероятно, разработан в Silicon Graphics в 1990-х, а реализация появилась в 1999 году в исходном коде компьютерной игры Quake III Arena, но данный метод не появлялся на общедоступных форумах, таких как Usenet, до 2002 или 2003 годов. Алгоритм генерирует достаточно точные результаты, используя уникальное первое приближение метода Ньютона. В то время основным преимуществом алгоритма был отказ от дорогих вычислительных операций с плавающей запятой в пользу целочисленных операций. Обратные квадратные корни используются для расчета углов падения и отражения для освещения и затенения в компьютерной графике.

Алгоритм принимает 32-битное беззнаковое число с плавающей запятой (unsigned float) в качестве исходных данных, сохраняет 1/2 числа для дальнейшего использования, после чего преобразует биты, представляющее оригинальное число с плавающей запятой в целое. Далее производится логическое смещение вправо на один бит и результат вычитается из «магической» константы 0x5f3759df. Это первое приближение обратного квадратного корня исходного числа. После производится обратое преобразование результата в число с плавающей запятой и вычисляется одна итерация метода Ньютона для получения более точного приближения. Алгоритм позволяет вычислять приблизительное значение обратного квадратного корня в среднем в 4 раза быстрее, чем деление чисел с плавающей запятой.

Алгоритм изначально приписывался Джону Кармаку, но исследования показали, что код имел более глубокие корни как в аппаратной, так и в программной сторонах компьютерной графики. Корректировки и изменения производились как Silicon Graphics так и 3dfx Interactive, с реализацией Гэри Таролли для SGI Indigo как раннее известное использование. Не известно, как эта костанта изначально выводилась, хотя расследование прольет свет на возможные методы.

С выходом в свет в 1998 году набора инструкций 3DNow! в процессорах фирмы AMD появилась ассемблерная инструкция PFRSQRT для быстрого приближенного вычисления инверсного квадратного корня.

Мотивация

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

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

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

$\|\boldsymbol{v}\| = \sqrt{{v_1}^2+{v_2}^2+{v_3}^2}$ — это норма вектора, аналог вычисления дистанции между двумя точками в в пространстве.

$\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\|$ — это нормализованный единичный вектор. Используется $\boldsymbol{x}$ для получения ${v_1}^2+{v_2}^2+{v_3}^2$,

$\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{x}$, который определяет единичный вектор обратный квадратному корню из расстояния компонентов.

Quake III Arena использует алгоритм быстрого обратного квадратного корня для ускорения обработки графики вычислительными блоками, но алгоритм уже реализован в некоторых специализированных аппаратных вершинных шейдерах, используя специальные программируемые матрицы (FPGA).

Внешние Ссылки

• Magical Square Root Implementation In Quake III