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

   1  /*
   2  * Mesh operations specific to D3DX9.
   3  *
   4  * Copyright (C) 2005 Henri Verbeet
   5  * Copyright (C) 2006 Ivan Gyurdiev
   6  * Copyright (C) 2009 David Adam
   7  * Copyright (C) 2010 Tony Wasserka
   8  * Copyright (C) 2011 Dylan Smith
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2.1 of the License, or (at your option) any later version.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  23  */
  24
  25 #include "config.h"
  26 #include "wine/port.h"
  27
  28 #define NONAMELESSUNION
  29 #include "windef.h"
  30 #include "wingdi.h"
  31 #include "d3dx9.h"
  32 #include "wine/debug.h"
  33 #include "wine/unicode.h"
  34 #include "d3dx9_36_private.h"
  35
  36 WINE_DEFAULT_DEBUG_CHANNEL(d3dx);
  37
  38 typedef struct ID3DXMeshImpl
  39 {
  40     ID3DXMesh ID3DXMesh_iface;
  41     LONG ref;
  42
  43     DWORD numfaces;
  44     DWORD numvertices;
  45     DWORD options;
  46     DWORD fvf;
  47     IDirect3DDevice9 *device;
  48     IDirect3DVertexDeclaration9 *vertex_declaration;
  49     IDirect3DVertexBuffer9 *vertex_buffer;
  50     IDirect3DIndexBuffer9 *index_buffer;
  51 } ID3DXMeshImpl;
  52
  53 static inline ID3DXMeshImpl *impl_from_ID3DXMesh(ID3DXMesh *iface)
  54 {
  55     return CONTAINING_RECORD(iface, ID3DXMeshImpl, ID3DXMesh_iface);
  56 }
  57
  58 static HRESULT WINAPI ID3DXMeshImpl_QueryInterface(ID3DXMesh *iface, REFIID riid, LPVOID *object)
  59 {
  60     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  61
  62     TRACE("(%p)->(%s, %p)\n", This, debugstr_guid(riid), object);
  63
  64     if (IsEqualGUID(riid, &IID_IUnknown) ||
  65         IsEqualGUID(riid, &IID_ID3DXBaseMesh) ||
  66         IsEqualGUID(riid, &IID_ID3DXMesh))
  67     {
  68         iface->lpVtbl->AddRef(iface);
  69         *object = This;
  70         return S_OK;
  71     }
  72
  73     WARN("Interface %s not found.\n", debugstr_guid(riid));
  74
  75     return E_NOINTERFACE;
  76 }
  77
  78 static ULONG WINAPI ID3DXMeshImpl_AddRef(ID3DXMesh *iface)
  79 {
  80     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  81
  82     TRACE("(%p)->(): AddRef from %d\n", This, This->ref);
  83
  84     return InterlockedIncrement(&This->ref);
  85 }
  86
  87 static ULONG WINAPI ID3DXMeshImpl_Release(ID3DXMesh *iface)
  88 {
  89     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
  90     ULONG ref = InterlockedDecrement(&This->ref);
  91
  92     TRACE("(%p)->(): Release from %d\n", This, ref + 1);
  93
  94     if (!ref)
  95     {
  96         IDirect3DIndexBuffer9_Release(This->index_buffer);
  97         IDirect3DVertexBuffer9_Release(This->vertex_buffer);
  98         IDirect3DVertexDeclaration9_Release(This->vertex_declaration);
  99         IDirect3DDevice9_Release(This->device);
 100         HeapFree(GetProcessHeap(), 0, This);
 101     }
 102
 103     return ref;
 104 }
 105
 106 /*** ID3DXBaseMesh ***/
 107 static HRESULT WINAPI ID3DXMeshImpl_DrawSubset(ID3DXMesh *iface, DWORD attrib_id)
 108 {
 109     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 110
 111     FIXME("(%p)->(%u): stub\n", This, attrib_id);
 112
 113     return E_NOTIMPL;
 114 }
 115
 116 static DWORD WINAPI ID3DXMeshImpl_GetNumFaces(ID3DXMesh *iface)
 117 {
 118     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 119
 120     TRACE("(%p)\n", This);
 121
 122     return This->numfaces;
 123 }
 124
 125 static DWORD WINAPI ID3DXMeshImpl_GetNumVertices(ID3DXMesh *iface)
 126 {
 127     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 128
 129     TRACE("(%p)\n", This);
 130
 131     return This->numvertices;
 132 }
 133
 134 static DWORD WINAPI ID3DXMeshImpl_GetFVF(ID3DXMesh *iface)
 135 {
 136     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 137
 138     TRACE("(%p)\n", This);
 139
 140     return This->fvf;
 141 }
 142
 143 static HRESULT WINAPI ID3DXMeshImpl_GetDeclaration(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 144 {
 145     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 146     UINT numelements;
 147
 148     TRACE("(%p)\n", This);
 149
 150     if (declaration == NULL) return D3DERR_INVALIDCALL;
 151
 152     return IDirect3DVertexDeclaration9_GetDeclaration(This->vertex_declaration,
 153                                                       declaration,
 154                                                       &numelements);
 155 }
 156
 157 static DWORD WINAPI ID3DXMeshImpl_GetNumBytesPerVertex(ID3DXMesh *iface)
 158 {
 159     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 160
 161     TRACE("iface (%p)\n", This);
 162
 163     return D3DXGetFVFVertexSize(This->fvf);
 164 }
 165
 166 static DWORD WINAPI ID3DXMeshImpl_GetOptions(ID3DXMesh *iface)
 167 {
 168     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 169
 170     TRACE("(%p)\n", This);
 171
 172     return This->options;
 173 }
 174
 175 static HRESULT WINAPI ID3DXMeshImpl_GetDevice(ID3DXMesh *iface, LPDIRECT3DDEVICE9 *device)
 176 {
 177     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 178
 179     TRACE("(%p)->(%p)\n", This, device);
 180
 181     if (device == NULL) return D3DERR_INVALIDCALL;
 182     *device = This->device;
 183     IDirect3DDevice9_AddRef(This->device);
 184
 185     return D3D_OK;
 186 }
 187
 188 static HRESULT WINAPI ID3DXMeshImpl_CloneMeshFVF(ID3DXMesh *iface, DWORD options, DWORD fvf, LPDIRECT3DDEVICE9 device, LPD3DXMESH *clone_mesh)
 189 {
 190     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 191
 192     FIXME("(%p)->(%u,%u,%p,%p): stub\n", This, options, fvf, device, clone_mesh);
 193
 194     return E_NOTIMPL;
 195 }
 196
 197 static HRESULT WINAPI ID3DXMeshImpl_CloneMesh(ID3DXMesh *iface, DWORD options, CONST D3DVERTEXELEMENT9 *declaration, LPDIRECT3DDEVICE9 device,
 198                                               LPD3DXMESH *clone_mesh)
 199 {
 200     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 201
 202     FIXME("(%p)->(%u,%p,%p,%p): stub\n", This, options, declaration, device, clone_mesh);
 203
 204     return E_NOTIMPL;
 205 }
 206
 207 static HRESULT WINAPI ID3DXMeshImpl_GetVertexBuffer(ID3DXMesh *iface, LPDIRECT3DVERTEXBUFFER9 *vertex_buffer)
 208 {
 209     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 210
 211     TRACE("(%p)->(%p)\n", This, vertex_buffer);
 212
 213     if (vertex_buffer == NULL) return D3DERR_INVALIDCALL;
 214     *vertex_buffer = This->vertex_buffer;
 215     IDirect3DVertexBuffer9_AddRef(This->vertex_buffer);
 216
 217     return D3D_OK;
 218 }
 219
 220 static HRESULT WINAPI ID3DXMeshImpl_GetIndexBuffer(ID3DXMesh *iface, LPDIRECT3DINDEXBUFFER9 *index_buffer)
 221 {
 222     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 223
 224     TRACE("(%p)->(%p)\n", This, index_buffer);
 225
 226     if (index_buffer == NULL) return D3DERR_INVALIDCALL;
 227     *index_buffer = This->index_buffer;
 228     IDirect3DIndexBuffer9_AddRef(This->index_buffer);
 229
 230     return D3D_OK;
 231 }
 232
 233 static HRESULT WINAPI ID3DXMeshImpl_LockVertexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 234 {
 235     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 236
 237     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 238
 239     return IDirect3DVertexBuffer9_Lock(This->vertex_buffer, 0, 0, data, flags);
 240 }
 241
 242 static HRESULT WINAPI ID3DXMeshImpl_UnlockVertexBuffer(ID3DXMesh *iface)
 243 {
 244     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 245
 246     TRACE("(%p)\n", This);
 247
 248     return IDirect3DVertexBuffer9_Unlock(This->vertex_buffer);
 249 }
 250
 251 static HRESULT WINAPI ID3DXMeshImpl_LockIndexBuffer(ID3DXMesh *iface, DWORD flags, LPVOID *data)
 252 {
 253     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 254
 255     TRACE("(%p)->(%u,%p)\n", This, flags, data);
 256
 257     return IDirect3DIndexBuffer9_Lock(This->index_buffer, 0, 0, data, flags);
 258 }
 259
 260 static HRESULT WINAPI ID3DXMeshImpl_UnlockIndexBuffer(ID3DXMesh *iface)
 261 {
 262     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 263
 264     TRACE("(%p)\n", This);
 265
 266     return IDirect3DIndexBuffer9_Unlock(This->index_buffer);
 267 }
 268
 269 static HRESULT WINAPI ID3DXMeshImpl_GetAttributeTable(ID3DXMesh *iface, D3DXATTRIBUTERANGE *attrib_table, DWORD *attrib_table_size)
 270 {
 271     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 272
 273     FIXME("(%p)->(%p,%p): stub\n", This, attrib_table, attrib_table_size);
 274
 275     return E_NOTIMPL;
 276 }
 277
 278 static HRESULT WINAPI ID3DXMeshImpl_ConvertPointRepsToAdjacency(ID3DXMesh *iface, CONST DWORD *point_reps, DWORD *adjacency)
 279 {
 280     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 281
 282     FIXME("(%p)->(%p,%p): stub\n", This, point_reps, adjacency);
 283
 284     return E_NOTIMPL;
 285 }
 286
 287 static HRESULT WINAPI ID3DXMeshImpl_ConvertAdjacencyToPointReps(ID3DXMesh *iface, CONST DWORD *adjacency, DWORD *point_reps)
 288 {
 289     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 290
 291     FIXME("(%p)->(%p,%p): stub\n", This, adjacency, point_reps);
 292
 293     return E_NOTIMPL;
 294 }
 295
 296 static HRESULT WINAPI ID3DXMeshImpl_GenerateAdjacency(ID3DXMesh *iface, FLOAT epsilon, DWORD *adjacency)
 297 {
 298     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 299
 300     FIXME("(%p)->(%f,%p): stub\n", This, epsilon, adjacency);
 301
 302     return E_NOTIMPL;
 303 }
 304
 305 static HRESULT WINAPI ID3DXMeshImpl_UpdateSemantics(ID3DXMesh *iface, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 306 {
 307     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 308
 309     FIXME("(%p)->(%p): stub\n", This, declaration);
 310
 311     return E_NOTIMPL;
 312 }
 313
 314 /*** ID3DXMesh ***/
 315 static HRESULT WINAPI ID3DXMeshImpl_LockAttributeBuffer(ID3DXMesh *iface, DWORD flags, DWORD **data)
 316 {
 317     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 318
 319     FIXME("(%p)->(%u,%p): stub\n", This, flags, data);
 320
 321     return E_NOTIMPL;
 322 }
 323
 324 static HRESULT WINAPI ID3DXMeshImpl_UnlockAttributeBuffer(ID3DXMesh *iface)
 325 {
 326     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 327
 328     FIXME("(%p): stub\n", This);
 329
 330     return E_NOTIMPL;
 331 }
 332
 333 static HRESULT WINAPI ID3DXMeshImpl_Optimize(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
 334                                              DWORD *face_remap, LPD3DXBUFFER *vertex_remap, LPD3DXMESH *opt_mesh)
 335 {
 336     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 337
 338     FIXME("(%p)->(%u,%p,%p,%p,%p,%p): stub\n", This, flags, adjacency_in, adjacency_out, face_remap, vertex_remap, opt_mesh);
 339
 340     return E_NOTIMPL;
 341 }
 342
 343 static HRESULT WINAPI ID3DXMeshImpl_OptimizeInplace(ID3DXMesh *iface, DWORD flags, CONST DWORD *adjacency_in, DWORD *adjacency_out,
 344                                                     DWORD *face_remap, LPD3DXBUFFER *vertex_remap)
 345 {
 346     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 347
 348     FIXME("(%p)->(%u,%p,%p,%p,%p): stub\n", This, flags, adjacency_in, adjacency_out, face_remap, vertex_remap);
 349
 350     return E_NOTIMPL;
 351 }
 352
 353 static HRESULT WINAPI ID3DXMeshImpl_SetAttributeTable(ID3DXMesh *iface, CONST D3DXATTRIBUTERANGE *attrib_table, DWORD attrib_table_size)
 354 {
 355     ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface);
 356
 357     FIXME("(%p)->(%p,%u): stub\n", This, attrib_table, attrib_table_size);
 358
 359     return E_NOTIMPL;
 360 }
 361
 362 static const struct ID3DXMeshVtbl D3DXMesh_Vtbl =
 363 {
 364     /*** IUnknown methods ***/
 365     ID3DXMeshImpl_QueryInterface,
 366     ID3DXMeshImpl_AddRef,
 367     ID3DXMeshImpl_Release,
 368     /*** ID3DXBaseMesh ***/
 369     ID3DXMeshImpl_DrawSubset,
 370     ID3DXMeshImpl_GetNumFaces,
 371     ID3DXMeshImpl_GetNumVertices,
 372     ID3DXMeshImpl_GetFVF,
 373     ID3DXMeshImpl_GetDeclaration,
 374     ID3DXMeshImpl_GetNumBytesPerVertex,
 375     ID3DXMeshImpl_GetOptions,
 376     ID3DXMeshImpl_GetDevice,
 377     ID3DXMeshImpl_CloneMeshFVF,
 378     ID3DXMeshImpl_CloneMesh,
 379     ID3DXMeshImpl_GetVertexBuffer,
 380     ID3DXMeshImpl_GetIndexBuffer,
 381     ID3DXMeshImpl_LockVertexBuffer,
 382     ID3DXMeshImpl_UnlockVertexBuffer,
 383     ID3DXMeshImpl_LockIndexBuffer,
 384     ID3DXMeshImpl_UnlockIndexBuffer,
 385     ID3DXMeshImpl_GetAttributeTable,
 386     ID3DXMeshImpl_ConvertPointRepsToAdjacency,
 387     ID3DXMeshImpl_ConvertAdjacencyToPointReps,
 388     ID3DXMeshImpl_GenerateAdjacency,
 389     ID3DXMeshImpl_UpdateSemantics,
 390     /*** ID3DXMesh ***/
 391     ID3DXMeshImpl_LockAttributeBuffer,
 392     ID3DXMeshImpl_UnlockAttributeBuffer,
 393     ID3DXMeshImpl_Optimize,
 394     ID3DXMeshImpl_OptimizeInplace,
 395     ID3DXMeshImpl_SetAttributeTable
 396 };
 397
 398 /*************************************************************************
 399  * D3DXBoxBoundProbe
 400  */
 401 BOOL WINAPI D3DXBoxBoundProbe(CONST D3DXVECTOR3 *pmin, CONST D3DXVECTOR3 *pmax, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
 402
 403 /* Algorithm taken from the article: An Efficient and Robust Ray-Box Intersection Algoritm
 404 Amy Williams             University of Utah
 405 Steve Barrus             University of Utah
 406 R. Keith Morley          University of Utah
 407 Peter Shirley            University of Utah
 408
 409 International Conference on Computer Graphics and Interactive Techniques  archive
 410 ACM SIGGRAPH 2005 Courses
 411 Los Angeles, California
 412
 413 This algorithm is free of patents or of copyrights, as confirmed by Peter Shirley himself.
 414
 415 Algorithm: Consider the box as the intersection of three slabs. Clip the ray
 416 against each slab, if there's anything left of the ray after we're
 417 done we've got an intersection of the ray with the box.
 418 */
 419
 420 {
 421     FLOAT div, tmin, tmax, tymin, tymax, tzmin, tzmax;
 422
 423     div = 1.0f / praydirection->x;
 424     if ( div >= 0.0f )
 425     {
 426         tmin = ( pmin->x - prayposition->x ) * div;
 427         tmax = ( pmax->x - prayposition->x ) * div;
 428     }
 429     else
 430     {
 431         tmin = ( pmax->x - prayposition->x ) * div;
 432         tmax = ( pmin->x - prayposition->x ) * div;
 433     }
 434
 435     if ( tmax < 0.0f ) return FALSE;
 436
 437     div = 1.0f / praydirection->y;
 438     if ( div >= 0.0f )
 439     {
 440         tymin = ( pmin->y - prayposition->y ) * div;
 441         tymax = ( pmax->y - prayposition->y ) * div;
 442     }
 443     else
 444     {
 445         tymin = ( pmax->y - prayposition->y ) * div;
 446         tymax = ( pmin->y - prayposition->y ) * div;
 447     }
 448
 449     if ( ( tymax < 0.0f ) || ( tmin > tymax ) || ( tymin > tmax ) ) return FALSE;
 450
 451     if ( tymin > tmin ) tmin = tymin;
 452     if ( tymax < tmax ) tmax = tymax;
 453
 454     div = 1.0f / praydirection->z;
 455     if ( div >= 0.0f )
 456     {
 457         tzmin = ( pmin->z - prayposition->z ) * div;
 458         tzmax = ( pmax->z - prayposition->z ) * div;
 459     }
 460     else
 461     {
 462         tzmin = ( pmax->z - prayposition->z ) * div;
 463         tzmax = ( pmin->z - prayposition->z ) * div;
 464     }
 465
 466     if ( (tzmax < 0.0f ) || ( tmin > tzmax ) || ( tzmin > tmax ) ) return FALSE;
 467
 468     return TRUE;
 469 }
 470
 471 /*************************************************************************
 472  * D3DXComputeBoundingBox
 473  */
 474 HRESULT WINAPI D3DXComputeBoundingBox(CONST D3DXVECTOR3 *pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pmin, D3DXVECTOR3 *pmax)
 475 {
 476     D3DXVECTOR3 vec;
 477     unsigned int i;
 478
 479     if( !pfirstposition || !pmin || !pmax ) return D3DERR_INVALIDCALL;
 480
 481     *pmin = *pfirstposition;
 482     *pmax = *pmin;
 483
 484     for(i=0; i<numvertices; i++)
 485     {
 486         vec = *( (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i) );
 487
 488         if ( vec.x < pmin->x ) pmin->x = vec.x;
 489         if ( vec.x > pmax->x ) pmax->x = vec.x;
 490
 491         if ( vec.y < pmin->y ) pmin->y = vec.y;
 492         if ( vec.y > pmax->y ) pmax->y = vec.y;
 493
 494         if ( vec.z < pmin->z ) pmin->z = vec.z;
 495         if ( vec.z > pmax->z ) pmax->z = vec.z;
 496     }
 497
 498     return D3D_OK;
 499 }
 500
 501 /*************************************************************************
 502  * D3DXComputeBoundingSphere
 503  */
 504 HRESULT WINAPI D3DXComputeBoundingSphere(CONST D3DXVECTOR3* pfirstposition, DWORD numvertices, DWORD dwstride, D3DXVECTOR3 *pcenter, FLOAT *pradius)
 505 {
 506     D3DXVECTOR3 temp, temp1;
 507     FLOAT d;
 508     unsigned int i;
 509
 510     if( !pfirstposition || !pcenter || !pradius ) return D3DERR_INVALIDCALL;
 511
 512     temp.x = 0.0f;
 513     temp.y = 0.0f;
 514     temp.z = 0.0f;
 515     temp1 = temp;
 516     *pradius = 0.0f;
 517
 518     for(i=0; i<numvertices; i++)
 519     {
 520         D3DXVec3Add(&temp1, &temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i));
 521         temp = temp1;
 522     }
 523
 524     D3DXVec3Scale(pcenter, &temp, 1.0f/((FLOAT)numvertices));
 525
 526     for(i=0; i<numvertices; i++)
 527     {
 528         d = D3DXVec3Length(D3DXVec3Subtract(&temp, (const D3DXVECTOR3*)((const char*)pfirstposition + dwstride * i), pcenter));
 529         if ( d > *pradius ) *pradius = d;
 530     }
 531     return D3D_OK;
 532 }
 533
 534 static const UINT d3dx_decltype_size[D3DDECLTYPE_UNUSED] =
 535 {
 536    /* D3DDECLTYPE_FLOAT1    */ 1 * 4,
 537    /* D3DDECLTYPE_FLOAT2    */ 2 * 4,
 538    /* D3DDECLTYPE_FLOAT3    */ 3 * 4,
 539    /* D3DDECLTYPE_FLOAT4    */ 4 * 4,
 540    /* D3DDECLTYPE_D3DCOLOR  */ 4 * 1,
 541    /* D3DDECLTYPE_UBYTE4    */ 4 * 1,
 542    /* D3DDECLTYPE_SHORT2    */ 2 * 2,
 543    /* D3DDECLTYPE_SHORT4    */ 4 * 2,
 544    /* D3DDECLTYPE_UBYTE4N   */ 4 * 1,
 545    /* D3DDECLTYPE_SHORT2N   */ 2 * 2,
 546    /* D3DDECLTYPE_SHORT4N   */ 4 * 2,
 547    /* D3DDECLTYPE_USHORT2N  */ 2 * 2,
 548    /* D3DDECLTYPE_USHORT4N  */ 4 * 2,
 549    /* D3DDECLTYPE_UDEC3     */ 4, /* 3 * 10 bits + 2 padding */
 550    /* D3DDECLTYPE_DEC3N     */ 4,
 551    /* D3DDECLTYPE_FLOAT16_2 */ 2 * 2,
 552    /* D3DDECLTYPE_FLOAT16_4 */ 4 * 2,
 553 };
 554
 555 static void append_decl_element(D3DVERTEXELEMENT9 *declaration, UINT *idx, UINT *offset,
 556         D3DDECLTYPE type, D3DDECLUSAGE usage, UINT usage_idx)
 557 {
 558     declaration[*idx].Stream = 0;
 559     declaration[*idx].Offset = *offset;
 560     declaration[*idx].Type = type;
 561     declaration[*idx].Method = D3DDECLMETHOD_DEFAULT;
 562     declaration[*idx].Usage = usage;
 563     declaration[*idx].UsageIndex = usage_idx;
 564
 565     *offset += d3dx_decltype_size[type];
 566     ++(*idx);
 567 }
 568
 569 /*************************************************************************
 570  * D3DXDeclaratorFromFVF
 571  */
 572 HRESULT WINAPI D3DXDeclaratorFromFVF(DWORD fvf, D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE])
 573 {
 574     static const D3DVERTEXELEMENT9 end_element = D3DDECL_END();
 575     DWORD tex_count = (fvf & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
 576     unsigned int offset = 0;
 577     unsigned int idx = 0;
 578     unsigned int i;
 579
 580     TRACE("fvf %#x, declaration %p.\n", fvf, declaration);
 581
 582     if (fvf & (D3DFVF_RESERVED0 | D3DFVF_RESERVED2)) return D3DERR_INVALIDCALL;
 583
 584     if (fvf & D3DFVF_POSITION_MASK)
 585     {
 586         BOOL has_blend = (fvf & D3DFVF_XYZB5) >= D3DFVF_XYZB1;
 587         DWORD blend_count = 1 + (((fvf & D3DFVF_XYZB5) - D3DFVF_XYZB1) >> 1);
 588         BOOL has_blend_idx = (fvf & D3DFVF_LASTBETA_D3DCOLOR) || (fvf & D3DFVF_LASTBETA_UBYTE4);
 589
 590         if (has_blend_idx) --blend_count;
 591
 592         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZW
 593                 || (has_blend && blend_count > 4))
 594             return D3DERR_INVALIDCALL;
 595
 596         if ((fvf & D3DFVF_POSITION_MASK) == D3DFVF_XYZRHW)
 597             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_POSITIONT, 0);
 598         else
 599             append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_POSITION, 0);
 600
 601         if (has_blend)
 602         {
 603             switch (blend_count)
 604             {
 605                  case 0:
 606                     break;
 607                  case 1:
 608                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_BLENDWEIGHT, 0);
 609                     break;
 610                  case 2:
 611                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_BLENDWEIGHT, 0);
 612                     break;
 613                  case 3:
 614                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_BLENDWEIGHT, 0);
 615                     break;
 616                  case 4:
 617                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_BLENDWEIGHT, 0);
 618                     break;
 619                  default:
 620                      ERR("Invalid blend count %u.\n", blend_count);
 621                      break;
 622             }
 623
 624             if (has_blend_idx)
 625             {
 626                 if (fvf & D3DFVF_LASTBETA_UBYTE4)
 627                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_UBYTE4, D3DDECLUSAGE_BLENDINDICES, 0);
 628                 else if (fvf & D3DFVF_LASTBETA_D3DCOLOR)
 629                     append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_BLENDINDICES, 0);
 630             }
 631         }
 632     }
 633
 634     if (fvf & D3DFVF_NORMAL)
 635         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_NORMAL, 0);
 636     if (fvf & D3DFVF_PSIZE)
 637         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_PSIZE, 0);
 638     if (fvf & D3DFVF_DIFFUSE)
 639         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 0);
 640     if (fvf & D3DFVF_SPECULAR)
 641         append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_D3DCOLOR, D3DDECLUSAGE_COLOR, 1);
 642
 643     for (i = 0; i < tex_count; ++i)
 644     {
 645         switch ((fvf >> (16 + 2 * i)) & 0x03)
 646         {
 647             case D3DFVF_TEXTUREFORMAT1:
 648                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT1, D3DDECLUSAGE_TEXCOORD, i);
 649                 break;
 650             case D3DFVF_TEXTUREFORMAT2:
 651                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT2, D3DDECLUSAGE_TEXCOORD, i);
 652                 break;
 653             case D3DFVF_TEXTUREFORMAT3:
 654                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT3, D3DDECLUSAGE_TEXCOORD, i);
 655                 break;
 656             case D3DFVF_TEXTUREFORMAT4:
 657                 append_decl_element(declaration, &idx, &offset, D3DDECLTYPE_FLOAT4, D3DDECLUSAGE_TEXCOORD, i);
 658                 break;
 659         }
 660     }
 661
 662     declaration[idx] = end_element;
 663
 664     return D3D_OK;
 665 }
 666
 667 /*************************************************************************
 668  * D3DXFVFFromDeclarator
 669  */
 670 HRESULT WINAPI D3DXFVFFromDeclarator(const D3DVERTEXELEMENT9 *declaration, DWORD *fvf)
 671 {
 672     unsigned int i = 0, texture, offset;
 673
 674     TRACE("(%p, %p)\n", declaration, fvf);
 675
 676     *fvf = 0;
 677     if (declaration[0].Type == D3DDECLTYPE_FLOAT3 && declaration[0].Usage == D3DDECLUSAGE_POSITION)
 678     {
 679         if ((declaration[1].Type == D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
 680              declaration[1].UsageIndex == 0) &&
 681             (declaration[2].Type == D3DDECLTYPE_FLOAT1 && declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES &&
 682              declaration[2].UsageIndex == 0))
 683         {
 684             return D3DERR_INVALIDCALL;
 685         }
 686         else if ((declaration[1].Type == D3DDECLTYPE_UBYTE4 || declaration[1].Type == D3DDECLTYPE_D3DCOLOR) &&
 687                  declaration[1].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[1].UsageIndex == 0)
 688         {
 689             if (declaration[1].Type == D3DDECLTYPE_UBYTE4)
 690             {
 691                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_UBYTE4;
 692             }
 693             else
 694             {
 695                 *fvf |= D3DFVF_XYZB1 | D3DFVF_LASTBETA_D3DCOLOR;
 696             }
 697             i = 2;
 698         }
 699         else if (declaration[1].Type <= D3DDECLTYPE_FLOAT4 && declaration[1].Usage == D3DDECLUSAGE_BLENDWEIGHT &&
 700                  declaration[1].UsageIndex == 0)
 701         {
 702             if ((declaration[2].Type == D3DDECLTYPE_UBYTE4 || declaration[2].Type == D3DDECLTYPE_D3DCOLOR) &&
 703                 declaration[2].Usage == D3DDECLUSAGE_BLENDINDICES && declaration[2].UsageIndex == 0)
 704             {
 705                 if (declaration[2].Type == D3DDECLTYPE_UBYTE4)
 706                 {
 707                     *fvf |= D3DFVF_LASTBETA_UBYTE4;
 708                 }
 709                 else
 710                 {
 711                     *fvf |= D3DFVF_LASTBETA_D3DCOLOR;
 712                 }
 713                 switch (declaration[1].Type)
 714                 {
 715                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB2; break;
 716                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB3; break;
 717                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB4; break;
 718                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB5; break;
 719                 }
 720                 i = 3;
 721             }
 722             else
 723             {
 724                 switch (declaration[1].Type)
 725                 {
 726                     case D3DDECLTYPE_FLOAT1: *fvf |= D3DFVF_XYZB1; break;
 727                     case D3DDECLTYPE_FLOAT2: *fvf |= D3DFVF_XYZB2; break;
 728                     case D3DDECLTYPE_FLOAT3: *fvf |= D3DFVF_XYZB3; break;
 729                     case D3DDECLTYPE_FLOAT4: *fvf |= D3DFVF_XYZB4; break;
 730                 }
 731                 i = 2;
 732             }
 733         }
 734         else
 735         {
 736             *fvf |= D3DFVF_XYZ;
 737             i = 1;
 738         }
 739     }
 740     else if (declaration[0].Type == D3DDECLTYPE_FLOAT4 && declaration[0].Usage == D3DDECLUSAGE_POSITIONT &&
 741              declaration[0].UsageIndex == 0)
 742     {
 743         *fvf |= D3DFVF_XYZRHW;
 744         i = 1;
 745     }
 746
 747     if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_NORMAL)
 748     {
 749         *fvf |= D3DFVF_NORMAL;
 750         i++;
 751     }
 752     if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_PSIZE &&
 753         declaration[i].UsageIndex == 0)
 754     {
 755         *fvf |= D3DFVF_PSIZE;
 756         i++;
 757     }
 758     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
 759         declaration[i].UsageIndex == 0)
 760     {
 761         *fvf |= D3DFVF_DIFFUSE;
 762         i++;
 763     }
 764     if (declaration[i].Type == D3DDECLTYPE_D3DCOLOR && declaration[i].Usage == D3DDECLUSAGE_COLOR &&
 765         declaration[i].UsageIndex == 1)
 766     {
 767         *fvf |= D3DFVF_SPECULAR;
 768         i++;
 769     }
 770
 771     for (texture = 0; texture < D3DDP_MAXTEXCOORD; i++, texture++)
 772     {
 773         if (declaration[i].Stream == 0xFF)
 774         {
 775             break;
 776         }
 777         else if (declaration[i].Type == D3DDECLTYPE_FLOAT1 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
 778                  declaration[i].UsageIndex == texture)
 779         {
 780             *fvf |= D3DFVF_TEXCOORDSIZE1(declaration[i].UsageIndex);
 781         }
 782         else if (declaration[i].Type == D3DDECLTYPE_FLOAT2 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
 783                  declaration[i].UsageIndex == texture)
 784         {
 785             *fvf |= D3DFVF_TEXCOORDSIZE2(declaration[i].UsageIndex);
 786         }
 787         else if (declaration[i].Type == D3DDECLTYPE_FLOAT3 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
 788                  declaration[i].UsageIndex == texture)
 789         {
 790             *fvf |= D3DFVF_TEXCOORDSIZE3(declaration[i].UsageIndex);
 791         }
 792         else if (declaration[i].Type == D3DDECLTYPE_FLOAT4 && declaration[i].Usage == D3DDECLUSAGE_TEXCOORD &&
 793                  declaration[i].UsageIndex == texture)
 794         {
 795             *fvf |= D3DFVF_TEXCOORDSIZE4(declaration[i].UsageIndex);
 796         }
 797         else
 798         {
 799             return D3DERR_INVALIDCALL;
 800         }
 801     }
 802
 803     *fvf |= (texture << D3DFVF_TEXCOUNT_SHIFT);
 804
 805     for (offset = 0, i = 0; declaration[i].Stream != 0xFF;
 806          offset += d3dx_decltype_size[declaration[i].Type], i++)
 807     {
 808         if (declaration[i].Offset != offset)
 809         {
 810             return D3DERR_INVALIDCALL;
 811         }
 812     }
 813
 814     return D3D_OK;
 815 }
 816
 817 /*************************************************************************
 818  * D3DXGetFVFVertexSize
 819  */
 820 static UINT Get_TexCoord_Size_From_FVF(DWORD FVF, int tex_num)
 821 {
 822     return (((((FVF) >> (16 + (2 * (tex_num)))) + 1) & 0x03) + 1);
 823 }
 824
 825 UINT WINAPI D3DXGetFVFVertexSize(DWORD FVF)
 826 {
 827     DWORD size = 0;
 828     UINT i;
 829     UINT numTextures = (FVF & D3DFVF_TEXCOUNT_MASK) >> D3DFVF_TEXCOUNT_SHIFT;
 830
 831     if (FVF & D3DFVF_NORMAL) size += sizeof(D3DXVECTOR3);
 832     if (FVF & D3DFVF_DIFFUSE) size += sizeof(DWORD);
 833     if (FVF & D3DFVF_SPECULAR) size += sizeof(DWORD);
 834     if (FVF & D3DFVF_PSIZE) size += sizeof(DWORD);
 835
 836     switch (FVF & D3DFVF_POSITION_MASK)
 837     {
 838         case D3DFVF_XYZ:    size += sizeof(D3DXVECTOR3); break;
 839         case D3DFVF_XYZRHW: size += 4 * sizeof(FLOAT); break;
 840         case D3DFVF_XYZB1:  size += 4 * sizeof(FLOAT); break;
 841         case D3DFVF_XYZB2:  size += 5 * sizeof(FLOAT); break;
 842         case D3DFVF_XYZB3:  size += 6 * sizeof(FLOAT); break;
 843         case D3DFVF_XYZB4:  size += 7 * sizeof(FLOAT); break;
 844         case D3DFVF_XYZB5:  size += 8 * sizeof(FLOAT); break;
 845         case D3DFVF_XYZW:   size += 4 * sizeof(FLOAT); break;
 846     }
 847
 848     for (i = 0; i < numTextures; i++)
 849     {
 850         size += Get_TexCoord_Size_From_FVF(FVF, i) * sizeof(FLOAT);
 851     }
 852
 853     return size;
 854 }
 855
 856 /*************************************************************************
 857  * D3DXGetDeclVertexSize
 858  */
 859 UINT WINAPI D3DXGetDeclVertexSize(const D3DVERTEXELEMENT9 *decl, DWORD stream_idx)
 860 {
 861     const D3DVERTEXELEMENT9 *element;
 862     UINT size = 0;
 863
 864     TRACE("decl %p, stream_idx %u\n", decl, stream_idx);
 865
 866     if (!decl) return 0;
 867
 868     for (element = decl; element->Stream != 0xff; ++element)
 869     {
 870         UINT type_size;
 871
 872         if (element->Stream != stream_idx) continue;
 873
 874         if (element->Type >= sizeof(d3dx_decltype_size) / sizeof(*d3dx_decltype_size))
 875         {
 876             FIXME("Unhandled element type %#x, size will be incorrect.\n", element->Type);
 877             continue;
 878         }
 879
 880         type_size = d3dx_decltype_size[element->Type];
 881         if (element->Offset + type_size > size) size = element->Offset + type_size;
 882     }
 883
 884     return size;
 885 }
 886
 887 /*************************************************************************
 888  * D3DXGetDeclLength
 889  */
 890 UINT WINAPI D3DXGetDeclLength(const D3DVERTEXELEMENT9 *decl)
 891 {
 892     const D3DVERTEXELEMENT9 *element;
 893
 894     TRACE("decl %p\n", decl);
 895
 896     /* null decl results in exception on Windows XP */
 897
 898     for (element = decl; element->Stream != 0xff; ++element);
 899
 900     return element - decl;
 901 }
 902
 903 /*************************************************************************
 904  * D3DXIntersectTri
 905  */
 906 BOOL WINAPI D3DXIntersectTri(CONST D3DXVECTOR3 *p0, CONST D3DXVECTOR3 *p1, CONST D3DXVECTOR3 *p2, CONST D3DXVECTOR3 *praypos, CONST D3DXVECTOR3 *praydir, FLOAT *pu, FLOAT *pv, FLOAT *pdist)
 907 {
 908     D3DXMATRIX m;
 909     D3DXVECTOR4 vec;
 910
 911     m.u.m[0][0] = p1->x - p0->x;
 912     m.u.m[1][0] = p2->x - p0->x;
 913     m.u.m[2][0] = -praydir->x;
 914     m.u.m[3][0] = 0.0f;
 915     m.u.m[0][1] = p1->y - p0->z;
 916     m.u.m[1][1] = p2->y - p0->z;
 917     m.u.m[2][1] = -praydir->y;
 918     m.u.m[3][1] = 0.0f;
 919     m.u.m[0][2] = p1->z - p0->z;
 920     m.u.m[1][2] = p2->z - p0->z;
 921     m.u.m[2][2] = -praydir->z;
 922     m.u.m[3][2] = 0.0f;
 923     m.u.m[0][3] = 0.0f;
 924     m.u.m[1][3] = 0.0f;
 925     m.u.m[2][3] = 0.0f;
 926     m.u.m[3][3] = 1.0f;
 927
 928     vec.x = praypos->x - p0->x;
 929     vec.y = praypos->y - p0->y;
 930     vec.z = praypos->z - p0->z;
 931     vec.w = 0.0f;
 932
 933     if ( D3DXMatrixInverse(&m, NULL, &m) )
 934     {
 935         D3DXVec4Transform(&vec, &vec, &m);
 936         if ( (vec.x >= 0.0f) && (vec.y >= 0.0f) && (vec.x + vec.y <= 1.0f) && (vec.z >= 0.0f) )
 937         {
 938             *pu = vec.x;
 939             *pv = vec.y;
 940             *pdist = fabs( vec.z );
 941             return TRUE;
 942         }
 943     }
 944
 945     return FALSE;
 946 }
 947
 948 /*************************************************************************
 949  * D3DXSphereBoundProbe
 950  */
 951 BOOL WINAPI D3DXSphereBoundProbe(CONST D3DXVECTOR3 *pcenter, FLOAT radius, CONST D3DXVECTOR3 *prayposition, CONST D3DXVECTOR3 *praydirection)
 952 {
 953     D3DXVECTOR3 difference;
 954     FLOAT a, b, c, d;
 955
 956     a = D3DXVec3LengthSq(praydirection);
 957     if (!D3DXVec3Subtract(&difference, prayposition, pcenter)) return FALSE;
 958     b = D3DXVec3Dot(&difference, praydirection);
 959     c = D3DXVec3LengthSq(&difference) - radius * radius;
 960     d = b * b - a * c;
 961
 962     if ( ( d <= 0.0f ) || ( sqrt(d) <= b ) ) return FALSE;
 963     return TRUE;
 964 }
 965
 966 /*************************************************************************
 967  * D3DXCreateMesh
 968  */
 969 HRESULT WINAPI D3DXCreateMesh(DWORD numfaces, DWORD numvertices, DWORD options, CONST D3DVERTEXELEMENT9 *declaration,
 970                               LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
 971 {
 972     HRESULT hr;
 973     DWORD fvf;
 974     IDirect3DVertexDeclaration9 *vertex_declaration;
 975     IDirect3DVertexBuffer9 *vertex_buffer;
 976     IDirect3DIndexBuffer9 *index_buffer;
 977     ID3DXMeshImpl *object;
 978
 979     TRACE("(%d, %d, %d, %p, %p, %p)\n", numfaces, numvertices, options, declaration, device, mesh);
 980
 981     if (numfaces == 0 || numvertices == 0 || declaration == NULL || device == NULL || mesh == NULL)
 982     {
 983         return D3DERR_INVALIDCALL;
 984     }
 985
 986     hr = D3DXFVFFromDeclarator(declaration, &fvf);
 987     if (hr != D3D_OK)
 988     {
 989         fvf = 0;
 990     }
 991
 992     /* Create vertex declaration */
 993     hr = IDirect3DDevice9_CreateVertexDeclaration(device,
 994                                                   declaration,
 995                                                   &vertex_declaration);
 996     if (FAILED(hr))
 997     {
 998         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexDeclaration.\n",hr);
 999         return hr;
1000     }
1001
1002     /* Create vertex buffer */
1003     hr = IDirect3DDevice9_CreateVertexBuffer(device,
1004                                              numvertices * D3DXGetDeclVertexSize(declaration, declaration[0].Stream),
1005                                              0,
1006                                              fvf,
1007                                              D3DPOOL_MANAGED,
1008                                              &vertex_buffer,
1009                                              NULL);
1010     if (FAILED(hr))
1011     {
1012         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
1013         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1014         return hr;
1015     }
1016
1017     /* Create index buffer */
1018     hr = IDirect3DDevice9_CreateIndexBuffer(device,
1019                                             numfaces * 6, /* 3 vertices per triangle, 2 triangles per face */
1020                                             0,
1021                                             D3DFMT_INDEX16,
1022                                             D3DPOOL_MANAGED,
1023                                             &index_buffer,
1024                                             NULL);
1025     if (FAILED(hr))
1026     {
1027         WARN("Unexpected return value %x from IDirect3DDevice9_CreateVertexBuffer.\n",hr);
1028         IDirect3DVertexBuffer9_Release(vertex_buffer);
1029         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1030         return hr;
1031     }
1032
1033     object = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(ID3DXMeshImpl));
1034     if (object == NULL)
1035     {
1036         IDirect3DIndexBuffer9_Release(index_buffer);
1037         IDirect3DVertexBuffer9_Release(vertex_buffer);
1038         IDirect3DVertexDeclaration9_Release(vertex_declaration);
1039         *mesh = NULL;
1040         return E_OUTOFMEMORY;
1041     }
1042     object->ID3DXMesh_iface.lpVtbl = &D3DXMesh_Vtbl;
1043     object->ref = 1;
1044
1045     object->numfaces = numfaces;
1046     object->numvertices = numvertices;
1047     object->options = options;
1048     object->fvf = fvf;
1049     object->device = device;
1050     IDirect3DDevice9_AddRef(device);
1051
1052     object->vertex_declaration = vertex_declaration;
1053     object->vertex_buffer = vertex_buffer;
1054     object->index_buffer = index_buffer;
1055
1056     *mesh = &object->ID3DXMesh_iface;
1057
1058     return D3D_OK;
1059 }
1060
1061 /*************************************************************************
1062  * D3DXCreateMeshFVF
1063  */
1064 HRESULT WINAPI D3DXCreateMeshFVF(DWORD numfaces, DWORD numvertices, DWORD options, DWORD fvf,
1065                                  LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh)
1066 {
1067     HRESULT hr;
1068     D3DVERTEXELEMENT9 declaration[MAX_FVF_DECL_SIZE];
1069
1070     TRACE("(%u, %u, %u, %u, %p, %p)\n", numfaces, numvertices, options, fvf, device, mesh);
1071
1072     hr = D3DXDeclaratorFromFVF(fvf, declaration);
1073     if (FAILED(hr)) return hr;
1074
1075     return D3DXCreateMesh(numfaces, numvertices, options, declaration, device, mesh);
1076 }
1077
1078 HRESULT WINAPI D3DXCreateBox(LPDIRECT3DDEVICE9 device, FLOAT width, FLOAT height,
1079                              FLOAT depth, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
1080 {
1081     FIXME("(%p, %f, %f, %f, %p, %p): stub\n", device, width, height, depth, mesh, adjacency);
1082
1083     return E_NOTIMPL;
1084 }
1085
1086 struct vertex
1087 {
1088     D3DXVECTOR3 position;
1089     D3DXVECTOR3 normal;
1090 };
1091
1092 typedef WORD face[3];
1093
1094 struct sincos_table
1095 {
1096     float *sin;
1097     float *cos;
1098 };
1099
1100 static void free_sincos_table(struct sincos_table *sincos_table)
1101 {
1102     HeapFree(GetProcessHeap(), 0, sincos_table->cos);
1103     HeapFree(GetProcessHeap(), 0, sincos_table->sin);
1104 }
1105
1106 /* pre compute sine and cosine tables; caller must free */
1107 static BOOL compute_sincos_table(struct sincos_table *sincos_table, float angle_start, float angle_step, int n)
1108 {
1109     float angle;
1110     int i;
1111
1112     sincos_table->sin = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->sin));
1113     if (!sincos_table->sin)
1114     {
1115         return FALSE;
1116     }
1117     sincos_table->cos = HeapAlloc(GetProcessHeap(), 0, n * sizeof(*sincos_table->cos));
1118     if (!sincos_table->cos)
1119     {
1120         HeapFree(GetProcessHeap(), 0, sincos_table->sin);
1121         return FALSE;
1122     }
1123
1124     angle = angle_start;
1125     for (i = 0; i < n; i++)
1126     {
1127         sincos_table->sin[i] = sin(angle);
1128         sincos_table->cos[i] = cos(angle);
1129         angle += angle_step;
1130     }
1131
1132     return TRUE;
1133 }
1134
1135 static WORD vertex_index(UINT slices, int slice, int stack)
1136 {
1137     return stack*slices+slice+1;
1138 }
1139
1140 HRESULT WINAPI D3DXCreateSphere(LPDIRECT3DDEVICE9 device, FLOAT radius, UINT slices,
1141                                 UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
1142 {
1143     DWORD number_of_vertices, number_of_faces;
1144     HRESULT hr;
1145     ID3DXMesh *sphere;
1146     struct vertex *vertices;
1147     face *faces;
1148     float phi_step, phi_start;
1149     struct sincos_table phi;
1150     float theta_step, theta, sin_theta, cos_theta;
1151     DWORD vertex, face;
1152     int slice, stack;
1153
1154     TRACE("(%p, %f, %u, %u, %p, %p)\n", device, radius, slices, stacks, mesh, adjacency);
1155
1156     if (!device || radius < 0.0f || slices < 2 || stacks < 2 || !mesh)
1157     {
1158         return D3DERR_INVALIDCALL;
1159     }
1160
1161     if (adjacency)
1162     {
1163         FIXME("Case of adjacency != NULL not implemented.\n");
1164         return E_NOTIMPL;
1165     }
1166
1167     number_of_vertices = 2 + slices * (stacks-1);
1168     number_of_faces = 2 * slices + (stacks - 2) * (2 * slices);
1169
1170     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
1171                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &sphere);
1172     if (FAILED(hr))
1173     {
1174         return hr;
1175     }
1176
1177     hr = sphere->lpVtbl->LockVertexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&vertices);
1178     if (FAILED(hr))
1179     {
1180         sphere->lpVtbl->Release(sphere);
1181         return hr;
1182     }
1183
1184     hr = sphere->lpVtbl->LockIndexBuffer(sphere, D3DLOCK_DISCARD, (LPVOID *)&faces);
1185     if (FAILED(hr))
1186     {
1187         sphere->lpVtbl->UnlockVertexBuffer(sphere);
1188         sphere->lpVtbl->Release(sphere);
1189         return hr;
1190     }
1191
1192     /* phi = angle on xz plane wrt z axis */
1193     phi_step = -2 * M_PI / slices;
1194     phi_start = M_PI / 2;
1195
1196     if (!compute_sincos_table(&phi, phi_start, phi_step, slices))
1197     {
1198         sphere->lpVtbl->UnlockIndexBuffer(sphere);
1199         sphere->lpVtbl->UnlockVertexBuffer(sphere);
1200         sphere->lpVtbl->Release(sphere);
1201         return E_OUTOFMEMORY;
1202     }
1203
1204     /* theta = angle on xy plane wrt x axis */
1205     theta_step = M_PI / stacks;
1206     theta = theta_step;
1207
1208     vertex = 0;
1209     face = 0;
1210     stack = 0;
1211
1212     vertices[vertex].normal.x = 0.0f;
1213     vertices[vertex].normal.y = 0.0f;
1214     vertices[vertex].normal.z = 1.0f;
1215     vertices[vertex].position.x = 0.0f;
1216     vertices[vertex].position.y = 0.0f;
1217     vertices[vertex].position.z = radius;
1218     vertex++;
1219
1220     for (stack = 0; stack < stacks - 1; stack++)
1221     {
1222         sin_theta = sin(theta);
1223         cos_theta = cos(theta);
1224
1225         for (slice = 0; slice < slices; slice++)
1226         {
1227             vertices[vertex].normal.x = sin_theta * phi.cos[slice];
1228             vertices[vertex].normal.y = sin_theta * phi.sin[slice];
1229             vertices[vertex].normal.z = cos_theta;
1230             vertices[vertex].position.x = radius * sin_theta * phi.cos[slice];
1231             vertices[vertex].position.y = radius * sin_theta * phi.sin[slice];
1232             vertices[vertex].position.z = radius * cos_theta;
1233             vertex++;
1234
1235             if (slice > 0)
1236             {
1237                 if (stack == 0)
1238                 {
1239                     /* top stack is triangle fan */
1240                     faces[face][0] = 0;
1241                     faces[face][1] = slice + 1;
1242                     faces[face][2] = slice;
1243                     face++;
1244                 }
1245                 else
1246                 {
1247                     /* stacks in between top and bottom are quad strips */
1248                     faces[face][0] = vertex_index(slices, slice-1, stack-1);
1249                     faces[face][1] = vertex_index(slices, slice, stack-1);
1250                     faces[face][2] = vertex_index(slices, slice-1, stack);
1251                     face++;
1252
1253                     faces[face][0] = vertex_index(slices, slice, stack-1);
1254                     faces[face][1] = vertex_index(slices, slice, stack);
1255                     faces[face][2] = vertex_index(slices, slice-1, stack);
1256                     face++;
1257                 }
1258             }
1259         }
1260
1261         theta += theta_step;
1262
1263         if (stack == 0)
1264         {
1265             faces[face][0] = 0;
1266             faces[face][1] = 1;
1267             faces[face][2] = slice;
1268             face++;
1269         }
1270         else
1271         {
1272             faces[face][0] = vertex_index(slices, slice-1, stack-1);
1273             faces[face][1] = vertex_index(slices, 0, stack-1);
1274             faces[face][2] = vertex_index(slices, slice-1, stack);
1275             face++;
1276
1277             faces[face][0] = vertex_index(slices, 0, stack-1);
1278             faces[face][1] = vertex_index(slices, 0, stack);
1279             faces[face][2] = vertex_index(slices, slice-1, stack);
1280             face++;
1281         }
1282     }
1283
1284     vertices[vertex].position.x = 0.0f;
1285     vertices[vertex].position.y = 0.0f;
1286     vertices[vertex].position.z = -radius;
1287     vertices[vertex].normal.x = 0.0f;
1288     vertices[vertex].normal.y = 0.0f;
1289     vertices[vertex].normal.z = -1.0f;
1290
1291     /* bottom stack is triangle fan */
1292     for (slice = 1; slice < slices; slice++)
1293     {
1294         faces[face][0] = vertex_index(slices, slice-1, stack-1);
1295         faces[face][1] = vertex_index(slices, slice, stack-1);
1296         faces[face][2] = vertex;
1297         face++;
1298     }
1299
1300     faces[face][0] = vertex_index(slices, slice-1, stack-1);
1301     faces[face][1] = vertex_index(slices, 0, stack-1);
1302     faces[face][2] = vertex;
1303
1304     free_sincos_table(&phi);
1305     sphere->lpVtbl->UnlockIndexBuffer(sphere);
1306     sphere->lpVtbl->UnlockVertexBuffer(sphere);
1307     *mesh = sphere;
1308
1309     return D3D_OK;
1310 }
1311
1312 HRESULT WINAPI D3DXCreateCylinder(LPDIRECT3DDEVICE9 device, FLOAT radius1, FLOAT radius2, FLOAT length, UINT slices,
1313                                   UINT stacks, LPD3DXMESH* mesh, LPD3DXBUFFER* adjacency)
1314 {
1315     DWORD number_of_vertices, number_of_faces;
1316     HRESULT hr;
1317     ID3DXMesh *cylinder;
1318     struct vertex *vertices;
1319     face *faces;
1320     float theta_step, theta_start;
1321     struct sincos_table theta;
1322     float delta_radius, radius, radius_step;
1323     float z, z_step, z_normal;
1324     DWORD vertex, face;
1325     int slice, stack;
1326
1327     TRACE("(%p, %f, %f, %f, %u, %u, %p, %p)\n", device, radius1, radius2, length, slices, stacks, mesh, adjacency);
1328
1329     if (device == NULL || radius1 < 0.0f || radius2 < 0.0f || length < 0.0f || slices < 2 || stacks < 1 || mesh == NULL)
1330     {
1331         return D3DERR_INVALIDCALL;
1332     }
1333
1334     if (adjacency)
1335     {
1336         FIXME("Case of adjacency != NULL not implemented.\n");
1337         return E_NOTIMPL;
1338     }
1339
1340     number_of_vertices = 2 + (slices * (3 + stacks));
1341     number_of_faces = 2 * slices + stacks * (2 * slices);
1342
1343     hr = D3DXCreateMeshFVF(number_of_faces, number_of_vertices, D3DXMESH_MANAGED,
1344                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &cylinder);
1345     if (FAILED(hr))
1346     {
1347         return hr;
1348     }
1349
1350     hr = cylinder->lpVtbl->LockVertexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&vertices);
1351     if (FAILED(hr))
1352     {
1353         cylinder->lpVtbl->Release(cylinder);
1354         return hr;
1355     }
1356
1357     hr = cylinder->lpVtbl->LockIndexBuffer(cylinder, D3DLOCK_DISCARD, (LPVOID *)&faces);
1358     if (FAILED(hr))
1359     {
1360         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
1361         cylinder->lpVtbl->Release(cylinder);
1362         return hr;
1363     }
1364
1365     /* theta = angle on xy plane wrt x axis */
1366     theta_step = -2 * M_PI / slices;
1367     theta_start = M_PI / 2;
1368
1369     if (!compute_sincos_table(&theta, theta_start, theta_step, slices))
1370     {
1371         cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
1372         cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
1373         cylinder->lpVtbl->Release(cylinder);
1374         return E_OUTOFMEMORY;
1375     }
1376
1377     vertex = 0;
1378     face = 0;
1379
1380     delta_radius = radius1 - radius2;
1381     radius = radius1;
1382     radius_step = delta_radius / stacks;
1383
1384     z = -length / 2;
1385     z_step = length / stacks;
1386     z_normal = delta_radius / length;
1387     if (isnan(z_normal))
1388     {
1389         z_normal = 0.0f;
1390     }
1391
1392     vertices[vertex].normal.x = 0.0f;
1393     vertices[vertex].normal.y = 0.0f;
1394     vertices[vertex].normal.z = -1.0f;
1395     vertices[vertex].position.x = 0.0f;
1396     vertices[vertex].position.y = 0.0f;
1397     vertices[vertex++].position.z = z;
1398
1399     for (slice = 0; slice < slices; slice++, vertex++)
1400     {
1401         vertices[vertex].normal.x = 0.0f;
1402         vertices[vertex].normal.y = 0.0f;
1403         vertices[vertex].normal.z = -1.0f;
1404         vertices[vertex].position.x = radius * theta.cos[slice];
1405         vertices[vertex].position.y = radius * theta.sin[slice];
1406         vertices[vertex].position.z = z;
1407
1408         if (slice > 0)
1409         {
1410             faces[face][0] = 0;
1411             faces[face][1] = slice;
1412             faces[face++][2] = slice + 1;
1413         }
1414     }
1415
1416     faces[face][0] = 0;
1417     faces[face][1] = slice;
1418     faces[face++][2] = 1;
1419
1420     for (stack = 1; stack <= stacks+1; stack++)
1421     {
1422         for (slice = 0; slice < slices; slice++, vertex++)
1423         {
1424             vertices[vertex].normal.x = theta.cos[slice];
1425             vertices[vertex].normal.y = theta.sin[slice];
1426             vertices[vertex].normal.z = z_normal;
1427             D3DXVec3Normalize(&vertices[vertex].normal, &vertices[vertex].normal);
1428             vertices[vertex].position.x = radius * theta.cos[slice];
1429             vertices[vertex].position.y = radius * theta.sin[slice];
1430             vertices[vertex].position.z = z;
1431
1432             if (stack > 1 && slice > 0)
1433             {
1434                 faces[face][0] = vertex_index(slices, slice-1, stack-1);
1435                 faces[face][1] = vertex_index(slices, slice-1, stack);
1436                 faces[face++][2] = vertex_index(slices, slice, stack-1);
1437
1438                 faces[face][0] = vertex_index(slices, slice, stack-1);
1439                 faces[face][1] = vertex_index(slices, slice-1, stack);
1440                 faces[face++][2] = vertex_index(slices, slice, stack);
1441             }
1442         }
1443
1444         if (stack > 1)
1445         {
1446             faces[face][0] = vertex_index(slices, slice-1, stack-1);
1447             faces[face][1] = vertex_index(slices, slice-1, stack);
1448             faces[face++][2] = vertex_index(slices, 0, stack-1);
1449
1450             faces[face][0] = vertex_index(slices, 0, stack-1);
1451             faces[face][1] = vertex_index(slices, slice-1, stack);
1452             faces[face++][2] = vertex_index(slices, 0, stack);
1453         }
1454
1455         if (stack < stacks + 1)
1456         {
1457             z += z_step;
1458             radius -= radius_step;
1459         }
1460     }
1461
1462     for (slice = 0; slice < slices; slice++, vertex++)
1463     {
1464         vertices[vertex].normal.x = 0.0f;
1465         vertices[vertex].normal.y = 0.0f;
1466         vertices[vertex].normal.z = 1.0f;
1467         vertices[vertex].position.x = radius * theta.cos[slice];
1468         vertices[vertex].position.y = radius * theta.sin[slice];
1469         vertices[vertex].position.z = z;
1470
1471         if (slice > 0)
1472         {
1473             faces[face][0] = vertex_index(slices, slice-1, stack);
1474             faces[face][1] = number_of_vertices - 1;
1475             faces[face++][2] = vertex_index(slices, slice, stack);
1476         }
1477     }
1478
1479     vertices[vertex].position.x = 0.0f;
1480     vertices[vertex].position.y = 0.0f;
1481     vertices[vertex].position.z = z;
1482     vertices[vertex].normal.x = 0.0f;
1483     vertices[vertex].normal.y = 0.0f;
1484     vertices[vertex].normal.z = 1.0f;
1485
1486     faces[face][0] = vertex_index(slices, slice-1, stack);
1487     faces[face][1] = number_of_vertices - 1;
1488     faces[face][2] = vertex_index(slices, 0, stack);
1489
1490     free_sincos_table(&theta);
1491     cylinder->lpVtbl->UnlockIndexBuffer(cylinder);
1492     cylinder->lpVtbl->UnlockVertexBuffer(cylinder);
1493     *mesh = cylinder;
1494
1495     return D3D_OK;
1496 }
1497
1498 HRESULT WINAPI D3DXCreateTeapot(LPDIRECT3DDEVICE9 device, LPD3DXMESH *mesh, LPD3DXBUFFER* adjacency)
1499 {
1500     FIXME("(%p, %p, %p): stub\n", device, mesh, adjacency);
1501
1502     return E_NOTIMPL;
1503 }
1504
1505 HRESULT WINAPI D3DXCreateTextA(LPDIRECT3DDEVICE9 device,
1506                                HDC hdc, LPCSTR text,
1507                                FLOAT deviation, FLOAT extrusion,
1508                                LPD3DXMESH *mesh, LPD3DXBUFFER *adjacency,
1509                                LPGLYPHMETRICSFLOAT glyphmetrics)
1510 {
1511     HRESULT hr;
1512     int len;
1513     LPWSTR textW;
1514
1515     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
1516           debugstr_a(text), deviation, extrusion, mesh, adjacency, glyphmetrics);
1517
1518     if (!text)
1519         return D3DERR_INVALIDCALL;
1520
1521     len = MultiByteToWideChar(CP_ACP, 0, text, -1, NULL, 0);
1522     textW = HeapAlloc(GetProcessHeap(), 0, len * sizeof(WCHAR));
1523     MultiByteToWideChar(CP_ACP, 0, text, -1, textW, len);
1524
1525     hr = D3DXCreateTextW(device, hdc, textW, deviation, extrusion,
1526                          mesh, adjacency, glyphmetrics);
1527     HeapFree(GetProcessHeap(), 0, textW);
1528
1529     return hr;
1530 }
1531
1532 enum pointtype {
1533     POINTTYPE_CURVE = 0,
1534     POINTTYPE_CORNER,
1535     POINTTYPE_CURVE_START,
1536     POINTTYPE_CURVE_END,
1537     POINTTYPE_CURVE_MIDDLE,
1538 };
1539
1540 struct point2d
1541 {
1542     D3DXVECTOR2 pos;
1543     enum pointtype corner;
1544 };
1545
1546 struct dynamic_array
1547 {
1548     int count, capacity;
1549     void *items;
1550 };
1551
1552 /* is a dynamic_array */
1553 struct outline
1554 {
1555     int count, capacity;
1556     struct point2d *items;
1557 };
1558
1559 /* is a dynamic_array */
1560 struct outline_array
1561 {
1562     int count, capacity;
1563     struct outline *items;
1564 };
1565
1566 struct face_array
1567 {
1568     int count;
1569     face *items;
1570 };
1571
1572 struct point2d_index
1573 {
1574     struct outline *outline;
1575     int vertex;
1576 };
1577
1578 struct point2d_index_array
1579 {
1580     int count;
1581     struct point2d_index *items;
1582 };
1583
1584 struct glyphinfo
1585 {
1586     struct outline_array outlines;
1587     struct face_array faces;
1588     struct point2d_index_array ordered_vertices;
1589     float offset_x;
1590 };
1591
1592 /* is an dynamic_array */
1593 struct word_array
1594 {
1595     int count, capacity;
1596     WORD *items;
1597 };
1598
1599 /* complex polygons are split into monotone polygons, which have
1600  * at most 2 intersections with the vertical sweep line */
1601 struct triangulation
1602 {
1603     struct word_array vertex_stack;
1604     BOOL last_on_top, merging;
1605 };
1606
1607 /* is an dynamic_array */
1608 struct triangulation_array
1609 {
1610     int count, capacity;
1611     struct triangulation *items;
1612
1613     struct glyphinfo *glyph;
1614 };
1615
1616 static BOOL reserve(struct dynamic_array *array, int count, int itemsize)
1617 {
1618     if (count > array->capacity) {
1619         void *new_buffer;
1620         int new_capacity;
1621         if (array->items && array->capacity) {
1622             new_capacity = max(array->capacity * 2, count);
1623             new_buffer = HeapReAlloc(GetProcessHeap(), 0, array->items, new_capacity * itemsize);
1624         } else {
1625             new_capacity = max(16, count);
1626             new_buffer = HeapAlloc(GetProcessHeap(), 0, new_capacity * itemsize);
1627         }
1628         if (!new_buffer)
1629             return FALSE;
1630         array->items = new_buffer;
1631         array->capacity = new_capacity;
1632     }
1633     return TRUE;
1634 }
1635
1636 static struct point2d *add_points(struct outline *array, int num)
1637 {
1638     struct point2d *item;
1639
1640     if (!reserve((struct dynamic_array *)array, array->count + num, sizeof(array->items[0])))
1641         return NULL;
1642
1643     item = &array->items[array->count];
1644     array->count += num;
1645     return item;
1646 }
1647
1648 static struct outline *add_outline(struct outline_array *array)
1649 {
1650     struct outline *item;
1651
1652     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
1653         return NULL;
1654
1655     item = &array->items[array->count++];
1656     ZeroMemory(item, sizeof(*item));
1657     return item;
1658 }
1659
1660 static inline face *add_face(struct face_array *array)
1661 {
1662     return &array->items[array->count++];
1663 }
1664
1665 static struct triangulation *add_triangulation(struct triangulation_array *array)
1666 {
1667     struct triangulation *item;
1668
1669     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
1670         return NULL;
1671
1672     item = &array->items[array->count++];
1673     ZeroMemory(item, sizeof(*item));
1674     return item;
1675 }
1676
1677 static HRESULT add_vertex_index(struct word_array *array, WORD vertex_index)
1678 {
1679     if (!reserve((struct dynamic_array *)array, array->count + 1, sizeof(array->items[0])))
1680         return E_OUTOFMEMORY;
1681
1682     array->items[array->count++] = vertex_index;
1683     return S_OK;
1684 }
1685
1686 /* assume fixed point numbers can be converted to float point in place */
1687 C_ASSERT(sizeof(FIXED) == sizeof(float));
1688 C_ASSERT(sizeof(POINTFX) == sizeof(D3DXVECTOR2));
1689
1690 static inline D3DXVECTOR2 *convert_fixed_to_float(POINTFX *pt, int count, float emsquare)
1691 {
1692     D3DXVECTOR2 *ret = (D3DXVECTOR2*)pt;
1693     while (count--) {
1694         D3DXVECTOR2 *pt_flt = (D3DXVECTOR2*)pt;
1695         pt_flt->x = (pt->x.value + pt->x.fract / (float)0x10000) / emsquare;
1696         pt_flt->y = (pt->y.value + pt->y.fract / (float)0x10000) / emsquare;
1697         pt++;
1698     }
1699     return ret;
1700 }
1701
1702 static HRESULT add_bezier_points(struct outline *outline, const D3DXVECTOR2 *p1,
1703                                  const D3DXVECTOR2 *p2, const D3DXVECTOR2 *p3,
1704                                  float max_deviation_sq)
1705 {
1706     D3DXVECTOR2 split1 = {0, 0}, split2 = {0, 0}, middle, vec;
1707     float deviation_sq;
1708
1709     D3DXVec2Scale(&split1, D3DXVec2Add(&split1, p1, p2), 0.5f);
1710     D3DXVec2Scale(&split2, D3DXVec2Add(&split2, p2, p3), 0.5f);
1711     D3DXVec2Scale(&middle, D3DXVec2Add(&middle, &split1, &split2), 0.5f);
1712
1713     deviation_sq = D3DXVec2LengthSq(D3DXVec2Subtract(&vec, &middle, p2));
1714     if (deviation_sq < max_deviation_sq) {
1715         struct point2d *pt = add_points(outline, 1);
1716         if (!pt) return E_OUTOFMEMORY;
1717         pt->pos = *p2;
1718         pt->corner = POINTTYPE_CURVE;
1719         /* the end point is omitted because the end line merges into the next segment of
1720          * the split bezier curve, and the end of the split bezier curve is added outside
1721          * this recursive function. */
1722     } else {
1723         HRESULT hr = add_bezier_points(outline, p1, &split1, &middle, max_deviation_sq);
1724         if (hr != S_OK) return hr;
1725         hr = add_bezier_points(outline, &middle, &split2, p3, max_deviation_sq);
1726         if (hr != S_OK) return hr;
1727     }
1728
1729     return S_OK;
1730 }
1731
1732 static inline BOOL is_direction_similar(D3DXVECTOR2 *dir1, D3DXVECTOR2 *dir2, float cos_theta)
1733 {
1734     /* dot product = cos(theta) */
1735     return D3DXVec2Dot(dir1, dir2) > cos_theta;
1736 }
1737
1738 static inline D3DXVECTOR2 *unit_vec2(D3DXVECTOR2 *dir, const D3DXVECTOR2 *pt1, const D3DXVECTOR2 *pt2)
1739 {
1740     return D3DXVec2Normalize(D3DXVec2Subtract(dir, pt2, pt1), dir);
1741 }
1742
1743 struct cos_table
1744 {
1745     float cos_half;
1746     float cos_45;
1747     float cos_90;
1748 };
1749
1750 static BOOL attempt_line_merge(struct outline *outline,
1751                                int pt_index,
1752                                const D3DXVECTOR2 *nextpt,
1753                                BOOL to_curve,
1754                                const struct cos_table *table)
1755 {
1756     D3DXVECTOR2 curdir, lastdir;
1757     struct point2d *prevpt, *pt;
1758     BOOL ret = FALSE;
1759
1760     pt = &outline->items[pt_index];
1761     pt_index = (pt_index - 1 + outline->count) % outline->count;
1762     prevpt = &outline->items[pt_index];
1763
1764     if (to_curve)
1765         pt->corner = pt->corner != POINTTYPE_CORNER ? POINTTYPE_CURVE_MIDDLE : POINTTYPE_CURVE_START;
1766
1767     if (outline->count < 2)
1768         return FALSE;
1769
1770     /* remove last point if the next line continues the last line */
1771     unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
1772     unit_vec2(&curdir, &pt->pos, nextpt);
1773     if (is_direction_similar(&lastdir, &curdir, table->cos_half))
1774     {
1775         outline->count--;
1776         if (pt->corner == POINTTYPE_CURVE_END)
1777             prevpt->corner = pt->corner;
1778         if (prevpt->corner == POINTTYPE_CURVE_END && to_curve)
1779             prevpt->corner = POINTTYPE_CURVE_MIDDLE;
1780         pt = prevpt;
1781
1782         ret = TRUE;
1783         if (outline->count < 2)
1784             return ret;
1785
1786         pt_index = (pt_index - 1 + outline->count) % outline->count;
1787         prevpt = &outline->items[pt_index];
1788         unit_vec2(&lastdir, &prevpt->pos, &pt->pos);
1789         unit_vec2(&curdir, &pt->pos, nextpt);
1790     }
1791     return ret;
1792 }
1793
1794 static HRESULT create_outline(struct glyphinfo *glyph, void *raw_outline, int datasize,
1795                               float max_deviation_sq, float emsquare, const struct cos_table *cos_table)
1796 {
1797     TTPOLYGONHEADER *header = (TTPOLYGONHEADER *)raw_outline;
1798
1799     while ((char *)header < (char *)raw_outline + datasize)
1800     {
1801         TTPOLYCURVE *curve = (TTPOLYCURVE *)(header + 1);
1802         struct point2d *lastpt, *pt;
1803         D3DXVECTOR2 lastdir;
1804         D3DXVECTOR2 *pt_flt;
1805         int j;
1806         struct outline *outline = add_outline(&glyph->outlines);
1807
1808         if (!outline)
1809             return E_OUTOFMEMORY;
1810
1811         pt = add_points(outline, 1);
1812         if (!pt)
1813             return E_OUTOFMEMORY;
1814         pt_flt = convert_fixed_to_float(&header->pfxStart, 1, emsquare);
1815         pt->pos = *pt_flt;
1816         pt->corner = POINTTYPE_CORNER;
1817
1818         if (header->dwType != TT_POLYGON_TYPE)
1819             FIXME("Unknown header type %d\n", header->dwType);
1820
1821         while ((char *)curve < (char *)header + header->cb)
1822         {
1823             D3DXVECTOR2 bezier_start = outline->items[outline->count - 1].pos;
1824             BOOL to_curve = curve->wType != TT_PRIM_LINE && curve->cpfx > 1;
1825
1826             if (!curve->cpfx) {
1827                 curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
1828                 continue;
1829             }
1830
1831             pt_flt = convert_fixed_to_float(curve->apfx, curve->cpfx, emsquare);
1832
1833             attempt_line_merge(outline, outline->count - 1, &pt_flt[0], to_curve, cos_table);
1834
1835             if (to_curve)
1836             {
1837                 HRESULT hr;
1838                 int count = curve->cpfx;
1839                 j = 0;
1840
1841                 while (count > 2)
1842                 {
1843                     D3DXVECTOR2 bezier_end;
1844
1845                     D3DXVec2Scale(&bezier_end, D3DXVec2Add(&bezier_end, &pt_flt[j], &pt_flt[j+1]), 0.5f);
1846                     hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &bezier_end, max_deviation_sq);
1847                     if (hr != S_OK)
1848                         return hr;
1849                     bezier_start = bezier_end;
1850                     count--;
1851                     j++;
1852                 }
1853                 hr = add_bezier_points(outline, &bezier_start, &pt_flt[j], &pt_flt[j+1], max_deviation_sq);
1854                 if (hr != S_OK)
1855                     return hr;
1856
1857                 pt = add_points(outline, 1);
1858                 if (!pt)
1859                     return E_OUTOFMEMORY;
1860                 j++;
1861                 pt->pos = pt_flt[j];
1862                 pt->corner = POINTTYPE_CURVE_END;
1863             } else {
1864                 pt = add_points(outline, curve->cpfx);
1865                 if (!pt)
1866                     return E_OUTOFMEMORY;
1867                 for (j = 0; j < curve->cpfx; j++)
1868                 {
1869                     pt->pos = pt_flt[j];
1870                     pt->corner = POINTTYPE_CORNER;
1871                     pt++;
1872                 }
1873             }
1874
1875             curve = (TTPOLYCURVE *)&curve->apfx[curve->cpfx];
1876         }
1877
1878         /* remove last point if the next line continues the last line */
1879         if (outline->count >= 3) {
1880             BOOL to_curve;
1881
1882             lastpt = &outline->items[outline->count - 1];
1883             pt = &outline->items[0];
1884             if (pt->pos.x == lastpt->pos.x && pt->pos.y == lastpt->pos.y) {
1885                 if (lastpt->corner == POINTTYPE_CURVE_END)
1886                 {
1887                     if (pt->corner == POINTTYPE_CURVE_START)
1888                         pt->corner = POINTTYPE_CURVE_MIDDLE;
1889                     else
1890                         pt->corner = POINTTYPE_CURVE_END;
1891                 }
1892                 outline->count--;
1893                 lastpt = &outline->items[outline->count - 1];
1894             } else {
1895                 /* outline closed with a line from end to start point */
1896                 attempt_line_merge(outline, outline->count - 1, &pt->pos, FALSE, cos_table);
1897             }
1898             lastpt = &outline->items[0];
1899             to_curve = lastpt->corner != POINTTYPE_CORNER && lastpt->corner != POINTTYPE_CURVE_END;
1900             if (lastpt->corner == POINTTYPE_CURVE_START)
1901                 lastpt->corner = POINTTYPE_CORNER;
1902             pt = &outline->items[1];
1903             if (attempt_line_merge(outline, 0, &pt->pos, to_curve, cos_table))
1904                 *lastpt = outline->items[outline->count];
1905         }
1906
1907         lastpt = &outline->items[outline->count - 1];
1908         pt = &outline->items[0];
1909         unit_vec2(&lastdir, &lastpt->pos, &pt->pos);
1910         for (j = 0; j < outline->count; j++)
1911         {
1912             D3DXVECTOR2 curdir;
1913
1914             lastpt = pt;
1915             pt = &outline->items[(j + 1) % outline->count];
1916             unit_vec2(&curdir, &lastpt->pos, &pt->pos);
1917
1918             switch (lastpt->corner)
1919             {
1920                 case POINTTYPE_CURVE_START:
1921                 case POINTTYPE_CURVE_END:
1922                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_45))
1923                         lastpt->corner = POINTTYPE_CORNER;
1924                     break;
1925                 case POINTTYPE_CURVE_MIDDLE:
1926                     if (!is_direction_similar(&lastdir, &curdir, cos_table->cos_90))
1927                         lastpt->corner = POINTTYPE_CORNER;
1928                     else
1929                         lastpt->corner = POINTTYPE_CURVE;
1930                     break;
1931                 default:
1932                     break;
1933             }
1934             lastdir = curdir;
1935         }
1936
1937         header = (TTPOLYGONHEADER *)((char *)header + header->cb);
1938     }
1939     return S_OK;
1940 }
1941
1942 /* Get the y-distance from a line to a point */
1943 static float get_line_to_point_y_distance(D3DXVECTOR2 *line_pt1,
1944                                           D3DXVECTOR2 *line_pt2,
1945                                           D3DXVECTOR2 *point)
1946 {
1947     D3DXVECTOR2 line_vec = {0, 0};
1948     float line_pt_dx;
1949     float line_y;
1950
1951     D3DXVec2Subtract(&line_vec, line_pt2, line_pt1);
1952     line_pt_dx = point->x - line_pt1->x;
1953     line_y = line_pt1->y + (line_vec.y * line_pt_dx) / line_vec.x;
1954     return point->y - line_y;
1955 }
1956
1957 static D3DXVECTOR2 *get_indexed_point(struct point2d_index *pt_idx)
1958 {
1959     return &pt_idx->outline->items[pt_idx->vertex].pos;
1960 }
1961
1962 static D3DXVECTOR2 *get_ordered_vertex(struct glyphinfo *glyph, WORD index)
1963 {
1964     return get_indexed_point(&glyph->ordered_vertices.items[index]);
1965 }
1966
1967 static void remove_triangulation(struct triangulation_array *array, struct triangulation *item)
1968 {
1969     HeapFree(GetProcessHeap(), 0, item->vertex_stack.items);
1970     MoveMemory(item, item + 1, (char*)&array->items[array->count] - (char*)(item + 1));
1971     array->count--;
1972 }
1973
1974 static HRESULT triangulation_add_point(struct triangulation **t_ptr,
1975                                        struct triangulation_array *triangulations,
1976                                        WORD vtx_idx,
1977                                        BOOL to_top)
1978 {
1979     struct glyphinfo *glyph = triangulations->glyph;
1980     struct triangulation *t = *t_ptr;
1981     HRESULT hr;
1982     face *face;
1983     int f1, f2;
1984
1985     if (t->last_on_top) {
1986         f1 = 1;
1987         f2 = 2;
1988     } else {
1989         f1 = 2;
1990         f2 = 1;
1991     }
1992
1993     if (t->last_on_top != to_top && t->vertex_stack.count > 1) {
1994         /* consume all vertices on the stack */
1995         WORD last_pt = t->vertex_stack.items[0];
1996         int i;
1997         for (i = 1; i < t->vertex_stack.count; i++)
1998         {
1999             face = add_face(&glyph->faces);
2000             if (!face) return E_OUTOFMEMORY;
2001             (*face)[0] = vtx_idx;
2002             (*face)[f1] = last_pt;
2003             (*face)[f2] = last_pt = t->vertex_stack.items[i];
2004         }
2005         t->vertex_stack.items[0] = last_pt;
2006         t->vertex_stack.count = 1;
2007     } else if (t->vertex_stack.count > 1) {
2008         int i = t->vertex_stack.count - 1;
2009         D3DXVECTOR2 *point = get_ordered_vertex(glyph, vtx_idx);
2010         WORD top_idx = t->vertex_stack.items[i--];
2011         D3DXVECTOR2 *top_pt = get_ordered_vertex(glyph, top_idx);
2012
2013         while (i >= 0)
2014         {
2015             WORD prev_idx = t->vertex_stack.items[i--];
2016             D3DXVECTOR2 *prev_pt = get_ordered_vertex(glyph, prev_idx);
2017
2018             if (prev_pt->x != top_pt->x &&
2019                 ((to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) > 0) ||
2020                  (!to_top && get_line_to_point_y_distance(prev_pt, top_pt, point) < 0)))
2021                 break;
2022
2023             face = add_face(&glyph->faces);
2024             if (!face) return E_OUTOFMEMORY;
2025             (*face)[0] = vtx_idx;
2026             (*face)[f1] = prev_idx;
2027             (*face)[f2] = top_idx;
2028
2029             top_pt = prev_pt;
2030             top_idx = prev_idx;
2031             t->vertex_stack.count--;
2032         }
2033     }
2034     t->last_on_top = to_top;
2035
2036     hr = add_vertex_index(&t->vertex_stack, vtx_idx);
2037
2038     if (hr == S_OK && t->merging) {
2039         struct triangulation *t2;
2040
2041         t2 = to_top ? t - 1 : t + 1;
2042         t2->merging = FALSE;
2043         hr = triangulation_add_point(&t2, triangulations, vtx_idx, to_top);
2044         if (hr != S_OK) return hr;
2045         remove_triangulation(triangulations, t);
2046         if (t2 > t)
2047             t2--;
2048         *t_ptr = t2;
2049     }
2050     return hr;
2051 }
2052
2053 /* check if the point is next on the outline for either the top or bottom */
2054 static D3DXVECTOR2 *triangulation_get_next_point(struct triangulation *t, struct glyphinfo *glyph, BOOL on_top)
2055 {
2056     int i = t->last_on_top == on_top ? t->vertex_stack.count - 1 : 0;
2057     WORD idx = t->vertex_stack.items[i];
2058     struct point2d_index *pt_idx = &glyph->ordered_vertices.items[idx];
2059     struct outline *outline = pt_idx->outline;
2060
2061     if (on_top)
2062         i = (pt_idx->vertex + outline->count - 1) % outline->count;
2063     else
2064         i = (pt_idx->vertex + 1) % outline->count;
2065
2066     return &outline->items[i].pos;
2067 }
2068
2069 static int compare_vertex_indices(const void *a, const void *b)
2070 {
2071     const struct point2d_index *idx1 = a, *idx2 = b;
2072     const D3DXVECTOR2 *p1 = &idx1->outline->items[idx1->vertex].pos;
2073     const D3DXVECTOR2 *p2 = &idx2->outline->items[idx2->vertex].pos;
2074     float diff = p1->x - p2->x;
2075
2076     if (diff == 0.0f)
2077         diff = p1->y - p2->y;
2078
2079     return diff == 0.0f ? 0 : (diff > 0.0f ? -1 : 1);
2080 }
2081
2082 static HRESULT triangulate(struct triangulation_array *triangulations)
2083 {
2084     int sweep_idx;
2085     HRESULT hr;
2086     struct glyphinfo *glyph = triangulations->glyph;
2087     int nb_vertices = 0;
2088     int i;
2089     struct point2d_index *idx_ptr;
2090
2091     for (i = 0; i < glyph->outlines.count; i++)
2092         nb_vertices += glyph->outlines.items[i].count;
2093
2094     glyph->ordered_vertices.items = HeapAlloc(GetProcessHeap(), 0,
2095             nb_vertices * sizeof(*glyph->ordered_vertices.items));
2096     if (!glyph->ordered_vertices.items)
2097         return E_OUTOFMEMORY;
2098
2099     idx_ptr = glyph->ordered_vertices.items;
2100     for (i = 0; i < glyph->outlines.count; i++)
2101     {
2102         struct outline *outline = &glyph->outlines.items[i];
2103         int j;
2104
2105         idx_ptr->outline = outline;
2106         idx_ptr->vertex = 0;
2107         idx_ptr++;
2108         for (j = outline->count - 1; j > 0; j--)
2109         {
2110             idx_ptr->outline = outline;
2111             idx_ptr->vertex = j;
2112             idx_ptr++;
2113         }
2114     }
2115     glyph->ordered_vertices.count = nb_vertices;
2116
2117     /* Native implementation seems to try to create a triangle fan from
2118      * the first outline point if the glyph only has one outline. */
2119     if (glyph->outlines.count == 1)
2120     {
2121         struct outline *outline = glyph->outlines.items;
2122         D3DXVECTOR2 *base = &outline->items[0].pos;
2123         D3DXVECTOR2 *last = &outline->items[1].pos;
2124         float ccw = 0;
2125
2126         for (i = 2; i < outline->count; i++)
2127         {
2128             D3DXVECTOR2 *next = &outline->items[i].pos;
2129             D3DXVECTOR2 v1 = {0.0f, 0.0f};
2130             D3DXVECTOR2 v2 = {0.0f, 0.0f};
2131
2132             D3DXVec2Subtract(&v1, base, last);
2133             D3DXVec2Subtract(&v2, last, next);
2134             ccw = D3DXVec2CCW(&v1, &v2);
2135             if (ccw > 0.0f)
2136                 break;
2137
2138             last = next;
2139         }
2140         if (ccw <= 0)
2141         {
2142             glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
2143                     (outline->count - 2) * sizeof(glyph->faces.items[0]));
2144             if (!glyph->faces.items)
2145                 return E_OUTOFMEMORY;
2146
2147             glyph->faces.count = outline->count - 2;
2148             for (i = 0; i < glyph->faces.count; i++)
2149             {
2150                 glyph->faces.items[i][0] = 0;
2151                 glyph->faces.items[i][1] = i + 1;
2152                 glyph->faces.items[i][2] = i + 2;
2153             }
2154             return S_OK;
2155         }
2156     }
2157
2158     /* Perform 2D polygon triangulation for complex glyphs.
2159      * Triangulation is performed using a sweep line concept, from right to left,
2160      * by processing vertices in sorted order. Complex polygons are split into
2161      * monotone polygons which are triangulated seperately. */
2162     /* FIXME: The order of the faces is not consistent with the native implementation. */
2163
2164     /* Reserve space for maximum possible faces from triangulation.
2165      * # faces for outer outlines = outline->count - 2
2166      * # faces for inner outlines = outline->count + 2
2167      * There must be at least 1 outer outline. */
2168     glyph->faces.items = HeapAlloc(GetProcessHeap(), 0,
2169             (nb_vertices + glyph->outlines.count * 2 - 4) * sizeof(glyph->faces.items[0]));
2170     if (!glyph->faces.items)
2171         return E_OUTOFMEMORY;
2172
2173     qsort(glyph->ordered_vertices.items, nb_vertices,
2174           sizeof(glyph->ordered_vertices.items[0]), compare_vertex_indices);
2175     for (sweep_idx = 0; sweep_idx < glyph->ordered_vertices.count; sweep_idx++)
2176     {
2177         int start = 0;
2178         int end = triangulations->count;
2179
2180         while (start < end)
2181         {
2182             D3DXVECTOR2 *sweep_vtx = get_ordered_vertex(glyph, sweep_idx);
2183             int current = (start + end) / 2;
2184             struct triangulation *t = &triangulations->items[current];
2185             BOOL on_top_outline = FALSE;
2186             D3DXVECTOR2 *top_next, *bottom_next;
2187             WORD top_idx, bottom_idx;
2188
2189             if (t->merging && t->last_on_top)
2190                 top_next = triangulation_get_next_point(t + 1, glyph, TRUE);
2191             else
2192                 top_next = triangulation_get_next_point(t, glyph, TRUE);
2193             if (sweep_vtx == top_next)
2194             {
2195                 if (t->merging && t->last_on_top)
2196                     t++;
2197                 hr = triangulation_add_point(&t, triangulations, sweep_idx, TRUE);
2198                 if (hr != S_OK) return hr;
2199
2200                 if (t + 1 < &triangulations->items[triangulations->count] &&
2201                     triangulation_get_next_point(t + 1, glyph, FALSE) == sweep_vtx)
2202                 {
2203                     /* point also on bottom outline of higher triangulation */
2204                     struct triangulation *t2 = t + 1;
2205                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, FALSE);
2206                     if (hr != S_OK) return hr;
2207
2208                     t->merging = TRUE;
2209                     t2->merging = TRUE;
2210                 }
2211                 on_top_outline = TRUE;
2212             }
2213
2214             if (t->merging && !t->last_on_top)
2215                 bottom_next = triangulation_get_next_point(t - 1, glyph, FALSE);
2216             else
2217                 bottom_next = triangulation_get_next_point(t, glyph, FALSE);
2218             if (sweep_vtx == bottom_next)
2219             {
2220                 if (t->merging && !t->last_on_top)
2221                     t--;
2222                 if (on_top_outline) {
2223                     /* outline finished */
2224                     remove_triangulation(triangulations, t);
2225                     break;
2226                 }
2227
2228                 hr = triangulation_add_point(&t, triangulations, sweep_idx, FALSE);
2229                 if (hr != S_OK) return hr;
2230
2231                 if (t > triangulations->items &&
2232                     triangulation_get_next_point(t - 1, glyph, TRUE) == sweep_vtx)
2233                 {
2234                     struct triangulation *t2 = t - 1;
2235                     /* point also on top outline of lower triangulation */
2236                     hr = triangulation_add_point(&t2, triangulations, sweep_idx, TRUE);
2237                     if (hr != S_OK) return hr;
2238                     t = t2 + 1; /* t may be invalidated by triangulation merging */
2239
2240                     t->merging = TRUE;
2241                     t2->merging = TRUE;
2242                 }
2243                 break;
2244             }
2245             if (on_top_outline)
2246                 break;
2247
2248             if (t->last_on_top) {
2249                 top_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
2250                 bottom_idx = t->vertex_stack.items[0];
2251             } else {
2252                 top_idx = t->vertex_stack.items[0];
2253                 bottom_idx = t->vertex_stack.items[t->vertex_stack.count - 1];
2254             }
2255
2256             /* check if the point is inside or outside this polygon */
2257             if (get_line_to_point_y_distance(get_ordered_vertex(glyph, top_idx),
2258                                              top_next, sweep_vtx) > 0)
2259             { /* above */
2260                 start = current + 1;
2261             } else if (get_line_to_point_y_distance(get_ordered_vertex(glyph, bottom_idx),
2262                                                     bottom_next, sweep_vtx) < 0)
2263             { /* below */
2264                 end = current;
2265             } else if (t->merging) {
2266                 /* inside, so cancel merging */
2267                 struct triangulation *t2 = t->last_on_top ? t + 1 : t - 1;
2268                 t->merging = FALSE;
2269                 t2->merging = FALSE;
2270                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
2271                 if (hr != S_OK) return hr;
2272                 hr = triangulation_add_point(&t2, triangulations, sweep_idx, t2->last_on_top);
2273                 if (hr != S_OK) return hr;
2274                 break;
2275             } else {
2276                 /* inside, so split polygon into two monotone parts */
2277                 struct triangulation *t2 = add_triangulation(triangulations);
2278                 if (!t2) return E_OUTOFMEMORY;
2279                 MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
2280                 if (t->last_on_top) {
2281                     t2 = t + 1;
2282                 } else {
2283                     t2 = t;
2284                     t++;
2285                 }
2286
2287                 ZeroMemory(&t2->vertex_stack, sizeof(t2->vertex_stack));
2288                 hr = add_vertex_index(&t2->vertex_stack, t->vertex_stack.items[t->vertex_stack.count - 1]);
2289                 if (hr != S_OK) return hr;
2290                 hr = add_vertex_index(&t2->vertex_stack, sweep_idx);
2291                 if (hr != S_OK) return hr;
2292                 t2->last_on_top = !t->last_on_top;
2293
2294                 hr = triangulation_add_point(&t, triangulations, sweep_idx, t->last_on_top);
2295                 if (hr != S_OK) return hr;
2296                 break;
2297             }
2298         }
2299         if (start >= end)
2300         {
2301             struct triangulation *t;
2302             struct triangulation *t2 = add_triangulation(triangulations);
2303             if (!t2) return E_OUTOFMEMORY;
2304             t = &triangulations->items[start];
2305             MoveMemory(t + 1, t, (char*)(t2 + 1) - (char*)t);
2306             ZeroMemory(t, sizeof(*t));
2307             hr = add_vertex_index(&t->vertex_stack, sweep_idx);
2308             if (hr != S_OK) return hr;
2309         }
2310     }
2311     return S_OK;
2312 }
2313
2314 HRESULT WINAPI D3DXCreateTextW(LPDIRECT3DDEVICE9 device,
2315                                HDC hdc, LPCWSTR text,
2316                                FLOAT deviation, FLOAT extrusion,
2317                                LPD3DXMESH *mesh_ptr, LPD3DXBUFFER *adjacency,
2318                                LPGLYPHMETRICSFLOAT glyphmetrics)
2319 {
2320     HRESULT hr;
2321     ID3DXMesh *mesh = NULL;
2322     DWORD nb_vertices, nb_faces;
2323     DWORD nb_front_faces, nb_corners, nb_outline_points;
2324     struct vertex *vertices = NULL;
2325     face *faces = NULL;
2326     int textlen = 0;
2327     float offset_x;
2328     LOGFONTW lf;
2329     OUTLINETEXTMETRICW otm;
2330     HFONT font = NULL, oldfont = NULL;
2331     const MAT2 identity = {{0, 1}, {0, 0}, {0, 0}, {0, 1}};
2332     void *raw_outline = NULL;
2333     int bufsize = 0;
2334     struct glyphinfo *glyphs = NULL;
2335     GLYPHMETRICS gm;
2336     struct triangulation_array triangulations = {0, 0, NULL};
2337     int i;
2338     struct vertex *vertex_ptr;
2339     face *face_ptr;
2340     float max_deviation_sq;
2341     const struct cos_table cos_table = {
2342         cos(D3DXToRadian(0.5f)),
2343         cos(D3DXToRadian(45.0f)),
2344         cos(D3DXToRadian(90.0f)),
2345     };
2346     int f1, f2;
2347
2348     TRACE("(%p, %p, %s, %f, %f, %p, %p, %p)\n", device, hdc,
2349           debugstr_w(text), deviation, extrusion, mesh_ptr, adjacency, glyphmetrics);
2350
2351     if (!device || !hdc || !text || !*text || deviation < 0.0f || extrusion < 0.0f || !mesh_ptr)
2352         return D3DERR_INVALIDCALL;
2353
2354     if (adjacency)
2355     {
2356         FIXME("Case of adjacency != NULL not implemented.\n");
2357         return E_NOTIMPL;
2358     }
2359
2360     if (!GetObjectW(GetCurrentObject(hdc, OBJ_FONT), sizeof(lf), &lf) ||
2361         !GetOutlineTextMetricsW(hdc, sizeof(otm), &otm))
2362     {
2363         return D3DERR_INVALIDCALL;
2364     }
2365
2366     if (deviation == 0.0f)
2367         deviation = 1.0f / otm.otmEMSquare;
2368     max_deviation_sq = deviation * deviation;
2369
2370     lf.lfHeight = otm.otmEMSquare;
2371     lf.lfWidth = 0;
2372     font = CreateFontIndirectW(&lf);
2373     if (!font) {
2374         hr = E_OUTOFMEMORY;
2375         goto error;
2376     }
2377     oldfont = SelectObject(hdc, font);
2378
2379     textlen = strlenW(text);
2380     for (i = 0; i < textlen; i++)
2381     {
2382         int datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, 0, NULL, &identity);
2383         if (datasize < 0)
2384             return D3DERR_INVALIDCALL;
2385         if (bufsize < datasize)
2386             bufsize = datasize;
2387     }
2388     if (!bufsize) { /* e.g. text == " " */
2389         hr = D3DERR_INVALIDCALL;
2390         goto error;
2391     }
2392
2393     glyphs = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, textlen * sizeof(*glyphs));
2394     raw_outline = HeapAlloc(GetProcessHeap(), 0, bufsize);
2395     if (!glyphs || !raw_outline) {
2396         hr = E_OUTOFMEMORY;
2397         goto error;
2398     }
2399
2400     offset_x = 0.0f;
2401     for (i = 0; i < textlen; i++)
2402     {
2403         /* get outline points from data returned from GetGlyphOutline */
2404         int datasize;
2405
2406         glyphs[i].offset_x = offset_x;
2407
2408         datasize = GetGlyphOutlineW(hdc, text[i], GGO_NATIVE, &gm, bufsize, raw_outline, &identity);
2409         hr = create_outline(&glyphs[i], raw_outline, datasize,
2410                             max_deviation_sq, otm.otmEMSquare, &cos_table);
2411         if (hr != S_OK) goto error;
2412
2413         triangulations.glyph = &glyphs[i];
2414         hr = triangulate(&triangulations);
2415         if (hr != S_OK) goto error;
2416         if (triangulations.count) {
2417             ERR("%d incomplete triangulations of glyph (%u).\n", triangulations.count, text[i]);
2418             triangulations.count = 0;
2419         }
2420
2421         if (glyphmetrics)
2422         {
2423             glyphmetrics[i].gmfBlackBoxX = gm.gmBlackBoxX / (float)otm.otmEMSquare;
2424             glyphmetrics[i].gmfBlackBoxY = gm.gmBlackBoxY / (float)otm.otmEMSquare;
2425             glyphmetrics[i].gmfptGlyphOrigin.x = gm.gmptGlyphOrigin.x / (float)otm.otmEMSquare;
2426             glyphmetrics[i].gmfptGlyphOrigin.y = gm.gmptGlyphOrigin.y / (float)otm.otmEMSquare;
2427             glyphmetrics[i].gmfCellIncX = gm.gmCellIncX / (float)otm.otmEMSquare;
2428             glyphmetrics[i].gmfCellIncY = gm.gmCellIncY / (float)otm.otmEMSquare;
2429         }
2430         offset_x += gm.gmCellIncX / (float)otm.otmEMSquare;
2431     }
2432
2433     /* corner points need an extra vertex for the different side faces normals */
2434     nb_corners = 0;
2435     nb_outline_points = 0;
2436     nb_front_faces = 0;
2437     for (i = 0; i < textlen; i++)
2438     {
2439         int j;
2440         nb_outline_points += glyphs[i].ordered_vertices.count;
2441         nb_front_faces += glyphs[i].faces.count;
2442         for (j = 0; j < glyphs[i].outlines.count; j++)
2443         {
2444             int k;
2445             struct outline *outline = &glyphs[i].outlines.items[j];
2446             nb_corners++; /* first outline point always repeated as a corner */
2447             for (k = 1; k < outline->count; k++)
2448                 if (outline->items[k].corner)
2449                     nb_corners++;
2450         }
2451     }
2452
2453     nb_vertices = (nb_outline_points + nb_corners) * 2 + nb_outline_points * 2;
2454     nb_faces = nb_outline_points * 2 + nb_front_faces * 2;
2455
2456
2457     hr = D3DXCreateMeshFVF(nb_faces, nb_vertices, D3DXMESH_MANAGED,
2458                            D3DFVF_XYZ | D3DFVF_NORMAL, device, &mesh);
2459     if (FAILED(hr))
2460         goto error;
2461
2462     hr = mesh->lpVtbl->LockVertexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&vertices);
2463     if (FAILED(hr))
2464         goto error;
2465
2466     hr = mesh->lpVtbl->LockIndexBuffer(mesh, D3DLOCK_DISCARD, (LPVOID *)&faces);
2467     if (FAILED(hr))
2468         goto error;
2469
2470     /* convert 2D vertices and faces into 3D mesh */
2471     vertex_ptr = vertices;
2472     face_ptr = faces;
2473     if (extrusion == 0.0f) {
2474         f1 = 1;
2475         f2 = 2;
2476     } else {
2477         f1 = 2;
2478         f2 = 1;
2479     }
2480     for (i = 0; i < textlen; i++)
2481     {
2482         int j;
2483         int count;
2484         struct vertex *back_vertices;
2485         face *back_faces;
2486
2487         /* side vertices and faces */
2488         for (j = 0; j < glyphs[i].outlines.count; j++)
2489         {
2490             struct vertex *outline_vertices = vertex_ptr;
2491             struct outline *outline = &glyphs[i].outlines.items[j];
2492             int k;
2493             struct point2d *prevpt = &outline->items[outline->count - 1];
2494             struct point2d *pt = &outline->items[0];
2495
2496             for (k = 1; k <= outline->count; k++)
2497             {
2498                 struct vertex vtx;
2499                 struct point2d *nextpt = &outline->items[k % outline->count];
2500                 WORD vtx_idx = vertex_ptr - vertices;
2501                 D3DXVECTOR2 vec;
2502
2503                 if (pt->corner == POINTTYPE_CURVE_START)
2504                     D3DXVec2Subtract(&vec, &pt->pos, &prevpt->pos);
2505                 else if (pt->corner)
2506                     D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
2507                 else
2508                     D3DXVec2Subtract(&vec, &nextpt->pos, &prevpt->pos);
2509                 D3DXVec2Normalize(&vec, &vec);
2510                 vtx.normal.x = -vec.y;
2511                 vtx.normal.y = vec.x;
2512                 vtx.normal.z = 0;
2513
2514                 vtx.position.x = pt->pos.x + glyphs[i].offset_x;
2515                 vtx.position.y = pt->pos.y;
2516                 vtx.position.z = 0;
2517                 *vertex_ptr++ = vtx;
2518
2519                 vtx.position.z = -extrusion;
2520                 *vertex_ptr++ = vtx;
2521
2522                 vtx.position.x = nextpt->pos.x + glyphs[i].offset_x;
2523                 vtx.position.y = nextpt->pos.y;
2524                 if (pt->corner && nextpt->corner && nextpt->corner != POINTTYPE_CURVE_END) {
2525                     vtx.position.z = -extrusion;
2526                     *vertex_ptr++ = vtx;
2527                     vtx.position.z = 0;
2528                     *vertex_ptr++ = vtx;
2529
2530                     (*face_ptr)[0] = vtx_idx;
2531                     (*face_ptr)[1] = vtx_idx + 2;
2532                     (*face_ptr)[2] = vtx_idx + 1;
2533                     face_ptr++;
2534
2535                     (*face_ptr)[0] = vtx_idx;
2536                     (*face_ptr)[1] = vtx_idx + 3;
2537                     (*face_ptr)[2] = vtx_idx + 2;
2538                     face_ptr++;
2539                 } else {
2540                     if (nextpt->corner) {
2541                         if (nextpt->corner == POINTTYPE_CURVE_END) {
2542                             D3DXVECTOR2 *nextpt2 = &outline->items[(k + 1) % outline->count].pos;
2543                             D3DXVec2Subtract(&vec, nextpt2, &nextpt->pos);
2544                         } else {
2545                             D3DXVec2Subtract(&vec, &nextpt->pos, &pt->pos);
2546                         }
2547                         D3DXVec2Normalize(&vec, &vec);
2548                         vtx.normal.x = -vec.y;
2549                         vtx.normal.y = vec.x;
2550
2551                         vtx.position.z = 0;
2552                         *vertex_ptr++ = vtx;
2553                         vtx.position.z = -extrusion;
2554                         *vertex_ptr++ = vtx;
2555                     }
2556
2557                     (*face_ptr)[0] = vtx_idx;
2558                     (*face_ptr)[1] = vtx_idx + 3;
2559                     (*face_ptr)[2] = vtx_idx + 1;
2560                     face_ptr++;
2561
2562                     (*face_ptr)[0] = vtx_idx;
2563                     (*face_ptr)[1] = vtx_idx + 2;
2564                     (*face_ptr)[2] = vtx_idx + 3;
2565                     face_ptr++;
2566                 }
2567
2568                 prevpt = pt;
2569                 pt = nextpt;
2570             }
2571             if (!pt->corner) {
2572                 *vertex_ptr++ = *outline_vertices++;
2573                 *vertex_ptr++ = *outline_vertices++;
2574             }
2575         }
2576
2577         /* back vertices and faces */
2578         back_faces = face_ptr;
2579         back_vertices = vertex_ptr;
2580         for (j = 0; j < glyphs[i].ordered_vertices.count; j++)
2581         {
2582             D3DXVECTOR2 *pt = get_ordered_vertex(&glyphs[i], j);
2583             vertex_ptr->position.x = pt->x + glyphs[i].offset_x;
2584             vertex_ptr->position.y = pt->y;
2585             vertex_ptr->position.z = 0;
2586             vertex_ptr->normal.x = 0;
2587             vertex_ptr->normal.y = 0;
2588             vertex_ptr->normal.z = 1;
2589             vertex_ptr++;
2590         }
2591         count = back_vertices - vertices;
2592         for (j = 0; j < glyphs[i].faces.count; j++)
2593         {
2594             face *f = &glyphs[i].faces.items[j];
2595             (*face_ptr)[0] = (*f)[0] + count;
2596             (*face_ptr)[1] = (*f)[1] + count;
2597             (*face_ptr)[2] = (*f)[2] + count;
2598             face_ptr++;
2599         }
2600
2601         /* front vertices and faces */
2602         j = count = vertex_ptr - back_vertices;
2603         while (j--)
2604         {
2605             vertex_ptr->position.x = back_vertices->position.x;
2606             vertex_ptr->position.y = back_vertices->position.y;
2607             vertex_ptr->position.z = -extrusion;
2608             vertex_ptr->normal.x = 0;
2609             vertex_ptr->normal.y = 0;
2610             vertex_ptr->normal.z = extrusion == 0.0f ? 1.0f : -1.0f;
2611             vertex_ptr++;
2612             back_vertices++;
2613         }
2614         j = face_ptr - back_faces;
2615         while (j--)
2616         {
2617             (*face_ptr)[0] = (*back_faces)[0] + count;
2618             (*face_ptr)[1] = (*back_faces)[f1] + count;
2619             (*face_ptr)[2] = (*back_faces)[f2] + count;
2620             face_ptr++;
2621             back_faces++;
2622         }
2623     }
2624
2625     *mesh_ptr = mesh;
2626     hr = D3D_OK;
2627 error:
2628     if (mesh) {
2629         if (faces) mesh->lpVtbl->UnlockIndexBuffer(mesh);
2630         if (vertices) mesh->lpVtbl->UnlockVertexBuffer(mesh);
2631         if (hr != D3D_OK) mesh->lpVtbl->Release(mesh);
2632     }
2633     if (glyphs) {
2634         for (i = 0; i < textlen; i++)
2635         {
2636             int j;
2637             for (j = 0; j < glyphs[i].outlines.count; j++)
2638                 HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items[j].items);
2639             HeapFree(GetProcessHeap(), 0, glyphs[i].outlines.items);
2640             HeapFree(GetProcessHeap(), 0, glyphs[i].faces.items);
2641             HeapFree(GetProcessHeap(), 0, glyphs[i].ordered_vertices.items);
2642         }
2643         HeapFree(GetProcessHeap(), 0, glyphs);
2644     }
2645     if (triangulations.items) {
2646         int i;
2647         for (i = 0; i < triangulations.count; i++)
2648             HeapFree(GetProcessHeap(), 0, triangulations.items[i].vertex_stack.items);
2649         HeapFree(GetProcessHeap(), 0, triangulations.items);
2650     }
2651     HeapFree(GetProcessHeap(), 0, raw_outline);
2652     if (oldfont) SelectObject(hdc, oldfont);
2653     if (font) DeleteObject(font);
2654
2655     return hr;
2656 }