A general advancing front technique for filling space with arbitrary objects

Published in Int. Journal for Numerical Methods in Engineering Vol. 61 (12), pp. 1977-1991, 2004
doi: 10.1002/nme.1068

Abstract

An advancing front space‐filling technique for arbitrary objects has been developed. The input required consists of the specification of the desired mean point distance in space and an initial triangulation of the surface. One object at a time is removed from the active front, and, if possible, surrounded by admissible new objects. This operation is repeated until no active objects are left. Two techniques to obtain maximum packing are discussed: closest object placement (during generation) and move/enlarge (after generation). Different deposition or layering patterns can be achieved by selecting the order in which objects are eliminated from the active front. Timings show that for simple objects like spheres the scheme is considerably faster than volume mesh generators based on the advancing front technique, making it possible to generate large $(>10^{6})$ yet optimal clouds of points in a matter of minutes on a PC. For more general objects, the performance may degrade depending on the complexity of the penetration checks. Several examples are included that demonstrate the capabilities of the technique.