1  #pragma kernel Initialize
  2  #pragma kernel Reduce
  3  #pragma kernel CalculateRanksAndDistances
  4  #pragma kernel FindStrokeTail
  5  #pragma kernel ResetNextPointer
  6  #pragma kernel InitializeRanksAndDistances
  7  
  8  
  9  
 10  #include "silhouette_defines.hh"
 11  
 12  RWStructuredBuffer<StrokeData> _strokes; // read from silhouette pass (the same structured layout)
 13  
 14  StructuredBuffer<uint> _nextPointerSrc;
 15  RWStructuredBuffer<uint> _nextPointerDst; // per-stroke successor index (adjacency)
 16  
 17  uint _NumVerts;
 18  
 19  // Convert float to a lexicographically sortable uint representation (preserves ordering including negatives)
 20  uint FloatToSortableUint(float f)
 21  {
 22      uint u = asuint(f);
 23      // flip sign bit so that integer ordering matches float ordering
 24      return (u & 0x80000000u) ? ~u : (u ^ 0x80000000u);
 25  }
 26  
 27  bool equals(float3 a, float3 b)
 28  {
 29      return (a.x == b.x) && (a.y == b.y) && (a.z == b.z);
 30  }
 31  
 32  [numthreads(64,1,1)]
 33  void Initialize(uint3 id : SV_DispatchThreadID)
 34  {
 35      uint i = id.x;
 36      if (i >= _NumVerts) return;
 37      StrokeData s = _strokes[i];
 38      _strokes[i].minPoint = i;
 39  
 40      int succ = s.adj;
 41      _nextPointerDst[i] = succ;
 42      if (succ >= 0)
 43      {
 44          StrokeData succStroke = _strokes[succ];
 45          if (!equals(succStroke.pos, s.pos))
 46          {
 47              _strokes[succ].flags|=STROKE_FLAG_IS_CHILD;
 48          }
 49      }
 50      
 51  }
 52  
 53  [numthreads(64,1,1)]
 54  void ResetNextPointer(uint3 id : SV_DispatchThreadID)
 55  {
 56      uint i = id.x;
 57      if (i >= _NumVerts) return;
 58      StrokeData s = _strokes[i];
 59      _nextPointerDst[i] = (s.adj >= 0) ? (uint)s.adj : INVALID_UINT;
 60      _strokes[i].flags&=!STROKE_FLAG_IS_CHILD;
 61  }
 62  
 63  
 64  bool lessThan(float3 a, float3 b)
 65  {
 66      if (a.x != b.x) return a.x < b.x;
 67      if (a.y != b.y) return a.y < b.y;
 68      return a.z < b.z;
 69  }
 70  
 71  bool lessThan(StrokeData a, StrokeData b)
 72  {
 73      if (a.adj != b.adj)
 74      {
 75          if (a.adj == ADJ_NONE)
 76              return true;
 77          if (b.adj == ADJ_NONE)
 78              return false;
 79      }
 80      return lessThan(a.pos, b.pos);
 81  }
 82  
 83  
 84  // Pointer-jumping to propagate the minimum point
 85  [numthreads(64,1,1)]
 86  void Reduce(uint3 id : SV_DispatchThreadID)
 87  {
 88      uint i = id.x;
 89      if (i >= _NumVerts) return;
 90      StrokeData s = _strokes[i];
 91      if (s.adj == INVALID)
 92      {
 93          _nextPointerDst[i] = INVALID_UINT;
 94          return;
 95      }
 96  
 97      uint succ = _nextPointerSrc[i];
 98      _nextPointerDst[i] = succ;
 99      if (succ != INVALID_UINT)
100      {
101          if (IsChild(_strokes[succ]) && equals(_strokes[succ].pos, s.pos))
102          {
103              return;
104          }
105          uint succ2hop = _nextPointerSrc[succ];
106          if (succ2hop != INVALID_UINT)
107          {
108              if (!IsChild(_strokes[succ2hop]) && equals(_strokes[succ].pos, _strokes[succ2hop].pos))
109              {
110                  _nextPointerDst[i] = succ2hop;
111                  //TODO: remove this
112                  _strokes[i].adj = succ2hop;
113              }
114          }
115      }
116  }
117  
118  // Pointer-jumping to propagate the minimum point
119  [numthreads(64,1,1)]
120  void FindStrokeTail(uint3 id : SV_DispatchThreadID)
121  {
122      uint i = id.x;
123      if (i >= _NumVerts) return;
124      StrokeData s = _strokes[i];
125      
126      if (IsInvalid(s))
127      {
128          _nextPointerDst[i] = INVALID_UINT;
129          return;
130      }
131  
132      int succ = _nextPointerSrc[i];
133      _nextPointerDst[i] = succ;
134      if (succ >= 0)
135      {
136          uint succMin = _strokes[_strokes[succ].minPoint].minPoint;
137          if (lessThan(_strokes[succMin], _strokes[s.minPoint]))
138          {
139              _strokes[i].minPoint = succMin;
140          }
141          _nextPointerDst[i] = _nextPointerSrc[succ];
142      }
143  }
144  
145  
146  [numthreads(64,1,1)]
147  void InitializeRanksAndDistances(uint3 id : SV_DispatchThreadID)
148  {
149      uint i = id.x;
150      if (i >= _NumVerts) return;
151      StrokeData s = _strokes[i];
152      
153      // zero length edges are invalid
154      if (equals(s.pos, _strokes[s.adj].pos))
155      {
156          _strokes[i].flags |= STROKE_FLAG_IS_INVALID;
157          _strokes[i].distFromTail = 0.0f;
158          _strokes[i].rank = 0u;
159          return;
160      }
161      
162      if (IsInvalid(s))
163      {
164          _strokes[i].distFromTail = 0.0f;
165          _strokes[i].rank = 0u;
166          return;
167      }
168  
169      bool isTail = (i == s.minPoint) || s.adj == ADJ_NONE;
170      if (isTail)
171      {
172          _strokes[i].distFromTail = 0.0f;
173          _strokes[i].rank = 0u;
174      }
175      else
176      {
177          float d = distance(s.pos, _strokes[s.adj].pos);
178          _strokes[i].distFromTail = d;
179          _strokes[i].rank = 1u;
180          
181          _strokes[s.adj].flags|=STROKE_FLAG_IS_CHILD;
182      }
183  }
184  
185  // Pointer-jumping list ranking: compute distance-to-tail (float) and hop count
186  [numthreads(64,1,1)]
187  void CalculateRanksAndDistances(uint3 id : SV_DispatchThreadID)
188  {
189      uint i = id.x;
190      if (i >= _NumVerts) return;
191      StrokeData si = _strokes[i];
192      if (IsInvalid(si))
193      {
194          _nextPointerDst[i] = INVALID_UINT;
195          return;
196      }
197  
198      if (i == si.minPoint)
199      {
200          if (si.adj != ADJ_NONE) _strokes[i].flags |= STROKE_FLAG_CYCLIC;
201          _nextPointerDst[i] = _nextPointerSrc[i];
202          return;
203      }
204  
205      uint succ = _nextPointerSrc[i];
206      _nextPointerDst[i] = succ;
207  
208      bool succIsTail = (succ == si.minPoint);
209  
210      StrokeData ss = _strokes[succ];
211      _strokes[i].distFromTail += ss.distFromTail;
212      _strokes[i].rank += ss.rank;
213  
214      if (succIsTail)
215      {
216          if (ss.adj != ADJ_NONE) _strokes[i].flags |= STROKE_FLAG_CYCLIC;
217      }
218      else
219      {
220          _nextPointerDst[i] = _nextPointerSrc[succ];
221      }
222  }