OpenGL Moderne

Appendice G : Cliquer sur un objet avec une fonction personnalisée d'intersection rayon-boîte englobante orientée

Opengl-tutorial.org

Traducteur

Alexandre Laurent

La dernière méthode est un sympathique compromis entre l'implémentation OpenGL « hacky » et l'utilisation d'un moteur physique complet pour de simples lancers de rayons.

Ce tutoriel utilise les concepts et les fonctions du tutoriel de Bullet, donc soyez sûr de le lire avant celui-ci.

Commentez

- Titre : OpenGL Moderne

- Auteur : Opengl-tutorial.org

- Traducteur : Alexandre Laurent

- Parution : 17 décembre 2014

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2014 opengl-tutorial.org. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- Navigation

- I. Introduction

- II. L'idée de base

- III. Algorithme d'intersection rayon-OBB

- IV. Implémentation de l'algorithme

- V. Utiliser l'algorithme

- VI. Avantages et inconvénients

- VII. Remarques finales

- VIII. Remerciements

- Navigation

Navigation

Sommaire

I - Introduction

La dernière méthode est un sympathique compromis entre l'implémentation OpenGL « hacky » et l'utilisation d'un moteur physique complet pour de simples lancers de rayons.

Ce tutoriel utilise les concepts et les fonctions du tutoriel de Bullet, donc soyez sûr de le lire avant celui-ci.

II - L'idée de base

Au lieu de dépendre de l'intersection d'un rayon contre une forme de collision de Bullet, nous allons l'implémenter nous-mêmes.

Comme nous l'avons vu, il y a plusieurs formes de collision possibles. Les sphères sont très simples à intersecter, mais pour de nombreux objets, elles représentent très mal les modèles. D'un autre côté, l'intersection d'un rayon avec tous les triangles du modèle original est très couteuse. Les boîtes englobantes orientées (Oriented Bounding Box (OBB)) sont un bon compromis. Elles sont assez précises (mais cela dépend de votre géométrie) et sont plutôt rapides à calculer.

Une OBB est une boîte englobant le modèle et lorsque le modèle est déplacé ou tourné, la même transformation est appliquée à la boîte :

III - Algorithme d'intersection rayon-OBB

(L'algorithme et les figures s'inspirent grandement du livre Real-Time Rendering Vol. 3. Achetez ce livre !)

Soit l'OBB ci-dessous. Sur l'axe des X, qui est délimité par deux plans verticaux, ici en rouge. Lorsqu'ils sont intersectés par le rayon (une opération très simple), cela donne deux intersections, une « proche » et une « lointaine » :

Lorsque le rayon intersecte les deux autres plans qui délimitent l'axe Y (en vert), cela donne deux intersections supplémentaires. Notez comment les intersections sont ordonnées : vous entrez dans la zone verte → vous sortez de la zone verte → vous entrez dans la zone rouge → vous sortez de la zone rouge. Cela signifie qu'il n'y a pas d'intersection.

Mais si l'ordre change (vous entrez dans la zone verte → vous entrez dans la zone rouge), alors vous savez qu'il y a une intersection !

Mettons cela en pratique.

IV - Implémentation de l'algorithme

(Le code complet est disponible dans le fichier Misc05/misc05_picking_custom.cpp.)

Notre fonction d'intersection rayon - OBB ressemblera à cela :

