Вырезка Безье

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

Т. В. Седерберг, BYU, Заметки по курсу компьютерного геометрического дизайна

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

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

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

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

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

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

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

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

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

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

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

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).

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

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.