SPACEGOO Blog | La troisième dimension et l'Internet

WebGL est un binding d’OpenGL ES pour javascript. OpenGL ES étant conçu pour les systèmes embarqués, celui-ci ne dispose pas de toutes les fonctionnalités d’OpenGL. Si certaines ne peuvent pas être remplacées, comme la disparition de certains shaders tel le geometry shaders dans OpenGL ES, d’autres peuvent êtres implémentées en utilisant des méthodes différentes, comme le picking.

Le picking consiste à pouvoir sélectionner un objet dans la scène 3D. Cela revient à associer un objet aux coordonnées (x, y) de la souris survolant la scène.

I/ Le selection buffer

Dans OpenGL, la technique la plus utilisée est celle du selection buffer :

Le selection buffer contient pour chaque pixel de la vue une référence à l’objet affiché. Il est actualisé lors du dessin de chaque objet dans le backbuffer. Chaque framebuffer est associé à un selection buffer.

L’avantage de cette technique est sa simplicité et le fait que le temps de calcul nécessaire au picking ne dépend ni du nombre de clics, ni de la position des objets.

II/ Première solution : en utilisant le canal alpha

WebGL ne dispose pas de sélection buffer. S’il y a peu d’objets (moins de 256), on peut ruser sous mozilla en utilisant le canal alpha :

dans le fragment shader, on déclare une variable uniforme contenant l’id de l’objet entre 0 et 255, et une variable uniforme objet_id :

uniform int objet_id;
[…]
void main(void) {
[…]
gl_FragColor[3]=objet_id/256; //set alpha canal to objet id
}

Lors du clic sur un pixel de la vue ayant pour coordonnées (X, Y), on fait appel à la fonction readpixel pour récupérer la valeur du canal alpha du pixel cliqué :

var buf = new Uint8Array(4);
gl.readPixels(X, Y, 1, 1, gl.RGBA, gl.UNSIGNED_BYTE, buf);
objet_id=buf[3];

Pour que le canvas apparaisse toujours opaque, il convient d’utiliser l’attribut mozOpaque :

gl = canvas.getContext(« experimental-webgl », {antialias:true});
canvas.mozOpaque=true;

Là vient un inconvénient de cette méthode : les navigateurs autre que Firefox n’ont pas d’attribut équivalent à mozOpaque.
De plus, l’attribut mozOpaque fait que Firefox active l’anti-crenelage et le flou cinétique. Ces deux fonctionnalités peuvent entraîner un ralentissement dans l’affichage, ou des effets graphiques indésirables.

Si le nombre d’objets est très faible, on peut donner des objet_id proches de 255. Par example s’il n’y a que 3 objets, on peut leur donner pour id 252, 253 et 254, le restant de la scène étant dessiné avec une opacité de 255. Entre un pixel ayant pour opacité 252 et un autre ayant pour opacité 255, la différence de perception sera moindre.

III/ Deuxième solution : par lancer de rayon

A partir des coordonnées du point cliqué ainsi que de la matrice des projections inversées, on calcul le vecteur k correspondant à la direction pointée :

k=^tM(P^-1(2*X/L-1,2*Y/l+1));

Où M est la matrice des mouvements (rotations + translations)
L et l sont les dimensions de la vue (hauteur et largeur)
X et Y sont les coordonnées du curseur
P est la matrice de la projection.

Ensuite la solution la plus simple consiste à vérifier que la demi droite formée par les points P=ak, avec a positif, intersecte les objets à sélectionner.

Pour calculer l’intersection entre une droite et un triangle en temps optimal sans avoir à résoudre le système formé par les équations du plan et de la demi-droite, on pourra utiliser les coordonnées de Plücker.

III/Méthodes pour accélérer le lancer de rayon

Le problème du lancer de rayon est que cette technique peut être très consommatrice en temps de calcul si on teste beaucoup d’intersections, c’est à dire s’il y a beaucoup d’objets sélectionnables sur la scène ou si ces objets ont un maillage fin.

Si l’objet est complexe, on pourra l’approximer par des sphères englobant à peu près ledit objet. Ce calcul devra être effectué avant d’afficher la scène.

Une autre méthode est celle de l’octree : on divise l’espace en cubes, et on place les cubes dans un arbre. A chaque cube on associe les objets susceptibles d’être sélectionnés.

Lors d’un lancer de rayon, on calcule les intersections entre le rayon et les cubes de l’octree. Puis pour chaque cube, on teste les intersections entre le rayon et les objets compris dans le cube.

Exemple :

On considère une scène comprise dans un espace cubique compris entre -2 et +2 sur les coordonnées X,Y. La caméra est au point O(0,0). Cet exemple est pleinement interposable en 3D.

Le point cliqué correspond à la direction pointée en rouge, et la demi-droite est représentée en vert.

Le quadtree créé lors du chargement de la scène présente la forme suivante :

En dimension 3, on aurait un octree avec 8 branches par noeuds. Pour des raisons de lisibilité, toutes les branches n’ont pas été représentées.

On prend e toute petite valeur positive. Par exemple e=0.001
On considère le point O’=O+e*k
D’après notre quadtree, en 2 tests on trouve que O’ est dans le carré 7.
S’il intersecte un objet compris dans le carré 7, on s’arrête sinon on continue.

On calcule A, deuxième intersection entre le rayon et le carré 7.
On calcule A’=A+e*k
D’après le quadtree, A’ est dans le carré 5
Si le rayon intersecte un objet compris dans le carré 5, on s’arrête sinon on continue.

On calcule B, la deuxième intersection entre le rayon et le carré 5, et B’=B+e*k
B’ est dans le carré 6.
Si le rayon intersecte un objet compris dans le carré 6, on s’arrête sinon on continue.
6 est en bordure de scène, donc on s’arrête.

Cette méthode permet de ne pas tester systématiquement tous les objets, et surtout de les tester dans le bon ordre.

Par exemple si chaque carré contient 5 objets, on aura effecté au plus 3*5*2=30 tests au lieu d’en effecter 5*16=80 tests.

A chacun sa méthode …

Il n’y a pas une solution qui pourrait être optimale pour tous les programmes webgl faisant appel au picking. Chaque programme a ses spécificités qui feront qu’une implémentation sera plus performante que l’autre. Dans la méthode du lancer de rayon, de nombreux paramètres sont ajustables : la finesse du maillage de l’octree, la méthode utilisée pour tester l’intersection avec les objets…

A noter que la première méthode peut venir pour aider l’optimisation de la seconde : on attribue à chaque pixel pickable une valeur alpha de 255 et à chaque pixel non pickable une valeur alpha de 254, et si l’utilisateur a sa souris sur un pixel ayant une valeur alpha de 254, on n’a pas à lancer de rayon.