Tes Perpotongan Antara Frustum dan AABB

Frustum didefinisikan dengan 6 bidang datar (Plane) dengan setiap plane didefinisikan dengan vektor normal dan satu titik yang berada di plane tersebut.

Untuk tes AABB dengan frustum (frustum tersebut sendiri dapat mempunyai orientasi), salah satu cara sederhana yang orang pikir pertama adalah dengan menyatakan AABB berada di luar frustum jika semua titik AABB berada di luar frustum. Akan tetapi, dapat dilihat dibawah, terdapat kasus-kasus tertentu dimana ini tidak benar (false negative).

Cara aman untuk menyelesaikan ini adalah dengan menyatakan AABB berada di luar frustum jika semua titik AABB berada di satu sisi plane yang salah. Akan tetapi, dpad dilihat pada gambar di bawah, terdapat false positive (algoritma ini menyatakan AABB berada didalam frustum, padahal sebenarnya tidak).

False positive ini bisa dibiarkan saja, umumnya untuk Frustum Culling, karena komputasi frustum-AABB intersection perlu dibuat semurah mungkin (pengecekan tambahan akan menambah biaya komputasi).

Terdapat cara yang lebih cepat daripada diatas. Worst case untuk algoritma diatas adalah  diperlukan pengecekan 8 titik untuk setiap bidang (48 pengecekan). Cara yang lebih cepat adalah dengan membandingkan hanya dua titik saja untuk setiap bidang (12 pengecekan). Dua titik tersebut dinamakan titik positif dan negatif. Titik positif adalah titik yang paling searah dengan vektor normal plane, sedangkan titik negatif adalah titik yang berlawanan dengan vektor normal plane.

Untuk mengetahui kedua titik tersebut, vektor normal frustum perlu berada di world space, sehingga dapat dengan mudah didapat :

Menggunakan titik positif, jika titik positif berada di sisi plane yang salah, maka AABB tersebut berada di luar frustum. Sedangkan jika titik positif berada di sisi plane yang benar, maka titik negatif perlu dicek. jika titik negatif berada di sisi plane yang salah, maka AABB memotong frustum. AABB berada di dalam frustum jika titik positif dan negatif berada di dalam semua sisi plane.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *