[prev in list] [next in list] [prev in thread] [next in thread] 

List:       wine-devel
Subject:    =?UTF-8?Q?Re=3A_GSoC=2D2011=3A_Implement_Missing_Mesh_Functions_in_W?=
From:       Henri Verbeet <hverbeet () gmail ! com>
Date:       2011-06-30 14:10:41
Message-ID: BANLkTik_+OsNjvTBessGBUTNzOMow=caqw () mail ! gmail ! com
[Download RAW message or body]

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.


[prev in list] [next in list] [prev in thread] [next in thread]