Membangun data adjacency segitiga

Diberikan daftar indeks segitiga, bagaimana tepatnya seseorang dapat mengubah itu menjadi daftar indeks dengan kedekatan untuk shader geometri?

Perhatikan bahwa kita benar-benar berbicara tentang indeks di sini - ada simpul, tetapi kita akan fokus hanya pada indeks, karena kita dapat menggunakannya untuk mencocokkan duplikat simpul tanpa harus masuk ke perbandingan titik mengambang dan epsilon - yang karya memiliki sudah dilakukan.

Saya tahu bahwa untuk setiap segitiga yang diberikan dalam daftar, indeks {0, 1}, {1, 2} dan {2, 0} (atau {n, n + 1}, {n + 1, n + 2}, { n + 2, n} jika Anda suka) dari itu membentuk tepi itu; daftar indeks terbentuk dengan baik dan menghormati urutan belitan dengan benar.

Saya tahu bahwa untuk setiap tepi yang diberikan tersebut, kita dapat mencari seluruh daftar untuk segitiga lain yang menggunakan dua indeks tersebut, dan indeks ketiga dari segitiga itu adalah yang digunakan untuk melengkapi segitiga yang berdekatan untuk tepi itu.

Saya tahu bahwa dalam daftar adjacency setiap segitiga asli diwakili oleh 6 indeks, indeks asli masuk ke slot 0, 2, 4; indeks baru untuk menyelesaikan adjacency masuk ke slot 1, 3, 5. Indeks untuk menyelesaikan edge {0, 1} masuk ke slot 1, indeks untuk menyelesaikan edge {1, 2} masuk ke slot 3, indeks untuk menyelesaikan edge {2, 1} masuk ke slot 5.

Apa yang sudah saya coba?

Saya sudah mencoba memaksakannya, dan ya, itu akan berhasil, tapi saya mencari pendekatan yang lebih elegan.

Saya sudah mencoba pembuat daftar tepi Eric Lengyel, tetapi (1) tampaknya tidak menghormati urutan segitiga asli, (2) tampaknya tidak menghormati urutan berkelok-kelok, (3) sejelas lumpur ke mana harus pergi selanjutnya setelah Anda membuat daftar tepi, dan (4) Saya mencurigai kode sampel yang memiliki kesalahan mencolok seperti "triangleIndex" versus "faceIndex" - apakah penulis bahkan menyusun kode, apalagi menjalankannya ke verifikasi itu?

Jadi - ada saran atau petunjuk dari sini?

Saya akan mencoba menggunakan tabel hash untuk ini (misalnya, std::unordered_mapjika Anda berada di C ++). Bangun tabel hash yang memetakan dari setengah sisi (dinyatakan sebagai sepasang indeks, secara berurutan) ke indeks ketiga segitiga yang dimiliki setengah sisi.

Ini dapat dibangun dengan hanya mengulangi daftar segitiga dan menambahkan masing-masing tiga sisi setengah segitiga ke tabel hash. Jika daftar indeks awal Anda memiliki sepasang segitiga yang berdekatan, (0, 1, 2, 2, 1, 3), Anda akan berakhir dengan tabel hash yang berisi:

(0, 1) -> 2
(1, 2) -> 0
(2, 0) -> 1
(2, 1) -> 3
(1, 3) -> 2
(3, 2) -> 1

Perhatikan bahwa tepi (1, 2) dan (2, 1) keduanya muncul dalam tabel, mewakili dua sisi tepi, dan menunjuk ke simpul ketiga dari masing-masing dua segitiga.

Kemudian, untuk membangun data kedekatan yang harus Anda lakukan adalah beralih ke daftar segitiga lagi, dan kueri setiap tepi segitiga dengan belitan yang berlawanan. Jadi saat memproses segitiga (0, 1, 2) Anda akan meminta tepi (1, 0), (2, 1), dan (0, 2). Ini akan menemukan titik kebalikan dari setiap sisi, jika ada.

Lihatlah struktur data setengah sisi .

Idenya kira-kira adalah Anda menyimpan daftar setengah sisi , misalnya setengah dari tepi tertentu yang melekat pada wajah tertentu. Struktur ini kemudian juga menyimpan informasi tentang setengah-tepi yang sesuai untuk wajah yang berdampingan.

Struktur data membuat pertanyaan tentang konektivitas, kedekatan, dan sebagainya sangat efisien. Ada algoritma untuk menghasilkan data secara efisien, meskipun tidak harus "waktu permainan" secara efisien (Anda mungkin ingin melakukan ini secara offline di pipa aset Anda).

Lihat juga posting blog ini . Saya percaya struktur dan algoritma juga dalam Deteksi Tabrakan Real-Time, tapi saya tidak ingat pasti dan tidak memiliki salinan di kantor.