OpenGL ES à partir du sol jusqu'à 9 (entracte): Quaternions

Avant que nous puissions entrer dans le prochain post dans le OpenGL ES à partir du sol pour, Qui couvre animation de squelette, nous avons à faire un petit détour et de parler d'un nouveau type de données que nous allons utiliser, le Quaternion. Nous allons utiliser les quaternions pour stocker la rotation sur les trois axes d'un seul os, ou, en d'autres termes, pour stocker la direction de l'os est pointé. Dans l'animation du squelette, comme vous le verrez dans le prochain épisode, les sommets dans le modèle sont attachés à un ou plusieurs os et déplacer les os ils sont attachés à se déplacer. En utilisant les quaternions, par opposition à stocker les trois Angles d'Euler des trois GLfloats ou un seul Vector3D a deux avantages:

1. Les quaternions sont pas soumis à blocage de cardan. Angles d'Euler sont donc quaternions va permettre à nos squelettes 3D pour avoir gamme complète de mouvement.
2. Combinant de multiples rotations en utilisant les quaternions nécessite des calculs nettement moins que de faire pivoter la matrice des transformations pour chaque angle d'Euler

Maintenant, les quaternions sont horriblement complexe et difficile à comprendre. Ils sont les mathématiques avancées: juju complètement fou. Heureusement, vous n'avez pas besoin de comprendre pleinement les mathématiques sous-jacentes à leur utilisation. Mais, nous devons utiliser les quaternions pour accomplir animation de squelette, donc il vaut mieux une seconde pour parler de ce qu'ils sont et comment nous les utilisons.

Discovery

Mathématiquement parlant, les quaternions sont une extension des nombres complexes et ont été découverts par Sir William Rowan Hamilton en 1843. Techniquement parlant, les quaternions forment un «quatre dimensions l'algèbre de division normée au cours de la nombres réels». Zoiks! Plus simplement, un quaternion utilise une quatrième dimension pour permettre le calcul de triples pour les trois coordonnées cartésiennes en fournissant chaque axe avec trois autres valeurs. Okay, peut-être que ce n'était pas si simple que cela, était-ce?

Ne soyez pas effrayés encore décollé. Si vous n'êtes pas profondément versé dans les mathématiques avancées, les quaternions peut faire votre malheur cerveau. Mais, comme je l'ai déjà dit, vous n'avez pas vraiment à Grok Quaternions à les utiliser. Le concept est très semblable à quelque chose que vous avez déjà vu. Si vous vous souvenez, des transformations de matrice impliquent l'utilisation d'une matrice 4x4 pour appliquer les transformations dans un espace tridimensionnel. Quand vient le temps d'utiliser les données transformées, nous simplement ignorer la quatrième valeur. Pensez à la quatrième valeur en un quaternion comme une valeur de travail, il est juste là pour fournir un espace pour les calculs. Commandants de maths, s'il vous plaît ne criez pas à moi - cette simplification permettra de simples mortels vivre en paix avec les quaternions.

Quaternions ont été considérés comme plutôt révolutionnaire à l'époque de la découverte, mais leur apogée était un peu courte durée. Dans le milieu des années 1880, calcul vectoriel a commencé à supplanter la théorie des quaternions en mathématiques, car elle décrit les mêmes phénomènes en utilisant des concepts qui sont plus faciles à comprendre et à décrire.

Not Quite Dead Yet!

Au 20e siècle, cependant, les quaternions retour en grâce. Comme nous l'avons discuté dans Partie 7, Il ya un phénomène appelé blocage de cardan qui peuvent survenir lorsque vous faites des transformations de rotation individuellement sur chaque axe, qui a pour effet indésirable d'arrêt de la rotation sur l'un des trois axes.

Malgré le fait que les quaternions est sorti de complexes, les mathématiques théoriques, ils ont des applications pratiques. Une telle application pratique est la représentation des angles de rotation sur les trois axes. Parce que les quaternions représentent les coordonnées cartésiennes (ou trois axes) de rotation en utilisant quatre dimensions, la représentation n'est pas soumise à blocage de cardan, et vous pouvez convertir entre les quaternions et les matrices de rotation, ainsi qu'entre les quaternions et les angles d'Euler, sans perte de fidélité ^ 1. Cela les rend absolument parfait pour stocker des informations rotation autour d'un objet, comme dire ... un os particulier d'un squelette articulé? Au lieu de stocker l'angle sur trois axes, nous stockons un quaternion unique.

