Тригонометрия

Перевод Обучение технологии ray-casting. Часть 2

04.09.2020 00:21:28 |

Автор: admin

Приветствую тебя, читатель. Это вторая часть серии переводов работы "Ray-Casting Tutorial For Game Development And Other Purposes". Второй части предшествует первая, которую так же можно просмотреть.

~~Начнем!~~ Продолжим!

Ограничения ray-casting

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

Отсюда мы получаем еще одно ограничение: точка обзора не может вращаться вдоль оси Z (которую мы все знаем, как ось аппликата-прим.пер.). Почему? Представим обратное: вращение разрешено. В таком случае стены могут наклоняться, и соответственно теряется преимущество отрисовки вертикальных срезов этих самых стен. Ограничение во вращении является одной из причин, почему технологию ray casting нельзя считать полноценным 3D.

Технология ray-casting позволяет игроку двигаться вперед/назад и поворачиваться вправо/влево, но не вращаться вокруг оси Z (такой тип вращения называется креном (если ось Y вертикальная, то вращение по ней-тангаж, а по оси X - рыскание, - прим.пер.)).

Шаг 1: Создание окружения

Для то, чтобы отобразить работу ray casting, мы создадим сцену в виде лабиринта, которая будет основываться на следующих геометрических ограничениях:

Стены всегда перпендикулярны полу
Стены представляютсобойодинакового размера кубы
Пол всегда ~~лава~~ плоский

Каждый куб будет иметь размер 64x64x64 (Выбор произвольный, но полезно иметь такое число, которое будет являться степенью 2. В таком случае мы сможем использовать операцию битового сдвига, которая работает быстрее умножения и деления). Стоит отметить, что чем больше размер блоков, тем более кубическим будет казаться наш мир, с другой стороны, слишком маленькие блоки ввиду их большого количества замедлят процессрендера.

Перед тем как продолжить, мы должны определить систему координат (далее-СК), чтобы далее не было каких-либо недопониманий. Наша СК изображена на следующем рисунке.

Любая картезианская СК также будет работать. Тем не менее, будьте последовательны и не используйте разные СК. Иначе вы можете запутать себя-проверено мною лично.

Шаг 2. Определение атрибутов проекции

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

Высота игрока, поле зрения игрока (FOV - Field Of View), и координаты игрока
Размеры плоскости проекции
Как соотносятся игрок и плоскость проекции

Игрок должен иметь возможность видеть то, что находится напротив него. Для этого мы объявим FOV, который определит, насколько широкая область сцены доступна для наблюдения игроком. Люди имеют FOV в 90 и больше. Тем не менее, такой угол не совсем подходит для экранов ПК. Мы выберем 60, которые были получены путем экспериментов и проб (насколько хорошо выглядит картинка с таким-то углом FOV). Высоту игрока определим, как 32 единицы. Это вдвое меньше, чем стены, что является разумным допущением. (если взять реальное соотношение средней высоты помещения к среднему росту человека-самца, то получим: 2.4/ 1.7 = 1.41 - прим.пер.).

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

Чтобы поместить игрока в наш мир, нужно для этого игрока определить X-координату, Y-координату и угол поворота. Эти 3 атрибута формируют POV (point of view) игрока.

Если предположить, что игрок где-то по центру координатной сетки (1, 2), и его угол поворота равен 45 относительно начала оси, то FOV будет выглядеть примерно, как на картинке ниже. (Каждый элемент сетки имеет размеры 64x64 единиц).

На картинке слева мы видим POV, которая представляет собой координаты игрока и его угол поворота. На картинке справа - FOV - область видимости игрока. - прим.пер.

Нам нужно определить плоскость, на которую мы будем проецировать то, что видит игрок. Плоскость шириной в 320 единиц и высотой в 200 - это хороший выбор, т.к. это разрешение большинстваVGАвидеокарт.

Когда POV игрока спроецирован на плоскость, сцена будет выглядеть, как на картинке ниже.

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

