Алгоритми и формули

Документация на растеризатора

Алгоритми и математически формули

Сцената се рисува изцяло със собствен код: линейна алгебра, орбитална камера, перспективна проекция, растеризация на триъгълници, Z-буфер, текстуриране и селекция на върхове. Няма Three.js, WebGL или други графични библиотеки.

1. Топология на мрежата

Мрежата е правоъгълна решетка с R реда клетки и C колони клетки. Броят на върховете е (R + 1) × (C + 1). Всеки връх V_i,j се индексира с ред i ∈ [0, R] и колона j ∈ [0, C].

Начална позиция в световни координати

V_i,j = ( (j − C / 2) · w , (i − R / 2) · h , 0 )

w е ширината на клетка, h е височината на клетка. Равнината на мрежата е XY, а Z е нормалата.

Всяка клетка е четириъгълник и се разбива на два триъгълника, за да може повърхността да се растеризира:

Два триъгълника за клетка (i, j)

T₁ = (V_i,j, V_i,j+1, V_i+1,j)

T₂ = (V_i,j+1, V_i+1,j+1, V_i+1,j)

Ръбовете са отсечки между съседни върхове по хоризонтала, вертикала и по диагонала на клетката. Текстурните координати (u, v) се разпределят равномерно върху цялата мрежа, така че зареденото изображение да покрива повърхността:

(u, v)_i,j = ( j / C , 1 − i / R )

2. Координатни пространства

Всяка точка минава през няколко пространства, преди да стане пиксел:

World (световно) — координатите на върховете на мрежата.
Camera / view — светът, видян от камерата. Камерата гледа по −Z.
Clip — след перспективната матрица; хомогенна точка (x, y, z, w).
NDC — нормализирани координати след деление на w.
Screen — пиксели върху платното.

3. Орбитална камера

Камерата обикаля около точката на интерес (центъра на мрежата) по сфера. Позицията се задава със сферични координати: ъгъл на завъртане около вертикалата yaw (ψ), ъгъл на издигане pitch (θ) и разстояние radius (ρ).

Позиция на камерата

E_x = T_x + ρ · cos(θ) · sin(ψ)

E_y = T_y + ρ · sin(θ)

E_z = T_z + ρ · cos(θ) · cos(ψ)

T е целевата точка. Pitch се ограничава, за да не се преобърне камерата при θ = ±90°.

Влаченето с левия бутон променя ъглите пропорционално на преместването на мишката:

ψ ← ψ + Δx · s

θ ← clamp(θ + Δy · s, −1.4, 1.4)

s е чувствителност в радиани на пиксел. Колелото на мишката променя ρ.

4. Матрица на изгледа (look-at)

Матрицата на изгледа преобразува световни координати в координати на камерата. Базисът на камерата се строи от позицията на окото E, целта T и световния вектор нагоре U = (0, 1, 0).

Ортонормиран базис

f̂ = normalize(T − E) (напред)

ŝ = normalize(f̂ × U) (надясно)

û = ŝ × f̂ (нагоре в камерата)

В камерно пространство камерата стои в началото и гледа по −Z, затова третият ред на матрицата е −f̂. Транслацията премахва позицията на окото:

View матрица 4×4

[  ŝx   ŝy   ŝz   −ŝ·E ]
[  ûx   ûy   ûz   −û·E ]
[ −f̂x  −f̂y  −f̂z    f̂·E ]
[   0    0    0      1  ]

5. Перспективна проекция

Перспективата прави далечните обекти по-малки. Ъгълът на зрителното поле е fov, отношението на страните е aspect = ширина / височина, а ближната и далечната равнина са n и f.

Фокусен мащаб

F = 1 / tan(fov / 2)

Перспективна матрица

[ F / aspect    0              0                    0            ]
[ 0             F              0                    0            ]
[ 0             0     (f + n) / (n − f)    (2 f n) / (n − f)     ]
[ 0             0             −1                    0            ]

След умножението се получава хомогенна точка C = (x_c, y_c, z_c, w_c). Делението на w възстановява перспективното свиване:

Нормализирани координати (NDC)

x_ndc = x_c / w_c

y_ndc = y_c / w_c

z_ndc = z_c / w_c

Преход към екранни пиксели

x_s = (x_ndc · 0.5 + 0.5) · W

y_s = (1 − (y_ndc · 0.5 + 0.5)) · H

Y се обръща, защото в NDC нагоре е +Y, а върху платното надолу е +Y.

6. Пълен графичен конвейер

За всеки връх V се изпълнява:

C = P · View · (V_x, V_y, V_z, 1)

ако w_c ≤ 0, точката е зад камерата и се отхвърля

Триъгълник, чиито три върха са зад ближната равнина, не се рисува. Обхождането на върховете (winding) определя предната страна. Ако ориентираната площ в екранни координати е отрицателна, триъгълникът е задна стена и се пропуска (back-face culling):

Двойна ориентирана площ

2S = (B_x − A_x)(C_y − A_y) − (C_x − A_x)(B_y − A_y)

При 2S ≤ 0 триъгълникът е обърнат с гръб към камерата.

7. Растеризация и барицентрични координати

