in DirectXMesh/DirectXMeshAdjacency.cpp [336:620]
HRESULT ConvertPointRepsToAdjacencyImpl(
_In_reads_(nFaces * 3) const index_t* indices, size_t nFaces,
_In_reads_(nVerts) const XMFLOAT3* positions, size_t nVerts,
_In_reads_(nVerts) const uint32_t* pointRep,
_Out_writes_(nFaces * 3) uint32_t* adjacency) noexcept
{
auto hashSize = std::max<size_t>(nVerts / 3, 1);
std::unique_ptr<edgeHashEntry*[]> hashTable(new (std::nothrow) edgeHashEntry*[hashSize]);
if (!hashTable)
return E_OUTOFMEMORY;
memset(hashTable.get(), 0, sizeof(edgeHashEntry*) * hashSize);
std::unique_ptr<edgeHashEntry[]> hashEntries(new (std::nothrow) edgeHashEntry[3 * nFaces]);
if (!hashEntries)
return E_OUTOFMEMORY;
uint32_t freeEntry = 0;
// add face edges to hash table and validate indices
for (size_t face = 0; face < nFaces; ++face)
{
index_t i0 = indices[face * 3];
index_t i1 = indices[face * 3 + 1];
index_t i2 = indices[face * 3 + 2];
if (i0 == index_t(-1)
|| i1 == index_t(-1)
|| i2 == index_t(-1))
continue;
if (i0 >= nVerts
|| i1 >= nVerts
|| i2 >= nVerts)
return E_UNEXPECTED;
uint32_t v1 = pointRep[i0];
uint32_t v2 = pointRep[i1];
uint32_t v3 = pointRep[i2];
// filter out degenerate triangles
if (v1 == v2 || v1 == v3 || v2 == v3)
continue;
for (uint32_t point = 0; point < 3; ++point)
{
uint32_t va = pointRep[indices[face * 3 + point]];
uint32_t vb = pointRep[indices[face * 3 + ((point + 1) % 3)]];
uint32_t vOther = pointRep[indices[face * 3 + ((point + 2) % 3)]];
uint32_t hashKey = va % hashSize;
assert(freeEntry < (3 * nFaces));
_Analysis_assume_(freeEntry < (3 * nFaces));
auto newEntry = &hashEntries[freeEntry];
++freeEntry;
newEntry->v1 = va;
newEntry->v2 = vb;
newEntry->vOther = vOther;
newEntry->face = uint32_t(face);
newEntry->next = hashTable[hashKey];
hashTable[hashKey] = newEntry;
}
}
assert(freeEntry <= (3 * nFaces));
memset(adjacency, 0xff, sizeof(uint32_t) * nFaces * 3);
for (size_t face = 0; face < nFaces; ++face)
{
index_t i0 = indices[face * 3];
index_t i1 = indices[face * 3 + 1];
index_t i2 = indices[face * 3 + 2];
// filter out unused triangles
if (i0 == index_t(-1)
|| i1 == index_t(-1)
|| i2 == index_t(-1))
continue;
assert(i0 < nVerts);
assert(i1 < nVerts);
assert(i2 < nVerts);
_Analysis_assume_(i0 < nVerts);
_Analysis_assume_(i1 < nVerts);
_Analysis_assume_(i2 < nVerts);
uint32_t v1 = pointRep[i0];
uint32_t v2 = pointRep[i1];
uint32_t v3 = pointRep[i2];
// filter out degenerate triangles
if (v1 == v2 || v1 == v3 || v2 == v3)
continue;
for (uint32_t point = 0; point < 3; ++point)
{
if (adjacency[face * 3 + point] != UNUSED32)
continue;
// see if edge already entered, if not then enter it
uint32_t va = pointRep[indices[face * 3 + ((point + 1) % 3)]];
uint32_t vb = pointRep[indices[face * 3 + point]];
uint32_t vOther = pointRep[indices[face * 3 + ((point + 2) % 3)]];
uint32_t hashKey = va % hashSize;
edgeHashEntry* current = hashTable[hashKey];
edgeHashEntry* prev = nullptr;
uint32_t foundFace = UNUSED32;
while (current != nullptr)
{
if ((current->v2 == vb) && (current->v1 == va))
{
foundFace = current->face;
break;
}
prev = current;
current = current->next;
}
edgeHashEntry* found = current;
edgeHashEntry* foundPrev = prev;
float bestDiff = -2.f;
// Scan for additional matches
if (current)
{
prev = current;
current = current->next;
// find 'better' match
while (current != nullptr)
{
if ((current->v2 == vb) && (current->v1 == va))
{
XMVECTOR pB1 = XMLoadFloat3(&positions[vb]);
XMVECTOR pB2 = XMLoadFloat3(&positions[va]);
XMVECTOR pB3 = XMLoadFloat3(&positions[vOther]);
XMVECTOR v12 = XMVectorSubtract(pB1, pB2);
XMVECTOR v13 = XMVectorSubtract(pB1, pB3);
XMVECTOR bnormal = XMVector3Normalize(XMVector3Cross(v12, v13));
if (bestDiff == -2.f)
{
XMVECTOR pA1 = XMLoadFloat3(&positions[found->v1]);
XMVECTOR pA2 = XMLoadFloat3(&positions[found->v2]);
XMVECTOR pA3 = XMLoadFloat3(&positions[found->vOther]);
v12 = XMVectorSubtract(pA1, pA2);
v13 = XMVectorSubtract(pA1, pA3);
XMVECTOR anormal = XMVector3Normalize(XMVector3Cross(v12, v13));
bestDiff = XMVectorGetX(XMVector3Dot(anormal, bnormal));
}
XMVECTOR pA1 = XMLoadFloat3(&positions[current->v1]);
XMVECTOR pA2 = XMLoadFloat3(&positions[current->v2]);
XMVECTOR pA3 = XMLoadFloat3(&positions[current->vOther]);
v12 = XMVectorSubtract(pA1, pA2);
v13 = XMVectorSubtract(pA1, pA3);
XMVECTOR anormal = XMVector3Normalize(XMVector3Cross(v12, v13));
float diff = XMVectorGetX(XMVector3Dot(anormal, bnormal));
// if face normals are closer, use new match
if (diff > bestDiff)
{
found = current;
foundPrev = prev;
foundFace = current->face;
bestDiff = diff;
}
}
prev = current;
current = current->next;
}
}
if (foundFace != UNUSED32)
{
assert(found != nullptr);
// remove found face from hash table
if (foundPrev != nullptr)
{
foundPrev->next = found->next;
}
else
{
hashTable[hashKey] = found->next;
}
assert(adjacency[face * 3 + point] == UNUSED32);
adjacency[face * 3 + point] = foundFace;
// Check for other edge
uint32_t hashKey2 = vb % hashSize;
current = hashTable[hashKey2];
prev = nullptr;
while (current != nullptr)
{
if ((current->face == uint32_t(face)) && (current->v2 == va) && (current->v1 == vb))
{
// trim edge from hash table
if (prev != nullptr)
{
prev->next = current->next;
}
else
{
hashTable[hashKey2] = current->next;
}
break;
}
prev = current;
current = current->next;
}
// mark neighbor to point back
bool linked = false;
for (uint32_t point2 = 0; point2 < point; ++point2)
{
if (foundFace == adjacency[face * 3 + point2])
{
linked = true;
adjacency[face * 3 + point] = UNUSED32;
break;
}
}
if (!linked)
{
uint32_t point2 = 0;
for (; point2 < 3; ++point2)
{
index_t k = indices[foundFace * 3 + point2];
if (k == index_t(-1))
continue;
assert(k < nVerts);
_Analysis_assume_(k < nVerts);
if (pointRep[k] == va)
break;
}
if (point2 < 3)
{
#ifndef NDEBUG
uint32_t testPoint = indices[foundFace * 3 + ((point2 + 1) % 3)];
testPoint = pointRep[testPoint];
assert(testPoint == vb);
#endif
assert(adjacency[foundFace * 3 + point2] == UNUSED32);
// update neighbor to point back to this face match edge
adjacency[foundFace * 3 + point2] = uint32_t(face);
}
}
}
}
}
return S_OK;
}