Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.2 Nopember2008
ISSN 1978-9483
PEMINDAIAN OBYEK DENGAN ALGORITMA SCANLINE Ina Agustina Jurusan Sistem Informasi, Fakultas Teknologi Komunikasi dan Informatika, Universitas Nasional Jl. Sawo Manila, Pejaten Pasar Minggu No.61, Jakarta 12520 Email:
[email protected] ABSTRACT On this paper we proposed scanline method in order to scan an complicated object dimension. By this method the line property of each dimension could be separated each other. The important result is the information of pixel could be mapped in detail. Keywords: scanline, polygon, pixel ABSTRAK Poligon adalah sederetan garis lurus (polyline) yang sambung -menyambung secara siklik melingkupi suatu area. Garis-garis tersebut disebut garis tepi (edge). Titik pertemuan se tiap pasang sisi kita sebut verteks. Dalam representasinya biasanya suatu poligon dinyatakan dengan koordinat verteks-verteks ini dan penggambaran tepi-tepi ploigon dilakukan dengan penggambaran setiap garis antara dua verteks bertuturan dengan algoritma yang akan dibahas. Untuk kasus di mana piksel-piksel di dalam area poligon perlu di-”warna” -i maka kita perlu mengenal algoritma pengisian poligon berikut ini. Kata kunci: algoritma, scanline, piksel
I. PENDAHULUAN Apabila kita mengetahui adanya suatu piksel yang berada dalam area poligon, maka pikselpiksel lain dapat dengan mudah dicapai dari piksel ini dengan suatu algoritma rekrusif. Namun secara umum hal ini tidak selalu bisa terjadi. Algoritma Scan line dapat memecahkan masalah ini dengan melakukan : • Scan secara horizontal dari kiri ke kanan: mendapatkan titik -titik perpotongan dengan tepi-tepi poligon, mengurutkan dari kiri ke kanan (menurut harga absis) kemudian memberi warna piksel-piksel di antara dua pasang urutan ganjil-genap titik potong tsb. • Hal tersebut dilakukan berulang dari yang paling bawah (harga ordinat verteks terkecil) ke yang paling atas (harga ordinat verteks terbesar).
108
Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.2 Nopember2008
ISSN 1978-9483
Dalam pembuatan program ini, akan dibuat dengan menggunakan C++ dengan menggunakan Algoritma scan line. II. PEMBAHASAN Scan Line Algoritma scanline memecahkan masalah permukaan-tersembunyi dengan 1 scan line pada satu waktu, biasanya dengan cara dari atas ke bawah. Algoritma ini memeriksa beberapan window secara berurutan yang masing2 setinggi scanline dan selebar layar. Algritma scanline yang paling sederhana yaitu versi 1 dimensi dari ‘depth buffer’. kita memerlukan 2 array: intensity[x] dan depth[x] untuk menampung nilai2 dari sebuah scanline. Algoritma Koherensi Scan Line Algoritma scan line meyelesaikan masa lah permukaan yang tersembunyi pada tiap scan line. Biasanya proses scan line berasal dari atas ke bawah dari gambar/penggambaran. Algoritma ini berhasil memerikasa seri dari jendela(windows) pada layar. Tiap jendela(window) adalah satu scan line tinggi dan lebar yang sama dengan layar(screen). Scan line yang paling sederhana adalah sebuah versi dimensi satu dari depth buffer(kedalaman penyangga). Kita membutuhkan dua array yaitu intensitas atau intensity[x] dan kedalaman atau depth[x], untuk menampung nilai dari scan line tunggal. Algoritma kohenerensi scan line Untuk tiap scan line terdiri dari 3 langkah : 1. Untuk semua pixel pada scan line, atur depth[x] ke 1.0 dan intensity[x] ke suatu nilai belakang (background value). 2. Untuk tiap polygon pada layar, temukan semua pixel pada scan line y sebelumnya yang rapat/berhimpit dengan polygon. Langkah ini menggunakan Y-X scan-conversion algoritma yang dideskripsikan pada sesi 16-5. Untuk tiap nilai x ini: a. Kalkulasi kedalaman z( depth z) dari polygon pada (x,y). b. Jika z< depth[x], atur depth[x] ke z dan intensity[x] ke korespondensi intensitas dari polygon shading. 3. Setelah semua polygon telah dipastikan, nilai yang terkandung pada intensitas array mewakili dari solusi, dan dapat di duplikat pada frame buffer. Akibatnya , algoritma pada akhirnya menkonversi scan sema polygon pada layar, satu scan line pada tiap waktu. Ini adalah sebuah ekstensi sederhana dari Y-X scan-conversion algoritma. Disini sebuah nilai kedalaman(depth) harus dikomputasi dan dibandingkan dengan nilai yang telah terekam/tersimpan pada depth buffer. Span-coherence algoritma 109
Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.2 Nopember2008
ISSN 1978-9483
Algoritma scan line dapat mengkapitalisasi pada subah form/bentuk dimensi satu dari area kohenesi yang dikenal sebagai span coherence. Spans pendek atau sekuensi pixel pada sebuah scanline akan berhimpit dengan polygon yang sama. Algoritma pencarian untuk sebuah span, ketika dibutuhkan, hanya membuat sedikit perbandingan kedalaman(depth) untuk mengindentifikasikan polygon yang tampak melalui span. Teknik ini diilustrasikan pada gambar 2.1, dimana menampilkan bagaimana segmen dari polygon dibuat dengan menginteseksi/menggabungkan polygon dengan representasi plane oleh scan line. y
z
z
1
2
x
(a)
3
4
5 x
(b) Gambar 2.1
Kalkulasi pada xz plane digunakan untuk mengdeterminasi hubungan antara segmen dari semua polygon menginterseksi scan line dan untuk memutuskan segmen mana yang Nampak pada tiap span. L okasi dari segmen yaitu digenerasikan oleh konkurensi scan konversi dari polygon, hanya untuk sebagai scan line coherence algoritma. Koordinat x dan z dari titik akhir dari segmen mungkin akan dikomputasikan/dihitung di sebuah incremental manner karena mereka adalah fungsi linear dari y, karena itu, persamaan dari tepi polygon dapat ditulis dengan x = ay + ß dan z = ?y + d. Span dari scan line diidentifikasikan dengan mengurutkan semua segmen titik akhir dengan x dan memeriksa wilayah/region yang tidak dibatasi oleh nila x ini. Sebuah span akan jatuh pada satu dari 3 kelas yaitu : 1. Tidak ada segmen yang muncul bersama span (span 1 dan 5). Intensitas latar belakan akan ditampilkan pada wilayah ini. 2. Segment tunggal jatuh bersama span(span 2 dan 4). Jelasnya, segment Nampak dan bayangan polygon ditampilkan melalui span. 3. Beberapa segmen diturunkanmelewati keseluruhan span (span 3). Segment dekat dengan mata, salah satu yang lebih kecil dari nilai z, ditemukan dengan membandingkan kedalaman dari semua segmen pada satu koodinat x, sperti pada tepi kiri dari span. Sekali polygon yang tampak diidentifikasi, intensitas yang diteriman dapat mengdeterminasi untuk span. Algoritma ini mengambil keuntungan dari koherensi untuk mereduksi pengurutan x dan z. daftar tepi/edge aktif tunggal,yang diurutkan berdasarkan x, mengandung deskripsi tepi untuk semua polygon yang menginterseksi scan line. Dengan menaikkan pembaruan dari scan line ke scan line, hal itu akan tersortir. Pada proses dari tiap scan line, dimana proses dari kiri ke kanan, tepi digunakan untuk menjaga kumpulan/urutan dari aktif polygon. Garis tepi memulai/menjalankan sebuah span, akan dapat membuat sebuah tepi kiri polygon. Dan menyebabkan polygon menjadi aktif (gambar 2.1 b). kiri kanan tepi secara alami dapat dijabarkan/dihasilkan oleh pengasosiasian dengan sebuah polygon yang mendekati record dari polygon yang sedang aktif dan dengan sedikit mengkomplementasikan tiap waktu dari tepi polygon; atau jika polygon selalu digambarkan dengan cara yang sama/konsisten, dengan membiarkan arah edge(garis tepi) mendeterminasy perpotongannya(parity). Sisi yang memulai sebuah span akan menjadi sisi kiri dari sebuah poligon dan menyebabkan 110
Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.2 Nopember2008
ISSN 1978-9483
poligon tersebut aktif, atau sisi kanan yang menonaktifkan poligon. Hal tersebut dapat dibedakan dengan 2 cara: 1. Asosiasikan sebuah bit dengan sebuah poligon untuk mencatat apakah poligon tersebut saat ini sedang aktif, dan dengan mengganti bitnya setiap kali ditemukan sisi dari poligon 2. (Jika poligon2 itu digambarkan secara konsisten)biarkan arah dari sisi menentukan bagiannya; sisi yang turun adalah sisi kiri. Pada tepi kiri dari span, polygon aktif sedang mencari untuk menemukan salah satu tepi dengan nilai z terkecil dan secara konsekuen mendekati pencari. Untuk menyederhanakan pencarian, lis t polygon aktif dapat tetap diurutkan oleh z, dengan polygon memasuki dan meninggalkan daftar ketika kita pindah dari span yang satu ke span yang lainnya. Walaupun nilai z harus dikalkulasikan kembali untuk tiap span, nilai baru mengubah depth ordering(pemesanan kedalaman) dari polygon. Kenyataannya, pengurutan/order tidak pernah mengubah setelah sebuah polygon dimasukkan kedalam daftar aktif jika kita tidak mengizinkan penetrasi wajah/bentuk, dimana wajah/bentuk(face) dari sebuah objek mempenetrasi melewati face lainnya. Penanganan penetrasi faces/wajah/bentuk akan juga membutuhakan tiga kasus yang dideskripsikan diatas, sebagai polygon tunggal yang mungkin tidak tampak menembus/melalui suatu span. Dengan mengubah algoritma yang memutuskan polygon mana yang nampak bersama span untuk menangani kasus lebih banyak, kita dapat memproses scan line dalam sedikit spans. Pada gambar 2.1 b, sebagai contoh, span 1 dan 2 dapat diproses menjadi satu: hanya satu segmen tunggal jatuh bersama region/wilayah. Span 3 dan 4 dapat dilayani bersama, kita tidak izinkan memenetrasi faces/wajah/bentuk atau membuat tambahan pembanding kedalaman bersama dengan span. Algoritma Watkin [500] mampu menangani span besar ini dan mengingat dari satu scan line ke scan line berikutnya dimana span menemukan cara cukup sederhana untuk menyelesaikan masalah tersebut. Scan line algoritma juga dapat menagmbil keuntungan dari depth koherensi. Suatu posisi segmen didalam list/daftar polygon aktif (diurutkan berdasarkan dept/kedalaman) tidak seperti untuk menangani dari satu scan line ke scan line berikutnya. Sebuah estimasi dari posisi mereduksi jumlah dari depth/kedalaman komputasi yang dibutuhkan untuk memasukkan polygon ke daftar aktif. Algoritma ScanLine Polygon 1. Tentukan Banyaknya garis. 2. Tentukan titik koordinat. 3. Gambar garis dari masing-masing titik dengan titik yang berdekatan. 4. Gambar masing-masing pixel per pixel didalam polygon. Algoritma ScanLine Rectangle 1. Tentukan koordinat kiri bawah dan kanan atas 2. Kemudian program akan menentukan koordinat kiri atas dan kanan bawah. 3. Setelah itu gambar dari masing-masing titik yang berdekatan. 4. Gambar masing-masing pixel per pixel didalam rectangle. Algoritma ScanLine Circle 1. Tentukan titik tengah dari lingkaran. 2. Tentukan jari-jari lingkaran 3. Gambar Lingkaran 4. Gambar masing-masing pixel per pixel didalam Circle.
111
Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.2 Nopember2008
ISSN 1978-9483
III. PENUTUP Algoritma scan-line memecahkan masalah hidden-surface pada pembacaan garis, biasanya memproses scan garis dari atas ke bawah dari tampilan. Algoritma ini berturut-turut diuji pada rangkaian window pada layar, masing-masing window adalah satu scan garis tinggi dan selebar layar. Algoritma scan-line paling sederhana adalah versi satu dimensi dari depth buffer. Kita membutuhkan dua array, intensity [x] dan depth [x] untuk mendapatkan nilai untuk single scan garis. Algoritma scan-line mengambil keuntungan dari hubungan antara scan garis berurutan dan dari rentang hubungan di dalam scan garis. Algoritma scan-line juga menyederhanakan perhitungan geometris dengan mereduksi suatu masalah tiga dimensi menjadi suatu perbandingan dua dimensi dari segmen-segmen pada bidang xz. Penyederhanaan geometris ini bukanlah tanpa kelemahan. Ketika kita mengamati algoritma scan-conversion, sangat kecil atau sangat terbatas poligon mungkin akan mengenai bidang scan-line. Penggunaan algoritma scan-line terutama dihubungkan dengan kompleksitas visible image. Perilaku ini pertama kali diamati oleh Watkins dan diselidiki lebih lanjut melalui survei dari beberapa algoritma. Algoritma scan-line mempunyai dua keuntungan, yaitu algoritma ini dapat diimplementasikan pada perangkat keras (hardware) dan dapat digeneralisasi untuk mengatasi bidang non linier (contohnya bidang non poligon).
DAFTAR PUSTAKA [1] Basuki, Achmad dan Nana Ramadijanti, Grafika Komputer: Teori dan Implementasi, Andi Yogyakarta, 2006. [2] Hill, F.S, Computer Graphic Using OpenGl, Second Edition, Prentice Hall, 2001. [3] Kadir, Abdul, Pemrograman C++, Andi Yogyakarta, 2003. [4] Bambang wirawan, Paulus, Grafik Komputer dengan C, Jakarta : Penerbit Andi, 2003 [5] http :\ \ www.eprogramming.com [6] http :\ \www.google.com\openGL [7] http :\ \www.google.com\yoav Lahav
112
