I have been developing an LOD algorithm similar to Nanite's style. I have been developing the algorithm using Vulkan. However, I encountered problems with LOD selection. It seems that the algorithm doesn't select some clusters, causing holes during the LOD selection process. Below is an image that shows these strange effects:

I'm using meshoptimizer to create meshlets and simplify my mesh, and the METIS library to group my meshlets. The error is stored per group and calculated as the sum of the errors of the meshlets within the group. I sum the group error of the current LOD with the maximum group error of the previous LOD to ensure that the child error is less than the parent error. I'm sure that the error function is monotonically increasing.

Where am I going wrong?

Many thanks

giuseppe7 said:
I have been developing the algorithm using Vulkan.

It might be worth to have a reference implementation on CPU as well, which is easy to debug.

Once it works, porting to GPU is much easier than ‘developing on GPU’.

@JoeJ I implemented the LOD algorithm on the CPU but using: meshoptmizer, METIS and Vulkan API. Following the implementation code of LOD selection:

std::vector<uint32_t> LODSelectionDispatcher::LodSelector(std::vector<MeshletGroup>& totalGroups,
                                                          const glm::mat4& modelViewMatrix, int width, float hFov,
                                                          const LOD& lastLOD, const glm::vec3& instancePos,
                                                          float& avgLOD, std::vector<MINERVA_VERTEX>& vertexBuffer) {
    float distanceMul = 2.0f;
    errorThreshold    = 1.0f;
    std::unordered_set<idx_t> groupsSelected;
    std::vector<uint32_t> newIndexBuffer;
    std::vector<MeshletGroup> tempTotal = totalGroups;
    for (auto& group : tempTotal) {
        MeshletGroup parentGroup = group;
        float parentGroupError   = 0.0f;

        float currentGroupError = ComputeScreenSpaceError(group.groupBound, modelViewMatrix, group.groupError, width,
                                                          hFov, instancePos, distanceMul);

        if (group.parentsGroup.size() <= 0) {
            parentGroupError = errorThreshold + 0.1f;
            if (currentGroupError <= errorThreshold && parentGroupError > errorThreshold && !group.isSelected) {
                group.isSelected = true;
                groupsSelected.insert(group.groupID);
            }
            continue;
        }

        for (int i = 0; i < group.parentsGroup.size(); i++) {
            parentGroup = tempTotal[group.parentsGroup[i]];
            assert(group.groupBound.radius > 0 && parentGroup.groupBound.radius > 0);
            assert(group.groupError < parentGroup.groupError);
            parentGroupError = ComputeScreenSpaceError(parentGroup.groupBound, modelViewMatrix, parentGroup.groupError,
                                                       width, hFov, instancePos, distanceMul);
            if (currentGroupError <= errorThreshold && parentGroupError > errorThreshold && !group.isSelected) {
                for (int i = 0; i < group.parentsGroup.size(); i++) {
                    MeshletGroup* parent = &tempTotal[group.parentsGroup[i]];
                    parent->isSelected   = true;
                }
                groupsSelected.insert(group.groupID);
            }
        }
    }
    // CPU side
    for (auto group : groupsSelected) {
        MeshletGroup* currentGroup = &totalGroups[group];
        avgLOD += currentGroup->lod;
        newIndexBuffer.insert(newIndexBuffer.end(), currentGroup->localGroupIndexBuffer.begin(),
                              currentGroup->localGroupIndexBuffer.end());

        vertexBuffer.insert(vertexBuffer.end(), currentGroup->localGroupVertexBuffer.begin(),
                            currentGroup->localGroupVertexBuffer.end());
    }
    avgLOD /= groupsSelected.size();
    if (newIndexBuffer.size() <= 0) {
        avgLOD         = -1.0f;
        newIndexBuffer = lastLOD.lodIndexBuffer;
    }
    currentAvgLOD = avgLOD;

    return newIndexBuffer;
}

float LODSelectionDispatcher::ComputeScreenSpaceError(PhoenixBound bound, const glm::mat4& modelViewMatrix,
                                                      float groupError, int width, float hFov,
                                                      const glm::vec3& instancePos, float distanceMul) {
    bound.center += instancePos;
    // Bound center in View space
    glm::vec4 distanceFromCamera = modelViewMatrix * glm::vec4{bound.center, 1.0f};
    float d                      = glm::length(distanceFromCamera);
    float screenSpaceError       = (groupError * static_cast<float>(width)) / (distanceMul * d * tan(hFov / 2.0f));
    return screenSpaceError;
}

This seems like the problem:

    // Bound center in View space
    glm::vec4 distanceFromCamera = modelViewMatrix * glm::vec4{bound.center, 1.0f};
    float d                      = glm::length(distanceFromCamera);

You are including the W component of the distanceFromCamera vector in the length calculation. The W component is probably 1, which will throw off your length calculation. You should only use the XYZ components in calculating the length.

@Aressera Hey

I change the code following your advice but I have still problems. It seems to choose the parent and the child at the same moment. So, in this way I have two LOD overlap as shown by this image:

I start thinking that the problem is how I create the parent-child relationship. In my code a child is linked to a parent if the meshlets “created” by the child is grouped to a parent. I use a std::map to link the meshlet ID to child group ID.

currentLod.lodVerticesMeshlets[i].meshletID = static_cast<idx_t>(i);
            if(prevLod)
            {
                //Meshlets generated by the child group
                prevLod->meshletToGroup.insert({currentLod.lodVerticesMeshlets[i].meshletID, groupID});
            }  

Then, when I group the mehlet, I use the meshlet ID to get back the child group and I create the relationship between parent and child:

//I'm binding the parent group with child one
                if(prevLod)
                {
                    /*I obtain the child group ID by using the ID of the meshlet, which is created from the simplified                         index of the child group.*/
                    idx_t oldGroupID = prevLod->meshletToGroup[meshlet.meshletID];
                    MeshletGroup* oldGroup = &totalGroups[oldGroupID];
                   
                    //I want avoid repeated values
                    if(std::find(oldGroup->parentsGroup.begin(), oldGroup->parentsGroup.end(), group->groupID)                        ==  oldGroup->parentsGroup.end())
                    {
                        //The new group is the parent of the old group
                        oldGroup->parentsGroup.emplace_back(group->groupID);    
                    }
                }

Where am I going wrong?

giuseppe7 said:
Where am I going wrong?

Idk, but the most confusing detail about Nanite to me is that it's not a tree, but a directed acyclic graph. Meaning a child can have multiple parents. Maybe that's related to the issue.

@JoeJ In my case the child can have multiple parents (I use a std::vector to store them), and furthermore the error between the child and the parent is monotonically increasing (childError < parentError) as the Epic's paper suggest. So I don't know were is the problem. In addition during the LOD selection also some holes are formed

Maybe the problem is that I create the DAG using the group of clusters and not using the clusters itself. I saw that some implementations of Nanite's style lod algoritm create the DAG using the clusters, so in this case the DAG's node is a cluster, in my implementation the DAG's node is a group of clusters. However, I think that my version should be better for two reason

1. In Nanite the LOD selection is made per-group and not per-cluster. This is done to avoid cracks between different LODs.
2. Create a DAG using group of cluster make more simpler the creation of parent-child relationship

I've used progressive lod only with storing clusters directly in nodes, not groups of clusters.

I'm not sure how do you want to work with group of clusters there (or how that works in general) - the problem with DAG for LOD is that once you include single child of a parent - you have to exclude ALL parents and include all children (you can't mix this, because that would result in duplicate geometry) within given sub-graph.