Что мы имеем:

На картинке слева мы видим плоскость проекции того, что видит игрок (это же экран нашего монитора): она имеет размеры 320х200 пикселей и центр в точке (160, 100). На картинке справа представлен вид "из глаз игрока". - прим.пер.

Теперь перейдем к расчетам (большая часть вычислений относится к программе старших классов, я советую повторить тригонометрию, теорему Пифагора, если вы не понимаете, как получены такие результаты).

FOV равен 60. При этом мы видим плоскость проекции шириной в 320 пикселей, то есть 60 соответствуют 320 столбцам и, следовательно, 1 столбец равен 60 / 320 градусам. - прим.пер.

FOV и плоскость проекции образуют равнобедренный треугольник. Если к плоскости проекции провести высоту, то мы получим два прямоугольных треугольника с одной стороной в 320 / 2 = 160 единиц и углами: 90, 60 / 2 = 30 и 90 - 30 = 60 соответственно. Используя формулы тригонометрии мы находимдлинувысоты (277), которая и является расстоянием между игроком и плоскостью проекции. - прим.пер.

По итогу нам известно:

Размеры плоскости проекции (экрана) = 320х200 единиц
Центр плоскости проекции (160, 100)
Расстояние до плоскости проекции = 277 единиц
Угол между последующими лучами = 60 / 320 градусов

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

Конец второй части

Подробнее..

Категории: Программирование , Перевод , Разработка , Разработка игр , Игровой движок , Тригонометрия , Псевдотрёхмерность

Подпольная тригонометрия различных метрик

11.10.2020 22:19:02 |

Автор: admin

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

Небольшая, но чертовски интересная преамбула

Идея этой статьи ко мне пришла случайно, когда в очередной раз я набросился на пресловутое уравнение

$display$

В попытке решить его АНАЛИТИЧЕСКИ, то есть получить так называемое closed-form solution или ответ в виде конечной композиции чисел (что-то типа $\sqrt 5 /2 + 17\pi$ ). Кстати, попробуйте сами! Потупив минут 15 над этим уравнением вы быстро поймёте, что предоставленных Вам школьных знаний явно не хватает (наверное) чтобы решить это уравнение, а сложные вышматовские штучки делают решение и вовсе недосягаемым. После вашей первой капитуляции перед этим уравнением, к Вам придёт желание пойти в гугл, а он с подобающим ему беспристрастием выдаст Вам Dottie number, предложив компромиссное решение в виде бесконечной сходящейся численной последовательности.

Да кстати, численное решение: $inline$ .

Получив решение, Вы можете, вздохнув с облегчением, закрыть вкладку в браузере, приняв реальность talis qualis. Однако я отношусь к той касте ~~отбитых~~ любителей математики, которые считают, что если такие чрезвычайно просто сформулированные задачи испытывают проблемы с решением, то у самой сути разработанной математики есть какие-то проблемы и их неплохо было бы решить (попутно разработав новый аппарат).

В любом случае, в один из таких крестовых походов на эту задачу ко мне пришёл резонный вопрос: "а что такое косинус?". Самое первое определение, которое я когда-то узнал в школе было следующим:

Косинус острого угла в прямоугольном треугольнике это отношение прилежащего катета к гипотенузе.

И именно с этого определения начинается мой рассказ.

Многоликость гипотенузы

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

$c=\sqrt{a^2+b^2}$

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

немного о теореме Пифагора

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

Давайте теперь изменим определение гипотенузы, предполагая, что мы работаем в пространстве с Манхэттенской метрикой. Тогда:

$display$

Соответственно определения Синуса и Косинуса станут:

$\sin(x)=\frac{a}{|a+b|},\ \cos(x)=\frac{b}{|a+b|}$

Лично у меня на этом этапе уже тряслись руки от безудержного желания поскорее построить графики этих "отвергнутых" из-за своей природы функций. Но позвольте сначала определиться со способом такого построения.

