Axis Aligned Spatial Division: Membagi ruang menjadi persegi panjang acak?

11

Saya perlu metode untuk membagi ruang 3d menjadi bentuk kotak sejajar sumbu acak. Untuk saat ini saya sedang membagi ruang 2d untuk tujuan pengujian. Pendekatan paling cepat yang saya lakukan adalah mendefinisikan persegi panjang ukuran (1, 1) dan kemudian secara rekursif membagi semua persegi panjang yang ada menjadi dua persegi panjang yang tidak rata bergantian antara sumbu X dan Y.

masukkan deskripsi gambar di sini

Masalahnya di sini sudah jelas. Pendekatan ini menghasilkan garis peregangan yang panjang (ditandai dengan warna merah)

masukkan deskripsi gambar di sini

Yang saya inginkan adalah sesuatu yang terlihat lebih organik (saya sertakan contoh)

Lihat, tidak ada garis lurus panjang dari atas ke bawah atau kiri ke kanan.

masukkan deskripsi gambar di sini

Satu-satunya kendala adalah bahwa saya mungkin ingin membatasi ukuran minimal dari persegi panjang tanpa mempengaruhi granularity ukuran. yaitu jika kotak terkecil adalah 1 cm persegi dari detik ruangan terkecil tidak harus 2 unit persegi.

Jadi idealnya algoritma harus memenuhi ketiga kendala berikut:

  1. Persegi panjang tidak terlalu kecil.
  2. Ukuran rect bukan perkalian diskrit dari ukuran rect terkecil. yaitu jika kotak terkecil adalah 3 unit persegi daripada rekt yang lebih besar tidak dibatasi menjadi 6, 9, 12 dan seterusnya unit persegi dan sebaliknya bisa menjadi 3,2 atau 4,7 dalam hal ini).
  3. Algoritme berjalan dalam waktu polinomial (perlu menghitung cepat).
AturSams
sumber

Jawaban:

12

Pendekatan yang Anda buat sederhana dan bermanfaat, tetapi menderita artefak mengerikan seperti yang ditunjukkan. Hindari itu. Anda membutuhkan algoritma pertumbuhan paralel; untuk model single-threaded, pendekatan round-robin mengikuti:

  1. Tempatkan berbagai titik secara acak di ruang peta Anda. Normalisasi distribusinya (hindari pengelompokan jelek) menggunakan distribusi Gaussian atau dengan menerapkan algoritma relaksasi berulang untuk memindahkan titik-titik yang ditempatkan secara acak satu sama lain, sesuai relaksasi Lloyd untuk Diagram Voronoi . Poin-poin ini mewakili centroid dari calon kamar Anda.
  2. (Paralel / Ulangi round-robin untuk semua kamar) Dari setiap titik, tumbuhkan 4 simpul ke luar (ruang persegi panjang), bergerak dari titik pusat per iterasi global (Anda dapat menumbuhkan kamar yang berbeda dengan laju yang berbeda di setiap sumbu daripada yang sama untuk semua, dan lihat bagaimana hasilnya - mungkin untuk hasil yang lebih organik / bervariasi). Pada titik tertentu, beberapa persegi panjang Anda akan mulai menekan satu sama lain. Pada titik itu, batasi pertumbuhan sumbu itu, pastikan ujung-ujung yang berdekatan dari kedua ruangan benar-benar bersentuhan, dan lanjutkan.
  3. Ulangi langkah 2, tumbuhkan setiap kamar secara bertahap, sampai semua pertumbuhan dibatasi oleh ruang yang berdekatan atau batas peta.
  4. Ini masih akan meninggalkan beberapa ruang kosong. Masalahnya sekarang menjadi salah satu penempatan dan pembuatan kamar dari ruang yang tidak ditempati. Faktanya, jika ruang Anda yang mendasari adalah kisi (integer-indexed) (dan setiap iterasi pertumbuhan masuk ke kisi itu), maka ini jauh lebih mudah untuk ditangani, karena Anda dapat mempertahankan daftar sel kisi yang diduduki dan tidak dihuni: Sekali Anda Saya telah menempatkan dan menumbuhkan semua kamar Anda, mencari melalui daftar kosong untuk ruang diskrit yang terdiri dari kelompok sel yang berdekatan. Karena banyak ruang yang tidak digunakan akan memiliki bentuk non-persegi panjang, Anda harus memilih sel secara acak dari dalam ruang non-persegi panjang itu, dan menumbuhkannya ke ukuran maksimal seperti yang Anda lakukan dengan kamar di langkah 2. Ulangi dalam kata non -Ruang segi empat, sampai benar-benar terisi.
  5. Ulangi langkah 4 hingga peta Anda terisi 100%.
