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