Algorithme pour rechercher des arêtes uniques à partir d'un maillage polygonal

Question

Je cherche un bon algorithme qui puisse me donner les arêtes uniques d’un ensemble de données de polygones. Dans ce cas, les polygones sont définis par deux tableaux. Un tableau est le nombre de points par polygone et l’autre est une liste d’index de sommets.

J'ai une version qui fonctionne mais les performances ralentissent lorsque l'on atteint plus de 500 000 polys. Ma version parcourt chaque face et ajoute les sommets triés de chaque bord à un stl :: set. Mes données seront principalement des triangles et des quadruples, et la plupart des arêtes seront partagées.

Existe-t-il un algorithme plus intelligent pour cela?

Answer 1

Oui
Utilisez une double carte de hachage.
Chaque bord a deux index A, B. Disons que A > B.
La première, carte de hachage de niveau supérieur, associe une carte de hachage A à une autre, laquelle associe à son tour B à une valeur représentant l'information que vous souhaitez sur chaque bord. (ou juste un bool si vous n'avez pas besoin de garder des informations pour les bords).
Cela crée essentiellement un arbre à deux niveaux composé de cartes de hachage.

Pour rechercher une arête dans cette structure, vous devez utiliser l'index le plus large, le rechercher au niveau supérieur et obtenir une carte de hachage. puis prenez le plus petit index et regardez-le dans cette deuxième carte de hachage.

Answer 2

Juste pour clarifier, vous voulez, pour une liste de polygones comme celle-ci:

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

Puis au lieu d'arêtes comme ceci:

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

alors vous voulez supprimer le bord B - C vs C - B dupliqué et le partager?

Quel genre de problème de performance voyez-vous avec votre algorithme? Je dirais qu'un ensemble avec une implémentation de hachage raisonnable devrait assez bien fonctionner. D'autre part, si votre hachage n'est pas optimal pour les données, vous aurez de nombreuses collisions qui pourraient affecter les performances.

Answer 3

Vous avez tous les deux raison. L'utilisation d'un bon hashset a permis d'obtenir des performances bien au-delà des niveaux requis. J'ai fini par rouler mon propre petit ensemble de hachage.

Le nombre total d'arêtes sera compris entre N / 2 et N. N étant le nombre de sommets uniques dans le maillage. Toutes les arêtes partagées seront N / 2 et toutes les arêtes uniques seront N. À partir de là, je vais allouer un tampon de uint64 et ranger mes index dans ces valeurs. En utilisant un petit ensemble de tables uniques, je peux trouver rapidement les bords uniques!

Answer 4

Voici une implémentation C du hachage des bords utilisée dans Blender dans le seul but de créer rapidement des bords à partir de visages, ce qui peut donner des conseils aux autres.

http: // gitorious. org / blenderprojects / blender / blobs / master / blender / source / blender / blenlib / intern / edgehash.c

http://gitorious.org/ projets blender / blender / blobs / master / blender / source / blender / blenlib / BLI_edgehash.h

Ceci utilise BLI_mempool, https://gitorious.org/blenderprojects /blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/ projets blender / blender / blobs / master / blender / source / blender / blenlib / BLI_mempool.h

Answer 5

Tout d'abord, vous devez vous assurer que vos sommets sont uniques. C'est-à-dire si vous ne voulez qu'un seul bord à une certaine position. Ensuite, j'utilise cette structure de données

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge contient les index de sommet qui composent l’arête dans l’ordre trié. Par conséquent, si sampleEdge est une arête composée de sommets portant les numéros d’index 12 et 5, sampleEdge.first = 5 et sampleEdge.12

Ensuite, vous pouvez simplement faire

uniqueEdges[sampleEdge] = true;

pour tous les bords. uniqueEdges tiendra toutes les arêtes uniques.