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