Hai, nama saya David, dan inilah saya sendiri, diberikan oleh render tulisan tangan saya sendiri:





Sayangnya, saya tidak dapat menemukan model gratis dengan kualitas yang lebih baik , tetapi saya tetap berterima kasih kepada pematung luar negeri yang menangkap saya secara digital! Dan seperti yang Anda duga, kita akan berbicara tentang menulis render CPU.

Ide

Dengan perkembangan bahasa shader dan peningkatan kekuatan GPU, semakin banyak orang yang tertarik dengan pemrograman grafis. Arah baru telah muncul, seperti Ray berbaris dengan popularitas yang berkembang pesat.



Untuk mengantisipasi rilis monster baru dari NVidia, saya memutuskan untuk menulis artikel saya sendiri (tabung dan sekolah lama) tentang dasar-dasar rendering pada CPU. Itu adalah cerminan dari pengalaman pribadi saya menulis render, dan di dalamnya saya akan mencoba menyampaikan konsep dan algoritma yang saya temui dalam proses coding. Perlu dipahami bahwa kinerja perangkat lunak ini akan sangat rendah karena ketidaksesuaian prosesor untuk melakukan tugas-tugas tersebut.



Pilihan bahasa awalnya jatuh ke c ++ atau rust , tetapi saya memilih c #karena kemudahan penulisan kode dan banyak peluang untuk pengoptimalan. Produk akhir dari artikel ini adalah render yang mampu menghasilkan gambar seperti ini:







Semua model yang saya gunakan di sini didistribusikan di domain publik, jangan membajak dan menghormati karya seniman!

Matematika

Tak perlu dikatakan lagi di mana menulis render tanpa memahami dasar matematika mereka. Di bagian ini, saya hanya akan membahas konsep yang saya gunakan dalam kode. Saya tidak menyarankan mereka yang tidak yakin dengan pengetahuannya untuk melewatkan bagian ini, tanpa memahami dasar-dasar ini akan sulit untuk memahami presentasi selanjutnya. Saya juga berharap bahwa mereka yang memutuskan untuk mempelajari geometri komputasi akan memiliki pengetahuan dasar tentang aljabar linier, geometri, serta trigonometri (sudut, vektor, matriks, perkalian titik). Bagi mereka yang ingin memahami geometri komputasi lebih dalam, saya dapat merekomendasikan buku oleh E. Nikulin "Geometri Komputer dan Algoritma Grafik Komputer" .

Vektor berubah. Matriks rotasi

Rotasi adalah salah satu transformasi linier dasar dari ruang vektor. Ini juga merupakan transformasi ortogonal, karena mempertahankan panjang vektor yang ditransformasikan. Ada dua jenis rotasi dalam ruang 2D:

• Rotasi relatif terhadap asalnya
• Rotasi tentang beberapa titik

Di sini saya hanya akan mempertimbangkan tipe pertama, karena yang kedua adalah turunan dari yang pertama dan hanya berbeda dalam perubahan sistem koordinat rotasi (kita akan menganalisis sistem koordinat lebih lanjut).



Mari kita turunkan rumus untuk memutar vektor dalam ruang dua dimensi. Mari kita tunjukkan koordinat vektor asli - {x, y} . Koordinat vektor baru yang diputar melalui sudut f akan dilambangkan sebagai {x 'y'} .





Kita tahu bahwa panjang vektor-vektor ini adalah umum dan oleh karena itu kita dapat menggunakan konsep cosinus dan sinus untuk menyatakan vektor-vektor ini dalam bentuk panjang dan sudut sumbu OX :





Perhatikan bahwa kita dapat menggunakan rumus sum dan cosinus untuk memperluas nilai x ' dan y' . Bagi yang sudah lupa, saya akan mengingatkan rumus ini:





Memperluas koordinat vektor yang diputar melalui mereka, kita mendapatkan:





Di sini mudah untuk melihat bahwa faktor l * cos a dan l * sin a adalah koordinat dari vektor asli: x = l * cos a, y = l * sin a . Mari kita ganti dengan x dan y :





Jadi, kami menyatakan vektor yang diputar dalam hal koordinat vektor asli dan sudut rotasinya. Sebagai matriks, ekspresi ini akan terlihat seperti ini:





Kalikan dan periksa apakah hasilnya sama dengan yang kita simpulkan.

Putar dalam ruang 3D

Kami telah mempertimbangkan rotasi dalam ruang dua dimensi, dan juga menurunkan matriks untuk itu. Sekarang muncul pertanyaan, bagaimana cara mendapatkan transformasi seperti itu untuk tiga dimensi? Dalam kasus dua dimensi, kita merotasi vektor pada sebuah bidang, di sini terdapat sejumlah bidang tak terhingga yang relatif untuk kita lakukan ini. Namun, ada tiga jenis rotasi dasar yang dapat digunakan untuk menyatakan rotasi apa pun dari vektor dalam ruang tiga dimensi - ini adalah rotasi XY , XZ , YZ . Rotasi



XY .



Dengan rotasi ini, kami memutar vektor di sekitar sumbu OZ dari sistem koordinat. Bayangkan bahwa vektor adalah bilah helikopter dan sumbu OZ adalah tiang yang dipegangnya. Dengan XYrotasi vektor akan berputar di sekitar sumbu OZ , seperti bilah helikopter relatif terhadap tiang.





Perhatikan bahwa dengan rotasi ini, z koordinat vektor tidak berubah, tapi x dan x koordinat perubahan - itu sebabnya ini disebut XY rotasi.





Tidaklah sulit untuk mendapatkan rumus untuk rotasi seperti itu: z - koordinatnya tetap sama, dan x dan y berubah sesuai dengan prinsip yang sama seperti pada rotasi 2D.





Hal yang sama dalam bentuk matriks:





Untuk rotasi XZ dan YZ , semuanya sama:

