operasi boolean pada jerat

15

diberikan satu set simpul dan segitiga untuk setiap mesh. Apakah ada yang tahu tentang algoritma, atau tempat untuk mulai mencari (saya mencoba google terlebih dahulu tetapi belum menemukan tempat yang baik untuk memulai) untuk melakukan operasi boolean pada jerat tersebut dan mendapatkan satu set simpul dan segitiga untuk mesh yang dihasilkan? Yang menarik adalah pengurangan dan persatuan.

Contoh gambar: http://www.rhino3d.com/4/help/Commands/Booleans.htm

graphics algorithm graphics-programming procedural lathomas64
sumber

Jawaban:

10

Saya menganggap ini sebagai Constructive-Solid-Geometry (CSG). Semoga Anda dapat menemukan bantuan di sini.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Juga cari google untuk Constructive Solid Geometry sebagai permulaan.

HTH

JustBoo
sumber
+1 - Saya akan memposting tautan yang sama, JustBoo - sampai saya perhatikan bahwa Anda mengalahkan saya! :)
jacmoe
Terima kasih! Terminologi Konstruktif-Solid-Geometri adalah persis apa yang saya butuhkan!
lathomas64
@ jacmoe - Ironinya luar biasa dan lengkap sekarang :-) Anda layak mendapatkan penghargaan untuk beberapa di antaranya. Terima kasih.
JustBoo
beberapa di antaranya? : PI yakin saya mencatat semuanya di sana. : D Tetap saja, itu hanya hal-hal dasar CSG. Itu menjadi sangat berbulu dari sana - bahkan paket pemodelan komersial utama tidak melakukannya dengan benar.
jacmoe
3

Saya pikir kita dapat memecahkannya jika kita hanya memikirkannya.

Anda tentu ingin membuat wajah (segitiga) tempat kedua geometri berpotongan. Kemudian Anda pergi dengan tiga jerat: persimpangan Anda baru saja diisolasi, geometri 1, dan geometri 2.

Kemudian, hapus saja apa yang tidak Anda butuhkan!

  • BooleanDifference: hapus bagian yang terisolasi dan geometri 2.
  • BooleanIntersection: hapus geometri 1 dan 2, biarkan bagian yang terisolasi
  • BooleanUnion: gabungkan geometri 1 dan 2 dan hapus bagian yang terisolasi (pastikan untuk menyatukan geometri 1 dan 2 menjadi geometri yang solid)
  • BooleanSplit: Pisahkan geometri 1, geometri 2, dan duplikat bagian yang terisolasi (pasang satu ke geometri 1 dan yang lain ke geometri 2)

Saya pikir itu menutupinya, eh? Bagian yang sulit jelas akan membuat wajah persimpangan. Untuk itu, ulangi setiap wajah satu dan periksa apakah wajah itu adalah bagian dari yang lain; jika benar-benar di dalam, salin wajah sebagai bagian dari persimpangan persimpangan. Jika sebagian berada di dalam, maka Anda perlu membagi segitiga di sepanjang garis persimpangan; Saya pikir DirectX dan OpenGL keduanya akan memiliki fungsi pembantu untuk ini, atau itu hanya beberapa bidang matematika 3D (vektor). Saya belajar hal semacam itu dalam Kalkulus 3 (atau apakah itu 2?) Tetapi jika Anda tidak memiliki petunjuk, mungkin bertanya di math.stackexchange.com . Dan tentu saja jika wajahnya ada di luar, jangan lakukan apa-apa. Setelah Anda mengulangi semua wajah dari kedua jerat Anda akan ditinggalkan dengan persimpangan mesh.

Ricket
sumber
2

Jika Anda berurusan dengan model poligonal, Anda mungkin harus berurusan dengan geometri yang tidak berlipat ganda, yang berarti pertanyaan tentang apa yang "di dalam" dan apa yang "di luar" tidak didefinisikan. Sulit untuk melakukan operasi boolean jika Anda tidak tahu apakah Anda memiliki 0 atau 1.

Anda juga harus berurusan dengan kasus pinggiran seperti poligon co-planar, poligon yang berpotongan tepi, simpul yang terletak di tepi dan / atau wajah, dan hal-hal semacam itu. Tidak ada yang tidak mungkin, Anda hanya perlu cara yang sangat kuat untuk mewakili data mesh Anda, dan definisi yang ketat tentang apa yang Anda harapkan terjadi dalam kasus tersebut.

JasonD
sumber
1

Perlu dicatat bahwa sebagian besar operasi Anda dapat diwakili oleh negasi dan penyatuan, di mana negasi dari beberapa geometri hanya geometri dengan normalnya yang dibalik. Jadi, jika Anda bisa mendapatkan serikat dengan benar, maka operasi lain hanya harus mengikuti:

  • persimpangan (A, B): =! union (! A,! B)
  • kurangi (A dan B): =! union (! A, B)

Sander memiliki beberapa posting blog yang cukup baik yang membahas implementasi CSG: http://sandervanrossen.blogspot.com/search/label/CSG

jpaver
sumber
1
Saya akan menyebutkan hal-hal CSG saya sendiri, tetapi ternyata orang lain sudah melakukannya: O)
Sander van Rossen