SO3Grids: SPOT Sampling on SO(3)

Benchmark of deterministic SO(3) grids. Lower is better in both panels. FCC-KR and SPOT are the strongest methods in the current comparison across both Riesz energy with s = 3 and covering radius.

Deterministic rotation grids for SO(3). This repo implements several established constructions together with two methods introduced here: FCC-KR and SPOT.

Methods Included

Method	API	Idea
Cubochoric	grid_cubochoric()	Primitive cubic lattice in the cubochoric cube
Hopf / ISOI	grid_hopf()	HEALPix on S^2 crossed with a 6-point S^1 grid, recursively refined
HArDiSh	grid_hardish()	Halton-Arvo / Diaconis-Shahshahani low-discrepancy sequence
super-Fibonacci	grid_fibonacci_all()	Super-Fibonacci spiral on S^3, canonicalized to SO(3)
FCC-KR	grid_fcc_kr()	FCC lattice in cubochoric space transported into the octahedral fundamental zone
SPOT	grid_spot()	Symmetry Packing Orientation Transport over a truncated-cube source domain with KR transport to the octahedral fundamental zone

What Is Being Measured

The benchmark reports two complementary metrics.

1. Riesz Energy With s = 3

For a set of points on S^3 / {+/-1}, the Riesz energy is

E_s = sum_{i != j} 1 / d(i, j)^s

where d(i, j) is chordal distance. This repo reports the normalized ratio E3 / E3*, where E3* is the asymptotic leading-order optimum on S^3.

Why s = 3 matters here:

• s = 1 and s = 2 are often too forgiving to separate very good grids.
• s = 3 is more local and penalizes near-collisions more strongly.
• That makes it a better discriminator when many constructions are already globally reasonable.

2. Covering Radius

The covering radius is the worst-case geodesic distance from an arbitrary rotation to the nearest grid point. This repo reports

theta / theta* - 1

where theta* is the simplex lower bound. That lower bound is not known to be realizable in general, so this quantity should be read as a normalized gap-to-bound rather than an exact optimality ratio.

In practice:

• low Riesz energy suggests strong local uniformity,
• low covering radius suggests fewer worst-case gaps.

Main Tradeoff

The main drawback of SPOT is that it is lattice based, so it does not provide arbitrary point counts. The grid sizes come from the underlying lattice construction rather than from a free choice of N.

When you need a grid with essentially any requested number of points, use super-Fibonacci via grid_fibonacci_all().

Project Structure

Path	Purpose
src/so3grids/grids.py	Grid generators for all implemented methods
src/so3grids/metrics.py	Riesz energy and covering-radius evaluation
src/so3grids/orientation_ops.py	Quaternion and rotation conversions
src/so3grids/kr_otr.py	KR machinery used by the octahedral methods
benchmarks/run_benchmark.py	Reproducible benchmark script
benchmark_results.png	Current comparison figure

Installation

Basic Install

git clone https://github.com/zvarley/SO3Grids.git
cd SO3Grids
pip install -e .

Accelerated E3 Computation

pip install -e ".[gpu]"

This enables the optional torch + pykeops path used for larger Riesz energy calculations.

Requirements

• Python >= 3.9
• numpy
• scipy
• matplotlib
• optional: torch, pykeops

Quick Start

from so3grids import (
    grid_hardish,
    grid_fcc_kr,
    grid_spot,
    riesz_energy_E3,
    optimal_constants_S3,
    covering_radius,
    covering_radius_star_deg,
)

# Full SO(3) grid
q_hardish = grid_hardish(4096)

# Octahedral-fundamental-zone grids
q_fcc_kr = grid_fcc_kr(h=6)
q_spot = grid_spot(h=8)

# Evaluate the stronger octahedral method
n_eff = 2 * 24 * len(q_spot)
_, _, e3_opt = optimal_constants_S3(n_eff)
e3_ratio = riesz_energy_E3(q_spot, laue_id=11) / e3_opt

theta_rad = covering_radius(q_spot, laue_id=11)
theta_star_deg = covering_radius_star_deg(n_eff)
cr_excess = theta_rad * 180.0 / 3.141592653589793 / theta_star_deg - 1.0

print(f"E3 / E3*      = {e3_ratio:.4f}")
print(f"theta/theta*-1 = {cr_excess:.4f}")

Reproducing The Figure

cd benchmarks
python run_benchmark.py

This writes:

• benchmark_results.png
• benchmark_results.pdf

It also caches benchmark artifacts under benchmark_cache/:

• benchmark_cache/grids/<method>/<param>.csv stores grid points
• benchmark_cache/metrics/<method>.json stores all cached metric values for that method

Useful flags:

• --refresh-grid recomputes cached grids
• --refresh-metrics recomputes cached metrics from cached grids when possible
• --refresh-all recomputes everything

The current benchmark compares:

• Hopf / ISOI
• HArDiSh
• Cubochoric
• super-Fibonacci
• FCC-KR
• SPOT / grid_spot

Benchmark interpretation:

• Panel (a) reports E3 / E3*, where lower values indicate better local uniformity.
• Panel (b) reports theta / theta* - 1, where values closer to 0 indicate tighter coverage relative to the simplex lower bound.
• In the current results, FCC-KR and SPOT are the strongest methods overall across both metrics.

Technical Notes

• Quaternions use the (w, x, y, z) convention throughout.
• SO(3) is represented as S^3 with antipodal identification.
• For octahedral symmetry, benchmarked grids are evaluated in the octahedral fundamental zone and expanded by symmetry during metric computation.
• The Hopf / ISOI implementation is ported to reproduce the reference sequence ordering.

Citation

If you use SPOT or FCC-KR grids in your work, please cite:

• ...coming soon

References

• Rosca, D., Morawiec, A., and De Graef, M. (2014). A new method of constructing a grid in the space of 3D rotations and its applications to texture analysis. Modelling and Simulation in Materials Science and Engineering, 22(7), 075013. https://doi.org/10.1088/0965-0393/22/7/075013
• Larsen, P. M., and Schmidt, S. (2017). Improved orientation sampling for indexing diffraction patterns of polycrystalline materials. Journal of Applied Crystallography, 50(6), 1571-1582. https://doi.org/10.1107/S1600576717012882
• Alexa, M. (2022). Super-Fibonacci Spirals: Fast, Low-Discrepancy Sampling of SO(3). In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 8281-8290). https://doi.org/10.1109/CVPR52688.2022.00811
• Beltran, C., and Ferizovic, D. (2020). Approximation to uniform distribution in SO(3). Constructive Approximation, 52(2), 283-311. https://doi.org/10.1007/s00365-020-09506-1
• Yershova, A., Jain, S., LaValle, S. M., and Mitchell, J. C. (2010). Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration. The International Journal of Robotics Research, 29(7), 801-812. https://doi.org/10.1177/0278364909352700

License

This project is released under the MIT License. See LICENSE.