Skip to content

cffk/orientation

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Nearly Optimal Coverings of Orientation Space

Charles F. F. Karney (charles@karney.com)
Version 1.0, March 6, 2006
Version 1.1 (with minor revisions), October 12, 2015

Introduction

Here we give various sets of orientations which cover orientation space nearly optimally. These are suitable for searching orientation space and for integrating over orientation (together with the provided weights). The background to this work is given in Section 8 of

Charles F. F. Karney,
Quaternions in molecular modeling,
J. Mol. Graph. Mod. 25(5), 595–604 (Jan. 2007),
Preprint: arXiv:physics/0506177.

Given a set of N orientations, we define its covering radius, α, as the maximum amount by which an arbitrary orientation needs to be rotated to align it with the closest member of the set. The coverage, c, is defined as

c = N(α − sin α)/π

A set of orientations is optimal if

  • there are no other sets with the same number of elements with a smaller α (and c).
  • all sets with a smaller number of elements have a larger α.

For any set of N orientations, we can perform a Voronoi tessellation of orientation space, associating with each member of the set, qi, all orientations for which qi is the closest orientation. We define the relative weight of qi as

wi = N (volume of Voronoi cell i ) / (volume of orientation space)
We can approximate an orientational average of f (q) with
f ⟩ = ∑i wi f (qi) / N
Assuming that the variation in f is bounded, we expect that, for a given N, the error in this approximation to be minimized with an optimal set of orientations.

Expressing the orientation as a unit quaternion or a pair of opposite points on S3, we see that this problem is just a 4-dimensional generalization of the “spherical covering” problem. See

R. H. Hardin, N. J. A. Sloane, and W. D. Smith,
Spherical coverings, (Feb. 1984),
with the additional constraint that the points come as opposite pairs. The formula for c above involves the “area” of a spherical cap on S3 of radius α/2. A quaternion [q0, q1, q2, q3] represents the rotation give by the matrix whose components are
1 − 2q22 − 2q32 2q1q2 − 2q0q3 2q1q3 + 2q0q2
2q2q1 + 2q0q3 1 − 2q32 − 2q12 2q2q3 − 2q0q1
2q3q1 − 2q0q2 2q3q2 + 2q0q1 1 − 2q12 − 2q22
where we have assumed that the quaternion is normalized, i.e., q02 + q12 + q22 + q32 = 1.

The problem of determining good orientation sets for the purposes of averaging is discussed in

M. Edén and M. H. Levitt,
Computation of orientational averages in solid state NMR by Gaussian spherical quadrature,
J. Magn. Reson. 132, 220–239 (1998).

Table of orientation sets

Because determining optimal sets of points is a hard problem, we provide here “nearly” optimal sets of points. We begin by providing a table of the orientation sets ranked by decreasing α.

name N α (°) c δ σ download
c48u1 24 62.80 1.57514 0.70000 0.00 quat grid euler
c600v 60 44.48 1.44480 quat euler
c48u9 216 38.45 3.38698 0.41422 0.00 quat grid euler
c48n9 216 36.47 2.89689 0.26091 7.00 quat grid euler
c600vc 360 27.78 2.15246 quat euler
c600vec 720 22.25 2.22117 quat euler
c48u27 648 20.83 1.64091 0.33582 0.00 quat grid euler
c48u83 1992 16.29 2.42065 0.25970 0.00 quat grid euler
c48u157 3768 14.49 3.22614 0.20710 0.00 quat grid euler
c48u181 4344 12.29 2.27013 0.19415 0.00 quat grid euler
c48u309 7416 10.07 2.13338 0.15846 0.00 quat grid euler
c48n309 7416 9.72 1.91567 0.15167 1.86 quat grid euler
c48u519 12456 9.05 2.60257 0.13807 0.00 quat grid
c48u527 12648 8.43 2.13318 0.13229 0.00 quat grid
c48n527 12648 8.17 1.94334 0.12599 1.86 quat grid
c48u815 19560 7.40 2.23719 0.11607 0.00 quat grid
c48u1153 27672 6.60 2.23735 0.10330 0.00 quat grid
c48u1201 28824 6.48 2.20918 0.09999 0.00 quat grid
c48u1641 39384 5.75 2.10646 0.08993 0.00 quat grid
c48u2219 53256 5.27 2.20117 0.08249 0.00 quat grid
c48u2867 68808 5.24 2.79649 0.07531 0.00 quat grid
c48u2947 70728 4.71 2.07843 0.07359 0.00 quat grid
c48u3733 89592 4.37 2.11197 0.06836 0.00 quat grid
c48u4701 112824 4.22 2.39041 0.06372 0.00 quat grid
c48u4749 113976 4.00 2.05300 0.06248 0.00 quat grid
c48u5879 141096 3.74 2.07325 0.05837 0.00 quat grid
c48u7111 170664 3.53 2.11481 0.05514 0.00 quat grid
c48u8649 207576 3.26 2.02898 0.05094 0.00 quat grid

The orientation sets can be downloaded by the links in the “download” column. The “quat” and “euler” files are in the following format:

  • Any number of initial comment lines beginning with “#”.
  • A line containing either “format quaternion” or “format euler”.
  • A line containing: N α(°) c.
  • N lines containing: q0i q1i q2i q3i wi (for quaternions)
  • or N lines containing: ai bi gi wi (for Euler angles).
The convention for Euler angles is that the rotation is given by Rz(a) Ry(b) Rz(g).

The “grid” links provide a compact representation for those orientation sets based on the 48-cell with δ and σ determining the grid spacing. This is described below. Only a subset of orientations sets in Euler angle format is provided here.

The following orientation sets are non-optimal:

  • c48u9 (beaten by c48n9),
  • c600vec (beaten by c48u27),
  • c48u309 (beaten by c48n309),
  • c48u527 (beaten by c48n527).

The following orientation sets are sub-optimal with a substantially thinner covering achieved by another set with somewhat more points:

  • c48u157 (use c48u181 instead),
  • c48u519 (use c48n527 instead),
  • c48u2867 (use c48u2947 instead),
  • c48u4701 (use c48u4749 instead).

Sets based on regular and semi-regular polytopes

One strategy for evenly spacing points on S3 is to place the points using the vertices or cell centers of regular and semi-regular polytopes. The vertices of all the regular 4-dimensional polytopes is given in

http://paulbourke.net/geometry/hyperspace/
c48u1 and c660v are two such sets. The points in c48u1 are placed at the centers of the cells of a truncated-cubic tetracontoctachoron (48-cell), see
https://en.wikipedia.org/wiki/Tetracontoctachoron.
These points are obtained by using the vertices of 2 24-cells in their mutually dual positions. Similarly the points in c600v are the vertices of a 600-cell. Both c48u1 and c600v probably are optimal sets.

The set c600v can be extended by adding the centers of the cells of the 600-cell (equivalent to the vertices of its dual, the 120-cell) to give the set c600vc and by adding, in addition, the midpoints of the edges of the 600-cell, to give the set c600vec.

Sets based on gridding the 48-cell

In order to obtain larger sets we seek a systematic way to place multiple points with the cells of a polytope. The 48-cell is convenient for this purpose. The cells are all identical truncated cubes and thus a body-center-cubic lattice lines up nicely with the cells. [A body-center-cubic lattice provides the thinnest covering of R3; see R. P. Bambah, On lattice coverings by spheres, Proc. Nat. Inst. Sci. India 20, 25–52 (1954).]

Here is the procedure. Each cell of the 48-cell is a truncated cube. Define the primary cell as

p0 = 1,
pi>0 < √2 − 1,
|p1| + |p2| + |p3| < 1.
The other cells are generated from this by the application of the rotational symmetry group of the cube.

Place a body-centered-cubic lattice, with lattice spacing δ, within the primary cell (including only points lying within the cell). Thus we take

p0 = 1,
[p1, p2, p3] = [k, l, m] δ/2
where [k, l, m] are either all even or all odd integers (to give a BCC lattice). These points are then normalized with q = p/|p| to place them on S3.

As δ is varied the number of points within the cell (N/24) varies. For a given N, pick the δ with the smallest covering. (To obtain the sets given here, we systematically varied δ in steps of 0.00001.) Discard any N for which there is a smaller N with a smaller (or equal) α.

This procedure yields the sets c48uMMM where MMM = Nc = N/24 is the number of points per cell.

There are many ways in which we might imagine improving these sets. One possibility is to use a non-uniform lattice spacing using

p1 = sinh(σ k δ/2)/σ,
and similarly for p2 and p3. (The uniform lattice is recovered in the limit σ → 0.) The increasing lattice spacing afforded by the sinh function counteracts the bunching of points occurring when the lattice points are projected onto S3.) The two sets c48n309 and c48n527 are two examples with reasonably thin coverage. In the case of c48n9, σ is used merely to delay the entry of a new set of points into the primary cell.

One might also offset the lattice and remove or perturb the points near the surface of the cells. However because these strategies make the search for good sets considerably more complex, the simple procedure with the uniform lattice outlined above probably suffices for most purposes.

Because of the regular way that the grids are obtained, we can define a compact represtentation of the orientation set with a file in the “grid” format. This consists of

  • Any number of initial comment lines beginning with “#”.
  • A line containing “format grid”.
  • A line containing: δ σ N Nc Nd α(°) c.
  • Nd lines containing: ki li mi wi ri(°) Mi.
