6 PenyaiianParametrik

6 6.1

PenyaiianParametrik dan Praktis Penyajian parametrik benda padat tiga-dimensi Meskipun representasi data telab diulas dalam Bab 2, penyajian parametrik memerlukan pemikiran yang lebih rinei; bab ini dipersembahkan seluruhnya untuk bentuk penyajian ini. Penyajian parametrik benda padat dan kurva kini merupakan alat yang ditetapkan dalam grafik komputer, khususnya dalam rancangan yang dibantu komputer (computer-aided design, CAD). Teknik yang aslinya dikembangkan untuk memodel badan mobil dan bentuk pesawat terbang kini banyak digunakan dalam banyak cabang yang bermacam-macam pada grafik komputer. Sebagai contoh, teknik yang digunakan dalam pemodelan obyek dan rancangan interaktif selanjutnya dan dalam bingkai-kunei animasi. Salah satu formulasi parametrik yang paling terkenal adalab lekatan Bezier yang dikembangkan dalam tabun 1960-an oleh Pierre Bezier yang digunakan dalam rancangan badan mobil Renault. Sistam CAD-nya, UNISURF, digunakan pada tabun 1972,tanpa ragu bertanggungjawab untuk banyak model yang bermacam-macam yang muncul dari pabrik Renault dalam tahun 1970-an. Kenyataannya pekerjaan Bezier telah didahului oleh P. de Casteljau pada Citroen dalam awal tabun 1960-an. Akan tetapi laporan internal tidak ditemukan hingga tabun 1975. Pada saat ini kita bisa jadi tidak merujuk lekatan Casteljau, akan tetapi namanya tidak ada yang kurang kenaI dalam sebuah algoritma yang digunakan secara luas untuk merancang dan menampilkan kurva dan permukaan. Pendekatan biasa dalam memperhatikan penyajian parametrik adalah mulai dengan uraian kurva tiga-dimensi dan kemudian untuk mensama-ratakan permukaan. Kita akan mengambil kecenderungan ini, dengan memusatkan perhatian 221

222

Pengantar Komputer Grajik

pada rumusan B6zier dan B-spline. Watak kurva dan notasi yang berhubungan jauh kurang praktis daripada untuk permukaan, dan kita akan memperlajari secara rinci wa~k kurva kita dalam pengetahuan bahwa semua sifat kurva meluas sampai pada permukaan. Sebagai tambahan, kurva yang digunakan dalam gnifik komputer menjadi hak milik mereka. Kita dapat 'menulis' lintasan suatu obyek melalui titik yang telah ditentukan dalam tiga-ruang dengan menginterpolasi sebuah kurva parametrik melalui titik ini. Juga, kita dapat menentukan atau memodel sebuah pipa padat dengan sapuan potongan melintang yang tetap atau berubah-ubah sepanjang kurva tersebut. Dalam setengah bab berikutnya algoritma de Casteljau digunakan untuk menampilkan kurva B6zier dan teknik rendering yang berbeda digunakan untuk memvisualisasikan permukaan yang didefinisikan secara parametrik telah dibahas.

6.1.1

Ulasan mengenai kurva parametrik Sebagaimana akan kita lihat, sebuah kurva parametrik didefinisikan oleh sebuah himpunan titik diskret yang dikenal sebagai titik kendaH atau puncak kendaH, bersama-sama dengan sebuah himpunan fungsi dasar atau campuran. Ini benar-benar berbeda dengan cara yang normal untuk menentukan sebuah kurva dalam bentuk sebuah fungsi yang lengkap. Gagasan tersebut didemonstrasikan dalam Gambar 6.1. Empat titik kendali Po sampai P3 disediakan kepada sebuah algoritma yang menghasilkan kurva tersebut. Catat bahwa dalam kasus ini kurva melewati dua titik tersebut. Ada sebauh fungsi dasar yang ditentukan pada jangkauan parameter u untuk masing-masing titik kendali dan sebuah kurva Q(u) dibentuk dengan menggunakan titik kendali untuk menskala fungsi dasar. Dalam Gambar 6.1 fungsi dasar tersebut merupakan fungsi B6zier. Jadi 3 x(u)

= j=O L

PxiBi(u)

yang menentukan bahwa kita menurunkan komponen x dari Q(u) dengan menjumlahkan komponen x pada masing-masing titik kendali yang diskala oleh nilai fungsi dasar pada u. Hal yang sarna: 3 y(u)

= i=O L P,ojBj(u) .

Penyajian Parametrik dan Praktis

223

dan: 3

z(u) =

2:Pz;B;(u)

;=0

atau lebih tepatnya: 3 Q(u)

= ;=0 2: P;B;(u)

Fungsi dasar yang digunakan untuk menskala atau mencampur titik kendali menjadi sebuah segmen kurva dapat berupa sembarang dari sejumlah fungsi dasar yang berbeda yang dikembangkan dalam CAD dan grafik komputer. Fungsi dasar yang berbeda memiliki sifat yang berbeda; secara prinsip apakah mereka menginterpolasi titik kendali atau memperkirakan mereka. Karakteristik pembeda utama yang lain adalah sifat kontinuitas kurva dan parameter yang digunakan untuk mengendalikan bentuk sebuah kurva melalui sebuah antarmuka interaktif. Dalam bab ini kita memusatkan perhatian pada fungsi dasar Bezier dan B-spline. Kurva Bezier terkenal karena kesederhanaan mereka dan karena obyek dapat dirender dengan mudah jika mereka dinyatakan dengan lekatan Bezier. Kurva Bezier memiliki kerugian tertentu yang dapat diatasi dengan menggunakan B-splines. ~ ~

P,.

~ ~

~

P;

Gambar 6.1 Sebuah kurva yang ditentukan oleh empat titik kendali. Dalam kasus ini kurva tersebut adalah sebuah kubus Bezier.

224

Pengantar Komputer Grafik

Spesifikasi sebuah segmen kurva (atau lekatan permukaan) oleh sebuah himpunan titik kendali merupakan dasar dari sebuah metode rancangan interaktif dalam CAD. Sebuah himpunan titik atau poligon ditentukan secara interaktif oleh seorang perancang. Sebuah kurva disusun dari titik ini dan dipandang. Jika tidak memuaskan sebuah himpunan titik yang baru ditentukan dan seterusnya. Kita membedakan antara sebuah kurva dan sebuah segmen kurva. Secara umum sebuah kurvadibuat dari sejumlahsegmenkurvayang digabungkanbersamasarna dengan beberapa kekangan yang berkelanjutan. Masing-masing segmen kurva ditentukan oleh empat titik kendali. Kita mendefinisikan "convex hull" dari titik kendali sebagai berikut. Jika kita memperhatikan semua titik kendali sebagai sebuah himpunan titik, maka "convex hull" dari titik ini (dalam sebuah bidang) dapat dianggap sebagai daerah yang direntangkan oleh pita karet mengelilingi titik kendali tersebut (Gambar 6.2). Catat bahwa "convex hull" tidak sarna dengan poligon yang dibentuk dengan penggabungan titik kendali yang berurutan. "Convex hull" pentingdalarnkonteksrendering. Sebagai contoh, dalam pelacakan sinar lekatan permukaan, "convex hull" dapat digunakan sebagai volume batas. Di dalam grafik komputer, kurva kubus cenderung digunakan. Ini karena mereka menunjukkan bentuk yang cukup tleksibel untuk kebanyakan aplikasi praktis dan karena semakin tinggi tingkat kurva akan menghasilkan tingkat biaya yang lebih tinggi dan kesulitan yang lain. Juga, polinomial kubus benar-benar merupakan kurva ruang - mereka bukan planar. Kurva kuadratik adalah fungsi dari tiga titik kendali dan dalam tiga-ruang dibatasi pada sebuah bidang. Sebuah kurva yang dibuat dari segmen kuadratik hanya dapat berupa sebuah himpunan potongan dari segmen dua-dimensi. Ini hampir dapat dipastikan tidak akan memenuhi syarat bila segmen ini digunakan untuk memodel bentuk tiga-dimensi. Jadi dalam bab ini kita memusatkan perhatian pada definisi polinomial kubus. Segmen kurva menampilkan sifat-sifat kontinuitas. Bila sebuah kurva gabungan yang dibuat dari segmen kurva sifat ini dapat berubah tergantung pada bagaimana segmen tersebut digabungkan. Dengan hanya menggabungkan dua segmen bersama~samapada sebuah titik bersama yang secara tidak langsung menyatakan kontinuitas geometrik GO.Jika vektor tangen terhadap masing-masing segmen kurva pada titik ujung bersama cocok dengan sebuah tetapan (arah sarna, magnitudo tidak sarna) maka kurva tersebut memiliki kontinuitas geometrik G1. Jika vektor tangen cocok, maka kurva tersebut menunjukkan kontinuitas tingkat pertama atau CI. Vektor tangen terhadap sebuah kurva diperlihatkan dalam Gambar 6.5. Secara umum, parameter kontinuitas Cn didefinisikan sebagai berikut. Jika


225

Gambar 6.2 Properti lensa cembung untuk lempengan kubik. Kurvanya berada dalam area yang terlindung dibentuk dari titik control.

arah dan magnitudo d"/d/'[Q(u)] sarna pada titik pertemuan antara segmen kemudian kurva tersebut menunjukkan kontinuitas Ct!.

6.2

Penyajian parametrik kurva tiga-dimensi Kini kita akan melihat secara rinci pada penurunan fungsi dasar definisi kurva yang dibahas dalam Bagian 6.1. Sebuah contoh praktis yang sederhana dari sebuah kurva ruang tiga-dimensi adalah sebuah titik yang bergerak dalam ruang (Gambar 6.3). Posisinya ditentukan oleh vektor r, yang merupakan fungsi dari waktu t. Ini memberikan deskripsi parameter dari suatu kurva sebagai sebuah himpunan yang terdiri dari tiga persamaan dalam t: x

=x(t)

y

=y(t)

z = z(t)

226


z

x

Gambar 6.3 Sebuah titik yang bergerak dalam ruang tiga-dimensi.

Dengan mengikuti ini kita dapat menguraikan sembarang kurva ruang secara parameter, dengan menggunakan sembarang parameter u, misalnya, dan sebuah kurva kubus diberikan oleh: x(u) y(u) z(u)

= axu3

'+ bxu2 + cxu + dx

= ayu3 +

= a:u3

byu2 + Cyu + dy + b:u~ + C:u + d:

(6.1)

dimana 0 :::;u :::;1, dan masing-masing x, y, dan z adalah sebuah polinomial kubus

dari parameter u. . Ada sejumlah alasan untuk menggunakan uraian parametrik dalam grafik komputer daripada fungsi implisit. (Sebuah fungsi implisit adalah f (x,y,z) = 0, misalnya, uraian fungsi implisit dari sebuah bola adalah x2 + l + i - r2 = 0.) Pertama, titik pada sebuah kurva dapat dihitung secara berurutan, daripadadengan dengan menyelesaikan persamaan bukan-linear untuk masing-masing titik dalam sebuah definisi implisit.Kurva (dan permukaan)parametrik mudah ditransformasikan. Dengan menggunakan sebuah transformasi linear terhadap penyajian parametrik suatu kurva mentransformasikan kurva itu sendiri. Kebanyakan pemakaian rancangan melibatkan kurva (dan/atau pemukaan kompleks) yang tidak dapat diuraikan dengan fungsi yang sederhana, sedangkan sebuah penyajian parametrik memungkinkan uraian potongan dan sebuah kurva atau sebuah permukaan dapat berupa sebuah himpunan yang terdiri dari polinomial potongan. (Polinomial derajad tinggi dapat menguraikan kurva kompleks akan tetapi memerlukan se-


227

jumlah besar koefisien dan bisa menimbulkan osilasi yang tidak diinginkan ke dalam kurva tersebut.)

6.2.1

Kurvakubus Bezier Kini kita melihat pada sebuah bentuk khusus dari penyajian parametrik: kurva kubus Bezier. Rumusan Bezzier pada sebuah kurva kubus melibatkan penentuan sebuah himpunan titik kendali dari mana polinomial kubus tersebut diturunkan. Bentuk ini diturunkan, dalam kebanyakan buku, berawal dengan pencampuran atau fungsi dasar (lihat di bawah ini). Foley dan kawan-kawan (1989) memberikan sebuah penurunan yang luas yang memperlihatkan hubungan antara rumusan Bezier dan kubus Hermite atau Ferguson. Dengan menuliskan kembali Persamaan (6.1) sebagai sebuah persamaan vektor tunggal memberikan:

dan ini adalah cara normal untuk menyatakan sebuah parameter polinomial kubus. Dengan menggunakan basis Bezier atau fungsi campuran Bernstein (ini dibahas sepenuhnya di bawah ini): (1 - u)3 3u (1 - u)~ 3u2(1

-

u)

u3

polinomial tersebut dinyatakan dalam suku-suku fungsi ini dan empat titik kendali:

atau dalam notasi matriks: Q(u) = UBP

-1 Ll 1][ _~

3 -6 3 o

-3 3 o o

228


Dari titik pandang intuisi rumusan matriks tersebut secara khusus tidak berguna, definisi fungsi campuran, yang diberikan di bawah, lebih disukai; akan tetapi sebuah rumusan matriks berguna bila memperhatikan implementasi perangkatkeras. Po,PI, P2,dan P3 adalah empat titik kendali yang menentukan kurva, Po dan P3 menjadi titik ujung. Mereka disebut titik kendali karena menggerakkan mereka berkeliling dalam ruang yang mengendalikan atau mempengaruhi bentuk kurva tersebut. Poligon yang dibentuk dengan menggabungkan titik kendali bersarnasarna disebut poligon karakteristik atau poligon kendali. Gambar 6.1 memperlihatkan sebuah kurva dan poligon karakteristiknya. Bentuk B6zier merupakan sebuah rumusan kembali dari sebuah bentuk poIinomial kubus Hermite. la memungkinkan bentuk kurva ditentukan secara keseluruhan dari posisi empattitik kendali.Secarakhusus,pemakaitidakhams menentukan atau mengendalikan vektor tangen, atau turunan pertama, yang diperlukan untuk spesifikasi Hermit. Sebuah penyajian geometrik mengenai cara kerja titik kendali adalah sebagai berikut. Ini dapat diabaikan dengan mudah jika anda hanya tertarik dalarn penggunaanpraktis dari segmenB6zier. Dengan menurunkanfungsi dasar terhadap u dapat diperlihatkanbahwa: Q,,(O) = 3(PI Q,,(1) = 3(Pz

-

Pu) P3)

Ini adalah vektor tangen terhadap kurva pada titik ujung dan ia dapat diilihat bahwa PI dan P2terletak pada vektor ini. Dengan penggantian empat titik kendali akan memungkinkan posisi dan bentuk kurva tersebut dikendalikan begitu mereka secara efektif mengubah titik ujung dan dua nilai nilai vektor tangen. Gambar 6.4 mencoba untuk memperlihatkan cara titik kendali mempengaruhi bentuk kurva dan Gambar 6.5 memperlihatkan sebuah kurva dan vektor tangennya. Dengan menuliskan sebuah program interaktif yang pendek dan mencoba posisi titik kendali akan memberikan apresiasi intuisi interpretasi geometrik ini. Secara khusus anda akan melihat bahwa pertengahan dua titik kendali tarnpak melakukan tarikan pada kurva tersebut. Katakan, misalnya, kita memerlukan sebuah metode rancangan yang menghasilkankembali bentuk bentuk kurva sederhana yang digambar dengan tangan. Kita dapat melakukannya sebagai berikut: (1) Perkirakan bentuk kurva dengan membentuk sebuah poligon kendali.


P: ~\-......... \

...................

\\

' \ \ , ',

..................... ....-.... ..................

---'... --~- P. .........-

\ ' ',

TI

'' ,\ \

II I

' \

III I

' ' ,, \, p"

Gambar 6.4 Pengaruh gerakan titik kendaHPI.

(2) Gunakan ini untuk menggambarkan kurva Bezier yang dihubungkan. (3) Atur titik kendali. (4) Ulangi 2 dan 3 hingga bentuknya dipenuhi. Q.IIt,

= 31 P; - Po,)

P"

Q) I) = 31P,

Gambar 6.5 Hubungan antara titik kendali Bezier dan vektor tangen.

- P;)

229

230


Kini kita kembali kepada fungsi dasar atau fungsi campuran yang dibahas pada awal bab ini. Empat fungsi dasar diperlihatkan dalam Gambar 6.6 dan untuk interpretasi ini kurva ditentukan oleh: 3 Q(u)

= i=O 2: Pi Bi.3(lI)

dimana masing-masing suku dalam penjumlahan tersebut adalah perkalian dari sebuah titik kendali Pi dan sebuah fungsi campuran Bi,3yang mana dalam kasus ini adalah sebuah polinomial derajad tiga. Kurva ini memperlihatkan pengaruh bahwa masing-masing titik kendali berada pada bentuk kurva akhir. Untuk sebuah nilai u yang tertentu kita menjumlahkan nilai yang diperoleh dari masingmasing empat fungsi campuran terse but. Po paling berpengaruh u = 0 (B] 1,3,B2,3, dan B3,3 semuanya nol pada titik ini). Begitu u dinaikkan menuju PI, Bo dan B] sangat menentukan bentuk kurva tersebut, dengan B2.3dan B3,3memiliki beberapa pengaruh. Titik kendali p] dan P2 sangat berpengaruh masing-masing bila u = 1/3 dan 2/3. Catat bahwa gerakan sembarang titik kendali akan mempengaruhi, lebih besar atau lebih sedikit, bentuk semua bagian pada kurva tersebut. Ini merupakan kerugian dari kurva Bezier - kendali adalah global. Masalah penting yang lain

