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