Introduction
Chaque structure d’accélération de niveau inférieur (BLAS) possède un AABB stocké à la racine qui englobe l’ensemble de la BLAS. Cet AABB se trouve dans le même espace que la géométrie, c’est-à-dire l’espace objet. Lors de l’insertion d’une instance d’une BLAS dans une structure d’accélération de niveau supérieur (TLAS), les limites de l’instance doivent être déterminées dans l’espace monde. L’approche naïve consiste à transformer les coins de l’AABB en espace objet vers l’espace monde et à former un nouvel AABB. Si la transformation comporte une rotation, cela gonflera l’AABB dans l’espace monde, ce qui augmentera sa surface et entraînera davantage d’intersections faussement positives. L’AABB de référence (vérité terrain) dans l’espace monde nécessiterait de transformer chaque sommet contenu dans la BLAS vers l’espace monde et d’en calculer l’englobant. Ce n’est pas pratique, surtout à l’exécution. Il existe un compromis qui peut améliorer l’ajustement de l’AABB dans l’espace monde sans un coût d’exécution aussi élevé que l’approche de référence. Il nécessite de préconstruire une enveloppe convexe (un treillis de points) qui englobe la BLAS. Plutôt que de faire pivoter un AABB de l’espace objet vers l’espace monde, nous pouvons faire pivoter ce treillis et trouver ses limites dans l’espace monde. Plus le treillis est raffiné, plus l’AABB de l’instance dans l’espace monde peut se rapprocher de la référence.k-DOP
Un k-DOP est un polytope discret orienté à « k » dimensions. Il s’agit d’un volume englobant généralisé comportant « k » plans englobants. Les boîtes englobantes alignées sur les axes (AABB) et les boîtes englobantes orientées (OBB) sont des exemples de 6-DOP, formés par trois tranches englobantes (paires de plans englobants). Un icosaèdre (dé à 20 faces) est un exemple de 20-DOP.Carte des points apex
Si le k-DOP représente les faces planes d’un maillage englobant, les points apex en sont les sommets. La carte des points apex (apex point map) désigne une méthode permettant de rechercher le point apex dans n’importe quelle direction donnée. On l’appelle point « apex » parce qu’il s’agit d’un point extrême du volume englobant.Implémentation
Nous appliquerons les concepts du k-DOP et de la carte des points apex pour générer une enveloppe convexe bien ajustée servant de volume englobant. Plutôt que de transformer tous les sommets de l’enveloppe vers l’espace monde, nous projetterons les vecteurs de base dans la carte des points apex pour obtenir les points extrêmes dans ces directions. Nous n’avons besoin de transformer que ces six points, car ce sont les points les plus extrêmes sur les axes X, Y et Z de l’espace monde. XDXR construit d’abord le k-DOP dans la mémoire de travail. Cela ressemble à la formation d’un AABB. Pour chaque plan du k-DOP, chaque sommet est projeté sur sa normale, et la distance maximale par rapport à l’origine est calculée. La normale et la distance définissent le plan englobant. Les normales des plans du k-DOP devraient idéalement être réparties uniformément sur la sphère unité, mais pour plus de commodité et pour faciliter la génération d’une table de correspondance, nous prenons plutôt des points à la surface d’un cube pour former les vecteurs normaux. Les faces du cube sont tessellées en NxN cellules carrées, où N est le facteur de tessellation. (Notez que N=1 équivaut à un AABB.) La taille du k-DOP (à partir du GDK de juin 2022) peut être calculée à partir du facteur de tessellation. Le nombre de sommets sur un côté du cube tessellé est (N+1)2.SizeOfKDOP = (N + 1) * (N + 1) * 6 * sizeof(float)
Une fois le k-DOP construit, nous pouvons former les points apex pour les régions délimitées par trois normales de plans. Rappelez-vous que les plans du k-DOP sont comme les faces d’un polyèdre, et que les points apex en sont les sommets. Pour trouver chaque point apex, nous intersectons trois plans. Chaque région carrée tessellée comporte quatre plans et, par conséquent, deux points apex. Chaque côté du cube tessellé comporte 2*N2 points apex.
SizeOfAPM = (2 * N * N) * 6 * sizeof(float3)
Remarque : seule la carte des points apex est conservée dans la BLAS finale. Le k-DOP n’est pas nécessaire à l’exécution.