Algoritma Pembentukan Garis Dda Dan Bres [PDF]

Citation preview

ALGORITMA PEMBENTUKAN GARIS DDA DAN BRESENHAM BESERTA PENGAPLIKASIANNYA DALAM JAVA



Alih Nurdiansyah*1,Fernado Tanudjaya*2, Angga Wiguna Abadi*3, Esa Firmansyah S.T.,M.Kom.*4 STMIK Sumedang, Jl.Angkrek Situ No. 19 Sumedang, Telpon : (0261)207395, E-mail:[email protected] E-mail :*1 [email protected] , [email protected], 3 [email protected] ,4 [email protected]



Abstrak



Seiring dengan berkembangnya zaman, dalam ilmu grafika komputer, kemajuan teknologi menyebabkan kebutuhan manusia semakin bertambah. Kebutuhan dan pemecahan masalah itu dapat lebih mudah terpenuhi. Tak terkecuali pada ilmu grafika kompter, perkembangan kemampuan komputasi prosesor yang pesat telah membuat komputer desktop mempunyai kemampuan komputasi yang besar. Hal ini mendorong perkembangan program aplikasi yang memerlukan komputasi yang besar seperti program aplikasi yang menggunakan grafik 3 dimensi. Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yang sarat komputasi, perlu dibarengi peningkatan efisiensi algoritma, sehingga pembuatan grafik garis dan kurva yang merupakan dasar pembuatan grafik dapat memberikan hasil yang optimal. Algoritma itu ssendiri adalah urutan atau langkah-langkah untuk penghitungan atau untuk menyelesaikan suatu masalah yang ditulis secara berurutan. Sedangkan garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritma yang umum adalah DDA dan Bressenham. Algoritma DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai integer. Sedangkan algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer



Katakunci :Algoritma pembentukan garis, DDA, Bresenham, Grafika Komputer.



1. PENDAHULUAN Apa itu Algoritma Pembentukan Garis? Mengapa di dalam ilmu grafika komputer kita perlu mengetahui algoritma pembentukan garis? Dalam matematika dan ilmu komputer, algoritma adalah urutan atau langkah-langkah untuk penghitungan atau untuk menyelesaikan suatu masalah yang ditulis secara berurutan. Sehingga, algoritma pemrograman adalah urutan atau langkahlangkah untuk menyelesaikan masalah pemrograman komputer. Dalam pemrograman, hal yang



penting untuk dipahami adalah logika kita dalam berpikir bagaimana cara untuk memecahkan masalah pemrograman yang akan dibuat. Sebagai contoh, banyak permasalahan matematika yang mudah jika diselesaikan secara tertulis, tetapi cukup sulit jika kita terjemahkan ke dalam pemrograman. Dalam hal ini, algoritma dan logika pemrograman akan sangat penting dalam pemecahan masalah. [1] Sedangkan garis itu sendiri merupakan suatu himpunan titik-titik yang anggotanya terdiri dari lebih satu buah titik. Dan titik-titik tersebut berderet ke dua arah yang berlawanan hingga jauh tidak terhingga. Sedangkan model ataupun representasi suatu garis misalkan seperti seutas benang atau juga tali lurus yang bisa diperpanjang pada kedua arah yang berlawanan hingga jauh tak terhingga. Garis juga merupakan salah satu bentuk dasar dari gambar. Sebuah garis dalam grafika komputer disebut dengan segmen. Garis hanya memiliki ukuran yang panjang, berbeda dengan titik yang diberikan nama menggunakan satu buah dari huruf kapital, tetapi garis diberi nama dengan mengunakan sebuah huruf kecil seperti g, h, k dan juga seterusnya ataupun dua buah huruf kapital misalkan AB, AC, BC dan juga seterusnya. [2]



