3D Scanning, the Bowyer-Watson Algorithm, and Real Time (maybe) Delaunay triangulation.

 

  Wasn't that a mouthful! I'm taking another look at my 3D scanner. I really haven't talked about this scanner very much on this blog, so I've posted a video of it I made earlier this fall as part of my MIT application above. I'll move a good deal of the content from that portion of my application onto this blog over time, so long as it doesn't become too obsolete.

  There's still certainly room for improvement in the scanner itself. Much to it's detriment, it's still mostly manual and requires far too much tweaking on the software side to be actually useful. The hardware itself is also really flimsy. The Knex gearbox you can see in the video above keeps snapping apart if it's brushed wrong. In addition, it's final output is a point cloud, not an actual model. Yea. It's that bad. I have no idea how I got into MIT showing this kind of work off...
  I've been inspired by this - a much more sophisticated way to 3D scan - to improve my own methods. I've already emailed ProFORMA's creator, (Dr.?) Qi Pan, asking if he has recommendations, or if he ever released the promised demo of ProFORMA, but I've decided to work on the assumption that I'm on my own in this for the time being.
  This post will attempt to work on the implementation of basic methods adapted from ProFORMA to turn the point clouds into something coherent. I'm still in the process of porting my existing code to python (and making much needed simplifications to several parts of it.), so I'm going to assume I have a working way to obtain point clouds. In fact, I'm going to be extremely optimistic and assume that at some point I'll have a way to get bits of this point cloud in real time (FYI, I'm thinking of real-time in a 2-10 Hz sense, not a 30Hz sense).
  All this relies heavily on producing the Delaney Triangulation of the pointcloud. If you don't understand the Wikipedia article (or don't want to read it), a Delaney Triangulation is a way obtain a reasonably sparse (and somewhat physically sensible) mesh from a pointcloud. The Bowyer-Watson algorithm is a way to build a Delaney Triangulation by adding a single point at a time to an existing Delaney Triangulation of part of the final pointcloud.
  I've got my own (to my knowledge) way to improve the algorithm a little bit: I'm going to represent the resulting triangulation with a graph.  Simplexes will be nodes, and their shared surfaces (in the 3D case, faces) are edges. While researching the Bowyer-Watson algorithm, I saw a couple different data structures used to represent the Triangulation. All of them improved performance, but none of them worked as naturally as I think a Graph does. The Graph is most obviously advantageous this has comes when identifying the cavity created by the addition of each new point. Since this cavity has to be simply connected, finding it becomes as simple as finding the first invalid simplex and performing a fill algorithm. The cavity itself (and the exterior space) can even be represented as a dummy node (since it's not necessarily a simplex itself), making it easy to identify the interior surfaces.

  Anyways, it's late, and I'm going to catch some sleep. I'll finish this post up (and slap up some code to go with it) in the near future.