Comment diviser un maillage en plusieurs morceaux de sorte que tous soient plus petits qu'un nombre donné de sommets?

Je dois importer un maillage dans une application qui ne peut gérer qu'un certain nombre de mailles par objet. À cause de cela, je suis obligé de diviser le maillage en plusieurs morceaux jusqu'à ce que tous les pices soient en dessous du nombre maximum de vertex. Le fractionnement doit se produire pendant l'exécution, donc je ne peux pas utiliser une application externe pour diviser le maillage.Comment diviser un maillage en plusieurs morceaux de sorte que tous soient plus petits qu'un nombre donné de sommets?

Je n'ai aucune exigence concernant la façon dont le maillage est divisé, mais il devrait conserver toutes les faces, normales et UV.

Y at-il un algorithme connu qui peut le faire?

Source

2017-03-01 kace91

Votre maillage faire usage d'indices ? Est-ce triangulé? Si c'est le cas, vous pouvez itérer sur les index, en copiant chaque sommet pointé par l'index actuel dans un nouveau maillage plus petit. Vous "terminerez" ce maillage lorsque le nombre de vertex du nouveau maillage est supérieur à votre nombre max_vertex_count - 3. –

@kirkroerig Oui, mon mesh est triangulé. Il se présente sous la forme d'une liste ordonnée de sommets, chacun incluant ses coordonnées UV. Les visages sont définis comme des groupes de 3 indices de la liste des vecteurs. Les triangles ne sont pas corrélatifs, je peux avoir un triangle avec les index 0, 300 et 1534 par exemple. – kace91

Vous devez utiliser un graphique d'adjacence triangulaire. Commencez par un triangle et marquez-le visité. Ensuite, à partir de chaque côté du triangle, déplacez-vous sur les triangles adjacents non visités et marquez-les. Une fois que le nombre de vertex atteint la limite, créez un nouveau mesh et recommencez.

Source

2017-03-02 08:27:53 abenci

Une possibilité à la fois simple à coder et qui donne un résultat raisonnablement bon est de trier les triangles spatialement, avec le tri de Hilbert [1]. Ensuite, vous parcourez la liste ordonnée de triangles, les regroupez en groupes de n éléments et générez les différentes parties de votre maillage. Une implémentation est disponible dans ma bibliothèque de programmation GEOGRAM [2]. Voir la fonction mesh_partition() [3]. Si vous voulez optimiser la "compacité" des parties (ie minimiser le nombre de composants connectés dans chaque partie), alors vous pouvez utiliser un algorithme de partitionnement de graphes tel que METIS [4] ou SCOTCH [5], appliqué au graphe de les facettes (qui ont un noeud par facette et un bord reliant chaque paire de facettes adjacentes). Cependant, il est plus cher (en termes de temps et de consommation de mémoire).

[1] https://en.wikipedia.org/wiki/Hilbert_curve

[2] http://alice.loria.fr/software/geogram/doc/html/index.html

[3] http://alice.loria.fr/software/geogram/doc/html/mesh__partition_8h.html

[4] http://glaros.dtc.umn.edu/gkhome/metis/metis/overview

[5] http://www.labri.fr/perso/pelegrin/scotch/

Source

2017-03-03 21:51:05 BrunoLevy

Comment diviser un maillage en plusieurs morceaux de sorte que tous soient plus petits qu'un nombre donné de sommets?

Répondre

Questions connexes