J'ai des milliers de OOBB (boîtes orientées objet) dans l'espace 3d qui englobent des maillages 3d allongés simples. Ils sont étroitement emballés ensemble. Je voudrais tirer des rayons sur eux et déterminer quels sont les OOBB qui sont touchés. En raison du nombre de tests d'intersection de rayons que je dois effectuer (en millions), une approche de force brute contre tous les OOBB ne suffira pas. A l'origine, je pensais qu'il serait facile d'utiliser un système de partitionnement spatial pour réduire rapidement les résultats potentiels, mais des systèmes tels que BVH ou KDTrees reposent sur des AABB (bounding bound bound box) pour accélérer les requêtes et dans mon cas, serait très inefficace (parce que beaucoup de mes OOBB serrés ont à peu près le même AABB en raison de la nature diagonale du maillage qu'ils englobent). Je lis à propos des OBBTrees dans la bibliothèque RAPID, mais il semble qu'ils soient construits de haut en bas (commencer par soupe de polygones et se subdiviser en groupes de plus en plus petits de OOBB pour former l'arbre), plutôt que de bas en haut (début avec beaucoup de OOBB et construire un arbre d'eux).Comment tester rapidement les intersections de rayons contre un groupe restreint de OOBB?
Y a-t-il d'autres structures de données que je peux utiliser pour accélérer mes tests d'intersection?
Voici une photo de mes OOBBs. Comme vous pouvez le voir, ils sont bien emballés et si vous pouvez imaginer à quoi ressemblerait leur AABB, vous verriez qu'ils se chevauchent au point où un arbre basé sur AABB ne stimulerait pas vraiment la performance (parce que la quasi-totalité d'entre eux serait frappé par un rayon tirant à travers le centre du groupe).
Il convient de noter que j'ai besoin d'interroger tous les OOBB touchés par un rayon, et pas seulement le premier/le plus proche.
Essayez de faire tourner le rayon dans un espace où la plupart des bbs sont proches d'être abbites et d'utiliser une sorte d'algorithme de partitionnement de l'espace dans ce nouvel espace. une autre solution qui s'applique si l'objet ne change pas de rayon en rayon sauf pour une transformation linéaire: vous pouvez également générer un tableau 3D où chaque cellule a une liste de ce que les triangles/oobbs croisent, et avancer le long du rayon tableau. – programmerjake
Quelle est la dynamique de la scène? C'est-à-dire, combien de rayons allez-vous lancer jusqu'à ce que les OOBB changent, et à quel point vont-ils changer radicalement? – Angew
@programmerjake Malheureusement, la première suggestion ne fonctionnera pas car les OOBB ne seront pas toujours bien alignés comme dans mon exemple d'image. La deuxième option pourrait être plus proche de quelque chose, mais l'empreinte de la mémoire et l'exigence de prétraitement pourrait être un problème ...J'ai besoin de la solution pour travailler dans de très grands environnements 3D, où un réseau 3D ne serait pas réalisable (il faudrait des milliards de cellules pour tout inclure tout en conservant une granularité raisonnable). Mais merci pour les suggestions. – Tyson