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

31. [numthreads(64,1,1)]
32. void CS_RayTriangle(uint3 dtid : SV_DispatchThreadID)
33. {
34.     if (dtid.x >= FaceCount) { return; }
35.     
36.     uint3 face = IndexBuffer[dtid.x];
37.     
38.     float3 p1 = PositionBuffer[face.x];
39.     float3 p2 = PositionBuffer[face.y];
40.     float3 p3 = PositionBuffer[face.z];
41.     
42.     float3 diff = raypos - p1;
43.     float3 e1 = p2 - p1;
44.     float3 e2 = p3 - p1;
45.     float3 n = normalize(cross(e1,e2));
46.     
47.     float DdN = dot(raydir,n);
48.     float fsign;
49.     
50.     bool hit = true;
51.  
52.     //Do you rayhit
53.     
54.     if (hit)
55.     {
56.         AppendVertexHitBuffer.Append(p1);
57.         AppendVertexHitBuffer.Append(p2);
58.         AppendVertexHitBuffer.Append(p3);
59.     }
60. }

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

72. [numthreads(64,1,1)]
73. void CS_MinDistance(uint3 dtid : SV_DispatchThreadID)
74. {
75.     if (dtid.x >= VertexHitCountBuffer.Load(0)) { return; }
76.     
77.     float3 p = VertexHitBuffer[dtid.x];
78.     
79.     float d = distance(raypos,p);
80.     uint dummy;    
81.     InterlockedMin(RWMinDistanceBuffer[0],asuint(d),dummy);
82. }

Now we need to filter closest element:

Code Snippet

84. [numthreads(64,1,1)]
85. void CS_StoreIndex(uint3 dtid : SV_DispatchThreadID)
86. {
87.     if (dtid.x >= VertexHitCountBuffer.Load(0)) { return; }
88.     
89.     float3 p = VertexHitBuffer[dtid.x];
90.     float d = distance(raypos,p);
91.     uint ud = asuint(d);
92.     
93.     uint mind = MinDistanceBuffer[0];    
94.     InterlockedCompareStore(RWMinElementBuffer[0], mind,ud);
95. }

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

97. [numthreads(1,1,1)]
98. void CS_ExtractPosition(uint3 dtid : SV_DispatchThreadID)
99. {
100.     uint idx = RWMinElementBuffer[0];
101.     RWPositionBuffer[0] = VertexHitBuffer[idx];
102. }

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

10. public class CalibrationPoint
11. {
12.     private readonly Vector2 screenPosition;
13.     private readonly Vector3 objectPosition;
14.  
15.     public CalibrationPoint(Vector2 screenPosition, Vector3 objectPosition)
16.     {
17.         this.screenPosition = screenPosition;
18.         this.objectPosition = objectPosition;
19.     }
20.  
21.     public Vector2 ScreenPosition
22.     {
23.         get { return this.screenPosition; }
24.     }
25.  
26.     public Vector3 ObjectPosition
27.     {
28.         get { return this.objectPosition; }
29.     }
30. }

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

31. public CalibrationPoint SetScreenPosition(Vector2 screenPosition)
32. {
33.     return this.screenPosition == screenPosition ? this : new CalibrationPoint(screenPosition, this.objectPosition);
34. }
35.  
36. public CalibrationPoint SetObjectPosition(Vector3 objectPosition)
37. {
38.     return this.objectPosition == objectPosition ? this : new CalibrationPoint(this.screenPosition, objectPosition);
39. }
40.  
41. public CalibrationPoint Set(Vector2 screenPosition, Vector3 objectPosition)
42. {
43.     return this.objectPosition == objectPosition &&
44.         this.screenPosition == screenPosition ? this : new CalibrationPoint(screenPosition, objectPosition);
45. }

Now do the same for Projector and calibration data:

Code Snippet

10. public class Projector
11. {
12.     private readonly string name;
13.     private readonly IEnumerable<CalibrationPoint> points;
14.  
15.     public Projector(string name, IEnumerable<CalibrationPoint> points)
16.     {
17.         if (name == null)
18.         {
19.             throw new ArgumentNullException("name");
20.         }
21.         if (points == null)
22.         {
23.             throw new ArgumentNullException("points");
24.         }
25.         this.name = name;
26.         this.points = points;
27.     }
28.  
29.     public string Name
30.     {
31.         get { return this.name; }
32.     }
33.  
34.     public IEnumerable<CalibrationPoint> Points
35.     {
36.         get { return this.points; }
37.     }
38. }

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

