Unity Compute Shader中Marching Cubes顶点去重的线程同步问题

背景 #

• 基于Unity Compute Shader实现Marching Cubes算法，功能正常，需优化顶点去重逻辑
• 原CPU端字典去重性能不达标，转用GPU哈希查找方案
• 实现逻辑：添加顶点时先计算哈希值，通过哈希表查询顶点是否存在，附带哈希冲突检测（通过距离判断是否为同一顶点）
• 现存问题：约10%场景下仍出现重复顶点，推测是多线程并发处理同一顶点时，均检测到顶点不存在并执行添加操作
• 已尝试使用Interlocked系列同步函数，问题未解决

核心实现代码 #

#ifndef UNIQUE_LIST
#define UNIQUE_LIST
RWStructuredBuffer<int> uniqueList_metadata;
    //0 size, 1 lastIdx
RWStructuredBuffer<int> uniqueList_indexLookup;
RWStructuredBuffer<float3> uniqueList_elements;

uint Hash(float3 v)
{
// Constants for hashing
    const uint seed = 42;
    const uint c1 = 0xcc9e2d51;
    const uint c2 = 0x1b873593;

    // Convert float3 to uint3
    uint3 intV = uint3(floor(v * 100000.0f));

    // Initial hash value
    uint hash = seed;

    // Hash the x component
    uint k1 = intV.x;
    k1 *= c1;
    k1 = (k1 << 15) | (k1 >> (32 - 15)); // ROTL32(k1, 15)
    k1 *= c2;
    hash ^= k1;
    hash = (hash << 13) | (hash >> (32 - 13)); // ROTL32(hash, 13)
    hash = hash * 5 + 0xe6546b64;

    // Hash the y component
    k1 = intV.y;
    k1 *= c1;
    k1 = (k1 << 15) | (k1 >> (32 - 15));
    k1 *= c2;
    hash ^= k1;
    hash = (hash << 13) | (hash >> (32 - 13));
    hash = hash * 5 + 0xe6546b64;

    // Hash the z component
    k1 = intV.z;
    k1 *= c1;
    k1 = (k1 << 15) | (k1 >> (32 - 15));
    k1 *= c2;
    hash ^= k1;
    hash = (hash << 13) | (hash >> (32 - 13));
    hash = hash * 5 + 0xe6546b64;

    // Finalization
    hash ^= 12; // length in bytes (3 * 4 bytes)
    hash ^= hash >> 16;
    hash *= 0x85ebca6b;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35;
    hash ^= hash >> 16;

    // Ensure bitSize output by taking modulo 2^bitSize
    int mask = (1 << uniqueList_metadata[0]) - 1;
    hash = hash & mask;

    return hash;
}

uint Rehash(uint hash)
{
    hash ^= hash >> 16;
    hash *= 0x85ebca6b;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35;
    hash ^= hash >> 16;

    int mask = (1 << uniqueList_metadata[0]) - 1;
    hash = hash & mask;
    
    return hash;
}

int UniqueList_Add(float3 element)
{
    //Get the hash value of the vertex and use it to lookup the index
    uint vecHash = Hash(element);
    int thisElementIdx = uniqueList_indexLookup[vecHash];
    
    //If the returned index is -1
    if(thisElementIdx == -1)
    {
        //Then the vertex doesn't already exist in the array and it can be added  
        InterlockedAdd(uniqueList_metadata[1], 1, thisElementIdx);
        
        int tmp;
        InterlockedExchange(uniqueList_indexLookup[vecHash], thisElementIdx, tmp);
        uniqueList_elements[thisElementIdx] = element;
    }
    else
    {
        //Else, either the vertex does already exist in the array or there is a hash collision with one that does
        //Check the proximity of the found vertex, to see if it genuinly matches, or is just a hash collision
        //Rehash the vertex hash (maximum 100 times) to find either a free hash or a genuine vertex match
        int loopLimit = 100;
        float sqrDistance = 9.99;
        do
        {
            float3 existingElement = uniqueList_elements[thisElementIdx];
            float3 diff = element - existingElement;
            sqrDistance = dot(diff, diff);
        
            if (sqrDistance < 0.0001)
            {
                //Not a collision, genuine vertex match
                //Exit the loop and the current index will be returned
                break;
            }

            vecHash = Rehash(vecHash);
            thisElementIdx = uniqueList_indexLookup[vecHash];
            
            if (thisElementIdx == -1)
            {
                //A free slot in the array has been found with the new hash (which also means the current vertex doesn't exist in the array)
                //So the vertex can be added to the array
                InterlockedAdd(uniqueList_metadata[1], 1, thisElementIdx);
                
                int tmp;
                InterlockedExchange(uniqueList_indexLookup[vecHash], thisElementIdx, tmp);
                uniqueList_elements[thisElementIdx] = element;
        
                break;
            }
        
            loopLimit--;
        } while (loopLimit > 0);
    
    }
    
    return thisElementIdx;
}

