kebutulan saya kebagian pada materi tentangspesifikasi dan representasi benda 3D
SPESIFIKASI DAN REPRESENTASI BENDA 3D
Mulai sekarang,
kami tidak akan lagi membatasi diri untuk kubus, seperti yang kita lakukan dalam
bab sebelumnya, melainkan menerima input file yang mendefinisikan objek dibatasi
oleh poligon (yang mungkin berisi lubang, sebagaimana akan kita lihat dalam
Bagian 6.4). File-file masukan terdiri dari dua bagian: daftar simpul,
masing-masing dalam bentuk sejumlah titik positif diikuti oleh tiga bilangan
real, dunia koordinat yang dhuwur. Bagian kedua terdiri dari baris input dari
form
wajah:
diikuti dengan urutan nomor puncak, urutan masing-masing diikuti dengan titik (.). Setiap urutan tersebut menunjukkan poligon objek. Untuk poligon masing-masing, bila dilihat dari luar objek, urutan simpul harus berlawanan arah jarum jam. Orientasi ini juga harus berlaku untuk tiga simpul pertama dari setiap urutan, dengan kata lain, angka kedua dari urutan masing-masing harus menunjukkan suatu titik cembung. Sebagai contoh, file input berikut, katakanlah, letterL.dat, menggambarkan huruf L yang solid.
wajah:
diikuti dengan urutan nomor puncak, urutan masing-masing diikuti dengan titik (.). Setiap urutan tersebut menunjukkan poligon objek. Untuk poligon masing-masing, bila dilihat dari luar objek, urutan simpul harus berlawanan arah jarum jam. Orientasi ini juga harus berlaku untuk tiga simpul pertama dari setiap urutan, dengan kata lain, angka kedua dari urutan masing-masing harus menunjukkan suatu titik cembung. Sebagai contoh, file input berikut, katakanlah, letterL.dat, menggambarkan huruf L yang solid.
Gambar 6.2:
1 20 0 0
2 20 50 0
3 0 50 0
4 0 0 0
5 0 20 10
6 20 40 10
7 0 40 10
8 0 0 10
9 20 40 80
10 20 50 80
11 0 50 80
12 0 40 80
Wajah:
1 2 10 9 6 5.
3 4 8 7 12 11.
2 3 11 10.
7 6 9 12.
4 1 5 8.
9 10 11 12.
5 6 7 8.
1 4 3 2.
1 20 0 0
2 20 50 0
3 0 50 0
4 0 0 0
5 0 20 10
6 20 40 10
7 0 40 10
8 0 0 10
9 20 40 80
10 20 50 80
11 0 50 80
12 0 40 80
Wajah:
1 2 10 9 6 5.
3 4 8 7 12 11.
2 3 11 10.
7 6 9 12.
4 1 5 8.
9 10 11 12.
5 6 7 8.
1 4 3 2.
Baris pertama setelah Wajah
menentukan wajah depan. Kita mungkin telah menggunakan urutan titik-nomor
yang berbeda untuk wajah ini, seperti
10 9 6 5 1 2.
Namun, urutan berikut tidak benar:
2 1 5 6 9 10. (valid: searah jarum jam)
9 6 5 1 2 10. (valid: 6 tidak simpul cembung)
Meskipun urutan
3 4 8 7 12 11.
tampaknya searah jarum jam, itu benar-benar berlawanan arah jarum jam ketika wajah yang dimaksud adalah dilihat dari luar objek, yaitu, dari belakang. Sebagaimana akan kita lihat dalam Bagian 7.1, kita menggunakan fenomena ini dalam program kita untuk mendeteksi kembali wajah.
Pada bagian pertama dari file masukan, tidak diperlukan bahwa jumlah titik yang berurutan dan dalam urutan menaik. Sebagai contoh, file input berikut (mendefinisikan sebuah piramida mirip dengan yang di Mesir) juga diterima. Ini juga menunjukkan bahwa koordinat titik tidak perlu bilangan bulat:
10 0 -1.5 -1.5
30 0 1.5 -1.5
20 1.5 1.5 0
12 -1,5 1,5 0
5 0 0 3
wajah:
30 20 5.
20 12 5.
12 10 5.
10 30 5.
30 10 12 20.
Kami akan menggunakan ekstensi. Dat untuk berkas-berkas masukan.
10 9 6 5 1 2.
Namun, urutan berikut tidak benar:
2 1 5 6 9 10. (valid: searah jarum jam)
9 6 5 1 2 10. (valid: 6 tidak simpul cembung)
Meskipun urutan
3 4 8 7 12 11.
tampaknya searah jarum jam, itu benar-benar berlawanan arah jarum jam ketika wajah yang dimaksud adalah dilihat dari luar objek, yaitu, dari belakang. Sebagaimana akan kita lihat dalam Bagian 7.1, kita menggunakan fenomena ini dalam program kita untuk mendeteksi kembali wajah.
Pada bagian pertama dari file masukan, tidak diperlukan bahwa jumlah titik yang berurutan dan dalam urutan menaik. Sebagai contoh, file input berikut (mendefinisikan sebuah piramida mirip dengan yang di Mesir) juga diterima. Ini juga menunjukkan bahwa koordinat titik tidak perlu bilangan bulat:
10 0 -1.5 -1.5
30 0 1.5 -1.5
20 1.5 1.5 0
12 -1,5 1,5 0
5 0 0 3
wajah:
30 20 5.
20 12 5.
12 10 5.
10 30 5.
30 10 12 20.
Kami akan menggunakan ekstensi. Dat untuk berkas-berkas masukan.
6.4 LUBANG DAN SEGMEN GARIS INVISIBLE
Cara di atas menentukan wajah batas obyek tidak bekerja untuk poligon yang mengandung lubang. Sebagai contoh, perhatikan huruf yang solid A dari Gambar 6.13, wajah depan yang bukan poligon yang tepat karena ada lubang berbentuk segitiga di dalamnya. Hal yang sama berlaku untuk wajah (identik) di bagian belakang. Setiap simpul i dari wajah depan terhubung dengan simpul i + 10 dari wajah kembali (1 ≤ i ≤ 10).
Cara di atas menentukan wajah batas obyek tidak bekerja untuk poligon yang mengandung lubang. Sebagai contoh, perhatikan huruf yang solid A dari Gambar 6.13, wajah depan yang bukan poligon yang tepat karena ada lubang berbentuk segitiga di dalamnya. Hal yang sama berlaku untuk wajah (identik) di bagian belakang. Setiap simpul i dari wajah depan terhubung dengan simpul i + 10 dari wajah kembali (1 ≤ i ≤ 10).
Kita dapat mengubah wajah
depan menjadi poligon dengan memperkenalkan celah yang sangat sempit,
katakanlah, antara simpul 7 dan 10, seperti yang ditunjukkan pada Gambar
6.14. Setelah melakukan ini, kita bisa mencoba menentukannya poligon baru sebagai
1 2 3 4 5 6 7 10 9 8 10 7.
Catatan bahwa ini memerlukan kesenjangan (7, 10) untuk memiliki lebar nol, sehingga hanya ada satu titik (7) di bagian atas. Di sisi lain, hanya kesenjangan yang nyata dengan jelas bahwa jumlah titik (10, 9, 8) terjadi dalam urutan pada baris masukan di atas: cukup ikuti simpul pada Gambar 6.14, mulai dari titik 1.
1 2 3 4 5 6 7 10 9 8 10 7.
Catatan bahwa ini memerlukan kesenjangan (7, 10) untuk memiliki lebar nol, sehingga hanya ada satu titik (7) di bagian atas. Di sisi lain, hanya kesenjangan yang nyata dengan jelas bahwa jumlah titik (10, 9, 8) terjadi dalam urutan pada baris masukan di atas: cukup ikuti simpul pada Gambar 6.14, mulai dari titik 1.
Jika kita
benar-benar ditentukan wajah depan dengan cara di atas, garis (7, 10) akan
dianggap sebagai tepi poligon dan karena itu muncul dalam hasil kita. Ini jelas
tidak diinginkan. Untuk mencegah hal ini terjadi, kita mengadopsi konvensi
penulisan tanda minus di depan simpul kedua pasangan, menunjukkan bahwa
pasangan ini menunjukkan suatu segmen garis yang tidak bisa ditarik. Kami
melakukan hal ini dengan pasangan terurut (7, 10) dan (10, 7) pada baris
masukan di atas, menulis (7, -10) dan (10, -7), sehingga kita menggunakan baris
input berikut bukan di atas satu:
1 2 3 4 5 6 7 -10 9 8 10 -7.
Surat padat A dari Gambar 6.13 Oleh karena itu diperoleh dengan menggunakan file input berikut, dimana tanda minus ekstra terjadi dalam dua baris pertama setelah Wajah kata:
1 0 -30 0
2 0 -20 0
3 0 -16 8
4 0 16 8
5 0 20 0
6 0 30 0
7 0 0 60
8 0 -12 16
9 0 12 16
10 0 0 40
11 -10 -30 0
12 -10 -20 0
13 -10 -16 8
14 -10 16 8
15 -10 20 0
16 -10 30 0
17 -10 0 60
18 -10 -12 16
19 -10 12 16
20 -10 0 40
Wajah:
1 2 3 4 5 6 7 -10 9 8 10 -7.
11 17 -20 18 19 20 -17 16 15 14 13 12.
2 12 13 3.
3 13 14 4.
15 5 4 14.
8 9 19 18.
8 18 20 10.
19 9 10 20.
6 16 17 7.
11 1 7 17.
11 12 2 1.
15 16 6 5.
(Catatan bahwa penggunaan tanda minus hanya berlaku untuk nomor titik di bagian kedua dari file input. Pada bagian pertama, minus tanda hanya dapat terjadi pada nilai-nilai koordinat, di mana mereka memiliki arti yang biasa mereka.)
Menerapkan ide ini sangat sederhana. Sebagai contoh, karena tanda minus yang mendahului jumlah vertex 10 di
... 7 -10 ...
kami tidak menyimpan segmen garis (7, 10) dalam struktur data yang akan dibahas dalam Bagian 6.5. Dalam hal lain, kita mengabaikan tanda-tanda minus. Oleh karena itu himpunan segitiga yang dihasilkan dari set lengkap atas data input (untuk huruf padat A) adalah sama seperti ketika tidak ada tanda minus di depan setiap nomor simpul.
Selain untuk lubang, kita juga dapat menggunakan tanda minus untuk pendekatan tersebut untuk permukaan lengkung, seperti yang dibahas dalam Bagian E.5 Lampiran E.
1 2 3 4 5 6 7 -10 9 8 10 -7.
Surat padat A dari Gambar 6.13 Oleh karena itu diperoleh dengan menggunakan file input berikut, dimana tanda minus ekstra terjadi dalam dua baris pertama setelah Wajah kata:
1 0 -30 0
2 0 -20 0
3 0 -16 8
4 0 16 8
5 0 20 0
6 0 30 0
7 0 0 60
8 0 -12 16
9 0 12 16
10 0 0 40
11 -10 -30 0
12 -10 -20 0
13 -10 -16 8
14 -10 16 8
15 -10 20 0
16 -10 30 0
17 -10 0 60
18 -10 -12 16
19 -10 12 16
20 -10 0 40
Wajah:
1 2 3 4 5 6 7 -10 9 8 10 -7.
11 17 -20 18 19 20 -17 16 15 14 13 12.
2 12 13 3.
3 13 14 4.
15 5 4 14.
8 9 19 18.
8 18 20 10.
19 9 10 20.
6 16 17 7.
11 1 7 17.
11 12 2 1.
15 16 6 5.
(Catatan bahwa penggunaan tanda minus hanya berlaku untuk nomor titik di bagian kedua dari file input. Pada bagian pertama, minus tanda hanya dapat terjadi pada nilai-nilai koordinat, di mana mereka memiliki arti yang biasa mereka.)
Menerapkan ide ini sangat sederhana. Sebagai contoh, karena tanda minus yang mendahului jumlah vertex 10 di
... 7 -10 ...
kami tidak menyimpan segmen garis (7, 10) dalam struktur data yang akan dibahas dalam Bagian 6.5. Dalam hal lain, kita mengabaikan tanda-tanda minus. Oleh karena itu himpunan segitiga yang dihasilkan dari set lengkap atas data input (untuk huruf padat A) adalah sama seperti ketika tidak ada tanda minus di depan setiap nomor simpul.
Selain untuk lubang, kita juga dapat menggunakan tanda minus untuk pendekatan tersebut untuk permukaan lengkung, seperti yang dibahas dalam Bagian E.5 Lampiran E.
6.5 INDIVIDU DAN WAJAH SEGMEN GARIS
Meskipun kami biasanya menggambarkan poligon yang batas wajah benda padat, kadang-kadang kita ingin menarik sangat tipis (terbatas) pesawat, di sini juga disebut wajah.
Contohnya adalah lembar kertas dan sebuah kubus yang terbuat dari bahan yang sangat tipis, yang muka atas dihapus, seperti yang ditunjukkan pada Gambar 6.15.
Meskipun kami biasanya menggambarkan poligon yang batas wajah benda padat, kadang-kadang kita ingin menarik sangat tipis (terbatas) pesawat, di sini juga disebut wajah.
Contohnya adalah lembar kertas dan sebuah kubus yang terbuat dari bahan yang sangat tipis, yang muka atas dihapus, seperti yang ditunjukkan pada Gambar 6.15.
Gambar 6.15: Sebuah kubus
berongga
Karena wajah seperti memiliki dua sisi terlihat, kita tentukan wajah masing-masing dua kali: berlawanan untuk sisi kita saat ini melihat dan searah jarum jam untuk sisi yang saat ini tak terlihat tetapi mungkin menjadi terlihat ketika kita mengubah sudut pandang. Misalnya, wajah depan kubus Gambar 6,15 ditentukan dua kali pada file input:
1 2 3 4.
4 3 2 1.
Meskipun pengguna memasok poligon dalam file input sebagai wajah objek, kita berurusan terutama dengan segmen garis, disebut sebagai PQ di bagian sebelumnya. Selain poligon dan segitiga yang dihasilkan dari mereka, kita juga menyimpan tepi poligon sebagai segmen garis. Diharapkan juga untuk dapat menarik segmen garis yang tidak tepi poligon.
Contoh-contoh 'longgar', segmen garis individu adalah sumbu sistem koordinat 3D. Terkadang kita ingin mendefinisikan tepi poligon sebagai segmen garis individu, untuk mencegah poligon tersebut dari menutupi segmen garis lainnya, menampilkan objek sebagai kawat-frame model. Contoh dari hal ini ditunjukkan pada Gambar 6.16. Di sini kita memiliki pas piramida padat menjadi kubus. Jelas, piramida tidak akan terlihat jika kubus adalah padat; maka kami lebih memilih yang terakhir yang akan ditampilkan sebagai model kawat-frame. Untuk memberikan file input untuk piramida ini, kita mulai dengan menetapkan nomor puncak.
Karena wajah seperti memiliki dua sisi terlihat, kita tentukan wajah masing-masing dua kali: berlawanan untuk sisi kita saat ini melihat dan searah jarum jam untuk sisi yang saat ini tak terlihat tetapi mungkin menjadi terlihat ketika kita mengubah sudut pandang. Misalnya, wajah depan kubus Gambar 6,15 ditentukan dua kali pada file input:
1 2 3 4.
4 3 2 1.
Meskipun pengguna memasok poligon dalam file input sebagai wajah objek, kita berurusan terutama dengan segmen garis, disebut sebagai PQ di bagian sebelumnya. Selain poligon dan segitiga yang dihasilkan dari mereka, kita juga menyimpan tepi poligon sebagai segmen garis. Diharapkan juga untuk dapat menarik segmen garis yang tidak tepi poligon.
Contoh-contoh 'longgar', segmen garis individu adalah sumbu sistem koordinat 3D. Terkadang kita ingin mendefinisikan tepi poligon sebagai segmen garis individu, untuk mencegah poligon tersebut dari menutupi segmen garis lainnya, menampilkan objek sebagai kawat-frame model. Contoh dari hal ini ditunjukkan pada Gambar 6.16. Di sini kita memiliki pas piramida padat menjadi kubus. Jelas, piramida tidak akan terlihat jika kubus adalah padat; maka kami lebih memilih yang terakhir yang akan ditampilkan sebagai model kawat-frame. Untuk memberikan file input untuk piramida ini, kita mulai dengan menetapkan nomor puncak.
Angka-angka ini terjadi pada titik input file berikut:
1 0 0 0
2 2 0 0
3 2 2 0
4 0 2 0
5 0 0 2
6 2 0 2
7 2 2 2
8 0 2 2
9 1 1 2
wajah:
1 4 3 2.
1 2 9.
2 3 9.
3 4 9.
4 1 9.
1 5.
2 6.
3 7.
4 8.
5 6.
6 7.
7 8.
8 5.
Setelah Wajah kata, kita mulai dengan wajah bagian bawah persegi dan empat wajah segitiga piramida. Setelah ini, empat vertikal dan empat sisi kubus horisontal mengikuti, masing-masing ditentukan oleh dua titik akhir. Ini mengikuti bahwa kata Faces dalam file masukan kami tidak boleh dipahami secara sangat harfiah: bagian ini dapat mencakup Wajah pasang nomor titik, yang tidak menghadapi sama sekali tetapi segmen garis belum tentu milik wajah.
Karena segmen garis dapat terjadi tidak hanya sebagai tepi wajah tetapi juga secara individu, kita harus merancang dan mengimplementasikan struktur data khusus untuk menyimpan mereka dalam program kami. Ini juga memberikan kita kesempatan untuk menyimpan mereka hanya sekali. Misalnya, tepi 3-9 dari piramida Gambar 6.17 adalah bagian dari wajah 2-3-9 dan 3-4-9, tetapi akan tidak efisien untuk menarik dua kali. Dengan menggunakan struktur data khusus untuk segmen garis, kita dapat memastikan bahwa tepi ini disimpan hanya sekali.
Struktur data kami untuk segmen garis akan didasarkan pada sebuah array dari array.
1 0 0 0
2 2 0 0
3 2 2 0
4 0 2 0
5 0 0 2
6 2 0 2
7 2 2 2
8 0 2 2
9 1 1 2
wajah:
1 4 3 2.
1 2 9.
2 3 9.
3 4 9.
4 1 9.
1 5.
2 6.
3 7.
4 8.
5 6.
6 7.
7 8.
8 5.
Setelah Wajah kata, kita mulai dengan wajah bagian bawah persegi dan empat wajah segitiga piramida. Setelah ini, empat vertikal dan empat sisi kubus horisontal mengikuti, masing-masing ditentukan oleh dua titik akhir. Ini mengikuti bahwa kata Faces dalam file masukan kami tidak boleh dipahami secara sangat harfiah: bagian ini dapat mencakup Wajah pasang nomor titik, yang tidak menghadapi sama sekali tetapi segmen garis belum tentu milik wajah.
Karena segmen garis dapat terjadi tidak hanya sebagai tepi wajah tetapi juga secara individu, kita harus merancang dan mengimplementasikan struktur data khusus untuk menyimpan mereka dalam program kami. Ini juga memberikan kita kesempatan untuk menyimpan mereka hanya sekali. Misalnya, tepi 3-9 dari piramida Gambar 6.17 adalah bagian dari wajah 2-3-9 dan 3-4-9, tetapi akan tidak efisien untuk menarik dua kali. Dengan menggunakan struktur data khusus untuk segmen garis, kita dapat memastikan bahwa tepi ini disimpan hanya sekali.
Struktur data kami untuk segmen garis akan didasarkan pada sebuah array dari array.
Elemen array
menghubungkan [i] yang mengacu ke array berisi bilangan bulat j menyiratkan
bahwa ada segmen garis (i, j) yang akan ditarik. Dengan mensyaratkan bahwa saya
kurang dari j, kami memastikan bahwa setiap segmen garis disimpan hanya sekali.
Sebagai contoh, menghubungkan [1] merujuk pada array yang berisi bilangan bulat
2, 4, 9 dan 5. Hal ini menunjukkan bahwa segmen baris berikut mulai pada titik
1 (masing-masing berujung pada simpul yang memiliki jumlah yang lebih tinggi
dari 1):, 1-2 1-4, 1-9 dan 1-5, yang sesuai dengan Gambar 6.17. Elemen
berikutnya, menghubungkan [2] mengacu pada tiga nomor titik, 3, 9 dan 6.
Meskipun, selain 2-3, 2-9 dan 2-6, ada juga segmen garis 2-1 (lihat Gambar
6.17), ini tidak termasuk di sini karena 2 lebih besar dari 1 dan segmen ini
telah disimpan sebagai garis segmen 1-2. Anda mungkin bertanya-tanya mengapa
pada Gambar 6.18 ada kotak hanya yang memberikan ruang untuk paling banyak
empat nomor verteks. Sebenarnya, ukuran kotak-kotak ini akan selalu kelipatan
dari beberapa ukuran chunk, berikut sewenang-wenang dipilih sebagai 4. Dengan
kata lain, jika ada segmen garis lima (i, j) dengan i sama dan semua dengan i
kurang dari j, ukuran kotak akan meningkat dari 4 sampai 8 dan sebagainya.
Sejak meningkatkan ukuran kotak memerlukan realokasi memori dan menyalin, kita
tidak harus memilih ukuran potongan terlalu kecil. Di sisi lain, semakin besar
ukuran chunk, semakin banyak memori akan sia-sia, karena mereka biasanya tidak
akan terisi penuh. Untuk menunjukkan berapa banyak nomor titik yang benar-benar
disimpan dalam setiap kotak, kita menggunakan yang lain array, nConnect,
seperti yang ditunjukkan pada Gambar 6.18 di sebelah kanan. Sebagai contoh,
nConnect [1] = 4 karena menghubungkan [1] merujuk pada empat nomor verteks.
Tidak ada komentar:
Posting Komentar