> ## Content Index
> Fetch the complete content index at: https://cms.yufeiran.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# mini3DRender
- URL: https://cms.yufeiran.com/en-mini3drender/
- Published: 2022-10-09T23:18:44.000Z
- Updated: 2026-09-27T12:37:57.000Z
- Author: Feiran Yu
- Tags: #lang-en, #legacy-import

# Background

In [Deriving Graphics Coordinate Transforms on Scratch Paper](https://yufeiran.com/en/cao-gao-zhi-shang-tui/?ref=cms.yufeiran.com), I derived the full coordinate-transformation process. To verify and firmly understand those transforms, this article implements a basic renderer that only uses the CPU for computation.

# Main Features

- Display OBJ files
- Draw points, lines, and triangles
- Draw textures

# Implementation Details

## \[1\] Bresenham Line Drawing Algorithm

This section introduces the famous Bresenham line drawing algorithm.

Modern screens consist of discrete pixels, so a line drawn by a computer can only be composed of discrete points. Bresenham’s algorithm can draw any line on the screen. It only needs integer division and does not require floating-point operations, so it has very high performance.

Below is the Bresenham process as I understand it, followed by my C++ implementation. To make the explanation easier, I only use lines with slopes between 0 and 1 as the example.

As shown below, discretizing a line means determining the next point ( (x\_{i+1}, y\_{i+1}) ) when the current point ( (x\_i, y\_i) ) is known. There are only two possibilities: ( (x\_{i+1}, y\_i) ) or ( (x\_{i+1}, y\_{i+1}) ).

![Bresenham idea](https://yufeiran.com/content/images/2022/10/1665406210210.jpg)

The core of Bresenham’s algorithm is to observe the distance from the real line to the fitted discrete line at the same x coordinate. This is the distance `D` in the diagram. When `D` exceeds the midpoint, 0.5, the fitted curve increments its y value by one, moving one pixel upward. This keeps `D <= 0.5`.

Pseudo-code:

```text
D = 0
for each x in (x0, x1)
  DrawPoint(x, y)
  D += k
  if (D > 0.5)
    y++
    D -= 1

```

This version can already draw any line, but it requires floating-point operations, such as computing `k` and `D`. For better performance, we optimize it.

First, instead of comparing `D` with `0.5`, multiply `D` by 2\. This does not affect the result:

```text
D1 = 0
for each x in (x0, x1)
  DrawPoint(x, y)
  D1 += 2 * k
  if (D1 > 1)
    y++
    D1 -= 2

```

Because `k = dy / dx`, where `dy = y1 - y0` and `dx = x1 - x0`, and both `dy` and `dx` are integers, we multiply `D` by `dx` to remove floating-point addition:

```text
D2 = 0
for each x in (x0, x1)
  DrawPoint(x, y)
  D2 += 2 * dy
  if (D2 > dx)
    y++
    D2 -= 2 * dx

```

Now we have a line drawing algorithm made entirely of integer operations. It can draw lines on the computer I previously built without a floating-point unit: [Building a Computer with Nexys4 DDR series](https://yufeiran.com/en/yong-nexys4ddr-zhi-zuo-yi-tai-ji-suan-ji/?ref=cms.yufeiran.com).

Full C++ code:

```cpp
void DrawLine_Bresenham(int x0, int y0, int x1, int y1, const Color& color)
{
	if (x1 < x0) {
		int tempX, tempY;
		tempX = x0;
		x0 = x1;
		x1 = tempX;
		tempY = y0;
		y0 = y1;
		y1 = tempY;
	}
	if (x1 == x0) {
		for (int y = min(y0, y1); y <= max(y0, y1); y++) {
			DrawPoint(x0, y, color);
		}
		return;
	}

	if (y1==y0) {
		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y0, color);
		}
		return;
	}
	int dx = x1 - x0, dy = y1 - y0;
	bool kSign = ((y1 - y0) >= 0 && (x1 - x0) >= 0) ? true : false;
	bool kGreaterThenOne = (abs(y1 - y0) > abs(x1 - x0)) ? true : false;

	int d = 0;
	if (kSign == true && kGreaterThenOne == false) {
		int y = y0;
		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y, color);
			d += 2 * dy;
			if (d > dx) {
				d -= 2 * dx;
				y++;
			}
		}
	}
	else if (kSign == true && kGreaterThenOne == true) {
		int x = x0;
		for (int y = y0; y < y1; y++) {
			DrawPoint(x, y, color);
			d += 2 * dx;
			if (d > dy) {
				d -= 2 * dy;
				x++;
			}
		}
	}
	else if(kSign==false&&kGreaterThenOne==false){
		int y = y0;
		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y, color);
			d += -2 * dy;
			if (d > dx) {
				d -= 2 * dx;
				y--;
			}
		}
	}
	else if (kSign == false && kGreaterThenOne == true) {
		int x = x0;
		for (int y = y0; y > y1; y--) {
			DrawPoint(x, y, color);
			d += 2 * dx;
			if (d > -dy) {
				d -= -2 * dy;
				x++;
			}
		}
	}
}

```

Here is the Stanford bunny drawn with Bresenham lines:

![Bresenham bunny](https://yufeiran.com/content/images/2022/10/20221011212023.png)

## \[2\] Triangle Rasterization Algorithm

This section introduces triangle rasterization. Most software rasterizers are based on drawing triangular faces.

Here I introduce the classic splitting method. As shown below, all triangles can be classified into three types:

1. The two lower vertices have the same y value.
2. The two upper vertices have the same y value.
3. Any other triangle, which can be split into one triangle of type 1 and one triangle of type 2.

![triangle classification](https://yufeiran.com/content/images/2022/10/1665494158668.jpg)

So, as long as we know how to draw type 1 and type 2 triangles, we can draw any triangle by combining them.

The following explains how to draw the first type:

![triangle rasterization](https://yufeiran.com/content/images/2022/10/1665495793379.jpg)

Type 2 is basically the same, so I skip it and directly introduce drawing arbitrary triangles.

To draw an arbitrary triangle using the method for type 1 and type 2 triangles, we still need one extra point to split it into two triangles. So we need to determine the position of the fourth point `v4`.

![split triangle](https://yufeiran.com/content/images/2022/10/IMG_20221011_214705.jpg)

![split triangle](https://yufeiran.com/content/images/2022/10/1665496210988.jpg)

The proof here is just middle-school geometry. It is simple, but it is best to draw it yourself once.

After obtaining the coordinates of the fourth point, we can use the previous functions for type 1 and type 2 triangles to draw the whole triangle.

The original article includes the full C++ implementation of `DrawTopFlatTriangle`, `DrawBottomFlatTriangle`, and `DrawTriangle`.

Here is the bunny drawn using this triangle rasterization algorithm:

![rasterized bunny](https://yufeiran.com/content/images/2022/10/20221011215425.png)

## \[3\] Barycentric Coordinates

Barycentric coordinates express any point `p` inside a triangle using the coordinates of the triangle’s vertices:

```text
p = i * A + j * B + k * C

```

Then any point inside a triangle can be represented as `(i, j, k)`. This is very useful for interpolation inside triangles, such as texture mapping and lighting.

To add texture mapping to mini3DRender, I first needed to understand triangle barycentric coordinates.

This section first introduces barycentric coordinates for triangles, then uses them to perform interpolation inside triangles.

First, consider barycentric coordinates on a line:

![line barycentric coordinates](https://yufeiran.com/content/images/2022/10/----_20221026090009.jpg)

The barycentric coordinates of a line express any point on the line using the two endpoints:

```text
p = j * A + k * B, where j + k = 1

```

Using this conclusion, we can derive the barycentric coordinate representation of any point inside a triangle.

![barycentric derivation](https://yufeiran.com/content/images/2022/10/1543e26b7d05714140dcbe196158eb6.jpg)

![barycentric derivation](https://yufeiran.com/content/images/2022/10/387919aa646439bf287be3d80a60d10.jpg)

![barycentric derivation](https://yufeiran.com/content/images/2022/10/5b40f8ee50f938f362ff01a472bb1ad.jpg)

From the scratch-paper derivation above, we can obtain `i` and `j` in the barycentric coordinates of any point, and then `k = 1 - i - j`.

This gives the barycentric coordinates of any point inside a **2D** triangle.

However, mini3DRender eventually performs perspective projection, so the coordinates change. The result computed here must be corrected accordingly.

![perspective correction](https://yufeiran.com/content/images/2022/10/2a8dc94d27e494aa08c62bdb46cffb0.jpg)

![perspective correction](https://yufeiran.com/content/images/2022/10/ff0241b25d1f7507dd22d7155a7bf75.jpg)

### References

[GAMES101 modern computer graphics notes: Lecture 09 Shading 3, texture mapping](https://www.cnblogs.com/marsggbo/p/12972314.html?ref=cms.yufeiran.com)

[Graphics basics: Barycentric Coordinates](https://blog.csdn.net/wangjiangrong/article/details/115326930?ref=cms.yufeiran.com)

[Deep exploration of perspective texture mapping, part 1](https://blog.csdn.net/popy007/article/details/5556639?spm=1001.2014.3001.5502&ref=cms.yufeiran.com)

[Deep exploration of perspective texture mapping, part 2](https://blog.csdn.net/popy007/article/details/5570803?spm=1001.2014.3001.5502&ref=cms.yufeiran.com)

## \[4\] Perspective Correction for Texture Mapping

When drawing triangles, texture mapping requires `u` and `v` coordinates, and those coordinates need interpolation. But the transformation from camera space to clip space does not preserve linearity; the whole space is distorted by perspective projection.

Therefore, `u` and `v` cannot be interpolated using coordinates in clip space or later screen space. The clip-space-to-screen-space transform is linear, but the perspective projection before it is not. Instead, `u` and `v` interpolation needs to be computed using camera-space coordinates.

The goal here is to restore camera-space coordinates from clip-space coordinates.

This section is basically notes on [Deep exploration of perspective texture mapping, part 1](https://blog.csdn.net/popy007/article/details/5556639?spm=1001.2014.3001.5502&ref=cms.yufeiran.com) and [part 2](https://blog.csdn.net/popy007/article/details/5570803?spm=1001.2014.3001.5502&ref=cms.yufeiran.com).

![perspective correction notes](https://yufeiran.com/content/images/2022/10/----_20221028172839.jpg)

![perspective correction notes](https://yufeiran.com/content/images/2022/10/93c6b687551f92d3a8f370b5d3b00fe.jpg)

## \[5\] Lighting

In a rasterization renderer, lighting is an approximation method used to reproduce lighting effects similar to objects in the real world.

Here I introduce the Blinn-Phong and Phong lighting models. The basic process is shown below:

![Phong components](https://yufeiran.com/content/images/2022/12/Phong_components_version_4.png)

These two models divide total lighting into:

**Ambient** \+ **Diffuse** \+ **Specular**

### Principle

![lighting notes](https://yufeiran.com/content/images/2022/12/1-2.jpg)

![lighting notes](https://yufeiran.com/content/images/2022/12/2.jpg)

![lighting notes](https://yufeiran.com/content/images/2022/12/3-2.jpg)

![lighting notes](https://yufeiran.com/content/images/2022/12/4.jpg)

### Implementation

I will add lighting to mini3DRender.

- Create `light.h` and `light.cpp` to define point lights.
- In the triangle drawing function, compute the normal vector of the current triangle and pass it into the final scanline drawing function.
- Compute lighting for each point according to the formulas above.

### Result

Still the Stanford bunny, but now with lighting:

![lightBunny](https://yufeiran.com/content/images/2022/12/lightBunny.png)

### References

[Some references for beginner rasterization renderers](https://blog.51cto.com/u%5F15273495/2914534?ref=cms.yufeiran.com)

[Introduction to shading: Blinn-Phong and Phong lighting models](https://zhuanlan.zhihu.com/p/352209183?ref=cms.yufeiran.com)

# Reference Links

[Rasterization algorithm for drawing lines](https://zhuanlan.zhihu.com/p/20213658?ref=cms.yufeiran.com)