adalah bahwa penyajian parametrik memungkinkan kurva yang bernilai jamak. Sebagai contoh, jika Po = P3 maka kurva yang dihasilkan akan berupa sebuah kalang tertutup. Himpunan fungsi dasar atau campuran diberikan untuk polinomial kubus: BO.3(u)

= (1 -

u)3

= 3u(1 -

BU(lI) B2.3(U)

= 3u2(1 -

B3,3(U)

= u3

u)2

u)

adalah sebuah kasus khusus dari fungsi dasar sembarang derajad n, dimana: n Q( u) = 2: PiB i.n(1I) i=O

dan:


231

u_ Gambar 6.6 Fungsi dasar Bezier kubus.

dan C(n,i) adalah koefisien binomial: C(n,i) = n!/U!( n

-

i)!)

Catat bahwa secara umum ini meningkatkan jumlah titik kendali menjadi n+1. Akan tetapi, masalah yang berhubungan dengan peningkatanjumlah titik kendali dengan meningkatkan derajad fungsi campuran, dan kesulitan ini merupakan salah satu alasan untuk lebih menyukai B-splines. Pasa saat ini berguna untuk memikirkan semua percabangan dari penyajian sebuah kurva dengan titik kendali. Sifat yang paling penting, sejauh yang diperhatikan mengenai interaksi, adalah bahwa gerakan titik kendali memberikan perubahan intusisi dalam bentuk kurva. Cara yang lain adalah dengan mengatakan bahwa kurva tersebut meniru bentuk poligon kendali. Sifat penting dari segi algoritma yang berhubungan dengan kurva (dan permukaan) adalah bahwa sebuah kurva selalu tertutup dalam "convex hull" yang dibentuk oleh poligon kendali. Ini mengikuti kenyataan bahwa fungsi dasar menjumlah menjadi satu untuk semua u. Dengan memperhatikan transformasi, karena kurva tersebut didefinisikan sebagai kombinasi linear dari titik kendali, maka kurva tersebut ditransformasikan oleh sembarang transformasi yang berhubungan dekat (rotasi, penyekalaan, translasi, dan lain sebagainya) dalam ruang tiga-dimensi dengan menggunakan transformasi yang sesuai terhadap himpunan titik kendali. Jadi

232


untuk mentransformasikan sebuah kurva kita mentransformasikan titik kendali kemudian menghitung titik tersebut pada kurva. Dalam konteks ini catat bahwa tidak mudah untuk mentransformasikan sebuah kurva dengan menghitung titik kemudian mentransformasikan (sebagaimana yang bisa kita lakukan dengan uraian implisit). Sebagai contoh, tidak jelas dalam penyekalaan berapa banyak titik yang diperlukan untuk menjamin kemulusan bila kurva tersebut diperbesar. Gatat di sini bahwa transformsi perspektif adalah "non-affine", dengan demikian kita tidak dapat memetakan titik kendali menuju ruang layar dan menghitung kurva disana. Meskipun kita telah membahas bentuk Bezier kubus, ini hanya merupakan sebuah kasus khusus dari sebuah himpunan kurva polinomial Bernstein-Bezier. kubus sering digunakan karena mereka cukup sederhana, akan tetapi masih cukup tleksibel untuk pekerjaan rancangan interaktif. Keuntungan dari kurva berderajad tinggi berhubungan dengan tingkat kontinuitas yang dapat dicapai antara segmen kurva (Iihat Bagian 6.2.2). Terpisah dari biaya komputasional, semakin tinggi derajad kurva yang digunakan maka hubungan antara poligon karakteristik yang dibentuk oleh titik kendali dan kurva tersebut menjadi semakin lemah.

6.2.2

Penggabungan segmen kurvaBezier Segmen kurva didetinisikan oleh sebuah himpunan yang terdiri dari empat titik kendali dapat digabungkan untuk membuat kurva yang lebi~ kompleks daripada yang dapat diperoleh dari bentuk polinomial kubus. Ini m.enghasilkan sebuah potongan kurva polinomial. Metode alternatif dari penyajian kurva yang lebih rumit untuk meningkatkan tingkat dari polinomial tersebut, akan tetapi memiliki kerugian komputasi dan kerugian matematika dan secara umum dianggap lebih mudah membagi kurva tersebut menjadipotongankubus. Dengan menghubungkan segmen kurva yang secara tidak langsung menyatakan bahwa kekangan harns diterapkan pada sambungan. Kekangan default adalah GO.Perbedaan antara kontinuitas GOdan G1 untuk sebuah kurva Bezier diperlihatkan dalam Gambar 6.7 dan Gambar 6.8. Kontinuitas GOberarti bahwa titik ujung pada segmen yang pertama berimpit dengan titik awal dari yang kedua. Kontinuitas G1berarti bahwa edge poligon karakteristik adalah "collinear" seperti yang diperlihatkan dalam Gambar tersebut. Ini berarti bahwa vektor tangen pada ujung salah satu kurva dan awal dari yang lain cocok dalam sebuah tetapan. Pada permukaan yang terbayang,


Q1 ~

233

~ ~ I

,,

R,

II

I I I I I I

,I I

/ // //

r--

I./

Q.1= RIO

//

/I. / / ,,

,, ,, " ,,

,,

,, \I

.

R:

Gambar 6.7 Kontinuitas posisi antara kurva Bezier.

dengan hanya mempertahankan kontinuitas GOmungkin akan menghasilkan sambung an yang dapat dilihat dalam obyek akhir yang dirender. Jika titik kendali pad a dua segmen adalah Qi dan Rj maka kontinuitas G1 dipertahankan jika:

Dengan menggunakana syarat ini, kurva Bezier komposit dapat dibuat dengan mudah dengan menambahkan sebuah segmen tunggal setiap saat. Akan tetapi, keuntungan mengenai kemampuan untuk membuat sebuah bentuk komposit dari segmen agak diabaikan oleh kekangan pada kendali lokal yang kini digunakan

r

Q,

I I

I

I I I I I I I I

