[4/5] d3dx9: Implement D3DXMESHOPT_ATTRSORT vertex reordering. (try 2)

[Dylan Smith]

---
try 2:
- Use include/wine/list.h for linked list.
- Use separate heap allocations for separate arrays.
---
 dlls/d3dx9_36/mesh.c |  130 +++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 124 insertions(+), 6 deletions(-)

diff --git a/dlls/d3dx9_36/mesh.c b/dlls/d3dx9_36/mesh.c
index eaa9763..45f5f70 100644
--- a/dlls/d3dx9_36/mesh.c
+++ b/dlls/d3dx9_36/mesh.c
@@ -32,6 +32,7 @@
 #include "d3dx9.h"
 #include "wine/debug.h"
 #include "wine/unicode.h"
+#include "wine/list.h"
 #include "d3dx9_36_private.h"
 
 WINE_DEFAULT_DEBUG_CHANNEL(d3dx);
@@ -665,6 +666,24 @@ static int attrib_entry_compare(const DWORD **a, const DWORD **b)
     return delta;
 }
 
+struct vertex_attrib_duplication {
+    DWORD attrib;
+    DWORD vertex_index;
+    union {
+        int orig_order;
+        struct list entry;
+    } u;
+};
+
+static int vertex_attrib_compare(const struct vertex_attrib_duplication *a,
+                                 const struct vertex_attrib_duplication *b)
+{
+    int delta = a->attrib - b->attrib;
+    if (delta) return delta;
+    delta = a->u.orig_order - b->u.orig_order;
+    return delta;
+}
+
 static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
                                                     DWORD *face_remap_out, LPD3DXBUFFER *vertex_remap_out)
 {
@@ -751,15 +770,114 @@ static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flag
         DWORD last_attribute;
         DWORD min_vertex, max_vertex;
 
+        hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
+        if (FAILED(hr)) goto cleanup;
+
         if (!(flags & D3DXMESHOPT_IGNOREVERTS))
         {
-            FIXME("D3DXMESHOPT_ATTRSORT vertex reordering not implemented.\n");
-            hr = E_NOTIMPL;
-            goto cleanup;
-        }
+            /* Reorder vertices */
+            BOOL is_splitting = !(flags & D3DXMESHOPT_DONOTSPLIT);
+            DWORD max_entries = is_splitting ? This->numfaces * 3 : This->numvertices;
+            struct vertex_attrib_duplication *next_duplicate = NULL;
+            DWORD num_duplicates = 0;
+            struct list *heads = NULL; /* head of list for each vertex */
+            struct vertex_attrib_duplication *duplications;
+            DWORD *vertex_remap_ptr;
+
+            heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*heads));
+            if (!heads) {
+                hr = E_OUTOFMEMORY;
+                goto cleanup;
+            }
+            duplications = HeapAlloc(GetProcessHeap(), 0, max_entries * sizeof(*duplications));
+            if (!duplications) {
+                HeapFree(GetProcessHeap(), 0, heads);
+                hr = E_OUTOFMEMORY;
+                goto cleanup;
+            }
+            for (i = 0; i < This->numvertices; i++)
+                list_init(&heads[i]);
+            next_duplicate = duplications;
 
-        hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
-        if (FAILED(hr)) goto cleanup;
+            for (i = 0; i < This->numfaces * 3; i++)
+            {
+                DWORD vertex_index = dword_indices[i];
+                struct list *vertex_list = &heads[vertex_index];
+                struct vertex_attrib_duplication *dup_ptr;
+                if (list_empty(vertex_list)) {
+                    dup_ptr = next_duplicate++;
+                    dup_ptr->attrib = attrib_buffer[i / 3];
+                    dup_ptr->vertex_index = vertex_index;
+                    list_add_tail(vertex_list, &dup_ptr->u.entry);
+                } else if (is_splitting) {
+                    DWORD attrib = attrib_buffer[i / 3];
+                    BOOL found = FALSE;
+                    LIST_FOR_EACH_ENTRY(dup_ptr, vertex_list, struct vertex_attrib_duplication, u.entry)
+                    {
+                        if (dup_ptr->attrib == attrib) {
+                            found = TRUE;
+                            break;
+                        }
+                    }
+                    if (!found) {
+                        num_duplicates++;
+                        dup_ptr = next_duplicate++;
+                        dup_ptr->attrib = attrib;
+                        dup_ptr->vertex_index = vertex_index;
+                        list_add_tail(vertex_list, &dup_ptr->u.entry);
+                    }
+                }
+            }
+            new_num_vertices = next_duplicate - duplications;
+            /* Sorting must be a stable sort to match native behaviour.
+             * The orig_order field mimics the desired relative original order
+             * for use in vertex_attrib_compare. */
+            for (i = 0; i < new_num_vertices; i++)
+                duplications[i].u.orig_order = This->numvertices + i;
+            for (i = 0; i < This->numvertices; i++) {
+                if (!list_empty(&heads[i]))
+                    LIST_ENTRY(list_head(&heads[i]), struct vertex_attrib_duplication, u.entry)->u.orig_order = i;
+            }
+            qsort(duplications, new_num_vertices, sizeof(*duplications),
+                  (int(*)(const void *, const void *))vertex_attrib_compare);
+            /* reconstruct the list of duplications for each vertex index */
+            for (i = 0; i < This->numvertices; i++)
+                list_init(&heads[i]);
+            for (i = 0; i < new_num_vertices; i++)
+                list_add_tail(&heads[duplications[i].vertex_index], &duplications[i].u.entry);
+
+            /* convert indices */
+            for (i = 0; i < This->numfaces * 3; i++) {
+                struct list *vertex_list = &heads[dword_indices[i]];
+                struct vertex_attrib_duplication *dup_ptr;
+                DWORD attrib = attrib_buffer[i / 3];
+
+                LIST_FOR_EACH_ENTRY(dup_ptr, vertex_list, struct vertex_attrib_duplication, u.entry)
+                {
+                    if (attrib == dup_ptr->attrib)
+                        dword_indices[i] = dup_ptr - duplications;
+                }
+            }
+
+            HeapFree(GetProcessHeap(), 0, heads);
+
+            /* native behaviour is to allocate a buffer this big, even though using new_num_vertices
+             * would make more sense. */
+            new_vertex_buffer_size = This->numvertices + num_duplicates;
+            hr = D3DXCreateBuffer(new_vertex_buffer_size * sizeof(DWORD), &vertex_remap);
+            if (FAILED(hr)) {
+                HeapFree(GetProcessHeap(), 0, duplications);
+                goto cleanup;
+            }
+            /* create new->old vertex map */
+            vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
+            for (i = 0; i < new_num_vertices; i++)
+                *vertex_remap_ptr++ = duplications[i].vertex_index;
+            for (; i < This->numvertices + num_duplicates; i++)
+                *vertex_remap_ptr++ = -1;
+
+            HeapFree(GetProcessHeap(), 0, duplications);
+        }
 
         /* Reorder faces in order to sort the attribute table */
         face_remap = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(*face_remap));
-- 
1.7.2.5