Perpustakaan apa yang cocok untuk octrees atau kd-tree? [Tutup]

8

Apakah ada perpustakaan berkinerja kuat untuk mengindeks objek?

Objek akan memiliki batas sendiri, daripada diwakili oleh poin; dan karena itu sebuah objek dapat berada di lebih dari satu kompartemen jika indeks membagi berbagai hal dalam partisi berukuran tetap.

Itu akan membutuhkan pemusnahan dan mengunjungi benda-benda yang terkena sinar serta pencarian lingkungan.

Saya dapat menemukan banyak artikel yang menunjukkan matematika untuk bagian-bagian komponen, sering sebagai aljabar daripada C sederhana, tetapi tidak ada yang menempatkan semuanya bersama-sama (terlepas dari mungkin Ogre, meskipun tampaknya PyOrge tidak mengekspos octree ). Tentunya pembuat game hobi tidak semua harus membuat indeks bela diri mereka sendiri?

(Saya duduk menulis sphere-sphere saya sendiri, sphere-ray, ray-aabb, cone-aabb, cone-fustrum, aabb-fustrum dan implementasi octree; tentu ada cara yang lebih baik yaitu seseorang telah melakukan ini dan membuat paket yang bagus?!?!)

(Python atau C / C ++ w / binding lebih disukai)

python octree frustum Akan
sumber

Jawaban:

10

Tentunya pembuat game hobi tidak semua harus membuat sendiri oktoberinya?

Kecuali mereka menggunakan sesuatu yang lebih besar (seperti Ogre, atau fisika lain / mesin rendering), banyak yang melakukannya. Sebuah octree adalah struktur yang cukup sederhana untuk diterapkan, dan ada banyak pertukaran:

  • Apakah octree itu mengganggu atau tidak? Jika mengganggu Anda mendapatkan kinerja cache yang lebih baik, tetapi struktur yang lebih besar.
  • Jika tidak mengganggu, apakah menyimpan pointer atau semacam pegangan yang aman?
  • Apakah disimpan rata atau dengan pointer anak?
  • Bagaimana jenis-amannya? Jika menggunakan templat, itu akan jauh lebih aman dengan overhead runtime minimal, tetapi jauh lebih sulit untuk diikat ke Python.
  • Setiap octree dengan query spasial harus menyertakan beberapa jenis vektor / titik / ray, dan segala sesuatu dengan frustum culling akan menyertakan frustum dan matrik rutin matematika. Apakah menulis kode ke antarmuka yang ke selusin kelas matriks / vektor yang telah Anda seret dari semua perpustakaan lain yang Anda gunakan sebenarnya kurang bekerja daripada hanya menulis basis octree yang Anda inginkan?
  • Apakah ini aman?

Yang sedang berkata, ada banyak implementasi octree online . Hanya saja, jangan menganggap mengambil salah satu dari mereka akan menghemat banyak pekerjaan, dan jangan menganggap ada Satu Cara Benar untuk membuat struktur data selain array.


sumber
Wawasan yang bagus! Saya bertanya-tanya bagaimana itu untuk pohon KD, apa yang saya lihat dari mereka adalah mereka cukup bagus untuk diimplementasikan (ada banyak detail rumit untuk diperhitungkan). Mungkin seseorang tahu lebih banyak tentang ini?
Nef
Apakah pohon kd sebenarnya lebih sulit untuk diterapkan? Saya pikir mereka lebih sulit untuk berpikir tentang, terutama tanpa menggambar, karena mereka membagi geometri dengan cara yang kurang intuitif. Tetapi algoritma dasar bangunan / kueri tidak benar-benar lagi atau kurang dieksplorasi daripada octree.
2
Oktree sebenarnya hanya kasus khusus KD-tree. Dengan pesawat pemisah posisi tetap. Menerapkan pohon-pohon KD Anda akan memerlukan beberapa cara untuk menemukan sumbu "terbaik" Anda membelah offset per node.
void
2

Agar adil, Python Octree yang ditautkan telah diposting pada tahun 2006, jadi Python-Ogre mungkin telah mengekspos kelas Octree sekarang.

Namun, melihat melalui sumber-sumber Ogre, saya bisa melihat dua implementasi Octree: satu masuk Plugins/OctreeSceneManager/OgreOctree.hdan satu masuk Plugins/OctreeZone/OgreOctreeZoneOctree.h.

Jika Anda mengarahkan saya ke salah satu yang perlu Anda buka, saya akan meletakkannya di daftar todo saya untuk bungkus Python saya yang ditulis tangan (tersedia di bitbucket, tertaut di profil saya.)

Bagaimanapun, semoga beruntung. : D

jsandell
sumber
itu tawaran yang sangat baik; Saya ahem sudah menulis sendiri.
Will
1

Saya menemukan beberapa kode untuk implementasi octree Python di sini , hanya dengan googling 'octree python'. ; D

Ini bukan ketergantungan perpustakaan (meskipun awalnya ditulis untuk PyOgre) dan dikomentari dengan baik.

Bebek Komunis
sumber
Satu hal yang saya temukan di murni-Python octrees adalah bahwa overhead tambahan untuk panggilan fungsi untuk pohon traversal dengan cepat mendominasi runtime Anda dan membuatnya lebih buruk daripada pencarian sederhana dalam daftar, untuk sejumlah objek yang Anda dapat memproses dalam-Python murni pula. Contoh khusus itu juga terlihat sangat tidak dioptimalkan.
Sementara itu sedikit kode yang bagus untuk dicerna jika Anda membuat octree Anda sendiri, di luar kotak itu octree tidak memiliki semua fitur - persimpangan ray dan fustrum misalnya - yang saya kutip dalam pertanyaan. Bahkan, ia bahkan tidak memiliki pencarian tetangga terdekat. Saya ingin tahu untuk apa mereka menggunakan octtree, jika mereka dapat memasukkan data tetapi tidak menanyakannya selain dari titik yang tepat? Dan itu menyimpan poin, bukan hal-hal dengan batas. Saya mencantumkan semua kekurangan ini karena ini merupakan indikasi dari semua python octrees yang saya temukan di web; mungkin orang lain dapat menemukan octree yang lebih lengkap di google? Saya tidak bisa :(
Will
1

Setelah gagal mencoba beberapa paket yang disebutkan di atas saya menemukan RTree , yang merupakan pembungkus libspatialindex .

Glennr
sumber