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     D3DXVECTOR2 *tex_coords;
1835
1836     DWORD num_materials;
1837     D3DXMATERIAL *materials;
1838     DWORD *material_indices;
1839 };
1840
1841 static HRESULT get_next_child(IDirectXFileData *filedata, IDirectXFileData **child, const GUID **type)
1842 {
1843     HRESULT hr;
1844     IDirectXFileDataReference *child_ref = NULL;
1845     IDirectXFileObject *child_obj = NULL;
1846     IDirectXFileData *child_data = NULL;
1847
1848     hr = IDirectXFileData_GetNextObject(filedata, &child_obj);
1849     if (FAILED(hr)) return hr;
1850
1851     hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileDataReference, (void**)&child_ref);
1852     if (SUCCEEDED(hr)) {
1853         hr = IDirectXFileDataReference_Resolve(child_ref, &child_data);
1854         IDirectXFileDataReference_Release(child_ref);
1855     } else {
1856         hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileData, (void**)&child_data);
1857     }
1858     IDirectXFileObject_Release(child_obj);
1859     if (FAILED(hr))
1860         return hr;
1861
1862     hr = IDirectXFileData_GetType(child_data, type);
1863     if (FAILED(hr)) {
1864         IDirectXFileData_Release(child_data);
1865     } else {
1866         *child = child_data;
1867     }
1868
1869     return hr;
1870 }
1871
1872 static HRESULT parse_texture_filename(IDirectXFileData *filedata, LPSTR *filename_out)
1873 {
1874     HRESULT hr;
1875     DWORD data_size;
1876     BYTE *data;
1877     char *filename_in;
1878     char *filename = NULL;
1879
1880     /* template TextureFilename {
1881      *     STRING filename;
1882      * }
1883      */
1884
1885     HeapFree(GetProcessHeap(), 0, *filename_out);
1886     *filename_out = NULL;
1887
1888     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
1889     if (FAILED(hr)) return hr;
1890
1891     if (data_size < sizeof(LPSTR)) {
1892         WARN("truncated data (%u bytes)\n", data_size);
1893         return E_FAIL;
1894     }
1895     filename_in = *(LPSTR*)data;
1896
1897     filename = HeapAlloc(GetProcessHeap(), 0, strlen(filename_in) + 1);
1898     if (!filename) return E_OUTOFMEMORY;
1899
1900     strcpy(filename, filename_in);
1901     *filename_out = filename;
1902
1903     return D3D_OK;
1904 }
1905
1906 static HRESULT parse_material(IDirectXFileData *filedata, D3DXMATERIAL *material)
1907 {
1908     HRESULT hr;
1909     DWORD data_size;
1910     BYTE *data;
1911     const GUID *type;
1912     IDirectXFileData *child;
1913
1914     material->pTextureFilename = NULL;
1915
1916     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
1917     if (FAILED(hr)) return hr;
1918
1919     /*
1920      * template ColorRGBA {
1921      *     FLOAT red;
1922      *     FLOAT green;
1923      *     FLOAT blue;
1924      *     FLOAT alpha;
1925      * }
1926      * template ColorRGB {
1927      *     FLOAT red;
1928      *     FLOAT green;
1929      *     FLOAT blue;
1930      * }
1931      * template Material {
1932      *     ColorRGBA faceColor;
1933      *     FLOAT power;
1934      *     ColorRGB specularColor;
1935      *     ColorRGB emissiveColor;
1936      *     [ ... ]
1937      * }
1938      */
1939     if (data_size != sizeof(FLOAT) * 11) {
1940         WARN("incorrect data size (%u bytes)\n", data_size);
1941         return E_FAIL;
1942     }
1943
1944     memcpy(&material->MatD3D.Diffuse, data, sizeof(D3DCOLORVALUE));
1945     data += sizeof(D3DCOLORVALUE);
1946     material->MatD3D.Power = *(FLOAT*)data;
1947     data += sizeof(FLOAT);
1948     memcpy(&material->MatD3D.Specular, data, sizeof(FLOAT) * 3);
1949     material->MatD3D.Specular.a = 1.0f;
1950     data += 3 * sizeof(FLOAT);
1951     memcpy(&material->MatD3D.Emissive, data, sizeof(FLOAT) * 3);
1952     material->MatD3D.Emissive.a = 1.0f;
1953     material->MatD3D.Ambient.r = 0.0f;
1954     material->MatD3D.Ambient.g = 0.0f;
1955     material->MatD3D.Ambient.b = 0.0f;
1956     material->MatD3D.Ambient.a = 1.0f;
1957
1958     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
1959     {
1960         if (IsEqualGUID(type, &TID_D3DRMTextureFilename)) {
1961             hr = parse_texture_filename(child, &material->pTextureFilename);
1962             if (FAILED(hr)) break;
1963         }
1964     }
1965     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
1966 }
1967
1968 static void destroy_materials(struct mesh_data *mesh)
1969 {
1970     int i;
1971     for (i = 0; i < mesh->num_materials; i++)
1972         HeapFree(GetProcessHeap(), 0, mesh->materials[i].pTextureFilename);
1973     HeapFree(GetProcessHeap(), 0, mesh->materials);
1974     HeapFree(GetProcessHeap(), 0, mesh->material_indices);
1975     mesh->num_materials = 0;
1976     mesh->materials = NULL;
1977     mesh->material_indices = NULL;
1978 }
1979
1980 static HRESULT parse_material_list(IDirectXFileData *filedata, struct mesh_data *mesh)
1981 {
1982     HRESULT hr;
1983     DWORD data_size;
1984     DWORD *data, *in_ptr;
1985     const GUID *type;
1986     IDirectXFileData *child;
1987     DWORD num_materials;
1988     int i;
1989
1990     destroy_materials(mesh);
1991
1992     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
1993     if (FAILED(hr)) return hr;
1994
1995     /* template MeshMaterialList {
1996      *     DWORD nMaterials;
1997      *     DWORD nFaceIndexes;
1998      *     array DWORD faceIndexes[nFaceIndexes];
1999      *     [ Material ]
2000      * }
2001      */
2002
2003     in_ptr = data;
2004
2005     if (data_size < sizeof(DWORD))
2006         goto truncated_data_error;
2007     num_materials = *in_ptr++;
2008     if (!num_materials)
2009         return D3D_OK;
2010
2011     if (data_size < 2 * sizeof(DWORD))
2012         goto truncated_data_error;
2013     if (*in_ptr++ != mesh->num_poly_faces) {
2014         WARN("number of material face indices (%u) doesn't match number of faces (%u)\n",
2015              *(in_ptr - 1), mesh->num_poly_faces);
2016         return E_FAIL;
2017     }
2018     if (data_size < 2 * sizeof(DWORD) + mesh->num_poly_faces * sizeof(DWORD))
2019         goto truncated_data_error;
2020     for (i = 0; i < mesh->num_poly_faces; i++) {
2021         if (*in_ptr++ >= num_materials) {
2022             WARN("face %u: reference to undefined material %u (only %u materials)\n",
2023                  i, *(in_ptr - 1), num_materials);
2024             return E_FAIL;
2025         }
2026     }
2027
2028     mesh->materials = HeapAlloc(GetProcessHeap(), 0, num_materials * sizeof(*mesh->materials));
2029     mesh->material_indices = HeapAlloc(GetProcessHeap(), 0, mesh->num_poly_faces * sizeof(*mesh->material_indices));
2030     if (!mesh->materials || !mesh->material_indices)
2031         return E_OUTOFMEMORY;
2032     memcpy(mesh->material_indices, data + 2, mesh->num_poly_faces * sizeof(DWORD));
2033
2034     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2035     {
2036         if (IsEqualGUID(type, &TID_D3DRMMaterial)) {
2037             if (mesh->num_materials >= num_materials) {
2038                 WARN("more materials defined than declared\n");
2039                 return E_FAIL;
2040             }
2041             hr = parse_material(child, &mesh->materials[mesh->num_materials++]);
2042             if (FAILED(hr)) break;
2043         }
2044     }
2045     if (hr != DXFILEERR_NOMOREOBJECTS)
2046         return hr;
2047     if (num_materials != mesh->num_materials) {
2048         WARN("only %u of %u materials defined\n", num_materials, mesh->num_materials);
2049         return E_FAIL;
2050     }
2051
2052     return D3D_OK;
2053 truncated_data_error:
2054     WARN("truncated data (%u bytes)\n", data_size);
2055     return E_FAIL;
2056 }
2057
2058 static HRESULT parse_texture_coords(IDirectXFileData *filedata, struct mesh_data *mesh)
2059 {
2060     HRESULT hr;
2061     DWORD data_size;
2062     BYTE *data;
2063
2064     HeapFree(GetProcessHeap(), 0, mesh->tex_coords);
2065     mesh->tex_coords = NULL;
2066
2067     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2068     if (FAILED(hr)) return hr;
2069
2070     /* template Coords2d {
2071      *     FLOAT u;
2072      *     FLOAT v;
2073      * }
2074      * template MeshTextureCoords {
2075      *     DWORD nTextureCoords;
2076      *     array Coords2d textureCoords[nTextureCoords];
2077      * }
2078      */
2079
2080     if (data_size < sizeof(DWORD))
2081         goto truncated_data_error;
2082     if (*(DWORD*)data != mesh->num_vertices) {
2083         WARN("number of texture coordinates (%u) doesn't match number of vertices (%u)\n",
2084              *(DWORD*)data, mesh->num_vertices);
2085         return E_FAIL;
2086     }
2087     data += sizeof(DWORD);
2088     if (data_size < sizeof(DWORD) + mesh->num_vertices * sizeof(*mesh->tex_coords))
2089         goto truncated_data_error;
2090
2091     mesh->tex_coords = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(*mesh->tex_coords));
2092     if (!mesh->tex_coords) return E_OUTOFMEMORY;
2093     memcpy(mesh->tex_coords, data, mesh->num_vertices * sizeof(*mesh->tex_coords));
2094
2095     mesh->fvf |= D3DFVF_TEX1;
2096
2097     return D3D_OK;
2098 truncated_data_error:
2099     WARN("truncated data (%u bytes)\n", data_size);
2100     return E_FAIL;
2101 }
2102
2103 static HRESULT parse_normals(IDirectXFileData *filedata, struct mesh_data *mesh)
2104 {
2105     HRESULT hr;
2106     DWORD data_size;
2107     BYTE *data;
2108     DWORD *index_out_ptr;
2109     int i;
2110     DWORD num_face_indices = mesh->num_poly_faces * 2 + mesh->num_tri_faces;
2111
2112     HeapFree(GetProcessHeap(), 0, mesh->normals);
2113     mesh->num_normals = 0;
2114     mesh->normals = NULL;
2115     mesh->normal_indices = NULL;
2116     mesh->fvf |= D3DFVF_NORMAL;
2117
2118     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2119     if (FAILED(hr)) return hr;
2120
2121     /* template Vector {
2122      *     FLOAT x;
2123      *     FLOAT y;
2124      *     FLOAT z;
2125      * }
2126      * template MeshFace {
2127      *     DWORD nFaceVertexIndices;
2128      *     array DWORD faceVertexIndices[nFaceVertexIndices];
2129      * }
2130      * template MeshNormals {
2131      *     DWORD nNormals;
2132      *     array Vector normals[nNormals];
2133      *     DWORD nFaceNormals;
2134      *     array MeshFace faceNormals[nFaceNormals];
2135      * }
2136      */
2137
2138     if (data_size < sizeof(DWORD) * 2)
2139         goto truncated_data_error;
2140     mesh->num_normals = *(DWORD*)data;
2141     data += sizeof(DWORD);
2142     if (data_size < sizeof(DWORD) * 2 + mesh->num_normals * sizeof(D3DXVECTOR3) +
2143                     num_face_indices * sizeof(DWORD))
2144         goto truncated_data_error;
2145
2146     mesh->normals = HeapAlloc(GetProcessHeap(), 0, mesh->num_normals * sizeof(D3DXVECTOR3));
2147     mesh->normal_indices = HeapAlloc(GetProcessHeap(), 0, num_face_indices * sizeof(DWORD));
2148     if (!mesh->normals || !mesh->normal_indices)
2149         return E_OUTOFMEMORY;
2150
2151     memcpy(mesh->normals, data, mesh->num_normals * sizeof(D3DXVECTOR3));
2152     data += mesh->num_normals * sizeof(D3DXVECTOR3);
2153     for (i = 0; i < mesh->num_normals; i++)
2154         D3DXVec3Normalize(&mesh->normals[i], &mesh->normals[i]);
2155
2156     if (*(DWORD*)data != mesh->num_poly_faces) {
2157         WARN("number of face normals (%u) doesn't match number of faces (%u)\n",
2158              *(DWORD*)data, mesh->num_poly_faces);
2159         return E_FAIL;
2160     }
2161     data += sizeof(DWORD);
2162     index_out_ptr = mesh->normal_indices;
2163     for (i = 0; i < mesh->num_poly_faces; i++)
2164     {
2165         DWORD j;
2166         DWORD count = *(DWORD*)data;
2167         if (count != mesh->num_tri_per_face[i] + 2) {
2168             WARN("face %u: number of normals (%u) doesn't match number of vertices (%u)\n",
2169                  i, count, mesh->num_tri_per_face[i] + 2);
2170             return E_FAIL;
2171         }
2172         data += sizeof(DWORD);
2173
2174         for (j = 0; j < count; j++) {
2175             DWORD normal_index = *(DWORD*)data;
2176             if (normal_index >= mesh->num_normals) {
2177                 WARN("face %u, normal index %u: reference to undefined normal %u (only %u normals)\n",
2178                      i, j, normal_index, mesh->num_normals);
2179                 return E_FAIL;
2180             }
2181             *index_out_ptr++ = normal_index;
2182             data += sizeof(DWORD);
2183         }
2184     }
2185
2186     return D3D_OK;
2187 truncated_data_error:
2188     WARN("truncated data (%u bytes)\n", data_size);
2189     return E_FAIL;
2190 }
2191
2192 /* for provide_flags parameters */
2193 #define PROVIDE_MATERIALS 0x1
2194 #define PROVIDE_SKININFO  0x2
2195
2196 static HRESULT parse_mesh(IDirectXFileData *filedata, struct mesh_data *mesh_data, DWORD provide_flags)
2197 {
2198     HRESULT hr;
2199     DWORD data_size;
2200     BYTE *data, *in_ptr;
2201     DWORD *index_out_ptr;
2202     const GUID *type;
2203     IDirectXFileData *child;
2204     int i;
2205
2206     /*
2207      * template Mesh {
2208      *     DWORD nVertices;
2209      *     array Vector vertices[nVertices];
2210      *     DWORD nFaces;
2211      *     array MeshFace faces[nFaces];
2212      *     [ ... ]
2213      * }
2214      */
2215
2216     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2217     if (FAILED(hr)) return hr;
2218
2219     in_ptr = data;
2220     if (data_size < sizeof(DWORD) * 2)
2221         goto truncated_data_error;
2222     mesh_data->num_vertices = *(DWORD*)in_ptr;
2223     if (data_size < sizeof(DWORD) * 2 + mesh_data->num_vertices * sizeof(D3DXVECTOR3))
2224         goto truncated_data_error;
2225     in_ptr += sizeof(DWORD) + mesh_data->num_vertices * sizeof(D3DXVECTOR3);
2226
2227     mesh_data->num_poly_faces = *(DWORD*)in_ptr;
2228     in_ptr += sizeof(DWORD);
2229
2230     mesh_data->num_tri_faces = 0;
2231     for (i = 0; i < mesh_data->num_poly_faces; i++)
2232     {
2233         DWORD num_poly_vertices;
2234         DWORD j;
2235
2236         if (data_size - (in_ptr - data) < sizeof(DWORD))
2237             goto truncated_data_error;
2238         num_poly_vertices = *(DWORD*)in_ptr;
2239         in_ptr += sizeof(DWORD);
2240         if (data_size - (in_ptr - data) < num_poly_vertices * sizeof(DWORD))
2241             goto truncated_data_error;
2242         if (num_poly_vertices < 3) {
2243             WARN("face %u has only %u vertices\n", i, num_poly_vertices);
2244             return E_FAIL;
2245         }
2246         for (j = 0; j < num_poly_vertices; j++) {
2247             if (*(DWORD*)in_ptr >= mesh_data->num_vertices) {
2248                 WARN("face %u, index %u: undefined vertex %u (only %u vertices)\n",
2249                      i, j, *(DWORD*)in_ptr, mesh_data->num_vertices);
2250                 return E_FAIL;
2251             }
2252             in_ptr += sizeof(DWORD);
2253         }
2254         mesh_data->num_tri_faces += num_poly_vertices - 2;
2255     }
2256
2257     mesh_data->fvf = D3DFVF_XYZ;
2258
2259     mesh_data->vertices = HeapAlloc(GetProcessHeap(), 0,
2260             mesh_data->num_vertices * sizeof(*mesh_data->vertices));
2261     mesh_data->num_tri_per_face = HeapAlloc(GetProcessHeap(), 0,
2262             mesh_data->num_poly_faces * sizeof(*mesh_data->num_tri_per_face));
2263     mesh_data->indices = HeapAlloc(GetProcessHeap(), 0,
2264             (mesh_data->num_tri_faces + mesh_data->num_poly_faces * 2) * sizeof(*mesh_data->indices));
2265     if (!mesh_data->vertices || !mesh_data->num_tri_per_face || !mesh_data->indices)
2266         return E_OUTOFMEMORY;
2267
2268     in_ptr = data + sizeof(DWORD);
2269     memcpy(mesh_data->vertices, in_ptr, mesh_data->num_vertices * sizeof(D3DXVECTOR3));
2270     in_ptr += mesh_data->num_vertices * sizeof(D3DXVECTOR3) + sizeof(DWORD);
2271
2272     index_out_ptr = mesh_data->indices;
2273     for (i = 0; i < mesh_data->num_poly_faces; i++)
2274     {
2275         DWORD count;
2276
2277         count = *(DWORD*)in_ptr;
2278         in_ptr += sizeof(DWORD);
2279         mesh_data->num_tri_per_face[i] = count - 2;
2280
2281         while (count--) {
2282             *index_out_ptr++ = *(DWORD*)in_ptr;
2283             in_ptr += sizeof(DWORD);
2284         }
2285     }
2286
2287     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2288     {
2289         if (IsEqualGUID(type, &TID_D3DRMMeshNormals)) {
2290             hr = parse_normals(child, mesh_data);
2291         } else if (IsEqualGUID(type, &TID_D3DRMMeshVertexColors)) {
2292             FIXME("Mesh vertex color loading not implemented.\n");
2293             hr = E_NOTIMPL;
2294         } else if (IsEqualGUID(type, &TID_D3DRMMeshTextureCoords)) {
2295             hr = parse_texture_coords(child, mesh_data);
2296         } else if (IsEqualGUID(type, &TID_D3DRMMeshMaterialList) &&
2297                    (provide_flags & PROVIDE_MATERIALS))
2298         {
2299             hr = parse_material_list(child, mesh_data);
2300         } else if (provide_flags & PROVIDE_SKININFO) {
2301             if (IsEqualGUID(type, &DXFILEOBJ_XSkinMeshHeader)) {
2302                 FIXME("Skin mesh loading not implemented.\n");
2303                 hr = E_NOTIMPL;
2304             } else if (IsEqualGUID(type, &DXFILEOBJ_SkinWeights)) {
2305                 /* ignored without XSkinMeshHeader */
2306             }
2307         }
2308         if (FAILED(hr))
2309             break;
2310     }
2311     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
2312 truncated_data_error:
2313     WARN("truncated data (%u bytes)\n", data_size);
2314     return E_FAIL;
2315 }
2316
2317 static HRESULT generate_effects(ID3DXBuffer *materials, DWORD num_materials,
2318                                 ID3DXBuffer **effects)
2319 {
2320     HRESULT hr;
2321     D3DXEFFECTINSTANCE *effect_ptr;
2322     BYTE *out_ptr;
2323     const D3DXMATERIAL *material_ptr = ID3DXBuffer_GetBufferPointer(materials);
2324     static const struct {
2325         const char *param_name;
2326         DWORD name_size;
2327         DWORD num_bytes;
2328         DWORD value_offset;
2329     } material_effects[] = {
2330 #define EFFECT_TABLE_ENTRY(str, field) \
2331     {str, sizeof(str), sizeof(material_ptr->MatD3D.field), offsetof(D3DXMATERIAL, MatD3D.field)}
2332         EFFECT_TABLE_ENTRY("Diffuse", Diffuse),
2333         EFFECT_TABLE_ENTRY("Power", Power),
2334         EFFECT_TABLE_ENTRY("Specular", Specular),
2335         EFFECT_TABLE_ENTRY("Emissive", Emissive),
2336         EFFECT_TABLE_ENTRY("Ambient", Ambient),
2337 #undef EFFECT_TABLE_ENTRY
2338     };
2339     static const char texture_paramname[] = "Texture0@Name";
2340     DWORD buffer_size;
2341     int i;
2342
2343     /* effects buffer layout:
2344      *
2345      * D3DXEFFECTINSTANCE effects[num_materials];
2346      * for (effect in effects)
2347      * {
2348      *     D3DXEFFECTDEFAULT defaults[effect.NumDefaults];
2349      *     for (default in defaults)
2350      *     {
2351      *         *default.pParamName;
2352      *         *default.pValue;
2353      *     }
2354      * }
2355      */
2356     buffer_size = sizeof(D3DXEFFECTINSTANCE);
2357     buffer_size += sizeof(D3DXEFFECTDEFAULT) * ARRAY_SIZE(material_effects);
2358     for (i = 0; i < ARRAY_SIZE(material_effects); i++) {
2359         buffer_size += material_effects[i].name_size;
2360         buffer_size += material_effects[i].num_bytes;
2361     }
2362     buffer_size *= num_materials;
2363     for (i = 0; i < num_materials; i++) {
2364         if (material_ptr[i].pTextureFilename) {
2365             buffer_size += sizeof(D3DXEFFECTDEFAULT);
2366             buffer_size += sizeof(texture_paramname);
2367             buffer_size += strlen(material_ptr[i].pTextureFilename) + 1;
2368         }
2369     }
2370
2371     hr = D3DXCreateBuffer(buffer_size, effects);
2372     if (FAILED(hr)) return hr;
2373     effect_ptr = ID3DXBuffer_GetBufferPointer(*effects);
2374     out_ptr = (BYTE*)(effect_ptr + num_materials);
2375
2376     for (i = 0; i < num_materials; i++)
2377     {
2378         int j;
2379         D3DXEFFECTDEFAULT *defaults = (D3DXEFFECTDEFAULT*)out_ptr;
2380
2381         effect_ptr->pDefaults = defaults;
2382         effect_ptr->NumDefaults = material_ptr->pTextureFilename ? 6 : 5;
2383         out_ptr = (BYTE*)(effect_ptr->pDefaults + effect_ptr->NumDefaults);
2384
2385         for (j = 0; j < ARRAY_SIZE(material_effects); j++)
2386         {
2387             defaults->pParamName = (LPSTR)out_ptr;
2388             strcpy(defaults->pParamName, material_effects[j].param_name);
2389             defaults->pValue = defaults->pParamName + material_effects[j].name_size;
2390             defaults->Type = D3DXEDT_FLOATS;
2391             defaults->NumBytes = material_effects[j].num_bytes;
2392             memcpy(defaults->pValue, (BYTE*)material_ptr + material_effects[j].value_offset, defaults->NumBytes);
2393             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
2394             defaults++;
2395         }
2396
2397         if (material_ptr->pTextureFilename) {
2398             defaults->pParamName = (LPSTR)out_ptr;
2399             strcpy(defaults->pParamName, texture_paramname);
2400             defaults->pValue = defaults->pParamName + sizeof(texture_paramname);
2401             defaults->Type = D3DXEDT_STRING;
2402             defaults->NumBytes = strlen(material_ptr->pTextureFilename) + 1;
2403             strcpy(defaults->pValue, material_ptr->pTextureFilename);
2404             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
2405         }
2406         material_ptr++;
2407         effect_ptr++;
2408     }
2409     assert(out_ptr - (BYTE*)ID3DXBuffer_GetBufferPointer(*effects) == buffer_size);
2410
2411     return D3D_OK;
2412 }
2413
2414 /* change to D3DXLoadSkinMeshFromXof when ID3DXFileData is implemented */
2415 static HRESULT load_skin_mesh_from_xof(IDirectXFileData *filedata,
2416                                        DWORD options,
2417                                        LPDIRECT3DDEVICE9 device,
2418                                        LPD3DXBUFFER *adjacency_out,
2419                                        LPD3DXBUFFER *materials_out,
2420                                        LPD3DXBUFFER *effects_out,
2421                                        DWORD *num_materials_out,
2422                                        LPD3DXSKININFO *skin_info_out,
2423                                        LPD3DXMESH *mesh_out)
2424 {
2425     HRESULT hr;
2426     DWORD *index_in_ptr;
2427     struct mesh_data mesh_data;
2428     DWORD total_vertices;
2429     ID3DXMesh *d3dxmesh = NULL;
2430     ID3DXBuffer *adjacency = NULL;
2431     ID3DXBuffer *materials = NULL;
2432     ID3DXBuffer *effects = NULL;
2433     struct vertex_duplication {
2434         DWORD normal_index;
2435         struct list entry;
2436     } *duplications = NULL;
2437     int i;
2438     void *vertices = NULL;
2439     void *indices = NULL;
2440     BYTE *out_ptr;
2441     DWORD provide_flags = 0;
2442
2443     ZeroMemory(&mesh_data, sizeof(mesh_data));
2444
2445     if (num_materials_out || materials_out || effects_out)
2446         provide_flags |= PROVIDE_MATERIALS;
2447     if (skin_info_out)
2448         provide_flags |= PROVIDE_SKININFO;
2449
2450     hr = parse_mesh(filedata, &mesh_data, provide_flags);
2451     if (FAILED(hr)) goto cleanup;
2452
2453     total_vertices = mesh_data.num_vertices;
2454     if (mesh_data.fvf & D3DFVF_NORMAL) {
2455         /* duplicate vertices with multiple normals */
2456         DWORD num_face_indices = mesh_data.num_poly_faces * 2 + mesh_data.num_tri_faces;
2457         duplications = HeapAlloc(GetProcessHeap(), 0, (mesh_data.num_vertices + num_face_indices) * sizeof(*duplications));
2458         if (!duplications) {
2459             hr = E_OUTOFMEMORY;
2460             goto cleanup;
2461         }
2462         for (i = 0; i < total_vertices; i++)
2463         {
2464             duplications[i].normal_index = -1;
2465             list_init(&duplications[i].entry);
2466         }
2467         for (i = 0; i < num_face_indices; i++) {
2468             DWORD vertex_index = mesh_data.indices[i];
2469             DWORD normal_index = mesh_data.normal_indices[i];
2470             struct vertex_duplication *dup_ptr = &duplications[vertex_index];
2471
2472             if (dup_ptr->normal_index == -1) {
2473                 dup_ptr->normal_index = normal_index;
2474             } else {
2475                 D3DXVECTOR3 *new_normal = &mesh_data.normals[normal_index];
2476                 struct list *dup_list = &dup_ptr->entry;
2477                 while (TRUE) {
2478                     D3DXVECTOR3 *cur_normal = &mesh_data.normals[dup_ptr->normal_index];
2479                     if (new_normal->x == cur_normal->x &&
2480                         new_normal->y == cur_normal->y &&
2481                         new_normal->z == cur_normal->z)
2482                     {
2483                         mesh_data.indices[i] = dup_ptr - duplications;
2484                         break;
2485                     } else if (!list_next(dup_list, &dup_ptr->entry)) {
2486                         dup_ptr = &duplications[total_vertices++];
2487                         dup_ptr->normal_index = normal_index;
2488                         list_add_tail(dup_list, &dup_ptr->entry);
2489                         mesh_data.indices[i] = dup_ptr - duplications;
2490                         break;
2491                     } else {
2492                         dup_ptr = LIST_ENTRY(list_next(dup_list, &dup_ptr->entry),
2493                                              struct vertex_duplication, entry);
2494                     }
2495                 }
2496             }
2497         }
2498     }
2499
2500     hr = D3DXCreateMeshFVF(mesh_data.num_tri_faces, total_vertices, options, mesh_data.fvf, device, &d3dxmesh);
2501     if (FAILED(hr)) goto cleanup;
2502
2503     hr = d3dxmesh->lpVtbl->LockVertexBuffer(d3dxmesh, D3DLOCK_DISCARD, &vertices);
2504     if (FAILED(hr)) goto cleanup;
2505
2506     out_ptr = vertices;
2507     for (i = 0; i < mesh_data.num_vertices; i++) {
2508         *(D3DXVECTOR3*)out_ptr = mesh_data.vertices[i];
2509         out_ptr += sizeof(D3DXVECTOR3);
2510         if (mesh_data.fvf & D3DFVF_NORMAL) {
2511             if (duplications[i].normal_index == -1)
2512                 ZeroMemory(out_ptr, sizeof(D3DXVECTOR3));
2513             else
2514                 *(D3DXVECTOR3*)out_ptr = mesh_data.normals[duplications[i].normal_index];
2515             out_ptr += sizeof(D3DXVECTOR3);
2516         }
2517         if (mesh_data.fvf & D3DFVF_TEX1) {
2518             *(D3DXVECTOR2*)out_ptr = mesh_data.tex_coords[i];
2519             out_ptr += sizeof(D3DXVECTOR2);
2520         }
2521     }
2522     if (mesh_data.fvf & D3DFVF_NORMAL) {
2523         DWORD vertex_size = D3DXGetFVFVertexSize(mesh_data.fvf);
2524         out_ptr = vertices;
2525         for (i = 0; i < mesh_data.num_vertices; i++) {
2526             struct vertex_duplication *dup_ptr;
2527             LIST_FOR_EACH_ENTRY(dup_ptr, &duplications[i].entry, struct vertex_duplication, entry)
2528             {
2529                 int j = dup_ptr - duplications;
2530                 BYTE *dest_vertex = (BYTE*)vertices + j * vertex_size;
2531
2532                 memcpy(dest_vertex, out_ptr, vertex_size);
2533                 dest_vertex += sizeof(D3DXVECTOR3);
2534                 *(D3DXVECTOR3*)dest_vertex = mesh_data.normals[dup_ptr->normal_index];
2535             }
2536             out_ptr += vertex_size;
2537         }
2538     }
2539     d3dxmesh->lpVtbl->UnlockVertexBuffer(d3dxmesh);
2540
2541     hr = d3dxmesh->lpVtbl->LockIndexBuffer(d3dxmesh, D3DLOCK_DISCARD, (void**)&indices);
2542     if (FAILED(hr)) goto cleanup;
2543
2544     index_in_ptr = mesh_data.indices;
2545 #define FILL_INDEX_BUFFER(indices_var) \
2546         for (i = 0; i < mesh_data.num_poly_faces; i++) \
2547         { \
2548             DWORD count = mesh_data.num_tri_per_face[i]; \
2549             WORD first_index = *index_in_ptr++; \
2550             while (count--) { \
2551                 *indices_var++ = first_index; \
2552                 *indices_var++ = *index_in_ptr; \
2553                 index_in_ptr++; \
2554                 *indices_var++ = *index_in_ptr; \
2555             } \
2556             index_in_ptr++; \
2557         }
2558     if (options & D3DXMESH_32BIT) {
2559         DWORD *dword_indices = indices;
2560         FILL_INDEX_BUFFER(dword_indices)
2561     } else {
2562         WORD *word_indices = indices;
2563         FILL_INDEX_BUFFER(word_indices)
2564     }
2565 #undef FILL_INDEX_BUFFER
2566     d3dxmesh->lpVtbl->UnlockIndexBuffer(d3dxmesh);
2567
2568     if (mesh_data.material_indices) {
2569         DWORD *attrib_buffer = NULL;
2570         hr = d3dxmesh->lpVtbl->LockAttributeBuffer(d3dxmesh, D3DLOCK_DISCARD, &attrib_buffer);
2571         if (FAILED(hr)) goto cleanup;
2572         for (i = 0; i < mesh_data.num_poly_faces; i++)
2573         {
2574             DWORD count = mesh_data.num_tri_per_face[i];
2575             while (count--)
2576                 *attrib_buffer++ = mesh_data.material_indices[i];
2577         }
2578         d3dxmesh->lpVtbl->UnlockAttributeBuffer(d3dxmesh);
2579
2580         hr = d3dxmesh->lpVtbl->OptimizeInplace(d3dxmesh,
2581                 D3DXMESHOPT_ATTRSORT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_DONOTSPLIT,
2582                 NULL, NULL, NULL, NULL);
2583         if (FAILED(hr)) goto cleanup;
2584     }
2585
2586     if (mesh_data.num_materials && (materials_out || effects_out)) {
2587         DWORD buffer_size = mesh_data.num_materials * sizeof(D3DXMATERIAL);
2588         char *strings_out_ptr;
2589         D3DXMATERIAL *materials_ptr;
2590
2591         for (i = 0; i < mesh_data.num_materials; i++) {
2592             if (mesh_data.materials[i].pTextureFilename)
2593                 buffer_size += strlen(mesh_data.materials[i].pTextureFilename) + 1;
2594         }
2595
2596         hr = D3DXCreateBuffer(buffer_size, &materials);
2597         if (FAILED(hr)) goto cleanup;
2598
2599         materials_ptr = ID3DXBuffer_GetBufferPointer(materials);
2600         memcpy(materials_ptr, mesh_data.materials, mesh_data.num_materials * sizeof(D3DXMATERIAL));
2601         strings_out_ptr = (char*)(materials_ptr + mesh_data.num_materials);
2602         for (i = 0; i < mesh_data.num_materials; i++) {
2603             if (materials_ptr[i].pTextureFilename) {
2604                 strcpy(strings_out_ptr, mesh_data.materials[i].pTextureFilename);
2605                 materials_ptr[i].pTextureFilename = strings_out_ptr;
2606                 strings_out_ptr += strlen(mesh_data.materials[i].pTextureFilename) + 1;
2607             }
2608         }
2609     }
2610
2611     if (mesh_data.num_materials && effects_out) {
2612         hr = generate_effects(materials, mesh_data.num_materials, &effects);
2613         if (FAILED(hr)) goto cleanup;
2614
2615         if (!materials_out) {
2616             ID3DXBuffer_Release(materials);
2617             materials = NULL;
2618         }
2619     }
2620
2621     if (adjacency_out) {
2622         hr = D3DXCreateBuffer(mesh_data.num_tri_faces * 3 * sizeof(DWORD), &adjacency);
2623         if (FAILED(hr)) goto cleanup;
2624         hr = d3dxmesh->lpVtbl->GenerateAdjacency(d3dxmesh, 0.0f, ID3DXBuffer_GetBufferPointer(adjacency));
2625         if (FAILED(hr)) goto cleanup;
2626     }
2627
2628     *mesh_out = d3dxmesh;
2629     if (adjacency_out) *adjacency_out = adjacency;
2630     if (num_materials_out) *num_materials_out = mesh_data.num_materials;
2631     if (materials_out) *materials_out = materials;
2632     if (effects_out) *effects_out = effects;
2633     if (skin_info_out) *skin_info_out = NULL;
2634
2635     hr = D3D_OK;
2636 cleanup:
2637     if (FAILED(hr)) {
2638         if (d3dxmesh) IUnknown_Release(d3dxmesh);
2639         if (adjacency) ID3DXBuffer_Release(adjacency);
2640         if (materials) ID3DXBuffer_Release(materials);
2641         if (effects) ID3DXBuffer_Release(effects);
2642     }
2643     HeapFree(GetProcessHeap(), 0, mesh_data.vertices);
2644     HeapFree(GetProcessHeap(), 0, mesh_data.num_tri_per_face);
2645     HeapFree(GetProcessHeap(), 0, mesh_data.indices);
2646     HeapFree(GetProcessHeap(), 0, mesh_data.normals);
2647     HeapFree(GetProcessHeap(), 0, mesh_data.normal_indices);
2648     destroy_materials(&mesh_data);
2649     HeapFree(GetProcessHeap(), 0, mesh_data.tex_coords);
2650     HeapFree(GetProcessHeap(), 0, duplications);
2651     return hr;
2652 }
2653
2654 static HRESULT filedata_get_name(IDirectXFileData *filedata, char **name)
2655 {
2656     HRESULT hr;
2657     DWORD name_len;
2658
2659     hr = IDirectXFileData_GetName(filedata, NULL, &name_len);
2660     if (FAILED(hr)) return hr;
2661
2662     if (!name_len)
2663         name_len++;
2664     *name = HeapAlloc(GetProcessHeap(), 0, name_len);
2665     if (!*name) return E_OUTOFMEMORY;
2666
2667     hr = IDirectXFileObject_GetName(filedata, *name, &name_len);
2668     if (FAILED(hr))
2669         HeapFree(GetProcessHeap(), 0, name);
2670     if (!name_len)
2671         (*name)[0] = 0;
2672
2673     return hr;
2674 }
2675
2676 static HRESULT load_mesh_container(IDirectXFileData *filedata,
2677                                    DWORD options,
2678                                    LPDIRECT3DDEVICE9 device,
2679                                    LPD3DXALLOCATEHIERARCHY alloc_hier,
2680                                    D3DXMESHCONTAINER **mesh_container)
2681 {
2682     HRESULT hr;
2683     ID3DXBuffer *adjacency = NULL;
2684     ID3DXBuffer *materials = NULL;
2685     ID3DXBuffer *effects = NULL;
2686     ID3DXSkinInfo *skin_info = NULL;
2687     D3DXMESHDATA mesh_data;
2688     DWORD num_materials = 0;
2689     char *name = NULL;
2690
2691     mesh_data.Type = D3DXMESHTYPE_MESH;
2692     mesh_data.u.pMesh = NULL;
2693
2694     hr = load_skin_mesh_from_xof(filedata, options, device,
2695             &adjacency, &materials, &effects, &num_materials,
2696             &skin_info, &mesh_data.u.pMesh);
2697     if (FAILED(hr)) return hr;
2698
2699     hr = filedata_get_name(filedata, &name);
2700     if (FAILED(hr)) goto cleanup;
2701
2702     hr = alloc_hier->lpVtbl->CreateMeshContainer(alloc_hier, name, &mesh_data,
2703             materials ? ID3DXBuffer_GetBufferPointer(materials) : NULL,
2704             effects ? ID3DXBuffer_GetBufferPointer(effects) : NULL,
2705             num_materials,
2706             adjacency ? ID3DXBuffer_GetBufferPointer(adjacency) : NULL,
2707             skin_info, mesh_container);
2708
2709 cleanup:
2710     if (materials) ID3DXBuffer_Release(materials);
2711     if (effects) ID3DXBuffer_Release(effects);
2712     if (adjacency) ID3DXBuffer_Release(adjacency);
2713     if (skin_info) IUnknown_Release(skin_info);
2714     if (mesh_data.u.pMesh) IUnknown_Release(mesh_data.u.pMesh);
2715     HeapFree(GetProcessHeap(), 0, name);
2716     return hr;
2717 }
2718
2719 static HRESULT parse_transform_matrix(IDirectXFileData *filedata, D3DXMATRIX *transform)
2720 {
2721     HRESULT hr;
2722     DWORD data_size;
2723     BYTE *data;
2724
2725     /* template Matrix4x4 {
2726      *     array FLOAT matrix[16];
2727      * }
2728      * template FrameTransformMatrix {
2729      *     Matrix4x4 frameMatrix;
2730      * }
2731      */
2732
2733     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2734     if (FAILED(hr)) return hr;
2735
2736     if (data_size != sizeof(D3DXMATRIX)) {
2737         WARN("incorrect data size (%u bytes)\n", data_size);
2738         return E_FAIL;
2739     }
2740
2741     memcpy(transform, data, sizeof(D3DXMATRIX));
2742
2743     return D3D_OK;
2744 }
2745
2746 static HRESULT load_frame(IDirectXFileData *filedata,
2747                           DWORD options,
2748                           LPDIRECT3DDEVICE9 device,
2749                           LPD3DXALLOCATEHIERARCHY alloc_hier,
2750                           D3DXFRAME **frame_out)
2751 {
2752     HRESULT hr;
2753     const GUID *type;
2754     IDirectXFileData *child;
2755     char *name = NULL;
2756     D3DXFRAME *frame = NULL;
2757     D3DXMESHCONTAINER **next_container;
2758     D3DXFRAME **next_child;
2759
2760     hr = filedata_get_name(filedata, &name);
2761     if (FAILED(hr)) return hr;
2762
2763     hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, name, frame_out);
2764     HeapFree(GetProcessHeap(), 0, name);
2765     if (FAILED(hr)) return E_FAIL;
2766
2767     frame = *frame_out;
2768     D3DXMatrixIdentity(&frame->TransformationMatrix);
2769     next_child = &frame->pFrameFirstChild;
2770     next_container = &frame->pMeshContainer;
2771
2772     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2773     {
2774         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
2775             hr = load_mesh_container(child, options, device, alloc_hier, next_container);
2776             if (SUCCEEDED(hr))
2777                 next_container = &(*next_container)->pNextMeshContainer;
2778         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
2779             hr = parse_transform_matrix(child, &frame->TransformationMatrix);
2780         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
2781             hr = load_frame(child, options, device, alloc_hier, next_child);
2782             if (SUCCEEDED(hr))
2783                 next_child = &(*next_child)->pFrameSibling;
2784         }
2785         if (FAILED(hr)) break;
2786     }
2787     if (hr == DXFILEERR_NOMOREOBJECTS)
2788         hr = D3D_OK;
2789
2790     return hr;
2791 }
2792
2793 HRESULT WINAPI D3DXLoadMeshHierarchyFromXInMemory(LPCVOID memory,
2794                                                   DWORD memory_size,
2795                                                   DWORD options,
2796                                                   LPDIRECT3DDEVICE9 device,
2797                                                   LPD3DXALLOCATEHIERARCHY alloc_hier,
2798                                                   LPD3DXLOADUSERDATA load_user_data,
2799                                                   LPD3DXFRAME *frame_hierarchy,
2800                                                   LPD3DXANIMATIONCONTROLLER *anim_controller)
2801 {
2802     HRESULT hr;
2803     IDirectXFile *dxfile = NULL;
2804     IDirectXFileEnumObject *enumobj = NULL;
2805     IDirectXFileData *filedata = NULL;
2806     DXFILELOADMEMORY source;
2807     D3DXFRAME *first_frame = NULL;
2808     D3DXFRAME **next_frame = &first_frame;
2809
2810     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
2811           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
2812
2813     if (!memory || !memory_size || !device || !frame_hierarchy || !alloc_hier)
2814         return D3DERR_INVALIDCALL;
2815     if (load_user_data || anim_controller) {
2816         if (load_user_data)
2817             FIXME("Loading user data not implemented\n");
2818         if (anim_controller)
2819             FIXME("Animation controller creation not implemented\n");
2820         return E_NOTIMPL;
2821     }
2822
2823     hr = DirectXFileCreate(&dxfile);
2824     if (FAILED(hr)) goto cleanup;
2825
2826     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
2827     if (FAILED(hr)) goto cleanup;
2828
2829     source.lpMemory = (void*)memory;
2830     source.dSize = memory_size;
2831     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
2832     if (FAILED(hr)) goto cleanup;
2833
2834     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
2835     {
2836         const GUID *guid = NULL;
2837
2838         hr = IDirectXFileData_GetType(filedata, &guid);
2839         if (SUCCEEDED(hr)) {
2840             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
2841                 hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, next_frame);
2842                 if (FAILED(hr)) {
2843                     hr = E_FAIL;
2844                     goto cleanup;
2845                 }
2846
2847                 D3DXMatrixIdentity(&(*next_frame)->TransformationMatrix);
2848
2849                 hr = load_mesh_container(filedata, options, device, alloc_hier, &(*next_frame)->pMeshContainer);
2850                 if (FAILED(hr)) goto cleanup;
2851             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
2852                 hr = load_frame(filedata, options, device, alloc_hier, next_frame);
2853                 if (FAILED(hr)) goto cleanup;
2854             }
2855             while (*next_frame)
2856                 next_frame = &(*next_frame)->pFrameSibling;
2857         }
2858
2859         IDirectXFileData_Release(filedata);
2860         filedata = NULL;
2861         if (FAILED(hr))
2862             goto cleanup;
2863     }
2864     if (hr != DXFILEERR_NOMOREOBJECTS)
2865         goto cleanup;
2866
2867     if (!first_frame) {
2868         hr = E_FAIL;
2869     } else if (first_frame->pFrameSibling) {
2870         D3DXFRAME *root_frame = NULL;
2871         hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, &root_frame);
2872         if (FAILED(hr)) {
2873             hr = E_FAIL;
2874             goto cleanup;
2875         }
2876         D3DXMatrixIdentity(&root_frame->TransformationMatrix);
2877         root_frame->pFrameFirstChild = first_frame;
2878         *frame_hierarchy = root_frame;
2879         hr = D3D_OK;
2880     } else {
2881         *frame_hierarchy = first_frame;
2882         hr = D3D_OK;
2883     }
2884
2885 cleanup:
2886     if (FAILED(hr) && first_frame) D3DXFrameDestroy(first_frame, alloc_hier);
2887     if (filedata) IDirectXFileData_Release(filedata);
2888     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
2889     if (dxfile) IDirectXFile_Release(dxfile);
2890     return hr;
2891 }
2892
2893 HRESULT WINAPI D3DXFrameDestroy(LPD3DXFRAME frame, LPD3DXALLOCATEHIERARCHY alloc_hier)
2894 {
2895     HRESULT hr;
2896     BOOL last = FALSE;
2897
2898     TRACE("(%p, %p)\n", frame, alloc_hier);
2899
2900     if (!frame || !alloc_hier)
2901         return D3DERR_INVALIDCALL;
2902
2903     while (!last) {
2904         D3DXMESHCONTAINER *container;
2905         D3DXFRAME *current_frame;
2906
2907         if (frame->pFrameSibling) {
2908             current_frame = frame->pFrameSibling;
2909             frame->pFrameSibling = current_frame->pFrameSibling;
2910             current_frame->pFrameSibling = NULL;
2911         } else if (frame) {
2912             current_frame = frame;
2913             last = TRUE;
2914         }
2915
2916         if (current_frame->pFrameFirstChild) {
2917             hr = D3DXFrameDestroy(current_frame->pFrameFirstChild, alloc_hier);
2918             if (FAILED(hr)) return hr;
2919             current_frame->pFrameFirstChild = NULL;
2920         }
2921
2922         container = current_frame->pMeshContainer;
2923         while (container) {
2924             D3DXMESHCONTAINER *next_container = container->pNextMeshContainer;
2925             hr = alloc_hier->lpVtbl->DestroyMeshContainer(alloc_hier, container);
2926             if (FAILED(hr)) return hr;
2927             container = next_container;
2928         }
2929         hr = alloc_hier->lpVtbl->DestroyFrame(alloc_hier, current_frame);
2930         if (FAILED(hr)) return hr;
2931     }
2932     return D3D_OK;
2933 }
2934
2935 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
2936                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
2937 {
2938     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
2939
2940     return E_NOTIMPL;
2941 }
2942
2943 struct vertex
2944 {
2945     D3DXVECTOR3 position;
2946     D3DXVECTOR3 normal;
2947 };
2948
2949 typedef WORD face[3];
2950
2951 struct sincos_table
2952 {
2953     float *sin;
2954     float *cos;
2955 };
2956
2957 static void free_sincos_table(struct sincos_table *sincos_table)
2958 {
2959     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
2960     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
2961 }
2962
2963 /* pre compute sine and cosine tables; caller must free */
2964 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
2965 {
2966     float angle;
2967     int i;
2968
2969     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
2970     if (!sincos_table->sin)
2971     {
2972         return FALSE;
2973     }
2974     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
2975     if (!sincos_table->cos)
2976     {
2977         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
2978         return FALSE;
2979     }
2980
2981     angle = angle_start;
2982     for (i = 0; i < n; i++)
2983     {
2984         sincos_table->sin[i] = sin(angle);
2985         sincos_table->cos[i] = cos(angle);
2986         angle += angle_step;
2987     }
2988
2989     return TRUE;
2990 }
2991
2992 static WORD vertex_index(UINT slices, int slice, int stack)
2993 {
2994     return stack*slices+slice+1;
2995 }
2996
2997 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
2998                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
2999 {
3000     DWORD number_of_vertices, number_of_faces;
3001     HRESULT hr;
3002     ID3DXMesh *sphere;
3003     struct vertex *vertices;
3004     face *faces;
3005     float phi_step, phi_start;
3006     struct sincos_table phi;
3007     float theta_step, theta, sin_theta, cos_theta;
3008     DWORD vertex, face;
3009     int slice, stack;
3010
3011     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
3012
3013     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
3014     {
3015         return D3DERR_INVALIDCALL;
3016     }
3017
3018     if (adjacency)
3019     {
3020         FIXME("Case of adjacency != NULL not implemented.\n");
3021         return E_NOTIMPL;
3022     }
3023
3024     number_of_vertices = 2 + slices * (stacks-1);
3025     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
3026
3027     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
3028                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
3029     if (FAILED(hr))
3030     {
3031         return hr;
3032     }
3033
3034     hr = sphere->lpVtbl->LockVertexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&vertices);
3035     if (FAILED(hr))
3036     {
3037         sphere->lpVtbl->Release(sphere);
3038         return hr;
3039     }
3040
3041     hr = sphere->lpVtbl->LockIndexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&faces);
3042     if (FAILED(hr))
3043     {
3044         sphere->lpVtbl->UnlockVertexBuffer(sphere);
3045         sphere->lpVtbl->Release(sphere);
3046         return hr;
3047     }
3048
3049     /* phi = angle on xz plane wrt z axis */
3050     phi_step = -2 * M_PI / slices;
3051     phi_start = M_PI / 2;
3052
3053     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
3054     {
3055         sphere->lpVtbl->UnlockIndexBuffer(sphere);
3056         sphere->lpVtbl->UnlockVertexBuffer(sphere);
3057         sphere->lpVtbl->Release(sphere);
3058         return E_OUTOFMEMORY;
3059     }
3060
3061     /* theta = angle on xy plane wrt x axis */
3062     theta_step = M_PI / stacks;
3063     theta = theta_step;
3064
3065     vertex = 0;
3066     face = 0;
3067     stack = 0;
3068
3069     vertices[vertex].normal.x = 0.0f;
3070     vertices[vertex].normal.y = 0.0f;
3071     vertices[vertex].normal.z = 1.0f;
3072     vertices[vertex].position.x = 0.0f;
3073     vertices[vertex].position.y = 0.0f;
3074     vertices[vertex].position.z = radius;
3075     vertex++;
3076
3077     for (stack = 0; stack < stacks - 1; stack++)
3078     {
3079         sin_theta = sin(theta);
3080         cos_theta = cos(theta);
3081
3082         for (slice = 0; slice < slices; slice++)
3083         {
3084             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
3085             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
3086             vertices[vertex].normal.z = cos_theta;
3087             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
3088             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
3089             vertices[vertex].position.z = radius * cos_theta;
3090             vertex++;
3091
3092             if (slice > 0)
3093             {
3094                 if (stack == 0)
3095                 {
3096                     /* top stack is triangle fan */
3097                     faces[face][0] = 0;
3098                     faces[face][1] = slice + 1;
3099                     faces[face][2] = slice;
3100                     face++;
3101                 }
3102                 else
3103                 {
3104                     /* stacks in between top and bottom are quad strips */
3105                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
3106                     faces[face][1] = vertex_index(slices, slice, stack-1);
3107                     faces[face][2] = vertex_index(slices, slice-1, stack);
3108                     face++;
3109
3110                     faces[face][0] = vertex_index(slices, slice, stack-1);
3111                     faces[face][1] = vertex_index(slices, slice, stack);
3112                     faces[face][2] = vertex_index(slices, slice-1, stack);
3113                     face++;
3114                 }
3115             }
3116         }
3117
3118         theta += theta_step;
3119
3120         if (stack == 0)
3121         {
3122             faces[face][0] = 0;
3123             faces[face][1] = 1;
3124             faces[face][2] = slice;
3125             face++;
3126         }
3127         else
3128         {
3129             faces[face][0] = vertex_index(slices, slice-1, stack-1);
3130             faces[face][1] = vertex_index(slices, 0, stack-1);
3131             faces[face][2] = vertex_index(slices, slice-1, stack);
3132             face++;
3133
3134             faces[face][0] = vertex_index(slices, 0, stack-1);
3135             faces[face][1] = vertex_index(slices, 0, stack);
3136             faces[face][2] = vertex_index(slices, slice-1, stack);
3137             face++;
3138         }
3139     }
3140
3141     vertices[vertex].position.x = 0.0f;
3142     vertices[vertex].position.y = 0.0f;
3143     vertices[vertex].position.z = -radius;
3144     vertices[vertex].normal.x = 0.0f;
3145     vertices[vertex].normal.y = 0.0f;
3146     vertices[vertex].normal.z = -1.0f;
3147
3148     /* bottom stack is triangle fan */
3149     for (slice = 1; slice < slices; slice++)
3150     {
3151         faces[face][0] = vertex_index(slices, slice-1, stack-1);
3152         faces[face][1] = vertex_index(slices, slice, stack-1);
3153         faces[face][2] = vertex;
3154         face++;
3155     }
3156
3157     faces[face][0] = vertex_index(slices, slice-1, stack-1);
3158     faces[face][1] = vertex_index(slices, 0, stack-1);
3159     faces[face][2] = vertex;
3160
3161     free_sincos_table(&phi);
3162     sphere->lpVtbl->UnlockIndexBuffer(sphere);
3163     sphere->lpVtbl->UnlockVertexBuffer(sphere);
3164     *mesh = sphere;
3165
3166     return D3D_OK;
3167 }
3168
3169 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
3170                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
3171 {
3172     DWORD number_of_vertices, number_of_faces;
3173     HRESULT hr;
3174     ID3DXMesh *cylinder;
3175     struct vertex *vertices;
3176     face *faces;
3177     float theta_step, theta_start;
3178     struct sincos_table theta;
3179     float delta_radius, radius, radius_step;
3180     float z, z_step, z_normal;
3181     DWORD vertex, face;
3182     int slice, stack;
3183
3184     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
3185
3186     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
3187     {
3188         return D3DERR_INVALIDCALL;
3189     }
3190
3191     if (adjacency)
3192     {
3193         FIXME("Case of adjacency != NULL not implemented.\n");
3194         return E_NOTIMPL;
3195     }
3196
3197     number_of_vertices = 2 + (slices * (3 + stacks));
3198     number_of_faces = 2 * slices + stacks * (2 * slices);
3199
3200     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
3201                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
3202     if (FAILED(hr))
3203     {
3204         return hr;
3205     }
3206
3207     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&vertices);
3208     if (FAILED(hr))
3209     {
3210         cylinder->lpVtbl->Release(cylinder);
3211         return hr;
3212     }
3213
3214     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&faces);
3215     if (FAILED(hr))
3216     {
3217         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
3218         cylinder->lpVtbl->Release(cylinder);
3219         return hr;
3220     }
3221
3222     /* theta = angle on xy plane wrt x axis */
3223     theta_step = -2 * M_PI / slices;
3224     theta_start = M_PI / 2;
3225
3226     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
3227     {
3228         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
3229         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
3230         cylinder->lpVtbl->Release(cylinder);
3231         return E_OUTOFMEMORY;
3232     }
3233
3234     vertex = 0;
3235     face = 0;
3236
3237     delta_radius = radius1 - radius2;
3238     radius = radius1;
3239     radius_step = delta_radius / stacks;
3240
3241     z = -length / 2;
3242     z_step = length / stacks;
3243     z_normal = delta_radius / length;
3244     if (isnan(z_normal))
3245     {
3246         z_normal = 0.0f;
3247     }
3248
3249     vertices[vertex].normal.x = 0.0f;
3250     vertices[vertex].normal.y = 0.0f;
3251     vertices[vertex].normal.z = -1.0f;
3252     vertices[vertex].position.x = 0.0f;
3253     vertices[vertex].position.y = 0.0f;
3254     vertices[vertex++].position.z = z;
3255
3256     for (slice = 0; slice < slices; slice++, vertex++)
3257     {
3258         vertices[vertex].normal.x = 0.0f;
3259         vertices[vertex].normal.y = 0.0f;
3260         vertices[vertex].normal.z = -1.0f;
3261         vertices[vertex].position.x = radius * theta.cos[slice];
3262         vertices[vertex].position.y = radius * theta.sin[slice];
3263         vertices[vertex].position.z = z;
3264
3265         if (slice > 0)
3266         {
3267             faces[face][0] = 0;
3268             faces[face][1] = slice;
3269             faces[face++][2] = slice + 1;
3270         }
3271     }
3272
3273     faces[face][0] = 0;
3274     faces[face][1] = slice;
3275     faces[face++][2] = 1;
3276
3277     for (stack = 1; stack <= stacks+1; stack++)
3278     {
3279         for (slice = 0; slice < slices; slice++, vertex++)
3280         {
3281             vertices[vertex].normal.x = theta.cos[slice];
3282             vertices[vertex].normal.y = theta.sin[slice];
3283             vertices[vertex].normal.z = z_normal;
3284             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
3285             vertices[vertex].position.x = radius * theta.cos[slice];
3286             vertices[vertex].position.y = radius * theta.sin[slice];
3287             vertices[vertex].position.z = z;
3288
3289             if (stack > 1 && slice > 0)
3290             {
3291                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
3292                 faces[face][1] = vertex_index(slices, slice-1, stack);
3293                 faces[face++][2] = vertex_index(slices, slice, stack-1);
3294
3295                 faces[face][0] = vertex_index(slices, slice, stack-1);
3296                 faces[face][1] = vertex_index(slices, slice-1, stack);
3297                 faces[face++][2] = vertex_index(slices, slice, stack);
3298             }
3299         }
3300
3301         if (stack > 1)
3302         {
3303             faces[face][0] = vertex_index(slices, slice-1, stack-1);
3304             faces[face][1] = vertex_index(slices, slice-1, stack);
3305             faces[face++][2] = vertex_index(slices, 0, stack-1);
3306
3307             faces[face][0] = vertex_index(slices, 0, stack-1);
3308             faces[face][1] = vertex_index(slices, slice-1, stack);
3309             faces[face++][2] = vertex_index(slices, 0, stack);
3310         }
3311
3312         if (stack < stacks + 1)
3313         {
3314             z += z_step;
3315             radius -= radius_step;
3316         }
3317     }
3318
3319     for (slice = 0; slice < slices; slice++, vertex++)
3320     {
3321         vertices[vertex].normal.x = 0.0f;
3322         vertices[vertex].normal.y = 0.0f;
3323         vertices[vertex].normal.z = 1.0f;
3324         vertices[vertex].position.x = radius * theta.cos[slice];
3325         vertices[vertex].position.y = radius * theta.sin[slice];
3326         vertices[vertex].position.z = z;
3327
3328         if (slice > 0)
3329         {
3330             faces[face][0] = vertex_index(slices, slice-1, stack);
3331             faces[face][1] = number_of_vertices - 1;
3332             faces[face++][2] = vertex_index(slices, slice, stack);
3333         }
3334     }
3335
3336     vertices[vertex].position.x = 0.0f;
3337     vertices[vertex].position.y = 0.0f;
3338     vertices[vertex].position.z = z;
3339     vertices[vertex].normal.x = 0.0f;
3340     vertices[vertex].normal.y = 0.0f;
3341     vertices[vertex].normal.z = 1.0f;
3342
3343     faces[face][0] = vertex_index(slices, slice-1, stack);
3344     faces[face][1] = number_of_vertices - 1;
3345     faces[face][2] = vertex_index(slices, 0, stack);
3346
3347     free_sincos_table(&theta);
3348     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
3349     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
3350     *mesh = cylinder;
3351
3352     return D3D_OK;
3353 }
3354
3355 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
3356 {
3357     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
3358
3359     return E_NOTIMPL;
3360 }
3361
3362 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
3363                                HDC hdc, LPCSTR text,
3364                                FLOAT deviation, FLOAT extrusion,
3365                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
3366                                LPGLYPHMETRICSFLOAT glyphmetrics)
3367 {
3368     HRESULT hr;
3369     int len;
3370     LPWSTR textW;
3371
3372     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
3373           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
3374
3375     if (!text)
3376         return D3DERR_INVALIDCALL;
3377
3378     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
3379     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3380     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
3381
3382     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
3383                          mesh, adjacency, glyphmetrics);
3384     HeapFree(GetProcessHeap(), 0, textW);
3385
3386     return hr;
3387 }
3388
3389 enum pointtype {
3390     POINTTYPE_CURVE = 0,
3391     POINTTYPE_CORNER,
3392     POINTTYPE_CURVE_START,
3393     POINTTYPE_CURVE_END,
3394     POINTTYPE_CURVE_MIDDLE,
3395 };
3396
3397 struct point2d
3398 {
3399     D3DXVECTOR2 pos;
3400     enum pointtype corner;
3401 };
3402
3403 struct dynamic_array
3404 {
3405     int count, capacity;
3406     void *items;
3407 };
3408
3409 /* is a dynamic_array */
3410 struct outline
3411 {
3412     int count, capacity;
3413     struct point2d *items;
3414 };
3415
3416 /* is a dynamic_array */
3417 struct outline_array
3418 {
3419     int count, capacity;
3420     struct outline *items;
3421 };
3422
3423 struct face_array
3424 {
3425     int count;
3426     face *items;
3427 };
3428
3429 struct point2d_index
3430 {
3431     struct outline *outline;
3432     int vertex;
3433 };
3434
3435 struct point2d_index_array
3436 {
3437     int count;
3438     struct point2d_index *items;
3439 };
3440
3441 struct glyphinfo
3442 {
3443     struct outline_array outlines;
3444     struct face_array faces;
3445     struct point2d_index_array ordered_vertices;
3446     float offset_x;
3447 };
3448
3449 /* is an dynamic_array */
3450 struct word_array
3451 {
3452     int count, capacity;
3453     WORD *items;
3454 };
3455
3456 /* complex polygons are split into monotone polygons, which have
3457  * at most 2 intersections with the vertical sweep line */
3458 struct triangulation
3459 {
3460     struct word_array vertex_stack;
3461     BOOL last_on_top, merging;
3462 };
3463
3464 /* is an dynamic_array */
3465 struct triangulation_array
3466 {
3467     int count, capacity;
3468     struct triangulation *items;
3469
3470     struct glyphinfo *glyph;
3471 };
3472
3473 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
3474 {
3475     if (count > array->capacity) {
3476         void *new_buffer;
3477         int new_capacity;
3478         if (array->items && array->capacity) {
3479             new_capacity = max(array->capacity * 2, count);
3480             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
3481         } else {
3482             new_capacity = max(16, count);
3483             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
3484         }
3485         if (!new_buffer)
3486             return FALSE;
3487         array->items = new_buffer;
3488         array->capacity = new_capacity;
3489     }
3490     return TRUE;
3491 }
3492
3493 static struct point2d *add_points(struct outline *array, int num)
3494 {
3495     struct point2d *item;
3496
3497     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
3498         return NULL;
3499
3500     item = &array->items[array->count];
3501     array->count += num;
3502     return item;
3503 }
3504
3505 static struct outline *add_outline(struct outline_array *array)
3506 {
3507     struct outline *item;
3508
3509     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
3510         return NULL;
3511
3512     item = &array->items[array->count++];
3513     ZeroMemory(item, sizeof(*item));
3514     return item;
3515 }
3516
3517 static inline face *add_face(struct face_array *array)
3518 {
3519     return &array->items[array->count++];
3520 }
3521
3522 static struct triangulation *add_triangulation(struct triangulation_array *array)
3523 {
3524     struct triangulation *item;
3525
3526     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
3527         return NULL;
3528
3529     item = &array->items[array->count++];
3530     ZeroMemory(item, sizeof(*item));
3531     return item;
3532 }
3533
3534 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
3535 {
3536     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
3537         return E_OUTOFMEMORY;
3538
3539     array->items[array->count++] = vertex_index;
3540     return S_OK;
3541 }
3542
3543 /* assume fixed point numbers can be converted to float point in place */
3544 C_ASSERT(sizeof(FIXED) == sizeof(float));
3545 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
3546
3547 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
3548 {
3549     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
3550     while (count--) {
3551         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
3552         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
3553         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
3554         pt++;
3555     }
3556     return ret;
3557 }
3558
3559 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
3560                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
3561                                  float max_deviation_sq)
3562 {
3563     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
3564     float deviation_sq;
3565
3566     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
3567     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
3568     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
3569
3570     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
3571     if (deviation_sq < max_deviation_sq) {
3572         struct point2d *pt = add_points(outline, 1);
3573         if (!pt) return E_OUTOFMEMORY;
3574         pt->pos = *p2;
3575         pt->corner = POINTTYPE_CURVE;
3576         /* the end point is omitted because the end line merges into the next segment of
3577          * the split bezier curve, and the end of the split bezier curve is added outside
3578          * this recursive function. */
3579     } else {
3580         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
3581         if (hr != S_OK) return hr;
3582         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
3583         if (hr != S_OK) return hr;
3584     }
3585
3586     return S_OK;
3587 }
3588
3589 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
3590 {
3591     /* dot product = cos(theta) */
3592     return D3DXVec2Dot(dir1, dir2) > cos_theta;
3593 }
3594
3595 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
3596 {
3597     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
3598 }
3599
3600 struct cos_table
3601 {
3602     float cos_half;
3603     float cos_45;
3604     float cos_90;
3605 };
3606
3607 static BOOL attempt_line_merge(struct outline *outline,
3608                                int pt_index,
3609                                const D3DXVECTOR2 *nextpt,
3610                                BOOL to_curve,
3611                                const struct cos_table *table)
3612 {
3613     D3DXVECTOR2 curdir, lastdir;
3614     struct point2d *prevpt, *pt;
3615     BOOL ret = FALSE;
3616
3617     pt = &outline->items[pt_index];
3618     pt_index = (pt_index - 1 + outline->count) % outline->count;
3619     prevpt = &outline->items[pt_index];
3620
3621     if (to_curve)
3622         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
3623
3624     if (outline->count < 2)
3625         return FALSE;
3626
3627     /* remove last point if the next line continues the last line */
3628     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
3629     unit_vec2(&curdir, &pt->pos, nextpt);
3630     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
3631     {
3632         outline->count--;
3633         if (pt->corner == POINTTYPE_CURVE_END)
3634             prevpt->corner = pt->corner;
3635         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
3636             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
3637         pt = prevpt;
3638
3639         ret = TRUE;
3640         if (outline->count < 2)
3641             return ret;
3642
3643         pt_index = (pt_index - 1 + outline->count) % outline->count;
3644         prevpt = &outline->items[pt_index];
3645         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
3646         unit_vec2(&curdir, &pt->pos, nextpt);
3647     }
3648     return ret;
3649 }
3650
3651 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
3652                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
3653 {
3654     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
3655
3656     while ((char *)header < (char *)raw_outline + datasize)
3657     {
3658         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
3659         struct point2d *lastpt, *pt;
3660         D3DXVECTOR2 lastdir;
3661         D3DXVECTOR2 *pt_flt;
3662         int j;
3663         struct outline *outline = add_outline(&glyph->outlines);
3664
3665         if (!outline)
3666             return E_OUTOFMEMORY;
3667
3668         pt = add_points(outline, 1);
3669         if (!pt)
3670             return E_OUTOFMEMORY;
3671         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
3672         pt->pos = *pt_flt;
3673         pt->corner = POINTTYPE_CORNER;
3674
3675         if (header->dwType != TT_POLYGON_TYPE)
3676             FIXME("Unknown header type %d\n", header->dwType);
3677
3678         while ((char *)curve < (char *)header + header->cb)
3679         {
3680             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
3681             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
3682
3683             if (!curve->cpfx) {
3684                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
3685                 continue;
3686             }
3687
3688             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
3689
3690             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
3691
3692             if (to_curve)
3693             {
3694                 HRESULT hr;
3695                 int count = curve->cpfx;
3696                 j = 0;
3697
3698                 while (count > 2)
3699                 {
3700                     D3DXVECTOR2 bezier_end;
3701
3702                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
3703                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
3704                     if (hr != S_OK)
3705                         return hr;
3706                     bezier_start = bezier_end;
3707                     count--;
3708                     j++;
3709                 }
3710                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
3711                 if (hr != S_OK)
3712                     return hr;
3713
3714                 pt = add_points(outline, 1);
3715                 if (!pt)
3716                     return E_OUTOFMEMORY;
3717                 j++;
3718                 pt->pos = pt_flt[j];
3719                 pt->corner = POINTTYPE_CURVE_END;
3720             } else {
3721                 pt = add_points(outline, curve->cpfx);
3722                 if (!pt)
3723                     return E_OUTOFMEMORY;
3724                 for (j = 0; j < curve->cpfx; j++)
3725                 {
3726                     pt->pos = pt_flt[j];
3727                     pt->corner = POINTTYPE_CORNER;
3728                     pt++;
3729                 }
3730             }
3731
3732             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
3733         }
3734
3735         /* remove last point if the next line continues the last line */
3736         if (outline->count >= 3) {
3737             BOOL to_curve;
3738
3739             lastpt = &outline->items[outline->count - 1];
3740             pt = &outline->items[0];
3741             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
3742                 if (lastpt->corner == POINTTYPE_CURVE_END)
3743                 {
3744                     if (pt->corner == POINTTYPE_CURVE_START)
3745                         pt->corner = POINTTYPE_CURVE_MIDDLE;
3746                     else
3747                         pt->corner = POINTTYPE_CURVE_END;
3748                 }
3749                 outline->count--;
3750                 lastpt = &outline->items[outline->count - 1];
3751             } else {
3752                 /* outline closed with a line from end to start point */
3753                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
3754             }
3755             lastpt = &outline->items[0];
3756             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
3757             if (lastpt->corner == POINTTYPE_CURVE_START)
3758                 lastpt->corner = POINTTYPE_CORNER;
3759             pt = &outline->items[1];
3760             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
3761                 *lastpt = outline->items[outline->count];
3762         }
3763
3764         lastpt = &outline->items[outline->count - 1];
3765         pt = &outline->items[0];
3766         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
3767         for (j = 0; j < outline->count; j++)
3768         {
3769             D3DXVECTOR2 curdir;
3770
3771             lastpt = pt;
3772             pt = &outline->items[(j + 1) % outline->count];
3773             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
3774
3775             switch (lastpt->corner)
3776             {
3777                 case POINTTYPE_CURVE_START:
3778                 case POINTTYPE_CURVE_END:
3779                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
3780                         lastpt->corner = POINTTYPE_CORNER;
3781                     break;
3782                 case POINTTYPE_CURVE_MIDDLE:
3783                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
3784                         lastpt->corner = POINTTYPE_CORNER;
3785                     else
3786                         lastpt->corner = POINTTYPE_CURVE;
3787                     break;
3788                 default:
3789                     break;
3790             }
3791             lastdir = curdir;
3792         }
3793
3794         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
3795     }
3796     return S_OK;
3797 }
3798
3799 /* Get the y-distance from a line to a point */
3800 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
3801                                           D3DXVECTOR2 *line_pt2,
3802                                           D3DXVECTOR2 *point)
3803 {
3804     D3DXVECTOR2 line_vec = {0, 0};
3805     float line_pt_dx;
3806     float line_y;
3807
3808     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
3809     line_pt_dx = point->x - line_pt1->x;
3810     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
3811     return point->y - line_y;
3812 }
3813
3814 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
3815 {
3816     return &pt_idx->outline->items[pt_idx->vertex].pos;
3817 }
3818
3819 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
3820 {
3821     return get_indexed_point(&glyph->ordered_vertices.items[index]);
3822 }
3823
3824 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
3825 {
3826     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
3827     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
3828     array->count--;
3829 }
3830
3831 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
3832                                        struct triangulation_array *triangulations,
3833                                        WORD vtx_idx,
3834                                        BOOL to_top)
3835 {
3836     struct glyphinfo *glyph = triangulations->glyph;
3837     struct triangulation *t = *t_ptr;
3838     HRESULT hr;
3839     face *face;
3840     int f1, f2;
3841
3842     if (t->last_on_top) {
3843         f1 = 1;
3844         f2 = 2;
3845     } else {
3846         f1 = 2;
3847         f2 = 1;
3848     }
3849
3850     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
3851         /* consume all vertices on the stack */
3852         WORD last_pt = t->vertex_stack.items[0];
3853         int i;
3854         for (i = 1; i < t->vertex_stack.count; i++)
3855         {
3856             face = add_face(&glyph->faces);
3857             if (!face) return E_OUTOFMEMORY;
3858             (*face)[0] = vtx_idx;
3859             (*face)[f1] = last_pt;
3860             (*face)[f2] = last_pt = t->vertex_stack.items[i];
3861         }
3862         t->vertex_stack.items[0] = last_pt;
3863         t->vertex_stack.count = 1;
3864     } else if (t->vertex_stack.count > 1) {
3865         int i = t->vertex_stack.count - 1;
3866         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
3867         WORD top_idx = t->vertex_stack.items[i--];
3868         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
3869
3870         while (i >= 0)
3871         {
3872             WORD prev_idx = t->vertex_stack.items[i--];
3873             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
3874
3875             if (prev_pt->x != top_pt->x &&
3876                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
3877                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
3878                 break;
3879
3880             face = add_face(&glyph->faces);
3881             if (!face) return E_OUTOFMEMORY;
3882             (*face)[0] = vtx_idx;
3883             (*face)[f1] = prev_idx;
3884             (*face)[f2] = top_idx;
3885
3886             top_pt = prev_pt;
3887             top_idx = prev_idx;
3888             t->vertex_stack.count--;
3889         }
3890     }
3891     t->last_on_top = to_top;
3892
3893     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
3894
3895     if (hr == S_OK && t->merging) {
3896         struct triangulation *t2;
3897
3898         t2 = to_top ? t - 1 : t + 1;
3899         t2->merging = FALSE;
3900         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
3901         if (hr != S_OK) return hr;
3902         remove_triangulation(triangulations, t);
3903         if (t2 > t)
3904             t2--;
3905         *t_ptr = t2;
3906     }
3907     return hr;
3908 }
3909
3910 /* check if the point is next on the outline for either the top or bottom */
3911 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
3912 {
3913     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
3914     WORD idx = t->vertex_stack.items[i];
3915     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
3916     struct outline *outline = pt_idx->outline;
3917
3918     if (on_top)
3919         i = (pt_idx->vertex + outline->count - 1) % outline->count;
3920     else
3921         i = (pt_idx->vertex + 1) % outline->count;
3922
3923     return &outline->items[i].pos;
3924 }
3925
3926 static int compare_vertex_indices(const void *a, const void *b)
3927 {
3928     const struct point2d_index *idx1 = a, *idx2 = b;
3929     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
3930     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
3931     float diff = p1->x - p2->x;
3932
3933     if (diff == 0.0f)
3934         diff = p1->y - p2->y;
3935
3936     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
3937 }
3938
3939 static HRESULT triangulate(struct triangulation_array *triangulations)
3940 {
3941     int sweep_idx;
3942     HRESULT hr;
3943     struct glyphinfo *glyph = triangulations->glyph;
3944     int nb_vertices = 0;
3945     int i;
3946     struct point2d_index *idx_ptr;
3947
3948     for (i = 0; i < glyph->outlines.count; i++)
3949         nb_vertices += glyph->outlines.items[i].count;
3950
3951     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
3952             nb_vertices * sizeof(*glyph->ordered_vertices.items));
3953     if (!glyph->ordered_vertices.items)
3954         return E_OUTOFMEMORY;
3955
3956     idx_ptr = glyph->ordered_vertices.items;
3957     for (i = 0; i < glyph->outlines.count; i++)
3958     {
3959         struct outline *outline = &glyph->outlines.items[i];
3960         int j;
3961
3962         idx_ptr->outline = outline;
3963         idx_ptr->vertex = 0;
3964         idx_ptr++;
3965         for (j = outline->count - 1; j > 0; j--)
3966         {
3967             idx_ptr->outline = outline;
3968             idx_ptr->vertex = j;
3969             idx_ptr++;
3970         }
3971     }
3972     glyph->ordered_vertices.count = nb_vertices;
3973
3974     /* Native implementation seems to try to create a triangle fan from
3975      * the first outline point if the glyph only has one outline. */
3976     if (glyph->outlines.count == 1)
3977     {
3978         struct outline *outline = glyph->outlines.items;
3979         D3DXVECTOR2 *base = &outline->items[0].pos;
3980         D3DXVECTOR2 *last = &outline->items[1].pos;
3981         float ccw = 0;
3982
3983         for (i = 2; i < outline->count; i++)
3984         {
3985             D3DXVECTOR2 *next = &outline->items[i].pos;
3986             D3DXVECTOR2 v1 = {0.0f, 0.0f};
3987             D3DXVECTOR2 v2 = {0.0f, 0.0f};
3988
3989             D3DXVec2Subtract(&v1, base, last);
3990             D3DXVec2Subtract(&v2, last, next);
3991             ccw = D3DXVec2CCW(&v1, &v2);
3992             if (ccw > 0.0f)
3993                 break;
3994
3995             last = next;
3996         }
3997         if (ccw <= 0)
3998         {
3999             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
4000                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
4001             if (!glyph->faces.items)
4002                 return E_OUTOFMEMORY;
4003
4004             glyph->faces.count = outline->count - 2;
4005             for (i = 0; i < glyph->faces.count; i++)
4006             {
4007                 glyph->faces.items[i][0] = 0;
4008                 glyph->faces.items[i][1] = i + 1;
4009                 glyph->faces.items[i][2] = i + 2;
4010             }
4011             return S_OK;
4012         }
4013     }
4014
4015     /* Perform 2D polygon triangulation for complex glyphs.
4016      * Triangulation is performed using a sweep line concept, from right to left,
4017      * by processing vertices in sorted order. Complex polygons are split into
4018      * monotone polygons which are triangulated separately. */
4019     /* FIXME: The order of the faces is not consistent with the native implementation. */
4020
4021     /* Reserve space for maximum possible faces from triangulation.
4022      * # faces for outer outlines = outline->count - 2
4023      * # faces for inner outlines = outline->count + 2
4024      * There must be at least 1 outer outline. */
4025     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
4026             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
4027     if (!glyph->faces.items)
4028         return E_OUTOFMEMORY;
4029
4030     qsort(glyph->ordered_vertices.items, nb_vertices,
4031           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
4032     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
4033     {
4034         int start = 0;
4035         int end = triangulations->count;
4036
4037         while (start < end)
4038         {
4039             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
4040             int current = (start + end) / 2;
4041             struct triangulation *t = &triangulations->items[current];
4042             BOOL on_top_outline = FALSE;
4043             D3DXVECTOR2 *top_next, *bottom_next;
4044             WORD top_idx, bottom_idx;
4045
4046             if (t->merging && t->last_on_top)
4047                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
4048             else
4049                 top_next = triangulation_get_next_point(t, glyph, TRUE);
4050             if (sweep_vtx == top_next)
4051             {
4052                 if (t->merging && t->last_on_top)
4053                     t++;
4054                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
4055                 if (hr != S_OK) return hr;
4056
4057                 if (t + 1 < &triangulations->items[triangulations->count] &&
4058                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
4059                 {
4060                     /* point also on bottom outline of higher triangulation */
4061                     struct triangulation *t2 = t + 1;
4062                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
4063                     if (hr != S_OK) return hr;
4064
4065                     t->merging = TRUE;
4066                     t2->merging = TRUE;
4067                 }
4068                 on_top_outline = TRUE;
4069             }
4070
4071             if (t->merging && !t->last_on_top)
4072                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
4073             else
4074                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
4075             if (sweep_vtx == bottom_next)
4076             {
4077                 if (t->merging && !t->last_on_top)
4078                     t--;
4079                 if (on_top_outline) {
4080                     /* outline finished */
4081                     remove_triangulation(triangulations, t);
4082                     break;
4083                 }
4084
4085                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
4086                 if (hr != S_OK) return hr;
4087
4088                 if (t > triangulations->items &&
4089                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
4090                 {
4091                     struct triangulation *t2 = t - 1;
4092                     /* point also on top outline of lower triangulation */
4093                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
4094                     if (hr != S_OK) return hr;
4095                     t = t2 + 1; /* t may be invalidated by triangulation merging */
4096
4097                     t->merging = TRUE;
4098                     t2->merging = TRUE;
4099                 }
4100                 break;
4101             }
4102             if (on_top_outline)
4103                 break;
4104
4105             if (t->last_on_top) {
4106                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
4107                 bottom_idx = t->vertex_stack.items[0];
4108             } else {
4109                 top_idx = t->vertex_stack.items[0];
4110                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
4111             }
4112
4113             /* check if the point is inside or outside this polygon */
4114             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
4115                                              top_next, sweep_vtx) > 0)
4116             { /* above */
4117                 start = current + 1;
4118             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
4119                                                     bottom_next, sweep_vtx) < 0)
4120             { /* below */
4121                 end = current;
4122             } else if (t->merging) {
4123                 /* inside, so cancel merging */
4124                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
4125                 t->merging = FALSE;
4126                 t2->merging = FALSE;
4127                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
4128                 if (hr != S_OK) return hr;
4129                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
4130                 if (hr != S_OK) return hr;
4131                 break;
4132             } else {
4133                 /* inside, so split polygon into two monotone parts */
4134                 struct triangulation *t2 = add_triangulation(triangulations);
4135                 if (!t2) return E_OUTOFMEMORY;
4136                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
4137                 if (t->last_on_top) {
4138                     t2 = t + 1;
4139                 } else {
4140                     t2 = t;
4141                     t++;
4142                 }
4143
4144                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
4145                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
4146                 if (hr != S_OK) return hr;
4147                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
4148                 if (hr != S_OK) return hr;
4149                 t2->last_on_top = !t->last_on_top;
4150
4151                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
4152                 if (hr != S_OK) return hr;
4153                 break;
4154             }
4155         }
4156         if (start >= end)
4157         {
4158             struct triangulation *t;
4159             struct triangulation *t2 = add_triangulation(triangulations);
4160             if (!t2) return E_OUTOFMEMORY;
4161             t = &triangulations->items[start];
4162             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
4163             ZeroMemory(t, sizeof(*t));
4164             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
4165             if (hr != S_OK) return hr;
4166         }
4167     }
4168     return S_OK;
4169 }
4170
4171 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
4172                                HDC hdc, LPCWSTR text,
4173                                FLOAT deviation, FLOAT extrusion,
4174                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
4175                                LPGLYPHMETRICSFLOAT glyphmetrics)
4176 {
4177     HRESULT hr;
4178     ID3DXMesh *mesh = NULL;
4179     DWORD nb_vertices, nb_faces;
4180     DWORD nb_front_faces, nb_corners, nb_outline_points;
4181     struct vertex *vertices = NULL;
4182     face *faces = NULL;
4183     int textlen = 0;
4184     float offset_x;
4185     LOGFONTW lf;
4186     OUTLINETEXTMETRICW otm;
4187     HFONT font = NULL, oldfont = NULL;
4188     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
4189     void *raw_outline = NULL;
4190     int bufsize = 0;
4191     struct glyphinfo *glyphs = NULL;
4192     GLYPHMETRICS gm;
4193     struct triangulation_array triangulations = {0, 0, NULL};
4194     int i;
4195     struct vertex *vertex_ptr;
4196     face *face_ptr;
4197     float max_deviation_sq;
4198     const struct cos_table cos_table = {
4199         cos(D3DXToRadian(0.5f)),
4200         cos(D3DXToRadian(45.0f)),
4201         cos(D3DXToRadian(90.0f)),
4202     };
4203     int f1, f2;
4204
4205     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
4206           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
4207
4208     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
4209         return D3DERR_INVALIDCALL;
4210
4211     if (adjacency)
4212     {
4213         FIXME("Case of adjacency != NULL not implemented.\n");
4214         return E_NOTIMPL;
4215     }
4216
4217     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
4218         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
4219     {
4220         return D3DERR_INVALIDCALL;
4221     }
4222
4223     if (deviation == 0.0f)
4224         deviation = 1.0f / otm.otmEMSquare;
4225     max_deviation_sq = deviation * deviation;
4226
4227     lf.lfHeight = otm.otmEMSquare;
4228     lf.lfWidth = 0;
4229     font = CreateFontIndirectW(&lf);
4230     if (!font) {
4231         hr = E_OUTOFMEMORY;
4232         goto error;
4233     }
4234     oldfont = SelectObject(hdc, font);
4235
4236     textlen = strlenW(text);
4237     for (i = 0; i < textlen; i++)
4238     {
4239         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
4240         if (datasize < 0)
4241             return D3DERR_INVALIDCALL;
4242         if (bufsize < datasize)
4243             bufsize = datasize;
4244     }
4245     if (!bufsize) { /* e.g. text == " " */
4246         hr = D3DERR_INVALIDCALL;
4247         goto error;
4248     }
4249
4250     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
4251     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
4252     if (!glyphs || !raw_outline) {
4253         hr = E_OUTOFMEMORY;
4254         goto error;
4255     }
4256
4257     offset_x = 0.0f;
4258     for (i = 0; i < textlen; i++)
4259     {
4260         /* get outline points from data returned from GetGlyphOutline */
4261         int datasize;
4262
4263         glyphs[i].offset_x = offset_x;
4264
4265         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
4266         hr = create_outline(&glyphs[i], raw_outline, datasize,
4267                             max_deviation_sq, otm.otmEMSquare, &cos_table);
4268         if (hr != S_OK) goto error;
4269
4270         triangulations.glyph = &glyphs[i];
4271         hr = triangulate(&triangulations);
4272         if (hr != S_OK) goto error;
4273         if (triangulations.count) {
4274             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
4275             triangulations.count = 0;
4276         }
4277
4278         if (glyphmetrics)
4279         {
4280             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
4281             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
4282             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
4283             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
4284             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
4285             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
4286         }
4287         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
4288     }
4289
4290     /* corner points need an extra vertex for the different side faces normals */
4291     nb_corners = 0;
4292     nb_outline_points = 0;
4293     nb_front_faces = 0;
4294     for (i = 0; i < textlen; i++)
4295     {
4296         int j;
4297         nb_outline_points += glyphs[i].ordered_vertices.count;
4298         nb_front_faces += glyphs[i].faces.count;
4299         for (j = 0; j < glyphs[i].outlines.count; j++)
4300         {
4301             int k;
4302             struct outline *outline = &glyphs[i].outlines.items[j];
4303             nb_corners++; /* first outline point always repeated as a corner */
4304             for (k = 1; k < outline->count; k++)
4305                 if (outline->items[k].corner)
4306                     nb_corners++;
4307         }
4308     }
4309
4310     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
4311     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
4312
4313
4314     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
4315                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
4316     if (FAILED(hr))
4317         goto error;
4318
4319     hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&vertices);
4320     if (FAILED(hr))
4321         goto error;
4322
4323     hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&faces);
4324     if (FAILED(hr))
4325         goto error;
4326
4327     /* convert 2D vertices and faces into 3D mesh */
4328     vertex_ptr = vertices;
4329     face_ptr = faces;
4330     if (extrusion == 0.0f) {
4331         f1 = 1;
4332         f2 = 2;
4333     } else {
4334         f1 = 2;
4335         f2 = 1;
4336     }
4337     for (i = 0; i < textlen; i++)
4338     {
4339         int j;
4340         int count;
4341         struct vertex *back_vertices;
4342         face *back_faces;
4343
4344         /* side vertices and faces */
4345         for (j = 0; j < glyphs[i].outlines.count; j++)
4346         {
4347             struct vertex *outline_vertices = vertex_ptr;
4348             struct outline *outline = &glyphs[i].outlines.items[j];
4349             int k;
4350             struct point2d *prevpt = &outline->items[outline->count - 1];
4351             struct point2d *pt = &outline->items[0];
4352
4353             for (k = 1; k <= outline->count; k++)
4354             {
4355                 struct vertex vtx;
4356                 struct point2d *nextpt = &outline->items[k % outline->count];
4357                 WORD vtx_idx = vertex_ptr - vertices;
4358                 D3DXVECTOR2 vec;
4359
4360                 if (pt->corner == POINTTYPE_CURVE_START)
4361                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
4362                 else if (pt->corner)
4363                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
4364                 else
4365                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
4366                 D3DXVec2Normalize(&vec, &vec);
4367                 vtx.normal.x = -vec.y;
4368                 vtx.normal.y = vec.x;
4369                 vtx.normal.z = 0;
4370
4371                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
4372                 vtx.position.y = pt->pos.y;
4373                 vtx.position.z = 0;
4374                 *vertex_ptr++ = vtx;
4375
4376                 vtx.position.z = -extrusion;
4377                 *vertex_ptr++ = vtx;
4378
4379                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
4380                 vtx.position.y = nextpt->pos.y;
4381                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
4382                     vtx.position.z = -extrusion;
4383                     *vertex_ptr++ = vtx;
4384                     vtx.position.z = 0;
4385                     *vertex_ptr++ = vtx;
4386
4387                     (*face_ptr)[0] = vtx_idx;
4388                     (*face_ptr)[1] = vtx_idx + 2;
4389                     (*face_ptr)[2] = vtx_idx + 1;
4390                     face_ptr++;
4391
4392                     (*face_ptr)[0] = vtx_idx;
4393                     (*face_ptr)[1] = vtx_idx + 3;
4394                     (*face_ptr)[2] = vtx_idx + 2;
4395                     face_ptr++;
4396                 } else {
4397                     if (nextpt->corner) {
4398                         if (nextpt->corner == POINTTYPE_CURVE_END) {
4399                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
4400                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
4401                         } else {
4402                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
4403                         }
4404                         D3DXVec2Normalize(&vec, &vec);
4405                         vtx.normal.x = -vec.y;
4406                         vtx.normal.y = vec.x;
4407
4408                         vtx.position.z = 0;
4409                         *vertex_ptr++ = vtx;
4410                         vtx.position.z = -extrusion;
4411                         *vertex_ptr++ = vtx;
4412                     }
4413
4414                     (*face_ptr)[0] = vtx_idx;
4415                     (*face_ptr)[1] = vtx_idx + 3;
4416                     (*face_ptr)[2] = vtx_idx + 1;
4417                     face_ptr++;
4418
4419                     (*face_ptr)[0] = vtx_idx;
4420                     (*face_ptr)[1] = vtx_idx + 2;
4421                     (*face_ptr)[2] = vtx_idx + 3;
4422                     face_ptr++;
4423                 }
4424
4425                 prevpt = pt;
4426                 pt = nextpt;
4427             }
4428             if (!pt->corner) {
4429                 *vertex_ptr++ = *outline_vertices++;
4430                 *vertex_ptr++ = *outline_vertices++;
4431             }
4432         }
4433
4434         /* back vertices and faces */
4435         back_faces = face_ptr;
4436         back_vertices = vertex_ptr;
4437         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
4438         {
4439             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
4440             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
4441             vertex_ptr->position.y = pt->y;
4442             vertex_ptr->position.z = 0;
4443             vertex_ptr->normal.x = 0;
4444             vertex_ptr->normal.y = 0;
4445             vertex_ptr->normal.z = 1;
4446             vertex_ptr++;
4447         }
4448         count = back_vertices - vertices;
4449         for (j = 0; j < glyphs[i].faces.count; j++)
4450         {
4451             face *f = &glyphs[i].faces.items[j];
4452             (*face_ptr)[0] = (*f)[0] + count;
4453             (*face_ptr)[1] = (*f)[1] + count;
4454             (*face_ptr)[2] = (*f)[2] + count;
4455             face_ptr++;
4456         }
4457
4458         /* front vertices and faces */
4459         j = count = vertex_ptr - back_vertices;
4460         while (j--)
4461         {
4462             vertex_ptr->position.x = back_vertices->position.x;
4463             vertex_ptr->position.y = back_vertices->position.y;
4464             vertex_ptr->position.z = -extrusion;
4465             vertex_ptr->normal.x = 0;
4466             vertex_ptr->normal.y = 0;
4467             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
4468             vertex_ptr++;
4469             back_vertices++;
4470         }
4471         j = face_ptr - back_faces;
4472         while (j--)
4473         {
4474             (*face_ptr)[0] = (*back_faces)[0] + count;
4475             (*face_ptr)[1] = (*back_faces)[f1] + count;
4476             (*face_ptr)[2] = (*back_faces)[f2] + count;
4477             face_ptr++;
4478             back_faces++;
4479         }
4480     }
4481
4482     *mesh_ptr = mesh;
4483     hr = D3D_OK;
4484 error:
4485     if (mesh) {
4486         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
4487         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
4488         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
4489     }
4490     if (glyphs) {
4491         for (i = 0; i < textlen; i++)
4492         {
4493             int j;
4494             for (j = 0; j < glyphs[i].outlines.count; j++)
4495                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
4496             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
4497             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
4498             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
4499         }
4500         HeapFree(GetProcessHeap(), 0, glyphs);
4501     }
4502     if (triangulations.items) {
4503         int i;
4504         for (i = 0; i < triangulations.count; i++)
4505             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
4506         HeapFree(GetProcessHeap(), 0, triangulations.items);
4507     }
4508     HeapFree(GetProcessHeap(), 0, raw_outline);
4509     if (oldfont) SelectObject(hdc, oldfont);
4510     if (font) DeleteObject(font);
4511
4512     return hr;
4513 }