К сферам

Определяя метрику в пространстве, мы автоматически определяем сферу на ней (которая по определению: множество равноудалённых точек от данной). Об этом на хабре уже были статьи (например Пространства с иным числом Пи). Поэтому коротко: если мы зададим радиус сферы равным 1, то для различных $inline$ норм, мы можем определить следующее равенство, задающее сферу (окружность для двумерного случая):

$(a^p+b^p)^\frac{1}{p}=1$

Подставляя различные значения p в уравнение, получаем наших героев:

Как вы наверняка догадались, случай $inline$ соответствует нашей привычной Евклидовой метрике, а $inline$ Манхэттенской метрике. Наблюдение того, как плавное изменение параметра p приводит к деформации сферы (и нашего понимания сферы), доставляет неподдельное эстетическое наслаждение Но давайте двинемся дальше.

К тригонометрии

Последний важный вопрос: "А что, собственно, такое угол?". На первый взгляд, угол это всего лишь некоторая мера, "как-то" характеризующая два луча исходящих из одной точки. Возможно для специалистов в математике этот вопрос покажется надуманным и избыточным, но для меня дилетанта, этот вопрос кажется крайне существенным. Однако, на текущий момент, я ничего не могу добавить к этому вопросу, кроме того, что угловая мера кажется мне "очень странной". Ну да ладно.

Для того чтобы наконец построить графики синуса или косинуса для манхэттенской метрики, мы будем будем действовать хитрым образом. Мы используем известные значения углов и их тригонометрических соотношений для Евклидовой метрики, а затем сменим метрику и найдём соответствующие синусы и косинусы в ней. Для лучшего понимания я введу специальную нотацию:

$\sin_p(x),\ \cos_p(x),\ \tan_p(x),$

где индекс $inline$ будет обозначать метрику для которой мы находим значение соответствующей тригонометрической функции. Например, как вы хорошо помните из школы: $\sin_2(\frac{\pi}{4})=\frac{\sqrt{2}}{2}$ или $\tan_2(\frac{\pi}{4})=1$ . Для перехода из одной метрики в другую, в рамках данной задачи, очень удобно воспользоваться простой линейной функцией $inline$ , где $inline$ коэффициент наклона прямой, $inline$ длина прилежащего катета прямоугольного треугольника (см. картинку ниже).

Таким образом, мы будем выполнять следующий набор действий, задавшись, как и ранее единичным радиусом окружности:

Зададимся некоторым углом $inline$ и найдём для него значнеие $\tan_2(x)$ ;
Приравняем полученное значение тангенса к коэффициенту наклона прямой: $k=\tan_2(x)$ , и построим эту прямую.
Решим уравнение $inline$ для $b\in[0,1]$ .
Для найденного значения $inline$ рассчитаем $inline$
Найдём значение $\sin_1(x),\ \cos_1(x)$ (или любую другую тригонометрическую функцию) по определению.

Кстати, напомню и сразу обобщу это определение для произвольной $inline$ нормы.

$\sin_p(x)=\frac{a}{(a^p+b^p)^{1/p}},\ \cos_p(x)=\frac{b}{(a^p+b^p)^{1/p}}$

Чтож, я обещал картинки? Да будут картинки! Отправимся же наконец в царство подпольной тригонометрии.

Подполье

Наша первая остановка косинус для Манхэттенской метрики, мы построили его для множества углов: $x\in[0,\pi/2]$ . Для удобства я также построил классический "легальный" косинус.

Что лично меня удивило в этом новом косинусе, это его невыпуклость (или возможно более точно "not concaveness") на заданном интервале. С удовольствием почитаю Ваш комментарий по вопросу: "почему выпуклость могла потеряться?".

Что-нибудь более периодическое?

Кстати, формулы приведения похоже работают как раньше.

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

А что там с тангенсом?

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

Продолжим наши развлечения, построим косинус для множества различных метрик.

Добавим точек:

