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 D3DXFrameDestroy(LPD3DXFRAME frame, LPD3DXALLOCATEHIERARCHY alloc_hier)
3822 {
3823     HRESULT hr;
3824     BOOL last = FALSE;
3825
3826     TRACE("(%p, %p)\n", frame, alloc_hier);
3827
3828     if (!frame || !alloc_hier)
3829         return D3DERR_INVALIDCALL;
3830
3831     while (!last) {
3832         D3DXMESHCONTAINER *container;
3833         D3DXFRAME *current_frame;
3834
3835         if (frame->pFrameSibling) {
3836             current_frame = frame->pFrameSibling;
3837             frame->pFrameSibling = current_frame->pFrameSibling;
3838             current_frame->pFrameSibling = NULL;
3839         } else {
3840             current_frame = frame;
3841             last = TRUE;
3842         }
3843
3844         if (current_frame->pFrameFirstChild) {
3845             hr = D3DXFrameDestroy(current_frame->pFrameFirstChild, alloc_hier);
3846             if (FAILED(hr)) return hr;
3847             current_frame->pFrameFirstChild = NULL;
3848         }
3849
3850         container = current_frame->pMeshContainer;
3851         while (container) {
3852             D3DXMESHCONTAINER *next_container = container->pNextMeshContainer;
3853             hr = alloc_hier->lpVtbl->DestroyMeshContainer(alloc_hier, container);
3854             if (FAILED(hr)) return hr;
3855             container = next_container;
3856         }
3857         hr = alloc_hier->lpVtbl->DestroyFrame(alloc_hier, current_frame);
3858         if (FAILED(hr)) return hr;
3859     }
3860     return D3D_OK;
3861 }
3862
3863 HRESULT WINAPI D3DXLoadMeshFromXA(LPCSTR filename,
3864                                   DWORD options,
3865                                   LPDIRECT3DDEVICE9 device,
3866                                   LPD3DXBUFFER *adjacency,
3867                                   LPD3DXBUFFER *materials,
3868                                   LPD3DXBUFFER *effect_instances,
3869                                   DWORD *num_materials,
3870                                   LPD3DXMESH *mesh)
3871 {
3872     HRESULT hr;
3873     int len;
3874     LPWSTR filenameW;
3875
3876     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_a(filename), options,
3877           device, adjacency, materials, effect_instances, num_materials, mesh);
3878
3879     if (!filename)
3880         return D3DERR_INVALIDCALL;
3881
3882     len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
3883     filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
3884     if (!filenameW) return E_OUTOFMEMORY;
3885     MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
3886
3887     hr = D3DXLoadMeshFromXW(filenameW, options, device, adjacency, materials,
3888                             effect_instances, num_materials, mesh);
3889     HeapFree(GetProcessHeap(), 0, filenameW);
3890
3891     return hr;
3892 }
3893
3894 HRESULT WINAPI D3DXLoadMeshFromXW(LPCWSTR filename,
3895                                   DWORD options,
3896                                   LPDIRECT3DDEVICE9 device,
3897                                   LPD3DXBUFFER *adjacency,
3898                                   LPD3DXBUFFER *materials,
3899                                   LPD3DXBUFFER *effect_instances,
3900                                   DWORD *num_materials,
3901                                   LPD3DXMESH *mesh)
3902 {
3903     HRESULT hr;
3904     DWORD size;
3905     LPVOID buffer;
3906
3907     TRACE("(%s, %x, %p, %p, %p, %p, %p, %p)\n", debugstr_w(filename), options,
3908           device, adjacency, materials, effect_instances, num_materials, mesh);
3909
3910     if (!filename)
3911         return D3DERR_INVALIDCALL;
3912
3913     hr = map_view_of_file(filename, &buffer, &size);
3914     if (FAILED(hr))
3915         return D3DXERR_INVALIDDATA;
3916
3917     hr = D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3918             materials, effect_instances, num_materials, mesh);
3919
3920     UnmapViewOfFile(buffer);
3921
3922     return hr;
3923 }
3924
3925 HRESULT WINAPI D3DXLoadMeshFromXResource(HMODULE module,
3926                                          LPCSTR name,
3927                                          LPCSTR type,
3928                                          DWORD options,
3929                                          LPDIRECT3DDEVICE9 device,
3930                                          LPD3DXBUFFER *adjacency,
3931                                          LPD3DXBUFFER *materials,
3932                                          LPD3DXBUFFER *effect_instances,
3933                                          DWORD *num_materials,
3934                                          LPD3DXMESH *mesh)
3935 {
3936     HRESULT hr;
3937     HRSRC resinfo;
3938     DWORD size;
3939     LPVOID buffer;
3940
3941     TRACE("(%p, %s, %s, %x, %p, %p, %p, %p, %p, %p)\n",
3942           module, debugstr_a(name), debugstr_a(type), options, device,
3943           adjacency, materials, effect_instances, num_materials, mesh);
3944
3945     resinfo = FindResourceA(module, name, type);
3946     if (!resinfo) return D3DXERR_INVALIDDATA;
3947
3948     hr = load_resource_into_memory(module, resinfo, &buffer, &size);
3949     if (FAILED(hr)) return D3DXERR_INVALIDDATA;
3950
3951     return D3DXLoadMeshFromXInMemory(buffer, size, options, device, adjacency,
3952             materials, effect_instances, num_materials, mesh);
3953 }
3954
3955 struct mesh_container
3956 {
3957     struct list entry;
3958     ID3DXMesh *mesh;
3959     ID3DXBuffer *adjacency;
3960     ID3DXBuffer *materials;
3961     ID3DXBuffer *effects;
3962     DWORD num_materials;
3963     D3DXMATRIX transform;
3964 };
3965
3966 static HRESULT parse_frame(IDirectXFileData *filedata,
3967                            DWORD options,
3968                            LPDIRECT3DDEVICE9 device,
3969                            const D3DXMATRIX *parent_transform,
3970                            struct list *container_list,
3971                            DWORD provide_flags)
3972 {
3973     HRESULT hr;
3974     D3DXMATRIX transform = *parent_transform;
3975     IDirectXFileData *child;
3976     const GUID *type;
3977
3978     while (SUCCEEDED(hr = get_next_child(filedata, &child, &type)))
3979     {
3980         if (IsEqualGUID(type, &TID_D3DRMMesh)) {
3981             struct mesh_container *container = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container));
3982             if (!container)  {
3983                 hr = E_OUTOFMEMORY;
3984                 break;
3985             }
3986             list_add_tail(container_list, &container->entry);
3987             container->transform = transform;
3988
3989             hr = load_skin_mesh_from_xof(child, options, device,
3990                     (provide_flags & PROVIDE_ADJACENCY) ? &container->adjacency : NULL,
3991                     (provide_flags & PROVIDE_MATERIALS) ? &container->materials : NULL,
3992                     NULL, &container->num_materials, NULL, &container->mesh);
3993         } else if (IsEqualGUID(type, &TID_D3DRMFrameTransformMatrix)) {
3994             D3DXMATRIX new_transform;
3995             hr = parse_transform_matrix(child, &new_transform);
3996             D3DXMatrixMultiply(&transform, &transform, &new_transform);
3997         } else if (IsEqualGUID(type, &TID_D3DRMFrame)) {
3998             hr = parse_frame(child, options, device, &transform, container_list, provide_flags);
3999         }
4000         if (FAILED(hr)) break;
4001     }
4002     return hr == DXFILEERR_NOMOREOBJECTS ? D3D_OK : hr;
4003 }
4004
4005 HRESULT WINAPI D3DXLoadMeshFromXInMemory(LPCVOID memory,
4006                                          DWORD memory_size,
4007                                          DWORD options,
4008                                          LPDIRECT3DDEVICE9 device,
4009                                          LPD3DXBUFFER *adjacency_out,
4010                                          LPD3DXBUFFER *materials_out,
4011                                          LPD3DXBUFFER *effects_out,
4012                                          DWORD *num_materials_out,
4013                                          LPD3DXMESH *mesh_out)
4014 {
4015     HRESULT hr;
4016     IDirectXFile *dxfile = NULL;
4017     IDirectXFileEnumObject *enumobj = NULL;
4018     IDirectXFileData *filedata = NULL;
4019     DXFILELOADMEMORY source;
4020     ID3DXBuffer *materials = NULL;
4021     ID3DXBuffer *effects = NULL;
4022     ID3DXBuffer *adjacency = NULL;
4023     struct list container_list = LIST_INIT(container_list);
4024     struct mesh_container *container_ptr, *next_container_ptr;
4025     DWORD num_materials;
4026     DWORD num_faces, num_vertices;
4027     D3DXMATRIX identity;
4028     int i;
4029     DWORD provide_flags = 0;
4030     DWORD fvf;
4031     ID3DXMesh *concat_mesh = NULL;
4032     D3DVERTEXELEMENT9 concat_decl[MAX_FVF_DECL_SIZE];
4033     BYTE *concat_vertices = NULL;
4034     void *concat_indices = NULL;
4035     DWORD index_offset;
4036     DWORD concat_vertex_size;
4037
4038     TRACE("(%p, %u, %x, %p, %p, %p, %p, %p, %p)\n", memory, memory_size, options,
4039           device, adjacency_out, materials_out, effects_out, num_materials_out, mesh_out);
4040
4041     if (!memory || !memory_size || !device || !mesh_out)
4042         return D3DERR_INVALIDCALL;
4043
4044     hr = DirectXFileCreate(&dxfile);
4045     if (FAILED(hr)) goto cleanup;
4046
4047     hr = IDirectXFile_RegisterTemplates(dxfile, D3DRM_XTEMPLATES, D3DRM_XTEMPLATE_BYTES);
4048     if (FAILED(hr)) goto cleanup;
4049
4050     source.lpMemory = (void*)memory;
4051     source.dSize = memory_size;
4052     hr = IDirectXFile_CreateEnumObject(dxfile, &source, DXFILELOAD_FROMMEMORY, &enumobj);
4053     if (FAILED(hr)) goto cleanup;
4054
4055     D3DXMatrixIdentity(&identity);
4056     if (adjacency_out) provide_flags |= PROVIDE_ADJACENCY;
4057     if (materials_out || effects_out) provide_flags |= PROVIDE_MATERIALS;
4058
4059     while (SUCCEEDED(hr = IDirectXFileEnumObject_GetNextDataObject(enumobj, &filedata)))
4060     {
4061         const GUID *guid = NULL;
4062
4063         hr = IDirectXFileData_GetType(filedata, &guid);
4064         if (SUCCEEDED(hr)) {
4065             if (IsEqualGUID(guid, &TID_D3DRMMesh)) {
4066                 container_ptr = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*container_ptr));
4067                 if (!container_ptr) {
4068                     hr = E_OUTOFMEMORY;
4069                     goto cleanup;
4070                 }
4071                 list_add_tail(&container_list, &container_ptr->entry);
4072                 D3DXMatrixIdentity(&container_ptr->transform);
4073
4074                 hr = load_skin_mesh_from_xof(filedata, options, device,
4075                         (provide_flags & PROVIDE_ADJACENCY) ? &container_ptr->adjacency : NULL,
4076                         (provide_flags & PROVIDE_MATERIALS) ? &container_ptr->materials : NULL,
4077                         NULL, &container_ptr->num_materials, NULL, &container_ptr->mesh);
4078             } else if (IsEqualGUID(guid, &TID_D3DRMFrame)) {
4079                 hr = parse_frame(filedata, options, device, &identity, &container_list, provide_flags);
4080             }
4081             if (FAILED(hr)) goto cleanup;
4082         }
4083         IDirectXFileData_Release(filedata);
4084         filedata = NULL;
4085         if (FAILED(hr))
4086             goto cleanup;
4087     }
4088     if (hr != DXFILEERR_NOMOREOBJECTS)
4089         goto cleanup;
4090
4091     IDirectXFileEnumObject_Release(enumobj);
4092     enumobj = NULL;
4093     IDirectXFile_Release(dxfile);
4094     dxfile = NULL;
4095
4096     if (list_empty(&container_list)) {
4097         hr = E_FAIL;
4098         goto cleanup;
4099     }
4100
4101     fvf = D3DFVF_XYZ;
4102     num_faces = 0;
4103     num_vertices = 0;
4104     num_materials = 0;
4105     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4106     {
4107         ID3DXMesh *mesh = container_ptr->mesh;
4108         fvf |= mesh->lpVtbl->GetFVF(mesh);
4109         num_faces += mesh->lpVtbl->GetNumFaces(mesh);
4110         num_vertices += mesh->lpVtbl->GetNumVertices(mesh);
4111         num_materials += container_ptr->num_materials;
4112     }
4113
4114     hr = D3DXCreateMeshFVF(num_faces, num_vertices, options, fvf, device, &concat_mesh);
4115     if (FAILED(hr)) goto cleanup;
4116
4117     hr = concat_mesh->lpVtbl->GetDeclaration(concat_mesh, concat_decl);
4118     if (FAILED(hr)) goto cleanup;
4119
4120     concat_vertex_size = D3DXGetDeclVertexSize(concat_decl, 0);
4121
4122     hr = concat_mesh->lpVtbl->LockVertexBuffer(concat_mesh, 0, (void**)&concat_vertices);
4123     if (FAILED(hr)) goto cleanup;
4124
4125     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4126     {
4127         D3DVERTEXELEMENT9 mesh_decl[MAX_FVF_DECL_SIZE];
4128         ID3DXMesh *mesh = container_ptr->mesh;
4129         DWORD num_mesh_vertices = mesh->lpVtbl->GetNumVertices(mesh);
4130         DWORD mesh_vertex_size;
4131         const BYTE *mesh_vertices;
4132
4133         hr = mesh->lpVtbl->GetDeclaration(mesh, mesh_decl);
4134         if (FAILED(hr)) goto cleanup;
4135
4136         mesh_vertex_size = D3DXGetDeclVertexSize(mesh_decl, 0);
4137
4138         hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_vertices);
4139         if (FAILED(hr)) goto cleanup;
4140
4141         for (i = 0; i < num_mesh_vertices; i++) {
4142             int j;
4143             int k = 1;
4144
4145             D3DXVec3TransformCoord((D3DXVECTOR3*)concat_vertices,
4146                                    (D3DXVECTOR3*)mesh_vertices,
4147                                    &container_ptr->transform);
4148             for (j = 1; concat_decl[j].Stream != 0xff; j++)
4149             {
4150                 if (concat_decl[j].Usage == mesh_decl[k].Usage &&
4151                     concat_decl[j].UsageIndex == mesh_decl[k].UsageIndex)
4152                 {
4153                     if (concat_decl[j].Usage == D3DDECLUSAGE_NORMAL) {
4154                         D3DXVec3TransformCoord((D3DXVECTOR3*)(concat_vertices + concat_decl[j].Offset),
4155                                                (D3DXVECTOR3*)(mesh_vertices + mesh_decl[k].Offset),
4156                                                &container_ptr->transform);
4157                     } else {
4158                         memcpy(concat_vertices + concat_decl[j].Offset,
4159                                mesh_vertices + mesh_decl[k].Offset,
4160                                d3dx_decltype_size[mesh_decl[k].Type]);
4161                     }
4162                     k++;
4163                 }
4164             }
4165             mesh_vertices += mesh_vertex_size;
4166             concat_vertices += concat_vertex_size;
4167         }
4168
4169         mesh->lpVtbl->UnlockVertexBuffer(mesh);
4170     }
4171
4172     concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
4173     concat_vertices = NULL;
4174
4175     hr = concat_mesh->lpVtbl->LockIndexBuffer(concat_mesh, 0, &concat_indices);
4176     if (FAILED(hr)) goto cleanup;
4177
4178     index_offset = 0;
4179     LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4180     {
4181         ID3DXMesh *mesh = container_ptr->mesh;
4182         const void *mesh_indices;
4183         DWORD num_mesh_faces = mesh->lpVtbl->GetNumFaces(mesh);
4184         int i;
4185
4186         hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_READONLY, (void**)&mesh_indices);
4187         if (FAILED(hr)) goto cleanup;
4188
4189         if (options & D3DXMESH_32BIT) {
4190             DWORD *dest = concat_indices;
4191             const DWORD *src = mesh_indices;
4192             for (i = 0; i < num_mesh_faces * 3; i++)
4193                 *dest++ = index_offset + *src++;
4194             concat_indices = dest;
4195         } else {
4196             WORD *dest = concat_indices;
4197             const WORD *src = mesh_indices;
4198             for (i = 0; i < num_mesh_faces * 3; i++)
4199                 *dest++ = index_offset + *src++;
4200             concat_indices = dest;
4201         }
4202         mesh->lpVtbl->UnlockIndexBuffer(mesh);
4203
4204         index_offset += num_mesh_faces * 3;
4205     }
4206
4207     concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
4208     concat_indices = NULL;
4209
4210     if (num_materials) {
4211         DWORD *concat_attrib_buffer = NULL;
4212         DWORD offset = 0;
4213
4214         hr = concat_mesh->lpVtbl->LockAttributeBuffer(concat_mesh, 0, &concat_attrib_buffer);
4215         if (FAILED(hr)) goto cleanup;
4216
4217         LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4218         {
4219             ID3DXMesh *mesh = container_ptr->mesh;
4220             const DWORD *mesh_attrib_buffer = NULL;
4221             DWORD count = mesh->lpVtbl->GetNumFaces(mesh);
4222
4223             hr = mesh->lpVtbl->LockAttributeBuffer(mesh, D3DLOCK_READONLY, (DWORD**)&mesh_attrib_buffer);
4224             if (FAILED(hr)) {
4225                 concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
4226                 goto cleanup;
4227             }
4228
4229             while (count--)
4230                 *concat_attrib_buffer++ = offset + *mesh_attrib_buffer++;
4231
4232             mesh->lpVtbl->UnlockAttributeBuffer(mesh);
4233             offset += container_ptr->num_materials;
4234         }
4235         concat_mesh->lpVtbl->UnlockAttributeBuffer(concat_mesh);
4236     }
4237
4238     if (materials_out || effects_out) {
4239         D3DXMATERIAL *out_ptr;
4240         if (!num_materials) {
4241             /* create default material */
4242             hr = D3DXCreateBuffer(sizeof(D3DXMATERIAL), &materials);
4243             if (FAILED(hr)) goto cleanup;
4244
4245             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
4246             out_ptr->MatD3D.Diffuse.r = 0.5f;
4247             out_ptr->MatD3D.Diffuse.g = 0.5f;
4248             out_ptr->MatD3D.Diffuse.b = 0.5f;
4249             out_ptr->MatD3D.Specular.r = 0.5f;
4250             out_ptr->MatD3D.Specular.g = 0.5f;
4251             out_ptr->MatD3D.Specular.b = 0.5f;
4252             /* D3DXCreateBuffer initializes the rest to zero */
4253         } else {
4254             DWORD buffer_size = num_materials * sizeof(D3DXMATERIAL);
4255             char *strings_out_ptr;
4256
4257             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4258             {
4259                 if (container_ptr->materials) {
4260                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
4261                     for (i = 0; i < container_ptr->num_materials; i++)
4262                     {
4263                         if (in_ptr->pTextureFilename)
4264                             buffer_size += strlen(in_ptr->pTextureFilename) + 1;
4265                         in_ptr++;
4266                     }
4267                 }
4268             }
4269
4270             hr = D3DXCreateBuffer(buffer_size, &materials);
4271             if (FAILED(hr)) goto cleanup;
4272             out_ptr = ID3DXBuffer_GetBufferPointer(materials);
4273             strings_out_ptr = (char*)(out_ptr + num_materials);
4274
4275             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4276             {
4277                 if (container_ptr->materials) {
4278                     const D3DXMATERIAL *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->materials);
4279                     for (i = 0; i < container_ptr->num_materials; i++)
4280                     {
4281                         out_ptr->MatD3D = in_ptr->MatD3D;
4282                         if (in_ptr->pTextureFilename) {
4283                             out_ptr->pTextureFilename = strings_out_ptr;
4284                             strcpy(out_ptr->pTextureFilename, in_ptr->pTextureFilename);
4285                             strings_out_ptr += strlen(in_ptr->pTextureFilename) + 1;
4286                         }
4287                         in_ptr++;
4288                         out_ptr++;
4289                     }
4290                 }
4291             }
4292         }
4293     }
4294     if (!num_materials)
4295         num_materials = 1;
4296
4297     if (effects_out) {
4298         generate_effects(materials, num_materials, &effects);
4299         if (!materials_out) {
4300             ID3DXBuffer_Release(materials);
4301             materials = NULL;
4302         }
4303     }
4304
4305     if (adjacency_out) {
4306         if (!list_next(&container_list, list_head(&container_list))) {
4307             container_ptr = LIST_ENTRY(list_head(&container_list), struct mesh_container, entry);
4308             adjacency = container_ptr->adjacency;
4309             container_ptr->adjacency = NULL;
4310         } else {
4311             DWORD offset = 0;
4312             DWORD *out_ptr;
4313
4314             hr = D3DXCreateBuffer(num_faces * 3 * sizeof(DWORD), &adjacency);
4315             if (FAILED(hr)) goto cleanup;
4316
4317             out_ptr = ID3DXBuffer_GetBufferPointer(adjacency);
4318             LIST_FOR_EACH_ENTRY(container_ptr, &container_list, struct mesh_container, entry)
4319             {
4320                 DWORD *in_ptr = ID3DXBuffer_GetBufferPointer(container_ptr->adjacency);
4321                 int count = 3 * container_ptr->mesh->lpVtbl->GetNumFaces(container_ptr->mesh);
4322
4323                 for (i = 0; i < count; i++)
4324                     *out_ptr++ = offset + *in_ptr++;
4325
4326                 offset += count;
4327             }
4328         }
4329     }
4330
4331     *mesh_out = concat_mesh;
4332     if (adjacency_out) *adjacency_out = adjacency;
4333     if (materials_out) *materials_out = materials;
4334     if (effects_out) *effects_out = effects;
4335     if (num_materials_out) *num_materials_out = num_materials;
4336
4337     hr = D3D_OK;
4338 cleanup:
4339     if (concat_indices) concat_mesh->lpVtbl->UnlockIndexBuffer(concat_mesh);
4340     if (concat_vertices) concat_mesh->lpVtbl->UnlockVertexBuffer(concat_mesh);
4341     if (filedata) IDirectXFileData_Release(filedata);
4342     if (enumobj) IDirectXFileEnumObject_Release(enumobj);
4343     if (dxfile) IDirectXFile_Release(dxfile);
4344     if (FAILED(hr)) {
4345         if (concat_mesh) IUnknown_Release(concat_mesh);
4346         if (materials) ID3DXBuffer_Release(materials);
4347         if (effects) ID3DXBuffer_Release(effects);
4348         if (adjacency) ID3DXBuffer_Release(adjacency);
4349     }
4350     LIST_FOR_EACH_ENTRY_SAFE(container_ptr, next_container_ptr, &container_list, struct mesh_container, entry)
4351     {
4352         if (container_ptr->mesh) IUnknown_Release(container_ptr->mesh);
4353         if (container_ptr->adjacency) ID3DXBuffer_Release(container_ptr->adjacency);
4354         if (container_ptr->materials) ID3DXBuffer_Release(container_ptr->materials);
4355         if (container_ptr->effects) ID3DXBuffer_Release(container_ptr->effects);
4356         HeapFree(GetProcessHeap(), 0, container_ptr);
4357     }
4358     return hr;
4359 }
4360
4361 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
4362                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4363 {
4364     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
4365
4366     return E_NOTIMPL;
4367 }
4368
4369 struct vertex
4370 {
4371     D3DXVECTOR3 position;
4372     D3DXVECTOR3 normal;
4373 };
4374
4375 typedef WORD face[3];
4376
4377 struct sincos_table
4378 {
4379     float *sin;
4380     float *cos;
4381 };
4382
4383 static void free_sincos_table(struct sincos_table *sincos_table)
4384 {
4385     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
4386     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
4387 }
4388
4389 /* pre compute sine and cosine tables; caller must free */
4390 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
4391 {
4392     float angle;
4393     int i;
4394
4395     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
4396     if (!sincos_table->sin)
4397     {
4398         return FALSE;
4399     }
4400     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
4401     if (!sincos_table->cos)
4402     {
4403         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
4404         return FALSE;
4405     }
4406
4407     angle = angle_start;
4408     for (i = 0; i < n; i++)
4409     {
4410         sincos_table->sin[i] = sin(angle);
4411         sincos_table->cos[i] = cos(angle);
4412         angle += angle_step;
4413     }
4414
4415     return TRUE;
4416 }
4417
4418 static WORD vertex_index(UINT slices, int slice, int stack)
4419 {
4420     return stack*slices+slice+1;
4421 }
4422
4423 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
4424                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4425 {
4426     DWORD number_of_vertices, number_of_faces;
4427     HRESULT hr;
4428     ID3DXMesh *sphere;
4429     struct vertex *vertices;
4430     face *faces;
4431     float phi_step, phi_start;
4432     struct sincos_table phi;
4433     float theta_step, theta, sin_theta, cos_theta;
4434     DWORD vertex, face;
4435     int slice, stack;
4436
4437     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
4438
4439     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
4440     {
4441         return D3DERR_INVALIDCALL;
4442     }
4443
4444     if (adjacency)
4445     {
4446         FIXME("Case of adjacency != NULL not implemented.\n");
4447         return E_NOTIMPL;
4448     }
4449
4450     number_of_vertices = 2 + slices * (stacks-1);
4451     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
4452
4453     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4454                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
4455     if (FAILED(hr))
4456     {
4457         return hr;
4458     }
4459
4460     hr = sphere->lpVtbl->LockVertexBuffer(sphere, 0, (LPVOID *)&vertices);
4461     if (FAILED(hr))
4462     {
4463         sphere->lpVtbl->Release(sphere);
4464         return hr;
4465     }
4466
4467     hr = sphere->lpVtbl->LockIndexBuffer(sphere, 0, (LPVOID *)&faces);
4468     if (FAILED(hr))
4469     {
4470         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4471         sphere->lpVtbl->Release(sphere);
4472         return hr;
4473     }
4474
4475     /* phi = angle on xz plane wrt z axis */
4476     phi_step = -2 * M_PI / slices;
4477     phi_start = M_PI / 2;
4478
4479     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
4480     {
4481         sphere->lpVtbl->UnlockIndexBuffer(sphere);
4482         sphere->lpVtbl->UnlockVertexBuffer(sphere);
4483         sphere->lpVtbl->Release(sphere);
4484         return E_OUTOFMEMORY;
4485     }
4486
4487     /* theta = angle on xy plane wrt x axis */
4488     theta_step = M_PI / stacks;
4489     theta = theta_step;
4490
4491     vertex = 0;
4492     face = 0;
4493
4494     vertices[vertex].normal.x = 0.0f;
4495     vertices[vertex].normal.y = 0.0f;
4496     vertices[vertex].normal.z = 1.0f;
4497     vertices[vertex].position.x = 0.0f;
4498     vertices[vertex].position.y = 0.0f;
4499     vertices[vertex].position.z = radius;
4500     vertex++;
4501
4502     for (stack = 0; stack < stacks - 1; stack++)
4503     {
4504         sin_theta = sin(theta);
4505         cos_theta = cos(theta);
4506
4507         for (slice = 0; slice < slices; slice++)
4508         {
4509             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
4510             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
4511             vertices[vertex].normal.z = cos_theta;
4512             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
4513             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
4514             vertices[vertex].position.z = radius * cos_theta;
4515             vertex++;
4516
4517             if (slice > 0)
4518             {
4519                 if (stack == 0)
4520                 {
4521                     /* top stack is triangle fan */
4522                     faces[face][0] = 0;
4523                     faces[face][1] = slice + 1;
4524                     faces[face][2] = slice;
4525                     face++;
4526                 }
4527                 else
4528                 {
4529                     /* stacks in between top and bottom are quad strips */
4530                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4531                     faces[face][1] = vertex_index(slices, slice, stack-1);
4532                     faces[face][2] = vertex_index(slices, slice-1, stack);
4533                     face++;
4534
4535                     faces[face][0] = vertex_index(slices, slice, stack-1);
4536                     faces[face][1] = vertex_index(slices, slice, stack);
4537                     faces[face][2] = vertex_index(slices, slice-1, stack);
4538                     face++;
4539                 }
4540             }
4541         }
4542
4543         theta += theta_step;
4544
4545         if (stack == 0)
4546         {
4547             faces[face][0] = 0;
4548             faces[face][1] = 1;
4549             faces[face][2] = slice;
4550             face++;
4551         }
4552         else
4553         {
4554             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4555             faces[face][1] = vertex_index(slices, 0, stack-1);
4556             faces[face][2] = vertex_index(slices, slice-1, stack);
4557             face++;
4558
4559             faces[face][0] = vertex_index(slices, 0, stack-1);
4560             faces[face][1] = vertex_index(slices, 0, stack);
4561             faces[face][2] = vertex_index(slices, slice-1, stack);
4562             face++;
4563         }
4564     }
4565
4566     vertices[vertex].position.x = 0.0f;
4567     vertices[vertex].position.y = 0.0f;
4568     vertices[vertex].position.z = -radius;
4569     vertices[vertex].normal.x = 0.0f;
4570     vertices[vertex].normal.y = 0.0f;
4571     vertices[vertex].normal.z = -1.0f;
4572
4573     /* bottom stack is triangle fan */
4574     for (slice = 1; slice < slices; slice++)
4575     {
4576         faces[face][0] = vertex_index(slices, slice-1, stack-1);
4577         faces[face][1] = vertex_index(slices, slice, stack-1);
4578         faces[face][2] = vertex;
4579         face++;
4580     }
4581
4582     faces[face][0] = vertex_index(slices, slice-1, stack-1);
4583     faces[face][1] = vertex_index(slices, 0, stack-1);
4584     faces[face][2] = vertex;
4585
4586     free_sincos_table(&phi);
4587     sphere->lpVtbl->UnlockIndexBuffer(sphere);
4588     sphere->lpVtbl->UnlockVertexBuffer(sphere);
4589     *mesh = sphere;
4590
4591     return D3D_OK;
4592 }
4593
4594 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
4595                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
4596 {
4597     DWORD number_of_vertices, number_of_faces;
4598     HRESULT hr;
4599     ID3DXMesh *cylinder;
4600     struct vertex *vertices;
4601     face *faces;
4602     float theta_step, theta_start;
4603     struct sincos_table theta;
4604     float delta_radius, radius, radius_step;
4605     float z, z_step, z_normal;
4606     DWORD vertex, face;
4607     int slice, stack;
4608
4609     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
4610
4611     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
4612     {
4613         return D3DERR_INVALIDCALL;
4614     }
4615
4616     if (adjacency)
4617     {
4618         FIXME("Case of adjacency != NULL not implemented.\n");
4619         return E_NOTIMPL;
4620     }
4621
4622     number_of_vertices = 2 + (slices * (3 + stacks));
4623     number_of_faces = 2 * slices + stacks * (2 * slices);
4624
4625     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
4626                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
4627     if (FAILED(hr))
4628     {
4629         return hr;
4630     }
4631
4632     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, 0, (LPVOID *)&vertices);
4633     if (FAILED(hr))
4634     {
4635         cylinder->lpVtbl->Release(cylinder);
4636         return hr;
4637     }
4638
4639     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, 0, (LPVOID *)&faces);
4640     if (FAILED(hr))
4641     {
4642         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4643         cylinder->lpVtbl->Release(cylinder);
4644         return hr;
4645     }
4646
4647     /* theta = angle on xy plane wrt x axis */
4648     theta_step = -2 * M_PI / slices;
4649     theta_start = M_PI / 2;
4650
4651     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
4652     {
4653         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4654         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4655         cylinder->lpVtbl->Release(cylinder);
4656         return E_OUTOFMEMORY;
4657     }
4658
4659     vertex = 0;
4660     face = 0;
4661
4662     delta_radius = radius1 - radius2;
4663     radius = radius1;
4664     radius_step = delta_radius / stacks;
4665
4666     z = -length / 2;
4667     z_step = length / stacks;
4668     z_normal = delta_radius / length;
4669     if (isnan(z_normal))
4670     {
4671         z_normal = 0.0f;
4672     }
4673
4674     vertices[vertex].normal.x = 0.0f;
4675     vertices[vertex].normal.y = 0.0f;
4676     vertices[vertex].normal.z = -1.0f;
4677     vertices[vertex].position.x = 0.0f;
4678     vertices[vertex].position.y = 0.0f;
4679     vertices[vertex++].position.z = z;
4680
4681     for (slice = 0; slice < slices; slice++, vertex++)
4682     {
4683         vertices[vertex].normal.x = 0.0f;
4684         vertices[vertex].normal.y = 0.0f;
4685         vertices[vertex].normal.z = -1.0f;
4686         vertices[vertex].position.x = radius * theta.cos[slice];
4687         vertices[vertex].position.y = radius * theta.sin[slice];
4688         vertices[vertex].position.z = z;
4689
4690         if (slice > 0)
4691         {
4692             faces[face][0] = 0;
4693             faces[face][1] = slice;
4694             faces[face++][2] = slice + 1;
4695         }
4696     }
4697
4698     faces[face][0] = 0;
4699     faces[face][1] = slice;
4700     faces[face++][2] = 1;
4701
4702     for (stack = 1; stack <= stacks+1; stack++)
4703     {
4704         for (slice = 0; slice < slices; slice++, vertex++)
4705         {
4706             vertices[vertex].normal.x = theta.cos[slice];
4707             vertices[vertex].normal.y = theta.sin[slice];
4708             vertices[vertex].normal.z = z_normal;
4709             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
4710             vertices[vertex].position.x = radius * theta.cos[slice];
4711             vertices[vertex].position.y = radius * theta.sin[slice];
4712             vertices[vertex].position.z = z;
4713
4714             if (stack > 1 && slice > 0)
4715             {
4716                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
4717                 faces[face][1] = vertex_index(slices, slice-1, stack);
4718                 faces[face++][2] = vertex_index(slices, slice, stack-1);
4719
4720                 faces[face][0] = vertex_index(slices, slice, stack-1);
4721                 faces[face][1] = vertex_index(slices, slice-1, stack);
4722                 faces[face++][2] = vertex_index(slices, slice, stack);
4723             }
4724         }
4725
4726         if (stack > 1)
4727         {
4728             faces[face][0] = vertex_index(slices, slice-1, stack-1);
4729             faces[face][1] = vertex_index(slices, slice-1, stack);
4730             faces[face++][2] = vertex_index(slices, 0, stack-1);
4731
4732             faces[face][0] = vertex_index(slices, 0, stack-1);
4733             faces[face][1] = vertex_index(slices, slice-1, stack);
4734             faces[face++][2] = vertex_index(slices, 0, stack);
4735         }
4736
4737         if (stack < stacks + 1)
4738         {
4739             z += z_step;
4740             radius -= radius_step;
4741         }
4742     }
4743
4744     for (slice = 0; slice < slices; slice++, vertex++)
4745     {
4746         vertices[vertex].normal.x = 0.0f;
4747         vertices[vertex].normal.y = 0.0f;
4748         vertices[vertex].normal.z = 1.0f;
4749         vertices[vertex].position.x = radius * theta.cos[slice];
4750         vertices[vertex].position.y = radius * theta.sin[slice];
4751         vertices[vertex].position.z = z;
4752
4753         if (slice > 0)
4754         {
4755             faces[face][0] = vertex_index(slices, slice-1, stack);
4756             faces[face][1] = number_of_vertices - 1;
4757             faces[face++][2] = vertex_index(slices, slice, stack);
4758         }
4759     }
4760
4761     vertices[vertex].position.x = 0.0f;
4762     vertices[vertex].position.y = 0.0f;
4763     vertices[vertex].position.z = z;
4764     vertices[vertex].normal.x = 0.0f;
4765     vertices[vertex].normal.y = 0.0f;
4766     vertices[vertex].normal.z = 1.0f;
4767
4768     faces[face][0] = vertex_index(slices, slice-1, stack);
4769     faces[face][1] = number_of_vertices - 1;
4770     faces[face][2] = vertex_index(slices, 0, stack);
4771
4772     free_sincos_table(&theta);
4773     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
4774     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
4775     *mesh = cylinder;
4776
4777     return D3D_OK;
4778 }
4779
4780 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
4781 {
4782     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
4783
4784     return E_NOTIMPL;
4785 }
4786
4787 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
4788                                HDC hdc, LPCSTR text,
4789                                FLOAT deviation, FLOAT extrusion,
4790                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
4791                                LPGLYPHMETRICSFLOAT glyphmetrics)
4792 {
4793     HRESULT hr;
4794     int len;
4795     LPWSTR textW;
4796
4797     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
4798           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
4799
4800     if (!text)
4801         return D3DERR_INVALIDCALL;
4802
4803     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
4804     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
4805     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
4806
4807     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
4808                          mesh, adjacency, glyphmetrics);
4809     HeapFree(GetProcessHeap(), 0, textW);
4810
4811     return hr;
4812 }
4813
4814 enum pointtype {
4815     POINTTYPE_CURVE = 0,
4816     POINTTYPE_CORNER,
4817     POINTTYPE_CURVE_START,
4818     POINTTYPE_CURVE_END,
4819     POINTTYPE_CURVE_MIDDLE,
4820 };
4821
4822 struct point2d
4823 {
4824     D3DXVECTOR2 pos;
4825     enum pointtype corner;
4826 };
4827
4828 struct dynamic_array
4829 {
4830     int count, capacity;
4831     void *items;
4832 };
4833
4834 /* is a dynamic_array */
4835 struct outline
4836 {
4837     int count, capacity;
4838     struct point2d *items;
4839 };
4840
4841 /* is a dynamic_array */
4842 struct outline_array
4843 {
4844     int count, capacity;
4845     struct outline *items;
4846 };
4847
4848 struct face_array
4849 {
4850     int count;
4851     face *items;
4852 };
4853
4854 struct point2d_index
4855 {
4856     struct outline *outline;
4857     int vertex;
4858 };
4859
4860 struct point2d_index_array
4861 {
4862     int count;
4863     struct point2d_index *items;
4864 };
4865
4866 struct glyphinfo
4867 {
4868     struct outline_array outlines;
4869     struct face_array faces;
4870     struct point2d_index_array ordered_vertices;
4871     float offset_x;
4872 };
4873
4874 /* is an dynamic_array */
4875 struct word_array
4876 {
4877     int count, capacity;
4878     WORD *items;
4879 };
4880
4881 /* complex polygons are split into monotone polygons, which have
4882  * at most 2 intersections with the vertical sweep line */
4883 struct triangulation
4884 {
4885     struct word_array vertex_stack;
4886     BOOL last_on_top, merging;
4887 };
4888
4889 /* is an dynamic_array */
4890 struct triangulation_array
4891 {
4892     int count, capacity;
4893     struct triangulation *items;
4894
4895     struct glyphinfo *glyph;
4896 };
4897
4898 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
4899 {
4900     if (count > array->capacity) {
4901         void *new_buffer;
4902         int new_capacity;
4903         if (array->items && array->capacity) {
4904             new_capacity = max(array->capacity * 2, count);
4905             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
4906         } else {
4907             new_capacity = max(16, count);
4908             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
4909         }
4910         if (!new_buffer)
4911             return FALSE;
4912         array->items = new_buffer;
4913         array->capacity = new_capacity;
4914     }
4915     return TRUE;
4916 }
4917
4918 static struct point2d *add_points(struct outline *array, int num)
4919 {
4920     struct point2d *item;
4921
4922     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
4923         return NULL;
4924
4925     item = &array->items[array->count];
4926     array->count += num;
4927     return item;
4928 }
4929
4930 static struct outline *add_outline(struct outline_array *array)
4931 {
4932     struct outline *item;
4933
4934     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4935         return NULL;
4936
4937     item = &array->items[array->count++];
4938     ZeroMemory(item, sizeof(*item));
4939     return item;
4940 }
4941
4942 static inline face *add_face(struct face_array *array)
4943 {
4944     return &array->items[array->count++];
4945 }
4946
4947 static struct triangulation *add_triangulation(struct triangulation_array *array)
4948 {
4949     struct triangulation *item;
4950
4951     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4952         return NULL;
4953
4954     item = &array->items[array->count++];
4955     ZeroMemory(item, sizeof(*item));
4956     return item;
4957 }
4958
4959 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
4960 {
4961     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
4962         return E_OUTOFMEMORY;
4963
4964     array->items[array->count++] = vertex_index;
4965     return S_OK;
4966 }
4967
4968 /* assume fixed point numbers can be converted to float point in place */
4969 C_ASSERT(sizeof(FIXED) == sizeof(float));
4970 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
4971
4972 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
4973 {
4974     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
4975     while (count--) {
4976         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
4977         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
4978         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
4979         pt++;
4980     }
4981     return ret;
4982 }
4983
4984 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
4985                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
4986                                  float max_deviation_sq)
4987 {
4988     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
4989     float deviation_sq;
4990
4991     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
4992     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
4993     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
4994
4995     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
4996     if (deviation_sq < max_deviation_sq) {
4997         struct point2d *pt = add_points(outline, 1);
4998         if (!pt) return E_OUTOFMEMORY;
4999         pt->pos = *p2;
5000         pt->corner = POINTTYPE_CURVE;
5001         /* the end point is omitted because the end line merges into the next segment of
5002          * the split bezier curve, and the end of the split bezier curve is added outside
5003          * this recursive function. */
5004     } else {
5005         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
5006         if (hr != S_OK) return hr;
5007         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
5008         if (hr != S_OK) return hr;
5009     }
5010
5011     return S_OK;
5012 }
5013
5014 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
5015 {
5016     /* dot product = cos(theta) */
5017     return D3DXVec2Dot(dir1, dir2) > cos_theta;
5018 }
5019
5020 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
5021 {
5022     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
5023 }
5024
5025 struct cos_table
5026 {
5027     float cos_half;
5028     float cos_45;
5029     float cos_90;
5030 };
5031
5032 static BOOL attempt_line_merge(struct outline *outline,
5033                                int pt_index,
5034                                const D3DXVECTOR2 *nextpt,
5035                                BOOL to_curve,
5036                                const struct cos_table *table)
5037 {
5038     D3DXVECTOR2 curdir, lastdir;
5039     struct point2d *prevpt, *pt;
5040     BOOL ret = FALSE;
5041
5042     pt = &outline->items[pt_index];
5043     pt_index = (pt_index - 1 + outline->count) % outline->count;
5044     prevpt = &outline->items[pt_index];
5045
5046     if (to_curve)
5047         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
5048
5049     if (outline->count < 2)
5050         return FALSE;
5051
5052     /* remove last point if the next line continues the last line */
5053     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
5054     unit_vec2(&curdir, &pt->pos, nextpt);
5055     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
5056     {
5057         outline->count--;
5058         if (pt->corner == POINTTYPE_CURVE_END)
5059             prevpt->corner = pt->corner;
5060         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
5061             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
5062         pt = prevpt;
5063
5064         ret = TRUE;
5065         if (outline->count < 2)
5066             return ret;
5067
5068         pt_index = (pt_index - 1 + outline->count) % outline->count;
5069         prevpt = &outline->items[pt_index];
5070         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
5071         unit_vec2(&curdir, &pt->pos, nextpt);
5072     }
5073     return ret;
5074 }
5075
5076 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
5077                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
5078 {
5079     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
5080
5081     while ((char *)header < (char *)raw_outline + datasize)
5082     {
5083         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
5084         struct point2d *lastpt, *pt;
5085         D3DXVECTOR2 lastdir;
5086         D3DXVECTOR2 *pt_flt;
5087         int j;
5088         struct outline *outline = add_outline(&glyph->outlines);
5089
5090         if (!outline)
5091             return E_OUTOFMEMORY;
5092
5093         pt = add_points(outline, 1);
5094         if (!pt)
5095             return E_OUTOFMEMORY;
5096         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
5097         pt->pos = *pt_flt;
5098         pt->corner = POINTTYPE_CORNER;
5099
5100         if (header->dwType != TT_POLYGON_TYPE)
5101             FIXME("Unknown header type %d\n", header->dwType);
5102
5103         while ((char *)curve < (char *)header + header->cb)
5104         {
5105             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
5106             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
5107
5108             if (!curve->cpfx) {
5109                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
5110                 continue;
5111             }
5112
5113             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
5114
5115             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
5116
5117             if (to_curve)
5118             {
5119                 HRESULT hr;
5120                 int count = curve->cpfx;
5121                 j = 0;
5122
5123                 while (count > 2)
5124                 {
5125                     D3DXVECTOR2 bezier_end;
5126
5127                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
5128                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
5129                     if (hr != S_OK)
5130                         return hr;
5131                     bezier_start = bezier_end;
5132                     count--;
5133                     j++;
5134                 }
5135                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
5136                 if (hr != S_OK)
5137                     return hr;
5138
5139                 pt = add_points(outline, 1);
5140                 if (!pt)
5141                     return E_OUTOFMEMORY;
5142                 j++;
5143                 pt->pos = pt_flt[j];
5144                 pt->corner = POINTTYPE_CURVE_END;
5145             } else {
5146                 pt = add_points(outline, curve->cpfx);
5147                 if (!pt)
5148                     return E_OUTOFMEMORY;
5149                 for (j = 0; j < curve->cpfx; j++)
5150                 {
5151                     pt->pos = pt_flt[j];
5152                     pt->corner = POINTTYPE_CORNER;
5153                     pt++;
5154                 }
5155             }
5156
5157             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
5158         }
5159
5160         /* remove last point if the next line continues the last line */
5161         if (outline->count >= 3) {
5162             BOOL to_curve;
5163
5164             lastpt = &outline->items[outline->count - 1];
5165             pt = &outline->items[0];
5166             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
5167                 if (lastpt->corner == POINTTYPE_CURVE_END)
5168                 {
5169                     if (pt->corner == POINTTYPE_CURVE_START)
5170                         pt->corner = POINTTYPE_CURVE_MIDDLE;
5171                     else
5172                         pt->corner = POINTTYPE_CURVE_END;
5173                 }
5174                 outline->count--;
5175                 lastpt = &outline->items[outline->count - 1];
5176             } else {
5177                 /* outline closed with a line from end to start point */
5178                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
5179             }
5180             lastpt = &outline->items[0];
5181             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
5182             if (lastpt->corner == POINTTYPE_CURVE_START)
5183                 lastpt->corner = POINTTYPE_CORNER;
5184             pt = &outline->items[1];
5185             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
5186                 *lastpt = outline->items[outline->count];
5187         }
5188
5189         lastpt = &outline->items[outline->count - 1];
5190         pt = &outline->items[0];
5191         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
5192         for (j = 0; j < outline->count; j++)
5193         {
5194             D3DXVECTOR2 curdir;
5195
5196             lastpt = pt;
5197             pt = &outline->items[(j + 1) % outline->count];
5198             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
5199
5200             switch (lastpt->corner)
5201             {
5202                 case POINTTYPE_CURVE_START:
5203                 case POINTTYPE_CURVE_END:
5204                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
5205                         lastpt->corner = POINTTYPE_CORNER;
5206                     break;
5207                 case POINTTYPE_CURVE_MIDDLE:
5208                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
5209                         lastpt->corner = POINTTYPE_CORNER;
5210                     else
5211                         lastpt->corner = POINTTYPE_CURVE;
5212                     break;
5213                 default:
5214                     break;
5215             }
5216             lastdir = curdir;
5217         }
5218
5219         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
5220     }
5221     return S_OK;
5222 }
5223
5224 /* Get the y-distance from a line to a point */
5225 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
5226                                           D3DXVECTOR2 *line_pt2,
5227                                           D3DXVECTOR2 *point)
5228 {
5229     D3DXVECTOR2 line_vec = {0, 0};
5230     float line_pt_dx;
5231     float line_y;
5232
5233     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
5234     line_pt_dx = point->x - line_pt1->x;
5235     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
5236     return point->y - line_y;
5237 }
5238
5239 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
5240 {
5241     return &pt_idx->outline->items[pt_idx->vertex].pos;
5242 }
5243
5244 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
5245 {
5246     return get_indexed_point(&glyph->ordered_vertices.items[index]);
5247 }
5248
5249 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
5250 {
5251     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
5252     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
5253     array->count--;
5254 }
5255
5256 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
5257                                        struct triangulation_array *triangulations,
5258                                        WORD vtx_idx,
5259                                        BOOL to_top)
5260 {
5261     struct glyphinfo *glyph = triangulations->glyph;
5262     struct triangulation *t = *t_ptr;
5263     HRESULT hr;
5264     face *face;
5265     int f1, f2;
5266
5267     if (t->last_on_top) {
5268         f1 = 1;
5269         f2 = 2;
5270     } else {
5271         f1 = 2;
5272         f2 = 1;
5273     }
5274
5275     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
5276         /* consume all vertices on the stack */
5277         WORD last_pt = t->vertex_stack.items[0];
5278         int i;
5279         for (i = 1; i < t->vertex_stack.count; i++)
5280         {
5281             face = add_face(&glyph->faces);
5282             if (!face) return E_OUTOFMEMORY;
5283             (*face)[0] = vtx_idx;
5284             (*face)[f1] = last_pt;
5285             (*face)[f2] = last_pt = t->vertex_stack.items[i];
5286         }
5287         t->vertex_stack.items[0] = last_pt;
5288         t->vertex_stack.count = 1;
5289     } else if (t->vertex_stack.count > 1) {
5290         int i = t->vertex_stack.count - 1;
5291         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
5292         WORD top_idx = t->vertex_stack.items[i--];
5293         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
5294
5295         while (i >= 0)
5296         {
5297             WORD prev_idx = t->vertex_stack.items[i--];
5298             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
5299
5300             if (prev_pt->x != top_pt->x &&
5301                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
5302                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
5303                 break;
5304
5305             face = add_face(&glyph->faces);
5306             if (!face) return E_OUTOFMEMORY;
5307             (*face)[0] = vtx_idx;
5308             (*face)[f1] = prev_idx;
5309             (*face)[f2] = top_idx;
5310
5311             top_pt = prev_pt;
5312             top_idx = prev_idx;
5313             t->vertex_stack.count--;
5314         }
5315     }
5316     t->last_on_top = to_top;
5317
5318     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
5319
5320     if (hr == S_OK && t->merging) {
5321         struct triangulation *t2;
5322
5323         t2 = to_top ? t - 1 : t + 1;
5324         t2->merging = FALSE;
5325         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
5326         if (hr != S_OK) return hr;
5327         remove_triangulation(triangulations, t);
5328         if (t2 > t)
5329             t2--;
5330         *t_ptr = t2;
5331     }
5332     return hr;
5333 }
5334
5335 /* check if the point is next on the outline for either the top or bottom */
5336 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
5337 {
5338     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
5339     WORD idx = t->vertex_stack.items[i];
5340     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
5341     struct outline *outline = pt_idx->outline;
5342
5343     if (on_top)
5344         i = (pt_idx->vertex + outline->count - 1) % outline->count;
5345     else
5346         i = (pt_idx->vertex + 1) % outline->count;
5347
5348     return &outline->items[i].pos;
5349 }
5350
5351 static int compare_vertex_indices(const void *a, const void *b)
5352 {
5353     const struct point2d_index *idx1 = a, *idx2 = b;
5354     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
5355     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
5356     float diff = p1->x - p2->x;
5357
5358     if (diff == 0.0f)
5359         diff = p1->y - p2->y;
5360
5361     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
5362 }
5363
5364 static HRESULT triangulate(struct triangulation_array *triangulations)
5365 {
5366     int sweep_idx;
5367     HRESULT hr;
5368     struct glyphinfo *glyph = triangulations->glyph;
5369     int nb_vertices = 0;
5370     int i;
5371     struct point2d_index *idx_ptr;
5372
5373     for (i = 0; i < glyph->outlines.count; i++)
5374         nb_vertices += glyph->outlines.items[i].count;
5375
5376     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
5377             nb_vertices * sizeof(*glyph->ordered_vertices.items));
5378     if (!glyph->ordered_vertices.items)
5379         return E_OUTOFMEMORY;
5380
5381     idx_ptr = glyph->ordered_vertices.items;
5382     for (i = 0; i < glyph->outlines.count; i++)
5383     {
5384         struct outline *outline = &glyph->outlines.items[i];
5385         int j;
5386
5387         idx_ptr->outline = outline;
5388         idx_ptr->vertex = 0;
5389         idx_ptr++;
5390         for (j = outline->count - 1; j > 0; j--)
5391         {
5392             idx_ptr->outline = outline;
5393             idx_ptr->vertex = j;
5394             idx_ptr++;
5395         }
5396     }
5397     glyph->ordered_vertices.count = nb_vertices;
5398
5399     /* Native implementation seems to try to create a triangle fan from
5400      * the first outline point if the glyph only has one outline. */
5401     if (glyph->outlines.count == 1)
5402     {
5403         struct outline *outline = glyph->outlines.items;
5404         D3DXVECTOR2 *base = &outline->items[0].pos;
5405         D3DXVECTOR2 *last = &outline->items[1].pos;
5406         float ccw = 0;
5407
5408         for (i = 2; i < outline->count; i++)
5409         {
5410             D3DXVECTOR2 *next = &outline->items[i].pos;
5411             D3DXVECTOR2 v1 = {0.0f, 0.0f};
5412             D3DXVECTOR2 v2 = {0.0f, 0.0f};
5413
5414             D3DXVec2Subtract(&v1, base, last);
5415             D3DXVec2Subtract(&v2, last, next);
5416             ccw = D3DXVec2CCW(&v1, &v2);
5417             if (ccw > 0.0f)
5418                 break;
5419
5420             last = next;
5421         }
5422         if (ccw <= 0)
5423         {
5424             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5425                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
5426             if (!glyph->faces.items)
5427                 return E_OUTOFMEMORY;
5428
5429             glyph->faces.count = outline->count - 2;
5430             for (i = 0; i < glyph->faces.count; i++)
5431             {
5432                 glyph->faces.items[i][0] = 0;
5433                 glyph->faces.items[i][1] = i + 1;
5434                 glyph->faces.items[i][2] = i + 2;
5435             }
5436             return S_OK;
5437         }
5438     }
5439
5440     /* Perform 2D polygon triangulation for complex glyphs.
5441      * Triangulation is performed using a sweep line concept, from right to left,
5442      * by processing vertices in sorted order. Complex polygons are split into
5443      * monotone polygons which are triangulated separately. */
5444     /* FIXME: The order of the faces is not consistent with the native implementation. */
5445
5446     /* Reserve space for maximum possible faces from triangulation.
5447      * # faces for outer outlines = outline->count - 2
5448      * # faces for inner outlines = outline->count + 2
5449      * There must be at least 1 outer outline. */
5450     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
5451             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
5452     if (!glyph->faces.items)
5453         return E_OUTOFMEMORY;
5454
5455     qsort(glyph->ordered_vertices.items, nb_vertices,
5456           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
5457     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
5458     {
5459         int start = 0;
5460         int end = triangulations->count;
5461
5462         while (start < end)
5463         {
5464             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
5465             int current = (start + end) / 2;
5466             struct triangulation *t = &triangulations->items[current];
5467             BOOL on_top_outline = FALSE;
5468             D3DXVECTOR2 *top_next, *bottom_next;
5469             WORD top_idx, bottom_idx;
5470
5471             if (t->merging && t->last_on_top)
5472                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
5473             else
5474                 top_next = triangulation_get_next_point(t, glyph, TRUE);
5475             if (sweep_vtx == top_next)
5476             {
5477                 if (t->merging && t->last_on_top)
5478                     t++;
5479                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
5480                 if (hr != S_OK) return hr;
5481
5482                 if (t + 1 < &triangulations->items[triangulations->count] &&
5483                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
5484                 {
5485                     /* point also on bottom outline of higher triangulation */
5486                     struct triangulation *t2 = t + 1;
5487                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
5488                     if (hr != S_OK) return hr;
5489
5490                     t->merging = TRUE;
5491                     t2->merging = TRUE;
5492                 }
5493                 on_top_outline = TRUE;
5494             }
5495
5496             if (t->merging && !t->last_on_top)
5497                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
5498             else
5499                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
5500             if (sweep_vtx == bottom_next)
5501             {
5502                 if (t->merging && !t->last_on_top)
5503                     t--;
5504                 if (on_top_outline) {
5505                     /* outline finished */
5506                     remove_triangulation(triangulations, t);
5507                     break;
5508                 }
5509
5510                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
5511                 if (hr != S_OK) return hr;
5512
5513                 if (t > triangulations->items &&
5514                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
5515                 {
5516                     struct triangulation *t2 = t - 1;
5517                     /* point also on top outline of lower triangulation */
5518                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
5519                     if (hr != S_OK) return hr;
5520                     t = t2 + 1; /* t may be invalidated by triangulation merging */
5521
5522                     t->merging = TRUE;
5523                     t2->merging = TRUE;
5524                 }
5525                 break;
5526             }
5527             if (on_top_outline)
5528                 break;
5529
5530             if (t->last_on_top) {
5531                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5532                 bottom_idx = t->vertex_stack.items[0];
5533             } else {
5534                 top_idx = t->vertex_stack.items[0];
5535                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
5536             }
5537
5538             /* check if the point is inside or outside this polygon */
5539             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
5540                                              top_next, sweep_vtx) > 0)
5541             { /* above */
5542                 start = current + 1;
5543             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
5544                                                     bottom_next, sweep_vtx) < 0)
5545             { /* below */
5546                 end = current;
5547             } else if (t->merging) {
5548                 /* inside, so cancel merging */
5549                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
5550                 t->merging = FALSE;
5551                 t2->merging = FALSE;
5552                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5553                 if (hr != S_OK) return hr;
5554                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
5555                 if (hr != S_OK) return hr;
5556                 break;
5557             } else {
5558                 /* inside, so split polygon into two monotone parts */
5559                 struct triangulation *t2 = add_triangulation(triangulations);
5560                 if (!t2) return E_OUTOFMEMORY;
5561                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5562                 if (t->last_on_top) {
5563                     t2 = t + 1;
5564                 } else {
5565                     t2 = t;
5566                     t++;
5567                 }
5568
5569                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
5570                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
5571                 if (hr != S_OK) return hr;
5572                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
5573                 if (hr != S_OK) return hr;
5574                 t2->last_on_top = !t->last_on_top;
5575
5576                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
5577                 if (hr != S_OK) return hr;
5578                 break;
5579             }
5580         }
5581         if (start >= end)
5582         {
5583             struct triangulation *t;
5584             struct triangulation *t2 = add_triangulation(triangulations);
5585             if (!t2) return E_OUTOFMEMORY;
5586             t = &triangulations->items[start];
5587             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
5588             ZeroMemory(t, sizeof(*t));
5589             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
5590             if (hr != S_OK) return hr;
5591         }
5592     }
5593     return S_OK;
5594 }
5595
5596 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
5597                                HDC hdc, LPCWSTR text,
5598                                FLOAT deviation, FLOAT extrusion,
5599                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
5600                                LPGLYPHMETRICSFLOAT glyphmetrics)
5601 {
5602     HRESULT hr;
5603     ID3DXMesh *mesh = NULL;
5604     DWORD nb_vertices, nb_faces;
5605     DWORD nb_front_faces, nb_corners, nb_outline_points;
5606     struct vertex *vertices = NULL;
5607     face *faces = NULL;
5608     int textlen = 0;
5609     float offset_x;
5610     LOGFONTW lf;
5611     OUTLINETEXTMETRICW otm;
5612     HFONT font = NULL, oldfont = NULL;
5613     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
5614     void *raw_outline = NULL;
5615     int bufsize = 0;
5616     struct glyphinfo *glyphs = NULL;
5617     GLYPHMETRICS gm;
5618     struct triangulation_array triangulations = {0, 0, NULL};
5619     int i;
5620     struct vertex *vertex_ptr;
5621     face *face_ptr;
5622     float max_deviation_sq;
5623     const struct cos_table cos_table = {
5624         cos(D3DXToRadian(0.5f)),
5625         cos(D3DXToRadian(45.0f)),
5626         cos(D3DXToRadian(90.0f)),
5627     };
5628     int f1, f2;
5629
5630     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
5631           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
5632
5633     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
5634         return D3DERR_INVALIDCALL;
5635
5636     if (adjacency)
5637     {
5638         FIXME("Case of adjacency != NULL not implemented.\n");
5639         return E_NOTIMPL;
5640     }
5641
5642     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
5643         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
5644     {
5645         return D3DERR_INVALIDCALL;
5646     }
5647
5648     if (deviation == 0.0f)
5649         deviation = 1.0f / otm.otmEMSquare;
5650     max_deviation_sq = deviation * deviation;
5651
5652     lf.lfHeight = otm.otmEMSquare;
5653     lf.lfWidth = 0;
5654     font = CreateFontIndirectW(&lf);
5655     if (!font) {
5656         hr = E_OUTOFMEMORY;
5657         goto error;
5658     }
5659     oldfont = SelectObject(hdc, font);
5660
5661     textlen = strlenW(text);
5662     for (i = 0; i < textlen; i++)
5663     {
5664         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
5665         if (datasize < 0)
5666             return D3DERR_INVALIDCALL;
5667         if (bufsize < datasize)
5668             bufsize = datasize;
5669     }
5670     if (!bufsize) { /* e.g. text == " " */
5671         hr = D3DERR_INVALIDCALL;
5672         goto error;
5673     }
5674
5675     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
5676     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
5677     if (!glyphs || !raw_outline) {
5678         hr = E_OUTOFMEMORY;
5679         goto error;
5680     }
5681
5682     offset_x = 0.0f;
5683     for (i = 0; i < textlen; i++)
5684     {
5685         /* get outline points from data returned from GetGlyphOutline */
5686         int datasize;
5687
5688         glyphs[i].offset_x = offset_x;
5689
5690         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
5691         hr = create_outline(&glyphs[i], raw_outline, datasize,
5692                             max_deviation_sq, otm.otmEMSquare, &cos_table);
5693         if (hr != S_OK) goto error;
5694
5695         triangulations.glyph = &glyphs[i];
5696         hr = triangulate(&triangulations);
5697         if (hr != S_OK) goto error;
5698         if (triangulations.count) {
5699             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
5700             triangulations.count = 0;
5701         }
5702
5703         if (glyphmetrics)
5704         {
5705             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
5706             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
5707             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
5708             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
5709             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
5710             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
5711         }
5712         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
5713     }
5714
5715     /* corner points need an extra vertex for the different side faces normals */
5716     nb_corners = 0;
5717     nb_outline_points = 0;
5718     nb_front_faces = 0;
5719     for (i = 0; i < textlen; i++)
5720     {
5721         int j;
5722         nb_outline_points += glyphs[i].ordered_vertices.count;
5723         nb_front_faces += glyphs[i].faces.count;
5724         for (j = 0; j < glyphs[i].outlines.count; j++)
5725         {
5726             int k;
5727             struct outline *outline = &glyphs[i].outlines.items[j];
5728             nb_corners++; /* first outline point always repeated as a corner */
5729             for (k = 1; k < outline->count; k++)
5730                 if (outline->items[k].corner)
5731                     nb_corners++;
5732         }
5733     }
5734
5735     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
5736     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
5737
5738
5739     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
5740                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
5741     if (FAILED(hr))
5742         goto error;
5743
5744     hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (LPVOID *)&vertices);
5745     if (FAILED(hr))
5746         goto error;
5747
5748     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, (LPVOID *)&faces);
5749     if (FAILED(hr))
5750         goto error;
5751
5752     /* convert 2D vertices and faces into 3D mesh */
5753     vertex_ptr = vertices;
5754     face_ptr = faces;
5755     if (extrusion == 0.0f) {
5756         f1 = 1;
5757         f2 = 2;
5758     } else {
5759         f1 = 2;
5760         f2 = 1;
5761     }
5762     for (i = 0; i < textlen; i++)
5763     {
5764         int j;
5765         int count;
5766         struct vertex *back_vertices;
5767         face *back_faces;
5768
5769         /* side vertices and faces */
5770         for (j = 0; j < glyphs[i].outlines.count; j++)
5771         {
5772             struct vertex *outline_vertices = vertex_ptr;
5773             struct outline *outline = &glyphs[i].outlines.items[j];
5774             int k;
5775             struct point2d *prevpt = &outline->items[outline->count - 1];
5776             struct point2d *pt = &outline->items[0];
5777
5778             for (k = 1; k <= outline->count; k++)
5779             {
5780                 struct vertex vtx;
5781                 struct point2d *nextpt = &outline->items[k % outline->count];
5782                 WORD vtx_idx = vertex_ptr - vertices;
5783                 D3DXVECTOR2 vec;
5784
5785                 if (pt->corner == POINTTYPE_CURVE_START)
5786                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
5787                 else if (pt->corner)
5788                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5789                 else
5790                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
5791                 D3DXVec2Normalize(&vec, &vec);
5792                 vtx.normal.x = -vec.y;
5793                 vtx.normal.y = vec.x;
5794                 vtx.normal.z = 0;
5795
5796                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
5797                 vtx.position.y = pt->pos.y;
5798                 vtx.position.z = 0;
5799                 *vertex_ptr++ = vtx;
5800
5801                 vtx.position.z = -extrusion;
5802                 *vertex_ptr++ = vtx;
5803
5804                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
5805                 vtx.position.y = nextpt->pos.y;
5806                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
5807                     vtx.position.z = -extrusion;
5808                     *vertex_ptr++ = vtx;
5809                     vtx.position.z = 0;
5810                     *vertex_ptr++ = vtx;
5811
5812                     (*face_ptr)[0] = vtx_idx;
5813                     (*face_ptr)[1] = vtx_idx + 2;
5814                     (*face_ptr)[2] = vtx_idx + 1;
5815                     face_ptr++;
5816
5817                     (*face_ptr)[0] = vtx_idx;
5818                     (*face_ptr)[1] = vtx_idx + 3;
5819                     (*face_ptr)[2] = vtx_idx + 2;
5820                     face_ptr++;
5821                 } else {
5822                     if (nextpt->corner) {
5823                         if (nextpt->corner == POINTTYPE_CURVE_END) {
5824                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
5825                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
5826                         } else {
5827                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
5828                         }
5829                         D3DXVec2Normalize(&vec, &vec);
5830                         vtx.normal.x = -vec.y;
5831                         vtx.normal.y = vec.x;
5832
5833                         vtx.position.z = 0;
5834                         *vertex_ptr++ = vtx;
5835                         vtx.position.z = -extrusion;
5836                         *vertex_ptr++ = vtx;
5837                     }
5838
5839                     (*face_ptr)[0] = vtx_idx;
5840                     (*face_ptr)[1] = vtx_idx + 3;
5841                     (*face_ptr)[2] = vtx_idx + 1;
5842                     face_ptr++;
5843
5844                     (*face_ptr)[0] = vtx_idx;
5845                     (*face_ptr)[1] = vtx_idx + 2;
5846                     (*face_ptr)[2] = vtx_idx + 3;
5847                     face_ptr++;
5848                 }
5849
5850                 prevpt = pt;
5851                 pt = nextpt;
5852             }
5853             if (!pt->corner) {
5854                 *vertex_ptr++ = *outline_vertices++;
5855                 *vertex_ptr++ = *outline_vertices++;
5856             }
5857         }
5858
5859         /* back vertices and faces */
5860         back_faces = face_ptr;
5861         back_vertices = vertex_ptr;
5862         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
5863         {
5864             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
5865             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
5866             vertex_ptr->position.y = pt->y;
5867             vertex_ptr->position.z = 0;
5868             vertex_ptr->normal.x = 0;
5869             vertex_ptr->normal.y = 0;
5870             vertex_ptr->normal.z = 1;
5871             vertex_ptr++;
5872         }
5873         count = back_vertices - vertices;
5874         for (j = 0; j < glyphs[i].faces.count; j++)
5875         {
5876             face *f = &glyphs[i].faces.items[j];
5877             (*face_ptr)[0] = (*f)[0] + count;
5878             (*face_ptr)[1] = (*f)[1] + count;
5879             (*face_ptr)[2] = (*f)[2] + count;
5880             face_ptr++;
5881         }
5882
5883         /* front vertices and faces */
5884         j = count = vertex_ptr - back_vertices;
5885         while (j--)
5886         {
5887             vertex_ptr->position.x = back_vertices->position.x;
5888             vertex_ptr->position.y = back_vertices->position.y;
5889             vertex_ptr->position.z = -extrusion;
5890             vertex_ptr->normal.x = 0;
5891             vertex_ptr->normal.y = 0;
5892             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
5893             vertex_ptr++;
5894             back_vertices++;
5895         }
5896         j = face_ptr - back_faces;
5897         while (j--)
5898         {
5899             (*face_ptr)[0] = (*back_faces)[0] + count;
5900             (*face_ptr)[1] = (*back_faces)[f1] + count;
5901             (*face_ptr)[2] = (*back_faces)[f2] + count;
5902             face_ptr++;
5903             back_faces++;
5904         }
5905     }
5906
5907     *mesh_ptr = mesh;
5908     hr = D3D_OK;
5909 error:
5910     if (mesh) {
5911         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
5912         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
5913         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
5914     }
5915     if (glyphs) {
5916         for (i = 0; i < textlen; i++)
5917         {
5918             int j;
5919             for (j = 0; j < glyphs[i].outlines.count; j++)
5920                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
5921             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
5922             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
5923             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
5924         }
5925         HeapFree(GetProcessHeap(), 0, glyphs);
5926     }
5927     if (triangulations.items) {
5928         int i;
5929         for (i = 0; i < triangulations.count; i++)
5930             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
5931         HeapFree(GetProcessHeap(), 0, triangulations.items);
5932     }
5933     HeapFree(GetProcessHeap(), 0, raw_outline);
5934     if (oldfont) SelectObject(hdc, oldfont);
5935     if (font) DeleteObject(font);
5936
5937     return hr;
5938 }
5939
5940 HRESULT WINAPI D3DXValidMesh(LPD3DXMESH mesh, CONST DWORD *adjacency, LPD3DXBUFFER *errors_and_warnings)
5941 {
5942     FIXME("(%p, %p, %p): stub\n", mesh, adjacency, *errors_and_warnings);
5943
5944     return E_NOTIMPL;
5945 }
5946
5947 static BOOL weld_float1(void *to, void *from, FLOAT epsilon)
5948 {
5949     FLOAT *v1 = to;
5950     FLOAT *v2 = from;
5951
5952     if (fabsf(*v1 - *v2) <= epsilon)
5953     {
5954         *v1 = *v2;
5955
5956         return TRUE;
5957     }
5958
5959     return FALSE;
5960 }
5961
5962 static BOOL weld_float2(void *to, void *from, FLOAT epsilon)
5963 {
5964     D3DXVECTOR2 *v1 = to;
5965     D3DXVECTOR2 *v2 = from;
5966     FLOAT diff_x = fabsf(v1->x - v2->x);
5967     FLOAT diff_y = fabsf(v1->y - v2->y);
5968     FLOAT max_abs_diff = max(diff_x, diff_y);
5969
5970     if (max_abs_diff <= epsilon)
5971     {
5972         memcpy(to, from, sizeof(D3DXVECTOR2));
5973
5974         return TRUE;
5975     }
5976
5977     return FALSE;
5978 }
5979
5980 static BOOL weld_float3(void *to, void *from, FLOAT epsilon)
5981 {
5982     D3DXVECTOR3 *v1 = to;
5983     D3DXVECTOR3 *v2 = from;
5984     FLOAT diff_x = fabsf(v1->x - v2->x);
5985     FLOAT diff_y = fabsf(v1->y - v2->y);
5986     FLOAT diff_z = fabsf(v1->z - v2->z);
5987     FLOAT max_abs_diff = max(diff_x, diff_y);
5988     max_abs_diff = max(diff_z, max_abs_diff);
5989
5990     if (max_abs_diff <= epsilon)
5991     {
5992         memcpy(to, from, sizeof(D3DXVECTOR3));
5993
5994         return TRUE;
5995     }
5996
5997     return FALSE;
5998 }
5999
6000 static BOOL weld_float4(void *to, void *from, FLOAT epsilon)
6001 {
6002     D3DXVECTOR4 *v1 = to;
6003     D3DXVECTOR4 *v2 = from;
6004     FLOAT diff_x = fabsf(v1->x - v2->x);
6005     FLOAT diff_y = fabsf(v1->y - v2->y);
6006     FLOAT diff_z = fabsf(v1->z - v2->z);
6007     FLOAT diff_w = fabsf(v1->w - v2->w);
6008     FLOAT max_abs_diff = fmax(diff_x, diff_y);
6009     max_abs_diff = max(diff_z, max_abs_diff);
6010     max_abs_diff = max(diff_w, max_abs_diff);
6011
6012     if (max_abs_diff <= epsilon)
6013     {
6014         memcpy(to, from, sizeof(D3DXVECTOR4));
6015
6016         return TRUE;
6017     }
6018
6019     return FALSE;
6020 }
6021
6022 static BOOL weld_ubyte4(void *to, void *from, FLOAT epsilon)
6023 {
6024     BYTE *b1 = to;
6025     BYTE *b2 = from;
6026     BYTE truncated_epsilon = (BYTE)epsilon;
6027     BYTE diff_x = b1[0] > b2[0] ? b1[0] - b2[0] : b2[0] - b1[0];
6028     BYTE diff_y = b1[1] > b2[1] ? b1[1] - b2[1] : b2[1] - b1[1];
6029     BYTE diff_z = b1[2] > b2[2] ? b1[2] - b2[2] : b2[2] - b1[2];
6030     BYTE diff_w = b1[3] > b2[3] ? b1[3] - b2[3] : b2[3] - b1[3];
6031     BYTE max_diff = max(diff_x, diff_y);
6032     max_diff = max(diff_z, max_diff);
6033     max_diff = max(diff_w, max_diff);
6034
6035     if (max_diff <= truncated_epsilon)
6036     {
6037         memcpy(to, from, 4 * sizeof(BYTE));
6038
6039         return TRUE;
6040     }
6041
6042     return FALSE;
6043 }
6044
6045 static BOOL weld_ubyte4n(void *to, void *from, FLOAT epsilon)
6046 {
6047     return weld_ubyte4(to, from, epsilon * UCHAR_MAX);
6048 }
6049
6050 static BOOL weld_d3dcolor(void *to, void *from, FLOAT epsilon)
6051 {
6052     return weld_ubyte4n(to, from, epsilon);
6053 }
6054
6055 static BOOL weld_short2(void *to, void *from, FLOAT epsilon)
6056 {
6057     SHORT *s1 = to;
6058     SHORT *s2 = from;
6059     SHORT truncated_epsilon = (SHORT)epsilon;
6060     SHORT diff_x = abs(s1[0] - s2[0]);
6061     SHORT diff_y = abs(s1[1] - s2[1]);
6062     SHORT max_abs_diff = max(diff_x, diff_y);
6063
6064     if (max_abs_diff <= truncated_epsilon)
6065     {
6066         memcpy(to, from, 2 * sizeof(SHORT));
6067
6068         return TRUE;
6069     }
6070
6071     return FALSE;
6072 }
6073
6074 static BOOL weld_short2n(void *to, void *from, FLOAT epsilon)
6075 {
6076     return weld_short2(to, from, epsilon * SHRT_MAX);
6077 }
6078
6079 static BOOL weld_short4(void *to, void *from, FLOAT epsilon)
6080 {
6081     SHORT *s1 = to;
6082     SHORT *s2 = from;
6083     SHORT truncated_epsilon = (SHORT)epsilon;
6084     SHORT diff_x = abs(s1[0] - s2[0]);
6085     SHORT diff_y = abs(s1[1] - s2[1]);
6086     SHORT diff_z = abs(s1[2] - s2[2]);
6087     SHORT diff_w = abs(s1[3] - s2[3]);
6088     SHORT max_abs_diff = max(diff_x, diff_y);
6089     max_abs_diff = max(diff_z, max_abs_diff);
6090     max_abs_diff = max(diff_w, max_abs_diff);
6091
6092     if (max_abs_diff <= truncated_epsilon)
6093     {
6094         memcpy(to, from, 4 * sizeof(SHORT));
6095
6096         return TRUE;
6097     }
6098
6099     return FALSE;
6100 }
6101
6102 static BOOL weld_short4n(void *to, void *from, FLOAT epsilon)
6103 {
6104     return weld_short4(to, from, epsilon * SHRT_MAX);
6105 }
6106
6107 static BOOL weld_ushort2n(void *to, void *from, FLOAT epsilon)
6108 {
6109     USHORT *s1 = to;
6110     USHORT *s2 = from;
6111     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
6112     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
6113     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
6114     USHORT max_diff = max(diff_x, diff_y);
6115
6116     if (max_diff <= scaled_epsilon)
6117     {
6118         memcpy(to, from, 2 * sizeof(USHORT));
6119
6120         return TRUE;
6121     }
6122
6123     return FALSE;
6124 }
6125
6126 static BOOL weld_ushort4n(void *to, void *from, FLOAT epsilon)
6127 {
6128     USHORT *s1 = to;
6129     USHORT *s2 = from;
6130     USHORT scaled_epsilon = (USHORT)(epsilon * USHRT_MAX);
6131     USHORT diff_x = s1[0] > s2[0] ? s1[0] - s2[0] : s2[0] - s1[0];
6132     USHORT diff_y = s1[1] > s2[1] ? s1[1] - s2[1] : s2[1] - s1[1];
6133     USHORT diff_z = s1[2] > s2[2] ? s1[2] - s2[2] : s2[2] - s1[2];
6134     USHORT diff_w = s1[3] > s2[3] ? s1[3] - s2[3] : s2[3] - s1[3];
6135     USHORT max_diff = max(diff_x, diff_y);
6136     max_diff = max(diff_z, max_diff);
6137     max_diff = max(diff_w, max_diff);
6138
6139     if (max_diff <= scaled_epsilon)
6140     {
6141         memcpy(to, from, 4 * sizeof(USHORT));
6142
6143         return TRUE;
6144     }
6145
6146     return FALSE;
6147 }
6148
6149 struct udec3
6150 {
6151     UINT x;
6152     UINT y;
6153     UINT z;
6154     UINT w;
6155 };
6156
6157 static struct udec3 dword_to_udec3(DWORD d)
6158 {
6159     struct udec3 v;
6160
6161     v.x = d & 0x3ff;
6162     v.y = (d & 0xffc00) >> 10;
6163     v.z = (d & 0x3ff00000) >> 20;
6164     v.w = (d & 0xc0000000) >> 30;
6165
6166     return v;
6167 }
6168
6169 static BOOL weld_udec3(void *to, void *from, FLOAT epsilon)
6170 {
6171     DWORD *d1 = to;
6172     DWORD *d2 = from;
6173     struct udec3 v1 = dword_to_udec3(*d1);
6174     struct udec3 v2 = dword_to_udec3(*d2);
6175     UINT truncated_epsilon = (UINT)epsilon;
6176     UINT diff_x = v1.x > v2.x ? v1.x - v2.x : v2.x - v1.x;
6177     UINT diff_y = v1.y > v2.y ? v1.y - v2.y : v2.y - v1.y;
6178     UINT diff_z = v1.z > v2.z ? v1.z - v2.z : v2.z - v1.z;
6179     UINT diff_w = v1.w > v2.w ? v1.w - v2.w : v2.w - v1.w;
6180     UINT max_diff = max(diff_x, diff_y);
6181     max_diff = max(diff_z, max_diff);
6182     max_diff = max(diff_w, max_diff);
6183
6184     if (max_diff <= truncated_epsilon)
6185     {
6186         memcpy(to, from, sizeof(DWORD));
6187
6188         return TRUE;
6189     }
6190
6191     return FALSE;
6192 }
6193
6194 struct dec3n
6195 {
6196     INT x;
6197     INT y;
6198     INT z;
6199     INT w;
6200 };
6201
6202 static struct dec3n dword_to_dec3n(DWORD d)
6203 {
6204     struct dec3n v;
6205
6206     v.x = d & 0x3ff;
6207     v.y = (d & 0xffc00) >> 10;
6208     v.z = (d & 0x3ff00000) >> 20;
6209     v.w = (d & 0xc0000000) >> 30;
6210
6211     return v;
6212 }
6213
6214 static BOOL weld_dec3n(void *to, void *from, FLOAT epsilon)
6215 {
6216     const UINT MAX_DEC3N = 511;
6217     DWORD *d1 = to;
6218     DWORD *d2 = from;
6219     struct dec3n v1 = dword_to_dec3n(*d1);
6220     struct dec3n v2 = dword_to_dec3n(*d2);
6221     INT scaled_epsilon = (INT)(epsilon * MAX_DEC3N);
6222     INT diff_x = abs(v1.x - v2.x);
6223     INT diff_y = abs(v1.y - v2.y);
6224     INT diff_z = abs(v1.z - v2.z);
6225     INT diff_w = abs(v1.w - v2.w);
6226     INT max_abs_diff = max(diff_x, diff_y);
6227     max_abs_diff = max(diff_z, max_abs_diff);
6228     max_abs_diff = max(diff_w, max_abs_diff);
6229
6230     if (max_abs_diff <= scaled_epsilon)
6231     {
6232         memcpy(to, from, sizeof(DWORD));
6233
6234         return TRUE;
6235     }
6236
6237     return FALSE;
6238 }
6239
6240 static BOOL weld_float16_2(void *to, void *from, FLOAT epsilon)
6241 {
6242     D3DXFLOAT16 *v1_float16 = to;
6243     D3DXFLOAT16 *v2_float16 = from;
6244     FLOAT diff_x;
6245     FLOAT diff_y;
6246     FLOAT max_abs_diff;
6247     const UINT NUM_ELEM = 2;
6248     FLOAT v1[NUM_ELEM];
6249     FLOAT v2[NUM_ELEM];
6250
6251     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
6252     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
6253
6254     diff_x = fabsf(v1[0] - v2[0]);
6255     diff_y = fabsf(v1[1] - v2[1]);
6256     max_abs_diff = max(diff_x, diff_y);
6257
6258     if (max_abs_diff <= epsilon)
6259     {
6260         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
6261
6262         return TRUE;
6263     }
6264
6265     return FALSE;
6266 }
6267
6268 static BOOL weld_float16_4(void *to, void *from, FLOAT epsilon)
6269 {
6270     D3DXFLOAT16 *v1_float16 = to;
6271     D3DXFLOAT16 *v2_float16 = from;
6272     FLOAT diff_x;
6273     FLOAT diff_y;
6274     FLOAT diff_z;
6275     FLOAT diff_w;
6276     FLOAT max_abs_diff;
6277     const UINT NUM_ELEM = 4;
6278     FLOAT v1[NUM_ELEM];
6279     FLOAT v2[NUM_ELEM];
6280
6281     D3DXFloat16To32Array(v1, v1_float16, NUM_ELEM);
6282     D3DXFloat16To32Array(v2, v2_float16, NUM_ELEM);
6283
6284     diff_x = fabsf(v1[0] - v2[0]);
6285     diff_y = fabsf(v1[1] - v2[1]);
6286     diff_z = fabsf(v1[2] - v2[2]);
6287     diff_w = fabsf(v1[3] - v2[3]);
6288     max_abs_diff = max(diff_x, diff_y);
6289     max_abs_diff = max(diff_z, max_abs_diff);
6290     max_abs_diff = max(diff_w, max_abs_diff);
6291
6292     if (max_abs_diff <= epsilon)
6293     {
6294         memcpy(to, from, NUM_ELEM * sizeof(D3DXFLOAT16));
6295
6296         return TRUE;
6297     }
6298
6299     return FALSE;
6300 }
6301
6302 /* Sets the vertex components to the same value if they are within epsilon. */
6303 static BOOL weld_component(void *to, void *from, D3DDECLTYPE type, FLOAT epsilon)
6304 {
6305     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
6306     BOOL fixme_once_unused = FALSE;
6307     BOOL fixme_once_unknown = FALSE;
6308
6309     switch (type)
6310     {
6311         case D3DDECLTYPE_FLOAT1:
6312             return weld_float1(to, from, epsilon);
6313
6314         case D3DDECLTYPE_FLOAT2:
6315             return weld_float2(to, from, epsilon);
6316
6317         case D3DDECLTYPE_FLOAT3:
6318             return weld_float3(to, from, epsilon);
6319
6320         case D3DDECLTYPE_FLOAT4:
6321             return weld_float4(to, from, epsilon);
6322
6323         case D3DDECLTYPE_D3DCOLOR:
6324             return weld_d3dcolor(to, from, epsilon);
6325
6326         case D3DDECLTYPE_UBYTE4:
6327             return weld_ubyte4(to, from, epsilon);
6328
6329         case D3DDECLTYPE_SHORT2:
6330             return weld_short2(to, from, epsilon);
6331
6332         case D3DDECLTYPE_SHORT4:
6333             return weld_short4(to, from, epsilon);
6334
6335         case D3DDECLTYPE_UBYTE4N:
6336             return weld_ubyte4n(to, from, epsilon);
6337
6338         case D3DDECLTYPE_SHORT2N:
6339             return weld_short2n(to, from, epsilon);
6340
6341         case D3DDECLTYPE_SHORT4N:
6342             return weld_short4n(to, from, epsilon);
6343
6344         case D3DDECLTYPE_USHORT2N:
6345             return weld_ushort2n(to, from, epsilon);
6346
6347         case D3DDECLTYPE_USHORT4N:
6348             return weld_ushort4n(to, from, epsilon);
6349
6350         case D3DDECLTYPE_UDEC3:
6351             return weld_udec3(to, from, epsilon);
6352
6353         case D3DDECLTYPE_DEC3N:
6354             return weld_dec3n(to, from, epsilon);
6355
6356         case D3DDECLTYPE_FLOAT16_2:
6357             return weld_float16_2(to, from, epsilon);
6358
6359         case D3DDECLTYPE_FLOAT16_4:
6360             return weld_float16_4(to, from, epsilon);
6361
6362         case D3DDECLTYPE_UNUSED:
6363             if (!fixme_once_unused++)
6364                 FIXME("D3DDECLTYPE_UNUSED welding not implemented.\n");
6365             break;
6366
6367         default:
6368             if (!fixme_once_unknown++)
6369                 FIXME("Welding of unknown declaration type %d is not implemented.\n", type);
6370             break;
6371     }
6372
6373     return FALSE;
6374 }
6375
6376 static FLOAT get_component_epsilon(const D3DVERTEXELEMENT9 *decl_ptr, const D3DXWELDEPSILONS *epsilons)
6377 {
6378     FLOAT epsilon = 0.0f;
6379     /* Quiet FIXMEs as this is in a loop with potentially thousand of iterations. */
6380     static BOOL fixme_once_blendindices = FALSE;
6381     static BOOL fixme_once_positiont = FALSE;
6382     static BOOL fixme_once_fog = FALSE;
6383     static BOOL fixme_once_depth = FALSE;
6384     static BOOL fixme_once_sample = FALSE;
6385     static BOOL fixme_once_unknown = FALSE;
6386
6387     switch (decl_ptr->Usage)
6388     {
6389         case D3DDECLUSAGE_POSITION:
6390             epsilon = epsilons->Position;
6391             break;
6392         case D3DDECLUSAGE_BLENDWEIGHT:
6393             epsilon = epsilons->BlendWeights;
6394             break;
6395         case D3DDECLUSAGE_NORMAL:
6396             epsilon = epsilons->Normals;
6397             break;
6398         case D3DDECLUSAGE_PSIZE:
6399             epsilon = epsilons->PSize;
6400             break;
6401         case D3DDECLUSAGE_TEXCOORD:
6402         {
6403             BYTE usage_index = decl_ptr->UsageIndex;
6404             if (usage_index > 7)
6405                 usage_index = 7;
6406             epsilon = epsilons->Texcoords[usage_index];
6407             break;
6408         }
6409         case D3DDECLUSAGE_TANGENT:
6410             epsilon = epsilons->Tangent;
6411             break;
6412         case D3DDECLUSAGE_BINORMAL:
6413             epsilon = epsilons->Binormal;
6414             break;
6415         case D3DDECLUSAGE_TESSFACTOR:
6416             epsilon = epsilons->TessFactor;
6417             break;
6418         case D3DDECLUSAGE_COLOR:
6419             if (decl_ptr->UsageIndex == 0)
6420                 epsilon = epsilons->Diffuse;
6421             else if (decl_ptr->UsageIndex == 1)
6422                 epsilon = epsilons->Specular;
6423             else
6424                 epsilon = 1e-6f;
6425             break;
6426         case D3DDECLUSAGE_BLENDINDICES:
6427             if (!fixme_once_blendindices++)
6428                 FIXME("D3DDECLUSAGE_BLENDINDICES welding not implemented.\n");
6429             break;
6430         case D3DDECLUSAGE_POSITIONT:
6431             if (!fixme_once_positiont++)
6432                 FIXME("D3DDECLUSAGE_POSITIONT welding not implemented.\n");
6433             break;
6434         case D3DDECLUSAGE_FOG:
6435             if (!fixme_once_fog++)
6436                 FIXME("D3DDECLUSAGE_FOG welding not implemented.\n");
6437             break;
6438         case D3DDECLUSAGE_DEPTH:
6439             if (!fixme_once_depth++)
6440                 FIXME("D3DDECLUSAGE_DEPTH welding not implemented.\n");
6441             break;
6442         case D3DDECLUSAGE_SAMPLE:
6443             if (!fixme_once_sample++)
6444                 FIXME("D3DDECLUSAGE_SAMPLE welding not implemented.\n");
6445             break;
6446         default:
6447             if (!fixme_once_unknown++)
6448                 FIXME("Unknown usage %x\n", decl_ptr->Usage);
6449             break;
6450     }
6451
6452     return epsilon;
6453 }
6454
6455 /* Helper function for reading a 32-bit index buffer. */
6456 static inline DWORD read_ib(void *index_buffer, BOOL indices_are_32bit,
6457                             DWORD index)
6458 {
6459     if (indices_are_32bit)
6460     {
6461         DWORD *indices = index_buffer;
6462         return indices[index];
6463     }
6464     else
6465     {
6466         WORD *indices = index_buffer;
6467         return indices[index];
6468     }
6469 }
6470
6471 /* Helper function for writing to a 32-bit index buffer. */
6472 static inline void write_ib(void *index_buffer, BOOL indices_are_32bit,
6473                             DWORD index, DWORD value)
6474 {
6475     if (indices_are_32bit)
6476     {
6477         DWORD *indices = index_buffer;
6478         indices[index] = value;
6479     }
6480     else
6481     {
6482         WORD *indices = index_buffer;
6483         indices[index] = value;
6484     }
6485 }
6486
6487 /*************************************************************************
6488  * D3DXWeldVertices    (D3DX9_36.@)
6489  *
6490  * Welds together similar vertices. The similarity between vert-
6491  * ices can be the position and other components such as
6492  * normal and color.
6493  *
6494  * PARAMS
6495  *   mesh             [I] Mesh which vertices will be welded together.
6496  *   flags            [I] D3DXWELDEPSILONSFLAGS specifying how to weld.
6497  *   epsilons         [I] How similar a component needs to be for welding.
6498  *   adjacency        [I] Which faces are adjacent to other faces.
6499  *   adjacency_out    [O] Updated adjacency after welding.
6500  *   face_remap_out   [O] Which faces the old faces have been mapped to.
6501  *   vertex_remap_out [O] Which vertices the old vertices have been mapped to.
6502  *
6503  * RETURNS
6504  *   Success: D3D_OK.
6505  *   Failure: D3DERR_INVALIDCALL, E_OUTOFMEMORY.
6506  *
6507  * BUGS
6508  *   Attribute sorting not implemented.
6509  *
6510  */
6511 HRESULT WINAPI D3DXWeldVertices(LPD3DXMESH mesh,
6512                                 DWORD flags,
6513                                 CONST D3DXWELDEPSILONS *epsilons,
6514                                 CONST DWORD *adjacency,
6515                                 DWORD *adjacency_out,
6516                                 DWORD *face_remap_out,
6517                                 LPD3DXBUFFER *vertex_remap_out)
6518 {
6519     DWORD *adjacency_generated = NULL;
6520     const DWORD *adjacency_ptr;
6521     DWORD *attributes = NULL;
6522     const FLOAT DEFAULT_EPSILON = 1.0e-6f;
6523     HRESULT hr;
6524     DWORD i;
6525     void *indices = NULL;
6526     BOOL indices_are_32bit = mesh->lpVtbl->GetOptions(mesh) & D3DXMESH_32BIT;
6527     DWORD optimize_flags;
6528     DWORD *point_reps = NULL;
6529     ID3DXMeshImpl *This = impl_from_ID3DXMesh(mesh);
6530     DWORD *vertex_face_map = NULL;
6531     ID3DXBuffer *vertex_remap = NULL;
6532     BYTE *vertices = NULL;
6533
6534     TRACE("(%p, %x, %p, %p, %p, %p, %p)\n", mesh, flags, epsilons,
6535            adjacency, adjacency_out, face_remap_out, vertex_remap_out);
6536
6537     if (flags == 0)
6538     {
6539         WARN("No flags is undefined. Using D3DXWELDEPSILONS_WELDPARTIALMATCHES instead.\n");
6540         flags = D3DXWELDEPSILONS_WELDPARTIALMATCHES;
6541     }
6542
6543     if (adjacency) /* Use supplied adjacency. */
6544     {
6545         adjacency_ptr = adjacency;
6546     }
6547     else /* Adjacency has to be generated. */
6548     {
6549         adjacency_generated = HeapAlloc(GetProcessHeap(), 0, 3 * This->numfaces * sizeof(*adjacency_generated));
6550         if (!adjacency_generated)
6551         {
6552             ERR("Couldn't allocate memory for adjacency_generated.\n");
6553             hr = E_OUTOFMEMORY;
6554             goto cleanup;
6555         }
6556         hr = mesh->lpVtbl->GenerateAdjacency(mesh, DEFAULT_EPSILON, adjacency_generated);
6557         if (FAILED(hr))
6558         {
6559             ERR("Couldn't generate adjacency.\n");
6560             goto cleanup;
6561         }
6562         adjacency_ptr = adjacency_generated;
6563     }
6564
6565     /* Point representation says which vertices can be replaced. */
6566     point_reps = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*point_reps));
6567     if (!point_reps)
6568     {
6569         hr = E_OUTOFMEMORY;
6570         ERR("Couldn't allocate memory for point_reps.\n");
6571         goto cleanup;
6572     }
6573     hr = mesh->lpVtbl->ConvertAdjacencyToPointReps(mesh, adjacency_ptr, point_reps);
6574     if (FAILED(hr))
6575     {
6576         ERR("ConvertAdjacencyToPointReps failed.\n");
6577         goto cleanup;
6578     }
6579
6580     hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, &indices);
6581     if (FAILED(hr))
6582     {
6583         ERR("Couldn't lock index buffer.\n");
6584         goto cleanup;
6585     }
6586
6587     hr = mesh->lpVtbl->LockAttributeBuffer(mesh, 0, &attributes);
6588     if (FAILED(hr))
6589     {
6590         ERR("Couldn't lock attribute buffer.\n");
6591         goto cleanup;
6592     }
6593     vertex_face_map = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*vertex_face_map));
6594     if (!vertex_face_map)
6595     {
6596         hr = E_OUTOFMEMORY;
6597         ERR("Couldn't allocate memory for vertex_face_map.\n");
6598         goto cleanup;
6599     }
6600     /* Build vertex face map, so that a vertex's face can be looked up. */
6601     for (i = 0; i < This->numfaces; i++)
6602     {
6603         DWORD j;
6604         for (j = 0; j < 3; j++)
6605         {
6606             DWORD index = read_ib(indices, indices_are_32bit, 3*i + j);
6607             vertex_face_map[index] = i;
6608         }
6609     }
6610
6611     if (flags & D3DXWELDEPSILONS_WELDPARTIALMATCHES)
6612     {
6613         hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, (void**)&vertices);
6614         if (FAILED(hr))
6615         {
6616             ERR("Couldn't lock vertex buffer.\n");
6617             goto cleanup;
6618         }
6619         /* For each vertex that can be removed, compare its vertex components
6620          * with the vertex components from the vertex that can replace it. A
6621          * vertex is only fully replaced if all the components match and the
6622          * flag D3DXWELDEPSILONS_DONOTREMOVEVERTICES is not set, and they
6623          * belong to the same attribute group. Otherwise the vertex components
6624          * that are within epsilon are set to the same value.
6625          */
6626         for (i = 0; i < 3 * This->numfaces; i++)
6627         {
6628             D3DVERTEXELEMENT9 *decl_ptr;
6629             DWORD vertex_size = mesh->lpVtbl->GetNumBytesPerVertex(mesh);
6630             DWORD num_vertex_components;
6631             INT matches = 0;
6632             BOOL all_match;
6633             DWORD index = read_ib(indices, indices_are_32bit, i);
6634
6635             for (decl_ptr = This->cached_declaration, num_vertex_components = 0; decl_ptr->Stream != 0xFF; decl_ptr++, num_vertex_components++)
6636             {
6637                 BYTE *to = &vertices[vertex_size*index + decl_ptr->Offset];
6638                 BYTE *from = &vertices[vertex_size*point_reps[index] + decl_ptr->Offset];
6639                 FLOAT epsilon = get_component_epsilon(decl_ptr, epsilons);
6640
6641                 /* Don't weld self */
6642                 if (index == point_reps[index])
6643                 {
6644                     matches++;
6645                     continue;
6646                 }
6647
6648                 if (weld_component(to, from, decl_ptr->Type, epsilon))
6649                     matches++;
6650             }
6651
6652             all_match = (num_vertex_components == matches);
6653             if (all_match && !(flags & D3DXWELDEPSILONS_DONOTREMOVEVERTICES))
6654             {
6655                 DWORD to_face = vertex_face_map[index];
6656                 DWORD from_face = vertex_face_map[point_reps[index]];
6657                 if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6658                     continue;
6659                 write_ib(indices, indices_are_32bit, i, point_reps[index]);
6660             }
6661         }
6662         mesh->lpVtbl->UnlockVertexBuffer(mesh);
6663         vertices = NULL;
6664     }
6665     else if (flags & D3DXWELDEPSILONS_WELDALL)
6666     {
6667         for (i = 0; i < 3 * This->numfaces; i++)
6668         {
6669             DWORD index = read_ib(indices, indices_are_32bit, i);
6670             DWORD to_face = vertex_face_map[index];
6671             DWORD from_face = vertex_face_map[point_reps[index]];
6672             if(attributes[to_face] != attributes[from_face] && !(flags & D3DXWELDEPSILONS_DONOTSPLIT))
6673                 continue;
6674             write_ib(indices, indices_are_32bit, i, point_reps[index]);
6675         }
6676     }
6677     mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6678     attributes = NULL;
6679     mesh->lpVtbl->UnlockIndexBuffer(mesh);
6680     indices = NULL;
6681
6682     /* Compact mesh using OptimizeInplace */
6683     optimize_flags = D3DXMESHOPT_COMPACT;
6684     hr = mesh->lpVtbl->OptimizeInplace(mesh, optimize_flags, adjacency_ptr, adjacency_out, face_remap_out, vertex_remap_out);
6685     if (FAILED(hr))
6686     {
6687         ERR("Couldn't compact mesh.\n");
6688         goto cleanup;
6689     }
6690
6691     hr = D3D_OK;
6692 cleanup:
6693     HeapFree(GetProcessHeap(), 0, adjacency_generated);
6694     HeapFree(GetProcessHeap(), 0, point_reps);
6695     HeapFree(GetProcessHeap(), 0, vertex_face_map);
6696     if (attributes) mesh->lpVtbl->UnlockAttributeBuffer(mesh);
6697     if (indices) mesh->lpVtbl->UnlockIndexBuffer(mesh);
6698     if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
6699     if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
6700
6701     return hr;
6702 }
6703
6704 /*************************************************************************
6705  * D3DXOptimizeFaces    (D3DX9_36.@)
6706  *
6707  * Re-orders the faces so the vertex cache is used optimally.
6708  *
6709  * PARAMS
6710  *   indices           [I] Pointer to an index buffer belonging to a mesh.
6711  *   num_faces         [I] Number of faces in the mesh.
6712  *   num_vertices      [I] Number of vertices in the mesh.
6713  *   indices_are_32bit [I] Specifies whether indices are 32- or 16-bit.
6714  *   face_remap        [I/O] The new order the faces should be drawn in.
6715  *
6716  * RETURNS
6717  *   Success: D3D_OK.
6718  *   Failure: D3DERR_INVALIDCALL.
6719  *
6720  * BUGS
6721  *   The face re-ordering does not use the vertex cache optimally.
6722  *
6723  */
6724 HRESULT WINAPI D3DXOptimizeFaces(LPCVOID indices,
6725                                  UINT num_faces,
6726                                  UINT num_vertices,
6727                                  BOOL indices_are_32bit,
6728                                  DWORD *face_remap)
6729 {
6730     UINT i;
6731     UINT j = num_faces - 1;
6732     UINT limit_16_bit = 2 << 15; /* According to MSDN */
6733     HRESULT hr = D3D_OK;
6734
6735     FIXME("(%p, %u, %u, %s, %p): semi-stub. Face order will not be optimal.\n",
6736           indices, num_faces, num_vertices,
6737           indices_are_32bit ? "TRUE" : "FALSE", face_remap);
6738
6739     if (!indices_are_32bit && num_faces >= limit_16_bit)
6740     {
6741         WARN("Number of faces must be less than %d when using 16-bit indices.\n",
6742              limit_16_bit);
6743         hr = D3DERR_INVALIDCALL;
6744         goto error;
6745     }
6746
6747     if (!face_remap)
6748     {
6749         WARN("Face remap pointer is NULL.\n");
6750         hr = D3DERR_INVALIDCALL;
6751         goto error;
6752     }
6753
6754     /* The faces are drawn in reverse order for simple meshes. This ordering
6755      * is not optimal for complicated meshes, but will not break anything
6756      * either. The ordering should be changed to take advantage of the vertex
6757      * cache on the graphics card.
6758      *
6759      * TODO Re-order to take advantage of vertex cache.
6760      */
6761     for (i = 0; i < num_faces; i++)
6762     {
6763         face_remap[i] = j--;
6764     }
6765
6766     return D3D_OK;
6767
6768 error:
6769     return hr;
6770 }