Insinyur
sumber
Ini saran yang bagus. Kerugiannya adalah mungkin tidak melakukan apa pun untuk melindungi saya dari rect yang sangat kecil. Saya perlu beberapa cara untuk membatasi seberapa kecil dan seberapa besar rect. Saat ini saya sedang dalam proses mengerjakan metode lain. Saya akan membandingkan hasilnya dan memperbarui.
AturSams
@ArthurWulfWhite Kemudian pertanyaan Anda tidak ditentukan dan harus diperbarui. Ukuran kamar minimum Anda ditentukan oleh resolusi sel-peta Anda; jadi jika Anda membuat yang berbutir kasar cukup untuk mengakomodasi ukuran kamar minimum, Anda dapat menyesuaikan sumbu berdasarkan floating-point, mengembalikan tampilan yang lebih organik.
Insinyur
Anda benar! Saya pikir saya menulis bagian itu. Tapi saya belum. Saya minta maaf atas kesalahan ini. Ya saya mengetahui ukuran kisi. Sebuah ruangan hanya bisa sekecil yang dimungkinkan oleh kotak.
AturSams
OK - harap Anda menemukan solusi yang cocok. BTW saya maksudkan "sesuaikan kisi-kisi garis", bukan "sesuaikan sumbu".
Insinyur
1
Sebenarnya saya melakukan sesuatu persis seperti itu secara longgar berdasarkan pada konsep yang Anda pikirkan. Saya akan memposting hasilnya di sini juga.
AturSams
2

Seperti yang Anda lihat, saya berhasil menyingkirkan dunia artefak ini. Idenya sangat mirip.

  1. Bagilah ruang 2d menjadi kotak yang tidak seragam. Jika dua garis terlalu dekat, hapus satu.
  2. Pilih persegi panjang secara acak, periksa apakah telah dimodifikasi di sumbu-y (tingginya) dan jika tetangga langsung dimodifikasi di sumbu-y. Saya sama-sama tidak dimodifikasi, minta mereka menegosiasikan ulang segmen di antara mereka (satu akan menyumbangkan beberapa ruang untuk yang lain).
  3. Lakukan hal yang sama seperti pada langkah 2 hanya kali ini pada sumbu lainnya.
  4. Ulangi proses ini sampai Anda memodifikasi sebanyak mungkin.

Kisi tidak seragam (1):

masukkan deskripsi gambar di sini

Bernegosiasi pada sumbu x (2):

masukkan deskripsi gambar di sini

Bernegosiasi pada sumbu y (3):

masukkan deskripsi gambar di sini

Hasil (4):

masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

AturSams
sumber
Ini secara longgar terinspirasi oleh wawasan dari @Nick Wiggill
AturSams
2
Seseorang dapat lebih meningkatkan hal ini dengan pertama-tama menggabungkan kelompok-kelompok sel yang berdekatan n * m menjadi satu persegi panjang tunggal. Ini menutupi grid yang mendasarinya masih terlihat di output di atas. Negosiasi dengan persegi panjang yang lebih besar ini sekarang harus bekerja pada semua sel di sepanjang salah satu ujungnya.
DMGregory
BAIK. Masih banyak batasan kolinear, saya akan mengusahakannya lebih jauh, tetapi bagus bahwa Anda telah menemukan solusi Anda! Senang membantu.
Insinyur
@ DMGregory Saya menganggap ini, tetapi saya ingin rasio antara rect kecil dan rect besar agak konsisten. Jika ini adalah tekstur atau level saya pasti akan melakukannya (Sebenarnya ada contoh sebelumnya yang melakukan itu).
AturSams
@NickWiggill Saya benar-benar dapat menghilangkan garis colinear. Ini hanya masalah mengutak-atik algoritma. Pasti ada cara untuk memperbaikinya lebih lanjut (perbarui dengan variasi terbaru)
AturSams