Skip to main content

À la recherche d’une meilleure décomposition convexe

septembre

01, 2020

by Khanovich


Technologie

Roblox a introduit la géométrie de construction de solides en 2014 et soutenir la simulation physique de ce projet a été mon premier grand projet au sein de l’équipe de simulation avec Tim Loduha. À l’époque, la société était beaucoup plus petite et l’équipe de physique ne comptait que deux personnes qui avaient d’autres responsabilités en dehors du développement. Donc, en espérant obtenir des résultats rapides, nous sommes allés chercher de l’aide dans une bibliothèque très populaire appelée Bullet Physics. Bullet Physics est utilisée dans de nombreux jeux aujourd’hui en raison de son accessibilité et de sa richesse fonctionnelle. Son caractère open-source et son extensibilité en ont fait le choix naturel pour les besoins de Roblox.

Bien que le moteur de physique de Roblox soit construit en interne, nous avions besoin d’utiliser deux composants principaux de Bullet Physics pour faire fonctionner PartOperations dans les simulations :

    1. Détection des collisions à géométrie complexe
    2. La décomposition convexe pour générer une collection d’objets convexes pour la détection de collisions de géométrie 3D arbitraire (standard dans l’industrie en raison de l’espace de solution et des contraintes de performance)

Lorsque nous avons commencé à travailler sur la partie du projet relative à la décomposition convexe, nous avons testé deux algorithmes fournis par BulletPhysics :

  • Décomposition convexe approximative hiérarchique (HACD)
  • Décomposition convexe approximative (ACD)

Si nous avons apprécié les résultats du HACD, la robustesse et la cohérence de l’ACD nous ont convaincus pour la première série de produits.

Un retour d’information précis

Après le lancement de la fonctionnalité, nous avons accumulé une montagne de réactions où les utilisateurs attendaient de meilleurs résultats géométriques de la détection des collisions. L’utilisation de la voxélisation grossière par l’ACD a provoqué le déplacement ou le recouvrement de divers artefacts, tels que des surfaces importantes de seuils ou de rebords.

Vous pouvez vous représenter comment ces concavités ont été scellées en imaginant comment une forme complexe serait vue à travers les yeux d’un voxelizer (ci-dessous).

Nous avions besoin de quelque chose de mieux – quelque chose qui respecte la géométrie originale. La voxélisation n’a pas été prise en compte en raison de la façon dont les surfaces ont tendance à « s’accrocher » aux grilles de Voxel. Nous avions besoin de quelque chose qui fonctionnerait automatiquement dans la grande majorité des géométries d’entrée sans aucune correction manuelle.

Décomposition hiérarchique convexe approximative

Nous sommes finalement revenus au HACD en raison des qualités suivantes :

  • Le maillage d’entrée a été utilisé comme état initial de l’algorithme
  • Vérification des erreurs par rapport à la géométrie d’entrée originale
  • Manipulation non manuelle (tout comme l’ACD)
  • Pas de voxélisation

Sur la base du document lié ci-dessus, le HACD comporte 3 composantes principales :

  • Élimination des doubles graphiques
  • Génération de l’enveloppe convexe
  • Calcul de l’erreur de concavité

Vue d’ensemble de l’algorithme :

1. Le maillage d’entrée est pris et transformé en un graphique où chaque triangle est un nœud et chaque arête entre deux triangles est une arête dans le graphique. C’est le double graphique de départ, où chaque triangle est traité comme une enveloppe convexe initiale.

2. Nous passons en revue chaque bord du graphique et calculons l’envleoppe convexe prévue qui résulterait de la combinaison des enveloppes convexes des nœuds que le bord relie.

3. Nous utilisons cette enveloppe convexe prédite pour calculer ensuite l’erreur de concavité induite par la géométrie d’origine. Ces erreurs sont utilisées pour trier tous les bords du graphique, du moins erroné au plus erroné.

4. Enfin, nous prenons le bord avec la plus petite erreur.

a. Si l’erreur est inférieure à l’erreur de concavité maximale autorisée configurée, nous supprimons le bord (aplatissement bord) et remplaçons les deux nœuds par l’enveloppe convexe prévue du bord.

b. Si l’erreur est supérieure à l’erreur de concavité maximale autorisée configurée, nous la supprimons.

