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