Triangles and Z-Buffering

引言

GAMES101现代图形学入门是由闫令琪老师教授。本次作业主要是关于三角形的光栅化。

大家好,GAMES101 Spring 2021 课程作业二现在发布!

在课程中段,我们会为同学们开启补提交通道。

SmartChair链接

GAMES链接

百度云链接 密码:34pc

请大家根据网络环境自行下载。

总览

在上次作业中,虽然我们在屏幕上画出一个线框三角形,但这看起来并不是 那么的有趣。所以这一次我们继续推进一步——在屏幕上画出一个实心三角形, 换言之,栅格化一个三角形。上一次作业中,在视口变化之后,我们调用了函数 rasterize_wireframe(const Triangle& t)。但这一次,你需要自己填写并调用函数 rasterize_triangle(const Triangle& t)

该函数的内部工作流程如下:

  1. 创建三角形的 2 维 bounding box。
  2. 遍历此 bounding box 内的所有像素(使用其整数索引)。然后,使用像素中心的屏幕空间坐标来检查中心点是否在三角形内。
  3. 如果在内部,则将其位置处的插值深度值 (interpolated depth value) 与深度缓冲区 (depth buffer) 中的相应值进行比较。
  4. 如果当前点更靠近相机,请设置像素颜色并更新深度缓冲区 (depth buffer)。

你需要修改的函数如下:

  • rasterize_triangle(): 执行三角形栅格化算法

  • static bool insideTriangle(): 测试点是否在三角形内。你可以修改此函 数的定义,这意味着,你可以按照自己的方式更新返回类型或函数参数。

因为我们只知道三角形三个顶点处的深度值,所以对于三角形内部的像素, 我们需要用插值的方法得到其深度值。我们已经为你处理好了这一部分,因为有 关这方面的内容尚未在课程中涉及。插值的深度值被储存在变量 z_interpolated 中。

请注意我们是如何初始化 depth buffer 和注意 z values 的符号。为了方便 同学们写代码,我们将 z 进行了反转,保证都是正数,并且越大表示离视点越远。

在此次作业中,你无需处理旋转变换,只需为模型变换返回一个单位矩阵。最 后,我们提供了两个 hard-coded 三角形来测试你的实现,如果程序实现正确,你 将看到如下所示的输出图像:

开始编写

在你自己的计算机或虚拟机上下载并使用我们更新的框架代码。你会注意到, 在 main.cpp 下的 get_projection_matrix() 函数是空的。请复制粘贴你在第一次作业中的实现来填充该函数。

评分与提交

评分

  • [5 分] 正确地提交所有必须的文件,且代码能够编译运行。

  • [20 分] 正确实现三角形栅格化算法。

  • [10 分] 正确测试点是否在三角形内。

  • [10 分] 正确实现 z-buffer 算法, 将三角形按顺序画在屏幕上。

  • [提高项 5 分] 用 super-sampling 处理 Anti-aliasing : 你可能会注意 到,当我们放大图像时,图像边缘会有锯齿感。我们可以用 super-sampling 来解决这个问题,即对每个像素进行 2 * 2 采样,并比较前后的结果 (这里 并不需要考虑像素与像素间的样本复用)。需要注意的点有,对于像素内的每 一个样本都需要维护它自己的深度值,即每一个像素都需要维护一个 sample list。最后,如果你实现正确的话,你得到的三角形不应该有不正常的黑边。

  • [-2 分] 惩罚分数:
    未删除 /build、/.vscode、Assignment2.pdf 等与代码无关的文件。 未提交或未按要求完成 README.md。
    代码相关文件和 README.md 文件不在你提交的文件夹下的第一层。

提交

当你完成作业后,请清理你的项目,记得在你的文件夹中包含 CMakeLists.txt

和所有的程序文件 (无论是否修改)。同时,请提交一份实验结果的图片与添加一 个 README.md 文件写下是否完成提高题 (如果完成了,也请同时提交一份结果 图片),并简要描述你在各个函数中实现的功能。最后,将上述内容打包,并用“姓 名 Homework2.zip”的命名方式提交到 SmartChair 平台。

平台链接:http://www.smartchair.org/GAMES101-Spring2021/。

实现

代码框架

// clang-format off
//
// Created by goksu on 4/6/19.
//

#include <algorithm>
#include <vector>
#include "rasterizer.hpp"
#include <opencv2/opencv.hpp>
#include <math.h>


rst::pos_buf_id rst::rasterizer::load_positions(const std::vector<Eigen::Vector3f> &positions)
{
auto id = get_next_id();
pos_buf.emplace(id, positions);

return {id};
}

rst::ind_buf_id rst::rasterizer::load_indices(const std::vector<Eigen::Vector3i> &indices)
{
auto id = get_next_id();
ind_buf.emplace(id, indices);

return {id};
}

rst::col_buf_id rst::rasterizer::load_colors(const std::vector<Eigen::Vector3f> &cols)
{
auto id = get_next_id();
col_buf.emplace(id, cols);

return {id};
}

auto to_vec4(const Eigen::Vector3f& v3, float w = 1.0f)
{
return Vector4f(v3.x(), v3.y(), v3.z(), w);
}


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]
}

static std::tuple<float, float, float> computeBarycentric2D(float x, float y, const Vector3f* v)
{
float c1 = (x*(v[1].y() - v[2].y()) + (v[2].x() - v[1].x())*y + v[1].x()*v[2].y() - v[2].x()*v[1].y()) / (v[0].x()*(v[1].y() - v[2].y()) + (v[2].x() - v[1].x())*v[0].y() + v[1].x()*v[2].y() - v[2].x()*v[1].y());
float c2 = (x*(v[2].y() - v[0].y()) + (v[0].x() - v[2].x())*y + v[2].x()*v[0].y() - v[0].x()*v[2].y()) / (v[1].x()*(v[2].y() - v[0].y()) + (v[0].x() - v[2].x())*v[1].y() + v[2].x()*v[0].y() - v[0].x()*v[2].y());
float c3 = (x*(v[0].y() - v[1].y()) + (v[1].x() - v[0].x())*y + v[0].x()*v[1].y() - v[1].x()*v[0].y()) / (v[2].x()*(v[0].y() - v[1].y()) + (v[1].x() - v[0].x())*v[2].y() + v[0].x()*v[1].y() - v[1].x()*v[0].y());
return {c1,c2,c3};
}

void rst::rasterizer::draw(pos_buf_id pos_buffer, ind_buf_id ind_buffer, col_buf_id col_buffer, Primitive type)
{
auto& buf = pos_buf[pos_buffer.pos_id];
auto& ind = ind_buf[ind_buffer.ind_id];
auto& col = col_buf[col_buffer.col_id];

float f1 = (50 - 0.1) / 2.0;
float f2 = (50 + 0.1) / 2.0;

Eigen::Matrix4f mvp = projection * view * model;
for (auto& i : ind)
{
Triangle t;
Eigen::Vector4f v[] = {
mvp * to_vec4(buf[i[0]], 1.0f),
mvp * to_vec4(buf[i[1]], 1.0f),
mvp * to_vec4(buf[i[2]], 1.0f)
};
//Homogeneous division
for (auto& vec : v) {
vec /= vec.w();
}
//Viewport transformation
for (auto & vert : v)
{
vert.x() = 0.5*width*(vert.x()+1.0);
vert.y() = 0.5*height*(vert.y()+1.0);
vert.z() = vert.z() * f1 + f2;
}

for (int i = 0; i < 3; ++i)
{
t.setVertex(i, v[i].head<3>());
t.setVertex(i, v[i].head<3>());
t.setVertex(i, v[i].head<3>());
}

auto col_x = col[i[0]];
auto col_y = col[i[1]];
auto col_z = col[i[2]];

t.setColor(0, col_x[0], col_x[1], col_x[2]);
t.setColor(1, col_y[0], col_y[1], col_y[2]);
t.setColor(2, col_z[0], col_z[1], col_z[2]);

rasterize_triangle(t);
}
}

//Screen space rasterization
void rst::rasterizer::rasterize_triangle(const Triangle& t) {
auto v = t.toVector4();

// TODO : Find out the bounding box of current triangle.
// iterate through the pixel and find if the current pixel is inside the triangle

// If so, use the following code to get the interpolated z value.
//auto[alpha, beta, gamma] = computeBarycentric2D(x, y, t.v);
//float w_reciprocal = 1.0/(alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
//float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();
//z_interpolated *= w_reciprocal;

// TODO : set the current pixel (use the set_pixel function) to the color of the triangle (use getColor function) if it should be painted.
}

void rst::rasterizer::set_model(const Eigen::Matrix4f& m)
{
model = m;
}

void rst::rasterizer::set_view(const Eigen::Matrix4f& v)
{
view = v;
}

void rst::rasterizer::set_projection(const Eigen::Matrix4f& p)
{
projection = p;
}

void rst::rasterizer::clear(rst::Buffers buff)
{
if ((buff & rst::Buffers::Color) == rst::Buffers::Color)
{
std::fill(frame_buf.begin(), frame_buf.end(), Eigen::Vector3f{0, 0, 0});
}
if ((buff & rst::Buffers::Depth) == rst::Buffers::Depth)
{
std::fill(depth_buf.begin(), depth_buf.end(), std::numeric_limits<float>::infinity());
}
}

rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)
{
frame_buf.resize(w * h);
depth_buf.resize(w * h);
}

int rst::rasterizer::get_index(int x, int y)
{
return (height-1-y)*width + x;
}

void rst::rasterizer::set_pixel(const Eigen::Vector3f& point, const Eigen::Vector3f& color)
{
//old index: auto ind = point.y() + point.x() * width;
auto ind = (height-1-point.y())*width + point.x();
frame_buf[ind] = color;

}

// clang-format on

投影函数

首先填写上次作业在 main.cpp 下的 get_projection_matrix() 函数:

Eigen::Matrix4f get_projection_matrix(float eye_fov, float aspect_ratio, float zNear, float zFar)
{
// Students will implement this function

Eigen::Matrix4f projection = Eigen::Matrix4f::Identity();

// TODO: Implement this function
// Create the projection matrix for the given parameters.
// Then return it.

// Matrix ortho

float angle = eye_fov / 180.0 * MY_PI;

float top = zNear * std::tan(angle / 2);
float bot = -top;
float left = top * aspect_ratio;
float right = -left;


Eigen::Matrix4f ortho = Eigen::Matrix4f::Identity();
Eigen::Matrix4f trans(4,4);
Eigen::Matrix4f scale(4,4);

trans << 2 / (right - left), 0, 0, 0,
0, 2 / (top - bot), 0, 0,
0, 0, 2 / (zNear -zFar), 0,
0, 0, 0, 1;

scale << 1, 0, 0, -(right + left) / 2,
0, 1, 0, -(top + bot) / 2,
0, 0, 1, -(zNear + zFar) / 2,
0, 0, 0, 1;

ortho = trans * scale;

// Matrix persp2ortho

float A = zNear + zFar;
float B = -zNear * zFar;

Eigen::Matrix4f persp2ortho = Eigen::Matrix4f::Identity();

persp2ortho << zNear, 0, 0, 0,
0, zNear, 0, 0,
0, 0, A, B,
0, 0, 1, 0;


// Matrix presp
projection = ortho * persp2ortho;

return projection;
}

包围盒边界

对于每个三角形,我们对其顶点的 x 与 y 值进行遍历,并找出minXmaxXminY 以及 maxY

由于顶点坐标是浮点型,为了不丢失信息,对于”min”值,bounding box的边界进行向下取整;对于”max”值,bounding box的边界进行向上取整:

int minX = std::floor(std::min(v[0][0], std::min(v[1][0], v[2][0])));
int minY = std::floor(std::min(v[0][1], std::min(v[1][1], v[2][1])));
int maxX = std::ceil(std::max(v[0][0], std::max(v[1][0], v[2][0])));
int maxY = std::ceil(std::max(v[0][1], std::max(v[1][1], v[2][1])));

判断函数

对于是否在三角形内的判别,我们使用向量叉积。在向量叉积中我们提到如何判断左右侧。我们有一个三角形$\bigtriangleup {P_0P_1P_2}$,判断点$Q$是否在三角形内。例如我们可以通过$\vec{P_1P_2} \times \vec{P_1Q}$,根据右手定则叉乘方向向屏幕外侧,所以$Q$在$P_1P_2$的左侧;同理$\vec{P_0P_1} \times \vec{P_0Q}$,得到的结果仍然在屏幕外侧,$Q$在$P_0P_1$的左侧;在我们判断$\vec{P_2P_0} \times \vec{P_2Q}$时,得到的结果是一个向里的向量,所以$Q$在$P_2P_0$的右侧,它不在三角形内部。

说了这么多,总结起来就是三个叉积向量(叉积时注意顺序)必须同向,向量两两对应做叉积,只要叉积结果符号均相同,则说明判断点在三角形内部。转换为公式为:

$(P_0P_1 \times P_0Q) \space\space && \space\space (P_1P_2 \times P_1Q) \space\space && \space\space (P_2P_0 \times P_2Q)$

之后就是把思路转换为代码了,分别表示出点和向量,一步步做运算,注意先补阶数:

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]

Eigen::Vector3f Q;
Q << float(x), float(y), 1;
Vector3f v[3];
for (int i = 0; i < 3; ++i) {
v[i] << _v[i].x(), _v[i].y(), 1;
}

Eigen::Vector3f P_01 = v[0] - v[1];
Eigen::Vector3f P_12 = v[1] - v[2];
Eigen::Vector3f P_20 = v[2] - v[0];

Eigen::Vector3f P_0Q = v[0] - Q;
Eigen::Vector3f P_1Q = v[1] - Q;
Eigen::Vector3f P_2Q = v[2] - Q;

if ((P_01.cross(P_0Q).z() > 0 && P_12.cross(P_1Q).z() > 0 && P_20.cross(P_2Q).z() > 0)
|| (P_01.cross(P_0Q).z() < 0 && P_12.cross(P_1Q).z() < 0 && P_20.cross(P_2Q).z() < 0))
return true;
return false;
}

网上许多的判定方法同向没有考虑三者都为负的情况,不知道为什么。我觉得自己写的这个函数很清楚,便于理解。

插值函数

用两层循环来遍历bounding box的所有点。我们需要判断当前点是否被包含在三角形内部,如果包含,则对它进行着色:

void rst::rasterizer::rasterize_triangle(const Triangle& t) {
...
for(int x = minX; x <= maxX; x++) {
for(int y = minY; y <= maxY; y++) {
if(insideTriangle(x + 0.5, y + 0.5, t.v)) {
...
}
}
}
}

只要点在三角形内部,我们马上对当前点的深度进行插值计算:

for (int x = minX; x <= maxX; ++x) {
for (int y = minY; y <= maxY; ++y) {
if (insideTriangle(x + 0.5, y + 0.5, t.v)) {
auto[alpha, beta, gamma] = computeBarycentric2D(float(x) + 0.5f, float(y) + 0.5f, t.v);
float w_reciprocal = 1.0f/(alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();
z_interpolated *= w_reciprocal;

int buf_index = get_index(x, y);
if (z_interpolated >= depth_buf[buf_index])
continue;

depth_buf[buf_index] = z_interpolated;
set_pixel(Vector3f(x, y, 1), t.getColor());
}
}
}

最终 rasterizer.cpp 完整代码如下:

// clang-format off
//
// Created by goksu on 4/6/19.
//

#include <algorithm>
#include <vector>
#include "rasterizer.hpp"
#include <opencv2/opencv.hpp>
#include <math.h>


rst::pos_buf_id rst::rasterizer::load_positions(const std::vector<Eigen::Vector3f> &positions)
{
auto id = get_next_id();
pos_buf.emplace(id, positions);

return {id};
}

rst::ind_buf_id rst::rasterizer::load_indices(const std::vector<Eigen::Vector3i> &indices)
{
auto id = get_next_id();
ind_buf.emplace(id, indices);

return {id};
}

rst::col_buf_id rst::rasterizer::load_colors(const std::vector<Eigen::Vector3f> &cols)
{
auto id = get_next_id();
col_buf.emplace(id, cols);

return {id};
}

auto to_vec4(const Eigen::Vector3f& v3, float w = 1.0f)
{
return Vector4f(v3.x(), v3.y(), v3.z(), w);
}


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]

Eigen::Vector3f Q;
Q << float(x), float(y), 1;
Vector3f v[3];
for (int i = 0; i < 3; ++i) {
v[i] << _v[i].x(), _v[i].y(), 1;
}

Eigen::Vector3f P_01 = v[0] - v[1];
Eigen::Vector3f P_12 = v[1] - v[2];
Eigen::Vector3f P_20 = v[2] - v[0];

Eigen::Vector3f P_0Q = v[0] - Q;
Eigen::Vector3f P_1Q = v[1] - Q;
Eigen::Vector3f P_2Q = v[2] - Q;

if ((P_01.cross(P_0Q).z() > 0 && P_12.cross(P_1Q).z() > 0 && P_20.cross(P_2Q).z() > 0)
|| (P_01.cross(P_0Q).z() < 0 && P_12.cross(P_1Q).z() < 0 && P_20.cross(P_2Q).z() < 0))
return true;
return false;
}

static std::tuple<float, float, float> computeBarycentric2D(float x, float y, const Vector3f* v)
{
float c1 = (x*(v[1].y() - v[2].y()) + (v[2].x() - v[1].x())*y + v[1].x()*v[2].y() - v[2].x()*v[1].y()) / (v[0].x()*(v[1].y() - v[2].y()) + (v[2].x() - v[1].x())*v[0].y() + v[1].x()*v[2].y() - v[2].x()*v[1].y());
float c2 = (x*(v[2].y() - v[0].y()) + (v[0].x() - v[2].x())*y + v[2].x()*v[0].y() - v[0].x()*v[2].y()) / (v[1].x()*(v[2].y() - v[0].y()) + (v[0].x() - v[2].x())*v[1].y() + v[2].x()*v[0].y() - v[0].x()*v[2].y());
float c3 = (x*(v[0].y() - v[1].y()) + (v[1].x() - v[0].x())*y + v[0].x()*v[1].y() - v[1].x()*v[0].y()) / (v[2].x()*(v[0].y() - v[1].y()) + (v[1].x() - v[0].x())*v[2].y() + v[0].x()*v[1].y() - v[1].x()*v[0].y());
return {c1,c2,c3};
}

void rst::rasterizer::draw(pos_buf_id pos_buffer, ind_buf_id ind_buffer, col_buf_id col_buffer, Primitive type)
{
auto& buf = pos_buf[pos_buffer.pos_id];
auto& ind = ind_buf[ind_buffer.ind_id];
auto& col = col_buf[col_buffer.col_id];

float f1 = (50 - 0.1) / 2.0;
float f2 = (50 + 0.1) / 2.0;

Eigen::Matrix4f mvp = projection * view * model;
for (auto& i : ind)
{
Triangle t;
Eigen::Vector4f v[] = {
mvp * to_vec4(buf[i[0]], 1.0f),
mvp * to_vec4(buf[i[1]], 1.0f),
mvp * to_vec4(buf[i[2]], 1.0f)
};
//Homogeneous division
for (auto& vec : v) {
vec /= vec.w();
}
//Viewport transformation
for (auto & vert : v)
{
vert.x() = 0.5*width*(vert.x()+1.0);
vert.y() = 0.5*height*(vert.y()+1.0);
vert.z() = vert.z() * f1 + f2;
}

for (int i = 0; i < 3; ++i)
{
t.setVertex(i, v[i].head<3>());
t.setVertex(i, v[i].head<3>());
t.setVertex(i, v[i].head<3>());
}

auto col_x = col[i[0]];
auto col_y = col[i[1]];
auto col_z = col[i[2]];

t.setColor(0, col_x[0], col_x[1], col_x[2]);
t.setColor(1, col_y[0], col_y[1], col_y[2]);
t.setColor(2, col_z[0], col_z[1], col_z[2]);

rasterize_triangle(t);
}
}

//Screen space rasterization
void rst::rasterizer::rasterize_triangle(const Triangle& t) {
auto v = t.toVector4();

// TODO : Find out the bounding box of current triangle.
// iterate through the pixel and find if the current pixel is inside the triangle

int minX = std::floor(std::min(v[0][0], std::min(v[1][0], v[2][0])));
int minY = std::floor(std::min(v[0][1], std::min(v[1][1], v[2][1])));
int maxX = std::ceil(std::max(v[0][0], std::max(v[1][0], v[2][0])));
int maxY = std::ceil(std::max(v[0][1], std::max(v[1][1], v[2][1])));

// If so, use the following code to get the interpolated z value.
//auto[alpha, beta, gamma] = computeBarycentric2D(x, y, t.v);
//float w_reciprocal = 1.0/(alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
//float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();
//z_interpolated *= w_reciprocal;

for (int x = minX; x <= maxX; ++x) {
for (int y = minY; y <= maxY; ++y) {
if (insideTriangle(x + 0.5, y + 0.5, t.v)) {
auto[alpha, beta, gamma] = computeBarycentric2D(float(x) + 0.5f, float(y) + 0.5f, t.v);
float w_reciprocal = 1.0f/(alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
float z_interpolated = alpha * v[0].z() / v[0].w() + beta * v[1].z() / v[1].w() + gamma * v[2].z() / v[2].w();
z_interpolated *= w_reciprocal;

int buf_index = get_index(x, y);
if (z_interpolated >= depth_buf[buf_index])
continue;

depth_buf[buf_index] = z_interpolated;
set_pixel(Vector3f(x, y, 1), t.getColor());
}
}
}


// TODO : set the current pixel (use the set_pixel function) to the color of the triangle (use getColor function) if it should be painted.

}

void rst::rasterizer::set_model(const Eigen::Matrix4f& m)
{
model = m;
}

void rst::rasterizer::set_view(const Eigen::Matrix4f& v)
{
view = v;
}

void rst::rasterizer::set_projection(const Eigen::Matrix4f& p)
{
projection = p;
}

void rst::rasterizer::clear(rst::Buffers buff)
{
if ((buff & rst::Buffers::Color) == rst::Buffers::Color)
{
std::fill(frame_buf.begin(), frame_buf.end(), Eigen::Vector3f{0, 0, 0});
}
if ((buff & rst::Buffers::Depth) == rst::Buffers::Depth)
{
std::fill(depth_buf.begin(), depth_buf.end(), std::numeric_limits<float>::infinity());
}
}

rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)
{
frame_buf.resize(w * h);
depth_buf.resize(w * h);
}

int rst::rasterizer::get_index(int x, int y)
{
return (height-1-y)*width + x;
}

void rst::rasterizer::set_pixel(const Eigen::Vector3f& point, const Eigen::Vector3f& color)
{
//old index: auto ind = point.y() + point.x() * width;
auto ind = (height-1-point.y())*width + point.x();
frame_buf[ind] = color;

}

// clang-format on

参考文章