games101 HomeWork1

games101 HomeWork 1

说起来我自己写games101的作业也是曲曲折折,虚拟机很卡就拿VS配环境,Windows不会配环境,就装Linux,现在装上了Linux,却因为没有经验把Windows格式化了(我是真的沙比),好在还是开始做了,也挺顺利的,所以再来记录一下作业。

这里是作业框架的下载作业框架下载

导航

导航

基础部分

这里需要完成两个函数,一个是模型变换矩阵,一个是透视投影矩阵。

模型变换矩阵

逐个元素地构建模型变换矩阵并返回该矩阵。在此函数中,你只需要实现三维中绕 z 轴旋转的变换矩阵,而不用处理平移与缩放。
这个部分的实现非常简单,只需要记住这个公式就好了。这里给出绕三个轴旋转的旋转矩阵:

image
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Eigen::Matrix4f get_model_matrix(float rotation_angle)
{
Eigen::Matrix4f model = Eigen::Matrix4f::Identity();
//角度制转弧度制
rotation_angle = rotation_angle / 180.0f * MY_PI;
// TODO: Implement this function
// Create the model matrix for rotating the triangle around the Z axis.
// Then return it.
model << cos(rotation_angle), -sin(rotation_angle), 0, 0,
sin(rotation_angle), cos(rotation_angle), 0, 0,
0, 0, 1, 0,
0, 0, 0, 1;
return model;
}

透视投影矩阵

使用给定的参数逐个元素地构建透视投影矩阵并返回
该矩阵。

这个题目的参数定义其实不是很明显(至少位蒙b了很久),先看一下函数原型:

1
Eigen::Matrix4f get_projection_matrix(float eye_fov, float aspect_ratio, float zNear, float zFar)

来解读一下前两个参数,eye_fov指的是摄像机的垂直可视角度,aspect_ratio指的是摄像机的长宽比。使用这四个值也能算出正交投影矩阵。(下图只供参考)
image

我们从透视投影矩阵开始:
根据课堂上的推导,我们已经知道透视投影矩阵的最终结果,并且所需要的值只有zNearzFar,于是我们能直接写出这个矩阵:

1
2
3
4
P << zNear, 0, 0, 0,
0, zNear, 0, 0,
0, 0, zNear + zFar, -zNear * zFar,
0, 0, 1, 0;

然后是我们的正交投影部分了,正交投影需要用到的数据有六个,分别是长方体的参数。
$$[l,r]\times[b,t]\times[f,n]$$
先把正的数据处理掉,直接给出答案,再证明

  • \(t=zNear*tan(eye\_fov/2)\)(弧度化后)
  • \(r=t*aspect\_ratio\)
    另外的lb分别等于rt的相反数。
    证明如下:(仅供参考)
    image

最后还剩下nf,这两个数和他们的名字差别很大,分别是后和前,赋值的时候需要小心,而且他们的值并不是zNear和zFar分别赋值,而是相反数赋值。如下

1
2
f = -zNear;
n = -zFar;

有了数据,我们就可进行投影矩阵的实现了,正交投影矩阵如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      eye_fov = eye_fov / 180 * MY_PI;
float l, r, b, t, n, f;
//注意这里的f和n代表的意义
f = -zNear;
n = -zFar;
t = -zNear * tan(eye_fov/2);
b = -t;
r = t * aspect_ratio;
l = -r;
S << 2 / (r - l), 0, 0, 0,
0, 2 / (t - b), 0, 0,
0, 0, 2 / (n - f), 0,
0, 0, 0, 1;
M << 1, 0, 0, -(r + l) / 2,
0, 1, 0, -(t + b) / 2,
0, 0, 1, -(n + f) / 2,
0, 0, 0, 1;
//S*M得到正交投影矩阵

普通要求代码汇总

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//main.cpp
bool ProjectMode=true;//这是一个控制模式的参数
Eigen::Matrix4f get_model_matrix(float rotation_angle)
{
Eigen::Matrix4f model = Eigen::Matrix4f::Identity();
rotation_angle = rotation_angle / 180.0f * MY_PI;
// TODO: Implement this function
// Create the model matrix for rotating the triangle around the Z axis.
// Then return it.
model << cos(rotation_angle), -sin(rotation_angle), 0, 0,
sin(rotation_angle), cos(rotation_angle), 0, 0,
0, 0, 1, 0,
0, 0, 0, 1;
return model;
}
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.
if (!ProjectMode)
{
Eigen::Matrix4f S, M, P;
eye_fov = eye_fov / 180 * MY_PI;
float l, r, b, t, n, f;
//注意这里的f和n代表的意义
f = -zNear;
n = -zFar;
t = -zNear * tan(eye_fov/2);
b = -t;
r = t * aspect_ratio;
l = -r;
S << 2 / (r - l), 0, 0, 0,
0, 2 / (t - b), 0, 0,
0, 0, 2 / (n - f), 0,
0, 0, 0, 1;
M << 1, 0, 0, -(r + l) / 2,
0, 1, 0, -(t + b) / 2,
0, 0, 1, -(n + f) / 2,
0, 0, 0, 1;
P << zNear, 0, 0, 0,
0, zNear, 0, 0,
0, 0, zNear + zFar, -zNear * zFar,
0, 0, 1, 0;
return S * M * P;
}
else//这是精简版本
{
eye_fov = eye_fov / 180 * MY_PI;
projection << 1 / (aspect_ratio * tan(eye_fov / 2.0f)), 0, 0, 0,
0, 1 / tan(eye_fov / 2.0f), 0, 0,
0, 0, -(zFar + zNear) / (zFar - zNear), 2 * zFar * zNear / (zNear - zFar),
0, 0, -1, 0;
return projection;
}
}

提升部分

提升部分要求:在 main.cpp 中构造一个函数,该函数的作用是得到绕任意
过原点的轴的旋转变换矩阵。根据101中的推导,我们需要计算的东西并不多,按要求写好就行了。我选择重载get_model_matrix函数,来实现任意旋转轴的旋转操作。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Eigen::Matrix4f get_rotation(Vector3f axis, float rotation_angle)
{
rotation_angle = rotation_angle / 180.0f * MY_PI;
Eigen::Matrix4f Result = Eigen::Matrix4f::Identity();
Eigen::Matrix3f I = Eigen::Matrix3f::Identity();//单位矩阵
Eigen::Matrix3f N = Eigen::Matrix3f::Identity();
Eigen::Matrix3f ResultMat3 = Eigen::Matrix3f::Identity();
N << 0, -axis[2], axis[1],
axis[2], 0, -axis[0],
-axis[1], axis[0], 0;
ResultMat3 = I * cos(rotation_angle) + (1 - cos(rotation_angle)) * axis * axis.transpose() + sin(rotation_angle) * N;
Result << ResultMat3(0, 0), ResultMat3(0, 1), ResultMat3(0, 2), 0,
ResultMat3(1, 0), ResultMat3(1, 1), ResultMat3(1, 2), 0,
ResultMat3(2, 0), ResultMat3(2, 1), ResultMat3(2, 2), 0,
0, 0, 0, 1;

return Result;
}

其余代码和普通要求一致。得到结果如下:

结果

因为是第一次作业,所以我这里给出编译的操作:
先来到作业目录
image
创建build文件夹
image
来到build文件夹
image
使用上级目录创建项目文件
image
构建编译,这里的-j8是表示调用的核心数量,最后一句target Rasterizer表示可执行文件为Rasterizer
image
运行
image
image
按下Esc或者Ctrl+C停止
image
全部指令汇总

1
2
3
4
5
mkdir build
cd build
cmake ..
make -j8
./Rasterizer

普通要求

运行指令与结果

./Rasterizer 不带参数运行

image

./Rasterizer -r 0 output.png无旋转保存图片

image
image

./Rasterizer -r 90 output90.png旋转保存图片

image

提升要求

先介绍一下main函数的两个参数argcargv

  • argc全称arugment count,表示调用程序的时候,传入的参数的个数。
  • argv全称argument vector,表示调用程序的时候,传入的参数向量,类型为字符串
    默认的,argv[0]是调用程序的完整路径,然后argv[0]-argv[argc-1]都是可以访问的字符串。在程序中,我们可以使用标准库定义的stof函数,把字符串转成浮点型,或者使用stod把字符串转化成整形。知道这一点之后,我们就可以设计一个main函数来把我们自定义的旋转轴作为参数传入程序了。

这里是我自己设计的一个传参方案,有兴趣的可以读一下程序。

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include "Triangle.hpp"
#include "rasterizer.hpp"
#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <opencv2/opencv.hpp>

constexpr double MY_PI = 3.1415926;
bool ProjectMode=true;

Eigen::Matrix4f get_view_matrix(Eigen::Vector3f eye_pos)
{
Eigen::Matrix4f view = Eigen::Matrix4f::Identity();

Eigen::Matrix4f translate;
translate << 1, 0, 0, -eye_pos[0], 0, 1, 0, -eye_pos[1], 0, 0, 1,
-eye_pos[2], 0, 0, 0, 1;

view = translate * view;

return view;
}

Eigen::Matrix4f get_model_matrix(float rotation_angle)
{
Eigen::Matrix4f model = Eigen::Matrix4f::Identity();
rotation_angle = rotation_angle / 180.0f * MY_PI;
// TODO: Implement this function
// Create the model matrix for rotating the triangle around the Z axis.
// Then return it.
model << cos(rotation_angle), -sin(rotation_angle), 0, 0,
sin(rotation_angle), cos(rotation_angle), 0, 0,
0, 0, 1, 0,
0, 0, 0, 1;
return model;
}

// Rodrigues rotation formula
Eigen::Matrix4f get_rotation(Vector3f axis, float angle)
{
angle = angle / 180.0f * MY_PI;
Eigen::Matrix4f Result = Eigen::Matrix4f::Identity();
Eigen::Matrix3f E = Eigen::Matrix3f::Identity();
Eigen::Matrix3f N = Eigen::Matrix3f::Identity();
Eigen::Matrix3f ResultMat3 = Eigen::Matrix3f::Identity();
N << 0, -axis[2], axis[1],
axis[2], 0, -axis[0],
-axis[1], axis[0], 0;
ResultMat3 = E * cos(angle) + (1 - cos(angle)) * axis * axis.transpose() + sin(angle) * N;
Result << ResultMat3(0, 0), ResultMat3(0, 1), ResultMat3(0, 2), 0,
ResultMat3(1, 0), ResultMat3(1, 1), ResultMat3(1, 2), 0,
ResultMat3(2, 0), ResultMat3(2, 1), ResultMat3(2, 2), 0,
0, 0, 0, 1;

return Result;
}


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.
if (!ProjectMode)
{
std::cout<<"Protable answer"<<std::endl;
Eigen::Matrix4f S, M, P;
eye_fov = eye_fov / 180 * MY_PI;
float l, r, b, t, n, f;
//注意这里的f和n代表的意义
f = -zNear;
n = -zFar;
t = -zNear * tan(eye_fov/2);
b = -t;
r = t * aspect_ratio;
l = -r;
S << 2 / (r - l), 0, 0, 0,
0, 2 / (t - b), 0, 0,
0, 0, 2 / (n - f), 0,
0, 0, 0, 1;
M << 1, 0, 0, -(r + l) / 2,
0, 1, 0, -(t + b) / 2,
0, 0, 1, -(n + f) / 2,
0, 0, 0, 1;
P << zNear, 0, 0, 0,
0, zNear, 0, 0,
0, 0, zNear + zFar, -zNear * zFar,
0, 0, 1, 0;
return S * M * P;
}
else
{
std::cout<<"true answer"<<std::endl;
eye_fov = eye_fov / 180 * MY_PI;
projection << 1 / (aspect_ratio * tan(eye_fov / 2.0f)), 0, 0, 0,
0, 1 / tan(eye_fov / 2.0f), 0, 0,
0, 0, -(zFar + zNear) / (zFar - zNear), 2 * zFar * zNear / (zNear - zFar),
0, 0, -1, 0;
return projection;
}
}
int main(int argc, const char **argv)
{
float angle = 0;
bool command_line = false;
Eigen::Vector3f axis = Eigen::Vector3f(0.f, 1.f, 0.f);
std::string filename = "output.png";
if(argc>=2){
std::cout<<argv[1]<<std::endl;
if(argv[1][1]=='m')//使用精简版本
ProjectMode=true;
else if(argv[1][1]=='p')//使用便阅读版本
ProjectMode=false;
std::cout<<ProjectMode<<std::endl;
}

if (argc >= 3)
{
std::cout<<argc<<std::endl;

angle = std::stof(argv[2]); // -r by default
if (argc == 4)
{
command_line = true;
filename = std::string(argv[3]);
}
else if(argc==6){//DIY(
axis.x()=std::stof(argv[3]);
axis.y()=std::stof(argv[4]);
axis.z()=std::stof(argv[5]);
axis.normalize();
}
//
}

rst::rasterizer r(700, 700);

Eigen::Vector3f eye_pos = {0, 0, 5};

std::vector<Eigen::Vector3f> pos{{2, 0, -2}, {0, 2, -2}, {-2, 0, -2}};

std::vector<Eigen::Vector3i> ind{{0, 1, 2}};

auto pos_id = r.load_positions(pos);
auto ind_id = r.load_indices(ind);

int key = 0;
int frame_count = 0;

if (command_line)
{
r.clear(rst::Buffers::Color | rst::Buffers::Depth);

r.set_model(get_model_matrix(angle));
r.set_view(get_view_matrix(eye_pos));
r.set_projection(get_projection_matrix(45, 1, 0.1, 50));

r.draw(pos_id, ind_id, rst::Primitive::Triangle);
cv::Mat image(700, 700, CV_32FC3, r.frame_buffer().data());
image.convertTo(image, CV_8UC3, 1.0f);

cv::imwrite(filename, image);

return 0;
}


while (key != 27)
{
r.clear(rst::Buffers::Color | rst::Buffers::Depth);


r.set_model(get_model_matrix(angle));
//DIY
if (argc == 6){
r.set_model(get_rotation(axis, angle));
std::cout<<"axis x:"<<axis.x()<<" y:"<<axis.y()<<" z:"<<axis.z()<<std::endl<<"angle:"<<angle<<std::endl;
}
//
r.set_view(get_view_matrix(eye_pos));
r.set_projection(get_projection_matrix(45, 1, 0.1, 50));

r.draw(pos_id, ind_id, rst::Primitive::Triangle);

cv::Mat image(700, 700, CV_32FC3, r.frame_buffer().data());
image.convertTo(image, CV_8UC3, 1.0f);
cv::imshow("image", image);
key = cv::waitKey(10);

std::cout << "frame count: " << frame_count++ << '\n';

if (key == 'a')
{
angle += 10;
}
else if (key == 'd')
{
angle -= 10;
}
}

return 0;
}


部分效果如下:
image
可执行操作如下

  • ./Rasterizer -p 使用便阅读版本矩阵进行计算
  • ./Rasterizer -m使用简便版本矩阵进行计算
    image
    image

games101 Hw1 到此就结束啦!

下一篇:图形填充


2023.8.17

写完之后,感觉少了点什么,于是便有了下面的东西。

框架解读

作业一的文件如下

  • main.cpp
  • rasterizer.cpp
  • rasterizer.hpp
  • Triangle.cpp
  • Triangle.hpp

读框架代码要从接口开始,也就是头文件,我们先注意一下各个头文件的引用情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
---------------------------------------------
//main
#include "Triangle.hpp"
#include "rasterizer.hpp"
#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <opencv2/opencv.hpp>
---------------------------------------------

//raserizer.hpp
#include "Triangle.hpp"
#include <algorithm>
#include <eigen3/Eigen/Eigen>
using namespace Eigen;
---------------------------------------------

//Triangle.hpp
#include <eigen3/Eigen/Eigen>
using namespace Eigen;
---------------------------------------------

可以看到,Triangle.hpp是一个独立的类,只需要依赖数学库Eigen,我们从这个三角形类开始。

Triangle

数据成员

这里用到的三角形类存储了一个三角形的顶点部分信息,以达到绘制一个线框所需要的数据结构。具体有这些:

  • Vector3f v[3]; 顶点坐标
  • Vector3f color[3]; 顶点颜色
  • Vector2f tex_coords[3]; 纹理坐标
  • Vector3f normal[3]; 法线方向
    其中只有顶点坐标在作业一中用到了。

接口函数

1
2
3
4
5
6
7
8
9
10
11
12
//访问顶点坐标
Eigen::Vector3f a() const { return v[0]; }
Eigen::Vector3f b() const { return v[1]; }
Eigen::Vector3f c() const { return v[2]; }
//设置顶点坐标、法线、颜色、纹理坐标
void setVertex(int ind, Vector3f ver); /*set i-th vertex coordinates */
void setNormal(int ind, Vector3f n); /*set i-th vertex normal vector*/
void setColor(int ind, float r, float g, float b); /*set i-th vertex color*/
void setTexCoord(int ind, float s,
float t); /*set i-th vertex texture coordinate*/
//到Vec4的转化,方便进行矩阵计算
std::array<Vector4f, 3> toVector4() const;

