mesh.c

Go to the documentation of this file.

#ifdef __REACTOS__
#include "precomp.h"
#include <rmxftmpl.h>
#else
 /*
 * Mesh operations specific to D3DX9.
 *
 * Copyright (C) 2005 Henri Verbeet
 * Copyright (C) 2006 Ivan Gyurdiev
 * Copyright (C) 2009 David Adam
 * Copyright (C) 2010 Tony Wasserka
 * Copyright (C) 2011 Dylan Smith
 * Copyright (C) 2011 Michael Mc Donnell
 * Copyright (C) 2013 Christian Costa
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
 
#include <assert.h>
#include <float.h>
 
#include "d3dx9_private.h"
#undef MAKE_DDHRESULT
#include "dxfile.h"
#include "rmxfguid.h"
#include "rmxftmpl.h"
#include "wine/list.h"
#endif /* __REACTOS__ */
 
WINE_DEFAULT_DEBUG_CHANNEL(d3dx);
 
struct d3dx9_mesh
{
    ID3DXMesh ID3DXMesh_iface;
    LONG ref;
 
    DWORD numfaces;
    DWORD numvertices;
    DWORD options;
    DWORD fvf;
    IDirect3DDevice9 *device;
    D3DVERTEXELEMENT9 cached_declaration[MAX_FVF_DECL_SIZE];
    IDirect3DVertexDeclaration9 *vertex_declaration;
    UINT vertex_declaration_size;
    UINT num_elem;
    IDirect3DVertexBuffer9 *vertex_buffer;
    IDirect3DIndexBuffer9 *index_buffer;
    DWORD *attrib_buffer;
    int attrib_buffer_lock_count;
    DWORD attrib_table_size;
    D3DXATTRIBUTERANGE *attrib_table;
};
 
static const UINT d3dx_decltype_size[] =
{
   /* D3DDECLTYPE_FLOAT1    */ sizeof(FLOAT),
   /* D3DDECLTYPE_FLOAT2    */ sizeof(D3DXVECTOR2),
   /* D3DDECLTYPE_FLOAT3    */ sizeof(D3DXVECTOR3),
   /* D3DDECLTYPE_FLOAT4    */ sizeof(D3DXVECTOR4),
   /* D3DDECLTYPE_D3DCOLOR  */ sizeof(D3DCOLOR),
   /* D3DDECLTYPE_UBYTE4    */ 4 * sizeof(BYTE),
   /* D3DDECLTYPE_SHORT2    */ 2 * sizeof(SHORT),
   /* D3DDECLTYPE_SHORT4    */ 4 * sizeof(SHORT),
   /* D3DDECLTYPE_UBYTE4N   */ 4 * sizeof(BYTE),
   /* D3DDECLTYPE_SHORT2N   */ 2 * sizeof(SHORT),
   /* D3DDECLTYPE_SHORT4N   */ 4 * sizeof(SHORT),
   /* D3DDECLTYPE_USHORT2N  */ 2 * sizeof(USHORT),
   /* D3DDECLTYPE_USHORT4N  */ 4 * sizeof(USHORT),
   /* D3DDECLTYPE_UDEC3     */ 4, /* 3 * 10 bits + 2 padding */
   /* D3DDECLTYPE_DEC3N     */ 4,
   /* D3DDECLTYPE_FLOAT16_2 */ 2 * sizeof(D3DXFLOAT16),
   /* D3DDECLTYPE_FLOAT16_4 */ 4 * sizeof(D3DXFLOAT16),
};
 
static inline struct d3dx9_mesh *impl_from_ID3DXMesh(ID3DXMesh *iface)
{
    return CONTAINING_RECORD(iface, struct d3dx9_mesh, ID3DXMesh_iface);
}
 
static HRESULT WINAPI d3dx9_mesh_QueryInterface(ID3DXMesh *iface, REFIID riid, void **out)
{
    TRACE("iface %p, riid %s, out %p.\n", iface, debugstr_guid(riid), out);
 
    if (IsEqualGUID(riid, &IID_IUnknown) ||
        IsEqualGUID(riid, &IID_ID3DXBaseMesh) ||
        IsEqualGUID(riid, &IID_ID3DXMesh))
    {
        iface->lpVtbl->AddRef(iface);
        *out = iface;
        return S_OK;
    }
 
    WARN("Interface %s not found.\n", debugstr_guid(riid));
 
    return E_NOINTERFACE;
}
 
static ULONG WINAPI d3dx9_mesh_AddRef(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
    ULONG refcount = InterlockedIncrement(&mesh->ref);
 
    TRACE("%p increasing refcount to %u.\n", mesh, refcount);
 
    return refcount;
}
 
static ULONG WINAPI d3dx9_mesh_Release(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
    ULONG refcount = InterlockedDecrement(&mesh->ref);
 
    TRACE("%p decreasing refcount to %u.\n", mesh, refcount);
 
    if (!refcount)
    {
        IDirect3DIndexBuffer9_Release(mesh->index_buffer);
        IDirect3DVertexBuffer9_Release(mesh->vertex_buffer);
        if (mesh->vertex_declaration)
            IDirect3DVertexDeclaration9_Release(mesh->vertex_declaration);
        IDirect3DDevice9_Release(mesh->device);
        HeapFree(GetProcessHeap(), 0, mesh->attrib_buffer);
        HeapFree(GetProcessHeap(), 0, mesh->attrib_table);
        HeapFree(GetProcessHeap(), 0, mesh);
    }
 
    return refcount;
}
 
static HRESULT WINAPI d3dx9_mesh_DrawSubset(ID3DXMesh *iface, DWORD attrib_id)
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    HRESULT hr;
    DWORD face_start;
    DWORD face_end = 0;
    DWORD vertex_size;
 
    TRACE("iface %p, attrib_id %u.\n", iface, attrib_id);
 
    if (!This->vertex_declaration)
    {
        WARN("Can't draw a mesh with an invalid vertex declaration.\n");
        return E_FAIL;
    }
 
    vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
 
    hr = IDirect3DDevice9_SetVertexDeclaration(This->device, This->vertex_declaration);
    if (FAILED(hr)) return hr;
    hr = IDirect3DDevice9_SetStreamSource(This->device, 0, This->vertex_buffer, 0, vertex_size);
    if (FAILED(hr)) return hr;
    hr = IDirect3DDevice9_SetIndices(This->device, This->index_buffer);
    if (FAILED(hr)) return hr;
 
    while (face_end < This->numfaces)
    {
        for (face_start = face_end; face_start < This->numfaces; face_start++)
        {
            if (This->attrib_buffer[face_start] == attrib_id)
                break;
        }
        if (face_start >= This->numfaces)
            break;
        for (face_end = face_start + 1; face_end < This->numfaces; face_end++)
        {
            if (This->attrib_buffer[face_end] != attrib_id)
                break;
        }
 
        hr = IDirect3DDevice9_DrawIndexedPrimitive(This->device, D3DPT_TRIANGLELIST,
                0, 0, This->numvertices, face_start * 3, face_end - face_start);
        if (FAILED(hr)) return hr;
    }
 
    return D3D_OK;
}
 
static DWORD WINAPI d3dx9_mesh_GetNumFaces(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return mesh->numfaces;
}
 
static DWORD WINAPI d3dx9_mesh_GetNumVertices(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return mesh->numvertices;
}
 
static DWORD WINAPI d3dx9_mesh_GetFVF(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return mesh->fvf;
}
 
static void copy_declaration(D3DVERTEXELEMENT9 *dst, const D3DVERTEXELEMENT9 *src, UINT num_elem)
{
    memcpy(dst, src, num_elem * sizeof(*src));
}
 
static HRESULT WINAPI d3dx9_mesh_GetDeclaration(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, declaration %p.\n", iface, declaration);
 
    if (!declaration)
        return D3DERR_INVALIDCALL;
 
    copy_declaration(declaration, mesh->cached_declaration, mesh->num_elem);
 
    return D3D_OK;
}
 
static DWORD WINAPI d3dx9_mesh_GetNumBytesPerVertex(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return mesh->vertex_declaration_size;
}
 
static DWORD WINAPI d3dx9_mesh_GetOptions(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return mesh->options;
}
 
static HRESULT WINAPI d3dx9_mesh_GetDevice(struct ID3DXMesh *iface, struct IDirect3DDevice9 **device)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, device %p.\n", iface, device);
 
    if (!device)
        return D3DERR_INVALIDCALL;
    *device = mesh->device;
    IDirect3DDevice9_AddRef(mesh->device);
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_CloneMeshFVF(struct ID3DXMesh *iface, DWORD options, DWORD fvf,
        struct IDirect3DDevice9 *device, struct ID3DXMesh **clone_mesh)
{
    HRESULT hr;
    D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
 
    TRACE("iface %p, options %#x, fvf %#x, device %p, clone_mesh %p.\n",
            iface, options, fvf, device, clone_mesh);
 
    if (FAILED(hr = D3DXDeclaratorFromFVF(fvf, declaration)))
        return hr;
 
    return iface->lpVtbl->CloneMesh(iface, options, declaration, device, clone_mesh);
}
 
static FLOAT scale_clamp_ubyten(FLOAT value)
{
    value = value * UCHAR_MAX;
 
    if (value < 0.0f)
    {
        return 0.0f;
    }
    else
    {
        if (value > UCHAR_MAX) /* Clamp at 255 */
            return UCHAR_MAX;
        else
            return value;
    }
}
 
static FLOAT scale_clamp_shortn(FLOAT value)
{
    value = value * SHRT_MAX;
 
    /* The tests show that the range is SHRT_MIN + 1 to SHRT_MAX. */
    if (value <= SHRT_MIN)
    {
        return SHRT_MIN + 1;
    }
    else if (value > SHRT_MAX)
    {
         return SHRT_MAX;
    }
    else
    {
        return value;
    }
}
 
static FLOAT scale_clamp_ushortn(FLOAT value)
{
    value = value * USHRT_MAX;
 
    if (value < 0.0f)
    {
        return 0.0f;
    }
    else
    {
        if (value > USHRT_MAX) /* Clamp at 65535 */
            return USHRT_MAX;
        else
            return value;
    }
}
 
static INT simple_round(FLOAT value)
{
    int res = (INT)(value + 0.5f);
 
    return res;
}
 
static void convert_float4(BYTE *dst, const D3DXVECTOR4 *src, D3DDECLTYPE type_dst)
{
    BOOL fixme_once = FALSE;
 
    switch (type_dst)
    {
        case D3DDECLTYPE_FLOAT1:
        {
            FLOAT *dst_ptr = (FLOAT*)dst;
            *dst_ptr = src->x;
            break;
        }
        case D3DDECLTYPE_FLOAT2:
        {
            D3DXVECTOR2 *dst_ptr = (D3DXVECTOR2*)dst;
            dst_ptr->x = src->x;
            dst_ptr->y = src->y;
            break;
        }
        case D3DDECLTYPE_FLOAT3:
        {
            D3DXVECTOR3 *dst_ptr = (D3DXVECTOR3*)dst;
            dst_ptr->x = src->x;
            dst_ptr->y = src->y;
            dst_ptr->z = src->z;
            break;
        }
        case D3DDECLTYPE_FLOAT4:
        {
            D3DXVECTOR4 *dst_ptr = (D3DXVECTOR4*)dst;
            dst_ptr->x = src->x;
            dst_ptr->y = src->y;
            dst_ptr->z = src->z;
            dst_ptr->w = src->w;
            break;
        }
        case D3DDECLTYPE_D3DCOLOR:
        {
            dst[0] = (BYTE)simple_round(scale_clamp_ubyten(src->z));
            dst[1] = (BYTE)simple_round(scale_clamp_ubyten(src->y));
            dst[2] = (BYTE)simple_round(scale_clamp_ubyten(src->x));
            dst[3] = (BYTE)simple_round(scale_clamp_ubyten(src->w));
            break;
        }
        case D3DDECLTYPE_UBYTE4:
        {
            dst[0] = src->x < 0.0f ? 0 : (BYTE)simple_round(src->x);
            dst[1] = src->y < 0.0f ? 0 : (BYTE)simple_round(src->y);
            dst[2] = src->z < 0.0f ? 0 : (BYTE)simple_round(src->z);
            dst[3] = src->w < 0.0f ? 0 : (BYTE)simple_round(src->w);
            break;
        }
        case D3DDECLTYPE_SHORT2:
        {
            SHORT *dst_ptr = (SHORT*)dst;
            dst_ptr[0] = (SHORT)simple_round(src->x);
            dst_ptr[1] = (SHORT)simple_round(src->y);
            break;
        }
        case D3DDECLTYPE_SHORT4:
        {
            SHORT *dst_ptr = (SHORT*)dst;
            dst_ptr[0] = (SHORT)simple_round(src->x);
            dst_ptr[1] = (SHORT)simple_round(src->y);
            dst_ptr[2] = (SHORT)simple_round(src->z);
            dst_ptr[3] = (SHORT)simple_round(src->w);
            break;
        }
        case D3DDECLTYPE_UBYTE4N:
        {
            dst[0] = (BYTE)simple_round(scale_clamp_ubyten(src->x));
            dst[1] = (BYTE)simple_round(scale_clamp_ubyten(src->y));
            dst[2] = (BYTE)simple_round(scale_clamp_ubyten(src->z));
            dst[3] = (BYTE)simple_round(scale_clamp_ubyten(src->w));
            break;
        }
        case D3DDECLTYPE_SHORT2N:
        {
            SHORT *dst_ptr = (SHORT*)dst;
            dst_ptr[0] = (SHORT)simple_round(scale_clamp_shortn(src->x));
            dst_ptr[1] = (SHORT)simple_round(scale_clamp_shortn(src->y));
            break;
        }
        case D3DDECLTYPE_SHORT4N:
        {
            SHORT *dst_ptr = (SHORT*)dst;
            dst_ptr[0] = (SHORT)simple_round(scale_clamp_shortn(src->x));
            dst_ptr[1] = (SHORT)simple_round(scale_clamp_shortn(src->y));
            dst_ptr[2] = (SHORT)simple_round(scale_clamp_shortn(src->z));
            dst_ptr[3] = (SHORT)simple_round(scale_clamp_shortn(src->w));
            break;
        }
        case D3DDECLTYPE_USHORT2N:
        {
            USHORT *dst_ptr = (USHORT*)dst;
            dst_ptr[0] = (USHORT)simple_round(scale_clamp_ushortn(src->x));
            dst_ptr[1] = (USHORT)simple_round(scale_clamp_ushortn(src->y));
            break;
        }
        case D3DDECLTYPE_USHORT4N:
        {
            USHORT *dst_ptr = (USHORT*)dst;
            dst_ptr[0] = (USHORT)simple_round(scale_clamp_ushortn(src->x));
            dst_ptr[1] = (USHORT)simple_round(scale_clamp_ushortn(src->y));
            dst_ptr[2] = (USHORT)simple_round(scale_clamp_ushortn(src->z));
            dst_ptr[3] = (USHORT)simple_round(scale_clamp_ushortn(src->w));
            break;
        }
        case D3DDECLTYPE_FLOAT16_2:
        {
            D3DXFloat32To16Array((D3DXFLOAT16*)dst, (FLOAT*)src, 2);
            break;
        }
        case D3DDECLTYPE_FLOAT16_4:
        {
            D3DXFloat32To16Array((D3DXFLOAT16*)dst, (FLOAT*)src, 4);
            break;
        }
        default:
            if (!fixme_once++)
                FIXME("Conversion from D3DDECLTYPE_FLOAT4 to %d not implemented.\n", type_dst);
            break;
    }
}
 
