Menemukan angka empat yang merepresentasikan rotasi dari satu vektor ke vektor lainnya

105

Saya memiliki dua vektor u dan v. Apakah ada cara untuk menemukan angka empat yang mewakili rotasi dari u ke v?

sdfqwerqaz1
sumber

Jawaban:

115
Quaternion q;
vector a = crossproduct(v1, v2);
q.xyz = a;
q.w = sqrt((v1.Length ^ 2) * (v2.Length ^ 2)) + dotproduct(v1, v2);

Jangan lupa untuk menormalkan q.

Richard benar tentang tidak adanya rotasi yang unik, tetapi di atas harus memberikan "busur terpendek," yang mungkin Anda butuhkan.

Polaris878
sumber
30
Sadarilah bahwa ini tidak menangani kasus vektor paralel (baik dalam arah yang sama atau menunjuk ke arah yang berlawanan). crossproducttidak akan valid dalam kasus ini, jadi pertama-tama Anda perlu memeriksa dot(v1, v2) > 0.999999dan dot(v1, v2) < -0.999999, masing-masing, dan mengembalikan quat identitas untuk vektor paralel, atau mengembalikan rotasi 180 derajat (tentang sumbu apa pun) untuk vektor yang berlawanan.
sinisterchipmunk
11
Implementasi yang baik dari ini dapat ditemukan di kode sumber ogre3d
João Portela
4
@sinisterchipmunk Sebenarnya, jika v1 = v2, crossproduct akan menjadi (0,0,0) dan w akan menjadi positif, yang menormalkan identitas. Menurut gamedev.net/topic/… seharusnya berfungsi dengan baik juga untuk v1 = -v2 dan di sekitar mereka.
jpa
3
Bagaimana orang bisa membuat teknik ini bekerja? Untuk satu, sqrt((v1.Length ^ 2) * (v2.Length ^ 2))sederhanakan menjadi v1.Length * v2.Length. Saya tidak bisa mendapatkan variasi apa pun dari ini untuk menghasilkan hasil yang masuk akal.
Joseph Thomson
2
Ya, ini berhasil. Lihat kode sumber . L61 menangani jika vektor menghadap ke arah yang berlawanan (mengembalikan PI, jika tidak maka akan mengembalikan identitas sesuai komentar @ jpa). L67 menangani vektor paralel: secara matematis tidak perlu, tetapi lebih cepat. L72 adalah jawaban Polaris878, dengan asumsi kedua vektor adalah panjang satuan (menghindari akar persegi). Lihat juga tes unit .
sinisterchipmunk
63

Solusi Vektor Setengah Arah

Saya datang dengan solusi yang saya percaya Imbrondir coba hadirkan (meskipun dengan kesalahan kecil, yang mungkin mengapa sinisterchipmunk kesulitan memverifikasinya).

Mengingat bahwa kita dapat membuat angka empat yang mewakili rotasi di sekitar sumbu seperti:

q.w == cos(angle / 2)
q.x == sin(angle / 2) * axis.x
q.y == sin(angle / 2) * axis.y
q.z == sin(angle / 2) * axis.z

Dan hasil perkalian titik dan silang dari dua vektor yang dinormalisasi adalah:

dot     == cos(theta)
cross.x == sin(theta) * perpendicular.x
cross.y == sin(theta) * perpendicular.y
cross.z == sin(theta) * perpendicular.z

Mengingat rotasi dari u ke v dapat dicapai dengan memutar theta (sudut antar vektor) di sekitar vektor tegak lurus, terlihat seolah-olah kita dapat secara langsung membuat angka empat yang mewakili rotasi tersebut dari hasil perkalian titik dan silang. ; Namun, sebagaimana berdiri, theta = sudut / 2 , yang berarti bahwa hal itu akan menghasilkan dua kali rotasi yang diinginkan.

Salah satu solusinya adalah dengan menghitung vektor setengah jalan antara u dan v , dan menggunakan perkalian titik dan silang dari u dan vektor setengah jalan untuk membuat angka empat yang mewakili rotasi dua kali sudut antara u dan vektor setengah jalan , yang membawa kita ke v !

Ada kasus khusus, di mana u == -v dan vektor setengah jalan yang unik menjadi tidak mungkin untuk dihitung. Hal ini diharapkan, mengingat banyaknya tak terhingga banyaknya rotasi "busur terpendek" yang dapat membawa kita dari u ke v , dan kita harus memutar 180 derajat di sekitar vektor ortogonal ke u (atau v ) sebagai solusi kasus khusus kita. Ini dilakukan dengan mengambil perkalian silang ternormalisasi dari u dengan vektor lain yang tidak sejajar dengan u .

Kode semu mengikuti (jelas, pada kenyataannya kasus khusus harus memperhitungkan ketidakakuratan floating point - mungkin dengan memeriksa produk titik terhadap beberapa ambang daripada nilai absolut).

Perhatikan juga bahwa tidak ada kasus khusus ketika u == v (angka empat identitas dihasilkan - periksa dan lihat sendiri).

// N.B. the arguments are _not_ axis and angle, but rather the
// raw scalar-vector components.
Quaternion(float w, Vector3 xyz);

Quaternion get_rotation_between(Vector3 u, Vector3 v)
{
  // It is important that the inputs are of equal length when
  // calculating the half-way vector.
  u = normalized(u);
  v = normalized(v);

  // Unfortunately, we have to check for when u == -v, as u + v
  // in this case will be (0, 0, 0), which cannot be normalized.
  if (u == -v)
  {
    // 180 degree rotation around any orthogonal vector
    return Quaternion(0, normalized(orthogonal(u)));
  }

  Vector3 half = normalized(u + v);
  return Quaternion(dot(u, half), cross(u, half));
}

The orthogonalmengembalikan fungsi vektor ortogonal terhadap vektor yang diberikan. Implementasi ini menggunakan perkalian silang dengan vektor basis paling ortogonal.

Vector3 orthogonal(Vector3 v)
{
    float x = abs(v.x);
    float y = abs(v.y);
    float z = abs(v.z);

    Vector3 other = x < y ? (x < z ? X_AXIS : Z_AXIS) : (y < z ? Y_AXIS : Z_AXIS);
    return cross(v, other);
}

Solusi Kuarter Setengah Jalan

Ini sebenarnya adalah solusi yang disajikan dalam jawaban yang diterima, dan tampaknya sedikit lebih cepat daripada solusi vektor setengah jalan (~ 20% lebih cepat menurut pengukuran saya, meskipun jangan percaya begitu saja). Saya menambahkannya di sini jika orang lain seperti saya tertarik dengan penjelasannya.

Pada dasarnya, alih-alih menghitung angka empat menggunakan vektor setengah jalan, Anda dapat menghitung angka empat yang menghasilkan dua kali rotasi yang diperlukan (seperti yang dijelaskan dalam solusi lain), dan mencari angka empat setengah jalan antara itu dan nol derajat.

Seperti yang saya jelaskan sebelumnya, angka empat untuk dua kali lipat rotasi yang diperlukan adalah:

q.w   == dot(u, v)
q.xyz == cross(u, v)

Dan angka empat untuk rotasi nol adalah:

q.w   == 1
q.xyz == (0, 0, 0)

Menghitung angka empat setengah jalan hanyalah masalah menjumlahkan angka empat dan menormalkan hasilnya, seperti halnya vektor. Akan tetapi, seperti halnya dengan vektor, kuaternion harus memiliki besaran yang sama, jika tidak, hasilnya akan miring ke arah kuaternion dengan besaran yang lebih besar.