函数实现

只有一个函数是值的讲解的toVector4:这个函数把三角形顶点坐标转化为齐次坐标后返回。

std::transform是一个通用算法,用于对输入范围中的元素执行给定的操作,并将结果存储在输出范围中。在这个例子中,我们使用std::transform(std::begin(v), std::end(v), res.begin(), [](auto& vec) { ... })来将v数组中的每个Vector4f对象转换为res数组中的对应对象。[](auto& vec) { ... }是一个lambda表达式,用于定义转换操作。

1
2
3
4
5
6
7
8
std::array<Vector4f, 3> Triangle::toVector4() const
{
std::array<Vector4f, 3> res;
std::transform(std::begin(v), std::end(v), res.begin(), [](auto& vec) {
return Vector4f(vec.x(), vec.y(), vec.z(), 1.f);
});
return res;
}

rasterizer

这个类就很有意思了,从类的数据成员开始看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class rasterizer
{
private:
//三个投影矩阵
Eigen::Matrix4f model;
Eigen::Matrix4f view;
Eigen::Matrix4f projection;

//顶点缓存
std::map<int, std::vector<Eigen::Vector3f>> pos_buf;
std::map<int, std::vector<Eigen::Vector3i>> ind_buf;

//颜色缓存
std::vector<Eigen::Vector3f> frame_buf;
//深度缓存 暂未使用
std::vector<float> depth_buf;

//显示区域参数
int width, height;
//工具
int next_id = 0;
};

frame_buf存储的是最后的颜色结果,虽然直译是指框架缓存。(英语不好,勿喷)
有了这些数据成员,就开开始写数据的构造和赋值了。构造只有对显示区域参数的初始化:

构造

1
2
3
4
5
6
//raterizer.cpp
rst::rasterizer::rasterizer(int w, int h) : width(w), height(h)
{
frame_buf.resize(w * h);
depth_buf.resize(w * h);
}

赋值

需要外部输入的数据成员还有

  • model
  • view
  • projection
  • pos_buf
  • ind_buf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}
//导入顶点坐标和顶点索引
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};
}

上面三个MVP函数是非常简单的,没什么好讲的,但是导入顶点坐标和索引的函数,可得好好讲讲。
首先是为什么这个两个函数返回值分别是rst::pos_buf_idrst::ind_buf_id ,在原代码框架里给了这么一段解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
For the curious : The draw function takes two buffer id's as its arguments.
These two structs make sure that if you mix up with their orders, the
compiler won't compile it. Aka : Type safety
*/
/*
对于感兴趣的人 : draw 函数接受两个缓冲区ID作为参数。
这些两个结构体确保如果将它们顺序混乱,编译器不会编译它。
又名 : 类型安全
*/
struct pos_buf_id{
int pos_id = 0;
};
struct ind_buf_id{
int ind_id = 0;
};

在我们的draw函数里面,直接对id进行了下标访问,因为我们不希望再去浪费查找的时间,这样一个设计可以让程序高效而安全。这就像是给一个整形变量贴上了标签一样。两个不同的返回值类型的存在,使得我们可以存在相同的id在pos_bufind_buf中,而不会产生问题。

而至于为什么要返回这么一个值呢?

这是因为我们在使用rasterizer类的时候,需要获得导入数据的控制buf_id,才能对导入的数据进行访问。

输出

数据成员的初始化和赋值都已经解决了,接下来就是如何准确的进行光栅化的问题了。光栅化要做的事情就两件,一、把颜色缓存填充好;二、深度缓存填充好。

一、颜色缓存

首先实现一个填充颜色的小函数rst::rasterizer::set_pixel(const Eigen::Vector3f& point, const Eigen::Vector3f& color)
作为rst::rasterizer 类的成员函数,他需要设置指定点的颜色,但是注意frame_buf是一个数组,数组意味着越界的风险,所以需要在设置之前判断下标的位置。

1
2
3
4
if (point.x() < 0 || point.x() >= width ||
point.y() < 0 || point.y() >= height) return;
auto ind = (height-point.y())*width + point.x();
frame_buf[ind] = color;
二、深度缓存

这个作业没有涉及到深度缓存,因为绘制的是一个平面的三角形,所以深度缓存留到下一次作业讲解。

计算机图形学笔记三——橡皮筋技术和椭圆扫描算法

上一篇:圆形、圆弧段的绘制算法
下一篇:暂无

橡皮筋技术

橡皮筋技术就是可以使得用户进行可视化编辑,也就是在编辑的时候,图像能够进行实时的变化。这是一种非常实用的技术,接下来和大家讲解一下这个技术。
我们有鼠标点击回调函数,还有鼠标移动回调函数。我们需要的是在鼠标点击过后,移动鼠标能够预览我们绘制的图像。比如这是有无橡皮筋技术的对比:

有橡皮筋技术

image
image
随着鼠标的移动,我们的最后一个顶点会跟着移动,可以达到很好的编辑效果。

没有橡皮筋技术

image
image
每次都会确定一个顶点位置,不能进行实时的更改。
橡皮筋技术的实现需要的两个函数和一个枚举:

1
2
3
4
5
6
7
8
//鼠标点击回调函数
glutMouseFunc(onMouse);
//鼠标移动回调函数
glutPassiveMotionFunc(onMouseMove);
typedef enum {
MOVE,
NONE
}MOUSEMODE;

鼠标点击回调函数

处理点击事件时,我们设置第一次点击创建两个顶点。想象一下,点击一次后,我们移动会带动第二个点移动,也就是说我们第一次点击需要创建两个顶点。在后面的点击只需要创建一个。并且把MouseMode更新为MOVE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*这里是onMouse(GLint button, GLint state, GLint x, GLint y)*/

//如果点击状态是按下
if (state == GLUT_DOWN) {
//如果是鼠标左键
if (button == GLUT_LEFT_BUTTON) {
//如果是第一个点,多创建一个顶点
if (!Vertex.size())
Vertex.push_back(make_pair(x, y));
Vertex.push_back(make_pair(x, y));
//设置控制点的位置
ctrlPoint = Vertex.size();
//修改控制模式
MouseMode = MOVE;
}
}

鼠标移动回调函数

在创建顶点过后,我们在鼠标移动回调函数中对最后一格顶点进行位置的更改,我们也可以叫最后一个顶点为临时顶点。

1
2
3
4
5
6
7
8
/*这里是onMouseMove(GLint xMouse, GLint yMouse)*/

//如果控制装填是移动
if (MouseMode == MOVE) {
Vertex[ctrlPoint - 1].first = xMouse, Vertex[ctrlPoint - 1].second = yMouse;
//发送重绘信息
glutPostRedisplay();
}

额外的——使用右键进行顶点的消除和暂停绘制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*这里是onMouse(GLint button, GLint state, GLint x, GLint y)*/

//如果按下的是右键
else if (button == GLUT_RIGHT_BUTTON) {
//如果正在进行橡皮筋操作
if (MouseMode == MOVE) {
//停止橡皮筋操作(停止实时绘画)
MouseMode = NONE;
return;
}
//否则为删除模式,判断顶点位置
auto ibeg = Vertex.begin();
while (ibeg != Vertex.end()) {
//模糊搜索,先绘制的顶点先删除(距离都满足条件的话)
if (((x - ibeg->first) * (x - ibeg->first)) + ((y - ibeg->second) * (y - ibeg->second)) < 400) {
//找到了,删除该顶点
Vertex.erase(ibeg);
break;
}
ibeg++;
}
}

这里是可以用于前面圆和圆弧绘制的测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*
你可以使用左键绘制顶点
你可以使用右键删除顶点
直线的绘制沿着顶点顺序
*/
#include <gl/glut.h>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include "DrawLine.hpp"
#include "DrawRound.hpp"

using namespace std;

#define m_POINT_SIZE 10
#define m_LINE_SIZE 2
typedef enum {
MOVE,
NONE
}MOUSEMODE;

vector<pair<GLint, GLint >>Vertex;
MOUSEMODE MouseMode = NONE;
GLint ctrlPoint = 0;

void onDisplay();
void onReshape(GLint w, GLint h);
void onMouse(GLint button, GLint state, GLint x, GLint y);
void onMouseMove(GLint xMouse, GLint yMouse);

void onReshape(GLint w, GLint h)
{
// 设置视口大小
glViewport(0, 0, w, h);
// 切换矩阵模式为投影矩阵
glMatrixMode(GL_PROJECTION);
// 载入单位矩阵
glLoadIdentity();
// 进行二维平行投影
gluOrtho2D(0, w, h, 0);
// 切换矩阵模式为模型矩阵
glMatrixMode(GL_MODELVIEW);
// 发送重绘
glutPostRedisplay();
}
void onMouse(GLint button, GLint state, GLint x, GLint y){
if (state == GLUT_DOWN) {
if (button == GLUT_LEFT_BUTTON) {
if(!Vertex.size())
Vertex.push_back(make_pair(x, y));
Vertex.push_back(make_pair(x, y));
ctrlPoint = Vertex.size();
MouseMode = MOVE;
}
else if (button == GLUT_RIGHT_BUTTON) {
if (MouseMode == MOVE) {
MouseMode = NONE;
return;
}
auto ibeg = Vertex.begin();
while (ibeg != Vertex.end()) {
if (((x - ibeg->first) * (x - ibeg->first)) + ((y - ibeg->second) * (y - ibeg->second)) < 400) {
Vertex.erase(ibeg);
break;
}
ibeg++;
}
}
}
glutPostRedisplay();
}
void onMouseMove(GLint xMouse, GLint yMouse) {
if (MouseMode == MOVE) {
Vertex[ctrlPoint-1].first = xMouse, Vertex[ctrlPoint-1].second = yMouse;
glutPostRedisplay();
}
}
void onDisplay() {
glClearColor(224 / 255.0, 237 / 255.0, 253 / 255.0,1.0);
glClear(GL_COLOR_BUFFER_BIT);

glColor3f(1.0f, 0, 0);
auto ibeg = Vertex.begin(),jbeg=ibeg;
GLint VertexNum = Vertex.size();
while (ibeg != Vertex.end()) {
glPointSize(m_POINT_SIZE);
glBegin(GL_POINTS);
glVertex2i(ibeg->first, ibeg->second);
glEnd();
glPointSize(m_LINE_SIZE);
if(VertexNum>=2) {
//这里可以选择直线绘制方式
BRESENHAM_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);
//TMP_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);
//DDA_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);

//这里是绘制圆形
//Mid_Circle( jbeg->first, jbeg->second,ibeg->first, ibeg->second);
//BRESENHAM_Circle(jbeg->first, jbeg->second, ibeg->first, ibeg->second);

}
jbeg = ibeg;
ibeg++;
}
//这里是绘制圆弧(只绘制前三个点,可以自己DIY)
if (VertexNum >= 3) {
cout << "Draw CircleArc" << endl;
DrawCircleArc(Vertex[0].first, Vertex[0].second, Vertex[1].first, Vertex[1].second, Vertex[2].first, Vertex[2].second);
}

glutSwapBuffers();
cout << "Once" << endl;
}

GLint main(GLint argc, char* argv[])
{

// 初始化 glut
glutInit(&argc, argv);
// 设置 OpenGL 显示模式(双缓存, RGB 颜色模式)
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
// 设置窗口初始尺寸
glutInitWindowSize(1000,800);
// 设置窗口初始位置
glutInitWindowPosition(0, 0);
// 设置窗口标题
glutCreateWindow("Terix");
glutReshapeFunc(onReshape);
glutDisplayFunc(onDisplay);
glutMouseFunc(onMouse);
glutPassiveMotionFunc(onMouseMove);
// 设置菜单
// 进入 glut 事件循环
glutMainLoop();
return 0;
}

椭圆扫描算法

然后我们来介绍一下最后一个绘制圆锥曲线的算法(我的专栏里)——椭圆的绘制.
由于椭圆的对称性较圆稍差,它的对称性只有4份,也就是四个卦象内对称,也就是说我们得绘制出第一卦象一整个卦象的图像。当斜率绝对值小于1的时候使用x作为步长,反之为y轴。接下来来推导一下迭代方程和斜率的判别式:
设一个椭圆方程为

\[b^2 x^2+a^2 y^2-a^2b^2=0 \]

x轴

假设当前最佳迭代点为 \((x_i+1, y_i)\),那么对于下一个迭代点的两种情况:

\[d_i=F(x_i+2,y_i-0.5)=b^2(x_i+1)^2+a^2(y_i-0.5)^2-a^2b^2 \]

d<0

\[d_i=F(x_i+2,y_i-0.5)=d+b^2(2x_i+3) \]

d>=0

\[d_i=F(x_i+2,y_i-1.5)=d+b^2(2x_i+3)+a^2(-2y_i+2) \]

迭代终点为斜率的绝对值大于1

斜率判别式

\[|k|=\frac{a^2(y_i-0.5)}{b^2(x_i+1)} \]

转化为:

\[b^2(x_i+1)<a^2(y_i-0.5) \]

y轴

同样的我们可以得到:
d<0

\[d_i=F(x_i+1.5,y_i-2)=d+b^2(2x_i+2)+a^2(-2y_i+3) \]

d>0

\[d_i=F(x_i+0.5,y_i-2)=d+a^2(-2y_i+3) \]

迭代终点为y==0

因为单纯使用函数已经无法很好的维护数据了,所以从椭圆开始我会将所有的算法和所需要的数据结构封装成类。

Ellipt类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Ellipt {
public:
Ellipt(GLint P1x=0,GLint P1y=0,GLint P2x=0,GLint P2y=0)
{
m_a = abs(static_cast<GLint>(P1x - P2x)/2);
m_b= abs(static_cast<GLint>(P1y - P2y)/2);
//四舍五入
m_R.x = static_cast<GLint>(((P1x + P2x) / 2.0 + 0.5));
m_R.y = static_cast<GLint>(((P1y + P2y) / 2.0 + 0.5));
}
void setData(GLint P1x, GLint P1y, GLint P2x, GLint P2y) {
m_a = abs(static_cast<GLint>(P1x - P2x)/2);
m_b = abs(static_cast<GLint>(P1y - P2y)/2);
//四舍五入
m_R.x = static_cast<GLint>(((P1x + P2x) / 2.0 + 0.5));
m_R.y = static_cast<GLint>(((P1y + P2y) / 2.0 + 0.5));
}
void Draw(){
MidPt_Elliptse(m_R, m_a, m_b);
}
private:
myPoint m_R;
GLint m_a,m_b;
void MidPt_Elliptse(myPoint cPt, GLint a, GLint b) {
glBegin(GL_POINTS);
GLint x, y, temp = a * 7 / 10, dir[4][2] = {
{ 1, 1 }, { 1,-1 },
{ -1,1}, {-1,-1 }
};
double d;
x = 0, y = b;
d = b * b + a * a * (-b + 0.25);
for (int i = 0; i < 4; i++) {
glVertex2i(cPt.x + x * dir[i][0], cPt.y + y * dir[i][1]);
}
while ((b * b * (x + 1)<a * a * (y + 0.5))) {
if (d > 0)
{
x += 1;
y -= 1;
d += b * b * (2 * x + 3) + a * a * (-2 * y + 2);
}
else {
x += 1;
d += b * b * (2 * x + 3);
}
for (int i = 0; i < 4; i++) {
glVertex2i(cPt.x + x * dir[i][0], cPt.y + y * dir[i][1]);
}
}
while (y > 0) {
if (d >= 0) {
y -= 1;
d += a * a * (-2 * y + 3);
}
else {
x += 1;
y -= 1;
d += a * a * (-2 * y + 3) + b * b * (2 * x + 2);
}
for (int i = 0; i < 4; i++) {
glVertex2i(cPt.x + x * dir[i][0], cPt.y + y * dir[i][1]);
}
}
glFlush();
glEnd();
}
};
``` 其中用到的myPoint类

```cpp
class myPoint;

//A point or a vector in R^2
class myPoint {
public:
myPoint(GLint X=0,GLint Y=0 ):x(X),y(Y){}
GLint x, y;
};
myPoint operator+(const myPoint& a, const myPoint& b) {
return myPoint(a.x + b.x, a.y + b.y);
}
myPoint operator-(const myPoint& a, const myPoint& b) {
return myPoint(a.x - b.x, a.y - b.y);
}
GLint operator*(const myPoint& a, const myPoint& b) {
return a.x * b.x + a.y * b.y;
}

代码汇总

你可以在这里找到目前为止所有的源代码
阿里云盘-代码汇总
gitee-代码汇总

下/上一篇

上一篇:圆形、圆弧段的绘制算法
下一篇:暂无

计算机图形学笔记一——绘制直线的算法

绘制直线的算法

下一篇->圆形的绘制

