<p>I have a triangular mesh with common vertices (VBO and EBO/IBO) that contain the normal vectors.
If I tessellate this mesh, the subdivision of the triangle edges of neighboring triangles has the same tessellation level. (The mesh therefore has no holes).</p>
<p>Each partial triangle created by the tessellation performs a normal calculation in the geometry shader, which results in flat shading. The individual triangles are therefore visible.</p>
<p>To avoid this flat shading and also to carry out some transformations afterwards, I decided to save the generated vertices in an SSBO buffer. The indices of the individual triangles are also saved in another SSBO buffer.</p>
<p>To avoid duplicates within the vbo SSBO, I try to hash the vertices according to their position.</p>
<p>But that doesn't seem to work properly. If you look at Figure 1, you can see the edge of two neighboring triangles that are tessellated. On the left side, some parts of the edge are &quot;blurred&quot;, these are the parts that work correctly. The vertices that meet at this point share their normal vector, the normal is interpolated, resulting in this blurred edge. At the other points of the edge, my hashing did not work. I saved the generated positions in a file to see where the problem is. Within the VBO-SSBO, each vertex position should be unique! But they are not! All vertices within the same triangle patch are unique, but on the edges where two triangle patches share the same edge, I get duplicates.</p>
<p>The exact same vertex position of two vertices therefore results in two different hash keys. So my problem seems to be the hash key generation.</p>
<p><a href="https://i.sstatic.net/LMGmQ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LMGmQ.png" alt="enter image description here" /></a></p>
<p><strong>This code generates the Hashkey:</strong></p>
<pre><code>// 32 bit Murmur3 hash
uint HASH_hashKey(uint key)
{
    uint HASH_TABLE_CAPACITY = 64 * 1024 * 1024;
    key ^= key &gt;&gt; 16;
    key *= 0x85ebca6b;
    key ^= key &gt;&gt; 13;
    key *= 0xc2b2ae35;
    key ^= key &gt;&gt; 16;
    return key &amp; (HASH_TABLE_CAPACITY - 1);
}

//generates a hash key (uint) depending on the mantissa of the 3D position. This hash key is NOT unique!! because the uint has not enough bits.
uint HASH_uvec3ToHash(uvec3 vector)
{
    return (vector.x &amp; 0x7ff) | ((vector.y &amp; 0x7ff) &lt;&lt; 11) | ((vector.z &amp; 0x3ff) &lt;&lt; 22);
}

//creates or returns a slot for the given vertex position(key) reinterpretes as an uvec3.
//uvec4 HashKeyValue[] is the hash table HashKeyValue[].xyz: vertexPosition (reinterpreted)
uint HASH_getHashSlot(uvec3 key)
{
    //key = uvec3(key.x | 1, key.y | 1, key.z | 1);
    uint HASH_TABLE_CAPACITY = 64 * 1024 * 1024;
    uint slot = HASH_hashKey(HASH_uvec3ToHash(key));
    uint empty = 0xffffffff;
    while (true)
    {
        uint prevX = atomicCompSwap(HashKeyValue[slot].x, empty, key.x);
        if (prevX == empty || prevX == key.x)
        {
            uint prevY = atomicCompSwap(HashKeyValue[slot].y, empty, key.y);
            if (prevY == empty || prevY == key.y)
            {
                uint prevZ = atomicCompSwap(HashKeyValue[slot].z, empty, key.z);
                if (prevZ == empty || prevZ == key.z)
                {
                    return slot;
                }
            }
        }
        slot = (slot + 1) &amp; (HASH_TABLE_CAPACITY - 1);
    }
}
</code></pre>
<p>The parameter &quot;key&quot; is the position of the vertex, reinterpreted as an unsigned integer (to be able to use atomic functions).</p>
<p><strong>The idea behind the code:</strong></p>
<p><code>uint slot = HASH_hashKey(HASH_uvec3ToHash(key));</code> This line should point to a slot in the hash table that depends on the vertex position. However, it is possible that different positions receive the same value. For this reason, we then perform an x, y and z test. It is important to say that we do not delete any vertices so that we can iterate from the 'slot' position until we find a free hash slot. This is done in the <code>while (true)</code> loop:</p>
<p>Here we first test whether the x-value of the slot is empty and atomicCompSwap the new x-position.
The atomicCompSwap command returns the original value. This can be <code>empty 0xffffffffff</code> or the x-position we are looking for =&gt; we move on to the next test. Otherwise, this slot is used by another vertex with a different position, which was hashed here.
The same happens with <code>y</code> and <code>z</code>. If all three conditions are true (x, y, z), then we have found the perfect hashing slot. Otherwise, we check the next slot.</p>
<p>Somewhere here must be my mistake, because the VBO-SSBO output has duplicates generated by different hash slots.</p>
<p><strong>EDIT:</strong> Tessellation takes place in ModelSpace, so that rotating the camera has no influence on the hash. Only race conditions can affect the hash slot if multiple positions refer to the same slot in the first hash. The bug is not flickering... so every frame is identical. therefore the same positions cause the same mismatch.</p>
<p>For those who are interested in the way the normals are calculated:</p>
<p>Each normal is multiplied by 1000 and saved as an integer. An atomicAdd function adds up all normals and during rendering it is converted to float and normalized.</p>

