软光栅|03三角形与光栅化
简单绘制一个三角形
上一节末我们已经能够画一条直线了
void line(int x0, int y0, int x1, int y1, TGAImage& image, TGAColor color)
{
// ...
}
在VS里新建一个geometry.h，然后把代码复制进去，这个头文件里就是一些坐标类型和计算，这个头文件依旧来自最开始介绍的git，你想去自己下载也行~
#ifndef __GEOMETRY_H__
#define __GEOMETRY_H__
#include <cmath>
#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <class t> struct Vec2
{
t raw[2];
t& x;
t& y;
Vec2<t>() : raw(), x(raw[0]), y(raw[1]) { x = y = t(); }
Vec2<t>(t _x, t _y) : raw(), x(raw[0]), y(raw[1]) { x = _x; y = _y; }
Vec2<t>(const Vec2<t>& v) : raw(), x(raw[0]), y(raw[1]) { *this = v; }
Vec2<t>& operator =(const Vec2<t>& v)
{
if (this != &v)
{
x = v.x;
y = v.y;
}
return *this;
}
Vec2<t> operator +(const Vec2<t>& V) const { return Vec2<t>(x + V.x, y + V.y); }
Vec2<t> operator -(const Vec2<t>& V) const { return Vec2<t>(x - V.x, y - V.y); }
Vec2<t> operator *(float f) const { return Vec2<t>(x * f, y * f); }
t& operator[](const int i) { return raw[i]; }
template <class > friend std::ostream& operator<<(std::ostream& s, Vec2<t>& v);
};
template <class t> struct Vec3
{
t raw[3];
t& x;
t& y;
t& z;
Vec3<t>() : raw(), x(raw[0]), y(raw[1]), z(raw[2]) { x = y = z = t(); }
Vec3<t>(t _x, t _y, t _z) : raw(), x(raw[0]), y(raw[1]), z(raw[2]) { x = _x; y = _y; z = _z; }
template <class u> Vec3<t>(const Vec3<u>& v);
Vec3<t>(const Vec3<t>& v) : raw(), x(raw[0]), y(raw[1]), z(raw[2]) { *this = v; }
Vec3<t>& operator =(const Vec3<t>& v)
{
if (this != &v)
{
x = v.x;
y = v.y;
z = v.z;
}
return *this;
}
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); }
Vec3<t> operator +(const Vec3<t>& v) const { return Vec3<t>(x + v.x, y + v.y, z + v.z); }
Vec3<t> operator -(const Vec3<t>& v) const { return Vec3<t>(x - v.x, y - v.y, z - v.z); }
Vec3<t> operator *(float f) const { return Vec3<t>(x * f, y * f, z * f); }
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 int i) { return raw[i]; }
template <class > friend std::ostream& operator<<(std::ostream& s, Vec3<t>& v);
};
typedef Vec2<float> Vec2f;
typedef Vec2<int> Vec2i;
typedef Vec3<float> Vec3f;
typedef Vec3<int> Vec3i;
template <> template <> Vec3<int>::Vec3(const Vec3<float>& v);
template <> template <> Vec3<float>::Vec3(const Vec3<int>& v);
template <class t> std::ostream& operator<<(std::ostream& s, Vec2<t>& v)
{
s << "(" << v.x << ", " << v.y << ")\n";
return s;
}
template <class t> std::ostream& operator<<(std::ostream& s, Vec3<t>& v)
{
s << "(" << v.x << ", " << v.y << ", " << v.z << ")\n";
return s;
}
//////////////////////////////////////////////////////////////////////////////////////////////
const int DEFAULT_ALLOC = 4;
class Matrix
{
std::vector<std::vector<float> > m;
int rows, cols;
public:
Matrix(int r = DEFAULT_ALLOC, int c = DEFAULT_ALLOC);
inline int nrows();
inline int ncols();
static Matrix identity(int dimensions);
std::vector<float>& operator[](const int i);
Matrix operator*(const Matrix& a);
Matrix transpose();
Matrix inverse();
friend std::ostream& operator<<(std::ostream& s, Matrix& m);
};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#endif //__GEOMETRY_H__
然后我们把原本的line函数再封装一下，改用Vec2i类型，或者就直接把原来的line的参数改掉就行…我就是懒得改了…
void line(Vec2i t0, Vec2i t1,TGAImage& image, TGAColor color)
{
line(t0.x, t0.y, t1.x, t1.y, image, color);
}
然后利用这个函数很容易写出一三角形的绘制方法
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
line(t0, t1, image, color);
line(t1, t2, image, color);
line(t2, t0, image, color);
}
测试一下
const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red = TGAColor(255, 0, 0, 255);
const TGAColor green = TGAColor(0, 255, 0, 255);
const int width = 200;
const int height = 200;
int main()
{
TGAImage image(width, height, TGAImage::RGB);
Vec2i t0[3] = { Vec2i(10, 70), Vec2i(50, 160), Vec2i(70, 80) };
Vec2i t1[3] = { Vec2i(180, 50), Vec2i(150, 1), Vec2i(70, 180) };
Vec2i t2[3] = { Vec2i(180, 150), Vec2i(120, 160), Vec2i(130, 180) };
triangle(t0[0], t0[1], t0[2], image, red);
triangle(t1[0], t1[1], t1[2], image, white);
triangle(t2[0], t2[1], t2[2], image, green);
image.flip_vertically();
image.write_tga_file("output.tga");
return 0;
}
这是很简单的…但不是我们想要的…很显然，我们应该需要一个填充满的三角形，而不是像这样只有边框
填充一个三角形
思路是很简单的，我们遍历所有的像素，然后判断这个像素在不在某个三角形内，如果在，那就填充他
因为有多个三角形，所以我们是分批遍历的，也就是说如果有3个三角形，那么就需要把所有的像素遍历3遍，但很明显这是有很大改进空间的，对于某一个三角形来说，我们不需要遍历所有的像素，只需要遍历它的包围盒就行
如图，假设这是一张30x30像素的图像，那么，如果我们想要遍历所有像素，那就需要计算900次，而三角形的包围盒，就是图中红色部分，我们只遍历这部分的话，那很明显，只需要遍历6x10=60次，当三角形数量非常大时，效率会提升非常的多！
那么现在就有两个问题
- 怎么确定一个三角形的包围盒？
- 怎么判断某一个点是否在三角形内？
第一个问题是比较简单的，根据3个顶点的坐标，很容易就能够确定这个包围盒，那么如何解决问题2呢？一般来说，我们会利用向量的叉乘
关于向量的叉乘我就不科普太多了，这部分知识掌我握程度不够，理解也很浅，这边就直接展示他的原理了
首先二维向量叉乘的公式是 (x1,y1)x(x2,y2)=x2y1-x1y2，结果是一个值（其实应该也算是向量，不多解释了）
那么怎么利用这个公式来判断D E两点是否在三角形内呢？
A(4,5) B(6,15) E(3,10) D(7,10)
AB=(2,10) AE=(-1,5) AD=(3,5)
ABxAE = -10 - 10 = -20
ABxAD = 30 - 10 = 20
结果很明显了，如果E点在AB的外侧，那么ABxAE就<0，反之如果D点在AB的内侧，ABxAD就>0
真的如此吗？
看起来是这样的..但其实不一定，多试几次就会发现问题…根据我们求的顺序可能会发生<0在内侧而>0在外侧的情况
但有一个结论是一定的：如果P点在三角形内侧，那么他与三个顶点组成的向量，分别叉乘的结果是一致的，即要么都大于0要么都小于0
所以我们依次计算
ABxAD BCxBD CAxCD
如果每一个结果都>0或者都<0，那就说明这个点在三角形的内部，如果有大有小，那么就在三角形外侧
注意一定要按顺序，要么是ABxAD BCxBD CAxCD要么是ACxAD CBxCD BAxBD
想实现这个算法的方式有很多，直接利用三维向量的cross来做是最简单的，但是可能不太好理解，这里我写上我的做法，非常非常非常的直观~
// pts是三角形的三个顶点，P就是想判断的点
int barycentric(Vec2i* pts, Vec2i P)
{
int pre = -1;
for (int i = 0; i < 3; i++)
{
// AB = B - A
int x1 = pts[(i + 1) % 3][0] - pts[i][0];
int y1 = pts[(i + 1) % 3][1] - pts[i][1];
// AP = P - A
int x2 = P[0] - pts[i][0];
int y2 = P[1] - pts[i][1];
// x2y1-x1y2
int res = (x2 * y1 - x1 * y2);
// 第一次的时候我们就确定好，这个点如果在内侧，是需要都大于0还是都小于0，只有第一次会计算哦
if (pre == -1)
{
pre = res > 0 ? 1 : 0;
}
res = res > 0 ? 1 : 0;
if (res != pre)
{
return 0;
}
}
return 1;
}
然后我们来改善我们的三角形算法
void triangle(Vec2i *pts, TGAImage &image, TGAColor color) {
// 这里是包围盒的最大最小范围
Vec2i bboxmin(image.get_width()-1, image.get_height()-1);
Vec2i bboxmax(0, 0);
// 这个是用来限制我们的范围，总不能比图片本身大小还大吧？
Vec2i clamp(image.get_width()-1, image.get_height()-1);
// 分别对三个顶点遍历
for (int i=0; i<3; i++)
{
// 分别对xy遍历
for (int j=0; j<2; j++)
{
// 这里嵌套了两层，先比较当前记录的最小和当前顶点，再比较0和最小点
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++)
{
int res = barycentric(pts, P);
if (res == 0)
continue;
image.set(P.x, P.y, color);
}
}
}
测试一下吧
int main()
{
TGAImage frame(200, 200, TGAImage::RGB);
Vec2i pts[3] = { Vec2i(10,10), Vec2i(100, 30), Vec2i(190, 160) };
triangle(pts, frame, red);
frame.flip_vertically();
frame.write_tga_file("output.tga");
return 0;
}
引入模型解析文件
在这里，下载model.h，model.cpp，并把obj文件夹里的模型数据文件也下载下来，导入VS中
我们用txt打卡obj文件夹中的文件，发现就是一堆数据而已
具体的数据格式解析可以参考这里，注意这是obj文件，不是fbx
模型绘制
const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red = TGAColor(255, 0, 0, 255);
const TGAColor green = TGAColor(0, 255, 0, 255);
Model* model = NULL;
const int width = 800;
const int height = 800;
int main()
{
model = new Model("obj/african_head.obj");
TGAImage image(width, height, TGAImage::RGB);
Vec3f light_dir(0, 0, -1);
// model->nfaces()代表这个obj数据一共有多少个面
for (int i = 0; i < model->nfaces(); i++)
{
// 这里我们获取到模型的某一个面
std::vector<int> face = model->face(i);
// 每一个面由3个顶点构成，这里我们获取到这3个定点，保存到screen_coords中
Vec2i screen_coords[3];
for (int j = 0; j < 3; j++)
{
// 注意，obj中我们获取到的是顶点数据，是世界坐标，而我们绘制在屏幕上需要的是屏幕坐标，是需要转换的
Vec3f world_coords = model->vert(face[j]);
screen_coords[j] = Vec2i((world_coords.x + 1.) * width / 2., (world_coords.y + 1.) * height / 2.);
}
// 最终我们得到了三个顶点坐标，注意这里是没有z的，只用了xy
triangle(screen_coords, image, white);
}
image.flip_vertically();
image.write_tga_file("output.tga");
delete model;
return 0;
}
结果会是一张纯白的图片，看起来完全不是一个3D模型，为什么会这样？
其实算法是没有问题的，但我们绘制的时候只是单纯的调用了绘制三角形的方法，而它会把三角形内的像素都填充为白色，并没有考虑三角形的朝向与颜色的关系，那自然就是纯白的一张图片了
稍微改进一下
int main()
{
model = new Model("obj/african_head.obj");
TGAImage image(width, height, TGAImage::RGB);
// 定义一个光照方向，用来计算颜色衰减，(0,0,-1)代表垂直往图片内看
Vec3f light_dir(0, 0, -1);
for (int i = 0; i < model->nfaces(); i++)
{
std::vector<int> face = model->face(i);
Vec2i screen_coords[3];
// 这里我们保存一下我们的世界坐标
Vec3f world_coords[3];
for (int j = 0; j < 3; j++)
{
Vec3f v = model->vert(face[j]);
screen_coords[j] = Vec2i((v.x + 1.) * width / 2., (v.y + 1.) * height / 2.);
world_coords[j] = v;
}
// 这里计算的是当前这个三角形面的法线，计算的很粗略，其实原理很简单，这里是世界坐标是三维的，我们知道三角形的三个顶点坐标，那很容易知道任意两条边 // 的向量，而三维向量的叉乘，结果还是一个向量，并且同时垂直于叉乘的两个向量，那可不就是这个面的法线嘛？
Vec3f n = (world_coords[2] - world_coords[0]) ^ (world_coords[1] - world_coords[0]);
n.normalize();
// 用光照方向乘以法线方向，注意这里是点积
// 其实也很好理解，如果法线方向是(0,0,-1)和光照方向完全一致，那么结果就是1,
// 如果法线方向类似于(0,0,1)和光照方向是反的，结果就是个负数，那么说明这个面是背对我们的，就不需要绘制了
// 而如果法线方向是其他的方向，比如(0.5,0,-0.5)，稍微有点偏斜的方向，那么结果就是0.5，说明这个三角形的亮度需要暗一些
// 当然这只是粗略计算
float intensity = n * light_dir;
if (intensity > 0)
{
triangle(screen_coords, image, TGAColor(intensity * 255, intensity * 255, intensity * 255, 255));
}
}
image.flip_vertically();
image.write_tga_file("output.tga");
delete model;
return 0;
}
图中的每一个部分都是三角形，很容易发现三角形的朝向和颜色有直接关系，不难理解~
但是我们会发现嘴巴和眼睛那里有很大的问题
我直接说原因了，比如嘴巴那部分，其实绘制的不是嘴巴，而是我们的后脑勺，为什么？
因为我们现在没有利用到坐标里的z轴，也就是说，如果我们的后脑勺和嘴巴，他们的三角形面片都是正面（因为如果是背面那会被忽视）
我们先绘制了嘴巴，然后再绘制后脑勺，这时候我们的嘴巴部分是会被覆盖的！！！
这就需要考虑Z-Buffer了，也就是深度缓冲~
不过那是下节课的内容啦！