数值微分法

数值微分法(digital differential analyzer DDA)使用直线的增量方程来计算直线的下一个迭代点像素的方法。直线的微分方程:
$$
\frac{dy}{dx}=\frac{\Delta y}{\Delta x}=\frac{y_1-y_0}{x_1-x_0}=k
$$
得到迭代公式:
$$
x_{i+1}=x_i+\beta \Delta x
$$
$$
y_{i+1}=y_i +\beta \Delta y
$$
其中$\beta=\frac{1}{max(|\Delta x|,|\Delta y|)}$
也就是说,当斜率的绝对值大于1的时候,取y的步长为1,当斜率的绝对值小于1时,取x的步长为1。然后对非步长点进行近似,得到这样的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
double x, y;
double k; //斜率
k = (static_cast<float>(endy - starty) / static_cast<float>(endx - startx));
x = (double)startx, y = (double)starty;
if (abs(k) < 1.0) {
for (int i = 0; i < abs(endx - startx); i++) {
if (endx > startx) {
x += 1;
y += k;
}
else {
x -= 1;
y -= k;
}
glVertex2d(static_cast<int>(x), static_cast<int>(y + 0.5)); //y四舍五入
}
}
else if (abs(k) > 1.0) {
for (int i = 0; i < abs(endy - starty); i++) {
if (endy > starty) {
y += 1;
x += 1.0 / k;
}
else {
y -= 1;
x -= 1.0 / k;
}
glVertex2d(static_cast<int>(x + 0.5), static_cast<int>(y)); //x四舍五入
}
}

再考虑斜率为0和斜率不存在的情况(垂直x轴和平行x轴),我们可以写出这样的代码,这便是DAA方法的实现。

DAA完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
void DDA_Line(int startx, int starty, int endx, int endy) {
glBegin(GL_POINTS);
if (startx != endx && starty != endy)
{
double x, y;
double k; //斜率
k = (static_cast<float>(endy - starty) /static_cast<float>(endx - startx));
x = (double)startx, y = (double)starty;
if (abs(k)<1.0) {
for (int i = 0; i < abs(endx - startx); i++) {
if (endx > startx) {
x += 1;
y += k;
}
else {
x -= 1;
y -= k;
}
glVertex2d(static_cast<int>(x), static_cast<int>(y+0.5)); //y四舍五入
}
}
else if (abs(k) > 1.0) {
for (int i = 0; i < abs(endy - starty); i++) {
if (endy > starty) {
y += 1;
x += 1.0/k;
}
else {
y -= 1;
x -= 1.0/k;
}
glVertex2d(static_cast<int>(x + 0.5), static_cast<int>(y)); //x四舍五入
}
}
}
else if (startx == endx) {//垂直画线
if (starty < endy) {
for (int i = starty; i < endy; i++) {
glVertex2d(startx, i);
}
}
else if (starty > endy) {
for (int i = endy; i < starty; i++) {
glVertex2d(startx, i);
}
}
}
else if (starty == endy) {//水平画线
if (startx < endx) {
for (int i = startx; i < endx; i++) {
glVertex2d(i, starty);
}
}
else if (startx > endx) {
for (int i = endx; i < startx; i++) {
glVertex2d(i, starty);
}
}
}
glFlush();
glEnd();
}

中点画线算法

不进行除法运算,减少计算量,使用一种近似的思想进行取样。下面两幅图中说明了这种算法的实施方法:
image
当曲线在一格的中间偏上时,使用上面的点作为采样点,当在中间偏下时,使用下面的一格。如此计算,便能绕靠斜率的除法运算。
实际实现方法:从左边的点开始,每次往右移动一格,计算这个点的中点处y与函数值的差,如果大于零,则y不变;反之y向上(下)移动一格。
那么有两个要求:
一、计算y移动的方向是上还是下
二、开始的点必须在左边

分析一下这个差值的计算:
$$
F(x,y)=ax+by+c=0

a=y_0-y_1

b=x_1-x_0

c=x_0y_1-x_1y_0

d=F(x_i+1,y_i+0.5)
$$
其中d也就是中点和直线的竖直距离,我们可以通过判断d的正负来进行采样。进一步分析
当d>=0时,下一个构造点为F$x_i+2,y_i$,那么

$$
d_1=a(x_i+1+1)+b(y_i+0.5)+c=d+a
$$
同理,当$d<0$时d$_1=F(x_i+2,y_i+1.5)$,即:

$d=a(x_i+2)+b(y_i+1.5)+c=d+a+b$

这样我们就得到了迭代方程,我们可以写出这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
if (startx != endx && starty != endy)
{
bool kFlag = 0; //斜率是否大于1
int sFlag = 1; //斜率的正负
if (startx > endx) { //因为算法是x递增的,所以要保持起点x在终点左边
int tempx = startx, tempy = starty;
startx = endx, starty = endy;
endx = tempx, endy = tempy;
}
if (abs(starty - endy) > abs(startx - endx)) {
kFlag = true;
}
if (starty > endy) { //标记斜率小于零
sFlag = -1;
}
int a, b, TA, TAB, d, x, y;
if (sFlag == -1)
endy = starty + (starty - endy);

a = starty - endy;
b = endx - startx;
TA = 2 * a; //twoA
TAB = 2 * (a + b); //twoAB
d = 2 * a + b;
x = startx, y = starty;
if (!kFlag) {
for (int i = 0; i < (endx - startx); i++) {
if (d >= 0) {
glVertex2i(++x, y);
d += TA;
}
else {
glVertex2i(++x, y += sFlag);
d += TAB;
}
}
}
else if (kFlag) {
if (kFlag == 1) {
TA = 2 * b;
d = 2 * b + a;
}
for (int i = 0; i < abs(endy - starty); i++) {
if (d >= 0) {
glVertex2i(++x, y += sFlag);
d += TAB;
}
else {
glVertex2i(x, y += sFlag);
d += TA;
}
}
}
}

你可以在这里找到所有代码

TMP算法完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
void TMP_Line(int startx, int starty, int endx, int endy) {
glBegin(GL_POINTS);
if (startx != endx && starty != endy)
{
bool kFlag = 0; //斜率是否大于1
int sFlag = 1; //斜率的正负
if (startx > endx) { //因为算法是x递增的,所以要保持起点x在终点左边
int tempx = startx, tempy = starty;
startx = endx, starty = endy;
endx = tempx, endy = tempy;
}
if (abs(starty - endy) > abs(startx - endx)) {
kFlag = true;
}
if (starty > endy) { //标记斜率小于零
sFlag = -1;
}
int a, b, TA, TAB, d, x, y;
if (sFlag == -1)
endy = starty + (starty - endy);

a = starty - endy;
b = endx - startx;
TA = 2 * a; //twoA
TAB = 2 * (a + b); //twoAB
d = 2 * a + b;
x = startx, y = starty;
if (!kFlag) {
for (int i = 0; i < (endx - startx); i++) {
if (d >= 0) {
glVertex2i(++x, y);
d += TA;
}
else {
glVertex2i(++x , y +=sFlag);
d += TAB;
}
}
}
else if (kFlag) {
if (kFlag == 1) {
TA = 2 * b;
d = 2 * b + a;
}
for (int i = 0; i < abs(endy - starty); i++) {
if (d >= 0) {
glVertex2i(++x , y +=sFlag);
d += TAB;
}
else {
glVertex2i(x, y+=sFlag);
d += TA;
}
}
}
}
else if (startx == endx) {//垂直画线
if (starty < endy) {
for (int i = starty; i < endy; i++) {
glVertex2i(startx, i);
}
}
else if (starty > endy) {
for (int i = endy; i < starty; i++) {
glVertex2i(startx, i);
}
}
}
else if (starty == endy) {//水平画线
if (startx < endx) {
for (int i = startx; i < endx; i++) {
glVertex2i(i, starty);
}
}
else if (startx > endx) {
for (int i = endx; i < startx; i++) {
glVertex2i(i, starty);
}
}
}
glFlush();
glEnd();
}

Bresenham画线算法

这是目前计算机图形学使用的最多的直线生成算法。在计算最佳逼近中使用的全部都是整数运算,可以大幅度的提升计算速度。
与TMP不同的一点就是,TMP是计算中点与直线上的点,而Bresenham是计算上下格子与直线竖直距离的差。也就是下面图像中的d2-d1
image
推导过程如下:
直线方程可以表示为(不管两种特殊情况)

$$
y=kx+b

k=\frac{y_1-y_0}{x_1-x_0}=\frac{dy}{dx},b=y_0-kx_0
$$

当 $ 0<k<1$时直线向正方向前进一个像素,对应的最佳逼近的 $x_{i+1}=x_i+1$, $y_{i+1}=y_i+1$or $y_i$

$$
y=k(x_i+1)+b

d_1=y-y_i

d_2=y_i+1-y
$$

$$
d_1-d_2=2y-2y_i-1=2(k(x_i+1)+b)-2y_i-1
$$

当 $d_1-d_2>0$时

$y_{i+1}=y_i+1$

当 $d_1-d_2<=0$时

$y_{i+1}=y_i$

魔法:当dx>0时,把 $d_10d_2$乘上$dx$,不影响整个式子的正负得到:

$$
p_i=dx(d_1-d_2)
$$

$$
k=\frac{dy}{dx}
$$

所以

$$
p_i=2x_0dy-2y_idx+2dy+(2b-1)dx
$$

当i=0时,得到迭代起点:

$$
p_0=2dy-dx
$$

当 $p_i>0时$

$$
p_{i+1}=pi+2dy-2dx
$$

当 $p_i<=0时$

$$
p_{i+1}=p_i+2dy
$$

推导到此结束,下面是实现,这个实现和TMP十分相似,但是计算量比TMP稍微小一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
if (startx != endx && starty != endy) {
bool kFlag = 0; //斜率是否大于1
int sFlag = 1; //斜率的正负
if (startx > endx) { //因为算法是x递增的,所以要保持起点x在终点左边
int tempx = startx, tempy = starty;
startx = endx, starty = endy;
endx = tempx, endy = tempy;
}
if (abs(starty - endy) > abs(startx - endx)) {
kFlag = true;
}
if (starty > endy) { //标记斜率小于零
sFlag = -1;
}
int x, y;
int dx, dy, p;
if (sFlag == -1)
endy = starty + (starty - endy);
dx = endx - startx;
dy = endy - starty;
x = startx, y = starty;
if (!kFlag) {
p = 2 * dy - dx;
for (int i = 0; i < (endx - startx); i++) {
if (p <= 0) {
glVertex2i(++x, y);
p += 2 * dy;
}
else {
glVertex2i(++x, y += sFlag);
p += 2 * dy - 2 * dx;
}
}
}
else {
p = 2 * dx - dy;
for (int i = 0; i < (endy - starty); i++) {
if (p <= 0) {
glVertex2i(x, y += sFlag);
p += 2 * dx;
}
else {
glVertex2i(++x, y += sFlag);
p += 2 * dx - 2 * dy;
}
}
}
}

同样的,你可以在这里找到完整代码:

BRESENHAM算法完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
void BRESENHAM_Line(int startx, int starty, int endx, int endy) {
glBegin(GL_POINTS);
if (startx != endx && starty != endy) {
bool kFlag = 0; //斜率是否大于1
int sFlag = 1; //斜率的正负
if (startx > endx) { //因为算法是x递增的,所以要保持起点x在终点左边
int tempx = startx, tempy = starty;
startx = endx, starty = endy;
endx = tempx, endy = tempy;
}
if (abs(starty - endy) > abs(startx - endx)) {
kFlag = true;
}
if (starty > endy) { //标记斜率小于零
sFlag = -1;
}
int x, y;
int dx, dy, p;
if (sFlag == -1)
endy = starty + (starty - endy);
dx = endx - startx;
dy = endy - starty;
x = startx, y = starty;
if (!kFlag) {
p = 2 * dy - dx;
for (int i = 0; i < (endx - startx); i++) {
if (p <= 0) {
glVertex2i(++x, y);
p += 2 * dy;
}
else {
glVertex2i(++x, y += sFlag);
p += 2 * dy - 2 * dx;
}
}
}
else {
p = 2 * dx - dy;
for (int i = 0;i < (endy - starty); i++) {
if (p <= 0) {
glVertex2i(x, y += sFlag);
p += 2 * dx;
}
else {
glVertex2i(++x, y += sFlag);
p += 2 * dx - 2 * dy;
}
}
}
}
else if (startx == endx) {//垂直画线
if (starty < endy) {
for (int i = starty; i < endy; i++) {
glVertex2i(startx, i);
}
}
else if (starty > endy) {
for (int i = endy; i < starty; i++) {
glVertex2i(startx, i);
}
}
}
else if (starty == endy) {//水平画线
if (startx < endx) {
for (int i = startx; i < endx; i++) {
glVertex2i(i, starty);
}
}
else if (startx > endx) {
for (int i = endx; i < startx; i++) {
glVertex2i(i, starty);
}
}
}
glFlush();
glEnd();
}

代码汇总

DrawLine.hpp代码

//DrawLine.hpp
#pragma once
#include <cmath>
#include <gl/glut.h>

/*
数值微分算法实现
*/
/// <summary>
/// digitial differential analyzer 
/// called DAA
/// </summary>
/// <param name="startx">起始位置x</param>
/// <param name="starty"></param>
/// <param name="endx">终止位置x</param>
/// <param name="endy"></param>
void DDA_Line(int startx, int starty, int endx, int endy) {
	glBegin(GL_POINTS);
	if (startx != endx && starty != endy)
	{
		double x, y;
		double k;			//斜率
		k = (static_cast<float>(endy - starty) /static_cast<float>(endx - startx));
		x = (double)startx, y = (double)starty;
		if (abs(k)<1.0) {
			for (int i = 0; i < abs(endx - startx); i++) {
				if (endx > startx) {
					x += 1;
					y += k;
				}
				else {
					x -= 1;
					y -= k;
				}
				glVertex2i(static_cast<int>(x), static_cast<int>(y+0.5));		//y四舍五入
			}
		}
		else if (abs(k) > 1.0) {
			for (int i = 0; i < abs(endy - starty); i++) {
				if (endy > starty) {
					y += 1;
					x += 1.0/k;
				}
				else {
					y -= 1;
					x -= 1.0/k;
				}
				glVertex2i(static_cast<int>(x + 0.5), static_cast<int>(y));		//x四舍五入
			}
		}
	}
	else if (startx == endx) {//垂直画线
		if (starty < endy) {
			for (int i = starty; i < endy; i++) {
				glVertex2i(startx, i);
			}
		}
		else if (starty > endy) {
			for (int i = endy; i < starty; i++) {
				glVertex2i(startx, i);
			}
		}
	}
	else if (starty == endy) {//水平画线
		if (startx < endx) {
			for (int i = startx; i < endx; i++) {
				glVertex2i(i, starty);
			}
		}
		else if (startx > endx) {
			for (int i = endx; i < startx; i++) {
				glVertex2i(i, starty);
			}
		}
	}
	glFlush();
	glEnd();
}

/*
中点画线算法实现
*/
/// <summary>
/// The Middle Point
/// Called TMP
/// </summary>
/// <param name="startx">起始位置x</param>
/// <param name="starty"></param>
/// <param name="endx">终止位置x</param>
/// <param name="endy"></param>
void TMP_Line(int startx, int starty, int endx, int endy) {
	glBegin(GL_POINTS);
	if (startx != endx && starty != endy)
	{
		bool kFlag = 0;		//斜率是否大于1
		int sFlag = 1;			//斜率的正负
		if (startx > endx) {		//因为算法是x递增的,所以要保持起点x在终点左边
			int tempx = startx, tempy = starty;
			startx = endx, starty = endy;
			endx = tempx, endy = tempy;
		}
		if (abs(starty - endy) > abs(startx - endx)) {
			kFlag = true;
		}
		if (starty > endy) {		//标记斜率小于零
			sFlag = -1;
		}
		int a, b, TA, TAB, d, x, y;
		if (sFlag == -1)
			endy = starty + (starty - endy);

		a = starty - endy;
		b = endx - startx;
		TA = 2 * a;					//twoA
		TAB = 2 * (a + b);		//twoAB
		d = 2 * a + b;
		x = startx, y = starty;
		if (!kFlag) {
			for (int i = 0; i < (endx - startx); i++) {
				if (d >= 0) {
					glVertex2i(++x, y);
					d += TA;
				}
				else {
					glVertex2i(++x , y +=sFlag);
					d += TAB;
				}
			}
		}
		else if (kFlag) {
			if (kFlag == 1) {
				TA = 2 * b;
				d = 2 * b + a;
			}
			for (int i = 0; i < abs(endy - starty); i++) {
				if (d >= 0) {
					glVertex2i(++x , y +=sFlag);
					d += TAB;
				}
				else {
					glVertex2i(x, y+=sFlag);
					d += TA;
				}
			}
		}
	}
	else if (startx == endx) {//垂直画线
		if (starty < endy) {
			for (int i = starty; i < endy; i++) {
				glVertex2i(startx, i);
			}
		}
		else if (starty > endy) {
			for (int i = endy; i < starty; i++) {
				glVertex2i(startx, i);
			}
		}
	}
	else if (starty == endy) {//水平画线
		if (startx < endx) {
			for (int i = startx; i < endx; i++) {
				glVertex2i(i, starty);
			}
		}
		else if (startx > endx) {
			for (int i = endx; i < startx; i++) {
				glVertex2i(i, starty);
			}
		}
	}
	glFlush();
	glEnd();
}

