Таблица Брадиса или непосредственное вычисление?

@Fedor666 · Регистрация: 22.02.2010

Author24 — интернет-сервис помощи студентам

Здравствуйте!
Синусы, косинусы и корни всякие - насколько действительно сильно они грузят процессор? Подскажите, пожалуйста, имеет ли смысл использовать таблицы заранее вычисленных тригонометрических функций в программировании 3D? Большая ли выгода по скорости и стоит ли она получаемой погрешности? Может их использование незаменимо, но только в определенных масштабах? В старых играх на старых компах подобные таблицы использовались по полной. А как обстоят дела в современном мире?
Спасибо.

@snake32 · 18.12.2015, 16:45

Сообщение от Fedor666

А как обстоят дела в современном мире?

Единственное что могу сказать: Смотря какая точность требуется. Ибо если таблица очень большая, то скорее всего там уже будет тормозить за счёт того что таблица не будет влезать в кэш процессора отсюда и большие задержки. Но это всё теория... на практике может всё отличаться.
Если есть желание - проведите исследования в этой области. Я с удовольствием почитаю.

Добавлено через 2 минуты
Сегодня где не хватает производительности FPU считают на GPU... правда там свои ограничения...

@Fulcrum_013 · 27.12.2015, 21:04

Сообщение от Fedor666

Большая ли выгода по скорости и стоит ли она получаемой погрешности?

Сообщение от Fedor666

А как обстоят дела в современном мире?

Ну наверное выгода присутсвует и очень сильная если даже в мелкософтовских экземплах к Direct3D в шейдер кидается предпросчитанная таблица тангенсов. Что касается точности - то размер таблицы 1000 значений. Видать хватает с головой. На старых 386-ых обычно пользовали Fixed-Point таблицу синусов размером 64kb. это 32 тысячи значений, т.е примерно 10 угловых секунд. Таблица брадиса которая и в навигации и суръезных технических расчетах в свое время пользовалась по части точности нервно курит в сторонке. кстати флоату можно доверять не более чем в 6 десятичных знаках после запятой (во всяком случае при установке машинного эпсилон float меньше 1e-06 производные вычисленные с таким шагом идут в разнос ), что в 16-битный фикседпоинт тоже укладывается.
Опять же смотреть надо от задачи. угловые погрешности имеют свойство проявляться на очень больших дистанциях. А в некоторых задачах получается что значения углов соответствуют какому либо шагу тогда таблица вообще является точным решением. Опять же значения из таблицы можно интерполировать, что будет быстрее чем считать суму степенного ряда (алгоритм счета синуса сопроцесором), хотя так он считал 20 лет назад, с тех пор тоже наверное таблицу брадиса под рукой держит, которую потом уточняет. Во всяком случае целочисленное умножение на старых процах выполнялось за 2+2n (n-второй множитель) а на современных за 2 (что говорит о том что без таблички явно не обошлось).

Добавлено через 1 час 28 минут

Сообщение от snake32

таблица не будет влезать в кэш процессора

Обычно кеш сопоставим с размером ОЗУ старых компов на которых таблица синусов пользовалась для графики. Имеется в виду AT. а ОЗУ XT так вообще 5 раз в кеш влезет.

Добавлено через 7 минут

Сообщение от Fedor666

А как обстоят дела в современном мире?

Еще есть подход с сокращением количества членов в расчете ряда Маклорена. Например в одной из "старых" игр для освещения по Фонгу, в котором самым тяжелыми является нормализация нормали и вектора направления на источник, использовали вычисление корня с точностю в два члена, т.е 1+(x-1)/2 чего вполне хватало

@Fedor666 · 28.12.2015, 10:46 **[ТС]**

Проверил. Таблица синусов/косинусов 512/1024/2048 (по разному пробовал) float'ов от 0 до PI/2. Остальное зеркалил. Точность получилась весьма приличная. В скорости выигрыш - раза полтора при моем кодинге если Debug, а если... Это еще после первого вычисления в большом цикле таблица в кэш попадала. Короче, нафиг надо! Оно того не стоит. Не теряйте время! Правда, было интересно.

