1  using System;
  2  using System.Collections.Generic;
  3  using UnityEngine;
  4  using System.Runtime.InteropServices;
  5  using DefaultNamespace;
  6  using UnityEditor;
  7  
  8  public class SharpSilhouetteEdgeCalculator : MonoBehaviour, IGreasePencilEdgeCalculator
  9  {
 10      private static readonly int WorldSpaceCameraPos = Shader.PropertyToID("_WorldSpaceCameraPos");
 11      private static readonly int ObjectToWorld = Shader.PropertyToID("_ObjectToWorld");
 12      private static readonly int ObjectToWorldIt = Shader.PropertyToID("_ObjectToWorldIT");
 13      private static readonly int NextPointerDst = Shader.PropertyToID("_nextPointerDst");
 14      private static readonly int NextPointerSrc = Shader.PropertyToID("_nextPointerSrc");
 15      private static readonly int RadiusMultiplier = Shader.PropertyToID("_radiusMultiplier");
 16      private const int ADJ_NONE = -1;
 17      private const int INVALID = -2;
 18  
 19      private ComputeShader _sharpSilhouetteEdgeFinder;
 20      private ComputeShader _sharpEdgesToStrokes;
 21      private ComputeShader _strokesToGreasePencilStrokes;
 22      
 23      private Mesh _sourceMesh;
 24      private int CornerCount => _sourceMesh.triangles.Length;
 25      private int FaceCount => _sourceMesh.triangles.Length / 3;
 26      
 27  
 28      public Camera viewCamera;
 29      public float radiusMultiplier = 1.0f;
 30  
 31      private ComputeBuffer _verticesBuffer;
 32      private ComputeBuffer _indicesBuffer;
 33      private ComputeBuffer _adjIndicesBuffer;
 34      private ComputeBuffer _strokesBuffer;
 35      private ComputeBuffer _nextPointerSrcBuffer;
 36      private ComputeBuffer _nextPointerDstBuffer;
 37      // Two 1-element buffers to be used as UAV atomic counters by the compute shader
 38      private ComputeBuffer _numStrokesCounterBuffer;
 39      private ComputeBuffer _numStrokePointsCounterBuffer;
 40  
 41      // Graphics buffers for GreasePencil output
 42      private GraphicsBuffer _denseStrokesBuffer;
 43      private GraphicsBuffer _colorBuffer;
 44      
 45      
 46      // Kernel indices for shaders
 47      private int _findSharpSilhouetteEdge_Kernel;
 48  
 49      private int _initialize_Kernel;
 50      private int _reduce_Kernel;
 51      private int _findStrokeTail_Kernel;
 52      private int _resetNext_Kernel;
 53      private int _initDistances_Kernel;
 54      private int _listRank_Kernel;
 55  
 56      private int _setStrokeLengthAtTail_Kernel;
 57      private int _calcStrokeOffsets_Kernel;
 58      private int _invalidateEntries_Kernel;
 59      private int _sorter_Kernel;
 60  
 61      private const uint NUM_POINTER_JUMP_ITERATIONS = 8;
 62      
 63      
 64      private void Awake()
 65      {
 66          _sharpSilhouetteEdgeFinder = Instantiate(Resources.Load<ComputeShader>("Lineart/ComputeShaders/SharpSilhouetteEdge"));
 67          _sharpEdgesToStrokes = Instantiate(Resources.Load<ComputeShader>("Lineart/ComputeShaders/SharpEdgesToStrokes"));
 68          _strokesToGreasePencilStrokes = Instantiate(Resources.Load<ComputeShader>("Lineart/ComputeShaders/StrokesToGreasePencil"));
 69          
 70          _sourceMesh = GetComponent<MeshFilter>()?.sharedMesh;
 71          
 72          ResolveViewCamera();
 73      }
 74      
 75      private void ResolveViewCamera()
 76      {
 77  #if UNITY_EDITOR
 78          if (viewCamera == null)
 79          {
 80              SceneView sceneView = SceneView.lastActiveSceneView;
 81              viewCamera = sceneView != null ? sceneView.camera : Camera.main;
 82          }
 83  #else
 84          if (viewCamera == null) viewCamera = Camera.main;
 85  #endif
 86      }
 87      
 88      void Start()
 89      {
 90          if (!SystemInfo.supportsComputeShaders)
 91          {
 92              Debug.LogError("Compute shaders are not supported on this platform.");
 93              return;
 94          }
 95  
 96          if (_sourceMesh == null)
 97          {
 98              return;
 99          }
100  
101          InitializeKernels();
102          InitializeBuffers();
103          BindBuffersToShaders();
104      }
105  
106      void InitializeKernels()
107      {
108          _findSharpSilhouetteEdge_Kernel = _sharpSilhouetteEdgeFinder.FindKernel("FindSilhouetteEdge");
109  
110          _initialize_Kernel = _sharpEdgesToStrokes.FindKernel("Initialize");
111          _reduce_Kernel = _sharpEdgesToStrokes.FindKernel("Reduce"); 
112          _findStrokeTail_Kernel = _sharpEdgesToStrokes.FindKernel("FindStrokeTail");
113          _resetNext_Kernel = _sharpEdgesToStrokes.FindKernel("ResetNextPointer");
114          _initDistances_Kernel = _sharpEdgesToStrokes.FindKernel("InitializeRanksAndDistances");
115          _listRank_Kernel = _sharpEdgesToStrokes.FindKernel("CalculateRanksAndDistances");
116  
117          _setStrokeLengthAtTail_Kernel = _strokesToGreasePencilStrokes.FindKernel("SetStrokeLengthAtTail");
118          _calcStrokeOffsets_Kernel = _strokesToGreasePencilStrokes.FindKernel("CalculateArrayOffsets");
119          _invalidateEntries_Kernel = _strokesToGreasePencilStrokes.FindKernel("InvalidateEntries");
120          _sorter_Kernel = _strokesToGreasePencilStrokes.FindKernel("MoveToDenseArray");
121      }
122      void InitializeBuffers()
123      {
124          CreateBuffersForSilhouetteEdgeFinder();
125          CreateBuffersForEdgesToStrokes();
126          CreateBuffersForGreasePencilStrokes();
127      }
128  
129      private void CreateBuffersForSilhouetteEdgeFinder()
130      {
131          Vector3[] positions = _sourceMesh.vertices;
132          Vector3[] normals = _sourceMesh.normals;
133          SilhouetteSourceVertex[] vertexDataArray = new SilhouetteSourceVertex[positions.Length];
134          for (int i = 0; i < positions.Length; i++)
135          {
136              vertexDataArray[i] = new SilhouetteSourceVertex
137              {
138                  position = positions[i],
139                  normal = normals[i]
140              };
141          }
142          _verticesBuffer = new ComputeBuffer(vertexDataArray.Length, Marshal.SizeOf(typeof(SilhouetteSourceVertex)));
143          _verticesBuffer.SetData(vertexDataArray);
144  
145          int[] indices = _sourceMesh.triangles;
146          _indicesBuffer = new ComputeBuffer(indices.Length, sizeof(int));
147          _indicesBuffer.SetData(indices);
148  
149          int[] adjData = CalculateCornerAdjacency(indices, positions);
150          _adjIndicesBuffer = new ComputeBuffer(adjData.Length, sizeof(uint));
151          _adjIndicesBuffer.SetData(adjData);
152  
153          _strokesBuffer = new ComputeBuffer(CornerCount, SilhouetteStrokeEdge.SizeOf);
154      }
155  
156      void CreateBuffersForEdgesToStrokes()
157      {
158          _nextPointerSrcBuffer = new ComputeBuffer(CornerCount, sizeof(int));
159          _nextPointerDstBuffer = new ComputeBuffer(CornerCount, sizeof(int));
160      }
161      
162      void CreateBuffersForGreasePencilStrokes()
163      {
164          //TODO: find a tighter limit for these buffer sizes
165          //output buffers
166          _denseStrokesBuffer = new GraphicsBuffer(GraphicsBuffer.Target.Structured, 2 * FaceCount, GreasePencilRenderer.GreasePencilStrokeVert.SizeOf);
167          _colorBuffer = new GraphicsBuffer(GraphicsBuffer.Target.Structured, 2 * FaceCount, GreasePencilRenderer.GreasePencilColorVert.SizeOf);
168  
169          //offset calculation buffers
170          _numStrokesCounterBuffer = new ComputeBuffer(1, sizeof(uint));
171          _numStrokePointsCounterBuffer = new ComputeBuffer(1, sizeof(uint));
172      }
173      
174      void BindBuffersToShaders()
175      {
176          _sharpSilhouetteEdgeFinder.SetBuffer(_findSharpSilhouetteEdge_Kernel, "_Vertices", _verticesBuffer);
177          _sharpSilhouetteEdgeFinder.SetBuffer(_findSharpSilhouetteEdge_Kernel, "_Indices", _indicesBuffer);
178          _sharpSilhouetteEdgeFinder.SetBuffer(_findSharpSilhouetteEdge_Kernel, "_AdjIndices", _adjIndicesBuffer);
179          _sharpSilhouetteEdgeFinder.SetBuffer(_findSharpSilhouetteEdge_Kernel, "_outStrokes", _strokesBuffer);
180          _sharpSilhouetteEdgeFinder.SetInt("_NumVerts", CornerCount);
181  
182          _sharpEdgesToStrokes.SetInt("_NumVerts", CornerCount);
183      
184          _sharpEdgesToStrokes.SetBuffer(_initialize_Kernel, "_strokes", _strokesBuffer);
185          _sharpEdgesToStrokes.SetBuffer(_reduce_Kernel, "_strokes", _strokesBuffer);
186          _sharpEdgesToStrokes.SetBuffer(_findStrokeTail_Kernel, "_strokes", _strokesBuffer);
187          _sharpEdgesToStrokes.SetBuffer(_listRank_Kernel, "_strokes", _strokesBuffer);
188          _sharpEdgesToStrokes.SetBuffer(_resetNext_Kernel, "_strokes", _strokesBuffer);
189          _sharpEdgesToStrokes.SetBuffer(_initDistances_Kernel, "_strokes", _strokesBuffer);
190              
191          _strokesToGreasePencilStrokes.SetInt("_NumFaces", CornerCount);
192          
193          _strokesToGreasePencilStrokes.SetBuffer(_setStrokeLengthAtTail_Kernel, "_strokes", _strokesBuffer);
194          
195          _strokesToGreasePencilStrokes.SetBuffer(_calcStrokeOffsets_Kernel, "_strokes", _strokesBuffer);
196          _strokesToGreasePencilStrokes.SetBuffer(_calcStrokeOffsets_Kernel, "numStrokesCounter", _numStrokesCounterBuffer);
197          _strokesToGreasePencilStrokes.SetBuffer(_calcStrokeOffsets_Kernel, "numStrokePointsCounter", _numStrokePointsCounterBuffer);
198  
199          _strokesToGreasePencilStrokes.SetBuffer(_invalidateEntries_Kernel, "_denseArray", _denseStrokesBuffer);
200          
201          _strokesToGreasePencilStrokes.SetBuffer(_sorter_Kernel, "_strokes", _strokesBuffer);
202          _strokesToGreasePencilStrokes.SetBuffer(_sorter_Kernel, "_denseArray", _denseStrokesBuffer);
203          _strokesToGreasePencilStrokes.SetBuffer(_sorter_Kernel, "_colorArray", _colorBuffer);
204      }
205      
206  
207      private void BindNextPointers(int kernel)
208      {
209          _sharpEdgesToStrokes.SetBuffer(kernel, NextPointerSrc, _nextPointerSrcBuffer);
210          _sharpEdgesToStrokes.SetBuffer(kernel, NextPointerDst, _nextPointerDstBuffer);
211      }
212  
213      private void SwapNextPointers()
214      {
215          (_nextPointerSrcBuffer, _nextPointerDstBuffer) = (_nextPointerDstBuffer, _nextPointerSrcBuffer);
216      }
217  
218      public void CalculateEdges()
219      {
220          if (_sourceMesh == null || viewCamera == null) return;
221  
222          _sharpSilhouetteEdgeFinder.SetVector(WorldSpaceCameraPos, viewCamera.transform.position);
223  
224          Matrix4x4 objectToWorld = transform.localToWorldMatrix;
225          _sharpSilhouetteEdgeFinder.SetMatrix(ObjectToWorld, objectToWorld);
226          _sharpSilhouetteEdgeFinder.SetMatrix(ObjectToWorldIt, objectToWorld.inverse.transpose);
227  
228          int threadGroups = Mathf.CeilToInt(FaceCount / 64.0f);
229          if (threadGroups > 0)
230          {
231              _sharpSilhouetteEdgeFinder.Dispatch(_findSharpSilhouetteEdge_Kernel, threadGroups, 1, 1);
232          }
233  
234          RunEdgesToStrokePasses(threadGroups);
235          RunStrokesToGreasePencilPass(threadGroups);
236      }
237  
238      private void RunEdgesToStrokePasses(int threadGroups)
239      {
240          BindNextPointers(_initialize_Kernel);
241          _sharpEdgesToStrokes.Dispatch(_initialize_Kernel, threadGroups, 1, 1);
242          SwapNextPointers();
243  
244          for (int i = 0; i < NUM_POINTER_JUMP_ITERATIONS; ++i)
245          {
246              BindNextPointers(_reduce_Kernel);
247              _sharpEdgesToStrokes.Dispatch(_reduce_Kernel, threadGroups, 1, 1);
248              SwapNextPointers();
249          }
250              
251          BindNextPointers(_resetNext_Kernel);
252          _sharpEdgesToStrokes.Dispatch(_resetNext_Kernel, threadGroups, 1, 1);
253          SwapNextPointers();
254          
255          for (int i = 0; i < NUM_POINTER_JUMP_ITERATIONS; ++i)
256          {
257              BindNextPointers(_findStrokeTail_Kernel);
258              _sharpEdgesToStrokes.Dispatch(_findStrokeTail_Kernel, threadGroups, 1, 1);
259              SwapNextPointers();
260          }
261  
262          BindNextPointers(_resetNext_Kernel);
263          _sharpEdgesToStrokes.Dispatch(_resetNext_Kernel, threadGroups, 1, 1);
264          SwapNextPointers();
265  
266          _sharpEdgesToStrokes.Dispatch(_initDistances_Kernel, threadGroups, 1, 1);
267  
268          for (int i = 0; i < 8; ++i)
269          {
270              BindNextPointers(_listRank_Kernel);
271              _sharpEdgesToStrokes.Dispatch(_listRank_Kernel, threadGroups, 1, 1);
272              SwapNextPointers();
273          }
274      }
275  
276      private void RunStrokesToGreasePencilPass(int threadGroups)
277      {
278          _numStrokesCounterBuffer.SetData(new[] { 0u });
279          _numStrokePointsCounterBuffer.SetData(new[] { 0u });
280              
281          _strokesToGreasePencilStrokes.Dispatch(_setStrokeLengthAtTail_Kernel, threadGroups, 1, 1);
282          _strokesToGreasePencilStrokes.Dispatch(_calcStrokeOffsets_Kernel, threadGroups, 1, 1);
283          _strokesToGreasePencilStrokes.Dispatch(_invalidateEntries_Kernel, threadGroups, 1, 1);
284          
285          _strokesToGreasePencilStrokes.SetFloat(RadiusMultiplier, radiusMultiplier);
286          _strokesToGreasePencilStrokes.Dispatch(_sorter_Kernel, threadGroups, 1, 1);
287      }
288  
289      private void DebugStrokes()
290      {
291          SilhouetteStrokeEdge[] strokes = new SilhouetteStrokeEdge[CornerCount];
292          _strokesBuffer.GetData(strokes);
293  
294          int printCount = 0;
295          for (int j = 0; j < strokes.Length && printCount < 10; j++)
296          {
297              if (strokes[j].adj != INVALID && strokes[j].adj != ADJ_NONE)
298              {
299                  Debug.Log($"Stroke[{j}] pos={strokes[j].pos} adj={strokes[j].adj} minPoint={strokes[j].minPoint} rank={strokes[j].rank} dist={strokes[j].distFromTail:F4}");
300                  printCount++;
301              }
302          }
303      }
304  
305      private void DebugGp()
306      {
307          var gpStrokes = new GreasePencilRenderer.GreasePencilStrokeVert[2*FaceCount];
308          _denseStrokesBuffer.GetData(gpStrokes);
309          
310          for (int j = 0; j < gpStrokes.Length; j++)
311          {
312              Debug.Log($"GP Stroke[{j}] pos={gpStrokes[j].pos} mat={gpStrokes[j].mat} strokePointIdx={gpStrokes[j].point_id}");
313          }
314      }
315  
316      void OnDestroy()
317      {
318          _verticesBuffer?.Release();
319          _indicesBuffer?.Release();
320          _adjIndicesBuffer?.Release();
321          _strokesBuffer?.Release();
322          _nextPointerSrcBuffer?.Release();
323          _nextPointerDstBuffer?.Release();
324          _numStrokesCounterBuffer?.Release();
325          _numStrokePointsCounterBuffer?.Release();
326          _denseStrokesBuffer?.Release();
327          _colorBuffer?.Release();
328  
329          if (_sharpSilhouetteEdgeFinder != null) Destroy(_sharpSilhouetteEdgeFinder);
330          if (_sharpEdgesToStrokes != null) Destroy(_sharpEdgesToStrokes);
331          if (_strokesToGreasePencilStrokes != null) Destroy(_strokesToGreasePencilStrokes);
332      }
333      
334      /// <summary>
335      /// For each corner, finds the index of its adjacent corner. The adjacent corner of corner C is the corner at the same position as C and part of the face that is adjacent to the edge that is clockwise from C.
336      /// </summary>
337      /// <param name="triangles"></param>
338      /// <param name="positions"></param>
339      /// <returns>array of length same as <paramref name="triangles"/> containing indices of the adjacent corners</returns>
340      private static int[] CalculateCornerAdjacency(int[] triangles, Vector3[] positions)
341      {
342          if (triangles == null) throw new ArgumentNullException(nameof(triangles));
343          if (positions == null) throw new ArgumentNullException(nameof(positions));
344          var cornerCount = triangles.Length;
345          if (cornerCount % 3 != 0) throw new ArgumentException("Triangle array length must be a multiple of 3.", nameof(triangles));
346  
347          var faceCount = cornerCount / 3;
348          int[] adj = new int[cornerCount];
349          for (int i = 0; i < adj.Length; i++) adj[i] = INVALID;
350  
351          var edgeMap = new Dictionary<EdgeKey, List<EdgeCorner>>(cornerCount);
352  
353          for (int f = 0; f < faceCount; f++)
354          {
355              int baseIdx = f * 3;
356              for (int c = 0; c < 3; c++)
357              {
358                  int currIdx = triangles[baseIdx + c];
359                  int nextIdx = triangles[baseIdx + ((c + 1) % 3)];
360                  Vector3 p0 = positions[currIdx];
361                  Vector3 p1 = positions[nextIdx];
362                  var key = new EdgeKey(p0, p1);
363                  if (!edgeMap.TryGetValue(key, out var list))
364                  {
365                      list = new List<EdgeCorner>(2);
366                      edgeMap[key] = list;
367                  }
368                  list.Add(new EdgeCorner(baseIdx + c));
369              }
370          }
371  
372          foreach (var kvp in edgeMap)
373          {
374              var corners = kvp.Value;
375              if (corners.Count < 1) continue;
376              if (corners.Count == 1)
377              {
378                  adj[corners[0].CornerIndex] = INVALID;
379                  continue;
380              }
381              if (corners.Count > 2)
382              {
383                  Debug.LogWarning("Non Manifold edges found in mesh");
384                  foreach (var corner in corners)
385                  {
386                      adj[corner.CornerIndex] = INVALID;
387                  }
388                  continue;
389              }
390              
391              // corners.Count == 2
392              int c1 = corners[0].CornerIndex;
393              int c2 = corners[1].CornerIndex;
394  
395              adj[c1] = (c2 + 1) % 3 + c2 / 3 * 3;
396              adj[c2] = (c1 + 1) % 3 + c1 / 3 * 3;
397          }
398  
399          return adj;
400      }
401  
402      private readonly struct EdgeCorner
403      {
404          public EdgeCorner(int cornerIndex)
405          {
406              CornerIndex = cornerIndex;
407          }
408  
409          public int CornerIndex { get; }
410      }
411  
412      private readonly struct EdgeKey : IEquatable<EdgeKey>
413      {
414          private readonly Vector3 _a;
415          private readonly Vector3 _b;
416  
417          public EdgeKey(Vector3 p0, Vector3 p1)
418          {
419              if (ComparePos(p0, p1) <= 0)
420              {
421                  _a = p0;
422                  _b = p1;
423              }
424              else
425              {
426                  _a = p1;
427                  _b = p0;
428              }
429          }
430  
431          public bool Equals(EdgeKey other) => PositionsEqual(_a, other._a) && PositionsEqual(_b, other._b);
432          public override bool Equals(object obj) => obj is EdgeKey other && Equals(other);
433  
434          public override int GetHashCode()
435          {
436              unchecked
437              {
438                  int h1 = HashVector(_a);
439                  int h2 = HashVector(_b);
440                  return (h1 * 397) ^ h2;
441              }
442          }
443  
444          private static int HashVector(Vector3 v)
445          {
446              unchecked
447              {
448                  int hx = v.x.GetHashCode();
449                  int hy = v.y.GetHashCode();
450                  int hz = v.z.GetHashCode();
451                  return ((hx * 397) ^ hy) * 397 ^ hz;
452              }
453          }
454  
455          private static int ComparePos(Vector3 a, Vector3 b)
456          {
457              if (a.x < b.x) return -1; if (a.x > b.x) return 1;
458              if (a.y < b.y) return -1; if (a.y > b.y) return 1;
459              if (a.z < b.z) return -1; if (a.z > b.z) return 1;
460              return 0;
461          }
462      }
463  
464      private static bool PositionsEqual(Vector3 a, Vector3 b)
465      {
466          const float epsilon = 1e-6f;
467          return Mathf.Abs(a.x - b.x) <= epsilon && Mathf.Abs(a.y - b.y) <= epsilon && Mathf.Abs(a.z - b.z) <= epsilon;
468      }
469  
470      public int GetMaximumBufferLength()
471      {
472          return CornerCount;
473      }
474      public GraphicsBuffer GetStrokeBuffer()
475      {
476          return _denseStrokesBuffer;
477      }
478      public GraphicsBuffer GetColorBuffer()
479      {
480          return _colorBuffer;
481      }
482  }