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 de l’espace objet vers l’espace monde et à former un nouvel AABB. Si la transformation comporte une rotation, cela gonfle l’AABB dans l’espace monde, ce qui augmente sa surface et entraîne davantage d’intersections faussement positives. L’AABB exact 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, en particulier à l’exécution. Il existe un compromis qui peut améliorer l’ajustement de l’AABB dans l’espace monde avec un coût d’exécution bien moindre que l’approche exacte. Il nécessite de préconstruire une enveloppe convexe (un réseau 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 réseau et trouver ses limites dans l’espace monde. Plus le réseau est raffiné, plus l’AABB de l’instance dans l’espace monde peut se rapprocher de la vérité exacte.k-DOP
Un k-DOP est un polytope orienté discret à « k » dimensions. Il s’agit d’un volume englobant généralisé doté de « 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 dalles englobantes (paires de plans englobants). Un icosaèdre (dé à 20 faces) est un exemple de 20-DOP.Apex Point Map
Si le k-DOP représente les faces planes d’un maillage englobant, les points apex en sont les sommets. L’apex point map désigne une méthode permettant de rechercher le point apex dans une direction donnée. On l’appelle point « apex » parce qu’il s’agit d’un point extrême du volume englobant.Implémentation
Nous allons appliquer les concepts du k-DOP et de l’Apex Point Map pour générer une enveloppe convexe très ajustée servant de volume englobant. Plutôt que de transformer tous les sommets de l’enveloppe vers l’espace monde, nous projetons les vecteurs de base dans l’apex point map afin d’obtenir les points extrêmes dans ces directions. Il suffit de transformer 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 à 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 par commodité et pour faciliter la génération d’une table de correspondance, nous utilisons 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 une face 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 des 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 calculons l’intersection de trois plans. Chaque région carrée tessellée possède quatre plans et, par conséquent, deux points apex. Chaque face du cube tessellé possède 2*N2 points apex.
SizeOfAPM = (2 * N * N) * 6 * sizeof(float3)
Remarque : seule l’apex point map est conservée dans la BLAS finale. Le k-DOP n’est pas nécessaire à l’exécution.