Proyeksi

Konsep proyeksi dapat berbeda-beda bergantung pada konteks penggunaannya. Banyak yang mungkin telah mendengar tentang konsep seperti proyeksi ke bidang atau proyeksi ke sumbu koordinat.



Dalam pengertian yang kita gunakan di sini, proyeksi ke vektor juga merupakan vektor. Koordinatnya adalah titik potong tegak lurus yang dijatuhkan dari vektor a ke b dengan vektor b .





Untuk mendefinisikan vektor seperti itu, kita perlu mengetahui panjang dan arahnya . Seperti yang kita ketahui, kaki yang berdekatan dan sisi miring dalam segitiga siku-siku terkait dengan rasio kosinus, jadi kami menggunakannya untuk menyatakan panjang vektor proyeksi:





Arah vektor proyeksi menurut definisi bertepatan dengan vektor b , yang berarti proyeksi ditentukan dengan rumus:





Di sini kita mendapatkan arah proyeksi sebagai vektor satuan dan mengalikannya dengan panjang proyeksi. Tidak sulit untuk memahami bahwa hasilnya akan persis seperti yang kita cari.



Sekarang mari kita gambarkan semuanya dalam hal produk titik :





Kami mendapatkan rumus yang mudah untuk menemukan proyeksi:

Sistem koordinat. Basis

Banyak yang terbiasa bekerja dalam sistem koordinat XYZ standar , di mana 2 sumbu akan tegak lurus satu sama lain, dan sumbu koordinat dapat direpresentasikan sebagai vektor satuan:





Faktanya, ada banyak sistem koordinat yang tak terhingga, masing-masing merupakan basis . Basis dari ruang dimensi- n adalah himpunan vektor {v1, v2 …… vn} yang melaluinya semua vektor ruang ini direpresentasikan. Dalam hal ini, tidak ada vektor dari basis yang dapat direpresentasikan melalui vektor lainnya. Faktanya, setiap basis adalah sistem koordinat terpisah di mana vektor akan memiliki koordinat uniknya sendiri.



Mari kita lihat apa dasar dari ruang dua dimensi. Ambil, misalnya, sistem koordinat Kartesius vektor X {1, 0} , Y {0, 1} , yang merupakan salah satu basis untuk ruang dua dimensi:







Vektor apa pun pada bidang dapat direpresentasikan sebagai jumlah vektor basis ini dengan koefisien tertentu, atau sebagai kombinasi linier . Ingat apa yang Anda lakukan saat Anda menuliskan koordinat vektor - Anda menulis x - koordinat, dan kemudian - y . Ini adalah bagaimana Anda sebenarnya menentukan koefisien muai dalam hal vektor basis.







Sekarang mari kita ambil dasar lain:







Vektor 2D apa pun juga dapat direpresentasikan melalui vektornya:







Tetapi kumpulan vektor seperti itu bukanlah dasar dari ruang dua dimensi:







Di dalamnya, dua vektor {1,1} dan {2,2} terletak pada satu garis lurus. Apa pun kombinasinya yang Anda ambil, Anda hanya akan menerima vektor yang terletak pada garis lurus umum y = x . Untuk tujuan kami, yang cacat seperti itu tidak akan berguna, namun, saya pikir perlu dipahami perbedaannya. Menurut definisi, semua basis disatukan oleh satu properti - tidak ada vektor basis yang dapat direpresentasikan sebagai jumlah dari vektor basis lainnya dengan koefisien, atau tidak ada vektor basis yang merupakan kombinasi linier dari yang lain. Berikut contoh himpunan 3 vektor yang juga bukan basis :







Vektor apa pun dari bidang dua dimensi dapat diekspresikan melaluinya , tetapi vektor {1, 1} di dalamnya berlebihan, karena vektor itu sendiri dapat diekspresikan melalui vektor {1, 0} dan {0,1} sebagai {1,0} + {0,1 } .



Secara umum, setiap basis dari ruang berdimensi - n akan mengandung tepat n vektor, untuk 2e n ini sama dengan 2.



Mari kita beralih ke 3d. Basis tiga dimensi akan berisi 3 vektor:







Jika untuk basis dua dimensi cukup dua vektor tidak terletak pada satu garis lurus, maka dalam ruang tiga dimensi himpunan vektor akan menjadi basis jika:

• 1) 2 vektor tidak terletak pada satu garis lurus
• 2) ketiga tidak terletak pada bidang yang dibentuk oleh dua lainnya.

Mulai sekarang, basis yang kita gunakan akan menjadi ortogonal (salah satu vektornya tegak lurus) dan dinormalisasi (panjang setiap vektor basis adalah 1). Kami tidak membutuhkan orang lain. Misalnya dasar standar







memenuhi kriteria ini.

Transisi ke basis lain

Sampai saat ini, kami telah menulis dekomposisi sebuah vektor sebagai penjumlahan dari vektor basis dengan koefisien:





Perhatikan kembali basis standarnya - vektor {1, 3, 6} di dalamnya dapat ditulis sebagai berikut:





Seperti yang Anda lihat, koefisien muai suatu vektor pada dasarnya adalah koordinatnya pada basis ini . Mari kita lihat contoh berikut ini:







Basis ini diturunkan dari standar dengan menerapkan rotasi 45 derajat XY padanya . Ambil vektor a dalam sistem standar dengan koordinat {0, 1, 1}







Melalui vektor basis baru, dapat diperluas sebagai berikut:







Jika Anda menghitung jumlah ini, Anda akan mendapatkan {0, 1, 1} - vektor a dalam basis standar. Berdasarkan ekspresi ini dalam basis baru vektor a memiliki koordinat {0.7, 0.7, 1} - koefisien muai. Ini akan lebih terlihat jika Anda melihat dari sudut yang berbeda:







