graphics - pro - titles adobe premiere

Recorte de Bezier (4)

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, que se enumeran 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 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.

Hay una serie de trabajos de investigación académica sobre cómo hacer recortes de 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

Recomiendo los métodos de intervalo porque, como usted describe, no 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 interpretación de intervalos, también puede consultar http://www.sunfishstudio.com

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 utilicé fue:

Deje que las curvas p, q, sean definidas por los puntos de control de Bezier. ¿Se cruzan?

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

px (t), py (t), qx (u), qy (u) son polinomios cúbicos en 0 <= t, u <= 1.0. La distancia al cuadrado (px - qx) ** 2 + (py - qy) ** 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

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

Si NR 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 recursión, q se ha convertido en p, por lo 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 recursión 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 encuentras una intersección, no has 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).

Sé que corro el riesgo de ser superfluo, 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 funcional.

Puede reescribir las curvas bezier como un conjunto de dos ecuaciones cúbicas bivariadas como esta:

Δx = ax₁ * t₁ ^ 3 + bx₁ * t₁ ^ 2 + cx₁ * t₁ + tx₁ - 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 por 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 a (como otro escritor puso es) explotar.

Pero si usa números enteros o racionales para sus puntos de control, puede usar las bases de Groebner para reescribir sus polinomios bi-variados de orden 3 en un (posiblemente-hasta-orden-9-así-su-nueve- posibles-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 amigable con los legos 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 del camino Bézier cúbico y curvas de desplazamiento " por TF Hain, que tiene muchas ecuaciones de utilidad para curvas de bezier, incluyendo cómo encontrar los coeficientes polinomiales para las ecuaciones x e y.

En cuanto a si el recorte de Bezier ayudará con este método en particular, lo dudo, pero el recorte más boo es un método para reducir las intersecciones, no para encontrar una respuesta final (aunque posiblemente aproximada) de dónde se encuentra. 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 de búsqueda de raíz unidimensional, 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.

Encontré la siguiente publicación para ser la mejor información con respecto a Bezier Clipping:

TW Sederberg, BYU, Curso de diseño geométrico asistido por computadora Notas del curso

El Capítulo 7 que habla sobre Curve Intersection está disponible en línea. Describe cuatro enfoques diferentes para encontrar intersecciones y describe Bezier Clipping en detalle:

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