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