Thursday 31 July 2014

Timeline

One obvious very useful feature for most graphics and audio toolset is some form of timeline.

In 4v you have the native one, which with a little effort could become ok (add undo, move keyframes with keyboard, export/import, and better color editor), but in it's current state is at best irritating. It's not as bad as the hlsl code completion in 4v but that's another story ;)

Then you have more standalone ones, vezer looks pretty cool but mac only, so not for me.

You also have duration, which is likely the best but has 2 major flaws, missing scroll and groups. Also opengl rendering would not fit as easily to integrate in my tool.

Then you have this brand new Posh svg, new 4v timeliner, presented as usual as the next big thing which will make your grandmother dance rock and roll again, and so and so.

So first pre alpha release tests were let's call it.... disappointing. Only one track type, no interpolation, and an amount of ui bugs that it could just eat a piece of wood like piranhas would eat my bum.
Next first "public" release is well... appalling, I personally hardly see the point of releasing something in that state, except to show off your incompetence at building user interface.

So first thing you do when you build a timeliner, you prepare a decent track setup, there is NO point showing 5 key frames and one track. So I start to prepare 8 tracks, 40 key frames each (which is really a small setup), and then everything goes laggy, I get 40 % cpu usage (where the hell does that go), selecting and moving several frames just blow up everything, you can't even recover and have to restart the software, usability at it's best.

So well I start to report those issues, and happily suggest that some DirectX11/OpenGL rendering for that type of things would likely fit and scale much nicer, but only reply I get is "yes I know it's slow but I don't care Dx is not as interesting as svg". So I try to explain that well if your ui doesn't scale, you might look for something else, but I get the usual "I don't give a fuck type of attitude which pisses me off so much". We suggested that actually some of the changes could easily make it through the old one (some undo + key) , I get the same I don't give a fuck.

So well I don't really understand the point (and as a user slightly pissed off that you have to pay 500 euros a license to get that type of answer). And I feel really horrified that this took several month to produce, I'm getting really worried about user interface in the next vvvv50, since in current version since there's no will to improve the old version, then it gets decided to produce a brand new ui framework which is as shit, so I got more or less no faith that we will ever have a decently smooth user interface in previous or next gen vvvv.

But let's stop whining and go to the more fun part ;)

So I'm still without a timeliner, since now I got 2  10% baked unusable pieces of junk, and some others which are nice but I can't integrate them.

So since I also mentioned dx11 would be a good candidate, I decided to spend an afternoon doing track renderers. Also that would really prove a point that modern rendering wins against this browser jazz. I also decided to only focus on the rendering for now, since well it's not too hard to hittest and drag a point after all ;)

Main focus is also to of course have some fast rendering, I want a smooth user interface ;)

I just push my tracks into buffers and then render them. I decided to start with color, which is really simple.

Code Snippet
  1. struct ColorKeyFrame
  2. {
  3.     float4 color;
  4.     float time;
  5.     int trackid;
  6. };
  7.  
  8. struct KeyFrameLink
  9. {
  10.     int left;
  11.     int right;
  12. };
  13.  
  14. StructuredBuffer<ColorKeyFrame> ColorKeyFrameBuffer;
  15. StructuredBuffer<KeyFrameLink> ColorLinkBuffer;
  16. StructuredBuffer<float2> TrackOffsetBuffer; //x = top, y = height

Render a bulk of instanced quads, grab color on the left keyframe, color on the right keyframe, position with a map function.

Code Snippet
  1. psInput VS(vsInput input)
  2. {
  3.     psInput output;
  4.  
  5.     KeyFrameLink cl = ColorLinkBuffer[input.ii];    
  6.     ColorKeyFrame left = ColorKeyFrameBuffer[cl.left];
  7.     ColorKeyFrame right = ColorKeyFrameBuffer[cl.right];
  8.     int tid = input.ii;
  9.     tid = tid / cpPerTrack;
  10.     
  11.     float2 pos = input.uv;
  12.     float2 offset = TrackOffsetBuffer[tid];
  13.     
  14.     pos.x = map(pos.x,left.time,right.time);
  15.     pos.x *= 2.0f;
  16.     pos.x -= 1.0f;
  17.     
  18.     pos.y += offset.x;
  19.     pos.y *= offset.y;
  20.         
  21.     output.pos = mul(float4(pos,0,1),tRange);
  22.     output.colstart = left.color;
  23.     output.colend = right.color;
  24.     output.uv = input.uv.x;
  25.     
  26.     return output;
  27. }

Send to the (hardcore) pixel shader:

Code Snippet
  1. float4 PS(psInput input) : SV_Target
  2.   {
  3.     return lerp(input.colstart,input.colend, input.uv);
  4. }

That was so hard ;)

Now let's go for value, positioning keyframe point, well one small Segment instance, just so simple that there's nothing to say about it, now let's build the connections, and let's add  the fact that I want more curves (aka tweens):


Code Snippet
  1. struct ValueKeyFrame
  2. {
  3.     float value;
  4.     float time;
  5.     int trackid;
  6.     int interpolation;
  7. };
  8.  
  9. struct KeyFrameLink
  10. {
  11.     int left;
  12.     int right;
  13. };


Of course usual buffers are there too, we send a PatchListWithOneControlPoint batch for each connection (we don't need 2, that's beautiful).

Code Snippet
  1. struct linkData
  2. {
  3.     int left : CPOINT0;
  4.     int right : CPOINT1;
  5. };

Now we only need to pass trough keyframe IDs till we reach the domain shader:

Code Snippet
  1. [domain("isoline")]
  2. psInput DS(hsConstantOutput input, OutputPatch<linkData, 1> op, float2 uv : SV_DomainLocation)
  3. {
  4.     psInput output;
  5.     float t = uv.x;
  6.     
  7.     ValueKeyFrame kl = ValueKeyFrameBuffer[op[0].left];
  8.     ValueKeyFrame kr = ValueKeyFrameBuffer[op[0].right];
  9.     
  10.     float2 start = ComputePosition(op[0].left);
  11.     float2 end = ComputePosition(op[0].right);
  12.  
  13.     float x = lerp(start.x,end.x,t);
  14.     float y = lerp(start.y,end.y,lerpFunc(t,kl.interpolation));
  15.     
  16.     float2 pos = float2(x,y);
  17.     output.pos = mul(float4(pos,0.0f, 1.0f), tRange);
  18.  
  19.     return output;
  20. }

lerpFunc selects interpolation function, which are all the basic tween modes.

Now well, bang track is simple instanced quad or line, nothing to speak about.

Then let's add wave track, I thought it would be a bit complicated, but that was so easy it's even embarrassing. So first get your favorite audio API (I used Bass). Load a music file, read all the samples as float and feed to a big fat structured buffer (float or float2). I chose float since at least i push any type of multi channel later.

Render a quad, then here is the insane pixel shader:

Code Snippet
  1. float4 PS(psInput input) : SV_Target
  2.   {
  3.     uint cnt, stride;
  4.     WaveDataBuffer.GetDimensions(cnt,stride);    
  5.     float off = cnt;
  6.     float xpos = input.uv.x * off;
  7.     
  8.     float sampleleft = WaveDataBuffer[xpos*2];
  9.     float sampleright = WaveDataBuffer[xpos*2+1];
  10.     float y = input.uv.y;    
  11.     y *= 2.0f;
  12.     y -= 1.0f;
  13.     
  14.     return (abs(sampleleft) > abs(y)) + 0.1f;
  15. }

That was hardcore, I could do a bit of oversampling for sure, but it already looks pretty ok.

So here we go, then you add a small ruler.

And now pushing some 4000 keyframes:


Unzoomed view:


And let's push the ui a little bit, since I said I wanted it to scale, 14K keyframes:



3 hours well spent, I now got a pretty decent scalable timeline renderer, which is a pretty huge step forward (80 fps rendering every frame, no caching is rather good so far).

To conclude, hlsl > all :)

Wednesday 16 July 2014

OpenCV, Compute and immutability

I know some of my friends use rather regularly the very nice OpenCV contribution from Elliot Woods.

Most times people use the Camera/Projector calibration tool. This works pretty well (could do with some ui improvemements), but most times I wanted to look at it I always end up with the same problem, you need to download the whole Image pack.

This is a great pack of course, but in that scenario, downloading a 500 megs bulk of dlls (which can also depend of version) is let's call "not ideal". Ok in our times with super fast internet you would think it's ok, but well, my hard drive doesn't like it (so I don't either). All that to call a single opencv function!

So just wrote a small P/Invoke dll (and use static library linking instead of dynamic), one 20 lines of dynamic plugin to call the function and here we go, 1 megabyte dll which doesn't need any other external. I like minimalism ;)

I remember I wanted to do this for a while, and considering the amount of (no) time it took I fell very embarrassed )



Now after this there's a (few) things I wanted to add/change in that tool.

First the point selection is nice in some cases, but not so nice in others. Basically current technique renders object space coordinates in a texture, then you just sample that texture.

If you have a model crammed with small polygons it's fine enough, but what I would simply like to do in general is just get closest vertex from a triangle raycast. Since I don't want to blow up 100k rays in cpu, and 3d model is already in GPU (as obviously we want to render it), let's do a little bit of compute shader ;)

So first let's load the model into a big fat buffer (to avoid subsets annoyance, simple prefix sum on indices), then we have the following data structures:

Code Snippet
  1. StructuredBuffer<float3> PositionBuffer : POSITIONBUFFER;
  2. StructuredBuffer<uint3> IndexBuffer : INDEXBUFFER;
  3.  
  4. AppendStructuredBuffer<float3> AppendVertexHitBuffer : APPENDVERTEXHITBUFFER;
  5.  
  6. float3 raypos : RAYPOSITION;
  7. float3 raydir : RAYDIRECTION;
  8.  
  9. int FaceCount : FACECOUNT;
  10.  
  11. float eps : EPSILON = 0.000001f;

Pretty simple, mouse position is converted back to ray, and we use append buffer to get potential candidates (since we might hit several triangles).

Now here is our ray shader (I omit the ray formula, which is the same as in http://www.geometrictools.com/ )

Code Snippet
  1. [numthreads(64,1,1)]
  2. void CS_RayTriangle(uint3 dtid : SV_DispatchThreadID)
  3. {
  4.     if (dtid.x >= FaceCount) { return; }
  5.     
  6.     uint3 face = IndexBuffer[dtid.x];
  7.     
  8.     float3 p1 = PositionBuffer[face.x];
  9.     float3 p2 = PositionBuffer[face.y];
  10.     float3 p3 = PositionBuffer[face.z];
  11.     
  12.     float3 diff = raypos - p1;
  13.     float3 e1 = p2 - p1;
  14.     float3 e2 = p3 - p1;
  15.     float3 n = normalize(cross(e1,e2));
  16.     
  17.     float DdN = dot(raydir,n);
  18.     float fsign;
  19.     
  20.     bool hit = true;
  21.  
  22.     //Do you rayhit
  23.     
  24.     if (hit)
  25.     {
  26.         AppendVertexHitBuffer.Append(p1);
  27.         AppendVertexHitBuffer.Append(p2);
  28.         AppendVertexHitBuffer.Append(p3);
  29.     }
  30. }

Now when we hit a triangle, we append 3 vertices as "candidates", we now need to find the one closest to us. We could readback filtered data (using CopyResourceRegion), and finish computation on CPU, but that's not fun, so let's continue ;)

First to think option is to sort the data, but that's expensive, we only want the closest element.

So first let's process all elements and write the closest distance into a single buffer:

Code Snippet
  1. [numthreads(64,1,1)]
  2. void CS_MinDistance(uint3 dtid : SV_DispatchThreadID)
  3. {
  4.     if (dtid.x >= VertexHitCountBuffer.Load(0)) { return; }
  5.     
  6.     float3 p = VertexHitBuffer[dtid.x];
  7.     
  8.     float d = distance(raypos,p);
  9.     uint dummy;    
  10.     InterlockedMin(RWMinDistanceBuffer[0],asuint(d),dummy);
  11. }

Now we need to filter closest element:

Code Snippet
  1. [numthreads(64,1,1)]
  2. void CS_StoreIndex(uint3 dtid : SV_DispatchThreadID)
  3. {
  4.     if (dtid.x >= VertexHitCountBuffer.Load(0)) { return; }
  5.     
  6.     float3 p = VertexHitBuffer[dtid.x];
  7.     float d = distance(raypos,p);
  8.     uint ud = asuint(d);
  9.     
  10.     uint mind = MinDistanceBuffer[0];    
  11.     InterlockedCompareStore(RWMinElementBuffer[0], mind,ud);
  12. }

Please note that we don't store position directly since interlocked operations are only allowed on int/uint type. Also we don't handle case if we have more than one candidate, this is easy to replace Store by append (but anyway at some point we need to decide which point we select).

And just get position:

Code Snippet
  1. [numthreads(1,1,1)]
  2. void CS_ExtractPosition(uint3 dtid : SV_DispatchThreadID)
  3. {
  4.     uint idx = RWMinElementBuffer[0];
  5.     RWPositionBuffer[0] = VertexHitBuffer[idx];
  6. }

Copy those 12 bytes back in your CPU and you have your closest vertex.

One part of the morning well spent )

Now one feature which is always useful for a good editor (since at the end we edit points), if of course some form of undo/redo.

You have three main ways to implement undo:

  • For each action, use one function to update your model and one function to revert it. THis can be really cumbersome and error prone.
  • Serialize the state, and on undo create a new (or part modified) state from serialized data
  • Use immutable state
I have much growing interest into using more immutable in general, this is safer and i like the concept around it (ok it doesn't map well everywhere and can consume memory), but in that case (something like 10 points and couple projectors data), this sounds like a good use case.

So here is a calibration point:

Code Snippet
  1. public class CalibrationPoint
  2. {
  3.     private readonly Vector2 screenPosition;
  4.     private readonly Vector3 objectPosition;
  5.  
  6.     public CalibrationPoint(Vector2 screenPosition, Vector3 objectPosition)
  7.     {
  8.         this.screenPosition = screenPosition;
  9.         this.objectPosition = objectPosition;
  10.     }
  11.  
  12.     public Vector2 ScreenPosition
  13.     {
  14.         get { return this.screenPosition; }
  15.     }
  16.  
  17.     public Vector3 ObjectPosition
  18.     {
  19.         get { return this.objectPosition; }
  20.     }
  21. }

You can see that once we create our point, we can't change properties anymore.

No to update properties, instead of setting data directly, we return a new point. There's a little way to help memory, if property is the same we return the same instance:

Code Snippet
  1. public CalibrationPoint SetScreenPosition(Vector2 screenPosition)
  2. {
  3.     return this.screenPosition == screenPosition ? this : new CalibrationPoint(screenPosition, this.objectPosition);
  4. }
  5.  
  6. public CalibrationPoint SetObjectPosition(Vector3 objectPosition)
  7. {
  8.     return this.objectPosition == objectPosition ? this : new CalibrationPoint(this.screenPosition, objectPosition);
  9. }
  10.  
  11. public CalibrationPoint Set(Vector2 screenPosition, Vector3 objectPosition)
  12. {
  13.     return this.objectPosition == objectPosition &&
  14.         this.screenPosition == screenPosition ? this : new CalibrationPoint(screenPosition, objectPosition);
  15. }

Now do the same for Projector and calibration data:

Code Snippet
  1. public class Projector
  2. {
  3.     private readonly string name;
  4.     private readonly IEnumerable<CalibrationPoint> points;
  5.  
  6.     public Projector(string name, IEnumerable<CalibrationPoint> points)
  7.     {
  8.         if (name == null)
  9.         {
  10.             throw new ArgumentNullException("name");
  11.         }
  12.         if (points == null)
  13.         {
  14.             throw new ArgumentNullException("points");
  15.         }
  16.         this.name = name;
  17.         this.points = points;
  18.     }
  19.  
  20.     public string Name
  21.     {
  22.         get { return this.name; }
  23.     }
  24.  
  25.     public IEnumerable<CalibrationPoint> Points
  26.     {
  27.         get { return this.points; }
  28.     }
  29. }

Some of the functions to modify (create new) state:

Code Snippet
  1. public Projector AddPoint(Vector2 screenPosition, Vector3 objectPosition)
  2. {
  3.     var point = new CalibrationPoint(screenPosition, objectPosition);
  4.  
  5.     return new Projector(this.name, this.points.Concat(new CalibrationPoint[] { point }));
  6. }
  7.  
  8. public Projector RemovePoint(CalibrationPoint point)
  9. {
  10.     return new Projector(this.name, this.points.Where(p => p != point));
  11. }

Calibration class:

Code Snippet
  1. public class Calibration
  2. {
  3.     private readonly IEnumerable<Projector> projectors;
  4.     private readonly CalibrationSettings settings;
  5.  
  6.     public Calibration(CalibrationSettings settings, IEnumerable<Projector> projectors)
  7.     {
  8.         if (settings == null)
  9.         {
  10.             throw new ArgumentNullException("settings");
  11.         }
  12.         if (projectors == null)
  13.         {
  14.             throw new ArgumentNullException("projectors");
  15.         }
  16.         this.settings = settings;
  17.         this.projectors = projectors;
  18.     }
  19. }

And to update projector data:

Code Snippet
  1. public Calibration UpdateProjector(Projector oldProjector, Projector newProjector)
  2. {
  3.     if (oldProjector == newProjector)
  4.     {
  5.         return this;
  6.     }
  7.     else
  8.     {
  9.         var projs = this.projectors.ToList();
  10.         int idx = projs.IndexOf(oldProjector);
  11.  
  12.         if (idx >= 0)
  13.         {
  14.             projs[idx] = newProjector;
  15.             return new Calibration(this.settings, projs);
  16.         }
  17.         else
  18.         {
  19.             throw new ArgumentException("oldProjector", "This projector is not part of this calibration data");
  20.         }
  21.     }
  22. }

I could do argument check first of course, and you can use some "Builder classes" to maintain those updates, but you get the point.

Now someone would say, this is a lot of work for simple classes....

But now once you are done with this (not so bad) boilerplate, here is out undo stack:

Code Snippet
  1. public class CalibrationUndoStack
  2. {
  3.     private readonly Stack<Calibration> undoStack;
  4.  
  5.     public CalibrationUndoStack(Calibration initial)
  6.     {
  7.         this.undoStack = new Stack<Calibration>();
  8.         this.undoStack.Push(initial);
  9.     }
  10.  
  11.     public void Apply(Func<Calibration, Calibration> commandFunc)
  12.     {
  13.         var newState = commandFunc(this.Current);
  14.         if (newState != this.Current)
  15.         {
  16.             this.undoStack.Push(newState);
  17.         }
  18.     }
  19.  
  20.     public Calibration Current
  21.     {
  22.         get { return this.undoStack.Peek(); }
  23.     }
  24.  
  25.     public Calibration Undo()
  26.     {
  27.         return this.CanUndo ? this.undoStack.Pop() : this.undoStack.Peek();
  28.     }
  29.  
  30.     public bool CanUndo
  31.     {
  32.         get { return this.undoStack.Count > 1; }
  33.     }
  34. }

As you can see, since we always return a new state, we pass a lambda to the stack, and if object has been modified (eg: function returns a new state), then we push our new state. That's how easy that is.

To implement update commands becomes as trivial as :

Code Snippet
  1. public static Calibration AddProjector(Calibration c, string name)
  2. {
  3.     return c.AddProjector(name);
  4. }
  5.  
  6. public static Calibration RenameProjector(Calibration state, Projector projector, string newname)
  7. {
  8.     var p = projector.SetName(newname);
  9.     return state.UpdateProjector(projector, p);
  10. }
  11.  
  12. public static Calibration AddPoint(Calibration state, Projector projector, Vector2 screen, Vector3 obj)
  13. {
  14.     var p = projector.AddPoint(screen, obj);
  15.     return state.UpdateProjector(projector, p);
  16. }
  17.  
  18. public static Calibration SetScreenPoint(Calibration state, Projector projector, CalibrationPoint point, Vector2 screen)
  19. {
  20.     var newPoint = point.SetScreenPosition(screen);
  21.     var newProjector = projector.UpdatePoint(point, newPoint);
  22.     return state.UpdateProjector(projector, newProjector);
  23.  
  24. }

And as you notice, this looks pretty verbose, here is how to do the same in f# (I love type inference, amongst may other things)

Code Snippet
  1. module CalibrationCommandsFS =
  2.  
  3.     let addprojector (c:Calibration,n) = c.AddProjector(n);
  4.     
  5.     let renameprojector(c:Calibration,p, n) = c.UpdateProjector(p,p.SetName(n))
  6.  
  7.     let addpoint(c:Calibration,p,s,o) = c.UpdateProjector(p,p.AddPoint(s,o))
  8.  
  9.     let setscreenpoint(c:Calibration,proj,pt,s) = c.UpdateProjector(proj,proj.UpdatePoint(pt,pt.SetScreenPosition(s)))

And to operate on calibration:

Code Snippet
  1. let x = new CalibrationUndoStack()
  2.  
  3. let s = new CalibrationSettings(Matrix.Identity)
  4. let empty  = []
  5. let c = new Calibration(s, [])
  6.  
  7. x.Apply(fun c -> addprojector(c,"hello"))

That's it for now, but likely more f# soon ;)