Outside-in Priority-based Approximation of 3D Models in LEGO Bricks

Abstract

In this paper, we discuss the problem of converting a 3D mesh into an assembly of LEGO blocks. The major challenge of this task is how to aggregate the voxels derived by the shape discretization into a set of standard bricks guaranteeing global connectivity. We propose an outside-in priority-based heuristic method based on the analysis of the critical regions that are more likely to cause the creation of a legal assembly to fail. We show that our graph-building heuristic provides relevant advantages, making it easier to obtain a connected graph with good properties with respect to the layer-based or random aggregation strategies applied in most of the optimization approaches. We also propose BRICKS, a novel dataset for the evaluation of aggregation strategies. It includes voxelizations at 3 different resolutions of 33 shapes and allows the easy comparison of different voxel aggregation strategies independently of the shape discretization step and also considering their scalability. We use it to evaluate our approach with respect to graph-based connectivity measures, showing the advantages of the proposed strategy.