Representasi peta berbentuk bola

Game terbaru saya akan berlangsung di planetoid kecil. Saya mencari struktur data yang baik untuk mewakili sel-sel pada permukaan bola. Segitiga, bujur sangkar, segilima, segi enam? Manakah yang meminimalkan bentangan paling banyak dan menciptakan ubin terbaik?

Pemetaan bola adalah yang termudah tetapi peregangan di kutub tidak dapat diterima. Kubemap juga cukup mudah tetapi masih akan ada bentangan besar di dekat sudut kubus. Membagi lagi icosahedron tampaknya yang terbaik dalam hal peregangan tetapi ada masalah pengindeksan banyak array segitiga dan menemukan sel-sel tetangga di perbatasan akan sulit.

Saya kira saya bisa menggunakan array linier tunggal dari poin yang mewakili N-gon, masing-masing dengan array dari indeks tetangga N, tetapi itu tampak seperti pemborosan besar ruang.

Gim ini memiliki elemen RTS jadi saya akan menyimpan hal-hal seperti memengaruhi peta dan melakukan pencarian jalan dan konvolusi A *, sehingga representasi harus efisien.

Oke, bagi siapa pun yang tertarik dengan topik ini sekarang saya akan merinci solusi yang saya pilih. Terima kasih untuk setiap orang yang menjawab dan memberi saya ide.

Pertama, untuk tesselation 'terbaik', saya akan memilih icosahedron yang terpotong sebagai titik awal. Membagi lagi itu mengarah pada sebuah tesselation hexagon yang sangat bagus dengan 12 pentagon menyediakan kelengkungan. Juga, melanjutkan subdivisi pada dual-nya akan memberi saya mesh segitiga yang sangat baik untuk rendering dengan properti bagus. Mengenai 12 sel pentagonal: Saya dapat mengabaikannya, menjadikannya istimewa (seperti satu-satunya tempat basis dapat dibangun), atau saya dapat menyembunyikannya di bawah pemandangan.

Sel-sel heksagonal dan pentagonal akan disimpan dalam struktur data setengah sisi untuk akses mudah ke tetangga dan traversal cepat. Satu-satunya bagian yang sulit adalah menemukan sel mana yang menjadi titik dunia tertentu, tetapi itu dapat dilakukan dengan mulai dari sel acak dan berjalan menuju titik melalui tetangga.

Saya harap seseorang menemukan informasi ini berguna. Saya telah belajar banyak dan berharap untuk mendapatkan beberapa hasil.

Edit:

Berikut adalah gambar yang menunjukkan hasil subdivisi icosahedron saya dan dual mesh switching menggunakan struktur data setengah-tepi.

Saya dapat melakukan beberapa iterasi relaksasi untuk mendapatkan area sel yang lebih seragam.

Ada cara untuk melakukan ini dengan agak elegan berdasarkan pembagian icosahedron, seperti yang Anda sarankan dalam pertanyaan Anda. Icosahedron terbuat dari 20 segitiga sama sisi, dan segitiga ini dapat dikelompokkan menjadi 5 set, di mana 4 segitiga dalam satu set membentuk bentuk jajaran genjang:

(Kelompok empat segitiga dengan coretan ditarik melalui mereka adalah jajaran genjang yang saya bicarakan. Panah mengatakan tepi mana yang akan direkatkan untuk melipat ini menjadi icosahedron.)

Jika segitiga ini dibagi lagi menjadi segitiga yang lebih kecil, seluruh jajaran genjang dapat diindeks seperti n oleh array persegi 4n (n = 4 dalam contoh):

Angka-angka di setiap sel adalah nomor kolom dari array persegi panjang. Aturan untuk menemukan tetangga dalam array cukup sederhana: tetangga horisontal hanya plus atau minus 1 kolom, sedangkan tetangga vertikal adalah minus satu baris dan ditambah satu kolom, atau ditambah satu baris dan minus satu kolom, tergantung pada apakah nomor kolom genap atau ganjil, masing-masing.

Namun, Anda masih harus menulis beberapa kode kasus khusus untuk menemukan tetangga yang melewati batas dari satu jajaran genjang ke berikutnya. Agak sulit karena di beberapa tempat, bagian atas atau bawah satu jajaran genjang akan terhubung ke sisi genjang lainnya, atau bagian atas dan bawah akan dihubungkan dengan offset horizontal di antara mereka, dll. Mungkin struktur setengah sisi atau serupa untuk jajaran genjang akan berguna di sini. Namun, setidaknya hubungan itu simetris di antara semua 5 jajaran genjang: mereka semua mengikuti pola yang sama di mana sisi terhubung ke sisi lain tetangga mereka.

Hmmm - komentar tentang stretch menunjukkan Anda bergerak antara pemetaan bola dan planar, itulah yang menyebabkan distorsi di kutub

Jika Anda ingin ubin menjadi rata dan seragam, Anda benar bahwa icosahedron, khususnya icosahedron yang terpotong cukup umum

Anda dapat menemukan semua pemetaan yang berbeda di sini - Polyhedron Bulat di wikipedia

Sejauh mempertahankan hubungan di antara wajah-wajah, itu adalah masalah topologi - Anda mungkin menemukan baik ujung bersayap atau ujung kuadrat membantu (dan Anda mendapatkan kesempatan luar biasa untuk memenuhi bentuk aljabar yang sama sekali baru) Winged Edge

Saya kira saya datang sedikit terlambat ke pesta, tapi di sini ada solusi yang dapat digunakan untuk mempertahankan dunia bola ukuran sewenang-wenang dan penampilan seragam.

Hal utama yang harus dipahami di sini adalah bahwa dunia tidak datar, dan oleh karena itu ubin seragam 100% tidak mungkin (ini mengikuti apa yang disebut Hairor Ball Theorem ). Beberapa penyimpangan harus diizinkan, dan yang terbaik yang bisa kita harapkan adalah menyebarkan penyimpangan itu secara merata di permukaan, membuat masing-masing sekecil mungkin.

Ini sebenarnya cukup mudah dilakukan dengan cara non-deterministik. Pertama, pilih N titik acak secara seragam di sekitar permukaan. Pastikan titik-titik tersebut benar-benar seragam (lihat Pemungutan titik Sphere , rumus 9-11). Pada langkah kedua kita membuat titik-titik itu kurang acak dan lebih seragam: anggap semua titik memiliki muatan listrik negatif sehingga mereka saling tolak. Simulasikan pergerakan titik untuk beberapa langkah, sampai titik-titik tersebut menyatu menjadi keadaan setimbang. Konfigurasi akhir dari titik-titik ini akan memberi Anda jaring yang hampir merata di sekitar permukaan bola.