Tugas Grafik Komputer 2
Kelompok 1
ALFIAN DHIMAS (50414808)
A. Pengertian VSD (Visible - Surface Determination)
Kelompok 1
ALFIAN DHIMAS (50414808)
BAYU YUNIANTO P (52414808)
EDHO PRATAMA BISMA A (52412355)
RIDWAN HILMY M (59414315)
M SOFYAN PRIYATNA (57414018)
FRENGKY ANGGIAT B (54414386)
A. Pengertian VSD (Visible - Surface Determination)
Visible-Surface
Determination atau yang sering disebut dengan Hidden Surface Removal adalah
suatu algoritma yang digunakan untuk menghilangkan penampilan bagian yang
tertutup oleh objek yang didepannya. Apabila ada dua bidang yang berpotongan,
apabila ditampilkan biasa tanpa menggunakan algoritma Visible Surface
Determination maka bagian yang berpotongan itu akan tidak kelihatan, oleh
karena bidang yang satu ditutupi oleh bagian yang lain tanpa memotong. Oleh
karena itu untuk menampilkan bidang perpotongan, diperlukan Algoritma Hidden
Surface Removal.
B. Kelas
kelas pada algoritma VSD
Kelas-kelas
pada Algoritma VSD
Terdapat beberapa cara atau metode untuk mendeteksi suatu permukaan yang terlihat ini, yaitu :
- Conservative
- Image Precision
- Object Precision
C. Pengertian
Object-Precision
Pendekatan historis pertama
• Roberts '63 - penghapusan garis
tersembunyi
- bandingkan setiap tepi dengan
setiap objek –
Menghilangkan tepi tak terlihat
atau bagian tepi.
• Kompleksitas: lebih buruk dari O
(n2) masing-masing
D.
Pengertian
Binary Space Partitioning
Dalam
ilmu komputer, binary space partitioning (BSP) adalah metode untuk membagi
secara rekursif ruang menjadi set cembung oleh hyperplanes. Subdivisi ini
memunculkan representasi objek di dalam ruang dengan menggunakan struktur data
pohon yang dikenal sebagai pohon BSP.
Partisi
ruang biner dikembangkan dalam konteks grafis komputer 3D, dimana struktur
pohon BSP memungkinkan informasi spasial tentang objek dalam adegan yang
berguna dalam rendering. Aplikasi lainnya termasuk melakukan operasi geometris
dengan bentuk (geometri solid konstruktif) di CAD, deteksi tabrakan pada
robotika dan video game 3-D.
Partisi
ruang biner adalah proses generik membagi secara rekursif menjadi dua adegan
sampai partisi memenuhi satu atau lebih persyaratan. Hal ini dapat dilihat
sebagai generalisasi struktur pohon spasial lainnya seperti pohon k-d dan
quadtrees, satu di mana hyperplanes yang memisahkan ruang mungkin memiliki
orientasi, daripada diselaraskan dengan sumbu koordinat seperti pada pohon k-d
atau quadtrees. Bila digunakan dalam grafis komputer untuk membuat adegan yang
terdiri dari poligon planar, bidang partisi seringkali (tapi tidak selalu)
dipilih bertepatan dengan bidang yang didefinisikan oleh poligon di tempat
kejadian.
Pilihan
spesifik dari bidang partisi dan kriteria untuk mengakhiri proses partisi
bervariasi tergantung pada tujuan pohon BSP. Misalnya, dalam rendering grafis
komputer, adegan dibagi sampai setiap simpul pohon BSP hanya berisi poligon
yang dapat dirender dalam urutan yang sewenang-wenang. Ketika pemusnahan
kembali digunakan, masing-masing node mengandung satu set poligon cembung,
sedangkan saat merender poligon dua sisi, setiap simpul pohon BSP hanya berisi
poligon dalam satu bidang. Dalam deteksi tabrakan atau penelusuran sinar,
sebuah adegan dapat dibagi menjadi primitif dimana tes persilangan tabrakan
atau sinar lurus.
Partisi
ruang biner muncul dari grafis komputer yang perlu dengan cepat menggambar tiga
dimensi yang terdiri dari poligon. Cara sederhana untuk menggambar adegan
seperti itu adalah algoritma pelukis, yang menghasilkan poligon sesuai jarak
dari penampil, kembali ke depan, melukis di atas latar belakang dan poligon
sebelumnya dengan masing-masing objek yang lebih dekat. Pendekatan ini memiliki
dua kekurangan: waktu yang dibutuhkan untuk mengurutkan poligon di belakang ke
depan dan kemungkinan kesalahan dalam poligon tumpang tindih. Fuchs dan rekan
penulis menunjukkan bahwa membangun pohon BSP memecahkan kedua masalah ini
dengan menyediakan metode penyortir poligon yang cepat sehubungan dengan sudut
pandang tertentu (linear dalam jumlah poligon di tempat kejadian) dan dengan
membagi poligon yang tumpang tindih ke Hindari kesalahan yang bisa terjadi
dengan algoritma pelukis. Kerugian dari partisi ruang biner adalah menghasilkan
pohon BSP dapat memakan waktu. Biasanya, oleh karena itu dilakukan sekali pada
geometri statis, sebagai langkah pra-perhitungan, sebelum melakukan rendering
atau operasi realtime lainnya di tempat kejadian. Biaya membangun pohon BSP
membuat sulit dan tidak efisien untuk secara langsung menerapkan benda bergerak
ke pohon.
Pohon
BSP sering digunakan oleh video game 3D, terutama game dengan genre penembak
orang pertama dan orang-orang dengan lingkungan dalam ruangan. Mesin permainan
yang memanfaatkan pohon BSP termasuk mesin Doom (mungkin game paling awal yang
menggunakan struktur data BSP adalah Doom), mesin Quake dan keturunannya. Dalam
permainan video, pohon BSP yang berisi geometri statis dari sebuah adegan
sering digunakan bersamaan dengan penyangga Z, untuk menggabungkan benda bergerak
dengan benar seperti pintu dan karakter ke pemandangan latar belakang.
Sementara partisi ruang biner menyediakan cara mudah untuk menyimpan dan
mengambil informasi spasial tentang poligon dalam sebuah adegan, namun tidak
memecahkan masalah penentuan permukaan yang terlihat.
Penggunaan
pohon BSP secara kanonik adalah untuk rendering poligon (yaitu dua sisi, yaitu
tanpa penghilangan muka) dengan algoritma pelukis. Setiap poligon ditunjuk
dengan sisi depan dan sisi belakang yang bisa dipilih semena-mena dan hanya
mempengaruhi struktur pohon tapi bukan hasil yang dibutuhkan. Pohon seperti itu
dibangun dari daftar unsorted semua poligon dalam sebuah adegan. Algoritma
rekursif untuk konstruksi pohon BSP dari daftar poligon tersebut adalah:
1. Pilih
poligon P dari daftar.
2. Buat
node N di pohon BSP, dan tambahkan P ke daftar poligon pada simpul tersebut.
Untuk
poligon satu sama lain dalam daftar :
Jika
poligon itu seluruhnya berada di depan bidang yang berisi P, pindahkan poligon
itu ke daftar nodus di depan P.
Jika
poligon itu seluruhnya berada di belakang bidang yang berisi P, pindahkan
poligon itu ke daftar simpul di belakang P.
Jika
poligon itu berpotongan dengan bidang yang mengandung P, pisahkan menjadi dua poligon dan pindahkan ke masing-masing daftar poligon di belakang dan di depan
P.
Jika
poligon itu terletak pada bidang yang mengandung P, tambahkan ke daftar poligon
pada simpul N.
3. Terapkan
algoritma ini ke daftar poligon di depan P.
4. Terapkan
algoritma ini ke daftar poligon di belakang P.
Diagram
berikut menggambarkan penggunaan algoritma ini dalam mengubah daftar garis atau
poligon menjadi pohon BSP. Pada masing-masing dari delapan langkah (i.-viii.),
Algoritma di atas diterapkan pada daftar baris, dan satu simpul baru
ditambahkan ke pohon.
Mulailah
dengan daftar garis, (atau dalam 3-D, poligon) yang membentuk pemandangan.
Dalam diagram pohon, daftar dilambangkan dengan persegi panjang bulat dan
simpul di pohon BSP oleh lingkaran. Dalam diagram spasial garis, arah yang
dipilih menjadi 'depan' garis dilambangkan dengan panah.
Langkah
(i)
Mengikuti
langkah-langkah dari algoritma di atas,
Kami
memilih sebuah garis, A, dari daftar dan, ...
...
menambahkannya ke sebuah simpul.
Kita
membagi garis yang tersisa dalam daftar ke dalam daftar di depan A (yaitu B2,
C2, D2), dan yang tertinggal (B1, C1, D1).
Kami
pertama memproses baris di depan A (dalam langkah ii-v), ...
...
diikuti oleh orang-orang di belakang (dalam langkah-langkah vi-vii).
Langkah
(ii)
Kami
sekarang menerapkan algoritma ke daftar garis di depan A (mengandung B2, C2,
D2). Kita memilih sebuah garis, B2, menambahkannya ke sebuah simpul dan membagi
sisa daftar ke garis-garis yang ada di depan B2 (D2), dan yang ada di
belakangnya (C2, D3)
Langkah
(iii)
Pilih
garis, D2, dari daftar garis di depan B2. Ini adalah satu-satunya garis dalam
daftar, jadi setelah menambahkannya ke sebuah simpul, tidak perlu dilakukan
lebih jauh lagi.
Langkah
(iv)
Kita
selesai dengan garis di depan B2, jadi perhatikan garis di belakang B2 (C2 dan
D3). Pilih salah satu dari ini (C2), tambahkan ke simpul, dan letakkan baris
lainnya dalam daftar (D3) ke dalam daftar garis di depan C2.
Langkah
(v)
Sekarang
lihat daftar garis di depan C2. Hanya ada satu baris (D3), jadi tambahkan ini
ke simpul dan lanjutkan.
Langkah
(vi)
Kita
sekarang telah menambahkan semua garis di depan A ke pohon BSP, jadi kita
sekarang mulai pada daftar garis di belakang A. Memilih garis (B1) dari daftar
ini, kita menambahkan B1 ke sebuah simpul dan membagi sisa dari Daftar ke garis
di depan B1 (yaitu D1), dan garis di belakang B1 (yaitu C1).
Langkah
(vii)
Pengolahan
daftar baris pertama di depan B1, D1 adalah satu-satunya garis dalam daftar
ini, jadi tambahkan ini ke simpul dan lanjutkan.
Langkah
(viii)
Melihat
selanjutnya daftar garis di belakang B1, satu-satunya garis dalam daftar ini
adalah C1, jadi tambahkan ini ke simpul, dan pohon BSP sudah selesai.
E. Contoh Kasus Binary Space
Partitioning
Menggunakan
BSP untuk membuat adegan
Meningkatkan
kinerja rendering adalah salah satu alasan pohon BSP digunakan. Pohon BSP pada
dasarnya mengungguli precalculation yang luas untuk algoritma back to front
painters atau algoritma backline back to back. Pohon itu bisa dilalui dalam waktu
linier dari sudut pandang yang sewenang-wenang.
Karena
algoritma pelukis bekerja dengan menggambar poligon terjauh dari mata terlebih
dahulu, kode berikut akan terulang kembali ke bagian bawah pohon dan menarik
poligon. Saat rekursi terhindar, poligon mendekati mata ditarik jauh dari
poligon. Karena pohon BSP allready memisahkan poligon menjadi potongan sepele,
bagian tersulit dari algoritma pelukis sudah bisa dipecahkan.
Kode
untuk kembali ke traversal pohon depan.
traverse_tree(bsp_tree* tree,point eye)
{
location = tree->find_location(eye);
if(tree->empty())
return;
if(location > 0) // if eye infront of location
{
traverse_tree(tree->back,eye);
display(tree->polygon_list);
traverse_tree(tree->front,eye);
}
else if(location < 0) // eye
behind location
{
traverse_tree(tree->front,eye);
display(tree->polygon_list);
travers_tree(tree->back,eye);
}
else // eye coincidental with
partition hyperplane
{
traverse_tree(tree->front,eye);
traverse_tree(tree->back,eye);
}
}
Menurut, pohon BSP juga
dapat digunakan untuk membuat adegan dengan front to back traversal pohon
menggunakan algoritma pemindaian scanline. Sebuah topeng tulis bisa digunakan
untuk mencegah sebuah pixel ditulis lebih dari satu kali. Dalam sebuah adegan
dengan banyak sumber cahaya, algoritma pelukis akan mengevaluasi piksel yang
sama lebih dari satu kali. Untuk melintasi pohon dari depan ke belakang, cukup
ubah urutan rekursi pada kode di atas.
Menggunakan BSP untuk Beberapa
Sumber Cahaya
Pohon SVBSP dapat
dengan mudah diperluas ke beberapa sumber cahaya. Pada dasarnya, buatlah pohon
SVBSP dengan sumber cahaya pertama. Simpan semua fragmen poligon pada simpul
pohon BSP yang sesuai yang menentukan pemandangan. Setelah semua poligon telah
dipartisi, buanglah pohon SVBSP saat ini. Selanjutnya, buat pohon SVBSP dari
sumber cahaya berikutnya. Saring fragmen poligon ke pohon baru ini. Ulangi
sampai tidak ada lagi sumber cahaya dan ada SVBSP terakhir yang siap untuk
generasi bayangan.
Chin dan Feiner
memperingatkan bahwa beberapa sumber cahaya bisa menghasilkan pohon yang sangat
besar dengan banyak poligon split. Mereka merekomendasikan agar sumber cahaya
diproses agar menyebabkan fragmentasi paling sedikit. Salah satu caranya adalah
mengolah sumber cahaya dalam rangka meningkatkan jumlah poligon yang
menghadapinya. Sebagai alternatif, proses sumber cahaya statis sumber pertama
dan dinamis terakhir.
Semua kode sumber dari
Near Real-Time shadow Generation Menggunakan Pohon BSP oleh Chin dan Feiner.
The shadowGenerator menciptakan volume bayangan dengan menerapkan fungsi
rekursif menentukan. Membentuk semua poligon pemandangan. DefineShadow
menyaring poligon dari pohon SVBSP yang membelahnya saat diperlukan dan
menambahkan volume bayangan fragmen yang menyala ke pohon SVBSP.
0 komentar:
Posting Komentar