¿Por qué es tan importante la propiedad del casco convexo (por ejemplo, de las curvas de Bézier)?

Question

Hace poco leí algunos apuntes y artículos sobre las curvas de Bézier. Todos ellos resumen las propiedades de las curvas de Bézier, como la propiedad de partición de la unidad de las funciones base ( Polinomios de Bernstein ), propiedad de variación decreciente de la curva ( la curva no se mueve/oscila más que el polígono de control ), y también la propiedad del casco convexo.

Al parecer, esta última es una propiedad importante, pero no encuentro el motivo. Tiene algo que ver con la estabilidad numérica de las combinaciones convexas, pero ¿por qué las combinaciones convexas son más "numéricamente estables" que otros tipos de combinaciones, como las afines?

Así, cuando se compara una curva de Bézier con, por ejemplo, una curva de Lagrange (que interpola todos sus puntos de control), la primera curva permanece dentro del polígono abarcado por sus puntos de control (el casco convexo), mientras que la segunda no. Sé que esto se debe a que una curva de Bézier se crea utilizando sólo combinaciones convexas, mientras que la curva de Lagrange no. Pero, ¿por qué es tan importante esta propiedad? ¿Por qué es mejor que una curva de Lagrange?

Answer 1

La propiedad de casco convexo garantiza que si todos los puntos de control se encuentran en una pequeña región del espacio, la curva no se alejará arbitrariamente de ella. Véase Fenómeno de Runge . Mejor aún, pruébelo usted mismo en Miniaplicación de interpolación de Lagrange de Mark Hoefer añade puntos hasta que haya unos veinte, luego arrastra uno de los puntos del centro fuera de la curva y mira a ver qué pasa. Esta es la razón por la que la propiedad de casco convexo es importante para la facilidad con que puede controlar la curva utilizando los puntos de control.

Sin duda, las combinaciones convexas también son importantes para la estabilidad numérica. En una combinación afín arbitraria, podrías tener valores positivos y negativos muy grandes sumándose para dar un resultado modesto, y esta cancelación de los bits de orden superior perdería precisión en el resultado. De hecho, esto ocurre en la interpolación de Lagrange, porque las funciones de base oscilan muy lejos de la $[0,1]$ gama. Por otra parte, con las curvas de Bézier todas las funciones de base son positivas, por lo que no se producen cancelaciones innecesarias y no se pierde mucha precisión numérica relativa.

Answer 2

La propiedad del casco convexo es la base de Recorte Bézier una técnica para resolver algunos problemas de forma adaptativa. Algunos ejemplos son la intersección de curvas y la búsqueda del cero en el trazado de rayos. Véase Intersección de curvas mediante recorte Bézier por Sederberg y Nishita.

Answer 3

La propiedad del casco convexo es útil para hacer una comprobación rápida antes de realizar algún cálculo más costoso. Por ejemplo, supongamos que tenemos que intersecar dos curvas Bézier. Es bastante fácil determinar que sus cascos convexos no se solapan. Por lo tanto, si compruebo que es así, no hay necesidad de buscar la intersección, porque no la habrá. Dicho de otro modo, las comprobaciones basadas en cascos convexos pueden dar una "salida anticipada" a los algoritmos geométricos. Esto puede suponer enormes aumentos de velocidad.

El algoritmo de recorte Bezier antes mencionado es un ejemplo, pero hay muchos otros. Algunos de ellos son:

• Intersección de dos curvas (como arriba)
• Decidir si un punto se encuentra en una curva
• Encontrar la curva de Bézier (de una colección) más cercana a un punto dado
• Intersección de una curva de Bézier con un plano o una superficie

La propiedad de casco convexo es aún más importante con las superficies Bezier. Esto se debe a que los cálculos de las superficies suelen ser más caros, por lo que una "salida temprana" es más valiosa.

Un par de puntos más:

El hecho de que las funciones de base sean no negativas facilita el control interactivo. Al desplazar un punto de control mediante un vector $v$ se le garantiza que todos los puntos de la curva se desplazarán unos positivo múltiplo de $v$ y, por tanto, se moverá en la misma dirección que el punto de control.

El hecho de que las funciones base sumen 1 es crucial: si no fuera así, la ecuación que define la curva de Bézier ni siquiera tendría sentido. Combinaciones lineales arbitrarias de puntos no tienen sentido; sólo tienen sentido las combinaciones afines.

Answer 4

Una curva Bézier siempre estará completamente contenida dentro del Casco Convexo de los puntos de control. Para curvas planas, imagine que cada punto de control es un clavo clavado en una tabla. La forma que adoptaría una goma elástica al ser encajada alrededor de los puntos de control es el casco convexo. Para las curvas de Bézier, cuyos puntos de control no están todos en un mismo plano, imagine que los puntos de control son pequeñas bolas en el espacio e imagine la forma que adoptaría un globo si se desplomara sobre las bolas. En este caso, esta forma es el casco convexo. En cualquier caso, una curva de Bézier siempre estará completamente dentro de su casco convexo plano o volumétrico. :)