2. TINJAUAN PUSTAKA Sebelum membahas lebih dalam mengenai algoritma pembentukan garis, terlebih dahulu kita membahas sejarah algoritma dan garis itu sendiri. Algoritma pada dasarnya adalah susunan logis dan sistematis yang digunakan untuk memecahkan atau pun menyelesaikan suatu permasalahan tertentu. Jadi, setiap susunan logis yang diurutkan berdasarkan sistematika tertentu yang dipakai untuk menyelesaikan permasalahan dapat digolongkan sebagai sebuah algoritma. Susunan atau pun langkah – langkah memasak mie intan misalnya, langkah – langkah sistematis yang digunakan untuk memasak mie instan dapat digolongkan ke dalam logaritma, karena menyelesaikan sebuah permasalahan yaitu permasalahan lapar yang dirasakan oleh manusia. Dalam dunia pemrograman, algoritma digunakan untuk membangun berbagai macam software yang digunakan pada perangkat komputer. Penerapan sistem algoritma dalam pembuatan software biasanya dilakukan melalui beberapa jenis bahasa pemrograman seperti bahasa pemrograman C, bahasa pemrograman C#, dan bahasa pemrograman Visual Basic.



Tanpa algoritma yang tepat, susunan sintax atau pun baris – baris kode bahasa pemrograman yang telah dibuat tidak akan ada artinya sama sekali. Hal ini dikarenakan seluruh baris – baris kode yang dibuat dengan menggunakan tiga macam bahasa pemrograman di atas diatur sepenuhnya oleh algoritma yang dibuat. Dari mulai aktivitas pembukaan software aplikasi hingga ke berbagai macam aktivitas kerja yang digunakan oleh penggunanya, semuanya diatur oleh algoritma pemrograman yang dibuat oleh pengembang software tersebut. Menurut Goodman Hedet Niemi “algoritma adalah urutan terbatas dari operasi-operasi terdefinisi dengan baik, yang masing-masing membutuhkan memori dan waktu yang terbatas untuk menyelesaikan suatu masalah”. Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. semua bentuk gambar berawal dari satu titik yang membuat suatu gerakan, titik itu bergerak dan terbentuklah suatu garis dikenal sebagai dimensi-pertama. Bila garis itu bergerak membentuk sebuah bidang, maka kita dapat menentukan sebuah unsur dua-dimensi. Selama perkembangannya dari bidang menjadi ruang, pertemuan bidang-bidang tadi melahirkan suatu badan (tiga-dimensi) Sebuah ringkasan mengenai energi kinetic yang menggerakkan sebuah titik menjadi garis, garis menjadi bidang dan bidang menjadi dimensi ruang” (1960, Paul Klee, The Thinking Eye: The Notebooks of Paul Klee). Garis dibuat dengan menentukan dua endpoint atau posisi awal dan posisi akhir dari suatu garis. Kemudian peralatan output membuat garis sesuai posisi titik titik tersebut. Untuk peralatan analog seperti plotter an random-scan display garis lurus dapat dihasilkan dengan halus. Garis adalah penghubung antara dua buah titik (titik awal dan titik akhir). Seperti yang kita tahu, bahwa persamaan garis lurus dinyatakan dalam rumus: y=mx+c. Dimana m adalah gradien yang didapatkan dari hasil pembagian deltaY dengan deltaX dan c adalah sebuah konstanta. Berangkat dari sini kita coba mulai untuk membahas algortima apa saja yang digunakan dalam pembuatan garis lurus. [3] Algoritma DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai integer. DDA ( Digital Differential Analyzer) adalah garis yang membentang antara 2 titik, P1 dan P2. Dimana ke-2 titik ini membentuk sudut



yang besarnya sangat bervariasi. Bekerja atas dasar penambahan nilai x dan nilai y. Dimana pada garis lurus, turunan pertama dari x dan y adalah kostanta. [4] Algoritma DDA mengambil nilai integer terdekat dengan jalur garis berdasarkan atas sebuah titik yang telah ditentukan sebelumnya(titik awal garis). Keuntungan dari algoritma ini adalah tidak perlu menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan metode offset). [5] Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilainilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path. [6] 3. PEMBAHASAN 1. ALGORITMA DDA A. PENGERTIAN ALGORITMA DDA Algoritma DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai integer. DDA ( Digital Differential Analyzer) adalah garis yang membentang antara 2 titik, P1 dan P2. Dimana ke-2 titik ini membentuk sudut yang besarnya sangat bervariasi. Bekerja atas dasar penambahan nilai x dan nilai y. Dimana pada garis lurus, turunan pertama dari x dan y adalah kostanta. B. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA 1.



Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.



