[4/5] d3dx9: Implement D3DXMESHOPT_ATTRSORT vertex reordering.

[Dylan Smith]

On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni <matteo.mystral at gmail.com>wrote:

> 2011/5/6 Dylan Smith <dylan.ah.smith at gmail.com>:
> > +struct vertex_attrib_duplication {
> > +    DWORD attrib;
> > +    DWORD vertex_index;
> > +    struct vertex_attrib_duplication *ptr;
> > +};
> ...
> > +            struct vertex_attrib_duplication **heads = NULL; /* head of
> list for each vertex */
>
> You probably want to use Wine lists (from include/wine/list.h) instead
> of your own implementation.
>
> I only wanted a singly linked list.  The back links would be unused, but
would waste memory and update operations.  The linked list also gets
invalidated by sorting, so the ptr field is actually also used to store the
original position in the array for performing a stable sort. I don't think
using include/wine/list.h would make the code clearer, since it would be
like trying to abstract the implementation details, when those details are
relevant to the implementation (see the answer to the next question for an
example).

> +            heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices *
> sizeof(*heads) + max_entries * sizeof(*duplications));
> > +            duplications = (struct vertex_attrib_duplication *)(heads +
> This->numvertices);
>
> I'm not sure why you are usually sticking together many arrays in a
> single allocation. Economizing on the number of HeapAllocs is not a
> great reason IMHO.
>

Reducing memory allocations and keeping locality of memory references seemed
like a good idea, but in this case it actually affects the behaviour of the
sort. The pointer values are used in vertex_attrib_compare as a secondary
value, which largely affects the result since many vertices share the same
attribute value.  Pointers into the heads array are used to keep the first
use of each vertex in the original order of the vertices, and duplications
of those vertices must be sorted using a stable sort, so their original
position in the array are compared where the attribute value is the same.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20110508/40b6bd18/attachment.htm>