in DirectXMesh/DirectXMeshletGenerator.cpp [240:448]
HRESULT Meshletize(
size_t maxVerts,
size_t maxPrims,
_In_reads_(nFaces * 3) const T* indices,
size_t nFaces,
_In_reads_(nVerts) const XMFLOAT3* positions,
size_t nVerts,
const std::pair<size_t, size_t>& subset,
_In_reads_(nFaces * 3) const uint32_t* adjacency,
std::vector<InlineMeshlet<T>>& meshlets)
{
if (!indices || !positions || !adjacency)
return E_INVALIDARG;
if (subset.first + subset.second > nFaces)
return E_UNEXPECTED;
meshlets.clear();
// Bitmask of all triangles in mesh to determine whether a specific one has been added
std::vector<bool> checklist;
checklist.resize(subset.second);
// Cache to maintain scores for each candidate triangle
std::vector<std::pair<uint32_t, float>> candidates;
std::unordered_set<uint32_t> candidateCheck;
// Positions and normals of the current primitive
std::vector<XMFLOAT3> vertices;
std::vector<XMFLOAT3> normals;
// Seed the candidate list with the first triangle of the subset
const uint32_t startIndex = static_cast<uint32_t>(subset.first);
const uint32_t endIndex = static_cast<uint32_t>(subset.first + subset.second);
uint32_t triIndex = static_cast<uint32_t>(subset.first);
candidates.push_back(std::make_pair(triIndex, 0.0f));
candidateCheck.insert(triIndex);
// Continue adding triangles until triangle list is exhausted.
InlineMeshlet<T>* curr = nullptr;
while (!candidates.empty())
{
uint32_t index = candidates.back().first;
candidates.pop_back();
T tri[3] =
{
indices[index * 3],
indices[index * 3 + 1],
indices[index * 3 + 2],
};
if (tri[0] >= nVerts ||
tri[1] >= nVerts ||
tri[2] >= nVerts)
{
return E_UNEXPECTED;
}
// Create a new meshlet if necessary
if (curr == nullptr)
{
vertices.clear();
normals.clear();
meshlets.emplace_back();
curr = &meshlets.back();
}
// Try to add triangle to meshlet
if (TryAddToMeshlet(maxVerts, maxPrims, tri, *curr))
{
// Success! Mark as added.
checklist[index - startIndex] = true;
// Add positions & normal to list
XMFLOAT3 points[3] =
{
positions[tri[0]],
positions[tri[1]],
positions[tri[2]],
};
vertices.push_back(points[0]);
vertices.push_back(points[1]);
vertices.push_back(points[2]);
normals.emplace_back();
XMStoreFloat3(&normals.back(), ComputeNormal(points));
// Compute new bounding sphere & normal axis
BoundingSphere positionBounds, normalBounds;
BoundingSphere::CreateFromPoints(positionBounds, vertices.size(), vertices.data(), sizeof(XMFLOAT3));
BoundingSphere::CreateFromPoints(normalBounds, normals.size(), normals.data(), sizeof(XMFLOAT3));
XMVECTOR psphere = XMLoadFloat4(reinterpret_cast<XMFLOAT4*>(&positionBounds));
XMVECTOR normal = XMVector3Normalize(XMLoadFloat4(reinterpret_cast<XMFLOAT4*>(&normalBounds)));
// Find and add all applicable adjacent triangles to candidate list
const uint32_t adjIndex = index * 3;
uint32_t adj[3] =
{
adjacency[adjIndex],
adjacency[adjIndex + 1],
adjacency[adjIndex + 2],
};
for (size_t i = 0; i < 3u; ++i)
{
// Invalid triangle in adjacency slot
if (adj[i] == uint32_t(-1))
continue;
// Primitive is outside the subset
if (adj[i] < subset.first || adj[i] > endIndex)
continue;
// Already processed triangle
if (checklist[adj[i] - startIndex])
continue;
// Triangle already in the candidate list
if (candidateCheck.count(adj[i]))
continue;
candidates.push_back(std::make_pair(adj[i], FLT_MAX));
candidateCheck.insert(adj[i]);
}
// Re-score remaining candidate triangles
for (size_t i = 0; i < candidates.size(); ++i)
{
uint32_t candidate = candidates[i].first;
T triIndices[3] =
{
indices[candidate * 3],
indices[candidate * 3 + 1],
indices[candidate * 3 + 2],
};
if (triIndices[0] >= nVerts ||
triIndices[1] >= nVerts ||
triIndices[2] >= nVerts)
{
return E_UNEXPECTED;
}
XMFLOAT3 triVerts[3] =
{
positions[triIndices[0]],
positions[triIndices[1]],
positions[triIndices[2]],
};
candidates[i].second = ComputeScore(*curr, psphere, normal, triIndices, triVerts);
}
// Determine whether we need to move to the next meshlet.
if (IsMeshletFull(maxVerts, maxPrims, *curr))
{
candidateCheck.clear();
curr = nullptr;
// Discard candidates - one of our existing candidates as the next meshlet seed.
if (!candidates.empty())
{
candidates[0] = candidates.back();
candidates.resize(1);
candidateCheck.insert(candidates[0].first);
}
}
else
{
// Sort in reverse order to use vector as a queue with pop_back
std::stable_sort(candidates.begin(), candidates.end(), [](auto& a, auto& b) { return a.second > b.second; });
}
}
else
{
// Ran out of candidates while attempting to fill the last bits of a meshlet.
if (candidates.empty())
{
candidateCheck.clear();
curr = nullptr;
}
}
// Ran out of candidates; add a new seed candidate to start the next meshlet.
if (candidates.empty())
{
while (triIndex < endIndex && checklist[triIndex - startIndex])
++triIndex;
if (triIndex == endIndex)
break;
candidates.push_back(std::make_pair(triIndex, 0.0f));
candidateCheck.insert(triIndex);
}
}
return S_OK;
}