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

[Matteo Bruni]

2011/5/8 Dylan Smith <dylan.ah.smith at gmail.com>:
> 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).

It is an ongoing effort (almost complete I think) to replace custom
list implementations with the generic one through the Wine codebase. I
don't think this case is so special to require a custom list. I don't
have a strong opinion here, but, e.g., I don't find adding one or two
fields to the structure a big drawback.

>>
>> > +            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.

I was referring to allocating "heads" and "duplications" from the same
call, which, as far as I can see, is not required.
Regarding the sorting requirements, those can also be addressed by
adding another index field to the structure.