On Thu, Jun 30, 2011 at 6:42 PM, Michael Mc Donnell <mich...@mcdonnell.dk> wrote: > On Thu, Jun 30, 2011 at 4:10 PM, Henri Verbeet <hverb...@gmail.com> wrote: >> On 30 June 2011 14:49, Michael Mc Donnell <mich...@mcdonnell.dk> wrote: >>> In init_edge_face_map I initialize an array of edge_face structs, and >>> in find_adjacent_face I do a linear search through that array. I would >>> like to replace the array with a hash table, so that the search time >>> becomes constant. I've found a standard list (wine/list.h) and >>> red-black tree implementation (wine/rbtree.h), but not a standard hash >>> table implementation. Is there a standard hash table implementation, >>> should I roll my own or find an LGPL'ed one? >>> >> I'm not sure if a hash table would be faster and how much, but an easy >> way to make the lookup cheaper would be to store the edge -> face map >> as a list for each vertex. >> >> ... >> >> It's then mostly trivial to determine adjacency. This assumes most >> vertices are only part of a handful of edges, but I don't think that's >> unreasonable in practice. > > Thanks for your suggestion. I think you're right that it is safe to > assume that most vertices will only be a part of a few edges. I'll > implement that for now.
I've implemented the look-up scheme that you described. I have another question about my test. I've basically copied all the test data from my ConvertAdjacencyToPointReps test, and then just inverted the conditions. Should I merge the two tests, put the test data in a separate function, or just ignore the duplication?
From 549a95e2f8f218541d3f54afd08ee522e4e27e3e Mon Sep 17 00:00:00 2001 From: Michael Mc Donnell <mich...@mcdonnell.dk> Date: Thu, 23 Jun 2011 17:46:51 +0200 Subject: d3dx9/test: Implemented ConvertPointRepsToAdjacency test. --- dlls/d3dx9_36/tests/mesh.c | 452 ++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 452 insertions(+), 0 deletions(-) diff --git a/dlls/d3dx9_36/tests/mesh.c b/dlls/d3dx9_36/tests/mesh.c index 98d77d9..1da6ed0 100644 --- a/dlls/d3dx9_36/tests/mesh.c +++ b/dlls/d3dx9_36/tests/mesh.c @@ -4904,6 +4904,457 @@ static void test_create_skin_info(void) ok(hr == D3DERR_INVALIDCALL, "Expected D3DERR_INVALIDCALL, got %#x\n", hr); } +static void test_convert_point_reps_to_adjacency(void) +{ + HRESULT hr; + struct test_context *test_context = NULL; + const DWORD options = D3DXMESH_32BIT | D3DXMESH_SYSTEMMEM; + const DWORD options_16bit = D3DXMESH_SYSTEMMEM; + const D3DVERTEXELEMENT9 declaration[] = + { + {0, 0, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_POSITION, 0}, + {0, 12, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_NORMAL, 0}, + {0, 24, D3DDECLTYPE_D3DCOLOR, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_COLOR, 0}, + D3DDECL_END() + }; + const unsigned int VERTS_PER_FACE = 3; + void *vertex_buffer; + void *index_buffer; + DWORD *attributes_buffer; + int i, j; + enum color { RED = 0xffff0000, GREEN = 0xff00ff00, BLUE = 0xff0000ff}; + struct vertex_pnc + { + D3DXVECTOR3 position; + D3DXVECTOR3 normal; + enum color color; /* In case of manual visual inspection */ + }; + D3DXVECTOR3 up = {0.0f, 0.0f, 1.0f}; + /* mesh0 (one face) + * + * 0--1 + * | / + * |/ + * 2 + */ + const struct vertex_pnc vertices0[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + }; + const DWORD indices0[] = {0, 1, 2}; + const unsigned int num_vertices0 = ARRAY_SIZE(vertices0); + const DWORD exp_adjacency0[] = {-1, -1, -1}; + const DWORD point_rep0[] = {0, 1, 2}; + /* mesh1 (right) + * + * 0--1 3 + * | / /| + * |/ / | + * 2 5--4 + */ + const struct vertex_pnc vertices1[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 3.0f, 3.0f, 0.f}, up, GREEN}, + {{ 3.0f, 0.0f, 0.f}, up, RED}, + {{ 1.0f, 0.0f, 0.f}, up, BLUE}, + }; + const DWORD indices1[] = {0, 1, 2, 3, 4, 5}; + const unsigned int num_vertices1 = ARRAY_SIZE(vertices1); + const DWORD exp_adjacency1[] = {-1, 1, -1, -1, -1, 0}; + const DWORD point_rep1[] = {0, 1, 2, 1, 4, 2}; + /* mesh2 (left) + * + * 3 0--1 + * /| | / + * / | |/ + * 5--4 2 + */ + const struct vertex_pnc vertices2[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{-1.0f, 3.0f, 0.f}, up, RED}, + {{-1.0f, 0.0f, 0.f}, up, GREEN}, + {{-3.0f, 0.0f, 0.f}, up, BLUE}, + }; + const DWORD indices2[] = {0, 1, 2, 3, 4, 5}; + const unsigned int num_vertices2 = ARRAY_SIZE(vertices2); + const DWORD exp_adjacency2[] = {-1, -1, 1, 0, -1, -1}; + const DWORD point_rep2[] = {0, 1, 2, 0, 2, 5}; + /* mesh3 (above) + * + * 3 + * /| + * / | + * 5--4 + * 0--1 + * | / + * |/ + * 2 + */ + struct vertex_pnc vertices3[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 2.0f, 7.0f, 0.f}, up, BLUE}, + {{ 2.0f, 4.0f, 0.f}, up, GREEN}, + {{ 0.0f, 4.0f, 0.f}, up, RED}, + }; + const DWORD indices3[] = {0, 1, 2, 3, 4, 5}; + const unsigned int num_vertices3 = ARRAY_SIZE(vertices3); + const DWORD exp_adjacency3[] = {1, -1, -1, -1, 0, -1}; + const DWORD point_rep3[] = {0, 1, 2, 3, 1, 0}; + /* mesh4 (below, tip against tip) + * + * 0--1 + * | / + * |/ + * 2 + * 3 + * |\ + * | \ + * 5--4 + */ + struct vertex_pnc vertices4[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 0.0f, -4.0f, 0.f}, up, BLUE}, + {{ 2.0f, -7.0f, 0.f}, up, GREEN}, + {{ 0.0f, -7.0f, 0.f}, up, RED}, + }; + const DWORD indices4[] = {0, 1, 2, 3, 4, 5}; + const unsigned int num_vertices4 = ARRAY_SIZE(vertices4); + const DWORD exp_adjacency4[] = {-1, -1, -1, -1, -1, -1}; + const DWORD point_rep4[] = {0, 1, 2, 3, 4, 5}; + /* mesh5 (gap in mesh) + * + * 0 3-----4 15 + * / \ \ / / \ + * / \ \ / / \ + * 2-----1 5 17-----16 + * 6-----7 9 12-----13 + * \ / / \ \ / + * \ / / \ \ / + * 8 10-----11 14 + * + */ + const struct vertex_pnc vertices5[] = + { + {{ 0.0f, 1.0f, 0.f}, up, RED}, + {{ 1.0f, -1.0f, 0.f}, up, GREEN}, + {{-1.0f, -1.0f, 0.f}, up, BLUE}, + + {{ 0.1f, 1.0f, 0.f}, up, RED}, + {{ 2.1f, 1.0f, 0.f}, up, BLUE}, + {{ 1.1f, -1.0f, 0.f}, up, GREEN}, + + {{-1.0f, -1.1f, 0.f}, up, BLUE}, + {{ 1.0f, -1.1f, 0.f}, up, GREEN}, + {{ 0.0f, -3.1f, 0.f}, up, RED}, + + {{ 1.1f, -1.1f, 0.f}, up, GREEN}, + {{ 2.1f, -3.1f, 0.f}, up, BLUE}, + {{ 0.1f, -3.1f, 0.f}, up, RED}, + + {{ 1.2f, -1.1f, 0.f}, up, GREEN}, + {{ 3.2f, -1.1f, 0.f}, up, RED}, + {{ 2.2f, -3.1f, 0.f}, up, BLUE}, + + {{ 2.2f, 1.0f, 0.f}, up, BLUE}, + {{ 3.2f, -1.0f, 0.f}, up, RED}, + {{ 1.2f, -1.0f, 0.f}, up, GREEN}, + }; + const DWORD indices5[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; + const unsigned int num_vertices5 = ARRAY_SIZE(vertices5); + const DWORD exp_adjacency5[] = {-1, 2, -1, -1, 5, -1, 0, -1, -1, 4, -1, -1, 5, -1, 3, -1, 4, 1}; + const DWORD point_rep5[] = {0, 1, 2, 3, 4, 5, 2, 1, 8, 5, 10, 11, 5, 13, 10, 4, 13, 5}; + /* mesh6 (indices re-ordering) + * + * 0--1 6 3 + * | / /| |\ + * |/ / | | \ + * 2 8--7 5--4 + */ + const struct vertex_pnc vertices6[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 3.0f, 3.0f, 0.f}, up, GREEN}, + {{ 3.0f, 0.0f, 0.f}, up, RED}, + {{ 1.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 4.0f, 3.0f, 0.f}, up, GREEN}, + {{ 6.0f, 0.0f, 0.f}, up, BLUE}, + {{ 4.0f, 0.0f, 0.f}, up, RED}, + }; + const DWORD indices6[] = {0, 1, 2, 6, 7, 8, 3, 4, 5}; + const unsigned int num_vertices6 = ARRAY_SIZE(vertices6); + const DWORD exp_adjacency6[] = {-1, 1, -1, 2, -1, 0, -1, -1, 1}; + const DWORD point_rep6[] = {0, 1, 2, 1, 4, 5, 1, 5, 2}; + /* mesh7 (expands collapsed triangle) + * + * 0--1 3 + * | / /| + * |/ / | + * 2 5--4 + */ + const struct vertex_pnc vertices7[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 3.0f, 3.0f, 0.f}, up, GREEN}, + {{ 3.0f, 0.0f, 0.f}, up, RED}, + {{ 1.0f, 0.0f, 0.f}, up, BLUE}, + }; + const DWORD indices7[] = {0, 1, 2, 3, 3, 3}; /* Face 1 is collapsed*/ + const unsigned int num_vertices7 = ARRAY_SIZE(vertices7); + const DWORD exp_adjacency7[] = {-1, -1, -1, -1, -1, -1}; + const DWORD point_rep7[] = {0, 1, 2, 3, 4, 5}; + /* mesh8 (indices re-ordering and double replacement) + * + * 0--1 9 6 + * | / /| |\ + * |/ / | | \ + * 2 11-10 8--7 + * 3--4 + * | / + * |/ + * 5 + */ + const struct vertex_pnc vertices8[] = + { + {{ 0.0f, 3.0f, 0.f}, up, RED}, + {{ 2.0f, 3.0f, 0.f}, up, GREEN}, + {{ 0.0f, 0.0f, 0.f}, up, BLUE}, + + {{ 4.0, -4.0, 0.f}, up, RED}, + {{ 6.0, -4.0, 0.f}, up, BLUE}, + {{ 4.0, -7.0, 0.f}, up, GREEN}, + + {{ 4.0f, 3.0f, 0.f}, up, GREEN}, + {{ 6.0f, 0.0f, 0.f}, up, BLUE}, + {{ 4.0f, 0.0f, 0.f}, up, RED}, + + {{ 3.0f, 3.0f, 0.f}, up, GREEN}, + {{ 3.0f, 0.0f, 0.f}, up, RED}, + {{ 1.0f, 0.0f, 0.f}, up, BLUE}, + }; + const DWORD indices8[] = {0, 1, 2, 9, 10, 11, 6, 7, 8, 3, 4, 5}; + const WORD indices8_16bit[] = {0, 1, 2, 9, 10, 11, 6, 7, 8, 3, 4, 5}; + const unsigned int num_vertices8 = ARRAY_SIZE(vertices8); + const DWORD exp_adjacency8[] = {-1, 1, -1, 2, -1, 0, -1, 3, 1, 2, -1, -1}; + const DWORD point_rep8[] = {0, 1, 2, 3, 4, 5, 1, 4, 3, 1, 3, 2}; + /* All mesh data */ + ID3DXMesh *mesh = NULL; + ID3DXMesh *mesh_null_check = NULL; + unsigned int attributes[] = {0}; + struct + { + const struct vertex_pnc *vertices; + const DWORD *indices; + const DWORD num_vertices; + const DWORD *point_reps; + const DWORD *exp_adjacency; + const DWORD options; + } + tc[] = + { + { + vertices0, + indices0, + num_vertices0, + point_rep0, + exp_adjacency0, + options + }, + { + vertices1, + indices1, + num_vertices1, + point_rep1, + exp_adjacency1, + options + }, + { + vertices2, + indices2, + num_vertices2, + point_rep2, + exp_adjacency2, + options + }, + { + vertices3, + indices3, + num_vertices3, + point_rep3, + exp_adjacency3, + options + }, + { + vertices4, + indices4, + num_vertices4, + point_rep4, + exp_adjacency4, + options + }, + { + vertices5, + indices5, + num_vertices5, + point_rep5, + exp_adjacency5, + options + }, + { + vertices6, + indices6, + num_vertices6, + point_rep6, + exp_adjacency6, + options + }, + { + vertices7, + indices7, + num_vertices7, + point_rep7, + exp_adjacency7, + options + }, + { + vertices8, + indices8, + num_vertices8, + point_rep8, + exp_adjacency8, + options + }, + { + vertices8, + (DWORD*)indices8_16bit, + num_vertices8, + point_rep8, + exp_adjacency8, + options_16bit + }, + }; + DWORD *adjacency = NULL; + + test_context = new_test_context(); + if (!test_context) + { + skip("Couldn't create test context\n"); + goto cleanup; + } + + for (i = 0; i < ARRAY_SIZE(tc); i++) + { + DWORD num_faces = tc[i].num_vertices / VERTS_PER_FACE; + hr = D3DXCreateMesh(num_faces, tc[i].num_vertices, tc[i].options, declaration, + test_context->device, &mesh); + if (FAILED(hr)) + { + skip("Couldn't create mesh %d. Got %x expected D3D_OK\n", i, hr); + goto cleanup; + } + + if (i == 0) /* Save first mesh for later NULL checks */ + mesh_null_check = mesh; + + adjacency = HeapAlloc(GetProcessHeap(), 0, VERTS_PER_FACE * num_faces * sizeof(*adjacency)); + if (!adjacency) { skip("Couldn't allocate adjacency array.\n"); goto cleanup; } + + hr = mesh->lpVtbl->LockVertexBuffer(mesh, 0, &vertex_buffer); + if (FAILED(hr)) { skip("Couldn't lock vertex buffer.\n"); goto cleanup; } + memcpy(vertex_buffer, tc[i].vertices, tc[i].num_vertices * sizeof(*tc[i].vertices)); + hr = mesh->lpVtbl->UnlockVertexBuffer(mesh); + if (FAILED(hr)) { skip("Couldn't unlock vertex buffer.\n"); goto cleanup; } + + hr = mesh->lpVtbl->LockIndexBuffer(mesh, 0, &index_buffer); + if (FAILED(hr)) { skip("Couldn't lock index buffer.\n"); goto cleanup; } + if (tc[i].options & D3DXMESH_32BIT) + { + memcpy(index_buffer, tc[i].indices, VERTS_PER_FACE * num_faces * sizeof(DWORD)); + } + else + { + memcpy(index_buffer, tc[i].indices, VERTS_PER_FACE * num_faces * sizeof(WORD)); + } + hr = mesh->lpVtbl->UnlockIndexBuffer(mesh); + if (FAILED(hr)) { skip("Couldn't unlock index buffer.\n"); goto cleanup; } + + hr = mesh->lpVtbl->LockAttributeBuffer(mesh, 0, &attributes_buffer); + if (FAILED(hr)) { skip("Couldn't lock attributes buffer.\n"); goto cleanup; } + memcpy(attributes_buffer, attributes, sizeof(attributes)); + hr = mesh->lpVtbl->UnlockAttributeBuffer(mesh); + if (FAILED(hr)) { skip("Couldn't unlock attributes buffer.\n"); goto cleanup; } + + /* Convert point representation to adjacency*/ + memset(adjacency, -2, tc[i].num_vertices * sizeof(*adjacency)); + hr = mesh->lpVtbl->ConvertPointRepsToAdjacency(mesh, tc[i].point_reps, adjacency); + todo_wine ok(hr == D3D_OK, "ConvertPointRepsToAdjacency failed case %d. " + "Got %x expected D3D_OK\n", i, hr); + /* Check adjacency */ + for (j = 0; j < tc[i].num_vertices; j++) + { + todo_wine ok(adjacency[j] == tc[i].exp_adjacency[j], + "Unexpected adjacency information at (%d, %d)." + " Got %d expected %d\n", + i, j, adjacency[j], tc[i].exp_adjacency[j]); + } + + /* NULL point representation is considered identity. */ + memset(adjacency, -2, tc[i].num_vertices * sizeof(*adjacency)); + hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh, NULL, adjacency); + todo_wine ok(hr == D3D_OK, "ConvertPointRepsToAdjacency NULL point_reps. " + "Got %x expected D3D_OK\n", hr); + for (j = 0; j < tc[i].num_vertices; j++) + { + todo_wine ok(adjacency[j] == -1, + "Unexpected adjacency information (id) at (%d, %d)." + " Got %d expected %d\n", + i, j, adjacency[j], -1); + } + + HeapFree(GetProcessHeap(), 0, adjacency); + if (i != 0) /* First mesh will be freed during cleanup */ + mesh->lpVtbl->Release(mesh); + } + + /* NULL checks */ + hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh_null_check, tc[0].point_reps, NULL); + todo_wine ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL adjacency. " + "Got %x expected D3DERR_INVALIDCALL\n", hr); + hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh_null_check, NULL, NULL); + todo_wine ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL point_reps and adjacency. " + "Got %x expected D3DERR_INVALIDCALL\n", hr); + +cleanup: + if (mesh_null_check) + mesh_null_check->lpVtbl->Release(mesh_null_check); + HeapFree(GetProcessHeap(), 0, adjacency); + free_test_context(test_context); +} + START_TEST(mesh) { D3DXBoundProbeTest(); @@ -4924,4 +5375,5 @@ START_TEST(mesh) D3DXGenerateAdjacencyTest(); test_update_semantics(); test_create_skin_info(); + test_convert_point_reps_to_adjacency(); } -- 1.7.5.4
From 99165650f10b5ec00e1cb525449956421423a66b Mon Sep 17 00:00:00 2001 From: Michael Mc Donnell <mich...@mcdonnell.dk> Date: Mon, 27 Jun 2011 22:44:33 +0200 Subject: d3dx9: Implemented ConvertPointRepsToAdjacency. Faster lookup of edge_face. --- dlls/d3dx9_36/mesh.c | 161 +++++++++++++++++++++++++++++++++++++++++++- dlls/d3dx9_36/tests/mesh.c | 32 +++++----- 2 files changed, 175 insertions(+), 18 deletions(-) diff --git a/dlls/d3dx9_36/mesh.c b/dlls/d3dx9_36/mesh.c index 2807150..62df0a3 100644 --- a/dlls/d3dx9_36/mesh.c +++ b/dlls/d3dx9_36/mesh.c @@ -432,13 +432,170 @@ static HRESULT WINAPI ID3DXMeshImpl_GetAttributeTable(ID3DXMesh *iface, D3DXATTR return D3D_OK; } +struct edge_face +{ + struct list entry; + DWORD v2; + DWORD face; +}; + +struct edge_face_map +{ + struct list *lists; + struct edge_face *entries; +}; + +/* Builds up a map of which face a new edge belongs to. That way the adjacency + * of another edge can be looked up. An edge has an adjacent face if there + * is an edge going in the opposite direction in the map. For example if the + * edge (v1, v2) belongs to face 4, and there is a mapping (v2, v1)->7, then + * face 4 and 7 are adjacent. + * + * Each edge might have been replaced with another edge, or none at all. There + * is at most one edge to face mapping, i.e. an edge can only belong to one + * face. + */ +static struct edge_face_map *init_edge_face_map(CONST DWORD *index_buffer, CONST DWORD *point_reps, CONST DWORD num_faces) +{ + DWORD face, edge; + DWORD i; + struct edge_face_map *edge_face_map; + + edge_face_map = HeapAlloc(GetProcessHeap(), 0, sizeof(*edge_face_map)); + if (!edge_face_map) return NULL; + + edge_face_map->lists = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->lists)); + if (!edge_face_map->lists) return NULL; + + edge_face_map->entries = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(*edge_face_map->entries)); + if (!edge_face_map->entries) return NULL; + + /* Initialize all lists */ + for (i = 0; i < 3 * num_faces; i++) + { + list_init(&edge_face_map->lists[i]); + } + /* Build edge face mapping */ + for (face = 0; face < num_faces; face++) + { + for (edge = 0; edge < 3; edge++) + { + DWORD v1 = index_buffer[3*face + edge]; + DWORD v2 = index_buffer[3*face + (edge+1)%3]; + DWORD new_v1 = point_reps[v1]; /* What v1 has been replaced with */ + DWORD new_v2 = point_reps[v2]; + + if (v1 != v2) /* Only map non-collapsed edges */ + { + i = 3*face + edge; + edge_face_map->entries[i].v2 = new_v2; + edge_face_map->entries[i].face = face; + list_add_head(&edge_face_map->lists[new_v1], &edge_face_map->entries[i].entry); + } + } + } + + return edge_face_map; +} + +static void free_edge_face_map(struct edge_face_map *edge_face_map) +{ + if (!edge_face_map) + return; + + HeapFree(GetProcessHeap(), 0, edge_face_map->lists); + HeapFree(GetProcessHeap(), 0, edge_face_map->entries); +} + +static DWORD find_adjacent_face(struct edge_face_map *edge_face_map, DWORD vertex1, DWORD vertex2, CONST DWORD num_faces) +{ + struct edge_face *edge_face_ptr; + + LIST_FOR_EACH_ENTRY(edge_face_ptr, &edge_face_map->lists[vertex2], struct edge_face, entry) + { + if (edge_face_ptr->v2 == vertex1) + return edge_face_ptr->face; + } + + return -1; +} + static HRESULT WINAPI ID3DXMeshImpl_ConvertPointRepsToAdjacency(ID3DXMesh *iface, CONST DWORD *point_reps, DWORD *adjacency) { ID3DXMeshImpl *This = impl_from_ID3DXMesh(iface); + HRESULT hr; + DWORD num_faces = iface->lpVtbl->GetNumFaces(iface); + DWORD options = iface->lpVtbl->GetOptions(iface); + BOOL indices_are_16_bit = !(options & D3DXMESH_32BIT); + DWORD *ib = NULL; + void *ib_ptr = NULL; + DWORD face; + DWORD edge; + struct edge_face_map *edge_face_map = NULL; - FIXME("(%p)->(%p,%p): stub\n", This, point_reps, adjacency); + TRACE("(%p)->(%p,%p)\n", This, point_reps, adjacency); - return E_NOTIMPL; + if (!adjacency) return D3DERR_INVALIDCALL; + + if (!point_reps) /* Indentity point reps */ + { + memset(adjacency, -1, 3 * num_faces * sizeof(*adjacency)); + return D3D_OK; + } + + hr = iface->lpVtbl->LockIndexBuffer(iface, 0, &ib_ptr); + if (FAILED(hr)) goto cleanup; + + if (indices_are_16_bit) + { + /* Widen 16 bit to 32 bit */ + DWORD i; + WORD *ib_16bit = ib_ptr; + ib = HeapAlloc(GetProcessHeap(), 0, 3 * num_faces * sizeof(DWORD)); + if (!ib) + { + hr = E_OUTOFMEMORY; + goto cleanup; + } + for (i = 0; i < 3 * num_faces; i++) + { + ib[i] = ib_16bit[i]; + } + } + else + { + ib = ib_ptr; + } + + edge_face_map = init_edge_face_map(ib, point_reps, num_faces); + if (!edge_face_map) + { + hr = E_OUTOFMEMORY; + goto cleanup; + } + + /* Create adjacency */ + for (face = 0; face < num_faces; face++) + { + for (edge = 0; edge < 3; edge++) + { + DWORD v1 = ib[3*face + edge]; + DWORD v2 = ib[3*face + (edge+1)%3]; + DWORD new_v1 = point_reps[v1]; + DWORD new_v2 = point_reps[v2]; + DWORD adj_face; + + adj_face = find_adjacent_face(edge_face_map, new_v1, new_v2, num_faces); + adjacency[3*face + edge] = adj_face; + } + } + + hr = D3D_OK; +cleanup: + if (indices_are_16_bit) HeapFree(GetProcessHeap(), 0, ib); + free_edge_face_map(edge_face_map); + iface->lpVtbl->UnlockIndexBuffer(iface); + return hr; } static HRESULT WINAPI ID3DXMeshImpl_ConvertAdjacencyToPointReps(ID3DXMesh *iface, CONST DWORD *adjacency, DWORD *point_reps) diff --git a/dlls/d3dx9_36/tests/mesh.c b/dlls/d3dx9_36/tests/mesh.c index 1da6ed0..e94acd9 100644 --- a/dlls/d3dx9_36/tests/mesh.c +++ b/dlls/d3dx9_36/tests/mesh.c @@ -5311,28 +5311,28 @@ static void test_convert_point_reps_to_adjacency(void) /* Convert point representation to adjacency*/ memset(adjacency, -2, tc[i].num_vertices * sizeof(*adjacency)); hr = mesh->lpVtbl->ConvertPointRepsToAdjacency(mesh, tc[i].point_reps, adjacency); - todo_wine ok(hr == D3D_OK, "ConvertPointRepsToAdjacency failed case %d. " - "Got %x expected D3D_OK\n", i, hr); + ok(hr == D3D_OK, "ConvertPointRepsToAdjacency failed case %d. " + "Got %x expected D3D_OK\n", i, hr); /* Check adjacency */ for (j = 0; j < tc[i].num_vertices; j++) { - todo_wine ok(adjacency[j] == tc[i].exp_adjacency[j], - "Unexpected adjacency information at (%d, %d)." - " Got %d expected %d\n", - i, j, adjacency[j], tc[i].exp_adjacency[j]); + ok(adjacency[j] == tc[i].exp_adjacency[j], + "Unexpected adjacency information at (%d, %d)." + " Got %d expected %d\n", + i, j, adjacency[j], tc[i].exp_adjacency[j]); } /* NULL point representation is considered identity. */ memset(adjacency, -2, tc[i].num_vertices * sizeof(*adjacency)); hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh, NULL, adjacency); - todo_wine ok(hr == D3D_OK, "ConvertPointRepsToAdjacency NULL point_reps. " - "Got %x expected D3D_OK\n", hr); + ok(hr == D3D_OK, "ConvertPointRepsToAdjacency NULL point_reps. " + "Got %x expected D3D_OK\n", hr); for (j = 0; j < tc[i].num_vertices; j++) { - todo_wine ok(adjacency[j] == -1, - "Unexpected adjacency information (id) at (%d, %d)." - " Got %d expected %d\n", - i, j, adjacency[j], -1); + ok(adjacency[j] == -1, + "Unexpected adjacency information (id) at (%d, %d)." + " Got %d expected %d\n", + i, j, adjacency[j], -1); } HeapFree(GetProcessHeap(), 0, adjacency); @@ -5342,11 +5342,11 @@ static void test_convert_point_reps_to_adjacency(void) /* NULL checks */ hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh_null_check, tc[0].point_reps, NULL); - todo_wine ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL adjacency. " - "Got %x expected D3DERR_INVALIDCALL\n", hr); + ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL adjacency. " + "Got %x expected D3DERR_INVALIDCALL\n", hr); hr = mesh_null_check->lpVtbl->ConvertPointRepsToAdjacency(mesh_null_check, NULL, NULL); - todo_wine ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL point_reps and adjacency. " - "Got %x expected D3DERR_INVALIDCALL\n", hr); + ok(hr == D3DERR_INVALIDCALL, "ConvertPointRepsToAdjacency NULL point_reps and adjacency. " + "Got %x expected D3DERR_INVALIDCALL\n", hr); cleanup: if (mesh_null_check) -- 1.7.5.4