Décomposition d'un maillage concave en un ensemble de mailles convexes

J'aimerais pouvoir décomposer un maillage concave en un ensemble de mailles convexes pour 2 raisons:

1. Rendu transparent
2. Formes physiques

Existe-t-il un algorithme qui prend un ensemble de triangles (concaves) en entrée et génère un certain nombre d'ensembles de triangles (convexes)? Je voudrais qu'il ne remplisse pas les trous entre les parties du maillage d'origine.

J'ai déjà rencontré une petite idée: trouver tous les bords concaves et diviser les mailles le long des boucles de bord. Suis-je sur la bonne voie? Comment pourrais-je implémenter cela?

Je dirais que vous êtes sur la bonne voie, mais trouver un algorithme optimal et / ou efficace est une autre affaire: c'est un problème difficile. Cependant, à moins que votre intérêt ne soit académique, une solution suffisamment bonne peut suffire.

Premièrement, si vous n'êtes pas intéressé à trouver votre propre solution, CGAL contient déjà un algorithme pour la décomposition des polyèdres convexes: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Maintenant pour la méthode; comme de nombreux problèmes en 3D, il est souvent utile de considérer le problème 2D qui est plus facile à comprendre. Pour la 2D, la tâche consiste à identifier les sommets réflexes et à diviser le polygone en deux en créant une nouvelle arête (et éventuellement de nouveaux sommets) à partir de ce sommet réflexe, et en continuant jusqu'à ce que vous ne soyez pas confronté à des sommets réflexes (et donc des polygones entièrement convexes). ).

Polygon Decomposition de J. Mark Keil contient l'algorithme suivant (sous une forme non optimisée):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Fondamentalement, il compare de manière exhaustive toutes les partitions possibles et renvoie celle avec le moins de diagonales produites. En ce sens, il est quelque peu brutal et optimal également.

Si vous voulez des décompositions "plus belles", c'est-à-dire celles qui produisent des formes plus compactes plutôt que des formes allongées, vous pouvez également envisager celle produite par Mark Bayazit , qui est gourmande (donc beaucoup plus rapide) et semble plus belle mais a quelques défauts. Il fonctionne essentiellement en essayant de connecter les sommets réflexes au meilleur opposé, généralement à un autre sommet réflexe:

L'un des inconvénients est qu'il ignore les «meilleures» décompositions en créant des points de Steiner (points qui n'existent pas sur un bord existant):

Le problème en 3D peut être similaire; au lieu de sommets réflexes, vous identifiez des "bords d'entaille". Une implémentation naïve consisterait à identifier les bords d'entaille et à effectuer des coupes planes sur le polyèdre à plusieurs reprises jusqu'à ce que tous les polyèdres soient convexes. Consultez "Partitions convexes des polyèdres: un algorithme optimal à borne inférieure et au pire des cas" par Bernard Chazelle pour plus de détails.

Notez que cette approche pourrait produire dans le pire des cas un nombre exponentiel de sous-polyèdres. C'est parce que vous pourriez avoir des cas dégénérés comme celui-ci:

Mais si vous avez un maillage non trivial (pensez à une surface cahoteuse), vous obtiendrez quand même de mauvais résultats. Il est très probable que vous souhaitiez faire beaucoup de simplification à l'avance, si vous avez besoin de l'utiliser pour des maillages complexes.

Le calcul d'une décomposition convexe exacte d'une surface S est un problème difficile à NP et produit généralement un nombre élevé de grappes. Pour surmonter ces limitations, la contrainte de convexité exacte peut être assouplie et une décomposition convexe approximative de S est à la place calculée. Ici, l'objectif est de déterminer une partition des triangles maillés avec un nombre minimal de clusters, tout en garantissant que chaque cluster a une concavité inférieure à un seuil défini par l'utilisateur.

Consultez les bibliothèques de décomposition convexe approximative suivantes: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

Voici un code qui pourrait vous aider. Il est en java donc vous devrez le convertir en c ++.

Voici également un autre article qui peut vous aider