A la recherche d'une meilleure décomposition convexe

Roblox a introduit la géométrie solide constructive en 2014, et soutenir la simulation physique de ce projet a été mon premier grand projet dans l'équipe de simulation avec Tim Loduha. À l'époque, l'entreprise était beaucoup plus petite et l'équipe de physique n'avait que deux personnes qui avaient d'autres responsabilités non liées au développement. Donc, dans un esprit de résultats rapides, nous sommes allés dans une bibliothèque très populaire appelée Bullet Physics pour obtenir de l'aide. Bullet Physics est utilisé dans de nombreux jeux aujourd'hui en raison de son accessibilité et de sa richesse en fonctionnalités, et sa nature open source et son extensibilité en ont fait le choix naturel pour les besoins de Roblox.

Bien que le moteur physique Roblox soit construit en interne, il y avait deux composants principaux que nous devions utiliser de Bullet Physics pour faire fonctionner PartOperations dans les simulations:

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

Lorsque nous travaillions à l'origine sur la partie décomposition convexe du projet, nous avons expérimenté deux algorithmes fournis avec BulletPhysics:

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

Bien que nous ayons aimé les résultats de HACD, ​​la robustesse et la cohérence d'ACD nous ont séduits pour le produit initial.

Retour de précision

Après l'expédition de la fonctionnalité, nous avons accumulé une montagne de commentaires où les utilisateurs s'attendaient à de meilleurs résultats géométriques de la détection de collision. L’utilisation par ACD de la voxélisation grossière a provoqué le déplacement ou la couverture de divers artefacts, tels que les surfaces importantes des portes ou des rebords.

Vous pouvez imaginer 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 respectait la géométrie d'origine. La voxélisation était hors de l'image en raison de la façon dont les surfaces ont tendance à «s'accrocher» aux grilles de voxels. 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 convexe approximative hiérarchique

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

• Le maillage d'entrée a été utilisé comme état initial de l'algorithme
• Vérification d'erreur par rapport à la géométrie d'entrée d'origine
• Non-collecteur géré (tout comme ACD)
• Pas de voxélisation

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

• Élimination double graphique
• Génération de coque convexe
• Calcul d'erreur de concavité

Présentation 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 bord entre deux triangles est un bord dans le graphique. C'est le début double graphique, où chacun Triangle est traité comme une initiale enveloppe convexe.

2. Nous passons par chaque bord du graphique et calculons la coque convexe prévue qui résulterait de la combinaison des coques convexes des nœuds que le bord relie.

3. Nous utilisons ceci coque convexe prévue pour ensuite calculer le erreur de concavité encourus par la géométrie d'origine. Ces erreurs sont utilisées pour trier tous les bords du graphique du moins erroné au plus.

4. Enfin, nous prenons l'avantage avec la plus petite erreur.

une. Si l'erreur est inférieure au maximum configuré configuré erreur de concavité on enlève le bord (effondrement des bords) et remplacez les deux nœuds par le bord coque convexe prévue.

b. Si l'erreur est supérieure au maximum configuré autorisé erreur de concavité nous terminons.

5. Chaque fois qu'un bord est supprimé par effondrement des bords, cela invalide le précédent erreur de concavité résultats pour les bords adjacents, nous répétons donc les étapes 2 et 3 pour les bords adjacents.

6. Nous mettons à jour les bords recalculés dans notre liste de bords triés en fonction de la nouvelle erreurs de concavité.

7. Répétez les étapes 4 à 6 jusqu'à ce que les seuls bords restants aient Erreur valeurs supérieures à erreur globale autorisée (ceci est configuré par l'utilisateur avant de démarrer l'algorithme).

Nous avons récupéré la dernière version disponible du code HACD open source et l'avons testée sur certains maillages. Certaines formes, comme la voiture, ont abouti à une géométrie de collision plus améliorée qu'auparavant, mais d'autres maillages d'entrée ont entraîné des sorties douteuses. L'algorithme en théorie semblait bien, donc notre prochaine étape était de comprendre ce qui causait ces résultats étranges.

Débogage visuel

Comme nous ne connaissions pas bien les opérations internes de la mise en œuvre, nous avons fait la seule chose que nous pouvions pour accélérer notre enquête. Nous avons écrit un débogueur visuel qui enregistrerait chaque étape du processus de suppression des bords à double graphique et nous permettrait de suivre chaque changement de la géométrie d'origine une étape à la fois.

