Tes Perpotongan Antar AABB

Axis Aligned Bounding Box (kotak selaras sumbu?) didefinisikan sebagai volume yang dibatasi dengan dua titik, min dan max. Pada left-handed coordinate system, min adalah titik paling kiri-bawah-depan sedangkan max adalah titik paling kanan-atas-belakang.

Ingin diketahui apakah AABB a (min_a, max_a ) dan AABB b (min_b, max_b ) saling berpotongan,

Diketahui : 

  • Empat titik : min_a, max_a, min_b, max_b

Analisa :

Untuk b dapat bersinggungan dengan a, kita dapat membayangkan daerah dimana b tepat menyentuh ke empat sisi a.

Dari gambar diatas, dapat dilihat untuk kotak hitam (AABB a) dan kotak kuning (AABB b), untuk dapat menyentuh a, titik pusat b = \frac{min_b + max_b}{2} harus memenuhi persamaan :

    \begin{alignat*}{2} x_{min} - \frac{w'}{2} &\leq x' &\leq x_{max} + \frac{w'}{2}\\ y_{min} - \frac{h'}{2} &\leq y' &\leq y_{max} + \frac{h'}{2} \end{alignat*}

dengan x', y' adalah titik pusat b; w', h' adalah lebar dan tinggi b.

Persamaan diatas juga berlaku untuk dimensi tiga dan seterusnya. Dari persamaan X, kita dapat dua persamaan yang dapat kemudian kita sederhanakan.

    \begin{alignat*}{1} x_{min} - \frac{w'}{2} &\leq x'\\ 2x_{min} - x_{max}' + x_{min}' &\leq x_{max}' + x_{min}'\\ x_{min} &\leq x_{max}'\\ \end{alignat*}

dan

    \begin{alignat*}{1} x' &\leq x_{max} + \frac{w'}{2}\\ x_{max}' + x_{min}' & \leq 2x_{max} + x_{max}' - x_{min}'\\ 2x_{min}' & \leq 2x_{max}\\ x_{min}' & \leq x_{max}\\ x_{max} & \geq x_{min}' \end{alignat*}

Persamaan yang serupa juga berlaku untuk y :

    \begin{alignat*}{1} y_{min} & \leq y_{max}'\\ y_{max} &\geq y_{min}' \end{alignat*}

Leave a Reply

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