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