git.oblomov.eu Git - wine/blob - dlls/d3dx9_36/mesh.c

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