Grafika Komputer: Algoritma Clipping

Apa itu Clipping?

Dalam grafika komputer, Clipping (pemotongan) adalah proses menentukan bagian mana dari sebuah objek geometri (seperti titik, garis, atau poligon) yang berada di dalam area pandang (viewport) dan membuang sisanya. Ini sangat penting untuk optimasi kinerja—mengapa menghitung piksel untuk objek yang tidak bisa dilihat pengguna?

Viewport (Jendela Tampilan): Biasanya berupa persegi panjang yang dibatasi oleh $(X_{min}, Y_{min})$ dan $(X_{max}, Y_{max})$.

1. Clipping Garis Cohen-Sutherland

Algoritma paling populer untuk memotong garis. Algoritma ini menggunakan kode wilayah 4-bit (region code) untuk dengan cepat menentukan apakah garis sepenuhnya di dalam, di luar, atau perlu dipotong.

Logika (Outcodes)

Layar dibagi menjadi 9 wilayah menggunakan 4 bit: Atas, Bawah, Kanan, Kiri.

1001
(Atas-Kiri)

1000
(Atas)

1010
(Atas-Kanan)

0001
(Kiri)

0000
(Jendela)

0010
(Kanan)

0101
(Bawah-Kiri)

0100
(Bawah)

0110
(Bawah-Kanan)

Terima Langsung (Trivial Accept): Kedua ujung garis memiliki kode 0000.
Tolak Langsung (Trivial Reject): Kedua ujung berbagi bit yang sama (Operasi AND $\neq$ 0).
Lainnya: Potong garis pada batas viewport dan ulangi tes.

Implementasi JavaScript

const INSIDE = 0; // 0000
const LEFT = 1;   // 0001
const RIGHT = 2;  // 0010
const BOTTOM = 4; // 0100
const TOP = 8;    // 1000

function hitungKode(x, y) {
  let code = INSIDE;
  // Menentukan posisi bit
  if (x < xmin) code |= LEFT;
  else if (x > xmax) code |= RIGHT;
  if (y < ymin) code |= BOTTOM;
  else if (y > ymax) code |= TOP;
  return code;
}

Demo Interaktif

Klik tombol di bawah untuk membuat garis acak. Abu-abu adalah bagian asli yang dibuang, Hijau adalah hasil clipping yang diterima.

2. Clipping Garis Liang-Barsky

Algoritma yang lebih efisien dibandingkan Cohen-Sutherland karena menggunakan persamaan parametrik. Algoritma ini menghindari operasi pembagian berulang yang berat secara komputasi.

Matematika

Garis didefinisikan sebagai $P(t) = P_1 + t(P_2 - P_1)$ dimana $0 \le t \le 1$.

Kita menyelesaikan pertidaksamaan $p_k \cdot t \le q_k$.

Nilai $t_E$ (memasuki/entering) dan $t_L$ (meninggalkan/leaving) dihitung. Jika interval $[t_E, t_L]$ valid, garis digambar.

Logika Kode

function clipLineLB(x1, y1, x2, y2) {
  let t0 = 0, t1 = 1; // t awal & akhir
  let dx = x2 - x1, dy = y2 - y1;
  
  // Cek 4 batas (hitung p & q)
  // Update t0 (maksimum dari t masuk)
  // Update t1 (minimum dari t keluar)
  
  if(t0 > t1) return null; // Tolak
  
  // Hitung koordinat baru berdasarkan t
  nx1 = x1 + t0 * dx;
  ny1 = y1 + t0 * dy;
  // ... dst
}

Demo Interaktif

Garis Biru adalah hasil perhitungan parametrik.

3. Clipping Poligon Sutherland-Hodgman

Memotong poligon lebih rumit karena memotong poligon cembung (convex) dapat menghasilkan lebih banyak titik sudut (vertex) daripada aslinya. Algoritma ini memotong seluruh poligon terhadap satu tepi jendela pada satu waktu.

Konsep Pipeline

Output dari satu tahap pemotongan menjadi input untuk tahap berikutnya.

Input Poligon $\to$ Pemotong Kiri
$\to$ Pemotong Kanan
$\to$ Pemotong Bawah
$\to$ Pemotong Atas $\to$ Poligon Akhir

Aturan Perpotongan: 1. Dalam $\to$ Luar: Simpan titik Potong.
2. Luar $\to$ Dalam: Simpan titik Potong & Tujuan.
3. Dalam $\to$ Dalam: Simpan Tujuan.
4. Luar $\to$ Luar: Abaikan.

Langkah Algoritma

for each sisiClip di Window:
  outputList = []
  for each vertex di inputList:
    curr = vertex
    prev = previousVertex
    
    if (Dlm -> Dlm) tambah curr
    if (Dlm -> Luar) tambah potong
    if (Luar -> Dlm) tambah potong, curr
    if (Luar -> Luar) abaikan
    
  inputList = outputList

Demo Interaktif

Bentuk Abu-abu adalah poligon asli. Bentuk Pink adalah hasil setelah dipotong kotak hitam.