détection collision rayon triangle par shader

salut,
je cherche un exemple qui permettrait de tester la collision entre une liste de triangles et un rayon mais par le gpu (sans passer par CUDA, car je bosse sur webgl) et non par cpu... je n'ai pas trouvé de quoi sur google... peut être mes mots clés...

si vous n'en connaissez pas, j'ai quelques idées à soumettre, et je ne suis pas contre le fait de monter cette idée à plusieurs... car surement utile à beaucoup de monde...


idées :

on sait que le vertex shader prend point par point, donc difficile de tester un triangle... par contre si à la place de stocker un point on en stocke 3 (le triangle), ça résoudrait une partie du test...

je m'explique, actuellement on empile dans le vbo,
point 1, point 2, point 3 (ça fait un triangle),
point 4, point 5, point 6 (ça fait un triangle),
...

la si on fait :

point 1, point 4, point 7 (vbo 1)
point 2, point 5, point 8 (vbo 2)
point 3, point 6, point 9 (vbo 3)

on envoi ensuite les 3 vbo au shader

ça permettrait d'avoir les 3 points du triangle en une fois...

le tout est de savoir comment indiquer quel triangles sont touchés... la seule réponse est décrire le résultat dans une texture...

- on peut imaginer plusieurs façon, appliquer une couleur à chaque triangle (dans un vbo) et écrire ensuite la liste 1 triangle par pixel

- mettre dans un vbo une sorte d'indice de tableau , ca ressemblerait donc à
0,1,2 ( 0 = triangle 1 p1 p2 p3, 1 = triangle 2 p4 p5 p6, ...) et renvoyer cette indice sous forme de couleur (implique un codage d'entier en couleur)

- renvoyer directement les coordonées des 3 points mais ça me semble le plus contraignant en terme de stockage dans la texture.

le tout est de savoir quoi mettre dans le fragment shader...

si vous avez des idées ?

on peut imaginer la même chose pour des tests entre rayon et obb, ....
plus compliquer je pense entre triangles et triangles, ou obb et obb ...

Salut,

Plusieur mots clé en vrac. Peut être que ça pourra t'aider.
-> geometry shader. Le geometry shader se calle après le vertex shader et connait les 3 vertex du triangles, pas besoin de faire des magouille sur tes VBO donc :)

-> GL_EXT_image_load_store (GL 4.2, assez récent donc). Cette extension magique permet de lire et surout d'écrire n'importe où dans une texture. Pas besoin de faire des bidouilles à base de FBO pour remplir sa texture.

-> GL_ARB_transform_feedback. Permet de récupérer la sortie du vertex ou geometry shader sur CPU. Tu peux donc "discarder" les triangles qui n'intersectent pas et garder uniquement les triangles qui intersectent.

Bonjour,

Si on veut vraiment y arriver, je pense qu'une solution serait de passer les positions des vertex dans texture (texture 1D par exemple) que l'on parcourra dans le pixel shader.
Comme nous sommes dans un pixel shader, il est très simple d'écrire le résultat (dans un FBO).

Donc, disons :

• pour chaque pixel de l'écran (pixel shader exécuté en dessinant un quad de la taille de l'écran)
• on lance un rayon
• on parcours la texture où sont stockés les objets pour détecter la collision avec le rayon
• on stocke le résultat en sortie

Après, ce qui me fait peur, c'est le parcours de la texture pour les détections de collision. Mais, y a une chance que ce ne soit pas trop lent.

Finalement, je conseillerai le super live coding de Iq qui nous fait un raytracer en 20 minute tout en GLSL :
http://www.youtube.com/watch?v=9g8CdctxmeU

@pyros
J'avais pensé aussi à ça... mais "webgl", donc pas de geometry shader, si GL_EXT_image_load_store (par contre, je crois que le transform feedback est dispo)

@LittleWhite
On est un peu différent d'un raytracer, qui utilise un lancé de rayon par pixel (voir plus). Ici, il y a qu'un seul rayon lancé, identique pour tous les triangles si j'ai bien compris (on est plus sur un technique de picking)

@dark poulpo
Pour mettre des données, tu peux utiliser (en gros) ce que tu veux. VBO me semble très bien. Pour la sortie, le plus simple est effectivement d'écrire sur une texture