@Fulcrum_013 · 28.12.2015, 20:15

Сообщение от Fedor666

Это еще после первого вычисления в большом цикле таблица в кэш попадала

Дело не в кеше а в синхронизации с FPU при преобразовании float аргумента в инт - номер в таблице. чтобы поиметь ускорение аргумент должен быть в исходе в fixed point

Добавлено через 12 минут

Сообщение от Fedor666

Это еще после первого вычисления в большом цикле таблица в кэш попадала

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

@snake32 · 29.12.2015, 12:46

Сообщение от Fulcrum_013

Тогда выигрыш по скорости получается от 5 раз по сравнению с FPU.

Где этот тест с конкретными цифрами? Какое железо использовалось?

@Fulcrum_013 · 04.02.2016, 06:13

Сообщение от snake32

Где этот тест с конкретными цифрами? Какое железо использовалось?

ну возьми потесть выборку из массива по целочисленному ключу в сравнении с вычислением SinCos на FPU. На любом железе выборка будет гораздо быстрее. Именно поэтому и нужен аргумент в fixed point, чтобы его можно было использовать как ключ без FPU преобразований. т.к. в работе с FPU основную задержку дает не само вычисление а синхронизация при получении результата.

@snake32 · 04.02.2016, 11:16

Сообщение от Fulcrum_013

ну возьми потесть выборку из массива по целочисленному ключу

То есть по мимо таблицы придётся ещё в ручную(без FPU) преобразовать float в целочисленный ключ?
Или можно как-то проще этот ключ получить?

@Fulcrum_013 · 04.02.2016, 12:21

Сообщение от snake32

То есть по мимо таблицы придётся ещё в ручную(без FPU) преобразовать float в целочисленный ключ?
Или можно как-то проще этот ключ получить?

в том то и фишка что аргумент должен быть в исходе не в float а в fixed point и не в радианах а в оборотах. тогда при размере таблицы кратной степени 2 значения аргумента преобразовываются в ключ сдвигом и наложением битовой маски, квадрант тоже наложением битовой маски. т.е. все значения углов придется держать в fixed point и операции над ними производить тоже в fixed point.

Добавлено через 3 минуты
вообще такая технология пришла с тех времен когда FPU были слишком медленными для real-time графики в принципе. а соответсвенно вообще все было в fixed point а то и вообще в int.

@snake32 · 04.02.2016, 12:22

Сообщение от Fulcrum_013

в том то и фишка что аргумент должен быть в исходе

Да уж, очень специфичная оптимизация получается... подойдёт лишь единицам не миллион

@Fulcrum_013 · 04.02.2016, 12:28

Сообщение от snake32

Да уж, очень специфичная оптимизация получается... подойдёт лишь единицам не миллион

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

@snake32 · 04.02.2016, 13:37

Сообщение от Fulcrum_013

для твердотельных редакторов

У меня чуть другие задачи

C++

                double2 coord;
        double ar = radians( azimut );
        double di = j * steps; // km
        double diRe = di * oneRearth;
        if( diRe < eps )
        {
            coord = station;
        } else
        {
            double sinar = sin( ar );
            double sinc3 = sin( diRe );
            double PiSubSt = radians( 90.0 - station.y );
            double dd = atan2( sinar, sin(PiSubSt) / ( sinc3 / cos(diRe) ) - cos(PiSubSt)*cos(ar) );
            double ss = sinc3*sinar / sin(dd);
            ss = degrees( atan2( ss, sqrt( 1.0 - ss*ss )));
 
            coord = (double2)( station.x + degrees(dd), 90.0 - ss );
        }

@Fulcrum_013 · 04.02.2016, 14:34

Сообщение от snake32

У меня чуть другие задачи

т.е. нужно сделать шаг по азимуту? это в твердотельных редакторах тоже на каждом шагу, как и вообще в графике.

@snake32 · 04.02.2016, 14:45

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

@Fulcrum_013 · 04.02.2016, 14:48

Да кстати, а зачем постоянно из радиан в градусы гонять и обратно? Я для этих целей сделал класс который хранит и делает операции над углами в оборотах. перевод в/из градусы и тп используется только при вводе-выводе, ну привычислении SinCos еще в радианы преобразует. Да и удобней, не перепутаешь в какой мере углы и с посторонними (не углами) значениями не сложишь.

