The SGI research program has been structured in a novel way in which each project lasts for one or two weeks only. This gives Fellows the opportunity to work with multiple mentors and in different areas of Geometry Processing. A lot of SGI fellows, including me, had wondered how we would be able to finish the projects in such a short period of time. After two weeks, as I pause my first research project at SGI, I am reminded of Professor Solomon’s remark that a surprising amount of work can be done within 1/2 weeks when guided by an expert mentor.
In this post, I have shared the work I have done under the mentorship of Prof. David Levin over the last two weeks.
Optimal Interlocking Parts via Implicit Shape Optimizations
In this project, we explored how to automatically design jigsaw puzzles such that all puzzle pieces are as close to a given input shape \(I\) as possible, while still satisfying the requirement of interlocking.
Lloyd relaxation with Shape Matching metric
As the first step, we needed a rough division of the domain into regions corresponding to puzzle pieces. For this initial division we used Lloyd’s relaxation as it ensured that the pieces would interlock. To create regions similar to the input shape, we employed a new distance metric. This metric is based on shape matching.
Shape Matching metric:
The input shape \(I\) is represented as a collection of points \(V\) on its boundary and is assumed to be of unit size and centered at the origin. Consider a pixel \(p\) and a site \(x\). First the input shape is translated to \(x\) ( \(V \rightarrow V’\)). The value of scaling factor \(s\) that minimizes the distance between \(p\) and the closest point \(V’_i\) on the boundary of the input shape gives us the shape matching metric. \[s^* = \text{arg min} \frac {1} {2}(dist(p, sV’))\]
Pre computing maps
The straightforward implementation for Lloyd’s relaxation that I had been using was iterative and therefore very slow. In fact, testing the algorithm for larger domains or complicated shapes that needed dense sampling of boundary points was infeasible. Therefore, optimizing the algorithm was an immediate requirement. I realized that relative to the site \(x\), the distances would vary around it in exactly the same way. So, computing the distance between each pixel and each site separately during each iteration of Lloyd’s relaxation was redundant and could be avoided by pre-computing a distance map for the given object before starting Lloyd’s relaxation.
Enhancing the shape matching metric
In addition to speeding up the algorithm, the distance maps also helped in determining the next step. As can be seen from the figures above, the maps weren’t smooth. These jumps in distance fields occurred because the shape matching metric worked on a set of discrete points. Optimizing the scaling factor for minimizing distance to the closest edge instead of closest point resolved this.
Shaping the puzzle pieces (In progress)
The initial regions are obtained from Lloyd’s algorithm with the shape matching metric need to be refined so that the final puzzle pieces are highly similar to the input shape \(I\).
I am currently exploring the use of point set registration methods to find the best transformations on the input shape so that it fits the initial regions. These transformations could then be used to inform the next iteration of Lloyd’s algorithm to refine the regions. This process can be repeated until the region stops changing, giving us our final puzzle pieces.
I have thoroughly enjoyed working on this project, and I am looking forward to the next project I would be working on!