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

[Dylan Smith]

---
 dlls/d3dx9_36/mesh.c |  119 +++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 113 insertions(+), 6 deletions(-)

diff --git a/dlls/d3dx9_36/mesh.c b/dlls/d3dx9_36/mesh.c
index 59ef997..4887c76 100644
--- a/dlls/d3dx9_36/mesh.c
+++ b/dlls/d3dx9_36/mesh.c
@@ -664,6 +664,21 @@ static int attrib_entry_compare(const DWORD **a, const DWORD **b)
     return delta;
 }
 
+struct vertex_attrib_duplication {
+    DWORD attrib;
+    DWORD vertex_index;
+    struct vertex_attrib_duplication *ptr;
+};
+
+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 = (BYTE*)a->ptr - (BYTE*)b->ptr;
+    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)
 {
@@ -750,15 +765,107 @@ 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 vertex_attrib_duplication **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) + max_entries * sizeof(*duplications));
+            if (!heads) {
+                hr = E_OUTOFMEMORY;
+                goto cleanup;
+            }
+            duplications = (struct vertex_attrib_duplication *)(heads + This->numvertices);
+            ZeroMemory(heads, This->numvertices * sizeof(*heads));
+            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 vertex_attrib_duplication *dup_ptr = heads[vertex_index];
+                if (!dup_ptr) {
+                    dup_ptr = next_duplicate++;
+                    dup_ptr->attrib = attrib_buffer[i / 3];
+                    dup_ptr->vertex_index = vertex_index;
+                    dup_ptr->ptr = NULL;
+                    heads[vertex_index] = dup_ptr;
+                } else if (is_splitting) {
+                    DWORD attrib = attrib_buffer[i / 3];
+                    while (dup_ptr->attrib != attrib)
+                    {
+                        if (!dup_ptr->ptr) {
+                            num_duplicates++;
+                            dup_ptr->ptr = next_duplicate++;
+                            dup_ptr = dup_ptr->ptr;
+                            dup_ptr->attrib = attrib;
+                            dup_ptr->vertex_index = vertex_index;
+                            dup_ptr->ptr = NULL;
+                            break;
+                        }
+                        dup_ptr = dup_ptr->ptr;
+                    }
+                }
+            }
+            new_num_vertices = next_duplicate - duplications;
+            /* Sorting depends primarily on the attribute value.
+             * Secondarily it depends on the vertex_index or position in
+             * the duplications array for the first instance of a vertex and
+             * their duplications respectively. This secondary value is
+             * stored in the ptr field, since sorting would invalidate it
+             * anyway. */
+            for (i = 0; i < new_num_vertices; i++)
+                duplications[i].ptr = &duplications[i];
+            for (i = 0; i < This->numvertices; i++) {
+                if (heads[i])
+                    heads[i]->ptr = (struct vertex_attrib_duplication*)&heads[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 */
+            ZeroMemory(heads, This->numvertices * sizeof(*heads));
+            for (i = 0; i < new_num_vertices; i++) {
+                DWORD vertex_index = duplications[i].vertex_index;
+                duplications[i].ptr = heads[vertex_index];
+                heads[vertex_index] = &duplications[i];
+            }
+
+            /* convert indices */
+            for (i = 0; i < This->numfaces * 3; i++) {
+                struct vertex_attrib_duplication *dup_ptr = heads[dword_indices[i]];
+                if (dup_ptr->ptr) {
+                    DWORD attrib = attrib_buffer[i / 3];
+                    while (attrib != dup_ptr->attrib)
+                        dup_ptr = dup_ptr->ptr;
+                }
+                dword_indices[i] = dup_ptr - duplications;
+            }
+
+            /* 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((This->numvertices + num_duplicates) * sizeof(DWORD), &vertex_remap);
+            if (FAILED(hr)) {
+                HeapFree(GetProcessHeap(), 0, heads);
+                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, heads);
+        }
 
         /* Reorder faces in order to sort the attribute table */
         face_remap = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(*face_remap));
-- 
1.7.2.5