CC BY-SA 4.0
2024-01-20T13:29:31.240Z
The entire point of a hashing algorithm is to produce the same output for a given input. So either the hash algorithm isn't behaving correctly (unlikely) or the inputs are different, (more likely) or the hash table is broken (less likely).  So it seems like the most likely issue is the keys have small differences and my suggestion would be to zero the low? high? ( I can never remember) bits of the mantissa after converting the float to an int. So that values like 1.23456 and 1.23457 become 1.2345.
pmw1234
CC BY-SA 4.0
2024-01-22T13:57:39.257Z
@pmw1234 After a lot of debugging, I found out that the mantissa has a difference of value 1. This means that the unsigned integer value can be reinterpreted 1075903897 and 1075903898. These are real values from my measurement. So far you are correct. The problem now is that if you add +1 to a value, the probability that only one bit is different is 50%. The probability of two different bits 25%, three different bits: 12.5%. 4 different bits 6.25% ... so the total value of the mantissa and the number of different bits vary a lot. So making 1.2345 out of 1.23456 and 1.23457 does not work
Thomas
CC BY-SA 4.0
2024-01-22T14:07:56.087Z
So the first hash (to find a starting place) is the main problem: it depends on 3 values (x,y,z), maybe it is wiser to add these three values together and do 5 checks: sum(x,y,z)-2,to sum(x,y,z)+2. The separate hash tests coming after that can be made very easy and efficient with a small margin.
Thomas
CC BY-SA 4.0
2024-01-22T14:23:57.200Z
or to say, if one of the `gl_TessCoord ` values is zero, then do another hash key generation might be solving the  problem. Do you have any other ideas?
Thomas
CC BY-SA 4.0
2024-01-22T16:28:41.680Z
It seems like quantization is the thing that is stinging the hash table, looking into floating point normalization might be helpful. Something like compute that quantization value for a given float then use that to normalize the float before converting it to an int. What I am calling the quantization value here is the smallest difference between floats that can be computed with the current mantissa size. I'm not sure how efficient that process could be made though.
pmw1234
<opengl><glsl>
OpenGL hash vertices by position does not work on shared tessellated edges
Thomas
# OpenGL hash vertices by position does not work on shared tessellated edges

(Asked by: username_0 on 2024-01-19)

I have a triangular mesh with common vertices (VBO and EBO/IBO) that contain the normal vectors.
If I tessellate this mesh, the subdivision of the triangle edges of neighboring triangles has the same tessellation level. (The mesh therefore has no holes).

Each partial triangle created by the tessellation performs a normal calculation in the geometry shader, which results in flat shading. The individual triangles are therefore visible.

To avoid this flat shading and also to carry out some transformations afterwards, I decided to save the generated vertices in an SSBO buffer. The indices of the individual triangles are also saved in another SSBO buffer.

To avoid duplicates within the vbo SSBO, I try to hash the vertices according to their position.

But that doesn't seem to work properly. If you look at Figure 1, you can see the edge of two neighboring triangles that are tessellated. On the left side, some parts of the edge are "blurred", these are the parts that work correctly. The vertices that meet at this point share their normal vector, the normal is interpolated, resulting in this blurred edge. At the other points of the edge, my hashing did not work. I saved the generated positions in a file to see where the problem is. Within the VBO-SSBO, each vertex position should be unique! But they are not! All vertices within the same triangle patch are unique, but on the edges where two triangle patches share the same edge, I get duplicates.

The exact same vertex position of two vertices therefore results in two different hash keys. So my problem seems to be the hash key generation.

