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