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, temp1;
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     temp1 = temp;
2004     *pradius = 0.0f;
2005
2006     for(i=0; i<numvertices; i++)
2007     {
2008         D3DXVec3Add(&temp1, &temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i));
2009         temp = temp1;
2010     }
2011
2012     D3DXVec3Scale(pcenter, &temp, 1.0f/((FLOAT)numvertices));
2013
2014     for(i=0; i<numvertices; i++)
2015     {
2016         d = D3DXVec3Length(D3DXVec3Subtract(&temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i), pcenter));
2017         if ( d > *pradius ) *pradius = d;
2018     }
2019     return D3D_OK;
2020 }
2021
2022 static void append_decl_element(D3DVERTEXELEMENT9 *declaration, UINT *idx, UINT *offset,
2023         D3DDECLTYPE type, D3DDECLUSAGE usage, UINT usage_idx)
2024 {
2025     declaration[*idx].Stream = 0;
2026     declaration[*idx].Offset = *offset;
2027     declaration[*idx].Type = type;
2028     declaration[*idx].Method = D3DDECLMETHOD_DEFAULT;
2029     declaration[*idx].Usage = usage;
2030     declaration[*idx].UsageIndex = usage_idx;
2031
2032     *offset += d3dx_decltype_size[type];
2033     ++(*idx);
2034 }
2035
2036 /*************************************************************************
2037  * D3DXDeclaratorFromFVF
2038  */
2039 HRESULT WINAPI D3DXDeclaratorFromFVF(DWORD fvf, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
2040 {
2041     static const D3DVERTEXELEMENT9 end_element = D3DDECL_END();
2042     DWORD tex_count = (fvf & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
2043     unsigned int offset = 0;
2044     unsigned int idx = 0;
2045     unsigned int i;
2046
2047     TRACE("fvf %#x, declaration %p.\n", fvf, declaration);
2048
2049     if (fvf & (D3DFVF_RESERVED0 | D3DFVF_RESERVED2)) return D3DERR_INVALIDCALL;
2050
2051     if (fvf & D3DFVF_POSITION_MASK)
2052     {
2053         BOOL has_blend = (fvf & D3DFVF_XYZB5) >= D3DFVF_XYZB1;
2054         DWORD blend_count = 1 + (((fvf & D3DFVF_XYZB5) - D3DFVF_XYZB1) >> 1);
2055         BOOL has_blend_idx = (fvf & D3DFVF_LASTBETA_D3DCOLOR) || (fvf & D3DFVF_LASTBETA_UBYTE4);
2056
2057         if (has_blend_idx) --blend_count;
2058
2059         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZW
2060                 || (has_blend && blend_count > 4))
2061             return D3DERR_INVALIDCALL;
2062
2063         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZRHW)
2064             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_POSITIONT, 0);
2065         else
2066             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_POSITION, 0);
2067
2068         if (has_blend)
2069         {
2070             switch (blend_count)
2071             {
2072                  case 0:
2073                     break;
2074                  case 1:
2075                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_BLENDWEIGHT, 0);
2076                     break;
2077                  case 2:
2078                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_BLENDWEIGHT, 0);
2079                     break;
2080                  case 3:
2081                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_BLENDWEIGHT, 0);
2082                     break;
2083                  case 4:
2084                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_BLENDWEIGHT, 0);
2085                     break;
2086                  default:
2087                      ERR("Invalid blend count %u.\n", blend_count);
2088                      break;
2089             }
2090
2091             if (has_blend_idx)
2092             {
2093                 if (fvf & D3DFVF_LASTBETA_UBYTE4)
2094                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_UBYTE4, D3DDECLUSAGE_BLENDINDICES, 0);
2095                 else if (fvf & D3DFVF_LASTBETA_D3DCOLOR)
2096                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_BLENDINDICES, 0);
2097             }
2098         }
2099     }
2100
2101     if (fvf & D3DFVF_NORMAL)
2102         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_NORMAL, 0);
2103     if (fvf & D3DFVF_PSIZE)
2104         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_PSIZE, 0);
2105     if (fvf & D3DFVF_DIFFUSE)
2106         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 0);
2107     if (fvf & D3DFVF_SPECULAR)
2108         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 1);
2109
2110     for (i = 0; i < tex_count; ++i)
2111     {
2112         switch ((fvf >> (16 + 2 * i)) & 0x03)
2113         {
2114             case D3DFVF_TEXTUREFORMAT1:
2115                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_TEXCOORD, i);
2116                 break;
2117             case D3DFVF_TEXTUREFORMAT2:
2118                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_TEXCOORD, i);
2119                 break;
2120             case D3DFVF_TEXTUREFORMAT3:
2121                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_TEXCOORD, i);
2122                 break;
2123             case D3DFVF_TEXTUREFORMAT4:
2124                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_TEXCOORD, i);
2125                 break;
2126         }
2127     }
2128
2129     declaration[idx] = end_element;
2130
2131     return D3D_OK;
2132 }
2133
2134 /*************************************************************************
2135  * D3DXFVFFromDeclarator
2136  */
2137 HRESULT WINAPI D3DXFVFFromDeclarator(const D3DVERTEXELEMENT9 *declaration, DWORD *fvf)
2138 {
2139     unsigned int i = 0, texture, offset;
2140
2141     TRACE("(%p, %p)\n", declaration, fvf);
2142
2143     *fvf = 0;
2144     if (declaration[0].Type == D3DDECLTYPE_FLOAT3 && declaration[0].Usage == D3DDECLUSAGE_POSITION)
2145     {
2146         if ((declaration[1].Type == D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
2147              declaration[1].UsageIndex == 0) &&
2148             (declaration[2].Type == D3DDECLTYPE_FLOAT1 && declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES &&
2149              declaration[2].UsageIndex == 0))
2150         {
2151             return D3DERR_INVALIDCALL;
2152         }
2153         else if ((declaration[1].Type == D3DDECLTYPE_UBYTE4 || declaration[1].Type == D3DDECLTYPE_D3DCOLOR) &&
2154                  declaration[1].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[1].UsageIndex == 0)
2155         {
2156             if (declaration[1].Type == D3DDECLTYPE_UBYTE4)
2157             {
2158                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_UBYTE4;
2159             }
2160             else
2161             {
2162                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_D3DCOLOR;
2163             }
2164             i = 2;
2165         }
2166         else if (declaration[1].Type <= D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
2167                  declaration[1].UsageIndex == 0)
2168         {
2169             if ((declaration[2].Type == D3DDECLTYPE_UBYTE4 || declaration[2].Type == D3DDECLTYPE_D3DCOLOR) &&
2170                 declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[2].UsageIndex == 0)
2171             {
2172                 if (declaration[2].Type == D3DDECLTYPE_UBYTE4)
2173                 {
2174                     *fvf |= D3DFVF_LASTBETA_UBYTE4;
2175                 }
2176                 else
2177                 {
2178                     *fvf |= D3DFVF_LASTBETA_D3DCOLOR;
2179                 }
2180                 switch (declaration[1].Type)
2181                 {
2182                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB2; break;
2183                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB3; break;
2184                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB4; break;
2185                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB5; break;
2186                 }
2187                 i = 3;
2188             }
2189             else
2190             {
2191                 switch (declaration[1].Type)
2192                 {
2193                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB1; break;
2194                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB2; break;
2195                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB3; break;
2196                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB4; break;
2197                 }
2198                 i = 2;
2199             }
2200         }
2201         else
2202         {
2203             *fvf |= D3DFVF_XYZ;
2204             i = 1;
2205         }
2206     }
2207     else if (declaration[0].Type == D3DDECLTYPE_FLOAT4 && declaration[0].Usage == D3DDECLUSAGE_POSITIONT &&
2208              declaration[0].UsageIndex == 0)
2209     {
2210         *fvf |= D3DFVF_XYZRHW;
2211         i = 1;
2212     }
2213
2214     if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_NORMAL)
2215     {
2216         *fvf |= D3DFVF_NORMAL;
2217         i++;
2218     }
2219     if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_PSIZE &&
2220         declaration[i].UsageIndex == 0)
2221     {
2222         *fvf |= D3DFVF_PSIZE;
2223         i++;
2224     }
2225     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
2226         declaration[i].UsageIndex == 0)
2227     {
2228         *fvf |= D3DFVF_DIFFUSE;
2229         i++;
2230     }
2231     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
2232         declaration[i].UsageIndex == 1)
2233     {
2234         *fvf |= D3DFVF_SPECULAR;
2235         i++;
2236     }
2237
2238     for (texture = 0; texture < D3DDP_MAXTEXCOORD; i++, texture++)
2239     {
2240         if (declaration[i].Stream == 0xFF)
2241         {
2242             break;
2243         }
2244         else if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
2245                  declaration[i].UsageIndex == texture)
2246         {
2247             *fvf |= D3DFVF_TEXCOORDSIZE1(declaration[i].UsageIndex);
2248         }
2249         else if (declaration[i].Type == D3DDECLTYPE_FLOAT2 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
2250                  declaration[i].UsageIndex == texture)
2251         {
2252             *fvf |= D3DFVF_TEXCOORDSIZE2(declaration[i].UsageIndex);
2253         }
2254         else if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
2255                  declaration[i].UsageIndex == texture)
2256         {
2257             *fvf |= D3DFVF_TEXCOORDSIZE3(declaration[i].UsageIndex);
2258         }
2259         else if (declaration[i].Type == D3DDECLTYPE_FLOAT4 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
2260                  declaration[i].UsageIndex == texture)
2261         {
2262             *fvf |= D3DFVF_TEXCOORDSIZE4(declaration[i].UsageIndex);
2263         }
2264         else
2265         {
2266             return D3DERR_INVALIDCALL;
2267         }
2268     }
2269
2270     *fvf |= (texture << D3DFVF_TEXCOUNT_SHIFT);
2271
2272     for (offset = 0, i = 0; declaration[i].Stream != 0xFF;
2273          offset += d3dx_decltype_size[declaration[i].Type], i++)
2274     {
2275         if (declaration[i].Offset != offset)
2276         {
2277             return D3DERR_INVALIDCALL;
2278         }
2279     }
2280
2281     return D3D_OK;
2282 }
2283
2284 /*************************************************************************
2285  * D3DXGetFVFVertexSize
2286  */
2287 static UINT Get_TexCoord_Size_From_FVF(DWORD FVF, int tex_num)
2288 {
2289     return (((((FVF) >> (16 + (2 * (tex_num)))) + 1) & 0x03) + 1);
2290 }
2291
2292 UINT WINAPI D3DXGetFVFVertexSize(DWORD FVF)
2293 {
2294     DWORD size = 0;
2295     UINT i;
2296     UINT numTextures = (FVF & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
2297
2298     if (FVF & D3DFVF_NORMAL) size += sizeof(D3DXVECTOR3);
2299     if (FVF & D3DFVF_DIFFUSE) size += sizeof(DWORD);
2300     if (FVF & D3DFVF_SPECULAR) size += sizeof(DWORD);
2301     if (FVF & D3DFVF_PSIZE) size += sizeof(DWORD);
2302
2303     switch (FVF & D3DFVF_POSITION_MASK)
2304     {
2305         case D3DFVF_XYZ:    size += sizeof(D3DXVECTOR3); break;
2306         case D3DFVF_XYZRHW: size += 4 * sizeof(FLOAT); break;
2307         case D3DFVF_XYZB1:  size += 4 * sizeof(FLOAT); break;
2308         case D3DFVF_XYZB2:  size += 5 * sizeof(FLOAT); break;
2309         case D3DFVF_XYZB3:  size += 6 * sizeof(FLOAT); break;
2310         case D3DFVF_XYZB4:  size += 7 * sizeof(FLOAT); break;
2311         case D3DFVF_XYZB5:  size += 8 * sizeof(FLOAT); break;
2312         case D3DFVF_XYZW:   size += 4 * sizeof(FLOAT); break;
2313     }
2314
2315     for (i = 0; i < numTextures; i++)
2316     {
2317         size += Get_TexCoord_Size_From_FVF(FVF, i) * sizeof(FLOAT);
2318     }
2319
2320     return size;
2321 }
2322
2323 /*************************************************************************
2324  * D3DXGetDeclVertexSize
2325  */
2326 UINT WINAPI D3DXGetDeclVertexSize(const D3DVERTEXELEMENT9 *decl, DWORD stream_idx)
2327 {
2328     const D3DVERTEXELEMENT9 *element;
2329     UINT size = 0;
2330
2331     TRACE("decl %p, stream_idx %u\n", decl, stream_idx);
2332
2333     if (!decl) return 0;
2334
2335     for (element = decl; element->Stream != 0xff; ++element)
2336     {
2337         UINT type_size;
2338
2339         if (element->Stream != stream_idx) continue;
2340
2341         if (element->Type >= sizeof(d3dx_decltype_size) / sizeof(*d3dx_decltype_size))
2342         {
2343             FIXME("Unhandled element type %#x, size will be incorrect.\n", element->Type);
2344             continue;
2345         }
2346
2347         type_size = d3dx_decltype_size[element->Type];
2348         if (element->Offset + type_size > size) size = element->Offset + type_size;
2349     }
2350
2351     return size;
2352 }
2353
2354 /*************************************************************************
2355  * D3DXGetDeclLength
2356  */
2357 UINT WINAPI D3DXGetDeclLength(const D3DVERTEXELEMENT9 *decl)
2358 {
2359     const D3DVERTEXELEMENT9 *element;
2360
2361     TRACE("decl %p\n", decl);
2362
2363     /* null decl results in exception on Windows XP */
2364
2365     for (element = decl; element->Stream != 0xff; ++element);
2366
2367     return element - decl;
2368 }
2369
2370 /*************************************************************************
2371  * D3DXIntersectTri
2372  */
2373 BOOL WINAPI D3DXIntersectTri(CONST D3DXVECTOR3 *p0, CONST D3DXVECTOR3 *p1, CONST D3DXVECTOR3 *p2, CONST D3DXVECTOR3 *praypos, CONST D3DXVECTOR3 *praydir, FLOAT *pu, FLOAT *pv, FLOAT *pdist)
2374 {
2375     D3DXMATRIX m;
2376     D3DXVECTOR4 vec;
2377
2378     m.u.m[0][0] = p1->x - p0->x;
2379     m.u.m[1][0] = p2->x - p0->x;
2380     m.u.m[2][0] = -praydir->x;
2381     m.u.m[3][0] = 0.0f;
2382     m.u.m[0][1] = p1->y - p0->z;
2383     m.u.m[1][1] = p2->y - p0->z;
2384     m.u.m[2][1] = -praydir->y;
2385     m.u.m[3][1] = 0.0f;
2386     m.u.m[0][2] = p1->z - p0->z;
2387     m.u.m[1][2] = p2->z - p0->z;
2388     m.u.m[2][2] = -praydir->z;
2389     m.u.m[3][2] = 0.0f;
2390     m.u.m[0][3] = 0.0f;
2391     m.u.m[1][3] = 0.0f;
2392     m.u.m[2][3] = 0.0f;
2393     m.u.m[3][3] = 1.0f;
2394
2395     vec.x = praypos->x - p0->x;
2396     vec.y = praypos->y - p0->y;
2397     vec.z = praypos->z - p0->z;
2398     vec.w = 0.0f;
2399
2400     if ( D3DXMatrixInverse(&m, NULL, &m) )
2401     {
2402         D3DXVec4Transform(&vec, &vec, &m);
2403         if ( (vec.x >= 0.0f) && (vec.y >= 0.0f) && (vec.x + vec.y <= 1.0f) && (vec.z >= 0.0f) )
2404         {
2405             *pu = vec.x;
2406             *pv = vec.y;
2407             *pdist = fabs( vec.z );
2408             return TRUE;
2409         }
2410     }
2411
2412     return FALSE;
2413 }
2414
2415 /*************************************************************************
2416  * D3DXSphereBoundProbe
2417  */
2418 BOOL WINAPI D3DXSphereBoundProbe(CONST D3DXVECTOR3 *pcenter, FLOAT radius, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
2419 {
2420     D3DXVECTOR3 difference;
2421     FLOAT a, b, c, d;
2422
2423     a = D3DXVec3LengthSq(praydirection);
2424     if (!D3DXVec3Subtract(&difference, prayposition, pcenter)) return FALSE;
2425     b = D3DXVec3Dot(&difference, praydirection);
2426     c = D3DXVec3LengthSq(&difference) - radius * radius;
2427     d = b * b - a * c;
2428
2429     if ( ( d <= 0.0f ) || ( sqrt(d) <= b ) ) return FALSE;
2430     return TRUE;
2431 }
2432
2433 /*************************************************************************
2434  * D3DXCreateMesh
2435  */
2436 HRESULT WINAPI D3DXCreateMesh(DWORD numfaces, DWORD numvertices, DWORD options, CONST D3DVERTEXELEMENT9 *declaration,
2437                               LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
2438 {
2439     HRESULT hr;
2440     DWORD fvf;
2441     IDirect3DVertexDeclaration9 *vertex_declaration;
2442     UINT vertex_declaration_size;
2443     UINT num_elem;
2444     IDirect3DVertexBuffer9 *vertex_buffer;
2445     IDirect3DIndexBuffer9 *index_buffer;
2446     DWORD *attrib_buffer;
2447     ID3DXMeshImpl *object;
2448     DWORD index_usage = 0;
2449     D3DPOOL index_pool = D3DPOOL_DEFAULT;
2450     D3DFORMAT index_format = D3DFMT_INDEX16;
2451     DWORD vertex_usage = 0;
2452     D3DPOOL vertex_pool = D3DPOOL_DEFAULT;
2453     int i;
2454
2455     TRACE("(%d, %d, %x, %p, %p, %p)\n", numfaces, numvertices, options, declaration, device, mesh);
2456
2457     if (numfaces == 0 || numvertices == 0 || declaration == NULL || device == NULL || mesh == NULL ||
2458         /* D3DXMESH_VB_SHARE is for cloning, and D3DXMESH_USEHWONLY is for ConvertToBlendedMesh */
2459         (options & (D3DXMESH_VB_SHARE | D3DXMESH_USEHWONLY | 0xfffe0000)))
2460     {
2461         return D3DERR_INVALIDCALL;
2462     }
2463     for (i = 0; declaration[i].Stream != 0xff; i++)
2464         if (declaration[i].Stream != 0)
2465             return D3DERR_INVALIDCALL;
2466     num_elem = i + 1;
2467
2468     if (options & D3DXMESH_32BIT)
2469         index_format = D3DFMT_INDEX32;
2470
2471     if (options & D3DXMESH_DONOTCLIP) {
2472         index_usage |= D3DUSAGE_DONOTCLIP;
2473         vertex_usage |= D3DUSAGE_DONOTCLIP;
2474     }
2475     if (options & D3DXMESH_POINTS) {
2476         index_usage |= D3DUSAGE_POINTS;
2477         vertex_usage |= D3DUSAGE_POINTS;
2478     }
2479     if (options & D3DXMESH_RTPATCHES) {
2480         index_usage |= D3DUSAGE_RTPATCHES;
2481         vertex_usage |= D3DUSAGE_RTPATCHES;
2482     }
2483     if (options & D3DXMESH_NPATCHES) {
2484         index_usage |= D3DUSAGE_NPATCHES;
2485         vertex_usage |= D3DUSAGE_NPATCHES;
2486     }
2487
2488     if (options & D3DXMESH_VB_SYSTEMMEM)
2489         vertex_pool = D3DPOOL_SYSTEMMEM;
2490     else if (options & D3DXMESH_VB_MANAGED)
2491         vertex_pool = D3DPOOL_MANAGED;
2492
2493     if (options & D3DXMESH_VB_WRITEONLY)
2494         vertex_usage |= D3DUSAGE_WRITEONLY;
2495     if (options & D3DXMESH_VB_DYNAMIC)
2496         vertex_usage |= D3DUSAGE_DYNAMIC;
2497     if (options & D3DXMESH_VB_SOFTWAREPROCESSING)
2498         vertex_usage |= D3DUSAGE_SOFTWAREPROCESSING;
2499
2500     if (options & D3DXMESH_IB_SYSTEMMEM)
2501         index_pool = D3DPOOL_SYSTEMMEM;
2502     else if (options & D3DXMESH_IB_MANAGED)
2503         index_pool = D3DPOOL_MANAGED;
2504
2505     if (options & D3DXMESH_IB_WRITEONLY)
2506         index_usage |= D3DUSAGE_WRITEONLY;
2507     if (options & D3DXMESH_IB_DYNAMIC)
2508         index_usage |= D3DUSAGE_DYNAMIC;
2509     if (options & D3DXMESH_IB_SOFTWAREPROCESSING)
2510         index_usage |= D3DUSAGE_SOFTWAREPROCESSING;
2511
2512     hr = D3DXFVFFromDeclarator(declaration, &fvf);
2513     if (hr != D3D_OK)
2514     {
2515         fvf = 0;
2516     }
2517
2518     /* Create vertex declaration */
2519     hr = IDirect3DDevice9_CreateVertexDeclaration(device,
2520                                                   declaration,
2521                                                   &vertex_declaration);
2522     if (FAILED(hr))
2523     {
2524         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexDeclaration.\n",hr);
2525         return hr;
2526     }
2527     vertex_declaration_size = D3DXGetDeclVertexSize(declaration, declaration[0].Stream);
2528
2529     /* Create vertex buffer */
2530     hr = IDirect3DDevice9_CreateVertexBuffer(device,
2531                                              numvertices * vertex_declaration_size,
2532                                              vertex_usage,
2533                                              fvf,
2534                                              vertex_pool,
2535                                              &vertex_buffer,
2536                                              NULL);
2537     if (FAILED(hr))
2538     {
2539         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
2540         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2541         return hr;
2542     }
2543
2544     /* Create index buffer */
2545     hr = IDirect3DDevice9_CreateIndexBuffer(device,
2546                                             numfaces * 3 * ((index_format == D3DFMT_INDEX16) ? 2 : 4),
2547                                             index_usage,
2548                                             index_format,
2549                                             index_pool,
2550                                             &index_buffer,
2551                                             NULL);
2552     if (FAILED(hr))
2553     {
2554         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
2555         IDirect3DVertexBuffer9_Release(vertex_buffer);
2556         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2557         return hr;
2558     }
2559
2560     attrib_buffer = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, numfaces * sizeof(*attrib_buffer));
2561     object = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(ID3DXMeshImpl));
2562     if (object == NULL || attrib_buffer == NULL)
2563     {
2564         HeapFree(GetProcessHeap(), 0, attrib_buffer);
2565         IDirect3DIndexBuffer9_Release(index_buffer);
2566         IDirect3DVertexBuffer9_Release(vertex_buffer);
2567         IDirect3DVertexDeclaration9_Release(vertex_declaration);
2568         *mesh = NULL;
2569         return E_OUTOFMEMORY;
2570     }
2571     object->ID3DXMesh_iface.lpVtbl = &D3DXMesh_Vtbl;
2572     object->ref = 1;
2573
2574     object->numfaces = numfaces;
2575     object->numvertices = numvertices;
2576     object->options = options;
2577     object->fvf = fvf;
2578     object->device = device;
2579     IDirect3DDevice9_AddRef(device);
2580
2581     copy_declaration(object->cached_declaration, declaration, num_elem);
2582     object->vertex_declaration = vertex_declaration;
2583     object->vertex_declaration_size = vertex_declaration_size;
2584     object->num_elem = num_elem;
2585     object->vertex_buffer = vertex_buffer;
2586     object->index_buffer = index_buffer;
2587     object->attrib_buffer = attrib_buffer;
2588
2589     *mesh = &object->ID3DXMesh_iface;
2590
2591     return D3D_OK;
2592 }
2593
2594 /*************************************************************************
2595  * D3DXCreateMeshFVF
2596  */
2597 HRESULT WINAPI D3DXCreateMeshFVF(DWORD numfaces, DWORD numvertices, DWORD options, DWORD fvf,
2598                                  LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
2599 {
2600     HRESULT hr;
2601     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
2602
2603     TRACE("(%u, %u, %u, %u, %p, %p)\n", numfaces, numvertices, options, fvf, device, mesh);
2604
2605     hr = D3DXDeclaratorFromFVF(fvf, declaration);
2606     if (FAILED(hr)) return hr;
2607
2608     return D3DXCreateMesh(numfaces, numvertices, options, declaration, device, mesh);
2609 }
2610
2611
2612 struct mesh_data {
2613     DWORD num_vertices;
2614     DWORD num_poly_faces;
2615     DWORD num_tri_faces;
2616     D3DXVECTOR3 *vertices;
2617     DWORD *num_tri_per_face;
2618     DWORD *indices;
2619
2620     DWORD fvf;
2621
2622     /* optional mesh data */
2623
2624     DWORD num_normals;
2625     D3DXVECTOR3 *normals;
2626     DWORD *normal_indices;
2627
2628     D3DXVECTOR2 *tex_coords;
2629
2630     DWORD *vertex_colors;
2631
2632     DWORD num_materials;
2633     D3DXMATERIAL *materials;
2634     DWORD *material_indices;
2635 };
2636
2637 static HRESULT get_next_child(IDirectXFileData *filedata, IDirectXFileData **child, const GUID **type)
2638 {
2639     HRESULT hr;
2640     IDirectXFileDataReference *child_ref = NULL;
2641     IDirectXFileObject *child_obj = NULL;
2642     IDirectXFileData *child_data = NULL;
2643
2644     hr = IDirectXFileData_GetNextObject(filedata, &child_obj);
2645     if (FAILED(hr)) return hr;
2646
2647     hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileDataReference, (void**)&child_ref);
2648     if (SUCCEEDED(hr)) {
2649         hr = IDirectXFileDataReference_Resolve(child_ref, &child_data);
2650         IDirectXFileDataReference_Release(child_ref);
2651     } else {
2652         hr = IDirectXFileObject_QueryInterface(child_obj, &IID_IDirectXFileData, (void**)&child_data);
2653     }
2654     IDirectXFileObject_Release(child_obj);
2655     if (FAILED(hr))
2656         return hr;
2657
2658     hr = IDirectXFileData_GetType(child_data, type);
2659     if (FAILED(hr)) {
2660         IDirectXFileData_Release(child_data);
2661     } else {
2662         *child = child_data;
2663     }
2664
2665     return hr;
2666 }
2667
2668 static HRESULT parse_texture_filename(IDirectXFileData *filedata, LPSTR *filename_out)
2669 {
2670     HRESULT hr;
2671     DWORD data_size;
2672     BYTE *data;
2673     char *filename_in;
2674     char *filename = NULL;
2675
2676     /* template TextureFilename {
2677      *     STRING filename;
2678      * }
2679      */
2680
2681     HeapFree(GetProcessHeap(), 0, *filename_out);
2682     *filename_out = NULL;
2683
2684     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2685     if (FAILED(hr)) return hr;
2686
2687     if (data_size < sizeof(LPSTR)) {
2688         WARN("truncated data (%u bytes)\n", data_size);
2689         return E_FAIL;
2690     }
2691     filename_in = *(LPSTR*)data;
2692
2693     filename = HeapAlloc(GetProcessHeap(), 0, strlen(filename_in) + 1);
2694     if (!filename) return E_OUTOFMEMORY;
2695
2696     strcpy(filename, filename_in);
2697     *filename_out = filename;
2698
2699     return D3D_OK;
2700 }
2701
2702 static HRESULT parse_material(IDirectXFileData *filedata, D3DXMATERIAL *material)
2703 {
2704     HRESULT hr;
2705     DWORD data_size;
2706     BYTE *data;
2707     const GUID *type;
2708     IDirectXFileData *child;
2709
2710     material->pTextureFilename = NULL;
2711
2712     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2713     if (FAILED(hr)) return hr;
2714
2715     /*
2716      * template ColorRGBA {
2717      *     FLOAT red;
2718      *     FLOAT green;
2719      *     FLOAT blue;
2720      *     FLOAT alpha;
2721      * }
2722      * template ColorRGB {
2723      *     FLOAT red;
2724      *     FLOAT green;
2725      *     FLOAT blue;
2726      * }
2727      * template Material {
2728      *     ColorRGBA faceColor;
2729      *     FLOAT power;
2730      *     ColorRGB specularColor;
2731      *     ColorRGB emissiveColor;
2732      *     [ ... ]
2733      * }
2734      */
2735     if (data_size != sizeof(FLOAT) * 11) {
2736         WARN("incorrect data size (%u bytes)\n", data_size);
2737         return E_FAIL;
2738     }
2739
2740     memcpy(&material->MatD3D.Diffuse, data, sizeof(D3DCOLORVALUE));
2741     data += sizeof(D3DCOLORVALUE);
2742     material->MatD3D.Power = *(FLOAT*)data;
2743     data += sizeof(FLOAT);
2744     memcpy(&material->MatD3D.Specular, data, sizeof(FLOAT) * 3);
2745     material->MatD3D.Specular.a = 1.0f;
2746     data += 3 * sizeof(FLOAT);
2747     memcpy(&material->MatD3D.Emissive, data, sizeof(FLOAT) * 3);
2748     material->MatD3D.Emissive.a = 1.0f;
2749     material->MatD3D.Ambient.r = 0.0f;
2750     material->MatD3D.Ambient.g = 0.0f;
2751     material->MatD3D.Ambient.b = 0.0f;
2752     material->MatD3D.Ambient.a = 1.0f;
2753
2754     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2755     {
2756         if (IsEqualGUID(type, &TID_D3DRMTextureFilename)) {
2757             hr = parse_texture_filename(child, &material->pTextureFilename);
2758             if (FAILED(hr)) break;
2759         }
2760     }
2761     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
2762 }
2763
2764 static void destroy_materials(struct mesh_data *mesh)
2765 {
2766     int i;
2767     for (i = 0; i < mesh->num_materials; i++)
2768         HeapFree(GetProcessHeap(), 0, mesh->materials[i].pTextureFilename);
2769     HeapFree(GetProcessHeap(), 0, mesh->materials);
2770     HeapFree(GetProcessHeap(), 0, mesh->material_indices);
2771     mesh->num_materials = 0;
2772     mesh->materials = NULL;
2773     mesh->material_indices = NULL;
2774 }
2775
2776 static HRESULT parse_material_list(IDirectXFileData *filedata, struct mesh_data *mesh)
2777 {
2778     HRESULT hr;
2779     DWORD data_size;
2780     DWORD *data, *in_ptr;
2781     const GUID *type;
2782     IDirectXFileData *child;
2783     DWORD num_materials;
2784     int i;
2785
2786     destroy_materials(mesh);
2787
2788     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2789     if (FAILED(hr)) return hr;
2790
2791     /* template MeshMaterialList {
2792      *     DWORD nMaterials;
2793      *     DWORD nFaceIndexes;
2794      *     array DWORD faceIndexes[nFaceIndexes];
2795      *     [ Material ]
2796      * }
2797      */
2798
2799     in_ptr = data;
2800
2801     if (data_size < sizeof(DWORD))
2802         goto truncated_data_error;
2803     num_materials = *in_ptr++;
2804     if (!num_materials)
2805         return D3D_OK;
2806
2807     if (data_size < 2 * sizeof(DWORD))
2808         goto truncated_data_error;
2809     if (*in_ptr++ != mesh->num_poly_faces) {
2810         WARN("number of material face indices (%u) doesn't match number of faces (%u)\n",
2811              *(in_ptr - 1), mesh->num_poly_faces);
2812         return E_FAIL;
2813     }
2814     if (data_size < 2 * sizeof(DWORD) + mesh->num_poly_faces * sizeof(DWORD))
2815         goto truncated_data_error;
2816     for (i = 0; i < mesh->num_poly_faces; i++) {
2817         if (*in_ptr++ >= num_materials) {
2818             WARN("face %u: reference to undefined material %u (only %u materials)\n",
2819                  i, *(in_ptr - 1), num_materials);
2820             return E_FAIL;
2821         }
2822     }
2823
2824     mesh->materials = HeapAlloc(GetProcessHeap(), 0, num_materials * sizeof(*mesh->materials));
2825     mesh->material_indices = HeapAlloc(GetProcessHeap(), 0, mesh->num_poly_faces * sizeof(*mesh->material_indices));
2826     if (!mesh->materials || !mesh->material_indices)
2827         return E_OUTOFMEMORY;
2828     memcpy(mesh->material_indices, data + 2, mesh->num_poly_faces * sizeof(DWORD));
2829
2830     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
2831     {
2832         if (IsEqualGUID(type, &TID_D3DRMMaterial)) {
2833             if (mesh->num_materials >= num_materials) {
2834                 WARN("more materials defined than declared\n");
2835                 return E_FAIL;
2836             }
2837             hr = parse_material(child, &mesh->materials[mesh->num_materials++]);
2838             if (FAILED(hr)) break;
2839         }
2840     }
2841     if (hr != DXFILEERR_NOMOREOBJECTS)
2842         return hr;
2843     if (num_materials != mesh->num_materials) {
2844         WARN("only %u of %u materials defined\n", num_materials, mesh->num_materials);
2845         return E_FAIL;
2846     }
2847
2848     return D3D_OK;
2849 truncated_data_error:
2850     WARN("truncated data (%u bytes)\n", data_size);
2851     return E_FAIL;
2852 }
2853
2854 static HRESULT parse_texture_coords(IDirectXFileData *filedata, struct mesh_data *mesh)
2855 {
2856     HRESULT hr;
2857     DWORD data_size;
2858     BYTE *data;
2859
2860     HeapFree(GetProcessHeap(), 0, mesh->tex_coords);
2861     mesh->tex_coords = NULL;
2862
2863     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2864     if (FAILED(hr)) return hr;
2865
2866     /* template Coords2d {
2867      *     FLOAT u;
2868      *     FLOAT v;
2869      * }
2870      * template MeshTextureCoords {
2871      *     DWORD nTextureCoords;
2872      *     array Coords2d textureCoords[nTextureCoords];
2873      * }
2874      */
2875
2876     if (data_size < sizeof(DWORD))
2877         goto truncated_data_error;
2878     if (*(DWORD*)data != mesh->num_vertices) {
2879         WARN("number of texture coordinates (%u) doesn't match number of vertices (%u)\n",
2880              *(DWORD*)data, mesh->num_vertices);
2881         return E_FAIL;
2882     }
2883     data += sizeof(DWORD);
2884     if (data_size < sizeof(DWORD) + mesh->num_vertices * sizeof(*mesh->tex_coords))
2885         goto truncated_data_error;
2886
2887     mesh->tex_coords = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(*mesh->tex_coords));
2888     if (!mesh->tex_coords) return E_OUTOFMEMORY;
2889     memcpy(mesh->tex_coords, data, mesh->num_vertices * sizeof(*mesh->tex_coords));
2890
2891     mesh->fvf |= D3DFVF_TEX1;
2892
2893     return D3D_OK;
2894 truncated_data_error:
2895     WARN("truncated data (%u bytes)\n", data_size);
2896     return E_FAIL;
2897 }
2898
2899 static HRESULT parse_vertex_colors(IDirectXFileData *filedata, struct mesh_data *mesh)
2900 {
2901     HRESULT hr;
2902     DWORD data_size;
2903     BYTE *data;
2904     DWORD num_colors;
2905     int i;
2906
2907     HeapFree(GetProcessHeap(), 0, mesh->vertex_colors);
2908     mesh->vertex_colors = NULL;
2909
2910     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2911     if (FAILED(hr)) return hr;
2912
2913     /* template IndexedColor {
2914      *     DWORD index;
2915      *     ColorRGBA indexColor;
2916      * }
2917      * template MeshVertexColors {
2918      *     DWORD nVertexColors;
2919      *     array IndexedColor vertexColors[nVertexColors];
2920      * }
2921      */
2922
2923     if (data_size < sizeof(DWORD))
2924         goto truncated_data_error;
2925     num_colors = *(DWORD*)data;
2926     data += sizeof(DWORD);
2927     if (data_size < sizeof(DWORD) + num_colors * (sizeof(DWORD) + sizeof(D3DCOLORVALUE)))
2928         goto truncated_data_error;
2929
2930     mesh->vertex_colors = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(DWORD));
2931     if (!mesh->vertex_colors)
2932         return E_OUTOFMEMORY;
2933
2934     for (i = 0; i < mesh->num_vertices; i++)
2935         mesh->vertex_colors[i] = D3DCOLOR_ARGB(0, 0xff, 0xff, 0xff);
2936     for (i = 0; i < num_colors; i++)
2937     {
2938         D3DCOLORVALUE color;
2939         DWORD index = *(DWORD*)data;
2940         data += sizeof(DWORD);
2941         if (index >= mesh->num_vertices) {
2942             WARN("vertex color %u references undefined vertex %u (only %u vertices)\n",
2943                  i, index, mesh->num_vertices);
2944             return E_FAIL;
2945         }
2946         memcpy(&color, data, sizeof(color));
2947         data += sizeof(color);
2948         color.r = min(1.0f, max(0.0f, color.r));
2949         color.g = min(1.0f, max(0.0f, color.g));
2950         color.b = min(1.0f, max(0.0f, color.b));
2951         color.a = min(1.0f, max(0.0f, color.a));
2952         mesh->vertex_colors[index] = D3DCOLOR_ARGB((BYTE)(color.a * 255.0f + 0.5f),
2953                                                    (BYTE)(color.r * 255.0f + 0.5f),
2954                                                    (BYTE)(color.g * 255.0f + 0.5f),
2955                                                    (BYTE)(color.b * 255.0f + 0.5f));
2956     }
2957
2958     mesh->fvf |= D3DFVF_DIFFUSE;
2959
2960     return D3D_OK;
2961 truncated_data_error:
2962     WARN("truncated data (%u bytes)\n", data_size);
2963     return E_FAIL;
2964 }
2965
2966 static HRESULT parse_normals(IDirectXFileData *filedata, struct mesh_data *mesh)
2967 {
2968     HRESULT hr;
2969     DWORD data_size;
2970     BYTE *data;
2971     DWORD *index_out_ptr;
2972     int i;
2973     DWORD num_face_indices = mesh->num_poly_faces * 2 + mesh->num_tri_faces;
2974
2975     HeapFree(GetProcessHeap(), 0, mesh->normals);
2976     mesh->num_normals = 0;
2977     mesh->normals = NULL;
2978     mesh->normal_indices = NULL;
2979     mesh->fvf |= D3DFVF_NORMAL;
2980
2981     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
2982     if (FAILED(hr)) return hr;
2983
2984     /* template Vector {
2985      *     FLOAT x;
2986      *     FLOAT y;
2987      *     FLOAT z;
2988      * }
2989      * template MeshFace {
2990      *     DWORD nFaceVertexIndices;
2991      *     array DWORD faceVertexIndices[nFaceVertexIndices];
2992      * }
2993      * template MeshNormals {
2994      *     DWORD nNormals;
2995      *     array Vector normals[nNormals];
2996      *     DWORD nFaceNormals;
2997      *     array MeshFace faceNormals[nFaceNormals];
2998      * }
2999      */
3000
3001     if (data_size < sizeof(DWORD) * 2)
3002         goto truncated_data_error;
3003     mesh->num_normals = *(DWORD*)data;
3004     data += sizeof(DWORD);
3005     if (data_size < sizeof(DWORD) * 2 + mesh->num_normals * sizeof(D3DXVECTOR3) +
3006                     num_face_indices * sizeof(DWORD))
3007         goto truncated_data_error;
3008
3009     mesh->normals = HeapAlloc(GetProcessHeap(), 0, mesh->num_normals * sizeof(D3DXVECTOR3));
3010     mesh->normal_indices = HeapAlloc(GetProcessHeap(), 0, num_face_indices * sizeof(DWORD));
3011     if (!mesh->normals || !mesh->normal_indices)
3012         return E_OUTOFMEMORY;
3013
3014     memcpy(mesh->normals, data, mesh->num_normals * sizeof(D3DXVECTOR3));
3015     data += mesh->num_normals * sizeof(D3DXVECTOR3);
3016     for (i = 0; i < mesh->num_normals; i++)
3017         D3DXVec3Normalize(&mesh->normals[i], &mesh->normals[i]);
3018
3019     if (*(DWORD*)data != mesh->num_poly_faces) {
3020         WARN("number of face normals (%u) doesn't match number of faces (%u)\n",
3021              *(DWORD*)data, mesh->num_poly_faces);
3022         return E_FAIL;
3023     }
3024     data += sizeof(DWORD);
3025     index_out_ptr = mesh->normal_indices;
3026     for (i = 0; i < mesh->num_poly_faces; i++)
3027     {
3028         DWORD j;
3029         DWORD count = *(DWORD*)data;
3030         if (count != mesh->num_tri_per_face[i] + 2) {
3031             WARN("face %u: number of normals (%u) doesn't match number of vertices (%u)\n",
3032                  i, count, mesh->num_tri_per_face[i] + 2);
3033             return E_FAIL;
3034         }
3035         data += sizeof(DWORD);
3036
3037         for (j = 0; j < count; j++) {
3038             DWORD normal_index = *(DWORD*)data;
3039             if (normal_index >= mesh->num_normals) {
3040                 WARN("face %u, normal index %u: reference to undefined normal %u (only %u normals)\n",
3041                      i, j, normal_index, mesh->num_normals);
3042                 return E_FAIL;
3043             }
3044             *index_out_ptr++ = normal_index;
3045             data += sizeof(DWORD);
3046         }
3047     }
3048
3049     return D3D_OK;
3050 truncated_data_error:
3051     WARN("truncated data (%u bytes)\n", data_size);
3052     return E_FAIL;
3053 }
3054
3055 /* for provide_flags parameters */
3056 #define PROVIDE_MATERIALS 0x1
3057 #define PROVIDE_SKININFO  0x2
3058 #define PROVIDE_ADJACENCY 0x4
3059
3060 static HRESULT parse_mesh(IDirectXFileData *filedata, struct mesh_data *mesh_data, DWORD provide_flags)
3061 {
3062     HRESULT hr;
3063     DWORD data_size;
3064     BYTE *data, *in_ptr;
3065     DWORD *index_out_ptr;
3066     const GUID *type;
3067     IDirectXFileData *child;
3068     int i;
3069
3070     /*
3071      * template Mesh {
3072      *     DWORD nVertices;
3073      *     array Vector vertices[nVertices];
3074      *     DWORD nFaces;
3075      *     array MeshFace faces[nFaces];
3076      *     [ ... ]
3077      * }
3078      */
3079
3080     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
3081     if (FAILED(hr)) return hr;
3082
3083     in_ptr = data;
3084     if (data_size < sizeof(DWORD) * 2)
3085         goto truncated_data_error;
3086     mesh_data->num_vertices = *(DWORD*)in_ptr;
3087     if (data_size < sizeof(DWORD) * 2 + mesh_data->num_vertices * sizeof(D3DXVECTOR3))
3088         goto truncated_data_error;
3089     in_ptr += sizeof(DWORD) + mesh_data->num_vertices * sizeof(D3DXVECTOR3);
3090
3091     mesh_data->num_poly_faces = *(DWORD*)in_ptr;
3092     in_ptr += sizeof(DWORD);
3093
3094     mesh_data->num_tri_faces = 0;
3095     for (i = 0; i < mesh_data->num_poly_faces; i++)
3096     {
3097         DWORD num_poly_vertices;
3098         DWORD j;
3099
3100         if (data_size - (in_ptr - data) < sizeof(DWORD))
3101             goto truncated_data_error;
3102         num_poly_vertices = *(DWORD*)in_ptr;
3103         in_ptr += sizeof(DWORD);
3104         if (data_size - (in_ptr - data) < num_poly_vertices * sizeof(DWORD))
3105             goto truncated_data_error;
3106         if (num_poly_vertices < 3) {
3107             WARN("face %u has only %u vertices\n", i, num_poly_vertices);
3108             return E_FAIL;
3109         }
3110         for (j = 0; j < num_poly_vertices; j++) {
3111             if (*(DWORD*)in_ptr >= mesh_data->num_vertices) {
3112                 WARN("face %u, index %u: undefined vertex %u (only %u vertices)\n",
3113                      i, j, *(DWORD*)in_ptr, mesh_data->num_vertices);
3114                 return E_FAIL;
3115             }
3116             in_ptr += sizeof(DWORD);
3117         }
3118         mesh_data->num_tri_faces += num_poly_vertices - 2;
3119     }
3120
3121     mesh_data->fvf = D3DFVF_XYZ;
3122
3123     mesh_data->vertices = HeapAlloc(GetProcessHeap(), 0,
3124             mesh_data->num_vertices * sizeof(*mesh_data->vertices));
3125     mesh_data->num_tri_per_face = HeapAlloc(GetProcessHeap(), 0,
3126             mesh_data->num_poly_faces * sizeof(*mesh_data->num_tri_per_face));
3127     mesh_data->indices = HeapAlloc(GetProcessHeap(), 0,
3128             (mesh_data->num_tri_faces + mesh_data->num_poly_faces * 2) * sizeof(*mesh_data->indices));
3129     if (!mesh_data->vertices || !mesh_data->num_tri_per_face || !mesh_data->indices)
3130         return E_OUTOFMEMORY;
3131
3132     in_ptr = data + sizeof(DWORD);
3133     memcpy(mesh_data->vertices, in_ptr, mesh_data->num_vertices * sizeof(D3DXVECTOR3));
3134     in_ptr += mesh_data->num_vertices * sizeof(D3DXVECTOR3) + sizeof(DWORD);
3135
3136     index_out_ptr = mesh_data->indices;
3137     for (i = 0; i < mesh_data->num_poly_faces; i++)
3138     {
3139         DWORD count;
3140
3141         count = *(DWORD*)in_ptr;
3142         in_ptr += sizeof(DWORD);
3143         mesh_data->num_tri_per_face[i] = count - 2;
3144
3145         while (count--) {
3146             *index_out_ptr++ = *(DWORD*)in_ptr;
3147             in_ptr += sizeof(DWORD);
3148         }
3149     }
3150
3151     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3152     {
3153         if (IsEqualGUID(type, &TID_D3DRMMeshNormals)) {
3154             hr = parse_normals(child, mesh_data);
3155         } else if (IsEqualGUID(type, &TID_D3DRMMeshVertexColors)) {
3156             hr = parse_vertex_colors(child, mesh_data);
3157         } else if (IsEqualGUID(type, &TID_D3DRMMeshTextureCoords)) {
3158             hr = parse_texture_coords(child, mesh_data);
3159         } else if (IsEqualGUID(type, &TID_D3DRMMeshMaterialList) &&
3160                    (provide_flags & PROVIDE_MATERIALS))
3161         {
3162             hr = parse_material_list(child, mesh_data);
3163         } else if (provide_flags & PROVIDE_SKININFO) {
3164             if (IsEqualGUID(type, &DXFILEOBJ_XSkinMeshHeader)) {
3165                 FIXME("Skin mesh loading not implemented.\n");
3166                 hr = E_NOTIMPL;
3167             } else if (IsEqualGUID(type, &DXFILEOBJ_SkinWeights)) {
3168                 /* ignored without XSkinMeshHeader */
3169             }
3170         }
3171         if (FAILED(hr))
3172             break;
3173     }
3174     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
3175 truncated_data_error:
3176     WARN("truncated data (%u bytes)\n", data_size);
3177     return E_FAIL;
3178 }
3179
3180 static HRESULT generate_effects(ID3DXBuffer *materials, DWORD num_materials,
3181                                 ID3DXBuffer **effects)
3182 {
3183     HRESULT hr;
3184     D3DXEFFECTINSTANCE *effect_ptr;
3185     BYTE *out_ptr;
3186     const D3DXMATERIAL *material_ptr = ID3DXBuffer_GetBufferPointer(materials);
3187     static const struct {
3188         const char *param_name;
3189         DWORD name_size;
3190         DWORD num_bytes;
3191         DWORD value_offset;
3192     } material_effects[] = {
3193 #define EFFECT_TABLE_ENTRY(str, field) \
3194     {str, sizeof(str), sizeof(material_ptr->MatD3D.field), offsetof(D3DXMATERIAL, MatD3D.field)}
3195         EFFECT_TABLE_ENTRY("Diffuse", Diffuse),
3196         EFFECT_TABLE_ENTRY("Power", Power),
3197         EFFECT_TABLE_ENTRY("Specular", Specular),
3198         EFFECT_TABLE_ENTRY("Emissive", Emissive),
3199         EFFECT_TABLE_ENTRY("Ambient", Ambient),
3200 #undef EFFECT_TABLE_ENTRY
3201     };
3202     static const char texture_paramname[] = "Texture0@Name";
3203     DWORD buffer_size;
3204     int i;
3205
3206     /* effects buffer layout:
3207      *
3208      * D3DXEFFECTINSTANCE effects[num_materials];
3209      * for (effect in effects)
3210      * {
3211      *     D3DXEFFECTDEFAULT defaults[effect.NumDefaults];
3212      *     for (default in defaults)
3213      *     {
3214      *         *default.pParamName;
3215      *         *default.pValue;
3216      *     }
3217      * }
3218      */
3219     buffer_size = sizeof(D3DXEFFECTINSTANCE);
3220     buffer_size += sizeof(D3DXEFFECTDEFAULT) * ARRAY_SIZE(material_effects);
3221     for (i = 0; i < ARRAY_SIZE(material_effects); i++) {
3222         buffer_size += material_effects[i].name_size;
3223         buffer_size += material_effects[i].num_bytes;
3224     }
3225     buffer_size *= num_materials;
3226     for (i = 0; i < num_materials; i++) {
3227         if (material_ptr[i].pTextureFilename) {
3228             buffer_size += sizeof(D3DXEFFECTDEFAULT);
3229             buffer_size += sizeof(texture_paramname);
3230             buffer_size += strlen(material_ptr[i].pTextureFilename) + 1;
3231         }
3232     }
3233
3234     hr = D3DXCreateBuffer(buffer_size, effects);
3235     if (FAILED(hr)) return hr;
3236     effect_ptr = ID3DXBuffer_GetBufferPointer(*effects);
3237     out_ptr = (BYTE*)(effect_ptr + num_materials);
3238
3239     for (i = 0; i < num_materials; i++)
3240     {
3241         int j;
3242         D3DXEFFECTDEFAULT *defaults = (D3DXEFFECTDEFAULT*)out_ptr;
3243
3244         effect_ptr->pDefaults = defaults;
3245         effect_ptr->NumDefaults = material_ptr->pTextureFilename ? 6 : 5;
3246         out_ptr = (BYTE*)(effect_ptr->pDefaults + effect_ptr->NumDefaults);
3247
3248         for (j = 0; j < ARRAY_SIZE(material_effects); j++)
3249         {
3250             defaults->pParamName = (LPSTR)out_ptr;
3251             strcpy(defaults->pParamName, material_effects[j].param_name);
3252             defaults->pValue = defaults->pParamName + material_effects[j].name_size;
3253             defaults->Type = D3DXEDT_FLOATS;
3254             defaults->NumBytes = material_effects[j].num_bytes;
3255             memcpy(defaults->pValue, (BYTE*)material_ptr + material_effects[j].value_offset, defaults->NumBytes);
3256             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
3257             defaults++;
3258         }
3259
3260         if (material_ptr->pTextureFilename) {
3261             defaults->pParamName = (LPSTR)out_ptr;
3262             strcpy(defaults->pParamName, texture_paramname);
3263             defaults->pValue = defaults->pParamName + sizeof(texture_paramname);
3264             defaults->Type = D3DXEDT_STRING;
3265             defaults->NumBytes = strlen(material_ptr->pTextureFilename) + 1;
3266             strcpy(defaults->pValue, material_ptr->pTextureFilename);
3267             out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
3268         }
3269         material_ptr++;
3270         effect_ptr++;
3271     }
3272     assert(out_ptr - (BYTE*)ID3DXBuffer_GetBufferPointer(*effects) == buffer_size);
3273
3274     return D3D_OK;
3275 }
3276
3277 /* change to D3DXLoadSkinMeshFromXof when ID3DXFileData is implemented */
3278 static HRESULT load_skin_mesh_from_xof(IDirectXFileData *filedata,
3279                                        DWORD options,
3280                                        LPDIRECT3DDEVICE9 device,
3281                                        LPD3DXBUFFER *adjacency_out,
3282                                        LPD3DXBUFFER *materials_out,
3283                                        LPD3DXBUFFER *effects_out,
3284                                        DWORD *num_materials_out,
3285                                        LPD3DXSKININFO *skin_info_out,
3286                                        LPD3DXMESH *mesh_out)
3287 {
3288     HRESULT hr;
3289     DWORD *index_in_ptr;
3290     struct mesh_data mesh_data;
3291     DWORD total_vertices;
3292     ID3DXMesh *d3dxmesh = NULL;
3293     ID3DXBuffer *adjacency = NULL;
3294     ID3DXBuffer *materials = NULL;
3295     ID3DXBuffer *effects = NULL;
3296     struct vertex_duplication {
3297         DWORD normal_index;
3298         struct list entry;
3299     } *duplications = NULL;
3300     int i;
3301     void *vertices = NULL;
3302     void *indices = NULL;
3303     BYTE *out_ptr;
3304     DWORD provide_flags = 0;
3305
3306     ZeroMemory(&mesh_data, sizeof(mesh_data));
3307
3308     if (num_materials_out || materials_out || effects_out)
3309         provide_flags |= PROVIDE_MATERIALS;
3310     if (skin_info_out)
3311         provide_flags |= PROVIDE_SKININFO;
3312
3313     hr = parse_mesh(filedata, &mesh_data, provide_flags);
3314     if (FAILED(hr)) goto cleanup;
3315
3316     total_vertices = mesh_data.num_vertices;
3317     if (mesh_data.fvf & D3DFVF_NORMAL) {
3318         /* duplicate vertices with multiple normals */
3319         DWORD num_face_indices = mesh_data.num_poly_faces * 2 + mesh_data.num_tri_faces;
3320         duplications = HeapAlloc(GetProcessHeap(), 0, (mesh_data.num_vertices + num_face_indices) * sizeof(*duplications));
3321         if (!duplications) {
3322             hr = E_OUTOFMEMORY;
3323             goto cleanup;
3324         }
3325         for (i = 0; i < total_vertices; i++)
3326         {
3327             duplications[i].normal_index = -1;
3328             list_init(&duplications[i].entry);
3329         }
3330         for (i = 0; i < num_face_indices; i++) {
3331             DWORD vertex_index = mesh_data.indices[i];
3332             DWORD normal_index = mesh_data.normal_indices[i];
3333             struct vertex_duplication *dup_ptr = &duplications[vertex_index];
3334
3335             if (dup_ptr->normal_index == -1) {
3336                 dup_ptr->normal_index = normal_index;
3337             } else {
3338                 D3DXVECTOR3 *new_normal = &mesh_data.normals[normal_index];
3339                 struct list *dup_list = &dup_ptr->entry;
3340                 while (TRUE) {
3341                     D3DXVECTOR3 *cur_normal = &mesh_data.normals[dup_ptr->normal_index];
3342                     if (new_normal->x == cur_normal->x &&
3343                         new_normal->y == cur_normal->y &&
3344                         new_normal->z == cur_normal->z)
3345                     {
3346                         mesh_data.indices[i] = dup_ptr - duplications;
3347                         break;
3348                     } else if (!list_next(dup_list, &dup_ptr->entry)) {
3349                         dup_ptr = &duplications[total_vertices++];
3350                         dup_ptr->normal_index = normal_index;
3351                         list_add_tail(dup_list, &dup_ptr->entry);
3352                         mesh_data.indices[i] = dup_ptr - duplications;
3353                         break;
3354                     } else {
3355                         dup_ptr = LIST_ENTRY(list_next(dup_list, &dup_ptr->entry),
3356                                              struct vertex_duplication, entry);
3357                     }
3358                 }
3359             }
3360         }
3361     }
3362
3363     hr = D3DXCreateMeshFVF(mesh_data.num_tri_faces, total_vertices, options, mesh_data.fvf, device, &d3dxmesh);
3364     if (FAILED(hr)) goto cleanup;
3365
3366     hr = d3dxmesh->lpVtbl->LockVertexBuffer(d3dxmesh, 0, &vertices);
3367     if (FAILED(hr)) goto cleanup;
3368
3369     out_ptr = vertices;
3370     for (i = 0; i < mesh_data.num_vertices; i++) {
3371         *(D3DXVECTOR3*)out_ptr = mesh_data.vertices[i];
3372         out_ptr += sizeof(D3DXVECTOR3);
3373         if (mesh_data.fvf & D3DFVF_NORMAL) {
3374             if (duplications[i].normal_index == -1)
3375                 ZeroMemory(out_ptr, sizeof(D3DXVECTOR3));
3376             else
3377                 *(D3DXVECTOR3*)out_ptr = mesh_data.normals[duplications[i].normal_index];
3378             out_ptr += sizeof(D3DXVECTOR3);
3379         }
3380         if (mesh_data.fvf & D3DFVF_DIFFUSE) {
3381             *(DWORD*)out_ptr = mesh_data.vertex_colors[i];
3382             out_ptr += sizeof(DWORD);
3383         }
3384         if (mesh_data.fvf & D3DFVF_TEX1) {
3385             *(D3DXVECTOR2*)out_ptr = mesh_data.tex_coords[i];
3386             out_ptr += sizeof(D3DXVECTOR2);
3387         }
3388     }
3389     if (mesh_data.fvf & D3DFVF_NORMAL) {
3390         DWORD vertex_size = D3DXGetFVFVertexSize(mesh_data.fvf);
3391         out_ptr = vertices;
3392         for (i = 0; i < mesh_data.num_vertices; i++) {
3393             struct vertex_duplication *dup_ptr;
3394             LIST_FOR_EACH_ENTRY(dup_ptr, &duplications[i].entry, struct vertex_duplication, entry)
3395             {
3396                 int j = dup_ptr - duplications;
3397                 BYTE *dest_vertex = (BYTE*)vertices + j * vertex_size;
3398
3399                 memcpy(dest_vertex, out_ptr, vertex_size);
3400                 dest_vertex += sizeof(D3DXVECTOR3);
3401                 *(D3DXVECTOR3*)dest_vertex = mesh_data.normals[dup_ptr->normal_index];
3402             }
3403             out_ptr += vertex_size;
3404         }
3405     }
3406     d3dxmesh->lpVtbl->UnlockVertexBuffer(d3dxmesh);
3407
3408     hr = d3dxmesh->lpVtbl->LockIndexBuffer(d3dxmesh, 0, &indices);
3409     if (FAILED(hr)) goto cleanup;
3410
3411     index_in_ptr = mesh_data.indices;
3412 #define FILL_INDEX_BUFFER(indices_var) \
3413         for (i = 0; i < mesh_data.num_poly_faces; i++) \
3414         { \
3415             DWORD count = mesh_data.num_tri_per_face[i]; \
3416             WORD first_index = *index_in_ptr++; \
3417             while (count--) { \
3418                 *indices_var++ = first_index; \
3419                 *indices_var++ = *index_in_ptr; \
3420                 index_in_ptr++; \
3421                 *indices_var++ = *index_in_ptr; \
3422             } \
3423             index_in_ptr++; \
3424         }
3425     if (options & D3DXMESH_32BIT) {
3426         DWORD *dword_indices = indices;
3427         FILL_INDEX_BUFFER(dword_indices)
3428     } else {
3429         WORD *word_indices = indices;
3430         FILL_INDEX_BUFFER(word_indices)
3431     }
3432 #undef FILL_INDEX_BUFFER
3433     d3dxmesh->lpVtbl->UnlockIndexBuffer(d3dxmesh);
3434
3435     if (mesh_data.material_indices) {
3436         DWORD *attrib_buffer = NULL;
3437         hr = d3dxmesh->lpVtbl->LockAttributeBuffer(d3dxmesh, 0, &attrib_buffer);
3438         if (FAILED(hr)) goto cleanup;
3439         for (i = 0; i < mesh_data.num_poly_faces; i++)
3440         {
3441             DWORD count = mesh_data.num_tri_per_face[i];
3442             while (count--)
3443                 *attrib_buffer++ = mesh_data.material_indices[i];
3444         }
3445         d3dxmesh->lpVtbl->UnlockAttributeBuffer(d3dxmesh);
3446
3447         hr = d3dxmesh->lpVtbl->OptimizeInplace(d3dxmesh,
3448                 D3DXMESHOPT_ATTRSORT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_DONOTSPLIT,
3449                 NULL, NULL, NULL, NULL);
3450         if (FAILED(hr)) goto cleanup;
3451     }
3452
3453     if (mesh_data.num_materials && (materials_out || effects_out)) {
3454         DWORD buffer_size = mesh_data.num_materials * sizeof(D3DXMATERIAL);
3455         char *strings_out_ptr;
3456         D3DXMATERIAL *materials_ptr;
3457
3458         for (i = 0; i < mesh_data.num_materials; i++) {
3459             if (mesh_data.materials[i].pTextureFilename)
3460                 buffer_size += strlen(mesh_data.materials[i].pTextureFilename) + 1;
3461         }
3462
3463         hr = D3DXCreateBuffer(buffer_size, &materials);
3464         if (FAILED(hr)) goto cleanup;
3465
3466         materials_ptr = ID3DXBuffer_GetBufferPointer(materials);
3467         memcpy(materials_ptr, mesh_data.materials, mesh_data.num_materials * sizeof(D3DXMATERIAL));
3468         strings_out_ptr = (char*)(materials_ptr + mesh_data.num_materials);
3469         for (i = 0; i < mesh_data.num_materials; i++) {
3470             if (materials_ptr[i].pTextureFilename) {
3471                 strcpy(strings_out_ptr, mesh_data.materials[i].pTextureFilename);
3472                 materials_ptr[i].pTextureFilename = strings_out_ptr;
3473                 strings_out_ptr += strlen(mesh_data.materials[i].pTextureFilename) + 1;
3474             }
3475         }
3476     }
3477
3478     if (mesh_data.num_materials && effects_out) {
3479         hr = generate_effects(materials, mesh_data.num_materials, &effects);
3480         if (FAILED(hr)) goto cleanup;
3481
3482         if (!materials_out) {
3483             ID3DXBuffer_Release(materials);
3484             materials = NULL;
3485         }
3486     }
3487
3488     if (adjacency_out) {
3489         hr = D3DXCreateBuffer(mesh_data.num_tri_faces * 3 * sizeof(DWORD), &adjacency);
3490         if (FAILED(hr)) goto cleanup;
3491         hr = d3dxmesh->lpVtbl->GenerateAdjacency(d3dxmesh, 0.0f, ID3DXBuffer_GetBufferPointer(adjacency));
3492         if (FAILED(hr)) goto cleanup;
3493     }
3494
3495     *mesh_out = d3dxmesh;
3496     if (adjacency_out) *adjacency_out = adjacency;
3497     if (num_materials_out) *num_materials_out = mesh_data.num_materials;
3498     if (materials_out) *materials_out = materials;
3499     if (effects_out) *effects_out = effects;
3500     if (skin_info_out) *skin_info_out = NULL;
3501
3502     hr = D3D_OK;
3503 cleanup:
3504     if (FAILED(hr)) {
3505         if (d3dxmesh) IUnknown_Release(d3dxmesh);
3506         if (adjacency) ID3DXBuffer_Release(adjacency);
3507         if (materials) ID3DXBuffer_Release(materials);
3508         if (effects) ID3DXBuffer_Release(effects);
3509     }
3510     HeapFree(GetProcessHeap(), 0, mesh_data.vertices);
3511     HeapFree(GetProcessHeap(), 0, mesh_data.num_tri_per_face);
3512     HeapFree(GetProcessHeap(), 0, mesh_data.indices);
3513     HeapFree(GetProcessHeap(), 0, mesh_data.normals);
3514     HeapFree(GetProcessHeap(), 0, mesh_data.normal_indices);
3515     destroy_materials(&mesh_data);
3516     HeapFree(GetProcessHeap(), 0, mesh_data.tex_coords);
3517     HeapFree(GetProcessHeap(), 0, mesh_data.vertex_colors);
3518     HeapFree(GetProcessHeap(), 0, duplications);
3519     return hr;
3520 }
3521
3522 HRESULT WINAPI D3DXLoadMeshHierarchyFromXA(LPCSTR filename,
3523                                            DWORD options,
3524                                            LPDIRECT3DDEVICE9 device,
3525                                            LPD3DXALLOCATEHIERARCHY alloc_hier,
3526                                            LPD3DXLOADUSERDATA load_user_data,
3527                                            LPD3DXFRAME *frame_hierarchy,
3528                                            LPD3DXANIMATIONCONTROLLER *anim_controller)
3529 {
3530     HRESULT hr;
3531     int len;
3532     LPWSTR filenameW;
3533
3534     TRACE("(%s, %x, %p, %p, %p, %p, %p)\n", debugstr_a(filename), options,
3535           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3536
3537     if (!filename)
3538         return D3DERR_INVALIDCALL;
3539
3540     len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
3541     filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3542     if (!filenameW) return E_OUTOFMEMORY;
3543     MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
3544
3545     hr = D3DXLoadMeshHierarchyFromXW(filenameW, options, device,
3546             alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3547     HeapFree(GetProcessHeap(), 0, filenameW);
3548
3549     return hr;
3550 }
3551
3552 HRESULT WINAPI D3DXLoadMeshHierarchyFromXW(LPCWSTR filename,
3553                                            DWORD options,
3554                                            LPDIRECT3DDEVICE9 device,
3555                                            LPD3DXALLOCATEHIERARCHY alloc_hier,
3556                                            LPD3DXLOADUSERDATA load_user_data,
3557                                            LPD3DXFRAME *frame_hierarchy,
3558                                            LPD3DXANIMATIONCONTROLLER *anim_controller)
3559 {
3560     HRESULT hr;
3561     DWORD size;
3562     LPVOID buffer;
3563
3564     TRACE("(%s, %x, %p, %p, %p, %p, %p)\n", debugstr_w(filename), options,
3565           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3566
3567     if (!filename)
3568         return D3DERR_INVALIDCALL;
3569
3570     hr = map_view_of_file(filename, &buffer, &size);
3571     if (FAILED(hr))
3572         return D3DXERR_INVALIDDATA;
3573
3574     hr = D3DXLoadMeshHierarchyFromXInMemory(buffer, size, options, device,
3575             alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3576
3577     UnmapViewOfFile(buffer);
3578
3579     return hr;
3580 }
3581
3582 static HRESULT filedata_get_name(IDirectXFileData *filedata, char **name)
3583 {
3584     HRESULT hr;
3585     DWORD name_len;
3586
3587     hr = IDirectXFileData_GetName(filedata, NULL, &name_len);
3588     if (FAILED(hr)) return hr;
3589
3590     if (!name_len)
3591         name_len++;
3592     *name = HeapAlloc(GetProcessHeap(), 0, name_len);
3593     if (!*name) return E_OUTOFMEMORY;
3594
3595     hr = IDirectXFileObject_GetName(filedata, *name, &name_len);
3596     if (FAILED(hr))
3597         HeapFree(GetProcessHeap(), 0, name);
3598     if (!name_len)
3599         (*name)[0] = 0;
3600
3601     return hr;
3602 }
3603
3604 static HRESULT load_mesh_container(IDirectXFileData *filedata,
3605                                    DWORD options,
3606                                    LPDIRECT3DDEVICE9 device,
3607                                    LPD3DXALLOCATEHIERARCHY alloc_hier,
3608                                    D3DXMESHCONTAINER **mesh_container)
3609 {
3610     HRESULT hr;
3611     ID3DXBuffer *adjacency = NULL;
3612     ID3DXBuffer *materials = NULL;
3613     ID3DXBuffer *effects = NULL;
3614     ID3DXSkinInfo *skin_info = NULL;
3615     D3DXMESHDATA mesh_data;
3616     DWORD num_materials = 0;
3617     char *name = NULL;
3618
3619     mesh_data.Type = D3DXMESHTYPE_MESH;
3620     mesh_data.u.pMesh = NULL;
3621
3622     hr = load_skin_mesh_from_xof(filedata, options, device,
3623             &adjacency, &materials, &effects, &num_materials,
3624             &skin_info, &mesh_data.u.pMesh);
3625     if (FAILED(hr)) return hr;
3626
3627     hr = filedata_get_name(filedata, &name);
3628     if (FAILED(hr)) goto cleanup;
3629
3630     hr = alloc_hier->lpVtbl->CreateMeshContainer(alloc_hier, name, &mesh_data,
3631             materials ? ID3DXBuffer_GetBufferPointer(materials) : NULL,
3632             effects ? ID3DXBuffer_GetBufferPointer(effects) : NULL,
3633             num_materials,
3634             adjacency ? ID3DXBuffer_GetBufferPointer(adjacency) : NULL,
3635             skin_info, mesh_container);
3636
3637 cleanup:
3638     if (materials) ID3DXBuffer_Release(materials);
3639     if (effects) ID3DXBuffer_Release(effects);
3640     if (adjacency) ID3DXBuffer_Release(adjacency);
3641     if (skin_info) IUnknown_Release(skin_info);
3642     if (mesh_data.u.pMesh) IUnknown_Release(mesh_data.u.pMesh);
3643     HeapFree(GetProcessHeap(), 0, name);
3644     return hr;
3645 }
3646
3647 static HRESULT parse_transform_matrix(IDirectXFileData *filedata, D3DXMATRIX *transform)
3648 {
3649     HRESULT hr;
3650     DWORD data_size;
3651     BYTE *data;
3652
3653     /* template Matrix4x4 {
3654      *     array FLOAT matrix[16];
3655      * }
3656      * template FrameTransformMatrix {
3657      *     Matrix4x4 frameMatrix;
3658      * }
3659      */
3660
3661     hr = IDirectXFileData_GetData(filedata, NULL, &data_size, (void**)&data);
3662     if (FAILED(hr)) return hr;
3663
3664     if (data_size != sizeof(D3DXMATRIX)) {
3665         WARN("incorrect data size (%u bytes)\n", data_size);
3666         return E_FAIL;
3667     }
3668
3669     memcpy(transform, data, sizeof(D3DXMATRIX));
3670
3671     return D3D_OK;
3672 }
3673
3674 static HRESULT load_frame(IDirectXFileData *filedata,
3675                           DWORD options,
3676                           LPDIRECT3DDEVICE9 device,
3677                           LPD3DXALLOCATEHIERARCHY alloc_hier,
3678                           D3DXFRAME **frame_out)
3679 {
3680     HRESULT hr;
3681     const GUID *type;
3682     IDirectXFileData *child;
3683     char *name = NULL;
3684     D3DXFRAME *frame = NULL;
3685     D3DXMESHCONTAINER **next_container;
3686     D3DXFRAME **next_child;
3687
3688     hr = filedata_get_name(filedata, &name);
3689     if (FAILED(hr)) return hr;
3690
3691     hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, name, frame_out);
3692     HeapFree(GetProcessHeap(), 0, name);
3693     if (FAILED(hr)) return E_FAIL;
3694
3695     frame = *frame_out;
3696     D3DXMatrixIdentity(&frame->TransformationMatrix);
3697     next_child = &frame->pFrameFirstChild;
3698     next_container = &frame->pMeshContainer;
3699
3700     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3701     {
3702         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
3703             hr = load_mesh_container(child, options, device, alloc_hier, next_container);
3704             if (SUCCEEDED(hr))
3705                 next_container = &(*next_container)->pNextMeshContainer;
3706         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
3707             hr = parse_transform_matrix(child, &frame->TransformationMatrix);
3708         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
3709             hr = load_frame(child, options, device, alloc_hier, next_child);
3710             if (SUCCEEDED(hr))
3711                 next_child = &(*next_child)->pFrameSibling;
3712         }
3713         if (FAILED(hr)) break;
3714     }
3715     if (hr == DXFILEERR_NOMOREOBJECTS)
3716         hr = D3D_OK;
3717
3718     return hr;
3719 }
3720
3721 HRESULT WINAPI D3DXLoadMeshHierarchyFromXInMemory(LPCVOID memory,
3722                                                   DWORD memory_size,
3723                                                   DWORD options,
3724                                                   LPDIRECT3DDEVICE9 device,
3725                                                   LPD3DXALLOCATEHIERARCHY alloc_hier,
3726                                                   LPD3DXLOADUSERDATA load_user_data,
3727                                                   LPD3DXFRAME *frame_hierarchy,
3728                                                   LPD3DXANIMATIONCONTROLLER *anim_controller)
3729 {
3730     HRESULT hr;
3731     IDirectXFile *dxfile = NULL;
3732     IDirectXFileEnumObject *enumobj = NULL;
3733     IDirectXFileData *filedata = NULL;
3734     DXFILELOADMEMORY source;
3735     D3DXFRAME *first_frame = NULL;
3736     D3DXFRAME **next_frame = &first_frame;
3737
3738     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
3739           device, alloc_hier, load_user_data, frame_hierarchy, anim_controller);
3740
3741     if (!memory || !memory_size || !device || !frame_hierarchy || !alloc_hier)
3742         return D3DERR_INVALIDCALL;
3743     if (load_user_data || anim_controller) {
3744         if (load_user_data)
3745             FIXME("Loading user data not implemented\n");
3746         if (anim_controller)
3747             FIXME("Animation controller creation not implemented\n");
3748         return E_NOTIMPL;
3749     }
3750
3751     hr = DirectXFileCreate(&dxfile);
3752     if (FAILED(hr)) goto cleanup;
3753
3754     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
3755     if (FAILED(hr)) goto cleanup;
3756
3757     source.lpMemory = (void*)memory;
3758     source.dSize = memory_size;
3759     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
3760     if (FAILED(hr)) goto cleanup;
3761
3762     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
3763     {
3764         const GUID *guid = NULL;
3765
3766         hr = IDirectXFileData_GetType(filedata, &guid);
3767         if (SUCCEEDED(hr)) {
3768             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
3769                 hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, next_frame);
3770                 if (FAILED(hr)) {
3771                     hr = E_FAIL;
3772                     goto cleanup;
3773                 }
3774
3775                 D3DXMatrixIdentity(&(*next_frame)->TransformationMatrix);
3776
3777                 hr = load_mesh_container(filedata, options, device, alloc_hier, &(*next_frame)->pMeshContainer);
3778                 if (FAILED(hr)) goto cleanup;
3779             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
3780                 hr = load_frame(filedata, options, device, alloc_hier, next_frame);
3781                 if (FAILED(hr)) goto cleanup;
3782             }
3783             while (*next_frame)
3784                 next_frame = &(*next_frame)->pFrameSibling;
3785         }
3786
3787         IDirectXFileData_Release(filedata);
3788         filedata = NULL;
3789         if (FAILED(hr))
3790             goto cleanup;
3791     }
3792     if (hr != DXFILEERR_NOMOREOBJECTS)
3793         goto cleanup;
3794
3795     if (!first_frame) {
3796         hr = E_FAIL;
3797     } else if (first_frame->pFrameSibling) {
3798         D3DXFRAME *root_frame = NULL;
3799         hr = alloc_hier->lpVtbl->CreateFrame(alloc_hier, NULL, &root_frame);
3800         if (FAILED(hr)) {
3801             hr = E_FAIL;
3802             goto cleanup;
3803         }
3804         D3DXMatrixIdentity(&root_frame->TransformationMatrix);
3805         root_frame->pFrameFirstChild = first_frame;
3806         *frame_hierarchy = root_frame;
3807         hr = D3D_OK;
3808     } else {
3809         *frame_hierarchy = first_frame;
3810         hr = D3D_OK;
3811     }
3812
3813 cleanup:
3814     if (FAILED(hr) && first_frame) D3DXFrameDestroy(first_frame, alloc_hier);
3815     if (filedata) IDirectXFileData_Release(filedata);
3816     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
3817     if (dxfile) IDirectXFile_Release(dxfile);
3818     return hr;
3819 }
3820
3821 HRESULT WINAPI D3DXCleanMesh(D3DXCLEANTYPE clean_type, LPD3DXMESH mesh_in, const DWORD *adjacency_in,
3822                              LPD3DXMESH *mesh_out, DWORD *adjacency_out, LPD3DXBUFFER *errors_and_warnings)
3823 {
3824     FIXME("(%u, %p, %p, %p, %p, %p)\n", clean_type, mesh_in, adjacency_in, mesh_out, adjacency_out, errors_and_warnings);
3825
3826     return E_NOTIMPL;
3827 }
3828
3829 HRESULT WINAPI D3DXFrameDestroy(LPD3DXFRAME frame, LPD3DXALLOCATEHIERARCHY alloc_hier)
3830 {
3831     HRESULT hr;
3832     BOOL last = FALSE;
3833
3834     TRACE("(%p, %p)\n", frame, alloc_hier);
3835
3836     if (!frame || !alloc_hier)
3837         return D3DERR_INVALIDCALL;
3838
3839     while (!last) {
3840         D3DXMESHCONTAINER *container;
3841         D3DXFRAME *current_frame;
3842
3843         if (frame->pFrameSibling) {
3844             current_frame = frame->pFrameSibling;
3845             frame->pFrameSibling = current_frame->pFrameSibling;
3846             current_frame->pFrameSibling = NULL;
3847         } else {
3848             current_frame = frame;
3849             last = TRUE;
3850         }
3851
3852         if (current_frame->pFrameFirstChild) {
3853             hr = D3DXFrameDestroy(current_frame->pFrameFirstChild, alloc_hier);
3854             if (FAILED(hr)) return hr;
3855             current_frame->pFrameFirstChild = NULL;
3856         }
3857
3858         container = current_frame->pMeshContainer;
3859         while (container) {
3860             D3DXMESHCONTAINER *next_container = container->pNextMeshContainer;
3861             hr = alloc_hier->lpVtbl->DestroyMeshContainer(alloc_hier, container);
3862             if (FAILED(hr)) return hr;
3863             container = next_container;
3864         }
3865         hr = alloc_hier->lpVtbl->DestroyFrame(alloc_hier, current_frame);
3866         if (FAILED(hr)) return hr;
3867     }
3868     return D3D_OK;
3869 }
3870
3871 HRESULT WINAPI D3DXLoadMeshFromXA(LPCSTR filename,
3872                                   DWORD options,
3873                                   LPDIRECT3DDEVICE9 device,
3874                                   LPD3DXBUFFER *adjacency,
3875                                   LPD3DXBUFFER *materials,
3876                                   LPD3DXBUFFER *effect_instances,
3877                                   DWORD *num_materials,
3878                                   LPD3DXMESH *mesh)
3879 {
3880     HRESULT hr;
3881     int len;
3882     LPWSTR filenameW;
3883
3884     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_a(filename), options,
3885           device, adjacency, materials, effect_instances, num_materials, mesh);
3886
3887     if (!filename)
3888         return D3DERR_INVALIDCALL;
3889
3890     len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
3891     filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3892     if (!filenameW) return E_OUTOFMEMORY;
3893     MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
3894
3895     hr = D3DXLoadMeshFromXW(filenameW, options, device, adjacency, materials,
3896                             effect_instances, num_materials, mesh);
3897     HeapFree(GetProcessHeap(), 0, filenameW);
3898
3899     return hr;
3900 }
3901
3902 HRESULT WINAPI D3DXLoadMeshFromXW(LPCWSTR filename,
3903                                   DWORD options,
3904                                   LPDIRECT3DDEVICE9 device,
3905                                   LPD3DXBUFFER *adjacency,
3906                                   LPD3DXBUFFER *materials,
3907                                   LPD3DXBUFFER *effect_instances,
3908                                   DWORD *num_materials,
3909                                   LPD3DXMESH *mesh)
3910 {
3911     HRESULT hr;
3912     DWORD size;
3913     LPVOID buffer;
3914
3915     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_w(filename), options,
3916           device, adjacency, materials, effect_instances, num_materials, mesh);
3917
3918     if (!filename)
3919         return D3DERR_INVALIDCALL;
3920
3921     hr = map_view_of_file(filename, &buffer, &size);
3922     if (FAILED(hr))
3923         return D3DXERR_INVALIDDATA;
3924
3925     hr = D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3926             materials, effect_instances, num_materials, mesh);
3927
3928     UnmapViewOfFile(buffer);
3929
3930     return hr;
3931 }
3932
3933 HRESULT WINAPI D3DXLoadMeshFromXResource(HMODULE module,
3934                                          LPCSTR name,
3935                                          LPCSTR type,
3936                                          DWORD options,
3937                                          LPDIRECT3DDEVICE9 device,
3938                                          LPD3DXBUFFER *adjacency,
3939                                          LPD3DXBUFFER *materials,
3940                                          LPD3DXBUFFER *effect_instances,
3941                                          DWORD *num_materials,
3942                                          LPD3DXMESH *mesh)
3943 {
3944     HRESULT hr;
3945     HRSRC resinfo;
3946     DWORD size;
3947     LPVOID buffer;
3948
3949     TRACE("(%p, %s, %s, %x, %p, %p, %p, %p, %p, %p)\n",
3950           module, debugstr_a(name), debugstr_a(type), options, device,
3951           adjacency, materials, effect_instances, num_materials, mesh);
3952
3953     resinfo = FindResourceA(module, name, type);
3954     if (!resinfo) return D3DXERR_INVALIDDATA;
3955
3956     hr = load_resource_into_memory(module, resinfo, &buffer, &size);
3957     if (FAILED(hr)) return D3DXERR_INVALIDDATA;
3958
3959     return D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3960             materials, effect_instances, num_materials, mesh);
3961 }
3962
3963 struct mesh_container
3964 {
3965     struct list entry;
3966     ID3DXMesh *mesh;
3967     ID3DXBuffer *adjacency;
3968     ID3DXBuffer *materials;
3969     ID3DXBuffer *effects;
3970     DWORD num_materials;
3971     D3DXMATRIX transform;
3972 };
3973
3974 static HRESULT parse_frame(IDirectXFileData *filedata,
3975                            DWORD options,
3976                            LPDIRECT3DDEVICE9 device,
3977                            const D3DXMATRIX *parent_transform,
3978                            struct list *container_list,
3979                            DWORD provide_flags)
3980 {
3981     HRESULT hr;
3982     D3DXMATRIX transform = *parent_transform;
3983     IDirectXFileData *child;
3984     const GUID *type;
3985
3986     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3987     {
3988         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
3989             struct mesh_container *container = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container));
3990             if (!container)  {
3991                 hr = E_OUTOFMEMORY;
3992                 break;
3993             }
3994             list_add_tail(container_list, &container->entry);
3995             container->transform = transform;
3996
3997             hr = load_skin_mesh_from_xof(child, options, device,
3998                     (provide_flags & PROVIDE_ADJACENCY) ? &container->adjacency : NULL,
3999                     (provide_flags & PROVIDE_MATERIALS) ? &container->materials : NULL,
4000                     NULL, &container->num_materials, NULL, &container->mesh);
4001         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
4002             D3DXMATRIX new_transform;
4003             hr = parse_transform_matrix(child, &new_transform);
4004             D3DXMatrixMultiply(&transform, &transform, &new_transform);
4005         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
4006             hr = parse_frame(child, options, device, &transform, container_list, provide_flags);
4007         }
4008         if (FAILED(hr)) break;
4009     }
4010     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
4011 }
4012
4013 HRESULT WINAPI D3DXLoadMeshFromXInMemory(LPCVOID memory,
4014                                          DWORD memory_size,
4015                                          DWORD options,
4016                                          LPDIRECT3DDEVICE9 device,
4017                                          LPD3DXBUFFER *adjacency_out,
4018                                          LPD3DXBUFFER *materials_out,
4019                                          LPD3DXBUFFER *effects_out,
4020                                          DWORD *num_materials_out,
4021                                          LPD3DXMESH *mesh_out)
4022 {
4023     HRESULT hr;
4024     IDirectXFile *dxfile = NULL;
4025     IDirectXFileEnumObject *enumobj = NULL;
4026     IDirectXFileData *filedata = NULL;
4027     DXFILELOADMEMORY source;
4028     ID3DXBuffer *materials = NULL;
4029     ID3DXBuffer *effects = NULL;
4030     ID3DXBuffer *adjacency = NULL;
4031     struct list container_list = LIST_INIT(container_list);
4032     struct mesh_container *container_ptr, *next_container_ptr;
4033     DWORD num_materials;
4034     DWORD num_faces, num_vertices;
4035     D3DXMATRIX identity;
4036     int i;
4037     DWORD provide_flags = 0;
4038     DWORD fvf;
4039     ID3DXMesh *concat_mesh = NULL;
4040     D3DVERTEXELEMENT9 concat_decl[MAX_FVF_DECL_SIZE];
4041     BYTE *concat_vertices = NULL;
4042     void *concat_indices = NULL;
4043     DWORD index_offset;
4044     DWORD concat_vertex_size;
4045
4046     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
4047           device, adjacency_out, materials_out, effects_out, num_materials_out, mesh_out);
4048
4049     if (!memory || !memory_size || !device || !mesh_out)
4050         return D3DERR_INVALIDCALL;
4051
4052     hr = DirectXFileCreate(&dxfile);
4053     if (FAILED(hr)) goto cleanup;
4054
4055     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
4056     if (FAILED(hr)) goto cleanup;
4057
4058     source.lpMemory = (void*)memory;
4059     source.dSize = memory_size;
4060     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
4061     if (FAILED(hr)) goto cleanup;
4062
4063     D3DXMatrixIdentity(&identity);
4064     if (adjacency_out) provide_flags |= PROVIDE_ADJACENCY;
4065     if (materials_out || effects_out) provide_flags |= PROVIDE_MATERIALS;
4066
4067     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
4068     {
4069         const GUID *guid = NULL;
4070
4071         hr = IDirectXFileData_GetType(filedata, &guid);
4072         if (SUCCEEDED(hr)) {
4073             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
4074                 container_ptr = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container_ptr));
4075                 if (!container_ptr) {
4076                     hr = E_OUTOFMEMORY;
4077                     goto cleanup;
4078                 }
4079                 list_add_tail(&container_list, &container_ptr->entry);
4080                 D3DXMatrixIdentity(&container_ptr->transform);
4081
4082                 hr = load_skin_mesh_from_xof(filedata, options, device,
4083                         (provide_flags & PROVIDE_ADJACENCY) ? &container_ptr->adjacency : NULL,
4084                         (provide_flags & PROVIDE_MATERIALS) ? &container_ptr->materials : NULL,
4085                         NULL, &container_ptr->num_materials, NULL, &container_ptr->mesh);
4086             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
4087                 hr = parse_frame(filedata, options, device, &identity, &container_list, provide_flags);
4088             }
4089             if (FAILED(hr)) goto cleanup;
4090         }
4091         IDirectXFileData_Release(filedata);
4092         filedata = NULL;
4093         if (FAILED(hr))
4094             goto cleanup;
4095     }
4096     if (hr != DXFILEERR_NOMOREOBJECTS)
4097         goto cleanup;
4098
4099     IDirectXFileEnumObject_Release(enumobj);
4100     enumobj = NULL;
4101     IDirectXFile_Release(dxfile);
4102     dxfile = NULL;
4103
4104     if (list_empty(&container_list)) {
4105         hr = E_FAIL;
4106         goto cleanup;
4107     }
4108
4109     fvf = D3DFVF_XYZ;
4110     num_faces = 0;
4111     num_vertices = 0;
4112     num_materials = 0;
4113     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4114     {
4115         ID3DXMesh *mesh = container_ptr->mesh;
4116         fvf |= mesh->lpVtbl->GetFVF(mesh);
4117         num_faces += mesh->lpVtbl->GetNumFaces(mesh);
4118         num_vertices += mesh->lpVtbl->GetNumVertices(mesh);
4119         num_materials += container_ptr->num_materials;
4120     }
4121
4122     hr = D3DXCreateMeshFVF(num_faces, num_vertices, options, fvf, device, &concat_mesh);
4123     if (FAILED(hr)) goto cleanup;
4124
4125     hr = concat_mesh->lpVtbl->GetDeclaration(concat_mesh, concat_decl);
4126     if (FAILED(hr)) goto cleanup;
4127
4128     concat_vertex_size = D3DXGetDeclVertexSize(concat_decl, 0);
4129
4130     hr = concat_mesh->lpVtbl->LockVertexBuffer(concat_mesh, 0, (void**)&concat_vertices);
4131     if (FAILED(hr)) goto cleanup;
4132
4133     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4134     {
4135         D3DVERTEXELEMENT9 mesh_decl[MAX_FVF_DECL_SIZE];
4136         ID3DXMesh *mesh = container_ptr->mesh;
4137         DWORD num_mesh_vertices = mesh->lpVtbl->GetNumVertices(mesh);
4138         DWORD mesh_vertex_size;
4139         const BYTE *mesh_vertices;
4140
4141         hr = mesh->lpVtbl->GetDeclaration(mesh, mesh_decl);
4142         if (FAILED(hr)) goto cleanup;
4143
4144         mesh_vertex_size = D3DXGetDeclVertexSize(mesh_decl, 0);
4145
4146         hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_vertices);
4147         if (FAILED(hr)) goto cleanup;
4148
4149         for (i = 0; i < num_mesh_vertices; i++) {
4150             int j;
4151             int k = 1;
4152
4153             D3DXVec3TransformCoord((D3DXVECTOR3*)concat_vertices,
4154                                    (D3DXVECTOR3*)mesh_vertices,
4155                                    &container_ptr->transform);
4156             for (j = 1; concat_decl[j].Stream != 0xff; j++)
4157             {
4158                 if (concat_decl[j].Usage == mesh_decl[k].Usage &&
4159                     concat_decl[j].UsageIndex == mesh_decl[k].UsageIndex)
4160                 {
4161                     if (concat_decl[j].Usage == D3DDECLUSAGE_NORMAL) {
4162                         D3DXVec3TransformCoord((D3DXVECTOR3*)(concat_vertices + concat_decl[j].Offset),
4163                                                (D3DXVECTOR3*)(mesh_vertices + mesh_decl[k].Offset),
4164                                                &container_ptr->transform);
4165                     } else {
4166                         memcpy(concat_vertices + concat_decl[j].Offset,
4167                                mesh_vertices + mesh_decl[k].Offset,
4168                                d3dx_decltype_size[mesh_decl[k].Type]);
4169                     }
4170                     k++;
4171                 }
4172             }
4173             mesh_vertices += mesh_vertex_size;
4174             concat_vertices += concat_vertex_size;
4175         }
4176
4177         mesh->lpVtbl->UnlockVertexBuffer(mesh);
4178     }
4179
4180     concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
4181     concat_vertices = NULL;
4182
4183     hr = concat_mesh->lpVtbl->LockIndexBuffer(concat_mesh, 0, &concat_indices);
4184     if (FAILED(hr)) goto cleanup;
4185
4186     index_offset = 0;
4187     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4188     {
4189         ID3DXMesh *mesh = container_ptr->mesh;
4190         const void *mesh_indices;
4191         DWORD num_mesh_faces = mesh->lpVtbl->GetNumFaces(mesh);
4192         int i;
4193
4194         hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_indices);
4195         if (FAILED(hr)) goto cleanup;
4196
4197         if (options & D3DXMESH_32BIT) {
4198             DWORD *dest = concat_indices;
4199             const DWORD *src = mesh_indices;
4200             for (i = 0; i < num_mesh_faces * 3; i++)
4201                 *dest++ = index_offset + *src++;
4202             concat_indices = dest;
4203         } else {
4204             WORD *dest = concat_indices;
4205             const WORD *src = mesh_indices;
4206             for (i = 0; i < num_mesh_faces * 3; i++)
4207                 *dest++ = index_offset + *src++;
4208             concat_indices = dest;
4209         }
4210         mesh->lpVtbl->UnlockIndexBuffer(mesh);
4211
4212         index_offset += num_mesh_faces * 3;
4213     }
4214
4215     concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
4216     concat_indices = NULL;
4217
4218     if (num_materials) {
4219         DWORD *concat_attrib_buffer = NULL;
4220         DWORD offset = 0;
4221
4222         hr = concat_mesh->lpVtbl->LockAttributeBuffer(concat_mesh, 0, &concat_attrib_buffer);
4223         if (FAILED(hr)) goto cleanup;
4224
4225         LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4226         {
4227             ID3DXMesh *mesh = container_ptr->mesh;
4228             const DWORD *mesh_attrib_buffer = NULL;
4229             DWORD count = mesh->lpVtbl->GetNumFaces(mesh);
4230
4231             hr = mesh->lpVtbl->LockAttributeBuffer(mesh, D3DLOCK_READONLY, (DWORD**)&mesh_attrib_buffer);
4232             if (FAILED(hr)) {
4233                 concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
4234                 goto cleanup;
4235             }
4236
4237             while (count--)
4238                 *concat_attrib_buffer++ = offset + *mesh_attrib_buffer++;
4239
4240             mesh->lpVtbl->UnlockAttributeBuffer(mesh);
4241             offset += container_ptr->num_materials;
4242         }
4243         concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
4244     }
4245
4246     if (materials_out || effects_out) {
4247         D3DXMATERIAL *out_ptr;
4248         if (!num_materials) {
4249             /* create default material */
4250             hr = D3DXCreateBuffer(sizeof(D3DXMATERIAL), &materials);
4251             if (FAILED(hr)) goto cleanup;
4252
4253             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
4254             out_ptr->MatD3D.Diffuse.r = 0.5f;
4255             out_ptr->MatD3D.Diffuse.g = 0.5f;
4256             out_ptr->MatD3D.Diffuse.b = 0.5f;
4257             out_ptr->MatD3D.Specular.r = 0.5f;
4258             out_ptr->MatD3D.Specular.g = 0.5f;
4259             out_ptr->MatD3D.Specular.b = 0.5f;
4260             /* D3DXCreateBuffer initializes the rest to zero */
4261         } else {
4262             DWORD buffer_size = num_materials * sizeof(D3DXMATERIAL);
4263             char *strings_out_ptr;
4264
4265             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4266             {
4267                 if (container_ptr->materials) {
4268                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
4269                     for (i = 0; i < container_ptr->num_materials; i++)
4270                     {
4271                         if (in_ptr->pTextureFilename)
4272                             buffer_size += strlen(in_ptr->pTextureFilename) + 1;
4273                         in_ptr++;
4274                     }
4275                 }
4276             }
4277
4278             hr = D3DXCreateBuffer(buffer_size, &materials);
4279             if (FAILED(hr)) goto cleanup;
4280             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
4281             strings_out_ptr = (char*)(out_ptr + num_materials);
4282
4283             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4284             {
4285                 if (container_ptr->materials) {
4286                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
4287                     for (i = 0; i < container_ptr->num_materials; i++)
4288                     {
4289                         out_ptr->MatD3D = in_ptr->MatD3D;
4290                         if (in_ptr->pTextureFilename) {
4291                             out_ptr->pTextureFilename = strings_out_ptr;
4292                             strcpy(out_ptr->pTextureFilename, in_ptr->pTextureFilename);
4293                             strings_out_ptr += strlen(in_ptr->pTextureFilename) + 1;
4294                         }
4295                         in_ptr++;
4296                         out_ptr++;
4297                     }
4298                 }
4299             }
4300         }
4301     }
4302     if (!num_materials)
4303         num_materials = 1;
4304
4305     if (effects_out) {
4306         generate_effects(materials, num_materials, &effects);
4307         if (!materials_out) {
4308             ID3DXBuffer_Release(materials);
4309             materials = NULL;
4310         }
4311     }
4312
4313     if (adjacency_out) {
4314         if (!list_next(&container_list, list_head(&container_list))) {
4315             container_ptr = LIST_ENTRY(list_head(&container_list), struct mesh_container, entry);
4316             adjacency = container_ptr->adjacency;
4317             container_ptr->adjacency = NULL;
4318         } else {
4319             DWORD offset = 0;
4320             DWORD *out_ptr;
4321
4322             hr = D3DXCreateBuffer(num_faces * 3 * sizeof(DWORD), &adjacency);
4323             if (FAILED(hr)) goto cleanup;
4324
4325             out_ptr = ID3DXBuffer_GetBufferPointer(adjacency);
4326             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4327             {
4328                 DWORD *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->adjacency);
4329                 int count = 3 * container_ptr->mesh->lpVtbl->GetNumFaces(container_ptr->mesh);
4330
4331                 for (i = 0; i < count; i++)
4332                     *out_ptr++ = offset + *in_ptr++;
4333
4334                 offset += count;
4335             }
4336         }
4337     }
4338
4339     *mesh_out = concat_mesh;
4340     if (adjacency_out) *adjacency_out = adjacency;
4341     if (materials_out) *materials_out = materials;
4342     if (effects_out) *effects_out = effects;
4343     if (num_materials_out) *num_materials_out = num_materials;
4344
4345     hr = D3D_OK;
4346 cleanup:
4347     if (concat_indices) concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
4348     if (concat_vertices) concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
4349     if (filedata) IDirectXFileData_Release(filedata);
4350     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
4351     if (dxfile) IDirectXFile_Release(dxfile);
4352     if (FAILED(hr)) {
4353         if (concat_mesh) IUnknown_Release(concat_mesh);
4354         if (materials) ID3DXBuffer_Release(materials);
4355         if (effects) ID3DXBuffer_Release(effects);
4356         if (adjacency) ID3DXBuffer_Release(adjacency);
4357     }
4358     LIST_FOR_EACH_ENTRY_SAFE(container_ptr, next_container_ptr, &container_list, struct mesh_container, entry)
4359     {
4360         if (container_ptr->mesh) IUnknown_Release(container_ptr->mesh);
4361         if (container_ptr->adjacency) ID3DXBuffer_Release(container_ptr->adjacency);
4362         if (container_ptr->materials) ID3DXBuffer_Release(container_ptr->materials);
4363         if (container_ptr->effects) ID3DXBuffer_Release(container_ptr->effects);
4364         HeapFree(GetProcessHeap(), 0, container_ptr);
4365     }
4366     return hr;
4367 }
4368
4369 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
4370                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4371 {
4372     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
4373
4374     return E_NOTIMPL;
4375 }
4376
4377 struct vertex
4378 {
4379     D3DXVECTOR3 position;
4380     D3DXVECTOR3 normal;
4381 };
4382
4383 typedef WORD face[3];
4384
4385 struct sincos_table
4386 {
4387     float *sin;
4388     float *cos;
4389 };
4390
4391 static void free_sincos_table(struct sincos_table *sincos_table)
4392 {
4393     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
4394     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
4395 }
4396
4397 /* pre compute sine and cosine tables; caller must free */
4398 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
4399 {
4400     float angle;
4401     int i;
4402
4403     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
4404     if (!sincos_table->sin)
4405     {
4406         return FALSE;
4407     }
4408     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
4409     if (!sincos_table->cos)
4410     {
4411         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
4412         return FALSE;
4413     }
4414
4415     angle = angle_start;
4416     for (i = 0; i < n; i++)
4417     {
4418         sincos_table->sin[i] = sin(angle);
4419         sincos_table->cos[i] = cos(angle);
4420         angle += angle_step;
4421     }
4422
4423     return TRUE;
4424 }
4425
4426 static WORD vertex_index(UINT slices, int slice, int stack)
4427 {
4428     return stack*slices+slice+1;
4429 }
4430
4431 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
4432                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4433 {
4434     DWORD number_of_vertices, number_of_faces;
4435     HRESULT hr;
4436     ID3DXMesh *sphere;
4437     struct vertex *vertices;
4438     face *faces;
4439     float phi_step, phi_start;
4440     struct sincos_table phi;
4441     float theta_step, theta, sin_theta, cos_theta;
4442     DWORD vertex, face;
4443     int slice, stack;
4444
4445     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
4446
4447     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
4448     {
4449         return D3DERR_INVALIDCALL;
4450     }
4451
4452     if (adjacency)
4453     {
4454         FIXME("Case of adjacency != NULL not implemented.\n");
4455         return E_NOTIMPL;
4456     }
4457
4458     number_of_vertices = 2 + slices * (stacks-1);
4459     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
4460
4461     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4462                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
4463     if (FAILED(hr))
4464     {
4465         return hr;
4466     }
4467
4468     hr = sphere->lpVtbl->LockVertexBuffer(sphere, 0, (LPVOID *)&vertices);
4469     if (FAILED(hr))
4470     {
4471         sphere->lpVtbl->Release(sphere);
4472         return hr;
4473     }
4474
4475     hr = sphere->lpVtbl->LockIndexBuffer(sphere, 0, (LPVOID *)&faces);
4476     if (FAILED(hr))
4477     {
4478         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4479         sphere->lpVtbl->Release(sphere);
4480         return hr;
4481     }
4482
4483     /* phi = angle on xz plane wrt z axis */
4484     phi_step = -2 * M_PI / slices;
4485     phi_start = M_PI / 2;
4486
4487     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
4488     {
4489         sphere->lpVtbl->UnlockIndexBuffer(sphere);
4490         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4491         sphere->lpVtbl->Release(sphere);
4492         return E_OUTOFMEMORY;
4493     }
4494
4495     /* theta = angle on xy plane wrt x axis */
4496     theta_step = M_PI / stacks;
4497     theta = theta_step;
4498
4499     vertex = 0;
4500     face = 0;
4501
4502     vertices[vertex].normal.x = 0.0f;
4503     vertices[vertex].normal.y = 0.0f;
4504     vertices[vertex].normal.z = 1.0f;
4505     vertices[vertex].position.x = 0.0f;
4506     vertices[vertex].position.y = 0.0f;
4507     vertices[vertex].position.z = radius;
4508     vertex++;
4509
4510     for (stack = 0; stack < stacks - 1; stack++)
4511     {
4512         sin_theta = sin(theta);
4513         cos_theta = cos(theta);
4514
4515         for (slice = 0; slice < slices; slice++)
4516         {
4517             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
4518             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
4519             vertices[vertex].normal.z = cos_theta;
4520             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
4521             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
4522             vertices[vertex].position.z = radius * cos_theta;
4523             vertex++;
4524
4525             if (slice > 0)
4526             {
4527                 if (stack == 0)
4528                 {
4529                     /* top stack is triangle fan */
4530                     faces[face][0] = 0;
4531                     faces[face][1] = slice + 1;
4532                     faces[face][2] = slice;
4533                     face++;
4534                 }
4535                 else
4536                 {
4537                     /* stacks in between top and bottom are quad strips */
4538                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4539                     faces[face][1] = vertex_index(slices, slice, stack-1);
4540                     faces[face][2] = vertex_index(slices, slice-1, stack);
4541                     face++;
4542
4543                     faces[face][0] = vertex_index(slices, slice, stack-1);
4544                     faces[face][1] = vertex_index(slices, slice, stack);
4545                     faces[face][2] = vertex_index(slices, slice-1, stack);
4546                     face++;
4547                 }
4548             }
4549         }
4550
4551         theta += theta_step;
4552
4553         if (stack == 0)
4554         {
4555             faces[face][0] = 0;
4556             faces[face][1] = 1;
4557             faces[face][2] = slice;
4558             face++;
4559         }
4560         else
4561         {
4562             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4563             faces[face][1] = vertex_index(slices, 0, stack-1);
4564             faces[face][2] = vertex_index(slices, slice-1, stack);
4565             face++;
4566
4567             faces[face][0] = vertex_index(slices, 0, stack-1);
4568             faces[face][1] = vertex_index(slices, 0, stack);
4569             faces[face][2] = vertex_index(slices, slice-1, stack);
4570             face++;
4571         }
4572     }
4573
4574     vertices[vertex].position.x = 0.0f;
4575     vertices[vertex].position.y = 0.0f;
4576     vertices[vertex].position.z = -radius;
4577     vertices[vertex].normal.x = 0.0f;
4578     vertices[vertex].normal.y = 0.0f;
4579     vertices[vertex].normal.z = -1.0f;
4580
4581     /* bottom stack is triangle fan */
4582     for (slice = 1; slice < slices; slice++)
4583     {
4584         faces[face][0] = vertex_index(slices, slice-1, stack-1);
4585         faces[face][1] = vertex_index(slices, slice, stack-1);
4586         faces[face][2] = vertex;
4587         face++;
4588     }
4589
4590     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4591     faces[face][1] = vertex_index(slices, 0, stack-1);
4592     faces[face][2] = vertex;
4593
4594     free_sincos_table(&phi);
4595     sphere->lpVtbl->UnlockIndexBuffer(sphere);
4596     sphere->lpVtbl->UnlockVertexBuffer(sphere);
4597     *mesh = sphere;
4598
4599     return D3D_OK;
4600 }
4601
4602 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
4603                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4604 {
4605     DWORD number_of_vertices, number_of_faces;
4606     HRESULT hr;
4607     ID3DXMesh *cylinder;
4608     struct vertex *vertices;
4609     face *faces;
4610     float theta_step, theta_start;
4611     struct sincos_table theta;
4612     float delta_radius, radius, radius_step;
4613     float z, z_step, z_normal;
4614     DWORD vertex, face;
4615     int slice, stack;
4616
4617     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
4618
4619     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
4620     {
4621         return D3DERR_INVALIDCALL;
4622     }
4623
4624     if (adjacency)
4625     {
4626         FIXME("Case of adjacency != NULL not implemented.\n");
4627         return E_NOTIMPL;
4628     }
4629
4630     number_of_vertices = 2 + (slices * (3 + stacks));
4631     number_of_faces = 2 * slices + stacks * (2 * slices);
4632
4633     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4634                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
4635     if (FAILED(hr))
4636     {
4637         return hr;
4638     }
4639
4640     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, 0, (LPVOID *)&vertices);
4641     if (FAILED(hr))
4642     {
4643         cylinder->lpVtbl->Release(cylinder);
4644         return hr;
4645     }
4646
4647     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, 0, (LPVOID *)&faces);
4648     if (FAILED(hr))
4649     {
4650         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4651         cylinder->lpVtbl->Release(cylinder);
4652         return hr;
4653     }
4654
4655     /* theta = angle on xy plane wrt x axis */
4656     theta_step = -2 * M_PI / slices;
4657     theta_start = M_PI / 2;
4658
4659     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
4660     {
4661         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4662         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4663         cylinder->lpVtbl->Release(cylinder);
4664         return E_OUTOFMEMORY;
4665     }
4666
4667     vertex = 0;
4668     face = 0;
4669
4670     delta_radius = radius1 - radius2;
4671     radius = radius1;
4672     radius_step = delta_radius / stacks;
4673
4674     z = -length / 2;
4675     z_step = length / stacks;
4676     z_normal = delta_radius / length;
4677     if (isnan(z_normal))
4678     {
4679         z_normal = 0.0f;
4680     }
4681
4682     vertices[vertex].normal.x = 0.0f;
4683     vertices[vertex].normal.y = 0.0f;
4684     vertices[vertex].normal.z = -1.0f;
4685     vertices[vertex].position.x = 0.0f;
4686     vertices[vertex].position.y = 0.0f;
4687     vertices[vertex++].position.z = z;
4688
4689     for (slice = 0; slice < slices; slice++, vertex++)
4690     {
4691         vertices[vertex].normal.x = 0.0f;
4692         vertices[vertex].normal.y = 0.0f;
4693         vertices[vertex].normal.z = -1.0f;
4694         vertices[vertex].position.x = radius * theta.cos[slice];
4695         vertices[vertex].position.y = radius * theta.sin[slice];
4696         vertices[vertex].position.z = z;
4697
4698         if (slice > 0)
4699         {
4700             faces[face][0] = 0;
4701             faces[face][1] = slice;
4702             faces[face++][2] = slice + 1;
4703         }
4704     }
4705
4706     faces[face][0] = 0;
4707     faces[face][1] = slice;
4708     faces[face++][2] = 1;
4709
4710     for (stack = 1; stack <= stacks+1; stack++)
4711     {
4712         for (slice = 0; slice < slices; slice++, vertex++)
4713         {
4714             vertices[vertex].normal.x = theta.cos[slice];
4715             vertices[vertex].normal.y = theta.sin[slice];
4716             vertices[vertex].normal.z = z_normal;
4717             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
4718             vertices[vertex].position.x = radius * theta.cos[slice];
4719             vertices[vertex].position.y = radius * theta.sin[slice];
4720             vertices[vertex].position.z = z;
4721
4722             if (stack > 1 && slice > 0)
4723             {
4724                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
4725                 faces[face][1] = vertex_index(slices, slice-1, stack);
4726                 faces[face++][2] = vertex_index(slices, slice, stack-1);
4727
4728                 faces[face][0] = vertex_index(slices, slice, stack-1);
4729                 faces[face][1] = vertex_index(slices, slice-1, stack);
4730                 faces[face++][2] = vertex_index(slices, slice, stack);
4731             }
4732         }
4733
4734         if (stack > 1)
4735         {
4736             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4737             faces[face][1] = vertex_index(slices, slice-1, stack);
4738             faces[face++][2] = vertex_index(slices, 0, stack-1);
4739
4740             faces[face][0] = vertex_index(slices, 0, stack-1);
4741             faces[face][1] = vertex_index(slices, slice-1, stack);
4742             faces[face++][2] = vertex_index(slices, 0, stack);
4743         }
4744
4745         if (stack < stacks + 1)
4746         {
4747             z += z_step;
4748             radius -= radius_step;
4749         }
4750     }
4751
4752     for (slice = 0; slice < slices; slice++, vertex++)
4753     {
4754         vertices[vertex].normal.x = 0.0f;
4755         vertices[vertex].normal.y = 0.0f;
4756         vertices[vertex].normal.z = 1.0f;
4757         vertices[vertex].position.x = radius * theta.cos[slice];
4758         vertices[vertex].position.y = radius * theta.sin[slice];
4759         vertices[vertex].position.z = z;
4760
4761         if (slice > 0)
4762         {
4763             faces[face][0] = vertex_index(slices, slice-1, stack);
4764             faces[face][1] = number_of_vertices - 1;
4765             faces[face++][2] = vertex_index(slices, slice, stack);
4766         }
4767     }
4768
4769     vertices[vertex].position.x = 0.0f;
4770     vertices[vertex].position.y = 0.0f;
4771     vertices[vertex].position.z = z;
4772     vertices[vertex].normal.x = 0.0f;
4773     vertices[vertex].normal.y = 0.0f;
4774     vertices[vertex].normal.z = 1.0f;
4775
4776     faces[face][0] = vertex_index(slices, slice-1, stack);
4777     faces[face][1] = number_of_vertices - 1;
4778     faces[face][2] = vertex_index(slices, 0, stack);
4779
4780     free_sincos_table(&theta);
4781     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4782     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4783     *mesh = cylinder;
4784
4785     return D3D_OK;
4786 }
4787
4788 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
4789 {
4790     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
4791
4792     return E_NOTIMPL;
4793 }
4794
4795 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
4796                                HDC hdc, LPCSTR text,
4797                                FLOAT deviation, FLOAT extrusion,
4798                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
4799                                LPGLYPHMETRICSFLOAT glyphmetrics)
4800 {
4801     HRESULT hr;
4802     int len;
4803     LPWSTR textW;
4804
4805     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
4806           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
4807
4808     if (!text)
4809         return D3DERR_INVALIDCALL;
4810
4811     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
4812     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
4813     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
4814
4815     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
4816                          mesh, adjacency, glyphmetrics);
4817     HeapFree(GetProcessHeap(), 0, textW);
4818
4819     return hr;
4820 }
4821
4822 enum pointtype {
4823     POINTTYPE_CURVE = 0,
4824     POINTTYPE_CORNER,
4825     POINTTYPE_CURVE_START,
4826     POINTTYPE_CURVE_END,
4827     POINTTYPE_CURVE_MIDDLE,
4828 };
4829
4830 struct point2d
4831 {
4832     D3DXVECTOR2 pos;
4833     enum pointtype corner;
4834 };
4835
4836 struct dynamic_array
4837 {
4838     int count, capacity;
4839     void *items;
4840 };
4841
4842 /* is a dynamic_array */
4843 struct outline
4844 {
4845     int count, capacity;
4846     struct point2d *items;
4847 };
4848
4849 /* is a dynamic_array */
4850 struct outline_array
4851 {
4852     int count, capacity;
4853     struct outline *items;
4854 };
4855
4856 struct face_array
4857 {
4858     int count;
4859     face *items;
4860 };
4861
4862 struct point2d_index
4863 {
4864     struct outline *outline;
4865     int vertex;
4866 };
4867
4868 struct point2d_index_array
4869 {
4870     int count;
4871     struct point2d_index *items;
4872 };
4873
4874 struct glyphinfo
4875 {
4876     struct outline_array outlines;
4877     struct face_array faces;
4878     struct point2d_index_array ordered_vertices;
4879     float offset_x;
4880 };
4881
4882 /* is an dynamic_array */
4883 struct word_array
4884 {
4885     int count, capacity;
4886     WORD *items;
4887 };
4888
4889 /* complex polygons are split into monotone polygons, which have
4890  * at most 2 intersections with the vertical sweep line */
4891 struct triangulation
4892 {
4893     struct word_array vertex_stack;
4894     BOOL last_on_top, merging;
4895 };
4896
4897 /* is an dynamic_array */
4898 struct triangulation_array
4899 {
4900     int count, capacity;
4901     struct triangulation *items;
4902
4903     struct glyphinfo *glyph;
4904 };
4905
4906 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
4907 {
4908     if (count > array->capacity) {
4909         void *new_buffer;
4910         int new_capacity;
4911         if (array->items && array->capacity) {
4912             new_capacity = max(array->capacity * 2, count);
4913             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
4914         } else {
4915             new_capacity = max(16, count);
4916             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
4917         }
4918         if (!new_buffer)
4919             return FALSE;
4920         array->items = new_buffer;
4921         array->capacity = new_capacity;
4922     }
4923     return TRUE;
4924 }
4925
4926 static struct point2d *add_points(struct outline *array, int num)
4927 {
4928     struct point2d *item;
4929
4930     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
4931         return NULL;
4932
4933     item = &array->items[array->count];
4934     array->count += num;
4935     return item;
4936 }
4937
4938 static struct outline *add_outline(struct outline_array *array)
4939 {
4940     struct outline *item;
4941
4942     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4943         return NULL;
4944
4945     item = &array->items[array->count++];
4946     ZeroMemory(item, sizeof(*item));
4947     return item;
4948 }
4949
4950 static inline face *add_face(struct face_array *array)
4951 {
4952     return &array->items[array->count++];
4953 }
4954
4955 static struct triangulation *add_triangulation(struct triangulation_array *array)
4956 {
4957     struct triangulation *item;
4958
4959     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4960         return NULL;
4961
4962     item = &array->items[array->count++];
4963     ZeroMemory(item, sizeof(*item));
4964     return item;
4965 }
4966
4967 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
4968 {
4969     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4970         return E_OUTOFMEMORY;
4971
4972     array->items[array->count++] = vertex_index;
4973     return S_OK;
4974 }
4975
4976 /* assume fixed point numbers can be converted to float point in place */
4977 C_ASSERT(sizeof(FIXED) == sizeof(float));
4978 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
4979
4980 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
4981 {
4982     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
4983     while (count--) {
4984         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
4985         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
4986         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
4987         pt++;
4988     }
4989     return ret;
4990 }
4991
4992 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
4993                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
4994                                  float max_deviation_sq)
4995 {
4996     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
4997     float deviation_sq;
4998
4999     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
5000     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
5001     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
5002
5003     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
5004     if (deviation_sq < max_deviation_sq) {
5005         struct point2d *pt = add_points(outline, 1);
5006         if (!pt) return E_OUTOFMEMORY;
5007         pt->pos = *p2;
5008         pt->corner = POINTTYPE_CURVE;
5009         /* the end point is omitted because the end line merges into the next segment of
5010          * the split bezier curve, and the end of the split bezier curve is added outside
5011          * this recursive function. */
5012     } else {
5013         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
5014         if (hr != S_OK) return hr;
5015         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
5016         if (hr != S_OK) return hr;
5017     }
5018
5019     return S_OK;
5020 }
5021
5022 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
5023 {
5024     /* dot product = cos(theta) */
5025     return D3DXVec2Dot(dir1, dir2) > cos_theta;
5026 }
5027
5028 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
5029 {
5030     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
5031 }
5032
5033 struct cos_table
5034 {
5035     float cos_half;
5036     float cos_45;
5037     float cos_90;
5038 };
5039
5040 static BOOL attempt_line_merge(struct outline *outline,
5041                                int pt_index,
5042                                const D3DXVECTOR2 *nextpt,
5043                                BOOL to_curve,
5044                                const struct cos_table *table)
5045 {
5046     D3DXVECTOR2 curdir, lastdir;
5047     struct point2d *prevpt, *pt;
5048     BOOL ret = FALSE;
5049
5050     pt = &outline->items[pt_index];
5051     pt_index = (pt_index - 1 + outline->count) % outline->count;
5052     prevpt = &outline->items[pt_index];
5053
5054     if (to_curve)
5055         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
5056
5057     if (outline->count < 2)
5058         return FALSE;
5059
5060     /* remove last point if the next line continues the last line */
5061     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
5062     unit_vec2(&curdir, &pt->pos, nextpt);
5063     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
5064     {
5065         outline->count--;
5066         if (pt->corner == POINTTYPE_CURVE_END)
5067             prevpt->corner = pt->corner;
5068         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
5069             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
5070         pt = prevpt;
5071
5072         ret = TRUE;
5073         if (outline->count < 2)
5074             return ret;
5075
5076         pt_index = (pt_index - 1 + outline->count) % outline->count;
5077         prevpt = &outline->items[pt_index];
5078         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
5079         unit_vec2(&curdir, &pt->pos, nextpt);
5080     }
5081     return ret;
5082 }
5083
5084 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
5085                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
5086 {
5087     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
5088
5089     while ((char *)header < (char *)raw_outline + datasize)
5090     {
5091         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
5092         struct point2d *lastpt, *pt;
5093         D3DXVECTOR2 lastdir;
5094         D3DXVECTOR2 *pt_flt;
5095         int j;
5096         struct outline *outline = add_outline(&glyph->outlines);
5097
5098         if (!outline)
5099             return E_OUTOFMEMORY;
5100
5101         pt = add_points(outline, 1);
5102         if (!pt)
5103             return E_OUTOFMEMORY;
5104         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
5105         pt->pos = *pt_flt;
5106         pt->corner = POINTTYPE_CORNER;
5107
5108         if (header->dwType != TT_POLYGON_TYPE)
5109             FIXME("Unknown header type %d\n", header->dwType);
5110
5111         while ((char *)curve < (char *)header + header->cb)
5112         {
5113             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
5114             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
5115
5116             if (!curve->cpfx) {
5117                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
5118                 continue;
5119             }
5120
5121             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
5122
5123             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
5124
5125             if (to_curve)
5126             {
5127                 HRESULT hr;
5128                 int count = curve->cpfx;
5129                 j = 0;
5130
5131                 while (count > 2)
5132                 {
5133                     D3DXVECTOR2 bezier_end;
5134
5135                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
5136                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
5137                     if (hr != S_OK)
5138                         return hr;
5139                     bezier_start = bezier_end;
5140                     count--;
5141                     j++;
5142                 }
5143                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
5144                 if (hr != S_OK)
5145                     return hr;
5146
5147                 pt = add_points(outline, 1);
5148                 if (!pt)
5149                     return E_OUTOFMEMORY;
5150                 j++;
5151                 pt->pos = pt_flt[j];
5152                 pt->corner = POINTTYPE_CURVE_END;
5153             } else {
5154                 pt = add_points(outline, curve->cpfx);
5155                 if (!pt)
5156                     return E_OUTOFMEMORY;
5157                 for (j = 0; j < curve->cpfx; j++)
5158                 {
5159                     pt->pos = pt_flt[j];
5160                     pt->corner = POINTTYPE_CORNER;
5161                     pt++;
5162                 }
5163             }
5164
5165             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
5166         }
5167
5168         /* remove last point if the next line continues the last line */
5169         if (outline->count >= 3) {
5170             BOOL to_curve;
5171
5172             lastpt = &outline->items[outline->count - 1];
5173             pt = &outline->items[0];
5174             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
5175                 if (lastpt->corner == POINTTYPE_CURVE_END)
5176                 {
5177                     if (pt->corner == POINTTYPE_CURVE_START)
5178                         pt->corner = POINTTYPE_CURVE_MIDDLE;
5179                     else
5180                         pt->corner = POINTTYPE_CURVE_END;
5181                 }
5182                 outline->count--;
5183                 lastpt = &outline->items[outline->count - 1];
5184             } else {
5185                 /* outline closed with a line from end to start point */
5186                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
5187             }
5188             lastpt = &outline->items[0];
5189             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
5190             if (lastpt->corner == POINTTYPE_CURVE_START)
5191                 lastpt->corner = POINTTYPE_CORNER;
5192             pt = &outline->items[1];
5193             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
5194                 *lastpt = outline->items[outline->count];
5195         }
5196
5197         lastpt = &outline->items[outline->count - 1];
5198         pt = &outline->items[0];
5199         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
5200         for (j = 0; j < outline->count; j++)
5201         {
5202             D3DXVECTOR2 curdir;
5203
5204             lastpt = pt;
5205             pt = &outline->items[(j + 1) % outline->count];
5206             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
5207
5208             switch (lastpt->corner)
5209             {
5210                 case POINTTYPE_CURVE_START:
5211                 case POINTTYPE_CURVE_END:
5212                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
5213                         lastpt->corner = POINTTYPE_CORNER;
5214                     break;
5215                 case POINTTYPE_CURVE_MIDDLE:
5216                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
5217                         lastpt->corner = POINTTYPE_CORNER;
5218                     else
5219                         lastpt->corner = POINTTYPE_CURVE;
5220                     break;
5221                 default:
5222                     break;
5223             }
5224             lastdir = curdir;
5225         }
5226
5227         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
5228     }
5229     return S_OK;
5230 }
5231
5232 /* Get the y-distance from a line to a point */
5233 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
5234                                           D3DXVECTOR2 *line_pt2,
5235                                           D3DXVECTOR2 *point)
5236 {
5237     D3DXVECTOR2 line_vec = {0, 0};
5238     float line_pt_dx;
5239     float line_y;
5240
5241     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
5242     line_pt_dx = point->x - line_pt1->x;
5243     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
5244     return point->y - line_y;
5245 }
5246
5247 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
5248 {
5249     return &pt_idx->outline->items[pt_idx->vertex].pos;
5250 }
5251
5252 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
5253 {
5254     return get_indexed_point(&glyph->ordered_vertices.items[index]);
5255 }
5256
5257 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
5258 {
5259     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
5260     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
5261     array->count--;
5262 }
5263
5264 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
5265                                        struct triangulation_array *triangulations,
5266                                        WORD vtx_idx,
5267                                        BOOL to_top)
5268 {
5269     struct glyphinfo *glyph = triangulations->glyph;
5270     struct triangulation *t = *t_ptr;
5271     HRESULT hr;
5272     face *face;
5273     int f1, f2;
5274
5275     if (t->last_on_top) {
5276         f1 = 1;
5277         f2 = 2;
5278     } else {
5279         f1 = 2;
5280         f2 = 1;
5281     }
5282
5283     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
5284         /* consume all vertices on the stack */
5285         WORD last_pt = t->vertex_stack.items[0];
5286         int i;
5287         for (i = 1; i < t->vertex_stack.count; i++)
5288         {
5289             face = add_face(&glyph->faces);
5290             if (!face) return E_OUTOFMEMORY;
5291             (*face)[0] = vtx_idx;
5292             (*face)[f1] = last_pt;
5293             (*face)[f2] = last_pt = t->vertex_stack.items[i];
5294         }
5295         t->vertex_stack.items[0] = last_pt;
5296         t->vertex_stack.count = 1;
5297     } else if (t->vertex_stack.count > 1) {
5298         int i = t->vertex_stack.count - 1;
5299         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
5300         WORD top_idx = t->vertex_stack.items[i--];
5301         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
5302
5303         while (i >= 0)
5304         {
5305             WORD prev_idx = t->vertex_stack.items[i--];
5306             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
5307
5308             if (prev_pt->x != top_pt->x &&
5309                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
5310                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
5311                 break;
5312
5313             face = add_face(&glyph->faces);
5314             if (!face) return E_OUTOFMEMORY;
5315             (*face)[0] = vtx_idx;
5316             (*face)[f1] = prev_idx;
5317             (*face)[f2] = top_idx;
5318
5319             top_pt = prev_pt;
5320             top_idx = prev_idx;
5321             t->vertex_stack.count--;
5322         }
5323     }
5324     t->last_on_top = to_top;
5325
5326     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
5327
5328     if (hr == S_OK && t->merging) {
5329         struct triangulation *t2;
5330
5331         t2 = to_top ? t - 1 : t + 1;
5332         t2->merging = FALSE;
5333         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
5334         if (hr != S_OK) return hr;
5335         remove_triangulation(triangulations, t);
5336         if (t2 > t)
5337             t2--;
5338         *t_ptr = t2;
5339     }
5340     return hr;
5341 }
5342
5343 /* check if the point is next on the outline for either the top or bottom */
5344 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
5345 {
5346     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
5347     WORD idx = t->vertex_stack.items[i];
5348     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
5349     struct outline *outline = pt_idx->outline;
5350
5351     if (on_top)
5352         i = (pt_idx->vertex + outline->count - 1) % outline->count;
5353     else
5354         i = (pt_idx->vertex + 1) % outline->count;
5355
5356     return &outline->items[i].pos;
5357 }
5358
5359 static int compare_vertex_indices(const void *a, const void *b)
5360 {
5361     const struct point2d_index *idx1 = a, *idx2 = b;
5362     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
5363     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
5364     float diff = p1->x - p2->x;
5365
5366     if (diff == 0.0f)
5367         diff = p1->y - p2->y;
5368
5369     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
5370 }
5371
5372 static HRESULT triangulate(struct triangulation_array *triangulations)
5373 {
5374     int sweep_idx;
5375     HRESULT hr;
5376     struct glyphinfo *glyph = triangulations->glyph;
5377     int nb_vertices = 0;
5378     int i;
5379     struct point2d_index *idx_ptr;
5380
5381     for (i = 0; i < glyph->outlines.count; i++)
5382         nb_vertices += glyph->outlines.items[i].count;
5383
5384     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
5385             nb_vertices * sizeof(*glyph->ordered_vertices.items));
5386     if (!glyph->ordered_vertices.items)
5387         return E_OUTOFMEMORY;
5388
5389     idx_ptr = glyph->ordered_vertices.items;
5390     for (i = 0; i < glyph->outlines.count; i++)
5391     {
5392         struct outline *outline = &glyph->outlines.items[i];
5393         int j;
5394
5395         idx_ptr->outline = outline;
5396         idx_ptr->vertex = 0;
5397         idx_ptr++;
5398         for (j = outline->count - 1; j > 0; j--)
5399         {
5400             idx_ptr->outline = outline;
5401             idx_ptr->vertex = j;
5402             idx_ptr++;
5403         }
5404     }
5405     glyph->ordered_vertices.count = nb_vertices;
5406
5407     /* Native implementation seems to try to create a triangle fan from
5408      * the first outline point if the glyph only has one outline. */
5409     if (glyph->outlines.count == 1)
5410     {
5411         struct outline *outline = glyph->outlines.items;
5412         D3DXVECTOR2 *base = &outline->items[0].pos;
5413         D3DXVECTOR2 *last = &outline->items[1].pos;
5414         float ccw = 0;
5415
5416         for (i = 2; i < outline->count; i++)
5417         {
5418             D3DXVECTOR2 *next = &outline->items[i].pos;
5419             D3DXVECTOR2 v1 = {0.0f, 0.0f};
5420             D3DXVECTOR2 v2 = {0.0f, 0.0f};
5421
5422             D3DXVec2Subtract(&v1, base, last);
5423             D3DXVec2Subtract(&v2, last, next);
5424             ccw = D3DXVec2CCW(&v1, &v2);
5425             if (ccw > 0.0f)
5426                 break;
5427
5428             last = next;
5429         }
5430         if (ccw <= 0)
5431         {
5432             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5433                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
5434             if (!glyph->faces.items)
5435                 return E_OUTOFMEMORY;
5436
5437             glyph->faces.count = outline->count - 2;
5438             for (i = 0; i < glyph->faces.count; i++)
5439             {
5440                 glyph->faces.items[i][0] = 0;
5441                 glyph->faces.items[i][1] = i + 1;
5442                 glyph->faces.items[i][2] = i + 2;
5443             }
5444             return S_OK;
5445         }
5446     }
5447
5448     /* Perform 2D polygon triangulation for complex glyphs.
5449      * Triangulation is performed using a sweep line concept, from right to left,
5450      * by processing vertices in sorted order. Complex polygons are split into
5451      * monotone polygons which are triangulated separately. */
5452     /* FIXME: The order of the faces is not consistent with the native implementation. */
5453
5454     /* Reserve space for maximum possible faces from triangulation.
5455      * # faces for outer outlines = outline->count - 2
5456      * # faces for inner outlines = outline->count + 2
5457      * There must be at least 1 outer outline. */
5458     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5459             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
5460     if (!glyph->faces.items)
5461         return E_OUTOFMEMORY;
5462
5463     qsort(glyph->ordered_vertices.items, nb_vertices,
5464           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
5465     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
5466     {
5467         int start = 0;
5468         int end = triangulations->count;
5469
5470         while (start < end)
5471         {
5472             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
5473             int current = (start + end) / 2;
5474             struct triangulation *t = &triangulations->items[current];
5475             BOOL on_top_outline = FALSE;
5476             D3DXVECTOR2 *top_next, *bottom_next;
5477             WORD top_idx, bottom_idx;
5478
5479             if (t->merging && t->last_on_top)
5480                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
5481             else
5482                 top_next = triangulation_get_next_point(t, glyph, TRUE);
5483             if (sweep_vtx == top_next)
5484             {
5485                 if (t->merging && t->last_on_top)
5486                     t++;
5487                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
5488                 if (hr != S_OK) return hr;
5489
5490                 if (t + 1 < &triangulations->items[triangulations->count] &&
5491                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
5492                 {
5493                     /* point also on bottom outline of higher triangulation */
5494                     struct triangulation *t2 = t + 1;
5495                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
5496                     if (hr != S_OK) return hr;
5497
5498                     t->merging = TRUE;
5499                     t2->merging = TRUE;
5500                 }
5501                 on_top_outline = TRUE;
5502             }
5503
5504             if (t->merging && !t->last_on_top)
5505                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
5506             else
5507                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
5508             if (sweep_vtx == bottom_next)
5509             {
5510                 if (t->merging && !t->last_on_top)
5511                     t--;
5512                 if (on_top_outline) {
5513                     /* outline finished */
5514                     remove_triangulation(triangulations, t);
5515                     break;
5516                 }
5517
5518                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
5519                 if (hr != S_OK) return hr;
5520
5521                 if (t > triangulations->items &&
5522                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
5523                 {
5524                     struct triangulation *t2 = t - 1;
5525                     /* point also on top outline of lower triangulation */
5526                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
5527                     if (hr != S_OK) return hr;
5528                     t = t2 + 1; /* t may be invalidated by triangulation merging */
5529
5530                     t->merging = TRUE;
5531                     t2->merging = TRUE;
5532                 }
5533                 break;
5534             }
5535             if (on_top_outline)
5536                 break;
5537
5538             if (t->last_on_top) {
5539                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5540                 bottom_idx = t->vertex_stack.items[0];
5541             } else {
5542                 top_idx = t->vertex_stack.items[0];
5543                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5544             }
5545
5546             /* check if the point is inside or outside this polygon */
5547             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
5548                                              top_next, sweep_vtx) > 0)
5549             { /* above */
5550                 start = current + 1;
5551             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
5552                                                     bottom_next, sweep_vtx) < 0)
5553             { /* below */
5554                 end = current;
5555             } else if (t->merging) {
5556                 /* inside, so cancel merging */
5557                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
5558                 t->merging = FALSE;
5559                 t2->merging = FALSE;
5560                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5561                 if (hr != S_OK) return hr;
5562                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
5563                 if (hr != S_OK) return hr;
5564                 break;
5565             } else {
5566                 /* inside, so split polygon into two monotone parts */
5567                 struct triangulation *t2 = add_triangulation(triangulations);
5568                 if (!t2) return E_OUTOFMEMORY;
5569                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5570                 if (t->last_on_top) {
5571                     t2 = t + 1;
5572                 } else {
5573                     t2 = t;
5574                     t++;
5575                 }
5576
5577                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
5578                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
5579                 if (hr != S_OK) return hr;
5580                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
5581                 if (hr != S_OK) return hr;
5582                 t2->last_on_top = !t->last_on_top;
5583
5584                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5585                 if (hr != S_OK) return hr;
5586                 break;
5587             }
5588         }
5589         if (start >= end)
5590         {
5591             struct triangulation *t;
5592             struct triangulation *t2 = add_triangulation(triangulations);
5593             if (!t2) return E_OUTOFMEMORY;
5594             t = &triangulations->items[start];
5595             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5596             ZeroMemory(t, sizeof(*t));
5597             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
5598             if (hr != S_OK) return hr;
5599         }
5600     }
5601     return S_OK;
5602 }
5603
5604 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
5605                                HDC hdc, LPCWSTR text,
5606                                FLOAT deviation, FLOAT extrusion,
5607                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
5608                                LPGLYPHMETRICSFLOAT glyphmetrics)
5609 {
5610     HRESULT hr;
5611     ID3DXMesh *mesh = NULL;
5612     DWORD nb_vertices, nb_faces;
5613     DWORD nb_front_faces, nb_corners, nb_outline_points;
5614     struct vertex *vertices = NULL;
5615     face *faces = NULL;
5616     int textlen = 0;
5617     float offset_x;
5618     LOGFONTW lf;
5619     OUTLINETEXTMETRICW otm;
5620     HFONT font = NULL, oldfont = NULL;
5621     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
5622     void *raw_outline = NULL;
5623     int bufsize = 0;
5624     struct glyphinfo *glyphs = NULL;
5625     GLYPHMETRICS gm;
5626     struct triangulation_array triangulations = {0, 0, NULL};
5627     int i;
5628     struct vertex *vertex_ptr;
5629     face *face_ptr;
5630     float max_deviation_sq;
5631     const struct cos_table cos_table = {
5632         cos(D3DXToRadian(0.5f)),
5633         cos(D3DXToRadian(45.0f)),
5634         cos(D3DXToRadian(90.0f)),
5635     };
5636     int f1, f2;
5637
5638     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
5639           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
5640
5641     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
5642         return D3DERR_INVALIDCALL;
5643
5644     if (adjacency)
5645     {
5646         FIXME("Case of adjacency != NULL not implemented.\n");
5647         return E_NOTIMPL;
5648     }
5649
5650     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
5651         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
5652     {
5653         return D3DERR_INVALIDCALL;
5654     }
5655
5656     if (deviation == 0.0f)
5657         deviation = 1.0f / otm.otmEMSquare;
5658     max_deviation_sq = deviation * deviation;
5659
5660     lf.lfHeight = otm.otmEMSquare;
5661     lf.lfWidth = 0;
5662     font = CreateFontIndirectW(&lf);
5663     if (!font) {
5664         hr = E_OUTOFMEMORY;
5665         goto error;
5666     }
5667     oldfont = SelectObject(hdc, font);
5668
5669     textlen = strlenW(text);
5670     for (i = 0; i < textlen; i++)
5671     {
5672         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
5673         if (datasize < 0)
5674             return D3DERR_INVALIDCALL;
5675         if (bufsize < datasize)
5676             bufsize = datasize;
5677     }
5678     if (!bufsize) { /* e.g. text == " " */
5679         hr = D3DERR_INVALIDCALL;
5680         goto error;
5681     }
5682
5683     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
5684     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
5685     if (!glyphs || !raw_outline) {
5686         hr = E_OUTOFMEMORY;
5687         goto error;
5688     }
5689
5690     offset_x = 0.0f;
5691     for (i = 0; i < textlen; i++)
5692     {
5693         /* get outline points from data returned from GetGlyphOutline */
5694         int datasize;
5695
5696         glyphs[i].offset_x = offset_x;
5697
5698         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
5699         hr = create_outline(&glyphs[i], raw_outline, datasize,
5700                             max_deviation_sq, otm.otmEMSquare, &cos_table);
5701         if (hr != S_OK) goto error;
5702
5703         triangulations.glyph = &glyphs[i];
5704         hr = triangulate(&triangulations);
5705         if (hr != S_OK) goto error;
5706         if (triangulations.count) {
5707             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
5708             triangulations.count = 0;
5709         }
5710
5711         if (glyphmetrics)
5712         {
5713             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
5714             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
5715             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
5716             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
5717             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
5718             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
5719         }
5720         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
5721     }
5722
5723     /* corner points need an extra vertex for the different side faces normals */
5724     nb_corners = 0;
5725     nb_outline_points = 0;
5726     nb_front_faces = 0;
5727     for (i = 0; i < textlen; i++)
5728     {
5729         int j;
5730         nb_outline_points += glyphs[i].ordered_vertices.count;
5731         nb_front_faces += glyphs[i].faces.count;
5732         for (j = 0; j < glyphs[i].outlines.count; j++)
5733         {
5734             int k;
5735             struct outline *outline = &glyphs[i].outlines.items[j];
5736             nb_corners++; /* first outline point always repeated as a corner */
5737             for (k = 1; k < outline->count; k++)
5738                 if (outline->items[k].corner)
5739                     nb_corners++;
5740         }
5741     }
5742
5743     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
5744     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
5745
5746
5747     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
5748                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
5749     if (FAILED(hr))
5750         goto error;
5751
5752     hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (LPVOID *)&vertices);
5753     if (FAILED(hr))
5754         goto error;
5755
5756     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, (LPVOID *)&faces);
5757     if (FAILED(hr))
5758         goto error;
5759
5760     /* convert 2D vertices and faces into 3D mesh */
5761     vertex_ptr = vertices;
5762     face_ptr = faces;
5763     if (extrusion == 0.0f) {
5764         f1 = 1;
5765         f2 = 2;
5766     } else {
5767         f1 = 2;
5768         f2 = 1;
5769     }
5770     for (i = 0; i < textlen; i++)
5771     {
5772         int j;
5773         int count;
5774         struct vertex *back_vertices;
5775         face *back_faces;
5776
5777         /* side vertices and faces */
5778         for (j = 0; j < glyphs[i].outlines.count; j++)
5779         {
5780             struct vertex *outline_vertices = vertex_ptr;
5781             struct outline *outline = &glyphs[i].outlines.items[j];
5782             int k;
5783             struct point2d *prevpt = &outline->items[outline->count - 1];
5784             struct point2d *pt = &outline->items[0];
5785
5786             for (k = 1; k <= outline->count; k++)
5787             {
5788                 struct vertex vtx;
5789                 struct point2d *nextpt = &outline->items[k % outline->count];
5790                 WORD vtx_idx = vertex_ptr - vertices;
5791                 D3DXVECTOR2 vec;
5792
5793                 if (pt->corner == POINTTYPE_CURVE_START)
5794                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
5795                 else if (pt->corner)
5796                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5797                 else
5798                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
5799                 D3DXVec2Normalize(&vec, &vec);
5800                 vtx.normal.x = -vec.y;
5801                 vtx.normal.y = vec.x;
5802                 vtx.normal.z = 0;
5803
5804                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
5805                 vtx.position.y = pt->pos.y;
5806                 vtx.position.z = 0;
5807                 *vertex_ptr++ = vtx;
5808
5809                 vtx.position.z = -extrusion;
5810                 *vertex_ptr++ = vtx;
5811
5812                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
5813                 vtx.position.y = nextpt->pos.y;
5814                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
5815                     vtx.position.z = -extrusion;
5816                     *vertex_ptr++ = vtx;
5817                     vtx.position.z = 0;
5818                     *vertex_ptr++ = vtx;
5819
5820                     (*face_ptr)[0] = vtx_idx;
5821                     (*face_ptr)[1] = vtx_idx + 2;
5822                     (*face_ptr)[2] = vtx_idx + 1;
5823                     face_ptr++;
5824
5825                     (*face_ptr)[0] = vtx_idx;
5826                     (*face_ptr)[1] = vtx_idx + 3;
5827                     (*face_ptr)[2] = vtx_idx + 2;
5828                     face_ptr++;
5829                 } else {
5830                     if (nextpt->corner) {
5831                         if (nextpt->corner == POINTTYPE_CURVE_END) {
5832                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
5833                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
5834                         } else {
5835                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5836                         }
5837                         D3DXVec2Normalize(&vec, &vec);
5838                         vtx.normal.x = -vec.y;
5839                         vtx.normal.y = vec.x;
5840
5841                         vtx.position.z = 0;
5842                         *vertex_ptr++ = vtx;
5843                         vtx.position.z = -extrusion;
5844                         *vertex_ptr++ = vtx;
5845                     }
5846
5847                     (*face_ptr)[0] = vtx_idx;
5848                     (*face_ptr)[1] = vtx_idx + 3;
5849                     (*face_ptr)[2] = vtx_idx + 1;
5850                     face_ptr++;
5851
5852                     (*face_ptr)[0] = vtx_idx;
5853                     (*face_ptr)[1] = vtx_idx + 2;
5854                     (*face_ptr)[2] = vtx_idx + 3;
5855                     face_ptr++;
5856                 }
5857
5858                 prevpt = pt;
5859                 pt = nextpt;
5860             }
5861             if (!pt->corner) {
5862                 *vertex_ptr++ = *outline_vertices++;
5863                 *vertex_ptr++ = *outline_vertices++;
5864             }
5865         }
5866
5867         /* back vertices and faces */
5868         back_faces = face_ptr;
5869         back_vertices = vertex_ptr;
5870         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
5871         {
5872             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
5873             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
5874             vertex_ptr->position.y = pt->y;
5875             vertex_ptr->position.z = 0;
5876             vertex_ptr->normal.x = 0;
5877             vertex_ptr->normal.y = 0;
5878             vertex_ptr->normal.z = 1;
5879             vertex_ptr++;
5880         }
5881         count = back_vertices - vertices;
5882         for (j = 0; j < glyphs[i].faces.count; j++)
5883         {
5884             face *f = &glyphs[i].faces.items[j];
5885             (*face_ptr)[0] = (*f)[0] + count;
5886             (*face_ptr)[1] = (*f)[1] + count;
5887             (*face_ptr)[2] = (*f)[2] + count;
5888             face_ptr++;
5889         }
5890
5891         /* front vertices and faces */
5892         j = count = vertex_ptr - back_vertices;
5893         while (j--)
5894         {
5895             vertex_ptr->position.x = back_vertices->position.x;
5896             vertex_ptr->position.y = back_vertices->position.y;
5897             vertex_ptr->position.z = -extrusion;
5898             vertex_ptr->normal.x = 0;
5899             vertex_ptr->normal.y = 0;
5900             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
5901             vertex_ptr++;
5902             back_vertices++;
5903         }
5904         j = face_ptr - back_faces;
5905         while (j--)
5906         {
5907             (*face_ptr)[0] = (*back_faces)[0] + count;
5908             (*face_ptr)[1] = (*back_faces)[f1] + count;
5909             (*face_ptr)[2] = (*back_faces)[f2] + count;
5910             face_ptr++;
5911             back_faces++;
5912         }
5913     }
5914
5915     *mesh_ptr = mesh;
5916     hr = D3D_OK;
5917 error:
5918     if (mesh) {
5919         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
5920         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
5921         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
5922     }
5923     if (glyphs) {
5924         for (i = 0; i < textlen; i++)
5925         {
5926             int j;
5927             for (j = 0; j < glyphs[i].outlines.count; j++)
5928                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
5929             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
5930             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
5931             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
5932         }
5933         HeapFree(GetProcessHeap(), 0, glyphs);
5934     }
5935     if (triangulations.items) {
5936         int i;
5937         for (i = 0; i < triangulations.count; i++)
5938             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
5939         HeapFree(GetProcessHeap(), 0, triangulations.items);
5940     }
5941     HeapFree(GetProcessHeap(), 0, raw_outline);
5942     if (oldfont) SelectObject(hdc, oldfont);
5943     if (font) DeleteObject(font);
5944
5945     return hr;
5946 }
5947
5948 HRESULT WINAPI D3DXValidMesh(LPD3DXMESH mesh, CONST DWORD *adjacency, LPD3DXBUFFER *errors_and_warnings)
5949 {
5950     FIXME("(%p, %p, %p): stub\n", mesh, adjacency, *errors_and_warnings);
5951
5952     return E_NOTIMPL;
5953 }
5954
5955 static BOOL weld_float1(void *to, void *from, FLOAT epsilon)
5956 {
5957     FLOAT *v1 = to;
5958     FLOAT *v2 = from;
5959
5960     if (fabsf(*v1 - *v2) <= epsilon)
5961     {
5962         *v1 = *v2;
5963
5964         return TRUE;
5965     }
5966
5967     return FALSE;
5968 }
5969
5970 static BOOL weld_float2(void *to, void *from, FLOAT epsilon)
5971 {
5972     D3DXVECTOR2 *v1 = to;
5973     D3DXVECTOR2 *v2 = from;
5974     FLOAT diff_x = fabsf(v1->x - v2->x);
5975     FLOAT diff_y = fabsf(v1->y - v2->y);
5976     FLOAT max_abs_diff = max(diff_x, diff_y);
5977
5978     if (max_abs_diff <= epsilon)
5979     {
5980         memcpy(to, from, sizeof(D3DXVECTOR2));
5981
5982         return TRUE;
5983     }
5984
5985     return FALSE;
5986 }
5987
5988 static BOOL weld_float3(void *to, void *from, FLOAT epsilon)
5989 {
5990     D3DXVECTOR3 *v1 = to;
5991     D3DXVECTOR3 *v2 = from;
5992     FLOAT diff_x = fabsf(v1->x - v2->x);
5993     FLOAT diff_y = fabsf(v1->y - v2->y);
5994     FLOAT diff_z = fabsf(v1->z - v2->z);
5995     FLOAT max_abs_diff = max(diff_x, diff_y);
5996     max_abs_diff = max(diff_z, max_abs_diff);
5997
5998     if (max_abs_diff <= epsilon)
5999     {
6000         memcpy(to, from, sizeof(D3DXVECTOR3));
6001
6002         return TRUE;
6003     }
6004
6005     return FALSE;
6006 }
6007
6008 static BOOL weld_float4(void *to, void *from, FLOAT epsilon)
6009 {
6010     D3DXVECTOR4 *v1 = to;
6011     D3DXVECTOR4 *v2 = from;
6012     FLOAT diff_x = fabsf(v1->x - v2->x);
6013     FLOAT diff_y = fabsf(v1->y - v2->y);
6014     FLOAT diff_z = fabsf(v1->z - v2->z);
6015     FLOAT diff_w = fabsf(v1->w - v2->w);
6016     FLOAT max_abs_diff = fmax(diff_x, diff_y);
6017     max_abs_diff = max(diff_z, max_abs_diff);
6018     max_abs_diff = max(diff_w, max_abs_diff);
6019
6020     if (max_abs_diff <= epsilon)
6021     {
6022         memcpy(to, from, sizeof(D3DXVECTOR4));
6023
6024         return TRUE;
6025     }
6026
6027     return FALSE;
6028 }
6029
6030 static BOOL weld_ubyte4(void *to, void *from, FLOAT epsilon)
6031 {
6032     BYTE *b1 = to;
6033     BYTE *b2 = from;
6034     BYTE truncated_epsilon = (BYTE)epsilon;
6035     BYTE diff_x = b1[0] > b2[0] ? b1[0] - b2[0] : b2[0] - b1[0];
6036     BYTE diff_y = b1[1] > b2[1] ? b1[1] - b2[1] : b2[1] - b1[1];
6037     BYTE diff_z = b1[2] > b2[2] ? b1[2] - b2[2] : b2[2] - b1[2];
6038     BYTE diff_w = b1[3] > b2[3] ? b1[3] - b2[3] : b2[3] - b1[3];
6039     BYTE max_diff = max(diff_x, diff_y);
6040     max_diff = max(diff_z, max_diff);
6041     max_diff = max(diff_w, max_diff);
6042
6043     if (max_diff <= truncated_epsilon)
6044     {
6045         memcpy(to, from, 4 * sizeof(BYTE));
6046
6047         return TRUE;
6048     }
6049
6050     return FALSE;
6051 }
6052
6053 static BOOL weld_ubyte4n(void *to, void *from, FLOAT epsilon)
6054 {
6055     return weld_ubyte4(to, from, epsilon * UCHAR_MAX);
6056 }
6057
6058 static BOOL weld_d3dcolor(void *to, void *from, FLOAT epsilon)
6059 {
6060     return weld_ubyte4n(to, from, epsilon);
6061 }
6062
6063 static BOOL weld_short2(void *to, void *from, FLOAT epsilon)
6064 {
6065     SHORT *s1 = to;
6066     SHORT *s2 = from;
6067     SHORT truncated_epsilon = (SHORT)epsilon;
6068     SHORT diff_x = abs(s1[0] - s2[0]);
6069     SHORT diff_y = abs(s1[1] - s2[1]);
6070     SHORT max_abs_diff = max(diff_x, diff_y);
6071
6072     if (max_abs_diff <= truncated_epsilon)
6073     {
6074         memcpy(to, from, 2 * sizeof(SHORT));
6075
6076         return TRUE;
6077     }
6078
6079     return FALSE;
6080 }
6081
6082 static BOOL weld_short2n(void *to, void *from, FLOAT epsilon)
6083 {
6084     return weld_short2(to, from, epsilon * SHRT_MAX);
6085 }
6086
6087 static BOOL weld_short4(void *to, void *from, FLOAT epsilon)
6088 {
6089     SHORT *s1 = to;
6090     SHORT *s2 = from;
6091     SHORT truncated_epsilon = (SHORT)epsilon;
6092     SHORT diff_x = abs(s1[0] - s2[0]);
6093     SHORT diff_y = abs(s1[1] - s2[1]);
6094     SHORT diff_z = abs(s1[2] - s2[2]);
6095     SHORT diff_w = abs(s1[3] - s2[3]);
6096     SHORT max_abs_diff = max(diff_x, diff_y);
6097     max_abs_diff = max(diff_z, max_abs_diff);
6098     max_abs_diff = max(diff_w, max_abs_diff);
6099
6100     if (max_abs_diff <= truncated_epsilon)
6101     {
6102         memcpy(to, from, 4 * sizeof(SHORT));
6103
6104         return TRUE;
6105     }
6106
6107     return FALSE;
6108 }
6109
6110 static BOOL weld_short4n(void *to, void *from, FLOAT epsilon)
6111 {
6112     return weld_short4(to, from, epsilon * SHRT_MAX);
6113 }
6114
6115 static BOOL weld_ushort2n(void *to, void *from, FLOAT epsilon)
6116 {
6117     USHORT *s1 = to;
6118     USHORT *s2 = from;
6119     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
6120     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
6121     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
6122     USHORT max_diff = max(diff_x, diff_y);
6123
6124     if (max_diff <= scaled_epsilon)
6125     {
6126         memcpy(to, from, 2 * sizeof(USHORT));
6127
6128         return TRUE;
6129     }
6130
6131     return FALSE;
6132 }
6133
6134 static BOOL weld_ushort4n(void *to, void *from, FLOAT epsilon)
6135 {
6136     USHORT *s1 = to;
6137     USHORT *s2 = from;
6138     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
6139     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
6140     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
6141     USHORT diff_z = s1[2] > s2[2] ? s1[2] - s2[2] : s2[2] - s1[2];
6142     USHORT diff_w = s1[3] > s2[3] ? s1[3] - s2[3] : s2[3] - s1[3];
6143     USHORT max_diff = max(diff_x, diff_y);
6144     max_diff = max(diff_z, max_diff);
6145     max_diff = max(diff_w, max_diff);
6146
6147     if (max_diff <= scaled_epsilon)
6148     {
6149         memcpy(to, from, 4 * sizeof(USHORT));
6150
6151         return TRUE;
6152     }
6153
6154     return FALSE;
6155 }
6156
6157 struct udec3
6158 {
6159     UINT x;
6160     UINT y;
6161     UINT z;
6162     UINT w;
6163 };
6164
6165 static struct udec3 dword_to_udec3(DWORD d)
6166 {
6167     struct udec3 v;
6168
6169     v.x = d & 0x3ff;
6170     v.y = (d & 0xffc00) >> 10;
6171     v.z = (d & 0x3ff00000) >> 20;
6172     v.w = (d & 0xc0000000) >> 30;
6173
6174     return v;
6175 }
6176
6177 static BOOL weld_udec3(void *to, void *from, FLOAT epsilon)
6178 {
6179     DWORD *d1 = to;
6180     DWORD *d2 = from;
6181     struct udec3 v1 = dword_to_udec3(*d1);
6182     struct udec3 v2 = dword_to_udec3(*d2);
6183     UINT truncated_epsilon = (UINT)epsilon;
6184     UINT diff_x = v1.x > v2.x ? v1.x - v2.x : v2.x - v1.x;
6185     UINT diff_y = v1.y > v2.y ? v1.y - v2.y : v2.y - v1.y;
6186     UINT diff_z = v1.z > v2.z ? v1.z - v2.z : v2.z - v1.z;
6187     UINT diff_w = v1.w > v2.w ? v1.w - v2.w : v2.w - v1.w;
6188     UINT max_diff = max(diff_x, diff_y);
6189     max_diff = max(diff_z, max_diff);
6190     max_diff = max(diff_w, max_diff);
6191
6192     if (max_diff <= truncated_epsilon)
6193     {
6194         memcpy(to, from, sizeof(DWORD));
6195
6196         return TRUE;
6197     }
6198
6199     return FALSE;
6200 }
6201
6202 struct dec3n
6203 {
6204     INT x;
6205     INT y;
6206     INT z;
6207     INT w;
6208 };
6209
6210 static struct dec3n dword_to_dec3n(DWORD d)
6211 {
6212     struct dec3n v;
6213
6214     v.x = d & 0x3ff;
6215     v.y = (d & 0xffc00) >> 10;
6216     v.z = (d & 0x3ff00000) >> 20;
6217     v.w = (d & 0xc0000000) >> 30;
6218
6219     return v;
6220 }
6221
6222 static BOOL weld_dec3n(void *to, void *from, FLOAT epsilon)
6223 {
6224     const UINT MAX_DEC3N = 511;
6225     DWORD *d1 = to;
6226     DWORD *d2 = from;
6227     struct dec3n v1 = dword_to_dec3n(*d1);
6228     struct dec3n v2 = dword_to_dec3n(*d2);
6229     INT scaled_epsilon = (INT)(epsilon * MAX_DEC3N);
6230     INT diff_x = abs(v1.x - v2.x);
6231     INT diff_y = abs(v1.y - v2.y);
6232     INT diff_z = abs(v1.z - v2.z);
6233     INT diff_w = abs(v1.w - v2.w);
6234     INT max_abs_diff = max(diff_x, diff_y);
6235     max_abs_diff = max(diff_z, max_abs_diff);
6236     max_abs_diff = max(diff_w, max_abs_diff);
6237
6238     if (max_abs_diff <= scaled_epsilon)
6239     {
6240         memcpy(to, from, sizeof(DWORD));
6241
6242         return TRUE;
6243     }
6244
6245     return FALSE;
6246 }
6247
6248 static BOOL weld_float16_2(void *to, void *from, FLOAT epsilon)
6249 {
6250     D3DXFLOAT16 *v1_float16 = to;
6251     D3DXFLOAT16 *v2_float16 = from;
6252     FLOAT diff_x;
6253     FLOAT diff_y;
6254     FLOAT max_abs_diff;
6255     const UINT NUM_ELEM = 2;
6256     FLOAT v1[NUM_ELEM];
6257     FLOAT v2[NUM_ELEM];
6258
6259     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
6260     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
6261
6262     diff_x = fabsf(v1[0] - v2[0]);
6263     diff_y = fabsf(v1[1] - v2[1]);
6264     max_abs_diff = max(diff_x, diff_y);
6265
6266     if (max_abs_diff <= epsilon)
6267     {
6268         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
6269
6270         return TRUE;
6271     }
6272
6273     return FALSE;
6274 }
6275
6276 static BOOL weld_float16_4(void *to, void *from, FLOAT epsilon)
6277 {
6278     D3DXFLOAT16 *v1_float16 = to;
6279     D3DXFLOAT16 *v2_float16 = from;
6280     FLOAT diff_x;
6281     FLOAT diff_y;
6282     FLOAT diff_z;
6283     FLOAT diff_w;
6284     FLOAT max_abs_diff;
6285     const UINT NUM_ELEM = 4;
6286     FLOAT v1[NUM_ELEM];
6287     FLOAT v2[NUM_ELEM];
6288
6289     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
6290     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
6291
6292     diff_x = fabsf(v1[0] - v2[0]);
6293     diff_y = fabsf(v1[1] - v2[1]);
6294     diff_z = fabsf(v1[2] - v2[2]);
6295     diff_w = fabsf(v1[3] - v2[3]);
6296     max_abs_diff = max(diff_x, diff_y);
6297     max_abs_diff = max(diff_z, max_abs_diff);
6298     max_abs_diff = max(diff_w, max_abs_diff);
6299
6300     if (max_abs_diff <= epsilon)
6301     {
6302         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
6303
6304         return TRUE;
6305     }
6306
6307     return FALSE;
6308 }
6309
6310 /* Sets the vertex components to the same value if they are within epsilon. */
6311 static BOOL weld_component(void *to, void *from, D3DDECLTYPE type, FLOAT epsilon)
6312 {
6313     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
6314     BOOL fixme_once_unused = FALSE;
6315     BOOL fixme_once_unknown = FALSE;
6316
6317     switch (type)
6318     {
6319         case D3DDECLTYPE_FLOAT1:
6320             return weld_float1(to, from, epsilon);
6321
6322         case D3DDECLTYPE_FLOAT2:
6323             return weld_float2(to, from, epsilon);
6324
6325         case D3DDECLTYPE_FLOAT3:
6326             return weld_float3(to, from, epsilon);
6327
6328         case D3DDECLTYPE_FLOAT4:
6329             return weld_float4(to, from, epsilon);
6330
6331         case D3DDECLTYPE_D3DCOLOR:
6332             return weld_d3dcolor(to, from, epsilon);
6333
6334         case D3DDECLTYPE_UBYTE4:
6335             return weld_ubyte4(to, from, epsilon);
6336
6337         case D3DDECLTYPE_SHORT2:
6338             return weld_short2(to, from, epsilon);
6339
6340         case D3DDECLTYPE_SHORT4:
6341             return weld_short4(to, from, epsilon);
6342
6343         case D3DDECLTYPE_UBYTE4N:
6344             return weld_ubyte4n(to, from, epsilon);
6345
6346         case D3DDECLTYPE_SHORT2N:
6347             return weld_short2n(to, from, epsilon);
6348
6349         case D3DDECLTYPE_SHORT4N:
6350             return weld_short4n(to, from, epsilon);
6351
6352         case D3DDECLTYPE_USHORT2N:
6353             return weld_ushort2n(to, from, epsilon);
6354
6355         case D3DDECLTYPE_USHORT4N:
6356             return weld_ushort4n(to, from, epsilon);
6357
6358         case D3DDECLTYPE_UDEC3:
6359             return weld_udec3(to, from, epsilon);
6360
6361         case D3DDECLTYPE_DEC3N:
6362             return weld_dec3n(to, from, epsilon);
6363
6364         case D3DDECLTYPE_FLOAT16_2:
6365             return weld_float16_2(to, from, epsilon);
6366
6367         case D3DDECLTYPE_FLOAT16_4:
6368             return weld_float16_4(to, from, epsilon);
6369
6370         case D3DDECLTYPE_UNUSED:
6371             if (!fixme_once_unused++)
6372                 FIXME("D3DDECLTYPE_UNUSED welding not implemented.\n");
6373             break;
6374
6375         default:
6376             if (!fixme_once_unknown++)
6377                 FIXME("Welding of unknown declaration type %d is not implemented.\n", type);
6378             break;
6379     }
6380
6381     return FALSE;
6382 }
6383
6384 static FLOAT get_component_epsilon(const D3DVERTEXELEMENT9 *decl_ptr, const D3DXWELDEPSILONS *epsilons)
6385 {
6386     FLOAT epsilon = 0.0f;
6387     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
6388     static BOOL fixme_once_blendindices = FALSE;
6389     static BOOL fixme_once_positiont = FALSE;
6390     static BOOL fixme_once_fog = FALSE;
6391     static BOOL fixme_once_depth = FALSE;
6392     static BOOL fixme_once_sample = FALSE;
6393     static BOOL fixme_once_unknown = FALSE;
6394
6395     switch (decl_ptr->Usage)
6396     {
6397         case D3DDECLUSAGE_POSITION:
6398             epsilon = epsilons->Position;
6399             break;
6400         case D3DDECLUSAGE_BLENDWEIGHT:
6401             epsilon = epsilons->BlendWeights;
6402             break;
6403         case D3DDECLUSAGE_NORMAL:
6404             epsilon = epsilons->Normals;
6405             break;
6406         case D3DDECLUSAGE_PSIZE:
6407             epsilon = epsilons->PSize;
6408             break;
6409         case D3DDECLUSAGE_TEXCOORD:
6410         {
6411             BYTE usage_index = decl_ptr->UsageIndex;
6412             if (usage_index > 7)
6413                 usage_index = 7;
6414             epsilon = epsilons->Texcoords[usage_index];
6415             break;
6416         }
6417         case D3DDECLUSAGE_TANGENT:
6418             epsilon = epsilons->Tangent;
6419             break;
6420         case D3DDECLUSAGE_BINORMAL:
6421             epsilon = epsilons->Binormal;
6422             break;
6423         case D3DDECLUSAGE_TESSFACTOR:
6424             epsilon = epsilons->TessFactor;
6425             break;
6426         case D3DDECLUSAGE_COLOR:
6427             if (decl_ptr->UsageIndex == 0)
6428                 epsilon = epsilons->Diffuse;
6429             else if (decl_ptr->UsageIndex == 1)
6430                 epsilon = epsilons->Specular;
6431             else
6432                 epsilon = 1e-6f;
6433             break;
6434         case D3DDECLUSAGE_BLENDINDICES:
6435             if (!fixme_once_blendindices++)
6436                 FIXME("D3DDECLUSAGE_BLENDINDICES welding not implemented.\n");
6437             break;
6438         case D3DDECLUSAGE_POSITIONT:
6439             if (!fixme_once_positiont++)
6440                 FIXME("D3DDECLUSAGE_POSITIONT welding not implemented.\n");
6441             break;
6442         case D3DDECLUSAGE_FOG:
6443             if (!fixme_once_fog++)
6444                 FIXME("D3DDECLUSAGE_FOG welding not implemented.\n");
6445             break;
6446         case D3DDECLUSAGE_DEPTH:
6447             if (!fixme_once_depth++)
6448                 FIXME("D3DDECLUSAGE_DEPTH welding not implemented.\n");
6449             break;
6450         case D3DDECLUSAGE_SAMPLE:
6451             if (!fixme_once_sample++)
6452                 FIXME("D3DDECLUSAGE_SAMPLE welding not implemented.\n");
6453             break;
6454         default:
6455             if (!fixme_once_unknown++)
6456                 FIXME("Unknown usage %x\n", decl_ptr->Usage);
6457             break;
6458     }
6459
6460     return epsilon;
6461 }
6462
6463 /* Helper function for reading a 32-bit index buffer. */
6464 static inline DWORD read_ib(void *index_buffer, BOOL indices_are_32bit,
6465                             DWORD index)
6466 {
6467     if (indices_are_32bit)
6468     {
6469         DWORD *indices = index_buffer;
6470         return indices[index];
6471     }
6472     else
6473     {
6474         WORD *indices = index_buffer;
6475         return indices[index];
6476     }
6477 }
6478
6479 /* Helper function for writing to a 32-bit index buffer. */
6480 static inline void write_ib(void *index_buffer, BOOL indices_are_32bit,
6481                             DWORD index, DWORD value)
6482 {
6483     if (indices_are_32bit)
6484     {
6485         DWORD *indices = index_buffer;
6486         indices[index] = value;
6487     }
6488     else
6489     {
6490         WORD *indices = index_buffer;
6491         indices[index] = value;
6492     }
6493 }
6494
6495 /*************************************************************************
6496  * D3DXWeldVertices    (D3DX9_36.@)
6497  *
6498  * Welds together similar vertices. The similarity between vert-
6499  * ices can be the position and other components such as
6500  * normal and color.
6501  *
6502  * PARAMS
6503  *   mesh             [I] Mesh which vertices will be welded together.
6504  *   flags            [I] D3DXWELDEPSILONSFLAGS specifying how to weld.
6505  *   epsilons         [I] How similar a component needs to be for welding.
6506  *   adjacency        [I] Which faces are adjacent to other faces.
6507  *   adjacency_out    [O] Updated adjacency after welding.
6508  *   face_remap_out   [O] Which faces the old faces have been mapped to.
6509  *   vertex_remap_out [O] Which vertices the old vertices have been mapped to.
6510  *
6511  * RETURNS
6512  *   Success: D3D_OK.
6513  *   Failure: D3DERR_INVALIDCALL, E_OUTOFMEMORY.
6514  *
6515  * BUGS
6516  *   Attribute sorting not implemented.
6517  *
6518  */
6519 HRESULT WINAPI D3DXWeldVertices(LPD3DXMESH mesh,
6520                                 DWORD flags,
6521                                 CONST D3DXWELDEPSILONS *epsilons,
6522                                 CONST DWORD *adjacency,
6523                                 DWORD *adjacency_out,
6524                                 DWORD *face_remap_out,
6525                                 LPD3DXBUFFER *vertex_remap_out)
6526 {
6527     DWORD *adjacency_generated = NULL;
6528     const DWORD *adjacency_ptr;
6529     DWORD *attributes = NULL;
6530     const FLOAT DEFAULT_EPSILON = 1.0e-6f;
6531     HRESULT hr;
6532     DWORD i;
6533     void *indices = NULL;
6534     BOOL indices_are_32bit = mesh->lpVtbl->GetOptions(mesh) & D3DXMESH_32BIT;
6535     DWORD optimize_flags;
6536     DWORD *point_reps = NULL;
6537     ID3DXMeshImpl *This = impl_from_ID3DXMesh(mesh);
6538     DWORD *vertex_face_map = NULL;
6539     ID3DXBuffer *vertex_remap = NULL;
6540     BYTE *vertices = NULL;
6541
6542     TRACE("(%p, %x, %p, %p, %p, %p, %p)\n", mesh, flags, epsilons,
6543            adjacency, adjacency_out, face_remap_out, vertex_remap_out);
6544
6545     if (flags == 0)
6546     {
6547         WARN("No flags is undefined. Using D3DXWELDEPSILONS_WELDPARTIALMATCHES instead.\n");
6548         flags = D3DXWELDEPSILONS_WELDPARTIALMATCHES;
6549     }
6550
6551     if (adjacency) /* Use supplied adjacency. */
6552     {
6553         adjacency_ptr = adjacency;
6554     }
6555     else /* Adjacency has to be generated. */
6556     {
6557         adjacency_generated = HeapAlloc(GetProcessHeap(), 0, 3 * This->numfaces * sizeof(*adjacency_generated));
6558         if (!adjacency_generated)
6559         {
6560             ERR("Couldn't allocate memory for adjacency_generated.\n");
6561             hr = E_OUTOFMEMORY;
6562             goto cleanup;
6563         }
6564         hr = mesh->lpVtbl->GenerateAdjacency(mesh, DEFAULT_EPSILON, adjacency_generated);
6565         if (FAILED(hr))
6566         {
6567             ERR("Couldn't generate adjacency.\n");
6568             goto cleanup;
6569         }
6570         adjacency_ptr = adjacency_generated;
6571     }
6572
6573     /* Point representation says which vertices can be replaced. */
6574     point_reps = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*point_reps));
6575     if (!point_reps)
6576     {
6577         hr = E_OUTOFMEMORY;
6578         ERR("Couldn't allocate memory for point_reps.\n");
6579         goto cleanup;
6580     }
6581     hr = mesh->lpVtbl->ConvertAdjacencyToPointReps(mesh, adjacency_ptr, point_reps);
6582     if (FAILED(hr))
6583     {
6584         ERR("ConvertAdjacencyToPointReps failed.\n");
6585         goto cleanup;
6586     }
6587
6588     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, &indices);
6589     if (FAILED(hr))
6590     {
6591         ERR("Couldn't lock index buffer.\n");
6592         goto cleanup;
6593     }
6594
6595     hr = mesh->lpVtbl->LockAttributeBuffer(mesh, 0, &attributes);
6596     if (FAILED(hr))
6597     {
6598         ERR("Couldn't lock attribute buffer.\n");
6599         goto cleanup;
6600     }
6601     vertex_face_map = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*vertex_face_map));
6602     if (!vertex_face_map)
6603     {
6604         hr = E_OUTOFMEMORY;
6605         ERR("Couldn't allocate memory for vertex_face_map.\n");
6606         goto cleanup;
6607     }
6608     /* Build vertex face map, so that a vertex's face can be looked up. */
6609     for (i = 0; i < This->numfaces; i++)
6610     {
6611         DWORD j;
6612         for (j = 0; j < 3; j++)
6613         {
6614             DWORD index = read_ib(indices, indices_are_32bit, 3*i + j);
6615             vertex_face_map[index] = i;
6616         }
6617     }
6618
6619     if (flags & D3DXWELDEPSILONS_WELDPARTIALMATCHES)
6620     {
6621         hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (void**)&vertices);
6622         if (FAILED(hr))
6623         {
6624             ERR("Couldn't lock vertex buffer.\n");
6625             goto cleanup;
6626         }
6627         /* For each vertex that can be removed, compare its vertex components
6628          * with the vertex components from the vertex that can replace it. A
6629          * vertex is only fully replaced if all the components match and the
6630          * flag D3DXWELDEPSILONS_DONOTREMOVEVERTICES is not set, and they
6631          * belong to the same attribute group. Otherwise the vertex components
6632          * that are within epsilon are set to the same value.
6633          */
6634         for (i = 0; i < 3 * This->numfaces; i++)
6635         {
6636             D3DVERTEXELEMENT9 *decl_ptr;
6637             DWORD vertex_size = mesh->lpVtbl->GetNumBytesPerVertex(mesh);
6638             DWORD num_vertex_components;
6639             INT matches = 0;
6640             BOOL all_match;
6641             DWORD index = read_ib(indices, indices_are_32bit, i);
6642
6643             for (decl_ptr = This->cached_declaration, num_vertex_components = 0; decl_ptr->Stream != 0xFF; decl_ptr++, num_vertex_components++)
6644             {
6645                 BYTE *to = &vertices[vertex_size*index + decl_ptr->Offset];
6646                 BYTE *from = &vertices[vertex_size*point_reps[index] + decl_ptr->Offset];
6647                 FLOAT epsilon = get_component_epsilon(decl_ptr, epsilons);
6648
6649                 /* Don't weld self */
6650                 if (index == point_reps[index])
6651                 {
6652                     matches++;
6653                     continue;
6654                 }
6655
6656                 if (weld_component(to, from, decl_ptr->Type, epsilon))
6657                     matches++;
6658             }
6659
6660             all_match = (num_vertex_components == matches);
6661             if (all_match && !(flags & D3DXWELDEPSILONS_DONOTREMOVEVERTICES))
6662             {
6663                 DWORD to_face = vertex_face_map[index];
6664                 DWORD from_face = vertex_face_map[point_reps[index]];
6665                 if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6666                     continue;
6667                 write_ib(indices, indices_are_32bit, i, point_reps[index]);
6668             }
6669         }
6670         mesh->lpVtbl->UnlockVertexBuffer(mesh);
6671         vertices = NULL;
6672     }
6673     else if (flags & D3DXWELDEPSILONS_WELDALL)
6674     {
6675         for (i = 0; i < 3 * This->numfaces; i++)
6676         {
6677             DWORD index = read_ib(indices, indices_are_32bit, i);
6678             DWORD to_face = vertex_face_map[index];
6679             DWORD from_face = vertex_face_map[point_reps[index]];
6680             if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6681                 continue;
6682             write_ib(indices, indices_are_32bit, i, point_reps[index]);
6683         }
6684     }
6685     mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6686     attributes = NULL;
6687     mesh->lpVtbl->UnlockIndexBuffer(mesh);
6688     indices = NULL;
6689
6690     /* Compact mesh using OptimizeInplace */
6691     optimize_flags = D3DXMESHOPT_COMPACT;
6692     hr = mesh->lpVtbl->OptimizeInplace(mesh, optimize_flags, adjacency_ptr, adjacency_out, face_remap_out, vertex_remap_out);
6693     if (FAILED(hr))
6694     {
6695         ERR("Couldn't compact mesh.\n");
6696         goto cleanup;
6697     }
6698
6699     hr = D3D_OK;
6700 cleanup:
6701     HeapFree(GetProcessHeap(), 0, adjacency_generated);
6702     HeapFree(GetProcessHeap(), 0, point_reps);
6703     HeapFree(GetProcessHeap(), 0, vertex_face_map);
6704     if (attributes) mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6705     if (indices) mesh->lpVtbl->UnlockIndexBuffer(mesh);
6706     if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
6707     if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
6708
6709     return hr;
6710 }
6711
6712 /*************************************************************************
6713  * D3DXOptimizeFaces    (D3DX9_36.@)
6714  *
6715  * Re-orders the faces so the vertex cache is used optimally.
6716  *
6717  * PARAMS
6718  *   indices           [I] Pointer to an index buffer belonging to a mesh.
6719  *   num_faces         [I] Number of faces in the mesh.
6720  *   num_vertices      [I] Number of vertices in the mesh.
6721  *   indices_are_32bit [I] Specifies whether indices are 32- or 16-bit.
6722  *   face_remap        [I/O] The new order the faces should be drawn in.
6723  *
6724  * RETURNS
6725  *   Success: D3D_OK.
6726  *   Failure: D3DERR_INVALIDCALL.
6727  *
6728  * BUGS
6729  *   The face re-ordering does not use the vertex cache optimally.
6730  *
6731  */
6732 HRESULT WINAPI D3DXOptimizeFaces(LPCVOID indices,
6733                                  UINT num_faces,
6734                                  UINT num_vertices,
6735                                  BOOL indices_are_32bit,
6736                                  DWORD *face_remap)
6737 {
6738     UINT i;
6739     UINT j = num_faces - 1;
6740     UINT limit_16_bit = 2 << 15; /* According to MSDN */
6741     HRESULT hr = D3D_OK;
6742
6743     FIXME("(%p, %u, %u, %s, %p): semi-stub. Face order will not be optimal.\n",
6744           indices, num_faces, num_vertices,
6745           indices_are_32bit ? "TRUE" : "FALSE", face_remap);
6746
6747     if (!indices_are_32bit && num_faces >= limit_16_bit)
6748     {
6749         WARN("Number of faces must be less than %d when using 16-bit indices.\n",
6750              limit_16_bit);
6751         hr = D3DERR_INVALIDCALL;
6752         goto error;
6753     }
6754
6755     if (!face_remap)
6756     {
6757         WARN("Face remap pointer is NULL.\n");
6758         hr = D3DERR_INVALIDCALL;
6759         goto error;
6760     }
6761
6762     /* The faces are drawn in reverse order for simple meshes. This ordering
6763      * is not optimal for complicated meshes, but will not break anything
6764      * either. The ordering should be changed to take advantage of the vertex
6765      * cache on the graphics card.
6766      *
6767      * TODO Re-order to take advantage of vertex cache.
6768      */
6769     for (i = 0; i < num_faces; i++)
6770     {
6771         face_remap[i] = j--;
6772     }
6773
6774     return D3D_OK;
6775
6776 error:
6777     return hr;
6778 }