Par contre, tu ne dis pas le nombre de triangles, pourquoi tu veux faire ça sur GPU et quel est l'utilisation que tu en fais. Si tu passes ton temps à envoyer et recevoir des données au GPU, il est probable que tu n'aies pas de meilleurs performances que sur le CPU (surtout si tu utilises les SSE du processeur)

Sinon, mathématiquement, les calculs sont simples : tu as 2 vecteurs formés par 2 côtés du triangle, ça te donne un plan, tu recherches les coordonnées du point d'intersection du rayon avec le plan (en utilisant de simples produits scalaires), si les coordonnées dans ce plan sont compris entre 0 et 1, c'est dans le triangle (en fait, il faut que x+y < 1 pour être dans le triangle et pas dans le rectangle)

Bon courage

Citation:

---

Envoyé par gbdivers

Par contre, tu ne dis pas le nombre de triangles, pourquoi tu veux faire ça sur GPU et quel est l'utilisation que tu en fais. Si tu passes ton temps à envoyer et recevoir des données au GPU, il est probable que tu n'aies pas de meilleurs performances que sur le CPU (surtout si tu utilises les SSE du processeur)

---

A ma connaissance, seule l’extension Firefox River Trail permet la parallélisation sur CPU, mais je n’ai pas pas pu le tester :cry: car je n'ai pas les outils nécessaire pour le compiler et n’ai pas trouvé de binaires de cet extension :calim2:

Sinon faut attendre une implémentation de WebCL en cours de normalisation par Khronos, il existe une implémentation de WebCL et WebGL pour la plateforme NodeJS

Ah, si c'est juste un rayon, pourquoi vouloir faire ça coté GPU du coup ? Le javascript est trop lent ?

Citation:

---

Envoyé par p3ga5e

A ma connaissance, seule l’extension Firefox River Trail permet la parallélisation sur CPU, mais je n’ai pas pas pu le tester :cry: car je n'ai pas les outils nécessaire pour le compiler et n’ai pas trouvé de binaires de cet extension :calim2:

Sinon faut attendre une implémentation de WebCL en cours de normalisation par Khronos, il existe une implémentation de WebCL et WebGL pour la plateforme NodeJS

---

Oui, effectivement, j'ai parlé un peu vite.

Du coup, entre une approche séquentielle en JS (interprété) et une approche GPU, même avec le surcoût pour le transfert des données, cela peut être plus rapide

@LittleWhite
Je crois, le JS reste de l'interprété (même s'il est optimisé), c'est relativement lent pour faire du calcul

JavaScript est de plus en plus rapide, les interpréteurs (V8 de Chrome et SpiderMonkey de Firefox) utilisent le Juste IN Time tous comme Java et c#, toute fois j’ai remarqué une baisse de perfs entre , un code Javasript exécuté, sur l’interpreteur et sur le navigateur. Les navigateurs trainnent, de lourde casseroles comme le DOM .
De plus le système d’encapsulation de tas mémoires managés (les closures) , bien que génialissime, doit coûter niveau performances également !

Citation:

---

A ma connaissance, seule l’extension Firefox River Trail permet la parallélisation sur CPU

---

J’ai oublié un grand acteur, qui permet la parallélisation CPU sur navigateur (et processeur Intel uniquement) les Shaders de Flash

merci pour vos réponses et idées...

j'ai environ 70000 triangles voir 100000...

j'ai pensé à les classer par obb, mais ça oblige à les créer... et le faire n'est pas chose aisée, j'avais fait un code pour ça sous xna, mais au final ils n'étaient pas aussi bien que les obb affichés sur les modeleurs type blender... il faut dire qu'il n'y a pas vraiment de doc claire sur ça ou d'exemple de code quand ça devient trop mathématique. Bref, comme le gpu est assez rapide pour traiter si peu de triangles, je me suis dit que ce sera bien plus rapide de tester mon rayon avec chaque triangle directement...

une soluce au quel je viens de penser à l'instant, ce serait aussi de donner une couleur a chaque groupe de triangle, et lire la couleur de retour pour connaitre le groupe de triangles a tester... ce serait peut être plus rapide que de faire des obb... l’inconvénient des collisions par couleur sont la distance... dès que ça devient très éloignés, on perd toute la précision... mais bon à chaque demande sa solution.

WebCL c'est quoi? l'équivalent de OpenCL ?