Avec cet outil, nous avons pu identifier qu'il y avait des problèmes à la fois dans calcul d'erreur de concavité et le génération de coque convexe. Nous avons pu avancer et trouver des cas où une coque convexe correctement formée aurait bloqué une concavité importante et grande, mais le calcul d'erreur de concavité rapporterait l'effondrement des bords qui a formé cette coque comme n'ayant aucune erreur. Sur le génération de coque convexe côté, nous avons constaté que les effondrements de bord provoquaient parfois la disparition de sommets et de faces entières. Il en résulterait des surfaces mineures manquantes dans certains cas et une dévastation complète dans d'autres.

Et avec cela, nous avons reconnu que nous devions plonger profondément et écrire notre propre logique pour chacun de ces composants.

Calcul d'erreur de concavité (Étape 3 de la vue d'ensemble de l'algorithme)

Le but de calcul d'erreur de concavité est de quantifier la quantité de «dommages» à la géométrie d'origine que la suppression d'un bord entraînerait par sa création d'une nouvelle coque convexe en combinant les coques que le bord relie. Le document d'origine mentionne que cette erreur peut être suivie de nombreuses façons, et la mise en œuvre a utilisé la distance la plus éloignée de la surface d'origine à la surface nouvellement formée à l'intérieur de la coque convexe prédictive nouvellement formée. Nous utiliserons la même définition.

Pour acquérir cette quantité, nous avons besoin de deux informations:

• Une représentation quantifiable de la géométrie source
• La coque convexe prédictive qui se formerait à partir de la suppression de ce bord (étape 2 de l'aperçu).

L'implémentation HACD d'origine utilisait quelques points d'échantillonnage par triangle comme représentation de la surface d'origine (au cours de l'étape 1 de l'aperçu). Ces points seraient ensuite utilisés pour diffuser des rayons à partir de, le long des normales de face, pour trouver la face arrière d'une coque convexe qui gêne 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. Il s'agit d'une approche raisonnable, mais en raison de la densité d'échantillonnage étant une opération par triangle, nous avons rencontré des problèmes où les formes simples avec de grandes faces triangulaires avaient d'énormes angles morts lors de la recherche d'objets susceptibles de bloquer les concavités.

Un système idéal essaierait essentiellement de faire une extrusion de surface à partir des triangles de surface d'origine sur la coque convexe en cours de test, mais c'est un problème très coûteux à résoudre et à optimiser, donc nous viserons plutôt à échantillonner les surfaces de triangle d'origine mais avec Distribution.

Nous générerons uniformément des points d'échantillonnage de surface pour chaque triangle en fonction d'une distance de grille configurée (voir à gauche). Étant donné que cela générera une grande quantité de points, nous avons également besoin d'un moyen de filtrer rapidement les points qui doivent être vérifiés par rapport aux coques convexes nouvellement formées pendant la erreur de concavité processus de calcul. Pour ce faire, nous jetons chaque point d'échantillonnage dans une grille spatiale, similaire à ceux utilisés dans la détection de collision, en utilisant le cadre de délimitation d'une coque que nous testons pour sélectionner rapidement un groupe de points d'échantillonnage de surface à tester.

Une fois que nous avons saisi les points que nous trouvons à l'intérieur de la boîte englobante, nous filtrons davantage les points qui sont À L'INTÉRIEUR de la coque convexe nouvellement formée, car nous essayons d'attraper les concavités scellées par la coque convexe actuelle. Nous avons ensuite diffusé des rayons de ces points d'échantillonnage contre les triangles de la coque. S'il n'y a pas d'erreur ajoutée, tous renverront des distances de zéro, mais une coque convexe problématique, comme dans le diagramme ci-dessus, aura les raycasts de la surface d'origine impact sur la face arrière de l'un des coque convexe prédictiveDes triangles!

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

• (Au cours de l'étape 1 de la vue d'ensemble de l'algorithme) Échantillonnez uniformément les points sur chaque triangle et jetez-les dans une grille spatiale.
• Saisissez la boîte englobante de la coque convexe que nous testons et rassemblez tous les points de la grille à l'intérieur de cette boîte englobante.
• À partir des points rassemblés, pour chaque point d'échantillon À L'INTÉRIEUR de la coque convexe, nous faisons un lancer de rayons le long de la normale de surface d'origine pour voir s'il touche la face arrière de la coque convexe.
• Le rayon avec la plus grande distance qui a frappé une face arrière finit par être notre erreur de concavité.
• Si la coque convexe n'extrude pas en dehors de la surface d'origine, le résultat doit être 0.
• Cela peut être optimisé en quittant tôt dès que le premier échantillon raycast dépasse l'erreur globale maximale autorisée, car cela suffit pour empêcher un bord de s'effondrer.

Ce système nous offre un moyen robuste de vérifier les coques convexes pour savoir combien d'erreur elles introduiraient dans notre forme d'origine, mais il manque encore une chose. Cette méthode ne fonctionne bien que sur les coques convexes 3D. Si la coque convexe est plate, les points d'échantillonnage ne seront jamais alignés dans les directions que nous aurions besoin de tester pendant la formation des coques convexes 2D. Prenons par exemple la configuration de droite, si les triangles bleu et vert forment une coque convexe puis tentent de se combiner avec le rouge, les points d'échantillonnage à l'intérieur de cette coque convexe n'auraient probablement pas d'impact sur la face arrière de la coque convexe à n'importe quelle distance mais 0. Afin de résoudre correctement ce problème, nous devrions envisager un processus de calcul d'erreur 2D complètement différent, qui serait tout aussi impliqué 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 coques convexes d'origine à l'aire du résultat. Si la coque résultante a plus de surface que la somme des deux coques source, vous savez qu'elle peut fermer une concavité, et donc la racine carrée de la zone supplémentaire peut être traitée comme erreur de concavité dans ce cas! Et enfin, nous avons une bonne méthode pour détecter les erreurs dans les candidats potentiels à la coque convexe, à condition que nos coques convexes d'entrée soient correctement formées!

Génération de coque convexe: Quickhull (Étape 2 de la vue d'ensemble de l'algorithme)

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

1. Certaines coques convexes qui scelleraient de grandes concavités passeraient erreur de concavité test avec un résultat de 0.
2. La combinaison de deux coques convexes ferait parfois disparaître un sommet, laissant un trou dans la forme d'origine.

La mise en œuvre originale de HACD a utilisé une variante de la Quickhull algorithme, qui est un choix parfait parce que l'algorithme est conçu pour ajouter rapidement de nouveaux points à une coque convexe existante, ce que nous ferons en réduisant les bords. Un premier examen des données collectées par notre débogueur de visualisation a révélé que, parfois, les coques résultantes auraient un triangle inversé, ce qui était une étape incontournable pour notre décrit précédemment calcul d'erreur de concavité méthode.

La façon dont cet algorithme est censé fonctionner est que lorsque vous choisissez un nouveau point à ajouter à une coque existante, vous trouvez alors des triangles pour les plans desquels le point se trouve à l'extérieur. Ces triangles sont ensuite marqués pour suppression, tandis que leurs bords à d'autres triangles seront utilisés pour former un nouvel ensemble de triangles avec le point en cours de traitement pour sceller la coque convexe. Quelque chose que vous pouvez apprendre du discours de Valve sur Quickhull l'algorithme est qu'il est très sensible aux erreurs en virgule flottante, surtout si l'une des coques a des triangles coplanaires. L'exemple à droite est une coupe transversale du boîtier facile qui n'illustre pas le problème décrit par Valve.

Pour comprendre le problème, vous devez considérer une coupe transversale qui ressemble à la forme de gauche. Considérez un Quickhull situation où nous ne savons pas très bien si les triangles E et F considèrent le point à l'extérieur ou à l'intérieur de leurs plans. En fait, le pire des cas est celui où E considère le point extérieur, tandis que F considère le point intérieur. Dans Quickhull, car l'orientation du triangle dépend des triangles adjacents, ce type de topologie incohérente peut soit créer des triangles mal orientés, soit entraîner une défaillance complète.

Dirk Gregorius de Valve résout ce problème en fusionnant des triangles coplanaires en objets à face singulière de sorte que ce type 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 épais plan auquel appartiennent plusieurs triangles coplanaires et utilisez ce plan pour vous assurer que tous les triangles qui sont connectés entre eux et s'insèrent dans le plan ne peuvent résoudre le calcul que si un point se trouve à l'intérieur ou à l'extérieur de manière singulière. Cela résout essentiellement le problème de la même manière que la solution de fusion de face de Dirk, tout en nous permettant de conserver des références directes aux triangles individuels.

Comme auparavant avec calcul d'erreur de concavité, nous devons également considérer le cas 2D. Afin de protéger votre code de décomposition convexe d'une variété de données d'entrée, vous DEVEZ implémenter un Quickhull 2D Ainsi qu'un 3D Quickhull 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 supprimera souvent les sommets d'entrée ou échouera.

Traitement cohérent en virgule flottante

Après avoir trouvé des solutions pour génération de coque convexe et erreur de concavité que nous avons fait confiance et que nous avons compris, nous rencontrions toujours des problèmes, mais le débogage 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 préoccupations les plus importantes en géométrie 3D – un traitement cohérent des virgules flottantes est un must. Pour que cet algorithme fonctionne de manière robuste, le concept d'epsilons et d'informations quantifiées devait être unifié.

Tout au long de l'algorithme, il existe différents points où un concept d'Epsilon a été utilisé:

• Lors de la création d'un double graphique à partir de la géométrie en entrée, les sommets dégénérés étaient combinés en un seul sommet.
• Tout au long de génération de coque convexe nous devions tester si les coques convexes étaient coplanaires entre elles, pour décider si nous devions opérer en mode 2D ou 3D.
• Pendant erreur de concavité calcul, nous avons également eu besoin de tester la coque actuelle pour la planéité, et nécessaire cohérente epsilons pour lancer des rayons contre l'intérieur des coques convexes.

Une fois la distance de quantification (s) est déterminé comme une configuration de l'algorithme, nous devons considérer que 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 doit être considérée comme coplanaire. Toute génération de coque convexe sur un ensemble de points qui correspondent à une largeur de plan s doivent être traités comme des opérations purement 2D. En outre, toutes nos requêtes sur les epsilons doivent être effectuées dans une seule dimension, ce qui signifie que toute demande de volume ou de zone d'objets doit être vérifiée par rapport aux distances maximales d'un avion.

Conclusions

À la fin du processus, il est toujours amusant de prendre du recul et de demander «Qu'avons-nous appris?» Pour HACD, ​​nous soulignerions certainement l'importance des concepts de haut niveau suivants afin d'obtenir des résultats de qualité cohérents:

• Échantillonnage uniforme de la surface – nous avons besoin d'une bonne image fidèle de la géométrie d'origine pour mesurer la progression de l'algorithme.
• Distinction entre opérations 2D et 3D pendant calcul d'erreur de concavité, et génération de coque convexe – l'algorithme passe une partie importante de son temps à traiter des opérations 2D, sauf si votre géométrie en entrée 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 le calcul de la connectivité des triangles d'entrée, aidant à Quickhull problème de face coplanaire et fractionnement des opérations 2D et 3D.

Ces trois concepts sont les piliers fondamentaux qui dirigent notre refacteur interne massif de la bibliothèque HACD, ​​et nous permettent de l'expédier en tant que générateur de géométrie de collision automatique générique pour le maillage triangulaire de Roblox et les objets CSG. Même avec ce travail accompli, 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 VHACD se concentre sur la résolution.
• Amélioration de l'erreur de concavité 2D: Notre calcul actuel d'erreur de concavité 2D donne des faux positifs puisque nous vérifions un changement de zone par rapport à fermeture de concavité. Cela pourrait être un problème car le blocage de l'effondrement des bords supprime inutilement une solution potentiellement valide de la convergence de votre algorithme.
• Exposition du réglage de l'algorithme aux utilisateurs avancés pour des résultats de réglage précis.

Roblox a toujours apprécié les fonctionnalités qui fonctionnent par défaut, et être en mesure d'obtenir des collisions de haute qualité sans masser manuellement la géométrie des collisions est un objectif difficile vers lequel nous nous efforçons constamment. Bien que nous n'ayons pas atteint des collisions parfaites en pixels, nous sommes ravis de pouvoir simuler automatiquement les résultats d'opérations CSG difficiles. Ce n'est que la première étape de la nouvelle phase passionnante de l'amélioration de la génération de collisions pour la géométrie arbitraire dans Roblox, et nous sommes ravis de voir où les recherches et les commentaires des utilisateurs de l'équipe pousseront nos efforts!

Résultats

Tous ces résultats ont été calculés avec des paramètres cohérents sur le HACD d'origine et le Roblox HACD. 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 // c'est l'erreur de concavité autorisée pour le retrait des bords
CompacityWeight 0 // ce paramètre favorise l'ordre d'effondrement des bords en fonction du périmètre, nous ne l'utilisons pas.
VolumeWeight 0 // ce paramètre favorise l'ordre de réduction des bords en fonction du volume, nous ne l'utilisons pas.