Quaternions peuvent être multipliés comme des matrices, et les valeurs stockées dans la rotation quaternions différentes peuvent être combinées en les multipliant. Le résultat d'une multiplication de quaternions est exactement la même que la multiplication de matrice avec deux matrices de rotation, et implique des calculs nettement moins à accomplir, ce qui signifie qu'en plus d'éviter blocage de cardan, nous réduisons le nombre de FLOPS nous effectuons à chaque fois grâce à notre boucle d'application. Non seulement il ya moins d'opérations dans la multiplication des quaternions de multiplication des matrices, mais puisque nous pouvons également représenter les trois axes en utilisant un quaternion unique, nous pouvons faire multiplications généralement quaternion moins multiplications matrice. Si nous devions stocker rotation dans un Vector3D ou de l'aide de trois GLfloats, nous ont souvent à faire trois multiplications matrice - une pour chaque axe. En conséquence, les quaternions stockage peut conduire à une amélioration substantielle des performances individuelles plus stocker les angles de rotation.

La structure Quaternion

Du point de vue des données, un quaternion est rien de plus qu'un Vector3D avec un supplément de GLfloat, Généralement dénommé w. Donc, pour nos fins, un quaternion ressemblera à ceci:

typedef struct {
   GLfloat x;
   GLfloat y;
   GLfloat z;
   GLfloat w;
} Quaternion3D;

Normaliser un quaternion

Assez facile. Maintenant, tout comme Vector3Ds, puisque les quaternions représentent une direction dans l'espace, les valeurs de distance réelle n'ont pas d'importance, et il est fréquent de les normaliser à 1,0 avant et / ou après avoir fait d'autres calculs. Nous pouvons accomplir cela comme ceci:

static inline void Quaternion3DNormalize(Quaternion3D *quaternion)
{
   GLfloat magnitude;

   magnitude = sqrtf((quaternion->x * quaternion->x) +
                     (quaternion->y * quaternion->y) +
                     (quaternion->z * quaternion->z) +
                     (quaternion->w * quaternion->w));

   quaternion->x /= magnitude;
   quaternion->y /= magnitude;
   quaternion->z /= magnitude;
   quaternion->w /= magnitude;
}

Créer un quaternion à partir d'une matrice de rotation

Quaternions ne pas nous faire de bon si nous n'avons pas aucun moyen de convertir les quaternions à et de notre autres objets utilisés pour représenter les angles de rotation. Regardons d'abord à créer un quaternion à partir d'une matrice de rotation. Voici ce que la fonction de faire cela ressemble:

static inline Quaternion3D Quaternion3DMakeWithMatrix3D(Matrix3D matrix)
{
   Quaternion3D quat;
   GLfloat trace, s;

   trace = matrix[0] + matrix[5] + matrix[10];
if (trace > 0.0f)
{
       s = sqrtf(trace + 1.0f);
       quat.w = s * 0.5f;
       s = 0.5f / s;

       quat.x = (matrix[9] - matrix[6]) * s;
       quat.y = (matrix[2] - matrix[8]) * s;
       quat.z = (matrix[4] - matrix[1]) * s;
   }
else
{
NSInteger biggest;
enum      {A,E,I};
if (matrix[0] > matrix[5])
if (matrix[10] > matrix[0])
               biggest = I;   
else
               biggest = A;
else
if (matrix[10] > matrix[0])
               biggest = I;
else
               biggest = E;

switch (biggest)
{
case A:
               s = sqrtf(matrix[0] - (matrix[5] + matrix[10]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.x = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[9] - matrix[6]) * s;
                   quat.y = (matrix[1] + matrix[4]) * s;
                   quat.z = (matrix[2] + matrix[8]) * s;
break;
               }
               s = sqrtf(matrix[10] - (matrix[0] + matrix[5]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.z = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[4] - matrix[1]) * s;
                   quat.x = (matrix[8] + matrix[2]) * s;
                   quat.y = (matrix[9] + matrix[6]) * s;
break;
               }
               s = sqrtf(matrix[5] - (matrix[10] + matrix[0]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.y = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[2] - matrix[8]) * s;
                   quat.z = (matrix[6] + matrix[9]) * s;
                   quat.x = (matrix[4] + matrix[1]) * s;
break;
               }
break;

case E:
               s = sqrtf(matrix[5] - (matrix[10] + matrix[0]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.y = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[2] - matrix[8]) * s;
                   quat.z = (matrix[6] + matrix[9]) * s;
                   quat.x = (matrix[4] + matrix[1]) * s;
break;
               }
               s = sqrtf(matrix[10] - (matrix[0] + matrix[5]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.z = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[4] - matrix[1]) * s;
                   quat.x = (matrix[8] + matrix[2]) * s;
                   quat.y = (matrix[9] + matrix[6]) * s;
break;
               }
               s = sqrtf(matrix[0] - (matrix[5] + matrix[10]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.x = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[9] - matrix[6]) * s;
                   quat.y = (matrix[1] + matrix[4]) * s;
                   quat.z = (matrix[2] + matrix[8]) * s;
break;
               }
break;

case I:
               s = sqrtf(matrix[10] - (matrix[0] + matrix[5]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.z = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[4] - matrix[1]) * s;
                   quat.x = (matrix[8] + matrix[2]) * s;
                   quat.y = (matrix[9] + matrix[6]) * s;
break;
               }
               s = sqrtf(matrix[0] - (matrix[5] + matrix[10]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.x = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[9] - matrix[6]) * s;
                   quat.y = (matrix[1] + matrix[4]) * s;
                   quat.z = (matrix[2] + matrix[8]) * s;
break;
               }
               s = sqrtf(matrix[5] - (matrix[10] + matrix[0]) + 1.0f);
if (s > QUATERNION_TRACE_ZERO_TOLERANCE)
{
                   quat.y = s * 0.5f;
                   s = 0.5f / s;
                   quat.w = (matrix[2] - matrix[8]) * s;
                   quat.z = (matrix[6] + matrix[9]) * s;
                   quat.x = (matrix[4] + matrix[1]) * s;
break;
               }
break;

default:
break;
       }
   }
return quat;
}

