Algoritma Cohen Sutherland: Penjepitan Garis yang Efisien

Dalam dunia grafika komputer, menggambar garis pada layar seringkali memerlukan proses pemotongan (clipping) agar garis tersebut hanya terlihat di dalam area tampilan yang ditentukan. Salah satu algoritma yang paling fundamental dan efisien untuk tugas ini adalah Algoritma Cohen Sutherland. Algoritma ini membagi area layar menjadi sembilan region, yang memungkinkan pemotongan garis dilakukan dengan cepat dan efektif.

Bagaimana Algoritma Cohen Sutherland Bekerja?

Inti dari Algoritma Cohen Sutherland adalah mengklasifikasikan titik-titik ujung sebuah garis ke dalam salah satu dari sembilan region yang didefinisikan oleh batas-batas area kliping. Area kliping biasanya berbentuk persegi panjang. Sembilan region ini terbentuk dari persimpangan garis-garis tak terhingga yang sejajar dengan batas-batas persegi panjang kliping.

Setiap region diberi kode empat bit (disebut Outcode) yang merepresentasikan posisi relatif titik terhadap batas-batas kliping. Kode ini dibentuk sebagai berikut:

• Bit 0 (Paling Kanan): Di atas batas atas
• Bit 1: Di bawah batas atas
• Bit 2: Di sebelah kanan batas kanan
• Bit 3 (Paling Kiri): Di sebelah kiri batas kiri

Misalnya, sebuah titik berada di region kiri atas dan di atas batas atas, maka outcodenya akan memiliki bit 3 (kiri) dan bit 0 (atas) yang bernilai 1.

Proses Kliping Menggunakan Outcode

Algoritma ini kemudian mengaplikasikan aturan-aturan berdasarkan outcode dari kedua titik ujung garis (P1 dan P2) untuk menentukan apakah garis tersebut sepenuhnya di dalam, sepenuhnya di luar, atau sebagian melintasi area kliping.

Berikut adalah langkah-langkah utamanya:

1. Hitung Outcode: Hitung outcode untuk kedua titik ujung garis, P1(x1, y1) dan P2(x2, y2), relatif terhadap batas-batas area kliping (xmin, ymin, xmax, ymax).
2. Analisis Outcode:
   • Jika kedua outcode adalah 0000 (titik P1 dan P2 keduanya berada di dalam area kliping), maka seluruh garis berada di dalam area kliping dan dapat digambar sepenuhnya.
   • Jika hasil operasi AND bitwise dari kedua outcode tidak nol (misalnya, outcode1 & outcode2 != 0), ini berarti kedua titik berada di sisi yang sama dari setidaknya satu batas kliping (misalnya, keduanya di kiri, atau keduanya di atas). Dalam kasus ini, garis sepenuhnya berada di luar area kliping dan tidak perlu digambar.
   • Jika salah satu outcode adalah 0000 dan outcode yang lain tidak, atau jika hasil operasi AND bitwise adalah nol, maka garis mungkin memotong area kliping. Kita perlu melakukan kliping lebih lanjut.
3. Klip Garis yang Memotong: Jika garis tidak sepenuhnya di dalam atau di luar, pilih salah satu titik ujung yang berada di luar area kliping (misalnya, P1). Temukan titik potong garis dengan salah satu batas kliping.
   • Jika P1 di sebelah kiri (outcode1 & LEFT), cari titik potong dengan batas kiri.
   • Jika P1 di sebelah kanan (outcode1 & RIGHT), cari titik potong dengan batas kanan.
   • Jika P1 di bawah (outcode1 & BOTTOM), cari titik potong dengan batas bawah.
   • Jika P1 di atas (outcode1 & TOP), cari titik potong dengan batas atas.
   Setelah menemukan titik potong, perbarui koordinat titik ujung yang berada di luar tersebut dengan koordinat titik potong. Hitung kembali outcode untuk titik yang diperbarui ini.
4. Ulangi Proses: Ulangi langkah 2 dan 3 sampai kedua titik ujung garis berada di dalam area kliping atau garis dipastikan sepenuhnya di luar.

Keuntungan Algoritma Cohen Sutherland

Algoritma ini sangat disukai karena kesederhanaannya dan efisiensinya. Dengan menggunakan operasi bitwise untuk perbandingan outcode, algoritma ini dapat dengan cepat menyingkirkan garis yang sepenuhnya di luar area kliping, yang merupakan kasus yang umum terjadi. Penggunaan region dan outcode mengurangi kebutuhan akan perhitungan titik potong yang rumit untuk sebagian besar garis.

Meskipun ada algoritma kliping garis lain yang lebih canggih seperti Liang-Barsky, Cohen Sutherland tetap menjadi pilihan yang solid untuk banyak aplikasi grafis, terutama ketika area kliping berbentuk persegi panjang. Pemahaman mendalam tentang algoritma ini merupakan dasar penting bagi siapa saja yang terlibat dalam pengembangan grafika komputer.