How do 3D engines use triangles to draw object surfaces?

In the exciting era of video games, it is essential to understand the technology behind them. As computer graphics have enhanced, the need for efficient rendering techniques has become clear.
Triangles have emerged as the building blocks for creating 3D environments in popular game development engines like Unity and Unreal Engine.

How engines draw triangles

3D graphics, simulations, and animations are part of the complex processes that use mathematics and computational algorithms. At the core of this complex process are simple geometric elements that are just lines and triangles.

How to draw a line

A line in a 2D coordinate system can be drawn using a digital differential analyzer (DDA) algorithm. It determines which points in a 2D grid should be highlighted best to represent a line between the two given points. 

How DDA works

The DDA algorithm works by sampling at regular intervals in either $x$ or $y$ coordinates, calculating the corresponding values in the coordinates, and rounding the values to the nearest integer to determine the pixel position.

The complete steps are given below.

• Start with the two points, say $(x_1, y_1)$ and $(x_2, y_2)$ to connect with a line.

• Calculate the difference in $x$ and $y$ coordinates as follows:

• Determine the number of steps to be taken as the absolute maximum difference between the two points $dx$ and $dy$.

  • If $|dx| > |dy|$, choose $dx$ as the number of steps to make a line

  • If $|dx| > |dy|$, choose $dy$ as the number of steps to make a line

• Divide the total difference in $x$ or $y$ by the number of steps to calculate the increment in $x$ and $y$ for each step.

• To increment the values of $x$ and $y$, you first need to check the slope by:

If the slope $m < 1$, increment the values of $x$ and $y$ as follows:

If the slope $m = 1$, increment the values of $x$ and $y$ as follows:

If the slope $m > 1$, increment the values of $x$ and $y$ as follows:

• Repeat the process for the total number of steps to get all the pixels that the line passes through.

How to use triangles

A triangle can easily be drawn by connecting three lines.
Let's say we have three points, A, B, and C, forming the triangle's vertices. You can follow the steps mentioned above to draw a line from A to B, B to C, and C to A. It will give us an outline for the triangle.

Now, we need to determine whether the pixel lies inside the triangle. We can use the line equation to determine which pixel should be illuminated.

Replace the values of $(x_1, y_1)$ and $(x_2, y_2)$ with the end points of the line and rearrange the equation:

Pick any random point and replace the $x$and $y$ with the coordinate values.

• If $L(x, y) > 0$, the point lies above the line.

• If $L(x, y) < 0$, the point lies below the line.

• If $L(x, y) = 0$, the point lies on the line.

Triangle orientation

Establishing a consistent orientation and understanding the concept of normal is essential to determine whether a point lies inside or outside the triangle.

There are two approaches to triangle orientation.

Counter-clockwise orientation approach

• Normal will point outward (away from the triangle).

• Inside of the triangle will be on the left side of the edges.

Clockwise orientation approach

• Normal will point inward (towards the triangle).

• The inside of the triangle will be on the right side of the edges.

Point-in triangle test

The point-in triangle test is a method used to determine whether a given point lies inside, outside, or on the boundary of the triangle.

A point $(x_n, y_n)$ is inside the triangle if it is inside all of the three lines.

Note:

• The above equation may produce inaccurate results if the triangle’s orientation is inconsistent.

• Thus, it is essential to establish a consistent orientation for the triangle and its vertices to ensure the accuracy of the test.

The above approach can be applied to each triangle in a 3D model, filling in all the pixels that make up the visible surface of the model.

In 3D graphics, hundreds of thousands to millions of triangles are rendered like this in every frame to create the detailed and complex images we see in video games and simulations.

Read more about triangles

• Why do 3D engines use triangles to draw object surfaces?