Обрезка Безье

Question

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

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

Answer 1

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

Т.В.Седерберг, BYU, Конспекты курса компьютерного геометрического проектирования

Глава 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 в одномерный полином (возможно, до порядка 9, таким образом, ваши девять возможных пересечений).После этого вам просто нужно найти корни (скажем, t₂) в одном измерении и снова подставить результаты в одно из исходных уравнений, чтобы найти другое измерение.

У Burchburger есть доступное для непрофессионалов введение в базы Гребнера под названием «Базы Грёбнера:Краткое введение для системных теоретиков"Это было очень полезно для меня.Погугли это.Другая статья, которая оказалась полезной, называлась «Быстрое и точное выравнивание кубических траекторий Безье и кривых смещения.» от TF Hain, в котором есть множество уравнений полезности для кривых Безье, в том числе о том, как найти полиномиальные коэффициенты для уравнений x и y.

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

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

Если вам нужен готовый код на Haskell для поиска пересечений, дайте мне знать.

Answer 3

Я написал код для этого очень-очень давно.Проект, над которым я работал, определял 2D-объекты с использованием кусочных границ Безье, которые были сгенерированы как пути 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.

NR может сходиться, а может и не сходиться.Кривые могут не пересекаться, или 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