游戏开发与图形学学习记录

Aspect-ux's Blog 喜欢coding，画画，动漫。大四，接触unity快两年了，目前想要做一名技术美术。 Links(链接) 知乎 (aspect - 知乎 (zhihu.com) 主要记录技术美术和渲染的学习 bilibili 技术美术作品集24届_哔哩哔哩_bilibili 个人作品集展示 github aspect-ux/AspectuxEngine (github.com) 基于OpenGL自制游戏引擎，使用c++17, 历时4个月左右，属于边学边抄边做的产物（曾经梦想做一款自己的游戏引擎...） 游戏开发比赛经历 如下 曾经参加GameJam的记录 个人板绘展示(挺丑的) 点击跳转 主要是大一大二时画的 Leetcode うみとご飯 - 力扣（LeetCode） 曾经沉迷刷题，记录一下账号 游戏开发比赛经历 2022网易Mini Game 2022网易游戏高校MINI-GAME挑战赛—— ...

TODO:2023/08/18 19:00: 1.递归非递归遍历 2.线索树 TODO:2023/08/21 20:00: 1.取消stl的使用 2.树，森林，二叉树 3. 哈夫曼编码 4. 并查集的应用 前言 使用语言：c/c++ 仅个人学习记录，如有细节错误望理解（欢迎指正） 完整可运行代码见文末 持续更新中 什么是树 定义：n（n>=0）个结点的有限集合。n = 0为空树。 什么是结点？可以理解成一个包含数据区域和若干个指向其他结点的指针的结构体。 对于非空树，有且仅有一个根结点，其他结点皆有前驱结点。 表示方法： 倒置树结构（如下图) 文氏图 广义表 凹入表示法 基本术语 度：分为结点的度和树的度两种。前者是该节点的子树数量，也即后驱结点个数；后者则是所有结点度的最大值。 叶结点：也称为终端结点 层级：从根结点往下，1-n 树的高度：最大层级数 结点的名称：子结点，根结点，父结点（双亲结点），兄弟结点，堂兄弟结点等等。 m（m>=0）棵互不相交的树。 二叉树 二叉树中一个结点的后驱 ...

查找与排序 前言 本文主要包括查找算法和经典排序算法两个部分 使用语言：c/c++ 仅用于个人学习记录，如有细节错误望理解（欢迎指正） 持续更新中,完整可运行代码见文末 参考https://www.runoob.com/w3cnote/merge-sort.html (归并排序开始) 查找 首先要理解什么是查找。 查找是在相同数据类型的集合中，使用唯一标识（关键字K）来查找数据元素（V）。 平均查找长度 ASL = \(P_1C_1 + P_1C_2 + ......\) 其中\(P_i\)是概率，\(C_i\)是查找第i个元素比较过的次数。 用于分析算法性能。 查找有哪些方法： * 比较式查找法 (1).线性表的查找 (2).树的查找 * 计算式查找法 (1).hash查找 理解以上三点后开始进一步学习具体的查找方法。 比较式查找-基于线性表的查找 顺序查找 存储方式可以是顺序结构，也可以是链式结构 按顺序与关键字比对查找。 12345typedef struct{ int key; int val;}Ke ...

What is Radiometry 辐射度量学主要是对光的描述测量,是在物理意义上对光的确切定义。 Measurement system and units for illumination 之所以需要这样一个确切的描述性的东西，是因为无论是之前着色的布林冯，还是whitted风格光线追踪，其实都是不准确，效果不好的。这些方法做了太多简化和trick，以至于实际效果不能满足要求。 Basic concepts of Radiometry Radiant Energy and Flux (Power) Radiant Energy 是电磁辐射的能量，用Q表示，单位是joules(焦耳) Radiant Flux(power) 是单位时间的能量，其实就是功率，单位瓦特W； 另一个别称叫做流明，类似于水的功率叫流量 Light Measurements(光照测量) 【基本英文名词】differential(微分) derivative(导数) 下图为三个表示光照能量的三个量 Radiant Intensity 光源发出的光照 Definition: ...

Why Ray Tracing?光线追踪和光栅化是两种不同的成像方式，为什么要选择光线追踪呢？ 光栅化的局限性在于全局效果的控制： 1. 不能实现软阴影 2. 光照不能反射超过1次（目前技术可行效果不好） 光栅化很快，效果却不好。 相反，光线追踪很慢，但是很精确 Light RaysThree ideas about light rays(满足三个假设的前提) Light travels in straight lines(though this is wrong) 光线沿直线传播 Light rays do not “collide” with each other if they cross(also wrong) 光线之间无碰撞 Light rays travel from the light source to the eye(but the physics is in variant under path reversal - reciprocity) (光线可逆性，可以理解为光的方向互逆) 正常情况下，我们的理解是光源打光到物体上，物体反射光照到人眼，根据反射的颜色 ...

