instances et lancer de rayons ?

Toutes les scènes ne sont pas décrites par un seul maillage / objet. dans pas mal de cas, on utilise plusieurs instances du même objet placées à des endroits différents de la scène. Il est bien sur possible de dupliquer tous les triangles (sans oublier de transformer leurs sommets...) et de construire une seule structure accélératrice comme expliqué dans le lancer de rayons, ça rame ? ou pas ? et construction de BVH optimal, SAH et parcours efficace, mais il y a souvent trop de triangles dupliqués, et le temps de construction de l'arbre augmente fortement (et dans certains cas, il n'est pas possible de stocker tous les triangles instanciés).

exemple : la scène du tp 2022, contient au total 36M de triangles instanciés

cette scène est composée de 200 objets uniques et de 6M de triangles... mais les objets sont instanciés plusieurs fois : la scène utilise 15000 instances et au final, il y a bien 36M de triangles.

et dans certains cas, il n'est pas possible de stocker les triangles dupliqués, par exemple cette scene de test de pbrt3, qui instancie ~3 milliards de triangles...

construire un arbre sans dupliquer les instances ?

comment ? euh en faisant la même chose ? si on regarde un peu plus précisement le fonctionnement des méthodes de construction des bvh, il est assez facile de se rendre compte que seules les boites englobantes des triangles sont utilisées...

du coup, on peut voir un bvh comme un arbre qui trie / organise des boites englobantes, sans se préoccuper des objets à l'intérieur des boites. on va donc pouvoir construire un bvh uniquement en fonction des englobants des instances (dans le repère de la scène) !

mais comment représenter la transformation qui place chaque instance dans la scène ? chaque instance est décrite par un objet et une transformation model, qui permet de transformer les sommets des triangles du repere de l'objet vers le repere de la scène. les rayons sont générés dans le repère de la scène, pas de problèmes pour calculer les intersections rayons / englobtans dans la scène, mais pour calculer les intersections rayons / triangles, il faut choisir un repère commun...

celui de la scène ? plutot celui de l'objet : il suffit de transformer l'origine et la direction du rayon dans le repère local de l'objet pour calculer les intersections avec ses triangles. il faut donc connaitre la transformation inverse de model, pour transformer le rayon et réaliser les calculs d'intersection.

pourquoi dans ce sens ? il est nettement plus rapide de transformer le rayon (un point et une direction) que de transformer tous les sommets des triangles de l'objet...

on va donc construire un bvh avec les englobants de chaque instance dans le repère de la scène. par contre, les feuilles de ce bvh stockent la transformation de la scène vers le repère de l'objet et une reference vers les triangles de l'objet. bien sur, pour calculer les intersections d'un rayon avec les triangles d'un objet, on va aussi construire un bvh... au final on va construire un bvh par objet dans son repere et un bvh global qui reference chaque instance dans le repere de la scene !

cette organisation s'appelle un bvh à 2 niveaux, l'arbre d'instances est le premier niveau (ou top level bvh) et les bvhs de triangles des objets forment le second niveau ou bottom level bvh.

TLAS : top level acceleration structure / bvh d'instances

comment construire le bvh des instances ? facile : de la même manière que l'on construit un bvh sur des triangles... en regardant les algos de construction de bvh, il est assez facile de vérifier qu'ils utilisent uniquement 2 propriétés des triangles : l'englobant et la fonction d'intersection...

struct Triangle
{
    { ... }     // representation du triangle
    BBox bounds;
    Hit intersect( const Ray& ray, const float tmax );
}

du coup, il suffit de représenter une instance de la même manière pour pouvoir construire un bvh sur un ensemble d'instances :

struct Instance
{
    { ... }     // representation de l'instance
    BBox bounds;
    Hit intersect( const Ray& ray, const float tmax );
};

il y a 2 manières de le faire en c++, soit en créant une classe de base, Primitive par exemple, dont dérivent les structures Triangle et Instance, soit en transformant le bvh en template...

template< typename T >
struct BVHT
{
    std::vector<T> primitives;
    std::vector<Node> nodes;
    int root;
    
    void build( const std::vector<T>& _primitives );
    Hit intersect( const Ray& ray );
};
 
typedef BVHT<Instance> TLAS;
typedef BVHT<Triangle> BLAS;
typedef BVHT<Triangle> BVH;

remarque : transformer le bvh en fonction du type des primitives qu'il stocke / organise est quand meme plus simple et plus efficace que d'utiliser une classe de base Primitive dont dérivent Triangle et Instance. la version template n'a pas besoin d'utiliser des appels de fonctions virtuelles sur les classes dérivées de Primitive.

remarque: on peut aussi construire explicitement le bvh sur un ensemble de boites englobantes qui referencent un objet ou un autre bvh...

intersection