/*
Bresenham算法
这是图形学中用的最多的直线生成算法,全部是整数计算,加快了计算的速度
*/
/// <summary>
/// Bresenham
/// </summary>
/// <param name="startx"></param>
/// <param name="starty"></param>
/// <param name="endx"></param>
/// <param name="endy"></param>
void BRESENHAM_Line(int startx, int starty, int endx, int endy) {
	glBegin(GL_POINTS);
	if (startx != endx && starty != endy) {
		bool kFlag = 0;		//斜率是否大于1
		int sFlag = 1;			//斜率的正负
		if (startx > endx) {		//因为算法是x递增的,所以要保持起点x在终点左边
			int tempx = startx, tempy = starty;
			startx = endx, starty = endy;
			endx = tempx, endy = tempy;
		}
		if (abs(starty - endy) > abs(startx - endx)) {
			kFlag = true;
		}
		if (starty > endy) {		//标记斜率小于零
			sFlag = -1;
		}
		int x, y;
		int dx, dy, p;
		if (sFlag == -1)
			endy = starty + (starty - endy);
		dx = endx - startx;
		dy = endy - starty;
		x = startx, y = starty;
		if (!kFlag) {
			p = 2 * dy - dx;
			for (int i = 0; i < (endx - startx); i++) {
				if (p <= 0) {
					glVertex2i(++x, y);
					p += 2 * dy;
				}
				else {
					glVertex2i(++x, y += sFlag);
					p += 2 * dy - 2 * dx;
				}
			}
		}
		else {
			p = 2 * dx - dy;
			for (int i = 0;i < (endy - starty); i++) {
				if (p <= 0) {
					glVertex2i(x, y += sFlag);
					p += 2 * dx;
				}
				else {
					glVertex2i(++x, y += sFlag);
					p += 2 * dx - 2 * dy;
				}
			}
		}
	}
	else if (startx == endx) {//垂直画线
		if (starty < endy) {
			for (int i = starty; i < endy; i++) {
				glVertex2i(startx, i);
			}
		}
		else if (starty > endy) {
			for (int i = endy; i < starty; i++) {
				glVertex2i(startx, i);
			}
		}
	}
	else if (starty == endy) {//水平画线
		if (startx < endx) {
			for (int i = startx; i < endx; i++) {
				glVertex2i(i, starty);
			}
		}
		else if (startx > endx) {
			for (int i = endx; i < startx; i++) {
				glVertex2i(i, starty);
			}
		}
	}
	glFlush();
	glEnd();
}
``` 用于测试的一个主函数

```cpp
/*
你可以使用左键绘制顶点
你可以使用右键删除顶点
直线的绘制沿着顶点顺序
*/
#include <gl/glut.h>
#include <iostream>
#include <list>
#include "DrawLine.hpp"
using namespace std;
#define m_POINT_SIZE 10
#define m_LINE_SIZE 2
list<pair<int, int >>Vertex;
void onDisplay();
void onReshape(int w, int h);
void onMouse(int button, int state, int x, int y);
void onReshape(int w, int h)
{
	// 设置视口大小
	glViewport(0, 0, w, h);
	// 切换矩阵模式为投影矩阵
	glMatrixMode(GL_PROJECTION);
	// 载入单位矩阵
	glLoadIdentity();
	// 进行二维平行投影
	gluOrtho2D(0, w, h, 0);
	// 切换矩阵模式为模型矩阵
	glMatrixMode(GL_MODELVIEW);
	// 发送重绘
	glutPostRedisplay();
}
void onMouse(int button, int state, int x, int y){
	if (state == GLUT_DOWN) {
		if (button == GLUT_LEFT_BUTTON)Vertex.push_back(make_pair(x, y));
		else if (button == GLUT_RIGHT_BUTTON) {
			auto ibeg = Vertex.begin();
			while (ibeg != Vertex.end()) {
				if (((x - ibeg->first) * (x - ibeg->first)) + ((y - ibeg->second) * (y - ibeg->second)) < 400) {
					Vertex.erase(ibeg);
					break;
				}
				ibeg++;
			}
		}
	}
	onDisplay();
}
void onDisplay() {
	glClearColor(224 / 255.0, 237 / 255.0, 253 / 255.0,1.0);
	glClear(GL_COLOR_BUFFER_BIT);

	glColor3f(1.0f, 0, 0);
	auto ibeg = Vertex.begin(),jbeg=ibeg;
	bool flag = false;
	while (ibeg != Vertex.end()) {
		glPointSize(m_POINT_SIZE);
		glBegin(GL_POINTS);
		glVertex2i(ibeg->first, ibeg->second);
		glEnd();
		glPointSize(m_LINE_SIZE);
		if (!flag)
			flag = true;
		else {
			//这里可以选择直线绘制方式
			BRESENHAM_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);
			//TMP_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);
			//DDA_Line(ibeg->first, ibeg->second, jbeg->first, jbeg->second);
		}
		jbeg = ibeg;
		ibeg++;
	}
	glutSwapBuffers();
}

