Archives par étiquette : octree

Moteur physique sur GPU basé sur le Cubemapping

Habituellement les moteurs physique WebGL ( ce qui empêche le joueur de passer à travers le décor ) tournent sur le CPU (Central Processing Unit) et non sur le GPU (Graphic Processing Unit).

Dans les applications compilées, la physique peut être calculée sur GPU, soit en utilisant des shaders comme le geometry shader auxquels on n’a pas accès en WebGL, soit en utilisant des fonctionnalités matérielles spécifiques, comme PhysX pour les carte graphiques Nvidia. Mais pour les applications WebGL, la physique est ramenée à des collisions sphère/octree calculées sur CPU.

L’octree (arbre contenant toutes les faces de la scène) est soit pré-calculé et inclus dans les données, soit calculé lors du chargement de la scène. Dans tous les cas, il alourdit le chargement. Quant au moteur physique en Javascript, il requiert beaucoup de calculs de collisions pour chaque image générée.

Je détaille le fonctionnement d’un tel moteur physique dans mon ouvrage WebGL : Guide de programmation d’applications web 3D.

Je présente ici une façon très différentes de calculer la physique. Elle ne nécessite ni de calcul d’octree, ni de calcul d’intersections sur CPU via des méthodes dérivées de l’utilisation des coordonnées de Plücker et du théorême de l’axe séparateur. Presque tout est effectué sur le GPU.

Capture d’écran de la démonstration :

Capture d'écran de la démonstration du moteur physique basé sur le cubemapping

Capture d’écran de la démonstration disponible sur http://spacegoo.com/publis/cubemapPhysics/implementation

Cliquez ici pour lire la publication détaillant le fonctionnement de l’algorithme (en anglais)

Cliquez ici pour jouer à la démonstration (utilisez les flèches du pavé directionnel du clavier pour vous déplacer, et la barre d’espace pour sauter),

Cliquez ici pour télécharger le code source de la démonstration

Cet algorithme est intéressant à implémenter pour des applications où la physique se résume à des collisions personnage/décor. S’il y a de nombreuses interactions physiques à calculer (interactions objet-objet notamment), il vaudra mieux passer par des algorithmes plus classiques basés sur l’utilisation d’octree.

New webgl demo : Tiananmen 1989

En ces temps où le contrôle de la liberté d’expression est plus que jamais un sujet à la mode, notamment grâce aux révolutions arabes et aux dernières révélations de wikileaks sur les entreprises occidentales ayant vendu des technologies de surveillance électronique à des dictatures ( http://wikileaks.org/the-spyfiles.html ), nous dévoilons notre nouvelle démo webgl consistant en un espace dédié à la liberté d’expression.

Avant d’aborder les aspects techniques de cette démonstration, je vais me permettre une rapide digression par rapport au sujet principal de ce blog, sur les évènements historiques l’ayant inspiré.

A partir du 15 Septembre 1989, un important mouvement populaire se forme sur la place Tiananmen, à Pékin. Ce mouvement est mené essentiellement par des étudiants, des intellectuels et des ouvriers. Ces deniers demandent des réformes politiques et démocratiques. Bien que ce mouvement soit totalement pacifique, le gouvernement communiste chinois met en place la loi martiale le 20 mai. A partir du 4 Juin, l’armée populaire ouvre le feu sur la foule. Le nombre de morts n’a pas été évalué avec certitude, et oscille entre plusieurs centaines et quelque milliers.

En Juin 1989, un manifestant  se place sur le chemin d’une colonne de chars, sur l’avenue Chang’An, qui borde la place Tiananmen au nord. Si l’identité de cet homme n’est pas connue, cette image est mondialement célèbre de par son puissant symbolisme.

Actuellement, même si la Chine n’est plus celle de Mao, elle reste une dictature communiste où la liberté d’expression est contrôlée et où les médias sont censurés. Leur outil de censure de l’Internet, le GFW (pour the Greate FireWall )  ne cesse de se perfectionner : il filtre le contenu des paquets lisibles, bloque les proxies, effectue du DNS poisoning, relentit les connexions HTTPS et de nombreux VPN, ….

Notre démonstration fige cet instant historique, et transforme ce symbole de la répression en un lieu de liberté d’expression. Tout internaute peut peindre et coller des images sur les chars, sur le sol ou sur le monument à la gloire des héros du communisme. Les modifications peuvent être sauvegardées sur le serveur de sorte à les partager.

Au niveau technique, les maillages ont été exportés de Blender. Les intersections se font via un octree créé à l’exportation de Blender, et non plus au chargement en javascript comme dans notre précédente démo Cadillac Ranch . Le serveur recréé le processus de création effectué côté client avec GD, la librairie de gestion d’images de PHP.

La démonstration est disponible ici : http://www.spacegoo.com/tiananmen

Et la vidéo capture d’écran pour les non compatibles webgl (profitez de Noël pour changer de PC ) :

Tiananmen 3D
Runtime
2:25
Compteur de vues
398

 

Nouvelle démo : le Cadillac Ranch

Le Cadillac Ranch est une oeuvre d’art monumentale collaborative localisée à Amarillo, au Texas, sur le tracé de l’ancienne Route 66. Elle a été conçu en 1974 par Chip Lord, Hudson Marquez et Doug Michel. Elle est constituée de 10 anciennes Cadillac alignées, à enterrées à moitié dans le sol par l’avant.

SPACEGOO a créé une version virtuelle du Cadillac Ranch : elle représente 10 Cadillac plantées dans le sol, et vous pouvez les peindre et vous promener autour. Les modifications que vous apportez aux Cadillac sont enregistrées, et les compressions successives des textures au format JPG entraine un vieillissement progressif des plus anciennes peintures. C’est une oeuvre d’art en 3D pour laquelle chaque internaute peut apporter sa contribution.

Utilisez les touches directionnelles et la molette de la souris pour vous déplacer, et pour peindre déplacez la souris avec le clic gauche enfoncé. Pour changer l’angle de la caméra, vous pouvez déplacer la souris avec le clic droit enfoncé.

Cliquez ici pour lancer la démo

Si vous n’avez pas un ordinateur webgl friendly, vous devrez vous contenter de la vidéo capture d’écran :

Il s’agit à notre connaissance de la première oeuvre d’art collaborative en 3D en ligne. Au niveau technique la principale difficulté a été d’implémenter un algorithme de calcul d’intersection utilisant un octree en javascript.

Le picking en WebGL

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.

découpage de l'espace en octreeLe 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 :

octree lié à l'exemple

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.

Xavier Bourry – © SPACEGOO 2011