结束了GAMES101的学习（好久了，又因为大作业的毛发渲染由于生病暂时没法摸到自己的电脑，突发奇想的能不能做一个光栅渲染器（因为做raytracer的人实在太多力），于是便开了一个仓库来放相关的东西：Tiny Rasterizer

渲染管线

这里，我们实现的时候因为偷懒因为方便，我只实现了以下的部分：

• 顶点定义
• 顶点变换
• 光栅化
• 片元着色
• 样本操作（暂未实现）

在计算机图形学的几何分支中，直线和曲线都属于隐式表示(Implicit Represent)的几何组件，我们需要一些高效的方式将这些图形以较高的质量绘制到屏幕上。

布雷森汉姆算法

虽然是相对朴素的算法，但是布雷森汉姆算法至今仍有着较高的使用率。

算法的基本想法是通过斜率来不断累积一个error，每当error的值超过一个阈值(0.5)的时候就在另一个方向上进行长度为1像素的前进，最终绘制出一根在屏幕上连续的直线。

NSCSCC2021 终于结束了，经过了一个月的奋战，虽然结果比较可惜只有一个三等奖，但是过程中还是有不少值得记录的东西。

先上个仓库地址：HectorMIPS

Chisel3 or SystemVerilog

在一开始技术选型的时候，我有纠结过是使用SystemVerilog还是Chisel，前者是被龙芯杯往年参赛选手广泛使用的编程语言，后者是被香山团队所Pick的语言。Which is better? 问题的结果并不重要，最后选择了chisel是基于我上个暑假已经使用verilog实现过一个MIPS的五级流水CPU（没带中断以及例外，指令集也高度阉割），However体验并不是很好，于是这次便大胆地尝试了chisel作为开发语言（虽然事实证明我们因此踩了不少坑）。

紧凑的日程

对于诸如域名一类的有限层级的数据，我们提出一种数据结构Bucket Tree来进行数据的树形存储

传统的域名为明显的有限的分级结构，形如mail.bupt.edu.cn，我们需要一种可靠的数据结构来进行存储。以域名的存储为例，有以下的特点：

• 有限层级: 域名最多只有 127 级
• 一次性写入，多次读出: 服务器会在开启时一次性读入硬盘上所有域名记录，且之后几乎没有新增操作
• 重叠性强: 对于类似于com的顶级域名极有可能被多个二级域名重复引用，如baidu.com, google.com

Bucket Tree

桶树是一种结合了多叉树与哈希集的数据结构，其中哈希集使用链地址查找法，平均查找、插入复杂度为O(1)，则对于一个m层的树，查找效率为O(m)，由于在 dns 的语境下，\(m = 127\)，则效率为O(1)。

Let's do some math.

由于我们在计算机中的三维图像最终都是需要渲染到屏幕上的，所以我们需要对其进行一次投影的操作，首先假定我们的坐标为右手系，我们首先在\((0,0,0)\) 原点坐标处放置朝向\(-z\)方向，上方为\(y\)轴方向的摄像机，需要得到的图像的大小为 1x1(假设下的理想情况)。现在，有两种投影方式可供选择：

正交投影 Orthographic Projection

虽然这并不是我们最终希望使用的投影方式，但是正交投影在许多场景如 2D 游戏、工程制图等都得到了较为广泛的应用。

之前写代码的时候发现自己其实完全不懂String和str之间的区别，现在写篇文章来细 🔒

首先查看官方参考文档中对 String 的描述如下

The String type is the most common string type that has ownership over the contents of the string. It has a close relationship with its borrowed counterpart, the primitive str.

我们可以发现 String 是拥有字符串内容的所有权的，而 str 则被描述为“借用”。查看具体实现的源代码，有如下的实现内容：

1
2
3

pub struct String {
    vec: Vec<u8>,
}

尝试使用 Verilog 实现一个 mips 五段流水处理器。

MIPS 指令集

MIPS 指令集分为三类，总共 31 条，分别是

• I 型
  • 指令内容中带有立即数
  • 最多使用两个寄存器
  • Op 字段用于区别不同指令
• J 型
  • 长跳转类型
  • 有且仅有一个立即数
  • Op 字段用于区别不同指令
• R 型
  • 仅使用寄存器的指令
  • Op 字段为 0，使用 funct 字段区别

这三种指令的具体划分以及内容参照这篇博客, 本文中不再赘述。

可作为复习资料打印

线性规划问题的单纯形法

线性规划的标准模型，下面给出一个例子

\[\max z = c_1x_1+c_2x_2+c_3x_3+c_4x_4\]

\[ \left\{\begin{array}{lr} a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1 &\\ a_{21}x_1+a_{22}x_2+a_{23}x_3+a_{24}x_4=b_2 &\\ a_{31}x_1+a_{32}x_2+a_{33}x_3+a_{34}x_4=b_3 &\\ a_{41}x_1+a_{42}x_2+a_{33}x_3+a_{44}x_4=b_4 &\\ x_1,x_2,x_3,x_4\ge 0 \end{array} \right. \]

由于离散数学期中过于拉跨，专门开贴记录相关知识点。

关系

三个定理

1. 如果\(A_1\subseteq A_2\)则有\(R(A_1)\subset R(A_2)\)
2. \(R(A_1\cup A_2)=R(A_1)\cup R(A_2)\)
3. 重点： \(R(A_1\cap A_2)\subseteq R(A_1)\cap R(A_2)\)

整除关系 定义整除关系\(a|b\)为：\(a\)能整除\(b\)，如\(3|6\)，画哈塞图表示（哈塞图无向），则为上面为被整除的数，下面为除数。对于定义在集合\(A=\{1,3,6,9,15,45\}\)上的哈塞图如下：

期末之前临时抱佛脚，复习数理统计

数理统计部分

统计量

1. 样本平均值 \[\bar{X}=\frac{1}{n}\sum_{i=1}^nX_i\]

2. 样本方差 \[S^2 = \frac{1}{n-1}\sum_{i=1}^n(X_i-\bar{X})^2\]

3. 样本标准差 \[S = \sqrt{S^2}\]

4. 样本 k 阶（原点）矩 \[A_k=\frac{1}{n}\sum_{i=1}^nX^k_i,\quad k=1,2,...;\]

5. 样本 k 阶中心矩 \[B_k=\frac{1}{n}\sum_{i=1}^n(X_i-\bar{X})^k,\quad k=1,2,...;\]

重要定理