Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Как найти пересечение луча с телом вращения, заданным полиномом

Как найти пересечение луча с телом вращения, заданным полиномом

Страницы: 1 2 Следующая »
LПостоялецwww10 июня 201821:18#0
Всем привет.

Задачка такова: имеется полином, скажем, 4 степени (возможно, в будущем, будет 5 степень). Этот полином задаёт тело вращения:

polysurface2 | Как найти пересечение луча с телом вращения, заданным полиномом

В данном случае это x^2*0.82 + x^4*-0.05 ,(но в задаче может быть больше членов, хотя, сейчас можно остановиться конкретно на такой форме)
При чём меня интересуют только конечные значения аргумента полинома! То есть не надо находить все все возможные пересечения, находим только в диапазоне X от 0 до понятного радиуса. На картинке максимальный радиус поверхности == 4.

Необходимо найти ближайшую точку точку пересечения (и определить сам факт нахождения пересечения) с лучом (линией).

Аналитически, конечно, это не посчитать, потому требуется численное итеративное решение задачи. Первый тупой вариант я конечно сам осилил сделать, запилил аналог метода Ньютона (точка пересечения луча обозначена синим кубиком на первой картинке):
1. Находим первое приближение решения - пересекаю луч с нулевой горизонтальной плоскостью, отсюда нахожу значение функции и получаю первую точку на поверхности.
2. итеративно повторяю следующее - нахожу нормаль к поверхности в точке, пересекаю луч заданный нормалью и плоскостью, шагаю в точку пересечения, пока предыдущее и новое значение функции не станут в шаге отличаться на < epsilon.

Если трассировать лучом, направленным примерно вдоль веритикальной оси, то решение находится достаточно быстро и просто, плюс ко всему я точно знаю, что полином гарантированно пересекается.
Однако, очевидно, такой метод не сможет найти все корни и, соответственно, не сможет выбрать именно ближайшее пересечение:
plot_bug | Как найти пересечение луча с телом вращения, заданным полиномом

и не сможет точно определить сам факт пересечения:
plot_bug2 | Как найти пересечение луча с телом вращения, заданным полиномом

Всякие тупые варианты я уже обдумывал, вроде "протрассировать в 3D методом хорд" или "вычесть из полинома линию, найти корни, побить радиально поверхность на диапазоны найденными корнями, отсканить каждый диапазон моим же первичным алгоритмом". Но это выглядит тяжеловато )

Правка: 12 июня 2018 21:50

MrShoorУчастникwww10 июня 201823:43#1
L
Можно методом Ньютона, но нужно знать, откуда его запускать.
На практике же для полинома N-ой степени у меня очень хорошо сработал бинарный поиск (лучше чем метод Ньютона, потому что для Ньютона надо считать не только значение функции но и значение производной. В итоге на бинарный поиск у меня уходило примерно в 2 раза больше вычислений, но сами вычисления дешевле).
Суть метода такова.
Для того, чтобы найти корни на участке функции нам достаточно найти экстремумы функции. Если соседние экстремумы лежат по разную сторону от оси X (т.е. разный знак у Y компоненты), то между экстремумами гарантированно есть корень. Поскольку участок функции между экстремумами монотонный, то бинарным поиском мы можем легко найти корень с нужной нам точностью.
Собственно чтобы найти экстремумы нам надо взять производную, и найти её корни. А поскольку у тебя полином N-ой степени, то каждая производная будет понижать эту степень на единицу, а значит ты гарантированно можешь найти все корни полинома.

Правка: 10 июня 2018 23:43

LПостоялецwww11 июня 20180:03#2
MrShoor
Я и написал, что юзаю метод Ньютона, модифицированный мной для 3D случая.  Расчёт производной происходит вполне быстро и с ней я во многих случаях (теоретически) могу  намного быстрее дошагать до нужного решения, так что быть может и не факт, что бинарный поиск будет заруливать.