Tetapi bagaimana Anda menemukan koefisien ini? Secara umum, metode universal adalah solusi dari sistem persamaan linier yang agak kompleks. Namun, seperti yang saya katakan sebelumnya, kami hanya akan menggunakan basis ortogonal dan dinormalisasi , dan bagi mereka ada cara yang sangat curang. Ini terdiri dari menemukan proyeksi ke vektor basis. Mari kita gunakan untuk mencari dekomposisi vektor a dalam basis X {0.7, 0.7, 0} Y {-0.7, 0.7, 0} Z {0, 0, 1}







Pertama, mari kita cari koefisien untuk y ' . Langkah pertama adalah mencari proyeksi vektor a ke vektor y ' (saya membahas cara melakukan ini di atas):







Langkah kedua: kita membagi panjang proyeksi yang ditemukan dengan panjang vektor y ' , dengan demikian kita menemukan "berapa banyak vektor y' yang sesuai dengan vektor proyeksi" - bilangan ini akan menjadi koefisien untuk y ' , dan juga y - koordinat vektor a dalam basis baru! Untuk x ' dan z', ulangi operasi serupa:







Sekarang kami memiliki rumus untuk transisi dari dasar standar ke yang baru:







Nah, karena kita hanya menggunakan basis yang dinormalisasi dan panjang vektornya sama dengan 1, tidak perlu membagi dengan panjang vektor dalam rumus transisi:







Perluas koordinat x- melalui rumus proyeksi:







Perhatikan bahwa penyebut (x ', x') dan vektor x ' dalam kasus basis ternormalisasi juga sama dengan 1 dan dapat dibuang. Kita mendapatkan:







Kita melihat bahwa basis x koordinat dinyatakan sebagai produk skalar dari (a, x ') , koordinat y , masing-masing - keduanya (a, y') , koordinat z - (a, z ') . Sekarang Anda dapat membuat matriks transisi ke koordinat baru:

Sistem Koordinat Offset

Semua sistem koordinat yang kami pertimbangkan di atas memiliki asal titik {0,0,0} . Selain itu, ada juga sistem dengan titik asal yang bergeser:







Untuk menerjemahkan vektor ke dalam sistem seperti itu, Anda harus terlebih dahulu mengekspresikannya secara relatif ke pusat koordinat yang baru. Untuk melakukan ini sederhana - kurangi pusat ini dari vektor. Jadi, Anda semacam "memindahkan" sistem koordinat itu sendiri ke pusat baru, sementara vektor tetap di tempatnya. Selanjutnya, Anda dapat menggunakan matriks transisi yang sudah kita kenal.

Menulis mesin geometri. Buat render seperti kawat.

Yah, saya pikir seseorang yang membaca bagian dengan matematika dan tidak menutup artikel dapat dicuci otak dengan hal-hal yang lebih menarik! Di bagian ini, kita akan mulai menulis dasar-dasar mesin 3D dan rendering. Secara umum, rendering adalah prosedur yang agak rumit yang mencakup banyak operasi berbeda: memotong tepi yang tak terlihat, rasterisasi, menghitung cahaya, memproses berbagai efek, material (terkadang bahkan fisika). Kami akan menganalisis sebagian semua ini di masa mendatang, tetapi sekarang kami akan melakukan hal-hal yang lebih sederhana - kami akan menulis render kawat . Intinya adalah menggambar sebuah objek berupa garis-garis yang menghubungkan simpul-simpulnya, sehingga hasilnya tampak seperti jaringan kabel:

Grafik poligonal

Secara tradisional, grafik komputer menggunakan representasi poligonal dari data objek 3D. Dengan demikian, data disajikan dalam OBJ, 3DS, FBX dan banyak lainnya. Di komputer, data tersebut disimpan dalam bentuk dua set: satu set simpul dan satu set wajah (poligon). Setiap simpul dari sebuah objek diwakili oleh posisinya dalam ruang - sebuah vektor, dan setiap wajah (poligon) diwakili oleh tiga bilangan bulat yang merupakan indeks dari simpul dari objek ini. Objek paling sederhana (kubus, bola, dll.) Terdiri dari poligon seperti itu dan disebut primitif.



Di mesin kami, primitif akan menjadi objek utama geometri 3D - semua objek lain akan mewarisi darinya. Mari kita gambarkan kelas primitif:

    abstract class Primitive
    {
        public Vector3[] Vertices { get; protected set; }
        public int[] Indexes { get; protected set; }
    }

Sejauh ini, semuanya sederhana - ada simpul primitif dan ada indeks untuk membentuk poligon. Sekarang Anda dapat menggunakan kelas ini untuk membuat kubus:

   public class Cube : Primitive
      {
        public Cube(Vector3 center, float sideLen)
        {
            var d = sideLen / 2;
            Vertices = new Vector3[]
                {
                    new Vector3(center.X - d , center.Y - d, center.Z - d) ,
                    new Vector3(center.X - d , center.Y - d, center.Z) ,
                    new Vector3(center.X - d , center.Y , center.Z - d) ,
                    new Vector3(center.X - d , center.Y , center.Z) ,
                    new Vector3(center.X + d , center.Y - d, center.Z - d) ,
                    new Vector3(center.X + d , center.Y - d, center.Z) ,
                    new Vector3(center.X + d , center.Y + d, center.Z - d) ,
                    new Vector3(center.X + d , center.Y + d, center.Z + d) ,
                };

            Indexes = new int[]
                {
                    1,2,4 ,
                    1,3,4 ,
                    1,2,6 ,
                    1,5,6 ,
                    5,6,8 ,
                    5,7,8 ,
                    8,4,3 ,
                    8,7,3 ,
                    4,2,8 ,
                    2,8,6 ,
                    3,1,7 ,
                    1,7,5
                };
        }
    }

int Main()
{
        var cube = new Cube(new Vector3(0, 0, 0), 2);
}

Menerapkan sistem koordinat

Tidaklah cukup hanya mengatur objek dengan sekumpulan poligon; untuk merencanakan dan membuat pemandangan yang kompleks, Anda perlu menempatkan objek di tempat yang berbeda, memutarnya, memperkecil atau menambah ukurannya. Untuk kenyamanan operasi ini, yang disebut sistem koordinat lokal dan global digunakan. Setiap objek di tempat kejadian memiliki sistem koordinatnya sendiri - lokal, serta titik pusatnya sendiri.





Representasi suatu objek dalam koordinat lokal memungkinkan Anda melakukan operasi apa pun dengan mudah. Misalnya, untuk memindahkan objek dengan vektor a , itu akan cukup untuk menggeser pusat sistem koordinatnya dengan vektor ini, untuk memutar objek - putar koordinat lokalnya.



Saat bekerja dengan suatu objek, kami akan melakukan operasi dengan simpulnya di sistem koordinat lokal; selama rendering, pertama-tama kami akan menerjemahkan semua objek dalam pemandangan ke dalam satu sistem koordinat - sistem global. Mari tambahkan sistem koordinat ke kode. Untuk melakukan ini, buat objek dari kelas Pivot (pivot, titik pivot), yang akan mewakili basis lokal objek dan titik pusatnya. Mengonversi titik menjadi sistem koordinat yang disajikan oleh Pivot akan dilakukan dalam 2 langkah:

• 1) Representasi suatu titik yang relatif terhadap pusat koordinat baru
• 2) Ekspansi dalam vektor basis baru

