Как стать автором
Обновить

Комментарии 13

Кто-нибудь понял, зачем автору вообще понадобился арктангенс? Ведь чтобы узнать, направлены ли два вектора в одну сторону, достаточно посчитать векторное произведение x1y2–y1x2 (ну, чтобы увидеть, насколько именно отличается направление – понадобится его нормировать).

Потому что ему нужно узнать численное значение угла между вектором и базисному к нему (не знаю зачем, скорее всего, экономит байты, это ведь NES все таки). Для использования формулы векторного произведения нужно
1) все равно реализовать формулу вычисления арк-фукнции (только арккосинуса),
2) вычислить модули, точнее, модуль вектора (второй уже известен, так как является проекцией на базисную ось). Если бы направления кораблей хранились в виде нормализованных векторов, то это можно было бы опустить, но это NES, байты и такты важны, и автор вынужден использовать только экранную системы координат.

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

Не надо ему знать значение угла. Надо знать, угол больше или меньше заданного.


Итого, если вектора нормированные – векторное произведение и сравнить его с threshold. Всё.


Если вектора не нормированные – позаморочнее, но всё равно модуль считать не надо. Можно, к примеру, сравнить векторное произведение со скалярным, умноженным на заранее посчитанный коэффициент. Можно и иначе. Но гарантированно ничего сложнее умножения.

> Не надо ему знать значение угла. Надо знать, угол больше или меньше заданного.
Из чего это следует? По статье, это универсальная функция, используемая несколько раз, в том числе, с конкретными вычисляемыми значениями.

> Итого, если вектора нормированные – векторное произведение и сравнить его с threshold.
Если бы все было так просто. Конечно, вектор не нормализован (это вообще расстояния между проекциями точек по осям).

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

В последнем случае – не надо ничего нормализовывать. Размерность у скалярного и векторного произведения одинакова. Надо проверить |A×B| < a A•B.


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

Надо проверить |A×B| < a A•B.

Скаляр — это модули, умноженные на косинус. Векторное произведение на плоскости — это модули, умноженные на синус. Приравнивая или решая неравенства с вектором и скаляром в разных частях неравенства, вы получите, внезапно, синус, деленный на косинус. Т.е., ровно тот же самый тангенс (ну или котангенс, естественно), от решения с которым пытаетесь уйти.


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

И зря. Я примерно представляю себе ход ваших мыслей, но все дело в ограничениях платформы, всякая обобщенная матрично-векторная математика на которой неприменима, от слова вообще.

Я не получаю тангенс, так как не делю: я косвенно сравниваю его с threshold.


В общем, у меня рефлексы, выработанные ещё на 8080: я избегаю вычисления тригонометрических функций.


Повторюсь: использовать LUT – ok, если я увижу, что мне не нужно точное решение – конечно, я им воспользуюсь. Но обдумывать использование арктангенса там, где мне даже не нужно его значение?! Это всё равно что перспективную проекцию строить через вычисление угла зрения, или поворот через углы Эйлера.

Тупо прямой табличный atan2(x,y) на 256 значений, который "округляет" x и y до 4х старших бит имеет среднеквадратичную ошибку 2 градуса, максимальную 4.
Если сделать на один квадрант, то можно либо сократить таблицу в 4 раза либо уменьшить ошибку в два раза.
А для 7.5 градусов можно и в таблицу на 16 байт уместиться без каких либо вычислений, за исключением проверки x<>0, y<>0 для выбора квадранта.


Заголовок спойлера

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

я про что можно без арфметики вообще всё двухмерное пространство в таблицу запихать, const char atan2[8][8]={{},{},...}, т.е. весь квадрат, а не только единичную окружность и получать результат atan2[x>>5][y>>5]
И что-то мне кажется что по размеру это будет не сказать что больше, и уж точно быстрее.
А ошибка при этом получается на удивление небольшая даже для совсем грубого округления координат до 2-3 бит.
И 8ми битные процессоры вроде нибблами умели ворочать, без сдвигов по одному биту, так если и не совсем бесплатная то почти.

Что вернет ваш вариант atan2(10,10)? А atan2(127,127)?

ну да, перед злым округлением надо бы проследить чтобы в 0,0 не округлиться и немного отнормироваться, если вдруг так получилось. if (x < 16) swap_nibble(x);


просто совсем недавно похожая задача вылезла на немощном МК оцифровать аналоговые sin/cos каналы относительных энкодеров и вычислять и отслеживать углы (накапливать переполнения через 2Pi)
там амплитуда получается всегда более менее отнормирована, а атан2 по таблице с ошибкой в градус считается за несколько тактов, ценой нескольких кБ флэша.

Миллениалы изобрели лукап-таблицы)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории