CodingCodingK Blog

参考查找1.顺序查找 顺序遍历。 2.二分查找 折半查找、二分查找，一个东西。对数据有要求，必须是按照关键字进行排序的。 3.插值查找 在二分查找上做的优化。其实就是计算mid值不再是除以2，而是根据线性插值求出一个接近的数。对数据更高要求，不但得是顺序，还必须满足数值分布均匀。 4.斐波那契查找 想在非均匀分布的数据中优化二分查找，就需要用到了。原理与黄金分割有关，从没见过暂时不看。 5.分块查找 这个就是类似桶排序的行为，把数据分成多个区间块来查找。 6.哈希查找 其实就是散列表。选一种哈希函数f，把数据的存储位置x和关键字y形成一种映射，然后查找关键字y时求出下标x即可（当然会有哈希碰撞问题要解决）。 搜索深度优先 DFS属于图算法一种，是一个针对图和树的遍历算法。是盲目搜索算法。一般用堆+栈数据结构来辅助进行遍历，堆是要遍历的对象、栈内是路径结果。 搜索前先定义是先找左下子结点还是右下子结点。探索时会不停往下找，直到下方结点没有了，就开始往上一级。遍历期间，将遇到的结点入栈，如果遇到往上一级的情 ...

参考精简归纳：https://www.drflower.top/posts/6a923688/ 入门图解： https://blog.csdn.net/weixin_50651363/article/details/120070517 https://blog.csdn.net/kexuanxiu1163/article/details/103051357 内部排序冒泡排序我们先固定队尾。进行多次遍历，每一次遍历途中两两比较、两两交换，直到确定到最后1位。下一次还是从头开始遍历，但是之确定到倒数第2位…直到第1位为止。 可以优化，如果某次遍历产生了0次交换，那么可以提前结束遍历。比如排序有序数组时，一次遍历就结束了。 选择排序我们先固定队头。将队列分为2个部分，前面是排序完的部分、后面是待排序部分，每一次遍历都是去找待排序部分的最小值，放到排序完部分的队尾。 Q:冒泡排序与选择排序哪个效率高？A:两者时间复杂度都时候O(n)，但冒泡排序在内存循环交换，选择排序在外循环交换，一般而言选择排序效率更高。 插入排序我们先固定队头。将队列分为2个部分，前面是即刻排序完的部分、后面是待排序部 ...

名词解释

图形渲染管线图形渲染管线 Graphics (Real-time Rendering) Pipeline Graphics Pipeline前面学的流程串起来，就是下图。里面还涉及到了 Shader 和 Texture Mapping 的时机。 Shader一般指 Shader Programs ，是一个程序，会对一个像素点/片段进行处理、着色。可以用OpenGL的语言写，也就是GLSL。 在线shader测试：http://shadertoy.com/view/ld3Gz2 shader展示：https://youtu.be/XuSnLbB1j6E 纹理映射 Texture Mapping前面已经知道，每个像素点的漫反射系数kd乘以光照强度，会得到该像素点最终的颜色。显然，每个像素点的漫反射系数是由物体本身的颜色属性来决定的，而这个像素点的颜色属性我们会通过一张材质图来确定。这就是贴图。 uvuv坐标是指纹理展开后，纹理上的坐标。u和v的范围，都定义在0-1之内。 纹理前面已经学了，三角面内进行插值着色，是用重心坐标来计算出任一个点对应的uv贴图坐标的（也就是决定漫反射系数k） ...

目前为止我们学会了什么？ 相机和物体 -> 变换坐标到原点 -> 拉伸后映射成2D图像 -> 对2D图像进行光栅化：滤波、采样、后处理，最终变成屏幕上的像素点 现在我们引入着色。 着色 Shading什么是着色？着色在普世意义上，是对明暗、颜色进行绘制。 而在图形学中，着色是一个对物体应用材质的过程，正是材质的不同才导致颜色不同。 理解一个简单的着色模型Blinn-Phong Reflectance Model 是一个常用参考的光照反射模型，它分为以下： 高光 Specular highlights：一根光线打到光滑平面（比如镜面）上，会往镜面反射附近去反射。 漫反射 Diffuse reflections：一根光线打到粗糙平面（比如墙面）上，被反射到各个地方的情况。图中茶杯从浅黄到深黄的变化。 环境光照 Ambient lighting：是由间接光源组成的光源统称。图中光线并没有直接打到箭头处，而是打到桌面上被反射，反射光再打到了箭头处。 开始前先定义一个“着色点” shading point虽然反射到的面有曲面、有直面，但我们只观察一个最小的反射点，那么曲面的 ...

之前几节课学了怎么映射一个三角面到画面上，这节学多个三角面之间的遮挡关系处理，谁在前谁在后，也就是可见性怎么处理。 实现遮挡关系画家算法由远及近依次画（光栅化）。近的物体覆盖远的物体，就可以实现遮挡关系。 但是画家算法也存在一些问题，比如存在一些不可依赖深度排序解决的问题。所以不会直接用画家算法。 深度缓存 Z-Buffer这是工业界采用的算法。这里的z不是z轴，而是深度 depth，是摄像机位置到所求点的距离。 最后，只渲染每个像素上depth最浅的那个颜色。当物体发生运动后，会同步更新深度，有更小值出现就重新赋色。 深度缓存的复杂度是O(n)，而不是排序的O(nlogn)，因为深度缓存并不排序只求最小值。

