Subdivisi permukaan

Dalam bidang komputer grafis 3D, subdivisi permukaan (biasanya disingkat SubD permukaan) merupakan representasi permukaan halus dari mesh poligon lebih kasar yang dihasilkan menggunakan algoritma rekursif. Permukaan halus ini berada di bawah permukaan aslinya yang kasar.^[1] Pemukaan halus tersebut dapat dihitung dari mesh kasarnya, yang disebut sangkar kendali (control cage) atau mesh luar. Sangkar kendali ini berfungsi sebagai batas fungsional dari proses berulang yang membagi setiap permukaan poligonal menjadi permukaan lebih kecil yang lebih halus dan mendekati bentuk asli dari permukaan kasarnya. Terkadang, algoritma sederhana digunakan untuk menambah geometri pada mesh dengan men-subdivisi permukaannya menjadi lebih kecil tanpa mengubah bentuk dan volume keseluruhan objek.

Kebalikannya dari proses ini adalah pengurangan poligon atau unsubdivisi .^[2]

Ringkasan

Algoritma subdivisi permukaan secara alami bersifat rekursif. Prosesnya dimulai dengan mesh poligon tingkat dasar. Skema penghalusan akan diterapkan pada mesh ini. Proses ini meggunakan mesh tersebut dan membaginya menjadi kecil-kecil, menciptakan verteks dan sisi (face) baru. Posisi verteks baru yang terbentuk ditentukan berdasarkan posisi verteks, rusuk (edge), dan/atau sisi mesh lama yang berdekatan. Dalam banyak skema penyempurnaan, posisi verteks lama juga mungkin diubah berdasarkan posisi verteks baru.

Proses ini menghasilkan mesh yang lebih padat daripada mesh aslinya, yang memiliki lebih banyak sisi poligon (dalam banyak kasus 4 kali lipatnya). Mesh-mesh yang dihasilkan ini dapat melalui skema penghalusan yang sama berulang kali untuk menghasilkan mesh yang lebih halus lagi. Setiap pengulangan ini sering disebut sebagai level subdivisi, dimulai dari nol (sebelum proses penghalusan terjadi).

Batas dari proses subdivisi permukaan adalah permukaan yang diasilkan dari diterapkannya proses subdivisi berulang kali sampai tak berhingga. Meskipun dalam penggunaannya, algortima ini digunakan secara terbatas hanya sampai 5 kali pengulangan.

Secara matematis, verteks khusus (verteks yang terbentuk dari pertemuan kurang dari atau lebih dari empat rusuk) yang bertetangga pada permukaan subdivisi adalah sebuah spline dengan titik tunggal secara parametrik. ^[3]

Skema penghalusan

Skema penghalusan pada subdivisi permukaan secara garis besar dapat digolongkan menjadi dua kategori: interpolasi dan perkiraan.

Skema interpolasi diperlukan untuk mencocokkan posisi awal verteks pada mesh asli
Skema perkiraan dapat menyesuaikan posisi verteks sesuai kebutuhan.

Secara umum, skema perkiraan akan membuat hasil yang lebih halus, namun pengguna tidak memiliki banyak kendali pada mesh yang dihasilkan. Hal ini mirip dengan permukaan dan kurva pada spline, dimana kurva Bézier diperlukan untuk menginterpolasi titik kendali (control point) tertentu, sedangkan B-Spline tidak.

Proses subdivisi permukaan juga dapat digolongkan berdasarkan jenis poligon di mana proses ini dilakukan, pada mesh segi empat (quad), dan pada mesh segitiga (tris). Namun sebagian besar proses ini berfungsi dengan baik pada mesh segi empat.

Skema perkiraan

Perkiraan artinya permukaan batas mendekati bentuk awal mesh, dan setelah pembagian, titik kendali baru yang dihasilkan tidak berada pada permukaan batas.^{[butuh klarifikasi]} Ada lima skema subdivisi perkiraan:

Catmull dan Clark (1978), Segi empat – menggeneralisasi penyisipan simpul B-spline seragam bi-kubik . Untuk mesh awal yang berubah-ubah, skema ini menghasilkan permukaan batas yang kontinu C2 di semua tempat kecuali pada verteks khusus yang kontinu C1 (Peters dan Reif 1998). ^[4]
Doo-Sabin (1978), Segi empat – Skema subdivisi kedua dikembangkan oleh Doo dan Sabin, yang berhasil memperluas metode pemotongan sudut Chaikin (George Chaikin, 1974 ^[5] ) untuk kurva ke permukaan. Mereka menggunakan ekspresi analitik dari permukaan B-spline seragam bi-kuadrat untuk menghasilkan prosedur subdivisi untuk menghasilkan permukaan batas C 1 dengan sebarang topologi untuk sebarang mesh awal. Titik tambahan dapat memperbaiki bentuk subdivisi Doo-Sabin. ^[6] Setelah dilakukan subdivisi, semua verteks memiliki valensi 4.^[7]
Loop (1987), Segitiga – Loop mengusulkan skema pembagiannya berdasarkan kotak-spline kuartik dari enam vektor arah untuk memberikan aturan untuk menghasilkan permukaan batas kontinu C 2 di mana pun kecuali pada verteks khusus di mana permukaan tersebut kontinu C 1 (Zorin 1997).
Skema subdivisi Mid-Edge (1997–1999) – Skema subdivisi mid-edge diusulkan secara independen oleh Peters-Reif (1997) ^[8] dan Habib-Warren (1999). ^[9] Yang pertama menggunakan titik tengah setiap rusuk untuk membuat mesh baru. Yang terakhir menggunakan spline kotak empat arah untuk membangun skema. Skema ini menghasilkan permukaan batas kontinu C 1 pada mesh awal dengan sebarang topologi. (Subdivisi Mid-Edge, yang bisa disebut "√2 subdivisi" karena dua langkah membagi dua jarak, bisa dianggap paling lambat. )
√3 skema subdivisi (2000), Segitiga – Skema ini dikembangkan oleh Kobbelt ^[10] dan menawarkan beberapa fitur menarik: menangani jerat segitiga sembarang, kontinu C 2 di semua tempat kecuali pada verteks khusus yang merupakan kontinu C 1 dan menawarkan penyempurnaan adaptif alami bila diperlukan. Ini menunjukkan setidaknya dua kekhususan: ini adalah skema Ganda untuk mesh segitiga dan memiliki tingkat penghalusan yang lebih lambat dibandingkan skema primal.

Skema Subdivisi

Catmull–Clark

Doo–Sabin

Loop

Skema interpolasi

Setelah dilakukan subdivisi, titik kendali dari mesh asli dan titik kendali mesh baru akan diinterpolasi ke permukaan batas. Dalam karya paling awal pada tahun 1990 oleh Dyn, Levin dan Gregory skema ini disebut sebagai " skema kupu-kupu ". Skema ini memperluas skema pembagian interpolasi empat titik untuk kurva menjadi skema pembagian permukaan. Zorin, Schröder dan Sweldens pada tahun 1996 menyadari bahwa skema kupu-kupu tidak dapat menghasil permukaan halus untuk mesh segitiga tak beraturan, karenanya mereka memodifikasi skema ini. Lebih lanjut, Kobbelt (1996) menyamaratakan skema subdivisi interpolasi empat titik untuk kurva ke skema subdivisi produk tensor untuk permukaan. Pada tahun 1991, Nasri mengusulkan skema interpolasi Doo-Sabin; ^[11] sedangkan pada tahun 1993 Halstead, Kass, dan DeRose mengusulkan skema interpolasi untuk Catmull-Clark.^[12]

Kupu-kupu (1990), Segitiga – diberi nama berdasarkan bentuk skema
Modified Butterfly (1996), Segi empat ^[13] – dirancang untuk mengatasi artefak yang dihasilkan oleh topologi tidak beraturan
Kobbelt (1996), Segi empat – variasi metode subdivisi yang mencoba mengatasi kelemahan subdivisi seragam

Perkembangan penting

1978: Subdivisi permukaan dijabarkan oleh Edwin Catmull dan Jim Clark (lihat subdivisi permukaan Catmull-Clark ), dan oleh Daniel Doo dan Malcom Sabin (lihat subdivisi permukaan Doo-Sabin ).
1995: Ulrich Reif memecahkan perilaku permukaan subdivisi di dekat verteks yang luar biasa. ^[14]
1998: Jos Stam menyumbangkan metode untuk evaluasi tepat pada subdivisi permukaan Catmull-Clark berdasarkan parameter yang berubah-ubah. ^[15]

Lihat juga

Geri's Game (1997) – film Pixar yang memelopori penggunaan subdivisi permukaan untuk menggambarkan kulit manusia
Permukaan B-spline rasional tidak seragam (NURBS) – metode lain untuk merepresentasikan permukaan melengkung

Referensi

