A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using Unity.Burst;
2using Unity.Collections;
3using Unity.Collections.LowLevel.Unsafe;
4using Unity.Mathematics;
5
6namespace UnityEngine.U2D.Animation
7{
8 [BurstCompile]
9 internal static class MeshUtilities
10 {
11 /// <summary>
12 /// Get the outline edges from a set of indices.
13 /// This method expects the index array to be laid out with one triangle for every 3 indices.
14 /// E.g. triangle 0: index 0 - 2, triangle 1: index 3 - 5, etc.
15 /// </summary>
16 /// <returns>Returns a NativeArray of sorted edges. It is up to the caller to dispose this array.</returns>
17 public static NativeArray<int2> GetOutlineEdges(in NativeArray<ushort> indices)
18 {
19 var edges = new UnsafeHashMap<int, int3>(indices.Length, Allocator.Persistent);
20
21 for (var i = 0; i < indices.Length; i += 3)
22 {
23 var i0 = indices[i];
24 var i1 = indices[i + 1];
25 var i2 = indices[i + 2];
26
27 var edge0 = new int2(i0, i1);
28 var edge1 = new int2(i1, i2);
29 var edge2 = new int2(i2, i0);
30
31 AddToEdgeMap(edge0, ref edges);
32 AddToEdgeMap(edge1, ref edges);
33 AddToEdgeMap(edge2, ref edges);
34 }
35
36#if COLLECTIONS_2_0_OR_ABOVE
37 var outlineEdges = new NativeList<int2>(edges.Count, Allocator.Temp);
38#else
39 var outlineEdges = new NativeList<int2>(edges.Count(), Allocator.Temp);
40#endif
41 foreach (var edgePair in edges)
42 {
43 // If an edge is only used in one triangle, it is an outline edge.
44 if (edgePair.Value.z == 1)
45 outlineEdges.Add(edgePair.Value.xy);
46 }
47
48 edges.Dispose();
49
50 SortEdges(outlineEdges.AsArray(), out var sortedEdges);
51 return sortedEdges;
52 }
53
54 [BurstCompile]
55 static void AddToEdgeMap(in int2 edge, ref UnsafeHashMap<int, int3> edgeMap)
56 {
57 var tmpEdge = math.min(edge.x, edge.y) == edge.x ? edge.xy : edge.yx;
58 var hashCode = tmpEdge.GetHashCode();
59
60 // We store the hashCode as key, so that we can do less GetHashCode-calls.
61 // Then we store the count the int3s z-value.
62 if (!edgeMap.ContainsKey(hashCode))
63 edgeMap[hashCode] = new int3(edge, 1);
64 else
65 {
66 var val = edgeMap[hashCode];
67 val.z++;
68 edgeMap[hashCode] = val;
69 }
70 }
71
72 [BurstCompile]
73 static void SortEdges(in NativeArray<int2> unsortedEdges, out NativeArray<int2> sortedEdges)
74 {
75 var tmpEdges = new NativeArray<int2>(unsortedEdges.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
76 var shapeStartingEdge = new NativeList<int>(1, Allocator.Persistent);
77
78 var edgeMap = new UnsafeHashMap<int, int>(unsortedEdges.Length, Allocator.Persistent);
79 var usedEdges = new NativeArray<bool>(unsortedEdges.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
80
81 for (var i = 0; i < unsortedEdges.Length; i++)
82 {
83 edgeMap[unsortedEdges[i].x] = i;
84 usedEdges[i] = false;
85 }
86
87 var findStartingEdge = true;
88 var edgeIndex = -1;
89 var startingEdge = 0;
90 for (var i = 0; i < unsortedEdges.Length; i++)
91 {
92 if (findStartingEdge)
93 {
94 edgeIndex = GetFirstUnusedIndex(usedEdges);
95 startingEdge = edgeIndex;
96 findStartingEdge = false;
97 shapeStartingEdge.Add(i);
98 }
99
100 usedEdges[edgeIndex] = true;
101 tmpEdges[i] = unsortedEdges[edgeIndex];
102 var nextVertex = unsortedEdges[edgeIndex].y;
103 edgeIndex = edgeMap[nextVertex];
104
105 if (edgeIndex == startingEdge)
106 findStartingEdge = true;
107 }
108
109 var finalEdgeArrLength = unsortedEdges.Length;
110 sortedEdges = new NativeArray<int2>(finalEdgeArrLength, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
111 var count = 0;
112 for (var i = 0; i < shapeStartingEdge.Length; ++i)
113 {
114 var edgeStart = shapeStartingEdge[i];
115 var edgeEnd = (i + 1) == shapeStartingEdge.Length ? tmpEdges.Length : shapeStartingEdge[i + 1];
116
117 for (var m = edgeStart; m < edgeEnd; ++m)
118 sortedEdges[count++] = tmpEdges[m];
119 }
120
121 usedEdges.Dispose();
122 edgeMap.Dispose();
123 shapeStartingEdge.Dispose();
124 tmpEdges.Dispose();
125 }
126
127 [BurstCompile]
128 static int GetFirstUnusedIndex(in NativeArray<bool> usedValues)
129 {
130 for (var i = 0; i < usedValues.Length; i++)
131 {
132 if (!usedValues[i])
133 return i;
134 }
135
136 return -1;
137 }
138 }
139}