画三角形
2023-3-25 ~ 2023-3-26
(0)
扫描线算法
首先根据三角形三个顶点的 y 坐标值，设 y 最小的顶点为 a(x₀, y₀)，y 最大的顶点为 c(x₂, y₂)，另一个顶点为 b(x₁, y₁)
其次填充 y₀~y₁ 之间的三角形区域，只需求出线段 ab，线段 ac 与直线 y = c (y₀ < c < y₁)，的交点 x_b，x_c，进行排序实际上是数值修改确保 x_b < x_c，然后填充 {(x, c) | x_b < x < x_c} 上的所有点。
最后填充 y₁~y₂ 之间的三角形区域，同上求出线段 bc，线段 ac 与直线 y = c (y₁ < c < y₂)，的交点 x_b，x_c，进行排序实际上是数值修改确保 x_b < x_c，然后填充 {(x, c) | x_b < x < x_c} 上的所有点。
求交点的方法可以用到参数方程的方法。
线性插值
设三角形三个顶点拥有不同的深度值 depth_a、depth_b、depth_c，要求三角形内任意点的深度值可以用线性插值的方法。
假设三角形内一点 p(x, y)，三角形三个点为 a、b、c，得到向量 ab(x₀, y₀)、ac(x₁, y₁)、ap(x₂, y₂) (x₀, y₀, x₁, y₁, x₂, y₂ 均与上文无关)。可以得出下式：
ap = m * ab + n * ac (0 <= m <= 1, 0 <= n <= 1, ap、ab、ac 均为向量)
此时点 p 的深度值为 depth_p = depth_a + (depth_b - depth_a) * m + (depth_c - depth_a) * n。
联立①②二式
① m * x₀ + n * x₁ = x₂
② m * y₀ + n * y₁ = y₂
得 m = (x₁ * y₂ - x₂ * y₁) / (x₁ * y₀ - x₀ * y₁)、n = (x₂ * y₀ - x₀ * y₂) / (x₁ * y₀ - x₀ * y₁)。
深度检测
要求出三维点在投影面上的深度只用求出三维点到摄像机平面的距离就行，设摄像机平面的法向量为 normalVec(x, y, z)，摄像机中心位置为 O，求出摄像机中心到三维点的向量 OP，求出 OP 在 normalVec 上的投影的长度 depth，此 depth 即为此三维点的深度。定义 DepthMap 保存屏幕上每个点的深度值，每个点的深度值可以用线性插值的方法求出，若新的像素点的深度值比在 DepthMap 上对应位置的深度值大，说明此像素点被遮挡，就不绘制此像素点，反之绘制此像素点并更新 DepthMap。
代码实现
////////////////////////////////////////////
// 程序：画三角形
// 作者：我想做三国志
// 编译环境：Visual Studio 2022，EasyX_20220901
// 编写日期：2023-3-26
#include <graphics.h>
#include <math.h>
#include <vector>
const double PI = 3.1415926536; // π
const int WIDTH = 640; // 屏幕宽度
const int HEIGHT = 480; // 屏幕高度
const int GAMEPAD = 60; // 游戏手柄，移动多少距离旋转 60
const double ProjectSurfaceDis = 500;
using std::vector;
// 三维向量
class Vec3
{
public:
double xx, yy, zz;
// 构造函数
Vec3(double xx = 0, double yy = 0, double zz = 0) : xx(xx), yy(yy), zz(zz) {}
// 向量相加
Vec3 operator+(Vec3 num) { return Vec3(this->xx + num.xx, this->yy + num.yy, this->zz + num.zz); }
// 向量乘法
Vec3 operator*(double num) { return Vec3(this->xx * num, this->yy * num, this->zz * num); }
// 向量点乘
double operator*(Vec3 num) { return this->xx * num.xx + this->yy * num.yy + this->zz * num.zz; }
// 向量除法
Vec3 operator/(double num) { return Vec3(this->xx / num, this->yy / num, this->zz / num); }
// 向量相减
Vec3 operator-(Vec3 num) { return Vec3(this->xx - num.xx, this->yy - num.yy, this->zz - num.zz); }
// 得到此向量模长
double GetLength() { return sqrt(this->xx * this->xx + this->yy * this->yy + this->zz * this->zz); }
// 得到两向量之间的 cos 值
double GetCosBetween(Vec3 num) { return (*this) * num / this->GetLength() / num.GetLength(); }
// 得到此向量的单位向量
Vec3 GetUnitVector() { return (*this) / this->GetLength(); }
// 得到此向量在另一个向量上的投影
Vec3 GetProjectionTo(Vec3 num) { return num.GetUnitVector() * (this->GetCosBetween(num) * this->GetLength()); }
// 向量叉乘
Vec3 MultiplicationCross(Vec3 num) { return Vec3(this->yy * num.zz - this->zz * num.yy, -this->xx * num.zz + this->zz * num.xx, this->xx * num.yy - this->yy * num.xx); }
// 求将此向量关于 X 轴，Y 轴，Z 轴旋转 a、b、c 度后的向量
Vec3 GetRotateVec(double a, double b, double c)
{
Vec3 result = this->GetUnitVector();
result = Vec3(result.xx, result.yy * cos(a) - result.zz * sin(a), result.zz * cos(a) + result.yy * sin(a)).GetUnitVector();
result = Vec3(result.xx * cos(b) - result.zz * sin(b), result.yy, result.zz * cos(b) + result.xx * sin(b)).GetUnitVector();
result = Vec3(result.xx * cos(c) - result.yy * sin(c), result.yy * cos(c) + result.xx * sin(c), result.zz).GetUnitVector();
return (result * this->GetLength());
}
};
// 二维向量
class Vec2
{
public:
double xx, yy;
// 构造函数
Vec2(double xx = 0, double yy = 0) : xx(xx), yy(yy) {}
// 向量相加
Vec2 operator+(Vec2 num) { return Vec2(this->xx + num.xx, this->yy + num.yy); }
// 向量乘法
Vec2 operator*(double num) { return Vec2(this->xx * num, this->yy * num); }
// 向量点乘
double operator*(Vec2 num) { return this->xx * num.xx + this->yy * num.yy; }
// 向量除法
Vec2 operator/(double num) { return Vec2(this->xx / num, this->yy / num); }
// 向量相减
Vec2 operator-(Vec2 num) { return Vec2(this->xx - num.xx, this->yy - num.yy); }
// 得到此向量模长
double GetLength() { return sqrt(this->xx * this->xx + this->yy * this->yy); }
// 得到两向量之间的 cos 值
double GetCosBetween(Vec2 num) { return (*this) * num / this->GetLength() / num.GetLength(); }
// 得到此向量的单位向量
Vec2 GetUnitVector() { return (*this) / this->GetLength(); }
// 得到此向量在另一个向量上的投影
Vec2 GetProjectionTo(Vec2 num) { return num.GetUnitVector() * (this->GetCosBetween(num) * this->GetLength()); }
// 得到此向量旋转 angle 后的向量
Vec2 GetRotateVec(double angle) { return Vec2(this->xx * cos(angle) - this->yy * sin(angle), this->yy * cos(angle) + this->xx * sin(angle)); }
};
// 2 维顶点
class Vertex2D
{
public:
Vec2 pos;
double R, G, B;
double depth;
Vertex2D(Vec2 pos = Vec2(), double R = 0, double G = 0, double B = 0, double depth = 0) :pos(pos), R(R), G(G), B(B), depth(depth) {}
};
// 3 维顶点
class Vertex3D
{
public:
Vec3 pos;
double R, G, B;
Vertex3D(Vec3 pos = Vec3(), double R = 0, double G = 0, double B = 0) :pos(pos), R(R), G(G), B(B) {}
};
// 2 维三角形
class Triangle2D
{
public:
Vertex2D vertex[3];
// 判断是否在 2 维三角形内
bool isInTriangle(Vec2 pos)
{
Vec2 vec_side_1 = vertex[1].pos - vertex[0].pos;
Vec2 vec_side_2 = vertex[2].pos - vertex[0].pos;
Vec2 vec_1 = pos - vertex[0].pos;
// vec_side_1*m+vec_side_2*n=vec_1
double n = (vec_1.xx * vec_side_1.yy - vec_1.yy * vec_side_1.xx) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
double m = (vec_1.yy * vec_side_2.xx - vec_1.xx * vec_side_2.yy) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
if (n >= 0 && m >= 0 && n + m <= 1)return true;
return false;
}
// 绘画 2 维三角形
void Draw(double* DepthMap, int w, int h)
{
int index[3] = { 0, 1, 2 };
if (vertex[index[0]].pos.yy > vertex[index[1]].pos.yy)
index[0] ^= index[1] ^= index[0] ^= index[1]; // 交换两个值
if (vertex[index[0]].pos.yy > vertex[index[2]].pos.yy)
index[0] ^= index[2] ^= index[0] ^= index[2]; // 交换两个值
if (vertex[index[1]].pos.yy > vertex[index[2]].pos.yy)
index[2] ^= index[1] ^= index[2] ^= index[1]; // 交换两个值
Vec2 vec_side_1 = vertex[index[1]].pos - vertex[index[0]].pos;
Vec2 vec_side_2 = vertex[index[2]].pos - vertex[index[0]].pos;
// 0~1
for (int i = (int)vertex[index[0]].pos.yy; i < (int)vertex[index[1]].pos.yy; i++)
{
if (i < 0 || i >= h) continue;
double t_b = (i - (int)vertex[index[0]].pos.yy) / (double)((int)vertex[index[1]].pos.yy - (int)vertex[index[0]].pos.yy);
double t_c = (i - (int)vertex[index[0]].pos.yy) / (double)((int)vertex[index[2]].pos.yy - (int)vertex[index[0]].pos.yy);
int x_b = vertex[index[0]].pos.xx + (vertex[index[1]].pos.xx - vertex[index[0]].pos.xx) * t_b;
int x_c = vertex[index[0]].pos.xx + (vertex[index[2]].pos.xx - vertex[index[0]].pos.xx) * t_c;
if (x_b > x_c)
x_b ^= x_c ^= x_b ^= x_c;
for (int j = x_b; j < x_c; j++)
{
if (j < 0 || j >= w) continue;
Vec2 vec_1 = Vec2(j, i) - vertex[index[0]].pos;
// vec_side_1*m+vec_side_2*n=vec_1
double n = (vec_1.xx * vec_side_1.yy - vec_1.yy * vec_side_1.xx) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
double m = (vec_1.yy * vec_side_2.xx - vec_1.xx * vec_side_2.yy) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
double depth = vertex[index[0]].depth + (vertex[index[1]].depth - vertex[index[0]].depth) * m + (vertex[index[2]].depth - vertex[index[0]].depth) * n;
if (depth < DepthMap[i * w + j] || depth>0 && DepthMap[i * w + j] <= 0)
{
double R = max(min(vertex[index[0]].R + (vertex[index[1]].R - vertex[index[0]].R) * m + (vertex[index[2]].R - vertex[index[0]].R) * n, 255), 0);
double G = max(min(vertex[index[0]].G + (vertex[index[1]].G - vertex[index[0]].G) * m + (vertex[index[2]].G - vertex[index[0]].G) * n, 255), 0);
double B = max(min(vertex[index[0]].B + (vertex[index[1]].B - vertex[index[0]].B) * m + (vertex[index[2]].B - vertex[index[0]].B) * n, 255), 0);
COLORREF col = RGB(R, G, B);
putpixel(j, i, col);
DepthMap[i * w + j] = depth;
}
}
}
// 1~2
for (int i = (int)vertex[index[1]].pos.yy; i < (int)vertex[index[2]].pos.yy; i++)
{
if (i < 0 || i >= h) continue;
double t_b = (i - (int)vertex[index[1]].pos.yy) / (double)((int)vertex[index[2]].pos.yy - (int)vertex[index[1]].pos.yy);
double t_c = (i - (int)vertex[index[0]].pos.yy) / (double)((int)vertex[index[2]].pos.yy - (int)vertex[index[0]].pos.yy);
int x_b = vertex[index[1]].pos.xx + (vertex[index[2]].pos.xx - vertex[index[1]].pos.xx) * t_b;
int x_c = vertex[index[0]].pos.xx + (vertex[index[2]].pos.xx - vertex[index[0]].pos.xx) * t_c;
if (x_b > x_c)
x_b ^= x_c ^= x_b ^= x_c;
for (int j = x_b; j < x_c; j++)
{
if (j < 0 || j >= w) continue;
Vec2 vec_1 = Vec2(j, i) - vertex[index[0]].pos;
// vec_side_1*m+vec_side_2*n=vec_1
double n = (vec_1.xx * vec_side_1.yy - vec_1.yy * vec_side_1.xx) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
double m = (vec_1.yy * vec_side_2.xx - vec_1.xx * vec_side_2.yy) / (vec_side_2.xx * vec_side_1.yy - vec_side_2.yy * vec_side_1.xx);
double depth = vertex[index[0]].depth + (vertex[index[1]].depth - vertex[index[0]].depth) * m + (vertex[index[2]].depth - vertex[index[0]].depth) * n;
if (depth < DepthMap[i * w + j] || depth>0 && DepthMap[i * w + j] <= 0)
{
double R = max(min(vertex[index[0]].R + (vertex[index[1]].R - vertex[index[0]].R) * m + (vertex[index[2]].R - vertex[index[0]].R) * n, 255), 0);
double G = max(min(vertex[index[0]].G + (vertex[index[1]].G - vertex[index[0]].G) * m + (vertex[index[2]].G - vertex[index[0]].G) * n, 255), 0);
double B = max(min(vertex[index[0]].B + (vertex[index[1]].B - vertex[index[0]].B) * m + (vertex[index[2]].B - vertex[index[0]].B) * n, 255), 0);
COLORREF col = RGB(R, G, B);
putpixel(j, i, col);
DepthMap[i * w + j] = depth;
}
}
}
}
};
// 3 维三角形
class Triangle3D
{
public:
Vertex3D vertex[3];
};
// 得到三维空间中的点在投影面上的投影
Vec2 GetProjectInSurface(Vec3 project, Vec3 X_Across, Vec3 Y_Across, Vec2 pericenter) // 这个是平行投影
{
return pericenter +
Vec2(project.GetLength() * project.GetCosBetween(X_Across),
project.GetLength() * project.GetCosBetween(Y_Across));
}
// 获取 3 维点的深度
double GetDepth(Vec3 pos, Vec3 ZAcross, double cameraLength)
{
double ori = pos * ZAcross / ZAcross.GetLength();
return cameraLength - ori;
}
// 将 3 维顶点转化为 2 为顶点
Vertex2D TransformV3DToV2D(Vertex3D vertex, Vec3 XAcross, Vec3 YAcross, double dis, Vec2 pericenter)
{
return Vertex2D(GetProjectInSurface(vertex.pos, XAcross, YAcross, pericenter), vertex.R, vertex.G, vertex.B,
GetDepth(vertex.pos, XAcross.MultiplicationCross(YAcross), dis));
}
// 将 3 维三角形转化为 2 维三角形
Triangle2D TransformT3DToT2D(Triangle3D tri, Vec3 XAcross, Vec3 YAcross, double dis, Vec2 pericenter)
{
Triangle2D result;
for (int i = 0; i < 3; i++)
result.vertex[i] = TransformV3DToV2D(tri.vertex[i], XAcross, YAcross, dis, pericenter);
return result;
}
// 鼠标横向拖动时 X 轴，Y 轴关于 Y 轴旋转
Vec3 HorizontalRotate(Vec3 X_Across, Vec3 Y_Across, double angle)
{
Vec3 Z_Across = X_Across.MultiplicationCross(Y_Across);
X_Across = X_Across * cos(angle) + Z_Across * sin(angle);
return X_Across.GetUnitVector();
}
// 鼠标竖向拖动时 X 轴，Y 轴关于 X 轴旋转
Vec3 VerticalRotate(Vec3 X_Across, Vec3 Y_Across, double angle)
{
Vec3 Z_Across = X_Across.MultiplicationCross(Y_Across);
Y_Across = Y_Across * cos(angle) + Z_Across * sin(angle);
return Y_Across.GetUnitVector();
}
// 绘画三维三角形
void DrawTriangle3D(Triangle3D tri, Vec3 XAcross, Vec3 YAcross, double dis, Vec2 pericenter, double* DepthMap, int w, int h)
{
TransformT3DToT2D(tri, XAcross, YAcross, dis, pericenter).Draw(DepthMap, w, h);
}
// 主函数
int main()
{
Vec3 X_Across(1, 0, 0), Y_Across(0, 1, 0);
initgraph(WIDTH, HEIGHT);
BeginBatchDraw();
Triangle3D tri_1, tri_2;
tri_1.vertex[0] = Vertex3D(Vec3(-100, 0, 0), 255, 0, 0);
tri_1.vertex[1] = Vertex3D(Vec3(100, 0, 0), 0, 255, 0);
tri_1.vertex[2] = Vertex3D(Vec3(0, 100, 0), 0, 0, 255);
tri_2.vertex[0] = Vertex3D(Vec3(0, 0, -100), 255, 255, 0);
tri_2.vertex[1] = Vertex3D(Vec3(0, 0, 100), 0, 255, 255);
tri_2.vertex[2] = Vertex3D(Vec3(0, 100, 0), 255, 0, 255);
double* DepthMap = new double[WIDTH * HEIGHT];
memset(DepthMap, 0, sizeof(double) * WIDTH * HEIGHT);
bool isExit = false;
bool isLPress = false;
Vec2 ori_L;
ExMessage msg;
while (!isExit)
{
while (peekmessage(&msg, EM_KEY | EM_MOUSE))
{
if (msg.message == WM_KEYDOWN)
{
if (msg.vkcode == VK_ESCAPE) isExit = true;
}
else if (msg.message == WM_MOUSEMOVE || msg.message == WM_LBUTTONDOWN || msg.message == WM_LBUTTONUP)
{
if (!isLPress && msg.lbutton)
{
ori_L = Vec2(msg.x, msg.y);
isLPress = true;
}
else if (isLPress && msg.lbutton)
{
Vec2 next = Vec2(msg.x, msg.y);
ori_L = next - ori_L;
double Th = 0;
double Fi = 0;
Th = ori_L.xx / GAMEPAD * PI / 3;
Fi = ori_L.yy / GAMEPAD * PI / 3;
X_Across = HorizontalRotate(X_Across, Y_Across, Th);
Y_Across = VerticalRotate(X_Across, Y_Across, Fi);
ori_L = next;
}
else if (isLPress && !msg.lbutton)
{
isLPress = false;
}
}
}
cleardevice();
memset(DepthMap, 0, sizeof(double) * WIDTH * HEIGHT);
DrawTriangle3D(tri_1, X_Across, Y_Across, ProjectSurfaceDis, Vec2(WIDTH / 2, HEIGHT / 2), DepthMap, WIDTH, HEIGHT);
DrawTriangle3D(tri_2, X_Across, Y_Across, ProjectSurfaceDis, Vec2(WIDTH / 2, HEIGHT / 2), DepthMap, WIDTH, HEIGHT);
FlushBatchDraw();
}
delete[] DepthMap;
return 0;
}
添加评论
取消回复