Kinetic Shape Reconstruction

Converting point clouds into concise polygonal meshes in an automated manner is an enduring problem in computer graphics. Prior works, which typically operate by assembling planar shapes detected from input points, largely overlooked the scalability issue of processing a large number of shapes. As a result, they tend to produce overly simplified meshes with assembling approaches that can hardly digest more than 100 shapes in practice. We propose a shape assembling mechanism that is at least one order of magnitude more efficient, both in time and in number of processed shapes. Our key idea relies upon the design of a kinetic data structure for partitioning the space into convex polyhedra. Instead of slicing all the planar shapes exhaustively as prior methods, we create a partition where shapes grow at constant speed until colliding and forming polyhedra. This simple idea produces a lighter yet meaningful partition with a lower algorithmic complexity than an exhaustive partition. A watertight polygonal mesh is then extracted from the partition with a min-cut formulation. We demonstrate the robustness and efficacy of our algorithm on a variety of objects and scenes in terms of complexity, size, and acquisition characteristics. In particular, we show the method can both faithfully represent piecewise planar structures and approximate freeform objects while offering high resilience to occlusions and missing data.