Eh bien, pouah! Si vous voulez vraiment comprendre ce qui se passe ici, il va exiger une compréhension de calcul matriciel, Théorème de la rotation d'EulerEt les concepts de eigenvalues and trace, Pour ne pas mentionner une compréhension approfondie de la façon dont les rotations sont représentés dans des matrices. Lorsque vous avez terminé votre doctorat en mathématiques, vous pouvez revenir et l'expliquer au reste de la USL. Vous pouvez trouver l'algorithme utilisé dans cette fonction énoncés dans le pseudocode Matrice FAQ.

Création d'une matrice de rotation à partir d'un quaternion

Dans l'autre sens est en réalité un peu plus facile. Encore une fois, l'algorithme de base provient de la Matrice FAQ, Si je devais le passer à la ligne-major de la commande:

static inline void Matrix3DSetUsingQuaternion3D(Matrix3D matrix, Quaternion3D quat)
{
   matrix[0]  = (1.0f - (2.0f * ((quat.y * quat.y) + (quat.z * quat.z))));
   matrix[1]  = (2.0f * ((quat.x * quat.y) - (quat.z * quat.w)));
   matrix[2]  = (2.0f * ((quat.x * quat.z) + (quat.y * quat.w)));
   matrix[3] = 0.0f;
   matrix[4]  = (2.0f * ((quat.x * quat.y) + (quat.z * quat.w)));
   matrix[5]  = (1.0f - (2.0f * ((quat.x * quat.x) + (quat.z * quat.z))));
   matrix[6]  = (2.0f * ((quat.y * quat.z) - (quat.x * quat.w)));
   matrix[7] = 0.0f;
   matrix[8]  = (2.0f * ((quat.x * quat.z) - (quat.y * quat.w)));
   matrix[9]  = (2.0f * ((quat.y * quat.z) + (quat.x * quat.w)));
   matrix[10] = (1.0f - (2.0f * ((quat.x * quat.x) + (quat.y * quat.y))));
   matrix[11] = 0.0f;
   matrix[12]  = 0.0f;
   matrix[13]  = 0.0f;
   matrix[14] = 0.0f;
   matrix[15] = 1.0f;
}

Conversion d'un angle et l'axe de rotation en un quaternion

Another conversion nous pouvons faire avec les quaternions est de faire tourner sur un axe arbitraire représenté par une Vector3D. Ceci peut être extrêmement utile dans l'animation du squelette et il est assez difficile à mettre en œuvre l'aide de matrices. Pour créer un quaternion basée sur un angle et l'axe de rotation, nous faisons ceci:

