# Filling a volume with generalised polyhedra

Given a volume (say, some polyhedron), I need to fill it with smaller polyhedra, such that the space is filled as much as possible. The constraints and relaxations are:

(0) For a computation perspective, the number of small polyhedra is low, perhaps 8-10.

(1) The smaller polyhedra are not of the same size, and conform to some volume distribution.

(2) The smaller polyhedra may be of different shapes (tetrahedra, hexahedra, octahedra) and orientations (i.e. face up/corner up/edge up/anthing in between).

(3) Ideally the smaller polyhedra would share faces, so that there aren't empty spaces between them.

(4) The outline of the large polyhedron can be relaxed, i.e. it is not necessary for the small polyhedra to conform exactly to the outer boundary.

The background of the problem is that I'm trying to create a polycrystalline aggregate (the big polyhedron), which is composed of individual crystals (the small polyhedra). The edge vectors of the individual crystals are required for further computation.

Conceptually, I was thinking along one of two lines:

(1) First generate the small polyhedra according to the given distribution, then try to tile them into the given large polyhedron, minimising gaps/overlaps by iteratively modifying the edges. This then becomes a sort of packing problem.

(2) Carve up the large polyhedron into smaller volumes by drawing lines/adding vertices, and then modify the lines to accomodate the polyhedra. This becomes something like Delaunay triangulation, with polyhedra.

What is the best way to go about this problem? If solutions to this or similar problems already exist, I would be very glad to go through them.

• Have you considered using 3D voronoi diagram to break up your volume into smaller polyhedrons? Jan 22, 2020 at 2:51
• @AloneProgrammer- Thanks, this would be along the lines of approach (2) that I mentioned. However, this would not give me any control over the size/shape of the Voronoi cells, which would need to correspond to some distribution. Or are there variants of Voronoi diagrams which allow this? Jan 22, 2020 at 3:51
• I second the suggestion of Voronoi diagrams. You might want to play with the probability distributions for the points to get a certain size distribution. Jan 22, 2020 at 5:42
• @WolfgangBangerth- thanks, just to be clear I understand correctly - by probability distribution for the points you mean their spatial coordinates? Jan 22, 2020 at 7:33