Sebaliknya, untuk merepresentasikan simpul lokal suatu objek dalam koordinat global, Anda harus melakukan tindakan ini dalam urutan terbalik:

• 1) Ekspansi dalam vektor basis global
• 2) Representasi relatif terhadap pusat global

Mari tulis kelas untuk merepresentasikan sistem koordinat:

    public class Pivot
    {
        // 
        public Vector3 Center { get; private set; }
        //   -   
        public Vector3 XAxis { get; private set; }
        public Vector3 YAxis { get; private set; }
        public Vector3 ZAxis { get; private set; }

        //    
        public Matrix3x3 LocalCoordsMatrix => new Matrix3x3
            (
                XAxis.X, YAxis.X, ZAxis.X,
                XAxis.Y, YAxis.Y, ZAxis.Y,
                XAxis.Z, YAxis.Z, ZAxis.Z
            );

        //    
        public Matrix3x3 GlobalCoordsMatrix => new Matrix3x3
            (
                XAxis.X , XAxis.Y , XAxis.Z,
                YAxis.X , YAxis.Y , YAxis.Z,
                ZAxis.X , ZAxis.Y , ZAxis.Z
            );

        public Vector3 ToLocalCoords(Vector3 global)
        {
            //          
            return LocalCoordsMatrix * (global - Center);
        }
        public Vector3 ToGlobalCoords(Vector3 local)
        {
            //    -            
            return (GlobalCoordsMatrix * local)  + Center;
        }

        public void Move(Vector3 v)
        {
            Center += v;
        }

        public void Rotate(float angle, Axis axis)
        {
            XAxis = XAxis.Rotate(angle, axis);
            YAxis = YAxis.Rotate(angle, axis);
            ZAxis = ZAxis.Rotate(angle, axis);
        }
    }

Sekarang, dengan menggunakan kelas ini, tambahkan fungsi rotasi, gerakan, dan tingkatkan ke primitif:

    public abstract class Primitive
    {
        //  
        public Pivot Pivot { get; protected set; }
        // 
        public Vector3[] LocalVertices { get; protected set; }
        // 
        public Vector3[] GlobalVertices { get; protected set; }
        // 
        public int[] Indexes { get; protected set; }

        public void Move(Vector3 v)
        {
            Pivot.Move(v);

            for (int i = 0; i < LocalVertices.Length; i++)
                GlobalVertices[i] += v;
        }

        public void Rotate(float angle, Axis axis)
        {
            Pivot.Rotate(angle , axis);

            for (int i = 0; i < LocalVertices.Length; i++)
                GlobalVertices[i] = Pivot.ToGlobalCoords(LocalVertices[i]);
        }

        public void Scale(float k)
        {
            for (int i = 0; i < LocalVertices.Length; i++)
                LocalVertices[i] *= k;

            for (int i = 0; i < LocalVertices.Length; i++)
                GlobalVertices[i] = Pivot.ToGlobalCoords(LocalVertices[i]);
        }
    }

Memutar dan Memindahkan Objek Menggunakan Koordinat Lokal

Menggambar poligon. Kamera

Objek utama dari pemandangan tersebut adalah kamera - dengan bantuannya objek akan digambar di layar. Kamera, seperti semua objek dalam pemandangan, akan memiliki koordinat lokal dalam bentuk objek kelas Pivot - melaluinya kita akan bergerak dan memutar kamera:





Untuk menampilkan objek di layar, kita akan menggunakan metode proyeksi perspektif sederhana . Prinsip yang mendasari metode ini adalah bahwa semakin jauh dari kita objeknya, semakin kecil tampilannya . Mungkin banyak sekali dipecahkan di sekolah masalah mengukur tinggi pohon pada jarak tertentu dari pengamat:





Bayangkan sebuah sinar dari puncak pohon jatuh pada bidang proyeksi tertentu yang terletak pada jarak C1 dari pengamat dan menggambar sebuah titik di atasnya. Pengamat melihat titik ini dan ingin menentukan ketinggian pohon darinya. Seperti yang Anda lihat, tinggi pohon dan ketinggian suatu titik pada bidang proyeksi terkait dengan rasio segitiga serupa. Kemudian pengamat dapat menentukan ketinggian titik menggunakan rasio ini:







