GroupMeshlets()

std::vector< MeshletGroup > Spices::MeshProcessor::GroupMeshlets ( MeshPack * meshPack, std::vector< Meshlet > & meshlets )

staticprivate

Split Meshlets to Groups.

Parameters

[in]	meshPack	MeshPack.
[in]	meshlets	MeshPack Meshlets.

Returns

Returns Groups.

Return one group with all meshlets.

Return if less than 8 meshlets.

xadj.

adjncy. Stores Meshlets Index.

Connect meshlets Count of each meshlet.

Skip if edge is internal edge.

Iter connected edge's meshlets.

Get a connect other meshlet.

Split Meshlets to Part.

Return groups.

Return one group with all meshlets.

Return if less than 8 meshlets.

xadj.

adjncy. Stores Meshlets Index.

Connect meshlets Count of each meshlet.

Skip if edge is internal edge.

Iter connected edge's meshlets.

Get a connect other meshlet.

Split Meshlets to Part.

Return groups.

Definition at line 317 of file MeshProcessor.cpp.

    {
        SPICES_PROFILE_ZONE;
 
        auto groupWithMeshlets = [&]() 
        {
            MeshletGroup group;
            for (int i = 0; i < meshlets.size(); ++i)
            {
                group.meshlets.push_back(i);
            }
            return std::vector{ group };
        };
 
        if (meshlets.size() < 8)
        {
            return groupWithMeshlets();
        }
 
        std::unordered_map<Edge, std::set<size_t>> edges2Meshlets;
        std::unordered_map<size_t, std::vector<Edge>> meshlets2Edges;
 
        for (size_t meshletIndex = 0; meshletIndex < meshlets.size(); meshletIndex++)
        {
            const auto& meshlet = meshlets[meshletIndex];
 
            for (size_t triangleIndex = 0; triangleIndex < meshlet.nPrimitives; triangleIndex++)
            {
                const glm::uvec3& primPts = (*meshPack->m_MeshResource.primitivePoints.attributes)[meshlet.primitiveOffset + triangleIndex];
 
                Edge edge0{ primPts.x , primPts.y };
                Edge edge1{ primPts.y , primPts.z };
                Edge edge2{ primPts.z , primPts.x };
 
                edges2Meshlets[edge0].insert(meshletIndex);
                edges2Meshlets[edge1].insert(meshletIndex);
                edges2Meshlets[edge2].insert(meshletIndex);
 
                meshlets2Edges[meshletIndex].push_back(edge0);
                meshlets2Edges[meshletIndex].push_back(edge1);
                meshlets2Edges[meshletIndex].push_back(edge2);
            }
        }
 
        /*
        * @brief remove internal edge.
        */
        for (auto first = edges2Meshlets.begin(), last = edges2Meshlets.end(); first != last;)
        {
            if ((*first).second.size() <= 1)
            {
                first = edges2Meshlets.erase(first);
            }
            else
            {
                ++first;
            }
        }
 
        /*
        * @brief return if no connected edge.
        */
        if (edges2Meshlets.empty())
        {
            return groupWithMeshlets();
        }
 
        idx_t vertexCount   = meshlets.size();
        idx_t ncon          = 1;
        idx_t nparts        = meshlets.size() / 4;
        assert(nparts > 1);
 
        idx_t options[METIS_NOPTIONS];
        METIS_SetDefaultOptions(options);
 
        options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
        options[METIS_OPTION_CCORDER] = 1;
 
        std::vector<idx_t> partition;
        partition.resize(vertexCount);
 
        std::vector<idx_t> xadjacency;
        xadjacency.reserve(vertexCount + 1);
 
        std::vector<idx_t> edgeAdjacency;
 
        std::vector<idx_t> edgeWeights;
 
        for (size_t meshletIndex = 0; meshletIndex < meshlets.size(); meshletIndex++)
        {
            size_t startIndexInEdgeAdjacency = edgeAdjacency.size();
            for (const auto& edge : meshlets2Edges[meshletIndex])
            {
                auto connectionsIter = edges2Meshlets.find(edge);
                if (connectionsIter == edges2Meshlets.end())
                {
                    continue;
                }
 
                const auto& connections = connectionsIter->second;
                for (const auto& connectedMeshlet : connections)
                {
                    if (connectedMeshlet != meshletIndex)
                    {
                        auto existingEdgeIter = std::find(edgeAdjacency.begin() + startIndexInEdgeAdjacency, edgeAdjacency.end(), connectedMeshlet);
                        if (existingEdgeIter == edgeAdjacency.end())
                        {
                            edgeAdjacency.emplace_back(connectedMeshlet);
                            edgeWeights.emplace_back(1);
                        }
                        else
                        {
                            std::ptrdiff_t d = std::distance(edgeAdjacency.begin(), existingEdgeIter);
                            assert(d >= 0 && d < edgeWeights.size());
                            edgeWeights[d]++;
                        }
                    }
                }
            }
            xadjacency.push_back(startIndexInEdgeAdjacency);
        }
        xadjacency.push_back(edgeAdjacency.size());
 
        assert(xadjacency.size() == meshlets.size() + 1);
        assert(edgeAdjacency.size() == edgeWeights.size());
 
        idx_t edgeCut;
        int result = METIS_PartGraphKway(
            &vertexCount,
            &ncon,
            xadjacency.data(),
            edgeAdjacency.data(),
            nullptr, /* vertex weights */
            nullptr, /* vertex size */
            edgeWeights.data(),
            &nparts,
            nullptr,
            nullptr,
            options,
            &edgeCut,
            partition.data()
        );
 
        assert(result == METIS_OK);
 
        std::vector<MeshletGroup> groups;
        groups.resize(nparts);
        for (size_t i = 0; i < meshlets.size(); i++)
        {
            idx_t partitionNumber = partition[i];
            groups[partitionNumber].meshlets.push_back(i);
        }
 
        return groups;
    }