On 30 June 2011 14:49, Michael Mc Donnell michael@mcdonnell.dk wrote:
In init_edge_face_map I initialize an array of edge_face structs, and in find_adjacent_face I do a linear search through that array. I would like to replace the array with a hash table, so that the search time becomes constant. I've found a standard list (wine/list.h) and red-black tree implementation (wine/rbtree.h), but not a standard hash table implementation. Is there a standard hash table implementation, should I roll my own or find an LGPL'ed one?
I'm not sure if a hash table would be faster and how much, but an easy way to make the lookup cheaper would be to store the edge -> face map as a list for each vertex.
So e.g. if you have these faces: f0: v0, v2, v1 f1: v1, v4, v3 f2: v1, v2, v4 f3: v2, v5, v4
You'd build these lists: v0: {v2:f0} v1: {v0:f0}, {v4:f1}, {v2:f2} v2: {v1:f0}, {v4:f2}, {v5:f3} v3: {v1:f1} v4: {v3:f1}, {v1:f2}, {v2:f3} v5: {v4:f3}
It's then mostly trivial to determine adjacency. This assumes most vertices are only part of a handful of edges, but I don't think that's unreasonable in practice.
We did have a hash table inside wined3d at some point, I suppose you could also try resurrecting that from git history.