@snake32 · 04.02.2016, 14:52

ЗЫ: зная начальную точку на сфере, азимут и длину шага получить новую координату

Добавлено через 2 минуты

Сообщение от Fulcrum_013

а зачем постоянно из радиан в градусы гонять и обратно?

Весь остальной алгоритм построен именно на градусах

@Fulcrum_013 · 04.02.2016, 14:55

Сообщение от snake32

Можно попробовать сгенерить матрицу поворота, перевести точку (долготу, широту) в 3d и путём умножения перенести точку на шаг. А потом наоборот из 3d в (долготу, широту)...

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

Добавлено через 2 минуты

Сообщение от snake32

Весь остальной алгоритм построен именно на градусах

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

@snake32 · 04.02.2016, 15:25

Сообщение от Fulcrum_013

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

Подход поправок, кажется, очень не точным. Мне нужна точность до метра на поверхности земли(R=6371км). Для примера, к таким требованиям даже float не подходит, так как не может хранить такую точность, тем более что-то вычислять на нём. При значениях от 128 точность флоата ~ 3-5 метров.

@Fulcrum_013 · 04.02.2016, 16:53

Сообщение от snake32

Подход поправок, кажется, очень не точным.

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

@snake32 · 04.02.2016, 16:59

Fulcrum_013, с эллипсоидом конечно круто было бы, но пока и на идеальной сфере не всё так гладко как хотелось бы.

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 14:55	17
	Сообщение от snake32 Можно попробовать сгенерить матрицу поворота, перевести точку (долготу, широту) в 3d и путём умножения перенести точку на шаг. А потом наоборот из 3d в (долготу, широту)... а можно задать зависимость длины шага по параллели в зависимости от широты, и просто домножать на соответствующее значение, которое можно брать из таблицы, и интерполировать. Вобщем примерно как на карте поправки на склонение местности вносятся. Добавлено через 2 минуты Сообщение от snake32 Весь остальной алгоритм построен именно на градусах Ну сделать хранение/вычисление в градусах тоже не проблема. Просто придется поменять массив коэффициентов для перевода в другие стандартные шкалы (градусы/грады/радианы/обороты) 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 16:53	19
	Сообщение от snake32 Подход поправок, кажется, очень не точным. Все зависит от таблицы правок. По большому счету для абсолютно точного решения нужно сделать сечение плоскостью проходящей через вектор направления и центр сферы. потом по полученной в этой плоскости окружности отмерять длину заданной длины, потом перевести координаты обратно в широту и долготу. При этом учесть что Земля не шар а геоид. т.е. двигаться не по окружности а по эллипсу. т.е. фактически сам шаг надо отмерять решением интегрального уравнения. 0

