Bezier, отсекающий

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

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

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

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

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

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

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

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

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

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

Существует много статей научного исследования о выполнении bezier отсечение:

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

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

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

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

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

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

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

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