Триъгълник със екранни върхове A, B, C покрива пикселите в ограничителния правоъгълник. За пиксел P се пресмятат барицентричните координати (α, β, γ):

Барицентрични тегла

α = площ(PBC) / площ(ABC)

β = площ(PCA) / площ(ABC)

γ = площ(PAB) / площ(ABC)

α + β + γ = 1

P е вътре в триъгълника точно когато α ≥ 0, β ≥ 0 и γ ≥ 0. Всяка интерполирана величина φ (цвят, дълбочина, текстура) е:

φ(P) = α · φ_A + β · φ_B + γ · φ_C

Това е същият принцип като линейна интерполация, но в двумерен симплекс. Площите се пресмятат чрез кръстосано произведение в 2D, което е евтино и стабилно.

8. Z-буфер (алгоритъм на дълбочината)

За всеки пиксел се пази най-малката видяна дълбочина. Нов фрагмент се записва само ако е по-близо до камерата. Така по-близките триъгълници закриват далечните без да е нужно сортиране (за разлика от алгоритъма на художника).

Тест за дълбочина

z(P) = α z_A + β z_B + γ z_C

ако z(P) < zBuffer[x, y] → запиши цвета и обнови буфера

Буферът се инициализира с +∞ в началото на всеки кадър. Използва се Float32Array с размер W × H. Цветовете се пишат директно в ImageData чрез Uint32Array.

9. Текстуриране с перспективна корекция

Линейната интерполация на (u, v) в екранното пространство е грешна при перспектива — текстурата „пълзи“. Правилната интерполация е по 1/w, защото перспективното деление е нелинейно.

Перспективно-коректни UV

invW(P) = α / w_A + β / w_B + γ / w_C

u(P) = (α · u_A / w_A + β · u_B / w_B + γ · u_C / w_C) / invW(P)

v(P) = (α · v_A / w_A + β · v_B / w_B + γ · v_C / w_C) / invW(P)

След това се чете тексел от изображението с най-близък съсед:

x_tex = floor(u · (ширина − 1))

y_tex = floor(v · (височина − 1))

Ако няма заредено изображение, фрагментът се оцветява с цвета на клетката, модулиран от осветяването.

10. Осветяване по Ламберт

За всеки триъгълник се пресмята нормала в световни координати. Светлината е насочена (без позиция), което е достатъчно, за да се чете релефът на мрежата.

Нормала на лице

N = normalize( (B − A) × (C − A) )

Интензитет

I = ambient + diffuse · max(0, N · L̂)

ambient ≈ 0.28, diffuse ≈ 0.72. I се умножава по RGB на цвета или на тексела.

Векторното произведение дава нормала, перпендикулярна на равнината на триъгълника. Скаларното произведение с посоката към светлината е косинусът на ъгъла между тях — законът на Ламберт.

11. Селекция на върхове

Върховете се рисуват като малки квадратчета в екранното пространство (бийлборди — винаги обърнати към камерата). Селекцията не използва лъч в 3D, а проверка в 2D след проекцията, което е точно за този интерфейс.

Попадане в квадратче

|x_mouse − x_s| ≤ half и |y_mouse − y_s| ≤ half

Ако няколко върха се припокриват, се избира този с най-малка камерна дълбочина (най-близкият). При задържане на курсора квадратчето се осветява; при клик върхът става активен и полетата X, Y, Z се пълнят с неговите световни координати.

Ако курсорът не е върху връх, влаченето с левия бутон върти камерата. Ако е върху връх, влаченето го плъзга в равнина, успоредна на екрана.

Лъч от камерата през пиксел

x_ndc = 2 · x_s / W − 1

y_ndc = 1 − 2 · y_s / H

посока в view: normalize( (x_ndc · aspect / F, y_ndc / F, −1) )

Равнината на плъзгане минава през върха и има нормала, равна на посоката на камерата. Сечението лъч–равнина дава новата позиция:

Сечение лъч–равнина

лъч: X(t) = E + t · D

равнина: N · (X − V) = 0

t = N · (V − E) / (N · D)

X = E + t · D при t > 0

12. Преместване на връх и посока на ръб

Ръбът е вектор между два върха. Ако се премести V_i,j, всеки свързан ръб променя посоката и дължината си.

Посока на ръб

D_horizontal = V_i,j+1 − V_i,j

D_vertical = V_i+1,j − V_i,j

единична посока: D̂ = D / ‖D‖

Полетата X, Y, Z записват директно световните координати на избрания връх. Промяната на Z повдига или снижава върха спрямо равнината на мрежата и така „огъва“ повърхността. Нормалите на съседните триъгълници се преизчисляват автоматично при следващия кадър, затова осветяването следва релефа.

При промяна на броя редове и колони мрежата се създава наново. При промяна само на ширината или височината на клетка X и Y се пренареждат по формулата от раздел 1, а изместването по Z се запазва.

Реализация в кода

js/math3d.js — вектори, матрици, проекция, лъчи и сечения.
js/camera.js — орбитална камера и матрици View / Projection.
js/mesh.js — върхове, триъгълници, ръбове и UV координати.
js/renderer.js — софтуерен растеризатор, Z-буфер, текстура, квадратчета.
js/app.js — връзка с интерфейса, селекция и цикъл на рисуване.