on vient de construire le bvh des instances, mais comment l'utiliser pour calculer les intersections d'un rayon ? les englobants des instances sont dans le repère de la scène, le rayon aussi, mais lorsque le rayon visite une feuille du bvh, il faut aussi parcourir le bvh de l'objet instancié. Mais avant de commencer le parcours du bvh de l'objet, il faut transformer le rayon dans le repère de l'objet.

c'est la fonction instersect d' Instance qui va faire cette transformation :

Hit Instance::intersect( const Ray& ray, const float tmax )
{
    Ray object_ray;
    { ... } // transformer l'origine et la direction du rayon 
    { ... } // continuer le parcours dans le repere de l'objet...
    { ... } // et s'il y a une intersection ??
    return hit;
}

pour transformer un rayon, pas de problemes, connaissant la transformation vers le repere de l'objet : il suffit de transformer l'origine et la direction :

object_ray.o= object_transform(ray.o);
object_ray.d= object_transform(ray.d);
object_ray.tmax= hit.t;

par contre, les valeurs de tmax et de hit.t ne changent pas lorsque l'on transforme le rayon...

pourquoi ? faites le calcul et vérifiez que t ne change pas !
indication : si on connait les coordonnées du point d'intersection, l'origine et l'extremite (ou la direction) du rayon, comment s'écrit la transformation ? quelle est la valeur de t dans chaque repère ?

maintenant que le rayon est dans le bon repère, il suffit d'appeler la fonction d'intersection du bvh de l'objet :

Hit hit= object_bvh->intersect(object_ray, tmax);

et c'est fini ! eventuellement on peut stocker l'indice de l'instance et de l'objet dans la structure hit, si c'est nécessaire, par exemple pour interpoler la normale ou les coordonnées de texture au point d'intersection.

maintenant que l'on sait quoi faire, il suffit de compléter la structure Instance avec la transformation et le bvh :

struct Instance
{
    Transform object_transform;
    BBox bounds;
    int mesh_index;
    int instance_index;
    BVH *object_bvh;
    
    Hit intersect( const Ray& ray, const float tmax );  
};

BLAS : bottom level acceleration structure / bvh de triangles

rien à signaler, c'est la même chose que d'habitude, un bvh construit sur un ensemble de triangles dans le repère de l'objet.

repassez dans la section sur la construction des bvh dans le lancer de rayons, ça rame ? ou pas ?, si nécessaire.

oulala, c'est compliqué, c'est ou le code ?

un exemple tout simple est dispo dans tuto_bvh2.cpp. il charge un fichier .obj / wavefront, crée quelques instances disposées sur une ligne et calcule les intersections.

un exemple plus complet qui charge un fichier gltf est dans tuto_bvh2_gltf.cpp. chaque GLTFMesh de la scène est utilisé pour construire un BLAS et ensuite un TLAS est construit à partir des instances représentées par les GLTFNode.

remarque : le code de construction est équivalent mais simplifié par rapport à celui décrit dans le lancer de rayons, ça rame ? ou pas ? / section bvh.

remarque sur le code d'exemple : les triangles stockent les positions de leurs sommets (pour calculer directement les intersections avec les rayons), ainsi que les indices de l'instance, du mesh et du groupe de primitives, que l'on peut utiliser ensuite pour interpoler les normales, les coordonnées de sommets, etc. mais pourquoi ne pas tout stocker dans le triangle ? ou n'utiliser que les indices des sommets ?

c'est un compromis : si chaque triangle stocke la position, les coordonnees de texture et les normales des sommets, toutes ces informations sont dupliquées, alors que les maillages de la scène sont indexés et nécessitent moins de mémoire. ce n'est pas très grave pour des scènes de taille raisonnable, mais ca limite la complexité de la scène que l'on peut stocker en mémoire. la solution proposée ne duplique que les positions, ce qui permet de faire des tests d'intersection plus rapides que si le triangle n'etait représenté que par son indice... (moins d'indirections et meilleure organisation mémoire pour les caches)

et ça marche vraiment bien ?

sur une scène raisonnable on peut comparer les 2 solutions : un seul arbre avec tous les triangles dupliqués ou un bvh à 2 niveaux... selon la répartiton des englobants des instances dans la scène, il est fréquent que le calcul d'intersection soit 2 fois plus lent avec le bvh à 2 niveaux. si, au contraire les instances sont bien séparées dans la scène, il y a peu de différence, mais c'est rarement le cas, surtout avec la végétation...

bien sur, on peut construire l'arbre d'instances de manière un peu plus astucieuse : au lieu de prendre l'englobant de chaque instance, on peut le découper (il suffit de parcourir le bvh / btlas de l'objet) et réduire les chevauchements des englobatns dans la scène, mais c'est un compromis entre quantité de mémoire nécessaire pour stocker tous ces nouveaux englobants et le temps de parcours de l'arbre complet (tlas + blas).

pour les curieux "Improved Two-Level BVHs using Partial Re-Braiding", C. Benthin, S. Woop, I. Wald, A. Afra 2017
et slides