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

[Michael Mc Donnell]

On Thu, Jun 30, 2011 at 6:42 PM, Michael Mc Donnell
<michael at mcdonnell.dk> wrote:
> 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.
>>
>>  ...
>>
>> 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.

I've implemented the look-up scheme that you described.

I have another question about my test. I've basically copied all the
test data from my ConvertAdjacencyToPointReps test, and then just
inverted the conditions. Should I merge the two tests, put the test
data in a separate function, or just ignore the duplication?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-d3dx9-test-Implemented-ConvertPointRepsToAdjacency-t.patch
Type: text/x-patch
Size: 15922 bytes
Desc: not available
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20110630/b44a0247/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-d3dx9-Implemented-ConvertPointRepsToAdjacency.patch
Type: text/x-patch
Size: 9261 bytes
Desc: not available
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20110630/b44a0247/attachment-0003.bin>