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