I’m developing an LOD algorithm Nanite’s style. Unfortunately, I’m facing a problem. The grouping algorithm, sometimes, groups clusters which aren’t near. The following image shows the effect:

I think that a group must be joined and not splitted as the image shows. The following code shows the implementation code for group algorithm:

//I use set to avoid duplicate edges
        std::unordered_map<MeshletEdge, std::unordered_set<size_t>, MeshletEdgeHasher> edges2Meshlets;
        std::unordered_map<size_t, std::unordered_set<MeshletEdge, MeshletEdgeHasher>> meshlets2Edges;
        for(size_t meshletIndex = 0; meshletIndex < currentLod.lodVerticesMeshlets.size(); meshletIndex++) 
        {
            const auto& meshlet = currentLod.lodVerticesMeshlets[meshletIndex];
            
            auto getVertexIndex = [&](size_t index) 
            {
                size_t indexVertex = currentLod.lodMeshletsClusterIndex[currentLod.lodMeshletsClusterTriangle
                [index + meshlet.meshletData.triangle_offset] + meshlet.meshletData.vertex_offset];
                return indexVertex;
            };

            const size_t triangleCount = meshlet.meshletData.triangle_count * 3;
            // for each triangle of the meshlet
            for(size_t triangleIndex = 0; triangleIndex < triangleCount; triangleIndex+=3) 
            {
                // for each edge of the triangle
                for(size_t i = 0; i < 3; i++) 
                {
                    MeshletEdge edge { getVertexIndex(i + triangleIndex), 
                    getVertexIndex(((i+1) % 3) + triangleIndex) };
                    if(edge.first != edge.second) 
                    {
                        edges2Meshlets[edge].insert(meshletIndex);
                        meshlets2Edges[meshletIndex].insert(edge);
                    }
                }
            }
        }

        std::erase_if(edges2Meshlets, [&](const auto& pair) 
        {
            return pair.second.size() <= 1;
        });

        if(edges2Meshlets.empty()) 
        {
            return groupWithAllMeshlets();
        }
        
        // vertex count, from the point of view of METIS, where Meshlet = graph vertex
        idx_t vertexCount = static_cast<idx_t>(currentLod.lodVerticesMeshlets.size());
        // only one constraint, minimum required by METIS
        idx_t ncon = 1; 
        idx_t nparts = static_cast<idx_t>(currentLod.lodVerticesMeshlets.size() / groupNumber);        idx_t options[METIS_NOPTIONS];
        METIS_SetDefaultOptions(options);
        options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
         // identify connected components first
        options[METIS_OPTION_CCORDER] = 1;
        std::vector<idx_t> partition;
        partition.resize(vertexCount);

        // xadj
        std::vector<idx_t> xadjacency;
        xadjacency.reserve(vertexCount + 1);

        // adjncy
        std::vector<idx_t> edgeAdjacency;
        // weight of each edge
        std::vector<idx_t> edgeWeights;

        for(size_t meshletIndex = 0; meshletIndex < currentLod.lodVerticesMeshlets.size(); meshletIndex++) 
        {
            size_t startIndexInEdgeAdjacency = edgeAdjacency.size();
            for(const auto& edge : meshlets2Edges[meshletIndex]) 
            {
                auto connectionsIter = edges2Meshlets.find(edge);
                if(connectionsIter == edges2Meshlets.end()) //Not find
                {
                    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()) //Not find
                        {
                            // first time we see this connection to the other meshlet
                            edgeAdjacency.emplace_back(connectedMeshlet);
                            edgeWeights.emplace_back(1);
                        } 
                        else 
                        {
                            // not the first time! increase number of times we encountered this meshlet
                            //std::distance returns the number of jumps from first to last.
                            ptrdiff_t d = std::distance(edgeAdjacency.begin(), existingEdgeIter);
                            assert(d >= 0);
                            assert(d < edgeWeights.size());
                            edgeWeights[d]++;
                        }
                    }
                }
            }
            xadjacency.push_back(static_cast<idx_t>(startIndexInEdgeAdjacency));
        }
        
        xadjacency.push_back(static_cast<idx_t>(edgeAdjacency.size()));
        assert(xadjacency.size() == currentLod.lodVerticesMeshlets.size() + 1);
        assert(edgeAdjacency.size() == edgeWeights.size());
        idx_t edgeCut; // final cost of the cut found by METIS
        int result = METIS_PartGraphKway(&vertexCount,
                                            &ncon,
                                            xadjacency.data(),
                                            edgeAdjacency.data(),
                                            nullptr, 
                                            nullptr, 
                                            edgeWeights.data(),
                                            &nparts,
                                            nullptr,
                                            nullptr,
                                            options,
                                            &edgeCut,
                                            partition.data()
                            );
        assert(result == METIS_OK);
        currentLod.groups.resize(nparts);

Where am I going wrong?