Hello everyone! Recently, I came across the graphics code I wrote two or three years ago and realized I've forgotten quite a bit. So, I'm writing this article to review it. Here are the previous results:
https://github.com/925558718/CanvasRender
This time, let's review how to draw a triangle
Prepare the rendering environment: Canvas
const canvas = document.querySelector<HTMLCanvasElement>("#canvas")!;
const ctx = canvas.getContext("2d")!;
const buffer = new Uint8ClampedArray(500 * 500 * 4);
ctx.putImageData(new ImageData(buffer, 500, 500), 0, 0);
We create a buffer, modify it, and then render it to the canvas.
Triangle Data Definition
We can store three vertices in an array, like [p1, p2, p3].
Our current canvas is 500x500, so we define a triangle as [[0,0], [250,500], [500,500]], which makes its bounding box the entire canvas.
The origin of the canvas coordinate system is at the top-left, so our goal is to render a triangle with its tip pointing to the left.
Two Ways to Draw a Triangle
Scanline Algorithm
This method involves scanning vertically from top to bottom, finding the two intersection points of a horizontal line with the triangle, and then iterating through the pixels between these two intersection points to color them.
First, sort the vertices to ensure the higher vertex is first.
// Sort vertices by y-coordinate
const sortedVertices = [...points].sort((a, b) => a[1] - b[1]);
const [p0, p1, p2] = sortedVertices;
For easier manipulation, we operate on the upper and lower regions separately.
Start iterating:
// Calculate intersection points, which is essentially interpolation. Given the y-value of the midpoint, find the x-component.
function interpolate(y: number, y0: number, x0: number, y1: number, x1: number): number {
if (y1 === y0) return x0;
return x0 + (x1 - x0) * (y - y0) / (y1 - y0);
}
function fillUpperTriangle() {
if (p1[1] === p0[1]) return; // Avoid division by zero
for (let y = p0[1]; y <= p1[1]; y++) {
// Calculate x-coordinates of the left and right boundaries
const x1 = interpolate(y, p0[1], p0[0], p1[1], p1[0]); // Edge from p0 to p1
const x2 = interpolate(y, p0[1], p0[0], p2[1], p2[0]); // Edge from p0 to p2
// Ensure xLeft < xRight
const xLeft = Math.min(x1, x2);
const xRight = Math.max(x1, x2);
// Fill the row
for (let x = Math.ceil(xLeft); x <= Math.floor(xRight); x++) {
setPixel(x, y, color[0], color[1], color[2], color[3]);
}
}
}
// Helper function to set pixel color
function setPixel(x: number, y: number, r: number, g: number, b: number, a: number) {
if (x < 0 || x >= 500 || y < 0 || y >= 500) return;
const index = (Math.floor(y) * 500 + Math.floor(x)) * 4;
buffer[index] = r; // Red
buffer[index + 1] = g; // Green
buffer[index + 2] = b; // Blue
buffer[index + 3] = a; // Alpha
}
The lower part uses a similar operation, just iterating through the lower region.
Iteration + Barycentric Coordinates
The scanline algorithm is fast, but its capabilities are limited. What if I want to render a colored triangle?
To render a colored triangle, we can define the colors of the three vertices, but how do we define the color of points in between? This is where barycentric coordinates come in handy.
What are Barycentric Coordinates?
Simply put, any point P within a triangle can be expressed as P=αP +βP +γP , where α+β+γ=1 and α,β,γ≥0. These three coefficients can then be multiplied by the colors to calculate the interpolated color of that point.
How to Calculate Barycentric Coordinates
Area Method
When point P is connected to the other three vertices, it forms three sub-regions within the triangle. The ratio of each sub-region's area to the total area of the triangle gives its corresponding coefficient. For example, for point P 3, its coefficient is Area(P,P2,P1)/Area(P1,P2,P3), which is precisely the percentage of the total area occupied by the region formed by the other two points and point P.
function getBarycentricCoordinates(px: number, py: number): [number, number, number] {
// Calculate barycentric coordinates using the area method
const denominator = (p1[1] - p2[1]) * (p0[0] - p2[0]) + (p2[0] - p1[0]) * (p0[1] - p2[1]);
if (Math.abs(denominator) < 1e-10) {
return [0, 0, 0]; // Degenerate triangle
}
// Barycentric coordinates u, v, w (corresponding to vertices p0, p1, p2)
const u = ((p1[1] - p2[1]) * (px - p2[0]) + (p2[0] - p1[0]) * (py - p2[1])) / denominator;
const v = ((p2[1] - p0[1]) * (px - p2[0]) + (p0[0] - p2[0]) * (py - p2[1])) / denominator;
const w = 1 - u - v;
return [u, v, w];
}
Then, we start iterating through the entire bounding box:
// Iterate over all pixels within the bounding box
for (let y = minY; y <= maxY; y++) {
for (let x = minX; x <= maxX; x++) {
// Calculate the barycentric coordinates for the current pixel
const [u, v, w] = getBarycentricCoordinates(x + 0.5, y + 0.5); // +0.5 for sampling the pixel center
// If the point is inside the triangle, fill it
if (isInsideTriangle(u, v, w)) {
// Use barycentric coordinates to interpolate the color
const [r, g, b, a] = interpolateColor(u, v, w);
setPixel(x, y, r, g, b, a);
}
}
}
However, iterating through every point in the bounding box and then calculating barycentric coordinates is quite inefficient. We can add some optimization to check if a point is inside the triangle before calculating barycentric coordinates, but I won't go into detail here. Let's just look at the results.