5. Chaque fois qu’un bord est enlevé par aplatissement, cela invalide les résultats d’erreur de concavitéprécédents pour les bords adjacents, nous répétons donc les étapes n° 2 et n° 3 pour les bords adjacents.

6. Nous mettons à jour les arêtes recalculées dans notre liste d’arêtes triées en fonction des nouvelles erreurs de concavité.

7. Répéter les étapes 4 à 6 jusqu’à ce que les seuls bords restants aient des valeurs d’erreur supérieures à l’erreur globale autorisée (celle-ci est configurée par l’utilisateur avant de lancer l’algorithme).

Nous avons pris la dernière version disponible du code open source HACD et l’avons testé sur quelques maillages. Certaines formes, comme la voiture, ont donné lieu à une géométrie de collision plus améliorée qu’auparavant mais d’autres maillages entrants ont donné des résultats douteux. En théorie, l’algorithme semblait bon, donc notre prochaine étape consistait à trouver la cause de ces étranges résultats.

Débuggage visuel

Comme nous ne connaissions pas bien les opérations internes de la mise en œuvre, nous avons fait la seule chose possible pour accélérer notre enquête. Nous avons écrit un debugger visuel qui enregistrerait chaque étape du processus de suppression des arêtes à double graphique et nous permettrait de passer en revue chaque modification de la géométrie originale, étape par étape.

Grâce à cet outil, nous avons pu constater qu’il y avait des problèmes dans le calcul de l’erreur de concavité et la génération de l’enveloppe convexe. Nous avons pu passer en revue et trouver des cas où une enveloppe convexe correctement formée aurait bloqué une importante et grande concavité alors que le calcul de l’erreur de concavité indiquerait que l’aplatissement des bords qui a formé cette enveloppe n’a pas du tout d’erreur. Du côté de la génération de l’enveloppe convexe, nous avons constaté que l’aplatissement des bords entraînait parfois la disparition de sommets et de faces entières. Il en résulterait des manques mineurs dans certains cas et une complète catastrophe dans d’autres.

Et avec cela, nous avons reconnu qu’il fallait creuser en profondeur et écrire notre propre logique pour chacun de ces éléments.

Calcul de l’erreur de concavité (étape 3 de l’aperçu des algorithmes)

Le but du calcul de l’erreur de concavité est de quantifier le montant des « dommages » à la géométrie originale qu’une suppression d’une arête causerait par sa création d’une nouvelle enveloppe convexe en combinant les enveloppes que l’arête relie. Le document original mentionne que cette erreur peut être suivie de nombreuses façons et la mise en œuvre a utilisé la distance la plus éloignée entre la surface originale et la surface nouvellement formée au sein de l’enveloppe convexe prédictive nouvellement formée. Nous utiliserons la même définition.

Pour acquérir cette quantité, nous avons besoin de deux types d’information :

  • Une représentation quantifiable de la géométrie de la source
  • L’enveloppe convexe prédictive qui se formerait à partir de la suppression de ce bord (étape 2 de la vue d’ensemble).

La mise en œuvre initiale du système HACD utilisait quelques points d’échantillonnage par triangle comme représentation de la surface d’origine (au cours de l’étape 1 de la vue d’ensemble). Ces points seraient ensuite utilisés pour « raycaster », le long des normales de la figure, afin de trouver la face arrière d’une enveloppe convexe qui entrave les concavités. La distance la plus longue entre la surface d’origine et la face arrière a été considérée comme l’erreur. C’est une approche raisonnable mais étant donné que la densité d’échantillonnage est une opération par triangle, nous nous sommes heurtés à des problèmes où des formes simples avec de grandes faces triangulaires avaient des angles morts considérables lors de la recherche d’objets pouvant bloquer des concavités.

Un système idéal consisterait essentiellement à essayer de faire une extraction de surface à partir des triangles de surface d’origine sur l’enveloppe convexe testée mais c’est un problème très coûteux à résoudre et à optimiser alors nous chercherons plutôt à échantillonner les surfaces des triangles d’origine, mais avec une distribution plus cohérente.

Nous allons générer uniformément des points d’échantillonnage de surface pour chaque triangle sur la base d’une distance de grille configurée (voir à gauche). Comme une grande quantité de points vont être générés, nous avons également besoin d’un moyen de filtrer rapidement les points qui doivent être vérifiés par rapport aux enveloppes convexes nouvellement formées pendant le processus de calcul de l’erreur de concavité. Pour le réaliser, nous jetons chaque point d’échantillonnage sur une grille dans l’espace, similaire à celles utilisées dans la détection des collisions et en utilisant la boîte de délimitation d’une enveloppe que nous testons pour sélectionner rapidement un groupe de points d’échantillonnage de surface à tester.

Une fois que nous avons saisi les points qui se trouvent à l’intérieur de la boîte de délimitation, nous filtrons encore les points qui sont à l’intérieur de l’enveloppe convexe nouvellement formée puisque nous essayons de capturer les concavités scellées par l’enveloppe convexe actuelle. Nous lançons ensuite ces points d’échantillonnage contre les triangles de l’enveloppe. S’il n’y a pas d’erreur ajoutée, tous retourneront des distances de zéro, mais une enveloppe convexe problématique, comme dans le diagramme ci-dessus, aura les raycasts de la surface originale qui auront impactés la face arrière d’un des triangles de l’enveloppe convexe prédictive !

En résumé, la génération d’erreurs peut être décrite comme telle :

  • (Au cours de l’étape 1 de la synthèse de l’algorithme) Échantillonnez uniformément des points sur chaque triangle et lancez-les sur une grille dans l’espace.
  • Prenez la boîte de délimitation de l’enveloppe convexe que nous testons et rassemblez tous les points de la grille à l’intérieur de cette boîte de délimitation.
  • À partir des points recueillis, pour chaque point échantillon à l’intérieur de l’enveloppe convexe, nous faisons un raycast le long de la surface normale d’origine pour voir si elle touche la face arrière de l’enveloppe convexe.
  • Le rayon avec la plus grande distance qui a frappé une face arrière finit par être notre erreur de concavité.
  • Si l’enveloppe convexe ne dépasse pas la surface d’origine, le résultat devrait être 0.
  • Il est possible d’optimiser ce processus en sortant plus tôt dès que le premier échantillon raycast dépasse l’erreur globale maximale autorisée car cela suffit à empêcher l’aplatissement d’un bord.

Ce système nous fournit un moyen fiable de vérifier les enveloppes convexes pour savoir combien d’erreur elles introduiraient dans notre forme originale mais il manque encore une chose. Cette méthode ne fonctionne bien que sur les enveloppes convexes 3D. Si l’enveloppe convexe est plate, les points de l’échantillon ne seront jamais alignés dans les directions que nous devrons tester lors de la formation d’enveloppes convexes 2D. Prenons par exemple la configuration de droite : si le triangle bleu et vert forme une enveloppe convexe et tente ensuite de se combiner avec le rouge, tout point d’échantillonnage à l’intérieur de cette enveloppe convexe n’aurait très probablement pas d’impact sur la face arrière de l’enveloppe convexe à une distance autre que 0. Pour résoudre correctement ce problème, nous devrions envisager un processus de calcul des erreurs 2D complètement différent et qui serait tout aussi intéressant que celui que nous avons décrit.

Il y a une petite astuce que nous pouvons faire à la place. Nous pouvons comparer l’aire de la somme des deux enveloppes convexes d’origine à l’aire du résultat. Si l’enveloppe obtenue a plus de surface que la somme des deux enveloppes sources, vous savez qu’elle peut fermer une concavité et donc la racine carrée de la surface supplémentaire peut être traitée comme l’erreur de concavité dans ce cas ! Et enfin, nous disposons d’une bonne méthode pour détecter les erreurs dans les candidats potentiels aux enveloppes convexes, à condition que nos enveloppes convexes d’entrée soient correctement formées !

Génération d’enveloppes convexes : Quickhull (étape 2 de l’aperçu des algorithmes)

Après avoir modifié le calcul de l’erreur de concavité, nous avons utilisé le débuggueur visuel pour confirmer que nous avions toujours des problèmes :

  1. Certaines enveloppes convexes qui scelleraient de grandes concavités passeraient encore le test d’erreur de concavité avec un résultat de 0.
  2. La combinaison de deux enveloppes convexes faisait parfois disparaître un sommet, laissant un trou dans la forme originale.

La mise en œuvre initiale du HACD utilisait une variante de l’algorithme Quickhull, qui est un choix parfait car l’algorithme est conçu pour ajouter rapidement de nouveaux points à une enveloppe convexe existante, ce que nous ferons en aplatissant les bords. Un premier examen des données collectées par notre debuggeur de visualisation a révélé que les enveloppes résultantes présentaient parfois un triangle inversé, ce qui était un obstacle à notre méthode de calcul des erreurs de concavité décrite précédemment.

La façon dont cet algorithme est censé fonctionner est que lorsque vous choisissez un nouveau point à ajouter à une enveloppe existante, vous trouvez alors des triangles pour les plans desquels le point se trouve à l’extérieur. Ces triangles sont ensuite marqués pour être supprimés, tandis que leurs bords vers d’autres triangles seront utilisés pour former un nouvel ensemble de triangles dont la pointe sera traitée pour sceller l’enveloppe convexe. Une chose que vous pouvez apprendre du discours de Valve sur l’algorithme Quickhull est qu’il est très sensible aux erreurs en virgule flottante surtout si l’une des enveloppes a des triangles coplanaires. L’exemple de droite est une coupe transversale du cas facile qui n’illustre pas le problème décrit par Valve.

Pour comprendre le problème, vous devez considérer une section transversale qui ressemble à la forme de gauche. Imaginons une situation de Quickhull où nous ne sommes pas sûrs que les triangles E et F considèrent le point à l’extérieur ou à l’intérieur de leurs plans. En fait, le pire scénario est celui où E considère le point à l’extérieur, tandis que F considère le point à l’intérieur. Dans Quickhull, comme l’orientation des triangles dépend des triangles adjacents, ce type de topologie incohérente peut soit créer des triangles mal orientés, soit entraîner un échec complet.

Dirk Gregorius de chez Valve traite ce problème en fusionnant des triangles coplanaires en objets à figures singulieres de telle sorte que ce genre d’incohérence est impossible, mais nous ne pouvons pas utiliser cette approche car la distinction entre les triangles individuels est toujours importante pour nous. Au lieu de cela, nous créons un plan solide auquel appartiennent plusieurs triangles coplanaires et nous utilisons ce plan pour nous assurer que tous les triangles qui sont reliés entre eux et qui s’inscrivent dans le plan ne peuvent résoudre le calcul que pour savoir si un point se trouve à l’intérieur ou à l’extérieur d’une manière singulière. Cela résout essentiellement le problème d’une manière similaire à la solution de fusion des figures de Dirk, tout en nous permettant de maintenir des références directes aux triangles individuels.

Comme pour le calcul de l’erreur de concavité, nous devons également tenir compte du cas 2D. Afin de protéger votre code de décomposition convexe contre une variété de données d’entrée, vous DEVEZ mettre en œuvre un Quickhull 2D ainsi qu’un Quickhull 3D pour permettre la combinaison de triangles coplanaires. Si nous essayons d’utiliser le même processus pour les triangles coplanaires, cela ne fonctionnera pas et souvent, les sommets d’entrée seront supprimés ou échoueront.

Traitement cohérent en virgule flottante

Après avoir trouvé des solutions pour la génération d’enveloppes convexes et l’erreur de concavité auxquelles nous faisions confiance et que nous comprenions, nous rencontrions encore quelques problèmes, mais le debugging visuel a révélé que c’était généralement dans les cas de surfaces semi-dégénérées.

Cela nous amène à l’une des plus importantes préoccupations en matière de géométrie 3D – le traitement cohérent des points flottants est un must. Pour que cet algorithme fonctionne de manière fiable, le concept d’epsilon et d’information quantifiée a dû être unifié.

Tout au long de l’algorithme, il y a différents points où un concept d’epsilon a été utilisé :

  • Lors de la création d’un graphique double à partir de la géométrie d’entrée, les sommets dégénérés ont été combinés en un seul sommet.
  • Tout au long de la génération d’enveloppes convexes, nous avons dû tester si les enveloppes convexes étaient coplanaires entre elles, pour décider si nous devions fonctionner en mode 2D ou 3D.
  • Lors du calcul de l’erreur de concavité, nous devions également tester la planéité de l’enveloppe actuelle, et nous avions besoin d’epsilons cohérents pour le raycasting contre l’intérieur des coques convexes.

