Algorithm for unique find edges from polygon mesh

Question

I'm looking for a good algorithm that can give me the unique edges from a set of polygon data. In this case, the polygons are defined by two arrays. One array is the number of points per polygon, and the other array is a list of vertex indices.

I have a version that is working, but performance gets slow when reaching over 500,000 polys. My version walks over each face and adds each edge's sorted vertices to an stl::set. My data set will be primarily triangle and quad polys, and most edges will be shared.

Is there a smarter algorithm for this?

Answer 1

Yes
Use a double hash map.
Every edge has two indexes A,B. lets say that A > B.
The first, top level hash-map maps A to another hash-map which is in turn maps B to some value which represents the information you want about every edge. (or just a bool if you don't need to keep information for edges).
Essentially this creates a two level tree composed of hash maps.

To look up an edge in this structure you take the larger index, look it up in the top level and end up with a hash map. then take the smaller index and look it up in this second hash map.

Answer 2

Just to clarify, you want, for a polygon list like this:

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

Then instead of edges like this:

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

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

then you want to remove the duplicate B - C vs. C - B edge and share it?

What kind of performance problem are you seeing with your algorithm? I'd say a set that has a reasonable hash implementation should perform pretty ok. On the other hand, if your hash is not optimal for the data, you'll have lots of collisions which might affect performance badly.

Answer 3

You are both correct. Using a good hashset has gotten the performance well beyond required levels. I ended up rolling my own little hash set.

The total number of edges will be between N/2 and N. N being the number of unique vertices in the mesh. All shared edges will be N/2, and all unique edges will be N. From there I allocate a buffer of uint64's and pack my indices into these values. Using a small set of unique tables I can find the unique edges fast!

Answer 4

heres a C implementation of edge hashing used in Blender exactly for the purpose of quickly creating edges from faces, may give some hints for others to make their own.

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

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

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

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

Answer 5

First you need to make sure your vertices are unique. That is if you want only one edge at a certain position. Then I use this data structure

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge contains the vertex indices that make up the edge in sorted order. Hence if sampleEdge is an edge made up of vertices with index numbers 12 and 5, sampleEdge.first = 5 and sampleEdge.12

Then you can just do

uniqueEdges[sampleEdge] = true;

for all the edges. uniqueEdges will hold all the unique edges.