Comment puis-je effectuer un test de triangle à l'intérieur dans des maillages polygonaux?

10

entrez la description de l'image ici J'ai 3 sommets (V1, V2, V3)sélectionnés au hasard sur un maillage triangulaire régulier. Pour ces 3 sommets, j'ai calculé la distance géodésique et le chemin (en utilisant Dijkstra) entre eux et formé une surface en forme de triangle comme dans la figure ci-dessus.

Maintenant, j'ai les sommets qui se trouvent dans chaque chemin et je peux calculer les distances géodésiques à partir d'un sommet donné.

Ce que je veux faire, c'est obtenir les sommets ou triangles qui se trouvent dans une zone de type triangle. Comment puis-je faire ceci?

mesh triangulation mkocabas
la source
2
En supposant que l'approche barycentrique fait ce que je pense qu'elle serait assez lente avec de grands ensembles. Imaginez un ensemble de 9 millions de sommets avec seulement 9 sommets dans l'ensemble souhaité. Pourquoi itérer l'ensemble entier lorsque v1, v2 et v3 vous donnent toutes les informations dont vous avez besoin. La réponse de remplissage d'inondation serait la solution flexible la plus rapide. Bien que non flexible, si vous pouvez supposer que vous avez des lignes comme vous le faites maintenant dans la géométrie, la ligne de balayage serait l'approche la plus rapide.
Andrew Wilson
Vous avez absolument raison sur les problèmes de performances. Je voudrais utiliser cette approche dans de grands maillages, donc ce que je recherche, c'est une méthode efficace. En fait, je ne connais ni les algorithmes de remplissage par inondation ni de remplissage par balayage, je vais les examiner. Merci.
mkocabas
3
Un remplissage avec un graphique commencerait à un nœud, visiterait chaque nœud voisin si la condition aux limites est remplie et non visitée, le marquerait comme visité et se répéterait (récursivité). Altération: marquez chaque nœud sur le chemin comme visité et commencez à partir d'un nœud à l'intérieur de l'ensemble. Ensuite, utilisez simplement la vérification des visites comme condition aux limites.
Andrew Wilson
Merci pour l'explication détaillée. Je trouve que le remplissage par inondation est plus raisonnable, mais je veux implémenter à la fois le remplissage par inondation et la ligne de balayage, puis comparer les performances.
mkocabas

Réponses:

4

Il existe une méthode alternative qui repose sur le remplissage par inondation. Organisez d'abord vos données de bord dans une boucle où les bords forment une boucle dans le sens antihoraire. Commencez ensuite à un point arbitraire de la boucle et choisissez des bords rejoignant ce point. Utilisez le bord limite sortant et traversez-le avec l'autre bord sortant, s'il pointe dans la direction de la face normale, c'est un bord à inclure, sinon jetez-le. À partir de ce bord, continuez jusqu'à ce que vous atteigniez un bord limite, à quel point vous terminez le remplissage. Continuez à un sommet de bord de limite encore à visiter.

joojaa
la source
Je ne connais pas l'algorithme de remplissage des inondations. Votre explication me semble un peu compliquée. Pourriez-vous s'il vous plaît fournir une référence décente à regarder? Merci.
mkocabas
J'ai trouvé la solution en lisant certains. Merci.
mkocabas
3

J'ai déjà commenté l'utilisation du remblayage et comment il serait préférable car il est plus flexible, mais une autre solution possible est scanline. (Je dis possible parce que cela fait beaucoup d'hypothèses sur votre géométrie, mais pour l'ensemble particulier montré et beaucoup d'autres similaires, cela fonctionnerait.)

Pour votre exemple avec 3 points: Trouvez le sommet d'intersection à partir du segment v1, v2 et de la ligne sur laquelle se trouve v3. (Le sommet en haut à gauche de v2) Nous appellerons ce sommet v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

entrez la description de l'image ici

Cela s'appelle scanline parce que (dans l'image ci-dessus) vous descendez les lignes rouges et vertes simultanément, puis les lignes rouges et bleues balayant simultanément les lignes au fur et à mesure.

Cette solution serait très rapide s'il existe un modèle d'index, ce qui est souvent le cas. Sinon, un calcul serait nécessaire pour déterminer quel sommet voisin se trouve sur la ligne.

Le plus drôle est la ligne de balayage, les tests barycentriques (dans la boîte englobante de triangle) et le remplissage par inondation sont tous des moyens de dessiner des triangles dans le rendu 3D.

Andrew Wilson
la source
2

Je pense que vous pouvez calculer des coordonnées barycentriques liées à la surface pour chaque point de la surface, puis les utiliser pour vérifier l'intérieur ou l'extérieur du triangle.

Je n'ai pas d'algorithme exact à portée de main mais j'ai trouvé cet article suivant qui semble gérer exactement ce type de coordonnées.

Coordonnées barycentriques sur les surfaces

Dragonseel
la source
Merci pour la réponse et le document de référence. Je vais essayer de mettre en œuvre la méthode proposée.
mkocabas