recorte de Bezier

Question

Estoy tratando de encontrar/hacer un algoritmo para calcular la intersección (un nuevo objeto lleno) de dos objetos 2D llenos arbitrarios. Los objetos se definen usando líneas o beziers cúbicos y pueden tener agujeros o autointersecarse. Conozco varios algoritmos existentes que hacen lo mismo con los polígonos, listed here. Sin embargo, me gustaría admitir beziers sin subdividirlos en polígonos, y la salida debería tener aproximadamente los mismos puntos de control que la entrada en áreas donde no hay intersecciones.

Esto es para un programa interactivo para hacer algunos CSG, pero el recorte no necesita ser en tiempo real. He buscado por un tiempo pero no he encontrado buenos puntos de partida.

Answer 1

me encontré con la siguiente publicación para ser el mejor de información sobre Bézier de recorte:

T. W. Sederberg, BYU, Computer Aided Geometric Design Notes curso

Capítulo 7 que habla de curva de intersección está disponible en línea. Describe 4 enfoques diferentes para encontrar intersecciones y describe el recorte de Bezier en detalle:

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

Answer 2

Hay una serie de trabajos de investigación académica en hacer Bézier de recorte:

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

recomiendo los métodos de intervalo porque como usted describe, no lo hace tiene que dividirse en polígonos, y puede obtener resultados garantizados, así como definir su propia precisión arbitraria para el conjunto de resultados. Para obtener más información sobre la representación de intervalo, también puede consultar http://www.sunfishstudio.com

Answer 3

Escribí el código para hacer esto hace mucho, mucho tiempo. El proyecto en el que estaba trabajando definió objetos 2D utilizando límites Bezier por partes que se generaron como rutas PostScipt.

El enfoque que utilizamos fue:

Let curvas p, q, ser definido por los puntos de control de Bézier. ¿Se cruzan?

Calcule los cuadros delimitadores de los puntos de control. Si no se superponen, entonces las dos curvas no se cruzan. De lo contrario:

p.x (t), p.y (t), q.x (u), q.y (u) son polinomios cúbicos en 0 < = t, u < = 1.0. La distancia al cuadrado (p.x - q.x) ** 2 + (p.y - q.y) ** 2 es un polinomio en (t, u). Usa Newton-Raphson para tratar de resolver eso para cero. Deseche cualquier solución fuera de 0 < = t, u < = 1.0

N-R puede que converja o no. Las curvas pueden no cruzarse, o N-R puede explotar cuando las dos curvas son casi paralelas. Así que corte N-R si no está convergiendo después de un número arbitrario de iteraciones. Este puede ser un número bastante pequeño.

Si N-R no converge en una solución, divida una curva (por ejemplo, p) en dos curvas pa, pb en t = 0.5. Esto es fácil, solo está midiendo puntos medios, como muestra el artículo vinculado. Luego pruebe recursivamente (q, pa) y (q, pb) para las intersecciones. (Tenga en cuenta que en la siguiente capa de recursividad q se ha convertido en p, así que p y q se dividen alternativamente en cada capa de la recursión.)

La mayoría de las llamadas recursivas regresan rápidamente porque los cuadros delimitadores no se superponen .

Tendrá que cortar la recursividad a una profundidad arbitraria, para manejar casos extraños donde las dos curvas son paralelas y no tocan del todo, pero la distancia entre ellas es arbitrariamente pequeña, quizás solo 1 ULP de diferencia .

Cuando encuentra una intersección, no ha terminado, porque las curvas cúbicas pueden tener múltiples cruces.Por lo tanto, debe dividir cada curva en el punto de intersección y buscar recursivamente más interrecciones entre (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Sé que estoy en riesgo de ser redundante, pero estaba investigando el mismo problema y encontré una solución que había leído en documentos académicos pero que no había encontrado una solución de trabajo.

Puede volver a escribir las curvas de Bézier como un conjunto de dos ecuaciones cúbicas bi-variable así:

• ? X = t₁ ax₁ *^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₂

Obviamente, las curvas se cortan para valores de (t₁, t₂ $), donde? x = Dy = 0. por desgracia, esto es complicado por el hecho de que yo Es difícil encontrar raíces en dos dimensiones, y los enfoques aproximados tienden a explotar (como lo dijo otro escritor).

Pero si estás usando números enteros o números racionales para sus puntos de control, entonces se puede utilizar bases de Groebner a reescribir sus bi-variable de pedidos 3 polinomios en una (posiblemente-up-to-order-9- por lo tanto, tu-nueve-posible-intersecciones) polinomio monovariado. Después de eso, solo necesita encontrar sus raíces (por ejemplo, t₂) en una dimensión, y volver a conectar sus resultados en una de sus ecuaciones originales para encontrar la otra dimensión.

Burchburger tiene una introducción sencilla a las Bases de Groebner llamada "Bases de Gröbner: una breve introducción para los teóricos de sistemas" que fue muy útil para mí. Buscalo en Google. El otro documento que fue útil fue uno llamado "Aplanamiento rápido y preciso de la trayectoria cúbica de Bézier y curvas de desplazamiento" de TF Hain, que tiene muchas ecuaciones de utilidad para curvas de bezier, que incluyen cómo encontrar los coeficientes polinomiales para la xey ecuaciones.

En cuanto a si el recorte de Bezier ayudará con este método en particular, lo dudo, pero el recorte de bezier es un método para reducir las intersecciones, no para encontrar una respuesta final (aunque posiblemente aproximada) de dónde está . Se utilizará mucho tiempo con este método para encontrar la ecuación monovariable, y esa tarea no se vuelve más fácil con el recorte. Encontrar las raíces es, por comparación, trivial.

Sin embargo, una de las ventajas de este método es que no depende de la subdivisión recursiva de la curva, y el problema se convierte en un simple problema unidimensional de búsqueda de raíz, que no es fácil, pero está bien documentado. La principal desventaja es que la computación de las bases de Groebner es costosa y se vuelve muy difícil de manejar si se trata de polinomios de coma flotante o el uso de curvas de Bezier de orden superior.

Si quieres un código terminado en Haskell para encontrar las intersecciones, házmelo saber.