com.unity.demoteam.digital-human/Runtime/MeshTools/MeshAdjacency.cs

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;

public class MeshAdjacency
{
    public LinkedIndexListArray vertexTriangles;
    public LinkedIndexListArray vertexVertices;
    public LinkedIndexListArray vertexWelded;
    public int[] vertexResolve;
    public int vertexCount;

    public LinkedIndexListArray triangleTriangles;
    public LinkedIndexListArray triangleVertices;
    public int triangleCount;

    public MeshAdjacency(MeshBuffers meshBuffers, bool welded = false)
    {
        LoadFrom(meshBuffers, welded);
    }

    public void LoadFrom(MeshBuffers meshBuffers, bool welded = false)
    {
        vertexCount = meshBuffers.vertexCount;
        vertexTriangles.Allocate(vertexCount, vertexCount * 8);
        vertexVertices.Allocate(vertexCount, vertexCount * 8);
        vertexWelded.Allocate(vertexCount, vertexCount);

        ArrayUtils.ResizeCheckedIfLessThan(ref vertexResolve, vertexCount);

        triangleCount = meshBuffers.triangleCount / 3;
        triangleTriangles.Allocate(triangleCount, triangleCount * 8);
        triangleVertices.Allocate(triangleCount, triangleCount * 3);

        int[] triangles = meshBuffers.triangles;

        // build vertex-triangle
        {
            for (int i = 0; i != triangleCount; i++)
            {
                int _0 = i * 3;
                int v0 = triangles[_0 + 0];
                int v1 = triangles[_0 + 1];
                int v2 = triangles[_0 + 2];

                vertexTriangles.Append(v0, i);
                vertexTriangles.Append(v1, i);
                vertexTriangles.Append(v2, i);
            }
        }

        // build vertex-welded
        unsafe
        {
            if (welded)
            {
                // for each vertex
                //   if vertex != closest vertex
                //     replace references to vertex with closest vertex
                triangles = triangles.Clone() as int[];

                using (var vertexWeldedMap = new UnsafeArrayBool(meshBuffers.vertexCount))
                {
                    vertexWeldedMap.Clear(false);

                    var vertexBSP = new KdTree3(meshBuffers.vertexPositions, meshBuffers.vertexCount);

                    for (int i = 0; i != vertexCount; i++)
                    {
                        int j = vertexBSP.FindNearest(ref meshBuffers.vertexPositions[i]);
                        if (j != i)
                        {
                            //Debug.Assert(vertexWeldedMap.val[j] == false);

                            // replace references to i with j, keeping j
                            foreach (var triangle in vertexTriangles[i])
                            {
                                int _0 = triangle * 3;
                                int v0 = triangles[_0 + 0];
                                int v1 = triangles[_0 + 1];
                                //..v2 = triangles[_0 + 2];

                                if (v0 == i)
                                    triangles[_0 + 0] = j;
                                else if (v1 == i)
                                    triangles[_0 + 1] = j;
                                else // (v2 == i)
                                    triangles[_0 + 2] = j;

                                // store i under j, so we can recover i at a later time
                                if (vertexWeldedMap.val[i] == false)
                                {
                                    vertexWeldedMap.val[i] = true;
                                    vertexWelded.Append(j, i);
                                }
                            }
                        }
                    }
                }

                // rebuild vertex-triangle
                vertexTriangles.Clear();

                for (int i = 0; i != triangleCount; i++)
                {
                    int _0 = i * 3;
                    int v0 = triangles[_0 + 0];
                    int v1 = triangles[_0 + 1];
                    int v2 = triangles[_0 + 2];

                    vertexTriangles.Append(v0, i);
                    vertexTriangles.Append(v1, i);
                    vertexTriangles.Append(v2, i);
                }
            }
        }

        // build vertex-resolve
        {
            for (int i = 0; i != vertexCount; i++)
            {
                vertexResolve[i] = i;
            }

            for (int i = 0; i != vertexCount; i++)
            {
                foreach (var j in vertexWelded[i])
                {
                    vertexResolve[j] = i;
                }
            }
        }

        // build vertex-vertex
        unsafe
        {
            using (var vertexAdded = new UnsafeArrayBool(vertexCount))
            {
                vertexAdded.Clear(false);

                for (int i = 0; i != vertexCount; i++)
                {
                    foreach (int triangle in vertexTriangles[i])
                    {
                        int _0 = triangle * 3;
                        int v0 = triangles[_0 + 0];
                        int v1 = triangles[_0 + 1];
                        int v2 = triangles[_0 + 2];

                        int vA, vB;
                        if (i == v0)
                        {
                            vA = v1;
                            vB = v2;
                        }
                        else if (i == v1)
                        {
                            vA = v2;
                            vB = v0;
                        }
                        else // (i == v2)
                        {
                            vA = v0;
                            vB = v1;
                        }

                        if (vertexAdded.val[vA] == false && (vertexAdded.val[vA] = true))
                            vertexVertices.Append(i, vA);

                        if (vertexAdded.val[vB] == false && (vertexAdded.val[vB] = true))
                            vertexVertices.Append(i, vB);
                    }

                    foreach (int j in vertexVertices[i])
                        vertexAdded.val[j] = false;
                }
            }
        }

        // build triangle-triangle
        unsafe
        {
            using (var triangleAdded = new UnsafeArrayBool(triangleCount))
            {
                triangleAdded.Clear(false);

                for (int i = 0; i != triangleCount; i++)
                {
                    int _0 = i * 3;
                    int v0 = triangles[_0 + 0];
                    int v1 = triangles[_0 + 1];
                    int v2 = triangles[_0 + 2];

                    triangleAdded.val[i] = true;

                    foreach (int j in vertexTriangles[v0])
                        if (triangleAdded.val[j] == false && (triangleAdded.val[j] = true))
                            triangleTriangles.Append(i, j);

                    foreach (int j in vertexTriangles[v1])
                        if (triangleAdded.val[j] == false && (triangleAdded.val[j] = true))
                            triangleTriangles.Append(i, j);

                    foreach (int j in vertexTriangles[v2])
                        if (triangleAdded.val[j] == false && (triangleAdded.val[j] = true))
                            triangleTriangles.Append(i, j);

                    triangleAdded.val[i] = false;

                    foreach (int j in triangleTriangles[i])
                        triangleAdded.val[j] = false;
                }
            }
        }

        // build triangle-vertex
        {
            for (int i = 0; i != triangleCount; i++)
            {
                int _0 = i * 3;
                int v0 = triangles[_0 + 0];
                int v1 = triangles[_0 + 1];
                int v2 = triangles[_0 + 2];

                triangleVertices.Append(i, v0);
                triangleVertices.Append(i, v1);
                triangleVertices.Append(i, v2);
            }
        }
    }
}