Sebuah angka empat dibangun dari titik dan produk silang dari dua vektor akan memiliki magnitudo yang sama seperti produk tersebut: length(u) * length(v). Daripada membagi keempat komponen dengan faktor ini, kita dapat meningkatkan skala angka identitas. Dan jika Anda bertanya-tanya mengapa jawaban yang diterima tampaknya memperumit masalah dengan menggunakan sqrt(length(u) ^ 2 * length(v) ^ 2), itu karena panjang kuadrat sebuah vektor lebih cepat dihitung daripada panjangnya, jadi kita dapat menyimpan satu sqrtperhitungan. Hasilnya adalah:

q.w   = dot(u, v) + sqrt(length_2(u) * length_2(v))
q.xyz = cross(u, v)

Dan kemudian menormalkan hasilnya. Kode pseudo berikut:

Quaternion get_rotation_between(Vector3 u, Vector3 v)
{
  float k_cos_theta = dot(u, v);
  float k = sqrt(length_2(u) * length_2(v));

  if (k_cos_theta / k == -1)
  {
    // 180 degree rotation around any orthogonal vector
    return Quaternion(0, normalized(orthogonal(u)));
  }

  return normalized(Quaternion(k_cos_theta + k, cross(u, v)));
}
Joseph Thomson
sumber
12
+1: Bagus! Ini bekerja sebagai pesona. Harus menjadi jawaban yang diterima.
Rekin
1
Sintaksis Quaternion diaktifkan pada beberapa contoh (Kuarter (xyz, w) dan Kuarter (w, xyz)). Juga tampaknya bahwa dalam blok kode terakhir radian dan derajat dicampur untuk menyatakan sudut (180 vs. k_cos_theta + k).
Guillermo Blasco
1
Kuarter (float, Vector3) adalah konstruksi dari vektor skalar, sedangkan Kuarter (Vector3, float) adalah konstruksi dari sudut sumbu. Mungkin berpotensi membingungkan, tapi menurut saya itu benar. Koreksi saya jika Anda masih menganggapnya salah!
Joseph Thomson
Berhasil! Terima kasih! Namun, saya menemukan tautan lain yang serupa dan dijelaskan dengan baik untuk melakukan operasi di atas. Pikir saya harus berbagi sebagai catatan;)
pendosa
1
@JosephThomson Solusi angka empat setengah jalan tampaknya datang dari sini .
legends2k
6

Masalah seperti yang dinyatakan tidak terdefinisi dengan baik: tidak ada rotasi unik untuk pasangan vektor tertentu. Perhatikan kasusnya, misalnya, di mana u = <1, 0, 0> dan v = <0, 1, 0> . Satu rotasi dari u ke v akan menjadi rotasi pi / 2 di sekitar sumbu z. Rotasi lain dari u ke v akan menjadi rotasi pi di sekitar vektor <1, 1, 0> .

Richard Dunlap
sumber
1
Faktanya, bukankah ada kemungkinan jawaban yang tak terbatas? Karena setelah Anda menyelaraskan vektor "dari" dengan vektor "ke", Anda masih dapat dengan bebas memutar hasilnya di sekitar porosnya? Tahukah Anda informasi tambahan apa yang biasanya dapat digunakan untuk membatasi pilihan ini dan membuat masalah didefinisikan dengan baik?
Doug McClean
5

Mengapa tidak merepresentasikan vektor menggunakan quaternions murni? Lebih baik jika Anda menormalkannya terlebih dahulu.
q 1 = (0 u x u y u z ) '
q 2 = (0 v x v y v z )'
q 1 q rot = q 2
Pra-kalikan dengan q 1 -1
q rot = q 1 -1 q 2
dimana q 1 -1 = q 1 konj / q norma
Ini dapat dianggap sebagai "divisi kiri". Pembagian kanan, yang tidak diinginkan adalah:
q rot, right = q 2 -1 q 1

orang gila
sumber
2
Saya tersesat, bukankah rotasi dari q1 ke q2 dihitung sebagai q_2 = q_rot q_1 q_rot ^ -1?
yota
4

