V4PCS: Volumetric 4pcs algorithm for global registration

With the advances in hardware and process development, additive manufacturing is realizing a new paradigm: mass customization. There are massive human-related data in mass customization, but there are also many similarities in masscustomized products. Therefore, reusing information can facilitate mass customization and create unprecedented opportunities in advancing the theory, method, and practice of design for mass-customized products. To enable information reuse, different models have to be aligned so that their similarity can be identified. This alignment is commonly known as the global registration that finds an optimal rigid transformation to align two three-dimensional shapes (scene and model) without any assumptions on their initial positions. The Super 4-Points Congruent Sets (S4PCS) is a popular algorithm used for this shape registration. While S4PCS performs the registration using a set of 4 coplanar points, we find that incorporating the volumetric information of the models can improve the robustness and the efficiency of the algorithm, which are particularly important for mass customization. In this paper, we propose a novel algorithm, Volumetric 4PCS (V4PCS), to extend the 4 coplanar points to non-coplanar ones for global registration, and theoretically demonstrate the computational complexity is significantly reduced. Several typical human-centered applications such as tooth aligner and hearing aid are investigated and compared with S4PCS. The experimental results show that the proposed V4PCS can achieve a maximum of 20 times speedup and can successfully compute the valid transformation with very limited number of sample points.