29.09.2012 - 23:20
Я создал репо git здесь:
https://github.com/ArthurWulfWhite/Bezier-Distance/
Вы можете скачать исходные файлы в виде zip оттуда. Он также включает в себя демонстрацию, которую вы можете скомпилировать с помощью FlashDevelop. Чтобы использовать демо, откройте проект во Flash Develop и нажмите «Test Project». Во время запуска демонстрации нажмите ЛКМ, чтобы рандомизировать новую кривую Безье и новый Круг.
Удачи!
Ссылку zip трудно увидеть - просто используйте Ctrl + F и введите zip. Этот источник представляет собой пару недель исследований и программирования, надеюсь, вам понравится.
Если вы планируете рекурсивно делить Безье на сегменты и проверять наличие с ними столкновений, я предлагаю создать массив 100 100 (сетку) и поместить каждый сегмент в четыре ближайших квадрата, так что вам нужно только проверять наличие столкновений с 4/10 000 из сегментирует каждый кадр.
Я действительно думаю, что Box2d принесет пользу как программисту, так и создателю игры, поскольку существует множество скрытых небольших препятствий в создании «простого» физического движка, который делает движение немного неровным и менее плавным, чем могло бы быть.
Старый ответ: чистый путь.
Вы можете увидеть, сталкивается ли окружность с кривой Безье, проверив расстояние между расстоянием между центром окружности и ближайшей точкой на кривой.
Уравнение для расстояния (в общем)
пояснил:
Уравнение Безье:
q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))
Это может быть суммировано до (с некоторой алгеброй) - я опущу. (X, y) для удобочитаемости (они все еще точки, а не одно число)
q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start
Расстояние от точки (x, y) составляет:
sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)
Чтобы найти ближайшую точку на безье к мячу, вам нужно вывести и найти все точки, где производная равна нулю (корни). Это многочлен третьей степени, поэтому вы можете использовать закрытую формулу, но это может быть ненадежно, поскольку точность представленных на компьютере дробей с плавающей запятой может быть недостаточной. Гораздо лучше использовать Ньютона или что-то в этом роде.
Производная, для которой нужно найти корни:
Предполагая: a = начало b = контроль c = конец d = центральная точка вращения
Хитрая часть умножает эти очки, вы должны использовать точечное произведение.
Если хотите, у меня есть код для этого, и я могу поделиться им здесь в форме функции, которая просто возвращает логическое значение, если есть столкновение или нет, и угол столкновения. Некоторые проблемы могут возникнуть в наивной реализации двигателя столкновения, такого как, например, быстро движущийся шар может попасть между двумя кривыми.
Я рекомендую избегать этого сейчас, просто суммируйте коэффициенты для оси x и для оси y и сложите их.
Используйте любой надежный метод, который вы можете выбрать, например, Ньютон, чтобы найти корни, проверьте расстояние от корневых точек на Безье, 0 <= t <= 1 до центра круга и проверьте расстояние для двух концов Безье (начало и в конце) к центру круга, в зависимости от того, кто ближе, скажет, есть ли столкновение.
Если радиус меньше минимального расстояния, происходит столкновение.
Угол примерно равен углу между центром круга и ближайшей точкой на Безье.
При этом, если вы действительно хотите создать игру с физикой столкновений, я предлагаю вам просто перебрать Безье
q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))
Разделите каждую часть по центру рекурсивно до тех пор, пока она не станет достаточно маленькой, скажем, 10 пикселей или меньше, затем построите безье примерно из коробок и используйте Box2d для физики, потому что возможно, что написание всего этого кода обнаружения столкновений окажется большим время, которое не сильно улучшает игровой процесс. Использование Box2d зарекомендовало себя в бесчисленных проектах в прошлом.
Для этого я бы:
Разбейте кривую Безье на несколько отрезков и сохраните их.
Поместите все эти сегменты в выровненную по оси ограничивающую рамку для всей кривой.
Обнаружение столкновения:
1) проверьте, находится ли сфера внутри основной ограничительной рамки. если нет, нет столкновения.
2) в противном случае проверьте, не сталкивается ли какой-либо из отдельных сегментов, рассчитанных выше, со сферой. См. Статью о пересечении линии и сферы из Википедии .
РЕДАКТИРОВАТЬ: если вам нужна высокая точность и хорошая производительность, вы также можете создать основной ограничивающий прямоугольник для всей кривой, а затем разделить кривую на два сегмента (например:
[0.0 - 0.5]и[0.5 - 1.0]). Создание bouding окна для каждого из них, а затем снова разделить каждый из этих сегментов в двух сегментах (таким образом , давая[0 - 0.25],[0.25 - 0.5]и[0.5 - 0.75],[0.75 - 1.0]). Продолжайте так, пока не достигнете достаточной точности. в конце вы получитеbinary treeограничивающие прямоугольники с основным ограничивающим прямоугольником кривой в корне и отрезки линий на листьях. поиск в дереве даст вамO(log n)вместоO(n)(гдеn= количество отрезков для кривой)источник
Пересечение между линией и кривой Безье достигается математически путем деления кривой. Это означает полагаться на свойство выпуклой оболочки кривой и делить ее на более мелкие дуги с различными управляющими полигонами в стиле «разделяй и властвуй».
Эта статья освещает это до некоторой степени: http://students.cs.byu.edu/~tom/557/text/cic.pdf .
Приятно то, что алгоритм работает с любой линией, вам просто нужно применить жесткое преобразование к кривой, чтобы вы могли рассматривать вашу целевую линию как параллельную оси Ox.
Точно так же вы можете проверить по кругу и многоугольнику каждой такой дуги Безье, когда вы подразделяете дугу Безье на две суб-дуги. Окружность должна пересекать контрольный многоугольник дуги, чтобы тест с кривой на окружность имел смысл.
источник