2D Triangulations from 3D Strokes Using the Leap Motion
Ryan Kehlenbeck
CPE 572 Spring 2017
The purpose of this project was to explore mesh creation using the Leap Motion interface. The Leap Motion allows the user to track their hands and fingers in 3D space. The approach was inspired by Teddy[1] a program for creating 3D meshes from 2D strokes. Although it's sort of backward, this program allows the user to draw strokes in 3D using the Leap Motion and creates a 2D triangulation of the points. This program was implemented in C++ using OpenGL, GLSL, GLEW, GLFW, Eigen, the Leap Motion Library, and a Delaunay Triangulation Library.

Leap Motion
The first step of this project was getting input data from the Leap Motion. The Leap Motion Library is available for multiple platforms[2] and the C++ library was used for this project. The features of the library used were palm tracking and grab angle for the right hand. The palm position is tracked and drawn to the screen as a sphere. The actual palm position reading from the Leap Motion was too jumpy, so the stabilized position was used instead. When the grab angle of the hand, measured between 0 and 180 degrees, is greater than 145 degrees, the hand is considered to be performing a grabbing gesture. When the hand is performing this gesture and changing position, the program stores the hand positions as points of a 3D stroke if there has been a large enough change in angle. For a greater minimum angle, a fewer number of points will be stored. The minimum angle used was scaled based on the distance between the points.

The biggest problem I faced was finding a proper library for triangulating the points. I initially looked at libraries like Triangle[3] and an open source C++ wrapper of Triangle[4], but I had trouble getting both to compile. Eventually I ended up using another Delaunay Triangulation library from GitHub[5]. This library uses the Bowyer-Watson algorithm[6], which is not a Constrained Delaunay Triangulation like the Teddy paper calls for. The result is triangles which do not necessarily include the original segments. The next steps from the Teddy paper for generating a mesh from the triangles would have been to create fan triangles from the triangles touching more than one boundary edge, and to connect the midpoints of the internal edges to create a spine. Once a spine is created, the internal vertices can be moved in the direction perpendicular to the plane the boundary edges are on, and by a magnitude based on distance from the boundary edges. Finally, the areas between the spine and boundary edges are triangulated again, resulting in a very round mesh. However, this has not been implemented in this project.

Lessons Learned
I learned a lot during the implementation of this project. Most of what I learned really revolves around the excessive amount of time I spent trying to compile and link libraries in Visual Studio. I think I could have accomplished much more having not run into this roadblock when adding a triangulation library. I did learn about different types of Delaunay Triangulation and would like to implement one myself in the future. I'm glad I was able to explore the use of the Leap Motion and learn about its features and shortcomings. I was also able to get a lot of practice writing C++ code, using C++ libraries, and drawing lines using OpenGL.
Future Work
This project has inspired a lot of ideas for future work. Better hand stabilization for the Leap Motion could be used for better stroke drawing since the position is either jumpy or slow and stabilized using the default library calls. A constrained delaunay triangulation library for C++ with an interface as simple as the used library used, could be written. And the rest of the mesh generation work from the Teddy paper could be implemented. There is also lots of potential for defining new mesh manipulation and generation techniques for 3D since the techniques from the Teddy paper are based around 2D operations.
[1] Teddy Takeo Igarashi
[2] Leap Motion Developers Leap Motion
[3] Triangle Jonathan Shewchuk
[4] wo80/Triangle GitHub
[5] Bl4ckb0ne/delaunay-triangulation GitHub
[6] Bowyer–Watson Algorithm Wikipedia