2.



Tentukan salah satu sebagai titik awal (x1, y1) dan titik akhir (x2, y2).



3.



Hitung dx = x2 – x1 dan dy = y2 – y1



4.



Tentukan step, yaitu jarak maksimum jumlah penambahan nilai x atau nilai y, dengan



ketentuan: a. bila |dx| > |dy| maka step = |dx| b. bila tidak, maka step = |dy| 5.



Hitung penambahan koordinat pixel dengan persamaan:



x_inc = dx / step y_inc = dy / step 6.



Koordinat selanjutnya (x+x_inc, y+y_inc)



7.



Plot pixel pada layar, nilai koordinat hasil perhitungan dibulatkan



8.



Ulangi step nomor 6 dan 7 untuk menentukan posisi pixel berikutnya sampai x = x1 atau y



= y1. Algoritma DDA merupakan salah satu algoritma menggambar cukup sederhana Bentuk garis: Cenderung mendatar Gradien bernilai 0 < m < 1 Pixel bertambah 1 pada sumbu x dan bertambah sebesar m pixel pada sumbu y



Cenderung tegak Gradien bernilai m > 1 Pixel bertambah 1 pada sumbu y dan bertambah sebesar 1/m pixel pada sumbu x



Miring 45° Gradien bernilai m = 1 Pixel bertambah 1 pada sumbu x dan bertambah sebesar 1 pixel pada sumbu y



C. KEUNTUNGAN DAN KERUGIAN ALGORITMA DDA Keuntungan dari algoritma Digital Differential Analyzer (DDA) adalah tidak perlu menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan metode off set) Kerugiannya dari algoritma Digital Differential Analyzer (DDA) adalah adanya akumulasi Round-off errors, sehingga garis akan melenceng dari garis lurus, selain itu operasi round-off juga menghabiskan waktu.



2. ALGORITMA BRESENHAM A.PENGERTIAN ALGORITMA BRESENHAM Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path. B. ATURAN BRESENHAM ·



Jika Pk bernilai positif (+),maka tambahkan hasilnya dengan B dan nilai x & y ditambah 1.



·



Jika Pk bernilai negatif (-), maka tambahkan hasilnya dengan A dan nilai x ditambah 1,



sedangkan y ditambah 0 (tetap). ·



Putaran dihentikan jika koordinat x dan y sudah mencapai batas akhir.



C. PRINSIP DARI ALGORITMA BRESENHAM 1.



Sumbu vertikal memperlihatkan posisi scan line.



2.



Sumbu horizontal memperlihatkan kolom pixel



3.



Pada tiap langkah, penentuan pixel selanjutnya didasari oleh parameter integer yang nilainya



proporsional dengan pengurangan antara vertical separations dari dua posisi piksel dari nilai actual.



Garis lurus dinyatakan dinyatakan dalam persamaan : y = mx + c è Persamaan(1) dimana : m : gradient dan c : konstanta.



Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c. m = (y2 – y1 ) / (x2-x1)



(2)



c = y1 / m* x1*



(3)



Operasi bilangan real berikutnya adalah menghitung nilai y dengan persamaan (1) Untuk mendapatkan koordinat piksel (x,y), untuk setiapnilai x, dari =x1 sampai x=x2, operasi inilah yang perlu dihindari,karena operasi ini memerlukan waktu operasi yang besar.



D. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA 1. 2.



Tentukan 2 titik yang akan dihubungkan dalam pembentuk garis. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0,Y0) dan titik lainnya



sebagai titik akhir (X1, Y1)



3.



hitung Dx, Dy, 2DX dan 2Dy-2Dy



4.



Hitung parameter P0= 2Dy – 2Dx



5.



Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,



·



bila pk