Вывод

И напоследок. Вызывая в вашем любимом ~~файлообменнике~~ языке программирования встроенную функцию Cos(), помните, что вы обречены получить в ответ только легальную, проверенную временем, всеми любимую $\cos_2()$ . И только те, кто решился на отчаянный шаг войти в ~~кастом~~ подполье, найдут для себя что-то новое и удивительное).

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

Для любителей посмотреть в код: https://github.com/shappiron/Lp_trigonometry

Подробнее..

Категории: Метрики , Математика , Песочница , Тригонометрия , Разное

Перевод Как решать упрямые уравнения?

20.05.2021 20:12:40 |

Автор: admin

Учителя математики сотни лет мучили учеников, загоняя коз в поля странной формы. Из этой статьи вы узнаете, почему одна задачка о пасущихся козах уже более века не даёт покоя математикам. Если вы когда-нибудь сдавали экзамен по математике, то наверняка вам задавали задачку про пасущуюся козу. Её смысл заключается в следующем: рассеянный фермер оставил козу привязанной к столбу у забора или сарая, и теперь она подъедает вокруг себя всю траву, до которой может дотянуться. Ваша задача рассчитать общую площадь, на которой может пастись коза. Давно ли вы проходили математическое тестирование?

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

В самом простом варианте задачи голодное животное привязывается к боковой стенке длинного сарая верёвкой фиксированной длины.

Обычно в таких задачах просят определить площадь области, в которой может перемещаться коза на верёвке. Как выглядит эта область?

Натягивая верёвку, коза описывает полукруг и, соответственно, может дотянуться до всего, что находится внутри этого полукруга. Вот формула площади круга:

Значит, площадь полукруга в два раза меньше:

$A = \frac12r^2$

При длине верёвки 4 коза выщипает площадь (в квадратных единицах), равную

$A = \frac12 4^2 = 8$

Решение этой элементарной задачи не представляет особой сложности ни для математика, ни для козы, поэтому давайте сделаем её интереснее. Что, если коза будет привязана к боковой стенке сарая квадратной формы?

Предположим, что длина верёвки и длина стороны сарая равны 4 и что верёвка прикреплена к середине одной из сторон. На какой площади теперь может пастись коза? Коза по-прежнему может пастись в том же полукруге, что и в первой задаче.

Но она также может заходить за угол сарая. Дойдя до угла, коза может использовать ещё два участка верёвки, то есть может выщипать ещё четверть круга радиусом 2 по обе стороны сарая.

Коза может попасть в полукруг радиуса 4 плюс ещё в две четверти круга радиуса 2, общая площадь которых в квадратных единицах составляет

$A = \frac12 4^2 + \frac14 2^2 + \frac14 2^2 = 10$

Задачу можно усложнить, изменив форму препятствия. Я видел задачи с козами, привязанными к треугольникам, шестиугольникам и даже к вогнутым формам.

Также можно задать новое условие математической задачи, изменив её вопрос на противоположный: не указывать длину верёвки и просить найти площадь, а указать площадь и просить найти длину верёвки.

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

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

Если длина верёвки больше 2 единиц, коза сможет обогнуть угол.

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

Нам необходимо найти длину верёвки, при которой общая площадь будет составлять 50 квадратных единиц. Математически это можно выполнить следующим образом: подставить в формулу площадь, равную 50, и решить это уравнение относительно r. Но для каждой области имеется своя формула расчёта площади. Какую же использовать?

Для того чтобы это выяснить, проведём небольшие вычисления. Если r 2, площадь области составит

$A = \frac12r^2$

Самая большая площадь будет при r = 2, то есть общая площадь составит

$A = \frac12 2^2 = 2 6,28$

Это меньше 50, поэтому нам нужно более 2 единиц верёвки.

Если 2 < r 6, мы получаем полукруг плюс две четверти круга. Радиус полукруга равен r, а радиус четверти круга равен r 2, так как для того, чтобы добраться до угла, потребуется две единицы верёвки, а оставшаяся верёвка выступает в качестве радиуса четверти круга с центром в углу сарая.

