9
votes

Algorithme pour convertir des sommets d'une bande triangulaire en polygone

J'ai un tableau avec des sommets représentant une bande triangulaire. J'ai besoin de le convertir en polygone. Il y a beaucoup de solution pour faire l'inverse, mais je n'ai pas trouvé l'un pour le problème ci-dessus. Ou cela pourrait être trop facile et je ne peux tout simplement pas le voir. S'il vous plaît aider.

opengl = compatible, voir http://en.wikipedia.org/wiki/triangle_strip

exemple: Pour cette bande http://fr.wikipedia.org/wiki/file:trianggle_strip_small.png < / a> J'ai besoin de sortie A B d F e C ou A C E F D B

algorithm opengl polygon triangulation

2 commentaires

Que voulez-vous dire par "bande triangulaire"? Est-ce une forme arbitraire construite de triangles? Ou quelque chose de plus spécifique?

Ceci est pour une "bande triangulaire", pas une "bande triangulaire". Un tristrip est un format de données qui spécifie une liste de triangles utilisant uniquement des ntrangles + 2 sommets, comme chaque triangle après la première utilisation des deux derniers sommets des triangles précédents.

3 Réponses :

0
votes

Il peut y avoir un raccourci si votre forme a une structure particulièrement simple, mais en général, je pense que vous voulez faire ce qui suit

Créez une liste de sommets et de bords de votre liste de triangles. Cela implique de détecter des points partagés (espérons-le, ce sont des correspondances exactes afin que vous puissiez les trouver en hachage au lieu d'avoir besoin d'une sorte de recherche floue) et de lignes partagées (c'est facile - il suffit de ne pas dessiner deux bords entre la même paire de sommets partagés) .
Trouvez le point le plus haut gauche.
Trouvez le bord qui se déplace aussi haut de gauche que possible et est dans la direction dans le sens anti-horaire.
Marchez jusqu'au sommet suivant.
Trouvez le bord suivant qui double le plus possible sur le précédent autant que possible.
continue d'aller jusqu'à ce que vous atteigniez à nouveau la plupart des points de gauche.

0 commentaires

6
votes

Je crois que ce qui suit devrait fonctionner:

traversez la liste des sommets. Ajoutez le premier point à votre polygone. Poussez le deuxième point sur la pile. Ajoutez le troisième point au polygone. Continuez en alternance entre les points de poussée sur la pile et les ajouter au polygone jusqu'à atteindre la fin de la liste. Lorsque vous arrivez à la fin de la liste, affichez les points de la pile et ajoutez-les au polygone.

5 commentaires

@Belisarius: Il n'essaie pas de "simplifier" le polygone, si c'est ce que vous voulez dire - c'est-à-dire que cela va créer un polygone qui correspond exactement au contour de la bande triangulaire exactement. Si (par exemple) vous avez tessellé une surface dans une longue bande de triangle qui vent beaucoup, il va produire un polygone qui se vent bien de la même manière. Au moins si vous utilisez 3 dimensions, vous ne pouvez pas faire beaucoup d'autre, cependant, les points intérieurs ont souvent différentes valeurs de Z qui doivent être préservées.

Ouais. Je pensais que c'était l'intention de l'OP. J'ai peut-être tort. Tnx.

Afin de simplifier le polygone, unifiez les noms des sommets égaux, puis passez dans votre liste circulaire, en remplaçant le modèle ABA avec A, jusqu'à ce que le remplacement de ce type ne soit plus possible.

@belisarius - Il n'y a pas de points intérieurs sur une bande de triangle.

@ Dash-Tom-Bang Oui, j'ai compris que longtemps après avoir posté le commentaire. Merci.

1
votes

text alt

Je suppose que votre bande triangulaire est toujours connectée de la même manière (que je croire est vrai pour OpenGL). P>

Les sommets "inférieurs" sont toujours deux Apart: A, C, E, ... Li>
le "haut" Les sommets sont toujours deux séparés: B, D, F, ... li> ul>
Prenez la liste "En bas" et appendez l'inverse de la liste "Top". (ACEFDB pour l'exemple) p>

ou, plus directement, à l'aide d'un index à base de zéro au lieu de lettres: p>
```
// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )
```

0 commentaires