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