Déterminer si la suppression d'un voxel va diviser un groupe

J'ai la situation suivante: j'ai une grille 3D de voxels (on / off, la taille max est probablement 128x128x128). Je sais à l'avance qu'à l'intérieur du réseau, tous les voxels qui sont allumés sont interconnectés, formant un seul groupe.

Maintenant, je dois déterminer: quand je supprime un voxel (éteignez-le), est-ce que cela cassera le groupe?

Mon idée initiale était de regarder les voisins du voxel qui est retiré et de déterminer s'ils sont toujours interconnectés via d'autres voxels (voir mon autre question: algorithme pour voir si deux voxels sont interconnectés ). Mais il pourrait y avoir de meilleures / autres façons de le faire.

Alors, quelle serait une bonne façon de déterminer si le retrait d'un voxel va briser le groupe dont il faisait partie?

J'ai couvert cela un peu dans mon autre commentaire, mais je pense que vous pensez ici à la classification externe / interne. En supprimant un voxel, vous changez les voxels qui l'entourent en voxels `` de bord '' (s'ils ne l'étaient pas déjà). Cela devrait se résumer en 3 cas réels (la symétrie vous donne le reste) - dans l'exemple ci-dessous, les nombres sont les identifiants de groupe, le - est le voxel supprimé

11      2    
1-     1-     1-2

• Le premier cas est trivial - c'est un coin, mais les voxels au-dessus et à gauche restent entièrement connectés via l'autre voxel.

• Le deuxième cas: c'est un coin et le voxel supprimé a déconnecté les voxels ci-dessus et gauche qui étaient précédemment connectés

• Le troisième cas: c'est une ligne, et le voxel supprimé a déconnecté les voxels gauche et droit précédemment connectés.

Si vous identifiez que les 2e ou 3e cas se sont produits, vous devez effectuer une recherche de chemin pour voir si 1 et 2 sont toujours connectés via leurs autres voxels adjacents.

Vous pouvez cependant obtenir une certaine efficacité ici. Si un voxel est entièrement interne à un groupe (c'est-à-dire que les 8 voisins font partie du même groupe), alors il peut être actualisé. Pourquoi? C'est une chose de topologie. Imaginez le cas 2D - il n'y a que deux possibilités. Soit il y a un seul bord qui, quelle que soit la façon dont il se tord et tourne, forme toujours un anneau de voxels. Ou, il y a deux anneaux, l'un contenant un voxel et l'autre contenant l'autre. Par exemple:

 xxx xxx
 x x-x x
 xxx xxx

ou

 xxxxxxx
 x     x
 xxx xxx
   x-x 
 xxx xxx

Cela devrait également s'étendre à la 3D, sauf qu'au lieu d'un anneau de limite, vous auriez une surface limite. Ainsi, lorsque vous essayez de déterminer si les deux voxels récemment déconnectés sont toujours connectés, vous pouvez exclure tous les voxels internes de votre parcours, car par définition, si un voxel est connecté à l'un des voxels limites d'un groupe, c'est également connecté à tous les voxels internes de ce groupe.

C'est en quelque sorte l'effet inverse des voxels concentrateurs dont j'ai parlé dans ma réponse à l'autre question - vous n'avez pas à trouver votre chemin de chaque voxel à tous les autres voxels, vous n'avez qu'à trouver votre chemin vers les voxels intéressants .

Si vous utilisez A *, vous pouvez l'utiliser ici.

En commençant par une liste des voxels qui étaient connectés au voxel supprimé. Commencez par le premier de la liste, utilisez A * pour trouver un chemin vers le second de la liste. Si un chemin existe, recherchez un chemin du deuxième au troisième, du troisième au quatrième et ainsi de suite.

La plupart de ces recherches seront très rapides, car les voxels seront juste à côté les uns des autres. S'il y a un chemin qui échoue, cela signifie qu'une discontinuité a été créée.

Cela devrait être assez facile à implémenter si vous avez déjà implémenté la fonctionnalité A *.