where Nd is the number of distinct entries, ri is the radius of the i th Voronoi cell [thus α = maxi(ri)], and Mi is the multiplicity of the entry. In the file, we restrict kilimi ≥ 0. For each such [ki, li, mi], we generate Mi distinct permutations by changing the order and the signs of the elements.

Code to produce the full orientation sets for the grid form is available in ExpandSet.cpp. After compiling this code, you can generate a quaternion orientation set with, e.g.,

./ExpandSet < c48u527.grid > c48u527.quat
Supply the “-e” option to obtain the corresponding file of Euler angles.

Additional denser orientation sets are provided below. Because these sets contain a large number of orientations (up to 25×106), they are provided only the grid format.

Further remarks

For each set, can obtain new sets by performing an arbitrary rotation of R4 via

qi′ = r qi s,
where r and s are fixed (possibly random) unit quaternions. The pre- and post-multiplication allows all rotations of R4 to be accessed.

One way of estimating the error in the numerical quadrature is to repeat the calculation several times with the same set of points but choosing different random r and s each time.

(Note that original sets possess symmetry that if qi is a member of the set then so is the inverse rotation qi*. The new sets qi′ do not have this property, in general.)

Estimated accuracy (ulp = units in last place):

  • δ: exact (search for “optimum” was with resolution 10−5)
  • σ: exact
  • α: 0.006° (0.6 ulp)
  • c: 0.6×10−5 (0.6 ulp)
  • w: average 1.5×10−6 (1 ulp), maximum 4×10−6 (4 ulp) (last digit adjusted to give ∑i wi = N)
  • r: 0.015° (1.5 ulp)
  • q0, q1, q2, q3: 0.51×10−9 (0.51 ulp)

ZCW3 Orientation Sets

Edén and Levitt studied the ZCW3 orientation sets. These are based on gridding the space of Euler angles. These yield less thin coverings of orientation space that the sets given above. Here is the data

name N α (°) c
ZCW3_50 50 69.66 4.426
ZCW3_100 100 56.05 4.735
ZCW3_144 144 42.44 3.021
ZCW3_200 200 48.07 6.050
ZCW3_300 300 40.25 5.384
ZCW3_538 538 32.53 5.142
ZCW3_1154 1154 26.81 6.203
ZCW3_3722 3722 18.33 6.436
ZCW3_6044 6044 18.10 10.051

Denser orientation sets

The procedure used to obtain the orientation sets based on the 48-cell can be continued to obtain denser orientation sets. Here are the results for uniform grids (σ = 0):

