Bounding Box

2.9.4 Bounding moving bounding boxes

Hay dos casos fáciles: primero, si las matrices de fotogramas clave son iguales, entonces podemos aplicar arbitrariamente sólo la transformación inicial para calcular los límites completos. En segundo lugar, si la transformación sólo incluye la escala y/o la traslación, entonces el cuadro delimitador que abarca las posiciones transformadas del cuadro delimitador tanto en el momento inicial como en el final delimita todo su movimiento. Para ver por qué esto es así, considera la posición de un punto transformado p como una función del tiempo; denotaremos esta función de dos matrices, un punto y un tiempo por a(M0, M1, p, t).

where s0,0 es el elemento correspondiente de la matriz de escala para M0, s0,0′ es el mismo elemento de la matriz de escala para M1, y los elementos de la matriz de traslación se denotan igualmente por d. (Aquí elegimos d por «delta», ya que t ya se reivindica como tiempo.) Como función lineal de t, los extremos de esta función se encuentran en los tiempos de inicio y final. ¡Las otras coordenadas y el caso de una escala generalizada siguen de manera similar.

〈Definiciones del método AnimatedTransform〉 + ≡

Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {

if (!actuallyAnimated)

return (*startTransform)(b);

if (hasRotation == false)

return Union((*startTransform)(b), (*endTransform)(b));

〈Retorno de los límites de movimiento teniendo en cuenta la rotación animada 108〉

}

Para el caso general con rotaciones animadas, la función de movimiento puede tener extremos en puntos en el medio del rango de tiempo. No conocemos ninguna forma sencilla de encontrar estos puntos. Muchos renderizadores abordan este problema muestreando un gran número de veces en el rango de tiempo, calculando la transformación interpolada en cada uno de ellos y tomando la unión de todos los cuadros delimitadores transformados correspondientes. Aquí desarrollaremos un método más fundamentado que nos permite calcular de forma robusta estos límites de movimiento.

Utilizamos un límite conservador ligeramente más sencillo que implica calcular el movimiento de las ocho esquinas del cuadro delimitador individualmente y encontrar la unión de esos límites.

〈Devuelve los límites de movimiento teniendo en cuenta la rotación animada〉 ≡ 108

Bounds3f bounds;

for (int corner = 0; corner <8; ++corner)

bounds = Union(bounds, BoundPointMotion(b.Corner(corner));

return bounds;

El resultado es bastante complejo cuando se expande, sobre todo debido al slerp y la conversión del cuaternión resultante a una matriz; un sistema de álgebra computacional es un requisito para trabajar con esta función.

donde θ es el arco coseno del producto punto de los dos cuaterniones y donde los cinco coeficientes ci son 3-vectores que dependen de las dos matrices y la posición p. Esta especialización funciona bien, ya que necesitaremos evaluar la función en muchos valores de tiempo para un punto dado.

Ahora tenemos dos tareas: primero, dado un par de matrices de fotogramas clave y un punto p, primero necesitamos ser capaces de calcular eficientemente los valores de los coeficientes ci. Luego, dada la función relativamente sencilla definida por ci y θ, necesitamos encontrar los ceros de la ecuación (2.12), que pueden representar los momentos en los que se producen los extremos del movimiento.

Así, dados los coeficientes ki y un punto p concreto del que queremos acotar el movimiento, podemos calcular de forma eficiente los coeficientes ci de la función derivativa de la ecuación (2.12). La estructura DerivativeTerm encapsula estos coeficientes y este cálculo.

〈AnimatedTransform Private Data〉 + ≡

struct DerivativeTerm {

DerivativeTerm(Float c, Float x, Float y, Float z)

: kc(c), kx(x), ky(y), kz(z) { }

Float kc, kx, ky, kz;

Float Eval(const Point3f &p) const {

return kc + kx * p.x + ky * p.y + kz * p.z;

}

};

Los atributos c1 – c5 almacenan la información de las derivadas correspondientes a los cinco términos de la ecuación (2.12). Los tres elementos del array corresponden a las tres dimensiones del espacio.

〈AnimatedTransform Private Data〉 + ≡

DerivativeTerm c1, c2, c3, c4, c5;

El fragmento 〈Compute terms of motion derivative function〉 en el constructor de AnimatedTransform, no incluido aquí, inicializa estos términos, mediante código generado automáticamente. Dado que requiere unos cuantos miles de operaciones de punto flotante, hacer este trabajo una vez y amortizarlo sobre las múltiples esquinas de la caja delimitadora es útil. Los coeficientes ki se calculan más fácilmente si asumimos un rango de tiempo canónico ; más tarde, tendremos que reasignar los valores t de los ceros de la función de movimiento al rango de tiempo real del obturador.

Dados los coeficientes ki basados en las matrices de fotogramas clave, BoundPointMotion() calcula un límite robusto del movimiento de p.

〈AnimatedTransform Method Definitions〉 + ≡

Bounds3f AnimatedTransform::BoundPointMotion(const Point3f &p) const {

Bounds3f bounds((*startTransform)(p), (*endTransform)(p));

Float cosTheta = Dot(R, R);

Float theta = std::acos(Clamp(cosTheta, -1, 1));

for (int c = 0; c <3; ++c) {

〈Encuentra cualquier cero de la derivada de movimiento para el componente c 111〉

〈Expande la caja delimitadora para cualquier cero de la derivada de movimiento encontrado 111〉

}

return bounds;

La función IntervalFindZeros(), que se presentará en breve, encuentra numéricamente los ceros de la ecuación (2.12). Hasta cuatro son posibles.

〈Encuentra los ceros de cualquier derivada del movimiento para el componente c〉 ≡ 110

Float zeros;

int nZeros = 0;

IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),

c5.Eval(p), theta,

Intervalo(0., 1.), ceros, &nCeros);

Los ceros se encuentran sobre t ∈ , por lo que necesitamos interpolar dentro del rango de tiempo antes de llamar al método para transformar el punto en el tiempo correspondiente. Obsérvese también que el extremo está sólo en una de las dimensiones x, y y z, por lo que los límites sólo necesitan ser actualizados en esa dimensión. Por conveniencia, aquí sólo usamos la función Union(), que considera todas las dimensiones, aunque dos podrían ser ignoradas.

〈Expandir la caja delimitadora para cualquier derivada de movimiento de los ceros encontrada〉 ≡ 110

for (int i = 0; i <nCeros; ++i) {

Point3f pz = (*this)(Lerp(zeros, startTime, endTime), p);

Límites = Unión(límites, pz);

}

Encontrar los ceros de la función derivada del movimiento, Ecuación (2.12), no puede hacerse algebraicamente; son necesarios métodos numéricos. Afortunadamente, la función se comporta bien – es bastante suave y tiene un número limitado de ceros. (Recuerde el gráfico de la figura 2.18, que era un representante inusualmente complejo.)

Aunque podríamos utilizar una búsqueda basada en la bisección o el método de Newton, nos arriesgaríamos a perder ceros cuando la función sólo cruza brevemente el eje. Por lo tanto, utilizaremos la aritmética de intervalos, una extensión de la aritmética que permite conocer el comportamiento de las funciones sobre rangos de valores, lo que hace posible encontrar de forma robusta los ceros de las funciones.

Para entender la idea básica de la aritmética de intervalos, consideremos, por ejemplo, la función f (x) = 2x. Si tenemos un intervalo de valores ∈ ℝ, entonces podemos ver que sobre el intervalo, el rango de f es el intervalo . En otras palabras f () ⊂ .

En otras palabras, si sumamos dos valores donde uno está en el intervalo y el segundo está en , entonces el resultado debe estar en el intervalo.

La aritmética de intervalos tiene la importante propiedad de que los intervalos que da son conservativos. En particular, si f () ⊂ y si c > 0, entonces sabemos con seguridad que ningún valor en hace que f sea negativo. A continuación, mostraremos cómo calcular la ecuación (2.12) sobre intervalos y aprovecharemos los límites conservativos de los intervalos calculados para encontrar eficientemente intervalos pequeños con cruces de cero en los que los métodos regulares de búsqueda de raíces pueden utilizarse de forma fiable.