Dalam kebanyakan sistem desain (CAD), representasi utama dari objek yang disimulasikan adalah representasi batas geometri atau B-rep (Representasi batas). Tetapi semakin, pengguna CAD harus berurusan dengan model poligon, misalnya, diperoleh sebagai hasil pemindaian 3D atau dipinjam dari katalog online.
Untuk membuatnya cocok untuk pekerjaan lebih lanjut, Anda perlu mengubah poligon menjadi model B-rep. Dan ini tidak mudah sama sekali.
Kami mengembangkan komponen perangkat lunak C3D B-Shaper, yang terintegrasi ke dalam sistem desain dan mengubah model poligon menjadi representasi batas. Dalam posting ini kami akan menunjukkan algoritma konversi dan contoh implementasi di C ++.




Apa masalah utama model poligonal dalam hal CAD? Alat tradisional tidak dapat diterapkan padanya - untuk melakukan operasi Boolean, untuk membangun chamfer dan fillet, untuk mendapatkan proyeksi dan bagian. Jika menggunakan model B-rep untuk membangun representasi poligonnya cukup mudah (ini dilakukan dengan menggunakan triangulasi), maka transformasi terbalik jauh lebih sulit. Sejumlah masalah muncul - pengenalan permukaan berbagai jenis (termasuk permukaan bentuk bebas), adanya kebisingan, yang merupakan karakteristik, misalnya, dari hasil pemindaian 3D.

Di SDK baru, kami menerapkan mekanisme tiga tahap untuk mengubah model poligon menjadi B-rep: segmentasi, rekonstruksi permukaan, konstruksi model B-rep. Secara umum, proses diasumsikan berulang: jika karena alasan tertentu pengguna tidak puas dengan hasilnya, maka ia dapat membuat perubahan korektif yang diperlukan pada tahap segmentasi dan rekonstruksi permukaan.


Skema untuk mengubah representasi poligon menjadi batas

Sebelum memulai proses konversi ke B-rep, perlu, dalam beberapa kasus, untuk meningkatkan kualitas mesh poligon asli: mengoordinasikan arah normal di poligon tetangga, menghilangkan "lubang", menerapkan algoritma penghalusan di hadapan kebisingan di mesh asli.

Segmentasi poligon

Pada tahap pertama, set awal poligon jala diklasifikasikan menjadi subset (segmen). Informasi tentang normals pada simpul mesh memungkinkan segmentasi orde pertama dan dengan demikian memastikan partisi mesh awal, serta mengklasifikasikan daerah datar atau sangat melengkung.

Penyambungan awal didasarkan pada definisi yang disebut "tajam" tepi - tepi tersebut antara dua poligon segitiga yang sudut antara normals rata-rata melebihi nilai yang telah ditentukan sebelumnya.

Segmentasi orde kedua menganalisis grid sesuai dengan kelengkungan utamanya, yang memberikan dasar yang cukup untuk klasifikasi permukaan dasar. Dalam menghitung kelengkungan pada simpul kisi-kisi, kami menggunakan hasil Mayer (Mark Meyer, Mathieu Desbrun, Peter Schroder, dan Alan H. Barr, operator Geometri Diferensial-Diskrit untuk Triangulasi 2-Manifold, Visualisasi dan Matematika III, 2003) untuk menentukan perbedaan diskrit operator untuk daerah triangulasi: untuk setiap simpul dari mesh asli, kami mempertimbangkan satu set simpul tetangga yang terkait dengan simpul yang diberikan melalui tepi. Kemudian, operator diskrit K dihitung untuk verteks yang diberikan, berdasarkan yang rata-rata normal, rata-rata KH _, dan kelengkungan Gaussian KG pada vertex grid ditentukan.


Pada definisi operator diferensial diskrit untuk domain triangulasi

Dengan demikian, tensor kelengkungan untuk setiap vertex dari grid dihitung, nilai eigen yang merupakan kelengkungan utama yang diinginkan K ₁ dan K ₂ , dan vektor eigen adalah arah utama dari perubahan kelengkungan.

Selanjutnya, simpul-simpul mesh diklasifikasi sesuai dengan nilai-nilai lekukan utama K ₁ dan K _{2 yang} dihitung di dalamnya. Algoritma klasifikasi vertex didasarkan pada metode k-means, yaitu, pada meminimalkan deviasi kuadrat total poin cluster dari pusat-pusat cluster ini. Akibatnya, pada output dari algoritma, setiap dhuwur dari grid dikaitkan dengan cluster tertentu $$$Ci$dan sepasang kelengkungan (pusat klaster) (L. Guillaume, "Segitiga Berbasis Kelengkungan Tensor Berbasis Kelengkungan dengan Rektifikasi Batas", Prosiding Computer Graphics International (CGI), 2004).


Klasifikasi simpul dari poligonal mesh dalam ruang lengkungan

Setelah mengklasifikasikan simpul dari poligon, perlu untuk mengklasifikasikan poligon. Pada awal prosedur ini, poligon segitiga dipilih yang kelengkungannya dapat dipertimbangkan secara lengkap (ketiga simpul itu milik satu kelompok atau dua simpul terletak di tepi yang tajam). Poligon ini dinyatakan sebagai segmen baru, dan prosedur rekursif untuk memperluas segmen dimulai dari itu: untuk setiap poligon segitiga, poligon yang berdekatan dengannya dianggap, asalkan tepi di antara mereka tidak "tajam".

Jika titik dari poligon tetangga, di seberang tepi yang sama, terletak di tepi yang tajam atau milik kelompok yang sama, maka poligon ini ditambahkan ke segmen. Proses ini diulangi sampai semua poligon dari grid ini dilihat. Inilah yang terlihat seperti mekanisme segmentasi mesh yang diterapkan.


Mekanisme segmentasi poligon mesh

Pada akhir prosedur pembentukan segmen, algoritma khusus untuk menjahit segmen yang berdekatan dilakukan untuk menghilangkan segmentasi yang berlebihan dari mesh yang dimaksud.

Pengenalan permukaan

Pada tahap kedua, masing-masing segmen harus dikaitkan dengan permukaan tertentu yang mendekati bentuknya dengan akurasi tertentu. Pertama-tama, nilai-nilai lengkungan utama untuk segmen tertentu menentukan kemungkinan menggambarkan bentuk segmen oleh permukaan dasar:

• pesawat: k ₁ = k ₂ = 0
• bola: k ₁ = k ₂ = K > 0
• silinder: k ₁ = K > 0, k ₂ = 0
• kerucut: k ₁ ∈ [ a , b ], k ₂ = 0
• torus: k ₁ = K , k ₂ ∈ [ a , b ]

Jika tidak ada permukaan dasar yang cocok untuk menggambarkan segmen, algoritma akan mencoba mengenali permukaan ekstrusi atau rotasi. Pada akhirnya, jika tidak mungkin untuk memilih permukaan analitis untuk menggambarkan bentuk segmen, permukaan NURBS akan dibangun untuk itu.

Permukaan elementer dikonstruksi menggunakan metode pemasangan benda geometris sederhana ke dalam satu set titik. Jadi, agar sesuai dengan lingkaran dan bola, metode kuadrat terkecil digunakan, agar sesuai dengan bidang - metode komponen utama. Setiap permukaan yang direkonstruksi diperiksa untuk kesesuaian dengan segmen untuk akurasi pengakuan yang diberikan.

Untuk kejelasan, kami melukis permukaan yang dikenal dalam berbagai warna: bidang - biru, silinder - merah, bola - hijau, kerucut - kuning, tori - ungu.


Mesh poligon asli (kiri) dan mesh tersegmentasi (kanan) dengan permukaan yang dikenali pada segmen

Membangun Model B-rep

Tahap akhir dari transformasi adalah pembangunan model B-rep berdasarkan segmentasi permukaan yang dikenal. Dalam pendekatan ini, grafik daerah yang berdekatan dibangun berdasarkan wilayah yang disegmentasi, yang mencerminkan topologi model dan berfungsi sebagai dasar untuk membangun model B-rep akhir.

Tidak seperti tahap konversi sebelumnya, rakitan B-rep dilakukan dalam mode otomatis sepenuhnya: garis-garis persimpangan dari permukaan-permukaan yang direkonstruksi ditemukan, tepi-tepi permukaan dibangun di atasnya, permukaan-permukaan itu sendiri dan, akhirnya, kulit B-rep dirakit.




Mesh poligon asli (kiri) dan model B-rep (kanan)

Namun, tidak selalu memungkinkan untuk membuat shell yang benar secara topologi. Sebagai contoh dari situasi seperti itu, anggaplah bahwa selama rekonstruksi permukaan kita memiliki dua permukaan - silinder dan pesawat, dan posisi mereka di ruang dekat dengan garis singgung. Karena kesalahan dalam rekonstruksi permukaan persimpangan mereka, mungkin tidak ada sama sekali. Dalam kasus tersebut, shell dapat dibuat dengan beberapa cacat yang dapat diperbaiki pengguna dengan menyesuaikan parameter permukaan dengan benar.

Jenis model poligonal dan pilihan mode konversi

Saat ini, ada beberapa sumber utama model dalam representasi poligonal:

