每周总结#3

游戏引擎

跟了个油管的博主，动手实现自己的game engine。

premake.lua

一个构建系统，相对cmake简单许多。

links ：这个命令是我一开始不太清楚的。因为在我们的解决方案中，我们实际上将游戏引擎和Sandbox作为两个项目，让游戏引擎engine这个项目的最终文件是个动态链接库（windows是.dll），运行时和sandbox生成的.exe文件放在一块。

事实上如果用premake构建vs项目，links其实是对于一个项目创建了另一个项目的引用，而不是链接了一些库。引用是告诉链接器，某些符号是可以使用的，但是它的具体实现在dll文件里（因此有必要运行一些复制dll到指定路径的命令）。

defines：定义一些宏，这些宏在对应的项目中可以使用。

例如针对dll的导出导入符号：

1
2
3
4
5
6
7
8
9

#ifdef E_PLATFORM_WINDOWS
	#ifdef E_BUILD_DLL
		#define E_API __declspec(dllexport)
	#else
		#define E_API __declspec(dllimport)
	#endif
#else
	#error only windows!
#endif

我们可以在构建文件中，针对设备的系统，以及项目，定义一些特定的宏。

事件系统

目前的Event System都是Block的，就是对于事件的执行都是立刻的，会阻塞当前线程。

考虑如何设计，首先我们很容易想到用enum或enum class来设置事件的种类，类型。

然后设置Event基类，后续具体的事件继承这个类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class E_API Event
{
	friend class EventDispatcher;
public:
	virtual EventType GetEventType() const = 0;
	virtual const char* GetName() const = 0;
	virtual int GetCategoryFlags() const = 0;
	virtual std::string ToString() const { return GetName(); }

	inline bool IsInCategory(EventCategory category)
	{
		return (GetCategoryFlags() & category);
	}
private:
	bool m_Handled = false;
};

由于事件很多，对于每一个子类都要重写方法很累，因此有个比较骚的操作就是将重写的内容用宏替代：

1
2
3
4
5

#define EVENT_CLASS_CATEGORY(category) virtual int GetCategoryFlags() const override { return category; }

