Enhancing and Analyzing Apollonian 3-d Sphere Packings for Arbitrary Objects

The goal of this thesis is to enhance the Apollonian 3-d sphere packing algorithm which is implemented in ProtoSphere.
3-d sphere packing is a technique to ﬁll many 3-d spheres into an object, to cover as much volume as possible without any sphere overlapping with another sphere or the bounds of the object.
Furthermore, several sphere packing analysis metrics are introduced. The metrics cover aspects like the distribution of the spheres and covered volume diﬀerences over the entire area, ﬁlling curves and the distribution of the spheres depending on its size to classify models. To optimize the packing quality, some adjustments were made to enhance the covered volume. In addition the adjustments, several packing conﬁgurations are tested which target aspects like computation time, most total covered volume, target number of spheres or any trade-oﬀ to compute the most optimal packing depending on the application.

Description

Models which meet the condition perform best with the ProtoSphere algorithms but the average covered volume for those models is about 85% while the upper bound for the covered volume depending on the model is somewhere in the range of 93% to 95%, 2.2.4. Therefore, the goal is to cover more than 92% of the volume on average.
Once the major issues for those models are solved with stable packing, the solutions can be adapted to other kind of models, which do not meet all the conditions. Aside from the covered volume, another goal of this thesis is to analyze sphere packing in several aspects.
The only measured criteria for the non-parallelized state of ProtoSphere was the covered volume percentage regardless of the distribution of the volume over the model. There are several other factors aside from a total covered volume percentage, like distribution of spheres, volume coverage and densities in the diﬀerent areas of the object.
Aside from other visual representations, there are also metrics like the packing speed, distribution of sphere sizes or the entropy which can be used to measure sphere packings for several aspects. Like the distribution of spheres (first image), the volume coverage (second image) and the packing quality (third image).

Results

The missing packed volume with ProtoSphere was reduced by more than 50% if the upper bound 95.01% is considered as the maximum packing density. This enhancement was achieved by adjusting the prototype distribution algorithm to consider any cell and adjusting the sphere size tolerance per step by a conﬁgurable limit.

There are new options to conﬁgure ProtoSphere to either pack models with a small amount of very good spheres, which is slow or pack a model quickly with any sphere which is inside the tolerance bounds.

To compare the similarity of two packings the similiarity of the sphere size distribution is calculated. The closer the result gets to 1.0 the more similar the two packings are.

On the other hand the divergence of the packings is calculated. The closer the result gets to 0.0 the less divergent the two packings are.

Files

Full version of the master's thesis (English only)

License

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.

If you would like to use the software commercially, please get in touch with us (zach at cs.uni-bremen dot de) to obtain the assets under a different license (a.k.a. multi-licensing).

If you use any of the assets or software from this web page to produce a publication, you must give credit and put a reference in your publication. For the reference, please use the following format:
Joscha Cepok, Enhancing and Analyzing Apollonian 3-d Sphere Packings for Arbitrary Objects. Master's Thesis, University of Bremen, 2020