mosra / magnum

Lightweight and modular C++11 graphics middleware for games and data visualization
https://magnum.graphics/
Other
4.75k stars 439 forks source link

Math: add AABB and bounding sphere algorithms #557

Closed pezcode closed 2 years ago

pezcode commented 2 years ago

:wave: This PR adds a function for generating (approximate) bounding spheres to MeshTools. It lives in the new BoundingVolume.h header (+ matching .cpp).

The algorithm used is "Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem", specifically the "Ritter substitution algorithm" proposed in the paper. Time complexity between Ritter and this algorithm is identical (3 passes over all position values) but it produces spheres with smaller radius. One side effect of this algorithm is that the radius is always at least some minimal hard-coded value, currently set to TypeTraits<Float>::epsilon(). Since the use case for this function is primarily expected to be some sort of culling, this seems acceptable to me.

Because it was pretty straight-forward, I also added a function for generating axis-aligned bounding boxes. It's just a wrapper around minmax() but it doesn't hurt to have.

pezcode commented 2 years ago

Thanks for the thorough review, much appreciated 😊 There's one open question regarding numerical stability, I'll get back to you on that after some reading.

Note: I force-pushed all the minor fixes into the initial commit (since the commit message was wrong, it had the Math: prefix) and the new test cases/benchmarks into extra commits.

codecov[bot] commented 2 years ago

Codecov Report

Merging #557 (4694b59) into master (7f4500d) will decrease coverage by 17.16%. The diff coverage is 100.00%.

@@             Coverage Diff             @@
##           master     #557       +/-   ##
===========================================
- Coverage   83.84%   66.67%   -17.17%     
===========================================
  Files         523      483       -40     
  Lines       33893    30070     -3823     
===========================================
- Hits        28417    20050     -8367     
- Misses       5476    10020     +4544     
Impacted Files Coverage Δ
src/Magnum/MeshTools/BoundingVolume.cpp 100.00% <100.00%> (ø)
src/Magnum/GL/Renderer.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/Text/Renderer.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/Audio/Extensions.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/MeshTools/Compile.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/DebugTools/BufferData.cpp 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/DebugTools/ForceRenderer.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/DebugTools/ObjectRenderer.h 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/DebugTools/ForceRenderer.cpp 0.00% <0.00%> (-100.00%) :arrow_down:
src/Magnum/DebugTools/ResourceManager.h 0.00% <0.00%> (-100.00%) :arrow_down:
... and 349 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 7f4500d...4694b59. Read the comment docs.

mosra commented 2 years ago

Thank you! Merged as 7f4500d9e02f74a1d27f9ba99a8c3a3e01e5a808...90b53798c22dec45fcd3a232b68adf071884d2cb. While cross-linking those with the algorithms in Math::Intersection, I realized the AABB calculating function could be named boundingRange() instead to be consistent with the intersection algos, so I renamed it. Besides that, I left the public header at just forward declarations to not drag along unneeded dependencies when people would want to use just one of the APIs.