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

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