Medial spheres for shape approximation.

Area of Science:

• Computer Graphics
• Computational Geometry
• Geometric Modeling

Background:

• Approximating complex 3D solids is crucial for various computational tasks.
• Existing methods for sphere-based approximation face limitations in speed and accuracy.

Purpose of the Study:

• To develop a novel, efficient, and accurate method for approximating 3D solids using a union of overlapping spheres.
• To outperform state-of-the-art methods in terms of speed, accuracy, and resource utilization (fewer spheres).

Main Methods:

• Generating internal spheres tangent to the solid's boundary.
• Utilizing these spheres for exact error analysis and efficient updates under deformation.
• Applying conservative dilation to the generated spheres.

Main Results:

• Achieved over an order of magnitude speedup compared to state-of-the-art methods.
• Obtained a tighter approximation in terms of volume difference using fewer spheres.
• Demonstrated superior time and error performance in approximate separation distance tests for (σ,θ)-fat solids.

Conclusions:

• The proposed sphere-based approximation method offers significant advantages in speed and accuracy.
• The internal, tangent spheres facilitate robust error analysis and efficient geometric processing.
• The method shows promise for applications like shape matching and segmentation.