Une fois que la distance de quantification (s) est déterminée comme une configuration de l’algorithme, nous devons traiter ce s comme l’epsilon, et aussi notre définition de la planéité. Cela signifie que tous les points qui s’inscrivent dans un seul plan de largeur s doivent être considérés comme coplanaires. Toute génération d’enveloppe convexe sur un ensemble de points qui s’inscrivent dans un plan de largeur s doit être traitée comme une opération purement 2D. En outre, toutes nos requêtes concernant les epsilons doivent être effectuées dans une seule dimension, ce qui signifie que toute requête concernant le volume ou la surface des objets doit être vérifiée par rapport aux distances maximales par rapport à un avion.

Conclusions

À la fin du processus, il est toujours amusant de prendre du recul et de se demander « Qu’avons-nous appris ? » En ce qui concerne le HACD, nous tenons à souligner l’importance des concepts de haut niveau suivants pour obtenir des résultats constants en matière de qualité :

  • Échantillonnage de surface uniforme – nous avons besoin d’un bon aperçu de la géométrie originale pour savoir si l’algorithme progresse bien.
  • Distinction entre les opérations 2D et 3D lors du calcul des erreurs de concavité, et génération de l’enveloppe convexe – l’algorithme passe une grande partie de son temps à traiter des opérations 2D à moins que votre géométrie d’entrée ne lisse des objets sans faces coplanaires. La phase 2D de l’algorithme est extrêmement importante.
  • Système cohérent de quantification et de traitement en virgule flottante – crucial pour calculer la connectivité des triangles d’entrée, aider à résoudre le problème de la face coplanaire de Quickhull et séparer les opérations 2D et 3D.

Ces trois concepts sont les piliers fondamentaux qui conduisent notre énorme refactorisation interne de la bibliothèque HACD, et nous permettent de la proposer comme un générateur générique de géométrie de collision automatique pour le maillage triangulaire de Roblox et les objets CSG. Même avec ce travail effectué, il reste encore beaucoup à faire pour améliorer encore ce système.

Il existe différentes pistes de recherche que nous aimerions suivre avec cette méthode :

  • Parallélisme, amélioration des performances.
  • Conservation volumétrique : Notre algorithme actuel ne conserve pas le volume, ce que la VHACD s’efforce de résoudre.
  • Amélioration de l’erreur de concavité 2D : Notre calcul actuel de l’erreur de concavité 2D donne des faux positifs puisque nous vérifions un changement de zone plutôt qu’une fermeture de la concavité. Cela pourrait être un problème car le blocage de l’aplatissement des bords supprime inutilement une solution potentiellement valable de la convergence de votre algorithme.
  • Exposer la mise au point des algorithmes aux utilisateurs avancés pour affiner les résultats.

Roblox a toujours apprécié les fonctionnalités qui marchent par défaut ainsi que de pouvoir obtenir des collisions de haute qualité sans avoir à intervenir manuellement sur la géométrie des collisions est un objectif difficile que nous nous efforçons constamment d’atteindre. Bien que nous n’ayons pas atteint des collisions parfaites au pixel près, nous sommes ravis de pouvoir simuler automatiquement les résultats des opérations difficiles du CSG. Ce n’est que la première étape de la nouvelle phase passionnante d’amélioration de la génération de collisions de la géométrie arbitraire dans Roblox et nous sommes impatients de voir où les recherches de l’équipe et les commentaires des utilisateurs vont pousser nos efforts dans l’avenir !

Résultats

Tous ces résultats ont été calculés avec des paramètres cohérents sur le HACD d’origine et le HACD Roblox. Chaque couleur est une coque convexe différente.

SetNClusters 1
ScaleFactor 1000 // Tous les objets sont redimensionnés en un cube de 1000 x 1000 x 1000 pour l’opération
ConnectDist 0.1 // c’est la distance de quantification
Concavité 10 // il s’agit de l’erreur de concavité autorisée pour l’élimination des bords
CompacityWeight 0 // ce réglage favorise l’ordre d’aplatissement des bords basé sur le périmètre que nous n’utilisons pas.
CompacityWeight 0 // ce réglage favorise l’ordre d’aplatissement des bords basé sur le périmètre, que nous n’utilisons pas.

 

À gauche : RoHACD Au milieu : Entrée Geom À droite : HACD


Ni Roblox Corporation ni ce blog ne cautionne ni ne soutient aucune entreprise ou service. En outre, aucune garantie ou promesse n’est faite quant à l’exactitude, la fiabilité ou l’exhaustivité des informations contenues dans ce blog.

Cet article de blog a été publié à l’origine sur Roblox Tech Blog.