static inline Quaternion3D Quaternion3DMakeWithAxisAndAngle(Vector3D axis, GLfloat angle)
{
   Quaternion3D quat;
   GLfloat sinAngle;

   angle *= 0.5f;
    Vector3DNormalize(&axis);
   sinAngle = sinf(angle);
   quat.x = (axis.x * sinAngle);
   quat.y = (axis.y * sinAngle);
   quat.z = (axis.z * sinAngle);
   quat.w = cos(angle);

return quat;
}

Extraction d'un angle et l'axe de rotation à partir d'un quaternion

Nous pouvons également aller dans l'autre. Nous pouvons prendre la rotation représentée dans un quaternion et extraire l'angle de rotation et de degrés d'elle, Comme ceci:

static inline void Quaternion3DExtractAxisAndAngle(Quaternion3D quat, Vector3D *axis, GLfloat *angle)
{
   GLfloat s;
    Quaternion3DNormalize(&quat);
   s = sqrtf(1.0f - (quat.w * quat.w));

if (fabs(s) < 0.0005f) s = 1.0f;

if (axis != NULL)
{
       axis->x = (quat.x / s);
       axis->y = (quat.y / s);
       axis->z = (quat.z / s);
   }

if (angle != NULL)
       *angle = (acosf(quat.w) * 2.0f);
}

Multiplication de quaternions

Pour combiner les rotations à partir de deux différents Quaternion3Ds, nous avons juste besoin de les multiplier ensemble. Here we go:

static inline void Quaternion3DMultiply(Quaternion3D *quat1, Quaternion3D *quat2)
{
   Vector3D v1, v2, cp;
float angle;

   v1.x = quat1->x;
   v1.y = quat1->y;
   v1.z = quat1->z;
   v2.x = quat2->x;
   v2.y = quat2->y;
   v2.z = quat2->z;
   angle = (quat1->w * quat2->w) - Vector3DDotProduct(v1, v2);

   cp = Vector3DCrossProduct(v1, v2);
   v1.x *= quat2->w;
   v1.y *= quat2->w;
   v1.z *= quat2->w;
   v2.x *= quat1->w;
   v2.y *= quat1->w;
   v2.z *= quat1->w;

   quat1->x = v1.x + v2.x + cp.x;
   quat1->y = v1.y + v2.y + cp.y;
   quat1->z = v1.z + v2.z + cp.z;
   quat1->w = angle;
}

Inverser un quaternion

Nous pouvons faire une spacial radier de tout quaternion en les conjuguant. Conjuguer un quaternion signifie simplement que nous inverser le cours des trois composantes du quaternion qui représente le vecteur (x, y et z). Dans cette application, nous avons également normaliser le quaternion dans le cadre du calcul plutôt que comme une étape distincte:

static inline void Quaternion3DInvert(Quaternion3D  *quat)
{
   GLfloat length = 1.0f / ((quat->x * quat->x) +
                    (quat->y * quat->y) +
                    (quat->z * quat->z) +
                    (quat->w * quat->w));
   quat->x *= -length;
   quat->y *= -length;
   quat->z *= -length;
   quat->w *= length;
}

Créer un quaternion d'Angles d'Euler

J'ai mis en garde contre les angles d'Euler pour la rotation, mais il ya des moments où vous aurez à convertir des angles d'Euler en un quaternion, Comme lors de l'acceptation d'entrée d'un utilisateur. Pour ce faire, nous devons créer Vector3Ds pour représenter chacun des axes d'Euler, de créer des quaternions en utilisant les vecteurs et le passé dans les valeurs, puis utilisez la multiplication des quaternions de combiner les quaternions résultant.

static inline Quaternion3D Quaternion3DMakeWithEulerAngles(GLfloat x, GLfloat y, GLfloat z)
{
   Vector3D vx = Vector3DMake(1.f, 0.f, 0.f);
   Vector3D vy = Vector3DMake(0.f, 1.f, 0.f);
   Vector3D vz = Vector3DMake(0.f, 0.f, 1.f);

   Quaternion3D qx = Quaternion3DMakeWithAxisAndAngle(vx, x);
   Quaternion3D qy = Quaternion3DMakeWithAxisAndAngle(vy, y);
   Quaternion3D qz = Quaternion3DMakeWithAxisAndAngle(vz, z);


    Quaternion3DMultiply(&qx, &qy );
    Quaternion3DMultiply(&qx, &qz );
return qx;
}

SLERPs et NLERPS