static void convert_component(BYTE *dst, BYTE *src, D3DDECLTYPE type_dst, D3DDECLTYPE type_src)
{
    BOOL fixme_once = FALSE;
 
    switch (type_src)
    {
        case D3DDECLTYPE_FLOAT1:
        {
            FLOAT *src_ptr = (FLOAT*)src;
            D3DXVECTOR4 src_float4 = {*src_ptr, 0.0f, 0.0f, 1.0f};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_FLOAT2:
        {
            D3DXVECTOR2 *src_ptr = (D3DXVECTOR2*)src;
            D3DXVECTOR4 src_float4 = {src_ptr->x, src_ptr->y, 0.0f, 1.0f};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_FLOAT3:
        {
            D3DXVECTOR3 *src_ptr = (D3DXVECTOR3*)src;
            D3DXVECTOR4 src_float4 = {src_ptr->x, src_ptr->y, src_ptr->z, 1.0f};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_FLOAT4:
        {
            D3DXVECTOR4 *src_ptr = (D3DXVECTOR4*)src;
            D3DXVECTOR4 src_float4 = {src_ptr->x, src_ptr->y, src_ptr->z, src_ptr->w};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_D3DCOLOR:
        {
            D3DXVECTOR4 src_float4 =
            {
                (FLOAT)src[2]/UCHAR_MAX,
                (FLOAT)src[1]/UCHAR_MAX,
                (FLOAT)src[0]/UCHAR_MAX,
                (FLOAT)src[3]/UCHAR_MAX
            };
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_UBYTE4:
        {
            D3DXVECTOR4 src_float4 = {src[0], src[1], src[2], src[3]};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_SHORT2:
        {
            SHORT *src_ptr = (SHORT*)src;
            D3DXVECTOR4 src_float4 = {src_ptr[0], src_ptr[1], 0.0f, 1.0f};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_SHORT4:
        {
            SHORT *src_ptr = (SHORT*)src;
            D3DXVECTOR4 src_float4 = {src_ptr[0], src_ptr[1], src_ptr[2], src_ptr[3]};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_UBYTE4N:
        {
            D3DXVECTOR4 src_float4 =
            {
                (FLOAT)src[0]/UCHAR_MAX,
                (FLOAT)src[1]/UCHAR_MAX,
                (FLOAT)src[2]/UCHAR_MAX,
                (FLOAT)src[3]/UCHAR_MAX
            };
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_SHORT2N:
        {
            SHORT *src_ptr = (SHORT*)src;
            D3DXVECTOR4 src_float4 = {(FLOAT)src_ptr[0]/SHRT_MAX, (FLOAT)src_ptr[1]/SHRT_MAX, 0.0f, 1.0f};
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_SHORT4N:
        {
            SHORT *src_ptr = (SHORT*)src;
            D3DXVECTOR4 src_float4 =
            {
                (FLOAT)src_ptr[0]/SHRT_MAX,
                (FLOAT)src_ptr[1]/SHRT_MAX,
                (FLOAT)src_ptr[2]/SHRT_MAX,
                (FLOAT)src_ptr[3]/SHRT_MAX
            };
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_FLOAT16_2:
        {
            D3DXVECTOR4 src_float4 = {0.0f, 0.0f, 0.0f, 1.0f};
            D3DXFloat16To32Array((FLOAT*)&src_float4, (D3DXFLOAT16*)src, 2);
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        case D3DDECLTYPE_FLOAT16_4:
        {
            D3DXVECTOR4 src_float4;
            D3DXFloat16To32Array((FLOAT*)&src_float4, (D3DXFLOAT16*)src, 4);
            convert_float4(dst, &src_float4, type_dst);
            break;
        }
        default:
            if (!fixme_once++)
                FIXME("Conversion of D3DDECLTYPE %d to %d not implemented.\n", type_src, type_dst);
            break;
    }
}
 
static INT get_equivalent_declaration_index(D3DVERTEXELEMENT9 orig_declaration, D3DVERTEXELEMENT9 *declaration)
{
    INT i;
 
    for (i = 0; declaration[i].Stream != 0xff; i++)
    {
        if (orig_declaration.Usage == declaration[i].Usage
            && orig_declaration.UsageIndex == declaration[i].UsageIndex)
        {
            return i;
        }
    }
 
    return -1;
}
 
static HRESULT convert_vertex_buffer(ID3DXMesh *mesh_dst, ID3DXMesh *mesh_src)
{
    HRESULT hr;
    D3DVERTEXELEMENT9 orig_declaration[MAX_FVF_DECL_SIZE] = {D3DDECL_END()};
    D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE] = {D3DDECL_END()};
    BYTE *vb_dst = NULL;
    BYTE *vb_src = NULL;
    UINT i;
    UINT num_vertices = mesh_src->lpVtbl->GetNumVertices(mesh_src);
    UINT dst_vertex_size = mesh_dst->lpVtbl->GetNumBytesPerVertex(mesh_dst);
    UINT src_vertex_size = mesh_src->lpVtbl->GetNumBytesPerVertex(mesh_src);
 
    hr = mesh_src->lpVtbl->GetDeclaration(mesh_src, orig_declaration);
    if (FAILED(hr)) return hr;
    hr = mesh_dst->lpVtbl->GetDeclaration(mesh_dst, declaration);
    if (FAILED(hr)) return hr;
 
    hr = mesh_src->lpVtbl->LockVertexBuffer(mesh_src, D3DLOCK_READONLY, (void**)&vb_src);
    if (FAILED(hr)) goto cleanup;
    hr = mesh_dst->lpVtbl->LockVertexBuffer(mesh_dst, 0, (void**)&vb_dst);
    if (FAILED(hr)) goto cleanup;
 
    /* Clear all new fields by clearing the entire vertex buffer. */
    memset(vb_dst, 0, num_vertices * dst_vertex_size);
 
    for (i = 0; orig_declaration[i].Stream != 0xff; i++)
    {
        INT eq_idx = get_equivalent_declaration_index(orig_declaration[i], declaration);
 
        if (eq_idx >= 0)
        {
            UINT j;
            for (j = 0; j < num_vertices; j++)
            {
                UINT idx_dst = dst_vertex_size * j + declaration[eq_idx].Offset;
                UINT idx_src = src_vertex_size * j + orig_declaration[i].Offset;
                UINT type_size = d3dx_decltype_size[orig_declaration[i].Type];
 
                if (orig_declaration[i].Type == declaration[eq_idx].Type)
                    memcpy(&vb_dst[idx_dst], &vb_src[idx_src], type_size);
                else
                   convert_component(&vb_dst[idx_dst], &vb_src[idx_src], declaration[eq_idx].Type, orig_declaration[i].Type);
            }
        }
    }
 
    hr = D3D_OK;
cleanup:
    if (vb_dst) mesh_dst->lpVtbl->UnlockVertexBuffer(mesh_dst);
    if (vb_src) mesh_src->lpVtbl->UnlockVertexBuffer(mesh_src);
 
    return hr;
}
 
static BOOL declaration_equals(const D3DVERTEXELEMENT9 *declaration1, const D3DVERTEXELEMENT9 *declaration2)
{
    UINT size1 = 0, size2 = 0;
 
    /* Find the size of each declaration */
    while (declaration1[size1].Stream != 0xff) size1++;
    while (declaration2[size2].Stream != 0xff) size2++;
 
    /* If not same size then they are definitely not equal */
    if (size1 != size2)
        return FALSE;
 
    /* Check that all components are the same */
    if (memcmp(declaration1, declaration2, size1*sizeof(*declaration1)) == 0)
        return TRUE;
 
    return FALSE;
}
 
static HRESULT WINAPI d3dx9_mesh_CloneMesh(struct ID3DXMesh *iface, DWORD options,
        const D3DVERTEXELEMENT9 *declaration, struct IDirect3DDevice9 *device, struct ID3DXMesh **clone_mesh_out)
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    struct d3dx9_mesh *cloned_this;
    ID3DXMesh *clone_mesh;
    D3DVERTEXELEMENT9 orig_declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
    void *data_in, *data_out;
    DWORD vertex_size;
    HRESULT hr;
    BOOL same_declaration;
 
    TRACE("iface %p, options %#x, declaration %p, device %p, clone_mesh_out %p.\n",
            iface, options, declaration, device, clone_mesh_out);
 
    if (!clone_mesh_out)
        return D3DERR_INVALIDCALL;
 
    hr = iface->lpVtbl->GetDeclaration(iface, orig_declaration);
    if (FAILED(hr)) return hr;
 
    hr = D3DXCreateMesh(This->numfaces, This->numvertices, options & ~D3DXMESH_VB_SHARE,
                        declaration, device, &clone_mesh);
    if (FAILED(hr)) return hr;
 
    cloned_this = impl_from_ID3DXMesh(clone_mesh);
    vertex_size = clone_mesh->lpVtbl->GetNumBytesPerVertex(clone_mesh);
    same_declaration = declaration_equals(declaration, orig_declaration);
 
    if (options & D3DXMESH_VB_SHARE) {
        if (!same_declaration) {
            hr = D3DERR_INVALIDCALL;
            goto error;
        }
        IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
        /* FIXME: refactor to avoid creating a new vertex buffer */
        IDirect3DVertexBuffer9_Release(cloned_this->vertex_buffer);
        cloned_this->vertex_buffer = This->vertex_buffer;
    } else if (same_declaration) {
        hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, &data_in);
        if (FAILED(hr)) goto error;
        hr = clone_mesh->lpVtbl->LockVertexBuffer(clone_mesh, 0, &data_out);
        if (FAILED(hr)) {
            iface->lpVtbl->UnlockVertexBuffer(iface);
            goto error;
        }
        memcpy(data_out, data_in, This->numvertices * vertex_size);
        clone_mesh->lpVtbl->UnlockVertexBuffer(clone_mesh);
        iface->lpVtbl->UnlockVertexBuffer(iface);
    } else {
        hr = convert_vertex_buffer(clone_mesh, iface);
        if (FAILED(hr)) goto error;
    }
 
    hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, &data_in);
    if (FAILED(hr)) goto error;
    hr = clone_mesh->lpVtbl->LockIndexBuffer(clone_mesh, 0, &data_out);
    if (FAILED(hr)) {
        iface->lpVtbl->UnlockIndexBuffer(iface);
        goto error;
    }
    if ((options ^ This->options) & D3DXMESH_32BIT) {
        DWORD i;
        if (options & D3DXMESH_32BIT) {
            for (i = 0; i < This->numfaces * 3; i++)
                ((DWORD*)data_out)[i] = ((WORD*)data_in)[i];
        } else {
            for (i = 0; i < This->numfaces * 3; i++)
                ((WORD*)data_out)[i] = ((DWORD*)data_in)[i];
        }
    } else {
        memcpy(data_out, data_in, This->numfaces * 3 * (options & D3DXMESH_32BIT ? 4 : 2));
    }
    clone_mesh->lpVtbl->UnlockIndexBuffer(clone_mesh);
    iface->lpVtbl->UnlockIndexBuffer(iface);
 
    memcpy(cloned_this->attrib_buffer, This->attrib_buffer, This->numfaces * sizeof(*This->attrib_buffer));
 
    if (This->attrib_table_size)
    {
        cloned_this->attrib_table_size = This->attrib_table_size;
        cloned_this->attrib_table = HeapAlloc(GetProcessHeap(), 0, This->attrib_table_size * sizeof(*This->attrib_table));
        if (!cloned_this->attrib_table) {
            hr = E_OUTOFMEMORY;
            goto error;
        }
        memcpy(cloned_this->attrib_table, This->attrib_table, This->attrib_table_size * sizeof(*This->attrib_table));
    }
 
    *clone_mesh_out = clone_mesh;
 
    return D3D_OK;
error:
    IUnknown_Release(clone_mesh);
    return hr;
}
 
static HRESULT WINAPI d3dx9_mesh_GetVertexBuffer(struct ID3DXMesh *iface,
        struct IDirect3DVertexBuffer9 **vertex_buffer)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, vertex_buffer %p.\n", iface, vertex_buffer);
 
    if (!vertex_buffer)
        return D3DERR_INVALIDCALL;
    *vertex_buffer = mesh->vertex_buffer;
    IDirect3DVertexBuffer9_AddRef(mesh->vertex_buffer);
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_GetIndexBuffer(struct ID3DXMesh *iface,
        struct IDirect3DIndexBuffer9 **index_buffer)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, index_buffer %p.\n", iface, index_buffer);
 
    if (!index_buffer)
        return D3DERR_INVALIDCALL;
    *index_buffer = mesh->index_buffer;
    IDirect3DIndexBuffer9_AddRef(mesh->index_buffer);
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_LockVertexBuffer(ID3DXMesh *iface, DWORD flags, void **data)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, flags %#x, data %p.\n", iface, flags, data);
 
    return IDirect3DVertexBuffer9_Lock(mesh->vertex_buffer, 0, 0, data, flags);
}
 
static HRESULT WINAPI d3dx9_mesh_UnlockVertexBuffer(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return IDirect3DVertexBuffer9_Unlock(mesh->vertex_buffer);
}
 
static HRESULT WINAPI d3dx9_mesh_LockIndexBuffer(ID3DXMesh *iface, DWORD flags, void **data)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, flags %#x, data %p.\n", iface, flags, data);
 
    return IDirect3DIndexBuffer9_Lock(mesh->index_buffer, 0, 0, data, flags);
}
 
static HRESULT WINAPI d3dx9_mesh_UnlockIndexBuffer(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p.\n", iface);
 
    return IDirect3DIndexBuffer9_Unlock(mesh->index_buffer);
}
 
/* FIXME: This looks just wrong, we never check *attrib_table_size before
 * copying the data. */
static HRESULT WINAPI d3dx9_mesh_GetAttributeTable(ID3DXMesh *iface,
        D3DXATTRIBUTERANGE *attrib_table, DWORD *attrib_table_size)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, attrib_table %p, attrib_table_size %p.\n",
            iface, attrib_table, attrib_table_size);
 
    if (attrib_table_size)
        *attrib_table_size = mesh->attrib_table_size;
 
    if (attrib_table)
        memcpy(attrib_table, mesh->attrib_table, mesh->attrib_table_size * sizeof(*attrib_table));
 
    return D3D_OK;
}
 
struct edge_face
{
    struct list entry;
    DWORD v2;
    DWORD face;
};
 
struct edge_face_map
{
    struct list *lists;
    struct edge_face *entries;
};
 
/* Builds up a map of which face a new edge belongs to. That way the adjacency
 * of another edge can be looked up. An edge has an adjacent face if there
 * is an edge going in the opposite direction in the map. For example if the
 * edge (v1, v2) belongs to face 4, and there is a mapping (v2, v1)->7, then
 * face 4 and 7 are adjacent.
 *
 * Each edge might have been replaced with another edge, or none at all. There
 * is at most one edge to face mapping, i.e. an edge can only belong to one
 * face.
 */
static HRESULT init_edge_face_map(struct edge_face_map *edge_face_map, const DWORD *index_buffer,
        const DWORD *point_reps, DWORD num_faces)
{
    DWORD face, edge;
    DWORD i;
 
    edge_face_map->lists = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->lists));
    if (!edge_face_map->lists) return E_OUTOFMEMORY;
 
    edge_face_map->entries = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->entries));
    if (!edge_face_map->entries) return E_OUTOFMEMORY;
 
 
    /* Initialize all lists */
    for (i = 0; i < 3 * num_faces; i++)
    {
        list_init(&edge_face_map->lists[i]);
    }
    /* Build edge face mapping */
    for (face = 0; face < num_faces; face++)
    {
        for (edge = 0; edge < 3; edge++)
        {
            DWORD v1 = index_buffer[3*face + edge];
            DWORD v2 = index_buffer[3*face + (edge+1)%3];
            DWORD new_v1 = point_reps[v1]; /* What v1 has been replaced with */
            DWORD new_v2 = point_reps[v2];
 
            if (v1 != v2) /* Only map non-collapsed edges */
            {
                i = 3*face + edge;
                edge_face_map->entries[i].v2 = new_v2;
                edge_face_map->entries[i].face = face;
                list_add_head(&edge_face_map->lists[new_v1], &edge_face_map->entries[i].entry);
            }
        }
    }
 
    return D3D_OK;
}
 
static DWORD find_adjacent_face(struct edge_face_map *edge_face_map, DWORD vertex1, DWORD vertex2, DWORD num_faces)
{
    struct edge_face *edge_face_ptr;
 
    LIST_FOR_EACH_ENTRY(edge_face_ptr, &edge_face_map->lists[vertex2], struct edge_face, entry)
    {
        if (edge_face_ptr->v2 == vertex1)
            return edge_face_ptr->face;
    }
 
    return -1;
}
 
static DWORD *generate_identity_point_reps(DWORD num_vertices)
{
        DWORD *id_point_reps;
        DWORD i;
 
        id_point_reps = HeapAlloc(GetProcessHeap(), 0, num_vertices * sizeof(*id_point_reps));
        if (!id_point_reps)
            return NULL;
 
        for (i = 0; i < num_vertices; i++)
        {
            id_point_reps[i] = i;
        }
 
        return id_point_reps;
}
 
static HRESULT WINAPI d3dx9_mesh_ConvertPointRepsToAdjacency(ID3DXMesh *iface,
        const DWORD *point_reps, DWORD *adjacency)
{
    HRESULT hr;
    DWORD num_faces = iface->lpVtbl->GetNumFaces(iface);
    DWORD num_vertices = iface->lpVtbl->GetNumVertices(iface);
    DWORD options = iface->lpVtbl->GetOptions(iface);
    BOOL indices_are_16_bit = !(options & D3DXMESH_32BIT);
    DWORD *ib = NULL;
    void *ib_ptr = NULL;
    DWORD face;
    DWORD edge;
    struct edge_face_map edge_face_map = {0};
    const DWORD *point_reps_ptr = NULL;
    DWORD *id_point_reps = NULL;
 
    TRACE("iface %p, point_reps %p, adjacency %p.\n", iface, point_reps, adjacency);
 
    if (!adjacency) return D3DERR_INVALIDCALL;
 
    if (!point_reps) /* Identity point reps */
    {
        id_point_reps = generate_identity_point_reps(num_vertices);
        if (!id_point_reps)
        {
            hr = E_OUTOFMEMORY;
            goto cleanup;
        }
 
        point_reps_ptr = id_point_reps;
    }
    else
    {
        point_reps_ptr = point_reps;
    }
 
    hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, &ib_ptr);
    if (FAILED(hr)) goto cleanup;
 
    if (indices_are_16_bit)
    {
        /* Widen 16 bit to 32 bit */
        DWORD i;
        WORD *ib_16bit = ib_ptr;
        ib = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(DWORD));
        if (!ib)
        {
            hr = E_OUTOFMEMORY;
            goto cleanup;
        }
        for (i = 0; i < 3 * num_faces; i++)
        {
            ib[i] = ib_16bit[i];
        }
    }
    else
    {
        ib = ib_ptr;
    }
 
    hr = init_edge_face_map(&edge_face_map, ib, point_reps_ptr, num_faces);
    if (FAILED(hr)) goto cleanup;
 
    /* Create adjacency */
    for (face = 0; face < num_faces; face++)
    {
        for (edge = 0; edge < 3; edge++)
        {
            DWORD v1 = ib[3*face + edge];
            DWORD v2 = ib[3*face + (edge+1)%3];
            DWORD new_v1 = point_reps_ptr[v1];
            DWORD new_v2 = point_reps_ptr[v2];
            DWORD adj_face;
 
            adj_face = find_adjacent_face(&edge_face_map, new_v1, new_v2, num_faces);
            adjacency[3*face + edge] = adj_face;
        }
    }
 
    hr = D3D_OK;
