Metode mana yang lebih disukai untuk menyimpan objek geometris besar di quadtree?

15

Saat menempatkan objek geometris dalam quadtree (atau octree), Anda dapat menempatkan objek yang lebih besar dari satu simpul dalam beberapa cara:

  1. Menempatkan referensi objek di setiap daun yang dikandungnya
  2. Menempatkan referensi objek di node terdalam yang sepenuhnya terkandung
  3. Keduanya # 1 dan # 2

Sebagai contoh:

masukkan deskripsi gambar di sini

Pada gambar ini, Anda bisa menempatkan lingkaran di keempat simpul daun (metode # 1) atau hanya di simpul akar (metode # 2) atau keduanya (metode # 3).

Untuk keperluan kueri quadtree, metode mana yang lebih umum dan mengapa?

graphics data-structures computational-geometry nsantorello
sumber
1
Tentunya itu harus menjadi referensi. Saya bermaksud bertanya apakah, untuk keperluan kueri quadtree, harus ada referensi di daun, non-daun, atau keduanya.
nsantorello
PS Diedit agar mudah-mudahan niat pertanyaan lebih jelas.
nsantorello
Apa pertanyaan yang Anda coba dukung?
Joe
@ Jo. Saya khususnya tertarik pada deteksi tabrakan, pengindeksan spasial, dan region / frustum culling.
nsantorello
1
@nsantorello Aturannya mungkin berbeda tergantung pada kueri mana yang ingin Anda dukung, tetapi ini tampaknya sangat relevan untuk deteksi tabrakan: stackoverflow.com/questions/4434335/…
Joe

Jawaban:

8

Dengan asumsi Anda menyimpan referensi, bukan objek itu sendiri, mungkin masuk akal untuk melakukan ini secara berbeda tergantung pada aplikasi Anda.

Misalnya, jika Anda menghitung tumbukan dengan lingkaran (padat) ini dan tumbukan itu terjadi di sudut kiri bawah, akan lebih mudah jika Anda memiliki akses ke semua geometri di daun itu langsung dari daun itu (metode # 3) (tanpa harus melintasi pohon ke atas dan menentukan geometri yang diwarisi). Tetapi, katakan saja Anda hanya menggunakan quadtrees untuk menggambar geometri, Anda ingin menggunakan metode # 1, karena hanya masuk akal untuk menggambar sesuatu di node yang sudah terkandung sepenuhnya (akan lebih sulit untuk mengetahui bagian mana yang untuk menggambar untuk setiap simpul daun dan di mana).

Adapun apa yang lebih umum, satu-satunya pengalaman saya dengan quadtrees adalah dengan menulis simulasi n-body di mana objek geometris benar-benar hanya titik yang tidak memiliki area, jadi saya tidak bisa menjawabnya secara definitif.

Rafe Kettler
sumber
Terima kasih Rafe, saya pikir Anda benar karena itu tergantung pada aplikasi.
nsantorello
6

Salah satu kelebihan Quadtree adalah Anda tidak perlu membagi simpul menjadi simpul turunannya jika semua simpul turunannya berisi informasi yang sama. Ini dapat menghemat banyak memori dan membuat pemrosesan lebih cepat.

Mengikuti prinsip ini, saya pikir lebih masuk akal untuk menyimpannya hanya di root node (metode # 2). Ini bisa menghemat banyak memori dan saya pikir juga akan membuat pemrosesan lebih mudah. Misalnya, jika Anda mencoba menemukan persimpangan lingkaran dengan garis yang melewati tiga simpul daun, Anda harus menghitung persimpangan secara terpisah untuk setiap simpul daun, atau ingat bahwa Anda sudah berpotongan dengan lingkaran ini.

Di sisi lain, jika Anda memiliki objek di node daun, itu bisa membantu Anda menghilangkan false positive (objek yang harus Anda periksa persimpangan, karena mereka berada di simpul yang benar, tetapi itu tidak benar-benar berpotongan).

Jadi, saya pikir kedua pendekatan memiliki kegunaannya dan saya tidak yakin bagaimana memilih yang mana yang akan digunakan.

Saya mungkin tidak akan menggunakan pendekatan # 3, karena saya tidak melihat hal positif tentang itu.

svick
sumber