Отсечение Безье

Question

Я пытаюсь найти / создать алгоритм для вычисления пересечения (новый заполненный объект) двух произвольно заполненных 2D-объектов. Объекты определяются с использованием линий или кубических безье и могут иметь отверстия или самопересекающиеся. Мне известно о нескольких существующих алгоритмах, делающих то же самое с полигонами, перечисленными здесь . Тем не менее, я хотел бы поддержать Безье, не подразделяя их на полигоны, и выходные данные должны иметь примерно те же контрольные точки, что и входные данные в областях, где нет пересечений.

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

Answer 1

Я нашел следующую публикацию лучшей информацией о Безье Клиппинге:

Т. В. Седерберг, УБЯ, Заметки по курсу «Компьютерное геометрическое проектирование»

Глава 7, в которой говорится о пересечении кривой, доступна онлайн. В нем изложены 4 различных подхода к поиску пересечений и подробно описывается отсечение Безье:

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Answer 2

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

Вы можете переписать кривые Безье как набор из двух бивариантных кубических уравнений, например:

• ∆x = ax₁ * t₁ ^ 3 + bx₁ * t₁ ^ 2 + cx₁ * t₁ + dx₁ - ax₂ * t₂ ^ 3 - bx₂ * t₂ ^ 2 - cx₂ * t₂ - dx₂
• ∆y = ay₁ * t₁ ^ 3 + by₁ * t₁ ^ 2 + cy₁ * t₁ + dy₁ - ay₂ * t₂ ^ 3 - by₂ * t₂ ^ 2 - cy₂ * t₂ - dy₂

Очевидно, что кривые пересекаются для значений (t₁, t₂), где ∆x = ∆y = 0. К сожалению, это осложняется тем, что трудно найти корни в двух измерениях, и приближенные подходы имеют тенденцию (как другой писатель положил) взорвать.

Но если вы используете целые числа или рациональные числа для своих контрольных точек, то вы можете использовать базы Гребнера , чтобы переписать ваши полиномы порядка 3-го порядка в (возможно, до порядка) Многовариантный многочлен. После этого вам просто нужно найти свои корни (например, t₂) в одном измерении и вставить результаты обратно в одно из ваших исходных уравнений, чтобы найти другое измерение.

Burchburger предлагает дружественное для мирян введение в основы Гребнера под названием " Основы Грёбнера: краткое введение для теоретиков систем ", которое было очень полезно для меня. Погугли это. Другая полезная статья была под названием « Быстрое точное сглаживание кубических кривых Безье и траектории смещения » Т. Ф. Хейна, в которой есть много полезных уравнений для кривых Безье, в том числе как найти полиномиальные коэффициенты для уравнения х и у.

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

Однако, одно из преимуществ этого метода заключается в том, что он не зависит от рекурсивного разбиения кривой, и задача становится простой одномерной задачей поиска корней, которая не проста, но хорошо документирована. Основным недостатком является то, что вычисление базисов Гребнера является дорогостоящим и становится очень громоздким, если вы имеете дело с полиномами с плавающей запятой или используете кривые Безье более высокого порядка.

Если вы хотите, чтобы какой-нибудь законченный код на Хаскеле нашел пересечения, дайте мне знать.

Answer 3

Я написал код, чтобы сделать это давным-давно. Проект, над которым я работал, определил двухмерные объекты, используя кусочные границы Безье, которые были сгенерированы как пути PostScipt.

Подход, который я использовал, был:

Пусть кривые p, q определены контрольными точками Безье. Они пересекаются?

Вычислить ограничивающие рамки контрольных точек. Если они не перекрываются, то две кривые не пересекаются. В противном случае:

p.x (t), p.y (t), q.x (u), q.y (u) являются кубическими полиномами при 0 <= t, u <= 1.0. Квадрат расстояния (p.x - q.x) ** 2 + (p.y - q.y) ** 2 является полиномом от (t, u). Используйте Ньютона-Рафсона, чтобы попытаться решить это за ноль. Откажитесь от любых решений за пределами 0 <= t, u <= 1,0 </p>

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

Если N-R не сходится в решении, разделите одну кривую (скажем, p) на две кривые pa, pb при t = 0,5. Это легко, это просто вычисление средних точек, как показано в связанной статье. Затем рекурсивно проверьте (q, pa) и (q, pb) пересечения. (Обратите внимание, что на следующем уровне рекурсии q стало p, поэтому p и q поочередно разделяются на каждый слой рекурсии.)

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

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

Когда вы найдете пересечение, вы не закончите, потому что кубические кривые могут иметь несколько пересечений. Таким образом, вы должны разбить каждую кривую в точке пересечения и рекурсивно проверить наличие большего взаимодействия между (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Существует ряд научных исследований, посвященных вырезке Безье:

http://www.andrew.cmu.edu/user/sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola/html/research_rr.html

Я рекомендую интервальные методы, потому что, как вы описываете, вам не нужно делить на полигоны, и вы можете получить гарантированные результаты, а также определить собственную произвольную точность для набора результатов. Для получения дополнительной информации об интервальном рендеринге вы также можете обратиться к http://www.sunfishstudio.com