bool TestRayOBBIntersection(
glm::vec3 ray_origin,        // Origine du rayon, dans l'espace monde
glm::vec3 ray_direction,     // Direction du rayon (PAS la cible !), dans l'espace monde. Doit être normalisé.
glm::vec3 aabb_min,          // Coordonnées minimales X,Y,Z du modèle lorsqu'il n'est pas transformé.
glm::vec3 aabb_max,          // Coordonnées maximales X,Y,Z. Souvent aabb_min*-1 si votre modèle est centré, mais ce n'est pas toujours le cas.
glm::mat4 ModelMatrix,       // Transformation appliquée au modèle (et qui sera donc appliquée à la boîte englobante)
float& intersection_distance // Sortie : la distance entre ray_origin et l'intersection avec l'OBB
){

Nous commençons par initialiser quelques variables. tMin est la plus grande intersection « proche » actuellement trouvée ; tMax est la plus petite intersection « lointaine » trouvée jusqu'à présent. Delta est utilisé pour calculer les intersections avec les plans.

float tMin = 0.0f;
float tMax = 100000.0f;

glm::vec3 OBBposition_worldspace(ModelMatrix[3].x, ModelMatrix[3].y, ModelMatrix[3].z);

glm::vec3 delta = OBBposition_worldspace - ray_origin;

Maintenant, calculons l'intersection entre les deux plans qui délimitent l'OBB sur l'axe des X :

glm::vec3 xaxis(ModelMatrix[0].x, ModelMatrix[0].y, ModelMatrix[0].z);
float e = glm::dot(xaxis, delta);
float f = glm::dot(ray_direction, xaxis);

// Attention, ne faites pas la division si f est proche de 0 ! Voyez le code source complet pour plus de détails.
float t1 = (e+aabb_min.x)/f; // Intersection avec le plan « gauche »
float t2 = (e+aabb_max.x)/f; // Intersection avec le plan « droit »

t1 et t2 contiennent maintenant les distances entre l'origine du rayon et les intersections avec le plan, mais nous ne savons pas dans quel ordre, donc nous nous assurons que t1 représente l'intersection « proche » et t2 l'intersection « lointaine » :

if (t1>t2){ // si dans le désordre
float w=t1;t1=t2;t2=w; // échange t1 et t2
}

Nous pouvons mettre à jour tMin et tMax :

// tMax est l'intersection « lointaine » la plus proche (parmi les paires de plans X,Y et Z)
if ( t2 < tMax ) tMax = t2;
// tMin est l'intersection « proche » la plus proche (parmi les paires de plans X,Y et Z)
if ( t1 > tMin ) tMin = t1;

Et voici une astuce : si l'intersection « lointaine » est plus proche que l'intersection « proche », il n'y a pas d'intersection.

if (tMax < tMin )
return false;

Cela est pour l'axe des X. C'est exactement la même chose pour les autres axes !

V - Utiliser l'algorithme

La fonction TestRayOBBIntersections() nous permet de tester l'intersection avec une seule OBB, donc nous devons toutes les tester. Dans ce tutoriel, nous testons simplement les boîtes les unes après les autres, mais si vous avez plein d'objets, vous pourriez avoir besoin d'une structure accélératrice comme un arbre binaire de partitionnement de l'espace (Binary Space Partitionning Tree BSP-Tree) ou une hiérarchie de volume englobant (Bounding Volume Hierarchy BVH).

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

float intersection_distance; // Sortie de TestRayOBBIntersection()
glm::vec3 aabb_min(-1.0f, -1.0f, -1.0f);
glm::vec3 aabb_max( 1.0f,  1.0f,  1.0f);

// Matrice de transformation ModelMatrix transforme :
// - le modèle à sa position et orientation voulue
// - mais aussi l'AABB (définie avec aabb_min et aabb_max) en une OBB
glm::mat4 RotationMatrix = glm::toMat4(orientations[i]);
glm::mat4 TranslationMatrix = translate(mat4(), positions[i]);
glm::mat4 ModelMatrix = TranslationMatrix * RotationMatrix;

if ( TestRayOBBIntersection(
ray_origin,
ray_direction,
aabb_min,
aabb_max,
ModelMatrix,
intersection_distance)
){
std::ostringstream oss;
oss << "mesh " << i;
message = oss.str();
break;
}
}

Notez que cet algorithme a un problème : il prend la première OBB qu'il trouve. Mais si cette OBB est derrière une autre, cela est faux. Donc vous devez prendre seulement l'OBB la plus proche ! C'est au lecteur de résoudre ce problème…

VI - Avantages et inconvénients

- Avantages :

- facile ;

- nécessite peu de mémoire (seulement le surplus de l'OBB) ;

- ne ralentit pas OpenGL comme le faisait la première version.

- Inconvénients :

- plus lent qu'avec le moteur physique, car il n'y a pas de structure accélératrice ;

- peut ne pas être assez précis.

VII - Remarques finales

Il y a de nombreuses autres routines d'intersection disponibles pour toutes sortes de formes de collisions ; lisez par exemple http://www.realtimerendering.com/intersections.html.

Si vous avez besoin d'une intersection précise, vous devez effectuer un test rayon-triangle. Encore une fois, ce n'est pas une bonne idée de vérifier tous les triangles de tous les modèles linéairement. Une structure accélératrice supplémentaire est nécessaire.

VIII - Remerciements

Cet article est une traduction autorisée dont le texte original peut être trouvé sur opengl-tutorial.org.

Navigation

Sommaire