Miniball method calculates incorrect bounding spheres

[janbridley]

Description

The minimal algorithm included with python's miniball package often calculates incorrect minimal bounding spheres for polyhedra with augmentations and/or large numbers of vertices. The current standard method of finding the minimal bounding sphere in three dimensions is Gärtner's miniball, which is an extension of Welzl’s algorithm and is written in c++. The package cyminiball (available with python -m pip install cyminiball) directly binds to the original c++ code, which is faster and more stable that the package miniball, which is a pure python implementation of the same algorithm with less stringent checks. This is the underlying issue behind the method as it currently stands, and will be fixed in an upcoming PR.

What about Fischer's exact solver?

There is a better method for calculating minimal bounding spheres, and it is available here. Although referred to as an "exact" solver, the method is not more accurate than Gärtner's implementation in all cases, although Fischer does include a number of internal checks as well as additional code to speed up runtimes. However, it is not currently available as a python package and would require a fair bit of complexity to incorporate into coxeter. For this reason, the fix PR for this will use Gärtner's miniball, and Fischer's algorithm can be revisited at a later date.

Further reading.

To reproduce

• Local pytest and CircleCI fail when running the test_get_set_minimal_bounding_sphere_radius method on some Johnson solids (see Added new shape families for Archimedean, Catalan, Johnson, and other solids. #177).
• Running pytest tests/test_polyhedron.py::test_get_set_minimal_bounding_sphere_radius on a branch that includes Johnson solids will easily reproduce these errors.
• Repeatedly running minimal_bounding_sphere on a highly aspherical mesh and comparing the results between runs will also reproduce this error

Error output

See #177 and #178.

System configuration

• macOS 13.1 on arm64
• Python 3.9.15
• coxeter 0.6.1

[bdice]

@janbridley Brilliant job with the descriptions written here. Thank you for the high quality documentation of the issue and context!

[joaander]

cyminibal is licensed under the GPL: https://github.com/hirsch-lab/cyminiball/blob/main/LICENSE. Using it in coxeter would require us to license coxeter (and all dependent packages) under the GPL as well, which is not acceptable.

The C++ source code cyminibal is based on is also GPL (https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html), so we cannot work around this with alternate bindings.

miniball (https://github.com/hbf/miniball) is available under the Apache 2.0 license which allows us to use it in coxeter.

[janbridley]

Looks like Fisher's code is licensed under Apache 2.0. I will come up with a plan to utilize that instead!

[janbridley]

Current progress on this issue:

1. I can compile the example c++ script on macOS arm64 and linux x86-64 with a few changes to Seb_debug.C script (and example.C)
2. I can pip install the package as-is using pip install . on linux (red hat 8.6 x86-64)

What I still am unable to do (and am working to address)

1. pip install the package on macOS arm64

What I have not tested yet:

1. pip install or c++ compile on Windows (x86-64)
2. pip install or c++ compile on macOS x86-64

[janbridley]

For pip installs on macOS, this is the error I get:

Processing /Users/$USER/Documents/GitHub/miniball/python
Preparing metadata (setup.py) ... done
Requirement already satisfied: numpy in /opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib/python3.10/site-packages (from miniball==1.0) (1.25.2)
Building wheels for collected packages: miniball
Building wheel for miniball (setup.py) ... error
error: subprocess-exited-with-error

× python setup.py bdist_wheel did not run successfully.
│ exit code: 1
╰─> [12 lines of output]
  running bdist_wheel
  running build
  running build_ext
  building 'miniball' extension
  creating build
  creating build/temp.macosx-11.0-arm64-cpython-310
  clang -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -fwrapv -O2 -Wall -fPIC -O2 -isystem /opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/include -arch arm64 -fPIC -O2 -isystem /opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/include -arch arm64 -I/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib/python3.10/site-packages/numpy/core/include -I/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/include/python3.10 -c miniball_python.cpp -o build/temp.macosx-11.0-arm64-cpython-310/miniball_python.o
  creating build/lib.macosx-11.0-arm64-cpython-310
  clang++ -bundle -undefined dynamic_lookup -Wl,-rpath,/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib -L/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib -Wl,-rpath,/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib -L/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/lib build/temp.macosx-11.0-arm64-cpython-310/miniball_python.o -o build/lib.macosx-11.0-arm64-cpython-310/miniball.cpython-310-darwin.so
  ld: library not found for -lSystem
  clang-14: error: linker command failed with exit code 1 (use -v to see invocation)
  error: command '/opt/homebrew/Caskroom/miniforge/base/envs/coxeterdev/bin/clang++' failed with exit code 1
  [end of output]

note: This error originates from a subprocess, and is likely not a problem with pip.
ERROR: Failed building wheel for miniball
Running setup.py clean for miniball
Failed to build miniball
ERROR: Could not build wheels for miniball, which is required to install pyproject.toml-based projects

[janbridley]

A further update:

hbf/miniball is pip installable and I made a few small tweaks to ensure it is buildable with gcc as well. Using the package with Coxeter does work, but still requires multiple (usually <10, always <100) iterations to converge to a the correct solution, regardless of the required precision. Shrinking methods (like Fischer's solver and the original python package we used) seem to experience numerical precision problems with sets of highly coplanar points like those that define a polyhedron. In some cases, points are ignored or passed over on the path to a solution, resulting in a SEB that does not contain one point. For a cloud of thousands of points clustered tightly together this is usually okay but for our case this is not. Many current algorithms are optimized for performance in high dimensions and are not tested with as many "degenerate" cases as we require in this package. That all being said, hbf/miniball does work as long as we allow for multiple tries to find the optimal solution. and is orders of magnitude faster than the original package.

This paper suggests that expanding algorithms (the dual approach to the miniball problem) are more effective in lower dimensions and may avoid the "missing points" problem I mentioned above. Of these, I think this algorithm (iterative orthant scan) seems optimal for the particular use case we have here. It is optimized for low dimensions and takes an approach that is less likely to miss points in a shape.

If I can find an open-source implementation of the iterative orthant scan I will try and use that, but in the mean time will get hbf/miniball working.