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