【GAMES101】Z-Buffer算法

本期，推送GAMES101作业2实现Z-Buffer算法。

画家算法

受画家算法的启发，从后到前绘制，在framebuffer中覆盖。

因为要排序，所以算法复杂度$\mathcal{O}(n\lg n)$。

但是对于交叉叠放这种请情况，画家算法行不通。

Z-Buffer（深度缓冲）算法

主要思想：

深度缓冲器存区每个像素的当前最小深度$z$值

深度值需要额外的缓冲区

• Frame buffer：储存颜色值
• Depth buffer (z-buffer)：储存深度值

Z-Buffer算法

• Initialization: depth buffer $\leftarrow \infty$

• Traversal:

  ---

  for each triangle $T$

  ? for each pixel $(x,y,z)$ in $T$

  ? if ($z$ < $zbuffer[x,y]$)

  ? $framebuffer[x,y]=rgb$;

  ? $zbuffer[x,y]=z$;

  ? else

  ? $?$

  ---

Z-Buffer算法复杂度

因为不需要排序，因此复杂度$\mathcal{O}(n)$

实现

实现代码

//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;auto x1 = t.v[0].x();auto y1 = t.v[0].y();auto x2 = t.v[1].x();auto y2 = t.v[1].y();auto x3 = t.v[2].x();auto y3 = t.v[2].y();std::cout << "(" << x1 << "," << y1 << ")\n";std::cout << "(" << x2 << "," << y2 << ")\n";std::cout << "(" << x3 << "," << y3 << ")\n";float max_x = std::max(std::max(x1, x2), x3);float min_x = std::min(std::min(x1, x2), x3);float max_y = std::max(std::max(y1, y2), y3);float min_y = std::min(std::min(y1, y2), y3);bool MSAA = false;if (MSAA){for (int x = min_x; x <= max_x; ++x){for (int y = min_y; y <= max_y; ++y){float minDepth = std::numeric_limits<double>::infinity();float count = 0;for (int i = 0; i < 2; ++i){for (int j = 0; j < 2; ++j){if (insideTriangle(x + 0.25 + i * 0.5, y + 0.25 + j * 0.5, t.v)){float alpha, beta, gamma;std::tie(alpha, beta, gamma) = computeBarycentric2D(x + 0.5, y + 0.5, 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;minDepth = std::min(std::fabs(minDepth), std::fabs(z_interpolated));count++;}}}auto ind = get_index(x, y);if (count != 0 && std::fabs(depth_buf[ind]) > std::fabs(minDepth)){depth_buf[ind] = minDepth;Eigen::Vector3f point = Eigen::Vector3f(x, y, minDepth);set_pixel(point, t.getColor());}}}} else{for (int x = min_x; x <= max_x; ++x){for (int y = min_y; y <= max_y; ++y){if (insideTriangle(x + 0.5, y + 0.5, t.v)){float alpha, beta, gamma;std::tie(alpha, beta, gamma) = computeBarycentric2D(x + 0.5, y + 0.5, 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;auto ind = get_index(x, y);if (std::fabs(depth_buf[ind]) > std::fabs(z_interpolated)){depth_buf[ind] = z_interpolated;Eigen::Vector3f point = Eigen::Vector3f(x, y, z_interpolated);set_pixel(point, 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.
}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]auto x1 = _v[0].x();auto y1 = _v[0].y();auto x2 = _v[1].x();auto y2 = _v[1].y();auto x3 = _v[2].x();auto y3 = _v[2].y();Eigen::Matrix<float, 2, 1> ab, bc, ca;ab << x1 - x2, y1 - y2;bc << x2 - x3, y2 - y3;ca << x3 - x1, y3 - y1;Eigen::Matrix<float, 2, 1> pa, pb, pc;pa << x1 - x, y1 - y;pb << x2 - x, y2 - y;pc << x3 - x, y3 - y;Eigen::Matrix2f H;H << 0, -1, 1, 0;double sig1 = ab.transpose() * H * pa;double sig2 = bc.transpose() * H * pb;double sig3 = ca.transpose() * H * pc;return (sig1 > 0 && sig2 > 0 && sig3 > 0) || (sig1 < 0 && sig2 < 0 && sig3 < 0);
}

渲染结果