Comment puis-je détecter efficacement la détection d'intersection d'un rayon et d'un maillage?

Question

J'ai plusieurs modèles 3D dans une application OpenGL ES pour iPhone et à un moment donné je veux que l'utilisateur touche l'écran et agisse sur eux. Le problème est de reconnaître lequel, parmi ceux rendus à l'écran, a été touché. Pour ce faire, j'ai calculé le rayon de prélèvement comme suggéré par la FAQ OpenGL, et je veux maintenant détecter si elle croise un modèle. J'ai regardé le code source d'irrlicht et j'ai trouvé que je peux calculer l'intersection entre le rayon et chaque triangle de modèle unique (ils le font en calculant si le rayon coupe d'abord le plan du triangle puis en voyant si le le point d'intersection tombe dans le triangle, mais il existe un moyen plus efficace de le faire comme indiqué here).

Ma question est la suivante: ai-je vraiment besoin de faire tout ce calcul pour chaque triangle de chaque modèle? N'y at-il pas un meilleur moyen (peut-être pas si précis) d'obtenir un résultat similaire?

Answer 1

Vous avez raison, il y a de meilleures façons de traverser l'arbre. Une méthode consiste à créer un octtree autour de l'objet. Ensuite, si le rayon intersecte l'un des 8 segments, vous pouvez vérifier lequel de ses 8 enfants il croise et ainsi de suite jusqu'à ce qu'il vous reste quelques triangles pour faire un test d'intersection. Une autre méthode consiste à créer un K-d tree.

Il existe de nombreuses façons de gérer efficacement ce problème. Rechercher des informations sur ray tracing acceleration structures.