Cara Membuat Custom 2D Physics Engine: Dasar dan Resolusi Impuls

Ada banyak alasan Anda mungkin ingin membuat physics engine khusus: pertama, mempelajari dan mengasah keterampilan Anda dalam matematika, fisika, dan pemrograman merupakan alasan bagus untuk mencoba proyek semacam itu; kedua, physics engine khusus dapat mengatasi segala macam efek teknis yang dimiliki pembuat konten. Dalam artikel ini saya ingin memberikan pengantar yang solid tentang cara membuat physics engine kustom sepenuhnya dari awal.

Physics menyediakan cara yang bagus untuk memungkinkan pemain untuk membenamkan diri dalam permainan. Masuk akal bahwa penguasaan physics engine akan menjadi aset yang berguna bagi setiap programmer untuk dimiliki pada penyelesaian mereka. Optimasi dan spesialisasi dapat dilakukan setiap saat karena pemahaman mendalam tentang cara kerja physics engine.

Pada akhir tutorial ini topik-topik berikut akan dibahas, dalam dua dimensi:

• Deteksi tabrakan sederhana
• Generasi manifold sederhana
• Impuls resolusi

Berikut demo cepatnya:

Custom Physics Engine Demo

Catatan: Meskipun tutorial ini ditulis menggunakan C++, Anda harus mampu menggunakan teknik dan konsep yang sama di hampir semua lingkungan pengembangan game.

Prasyarat

Artikel ini melibatkan cukup banyak matematika dan geometri, dan pada tingkat yang jauh lebih rendah dari coding. Beberapa prasyarat untuk artikel ini adalah:

• Pemahaman dasar matematika vektor sederhana
• Kemampuan untuk melakukan matematika aljabar

Deteksi Tabrakan

Ada beberapa artikel dan tutorial di internet, termasuk di sini di Tuts+, yang mencakup deteksi tabrakan. Mengetahui hal ini, saya ingin menjalankan topik dengan sangat cepat karena bagian ini bukan fokus dari artikel ini.

Axis Aligned Bounding Box

Axis Aligned Bounding Box (AABB) adalah kotak yang memiliki empat sumbu yang disejajarkan dengan sistem koordinat tempat ia berada. Hal ini berarti bahwa kotak itu tidak dapat diputar, dan selalu dikuadratkan pada 90 derajat (biasanya sejajar dengan layar). Secara umum disebut sebagai "bounding box" karena AABB digunakan untuk mengikat bentuk yang lebih kompleks lainnya.

AABB bentuk kompleks dapat digunakan sebagai tes sederhana untuk melihat apakah bentuk yang lebih kompleks di dalam AABBs dapat berpotongan. Namun dalam kasus sebagian besar game, AABB digunakan sebagai bentuk dasar, dan sebenarnya tidak mengikat yang lain. Struktur AABB Anda penting. Ada beberapa cara berbeda untuk mewakili AABB, namun inilah favorit saya:

1

struct AABB

2

{

3

  Vec2 min;

4

  Vec2 max;

5

};

Formasi ini memungkinkan AABB diwakili oleh dua poin. Titik min mewakili batas bawah sumbu x dan y, dan maks mewakili batas yang lebih tinggi - dengan kata lain, mereka mewakili sudut kiri atas dan bawah kanan. Untuk mengetahui apakah dua bentuk AABB berpotongan Anda perlu memiliki pemahaman dasar tentang Separating Axis Theorem (SAT).

Berikut adalah tes cepat yang diambil dari Deteksi Tabrakan Real-Time oleh Christer Ericson, yang menggunakan SAT:

1

bool AABBvsAABB( AABB a, AABB b )

2

{

3

  // Exit with no intersection if found separated along an axis

4

  if(a.max.x < b.min.x or a.min.x > b.max.x) return false

5

  if(a.max.y < b.min.y or a.min.y > b.max.y) return false

6

7

  // No separating axis found, therefor there is at least one overlapping axis

8

  return true

9

}

Circles

Lingkaran diwakili oleh radius dan titik. Seperti inilah struktur lingkaran Anda terlihat:

1

struct Circle

2

{

3

  float radius

4

  Vec position

5

};

Menguji apakah dua lingkaran berpotongan sangat sederhana: ambil jari-jari dari dua lingkaran dan tambahkan mereka bersama-sama, lalu periksa untuk melihat apakah jumlah ini lebih besar daripada jarak antara dua lingkaran.

