Безье обрезание

Question

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

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

Answer 1

я нашел следующую публикацию, чтобы быть лучшими из информации о Безье Clipping:

Т. В. Sederberg, BYU, Computer Aided геометрического дизайн курс Примечание

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

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

Answer 2

Есть целый ряд научно-исследовательских работ по ведению Безье вырезку:

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

Answer 3

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

Подход я использовал:

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

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

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). Используйте Newton-Raphson, чтобы попытаться решить это для нуля. Отменить любые решения за пределами 0 < = t, u < = 1,0

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

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

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

• =? 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. К сожалению, это осложняется тем, что i t трудно найти корни в двух измерениях, а приближенные подходы, как это делает другой писатель, взорвались.

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

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

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

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

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