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