cleanup:
    HeapFree(GetProcessHeap(), 0, id_point_reps);
    if (indices_are_16_bit) HeapFree(GetProcessHeap(), 0, ib);
    HeapFree(GetProcessHeap(), 0, edge_face_map.lists);
    HeapFree(GetProcessHeap(), 0, edge_face_map.entries);
    if(ib_ptr) iface->lpVtbl->UnlockIndexBuffer(iface);
    return hr;
}
 
/* ConvertAdjacencyToPointReps helper function.
 *
 * Goes around the edges of each face and replaces the vertices in any adjacent
 * face's edge with its own vertices(if its vertices have a lower index). This
 * way as few as possible low index vertices are shared among the faces. The
 * re-ordered index buffer is stored in new_indices.
 *
 * The vertices in a point representation must be ordered sequentially, e.g.
 * index 5 holds the index of the vertex that replaces vertex 5, i.e. if
 * vertex 5 is replaced by vertex 3 then index 5 would contain 3. If no vertex
 * replaces it, then it contains the same number as the index itself, e.g.
 * index 5 would contain 5. */
static HRESULT propagate_face_vertices(const DWORD *adjacency, DWORD *point_reps,
        const DWORD *indices, DWORD *new_indices, DWORD face, DWORD numfaces)
{
    const unsigned int VERTS_PER_FACE = 3;
    DWORD edge, opp_edge;
    DWORD face_base = VERTS_PER_FACE * face;
 
    for (edge = 0; edge < VERTS_PER_FACE; edge++)
    {
        DWORD adj_face = adjacency[face_base + edge];
        DWORD adj_face_base;
        DWORD i;
        if (adj_face == -1) /* No adjacent face. */
            continue;
        else if (adj_face >= numfaces)
        {
            /* This throws exception on Windows */
            WARN("Index out of bounds. Got %d expected less than %d.\n",
                adj_face, numfaces);
            return D3DERR_INVALIDCALL;
        }
        adj_face_base = 3 * adj_face;
 
        /* Find opposite edge in adjacent face. */
        for (opp_edge = 0; opp_edge < VERTS_PER_FACE; opp_edge++)
        {
            DWORD opp_edge_index = adj_face_base + opp_edge;
            if (adjacency[opp_edge_index] == face)
                break; /* Found opposite edge. */
        }
 
        /* Replaces vertices in opposite edge with vertices from current edge. */
        for (i = 0; i < 2; i++)
        {
            DWORD from = face_base + (edge + (1 - i)) % VERTS_PER_FACE;
            DWORD to = adj_face_base + (opp_edge + i) % VERTS_PER_FACE;
 
            /* Propagate lowest index. */
            if (new_indices[to] > new_indices[from])
            {
                new_indices[to] = new_indices[from];
                point_reps[indices[to]] = new_indices[from];
            }
        }
    }
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_ConvertAdjacencyToPointReps(ID3DXMesh *iface,
        const DWORD *adjacency, DWORD *point_reps)
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    HRESULT hr;
    DWORD face;
    DWORD i;
    DWORD *indices = NULL;
    WORD *indices_16bit = NULL;
    DWORD *new_indices = NULL;
    const unsigned int VERTS_PER_FACE = 3;
 
    TRACE("iface %p, adjacency %p, point_reps %p.\n", iface, adjacency, point_reps);
 
    if (!adjacency)
    {
        WARN("NULL adjacency.\n");
        hr = D3DERR_INVALIDCALL;
        goto cleanup;
    }
 
    if (!point_reps)
    {
        WARN("NULL point_reps.\n");
        hr = D3DERR_INVALIDCALL;
        goto cleanup;
    }
 
    /* Should never happen as CreateMesh does not allow meshes with 0 faces */
    if (This->numfaces == 0)
    {
        ERR("Number of faces was zero.\n");
        hr = D3DERR_INVALIDCALL;
        goto cleanup;
    }
 
    new_indices = HeapAlloc(GetProcessHeap(), 0, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
    if (!new_indices)
    {
        hr = E_OUTOFMEMORY;
        goto cleanup;
    }
 
    if (This->options & D3DXMESH_32BIT)
    {
        hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices);
        if (FAILED(hr)) goto cleanup;
        memcpy(new_indices, indices, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
    }
    else
    {
        /* Make a widening copy of indices_16bit into indices and new_indices
         * in order to re-use the helper function */
        hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices_16bit);
        if (FAILED(hr)) goto cleanup;
        indices = HeapAlloc(GetProcessHeap(), 0, VERTS_PER_FACE * This->numfaces * sizeof(*indices));
        if (!indices)
        {
            hr = E_OUTOFMEMORY;
            goto cleanup;
        }
        for (i = 0; i < VERTS_PER_FACE * This->numfaces; i++)
        {
            new_indices[i] = indices_16bit[i];
            indices[i] = indices_16bit[i];
        }
    }
 
    /* Vertices are ordered sequentially in the point representation. */
    for (i = 0; i < This->numvertices; i++)
    {
        point_reps[i] = i;
    }
 
    /* Propagate vertices with low indices so as few vertices as possible
     * are used in the mesh.
     */
    for (face = 0; face < This->numfaces; face++)
    {
        hr = propagate_face_vertices(adjacency, point_reps, indices, new_indices, face, This->numfaces);
        if (FAILED(hr)) goto cleanup;
    }
    /* Go in opposite direction to catch all face orderings */
    for (face = 0; face < This->numfaces; face++)
    {
        hr = propagate_face_vertices(adjacency, point_reps,
                                     indices, new_indices,
                                     (This->numfaces - 1) - face, This->numfaces);
        if (FAILED(hr)) goto cleanup;
    }
 
    hr = D3D_OK;
cleanup:
    if (This->options & D3DXMESH_32BIT)
    {
        if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
    }
    else
    {
        if (indices_16bit) iface->lpVtbl->UnlockIndexBuffer(iface);
        HeapFree(GetProcessHeap(), 0, indices);
    }
    HeapFree(GetProcessHeap(), 0, new_indices);
    return hr;
}
 
struct vertex_metadata {
  float key;
  DWORD vertex_index;
  DWORD first_shared_index;
};
 
static int __cdecl compare_vertex_keys(const void *a, const void *b)
{
    const struct vertex_metadata *left = a;
    const struct vertex_metadata *right = b;
    if (left->key == right->key)
        return 0;
    return left->key < right->key ? -1 : 1;
}
 
static HRESULT WINAPI d3dx9_mesh_GenerateAdjacency(ID3DXMesh *iface, float epsilon, DWORD *adjacency)
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    HRESULT hr;
    BYTE *vertices = NULL;
    const DWORD *indices = NULL;
    DWORD vertex_size;
    DWORD buffer_size;
    /* sort the vertices by (x + y + z) to quickly find coincident vertices */
    struct vertex_metadata *sorted_vertices;
    /* shared_indices links together identical indices in the index buffer so
     * that adjacency checks can be limited to faces sharing a vertex */
    DWORD *shared_indices = NULL;
    const FLOAT epsilon_sq = epsilon * epsilon;
    DWORD i;
 
    TRACE("iface %p, epsilon %.8e, adjacency %p.\n", iface, epsilon, adjacency);
 
    if (!adjacency)
        return D3DERR_INVALIDCALL;
 
    buffer_size = This->numfaces * 3 * sizeof(*shared_indices) + This->numvertices * sizeof(*sorted_vertices);
    if (!(This->options & D3DXMESH_32BIT))
        buffer_size += This->numfaces * 3 * sizeof(*indices);
    shared_indices = HeapAlloc(GetProcessHeap(), 0, buffer_size);
    if (!shared_indices)
        return E_OUTOFMEMORY;
    sorted_vertices = (struct vertex_metadata*)(shared_indices + This->numfaces * 3);
 
    hr = iface->lpVtbl->LockVertexBuffer(iface, D3DLOCK_READONLY, (void**)&vertices);
    if (FAILED(hr)) goto cleanup;
    hr = iface->lpVtbl->LockIndexBuffer(iface, D3DLOCK_READONLY, (void**)&indices);
    if (FAILED(hr)) goto cleanup;
 
    if (!(This->options & D3DXMESH_32BIT)) {
        const WORD *word_indices = (const WORD*)indices;
        DWORD *dword_indices = (DWORD*)(sorted_vertices + This->numvertices);
        indices = dword_indices;
        for (i = 0; i < This->numfaces * 3; i++)
            *dword_indices++ = *word_indices++;
    }
 
    vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
    for (i = 0; i < This->numvertices; i++) {
        D3DXVECTOR3 *vertex = (D3DXVECTOR3*)(vertices + vertex_size * i);
        sorted_vertices[i].first_shared_index = -1;
        sorted_vertices[i].key = vertex->x + vertex->y + vertex->z;
        sorted_vertices[i].vertex_index = i;
    }
    for (i = 0; i < This->numfaces * 3; i++) {
        DWORD *first_shared_index = &sorted_vertices[indices[i]].first_shared_index;
        shared_indices[i] = *first_shared_index;
        *first_shared_index = i;
        adjacency[i] = -1;
    }
    qsort(sorted_vertices, This->numvertices, sizeof(*sorted_vertices), compare_vertex_keys);
 
    for (i = 0; i < This->numvertices; i++) {
        struct vertex_metadata *sorted_vertex_a = &sorted_vertices[i];
        D3DXVECTOR3 *vertex_a = (D3DXVECTOR3*)(vertices + sorted_vertex_a->vertex_index * vertex_size);
        DWORD shared_index_a = sorted_vertex_a->first_shared_index;
 
        while (shared_index_a != -1) {
            DWORD j = i;
            DWORD shared_index_b = shared_indices[shared_index_a];
            struct vertex_metadata *sorted_vertex_b = sorted_vertex_a;
 
            while (TRUE) {
                while (shared_index_b != -1) {
                    /* faces are adjacent if they have another coincident vertex */
                    DWORD base_a = (shared_index_a / 3) * 3;
                    DWORD base_b = (shared_index_b / 3) * 3;
                    BOOL adjacent = FALSE;
                    int k;
 
                    for (k = 0; k < 3; k++) {
                        if (adjacency[base_b + k] == shared_index_a / 3) {
                            adjacent = TRUE;
                            break;
                        }
                    }
                    if (!adjacent) {
                        for (k = 1; k <= 2; k++) {
                            DWORD vertex_index_a = base_a + (shared_index_a + k) % 3;
                            DWORD vertex_index_b = base_b + (shared_index_b + (3 - k)) % 3;
                            adjacent = indices[vertex_index_a] == indices[vertex_index_b];
                            if (!adjacent && epsilon >= 0.0f) {
                                D3DXVECTOR3 delta = {0.0f, 0.0f, 0.0f};
                                FLOAT length_sq;
 
                                D3DXVec3Subtract(&delta,
                                                 (D3DXVECTOR3*)(vertices + indices[vertex_index_a] * vertex_size),
                                                 (D3DXVECTOR3*)(vertices + indices[vertex_index_b] * vertex_size));
                                length_sq = D3DXVec3LengthSq(&delta);
                                adjacent = epsilon == 0.0f ? length_sq == 0.0f : length_sq < epsilon_sq;
                            }
                            if (adjacent) {
                                DWORD adj_a = base_a + 2 - (vertex_index_a + shared_index_a + 1) % 3;
                                DWORD adj_b = base_b + 2 - (vertex_index_b + shared_index_b + 1) % 3;
                                if (adjacency[adj_a] == -1 && adjacency[adj_b] == -1) {
                                    adjacency[adj_a] = base_b / 3;
                                    adjacency[adj_b] = base_a / 3;
                                    break;
                                }
                            }
                        }
                    }
 
                    shared_index_b = shared_indices[shared_index_b];
                }
                while (++j < This->numvertices) {
                    D3DXVECTOR3 *vertex_b;
 
                    sorted_vertex_b++;
                    if (sorted_vertex_b->key - sorted_vertex_a->key > epsilon * 3.0f) {
                        /* no more coincident vertices to try */
                        j = This->numvertices;
                        break;
                    }
                    /* check for coincidence */
                    vertex_b = (D3DXVECTOR3*)(vertices + sorted_vertex_b->vertex_index * vertex_size);
                    if (fabsf(vertex_a->x - vertex_b->x) <= epsilon &&
                        fabsf(vertex_a->y - vertex_b->y) <= epsilon &&
                        fabsf(vertex_a->z - vertex_b->z) <= epsilon)
                    {
                        break;
                    }
                }
                if (j >= This->numvertices)
                    break;
                shared_index_b = sorted_vertex_b->first_shared_index;
            }
 
            sorted_vertex_a->first_shared_index = shared_indices[sorted_vertex_a->first_shared_index];
            shared_index_a = sorted_vertex_a->first_shared_index;
        }
    }
 
    hr = D3D_OK;
cleanup:
    if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
    if (vertices) iface->lpVtbl->UnlockVertexBuffer(iface);
    HeapFree(GetProcessHeap(), 0, shared_indices);
    return hr;
}
 
static HRESULT WINAPI d3dx9_mesh_UpdateSemantics(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    HRESULT hr;
    UINT vertex_declaration_size;
    int i;
 
    TRACE("iface %p, declaration %p.\n", iface, declaration);
 
    if (!declaration)
    {
        WARN("Invalid declaration. Can't use NULL declaration.\n");
        return D3DERR_INVALIDCALL;
    }
 
    /* New declaration must be same size as original */
    vertex_declaration_size = D3DXGetDeclVertexSize(declaration, declaration[0].Stream);
    if (vertex_declaration_size != This->vertex_declaration_size)
    {
        WARN("Invalid declaration. New vertex size does not match the original vertex size.\n");
        return D3DERR_INVALIDCALL;
    }
 
    /* New declaration must not contain non-zero Stream value  */
    for (i = 0; declaration[i].Stream != 0xff; i++)
    {
        if (declaration[i].Stream != 0)
        {
            WARN("Invalid declaration. New declaration contains non-zero Stream value.\n");
            return D3DERR_INVALIDCALL;
        }
    }
 
    This->num_elem = i + 1;
    copy_declaration(This->cached_declaration, declaration, This->num_elem);
 
    if (This->vertex_declaration)
        IDirect3DVertexDeclaration9_Release(This->vertex_declaration);
 
    /* An application can pass an invalid declaration to UpdateSemantics and
     * still expect D3D_OK (see tests). If the declaration is invalid, then
     * subsequent calls to DrawSubset will fail. This is handled by setting the
     * vertex declaration to NULL.
     *     GetDeclaration, GetNumBytesPerVertex must, however, use the new
     * invalid declaration. This is handled by them using the cached vertex
     * declaration instead of the actual vertex declaration.
     */
    hr = IDirect3DDevice9_CreateVertexDeclaration(This->device,
                                                  declaration,
                                                  &This->vertex_declaration);
    if (FAILED(hr))
    {
        WARN("Using invalid declaration. Calls to DrawSubset will fail.\n");
        This->vertex_declaration = NULL;
    }
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_LockAttributeBuffer(ID3DXMesh *iface, DWORD flags, DWORD **data)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
 
    TRACE("iface %p, flags %#x, data %p.\n", iface, flags, data);
 
    InterlockedIncrement(&mesh->attrib_buffer_lock_count);
 
    if (!(flags & D3DLOCK_READONLY))
    {
        D3DXATTRIBUTERANGE *attrib_table = mesh->attrib_table;
        mesh->attrib_table_size = 0;
        mesh->attrib_table = NULL;
        HeapFree(GetProcessHeap(), 0, attrib_table);
    }
 
    *data = mesh->attrib_buffer;
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_UnlockAttributeBuffer(ID3DXMesh *iface)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
    int lock_count;
 
    TRACE("iface %p.\n", iface);
 
    lock_count = InterlockedDecrement(&mesh->attrib_buffer_lock_count);
    if (lock_count < 0)
    {
        InterlockedIncrement(&mesh->attrib_buffer_lock_count);
        return D3DERR_INVALIDCALL;
    }
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_Optimize(ID3DXMesh *iface, DWORD flags, const DWORD *adjacency_in,
        DWORD *adjacency_out, DWORD *face_remap, ID3DXBuffer **vertex_remap, ID3DXMesh **opt_mesh)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
    HRESULT hr;
    D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE] = { D3DDECL_END() };
    ID3DXMesh *optimized_mesh;
 
    TRACE("iface %p, flags %#x, adjacency_in %p, adjacency_out %p, face_remap %p, vertex_remap %p, opt_mesh %p.\n",
            iface, flags, adjacency_in, adjacency_out, face_remap, vertex_remap, opt_mesh);
 
    if (!opt_mesh)
        return D3DERR_INVALIDCALL;
 
    hr = iface->lpVtbl->GetDeclaration(iface, declaration);
    if (FAILED(hr)) return hr;
 
    if (FAILED(hr = iface->lpVtbl->CloneMesh(iface, mesh->options, declaration, mesh->device, &optimized_mesh)))
        return hr;
 
    hr = optimized_mesh->lpVtbl->OptimizeInplace(optimized_mesh, flags, adjacency_in, adjacency_out, face_remap, vertex_remap);
    if (SUCCEEDED(hr))
        *opt_mesh = optimized_mesh;
    else
        IUnknown_Release(optimized_mesh);
    return hr;
}
 