Code Snippet

44. public Projector AddPoint(Vector2 screenPosition, Vector3 objectPosition)
45. {
46.     var point = new CalibrationPoint(screenPosition, objectPosition);
47.  
48.     return new Projector(this.name, this.points.Concat(new CalibrationPoint[] { point }));
49. }
50.  
51. public Projector RemovePoint(CalibrationPoint point)
52. {
53.     return new Projector(this.name, this.points.Where(p => p != point));
54. }

Calibration class:

Code Snippet

10. public class Calibration
11. {
12.     private readonly IEnumerable<Projector> projectors;
13.     private readonly CalibrationSettings settings;
14.  
15.     public Calibration(CalibrationSettings settings, IEnumerable<Projector> projectors)
16.     {
17.         if (settings == null)
18.         {
19.             throw new ArgumentNullException("settings");
20.         }
21.         if (projectors == null)
22.         {
23.             throw new ArgumentNullException("projectors");
24.         }
25.         this.settings = settings;
26.         this.projectors = projectors;
27.     }
28. }

And to update projector data:

Code Snippet

41. public Calibration UpdateProjector(Projector oldProjector, Projector newProjector)
42. {
43.     if (oldProjector == newProjector)
44.     {
45.         return this;
46.     }
47.     else
48.     {
49.         var projs = this.projectors.ToList();
50.         int idx = projs.IndexOf(oldProjector);
51.  
52.         if (idx >= 0)
53.         {
54.             projs[idx] = newProjector;
55.             return new Calibration(this.settings, projs);
56.         }
57.         else
58.         {
59.             throw new ArgumentException("oldProjector", "This projector is not part of this calibration data");
60.         }
61.     }
62. }

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

10. public class CalibrationUndoStack
11. {
12.     private readonly Stack<Calibration> undoStack;
13.  
14.     public CalibrationUndoStack(Calibration initial)
15.     {
16.         this.undoStack = new Stack<Calibration>();
17.         this.undoStack.Push(initial);
18.     }
19.  
20.     public void Apply(Func<Calibration, Calibration> commandFunc)
21.     {
22.         var newState = commandFunc(this.Current);
23.         if (newState != this.Current)
24.         {
25.             this.undoStack.Push(newState);
26.         }
27.     }
28.  
29.     public Calibration Current
30.     {
31.         get { return this.undoStack.Peek(); }
32.     }
33.  
34.     public Calibration Undo()
35.     {
36.         return this.CanUndo ? this.undoStack.Pop() : this.undoStack.Peek();
37.     }
38.  
39.     public bool CanUndo
40.     {
41.         get { return this.undoStack.Count > 1; }
42.     }
43. }

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

13. public static Calibration AddProjector(Calibration c, string name)
14. {
15.     return c.AddProjector(name);
16. }
17.  
18. public static Calibration RenameProjector(Calibration state, Projector projector, string newname)
19. {
20.     var p = projector.SetName(newname);
21.     return state.UpdateProjector(projector, p);
22. }
23.  
24. public static Calibration AddPoint(Calibration state, Projector projector, Vector2 screen, Vector3 obj)
25. {
26.     var p = projector.AddPoint(screen, obj);
27.     return state.UpdateProjector(projector, p);
28. }
29.  
30. public static Calibration SetScreenPoint(Calibration state, Projector projector, CalibrationPoint point, Vector2 screen)
31. {
32.     var newPoint = point.SetScreenPosition(screen);
33.     var newProjector = projector.UpdatePoint(point, newPoint);
34.     return state.UpdateProjector(projector, newProjector);
35.  
36. }

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

6. module CalibrationCommandsFS =
7.  
8.     let addprojector (c:Calibration,n) = c.AddProjector(n);
9.     
10.     let renameprojector(c:Calibration,p, n) = c.UpdateProjector(p,p.SetName(n))
11.  
12.     let addpoint(c:Calibration,p,s,o) = c.UpdateProjector(p,p.AddPoint(s,o))
13.  
14.     let setscreenpoint(c:Calibration,proj,pt,s) = c.UpdateProjector(proj,proj.UpdatePoint(pt,pt.SetScreenPosition(s)))

And to operate on calibration:

Code Snippet

17. let x = new CalibrationUndoStack()
18.  
19. let s = new CalibrationSettings(Matrix.Identity)
20. let empty  = []
21. let c = new Calibration(s, [])
22.  
23. x.Apply(fun c -> addprojector(c,"hello"))

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