Algorithme de contour 2D pour le maillage 3D projeté

Question

Étant donné: un maillage 3D défini avec un ensemble de sommets et de triangles construisant le maillage avec ces points.

Problème: recherchez le contour 2d du maillage projeté ayant subi une rotation arbitraire dans un plan arbitraire.

La projection est facile. Le défi consiste à trouver la "coque". des bords du triangle projetés dans le plan. J'ai besoin d'aide pour les entrées / indications sur la recherche de cet algorithme. Pour plus de simplicité, nous pouvons supposer que les arêtes 3D sont projetées directement vers le bas sur le plan xy.

Answer 1

• Commencez par le point le plus à droite (le point avec la plus grande coordonnée x)
• Obtenir toutes les arêtes de ce point
• Suivez le bord présentant l'angle le plus petit par rapport à l'axe des x positif et ajoutez-le également à l'ensemble de solutions
• À partir du point atteint, suivez et ajoutez le bord avec le plus petit angle au bord d'où vous venez
• Répétez l'opération jusqu'à atteindre le point d'origine

Answer 2

Je ne vois que des solutions pour les solutions convexes, alors voici la mienne pour les solutions non convexes. (C'était un peu déroutant quelle était l'intention.)

Prenez toutes les arêtes de vos triangles 2D et regroupez-les. Si deux arêtes partagent les deux extrémités, elles appartiennent au même groupe. Tous les groupes, avec un seul bord, font alors partie du shell.

Enfin, vous pouvez associer les bords de la coquille à un anneau en les joignant.

Answer 3

La technique des formes alpha mentionnée dans cette question traite un ensemble général de points où les connexions au sommet ne sont pas connues:

Y a-t-il un algorithme efficace pour générer une coque concave 2D?

Cependant, puisque vous connaissez déjà le "visage", informations qui peuvent être conservées grâce à la projection, ce n’est probablement pas la meilleure approche.

Un algorithme de force brute pourrait être réalisable, en particulier si des structures de tri spatial sont utilisées. par exemple pour chaque facette:

1. La facette du projet dans l'avion
2. Vérifiez si la facette projetée est complètement entourée par la géométrie existante, si c'est le cas (terminé (pas besoin d'agrandir la silhouette projetée))
3. Si des points sortent de la géométrie existante, faites des intersections triangle-triangle pour déterminer les portions tombant à l'extérieur, créez un n-gon arbitraire (éventuellement concave) pour remplir l'espace manquant, puis découpez le n-gon en triangles

Une autre idée, en fonction de la fidélité souhaitée, consiste à tirer un faisceau de rayons normaux de votre plan de projection à votre géométrie d'origine. Créez un hit / miss en 2D et utilisez-le pour déterminer votre étendue.

Answer 4

Le contour 2D de la projection du maillage est un sous-ensemble de la projection de ses bords.

Cette observation permet de déterminer le contour 2D à l'aide de la méthode suivante:

• la projection de chaque bord appartenant à une seule face fait partie du contour 2D,
• pour les autres arêtes, déterminez le vecteur normal de ses faces adjacentes
• calcule les produits scalaires de ces normales avec la normale du plan de projection
• la projection de cette arête appartient au contour 2D si tous les signes des produits scalaires ne sont pas identiques (ce qui signifie qu’une face est dirigée vers le plan de projection, tandis qu’une autre au moins ne l’est pas, ce qui identifie l’arête comme partie du contour).

Notez que cette méthode générera tous les arêtes orthogonales au plan de projection, même celles qui ne sont pas visibles du point de vue du plan de projection. Par exemple, avec un tore, il trouvera les contours intérieur et extérieur, même lorsque le tore est tourné de telle sorte que son trou intérieur ne soit pas visible du point de vue du plan de projection. Pour déterminer quelles arêtes sont visibles, vous aurez besoin d’une sorte de test de visibilité. Si l'utilisation prévue est pour l'affichage par l'utilisateur, vous pouvez utiliser un tampon de profondeur calculé avec une matrice de projection orthogonale pour restituer la géométrie à partir du point de vue du plan de projection et effectuer un test z pour déterminer les arêtes visibles du plan. Si vous avez besoin de précision, vous devrez effectuer une intersection de rayons et de triangles pour déterminer la visibilité.

Answer 5

Juste pour ajouter: un moyen très intuitif de trouver des arêtes dans une projection est de sélectionner le visage arrière! Tout bord entre un visage isolé et un visage non isolé doit être un contour. Si vous souhaitez masquer les bords intérieurs, utilisez simplement le z-buffer. La sélection de la face arrière est simplement l'ordre des sommets après la projection et est très économique à calculer.

Answer 6

S'agit-il simplement de projeter les points xyz en points x'Y 'sur le plan arbitraire, puis de simplement faire une coque convexe dans ces coordonnées?