@Fedor666 Основоположник на всё 44 / 44 / 3 Регистрация: 22.02.2010 Сообщений: 362
		1
	Таблица Брадиса или непосредственное вычисление? 17.12.2015, 05:38. Показов 3778. Ответов 33 Метки нет (Все метки) Здравствуйте! Синусы, косинусы и корни всякие - насколько действительно сильно они грузят процессор? Подскажите, пожалуйста, имеет ли смысл использовать таблицы заранее вычисленных тригонометрических функций в программировании 3D? Большая ли выгода по скорости и стоит ли она получаемой погрешности? Может их использование незаменимо, но только в определенных масштабах? В старых играх на старых компах подобные таблицы использовались по полной. А как обстоят дела в современном мире? Спасибо. 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	18.12.2015, 16:45	2
	Сообщение от Fedor666 А как обстоят дела в современном мире? Единственное что могу сказать: Смотря какая точность требуется. Ибо если таблица очень большая, то скорее всего там уже будет тормозить за счёт того что таблица не будет влезать в кэш процессора отсюда и большие задержки. Но это всё теория... на практике может всё отличаться. Если есть желание - проведите исследования в этой области. Я с удовольствием почитаю. Добавлено через 2 минуты Сегодня где не хватает производительности FPU считают на GPU... правда там свои ограничения... 1

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	27.12.2015, 21:04	3
	Сообщение было отмечено Fedor666 как решение Решение Сообщение от Fedor666 Большая ли выгода по скорости и стоит ли она получаемой погрешности? Сообщение от Fedor666 А как обстоят дела в современном мире? Ну наверное выгода присутсвует и очень сильная если даже в мелкософтовских экземплах к Direct3D в шейдер кидается предпросчитанная таблица тангенсов. Что касается точности - то размер таблицы 1000 значений. Видать хватает с головой. На старых 386-ых обычно пользовали Fixed-Point таблицу синусов размером 64kb. это 32 тысячи значений, т.е примерно 10 угловых секунд. Таблица брадиса которая и в навигации и суръезных технических расчетах в свое время пользовалась по части точности нервно курит в сторонке. кстати флоату можно доверять не более чем в 6 десятичных знаках после запятой (во всяком случае при установке машинного эпсилон float меньше 1e-06 производные вычисленные с таким шагом идут в разнос ), что в 16-битный фикседпоинт тоже укладывается. Опять же смотреть надо от задачи. угловые погрешности имеют свойство проявляться на очень больших дистанциях. А в некоторых задачах получается что значения углов соответствуют какому либо шагу тогда таблица вообще является точным решением. Опять же значения из таблицы можно интерполировать, что будет быстрее чем считать суму степенного ряда (алгоритм счета синуса сопроцесором), хотя так он считал 20 лет назад, с тех пор тоже наверное таблицу брадиса под рукой держит, которую потом уточняет. Во всяком случае целочисленное умножение на старых процах выполнялось за 2+2n (n-второй множитель) а на современных за 2 (что говорит о том что без таблички явно не обошлось). Добавлено через 1 час 28 минут Сообщение от snake32 таблица не будет влезать в кэш процессора Обычно кеш сопоставим с размером ОЗУ старых компов на которых таблица синусов пользовалась для графики. Имеется в виду AT. а ОЗУ XT так вообще 5 раз в кеш влезет. Добавлено через 7 минут Сообщение от Fedor666 А как обстоят дела в современном мире? Еще есть подход с сокращением количества членов в расчете ряда Маклорена. Например в одной из "старых" игр для освещения по Фонгу, в котором самым тяжелыми является нормализация нормали и вектора направления на источник, использовали вычисление корня с точностю в два члена, т.е 1+(x-1)/2 чего вполне хватало 1

