Apa logika persimpangan pohon kd?

12

Saya mencoba mencari cara menerapkan pohon KD.

Pada halaman 322 "Deteksi tabrakan real time" oleh Ericson

Bagian teks disertakan di bawah jika pratinjau buku Google tidak membiarkan Anda melihatnya saat Anda mengklik tautan

bagian teks

Bagian yang relevan:

Ide dasar di balik memotong sinar atau segmen garis terarah dengan pohon kd sangat mudah. Garis berpotongan dengan bidang pembelahan node, dan nilai t dari persimpangan dihitung. Jika t berada dalam interval garis, 0 <= t <= tmax, garis mengangkang bidang dan kedua anak pohon diturunkan secara rekursif. Jika tidak, hanya sisi yang berisi asal segmen yang dikunjungi secara rekursif.

Jadi inilah yang saya miliki: ( buka gambar di tab baru jika Anda tidak dapat melihat hurufnya)

gambar

Pohon logis

divs

Di sini sinar oranye akan melalui adegan 3d. X mewakili persimpangan dengan bidang. Dari KIRI, sinar itu mengenai:

  • Wajah depan dari kubus tempat kejadian,
  • (1) bidang yang membelah
  • Pesawat pembelah (2.2)
  • Sisi kanan kubus tempat kejadian

Tapi inilah yang akan terjadi, secara naif mengikuti deskripsi dasar Ericson di atas:

  • Tes terhadap bidang yang membelah (1). Ray memukul pesawat pembelah (1), sehingga anak kiri dan kanan pesawat pembelah (1) dimasukkan dalam tes berikutnya.
  • Tes terhadap bidang yang membelah (2.1). Ray benar-benar menabrak pesawat itu, (jauh ke kanan) sehingga kedua anak termasuk dalam tes tingkat berikutnya. (Ini kontra-intuitif - seharusnya tidak hanya simpul bawah yang disertakan dalam pengujian berikutnya)

Bisakah seseorang menggambarkan apa yang terjadi ketika sinar oranye melewati adegan dengan benar?

bobobobo
sumber

Jawaban:

14

Ini benar-benar sangat sederhana; tes terhadap bidang pembelahan (2.1) harus gagal, karena hal berikut:

Saat sinar membelah bidang (1), Anda "membelah sinar", atau; Anda mengatur t-range yang valid, dan lanjutkan ke bawah pohon dengan bagian-bagian yang dihasilkan.

Jadi, ketika memeriksa terhadap bidang (2.1), Anda harus memeriksa apakah hanya bagian dari sinar yang tertinggal dari bidang (1) berpotongan dengan bidang (2.1), yang mana tidak. Persimpangan "jauh ke kanan" yang Anda bicarakan memiliki nilai t> di tmana Anda membagi sinar dengan bidang (1).

Saya harap itu cukup jelas.

Ringkasan: Persimpangan ray / bidang selanjutnya harus dilakukan hanya dengan bagian ray yang tersisa setelah membelahnya dengan bidang yang dimaksud.

Torious
sumber
1
Grr !! (kependekan dari jawaban yang bagus)
bobobobo
Jawaban yang bagus, Torious! Selamat datang di GDSE.
MichaelHouse