Bounding Box

Donné un Bounds3f qui est transformé par une transformation animée, il est utile de pouvoir calculer une bounding box qui englobe tout son mouvement sur la période de temps de l’animation. Par exemple, si nous pouvons délimiter le mouvement d’une primitive géométrique animée, nous pouvons intersecter des rayons avec cette délimitation pour déterminer si le rayon peut couper l’objet avant d’encourir le coût de l’interpolation de la délimitation de la primitive au temps du rayon pour vérifier cette intersection. La méthode AnimatedTransform::MotionBounds() effectue ce calcul, prenant une boîte englobante et renvoyant la boîte englobante de son mouvement sur la plage de temps de l’AnimatedTransform.

Puisque dans ce cas la composante de rotation de la décomposition est l’identité, alors avec notre décomposition matricielle nous avons

où la translation et l’échelle sont toutes deux écrites comme fonctions du temps. En supposant pour simplifier que S(t) est une échelle régulière, nous pouvons trouver des expressions pour les composantes de a(M0, M1, p, t). Par exemple, pour la composante x, nous avons :

Pour chaque coin de boîte englobante p, nous devons trouver l’extrema de a sur la plage de temps de l’animation. Rappelons que les extrema d’une fonction continue sur un certain domaine sont soit aux points limites du domaine, soit aux points où la dérivée première de la fonction est nulle. Ainsi, la borne globale est donnée par l’union des positions au début et à la fin du mouvement ainsi que la position à tout extrema.

Figure 2.18 montre un tracé d’une coordonnée de la fonction de mouvement et de sa dérivée pour une trajectoire de mouvement intéressante d’un point. Notez que la valeur maximale de la fonction sur la plage de temps est atteinte à un point où la dérivée a un zéro.

Figure 2.18. (a) Mouvement de la coordonnée x d’un point p en fonction du temps, déterminé par deux matrices d’images clés. (b) La dérivée de la fonction de mouvement, équation (2.12). Notez que les extrema de la fonction de mouvement dans la plage de temps donnée correspondent aux zéros de la dérivée.

Pour lier le mouvement d’un seul point, nous commençons notre dérivation en suivant l’approche utilisée pour le cas sans rotation, en développant les trois composantes T, R et S de l’équation (2.9) comme fonctions du temps et en trouvant leur produit. Nous avons :

La dérivée ∂a(M0, M1, p, t)/∂t est également assez complexe-dans toute sa gloire algébrique, plus de 2 000 opérations sont nécessaires pour évaluer sa valeur pour une paire donnée de matrices décomposées, point et temps. Cependant, étant donné des matrices de transformation spécifiques et un point spécifique, a est considérablement simplifié ; nous désignerons la fonction spécialisée de t seul comme aM, p(t). L’évaluation de sa dérivée nécessite environ 10 opérations en virgule flottante, un sinus et un cosinus à évaluer pour chaque coordonnée :

Pour la première tâche, nous allons d’abord factoriser les contributions aux coefficients qui dépendent des matrices d’images clés de celles qui dépendent du point p, en supposant que les boîtes limites pour le mouvement de plusieurs points seront calculées pour chaque paire de matrices d’images clés (comme c’est le cas ici). Le résultat est heureusement assez simple – les vecteurs ci sont sont des fonctions linéaires des composantes x, y et z du point.

}

La fonction IntervalFindZeros(), qui sera introduite prochainement, trouve numériquement les zéros de l’équation (2.12). Jusqu’à quatre sont possibles.

〈Trouver tous les zéros de la dérivée du mouvement pour la composante c〉 ≡ 110

Float zeros;

int nZeros = 0;

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

c5.Eval(p), thêta,

Intervalle(0., 1.), zéros, &nZeros);

Les zéros sont trouvés sur t ∈ , nous devons donc interpoler dans l’intervalle de temps avant d’appeler la méthode pour transformer le point au temps correspondant. Notez également que l’extremum n’est qu’à l’une des dimensions x, y, et z, et donc les limites ne doivent être mises à jour que dans cette seule dimension. Par commodité, nous utilisons ici simplement la fonction Union(), qui prend en compte toutes les dimensions, même si deux pourraient être ignorées.

〈Expansion de la boîte englobante pour tout mouvement dérivé des zéros trouvés〉 ≡ 110

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

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

bounds = Union(bounds, pz);

}

La recherche des zéros de la fonction dérivée du mouvement, équation (2.12), ne peut pas être fait algébriquement ; des méthodes numériques sont nécessaires. Heureusement, la fonction se comporte bien : elle est assez lisse et possède un nombre limité de zéros. (Rappelez-vous le tracé de la figure 2.18, qui était un représentant inhabituellement complexe.)

Bien que nous puissions utiliser une recherche basée sur la bissection ou la méthode de Newton, nous risquerions de manquer des zéros lorsque la fonction ne traverse que brièvement l’axe. Par conséquent, nous utiliserons l’arithmétique d’intervalle, une extension de l’arithmétique qui donne un aperçu du comportement des fonctions sur des plages de valeurs, ce qui permet de trouver de manière robuste les zéros des fonctions.

Pour comprendre l’idée de base de l’arithmétique d’intervalle, considérons, par exemple, la fonction f (x) = 2x. Si nous avons un intervalle de valeurs ∈ ℝ, alors nous pouvons voir que sur l’intervalle, l’étendue de f est l’intervalle . En d’autres termes, f () ⊂ .

En d’autres termes, si nous additionnons deux valeurs dont l’une est dans l’intervalle et la seconde dans , alors le résultat doit être dans l’intervalle ,

L’arithmétique d’intervalle a la propriété importante que les intervalles qu’elle donne sont conservatifs. En particulier, si f () ⊂ et si c > 0, alors on sait avec certitude qu’aucune valeur de dans ne fait que f soit négative. Dans ce qui suit, nous montrerons comment calculer l’équation (2.12) sur des intervalles et nous profiterons des limites conservatrices des intervalles calculés pour trouver efficacement de petits intervalles avec des passages à zéro où les méthodes régulières de recherche de racines peuvent être utilisées de manière fiable.