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

   1  /*
   2  * Mesh operations specific to D3DX9.
   3  *
   4  * Copyright (C) 2005 Henri Verbeet
   5  * Copyright (C) 2006 Ivan Gyurdiev
   6  * Copyright (C) 2009 David Adam
   7  * Copyright (C) 2010 Tony Wasserka
   8  * Copyright (C) 2011 Dylan Smith
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2.1 of the License, or (at your option) any later version.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  23  */
  24
  25 #include "config.h"
  26 #include "wine/port.h"
  27
  28 #define COBJMACROS
  29 #define NONAMELESSUNION
  30 #include "windef.h"
  31 #include "wingdi.h"
  32 #include "d3dx9.h"
  33 #include "wine/debug.h"
  34 #include "wine/unicode.h"
  35 #include "d3dx9_36_private.h"
  36
  37 WINE_DEFAULT_DEBUG_CHANNEL(d3dx);
  38
  39 typedef struct ID3DXMeshImpl
  40 {
  41     ID3DXMesh ID3DXMesh_iface;
  42     LONG ref;
  43
  44     DWORD numfaces;
  45     DWORD numvertices;
  46     DWORD options;
  47     DWORD fvf;
  48     IDirect3DDevice9 *device;
  49     IDirect3DVertexDeclaration9 *vertex_declaration;
  50     IDirect3DVertexBuffer9 *vertex_buffer;
  51     IDirect3DIndexBuffer9 *index_buffer;
  52     DWORD *attrib_buffer;
  53     int attrib_buffer_lock_count;
  54     DWORD attrib_table_size;
  55     D3DXATTRIBUTERANGE *attrib_table;
  56 } ID3DXMeshImpl;
  57
  58 static inline ID3DXMeshImpl *impl_from_ID3DXMesh(ID3DXMesh *iface)
  59 {
  60     return CONTAINING_RECORD(iface, ID3DXMeshImpl, ID3DXMesh_iface);
  61 }
  62
  63 static HRESULT WINAPI ID3DXMeshImpl_QueryInterface(ID3DXMesh *iface, REFIID riid, LPVOID *object)
  64 {
  65     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  66
  67     TRACE("(%p)->(%s, %p)\n", This, debugstr_guid(riid), object);
  68
  69     if (IsEqualGUID(riid, &IID_IUnknown) ||
  70         IsEqualGUID(riid, &IID_ID3DXBaseMesh) ||
  71         IsEqualGUID(riid, &IID_ID3DXMesh))
  72     {
  73         iface->lpVtbl->AddRef(iface);
  74         *object = This;
  75         return S_OK;
  76     }
  77
  78     WARN("Interface %s not found.\n", debugstr_guid(riid));
  79
  80     return E_NOINTERFACE;
  81 }
  82
  83 static ULONG WINAPI ID3DXMeshImpl_AddRef(ID3DXMesh *iface)
  84 {
  85     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  86
  87     TRACE("(%p)->(): AddRef from %d\n", This, This->ref);
  88
  89     return InterlockedIncrement(&This->ref);
  90 }
  91
  92 static ULONG WINAPI ID3DXMeshImpl_Release(ID3DXMesh *iface)
  93 {
  94     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  95     ULONG ref = InterlockedDecrement(&This->ref);
  96
  97     TRACE("(%p)->(): Release from %d\n", This, ref + 1);
  98
  99     if (!ref)
 100     {
 101         IDirect3DIndexBuffer9_Release(This->index_buffer);
 102         IDirect3DVertexBuffer9_Release(This->vertex_buffer);
 103         IDirect3DVertexDeclaration9_Release(This->vertex_declaration);
 104         IDirect3DDevice9_Release(This->device);
 105         HeapFree(GetProcessHeap(), 0, This->attrib_buffer);
 106         HeapFree(GetProcessHeap(), 0, This->attrib_table);
 107         HeapFree(GetProcessHeap(), 0, This);
 108     }
 109
 110     return ref;
 111 }
 112
 113 /*** ID3DXBaseMesh ***/
 114 static HRESULT WINAPI ID3DXMeshImpl_DrawSubset(ID3DXMesh *iface, DWORD attrib_id)
 115 {
 116     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 117     HRESULT hr;
 118     DWORD face_start;
 119     DWORD face_end = 0;
 120     DWORD vertex_size;
 121
 122     TRACE("(%p)->(%u)\n", This, attrib_id);
 123
 124     vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 125
 126     hr = IDirect3DDevice9_SetVertexDeclaration(This->device, This->vertex_declaration);
 127     if (FAILED(hr)) return hr;
 128     hr = IDirect3DDevice9_SetStreamSource(This->device, 0, This->vertex_buffer, 0, vertex_size);
 129     if (FAILED(hr)) return hr;
 130     hr = IDirect3DDevice9_SetIndices(This->device, This->index_buffer);
 131     if (FAILED(hr)) return hr;
 132
 133     while (face_end < This->numfaces)
 134     {
 135         for (face_start = face_end; face_start < This->numfaces; face_start++)
 136         {
 137             if (This->attrib_buffer[face_start] == attrib_id)
 138                 break;
 139         }
 140         if (face_start >= This->numfaces)
 141             break;
 142         for (face_end = face_start + 1; face_end < This->numfaces; face_end++)
 143         {
 144             if (This->attrib_buffer[face_end] != attrib_id)
 145                 break;
 146         }
 147
 148         hr = IDirect3DDevice9_DrawIndexedPrimitive(This->device, D3DPT_TRIANGLELIST,
 149                 0, 0, This->numvertices, face_start * 3, face_end - face_start);
 150         if (FAILED(hr)) return hr;
 151     }
 152
 153     return D3D_OK;
 154 }
 155
 156 static DWORD WINAPI ID3DXMeshImpl_GetNumFaces(ID3DXMesh *iface)
 157 {
 158     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 159
 160     TRACE("(%p)\n", This);
 161
 162     return This->numfaces;
 163 }
 164
 165 static DWORD WINAPI ID3DXMeshImpl_GetNumVertices(ID3DXMesh *iface)
 166 {
 167     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 168
 169     TRACE("(%p)\n", This);
 170
 171     return This->numvertices;
 172 }
 173
 174 static DWORD WINAPI ID3DXMeshImpl_GetFVF(ID3DXMesh *iface)
 175 {
 176     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 177
 178     TRACE("(%p)\n", This);
 179
 180     return This->fvf;
 181 }
 182
 183 static HRESULT WINAPI ID3DXMeshImpl_GetDeclaration(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 184 {
 185     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 186     UINT numelements;
 187
 188     TRACE("(%p)\n", This);
 189
 190     if (declaration == NULL) return D3DERR_INVALIDCALL;
 191
 192     return IDirect3DVertexDeclaration9_GetDeclaration(This->vertex_declaration,
 193                                                       declaration,
 194                                                       &numelements);
 195 }
 196
 197 static DWORD WINAPI ID3DXMeshImpl_GetNumBytesPerVertex(ID3DXMesh *iface)
 198 {
 199     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 200     UINT numelements;
 201     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
 202
 203     TRACE("iface (%p)\n", This);
 204
 205     IDirect3DVertexDeclaration9_GetDeclaration(This->vertex_declaration,
 206                                                declaration,
 207                                                &numelements);
 208     return D3DXGetDeclVertexSize(declaration, 0);
 209 }
 210
 211 static DWORD WINAPI ID3DXMeshImpl_GetOptions(ID3DXMesh *iface)
 212 {
 213     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 214
 215     TRACE("(%p)\n", This);
 216
 217     return This->options;
 218 }
 219
 220 static HRESULT WINAPI ID3DXMeshImpl_GetDevice(ID3DXMesh *iface, LPDIRECT3DDEVICE9 *device)
 221 {
 222     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 223
 224     TRACE("(%p)->(%p)\n", This, device);
 225
 226     if (device == NULL) return D3DERR_INVALIDCALL;
 227     *device = This->device;
 228     IDirect3DDevice9_AddRef(This->device);
 229
 230     return D3D_OK;
 231 }
 232
 233 static HRESULT WINAPI ID3DXMeshImpl_CloneMeshFVF(ID3DXMesh *iface, DWORD options, DWORD fvf, LPDIRECT3DDEVICE9 device, LPD3DXMESH *clone_mesh)
 234 {
 235     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 236     HRESULT hr;
 237     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
 238
 239     TRACE("(%p)->(%x,%x,%p,%p)\n", This, options, fvf, device, clone_mesh);
 240
 241     hr = D3DXDeclaratorFromFVF(fvf, declaration);
 242     if (FAILED(hr)) return hr;
 243
 244     return iface->lpVtbl->CloneMesh(iface, options, declaration, device, clone_mesh);
 245 }
 246
 247 static HRESULT WINAPI ID3DXMeshImpl_CloneMesh(ID3DXMesh *iface, DWORD options, CONST D3DVERTEXELEMENT9 *declaration, LPDIRECT3DDEVICE9 device,
 248                                               LPD3DXMESH *clone_mesh_out)
 249 {
 250     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 251     ID3DXMeshImpl *cloned_this;
 252     ID3DXMesh *clone_mesh;
 253     D3DVERTEXELEMENT9 orig_declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
 254     void *data_in, *data_out;
 255     DWORD vertex_size;
 256     HRESULT hr;
 257     int i;
 258
 259     TRACE("(%p)->(%x,%p,%p,%p)\n", This, options, declaration, device, clone_mesh_out);
 260
 261     if (!clone_mesh_out)
 262         return D3DERR_INVALIDCALL;
 263
 264     hr = iface->lpVtbl->GetDeclaration(iface, orig_declaration);
 265     if (FAILED(hr)) return hr;
 266
 267     for (i = 0; orig_declaration[i].Stream != 0xff; i++) {
 268         if (memcmp(&orig_declaration[i], &declaration[i], sizeof(*declaration)))
 269         {
 270             FIXME("Vertex buffer conversion not implemented.\n");
 271             return E_NOTIMPL;
 272         }
 273     }
 274
 275     hr = D3DXCreateMesh(This->numfaces, This->numvertices, options & ~D3DXMESH_VB_SHARE,
 276                         declaration, device, &clone_mesh);
 277     if (FAILED(hr)) return hr;
 278
 279     cloned_this = impl_from_ID3DXMesh(clone_mesh);
 280     vertex_size = clone_mesh->lpVtbl->GetNumBytesPerVertex(clone_mesh);
 281
 282     if (options & D3DXMESH_VB_SHARE) {
 283         IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
 284         /* FIXME: refactor to avoid creating a new vertex buffer */
 285         IDirect3DVertexBuffer9_Release(cloned_this->vertex_buffer);
 286         cloned_this->vertex_buffer = This->vertex_buffer;
 287     } else {
 288         hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, &data_in);
 289         if (FAILED(hr)) goto error;
 290         hr = clone_mesh->lpVtbl->LockVertexBuffer(clone_mesh, D3DLOCK_DISCARD, &data_out);
 291         if (FAILED(hr)) {
 292             iface->lpVtbl->UnlockVertexBuffer(iface);
 293             goto error;
 294         }
 295         memcpy(data_out, data_in, This->numvertices * vertex_size);
 296         clone_mesh->lpVtbl->UnlockVertexBuffer(clone_mesh);
 297         iface->lpVtbl->UnlockVertexBuffer(iface);
 298     }
 299
 300     hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, &data_in);
 301     if (FAILED(hr)) goto error;
 302     hr = clone_mesh->lpVtbl->LockIndexBuffer(clone_mesh, D3DLOCK_DISCARD, &data_out);
 303     if (FAILED(hr)) {
 304         iface->lpVtbl->UnlockIndexBuffer(iface);
 305         goto error;
 306     }
 307     if ((options ^ This->options) & D3DXMESH_32BIT) {
 308         if (options & D3DXMESH_32BIT) {
 309             for (i = 0; i < This->numfaces * 3; i++)
 310                 ((DWORD*)data_out)[i] = ((WORD*)data_in)[i];
 311         } else {
 312             for (i = 0; i < This->numfaces * 3; i++)
 313                 ((WORD*)data_out)[i] = ((DWORD*)data_in)[i];
 314         }
 315     } else {
 316         memcpy(data_out, data_in, This->numfaces * 3 * (options & D3DXMESH_32BIT ? 4 : 2));
 317     }
 318     clone_mesh->lpVtbl->UnlockIndexBuffer(clone_mesh);
 319     iface->lpVtbl->UnlockIndexBuffer(iface);
 320
 321     memcpy(cloned_this->attrib_buffer, This->attrib_buffer, This->numfaces * sizeof(*This->attrib_buffer));
 322
 323     if (This->attrib_table_size)
 324     {
 325         cloned_this->attrib_table_size = This->attrib_table_size;
 326         cloned_this->attrib_table = HeapAlloc(GetProcessHeap(), 0, This->attrib_table_size * sizeof(*This->attrib_table));
 327         if (!cloned_this->attrib_table) {
 328             hr = E_OUTOFMEMORY;
 329             goto error;
 330         }
 331         memcpy(cloned_this->attrib_table, This->attrib_table, This->attrib_table_size * sizeof(*This->attrib_table));
 332     }
 333
 334     *clone_mesh_out = clone_mesh;
 335
 336     return D3D_OK;
 337 error:
 338     IUnknown_Release(clone_mesh);
 339     return hr;
 340 }
 341
 342 static HRESULT WINAPI ID3DXMeshImpl_GetVertexBuffer(ID3DXMesh *iface, LPDIRECT3DVERTEXBUFFER9 *vertex_buffer)
 343 {
 344     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 345
 346     TRACE("(%p)->(%p)\n", This, vertex_buffer);
 347
 348     if (vertex_buffer == NULL) return D3DERR_INVALIDCALL;
 349     *vertex_buffer = This->vertex_buffer;
 350     IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
 351
 352     return D3D_OK;
 353 }
 354
 355 static HRESULT WINAPI ID3DXMeshImpl_GetIndexBuffer(ID3DXMesh *iface, LPDIRECT3DINDEXBUFFER9 *index_buffer)
 356 {
 357     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 358
 359     TRACE("(%p)->(%p)\n", This, index_buffer);
 360
 361     if (index_buffer == NULL) return D3DERR_INVALIDCALL;
 362     *index_buffer = This->index_buffer;
 363     IDirect3DIndexBuffer9_AddRef(This->index_buffer);
 364
 365     return D3D_OK;
 366 }
 367
 368 static HRESULT WINAPI ID3DXMeshImpl_LockVertexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 369 {
 370     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 371
 372     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 373
 374     return IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, data, flags);
 375 }
 376
 377 static HRESULT WINAPI ID3DXMeshImpl_UnlockVertexBuffer(ID3DXMesh *iface)
 378 {
 379     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 380
 381     TRACE("(%p)\n", This);
 382
 383     return IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
 384 }
 385
 386 static HRESULT WINAPI ID3DXMeshImpl_LockIndexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 387 {
 388     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 389
 390     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 391
 392     return IDirect3DIndexBuffer9_Lock(This->index_buffer, 0, 0, data, flags);
 393 }
 394
 395 static HRESULT WINAPI ID3DXMeshImpl_UnlockIndexBuffer(ID3DXMesh *iface)
 396 {
 397     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 398
 399     TRACE("(%p)\n", This);
 400
 401     return IDirect3DIndexBuffer9_Unlock(This->index_buffer);
 402 }
 403
 404 static HRESULT WINAPI ID3DXMeshImpl_GetAttributeTable(ID3DXMesh *iface, D3DXATTRIBUTERANGE *attrib_table, DWORD *attrib_table_size)
 405 {
 406     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 407
 408     TRACE("(%p)->(%p,%p)\n", This, attrib_table, attrib_table_size);
 409
 410     if (attrib_table_size)
 411         *attrib_table_size = This->attrib_table_size;
 412
 413     if (attrib_table)
 414         CopyMemory(attrib_table, This->attrib_table, This->attrib_table_size * sizeof(*attrib_table));
 415
 416     return D3D_OK;
 417 }
 418
 419 static HRESULT WINAPI ID3DXMeshImpl_ConvertPointRepsToAdjacency(ID3DXMesh *iface, CONST DWORD *point_reps, DWORD *adjacency)
 420 {
 421     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 422
 423     FIXME("(%p)->(%p,%p): stub\n", This, point_reps, adjacency);
 424
 425     return E_NOTIMPL;
 426 }
 427
 428 static HRESULT WINAPI ID3DXMeshImpl_ConvertAdjacencyToPointReps(ID3DXMesh *iface, CONST DWORD *adjacency, DWORD *point_reps)
 429 {
 430     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 431
 432     FIXME("(%p)->(%p,%p): stub\n", This, adjacency, point_reps);
 433
 434     return E_NOTIMPL;
 435 }
 436
 437 struct vertex_metadata {
 438   float key;
 439   DWORD vertex_index;
 440   DWORD first_shared_index;
 441 };
 442
 443 static int compare_vertex_keys(const void *a, const void *b)
 444 {
 445     const struct vertex_metadata *left = a;
 446     const struct vertex_metadata *right = b;
 447     if (left->key == right->key)
 448         return 0;
 449     return left->key < right->key ? -1 : 1;
 450 }
 451
 452 static HRESULT WINAPI ID3DXMeshImpl_GenerateAdjacency(ID3DXMesh *iface, FLOAT epsilon, DWORD *adjacency)
 453 {
 454     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 455     HRESULT hr;
 456     BYTE *vertices = NULL;
 457     const DWORD *indices = NULL;
 458     DWORD vertex_size;
 459     DWORD buffer_size;
 460     /* sort the vertices by (x + y + z) to quickly find coincident vertices */
 461     struct vertex_metadata *sorted_vertices;
 462     /* shared_indices links together identical indices in the index buffer so
 463      * that adjacency checks can be limited to faces sharing a vertex */
 464     DWORD *shared_indices = NULL;
 465     const FLOAT epsilon_sq = epsilon * epsilon;
 466     int i;
 467
 468     TRACE("(%p)->(%f,%p)\n", This, epsilon, adjacency);
 469
 470     if (!adjacency)
 471         return D3DERR_INVALIDCALL;
 472
 473     buffer_size = This->numfaces * 3 * sizeof(*shared_indices) + This->numvertices * sizeof(*sorted_vertices);
 474     if (!(This->options & D3DXMESH_32BIT))
 475         buffer_size += This->numfaces * 3 * sizeof(*indices);
 476     shared_indices = HeapAlloc(GetProcessHeap(), 0, buffer_size);
 477     if (!shared_indices)
 478         return E_OUTOFMEMORY;
 479     sorted_vertices = (struct vertex_metadata*)(shared_indices + This->numfaces * 3);
 480
 481     hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, (void**)&vertices);
 482     if (FAILED(hr)) goto cleanup;
 483     hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices);
 484     if (FAILED(hr)) goto cleanup;
 485
 486     if (!(This->options & D3DXMESH_32BIT)) {
 487         const WORD *word_indices = (const WORD*)indices;
 488         DWORD *dword_indices = (DWORD*)(sorted_vertices + This->numvertices);
 489         indices = dword_indices;
 490         for (i = 0; i < This->numfaces * 3; i++)
 491             *dword_indices++ = *word_indices++;
 492     }
 493
 494     vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 495     for (i = 0; i < This->numvertices; i++) {
 496         D3DXVECTOR3 *vertex = (D3DXVECTOR3*)(vertices + vertex_size * i);
 497         sorted_vertices[i].first_shared_index = -1;
 498         sorted_vertices[i].key = vertex->x + vertex->y + vertex->z;
 499         sorted_vertices[i].vertex_index = i;
 500     }
 501     for (i = 0; i < This->numfaces * 3; i++) {
 502         DWORD *first_shared_index = &sorted_vertices[indices[i]].first_shared_index;
 503         shared_indices[i] = *first_shared_index;
 504         *first_shared_index = i;
 505         adjacency[i] = -1;
 506     }
 507     qsort(sorted_vertices, This->numvertices, sizeof(*sorted_vertices), compare_vertex_keys);
 508
 509     for (i = 0; i < This->numvertices; i++) {
 510         struct vertex_metadata *sorted_vertex_a = &sorted_vertices[i];
 511         D3DXVECTOR3 *vertex_a = (D3DXVECTOR3*)(vertices + sorted_vertex_a->vertex_index * vertex_size);
 512         DWORD shared_index_a = sorted_vertex_a->first_shared_index;
 513
 514         while (shared_index_a != -1) {
 515             int j = i;
 516             DWORD shared_index_b = shared_indices[shared_index_a];
 517             struct vertex_metadata *sorted_vertex_b = sorted_vertex_a;
 518
 519             while (TRUE) {
 520                 while (shared_index_b != -1) {
 521                     /* faces are adjacent if they have another coincident vertex */
 522                     DWORD base_a = (shared_index_a / 3) * 3;
 523                     DWORD base_b = (shared_index_b / 3) * 3;
 524                     BOOL adjacent = FALSE;
 525                     int k;
 526
 527                     for (k = 0; k < 3; k++) {
 528                         if (adjacency[base_b + k] == shared_index_a / 3) {
 529                             adjacent = TRUE;
 530                             break;
 531                         }
 532                     }
 533                     if (!adjacent) {
 534                         for (k = 1; k <= 2; k++) {
 535                             DWORD vertex_index_a = base_a + (shared_index_a + k) % 3;
 536                             DWORD vertex_index_b = base_b + (shared_index_b + (3 - k)) % 3;
 537                             adjacent = indices[vertex_index_a] == indices[vertex_index_b];
 538                             if (!adjacent && epsilon >= 0.0f) {
 539                                 D3DXVECTOR3 delta = {0.0f, 0.0f, 0.0f};
 540                                 FLOAT length_sq;
 541
 542                                 D3DXVec3Subtract(&delta,
 543                                                  (D3DXVECTOR3*)(vertices + indices[vertex_index_a] * vertex_size),
 544                                                  (D3DXVECTOR3*)(vertices + indices[vertex_index_b] * vertex_size));
 545                                 length_sq = D3DXVec3LengthSq(&delta);
 546                                 adjacent = epsilon == 0.0f ? length_sq == 0.0f : length_sq < epsilon_sq;
 547                             }
 548                             if (adjacent) {
 549                                 DWORD adj_a = base_a + 2 - (vertex_index_a + shared_index_a + 1) % 3;
 550                                 DWORD adj_b = base_b + 2 - (vertex_index_b + shared_index_b + 1) % 3;
 551                                 if (adjacency[adj_a] == -1 && adjacency[adj_b] == -1) {
 552                                     adjacency[adj_a] = base_b / 3;
 553                                     adjacency[adj_b] = base_a / 3;
 554                                     break;
 555                                 }
 556                             }
 557                         }
 558                     }
 559
 560                     shared_index_b = shared_indices[shared_index_b];
 561                 }
 562                 while (++j < This->numvertices) {
 563                     D3DXVECTOR3 *vertex_b;
 564
 565                     sorted_vertex_b++;
 566                     if (sorted_vertex_b->key - sorted_vertex_a->key > epsilon * 3.0f) {
 567                         /* no more coincident vertices to try */
 568                         j = This->numvertices;
 569                         break;
 570                     }
 571                     /* check for coincidence */
 572                     vertex_b = (D3DXVECTOR3*)(vertices + sorted_vertex_b->vertex_index * vertex_size);
 573                     if (fabsf(vertex_a->x - vertex_b->x) <= epsilon &&
 574                         fabsf(vertex_a->y - vertex_b->y) <= epsilon &&
 575                         fabsf(vertex_a->z - vertex_b->z) <= epsilon)
 576                     {
 577                         break;
 578                     }
 579                 }
 580                 if (j >= This->numvertices)
 581                     break;
 582                 shared_index_b = sorted_vertex_b->first_shared_index;
 583             }
 584
 585             sorted_vertex_a->first_shared_index = shared_indices[sorted_vertex_a->first_shared_index];
 586             shared_index_a = sorted_vertex_a->first_shared_index;
 587         }
 588     }
 589
 590     hr = D3D_OK;
 591 cleanup:
 592     if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
 593     if (vertices) iface->lpVtbl->UnlockVertexBuffer(iface);
 594     HeapFree(GetProcessHeap(), 0, shared_indices);
 595     return hr;
 596 }
 597
 598 static HRESULT WINAPI ID3DXMeshImpl_UpdateSemantics(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 599 {
 600     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 601
 602     FIXME("(%p)->(%p): stub\n", This, declaration);
 603
 604     return E_NOTIMPL;
 605 }
 606
 607 /*** ID3DXMesh ***/
 608 static HRESULT WINAPI ID3DXMeshImpl_LockAttributeBuffer(ID3DXMesh *iface, DWORD flags, DWORD **data)
 609 {
 610     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 611
 612     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 613
 614     InterlockedIncrement(&This->attrib_buffer_lock_count);
 615
 616     if (!(flags & D3DLOCK_READONLY)) {
 617         D3DXATTRIBUTERANGE *attrib_table = This->attrib_table;
 618         This->attrib_table_size = 0;
 619         This->attrib_table = NULL;
 620         HeapFree(GetProcessHeap(), 0, attrib_table);
 621     }
 622
 623     *data = This->attrib_buffer;
 624
 625     return D3D_OK;
 626 }
 627
 628 static HRESULT WINAPI ID3DXMeshImpl_UnlockAttributeBuffer(ID3DXMesh *iface)
 629 {
 630     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 631     int lock_count;
 632
 633     TRACE("(%p)\n", This);
 634
 635     lock_count = InterlockedDecrement(&This->attrib_buffer_lock_count);
 636
 637     if (lock_count < 0) {
 638         InterlockedIncrement(&This->attrib_buffer_lock_count);
 639         return D3DERR_INVALIDCALL;
 640     }
 641
 642     return D3D_OK;
 643 }
 644
 645 static HRESULT WINAPI ID3DXMeshImpl_Optimize(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
 646                                              DWORD *face_remap, LPD3DXBUFFER *vertex_remap, LPD3DXMESH *opt_mesh)
 647 {
 648     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 649     HRESULT hr;
 650     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
 651     ID3DXMesh *optimized_mesh;
 652
 653     TRACE("(%p)->(%x,%p,%p,%p,%p,%p)\n", This, flags, adjacency_in, adjacency_out, face_remap, vertex_remap, opt_mesh);
 654
 655     if (!opt_mesh)
 656         return D3DERR_INVALIDCALL;
 657
 658     hr = iface->lpVtbl->GetDeclaration(iface, declaration);
 659     if (FAILED(hr)) return hr;
 660
 661     hr = iface->lpVtbl->CloneMesh(iface, This->options, declaration, This->device, &optimized_mesh);
 662     if (FAILED(hr)) return hr;
 663
 664     hr = optimized_mesh->lpVtbl->OptimizeInplace(optimized_mesh, flags, adjacency_in, adjacency_out, face_remap, vertex_remap);
 665     if (SUCCEEDED(hr))
 666         *opt_mesh = optimized_mesh;
 667     else
 668         IUnknown_Release(optimized_mesh);
 669     return hr;
 670 }
 671
 672 /* Creates a vertex_remap that removes unused vertices.
 673  * Indices are updated according to the vertex_remap. */
 674 static HRESULT compact_mesh(ID3DXMeshImpl *This, DWORD *indices, DWORD *new_num_vertices, ID3DXBuffer **vertex_remap)
 675 {
 676     HRESULT hr;
 677     DWORD *vertex_remap_ptr;
 678     DWORD num_used_vertices;
 679     DWORD i;
 680
 681     hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), vertex_remap);
 682     if (FAILED(hr)) return hr;
 683     vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(*vertex_remap);
 684
 685     for (i = 0; i < This->numfaces * 3; i++)
 686         vertex_remap_ptr[indices[i]] = 1;
 687
 688     /* create old->new vertex mapping */
 689     num_used_vertices = 0;
 690     for (i = 0; i < This->numvertices; i++) {
 691         if (vertex_remap_ptr[i])
 692             vertex_remap_ptr[i] = num_used_vertices++;
 693         else
 694             vertex_remap_ptr[i] = -1;
 695     }
 696     /* convert indices */
 697     for (i = 0; i < This->numfaces * 3; i++)
 698         indices[i] = vertex_remap_ptr[indices[i]];
 699
 700     /* create new->old vertex mapping */
 701     num_used_vertices = 0;
 702     for (i = 0; i < This->numvertices; i++) {
 703         if (vertex_remap_ptr[i] != -1)
 704             vertex_remap_ptr[num_used_vertices++] = i;
 705     }
 706     for (i = num_used_vertices; i < This->numvertices; i++)
 707         vertex_remap_ptr[i] = -1;
 708
 709     *new_num_vertices = num_used_vertices;
 710
 711     return D3D_OK;
 712 }
 713
 714 /* count the number of unique attribute values in a sorted attribute buffer */
 715 static DWORD count_attributes(const DWORD *attrib_buffer, DWORD numfaces)
 716 {
 717     DWORD last_attribute = attrib_buffer[0];
 718     DWORD attrib_table_size = 1;
 719     DWORD i;
 720     for (i = 1; i < numfaces; i++) {
 721         if (attrib_buffer[i] != last_attribute) {
 722             last_attribute = attrib_buffer[i];
 723             attrib_table_size++;
 724         }
 725     }
 726     return attrib_table_size;
 727 }
 728
 729 static void fill_attribute_table(DWORD *attrib_buffer, DWORD numfaces, void *indices,
 730                                  BOOL is_32bit_indices, D3DXATTRIBUTERANGE *attrib_table)
 731 {
 732     DWORD attrib_table_size = 0;
 733     DWORD last_attribute = attrib_buffer[0];
 734     DWORD min_vertex, max_vertex;
 735     DWORD i;
 736
 737     attrib_table[0].AttribId = last_attribute;
 738     attrib_table[0].FaceStart = 0;
 739     min_vertex = (DWORD)-1;
 740     max_vertex = 0;
 741     for (i = 0; i < numfaces; i++) {
 742         DWORD j;
 743
 744         if (attrib_buffer[i] != last_attribute) {
 745             last_attribute = attrib_buffer[i];
 746             attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
 747             attrib_table[attrib_table_size].VertexStart = min_vertex;
 748             attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
 749             attrib_table_size++;
 750             attrib_table[attrib_table_size].AttribId = attrib_buffer[i];
 751             attrib_table[attrib_table_size].FaceStart = i;
 752             min_vertex = (DWORD)-1;
 753             max_vertex = 0;
 754         }
 755         for (j = 0; j < 3; j++) {
 756             DWORD vertex_index = is_32bit_indices ? ((DWORD*)indices)[i * 3 + j] : ((WORD*)indices)[i * 3 + j];
 757             if (vertex_index < min_vertex)
 758                 min_vertex = vertex_index;
 759             if (vertex_index > max_vertex)
 760                 max_vertex = vertex_index;
 761         }
 762     }
 763     attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
 764     attrib_table[attrib_table_size].VertexStart = min_vertex;
 765     attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
 766     attrib_table_size++;
 767 }
 768
 769 static int attrib_entry_compare(const DWORD **a, const DWORD **b)
 770 {
 771     const DWORD *ptr_a = *a;
 772     const DWORD *ptr_b = *b;
 773     int delta = *ptr_a - *ptr_b;
 774
 775     if (delta)
 776         return delta;
 777
 778     delta = ptr_a - ptr_b; /* for stable sort */
 779     return delta;
 780 }
 781
 782 /* Create face_remap, a new attribute buffer for attribute sort optimization. */
 783 static HRESULT remap_faces_for_attrsort(ID3DXMeshImpl *This, const DWORD *indices,
 784         const DWORD *attrib_buffer, DWORD **sorted_attrib_buffer, DWORD **face_remap)
 785 {
 786     const DWORD **sorted_attrib_ptr_buffer = NULL;
 787     DWORD i;
 788
 789     *face_remap = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(**face_remap));
 790     sorted_attrib_ptr_buffer = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(*sorted_attrib_ptr_buffer));
 791     if (!*face_remap || !sorted_attrib_ptr_buffer) {
 792         HeapFree(GetProcessHeap(), 0, sorted_attrib_ptr_buffer);
 793         return E_OUTOFMEMORY;
 794     }
 795     for (i = 0; i < This->numfaces; i++)
 796         sorted_attrib_ptr_buffer[i] = &attrib_buffer[i];
 797     qsort(sorted_attrib_ptr_buffer, This->numfaces, sizeof(*sorted_attrib_ptr_buffer),
 798          (int(*)(const void *, const void *))attrib_entry_compare);
 799
 800     for (i = 0; i < This->numfaces; i++)
 801     {
 802         DWORD old_face = sorted_attrib_ptr_buffer[i] - attrib_buffer;
 803         (*face_remap)[old_face] = i;
 804     }
 805
 806     /* overwrite sorted_attrib_ptr_buffer with the values themselves */
 807     *sorted_attrib_buffer = (DWORD*)sorted_attrib_ptr_buffer;
 808     for (i = 0; i < This->numfaces; i++)
 809         (*sorted_attrib_buffer)[(*face_remap)[i]] = attrib_buffer[i];
 810
 811     return D3D_OK;
 812 }
 813
 814 static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
 815                                                     DWORD *face_remap_out, LPD3DXBUFFER *vertex_remap_out)
 816 {
 817     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 818     void *indices = NULL;
 819     DWORD *attrib_buffer = NULL;
 820     HRESULT hr;
 821     ID3DXBuffer *vertex_remap = NULL;
 822     DWORD *face_remap = NULL; /* old -> new mapping */
 823     DWORD *dword_indices = NULL;
 824     DWORD new_num_vertices = 0;
 825     DWORD new_num_alloc_vertices = 0;
 826     IDirect3DVertexBuffer9 *vertex_buffer = NULL;
 827     DWORD *sorted_attrib_buffer = NULL;
 828     DWORD i;
 829
 830     TRACE("(%p)->(%x,%p,%p,%p,%p)\n", This, flags, adjacency_in, adjacency_out, face_remap_out, vertex_remap_out);
 831
 832     if (!flags)
 833         return D3DERR_INVALIDCALL;
 834     if (!adjacency_in && (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)))
 835         return D3DERR_INVALIDCALL;
 836     if ((flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)) == (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
 837         return D3DERR_INVALIDCALL;
 838
 839     if (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
 840     {
 841         if (flags & D3DXMESHOPT_VERTEXCACHE)
 842             FIXME("D3DXMESHOPT_VERTEXCACHE not implemented.\n");
 843         if (flags & D3DXMESHOPT_STRIPREORDER)
 844             FIXME("D3DXMESHOPT_STRIPREORDER not implemented.\n");
 845         return E_NOTIMPL;
 846     }
 847
 848     hr = iface->lpVtbl->LockIndexBuffer(iface, 0, (void**)&indices);
 849     if (FAILED(hr)) goto cleanup;
 850
 851     dword_indices = HeapAlloc(GetProcessHeap(), 0, This->numfaces * 3 * sizeof(DWORD));
 852     if (!dword_indices) return E_OUTOFMEMORY;
 853     if (This->options & D3DXMESH_32BIT) {
 854         memcpy(dword_indices, indices, This->numfaces * 3 * sizeof(DWORD));
 855     } else {
 856         WORD *word_indices = indices;
 857         for (i = 0; i < This->numfaces * 3; i++)
 858             dword_indices[i] = *word_indices++;
 859     }
 860
 861     if ((flags & (D3DXMESHOPT_COMPACT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_ATTRSORT)) == D3DXMESHOPT_COMPACT)
 862     {
 863         new_num_alloc_vertices = This->numvertices;
 864         hr = compact_mesh(This, dword_indices, &new_num_vertices, &vertex_remap);
 865         if (FAILED(hr)) goto cleanup;
 866     } else if (flags & D3DXMESHOPT_ATTRSORT) {
 867         if (!(flags & D3DXMESHOPT_IGNOREVERTS))
 868         {
 869             FIXME("D3DXMESHOPT_ATTRSORT vertex reordering not implemented.\n");
 870             hr = E_NOTIMPL;
 871             goto cleanup;
 872         }
 873
 874         hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
 875         if (FAILED(hr)) goto cleanup;
 876
 877         hr = remap_faces_for_attrsort(This, dword_indices, attrib_buffer, &sorted_attrib_buffer, &face_remap);
 878         if (FAILED(hr)) goto cleanup;
 879     }
 880
 881     if (vertex_remap)
 882     {
 883         /* reorder the vertices using vertex_remap */
 884         D3DVERTEXBUFFER_DESC vertex_desc;
 885         DWORD *vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
 886         DWORD vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 887         BYTE *orig_vertices;
 888         BYTE *new_vertices;
 889
 890         hr = IDirect3DVertexBuffer9_GetDesc(This->vertex_buffer, &vertex_desc);
 891         if (FAILED(hr)) goto cleanup;
 892
 893         hr = IDirect3DDevice9_CreateVertexBuffer(This->device, new_num_alloc_vertices * vertex_size,
 894                 vertex_desc.Usage, This->fvf, vertex_desc.Pool, &vertex_buffer, NULL);
 895         if (FAILED(hr)) goto cleanup;
 896
 897         hr = IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, (void**)&orig_vertices, D3DLOCK_READONLY);
 898         if (FAILED(hr)) goto cleanup;
 899
 900         hr = IDirect3DVertexBuffer9_Lock(vertex_buffer, 0, 0, (void**)&new_vertices, D3DLOCK_DISCARD);
 901         if (FAILED(hr)) {
 902             IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
 903             goto cleanup;
 904         }
 905
 906         for (i = 0; i < new_num_vertices; i++)
 907             memcpy(new_vertices + i * vertex_size, orig_vertices + vertex_remap_ptr[i] * vertex_size, vertex_size);
 908
 909         IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
 910         IDirect3DVertexBuffer9_Unlock(vertex_buffer);
 911     } else if (vertex_remap_out) {
 912         DWORD *vertex_remap_ptr;
 913
 914         hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), &vertex_remap);
 915         if (FAILED(hr)) goto cleanup;
 916         vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
 917         for (i = 0; i < This->numvertices; i++)
 918             *vertex_remap_ptr++ = i;
 919     }
 920
 921     if (flags & D3DXMESHOPT_ATTRSORT)
 922     {
 923         D3DXATTRIBUTERANGE *attrib_table;
 924         DWORD attrib_table_size;
 925
 926         attrib_table_size = count_attributes(sorted_attrib_buffer, This->numfaces);
 927         attrib_table = HeapAlloc(GetProcessHeap(), 0, attrib_table_size * sizeof(*attrib_table));
 928         if (!attrib_table) {
 929             hr = E_OUTOFMEMORY;
 930             goto cleanup;
 931         }
 932
 933         memcpy(attrib_buffer, sorted_attrib_buffer, This->numfaces * sizeof(*attrib_buffer));
 934
 935         /* reorder the indices using face_remap */
 936         if (This->options & D3DXMESH_32BIT) {
 937             for (i = 0; i < This->numfaces; i++)
 938                 memcpy((DWORD*)indices + face_remap[i] * 3, dword_indices + i * 3, 3 * sizeof(DWORD));
 939         } else {
 940             WORD *word_indices = indices;
 941             for (i = 0; i < This->numfaces; i++) {
 942                 DWORD new_pos = face_remap[i] * 3;
 943                 DWORD old_pos = i * 3;
 944                 word_indices[new_pos++] = dword_indices[old_pos++];
 945                 word_indices[new_pos++] = dword_indices[old_pos++];
 946                 word_indices[new_pos] = dword_indices[old_pos];
 947             }
 948         }
 949
 950         fill_attribute_table(attrib_buffer, This->numfaces, indices,
 951                              This->options & D3DXMESH_32BIT, attrib_table);
 952
 953         HeapFree(GetProcessHeap(), 0, This->attrib_table);
 954         This->attrib_table = attrib_table;
 955         This->attrib_table_size = attrib_table_size;
 956     } else {
 957         if (This->options & D3DXMESH_32BIT) {
 958             memcpy(indices, dword_indices, This->numfaces * 3 * sizeof(DWORD));
 959         } else {
 960             WORD *word_indices = indices;
 961             for (i = 0; i < This->numfaces * 3; i++)
 962                 *word_indices++ = dword_indices[i];
 963         }
 964     }
 965
 966     if (adjacency_out) {
 967         if (face_remap) {
 968             for (i = 0; i < This->numfaces; i++) {
 969                 DWORD old_pos = i * 3;
 970                 DWORD new_pos = face_remap[i] * 3;
 971                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
 972                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
 973                 adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
 974             }
 975         } else {
 976             memcpy(adjacency_out, adjacency_in, This->numfaces * 3 * sizeof(*adjacency_out));
 977         }
 978     }
 979     if (face_remap_out) {
 980         if (face_remap) {
 981             for (i = 0; i < This->numfaces; i++)
 982                 face_remap_out[face_remap[i]] = i;
 983         } else {
 984             for (i = 0; i < This->numfaces; i++)
 985                 face_remap_out[i] = i;
 986         }
 987     }
 988     if (vertex_remap_out)
 989         *vertex_remap_out = vertex_remap;
 990     vertex_remap = NULL;
 991
 992     if (vertex_buffer) {
 993         IDirect3DVertexBuffer9_Release(This->vertex_buffer);
 994         This->vertex_buffer = vertex_buffer;
 995         vertex_buffer = NULL;
 996         This->numvertices = new_num_vertices;
 997     }
 998
 999     hr = D3D_OK;
