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

[Dylan Smith]

---
try 3: remap vertices in a helper function.
---
 dlls/d3dx9_36/mesh.c |  139 +++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 133 insertions(+), 6 deletions(-)

diff --git a/dlls/d3dx9_36/mesh.c b/dlls/d3dx9_36/mesh.c
index 0ed5030..650686a 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);
@@ -694,6 +695,131 @@ static HRESULT compact_mesh(ID3DXMeshImpl *This, DWORD *indices, DWORD *new_num_
     return D3D_OK;
 }
 
+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;
+}
+
+/* Creates vertex_remap for attribute sort optimization.
+ * Indices are updated according to the vertex_remap. */
+static HRESULT remap_vertices_for_attrsort(ID3DXMeshImpl *This, DWORD *indices,
+        const DWORD *attrib_buffer, BOOL split_vertices, DWORD *new_num_vertices,
+        DWORD *new_num_alloc_vertices, ID3DXBuffer **vertex_remap)
+{
+    HRESULT hr;
+    DWORD max_entries = split_vertices ? 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;
+    DWORD i;
+
+    heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*heads));
+    if (!heads) return E_OUTOFMEMORY;
+    duplications = HeapAlloc(GetProcessHeap(), 0, max_entries * sizeof(*duplications));
+    if (!duplications) {
+        HeapFree(GetProcessHeap(), 0, heads);
+        return E_OUTOFMEMORY;
+    }
+    for (i = 0; i < This->numvertices; i++)
+        list_init(&heads[i]);
+    next_duplicate = duplications;
+
+    for (i = 0; i < This->numfaces * 3; i++)
+    {
+        DWORD vertex_index = 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 (split_vertices) {
+            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[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)
+                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_num_alloc_vertices = This->numvertices + num_duplicates;
+    hr = D3DXCreateBuffer(*new_num_alloc_vertices * sizeof(DWORD), vertex_remap);
+    if (FAILED(hr)) {
+        HeapFree(GetProcessHeap(), 0, duplications);
+        return hr;
+    }
+    /* 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);
+    return D3D_OK;
+}
+
 /* count the number of unique attribute values in a sorted attribute buffer */
 static DWORD count_attributes(const DWORD *attrib_buffer, DWORD numfaces)
 {
@@ -847,16 +973,17 @@ static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flag
         hr = compact_mesh(This, dword_indices, &new_num_vertices, &vertex_remap);
         if (FAILED(hr)) goto cleanup;
     } else if (flags & D3DXMESHOPT_ATTRSORT) {
+        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;
+            BOOL split_vertices = !(flags & D3DXMESHOPT_DONOTSPLIT);
+            hr = remap_vertices_for_attrsort(This, dword_indices, attrib_buffer, split_vertices,
+                                             &new_num_vertices, &new_num_alloc_vertices, &vertex_remap);
+            if (FAILED(hr)) goto cleanup;
         }
 
-        hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
-        if (FAILED(hr)) goto cleanup;
-
         hr = remap_faces_for_attrsort(This, dword_indices, attrib_buffer, &sorted_attrib_buffer, &face_remap);
         if (FAILED(hr)) goto cleanup;
     }
-- 
1.7.2.5