Площадь этого полукруга равна

$\frac12r^2$

А площадь каждой четверти круга равна

$\frac14(r 2)^2$

Просуммировав выражения, получим общую площадь:

$\begin{aligned}A&=\frac{1}{2} \pi r^{2} +\frac{1}{4}\pi (r-2)^{2} + \frac{1}{4}\pi (r-2)^{2}\\[1pt] \\A &=\frac{1}{2} \pi r^{2} + \frac{1}{2}\pi (r-2)^{2}.\end{aligned}$

Наибольшую возможную площадь мы получим при r = 6, что даёт

$A = \frac12 6^2 + \frac12 4^2 = 26 81,68$

квадратных единиц. Поскольку 50 < 26, это означает, что значение r, дающее 50 квадратных единиц площади, должно быть меньше 6.

Знание того, что значение r должно быть от 2 до 6 единиц, снимает вопрос о том, какую формулу для расчёта площади нужно использовать: если 2 < r 6, площадь

$A = \frac12r^2 + \frac12(r 2)^2$

Чтобы найти точное значение r, которое даст 50 квадратных единиц площади, составим такое уравнение:

$50 = \frac{1}{2}r^2 + \frac{1}{2}(r 2)^2.$

Видите, я был прав, говоря, что перевёрнутую задачу решать сложнее, чем оригинальную: вместо того чтобы просто вычислить площадь, которую может выщипать коза, нам нужно решить уравнение, чтобы определить длину верёвки. Для этого нужно выделить r. Чтобы перенести r в одну сторону уравнения и узнать, таким образом, его точное значение, используем арифметические и алгебраические методы.

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

а затем воспользуемся формулой для решения квадратных уравнений. Немного алгебры и арифметики делают своё дело.

$50 = \frac{1}{2}r^2 + \frac{1}{2}(r 2)^2$ $\frac{100}{\pi} = r^2 + (r 2)^2$ $\frac{100}{\pi} = 2r^2 4r + 4$ $0 = 2r^2 4r + 4 \frac{100}{\pi}.$

Возможно, это не самое красивое математическое выражение в мире, но это всего лишь квадратное уравнение, с помощью которого можно найти точное значение r. Получаем ответ:

Поскольку мы смогли выделить r в уравнении, теперь мы точно знаем, какой длины должна быть верёвка, чтобы получить площадь в 50 квадратных единиц. (Обратите внимание, что найденное нами значение r, как и предполагалось, находится в пределах от 2 до 6.)

Думаете, это самая заковыристая задача с козой у сарая? Как бы не так! Математики обнаружили, что задача становится ещё более сложной, если поместить козу внутрь сарая.

Поместим козу внутрь квадратного сарая с длиной стороны 4 и прикрепим верёвку к середине стены. Какой длины должна быть верёвка, чтобы коза могла выщипать половину площади внутри сарая?

Как было сказано выше, часть проблемы заключается в том, что форма области зависит от значения r. Чтобы получить половину площади квадрата, нужно, чтобы значение r было больше половины длины стороны сарая, но меньше полной длины стороны, что даёт нам примерно такую область.

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

Начнём с треугольников. Согласно теореме Пифагора длины катетов в каждом правильном треугольнике равны

$\sqrt{r^{2}-4}$

Таким образом, площадь одного из треугольников равна

$\frac{1}{2}2\sqrt{r^{2} 4}=\sqrt{r^{2} 4}$

Поэтому суммарная площадь обоих треугольников равняется

$2\sqrt{r^{2}-4}$

Перейдём к круговому сектору.

Площадь сектора равняется

$A = \frac12r^2$

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

Применяя теорему косинусов к равнобедренному треугольнику со сторонами r, r и 4, получаем:

$4^2 = r^2 + r^2 - 2r^2\cos{\theta},$

