1. PENDAHULUAN
Perkembangan kemampuan komputasi prosesor yang pesat telah membuat komputer desktop mempunyai kemampuan komputasi yang besar. Hal inimendorong perkembangan program aplikasi yang memerlukan komputasi yangbesar 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 pembuatangrafik dapat memberikan hasil yang optimal.
Algoritma midpoint merupakan algoritma pembuatan garis dan kurva dengan dasar operasi bilangan integer yang menonjolkan ciri kecepatan. Sehingga algoritma ini dapat dipakai sebagai algoritma pembuatan grafik yang menuntut kecepatan sebagai hal yang diutamakan. Pembahasan algoritma Midpoint dilakukan dengan mengasumsikan garis lurus dari kiri ke kanan,dan gadient antara 0 dan 1, sedangkan untuk lingkaran dengan mengasumsikan hanya sebagian lingkaran dengan sudut sebesar 45° , hal ini dilakukan untuk mempermudah penjelasan, sedangkan untuk kondisi yanglain dapat diderivasi dengan cara yang serupa. Untuk mendapatkan kinerja algoritma midpoint, dilakukan uji kecepatan komputasi dengan cara mengimplementasikan kedalam bahasa pemrograman C, dan melakukan perbandingan waktu komputasi dengan algoritma yang menggunakan dasar komputasi bilangan riel, maupun algoritma lain yang telah banyak dikenal seperti algoritma dda dan algoritma bressenham.
Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yang lebih sedikit dibandingkan dengan algoritma yang menggunakan operasi bilangan real. Implementasi ke dalam bahasa pemrograman C dari kedua macam algoritma diatas, menunjukkan bahwa waktu komputasi algoritma midpoint lebih cepat sebesar 8 kali pada pembuatan garis lurus, dan lebih cepat sebesar 15 kali pada penggambaran lingkaran, dibandingkan dengan waktu komputasi algoritma yang menggunakan dasar operasi bilangan
riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi algoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.
riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi algoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.
I. PENGERTIAN GARIS
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)
Pengertian garis menurut Leksikon Grafika adalah benda dua dimensi tipis memanjang. Sedangkan Lillian Gareth mendefinisikan garis sebagai sekumpulan titik yang bila dideretkan maka dimensi panjangnya akan tampak menonjol dan sosoknya disebut dengan garis.
Terbentuknya garis merupakan gerakan dari suatu titik yang membekaskan jejaknya sehingga terbentuk suatu goresan. Untuk menimbulkan bekas, biasa mempergunakan pensil, pena, kuas dan lain-lain. Bagi senirupa garis memiliki fungsi yang fundamental, sehingga diibaratkan jantungnya senirupa. Garis sering pula disebut dengan kontur, sebuah kata yang samar dan jarang dipergunakan. Pentingnya garis sebagai elemen senirupa, sudah terlihat sejak dahulu kala. Nenek moyang manusia jaman dulu, menggunakan garis ini sebagai media ekspresi senirupa di gua-gua. Mereka menggunakan garis ini untuk membentuk obyek-obyek ritual mereka. Sebagai contoh adalah lukisan di dinding gua Lascaux di Prancis, Leang-leang di Sulawesi, Altamira di Spanyol dan masih banyak lainnya. Selain berupa lukisan, nenek moyang manusia juga menggunakan garis sebagai media komunikasi, seperti huruf paku peninggalan bangsa Phoenicia
ATRIBUT PRIMITIF 2D. Yang merupakan atribut primitif adalah: titik dan garis. Ada
· GARIS LURUS
Garis lurus dinyatakan dinyatakan dalam persamaan :
y = mx + c (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 riel, 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 riel untuk menghitung gradient m dan konstanta c.
m = (y2 - y1 ) / (x2-x1) (2)
c = y1 ? m* x1* (3)
Operasi bilangan riel 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.
ALGORITMA GARIS BRESENHAM
Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan riel perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Algoritma garis Bresenham merupakan algoritma yang menentukan titik-titik dalam raster n-dimensi yang diplot untuk membentuk pendekatan dengan garis lurus antara dua titik yang diberikan. Hal ini biasanya digunakan untuk menggambar garis pada layar komputer, dengan menggunakan integer penambahan, pengurangan dan pergeseran bit, dalam arsitektur komputer standar. Algoritma bresenham adalah salah satu algoritma paling awal dikembangkan di bidang komputer grafis. Sebuah ekstensi kecil dengan algoritma asli juga berhubungan dengan lingkaran gambar.
Sedangkan algoritma seperti algoritma Wu juga sering digunakan dalam grafis komputer modern karena mereka dapat mendukung antialiasing, kecepatan dan kesederhanaan algoritma garis Bresenham. Algoritma ini digunakan dalam perangkat keras seperti gabungan dan dalam chip grafis dari kartu grafis modern. Hal ini juga dapat ditemukan di library banyak perangkat lunak grafis. Karena algoritma yang sangat sederhana, sering dilaksanakan baik di dalam firmware atau perangkat keras kartu grafis modern.
Ilustrasi hasil algoritma garis Bresenham's. (0,0) berada pada pojok kiri atas. Konvensi-konvensi umum yang koordinat pixel peningkatan arah bawah dan kanan (misalnya bahwa pixel di (1,1) secara langsung di atas pixel di (1,2)) dan bahwa pusat pixel yang telah integer koordinat tersebut digunakan. Titik-titik ujung garis adalah piksel pada (x0, y0) dan (x1, y1), dimana koordinat pertama dari pasangan adalah kolom dan koordinat kedua adalah baris.
Algoritma ini akan disajikan awalnya hanya untuk octant di mana segmen kebawah dan ke kanan (x0 y0 ≤ ≤ x1 dan y1), dan proyeksi horisontal x1 - x0 lebih panjang dari proyeksi vertikal y1 - y0. Dalam octant ini, untuk setiap kolom x antara x0 dan x1, ada tepat satu baris y (dihitung dengan algoritma) yang berisi garis pixel, sementara tiap baris antara y0 dan y1 dapat berisi piksel rasterized ganda.
algoritma Bresenham's memilih integer y sesuai dengan pusat pixel yang terdekat dengan y (pecahan) yang ideal hal yang sama untuk x; pada kolom berturut-turut y bisa tetap sama atau meningkat
1. Persamaan umum garis melalui endpoint diperoleh dari:
(y -y0)/(y1 - yo) = (x - x0)/(x1 -x0)
Karena kita tahu kolom, x, baris pixel , y, diberikan oleh pembulatan kuantitas ini ke integer terdekat:
y = ((y1 -yo)/(x1 - x0)). (x -x0) + y0
Kemiringan (y1 - y0) / (x1 - x0) tergantung pada titik akhir koordinat dan dapat precomputed, dan y ideal untuk nilai integer x berturut-turut dapat dihitung mulai dari y0 dengan berulang kali menambahkan slope.
Tujuan dari algoritma Bressenham ini adalah untuk menghindari pembulatan nilai seperti pada algoritma DDA.
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik di sebelah kiri sebagai titi awal, yaitu (x0,y0) dan titik lainnya sebgai titik akhir (x1,y1).
3. Hitung dx,dy,2dx dan 2dy-2dx.
4. Hitung parameter P0 = 2dy-dx
5. Untuk setiap Xk sepanjang jalur garis, dimulai dengan k=0,bila pk <0,>k+1, yk), dan Pk+1 = Pk+2dybila tidak, maka titik selanjutnya adalah (xk+1,yk+1), dan Pk+1 = Pk+2dy-2dx
6. Ulangi langkah no 5 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y1.
Sub Rutim Berssenham dalam CVoid line (int xa, ya, xb, yb, xEnd; flot x,y)
{
Int dx = abs(xb-xa), dy=abs(yb-ya);
Int p = 2*dy-dx;
Int twoDy = 2*dy,
twodyDx = 2*(dy-dx);
If (xa>xb)
{
X = xb;
Y = yb;
Xend = xa;
}
Else
{
X = xa;
Y = ya;
xEnd = xb;
}
SetPixel(x,y);
While (x
{
X++;
If (p<0)
P+ = twody;
Else
{
Y++;
P+ = twoDyDx;
}
SetPixel(x,y);
}
};
PROGRAM GARIS :
Daftar pustaka :
http://www.wahyukurniawan.info/blog/index.php?entry=entry090128-091028
