Kinetic Shape Reconstruction

Jean-Philippe Bauchet (1) , Florent Lafarge (1)

1 TITANE - Geometric Modeling of 3D Environments

Converting point clouds into concise polygonal meshes in an automated manner is an enduring problem in Computer Graphics. Prior work, 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 one hundred shapes in practice. We propose a shape assembling mechanism which is at least one order 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 approximating freeform objects while offering high resilience to occlusions and missing data.

Mots clés: piecewise-planar geometry; Surface reconstruction; Surface approximation; polygonal surface mesh; kinetic framework; point clouds; Mesh models; Parametric curve; surface approximation; surface models; CCS Concepts; Computing methodologies

Domaines: Mathématique discrète [cs.DM]; Géométrie algorithmique [cs.CG]

Jean-Philippe Bauchet, Florent Lafarge. Kinetic Shape Reconstruction. ACM Transactions on Graphics, 2020. ⟨hal-02924409⟩