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