Насчёт экстремумов я думал, но я не особо математик, потому могу не знать какого-то особо классного метода, может есть что-то круче? :D  А то решение кажется слишком "влобным" и кажется, что должно быть что-то веселее. Да и выглядит как вдвойне корявость - сначала итеративно ищем экстремумы, потом итеративно ищем по куче отрезков пересечения.

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

Правка: 11 июня 2018 0:13

SuslikМодераторwww11 июня 20185:33#3
L
в таких случаях обычно не обойтись без грубого раннего поиска с обычным фиксированным шагом. просто делишь свой отрезок на N частей(например, 10) и дальше запускаешь метод хорд/ньютона/бинарный поиск на тех отрезках, у которых один конец лежит внутри, второй — снаружи.

Правка: 11 июня 2018 5:33

MrShoorУчастникwww11 июня 201819:11#4
L
Задача сводится не к каким-то модифицированным алгоритмам, а просто к поиску корней полинома N-ой степени.
Твое тело вращения - это вот такой полином:
poly | Как найти пересечение луча с телом вращения, заданным полиномом
где r собственно расстояние от нулевой точки (или радиус)
Прямую же можно задать параметрически:
line | Как найти пересечение луча с телом вращения, заданным полиномом
Легко видно, что радиус выражается через t:
r_t | Как найти пересечение луча с телом вращения, заданным полиномом
И в целом тебе надо найти значение аргумента функции полинома, удовлетворяющее условию:
pz_t | Как найти пересечение луча с телом вращения, заданным полиномом

Так как у тебя r(t) подкоренное выражение, то нам надо избавится от него, отделив нечетные степени по одну сторону от равенства и возведя в квадрат (не забыв потом проверить корни). Ну а после подстановки в выражение r(t) и f(r) уравнения твоей прямой ты получишь просто уравнение степени N, которое и решается обычными методами. Как-то так чтоль.

Правка: 11 июня 2018 19:24

MrShoorУчастникwww11 июня 201819:28#5
А можно даже не избавляться от квадратов, а искать значения для r исходного полинома, а потом для найденных корней r решить уравнение r(t). С точки зрения программирования так будет даже проще (но точность предсказать сложнее).
Тьфу, нельзя же так. У нас же f(r)=P.z*t+P0.z. Так что в любом случае от корней избавляться надо будет.

Правка: 11 июня 2018 20:34

LПостоялецwww11 июня 201823:20#6
Suslik
MrShoor
Ок, спасибо, я понял.

Suslik
>просто делишь свой отрезок на N частей(например, 10) и дальше запускаешь метод хорд/ньютона/бинарный поиск на тех отрезках, у которых один конец лежит внутри, второй — снаружи.
sine_plot | Как найти пересечение луча с телом вращения, заданным полиномом
Я ведь правильно понимаю, что при таком нарезании (вертикальными красными линиями) я не смогу, конечно же, понять, в каких именно отрезках есть корни. Это как-то хендлится какими-то убер красивыми алгоритмами?  У меня интуиция подсказывает, что нельзя нарезать "правильно" и придётся страдать, подбирать под частную задачу очередную хитрую и корявую нарезку (что фу и не надо)? 

Быть может лучше тогда методом Ньютона шагать от начала до первого минимума, потом продолжать с него искать до второго и т.п., пока не выйду за  разрешенный радиус. Это выглядит гарантированней, чем нарезка с непонятной частотой.