int main(int argc, char* argv[])
{
	// 初始化 glut
	glutInit(&argc, argv);
	// 设置 OpenGL 显示模式(双缓存, RGB 颜色模式)
	glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
	// 设置窗口初始尺寸
	glutInitWindowSize(1000,800);
	// 设置窗口初始位置
	glutInitWindowPosition(0, 0);
	// 设置窗口标题
	glutCreateWindow("Terix");
	glutReshapeFunc(onReshape);
	glutDisplayFunc(onDisplay);
	glutMouseFunc(onMouse);
	// 进入 glut 事件循环
	glutMainLoop();
	return 0;
}
``` ## 下一篇 [下一篇->圆形的绘制](https://www.cnblogs.com/zhywyt/articles/17341756.html)

基于Glut的俄罗斯方块开发

# 基于Glut的俄罗斯方块

概述

作为大一下期的一个C++程序设计的作业,原本李卫明老师是打算让我们用MFC实现一个俄罗斯方块的,但是我不想学习MFC,所以使用了glut来实现它。所有的代码由自己一个人完成,Game类的维护由李卫明老师的教程优化而来。李卫明老师课程传送门:
1.建立框架
2.添加功能模块
3.消息响应和界面绘制
其中,我借鉴了李老师俄罗斯方块的存储方式(4*4的二维数组来存储一个俄罗斯方块)然后在这篇博客的最后也回答一下李老师提出的这些问题:

Q1本游戏开发的主要过程分哪几步?点击跳转
Q2游戏界面里控件ID有什么作用? 点击跳转
Q3游戏中主要有哪些类?哪些类使用了继承? A:并没有
Q4用什么表示俄罗斯方块的形状和颜色?点击跳转
Q5l游戏里的俄罗斯方块判断是否可以下落、左移、右移、旋转的方法是什么?点击跳转
Q6程序里如何实现俄罗斯方块实际下落、左移、右移、旋转?点击跳转
Q7程序里是哪里使用了动态分配?如何避免内存泄漏? A:没有使用,唯一的地方是Vector,不需要自己进行管理。
Q8主界面如何绘制、备用俄罗斯方块如何绘制?点击跳转
Q9如何实现俄罗斯方块的定时下落?点击跳转
Q10如何实现按钮点击响应?点击跳转
所以这篇博客可能会比较长,就当自己的一次记录吧。

Game类

Game类的规划

在我的Game类里面,存储了整个游戏需要的数据,而且维护了整个游戏的运行,但是因为回调函数不允许绑定了对象的函数指针,所以我使用了友元函数作为回调函数,至于为什么没有使用类的静态函数成员,可能是因为我懒吧。或者这个项目比较小,所以没在乎这么多了。这次的代码及其不规范,算是给自己积累一些经验吧。

Game类的数据成员

首先我们来分析一下俄罗斯方块这个游戏的场景和运行逻辑:
image
这里分为了三个方块单位,和一些文字单位,可以看到,蓝色的俄罗斯方块正在随着时间往下走,白色的预备方块静止在等待区域,那么我们需要两个俄罗斯方块对象来存储他们的信息。再看下面的绿色 L 形状的俄罗斯方块,它已经到底了,和场景融为了一体,那么我们也就不需要一个俄罗斯方块的类来存储它了,可以把它存储在场景中,我们用一个二维向量来存储这个场景的信息。

方块成员

image
Tool类我们稍后再讲,它会是存储一个俄罗斯方块的工具类。然后我们使用vector<vector<int>>来存储这个场景的所有信息。(李卫明老师的教程中使用了动态分配的数组。)

信息成员(分数,等级)

image
分数、最高分和等级我们使用三个无符号整型来存储。等级是难度等级,可以用于我们之后的提高难度。

Tool类

好了,现在我们来实现最基础的Tool类,Tool类是一个俄罗斯方块对象,它有着这些属性:
**
1.记录了方俄罗斯方块的类型
2.记录了俄罗斯方块的形状
3.记录了俄罗斯方块的位置
4.记录是否有过移动(用于判断游戏结束)
5.可以进行移动、旋转
**

点击返回问题目录

1.俄罗斯方块的类型

我们使用一个枚举类型,来方便自己绘制俄罗斯方块,枚举中的名字为俄罗斯方块的类型,还可以作为绘制方块时的颜色的枚举使用,如下:
image
其中 WALL是提供给场景使用的一个枚举常量

2.俄罗斯方块的形状

每一个俄罗斯方块都可以认为被一个4 * 4的网格包裹住了,所以我们可以使用一个4 * 4的二维数组来记录它在地图中所占的位置:

3.俄罗斯方块的位置

我们记录一个4 * 4的网格的位置,其实只需要这个网格左上角的方块的坐标就可以了,也就是说我们记录俄罗斯方块的位置,其实只需要记录一个点的x、y坐标。

4.是否移动过

很简单,使用一个bool类型的变量即可,那么我们的Tool类的数据成员看起来像这样:
image

点击返回问题目录

5.移动旋转的实现

判断是否可以旋转的时候,我们就需要和场景中的方块联系起来了,如果一个方块无法往某个方向移动的话,意味着移动了就会与已经存在的方块重合,或者出游戏区域,那么我们的Tool类旋转的工作就是返回一个移动后的Tool类的结果,但是不能直接对自己移动,因为对于一个Tool对象来说,它不能知道自己是否可以移动但是移动的函数,直接移动就行,之后后讲到为什么,这里举两个例子,旋转和下落:

旋转

1
2
3
4
5
6
7
8
9
//顺时针旋转
Tool Rotate() {
Tool NewOne(*this);
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
NewOne._data[j][3 - i] = _data[i][j];
}
return NewOne;
}

下落

1
2
3
void MoveDown() {
setPosition(_x, _y + 1);
}

特别的setPosition函数,就是更改了Tool的位置信息,就不说了。然后我们来说一下Tool的构造函数。我们需要自己定义两个构造函数,一个是默认的构造函数,一个是接受三个参数的构造函数,函数原型如下:
image
它接受了一个坐标和一个类型作为参数,对对象进行初始化。要记得对所有的数据成员进行初始化哦,保持好习惯~

带参的构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Tool(int x, int y, ToolType type) 
:_x(x), _y(y), _type(type),run(false)
{
_data.resize(4, vector<int>(4));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
_data[i][j] = 0;
switch (type)
{
case LL:
for (int i = 0; i <= 2; i++)_data[1][i] = LL;
_data[2][2] = LL;
break;
case OO:
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= 2; j++)
_data[i][j] = OO;
break;
case DOT:
_data[1][1] = DOT;
break;
case II:
for (int i = 0; i < 4; i++)_data[1][i] = II;
break;
case TT:
for (int i = 0; i < 3; i++)_data[2][i] = TT;
_data[1][1] = TT;
break;
}
}

然后,我们还需要一个默认构造函数,来创建临时的Tool对象:

1
2
3
4
5
Tool()
:run(false),_x(0),_y(0),_type(LL)
{
_data.resize(4, vector<int>(4));
}

因为没有动态分配的数据(vector可以自己析构,不用处理),所以我们不需要写析构函数,使用默认的析构函数即可。
到此,我们的Tool类就写完了。

Game类的数据维护函数(私有)

NextTool

Game类有了他自己的数据成员,那么可以开始对数据成员进行维护了,当一个俄罗斯方块落地的时候,替补的俄罗斯方块就会替补当前使用的俄罗斯方块,然后再生成一个新的俄罗斯方块,这个函数我们叫NextTool()

NextTool

1
2
3
4
5
6
void Game::NextTool() {
swap(m_tool, m_next);
m_tool.setPosition(rePx, rePy);
ToolType aType = ToolType(abs(rand()%(TTEnd-LL))+LL);
m_next = Tool(waitPx, waitPy, aType);
}

我们首先交换两个Tool对象,然后把工作中的Tool对象m_tool移动到游戏区域,并且把m_next对象重置为一个随机的俄罗斯方块。这里的随机操作其实是比较优美的形式,因为abs(rand()%a)得到是数据的范围是(0,a-1),但是我们的ToolType的枚举的数值范围是(LL,TTEnd-1),所以我们设置为abs(rand()%(TTEnd-LL))+LL就解决了这个问题。

AddToMap

然后当这个Tool无法继续下落的时候,我们判断这个这个Tool对象应该加入场景了,我们创建函数AddToMap():

AddToMap

1
2
3
4
5
//先把游戏方块加入背景
for(int i=0;i<4;i++)
for (int j = 0; j < 4; j++)
if (m_tool._data[i][j])
m_map[i + m_tool._x][j + m_tool._y] = m_tool._data[i][j];

思考一下,什么时候会出现一行被消除?是不是只有某一个对象加入场景的时候?也就是说,我们应该在对象加入场景的时候进行检测,是否存在某行可以消除。我们可以在加入场景的时候记录一下改变的行数,然后对这些改变的行进行检测。最终的AddToMap代码如下:

AddToMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void Game::AddToMap() {
vector<int>test;
//先把游戏方块加入背景
for(int i=0;i<4;i++)
for (int j = 0; j < 4; j++)
if (m_tool._data[i][j]) {
m_map[i + m_tool._x][j + m_tool._y] = m_tool._data[i][j];
test.push_back(j + m_tool._y);
}
//检查游戏区域是否可以消除
auto ibeg = test.begin();
while (ibeg != test.end()) {
int i = *ibeg;
bool flag = true;
for (int j = dx; j < GameRow; j++) {
if (!m_map[j][i]) {
flag = false;
break;
}
}
//可以消除第 i 行
if (flag) {
//把 i 行上面的所有行向下移动
for (int k = i; k > 0; k--) {
for (int j = dx; j < GameRow; j++) {
m_map[j][k] = m_map[j][k - 1];
}
}
//把顶部置空
for (int j = dx; j < GameRow + dx; j++)
m_map[j][0] = 0;
clearTimes++;
//计算加分
_points += GameRow * clearTimes;
if (_points > PB_points) {
PB = true;
PB_points = _points;
}
}
//设置难度
Diff = clearTimes / 3;
ibeg++;
}
//如果加入的时候方块没有移动,判断游戏结束
if (!m_tool.run) {
GameOver();
}
}

很好,我们的AddToMap函数就这样完成了。接下来就是让我们的Tool对象接受消息然后动起来了。我们需要实现向下、向左、向右以及旋转的判断和实施函数。

向下、向左、向右以及旋转

点击返回问题目录
我们的Tool类可以返回变换之后的结果,那么我们的Game类就需要判断是否能够进行变换,以及管理变换,这里我们还是以向下和旋转来举例:

CanMoveDown

1
2
3
4
5
6
7
8
9
10
11
12
bool Game::CanMoveDown() {
for(int i=0;i<4;i++)
for (int j = 0; j < 4; j++) {
if (m_tool._data[i][j]) {
if (m_tool._y +j+ 1 < Cow) {
if (m_map[m_tool._x+i][m_tool._y +j + 1])return false;
}
else return false;
}
}
return true;
}

这个函数没什么意思,就是一个个的查看,如果重合,那么说明不能进行移动,否则可以。CangetMoveRight函数和CangetMoveLeft函数也相似。本质上是因为平移只需要改变Tool对象的坐标就行了,不需要对节点信息进行修改。让我们来看看旋转

Rotate

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Game::Rotate() {
//剪枝,如果是中心对称的图形,直接返回true,代表以及完成了旋转。
if (m_tool._type == DOT||m_tool._type==OO)return true;
Tool revTool = m_tool.Rotate();
for(int i=0;i<4;i++)
for (int j = 0; j < 4; j++)
if (revTool._data[i][j])
if (m_map[revTool._x+i][revTool._y+j])return false;
//如果没有冲突,直接交换revTool和m_tool,这里和移动赋值的理念有点相似,
//因为我的m_tool已经不需要了,直接让revTool来进行析构。
swap(m_tool, revTool);
return true;
}

因为旋转的开销还是比较大的,所以我们不进行多次旋转操作,也就是不设置CanRotate函数,直接改成Rotate函数,如果能够旋转就实施了。

Drop

因为下落有着独特的数据维护方法,所以我们写一个Drop函数来维护这一行为,Drop函数需要检查是否可以下落,以及下落之后的状态更新,还有不能下落时的数据处理。

Drop

1
2
3
4
5
6
7
8
9
10
void Game::Drop() {
if (CanMoveDown()) {
m_tool.run = true;
m_tool.MoveDown();
}
else {
AddToMap();
NextTool();
}
}

在可以移动时,更新Tool的移动状态为true,并更新m_tool的数据,

Start

到这里,我们的数据维护函数就基本上写完了,我们的Game对象可以操控两个Tool对象进行移动,判断是否可以移动,计算游戏加分,计算游戏是否结束等等,接下来我们为Game类添加开始函数,因为在游戏开始之前,我们的Game对象中的Tool对象是没有任何数据的,所以我们使用两次NextTool来让m_tool和m_next都有数据。然后,我们还需要引入一个新的概念游戏状态,我们来看Start函数:

Start

1
2
3
4
5
void Game::Start() {
status = RUN;
NextTool();
NextTool();
}

我们要做的事情很简单,把游戏的状态更改为RUN,然后调用两次NextTool就行了。

游戏状态的更新

首先我们为Game类添加一个枚举对象,用于描述游戏的状态:

1
2
3
4
5
6
7
typedef enum {
STOP, //游戏暂停
PRESTART, //游戏开始前
RUN, //游戏进行时
GAMEOVER, //游戏结束
GAMEWIN, //游戏胜利
}GameMode;

(其实是不存在游戏胜利这一说的,但是我想留一个小彩蛋,所以加入了这一状态,但是达到这个条件是人类不太可能完成的。)
然后我们为之前需要更改游戏状态的地方添加游戏状态的更改。比如在AddToMap中提到的GameOver函数:

GameOver
1
2
3
4
5
6
7
void Game::GameOver() {
if (_points > PB_points) {
PB = true;
PB_points = _points;
}
status = GAMEOVER;
}

更新游戏状态,并检测是否破纪录。

构造函数

创建一个Game类的对象的时候,将游戏的状态设置为PRESTAT开始前:

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Game::Game() 
:status(PRESTART),_points(0),PB_points(0),PB_Diff(0),
clearTimes(0),Diff(0),PB(false)
{
m_map.resize(Row, vector<int>(Cow));
srand((unsigned int)time(NULL));
for (int i = 0; i < Cow; i++) {
//左边竖墙
for (int j = 0; j < dx; j++)
m_map[j][i] = WALL;
//中间竖墙
for (int j = 1; j <= dx; j++)
m_map[GameRow + j][i] = WALL;
//右边竖墙
for (int j = 1; j <= dx; j++)
m_map[Row - j][i] = WALL;
}
//顶上底下横墙
for (int i = 0; i < dx; i++)
for (int j = 0; j < Row - GameRow - 3 * dx; j++) {
m_map[GameRow + 2 * dx + j][i] = WALL;
m_map[GameRow + 2 * dx + j][Cow - 1 - i] = WALL;
}
//中间横墙
for (int i = 0; i < Row - GameRow - 3 * dx; i++)m_map[GameRow + 2 * dx + i][4 + dx] = WALL;
//next Toll右边的横杆
for (int i = 0; i < 4; i++)m_map[2 * dx + GameRow][dx + i] = WALL;
}

构造函数不仅要初始化所有数据、设置游戏状态外,还需要将场景的WALL部分填充,dx是设置的一个静态整形变量,用于调整边界的厚度。Row和Cow是屏幕的大小;GameRow和GameCow就是游戏区域了,这些是整形常量,这个图可以说明这一关系:
image
这里是我的初始化

1
2
3
4
5
6
const int mapScre = 1;						//场景缩放
const int NodeSize = 20; //方形边长
const int Cow = 30 * mapScre; //窗口行数 y
const int Row = 24 * mapScre; //列数 x
const int GameCow = 30 * mapScre; //游戏场景行数
const int GameRow = 16 * mapScre; //列数
1
2
3
4
5
//Game::public
static const int dx, dy; //用于弥补场景边框距离
static const int rePx, rePy; //操纵的Tool的初始位置
static const int waitPx, waitPy; //等待初始位置
static const int infoPx, infoPy; //信息所绘制的位置
reset

其他的状态更新操作会在消息处理的时候进行,然后我还需要完成Game类的最后一个成员函数reset,用于重置游戏:

1
2
3
4
5
6
7
8
9
10
void Game::reset() {
PB = false;
status = PRESTART;
_points = 0;
clearTimes = 0;
Diff = 0;
for (int i = dx; i < GameRow+dx; i++)
for (int j = 0; j < GameCow; j++)
m_map[i][j] = 0;
}

Glut

不会装glut的可以参考这篇博客

【Opengl】Glut下载与环境配置
返回irrklang

另外,我们还需要glfw来提供消息处理的宏定义。这里我只教VS的配置方法:
打开你的目标工程,然后点击上方的工具->NuGet包管理器

image
点击浏览->搜索glfw->下载
image
下载到当前项目就行了。我们需要的头文件有这么两个:

1
2
#include <gl/glut.h>
#include <GLFW/glfw3.h>

当然还要包括你自己写的Game类的头文件,然后创建我们唯一的Game类对象(作为全局变量)Game myGame;在main函数中对窗口进行初始化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(int argc, char* argv[])
{
// 初始化 glut
glutInit(&argc, argv);
// 设置 OpenGL 显示模式(双缓存, RGB 颜色模式)
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
// 设置窗口初始尺寸
glutInitWindowSize(Row*NodeSize, Cow*NodeSize);
// 设置窗口初始位置
glutInitWindowPosition(100, 100);
// 设置窗口标题
glutCreateWindow("Terix");
// 进入 glut 事件循环
glutMainLoop();
return 0;
}

然后我们还需要绑定输入回调函数、显示回调函数、计时器、窗口尺寸改变的回调函数以及设置菜单(非必须)。

回调函数

回调函数中,大部分需要对Game类的的数据进行更新或者读取,那么最好的办法就是使用成员函数进行绑定,但是这是不被允许的。因为指向绑定函数的指针只能用于调用函数。也就是说我们的回调函数不能是类的成员函数。所以我们将其设置为友元。

1
2
3
4
friend void Input(int data, int x, int y);
friend void onDisplay();
friend void Input(unsigned char nchar, int x, int y);
friend void processMenuEvents(int option);

然后我们开始,先从简单的来处理

1.窗口尺寸变化回调函数

这个函数允许我们的窗口在大小改变时,不会出现图像拉扯的情况,设置了这个回调函数之后的效果是这样的:
image
拖动窗口,使其尺寸发生变化,会得到这样的结果:
image
不仅如此,我们的投影也发生在这个函数里面,投影的原理我就不讲了,这涉及到一些图形学的内容,有兴趣的可以去看Games101的课程,传送门:
【GAMES101-现代计算机图形学入门-闫令琪】
这里我们设置一个简单的二维平行投影:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void onReshape(int w, int h)
{
// 设置视口大小
glViewport(0, 0, w, h);
// 切换矩阵模式为投影矩阵
glMatrixMode(GL_PROJECTION);
// 载入单位矩阵
glLoadIdentity();
// 进行二维平行投影
gluOrtho2D(0, w, h, 0);
// 切换矩阵模式为模型矩阵
glMatrixMode(GL_MODELVIEW);
// 发送重绘
glutPostRedisplay();
}

// In main
------------
// 设置窗口尺寸变化回调函数
glutReshapeFunc(onReshape);

2.计时器

计时器可以让我们在一定的时间内调用一次该函数,我们需要计时器来使俄罗斯方块自动的下坠,并且下降的速度就是我们调用这个函数所间隔的时间,我们可以利用这点来动态的设置游戏的难度:

点击返回问题目录

1
2
3
4
5
6
7
8
9
10
11
12
13
void Ontime(int timeid) {
timeid++;
timeid %= 1000;
//如果游戏进行中,那么下降一格
if(myGame.getStatus() == RUN)
myGame.Drop();
int Deltatime = 150 - 3 * myGame.getDiff();
//It is imposible!!!
if (Deltatime <= 50)myGame.ChangeStatus(GAMEWIN) ;
//进行图形的绘制
onDisplay();
glutTimerFunc(Deltatime, Ontime, 1);
}

这里我设置了一个很简单的难度系统,难度和等级成正比?Deltatime就是调用该函数所间隔的时间,我设置了当Deltatime<=50时判定为游戏胜利,也就是1秒钟1000/50=20帧,就是说它会下降20格。(

3.显示回调函数

可以看到,在Ontime里面调用了onDisplay函数,这个函数绘制了Game类的所有信息。首先让我们学一下glut的绘制逻辑,在每次绘制之前,我们需要对屏幕上的像素进行清理,我们叫它Clear,清理也不是随便清理,相当于清除了一帧的缓存,清除之前设置一个清楚颜色:

1
2
3
4
5
6
7
8
9
10
//in OnDisplay()
// 设置清屏颜色
glClearColor(BCR_COLOR,1);
// 用指定颜色清除帧缓存
glClear(GL_COLOR_BUFFER_BIT);
/*
绘制操作
*/
//Clear Buffer
glutSwapBuffers();

因为我们采用了双缓存的模式,所以以交换缓存为绘制结束。这样我们就不会出现频闪的问题。这里我也可以解释一下频闪出现的原因,频闪的出现不是因为电脑性能不行,而是你在画图的时候给屏幕发的绘制指令数太多了,应该先把一帧的画图操作全部写在缓存中,然后一次性发给屏幕绘制。

让我们回到俄罗斯方块的游戏场景,这次我们分游戏状态来处理:

RUN

image
这里我们需要绘制的信息有:两个俄罗斯方块、场景方块、游戏信息。

STOP

image
STOP很简单,我们只需要在RUN的基础上加上一句暂停的提示语就行了。

GAMEOVER

image
为了让GAMEOVER的时候,玩家可以感受到一种视觉冲击,所以我设置为了只绘制失败信息,并且如果分数没有超过作者的话,会奉上一句Git Gud,以表示敬意

PRESTART

image
这个就是游戏开始之前的画面,需要绘制一些指导的信息,比如如何开始游戏、游戏的一些快捷操作、游戏的自动保存机制等等。

实现

从上面的总结来看,不难发现:只有两个状态需要绘制场景和俄罗斯方块:

如何绘制一个方块?

在正式的绘制信息之前,我们先来介绍一下如何绘制一个正方形。在glut中绘制一个正方形的方式非常的简单,我们可以直接使用它封装的函数进行绘制。绘制一个矩形的代码会像这样:

1
2
glColor3f(ITEM_COLOR);
glRectd(x1,y1,x2,y2);

在绘制矩形前设置矩形的填充颜色,然后设置矩形对角线的两个点的坐标就行了。

点击返回问题目录

如何绘制信息?

在画面上,还有各种的信息显示,这里使用的是全英文的位图,因为内置的位图不支持中文,所以使用英文图个方便。绘制一串话的代码会像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
const char points[20] = "Points:";
char points_num[20];
sprintf(points_num, "%d", myGame._points);
//设置字体颜色
glColor3f(TEXT_COLOR);
//设置位图位置
glRasterPos2d(Infox, Infoy);
for(int i=0;points[i]!='\0';i++)
glutBitmapCharacter(INFO_FONT, points[i]);
//设置位图位置
glRasterPos2d(Infox, Infoy+5);
for(int i=0;points_num[i]!='\0';i++)
glutBitmapCharacter(INFO_FONT, points_num[i]);

因为使用了sprintf,所以这段代码在VS是跑不出来的,我们需要让VS认为这是安全的:加入宏定义:#define _CRT_SECURE_NO_WARNINGS

具体实现

运行时和暂停的绘制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
	//Draw Normal Info
if (myGame.status!=PRESTART&&myGame.status!=GAMEOVER&&myGame.status!=GAMEWIN) {
//Draw BackGroud
for (int i = 0; i < Row; i++) {
bool flag = true;
for (int j = 0; j < Cow; j++) {
switch (myGame.m_map[i][j]) {
case 0:
flag = false;
break;
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
case Game::WALL:
glColor3f(WALL_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}
if (flag)
glRectd(i * NodeSize, j * NodeSize, (i + 1) * NodeSize, (j + 1) * NodeSize);

flag = true;
}
}

//Draw Active Terix
switch (myGame.m_tool._type) {
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (myGame.m_tool._data[i][j])
glRectd((myGame.m_tool._x + i) * NodeSize, (myGame.m_tool._y + j) * NodeSize, (myGame.m_tool._x + i + 1) * NodeSize, (myGame.m_tool._y + j + 1) * NodeSize);
}
}
//Draw Waiting Terix
switch (myGame.m_next._type) {
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (myGame.m_next._data[i][j])
glRectd((myGame.m_next._x + i) * NodeSize, (myGame.m_next._y + j) * NodeSize, (myGame.m_next._x + i + 1) * NodeSize, (myGame.m_next._y + j + 1) * NodeSize);
}
}
//Draw Info
const char points[20] = "Points:", PBpoints[20] = "PB:", Diff[20] = "Rank:",zhywyt[]="zhywyt:";
char points_num[20], PBpoints_num[20], Diff_num[20],zhywyt_num[20];
sprintf(points_num, "%d", myGame._points);
sprintf(PBpoints_num, "%d", myGame.PB_points);
sprintf(Diff_num, "%d", myGame.Diff);
sprintf(zhywyt_num, "%d", myGame.zhywyt);

const char* strinfo[] = { points,PBpoints,Diff,zhywyt };
char* str_num[] = { points_num,PBpoints_num,Diff_num ,zhywyt_num};
if (!myGame.PB)
glColor3f(TEXT_COLOR);
else
glColor3f(PB_TEXT_COLOR);
for (int i = 0; i < 4; i++) {
if (i == 3)glColor3f(PB_TEXT_COLOR);
glRasterPos2d(Game::infoPx * NodeSize, (Game::infoPy + 5 * i) * NodeSize);
for (int j = 0; strinfo[i][j] != '\0'; j++)glutBitmapCharacter(INFO_FONT, strinfo[i][j]);
glRasterPos2d(Game::infoPx * NodeSize, (Game::infoPy + 5 * i + 2) * NodeSize);
for (int j = 0; str_num[i][j] != '\0'; j++)glutBitmapCharacter(INFO_FONT, str_num[i][j]);
}
//Draw Stop Info
if (myGame.status == STOP) {
const char PrestartInfo[30] = "Press Space to start.";
glRasterPos2d((Game::dx)*NodeSize, (GameCow + 3 * Game::dx) / 2 * NodeSize);
glColor3f(TEXT_COLOR);
for (int i = 0; PrestartInfo[i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, PrestartInfo[i]);
}
}
``` 其他的纯文本绘制

```c++
else {
if (myGame.status == GAMEOVER) {
//Draw gameover info
const char GameOverinfo[30] = "Game Over!";
char Score[30], Points[30];
sprintf(Points, "%d", myGame._points);
const char* VAO[3] = { GameOverinfo,Score,Points };
if (!myGame.PB) {
glColor3f(GAMEOVER_TEXT_COLOR);
sprintf(Score, "Your score is ");
}
else {
glColor3f(PB_TEXT_COLOR);
sprintf(Score, "WoW!! PB! ");
}
for (int i = 0; i < 3; i++) {
glRasterPos2d((Game::dx * 2) * NodeSize, ((GameCow - 4 * Game::dx) / 2+i*2*Game::dx) * NodeSize);
for (int j = 0; VAO[i][j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, VAO[i][j]);
}
char Good[40];
if (myGame.exZhywyt) {
sprintf(Good, "You are great ! You over the zhywyt!!");
}
else {
sprintf(Good, "Git Gud.");
}
glRasterPos2d((Game::dx * 2)* NodeSize, ((GameCow-4*Game::dx ) / 2+6*Game::dx) * NodeSize);
for (int j = 0;Good[j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, Good[j]);

}
else if (myGame.status == GAMEWIN) {
//It is imposible!!!!!
const char Info1[30] = "You may use something else", Info2[30] = "To do this imposible task.";
const char* str[] = { Info1,Info2 };
glColor3f(RGB(255, 0, 255));
for (int i = 0; i < 2; i++) {
glRasterPos2d((Game::dx * 2) * NodeSize, (GameCow + (i * 3 + 1) * Game::dx) / 2 * NodeSize);
for (int j = 0;str[i][j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, str[i][j]);
}
}
else {
const char helpInfo1[] = "Your Can Press the Space to stop Game.";
const char helpInfo2[] = "And you can click the right butttom to-";
const char helpInfo21[] = "-open the emun";
const char helpInfo3[] = "You should use the emnu \"exit\" to exit-";
const char helpInfo31[] = "-not close the window";
const char PrestartInfo[30] = "Press Space to start.";
const char LuckInfo[] = "Have Good Time!";
const char* str[] = {PrestartInfo,helpInfo31,helpInfo3,helpInfo21,helpInfo2,helpInfo1 };
glColor3f(TEXT_COLOR);
for (int j = 5; j >=0; j--) {
glRasterPos2d((Game::dx)*NodeSize, ((GameCow + 9 * Game::dx) / 2-j*2 )* NodeSize);
for (int i = 0; str[j][i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, str[j][i]);
}
glColor3f(PB_TEXT_COLOR);
glRasterPos2d((Game::dx)*NodeSize, ((GameCow + 12 * Game::dx)/2* NodeSize));
for (int i = 0; LuckInfo[i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, LuckInfo[i]);
}
}
``` onDisplay