^ "Subdivision Surfaces". nevercenter.com. Diakses tanggal 19 January 2021.
^ Blender: Reduce Polygons – Simply Explained
^ J. Peters and U. Reif: Subdivision Surfaces, Springer series Geometry and Computing monograph 3, 2008, doi
^ J. Peters and U. Reif: Analysis of generalized B-spline subdivision algorithms, SIAM J of Numer. Anal. 32 (2) 1998, p.728-748
^ "Chaikin Curves in Processing".
^ K. Karciauskas and J. Peters: Point-augmented biquadratic C¹ subdivision surfaces, Graphical Models, 77, p.18-26
^ Joy, Ken (1996–2000). "DOO-SABIN SURFACES" (PDF). On-Line Geometric Modeling Notes.
^ J. Peters and U. Reif: The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics 16(4) (October 1997) p.420-431, doi
^ A. Habib and J. Warren: Edge and vertex insertion for a class of C¹ subdivision surfaces, Computer Aided Geometric Design 16(4) (May 1999) p.223-247, doi
^ L. Kobbelt: √3-subdivision, 27th annual conference on Computer graphics and interactive techniques, doi
^ Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991), 89–96.
^ Halstead, M., Kass, M., and DeRose, T. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph
^ Zorin, Denis; Schröder, Peter; Sweldens, Wim (1996). "Interpolating Subdivision for Meshes with Arbitrary Topology" (PDF). Department of Computer Science, California Institute of Technology, Pasadena, CA 91125.
^ Ulrich Reif. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design. 12(2)153–174
^ Jos Stam, "Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values", Proceedings of SIGGRAPH'98. In Computer Graphics Proceedings, ACM SIGGRAPH, 1998, 395–404

Pranala luar

Permainan Geri : Animasi pemenang Oscar oleh Pixar yang diselesaikan pada tahun 1997 yang memperkenalkan subdivisi permukaan menggunakan subdivisi Catmull-Clark (bersama dengan simulasi kain)
Subbagian tutorial Pemodelan dan Animasi, catatan mata kuliah SIGGRAPH 1999
Subbagian tutorial Pemodelan dan Animasi, catatan mata kuliah SIGGRAPH 2000
Pendekatan terpadu untuk algoritma subdivisi dekat simpul luar biasa, Ulrich Reif (Computer Aided Geometric Design 12(2):153–174 Maret 1995)
Subdivisi Jerat Permukaan dan Volumetrik, perangkat lunak untuk melakukan pembagian menggunakan skema paling populer
Metode Subdivisi Permukaan di CGAL, Perpustakaan Algoritma Geometri Komputasi

[1] "Subdivision Surfaces". nevercenter.com. Diakses tanggal 19 January 2021.

[2] Blender: Reduce Polygons – Simply Explained

[PetersBook-3] J. Peters and U. Reif: Subdivision Surfaces, Springer series Geometry and Computing monograph 3, 2008, doi

[PetersAnalysis-4] J. Peters and U. Reif: Analysis of generalized B-spline subdivision algorithms, SIAM J of Numer. Anal. 32 (2) 1998, p.728-748

[5] "Chaikin Curves in Processing".

[Karciauskas-6] K. Karciauskas and J. Peters: Point-augmented biquadratic C¹ subdivision surfaces, Graphical Models, 77, p.18-26

[7] Joy, Ken (1996–2000). "DOO-SABIN SURFACES" (PDF). On-Line Geometric Modeling Notes.

[Peters-8] J. Peters and U. Reif: The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics 16(4) (October 1997) p.420-431, doi

[Habib-9] A. Habib and J. Warren: Edge and vertex insertion for a class of C¹ subdivision surfaces, Computer Aided Geometric Design 16(4) (May 1999) p.223-247, doi

[Kobbelt-10] L. Kobbelt: √3-subdivision, 27th annual conference on Computer graphics and interactive techniques, doi

[11] Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991), 89–96.

[12] Halstead, M., Kass, M., and DeRose, T. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph

[13] Zorin, Denis; Schröder, Peter; Sweldens, Wim (1996). "Interpolating Subdivision for Meshes with Arbitrary Topology" (PDF). Department of Computer Science, California Institute of Technology, Pasadena, CA 91125.

[Reif-14] Ulrich Reif. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design. 12(2)153–174

[Stam-15] Jos Stam, "Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values", Proceedings of SIGGRAPH'98. In Computer Graphics Proceedings, ACM SIGGRAPH, 1998, 395–404

[1]