Comment puis-je ajouter et soustraire des polygones convexes?

J'ai deux polygones convexes 2D qui se chevauchent . Je recherche un algorithme pour les soustraire et les ajouter . Le résultat doit être un seul polygone concave ou (mieux encore) un ensemble de plus grands convexes formant le résultat concave (par exemple des triangles).

(À gauche: les polygones qui se chevauchent initialement. Au milieu: le polygone concave résultant après l'ajout. À droite: un ensemble de polygones convexes formant le résultat concave. Ici, il serait préférable d'avoir des polygones convexes plus grands qu'un triangle pour des raisons de performances. Une soustraction de la deux polygones qui se chevauchent mèneraient à la même image qu'à gauche mais avec la zone de chevauchement ne faisant pas partie du polygone résultant.)

Comment puis-je faire ceci?

TL; DR Vous devez implémenter des opérations booléennes à l'aide d'arbres BSP.

Eh bien, il semble que nous parlions ici de géométrie solide constructive . J'ai implémenté CSG à un niveau commercial, donc je sais une chose ou deux à ce sujet.

L'article classique sur CSG s'appelle Merging BSP Trees Yields Polyhedral Set Operations , pour être honnête, c'est trop à expliquer ici, mais en bref, l'algorithme traite des polygones qui se trouvent sur le même plan qu'un partitionnement d'espace binaire, construisant essentiellement un arbre BSP de chaque maillage polygonal. La deuxième étape consiste à fusionner ces arbres BSP; vous prenez simplement un arbre et l'insérez dans l'autre. L'algorithme continue ensuite d'expliquer comment traiter chaque nœud feuille pour diviser et soustraire les nœuds, les nœuds qui ne sont pas nécessaires dans la forme finale seront supprimés, d'autres recevront le parent approprié.

Mais attendez! Ce document parle essentiellement des maillages polygonaux et des plans 3D, NON?

L'algorithme peut être généralisé dans n'importe quelle dimension, donc dans votre cas 2D, il est facile d'utiliser des segments de ligne au lieu de plan comme partitions binaires. Ainsi, chaque polygone sera converti en un arbre BSP que les deux seront fusionnés. Enfin, vous traversez l'arbre résultant pour générer le polygone final,

Notez que cet algorithme et le CSG en général ne traitent pas directement le rendu et les faces de maillage et ne sont pas vraiment prêts, vous devez donc extraire les faces des arborescences BSP finales. Je trouve également que le lancer de rayons est une approche plus facile pour rendre le résultat CSG, vous n'avez besoin que des rayons pour traverser l'arbre au lieu d'extraire et de diviser les faces (rappelez-vous que nous ne traitons que des partitions binaires).

Concernant la robustesse numérique. Il est bon de noter qu'il existe deux types de calculs géométriques,

• Ceux qui sont basés sur la construction, vous construisez une forme basée sur le résultat d'une opération précédente. Par exemple y = sqrt(x), puis utiliser ydans une nouvelle opération. C'est ce qu'on appelle la construction; le problème est que les erreurs numériques s'accumulent rapidement.
• Alternativement, il existe des opérations qui utilisent des prédicats à la place, essentiellement au lieu d'utiliser la construction, vous demandez simplement si une condition est vraie / fausse et utilisez la même valeur dans une opération différente. Les tests classiques incluent incircle et le test d'orientation; cela est également suspect d'erreurs numériques, surtout si vous utilisez une précision simple ou double, mais donne généralement de bien meilleurs résultats. il existe d'autres solutions qui varient selon la vitesse et la précision. Voici l'un des articles récents qui évitent la construction en utilisant une géométrie plane pour donner des résultats précis. Je citerai également le document:

Le concept de représentation plane des maillages polygonaux a été décrit pour la première fois par Sugihara et Iri [SI89]. Ce type de représentation fournit un avantage important en ce qui concerne les tâches qui impliquent de changer la topologie des solides représentés par des maillages comme l'évaluation des expressions booléennes: aucune nouvelle information de géométrie primaire ne doit être construite pour obtenir le polyèdre résultant

Et enfin, je voudrais ajouter, si vous souhaitez démarrer votre implémentation CSG BSP, je recommanderais de commencer sur les FAQ BSP .

En suivant votre exemple:

Choisissez un sommet de départ sur le polygone A, puis commencez à vérifier les arêtes qui se coupent dans le sens horaire (ou antihoraire). S'il n'y a pas d'intersection, ajoutez le sommet précédent à votre polygone résultant. S'il y a une intersection, ajoutez le point auquel ils se sont intersectés au polygone résultant, puis commencez à itérer sur le polygone B, dans le même ordre d'enroulement. Faites la même chose, en échangeant à nouveau vers le polygone A si une intersection se produit.

Une fois que vous avez accumulé tous les sommets du nouveau polygone, exécutez un algorithme de triangulation dessus. La méthode de coupure d'oreille est facile à mettre en œuvre, mais il existe des options plus rapides.

Important: assurez-vous que le sommet à partir duquel vous commencez n'est pas à l'intérieur de l'autre polygone (consultez cet article pour les points dans les tests de polygone).

Itérer sur chaque arête, pour vérifier une intersection serait un algorithme O (n ^ 2). Vous pouvez l'accélérer en trouvant d'abord les sommets qui se trouvent à l'intérieur de l'autre polygone, car les arêtes liées à ces sommets seront celles qui se coupent.

Si vous voulez un polygone concave , choisissez simplement l'arête la plus proche entre les deux polygones d'entrée et ajoutez deux nouvelles arêtes:

La convexe devient un peu plus compliquée:

Une approche est itérative en ce qu'elle ajoute des sommets du deuxième polygone au premier, un à la fois, faisant évoluer le premier polygone dans un conteneur qui englobe tout.

Fondamentalement:

• Itérer à travers les sommets du deuxième polygone.
• Pour chaque sommet V, parcourez les arêtes du premier polygone:
• Trouver une "plage" d'arêtes qui font toutes face au sommet
• prendre la paire de sommets externes qui définissent cette plage et supprimer toutes les arêtes de la plage qui les relie
• Dessinez deux nouveaux segments de ces sommets externes vers le nouveau sommet (à partir du deuxième polygone), en vous assurant que les nouvelles arêtes sont orientées dans la bonne direction.
• Passez au sommet suivant du deuxième polygone

Voici un diagramme illustrant le processus pour le premier sommet:

Une méthode plus rapide consiste à trouver la liste des arêtes sur chaque polygone qui ne font pas face à l'autre polygone, supprimer tout le reste et connecter les extrémités des bandes de lignes restantes les unes aux autres.

Peut-être que quelqu'un d'autre peut sonner avec quelques conseils de soustraction.