Enfin, la pièce de résistance: SLERPs et NLERPS. SLERP est un raccourci pour Interpolation linéaire sphérique and NLERPS for normalisée interpolation linéaire. Rappelez-vous comment nous avons fait algébriques interpolation linéaire en Partie 9a pour calculer l'emplacement correct pour chaque vertex basé sur combien de temps s'était écoulé? Eh bien, ces mêmes calculs ne vont pas nécessairement de nous donner les résultats que nous voulons quand interpolation quaternions. Imaginez une rotule:

Source: Wikipedia

Vous savez où il ya une rotule? Dans votre épaule. La clavicule et l'épine de l'omoplate forme un berceau pour la saillie en forme de boule au sommet de l'humérus. Eh bien, c'est très pratique. Tenez-vous devant un miroir, tenez votre am-dessus de votre tête, puis en gardant votre bras droit, le faire descendre jusqu'à ce qu'il soit à vos côtés. Votre main ne bouge pas en ligne droite, ça. Votre main se déplace sur un arc et se déplace plus vite que votre coude et votre épaule et les chances sont de votre main ne bouge pas à une vitesse constante. C'est le mouvement de base nous voulons simuler quand nous animent des angles de rotation.

SLERPs et NLERPs sont les deux approches les plus courantes. SLERPs sont plus précis et donner une meilleure simulation de la réalité, mais ils sont plus lents et plus intensive du processeur. NLERPs sont beaucoup plus rapides parce qu'ils sont essentiellement les mêmes d'interpolation linéaire, nous avons déjà utilisé, seulement normalisé après avoir fait l'interpolation, ce qui vous aurait été capable de deviner le nom de «interpolation linéaire normalisé».

Utilisez SLERPs quand réalistes animation regarder est plus importante que la vitesse, NLERPs autrement. Les deux méthodes prennent exactement les mêmes paramètres, afin de commutation entre les deux ne devraient pas être une grosse affaire, de sorte que vous pouvez expérimenter pour voir si SLERPs valent le coût de traitement supplémentaire.

Voici la simple mise en œuvre NLERP:

static inline Quaternion3D Quaternion3DMakeWithNLERP(Quaternion3D *start, Quaternion3D *finish, GLclampf progress)
{
   Quaternion3D ret;
   GLfloat inverseProgress = 1.0f - progress;
   ret.x = (start->x * inverseProgress) + (finish->x * progress);    
   ret.y = (start->y * inverseProgress) + (finish->y * progress);
   ret.z = (start->z * inverseProgress) + (finish->z * progress);
   ret.w = (start->w * inverseProgress) + (finish->w * progress);
    Quaternion3DNormalize(&ret);
return ret;
}

Maintenant, la mise en œuvre SLERP est un peu plus complexe et nécessite la capacité à calculer un produit scalaire sur un quaternion, qui se fait exactement le même que le calcul du produit scalaire d'un vecteur:

static inline Quaternion3D Quaternion3DMakeWithSLERP(Quaternion3D *start, Quaternion3D *finish, GLclampf progress)
{
   GLfloat startWeight, finishWeight, difference;
   Quaternion3D ret;

   difference = ((start->x * finish->x) + (start->y * finish->y) + (start->z * finish->z) + (start->w * finish->w));
if ((1.f - fabs(difference)) > .01f)
{
       GLfloat theta, oneOverSinTheta;

       theta = acosf(fabsf(difference));
       oneOverSinTheta = (1.f / sinf(theta));
       startWeight = (sinf(theta * (1.f - progress)) * oneOverSinTheta);
       finishWeight = (sinf(theta * progress) * oneOverSinTheta);
if (difference < 0.f)
           startWeight = -startWeight;
   } else
{
       startWeight = (1.f - progress);
       finishWeight = progress;
   }
   ret.x = (start->x * startWeight) + (finish->x * finishWeight);
   ret.y = (start->y * startWeight) + (finish->y * finishWeight);
   ret.z = (start->z * startWeight) + (finish->z * finishWeight);
   ret.w = (start->w * startWeight) + (finish->w * finishWeight);
    Quaternion3DNormalize(&ret);

return ret;
}

Finish Line

Bon, maintenant que nous sommes armés et dangereux et prêt à faire une animation squelettique. Je vais vous répondre revenir ici la prochaine fois pour elle. J'ai mis à jour le Xcode modèle de projet avec ces nouvelles fonctions et des types de données.

---

1 Parce que nos programmes utilisent des variables à virgule flottante, nous allons réellement voir de légers changements dans les données en raison du phénomène connu sous le nom perte de signification. Ce n'est pas parce que nous sommes en utilisant les quaternions. C'est parce que nous utilisons des variables à virgule flottante.