Most efficient way to generate a mesh's string-hash in unity/c#?

Question

As part of my current project, I need to generate hashes for meshes in Unity. These are used to later check whether the mesh content has changed. Due to interface considerations, the hash unfortunately has to be in form of a string.

My current approach looks like this:

        public override string GetHash()
        {
            StringBuilder hash = new StringBuilder();
            hash.Append("v");
            foreach (Vector3 val in this.v)
            {
                hash.Append(val.ToString());
            }
            hash.Append("n");
            foreach (Vector3 val in this.n)
            {
                hash.Append(val.ToString());
            }
            hash.Append("u");
            foreach (Vector2 val in this.u)
            {
                hash.Append(val.ToString());
            }
            hash.Append("v");
            foreach (int val in this.t)
            {
                hash.Append(val.ToString());
            }
            return hash.ToString();
        }

This has turned out to be a significant bottleneck, primarily due to the Vector3.ToString()-calls. (about 4-5ms for the cube primitive).

Are there more performant ways to hash meshes that are still sensitive to small changes in the mesh?

Is it acceptable a very small chance that two different meshes will generate the same hash? By small I mean 1 / 2,147,483,647. — Theodor Zoulias, Nov 14 '19 at 21:28
@Theodor: If those collisions aren't linked to similarities in the original mesh, that seems acceptably low. — Tobl, Nov 15 '19 at 14:43
and in general what kind of changes do you need to track? Is it really relevant if normals or uvs change? Isn't it enough if a vertex position was changed? — derHugo, Nov 15 '19 at 14:45
@derHugo: I believe mesh.GetHashCode is linked to the instance, not the content of the mesh. So two different meshes with identical structure would result in different hashes, would they not? — Tobl, Nov 15 '19 at 14:45
@Tobl probably true yes. But how about the content? Can't you atleast reduce it to the vertices? — derHugo, Nov 15 '19 at 14:49

score 2 · Answer 1 · answered Nov 15 '19 at 15:24

You could try this implementation of GetHash. The CombineHashCodes method is stolen from Microsoft's source code.

public override string GetHash()
{
    int hashCode = 0;
    foreach (Vector3 val in this.v)
    {
        hashCode = CombineHashCodes(hashCode, val.X.GetHashCode());
        hashCode = CombineHashCodes(hashCode, val.Y.GetHashCode());
        hashCode = CombineHashCodes(hashCode, val.Z.GetHashCode());
    }
    foreach (Vector3 val in this.n)
    {
        hashCode = CombineHashCodes(hashCode, val.X.GetHashCode());
        hashCode = CombineHashCodes(hashCode, val.Y.GetHashCode());
        hashCode = CombineHashCodes(hashCode, val.Z.GetHashCode());
    }
    foreach (Vector2 val in this.u)
    {
        hashCode = CombineHashCodes(hashCode, val.X.GetHashCode());
        hashCode = CombineHashCodes(hashCode, val.Y.GetHashCode());
    }
    foreach (int val in this.t)
    {
        hashCode = CombineHashCodes(hashCode, val.GetHashCode());
    }
    return hashCode.ToString();
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int CombineHashCodes(int h1, int h2)
{
    return ((h1 << 5) + h1) ^ h2;
}

For other implementations of CombineHashCodes look here: Quick and Simple Hash Code Combinations

You could also try switching from `int` to `long`, for an even smaller probability of collision. In 64 bit systems it may not be slower. — Theodor Zoulias, Nov 15 '19 at 15:34

derHugo · Answer 2 · 2019-11-15T15:12:31.243

Vector3 is a struct and its GetHashCode implementation returns the same hash if the Vector3 has the same value(s):

public override int GetHashCode()
{
    return this.x.GetHashCode() ^ this.y.GetHashCode() << 2 ^ this.z.GetHashCode() >> 2;
}

So in general I would rather do the hash calculation as an int and only return a string as the very last step:

public override string GetHash()
{
    var output = 0;
    foreach (Vector3 val in this.v)
    {
        // e.g. using bitwise XOR
        output = output ^ val.GetHashCode();
    }

    foreach (Vector3 val in this.n)
    {
        output = output ^ val.GetHashCode();
    }

    foreach (Vector2 val in this.u)
    {
        output = output ^ val.GetHashCode();
    }

    foreach (int val in this.t)
    {
        output = output ^ val.GetHashCode();
    }
    return output.ToString();
}

Also I don't know your exact use-case but it is probably enough to have a hash of the vertex positions.

I would suggest using something like

var output = 0;
foreach (var vertex in mesh.vertices)
{
    output = output ^ vertex.GetHashCode();
}
return output.ToString();

Most efficient way to generate a mesh's string-hash in unity/c#?

2 Answers2