#define EVENT_CLASS_TYPE(type) static EventType GetStaticType() { return EventType::##type; } \
								virtual EventType GetEventType() const override { return GetStaticType(); } \
								virtual const char* GetName() const override { return #type; }

EventType::##type 中的 ## 是预处理操作符，用于将宏参数 type 与 EventType:: 连接起来。例如，如果 type 是 Mouse，那么 EventType::##type 就会被展开为 EventType::Mouse。 return #type; 中的 # 是字符串化操作符，将宏参数转换为字符串。如果 type 是 Mouse，那么 #type 就会被展开为 "Mouse"。

然后在类里面根据具体事件类型进行宏展开。

事件分发器，这个东西负责将其对应的事件传到某个函数进行执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class EventDispatcher
{
	template<typename T>
	using EventFn = std::function<bool(T&)>;
public:
	EventDispatcher(Event& event)
		: m_Event(event)
	{
	}

	template<typename T>
	bool Dispatch(EventFn<T> func)
	{
		if (m_Event.GetEventType() == T::GetStaticType())
		{
			m_Event.m_Handled = func(*(T*)&m_Event);
			return true;
		}
		return false;
	}
private:
	Event& m_Event;
};

std::function 我并不是很熟悉（虽然见过好多次了），暂且将其理解为函数指针。然后对于这里强制转换：func(*(T*)&m_Event)，个人认为没有什么必要？

由于还没使用到事件分发器，这里先略过。

软光栅

使用类似engine的设计思路，将渲染器的主体封装成dll，给具体的系统（前端233）作为运行时库调用。我目前希望能够跨平台（虽然现在只知道在windows下是用dll进行符号传递），所以采用了premake作为构建系统，然后不调win32。

目前完成了：

• I/O
  • obj导入
  • 贴图导入
  • ppm形式输出
• gl
  • 画线
  • 画三角形
  • Z-buffer

大部分时间都在调bug吧，今天调了一上午bug，发现是重心坐标公式抄错了。然后CursorAI把width和height弄反了，又搞了半天。

因为感觉渲染一张图有点慢了，因此尝试用了vs的性能分析，结果发现：

好家伙，时间全浪费在输出流上了。这个后续实现实时渲染的时候再考虑吧，看看能不能和QT对接（outputer使用特定平台开发，跨平台只针对我的AYR项目），然后去掉这个流。

UE

这个嘛，因为我更偏向做游戏客户端（引擎感觉太难了，可能要paper，然而我已经没时间走学术了），所以目前有空就熟悉一下UE的使用。后续找实习的时候肯定是需要一个具体游戏项目放在简历的。

毕设

懒得搞。

TODO

得处理一些学校的破事了。然后继续学习。

最近在考虑做游戏客户端是不是容易被AI替代，但是目前的我应该是没有能力去分析这个的。因为目前我还在图形学这里自娱自乐，整天盯着我那屎山项目。但如果以我几年前玩Unity的经验，我觉得短期容易被替代的是那种只会写简单逻辑的程序员。我相信gameplay会是一个很大的，充满想象力的学问，而AI是不会取代具有想象力的工作的。

所以该做什么就做什么，先把手上的软光栅做了，然后尝试构思自己的玩法，开发一个有意思的FPS游戏。

一个很不成熟的做题家思维：你一个南大的会被替代，那其他人不是更寄？。但是回过来看，光焦虑也没用，反而影响自己的进度。这种做题家思维反而会有效减少一些焦虑。

每周总结#2

1. 毕设

目前为止还是不知道自己要做什么。

不过就算知道了，我估计也做不出来。python代码有个弊端就是，对于一个变量它的类型需要你无数次Ctrl+F来自行推导。对于pytorch这里面无数的张量，你要一个一个推出它的shape，然后来确保自己在某个函数的代码能够理解了。

当然我要写的话应该是写cuda代码，然后在python这里看看怎么调用cuda。唉，真头疼，感觉选了个最难的毕设。

我要做的是研究3DGS与光照结合的方法。之前在games101学的无论是光栅化还是光线追踪，都是基于mesh的模型，而3DGS是点云模型，因此需要研究方法能让点云模型具有光照特性。老师给的论文介绍了，在3DGS的基础上，增加一些诸如法向量，以及一些PBR材质相关的可训练的参数。然而我不是做AI的，不知道在代码层面上是怎么在cuda里实现反向传播的（只知道pytorch里的optimizer.step），结果要我改这部分cuda的代码，。。。

希望能水过去，搞的我现在有点烦。

2. 学习

games104

开始了games104的课程，这是个讲游戏引擎怎么构建的课。

目前听了前三节，感觉讲的太笼统了，我还是比较喜欢看代码。

稍微总结一下吧：

首先是引擎架构，其根据功能进行分层，有：

• 平台层：不同平台（比如操作系统，当然还有所谓的Graphics API，比如opengl,dx,vulkan，当然这些我也不是很懂）会提供不同的底层API，游戏引擎需要为开发者提供统一的API，这东西好像叫RHI。
• 核心层：一些数学运算、内存管理、数据结构的实现，比较底层
• 资源层：将不同类型的资源(resource)导入引擎成为对应的资产(asset)，每个asset有对应的GUID方便管理，每个asset也有对应的生命周期，需要handle系统去管理
• 功能层：每一帧会调用tick函数，它大致执行两个任务：tick logic和tick render。当然也不止这两个任务，功能层是最多的内容，它可能还涉及到并行化。
• 工具层：编辑器那些，让开发者进行开发的空间。

然后是对于游戏世界的认识，它包括一些动态物、静态物、环境等等。对于基本的游戏世界的对象，用GO(Game Object)来表示。

每个GO有许多的组件（compoment，玩过Unity应该很熟悉这个），当然这样的组件化设计其实是有很多缺点的，但我没写过对应的代码，没什么认识。

其次就是tick，它是让游戏世界动起来的原因。一种tick方式是一个GO一个GO的tick，还有一种tick方式是按照组件类型进行tick，后者可能会更有效。（cache的空间局限性？）

其次就是交互，采用event事件机制，将不同对象的不同组件之间进行解耦合。

对于场景的管理，引擎的核心层（我猜的哈）可能会用一些数据结构进行高效管理，例如毕设接触到的bvh树来通过场景内的物体位置进行构建，加速查询流程。

对于tick，其实它的时序很有讲究。针对event的邮局机制则有效地解决了事件机制与并行化结合可能导致的时序问题。

总结完了，感觉啥都没总结到。慢慢学吧，我总是太急，想看代码。

tinyrenderer

之前说过，结束了games101的学习，大部分同学可能都会尝试地去写一个自己的软光栅。我也不例外，因此我开始了这个项目的学习。

目前呢？刚学会画直线？？？2333

misc

好消息，离开NUAA了，真的非常开心。

下一次就可以永别这里了，希望再也不用看见这里的人，再也想不起这里的事。

3. TODO

白天搞学校的毕设和其它事情（读论文？做实验？反正都是浪费时间的事情）

晚上学自己喜欢的东西。

没时间打acm了，认命吧，拿不了金牌的fw。

每周总结#1

cf想上橙，但没办法all in算法，所以进行复盘，多注重思维积累

刷题记录 2

dp

ABC373F

link：https://atcoder.jp/contests/abc373/tasks/abc373_f

在裸的完全背包上加了个条件：如果购买了 个相同物品，会有 的价值损失。

尝试先用正常的dp：记 为考虑前 个物品，用了 个容量的答案。

显然有转移 ，时间复杂度是 ，如果 全为1就是 级别的。

因此我们可以考虑将dp的第一维用单个物品容量来代替。记 为考虑单个容量不超过 的物品，用了 个容量的答案。

转移一样是 ，即考虑单个容量为 的物品的贡献，时间复杂度是 。

但是这里有个问题，就是单个容量为 的物品可能不是唯一的。假设对于容量为 的物品有两件，我们在dp转移枚举 (即购买两件物品)的时候，可能是购买同一个物品两件，也可能两件物品各购买一件，而这两种情况显然是不一样的，我们需要取最优。

因此我们将转移方程写为 ，这里的 为考虑购买 个容量为 个物品时对于答案的最优贡献。

怎么算这个 呢？第一反应是从 进行转移，当然这种想法是正确的。

假设我们从 转移到 ，且容量为 的物品有两件，记为a和b。而对于 ，我们假设它是购买了三个a，两个b。

我们转移到 时，就应该需要知道购买第四个a和第三个b时，二者分别对答案的贡献。购买第k件同一个物品时该物品的贡献为 （做个差分就行了）。这个东西（显然）是单调递减的，因此可以采用贪心策略：

• 首先我们先算出所有单个容量为 的物品在 时对答案的贡献。
• 搞个大顶堆，将这些答案以及对应的 放进去。然后开始计算 ，每次从大顶堆取出答案时，根据取出的答案对应的 ，计算出该物品取 的贡献，重新插到堆里。

Code：https://atcoder.jp/contests/abc373/submissions/59299326

总结：本题的突破口在于将传统的背包dp中枚举第几个物品转换为枚举单个物品的容量，同时还要在意到该题购买同一个物品时其对答案的贡献是单调递减的（从数学上来讲，就是 对 的二阶导为非正，因此你可以在出类似于校内新生赛的时候把这个式子改一改，从而转换成自己的题（不是）），如果不是单调递减的话那么贪心策略就是错的。

graph

misc

一类套路题

有两种购买物品的方式，花p元购买a个物品或者花q元购买b个物品。求至少买w个物品的情况下，花钱的最少数。

这种套路题用数学表示为，在满足 的情况下，最小化 的值。

解法

怎么做呢？首先你可能会想到用斜率+贪心的方法，但这肯定是错的。

事实上有这么一个结论：

不可能同时用花p元的方式购买b次且用花q元的方式购买a次。

如何证明呢？首先我们考虑购买ab个物品，如果用p元的方法会花pb元，而用另一种方法会花qa元。

如果我们同时购买很多次ab个物品，那么一定会只使用花费为pb或者qa中的一种的方法，看二者哪个更小。

因此的话，有种 的方法：从 枚举花p元的方式，再从 枚举花q元的方式。

ABC374E

在上面套路添加了一层二分，事实上二分很好想，但上面的贪心套路才是关键。

这里会爆 int ，因此我为了方便就 #define int long long 了。

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

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
constexpr int _{110};

int a[_], b[_], p[_], q[_];
int n, x;
signed main()
{
	std::cin >> n >> x;
	for(int i = 0; i < n; ++i)
		std::cin >> a[i] >> p[i] >> b[i] >> q[i];
	int l{1}, r{1000000000};
	int ans{};
	while(l <= r)
	{
		int mid{l+r>>1};
		ll sum{};
		for(int i = 0; i < n; ++i)
		{
			int smn{x+1};
			for(int j = 0; j < b[i]; ++j)
			{
				int s{};
				if(j * a[i] >= mid)
				{
					s = j * p[i];
				}
				else
				{
					s = j * p[i] + (mid - j * a[i] + b[i] - 1) / b[i] * q[i];
				}
				smn = std::min(smn, s);
			}
			for(int j = 0; j < a[i]; ++j)
			{
				int s{};
				if(j * b[i] >= mid)
				{
					s = j * q[i];
				}
				else
				{
					s = j * q[i] + (mid - j * b[i] + a[i] - 1) / a[i] * p[i];
				}
				smn = std::min(smn, s);
			}

			sum += smn;
		}

		if(sum <= x)
		{
			ans = mid;
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	std::cout << ans;
	return 0;
}