```c++
void onDisplay()
{
// 设置清屏颜色
glClearColor(BCR_COLOR,1);
// 用指定颜色清除帧缓存
glClear(GL_COLOR_BUFFER_BIT);

//Draw Normal Info
if (myGame.status!=PRESTART&&myGame.status!=GAMEOVER&&myGame.status!=GAMEWIN) {
//Draw BackGroud
for (int i = 0; i < Row; i++) {
bool flag = true;
for (int j = 0; j < Cow; j++) {
switch (myGame.m_map[i][j]) {
case 0:
flag = false;
break;
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
case Game::WALL:
glColor3f(WALL_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}
if (flag)
glRectd(i * NodeSize, j * NodeSize, (i + 1) * NodeSize, (j + 1) * NodeSize);

flag = true;
}
}

//Draw Active Terix
switch (myGame.m_tool._type) {
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (myGame.m_tool._data[i][j])
glRectd((myGame.m_tool._x + i) * NodeSize, (myGame.m_tool._y + j) * NodeSize, (myGame.m_tool._x + i + 1) * NodeSize, (myGame.m_tool._y + j + 1) * NodeSize);
}
}
//Draw Waiting Terix
switch (myGame.m_next._type) {
case Game::LL:
glColor3f(LL_COLOR);
break;
case Game::OO:
glColor3f(OO_COLOR);
break;
case Game::DOT:
glColor3f(DOT_COLOR);
break;
case Game::II:
glColor3f(II_COLOR);
break;
case Game::TT:
glColor3f(TT_COLOR);
break;
default:
glColor3f(ELSE_COLOR);
}

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (myGame.m_next._data[i][j])
glRectd((myGame.m_next._x + i) * NodeSize, (myGame.m_next._y + j) * NodeSize, (myGame.m_next._x + i + 1) * NodeSize, (myGame.m_next._y + j + 1) * NodeSize);
}
}
//Draw Info
const char points[20] = "Points:", PBpoints[20] = "PB:", Diff[20] = "Rank:",zhywyt[]="zhywyt:";
char points_num[20], PBpoints_num[20], Diff_num[20],zhywyt_num[20];
sprintf(points_num, "%d", myGame._points);
sprintf(PBpoints_num, "%d", myGame.PB_points);
sprintf(Diff_num, "%d", myGame.Diff);
sprintf(zhywyt_num, "%d", myGame.zhywyt);

const char* strinfo[] = { points,PBpoints,Diff,zhywyt };
char* str_num[] = { points_num,PBpoints_num,Diff_num ,zhywyt_num};
if (!myGame.PB)
glColor3f(TEXT_COLOR);
else
glColor3f(PB_TEXT_COLOR);
for (int i = 0; i < 4; i++) {
if (i == 3)glColor3f(PB_TEXT_COLOR);
glRasterPos2d(Game::infoPx * NodeSize, (Game::infoPy + 5 * i) * NodeSize);
for (int j = 0; strinfo[i][j] != '\0'; j++)glutBitmapCharacter(INFO_FONT, strinfo[i][j]);
glRasterPos2d(Game::infoPx * NodeSize, (Game::infoPy + 5 * i + 2) * NodeSize);
for (int j = 0; str_num[i][j] != '\0'; j++)glutBitmapCharacter(INFO_FONT, str_num[i][j]);
}
//Draw Stop Info
if (myGame.status == STOP) {
const char PrestartInfo[30] = "Press Space to start.";
glRasterPos2d((Game::dx)*NodeSize, (GameCow + 3 * Game::dx) / 2 * NodeSize);
glColor3f(TEXT_COLOR);
for (int i = 0; PrestartInfo[i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, PrestartInfo[i]);
}
}
//Draw Prestart info
else {
if (myGame.status == GAMEOVER) {
//Draw gameover info
const char GameOverinfo[30] = "Game Over!";
char Score[30], Points[30];
sprintf(Points, "%d", myGame._points);
const char* VAO[3] = { GameOverinfo,Score,Points };
if (!myGame.PB) {
glColor3f(GAMEOVER_TEXT_COLOR);
sprintf(Score, "Your score is ");
}
else {
glColor3f(PB_TEXT_COLOR);
sprintf(Score, "WoW!! PB! ");
}
for (int i = 0; i < 3; i++) {
glRasterPos2d((Game::dx * 2) * NodeSize, ((GameCow - 4 * Game::dx) / 2+i*2*Game::dx) * NodeSize);
for (int j = 0; VAO[i][j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, VAO[i][j]);
}
char Good[40];
if (myGame.exZhywyt) {
sprintf(Good, "You are great ! You over the zhywyt!!");
}
else {
sprintf(Good, "Git Gud.");
}
glRasterPos2d((Game::dx * 2)* NodeSize, ((GameCow-4*Game::dx ) / 2+6*Game::dx) * NodeSize);
for (int j = 0;Good[j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, Good[j]);

}
else if (myGame.status == GAMEWIN) {
//It is imposible!!!!!
const char Info1[30] = "You may use something else", Info2[30] = "To do this imposible task.";
const char* str[] = { Info1,Info2 };
glColor3f(RGB(255, 0, 255));
for (int i = 0; i < 2; i++) {
glRasterPos2d((Game::dx * 2) * NodeSize, (GameCow + (i * 3 + 1) * Game::dx) / 2 * NodeSize);
for (int j = 0;str[i][j] != '\0'; j++)
glutBitmapCharacter(INFO_FONT, str[i][j]);
}
}
else {
const char helpInfo1[] = "Your Can Press the Space to stop Game.";
const char helpInfo2[] = "And you can click the right butttom to-";
const char helpInfo21[] = "-open the emun";
const char helpInfo3[] = "You should use the emnu \"exit\" to exit-";
const char helpInfo31[] = "-not close the window";
const char PrestartInfo[30] = "Press Space to start.";
const char LuckInfo[] = "Have Good Time!";
const char* str[] = {PrestartInfo,helpInfo31,helpInfo3,helpInfo21,helpInfo2,helpInfo1 };
glColor3f(TEXT_COLOR);
for (int j = 5; j >=0; j--) {
glRasterPos2d((Game::dx)*NodeSize, ((GameCow + 9 * Game::dx) / 2-j*2 )* NodeSize);
for (int i = 0; str[j][i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, str[j][i]);
}
glColor3f(PB_TEXT_COLOR);
glRasterPos2d((Game::dx)*NodeSize, ((GameCow + 12 * Game::dx)/2* NodeSize));
for (int i = 0; LuckInfo[i] != '\0'; i++)
glutBitmapCharacter(INFO_FONT, LuckInfo[i]);
}
}
//Clear Buffer
glutSwapBuffers();
}

如果仔细的读过代码的人会发现,代码里面出现了很多的宏定义,那是为了编程的方便,我们会设置一个Reasource.h文件,来统一管理我们的资源。完整的Reasource.h代码在这里贴出:

Reasource.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef REASOURCE_H
#define REASOURCE_H
#define GLUT_KEY_ESCAPE 27
#define RGB(a,b,c) (a/255.0),(b/255.0),(c/255.0) //用于255转0.0-1.0
#define BCR_COLOR RGB(0,0,0) //背景颜色

//所有俄罗斯方块的颜色
#define LL_COLOR RGB(0,255,0)
#define OO_COLOR RGB(255,0,0)
#define DOT_COLOR RGB(255,255,255)
#define II_COLOR RGB(0,255,255)
#define TT_COLOR RGB(164, 225, 202)
#define ELSE_COLOR RGB(0,0,0)
#define WALL_COLOR RGB(100,255,0)

//状态颜色
#define TEXT_COLOR RGB(255,255,255)
#define GAMEOVER_TEXT_COLOR RGB(255,0,0)
#define PB_TEXT_COLOR RGB(0,255,0)

//字体设置
#define INFO_FONT GLUT_BITMAP_TIMES_ROMAN_24

#endif

4.输入回调函数

终于到了激动人心的输入回调函数了,这里将是用户和窗口进行交互的地方,会处理用户所有的键盘敲击。用户的输入的作用是会随着游戏的状态的改变而改变的。在俄罗斯方块中,用户的输入大概有这些

1.WASD
2.UP DOWN LEFT RIGHT

其实我们知道他们是对应相等的。这里我还添加了第三个输入:

3.SPACE

这个SPACE可以干很多事情,比如在游戏运行的时候可以暂停游戏,在游戏暂停的时候可以恢复游戏,在游戏结束的时候可以重置游戏,在游戏准备阶段可以开始游戏。我个人觉得是非常好的一个设计。好了,知道了输入的信息种类,我们来介绍一下glut的消息处理机制。glut中有两种消息的大类型:普通消息和特殊消息

普通消息处理

普通消息的回调函数的绑定是这样的:

1
glutKeyboardFunc(Input);

其中Input函数的声明式这样的:

1
void Input(unsigned char nchar, int x, int y); 

从参数列表中可以看到nchar就是消息的信息,它的类型是unsigned char也就是说它所能承载的消息数量是不多的,包括了大部分的键盘输入但是没有功能键和方向键。所以我们还需要一个特殊消息处理回调函数。

特殊消息处理

与普通消息处理不同的是,特殊消息处理中的nchar参数的类型是int 这允许了它可以包含几乎所有的消息。它的绑定回调函数是这样的:

1
glutSpecialFunc(Input);

回调函数是这样的:

1
void Input( int nchar, int x, int y);

输入信息

我们来分析这个过程,从游戏开始到结束,分别可以接受的输入有哪些。

1.游戏开始前

只能接受一个SPACE信息,然后进入RUN状态。

1
2
3
4
5
6
//处理游戏开始前的输入
if (myGame.status == PRESTART) {
if (nchar == GLFW_KEY_SPACE) {
myGame.Start();
}
}
2.游戏进行中

可以接受移动的信息,以及空格信息进行暂停操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//处理游戏时的输入
if (myGame.status == RUN) {
if (nchar == GLUT_KEY_UP || nchar == GLFW_KEY_W) {
myGame.Rotate();
}
else if (nchar == GLFW_KEY_S || nchar == GLUT_KEY_DOWN) {
myGame.Drop();
}
else if (nchar == GLFW_KEY_A || nchar == GLUT_KEY_LEFT) {
if (myGame.CangetMoveLeft())
myGame.m_tool.MoveLeft();
}
else if (nchar == GLFW_KEY_D || nchar == GLUT_KEY_RIGHT) {
if (myGame.CangetMoveRight())
myGame.m_tool.MoveRight();
}
else if (nchar == GLFW_KEY_SPACE) {
if (myGame.status == GAMEOVER) {
myGame.status = PRESTART;
myGame.reset();
}
else if (myGame.status == RUN) {
myGame.status = STOP;
}
}
}
3.游戏暂停

很简单,接受一个信息SPACE,转换游戏状态为RUN就行。

1
2
3
4
5
6
//处理暂停时的输入
if (myGame.status == STOP ) {
if (nchar == GLFW_KEY_SPACE) {
myGame.status = RUN;
}
}
4.游戏结束

接受一个SPACE信号,把游戏状态转换为PRESTART。

1
2
3
4
5
6
//处理结束的操作
//处理结束的操作
if (myGame.status == GAMEOVER) {
if(nchar==GLFW_KEY_SPACE)
myGame.reset();
}
5.游戏胜利

这个比较模糊,大家自由发挥。)

6.特殊的特殊

在任何状态下,我们都可以使用esc退出游戏,我们把这个输入设置在普通消息中,为了让消息处理看上去更加啊的完整,我们在普通消息处理中调用特殊消息处理函数,使用特殊消息处理函数来处理除esc以外的所有消息。

1
2
3
4
5
6
7
8
9
10
void Input(unsigned char nchar, int x, int y) {
if (nchar == GLUT_KEY_ESCAPE) {
//退出前保存数据
myGame.GameOver();
exit(0);
}
//全部转化为大写进行处理
if (nchar >= 'a' && nchar <= 'z')nchar += 'A' - 'a';
Input((int)nchar, x, y);
}

普通消息处理函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//简单键盘输入
void Input(unsigned char nchar, int x, int y) {
if (nchar == GLUT_KEY_ESCAPE) {
//推出前保存数据
myGame.GameOver();
exit(0);
}
if (nchar >= 'a' && nchar <= 'z')nchar += 'A' - 'a';
Input((int)nchar, x, y);
}
``` 特殊的消息处理函数