и это уравнение можно решить для cos:

$\cos{\theta} = \frac{2 r^{2}-16}{2 r^{2}} = \frac{r^{2}-8}{r^{2}}$

Чтобы выделить , нужно взять обратный косинус, или арккосинус, от обеих сторон уравнения. Это даёт:

$\theta = \arccos{\left(\frac{r^{2}-8}{r^{2}}\right)}$

Теперь у нас имеется угол , выраженный через r, поэтому площадь нашего сектора можно выразить только в r:

$A = \frac12r^2\theta$ $A = \left(\frac{r^{2}-8}{r^{2}}\right) + 2\sqrt{r^{2}-4}$

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

Мы получили формулу для расчёта площади области, в которой может перемещаться коза внутри квадрата, полностью через r. Теперь нужно просто найти значение r, дающее козе доступ к половине площади. Площадь всего квадрата равна 16, поэтому нам остаётся только подставить в наше уравнение A = 8, решить его относительно r, и дело сделано.

$8 = \left(\frac{r^{2}-8}{r^{2}}\right) + 2\sqrt{r^{2}-4}$

Однако возникает одна небольшая проблема: это уравнение невозможно решить относительно r.

Вернее, это уравнение невозможно решить точно относительно r. Для приблизительного определения значения r можно использовать калькулятор (получится примерно 2,331), но выделить r в нашем уравнении нельзя. Сочетание в уравнении тригонометрических и полиномиальных функций создаёт непреодолимые препятствия для его точного разрешения относительно r.

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

Эта особенность трансцендентных функций лежит в основе известной проблемы XIX века о пасущейся козе, помещённой внутрь круглого сарая. Как и в нашей задаче с квадратным сараем, задача XIX века состояла в том, чтобы определить, какой длины должна быть верёвка, чтобы коза могла выщипать половину области.

Доступная для козы область имеет форму "линзы" два сложенных вместе круговых сегмента.

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

Подобное упрямство уравнения сродни упрямству козы, не находите? Более 100 лет математики пытались найти точное решение головоломки "коза в круге", но только в прошлом году немецкий математик наконец её разгадал. Для поиска точного значения r он использовал методы комплексного анализа области математики, далёкой от геометрии кругов и квадратов, на которой основывается большинство задач о козах. И, хотя применение такого продвинутого математического инструмента, как контурный интеграл, для определения длины верёвки, к которой привязана коза, может показаться излишеством, всегда чувствуешь математическое удовлетворение после того, как делаешь то, что раньше считалось невозможным. И всегда существует вероятность, что эти новые методы, даже если они возникли в результате изучения детской задачки о козе, могут привести к открытиям, выходящим за границы деревенского сарая.

Упражнения

1. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 8 единиц за пределами сарая, какова площадь области, которую может выщипать коза?

2. Если коза привязана к углу квадратного сарая с длиной стороны 4 верёвкой длиной 8 за пределами сарая, какова площадь области, которую может выщипать коза?

3. Предположим, что коза находится внутри равностороннего треугольника со стороной 4 и привязана к одной из его вершин. Какой длины должна быть верёвка, чтобы коза могла выщипать половину площади треугольника?

4. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 10 за пределами сарая, какова площадь области, которую может выщипать коза?

Ответ на задачу 1

Область состоит из полукруга радиуса 8, двух четвертей окружности радиуса 6 и двух четвертей окружности радиуса 2. Поскольку 8 равно половине периметра сарая, два полукруга за сараем пересекаются в середине.

$\frac12 8^2 + \frac12 6^2 + \frac12 2^2 = 52$

Эта площадь состоит из трёх четвертей площади окружности радиуса 8 и двух четвертей площади окружности с радиусом 4.

И она равна

$\frac{1}{2} 8^2 + \frac12 6^2 + \frac12 2^2= 56$

Ответ на задачу 2

Эта область состоит из трёх четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4.

И она равна

