voidtriangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color){ // sort the vertices, t0, t1, t2 lower−to−upper (bubblesort yay!) if (t0.y>t1.y) std::swap(t0, t1); if (t0.y>t2.y) std::swap(t0, t2); if (t1.y>t2.y) std::swap(t1, t2); int total_height = t2.y-t0.y; for (int y=t0.y; y<=t1.y; y++) { int segment_height = t1.y-t0.y+1; float alpha = (float)(y-t0.y)/total_height; float beta = (float)(y-t0.y)/segment_height; // be careful with divisions by zero Vec2i A = t0 + (t2-t0)*alpha; Vec2i B = t0 + (t1-t0)*beta; image.set(A.x, y, red); image.set(B.x, y, green); } }

Note that the alpha & beta are proportions of similar triangles.

Better mathod for multithread processor

Barycentric coordinate system

1 2 3 4 5 6 7

AB *--------------------------------------* ab

APB *---------*----------------------------* ab

There is a line(A, B), and it’s vertices have different weight.

We assume they are equal to, $a$ and $b$, respectively. So, if we want to find out the barycenter of the line. We probably know that the barycenter $P$ well may be at the side closing A.

We assume $\frac{AP}{AB}$ equals to $i$ and $\frac{PB}{AB}$ equals to $j$.

Then $i + j = 1$.

Similarly, in the 3D space, the triangle’s barycenter named $P$, then $P = i \overrightarrow{PA} + j\overrightarrow{PB} + k\overrightarrow{PC}$, and $i + j + k = 1$.

If we regard $\overrightarrow{PA}$ , $\overrightarrow{PB}$ , and $\overrightarrow{PC}$ as the basis of a coordinate system, we would call system a barycentric coordinate system.

Rename $(i,j,k)$ to $(w, u, v)$ and change the equation to:

Then the barycentric coordinates of point $P$ become $(1-u-v, u, v)$ .

Calculate the value of u & v

We can find a linear system of two equations with two variables:

Vec3f barycentric(Vec2i *pts, Vec2i P){ Vec3f u = Vec3f(pts[2][0]-pts[0][0], pts[1][0]-pts[0][0], pts[0][0]-P[0])^Vec3f(pts[2][1]-pts[0][1], pts[1][1]-pts[0][1], pts[0][1]-P[1]); /* `pts` and `P` has integer value as coordinates so `abs(u[2])` < 1 means `u[2]` is 0, that means triangle is degenerate, in this case return something with negative coordinates */ if (std::abs(u.z)<1) returnVec3f(-1,1,1); returnVec3f(1.f-(u.x+u.y)/u.z, u.y/u.z, u.x/u.z); }

intmain(int argc, char** argv){ TGAImage frame(200, 200, TGAImage::RGB); Vec2i pts[3] = {Vec2i(10,10), Vec2i(100, 30), Vec2i(190, 160)}; triangle(pts, frame, TGAColor(255, 0, 0)); frame.flip_vertically(); // to place the origin in the bottom left corner of the image frame.write_tga_file("framebuffer.tga"); return0; }

In this code, the barycentric function compute the barycentric coordinates of Point $P$ . The cartesian coordinates of point $P$ come from the triangle function. To determine whether the cartesian coordinates of point $P$ are in the triangle by determining whether the value of the barycentric coordinates of it has a negative value.

The triangle function also has a clipping of the bounding box with the screen rectangle to reduce the CPU load for the triangles outside of the screen.