Memandangkan skrin paparan LCD boleh dilihat sebagai matriks unsur diskret (piksel), setiap satunya boleh diterangi latar, tidak mungkin untuk melukis garisan secara langsung dari satu titik ke titik yang lain. Proses pengesanan piksel cara yang paling baik menghampiri segmen tertentu dipanggil penguraian raster. Apabila digabungkan dengan proses pemaparan baris demi baris imej, ia dikenali sebagai penukaran imbasan raster. Untuk mendatar, menegak dan condong pada sudut 45°. segmen, pilihan elemen raster adalah jelas. Dengan mana-mana orientasi lain, adalah lebih sukar untuk memilih piksel yang diperlukan, seperti yang ditunjukkan dalam Rajah 1.
Rajah 1. Penguraian raster bagi segmen garisan.
Keperluan umum untuk algoritma untuk melukis segmen adalah seperti berikut: Segmen mesti kelihatan lurus, bermula dan berakhir pada titik tertentu, kecerahan sepanjang segmen mestilah malar dan bebas daripada panjang dan cerun, dan mesti dilukis dengan cepat.
Kecerahan malar di sepanjang keseluruhan segmen dicapai hanya apabila melukis garisan mendatar, menegak dan condong pada sudut 45°. Untuk semua orientasi lain, rasterisasi akan menghasilkan ketidaksamaan kecerahan, seperti ditunjukkan dalam Rajah. 1.
Kebanyakan algoritma lukisan garisan digunakan algoritma langkah demi langkah. Berikut ialah contoh algoritma sedemikian:
Algoritma langkah demi langkah yang mudah
kedudukan = mula
langkah = kenaikan
1. jika kedudukan - akhir< точность kemudian 4
jika kedudukan > akhir kemudian 2
jika kedudukan< конец kemudian 3
2. kedudukan = kedudukan – langkah
3. kedudukan = kedudukan + langkah
4. selesai
Algoritma Bresenham.
Walaupun algoritma Bresenham pada asalnya dibangunkan untuk plotter digital, ia adalah sama-sama Sesuai untuk monitor LCD. Algoritma memilih koordinat raster optimum untuk mewakili segmen. Semasa operasi, salah satu koordinat adalah sama ada x atau y (bergantung kepada cerun) - perubahan oleh satu. Menukar koordinat lain (ke 0 atau 1) bergantung pada jarak antara kedudukan sebenar segmen dan koordinat grid terdekat. Kami akan memanggil jarak ini sebagai ralat.
Algoritma dibina sedemikian rupa sehingga hanya tanda ralat ini perlu diperiksa. Dalam Rajah 2 ini digambarkan untuk segmen dalam oktan pertama, i.e. untuk segmen dengan kecerunan antara 0 hingga 1. Daripada rajah anda boleh lihat bahawa jika kecerunan segmen dari titik (0,0) lebih besar daripada 1/2, maka persilangan dengan garis x = 1 akan terletak lebih dekat dengan garis y = 1 daripada garis lurus y = 0. Akibatnya, titik raster (1,1) lebih baik menghampiri laluan segmen daripada titik (1,0). Jika cerun kurang daripada 1/2, maka sebaliknya adalah benar. untuk kecerunan 1/2 tiada pilihan pilihan. DALAM dalam kes ini algoritma memilih titik (1,1).
nasi. 2. Idea utama algoritma Bresenham.
Tidak semua segmen melalui mata raster. Keadaan yang serupa digambarkan dalam Rajah 3, di mana segmen dengan kecerunan 3/8 mula-mula melalui titik raster (0,0) dan secara berurutan bersilang tiga piksel. Pengiraan ralat apabila mewakili segmen dengan piksel diskret juga digambarkan.
Rajah.3. Graf ralat dalam algoritma Bresenham.
Oleh kerana ia adalah wajar untuk menyemak hanya tanda ralat, ia pada mulanya ditetapkan kepada -1/2. Oleh itu, jika pekali sudut segmen lebih besar daripada atau sama dengan 1/2, maka nilai ralat pada titik raster seterusnya dengan koordinat (1,0) boleh dikira sebagai
e= e + m
di mana m- pekali sudut. Dalam kes kita, apabila nilai awal ralat -1/2
e = 1/2 + 3/8 = -1/8
Kerana e negatif, segmen akan melepasi di bawah bahagian tengah piksel. Oleh itu, piksel pada tahap mendatar yang sama lebih baik menghampiri kedudukan segmen, jadi di tidak meningkat. Kami mengira ralat dengan cara yang sama
e= -1/8 + 3/8 = 1/4
pada titik raster seterusnya (2,0). Sekarang e positif, yang bermaksud segmen akan melepasi lebih tinggi titik tengah. Elemen raster (2,1) dengan koordinat terbesar seterusnya di lebih baik menghampiri kedudukan segmen. Oleh itu di meningkat sebanyak 1. Sebelum mempertimbangkan piksel seterusnya, adalah perlu untuk membetulkan ralat dengan menolak 1 daripadanya
e = 1/4 - 1 = -3/4
Perhatikan bahawa persilangan garis menegak x= 2 s segmen yang diberikan terletak 1/4 di bawah garis lurus di= 1. Jika kita menggerakkan segmen 1/2 ke bawah, kita mendapat nilai -3/4 dengan tepat. Meneruskan pengiraan untuk piksel seterusnya memberi
e = -3/4 + 3/8 = -3/8
Kerana e adalah negatif, maka y tidak bertambah. Daripada semua yang telah dikatakan, ia mengikuti bahawa ralat adalah selang yang terputus sepanjang paksi di segmen dipertimbangkan dalam setiap elemen raster (berbanding dengan -1/2).
Mari kita bentangkan algoritma Bresenham untuk oktan pertama, i.e. untuk kes 0 =< y =< x.
Algoritma Bresenham untuk menguraikan segmen menjadi raster untuk oktan pertama
Integer- fungsi penukaran kepada integer
x, y, x, y - integer
e - sebenar
permulaan pembolehubah
Pembetulan permulaan separuh piksel
permulaan gelung utama
manakala (e => 0)
Gambar rajah blok algoritma ditunjukkan dalam Rajah 4.
Rajah.4. Gambar rajah blok algoritma Bresenham.
Contoh algoritma Bresenham.
Pertimbangkan segmen yang dilukis dari titik (0,0) ke titik (5,5). Mengurai segmen menjadi raster menggunakan algoritma Bresenham membawa kepada hasil berikut:
tetapan awal
e = 1 - 1/2 = 1/2
Hasilnya ditunjukkan dalam Rajah 5 dan bertepatan dengan apa yang dijangkakan. Ambil perhatian bahawa titik raster dengan koordinat (5,5) tidak diaktifkan. Titik ini boleh diaktifkan dengan menukar gelung for-next kepada 0 kepada x. Pengaktifan titik (0,0) boleh dihapuskan dengan meletakkan pernyataan Plot sejurus sebelum baris i seterusnya.
nasi. 5. Hasil daripada algoritma Bresenham dalam oktan pertama.
Algoritma am Bresenham.
Agar pelaksanaan algoritma Bresenham menjadi lengkap, adalah perlu untuk memproses segmen dalam semua oktan. Pengubahsuaian adalah mudah dilakukan, dengan mengambil kira dalam algoritma bilangan kuadran di mana segmen terletak dan pekali sudutnya. Bila nilai mutlak cerun lebih besar daripada 1, di sentiasa berubah satu, dan kriteria ralat Bresenham digunakan untuk memutuskan sama ada untuk menukar nilai x. Pilihan koordinat yang sentiasa berubah (dengan +1 atau -1) bergantung pada kuadran (Rajah 6.). Algoritma umum boleh dirumuskan seperti berikut:
Algoritma kuadran Bresenham integer umum
diandaikan bahawa hujung segmen (x1,y1) dan (x2,y2) tidak bertepatan
semua pembolehubah dianggap integer
Tanda- fungsi yang mengembalikan -1, 0, 1 untuk hujah negatif, sifar dan positif, masing-masing
permulaan pembolehubah
x = abs(x2 - x1)
y = abs(y2 - y1)
s1 = Tanda(x2 - x1)
s2 = Tanda(y2 - y1)
pertukaran nilai x dan y bergantung pada cerun segmen
jika y< x kemudian
tamat jika
permulaan e dilaraskan dengan separuh piksel
gelung utama
untuk i=1 kepada x
Plot(x,y)
sementara(e =>0)
jika Pertukaran = 1 kemudian
tamat sementara
jika Pertukaran = 1 kemudian
Rajah.6. Analisis kes untuk algoritma Bresenham umum.
Contoh. Algoritma Bresenham umum.
Untuk ilustrasi, pertimbangkan segmen dari titik (0,0) hingga titik (-8, -4).
tetapan awal
keputusan kitaran langkah demi langkah
Rajah.7. Hasil daripada algoritma Bresenham umum dalam kuadran ketiga.
Dalam Rajah. 7 menunjukkan hasilnya. Perbandingan dengan Rajah. 5 menunjukkan bahawa keputusan kedua-dua algoritma adalah berbeza.
Bahagian seterusnya membincangkan algoritma Bresenham untuk menghasilkan bulatan.
Algoritma Bresenham untuk menghasilkan bulatan.
Ia perlu untuk mengurai menjadi raster bukan sahaja linear, tetapi juga yang lain, lebih banyak lagi fungsi kompleks. pereputan bahagian kon, iaitu, bulatan, elips, parabola, hiperbola, sejumlah besar karya telah dikhaskan. Kebanyakan perhatian, sudah tentu, diberikan kepada bulatan. Salah satu algoritma penjanaan bulatan yang paling cekap dan mudah difahami adalah disebabkan oleh Bresenham. Pertama, ambil perhatian bahawa anda hanya perlu menjana satu perlapan daripada bulatan. Bahagian selebihnya boleh didapati dengan pantulan berturut-turut, seperti yang ditunjukkan dalam Rajah. 8. Jika oktan pertama dijana (dari 0 hingga 45° lawan jam), maka oktan kedua boleh diperoleh dengan pantulan cermin berbanding garis lurus y = x, yang bersama-sama memberikan sukuan pertama. Sukatan pertama dipantulkan secara relatif kepada garis x = 0 untuk mendapatkan bahagian bulatan yang sepadan dalam sukuan kedua. Separuh bulatan atas dipantulkan relatif kepada garis lurus y = 0 untuk melengkapkan pembinaan. Dalam Rajah. Rajah 8 menunjukkan matriks dua dimensi bagi penjelmaan yang sepadan.
nasi. 8. Generasi bulatan penuh daripada lengkok pada oktan pertama.
Untuk mendapatkan algoritma, pertimbangkan suku pertama bulatan dengan pusatnya di tempat asal. Ambil perhatian bahawa jika algoritma bermula pada titik x = 0, y = R, kemudian apabila menghasilkan bulatan mengikut arah jam dalam sukuan pertama di ialah fungsi menurun secara monoton bagi hujah (Rajah 9). Begitu juga jika titik permulaan ialah y = 0, X = R, kemudian apabila menghasilkan bulatan lawan jam X akan menjadi fungsi menurun secara monoton bagi hujah u. Dalam kes kami, penjanaan mengikut arah jam dipilih, bermula pada titik X = 0, y = R. Diandaikan bahawa pusat bulatan dan titik permulaan adalah tepat pada titik raster.
Untuk sesiapa titik yang diberikan pada bulatan, apabila menjana mengikut arah jam, terdapat hanya tiga kemungkinan untuk memilih piksel seterusnya yang paling sesuai menghampiri bulatan: secara mendatar ke kanan, menyerong ke bawah dan ke kanan, menegak ke bawah. Dalam Rajah. 10 arah ini ditetapkan masing-masing m H , m D , m V . Algoritma memilih piksel yang mana kuasa dua jarak antara salah satu piksel ini dan bulatan adalah minimum, iaitu, minimum
m H = |(x i + 1) 2 + (y i) 2 -R 2 |
m D = | |
m V = |(x i) 2 + (y i -1) 2 -R 2 |
Pengiraan boleh dipermudahkan jika kita perhatikan bahawa di sekitar titik (xi, yi,) hanya lima jenis persilangan bulatan dan grid raster yang mungkin, ditunjukkan dalam Rajah. sebelas.
nasi. 11. Persilangan bulatan dan grid raster.
Perbezaan antara jarak kuasa dua dari pusat bulatan ke piksel pepenjuru (x i, + 1, y i - 1) dan dari pusat ke titik pada bulatan R 2 adalah sama dengan
d i = (x i + 1) 2 + (y i -1) 2 -R 2
Seperti dalam algoritma Bresenham untuk segmen, adalah dinasihatkan untuk menggunakan hanya tanda ralat, dan bukan magnitudnya, untuk memilih piksel yang sepadan.
Apabila d i< 0 диагональная точка (x i , + 1, у i - 1) terletak di dalam bulatan sebenar, iaitu ini adalah kes 1 atau 2 dalam Rajah. 11. Jelas bahawa dalam situasi ini anda harus memilih sama ada piksel (x i, + 1, di i) , iaitu m H, atau piksel (x i, + 1, di i - 1), iaitu m D . Untuk melakukan ini, mula-mula pertimbangkan kes 1 dan semak perbezaan dalam jarak kuasa dua dari bulatan ke piksel dalam arah mendatar dan pepenjuru:
d = |(x i + 1) 2 + (y i) 2 -R 2 | - |(x i + 1) 2 + (y i -1) 2 -R 2 |
Pada d< 0 расстояние от окружности до диагонального пикселя больше, чем до горизонтального. Sebaliknya, jika d > 0, jarak ke piksel mendatar adalah lebih besar. Oleh itu,
pada d<= 0 выбираем m H в (x i , + 1, у i - 1)
untuk d > 0, pilih m D dalam (x i, + 1, y i - 1)
Pada e = 0, apabila jarak dari bulatan ke kedua-dua piksel adalah sama, kami memilih langkah mendatar.
Bilangan pengiraan yang diperlukan untuk menganggarkan nilai e boleh dikurangkan dengan menyatakan bahawa dalam kes 1
(x i + 1) 2 + (y i) 2 -R 2 >= 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
sejak piksel pepenjuru (x i, + 1, di i - 1) sentiasa terletak di dalam bulatan, dan mendatar (x i, + 1, di i) - di luarnya. Oleh itu, e boleh dikira menggunakan formula
d = (x i + 1) 2 + (y i) 2 -R 2 + (x i + 1) 2 + (y i -1) 2 -R 2
Tambahan kepada persegi penuh sebutan (y i) 2 menggunakan penambahan dan penolakan - 2y i + 1 memberi
d = 2[(x i + 1) 2 + (y i -1) 2 -R 2 ] + 2y i - 1
DALAM dalam kurungan berdiri dengan takrif e i dan penggantiannya
d = 2(e i + y i) - 1
sangat memudahkan ungkapan.
Pertimbangkan kes 2 dalam Rajah. 11 dan ambil perhatian bahawa di sini piksel mendatar (x i, + 1, y i) mesti dipilih, kerana y ialah fungsi menurun secara monoton. Menyemak komponen e menunjukkan bahawa
(x i + 1) 2 + (y i) 2 -R 2< 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
kerana dalam kes 2 piksel mendatar (x i, + 1, y i) dan pepenjuru (x i, + 1, y i -1) terletak di dalam bulatan. Oleh itu d< 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x i , + 1, у i).
Jika e i > 0, maka titik pepenjuru (x i, + 1, y i -1) berada di luar bulatan, iaitu ini adalah kes 3 dan 4 dalam Rajah. 11. Dalam keadaan ini, jelas bahawa sama ada piksel (x i, + 1, y i -1) atau (x i, y i -1) mesti dipilih . Sama seperti analisis kes sebelumnya, kriteria pemilihan boleh diperoleh dengan terlebih dahulu mempertimbangkan kes 3 dan menyemak perbezaan antara jarak kuasa dua dari bulatan ke pepenjuru m D dan piksel m V menegak,
iaitu d " = |(x i + 1) 2 + (y i -1) 2 -R 2 | - |(x i) 2 + (y i -1) 2 -R 2 |
Pada d " < 0, jarak dari bulatan ke piksel menegak (x i, y i -1) adalah lebih besar dan anda harus memilih langkah pepenjuru ke piksel (x i, + 1, y i -1). Sebaliknya, dalam kes d " > 0, jarak dari bulatan ke piksel pepenjuru adalah lebih besar dan anda harus memilih pergerakan menegak ke piksel (x i, y i -1). Oleh itu,
pada d " <= 0 pilih m D dalam (x i +1, y i -1)
pada d " > 0 pilih m V dalam (x i, y i -1)
Di sini sekiranya d " = 0, iaitu apabila jarak adalah sama, langkah pepenjuru dipilih.
Memeriksa komponen e " menunjukkan bahawa
(x i) 2 + (y i -1) 2 -R 2 >= 0
(x i + 1) 2 + (y i -1) 2 -R 2< 0
kerana untuk kes 3, piksel pepenjuru (x i +1, y i -1) berada di luar bulatan, manakala piksel menegak (x i, y i -1) berada di dalamnya. Ini membolehkan kita menulis e " sebagai
d " = (x i +1) 2 + (y i -1) 2 -R 2 + (x i) 2 + (y i -1) 2 -R 2
Melengkapkan kuasa dua sempurna bagi sebutan (x i) 2 dengan menambah dan menolak 2x i + 1 memberikan
d " = 2[(x i +1) 2 + (y i -1) 2 -R 2 ] - 2x i - 1
Menggunakan definisi d i membawa ungkapan kepada bentuk
d " = 2(e i - x i )- 1
Sekarang, mempertimbangkan kes 4, kita sekali lagi ambil perhatian bahawa kita harus memilih piksel menegak (x i, y i -1), kerana y ialah fungsi menurun secara monoton apabila ia meningkat X.
Menyemak komponen d " untuk kes 4 menunjukkan bahawa
(x i +1) 2 + (y i -1) 2 -R 2 > 0
(x i) 2 + (y i -1) 2 -R 2 > 0
kerana kedua-dua piksel berada di luar bulatan. Oleh itu, e " > 0 dan apabila menggunakan kriteria yang dibangunkan untuk kes 3, pilihan m V yang betul berlaku .
Ia kekal untuk menyemak hanya kes 5 dalam Rajah. 11, yang berlaku apabila piksel pepenjuru (x i, y i -1) terletak pada bulatan, iaitu d i = 0. Memeriksa komponen e menunjukkan bahawa
(x i +1) 2 + (y i) 2 -R 2 > 0
Oleh itu, d > 0 dan piksel pepenjuru (x i +1, y i -1) dipilih. Begitu juga, kami menganggarkan komponen d " :
(x i +1) 2 + (y i -1) 2 -R 2 = 0
(x i +1) 2 + (y i -1) 2 -R 2< 0
dan d " < 0, что является условием выбора правильного диагонального шага к (x i +1 , у i -1) . Таким образом, случай d i = 0 подчиняется тому же критерию, что и случай d i < 0 или d i >0. Mari kita ringkaskan hasil yang diperoleh:
d<= 0 выбираем пиксел (x i +1 , у i) - m H
d > 0 pilih piksel (x i +1, y i -1) - m D
d " <= 0 выбираем пиксел (x i +1 , у i -1) - m D
d " > 0 pilih piksel (x i, y i -1)- m V
d i = 0 pilih piksel (x i +1, y i -1) - m D
Adalah mudah untuk membangunkan hubungan berulang yang mudah untuk melaksanakan algoritma langkah demi langkah. Mula-mula pertimbangkan langkah mendatar m H kepada piksel (x i + 1, y i) . Mari kita nyatakan kedudukan piksel baharu ini sebagai (i + 1). Kemudian koordinat piksel baharu dan nilai e i adalah sama
d i +1 = (x i +1 +1) 2 + (y i +1 -1) 2 -R 2 dd i + 2x i +1 + 1
Begitu juga, koordinat piksel baharu dan nilai d i untuk langkah m D ke piksel (x i + 1, y i -1) adalah seperti berikut:
d i+1 = d i + 2x i+1 - 2y i+1 +2
Begitu juga untuk langkah m V hingga (x i, y i -1)
d i+1 = d i - 2y i+1 +1
Pelaksanaan algoritma Bresenham dalam pseudokod untuk bulatan diberikan di bawah.
Algoritma langkah demi langkah Bresenham untuk menghasilkan bulatan dalam kuadran pertama
semua pembolehubah adalah integer
permulaan pembolehubah
Had = 0
1 Plot(x i , y i )
jika y i<= Пределkemudian 4
Memilih kes 1 atau 2, 4 atau 5, atau 3
jika D i< 0kemudian 2
jika D > 0kemudian 3
jika D i = 0 kemudian 20
definisi kes 1 atau 2
2 d = 2d i + 2у i - 1
jika d<= 0kemudian 10
jika d > 0 kemudian 20
definisi kes 4 atau 5
3 d = 2D i + 2x i - 1
jika d <= 0kemudian 20
jika d > 0 kemudian 30
melaksanakan langkah
10 x i = x i + 1
D i = D i + 2x i + 1
gOkepada 1
20 x i = x i + 1
D i = D i + 2х i - 2у i + 2
pergi ke 1
4 selesai
Pembolehubah had ditetapkan kepada sifar untuk menamatkan algoritma pada paksi mendatar, menyebabkan bulatan dijana dalam kuadran pertama. Jika hanya satu oktant diperlukan, maka oktan kedua boleh diperolehi menggunakan tetapan Had = Integer(R/sqrt(2)), dan yang pertama - menggunakan pantulan oktan kedua berbanding garis lurus y = x (Rajah 8). Gambar rajah blok algoritma ditunjukkan dalam Rajah. 12.
nasi. 12. Gambar rajah blok algoritma langkah demi langkah Bresenham untuk menghasilkan bulatan dalam kuadran pertama.
Keluk Bezier dan algoritma geometrinya.
Keluk Bezier dibangunkan secara bebas pada tahun 60-an abad ke-20 oleh Pierre Bezier dari syarikat kereta Renault dan Paul de Casteljau dari syarikat Citroen, di mana ia digunakan untuk mereka bentuk badan kereta.
Walaupun penemuan de Castellier dibuat agak lebih awal daripada Bézier (1959), penyelidikannya tidak diterbitkan dan disembunyikan oleh syarikat sebagai rahsia perdagangan sehingga akhir 1960-an.
Curves pertama kali diperkenalkan kepada orang ramai pada tahun 1962 oleh jurutera Perancis Pierre Bézier, yang, setelah membangunkannya secara bebas daripada de Castellier, menggunakannya untuk reka bentuk bantuan komputer badan automobil. Lengkung itu dinamakan sempena Bezier, dan kaedah rekursif yang dibangunkannya untuk menentukan lengkung (algoritma de Castelier) dinamakan sempena de Castellier.
Selepas itu, penemuan ini menjadi salah satu alat terpenting dalam sistem reka bentuk bantuan komputer dan program grafik komputer.
Keluk Bezier – lengkung parametrik yang diberikan oleh ungkapan
, 0 < t <1
di manakah fungsi komponen vektor bagi bucu sokongan, dan – fungsi asas Bezier curve, juga dipanggil polinomial Bernstein.
di mana n ialah darjah polinomial, i ialah nombor ordinal bucu rujukan.
Jenis lengkung Bezier
Lengkung linear
Apabila n = 1, lengkung ialah segmen garis lurus, titik rujukan P0 dan P1 mentakrifkan permulaan dan penghujungnya.
Lengkung diberikan oleh persamaan:
,
Lengkung kuadratik
(n = 2) ditentukan oleh 3 titik rujukan: P0, P1 dan P2.
Lengkung Bezier Kuadratik sebagai sebahagian daripada splines digunakan untuk menerangkan bentuk aksara dalam fon TrueType dan fail SWF.
Lengkung padu
(n = 3) diterangkan oleh persamaan berikut:
Empat titik rujukan P0, P1, P2 dan P3, yang ditakrifkan dalam ruang 2 atau 3 dimensi, tentukan bentuk lengkung.
Garisan bermula dari titik P0 menuju ke arah P1 dan berakhir di titik P3 menghampirinya dari P2. Iaitu, lengkung tidak melalui titik P1 dan P2, ia digunakan untuk menunjukkan arahnya. Panjang segmen antara P0 dan P1 menentukan berapa lama lengkung akan beralih ke P3.
Dalam bentuk matriks, lengkung Bezier kubik ditulis seperti berikut:
,
di mana ia dipanggil matriks asas Bezier:
Sistem grafik moden seperti PostScript, Metafont dan GIMP menggunakan spline Bezier yang terdiri daripada lengkung padu untuk mewakili bentuk melengkung.
Aplikasi dalam grafik komputer
Disebabkan oleh kemudahan definisi dan manipulasi, lengkung Bezier digunakan secara meluas dalam grafik komputer untuk memodelkan garis halus. Lengkung terletak sepenuhnya pada badan cembung titik rujukannya. Sifat lengkung Bezier ini, dalam satu pihak, sangat memudahkan tugas mencari titik persilangan lengkung (jika badan cembung tidak bersilang, maka lengkung itu sendiri tidak bersilang), dan sebaliknya, ia membolehkan anda untuk menggambarkan lengkung menggunakan titik rujukannya. Selain itu, transformasi lengkung affine (terjemahan, penskalaan, putaran) juga boleh dilaksanakan dengan menggunakan transformasi yang sesuai pada titik kawalan.
Yang paling penting ialah lengkung Bezier darjah kedua dan ketiga (kuadrat dan kubik). Lengkung darjah yang lebih tinggi memerlukan lebih banyak pengiraan apabila diproses dan digunakan kurang kerap untuk tujuan praktikal. Untuk membina garisan bentuk kompleks, lengkung Bezier individu boleh disambungkan secara berurutan antara satu sama lain untuk membentuk spline Bezier. Untuk memastikan garis licin di persimpangan dua lengkung, titik kawalan bersebelahan kedua-dua lengkung mesti terletak pada garisan yang sama. Dalam program grafik vektor seperti Adobe Illustrator atau Inkscape, serpihan ini dikenali sebagai "laluan".
Algoritma geometri untuk lengkung Bezier
Algoritma ini membolehkan anda mengira koordinat (x, y) titik pada lengkung Bezier berdasarkan nilai parameter t.
1. Setiap sisi kontur poligon yang melalui titik mercu tanda dibahagikan secara berkadar dengan nilai t.
2. Titik bahagi disambungkan dengan tembereng lurus dan membentuk poligon baharu. Bilangan nod litar baharu adalah kurang satu daripada bilangan nod litar sebelumnya.
3. Sisi kontur baru sekali lagi dibahagikan mengikut perkadaran dengan nilai t. Dan sebagainya. Ini berterusan sehingga satu titik pembahagian diperoleh. Titik ini akan menjadi titik keluk Bezier.
Berikut ialah rakaman algoritma geometri dalam C++:
untuk (i = 0;i< = m;i + +)
R[i] =P[i]; // cipta tatasusunan tambahanR
untuk (j = m; i > 0; i – –)
untuk (i = 0; i< j; i + +)
R[i] =R[i] +t*(R[i + 1] –R[i]);
Hasil daripada algoritma ialah koordinat satu titik pada lengkung Bezier ditulis dalam R.
Model untuk menerangkan permukaan. Model analisis.
Model analisis ialah perihalan permukaan menggunakan formula matematik:
z = f(x,y) – penerangan menggunakan fungsi,
F(x,y,z) = 0 – penerangan menggunakan persamaan tersirat.
Bentuk parametrik perihalan permukaan sering digunakan:
dengan s dan t ialah parameter yang berubah dalam julat tertentu, dan fungsi Fx, Fy dan Fz menentukan bentuk permukaan.
Kelebihan bentuk parametrik terletak pada kemudahan menggambarkan permukaan yang sepadan dengan fungsi samar-samar dan permukaan tertutup.
Penerangan parametrik boleh ditetapkan sedemikian rupa sehingga formula tidak akan berubah dengan ketara (menjadi lebih rumit) apabila permukaan diputar atau berskala.
Sebagai contoh, pertimbangkan penerangan analitikal permukaan bola.
ialah fungsi eksplisit dua hujah,
– persamaan tersirat,
x = R sin s cos t, y = R sin s sin t, z = R cos s – dalam bentuk parametrik.
Model analisis paling sesuai untuk banyak operasi analisis permukaan.
Kelebihan model (dari sudut pandangan CG):
- kemudahan mengira koordinat setiap titik permukaan dan normal;
- sejumlah kecil data untuk menerangkan bentuk yang agak kompleks.
Kelemahan:
- kerumitan formula penerangan menggunakan fungsi yang dikira secara perlahan pada komputer mengurangkan kelajuan operasi paparan;
- adalah mustahil dalam kebanyakan kes untuk menggunakan bentuk perihalan ini terus kepada imej permukaan - permukaan dipaparkan sebagai polihedron, koordinat bucu dan mukanya dikira semasa proses paparan, yang mengurangkan kelajuan berbanding dengan poligon model penerangan.
Model permukaan "jaring seragam".
Model ini menerangkan koordinat titik permukaan individu dengan cara berikut. Setiap nod grid dengan indeks (i, j) diberikan nilai ketinggian zij. Indeks (i, j) sepadan dengan nilai koordinat tertentu (x, y). Jarak antara nod adalah sama - dx sepanjang paksi-x, dy sepanjang paksi-y. Malah, model sedemikian ialah tatasusunan dua dimensi, raster, matriks, setiap elemen yang menyimpan nilai ketinggian.
Tidak semua permukaan boleh diwakili oleh model ini. Jika hanya satu nilai ketinggian direkodkan pada setiap nod (i, j), ini bermakna permukaan diterangkan oleh fungsi bernilai tunggal z = f (x, y). Dalam erti kata lain, ini adalah permukaan yang setiap menegak bersilang sekali sahaja. Muka menegak juga tidak boleh dimodelkan. Perlu diingatkan bahawa grid boleh ditentukan bukan sahaja dalam koordinat Cartesian. Sebagai contoh, untuk menerangkan permukaan bola dengan fungsi unik, anda boleh menggunakan koordinat kutub. Menggunakan grid seragam, kelegaan permukaan bumi sering digambarkan.
Ciri positif grid seragam:
- kemudahan perihalan permukaan;
- keupayaan untuk mengetahui dengan cepat ketinggian mana-mana titik pada permukaan dengan interpolasi mudah.
Kelemahan jaringan seragam:
- permukaan yang sepadan dengan fungsi ketinggian yang tidak jelas pada titik grid tidak boleh dimodelkan;
- Untuk menerangkan permukaan yang kompleks, sejumlah besar nod diperlukan, yang mungkin dihadkan oleh jumlah memori komputer.
Model permukaan "jaringan tidak sekata".
Jaring tidak rata ialah model untuk menerangkan permukaan dalam bentuk set titik individu ((x0, y0, z0), (x1, y1, z1), ..., (xn – 1, yn – 1, zn – 1)) kepunyaan permukaan. Titik ini boleh diperolehi, sebagai contoh, hasil daripada mengukur permukaan objek menggunakan peralatan tertentu. Model ini boleh dianggap sebagai generalisasi untuk beberapa model yang dibincangkan di atas. Sebagai contoh, model poligon vektor dan jaringan seragam boleh dianggap sebagai variasi jaringan tidak seragam.
Mari kita pertimbangkan model permukaan dalam bentuk satu set nilai titik yang secara logiknya tidak berkaitan antara satu sama lain. Ketaksamaan menentukan titik rujukan menyukarkan penentuan koordinat untuk titik permukaan lain yang tidak bertepatan dengan titik rujukan. Teknik interpolasi spatial khas diperlukan.
Biarkan tugasnya adalah untuk mengira nilai koordinat z daripada koordinat yang diketahui (x, y). Untuk melakukan ini, anda perlu mencari beberapa titik terdekat, dan kemudian mengira nilai z yang dikehendaki berdasarkan kedudukan relatif titik ini dalam unjuran (x, y). Untuk grid seragam, masalah ini diselesaikan dengan agak mudah - hampir tiada carian, indeks titik rujukan terdekat segera dikira.
Tugas kedua ialah untuk memaparkan (memvisualisasikan) permukaan. Masalah ini boleh diselesaikan dengan beberapa cara. Salah satu yang paling biasa ialah triangulasi.
Proses triangulasi boleh diwakili seperti berikut:
- kita dapati tiga mata pertama paling hampir antara satu sama lain - kita mendapat satu muka segi tiga rata;
- kita mencari titik yang paling hampir dengan muka ini dan membentuk muka bersebelahan, dan seterusnya, sehingga tidak ada satu titik pun yang tinggal.
Algoritma Bresenham telah dicadangkan oleh Jack E. Bresenham pada tahun 1962 dan bertujuan untuk melukis bentuk dengan mata pada satah. Algoritma ini digunakan secara meluas dalam grafik komputer untuk melukis garisan pada skrin. Algoritma menentukan mata raster dua dimensi yang perlu dicat.
Tafsiran grafik algoritma Bresenham dibentangkan dalam rajah.
Untuk melukis segmen lurus pada satah menggunakan algoritma Bresenham, kami menulis persamaan garis lurus dalam bentuk umum
f(x,y)=Ax+Oleh+C=0
di manakah pekali A Dan B dinyatakan melalui pekali k Dan b persamaan garis lurus. Jika garis melalui dua titik dengan koordinat ( x1;y1) Dan ( x2;y2) , maka pekali persamaan garis lurus ditentukan oleh formula
A=y2-y1
B=x1-x2
C=y1∙x2-y2∙x1
Untuk mana-mana titik raster dengan koordinat ( xi;yi) fungsi nilai
- f(xi,yi)=0 jika titik terletak pada garis
- f(xi,yi)>0 jika titik terletak di bawah garisan
- f(xi,yi) di mana i– nombor titik yang dipaparkan.
Oleh itu, satu kaedah untuk menentukan titik mana P atau Q(lihat rajah) akan dipaparkan dalam langkah seterusnya, adalah perbandingan bahagian tengah segmen |P-Q| dengan nilai fungsi f(x,y). Jika nilai f(x,y) terletak di bawah titik tengah segmen |P-Q|, maka titik seterusnya yang akan dipaparkan ialah titik P, jika tidak - titik Q
.
Mari kita tuliskan kenaikan fungsi tersebut
∆f=A∆x+B∆y
Selepas memaparkan titik dengan koordinat (xi,yi) keputusan dibuat tentang perkara seterusnya yang akan dipaparkan. Untuk melakukan ini, kenaikan dibandingkan Δx Dan Δy, mencirikan kehadiran atau ketiadaan pergerakan di sepanjang koordinat yang sepadan. Kenaikan ini boleh menjadi 0 atau 1. Oleh itu, apabila kita bergerak dari satu titik ke kanan,
apabila kita bergerak dari satu titik ke kanan dan ke bawah, maka
∆f=A+B,
apabila kita bergerak dari satu titik ke bawah, maka
Kami mengetahui koordinat permulaan segmen, iaitu titik yang jelas terletak pada garisan yang dikehendaki. Kami meletakkan titik pertama di sana dan menerima f= 0 . Anda boleh mengambil dua langkah dari titik semasa - sama ada secara menegak (mendatar) atau menyerong dengan satu piksel.
Arah pergerakan secara menegak atau mendatar ditentukan oleh pekali sudut kecondongan. Jika sudut kecondongan kurang daripada 45º, dan
|A|<|B|
Dengan setiap langkah, pergerakan berlaku secara mendatar atau menyerong.
Jika sudut kecondongan lebih besar daripada 45º, dengan setiap langkah pergerakan adalah menegak atau menyerong.
Oleh itu, algoritma untuk melukis segmen condong adalah seperti berikut:
Pelaksanaan dalam C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#termasuk
menggunakan ruang nama std;
void Brezenhem(char **z, int x0, int y0, int x1, int y1)
{
int A, B, tanda;
A = y1 - y0;
B = x0 - x1;
jika (abs(A) > abs(B)) tanda = 1;
tanda lain = -1;
int signa, signb;
sekiranya< 0) signa = -1;
else signa = 1;
jika (B< 0) signb = -1;
tanda lain b = 1;
int f = 0;
z = "*" ;
int x = x0, y = y0;
jika (tanda == -1)
{
buat (
f += A*tanda;
jika (f > 0)
{
f -= B*tanda b;
y += tanda;
}
x -= tandab;
z[y][x] = "*" ;
}
lain
{
buat (
f += B*tanda b;
jika (f > 0) (
f -= A*tanda;
x -= tandab;
}
y += tanda;
z[y][x] = "*" ;
) manakala (x != x1 || y != y1);
}
}
int utama()
{
const int SAIZ = 25; // saiz medan
int x1, x2, y1, y2;
char**z;
z = aksara baharu *;
untuk (int i = 0; i< SIZE; i++)
{
z[i] = aksara baharu ;
untuk (int j = 0; j< SIZE; j++)
z[i][j] = "-" ;
}
cout<<
"x1 = "
; cin >> x1;
cout<<
"y1 = "
; cin >> y1;
cout<<
"x2 = "
; cin >>x2;
cout<<
"y2 = "
; cin >> y2;
Brezenhem(z, x1, y1, x2, y2);
untuk (int i = 0; i< SIZE; i++)
{
untuk (int j = 0; j< SIZE; j++)
cout<<
z[i][j];
cout<<
endl;
}
cin.get(); cin.get();
pulangan 0;
}
Hasil pelaksanaan
Algoritma Bresenham juga boleh digunakan dalam masalah kawalan, seperti kawalan kuasa atau kelajuan. Dalam kes ini, paksi mendatar ialah paksi masa, dan nilai yang ditentukan menetapkan pekali sudut kecondongan garis lurus.
Algoritma Bresenham ialah algoritma yang menentukan titik pada raster dua dimensi yang perlu dilorek untuk mendapatkan penghampiran hampir garis lurus antara dua titik tertentu.
Segmen dilukis di antara dua titik - (x0,y0) dan (x1,y1), di mana dalam pasangan ini lajur dan baris ditunjukkan, masing-masing, nombor yang meningkat ke kanan dan ke bawah. Mula-mula kita akan menganggap bahawa garisan kita turun dan ke kanan, dan jarak mendatar x1 − x0 melebihi jarak menegak y1 − y0, i.e. kecondongan garisan dari mengufuk adalah kurang daripada 45°. Matlamat kami adalah untuk setiap lajur x antara x0 dan x1, tentukan baris y yang paling hampir dengan garis dan lukis satu titik (x,y).
Formula umum untuk garis antara dua titik ialah:
Oleh kerana kita mengetahui lajur x, baris y diperoleh dengan membundarkan kepada integer nilai berikut:
Walau bagaimanapun, tidak perlu mengira nilai tepat ungkapan ini. Cukup untuk ambil perhatian bahawa y tumbuh dari y0 dan untuk setiap langkah kita tambah satu kepada x dan tambah nilai cerun kepada y
yang boleh dikira terlebih dahulu. Selain itu, pada setiap langkah kami melakukan satu daripada dua perkara: sama ada mengekalkan y sama atau meningkatkannya sebanyak 1.
Mana antara kedua-dua ini untuk dipilih boleh diputuskan dengan menjejaki nilai ralat, yang bermaksud jarak menegak antara nilai y semasa dan nilai y tepat untuk x semasa. Setiap kali kita meningkatkan x, kita meningkatkan nilai ralat dengan jumlah cerun s yang diberikan di atas. Jika ralat lebih besar daripada 0.5, garisan lebih dekat dengan y seterusnya, jadi kami menambah y dengan satu sambil mengurangkan nilai ralat sebanyak 1. Dalam pelaksanaan algoritma di bawah, plot(x,y) melukis titik, dan abs mengembalikan nilai mutlak nombor:
fungsi baris(x0, x1, y0, y1)
int deltax:= abs(x1 - x0)
int deltay:= abs(y1 - y0)
sebenar ralat: = 0
sebenar deltaerr:= deltay / deltax
int y:=y0
untuk x daripada x0 kepada x1
ralat:= ralat + deltaerr
jika ralat >= 0.5
ralat:= ralat - 1.0
Biarkan permulaan segmen mempunyai koordinat (X 1,Y 1), dan penghujungnya (X 1,X 2). Mari kita nyatakan
Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Tanpa kehilangan keluasan, kita akan menganggap bahawa permulaan segmen bertepatan dengan asal koordinat, dan garis lurus mempunyai bentuk
di mana. Kami menganggap bahawa titik permulaan adalah di sebelah kiri. Biarkan pada langkah (i-1) titik semasa segmen itu ialah P i -1 =(r,q) . Pilihan titik S i atau T i seterusnya bergantung kepada tanda perbezaan (s-t). Jika (s-t)<0 , то P i =T i =(r+1,q) и тогда
X i +1 =i+1;Y i +1 =Y i , jika (s-t)≥0, maka P i =T i =(r+1,q+1) dan kemudian X i +1 =i+ 1 ; Y i +1 =Y i +1 ;
dx=(s-t)=2(rdy-qdx)+2dy –dx
Oleh kerana tanda dx=(s-t) bertepatan dengan tanda perbezaan), kita akan menyemak tanda ungkapan d i =dx(s-t). . Oleh kerana r=X i -1 dan q=Y i -1 , maka
d i +1 = d i +2dy -2dx(y i -y i -1) .
Biar pada langkah sebelumnya d i<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)
Tinggal untuk mengetahui cara mengira d i. Oleh kerana untuk i=1
Prosedur Bresenham(x1,y1,x2,y2,Warna: integer);
dx,dy,incr1,incr2,d,x,y,xend: integer;
dx:= ABS(x2-x1);
dy:= Abs(y2-y1);
d:=2*dy-dx; (nilai awal untuk d)
incr1:=2*dy; (kenaikan untuk d<0}
incr2:=2*(dy-dx); (kenaikan untuk d>=0)
jika x1>x2 maka (mulakan dari titik dengan nilai x yang lebih kecil)
PutPixel(x,y,Warna); (titik pertama segmen)
Manakala x d:=d+incr1 (pilih titik bawah) d:=d+incr2; (pilih titik atas, y-meningkat) PutPixel(x,y,Warna); 26. Algoritma General Bresenham.
Algoritma memilih koordinat raster optimum untuk mewakili segmen. Peningkatan yang lebih besar, sama ada Δx atau Δy, dipilih sebagai unit raster. Semasa operasi, salah satu koordinat - sama ada x atau y (bergantung pada cerun) - berubah satu. Menukar koordinat lain (ke 0 atau 1) bergantung pada jarak antara kedudukan sebenar segmen dan koordinat grid terdekat. Jarak ini adalah kesilapan. Algoritma dibina sedemikian rupa sehingga anda hanya perlu mengetahui tanda ralat ini. Akibatnya, titik raster (1, 1) lebih baik menghampiri laluan segmen daripada titik (1, 0). Jika kecerunan kurang daripada ½, maka sebaliknya adalah benar. Untuk kecerunan ½, tiada pilihan pilihan. Dalam kes ini, algoritma memilih titik (1, 1). Oleh kerana ia adalah wajar untuk menyemak hanya tanda ralat, ia pada mulanya ditetapkan kepada -½. Oleh itu, jika kecerunan segmen lebih besar daripada atau sama dengan ½, maka nilai ralat pada titik raster seterusnya boleh dikira sebagai e = -½ + Δy/Δx. Agar pelaksanaan algoritma Bresenham menjadi lengkap, adalah perlu untuk memproses segmen dalam semua oktan. Ini mudah dilakukan, dengan mengambil kira dalam algoritma bilangan kuadran di mana segmen terletak dan pekali sudutnya. Apabila nilai mutlak cerun lebih besar daripada 1, y sentiasa diubah oleh satu, dan kriteria ralat Bresenham digunakan untuk memutuskan sama ada untuk menukar nilai x. Pilihan koordinat yang sentiasa berubah (+1 atau -1) bergantung pada kuadran
var x,y,sy,sx,dx,dy,e,z,i: Integer; 27. Algoritma Bresenham untuk menghasilkan bulatan
Raster perlu dikembangkan sebagai linear dan fungsi lain yang lebih kompleks. Pengagihan potongan terminal, seperti lunas, elips, parabola, hiperbola, telah diberikan kepada nilai robot. Dengan penuh hormat, boleh difahami, satu kepentingan telah ditambah. Salah satu algoritma penjanaan bulatan yang paling cekap dan paling mudah difahami ialah Bresenham. Untuk tongkol, adalah penting untuk menjana hanya satu perlapan daripada pegangan. Bahagian-bahagian ini boleh dikeluarkan dengan rentak berturut-turut. Sebaik sahaja oktan pertama dijana (dari 0 hingga 45 ° anak panah anti tahun), maka oktan lain boleh dinyatakan sebagai imej cermin garis lurus y = x, yang bersama-sama memberikan kuadran pertama. Kuadran pertama tersingkir dengan garis lurus x = 0 untuk mengeluarkan bahagian penyokong pancang dari kuadran yang lain. Bahagian atas ditumbangkan terus pada = 0 untuk menyelesaikan tugas. Untuk menunjukkan algoritma, mari kita lihat satu perempat daripada pancang yang berpusat pada tongkol koordinat. Sila ambil perhatian bahawa oleh kerana algoritma bermula pada titik x = 0, y = R, maka apabila menjana bulatan di belakang anak panah tahun dalam petak pertama, y ialah fungsi menurun secara monoton bagi argumen. Begitu juga, jika titik output ialah y = 0, x == R, maka apabila menghasilkan bulatan bertentangan anak panah x akan menjadi fungsi menurun secara monoton bagi hujah y. Dalam kes kami, penjanaan di belakang anak panah tahun dengan tongkol pada titik x = 0, y = R dipilih Ia dipindahkan bahawa pusat pancang dan titik tongkol berada tepat pada titik raster. Untuk mana-mana titik tertentu pada bulatan apabila menjana di belakang anak panah tahun, terdapat hanya tiga pilihan untuk memilih piksel seterusnya, bulatan terdekat: secara mendatar ke kanan, menyerong ke bawah dan ke kanan, menegak ke bawah. Algoritma memilih piksel yang mana persegi minimum terletak di antara salah satu piksel ini dan bulatan. 28. Konsep fraktal. Sejarah grafik fraktal
Dalam kehidupan seharian, anda sering dapat memerhatikan imej (corak) yang, nampaknya, tidak dapat diterangkan secara matematik. Contoh: tingkap membeku pada musim sejuk, anda boleh memerhatikan gambar itu. Set sedemikian dipanggil fraktal. Fraktal tidak serupa dengan angka terkenal dari geometri, dan ia dibina menggunakan algoritma tertentu yang boleh dilaksanakan pada komputer. Ringkasnya, fraktal ialah imej yang terhasil daripada beberapa transformasi yang digunakan berulang kali pada bentuk asal. Fraktal ialah angka geometri yang terdiri daripada bahagian dan yang boleh dibahagikan kepada bahagian, setiap satunya akan mewakili salinan keseluruhan yang lebih kecil. Sifat utama fraktal ialah persamaan diri, i.e. mana-mana serpihan fraktal dalam satu cara atau yang lain menghasilkan semula struktur globalnya. Fraktal dibahagikan kepada geometri, algebra, stokastik dan sistem fungsi boleh lelar. 29. Konsep dimensi dan pengiraannya
Dalam kehidupan seharian kita sentiasa menghadapi dimensi. Kami menganggarkan panjang jalan, mengetahui luas apartmen, dsb. Konsep ini agak intuitif dan, nampaknya, tidak memerlukan penjelasan. Garis mempunyai dimensi 1. Ini bermakna dengan memilih titik rujukan, kita boleh mentakrifkan mana-mana titik pada garis ini menggunakan 1 nombor - positif atau negatif. Lebih-lebih lagi, ini terpakai kepada semua garis - bulatan, persegi, parabola, dll. Dimensi 2 bermakna kita boleh mentakrifkan mana-mana titik secara unik dengan dua nombor. Jangan fikir dua dimensi bermaksud rata. Permukaan sfera juga adalah dua dimensi (ia boleh ditakrifkan menggunakan dua nilai - sudut seperti lebar dan longitud). Jika anda melihatnya dari sudut pandangan matematik, dimensi ditentukan seperti berikut: untuk objek satu dimensi, menggandakan saiz linearnya membawa kepada peningkatan saiz (dalam kes ini, panjang) dengan faktor dua (2^ 1). Untuk objek dua dimensi, penggandaan dimensi linear menghasilkan pertambahan saiz (contohnya, luas segi empat tepat) sebanyak empat kali ganda (2^2). Untuk objek 3 dimensi, menggandakan dimensi linear membawa kepada peningkatan lapan kali ganda dalam isipadu (2^3) dan seterusnya. Fraktal geometri Dengan fraktal inilah sejarah perkembangan fraktal secara umum bermula. Jenis fraktal ini diperolehi melalui binaan geometri mudah. Biasanya, apabila membina fraktal geometri, algoritma berikut digunakan: Contoh fraktal geometri: Lengkung Peano, kepingan salji Koch, daun pakis, segi tiga Sierpinski, Fraktal algebra Fraktal- rajah geometri kompleks yang mempunyai sifat persamaan diri, iaitu, terdiri daripada beberapa bahagian, setiap satunya serupa dengan keseluruhan rajah Fraktal algebra mendapat namanya kerana ia dibina berdasarkan fungsi algebra. Fraktal algebra termasuk: Set Mandelbrot, set Julia, lembangan Newton, biomorf. -Set Mandelbrot: Set Mandelbrot pertama kali diterangkan pada tahun 1905 oleh Pierre Fatou. Fatou mengkaji proses rekursif bentuk Bermula dengan satu titik pada satah kompleks, anda boleh mendapatkan mata baharu dengan menggunakan formula ini secara berturut-turut kepada mereka. Urutan titik sedemikian dipanggil orbit di bawah transformasi Fatou mendapati bahawa orbit di bawah transformasi ini menunjukkan tingkah laku yang agak kompleks dan menarik. Terdapat bilangan transformasi yang tidak terhingga - satu untuk setiap nilai. (dinamakan Mandelbrot kerana dia adalah orang pertama yang menjalankan bilangan pengiraan yang diperlukan menggunakan komputer). -set Julia: Set Julia pemetaan rasional -Kolam Newton: Kawasan dengan sempadan fraktal muncul apabila punca-punca persamaan tak linear lebih kurang ditemui oleh algoritma Newton pada satah kompleks (untuk fungsi pembolehubah nyata, kaedah Newton sering dipanggil kaedah tangen, yang, dalam kes ini, digeneralisasikan kepada satah kompleks). Mari gunakan kaedah Newton untuk mencari sifar fungsi pembolehubah kompleks menggunakan prosedur: Pilihan anggaran awal adalah kepentingan tertentu. Kerana fungsi mungkin mempunyai berbilang sifar, dan dalam kes yang berbeza kaedah mungkin menumpu kepada nilai yang berbeza. -biomorf: bentuk singkatan set Julia, dikira dengan formula z=z 3 +c. Ia mendapat namanya kerana persamaannya dengan organisma bersel tunggal. Fraktal stokastik Wakil tipikal bagi jenis fraktal ini ialah apa yang dipanggil plasma. Untuk membinanya, ambil segi empat tepat dan tentukan warna untuk setiap sudutnya. Seterusnya, cari titik tengah segi empat tepat dan cat dengan warna yang sama dengan min aritmetik bagi warna di bucu segi empat tepat + beberapa nombor rawak. Lebih besar nombor rawak ini, lebih banyak koyak lukisan itu. Objek semula jadi selalunya mempunyai bentuk fraktal. Fraktal stokastik (rawak) boleh digunakan untuk memodelkannya. Contoh fraktal stokastik: trajektori gerakan Brown pada satah dan di angkasa; sempadan trajektori gerakan Brown pada satah. Pada tahun 2001, Lawler, Schramm dan Werner membuktikan hipotesis Mandelbrot bahawa dimensinya ialah 4/3. Evolusi Schramm-Löwner ialah lengkung fraktal invarian secara konsisten yang timbul dalam model dua dimensi kritikal mekanik statistik, contohnya, dalam model Ising dan perkolasi. pelbagai jenis fraktal rawak, iaitu, fraktal yang diperoleh menggunakan prosedur rekursif di mana parameter rawak diperkenalkan pada setiap langkah. Plasma adalah contoh penggunaan fraktal tersebut dalam grafik komputer. Monotaip fraktal, atau stochatypy, ialah trend dalam seni halus yang melibatkan mendapatkan imej fraktal rawak. Maklumat berkaitan. Apa yang anda lihat sekarang? Melainkan anda dari alam semesta selari di mana semua orang duduk di belakang monitor vektor, maka ini adalah imej raster. Lihat jalur ini: /. Jika anda bergerak lebih dekat ke monitor, anda boleh melihat langkah berpiksel yang cuba berpura-pura menjadi garis vektor. Terdapat sejumlah besar algoritma rasterisasi yang berbeza untuk tujuan ini, tetapi saya ingin bercakap tentang algoritma Bresenham dan algoritma Y, yang mencari anggaran segmen vektor dalam koordinat raster. Saya menghadapi masalah rasterisasi semasa bekerja pada penjana prosedur pelan bangunan. Saya perlu mewakili dinding bilik sebagai sel tatasusunan dua dimensi. Masalah yang sama boleh dihadapi dalam pengiraan fizik, algoritma pencarian laluan, atau pengiraan pencahayaan jika pembahagian ruang digunakan. Siapa sangka bahawa kebiasaan dengan algoritma rasterisasi boleh berguna suatu hari nanti? Ini adalah intipati algoritma, pada hakikatnya semuanya kelihatan seperti ini. Pertama, cerun dikira (y1 - y0)/(x1 - x0). Nilai ralat pada titik permulaan segmen (0,0)
diambil sama dengan sifar dan sel pertama diisi. Pada langkah seterusnya, cerun ditambah kepada ralat dan nilainya dianalisis jika ralat kurang 0.5
, maka sel itu diisi (x0+1, y0), jika lebih, maka sel itu terisi (x0+1, y0+1) dan satu ditolak daripada nilai ralat. Dalam gambar di bawah, garisan sebelum rasterisasi ditunjukkan dalam warna kuning, dan jarak ke sel terdekat ditunjukkan dalam warna hijau dan merah. Cerun adalah sama dengan satu perenam, pada langkah pertama ralat menjadi sama dengan cerun, iaitu kurang 0.5
, yang bermaksud ordinat tetap sama. Ke arah tengah garisan, ralat melintasi garisan, satu ditolak daripadanya, dan piksel baharu meningkat lebih tinggi. Dan seterusnya sehingga akhir segmen. Satu lagi nuansa. Jika unjuran segmen ke paksi x kurang unjuran pada paksi y atau permulaan dan akhir segmen ditukar, maka algoritma tidak akan berfungsi. Untuk mengelakkan ini daripada berlaku, anda perlu menyemak arah vektor dan cerunnya, dan kemudian, jika perlu, tukar koordinat segmen, putar paksi, dan, akhirnya, kurangkan semuanya kepada satu atau sekurang-kurangnya dua kes. Perkara utama ialah jangan lupa mengembalikan kapak ke tempatnya semasa melukis. Untuk mengoptimumkan pengiraan, gunakan helah untuk mendarab semua pembolehubah pecahan dengan dx = (x1 - x0). Kemudian pada setiap langkah ralat akan berubah kepada dy = (y1 - y0) bukannya cerun dan oleh dx bukannya satu. Anda juga boleh menukar sedikit logik, "gerakkan" ralat supaya sempadan berada pada sifar, dan anda boleh menyemak tanda ralat ini mungkin lebih cepat. Kod untuk melukis garis raster menggunakan algoritma Bresenham mungkin kelihatan seperti ini. Pseudokod dari Wikipedia ditukar kepada C#. void BresenhamLine(int x0, int y0, int x1, int y1) ( var curam = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Semak pertumbuhan segmen sepanjang paksi-x dan sepanjang paksi-y / / Pantulkan garis secara menyerong jika sudut kecondongan terlalu besar jika (curam) ( Tukar(rujuk x0, ref y0); // Kocok koordinat disertakan dalam fungsi berasingan untuk kecantikan Tukar(ref x1, ref y1); ) // Jika garisan tidak tumbuh dari kiri ke kanan, maka kita menukar permulaan dan penghujung segmen jika (x0 > x1) ( Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) int dx = x1 - x0; (y1 - y0);< y1) ? 1: -1; // Выбираем направление роста координаты y
int y = y0;
for (int x = x0; x <= x1; x++)
{
DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место
error -= dy;
if (error < 0)
{
y += ystep;
error += dx;
}
}
}
Contoh kod untuk melukis bulatan dalam C#. void BresenhamCircle(int x0, int y0, int radius) ( int x = radius; int y = 0; int radiusRalat = 1 - x; manakala (x >= y) ( DrawPoint(x + x0, y + y0); DrawPoint (y + x0, x + y0); -y + y0); DrawPoint(y + x0, -x + y++);< 0)
{
radiusError += 2 * y + 1;
}
else
{
x--;
radiusError += 2 * (y - x + 1);
}
}
} Dalam gambar di atas, warna merah dan hijau menunjukkan jarak kepada dua piksel berjiran. Untuk mengira ralat, anda boleh menggunakan pembolehubah titik terapung dan mengambil nilai ralat daripada bahagian pecahan. Contoh kod untuk baris lancar Wu Xiaolin dalam C#. private void WuLine(int x0, int y0, int x1, int y1) ( var curam = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (curam) ( Tukar(ref x0, ref y0 ); Swap(rujuk x1, ref y1); jika (x0 > x1) ( Tukar(rujuk x0, ref x1); Tukar(rujuk y0, ref y1); ) DrawPoint(curam, x0, y0, 1); Fungsi ini secara automatik menukar koordinat bergantung pada pembolehubah curam DrawPoint(curam, x1, y1, 1); ; apungan y = y0 + kecerunan;<= x1 - 1; x++)
{
DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
DrawPoint(steep, x, (int)y + 1, y - (int)y);
y += gradient;
}
}
Sukar hari ini untuk mencari orang yang tidak pernah menemui grafik komputer dalam satu bentuk atau yang lain. Jika seseorang mula berminat dengan algoritma yang mendasarinya, maka algoritma Bresenham akan menjadi salah satu yang pertama. Satu-satunya masalah ialah saya masih belum menemui penerangan ringkas dan mudah difahami tentang algoritma ini, apatah lagi pelaksanaan. Dalam artikel ini, saya akan cuba bercakap semudah mungkin tentang keluarga algoritma Bresenham, dan juga akan menyediakan kod sedia untuk digunakan dalam JavaScript, yang boleh dikatakan tidak berbeza daripada kod dalam C/C++. Kod tersebut boleh diambil dan digunakan dengan terlebih dahulu menulis surat terima kasih kepada pengarang. Jadi, tujuan algoritma Bresenham adalah untuk melukis garisan pada peranti raster, biasanya monitor. Seperti yang anda lihat dalam Rajah 1, tidak semua piksel yang termasuk dalam imej baris terletak pada baris ini, iaitu, tugas algoritma adalah untuk mencari piksel yang paling hampir. Kelebihan utama algoritma Bresenham ialah ia tidak menggunakan operasi pendaraban yang mahal dalam gelung. Algoritma ini sesuai untuk garis lurus atau lengkung tertib kedua*. Terdapat pengubahsuaian algoritma untuk empat bersambung (iaitu, titik yang berbeza dengan 1 dalam satu koordinat dianggap jiran) dan lapan bersambung (iaitu, titik dianggap jiran jika kedua-dua koordinat berbeza tidak lebih daripada 1). Berikut adalah pilihan kedua - lebih kompleks, tetapi juga memberikan hasil yang lebih baik. Idea utama algoritma ialah garis yang akan dilukis membahagikan satah kepada dua bahagian. Persamaan lengkung ditulis sebagai Z = f (x,y) . Pada semua titik lengkung Z = 0, pada titik yang terletak di atas lengkung Z > 0, dan pada titik di bawah lengkung Z< 0 . Нам известны координаты начала отрезка, то есть точки,
заведомо лежащей на искомой кривой. Ставим туда первый пиксель и принимаем
Z = 0 . От текущего пикселя можно сделать два шага — либо
по вертикали (по горизонтали), либо по диагонали на один пиксель. Конкретные
направления шагов выбираются в зависимости от типа линии, которую надо нарисовать.
Делая шаг, мы мы вычисляем, как изменятся значение Z: ΔZ = Z" x Δx + Z" y Δy Pada salah satu langkah yang mungkin Z meningkat, pada satu lagi ia berkurang. Setiap langkah dipilih supaya nilai Z untuk piksel baharu adalah sehampir mungkin dengan 0 Oleh itu, kami akan bergerak di sepanjang garis, mencipta imejnya. Mari kita segera bersetuju bahawa algoritma untuk garis lurus tidak melukis garis mendatar dan menegak. Ini kerana lukisan garisan sedemikian boleh dilaksanakan dengan cara yang lebih mudah, selalunya pada peringkat BIOS atau pemandu. Segmen yang tinggal dibahagikan kepada dua kumpulan: mendatar dan menegak. Jika kita mewakili persamaan garis lurus dalam bentuk y = kx, maka segmen yang |k| ≤ 1 dan menegak - yang mana |k| > 1. Dengan memberikan segmen kepada salah satu kumpulan, kita boleh menukar koordinat hujung supaya segmen mendatar sentiasa dilukis dari kiri ke kanan dan segmen menegak sentiasa dilukis dari atas ke bawah. Untuk segmen mendatar, setiap piksel baharu akan berada 1 di sebelah kanan yang sebelumnya, dan ia juga boleh lebih tinggi (lebih rendah), i.e. dua langkah boleh dilakukan - ke kanan dan ke kanan secara menyerong. Untuk segmen menegak, langkah yang mungkin adalah ke bawah dan ke bawah secara menyerong. Jika koordinat hujung segmen ialah (x 1 ,y 1) dan (x 2 ,y 2), masing-masing, maka dengan setiap langkah di sepanjang paksi x Z berubah sebanyak 1, dan di sepanjang paksi y - oleh (x 2 -x 1)/(y 2 -y 1) . Untuk tidak berurusan dengan pembahagian dan kekal dalam had aritmetik integer, kami akan menukar pembolehubah Z kepada y2-y1 dan x2-x1, masing-masing. Itu sahaja matematik, selebihnya boleh difahami dari kod. Algoritma untuk melukis lengkok akan kekal di luar skop artikel, tetapi algoritma untuk melukis bulatan ternyata lebih mudah daripada garis lurus. Ini disebabkan oleh banyak sebab. Pertama, kita hanya melukis satu perlapan daripada bulatan - dari π/2 hingga π/4, dan dalam arah yang bertentangan, iaitu, mengikut arah jam. Selebihnya bulatan diperoleh dengan memantulkan bahagian ini berbanding dengan pusat bulatan, paksi mendatar dan menegak, serta garis lurus y = x + b dan y = -x + b yang melalui pusat bulatan. . Kedua, disebabkan oleh simetri, sisihan garis dari bulatan tidak begitu ketara seperti sisihan dari garis lurus, jadi Z boleh dibandingkan dengan sifar tanpa mengira sisihan maksimum yang dibenarkan. Langkah yang sah adalah betul dan betul pepenjuru, dan perubahan dalam Z bergantung pada nilai x dan y, tetapi hubungannya adalah linear, jadi tiada operasi pendaraban diperlukan. Itu sahaja, sebenarnya. Di bawah anda akan menemui skrip yang menunjukkan operasi algoritma yang diterangkan, dan untuk memahami cara ia berfungsi, lihat sahaja teks sumber halaman. Semoga berjaya! Jika anda ingin melihat demonstrasi algoritma dalam tetingkap penyemak imbas anda, sila dayakan JavaScript!
perubahan: boolean;
bermula
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1) ;
sx:=tanda(x2-x1); sy:=tanda(y2-y1);
e:= 2*dy-dx;
jika dy
lain bermula
z:=dx;
dx:=dy; dy:=z;
perubahan:=benar
akhir;
untuk i:=1 hingga dx+dy bermula
jika dy< dx then begin
jika tukar maka y:=y+sy
lain x:=x+sx;
e:=e+2*dy;
akhir lain
jika tukar maka x:=x+sx
lain y:=y+sy;
e:=e-2*dx
akhir;
Form1.Canvas.Pixels:=clblack; // mengeluarkan titik, sebagai contoh
akhir;
Idea pertama geometri fraktal timbul pada abad ke-19. Cantor, menggunakan prosedur rekursif yang mudah, menukar garisan menjadi koleksi titik tidak bersambung, yang kemudiannya dipanggil "Debu Cantor." Dia akan mengambil garisan dan mengeluarkan sepertiga tengah dan kemudian mengulangi perkara yang sama dengan bahagian yang tinggal. Peano melukis jenis garisan khas. Untuk melukisnya, Peano menggunakan algoritma berikut:
Dia mengambil garis lurus dan menggantikannya dengan segmen tiga kali lebih pendek daripada garis asal. Kemudian dia mengulangi tindakan yang sama dengan setiap segmen. Keunikannya ialah ia memenuhi seluruh pesawat, i.e. untuk setiap titik yang terletak pada satah, anda boleh mencari titik kepunyaan garis Peano.
Pengasas geometri fraktal dipertimbangkan Benoit Mandelbrot. Mandelbrot memperkenalkan konsep "fraktal".
nasi. Kepingan salji Koch
nasi. Lembaran
nasi. Segitiga Sierpinski
- satu set titik, dinamik di sekitar yang, dalam erti kata tertentu, tidak stabil berkenaan dengan gangguan kecil pada kedudukan awal. Jika f- polinomial, kami juga menganggap set Julia yang diisi - set mata yang tidak cenderung kepada infiniti. Set Julia biasa adalah sempadannya.
Prinsip operasi algoritma Bresenham adalah sangat mudah. Ambil segmen dan koordinat awalnya x. Pada x dalam kitaran kita tambah satu demi satu ke arah penghujung segmen. Pada setiap langkah, ralat dikira - jarak antara koordinat sebenar y di lokasi ini dan sel grid terdekat. Jika ralat tidak melebihi separuh ketinggian sel, maka ia diisi. Itulah keseluruhan algoritma.
Algoritma Bresenham mempunyai pengubahsuaian untuk melukis bulatan. Segala-galanya di sana berfungsi pada prinsip yang sama, dalam beberapa cara bahkan lebih mudah. Pengiraan dilakukan untuk satu oktan, dan semua bahagian lain bulatan dilukis mengikut simetri.
Sekarang tentang algoritma Wu Xiaolin untuk melukis garis halus. Ia berbeza kerana pada setiap langkah pengiraan dijalankan untuk dua piksel yang paling hampir dengan garisan, dan ia dicat dengan keamatan yang berbeza, bergantung pada jarak. Melintasi tengah piksel secara tepat memberikan 100% keamatan; jika piksel berada pada jarak 0.9 piksel, maka keamatan akan menjadi 10%. Dalam erti kata lain, seratus peratus daripada keamatan dibahagikan antara piksel yang mengehadkan garis vektor pada kedua-dua belah. 
Jika anda pernah mendapati diri anda bekerja dengan jerat pada masa hadapan, fikir sejenak, mungkin anda mencipta semula roda dan anda sebenarnya bekerja dengan piksel, walaupun anda tidak mengetahuinya. Pengubahsuaian algoritma ini boleh digunakan dalam permainan untuk mencari sel di hadapan unit pada peta, mengira kawasan kesan pukulan atau menyusun objek dengan cantik. Atau anda boleh melukis garisan, seperti dalam program dari pautan di bawah. Saya ingin menyatakan perasaan saya yang mendalam dan ikhlas terhadap pembangun piawaian www dan mereka yang melaksanakannya. Varian kod JavaScript yang berfungsi dalam semua penyemak imbas yang tersedia, i.e. IE 6.0, NN 7.0 dan Opera 6.0x tidak dibezakan oleh kecantikan dan kecanggihannya. Walau bagaimanapun, "ini tiada kaitan dengan sains yang saya wakili sekarang."
Melukis segmen garisan
Melukis bulatan
x1: y1:
x2: y2:
x0: y0:
R: