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