Sebaliknya, dengan mengetahui ketinggian pohon, dia dapat menemukan ketinggian sebuah titik pada bidang proyeksi:







Sekarang mari kembali ke kamera kita. Bayangkan bahwa sebuah pesawat proyeksi melekat pada z sumbu koordinat kamera pada jarak z ' dari asal. Rumus bidang tersebut adalah z = z ' , dapat diberikan dengan satu angka - z' . Sinar dari simpul berbagai objek jatuh pada bidang ini. Saat sinar menghantam pesawat, ia akan meninggalkan satu titik di atasnya. Dengan menghubungkan titik-titik tersebut, Anda dapat menggambar sebuah objek.







Pesawat ini akan mewakili layar. Kami akan menemukan koordinat proyeksi simpul objek di layar dalam 2 tahap:

• 1) Kami menerjemahkan simpul ke dalam koordinat lokal kamera
• 2) Temukan proyeksi suatu titik melalui rasio segitiga serupa

Proyeksi akan menjadi vektor 2 dimensi, koordinat x 'dan y' nya akan menentukan posisi titik pada layar komputer.





Kode ini memiliki beberapa kesalahan, yang akan kita bicarakan nanti untuk memperbaikinya.

Potong poligon yang tidak terlihat

Setelah memproyeksikan tiga titik poligon di layar dengan cara ini, kami mendapatkan koordinat segitiga yang sesuai dengan tampilan poligon di layar. Tetapi dengan cara ini kamera akan memproses simpul apa pun , termasuk yang proyeksinya melampaui area layar, jika Anda mencoba menggambar simpul seperti itu, ada kemungkinan tinggi untuk menangkap kesalahan. Kamera juga akan memproses poligon yang ada di belakangnya (koordinat z titik mereka di dasar kamera lokal kurang dari z ' ) - kita juga tidak memerlukan penglihatan "oksipital" seperti itu.







Untuk memotong simpul tak terlihat di gl terbuka, metode piramida pemotongan digunakan. Ini terdiri dari pengaturan dua bidang - dekat (bidang dekat) dan jauh (bidang jauh). Segala sesuatu yang terletak di antara kedua bidang ini akan diproses lebih lanjut. Saya menggunakan versi yang disederhanakan dengan satu bidang kliping - z ' . Semua simpul di belakangnya tidak akan terlihat.



Mari tambahkan dua bidang baru ke kamera - lebar dan tinggi layar.

Sekarang kita akan memeriksa setiap titik yang diproyeksikan untuk mencapai area layar. Mari kita juga memotong titik di belakang kamera. Jika titik berada di belakang atau proyeksinya tidak jatuh pada layar, maka metode akan mengembalikan titik {float.NaN, float.NaN} .

Menerjemahkan ke koordinat layar

Di sini saya akan menjelaskan satu hal. Hal ini terkait dengan fakta bahwa di banyak pustaka grafik, penggambaran berlangsung dalam sistem koordinat layar, dalam koordinat seperti itu, asalnya adalah titik kiri atas layar, x meningkat saat bergerak ke kanan, dan y saat bergerak ke bawah. Dalam bidang proyeksi kami, titik direpresentasikan dalam koordinat Cartesian biasa , dan sebelum menggambar, koordinat ini harus diubah menjadi koordinat layar. Ini mudah dilakukan, Anda hanya perlu menggeser titik awal ke pojok kiri atas dan membalik y :

Menyesuaikan ukuran gambar yang diproyeksikan

Jika Anda menggunakan kode sebelumnya untuk menggambar objek, Anda akan mendapatkan sesuatu seperti ini:







Untuk beberapa alasan, semua objek digambar sangat kecil. Untuk memahami alasannya, ingatlah bagaimana kita menghitung proyeksi - kita mengalikan koordinat x dan y dengan delta rasio z '/ z . Artinya, ukuran objek di layar bergantung pada jarak ke bidang proyeksi z ' . Tapi kita bisa mengatur z ' sekecil yang kita mau. Ini berarti kita perlu menyesuaikan ukuran proyeksi tergantung pada nilai z saat ini . Untuk melakukan ini, mari tambahkan bidang lain ke kamera - sudut pandangnya .







Kami membutuhkannya untuk menyesuaikan ukuran sudut layar dengan lebarnya. Sudut akan disesuaikan dengan lebar layar dengan cara ini: sudut maksimum yang dilihat kamera adalah tepi kiri atau kanan layar. Kemudian sudut maksimum dari sumbu z kamera adalah o / 2 . Proyeksi yang jatuh di tepi kanan layar harus memiliki koordinat x = width / 2 , dan di sebelah kiri: x = -width / 2 . Mengetahui hal ini, kami memperoleh rumus untuk mencari koefisien regangan proyeksi:









Berikut kode rendering sederhana yang saya gunakan untuk pengujian:





Mari kita periksa render di tempat kejadian dan kubus:







Dan ya, semuanya bekerja dengan baik. Bagi mereka yang tidak menemukan kubus warna-warni yang megah, saya menulis fungsi untuk mem-parsing model format OBJ menjadi objek Primitif, mengisi latar belakang dengan warna hitam dan memberikan beberapa model:

Rasterisasi poligon. Kami menghadirkan keindahan.

Di bagian terakhir, kami menulis render wireframe. Sekarang kita akan membahas modernisasi - kita akan menerapkan rasterisasi poligon.



Cukup rasterizing poligon cara melukis di atas. Tampaknya mengapa menulis sepeda ketika sudah ada fungsi rasterisasi segitiga yang sudah jadi. Inilah yang terjadi jika Anda menggambar semuanya dengan alat default:







Seni kontemporer, poligon di belakang yang depan digambar, singkatnya - bubur. Juga, bagaimana Anda memberi tekstur pada objek dengan cara ini? Ya tidak mungkin. Jadi kita perlu membuat rasterizer imba kita sendiri, yang akan dapat memotong titik , tekstur, dan bahkan bayangan yang tidak terlihat! Tetapi untuk melakukan ini, ada baiknya memahami cara melukis segitiga secara umum.

Algoritma Bresenham untuk Gambar Garis.

Mari kita mulai dengan garis. Jika ada yang belum mengetahui algoritma Bresenham, inilah algoritma utama untuk menggambar garis lurus dalam grafik komputer. Dia atau modifikasinya digunakan secara harfiah di mana-mana: menggambar garis, segmen, lingkaran, dll. Siapapun yang tertarik dengan deskripsi yang lebih rinci - baca wiki. Algoritma Bresenham



Ada ruas garis yang menghubungkan titik-titik {x1, y1} dan {x2, y2} . Untuk menggambar segmen di antara mereka, Anda perlu mengecat semua piksel yang jatuh di atasnya. Untuk dua titik segmen, Anda dapat menemukan koordinat x dari piksel tempat mereka berada: Anda hanya perlu mengambil seluruh bagian koordinat x1 dan x2 . Untuk melukis piksel pada segmen, kami memulai siklus dari x1 ke x2 dan pada setiap iterasi kami menghitungy - koordinat piksel yang jatuh pada garis. Ini kodenya:

void Brezenkhem(Vector2 p1 , Vector2 p2)
{
    int x1 = Floor(p1.X);
    int x2 = Floor(p2.X);
    if (x1 > x2) {Swap(x1, x2); Swap(p1 , p2);}
    float d = (p2.Y - p1.Y) / (x2 - x1);
    float y = p1.Y;
    for (int i = x1; i <= x2; i++)
    {
        int pixelY = Floor(y);
        FillPixel(i , pixelY);
        y += d;
    }
}

Gambar dari wiki

Rasterisasi segitiga. Isi Algoritma

Kita tahu cara menggambar garis, tetapi dengan segitiga itu akan sedikit lebih sulit (tidak banyak)! Tugas menggambar segitiga direduksi menjadi beberapa tugas menggambar garis. Pertama, mari kita pisahkan segitiga menjadi dua bagian, setelah sebelumnya mengurutkan titik-titik dalam urutan naik x :







Perhatikan - sekarang kita memiliki dua bagian di mana batas bawah dan atas diekspresikan dengan jelas . yang tersisa hanyalah mengisi semua piksel di antaranya! Ini dapat dilakukan dalam 2 siklus: dari x1 ke x2 dan dari x3 ke x2 .

void Triangle(Vector2 v1 , Vector2 v2 , Vector2 v3)
{
    // BubbleSort    x
    if (v1.X > v2.X) { Swap(v1, v2); }
    if (v2.X > v3.X) { Swap(v2, v3); }
    if (v1.X > v2.X) { Swap(v1, v2); }

    //    y    x
    //   0:  x1 == x2     - 
    var steps12 = max(v2.X - v1.X , 1);
    var steps13 = max(v3.X - v1.X , 1);
    var upDelta = (v2.Y - v1.Y) / steps12;
    var downDelta = (v3.Y - v1.Y) / steps13;

    //     
    if (upDelta < downDelta) Swap(upDelta , downDelta);

    //     y1
    var up = v1.Y;
    var down = v1.Y;

    for (int i = (int)v1.X; i <= (int)v2.X; i++)
    {
        for (int g = (int)down; g <= (int)up; g++)
        {
            FillPixel(i , g);
        }
        up += upDelta;
        down += downDelta;
    }

    //       
    var steps32 = max(v2.X - v3.X , 1);
    var steps31 = max(v1.X - v3.X , 1);
    upDelta = (v2.Y - v3.Y) / steps32;
    downDelta = (v1.Y - v3.Y) / steps31;

    if (upDelta < downDelta) Swap(upDelta, downDelta);

    up = v3.Y;
    down = v3.Y;

    for (int i = (int)v3.X; i >=(int)v2.X; i--)
    {
        for (int g = (int)down; g <= (int)up; g++)
        {
            FillPixel(i, g);
        }
        up += upDelta;
        down += downDelta;
    }
}

Tidak diragukan lagi, kode ini dapat difaktorisasi ulang dan tidak untuk menduplikasi loop:

void Triangle(Vector2 v1 , Vector2 v2 , Vector2 v3)
{
    if (v1.X > v2.X) { Swap(v1, v2); }
    if (v2.X > v3.X) { Swap(v2, v3); }
    if (v1.X > v2.X) { Swap(v1, v2); }

    var steps12 = max(v2.X - v1.X , 1);
    var steps13 = max(v3.X - v1.X , 1);
    var steps32 = max(v2.X - v3.X , 1);
    var steps31 = max(v1.X - v3.X , 1);

    var upDelta = (v2.Y - v1.Y) / steps12;
    var downDelta = (v3.Y - v1.Y) / steps13;
    if (upDelta < downDelta) Swap(upDelta , downDelta);

    TrianglePart(v1.X , v2.X , v1.Y , upDelta , downDelta);

    upDelta = (v2.Y - v3.Y) / steps32;
    downDelta = (v1.Y - v3.Y) / steps31;
    if (upDelta < downDelta) Swap(upDelta, downDelta);

    TrianglePart(v3.X, v2.X, v3.Y, upDelta, downDelta);
}

void TrianglePart(float x1 , float x2 , float y1  , float upDelta , float downDelta)
{
    float up = y1, down = y1;
    for (int i = (int)x1; i <= (int)x2; i++)
    {
        for (int g = (int)down; g <= (int)up; g++)
        {
            FillPixel(i , g);
        }
        up += upDelta; down += downDelta;
    }
}

Memotong titik tak terlihat.

Pertama, pikirkan tentang bagaimana Anda melihat. Sekarang ada layar di depan Anda, dan apa yang ada di belakangnya tersembunyi dari mata Anda. Dalam rendering, mekanisme serupa bekerja - jika satu poligon tumpang tindih dengan yang lain, render akan menggambarnya di atas poligon yang tumpang tindih. Sebaliknya, ini tidak akan menggambar bagian tertutup dari poligon:







Untuk memahami apakah titik-titik tersebut terlihat atau tidak, mekanisme zbuffer (buffer kedalaman) digunakan dalam rendering . zbuffer dapat dianggap sebagai array dua dimensi (dapat dikompresi menjadi satu dimensi) dengan lebar * tinggi . Untuk setiap piksel di layar, ia menyimpan nilai z - koordinat pada poligon asli tempat titik ini diproyeksikan. Dengan demikian, semakin dekat titik ke pengamat, semakin kecil koordinat z- nya. Akhirnya, jika proyeksi beberapa titik bertepatan, Anda perlu meraster titik tersebut dengan koordinat-z minimum :







Sekarang muncul pertanyaan - bagaimana menemukan koordinat z- titik pada poligon asli? Hal ini dapat dilakukan dengan beberapa cara. Misalnya, Anda bisa membidik sinar dari kamera asli, melewati sebuah titik pada bidang proyeksi {x, y, z '} dan menemukan perpotongannya dengan poligon. Tetapi mencari persimpangan adalah operasi yang sangat mahal, jadi kami akan menggunakan metode yang berbeda. Untuk menggambar segitiga, kami menginterpolasi koordinat proyeksinya , sekarang, selain ini, kami juga akan menginterpolasi koordinat poligon asli . Untuk memotong titik yang tidak terlihat, kita akan menggunakan status zbuffer untuk frame saat ini dalam metode rasterization . Zbuffer



saya akan terlihat sepertiVector3 [] - tidak hanya berisi koordinat z - , tetapi juga nilai titik poligon (fragmen) yang diinterpolasi untuk setiap piksel layar. Ini dilakukan untuk menghemat memori, karena di masa mendatang kita masih membutuhkan nilai-nilai ini untuk menulis shader ! Sementara itu, kami memiliki kode berikut untuk menentukan simpul yang terlihat (fragmen) :







Animasi langkah-langkah rasterizer (saat menulis ulang kedalaman di zbuffer, pikselnya disorot dengan warna merah):



Untuk kenyamanan, saya memindahkan semua kode ke modul Rasterizer terpisah:





Sekarang mari kita periksa pekerjaan render. Untuk ini, saya menggunakan model Sylvanas dari RPG terkenal "WOW":







Tidak terlalu jelas, bukan? Ini karena tidak ada tekstur atau pencahayaan di sini. Tapi kami akan segera memperbaikinya.

Tekstur! Normal! Petir! Motor!

Mengapa saya menggabungkan semuanya menjadi satu bagian? Dan karena pada dasarnya texturization dan perhitungan normals benar-benar identik dan Anda akan segera memahami ini.



Pertama, mari kita lihat tugas memberi tekstur untuk satu poligon. Sekarang, selain koordinat biasa dari simpul poligon, kami juga akan menyimpan koordinat teksturnya . Koordinat tekstur dari simpul direpresentasikan sebagai vektor 2D dan menunjuk ke sebuah piksel pada gambar tekstur. Saya menemukan gambar yang bagus di internet untuk menunjukkan ini:





Perhatikan bahwa awal tekstur ( piksel kiri bawah ) dalam koordinat tekstur adalah {0, 0} , dan akhir ( piksel kanan atas ) adalah {1, 1} . Mempertimbangkan sistem koordinat tekstur dan kemungkinan melampaui batas gambar saat koordinat tekstur adalah 1.



Mari buat kelas untuk merepresentasikan data simpul segera:

  public class Vertex
    {
        public Vector3 Position { get; set; }
        public Color Color { get; set; }
        public Vector2 TextureCoord { get; set; }
        public Vector3 Normal { get; set; }

        public Vertex(Vector3 pos , Color color , Vector2 texCoord , Vector3 normal)
        {
            Position = pos;
            Color = color;
            TextureCoord = texCoord;
            Normal = normal;
        }
    }

Saya akan menjelaskan mengapa normals diperlukan nanti, untuk saat ini kita hanya akan tahu bahwa simpul dapat memilikinya. Sekarang, untuk memberi tekstur pada poligon, kita perlu memetakan nilai warna dari tekstur ke piksel tertentu. Ingat bagaimana kita menginterpolasi simpul? Lakukan hal yang sama di sini! Saya tidak akan menulis ulang kode rasterisasi lagi, tetapi saya menyarankan Anda menerapkan tekstur pada render Anda sendiri. Hasilnya adalah tampilan tekstur yang benar pada model. Inilah yang saya dapatkan:







Semua informasi tentang koordinat tekstur model ada di file OBJ. Untuk menggunakan ini pelajari format: format OBJ.

Petir

Dengan tekstur semuanya menjadi jauh lebih menyenangkan, tetapi kesenangan sebenarnya adalah ketika kita menerapkan pencahayaan untuk pemandangan itu. Untuk mensimulasikan pencahayaan "murah", saya akan menggunakan model Phong .

Model Phong

Secara umum metode ini mensimulasikan keberadaan 3 komponen pencahayaan: latar belakang (ambient), hamburan (diffuse) dan cermin (refleks). Jumlah ketiga komponen ini pada akhirnya akan mensimulasikan perilaku fisik cahaya.





Model Phong



Untuk menghitung pencahayaan Phong kita membutuhkanpermukaan normal , untuk ini saya menambahkannya di kelas Vertex. Di mana kita bisa mendapatkan nilai-nilai normals ini? Tidak, kami tidak perlu menghitung apapun. Faktanya adalah bahwa editor 3D yang murah hati sering menganggapnya sendiri dan memberikan model bersama dengan data dalam konteks format OBJ. Setelah mem-parsing file model kita mendapatkan nilai normal untuk 3 simpul dari setiap poligon.





Gambar dari wiki



Untuk menghitung normal pada setiap titik pada poligon, Anda perlu menginterpolasi nilai-nilai ini, kita sudah tahu bagaimana melakukan ini. Sekarang mari kita lihat semua komponen untuk menghitung pencahayaan Phong.

Lampu latar (Ambien)

Awalnya, kami mengatur pencahayaan latar belakang konstan , untuk objek non-tekstur, Anda dapat memilih warna apa pun untuk objek dengan tekstur Saya membagi masing-masing komponen RGB dengan rasio shading dasar (baseShading).

Cahaya menyebar

Ketika cahaya menyentuh permukaan poligon, itu tersebar merata. Untuk menghitung nilai difus untuk piksel tertentu, sudut di mana cahaya menyentuh permukaan diperhitungkan . Untuk menghitung sudut ini, Anda dapat menerapkan perkalian titik dari sinar datang dan normal (tentu saja, vektor harus dinormalisasi sebelum itu). Sudut ini akan dikalikan dengan faktor intensitas cahaya. Jika perkalian titik negatif, berarti sudut antar vektor lebih besar dari 90 derajat. Dalam hal ini, kita akan mulai menghitung bukan keringanan, tetapi sebaliknya, bayangan. Sebaiknya hindari hal ini, Anda dapat melakukannya menggunakan fungsi max .





Mari terapkan cahaya yang tersebar dan hilangkan kegelapan:

Cahaya cermin (Refleksi)

Untuk menghitung komponen cermin, Anda perlu memperhitungkan titik dari mana kita melihat objek tersebut . Sekarang kita akan mengambil produk titik sinar dari pengamat dan sinar yang dipantulkan dari permukaan dikalikan dengan faktor intensitas cahaya.





Sangat mudah untuk menemukan sinar dari pengamat ke permukaan - ini akan menjadi posisi simpul yang diproses dalam koordinat lokal . Untuk menemukan sinar yang dipantulkan, saya menggunakan metode berikut. Sinar datang dapat diuraikan menjadi 2 vektor: proyeksinya ke dalam normal dan vektor kedua yang dapat ditemukan dengan mengurangkan proyeksi ini dari sinar datang. Untuk menemukan sinar yang dipantulkan, Anda perlu mengurangi nilai vektor kedua dari proyeksi ke normal.





Sekarang gambarnya terlihat seperti ini:

Bayangan

Titik akhir dari presentasi saya adalah implementasi bayangan untuk rendering. Ide buntu pertama yang berasal dari tengkorak saya adalah memeriksa setiap titik apakah ada poligon antara titik itu dan cahaya . Jika ya, Anda tidak perlu menerangi piksel. Model Sylvanas berisi lebih dari 220 ribu poligon. Jika demikian untuk setiap titik untuk memeriksa persimpangan dengan semua poligon ini, maka Anda perlu membuat maksimum 220000 * 1920 * 1080 * 219999 panggilan ke metode persimpangan! Dalam 10 menit, komputer saya dapat menguasai bagian ke-10 dari semua perhitungan (2600 poligon dari 220.000), setelah itu saya mendapat giliran kerja dan saya mencari metode baru.



Di Internet, saya menemukan cara yang sangat sederhana dan indah yang melakukan perhitungan yang samaribuan kali lebih cepat . Ini disebut pemetaan bayangan . Ingat bagaimana kami menentukan poin yang terlihat oleh pengamat - kami menggunakan zbuffer . Pemetaan bayangan melakukan hal yang sama! Pada lintasan pertama, kamera kita akan berada pada posisi terang dan melihat objek. Ini akan menghasilkan peta kedalaman untuk sumber cahaya. Peta kedalaman adalah zbuffer yang sudah dikenal. Langkah kedua, kami menggunakan peta ini untuk menentukan simpul mana yang harus diterangi. Sekarang saya akan melanggar aturan kode yang baik dan melakukan cheat - saya hanya memberikan objek rasterizer baru pada shader dan itu akan menggunakannya untuk membuat peta kedalaman untuk kita.





Untuk pemandangan statis, cukup memanggil konstruksi peta kedalaman satu kali, lalu menggunakannya di semua bingkai. Sebagai pengujian, saya menggunakan model pistol yang tidak terlalu poligonal. Ini adalah gambar keluarannya:







Banyak dari Anda mungkin telah memperhatikan artefak dari shader ini (titik hitam tidak diproses oleh cahaya). Sekali lagi, beralih ke jaringan mahatahu, saya menemukan deskripsi efek ini dengan nama jahat "jerawat bayangan" (maafkan saya orang dengan penampilan yang rumit). Inti dari "celah" tersebut adalah bahwa kami menggunakan resolusi terbatas dari peta kedalaman untuk menentukan bayangan. Artinya, beberapa simpul saat rendering menerima satu nilai dari peta kedalaman. Yang paling rentan terhadap artefak semacam itu adalah permukaan tempat cahaya jatuh pada sudut yang dangkal . Efeknya bisa dikoreksi dengan meningkatkan resolusi render dari lampu, tetapi ada cara yang lebih elegan . Itu terdiri dari penambahanpergeseran tertentu untuk kedalaman tergantung pada sudut antara berkas cahaya dan permukaan . Ini dapat dilakukan dengan menggunakan perkalian titik.

Kesimpulan

Saya menganggap diri saya seorang pemula dalam grafik 3D, saya tidak mengecualikan kesalahan yang saya buat selama presentasi. Satu-satunya hal yang saya andalkan adalah hasil praktis yang diperoleh dalam proses penciptaan. Anda dapat meninggalkan semua koreksi dan optimisasi (jika ada) di komentar, saya akan dengan senang hati membacanya. Tautkan ke repositori proyek .