search

PistonDevelopers / quaternion

A simple and type agnostic Rust library for quaternion math designed for reexporting
Apache License 2.0
13 stars 6 forks source link

Apply more efficient rotation algorithm #36

Closed red-hara closed 5 years ago

red-hara commented 5 years ago

Proposed rotation algorithm provides increase in calculation speed up to 1.6 (5ns/iter vs 8ns/iter) on my machine with benching made on nightly Rust rustc 1.33.0-nightly (4c2be9c97 2019-01-22).

HeroicKatora commented 5 years ago

Just a friendly pointer for future pull requests, all the non-essential style changes make it hard to pick out which changes are of semantic nature. For reference, the speedup is here: https://github.com/PistonDevelopers/quaternion/pull/36/files#diff-b4aea3e418ccdb71239b96952d9cddb6L112

red-hara commented 5 years ago

Main logic change happens in fn rotate_vector. PS: My bad, I just rely on cargo fmt as on convention. My apologies for that.

HeroicKatora commented 5 years ago

Thanks! The operations at least seem to be typed correctly (in an i.j.k sense). Could you add a few comments explaining the math, especially where the two comes from?

red-hara commented 5 years ago

Some time ago I found good PDF for quaternion calculation and included that solution in my Java code base. Unfortunately, currently I can point only to this StackExchange answer.

HeroicKatora commented 5 years ago

I don't see the equivalence. In particular, I don't find any squared scalar component in your code.

red-hara commented 5 years ago

I'll do the P part, not NP. I will prove that both methods provide identical results, but right now I cannot provide proper method for explaining alt mode.

Let vector v be vx, vy, vz and quaternion q be qw, qx, qy and qz. In classic mode q*v*conj(q) we will get: xc = qw^2*vx + qx^2*vx - (qy^2 + qz^2)*vx + qw*(-2*qz*vy + 2*qy*vz) + 2*qx*(qy*vy + qz*vz) yc = 2*qx*qy*vx + 2*qw*qz*vx + qw^2*vy - qx^2*vy + qy^2*vy - qz^2*vy - 2*qw*qx*vz + 2*qy*qz*vz zc = -2*qw*qy*vx + 2*qx*qz*vx + 2*qw*qx*vy + 2*qy*qz*vy + qw^2*vz - qx^2*vz - qy^2*vz + qz^2*vz

In alt mode: xa = vx - 2*qy^2*vx - 2*qz^2*vx + 2*qx*qy*vy - 2*qw*qz*vy + 2*qw*qy*vz + 2*qx*qz*vz ya = 2*qx*qy*vx + 2*qw*qz*vx + vy - 2*qx^2*vy - 2*qz^2*vy - 2*qw*qx*vz + 2*qy*qz*vz za = -2*qw*qy*vx + 2*qx*qz*vx + 2*qw*qx*vy + 2*qy*qz*vy + vz - 2*qx^2*vz - 2*qy^2*vz

Now we need to compare two results. To do so I will subtract alt xa value from classic xc and so on. xc - xa = vx*(qw^2 + qx^2 + qt^2 + qz ^ 2 - 1) yc - ya = vy*(qw^2 + qx^2 + qt^2 + qz ^ 2 - 1) zc - za = vz*(qw^2 + qx^2 + qt^2 + qz ^ 2 - 1)

Note that rotatation is represented by unit quaternion. Then qw^2 + qx^2 + qy^2 + qz^2 - 1 = 0 is always true. That means that difference between vector rotated in classic mode and vector rotated in alt mode is zero (both methods give the same result).

bvssvni commented 5 years ago

Does this assume unit quaternions? Perhaps we should add another method instead.

red-hara commented 5 years ago

Rotations in 3d space in quaternion representation are always unit quaternions.

bvssvni commented 5 years ago

Looks good to me.

bvssvni commented 5 years ago

Merging.

bvssvni commented 5 years ago

Thanks!