recorte de Bézier

Question

Estoy tratando de encontrar/crear un algoritmo para calcular la intersección (un nuevo objeto relleno) de dos objetos 2D rellenos arbitrarios.Los objetos se definen mediante líneas o béziers cúbicos y pueden tener agujeros o intersecarse.Soy consciente de que existen varios algoritmos que hacen lo mismo con los polígonos, listado aquí.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 que un programa interactivo haga algo de CSG, pero no es necesario que el recorte sea en tiempo real.He buscado durante un tiempo pero no he encontrado buenos puntos de partida.

Answer 1

Encontré que la siguiente publicación es la mejor información sobre el recorte de Bezier:

T.w.Sederberg, BYU, Notas del curso de diseño geométrico asistido por computadora

El capítulo 7 que habla sobre la intersección de curvas está disponible en línea.Describe 4 enfoques diferentes para encontrar intersecciones y describe Bezier Clipping en detalle:

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

Answer 2

Sé que corro el riesgo de ser redundante, pero estaba investigando el mismo problema y encontré una solución que había leído en artículos académicos pero para la que no había encontrado una solución funcional.

Puedes reescribir las curvas de Bézier como un conjunto de dos ecuaciones cúbicas bivariadas como esta:

• ∆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₂

Obviamente, las curvas se cruzan para valores de (t₁,t₂) donde ∆x = ∆y = 0.Desafortunadamente, es complicado por el hecho de que es difícil encontrar raíces en dos dimensiones, y los enfoques aproximados tienden (como dijo otro escritor) a fracasar.

Pero si estás usando números enteros o racionales para tus puntos de control, entonces puedes usar Bases de Groebner para reescribir sus polinomios bivariados de orden 3 en un polinomio monovariado (posiblemente de hasta orden 9 y, por lo tanto, sus nueve posibles intersecciones).Después de eso, solo necesitas encontrar tus raíces (por ejemplo, t₂) en una dimensión y volver a conectar tus resultados en una de tus ecuaciones originales para encontrar la otra dimensión.

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

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

Sin embargo, una de las ventajas de este método es que no depende de subdividir recursivamente la curva, y el problema se convierte en un simple problema unidimensional de búsqueda de raíces, lo cual no es fácil, pero está bien documentado.La principal desventaja es que calcular las bases de Groebner es costoso y resulta muy difícil de manejar si se trata de polinomios de punto flotante o se utilizan curvas de Bézier de orden superior.

Si desea algún código terminado en Haskell para encontrar las intersecciones, hágamelo saber.

Answer 3

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

El enfoque que utilicé fue:

Sean las curvas p, q definidas por 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 intentar resolver eso para cero.Descartar cualquier solución fuera de 0 <= t,u <= 1.0

N-R puede converger o no.Es posible que las curvas no se crucen, o que N-R simplemente explote cuando las dos curvas sean casi paralelas.Por lo tanto, corte N-R si no converge 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 (digamos, p) en dos curvas pa, pb en t = 0,5.Esto es fácil, solo se trata de calcular 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, de modo que p y q se dividen alternativamente en cada capa de la recursividad).

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 en los que las dos curvas son paralelas y no se tocan del todo, pero la distancia entre ellas es arbitrariamente pequeña, tal vez solo 1 ULP de diferencia.

Cuando encuentre una intersección, no habrá 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 verificar recursivamente si hay más intersecciones entre (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Hay una serie de artículos de investigación académica sobre cómo realizar recortes Bézier:

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 es necesario dividirlos 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 renderización de intervalos, también puede consultar http://www.sunfishstudio.com