"""'~:

~

....

, ....

~

Gambar 6.8 Kontinuitas tangensial antara kurva Bezier.

234

Pengantar Komputer Graftk

karena syarat gabungan. Ini hanya dapat dikurangi dengan meningkatkan derajad polin~mial atau dengan pembagian sebuah segmen menjadi dua segmen atau lebih yang lebih keeil.

6.2.3

KesimpulansifatkurvaBezier

.

. .

.

Derajad polinomial selalu kurang satu dari jumlah titik kendali. Dalam grafik komputer umumnya kita menggunakan derajad tiga. Kurva tersebut "mengikuti" bentuk poligon titik kendali dan dibatasi dalam "convex hull" yang dibentuk oleh titik kendali. Titik kendali tidak menggunakan kendali "Iokal". Dengan menggerakkan sembarang titik kendali mempengaruhi semua kurva menjadi lebih besar atau lebih keeil. Ini dapat dilihat dengan menguji Gambar 6.6, yang memperlihatkan bahwa semua fungsi basis dimana saja bukan-nol keeuali pada titik u = 0 dan titik u = 1. Titik kendali yang pertama dan terakhir adalah titik ujung dari segmen kurva

tersebut.

. . .

6.3

Vektor tangen terhadap kurva tersebut pada titik ujung berimpit dengan dengan edge awal dan akhir dari poligon titik kendali. Kurva tersebut tidak berosilasi mengelilingi sembarang garis lurus lebih sering dari poligon titik kendali ini dikenal sebagai variasi sifat pengurangan. Kurva tesebut ditransformasikan dengan menggunakan sembarang transformasi "affine" (yakni, segala kombinasi transformasi linear) terhadap penyajian titik kendalinya. Kurva tersebut adalah "invariant" (tidak berubah bentuk) pada transformasi ini.

-

Kurva B-spline Dua kerugian yang berhubungan dengan kurva Bezier diatasi dengan menggunakan kurva B-spline adalah ketidak-Iokalan dan hubungan antara derajad kurva dan jumlah titik kendali. Sifat yang pertama - ketidak-Iokalan - seeara tidak langsung menjelaskan bahwa meskipun sebuah titik kendali sangat mempengaruhi bagian kurva yang paling dekat kepadanya, ia juga memiliki beberapa pengaruh pada semua kurva dan ini dapat dilihat dengan pengujian Gambar 6.6. Semua fungsi dasar adalah bukan nol pada seluruh jangkauan nilai u. Kerugian


235

yang kedua berarti bahwa kita tidak dapat menggunakan sebuah kurva kubus Bezier untuk memperkirakan atau menyatakan n titik tanpa ketidak-nyamanan dari penggunaan segmen kurvajamak (atau dengan meningkatkan derajad kurva tersebut). Sebenarnya, "spline" adalah alat bantu bagi seorang juru gambar. Ia berupa sebuah strip metal yang tipis (atau kayu) yang digunakan untuk menggambar kurva melalui titik tetap dengan menambahkan beban pada titik yang disebut "nodes" atau "knots". Kurva yang dihasilkan adalah mulus dan meminimalkan tegangan internal dalam spline tersebut. Matematika yang setara adalah spline polinomial kubus. Seperti sebuah kurva Bezier, sebuah kurva B-spline tidak lewat melalui titik kendali. Sebuah B-spline adalah sebuah potongan lengkap polinomial kubus yang berisi sembarang jumlah segmen kurva. (Untuk kesederhanaan notasi kita hanya akan memperhatikan B-spline kubus. Akan tetapi kita dapat memiliki B-spline sampai sembarang derajad.) Ia adalah sebuah segmen kubus pada interval tertentu, dan pergi dari salah satu interval menuju yang berikutnya, koefisien berubah. Untuk sebuah segmen tuggal saja, kita dapat membandingkan rumusan B-spline dengan rumusan Bezier dengan menggunakan notasi matriks yang sarna. Rumusan B-spline adalah: Q;(u)

= UB.P

-1 3

3 -6

u 1] 6 _~

4

1

[

o

-3 3 3 1

1

o o oJ

[

Pi-3 Pi-2 Pi-1 Pi

l

dimana Qiadalah segmen B-spline yang ke-i dan Pi adalah sebuah himpunan yang terdiri dari empat titik kendali yang berurutan. Sebagai alternatif kita dapat menulis: 3 Qi(U)

= k=1) 2: Pi-3+kBi-3+JJU)

(6.2)

dimana i adalah jumlah segmen dan k adalah indeks titik kendali lokal, yakni, indeks untuk segmen i. Nilai u pada sebuah segmen kurva tunggal adalah 0 ~ u ~ I. Dengan menggunakan notasi ini kita dapat menguraikan u sebagai sebuah

236


-

parameter lokal yang berubahsecara lokal padajangkauanparameterdari 0 sampai 1 untuk mendetinisikan sebuah segmen kurva B-spline. Jadi dengan menggunakan notasi ini kita lihat bahwa kurva B-spline adalah sebuah deret dari m-2 segmen kurva yang secara umum kita beri label Q3,Q4,..., Qmyang didetinisikan atau ditentukan oleh empat titik kenali dan masing-masing titik kendali mempengaruhi empat dan hanya empat segmen kurva. Ini adalah sifat kendali lokal dari kurva B-spline - keuntungan utama dibandingkan dengan kurva Bezier. (Oi sini kita harus hati-hati. Barsky (Bartels, Beatty, dan Barsky, 1988) menunjukkan bahwa membandingkan kurva Bezier dan B-spline adalah menyesatkan karena ia bukan sebuah perbandingan seperti dengan seperti akan tetapi sebuah perbandingan sebuah kurva Bezier segmen-tunggal (yang bisa memiliki himpunan puncak kendali yang diperluas dan derajad kurva dinaikkan) dengan sebuah potongan atau kurva B-spline komposit. Sebuah kurva Bezier segmen-tunggal adalah subyek terhadap kendali global karena gerakan sebuah titik kendali mempengaruhi kurva yang sempuma. Oi dalam sebuah kurva Bspline komposit, gerakan sebuah titik kendali hanya mempengaruhi beberapa segmen kurva. Perbandingan seharusnya antara kurva Bezier dan B-spline segmen-jamak. Perbedaan di sini adalah bahwa untuk mempertahankan kontinuitas antara segmen Bezier gerakan titik kendali harus memenuhi kekangan, sedangkan titik kendali pada B-spline komposit dapat digerakkan sembarang arah.) B-spline menunjukkan posisi, kontinuitas turunan pertama dan turunan kedua (C2) dan ini dicapai karena fungsi basis adalah mereka sendiri C2 polinomial potongan. Sebuah kombinasi linear seperti fungsi dasar juga akan berupa C2yang kontinyu. Kita mendetinisikan seluruh himpunan segmen kurva sebagai satu kurva B-spline dalam u:

-

m

Q(u)

= j=O L PjBj(ll)

Oalam notasi ini kini j adalah sejumlah titik kendali yang bukan-Iokal dan u adalah sebuah parameter global yang dibahas lebih rinei dalam bagian berikutnya.

6.3.1

B-splines seragam Persamaan 6.2 memperlihatkan bahwa masing-masing segmen dalam sebuah kurva B-spline dedetinisikan oleh empat fungsi dasar dan empat puncak kendali.


237

Oleh karena itu ada tiga fungsi dasar lagi dan tiga puncak kendali lagi daripada segmen kurva. Titik hubung pada suatu nilai u antara segmen disebut "knot value" dan B-spline yang seragam berarti bahwa knot-knot berjarak pada interval yang sarna pada parameter u. Gambar 6.9 memperlihatkan sebuah kurva B-spline yang didetinisikan oleh (posisi dari) enam puncak kendali atau titik kendali Poop\, ..., Ps. lajuga memperlihatkan pengaruh perubahan derajad polinomial, dan kurva yang diperlihatkan untuk derajad 2, 3, dan 4. Secara umum kita tertarik pada kubus dan ini adalah sebuah kurva tiga segmen dengan titik ujung sebelah kiri Q3 dekat Po dan titik ujung sebelah kanan Qs dekat Ps. (Jadi kita lihat bahwa sebuah B-spline tidak, secara umum, menginterpolasi titik kendali ujung, tidak seperti sebuah kurva Bezier.) Notasi memberi kita orgainsasi berikut: Q3ditentukan oleh PoP]P2P3yang diskala oleh BoB]B2B3 Q4ditentukan oleh P1P2P3P4yang diskala oleh B]B2B3B4 Qs ditentukan oleh P2P3P4Psyang diskala oleh B2B3B~S Kenyataan bahwa masing-masing segmen kurva yang patungan titik kendali adalah landasan mekanisme dimana kontinuitas C2dipertahankan antara segmen kurva. Gambar 6.10 memperlihatkan pengaruh dari perubahan posisi titik kendali P4. Ini menarik segmen Qs pada arah yang sesuai dan juga mempengaruhi, yang kurang luas, segmen Q4 (yang juga ditentukan oleh P4). Akan tetapi ia tidak mempengaruhi Q3dan gambar ini mendemonstrasikan pentingnya sifat lokal dari

Gambar 6.9 Sebuah kurva B-spline tiga-segmen yang ditentukan oleh enam titik kendali.

238


B-splines. Secara umum, tentu saja, sebuah titik kendali tunggal mempengaruhi empat segmen kurva. Kini kita memperhatikan fungsi dasar yang melandasi yang menentukan kurva. Masing-masing fungsi basis adalah bukan-nol pada empat interval Uyang berurutan (Gambar 6.11). Ini adalah, dalam kenyataan, sebuah kubus yang dirinya tersusun dari empat segmen. B-spline adalah bukan nol pada interval, Ui,Ui+\,Ui+2, Ui+3,Ui+4, dan berpusat pada Ui+2. Kini masing-masing titik diskala oleh sebuah fungsi dasar tunggal, dan jika kita menganggap bahwa nilai "knot" kita berjarak sarna, maka masing-masing fungsi basis adalah sebuah salinan atau translasi dan himpunan fungsi dasar yang digunakan oleh kurva dalam Gambar 6.9diperlihatkan dalam Gambar 6.12. Dalam kasus ini fungsi dasar menjumlah menjadi satu dalam jangkauan U= 3 sampai U= 6, nilai dari parameter Udimana kurva tersebut ditentukan. Sebagai akibat dari hal ini adalah bahwa seluruh kurva B-spline terdapat didalam "convex hull" titik kendalinya. Jika kita memperhatikan sebuah segmen tunggal di dalam kurva kemudian ini menentukan sebuah jangkauan parameter Ui sampai Ui+l. Fungsi dasar yang aktif didalam interval parameter yang ke-i, Uisampai Ui+l, yakni, fungsi yang menentukan sebuah segmen kurva tunggal, yang diperlihatkan tebal dalam Gambar 6.13. Ini memberikan sebuah pernyataan yang berguna mengenai watak dari fungsi tersebut begitu Udiubah-ubah. Secara umum, untuk nilai Uyang bukan nilai "knot", empat fungsi dasar aktif dan menjumlah menjadi satu. Pada saat sebuah nilai "knot" U= Uitercapai, salah satu fungsi dasar akan dimatikan dan yang lain dihidupkan. Pada nilai "knot" ada tiga fungsi dasar yang

menjumlahmenjadisatu.

.

Pada tahap ini kita dapat menyimpulkan dan menyatakan bahwa kurva Bspline dibuat dari m-2 segmen yang ditentukan oleh posisi dari m+I fungsi dasar pada m+5 nilai knot. Jadi dalam Gambar 6.9 kita memiliki tiga segmen, enam titik kendali, dan empat fungsi dasar pada sepuluh nilai knot. Kini perhatikan lagi Gambar 6.13. Dalam jangkauan parameter Ui::;U::;Ui+( kita mengevaluasi empat B-splines, Bj, Bi-I, Bi-2,dan Bi-3,dengan menggantikan 0 ::;U::;1 dan menghitung: Bi Bi-I

Bi-2 Bi-3

= 1/6 u3 = 1/6 (-3u3 + 3u2 + 3u = 1/6 (3u3 - 6u2 + 4) = 1/6 (1 - u)3

+ 1)

(6.3)


239

Po,

P;

Gambar 6.10 Pendemonstrasian sifat lokal dari kurva B-spline. Gerakan PI merubah Qs dan Q4 yang agak kurang. Q3 tidak berubah.

Penting untuk dicatat bahwa definisi ini memberikan sebuah segmen tunggal dari masing-masing empat fungsi dasar B-spline pada jangkauan 0 ~ U~ 1. Ia tidak menentukan sebuah fungsi dasar B- spline tunggal yang berisi empat segmen padajangkauan 0 ~ u ~ 4. Kini kita hadir untuk memperhatikan puncak kendali dan catat lagi bahwa kurva tersebut tidak menginterpolasi titik ini. Secara umum, tentu saja, sebuah kurva B-spline tidak menginterpolasikan sembarang titik kendali. Kita dapat membuat sebuah kurva B-spline menginterpolasi titik kendali dengan memperkenalkan puncak jamak. Akan tetapi ini melibatkan rugi kontinuitas sebagai-

8'(1I)""'''-

/

1

/

"I"

u,

/,

II,.,

Gambar 6.11 B-spline kubus seragarn B;(u).

~

I Il,..~

'

Il,.,\ I '... '-_

--

U,..: ..J

240


Parameter ranee of curve

-

Gambar 6.12 Enarn B-splines yang digunakan dalarn penyusunan kurva pada Garnbar 6.9. Mereka semuanya mentranslasikan satu-sarna lain.

mana yang akan kita lihat. Secara intuisi kita dapat memikirkan peningkatan pengaruh dari sebuah titik kendali dengan mengulanginya. Kurva tersebut ditarik ke titik yang diulang. Sebuah segmen dibuat oleh fungsi dasar yang menskalakan titik kendali. Jika sebuah titik kendali diulang ia akan digunakan lebih dari satu kali dalam pengevaluasian sebuah segmen tunggaI. Teknik yang seperti ini dapat digunakan untuk membuat kurva yang menginterpolasi titik kendali perantara dan titik akhir - dimana rugi kontinuitas bisajadi sarna pentingnya. Sebagai contoh, perhatikan Gambar 6.14 dan bandingkan ia dengan Gambar 6.9. Titik kendali yang terakhir dalam contoh pada Gambar 6.9 kini diulangi tiga kali. Ada lima segmen dan Ps digunakan satu kali dalam penentuan Qs, dua kali dalam Q6,dan tiga kali dalam Q7. Kini kurva tersebut memiliki jangkauan 3 :5;u :5;8. Pada u

=8

kurva tersebut berimpit dengan Ps. Gambar 6.15 (a) memperlihatkan pengaruh diperkenalkannya titik kendali perantara jamak. Dalam gambar ini P3 digandakan. P3 hampir diinterpolasikan dan diperkenalkan sebuah segmen tambahan. Kontinuitas berubah dari C2G2

Gambar 6.13 Empat B-splines yang bukan-nol atau aktif untuk segmen kurva yang pertama dalarn Garnbar 6.9.


241

.p-,

.P"

//("~ . ~"

PI

. P:

,/ ' Q"

~/ P;.P;.P; Gambar 6.14 Pendernonstrasian pengaruh titik kendali ujung jarnak. Ps diulangi tiga kali yang rnernaksa kurva tersebut untuk menginterpolasinya.

menjadi C2G1. Gambar 6.15(b) memperlihatkan P3 dibuat menjadi sebuah titik kendali lipat tiga. Saat ini kurva tersebut menginterpolasoi titik kendali dan kurva terse but menjadi sebuah garis lurus pada salah satu sisi dari titik kendali. Kini kontinuitas sederhana menjadi C2GO.

6.3.2

B-splinesyang tidak-seragam B-spline yang tidak seragam adalah sebuah kurva dimana interval parameter antara nilai knot yang berurutan tidak perlu sarna. Ini secara tidak langsung menjelaskan bahwa fungsi campuran tidak lagi mentranslasikan satu sarna lain akan tetapi berubah dari interval ke interval. Bentuk yang paling umum dari B-spline yang tidak-seragam adalah dimana beberapa interval antara nilai knot yang berurutan dikurangi menuju nol dengan menyisipkan knot jarnak. Fasilitas ini digunakan untuk rnenginterpolasikan titik kendali (titik ujung dan titik perantara) dan ia merniliki keuntungan tertentu dibanding rnetode yang digunakan dalam bagian sebelumnya

-

penyisipan titik kendali jarnak. Secara khusus,

sebuah titik kendali dapat diinterpolasi tanpa pengaruh yang terjadi dengan puncak kendali jarnak, katakan, segmen kurva garis-Iurus pada salah satu sisi dari titik kendali. Perhatikan kurva yang dihasilkan dalam Garnbar 6.9. Nilai knot untuk kurva ini adalah u = 3,4,5,6. Kita detinisikan sebuah jangkauan pararnetrik yang ber-

242


(a)

. P"

(b)

.

P.

Gambar 6.15 Pendemonstrasian pengaruh titik kendali perantara jarnak. (a) P3 dilipat-duakan. (b) P3 dilipat-tigakan.

guna (dalam mana fungsi dasar menjumlah menjadi satu) sebagai 3 ~ u ~ 6. Interval antara masing-masing nilai knot adalah 1. Jika digunakan nilai knot yang tidak seragam, maka fungsi dasar tidak lagi sarna untuk masing-masing interval parameter, akan tetapi berubah-ubah padajangkauan u. Perhatikan Gambar 6.16. Ini menggunakan titik kendali yang sarna seperti Gambar 6.9 dan kurva B-spline masih dibuat dari tiga segmen. Akan tetapi, kini kurva tersebut menginterpolasi titik ujung karena knot jamak disisipkan pada masing-masing ujung vektor knot. Vektor knot yang digunakan adalah [0,0,0,0,1,2,3,3,3,3].Fungsi dasar juga diperlihatkan dalam Gambar tersebut. Kini kurva tersebut memiliki sembilan segmen, Qo sampai Qs. Akan tetapi, Qo,QJ, dan Q2disederhanakan menjadi sebuah titik tunggal. Q3, Q4, dan Q5 ditentukan pada jangkauan 0 ~ u ~ 3. Q6, Q7, dan Qs disederhanakan menjadi sebuah titik tunggal u = 3. Sebuah contoh yang kedua


243

P,

u_ Gambar 6.16 B-spline tidak-linear yang menginterpolasikan titik ujung dengan menggunakan sebuah vektor knot [0,0,0,0,1,2,3,3,3,3].

memperlihatkan fleksibilitassebuah kurva B- spline yang diberikan dalam Gambar 6.17. Di sini kita memiliki sembilan titik kendali dan tigabelas knot. Vektor knot tersebut adalah [0,0,0,0,1,2,3,4,5,6,6,6,6]. Secara urnurn, sebuah vektor knot adalah sembarang urutan nilai knot yang tidak-berkurang Uosampai Um+4. Sebagaimana yang kita lihat, nilai knot yang berurutan dapat sarna dan jumlah nilai yang identik disebut "multiciplity" knot tersebut. Yang menyebabkan sebuah kurva untuk menginterpolasi titik ujung dengan menggunakan puncak kendali jamak yang tidak memiliki pengaruh yang tepat sarna seperti menggunakan puncak kendali jarnak, dan Gambar 6.18 memperlihatkan titik kendali terakhir Ps dalam contoh standar kita diinterpolasi dengan menggunakan sebuah titik kendali dan sebuah vektor knot dengan "multiplicity" 4 pada nilai knot yang terakhir. Jika kita menggunakan vektor knot [0,0,0,0, 1,1,1,1] maka kita memiliki kurva segmen tunggal yang menginterpolasi Po dan P3. Dalam contoh ini fungsi dasar adalah fungsi dasar Bezier (Gambar 6.6) dan kurva yang dihasilkan adalah sebuah kurva Bezier. Jadi kita lihat bahwa sebuah kurva Bezier hanya merupakan kasus khusus dari sebuah B-spline yang tidak-seragam.

244


Pengaruh dari sebuah knot jamak pada bentuk ,sebuah fungsi dasar terlihat dengan mudah. Perhatikan Gambar 6.19. Bagian (a) memperlihatkan fungsi dasar B-spline yang ditentukan pada knot 0,1,2,3,4. Sebagaimana yang dijelaskan dalam bagian sebelumnya, ini ia sendiri dibuat dari segmen polinomial kubus yang ditentukan pada jangkauan nilai yang ditentukan. Ini dihasilkan dengan menggunakan Persamaan 6.3 dan mentranslasikan masing-masing segmen kubus dengan 0, 1,2,3, dan 4 satuan dalam u. Altematifnya kita dapat menggunakan: b_O(U) = 1/6 u3 Bo(u) = b_1(u) = -1/6(3u3 - 12u2 + 12u - 4) b_2(u) = 1/6(3u3 24u2 + 60u - 44) { b_3(u) = -1/6(u3 - 12u2 + 48u - 64)

-

0 ~ U~ 1

1~ u ~ 2 u~ 3 3~ u ~ 4 2.~

Bandingkan dengan Persamaan 6.3 catat bahwa ini menentukan sebuah fungsi dasar B-spline tunggal pada jangkauan 0 ~ u ~ 4. Jika kita menggandakan knot yang kedua dan menggunakan [0,1,1,2,3], b_1(u)menyusut menjadi panjang nol dan fungsi tersebut menjadi tidak simetris seperti yang diperlihatkan dalam Gambar 6.19(b). Knot ganda menghilangkan kontinuitas turunan kedua akan tetapi kontinuitas turunan pertama masih. Pelipat-tigaan knot yang kedua dengan menggunakan vektor knot [0,1,1,1,2] memberikan fungsi simetris yang diperlihatkan pada Gambar 6.19(c) yang kini hanya memiliki kontinuitas posisi. Pelipat-empatan knot ini [0,1,1,1,1] menghasilkan fungsi yang diperlihatkan dalam Gambar 6.19(d) dimana kontinuitas posisi datar dihilangkan. Jika kini kita kembali kepada konteks yang diperlihatkan dalam Gambar 6.16, fungsi basis yang pertama ditentukan pada 0,0,0,0,1 dan tidak simetris dengan tanpa kontinuitas posisi. Yang kedua ditentukan pada sebulihhimpunan nilai knot yang berisi sebuah knot kelipatan-tiga - 0,0,0,1,2. Yang ketiga didefinisikan pada urutan 0,0,1,2,3 dan juga tidak simetris. Dalam kasus ini semua fungsi adalah tidak simetris dan deriganmeringkaskan kita memiliki: Vektor knot

00001 00012 00123 01233 12333 23333

Fungsi dasar Bo Bl B2 B3 B4 B5

Penyajian Parametrik don PrakJis 245

,-... I

--~

:=

\\

\ \ \ \ 4.

Gambar 6.17 Memperlihatkan tleksibilitas kurva B-spline. Vektor knot adalah [0,0,0,0,1,2,3,4,5, 6,6,6,6].

246


Gambar 6.18 Pembandingan knotjamak dengan titik kendali. (a) Kurva tersebut dihasilkan oleh sebuah vektor knot dengan multiplicity 4 pada nilai awal dan akhir. (b) PS diulang tiga kali.

Selanjutnya kita dapat melihat dari himpunan fungsi dasar ini bahwa mereka menjumlah menjadi 1 pada seluruh jangkauan nilai u dan bahwa pada u = 0 dan u = 3 fungsi dasar bukan-nol hanya Bo dan Bs (keduanya satu) yang menyebabkan titik ujung masing-masing diinterpolasi oleh Q3dan Qs. Kini kita perhatikan perubahan "multiplicity" knot bagi knot interior dimana masalah mengenai perubahan kontinuitas menjadi tampak. Perhatikan contoh yang diperlihatkan dalam Gambar 6.20. Ini adalah contoh yang sarna seperti yang kita gunakan dalam Gambar 6.9 kecuali bahwa sebuah titik tambahan ditambahkan untuk memberi kita kurva dengan empat segmen. Vektor knot tersebut adalah [0,1,2,3,4,4,5,6,7,8,9,10] dan Gambar 6.20(a) memperlihatkan kurva tersebut. Gambar 6.20(b) memperlihatkan pengaruh diperkenalkannya knot ganda dengan menggunakan vektor [0,1,2,3,4,4,5,6,7,8,9]. Jumlah segmen disederhanakan menjadi tiga. Q4menyusut menuju nol. "Convex hull" berisi Q3dan Qs bertemu pada edge P2P3dan titik sambung antara Q3Q4dan Qs dipaksa untuk terletak pada garis ini. Dalam Gambar 6.20(c) sebuah knot kelipatan-tiga diperkenalkan [0,1,2,3,4,4,4,5,6,7,8]. Kurva tersebut disederhanakan menjadi dua segmen. Q4 dan Qs menyusut menuju nol pada P3.Hanya ada kontinuitas posisi antara Q3dan Q6 tetapi segmen tersebut pada salah satu sisi titik kendali P3 melengkung. Ini hendaknya dibandingkan dengan Gambar 6.15, yang diproduksi dengan menggunakan sebuah puncak kendali kelipatan-tiga. Dalam Gambar 6.20(d) diperkenalkan sebuah knot kelipatan-empat - [0,1,2,3,4,4,4,4,5,6,7,8]. Kontinuitas posisi


~ I

T I

247

T--I

~)

I (c)

~, (lI)

Gambar 6.19 Pengaruh multiplicity knot pada sebuah fungsi dasar B-spline kubus tunggal. (a) Semua multiplicity knot adalah satu: [O,I,2,3,4J. (b) Knot yang kedua memiliki multiplicity 2: [0,1,1,2,3]. (c) Knot yang ketiga memiliki multiplicity 3: [0,1,1,1,2]. (d) Knot yang ketiga memiliki multiplicity 4: [0,1,1,1,1].

dihancurkan. Kurva tersebut menyederhanakan menjadi sebuah segmen tunggal. Untuk melihat apakah ini artinya,.kita memperkenalkan titik kendali yang lain sedemikian rupa sehingga segmen yang lain, Q7, kini tampak. Kini ada sebuah celah antara akhir Q3dan awal Q7.Mereka tidak memiliki titik kendali bersama. Kini kita perhatikan sebuah metode rekursif untuk menghasilkan fungsi dasar atau campuran untuk B-splines tidak-seragam. Metode tersebut dikenal sebagai algoritma Cox-deBoor (De Boor, 1972; Cox, 1972), sungguh dapat menghasilkan B-splines yang seragam atau tidak-seragam untuk sembarang tingkat dengan menggunakan sebuah rumus rekursif tunggal. Karena fungsi tersebut tidak lagi mentranslasikan satu sama lain maka komputasi lebih mahal. Untuk sebuah kurva kubus (tingkat keempat) kita dapat menentukan rekursi dalam bentuknya

248


yang terbuka. Dengan memperluas notasi pada B-spline dengan mencantumkan tingkat sebagai subscript yang kedua, kita tentukan fungsi dasar untuk titik kendali pembebanan Pi sebagai Bij(U)dan hubungan yang berulang untuk sebuah B-spline kubus adalah: otherwise

Bila knot diulangi maka dapat terjadi hasil bagi % didalam definisi deBoor dan ini dianggap bemilai noI. Secara komputasional pembilang selalu dicek apakah not dan hasil ditetapkan bemilai nol tidak memperhatikan berapapun nilai penyebut. Pilihan mengenai sebuah knot khusus yang ditetapkan dalam sistemsistem CAD yang menggunakan B-splines biasanya adalah bagian dari sistem yang telah ditentukan sebelumnya.

6.3.3

Kesimpulan mengenai sifat kurva B-Spline Beberapa sifat yang kita daftar untuk kurva Bezier diterapkan pada kurva Bspline. Secara khusus:

· . ·

Kurva tersebut mengikuti bentuk poligon titik kendali dan dikekang agar terletak dalam "convex hull" titik kendali. Kurva tersebut menunjukkan variasi sifat yang berkurang. Kurva tersebut ditransformasikan dengan menggunakan sembarang transformasi "affine" terhadap penyajian titik kendalinya.

Sebagai tambahan B-splines memiliki sifat berikut:


p,

(a)

(a) .Sebuah kurva B-spline empat-seg" men. Knot vektor adalah [0,1,2,3,4,5,6,7, 8,9,10]. Semua B-splines mentranslasikan satu sarna lain.

P,

P;

(h)

P, Q,

P,

(b) Vektor knot adalah [0,1,2,3,4,4,5,6, 7,8,9].Q4 menyusut menjadi no\.

~

3

4

5

6

. Douhlc knot

Gambar 6.20 Pengaruh multiplicity knot interior pada sebuah kurva B-spline.

249

250


(c)

(c) Vektor knot adalah [0,1,2,3,4,4,4, 5,6,7,8J.Q. dan Q5 menyusust menjadi nol. Kontinuitas antara Q3dan Q6adalah posisi.

3

5

oJ

t

Triple knut

p.

P,

:_~-------

P.

(d) Vektor knot adalah [0,1,2,3,4,4,4,4,5, 6,7,8J. Kurva tersebut sederhana menjadi sebuah segmen tunggal Q3. Titik kendali yang lain ditambahkan untuk memperlihatkan bahwa kini kurva tersebut putus antara P3 dan P..

~

3

oJ

+ Quadruph: knul

5

Penyajian Parametrik dan PrakJis 251

. Sebuah kurva B-spline memperlihatkankendali lokal - sebuah titik kendali dihubungkan ke empat segmen (dalam kasus sebuah kubus) dan dengan menggerakkan sebuah titik kendali hanya dapat mempengaruhi segmen ini.

6.4

Permukaan kubus biparametrik Cara memperlakukan parameter segmen kurva kubus diberikan dalam bagianbagian yang lebih dulu mudah disama ratakan dengan parameter ganda lekatan permukaan kubus. Sebuah titik pada lekatan permukaan ditentukan oleh sebuah fungsi parameter ganda dan sebuah himpunan fungsi dasar atau campuran digunakan untuk masing-masing parameter. Sebuah lekatan Bezier didefinisikan sebagai: 3

Q(u, v) =

3

2:2:PijBi(u)Bj(v)

i=O j=O

Secara matematika, permukaan tiga dimensi dikatakan dihasilkan dari perkalian cartesian dari dua kurva. Sebuah lekatan Bezier dan titik kendalinya diperlihatkan dalam Gambar 6.21 dimana lekatan ditampilkan dengan menggunakan garis isoparametrik. Enam-be1astitik kendali dari sebuah poluhedron karakteristik dan ini melahirkan hubungan terhadap bentuk permukaan dengan cara yang sarna poligon karakteristik menghubungkan ke sebuah segmen kurva. Dari Gambar 6.21(a) dapat dilihat secara intuisi bahwa 12 dari titik kendali tersebut berhubungan dengan edge batas dari suatu lekatan (empat dari mereka menentukan titik ujung) dan empet titik interior menentukan bentuk bagian dalam. Hanya puncak sisi saja yang terletak pada permukaan. Sifat dari rumusan kurva Bezier diperluas menjadi kawasan permukaan. Gambar 6.22 memperlihatkan sebuah lekatan yang dibentuk dengan menarik keluar sebuah titik kendali. Perasaan intuisi untuk permukaan yang melalui titik kendalinya, dan kemampuan untuk menjamin kontinuitas tingkat-pertama dipertahankan. Lekatan permukaan ditransformasikan dengan menerapkan transformasi terhadap masing-masing dari titik kendali. Cara titik kendali bekerja dapat dilihat dengan analogi kurva kubus. Penyajian geometrik secara alami lebih sulit daripada untuk kurva, dan tentu saja, tujuan dari rumusan Bezier adalah untuk mengamankan perancang terhadap keharusan

252


memanipulasi vektor tangen dan lain sebagainya, akan tetapi ia dicantumkan sebagai kelengkapan. Spesifikasi matriks tersebut adalah:

P(u, v) = [u' u' u

l][BPBT{~:]

dimana:

-1 B= -33 1

[

3

-6 3

o

-3 3

o o

Ini merupakan perintah untuk menguji hubungan antara titik kendaH dan vektor derivatif pada sisi sebuah lekatan. Sebagai contoh, perhatikan sisi u = v = O.Hubungan antara titik kendali dan vektor yang berhubungan dengan puncak Poo adalah sebagai berikut: Qu(O,O)

= 3(PIO -

Qv(O,O) = 3(POI-

Quv(O,O) = 9(Poo-

Poo) Poo) POI

- PIO + PH)

(6.4)

Gambar 6.23 memperlihatkan vektor ini pada sebuah sisi lekatan. Qu(O,O)adalah sebuah tetapan dikalikan dengan vektor tangen pada Q(O,O)dalam arah parameter u. Hal yang sarna QV(O,O)berhubungan vektor tangen dalam arah parameter v. Derivatif silang pada masing-masing titik ujung, kadang-kadang disebut vektor puntir, menentukan pesat perubahan vektor tangen terhadap u dan v. la adalah sebuah vektor normal terhadap bidang yang berisi vektor tangen. Mirip dengan titik kendali dalam kurva Bezier

-

yang telah kita lihat adalah

sebuah rumusan kembali dari kurva Hermite - jaring yang terdiri dari 16 titik kendali adalah sebuah rumusan kembaH dari lekatan permukaan Hermite yang merupakan lekatan yang ditentukan dalam suku-suku empat titik ujung, delapan


u

I u

/

v__ (a)

Gambar 6.21

t

(b)

(a) Sebuah titik kendali polihedron dan (b) lekatan Bezier bikubus yang dihasilkan.

t

t

Gambar 6.22 Pengaruh pengangkatan salah satu dari titik kendali pada sebuah lekatan B6zier.

254


/

Gambar 6.23 Vektor tangen pada Poo.

vektor tangen (dua pada masing-masing sudut) dan empat vektor puntir. Perhatikan Gambar 6.24 yang memperlihatkan elemen daTipolihedron titik kendali yang terlibat dalam derivatif. Empatpasangtitik menentukanvektor tangen dalam u pada masing-masing sudut (dua baris dalam matriks tersebut), empat pasang menentukan vektor tangen dalam v (dua kolom dalam matriks tersebut) dan 16 elemen semuanya menentukan vektor puntir. Untuk perhitunganbayangankita perlu menghitungnormal permukaan tertentu. Salah satu cara yang paling mudah untuk membayangi sebuah lekatan adalah dengan membagi-baginya sehingga perkalian dari sub-bagian kira-kira planar (teknik ini nanti dibahas sepenuhnyadalam bab ini). Lekatan tersebut dapat diperlakukan sebagai poligon planar dan digunakan bayangan Gouraud atau Phong. Normal puncak dihitung daTi perkalian silang dua vektor tangen pada puncak tersebut. Sebagai contoh: a b

= (POI = (PIO -

Poo)

Poo)

N=axb Sebuah normal dapat dihitung pada sembarang titik pada suatu permukaan dari perkalian silang dua derivatif parsial 8Q/Bu dan 8Q/Bv akan tetapi bayangan sebuah lekatan dengan perhitungan yang lengkap pada titik internal dari uraian parameter adalah perhitungan yang mahal dan merupakan subyek terhadap masalah yang lain (yang diuraikan dibawah). Keuntungan dari penggunaan sebuah parameter uraian lekatan pada sebuah permukaan tidak terdapat dalam kenyataan

Penyajian Parametrik dan PralcJis 255

D

o

D HE

Corn~r points

Tanl!~nt \"~ctors in \' : for ;\ampl~, Q, (0. OJ = 3(P", - P. I

Tanl!~nt \'~ctors in II : for ';:,ample. Q..(O. OJ = 3(PII' - P..,)

Twist

\,cctors:

fnr example,

Quo

(0, OJ

= 9(P,1I- P , - P,,, + P,,)

Gambar 6.24 Elemen matriks titik kendali.

bahwa sebuah koordinat alam yang tepat tersedia bagi setiap titik pada pennukaan

-

-

biaya dari infonnasi ini biasanya terlalu tinggi akan tetapi keuntungannya adalah bahwa penyajian lekatan tersebut harns menawarkan dalam pemodelan

obyek. 6.4.1

'

Penyambungan lekatan permukaan Bezier Penetapan kontinuitas yang melintas dua lekatan adalah perluasan sederhana dari kekangan penyambungan-kurva dan yang terbaik diperhatikan secara geometris. Gambar 6.25 memperlihatkan dua lekatan, Q dan R, patungan sebuah edge bersama. Untuk kontinuitas posisi atau tingkat-nol: Q(1,v)

= R(O,v)

untuk 0 ~ v ~ 1

Penyajian Parametrik don Praktis

257

(a)

Control

point

polyhedra

Patches

(b) Four sets 01three conuolpoiRls must he collinear

Control point polyhedra

Gambar 6.26 (a) Kontinuitas posisi antara lekatan B6zier bikubus dan (b) kontinuitas tangensiaI antara lekatan B6zier bikubus.

258


sebuah lekatan kepada dua lekatan yang telah ada secara tidak langsung menjelaskan bahwa 12 dari titik kendali tersebut tetap. . Syarat penyambungan yang agak kurang tegas dikembangkan oleh B6zier pada tabun 1972 (B6zier, 1972). Dalam lekatan ini, sudut memiliki kontinuitas posisi akan tetapi tidak memiliki kontinuitas gradien. Akan tetapi, vektor tangen pada edge yang bertemu pada sebuah sudut hams berupa coplanar. Meskipun dengan tleksibilitas yang jauh lebih besar ini, masih ada masalah yang berhubungan dengan rancangan permukaan komposit dan salah satu penyelesaian adalah dengan menggunakan lekatan yang tingkatnya lebih tinggi daripada kubus. Hams disebutkan bahwa meskipun cara penanganan yang telah lalu berhubungan dengan lekatan persegi, lekatan persegi tersebut tidak dapat mewakili semua bentuk. Perhatikan, misalnya, sebuah obyek yang berbentuk bola. Lekatan persegi hams diubah menjadi segitiga pada kutub. Lekatan segitiga tidak berubah dengan adanya perubahan tersebut dan merupakan pilihan yang lebih sesuai bagi bentuk kompleks. Farin (1988) menunjukkan bahwa barangkali alasan utama bagi berpengaruhnya lekatan persegi dalam kebanyakan sistem CAD adalah bahwa penggunaan lekatan yang pertama dalam rancanganmobil adalah untuk rancangan panel badan mobil bagian luar. Bagian tersebut memiliki geometri persegi dan secara alami memecah mereka menjadi persegi yang lebih kecil dan menggunakan lekatan yang berbentuk persegi.

6.4.2

LekatanpennukaanB-spline Untuk membentuk sebuah lekatan permukaan B-spline kita perlu mengevaluasi: n

Q(u,v)

m

= ;=0 2: 2: P;jB;,j(u.v) j=O

dimana Pijadalah sebuah larik titik kendali dan Bij(U,v) adalah fungsi dasar yang bervariasi ganda. Kita dapat menghasilkan Bij(U,V)dari: B;,j(u,v) = B;(u)Bj(v) dimana Bi(U)dan Bj(v) adalah B-spline kubus variasi tunggal yang telah didefinisikan sebelumnya. Sebuah fungsi dasar yang dibentuk dengan cara ini disebut "tensor product surface". Jadi kita memiliki:


7

t II

()

7

II I'~

Gambar 6.27 Enam-belas puncak B-splines variasi ganda pada titik yang diperlihatkan dalam ruang parameter.

n

m

Q(u,v) = 2: 2: P;jB;(u)Bj(u) ;=0j=o Mirip dengan kurva B-spline, kita perhatikan sebuah lekatan B-spline yang dibuat dari beberapa segmen lekatan permukaan persegi. Kini kita memiliki dua urutan knot dalam u dan v, yang diambil bersama-sama dari sebuah kisi dalam ruang parameter. Kita perhatikan lekatan B-spline yang seragam dimana kisi dari nilai knot menunjukkan interval yang sama dalam arah parameter u dan v. Pertama, perhatikan sebuah segmen lekatan tunggal. Kita akan menggunakan istilah "segmen lekatan tunggal" yang berarti besaran dalam ruang dua-parameter yang mirip dengan sebuah segmen kurva dalam ruang parameter tunggal. Jadi kita katakan bahwa sebuah lekatan permukaan B-spline dibuat dari beberapa segmen lekatan. Dengan memperluas ke ruang dua-parameter kini kita memerlukan sebuah kisi, Pij, titik kendali 4 x 4 untuk membentuk sebuah segmen lekatan tunggal. Titik kendali ini dicampur dengan fungsi dasar variasi ganda 4 x 4. Ingat dari Gambar 6.12 dan Gambar 6.13 bahwa sebuah segmen B-spline tunggal memerlukan sebuah kisi atau larik knot dari 8 x 8 nilai knot (Gambar 6.27). Puncak fungsi dasar variasi ganda pada nilai knot yang diperlihatkan dengan sebuah persegi.

260


Perhatikan sebuah contoh yang sederhana. Gambar 6.28 memperlihatkan sebuah segmen lekatan yang ditentukan oleh 16 titik kendali. Catat bahwa lekatan tersebut dibatasi pada daerah yang lebih dekat dengan pusat dari empat titik kendali. Sebagaimana kurva B-spline, yang tidak menginterpolasi titik'kendali mereka, sebuah sebmen lekatan B-spline tidak menginterpolasi 4 titik kendali yang berada didalam atau sembarang dari 12yang ada diluar. Kita dapat mengendalikan watak lekatan pada edge titik kendali polihedron dengan menggunakan puncakjamak (sebagaimana kita kendalikan kurva dengan menggunakan titik ujung jamak). Ini didemonstrasikan secara mudah dengan menggunakan sebuah contoh sederhana. Perhatikan Gambar 6.29. Di sini kita memiliki kelipatan tiga himpunan puncak batas yang membentuk sebuah matriks titik kendali yang dibuat dari 24 titik. Ini menyebabkan sebuah lekatan tiga-segmen dibentuk yang ditarik menuju puncak batas. Catat bahwa.tidak satupun dari puncak batas yang sebenarnya diinterpolasi. Dalam contoh yang kedua (Gambar 6.30) kita melipatkan tiga dua himpunan puncak batas, salah satunya yang membentuk sebuah himpunan collinear. Ini

Gambar 6.28

Sebuah segmen lekatan B-spline tunggal.


261

..

Gambar 6.29 Pelipatan-tiga sebuah baris titik kendaIi untuk contoh dalam Gambar 6.28.

menghasilkan sebuah lekatan sembilan-segmen dimana puncak collinear diinterpolasikan. Jika kita melipatkan tiga semua puncak batas maka kita berakhir dengan sebuah permukaan segmen 2S-lekatan yang, secara umum, hanya akan menginterpolasi titik sudut. Penggandaan dan pelipatan tiga titik kendali yang berada didalam dapat digunakan untuk menghasilkan efek pemodelan yang lebih berdaya guna daripada yang tersedia dengan m~nggunakan lekatan Bezier. Gambar 6.31 merupakan sebuah contoh. Titik kendali polihedron adalah seperti dalam contoh sebelumnya kecuali bahwa sebuah titik yang beraoa di dalam diangkat. Sebuah baris dan sebuah kolom dari titik kendali dilipat-tigakan. Oalam kasus kolom, tiga buah puncak kendali adalah collinear dan ini menghasilkan sebuah permukaan dengan lipatan yang diluruskan sepanjang edge yang berhubungan dalam titik kendali polihedron. Kini perhatikan baris yang dilipatkan-tiga. Oi sini titik tidak collinear dan pengaruh lipatan kurang tajam. Yang jelas, pengaruh ini dapat dibuat

262


.. ..

Lincs of constant

u

..

...

.

Linesof constant I'

.. Gambar 6.30 Sebuah lekatan B-spline sembilan-segmen yang dibentuk dengan pelipatan-tiga sebuah baris dan sebuah kolom dari titik kendali.


263

Triplicated row

r~"'liflCd

~

point"

Triplicated column

Gambar 6.31 Pelipatan-tiga titik kendali bagian dalam menghasilkan sebuah lekatan dengan lipatan-lipatan.

264


kedalam sebuah program pemodelan di mana baris dan kolom dilipatkan-tiga dan seluruh edge dari titik kendali polihedron digerakkan secara interaktif untuk menentukan atau menarik sebuah lipatan pada permukaan. Penllukaan yang berisi lipatan adalah biasa, misalnya, dalam badan mobil.

6.5

Rendering permukaan parametrik Algoritma scan mengubah permukaan yang diwakili oleh lekatan parametrik bikubus secara alami dibagi menjadi dua kategori:

. .

yang merender secara langsung dari uraian parametrik, dan yang memperkirakan permukaan dengan sebuah jaring poligon dan menggunakan sebuah pengubah scan poligon planar untuk merender perkiraan ini.

Pasa saat ini pendekatan yang kedua tampak menjadi lebih terkenal. Ia tentu saja lebih mudah diimplementasikan dan secara komputasionallebih murah. Contoh dari yang pertama ditemukan dalam Blinn (1978), Whitted (1978), Schweitzer dan Cobb (1982), dan Griffith (1984). Lane dan kawan-kawan (1980) memberikan sebuah uraian perbandingan mengenai metode ini dan menggambarkan sebuah pengimplementasian pendekatan yang kedua. Pengubahan scan permukaan yang ditentukan secara parametrik sulit karena atribut pada sebuahjaring poligon,yang digunakandalam poligon standarpengubah scan, tidak tersedia dari lekatan yang ditentukansecara parametrik.Atribut tersebut pada sebuah poligonyang membuatpetigubahanscan sederhanaadalah:

. . .

Koordinat Y maksimum dan minimum mudah diperoleh dari daftar puncak. Persamaan yang bertambah dapat digunakan untuk mengikuti masing-masing edge poligon sebagai fungsi Y. Persamaan yang bertambah dapat digunakan untuk menghitung kedalaman layar Z sebagai fungsi X.

Sebuah permukaan yang ditentukan secara parametrik tidak memiliki satupun dari sifat ini. Koordinat Y maksimum dan minimum tidak akan, secara umum, berada pada batas atau edge permukaan dan sebuah lekatan akan sering menampakkan sebuah edge bayangan hitam. Edge bayangan hitam sulit karena mereka tidak perlu edge lekatan yang sebenarnya tetapi, katakan, bagian dari sebuah pusat tonjolan yang mengaburkan sebuah edge yang sebenarnya. Dengan permukaan yang ditentukan secara parametrik edge batas dan edge bayangan hitam


keduanya perlu diikuti. Kerumitan selanjutnya adalah bahwa sebuah edge bayangan hitam dan sebuah edge batas bisa berpotongan. Akhirnya, secara umum, apakah edge batas atau edge bayangan hitam tidak akan sarna dalam X atau Y. Kita ingat bahwa sebuah permukaan yang didetinisikan secara parametrik, ditentukan oleh tiga fungsi variasi ganda: x = X(u,v) y = Y(u,v) z = Z(u,v) dimana u dan v keduanya berubah antara 0 dan 1. Batas pada sebuah lekatan permukaan ditentukan oleh nilai u = 0, u = 1, v = 0 dan v = 1. lni menghasilkan sebuah lekatan bersisi empat. Salah satu cara melihat pengubahan scan didalarn konteks lekatan pararnetrik bikubus adalah bahwa ia ~erupakan sebuah algoritma yang beroperasi pada kurva yang dibentuk oleh perpotongan bidang scan.xz dengan permukaan. Secara umum, kurva tersebut berada antara dua titik batas atau antara sebuah titik batas dan sebuah edge bayangan hitam. Dengan poligon planar kurva ini adalah sebuah garis lurus dan ia hanya perlu menyimpan titik ujung. Dalam kasus permukaan pararnetrik, semua titik pada kurva perpotongan perlu ditentukan. Algoritma Blinn (Blinn, 1978) untuk pararnetrik pengubah scan adalah sebuah pendekatan aljabar yang secara langsung dan melibatkan penyelesaian persamaan (dengan menggunakan teknik iteratif) untuk perpotongan pada kurva batas dan edge bayangan hitarn dengan masing-masing garis scan. Perpotongan pada sebuah garis scan Ys dengan batas pada sebuah lekatan diberikan oleh: Ys = Y(O.v) Ys

= Y(l,v)

Ys

= Y(u,O)

Ys = Y(u,I) Perpotongan edge bayangan hitam diberikan oleh: Ys

= Y(u.v)

o = N:(u,v) dimana Nz adalah komponen z pada normal permukaan terhadap lekatan tersebut. Sebuah edge bayangan hitam dditentukan oleh titik pada permukaan yang menarnpakkan sebuah normal permukaan dengan komponen z nol. Maksimum dan minimum lokal ditentukan dari:

266


Yu(u,v) = 0 Y.,(lI,V) = 0 Titik pada kurva antara titik ini ditentukan oleh: Y(u,v)

X(u,v)

-

-

Ys

Xs

=0

=0

Dengan menyelesaikan persamaan ini menghasilkan sebuah himpunan titik (u,v) dalam ruang parametrik yang dapat digantikan kedalam fungsi X dan Z untuk menghasilkan nilai X dan Z dari edge pada bidang scan yang sedang berlangsung. Prosedur ini diikuti untuk masing-masing lekatan atau permukaan, yang menghasilkan pasangan yang berurutan dari batas yang menyatakan luasan yang dibayangi. Begitu bidang scan bergerak kebawah layar, edge batas dan edge bayangan hitam harus diikuti dan hubungan mereka dipertahankan. Ini bukan merupakan sebuah proses yang mudah dan Blinn memberikan sebuah contoh instruktif dengan menggunakan titik pelana. Pendeteksian sebuah maksimum lokal secara tidak langsung menjelaskan bahwa sebuah kurva perpotongan yang barn ditambahkan terhadap sebuah perpotongan daftar kurva. Kurva dihapus pada Y minimum. Pengarnh dari proses ini adalah untuk membagi-bagi lekatan permukaan menjadi daerah yang berkurang secara monotonic dalam Y dan bernilai tunggal dalam Z. Ini ditunjukkan Lane dan kawan-kawan (1980) bahwa ada banyak masalah dengan pendekatan ini, akan tetapi untuk kebanyakan bentuk algoritma tersebut tegar. Jadi sebagaimana dengan poligon planar pengubah scan, kalang scan bagian luar Y mengikuti edge batas dan edge bayangan hitam dan kalang scan X bagian dalam "mengisi" titik pada kurva perpotongan dalam bidang scan Y. Selanjutnya Blinn memodifikasi proses ini dengan menukar ketelitian dan kecepatan, memperkirakan kurva perpotongan dengan segmen garis lurus. Metode Whitted, Schweitzer, dan Griffith semua adalah variasi dari pendekatan dasar ini.

6.6

Aproksimasi pada lekatan permukaan dengan menggunakan sebuah jaring poligon Dalam Bab 2 kita ulas proses pemisahan lekatan sebagai strategi rendering untuk obyek yang dimodeI dari lekatan parametrik bikubus. Kini kita selidiki proses ini secara lebih rinei.


267

Sebuah jaring poligon planar dihasilkan dengan mudah dari sebuah lekatan permukaan. Lekatan tersebut dapat dibagi dengan menggunakan kurva isoparametrik. (Pemisahan sebuah lekatan menjadi kurva isoparametrik adalah metode utama pada tampilan dalam sistem CAD, yang memungkinkan pemvisualisa'sian sebuah bingkai kawat pada permukaan cukup bagi keperluan sistem yang sedemikian.) Ini menghasilkan sebuah jala atau titik jaring pada perpotongan kurva ini dengan satu sarna lain dan edge batas. Jala dari titik ini dapat digunakan untuk menentukan puncak untuk sebuah jaring poligon planar yang kemudian dapat dirender d~ngan menggunakan sebuah perender poligon planar. Ada dua kekurangan dasar dalam pendekatan yang belum sempurna ini. Edge batas yang dapat dilihat dan edge bayangan hitam dapat menampakkan ketidak-malaran (discontinuities). Secara umum, resolusi poligon yang lebih bagus akan diperlukan untuk mengurangi tarnpaknya potongan linear yang tidak malarpada edge daripada diperlukan untuk mempertahankan bayangan yang mulus dalam lekatan tersebut. Juga edge bayangan hitam internal dalam lekatan tersebut biasanya akan menjadi tingkat yang lebih tinggi daripada kubus. Yang dihubungkan dengan hal ini adalah pertanyaan: sebagus apa seharusnya pembagian isoparametrik itu? Sub-pembagian yang terlalu bagus secara komputasional adalah mahal; terlalu kasar tampak terputus-putus. Sebuah pendekatan yang memungkinkan adalah untuk menghubungkan jumlah pembagian dengan luasan yang diproyeksikan oleh lekatan tersebut pada layar. Sebuah pendekatan yang halus adalah perubahan resolusi. Luasan lekatan tersebut yang rata menjadi subyek bagi beberapa sub-pembagian. Luasan dimana lekukan lokal tinggi merupakan subyek bagi sub-pembagian yang lebih banyak. Secara efektif, lekatan tersebut dibagi-bagi menjadi suatu tingkat yang tergantung pada lekukan lokal. Ini adalah pendekatan yang diterima oleh Lane dan kawankawan (1989). la didemonstrasikan dalarn Garnbar 6.32. Lekatan dibagi-bagi sehingga perkalian dari sub-pembagian tersebut diterima oleh kriteria rata. Kini lekatan yang demikian ini dianggap kira-kira poligon planar dan diubah scan oleh sebuah perender poligon normal dengan menggunakan titik sudut dari lekatan tersebut sebagai puncak untuk persegi dalarnjaring poligon. Himpunan lekatan yang mewakili permukaan dapat diproses terlebih dahulu, yang menghasilkan sebuah himpunan poligon yang kemudian diubah scan sebagai normal. Pendekatan ini diterima oleh Clark (1979). Lane mengintegrasikan pendekatan pemisahan lekatan ini dengan sebuah algoritma pengubah scan.

268


Gambar 6.32

Sub-pembagian sebuah lekatan Bezier yang seragam dan tidak seragam.

Ada dua keuntungan yang cukup berarti bagi pemisahan lekatan: ( 1) ia cepat, dan (2) kecepatan dapat diubah-ubah dengan perubahan kedalaman sub pembagian. Ini penting bagi sistem interaktif. Kerugian dari sub-pembagian yang tidak seragam adalah bahwa lubang dapat tampak antara lekatan yang dimiliki oleh perkiraan pada sebuah batas lekatan oleh sebuah garis lurus. Sebuah contoh dari proses degeneratif ini diperlihatkan dalam Gambar 6.33. Algoritma sub-pembagian yang paling baik dipikirkan untuk sebuah kurva. Kemudian ini dengan mudah diperluas atau disama ratakan agar berhubungan dengan sebuah lekatan. Hal yang terpenting dari metode tersebut bukan hanya sekedar mengevaluasi titik sepanjang sebuah kurva, kurva tersebut diperkirakan oleh sebuah versi potongan linear yang diperoleh dengan sub-pembagian titik kendali secara rekursif. Ini memberikan perkiraan yang lebih bagus dan semakin bagus terhadap kurva tersebut. Tingkat sub-pembagianlrekursiberhenti bila kriteria linear dipenuhi. Lane dan Riesenfeld(1980) memperlihatkanbahwa perkiraan potongan linear terhadap kurva tersebut akhirnya akan runtuh pada kurva tersebut, yang memberitahu bahwa sub-pembagian yang dilakukan sudah cukup. Sebuah rumus sub-pembagian untuk basis Bezier (atau, secara umum, basis Bernstein) diberikan oleh Lane dan kawan-kawan (1980) dan diturunkan oleh Lane dan Riesenfeld (1980). (Proses ini dapat digunakan untuk sembarang basis pertama-tama dengan mengubah penyajian menjadi basis Bezier sebagaimana yang diuraikan dalam Bagian 6.9.1.) Ini adalah, pengaruh, algoritma de Casteljau


Gambar

6.33

269

Sobekan yang dihasilkan oleh sub-pembagian lekatan yang tidal<seragam.

yang disebutkan pada awal bab ini. Sebuah kurva Bezier dibagi-bagi menjadi dua kurva dengan sub-pembagian titik kendali, yang membentuk dua himpunan titik kendali Ri dan Si yang baru. Titik R3/S0adalah titik ujung pada kurva yang pertama dan awal yang kedua. Rumus tersebut adalah: Ro = Qo RI = (Qo + QI)/2 R2 = RI/2 + (QI + Q2)/4 R3

= (R2

+ 51)/2

50 51

= R3 = (QI

+ Q2)/4 + 52/2 52 = (Q2 + Q3)/2 53 = Q3

Gambar 6.34 memperlihatkanbagaimana,setelah sub-pembagiantunggal, potongan kurva linear yang menggabungkan dua himpuan titik kendali yang baru adalah perkiraan yang lebih bagus terhadap kurva tersebut daripada yang asli. Perkiraan setelah sub-pembagian tiga tingkat diperlihatkan dalam Gambar 6.35. Proses pemisahan kurva diperluas secara mudah menjadi lekatan, seperti yang dilukiskan pada Gambar 6.36. Kita perhatikan lekatan tersebut dibuat dari empat kurva dengan u yang tetap dan empat kurva dengan v yang tetap, yang memiliki titik kendali berupa baris yang berurutan dan kolom yang berurutan pada matriks titik kendali. Kita menerapkan rumus pemisahan kurva secara terpisah terhadap masing-masing dari empat kurva dalam u yang menghasilkan dua buah sublekatan dari lekatan yang asli. Dengan mengulangi lagi proses tersebut pada u akan menghasilkan dua buah sub-lekatan dan menaruh pembagian ini bersamasama membagi lekatan tersebut menjadi empat. Kedalaman sub-pembagian mudah dikendalikan dengan menggunakan sebuah kriteria linearitas.Fungsi dasar Beziersecara identukmenjumlahmenjadi 1:

270


Q:---

r

/

I 1// 1/

I

\\

",

\

"51

R, ___~,

\\ "_" \\\

'''5-

\

/

1/\

I R,; I

/

~_ __

R:J/

I

I I 1

/

--,.~: ,,/

-..Q:

/

_

\ \ \

\

/ I.

\

Gambar 6.34 Pemisahan sebuah kurva Bezier bikubus.

3

L B;,n(u) = 1

;=0

Ini berarti bahwa kurva tersebut terletak dalam "convex hull" yang dibentuk oleh titik kendali Pi, HasH perkalian sub-pembagian potongan linear akan berimpit dengan kurva bila ia bergabung dengan garis yang menghubungkan dua titik

--r

/

/

Gambar

6.35

Penggambaran

\

\\

I

I I I

i

~

\ \ \ \ \

titik kendali pada masing-masing tingkat sub-pembagian.


271

Control point matrix

Generate four curves of

t

constantII (u ;0.0.:5.0.5.0.1)

t

Apply cUl'\e-spliuing formula

t

Applycurve-splitting

.formula to each~.

to each u

cUI'\'e separaldy to define a split cUI'\'e

Generate four cUl'\'esof constant v (~. ; 0.0.15.0.5. 1.0)

~

cUl'\'e ~parately to define a split curve

The split curves divide the patch into fuur

Gambar 6.36 Menggunakan pemisahan kurva untuk membagi-bagi sebuah lekatan menjadi empat sub-Iekatan.

272


ujung. Derajad yang mana ia dicapai, yakni, linearitas garis yang menghubungkan empat titik kendali, dapat diuji dengan pengukuran jarak dari titik tengah antara dua titik kendali terhadap garis penghubung titik ujung (Gambar 6.37). Filosofi pengujian ini mudah diperluas menjadi lekatan permukaan. Sebuah bidang yang ditetapkan melalui tiga titik kendali yang tidak collinear. Jarak dari masing-masing 13 titik kendali yang lain dari bidang ini kemudian dihitung. Jika salah satu dari jarak-jarak ini terletak diluar toleransi yang telah ditentukan sebelumnya, maka lekatan tersebut selanjutnya dibagi-bagi. Sebuah masalah praktis yang terjadi bila memperhatikan sub-pembagian yang tidak seragam (sub-pembagian sehingga dipenuhi kriteria sifat datar) dibandingkan dengan sub-pembagian yang seragam menjadi beberapa tingkat yang telah ditentukan, merupakan biaya bagi pengujian mengenai sifat datar. la dapat diperdebatkan jika ia lebih sederhana dan lebih bagus, akan tetapi merupakan pendekatan yang kurang bagus, dengan hanya menerima sub-pembagian yang seragam dan mengabaikan kenyataan bahwa beberapa bidang tidak perlu dibagi-bagi (karena mereka telah datar). Plate 8 memperlihatkan sebuah pendekatan sub-pembagian yang seragam untuk teko teh Utah pada sub-sub pembagian satu, dua, dan tiga. Ini memperlihatkan perbedaaan mutu yang dapat diperkirakan mengenai mutu antara gambar-gambar yang dirender terutama dapat dilihat sepanjang edge yang berbayang hitam. Jika sub-pembagian yang seragam diterima maka rendering lekatan bikubus dapat disederhanakanmenjadi fase yang diproses sebelumnyadari sebuah perender penyangga-Z normal. Jika cukup banyak memori yang tersedia, dan kerumitan P,

/

/ / / / /

/.

/ / / / / /

/ / / /

-- P~

d,

P" Gambar 6.37 Sebuah kurva Bezier kubus dengan titik kendali Po,PI, P2, P3.


273

tambahan dari sebuah algoritma garis lacak diperkenalkan, maka ia bukan merupakan langkahyang besar untuk menggunakansub-pembagianyang tidak seragam. Keseluruhan struktur dari sebuah algoritma garis lacak seperti algoritma Lane Carpenter adalah sebagai berikut:

.

(1) Sortir lekatan dtmgan nilai Y maksimum yang memungkinkan. Nilai ini, sebagaimana yang telah dinyatakan, dapat berupa sebuah titik sudut, sebuah titik pada sebuah edge batas, atau sebuah titik pada sebuah edge bayangan hitam. Cara yang cepat untuk memperkirakan nilai ini adalah hanya dengan mengambil nilai Y maksimum "convex hull" dari titik kendali. (2) Untuk masing-masing garis scan sebuah daftar lekatan yang tidak aktif dan aktif diperbaharui. Untuk masing-masing lekatan aktif, sub pembagian dilakukan sehingga apakah kriteria mengenai sifat datar dipenuhi, atau sehingga sembarang dari salah satu hasil sub pembagian tidak lagi memihak sebuah garis scan. Poligon "datar" ditambahkan kepada sebuah daftar poligon aktif dan scan diubah dengan cara normal. Hasil sub pembagian yang tidak lagi tumpan-tindih garis scan dapat ditambahkan pada daftar lekatan yang tidak aktif. Jadi kita memiliki sebuah daftar lekatan yang aktif dan tidak aktif bersama-sama dengan sebuah daftar poligon datar yang aktif. Salah satu hal praktis yang dihubungkan dengan hal ini adalah masalah sobekan. Sobekan merupakan akibat alami dari sub pembagian rekursif atau tidak seragam. Jika salah satu bagian dari sebuah lekatan permukaan dibagi-bagi sepanjang sebuah batas yang digunakan bersama oleh sebuah tambalah yang lain yang tidak memerlukan lagi sub pembagian, maka secara alami akan menghasilkan sebuah celah antara dua bagian tersebut. Kemudian sobekan ini merupakan sebuah luasan yang tidak dinyatakan dan akan tampak sebagai sebuah celah atau lobang dalam fase rendering akhir (Gambar 6.33). Algoritma Lane-Carpenter tidak berhubungan dengan masalah ini. Hal ini dapat diminimalkan dengan pembuatan kriteria mengenai sifat datar lebih teliti, akan tetapi di sini terdapat paradoks komputasi normal. Filosofi dari pendekatan sub pembagian adalah bahwa luasan dari sebuah permukaan dibagi-bagi sampai pada tingkat yang berhubungan dengan lekukan lokal. Luasan datar yang luas merupakan yang dibagi-bagi secara minimal. Luasan yang menunjukkan perubahan lekukan yang eepat akan dibagibagi menjadi poligon yang eukup keeil. Pengetatan kriteria sifat datar berarti bahwa semakin banyak poligon yang dihasilkan dan fase rendering akhir perlu waktu yang lebih lama.

274


Metode Clark berhubungan dengan masalah ini dengan cara yang lebih bagus dengan mengarnbil metode sub pembagian yang sebenamya dibatasi pada kurva batas. Tiga langkah yang terlibat adalah: (I)

Kriteria "convex hull" diterapkan pada edge batas u = I dan u = 0 dan suatu . lekatan dibagi-bagi sepanjang arah v sehingga ini dipenuhi.

(2)

Kemudian metode yang sarna diterapkan terhadap batas v = 1 dan v = O.

(3)

Akhimya, pengujian normal "convex hull" diterapkan kepada hasil sub pembagian tersebut dan proses dilanjutkan, jika perlu, apakah sepanjang arah u atau arah v.

Begitusebuahbatasmemenuhikriteria"convexhull" ia dianggapberupasebuahgaris lurus. Sembarangsub pembagian selanjutnyatidak akan menghasilkanpemisahan. Keuntunganyang memungkinkandari sub pembagianyang searah dengan batas u atau batas v adalah bahwa dengan beberapa obyek ini akan menghasilkanlekatan yang lebihsedikit.Perhatikan,misalnya,subpembagiansebuahpipa padat - sebuah sHinder merupakan sebuah contoh yang biasa bagi obyek seperti ini. Sub pembagian sHinder tersebut yang searah dengan arah yang sejajar dengan sumbu panjangnya akan menghantarkan algoritma ini untuk lebih cepat bersatu dan dengan lekatan yang lebih sedikit daripadaj ika sub pembagian dilakukan pada kedua arah pararnetrik. Kekurangan dari pendekatan ini adalah bahwa ia sulit untuk mengintegrasikandengan sebuahalgoritmagaris scan.Algoritmagaris scanmengemudikan atau mengendalikan urutan sub pembagian.tergantung pada bagaimana lekatan tersebut terletak berkenaan dengan garis scan. Aspek lain yang memerlukan perhatian adalah perhitungan normal permukaan. Ini adalah, tentu saja, diperlukan untuk pembayangan. Mereka dapat diperoleh dengan mudah dari uraian parametrik asal pada sembarang titik (u,v) pada permukaan dengan menghitung perkalian silang dari derivatif u dan derivatifv. Akan tetapi jika sebuah metode sub pembagian digunakan untuk mengubah scan maka rendering poligon akhir akan menggunakan metode interpolasi Phong dan normal puncak dihitung secara mudah dengan mengambil perkalian silang vektor tangen pada titik sudut. Hal ini akan, secara umum, tergantung pada tingkat sub pembagian, memberikan normal puncak yang tidak sejajar untuk poligon datar, akan tetapi semua poligon yang andil pada sebuah puncak akan memiliki normal yang sarna. Dua akibat yang dapat dihasilkan dari kenyataan bahwa poligon datar yang dikirimkan ke sebuah pembuat bayangan dengan normal puncak yang tidak


275

sejajar. Pertama, kesalahan pengaruh bayangan dapat terjadi pada sub pembagian tingkat rendah. Kedua, pertanyaan mengenai normal puneak manakah yang digunakan untuk memisahkan muneul. Masalah terjadi karena tidak semua poligon yang mengitari sebuah puneak dapat tersedia, karena sub pembagian berlangsung dan sebuah puneak rata-rata tidak dapat dihitung sebagaimana dalam jaring poligon. Kasus dapat muneul salah satu normal terletak berlawanan dengan sudut pandang yang lebih besar dari 90° dan salah satunya dengan sudut yang lebih keeil dari 90°. Tindakan yang aman adalah hanya dengan memisahkan sebuah poligon dengan pengujian masing-masing normal puneaknya. Jika sembarang normal puneak dapat dilihat maka poligontersebut tidak dipisahkan. Pendekatan yang lebih dahulu oleh Catmull (1974) membagi-bagi lekatan sehingga mereka kira-kira sama dengan ukuran sebuah pixel tunggal, dengan menuliskan hasil kedalam sebuah penyangga-Z. Hal ini dapat dilaksanakan seeara langsung akan tetapi langlah-Iangkahpendekatan seeara komputasi mahal belum lagi masalah yang lain - yang berhubungan dengan sub pembagian terhadap ukuran layar yang diproyeksikan dari suatu lekatan. Yang jelas disana tidak ada titik dalam sub pembagian yang makin dan semakin dalam jika, bila diproyeksikan menuju ruang layar, tambalah tersebut hanya meneakup beberapa pixel. Clark menghubungkan pengujian sub pembagian terhadap koordinat kedalaman titik kendali dari lekatan. Akhirnya, metode sub pembagian ini berbeda mengenai dasar yang digunakan. Algoritma Lane-Carpenter menggunakan dasar sebuah kubus Bernstein atau B6zier. Clark menggunakan perluasan deret Taylor dan perbedaan pusat untuk menurunkan rumus sub pembagian yang lebih efisien dan menggunakan pengujian mengenai sifat datar yang seeara langsung tersedia dari komponen sub pembagian. Kita uraikan penyajian ini hanya untuk kurva saja akan tetapi, sebagaimana biasanya, teori tersebut meluas sampai lekatan.

6.7

Perluasan kendali: NURBS dan fJ-splines Dua pola penyajian permukaan penting yang ada yang memperluas kendali bentuk gerakan dari puneak kendali. Ini adalah NURBS (non-uniform rational B-splines) dan f3-splines. Dalam kasus NURBS, sebuah puneak kendali diperluas menjadi koordinat empat-dimensi, parametrik tambahan yang menjadi beban yang memungkinkan sebuah bentuk kendali yang halus yang berbeda pengaruh

276


terhadap gerakan sebuah puncak kendali. Dalam bentuk kendali f3-splineyang paling sederhana, dua buah parametrik global diperkenalkan yang mempengaruhi keseluruhan kurva. Ini adalah kendali "bias" dan kendali "ketegangan".

6.7.1

NURBS Sebuah kurva B-spline yang tidak seragam adalah sebuah kurva yang didetinisikan pada sebuah vektor knot dimana rentangan knot bagian dalam tidak sama. Sebagai contoh, kita bisa memiliki knot interior dengan faktor perkalian yang lebih besar dari I Gadi, rentangan knot panjag nol). Beberapa kurva dan permukaan yang biasa, seperti lingkaran dan silinder, memerlukan jarak knot yang tidak seragam, dan penggunaan pilihan ini umumnya memungkinkan kendali bentuk yang lebih bagus dan kemampuan untuk memodel kelompok bentuk yang lebih besar. Perbandingan kurva B-spline didetinisikan oleh sebuah himpunan yang terdiri dari titik kendali empat dimensi:

Peta perspektiof dari kurva tersebut dalam ruang tiga dimensi disebut sebuah kurva "rational B-spline": P(u) = H[~P~ B;.k(U)]

"

=

LP;w;B;.k(U)

;=0

"

L W;B;.k(U) ;=0

"

= ;=0 LP;R;.k(U) dimana

" L. " B.}.k(U)Wj

j=O


"Rational B-splines" memiliki sifat-sifat analitik dan geometrik yang sarna sebagaimana "non-rational B-splines" danjika: untuk semua i

Wi= I

maka:

Wi yang berhubungan dengan masing-masing titik kendali disebut be ban dan dapat dipandang sebagai pararnetrik bentuk tambahan. Dapat diperlihatkan bahwa Wihanya mempengaruhi kurva secara lokal saja. Jika, misalnya, Wjtetap untuk semuaj *-i, sebuah perubahan dalam Wihanya akan mempengaruhi kurva tersebut pada rentangan knot k (seperti menggerakkan sebuah titik kendali hanya akan mempengaruhi kurva tersebut pada rentangan k). Widapat diinterpretasikan secara geometri sebagai sebuah faktor gandengan. Kurva tersebut ditarik ke arah sebuah titik kendali P;jika Wibertambah. Jika Wiberkurang maka kurva tersebut bergerak menjauh dari titik kendali. Kekhususan dari "rational B-splines" disamaratakan dengan segmen conic yang penting dalam CAD. Faux dan Pratt (1979) memperlihatkan bahwa sebuah bentuk kuadrat perbandingan akan menghasilkan sebuah keluarga satu parametrik (w) dari segmen conic.

6.7.2

j'j-splines {3-splinesadalah sebuah rumusan (Barsky dan Beatty, 1983) segmen kurva Bspline. Barsky memperkenalkan dua derajad kebebasan yang baru - bias dan ketegangan - yang dapat diterapkan apakah secara seragam terhadap keselu-

ruhan kurva (B-splines yang berbentuk seragam) atau secara tidak seragam dengan mengubah-ubah nilai mereka sepanjang kurva tersebut (B-splines yang dibentuk secara terus menerus). Untuk nilai bias dan ketengangan yang sesuai, rumusanf3-splinesederhanamenjadisebuahB-splinekubusyang seragarn. Sebuah kurva f3-splineditentukan oleh urutan segmen kurva m-2, yang ke-i adalah: 1

Pj(U)

= r=-2 2: Pi-rbr(/3t>/32,U)

278


dimana: Pi adalah sebuah himpunan titik kendali [PO,PI,...,Pm] O;5;u;5;l i = 2, ..., m-l

br(r31,r32,u)adalah sebuah polinomial kubus yang disebut fungsi dasar p-spline yang ke-r. Dengan mengendorkan keperluan akan kontinuitas derivatif pertama dan kedua (C2) bagi kurva B-spline menjadi tangen satuan dan kontinuitas kurva lekukan (G2), Barsky memberikan rumusan berikut untuk nilai empat fungsi dasar bagi masing-masing segmen kurva seba~ai: b_2(!3l>!32,U)= (2!3V<5)(1- u)3 b_1(!31>!32,U)= (1/<5)[2!3iu(u2- 3u + 3) + 2!3i(u3 3u2 + 2) + 2!31(U3 3u + 2) + !32(2u3 3u2 + 1)] bO(!31>!32,U) = (1/<5)[2!3iu2(-u + 3) + 2!31U(-u2 + 3)

-

+ !32u2(-2u + 3) + 2(-u3 + 1)] b1(!31,!32,U)

= (2u3)/<5

dimana: <5

= 2!3i +

4!3i + 4131+ !32+ 2

Bila r31 = 1 maka kurva tersebut dikatakan tidak dibias. Penarnbahan r31menyebabkan kurva tersebut condong ke salah satu sisi mendekati poligon kendali dengan cara yang tidak simetris. Penggantian r31 dengan nilai kebalikan akan

menyebabkan kurva tersebut condong ke arah yang berlawanan. Parameter ~ mempengaruhi kesimetrisan kurva dan disebut ketegangan. Begitu ~ dinaikkan maka kurva tersebut mendekati po ligon kendali. Bila r31= I dan ~ = 0 maka B-spline sederhana menjadi B-spline kubus yang seragarn. Barsky mengkategorisasikan kurva B-spline yang sedemikian rupa, dalam suku-suku definisinya, sebagai tidak dibias, p-spline yang tidak ditegangkan. Karena p-spline disama-ratakan dengan B-splines, ia memiliki watak yang sarna bila diperkenalkan titik kendali jamak atau knot jamak. Kedua metode kurva tersebut dapat diperluas kepada permukaan perkalian penegang dengan cara yang sarna seperti definisi kurva Bezier dan B-spline yang digunakan sebagai dasar permukaan.


6.8

Interpolasi dengan menggunakan B-splines Dengan menetapkan kurva B-spline (atau permukaan) melalui titik data y~g ada memperoleh dua pemakaian utama dalam grafik komputer. Pertama, dalam pemodelan: sebuah himpunan titik data dapat dihasilkan oleh piranti pendigitasi tiga-djmensi, misalnya seperti "laser ranger". Kemudian masalahnya adalah untuk menetapkan sebuah permukaan melalui titik ini sedemikian hingga sebuah penyajian grafik komputer yang lengkap tersedia untuk pemanipulasian (katakan, untuk animasi atau perubahan bentuk) dengan sebuah program. Kedua, dalam animasi komputer: kita bisa menggunakan sebuah kurva parametrik untuk menyatakan lintasan sebuah obyek yang bergerak melalui tiga-ruang. Posisi tertentu obyek tersebut (posisi bingkai kunci) dapat ditentukan, dan kita perlu menetapkan sebuah kurva melalui titik ini. Sebuah kurva B-spline biasa digunakan untuk maksud ini karena sifat kontinuitasnya C2.Dalam animasi normalnya kita tertarik pada gerakan yang mulus dan kurva B-spline menyatakan posisi sebuah obyek sebagai sebuah fungsi waktu akan menjamin hal ini. Dalam bagian ini kita akan memusatkan perhatian pada interpolasi kurva. Meskipun teori kurva normalnya meluas pada permukaan, ini bukan merupakan kasus bila seseorang ingin untuk memperluas penetapan kurva menjadi penetapan permukaan. Ada masalah yang cukup berarti, yang unik terhadap penetapan permukaan, yang membuat topik ini menjadi bidang penelitian. Prinsip mengenai penetapan permukaan telah diperkenalkan dalam Bab 2 dan diuraikan secara lebih rinei dalam bagian berikutnya. Kita menyatakan masalah interpolasi B-spline secara informal sebagai berikut: ditentukan sebuah himpunan titik data yang kita perlukan untuk menurunkan sebuah himpunan titik kendali untuk sebuah kurva B-spline yang akan menentukan sebuah kurva bebas yang menyatakan titik data. Kita bisa memerlukan kurva tersebut untuk menginterpolasi semua titik atau untuk menginterpolasi sebuah sub himpunan titik dan lewat berdekatan dengan yang lain. Sebagai contoh, pada kasus dimana titik data diketahui agak berderau (ber-noise) atau agak kurang dapat dipercaya barangkali kita tidak memerlukan sebuah interpolasi yang tepat melalui semua titik. Metode yang berbeda untuk penetapan sebuah kurva B-spline kepada sebuah himpunan titik data diberikan oleh Bartels, Beatty, dan Barsky (1988). Kita dapat menyatakan masalah tersebut secara formal untuk kasus dimana kita memerlukan kurva tersebut untuk menginterpolasi semua titik data. Jika kita

280


memperhatikan titik data berupa nilai knot dalam u maka kita memiliki sebuah kubus: m

Q(up) =

L PtB,{up) ;=0

=Dp untuksemua p = 3, . . ., m + 1

dimana: Dp adalah sebuah titik data Upadalah sebuah nilai knot yang berhubungan dengan titik data tersebut Kini masalah yang kita miliki adalah untuk menentukan up. Penyelesaian yang paling mudah, dan satu-satunya yang kita ambil di sini, adalah untuk menetapkan upmenjadip. Ini disebut parametrikisasian seragam dan ia sepenuhnya mengabaikan hubungan geometris antara titik data dan biasanya dipandang sebagai pemberian interpolant yang paling lemah dalam sebuah hierarki mengenai kemungkinan yang diuraikan secara rinei oleh Farin (1990). Penyelesaian berikutnya yang paling bagus, parametrikisasi panjang penghubung, menetapkan interval knot sebanding dengan jarak antara titik data. Keuntungan dari parametrikisasi seragam adalah bahwa ia invariant pada transformasi "affine" dari titik data. Di sini kita menentukan sebuah kurva B-spline melalui titik data. Ada m-I titik data yang diinterpolasikan dan kurva tersebut ditentukan oleh m+] titik kendali. Jika kita memperhatikan sebuah komponen tunggal, katakan x, maka kita memiliki: m x(up)

= ;=0 2.Px;B;(up) = Dxp

dimana Dxp adalah komponen x dari titik data tersebut Ini menentukan sebuah sistem persamaan yang kita selesaikan untuk Pxi:


281

Pola ini menghasilkan m - 1 persamaan dengan m + 1 besaran yang belum diketahui. Sebagai contoh, untuk m = 5 kita memiliki enam titik kendali untuk diperoleh dari empat titik data. Muncul bermacam-macam kemungkinan. Pendekatan yang paling mudah adalah dengan memilih dua buah titik tambahan, P2dan P7, yang diinterpolasikan pada perluasan terhadap kurva pada Q(U2)dan Q(Um+2) memberikan: BO(U2) BO(U3)

Bm(U2) Bm(U3) .

PXO

...

..

Bo(~m+l)

Bm(Um+l)

[BO(Um+2)

Bm(Um+2)

Dx2

-

][ ] [ Pxm

Dx3 .

..

Dxm~l Dxm+1

]

Dalam persamaan ini matriks tersebut akan memiliki masukan nol kecuali dalam sebuah bidang tiga masukan yang lebar sepanjang diagonal utama, dan untuk B-splines kubus matriks tersebut adalah: 4 1

1 4 1

1 4

1

-1 6

I

1

6.9

4 1

1 4

Pemodelan obyek dengan Jaring parametrik bikubus Dalam Bab II kita mengulas teknik pemodelan yang memungkinkan obyek dinyatakan dengan sebuah jaring lekatan parametrik. Kini kita akan melihat proses ini lebih rinci. Masalah pemodelan mencakup pembuatan sebuah uraian jaring parametrik dari goresan dan pengeditan atau perubahan bentuk dari uraian yang telah ada. Salah satu motivasi bagi penggunaan sebuah uraian lekatan adalah kemampuan untuk "memahat" sebuah permukaan yang telah ada dengan perubahan bentuknya. Sedangkan pemodelan dengan sebuah lekatan tunggal, misalnya sebuah tambalah Bezier, adalah secara langsung, kesulitan yang cukup berarti yang muncul bila berkenaan dengan sebuah jaring yang terdiri dari lekatan. Bidang

282


subyek tersebut masih merupakan pokok permasalahan penelitian yang sangat banyak dan karena alasan itulah bahan tersebut di luar cakupan buku ini. Akan tetapi ini merupakan bidang yang sangat penting dan kita akan cakup ia seluas mungkin.

6.9.1

Penetapan pennukaan Teknik yang pertama berarti bahwa kita ingin menginterpolasikan sebuah himpunan titik data tiga-dimensi dengan sebuah permukaan yang didefinisikan secara parametrik. Sebagaimana diuraikan dalam Bab 2, kita melakukan ini pertamatama dengan menetapkan sebuah jaringan yang terdiri dari kurva uv melalui titik data tersebut. Masing-masing titik data diinterpolasi dengan sebuah kurva u dan v yang tetap. Kurva ini adalah B-splines yang diinterpolasi melalui titik data dengan menggunakan teknik interpolasi kurva B-spline dasar. Oalam tahap berikutnya, kurva B-spline diubah menjadi kurva B6zier. Jaringan kurva ini dibagi menjadi elemen jaring individual yang dibentuk dari empat segmen kurva B6zier (lihat Gambar 2.10). Segmen kurva ini adalah batas edge sebuah lekatan B6zier dan ini ditentukan sehingga kita dapat menurunkan titik kendali untuk lekatan tersebut. Jadi seb~ah himpunan titik dalam tiga-ruang diubah menjadi sebuah jaring yang terdiri dari lekatan B6zier dengan menggunakan sebuah jaring yang terdiri dari kurva B-spline sebagai perantara. Kini marilah kita perhatikan tahap pertama

-

dengan menurunkan sebuah

jaringan kurva yang menginterpolasikan titik data. Oi sini masalah utama adalah bahwa kita bisa saja tidak memiliki pengetahuan mengenai topologi dari titik tersebut. (Oalam interpolasi kurva kita ketahui bahwa titik tersebut berurutan.) Ini adalah sebuah masalah yang hanya dapat diselesaikan dalam konteks dan salah satu pendekatan diberikan oleh Watt dan Watt (1992). Perhatikan kasus dimana titik tersebut diperoleh dari sebuah obyek nyata dengan menggunakan sebuah digitizer manual dan urutan titik mana yang menginterpolasi dengan kurva diketahui. Ini merupakan konteks yang umum dan kita akan melanjutkan ke tahap yang kedua

-

yakni penurunan sebuah jaring lekatan B6zier dari sebuah jaringan

kurva B-spline. Pertama kita perlu mengubah kurva B-spline menjadi kurva B6zier dengan segmen yang banyak. Jika pertama yang kita perhatikan sebuah B-spline tunggal maka pengubahan ke bentuk B6zier adalah secara langsung dan ditentukan oleh:


283

dimana:

P adalah titik kendali B6zier Q adalah titik kendali B-spline B adalah matriks B6zier Bs adalah matriks B-spline (Catat bahwa perubahan matriks basis hanya dapat digunakan untuk B-splines yang seragam. Jika jaringan kurva tersebut berisi B-splines yang tidak seragam maka pengubahan harus dilakukan dengan penyisipan knot. Pendekatan yang lebih umum ini diuraikan oleh Watt dan Watt (1992).) Untuk sebuah kurva B-spline segmen banyak kita gunakan rumus ini berulang-ulang terhadap titik kendali yang sesuai. Sebagai contoh, perhatikan sebuah kurva B-spline dua-segmen yang ditentukan oleh lima titik kendali [QoQI Q2Q3 Q4].Rumus pengubahan digunakan dua kali untuk himpunan titik kendali [QoQI Q2Q3]dan [QI Q2Q3Q4]. Kini perhatikan sebuahjaring yang terdiri dari kurva B-spline dua-segmen 5 x 5 dengan titik kendali yang diperlihatkan dalam Gambar 6038(a).Pemakaian pola diatas pada basis baris-demi-baris menghasilkan lima kurva Bezier dua-segmen (Gambar 6038b).Kini kita menterjemahkan ini, kolom-demi-kolom, dan perhatikan masing-masing kolom menjadi titik kendali sebuah kurva B-spline. Ini menghasilkan sebuah jaring yang terdiri dari kurva Bezier dua-segmen 7 x 7 (Gambar 6038c). KIta tahu bahwa edge batas sebuah lekatan B6zier adalah sebuah kurva Bezier dan kita menterjemahkan garis-garis yang tidak terputus dalam Gambar 6038(c)sbagai batas-batas dari empat lekatan Bezier. Jadi kita mengubah sebuah jaringan kurva B-spline dua segmen 5 x 5 menjadi lekatan Bezier 2 x 2. Akan tetapi, kita hanya mendefinisikan batas dari masing-masing lekatan, jadi, kita hanya menentukan 12 dari 16 titik kendali untuk masing-masing lekatan.

284


Pertanyaan yang kini muncul adalah: bagaimana kita menentukan empat titik kendali bagian dalam? Pertama kita perhatikan kepentingan mereka dengan menghasilkan kembali Persamaan 6.4:

Ini menentukan belokan sebuah permukaan sebagai sebuah turunan parsial campuran dan dapat diartikan sebagai sebuah vektor yang merupakan simpangan dari empat sisi sudut polihedron kendali dari sebuah jajaran genjang (Gambar 6.39). Pada saat puntiran nol vektor ini berkurang menuju nol dan sudut empat sisi berupa sebuah jajaran genjang. Pemahaman intuisi mengenai pengaruh puntiran yang bukan nol adalah sulit. Lebih mudah melihat pada arti geometris bila sebuah lekatan memiliki puntiran nol pada sernua empat sisi. Kemudian kita memiliki sebuah permukaan translasi dirnana setiap ernpat sisi dari polihedron kendali adalah sebuahjajaran genjang. Jajaran genjang tersebutjuga mentranslasikan satu sarna lain. Lekatan yang demikian ini disebut permukaan translasi karena ia dihasilkan oleh dua buah kurva, CI(U)dan C2(V).Sembarang garis isoparametrik dalam Uadalah sebuah translasi dari C1dan sernbarang garis isoparametrik dalam v adalah sebuah translasi dari C2. Jadi penyelesaian yang paling mudah untuk memperkirakan empat titik kendali bagian dalam adalah menganggap bahwa lekatan tersebut adalah sebuah permukaan translasi, kemudian titik bagian dalam dapat diturunkandari titik batas. Dampak dari ini, dalam istilah penetapan permukaan, adalah bahwa kurva batasdari lekatan tersebut harus lebih atau kurang rnentranslasikan satu terhadap yang lain. Dalarn sembarang situasi praktis ini akan tergantung pada dua buah faktor: bentuk obyek dan resolusijaringan kurva uv. Anda dapat rnelihat, misalnya dalarn Gambar 2.11, bagaimana keabsahan anggapan ini berubah-ubah pada permukaan obyek tersebut. Metode tersebut memberi kita sebuah permukaan yang benar dengan kontinuitas keseluruhan Cl, akan tetapi ia tidak menjamin bentuk yang bagus. Metode alternatif untuk penentuan puntiran pada sebuah permukaan diberikan oleh Farin (1990).

6.9.2

Rancangan potongan-melintang Rancangan potongan melintang berarti penyusunan sebuah saluran pejal dengan penentuan potongan melintang pada interval sepanjang kurva sapuan atau kurva

Penyajian Parametrik don Pra/ctis 285

(a)

.-

c:

D

.- c:

c:

..

..

D

D

..

c:

c:

..

.

c-

D

..

D

D

..

..

D

c-

..

D

D

..

..

D

C>

.

D

D

..

(b)

I 1

. I

1 I I

. 1 1 I

1 1 1 I

I

I 1

I 1 1

I I 1

I 1

I I

1 1

I I I

1 I I

I I

I

---, I

---, I

'--

___L___L__

,--.

,---

1

I .

--+---:--I 1 1 __.J

--+--+-I I I

T--I

I I I

I

1 L__ . I I

.. (e)

Gambar 6.38 Pengubahan sebuahjaringan kurva B-spline menjadi lekatan B~zier (menurut Farin (1990». (a) Jaringan kurva B-spline dua segmen 5 x 5. (b) Jaringan kurva diubah barisnya menjadi 5 kurva B~zier dua-segmen. (c) Jaringan kurva diubah menjadi kurva B~zierdua segmen 7 x 7 yang membentuk batas dari empat lekatan B~zier.

286


Gambar 6.39 Koefisien puntiran sesuai dengan simpangan polihedron kendali sub-empat sisi dari sebuah jajaran genjang.

spine. Kita rnulai dengan rnendaftarkan hierarki kernungkinan yang tergantung pada kekangan bentuk yang rnelandasi. Ini adalah:

. .

.

Rancangan

-

Surnbu linear: permukaan revolusi (potongan rnelintang lingkaran) kurva sapuan berupa sebuah garis lurus. Surnbu linear: potongan rnelintang yang disarna-ratakan - kurva sapuan berupa sebuah garis lurus, potongan rnelintang berupa sebuah kurva pararnetrik tertutup. Kurva rnelengkung: potongan rnelintang - kurva sapuan dan potongan rnelintang keduanya rnerupakan kurva pararnetrik.

sumbu linear: permukaan

revolusi

Jika kita rnengekang surnbu atau kurva sapuan berupa sebuah garis lurus, kernudian dua kernungkinan secara langsung segera diterirna. Pertarna, permukaan revolusi. Oi sini potongan rnelintang adalah lingkaran dan normal terhadap surnbu tersebut. Variasi potongan rnelintang dikendalikan oleh sebuah kurva profil yang kita detinisikan sebagai sebuah kurva pararnetrik. Untuk rnerancang obyek tersebut seorang pernakai hanya rnendetinisikan dan rnengedit kurva profil tersebut. Ini, jika bukan sebuah kurva Bezier, diubah rnenjadi penyajian Bezier dan dibagi-bagi rnenjadi potongan resolusi linear yang sesuai. Kurva tersebut disapu sekitar surnbu untuk rnenghasilkan sebuah penyajianjaring poligon secara langsung.


Rancangan

sumbu linear: potongan

melintang yang disama-ratakan

Kini kita perhatikan kasus dimana kita memiliki sebuah segmen melintang yang ditentukan oleh sebuah kurva B6zier segmen banyak yang diijinkan untuk berubah sebanding begitu ia disapu sepanjang sumbu tersebut. Sebagai eontoh, perhatikan satu segrnen dari sebuah kurva dengan simetri putar lipat-empat sekitar sumbu z (Gambar 6.40a). Ini ditentukan oleh titik kendali [SoS) S2 S3]. Selanjutnya perhatikan. bahwa ukuran potongan melintang diperbolehkan berubah-ubah sesuai dengan sebuah kurva r = r(v) yang juga sebuah kurva B6zier (Gambar 6.40b) ditentukan oleh titik kendali [Ro R) R2 R3]. Dari uraian ini kita perlu menghasilkan empat lekatan seperti yang diperlihatkan dalam Gambar 6.40(e). Masing-masing lekatan dihasilkan dengan menggerakkan kurva potongan melintang sepanjang sumbu z, penyekalaan sesuai dengan r(v). Jadi, lekatan tersebut adalah sebuah perrnukaan yang berbentuk: Q(u,v) = r(v)Q(u,O) Mudah dilihat (Gambar 6.40d) bahwa 16titik kendali ditentukan oleh:

Rancangan

sumbu yang melengkung

Pertama eatat bahwa dalam Bab 2 kita menghadapi sebuah kasus khusus dari kategori ini. Di sana kurva sapuan atau kurva spine berupa sebuah kurva parametrik akan tetapi potongan melintang berupa sebuah kurva potongan linear, dan model tersebut dihasilkan begitu potongan melintang tersebut disapu sepanjang spine tersebut berupa sebuah obyekjaring poligon. Dalam Bab 2 kita menghadapi masalah bagaimana untuk meletakkan atau mengorientasikanmasing-masing potongan melintang dengan menggunakan sebuah sistem koordinat lokal yang ditentukan pada setiap titik sepanjang kurva tersebut. Kita juga melihat masalah yang muneul sehubungan dengan lekukan kurva sapuan tersebut. Kasus umum pada sebuah saluran padat adalah sebuah kurva variabel yang digerakkan sepanjang sebuah spine variabel. Meskipun ini tampak menjadi se-

288


z

y-+. 5",

.5'11

.......... .5:11

- ---r:

z,

5)(, x

'r;;-

=11--I

'l "

(a)

- --;:.?"

RJ

"

RII r

J

Ji

.

(b)

1'...

x

x (c)

(d)

Gambar 6.40 Rancangan sumbu linear dengan potongan melintang yang disarna-ratakan. (a) Empat kurva Bezier menentukan sebuah potongan melintang dengan simetri lipat-empat. (b) Sebuah kurva penyekalaan untuk potongan melintang. (c) Pembuatan sebuah lekatan dengan penyapuan sepanjang z dan mensekalanya pada saat yang sarna. (d) Titik kendali sisi empat untuk lekatan tersebut.

buah kasus khusus daTimetodologi penetapan permukaan, dimana kita menghas~lkan sebuah jaringan uv di sana ada masalah. Perhatikan Gambar 6.41 yang memperlihatkan dua buah segmen kurva dengan v yang tetap yang ditarik dalam


bidang-bidang ditentukan oleh sebuah sistem koordinat lokal pada kurva tersebut (lihat Bab 2). Kurva tersebut adalah segmen potongan melintang yang ditentukan oleh perancang pada interval yang sesuai sepanjang spine. Masing-masing contoh pada sebuah segmen kurva menentukan sebuah batas dari lekatan yang diperlukan (v = 0, v = 1). Ini menentukan delapan titik kendali untuk lekatan tersebut. Empat titik kendali bagian dalam akhimya dapat dihitung untuk puntiran nol atau bukannol seperti yang telah diuraikan sebelumnya. Masalah muncul dalam penentuan empat titik kendali yang lain yang menentukan kurva yang disapu oleh titik ujung pada segmen kurva tersebut (Gambar 6.42). Karena kurva potongan melintang berubah-ubah, kurva ini tidak mentranslasikan kurva spine. Sebuah penyelesaian terhadap masalah ini, dalam istilah pada sebuah parametrik yang ditentukan oleh diberikan oleh Goss (1976). perancang - 'sudut yang mengembang'

-

6.9.3

Rancangan polihedron kendali: teknik dasar Pendekatan ini untuk pemodelan dengan sebuah obyek lekatan parametrik adalah satu-satunya obyek yang diuraikan dalam kebanyakan buku pelajaran. Gagasan tersebut adalah bahwa, model lekatan yang ada yang telah ditentukan, seorang perancang berinteraksi sebuah kalang yang memungkinkan titik kendaH untuk digerakkan, dan hasil perpindahan yang ditampilkan sebagai sebuah permukaan yang baru. Kadang-kadang ia diuraikan sebagai 'pahatan bentuk-bebas (free-form sculpting)'. Perancang dapat menggerakkan salah satu atau sejumlah titik kendaH sewaktu-waktu, pemodelan sebuah permukaan sebagaimanajika ia berupa bahan yang mudah ditempa seperti pemodelan tanah liat. Dengan meninggalkan masalah praktis mengenai penyediaaan sistem pengeditan tiga-dimensi untuk memudahkan pergerakan titik kendaH,muncul dua masalah yang mendasar. Pertama, apa yang kita kerjakan bila kita berinteraksi dengan sebuah jaring yang terdiri dari lekatan yang bukan berupa sebuah lekatan tunggal? Meskipun rancangan lekatan tunggal dapat mencakup sejumlah masalah praktis, panel badan mobil, misalnya, kita perlu bekerja dengan sebuah jaring lekatan. Masalahnyaadalahbahwakita tidak dapat menggerakkantitik kendali tanpa sebuah lekatan tunggal tanpa memperhatikan kontinuitas dengan lekatan di sekitamya. Sebagai contoh, jika kita memperhatikan sebuah obyek yang dibuat dari lekatan Bezier, maka salah satu cara menggerakkan titik kendaH dan mempertahankan kontinuitas lekatan yang berdampingan adalah untuk menggerakkan kelompok sembilan titik kendaH sebagai sebuah satuan tunggal, sebagaimana yang diperli-

290


Gambar 6.41 Sapuan sebuah kurva umum sepanjang spine umum.

hatkan dalam Gambar 6.43(a). Ini secara otomatis menjamin kontinuitas lekatan akan tetapi ia memiliki pengaruh menghadirkan 'plateaux' kedalam permukaan. Ini mudah dilihat dengan kurva. Gambar 6.43(b) memperlihatkan sebuah kurva Bezier dua-segmen. Jika kita menggerakkan titik kendali dalam kelompok-

--

7 ----

Curl/e ~wept by cro~s.section segment

end points

Sweep curve

Gambar 6.42 Memperlihatkan masalah penentuan titik kendali pada kurva yang disapu oleh titik ujung potongan melintang.


291

kelompok collinear tiga kemudian kita peroleh sebuah pengaruh langkah melengkung (Gambar 6.43c). Apa yang kita perlukan adalah sebuah perubahan bentuk seperti yang diperlihatkan pada Gambar 6.43(d).

6.9.4

Rancangan polihedron kendali: kendali yang teliti Masalah lain yang muncul adalah lokalitas kendali. Kita telah bahas ini dengan memperhatikan lekatan B6zier terhadap lekatan B-spline dan kini kita perhatikan kasus B-spline lebih rinei. Kesulitan memusatkan sekitar kebutuhan agar dapat mengubah skala perubahan bentuk. Meskipun dengan menggerakkan sebuah titik kendali hanya mengubah lekatan yang menggunakan titik tersebut secara bersama-sama, skala perubahan bentuk dalam ruang obyek dihubungkan dengan ukuran lekatan. Ini menganggap bahwa kita dapat mengendalikan skala dengan sub-pembagian lekatan secara lokal dalam daerah perubahan bentukjika diingin-

.

. (b)

Ie)

Gambar 6.43 (a) Empat lekatan Bezier yang berdekatan dan titik kendaH mereka. Kekangan kontinuitas secara tidak langsung menjelaskan bahwa titik kendaH pusat tidak dapat digerakkan tanpa memperhatikan delapan tetangganya. Sembilan titik semuanya dapat digerakkan bersarnasarna dan kontinuitas dipertahankan. (b) Kurva dua-segmen yang tidak diubah bentuk. (c) Kurva yang diubah bentuk dengan menggerakkan titik kendaHdalarn kelompokk collinear. (d) Perubahan bentuk yang diinginkan.

292


kan perubahan yang teliti. Ini adalah dasar dari teknik yang disebut perubahan bentuk B-spline secara hierarki (Forsey dan Bartels, 1988). Perhatikan definisi dari sebuah lekatan B-spline: n

Q(u,v) =

m

L LP;jB;(u)Bj(u)

;=0j=O

Ini dapat didefinisikan kembali oleh penyisipan knot (Farin, 1990) terhadap sebuah lekatan: N .ad

Q(u,v) =

LL

R;jB;(u)Bj(u) ;=0j=O

dimana:

N>n

dan

M>m

Titik kendali yang baru diturunkan sebagaimana yang diuraikan oleh Forsey dan Bartels (1988). Masalahnya adalah bagaimana menggunakan strategi ini terhadap daerah permukaan yang kita tinjau. Forsey dan Bartels melakukan hal ini dengan menentukan sebuah permukaan minimal

-

bagian terkecil dari permuka-

an yang mana perbaikan kembali titik kendali ini dapat diterapkan. Permukaan minimal ini memenuhi dua kekangan:

. .

pe,rgerakan titik kendali yang baru menghasilkan perubahan bentuk yang dilokalisasi terhadap permukaan minimal ini. Derivatif pada batas permukaan minimal masih tetap tidak diubah.

Ini berarti bahwa perubahan bentuk dalam permukaan yang diperbaiki kembali tidak akan mempengaruhi permukaan tersebut dari mana ia diturunkan dan kontinuitas dimana-mana dipertahankan. Motivasi bagi pendekatan yang teliti ini adalah untuk mempengaruhi titik kendali yang diperbaiki hanya dimana diperlukan. Alternatif berupa titik kendali yang diperbaiki kembali pada seluruh permukaan. Proses ini dapat diulang dalam permukaan yang diperbaiki kembali oleh karena sehingga tingkat yang memenuhi dari kendali yang teliti dicapai itu istilah hierarki. Sebuah permukaan minimal adalah 16 lekatan yang didetinisikan oleh sebuah matriks titik kendali 7 x 7 (Gambar 6.44a). Titik kendali yang diperlukan jika

-


293

pusat 4 lekatan diperbaiki kembali menjadi 16 diperlihatkan dalarn Garnbar 6.44(b). Di sini kita catat bahwa 3 x 3 dari titik kendali yang asli digunakan bersama-sarna dengan lekatan yang diperbaiki kembali. Sebuah struktur dinarnik titik kendali diciptakan dengan permukaan yang asli pada akar sebuah pohon hamparan titik kendali. Pengeditan permukaan meminta sebuah pohon melintang dan salah satu titk yang penting dari pola tersebut adalah bahwa lintasan dapat terjadi pada salah satu arah. Perbaikan kembali yang kasar akan membawa perbaikan kembali yang teliti sebelumnya dalarn daerah permukaan yang sarna, karena penyajian dari titik kendali dalarn suku offset yang relatifterhadap sebuah bingkai referensi lokal.

6.9.5

Rancanganpolihedronkendali:kendaliyang kaso,

-

Kini kita memperhatikan kebalikan dari kasus sebelumnya kendali yang kasar. Katakan bahwa kita tertarik mengenai perubahan bentuk global, misalnya, dengan mengarnbil sebuah silinder atau obyek yang berbentuk pipa dan membengkokkannya menjadi sebuah bentuk toroida. Di sini mungkin kita perlu mengoperasikan, sarnpai beberapa tingkat, pada semua titik kendali secara serentak. Perhatikan strategi yang digunakan pada sebuah kurva Q(t) yang ditentukan oleh empat titik kendali Pi. Pertama, kita mencantumkan kurva tersebut dalam sebuah satuan luas dan membagi daerah ini ke dalam kisi biasa dari titik Rij (i

=

0,...,3);j = 0, ..., 3) sebagaimana yang diperlihatkan dalarn Garnbar 6.45. Jika kita memperhatikan persegi tersebut berupa ruang uv maka kita dapat menulis: 3

(u,v) =

3

L LR;jB;(u)Bj(v)

;=0j=O

Bandingkan identitas ini dengan persamaan untuk sebuah lekatan B6zier parametrik bikubus. Identitas ini mengikuti sifat ketepatan linear dari polinomial B,(u) dan Biv) dan ia menyatakan kenyataan bahwa sebuah himpunan titik kendali coplanar akan menentukan sebuah lekatan planar. Jika kisi dari titik Rij kini diubah menjadi kisi R'ij (Gambar 6.45) maka titik (u,v) akan dipetakan menuju titik (u' ,v') 3

(u' ,v') =

3

L L RijB;(u)Bj(v) ;=0 j=O

294


0

0

0

0

0

0

0 0

0 0

./

./'"

0

0

0

0

0

0

0

-",Po.

0

o - control

0

0

0

0

0

0

0

0

poinls P (a)

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

t--..., I I ....-4

0

0

refin.:d

patch.:>

0

.-

0

0

cOnlrol points q

(b)

Gambar 6.44 (a) Enambelas lekatan permukaan minimal dengan 49 titik kendali. (b) Pusat 4 lekatan yang diperbaiki kembali menjadi 161ekatan (menurut Forsey dan Bartels (1988».

dan kita dapat menggunakan persarnaan ini untuk menurunkan sebuah himpunan titik kendali yang baru, P;', untuk kurva yang baru °Q'(t). Ini adalah sebuah metode perubahan bentuk kurva secara global dan tidak secara langsung. Kita melekatkan kurva tersebut dalam sebuah lekatan planar, mengubah lekatan tersebut dengan menggerakkan titik kendali lekatan tersebut dan, pada saat yang sarna, mengubah bentuk kurva tersebut. Kini untuk memperluas prinsip ini untuk beroperasi secara global pada lekatan yang kita lekatkan titik kendali, Pij, pada lekatan yang kita harap agar berubah bentuk dalam 'triviate Bezier hyperpatch, ia sendiri ditentukan oleh sebuah kisi titik kendali tiga-dimensi, Rijk,yang membentuk sebuah kubus satuan. Jadi kita memiliki:


Q(I)

c =R" o =P,

t

c = R'

Q'(I)

o =P'

Gambar 6.45 Perubahan global dari sebuah kurva planar (menurut Farin (1990)).

3

(u' ,v' ,w') =

3

3

2:2:2:RljkB;(u)Bj(v)Bk(W)

(6.5)

;-=0 j=O k=O

Kisi kubus satuan tersebut diubah secara global dengan sembarang cara yang kita perlukan dan titik kendali lekatan yang barn, P'ij, dihitung. Sebuah aspek penting dari teknik ini adalah bahwa ia dapat diterapkan pada sebuah obyek dengan sembarang penyajian parametrik. Jadi kita juga dapat melekatkan dalarn ruang Bezier trivial. Kita juga dapat melekatkan puncak jaring poligon dengan cara yang sarna. Ini memberi kita konsep pada sembarang titik x yang dilekatkan dalarn sebuah volume hyperpatch trivial dan kemudian dipetakan ke titik x' oleh pengubahan secara global kisi kendali dari lekatan trivial. Dengan menggunakan Persarnaan 6.5 untuk melakukan ini kita perlu memetakan x

296


menuju ruang (U,V,W)dan (U',V',W') kembali menuju ruang cartesian. Pengubahan tersebut adalah:

x

= xo +

uu + av + ww

dan

= u . (x - xo) a = v . (x - xo) w = w . (x - xo)

u

Xomenentukan asal rugna (u,v,w) dan u,v,w menentukan ruang tersebut. Nilai ini ditetapkan oleh perancang, yang menempatkan kubus satuan terhadap obyek yang diubah. Teknik tersebut mulanya dikembangkan oleh Bezier (1972) akan tetapi kebanyakan penanganan yang berorientasikan-grafik mengacu pada tulisan Sederberg dan Parry (1986) dimana strategi ini diistilahkan 'free form deformation (FDD), perubahan bentuk bebas).

Proyek, catatan, dan saran. 6.1 Patch editor (*) Tulislah sebuah editor interaktif yang memudahkan perubahan bentuk sebuah kurva Bezier atau sebuah lekatan permukaan Bezier. Editor tersebut hams memperbolehkan pemakai meraih dan memanipulasi titik kendali. Proyek 1.3 membahas masalah umum mengenai penggunaan sebuah piranti locator dua-dimensi dalam ruang tiga-dimensi. 6.2 Animasi titik kendali (*) Dengan menggunakan prosedur interpolasi yang sesuai dengan titik kendali yang menentukan bentuk yang dibuat, katakan, segmen Bezier potongan, tulislah sebuah program untuk berada antara pentransformasian pada salah satu bentuk bebas menjadi bentuk yang lain. Sebagai contoh, Gambar 6.46 memperlihatkan sebuah kurva Bezier segmen banyak yang membentuk huruf 'E' yang berubah menjadi sebuah kurva yang membentuk huruf 'Z'. UIangi prosedur ini dengan menggunakan B-splines. Perluas prosedur tersebut untuk menangani permukaan.


297

6.3 Perenderan lekatan bikubus Dengan menggunakan perangkat-lunak perenderan pada Bab 5, tulislah sebuah algoritma sub-pembagian seragam yang mengubah lekatan parametrik ,bikubus menjadi poligon. Bandingkan biaya sub-pembagian seragam dengan sub-pembagian yang tidak seragam.

Gambar 6.46 Sebuah kurva Bezier segmen banyak yang menyatakan huruf 'E' yang berubah menjadi sebuah kurva yang menyatakan huruf 'Z'.

I

298


6.4 Metode pemodelan dan metode penyajian

~

sebuah perbandingan

(*)

Perhatikan sebuah contoh mengenai sebuah benda padat yang bukan trivial, katakan misalnya, yang dibentuk dari gabungan tiga buah sHinder yang saling tegak lurus satu sarna lain. Gunakan sebuah benda padat seperti ini dalam studi yang membandingkan metode penyajian berikut ini: (I)

Sebuah model jaring poligon: Model jaring poligon yang diambil dalam buku ini hanya salah satu dari sejumlah pola yang memungkinkan yang secara umum dikenal sebagai penyajian batas. Pola ini berbeda cara edge dan puncak dinyatakan dan dihubungkan, dan dalam besaran, yang bukan poligon, yang tampak dalam penyajian tersebut.

(2) Permukaan kuadrat. Gunakan sebuah himpunan persamaan implisit untuk sebuah kumpulan fungsi kuadrat (Proyek 2.4). (3) Sebuah modellekatan parametrik bikubus: Gunakan sebuah jaring dari sejumlah lekatan parametrik bikubus yang sesuai untuk menyatakan suatu permukaan. (4) Sebuah pohon CSG: CSG menunjukkan susunan geometri dan merupakan sebuah bentuk yang terutama digunakan dalam pemakaian CAD. (5) Octrees: Dibahas dalam Bab 2, octrees digunakan secara luas, misalnya, dalam gambar medis, dimana gambar potongan melintang yang berurutan digabungkan untuk membentuk sebuah medan data tiga-dimensi yang dinyatakan oleh sebuah octree. Pokok masalah yang bisa anda pikirkan sebagai perbandingan adalah:

· · · ·

Kesama-rataan penyajian. Apakah batasan pada jenis bentuk tiga-dimensi yang dapat dinyatakan? Kesulitan relatif dalam membangun antau menentukan struktur asalnya. Kemampuan untuk menurunkansebuah bentuk penyajiandari data yang dikumpulkan secara otomatis sepertisebuah obyek yang di-scan oleh "laser ranger". Keperluan akan penyimpan data.


.

.

.

299

Kemampuan dari metode tersebut untuk mengakomodasi sebuah pola pengeditan interaktif. Mudahnya perenderan obyek. Sebagai contoh, apa yang anda lakukan mengenai pengambilan sebuah permukaan dari sebuah penyajian octree? Yangjelas perender penyangga-Z dapat menangani sebuah operator gabungan dalam sebuah penyajianCSG, akantetapi seberapabagus sebuahperenderpenyangga-Z dapat menangani sebuah pohon CSG? Kesama-rataan metode tersebut terhadap pemakaian. Sebagai contoh, dapatkan metode CSG diterapkan dalam grafik tiga-dimensi "kreatif' dimana model jaring poligon cenderung lebih dominan?

Proyek ini harus mencantumkan pencarian yang luas melalui literatur dan referensi yang dengan sengaja diabaikan. 6.5 Pemodelan silinder yang disama-ratakan (*) Rancanglah sebuah sistem yang mengimplementasikan sebuah metode silinder yang disama-ratakan (Bab 2) untuk pemodelan obyekjaring pOligOl..Tiga bidang pandang harus tampak pada layar: satu untuk kurva profit, satu untuk potongan melintang, dan satu untuk obyek. Kurva profit dan obyek harus berupa kurva

A

Gambar 6.47 Sebuah obyek sapuan yang berkerut. Kurva A adalah kurva sumbu utama. Kurva B adalah profil obyek sapuan (jadi, ia menyatakan ukuran potongan melintang sepanjang A) dan pada kanan atas ukuran potongan melintang terlalu besar.

300


B6zier yang dihasilkan secara interaktif dan pola tersebut untuk menjamin resolusi poligon sebagai sebuah fungsi lekukan kurva sapuan harus diimplementasikan. Catat bahwa disana ada sebuah masalah praktis, sebuah contoh dari masalah tersebut diperlihatkan dalam Gambar 6.47. Di sini A adalah sebuah kurva sapuan. Anggap sebuah kurva profil yang datar. Jika lekukan kurva tersebut terlalu ketat sebuah kerutan dapat terjadi karena offset profil obyek tersebut terlalu besar bagi lengkungan.

6 PenyaiianParametrik

Recommend Documents