Re: GSoC-2011: Implement Missing Mesh Functions in Wine’s D3DX9

[Michael Mc Donnell]

On Thu, Jun 30, 2011 at 4:10 PM, Henri Verbeet <hverbeet at gmail.com> wrote:
> On 30 June 2011 14:49, Michael Mc Donnell <michael at 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.

Thanks for your suggestion. I think you're right that it is safe to
assume that most vertices will only be a part of a few edges. I'll
implement that for now.

> We did have a hash table inside wined3d at some point, I suppose you
> could also try resurrecting that from git history.

I'll stick with your suggestion as it seems easier to implement :-)

Btw I just searched source.winehq.org for hash_table and found several
hits in different dlls. I think it would be nice if they could all use
the same implementation like list.h and rbtree.h. That way it could
also later be used for other parts of wine. Should I add it to
http://wiki.winehq.org/JanitorialProjects?