Bagaimana saya bisa melakukan tes dalam segitiga di jerat poligon?

10

masukkan deskripsi gambar di sini Saya memiliki 3 simpul yang (V1, V2, V3)dipilih secara acak pada mesh segitiga biasa. Untuk 3 simpul ini, saya telah menghitung jarak geodesik dan jalur (dengan menggunakan Dijkstra) di antara mereka dan membentuk permukaan seperti segitiga seperti pada gambar di atas.

Sekarang, saya memiliki simpul yang terletak di setiap jalur dan dapat menghitung jarak geodesik dari titik tertentu.

Yang ingin saya lakukan adalah mendapatkan simpul atau segitiga yang terletak di area seperti segitiga. Bagaimana saya bisa melakukan ini?

mesh triangulation mkocabas
sumber
2
Dengan asumsi bahwa pendekatan barycentric melakukan apa yang saya pikir itu akan cukup lambat dengan set besar. Bayangkan satu set 9 juta simpul dengan hanya 9 simpul pada set yang diinginkan. Mengapa iterate seluruh set ketika v1, v2, dan v3 memberi Anda semua informasi yang Anda butuhkan. Jawaban mengisi banjir akan menjadi solusi fleksibel tercepat. Meskipun tidak fleksibel, jika Anda dapat mengasumsikan bahwa Anda memiliki garis seperti yang Anda lakukan sekarang dalam geometri maka scanline akan menjadi pendekatan tercepat.
Andrew Wilson
Anda benar tentang masalah kinerja. Saya ingin menggunakan pendekatan ini dalam kaitan besar, jadi apa yang saya cari adalah metode yang efisien. Sebenarnya saya tidak terbiasa dengan mengisi banjir atau memindai algoritma mengisi, saya akan melihatnya. Terima kasih.
mkocabas
3
Isi banjir dengan grafik akan dimulai pada sebuah node, mengunjungi setiap node tetangga jika kondisi batas dipenuhi dan tidak dikunjungi, tandai sebagai dikunjungi, dan ulangi (rekursi). Alteration: tandai setiap node di jalur sebagai dikunjungi dan mulai dari node di dalam set. Kemudian cukup gunakan pemeriksaan kunjungan sebagai kondisi batas.
Andrew Wilson
Terima kasih untuk penjelasan rinci. Saya menemukan pengisian banjir juga lebih masuk akal, tetapi saya ingin menerapkan pengisian banjir dan pemindaian baris, kemudian membandingkan kinerjanya.
mkocabas

Jawaban:

4

Ada metode alternatif yang mengandalkan pengisian banjir. Pertama-tama, atur data tepi Anda menjadi loop di mana ujung-ujungnya membentuk loop berlawanan arah jarum jam. Kemudian mulailah dari titik arbitrer pada loop dan pilih tepi yang menghubungkan titik tersebut. Gunakan tepi batas keluar dan silangkan dengan tepi keluar lainnya, jika itu menunjuk ke arah wajah normal maka itu adalah tepi yang akan dimasukkan, jika tidak membuangnya. Dari tepi ini terus sampai Anda mencapai tepi batas, pada titik mana Anda mengakhiri isian. Lanjutkan di vertex tepi batas yang belum dikunjungi.

joojaa
sumber
Saya tidak terbiasa dengan algoritma pengisian banjir. Penjelasan Anda tampaknya sedikit rumit bagi saya. Bisakah Anda memberikan referensi yang layak untuk dilihat? Terima kasih.
mkocabas
Saya mendapatkan solusinya dengan membaca beberapa. Terima kasih.
mkocabas
3

Saya sudah berkomentar tentang penggunaan mengisi banjir dan bagaimana akan lebih baik karena lebih fleksibel tetapi solusi lain yang mungkin adalah scanline. (Saya katakan mungkin karena itu membuat banyak asumsi tentang geometri Anda tetapi untuk himpunan tertentu yang ditampilkan dan banyak yang serupa itu akan berhasil.)

Sebagai contoh Anda dengan 3 poin: Temukan vertex persimpangan dari segmen v1, v2 dan garis di mana v3 terletak. (Titik ke kiri atas v2) Kami akan memanggil titik ini v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

masukkan deskripsi gambar di sini

Ini disebut scanline karena (pada gambar di atas) Anda turun garis merah dan hijau secara bersamaan dan kemudian garis merah dan biru secara bersamaan memindai garis saat Anda pergi.

Solusi ini akan sangat cepat jika ada pola indeks, yang sering terjadi. Kalau tidak, perhitungan akan diperlukan untuk menentukan titik tetangga yang terletak di garis.

Lucunya adalah scanline, pengujian barycentric (dalam kotak pembatas segitiga), dan mengisi banjir adalah semua cara menggambar segitiga dalam rendering 3d.

Andrew Wilson
sumber
2

Saya pikir Anda dapat menghitung beberapa koordinat barikentrik permukaan-terikat untuk setiap titik di permukaan, dan kemudian menggunakannya untuk memeriksa di dalam atau di luar segitiga.

Saya tidak memiliki algoritma yang tepat di tangan tetapi saya menemukan makalah berikut ini yang tampaknya menangani persis koordinat semacam ini.

Barycentric Coordinates On Surface

Dragonseel
sumber
Terima kasih atas jawaban dan makalah referensi. Saya akan mencoba menerapkan metode yang diusulkan.
mkocabas