/* Creates a vertex_remap that removes unused vertices.
 * Indices are updated according to the vertex_remap. */
static HRESULT compact_mesh(struct d3dx9_mesh *This, DWORD *indices,
        DWORD *new_num_vertices, ID3DXBuffer **vertex_remap)
{
    HRESULT hr;
    DWORD *vertex_remap_ptr;
    DWORD num_used_vertices;
    DWORD i;
 
    hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), vertex_remap);
    if (FAILED(hr)) return hr;
    vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(*vertex_remap);
 
    for (i = 0; i < This->numfaces * 3; i++)
        vertex_remap_ptr[indices[i]] = 1;
 
    /* create old->new vertex mapping */
    num_used_vertices = 0;
    for (i = 0; i < This->numvertices; i++) {
        if (vertex_remap_ptr[i])
            vertex_remap_ptr[i] = num_used_vertices++;
        else
            vertex_remap_ptr[i] = -1;
    }
    /* convert indices */
    for (i = 0; i < This->numfaces * 3; i++)
        indices[i] = vertex_remap_ptr[indices[i]];
 
    /* create new->old vertex mapping */
    num_used_vertices = 0;
    for (i = 0; i < This->numvertices; i++) {
        if (vertex_remap_ptr[i] != -1)
            vertex_remap_ptr[num_used_vertices++] = i;
    }
    for (i = num_used_vertices; i < This->numvertices; i++)
        vertex_remap_ptr[i] = -1;
 
    *new_num_vertices = num_used_vertices;
 
    return D3D_OK;
}
 
/* count the number of unique attribute values in a sorted attribute buffer */
static DWORD count_attributes(const DWORD *attrib_buffer, DWORD numfaces)
{
    DWORD last_attribute = attrib_buffer[0];
    DWORD attrib_table_size = 1;
    DWORD i;
    for (i = 1; i < numfaces; i++) {
        if (attrib_buffer[i] != last_attribute) {
            last_attribute = attrib_buffer[i];
            attrib_table_size++;
        }
    }
    return attrib_table_size;
}
 
static void fill_attribute_table(DWORD *attrib_buffer, DWORD numfaces, void *indices,
                                 BOOL is_32bit_indices, D3DXATTRIBUTERANGE *attrib_table)
{
    DWORD attrib_table_size = 0;
    DWORD last_attribute = attrib_buffer[0];
    DWORD min_vertex, max_vertex;
    DWORD i;
 
    attrib_table[0].AttribId = last_attribute;
    attrib_table[0].FaceStart = 0;
    min_vertex = (DWORD)-1;
    max_vertex = 0;
    for (i = 0; i < numfaces; i++) {
        DWORD j;
 
        if (attrib_buffer[i] != last_attribute) {
            last_attribute = attrib_buffer[i];
            attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
            attrib_table[attrib_table_size].VertexStart = min_vertex;
            attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
            attrib_table_size++;
            attrib_table[attrib_table_size].AttribId = attrib_buffer[i];
            attrib_table[attrib_table_size].FaceStart = i;
            min_vertex = (DWORD)-1;
            max_vertex = 0;
        }
        for (j = 0; j < 3; j++) {
            DWORD vertex_index = is_32bit_indices ? ((DWORD*)indices)[i * 3 + j] : ((WORD*)indices)[i * 3 + j];
            if (vertex_index < min_vertex)
                min_vertex = vertex_index;
            if (vertex_index > max_vertex)
                max_vertex = vertex_index;
        }
    }
    attrib_table[attrib_table_size].FaceCount = i - attrib_table[attrib_table_size].FaceStart;
    attrib_table[attrib_table_size].VertexStart = min_vertex;
    attrib_table[attrib_table_size].VertexCount = max_vertex - min_vertex + 1;
    attrib_table_size++;
}
 
static int __cdecl attrib_entry_compare(const void *a, const void *b)
{
    const DWORD *ptr_a = *(const DWORD **)a;
    const DWORD *ptr_b = *(const DWORD **)b;
    int delta = *ptr_a - *ptr_b;
 
    if (delta)
        return delta;
 
    delta = ptr_a - ptr_b; /* for stable sort */
    return delta;
}
 
/* Create face_remap, a new attribute buffer for attribute sort optimization. */
static HRESULT remap_faces_for_attrsort(struct d3dx9_mesh *This, const DWORD *indices,
        DWORD *attrib_buffer, DWORD **sorted_attrib_buffer, DWORD **face_remap)
{
    DWORD **sorted_attrib_ptr_buffer = NULL;
    DWORD i;
 
    sorted_attrib_ptr_buffer = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(*sorted_attrib_ptr_buffer));
    if (!sorted_attrib_ptr_buffer)
        return E_OUTOFMEMORY;
 
    *face_remap = HeapAlloc(GetProcessHeap(), 0, This->numfaces * sizeof(**face_remap));
    if (!*face_remap)
    {
        HeapFree(GetProcessHeap(), 0, sorted_attrib_ptr_buffer);
        return E_OUTOFMEMORY;
    }
 
    for (i = 0; i < This->numfaces; i++)
        sorted_attrib_ptr_buffer[i] = &attrib_buffer[i];
    qsort(sorted_attrib_ptr_buffer, This->numfaces, sizeof(*sorted_attrib_ptr_buffer), attrib_entry_compare);
 
    for (i = 0; i < This->numfaces; i++)
    {
        DWORD old_face = sorted_attrib_ptr_buffer[i] - attrib_buffer;
        (*face_remap)[old_face] = i;
    }
 
    /* overwrite sorted_attrib_ptr_buffer with the values themselves */
    *sorted_attrib_buffer = (DWORD*)sorted_attrib_ptr_buffer;
    for (i = 0; i < This->numfaces; i++)
        (*sorted_attrib_buffer)[(*face_remap)[i]] = attrib_buffer[i];
 
    return D3D_OK;
}
 
static HRESULT WINAPI d3dx9_mesh_OptimizeInplace(ID3DXMesh *iface, DWORD flags, const DWORD *adjacency_in,
        DWORD *adjacency_out, DWORD *face_remap_out, ID3DXBuffer **vertex_remap_out)
{
    struct d3dx9_mesh *This = impl_from_ID3DXMesh(iface);
    void *indices = NULL;
    DWORD *attrib_buffer = NULL;
    HRESULT hr;
    ID3DXBuffer *vertex_remap = NULL;
    DWORD *face_remap = NULL; /* old -> new mapping */
    DWORD *dword_indices = NULL;
    DWORD new_num_vertices = 0;
    DWORD new_num_alloc_vertices = 0;
    IDirect3DVertexBuffer9 *vertex_buffer = NULL;
    DWORD *sorted_attrib_buffer = NULL;
    DWORD i;
 
    TRACE("iface %p, flags %#x, adjacency_in %p, adjacency_out %p, face_remap_out %p, vertex_remap_out %p.\n",
            iface, flags, adjacency_in, adjacency_out, face_remap_out, vertex_remap_out);
 
    if (!flags)
        return D3DERR_INVALIDCALL;
    if (!adjacency_in && (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)))
        return D3DERR_INVALIDCALL;
    if ((flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER)) == (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
        return D3DERR_INVALIDCALL;
 
    if (flags & (D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_STRIPREORDER))
    {
        if (flags & D3DXMESHOPT_VERTEXCACHE)
            FIXME("D3DXMESHOPT_VERTEXCACHE not implemented.\n");
        if (flags & D3DXMESHOPT_STRIPREORDER)
            FIXME("D3DXMESHOPT_STRIPREORDER not implemented.\n");
        return E_NOTIMPL;
    }
 
    hr = iface->lpVtbl->LockIndexBuffer(iface, 0, &indices);
    if (FAILED(hr)) goto cleanup;
 
    dword_indices = HeapAlloc(GetProcessHeap(), 0, This->numfaces * 3 * sizeof(DWORD));
    if (!dword_indices) return E_OUTOFMEMORY;
    if (This->options & D3DXMESH_32BIT) {
        memcpy(dword_indices, indices, This->numfaces * 3 * sizeof(DWORD));
    } else {
        WORD *word_indices = indices;
        for (i = 0; i < This->numfaces * 3; i++)
            dword_indices[i] = *word_indices++;
    }
 
    if ((flags & (D3DXMESHOPT_COMPACT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_ATTRSORT)) == D3DXMESHOPT_COMPACT)
    {
        new_num_alloc_vertices = This->numvertices;
        hr = compact_mesh(This, dword_indices, &new_num_vertices, &vertex_remap);
        if (FAILED(hr)) goto cleanup;
    } else if (flags & D3DXMESHOPT_ATTRSORT) {
        if (!(flags & D3DXMESHOPT_IGNOREVERTS))
            FIXME("D3DXMESHOPT_ATTRSORT vertex reordering not implemented.\n");
 
        hr = iface->lpVtbl->LockAttributeBuffer(iface, 0, &attrib_buffer);
        if (FAILED(hr)) goto cleanup;
 
        hr = remap_faces_for_attrsort(This, dword_indices, attrib_buffer, &sorted_attrib_buffer, &face_remap);
        if (FAILED(hr)) goto cleanup;
    }
 
    if (vertex_remap)
    {
        /* reorder the vertices using vertex_remap */
        D3DVERTEXBUFFER_DESC vertex_desc;
        DWORD *vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
        DWORD vertex_size = iface->lpVtbl->GetNumBytesPerVertex(iface);
        BYTE *orig_vertices;
        BYTE *new_vertices;
 
        hr = IDirect3DVertexBuffer9_GetDesc(This->vertex_buffer, &vertex_desc);
        if (FAILED(hr)) goto cleanup;
 
        hr = IDirect3DDevice9_CreateVertexBuffer(This->device, new_num_alloc_vertices * vertex_size,
                vertex_desc.Usage, This->fvf, vertex_desc.Pool, &vertex_buffer, NULL);
        if (FAILED(hr)) goto cleanup;
 
        hr = IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, (void**)&orig_vertices, D3DLOCK_READONLY);
        if (FAILED(hr)) goto cleanup;
 
        hr = IDirect3DVertexBuffer9_Lock(vertex_buffer, 0, 0, (void**)&new_vertices, 0);
        if (FAILED(hr)) {
            IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
            goto cleanup;
        }
 
        for (i = 0; i < new_num_vertices; i++)
            memcpy(new_vertices + i * vertex_size, orig_vertices + vertex_remap_ptr[i] * vertex_size, vertex_size);
 
        IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
        IDirect3DVertexBuffer9_Unlock(vertex_buffer);
    } else if (vertex_remap_out) {
        DWORD *vertex_remap_ptr;
 
        hr = D3DXCreateBuffer(This->numvertices * sizeof(DWORD), &vertex_remap);
        if (FAILED(hr)) goto cleanup;
        vertex_remap_ptr = ID3DXBuffer_GetBufferPointer(vertex_remap);
        for (i = 0; i < This->numvertices; i++)
            *vertex_remap_ptr++ = i;
    }
 
    if (flags & D3DXMESHOPT_ATTRSORT)
    {
        D3DXATTRIBUTERANGE *attrib_table;
        DWORD attrib_table_size;
 
        attrib_table_size = count_attributes(sorted_attrib_buffer, This->numfaces);
        attrib_table = HeapAlloc(GetProcessHeap(), 0, attrib_table_size * sizeof(*attrib_table));
        if (!attrib_table) {
            hr = E_OUTOFMEMORY;
            goto cleanup;
        }
 
        memcpy(attrib_buffer, sorted_attrib_buffer, This->numfaces * sizeof(*attrib_buffer));
 
        /* reorder the indices using face_remap */
        if (This->options & D3DXMESH_32BIT) {
            for (i = 0; i < This->numfaces; i++)
                memcpy((DWORD*)indices + face_remap[i] * 3, dword_indices + i * 3, 3 * sizeof(DWORD));
        } else {
            WORD *word_indices = indices;
            for (i = 0; i < This->numfaces; i++) {
                DWORD new_pos = face_remap[i] * 3;
                DWORD old_pos = i * 3;
                word_indices[new_pos++] = dword_indices[old_pos++];
                word_indices[new_pos++] = dword_indices[old_pos++];
                word_indices[new_pos] = dword_indices[old_pos];
            }
        }
 
        fill_attribute_table(attrib_buffer, This->numfaces, indices,
                             This->options & D3DXMESH_32BIT, attrib_table);
 
        HeapFree(GetProcessHeap(), 0, This->attrib_table);
        This->attrib_table = attrib_table;
        This->attrib_table_size = attrib_table_size;
    } else {
        if (This->options & D3DXMESH_32BIT) {
            memcpy(indices, dword_indices, This->numfaces * 3 * sizeof(DWORD));
        } else {
            WORD *word_indices = indices;
            for (i = 0; i < This->numfaces * 3; i++)
                *word_indices++ = dword_indices[i];
        }
    }
 
    if (adjacency_out) {
        if (face_remap) {
            for (i = 0; i < This->numfaces; i++) {
                DWORD old_pos = i * 3;
                DWORD new_pos = face_remap[i] * 3;
                adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
                adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
                adjacency_out[new_pos++] = face_remap[adjacency_in[old_pos++]];
            }
        } else {
            memcpy(adjacency_out, adjacency_in, This->numfaces * 3 * sizeof(*adjacency_out));
        }
    }
    if (face_remap_out) {
        if (face_remap) {
            for (i = 0; i < This->numfaces; i++)
                face_remap_out[face_remap[i]] = i;
        } else {
            for (i = 0; i < This->numfaces; i++)
                face_remap_out[i] = i;
        }
    }
    if (vertex_remap_out)
        *vertex_remap_out = vertex_remap;
    vertex_remap = NULL;
 
    if (vertex_buffer) {
        IDirect3DVertexBuffer9_Release(This->vertex_buffer);
        This->vertex_buffer = vertex_buffer;
        vertex_buffer = NULL;
        This->numvertices = new_num_vertices;
    }
 
    hr = D3D_OK;
cleanup:
    HeapFree(GetProcessHeap(), 0, sorted_attrib_buffer);
    HeapFree(GetProcessHeap(), 0, face_remap);
    HeapFree(GetProcessHeap(), 0, dword_indices);
    if (vertex_remap) ID3DXBuffer_Release(vertex_remap);
    if (vertex_buffer) IDirect3DVertexBuffer9_Release(vertex_buffer);
    if (attrib_buffer) iface->lpVtbl->UnlockAttributeBuffer(iface);
    if (indices) iface->lpVtbl->UnlockIndexBuffer(iface);
    return hr;
}
 
static HRESULT WINAPI d3dx9_mesh_SetAttributeTable(ID3DXMesh *iface,
        const D3DXATTRIBUTERANGE *attrib_table, DWORD attrib_table_size)
{
    struct d3dx9_mesh *mesh = impl_from_ID3DXMesh(iface);
    D3DXATTRIBUTERANGE *new_table = NULL;
 
    TRACE("iface %p, attrib_table %p, attrib_table_size %u.\n", iface, attrib_table, attrib_table_size);
 
    if (attrib_table_size) {
        size_t size = attrib_table_size * sizeof(*attrib_table);
 
        new_table = HeapAlloc(GetProcessHeap(), 0, size);
        if (!new_table)
            return E_OUTOFMEMORY;
 
        CopyMemory(new_table, attrib_table, size);
    } else if (attrib_table) {
        return D3DERR_INVALIDCALL;
    }
    HeapFree(GetProcessHeap(), 0, mesh->attrib_table);
    mesh->attrib_table = new_table;
    mesh->attrib_table_size = attrib_table_size;
 
    return D3D_OK;
}
 
