---
title: "采样与光栅化"
date: 2022-05-12T09:10:25+08:00

---


#### 屏幕空间
屏幕空间可以被看做是由一组像素点构成，每个像素点可以被视为中心为$(x+0.5,y+0.5)$的一个正方形，

![](../../images/pixel_and_screen_space.png)

--------------

#### 模型的面
大多数模型的面(mesh)以三角形为主（也有一些不同的面）
选择三角形的原因：
1. 大多数多边形最终都可以被分割为三角形
2. 边界清晰，便于判定某个点是否位于面内(与采样有关)
3. 对于三角形的每个顶点值有清晰的插值方式(质心插值)

------------
#### 采样的功能（光栅化）
遍历整个屏幕上所有的像素点，如果某个像素点的中心位于三角形内，则对这个像素点进行采样

伪代码
```c++
for(int x = 0 ; x < xmax; ++x)
    for(int y = 0; y< xmax ; ++y)
        image[x][y] = inside(tri,x+0.5,y+0.5);
```

可视化过程如图

![](../../images/sample_progress.png)

----------------

#### 判断像素点在三角形内部
inside的判断主要由叉乘(cross product)来实现

计算三角形各边的向量和目标测试点与三角形三个顶点的向量，将各边向量分别与测试点与顶点的向量进行叉乘，得出三个值，如果三个值得符号相同，则目标测试点位于三角形内，相反则测试点在三角形外

代码实现
```C++
//判断测试点是否在三角形内
static bool insideTriangle(int x, int y, const Vector3f* _v)
{
	// TODO : Implement this function to check if the point (x, y) is inside
    // the triangle represented by _v[0], _v[1], _v[2]

	//测试点的坐标为(x, y)
	//三角形三点的坐标分别为_v[0], _v[1], _v[2]

	//叉乘公式为(x1, y1)X(x2, y2) = x1*y2 - y1*x2

	//准备三角形各边的的向量
	Eigen::Vector2f side1;
	side1 <- _v[1].x() - _v[0].x(), _v[1].y() - _v[0].y();
	Eigen::Vector2f side2;
	side2 <- _v[2].x() - _v[1].x(), _v[2].y() - _v[1].y();
	Eigen::Vector2f side3;
	side3 <- _v[0].x() - _v[2].x(), _v[0].y() - _v[2].y();

	//计算测量点和三角形各点连线的向量
	Eigen::Vector2f v1;
	v1 <- x - _v[0].x(), y - _v[0].y();
	Eigen::Vector2f v2;
	v2 <- x - _v[1].x(), y - _v[1].y();
	Eigen::Vector2f v3;
	v3 <- x - _v[2].x(), y - _v[2].y();

	//三角形各边的的向量叉乘测量点和三角形各点连线的向量
	float z1 = side1.x() * v1.y() - side1.y() * v1.x();
	float z2 = side2.x() * v2.y() - side2.y() * v2.x();
	float z3 = side3.x() * v3.y() - side3.y() * v3.x();

	//判断叉乘结果是否有相同的符号
	if ((z1 > 0 && z2 > 0 && z3 > 0) || (z1 < 0 && z2 < 0 && z3 < 0))
	{
		return true;
	}
	else
	{
		return false;
	}
}
```
#### 加速算法

##### Bounding box

每一次判断屏幕上的像素点是否在三角形内都检测所有在屏幕上像素点会带来额外的性能开销和渲染时间

使用包围盒将三角形包围后，只判断包围盒内的像素点是否在三角形内能够减少这种情况的出现

![](../../images/BoundingBox.png)

代码实例

```c++
    auto v = t.toVector4();//包含三角形三个顶点的结构体
//利用三角形的三个顶点，计算三角形的包围盒
    float min_x = std::min(v[0].x(), std::min(v[1].x(), v[2].x()));
	float max_x = std::max(v[0].x(), std::max(v[1].x(), v[2].x()));
	float min_y = std::min(v[0].y(), std::min(v[1].y(), v[2].y()));
	float max_y = std::max(v[0].y(), std::max(v[1].y(), v[2].y()));
```

##### incremental triangle Traversal 
对于每一行像素点，只遍历三角形最左到最右的像素点，只适用于较窄的且经过旋转的三角形

![](../../images/IncrementalTriangleTraversal.png)