Pengoptimalan penting untuk dilakukan adalah menyingkirkan semua kebutuhan untuk menggunakan operator akar kuadrat:

1

float Distance( Vec2 a, Vec2 b )

2

{

3

  return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 )

4

}

5

6

bool CirclevsCircleUnoptimized( Circle a, Circle b )

7

{

8

  float r = a.radius + b.radius

9

  return r < Distance( a.position, b.position )

10

}

11

12

bool CirclevsCircleOptimized( Circle a, Circle b )

13

{

14

  float r = a.radius + b.radius

15

  r *= r

16

  return r < (a.x + b.x)^2 + (a.y + b.y)^2

17

}

Secara umum, perkalian adalah operasi yang jauh lebih murah daripada mengambil akar kuadrat dari suatu nilai.

Impulse Resolution

Impulse resolution adalah tipe tertentu dari strategi resolusi tabrakan. Resolusi tabrakan adalah tindakan mengambil dua objek yang ditemukan berpotongan dan memodifikasi mereka sedemikian rupa sehingga tidak memungkinkan mereka untuk tetap berpotongan.

Secara umum sebuah objek dalam physics engine memiliki tiga derajat kebebasan utama (dalam dua dimensi): gerakan dalam bidang xy dan rotasi. Dalam artikel ini kita secara implisit membatasi rotasi dan hanya menggunakan AABBs dan Circles, sehingga satu-satunya tingkat kebebasan yang benar-benar perlu kita pertimbangkan adalah pergerakan sepanjang xy plane.

Dengan menyelesaikan tabrakan yang terdeteksi kita menempatkan pembatasan pada gerakan sehingga objek tidak dapat tetap berpotongan satu sama lain. Gagasan di balik resolusi impuls adalah menggunakan impuls (perubahan kecepatan seketika) untuk memisahkan objek yang ditemukan bertabrakan. Untuk melakukan hal ini, massa, posisi, dan kecepatan setiap objek entah bagaimana harus diperhitungkan: kita ingin benda besar bertabrakan dengan yang lebih kecil untuk bergerak sedikit selama tabrakan, dan untuk mengirim benda-benda kecil terbang menjauh. Kita juga ingin objek dengan massa tak terbatas untuk tidak bergerak sama sekali.

Untuk mencapai efek tersebut dan mengikuti intuisi alami tentang bagaimana benda-benda bergerak kita akan menggunakan tubuh yang kaku dan sedikit matematika yang wajar. Tubuh kaku adalah bentuk yang ditentukan oleh pengguna (yaitu, oleh Anda, pengembang) yang secara implisit didefinisikan menjadi tidak dapat diubah bentuknya. Baik AABB dan Circles dalam artikel ini tidak bisa diubah bentuknya, dan akan selalu menjadi AABB atau Circles. Tidak ada pengapitan atau peregangan yang diizinkan.

Bekerja dengan badan kaku memungkinkan banyak matematika dan derivasi menjadi sangat disederhanakan. Inilah sebabnya mengapa tubuh kaku biasanya digunakan dalam simulasi game, dan mengapa kita akan menggunakannya dalam artikel ini.

Objek Kita Bertabrakan - Sekarang Apa?

Dengan asumsi kita memiliki dua bentuk yang ditemukan berpotongan, bagaimana cara memisahkan keduanya? Mari kita asumsikan deteksi tabrakan memberi kita dua informasi penting:

• Tabrakan normal
• Penyusupan mendalam

Untuk menerapkan dorongan ke kedua objek dan memisahkannya, kita perlu tahu arah mana untuk mendorongnya dan seberapa banyak. Tabrakan normal adalah arah di mana impuls akan diterapkan. Kedalaman penyusupan (bersama dengan beberapa hal lain) menentukan seberapa besar dorongan akan digunakan. Ini berarti satu-satunya nilai yang perlu dipecahkan adalah besarnya dorongan kita.

Sekarang mari kita melakukan perjalanan panjang untuk menemukan bagaimana kita bisa memecahkan dorongan besar ini. Kita akan mulai dengan dua objek yang telah ditemukan berpotongan:

\[ V^{AB} = V^B - V^A \] Perhatikan bahwa untuk membuat vektor dari posisi A ke posisi B, Anda harus melakukan: endpoint - startpoint. \(V ^{AB}\) adalah kecepatan relatif dari A ke B. Persamaan ini harus dinyatakan dalam hal tabrakan normal \(n\) - yaitu, kita ingin mengetahui kecepatan relatif dari A ke B sepanjang arah tabrakan normal:

\[ V^{AB} \cdot n = (V^B - V^A) \cdot n \]

Kita sekarang memanfaatkan dot product. Dot product itu sederhana; merupakan jumlah dari produk-produk component-wise:

\[ V_1 = \begin{bmatrix}x_1 \\y_1\end{bmatrix}, V_2 = \begin{bmatrix}x_2 \\y_2\end{bmatrix} \\ V_1 \cdot V_2 = x_1 * x_2 + y_2 * y_2 \]

Langkah selanjutnya adalah memperkenalkan apa yang disebut coefficient of restitution. Restitusi adalah istilah yang berarti elastisitas, atau pantulan. Setiap objek di mesin fisika Anda akan memiliki ganti rugi yang direpresentasikan sebagai nilai desimal. Namun hanya satu nilai desimal yang akan digunakan selama perhitungan impuls.

Untuk memutuskan restitusi apa yang digunakan (dilambangkan dengan \(e\) untuk epsilon), Anda harus selalu menggunakan restitusi terendah yang terlibat dalam tabrakan untuk hasil yang intuitif:

1

// Given two objects A and B

2

e = min( A.restitution, B.restitution )

Setelah \(9e\) diperoleh, kita dapat menempatkannya ke dalam pemecahan persamaan untuk besaran impuls.

Hukum Restitusi Newton menyatakan hal-hal berikut:

\[V' = e * V \]

Semua ini mengatakan bahwa kecepatan setelah tabrakan sama dengan kecepatan sebelumnya, dikalikan dengan beberapa konstanta. Konstanta ini mewakili "faktor pentalan". Mengetahui hal ini, menjadi cukup mudah untuk mengintegrasikan restitusi ke dalam derivasi kita saat ini:

\[ V^{AB} \cdot n = -e * (V^B - V^A) \cdot n \]

Perhatikan bagaimana kita memperkenalkan tanda negatif di sini. Dalam Hukum Restitusi Newton, \(V'\), vektor yang dihasilkan setelah bouncing, sebenarnya berjalan berlawanan arah V. Jadi bagaimana kita mewakili arah yang berlawanan dalam derivasi kita? Memperkenalkan tanda negatif.

Sejauh ini baik-baik saja. Sekarang kita perlu untuk dapat mengekspresikan kecepatan ini sementara di bawah pengaruh dorongan. Berikut adalah persamaan sederhana untuk memodifikasi vektor dengan beberapa dorongan skalar \(j\) sepanjang \(n\) arah tertentu:

\ [V' = V + j * n \]

Mudah-mudahan persamaan di atas akal, karena sangat penting untuk memahami. Kita memiliki vektor satuan \(n\) yang mewakili arah. Kita memiliki skalar \(j\) yang mewakili berapa lama \(n\). Kita kemudian menambahkan vektor skala (n) ke \(V\) untuk menghasilkan \(V'\). Ini hanya menambahkan satu vektor ke vektor lainnya, dan kita dapat menggunakan persamaan kecil ini untuk menerapkan impuls satu vektor ke vektor lainnya.

Ada sedikit pekerjaan yang harus dilakukan di sini. Secara formal, suatu impuls didefinisikan sebagai perubahan momentum. Momentum adalah mass * velocity. Mengetahui hal ini, kita dapat mewakili suatu dorongan karena secara resmi didefinisikan seperti ini:

\[ Impulse = mass * Velocity \\ Velocity = \frac{Impulse}{mass} \therefore V' = V + \frac{j * n}{mass}\]

Kemajuan yang bagus telah dibuat sejauh ini! Namun kita harus mampu mengekspresikan dorongan menggunakan \(j\) dalam dua benda yang berbeda. Selama tabrakan dengan objek A dan B, A akan didorong ke arah yang berlawanan dari B:

\[ V'^A = V^A + \frac{j * n}{mass^A} \\ V'^B = V^B - \frac{j * n}{mass^B} \]

Kedua persamaan ini akan mendorong A menjauh dari B sepanjang vektor unit arah \(n\) oleh skalar impuls (besarnya \(n\)) \(j\).

Semua yang dibutuhkan sekarang adalah menggabungkan Persamaan 8 dan 5. Persamaan yang dihasilkan akan terlihat seperti ini:

\[ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = -e * (V^B - V^A) \cdot n \\ \therefore \\ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \]

Jika Anda ingat, tujuan awalnya adalah mengisolasi magnitude kita. Ini karena kita tahu apa arah untuk menyelesaikan tabrakan (diasumsikan diberikan oleh deteksi tabrakan), dan hanya tersisa untuk menyelesaikan besarnya arah ini. Besaran yang tidak diketahui dalam kasus kita adalah \(j\); kita harus mengisolasi \(j\) dan memecahkannya.

\[ (V^B - V^A) \cdot n + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \\ \therefore \\ (1 + e)((V^B - V^A) \cdot n) + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = 0 \\ \therefore \\ j = \frac{-(1 + e)((V^B - V^A) \cdot n)}{\frac{1}{mass^A} + \frac{1}{mass^B}} \]

Wah! Itu sedikit matematika! Semuanya sudah berakhir untuk sekarang. Sangat penting untuk diperhatikan bahwa pada versi terakhir dari Persamaan 10 kita memiliki \(j\) di sebelah kiri (magnitudo kita) dan semua yang ada di sebelah kanan semuanya diketahui. Ini berarti kita dapat menulis beberapa baris kode untuk menyelesaikan skalar impuls \(j\). Dan anak laki-laki adalah kode yang jauh lebih mudah dibaca daripada notasi matematika!

1

void ResolveCollision( Object A, Object B )

2

{

3

  // Calculate relative velocity

4

  Vec2 rv = B.velocity - A.velocity

5

6

  // Calculate relative velocity in terms of the normal direction

7

  float velAlongNormal = DotProduct( rv, normal )

8

9

  // Do not resolve if velocities are separating

10

  if(velAlongNormal > 0)

11

    return;

12

13

  // Calculate restitution

14

  float e = min( A.restitution, B.restitution)

15

16

  // Calculate impulse scalar

17

  float j = -(1 + e) * velAlongNormal

18

  j /= 1 / A.mass + 1 / B.mass

19

20

  // Apply impulse

21

  Vec2 impulse = j * normal

22

  A.velocity -= 1 / A.mass * impulse

23

  B.velocity += 1 / B.mass * impulse

24

}

Ada beberapa hal penting yang perlu diperhatikan dalam contoh kode di atas. Hal pertama adalah pemeriksaan di Jalur 10, if(VelAlongNormal > 0). Pemeriksaan ini sangat penting; itu memastikan bahwa Anda hanya menyelesaikan tabrakan jika objek bergerak ke arah satu sama lain.

Jika objek bergerak menjauh satu sama lain, kita tidak ingin melakukan apa-apa. Ini akan mencegah benda-benda yang seharusnya tidak benar-benar dianggap bertabrakan dari saling menjauh satu sama lain. Ini penting untuk membuat simulasi yang mengikuti intuisi manusia tentang apa yang seharusnya terjadi selama interaksi objek.

Hal kedua yang perlu diperhatikan adalah bahwa massa terbalik dihitung beberapa kali tanpa alasan. Sebaiknya simpan saja massa terbalik Anda dalam setiap objek dan lakukan pra-komputasi satu kali:

1

A.inv_mass = 1 / A.mass

Hal terakhir yang perlu diperhatikan adalah kita secara cerdas mendistribusikan skalar impuls \(j\) di atas dua objek. Kita ingin benda-benda kecil untuk bangkit dari benda-benda besar dengan sebagian besar \(j\), dan benda-benda besar untuk memiliki kecepatan mereka diubah oleh porsi yang sangat kecil dari \(j\).

Untuk melakukan ini, Anda dapat melakukan:

1

float mass_sum = A.mass + B.mass

2

float ratio = A.mass / mass_sum

3

A.velocity -= ratio * impulse

4

5

ratio = B.mass / mass_sum

6

B.velocity += ratio * impulse

Penting untuk menyadari bahwa kode di atas setara dengan fungsi sampel ResolveCollision() dari sebelumnya. Seperti dinyatakan sebelumnya, massa invers cukup berguna dalam physics engine.

Sinking Objects

Jika kita terus menggunakan kode yang kita miliki sejauh ini, objek akan saling bertabrakan dan terpental. Ini bagus, meskipun apa yang terjadi jika salah satu objek memiliki massa yang tak terbatas? Kita membutuhkan cara yang baik untuk mewakili massa tak terbatas dalam simulasi.

Saya sarankan menggunakan nol sebagai massa tak terbatas - meskipun jika kita mencoba untuk menghitung massa invers suatu objek dengan nol kita akan memiliki pembagian dengan nol. Solusi untuk ini adalah melakukan hal berikut saat menghitung inversi massal:

1

if(A.mass == 0)

2

  A.inv_mass = 0

3

else

4

  A.inv_mass = 1 / A.mass

Nilai nol akan menghasilkan perhitungan yang tepat selama resolusi impuls. Ini masih oke. Masalah tenggelamnya objek muncul ketika sesuatu mulai tenggelam ke objek lain karena gravitasi. Mungkin sesuatu dengan restitusi rendah menyentuh dinding dengan massa tak terbatas dan mulai tenggelam.

Tenggelam ini disebabkan oleh kesalahan floating point. Selama setiap perhitungan floating point kesalahan floating point kecil diperkenalkan karena perangkat keras. (Untuk informasi lebih lanjut, Google [Floating point error IEEE754].) Seiring waktu, kesalahan ini terakumulasi dalam kesalahan posisi, menyebabkan objek tenggelam ke dalam satu sama lain.

Untuk memperbaiki kesalahan ini harus diperhitungkan. Untuk memperbaiki kesalahan posisi ini saya akan menunjukkan kepada Anda metode yang disebut proyeksi linier. Proyeksi linier mengurangi pentusupan dua objek dengan persentase kecil, dan ini dilakukan setelah impuls diterapkan. Koreksi posisi sangat sederhana: gerakkan setiap objek di sepanjang tabrakan normal \(n\) dengan persentase kedalaman penyusupan:

1

void PositionalCorrection( Object A, Object B )

2

{

3

  const float percent = 0.2 // usually 20% to 80%

4

  Vec2 correction = penetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n

5

  A.position -= A.inv_mass * correction

6

  B.position += B.inv_mass * correction

7

}

Perhatikan bahwa kita mengukur penetrationDepth dengan total massa sistem. Ini akan memberikan koreksi posisi sebanding dengan berapa banyak massa yang kita hadapi. Benda kecil mendorong jauh lebih cepat daripada benda yang lebih berat.

Ada sedikit masalah dengan implementasi ini: jika kita selalu menyelesaikan kesalahan posisional kita maka objek akan naik-turun sementara mereka beristirahat pada satu sama lain. Untuk mencegah hal ini, beberapa slack harus diberikan. Kita hanya melakukan koreksi posisi jika penyusupan berada di atas beberapa ambang arbitrer, yang disebut sebagai "slop":

1

void PositionalCorrection( Object A, Object B )

2

{

3

  const float percent = 0.2 // usually 20% to 80%

4

  const float slop = 0.01 // usually 0.01 to 0.1

5

  Vec2 correction = max( penetration - k_slop, 0.0f ) / (A.inv_mass + B.inv_mass)) * percent * n

6

  A.position -= A.inv_mass * correction

7

  B.position += B.inv_mass * correction

8

}

Hal ini memungkinkan objek untuk menembus sedikit tanpa koreksi posisi menendang.

Generasi Manifold Sederhana

Topik terakhir yang dibahas dalam artikel ini adalah generasi manifold sederhana. Manifold dalam istilah matematika adalah sesuatu di sepanjang garis "kumpulan poin yang mewakili area dalam ruang". Namun, ketika saya merujuk ke manifold istilah saya mengacu pada objek kecil yang berisi informasi tentang tabrakan antara dua objek.

Berikut ini adalah pengaturan manifold yang khas:

1

struct Manifold

2

{

3

  Object *A;

4

  Object *B;

5

  float penetration;

6

  Vec2 normal;

7

};

Selama deteksi tabrakan, penyusupan dan tabrakan yang normal harus dihitung. Untuk menemukan info ini algoritma pendeteksi tabrakan asli dari bagian atas artikel ini harus diperluas.

Circle vs Circle

Mari kita mulai dengan algoritma tabrakan yang paling sederhana: Circle vs Circle. Tes ini kebanyakan sepele. Dapatkah Anda membayangkan apa arah untuk menyelesaikan tabrakan akan terjadi? Ini adalah vektor dari Lingkaran A ke Lingkaran B. Ini dapat diperoleh dengan mengurangi posisi B dari A.

Kedalaman penyusupan berhubungan dengan jari-jari lingkaran dan jarak satu sama lain. Tumpang tindih Lingkaran dapat dihitung dengan mengurangi jari-jari dijumlahkan oleh jarak dari masing-masing objek.

Berikut ini adalah contoh algoritma lengkap untuk menghasilkan manifold dari tabrakan Circle vs Circle:

1

bool CirclevsCircle( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A;

5

  Object *B = m->B;

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  float r = A->radius + B->radius

11

  r *= r

12

13

  if(n.LengthSquared( ) > r)

14

    return false

15

16

  // Circles have collided, now compute manifold

17

  float d = n.Length( ) // perform actual sqrt

18

19

  // If distance between circles is not zero

20

  if(d != 0)

21

  {

22

    // Distance is difference between radius and distance

23

    m->penetration = r - d

24

25

    // Utilize our d since we performed sqrt on it already within Length( )

26

    // Points from A to B, and is a unit vector

27

    c->normal = t / d

28

    return true

29

  }

30

31

  // Circles are on same position

32

  else

33

  {

34

    // Choose random (but consistent) values

35

    c->penetration = A->radius

36

    c->normal = Vec( 1, 0 )

37

    return true

38

  }

39

}

Hal yang paling penting di sini adalah: kita tidak melakukan akar kuadrat apa pun sampai perlu (objek ditemukan bertabrakan), dan kita memeriksa untuk memastikan lingkaran tidak pada posisi yang sama persis. Jika mereka pada posisi yang sama jarak kita akan nol, dan kita harus menghindari pembagian dengan nol ketika kita menghitung t/d.

AABB vs AABB

Tes AABB to AABB sedikit lebih kompleks daripada Circle vs Circle. Tabrakan yang normal tidak akan menjadi vektor dari A ke B, tetapi akan menjadi tampilan normal. AABB adalah kotak dengan empat tampilan. Setiap tampilan memiliki normal. Normal ini merupakan vektor satuan yang tegak lurus dengan tampilan.

Periksa persamaan umum garis dalam 2D:

\[ ax + by + c = 0 \\ normal = \begin{bmatrix}a \\b\end{bmatrix} \]

Dalam persamaan di atas, a dan b adalah vektor normal untuk suatu garis, dan vektor (a, b) diasumsikan dinormalkan (panjang vektor adalah nol). Sekali lagi, tabrakan kita normal (arah untuk menyelesaikan tabrakan) akan berada di arah salah satu norma tampilan.

Sekarang semua yang diperlukan adalah untuk mengetahui tampilan mana yang bertabrakan pada salah satu objek dengan objek lain, dan kita memiliki normal. Namun terkadang beberapa tampilan  dari dua AABB dapat berpotongan, seperti ketika dua sudut saling berpotongan. Ini berarti kita harus menemukan sumbu penyusupan terkecil.

Berikut ini adalah algoritma lengkap untuk AABB untuk generasi manifold AABB dan deteksi tabrakan:

1

bool AABBvsAABB( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A

5

  Object *B = m->B

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  AABB abox = A->aabb

11

  AABB bbox = B->aabb

12

13

  // Calculate half extents along x axis for each object

14

  float a_extent = (abox.max.x - abox.min.x) / 2

15

  float b_extent = (bbox.max.x - bbox.min.x) / 2

16

17

  // Calculate overlap on x axis

18

  float x_overlap = a_extent + b_extent - abs( n.x )

19

20

  // SAT test on x axis

21

  if(x_overlap > 0)

22

  {

23

    // Calculate half extents along x axis for each object

24

    float a_extent = (abox.max.y - abox.min.y) / 2

25

    float b_extent = (bbox.max.y - bbox.min.y) / 2

26

27

    // Calculate overlap on y axis

28

    float y_overlap = a_extent + b_extent - abs( n.y )

29

30

    // SAT test on y axis

31

    if(y_overlap > 0)

32

    {

33

      // Find out which axis is axis of least penetration

34

      if(x_overlap > y_overlap)

35

      {

36

        // Point towards B knowing that n points from A to B

37

        if(n.x < 0)

38

          m->normal = Vec2( -1, 0 )

39

        else

40

          m->normal = Vec2( 0, 0 )

41

        m->penetration = x_overlap

42

        return true

43

      }

44

      else

45

      {

46

        // Point toward B knowing that n points from A to B

47

        if(n.y < 0)

48

          m->normal = Vec2( 0, -1 )

49

        else

50

          m->normal = Vec2( 0, 1 )

51

        m->penetration = y_overlap

52

        return true

53

      }

54

    }

55

  }

56

}

Circle vs AABB

Tes terakhir yang akan saya bahas adalah tes Circle vs AABB. Idenya di sini adalah untuk menghitung titik terdekat pada AABB ke Circle; dari sana tes berubah menjadi sesuatu yang mirip dengan uji Circle vs Circle. Setelah titik terdekat dihitung dan tabrakan terdeteksi normal adalah arah titik terdekat ke pusat lingkaran. Kedalaman penyusupan adalah perbedaan antara jarak titik terdekat dengan lingkaran dan jari-jari lingkaran.

Ada satu kasus khusus yang rumit; jika pusat lingkaran berada dalam AABB maka pusat lingkaran harus dipotong ke tepi terdekat dari AABB, dan kebutuhan normal akan dibalik.

1

bool AABBvsCircle( Manifold *m )

2

{

3

  // Setup a couple pointers to each object

4

  Object *A = m->A

5

  Object *B = m->B

6

7

  // Vector from A to B

8

  Vec2 n = B->pos - A->pos

9

10

  // Closest point on A to center of B

11

  Vec2 closest = n

12

13

  // Calculate half extents along each axis

14

  float x_extent = (A->aabb.max.x - A->aabb.min.x) / 2

15

  float y_extent = (A->aabb.max.y - A->aabb.min.y) / 2

16

17

  // Clamp point to edges of the AABB

18

  closest.x = Clamp( -x_extent, x_extent, closest.x )

19

  closest.y = Clamp( -y_extent, y_extent, closest.y )

20

21

  bool inside = false

22

23

  // Circle is inside the AABB, so we need to clamp the circle's center

24

  // to the closest edge

25

  if(n == closest)

26

  {

27

    inside = true

28

29

    // Find closest axis

30

    if(abs( n.x ) > abs( n.y ))

31

    {

32

      // Clamp to closest extent

33

      if(closest.x > 0)

34

        closest.x = x_extent

35

      else

36

        closest.x = -x_extent

37

    }

38

39

    // y axis is shorter

40

    else

41

    {

42

      // Clamp to closest extent

43

      if(closest.y > 0)

44

        closest.y = y_extent

45

      else

46

        closest.y = -y_extent

47

    }

48

  }

49

50

  Vec2 normal = n - closest

51

  real d = normal.LengthSquared( )

52

  real r = B->radius

53

54

  // Early out of the radius is shorter than distance to closest point and

55

  // Circle not inside the AABB

56

  if(d > r * r && !inside)

57

    return false

58

59

  // Avoided sqrt until we needed

60

  d = sqrt( d )

61

62

  // Collision normal needs to be flipped to point outside if circle was

63

  // inside the AABB

64

  if(inside)

65

  {

66

    m->normal = -n

67

    m->penetration = r - d

68

  }

69

  else

70

  {

71

    m->normal = n

72

    m->penetration = r - d

73

  }

74

75

  return true

76

}

Kesimpulan

Semoga sekarang Anda telah belajar satu atau dua hal tentang simulasi physics . Tutorial ini cukup untuk memungkinkan Anda mengatur physics engine kustom sederhana yang seluruhnya terbuat dari awal. Di bagian selanjutnya, kita akan mencakup semua ekstensi yang diperlukan yang diperlukan oleh semua physics engines, termasuk:

• Hubungi pasangan menyortir dan memusnahkan
• Broadphase
• Layering
• Integrasi
• Timestepping
• Persimpangan Halfspace
• Desain Modular (bahan, massa dan kekuatan)

Saya harap Anda menikmati artikel ini dan saya berharap dapat menjawab pertanyaan di komentar.