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