#endif

问题根源与修复方案 #

核心竞态问题 #

当前代码的同步逻辑存在漏洞：检测哈希槽为空和占用槽位写入顶点是两个分离的操作，无法保证原子性。当多个线程同时处理同一顶点时：

1. 线程A读取哈希槽值为-1
2. 线程B同时读取同一哈希槽，值也为-1
3. 两者都会执行InterlockedAdd获取新索引，随后写入哈希槽和顶点数组，最终导致重复顶点

修复措施 #

1. 原子化哈希槽的检测与占用
   使用InterlockedCompareExchange替代先读后写的逻辑：只有当哈希槽当前值确实为-1时，才将新索引写入槽位，否则放弃操作，避免并发写入。
2. 冲突检测时的线程安全验证
   在冲突检测循环中，读取顶点数据后直接判断是否为同一顶点，若冲突则重新哈希查找，确保逻辑闭环。
3. 调整索引回退逻辑
   当尝试占用哈希槽失败时，回退已分配的索引计数，避免顶点数组出现空槽。

修复后的UniqueList_Add函数 #

int UniqueList_Add(float3 element)
{
    uint vecHash = Hash(element);
    int loopLimit = 100;

    while (loopLimit > 0)
    {
        int currentIdx = uniqueList_indexLookup[vecHash];
        
        // 情况1：哈希槽为空，尝试原子占用
        if (currentIdx == -1)
        {
            // 先获取新索引
            int newIdx;
            InterlockedAdd(uniqueList_metadata[1], 1, newIdx);
            
            // 原子检查并写入哈希槽：只有当槽位还是-1时才成功
            int originalIdx;
            originalIdx = InterlockedCompareExchange(uniqueList_indexLookup[vecHash], newIdx, -1);
            
            if (originalIdx == -1)
            {
                // 成功占用槽位，写入顶点
                uniqueList_elements[newIdx] = element;
                return newIdx;
            }
            else
            {
                // 被其他线程抢先占用，回退索引计数
                InterlockedAdd(uniqueList_metadata[1], -1);
                // 用被占用的索引继续检查是否是同一顶点
                currentIdx = originalIdx;
            }
        }
        
        // 情况2：哈希槽已有索引，检查是否是同一顶点
        float3 existingElement = uniqueList_elements[currentIdx];
        float3 diff = element - existingElement;
        float sqrDistance = dot(diff, diff);
        
        if (sqrDistance < 0.0001)
        {
            // 是同一顶点，返回已有索引
            return currentIdx;
        }
        
        // 哈希冲突，重新哈希继续查找
        vecHash = Rehash(vecHash);
        loopLimit--;
    }

    // 循环超时，返回无效索引（可根据需求处理）
    return -1;
}

额外优化建议 #

• 增大哈希表的大小（uniqueList_metadata[0]对应的位数），减少哈希冲突概率，降低循环次数
• 调整顶点精度阈值（0.0001），匹配你的Marching Cubes顶点生成精度，避免误判
• 确保uniqueList_elements和uniqueList_indexLookup的内存足够，防止越界写入

内容的提问来源于stack exchange，提问作者VVJ21