1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Have you considered using 3D voronoi diagram to break up your volume into smaller polyhedrons? $\endgroup$
    – Mithridates the Great
    Jan 22, 2020 at 2:51
  • $\begingroup$ @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? $\endgroup$
    – ScientificPythonNovice
    Jan 22, 2020 at 3:51
  • 3
    $\begingroup$ 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. $\endgroup$
    – Wolfgang Bangerth
    Jan 22, 2020 at 5:42
  • $\begingroup$ @WolfgangBangerth- thanks, just to be clear I understand correctly - by probability distribution for the points you mean their spatial coordinates? $\endgroup$
    – ScientificPythonNovice
    Jan 22, 2020 at 7:33

1 Answer 1

Reset to default
1
$\begingroup$

I believe the easiest approach here is using 3D Voronoi diagram algorithm. I suggest to use Voro++. Also you mentioned that you want to have control over distribution or statistics of the polyhedrons, so look at the tutorial for having custom distribution of polyhedrons with Voro++ here. For all other tutorials, which will help you to getting started please look at here. The code is written in C++ and you can use it in C++.

Last thing, which I found it very cool and at the time that I initially encountered the Voro++ and I wanted to use it for any 3D shape to fill it with 3D polyhedrons, is https://github.com/esean/stl_voro_fill, which is built on top of Voro++ and could fill any closed 3D surface with Voronois.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Voro++ looks really cool and I'm sure it will make generating volumes easier. The statistics, well, that will need to be played with I think. One concern is that I need the edge vectors of the cells, whereas Voro++ seems to only give the vertex coordinates and number/perimeter of edges(math.lbl.gov/voro++/doc/custom.html). Is there some way to uniquely determine the edges, i.e. how the vertices are connected? $\endgroup$
    – ScientificPythonNovice
    Jan 22, 2020 at 16:53
  • 1
    $\begingroup$ @ScientificPythonNovice Yes, you can extract edge connectivity matrix easily as it is described here in page 11: math.lbl.gov/voro++/doc/voro++_overview.pdf . Remember edges are just connectivity of vertices for each Voronoi. $\endgroup$
    – Mithridates the Great
    Jan 22, 2020 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.