MrShoorУчастникwww11 июня 201823:41#7
L
> Быть может лучше тогда методом Ньютона шагать от начала до первого минимума
Эм.. а как ты Ньютоном шагаешь до первого минимума то? Ньютон же он корни ищет.
DelfigamerПостоялецwww12 июня 20180:09#8
MrShoor
Ньютон по производной?
MrShoorУчастникwww12 июня 20180:26#9
Delfigamer
> Ньютон по производной?
А корни производной как найти?
we need to go deeper
SuslikМодераторwww12 июня 20184:02#10
L
> Я ведь правильно понимаю, что при таком нарезании (вертикальными красными
> линиями) я не смогу, конечно же, понять, в каких именно отрезках есть корни.
> Это как-то хендлится какими-то убер красивыми алгоритмами?
для полиномов — да. их можно дифференцировать до потери сознания, пока не получишь полином первой степени. его корень будет экстремумом полинома второй степени, корни которого гарантированно будут слева и справа от него. эти корни могут быть экстремумами полинома третьей степени, корни которого будут также между ними. корни полинома третьей степени в свою очередь могут быть экстремумами четвёртой степени, между которыми могут быть корни пятой степени, которые могут быть экстремумами шестой, и так далее.. нутыпонил. но на практике я не встречал, чтобы так делали, потому что обычно бывают не совсем полиномы, а с делением или с квадратным корнем каким-нибудь, и всё, привет, метод уже не прокатит.
ещё есть методы, основанные на оценке критерия липшица, где для каждой точки оценивается максимальная величина производной в её окрестности и шагается на расстояние, на котором она гарантированно не пересечёт ось х. но оценить производную на интервале может быть не так-то просто.
я не знаю красивого алгоритма поиска гарантированно всех корней. да и учитывая функции вроде tg(1/x), а ещё лучше — 1/sin(1/x), становится понятно, что в общем случае такой алгоритм едва ли будет существовать.

Правка: 12 июня 2018 4:03

MrShoorУчастникwww12 июня 20184:14#11
Suslik
> а с делением или с квадратным корнем каким-нибудь
Да ладно не прокатит. Все половинные степени выносятся по одну строну, и правая и левая часть возводятся в квадрат.
MikleМодераторwww12 июня 201814:33#12
L
> имеется полином, скажем, 4 степени (возможно, в будущем, будет 5 степень)
С чётными степенями всё ясно, график функции симметричен относительно оси Y. И что-то мне говорит, что сечение их вертикальной плоскостью (в том числе содержащей луч) будет той же степени, впрочем, надо проверить.
А как ты себе представляешь 5-ю степень? Будет две поверхности?
LПостоялецwww12 июня 201822:12#13
Mikle
> А как ты себе представляешь 5-ю степень? Будет две поверхности?
Так же как и четную функцию - возьму аргумент по модулю и будет мне симметрия. Тем более у меня так сказать функция от радиуса используется) Да, ок, только "правая" часть функции заюзается, но почему это не может быть целью? Быть может нечётными степенями у меня лучше опишется поверхность (в плане тех же вычислений - если нечётные ложатся сразу как надо, то не надо докручивать форму дополнительными членами ещё больших степеней в случае чётного аналога)

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

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

Suslik
> 1/sin(1/x)
Ой, это вообще жесть, сюда я не сунусь )

Suslik
> становится понятно, что в общем случае такой алгоритм едва ли будет
> существовать.
То есть, как я понял, магии не будет ) Придётся для каждого семейства моих полиномов вручную подбирать "тот самый" алгоритм нарезания (либо ещё чего), примерно учитывающий форму функции, и им сканить на экстремумы. И не выделываться ) Благо, я в обозримом будущем для текущей задачи я пока собираюсь юзать только полиномы вида a*x^2 + b*x^4 + c*x^6 ...  (кстати, а у такого вида полинома есть какое-то кошерное название? Было бы классно, а то сложно каждый раз объяснять какой вид полинома я имею в виду))

MrShoor
> А корни производной как найти?
> we need to go deeper
Ну вот так deeper шагать до 1 степени (или 2, там тоже минимум очевиден же) и искать рекурсивно :D Если члены не убер сложные.

Правка: 12 июня 2018 22:19

MikleМодераторwww12 июня 201822:22#14
L
> ок, только "правая" часть функции заюзается, но почему это не может быть целью?
> Быть может нечётными степенями у меня лучше опишется поверхность
Всё может быть, я просто уточнял.
Страницы: 1 2 Следующая »

/ Форум / Программирование игр / Общее

2001—2018 © GameDev.ru — Разработка игр