1000 cleanup:
1001     HeapFree(GetProcessHeap(), 0, sorted_attrib_buffer);
1002     HeapFree(GetProcessHeap(), 0, face_remap);
1003     HeapFree(GetProcessHeap(), 0, dword_indices);
1004     if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
1005     if (vertex_buffer) IDirect3DVertexBuffer9_Release(vertex_buffer);
1006     if (attrib_buffer) iface->lpVtbl->UnlockAttributeBuffer(iface);
1007     if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
1008     return hr;
1009 }
1010
1011 static HRESULT WINAPI ID3DXMeshImpl_SetAttributeTable(ID3DXMesh *iface, CONST D3DXATTRIBUTERANGE *attrib_table, DWORD attrib_table_size)
1012 {
1013     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
1014     D3DXATTRIBUTERANGE *new_table = NULL;
1015
1016     TRACE("(%p)->(%p,%u)\n", This, attrib_table, attrib_table_size);
1017
1018     if (attrib_table_size) {
1019         size_t size = attrib_table_size * sizeof(*attrib_table);
1020
1021         new_table = HeapAlloc(GetProcessHeap(), 0, size);
1022         if (!new_table)
1023             return E_OUTOFMEMORY;
1024
1025         CopyMemory(new_table, attrib_table, size);
1026     } else if (attrib_table) {
1027         return D3DERR_INVALIDCALL;
1028     }
1029     HeapFree(GetProcessHeap(), 0, This->attrib_table);
1030     This->attrib_table = new_table;
1031     This->attrib_table_size = attrib_table_size;
1032
1033     return D3D_OK;
1034 }
1035
1036 static const struct ID3DXMeshVtbl D3DXMesh_Vtbl =
1037 {
1038     /*** IUnknown methods ***/
1039     ID3DXMeshImpl_QueryInterface,
1040     ID3DXMeshImpl_AddRef,
1041     ID3DXMeshImpl_Release,
1042     /*** ID3DXBaseMesh ***/
1043     ID3DXMeshImpl_DrawSubset,
1044     ID3DXMeshImpl_GetNumFaces,
1045     ID3DXMeshImpl_GetNumVertices,
1046     ID3DXMeshImpl_GetFVF,
1047     ID3DXMeshImpl_GetDeclaration,
1048     ID3DXMeshImpl_GetNumBytesPerVertex,
1049     ID3DXMeshImpl_GetOptions,
1050     ID3DXMeshImpl_GetDevice,
1051     ID3DXMeshImpl_CloneMeshFVF,
1052     ID3DXMeshImpl_CloneMesh,
1053     ID3DXMeshImpl_GetVertexBuffer,
1054     ID3DXMeshImpl_GetIndexBuffer,
1055     ID3DXMeshImpl_LockVertexBuffer,
1056     ID3DXMeshImpl_UnlockVertexBuffer,
1057     ID3DXMeshImpl_LockIndexBuffer,
1058     ID3DXMeshImpl_UnlockIndexBuffer,
1059     ID3DXMeshImpl_GetAttributeTable,
1060     ID3DXMeshImpl_ConvertPointRepsToAdjacency,
1061     ID3DXMeshImpl_ConvertAdjacencyToPointReps,
1062     ID3DXMeshImpl_GenerateAdjacency,
1063     ID3DXMeshImpl_UpdateSemantics,
1064     /*** ID3DXMesh ***/
1065     ID3DXMeshImpl_LockAttributeBuffer,
1066     ID3DXMeshImpl_UnlockAttributeBuffer,
1067     ID3DXMeshImpl_Optimize,
1068     ID3DXMeshImpl_OptimizeInplace,
1069     ID3DXMeshImpl_SetAttributeTable
1070 };
1071
1072 /*************************************************************************
1073  * D3DXBoxBoundProbe
1074  */
1075 BOOL WINAPI D3DXBoxBoundProbe(CONST D3DXVECTOR3 *pmin, CONST D3DXVECTOR3 *pmax, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
1076
1077 /* Algorithm taken from the article: An Efficient and Robust Ray-Box Intersection Algoritm
1078 Amy Williams             University of Utah
1079 Steve Barrus             University of Utah
1080 R. Keith Morley          University of Utah
1081 Peter Shirley            University of Utah
1082
1083 International Conference on Computer Graphics and Interactive Techniques  archive
1084 ACM SIGGRAPH 2005 Courses
1085 Los Angeles, California
1086
1087 This algorithm is free of patents or of copyrights, as confirmed by Peter Shirley himself.
1088
1089 Algorithm: Consider the box as the intersection of three slabs. Clip the ray
1090 against each slab, if there's anything left of the ray after we're
1091 done we've got an intersection of the ray with the box.
1092 */
1093
1094 {
1095     FLOAT div, tmin, tmax, tymin, tymax, tzmin, tzmax;
1096
1097     div = 1.0f / praydirection->x;
1098     if ( div >= 0.0f )
1099     {
1100         tmin = ( pmin->x - prayposition->x ) * div;
1101         tmax = ( pmax->x - prayposition->x ) * div;
1102     }
1103     else
1104     {
1105         tmin = ( pmax->x - prayposition->x ) * div;
1106         tmax = ( pmin->x - prayposition->x ) * div;
1107     }
1108
1109     if ( tmax < 0.0f ) return FALSE;
1110
1111     div = 1.0f / praydirection->y;
1112     if ( div >= 0.0f )
1113     {
1114         tymin = ( pmin->y - prayposition->y ) * div;
1115         tymax = ( pmax->y - prayposition->y ) * div;
1116     }
1117     else
1118     {
1119         tymin = ( pmax->y - prayposition->y ) * div;
1120         tymax = ( pmin->y - prayposition->y ) * div;
1121     }
1122
1123     if ( ( tymax < 0.0f ) || ( tmin > tymax ) || ( tymin > tmax ) ) return FALSE;
1124
1125     if ( tymin > tmin ) tmin = tymin;
1126     if ( tymax < tmax ) tmax = tymax;
1127
1128     div = 1.0f / praydirection->z;
1129     if ( div >= 0.0f )
1130     {
1131         tzmin = ( pmin->z - prayposition->z ) * div;
1132         tzmax = ( pmax->z - prayposition->z ) * div;
1133     }
1134     else
1135     {
1136         tzmin = ( pmax->z - prayposition->z ) * div;
1137         tzmax = ( pmin->z - prayposition->z ) * div;
1138     }
1139
1140     if ( (tzmax < 0.0f ) || ( tmin > tzmax ) || ( tzmin > tmax ) ) return FALSE;
1141
1142     return TRUE;
1143 }
1144
1145 /*************************************************************************
1146  * D3DXComputeBoundingBox
1147  */
1148 HRESULT WINAPI D3DXComputeBoundingBox(CONST D3DXVECTOR3 *pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pmin, D3DXVECTOR3 *pmax)
1149 {
1150     D3DXVECTOR3 vec;
1151     unsigned int i;
1152
1153     if( !pfirstposition || !pmin || !pmax ) return D3DERR_INVALIDCALL;
1154
1155     *pmin = *pfirstposition;
1156     *pmax = *pmin;
1157
1158     for(i=0; i<numvertices; i++)
1159     {
1160         vec = *( (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i) );
1161
1162         if ( vec.x < pmin->x ) pmin->x = vec.x;
1163         if ( vec.x > pmax->x ) pmax->x = vec.x;
1164
1165         if ( vec.y < pmin->y ) pmin->y = vec.y;
1166         if ( vec.y > pmax->y ) pmax->y = vec.y;
1167
1168         if ( vec.z < pmin->z ) pmin->z = vec.z;
1169         if ( vec.z > pmax->z ) pmax->z = vec.z;
1170     }
1171
1172     return D3D_OK;
1173 }
1174
1175 /*************************************************************************
1176  * D3DXComputeBoundingSphere
1177  */
1178 HRESULT WINAPI D3DXComputeBoundingSphere(CONST D3DXVECTOR3* pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pcenter, FLOAT *pradius)
1179 {
1180     D3DXVECTOR3 temp, temp1;
1181     FLOAT d;
1182     unsigned int i;
1183
1184     if( !pfirstposition || !pcenter || !pradius ) return D3DERR_INVALIDCALL;
1185
1186     temp.x = 0.0f;
1187     temp.y = 0.0f;
1188     temp.z = 0.0f;
1189     temp1 = temp;
1190     *pradius = 0.0f;
1191
1192     for(i=0; i<numvertices; i++)
1193     {
1194         D3DXVec3Add(&temp1, &temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i));
1195         temp = temp1;
1196     }
1197
1198     D3DXVec3Scale(pcenter, &temp, 1.0f/((FLOAT)numvertices));
1199
1200     for(i=0; i<numvertices; i++)
1201     {
1202         d = D3DXVec3Length(D3DXVec3Subtract(&temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i), pcenter));
1203         if ( d > *pradius ) *pradius = d;
1204     }
1205     return D3D_OK;
1206 }
1207
1208 static const UINT d3dx_decltype_size[D3DDECLTYPE_UNUSED] =
1209 {
1210    /* D3DDECLTYPE_FLOAT1    */ 1 * 4,
1211    /* D3DDECLTYPE_FLOAT2    */ 2 * 4,
1212    /* D3DDECLTYPE_FLOAT3    */ 3 * 4,
1213    /* D3DDECLTYPE_FLOAT4    */ 4 * 4,
1214    /* D3DDECLTYPE_D3DCOLOR  */ 4 * 1,
1215    /* D3DDECLTYPE_UBYTE4    */ 4 * 1,
1216    /* D3DDECLTYPE_SHORT2    */ 2 * 2,
1217    /* D3DDECLTYPE_SHORT4    */ 4 * 2,
1218    /* D3DDECLTYPE_UBYTE4N   */ 4 * 1,
1219    /* D3DDECLTYPE_SHORT2N   */ 2 * 2,
1220    /* D3DDECLTYPE_SHORT4N   */ 4 * 2,
1221    /* D3DDECLTYPE_USHORT2N  */ 2 * 2,
1222    /* D3DDECLTYPE_USHORT4N  */ 4 * 2,
1223    /* D3DDECLTYPE_UDEC3     */ 4, /* 3 * 10 bits + 2 padding */
1224    /* D3DDECLTYPE_DEC3N     */ 4,
1225    /* D3DDECLTYPE_FLOAT16_2 */ 2 * 2,
1226    /* D3DDECLTYPE_FLOAT16_4 */ 4 * 2,
1227 };
1228
1229 static void append_decl_element(D3DVERTEXELEMENT9 *declaration, UINT *idx, UINT *offset,
1230         D3DDECLTYPE type, D3DDECLUSAGE usage, UINT usage_idx)
1231 {
1232     declaration[*idx].Stream = 0;
1233     declaration[*idx].Offset = *offset;
1234     declaration[*idx].Type = type;
1235     declaration[*idx].Method = D3DDECLMETHOD_DEFAULT;
1236     declaration[*idx].Usage = usage;
1237     declaration[*idx].UsageIndex = usage_idx;
1238
1239     *offset += d3dx_decltype_size[type];
1240     ++(*idx);
1241 }
1242
1243 /*************************************************************************
1244  * D3DXDeclaratorFromFVF
1245  */
1246 HRESULT WINAPI D3DXDeclaratorFromFVF(DWORD fvf, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
1247 {
1248     static const D3DVERTEXELEMENT9 end_element = D3DDECL_END();
1249     DWORD tex_count = (fvf & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
1250     unsigned int offset = 0;
1251     unsigned int idx = 0;
1252     unsigned int i;
1253
1254     TRACE("fvf %#x, declaration %p.\n", fvf, declaration);
1255
1256     if (fvf & (D3DFVF_RESERVED0 | D3DFVF_RESERVED2)) return D3DERR_INVALIDCALL;
1257
1258     if (fvf & D3DFVF_POSITION_MASK)
1259     {
1260         BOOL has_blend = (fvf & D3DFVF_XYZB5) >= D3DFVF_XYZB1;
1261         DWORD blend_count = 1 + (((fvf & D3DFVF_XYZB5) - D3DFVF_XYZB1) >> 1);
1262         BOOL has_blend_idx = (fvf & D3DFVF_LASTBETA_D3DCOLOR) || (fvf & D3DFVF_LASTBETA_UBYTE4);
1263
1264         if (has_blend_idx) --blend_count;
1265
1266         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZW
1267                 || (has_blend && blend_count > 4))
1268             return D3DERR_INVALIDCALL;
1269
1270         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZRHW)
1271             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_POSITIONT, 0);
1272         else
1273             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_POSITION, 0);
1274
1275         if (has_blend)
1276         {
1277             switch (blend_count)
1278             {
1279                  case 0:
1280                     break;
1281                  case 1:
1282                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_BLENDWEIGHT, 0);
1283                     break;
1284                  case 2:
1285                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_BLENDWEIGHT, 0);
1286                     break;
1287                  case 3:
1288                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_BLENDWEIGHT, 0);
1289                     break;
1290                  case 4:
1291                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_BLENDWEIGHT, 0);
1292                     break;
1293                  default:
1294                      ERR("Invalid blend count %u.\n", blend_count);
1295                      break;
1296             }
1297
1298             if (has_blend_idx)
1299             {
1300                 if (fvf & D3DFVF_LASTBETA_UBYTE4)
1301                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_UBYTE4, D3DDECLUSAGE_BLENDINDICES, 0);
1302                 else if (fvf & D3DFVF_LASTBETA_D3DCOLOR)
1303                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_BLENDINDICES, 0);
1304             }
1305         }
1306     }
1307
1308     if (fvf & D3DFVF_NORMAL)
1309         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_NORMAL, 0);
1310     if (fvf & D3DFVF_PSIZE)
1311         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_PSIZE, 0);
1312     if (fvf & D3DFVF_DIFFUSE)
1313         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 0);
1314     if (fvf & D3DFVF_SPECULAR)
1315         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 1);
1316
1317     for (i = 0; i < tex_count; ++i)
1318     {
1319         switch ((fvf >> (16 + 2 * i)) & 0x03)
1320         {
1321             case D3DFVF_TEXTUREFORMAT1:
1322                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_TEXCOORD, i);
1323                 break;
1324             case D3DFVF_TEXTUREFORMAT2:
1325                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_TEXCOORD, i);
1326                 break;
1327             case D3DFVF_TEXTUREFORMAT3:
1328                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_TEXCOORD, i);
1329                 break;
1330             case D3DFVF_TEXTUREFORMAT4:
1331                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_TEXCOORD, i);
1332                 break;
1333         }
1334     }
1335
1336     declaration[idx] = end_element;
1337
1338     return D3D_OK;
1339 }
1340
1341 /*************************************************************************
1342  * D3DXFVFFromDeclarator
1343  */
1344 HRESULT WINAPI D3DXFVFFromDeclarator(const D3DVERTEXELEMENT9 *declaration, DWORD *fvf)
1345 {
1346     unsigned int i = 0, texture, offset;
1347
1348     TRACE("(%p, %p)\n", declaration, fvf);
1349
1350     *fvf = 0;
1351     if (declaration[0].Type == D3DDECLTYPE_FLOAT3 && declaration[0].Usage == D3DDECLUSAGE_POSITION)
1352     {
1353         if ((declaration[1].Type == D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
1354              declaration[1].UsageIndex == 0) &&
1355             (declaration[2].Type == D3DDECLTYPE_FLOAT1 && declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES &&
1356              declaration[2].UsageIndex == 0))
1357         {
1358             return D3DERR_INVALIDCALL;
1359         }
1360         else if ((declaration[1].Type == D3DDECLTYPE_UBYTE4 || declaration[1].Type == D3DDECLTYPE_D3DCOLOR) &&
1361                  declaration[1].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[1].UsageIndex == 0)
1362         {
1363             if (declaration[1].Type == D3DDECLTYPE_UBYTE4)
1364             {
1365                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_UBYTE4;
1366             }
1367             else
1368             {
1369                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_D3DCOLOR;
1370             }
1371             i = 2;
1372         }
1373         else if (declaration[1].Type <= D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
1374                  declaration[1].UsageIndex == 0)
1375         {
1376             if ((declaration[2].Type == D3DDECLTYPE_UBYTE4 || declaration[2].Type == D3DDECLTYPE_D3DCOLOR) &&
1377                 declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[2].UsageIndex == 0)
1378             {
1379                 if (declaration[2].Type == D3DDECLTYPE_UBYTE4)
1380                 {
1381                     *fvf |= D3DFVF_LASTBETA_UBYTE4;
1382                 }
1383                 else
1384                 {
1385                     *fvf |= D3DFVF_LASTBETA_D3DCOLOR;
1386                 }
1387                 switch (declaration[1].Type)
1388                 {
1389                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB2; break;
1390                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB3; break;
1391                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB4; break;
1392                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB5; break;
1393                 }
1394                 i = 3;
1395             }
1396             else
1397             {
1398                 switch (declaration[1].Type)
1399                 {
1400                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB1; break;
1401                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB2; break;
1402                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB3; break;
1403                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB4; break;
1404                 }
1405                 i = 2;
1406             }
1407         }
1408         else
1409         {
1410             *fvf |= D3DFVF_XYZ;
1411             i = 1;
1412         }
1413     }
1414     else if (declaration[0].Type == D3DDECLTYPE_FLOAT4 && declaration[0].Usage == D3DDECLUSAGE_POSITIONT &&
1415              declaration[0].UsageIndex == 0)
1416     {
1417         *fvf |= D3DFVF_XYZRHW;
1418         i = 1;
1419     }
1420
1421     if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_NORMAL)
1422     {
1423         *fvf |= D3DFVF_NORMAL;
1424         i++;
1425     }
1426     if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_PSIZE &&
1427         declaration[i].UsageIndex == 0)
1428     {
1429         *fvf |= D3DFVF_PSIZE;
1430         i++;
1431     }
1432     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
1433         declaration[i].UsageIndex == 0)
1434     {
1435         *fvf |= D3DFVF_DIFFUSE;
1436         i++;
1437     }
1438     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
1439         declaration[i].UsageIndex == 1)
1440     {
1441         *fvf |= D3DFVF_SPECULAR;
1442         i++;
1443     }
1444
1445     for (texture = 0; texture < D3DDP_MAXTEXCOORD; i++, texture++)
1446     {
1447         if (declaration[i].Stream == 0xFF)
1448         {
1449             break;
1450         }
1451         else if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1452                  declaration[i].UsageIndex == texture)
1453         {
1454             *fvf |= D3DFVF_TEXCOORDSIZE1(declaration[i].UsageIndex);
1455         }
1456         else if (declaration[i].Type == D3DDECLTYPE_FLOAT2 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1457                  declaration[i].UsageIndex == texture)
1458         {
1459             *fvf |= D3DFVF_TEXCOORDSIZE2(declaration[i].UsageIndex);
1460         }
1461         else if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1462                  declaration[i].UsageIndex == texture)
1463         {
1464             *fvf |= D3DFVF_TEXCOORDSIZE3(declaration[i].UsageIndex);
1465         }
1466         else if (declaration[i].Type == D3DDECLTYPE_FLOAT4 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
1467                  declaration[i].UsageIndex == texture)
1468         {
1469             *fvf |= D3DFVF_TEXCOORDSIZE4(declaration[i].UsageIndex);
1470         }
1471         else
1472         {
1473             return D3DERR_INVALIDCALL;
1474         }
1475     }
1476
1477     *fvf |= (texture << D3DFVF_TEXCOUNT_SHIFT);
1478
1479     for (offset = 0, i = 0; declaration[i].Stream != 0xFF;
1480          offset += d3dx_decltype_size[declaration[i].Type], i++)
1481     {
1482         if (declaration[i].Offset != offset)
1483         {
1484             return D3DERR_INVALIDCALL;
1485         }
1486     }
1487
1488     return D3D_OK;
1489 }
1490
1491 /*************************************************************************
1492  * D3DXGetFVFVertexSize
1493  */
1494 static UINT Get_TexCoord_Size_From_FVF(DWORD FVF, int tex_num)
1495 {
1496     return (((((FVF) >> (16 + (2 * (tex_num)))) + 1) & 0x03) + 1);
1497 }
1498
1499 UINT WINAPI D3DXGetFVFVertexSize(DWORD FVF)
1500 {
1501     DWORD size = 0;
1502     UINT i;
1503     UINT numTextures = (FVF & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
1504
1505     if (FVF & D3DFVF_NORMAL) size += sizeof(D3DXVECTOR3);
1506     if (FVF & D3DFVF_DIFFUSE) size += sizeof(DWORD);
1507     if (FVF & D3DFVF_SPECULAR) size += sizeof(DWORD);
1508     if (FVF & D3DFVF_PSIZE) size += sizeof(DWORD);
1509
1510     switch (FVF & D3DFVF_POSITION_MASK)
1511     {
1512         case D3DFVF_XYZ:    size += sizeof(D3DXVECTOR3); break;
1513         case D3DFVF_XYZRHW: size += 4 * sizeof(FLOAT); break;
1514         case D3DFVF_XYZB1:  size += 4 * sizeof(FLOAT); break;
1515         case D3DFVF_XYZB2:  size += 5 * sizeof(FLOAT); break;
1516         case D3DFVF_XYZB3:  size += 6 * sizeof(FLOAT); break;
1517         case D3DFVF_XYZB4:  size += 7 * sizeof(FLOAT); break;
1518         case D3DFVF_XYZB5:  size += 8 * sizeof(FLOAT); break;
1519         case D3DFVF_XYZW:   size += 4 * sizeof(FLOAT); break;
1520     }
1521
1522     for (i = 0; i < numTextures; i++)
1523     {
1524         size += Get_TexCoord_Size_From_FVF(FVF, i) * sizeof(FLOAT);
1525     }
1526
1527     return size;
1528 }
1529
1530 /*************************************************************************
1531  * D3DXGetDeclVertexSize
1532  */
1533 UINT WINAPI D3DXGetDeclVertexSize(const D3DVERTEXELEMENT9 *decl, DWORD stream_idx)
1534 {
1535     const D3DVERTEXELEMENT9 *element;
1536     UINT size = 0;
1537
1538     TRACE("decl %p, stream_idx %u\n", decl, stream_idx);
1539
1540     if (!decl) return 0;
1541
1542     for (element = decl; element->Stream != 0xff; ++element)
1543     {
1544         UINT type_size;
1545
1546         if (element->Stream != stream_idx) continue;
1547
1548         if (element->Type >= sizeof(d3dx_decltype_size) / sizeof(*d3dx_decltype_size))
1549         {
1550             FIXME("Unhandled element type %#x, size will be incorrect.\n", element->Type);
1551             continue;
1552         }
1553
1554         type_size = d3dx_decltype_size[element->Type];
1555         if (element->Offset + type_size > size) size = element->Offset + type_size;
1556     }
1557
1558     return size;
1559 }
1560
1561 /*************************************************************************
1562  * D3DXGetDeclLength
1563  */
1564 UINT WINAPI D3DXGetDeclLength(const D3DVERTEXELEMENT9 *decl)
1565 {
1566     const D3DVERTEXELEMENT9 *element;
1567
1568     TRACE("decl %p\n", decl);
1569
1570     /* null decl results in exception on Windows XP */
1571
1572     for (element = decl; element->Stream != 0xff; ++element);
1573
1574     return element - decl;
1575 }
1576
1577 /*************************************************************************
1578  * D3DXIntersectTri
1579  */
1580 BOOL WINAPI D3DXIntersectTri(CONST D3DXVECTOR3 *p0, CONST D3DXVECTOR3 *p1, CONST D3DXVECTOR3 *p2, CONST D3DXVECTOR3 *praypos, CONST D3DXVECTOR3 *praydir, FLOAT *pu, FLOAT *pv, FLOAT *pdist)
1581 {
1582     D3DXMATRIX m;
1583     D3DXVECTOR4 vec;
1584
1585     m.u.m[0][0] = p1->x - p0->x;
1586     m.u.m[1][0] = p2->x - p0->x;
1587     m.u.m[2][0] = -praydir->x;
1588     m.u.m[3][0] = 0.0f;
1589     m.u.m[0][1] = p1->y - p0->z;
1590     m.u.m[1][1] = p2->y - p0->z;
1591     m.u.m[2][1] = -praydir->y;
1592     m.u.m[3][1] = 0.0f;
1593     m.u.m[0][2] = p1->z - p0->z;
1594     m.u.m[1][2] = p2->z - p0->z;
1595     m.u.m[2][2] = -praydir->z;
1596     m.u.m[3][2] = 0.0f;
1597     m.u.m[0][3] = 0.0f;
1598     m.u.m[1][3] = 0.0f;
1599     m.u.m[2][3] = 0.0f;
1600     m.u.m[3][3] = 1.0f;
1601
1602     vec.x = praypos->x - p0->x;
1603     vec.y = praypos->y - p0->y;
1604     vec.z = praypos->z - p0->z;
1605     vec.w = 0.0f;
1606
1607     if ( D3DXMatrixInverse(&m, NULL, &m) )
1608     {
1609         D3DXVec4Transform(&vec, &vec, &m);
1610         if ( (vec.x >= 0.0f) && (vec.y >= 0.0f) && (vec.x + vec.y <= 1.0f) && (vec.z >= 0.0f) )
1611         {
1612             *pu = vec.x;
1613             *pv = vec.y;
1614             *pdist = fabs( vec.z );
1615             return TRUE;
1616         }
1617     }
1618
1619     return FALSE;
1620 }
1621
1622 /*************************************************************************
1623  * D3DXSphereBoundProbe
1624  */
1625 BOOL WINAPI D3DXSphereBoundProbe(CONST D3DXVECTOR3 *pcenter, FLOAT radius, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
1626 {
1627     D3DXVECTOR3 difference;
1628     FLOAT a, b, c, d;
1629
1630     a = D3DXVec3LengthSq(praydirection);
1631     if (!D3DXVec3Subtract(&difference, prayposition, pcenter)) return FALSE;
1632     b = D3DXVec3Dot(&difference, praydirection);
1633     c = D3DXVec3LengthSq(&difference) - radius * radius;
1634     d = b * b - a * c;
1635
1636     if ( ( d <= 0.0f ) || ( sqrt(d) <= b ) ) return FALSE;
1637     return TRUE;
1638 }
1639
1640 /*************************************************************************
1641  * D3DXCreateMesh
1642  */
1643 HRESULT WINAPI D3DXCreateMesh(DWORD numfaces, DWORD numvertices, DWORD options, CONST D3DVERTEXELEMENT9 *declaration,
1644                               LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
1645 {
1646     HRESULT hr;
1647     DWORD fvf;
1648     IDirect3DVertexDeclaration9 *vertex_declaration;
1649     IDirect3DVertexBuffer9 *vertex_buffer;
1650     IDirect3DIndexBuffer9 *index_buffer;
1651     DWORD *attrib_buffer;
1652     ID3DXMeshImpl *object;
1653     DWORD index_usage = 0;
1654     D3DPOOL index_pool = D3DPOOL_DEFAULT;
1655     D3DFORMAT index_format = D3DFMT_INDEX16;
1656     DWORD vertex_usage = 0;
1657     D3DPOOL vertex_pool = D3DPOOL_DEFAULT;
1658     int i;
1659
1660     TRACE("(%d, %d, %x, %p, %p, %p)\n", numfaces, numvertices, options, declaration, device, mesh);
1661
1662     if (numfaces == 0 || numvertices == 0 || declaration == NULL || device == NULL || mesh == NULL ||
1663         /* D3DXMESH_VB_SHARE is for cloning, and D3DXMESH_USEHWONLY is for ConvertToBlendedMesh */
1664         (options & (D3DXMESH_VB_SHARE | D3DXMESH_USEHWONLY | 0xfffe0000)))
1665     {
1666         return D3DERR_INVALIDCALL;
1667     }
1668     for (i = 0; declaration[i].Stream != 0xff; i++)
1669         if (declaration[i].Stream != 0)
1670             return D3DERR_INVALIDCALL;
1671
1672     if (options & D3DXMESH_32BIT)
1673         index_format = D3DFMT_INDEX32;
1674
1675     if (options & D3DXMESH_DONOTCLIP) {
1676         index_usage |= D3DUSAGE_DONOTCLIP;
1677         vertex_usage |= D3DUSAGE_DONOTCLIP;
1678     }
1679     if (options & D3DXMESH_POINTS) {
1680         index_usage |= D3DUSAGE_POINTS;
1681         vertex_usage |= D3DUSAGE_POINTS;
1682     }
1683     if (options & D3DXMESH_RTPATCHES) {
1684         index_usage |= D3DUSAGE_RTPATCHES;
1685         vertex_usage |= D3DUSAGE_RTPATCHES;
1686     }
1687     if (options & D3DXMESH_NPATCHES) {
1688         index_usage |= D3DUSAGE_NPATCHES;
1689         vertex_usage |= D3DUSAGE_NPATCHES;
1690     }
1691
1692     if (options & D3DXMESH_VB_SYSTEMMEM)
1693         vertex_pool = D3DPOOL_SYSTEMMEM;
1694     else if (options & D3DXMESH_VB_MANAGED)
1695         vertex_pool = D3DPOOL_MANAGED;
1696
1697     if (options & D3DXMESH_VB_WRITEONLY)
1698         vertex_usage |= D3DUSAGE_WRITEONLY;
1699     if (options & D3DXMESH_VB_DYNAMIC)
1700         vertex_usage |= D3DUSAGE_DYNAMIC;
1701     if (options & D3DXMESH_VB_SOFTWAREPROCESSING)
1702         vertex_usage |= D3DUSAGE_SOFTWAREPROCESSING;
1703
1704     if (options & D3DXMESH_IB_SYSTEMMEM)
1705         index_pool = D3DPOOL_SYSTEMMEM;
1706     else if (options & D3DXMESH_IB_MANAGED)
1707         index_pool = D3DPOOL_MANAGED;
1708
1709     if (options & D3DXMESH_IB_WRITEONLY)
1710         index_usage |= D3DUSAGE_WRITEONLY;
1711     if (options & D3DXMESH_IB_DYNAMIC)
1712         index_usage |= D3DUSAGE_DYNAMIC;
1713     if (options & D3DXMESH_IB_SOFTWAREPROCESSING)
1714         index_usage |= D3DUSAGE_SOFTWAREPROCESSING;
1715
1716     hr = D3DXFVFFromDeclarator(declaration, &fvf);
1717     if (hr != D3D_OK)
1718     {
1719         fvf = 0;
1720     }
1721
1722     /* Create vertex declaration */
1723     hr = IDirect3DDevice9_CreateVertexDeclaration(device,
1724                                                   declaration,
1725                                                   &vertex_declaration);
1726     if (FAILED(hr))
1727     {
1728         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexDeclaration.\n",hr);
1729         return hr;
1730     }
1731
1732     /* Create vertex buffer */
1733     hr = IDirect3DDevice9_CreateVertexBuffer(device,
1734                                              numvertices * D3DXGetDeclVertexSize(declaration, declaration[0].Stream),
1735                                              vertex_usage,
1736                                              fvf,
1737                                              vertex_pool,
1738                                              &vertex_buffer,
1739                                              NULL);
1740     if (FAILED(hr))
1741     {
1742         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
1743         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1744         return hr;
1745     }
1746
1747     /* Create index buffer */
1748     hr = IDirect3DDevice9_CreateIndexBuffer(device,
1749                                             numfaces * 3 * ((index_format == D3DFMT_INDEX16) ? 2 : 4),
1750                                             index_usage,
1751                                             index_format,
1752                                             index_pool,
1753                                             &index_buffer,
1754                                             NULL);
1755     if (FAILED(hr))
1756     {
1757         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
1758         IDirect3DVertexBuffer9_Release(vertex_buffer);
1759         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1760         return hr;
1761     }
1762
1763     attrib_buffer = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, numfaces * sizeof(*attrib_buffer));
1764     object = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(ID3DXMeshImpl));
1765     if (object == NULL || attrib_buffer == NULL)
1766     {
1767         HeapFree(GetProcessHeap(), 0, attrib_buffer);
1768         IDirect3DIndexBuffer9_Release(index_buffer);
1769         IDirect3DVertexBuffer9_Release(vertex_buffer);
1770         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1771         *mesh = NULL;
1772         return E_OUTOFMEMORY;
1773     }
1774     object->ID3DXMesh_iface.lpVtbl = &D3DXMesh_Vtbl;
1775     object->ref = 1;
1776
1777     object->numfaces = numfaces;
1778     object->numvertices = numvertices;
1779     object->options = options;
1780     object->fvf = fvf;
1781     object->device = device;
1782     IDirect3DDevice9_AddRef(device);
1783
1784     object->vertex_declaration = vertex_declaration;
1785     object->vertex_buffer = vertex_buffer;
1786     object->index_buffer = index_buffer;
1787     object->attrib_buffer = attrib_buffer;
1788
1789     *mesh = &object->ID3DXMesh_iface;
1790
1791     return D3D_OK;
1792 }
1793
1794 /*************************************************************************
1795  * D3DXCreateMeshFVF
1796  */
1797 HRESULT WINAPI D3DXCreateMeshFVF(DWORD numfaces, DWORD numvertices, DWORD options, DWORD fvf,
1798                                  LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
1799 {
1800     HRESULT hr;
1801     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
1802
1803     TRACE("(%u, %u, %u, %u, %p, %p)\n", numfaces, numvertices, options, fvf, device, mesh);
1804
1805     hr = D3DXDeclaratorFromFVF(fvf, declaration);
1806     if (FAILED(hr)) return hr;
1807
1808     return D3DXCreateMesh(numfaces, numvertices, options, declaration, device, mesh);
1809 }
1810
1811
1812 HRESULT WINAPI D3DXFrameDestroy(LPD3DXFRAME frame, LPD3DXALLOCATEHIERARCHY alloc_hier)
1813 {
1814     HRESULT hr;
1815     BOOL last = FALSE;
1816
1817     TRACE("(%p, %p)\n", frame, alloc_hier);
1818
1819     if (!frame || !alloc_hier)
1820         return D3DERR_INVALIDCALL;
1821
1822     while (!last) {
1823         D3DXMESHCONTAINER *container;
1824         D3DXFRAME *current_frame;
1825
1826         if (frame->pFrameSibling) {
1827             current_frame = frame->pFrameSibling;
1828             frame->pFrameSibling = current_frame->pFrameSibling;
1829             current_frame->pFrameSibling = NULL;
1830         } else if (frame) {
1831             current_frame = frame;
1832             last = TRUE;
1833         }
1834
1835         if (current_frame->pFrameFirstChild) {
1836             hr = D3DXFrameDestroy(current_frame->pFrameFirstChild, alloc_hier);
1837             if (FAILED(hr)) return hr;
1838             current_frame->pFrameFirstChild = NULL;
1839         }
1840
1841         container = current_frame->pMeshContainer;
1842         while (container) {
1843             D3DXMESHCONTAINER *next_container = container->pNextMeshContainer;
1844             hr = alloc_hier->lpVtbl->DestroyMeshContainer(alloc_hier, container);
1845             if (FAILED(hr)) return hr;
1846             container = next_container;
1847         }
1848         hr = alloc_hier->lpVtbl->DestroyFrame(alloc_hier, current_frame);
1849         if (FAILED(hr)) return hr;
1850     }
1851     return D3D_OK;
1852 }
1853
1854 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
1855                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
1856 {
1857     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
1858
1859     return E_NOTIMPL;
1860 }
1861
1862 struct vertex
1863 {
1864     D3DXVECTOR3 position;
1865     D3DXVECTOR3 normal;
1866 };
1867
1868 typedef WORD face[3];
1869
1870 struct sincos_table
1871 {
1872     float *sin;
1873     float *cos;
1874 };
1875
1876 static void free_sincos_table(struct sincos_table *sincos_table)
1877 {
1878     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
1879     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
1880 }
1881
1882 /* pre compute sine and cosine tables; caller must free */
1883 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
1884 {
1885     float angle;
1886     int i;
1887
1888     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
1889     if (!sincos_table->sin)
1890     {
1891         return FALSE;
1892     }
1893     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
1894     if (!sincos_table->cos)
1895     {
1896         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
1897         return FALSE;
1898     }
1899
1900     angle = angle_start;
1901     for (i = 0; i < n; i++)
1902     {
1903         sincos_table->sin[i] = sin(angle);
1904         sincos_table->cos[i] = cos(angle);
1905         angle += angle_step;
1906     }
1907
1908     return TRUE;
1909 }
1910
1911 static WORD vertex_index(UINT slices, int slice, int stack)
1912 {
1913     return stack*slices+slice+1;
1914 }
1915
1916 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
1917                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
1918 {
1919     DWORD number_of_vertices, number_of_faces;
1920     HRESULT hr;
1921     ID3DXMesh *sphere;
1922     struct vertex *vertices;
1923     face *faces;
1924     float phi_step, phi_start;
1925     struct sincos_table phi;
1926     float theta_step, theta, sin_theta, cos_theta;
1927     DWORD vertex, face;
1928     int slice, stack;
1929
1930     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
1931
1932     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
1933     {
1934         return D3DERR_INVALIDCALL;
1935     }
1936
1937     if (adjacency)
1938     {
1939         FIXME("Case of adjacency != NULL not implemented.\n");
1940         return E_NOTIMPL;
1941     }
1942
1943     number_of_vertices = 2 + slices * (stacks-1);
1944     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
1945
1946     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
1947                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
1948     if (FAILED(hr))
1949     {
1950         return hr;
1951     }
1952
1953     hr = sphere->lpVtbl->LockVertexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&vertices);
1954     if (FAILED(hr))
1955     {
1956         sphere->lpVtbl->Release(sphere);
1957         return hr;
1958     }
1959
1960     hr = sphere->lpVtbl->LockIndexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&faces);
1961     if (FAILED(hr))
1962     {
1963         sphere->lpVtbl->UnlockVertexBuffer(sphere);
1964         sphere->lpVtbl->Release(sphere);
1965         return hr;
1966     }
1967
1968     /* phi = angle on xz plane wrt z axis */
1969     phi_step = -2 * M_PI / slices;
1970     phi_start = M_PI / 2;
1971
1972     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
1973     {
1974         sphere->lpVtbl->UnlockIndexBuffer(sphere);
1975         sphere->lpVtbl->UnlockVertexBuffer(sphere);
1976         sphere->lpVtbl->Release(sphere);
1977         return E_OUTOFMEMORY;
1978     }
1979
1980     /* theta = angle on xy plane wrt x axis */
1981     theta_step = M_PI / stacks;
1982     theta = theta_step;
1983
1984     vertex = 0;
1985     face = 0;
1986     stack = 0;
1987
1988     vertices[vertex].normal.x = 0.0f;
1989     vertices[vertex].normal.y = 0.0f;
1990     vertices[vertex].normal.z = 1.0f;
1991     vertices[vertex].position.x = 0.0f;
1992     vertices[vertex].position.y = 0.0f;
1993     vertices[vertex].position.z = radius;
1994     vertex++;
1995
1996     for (stack = 0; stack < stacks - 1; stack++)
1997     {
1998         sin_theta = sin(theta);
1999         cos_theta = cos(theta);
2000
2001         for (slice = 0; slice < slices; slice++)
2002         {
2003             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
2004             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
2005             vertices[vertex].normal.z = cos_theta;
2006             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
2007             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
2008             vertices[vertex].position.z = radius * cos_theta;
2009             vertex++;
2010
2011             if (slice > 0)
2012             {
2013                 if (stack == 0)
2014                 {
2015                     /* top stack is triangle fan */
2016                     faces[face][0] = 0;
2017                     faces[face][1] = slice + 1;
2018                     faces[face][2] = slice;
2019                     face++;
2020                 }
2021                 else
2022                 {
2023                     /* stacks in between top and bottom are quad strips */
2024                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
2025                     faces[face][1] = vertex_index(slices, slice, stack-1);
2026                     faces[face][2] = vertex_index(slices, slice-1, stack);
2027                     face++;
2028
2029                     faces[face][0] = vertex_index(slices, slice, stack-1);
2030                     faces[face][1] = vertex_index(slices, slice, stack);
2031                     faces[face][2] = vertex_index(slices, slice-1, stack);
2032                     face++;
2033                 }
2034             }
2035         }
2036
2037         theta += theta_step;
2038
2039         if (stack == 0)
2040         {
2041             faces[face][0] = 0;
2042             faces[face][1] = 1;
2043             faces[face][2] = slice;
2044             face++;
2045         }
2046         else
2047         {
2048             faces[face][0] = vertex_index(slices, slice-1, stack-1);
2049             faces[face][1] = vertex_index(slices, 0, stack-1);
2050             faces[face][2] = vertex_index(slices, slice-1, stack);
2051             face++;
2052
2053             faces[face][0] = vertex_index(slices, 0, stack-1);
2054             faces[face][1] = vertex_index(slices, 0, stack);
2055             faces[face][2] = vertex_index(slices, slice-1, stack);
2056             face++;
2057         }
2058     }
2059
2060     vertices[vertex].position.x = 0.0f;
2061     vertices[vertex].position.y = 0.0f;
2062     vertices[vertex].position.z = -radius;
2063     vertices[vertex].normal.x = 0.0f;
2064     vertices[vertex].normal.y = 0.0f;
2065     vertices[vertex].normal.z = -1.0f;
2066
2067     /* bottom stack is triangle fan */
2068     for (slice = 1; slice < slices; slice++)
2069     {
2070         faces[face][0] = vertex_index(slices, slice-1, stack-1);
2071         faces[face][1] = vertex_index(slices, slice, stack-1);
2072         faces[face][2] = vertex;
2073         face++;
2074     }
2075
2076     faces[face][0] = vertex_index(slices, slice-1, stack-1);
2077     faces[face][1] = vertex_index(slices, 0, stack-1);
2078     faces[face][2] = vertex;
2079
2080     free_sincos_table(&phi);
2081     sphere->lpVtbl->UnlockIndexBuffer(sphere);
2082     sphere->lpVtbl->UnlockVertexBuffer(sphere);
2083     *mesh = sphere;
2084
2085     return D3D_OK;
2086 }
2087
2088 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
2089                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
2090 {
2091     DWORD number_of_vertices, number_of_faces;
2092     HRESULT hr;
2093     ID3DXMesh *cylinder;
2094     struct vertex *vertices;
2095     face *faces;
2096     float theta_step, theta_start;
2097     struct sincos_table theta;
2098     float delta_radius, radius, radius_step;
2099     float z, z_step, z_normal;
2100     DWORD vertex, face;
2101     int slice, stack;
2102
2103     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
2104
2105     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
2106     {
2107         return D3DERR_INVALIDCALL;
2108     }
2109
2110     if (adjacency)
2111     {
2112         FIXME("Case of adjacency != NULL not implemented.\n");
2113         return E_NOTIMPL;
2114     }
2115
2116     number_of_vertices = 2 + (slices * (3 + stacks));
2117     number_of_faces = 2 * slices + stacks * (2 * slices);
2118
2119     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
2120                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
2121     if (FAILED(hr))
2122     {
2123         return hr;
2124     }
2125
2126     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&vertices);
2127     if (FAILED(hr))
2128     {
2129         cylinder->lpVtbl->Release(cylinder);
2130         return hr;
2131     }
2132
2133     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&faces);
2134     if (FAILED(hr))
2135     {
2136         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
2137         cylinder->lpVtbl->Release(cylinder);
2138         return hr;
2139     }
2140
2141     /* theta = angle on xy plane wrt x axis */
2142     theta_step = -2 * M_PI / slices;
2143     theta_start = M_PI / 2;
2144
2145     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
2146     {
2147         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
2148         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
2149         cylinder->lpVtbl->Release(cylinder);
2150         return E_OUTOFMEMORY;
2151     }
2152
2153     vertex = 0;
2154     face = 0;
2155
2156     delta_radius = radius1 - radius2;
2157     radius = radius1;
2158     radius_step = delta_radius / stacks;
2159
2160     z = -length / 2;
2161     z_step = length / stacks;
2162     z_normal = delta_radius / length;
2163     if (isnan(z_normal))
2164     {
2165         z_normal = 0.0f;
2166     }
2167
2168     vertices[vertex].normal.x = 0.0f;
2169     vertices[vertex].normal.y = 0.0f;
2170     vertices[vertex].normal.z = -1.0f;
2171     vertices[vertex].position.x = 0.0f;
2172     vertices[vertex].position.y = 0.0f;
2173     vertices[vertex++].position.z = z;
2174
2175     for (slice = 0; slice < slices; slice++, vertex++)
2176     {
2177         vertices[vertex].normal.x = 0.0f;
2178         vertices[vertex].normal.y = 0.0f;
2179         vertices[vertex].normal.z = -1.0f;
2180         vertices[vertex].position.x = radius * theta.cos[slice];
2181         vertices[vertex].position.y = radius * theta.sin[slice];
2182         vertices[vertex].position.z = z;
2183
2184         if (slice > 0)
2185         {
2186             faces[face][0] = 0;
2187             faces[face][1] = slice;
2188             faces[face++][2] = slice + 1;
2189         }
2190     }
2191
2192     faces[face][0] = 0;
2193     faces[face][1] = slice;
2194     faces[face++][2] = 1;
2195
2196     for (stack = 1; stack <= stacks+1; stack++)
2197     {
2198         for (slice = 0; slice < slices; slice++, vertex++)
2199         {
2200             vertices[vertex].normal.x = theta.cos[slice];
2201             vertices[vertex].normal.y = theta.sin[slice];
2202             vertices[vertex].normal.z = z_normal;
2203             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
2204             vertices[vertex].position.x = radius * theta.cos[slice];
2205             vertices[vertex].position.y = radius * theta.sin[slice];
2206             vertices[vertex].position.z = z;
2207
2208             if (stack > 1 && slice > 0)
2209             {
2210                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
2211                 faces[face][1] = vertex_index(slices, slice-1, stack);
2212                 faces[face++][2] = vertex_index(slices, slice, stack-1);
2213
2214                 faces[face][0] = vertex_index(slices, slice, stack-1);
2215                 faces[face][1] = vertex_index(slices, slice-1, stack);
2216                 faces[face++][2] = vertex_index(slices, slice, stack);
2217             }
2218         }
2219
2220         if (stack > 1)
2221         {
2222             faces[face][0] = vertex_index(slices, slice-1, stack-1);
2223             faces[face][1] = vertex_index(slices, slice-1, stack);
2224             faces[face++][2] = vertex_index(slices, 0, stack-1);
2225
2226             faces[face][0] = vertex_index(slices, 0, stack-1);
2227             faces[face][1] = vertex_index(slices, slice-1, stack);
2228             faces[face++][2] = vertex_index(slices, 0, stack);
2229         }
2230
2231         if (stack < stacks + 1)
2232         {
2233             z += z_step;
2234             radius -= radius_step;
2235         }
2236     }
2237
2238     for (slice = 0; slice < slices; slice++, vertex++)
2239     {
2240         vertices[vertex].normal.x = 0.0f;
2241         vertices[vertex].normal.y = 0.0f;
2242         vertices[vertex].normal.z = 1.0f;
2243         vertices[vertex].position.x = radius * theta.cos[slice];
2244         vertices[vertex].position.y = radius * theta.sin[slice];
2245         vertices[vertex].position.z = z;
2246
2247         if (slice > 0)
2248         {
2249             faces[face][0] = vertex_index(slices, slice-1, stack);
2250             faces[face][1] = number_of_vertices - 1;
2251             faces[face++][2] = vertex_index(slices, slice, stack);
2252         }
2253     }
2254
2255     vertices[vertex].position.x = 0.0f;
2256     vertices[vertex].position.y = 0.0f;
2257     vertices[vertex].position.z = z;
2258     vertices[vertex].normal.x = 0.0f;
2259     vertices[vertex].normal.y = 0.0f;
2260     vertices[vertex].normal.z = 1.0f;
2261
2262     faces[face][0] = vertex_index(slices, slice-1, stack);
2263     faces[face][1] = number_of_vertices - 1;
2264     faces[face][2] = vertex_index(slices, 0, stack);
2265
2266     free_sincos_table(&theta);
2267     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
2268     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
2269     *mesh = cylinder;
2270
2271     return D3D_OK;
2272 }
2273
2274 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
2275 {
2276     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
2277
2278     return E_NOTIMPL;
2279 }
2280
2281 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
2282                                HDC hdc, LPCSTR text,
2283                                FLOAT deviation, FLOAT extrusion,
2284                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
2285                                LPGLYPHMETRICSFLOAT glyphmetrics)
2286 {
2287     HRESULT hr;
2288     int len;
2289     LPWSTR textW;
2290
2291     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
2292           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
2293
2294     if (!text)
2295         return D3DERR_INVALIDCALL;
2296
2297     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
2298     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
2299     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
2300
2301     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
2302                          mesh, adjacency, glyphmetrics);
2303     HeapFree(GetProcessHeap(), 0, textW);
2304
2305     return hr;
2306 }
2307
2308 enum pointtype {
2309     POINTTYPE_CURVE = 0,
2310     POINTTYPE_CORNER,
2311     POINTTYPE_CURVE_START,
2312     POINTTYPE_CURVE_END,
2313     POINTTYPE_CURVE_MIDDLE,
2314 };
2315
2316 struct point2d
2317 {
2318     D3DXVECTOR2 pos;
2319     enum pointtype corner;
2320 };
2321
2322 struct dynamic_array
2323 {
2324     int count, capacity;
2325     void *items;
2326 };
2327
2328 /* is a dynamic_array */
2329 struct outline
2330 {
2331     int count, capacity;
2332     struct point2d *items;
2333 };
2334
2335 /* is a dynamic_array */
2336 struct outline_array
2337 {
2338     int count, capacity;
2339     struct outline *items;
2340 };
2341
2342 struct face_array
2343 {
2344     int count;
2345     face *items;
2346 };
2347
2348 struct point2d_index
2349 {
2350     struct outline *outline;
2351     int vertex;
2352 };
2353
2354 struct point2d_index_array
2355 {
2356     int count;
2357     struct point2d_index *items;
2358 };
2359
2360 struct glyphinfo
2361 {
2362     struct outline_array outlines;
2363     struct face_array faces;
2364     struct point2d_index_array ordered_vertices;
2365     float offset_x;
2366 };
2367
2368 /* is an dynamic_array */
2369 struct word_array
2370 {
2371     int count, capacity;
2372     WORD *items;
2373 };
2374
2375 /* complex polygons are split into monotone polygons, which have
2376  * at most 2 intersections with the vertical sweep line */
2377 struct triangulation
2378 {
2379     struct word_array vertex_stack;
2380     BOOL last_on_top, merging;
2381 };
2382
2383 /* is an dynamic_array */
2384 struct triangulation_array
2385 {
2386     int count, capacity;
2387     struct triangulation *items;
2388
2389     struct glyphinfo *glyph;
2390 };
2391
2392 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
2393 {
2394     if (count > array->capacity) {
2395         void *new_buffer;
2396         int new_capacity;
2397         if (array->items && array->capacity) {
2398             new_capacity = max(array->capacity * 2, count);
2399             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
2400         } else {
2401             new_capacity = max(16, count);
2402             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
2403         }
2404         if (!new_buffer)
2405             return FALSE;
2406         array->items = new_buffer;
2407         array->capacity = new_capacity;
2408     }
2409     return TRUE;
2410 }
2411
2412 static struct point2d *add_points(struct outline *array, int num)
2413 {
2414     struct point2d *item;
2415
2416     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
2417         return NULL;
2418
2419     item = &array->items[array->count];
2420     array->count += num;
2421     return item;
2422 }
2423
2424 static struct outline *add_outline(struct outline_array *array)
2425 {
2426     struct outline *item;
2427
2428     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
2429         return NULL;
2430
2431     item = &array->items[array->count++];
2432     ZeroMemory(item, sizeof(*item));
2433     return item;
2434 }
2435
2436 static inline face *add_face(struct face_array *array)
2437 {
2438     return &array->items[array->count++];
2439 }
2440
2441 static struct triangulation *add_triangulation(struct triangulation_array *array)
2442 {
2443     struct triangulation *item;
2444
2445     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
2446         return NULL;
2447
2448     item = &array->items[array->count++];
2449     ZeroMemory(item, sizeof(*item));
2450     return item;
2451 }
2452
2453 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
2454 {
2455     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
2456         return E_OUTOFMEMORY;
2457
2458     array->items[array->count++] = vertex_index;
2459     return S_OK;
2460 }
2461
2462 /* assume fixed point numbers can be converted to float point in place */
2463 C_ASSERT(sizeof(FIXED) == sizeof(float));
2464 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
2465
2466 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
2467 {
2468     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
2469     while (count--) {
2470         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
2471         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
2472         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
2473         pt++;
2474     }
2475     return ret;
2476 }
2477
2478 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
2479                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
2480                                  float max_deviation_sq)
2481 {
2482     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
2483     float deviation_sq;
2484
2485     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
2486     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
2487     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
2488
2489     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
2490     if (deviation_sq < max_deviation_sq) {
2491         struct point2d *pt = add_points(outline, 1);
2492         if (!pt) return E_OUTOFMEMORY;
2493         pt->pos = *p2;
2494         pt->corner = POINTTYPE_CURVE;
2495         /* the end point is omitted because the end line merges into the next segment of
2496          * the split bezier curve, and the end of the split bezier curve is added outside
2497          * this recursive function. */
2498     } else {
2499         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
2500         if (hr != S_OK) return hr;
2501         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
2502         if (hr != S_OK) return hr;
2503     }
2504
2505     return S_OK;
2506 }
2507
2508 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
2509 {
2510     /* dot product = cos(theta) */
2511     return D3DXVec2Dot(dir1, dir2) > cos_theta;
2512 }
2513
2514 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
2515 {
2516     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
2517 }
2518
2519 struct cos_table
2520 {
2521     float cos_half;
2522     float cos_45;
2523     float cos_90;
2524 };
2525
2526 static BOOL attempt_line_merge(struct outline *outline,
2527                                int pt_index,
2528                                const D3DXVECTOR2 *nextpt,
2529                                BOOL to_curve,
2530                                const struct cos_table *table)
2531 {
2532     D3DXVECTOR2 curdir, lastdir;
2533     struct point2d *prevpt, *pt;
2534     BOOL ret = FALSE;
2535
2536     pt = &outline->items[pt_index];
2537     pt_index = (pt_index - 1 + outline->count) % outline->count;
2538     prevpt = &outline->items[pt_index];
2539
2540     if (to_curve)
2541         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
2542
2543     if (outline->count < 2)
2544         return FALSE;
2545
2546     /* remove last point if the next line continues the last line */
2547     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
2548     unit_vec2(&curdir, &pt->pos, nextpt);
2549     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
2550     {
2551         outline->count--;
2552         if (pt->corner == POINTTYPE_CURVE_END)
2553             prevpt->corner = pt->corner;
2554         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
2555             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
2556         pt = prevpt;
2557
2558         ret = TRUE;
2559         if (outline->count < 2)
2560             return ret;
2561
2562         pt_index = (pt_index - 1 + outline->count) % outline->count;
2563         prevpt = &outline->items[pt_index];
2564         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
2565         unit_vec2(&curdir, &pt->pos, nextpt);
2566     }
2567     return ret;
2568 }
2569
2570 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
2571                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
2572 {
2573     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
2574
2575     while ((char *)header < (char *)raw_outline + datasize)
2576     {
2577         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
2578         struct point2d *lastpt, *pt;
2579         D3DXVECTOR2 lastdir;
2580         D3DXVECTOR2 *pt_flt;
2581         int j;
2582         struct outline *outline = add_outline(&glyph->outlines);
2583
2584         if (!outline)
2585             return E_OUTOFMEMORY;
2586
2587         pt = add_points(outline, 1);
2588         if (!pt)
2589             return E_OUTOFMEMORY;
2590         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
2591         pt->pos = *pt_flt;
2592         pt->corner = POINTTYPE_CORNER;
2593
2594         if (header->dwType != TT_POLYGON_TYPE)
2595             FIXME("Unknown header type %d\n", header->dwType);
2596
2597         while ((char *)curve < (char *)header + header->cb)
2598         {
2599             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
2600             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
2601
2602             if (!curve->cpfx) {
2603                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
2604                 continue;
2605             }
2606
2607             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
2608
2609             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
2610
2611             if (to_curve)
2612             {
2613                 HRESULT hr;
2614                 int count = curve->cpfx;
2615                 j = 0;
2616
2617                 while (count > 2)
2618                 {
2619                     D3DXVECTOR2 bezier_end;
2620
2621                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
2622                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
2623                     if (hr != S_OK)
2624                         return hr;
2625                     bezier_start = bezier_end;
2626                     count--;
2627                     j++;
2628                 }
2629                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
2630                 if (hr != S_OK)
2631                     return hr;
2632
2633                 pt = add_points(outline, 1);
2634                 if (!pt)
2635                     return E_OUTOFMEMORY;
2636                 j++;
2637                 pt->pos = pt_flt[j];
2638                 pt->corner = POINTTYPE_CURVE_END;
2639             } else {
2640                 pt = add_points(outline, curve->cpfx);
2641                 if (!pt)
2642                     return E_OUTOFMEMORY;
2643                 for (j = 0; j < curve->cpfx; j++)
2644                 {
2645                     pt->pos = pt_flt[j];
2646                     pt->corner = POINTTYPE_CORNER;
2647                     pt++;
2648                 }
2649             }
2650
2651             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
2652         }
2653
2654         /* remove last point if the next line continues the last line */
2655         if (outline->count >= 3) {
2656             BOOL to_curve;
2657
2658             lastpt = &outline->items[outline->count - 1];
2659             pt = &outline->items[0];
2660             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
2661                 if (lastpt->corner == POINTTYPE_CURVE_END)
2662                 {
2663                     if (pt->corner == POINTTYPE_CURVE_START)
2664                         pt->corner = POINTTYPE_CURVE_MIDDLE;
2665                     else
2666                         pt->corner = POINTTYPE_CURVE_END;
2667                 }
2668                 outline->count--;
2669                 lastpt = &outline->items[outline->count - 1];
2670             } else {
2671                 /* outline closed with a line from end to start point */
2672                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
2673             }
2674             lastpt = &outline->items[0];
2675             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
2676             if (lastpt->corner == POINTTYPE_CURVE_START)
2677                 lastpt->corner = POINTTYPE_CORNER;
2678             pt = &outline->items[1];
2679             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
2680                 *lastpt = outline->items[outline->count];
2681         }
2682
2683         lastpt = &outline->items[outline->count - 1];
2684         pt = &outline->items[0];
2685         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
2686         for (j = 0; j < outline->count; j++)
2687         {
2688             D3DXVECTOR2 curdir;
2689
2690             lastpt = pt;
2691             pt = &outline->items[(j + 1) % outline->count];
2692             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
2693
2694             switch (lastpt->corner)
2695             {
2696                 case POINTTYPE_CURVE_START:
2697                 case POINTTYPE_CURVE_END:
2698                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
2699                         lastpt->corner = POINTTYPE_CORNER;
2700                     break;
2701                 case POINTTYPE_CURVE_MIDDLE:
2702                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
2703                         lastpt->corner = POINTTYPE_CORNER;
2704                     else
2705                         lastpt->corner = POINTTYPE_CURVE;
2706                     break;
2707                 default:
2708                     break;
2709             }
2710             lastdir = curdir;
2711         }
2712
2713         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
2714     }
2715     return S_OK;
2716 }
2717
2718 /* Get the y-distance from a line to a point */
2719 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
2720                                           D3DXVECTOR2 *line_pt2,
2721                                           D3DXVECTOR2 *point)
2722 {
2723     D3DXVECTOR2 line_vec = {0, 0};
2724     float line_pt_dx;
2725     float line_y;
2726
2727     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
2728     line_pt_dx = point->x - line_pt1->x;
2729     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
2730     return point->y - line_y;
2731 }
2732
2733 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
2734 {
2735     return &pt_idx->outline->items[pt_idx->vertex].pos;
2736 }
2737
2738 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
2739 {
2740     return get_indexed_point(&glyph->ordered_vertices.items[index]);
2741 }
2742
2743 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
2744 {
2745     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
2746     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
2747     array->count--;
2748 }
2749
2750 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
2751                                        struct triangulation_array *triangulations,
2752                                        WORD vtx_idx,
2753                                        BOOL to_top)
2754 {
2755     struct glyphinfo *glyph = triangulations->glyph;
2756     struct triangulation *t = *t_ptr;
2757     HRESULT hr;
2758     face *face;
2759     int f1, f2;
2760
2761     if (t->last_on_top) {
2762         f1 = 1;
2763         f2 = 2;
2764     } else {
2765         f1 = 2;
2766         f2 = 1;
2767     }
2768
2769     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
2770         /* consume all vertices on the stack */
2771         WORD last_pt = t->vertex_stack.items[0];
2772         int i;
2773         for (i = 1; i < t->vertex_stack.count; i++)
2774         {
2775             face = add_face(&glyph->faces);
2776             if (!face) return E_OUTOFMEMORY;
2777             (*face)[0] = vtx_idx;
2778             (*face)[f1] = last_pt;
2779             (*face)[f2] = last_pt = t->vertex_stack.items[i];
2780         }
2781         t->vertex_stack.items[0] = last_pt;
2782         t->vertex_stack.count = 1;
2783     } else if (t->vertex_stack.count > 1) {
2784         int i = t->vertex_stack.count - 1;
2785         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
2786         WORD top_idx = t->vertex_stack.items[i--];
2787         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
2788
2789         while (i >= 0)
2790         {
2791             WORD prev_idx = t->vertex_stack.items[i--];
2792             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
2793
2794             if (prev_pt->x != top_pt->x &&
2795                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
2796                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
2797                 break;
2798
2799             face = add_face(&glyph->faces);
2800             if (!face) return E_OUTOFMEMORY;
2801             (*face)[0] = vtx_idx;
2802             (*face)[f1] = prev_idx;
2803             (*face)[f2] = top_idx;
2804
2805             top_pt = prev_pt;
2806             top_idx = prev_idx;
2807             t->vertex_stack.count--;
2808         }
2809     }
2810     t->last_on_top = to_top;
2811
2812     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
2813
2814     if (hr == S_OK && t->merging) {
2815         struct triangulation *t2;
2816
2817         t2 = to_top ? t - 1 : t + 1;
2818         t2->merging = FALSE;
2819         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
2820         if (hr != S_OK) return hr;
2821         remove_triangulation(triangulations, t);
2822         if (t2 > t)
2823             t2--;
2824         *t_ptr = t2;
2825     }
2826     return hr;
2827 }
2828
2829 /* check if the point is next on the outline for either the top or bottom */
2830 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
2831 {
2832     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
2833     WORD idx = t->vertex_stack.items[i];
2834     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
2835     struct outline *outline = pt_idx->outline;
2836
2837     if (on_top)
2838         i = (pt_idx->vertex + outline->count - 1) % outline->count;
2839     else
2840         i = (pt_idx->vertex + 1) % outline->count;
2841
2842     return &outline->items[i].pos;
2843 }
2844
2845 static int compare_vertex_indices(const void *a, const void *b)
2846 {
2847     const struct point2d_index *idx1 = a, *idx2 = b;
2848     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
2849     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
2850     float diff = p1->x - p2->x;
2851
2852     if (diff == 0.0f)
2853         diff = p1->y - p2->y;
2854
2855     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
2856 }
2857
2858 static HRESULT triangulate(struct triangulation_array *triangulations)
2859 {
2860     int sweep_idx;
2861     HRESULT hr;
2862     struct glyphinfo *glyph = triangulations->glyph;
2863     int nb_vertices = 0;
2864     int i;
2865     struct point2d_index *idx_ptr;
2866
2867     for (i = 0; i < glyph->outlines.count; i++)
2868         nb_vertices += glyph->outlines.items[i].count;
2869
2870     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
2871             nb_vertices * sizeof(*glyph->ordered_vertices.items));
2872     if (!glyph->ordered_vertices.items)
2873         return E_OUTOFMEMORY;
2874
2875     idx_ptr = glyph->ordered_vertices.items;
2876     for (i = 0; i < glyph->outlines.count; i++)
2877     {
2878         struct outline *outline = &glyph->outlines.items[i];
2879         int j;
2880
2881         idx_ptr->outline = outline;
2882         idx_ptr->vertex = 0;
2883         idx_ptr++;
2884         for (j = outline->count - 1; j > 0; j--)
2885         {
2886             idx_ptr->outline = outline;
2887             idx_ptr->vertex = j;
2888             idx_ptr++;
2889         }
2890     }
2891     glyph->ordered_vertices.count = nb_vertices;
2892
2893     /* Native implementation seems to try to create a triangle fan from
2894      * the first outline point if the glyph only has one outline. */
2895     if (glyph->outlines.count == 1)
2896     {
2897         struct outline *outline = glyph->outlines.items;
2898         D3DXVECTOR2 *base = &outline->items[0].pos;
2899         D3DXVECTOR2 *last = &outline->items[1].pos;
2900         float ccw = 0;
2901
2902         for (i = 2; i < outline->count; i++)
2903         {
2904             D3DXVECTOR2 *next = &outline->items[i].pos;
2905             D3DXVECTOR2 v1 = {0.0f, 0.0f};
2906             D3DXVECTOR2 v2 = {0.0f, 0.0f};
2907
2908             D3DXVec2Subtract(&v1, base, last);
2909             D3DXVec2Subtract(&v2, last, next);
2910             ccw = D3DXVec2CCW(&v1, &v2);
2911             if (ccw > 0.0f)
2912                 break;
2913
2914             last = next;
2915         }
2916         if (ccw <= 0)
2917         {
2918             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
2919                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
2920             if (!glyph->faces.items)
2921                 return E_OUTOFMEMORY;
2922
2923             glyph->faces.count = outline->count - 2;
2924             for (i = 0; i < glyph->faces.count; i++)
2925             {
2926                 glyph->faces.items[i][0] = 0;
2927                 glyph->faces.items[i][1] = i + 1;
2928                 glyph->faces.items[i][2] = i + 2;
2929             }
2930             return S_OK;
2931         }
2932     }
2933
2934     /* Perform 2D polygon triangulation for complex glyphs.
2935      * Triangulation is performed using a sweep line concept, from right to left,
2936      * by processing vertices in sorted order. Complex polygons are split into
2937      * monotone polygons which are triangulated separately. */
2938     /* FIXME: The order of the faces is not consistent with the native implementation. */
2939
2940     /* Reserve space for maximum possible faces from triangulation.
2941      * # faces for outer outlines = outline->count - 2
2942      * # faces for inner outlines = outline->count + 2
2943      * There must be at least 1 outer outline. */
2944     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
2945             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
2946     if (!glyph->faces.items)
2947         return E_OUTOFMEMORY;
2948
2949     qsort(glyph->ordered_vertices.items, nb_vertices,
2950           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
2951     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
2952     {
2953         int start = 0;
2954         int end = triangulations->count;
2955
2956         while (start < end)
2957         {
2958             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
2959             int current = (start + end) / 2;
2960             struct triangulation *t = &triangulations->items[current];
2961             BOOL on_top_outline = FALSE;
2962             D3DXVECTOR2 *top_next, *bottom_next;
2963             WORD top_idx, bottom_idx;
2964
2965             if (t->merging && t->last_on_top)
2966                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
2967             else
2968                 top_next = triangulation_get_next_point(t, glyph, TRUE);
2969             if (sweep_vtx == top_next)
2970             {
2971                 if (t->merging && t->last_on_top)
2972                     t++;
2973                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
2974                 if (hr != S_OK) return hr;
2975
2976                 if (t + 1 < &triangulations->items[triangulations->count] &&
2977                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
2978                 {
2979                     /* point also on bottom outline of higher triangulation */
2980                     struct triangulation *t2 = t + 1;
2981                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
2982                     if (hr != S_OK) return hr;
2983
2984                     t->merging = TRUE;
2985                     t2->merging = TRUE;
2986                 }
2987                 on_top_outline = TRUE;
2988             }
2989
2990             if (t->merging && !t->last_on_top)
2991                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
2992             else
2993                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
2994             if (sweep_vtx == bottom_next)
2995             {
2996                 if (t->merging && !t->last_on_top)
2997                     t--;
2998                 if (on_top_outline) {
2999                     /* outline finished */
3000                     remove_triangulation(triangulations, t);
3001                     break;
3002                 }
3003
3004                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
3005                 if (hr != S_OK) return hr;
3006
3007                 if (t > triangulations->items &&
3008                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
3009                 {
3010                     struct triangulation *t2 = t - 1;
3011                     /* point also on top outline of lower triangulation */
3012                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
3013                     if (hr != S_OK) return hr;
3014                     t = t2 + 1; /* t may be invalidated by triangulation merging */
3015
3016                     t->merging = TRUE;
3017                     t2->merging = TRUE;
3018                 }
3019                 break;
3020             }
3021             if (on_top_outline)
3022                 break;
3023
3024             if (t->last_on_top) {
3025                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
3026                 bottom_idx = t->vertex_stack.items[0];
3027             } else {
3028                 top_idx = t->vertex_stack.items[0];
3029                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
3030             }
3031
3032             /* check if the point is inside or outside this polygon */
3033             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
3034                                              top_next, sweep_vtx) > 0)
3035             { /* above */
3036                 start = current + 1;
3037             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
3038                                                     bottom_next, sweep_vtx) < 0)
3039             { /* below */
3040                 end = current;
3041             } else if (t->merging) {
3042                 /* inside, so cancel merging */
3043                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
3044                 t->merging = FALSE;
3045                 t2->merging = FALSE;
3046                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
3047                 if (hr != S_OK) return hr;
3048                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
3049                 if (hr != S_OK) return hr;
3050                 break;
3051             } else {
3052                 /* inside, so split polygon into two monotone parts */
3053                 struct triangulation *t2 = add_triangulation(triangulations);
3054                 if (!t2) return E_OUTOFMEMORY;
3055                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
3056                 if (t->last_on_top) {
3057                     t2 = t + 1;
3058                 } else {
3059                     t2 = t;
3060                     t++;
3061                 }
3062
3063                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
3064                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
3065                 if (hr != S_OK) return hr;
3066                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
3067                 if (hr != S_OK) return hr;
3068                 t2->last_on_top = !t->last_on_top;
3069
3070                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
3071                 if (hr != S_OK) return hr;
3072                 break;
3073             }
3074         }
3075         if (start >= end)
3076         {
3077             struct triangulation *t;
3078             struct triangulation *t2 = add_triangulation(triangulations);
3079             if (!t2) return E_OUTOFMEMORY;
3080             t = &triangulations->items[start];
3081             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
3082             ZeroMemory(t, sizeof(*t));
3083             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
3084             if (hr != S_OK) return hr;
3085         }
3086     }
3087     return S_OK;
3088 }
3089
3090 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
3091                                HDC hdc, LPCWSTR text,
3092                                FLOAT deviation, FLOAT extrusion,
3093                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
3094                                LPGLYPHMETRICSFLOAT glyphmetrics)
3095 {
3096     HRESULT hr;
3097     ID3DXMesh *mesh = NULL;
3098     DWORD nb_vertices, nb_faces;
3099     DWORD nb_front_faces, nb_corners, nb_outline_points;
3100     struct vertex *vertices = NULL;
3101     face *faces = NULL;
3102     int textlen = 0;
3103     float offset_x;
3104     LOGFONTW lf;
3105     OUTLINETEXTMETRICW otm;
3106     HFONT font = NULL, oldfont = NULL;
3107     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
3108     void *raw_outline = NULL;
3109     int bufsize = 0;
3110     struct glyphinfo *glyphs = NULL;
3111     GLYPHMETRICS gm;
3112     struct triangulation_array triangulations = {0, 0, NULL};
3113     int i;
3114     struct vertex *vertex_ptr;
3115     face *face_ptr;
3116     float max_deviation_sq;
3117     const struct cos_table cos_table = {
3118         cos(D3DXToRadian(0.5f)),
3119         cos(D3DXToRadian(45.0f)),
3120         cos(D3DXToRadian(90.0f)),
3121     };
3122     int f1, f2;
3123
3124     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
3125           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
3126
3127     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
3128         return D3DERR_INVALIDCALL;
3129
3130     if (adjacency)
3131     {
3132         FIXME("Case of adjacency != NULL not implemented.\n");
3133         return E_NOTIMPL;
3134     }
3135
3136     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
3137         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
3138     {
3139         return D3DERR_INVALIDCALL;
3140     }
3141
3142     if (deviation == 0.0f)
3143         deviation = 1.0f / otm.otmEMSquare;
3144     max_deviation_sq = deviation * deviation;
3145
3146     lf.lfHeight = otm.otmEMSquare;
3147     lf.lfWidth = 0;
3148     font = CreateFontIndirectW(&lf);
3149     if (!font) {
3150         hr = E_OUTOFMEMORY;
3151         goto error;
3152     }
3153     oldfont = SelectObject(hdc, font);
3154
3155     textlen = strlenW(text);
3156     for (i = 0; i < textlen; i++)
3157     {
3158         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
3159         if (datasize < 0)
3160             return D3DERR_INVALIDCALL;
3161         if (bufsize < datasize)
3162             bufsize = datasize;
3163     }
3164     if (!bufsize) { /* e.g. text == " " */
3165         hr = D3DERR_INVALIDCALL;
3166         goto error;
3167     }
3168
3169     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
3170     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
3171     if (!glyphs || !raw_outline) {
3172         hr = E_OUTOFMEMORY;
3173         goto error;
3174     }
3175
3176     offset_x = 0.0f;
3177     for (i = 0; i < textlen; i++)
3178     {
3179         /* get outline points from data returned from GetGlyphOutline */
3180         int datasize;
3181
3182         glyphs[i].offset_x = offset_x;
3183
3184         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
3185         hr = create_outline(&glyphs[i], raw_outline, datasize,
3186                             max_deviation_sq, otm.otmEMSquare, &cos_table);
3187         if (hr != S_OK) goto error;
3188
3189         triangulations.glyph = &glyphs[i];
3190         hr = triangulate(&triangulations);
3191         if (hr != S_OK) goto error;
3192         if (triangulations.count) {
3193             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
3194             triangulations.count = 0;
3195         }
3196
3197         if (glyphmetrics)
3198         {
3199             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
3200             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
3201             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
3202             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
3203             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
3204             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
3205         }
3206         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
3207     }
3208
3209     /* corner points need an extra vertex for the different side faces normals */
3210     nb_corners = 0;
3211     nb_outline_points = 0;
3212     nb_front_faces = 0;
3213     for (i = 0; i < textlen; i++)
3214     {
3215         int j;
3216         nb_outline_points += glyphs[i].ordered_vertices.count;
3217         nb_front_faces += glyphs[i].faces.count;
3218         for (j = 0; j < glyphs[i].outlines.count; j++)
3219         {
3220             int k;
3221             struct outline *outline = &glyphs[i].outlines.items[j];
3222             nb_corners++; /* first outline point always repeated as a corner */
3223             for (k = 1; k < outline->count; k++)
3224                 if (outline->items[k].corner)
3225                     nb_corners++;
3226         }
3227     }
3228
3229     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
3230     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
3231
3232
3233     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
3234                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
3235     if (FAILED(hr))
3236         goto error;
3237
3238     hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&vertices);
3239     if (FAILED(hr))
3240         goto error;
3241
3242     hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&faces);
3243     if (FAILED(hr))
3244         goto error;
3245
3246     /* convert 2D vertices and faces into 3D mesh */
3247     vertex_ptr = vertices;
3248     face_ptr = faces;
3249     if (extrusion == 0.0f) {
3250         f1 = 1;
3251         f2 = 2;
3252     } else {
3253         f1 = 2;
3254         f2 = 1;
3255     }
3256     for (i = 0; i < textlen; i++)
3257     {
3258         int j;
3259         int count;
3260         struct vertex *back_vertices;
3261         face *back_faces;
3262
3263         /* side vertices and faces */
3264         for (j = 0; j < glyphs[i].outlines.count; j++)
3265         {
3266             struct vertex *outline_vertices = vertex_ptr;
3267             struct outline *outline = &glyphs[i].outlines.items[j];
3268             int k;
3269             struct point2d *prevpt = &outline->items[outline->count - 1];
3270             struct point2d *pt = &outline->items[0];
3271
3272             for (k = 1; k <= outline->count; k++)
3273             {
3274                 struct vertex vtx;
3275                 struct point2d *nextpt = &outline->items[k % outline->count];
3276                 WORD vtx_idx = vertex_ptr - vertices;
3277                 D3DXVECTOR2 vec;
3278
3279                 if (pt->corner == POINTTYPE_CURVE_START)
3280                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
3281                 else if (pt->corner)
3282                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
3283                 else
3284                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
3285                 D3DXVec2Normalize(&vec, &vec);
3286                 vtx.normal.x = -vec.y;
3287                 vtx.normal.y = vec.x;
3288                 vtx.normal.z = 0;
3289
3290                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
3291                 vtx.position.y = pt->pos.y;
3292                 vtx.position.z = 0;
3293                 *vertex_ptr++ = vtx;
3294
3295                 vtx.position.z = -extrusion;
3296                 *vertex_ptr++ = vtx;
3297
3298                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
3299                 vtx.position.y = nextpt->pos.y;
3300                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
3301                     vtx.position.z = -extrusion;
3302                     *vertex_ptr++ = vtx;
3303                     vtx.position.z = 0;
3304                     *vertex_ptr++ = vtx;
3305
3306                     (*face_ptr)[0] = vtx_idx;
3307                     (*face_ptr)[1] = vtx_idx + 2;
3308                     (*face_ptr)[2] = vtx_idx + 1;
3309                     face_ptr++;
3310
3311                     (*face_ptr)[0] = vtx_idx;
3312                     (*face_ptr)[1] = vtx_idx + 3;
3313                     (*face_ptr)[2] = vtx_idx + 2;
3314                     face_ptr++;
3315                 } else {
3316                     if (nextpt->corner) {
3317                         if (nextpt->corner == POINTTYPE_CURVE_END) {
3318                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
3319                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
3320                         } else {
3321                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
3322                         }
3323                         D3DXVec2Normalize(&vec, &vec);
3324                         vtx.normal.x = -vec.y;
3325                         vtx.normal.y = vec.x;
3326
3327                         vtx.position.z = 0;
3328                         *vertex_ptr++ = vtx;
3329                         vtx.position.z = -extrusion;
3330                         *vertex_ptr++ = vtx;
3331                     }
3332
3333                     (*face_ptr)[0] = vtx_idx;
3334                     (*face_ptr)[1] = vtx_idx + 3;
3335                     (*face_ptr)[2] = vtx_idx + 1;
3336                     face_ptr++;
3337
3338                     (*face_ptr)[0] = vtx_idx;
3339                     (*face_ptr)[1] = vtx_idx + 2;
3340                     (*face_ptr)[2] = vtx_idx + 3;
3341                     face_ptr++;
3342                 }
3343
3344                 prevpt = pt;
3345                 pt = nextpt;
3346             }
3347             if (!pt->corner) {
3348                 *vertex_ptr++ = *outline_vertices++;
3349                 *vertex_ptr++ = *outline_vertices++;
3350             }
3351         }
3352
3353         /* back vertices and faces */
3354         back_faces = face_ptr;
3355         back_vertices = vertex_ptr;
3356         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
3357         {
3358             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
3359             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
3360             vertex_ptr->position.y = pt->y;
3361             vertex_ptr->position.z = 0;
3362             vertex_ptr->normal.x = 0;
3363             vertex_ptr->normal.y = 0;
3364             vertex_ptr->normal.z = 1;
3365             vertex_ptr++;
3366         }
3367         count = back_vertices - vertices;
3368         for (j = 0; j < glyphs[i].faces.count; j++)
3369         {
3370             face *f = &glyphs[i].faces.items[j];
3371             (*face_ptr)[0] = (*f)[0] + count;
3372             (*face_ptr)[1] = (*f)[1] + count;
3373             (*face_ptr)[2] = (*f)[2] + count;
3374             face_ptr++;
3375         }
3376
3377         /* front vertices and faces */
3378         j = count = vertex_ptr - back_vertices;
3379         while (j--)
3380         {
3381             vertex_ptr->position.x = back_vertices->position.x;
3382             vertex_ptr->position.y = back_vertices->position.y;
3383             vertex_ptr->position.z = -extrusion;
3384             vertex_ptr->normal.x = 0;
3385             vertex_ptr->normal.y = 0;
3386             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
3387             vertex_ptr++;
3388             back_vertices++;
3389         }
3390         j = face_ptr - back_faces;
3391         while (j--)
3392         {
3393             (*face_ptr)[0] = (*back_faces)[0] + count;
3394             (*face_ptr)[1] = (*back_faces)[f1] + count;
3395             (*face_ptr)[2] = (*back_faces)[f2] + count;
3396             face_ptr++;
3397             back_faces++;
3398         }
3399     }
3400
3401     *mesh_ptr = mesh;
3402     hr = D3D_OK;
3403 error:
3404     if (mesh) {
3405         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
3406         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
3407         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
3408     }
3409     if (glyphs) {
3410         for (i = 0; i < textlen; i++)
3411         {
3412             int j;
3413             for (j = 0; j < glyphs[i].outlines.count; j++)
3414                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
3415             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
3416             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
3417             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
3418         }
3419         HeapFree(GetProcessHeap(), 0, glyphs);
3420     }
3421     if (triangulations.items) {
3422         int i;
3423         for (i = 0; i < triangulations.count; i++)
3424             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
3425         HeapFree(GetProcessHeap(), 0, triangulations.items);
3426     }
3427     HeapFree(GetProcessHeap(), 0, raw_outline);
3428     if (oldfont) SelectObject(hdc, oldfont);
3429     if (font) DeleteObject(font);
3430
3431     return hr;
3432 }