Automated brick sculpture construction

[摘要] In this thesis we consider the modelling of a particular layout optimisation problem,namely, the LEGO construction problem. The LEGO construction problem, in short,concerns the optimal layout of a set of LEGO bricks to represent a given object.Our goal is to develop a software package which LEGO enthusiasts can use to constructLEGO sculptures for any real-world object.We therefore not only consider the layout optimisation problem, but also the generationof the input data required by the LEGO construction problem. We show that by using3D geometric models to represent the real-world object, our implemented voxelisationtechnique delivers accurate input data for the LEGO construction problem.The LEGO construction problem has previously been solved with optimisation techniquesbased on simulated annealing, evolutionary algorithms, and a beam search approach.These techniques all indicate that it is possible to generate LEGO buildinginstructions for real-world objects, albeit not necessarily in reasonable time.We show that the LEGO construction problem can be modelled easily with cellularautomata, provided that cells are considered as clusters which can merge or split duringeach time step of the evolution of the cellular automaton. We show that the use ofcellular automata gives comparable layout results in general, and improves the resultsin many respects. The cellular automata method requires substantially less memoryand generally uses fewer LEGO bricks to construct the LEGO sculpture when usingcomparable execution times.

[发布机构] Stellenbosch University