@Fedor666 Основоположник на всё 44 / 44 / 3 Регистрация: 22.02.2010 Сообщений: 362
	28.12.2015, 10:46 [ТС]	4
	Проверил. Таблица синусов/косинусов 512/1024/2048 (по разному пробовал) float'ов от 0 до PI/2. Остальное зеркалил. Точность получилась весьма приличная. В скорости выигрыш - раза полтора при моем кодинге если Debug, а если... Это еще после первого вычисления в большом цикле таблица в кэш попадала. Короче, нафиг надо! Оно того не стоит. Не теряйте время! Правда, было интересно. 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	28.12.2015, 20:15	5
	Сообщение от Fedor666 Это еще после первого вычисления в большом цикле таблица в кэш попадала Дело не в кеше а в синхронизации с FPU при преобразовании float аргумента в инт - номер в таблице. чтобы поиметь ускорение аргумент должен быть в исходе в fixed point Добавлено через 12 минут Сообщение от Fedor666 Это еще после первого вычисления в большом цикле таблица в кэш попадала Смысл таблицы в том чтобы FPU вообще не трогать (а тем более не эмулировать, во время появления этого метода FPU было роскошью). Тогда выигрыш по скорости получается от 5 раз по сравнению с FPU. 1

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	29.12.2015, 12:46	6
	Сообщение от Fulcrum_013 Тогда выигрыш по скорости получается от 5 раз по сравнению с FPU. Где этот тест с конкретными цифрами? Какое железо использовалось? 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 06:13	7
	Сообщение от snake32 Где этот тест с конкретными цифрами? Какое железо использовалось? ну возьми потесть выборку из массива по целочисленному ключу в сравнении с вычислением SinCos на FPU. На любом железе выборка будет гораздо быстрее. Именно поэтому и нужен аргумент в fixed point, чтобы его можно было использовать как ключ без FPU преобразований. т.к. в работе с FPU основную задержку дает не само вычисление а синхронизация при получении результата. 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	04.02.2016, 11:16	8
	Сообщение от Fulcrum_013 ну возьми потесть выборку из массива по целочисленному ключу То есть по мимо таблицы придётся ещё в ручную(без FPU) преобразовать float в целочисленный ключ? Или можно как-то проще этот ключ получить? 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 12:21	9
	Сообщение от snake32 То есть по мимо таблицы придётся ещё в ручную(без FPU) преобразовать float в целочисленный ключ? Или можно как-то проще этот ключ получить? в том то и фишка что аргумент должен быть в исходе не в float а в fixed point и не в радианах а в оборотах. тогда при размере таблицы кратной степени 2 значения аргумента преобразовываются в ключ сдвигом и наложением битовой маски, квадрант тоже наложением битовой маски. т.е. все значения углов придется держать в fixed point и операции над ними производить тоже в fixed point. Добавлено через 3 минуты вообще такая технология пришла с тех времен когда FPU были слишком медленными для real-time графики в принципе. а соответсвенно вообще все было в fixed point а то и вообще в int. 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	04.02.2016, 12:22	10
	Сообщение от Fulcrum_013 в том то и фишка что аргумент должен быть в исходе Да уж, очень специфичная оптимизация получается... подойдёт лишь единицам не миллион 0

	04.02.2016, 16:59

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 12:28	11
	Сообщение от snake32 Да уж, очень специфичная оптимизация получается... подойдёт лишь единицам не миллион Ну вообще к примеру для твердотельных редакторов углы удобнее считать в оборотах и для работы с ними (сложение вычитание, перевод в радианы градусы и т.д.) использовать соответствующий класс. сделать класс шаблоном и пихнуть в качестве аргумента класс FixedPoint реализация которого тривиальна не такая уж и проблема. 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 14:34	13
	Сообщение от snake32 У меня чуть другие задачи т.е. нужно сделать шаг по азимуту? это в твердотельных редакторах тоже на каждом шагу, как и вообще в графике. 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	04.02.2016, 14:45	14
	Fulcrum_013, я, например, не представляю как можно с помощью таблиц оптимизировать этот код. Можно попробовать сгенерить матрицу поворота, перевести точку (долготу, широту) в 3d и путём умножения перенести точку на шаг. А потом наоборот из 3d в (долготу, широту)... 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.02.2016, 14:48	15
	Да кстати, а зачем постоянно из радиан в градусы гонять и обратно? Я для этих целей сделал класс который хранит и делает операции над углами в оборотах. перевод в/из градусы и тп используется только при вводе-выводе, ну привычислении SinCos еще в радианы преобразует. Да и удобней, не перепутаешь в какой мере углы и с посторонними (не углами) значениями не сложишь. 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	04.02.2016, 14:52	16
	ЗЫ: зная начальную точку на сфере, азимут и длину шага получить новую координату Добавлено через 2 минуты Сообщение от Fulcrum_013 а зачем постоянно из радиан в градусы гонять и обратно? Весь остальной алгоритм построен именно на градусах 0

@snake32 3419 / 1606 / 236 Регистрация: 26.02.2009 Сообщений: 7,855 Записей в блоге: 5
	04.02.2016, 15:25	18
	Сообщение от Fulcrum_013 а можно задать зависимость длины шага по параллели в зависимости от широты, и просто домножать на соответствующее значение, которое можно брать из таблицы, и интерполировать. Вобщем примерно как на карте поправки на склонение местности вносятся. Подход поправок, кажется, очень не точным. Мне нужна точность до метра на поверхности земли(R=6371км). Для примера, к таким требованиям даже float не подходит, так как не может хранить такую точность, тем более что-то вычислять на нём. При значениях от 128 точность флоата ~ 3-5 метров. 0

Таблица Брадиса или непосредственное вычисление?

Решение