name N α (°) c δ approx δ download
141096 3.735 2.07261 0.058364 2/34.2973
170664 3.529 2.11458 0.055138 2/36.2973
207576 3.260 2.02803 0.050932 2s/16.2657
c48u10305 247320 3.102 2.08130 0.048456 2/41.2973 grid
c48u12083 289992 3.096 2.42678 0.046023 grid
c48u12251 294024 2.903 2.02950 0.045354 2s/18.2657 grid
c48u14251 342024 2.767 2.04269 0.043215 2/46.2973 grid
c48u16533 396792 2.655 2.09385 0.041421 2/48.2973 grid
c48u19181 460344 2.497 2.02149 0.039000 2s/21.2450 grid
c48u21863 524712 2.403 2.05419 0.037534 2/53.2973 grid
c48u25039 600936 2.282 2.01458 0.035641 2s/23.2450 grid
c48u28329 679896 2.197 2.03407 0.034313 2/58.2973 grid
c48u31793 763032 2.162 2.17361 0.033137 grid
c48u32081 769944 2.116 2.05852 0.032786 grid
c48u35851 860424 2.024 2.01113 0.031601 2/63.2973 grid
c48u40003 960072 1.962 2.04420 0.030633 2/65.2973 grid
c48u44709 1073016 1.877 2.00081 0.029307 2s/28.2657 grid
c48u49397 1185528 1.822 2.02304 0.028453 2/70.2973 grid
c48u54799 1315176 1.753 1.99776 0.027370 2s/30.2657 grid
c48u60279 1446696 1.701 2.00892 0.026563 2/75.2973 grid
c48u65985 1583640 1.657 2.03291 0.025876 2/77.2973 grid
c48u72521 1740504 1.596 1.99529 0.024918 2s/33.2450 grid
c48u79099 1898376 1.557 2.01914 0.024303 2/82.2973 grid
c48u86451 2074824 1.505 1.99648 0.023504 2s/35.2450 grid
c48u93701 2248824 1.467 2.00411 0.022911 2/87.2973 grid
c48u101477 2435448 1.447 2.07920 0.022389 grid
c48u101917 2446008 1.444 2.07768 0.022222 grid
c48u110143 2643432 1.388 1.99316 0.021669 2/92.2973 grid
c48u118647 2847528 1.358 2.01352 0.021210 2/94.2973 grid
c48u128249 3077976 1.318 1.98655 0.020574 2s/40.2657 grid
c48u137809 3307416 1.290 2.00301 0.020142 2/99.2973 grid
c48u148395 3561480 1.255 1.98744 0.019600 2s/42.2657 grid
c48u158763 3810312 1.228 1.99130 0.019176 2/104.2973 grid
c48u169757 4074168 1.205 2.01122 0.018815 2/106.2973 grid
c48u181909 4365816 1.173 1.98631 0.018310 2s/45.2450 grid
c48u193767 4650408 1.151 2.00013 0.017970 2/111.2973 grid
c48u207023 4968552 1.123 1.98553 0.017535 2s/47.2450 grid
c48u220121 5282904 1.102 1.99143 0.017197 2/116.2973 grid
c48u233569 5605656 1.083 2.00765 0.016906 2/118.2973 grid
c48u248571 5965704 1.056 1.98203 0.016488 2/121.2973 grid
c48u263339 6320136 1.039 1.99944 0.016221 2/123.2973 grid
c48u279565 6709560 1.015 1.98032 0.015850 2s/52.2657 grid
c48u295333 7087992 0.999 1.99038 0.015589 2/128.2973 grid
c48u312831 7507944 0.978 1.97997 0.015266 2s/54.2657 grid
c48u330023 7920552 0.961 1.98309 0.015004 2/133.2973 grid
c48u347617 8342808 0.947 1.99747 0.014782 2/135.2973 grid
c48u367113 8810712 0.927 1.97956 0.014472 2s/57.2450 grid
c48u386211 9269064 0.913 1.99027 0.014255 2/140.2973 grid
c48u407099 9770376 0.896 1.98011 0.013983 2s/59.2450 grid
c48u427333 10255992 0.882 1.98284 0.013765 2/145.2973 grid
c48u448437 10762488 0.870 1.99711 0.013578 2/147.2973 grid
c48u471503 11316072 0.852 1.97662 0.013307 2/150.2973 grid
c48u493799 11851176 0.841 1.98949 0.013132 2/152.2973 grid
c48u518377 12441048 0.826 1.97564 0.012891 2s/64.2657 grid
c48u542361 13016664 0.814 1.98354 0.012715 2/157.2973 grid
c48u566819 13603656 0.814 2.06674 0.012551 grid
c48u568499 13643976 0.807 2.02337 0.012499 grid
c48u593755 14250120 0.789 1.97681 0.012323 2/162.2973 grid
c48u619981 14879544 0.780 1.98967 0.012173 2/164.2973 grid
c48u648549 15565176 0.766 1.97599 0.011964 2s/69.2450 grid
c48u676103 16226472 0.757 1.98293 0.011813 2/169.2973 grid
c48u706351 16952424 0.747 1.98930 0.011627 2s/71.2450 grid
c48u735777 17658648 0.735 1.97798 0.011475 2/174.2973 grid
c48u765729 18377496 0.727 1.98881 0.011344 2/176.2973 grid
c48u798587 19166088 0.715 1.97265 0.011155 2/179.2973 grid
c48u830491 19931784 0.707 1.98390 0.011032 2/181.2973 grid
c48u865149 20763576 0.696 1.97317 0.010863 2s/76.2657 grid
c48u898517 21564408 0.688 1.97768 0.010735 2/186.2973 grid
c48u932999 22391976 0.683 2.01538 0.010620 grid
c48u970447 23290728 0.670 1.97320 0.010455 2/191.2973 grid
c48u1006449 24154776 0.663 1.98364 0.010347 2/193.2973 grid
c48u1045817 25099608 0.653 1.97289 0.010197 2s/81.2450 grid
c48u1083955 26014920 0.646 1.97878 0.010086 2/198.2973 grid
27960696 0.630 1.97374 0.009838 2/203.2973
28943544 0.624 1.98389 0.009742 2/205.2973

As before, ExpandSet.cpp can be used to expand the grids into sets of quaternions or Euler angles. The computation of the weights in these high density grid files is carried out by determining the volume of the Voronoi cells in axis-angle space. Some corrections are applied to account for the fact that orientation space is not flat and the resulting maximum error in the weights is approximately (δ/12)2.

The column labeled “approx δ” illustrates that the optimal grid spacing follow one of three patterns (here s = √2 − 1). This follows from the requirement that the separation of the lattice planes at one set of faces (triangles or octogons) be such that the maximum Voronoi radius of points near this face match that of the point at the center of the cell. At the same time, the separation of the lattice planes at the other set of faces must not result in larger Voronoi radii.

About

Nearly Optimal Coverings of Orientation Space

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages