从零开始软渲染1-直线和三角形

上回我们已经可以在屏幕上画出点了，现在我们开始画直线和三角形。

基础数据结构

我们先准备一些数据结构，如二维向量和三维向量，方便后面使用。

template <class t> struct Vec2 {     union {         struct { t u, v; };         struct { t x, y; };         t raw[2];     };     Vec2() : u(0), v(0) {}     Vec2(t _u, t _v) : u(_u), v(_v) {}     inline Vec2<t> operator +(const Vec2<t>& V) const { return Vec2<t>(u + V.u, v + V.v); }     inline Vec2<t> operator -(const Vec2<t>& V) const { return Vec2<t>(u - V.u, v - V.v); }     inline Vec2<t> operator *(float f)          const { return Vec2<t>(u * f, v * f); }     t& operator[](const size_t i) { assert(i < 2); return i <= 0 ? x : y; }     const t& operator[](const size_t i) const { assert(i < 2); return i <= 0 ? x : y; } }; template <class t> struct Vec3 {     union {         struct { t x, y, z; };         struct { t r, g, b; };         struct { t ivert, iuv, inorm; };         t raw[3];     };     Vec3() : x(0), y(0), z(0) {}     Vec3(t _x, t _y, t _z) : x(_x), y(_y), z(_z) {}     inline Vec3<t> operator ^(const Vec3<t>& v) const { return Vec3<t>(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x); }     inline Vec3<t> operator +(const Vec3<t>& v) const { return Vec3<t>(x + v.x, y + v.y, z + v.z); }     inline Vec3<t> operator -(const Vec3<t>& v) const { return Vec3<t>(x - v.x, y - v.y, z - v.z); }     inline Vec3<t> operator *(float f)          const { return Vec3<t>(x * f, y * f, z * f); }     inline t       operator *(const Vec3<t>& v) const { return x * v.x + y * v.y + z * v.z; }     float norm() const { return std::sqrt(x * x + y * y + z * z); }     Vec3<t>& normalize(t l = 1) { *this = (*this) * (l / norm()); return *this; }     t& operator[](const size_t i) { assert(i < 3); return i <= 0 ? x : (1 == i ? y : z); }     const t& operator[](const size_t i) const { assert(i < 3); return i <= 0 ? x : (1 == i ? y : z); } }; typedef Vec2<float> Vec2f; typedef Vec2<int>   Vec2i; typedef Vec3<float> Vec3f; typedef Vec3<int>   Vec3i; template <typename T> Vec3<T> cross(Vec3<T> v1, Vec3<T> v2) {     return Vec3<T>(v1.y * v2.z - v1.z * v2.y, v1.z * v2.x - v1.x * v2.z, v1.x * v2.y - v1.y * v2.x); }

 

先说直线

说到画直线，就要提到大名鼎鼎的Bresenham算法了。

简单说一下算法的原理，考虑画一条斜率在0到1之间的直线，给定起点和终点后，如果从左下角开始画，起点作为第一个点，那么第二个点如何选择？横坐标很好确定，直接从上一个点的横坐标加1就可以得到，纵坐标怎么办？因为斜率不超过1，所以纵坐标只有两种选择：要么和上一个点相同，要么比上一个点加1。那么究竟要不要加1，就要根据这两种选择哪一个离直线更近来确定了。以此类推，直到到达终点。斜率超过1的可以交换横纵坐标来画。Bresenham算法最精妙的地方就在于给出了高效判定的方法，具体的数学推到这里就不详述了，网上可以搜到大把大把的资料，直接贴出代码。

void line(int x0, int y0, int x1, int y1) {        bool steep = false;     if (std::abs(x0 - x1) < std::abs(y0 - y1)) {         std::swap(x0, y0);         std::swap(x1, y1);         steep = true;     }     if (x0 > x1) {         std::swap(x0, x1);         std::swap(y0, y1);     }     int dx = x1 - x0;     int dy = y1 - y0;     float derror = std::abs(dy / float(dx));     float error = 0;     int y = y0;     for (int x = x0; x <= x1; x++) {         if (steep) {             SDLDrawPixel(y, x);         }         else {             SDLDrawPixel(x, y);         }         error += derror;         if (error > .5) {             y += (y1 > y0 ? 1 : -1);             error -= 1.;         }     } }

简单画两条线试一下：

line(100, 65, 200, 400); line(400, 200, 65, 100);

 

再说三角形

为什么要画三角形？而不是四边形五边形之类的？因为三角形是计算机图形学面的最小单位，有了三角形，就可以拼出各种各样的面了。

怎么画三角形？提到画三角形，很多资料都会提到扫描线算法，按照从上到下从左到右的顺序把三角形内部填充完毕，非常符合直觉的一个算法，不过现代GPU已经不用了。

那么现代GPU用什么呢？答案是重心坐标系(barycentric coordinates)。

重心坐标系可以帮助我们判断点是否在三角形内，并且可以对顶点属性（颜色、UV等）线性插值。对于画三角形来说，只需要第一点。我们拿到三角形的包围盒，然后遍历包围盒里的每个一点，计算重心坐标，如果在三角形内，就把点绘制出来。

Vec3f barycentric(Vec2i* pts, Vec2i P) {     Vec3f u = cross(Vec3f(pts[2][0] - pts[0][0], pts[1][0] - pts[0][0], pts[0][0] - P[0]), Vec3f(pts[2][1] - pts[0][1], pts[1][1] - pts[0][1], pts[0][1] - P[1]));     /* `pts` and `P` has integer value as coordinates        so `abs(u[2])` < 1 means `u[2]` is 0, that means        triangle is degenerate, in this case return something with negative coordinates */     if (std::abs(u[2]) < 1) return Vec3f(-1, 1, 1);     return Vec3f(1.f - (u.x + u.y) / u.z, u.y / u.z, u.x / u.z); } void triangle(Vec2i* pts) {     Vec2i bboxmin(SCREEN_WIDTH - 1, SCREEN_HEIGHT - 1);     Vec2i bboxmax(0, 0);     Vec2i clamp(SCREEN_WIDTH - 1, SCREEN_HEIGHT - 1);     for (int i = 0; i < 3; i++) {         for (int j = 0; j < 2; j++) {             bboxmin[j] = std::max(0, std::min(bboxmin[j], pts[i][j]));             bboxmax[j] = std::min(clamp[j], std::max(bboxmax[j], pts[i][j]));         }     }     Vec2i P;     for (P.x = bboxmin.x; P.x <= bboxmax.x; P.x++) {         for (P.y = bboxmin.y; P.y <= bboxmax.y; P.y++) {             Vec3f bc_screen = barycentric(pts, P);             if (bc_screen.x < 0 || bc_screen.y < 0 || bc_screen.z < 0) continue;             SDLDrawPixel(P.x, P.y);         }     } }

 

附上一个参考链接：

https://zhuanlan.zhihu.com/p/58199366

 

下面来试试画三角形的函数：

    Vec2i pts[3] = { Vec2i(10,10), Vec2i(100, 30), Vec2i(190, 160) }; triangle(pts);

运行可以看到结果：

嗯，大功告成。