git.oblomov.eu Git - wine/blob - dlls/d3dx9_36/mesh.c

   1  /*
   2  * Mesh operations specific to D3DX9.
   3  *
   4  * Copyright (C) 2005 Henri Verbeet
   5  * Copyright (C) 2006 Ivan Gyurdiev
   6  * Copyright (C) 2009 David Adam
   7  * Copyright (C) 2010 Tony Wasserka
   8  * Copyright (C) 2011 Dylan Smith
   9  * Copyright (C) 2011 Michael Mc Donnell
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  24  */
  25
  26 #include "config.h"
  27 #include "wine/port.h"
  28
  29 #define COBJMACROS
  30 #define NONAMELESSUNION
  31 #include <assert.h>
  32 #ifdef HAVE_FLOAT_H
  33 # include <float.h>
  34 #endif
  35 #include "windef.h"
  36 #include "wingdi.h"
  37 #include "d3dx9.h"
  38 #undef MAKE_DDHRESULT
  39 #include "dxfile.h"
  40 #include "rmxfguid.h"
  41 #include "rmxftmpl.h"
  42 #include "wine/debug.h"
  43 #include "wine/unicode.h"
  44 #include "wine/list.h"
  45 #include "d3dx9_36_private.h"
  46
  47 WINE_DEFAULT_DEBUG_CHANNEL(d3dx);
  48
  49 typedef struct ID3DXMeshImpl
  50 {
  51     ID3DXMesh ID3DXMesh_iface;
  52     LONG ref;
  53
  54     DWORD numfaces;
  55     DWORD numvertices;
  56     DWORD options;
  57     DWORD fvf;
  58     IDirect3DDevice9 *device;
  59     D3DVERTEXELEMENT9 cached_declaration[MAX_FVF_DECL_SIZE];
  60     IDirect3DVertexDeclaration9 *vertex_declaration;
  61     UINT vertex_declaration_size;
  62     UINT num_elem;
  63     IDirect3DVertexBuffer9 *vertex_buffer;
  64     IDirect3DIndexBuffer9 *index_buffer;
  65     DWORD *attrib_buffer;
  66     int attrib_buffer_lock_count;
  67     DWORD attrib_table_size;
  68     D3DXATTRIBUTERANGE *attrib_table;
  69 } ID3DXMeshImpl;
  70
  71 static inline ID3DXMeshImpl *impl_from_ID3DXMesh(ID3DXMesh *iface)
  72 {
  73     return CONTAINING_RECORD(iface, ID3DXMeshImpl, ID3DXMesh_iface);
  74 }
  75
  76 static HRESULT WINAPI ID3DXMeshImpl_QueryInterface(ID3DXMesh *iface, REFIID riid, LPVOID *object)
  77 {
  78     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  79
  80     TRACE("(%p)->(%s, %p)\n", This, debugstr_guid(riid), object);
  81
  82     if (IsEqualGUID(riid, &IID_IUnknown) ||
  83         IsEqualGUID(riid, &IID_ID3DXBaseMesh) ||
  84         IsEqualGUID(riid, &IID_ID3DXMesh))
  85     {
  86         iface->lpVtbl->AddRef(iface);
  87         *object = This;
  88         return S_OK;
  89     }
  90
  91     WARN("Interface %s not found.\n", debugstr_guid(riid));
  92
  93     return E_NOINTERFACE;
  94 }
  95
  96 static ULONG WINAPI ID3DXMeshImpl_AddRef(ID3DXMesh *iface)
  97 {
  98     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  99
 100     TRACE("(%p)->(): AddRef from %d\n", This, This->ref);
 101
 102     return InterlockedIncrement(&This->ref);
 103 }
 104
 105 static ULONG WINAPI ID3DXMeshImpl_Release(ID3DXMesh *iface)
 106 {
 107     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 108     ULONG ref = InterlockedDecrement(&This->ref);
 109
 110     TRACE("(%p)->(): Release from %d\n", This, ref + 1);
 111
 112     if (!ref)
 113     {
 114         IDirect3DIndexBuffer9_Release(This->index_buffer);
 115         IDirect3DVertexBuffer9_Release(This->vertex_buffer);
 116         if (This->vertex_declaration)
 117             IDirect3DVertexDeclaration9_Release(This->vertex_declaration);
 118         IDirect3DDevice9_Release(This->device);
 119         HeapFree(GetProcessHeap(), 0, This->attrib_buffer);
 120         HeapFree(GetProcessHeap(), 0, This->attrib_table);
 121         HeapFree(GetProcessHeap(), 0, This);
 122     }
 123
 124     return ref;
 125 }
 126
 127 /*** ID3DXBaseMesh ***/
 128 static HRESULT WINAPI ID3DXMeshImpl_DrawSubset(ID3DXMesh *iface, DWORD attrib_id)
 129 {
 130     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 131     HRESULT hr;
 132     DWORD face_start;
 133     DWORD face_end = 0;
 134     DWORD vertex_size;
 135
 136     TRACE("(%p)->(%u)\n", This, attrib_id);
 137
 138     if (!This->vertex_declaration)
 139     {
 140         WARN("Can't draw a mesh with an invalid vertex declaration.\n");
 141         return E_FAIL;
 142     }
 143
 144     vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 145
 146     hr = IDirect3DDevice9_SetVertexDeclaration(This->device, This->vertex_declaration);
 147     if (FAILED(hr)) return hr;
 148     hr = IDirect3DDevice9_SetStreamSource(This->device, 0, This->vertex_buffer, 0, vertex_size);
 149     if (FAILED(hr)) return hr;
 150     hr = IDirect3DDevice9_SetIndices(This->device, This->index_buffer);
 151     if (FAILED(hr)) return hr;
 152
 153     while (face_end < This->numfaces)
 154     {
 155         for (face_start = face_end; face_start < This->numfaces; face_start++)
 156         {
 157             if (This->attrib_buffer[face_start] == attrib_id)
 158                 break;
 159         }
 160         if (face_start >= This->numfaces)
 161             break;
 162         for (face_end = face_start + 1; face_end < This->numfaces; face_end++)
 163         {
 164             if (This->attrib_buffer[face_end] != attrib_id)
 165                 break;
 166         }
 167
 168         hr = IDirect3DDevice9_DrawIndexedPrimitive(This->device, D3DPT_TRIANGLELIST,
 169                 0, 0, This->numvertices, face_start * 3, face_end - face_start);
 170         if (FAILED(hr)) return hr;
 171     }
 172
 173     return D3D_OK;
 174 }
 175
 176 static DWORD WINAPI ID3DXMeshImpl_GetNumFaces(ID3DXMesh *iface)
 177 {
 178     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 179
 180     TRACE("(%p)\n", This);
 181
 182     return This->numfaces;
 183 }
 184
 185 static DWORD WINAPI ID3DXMeshImpl_GetNumVertices(ID3DXMesh *iface)
 186 {
 187     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 188
 189     TRACE("(%p)\n", This);
 190
 191     return This->numvertices;
 192 }
 193
 194 static DWORD WINAPI ID3DXMeshImpl_GetFVF(ID3DXMesh *iface)
 195 {
 196     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 197
 198     TRACE("(%p)\n", This);
 199
 200     return This->fvf;
 201 }
 202
 203 static void copy_declaration(D3DVERTEXELEMENT9 *dst, const D3DVERTEXELEMENT9 *src, UINT num_elem)
 204 {
 205     memcpy(dst, src, num_elem * sizeof(*src));
 206 }
 207
 208 static HRESULT WINAPI ID3DXMeshImpl_GetDeclaration(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 209 {
 210     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 211
 212     TRACE("(%p)\n", This);
 213
 214     if (declaration == NULL) return D3DERR_INVALIDCALL;
 215
 216     copy_declaration(declaration, This->cached_declaration, This->num_elem);
 217
 218     return D3D_OK;
 219 }
 220
 221 static DWORD WINAPI ID3DXMeshImpl_GetNumBytesPerVertex(ID3DXMesh *iface)
 222 {
 223     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 224
 225     TRACE("iface (%p)\n", This);
 226
 227     return This->vertex_declaration_size;
 228 }
 229
 230 static DWORD WINAPI ID3DXMeshImpl_GetOptions(ID3DXMesh *iface)
 231 {
 232     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 233
 234     TRACE("(%p)\n", This);
 235
 236     return This->options;
 237 }
 238
 239 static HRESULT WINAPI ID3DXMeshImpl_GetDevice(ID3DXMesh *iface, LPDIRECT3DDEVICE9 *device)
 240 {
 241     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 242
 243     TRACE("(%p)->(%p)\n", This, device);
 244
 245     if (device == NULL) return D3DERR_INVALIDCALL;
 246     *device = This->device;
 247     IDirect3DDevice9_AddRef(This->device);
 248
 249     return D3D_OK;
 250 }
 251
 252 static HRESULT WINAPI ID3DXMeshImpl_CloneMeshFVF(ID3DXMesh *iface, DWORD options, DWORD fvf, LPDIRECT3DDEVICE9 device, LPD3DXMESH *clone_mesh)
 253 {
 254     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 255     HRESULT hr;
 256     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
 257
 258     TRACE("(%p)->(%x,%x,%p,%p)\n", This, options, fvf, device, clone_mesh);
 259
 260     hr = D3DXDeclaratorFromFVF(fvf, declaration);
 261     if (FAILED(hr)) return hr;
 262
 263     return iface->lpVtbl->CloneMesh(iface, options, declaration, device, clone_mesh);
 264 }
 265
 266 static HRESULT WINAPI ID3DXMeshImpl_CloneMesh(ID3DXMesh *iface, DWORD options, CONST D3DVERTEXELEMENT9 *declaration, LPDIRECT3DDEVICE9 device,
 267                                               LPD3DXMESH *clone_mesh_out)
 268 {
 269     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 270     ID3DXMeshImpl *cloned_this;
 271     ID3DXMesh *clone_mesh;
 272     D3DVERTEXELEMENT9 orig_declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
 273     void *data_in, *data_out;
 274     DWORD vertex_size;
 275     HRESULT hr;
 276     int i;
 277
 278     TRACE("(%p)->(%x,%p,%p,%p)\n", This, options, declaration, device, clone_mesh_out);
 279
 280     if (!clone_mesh_out)
 281         return D3DERR_INVALIDCALL;
 282
 283     hr = iface->lpVtbl->GetDeclaration(iface, orig_declaration);
 284     if (FAILED(hr)) return hr;
 285
 286     for (i = 0; orig_declaration[i].Stream != 0xff; i++) {
 287         if (memcmp(&orig_declaration[i], &declaration[i], sizeof(*declaration)))
 288         {
 289             FIXME("Vertex buffer conversion not implemented.\n");
 290             return E_NOTIMPL;
 291         }
 292     }
 293
 294     hr = D3DXCreateMesh(This->numfaces, This->numvertices, options & ~D3DXMESH_VB_SHARE,
 295                         declaration, device, &clone_mesh);
 296     if (FAILED(hr)) return hr;
 297
 298     cloned_this = impl_from_ID3DXMesh(clone_mesh);
 299     vertex_size = clone_mesh->lpVtbl->GetNumBytesPerVertex(clone_mesh);
 300
 301     if (options & D3DXMESH_VB_SHARE) {
 302         IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
 303         /* FIXME: refactor to avoid creating a new vertex buffer */
 304         IDirect3DVertexBuffer9_Release(cloned_this->vertex_buffer);
 305         cloned_this->vertex_buffer = This->vertex_buffer;
 306     } else {
 307         hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, &data_in);
 308         if (FAILED(hr)) goto error;
 309         hr = clone_mesh->lpVtbl->LockVertexBuffer(clone_mesh, D3DLOCK_DISCARD, &data_out);
 310         if (FAILED(hr)) {
 311             iface->lpVtbl->UnlockVertexBuffer(iface);
 312             goto error;
 313         }
 314         memcpy(data_out, data_in, This->numvertices * vertex_size);
 315         clone_mesh->lpVtbl->UnlockVertexBuffer(clone_mesh);
 316         iface->lpVtbl->UnlockVertexBuffer(iface);
 317     }
 318
 319     hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, &data_in);
 320     if (FAILED(hr)) goto error;
 321     hr = clone_mesh->lpVtbl->LockIndexBuffer(clone_mesh, D3DLOCK_DISCARD, &data_out);
 322     if (FAILED(hr)) {
 323         iface->lpVtbl->UnlockIndexBuffer(iface);
 324         goto error;
 325     }
 326     if ((options ^ This->options) & D3DXMESH_32BIT) {
 327         if (options & D3DXMESH_32BIT) {
 328             for (i = 0; i < This->numfaces * 3; i++)
 329                 ((DWORD*)data_out)[i] = ((WORD*)data_in)[i];
 330         } else {
 331             for (i = 0; i < This->numfaces * 3; i++)
 332                 ((WORD*)data_out)[i] = ((DWORD*)data_in)[i];
 333         }
 334     } else {
 335         memcpy(data_out, data_in, This->numfaces * 3 * (options & D3DXMESH_32BIT ? 4 : 2));
 336     }
 337     clone_mesh->lpVtbl->UnlockIndexBuffer(clone_mesh);
 338     iface->lpVtbl->UnlockIndexBuffer(iface);
 339
 340     memcpy(cloned_this->attrib_buffer, This->attrib_buffer, This->numfaces * sizeof(*This->attrib_buffer));
 341
 342     if (This->attrib_table_size)
 343     {
 344         cloned_this->attrib_table_size = This->attrib_table_size;
 345         cloned_this->attrib_table = HeapAlloc(GetProcessHeap(), 0, This->attrib_table_size * sizeof(*This->attrib_table));
 346         if (!cloned_this->attrib_table) {
 347             hr = E_OUTOFMEMORY;
 348             goto error;
 349         }
 350         memcpy(cloned_this->attrib_table, This->attrib_table, This->attrib_table_size * sizeof(*This->attrib_table));
 351     }
 352
 353     *clone_mesh_out = clone_mesh;
 354
 355     return D3D_OK;
 356 error:
 357     IUnknown_Release(clone_mesh);
 358     return hr;
 359 }
 360
 361 static HRESULT WINAPI ID3DXMeshImpl_GetVertexBuffer(ID3DXMesh *iface, LPDIRECT3DVERTEXBUFFER9 *vertex_buffer)
 362 {
 363     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 364
 365     TRACE("(%p)->(%p)\n", This, vertex_buffer);
 366
 367     if (vertex_buffer == NULL) return D3DERR_INVALIDCALL;
 368     *vertex_buffer = This->vertex_buffer;
 369     IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
 370
 371     return D3D_OK;
 372 }
 373
 374 static HRESULT WINAPI ID3DXMeshImpl_GetIndexBuffer(ID3DXMesh *iface, LPDIRECT3DINDEXBUFFER9 *index_buffer)
 375 {
 376     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 377
 378     TRACE("(%p)->(%p)\n", This, index_buffer);
 379
 380     if (index_buffer == NULL) return D3DERR_INVALIDCALL;
 381     *index_buffer = This->index_buffer;
 382     IDirect3DIndexBuffer9_AddRef(This->index_buffer);
 383
 384     return D3D_OK;
 385 }
 386
 387 static HRESULT WINAPI ID3DXMeshImpl_LockVertexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 388 {
 389     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 390
 391     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 392
 393     return IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, data, flags);
 394 }
 395
 396 static HRESULT WINAPI ID3DXMeshImpl_UnlockVertexBuffer(ID3DXMesh *iface)
 397 {
 398     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 399
 400     TRACE("(%p)\n", This);
 401
 402     return IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
 403 }
 404
 405 static HRESULT WINAPI ID3DXMeshImpl_LockIndexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 406 {
 407     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 408
 409     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 410
 411     return IDirect3DIndexBuffer9_Lock(This->index_buffer, 0, 0, data, flags);
 412 }
 413
 414 static HRESULT WINAPI ID3DXMeshImpl_UnlockIndexBuffer(ID3DXMesh *iface)
 415 {
 416     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 417
 418     TRACE("(%p)\n", This);
 419
 420     return IDirect3DIndexBuffer9_Unlock(This->index_buffer);
 421 }
 422
 423 static HRESULT WINAPI ID3DXMeshImpl_GetAttributeTable(ID3DXMesh *iface, D3DXATTRIBUTERANGE *attrib_table, DWORD *attrib_table_size)
 424 {
 425     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 426
 427     TRACE("(%p)->(%p,%p)\n", This, attrib_table, attrib_table_size);
 428
 429     if (attrib_table_size)
 430         *attrib_table_size = This->attrib_table_size;
 431
 432     if (attrib_table)
 433         CopyMemory(attrib_table, This->attrib_table, This->attrib_table_size * sizeof(*attrib_table));
 434
 435     return D3D_OK;
 436 }
 437
 438 struct edge_face
 439 {
 440     struct list entry;
 441     DWORD v2;
 442     DWORD face;
 443 };
 444
 445 struct edge_face_map
 446 {
 447     struct list *lists;
 448     struct edge_face *entries;
 449 };
 450
 451 /* Builds up a map of which face a new edge belongs to. That way the adjacency
 452  * of another edge can be looked up. An edge has an adjacent face if there
 453  * is an edge going in the opposite direction in the map. For example if the
 454  * edge (v1, v2) belongs to face 4, and there is a mapping (v2, v1)->7, then
 455  * face 4 and 7 are adjacent.
 456  *
 457  * Each edge might have been replaced with another edge, or none at all. There
 458  * is at most one edge to face mapping, i.e. an edge can only belong to one
 459  * face.
 460  */
 461 static HRESULT init_edge_face_map(struct edge_face_map *edge_face_map, CONST DWORD *index_buffer, CONST DWORD *point_reps, CONST DWORD num_faces)
 462 {
 463     DWORD face, edge;
 464     DWORD i;
 465
 466     edge_face_map->lists = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->lists));
 467     if (!edge_face_map->lists) return E_OUTOFMEMORY;
 468
 469     edge_face_map->entries = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->entries));
 470     if (!edge_face_map->entries) return E_OUTOFMEMORY;
 471
 472
 473     /* Initialize all lists */
 474     for (i = 0; i < 3 * num_faces; i++)
 475     {
 476         list_init(&edge_face_map->lists[i]);
 477     }
 478     /* Build edge face mapping */
 479     for (face = 0; face < num_faces; face++)
 480     {
 481         for (edge = 0; edge < 3; edge++)
 482         {
 483             DWORD v1 = index_buffer[3*face + edge];
 484             DWORD v2 = index_buffer[3*face + (edge+1)%3];
 485             DWORD new_v1 = point_reps[v1]; /* What v1 has been replaced with */
 486             DWORD new_v2 = point_reps[v2];
 487
 488             if (v1 != v2) /* Only map non-collapsed edges */
 489             {
 490                 i = 3*face + edge;
 491                 edge_face_map->entries[i].v2 = new_v2;
 492                 edge_face_map->entries[i].face = face;
 493                 list_add_head(&edge_face_map->lists[new_v1], &edge_face_map->entries[i].entry);
 494             }
 495         }
 496     }
 497
 498     return D3D_OK;
 499 }
 500
 501 static DWORD find_adjacent_face(struct edge_face_map *edge_face_map, DWORD vertex1, DWORD vertex2, CONST DWORD num_faces)
 502 {
 503     struct edge_face *edge_face_ptr;
 504
 505     LIST_FOR_EACH_ENTRY(edge_face_ptr, &edge_face_map->lists[vertex2], struct edge_face, entry)
 506     {
 507         if (edge_face_ptr->v2 == vertex1)
 508             return edge_face_ptr->face;
 509     }
 510
 511     return -1;
 512 }
 513
 514 static DWORD *generate_identity_point_reps(DWORD num_vertices)
 515 {
 516         DWORD *id_point_reps;
 517         DWORD i;
 518
 519         id_point_reps = HeapAlloc(GetProcessHeap(), 0, num_vertices * sizeof(*id_point_reps));
 520         if (!id_point_reps)
 521             return NULL;
 522
 523         for (i = 0; i < num_vertices; i++)
 524         {
 525             id_point_reps[i] = i;
 526         }
 527
 528         return id_point_reps;
 529 }
 530
 531 static HRESULT WINAPI ID3DXMeshImpl_ConvertPointRepsToAdjacency(ID3DXMesh *iface, CONST DWORD *point_reps, DWORD *adjacency)
 532 {
 533     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 534     HRESULT hr;
 535     DWORD num_faces = iface->lpVtbl->GetNumFaces(iface);
 536     DWORD num_vertices = iface->lpVtbl->GetNumVertices(iface);
 537     DWORD options = iface->lpVtbl->GetOptions(iface);
 538     BOOL indices_are_16_bit = !(options & D3DXMESH_32BIT);
 539     DWORD *ib = NULL;
 540     void *ib_ptr = NULL;
 541     DWORD face;
 542     DWORD edge;
 543     struct edge_face_map edge_face_map = {0};
 544     CONST DWORD *point_reps_ptr = NULL;
 545     DWORD *id_point_reps = NULL;
 546
 547     TRACE("(%p)->(%p,%p)\n", This, point_reps, adjacency);
 548
 549     if (!adjacency) return D3DERR_INVALIDCALL;
 550
 551     if (!point_reps) /* Identity point reps */
 552     {
 553         id_point_reps = generate_identity_point_reps(num_vertices);
 554         if (!id_point_reps)
 555         {
 556             hr = E_OUTOFMEMORY;
 557             goto cleanup;
 558         }
 559
 560         point_reps_ptr = id_point_reps;
 561     }
 562     else
 563     {
 564         point_reps_ptr = point_reps;
 565     }
 566
 567     hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, &ib_ptr);
 568     if (FAILED(hr)) goto cleanup;
 569
 570     if (indices_are_16_bit)
 571     {
 572         /* Widen 16 bit to 32 bit */
 573         DWORD i;
 574         WORD *ib_16bit = ib_ptr;
 575         ib = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(DWORD));
 576         if (!ib)
 577         {
 578             hr = E_OUTOFMEMORY;
 579             goto cleanup;
 580         }
 581         for (i = 0; i < 3 * num_faces; i++)
 582         {
 583             ib[i] = ib_16bit[i];
 584         }
 585     }
 586     else
 587     {
 588         ib = ib_ptr;
 589     }
 590
 591     hr = init_edge_face_map(&edge_face_map, ib, point_reps_ptr, num_faces);
 592     if (FAILED(hr)) goto cleanup;
 593
 594     /* Create adjacency */
 595     for (face = 0; face < num_faces; face++)
 596     {
 597         for (edge = 0; edge < 3; edge++)
 598         {
 599             DWORD v1 = ib[3*face + edge];
 600             DWORD v2 = ib[3*face + (edge+1)%3];
 601             DWORD new_v1 = point_reps_ptr[v1];
 602             DWORD new_v2 = point_reps_ptr[v2];
 603             DWORD adj_face;
 604
 605             adj_face = find_adjacent_face(&edge_face_map, new_v1, new_v2, num_faces);
 606             adjacency[3*face + edge] = adj_face;
 607         }
 608     }
 609
 610     hr = D3D_OK;
 611 cleanup:
 612     HeapFree(GetProcessHeap(), 0, id_point_reps);
 613     if (indices_are_16_bit) HeapFree(GetProcessHeap(), 0, ib);
 614     HeapFree(GetProcessHeap(), 0, edge_face_map.lists);
 615     HeapFree(GetProcessHeap(), 0, edge_face_map.entries);
 616     if(ib_ptr) iface->lpVtbl->UnlockIndexBuffer(iface);
 617     return hr;
 618 }
 619
 620 /* ConvertAdjacencyToPointReps helper function.
 621  *
 622  * Goes around the edges of each face and replaces the vertices in any adjacent
 623  * face's edge with its own vertices(if its vertices have a lower index). This
 624  * way as few as possible low index vertices are shared among the faces. The
 625  * re-ordered index buffer is stored in new_indices.
 626  *
 627  * The vertices in a point representation must be ordered sequentially, e.g.
 628  * index 5 holds the index of the vertex that replaces vertex 5, i.e. if
 629  * vertex 5 is replaced by vertex 3 then index 5 would contain 3. If no vertex
 630  * replaces it, then it contains the same number as the index itself, e.g.
 631  * index 5 would contain 5. */
 632 static HRESULT propagate_face_vertices(CONST DWORD *adjacency, DWORD *point_reps,
 633                                     CONST DWORD *indices, DWORD *new_indices,
 634                                     CONST DWORD face, CONST DWORD numfaces)
 635 {
 636     const unsigned int VERTS_PER_FACE = 3;
 637     DWORD edge, opp_edge;
 638     DWORD face_base = VERTS_PER_FACE * face;
 639
 640     for (edge = 0; edge < VERTS_PER_FACE; edge++)
 641     {
 642         DWORD adj_face = adjacency[face_base + edge];
 643         DWORD adj_face_base;
 644         DWORD i;
 645         if (adj_face == -1) /* No adjacent face. */
 646             continue;
 647         else if (adj_face >= numfaces)
 648         {
 649             /* This throws exception on Windows */
 650             WARN("Index out of bounds. Got %d expected less than %d.\n",
 651                 adj_face, numfaces);
 652             return D3DERR_INVALIDCALL;
 653         }
 654         adj_face_base = 3 * adj_face;
 655
 656         /* Find opposite edge in adjacent face. */
 657         for (opp_edge = 0; opp_edge < VERTS_PER_FACE; opp_edge++)
 658         {
 659             DWORD opp_edge_index = adj_face_base + opp_edge;
 660             if (adjacency[opp_edge_index] == face)
 661                 break; /* Found opposite edge. */
 662         }
 663
 664         /* Replaces vertices in opposite edge with vertices from current edge. */
 665         for (i = 0; i < 2; i++)
 666         {
 667             DWORD from = face_base + (edge + (1 - i)) % VERTS_PER_FACE;
 668             DWORD to = adj_face_base + (opp_edge + i) % VERTS_PER_FACE;
 669
 670             /* Propagate lowest index. */
 671             if (new_indices[to] > new_indices[from])
 672             {
 673                 new_indices[to] = new_indices[from];
 674                 point_reps[indices[to]] = new_indices[from];
 675             }
 676         }
 677     }
 678
 679     return D3D_OK;
 680 }
 681
 682 static HRESULT WINAPI ID3DXMeshImpl_ConvertAdjacencyToPointReps(ID3DXMesh *iface, CONST DWORD *adjacency, DWORD *point_reps)
 683 {
 684     HRESULT hr;
 685     DWORD face;
 686     DWORD i;
 687     DWORD *indices = NULL;
 688     WORD *indices_16bit = NULL;
 689     DWORD *new_indices = NULL;
 690     const unsigned int VERTS_PER_FACE = 3;
 691
 692     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 693
 694     TRACE("(%p)->(%p,%p)\n", This, adjacency, point_reps);
 695
 696     if (!adjacency)
 697     {
 698         WARN("NULL adjacency.\n");
 699         hr = D3DERR_INVALIDCALL;
 700         goto cleanup;
 701     }
 702
 703     if (!point_reps)
 704     {
 705         WARN("NULL point_reps.\n");
 706         hr = D3DERR_INVALIDCALL;
 707         goto cleanup;
 708     }
 709
 710     /* Should never happen as CreateMesh does not allow meshes with 0 faces */
 711     if (This->numfaces == 0)
 712     {
 713         ERR("Number of faces was zero.\n");
 714         hr = D3DERR_INVALIDCALL;
 715         goto cleanup;
 716     }
 717
 718     new_indices = HeapAlloc(GetProcessHeap(), 0, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
 719     if (!new_indices)
 720     {
 721         hr = E_OUTOFMEMORY;
 722         goto cleanup;
 723     }
 724
 725     if (This->options & D3DXMESH_32BIT)
 726     {
 727         hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices);
 728         if (FAILED(hr)) goto cleanup;
 729         memcpy(new_indices, indices, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
 730     }
 731     else
 732     {
 733         /* Make a widening copy of indices_16bit into indices and new_indices
 734          * in order to re-use the helper function */
 735         hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices_16bit);
 736         if (FAILED(hr)) goto cleanup;
 737         indices = HeapAlloc(GetProcessHeap(), 0, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
 738         if (!indices)
 739         {
 740             hr = E_OUTOFMEMORY;
 741             goto cleanup;
 742         }
 743         for (i = 0; i < VERTS_PER_FACE * This->numfaces; i++)
 744         {
 745             new_indices[i] = indices_16bit[i];
 746             indices[i] = indices_16bit[i];
 747         }
 748     }
 749
 750     /* Vertices are ordered sequentially in the point representation. */
 751     for (i = 0; i < This->numvertices; i++)
 752     {
 753         point_reps[i] = i;
 754     }
 755
 756     /* Propagate vertices with low indices so as few vertices as possible
 757      * are used in the mesh.
 758      */
 759     for (face = 0; face < This->numfaces; face++)
 760     {
 761         hr = propagate_face_vertices(adjacency, point_reps, indices, new_indices, face, This->numfaces);
 762         if (FAILED(hr)) goto cleanup;
 763     }
 764     /* Go in opposite direction to catch all face orderings */
 765     for (face = 0; face < This->numfaces; face++)
 766     {
 767         hr = propagate_face_vertices(adjacency, point_reps,
 768                                      indices, new_indices,
 769                                      (This->numfaces - 1) - face, This->numfaces);
 770         if (FAILED(hr)) goto cleanup;
 771     }
 772
 773     hr = D3D_OK;
 774 cleanup:
 775     if (This->options & D3DXMESH_32BIT)
 776     {
 777         if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
 778     }
 779     else
 780     {
 781         if (indices_16bit) iface->lpVtbl->UnlockIndexBuffer(iface);
 782         HeapFree(GetProcessHeap(), 0, indices);
 783     }
 784     HeapFree(GetProcessHeap(), 0, new_indices);
 785     return hr;
 786 }
 787
 788 struct vertex_metadata {
 789   float key;
 790   DWORD vertex_index;
 791   DWORD first_shared_index;
 792 };
 793
 794 static int compare_vertex_keys(const void *a, const void *b)
 795 {
 796     const struct vertex_metadata *left = a;
 797     const struct vertex_metadata *right = b;
 798     if (left->key == right->key)
 799         return 0;
 800     return left->key < right->key ? -1 : 1;
 801 }
 802
 803 static HRESULT WINAPI ID3DXMeshImpl_GenerateAdjacency(ID3DXMesh *iface, FLOAT epsilon, DWORD *adjacency)
 804 {
 805     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 806     HRESULT hr;
 807     BYTE *vertices = NULL;
 808     const DWORD *indices = NULL;
 809     DWORD vertex_size;
 810     DWORD buffer_size;
 811     /* sort the vertices by (x + y + z) to quickly find coincident vertices */
 812     struct vertex_metadata *sorted_vertices;
 813     /* shared_indices links together identical indices in the index buffer so
 814      * that adjacency checks can be limited to faces sharing a vertex */
 815     DWORD *shared_indices = NULL;
 816     const FLOAT epsilon_sq = epsilon * epsilon;
 817     int i;
 818
 819     TRACE("(%p)->(%f,%p)\n", This, epsilon, adjacency);
 820
 821     if (!adjacency)
 822         return D3DERR_INVALIDCALL;
 823
 824     buffer_size = This->numfaces * 3 * sizeof(*shared_indices) + This->numvertices * sizeof(*sorted_vertices);
 825     if (!(This->options & D3DXMESH_32BIT))
 826         buffer_size += This->numfaces * 3 * sizeof(*indices);
 827     shared_indices = HeapAlloc(GetProcessHeap(), 0, buffer_size);
 828     if (!shared_indices)
 829         return E_OUTOFMEMORY;
 830     sorted_vertices = (struct vertex_metadata*)(shared_indices + This->numfaces * 3);
 831
 832     hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, (void**)&vertices);
 833     if (FAILED(hr)) goto cleanup;
 834     hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices);
 835     if (FAILED(hr)) goto cleanup;
 836
 837     if (!(This->options & D3DXMESH_32BIT)) {
 838         const WORD *word_indices = (const WORD*)indices;
 839         DWORD *dword_indices = (DWORD*)(sorted_vertices + This->numvertices);
 840         indices = dword_indices;
 841         for (i = 0; i < This->numfaces * 3; i++)
 842             *dword_indices++ = *word_indices++;
 843     }
 844
 845     vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 846     for (i = 0; i < This->numvertices; i++) {
 847         D3DXVECTOR3 *vertex = (D3DXVECTOR3*)(vertices + vertex_size * i);
 848         sorted_vertices[i].first_shared_index = -1;
 849         sorted_vertices[i].key = vertex->x + vertex->y + vertex->z;
 850         sorted_vertices[i].vertex_index = i;
 851     }
 852     for (i = 0; i < This->numfaces * 3; i++) {
 853         DWORD *first_shared_index = &sorted_vertices[indices[i]].first_shared_index;
 854         shared_indices[i] = *first_shared_index;
 855         *first_shared_index = i;
 856         adjacency[i] = -1;
 857     }
 858     qsort(sorted_vertices, This->numvertices, sizeof(*sorted_vertices), compare_vertex_keys);
 859
 860     for (i = 0; i < This->numvertices; i++) {
 861         struct vertex_metadata *sorted_vertex_a = &sorted_vertices[i];
 862         D3DXVECTOR3 *vertex_a = (D3DXVECTOR3*)(vertices + sorted_vertex_a->vertex_index * vertex_size);
 863         DWORD shared_index_a = sorted_vertex_a->first_shared_index;
 864
 865         while (shared_index_a != -1) {
 866             int j = i;
 867             DWORD shared_index_b = shared_indices[shared_index_a];
 868             struct vertex_metadata *sorted_vertex_b = sorted_vertex_a;
 869
 870             while (TRUE) {
 871                 while (shared_index_b != -1) {
 872                     /* faces are adjacent if they have another coincident vertex */
 873                     DWORD base_a = (shared_index_a / 3) * 3;
 874                     DWORD base_b = (shared_index_b / 3) * 3;
 875                     BOOL adjacent = FALSE;
 876                     int k;
 877
 878                     for (k = 0; k < 3; k++) {
 879                         if (adjacency[base_b + k] == shared_index_a / 3) {
 880                             adjacent = TRUE;
 881                             break;
 882                         }
 883                     }
 884                     if (!adjacent) {
 885                         for (k = 1; k <= 2; k++) {
 886                             DWORD vertex_index_a = base_a + (shared_index_a + k) % 3;
 887                             DWORD vertex_index_b = base_b + (shared_index_b + (3 - k)) % 3;
 888                             adjacent = indices[vertex_index_a] == indices[vertex_index_b];
 889                             if (!adjacent && epsilon >= 0.0f) {
 890                                 D3DXVECTOR3 delta = {0.0f, 0.0f, 0.0f};
 891                                 FLOAT length_sq;
 892
 893                                 D3DXVec3Subtract(&delta,
 894                                                  (D3DXVECTOR3*)(vertices + indices[vertex_index_a] * vertex_size),
 895                                                  (D3DXVECTOR3*)(vertices + indices[vertex_index_b] * vertex_size));
 896                                 length_sq = D3DXVec3LengthSq(&delta);
 897                                 adjacent = epsilon == 0.0f ? length_sq == 0.0f : length_sq < epsilon_sq;
 898                             }
 899                             if (adjacent) {
 900                                 DWORD adj_a = base_a + 2 - (vertex_index_a + shared_index_a + 1) % 3;
 901                                 DWORD adj_b = base_b + 2 - (vertex_index_b + shared_index_b + 1) % 3;
 902                                 if (adjacency[adj_a] == -1 && adjacency[adj_b] == -1) {
 903                                     adjacency[adj_a] = base_b / 3;
 904                                     adjacency[adj_b] = base_a / 3;
 905                                     break;
 906                                 }
 907                             }
 908                         }
 909                     }
 910
 911                     shared_index_b = shared_indices[shared_index_b];
 912                 }
 913                 while (++j < This->numvertices) {
 914                     D3DXVECTOR3 *vertex_b;
 915
 916                     sorted_vertex_b++;
 917                     if (sorted_vertex_b->key - sorted_vertex_a->key > epsilon * 3.0f) {
 918                         /* no more coincident vertices to try */
 919                         j = This->numvertices;
 920                         break;
 921                     }
 922                     /* check for coincidence */
 923                     vertex_b = (D3DXVECTOR3*)(vertices + sorted_vertex_b->vertex_index * vertex_size);
 924                     if (fabsf(vertex_a->x - vertex_b->x) <= epsilon &&
 925                         fabsf(vertex_a->y - vertex_b->y) <= epsilon &&
 926                         fabsf(vertex_a->z - vertex_b->z) <= epsilon)
 927                     {
 928                         break;
 929                     }
 930                 }
 931                 if (j >= This->numvertices)
 932                     break;
 933                 shared_index_b = sorted_vertex_b->first_shared_index;
 934             }
 935
 936             sorted_vertex_a->first_shared_index = shared_indices[sorted_vertex_a->first_shared_index];
 937             shared_index_a = sorted_vertex_a->first_shared_index;
 938         }
 939     }
 940
 941     hr = D3D_OK;
 942 cleanup:
 943     if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
 944     if (vertices) iface->lpVtbl->UnlockVertexBuffer(iface);
 945     HeapFree(GetProcessHeap(), 0, shared_indices);
 946     return hr;
 947 }
 948
 949 static HRESULT WINAPI ID3DXMeshImpl_UpdateSemantics(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 950 {
 951     HRESULT hr;
 952     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 953     UINT vertex_declaration_size;
 954     int i;
 955
 956     TRACE("(%p)->(%p)\n", This, declaration);
 957
 958     if (!declaration)
 959     {
 960         WARN("Invalid declaration. Can't use NULL declaration.\n");
 961         return D3DERR_INVALIDCALL;
 962     }
 963
 964     /* New declaration must be same size as original */
 965     vertex_declaration_size = D3DXGetDeclVertexSize(declaration, declaration[0].Stream);
 966     if (vertex_declaration_size != This->vertex_declaration_size)
 967     {
 968         WARN("Invalid declaration. New vertex size does not match the original vertex size.\n");
 969         return D3DERR_INVALIDCALL;
 970     }
 971
 972     /* New declaration must not contain non-zero Stream value  */
 973     for (i = 0; declaration[i].Stream != 0xff; i++)
 974     {
 975         if (declaration[i].Stream != 0)
 976         {
 977             WARN("Invalid declaration. New declaration contains non-zero Stream value.\n");
 978             return D3DERR_INVALIDCALL;
 979         }
 980     }
 981
 982     This->num_elem = i + 1;
 983     copy_declaration(This->cached_declaration, declaration, This->num_elem);
 984
 985     if (This->vertex_declaration)
 986         IDirect3DVertexDeclaration9_Release(This->vertex_declaration);
 987
 988     /* An application can pass an invalid declaration to UpdateSemantics and
 989      * still expect D3D_OK (see tests). If the declaration is invalid, then
 990      * subsequent calls to DrawSubset will fail. This is handled by setting the
 991      * vertex declaration to NULL.
 992      *     GetDeclaration, GetNumBytesPerVertex must, however, use the new
 993      * invalid declaration. This is handled by them using the cached vertex
 994      * declaration instead of the actual vertex declaration.
 995      */
 996     hr = IDirect3DDevice9_CreateVertexDeclaration(This->device,
 997                                                   declaration,
 998                                                   &This->vertex_declaration);
 999     if (FAILED(hr))
1000     {
1001         WARN("Using invalid declaration. Calls to DrawSubset will fail.\n");
1002         This->vertex_declaration = NULL;
1003     }
1004
1005     return D3D_OK;
1006 }
1007
1008 /*** ID3DXMesh ***/
1009 static HRESULT WINAPI ID3DXMeshImpl_LockAttributeBuffer(ID3DXMesh *iface, DWORD flags, DWORD **data)
1010 {
1011     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1012
1013     TRACE("(%p)->(%u,%p)\n", This, flags, data);
1014
1015     InterlockedIncrement(&This->attrib_buffer_lock_count);
1016
1017     if (!(flags & D3DLOCK_READONLY)) {
1018         D3DXATTRIBUTERANGE *attrib_table = This->attrib_table;
1019         This->attrib_table_size = 0;
1020         This->attrib_table = NULL;
1021         HeapFree(GetProcessHeap(), 0, attrib_table);
1022     }
1023
1024     *data = This->attrib_buffer;
1025
1026     return D3D_OK;
1027 }
1028
1029 static HRESULT WINAPI ID3DXMeshImpl_UnlockAttributeBuffer(ID3DXMesh *iface)
1030 {
1031     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1032     int lock_count;
1033
1034     TRACE("(%p)\n", This);
1035
1036     lock_count = InterlockedDecrement(&This->attrib_buffer_lock_count);
1037
1038     if (lock_count < 0) {
1039         InterlockedIncrement(&This->attrib_buffer_lock_count);
1040         return D3DERR_INVALIDCALL;
1041     }
1042
1043     return D3D_OK;
1044 }
1045
1046 static HRESULT WINAPI ID3DXMeshImpl_Optimize(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
1047                                              DWORD *face_remap, LPD3DXBUFFER *vertex_remap, LPD3DXMESH *opt_mesh)
1048 {
1049     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1050     HRESULT hr;
1051     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
1052     ID3DXMesh *optimized_mesh;
1053
1054     TRACE("(%p)->(%x,%p,%p,%p,%p,%p)\n", This, flags, adjacency_in, adjacency_out, face_remap, vertex_remap, opt_mesh);
1055
1056     if (!opt_mesh)
1057         return D3DERR_INVALIDCALL;
1058
1059     hr = iface->lpVtbl->GetDeclaration(iface, declaration);
1060     if (FAILED(hr)) return hr;
1061
1062     hr = iface->lpVtbl->CloneMesh(iface, This->options, declaration, This->device, &optimized_mesh);
1063     if (FAILED(hr)) return hr;
1064
1065     hr = optimized_mesh->lpVtbl->OptimizeInplace(optimized_mesh, flags, adjacency_in, adjacency_out, face_remap, vertex_remap);
1066     if (SUCCEEDED(hr))
1067         *opt_mesh = optimized_mesh;
1068     else
1069         IUnknown_Release(optimized_mesh);
1070     return hr;
1071 }
1072
1073 /* Creates a vertex_remap that removes unused vertices.
1074  * Indices are updated according to the vertex_remap. */
1075 static HRESULT compact_mesh(ID3DXMeshImpl *This, DWORD *indices, DWORD *new_num_vertices, ID3DXBuffer **vertex_remap)
1076 {
1077     HRESULT hr;
1078     DWORD *vertex_remap_ptr;
1079     DWORD num_used_vertices;
1080     DWORD i;
1081
1082     hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), vertex_remap);
1083     if (FAILED(hr)) return hr;
1084     vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(*vertex_remap);
1085
1086     for (i = 0; i < This->numfaces * 3; i++)
1087         vertex_remap_ptr[indices[i]] = 1;
1088
1089     /* create old->new vertex mapping */
1090     num_used_vertices = 0;
1091     for (i = 0; i < This->numvertices; i++) {
1092         if (vertex_remap_ptr[i])
1093             vertex_remap_ptr[i] = num_used_vertices++;
1094         else
1095             vertex_remap_ptr[i] = -1;
1096     }
1097     /* convert indices */
1098     for (i = 0; i < This->numfaces * 3; i++)
1099         indices[i] = vertex_remap_ptr[indices[i]];
1100
1101     /* create new->old vertex mapping */
1102     num_used_vertices = 0;
1103     for (i = 0; i < This->numvertices; i++) {
1104         if (vertex_remap_ptr[i] != -1)
1105             vertex_remap_ptr[num_used_vertices++] = i;
1106     }
1107     for (i = num_used_vertices; i < This->numvertices; i++)
1108         vertex_remap_ptr[i] = -1;
1109
1110     *new_num_vertices = num_used_vertices;
1111
1112     return D3D_OK;
1113 }
1114
1115 /* count the number of unique attribute values in a sorted attribute buffer */
1116 static DWORD count_attributes(const DWORD *attrib_buffer, DWORD numfaces)
1117 {
1118     DWORD last_attribute = attrib_buffer[0];
1119     DWORD attrib_table_size = 1;
1120     DWORD i;
1121     for (i = 1; i < numfaces; i++) {
1122         if (attrib_buffer[i] != last_attribute) {
1123             last_attribute = attrib_buffer[i];
1124             attrib_table_size++;
1125         }
1126     }
1127     return attrib_table_size;
1128 }
1129
1130 static void fill_attribute_table(DWORD *attrib_buffer, DWORD numfaces, void *indices,
1131                                  BOOL is_32bit_indices, D3DXATTRIBUTERANGE *attrib_table)
1132 {
1133     DWORD attrib_table_size = 0;
1134     DWORD last_attribute = attrib_buffer[0];
1135     DWORD min_vertex, max_vertex;
1136     DWORD i;
1137
1138     attrib_table[0].AttribId = last_attribute;
1139     attrib_table[0].FaceStart = 0;
1140     min_vertex = (DWORD)-1;
1141     max_vertex = 0;
1142     for (i = 0; i < numfaces; i++) {
1143         DWORD j;
1144
1145         if (attrib_buffer[i] != last_attribute) {
1146             last_attribute = attrib_buffer[i];
1147             attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
1148             attrib_table[attrib_table_size].VertexStart = min_vertex;
1149             attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
1150             attrib_table_size++;
1151             attrib_table[attrib_table_size].AttribId = attrib_buffer[i];
1152             attrib_table[attrib_table_size].FaceStart = i;
1153             min_vertex = (DWORD)-1;
1154             max_vertex = 0;
1155         }
1156         for (j = 0; j < 3; j++) {
1157             DWORD vertex_index = is_32bit_indices ? ((DWORD*)indices)[i * 3 + j] : ((WORD*)indices)[i * 3 + j];
1158             if (vertex_index < min_vertex)
1159                 min_vertex = vertex_index;
1160             if (vertex_index > max_vertex)
1161                 max_vertex = vertex_index;
1162         }
1163     }
1164     attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
1165     attrib_table[attrib_table_size].VertexStart = min_vertex;
1166     attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
1167     attrib_table_size++;
1168 }
1169
1170 static int attrib_entry_compare(const DWORD **a, const DWORD **b)
1171 {
1172     const DWORD *ptr_a = *a;
1173     const DWORD *ptr_b = *b;
1174     int delta = *ptr_a - *ptr_b;
1175
1176     if (delta)
1177         return delta;
1178
1179     delta = ptr_a - ptr_b; /* for stable sort */
1180     return delta;
1181 }
1182
1183 /* Create face_remap, a new attribute buffer for attribute sort optimization. */
1184 static HRESULT remap_faces_for_attrsort(ID3DXMeshImpl *This, const DWORD *indices,
1185         const DWORD *attrib_buffer, DWORD **sorted_attrib_buffer, DWORD **face_remap)
1186 {
1187     const DWORD **sorted_attrib_ptr_buffer = NULL;
1188     DWORD i;
1189
1190     *face_remap = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(**face_remap));
1191     sorted_attrib_ptr_buffer = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(*sorted_attrib_ptr_buffer));
1192     if (!*face_remap || !sorted_attrib_ptr_buffer) {
1193         HeapFree(GetProcessHeap(), 0, sorted_attrib_ptr_buffer);
1194         return E_OUTOFMEMORY;
1195     }
1196     for (i = 0; i < This->numfaces; i++)
1197         sorted_attrib_ptr_buffer[i] = &attrib_buffer[i];
1198     qsort(sorted_attrib_ptr_buffer, This->numfaces, sizeof(*sorted_attrib_ptr_buffer),
1199          (int(*)(const void *, const void *))attrib_entry_compare);
1200
1201     for (i = 0; i < This->numfaces; i++)
1202     {
1203         DWORD old_face = sorted_attrib_ptr_buffer[i] - attrib_buffer;
1204         (*face_remap)[old_face] = i;
1205     }
1206
1207     /* overwrite sorted_attrib_ptr_buffer with the values themselves */
1208     *sorted_attrib_buffer = (DWORD*)sorted_attrib_ptr_buffer;
1209     for (i = 0; i < This->numfaces; i++)
1210         (*sorted_attrib_buffer)[(*face_remap)[i]] = attrib_buffer[i];
1211
1212     return D3D_OK;
1213 }
1214
1215 static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
1216                                                     DWORD *face_remap_out, LPD3DXBUFFER *vertex_remap_out)
1217 {
1218     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1219     void *indices = NULL;
1220     DWORD *attrib_buffer = NULL;
1221     HRESULT hr;
1222     ID3DXBuffer *vertex_remap = NULL;
1223     DWORD *face_remap = NULL; /* old -> new mapping */
1224     DWORD *dword_indices = NULL;
1225     DWORD new_num_vertices = 0;
1226     DWORD new_num_alloc_vertices = 0;
1227     IDirect3DVertexBuffer9 *vertex_buffer = NULL;
1228     DWORD *sorted_attrib_buffer = NULL;
1229     DWORD i;
1230
1231     TRACE("(%p)->(%x,%p,%p,%p,%p)\n", This, flags, adjacency_in, adjacency_out, face_remap_out, vertex_remap_out);
1232
1233     if (!flags)
1234         return D3DERR_INVALIDCALL;
1235     if (!adjacency_in && (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)))
1236         return D3DERR_INVALIDCALL;
1237     if ((flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)) == (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
1238         return D3DERR_INVALIDCALL;
1239
1240     if (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
1241     {
1242         if (flags & D3DXMESHOPT_VERTEXCACHE)
1243             FIXME("D3DXMESHOPT_VERTEXCACHE not implemented.\n");
1244         if (flags & D3DXMESHOPT_STRIPREORDER)
1245             FIXME("D3DXMESHOPT_STRIPREORDER not implemented.\n");
1246         return E_NOTIMPL;
1247     }
1248
1249     hr = iface->lpVtbl->LockIndexBuffer(iface, 0, &indices);
1250     if (FAILED(hr)) goto cleanup;
1251
1252     dword_indices = HeapAlloc(GetProcessHeap(), 0, This->numfaces * 3 * sizeof(DWORD));
1253     if (!dword_indices) return E_OUTOFMEMORY;
1254     if (This->options & D3DXMESH_32BIT) {
1255         memcpy(dword_indices, indices, This->numfaces * 3 * sizeof(DWORD));
1256     } else {
1257         WORD *word_indices = indices;
1258         for (i = 0; i < This->numfaces * 3; i++)
1259             dword_indices[i] = *word_indices++;
1260     }
1261
1262     if ((flags & (D3DXMESHOPT_COMPACT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_ATTRSORT)) == D3DXMESHOPT_COMPACT)
1263     {
1264         new_num_alloc_vertices = This->numvertices;
1265         hr = compact_mesh(This, dword_indices, &new_num_vertices, &vertex_remap);
1266         if (FAILED(hr)) goto cleanup;
1267     } else if (flags & D3DXMESHOPT_ATTRSORT) {
1268         if (!(flags & D3DXMESHOPT_IGNOREVERTS))
1269         {
1270             FIXME("D3DXMESHOPT_ATTRSORT vertex reordering not implemented.\n");
1271             hr = E_NOTIMPL;
1272             goto cleanup;
1273         }
1274
1275         hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
1276         if (FAILED(hr)) goto cleanup;
1277
1278         hr = remap_faces_for_attrsort(This, dword_indices, attrib_buffer, &sorted_attrib_buffer, &face_remap);
1279         if (FAILED(hr)) goto cleanup;
1280     }
1281
1282     if (vertex_remap)
1283     {
1284         /* reorder the vertices using vertex_remap */
1285         D3DVERTEXBUFFER_DESC vertex_desc;
1286         DWORD *vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
1287         DWORD vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
1288         BYTE *orig_vertices;
1289         BYTE *new_vertices;
1290
1291         hr = IDirect3DVertexBuffer9_GetDesc(This->vertex_buffer, &vertex_desc);
1292         if (FAILED(hr)) goto cleanup;
1293
1294         hr = IDirect3DDevice9_CreateVertexBuffer(This->device, new_num_alloc_vertices * vertex_size,
1295                 vertex_desc.Usage, This->fvf, vertex_desc.Pool, &vertex_buffer, NULL);
1296         if (FAILED(hr)) goto cleanup;
1297
1298         hr = IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, (void**)&orig_vertices, D3DLOCK_READONLY);
1299         if (FAILED(hr)) goto cleanup;
1300
1301         hr = IDirect3DVertexBuffer9_Lock(vertex_buffer, 0, 0, (void**)&new_vertices, 0);
1302         if (FAILED(hr)) {
1303             IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
1304             goto cleanup;
1305         }
1306
1307         for (i = 0; i < new_num_vertices; i++)
1308             memcpy(new_vertices + i * vertex_size, orig_vertices + vertex_remap_ptr[i] * vertex_size, vertex_size);
1309
1310         IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
1311         IDirect3DVertexBuffer9_Unlock(vertex_buffer);
1312     } else if (vertex_remap_out) {
1313         DWORD *vertex_remap_ptr;
1314
1315         hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), &vertex_remap);
1316         if (FAILED(hr)) goto cleanup;
1317         vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
1318         for (i = 0; i < This->numvertices; i++)
1319             *vertex_remap_ptr++ = i;
1320     }
1321
1322     if (flags & D3DXMESHOPT_ATTRSORT)
1323     {
1324         D3DXATTRIBUTERANGE *attrib_table;
1325         DWORD attrib_table_size;
1326
1327         attrib_table_size = count_attributes(sorted_attrib_buffer, This->numfaces);
1328         attrib_table = HeapAlloc(GetProcessHeap(), 0, attrib_table_size * sizeof(*attrib_table));
1329         if (!attrib_table) {
1330             hr = E_OUTOFMEMORY;
1331             goto cleanup;
1332         }
1333
1334         memcpy(attrib_buffer, sorted_attrib_buffer, This->numfaces * sizeof(*attrib_buffer));
1335
1336         /* reorder the indices using face_remap */
1337         if (This->options & D3DXMESH_32BIT) {
1338             for (i = 0; i < This->numfaces; i++)
1339                 memcpy((DWORD*)indices + face_remap[i] * 3, dword_indices + i * 3, 3 * sizeof(DWORD));
1340         } else {
1341             WORD *word_indices = indices;
1342             for (i = 0; i < This->numfaces; i++) {
1343                 DWORD new_pos = face_remap[i] * 3;
1344                 DWORD old_pos = i * 3;
1345                 word_indices[new_pos++] = dword_indices[old_pos++];
1346                 word_indices[new_pos++] = dword_indices[old_pos++];
1347                 word_indices[new_pos] = dword_indices[old_pos];
1348             }
1349         }
1350
1351         fill_attribute_table(attrib_buffer, This->numfaces, indices,
1352                              This->options & D3DXMESH_32BIT, attrib_table);
1353
1354         HeapFree(GetProcessHeap(), 0, This->attrib_table);
1355         This->attrib_table = attrib_table;
1356         This->attrib_table_size = attrib_table_size;
1357     } else {
1358         if (This->options & D3DXMESH_32BIT) {
1359             memcpy(indices, dword_indices, This->numfaces * 3 * sizeof(DWORD));
1360         } else {
1361             WORD *word_indices = indices;
1362             for (i = 0; i < This->numfaces * 3; i++)
1363                 *word_indices++ = dword_indices[i];
1364         }
1365     }
1366
1367     if (adjacency_out) {
1368         if (face_remap) {
1369             for (i = 0; i < This->numfaces; i++) {
1370                 DWORD old_pos = i * 3;
1371                 DWORD new_pos = face_remap[i] * 3;
1372                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
1373                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
1374                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
1375             }
1376         } else {
1377             memcpy(adjacency_out, adjacency_in, This->numfaces * 3 * sizeof(*adjacency_out));
1378         }
1379     }
1380     if (face_remap_out) {
1381         if (face_remap) {
1382             for (i = 0; i < This->numfaces; i++)
1383                 face_remap_out[face_remap[i]] = i;
1384         } else {
1385             for (i = 0; i < This->numfaces; i++)
1386                 face_remap_out[i] = i;
1387         }
1388     }
1389     if (vertex_remap_out)
1390         *vertex_remap_out = vertex_remap;
1391     vertex_remap = NULL;
1392
1393     if (vertex_buffer) {
1394         IDirect3DVertexBuffer9_Release(This->vertex_buffer);
1395         This->vertex_buffer = vertex_buffer;
1396         vertex_buffer = NULL;
1397         This->numvertices = new_num_vertices;
1398     }
1399
1400     hr = D3D_OK;
1401 cleanup:
1402     HeapFree(GetProcessHeap(), 0, sorted_attrib_buffer);
1403     HeapFree(GetProcessHeap(), 0, face_remap);
1404     HeapFree(GetProcessHeap(), 0, dword_indices);
1405     if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
1406     if (vertex_buffer) IDirect3DVertexBuffer9_Release(vertex_buffer);
1407     if (attrib_buffer) iface->lpVtbl->UnlockAttributeBuffer(iface);
1408     if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
1409     return hr;
1410 }
1411
1412 static HRESULT WINAPI ID3DXMeshImpl_SetAttributeTable(ID3DXMesh *iface, CONST D3DXATTRIBUTERANGE *attrib_table, DWORD attrib_table_size)
1413 {
1414     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1415     D3DXATTRIBUTERANGE *new_table = NULL;
1416
1417     TRACE("(%p)->(%p,%u)\n", This, attrib_table, attrib_table_size);
1418
1419     if (attrib_table_size) {
1420         size_t size = attrib_table_size * sizeof(*attrib_table);
1421
1422         new_table = HeapAlloc(GetProcessHeap(), 0, size);
1423         if (!new_table)
1424             return E_OUTOFMEMORY;
1425
1426         CopyMemory(new_table, attrib_table, size);
1427     } else if (attrib_table) {
1428         return D3DERR_INVALIDCALL;
1429     }
1430     HeapFree(GetProcessHeap(), 0, This->attrib_table);
1431     This->attrib_table = new_table;
1432     This->attrib_table_size = attrib_table_size;
1433
1434     return D3D_OK;
1435 }
1436
1437 static const struct ID3DXMeshVtbl D3DXMesh_Vtbl =
1438 {
1439     /*** IUnknown methods ***/
1440     ID3DXMeshImpl_QueryInterface,
1441     ID3DXMeshImpl_AddRef,
1442     ID3DXMeshImpl_Release,
1443     /*** ID3DXBaseMesh ***/
1444     ID3DXMeshImpl_DrawSubset,
1445     ID3DXMeshImpl_GetNumFaces,
1446     ID3DXMeshImpl_GetNumVertices,
1447     ID3DXMeshImpl_GetFVF,
1448     ID3DXMeshImpl_GetDeclaration,
1449     ID3DXMeshImpl_GetNumBytesPerVertex,
1450     ID3DXMeshImpl_GetOptions,
1451     ID3DXMeshImpl_GetDevice,
1452     ID3DXMeshImpl_CloneMeshFVF,
1453     ID3DXMeshImpl_CloneMesh,
1454     ID3DXMeshImpl_GetVertexBuffer,
1455     ID3DXMeshImpl_GetIndexBuffer,
1456     ID3DXMeshImpl_LockVertexBuffer,
1457     ID3DXMeshImpl_UnlockVertexBuffer,
1458     ID3DXMeshImpl_LockIndexBuffer,
1459     ID3DXMeshImpl_UnlockIndexBuffer,
1460     ID3DXMeshImpl_GetAttributeTable,
1461     ID3DXMeshImpl_ConvertPointRepsToAdjacency,
1462     ID3DXMeshImpl_ConvertAdjacencyToPointReps,
1463     ID3DXMeshImpl_GenerateAdjacency,
1464     ID3DXMeshImpl_UpdateSemantics,
1465     /*** ID3DXMesh ***/
1466     ID3DXMeshImpl_LockAttributeBuffer,
1467     ID3DXMeshImpl_UnlockAttributeBuffer,
1468     ID3DXMeshImpl_Optimize,
1469     ID3DXMeshImpl_OptimizeInplace,
1470     ID3DXMeshImpl_SetAttributeTable
1471 };
1472
1473 /*************************************************************************
1474  * D3DXBoxBoundProbe
1475  */
1476 BOOL WINAPI D3DXBoxBoundProbe(CONST D3DXVECTOR3 *pmin, CONST D3DXVECTOR3 *pmax, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
1477
1478 /* Algorithm taken from the article: An Efficient and Robust Ray-Box Intersection Algoritm
1479 Amy Williams             University of Utah
1480 Steve Barrus             University of Utah
1481 R. Keith Morley          University of Utah
1482 Peter Shirley            University of Utah
1483
1484 International Conference on Computer Graphics and Interactive Techniques  archive
1485 ACM SIGGRAPH 2005 Courses
1486 Los Angeles, California
1487
1488 This algorithm is free of patents or of copyrights, as confirmed by Peter Shirley himself.
1489
1490 Algorithm: Consider the box as the intersection of three slabs. Clip the ray
1491 against each slab, if there's anything left of the ray after we're
1492 done we've got an intersection of the ray with the box.
1493 */
1494
1495 {
1496     FLOAT div, tmin, tmax, tymin, tymax, tzmin, tzmax;
1497
1498     div = 1.0f / praydirection->x;
1499     if ( div >= 0.0f )
1500     {
1501         tmin = ( pmin->x - prayposition->x ) * div;
1502         tmax = ( pmax->x - prayposition->x ) * div;
1503     }
1504     else
1505     {
1506         tmin = ( pmax->x - prayposition->x ) * div;
1507         tmax = ( pmin->x - prayposition->x ) * div;
1508     }
1509
1510     if ( tmax < 0.0f ) return FALSE;
1511
1512     div = 1.0f / praydirection->y;
1513     if ( div >= 0.0f )
1514     {
1515         tymin = ( pmin->y - prayposition->y ) * div;
1516         tymax = ( pmax->y - prayposition->y ) * div;
1517     }
1518     else
1519     {
1520         tymin = ( pmax->y - prayposition->y ) * div;
1521         tymax = ( pmin->y - prayposition->y ) * div;
1522     }
1523
1524     if ( ( tymax < 0.0f ) || ( tmin > tymax ) || ( tymin > tmax ) ) return FALSE;
1525
1526     if ( tymin > tmin ) tmin = tymin;
1527     if ( tymax < tmax ) tmax = tymax;
1528
1529     div = 1.0f / praydirection->z;
1530     if ( div >= 0.0f )
1531     {
1532         tzmin = ( pmin->z - prayposition->z ) * div;
1533         tzmax = ( pmax->z - prayposition->z ) * div;
1534     }
1535     else
1536     {
1537         tzmin = ( pmax->z - prayposition->z ) * div;
1538         tzmax = ( pmin->z - prayposition->z ) * div;
1539     }
1540
1541     if ( (tzmax < 0.0f ) || ( tmin > tzmax ) || ( tzmin > tmax ) ) return FALSE;
1542
1543     return TRUE;
1544 }
1545
1546 /*************************************************************************
1547  * D3DXComputeBoundingBox
1548  */
1549 HRESULT WINAPI D3DXComputeBoundingBox(CONST D3DXVECTOR3 *pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pmin, D3DXVECTOR3 *pmax)
1550 {
1551     D3DXVECTOR3 vec;
1552     unsigned int i;
1553
1554     if( !pfirstposition || !pmin || !pmax ) return D3DERR_INVALIDCALL;
1555
1556     *pmin = *pfirstposition;
1557     *pmax = *pmin;
1558
1559     for(i=0; i<numvertices; i++)
1560     {
1561         vec = *( (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i) );
1562
1563         if ( vec.x < pmin->x ) pmin->x = vec.x;
1564         if ( vec.x > pmax->x ) pmax->x = vec.x;
1565
1566         if ( vec.y < pmin->y ) pmin->y = vec.y;
1567         if ( vec.y > pmax->y ) pmax->y = vec.y;
1568
1569         if ( vec.z < pmin->z ) pmin->z = vec.z;
1570         if ( vec.z > pmax->z ) pmax->z = vec.z;
1571     }
1572
1573     return D3D_OK;
1574 }
1575
1576 /*************************************************************************
1577  * D3DXComputeBoundingSphere
1578  */
1579 HRESULT WINAPI D3DXComputeBoundingSphere(CONST D3DXVECTOR3* pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pcenter, FLOAT *pradius)
1580 {
1581     D3DXVECTOR3 temp, temp1;
1582     FLOAT d;
1583     unsigned int i;
1584
1585     if( !pfirstposition || !pcenter || !pradius ) return D3DERR_INVALIDCALL;
1586
1587     temp.x = 0.0f;
1588     temp.y = 0.0f;
1589     temp.z = 0.0f;
1590     temp1 = temp;
1591     *pradius = 0.0f;
1592
1593     for(i=0; i<numvertices; i++)
1594     {
1595         D3DXVec3Add(&temp1, &temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i));
1596         temp = temp1;
1597     }
1598
1599     D3DXVec3Scale(pcenter, &temp, 1.0f/((FLOAT)numvertices));
1600
1601     for(i=0; i<numvertices; i++)
1602     {
1603         d = D3DXVec3Length(D3DXVec3Subtract(&temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i), pcenter));
1604         if ( d > *pradius ) *pradius = d;
1605     }
1606     return D3D_OK;
1607 }
1608
1609 static const UINT d3dx_decltype_size[D3DDECLTYPE_UNUSED] =
1610 {
1611    /* D3DDECLTYPE_FLOAT1    */ 1 * 4,
1612    /* D3DDECLTYPE_FLOAT2    */ 2 * 4,
1613    /* D3DDECLTYPE_FLOAT3    */ 3 * 4,
1614    /* D3DDECLTYPE_FLOAT4    */ 4 * 4,
1615    /* D3DDECLTYPE_D3DCOLOR  */ 4 * 1,
1616    /* D3DDECLTYPE_UBYTE4    */ 4 * 1,
1617    /* D3DDECLTYPE_SHORT2    */ 2 * 2,
1618    /* D3DDECLTYPE_SHORT4    */ 4 * 2,
1619    /* D3DDECLTYPE_UBYTE4N   */ 4 * 1,
1620    /* D3DDECLTYPE_SHORT2N   */ 2 * 2,
1621    /* D3DDECLTYPE_SHORT4N   */ 4 * 2,
1622    /* D3DDECLTYPE_USHORT2N  */ 2 * 2,
1623    /* D3DDECLTYPE_USHORT4N  */ 4 * 2,
1624    /* D3DDECLTYPE_UDEC3     */ 4, /* 3 * 10 bits + 2 padding */
1625    /* D3DDECLTYPE_DEC3N     */ 4,
1626    /* D3DDECLTYPE_FLOAT16_2 */ 2 * 2,
1627    /* D3DDECLTYPE_FLOAT16_4 */ 4 * 2,
1628 };
1629
1630 static void append_decl_element(D3DVERTEXELEMENT9 *declaration, UINT *idx, UINT *offset,
1631         D3DDECLTYPE type, D3DDECLUSAGE usage, UINT usage_idx)
1632 {
1633     declaration[*idx].Stream = 0;
1634     declaration[*idx].Offset = *offset;
1635     declaration[*idx].Type = type;
1636     declaration[*idx].Method = D3DDECLMETHOD_DEFAULT;
1637     declaration[*idx].Usage = usage;
1638     declaration[*idx].UsageIndex = usage_idx;
1639
1640     *offset += d3dx_decltype_size[type];
1641     ++(*idx);
1642 }
1643
1644 /*************************************************************************
1645  * D3DXDeclaratorFromFVF
1646  */
1647 HRESULT WINAPI D3DXDeclaratorFromFVF(DWORD fvf, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
1648 {
1649     static const D3DVERTEXELEMENT9 end_element = D3DDECL_END();
1650     DWORD tex_count = (fvf & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
1651     unsigned int offset = 0;
1652     unsigned int idx = 0;
1653     unsigned int i;
1654
1655     TRACE("fvf %#x, declaration %p.\n", fvf, declaration);
1656
1657     if (fvf & (D3DFVF_RESERVED0 | D3DFVF_RESERVED2)) return D3DERR_INVALIDCALL;
1658
1659     if (fvf & D3DFVF_POSITION_MASK)
1660     {
1661         BOOL has_blend = (fvf & D3DFVF_XYZB5) >= D3DFVF_XYZB1;
1662         DWORD blend_count = 1 + (((fvf & D3DFVF_XYZB5) - D3DFVF_XYZB1) >> 1);
1663         BOOL has_blend_idx = (fvf & D3DFVF_LASTBETA_D3DCOLOR) || (fvf & D3DFVF_LASTBETA_UBYTE4);
1664
1665         if (has_blend_idx) --blend_count;
1666
1667         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZW
1668                 || (has_blend && blend_count > 4))
1669             return D3DERR_INVALIDCALL;
1670
1671         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZRHW)
1672             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_POSITIONT, 0);
1673         else
1674             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_POSITION, 0);
1675
1676         if (has_blend)
1677         {
1678             switch (blend_count)
1679             {
1680                  case 0:
1681                     break;
1682                  case 1:
1683                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_BLENDWEIGHT, 0);
1684                     break;
1685                  case 2:
1686                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_BLENDWEIGHT, 0);
1687                     break;
1688                  case 3:
1689                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_BLENDWEIGHT, 0);
1690                     break;
1691                  case 4:
1692                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_BLENDWEIGHT, 0);
1693                     break;
1694                  default:
1695                      ERR("Invalid blend count %u.\n", blend_count);
1696                      break;
1697             }
1698
1699             if (has_blend_idx)
1700             {
1701                 if (fvf & D3DFVF_LASTBETA_UBYTE4)
1702                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_UBYTE4, D3DDECLUSAGE_BLENDINDICES, 0);
1703                 else if (fvf & D3DFVF_LASTBETA_D3DCOLOR)
1704                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_BLENDINDICES, 0);
1705             }
1706         }
1707     }
1708
1709     if (fvf & D3DFVF_NORMAL)
1710         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_NORMAL, 0);
1711     if (fvf & D3DFVF_PSIZE)
1712         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_PSIZE, 0);
1713     if (fvf & D3DFVF_DIFFUSE)
1714         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 0);
1715     if (fvf & D3DFVF_SPECULAR)
1716         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 1);
1717
1718     for (i = 0; i < tex_count; ++i)
1719     {
1720         switch ((fvf >> (16 + 2 * i)) & 0x03)
1721         {
1722             case D3DFVF_TEXTUREFORMAT1:
1723                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_TEXCOORD, i);
1724                 break;
1725             case D3DFVF_TEXTUREFORMAT2:
1726                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_TEXCOORD, i);
1727                 break;
1728             case D3DFVF_TEXTUREFORMAT3:
1729                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_TEXCOORD, i);
1730                 break;
1731             case D3DFVF_TEXTUREFORMAT4:
1732                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_TEXCOORD, i);
1733                 break;
1734         }
1735     }
1736
1737     declaration[idx] = end_element;
1738
1739     return D3D_OK;
1740 }
1741
1742 /*************************************************************************
1743  * D3DXFVFFromDeclarator
1744  */
1745 HRESULT WINAPI D3DXFVFFromDeclarator(const D3DVERTEXELEMENT9 *declaration, DWORD *fvf)
1746 {
1747     unsigned int i = 0, texture, offset;
1748
1749     TRACE("(%p, %p)\n", declaration, fvf);
1750
1751     *fvf = 0;
1752     if (declaration[0].Type == D3DDECLTYPE_FLOAT3 && declaration[0].Usage == D3DDECLUSAGE_POSITION)
1753     {
1754         if ((declaration[1].Type == D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
1755              declaration[1].UsageIndex == 0) &&
1756             (declaration[2].Type == D3DDECLTYPE_FLOAT1 && declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES &&
1757              declaration[2].UsageIndex == 0))
1758         {
1759             return D3DERR_INVALIDCALL;
1760         }
1761         else if ((declaration[1].Type == D3DDECLTYPE_UBYTE4 || declaration[1].Type == D3DDECLTYPE_D3DCOLOR) &&
1762                  declaration[1].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[1].UsageIndex == 0)
1763         {
1764             if (declaration[1].Type == D3DDECLTYPE_UBYTE4)
1765             {
1766                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_UBYTE4;
1767             }
1768             else
1769             {
1770                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_D3DCOLOR;
1771             }
1772             i = 2;
1773         }
1774         else if (declaration[1].Type <= D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
1775                  declaration[1].UsageIndex == 0)
1776         {
1777             if ((declaration[2].Type == D3DDECLTYPE_UBYTE4 || declaration[2].Type == D3DDECLTYPE_D3DCOLOR) &&
1778                 declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[2].UsageIndex == 0)
1779             {
1780                 if (declaration[2].Type == D3DDECLTYPE_UBYTE4)
1781                 {
1782                     *fvf |= D3DFVF_LASTBETA_UBYTE4;
1783                 }
1784                 else
1785                 {
1786                     *fvf |= D3DFVF_LASTBETA_D3DCOLOR;
1787                 }
1788                 switch (declaration[1].Type)
1789                 {
1790                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB2; break;
1791                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB3; break;
1792                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB4; break;
1793                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB5; break;
1794                 }
1795                 i = 3;
1796             }
1797             else
1798             {
1799                 switch (declaration[1].Type)
1800                 {
1801                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB1; break;
1802                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB2; break;
1803                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB3; break;
1804                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB4; break;
1805                 }
1806                 i = 2;
1807             }
1808         }
1809         else
1810         {
1811             *fvf |= D3DFVF_XYZ;
1812             i = 1;
1813         }
1814     }
1815     else if (declaration[0].Type == D3DDECLTYPE_FLOAT4 && declaration[0].Usage == D3DDECLUSAGE_POSITIONT &&
1816              declaration[0].UsageIndex == 0)
1817     {
1818         *fvf |= D3DFVF_XYZRHW;
1819         i = 1;
1820     }
1821
1822     if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_NORMAL)
1823     {
1824         *fvf |= D3DFVF_NORMAL;
1825         i++;
1826     }
1827     if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_PSIZE &&
1828         declaration[i].UsageIndex == 0)
1829     {
1830         *fvf |= D3DFVF_PSIZE;
1831         i++;
1832     }
1833     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
1834         declaration[i].UsageIndex == 0)
1835     {
1836         *fvf |= D3DFVF_DIFFUSE;
1837         i++;
1838     }
1839     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
1840         declaration[i].UsageIndex == 1)
1841     {
1842         *fvf |= D3DFVF_SPECULAR;
1843         i++;
1844     }
1845
1846     for (texture = 0; texture < D3DDP_MAXTEXCOORD; i++, texture++)
1847     {
1848         if (declaration[i].Stream == 0xFF)
1849         {
1850             break;
1851         }
1852         else if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1853                  declaration[i].UsageIndex == texture)
1854         {
1855             *fvf |= D3DFVF_TEXCOORDSIZE1(declaration[i].UsageIndex);
1856         }
1857         else if (declaration[i].Type == D3DDECLTYPE_FLOAT2 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1858                  declaration[i].UsageIndex == texture)
1859         {
1860             *fvf |= D3DFVF_TEXCOORDSIZE2(declaration[i].UsageIndex);
1861         }
1862         else if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1863                  declaration[i].UsageIndex == texture)
1864         {
1865             *fvf |= D3DFVF_TEXCOORDSIZE3(declaration[i].UsageIndex);
1866         }
1867         else if (declaration[i].Type == D3DDECLTYPE_FLOAT4 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1868                  declaration[i].UsageIndex == texture)
1869         {
1870             *fvf |= D3DFVF_TEXCOORDSIZE4(declaration[i].UsageIndex);
1871         }
1872         else
1873         {
1874             return D3DERR_INVALIDCALL;
1875         }
1876     }
1877
1878     *fvf |= (texture << D3DFVF_TEXCOUNT_SHIFT);
1879
1880     for (offset = 0, i = 0; declaration[i].Stream != 0xFF;
1881          offset += d3dx_decltype_size[declaration[i].Type], i++)
1882     {
1883         if (declaration[i].Offset != offset)
1884         {
1885             return D3DERR_INVALIDCALL;
1886         }
1887     }
1888
1889     return D3D_OK;
1890 }
1891
1892 /*************************************************************************
1893  * D3DXGetFVFVertexSize
1894  */
1895 static UINT Get_TexCoord_Size_From_FVF(DWORD FVF, int tex_num)
1896 {
1897     return (((((FVF) >> (16 + (2 * (tex_num)))) + 1) & 0x03) + 1);
1898 }
1899
1900 UINT WINAPI D3DXGetFVFVertexSize(DWORD FVF)
1901 {
1902     DWORD size = 0;
1903     UINT i;
1904     UINT numTextures = (FVF & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
1905
1906     if (FVF & D3DFVF_NORMAL) size += sizeof(D3DXVECTOR3);
1907     if (FVF & D3DFVF_DIFFUSE) size += sizeof(DWORD);
1908     if (FVF & D3DFVF_SPECULAR) size += sizeof(DWORD);
1909     if (FVF & D3DFVF_PSIZE) size += sizeof(DWORD);
1910
1911     switch (FVF & D3DFVF_POSITION_MASK)
1912     {
1913         case D3DFVF_XYZ:    size += sizeof(D3DXVECTOR3); break;
1914         case D3DFVF_XYZRHW: size += 4 * sizeof(FLOAT); break;
1915         case D3DFVF_XYZB1:  size += 4 * sizeof(FLOAT); break;
1916         case D3DFVF_XYZB2:  size += 5 * sizeof(FLOAT); break;
1917         case D3DFVF_XYZB3:  size += 6 * sizeof(FLOAT); break;
1918         case D3DFVF_XYZB4:  size += 7 * sizeof(FLOAT); break;
1919         case D3DFVF_XYZB5:  size += 8 * sizeof(FLOAT); break;
1920         case D3DFVF_XYZW:   size += 4 * sizeof(FLOAT); break;
1921     }
1922
1923     for (i = 0; i < numTextures; i++)
1924     {
1925         size += Get_TexCoord_Size_From_FVF(FVF, i) * sizeof(FLOAT);
1926     }
1927
1928     return size;
1929 }
1930
1931 /*************************************************************************
1932  * D3DXGetDeclVertexSize
1933  */
1934 UINT WINAPI D3DXGetDeclVertexSize(const D3DVERTEXELEMENT9 *decl, DWORD stream_idx)
1935 {
1936     const D3DVERTEXELEMENT9 *element;
1937     UINT size = 0;
1938
1939     TRACE("decl %p, stream_idx %u\n", decl, stream_idx);
1940
1941     if (!decl) return 0;
1942
1943     for (element = decl; element->Stream != 0xff; ++element)
1944     {
1945         UINT type_size;
1946
1947         if (element->Stream != stream_idx) continue;
1948
1949         if (element->Type >= sizeof(d3dx_decltype_size) / sizeof(*d3dx_decltype_size))
1950         {
1951             FIXME("Unhandled element type %#x, size will be incorrect.\n", element->Type);
1952             continue;
1953         }
1954
1955         type_size = d3dx_decltype_size[element->Type];
1956         if (element->Offset + type_size > size) size = element->Offset + type_size;
1957     }
1958
1959     return size;
1960 }
1961
1962 /*************************************************************************
1963  * D3DXGetDeclLength
1964  */
1965 UINT WINAPI D3DXGetDeclLength(const D3DVERTEXELEMENT9 *decl)
1966 {
1967     const D3DVERTEXELEMENT9 *element;
1968
1969     TRACE("decl %p\n", decl);
1970
1971     /* null decl results in exception on Windows XP */
1972
1973     for (element = decl; element->Stream != 0xff; ++element);
1974
1975     return element - decl;
1976 }
1977
1978 /*************************************************************************
1979  * D3DXIntersectTri
1980  */
1981 BOOL WINAPI D3DXIntersectTri(CONST D3DXVECTOR3 *p0, CONST D3DXVECTOR3 *p1, CONST D3DXVECTOR3 *p2, CONST D3DXVECTOR3 *praypos, CONST D3DXVECTOR3 *praydir, FLOAT *pu, FLOAT *pv, FLOAT *pdist)
1982 {
1983     D3DXMATRIX m;
1984     D3DXVECTOR4 vec;
1985
1986     m.u.m[0][0] = p1->x - p0->x;
1987     m.u.m[1][0] = p2->x - p0->x;
1988     m.u.m[2][0] = -praydir->x;
1989     m.u.m[3][0] = 0.0f;
1990     m.u.m[0][1] = p1->y - p0->z;
1991     m.u.m[1][1] = p2->y - p0->z;
1992     m.u.m[2][1] = -praydir->y;
1993     m.u.m[3][1] = 0.0f;
1994     m.u.m[0][2] = p1->z - p0->z;
1995     m.u.m[1][2] = p2->z - p0->z;
1996     m.u.m[2][2] = -praydir->z;
1997     m.u.m[3][2] = 0.0f;
1998     m.u.m[0][3] = 0.0f;
1999     m.u.m[1][3] = 0.0f;
2000     m.u.m[2][3] = 0.0f;
2001     m.u.m[3][3] = 1.0f;
2002
2003     vec.x = praypos->x - p0->x;
2004     vec.y = praypos->y - p0->y;
2005     vec.z = praypos->z - p0->z;
2006     vec.w = 0.0f;
2007
2008     if ( D3DXMatrixInverse(&m, NULL, &m) )
2009     {
2010         D3DXVec4Transform(&vec, &vec, &m);
2011         if ( (vec.x >= 0.0f) && (vec.y >= 0.0f) && (vec.x + vec.y <= 1.0f) && (vec.z >= 0.0f) )
2012         {
2013             *pu = vec.x;
2014             *pv = vec.y;
2015             *pdist = fabs( vec.z );
2016             return TRUE;
2017         }
2018     }
2019
2020     return FALSE;
2021 }
2022
2023 /*************************************************************************
2024  * D3DXSphereBoundProbe
2025  */
2026 BOOL WINAPI D3DXSphereBoundProbe(CONST D3DXVECTOR3 *pcenter, FLOAT radius, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
2027 {
2028     D3DXVECTOR3 difference;
2029     FLOAT a, b, c, d;
2030
2031     a = D3DXVec3LengthSq(praydirection);
2032     if (!D3DXVec3Subtract(&difference, prayposition, pcenter)) return FALSE;
2033     b = D3DXVec3Dot(&difference, praydirection);
2034     c = D3DXVec3LengthSq(&difference) - radius * radius;
2035     d = b * b - a * c;
2036
2037     if ( ( d <= 0.0f ) || ( sqrt(d) <= b ) ) return FALSE;
2038     return TRUE;
2039 }
2040
2041 /*************************************************************************
2042  * D3DXCreateMesh
2043  */
2044 HRESULT WINAPI D3DXCreateMesh(DWORD numfaces, DWORD numvertices, DWORD options, CONST D3DVERTEXELEMENT9 *declaration,
2045                               LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
2046 {
2047     HRESULT hr;
2048     DWORD fvf;
2049     IDirect3DVertexDeclaration9 *vertex_declaration;
2050     UINT vertex_declaration_size;
2051     UINT num_elem;
2052     IDirect3DVertexBuffer9 *vertex_buffer;
2053     IDirect3DIndexBuffer9 *index_buffer;
2054     DWORD *attrib_buffer;
2055     ID3DXMeshImpl *object;
2056     DWORD index_usage = 0;
2057     D3DPOOL index_pool = D3DPOOL_DEFAULT;
2058     D3DFORMAT index_format = D3DFMT_INDEX16;
2059     DWORD vertex_usage = 0;
2060     D3DPOOL vertex_pool = D3DPOOL_DEFAULT;
2061     int i;
2062
2063     TRACE("(%d, %d, %x, %p, %p, %p)\n", numfaces, numvertices, options, declaration, device, mesh);
2064
2065     if (numfaces == 0 || numvertices == 0 || declaration == NULL || device == NULL || mesh == NULL ||
2066         /* D3DXMESH_VB_SHARE is for cloning, and D3DXMESH_USEHWONLY is for ConvertToBlendedMesh */
2067         (options & (D3DXMESH_VB_SHARE | D3DXMESH_USEHWONLY | 0xfffe0000)))
2068     {
2069         return D3DERR_INVALIDCALL;
2070     }
2071     for (i = 0; declaration[i].Stream != 0xff; i++)
2072         if (declaration[i].Stream != 0)
2073             return D3DERR_INVALIDCALL;
2074     num_elem = i + 1;
2075
2076     if (options & D3DXMESH_32BIT)
2077         index_format = D3DFMT_INDEX32;
2078
2079     if (options & D3DXMESH_DONOTCLIP) {
2080         index_usage |= D3DUSAGE_DONOTCLIP;
2081         vertex_usage |= D3DUSAGE_DONOTCLIP;
2082     }
2083     if (options & D3DXMESH_POINTS) {
2084         index_usage |= D3DUSAGE_POINTS;
2085         vertex_usage |= D3DUSAGE_POINTS;
2086     }
2087     if (options & D3DXMESH_RTPATCHES) {
2088         index_usage |= D3DUSAGE_RTPATCHES;
2089         vertex_usage |= D3DUSAGE_RTPATCHES;
2090     }
2091     if (options & D3DXMESH_NPATCHES) {
2092         index_usage |= D3DUSAGE_NPATCHES;
2093         vertex_usage |= D3DUSAGE_NPATCHES;
2094     }
2095
2096     if (options & D3DXMESH_VB_SYSTEMMEM)
2097         vertex_pool = D3DPOOL_SYSTEMMEM;
2098     else if (options & D3DXMESH_VB_MANAGED)
2099         vertex_pool = D3DPOOL_MANAGED;
2100
2101     if (options & D3DXMESH_VB_WRITEONLY)
2102         vertex_usage |= D3DUSAGE_WRITEONLY;
2103     if (options & D3DXMESH_VB_DYNAMIC)
2104         vertex_usage |= D3DUSAGE_DYNAMIC;
2105     if (options & D3DXMESH_VB_SOFTWAREPROCESSING)
2106         vertex_usage |= D3DUSAGE_SOFTWAREPROCESSING;
2107
2108     if (options & D3DXMESH_IB_SYSTEMMEM)
2109         index_pool = D3DPOOL_SYSTEMMEM;
2110     else if (options & D3DXMESH_IB_MANAGED)
2111         index_pool = D3DPOOL_MANAGED;
2112
2113     if (options & D3DXMESH_IB_WRITEONLY)
2114         index_usage |= D3DUSAGE_WRITEONLY;
2115     if (options & D3DXMESH_IB_DYNAMIC)
2116         index_usage |= D3DUSAGE_DYNAMIC;
2117     if (options & D3DXMESH_IB_SOFTWAREPROCESSING)
2118         index_usage |= D3DUSAGE_SOFTWAREPROCESSING;
2119
2120     hr = D3DXFVFFromDeclarator(declaration, &fvf);
2121     if (hr != D3D_OK)
2122     {
2123         fvf = 0;
2124     }
2125
2126     /* Create vertex declaration */
2127     hr = IDirect3DDevice9_CreateVertexDeclaration(device,
2128                                                   declaration,
2129                                                   &vertex_declaration);
2130     if (FAILED(hr))
2131     {
2132         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexDeclaration.\n",hr);
2133         return hr;
2134     }
2135     vertex_declaration_size = D3DXGetDeclVertexSize(declaration, declaration[0].Stream);
2136
2137     /* Create vertex buffer */
2138     hr = IDirect3DDevice9_CreateVertexBuffer(device,
2139                                              numvertices * vertex_declaration_size,
2140                                              vertex_usage,
2141                                              fvf,
2142                                              vertex_pool,
2143                                              &vertex_buffer,
2144                                              NULL);
2145     if (FAILED(hr))
2146     {
2147         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
2148         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2149         return hr;
2150     }
2151
2152     /* Create index buffer */
2153     hr = IDirect3DDevice9_CreateIndexBuffer(device,
2154                                             numfaces * 3 * ((index_format == D3DFMT_INDEX16) ? 2 : 4),
2155                                             index_usage,
2156                                             index_format,
2157                                             index_pool,
2158                                             &index_buffer,
2159                                             NULL);
2160     if (FAILED(hr))
2161     {
2162         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
2163         IDirect3DVertexBuffer9_Release(vertex_buffer);
2164         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2165         return hr;
2166     }
2167
2168     attrib_buffer = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, numfaces * sizeof(*attrib_buffer));
2169     object = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(ID3DXMeshImpl));
2170     if (object == NULL || attrib_buffer == NULL)
2171     {
2172         HeapFree(GetProcessHeap(), 0, attrib_buffer);
2173         IDirect3DIndexBuffer9_Release(index_buffer);
2174         IDirect3DVertexBuffer9_Release(vertex_buffer);
2175         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2176         *mesh = NULL;
2177         return E_OUTOFMEMORY;
2178     }
2179     object->ID3DXMesh_iface.lpVtbl = &D3DXMesh_Vtbl;
2180     object->ref = 1;
2181
2182     object->numfaces = numfaces;
2183     object->numvertices = numvertices;
2184     object->options = options;
2185     object->fvf = fvf;
2186     object->device = device;
2187     IDirect3DDevice9_AddRef(device);
2188
2189     copy_declaration(object->cached_declaration, declaration, num_elem);
2190     object->vertex_declaration = vertex_declaration;
2191     object->vertex_declaration_size = vertex_declaration_size;
2192     object->num_elem = num_elem;
2193     object->vertex_buffer = vertex_buffer;
2194     object->index_buffer = index_buffer;
2195     object->attrib_buffer = attrib_buffer;
2196
2197     *mesh = &object->ID3DXMesh_iface;
2198
2199     return D3D_OK;
2200 }
2201
2202 /*************************************************************************
2203  * D3DXCreateMeshFVF
2204  */
2205 HRESULT WINAPI D3DXCreateMeshFVF(DWORD numfaces, DWORD numvertices, DWORD options, DWORD fvf,
2206                                  LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
2207 {
2208     HRESULT hr;
2209     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
2210
2211     TRACE("(%u, %u, %u, %u, %p, %p)\n", numfaces, numvertices, options, fvf, device, mesh);
2212
2213     hr = D3DXDeclaratorFromFVF(fvf, declaration);
2214     if (FAILED(hr)) return hr;
2215
2216     return D3DXCreateMesh(numfaces, numvertices, options, declaration, device, mesh);
2217 }
2218
2219
2220 struct mesh_data {
2221     DWORD num_vertices;
2222     DWORD num_poly_faces;
2223     DWORD num_tri_faces;
2224     D3DXVECTOR3 *vertices;
2225     DWORD *num_tri_per_face;
2226     DWORD *indices;
2227
2228     DWORD fvf;
2229
2230     /* optional mesh data */
2231
2232     DWORD num_normals;
2233     D3DXVECTOR3 *normals;
2234     DWORD *normal_indices;
2235
2236     D3DXVECTOR2 *tex_coords;
2237
2238     DWORD *vertex_colors;
2239
2240     DWORD num_materials;
2241     D3DXMATERIAL *materials;
2242     DWORD *material_indices;
2243 };
2244
2245 static HRESULT get_next_child(IDirectXFileData *filedata, IDirectXFileData **child, const GUID **type)
2246 {
2247     HRESULT hr;
2248     IDirectXFileDataReference *child_ref = NULL;
2249     IDirectXFileObject *child_obj = NULL;
2250     IDirectXFileData *child_data = NULL;
2251
2252     hr = IDirectXFileData_GetNextObject(filedata, &child_obj);
2253     if (FAILED(hr)) return hr;
2254
2255     hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileDataReference, (void**)&child_ref);
2256     if (SUCCEEDED(hr)) {
2257         hr = IDirectXFileDataReference_Resolve(child_ref, &child_data);
2258         IDirectXFileDataReference_Release(child_ref);
2259     } else {
2260         hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileData, (void**)&child_data);
2261     }
2262     IDirectXFileObject_Release(child_obj);
2263     if (FAILED(hr))
2264         return hr;
2265
2266     hr = IDirectXFileData_GetType(child_data, type);
2267     if (FAILED(hr)) {
2268         IDirectXFileData_Release(child_data);
2269     } else {
2270         *child = child_data;
2271     }
2272
2273     return hr;
2274 }
2275
2276 static HRESULT parse_texture_filename(IDirectXFileData *filedata, LPSTR *filename_out)
2277 {
2278     HRESULT hr;
2279     DWORD data_size;
2280     BYTE *data;
2281     char *filename_in;
2282     char *filename = NULL;
2283
2284     /* template TextureFilename {
2285      *     STRING filename;
2286      * }
2287      */
2288
2289     HeapFree(GetProcessHeap(), 0, *filename_out);
2290     *filename_out = NULL;
2291
2292     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2293     if (FAILED(hr)) return hr;
2294
2295     if (data_size < sizeof(LPSTR)) {
2296         WARN("truncated data (%u bytes)\n", data_size);
2297         return E_FAIL;
2298     }
2299     filename_in = *(LPSTR*)data;
2300
2301     filename = HeapAlloc(GetProcessHeap(), 0, strlen(filename_in) + 1);
2302     if (!filename) return E_OUTOFMEMORY;
2303
2304     strcpy(filename, filename_in);
2305     *filename_out = filename;
2306
2307     return D3D_OK;
2308 }
2309
2310 static HRESULT parse_material(IDirectXFileData *filedata, D3DXMATERIAL *material)
2311 {
2312     HRESULT hr;
2313     DWORD data_size;
2314     BYTE *data;
2315     const GUID *type;
2316     IDirectXFileData *child;
2317
2318     material->pTextureFilename = NULL;
2319
2320     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2321     if (FAILED(hr)) return hr;
2322
2323     /*
2324      * template ColorRGBA {
2325      *     FLOAT red;
2326      *     FLOAT green;
2327      *     FLOAT blue;
2328      *     FLOAT alpha;
2329      * }
2330      * template ColorRGB {
2331      *     FLOAT red;
2332      *     FLOAT green;
2333      *     FLOAT blue;
2334      * }
2335      * template Material {
2336      *     ColorRGBA faceColor;
2337      *     FLOAT power;
2338      *     ColorRGB specularColor;
2339      *     ColorRGB emissiveColor;
2340      *     [ ... ]
2341      * }
2342      */
2343     if (data_size != sizeof(FLOAT) * 11) {
2344         WARN("incorrect data size (%u bytes)\n", data_size);
2345         return E_FAIL;
2346     }
2347
2348     memcpy(&material->MatD3D.Diffuse, data, sizeof(D3DCOLORVALUE));
2349     data += sizeof(D3DCOLORVALUE);
2350     material->MatD3D.Power = *(FLOAT*)data;
2351     data += sizeof(FLOAT);
2352     memcpy(&material->MatD3D.Specular, data, sizeof(FLOAT) * 3);
2353     material->MatD3D.Specular.a = 1.0f;
2354     data += 3 * sizeof(FLOAT);
2355     memcpy(&material->MatD3D.Emissive, data, sizeof(FLOAT) * 3);
2356     material->MatD3D.Emissive.a = 1.0f;
2357     material->MatD3D.Ambient.r = 0.0f;
2358     material->MatD3D.Ambient.g = 0.0f;
2359     material->MatD3D.Ambient.b = 0.0f;
2360     material->MatD3D.Ambient.a = 1.0f;
2361
2362     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2363     {
2364         if (IsEqualGUID(type, &TID_D3DRMTextureFilename)) {
2365             hr = parse_texture_filename(child, &material->pTextureFilename);
2366             if (FAILED(hr)) break;
2367         }
2368     }
2369     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
2370 }
2371
2372 static void destroy_materials(struct mesh_data *mesh)
2373 {
2374     int i;
2375     for (i = 0; i < mesh->num_materials; i++)
2376         HeapFree(GetProcessHeap(), 0, mesh->materials[i].pTextureFilename);
2377     HeapFree(GetProcessHeap(), 0, mesh->materials);
2378     HeapFree(GetProcessHeap(), 0, mesh->material_indices);
2379     mesh->num_materials = 0;
2380     mesh->materials = NULL;
2381     mesh->material_indices = NULL;
2382 }
2383
2384 static HRESULT parse_material_list(IDirectXFileData *filedata, struct mesh_data *mesh)
2385 {
2386     HRESULT hr;
2387     DWORD data_size;
2388     DWORD *data, *in_ptr;
2389     const GUID *type;
2390     IDirectXFileData *child;
2391     DWORD num_materials;
2392     int i;
2393
2394     destroy_materials(mesh);
2395
2396     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2397     if (FAILED(hr)) return hr;
2398
2399     /* template MeshMaterialList {
2400      *     DWORD nMaterials;
2401      *     DWORD nFaceIndexes;
2402      *     array DWORD faceIndexes[nFaceIndexes];
2403      *     [ Material ]
2404      * }
2405      */
2406
2407     in_ptr = data;
2408
2409     if (data_size < sizeof(DWORD))
2410         goto truncated_data_error;
2411     num_materials = *in_ptr++;
2412     if (!num_materials)
2413         return D3D_OK;
2414
2415     if (data_size < 2 * sizeof(DWORD))
2416         goto truncated_data_error;
2417     if (*in_ptr++ != mesh->num_poly_faces) {
2418         WARN("number of material face indices (%u) doesn't match number of faces (%u)\n",
2419              *(in_ptr - 1), mesh->num_poly_faces);
2420         return E_FAIL;
2421     }
2422     if (data_size < 2 * sizeof(DWORD) + mesh->num_poly_faces * sizeof(DWORD))
2423         goto truncated_data_error;
2424     for (i = 0; i < mesh->num_poly_faces; i++) {
2425         if (*in_ptr++ >= num_materials) {
2426             WARN("face %u: reference to undefined material %u (only %u materials)\n",
2427                  i, *(in_ptr - 1), num_materials);
2428             return E_FAIL;
2429         }
2430     }
2431
2432     mesh->materials = HeapAlloc(GetProcessHeap(), 0, num_materials * sizeof(*mesh->materials));
2433     mesh->material_indices = HeapAlloc(GetProcessHeap(), 0, mesh->num_poly_faces * sizeof(*mesh->material_indices));
2434     if (!mesh->materials || !mesh->material_indices)
2435         return E_OUTOFMEMORY;
2436     memcpy(mesh->material_indices, data + 2, mesh->num_poly_faces * sizeof(DWORD));
2437
2438     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2439     {
2440         if (IsEqualGUID(type, &TID_D3DRMMaterial)) {
2441             if (mesh->num_materials >= num_materials) {
2442                 WARN("more materials defined than declared\n");
2443                 return E_FAIL;
2444             }
2445             hr = parse_material(child, &mesh->materials[mesh->num_materials++]);
2446             if (FAILED(hr)) break;
2447         }
2448     }
2449     if (hr != DXFILEERR_NOMOREOBJECTS)
2450         return hr;
2451     if (num_materials != mesh->num_materials) {
2452         WARN("only %u of %u materials defined\n", num_materials, mesh->num_materials);
2453         return E_FAIL;
2454     }
2455
2456     return D3D_OK;
2457 truncated_data_error:
2458     WARN("truncated data (%u bytes)\n", data_size);
2459     return E_FAIL;
2460 }
2461
2462 static HRESULT parse_texture_coords(IDirectXFileData *filedata, struct mesh_data *mesh)
2463 {
2464     HRESULT hr;
2465     DWORD data_size;
2466     BYTE *data;
2467
2468     HeapFree(GetProcessHeap(), 0, mesh->tex_coords);
2469     mesh->tex_coords = NULL;
2470
2471     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2472     if (FAILED(hr)) return hr;
2473
2474     /* template Coords2d {
2475      *     FLOAT u;
2476      *     FLOAT v;
2477      * }
2478      * template MeshTextureCoords {
2479      *     DWORD nTextureCoords;
2480      *     array Coords2d textureCoords[nTextureCoords];
2481      * }
2482      */
2483
2484     if (data_size < sizeof(DWORD))
2485         goto truncated_data_error;
2486     if (*(DWORD*)data != mesh->num_vertices) {
2487         WARN("number of texture coordinates (%u) doesn't match number of vertices (%u)\n",
2488              *(DWORD*)data, mesh->num_vertices);
2489         return E_FAIL;
2490     }
2491     data += sizeof(DWORD);
2492     if (data_size < sizeof(DWORD) + mesh->num_vertices * sizeof(*mesh->tex_coords))
2493         goto truncated_data_error;
2494
2495     mesh->tex_coords = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(*mesh->tex_coords));
2496     if (!mesh->tex_coords) return E_OUTOFMEMORY;
2497     memcpy(mesh->tex_coords, data, mesh->num_vertices * sizeof(*mesh->tex_coords));
2498
2499     mesh->fvf |= D3DFVF_TEX1;
2500
2501     return D3D_OK;
2502 truncated_data_error:
2503     WARN("truncated data (%u bytes)\n", data_size);
2504     return E_FAIL;
2505 }
2506
2507 static HRESULT parse_vertex_colors(IDirectXFileData *filedata, struct mesh_data *mesh)
2508 {
2509     HRESULT hr;
2510     DWORD data_size;
2511     BYTE *data;
2512     DWORD num_colors;
2513     int i;
2514
2515     HeapFree(GetProcessHeap(), 0, mesh->vertex_colors);
2516     mesh->vertex_colors = NULL;
2517
2518     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2519     if (FAILED(hr)) return hr;
2520
2521     /* template IndexedColor {
2522      *     DWORD index;
2523      *     ColorRGBA indexColor;
2524      * }
2525      * template MeshVertexColors {
2526      *     DWORD nVertexColors;
2527      *     array IndexedColor vertexColors[nVertexColors];
2528      * }
2529      */
2530
2531     if (data_size < sizeof(DWORD))
2532         goto truncated_data_error;
2533     num_colors = *(DWORD*)data;
2534     data += sizeof(DWORD);
2535     if (data_size < sizeof(DWORD) + num_colors * (sizeof(DWORD) + sizeof(D3DCOLORVALUE)))
2536         goto truncated_data_error;
2537
2538     mesh->vertex_colors = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(DWORD));
2539     if (!mesh->vertex_colors)
2540         return E_OUTOFMEMORY;
2541
2542     for (i = 0; i < mesh->num_vertices; i++)
2543         mesh->vertex_colors[i] = D3DCOLOR_ARGB(0, 0xff, 0xff, 0xff);
2544     for (i = 0; i < num_colors; i++)
2545     {
2546         D3DCOLORVALUE color;
2547         DWORD index = *(DWORD*)data;
2548         data += sizeof(DWORD);
2549         if (index >= mesh->num_vertices) {
2550             WARN("vertex color %u references undefined vertex %u (only %u vertices)\n",
2551                  i, index, mesh->num_vertices);
2552             return E_FAIL;
2553         }
2554         memcpy(&color, data, sizeof(color));
2555         data += sizeof(color);
2556         color.r = min(1.0f, max(0.0f, color.r));
2557         color.g = min(1.0f, max(0.0f, color.g));
2558         color.b = min(1.0f, max(0.0f, color.b));
2559         color.a = min(1.0f, max(0.0f, color.a));
2560         mesh->vertex_colors[index] = D3DCOLOR_ARGB((BYTE)(color.a * 255.0f + 0.5f),
2561                                                    (BYTE)(color.r * 255.0f + 0.5f),
2562                                                    (BYTE)(color.g * 255.0f + 0.5f),
2563                                                    (BYTE)(color.b * 255.0f + 0.5f));
2564     }
2565
2566     mesh->fvf |= D3DFVF_DIFFUSE;
2567
2568     return D3D_OK;
2569 truncated_data_error:
2570     WARN("truncated data (%u bytes)\n", data_size);
2571     return E_FAIL;
2572 }
2573
2574 static HRESULT parse_normals(IDirectXFileData *filedata, struct mesh_data *mesh)
2575 {
2576     HRESULT hr;
2577     DWORD data_size;
2578     BYTE *data;
2579     DWORD *index_out_ptr;
2580     int i;
2581     DWORD num_face_indices = mesh->num_poly_faces * 2 + mesh->num_tri_faces;
2582
2583     HeapFree(GetProcessHeap(), 0, mesh->normals);
2584     mesh->num_normals = 0;
2585     mesh->normals = NULL;
2586     mesh->normal_indices = NULL;
2587     mesh->fvf |= D3DFVF_NORMAL;
2588
2589     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2590     if (FAILED(hr)) return hr;
2591
2592     /* template Vector {
2593      *     FLOAT x;
2594      *     FLOAT y;
2595      *     FLOAT z;
2596      * }
2597      * template MeshFace {
2598      *     DWORD nFaceVertexIndices;
2599      *     array DWORD faceVertexIndices[nFaceVertexIndices];
2600      * }
2601      * template MeshNormals {
2602      *     DWORD nNormals;
2603      *     array Vector normals[nNormals];
2604      *     DWORD nFaceNormals;
2605      *     array MeshFace faceNormals[nFaceNormals];
2606      * }
2607      */
2608
2609     if (data_size < sizeof(DWORD) * 2)
2610         goto truncated_data_error;
2611     mesh->num_normals = *(DWORD*)data;
2612     data += sizeof(DWORD);
2613     if (data_size < sizeof(DWORD) * 2 + mesh->num_normals * sizeof(D3DXVECTOR3) +
2614                     num_face_indices * sizeof(DWORD))
2615         goto truncated_data_error;
2616
2617     mesh->normals = HeapAlloc(GetProcessHeap(), 0, mesh->num_normals * sizeof(D3DXVECTOR3));
2618     mesh->normal_indices = HeapAlloc(GetProcessHeap(), 0, num_face_indices * sizeof(DWORD));
2619     if (!mesh->normals || !mesh->normal_indices)
2620         return E_OUTOFMEMORY;
2621
2622     memcpy(mesh->normals, data, mesh->num_normals * sizeof(D3DXVECTOR3));
2623     data += mesh->num_normals * sizeof(D3DXVECTOR3);
2624     for (i = 0; i < mesh->num_normals; i++)
2625         D3DXVec3Normalize(&mesh->normals[i], &mesh->normals[i]);
2626
2627     if (*(DWORD*)data != mesh->num_poly_faces) {
2628         WARN("number of face normals (%u) doesn't match number of faces (%u)\n",
2629              *(DWORD*)data, mesh->num_poly_faces);
2630         return E_FAIL;
2631     }
2632     data += sizeof(DWORD);
2633     index_out_ptr = mesh->normal_indices;
2634     for (i = 0; i < mesh->num_poly_faces; i++)
2635     {
2636         DWORD j;
2637         DWORD count = *(DWORD*)data;
2638         if (count != mesh->num_tri_per_face[i] + 2) {
2639             WARN("face %u: number of normals (%u) doesn't match number of vertices (%u)\n",
2640                  i, count, mesh->num_tri_per_face[i] + 2);
2641             return E_FAIL;
2642         }
2643         data += sizeof(DWORD);
2644
2645         for (j = 0; j < count; j++) {
2646             DWORD normal_index = *(DWORD*)data;
2647             if (normal_index >= mesh->num_normals) {
2648                 WARN("face %u, normal index %u: reference to undefined normal %u (only %u normals)\n",
2649                      i, j, normal_index, mesh->num_normals);
2650                 return E_FAIL;
2651             }
2652             *index_out_ptr++ = normal_index;
2653             data += sizeof(DWORD);
2654         }
2655     }
2656
2657     return D3D_OK;
2658 truncated_data_error:
2659     WARN("truncated data (%u bytes)\n", data_size);
2660     return E_FAIL;
2661 }
2662
2663 /* for provide_flags parameters */
2664 #define PROVIDE_MATERIALS 0x1
2665 #define PROVIDE_SKININFO  0x2
2666 #define PROVIDE_ADJACENCY 0x4
2667
2668 static HRESULT parse_mesh(IDirectXFileData *filedata, struct mesh_data *mesh_data, DWORD provide_flags)
2669 {
2670     HRESULT hr;
2671     DWORD data_size;
2672     BYTE *data, *in_ptr;
2673     DWORD *index_out_ptr;
2674     const GUID *type;
2675     IDirectXFileData *child;
2676     int i;
2677
2678     /*
2679      * template Mesh {
2680      *     DWORD nVertices;
2681      *     array Vector vertices[nVertices];
2682      *     DWORD nFaces;
2683      *     array MeshFace faces[nFaces];
2684      *     [ ... ]
2685      * }
2686      */
2687
2688     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2689     if (FAILED(hr)) return hr;
2690
2691     in_ptr = data;
2692     if (data_size < sizeof(DWORD) * 2)
2693         goto truncated_data_error;
2694     mesh_data->num_vertices = *(DWORD*)in_ptr;
2695     if (data_size < sizeof(DWORD) * 2 + mesh_data->num_vertices * sizeof(D3DXVECTOR3))
2696         goto truncated_data_error;
2697     in_ptr += sizeof(DWORD) + mesh_data->num_vertices * sizeof(D3DXVECTOR3);
2698
2699     mesh_data->num_poly_faces = *(DWORD*)in_ptr;
2700     in_ptr += sizeof(DWORD);
2701
2702     mesh_data->num_tri_faces = 0;
2703     for (i = 0; i < mesh_data->num_poly_faces; i++)
2704     {
2705         DWORD num_poly_vertices;
2706         DWORD j;
2707
2708         if (data_size - (in_ptr - data) < sizeof(DWORD))
2709             goto truncated_data_error;
2710         num_poly_vertices = *(DWORD*)in_ptr;
2711         in_ptr += sizeof(DWORD);
2712         if (data_size - (in_ptr - data) < num_poly_vertices * sizeof(DWORD))
2713             goto truncated_data_error;
2714         if (num_poly_vertices < 3) {
2715             WARN("face %u has only %u vertices\n", i, num_poly_vertices);
2716             return E_FAIL;
2717         }
2718         for (j = 0; j < num_poly_vertices; j++) {
2719             if (*(DWORD*)in_ptr >= mesh_data->num_vertices) {
2720                 WARN("face %u, index %u: undefined vertex %u (only %u vertices)\n",
2721                      i, j, *(DWORD*)in_ptr, mesh_data->num_vertices);
2722                 return E_FAIL;
2723             }
2724             in_ptr += sizeof(DWORD);
2725         }
2726         mesh_data->num_tri_faces += num_poly_vertices - 2;
2727     }
2728
2729     mesh_data->fvf = D3DFVF_XYZ;
2730
2731     mesh_data->vertices = HeapAlloc(GetProcessHeap(), 0,
2732             mesh_data->num_vertices * sizeof(*mesh_data->vertices));
2733     mesh_data->num_tri_per_face = HeapAlloc(GetProcessHeap(), 0,
2734             mesh_data->num_poly_faces * sizeof(*mesh_data->num_tri_per_face));
2735     mesh_data->indices = HeapAlloc(GetProcessHeap(), 0,
2736             (mesh_data->num_tri_faces + mesh_data->num_poly_faces * 2) * sizeof(*mesh_data->indices));
2737     if (!mesh_data->vertices || !mesh_data->num_tri_per_face || !mesh_data->indices)
2738         return E_OUTOFMEMORY;
2739
2740     in_ptr = data + sizeof(DWORD);
2741     memcpy(mesh_data->vertices, in_ptr, mesh_data->num_vertices * sizeof(D3DXVECTOR3));
2742     in_ptr += mesh_data->num_vertices * sizeof(D3DXVECTOR3) + sizeof(DWORD);
2743
2744     index_out_ptr = mesh_data->indices;
2745     for (i = 0; i < mesh_data->num_poly_faces; i++)
2746     {
2747         DWORD count;
2748
2749         count = *(DWORD*)in_ptr;
2750         in_ptr += sizeof(DWORD);
2751         mesh_data->num_tri_per_face[i] = count - 2;
2752
2753         while (count--) {
2754             *index_out_ptr++ = *(DWORD*)in_ptr;
2755             in_ptr += sizeof(DWORD);
2756         }
2757     }
2758
2759     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2760     {
2761         if (IsEqualGUID(type, &TID_D3DRMMeshNormals)) {
2762             hr = parse_normals(child, mesh_data);
2763         } else if (IsEqualGUID(type, &TID_D3DRMMeshVertexColors)) {
2764             hr = parse_vertex_colors(child, mesh_data);
2765         } else if (IsEqualGUID(type, &TID_D3DRMMeshTextureCoords)) {
2766             hr = parse_texture_coords(child, mesh_data);
2767         } else if (IsEqualGUID(type, &TID_D3DRMMeshMaterialList) &&
2768                    (provide_flags & PROVIDE_MATERIALS))
2769         {
2770             hr = parse_material_list(child, mesh_data);
2771         } else if (provide_flags & PROVIDE_SKININFO) {
2772             if (IsEqualGUID(type, &DXFILEOBJ_XSkinMeshHeader)) {
2773                 FIXME("Skin mesh loading not implemented.\n");
2774                 hr = E_NOTIMPL;
2775             } else if (IsEqualGUID(type, &DXFILEOBJ_SkinWeights)) {
2776                 /* ignored without XSkinMeshHeader */
2777             }
2778         }
2779         if (FAILED(hr))
2780             break;
2781     }
2782     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
2783 truncated_data_error:
2784     WARN("truncated data (%u bytes)\n", data_size);
2785     return E_FAIL;
2786 }
2787
2788 static HRESULT generate_effects(ID3DXBuffer *materials, DWORD num_materials,
2789                                 ID3DXBuffer **effects)
2790 {
2791     HRESULT hr;
2792     D3DXEFFECTINSTANCE *effect_ptr;
2793     BYTE *out_ptr;
2794     const D3DXMATERIAL *material_ptr = ID3DXBuffer_GetBufferPointer(materials);
2795     static const struct {
2796         const char *param_name;
2797         DWORD name_size;
2798         DWORD num_bytes;
2799         DWORD value_offset;
2800     } material_effects[] = {
2801 #define EFFECT_TABLE_ENTRY(str, field) \
2802     {str, sizeof(str), sizeof(material_ptr->MatD3D.field), offsetof(D3DXMATERIAL, MatD3D.field)}
2803         EFFECT_TABLE_ENTRY("Diffuse", Diffuse),
2804         EFFECT_TABLE_ENTRY("Power", Power),
2805         EFFECT_TABLE_ENTRY("Specular", Specular),
2806         EFFECT_TABLE_ENTRY("Emissive", Emissive),
2807         EFFECT_TABLE_ENTRY("Ambient", Ambient),
2808 #undef EFFECT_TABLE_ENTRY
2809     };
2810     static const char texture_paramname[] = "Texture0@Name";
2811     DWORD buffer_size;
2812     int i;
2813
2814     /* effects buffer layout:
2815      *
2816      * D3DXEFFECTINSTANCE effects[num_materials];
2817      * for (effect in effects)
2818      * {
2819      *     D3DXEFFECTDEFAULT defaults[effect.NumDefaults];
2820      *     for (default in defaults)
2821      *     {
2822      *         *default.pParamName;
2823      *         *default.pValue;
2824      *     }
2825      * }
2826      */
2827     buffer_size = sizeof(D3DXEFFECTINSTANCE);
2828     buffer_size += sizeof(D3DXEFFECTDEFAULT) * ARRAY_SIZE(material_effects);
2829     for (i = 0; i < ARRAY_SIZE(material_effects); i++) {
2830         buffer_size += material_effects[i].name_size;
2831         buffer_size += material_effects[i].num_bytes;
2832     }
2833     buffer_size *= num_materials;
2834     for (i = 0; i < num_materials; i++) {
2835         if (material_ptr[i].pTextureFilename) {
2836             buffer_size += sizeof(D3DXEFFECTDEFAULT);
2837             buffer_size += sizeof(texture_paramname);
2838             buffer_size += strlen(material_ptr[i].pTextureFilename) + 1;
2839         }
2840     }
2841
2842     hr = D3DXCreateBuffer(buffer_size, effects);
2843     if (FAILED(hr)) return hr;
2844     effect_ptr = ID3DXBuffer_GetBufferPointer(*effects);
2845     out_ptr = (BYTE*)(effect_ptr + num_materials);
2846
2847     for (i = 0; i < num_materials; i++)
2848     {
2849         int j;
2850         D3DXEFFECTDEFAULT *defaults = (D3DXEFFECTDEFAULT*)out_ptr;
2851
2852         effect_ptr->pDefaults = defaults;
2853         effect_ptr->NumDefaults = material_ptr->pTextureFilename ? 6 : 5;
2854         out_ptr = (BYTE*)(effect_ptr->pDefaults + effect_ptr->NumDefaults);
2855
2856         for (j = 0; j < ARRAY_SIZE(material_effects); j++)
2857         {
2858             defaults->pParamName = (LPSTR)out_ptr;
2859             strcpy(defaults->pParamName, material_effects[j].param_name);
2860             defaults->pValue = defaults->pParamName + material_effects[j].name_size;
2861             defaults->Type = D3DXEDT_FLOATS;
2862             defaults->NumBytes = material_effects[j].num_bytes;
2863             memcpy(defaults->pValue, (BYTE*)material_ptr + material_effects[j].value_offset, defaults->NumBytes);
2864             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
2865             defaults++;
2866         }
2867
2868         if (material_ptr->pTextureFilename) {
2869             defaults->pParamName = (LPSTR)out_ptr;
2870             strcpy(defaults->pParamName, texture_paramname);
2871             defaults->pValue = defaults->pParamName + sizeof(texture_paramname);
2872             defaults->Type = D3DXEDT_STRING;
2873             defaults->NumBytes = strlen(material_ptr->pTextureFilename) + 1;
2874             strcpy(defaults->pValue, material_ptr->pTextureFilename);
2875             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
2876         }
2877         material_ptr++;
2878         effect_ptr++;
2879     }
2880     assert(out_ptr - (BYTE*)ID3DXBuffer_GetBufferPointer(*effects) == buffer_size);
2881
2882     return D3D_OK;
2883 }
2884
2885 /* change to D3DXLoadSkinMeshFromXof when ID3DXFileData is implemented */
2886 static HRESULT load_skin_mesh_from_xof(IDirectXFileData *filedata,
2887                                        DWORD options,
2888                                        LPDIRECT3DDEVICE9 device,
2889                                        LPD3DXBUFFER *adjacency_out,
2890                                        LPD3DXBUFFER *materials_out,
2891                                        LPD3DXBUFFER *effects_out,
2892                                        DWORD *num_materials_out,
2893                                        LPD3DXSKININFO *skin_info_out,
2894                                        LPD3DXMESH *mesh_out)
2895 {
2896     HRESULT hr;
2897     DWORD *index_in_ptr;
2898     struct mesh_data mesh_data;
2899     DWORD total_vertices;
2900     ID3DXMesh *d3dxmesh = NULL;
2901     ID3DXBuffer *adjacency = NULL;
2902     ID3DXBuffer *materials = NULL;
2903     ID3DXBuffer *effects = NULL;
2904     struct vertex_duplication {
2905         DWORD normal_index;
2906         struct list entry;
2907     } *duplications = NULL;
2908     int i;
2909     void *vertices = NULL;
2910     void *indices = NULL;
2911     BYTE *out_ptr;
2912     DWORD provide_flags = 0;
2913
2914     ZeroMemory(&mesh_data, sizeof(mesh_data));
2915
2916     if (num_materials_out || materials_out || effects_out)
2917         provide_flags |= PROVIDE_MATERIALS;
2918     if (skin_info_out)
2919         provide_flags |= PROVIDE_SKININFO;
2920
2921     hr = parse_mesh(filedata, &mesh_data, provide_flags);
2922     if (FAILED(hr)) goto cleanup;
2923
2924     total_vertices = mesh_data.num_vertices;
2925     if (mesh_data.fvf & D3DFVF_NORMAL) {
2926         /* duplicate vertices with multiple normals */
2927         DWORD num_face_indices = mesh_data.num_poly_faces * 2 + mesh_data.num_tri_faces;
2928         duplications = HeapAlloc(GetProcessHeap(), 0, (mesh_data.num_vertices + num_face_indices) * sizeof(*duplications));
2929         if (!duplications) {
2930             hr = E_OUTOFMEMORY;
2931             goto cleanup;
2932         }
2933         for (i = 0; i < total_vertices; i++)
2934         {
2935             duplications[i].normal_index = -1;
2936             list_init(&duplications[i].entry);
2937         }
2938         for (i = 0; i < num_face_indices; i++) {
2939             DWORD vertex_index = mesh_data.indices[i];
2940             DWORD normal_index = mesh_data.normal_indices[i];
2941             struct vertex_duplication *dup_ptr = &duplications[vertex_index];
2942
2943             if (dup_ptr->normal_index == -1) {
2944                 dup_ptr->normal_index = normal_index;
2945             } else {
2946                 D3DXVECTOR3 *new_normal = &mesh_data.normals[normal_index];
2947                 struct list *dup_list = &dup_ptr->entry;
2948                 while (TRUE) {
2949                     D3DXVECTOR3 *cur_normal = &mesh_data.normals[dup_ptr->normal_index];
2950                     if (new_normal->x == cur_normal->x &&
2951                         new_normal->y == cur_normal->y &&
2952                         new_normal->z == cur_normal->z)
2953                     {
2954                         mesh_data.indices[i] = dup_ptr - duplications;
2955                         break;
2956                     } else if (!list_next(dup_list, &dup_ptr->entry)) {
2957                         dup_ptr = &duplications[total_vertices++];
2958                         dup_ptr->normal_index = normal_index;
2959                         list_add_tail(dup_list, &dup_ptr->entry);
2960                         mesh_data.indices[i] = dup_ptr - duplications;
2961                         break;
2962                     } else {
2963                         dup_ptr = LIST_ENTRY(list_next(dup_list, &dup_ptr->entry),
2964                                              struct vertex_duplication, entry);
2965                     }
2966                 }
2967             }
2968         }
2969     }
2970
2971     hr = D3DXCreateMeshFVF(mesh_data.num_tri_faces, total_vertices, options, mesh_data.fvf, device, &d3dxmesh);
2972     if (FAILED(hr)) goto cleanup;
2973
2974     hr = d3dxmesh->lpVtbl->LockVertexBuffer(d3dxmesh, 0, &vertices);
2975     if (FAILED(hr)) goto cleanup;
2976
2977     out_ptr = vertices;
2978     for (i = 0; i < mesh_data.num_vertices; i++) {
2979         *(D3DXVECTOR3*)out_ptr = mesh_data.vertices[i];
2980         out_ptr += sizeof(D3DXVECTOR3);
2981         if (mesh_data.fvf & D3DFVF_NORMAL) {
2982             if (duplications[i].normal_index == -1)
2983                 ZeroMemory(out_ptr, sizeof(D3DXVECTOR3));
2984             else
2985                 *(D3DXVECTOR3*)out_ptr = mesh_data.normals[duplications[i].normal_index];
2986             out_ptr += sizeof(D3DXVECTOR3);
2987         }
2988         if (mesh_data.fvf & D3DFVF_DIFFUSE) {
2989             *(DWORD*)out_ptr = mesh_data.vertex_colors[i];
2990             out_ptr += sizeof(DWORD);
2991         }
2992         if (mesh_data.fvf & D3DFVF_TEX1) {
2993             *(D3DXVECTOR2*)out_ptr = mesh_data.tex_coords[i];
2994             out_ptr += sizeof(D3DXVECTOR2);
2995         }
2996     }
2997     if (mesh_data.fvf & D3DFVF_NORMAL) {
2998         DWORD vertex_size = D3DXGetFVFVertexSize(mesh_data.fvf);
2999         out_ptr = vertices;
3000         for (i = 0; i < mesh_data.num_vertices; i++) {
3001             struct vertex_duplication *dup_ptr;
3002             LIST_FOR_EACH_ENTRY(dup_ptr, &duplications[i].entry, struct vertex_duplication, entry)
3003             {
3004                 int j = dup_ptr - duplications;
3005                 BYTE *dest_vertex = (BYTE*)vertices + j * vertex_size;
3006
3007                 memcpy(dest_vertex, out_ptr, vertex_size);
3008                 dest_vertex += sizeof(D3DXVECTOR3);
3009                 *(D3DXVECTOR3*)dest_vertex = mesh_data.normals[dup_ptr->normal_index];
3010             }
3011             out_ptr += vertex_size;
3012         }
3013     }
3014     d3dxmesh->lpVtbl->UnlockVertexBuffer(d3dxmesh);
3015
3016     hr = d3dxmesh->lpVtbl->LockIndexBuffer(d3dxmesh, 0, &indices);
3017     if (FAILED(hr)) goto cleanup;
3018
3019     index_in_ptr = mesh_data.indices;
3020 #define FILL_INDEX_BUFFER(indices_var) \
3021         for (i = 0; i < mesh_data.num_poly_faces; i++) \
3022         { \
3023             DWORD count = mesh_data.num_tri_per_face[i]; \
3024             WORD first_index = *index_in_ptr++; \
3025             while (count--) { \
3026                 *indices_var++ = first_index; \
3027                 *indices_var++ = *index_in_ptr; \
3028                 index_in_ptr++; \
3029                 *indices_var++ = *index_in_ptr; \
3030             } \
3031             index_in_ptr++; \
3032         }
3033     if (options & D3DXMESH_32BIT) {
3034         DWORD *dword_indices = indices;
3035         FILL_INDEX_BUFFER(dword_indices)
3036     } else {
3037         WORD *word_indices = indices;
3038         FILL_INDEX_BUFFER(word_indices)
3039     }
3040 #undef FILL_INDEX_BUFFER
3041     d3dxmesh->lpVtbl->UnlockIndexBuffer(d3dxmesh);
3042
3043     if (mesh_data.material_indices) {
3044         DWORD *attrib_buffer = NULL;
3045         hr = d3dxmesh->lpVtbl->LockAttributeBuffer(d3dxmesh, 0, &attrib_buffer);
3046         if (FAILED(hr)) goto cleanup;
3047         for (i = 0; i < mesh_data.num_poly_faces; i++)
3048         {
3049             DWORD count = mesh_data.num_tri_per_face[i];
3050             while (count--)
3051                 *attrib_buffer++ = mesh_data.material_indices[i];
3052         }
3053         d3dxmesh->lpVtbl->UnlockAttributeBuffer(d3dxmesh);
3054
3055         hr = d3dxmesh->lpVtbl->OptimizeInplace(d3dxmesh,
3056                 D3DXMESHOPT_ATTRSORT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_DONOTSPLIT,
3057                 NULL, NULL, NULL, NULL);
3058         if (FAILED(hr)) goto cleanup;
3059     }
3060
3061     if (mesh_data.num_materials && (materials_out || effects_out)) {
3062         DWORD buffer_size = mesh_data.num_materials * sizeof(D3DXMATERIAL);
3063         char *strings_out_ptr;
3064         D3DXMATERIAL *materials_ptr;
3065
3066         for (i = 0; i < mesh_data.num_materials; i++) {
3067             if (mesh_data.materials[i].pTextureFilename)
3068                 buffer_size += strlen(mesh_data.materials[i].pTextureFilename) + 1;
3069         }
3070
3071         hr = D3DXCreateBuffer(buffer_size, &materials);
3072         if (FAILED(hr)) goto cleanup;
3073
3074         materials_ptr = ID3DXBuffer_GetBufferPointer(materials);
3075         memcpy(materials_ptr, mesh_data.materials, mesh_data.num_materials * sizeof(D3DXMATERIAL));
3076         strings_out_ptr = (char*)(materials_ptr + mesh_data.num_materials);
3077         for (i = 0; i < mesh_data.num_materials; i++) {
3078             if (materials_ptr[i].pTextureFilename) {
3079                 strcpy(strings_out_ptr, mesh_data.materials[i].pTextureFilename);
3080                 materials_ptr[i].pTextureFilename = strings_out_ptr;
3081                 strings_out_ptr += strlen(mesh_data.materials[i].pTextureFilename) + 1;
3082             }
3083         }
3084     }
3085
3086     if (mesh_data.num_materials && effects_out) {
3087         hr = generate_effects(materials, mesh_data.num_materials, &effects);
3088         if (FAILED(hr)) goto cleanup;
3089
3090         if (!materials_out) {
3091             ID3DXBuffer_Release(materials);
3092             materials = NULL;
3093         }
3094     }
3095
3096     if (adjacency_out) {
3097         hr = D3DXCreateBuffer(mesh_data.num_tri_faces * 3 * sizeof(DWORD), &adjacency);
3098         if (FAILED(hr)) goto cleanup;
3099         hr = d3dxmesh->lpVtbl->GenerateAdjacency(d3dxmesh, 0.0f, ID3DXBuffer_GetBufferPointer(adjacency));
3100         if (FAILED(hr)) goto cleanup;
3101     }
3102
3103     *mesh_out = d3dxmesh;
3104     if (adjacency_out) *adjacency_out = adjacency;
3105     if (num_materials_out) *num_materials_out = mesh_data.num_materials;
3106     if (materials_out) *materials_out = materials;
3107     if (effects_out) *effects_out = effects;
3108     if (skin_info_out) *skin_info_out = NULL;
3109
3110     hr = D3D_OK;
3111 cleanup:
3112     if (FAILED(hr)) {
3113         if (d3dxmesh) IUnknown_Release(d3dxmesh);
3114         if (adjacency) ID3DXBuffer_Release(adjacency);
3115         if (materials) ID3DXBuffer_Release(materials);
3116         if (effects) ID3DXBuffer_Release(effects);
3117     }
3118     HeapFree(GetProcessHeap(), 0, mesh_data.vertices);
3119     HeapFree(GetProcessHeap(), 0, mesh_data.num_tri_per_face);
3120     HeapFree(GetProcessHeap(), 0, mesh_data.indices);
3121     HeapFree(GetProcessHeap(), 0, mesh_data.normals);
3122     HeapFree(GetProcessHeap(), 0, mesh_data.normal_indices);
3123     destroy_materials(&mesh_data);
3124     HeapFree(GetProcessHeap(), 0, mesh_data.tex_coords);
3125     HeapFree(GetProcessHeap(), 0, mesh_data.vertex_colors);
3126     HeapFree(GetProcessHeap(), 0, duplications);
3127     return hr;
3128 }
3129
3130 HRESULT WINAPI D3DXLoadMeshHierarchyFromXA(LPCSTR filename,
3131                                            DWORD options,
3132                                            LPDIRECT3DDEVICE9 device,
3133                                            LPD3DXALLOCATEHIERARCHY alloc_hier,
3134                                            LPD3DXLOADUSERDATA load_user_data,
3135                                            LPD3DXFRAME *frame_hierarchy,
3136                                            LPD3DXANIMATIONCONTROLLER *anim_controller)
3137 {
3138     HRESULT hr;
3139     int len;
3140     LPWSTR filenameW;
3141
3142     TRACE("(%s, %x, %p, %p, %p, %p, %p)\n", debugstr_a(filename), options,
3143           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3144
3145     if (!filename)
3146         return D3DERR_INVALIDCALL;
3147
3148     len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
3149     filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3150     if (!filenameW) return E_OUTOFMEMORY;
3151     MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
3152
3153     hr = D3DXLoadMeshHierarchyFromXW(filenameW, options, device,
3154             alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3155     HeapFree(GetProcessHeap(), 0, filenameW);
3156
3157     return hr;
3158 }
3159
3160 HRESULT WINAPI D3DXLoadMeshHierarchyFromXW(LPCWSTR filename,
3161                                            DWORD options,
3162                                            LPDIRECT3DDEVICE9 device,
3163                                            LPD3DXALLOCATEHIERARCHY alloc_hier,
3164                                            LPD3DXLOADUSERDATA load_user_data,
3165                                            LPD3DXFRAME *frame_hierarchy,
3166                                            LPD3DXANIMATIONCONTROLLER *anim_controller)
3167 {
3168     HRESULT hr;
3169     DWORD size;
3170     LPVOID buffer;
3171
3172     TRACE("(%s, %x, %p, %p, %p, %p, %p)\n", debugstr_w(filename), options,
3173           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3174
3175     if (!filename)
3176         return D3DERR_INVALIDCALL;
3177
3178     hr = map_view_of_file(filename, &buffer, &size);
3179     if (FAILED(hr))
3180         return D3DXERR_INVALIDDATA;
3181
3182     hr = D3DXLoadMeshHierarchyFromXInMemory(buffer, size, options, device,
3183             alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3184
3185     UnmapViewOfFile(buffer);
3186
3187     return hr;
3188 }
3189
3190 static HRESULT filedata_get_name(IDirectXFileData *filedata, char **name)
3191 {
3192     HRESULT hr;
3193     DWORD name_len;
3194
3195     hr = IDirectXFileData_GetName(filedata, NULL, &name_len);
3196     if (FAILED(hr)) return hr;
3197
3198     if (!name_len)
3199         name_len++;
3200     *name = HeapAlloc(GetProcessHeap(), 0, name_len);
3201     if (!*name) return E_OUTOFMEMORY;
3202
3203     hr = IDirectXFileObject_GetName(filedata, *name, &name_len);
3204     if (FAILED(hr))
3205         HeapFree(GetProcessHeap(), 0, name);
3206     if (!name_len)
3207         (*name)[0] = 0;
3208
3209     return hr;
3210 }
3211
3212 static HRESULT load_mesh_container(IDirectXFileData *filedata,
3213                                    DWORD options,
3214                                    LPDIRECT3DDEVICE9 device,
3215                                    LPD3DXALLOCATEHIERARCHY alloc_hier,
3216                                    D3DXMESHCONTAINER **mesh_container)
3217 {
3218     HRESULT hr;
3219     ID3DXBuffer *adjacency = NULL;
3220     ID3DXBuffer *materials = NULL;
3221     ID3DXBuffer *effects = NULL;
3222     ID3DXSkinInfo *skin_info = NULL;
3223     D3DXMESHDATA mesh_data;
3224     DWORD num_materials = 0;
3225     char *name = NULL;
3226
3227     mesh_data.Type = D3DXMESHTYPE_MESH;
3228     mesh_data.u.pMesh = NULL;
3229
3230     hr = load_skin_mesh_from_xof(filedata, options, device,
3231             &adjacency, &materials, &effects, &num_materials,
3232             &skin_info, &mesh_data.u.pMesh);
3233     if (FAILED(hr)) return hr;
3234
3235     hr = filedata_get_name(filedata, &name);
3236     if (FAILED(hr)) goto cleanup;
3237
3238     hr = alloc_hier->lpVtbl->CreateMeshContainer(alloc_hier, name, &mesh_data,
3239             materials ? ID3DXBuffer_GetBufferPointer(materials) : NULL,
3240             effects ? ID3DXBuffer_GetBufferPointer(effects) : NULL,
3241             num_materials,
3242             adjacency ? ID3DXBuffer_GetBufferPointer(adjacency) : NULL,
3243             skin_info, mesh_container);
3244
3245 cleanup:
3246     if (materials) ID3DXBuffer_Release(materials);
3247     if (effects) ID3DXBuffer_Release(effects);
3248     if (adjacency) ID3DXBuffer_Release(adjacency);
3249     if (skin_info) IUnknown_Release(skin_info);
3250     if (mesh_data.u.pMesh) IUnknown_Release(mesh_data.u.pMesh);
3251     HeapFree(GetProcessHeap(), 0, name);
3252     return hr;
3253 }
3254
3255 static HRESULT parse_transform_matrix(IDirectXFileData *filedata, D3DXMATRIX *transform)
3256 {
3257     HRESULT hr;
3258     DWORD data_size;
3259     BYTE *data;
3260
3261     /* template Matrix4x4 {
3262      *     array FLOAT matrix[16];
3263      * }
3264      * template FrameTransformMatrix {
3265      *     Matrix4x4 frameMatrix;
3266      * }
3267      */
3268
3269     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
3270     if (FAILED(hr)) return hr;
3271
3272     if (data_size != sizeof(D3DXMATRIX)) {
3273         WARN("incorrect data size (%u bytes)\n", data_size);
3274         return E_FAIL;
3275     }
3276
3277     memcpy(transform, data, sizeof(D3DXMATRIX));
3278
3279     return D3D_OK;
3280 }
3281
3282 static HRESULT load_frame(IDirectXFileData *filedata,
3283                           DWORD options,
3284                           LPDIRECT3DDEVICE9 device,
3285                           LPD3DXALLOCATEHIERARCHY alloc_hier,
3286                           D3DXFRAME **frame_out)
3287 {
3288     HRESULT hr;
3289     const GUID *type;
3290     IDirectXFileData *child;
3291     char *name = NULL;
3292     D3DXFRAME *frame = NULL;
3293     D3DXMESHCONTAINER **next_container;
3294     D3DXFRAME **next_child;
3295
3296     hr = filedata_get_name(filedata, &name);
3297     if (FAILED(hr)) return hr;
3298
3299     hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, name, frame_out);
3300     HeapFree(GetProcessHeap(), 0, name);
3301     if (FAILED(hr)) return E_FAIL;
3302
3303     frame = *frame_out;
3304     D3DXMatrixIdentity(&frame->TransformationMatrix);
3305     next_child = &frame->pFrameFirstChild;
3306     next_container = &frame->pMeshContainer;
3307
3308     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3309     {
3310         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
3311             hr = load_mesh_container(child, options, device, alloc_hier, next_container);
3312             if (SUCCEEDED(hr))
3313                 next_container = &(*next_container)->pNextMeshContainer;
3314         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
3315             hr = parse_transform_matrix(child, &frame->TransformationMatrix);
3316         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
3317             hr = load_frame(child, options, device, alloc_hier, next_child);
3318             if (SUCCEEDED(hr))
3319                 next_child = &(*next_child)->pFrameSibling;
3320         }
3321         if (FAILED(hr)) break;
3322     }
3323     if (hr == DXFILEERR_NOMOREOBJECTS)
3324         hr = D3D_OK;
3325
3326     return hr;
3327 }
3328
3329 HRESULT WINAPI D3DXLoadMeshHierarchyFromXInMemory(LPCVOID memory,
3330                                                   DWORD memory_size,
3331                                                   DWORD options,
3332                                                   LPDIRECT3DDEVICE9 device,
3333                                                   LPD3DXALLOCATEHIERARCHY alloc_hier,
3334                                                   LPD3DXLOADUSERDATA load_user_data,
3335                                                   LPD3DXFRAME *frame_hierarchy,
3336                                                   LPD3DXANIMATIONCONTROLLER *anim_controller)
3337 {
3338     HRESULT hr;
3339     IDirectXFile *dxfile = NULL;
3340     IDirectXFileEnumObject *enumobj = NULL;
3341     IDirectXFileData *filedata = NULL;
3342     DXFILELOADMEMORY source;
3343     D3DXFRAME *first_frame = NULL;
3344     D3DXFRAME **next_frame = &first_frame;
3345
3346     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
3347           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3348
3349     if (!memory || !memory_size || !device || !frame_hierarchy || !alloc_hier)
3350         return D3DERR_INVALIDCALL;
3351     if (load_user_data || anim_controller) {
3352         if (load_user_data)
3353             FIXME("Loading user data not implemented\n");
3354         if (anim_controller)
3355             FIXME("Animation controller creation not implemented\n");
3356         return E_NOTIMPL;
3357     }
3358
3359     hr = DirectXFileCreate(&dxfile);
3360     if (FAILED(hr)) goto cleanup;
3361
3362     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
3363     if (FAILED(hr)) goto cleanup;
3364
3365     source.lpMemory = (void*)memory;
3366     source.dSize = memory_size;
3367     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
3368     if (FAILED(hr)) goto cleanup;
3369
3370     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
3371     {
3372         const GUID *guid = NULL;
3373
3374         hr = IDirectXFileData_GetType(filedata, &guid);
3375         if (SUCCEEDED(hr)) {
3376             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
3377                 hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, next_frame);
3378                 if (FAILED(hr)) {
3379                     hr = E_FAIL;
3380                     goto cleanup;
3381                 }
3382
3383                 D3DXMatrixIdentity(&(*next_frame)->TransformationMatrix);
3384
3385                 hr = load_mesh_container(filedata, options, device, alloc_hier, &(*next_frame)->pMeshContainer);
3386                 if (FAILED(hr)) goto cleanup;
3387             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
3388                 hr = load_frame(filedata, options, device, alloc_hier, next_frame);
3389                 if (FAILED(hr)) goto cleanup;
3390             }
3391             while (*next_frame)
3392                 next_frame = &(*next_frame)->pFrameSibling;
3393         }
3394
3395         IDirectXFileData_Release(filedata);
3396         filedata = NULL;
3397         if (FAILED(hr))
3398             goto cleanup;
3399     }
3400     if (hr != DXFILEERR_NOMOREOBJECTS)
3401         goto cleanup;
3402
3403     if (!first_frame) {
3404         hr = E_FAIL;
3405     } else if (first_frame->pFrameSibling) {
3406         D3DXFRAME *root_frame = NULL;
3407         hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, &root_frame);
3408         if (FAILED(hr)) {
3409             hr = E_FAIL;
3410             goto cleanup;
3411         }
3412         D3DXMatrixIdentity(&root_frame->TransformationMatrix);
3413         root_frame->pFrameFirstChild = first_frame;
3414         *frame_hierarchy = root_frame;
3415         hr = D3D_OK;
3416     } else {
3417         *frame_hierarchy = first_frame;
3418         hr = D3D_OK;
3419     }
3420
3421 cleanup:
3422     if (FAILED(hr) && first_frame) D3DXFrameDestroy(first_frame, alloc_hier);
3423     if (filedata) IDirectXFileData_Release(filedata);
3424     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
3425     if (dxfile) IDirectXFile_Release(dxfile);
3426     return hr;
3427 }
3428
3429 HRESULT WINAPI D3DXFrameDestroy(LPD3DXFRAME frame, LPD3DXALLOCATEHIERARCHY alloc_hier)
3430 {
3431     HRESULT hr;
3432     BOOL last = FALSE;
3433
3434     TRACE("(%p, %p)\n", frame, alloc_hier);
3435
3436     if (!frame || !alloc_hier)
3437         return D3DERR_INVALIDCALL;
3438
3439     while (!last) {
3440         D3DXMESHCONTAINER *container;
3441         D3DXFRAME *current_frame;
3442
3443         if (frame->pFrameSibling) {
3444             current_frame = frame->pFrameSibling;
3445             frame->pFrameSibling = current_frame->pFrameSibling;
3446             current_frame->pFrameSibling = NULL;
3447         } else if (frame) {
3448             current_frame = frame;
3449             last = TRUE;
3450         }
3451
3452         if (current_frame->pFrameFirstChild) {
3453             hr = D3DXFrameDestroy(current_frame->pFrameFirstChild, alloc_hier);
3454             if (FAILED(hr)) return hr;
3455             current_frame->pFrameFirstChild = NULL;
3456         }
3457
3458         container = current_frame->pMeshContainer;
3459         while (container) {
3460             D3DXMESHCONTAINER *next_container = container->pNextMeshContainer;
3461             hr = alloc_hier->lpVtbl->DestroyMeshContainer(alloc_hier, container);
3462             if (FAILED(hr)) return hr;
3463             container = next_container;
3464         }
3465         hr = alloc_hier->lpVtbl->DestroyFrame(alloc_hier, current_frame);
3466         if (FAILED(hr)) return hr;
3467     }
3468     return D3D_OK;
3469 }
3470
3471 HRESULT WINAPI D3DXLoadMeshFromXA(LPCSTR filename,
3472                                   DWORD options,
3473                                   LPDIRECT3DDEVICE9 device,
3474                                   LPD3DXBUFFER *adjacency,
3475                                   LPD3DXBUFFER *materials,
3476                                   LPD3DXBUFFER *effect_instances,
3477                                   DWORD *num_materials,
3478                                   LPD3DXMESH *mesh)
3479 {
3480     HRESULT hr;
3481     int len;
3482     LPWSTR filenameW;
3483
3484     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_a(filename), options,
3485           device, adjacency, materials, effect_instances, num_materials, mesh);
3486
3487     if (!filename)
3488         return D3DERR_INVALIDCALL;
3489
3490     len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
3491     filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3492     if (!filenameW) return E_OUTOFMEMORY;
3493     MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
3494
3495     hr = D3DXLoadMeshFromXW(filenameW, options, device, adjacency, materials,
3496                             effect_instances, num_materials, mesh);
3497     HeapFree(GetProcessHeap(), 0, filenameW);
3498
3499     return hr;
3500 }
3501
3502 HRESULT WINAPI D3DXLoadMeshFromXW(LPCWSTR filename,
3503                                   DWORD options,
3504                                   LPDIRECT3DDEVICE9 device,
3505                                   LPD3DXBUFFER *adjacency,
3506                                   LPD3DXBUFFER *materials,
3507                                   LPD3DXBUFFER *effect_instances,
3508                                   DWORD *num_materials,
3509                                   LPD3DXMESH *mesh)
3510 {
3511     HRESULT hr;
3512     DWORD size;
3513     LPVOID buffer;
3514
3515     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_w(filename), options,
3516           device, adjacency, materials, effect_instances, num_materials, mesh);
3517
3518     if (!filename)
3519         return D3DERR_INVALIDCALL;
3520
3521     hr = map_view_of_file(filename, &buffer, &size);
3522     if (FAILED(hr))
3523         return D3DXERR_INVALIDDATA;
3524
3525     hr = D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3526             materials, effect_instances, num_materials, mesh);
3527
3528     UnmapViewOfFile(buffer);
3529
3530     return hr;
3531 }
3532
3533 HRESULT WINAPI D3DXLoadMeshFromXResource(HMODULE module,
3534                                          LPCSTR name,
3535                                          LPCSTR type,
3536                                          DWORD options,
3537                                          LPDIRECT3DDEVICE9 device,
3538                                          LPD3DXBUFFER *adjacency,
3539                                          LPD3DXBUFFER *materials,
3540                                          LPD3DXBUFFER *effect_instances,
3541                                          DWORD *num_materials,
3542                                          LPD3DXMESH *mesh)
3543 {
3544     HRESULT hr;
3545     HRSRC resinfo;
3546     DWORD size;
3547     LPVOID buffer;
3548
3549     TRACE("(%p, %s, %s, %x, %p, %p, %p, %p, %p, %p)\n",
3550           module, debugstr_a(name), debugstr_a(type), options, device,
3551           adjacency, materials, effect_instances, num_materials, mesh);
3552
3553     resinfo = FindResourceA(module, name, type);
3554     if (!resinfo) return D3DXERR_INVALIDDATA;
3555
3556     hr = load_resource_into_memory(module, resinfo, &buffer, &size);
3557     if (FAILED(hr)) return D3DXERR_INVALIDDATA;
3558
3559     return D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3560             materials, effect_instances, num_materials, mesh);
3561 }
3562
3563 struct mesh_container
3564 {
3565     struct list entry;
3566     ID3DXMesh *mesh;
3567     ID3DXBuffer *adjacency;
3568     ID3DXBuffer *materials;
3569     ID3DXBuffer *effects;
3570     DWORD num_materials;
3571     D3DXMATRIX transform;
3572 };
3573
3574 static HRESULT parse_frame(IDirectXFileData *filedata,
3575                            DWORD options,
3576                            LPDIRECT3DDEVICE9 device,
3577                            const D3DXMATRIX *parent_transform,
3578                            struct list *container_list,
3579                            DWORD provide_flags)
3580 {
3581     HRESULT hr;
3582     D3DXMATRIX transform = *parent_transform;
3583     IDirectXFileData *child;
3584     const GUID *type;
3585
3586     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3587     {
3588         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
3589             struct mesh_container *container = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container));
3590             if (!container)  {
3591                 hr = E_OUTOFMEMORY;
3592                 break;
3593             }
3594             list_add_tail(container_list, &container->entry);
3595             container->transform = transform;
3596
3597             hr = load_skin_mesh_from_xof(child, options, device,
3598                     (provide_flags & PROVIDE_ADJACENCY) ? &container->adjacency : NULL,
3599                     (provide_flags & PROVIDE_MATERIALS) ? &container->materials : NULL,
3600                     NULL, &container->num_materials, NULL, &container->mesh);
3601         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
3602             D3DXMATRIX new_transform;
3603             hr = parse_transform_matrix(child, &new_transform);
3604             D3DXMatrixMultiply(&transform, &transform, &new_transform);
3605         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
3606             hr = parse_frame(child, options, device, &transform, container_list, provide_flags);
3607         }
3608         if (FAILED(hr)) break;
3609     }
3610     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
3611 }
3612
3613 HRESULT WINAPI D3DXLoadMeshFromXInMemory(LPCVOID memory,
3614                                          DWORD memory_size,
3615                                          DWORD options,
3616                                          LPDIRECT3DDEVICE9 device,
3617                                          LPD3DXBUFFER *adjacency_out,
3618                                          LPD3DXBUFFER *materials_out,
3619                                          LPD3DXBUFFER *effects_out,
3620                                          DWORD *num_materials_out,
3621                                          LPD3DXMESH *mesh_out)
3622 {
3623     HRESULT hr;
3624     IDirectXFile *dxfile = NULL;
3625     IDirectXFileEnumObject *enumobj = NULL;
3626     IDirectXFileData *filedata = NULL;
3627     DXFILELOADMEMORY source;
3628     ID3DXBuffer *materials = NULL;
3629     ID3DXBuffer *effects = NULL;
3630     ID3DXBuffer *adjacency = NULL;
3631     struct list container_list = LIST_INIT(container_list);
3632     struct mesh_container *container_ptr, *next_container_ptr;
3633     DWORD num_materials;
3634     DWORD num_faces, num_vertices;
3635     D3DXMATRIX identity;
3636     int i;
3637     DWORD provide_flags = 0;
3638     DWORD fvf;
3639     ID3DXMesh *concat_mesh = NULL;
3640     D3DVERTEXELEMENT9 concat_decl[MAX_FVF_DECL_SIZE];
3641     BYTE *concat_vertices = NULL;
3642     void *concat_indices = NULL;
3643     DWORD index_offset;
3644     DWORD concat_vertex_size;
3645
3646     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
3647           device, adjacency_out, materials_out, effects_out, num_materials_out, mesh_out);
3648
3649     if (!memory || !memory_size || !device || !mesh_out)
3650         return D3DERR_INVALIDCALL;
3651
3652     hr = DirectXFileCreate(&dxfile);
3653     if (FAILED(hr)) goto cleanup;
3654
3655     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
3656     if (FAILED(hr)) goto cleanup;
3657
3658     source.lpMemory = (void*)memory;
3659     source.dSize = memory_size;
3660     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
3661     if (FAILED(hr)) goto cleanup;
3662
3663     D3DXMatrixIdentity(&identity);
3664     if (adjacency_out) provide_flags |= PROVIDE_ADJACENCY;
3665     if (materials_out || effects_out) provide_flags |= PROVIDE_MATERIALS;
3666
3667     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
3668     {
3669         const GUID *guid = NULL;
3670
3671         hr = IDirectXFileData_GetType(filedata, &guid);
3672         if (SUCCEEDED(hr)) {
3673             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
3674                 container_ptr = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container_ptr));
3675                 if (!container_ptr) {
3676                     hr = E_OUTOFMEMORY;
3677                     goto cleanup;
3678                 }
3679                 list_add_tail(&container_list, &container_ptr->entry);
3680                 D3DXMatrixIdentity(&container_ptr->transform);
3681
3682                 hr = load_skin_mesh_from_xof(filedata, options, device,
3683                         (provide_flags & PROVIDE_ADJACENCY) ? &container_ptr->adjacency : NULL,
3684                         (provide_flags & PROVIDE_MATERIALS) ? &container_ptr->materials : NULL,
3685                         NULL, &container_ptr->num_materials, NULL, &container_ptr->mesh);
3686             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
3687                 hr = parse_frame(filedata, options, device, &identity, &container_list, provide_flags);
3688             }
3689             if (FAILED(hr)) goto cleanup;
3690         }
3691         IDirectXFileData_Release(filedata);
3692         filedata = NULL;
3693         if (FAILED(hr))
3694             goto cleanup;
3695     }
3696     if (hr != DXFILEERR_NOMOREOBJECTS)
3697         goto cleanup;
3698
3699     IDirectXFileEnumObject_Release(enumobj);
3700     enumobj = NULL;
3701     IDirectXFile_Release(dxfile);
3702     dxfile = NULL;
3703
3704     if (list_empty(&container_list)) {
3705         hr = E_FAIL;
3706         goto cleanup;
3707     }
3708
3709     fvf = D3DFVF_XYZ;
3710     num_faces = 0;
3711     num_vertices = 0;
3712     num_materials = 0;
3713     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3714     {
3715         ID3DXMesh *mesh = container_ptr->mesh;
3716         fvf |= mesh->lpVtbl->GetFVF(mesh);
3717         num_faces += mesh->lpVtbl->GetNumFaces(mesh);
3718         num_vertices += mesh->lpVtbl->GetNumVertices(mesh);
3719         num_materials += container_ptr->num_materials;
3720     }
3721
3722     hr = D3DXCreateMeshFVF(num_faces, num_vertices, options, fvf, device, &concat_mesh);
3723     if (FAILED(hr)) goto cleanup;
3724
3725     hr = concat_mesh->lpVtbl->GetDeclaration(concat_mesh, concat_decl);
3726     if (FAILED(hr)) goto cleanup;
3727
3728     concat_vertex_size = D3DXGetDeclVertexSize(concat_decl, 0);
3729
3730     hr = concat_mesh->lpVtbl->LockVertexBuffer(concat_mesh, 0, (void**)&concat_vertices);
3731     if (FAILED(hr)) goto cleanup;
3732
3733     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3734     {
3735         D3DVERTEXELEMENT9 mesh_decl[MAX_FVF_DECL_SIZE];
3736         ID3DXMesh *mesh = container_ptr->mesh;
3737         DWORD num_mesh_vertices = mesh->lpVtbl->GetNumVertices(mesh);
3738         DWORD mesh_vertex_size;
3739         const BYTE *mesh_vertices;
3740
3741         hr = mesh->lpVtbl->GetDeclaration(mesh, mesh_decl);
3742         if (FAILED(hr)) goto cleanup;
3743
3744         mesh_vertex_size = D3DXGetDeclVertexSize(mesh_decl, 0);
3745
3746         hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_vertices);
3747         if (FAILED(hr)) goto cleanup;
3748
3749         for (i = 0; i < num_mesh_vertices; i++) {
3750             int j;
3751             int k = 1;
3752
3753             D3DXVec3TransformCoord((D3DXVECTOR3*)concat_vertices,
3754                                    (D3DXVECTOR3*)mesh_vertices,
3755                                    &container_ptr->transform);
3756             for (j = 1; concat_decl[j].Stream != 0xff; j++)
3757             {
3758                 if (concat_decl[j].Usage == mesh_decl[k].Usage &&
3759                     concat_decl[j].UsageIndex == mesh_decl[k].UsageIndex)
3760                 {
3761                     if (concat_decl[j].Usage == D3DDECLUSAGE_NORMAL) {
3762                         D3DXVec3TransformCoord((D3DXVECTOR3*)(concat_vertices + concat_decl[j].Offset),
3763                                                (D3DXVECTOR3*)(mesh_vertices + mesh_decl[k].Offset),
3764                                                &container_ptr->transform);
3765                     } else {
3766                         memcpy(concat_vertices + concat_decl[j].Offset,
3767                                mesh_vertices + mesh_decl[k].Offset,
3768                                d3dx_decltype_size[mesh_decl[k].Type]);
3769                     }
3770                     k++;
3771                 }
3772             }
3773             mesh_vertices += mesh_vertex_size;
3774             concat_vertices += concat_vertex_size;
3775         }
3776
3777         mesh->lpVtbl->UnlockVertexBuffer(mesh);
3778     }
3779
3780     concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
3781     concat_vertices = NULL;
3782
3783     hr = concat_mesh->lpVtbl->LockIndexBuffer(concat_mesh, 0, &concat_indices);
3784     if (FAILED(hr)) goto cleanup;
3785
3786     index_offset = 0;
3787     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3788     {
3789         ID3DXMesh *mesh = container_ptr->mesh;
3790         const void *mesh_indices;
3791         DWORD num_mesh_faces = mesh->lpVtbl->GetNumFaces(mesh);
3792         int i;
3793
3794         hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_indices);
3795         if (FAILED(hr)) goto cleanup;
3796
3797         if (options & D3DXMESH_32BIT) {
3798             DWORD *dest = concat_indices;
3799             const DWORD *src = mesh_indices;
3800             for (i = 0; i < num_mesh_faces * 3; i++)
3801                 *dest++ = index_offset + *src++;
3802             concat_indices = dest;
3803         } else {
3804             WORD *dest = concat_indices;
3805             const WORD *src = mesh_indices;
3806             for (i = 0; i < num_mesh_faces * 3; i++)
3807                 *dest++ = index_offset + *src++;
3808             concat_indices = dest;
3809         }
3810         mesh->lpVtbl->UnlockIndexBuffer(mesh);
3811
3812         index_offset += num_mesh_faces * 3;
3813     }
3814
3815     concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
3816     concat_indices = NULL;
3817
3818     if (num_materials) {
3819         DWORD *concat_attrib_buffer = NULL;
3820         DWORD offset = 0;
3821
3822         hr = concat_mesh->lpVtbl->LockAttributeBuffer(concat_mesh, 0, &concat_attrib_buffer);
3823         if (FAILED(hr)) goto cleanup;
3824
3825         LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3826         {
3827             ID3DXMesh *mesh = container_ptr->mesh;
3828             const DWORD *mesh_attrib_buffer = NULL;
3829             DWORD count = mesh->lpVtbl->GetNumFaces(mesh);
3830
3831             hr = mesh->lpVtbl->LockAttributeBuffer(mesh, D3DLOCK_READONLY, (DWORD**)&mesh_attrib_buffer);
3832             if (FAILED(hr)) {
3833                 concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
3834                 goto cleanup;
3835             }
3836
3837             while (count--)
3838                 *concat_attrib_buffer++ = offset + *mesh_attrib_buffer++;
3839
3840             mesh->lpVtbl->UnlockAttributeBuffer(mesh);
3841             offset += container_ptr->num_materials;
3842         }
3843         concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
3844     }
3845
3846     if (materials_out || effects_out) {
3847         D3DXMATERIAL *out_ptr;
3848         if (!num_materials) {
3849             /* create default material */
3850             hr = D3DXCreateBuffer(sizeof(D3DXMATERIAL), &materials);
3851             if (FAILED(hr)) goto cleanup;
3852
3853             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
3854             out_ptr->MatD3D.Diffuse.r = 0.5f;
3855             out_ptr->MatD3D.Diffuse.g = 0.5f;
3856             out_ptr->MatD3D.Diffuse.b = 0.5f;
3857             out_ptr->MatD3D.Specular.r = 0.5f;
3858             out_ptr->MatD3D.Specular.g = 0.5f;
3859             out_ptr->MatD3D.Specular.b = 0.5f;
3860             /* D3DXCreateBuffer initializes the rest to zero */
3861         } else {
3862             DWORD buffer_size = num_materials * sizeof(D3DXMATERIAL);
3863             char *strings_out_ptr;
3864
3865             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3866             {
3867                 if (container_ptr->materials) {
3868                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
3869                     for (i = 0; i < container_ptr->num_materials; i++)
3870                     {
3871                         if (in_ptr->pTextureFilename)
3872                             buffer_size += strlen(in_ptr->pTextureFilename) + 1;
3873                         in_ptr++;
3874                     }
3875                 }
3876             }
3877
3878             hr = D3DXCreateBuffer(buffer_size, &materials);
3879             if (FAILED(hr)) goto cleanup;
3880             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
3881             strings_out_ptr = (char*)(out_ptr + num_materials);
3882
3883             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3884             {
3885                 if (container_ptr->materials) {
3886                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
3887                     for (i = 0; i < container_ptr->num_materials; i++)
3888                     {
3889                         out_ptr->MatD3D = in_ptr->MatD3D;
3890                         if (in_ptr->pTextureFilename) {
3891                             out_ptr->pTextureFilename = strings_out_ptr;
3892                             strcpy(out_ptr->pTextureFilename, in_ptr->pTextureFilename);
3893                             strings_out_ptr += strlen(in_ptr->pTextureFilename) + 1;
3894                         }
3895                         in_ptr++;
3896                         out_ptr++;
3897                     }
3898                 }
3899             }
3900         }
3901     }
3902     if (!num_materials)
3903         num_materials = 1;
3904
3905     if (effects_out) {
3906         generate_effects(materials, num_materials, &effects);
3907         if (!materials_out) {
3908             ID3DXBuffer_Release(materials);
3909             materials = NULL;
3910         }
3911     }
3912
3913     if (adjacency_out) {
3914         if (!list_next(&container_list, list_head(&container_list))) {
3915             container_ptr = LIST_ENTRY(list_head(&container_list), struct mesh_container, entry);
3916             adjacency = container_ptr->adjacency;
3917             container_ptr->adjacency = NULL;
3918         } else {
3919             DWORD offset = 0;
3920             DWORD *out_ptr;
3921
3922             hr = D3DXCreateBuffer(num_faces * 3 * sizeof(DWORD), &adjacency);
3923             if (FAILED(hr)) goto cleanup;
3924
3925             out_ptr = ID3DXBuffer_GetBufferPointer(adjacency);
3926             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
3927             {
3928                 DWORD *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->adjacency);
3929                 int count = 3 * container_ptr->mesh->lpVtbl->GetNumFaces(container_ptr->mesh);
3930
3931                 for (i = 0; i < count; i++)
3932                     *out_ptr++ = offset + *in_ptr++;
3933
3934                 offset += count;
3935             }
3936         }
3937     }
3938
3939     *mesh_out = concat_mesh;
3940     if (adjacency_out) *adjacency_out = adjacency;
3941     if (materials_out) *materials_out = materials;
3942     if (effects_out) *effects_out = effects;
3943     if (num_materials_out) *num_materials_out = num_materials;
3944
3945     hr = D3D_OK;
3946 cleanup:
3947     if (concat_indices) concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
3948     if (concat_vertices) concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
3949     if (filedata) IDirectXFileData_Release(filedata);
3950     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
3951     if (dxfile) IDirectXFile_Release(dxfile);
3952     if (FAILED(hr)) {
3953         if (concat_mesh) IUnknown_Release(concat_mesh);
3954         if (materials) ID3DXBuffer_Release(materials);
3955         if (effects) ID3DXBuffer_Release(effects);
3956         if (adjacency) ID3DXBuffer_Release(adjacency);
3957     }
3958     LIST_FOR_EACH_ENTRY_SAFE(container_ptr, next_container_ptr, &container_list, struct mesh_container, entry)
3959     {
3960         if (container_ptr->mesh) IUnknown_Release(container_ptr->mesh);
3961         if (container_ptr->adjacency) ID3DXBuffer_Release(container_ptr->adjacency);
3962         if (container_ptr->materials) ID3DXBuffer_Release(container_ptr->materials);
3963         if (container_ptr->effects) ID3DXBuffer_Release(container_ptr->effects);
3964         HeapFree(GetProcessHeap(), 0, container_ptr);
3965     }
3966     return hr;
3967 }
3968
3969 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
3970                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
3971 {
3972     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
3973
3974     return E_NOTIMPL;
3975 }
3976
3977 struct vertex
3978 {
3979     D3DXVECTOR3 position;
3980     D3DXVECTOR3 normal;
3981 };
3982
3983 typedef WORD face[3];
3984
3985 struct sincos_table
3986 {
3987     float *sin;
3988     float *cos;
3989 };
3990
3991 static void free_sincos_table(struct sincos_table *sincos_table)
3992 {
3993     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
3994     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
3995 }
3996
3997 /* pre compute sine and cosine tables; caller must free */
3998 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
3999 {
4000     float angle;
4001     int i;
4002
4003     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
4004     if (!sincos_table->sin)
4005     {
4006         return FALSE;
4007     }
4008     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
4009     if (!sincos_table->cos)
4010     {
4011         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
4012         return FALSE;
4013     }
4014
4015     angle = angle_start;
4016     for (i = 0; i < n; i++)
4017     {
4018         sincos_table->sin[i] = sin(angle);
4019         sincos_table->cos[i] = cos(angle);
4020         angle += angle_step;
4021     }
4022
4023     return TRUE;
4024 }
4025
4026 static WORD vertex_index(UINT slices, int slice, int stack)
4027 {
4028     return stack*slices+slice+1;
4029 }
4030
4031 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
4032                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4033 {
4034     DWORD number_of_vertices, number_of_faces;
4035     HRESULT hr;
4036     ID3DXMesh *sphere;
4037     struct vertex *vertices;
4038     face *faces;
4039     float phi_step, phi_start;
4040     struct sincos_table phi;
4041     float theta_step, theta, sin_theta, cos_theta;
4042     DWORD vertex, face;
4043     int slice, stack;
4044
4045     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
4046
4047     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
4048     {
4049         return D3DERR_INVALIDCALL;
4050     }
4051
4052     if (adjacency)
4053     {
4054         FIXME("Case of adjacency != NULL not implemented.\n");
4055         return E_NOTIMPL;
4056     }
4057
4058     number_of_vertices = 2 + slices * (stacks-1);
4059     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
4060
4061     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4062                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
4063     if (FAILED(hr))
4064     {
4065         return hr;
4066     }
4067
4068     hr = sphere->lpVtbl->LockVertexBuffer(sphere, 0, (LPVOID *)&vertices);
4069     if (FAILED(hr))
4070     {
4071         sphere->lpVtbl->Release(sphere);
4072         return hr;
4073     }
4074
4075     hr = sphere->lpVtbl->LockIndexBuffer(sphere, 0, (LPVOID *)&faces);
4076     if (FAILED(hr))
4077     {
4078         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4079         sphere->lpVtbl->Release(sphere);
4080         return hr;
4081     }
4082
4083     /* phi = angle on xz plane wrt z axis */
4084     phi_step = -2 * M_PI / slices;
4085     phi_start = M_PI / 2;
4086
4087     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
4088     {
4089         sphere->lpVtbl->UnlockIndexBuffer(sphere);
4090         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4091         sphere->lpVtbl->Release(sphere);
4092         return E_OUTOFMEMORY;
4093     }
4094
4095     /* theta = angle on xy plane wrt x axis */
4096     theta_step = M_PI / stacks;
4097     theta = theta_step;
4098
4099     vertex = 0;
4100     face = 0;
4101
4102     vertices[vertex].normal.x = 0.0f;
4103     vertices[vertex].normal.y = 0.0f;
4104     vertices[vertex].normal.z = 1.0f;
4105     vertices[vertex].position.x = 0.0f;
4106     vertices[vertex].position.y = 0.0f;
4107     vertices[vertex].position.z = radius;
4108     vertex++;
4109
4110     for (stack = 0; stack < stacks - 1; stack++)
4111     {
4112         sin_theta = sin(theta);
4113         cos_theta = cos(theta);
4114
4115         for (slice = 0; slice < slices; slice++)
4116         {
4117             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
4118             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
4119             vertices[vertex].normal.z = cos_theta;
4120             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
4121             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
4122             vertices[vertex].position.z = radius * cos_theta;
4123             vertex++;
4124
4125             if (slice > 0)
4126             {
4127                 if (stack == 0)
4128                 {
4129                     /* top stack is triangle fan */
4130                     faces[face][0] = 0;
4131                     faces[face][1] = slice + 1;
4132                     faces[face][2] = slice;
4133                     face++;
4134                 }
4135                 else
4136                 {
4137                     /* stacks in between top and bottom are quad strips */
4138                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4139                     faces[face][1] = vertex_index(slices, slice, stack-1);
4140                     faces[face][2] = vertex_index(slices, slice-1, stack);
4141                     face++;
4142
4143                     faces[face][0] = vertex_index(slices, slice, stack-1);
4144                     faces[face][1] = vertex_index(slices, slice, stack);
4145                     faces[face][2] = vertex_index(slices, slice-1, stack);
4146                     face++;
4147                 }
4148             }
4149         }
4150
4151         theta += theta_step;
4152
4153         if (stack == 0)
4154         {
4155             faces[face][0] = 0;
4156             faces[face][1] = 1;
4157             faces[face][2] = slice;
4158             face++;
4159         }
4160         else
4161         {
4162             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4163             faces[face][1] = vertex_index(slices, 0, stack-1);
4164             faces[face][2] = vertex_index(slices, slice-1, stack);
4165             face++;
4166
4167             faces[face][0] = vertex_index(slices, 0, stack-1);
4168             faces[face][1] = vertex_index(slices, 0, stack);
4169             faces[face][2] = vertex_index(slices, slice-1, stack);
4170             face++;
4171         }
4172     }
4173
4174     vertices[vertex].position.x = 0.0f;
4175     vertices[vertex].position.y = 0.0f;
4176     vertices[vertex].position.z = -radius;
4177     vertices[vertex].normal.x = 0.0f;
4178     vertices[vertex].normal.y = 0.0f;
4179     vertices[vertex].normal.z = -1.0f;
4180
4181     /* bottom stack is triangle fan */
4182     for (slice = 1; slice < slices; slice++)
4183     {
4184         faces[face][0] = vertex_index(slices, slice-1, stack-1);
4185         faces[face][1] = vertex_index(slices, slice, stack-1);
4186         faces[face][2] = vertex;
4187         face++;
4188     }
4189
4190     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4191     faces[face][1] = vertex_index(slices, 0, stack-1);
4192     faces[face][2] = vertex;
4193
4194     free_sincos_table(&phi);
4195     sphere->lpVtbl->UnlockIndexBuffer(sphere);
4196     sphere->lpVtbl->UnlockVertexBuffer(sphere);
4197     *mesh = sphere;
4198
4199     return D3D_OK;
4200 }
4201
4202 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
4203                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4204 {
4205     DWORD number_of_vertices, number_of_faces;
4206     HRESULT hr;
4207     ID3DXMesh *cylinder;
4208     struct vertex *vertices;
4209     face *faces;
4210     float theta_step, theta_start;
4211     struct sincos_table theta;
4212     float delta_radius, radius, radius_step;
4213     float z, z_step, z_normal;
4214     DWORD vertex, face;
4215     int slice, stack;
4216
4217     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
4218
4219     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
4220     {
4221         return D3DERR_INVALIDCALL;
4222     }
4223
4224     if (adjacency)
4225     {
4226         FIXME("Case of adjacency != NULL not implemented.\n");
4227         return E_NOTIMPL;
4228     }
4229
4230     number_of_vertices = 2 + (slices * (3 + stacks));
4231     number_of_faces = 2 * slices + stacks * (2 * slices);
4232
4233     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4234                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
4235     if (FAILED(hr))
4236     {
4237         return hr;
4238     }
4239
4240     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, 0, (LPVOID *)&vertices);
4241     if (FAILED(hr))
4242     {
4243         cylinder->lpVtbl->Release(cylinder);
4244         return hr;
4245     }
4246
4247     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, 0, (LPVOID *)&faces);
4248     if (FAILED(hr))
4249     {
4250         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4251         cylinder->lpVtbl->Release(cylinder);
4252         return hr;
4253     }
4254
4255     /* theta = angle on xy plane wrt x axis */
4256     theta_step = -2 * M_PI / slices;
4257     theta_start = M_PI / 2;
4258
4259     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
4260     {
4261         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4262         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4263         cylinder->lpVtbl->Release(cylinder);
4264         return E_OUTOFMEMORY;
4265     }
4266
4267     vertex = 0;
4268     face = 0;
4269
4270     delta_radius = radius1 - radius2;
4271     radius = radius1;
4272     radius_step = delta_radius / stacks;
4273
4274     z = -length / 2;
4275     z_step = length / stacks;
4276     z_normal = delta_radius / length;
4277     if (isnan(z_normal))
4278     {
4279         z_normal = 0.0f;
4280     }
4281
4282     vertices[vertex].normal.x = 0.0f;
4283     vertices[vertex].normal.y = 0.0f;
4284     vertices[vertex].normal.z = -1.0f;
4285     vertices[vertex].position.x = 0.0f;
4286     vertices[vertex].position.y = 0.0f;
4287     vertices[vertex++].position.z = z;
4288
4289     for (slice = 0; slice < slices; slice++, vertex++)
4290     {
4291         vertices[vertex].normal.x = 0.0f;
4292         vertices[vertex].normal.y = 0.0f;
4293         vertices[vertex].normal.z = -1.0f;
4294         vertices[vertex].position.x = radius * theta.cos[slice];
4295         vertices[vertex].position.y = radius * theta.sin[slice];
4296         vertices[vertex].position.z = z;
4297
4298         if (slice > 0)
4299         {
4300             faces[face][0] = 0;
4301             faces[face][1] = slice;
4302             faces[face++][2] = slice + 1;
4303         }
4304     }
4305
4306     faces[face][0] = 0;
4307     faces[face][1] = slice;
4308     faces[face++][2] = 1;
4309
4310     for (stack = 1; stack <= stacks+1; stack++)
4311     {
4312         for (slice = 0; slice < slices; slice++, vertex++)
4313         {
4314             vertices[vertex].normal.x = theta.cos[slice];
4315             vertices[vertex].normal.y = theta.sin[slice];
4316             vertices[vertex].normal.z = z_normal;
4317             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
4318             vertices[vertex].position.x = radius * theta.cos[slice];
4319             vertices[vertex].position.y = radius * theta.sin[slice];
4320             vertices[vertex].position.z = z;
4321
4322             if (stack > 1 && slice > 0)
4323             {
4324                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
4325                 faces[face][1] = vertex_index(slices, slice-1, stack);
4326                 faces[face++][2] = vertex_index(slices, slice, stack-1);
4327
4328                 faces[face][0] = vertex_index(slices, slice, stack-1);
4329                 faces[face][1] = vertex_index(slices, slice-1, stack);
4330                 faces[face++][2] = vertex_index(slices, slice, stack);
4331             }
4332         }
4333
4334         if (stack > 1)
4335         {
4336             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4337             faces[face][1] = vertex_index(slices, slice-1, stack);
4338             faces[face++][2] = vertex_index(slices, 0, stack-1);
4339
4340             faces[face][0] = vertex_index(slices, 0, stack-1);
4341             faces[face][1] = vertex_index(slices, slice-1, stack);
4342             faces[face++][2] = vertex_index(slices, 0, stack);
4343         }
4344
4345         if (stack < stacks + 1)
4346         {
4347             z += z_step;
4348             radius -= radius_step;
4349         }
4350     }
4351
4352     for (slice = 0; slice < slices; slice++, vertex++)
4353     {
4354         vertices[vertex].normal.x = 0.0f;
4355         vertices[vertex].normal.y = 0.0f;
4356         vertices[vertex].normal.z = 1.0f;
4357         vertices[vertex].position.x = radius * theta.cos[slice];
4358         vertices[vertex].position.y = radius * theta.sin[slice];
4359         vertices[vertex].position.z = z;
4360
4361         if (slice > 0)
4362         {
4363             faces[face][0] = vertex_index(slices, slice-1, stack);
4364             faces[face][1] = number_of_vertices - 1;
4365             faces[face++][2] = vertex_index(slices, slice, stack);
4366         }
4367     }
4368
4369     vertices[vertex].position.x = 0.0f;
4370     vertices[vertex].position.y = 0.0f;
4371     vertices[vertex].position.z = z;
4372     vertices[vertex].normal.x = 0.0f;
4373     vertices[vertex].normal.y = 0.0f;
4374     vertices[vertex].normal.z = 1.0f;
4375
4376     faces[face][0] = vertex_index(slices, slice-1, stack);
4377     faces[face][1] = number_of_vertices - 1;
4378     faces[face][2] = vertex_index(slices, 0, stack);
4379
4380     free_sincos_table(&theta);
4381     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4382     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4383     *mesh = cylinder;
4384
4385     return D3D_OK;
4386 }
4387
4388 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
4389 {
4390     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
4391
4392     return E_NOTIMPL;
4393 }
4394
4395 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
4396                                HDC hdc, LPCSTR text,
4397                                FLOAT deviation, FLOAT extrusion,
4398                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
4399                                LPGLYPHMETRICSFLOAT glyphmetrics)
4400 {
4401     HRESULT hr;
4402     int len;
4403     LPWSTR textW;
4404
4405     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
4406           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
4407
4408     if (!text)
4409         return D3DERR_INVALIDCALL;
4410
4411     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
4412     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
4413     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
4414
4415     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
4416                          mesh, adjacency, glyphmetrics);
4417     HeapFree(GetProcessHeap(), 0, textW);
4418
4419     return hr;
4420 }
4421
4422 enum pointtype {
4423     POINTTYPE_CURVE = 0,
4424     POINTTYPE_CORNER,
4425     POINTTYPE_CURVE_START,
4426     POINTTYPE_CURVE_END,
4427     POINTTYPE_CURVE_MIDDLE,
4428 };
4429
4430 struct point2d
4431 {
4432     D3DXVECTOR2 pos;
4433     enum pointtype corner;
4434 };
4435
4436 struct dynamic_array
4437 {
4438     int count, capacity;
4439     void *items;
4440 };
4441
4442 /* is a dynamic_array */
4443 struct outline
4444 {
4445     int count, capacity;
4446     struct point2d *items;
4447 };
4448
4449 /* is a dynamic_array */
4450 struct outline_array
4451 {
4452     int count, capacity;
4453     struct outline *items;
4454 };
4455
4456 struct face_array
4457 {
4458     int count;
4459     face *items;
4460 };
4461
4462 struct point2d_index
4463 {
4464     struct outline *outline;
4465     int vertex;
4466 };
4467
4468 struct point2d_index_array
4469 {
4470     int count;
4471     struct point2d_index *items;
4472 };
4473
4474 struct glyphinfo
4475 {
4476     struct outline_array outlines;
4477     struct face_array faces;
4478     struct point2d_index_array ordered_vertices;
4479     float offset_x;
4480 };
4481
4482 /* is an dynamic_array */
4483 struct word_array
4484 {
4485     int count, capacity;
4486     WORD *items;
4487 };
4488
4489 /* complex polygons are split into monotone polygons, which have
4490  * at most 2 intersections with the vertical sweep line */
4491 struct triangulation
4492 {
4493     struct word_array vertex_stack;
4494     BOOL last_on_top, merging;
4495 };
4496
4497 /* is an dynamic_array */
4498 struct triangulation_array
4499 {
4500     int count, capacity;
4501     struct triangulation *items;
4502
4503     struct glyphinfo *glyph;
4504 };
4505
4506 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
4507 {
4508     if (count > array->capacity) {
4509         void *new_buffer;
4510         int new_capacity;
4511         if (array->items && array->capacity) {
4512             new_capacity = max(array->capacity * 2, count);
4513             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
4514         } else {
4515             new_capacity = max(16, count);
4516             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
4517         }
4518         if (!new_buffer)
4519             return FALSE;
4520         array->items = new_buffer;
4521         array->capacity = new_capacity;
4522     }
4523     return TRUE;
4524 }
4525
4526 static struct point2d *add_points(struct outline *array, int num)
4527 {
4528     struct point2d *item;
4529
4530     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
4531         return NULL;
4532
4533     item = &array->items[array->count];
4534     array->count += num;
4535     return item;
4536 }
4537
4538 static struct outline *add_outline(struct outline_array *array)
4539 {
4540     struct outline *item;
4541
4542     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4543         return NULL;
4544
4545     item = &array->items[array->count++];
4546     ZeroMemory(item, sizeof(*item));
4547     return item;
4548 }
4549
4550 static inline face *add_face(struct face_array *array)
4551 {
4552     return &array->items[array->count++];
4553 }
4554
4555 static struct triangulation *add_triangulation(struct triangulation_array *array)
4556 {
4557     struct triangulation *item;
4558
4559     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4560         return NULL;
4561
4562     item = &array->items[array->count++];
4563     ZeroMemory(item, sizeof(*item));
4564     return item;
4565 }
4566
4567 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
4568 {
4569     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4570         return E_OUTOFMEMORY;
4571
4572     array->items[array->count++] = vertex_index;
4573     return S_OK;
4574 }
4575
4576 /* assume fixed point numbers can be converted to float point in place */
4577 C_ASSERT(sizeof(FIXED) == sizeof(float));
4578 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
4579
4580 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
4581 {
4582     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
4583     while (count--) {
4584         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
4585         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
4586         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
4587         pt++;
4588     }
4589     return ret;
4590 }
4591
4592 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
4593                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
4594                                  float max_deviation_sq)
4595 {
4596     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
4597     float deviation_sq;
4598
4599     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
4600     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
4601     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
4602
4603     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
4604     if (deviation_sq < max_deviation_sq) {
4605         struct point2d *pt = add_points(outline, 1);
4606         if (!pt) return E_OUTOFMEMORY;
4607         pt->pos = *p2;
4608         pt->corner = POINTTYPE_CURVE;
4609         /* the end point is omitted because the end line merges into the next segment of
4610          * the split bezier curve, and the end of the split bezier curve is added outside
4611          * this recursive function. */
4612     } else {
4613         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
4614         if (hr != S_OK) return hr;
4615         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
4616         if (hr != S_OK) return hr;
4617     }
4618
4619     return S_OK;
4620 }
4621
4622 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
4623 {
4624     /* dot product = cos(theta) */
4625     return D3DXVec2Dot(dir1, dir2) > cos_theta;
4626 }
4627
4628 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
4629 {
4630     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
4631 }
4632
4633 struct cos_table
4634 {
4635     float cos_half;
4636     float cos_45;
4637     float cos_90;
4638 };
4639
4640 static BOOL attempt_line_merge(struct outline *outline,
4641                                int pt_index,
4642                                const D3DXVECTOR2 *nextpt,
4643                                BOOL to_curve,
4644                                const struct cos_table *table)
4645 {
4646     D3DXVECTOR2 curdir, lastdir;
4647     struct point2d *prevpt, *pt;
4648     BOOL ret = FALSE;
4649
4650     pt = &outline->items[pt_index];
4651     pt_index = (pt_index - 1 + outline->count) % outline->count;
4652     prevpt = &outline->items[pt_index];
4653
4654     if (to_curve)
4655         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
4656
4657     if (outline->count < 2)
4658         return FALSE;
4659
4660     /* remove last point if the next line continues the last line */
4661     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
4662     unit_vec2(&curdir, &pt->pos, nextpt);
4663     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
4664     {
4665         outline->count--;
4666         if (pt->corner == POINTTYPE_CURVE_END)
4667             prevpt->corner = pt->corner;
4668         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
4669             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
4670         pt = prevpt;
4671
4672         ret = TRUE;
4673         if (outline->count < 2)
4674             return ret;
4675
4676         pt_index = (pt_index - 1 + outline->count) % outline->count;
4677         prevpt = &outline->items[pt_index];
4678         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
4679         unit_vec2(&curdir, &pt->pos, nextpt);
4680     }
4681     return ret;
4682 }
4683
4684 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
4685                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
4686 {
4687     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
4688
4689     while ((char *)header < (char *)raw_outline + datasize)
4690     {
4691         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
4692         struct point2d *lastpt, *pt;
4693         D3DXVECTOR2 lastdir;
4694         D3DXVECTOR2 *pt_flt;
4695         int j;
4696         struct outline *outline = add_outline(&glyph->outlines);
4697
4698         if (!outline)
4699             return E_OUTOFMEMORY;
4700
4701         pt = add_points(outline, 1);
4702         if (!pt)
4703             return E_OUTOFMEMORY;
4704         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
4705         pt->pos = *pt_flt;
4706         pt->corner = POINTTYPE_CORNER;
4707
4708         if (header->dwType != TT_POLYGON_TYPE)
4709             FIXME("Unknown header type %d\n", header->dwType);
4710
4711         while ((char *)curve < (char *)header + header->cb)
4712         {
4713             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
4714             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
4715
4716             if (!curve->cpfx) {
4717                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
4718                 continue;
4719             }
4720
4721             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
4722
4723             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
4724
4725             if (to_curve)
4726             {
4727                 HRESULT hr;
4728                 int count = curve->cpfx;
4729                 j = 0;
4730
4731                 while (count > 2)
4732                 {
4733                     D3DXVECTOR2 bezier_end;
4734
4735                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
4736                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
4737                     if (hr != S_OK)
4738                         return hr;
4739                     bezier_start = bezier_end;
4740                     count--;
4741                     j++;
4742                 }
4743                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
4744                 if (hr != S_OK)
4745                     return hr;
4746
4747                 pt = add_points(outline, 1);
4748                 if (!pt)
4749                     return E_OUTOFMEMORY;
4750                 j++;
4751                 pt->pos = pt_flt[j];
4752                 pt->corner = POINTTYPE_CURVE_END;
4753             } else {
4754                 pt = add_points(outline, curve->cpfx);
4755                 if (!pt)
4756                     return E_OUTOFMEMORY;
4757                 for (j = 0; j < curve->cpfx; j++)
4758                 {
4759                     pt->pos = pt_flt[j];
4760                     pt->corner = POINTTYPE_CORNER;
4761                     pt++;
4762                 }
4763             }
4764
4765             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
4766         }
4767
4768         /* remove last point if the next line continues the last line */
4769         if (outline->count >= 3) {
4770             BOOL to_curve;
4771
4772             lastpt = &outline->items[outline->count - 1];
4773             pt = &outline->items[0];
4774             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
4775                 if (lastpt->corner == POINTTYPE_CURVE_END)
4776                 {
4777                     if (pt->corner == POINTTYPE_CURVE_START)
4778                         pt->corner = POINTTYPE_CURVE_MIDDLE;
4779                     else
4780                         pt->corner = POINTTYPE_CURVE_END;
4781                 }
4782                 outline->count--;
4783                 lastpt = &outline->items[outline->count - 1];
4784             } else {
4785                 /* outline closed with a line from end to start point */
4786                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
4787             }
4788             lastpt = &outline->items[0];
4789             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
4790             if (lastpt->corner == POINTTYPE_CURVE_START)
4791                 lastpt->corner = POINTTYPE_CORNER;
4792             pt = &outline->items[1];
4793             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
4794                 *lastpt = outline->items[outline->count];
4795         }
4796
4797         lastpt = &outline->items[outline->count - 1];
4798         pt = &outline->items[0];
4799         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
4800         for (j = 0; j < outline->count; j++)
4801         {
4802             D3DXVECTOR2 curdir;
4803
4804             lastpt = pt;
4805             pt = &outline->items[(j + 1) % outline->count];
4806             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
4807
4808             switch (lastpt->corner)
4809             {
4810                 case POINTTYPE_CURVE_START:
4811                 case POINTTYPE_CURVE_END:
4812                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
4813                         lastpt->corner = POINTTYPE_CORNER;
4814                     break;
4815                 case POINTTYPE_CURVE_MIDDLE:
4816                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
4817                         lastpt->corner = POINTTYPE_CORNER;
4818                     else
4819                         lastpt->corner = POINTTYPE_CURVE;
4820                     break;
4821                 default:
4822                     break;
4823             }
4824             lastdir = curdir;
4825         }
4826
4827         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
4828     }
4829     return S_OK;
4830 }
4831
4832 /* Get the y-distance from a line to a point */
4833 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
4834                                           D3DXVECTOR2 *line_pt2,
4835                                           D3DXVECTOR2 *point)
4836 {
4837     D3DXVECTOR2 line_vec = {0, 0};
4838     float line_pt_dx;
4839     float line_y;
4840
4841     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
4842     line_pt_dx = point->x - line_pt1->x;
4843     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
4844     return point->y - line_y;
4845 }
4846
4847 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
4848 {
4849     return &pt_idx->outline->items[pt_idx->vertex].pos;
4850 }
4851
4852 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
4853 {
4854     return get_indexed_point(&glyph->ordered_vertices.items[index]);
4855 }
4856
4857 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
4858 {
4859     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
4860     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
4861     array->count--;
4862 }
4863
4864 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
4865                                        struct triangulation_array *triangulations,
4866                                        WORD vtx_idx,
4867                                        BOOL to_top)
4868 {
4869     struct glyphinfo *glyph = triangulations->glyph;
4870     struct triangulation *t = *t_ptr;
4871     HRESULT hr;
4872     face *face;
4873     int f1, f2;
4874
4875     if (t->last_on_top) {
4876         f1 = 1;
4877         f2 = 2;
4878     } else {
4879         f1 = 2;
4880         f2 = 1;
4881     }
4882
4883     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
4884         /* consume all vertices on the stack */
4885         WORD last_pt = t->vertex_stack.items[0];
4886         int i;
4887         for (i = 1; i < t->vertex_stack.count; i++)
4888         {
4889             face = add_face(&glyph->faces);
4890             if (!face) return E_OUTOFMEMORY;
4891             (*face)[0] = vtx_idx;
4892             (*face)[f1] = last_pt;
4893             (*face)[f2] = last_pt = t->vertex_stack.items[i];
4894         }
4895         t->vertex_stack.items[0] = last_pt;
4896         t->vertex_stack.count = 1;
4897     } else if (t->vertex_stack.count > 1) {
4898         int i = t->vertex_stack.count - 1;
4899         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
4900         WORD top_idx = t->vertex_stack.items[i--];
4901         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
4902
4903         while (i >= 0)
4904         {
4905             WORD prev_idx = t->vertex_stack.items[i--];
4906             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
4907
4908             if (prev_pt->x != top_pt->x &&
4909                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
4910                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
4911                 break;
4912
4913             face = add_face(&glyph->faces);
4914             if (!face) return E_OUTOFMEMORY;
4915             (*face)[0] = vtx_idx;
4916             (*face)[f1] = prev_idx;
4917             (*face)[f2] = top_idx;
4918
4919             top_pt = prev_pt;
4920             top_idx = prev_idx;
4921             t->vertex_stack.count--;
4922         }
4923     }
4924     t->last_on_top = to_top;
4925
4926     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
4927
4928     if (hr == S_OK && t->merging) {
4929         struct triangulation *t2;
4930
4931         t2 = to_top ? t - 1 : t + 1;
4932         t2->merging = FALSE;
4933         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
4934         if (hr != S_OK) return hr;
4935         remove_triangulation(triangulations, t);
4936         if (t2 > t)
4937             t2--;
4938         *t_ptr = t2;
4939     }
4940     return hr;
4941 }
4942
4943 /* check if the point is next on the outline for either the top or bottom */
4944 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
4945 {
4946     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
4947     WORD idx = t->vertex_stack.items[i];
4948     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
4949     struct outline *outline = pt_idx->outline;
4950
4951     if (on_top)
4952         i = (pt_idx->vertex + outline->count - 1) % outline->count;
4953     else
4954         i = (pt_idx->vertex + 1) % outline->count;
4955
4956     return &outline->items[i].pos;
4957 }
4958
4959 static int compare_vertex_indices(const void *a, const void *b)
4960 {
4961     const struct point2d_index *idx1 = a, *idx2 = b;
4962     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
4963     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
4964     float diff = p1->x - p2->x;
4965
4966     if (diff == 0.0f)
4967         diff = p1->y - p2->y;
4968
4969     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
4970 }
4971
4972 static HRESULT triangulate(struct triangulation_array *triangulations)
4973 {
4974     int sweep_idx;
4975     HRESULT hr;
4976     struct glyphinfo *glyph = triangulations->glyph;
4977     int nb_vertices = 0;
4978     int i;
4979     struct point2d_index *idx_ptr;
4980
4981     for (i = 0; i < glyph->outlines.count; i++)
4982         nb_vertices += glyph->outlines.items[i].count;
4983
4984     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
4985             nb_vertices * sizeof(*glyph->ordered_vertices.items));
4986     if (!glyph->ordered_vertices.items)
4987         return E_OUTOFMEMORY;
4988
4989     idx_ptr = glyph->ordered_vertices.items;
4990     for (i = 0; i < glyph->outlines.count; i++)
4991     {
4992         struct outline *outline = &glyph->outlines.items[i];
4993         int j;
4994
4995         idx_ptr->outline = outline;
4996         idx_ptr->vertex = 0;
4997         idx_ptr++;
4998         for (j = outline->count - 1; j > 0; j--)
4999         {
5000             idx_ptr->outline = outline;
5001             idx_ptr->vertex = j;
5002             idx_ptr++;
5003         }
5004     }
5005     glyph->ordered_vertices.count = nb_vertices;
5006
5007     /* Native implementation seems to try to create a triangle fan from
5008      * the first outline point if the glyph only has one outline. */
5009     if (glyph->outlines.count == 1)
5010     {
5011         struct outline *outline = glyph->outlines.items;
5012         D3DXVECTOR2 *base = &outline->items[0].pos;
5013         D3DXVECTOR2 *last = &outline->items[1].pos;
5014         float ccw = 0;
5015
5016         for (i = 2; i < outline->count; i++)
5017         {
5018             D3DXVECTOR2 *next = &outline->items[i].pos;
5019             D3DXVECTOR2 v1 = {0.0f, 0.0f};
5020             D3DXVECTOR2 v2 = {0.0f, 0.0f};
5021
5022             D3DXVec2Subtract(&v1, base, last);
5023             D3DXVec2Subtract(&v2, last, next);
5024             ccw = D3DXVec2CCW(&v1, &v2);
5025             if (ccw > 0.0f)
5026                 break;
5027
5028             last = next;
5029         }
5030         if (ccw <= 0)
5031         {
5032             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5033                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
5034             if (!glyph->faces.items)
5035                 return E_OUTOFMEMORY;
5036
5037             glyph->faces.count = outline->count - 2;
5038             for (i = 0; i < glyph->faces.count; i++)
5039             {
5040                 glyph->faces.items[i][0] = 0;
5041                 glyph->faces.items[i][1] = i + 1;
5042                 glyph->faces.items[i][2] = i + 2;
5043             }
5044             return S_OK;
5045         }
5046     }
5047
5048     /* Perform 2D polygon triangulation for complex glyphs.
5049      * Triangulation is performed using a sweep line concept, from right to left,
5050      * by processing vertices in sorted order. Complex polygons are split into
5051      * monotone polygons which are triangulated separately. */
5052     /* FIXME: The order of the faces is not consistent with the native implementation. */
5053
5054     /* Reserve space for maximum possible faces from triangulation.
5055      * # faces for outer outlines = outline->count - 2
5056      * # faces for inner outlines = outline->count + 2
5057      * There must be at least 1 outer outline. */
5058     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5059             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
5060     if (!glyph->faces.items)
5061         return E_OUTOFMEMORY;
5062
5063     qsort(glyph->ordered_vertices.items, nb_vertices,
5064           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
5065     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
5066     {
5067         int start = 0;
5068         int end = triangulations->count;
5069
5070         while (start < end)
5071         {
5072             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
5073             int current = (start + end) / 2;
5074             struct triangulation *t = &triangulations->items[current];
5075             BOOL on_top_outline = FALSE;
5076             D3DXVECTOR2 *top_next, *bottom_next;
5077             WORD top_idx, bottom_idx;
5078
5079             if (t->merging && t->last_on_top)
5080                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
5081             else
5082                 top_next = triangulation_get_next_point(t, glyph, TRUE);
5083             if (sweep_vtx == top_next)
5084             {
5085                 if (t->merging && t->last_on_top)
5086                     t++;
5087                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
5088                 if (hr != S_OK) return hr;
5089
5090                 if (t + 1 < &triangulations->items[triangulations->count] &&
5091                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
5092                 {
5093                     /* point also on bottom outline of higher triangulation */
5094                     struct triangulation *t2 = t + 1;
5095                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
5096                     if (hr != S_OK) return hr;
5097
5098                     t->merging = TRUE;
5099                     t2->merging = TRUE;
5100                 }
5101                 on_top_outline = TRUE;
5102             }
5103
5104             if (t->merging && !t->last_on_top)
5105                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
5106             else
5107                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
5108             if (sweep_vtx == bottom_next)
5109             {
5110                 if (t->merging && !t->last_on_top)
5111                     t--;
5112                 if (on_top_outline) {
5113                     /* outline finished */
5114                     remove_triangulation(triangulations, t);
5115                     break;
5116                 }
5117
5118                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
5119                 if (hr != S_OK) return hr;
5120
5121                 if (t > triangulations->items &&
5122                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
5123                 {
5124                     struct triangulation *t2 = t - 1;
5125                     /* point also on top outline of lower triangulation */
5126                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
5127                     if (hr != S_OK) return hr;
5128                     t = t2 + 1; /* t may be invalidated by triangulation merging */
5129
5130                     t->merging = TRUE;
5131                     t2->merging = TRUE;
5132                 }
5133                 break;
5134             }
5135             if (on_top_outline)
5136                 break;
5137
5138             if (t->last_on_top) {
5139                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5140                 bottom_idx = t->vertex_stack.items[0];
5141             } else {
5142                 top_idx = t->vertex_stack.items[0];
5143                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5144             }
5145
5146             /* check if the point is inside or outside this polygon */
5147             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
5148                                              top_next, sweep_vtx) > 0)
5149             { /* above */
5150                 start = current + 1;
5151             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
5152                                                     bottom_next, sweep_vtx) < 0)
5153             { /* below */
5154                 end = current;
5155             } else if (t->merging) {
5156                 /* inside, so cancel merging */
5157                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
5158                 t->merging = FALSE;
5159                 t2->merging = FALSE;
5160                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5161                 if (hr != S_OK) return hr;
5162                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
5163                 if (hr != S_OK) return hr;
5164                 break;
5165             } else {
5166                 /* inside, so split polygon into two monotone parts */
5167                 struct triangulation *t2 = add_triangulation(triangulations);
5168                 if (!t2) return E_OUTOFMEMORY;
5169                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5170                 if (t->last_on_top) {
5171                     t2 = t + 1;
5172                 } else {
5173                     t2 = t;
5174                     t++;
5175                 }
5176
5177                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
5178                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
5179                 if (hr != S_OK) return hr;
5180                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
5181                 if (hr != S_OK) return hr;
5182                 t2->last_on_top = !t->last_on_top;
5183
5184                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5185                 if (hr != S_OK) return hr;
5186                 break;
5187             }
5188         }
5189         if (start >= end)
5190         {
5191             struct triangulation *t;
5192             struct triangulation *t2 = add_triangulation(triangulations);
5193             if (!t2) return E_OUTOFMEMORY;
5194             t = &triangulations->items[start];
5195             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5196             ZeroMemory(t, sizeof(*t));
5197             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
5198             if (hr != S_OK) return hr;
5199         }
5200     }
5201     return S_OK;
5202 }
5203
5204 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
5205                                HDC hdc, LPCWSTR text,
5206                                FLOAT deviation, FLOAT extrusion,
5207                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
5208                                LPGLYPHMETRICSFLOAT glyphmetrics)
5209 {
5210     HRESULT hr;
5211     ID3DXMesh *mesh = NULL;
5212     DWORD nb_vertices, nb_faces;
5213     DWORD nb_front_faces, nb_corners, nb_outline_points;
5214     struct vertex *vertices = NULL;
5215     face *faces = NULL;
5216     int textlen = 0;
5217     float offset_x;
5218     LOGFONTW lf;
5219     OUTLINETEXTMETRICW otm;
5220     HFONT font = NULL, oldfont = NULL;
5221     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
5222     void *raw_outline = NULL;
5223     int bufsize = 0;
5224     struct glyphinfo *glyphs = NULL;
5225     GLYPHMETRICS gm;
5226     struct triangulation_array triangulations = {0, 0, NULL};
5227     int i;
5228     struct vertex *vertex_ptr;
5229     face *face_ptr;
5230     float max_deviation_sq;
5231     const struct cos_table cos_table = {
5232         cos(D3DXToRadian(0.5f)),
5233         cos(D3DXToRadian(45.0f)),
5234         cos(D3DXToRadian(90.0f)),
5235     };
5236     int f1, f2;
5237
5238     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
5239           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
5240
5241     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
5242         return D3DERR_INVALIDCALL;
5243
5244     if (adjacency)
5245     {
5246         FIXME("Case of adjacency != NULL not implemented.\n");
5247         return E_NOTIMPL;
5248     }
5249
5250     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
5251         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
5252     {
5253         return D3DERR_INVALIDCALL;
5254     }
5255
5256     if (deviation == 0.0f)
5257         deviation = 1.0f / otm.otmEMSquare;
5258     max_deviation_sq = deviation * deviation;
5259
5260     lf.lfHeight = otm.otmEMSquare;
5261     lf.lfWidth = 0;
5262     font = CreateFontIndirectW(&lf);
5263     if (!font) {
5264         hr = E_OUTOFMEMORY;
5265         goto error;
5266     }
5267     oldfont = SelectObject(hdc, font);
5268
5269     textlen = strlenW(text);
5270     for (i = 0; i < textlen; i++)
5271     {
5272         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
5273         if (datasize < 0)
5274             return D3DERR_INVALIDCALL;
5275         if (bufsize < datasize)
5276             bufsize = datasize;
5277     }
5278     if (!bufsize) { /* e.g. text == " " */
5279         hr = D3DERR_INVALIDCALL;
5280         goto error;
5281     }
5282
5283     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
5284     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
5285     if (!glyphs || !raw_outline) {
5286         hr = E_OUTOFMEMORY;
5287         goto error;
5288     }
5289
5290     offset_x = 0.0f;
5291     for (i = 0; i < textlen; i++)
5292     {
5293         /* get outline points from data returned from GetGlyphOutline */
5294         int datasize;
5295
5296         glyphs[i].offset_x = offset_x;
5297
5298         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
5299         hr = create_outline(&glyphs[i], raw_outline, datasize,
5300                             max_deviation_sq, otm.otmEMSquare, &cos_table);
5301         if (hr != S_OK) goto error;
5302
5303         triangulations.glyph = &glyphs[i];
5304         hr = triangulate(&triangulations);
5305         if (hr != S_OK) goto error;
5306         if (triangulations.count) {
5307             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
5308             triangulations.count = 0;
5309         }
5310
5311         if (glyphmetrics)
5312         {
5313             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
5314             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
5315             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
5316             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
5317             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
5318             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
5319         }
5320         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
5321     }
5322
5323     /* corner points need an extra vertex for the different side faces normals */
5324     nb_corners = 0;
5325     nb_outline_points = 0;
5326     nb_front_faces = 0;
5327     for (i = 0; i < textlen; i++)
5328     {
5329         int j;
5330         nb_outline_points += glyphs[i].ordered_vertices.count;
5331         nb_front_faces += glyphs[i].faces.count;
5332         for (j = 0; j < glyphs[i].outlines.count; j++)
5333         {
5334             int k;
5335             struct outline *outline = &glyphs[i].outlines.items[j];
5336             nb_corners++; /* first outline point always repeated as a corner */
5337             for (k = 1; k < outline->count; k++)
5338                 if (outline->items[k].corner)
5339                     nb_corners++;
5340         }
5341     }
5342
5343     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
5344     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
5345
5346
5347     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
5348                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
5349     if (FAILED(hr))
5350         goto error;
5351
5352     hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (LPVOID *)&vertices);
5353     if (FAILED(hr))
5354         goto error;
5355
5356     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, (LPVOID *)&faces);
5357     if (FAILED(hr))
5358         goto error;
5359
5360     /* convert 2D vertices and faces into 3D mesh */
5361     vertex_ptr = vertices;
5362     face_ptr = faces;
5363     if (extrusion == 0.0f) {
5364         f1 = 1;
5365         f2 = 2;
5366     } else {
5367         f1 = 2;
5368         f2 = 1;
5369     }
5370     for (i = 0; i < textlen; i++)
5371     {
5372         int j;
5373         int count;
5374         struct vertex *back_vertices;
5375         face *back_faces;
5376
5377         /* side vertices and faces */
5378         for (j = 0; j < glyphs[i].outlines.count; j++)
5379         {
5380             struct vertex *outline_vertices = vertex_ptr;
5381             struct outline *outline = &glyphs[i].outlines.items[j];
5382             int k;
5383             struct point2d *prevpt = &outline->items[outline->count - 1];
5384             struct point2d *pt = &outline->items[0];
5385
5386             for (k = 1; k <= outline->count; k++)
5387             {
5388                 struct vertex vtx;
5389                 struct point2d *nextpt = &outline->items[k % outline->count];
5390                 WORD vtx_idx = vertex_ptr - vertices;
5391                 D3DXVECTOR2 vec;
5392
5393                 if (pt->corner == POINTTYPE_CURVE_START)
5394                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
5395                 else if (pt->corner)
5396                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5397                 else
5398                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
5399                 D3DXVec2Normalize(&vec, &vec);
5400                 vtx.normal.x = -vec.y;
5401                 vtx.normal.y = vec.x;
5402                 vtx.normal.z = 0;
5403
5404                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
5405                 vtx.position.y = pt->pos.y;
5406                 vtx.position.z = 0;
5407                 *vertex_ptr++ = vtx;
5408
5409                 vtx.position.z = -extrusion;
5410                 *vertex_ptr++ = vtx;
5411
5412                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
5413                 vtx.position.y = nextpt->pos.y;
5414                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
5415                     vtx.position.z = -extrusion;
5416                     *vertex_ptr++ = vtx;
5417                     vtx.position.z = 0;
5418                     *vertex_ptr++ = vtx;
5419
5420                     (*face_ptr)[0] = vtx_idx;
5421                     (*face_ptr)[1] = vtx_idx + 2;
5422                     (*face_ptr)[2] = vtx_idx + 1;
5423                     face_ptr++;
5424
5425                     (*face_ptr)[0] = vtx_idx;
5426                     (*face_ptr)[1] = vtx_idx + 3;
5427                     (*face_ptr)[2] = vtx_idx + 2;
5428                     face_ptr++;
5429                 } else {
5430                     if (nextpt->corner) {
5431                         if (nextpt->corner == POINTTYPE_CURVE_END) {
5432                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
5433                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
5434                         } else {
5435                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5436                         }
5437                         D3DXVec2Normalize(&vec, &vec);
5438                         vtx.normal.x = -vec.y;
5439                         vtx.normal.y = vec.x;
5440
5441                         vtx.position.z = 0;
5442                         *vertex_ptr++ = vtx;
5443                         vtx.position.z = -extrusion;
5444                         *vertex_ptr++ = vtx;
5445                     }
5446
5447                     (*face_ptr)[0] = vtx_idx;
5448                     (*face_ptr)[1] = vtx_idx + 3;
5449                     (*face_ptr)[2] = vtx_idx + 1;
5450                     face_ptr++;
5451
5452                     (*face_ptr)[0] = vtx_idx;
5453                     (*face_ptr)[1] = vtx_idx + 2;
5454                     (*face_ptr)[2] = vtx_idx + 3;
5455                     face_ptr++;
5456                 }
5457
5458                 prevpt = pt;
5459                 pt = nextpt;
5460             }
5461             if (!pt->corner) {
5462                 *vertex_ptr++ = *outline_vertices++;
5463                 *vertex_ptr++ = *outline_vertices++;
5464             }
5465         }
5466
5467         /* back vertices and faces */
5468         back_faces = face_ptr;
5469         back_vertices = vertex_ptr;
5470         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
5471         {
5472             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
5473             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
5474             vertex_ptr->position.y = pt->y;
5475             vertex_ptr->position.z = 0;
5476             vertex_ptr->normal.x = 0;
5477             vertex_ptr->normal.y = 0;
5478             vertex_ptr->normal.z = 1;
5479             vertex_ptr++;
5480         }
5481         count = back_vertices - vertices;
5482         for (j = 0; j < glyphs[i].faces.count; j++)
5483         {
5484             face *f = &glyphs[i].faces.items[j];
5485             (*face_ptr)[0] = (*f)[0] + count;
5486             (*face_ptr)[1] = (*f)[1] + count;
5487             (*face_ptr)[2] = (*f)[2] + count;
5488             face_ptr++;
5489         }
5490
5491         /* front vertices and faces */
5492         j = count = vertex_ptr - back_vertices;
5493         while (j--)
5494         {
5495             vertex_ptr->position.x = back_vertices->position.x;
5496             vertex_ptr->position.y = back_vertices->position.y;
5497             vertex_ptr->position.z = -extrusion;
5498             vertex_ptr->normal.x = 0;
5499             vertex_ptr->normal.y = 0;
5500             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
5501             vertex_ptr++;
5502             back_vertices++;
5503         }
5504         j = face_ptr - back_faces;
5505         while (j--)
5506         {
5507             (*face_ptr)[0] = (*back_faces)[0] + count;
5508             (*face_ptr)[1] = (*back_faces)[f1] + count;
5509             (*face_ptr)[2] = (*back_faces)[f2] + count;
5510             face_ptr++;
5511             back_faces++;
5512         }
5513     }
5514
5515     *mesh_ptr = mesh;
5516     hr = D3D_OK;
5517 error:
5518     if (mesh) {
5519         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
5520         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
5521         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
5522     }
5523     if (glyphs) {
5524         for (i = 0; i < textlen; i++)
5525         {
5526             int j;
5527             for (j = 0; j < glyphs[i].outlines.count; j++)
5528                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
5529             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
5530             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
5531             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
5532         }
5533         HeapFree(GetProcessHeap(), 0, glyphs);
5534     }
5535     if (triangulations.items) {
5536         int i;
5537         for (i = 0; i < triangulations.count; i++)
5538             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
5539         HeapFree(GetProcessHeap(), 0, triangulations.items);
5540     }
5541     HeapFree(GetProcessHeap(), 0, raw_outline);
5542     if (oldfont) SelectObject(hdc, oldfont);
5543     if (font) DeleteObject(font);
5544
5545     return hr;
5546 }
5547
5548 static BOOL weld_float1(void *to, void *from, FLOAT epsilon)
5549 {
5550     FLOAT *v1 = to;
5551     FLOAT *v2 = from;
5552
5553     if (fabsf(*v1 - *v2) <= epsilon)
5554     {
5555         *v1 = *v2;
5556
5557         return TRUE;
5558     }
5559
5560     return FALSE;
5561 }
5562
5563 static BOOL weld_float2(void *to, void *from, FLOAT epsilon)
5564 {
5565     D3DXVECTOR2 *v1 = to;
5566     D3DXVECTOR2 *v2 = from;
5567     FLOAT diff_x = fabsf(v1->x - v2->x);
5568     FLOAT diff_y = fabsf(v1->y - v2->y);
5569     FLOAT max_abs_diff = max(diff_x, diff_y);
5570
5571     if (max_abs_diff <= epsilon)
5572     {
5573         memcpy(to, from, sizeof(D3DXVECTOR2));
5574
5575         return TRUE;
5576     }
5577
5578     return FALSE;
5579 }
5580
5581 static BOOL weld_float3(void *to, void *from, FLOAT epsilon)
5582 {
5583     D3DXVECTOR3 *v1 = to;
5584     D3DXVECTOR3 *v2 = from;
5585     FLOAT diff_x = fabsf(v1->x - v2->x);
5586     FLOAT diff_y = fabsf(v1->y - v2->y);
5587     FLOAT diff_z = fabsf(v1->z - v2->z);
5588     FLOAT max_abs_diff = max(diff_x, diff_y);
5589     max_abs_diff = max(diff_z, max_abs_diff);
5590
5591     if (max_abs_diff <= epsilon)
5592     {
5593         memcpy(to, from, sizeof(D3DXVECTOR3));
5594
5595         return TRUE;
5596     }
5597
5598     return FALSE;
5599 }
5600
5601 static BOOL weld_float4(void *to, void *from, FLOAT epsilon)
5602 {
5603     D3DXVECTOR4 *v1 = to;
5604     D3DXVECTOR4 *v2 = from;
5605     FLOAT diff_x = fabsf(v1->x - v2->x);
5606     FLOAT diff_y = fabsf(v1->y - v2->y);
5607     FLOAT diff_z = fabsf(v1->z - v2->z);
5608     FLOAT diff_w = fabsf(v1->w - v2->w);
5609     FLOAT max_abs_diff = fmax(diff_x, diff_y);
5610     max_abs_diff = max(diff_z, max_abs_diff);
5611     max_abs_diff = max(diff_w, max_abs_diff);
5612
5613     if (max_abs_diff <= epsilon)
5614     {
5615         memcpy(to, from, sizeof(D3DXVECTOR4));
5616
5617         return TRUE;
5618     }
5619
5620     return FALSE;
5621 }
5622
5623 static BOOL weld_ubyte4(void *to, void *from, FLOAT epsilon)
5624 {
5625     BYTE *b1 = to;
5626     BYTE *b2 = from;
5627     BYTE truncated_epsilon = (BYTE)epsilon;
5628     BYTE diff_x = b1[0] > b2[0] ? b1[0] - b2[0] : b2[0] - b1[0];
5629     BYTE diff_y = b1[1] > b2[1] ? b1[1] - b2[1] : b2[1] - b1[1];
5630     BYTE diff_z = b1[2] > b2[2] ? b1[2] - b2[2] : b2[2] - b1[2];
5631     BYTE diff_w = b1[3] > b2[3] ? b1[3] - b2[3] : b2[3] - b1[3];
5632     BYTE max_diff = max(diff_x, diff_y);
5633     max_diff = max(diff_z, max_diff);
5634     max_diff = max(diff_w, max_diff);
5635
5636     if (max_diff <= truncated_epsilon)
5637     {
5638         memcpy(to, from, 4 * sizeof(BYTE));
5639
5640         return TRUE;
5641     }
5642
5643     return FALSE;
5644 }
5645
5646 static BOOL weld_ubyte4n(void *to, void *from, FLOAT epsilon)
5647 {
5648     return weld_ubyte4(to, from, epsilon * UCHAR_MAX);
5649 }
5650
5651 static BOOL weld_d3dcolor(void *to, void *from, FLOAT epsilon)
5652 {
5653     return weld_ubyte4n(to, from, epsilon);
5654 }
5655
5656 static BOOL weld_short2(void *to, void *from, FLOAT epsilon)
5657 {
5658     SHORT *s1 = to;
5659     SHORT *s2 = from;
5660     SHORT truncated_epsilon = (SHORT)epsilon;
5661     SHORT diff_x = abs(s1[0] - s2[0]);
5662     SHORT diff_y = abs(s1[1] - s2[1]);
5663     SHORT max_abs_diff = max(diff_x, diff_y);
5664
5665     if (max_abs_diff <= truncated_epsilon)
5666     {
5667         memcpy(to, from, 2 * sizeof(SHORT));
5668
5669         return TRUE;
5670     }
5671
5672     return FALSE;
5673 }
5674
5675 static BOOL weld_short2n(void *to, void *from, FLOAT epsilon)
5676 {
5677     return weld_short2(to, from, epsilon * SHRT_MAX);
5678 }
5679
5680 static BOOL weld_short4(void *to, void *from, FLOAT epsilon)
5681 {
5682     SHORT *s1 = to;
5683     SHORT *s2 = from;
5684     SHORT truncated_epsilon = (SHORT)epsilon;
5685     SHORT diff_x = abs(s1[0] - s2[0]);
5686     SHORT diff_y = abs(s1[1] - s2[1]);
5687     SHORT diff_z = abs(s1[2] - s2[2]);
5688     SHORT diff_w = abs(s1[3] - s2[3]);
5689     SHORT max_abs_diff = max(diff_x, diff_y);
5690     max_abs_diff = max(diff_z, max_abs_diff);
5691     max_abs_diff = max(diff_w, max_abs_diff);
5692
5693     if (max_abs_diff <= truncated_epsilon)
5694     {
5695         memcpy(to, from, 4 * sizeof(SHORT));
5696
5697         return TRUE;
5698     }
5699
5700     return FALSE;
5701 }
5702
5703 static BOOL weld_short4n(void *to, void *from, FLOAT epsilon)
5704 {
5705     return weld_short4(to, from, epsilon * SHRT_MAX);
5706 }
5707
5708 static BOOL weld_ushort2n(void *to, void *from, FLOAT epsilon)
5709 {
5710     USHORT *s1 = to;
5711     USHORT *s2 = from;
5712     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
5713     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
5714     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
5715     USHORT max_diff = max(diff_x, diff_y);
5716
5717     if (max_diff <= scaled_epsilon)
5718     {
5719         memcpy(to, from, 2 * sizeof(USHORT));
5720
5721         return TRUE;
5722     }
5723
5724     return FALSE;
5725 }
5726
5727 static BOOL weld_ushort4n(void *to, void *from, FLOAT epsilon)
5728 {
5729     USHORT *s1 = to;
5730     USHORT *s2 = from;
5731     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
5732     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
5733     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
5734     USHORT diff_z = s1[2] > s2[2] ? s1[2] - s2[2] : s2[2] - s1[2];
5735     USHORT diff_w = s1[3] > s2[3] ? s1[3] - s2[3] : s2[3] - s1[3];
5736     USHORT max_diff = max(diff_x, diff_y);
5737     max_diff = max(diff_z, max_diff);
5738     max_diff = max(diff_w, max_diff);
5739
5740     if (max_diff <= scaled_epsilon)
5741     {
5742         memcpy(to, from, 4 * sizeof(USHORT));
5743
5744         return TRUE;
5745     }
5746
5747     return FALSE;
5748 }
5749
5750 struct udec3
5751 {
5752     UINT x;
5753     UINT y;
5754     UINT z;
5755     UINT w;
5756 };
5757
5758 static struct udec3 dword_to_udec3(DWORD d)
5759 {
5760     struct udec3 v;
5761
5762     v.x = d & 0x3ff;
5763     v.y = (d & 0xffc00) >> 10;
5764     v.z = (d & 0x3ff00000) >> 20;
5765     v.w = (d & 0xc0000000) >> 30;
5766
5767     return v;
5768 }
5769
5770 static BOOL weld_udec3(void *to, void *from, FLOAT epsilon)
5771 {
5772     DWORD *d1 = to;
5773     DWORD *d2 = from;
5774     struct udec3 v1 = dword_to_udec3(*d1);
5775     struct udec3 v2 = dword_to_udec3(*d2);
5776     UINT truncated_epsilon = (UINT)epsilon;
5777     UINT diff_x = v1.x > v2.x ? v1.x - v2.x : v2.x - v1.x;
5778     UINT diff_y = v1.y > v2.y ? v1.y - v2.y : v2.y - v1.y;
5779     UINT diff_z = v1.z > v2.z ? v1.z - v2.z : v2.z - v1.z;
5780     UINT diff_w = v1.w > v2.w ? v1.w - v2.w : v2.w - v1.w;
5781     UINT max_diff = max(diff_x, diff_y);
5782     max_diff = max(diff_z, max_diff);
5783     max_diff = max(diff_w, max_diff);
5784
5785     if (max_diff <= truncated_epsilon)
5786     {
5787         memcpy(to, from, sizeof(DWORD));
5788
5789         return TRUE;
5790     }
5791
5792     return FALSE;
5793 }
5794
5795 struct dec3n
5796 {
5797     INT x;
5798     INT y;
5799     INT z;
5800     INT w;
5801 };
5802
5803 static struct dec3n dword_to_dec3n(DWORD d)
5804 {
5805     struct dec3n v;
5806
5807     v.x = d & 0x3ff;
5808     v.y = (d & 0xffc00) >> 10;
5809     v.z = (d & 0x3ff00000) >> 20;
5810     v.w = (d & 0xc0000000) >> 30;
5811
5812     return v;
5813 }
5814
5815 static BOOL weld_dec3n(void *to, void *from, FLOAT epsilon)
5816 {
5817     const UINT MAX_DEC3N = 511;
5818     DWORD *d1 = to;
5819     DWORD *d2 = from;
5820     struct dec3n v1 = dword_to_dec3n(*d1);
5821     struct dec3n v2 = dword_to_dec3n(*d2);
5822     INT scaled_epsilon = (INT)(epsilon * MAX_DEC3N);
5823     INT diff_x = abs(v1.x - v2.x);
5824     INT diff_y = abs(v1.y - v2.y);
5825     INT diff_z = abs(v1.z - v2.z);
5826     INT diff_w = abs(v1.w - v2.w);
5827     INT max_abs_diff = max(diff_x, diff_y);
5828     max_abs_diff = max(diff_z, max_abs_diff);
5829     max_abs_diff = max(diff_w, max_abs_diff);
5830
5831     if (max_abs_diff <= scaled_epsilon)
5832     {
5833         memcpy(to, from, sizeof(DWORD));
5834
5835         return TRUE;
5836     }
5837
5838     return FALSE;
5839 }
5840
5841 static BOOL weld_float16_2(void *to, void *from, FLOAT epsilon)
5842 {
5843     D3DXFLOAT16 *v1_float16 = to;
5844     D3DXFLOAT16 *v2_float16 = from;
5845     FLOAT diff_x;
5846     FLOAT diff_y;
5847     FLOAT max_abs_diff;
5848     const UINT NUM_ELEM = 2;
5849     FLOAT v1[NUM_ELEM];
5850     FLOAT v2[NUM_ELEM];
5851
5852     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
5853     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
5854
5855     diff_x = fabsf(v1[0] - v2[0]);
5856     diff_y = fabsf(v1[1] - v2[1]);
5857     max_abs_diff = max(diff_x, diff_y);
5858
5859     if (max_abs_diff <= epsilon)
5860     {
5861         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
5862
5863         return TRUE;
5864     }
5865
5866     return FALSE;
5867 }
5868
5869 static BOOL weld_float16_4(void *to, void *from, FLOAT epsilon)
5870 {
5871     D3DXFLOAT16 *v1_float16 = to;
5872     D3DXFLOAT16 *v2_float16 = from;
5873     FLOAT diff_x;
5874     FLOAT diff_y;
5875     FLOAT diff_z;
5876     FLOAT diff_w;
5877     FLOAT max_abs_diff;
5878     const UINT NUM_ELEM = 4;
5879     FLOAT v1[NUM_ELEM];
5880     FLOAT v2[NUM_ELEM];
5881
5882     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
5883     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
5884
5885     diff_x = fabsf(v1[0] - v2[0]);
5886     diff_y = fabsf(v1[1] - v2[1]);
5887     diff_z = fabsf(v1[2] - v2[2]);
5888     diff_w = fabsf(v1[3] - v2[3]);
5889     max_abs_diff = max(diff_x, diff_y);
5890     max_abs_diff = max(diff_z, max_abs_diff);
5891     max_abs_diff = max(diff_w, max_abs_diff);
5892
5893     if (max_abs_diff <= epsilon)
5894     {
5895         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
5896
5897         return TRUE;
5898     }
5899
5900     return FALSE;
5901 }
5902
5903 /* Sets the vertex components to the same value if they are within epsilon. */
5904 static BOOL weld_component(void *to, void *from, D3DDECLTYPE type, FLOAT epsilon)
5905 {
5906     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
5907     BOOL fixme_once_unused = FALSE;
5908     BOOL fixme_once_unknown = FALSE;
5909
5910     switch (type)
5911     {
5912         case D3DDECLTYPE_FLOAT1:
5913             return weld_float1(to, from, epsilon);
5914
5915         case D3DDECLTYPE_FLOAT2:
5916             return weld_float2(to, from, epsilon);
5917
5918         case D3DDECLTYPE_FLOAT3:
5919             return weld_float3(to, from, epsilon);
5920
5921         case D3DDECLTYPE_FLOAT4:
5922             return weld_float4(to, from, epsilon);
5923
5924         case D3DDECLTYPE_D3DCOLOR:
5925             return weld_d3dcolor(to, from, epsilon);
5926
5927         case D3DDECLTYPE_UBYTE4:
5928             return weld_ubyte4(to, from, epsilon);
5929
5930         case D3DDECLTYPE_SHORT2:
5931             return weld_short2(to, from, epsilon);
5932
5933         case D3DDECLTYPE_SHORT4:
5934             return weld_short4(to, from, epsilon);
5935
5936         case D3DDECLTYPE_UBYTE4N:
5937             return weld_ubyte4n(to, from, epsilon);
5938
5939         case D3DDECLTYPE_SHORT2N:
5940             return weld_short2n(to, from, epsilon);
5941
5942         case D3DDECLTYPE_SHORT4N:
5943             return weld_short4n(to, from, epsilon);
5944
5945         case D3DDECLTYPE_USHORT2N:
5946             return weld_ushort2n(to, from, epsilon);
5947
5948         case D3DDECLTYPE_USHORT4N:
5949             return weld_ushort4n(to, from, epsilon);
5950
5951         case D3DDECLTYPE_UDEC3:
5952             return weld_udec3(to, from, epsilon);
5953
5954         case D3DDECLTYPE_DEC3N:
5955             return weld_dec3n(to, from, epsilon);
5956
5957         case D3DDECLTYPE_FLOAT16_2:
5958             return weld_float16_2(to, from, epsilon);
5959
5960         case D3DDECLTYPE_FLOAT16_4:
5961             return weld_float16_4(to, from, epsilon);
5962
5963         case D3DDECLTYPE_UNUSED:
5964             if (!fixme_once_unused++)
5965                 FIXME("D3DDECLTYPE_UNUSED welding not implemented.\n");
5966             break;
5967
5968         default:
5969             if (!fixme_once_unknown++)
5970                 FIXME("Welding of unknown declaration type %d is not implemented.\n", type);
5971             break;
5972     }
5973
5974     return FALSE;
5975 }
5976
5977 static FLOAT get_component_epsilon(const D3DVERTEXELEMENT9 *decl_ptr, const D3DXWELDEPSILONS *epsilons)
5978 {
5979     FLOAT epsilon = 0.0f;
5980     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
5981     static BOOL fixme_once_blendindices = FALSE;
5982     static BOOL fixme_once_positiont = FALSE;
5983     static BOOL fixme_once_fog = FALSE;
5984     static BOOL fixme_once_depth = FALSE;
5985     static BOOL fixme_once_sample = FALSE;
5986     static BOOL fixme_once_unknown = FALSE;
5987
5988     switch (decl_ptr->Usage)
5989     {
5990         case D3DDECLUSAGE_POSITION:
5991             epsilon = epsilons->Position;
5992             break;
5993         case D3DDECLUSAGE_BLENDWEIGHT:
5994             epsilon = epsilons->BlendWeights;
5995             break;
5996         case D3DDECLUSAGE_NORMAL:
5997             epsilon = epsilons->Normals;
5998             break;
5999         case D3DDECLUSAGE_PSIZE:
6000             epsilon = epsilons->PSize;
6001             break;
6002         case D3DDECLUSAGE_TEXCOORD:
6003         {
6004             BYTE usage_index = decl_ptr->UsageIndex;
6005             if (usage_index > 7)
6006                 usage_index = 7;
6007             epsilon = epsilons->Texcoords[usage_index];
6008             break;
6009         }
6010         case D3DDECLUSAGE_TANGENT:
6011             epsilon = epsilons->Tangent;
6012             break;
6013         case D3DDECLUSAGE_BINORMAL:
6014             epsilon = epsilons->Binormal;
6015             break;
6016         case D3DDECLUSAGE_TESSFACTOR:
6017             epsilon = epsilons->TessFactor;
6018             break;
6019         case D3DDECLUSAGE_COLOR:
6020             if (decl_ptr->UsageIndex == 0)
6021                 epsilon = epsilons->Diffuse;
6022             else if (decl_ptr->UsageIndex == 1)
6023                 epsilon = epsilons->Specular;
6024             else
6025                 epsilon = 1e-6f;
6026             break;
6027         case D3DDECLUSAGE_BLENDINDICES:
6028             if (!fixme_once_blendindices++)
6029                 FIXME("D3DDECLUSAGE_BLENDINDICES welding not implemented.\n");
6030             break;
6031         case D3DDECLUSAGE_POSITIONT:
6032             if (!fixme_once_positiont++)
6033                 FIXME("D3DDECLUSAGE_POSITIONT welding not implemented.\n");
6034             break;
6035         case D3DDECLUSAGE_FOG:
6036             if (!fixme_once_fog++)
6037                 FIXME("D3DDECLUSAGE_FOG welding not implemented.\n");
6038             break;
6039         case D3DDECLUSAGE_DEPTH:
6040             if (!fixme_once_depth++)
6041                 FIXME("D3DDECLUSAGE_DEPTH welding not implemented.\n");
6042             break;
6043         case D3DDECLUSAGE_SAMPLE:
6044             if (!fixme_once_sample++)
6045                 FIXME("D3DDECLUSAGE_SAMPLE welding not implemented.\n");
6046             break;
6047         default:
6048             if (!fixme_once_unknown++)
6049                 FIXME("Unknown usage %x\n", decl_ptr->Usage);
6050             break;
6051     }
6052
6053     return epsilon;
6054 }
6055
6056 /* Helper function for reading a 32-bit index buffer. */
6057 static inline DWORD read_ib(void *index_buffer, BOOL indices_are_32bit,
6058                             DWORD index)
6059 {
6060     if (indices_are_32bit)
6061     {
6062         DWORD *indices = index_buffer;
6063         return indices[index];
6064     }
6065     else
6066     {
6067         WORD *indices = index_buffer;
6068         return indices[index];
6069     }
6070 }
6071
6072 /* Helper function for writing to a 32-bit index buffer. */
6073 static inline void write_ib(void *index_buffer, BOOL indices_are_32bit,
6074                             DWORD index, DWORD value)
6075 {
6076     if (indices_are_32bit)
6077     {
6078         DWORD *indices = index_buffer;
6079         indices[index] = value;
6080     }
6081     else
6082     {
6083         WORD *indices = index_buffer;
6084         indices[index] = value;
6085     }
6086 }
6087
6088 /*************************************************************************
6089  * D3DXWeldVertices    (D3DX9_36.@)
6090  *
6091  * Welds together similar vertices. The similarity between vert-
6092  * ices can be the position and other components such as
6093  * normal and color.
6094  *
6095  * PARAMS
6096  *   mesh             [I] Mesh which vertices will be welded together.
6097  *   flags            [I] D3DXWELDEPSILONSFLAGS specifying how to weld.
6098  *   epsilons         [I] How similar a component needs to be for welding.
6099  *   adjacency        [I] Which faces are adjacent to other faces.
6100  *   adjacency_out    [O] Updated adjacency after welding.
6101  *   face_remap_out   [O] Which faces the old faces have been mapped to.
6102  *   vertex_remap_out [O] Which vertices the old vertices have been mapped to.
6103  *
6104  * RETURNS
6105  *   Success: D3D_OK.
6106  *   Failure: D3DERR_INVALIDCALL, E_OUTOFMEMORY.
6107  *
6108  * BUGS
6109  *   Attribute sorting not implemented.
6110  *
6111  */
6112 HRESULT WINAPI D3DXWeldVertices(LPD3DXMESH mesh,
6113                                 DWORD flags,
6114                                 CONST D3DXWELDEPSILONS *epsilons,
6115                                 CONST DWORD *adjacency,
6116                                 DWORD *adjacency_out,
6117                                 DWORD *face_remap_out,
6118                                 LPD3DXBUFFER *vertex_remap_out)
6119 {
6120     DWORD *adjacency_generated = NULL;
6121     const DWORD *adjacency_ptr;
6122     DWORD *attributes = NULL;
6123     const FLOAT DEFAULT_EPSILON = 1.0e-6f;
6124     HRESULT hr;
6125     DWORD i;
6126     void *indices = NULL;
6127     BOOL indices_are_32bit = mesh->lpVtbl->GetOptions(mesh) & D3DXMESH_32BIT;
6128     DWORD optimize_flags;
6129     DWORD *point_reps = NULL;
6130     ID3DXMeshImpl *This = impl_from_ID3DXMesh(mesh);
6131     DWORD *vertex_face_map = NULL;
6132     ID3DXBuffer *vertex_remap = NULL;
6133     BYTE *vertices = NULL;
6134
6135     TRACE("(%p, %x, %p, %p, %p, %p, %p)\n", mesh, flags, epsilons,
6136            adjacency, adjacency_out, face_remap_out, vertex_remap_out);
6137
6138     if (flags == 0)
6139     {
6140         WARN("No flags is undefined. Using D3DXWELDEPSILONS_WELDPARTIALMATCHES instead.\n");
6141         flags = D3DXWELDEPSILONS_WELDPARTIALMATCHES;
6142     }
6143
6144     if (adjacency) /* Use supplied adjacency. */
6145     {
6146         adjacency_ptr = adjacency;
6147     }
6148     else /* Adjacency has to be generated. */
6149     {
6150         adjacency_generated = HeapAlloc(GetProcessHeap(), 0, 3 * This->numfaces * sizeof(*adjacency_generated));
6151         if (!adjacency_generated)
6152         {
6153             ERR("Couldn't allocate memory for adjacency_generated.\n");
6154             hr = E_OUTOFMEMORY;
6155             goto cleanup;
6156         }
6157         hr = mesh->lpVtbl->GenerateAdjacency(mesh, DEFAULT_EPSILON, adjacency_generated);
6158         if (FAILED(hr))
6159         {
6160             ERR("Couldn't generate adjacency.\n");
6161             goto cleanup;
6162         }
6163         adjacency_ptr = adjacency_generated;
6164     }
6165
6166     /* Point representation says which vertices can be replaced. */
6167     point_reps = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*point_reps));
6168     if (!point_reps)
6169     {
6170         hr = E_OUTOFMEMORY;
6171         ERR("Couldn't allocate memory for point_reps.\n");
6172         goto cleanup;
6173     }
6174     hr = mesh->lpVtbl->ConvertAdjacencyToPointReps(mesh, adjacency_ptr, point_reps);
6175     if (FAILED(hr))
6176     {
6177         ERR("ConvertAdjacencyToPointReps failed.\n");
6178         goto cleanup;
6179     }
6180
6181     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, &indices);
6182     if (FAILED(hr))
6183     {
6184         ERR("Couldn't lock index buffer.\n");
6185         goto cleanup;
6186     }
6187
6188     hr = mesh->lpVtbl->LockAttributeBuffer(mesh, 0, &attributes);
6189     if (FAILED(hr))
6190     {
6191         ERR("Couldn't lock attribute buffer.\n");
6192         goto cleanup;
6193     }
6194     vertex_face_map = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*vertex_face_map));
6195     if (!vertex_face_map)
6196     {
6197         hr = E_OUTOFMEMORY;
6198         ERR("Couldn't allocate memory for vertex_face_map.\n");
6199         goto cleanup;
6200     }
6201     /* Build vertex face map, so that a vertex's face can be looked up. */
6202     for (i = 0; i < This->numfaces; i++)
6203     {
6204         DWORD j;
6205         for (j = 0; j < 3; j++)
6206         {
6207             DWORD index = read_ib(indices, indices_are_32bit, 3*i + j);
6208             vertex_face_map[index] = i;
6209         }
6210     }
6211
6212     if (flags & D3DXWELDEPSILONS_WELDPARTIALMATCHES)
6213     {
6214         hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (void**)&vertices);
6215         if (FAILED(hr))
6216         {
6217             ERR("Couldn't lock vertex buffer.\n");
6218             goto cleanup;
6219         }
6220         /* For each vertex that can be removed, compare its vertex components
6221          * with the vertex components from the vertex that can replace it. A
6222          * vertex is only fully replaced if all the components match and the
6223          * flag D3DXWELDEPSILONS_DONOTREMOVEVERTICES is not set, and they
6224          * belong to the same attribute group. Otherwise the vertex components
6225          * that are within epsilon are set to the same value.
6226          */
6227         for (i = 0; i < 3 * This->numfaces; i++)
6228         {
6229             D3DVERTEXELEMENT9 *decl_ptr;
6230             DWORD vertex_size = mesh->lpVtbl->GetNumBytesPerVertex(mesh);
6231             DWORD num_vertex_components;
6232             INT matches = 0;
6233             BOOL all_match;
6234             DWORD index = read_ib(indices, indices_are_32bit, i);
6235
6236             for (decl_ptr = This->cached_declaration, num_vertex_components = 0; decl_ptr->Stream != 0xFF; decl_ptr++, num_vertex_components++)
6237             {
6238                 BYTE *to = &vertices[vertex_size*index + decl_ptr->Offset];
6239                 BYTE *from = &vertices[vertex_size*point_reps[index] + decl_ptr->Offset];
6240                 FLOAT epsilon = get_component_epsilon(decl_ptr, epsilons);
6241
6242                 if (weld_component(to, from, decl_ptr->Type, epsilon))
6243                     matches++;
6244             }
6245
6246             all_match = (num_vertex_components == matches);
6247             if (all_match && !(flags & D3DXWELDEPSILONS_DONOTREMOVEVERTICES))
6248             {
6249                 DWORD to_face = vertex_face_map[index];
6250                 DWORD from_face = vertex_face_map[point_reps[index]];
6251                 if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6252                     continue;
6253                 write_ib(indices, indices_are_32bit, i, point_reps[index]);
6254             }
6255         }
6256         mesh->lpVtbl->UnlockVertexBuffer(mesh);
6257         vertices = NULL;
6258     }
6259     else if (flags & D3DXWELDEPSILONS_WELDALL)
6260     {
6261         for (i = 0; i < 3 * This->numfaces; i++)
6262         {
6263             DWORD index = read_ib(indices, indices_are_32bit, i);
6264             DWORD to_face = vertex_face_map[index];
6265             DWORD from_face = vertex_face_map[point_reps[index]];
6266             if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6267                 continue;
6268             write_ib(indices, indices_are_32bit, i, point_reps[index]);
6269         }
6270     }
6271     mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6272     attributes = NULL;
6273     mesh->lpVtbl->UnlockIndexBuffer(mesh);
6274     indices = NULL;
6275
6276     /* Compact mesh using OptimizeInplace */
6277     optimize_flags = D3DXMESHOPT_COMPACT;
6278     hr = mesh->lpVtbl->OptimizeInplace(mesh, optimize_flags, adjacency_ptr, adjacency_out, face_remap_out, vertex_remap_out);
6279     if (FAILED(hr))
6280     {
6281         ERR("Couldn't compact mesh.\n");
6282         goto cleanup;
6283     }
6284
6285     hr = D3D_OK;
6286 cleanup:
6287     HeapFree(GetProcessHeap(), 0, adjacency_generated);
6288     HeapFree(GetProcessHeap(), 0, point_reps);
6289     HeapFree(GetProcessHeap(), 0, vertex_face_map);
6290     if (attributes) mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6291     if (indices) mesh->lpVtbl->UnlockIndexBuffer(mesh);
6292     if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
6293     if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
6294
6295     return hr;
6296 }