```c++
void Input( int nchar, int x, int y){
//处理游戏时的输入
if (myGame.status == RUN) {
if (nchar == GLUT_KEY_UP || nchar == GLFW_KEY_W) {
myGame.Rotate();
}
else if (nchar == GLFW_KEY_S || nchar == GLUT_KEY_DOWN) {
myGame.Drop();
}
else if (nchar == GLFW_KEY_A || nchar == GLUT_KEY_LEFT) {
if (myGame.CangetMoveLeft())
myGame.m_tool.MoveLeft();
}
else if (nchar == GLFW_KEY_D || nchar == GLUT_KEY_RIGHT) {
if (myGame.CangetMoveRight())
myGame.m_tool.MoveRight();
}
else if (nchar == GLFW_KEY_SPACE) {
if (myGame.status == GAMEOVER) {
myGame.status = PRESTART;
myGame.reset();
}
else if (myGame.status == RUN) {
myGame.status = STOP;
}
}
}
//处理暂停时的输入
else if (myGame.status == STOP ) {
if (nchar == GLFW_KEY_SPACE) {
myGame.status = RUN;
}
}
//处理游戏开始前的输入
else if (myGame.status == PRESTART) {
if (nchar == GLFW_KEY_SPACE) {
myGame.Start();
}
}
//处理结束的操作
else if (myGame.status == GAMEOVER) {
if(nchar==GLFW_KEY_SPACE)
myGame.reset();
}
else if (myGame.status == GAMEWIN) {
if (nchar)exit(0);
}
}

这样,我们的消息处理就完整啦!!(快要做完了!!好激动)

菜单(非必要)

创建菜单

做完上面的内容之后,我觉得我的小游戏还是少了些什么东西,它好像不能存档,它好像没有菜单,它好像很垃圾??然后我就给它加上了几行代码,使得这个小游戏 更加的有意思了。我们可以在菜单对游戏进行重置,我们可以在提供的三个存档位中进行选择,我们可以在正常退出时保存数据,下次打开自动保存存档又能回到之前的进度!

关于glut的Menu

首先我们需要做的是创建一个菜单,glut提供的注册函数是glutCreateMenu()


1
extern int APIENTRY glutCreateMenu(void (*)(int));

它会返回所创建的菜单的ID,类型是int。
然后是创建这个ID下的菜单列表,使用函数:glutAddMenuEntry()


1
extern void APIENTRY glutAddMenuEntry(const char *label, int value);

需要一个执行操作的函数,和一个对应执行的“值”,这个值我们一般使用枚举来提高代码可读性。

点击返回问题目录
然后我们可以使用一个菜单的ID去创建一个父菜单,像这样:
image
使用函数glutAddSubMenu()


1
extern void APIENTRY glutAddSubMenu(const char *label, int submenu);

点击返回问题目录
最后,我们需要绑定菜单触发的输入,比如GLUT_RIGHT_BUTTON,就是鼠标右键。

响应菜单

在创建菜单的时候,会将子菜单绑定到一个函数上,这个函数需要接受一个value值,然后处理对应的操作。这里先给出createGLUTMenus函数的定义:

createGLUTMenus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void createGLUTMenus() {
//菜单ID
int menu,submenu, Savemenu, Loadmenu;
//设置回调函数processMenuEvents(),获取与之对于的菜单ID
submenu = glutCreateMenu(processMenuEvents);
glutAddMenuEntry("Start", RUN);
glutAddMenuEntry("Reset", PRESTART);
//以后再做
//glutAddMenuEntry("Check My Best", CHECKBEST);
Savemenu = glutCreateMenu(processMenuEvents);
glutAddMenuEntry("Save1", SAVE1);
glutAddMenuEntry("Save2", SAVE2);
glutAddMenuEntry("Save3", SAVE3);
Loadmenu = glutCreateMenu(processMenuEvents);
glutAddMenuEntry("Load1", LOAD1);
glutAddMenuEntry("Load2", LOAD2);
glutAddMenuEntry("Load3", LOAD3);
glutAddMenuEntry("LoadAutoSave", LOADAUTOSAVE);
menu = glutCreateMenu(processMenuEvents);
//设置父菜单
glutAddMenuEntry("Stop", STOP);
glutAddSubMenu("Option", submenu);
glutAddSubMenu("Save", Savemenu);
glutAddSubMenu("LoadSave", Loadmenu);
glutAddMenuEntry("Exit", GAMEOVER);
//绑定鼠标点击
glutAttachMenu(GLUT_RIGHT_BUTTON);
}

然后我们定义在createGLUTMenus中使用过的函数指针processMenuEvents。在这个函数中,我们对应各个枚举进行实现。

processMenuEvents

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void processMenuEvents(int option) {
switch (option) {
case RUN:
if (myGame.status == PRESTART)myGame.Start();
myGame.status = RUN;
break;
case GAMEOVER:
myGame.GameOver();
myGame.Save("AutoSave.zhywyt");
exit(0);
break;
case PRESTART:
myGame.status = PRESTART;
myGame.GameOver();
myGame.reset();
//添加重置的操作
break;
case STOP:
if(myGame.status!=PRESTART)
myGame.status = STOP;
break;
}
if (option >= SAVE1 && option <= SAVE3) {
if (myGame.getStatus() != PRESTART) {
int index = option - SAVE1 + 1;
char FileName[30];
sprintf(FileName, "Save%d.zhywyt", index);
string name(FileName);
if (myGame.Save(name))
myGame.ChangeStatus(STOP);
}
}
else if (option >= LOAD1 && option <= LOAD3) {
int index = option - LOAD1 + 1;
char FileName[30];
sprintf(FileName, "Save%d.zhywyt", index);
string name(FileName);
if(myGame.Load(name))
myGame.ChangeStatus(STOP);
else {
myGame.reset();
myGame.ChangeStatus(PRESTART);
}
}
else if (option == LOADAUTOSAVE) {
if(myGame.Load("AutoSave.zhywyt"))
myGame.ChangeStatus(STOP);
}
}

存档(非必要)

前面的菜单里面,有着需要Game类内部实现的存档系统,那么我们来稍微修改一下Game类,为它添加存档的功能。

Save函数和Load函数

1
2
bool Save(string FileName);
bool Load(string FileName);

实现:

Save

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool Game::Save(string FileName) {
ofstream ofs(FileName, fstream::out);
if (ofs) {
//按照数据顺序来
ofs << status << " " << clearTimes << " "
<< zhywyt << " " << _points << " "
<< PB_points << " " << Diff << " "
<< PB_Diff << " " << PB << endl;
ofs << m_tool._type << " " << m_next._type << endl;
for (int i = 0; i < Row; i++) {
for (int j = 0; j < Cow; j++)
ofs << m_map[i][j] << " ";
ofs << endl;
}
return true;
}
return false;
}
``` Load