• katalog online, basis data model 3D dalam format poligon (STL, VRML, OBJ), misalnya Gudang 3D, Cults 3D, dll.
• Hasil pemindaian 3D
• hasil optimasi model topologi oleh CAE-algoritma.

Model poligonal dari sumber-sumber ini dapat dibagi menjadi dua kelompok: yang pertama meliputi model yang merupakan triangulasi objek B-rep, dan yang kedua - yang lainnya. Perbedaan karakteristik dari kelompok pertama adalah tidak adanya kebisingan dalam mesh poligonal dan dominasi permukaan yang didefinisikan secara analitis. Dengan demikian, konversi ke model B-rep dari kelompok pertama akan berlangsung baik dalam mode otomatis penuh atau dengan intervensi pengguna minimal.

Grid poligonal dari model kelompok kedua menyiratkan interaksi interaktif yang lebih padat dengan pengguna. Karena itu, pada awalnya kami meletakkan dua mode operasi di C3D B-Shaper - sepenuhnya otomatis dan interaktif.

Pilihan mode tertentu juga tergantung pada tujuan transformasi: dalam beberapa kasus, konektivitas topologi elemen shell yang dihasilkan, serta kebenarannya, dapat diabaikan. Pendekatan semacam itu dapat diterima, misalnya, untuk mengoptimalkan rendering dalam aplikasi BIM, ketika pengguna dapat menambahkan item interior yang sewenang-wenang ke model ruangan saat ini. Di sisi lain, untuk tugas rekayasa balik, perlu untuk mendapatkan salinan paling akurat dari model asli, misalnya, untuk menjaga keselarasan silinder dengan akurasi yang diberikan, untuk memastikan lokasi bersinggungan dari sepasang permukaan dan, sebagai akibatnya, untuk mendapatkan topologi model yang benar - dalam kasus ini, Anda tidak dapat melakukannya tanpa campur tangan pengguna dalam proses konversi.

Antarmuka konversi otomatis B-Shaper C3D diwakili oleh fungsi-fungsi berikut, yang menerima kisi input dan pengaturan konversi sebagai input:

MbResultType ConvertMeshToShell( MbMesh & mesh, MbFaceShell *& shell, const MbMeshProcessorValues & params ); MbResultType ConvertCollectionToShell( MbCollection & collection, MbFaceShell *& shell, const MbMeshProcessorValues & params ); 

Pengaturan konversi mencakup nilai akurasi pengenalan, mis. jarak maksimum yang diijinkan dari simpul mesh poligonal dalam batas-batas segmen ini ke permukaan yang dikenali. Akurasi ini bisa absolut atau relatif: ketika menggunakan akurasi relatif, penyimpangan wajah-wajah tubuh dari grid diperiksa sehubungan dengan ukuran model.

Selain itu, pengguna memiliki opsi untuk beralih mode pengenalan, yang memungkinkan Anda untuk mengontrol jenis permukaan selama rekonstruksi.
Kemampuan canggih untuk mengelola segmentasi dan proses pengenalan permukaan disediakan oleh antarmuka kelas MbMeshProcessor:

 class MbMeshProcessor { .. public: // “” . void SetUseMeshSmoothing( bool useSmoothing ); //   . const MbCollection & GetSegmentedMesh(); MbResultType SegmentMesh( bool createSurfaces = true ); void ResetSegmentation(); void UniteSegments( size_t firstSegmentIdx, size_t secondSegmentIdx ); MbResultType SegmentMeshBySeparators( const std::vector<std::vector<uint>> & sep ); //   . void FitSurfaceToSegment( size_t idxSegment ); void FitSurfaceToSegment( size_t idxSegment, MbeSpaceType surfaceType ); const MbSurface * GetSegmentSurface( size_t idxSegment ) const; //  B-rep . MbResultType CreateBRepShell( MbFaceShell *& pShell ); .. } 

Misalnya, untuk memperbaiki hasil segmentasi otomatis, alat disediakan untuk menggabungkan segmen, memisahkan mereka, dll. Pengguna dapat memasukkan permukaan jenis tertentu di segmen, serta mengubah parameter untuk permukaan yang sudah dikenal.

Apa yang terjadi sekarang?

Pada bulan Juli, kami merilis versi pertama komponen dan sekarang terus berkembang di beberapa bidang: algoritma segmentasi otomatis, alat pengeditan segmentasi, membangun permukaan bentuk bebas (NURBS) berdasarkan segmen, dan meningkatkan kualitas build dari kerang B-rep.

Pengembang yang tertarik dapat menguji B-Shaper C3D. Komponen disediakan gratis selama tiga bulan berdasarkan permintaan di situs web kami.

Penulis - Andrey Tumanin, Ph.D., matematikawan-programmer C3D Labs