$\frac34 8^2 + \frac12 4^2 = 56$

Подумайте, что произойдёт, если длина верёвки будет равна 10.

Ответ на задачу 3

Поскольку углы равностороннего треугольника равны 60, доступная козе площадь составляет одну шестую часть круга радиуса r, площадь которой равна

$\frac16r^2$

Площадь равностороннего треугольника равна

$\frac{\sqrt{3}}{4}s^2$

Поэтому площадь треугольника с длиной стороны 4 равна

$\frac{\sqrt{3}}{4} 4^2=4\sqrt3$

Положим обе площади равными

$\frac16r^2 = \frac12 4 \sqrt3$

И с помощью этой формулы выразим r. Мы получим

$r=\sqrt{\frac{12 \sqrt{3}}{\pi}}$

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

Ответ на задачу 4

Площадь, по-видимому, состоит из полукруга радиуса 10, двух четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4. Эта площадь составляет

$\frac12 10^2 + \frac12 8^2 + \frac12 4^2 = 90$

Но последние две четверти круга пересекаются за сараем.

Это перекрытие было учтено дважды, поэтому нам нужно вычесть его площадь из 90. Область перекрытия можно представить как две шестые окружности радиуса 4 минус равносторонний треугольник со стороной 4. Площадь этой области составляет

$2 \frac16 4^2 - \frac{\sqrt{3}}{4} 4^2 = \frac{16}{3} - 4{\sqrt{3}}$

Таким образом, общая площадь равна

$90 - \left(\frac{16}{3} \pi-4 \sqrt{3}\right) = \frac{254}{3} + 4 \sqrt3$

Примечание: это пересечение было бы гораздо сложнее найти, если бы две окружности имели разные радиусы, именно поэтому так трудно найти площадь линзы, о которой говорилось выше.

Если вам интересна не только математика, но и её практические приложения, вы можете обратить внимание на курс по Data Science: область науки о данных развивается и будет актуальна как минимум в ближайшие десять лет.

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

Другие профессии и курсы

ПРОФЕССИИ

КУРС

Подробнее..

Категории: Научно-популярное , Математика , Блог компании skillfactory , Читальный зал , Занимательные задачки , Задачки , Геометрия , Тригонометрия , Skillfactory , Площади , Проблемы математики , Занимательно о математике , Задача о козе на привязи , Коза на привязи

Перевод Дискретный арктангенс в процессоре NES

06.11.2020 10:14:52 |

Автор: admin

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

Определение арктангенса: в прямоугольном треугольнике arctan вычисляет один из непрямых углов, используя в качестве входных данных длину стороны, противоположной этому углу, разделённую на длину прилежащей стороны. В случае Star Versus сторонами треугольника являются расстояния X/Y между двумя объектами, например, снарядом и кораблём, а угол это направление, в котором должен двигаться первый, чтобы достичь второго.

Поначалу арктангенс нужен был для того, чтобы понять, когда один корабль ударяет по другому своим мечом. Мечи не имеют собственной информации о коллизиях, из-за необходимости анимаций они существуют исключительно как артефакты рендеринга. Поэтому они используют код, распознающий коллизии между двумя кораблями с увеличенным хитбоксом для учёта радиуса удара меча. Это позволяет движку экономить драгоценное время процессора, вычисляя дельты X/Y всего один раз. Однако для этого нужно гарантировать, что размахивающий мечом смотрит в нужном направлении, а не совершает удар в сторону от цели, и здесь нам пригождается арктангенс.

Реализация

Важным упрощением в Star Versus является то, что направление не непрерывно, а дискретно. Объекты могут двигаться только в 24 возможных направлениях. Перемещение вправо соответствует 0, вверх 6, влево 12, а вниз 18. Каждый инкремент направления представляет собой угол в / 24 радиан. ( это фундаментальная константа окружности, равная 6.2831853)

После выполнения кода распознавания коллизий у нас уже есть дельты позиций X/Y для функции arctan. Нам достаточно одних знаков, чтобы понять, в каком из четырёх квадрантов находится результат, поэтому остальная часть кода должна выяснить при помощи абсолютных значений дельт, какое из 6 направлений квадранта является правильным.

Процессор 6502 слишком медленный, чтобы вычислять arctan при помощи стандартных способов, например рядов Тейлора, но поскольку результат должен быть правильным в рамках / 24, мы можем сжульничать и использовать аппроксимацию. В целом план заключался в том, чтобы сначала найти соотношение X/Y, затем представить набор линий, разделяющих пространство в соответствии с возможными направлениями, затем найти наклон этих линий, и сравнить соотношение, чтобы понять, к какому из направлений угол ближе всего.

Нам нужно быть внимательными к тем углам, которые равномерно делят пространство на области, окружающие направления, которые должен возвращать arctan. Это /48, 3/48, 5/48, 11/48. Тангенс каждого из них равен:

tan( 1 * / 48) = 0.131652497587 tan( 3 * / 48) = 0.414213562373 tan( 5 * / 48) = 0.767326987979 tan( 7 * / 48) = 1.30322537284 tan( 9 * / 48) = 2.41421356237 tan(11 * / 48) = 7.59575411273

Поскольку у процессора 6502 нет команд умножения и деления, дробные значения нежелательны. Однако у него есть битовые сдвиги, с помощью которых можно малозатратно делить или умножать на 2. К счастью, три значения тангенсов выше диагонали довольно близки к 1.25, 2.5 и 7.5, а эти значения довольно легко найти при помощи битовых сдвигов [1]. Другие углы ниже диагонали просто являются их отражениями, поэтому мы можем найти их, поменяв местами X и Y.

Сравнивая соотношение X/Y с этими значениями, мы получим номер области от 0 и 3. Будет ли эта область находиться над диагональю, зависит от того, поменяли ли мы местами X и Y. Вот псевдокод алгоритма:

small, large = x, yif y < x:    small, large = y,xhalf = small / 2// compare to 2.5 slopeif small * 2 + half > large:    // compare to 1.25    quarter = half / 2    if small + quarter > large:        region = 1    else:        region = 0else:  // compare to 7.5  if small * 8 - half > large:    region = 3  else:    region = 2// Use region, whether X/Y were swapped, and quadrant in a lookup table.

Полный код на ассемблере выложен здесь вместе с юнит-тестами, использующими nes_unit_testing.

Применение

После реализации arctan он применяется во всех аспектах игры. Кроме коллизий мечей нужно также рассчитывать движение бомб, которые должны попадать в свои цели. Для этого они периодически проверяют направление в сторону движения к другому кораблю, и изменяя его, если отклонились от курса [2]. Почти так же arctan используется при стрейфе по кругу, поворачивая корабль в направлении другого корабля, пока он движется вбок, создавая круговое движение. Хотя реализация arctan неидеальна, на практике погрешность достаточно мала, поэтому самонаведение бомб и круговой стрейф работают хорошо.

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

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

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

Примечания

[1] Умножение меньшего числа вместо деления большего имеет и ещё одно полезное преимущество оно позволяет избежать числовых искажений, снижая вероятность ошибок.

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

Подробнее..

Категории: Разработка игр , Оптимизация кода , Тригонометрия , Nes , Nintendo entertainment system , Хаки

	Русский
	English

Тригонометрия

Перевод Обучение технологии ray-casting. Часть 2

Ограничения ray-casting

Шаг 1: Создание окружения

Шаг 2. Определение атрибутов проекции

Конец второй части

Подпольная тригонометрия различных метрик

Небольшая, но чертовски интересная преамбула

Многоликость гипотенузы

К сферам

К тригонометрии

Подполье

Вывод

Перевод Как решать упрямые уравнения?

Упражнения

Перевод Дискретный арктангенс в процессоре NES

Реализация

Применение

Примечания

Категории

Последние комментарии