Introduce to GeometryExamples of Geometry机械 水 毛发 Representation of GeometryImplicit(隐式表达) 隐式表达，一般看表达式，但是光看表达式并不直观。algebraic方式。 另一种方法是constructive solid geometry（csg,构造立体几何法) 距离函数Distance Function 希望blend得到AB的中间状态，SDF是有向距离场 如果是第一行的图，结果不能得到左黑右白的中间态 第二行使用SDF，通过blend，可以得到0的位置，颜色围绕0开始渐变。 插值得到的SDF再转回原图像 Explicit(显式表达) 直接通过uv映射方式定义 隐式不知道函数的结果是哪个变量，显示知道；显示通过已知的自变量就能得出图形的结果样子。 Geometry is hard! Point Cloud（最简单）,lists of point,点足够多就成了面 Polygon Mesh(多边形网格)，如三角网格 The Wavefront Objec ...

Shading(着色)Visibility/Occulusion(可见性/遮蔽)Painter’s Algorithm 从后往前画 但是由于自遮挡的关系，有些无法具体描述远近的（如上图左右面的绘制），绘制顺序显得尤为重要。 左，下，右，上，这个顺序结果正确 但是右，上，左，下，由于左下两面的错误遮挡，导致结果错误。 假如一个模型是两个蛇状管道相互缠绕组合而成的，那渲染先后的问题就更加困难，正方体能够区分不同面无非是一个面遮挡另一个，后者不规则的分区有着非单一的复杂遮挡关系，如此看来这种算法局限性也很大 结论： 一定程度上画家算法是有效的，但是sorting layer的问题是难以解决的。 ZBuffer 深度缓存 为了解决画家算法的问题，引入深度缓存 简而言之，对每个像素的深度进行保存，保留最近的那个深度值 framebuffer存颜色值 depth buffer(z-buffer)存深度值 效果如下图，记z值为positive 具体代码实现算法，记初始zbuffer的值都是无限大，每绘制一个图元都来一次二重循环遍历所有像素，不断装填覆盖更小的z 时间复杂度O(n),设三角 ...

VS CPP 配置在VS上编写cpp程序时，经常出现少了xx库或者xx undefined 分为静态和动态配置方法 下载对应资源包 认识配置方法 属性面板有三个选项， 动态载入： ①对于下载的include 在”C/C++”下配置；②lib在linker下配置，具体lib文件在linker->input下配置；③dll一般放在根目录（或者32dll放在sysWOW64,64dll放在system32下） 静态载入： 前两步和之前一样，但是第三步变成在linker->proprocessor中加入对应宏 注意对应版本文件夹 常用文件解释bin文件夹 放置二进制文件，也即可执行二进制文件 .lib文件和.dll文件 在了解”.lib”文件之前，我们得清楚几个点 ①首先，程序编译和运行是两个过程 ②其次，语言分两种，编译型语言和解释型语言：a.编译型语言里程序执行一般是有编译->链接这两个过程的b.解释型语言没有这两个过程，你可以说没有链接过程，也可以说随时都在链接 ③大家看到的静态链接、动态链接实际都发生在编译阶段！ ④链接简单来说就是把编译的代码里的对象符号 ...

Rasterization(光栅化)前一节讲了变换（transform),过程总览如下图 光栅化流程之前提到了MVP过程，在这之后,所有的物体都会停留在【-1，1】^3 立方体(Canonical Cube)空间中，然后要进行光栅化。 Viewport Transformation(视口变换)也就是将物体“画”到屏幕上，这里具体要做的是上图中的viewport mapping 即将【-1，1】拉伸(重映射remapping)到【width,height】的屏幕上 设置什么样的变换矩阵才能变换成功呢？ （其实在半兰伯特光照模型中就有这个思路，先乘以1/2，然后加上1/2，就转换到【0，1】区间了。） 根据这个思路得到转换矩阵 需要注意：这个变换与z值无关 Rasterizing triangles into pixels上面只是说了光栅化是画物体到屏幕，具体来说，物体是由一个又一个多边形构成，最基本的元素是三角形，我们要做的是让这个三角行用像素画出来(或填充)，进而在屏幕上显示。 具体实现算法就是通过遍历像素，判断像素中心是否在三角形内。 如何判断是否在三角形内 假设从ABC ...

Transformation(变换)变换的数学意义(介绍)Why TransformationQ1： 为什么要学习变换呢？ A1： 动画的实现，光栅化图像变换投射进“人眼”。由于计算机最终的变换服务于数学世界，于是同一用矩阵来表示变换，线性代数中学过对应知识。 Q2: 举例有哪些变换？ A2： Scale Matrix，缩放；Reflection Matrix,对称(镜像)； Shear Matrix,切变(有称”错切“，”斜切“)； Rotate Matrix… 旋转矩阵推导 到目前为止的变换，我们都可以对(x,y…)进行线性变换(Liner transformation)得到变换结果(x’,y’) 但是平移变换不行？ 试想一下，如果对x平移一个单位，那么变换矩阵 无法用一个矩阵就解决变换，（上面的变换形式引出仿射变换(Affine Transformation)的概念），同时进行线性和平移变换 接下来 Homogeneous coordinates(齐次坐标)要想用一个矩阵表示所有变换 这里引入了齐次坐标的概念，以二维举例，引入第三维度 设点的第三维度为1，向量为0. 之 ...