Saya tidak terlalu bagus di Quaternion. Namun saya berjuang selama berjam-jam dalam hal ini, dan tidak dapat membuat solusi Polaris878 berfungsi. Saya sudah mencoba melakukan pra-normalisasi v1 dan v2. Normalisasi q. Normalisasi q.xyz. Namun tetap saja saya tidak mengerti. Hasilnya masih belum memberikan hasil yang benar.

Pada akhirnya saya menemukan solusi yang berhasil. Jika itu membantu orang lain, inilah kode kerja saya (python):

def diffVectors(v1, v2):
    """ Get rotation Quaternion between 2 vectors """
    v1.normalize(), v2.normalize()
    v = v1+v2
    v.normalize()
    angle = v.dot(v2)
    axis = v.cross(v2)
    return Quaternion( angle, *axis )

Kasus khusus harus dibuat jika v1 dan v2 adalah paralel seperti v1 == v2 atau v1 == -v2 (dengan beberapa toleransi), di mana saya yakin solusinya harus Quaternion (1, 0,0,0) (tanpa rotasi) atau Quaternion (0, * v1) (rotasi 180 derajat)

Imbrondir
sumber
Saya memiliki penerapan yang berfungsi, tetapi ini milik Anda lebih cantik, jadi saya benar-benar ingin ini berhasil. Sayangnya itu gagal dalam semua kasus pengujian saya. Tes saya semuanya terlihat seperti quat = diffVectors(v1, v2); assert quat * v1 == v2.
sinisterchipmunk
Ini tidak mungkin bahwa ini akan berhasil sama sekali karena anglemendapatkan nilainya dari perkalian titik.
sam hocevar
Di mana fungsi Quaternion ()?
June Wang
3

Beberapa jawaban tampaknya tidak mempertimbangkan kemungkinan bahwa perkalian silang bisa menjadi 0. Cuplikan di bawah ini menggunakan representasi sumbu-sudut:

//v1, v2 are assumed to be normalized
Vector3 axis = v1.cross(v2);
if (axis == Vector3::Zero())
    axis = up();
else
    axis = axis.normalized();

return toQuaternion(axis, ang);

Hal tersebut toQuaterniondapat diimplementasikan sebagai berikut:

static Quaternion toQuaternion(const Vector3& axis, float angle)
{
    auto s = std::sin(angle / 2);
    auto u = axis.normalized();
    return Quaternion(std::cos(angle / 2), u.x() * s, u.y() * s, u.z() * s);
}

Jika Anda menggunakan perpustakaan Eigen, Anda juga dapat melakukan:

Quaternion::FromTwoVectors(from, to)
Shital Shah
sumber
toQuaternion(axis, ang)-> Anda lupa menentukan apa ituang
Maksym Ganenko
Parameter ke-2 angleadalah bagian dari representasi sudut sumbu dari kuaternion, diukur dalam radian.
Shital Shah
Anda diminta mendapatkan angka empat untuk memutar dari satu vektor ke vektor lainnya. Anda tidak memiliki sudut, Anda harus menghitungnya terlebih dahulu. Jawaban Anda harus berisi perhitungan sudut. Bersulang!
Maksym Ganenko
Ini adalah c ++? apa itu ux ()?
Juni Wang
Ya, ini C ++. u adalah jenis vektor dari perpustakaan Eigen (jika Anda menggunakannya).
Shital Shah
2

Dari sudut pandang algoritma, solusi tercepat terlihat di pseudocode

 Quaternion shortest_arc(const vector3& v1, const vector3& v2 ) 
 {
     // input vectors NOT unit
     Quaternion q( cross(v1, v2), dot(v1, v2) );
     // reducing to half angle
     q.w += q.magnitude(); // 4 multiplication instead of 6 and more numerical stable

     // handling close to 180 degree case
     //... code skipped 

        return q.normalized(); // normalize if you need UNIT quaternion
 }

Pastikan Anda membutuhkan satuan satuan (biasanya, diperlukan untuk interpolasi).

CATATAN: Quaternions nonunit dapat digunakan dengan beberapa operasi lebih cepat dari unit.

minorlogic
sumber