![[../../00 Asset Bank/Pasted image 20241028140759.png|invert_Sepia]] Given a lattice of [[Pixel|Pixels]] and a [[Triangle]] of points, to rasterize the shape you need to fill all pixels that are within the [[Triangle]]. >[!note]- Boundry >It is subjective / problem dependent whether or not you consider boundry of the [[Triangle]] as inside or out ## Math Model ### Most common Algorithm for most [[GPU|GPUs]] Given a triangle $\triangle PQR \in \Rn 2$ with points $P, Q, R$, where $\triangle PQR$ is [[Non-Degenerate]]. you start by creating the [[Bounding Box]] $\square ABCD$ for $\triangle PQR$. ![[../../00 Excalidraw/Triangle Rasterization .excalidraw.dark.svg]] %%[[../../00 Excalidraw/Triangle Rasterization .excalidraw.md|🖋 Edit in Excalidraw]], and the [[../../00 Excalidraw/Triangle Rasterization .excalidraw.light.svg|light exported image]]%% ```tikz \begin{tikzpicture}[step=1cm,gray,very thin] \draw (0, 0) -- (4, 2) \end{tikzpicture} ``` Then for every [[Pixel]] $p \in \square ABCD$ you check if $p \in \triangle PQR$, and if so you fill the pixel >[!tip] Efficiency >This algorithm is not the most efficient in terms of work, but it is highly [[Parallelizable]] which means it takes advantage of the [[GPU|GPU's]] strength In order to check if $p \in \triangle PQR$ you can use [[../Math/Barycentric Coordinates#Standard Form#Interiors|Barycentric Coordinates]]. $\huge \begin{align} \ba{\mu, \nu, \lambda}_{\triangle PQR} &= \pa{\mathcal{C}_{\Delta \to \triangle PQR }}^{-1} \circ p \\ &= \mat{ \tilde P & \tilde Q & \tilde R }^{-1} p \\ \end{align}$ $\huge \begin{align} p &=\lambda P + \mu Q + \nu R \\ 1 &= \lambda + \mu + \nu \end{align} $ With the [[../Math/Barycentric Coordinates|Barycentric Coordinates]] of $p$ you can do an [[../Math/Barycentric Coordinates#Interiors|Interior Check]] to see if $p \in \triangle PQR$. $\huge \begin{align} p \in \triangle PQR \iff \begin{cases} \lambda\ge 0 \\ \mu\ge 0 \\ \nu\ge 0 \\ \end{cases} \end{align} $ >[!example] >$\huge \begin{align} > >\let \triangle PQR &= \begin{cases} >P &= (10, 20) \\ >Q &= (70, 30) \\ >R &= (60, 80) >\end{cases} >\\ > >\let p &= (55, 43) \\ > >\pa{\mathcal C_{S\to \triangle PQR} }p &= \ba{0.2, 0.5, 0.3}_{\triangle PQR} \\ >\\ >0.2 &\ge 0 \\ >0.5 &\ge 0 \\ >0.3 &\ge 0 \\ >\\ >\therefore > >p &\in \triangle PQR >\end{align}$ ### [[../Math/Barycentric Coordinates|Barycentric Coordinates]] [[Function]] For any point $p$ in the [[Planes|Plane]] can be written uniquely as: $\huge p = \lambda_{p}P+ \mu_{p}Q+ \nu_{p}R $ $\huge \begin{align} \let \lambda &: I \mapsto \lambda_{p} \\ \let \mu &:I \mapsto \mu{p} \\ \let \nu &:I \mapsto \nu{p} \\ \end{align}$ Uniquely defined by the values: $\huge \begin{align} \begin{matrix} \lambda(P) = 1 & \mu(P) = 0 & \nu(P) = 0 & \\ \lambda(Q) = 0 & \mu(Q) = 1 & \nu(R) = 0 & \\ \lambda(R) = 0 & \nu(Q) = 0 & \nu(R) = 1 & \end{matrix} \end{align} $ #### [[../Math/Homogeneous Coordinates|Homogeneous]] Representation of [[../Math/Barycentric Coordinates|Barycentric Coordinates]] [[Function|Functions]] $\huge \begin{align} \lambda &= \mat{a\\b\\-d} \\ I &= (x,y)\\ \lambda_{I} &= \mat{a\\b\\-d} \cdot \tilde I = ax+bx-d \end{align}$ To compute a BC Coordinate Function for $\mu_p$: - Find the vector $\vec m \perp \overline{PR}$ (determined by the line that does not contain the [[Point]] correlating with $\mu$) - Compute the normal form of the line $\overline{PR}$ $\huge \begin{align} d &= \vector{PR}_{\perp} \cdot \tilde P \\ N&= \mat{\vector{PR}_{\perp} \\ -d} \cdot \tilde Q \\ \mu(\tilde X) &= \frac{1}{N} {\mat{\vector{PR}_{\perp}\\-d}} \cdot \tilde X\\ \end{align}$ Finding the [[../Math/Barycentric Coordinates|Barycentric Coordinates]] for some point $I$ $\huge \begin{align} \lambda_{I} &= \lambda \cdot I\\ \mu_{I} &= \mu \cdot I\\ \nu_{I} &= \nu \cdot I\\ \end{align} $ >[!tip] > Note that you only have to calculate $2$ values of the coordinate, as each coordinate is equal to one minus the 2 others $\huge \begin{align} \lambda_{I} &= 1 - \mu_{I} - \nu_{I} \\ \mu_{I} &= 1 - \lambda{I} - \nu_{I} \\ \nu_{I} &= 1 - \mu_{I} - \lambda{I} \end{align} $ ## Software Rasterization 1. Given [[Triangle]] [[Vertex|Vertices]] $\triangle PQR$ with vertex attributes $v_{p}, v_{q}, v_{r}$. 2. First you calculate the [[Bounding Box]] $\square BD$ of $\triangle PQR$. $\huge \begin{align} B &=\min\pa{P,Q,R} \\ D &=\max\pa{P,Q,R} \\ \end{align} $ 3. Find the [[#../Math/Barycentric Coordinates Barycentric Coordinates Function|Barycentric Coordinate Function]] of $\triangle PQR$. 4. Iterate through all [[Pixel|Pixels]] $\pa{i, j} \in \square BD$ (where $\square BD$ are integer pixel [[../Math/Coordinate System|Coordinates]])$\huge \begin{align} i_{B} &= \ceil{B} \\ \\ j_{D} &= \floor{D} \\ \end{align}$<br> 5. For each pixel $I=(i, j)$, Compute [[../Math/Barycentric Coordinates|Barycentric Coordinates]] at $I$. $\huge \begin{matrix} \lambda_{I} = \lambda(I) & \mu_{I} = \mu(I)& \nu_{I} = \nu(I)& \end{matrix} $ $\huge \begin{align} I \in \triangle PQR \iff \begin{cases} \lambda_{I}\ge 0 \\ \mu_{I}\ge 0 \\ \nu_{I}\ge 0 \\ \end{cases} \end{align}$ Assuming a [[Fragment Shader]] $F(v)$ that simply takes in a [[Color]] [[Vertex Attribute]] and outputs it ($\op{id}_{v}$). $\huge \begin{align} v_{I} &= \lambda_{I}v_{p} + \mu_{I}v_{q} + \nu_{I} \end{align}$ >[!tip] This is the same result as [[Linear Interpolation]] >[!example] >```rust > >fn raster(screen: &mut Screen, tri: &Triangle) { > let (p, q, r, v_p, v_q, v_r) = tri; > > let bounding_box = Rectangle::new( > p.min(q).min(r), > p.max(q).max(r), > ); > > let (lambda, mu, nu) = Mat3::from_columns(p, q, r).inverse(); > > let (bottom_left, top_right) = bounding_box; > > for x in bottom_left.x.ceil()..=top_right.x.floor() { > for y in bottom_left.y.ceil()..=top_right.y.floor() { > let i = Vec2::new(x, y); > > let (lambda, mu, nu) = (lambda.dot(i), mu.dot(i), nu.dot(i)); > > if lambda >= 0. && mu >= 0. && nu >= 0. { > screen.fill_pixel( > i, > lambda * v_p + mu * v_q + nu * v_r > ); > } > } > } >}