Википедия

Быстрый обратный квадратный корень: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м чистка управляющих символов Юникода
 
(не показаны 4 промежуточные версии 1 участника)
Строка 6:
Алгоритм принимает 32-битное число с плавающей запятой ([[число одинарной точности|одинарной точности]] в формате [[IEEE 754]]) в качестве исходных данных и производит над ним следующие операции:
# Трактуя 32-битное дробное число как целое, провести операцию {{nobr|1=y<sub>0</sub> = 5F3759DF[[Шестнадцатеричная система счисления|<sub>16</sub>]] − (x >> 1)}}, где >> — [[битовый сдвиг]] вправо. Результат снова трактуется как 32-битное дробное число.
# Для уточнения можно провести одну итерацию [[Метод Ньютона|метода Ньютона]]: {{nobr|1 = y<sub>1</sub>y₁ = y<sub>0</sub>y₀(1,5 − 0,5xy<sub>0</sub>5xy₀²)}}.
Реализация из Quake III<ref name="hummus" />:
<syntaxhighlight lang="c" line="1">
Строка 40:
float f;
uint32_t i;
} conv = {number}; // memberтакая 'f'инициализация setприсвоит toполе value of 'number'.«f»
conv.i = 0x5f3759df - ( conv.i >> 1 );
conv.f *= threehalfs - x2 * conv.f * conv.f;
Строка 181:
[[Метод Ньютона]] даёт<ref name="moroz" /> <math>f(y)=\frac{1}{y^2}-x</math>, <math>f'(y)=-\frac{2}{y^3}</math>, и <math>y_{n+1} = y_{n} - \frac{f(y_n)}{f'(y_n)} = \frac{y_{n}(3-x y_n^2)}{2} = y_{n}(1{,}5-0{,}5 \, x y_n^2)</math>. Функция <math>f(y)</math> убывает и выпукла вниз, на таких функциях метод Ньютона подбирается к истинному значению слева — потому алгоритм всегда занижает ответ.
 
После одного шага метода Ньютона результат получается довольно точный ({{nobr|+0 0% −0,18 18%}})<ref name="lomont" /><ref name="robertson" />, что для целей компьютерной графики более чем подходит ({{nobr|1={{дробь|1|256}} ≈ 0,39 39%}}). Такая погрешность сохраняется на всём диапазоне нормированных дробных чисел. Два шага дают точность в 5 цифр<ref name="lomont" />, после четырёх достигается погрешность ''double''.
 
Метод Ньютона не гарантирует монотонности, но компьютерный перебор показывает, что монотонность всё-таки есть.
Строка 250:
 
== Мотивация ==
[[Файл:Lighting prism cylinder.svg|thumb|upright=1.5|Поле нормалей: {{nobr|а) для}} призмы (всеугловатый рёбра острыеобъект); {{nobr|б) для}} низкополигонального цилиндра (шесть рёбер сглажены)<ref name="normal_map" />]]
«Прямое» наложение освещения на [[Полигональная сетка|трёхмерную модель]], даже высокополигональную, даже с учётом [[Закон Ламберта|закона Ламберта]] и других сложных формул отражения и рассеивания, сразу же выдаст полигональный вид — зритель увидит разницу в освещении по рёбрам многогранника<ref name="normal_map">{{Cite web |url=https://habr.com/ru/post/481480/ |title=Это норма: что такое карты нормалей и как они работают / Хабр<!-- Заголовок добавлен ботом --> |access-date=2022-07-04 |archive-date=2020-07-10 |archive-url=https://web.archive.org/web/20200710004038/https://habr.com/ru/post/481480/ |deadlink=no }}</ref>. Иногда так и нужно — если предмет действительно угловатый. А для криволинейных предметов поступают так: в трёхмерной программе указывают, острое ребро или сглаженное<ref name="normal_map" />. В зависимости от этого ещё при экспорте модели в игру по углам треугольников вычисляют нормаль [[единичный вектор|единичной длины]] к криволинейной поверхности. При анимации и поворотах игра преобразует эти нормали вместе с остальными трёхмерными данными; при наложении освещения — интерполирует по всему треугольнику и нормализует (доводит до единичной длины).
 
Источник — https://ru.wikipedia.org/wiki/Быстрый_обратный_квадратный_корень