static const struct ID3DXMeshVtbl D3DXMesh_Vtbl =
{
    d3dx9_mesh_QueryInterface,
    d3dx9_mesh_AddRef,
    d3dx9_mesh_Release,
    d3dx9_mesh_DrawSubset,
    d3dx9_mesh_GetNumFaces,
    d3dx9_mesh_GetNumVertices,
    d3dx9_mesh_GetFVF,
    d3dx9_mesh_GetDeclaration,
    d3dx9_mesh_GetNumBytesPerVertex,
    d3dx9_mesh_GetOptions,
    d3dx9_mesh_GetDevice,
    d3dx9_mesh_CloneMeshFVF,
    d3dx9_mesh_CloneMesh,
    d3dx9_mesh_GetVertexBuffer,
    d3dx9_mesh_GetIndexBuffer,
    d3dx9_mesh_LockVertexBuffer,
    d3dx9_mesh_UnlockVertexBuffer,
    d3dx9_mesh_LockIndexBuffer,
    d3dx9_mesh_UnlockIndexBuffer,
    d3dx9_mesh_GetAttributeTable,
    d3dx9_mesh_ConvertPointRepsToAdjacency,
    d3dx9_mesh_ConvertAdjacencyToPointReps,
    d3dx9_mesh_GenerateAdjacency,
    d3dx9_mesh_UpdateSemantics,
    d3dx9_mesh_LockAttributeBuffer,
    d3dx9_mesh_UnlockAttributeBuffer,
    d3dx9_mesh_Optimize,
    d3dx9_mesh_OptimizeInplace,
    d3dx9_mesh_SetAttributeTable,
};
 
 
/* Algorithm taken from the article: An Efficient and Robust Ray-Box Intersection Algorithm
Amy Williams             University of Utah
Steve Barrus             University of Utah
R. Keith Morley          University of Utah
Peter Shirley            University of Utah
 
International Conference on Computer Graphics and Interactive Techniques  archive
ACM SIGGRAPH 2005 Courses
Los Angeles, California
 
This algorithm is free of patents or of copyrights, as confirmed by Peter Shirley himself.
 
Algorithm: Consider the box as the intersection of three slabs. Clip the ray
against each slab, if there's anything left of the ray after we're
done we've got an intersection of the ray with the box. */
BOOL WINAPI D3DXBoxBoundProbe(const D3DXVECTOR3 *pmin, const D3DXVECTOR3 *pmax,
        const D3DXVECTOR3 *prayposition, const D3DXVECTOR3 *praydirection)
{
    FLOAT div, tmin, tmax, tymin, tymax, tzmin, tzmax;
 
    div = 1.0f / praydirection->x;
    if ( div >= 0.0f )
    {
        tmin = ( pmin->x - prayposition->x ) * div;
        tmax = ( pmax->x - prayposition->x ) * div;
    }
    else
    {
        tmin = ( pmax->x - prayposition->x ) * div;
        tmax = ( pmin->x - prayposition->x ) * div;
    }
 
    if ( tmax < 0.0f ) return FALSE;
 
    div = 1.0f / praydirection->y;
    if ( div >= 0.0f )
    {
        tymin = ( pmin->y - prayposition->y ) * div;
        tymax = ( pmax->y - prayposition->y ) * div;
    }
    else
    {
        tymin = ( pmax->y - prayposition->y ) * div;
        tymax = ( pmin->y - prayposition->y ) * div;
    }
 
    if ( ( tymax < 0.0f ) || ( tmin > tymax ) || ( tymin > tmax ) ) return FALSE;
 
    if ( tymin > tmin ) tmin = tymin;
    if ( tymax < tmax ) tmax = tymax;
 
    div = 1.0f / praydirection->z;
    if ( div >= 0.0f )
    {
        tzmin = ( pmin->z - prayposition->z ) * div;
        tzmax = ( pmax->z - prayposition->z ) * div;
    }
    else
    {
        tzmin = ( pmax->z - prayposition->z ) * div;
        tzmax = ( pmin->z - prayposition->z ) * div;
    }
 
    if ( (tzmax < 0.0f ) || ( tmin > tzmax ) || ( tzmin > tmax ) ) return FALSE;
 
    return TRUE;
}
 
HRESULT WINAPI D3DXComputeBoundingBox(const D3DXVECTOR3 *pfirstposition,
        DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pmin, D3DXVECTOR3 *pmax)
{
    D3DXVECTOR3 vec;
    unsigned int i;
 
    if( !pfirstposition || !pmin || !pmax ) return D3DERR_INVALIDCALL;
 
    *pmin = *pfirstposition;
    *pmax = *pmin;
 
    for(i=0; i<numvertices; i++)
    {
        vec = *( (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i) );
 
        if ( vec.x < pmin->x ) pmin->x = vec.x;
        if ( vec.x > pmax->x ) pmax->x = vec.x;
 
        if ( vec.y < pmin->y ) pmin->y = vec.y;
        if ( vec.y > pmax->y ) pmax->y = vec.y;
 
        if ( vec.z < pmin->z ) pmin->z = vec.z;
        if ( vec.z > pmax->z ) pmax->z = vec.z;
    }
 
    return D3D_OK;
}
 
HRESULT WINAPI D3DXComputeBoundingSphere(const D3DXVECTOR3 *pfirstposition,
        DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pcenter, float *pradius)
{
    D3DXVECTOR3 temp;
    FLOAT d;
    unsigned int i;
 
    if( !pfirstposition || !pcenter || !pradius ) return D3DERR_INVALIDCALL;
 
    temp.x = 0.0f;
    temp.y = 0.0f;
    temp.z = 0.0f;
    *pradius = 0.0f;
 
    for(i=0; i<numvertices; i++)
        D3DXVec3Add(&temp, &temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i));
 
    D3DXVec3Scale(pcenter, &temp, 1.0f / numvertices);
 
    for(i=0; i<numvertices; i++)
    {
        d = D3DXVec3Length(D3DXVec3Subtract(&temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i), pcenter));
        if ( d > *pradius ) *pradius = d;
    }
    return D3D_OK;
}
 
static void append_decl_element(D3DVERTEXELEMENT9 *declaration, UINT *idx, UINT *offset,
        D3DDECLTYPE type, D3DDECLUSAGE usage, UINT usage_idx)
{
    declaration[*idx].Stream = 0;
    declaration[*idx].Offset = *offset;
    declaration[*idx].Type = type;
    declaration[*idx].Method = D3DDECLMETHOD_DEFAULT;
    declaration[*idx].Usage = usage;
    declaration[*idx].UsageIndex = usage_idx;
 
    *offset += d3dx_decltype_size[type];
    ++(*idx);
}
 
/*************************************************************************
 * D3DXDeclaratorFromFVF
 */
HRESULT WINAPI D3DXDeclaratorFromFVF(DWORD fvf, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
{
    static const D3DVERTEXELEMENT9 end_element = D3DDECL_END();
    DWORD tex_count = (fvf & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
    unsigned int offset = 0;
    unsigned int idx = 0;
    unsigned int i;
 
    TRACE("fvf %#x, declaration %p.\n", fvf, declaration);
 
    if (fvf & (D3DFVF_RESERVED0 | D3DFVF_RESERVED2)) return D3DERR_INVALIDCALL;
 
    if (fvf & D3DFVF_POSITION_MASK)
    {
        BOOL has_blend = (fvf & D3DFVF_XYZB5) >= D3DFVF_XYZB1;
        DWORD blend_count = 1 + (((fvf & D3DFVF_XYZB5) - D3DFVF_XYZB1) >> 1);
        BOOL has_blend_idx = (fvf & D3DFVF_LASTBETA_D3DCOLOR) || (fvf & D3DFVF_LASTBETA_UBYTE4);
 
        if (has_blend_idx) --blend_count;
 
        if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZW
                || (has_blend && blend_count > 4))
            return D3DERR_INVALIDCALL;
 
        if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZRHW)
            append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_POSITIONT, 0);
        else
            append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_POSITION, 0);
 
        if (has_blend)
        {
            switch (blend_count)
            {
                 case 0:
                    break;
                 case 1:
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_BLENDWEIGHT, 0);
                    break;
                 case 2:
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_BLENDWEIGHT, 0);
                    break;
                 case 3:
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_BLENDWEIGHT, 0);
                    break;
                 case 4:
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_BLENDWEIGHT, 0);
                    break;
                 default:
                     ERR("Invalid blend count %u.\n", blend_count);
                     break;
            }
 
            if (has_blend_idx)
            {
                if (fvf & D3DFVF_LASTBETA_UBYTE4)
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_UBYTE4, D3DDECLUSAGE_BLENDINDICES, 0);
                else if (fvf & D3DFVF_LASTBETA_D3DCOLOR)
                    append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_BLENDINDICES, 0);
            }
        }
    }
 
    if (fvf & D3DFVF_NORMAL)
        append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_NORMAL, 0);
    if (fvf & D3DFVF_PSIZE)
        append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_PSIZE, 0);
    if (fvf & D3DFVF_DIFFUSE)
        append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 0);
    if (fvf & D3DFVF_SPECULAR)
        append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 1);
 
    for (i = 0; i < tex_count; ++i)
    {
        switch ((fvf >> (16 + 2 * i)) & 0x03)
        {
            case D3DFVF_TEXTUREFORMAT1:
                append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_TEXCOORD, i);
                break;
            case D3DFVF_TEXTUREFORMAT2:
                append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_TEXCOORD, i);
                break;
            case D3DFVF_TEXTUREFORMAT3:
                append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_TEXCOORD, i);
                break;
            case D3DFVF_TEXTUREFORMAT4:
                append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_TEXCOORD, i);
                break;
        }
    }
 
    declaration[idx] = end_element;
 
    return D3D_OK;
}
 
/*************************************************************************
 * D3DXFVFFromDeclarator
 */
HRESULT WINAPI D3DXFVFFromDeclarator(const D3DVERTEXELEMENT9 *declaration, DWORD *fvf)
{
    unsigned int i = 0, texture, offset;
 
    TRACE("(%p, %p)\n", declaration, fvf);
 
    *fvf = 0;
    if (declaration[0].Type == D3DDECLTYPE_FLOAT3 && declaration[0].Usage == D3DDECLUSAGE_POSITION)
    {
        if ((declaration[1].Type == D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
             declaration[1].UsageIndex == 0) &&
            (declaration[2].Type == D3DDECLTYPE_FLOAT1 && declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES &&
             declaration[2].UsageIndex == 0))
        {
            return D3DERR_INVALIDCALL;
        }
        else if ((declaration[1].Type == D3DDECLTYPE_UBYTE4 || declaration[1].Type == D3DDECLTYPE_D3DCOLOR) &&
                 declaration[1].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[1].UsageIndex == 0)
        {
            if (declaration[1].Type == D3DDECLTYPE_UBYTE4)
            {
                *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_UBYTE4;
            }
            else
            {
                *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_D3DCOLOR;
            }
            i = 2;
        }
        else if (declaration[1].Type <= D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
                 declaration[1].UsageIndex == 0)
        {
            if ((declaration[2].Type == D3DDECLTYPE_UBYTE4 || declaration[2].Type == D3DDECLTYPE_D3DCOLOR) &&
                declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[2].UsageIndex == 0)
            {
                if (declaration[2].Type == D3DDECLTYPE_UBYTE4)
                {
                    *fvf |= D3DFVF_LASTBETA_UBYTE4;
                }
                else
                {
                    *fvf |= D3DFVF_LASTBETA_D3DCOLOR;
                }
                switch (declaration[1].Type)
                {
                    case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB2; break;
                    case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB3; break;
                    case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB4; break;
                    case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB5; break;
                }
                i = 3;
            }
            else
            {
                switch (declaration[1].Type)
                {
                    case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB1; break;
                    case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB2; break;
                    case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB3; break;
                    case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB4; break;
                }
                i = 2;
            }
        }
        else
        {
            *fvf |= D3DFVF_XYZ;
            i = 1;
        }
    }
    else if (declaration[0].Type == D3DDECLTYPE_FLOAT4 && declaration[0].Usage == D3DDECLUSAGE_POSITIONT &&
             declaration[0].UsageIndex == 0)
    {
        *fvf |= D3DFVF_XYZRHW;
        i = 1;
    }
 
    if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_NORMAL)
    {
        *fvf |= D3DFVF_NORMAL;
        i++;
    }
    if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_PSIZE &&
        declaration[i].UsageIndex == 0)
    {
        *fvf |= D3DFVF_PSIZE;
        i++;
    }
    if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
        declaration[i].UsageIndex == 0)
    {
        *fvf |= D3DFVF_DIFFUSE;
        i++;
    }
    if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
        declaration[i].UsageIndex == 1)
    {
        *fvf |= D3DFVF_SPECULAR;
        i++;
    }
 
    for (texture = 0; texture < D3DDP_MAXTEXCOORD; i++, texture++)
    {
        if (declaration[i].Stream == 0xFF)
        {
            break;
        }
        else if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
                 declaration[i].UsageIndex == texture)
        {
            *fvf |= D3DFVF_TEXCOORDSIZE1(declaration[i].UsageIndex);
        }
        else if (declaration[i].Type == D3DDECLTYPE_FLOAT2 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
                 declaration[i].UsageIndex == texture)
        {
            *fvf |= D3DFVF_TEXCOORDSIZE2(declaration[i].UsageIndex);
        }
        else if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
                 declaration[i].UsageIndex == texture)
        {
            *fvf |= D3DFVF_TEXCOORDSIZE3(declaration[i].UsageIndex);
        }
        else if (declaration[i].Type == D3DDECLTYPE_FLOAT4 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
                 declaration[i].UsageIndex == texture)
        {
            *fvf |= D3DFVF_TEXCOORDSIZE4(declaration[i].UsageIndex);
        }
        else
        {
            return D3DERR_INVALIDCALL;
        }
    }
 
    *fvf |= (texture << D3DFVF_TEXCOUNT_SHIFT);
 
    for (offset = 0, i = 0; declaration[i].Stream != 0xFF;
         offset += d3dx_decltype_size[declaration[i].Type], i++)
    {
        if (declaration[i].Offset != offset)
        {
            return D3DERR_INVALIDCALL;
        }
    }
 
    return D3D_OK;
}
 
/*************************************************************************
 * D3DXGetFVFVertexSize
 */
static UINT Get_TexCoord_Size_From_FVF(DWORD FVF, int tex_num)
{
    return (((((FVF) >> (16 + (2 * (tex_num)))) + 1) & 0x03) + 1);
}
 