[![enter image description here](https://i.sstatic.net/LMGmQ.png)](https://i.sstatic.net/LMGmQ.png)

**This code generates the Hashkey:**

```
// 32 bit Murmur3 hash
uint HASH_hashKey(uint key)
{
    uint HASH_TABLE_CAPACITY = 64 * 1024 * 1024;
    key ^= key >> 16;
    key *= 0x85ebca6b;
    key ^= key >> 13;
    key *= 0xc2b2ae35;
    key ^= key >> 16;
    return key & (HASH_TABLE_CAPACITY - 1);
}

//generates a hash key (uint) depending on the mantissa of the 3D position. This hash key is NOT unique!! because the uint has not enough bits.
uint HASH_uvec3ToHash(uvec3 vector)
{
    return (vector.x & 0x7ff) | ((vector.y & 0x7ff) << 11) | ((vector.z & 0x3ff) << 22);
}

//creates or returns a slot for the given vertex position(key) reinterpretes as an uvec3.
//uvec4 HashKeyValue[] is the hash table HashKeyValue[].xyz: vertexPosition (reinterpreted)
uint HASH_getHashSlot(uvec3 key)
{
    //key = uvec3(key.x | 1, key.y | 1, key.z | 1);
    uint HASH_TABLE_CAPACITY = 64 * 1024 * 1024;
    uint slot = HASH_hashKey(HASH_uvec3ToHash(key));
    uint empty = 0xffffffff;
    while (true)
    {
        uint prevX = atomicCompSwap(HashKeyValue[slot].x, empty, key.x);
        if (prevX == empty || prevX == key.x)
        {
            uint prevY = atomicCompSwap(HashKeyValue[slot].y, empty, key.y);
            if (prevY == empty || prevY == key.y)
            {
                uint prevZ = atomicCompSwap(HashKeyValue[slot].z, empty, key.z);
                if (prevZ == empty || prevZ == key.z)
                {
                    return slot;
                }
            }
        }
        slot = (slot + 1) & (HASH_TABLE_CAPACITY - 1);
    }
}

```

The parameter "key" is the position of the vertex, reinterpreted as an unsigned integer (to be able to use atomic functions).

**The idea behind the code:**

`uint slot = HASH_hashKey(HASH_uvec3ToHash(key));` This line should point to a slot in the hash table that depends on the vertex position. However, it is possible that different positions receive the same value. For this reason, we then perform an x, y and z test. It is important to say that we do not delete any vertices so that we can iterate from the 'slot' position until we find a free hash slot. This is done in the `while (true)` loop:

Here we first test whether the x-value of the slot is empty and atomicCompSwap the new x-position.
The atomicCompSwap command returns the original value. This can be `empty 0xffffffffff` or the x-position we are looking for => we move on to the next test. Otherwise, this slot is used by another vertex with a different position, which was hashed here.
The same happens with `y` and `z`. If all three conditions are true (x, y, z), then we have found the perfect hashing slot. Otherwise, we check the next slot.

Somewhere here must be my mistake, because the VBO-SSBO output has duplicates generated by different hash slots.

**EDIT:** Tessellation takes place in ModelSpace, so that rotating the camera has no influence on the hash. Only race conditions can affect the hash slot if multiple positions refer to the same slot in the first hash. The bug is not flickering... so every frame is identical. therefore the same positions cause the same mismatch.

For those who are interested in the way the normals are calculated:

Each normal is multiplied by 1000 and saved as an integer. An atomicAdd function adds up all normals and during rendering it is converted to float and normalized.

**Tags:** opengl, glsl

> **Comments:**
> **username_1**: The entire point of a hashing algorithm is to produce the same output for a given input. So either the hash algorithm isn't behaving correctly (unlikely) or the inputs are different, (more likely) or the hash table is broken (less likely).  So it seems like the most likely issue is the keys have small differences and my suggestion would be to zero the low? high? ( I can never remember) bits of the mantissa after converting the float to an int. So that values like 1.23456 and 1.23457 become 1.2345.  
> **username_0**: @username_1 After a lot of debugging, I found out that the mantissa has a difference of value 1. This means that the unsigned integer value can be reinterpreted 1075903897 and 1075903898. These are real values from my measurement. So far you are correct. The problem now is that if you add +1 to a value, the probability that only one bit is different is 50%. The probability of two different bits 25%, three different bits: 12.5%. 4 different bits 6.25% ... so the total value of the mantissa and the number of different bits vary a lot. So making 1.2345 out of 1.23456 and 1.23457 does not work  
> **username_0**: So the first hash (to find a starting place) is the main problem: it depends on 3 values (x,y,z), maybe it is wiser to add these three values together and do 5 checks: sum(x,y,z)-2,to sum(x,y,z)+2. The separate hash tests coming after that can be made very easy and efficient with a small margin.  
> **username_0**: or to say, if one of the `gl_TessCoord ` values is zero, then do another hash key generation might be solving the  problem. Do you have any other ideas?  
> **username_1**: It seems like quantization is the thing that is stinging the hash table, looking into floating point normalization might be helpful. Something like compute that quantization value for a given float then use that to normalize the float before converting it to an int. What I am calling the quantization value here is the smallest difference between floats that can be computed with the current mantissa size. I'm not sure how efficient that process could be made though.  

---

## 0 answers