学之前你必须知道视锥这是透视相机的概念，用来衡量视距的大小。一般用2种属性来描述一个视锥： near面的宽高比 垂直视角 Vertical Field of View 有了上面2个确定值，然后再自己定义一个near的值（近平面与相机的距离），就能确定成像了，视锥完成。 屏幕上的概念分辨率，也就是1080p、2k等，就是像素的多少。 屏幕 Raster，德语中的屏幕的意思，而屏幕是一个光栅成像设备。 光栅化 Rasterize，把东西画在屏幕上的过程。 像素 Pixel，全名picture element，是最小单位的小正方形，它的颜色由Red、Green、Blue三个色(0~255)来混和成。 屏幕发展过程过去方式 示波器 阴极射线管 Cathode Ray Tube：和示波器原理相同，用很多电子打在屏幕上。通过扫描一样的方式，一条一条画横线，组成图像。 隔行扫描 Raster Scan：上面的画横线，优化的话还会在一帧只画1、3、5…奇数行，下一帧再只画偶数行。这样省去了一半的工作量，也能一定程度欺骗到肉眼。 现代方式 液晶显示器 LCD（Liquid ...

从三维旋转到欧拉角首先三维旋转绕某个轴旋转，已经知道是这样的了。 那么就可以通过对3个轴的旋转分别描述，来实现复杂的旋转角。这3个旋转角就叫做欧拉角。 罗德里格斯旋转公式一个公式，来实现绕轴n旋转α角度。轴n的定义为起点为原点，方向为n。 推导// TODO 四元数的引入由于用旋转矩阵来做平滑插值并不合理（旋转20°矩阵 和 旋转50°矩阵 的平均值并不是旋转35°），并且存在万向锁问题，所以引入四元数。games101不展开。 MVP变换Model-View-Projection 模型-视图-投影变换：将3D的模型（Model）投影到2D的屏幕（View）上。 先定义相机的 位置 Position、朝向 Look-at、向上方向 Up direction（与朝向垂直，用于确定相机本身的旋转角）。 视图结果是相对不变的，当物体和相机的移动方式完全一致、没有相对运动时，成像不变。 标准相机我们定义一个Position在 原点，Look-at在 -Z，Up direction在 Y的相机作为默认相机。 以后就可以将其他相机移成标准相机、然后再做变换、最后移回就实现了相机旋转。 投影 ...

向量 Vector小概念数学上叫做向量，物理上喜欢称作矢量。 向量的模 Magnitude。 向量的归一化，意味着求单位向量 unit Vector。 向量矩阵下面是在表示笛卡尔坐标系x-y下的某个向量，可以用矩阵来表示向量。 点乘 Dot满足交换律、结合律、分配律。 结果是一个数值，可以用来检测2个向量的夹角，<90度为正，90度为0，90~180度为负。 叉乘 Cross不满足交换律！向量A x 向量B = -向量B x 向量A 结果是一个向量，这个向量是与A、B向量所组成平面的垂直向量，也就是说A、B、C向量构成一个右手直角坐标系。而法线的方向，满足右手螺旋。注意a在前所以a是食指。 图形学上，用来检测某个点是否在一个多边形（比如三角形）内。 //因为 向量AB x 向量AP 的结果大于0则说明P在AB左侧，小于0则说明P在AB右侧。 更新=> 首先确定是左手还是右手坐标系。在【右手坐标系】下，如果两个向量的叉乘结果为正值，表示向量AB经过不大于180°的【逆时针】旋转可以与向量AP的方向一致；如果为负，那么就需要转180°到360°（右手法则）。 至于为什么，思 ...

计算机图形学看一个游戏的图形方面做得如何，一般可以参考画面亮不亮，原因是这关系到了全局光照。 光栅化 Rasterization把三维的几何形体画在屏幕上，这个画的过程，就叫光栅化。 几何学 Curves and Meshes光线追踪 Ray Tracing从相机发射光线穿过每个像素，计算交集和阴影，并继续反射光线直到它们击中光源。 动画、仿真 Animation/Simulation其他行业应用。 总结描述整个渲染管线现代GPU常规流程。具体的可以看渲染管线篇。 0.一堆三维空间的顶点。 1.将顶点做MVP变换，拉伸转换成2维平面。这步涉及2种相机、根据相似三角形确定的拉伸矩阵、纹理映射。（如果是顶点着色模式，这在一步，还会进行Shading。 纹理映射：这一步就要做，因为需要在3维空间内和uv贴图进行一一映射。关系是 二维像素 - 三维平面 - uv贴图。 2.将二维平面的点进行连线，做出大量三角面（顺时针为正面）。 3.将三角面进行采样，投射到屏幕的像素点上，这一步叫光栅化。这步涉及：光栅化的预处理视口变换、采样阶段的优化包围盒、为了抗锯齿做的预处理（滤波、模糊）。 ...