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