UINT WINAPI D3DXGetFVFVertexSize(DWORD FVF)
{
    DWORD size = 0;
    UINT i;
    UINT numTextures = (FVF & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
 
    if (FVF & D3DFVF_NORMAL) size += sizeof(D3DXVECTOR3);
    if (FVF & D3DFVF_DIFFUSE) size += sizeof(DWORD);
    if (FVF & D3DFVF_SPECULAR) size += sizeof(DWORD);
    if (FVF & D3DFVF_PSIZE) size += sizeof(DWORD);
 
    switch (FVF & D3DFVF_POSITION_MASK)
    {
        case D3DFVF_XYZ:    size += sizeof(D3DXVECTOR3); break;
        case D3DFVF_XYZRHW: size += 4 * sizeof(FLOAT); break;
        case D3DFVF_XYZB1:  size += 4 * sizeof(FLOAT); break;
        case D3DFVF_XYZB2:  size += 5 * sizeof(FLOAT); break;
        case D3DFVF_XYZB3:  size += 6 * sizeof(FLOAT); break;
        case D3DFVF_XYZB4:  size += 7 * sizeof(FLOAT); break;
        case D3DFVF_XYZB5:  size += 8 * sizeof(FLOAT); break;
        case D3DFVF_XYZW:   size += 4 * sizeof(FLOAT); break;
    }
 
    for (i = 0; i < numTextures; i++)
    {
        size += Get_TexCoord_Size_From_FVF(FVF, i) * sizeof(FLOAT);
    }
 
    return size;
}
 
/*************************************************************************
 * D3DXGetDeclVertexSize
 */
UINT WINAPI D3DXGetDeclVertexSize(const D3DVERTEXELEMENT9 *decl, DWORD stream_idx)
{
    const D3DVERTEXELEMENT9 *element;
    UINT size = 0;
 
    TRACE("decl %p, stream_idx %u\n", decl, stream_idx);
 
    if (!decl) return 0;
 
    for (element = decl; element->Stream != 0xff; ++element)
    {
        UINT type_size;
 
        if (element->Stream != stream_idx) continue;
 
        if (element->Type >= ARRAY_SIZE(d3dx_decltype_size))
        {
            FIXME("Unhandled element type %#x, size will be incorrect.\n", element->Type);
            continue;
        }
 
        type_size = d3dx_decltype_size[element->Type];
        if (element->Offset + type_size > size) size = element->Offset + type_size;
    }
 
    return size;
}
 
/*************************************************************************
 * D3DXGetDeclLength
 */
UINT WINAPI D3DXGetDeclLength(const D3DVERTEXELEMENT9 *decl)
{
    const D3DVERTEXELEMENT9 *element;
 
    TRACE("decl %p\n", decl);
 
    /* null decl results in exception on Windows XP */
 
    for (element = decl; element->Stream != 0xff; ++element);
 
    return element - decl;
}
 
BOOL WINAPI D3DXIntersectTri(const D3DXVECTOR3 *p0, const D3DXVECTOR3 *p1, const D3DXVECTOR3 *p2,
        const D3DXVECTOR3 *praypos, const D3DXVECTOR3 *praydir, float *pu, float *pv, float *pdist)
{
    D3DXMATRIX m;
    D3DXVECTOR4 vec;
 
    TRACE("p0 %p, p1 %p, p2 %p, praypos %p, praydir %p, pu %p, pv %p, pdist %p.\n",
            p0, p1, p2, praypos, praydir, pu, pv, pdist);
 
    m.u.m[0][0] = p1->x - p0->x;
    m.u.m[1][0] = p2->x - p0->x;
    m.u.m[2][0] = -praydir->x;
    m.u.m[3][0] = 0.0f;
    m.u.m[0][1] = p1->y - p0->y;
    m.u.m[1][1] = p2->y - p0->y;
    m.u.m[2][1] = -praydir->y;
    m.u.m[3][1] = 0.0f;
    m.u.m[0][2] = p1->z - p0->z;
    m.u.m[1][2] = p2->z - p0->z;
    m.u.m[2][2] = -praydir->z;
    m.u.m[3][2] = 0.0f;
    m.u.m[0][3] = 0.0f;
    m.u.m[1][3] = 0.0f;
    m.u.m[2][3] = 0.0f;
    m.u.m[3][3] = 1.0f;
 
    vec.x = praypos->x - p0->x;
    vec.y = praypos->y - p0->y;
    vec.z = praypos->z - p0->z;
    vec.w = 0.0f;
 
    if ( D3DXMatrixInverse(&m, NULL, &m) )
    {
        D3DXVec4Transform(&vec, &vec, &m);
        if ( (vec.x >= 0.0f) && (vec.y >= 0.0f) && (vec.x + vec.y <= 1.0f) && (vec.z >= 0.0f) )
        {
            if (pu) *pu = vec.x;
            if (pv) *pv = vec.y;
            if (pdist) *pdist = fabsf( vec.z );
            return TRUE;
        }
    }
 
    return FALSE;
}
 
BOOL WINAPI D3DXSphereBoundProbe(const D3DXVECTOR3 *center, float radius,
        const D3DXVECTOR3 *ray_position, const D3DXVECTOR3 *ray_direction)
{
    D3DXVECTOR3 difference = {0};
    float a, b, c, d;
 
    D3DXVec3Subtract(&difference, ray_position, center);
    c = D3DXVec3LengthSq(&difference) - radius * radius;
    if (c < 0.0f)
        return TRUE;
    a = D3DXVec3LengthSq(ray_direction);
    b = D3DXVec3Dot(&difference, ray_direction);
    d = b * b - a * c;
 
    return d >= 0.0f && (b <= 0.0f || d > b * b);
}
 
/*************************************************************************
 * D3DXCreateMesh
 */
HRESULT WINAPI D3DXCreateMesh(DWORD numfaces, DWORD numvertices, DWORD options,
        const D3DVERTEXELEMENT9 *declaration, struct IDirect3DDevice9 *device, struct ID3DXMesh **mesh)
{
    HRESULT hr;
    DWORD fvf;
    IDirect3DVertexDeclaration9 *vertex_declaration;
    UINT vertex_declaration_size;
    UINT num_elem;
    IDirect3DVertexBuffer9 *vertex_buffer;
    IDirect3DIndexBuffer9 *index_buffer;
    DWORD *attrib_buffer;
    struct d3dx9_mesh *object;
    DWORD index_usage = 0;
    D3DPOOL index_pool = D3DPOOL_DEFAULT;
    D3DFORMAT index_format = D3DFMT_INDEX16;
    DWORD vertex_usage = 0;
    D3DPOOL vertex_pool = D3DPOOL_DEFAULT;
    int i;
 
    TRACE("numfaces %u, numvertices %u, options %#x, declaration %p, device %p, mesh %p.\n",
            numfaces, numvertices, options, declaration, device, mesh);
 
    if (numfaces == 0 || numvertices == 0 || declaration == NULL || device == NULL || mesh == NULL ||
        /* D3DXMESH_VB_SHARE is for cloning, and D3DXMESH_USEHWONLY is for ConvertToBlendedMesh */
        (options & (D3DXMESH_VB_SHARE | D3DXMESH_USEHWONLY | 0xfffe0000)))
    {
        return D3DERR_INVALIDCALL;
    }
    for (i = 0; declaration[i].Stream != 0xff; i++)
        if (declaration[i].Stream != 0)
            return D3DERR_INVALIDCALL;
    num_elem = i + 1;
 
    if (options & D3DXMESH_32BIT)
        index_format = D3DFMT_INDEX32;
 
    if (options & D3DXMESH_DONOTCLIP) {
        index_usage |= D3DUSAGE_DONOTCLIP;
        vertex_usage |= D3DUSAGE_DONOTCLIP;
    }
    if (options & D3DXMESH_POINTS) {
        index_usage |= D3DUSAGE_POINTS;
        vertex_usage |= D3DUSAGE_POINTS;
    }
    if (options & D3DXMESH_RTPATCHES) {
        index_usage |= D3DUSAGE_RTPATCHES;
        vertex_usage |= D3DUSAGE_RTPATCHES;
    }
    if (options & D3DXMESH_NPATCHES) {
        index_usage |= D3DUSAGE_NPATCHES;
        vertex_usage |= D3DUSAGE_NPATCHES;
    }
 
    if (options & D3DXMESH_VB_SYSTEMMEM)
        vertex_pool = D3DPOOL_SYSTEMMEM;
    else if (options & D3DXMESH_VB_MANAGED)
        vertex_pool = D3DPOOL_MANAGED;
 
    if (options & D3DXMESH_VB_WRITEONLY)
        vertex_usage |= D3DUSAGE_WRITEONLY;
    if (options & D3DXMESH_VB_DYNAMIC)
        vertex_usage |= D3DUSAGE_DYNAMIC;
    if (options & D3DXMESH_VB_SOFTWAREPROCESSING)
        vertex_usage |= D3DUSAGE_SOFTWAREPROCESSING;
 
    if (options & D3DXMESH_IB_SYSTEMMEM)
        index_pool = D3DPOOL_SYSTEMMEM;
    else if (options & D3DXMESH_IB_MANAGED)
        index_pool = D3DPOOL_MANAGED;
 
    if (options & D3DXMESH_IB_WRITEONLY)
        index_usage |= D3DUSAGE_WRITEONLY;
    if (options & D3DXMESH_IB_DYNAMIC)
        index_usage |= D3DUSAGE_DYNAMIC;
    if (options & D3DXMESH_IB_SOFTWAREPROCESSING)
        index_usage |= D3DUSAGE_SOFTWAREPROCESSING;
 
    hr = D3DXFVFFromDeclarator(declaration, &fvf);
    if (hr != D3D_OK)
    {
        fvf = 0;
    }
 
    /* Create vertex declaration */
    hr = IDirect3DDevice9_CreateVertexDeclaration(device,
                                                  declaration,
                                                  &vertex_declaration);
    if (FAILED(hr))
    {
        WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexDeclaration.\n",hr);
        return hr;
    }
    vertex_declaration_size = D3DXGetDeclVertexSize(declaration, declaration[0].Stream);
 
    /* Create vertex buffer */
    hr = IDirect3DDevice9_CreateVertexBuffer(device,
                                             numvertices * vertex_declaration_size,
                                             vertex_usage,
                                             fvf,
                                             vertex_pool,
                                             &vertex_buffer,
                                             NULL);
    if (FAILED(hr))
    {
        WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
        IDirect3DVertexDeclaration9_Release(vertex_declaration);
        return hr;
    }
 
    /* Create index buffer */
    hr = IDirect3DDevice9_CreateIndexBuffer(device,
                                            numfaces * 3 * ((index_format == D3DFMT_INDEX16) ? 2 : 4),
                                            index_usage,
                                            index_format,
                                            index_pool,
                                            &index_buffer,
                                            NULL);
    if (FAILED(hr))
    {
        WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
        IDirect3DVertexBuffer9_Release(vertex_buffer);
        IDirect3DVertexDeclaration9_Release(vertex_declaration);
        return hr;
    }
 
    attrib_buffer = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, numfaces * sizeof(*attrib_buffer));
    object = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*object));
    if (object == NULL || attrib_buffer == NULL)
    {
        HeapFree(GetProcessHeap(), 0, object);
        HeapFree(GetProcessHeap(), 0, attrib_buffer);
        IDirect3DIndexBuffer9_Release(index_buffer);
        IDirect3DVertexBuffer9_Release(vertex_buffer);
        IDirect3DVertexDeclaration9_Release(vertex_declaration);
        *mesh = NULL;
        return E_OUTOFMEMORY;
    }
    object->ID3DXMesh_iface.lpVtbl = &D3DXMesh_Vtbl;
    object->ref = 1;
 
    object->numfaces = numfaces;
    object->numvertices = numvertices;
    object->options = options;
    object->fvf = fvf;
    object->device = device;
    IDirect3DDevice9_AddRef(device);
 
    copy_declaration(object->cached_declaration, declaration, num_elem);
    object->vertex_declaration = vertex_declaration;
    object->vertex_declaration_size = vertex_declaration_size;
    object->num_elem = num_elem;
    object->vertex_buffer = vertex_buffer;
    object->index_buffer = index_buffer;
    object->attrib_buffer = attrib_buffer;
 
    *mesh = &object->ID3DXMesh_iface;
 
    return D3D_OK;
}
 
/*************************************************************************
 * D3DXCreateMeshFVF
 */
HRESULT WINAPI D3DXCreateMeshFVF(DWORD numfaces, DWORD numvertices, DWORD options,
        DWORD fvf, struct IDirect3DDevice9 *device, struct ID3DXMesh **mesh)
{
    HRESULT hr;
    D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
 
    TRACE("(%u, %u, %u, %u, %p, %p)\n", numfaces, numvertices, options, fvf, device, mesh);
 
    hr = D3DXDeclaratorFromFVF(fvf, declaration);
    if (FAILED(hr)) return hr;
 
    return D3DXCreateMesh(numfaces, numvertices, options, declaration, device, mesh);
}
 
 
struct mesh_data {
    DWORD num_vertices;
    DWORD num_poly_faces;
    DWORD num_tri_faces;
    D3DXVECTOR3 *vertices;
    DWORD *num_tri_per_face;
    DWORD *indices;
 
    DWORD fvf;
 
    /* optional mesh data */
 
    DWORD num_normals;
    D3DXVECTOR3 *normals;
    DWORD *normal_indices;
 
    D3DXVECTOR2 *tex_coords;
 
    DWORD *vertex_colors;
 
    DWORD num_materials;
    D3DXMATERIAL *materials;
    DWORD *material_indices;
 
    struct ID3DXSkinInfo *skin_info;
    DWORD nb_bones;
};
 
static HRESULT parse_texture_filename(ID3DXFileData *filedata, char **filename_out)
{
    HRESULT hr;
    SIZE_T data_size;
    BYTE *data;
    char *filename_in;
    char *filename = NULL;
 
    /* template TextureFilename {
     *     STRING filename;
     * }
     */
 
    HeapFree(GetProcessHeap(), 0, *filename_out);
    *filename_out = NULL;
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /* FIXME: String must be retrieved directly instead of through a pointer once ID3DXFILE is fixed */
    if (data_size < sizeof(filename_in))
    {
        WARN("truncated data (%lu bytes)\n", data_size);
        filedata->lpVtbl->Unlock(filedata);
        return E_FAIL;
    }
    filename_in = *(char **)data;
 
    filename = HeapAlloc(GetProcessHeap(), 0, strlen(filename_in) + 1);
    if (!filename) {
        filedata->lpVtbl->Unlock(filedata);
        return E_OUTOFMEMORY;
    }
 
    strcpy(filename, filename_in);
    *filename_out = filename;
 
    filedata->lpVtbl->Unlock(filedata);
 
    return D3D_OK;
}
 
static HRESULT parse_material(ID3DXFileData *filedata, D3DXMATERIAL *material)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data;
    GUID type;
    ID3DXFileData *child;
    SIZE_T i, nb_children;
 
    material->pTextureFilename = NULL;
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /*
     * template ColorRGBA {
     *     FLOAT red;
     *     FLOAT green;
     *     FLOAT blue;
     *     FLOAT alpha;
     * }
     * template ColorRGB {
     *     FLOAT red;
     *     FLOAT green;
     *     FLOAT blue;
     * }
     * template Material {
     *     ColorRGBA faceColor;
     *     FLOAT power;
     *     ColorRGB specularColor;
     *     ColorRGB emissiveColor;
     *     [ ... ]
     * }
     */
    if (data_size != sizeof(FLOAT) * 11) {
        WARN("incorrect data size (%ld bytes)\n", data_size);
        filedata->lpVtbl->Unlock(filedata);
        return E_FAIL;
    }
 
    memcpy(&material->MatD3D.Diffuse, data, sizeof(D3DCOLORVALUE));
    data += sizeof(D3DCOLORVALUE);
    material->MatD3D.Power = *(FLOAT*)data;
    data += sizeof(FLOAT);
    memcpy(&material->MatD3D.Specular, data, sizeof(FLOAT) * 3);
    material->MatD3D.Specular.a = 1.0f;
    data += 3 * sizeof(FLOAT);
    memcpy(&material->MatD3D.Emissive, data, sizeof(FLOAT) * 3);
    material->MatD3D.Emissive.a = 1.0f;
    material->MatD3D.Ambient.r = 0.0f;
    material->MatD3D.Ambient.g = 0.0f;
    material->MatD3D.Ambient.b = 0.0f;
    material->MatD3D.Ambient.a = 1.0f;
 
    filedata->lpVtbl->Unlock(filedata);
 
    hr = filedata->lpVtbl->GetChildren(filedata, &nb_children);
    if (FAILED(hr))
        return hr;
 
    for (i = 0; i < nb_children; i++)
    {
        hr = filedata->lpVtbl->GetChild(filedata, i, &child);
        if (FAILED(hr))
            return hr;
        hr = child->lpVtbl->GetType(child, &type);
        if (FAILED(hr))
            goto err;
 
        if (IsEqualGUID(&type, &TID_D3DRMTextureFilename)) {
            hr = parse_texture_filename(child, &material->pTextureFilename);
            if (FAILED(hr))
                goto err;
        }
        IUnknown_Release(child);
    }
    return D3D_OK;
 
err:
    IUnknown_Release(child);
    return hr;
}
 
static void destroy_materials(struct mesh_data *mesh)
{
    DWORD i;
    for (i = 0; i < mesh->num_materials; i++)
        HeapFree(GetProcessHeap(), 0, mesh->materials[i].pTextureFilename);
    HeapFree(GetProcessHeap(), 0, mesh->materials);
    HeapFree(GetProcessHeap(), 0, mesh->material_indices);
    mesh->num_materials = 0;
    mesh->materials = NULL;
    mesh->material_indices = NULL;
}
 
static HRESULT parse_material_list(ID3DXFileData *filedata, struct mesh_data *mesh)
{
    HRESULT hr;
    SIZE_T data_size;
    const DWORD *data, *in_ptr;
    GUID type;
    ID3DXFileData *child = NULL;
    DWORD num_materials;
    DWORD i;
    SIZE_T nb_children;
 
    destroy_materials(mesh);
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /* template MeshMaterialList {
     *     DWORD nMaterials;
     *     DWORD nFaceIndexes;
     *     array DWORD faceIndexes[nFaceIndexes];
     *     [ Material ]
     * }
     */
 
    in_ptr = data;
    hr = E_FAIL;
 
    if (data_size < sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    num_materials = *in_ptr++;
    if (!num_materials) {
        hr = D3D_OK;
        goto end;
    }
 
    if (data_size < 2 * sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    if (*in_ptr++ != mesh->num_poly_faces) {
        WARN("number of material face indices (%u) doesn't match number of faces (%u)\n",
             *(in_ptr - 1), mesh->num_poly_faces);
        goto end;
    }
    if (data_size < 2 * sizeof(DWORD) + mesh->num_poly_faces * sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    for (i = 0; i < mesh->num_poly_faces; i++) {
        if (*in_ptr++ >= num_materials) {
            WARN("face %u: reference to undefined material %u (only %u materials)\n",
                 i, *(in_ptr - 1), num_materials);
            goto end;
        }
    }
 
    mesh->materials = HeapAlloc(GetProcessHeap(), 0, num_materials * sizeof(*mesh->materials));
    mesh->material_indices = HeapAlloc(GetProcessHeap(), 0, mesh->num_poly_faces * sizeof(*mesh->material_indices));
    if (!mesh->materials || !mesh->material_indices) {
        hr = E_OUTOFMEMORY;
        goto end;
    }
    memcpy(mesh->material_indices, data + 2, mesh->num_poly_faces * sizeof(DWORD));
 
    hr = filedata->lpVtbl->GetChildren(filedata, &nb_children);
    if (FAILED(hr))
        goto end;
 
    for (i = 0; i < nb_children; i++)
    {
        hr = filedata->lpVtbl->GetChild(filedata, i, &child);
        if (FAILED(hr))
            goto end;
        hr = child->lpVtbl->GetType(child, &type);
        if (FAILED(hr))
            goto end;
 
        if (IsEqualGUID(&type, &TID_D3DRMMaterial)) {
            if (mesh->num_materials >= num_materials) {
                WARN("more materials defined than declared\n");
                hr = E_FAIL;
                goto end;
            }
            hr = parse_material(child, &mesh->materials[mesh->num_materials++]);
            if (FAILED(hr))
                goto end;
        }
 
        IUnknown_Release(child);
        child = NULL;
    }
    if (num_materials != mesh->num_materials) {
        WARN("only %u of %u materials defined\n", num_materials, mesh->num_materials);
        hr = E_FAIL;
    }
 
end:
    if (child)
        IUnknown_Release(child);
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
static HRESULT parse_texture_coords(ID3DXFileData *filedata, struct mesh_data *mesh)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data;
 
    HeapFree(GetProcessHeap(), 0, mesh->tex_coords);
    mesh->tex_coords = NULL;
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /* template Coords2d {
     *     FLOAT u;
     *     FLOAT v;
     * }
     * template MeshTextureCoords {
     *     DWORD nTextureCoords;
     *     array Coords2d textureCoords[nTextureCoords];
     * }
     */
 
    hr = E_FAIL;
 
    if (data_size < sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    if (*(DWORD*)data != mesh->num_vertices) {
        WARN("number of texture coordinates (%u) doesn't match number of vertices (%u)\n",
             *(DWORD*)data, mesh->num_vertices);
        goto end;
    }
    data += sizeof(DWORD);
    if (data_size < sizeof(DWORD) + mesh->num_vertices * sizeof(*mesh->tex_coords)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
 
    mesh->tex_coords = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(*mesh->tex_coords));
    if (!mesh->tex_coords) {
        hr = E_OUTOFMEMORY;
        goto end;
    }
    memcpy(mesh->tex_coords, data, mesh->num_vertices * sizeof(*mesh->tex_coords));
 
    mesh->fvf |= D3DFVF_TEX1;
 
    hr = D3D_OK;
 
end:
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
static HRESULT parse_vertex_colors(ID3DXFileData *filedata, struct mesh_data *mesh)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data;
    DWORD num_colors;
    DWORD i;
 
    HeapFree(GetProcessHeap(), 0, mesh->vertex_colors);
    mesh->vertex_colors = NULL;
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /* template IndexedColor {
     *     DWORD index;
     *     ColorRGBA indexColor;
     * }
     * template MeshVertexColors {
     *     DWORD nVertexColors;
     *     array IndexedColor vertexColors[nVertexColors];
     * }
     */
 
    hr = E_FAIL;
 
    if (data_size < sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    num_colors = *(DWORD*)data;
    data += sizeof(DWORD);
    if (data_size < sizeof(DWORD) + num_colors * (sizeof(DWORD) + sizeof(D3DCOLORVALUE))) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
 
    mesh->vertex_colors = HeapAlloc(GetProcessHeap(), 0, mesh->num_vertices * sizeof(DWORD));
    if (!mesh->vertex_colors) {
        hr = E_OUTOFMEMORY;
        goto end;
    }
 
    for (i = 0; i < mesh->num_vertices; i++)
        mesh->vertex_colors[i] = D3DCOLOR_ARGB(0, 0xff, 0xff, 0xff);
    for (i = 0; i < num_colors; i++)
    {
        D3DCOLORVALUE color;
        DWORD index = *(DWORD*)data;
        data += sizeof(DWORD);
        if (index >= mesh->num_vertices) {
            WARN("vertex color %u references undefined vertex %u (only %u vertices)\n",
                 i, index, mesh->num_vertices);
            goto end;
        }
        memcpy(&color, data, sizeof(color));
        data += sizeof(color);
        color.r = min(1.0f, max(0.0f, color.r));
        color.g = min(1.0f, max(0.0f, color.g));
        color.b = min(1.0f, max(0.0f, color.b));
        color.a = min(1.0f, max(0.0f, color.a));
        mesh->vertex_colors[index] = D3DCOLOR_ARGB((BYTE)(color.a * 255.0f + 0.5f),
                                                   (BYTE)(color.r * 255.0f + 0.5f),
                                                   (BYTE)(color.g * 255.0f + 0.5f),
                                                   (BYTE)(color.b * 255.0f + 0.5f));
    }
 
    mesh->fvf |= D3DFVF_DIFFUSE;
 
    hr = D3D_OK;
 
end:
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
static HRESULT parse_normals(ID3DXFileData *filedata, struct mesh_data *mesh)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data;
    DWORD *index_out_ptr;
    DWORD i;
    DWORD num_face_indices = mesh->num_poly_faces * 2 + mesh->num_tri_faces;
 
    HeapFree(GetProcessHeap(), 0, mesh->normals);
    mesh->num_normals = 0;
    mesh->normals = NULL;
    mesh->normal_indices = NULL;
    mesh->fvf |= D3DFVF_NORMAL;
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    /* template Vector {
     *     FLOAT x;
     *     FLOAT y;
     *     FLOAT z;
     * }
     * template MeshFace {
     *     DWORD nFaceVertexIndices;
     *     array DWORD faceVertexIndices[nFaceVertexIndices];
     * }
     * template MeshNormals {
     *     DWORD nNormals;
     *     array Vector normals[nNormals];
     *     DWORD nFaceNormals;
     *     array MeshFace faceNormals[nFaceNormals];
     * }
     */
 
    hr = E_FAIL;
 
    if (data_size < sizeof(DWORD) * 2) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    mesh->num_normals = *(DWORD*)data;
    data += sizeof(DWORD);
    if (data_size < sizeof(DWORD) * 2 + mesh->num_normals * sizeof(D3DXVECTOR3) +
                    num_face_indices * sizeof(DWORD)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
 
    mesh->normals = HeapAlloc(GetProcessHeap(), 0, mesh->num_normals * sizeof(D3DXVECTOR3));
    mesh->normal_indices = HeapAlloc(GetProcessHeap(), 0, num_face_indices * sizeof(DWORD));
    if (!mesh->normals || !mesh->normal_indices) {
        hr = E_OUTOFMEMORY;
        goto end;
    }
 
    memcpy(mesh->normals, data, mesh->num_normals * sizeof(D3DXVECTOR3));
    data += mesh->num_normals * sizeof(D3DXVECTOR3);
    for (i = 0; i < mesh->num_normals; i++)
        D3DXVec3Normalize(&mesh->normals[i], &mesh->normals[i]);
 
    if (*(DWORD*)data != mesh->num_poly_faces) {
        WARN("number of face normals (%u) doesn't match number of faces (%u)\n",
             *(DWORD*)data, mesh->num_poly_faces);
        goto end;
    }
    data += sizeof(DWORD);
    index_out_ptr = mesh->normal_indices;
    for (i = 0; i < mesh->num_poly_faces; i++)
    {
        DWORD j;
        DWORD count = *(DWORD*)data;
        if (count != mesh->num_tri_per_face[i] + 2) {
            WARN("face %u: number of normals (%u) doesn't match number of vertices (%u)\n",
                 i, count, mesh->num_tri_per_face[i] + 2);
            goto end;
        }
        data += sizeof(DWORD);
 
        for (j = 0; j < count; j++) {
            DWORD normal_index = *(DWORD*)data;
            if (normal_index >= mesh->num_normals) {
                WARN("face %u, normal index %u: reference to undefined normal %u (only %u normals)\n",
                     i, j, normal_index, mesh->num_normals);
                goto end;
            }
            *index_out_ptr++ = normal_index;
            data += sizeof(DWORD);
        }
    }
 
    hr =  D3D_OK;
 
end:
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
static HRESULT parse_skin_mesh_info(ID3DXFileData *filedata, struct mesh_data *mesh_data, DWORD index)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data;
 
    TRACE("(%p, %p, %u)\n", filedata, mesh_data, index);
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    hr = E_FAIL;
 
    if (!mesh_data->skin_info) {
        if (data_size < sizeof(WORD) * 3) {
            WARN("truncated data (%ld bytes)\n", data_size);
            goto end;
        }
        /* Skip nMaxSkinWeightsPerVertex and nMaxSkinWeightsPerFace */
        data += 2 * sizeof(WORD);
        mesh_data->nb_bones = *(WORD*)data;
        hr = D3DXCreateSkinInfoFVF(mesh_data->num_vertices, mesh_data->fvf, mesh_data->nb_bones, &mesh_data->skin_info);
    } else {
        const char *name;
        DWORD nb_influences;
 
        /* FIXME: String must be retrieved directly instead of through a pointer once ID3DXFILE is fixed */
        name = *(const char**)data;
        data += sizeof(char*);
 
        nb_influences = *(DWORD*)data;
        data += sizeof(DWORD);
 
        if (data_size < (sizeof(char*) + sizeof(DWORD) + nb_influences * (sizeof(DWORD) + sizeof(FLOAT)) + 16 * sizeof(FLOAT))) {
            WARN("truncated data (%ld bytes)\n", data_size);
            goto end;
        }
 
        hr = mesh_data->skin_info->lpVtbl->SetBoneName(mesh_data->skin_info, index, name);
        if (SUCCEEDED(hr))
            hr = mesh_data->skin_info->lpVtbl->SetBoneInfluence(mesh_data->skin_info, index, nb_influences,
                     (const DWORD*)data, (const FLOAT*)(data + nb_influences * sizeof(DWORD)));
        if (SUCCEEDED(hr))
            hr = mesh_data->skin_info->lpVtbl->SetBoneOffsetMatrix(mesh_data->skin_info, index,
                     (const D3DMATRIX*)(data + nb_influences * (sizeof(DWORD) + sizeof(FLOAT))));
    }
 
end:
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
/* for provide_flags parameters */
#define PROVIDE_MATERIALS 0x1
#define PROVIDE_SKININFO  0x2
#define PROVIDE_ADJACENCY 0x4
 
static HRESULT parse_mesh(ID3DXFileData *filedata, struct mesh_data *mesh_data, DWORD provide_flags)
{
    HRESULT hr;
    SIZE_T data_size;
    const BYTE *data, *in_ptr;
    DWORD *index_out_ptr;
    GUID type;
    ID3DXFileData *child = NULL;
    DWORD i;
    SIZE_T nb_children;
    DWORD nb_skin_weights_info = 0;
 
    /*
     * template Mesh {
     *     DWORD nVertices;
     *     array Vector vertices[nVertices];
     *     DWORD nFaces;
     *     array MeshFace faces[nFaces];
     *     [ ... ]
     * }
     */
 
    hr = filedata->lpVtbl->Lock(filedata, &data_size, (const void**)&data);
    if (FAILED(hr)) return hr;
 
    in_ptr = data;
    hr = E_FAIL;
 
    if (data_size < sizeof(DWORD) * 2) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    mesh_data->num_vertices = *(DWORD*)in_ptr;
    if (data_size < sizeof(DWORD) * 2 + mesh_data->num_vertices * sizeof(D3DXVECTOR3)) {
        WARN("truncated data (%ld bytes)\n", data_size);
        goto end;
    }
    in_ptr += sizeof(DWORD) + mesh_data->num_vertices * sizeof(D3DXVECTOR3);
 
    mesh_data->num_poly_faces = *(DWORD*)in_ptr;
    in_ptr += sizeof(DWORD);
 
    mesh_data->num_tri_faces = 0;
    for (i = 0; i < mesh_data->num_poly_faces; i++)
    {
        DWORD num_poly_vertices;
        DWORD j;
 
        if (data_size - (in_ptr - data) < sizeof(DWORD)) {
            WARN("truncated data (%ld bytes)\n", data_size);
            goto end;
        }
        num_poly_vertices = *(DWORD*)in_ptr;
        in_ptr += sizeof(DWORD);
        if (data_size - (in_ptr - data) < num_poly_vertices * sizeof(DWORD)) {
            WARN("truncated data (%ld bytes)\n", data_size);
            goto end;
        }
        if (num_poly_vertices < 3) {
            WARN("face %u has only %u vertices\n", i, num_poly_vertices);
            goto end;
        }
        for (j = 0; j < num_poly_vertices; j++) {
            if (*(DWORD*)in_ptr >= mesh_data->num_vertices) {
                WARN("face %u, index %u: undefined vertex %u (only %u vertices)\n",
                     i, j, *(DWORD*)in_ptr, mesh_data->num_vertices);
                goto end;
            }
            in_ptr += sizeof(DWORD);
        }
        mesh_data->num_tri_faces += num_poly_vertices - 2;
    }
 
    mesh_data->fvf = D3DFVF_XYZ;
 
    mesh_data->vertices = HeapAlloc(GetProcessHeap(), 0,
            mesh_data->num_vertices * sizeof(*mesh_data->vertices));
    mesh_data->num_tri_per_face = HeapAlloc(GetProcessHeap(), 0,
            mesh_data->num_poly_faces * sizeof(*mesh_data->num_tri_per_face));
    mesh_data->indices = HeapAlloc(GetProcessHeap(), 0,
            (mesh_data->num_tri_faces + mesh_data->num_poly_faces * 2) * sizeof(*mesh_data->indices));
    if (!mesh_data->vertices || !mesh_data->num_tri_per_face || !mesh_data->indices) {
        hr = E_OUTOFMEMORY;
        goto end;
    }
 
    in_ptr = data + sizeof(DWORD);
    memcpy(mesh_data->vertices, in_ptr, mesh_data->num_vertices * sizeof(D3DXVECTOR3));
    in_ptr += mesh_data->num_vertices * sizeof(D3DXVECTOR3) + sizeof(DWORD);
 
    index_out_ptr = mesh_data->indices;
    for (i = 0; i < mesh_data->num_poly_faces; i++)
    {
        DWORD count;
 
        count = *(DWORD*)in_ptr;
        in_ptr += sizeof(DWORD);
        mesh_data->num_tri_per_face[i] = count - 2;
 
        while (count--) {
            *index_out_ptr++ = *(DWORD*)in_ptr;
            in_ptr += sizeof(DWORD);
        }
    }
 
    hr = filedata->lpVtbl->GetChildren(filedata, &nb_children);
    if (FAILED(hr))
        goto end;
 
    for (i = 0; i < nb_children; i++)
    {
        hr = filedata->lpVtbl->GetChild(filedata, i, &child);
        if (FAILED(hr))
            goto end;
        hr = child->lpVtbl->GetType(child, &type);
        if (FAILED(hr))
            goto end;
 
        if (IsEqualGUID(&type, &TID_D3DRMMeshNormals)) {
            hr = parse_normals(child, mesh_data);
        } else if (IsEqualGUID(&type, &TID_D3DRMMeshVertexColors)) {
            hr = parse_vertex_colors(child, mesh_data);
        } else if (IsEqualGUID(&type, &TID_D3DRMMeshTextureCoords)) {
            hr = parse_texture_coords(child, mesh_data);
        } else if (IsEqualGUID(&type, &TID_D3DRMMeshMaterialList) &&
                   (provide_flags & PROVIDE_MATERIALS))
        {
            hr = parse_material_list(child, mesh_data);
        } else if (provide_flags & PROVIDE_SKININFO) {
            if (IsEqualGUID(&type, &DXFILEOBJ_XSkinMeshHeader)) {
                if (mesh_data->skin_info) {
                    WARN("Skin mesh header already encountered\n");
                    hr = E_FAIL;
                    goto end;
                }
                hr = parse_skin_mesh_info(child, mesh_data, 0);
                if (FAILED(hr))
                    goto end;
            } else if (IsEqualGUID(&type, &DXFILEOBJ_SkinWeights)) {
                if (!mesh_data->skin_info) {
                    WARN("Skin weights found but skin mesh header not encountered yet\n");
                    hr = E_FAIL;
                    goto end;
                }
                hr = parse_skin_mesh_info(child, mesh_data, nb_skin_weights_info);
                if (FAILED(hr))
                    goto end;
                nb_skin_weights_info++;
            }
        }
        if (FAILED(hr))
            goto end;
 
        IUnknown_Release(child);
        child = NULL;
    }
 
    if (mesh_data->skin_info && (nb_skin_weights_info != mesh_data->nb_bones)) {
        WARN("Mismatch between nb skin weights info %u encountered and nb bones %u from skin mesh header\n",
             nb_skin_weights_info, mesh_data->nb_bones);
        hr = E_FAIL;
        goto end;
    }
 
    if ((provide_flags & PROVIDE_SKININFO) && !mesh_data->skin_info)
    {
        if (FAILED(hr = D3DXCreateSkinInfoFVF(mesh_data->num_vertices, mesh_data->fvf,
                mesh_data->nb_bones, &mesh_data->skin_info)))
            goto end;
    }
 
    hr = D3D_OK;
 
end:
    if (child)
        IUnknown_Release(child);
    filedata->lpVtbl->Unlock(filedata);
    return hr;
}
 
static HRESULT generate_effects(ID3DXBuffer *materials, DWORD num_materials,
                                ID3DXBuffer **effects)
{
    HRESULT hr;
    D3DXEFFECTINSTANCE *effect_ptr;
    BYTE *out_ptr;
    const D3DXMATERIAL *material_ptr = ID3DXBuffer_GetBufferPointer(materials);
    static const struct {
        const char *param_name;
        DWORD name_size;
        DWORD num_bytes;
        DWORD value_offset;
    } material_effects[] = {
#define EFFECT_TABLE_ENTRY(str, field) \
    {str, sizeof(str), sizeof(material_ptr->MatD3D.field), offsetof(D3DXMATERIAL, MatD3D.field)}
        EFFECT_TABLE_ENTRY("Diffuse", Diffuse),
        EFFECT_TABLE_ENTRY("Power", Power),
        EFFECT_TABLE_ENTRY("Specular", Specular),
        EFFECT_TABLE_ENTRY("Emissive", Emissive),
        EFFECT_TABLE_ENTRY("Ambient", Ambient),
#undef EFFECT_TABLE_ENTRY
    };
    static const char texture_paramname[] = "Texture0@Name";
    DWORD buffer_size;
    DWORD i;
 
    /* effects buffer layout:
     *
     * D3DXEFFECTINSTANCE effects[num_materials];
     * for (effect in effects)
     * {
     *     D3DXEFFECTDEFAULT defaults[effect.NumDefaults];
     *     for (default in defaults)
     *     {
     *         *default.pParamName;
     *         *default.pValue;
     *     }
     * }
     */
    buffer_size = sizeof(D3DXEFFECTINSTANCE);
    buffer_size += sizeof(D3DXEFFECTDEFAULT) * ARRAY_SIZE(material_effects);
    for (i = 0; i < ARRAY_SIZE(material_effects); i++) {
        buffer_size += material_effects[i].name_size;
        buffer_size += material_effects[i].num_bytes;
    }
    buffer_size *= num_materials;
    for (i = 0; i < num_materials; i++) {
        if (material_ptr[i].pTextureFilename) {
            buffer_size += sizeof(D3DXEFFECTDEFAULT);
            buffer_size += sizeof(texture_paramname);
            buffer_size += strlen(material_ptr[i].pTextureFilename) + 1;
        }
    }
 
    hr = D3DXCreateBuffer(buffer_size, effects);
    if (FAILED(hr)) return hr;
    effect_ptr = ID3DXBuffer_GetBufferPointer(*effects);
    out_ptr = (BYTE*)(effect_ptr + num_materials);
 
    for (i = 0; i < num_materials; i++)
    {
        DWORD j;
        D3DXEFFECTDEFAULT *defaults = (D3DXEFFECTDEFAULT*)out_ptr;
 
        effect_ptr->pDefaults = defaults;
        effect_ptr->NumDefaults = material_ptr->pTextureFilename ? 6 : 5;
        out_ptr = (BYTE*)(effect_ptr->pDefaults + effect_ptr->NumDefaults);
 
        for (j = 0; j < ARRAY_SIZE(material_effects); j++)
        {
            defaults->pParamName = (char *)out_ptr;
            strcpy(defaults->pParamName, material_effects[j].param_name);
            defaults->pValue = defaults->pParamName + material_effects[j].name_size;
            defaults->Type = D3DXEDT_FLOATS;
            defaults->NumBytes = material_effects[j].num_bytes;
            memcpy(defaults->pValue, (BYTE*)material_ptr + material_effects[j].value_offset, defaults->NumBytes);
            out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
            defaults++;
        }
 
        if (material_ptr->pTextureFilename)
        {
            defaults->pParamName = (char *)out_ptr;
            strcpy(defaults->pParamName, texture_paramname);
            defaults->pValue = defaults->pParamName + sizeof(texture_paramname);
            defaults->Type = D3DXEDT_STRING;
            defaults->NumBytes = strlen(material_ptr->pTextureFilename) + 1;
            strcpy(defaults->pValue, material_ptr->pTextureFilename);
            out_ptr = (BYTE*)defaults->pValue + defaults->NumBytes;
        }
        material_ptr++;
        effect_ptr++;
    }
    assert(out_ptr - (BYTE*)ID3DXBuffer_GetBufferPointer(*effects) == buffer_size);
 
    return D3D_OK;
}
 
HRESULT WINAPI D3DXLoadSkinMeshFromXof(struct ID3DXFileData *filedata, DWORD options,
        struct IDirect3DDevice9 *device, struct ID3DXBuffer **adjacency_out, struct ID3DXBuffer **materials_out,
        struct ID3DXBuffer **effects_out, DWORD *num_materials_out, struct ID3DXSkinInfo **skin_info_out,
        struct ID3DXMesh **mesh_out)
{
    HRESULT hr;
    DWORD *index_in_ptr;
    struct mesh_data mesh_data;
    DWORD total_vertices;
    ID3DXMesh *d3dxmesh = NULL;
    ID3DXBuffer *adjacency = NULL;
    ID3DXBuffer *materials = NULL;
    ID3DXBuffer *effects = NULL;
    struct vertex_duplication {
        DWORD normal_index;
        struct list entry;
    } *duplications = NULL;
    DWORD i;
    void *vertices = NULL;
    void *indices = NULL;
    BYTE *out_ptr;
    DWORD provide_flags = 0;
 
    TRACE("(%p, %x, %p, %p, %p, %p, %p, %p, %p)\n", filedata, options, device, adjacency_out, materials_out,
          effects_out, num_materials_out, skin_info_out, mesh_out);
 
    ZeroMemory(&mesh_data, sizeof(mesh_data));
 
    if (num_materials_out || materials_out || effects_out)
        provide_flags |= PROVIDE_MATERIALS;
    if (skin_info_out)
        provide_flags |= PROVIDE_SKININFO;
 
    hr = parse_mesh(filedata, &mesh_data, provide_flags);
    if (FAILED(hr)) goto cleanup;
 
    total_vertices = mesh_data.num_vertices;
    if (mesh_data.fvf & D3DFVF_NORMAL) {
        /* duplicate vertices with multiple normals */
        DWORD num_face_indices = mesh_data.num_poly_faces * 2 + mesh_data.num_tri_faces;
        duplications = HeapAlloc(GetProcessHeap(), 0, (mesh_data.num_vertices + num_face_indices) * sizeof(*duplications));
        if (!duplications) {
            hr = E_OUTOFMEMORY;
            goto cleanup;
        }
        for (i = 0; i < total_vertices; i++)
        {
            duplications[i].normal_index = -1;
            list_init(&duplications[i].entry);
        }
        for (i = 0; i < num_face_indices; i++) {
            DWORD vertex_index = mesh_data.indices[i];
            DWORD normal_index = mesh_data.normal_indices[i];
            struct vertex_duplication *dup_ptr = &duplications[vertex_index];
 
            if (dup_ptr->normal_index == -1) {
                dup_ptr->normal_index = normal_index;
            } else {
                D3DXVECTOR3 *new_normal = &mesh_data.normals[normal_index];
                struct list *dup_list = &dup_ptr->entry;
                while (TRUE) {
                    D3DXVECTOR3 *cur_normal = &mesh_data.normals[dup_ptr->normal_index];
                    if (new_normal->x == cur_normal->x &&
                        new_normal->y == cur_normal->y &&
                        new_normal->z == cur_normal->z)
                    {
                        mesh_data.indices[i] = dup_ptr - duplications;
                        break;
                    } else if (!list_next(dup_list, &dup_ptr->entry)) {
                        dup_ptr = &duplications[total_vertices++];
                        dup_ptr->normal_index = normal_index;
                        list_add_tail(dup_list, &dup_ptr->entry);
                        mesh_data.indices[i] = dup_ptr - duplications;
                        break;
                    } else {
                        dup_ptr = LIST_ENTRY(list_next(dup_list, &dup_ptr->entry),
                                             struct vertex_duplication, entry);
                    }
                }
            }
        }
    }
 
    hr = D3DXCreateMeshFVF(mesh_data.num_tri_faces, total_vertices, options, mesh_data.fvf, device, &d3dxmesh);
    if (FAILED(hr)) goto cleanup;
 
    hr = d3dxmesh->lpVtbl->LockVertexBuffer(d3dxmesh, 0, &vertices);
    if (FAILED(hr)) goto cleanup;
 
    out_ptr = vertices;
    for (i = 0; i < mesh_data.num_vertices; i++) {
        *(D3DXVECTOR3*)out_ptr = mesh_data.vertices[i];
        out_ptr += sizeof(D3DXVECTOR3);
        if (mesh_data.fvf & D3DFVF_NORMAL) {
            if (duplications[i].normal_index == -1)
                ZeroMemory(out_ptr, sizeof(D3DXVECTOR3));
            else
                *(D3DXVECTOR3*)out_ptr = mesh_data.normals[duplications[i].normal_index];
            out_ptr += sizeof(D3DXVECTOR3);
        }
        if (mesh_data.fvf & D3DFVF_DIFFUSE) {
            *(DWORD*)out_ptr = mesh_data.vertex_colors[i];
            out_ptr += sizeof(DWORD);
        }
        if (mesh_data.fvf & D3DFVF_TEX1) {
            *(D3DXVECTOR2*)out_ptr = mesh_data.tex_coords[i];
            out_ptr += sizeof(D3DXVECTOR2);
        }
    }
    if (mesh_data.fvf & D3DFVF_NORMAL) {
        DWORD vertex_size = D3DXGetFVFVertexSize(mesh_data.fvf);
        out_ptr = vertices;
        for (i = 0; i < mesh_data.num_vertices; i++) {
            struct vertex_duplication *dup_ptr;
            LIST_FOR_EACH_ENTRY(dup_ptr, &duplications[i].entry, struct vertex_duplication, entry)
            {
                int j = dup_ptr - duplications;
                BYTE *dest_vertex = (BYTE*)vertices + j * vertex_size;
 
                memcpy(dest_vertex, out_ptr, vertex_size);
                dest_vertex += sizeof(D3DXVECTOR3);
                *(D3DXVECTOR3*)dest_vertex = mesh_data.normals[dup_ptr->normal_index];
            }
            out_ptr += vertex_size;
        }
    }
    d3dxmesh->lpVtbl->UnlockVertexBuffer(d3dxmesh);
 
    hr = d3dxmesh->lpVtbl->LockIndexBuffer(d3dxmesh, 0, &indices);
    if (FAILED(hr)) goto cleanup;
 
    index_in_ptr = mesh_data.indices;
#define FILL_INDEX_BUFFER(indices_var) \
        for (i = 0; i < mesh_data.num_poly_faces; i++) \
        { \
            DWORD count = mesh_data.num_tri_per_face[i]; \
            WORD first_index = *index_in_ptr++; \
            while (count--) { \
                *indices_var++ = first_index; \
                *indices_var++ = *index_in_ptr; \
                index_in_ptr++; \
                *indices_var++ = *index_in_ptr; \
            } \
            index_in_ptr++; \
        }
    if (options & D3DXMESH_32BIT) {
        DWORD *dword_indices = indices;
        FILL_INDEX_BUFFER(dword_indices)
    } else {
        WORD *word_indices = indices;
        FILL_INDEX_BUFFER(word_indices)
    }
#undef FILL_INDEX_BUFFER
    d3dxmesh->lpVtbl->UnlockIndexBuffer(d3dxmesh);
 
    if (mesh_data.material_indices) {
        DWORD *attrib_buffer = NULL;
        hr = d3dxmesh->lpVtbl->LockAttributeBuffer(d3dxmesh, 0, &attrib_buffer);
        if (FAILED(hr)) goto cleanup;
        for (i = 0; i < mesh_data.num_poly_faces; i++)
        {
            DWORD count = mesh_data.num_tri_per_face[i];
            while (count--)
                *attrib_buffer++ = mesh_data.material_indices[i];
        }
        d3dxmesh->lpVtbl->UnlockAttributeBuffer(d3dxmesh);
 
        hr = d3dxmesh->lpVtbl->OptimizeInplace(d3dxmesh,
                D3DXMESHOPT_ATTRSORT | D3DXMESHOPT_IGNOREVERTS | D3DXMESHOPT_DONOTSPLIT,
                NULL, NULL, NULL, NULL);
        if (FAILED(hr)) goto cleanup;
    }
 
    if (mesh_data.num_materials && (materials_out || effects_out)) {
        DWORD buffer_size = mesh_data.num_materials * sizeof(D3DXMATERIAL);
        char *strings_out_ptr;
        D3DXMATERIAL *materials_ptr;
 
        for (i = 0; i < mesh_data.num_materials; i++) {
            if (mesh_data.materials[i].pTextureFilename)
                buffer_size += strlen(mesh_data.materials[i].pTextureFilename) + 1;
        }
 
        hr = D3DXCreateBuffer(buffer_size, &materials);
        if (FAILED(hr)) goto cleanup;
 
        materials_ptr = ID3DXBuffer_GetBufferPointer(materials);
        memcpy(materials_ptr, mesh_data.materials, mesh_data.num_materials * sizeof(D3DXMATERIAL));
        strings_out_ptr = (char*)(materials_ptr + mesh_data.num_materials);
        for (i = 0; i < mesh_data.num_materials; i++) {
            if (materials_ptr[i].pTextureFilename) {
                strcpy(strings_out_ptr, mesh_data.materials[i].pTextureFilename);
                materials_ptr[i].pTextureFilename = strings_out_ptr;
                strings_out_ptr += strlen(mesh_data.materials[i].pTextureFilename) + 1;
            }
        }
    }
 
    if (mesh_data.num_materials && effects_out) {
        hr = generate_effects(materials, mesh_data.num_materials, &effects);
        if (FAILED(hr)) goto cleanup;
 
        if (!materials_out) {
            ID3DXBuffer_Release(materials);
            materials = NULL;
        }
    }
 
    if (adjacency_out) {
        hr = D3DXCreateBuffer(mesh_data.num_tri_faces * 3 * sizeof(DWORD), &adjacency);
        if (FAILED(hr)) goto cleanup;
        hr = d3dxmesh->lpVtbl->GenerateAdjacency(d3dxmesh, 0.0f, ID3DXBuffer_GetBufferPointer(adjacency));
        if (FAILED(hr)) goto cleanup;
    }
 
    *mesh_out = d3dxmesh;
    if (adjacency_out) *adjacency_out = adjacency;
    if (num_materials_out) *num_materials_out = mesh_data.num_materials;
    if (materials_out) *materials_out = materials;
    if (effects_out) *effects_out = effects;
    if (skin_info_out) *skin_info_out = mesh_data.skin_info;
 
    hr = D3D_OK;
cleanup:
    if (FAILED(hr)) {
        if (d3dxmesh) IUnknown_Release(d3dxmesh);
        if (adjacency) ID3DXBuffer_Release(adjacency);
        if (materials) ID3DXBuffer_Release(materials);
        if (effects) ID3DXBuffer_Release(effects);
        if (mesh_data.skin_info) mesh_data.skin_info->lpVtbl->Release(mesh_data.skin_info);
        if (skin_info_out) *skin_info_out = NULL;
    }
    HeapFree(GetProcessHeap(), 0, mesh_data.vertices);
    HeapFree(GetProcessHeap(), 0, mesh_data.num_tri_per_face);
    HeapFree(GetProcessHeap(), 0, mesh_data.indices);
    HeapFree(GetProcessHeap(), 0, mesh_data.normals);
    HeapFree(GetProcessHeap(), 0, mesh_data.normal_indices);
    destroy_materials(&mesh_data);
    HeapFree(GetProcessHeap(), 0, mesh_data.tex_coords);
    HeapFree(GetProcessHeap(), 0, mesh_data.vertex_colors);
    HeapFree(GetProcessHeap(), 0, duplications);
    return hr;
}
 
HRESULT WINAPI D3DXLoadMeshHierarchyFromXA(const char *filename, DWORD options, struct IDirect3DDevice9 *device,
        struct ID3DXAllocateHierarchy *alloc_hier, struct ID3DXLoadUserData *load_user_data,
        D3DXFRAME **frame_hierarchy, struct ID3DXAnimationController **anim_controller)
{
    WCHAR *filenameW;
    HRESULT hr;
    int len;
 
    TRACE("filename %s, options %#x, device %p, alloc_hier %p, "
            "load_user_data %p, frame_hierarchy %p, anim_controller %p.\n",
            debugstr_a(filename), options, device, alloc_hier,
            load_user_data, frame_hierarchy, anim_controller);
 
    if (!filename)
        return D3DERR_INVALIDCALL;
 
    len = MultiByteToWideChar(CP_ACP, 0, filename, -1, NULL, 0);
    filenameW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
    if (!filenameW) return E_OUTOFMEMORY;
    MultiByteToWideChar(CP_ACP, 0, filename, -1, filenameW, len);
 
    hr = D3DXLoadMeshHierarchyFromXW(filenameW, options, device,
            alloc_hier, load_user_data, frame_hierarchy, anim_controller);
    HeapFree(GetProcessHeap(), 0, filenameW);
 
    return hr;
}
 
HRESULT WINAPI D3DXLoadMeshHierarchyFromXW(const WCHAR *filename, DWORD options, struct IDirect3DDevice9 *device,
        struct ID3DXAllocateHierarchy *alloc_hier, struct ID3DXLoadUserData *load_user_data,
        D3DXFRAME **frame_hierarchy, struct ID3DXAnimationController **anim_controller)
{
    void *buffer;
    HRESULT hr;
    DWORD size;
 
    TRACE("filename %s, options %#x, device %p, alloc_hier %p, "
            "load_user_data %p, frame_hierarchy %p, anim_controller %p.\n",
            debugstr_w(filename), options, device, alloc_hier,
            load_user_data, frame_hierarchy, anim_controller);
 
    if (!filename)
        return D3DERR_INVALIDCALL;
 
    hr = map_view_of_file(filename, &buffer, &size);
    if (FAILED(hr))
        return D3DXERR_INVALIDDATA;
 
    hr = D3DXLoadMeshHierarchyFromXInMemory(buffer, size, options, device,
            alloc_hier, load_user_data, frame_hierarchy, anim_controller);
 
    UnmapViewOfFile(buffer);
 
    return hr;
}
 
static HRESULT filedata_get_name(ID3DXFileData *filedata, char **name)
{
    HRESULT hr;
    SIZE_T name_len;
 
    hr = filedata->lpVtbl->GetName(filedata, NULL, &name_len);
    if (FAILED(hr)) return hr;
 
    if (!name_len)
        name_len++;
    *name = HeapAlloc(GetProcessHeap(), 0, name_len);
    if (!*name) return E_OUTOFMEMORY;