A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Collections.Generic;
3using UnityEngine;
4using UnityEditor.U2D.Common;
5using UnityEditor.U2D.Animation.ClipperLib;
6using UnityEditor.U2D.Sprites;
7
8namespace UnityEditor.U2D.Animation
9{
10 using Path = List<IntPoint>;
11 using Paths = List<List<IntPoint>>;
12
13 internal class OutlineGenerator : IOutlineGenerator
14 {
15 const double kClipperScale = 1000.0;
16
17 private const float kEpsilon = 1.2e-12f;
18 private const float kMinLinearizeDistance = 5f;
19 private Texture2D m_CurrentTexture;
20 private Rect m_CurrentRect;
21 private byte m_CurrentAlphaTolerance;
22
23 public void GenerateOutline(ITextureDataProvider textureDataProvider, Rect rect, float detail, byte alphaTolerance, bool holeDetection, out Vector2[][] paths)
24 {
25 if (alphaTolerance >= 255)
26 throw new ArgumentException("Alpha tolerance should be lower than 255");
27
28 m_CurrentTexture = textureDataProvider.GetReadableTexture2D();
29 m_CurrentRect = rect;
30 m_CurrentAlphaTolerance = alphaTolerance;
31
32 InternalEditorBridge.GenerateOutline(textureDataProvider.texture, rect, 1f, alphaTolerance, holeDetection, out paths);
33
34 if (paths.Length > 0)
35 {
36 ClipPaths(ref paths);
37
38 Debug.Assert(paths.Length > 0);
39
40 var rectSizeMagnitude = rect.size.magnitude;
41 var minDistance = Mathf.Max(rectSizeMagnitude / 10f, kMinLinearizeDistance);
42 var maxDistance = Mathf.Max(rectSizeMagnitude / 100f, kMinLinearizeDistance);
43 var distance = Mathf.Lerp(minDistance, maxDistance, detail);
44
45 for (var pathIndex = 0; pathIndex < paths.Length; ++pathIndex)
46 {
47 var pathLength = CalculatePathLength(paths[pathIndex]);
48 if (pathLength > distance)
49 {
50 var newPath = Linearize(new List<Vector2>(paths[pathIndex]), distance);
51
52 if (newPath.Count > 3)
53 paths[pathIndex] = newPath.ToArray();
54
55 SmoothPath(paths[pathIndex], 5, 0.1f, 135f);
56 }
57 }
58
59 ClipPaths(ref paths);
60 }
61
62 // Merge the Polygons to one (doesn't always succeeds).
63 var clipper = new Clipper(Clipper.ioPreserveCollinear);
64 var subj = ToClipper(paths);
65 var solution = new Paths();
66 clipper.AddPaths(subj, PolyType.ptSubject, true);
67 clipper.Execute(ClipType.ctUnion, solution, PolyFillType.pftNonZero, PolyFillType.pftNonZero);
68 paths = ToVector2(solution);
69 m_CurrentAlphaTolerance = alphaTolerance;
70 }
71
72 private void ClipPaths(ref Vector2[][] paths)
73 {
74 Debug.Assert(paths.Length > 0);
75
76 var subj = ToClipper(paths);
77 var solution = new Paths();
78 var clipper = new Clipper(Clipper.ioPreserveCollinear);
79
80 clipper.AddPaths(subj, PolyType.ptSubject, true);
81 clipper.Execute(ClipType.ctUnion, solution, PolyFillType.pftPositive, PolyFillType.pftPositive);
82 FilterNestedPaths(solution);
83 paths = ToVector2(solution);
84 }
85
86 private void FilterNestedPaths(Paths paths)
87 {
88 var filtered = new List<Path>(paths);
89
90 for (var i = 0; i < paths.Count; ++i)
91 {
92 var path = paths[i];
93
94 if (!filtered.Contains(path))
95 continue;
96
97 for (var j = i + 1; j < paths.Count; ++j)
98 {
99 if (!filtered.Contains(path))
100 continue;
101
102 var other = paths[j];
103
104 if (IsPathContainedInOtherPath(path, other))
105 {
106 filtered.Remove(path);
107 break;
108 }
109 else if (IsPathContainedInOtherPath(other, path))
110 filtered.Remove(other);
111 }
112 }
113
114 paths.Clear();
115 paths.AddRange(filtered);
116 }
117
118 private bool IsPathContainedInOtherPath(Path path, Path other)
119 {
120 foreach (var p in path)
121 {
122 if (Clipper.PointInPolygon(p, other) < 1)
123 return false;
124 }
125
126 return true;
127 }
128
129 private Paths ToClipper(Vector2[][] paths)
130 {
131 return new Paths(Array.ConvertAll(paths, p => ToClipper(p)));
132 }
133
134 private Path ToClipper(Vector2[] path)
135 {
136 return new Path(Array.ConvertAll(path, p => new IntPoint(p.x * kClipperScale, p.y * kClipperScale)));
137 }
138
139 private Vector2[][] ToVector2(Paths paths)
140 {
141 return paths.ConvertAll(p => ToVector2(p)).ToArray();
142 }
143
144 private Vector2[] ToVector2(Path path)
145 {
146 return path.ConvertAll(p => new Vector2((float)(p.X / kClipperScale), (float)(p.Y / kClipperScale))).ToArray();
147 }
148
149 private float CalculatePathLength(Vector2[] path)
150 {
151 var sum = 0f;
152 for (var i = 0; i < path.Length; i++)
153 {
154 var nextIndex = NextIndex(i, path.Length);
155 var p0 = path[i];
156 var p1 = path[nextIndex];
157 sum += Vector2.Distance(p0, p1);
158 }
159
160 return sum;
161 }
162
163 //Adapted from https://github.com/burningmime/curves
164 private List<Vector2> Linearize(List<Vector2> src, float pointDistance)
165 {
166 if (src == null) throw new ArgumentNullException("src");
167 if (pointDistance <= kEpsilon) throw new InvalidOperationException("pointDistance " + pointDistance + " is less than epislon " + kEpsilon);
168
169 var dst = new List<Vector2>();
170
171 if (src.Count > 0)
172 {
173 var accDistance = 0f;
174 var lastIndex = 0;
175 var lastPoint = src[0];
176
177 dst.Add(lastPoint);
178
179 for (var i = 0; i < src.Count; i++)
180 {
181 var nextIndex = NextIndex(i, src.Count);
182 var p0 = src[i];
183 var p1 = src[nextIndex];
184 var edgeDistance = Vector2.Distance(p0, p1);
185
186 if (accDistance + edgeDistance > pointDistance || nextIndex == 0)
187 {
188 var partialDistance = pointDistance - accDistance;
189 var newPoint = Vector2.Lerp(p0, p1, partialDistance / edgeDistance);
190 var remainingDistance = edgeDistance - partialDistance;
191
192 //Roll back until we do not intersect any pixel
193 var step = 1f;
194 bool finish = false;
195 while (!finish && IsLineOverImage(newPoint, lastPoint))
196 {
197 partialDistance = Vector2.Distance(p0, newPoint) - step;
198
199 while (partialDistance < 0f)
200 {
201 if (i > lastIndex + 1)
202 {
203 accDistance -= edgeDistance;
204 --i;
205 p1 = p0;
206 p0 = src[i];
207 edgeDistance = Vector2.Distance(p0, p1);
208 partialDistance += edgeDistance;
209 }
210 else
211 {
212 partialDistance = 0f;
213 finish = true;
214 }
215
216 remainingDistance = edgeDistance - partialDistance;
217 }
218
219 newPoint = Vector2.Lerp(p0, p1, partialDistance / edgeDistance);
220 }
221
222 Debug.Assert(lastIndex <= i, "Generate Outline failed");
223
224 nextIndex = NextIndex(i, src.Count);
225 if (nextIndex != 0 || !EqualsOrClose(newPoint, p1))
226 {
227 dst.Add(newPoint);
228 lastPoint = newPoint;
229 lastIndex = i;
230 }
231
232 while (remainingDistance > pointDistance)
233 {
234 remainingDistance -= pointDistance;
235 newPoint = Vector2.Lerp(p0, p1, (edgeDistance - remainingDistance) / edgeDistance);
236 if (!EqualsOrClose(newPoint, lastPoint))
237 {
238 dst.Add(newPoint);
239 lastPoint = newPoint;
240 }
241 }
242
243 accDistance = remainingDistance;
244 }
245 else
246 {
247 accDistance += edgeDistance;
248 }
249 }
250 }
251
252 return dst;
253 }
254
255 private bool EqualsOrClose(Vector2 v1, Vector2 v2)
256 {
257 return (v1 - v2).sqrMagnitude < kEpsilon;
258 }
259
260 private void SmoothPath(Vector2[] path, int iterations, float velocity, float minAngle)
261 {
262 Debug.Assert(iterations > 0f);
263 Debug.Assert(minAngle >= 0f);
264 Debug.Assert(minAngle < 180f);
265
266 var cosTolerance = Mathf.Cos(minAngle * Mathf.Deg2Rad);
267
268 for (int iteration = 0; iteration < iterations; ++iteration)
269 for (int i = 0; i < path.Length; ++i)
270 {
271 var prevPoint = path[PreviousIndex(i, path.Length)];
272 var point = path[i];
273 var nextPoint = path[NextIndex(i, path.Length)];
274
275 var t1 = prevPoint - point;
276 var t2 = nextPoint - point;
277
278 var dot = Vector2.Dot(t1.normalized, t2.normalized);
279
280 if (dot > cosTolerance)
281 continue;
282
283 var w1 = 1f / (point - prevPoint).magnitude;
284 var w2 = 1f / (point - nextPoint).magnitude;
285 var laplacian = (w1 * prevPoint + w2 * nextPoint) / (w1 + w2) - point;
286 point += laplacian * velocity;
287
288 if (!IsLineOverImage(point, nextPoint) && !IsLineOverImage(point, prevPoint))
289 path[i] = point;
290 }
291 }
292
293 private Vector2Int ToVector2Int(Vector2 v)
294 {
295 return new Vector2Int(Mathf.RoundToInt(v.x), Mathf.RoundToInt(v.y));
296 }
297
298 private bool IsLineOverImage(Vector2 pointA, Vector2 pointB)
299 {
300 var pointAInt = ToVector2Int(pointA);
301 var pointBInt = ToVector2Int(pointB);
302
303 if (IsPointInRectEdge(pointA) && IsPointInRectEdge(pointB) && (pointAInt.x == pointBInt.x || pointAInt.y == pointBInt.y))
304 return false;
305
306 foreach (var point in GetPointsOnLine(pointAInt.x, pointAInt.y, pointBInt.x, pointBInt.y))
307 {
308 if (IsPointOverImage(point))
309 return true;
310 }
311
312 return false;
313 }
314
315 private bool IsPointOverImage(Vector2 point)
316 {
317 Debug.Assert(m_CurrentTexture != null);
318 point += m_CurrentRect.center;
319 return m_CurrentTexture.GetPixel((int)point.x, (int)point.y).a * 255 > m_CurrentAlphaTolerance;
320 }
321
322 private bool IsPointInRectEdge(Vector2 point)
323 {
324 point += m_CurrentRect.center;
325 var pointInt = ToVector2Int(point);
326 var minInt = ToVector2Int(m_CurrentRect.min);
327 var maxInt = ToVector2Int(m_CurrentRect.max);
328 return minInt.x >= pointInt.x || maxInt.x <= pointInt.x || minInt.y >= pointInt.y || maxInt.y <= pointInt.y;
329 }
330
331 //From http://ericw.ca/notes/bresenhams-line-algorithm-in-csharp.html
332 private IEnumerable<Vector2Int> GetPointsOnLine(int x0, int y0, int x1, int y1)
333 {
334 bool steep = Mathf.Abs(y1 - y0) > Math.Abs(x1 - x0);
335 if (steep)
336 {
337 int t;
338 t = x0; // swap x0 and y0
339 x0 = y0;
340 y0 = t;
341 t = x1; // swap x1 and y1
342 x1 = y1;
343 y1 = t;
344 }
345
346 if (x0 > x1)
347 {
348 int t;
349 t = x0; // swap x0 and x1
350 x0 = x1;
351 x1 = t;
352 t = y0; // swap y0 and y1
353 y0 = y1;
354 y1 = t;
355 }
356
357 int dx = x1 - x0;
358 int dy = Mathf.Abs(y1 - y0);
359 int error = dx / 2;
360 int ystep = (y0 < y1) ? 1 : -1;
361 int y = y0;
362 for (int x = x0; x <= x1; x++)
363 {
364 yield return new Vector2Int((steep ? y : x), (steep ? x : y));
365 error = error - dy;
366 if (error < 0)
367 {
368 y += ystep;
369 error += dx;
370 }
371 }
372
373 yield break;
374 }
375
376 private int NextIndex(int index, int pointCount)
377 {
378 return Mod(index + 1, pointCount);
379 }
380
381 private int PreviousIndex(int index, int pointCount)
382 {
383 return Mod(index - 1, pointCount);
384 }
385
386 private int Mod(int x, int m)
387 {
388 int r = x % m;
389 return r < 0 ? r + m : r;
390 }
391 }
392}