```c++
bool Game::Load(string FileName) {
ifstream ifs(FileName, fstream::in);
if (ifs) {
int Status, m_tool_Type, m_next_Type;
ifs >> Status >> clearTimes
>> zhywyt >> _points
>> PB_points >> Diff
>> PB_Diff >> PB
>> m_tool_Type >> m_next_Type;
for (int i = 0; i < Row; i++)
for (int j = 0; j < Cow; j++)
ifs >> m_map[i][j];
status = GameMode(Status);
m_tool = Tool(rePx,rePy,ToolType(m_tool_Type));
m_next = Tool(waitPx, waitPy, ToolType(m_next_Type));
return true;
}
return false;
}

自动存档

在用户是哟esc进行退出时,和使用exit进行退出时,我们先保存一次游戏的数据,再退出,这样可以让用户在下次进入游戏的时候找回之前忘记保存的存档。我们更新之前的普通消息处理函数:

1
2
3
4
5
6
7
8
9
10
11
12
void Input(unsigned char nchar, int x, int y) {
if (nchar == GLUT_KEY_ESCAPE) {
//退出前保存数据
myGame.GameOver();
//真正的保存数据
myGame.Save("AutoSave.zhywyt");
exit(0);
}
//全部转化为大写信息处理
if (nchar >= 'a' && nchar <= 'z')nchar += 'A' - 'a';
Input((int)nchar, x, y);
}

最后,要注意存档不存在的时候,这里我就没有进行额外的处理了,只是在没有存档的时候不做任何事情。

更新于2023.4.15

音乐

一个游戏不能没有音乐,或者说一个完整的游戏不能没有音乐,所以我还是给我的俄罗斯方块小游戏加上了音乐。

irrklang

因为OpenGL是没有提供音频的接口的,所以我需要使用外部库来实现音乐部分。这里使用的是irrklang音频库,它可以非常方便的使用多种文件的音频。可以在这里找到它的下载链接

irrKlang我使用了32位进行实现。下载好后按照之前配置glut的方式配置irrklangglut的配置

irrklang使用

irrklang可以实现3D音效,但是我们这里不需要用到这个高级的方法。我们只使用它的2D效果。主要介绍它的两个类:

ISoundEngine类

ISoundEngine类允许我们创建一个可以播放音乐的对象,这个对象由函数createIrrKlangDevice得到。

1
ISoundEngine* SoundEngine = createIrrKlangDevice();

ISoundEngine类拥有很多的成员函数,我们需要使用的只有两个,分别是:

1
2
3
4
5
6
7
8
9
10
SoundEngine->play2D();
SoundEngine->drop();
//函数原型
virtual ISound* play2D(const char* soundFileName,
bool playLooped = false,
bool startPaused = false,
bool track = false,
E_STREAM_MODE streamMode = ESM_AUTO_DETECT,
bool enableSoundEffects = false) = 0;

drop函数很单纯,就是释放这个ISoundEngine对象的内存,销毁该对象。在程序退出前记得调用这个函数;而play2D这个函数使用了大量的默认形参,所以我们甚至可以简洁的写成:SoundEngine->play2D("Filename")这样简单的代码直接播放一首歌曲。它第二个参数的意义是是否进行循环播放,第三个参数的意义是第一次触发是否暂停播放,等待第二次触发再播放,第四个参数是是否返回ISound指针。后面的参数我们用不到了。我们可以得到两种使用方式,分别对应我们的背景音乐和音效。

1
2
3
4
5
6
//BackGroundMusic背景音乐
//需要持续播放且进行"track"的的音乐
ISound*BackGroundSound SoundEngine->play2D("filename",GL_TRUE,GL_FALSE,GL_TRUE);
//音效
//只需要当前位置播放一次的音乐
SoundEngine->play2D("filename");

然后我们来讲一下ISound类,它可以对一段音乐的播放进行更加细致的操纵。

ISound类

ISound类对象的指针由play2D开启第四个参数时返回,得到的ISound对象可以对这首音乐进行操纵,比如暂停、调节音量、释放空间等等。这里我们只需要用到暂停和释放空间就行了。我们用到它的两个成员函数

1
2
3
4
5
6
7
//开启音乐播放
//TRUE暂停
BackGroundMusic->setIsPaused(GL_FLASE);
//销毁音乐,之后置空
BackGroundMusic->drop();
//设置音量(0.0 - 1.0)
RunSound->setVolume(value);

2023.4.15更新至此

点击返回问题目录

一个游戏的开发过程主要有哪些呢?

以下全部都是个人见解,肯定是非常不全面的,但是既然是自己第一个完整的游戏,那么也把整个开发过程的想法说一说。

1.分析游戏对象

想要做一个游戏,首先我们得知道这个游戏会有哪些对象,先从对象入手。把对象作为我们游戏的最小单元,比如游戏中的NPC,我们可能先剥离所有NPC的共性,然后写出一个基类people类,再people这个类的基础上进行继承,形成新的类,逐渐完善所有的对象类。我觉得这个步骤至关重要,也能理解为什么策划在团体中的重要性了。

2.分析游戏过程

在我自己的想法中,我还是不能把Game类和过程剥离开,整个Game类的设计还是在进行一种面向过程的编程方式,但是我觉得面向对象的意义其实就是更好的面向过程,我无法想象如何真正意义上的面向对象?我的绘图,我的消息处理,甚至我的Timer计时器,从里到外都透露着面向过程的思想。但是就这一个俄罗斯方块来说,我觉得我的处理还是很正确的,以友元作为回调函数,设置唯一的Game类。但是转念一想,那我的Game类有什么意义呢?认真的思考过后,我认为:这个游戏中对对象的封装止步于Game类的数据维护,剩下的所有事情都是在面向过程。

3.代码实现

涉及到的知识就很多了,包括C++的编程基础和图形API/库的接口使用。

感谢您的阅读,谢谢!

有什么问题请大家狠狠的指出,大家的意见都是小白在学习中的一次进步!代码多有不规范的地方还请大家包涵。

代码汇总

zhywyt

Games101笔记 P11~?

贝塞尔曲线(Bezier Curve-General Algebraic Formula)

三个点的贝塞尔曲线迭代公式:

\[b^1_0(t)=(1-t)b_0+tb_1 \]

\[b_1^1(t)=(1-t)b_1+tb_2 \]

\[b_0^2(t)=(1-t)b_0^1+tb_!^1 \]

展开得到

\[b^2_0(t)=(1-t)^2b_0+(1-t)tb_1+t^2b_2 \]

n个控制点的贝塞尔曲线,每一个时刻曲线上的点的坐标,可以通过二项式展开得到。

\[b^n(t)=b_0^n(t)=\sum^n_{j=0}b_j B^n_j(t) \]

其中\(B^n_j(t)\)就是伯恩斯坦多项式,也就是二项式展开的系数,写作:

\[B_i^n(t)=(n,i)^Tt^i(1-t)^{n-1}={C_n^i}t^i(1-t)^{n-i} \]

用语言表述就是,用伯恩斯坦系数给各个控制点加权得到贝塞尔曲线的解。

优美的性质->1.线性不变:贝塞尔曲线只需要记录控制点的位置,在线性变换下,对控制点进行变换之后重新生成的曲线与直接对曲线进行变换得到的曲线相同。
2.凸包性:贝塞尔曲线一定在控制点形成的凸包内。

逐段的贝塞尔曲线

因为在控制点很多的时候,每一个控制点对曲线的影响很小了,人们更趋向于使用较少的控制点和较多的贝塞尔曲线,来刻画曲线,一般使用四个控制点来处理一段曲线,然后把各段曲线连起来,可以得到不错的效果。
image
当一条贝塞尔的曲线的终点和另一条贝塞尔曲线的起点重合时即\(a_n=b_0\),我们叫它\(C_0\)连续。也就是函数连续。
image
在\(C_0\)连续的情况下,当一条贝塞尔曲线的终止向量的和另一个贝塞尔曲线的起始向量反向相等时,我们称之为\(C_1\)连续。理解起来就是这条曲线在这点导数连续。
image

Bezier Surfaces(贝塞尔曲面)

用四条贝塞尔曲线的点当作四个控制点,再生成一条贝塞尔曲线,然后遍历之前的贝塞尔曲线,就可以得到贝塞尔曲面。
如图,四个贝塞尔曲线上的点形成了新的控制点,然后绘制新的贝塞尔曲线。
image
最后形成贝塞尔曲面:
image

网格细分(Mesh Subdivision)

一、Loop Subdivision(发明人叫Loop和循环没关系)

对新顶点

通过提高三角形的数量来提高模型的质量,把一个三角形分成等大的四块三角形。对于一般情况添加的点来说它会由两三角形所共享,那么这个点就可以由已知的两个三角形所确定。具体就是取加权平均数。

\[E=\frac{3}{8}(A++B)+\frac{1}{8}(C+D) \]

其中E点就在AB线段上,C、D就是两个三角形的另外两个顶点。
image

对旧的顶点

对于旧的顶点,参考周围的老的顶点,按照“度”(就是一个节点与周围的连线的数量)来进行加权平均,当然旧的点也需要参考自己的坐标。
image
其中 u 就是旧节点的度,这里是6。u 就是需要周围点的权值,参考度来生成。除去周围节点的权值,剩下的就是旧节点自己所占的权值了。

二、Catmull-Clark Subdivision(General Mesh)

Loop Subdivision只能处理三角形网格,Catmull则可以细分四边形网格。

定义

Non-quad face——非四边形面
Extrordinary vertex(degree!=4)——奇异点(度不等于4的点)
image

操作

在每一条边上取中电,每一个面上取中点,然后把这些点连起来,增加面密度。
image
经过一次操作,把所有的非四边形面变成了奇异点,使得所有的面都是四边形面,又因为非四边形面细分之后得到奇异点,所以在第一次细分之后不会再出现非四边形面。

点的更新

第一类:四边形中间的点(Face Point)

直接取顶点的平均即可
image

第二类:在边上的点(Edge Point)

参照构成该边的两个点和附近两个区域的内点进行平均(无视图中的f )
image

第三类:顶点(Vertex Point)

使用周围的八个点和自身,进行加权平均计算
image

网格简化(Mesh Simplification)

目的

Goal : reduce number of mesh elements while maintaining the overall shape.
在保证模型不走样的情况下,减少网格元素。

edge collapsing 边塌缩

边塌缩不是随便删除点就行,需要进行二次度量误差Quadric Error Metrics

Quadric Error Of Edge Collapse 二次度量误差

计算二次度量误差,给每一个边进行二次度量误差检查,给每一个边进行计算,得到一个二次度量误差。从二次度量误差最小的开始。然后每次塌缩最小的一条边,再更新被影响的边。

Shadows(阴影)

Shadow Mapping

只能处理点光源

Key idea 中心思想

如果一个点不在阴影里面,那么这个点可以被光源看到,也可以被相机看到。

Pass1 :Render from Light 从光源进行光栅化

>Depth image from light sourse 从光源进行光栅化,记录点的深度
image

Pass2A:Render from eye

从摄像机进行光栅化
image

Pass2B:Project to light

把摄像机中的点和这个点对于光源的深度和之前光源光栅化记录的深度进行比较,如果深度一样,说明这个点是可见的,可以被光源和摄像机同时看到。但是如果深度不一样,如图红色的深度是对于光源的深度,蓝色的深度是记录的深度,但深度大于记录的深度时,说明这个点无法被光照到。
image

Problems with shadow maps

shadow maps只能做硬阴影,也就是说阴影要么是黑,要么是白,但是现实生活中是软阴影,因为非点光源导致的影子是存在本影和伴影,所以Shadow maps 只能做点光源的阴影,但是不能做立体光源的阴影,也就是软阴影。
image

Ray Tracing 光线追踪

Why Ray Tracing?

Rasterization could’t handle global effects well
光栅化不能很好的表现全局的效果

And especially when the light bounces more than once
光栅化无法很好的处理光线在场景中反射了不止一次的情况

(Soft)shadows 不能很好的表示和软阴影
Glossy reflection 光泽反射
indirect illumination 间接光照
image
光栅化在处理多次反射的时候会比较麻烦,而且不能保证物理上的正确性。相当于光珊化是一种快速的近似。而光线追踪是非常非常慢的,很真实的图形,一般用于离线,比如动画的渲染。

Basic Ray-Tracing Algorithm

Light Rays 光线

Three ideas about light rays
1.Light travels in straight lines 光线沿直线传播
2.Light rays do not “collide” with each other if they cross 光路互不干扰
(though are wrong)
3.Light rays travel from the light sources to the eye(光路可逆)

Ray Casting 光线投射

1.Generate an image by casting one ray per pixel通过每像素投射一条光线来生成图像
2.Check for shadows by sending aray to the light通过向灯光发送光线来检查阴影
image
在光线投射中,记录每一根光线碰到的第一个物体closest scene,那么就完美的解决了深度测试的问题,不需要再考虑深度测试。
image
找到一个交点之后,我们考虑这个点会不会被照亮,然后从这个点连一条线到光源,如果路径上没有阻挡,那么就可以说明这点被光照亮了,再利用法线进行着色Shading
image
这种方法光线还是只反射了一次。

Recursive(Whitted-Style) Ray Tracing

在光线投射的基础上,我们把从像素出发的点在碰到物体之后进行反射和折射。
image
最后的着色则由各个点的着色的加权叠加组成,每一个点都需要计算它的shadow ray
image

问题一:Ray-Surface Intersection(交点)

Ray is defined by its origin and a directino vector
光线定义为一个起点和一个方向向量

光线的方程:

\[Ray: r(t)=o+td,0<t< \infty \]

与最简单的图形球的交:

球:

\[p:(p-c)^2-R^2=0 \]

若相交,那么交点会满足两个方程,我们把光线的方程带入球的方程:

\[(o+td-c)^2-R^2=0 \]

然后解时间t,需要满足:
1.t是正的
2.t不是虚数
3.t得是最小的

与隐式表面的交:

隐式表面就是L:\(p:f(p)\)表示的一个方程
带入得到:

\[f(o+td)=0 \]

同样的需要满足,t是正的,t不是虚数
目前的求根的方法已经很发达了,所以求根不是问题

怎么计算交点?

Simple idea:jusr intersect ray with each triangle
直接计算每一个三角形与光线是否相交。(很慢,但有效)

把问题分解为两个小的问题:
1.光线经不经过三角形所在平面
2.光线与平面的交点在不在三角形内

三角形所在平面

点法式
平面方程为

\[(P-P’)\cdot N=0 \]

求交点

简单的方法

\[(o+td-P’)\cdot N=0 \]

\[t=\frac{(P’ -o)\cdot N}{d\cdot N} \]

Check:$0<t<\infty $

交点是不是在三角形内

交点与顶点构成的向量与边的向量进行叉乘

快速的方法

一步到位 Moller Trumbore Algorithm

其中\(\vec O+t\vec D\)就是光线的位置,如果在三角形内,那么一定可以用三角形的重心公式写出来,又这是三维向量,那么就是三个未知数,三个方程,可以直接解线性方程组,就能判断是否相交。甚至可以直接计算行列式来进行在否的判断,而不需要计算点的具体位置。用到克莱默法则
image

问题二:加速求交(从三角形数量上)

Bounding Volumes 包围盒

1.Object is fully contained in the volume.
2.If it doesn’t hit the volume, it doesn’t hit the object.
3.So test BVol first, then test object if it hits.
如果碰不到包围盒,那么肯定碰不到物体,所以首先测试包围盒,如果能碰到包围盒,再测试物体本身。

Axis-Aligned Bounding Box,使用三个对面来唯一确定一个长方体,使用AABB来当作包围盒,与光线进行求交。在二维时候,对于两个对面,我们可以计算出光线进入面和出面的时间(可能为负数),把光线和经过的两个线段求交集,得到的就是光线进入和出去光线的路径。
image
拓展到三维:只有当光线进入了所有的三个对面后,再出某一个对面。也就是光线进入三个对面的时间都小于离开任意一个对面的时间。也就是最大的进入时间小于最小的离开时间时,说明光线进入了AABB。
image
得到光线与AABB有交点:
image
为什么使用AABB?计算简单
image

Preprocess - Build Acceleration Grid

通过画小网格,来细分包围盒。找出可能有物体(边缘)的格子,然后进行光线追踪。
image
image
那么对于划分格子也相当有技术,太稀疏和太密集都不太好,一般使用物体的数量乘以27(虽然没什么意义hh)
image

Spatial Partitions

空间划分,因为空旷的地方出现一个小的物体,会导致网格划分非常的低效。使用空间划分来解决这个问题。
image
第一个是八叉树,进行细分,并且给一个停止细分的规则,比如格子中的物体数量小于某个数。但是八叉树的性质不好,因为细分度和维度呈几何次数上升。2 4 8

第二个是每一次只在格子里沿着某一个轴,进行划分,但是保证划分是交替出现,x\y\z。这么进行不会导致非常高的复杂度,而且保存了二叉树的原理。

第三个是BSP树,不满足AABB

我们主要学习KD-Tree
image
进行空间划分,但是对于左边的蓝也需要进行相同弄的操作。会形成一棵二叉树。实际的数据只存储在叶子节点上。进行计算时,首先对最大的包围盒进行计算:
image
image
发现光线和左边的叶子节点有交点,那么开始计算光线和左边包围盒中的物体进行求交。
image
然后继续搜索。计算所有和光线相交的叶子节点。
问题出现了,两个包围盒会同时包括一个物体,那么会产生极大的消耗。使用BVH(Bounding Volume Hierarchy)来解决这个问题。在KD的基础上,进行优化不再划分空间,而是对物体进行划分:把物体分为两堆,然后对物体堆进行包围盒的计算。
image
但是BVH划分的包围盒存在相交,这也是另一个问题,但是比KD-Tree得到的划分更加的好。BVH的怎么划分就成了重要的问题。
BVH的划分:
把三角形进行排序,然后取中间的三角形进行划分,可以使得这个树更加的平衡,也就意味着树的深度可以达到最小。算法:
给一列n个的数,你要找第i大的数,你可以在o(k)进行处理(快速选择算法)。BVH的递归算法:(伪代码)
image
KD-Tree与BVH
image

Basic radiometry(辐射度量学)

快速读入模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define New int
inline New read()//快速读入
{
New X = 0, w = 0;
char ch = 0;
while (!isdigit(ch))
{
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
char F[200];
inline void write(New x) //快速输出
{
if (x == 0)
{
putchar('0');
return;
}
New tmp = x > 0 ? x : -x;
int cnt = 0;
if (x < 0)
putchar('-');
while (tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(F[--cnt]);
}

c语言文件读写

C语言文件读写

算法

1.fseek()函数

此函数用于移动文件指针到指定位置。例如,要将文件指针移动到文件的第5个字节处,您可以使用以下代码:

1
fseek(fp, 5, SEEK_SET); // 将文件指针移动到第5个字节

其中,第二个参数是移动的字节数,第三个参数指定移动的起始位置。

2.ftell()函数

此函数用于获取文件指针的当前位置。例如:

1
2
long pos;
pos = ftell(fp); // 获取当前位置

此函数返回一个长整型值,表示文件指针的当前位置。

3. freopen()函数

此函数用于重新打开文件,并将其关联到另一个文件流。例如,要将文件指针fp关联到一个名为”output.txt”的文件,您可以使用以下代码:

1
fp = freopen("output.txt", "w", stdout); // 将stdout(标准输出)关联到output.txt文件

此函数将文件指针fp重新打开,并将其与stdout流关联,以便将输出写入文件而不是控制台。

4. remove()函数

此函数用于删除指定的文件。例如,要删除名为”example.txt”的文件,您可以使用以下代码:

1
remove("example.txt"); // 删除文件

5.rename()函数

此函数用于重命名文件。例如,要将名为”oldname.txt”的文件重命名为”newname.txt”,您可以使用以下代码:

1
rename("oldname.txt", "newname.txt"); // 重命名文件

6.temfile()函数

此函数用于创建一个临时文件。例如,要创建一个临时文件,您可以使用以下代码:

1
2
FILE *fp;
fp = tmpfile(); // 创建临时文件

该函数将创建一个二进制文件,并返回一个指向该文件的文件指针。当程序退出时,临时文件将自动被删除。

7.setbuf()函数

此函数用于为文件流设置缓冲区。例如,要为文件指针fp设置一个8192字节的缓冲区,您可以使用以下代码:

1
2
char buffer[8192];
setbuf(fp, buffer); // 为文件流设置缓冲区

8.fflush()函数

此函数用于将缓冲区中的数据写入文件。例如,要将文件指针fp的缓冲区中的数据写入文件,您可以使用以下代码:

1
fflush(fp); // 将缓冲区中的数据写入文件

文本文件

1. fopen()函数

此函数用于打开文件,并返回一个文件指针。您可以使用文件指针来读取或写入文件。例如,要打开一个名为”example.txt”的文件,您可以使用以下代码:

1
2
FILE *fp;
fp = fopen("example.txt", "r"); // 打开文件

2. fclose()函数

此函数用于关闭文件。当您完成对文件的操作时,应使用fclose()函数将其关闭。例如:

1
fclose(fp);// 关闭文件

3. fgetc()函数

此函数用于从文件中读取一个字符。例如:

1
2
int c;
c = fgetc(fp); // 读取一个字符

4. fputs()函数

此函数用于将一个字符写入文件。例如:

1
fputc('A', fp); // 将字符'A'写入文件

5. fgets()函数

此函数用于从文件中读取一行文本。例如:

1
2
char buf[100];
fgets(buf, 100, fp); // 读取一行文本

6. fputs()函数

此函数用于将一行文本写入文件。例如:

1
fputs("Hello, world!", fp); // 将一行文本写入文件

7.fprintf()函数

此函数用于将格式化的文本写入文件。例如:

1
2
int x = 10;
fprintf(fp, "The value of x is %d", x); // 将格式化的文本写入文件

二进制文件

1. fread()函数

此函数用于从文件中读取一定数量的数据。例如,要从文件中读取10个整数,您可以使用以下代码:

1
2
int data[10];
fread(data, sizeof(int), 10, fp); // 读取10个整数

其中,第一个参数是数据的存储位置,第二个参数是数据类型的大小,第三个参数是要读取的数据数量,第四个参数是文件指针。

2.fwrite()函数

此函数用于将一定数量的数据写入文件。例如,要将10个整数写入文件,您可以使用以下代码:

1
2
int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
fwrite(data, sizeof(int), 10, fp); // 写入10个整数

康托展开

康托展开

名词解释:

康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。
-–康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。

原理介绍

\(X = a_{n}(n-1)!+a_{n-1}(n-2)!+… +a_{1} \times 0!\)
其中,\(a_i\) 为整数,并且\(0\leq a_{i}<i,1\leq i\leq n\) 。
表示原数的第i位在当前未出现的元素中是排在第几个
康托展开的逆运算
既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出n的全排列中第x大排列。
如n=5,x=96时:
首先用96-1得到95,说明x之前有95个排列.(将此数本身减去1)用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4.用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5.用5去除2!得到2余1,类似地,这一位是3.用1去除1!得到1余0,这一位是2.最后一位只能是1.所以这个数是45321。
按以上方法可以得出通用的算法。{^1}

康托展开

再举个例子说明。
在{\({1, 2, 3, 4,5}\)}5个数的排列组合中,计算\(34152\)的康托展开值。
首位是\(3\),则小于\(3\)的数有两个,为\(1\)和\(2\),\(a[5]=2\),则首位小于3的所有排列组合为\(a[5]\times (5-1)!\)
第二位是4,由于第一位小于\(4\),{\({1,2,3}\)}中一定会有\(1\)个充当第一位,所以排在\(4\)之下的只剩\(2\)个,所以其实计算的是在第二位之后小于\(4\)的个数。因此\(a[4]=2\)。
第三位是1,则在其之后小于1的数有0个,所以\(a[3]=0\)。
第四位是5,则在其之后小于5的数有1个,为2,所以\(a[2]=1\)。
最后一位就不用计算啦,因为在它之后已经没有数了,所以\(a[1]\)固定为0
根据公式:

\[X=2\times 4!+2\times 3!+0\times 2!+1\times 1!+0\times 0!=61 \]

所以比34152小的组合有61个,即34152是排第62。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
const int factorial[]={1,1,2,6,24,120,720,5040,40320,362880,3628800};//阶乘0-10
int cantor(int a[],int n){//cantor展开,n表示是n位的全排列,a[]表示全排列的数(用数组表示)
int ans=0,sum=0;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++)
if(a[j]<a[i])
sum++;
ans+=sum*factorial[n-i];//累积
sum=0;//计数器归零
}
return ans+1;
}
int main(){
int sb[12],gs;
cin>>gs;
for(int i=1;i<=gs;i++)
cin>>sb[i];
cout<<cantor(sb,gs);//输出该集合在全排列所在位置
return 0;
}

康托逆展开

一开始已经提过了,康托展开是一个全排列到一个自然数的双射,因此是可逆的。即对于上述例子,在给出61可以算出起排列组合为34152。由上述的计算过程可以容易的逆推回来.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
//康托展开逆运算
void decantor(int x, int n)
{
vector<int> v; // 存放当前可选数
vector<int> a; // 所求排列组合
for(int i=1;i<=n;i++)
v.push_back(i);
for(int i=n;i>=1;i--)
{
int r = x % FAC[i-1];
int t = x / FAC[i-1];
x = r;
sort(v.begin(),v.end());// 从小到大排序
a.push_back(v[t]); // 剩余数里第t+1个数为当前位
v.erase(v.begin()+t); // 移除选做当前位的数
}
}

就到这里啦!

P1088 [NOIP2004 普及组] 火星人

[NOIP2004 普及组] 火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为 \(1,2,3,\cdots\)。火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 \(1,2,3,4\) 和 \(5\),当它们按正常顺序排列时,形成了 \(5\) 位数 \(12345\),当你交换无名指和小指的位置时,会形成 \(5\) 位数 \(12354\),当你把五个手指的顺序完全颠倒时,会形成 \(54321\),在所有能够形成的 \(120\) 个 \(5\) 位数中,\(12345\) 最小,它表示 \(1\);\(12354\) 第二小,它表示 \(2\);\(54321\) 最大,它表示 \(120\)。下表展示了只有 \(3\) 根手指时能够形成的 \(6\) 个 \(3\) 位数和它们代表的数字:

三进制数 代表的数字
\(123\) \(1\)
\(132\) \(2\)
\(213\) \(3\)
\(231\) \(4\)
\(312\) \(5\)
\(321\) \(6\)

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 \(N\),表示火星人手指的数目(\(1 \le N \le 10000\))。
第二行是一个正整数 \(M\),表示要加上去的小整数(\(1 \le M \le 100\))。
下一行是 \(1\) 到 \(N\) 这 \(N\) 个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。

输出格式

\(N\) 个整数,表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开,不能有多余的空格。

样例 #1

样例输入 #1

1
2
3
5
3
1 2 3 4 5

样例输出 #1

1
1 2 4 5 3

提示

对于 \(30\%\) 的数据,\(N \le 15\)。

对于 \(60\%\) 的数据,\(N \le 50\)。

对于 \(100\%\) 的数据,\(N \le 10000\)。

noip2004 普及组第 4 题

这题可以用到康托展开->https://www.cnblogs.com/zhywyt/p/17090301.html,但是这里并不像展开说明康托展开,只把他当作一个理论基础来完成这个模拟题

由康托展开我们可以知道:康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。,那么我们就可以先把外星人的排列映射成一个数的序列,这个序列是可以和自然数进行加减的,所以可以很方便的完成本题的要求.

映射方法:

对于一个序列,比如\({1, 3, 2, 4, 5}\)
第一个数\(1\),是数列{\({1, 2, 3, 4, 5}\)}中的第一个,所对应的值就是\(0\)
第二个数\(3\),是数列{\({2, 3, 4, 5}\)}中的第二个,所对应的值也就是\(1\)
第三个数\(2\),是数列{\({2, 4, 5}\)}中的第一个,所对应的值也就是\(0\)
以此类推
得到最后的映射就是{\({0,1,0,0,0}\)}

1
关于这个映射, 有一个和进制规则在里面: 从右往左, 序列的下标代表该位数字的进制, 比如这里的$1$, 就是4进制数, 所以这个序列代表的十进制数就是3.
序列长度 \(n=5\)
映射序列数 进制 index
0 5 0
1 4 1
0 3 2
0 2 3
0 1 4

所以代表的进制就等于\(n-index\)

这样我们就有了\(to()\)方法和\(back()\)方法了!

\(to()\)方法

1
2
3
4
5
6
7
8
9
10
11
void to() {
int sum = 0;
for (int i = 0; i < n-1; i++) {
for (int j = i + 1; j < n; j++)
if (str[j] < str[i])
sum++;
sav[i] = sum;
sum = 0;
}
}

\(back()\)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void back() {
memset(via, 0, sizeof(int) * n);
for (int i = 0; i < n; i++) {
int index = 0;
while (via[index])index++;
for (int j = 0; j < sav[i]; j++) {
do {
index++;
} while (via[index]);
}
via[index] = 1;
str[i] = index +1;
}
}

中途一个进位的小函数就不再复述了,没有什么难度.
最后奉上完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <fstream>

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n, m;
int str[10010],sav[10010];
int via[10010];
void to();
void back();
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> str[i];
}
to();
sav[n - 1] += m;
int jin = 0;
for (int i = 1; i <= n; i++) {
sav[n - i] += jin;
jin = sav[n - i] / i;
sav[n - i] %= i;
}
back();
cout << str[0];
for (int i = 1; i < n; i++) {
cout << " " << str[i];
}
cout << endl;
return 0;
}
void to() {
int sum = 0;
for (int i = 0; i < n-1; i++) {
for (int j = i + 1; j < n; j++)
if (str[j] < str[i])
sum++;
sav[i] = sum;
sum = 0;
}
}
void back() {
memset(via, 0, sizeof(int) * n);
for (int i = 0; i < n; i++) {
int index = 0;
while (via[index])index++;
for (int j = 0; j < sav[i]; j++) {
do {
index++;
} while (via[index]);
}
via[index] = 1;
str[i] = index +1;
}
}
|