[toc] https://oi-wiki.org/geometry/convex-hull/# 凸多边形 # 凸包 在给定平面上能够包含给定点的最小的凸多边形叫做凸包 使用三角不等式可以证明最小凸多边形的周长最小 # Andrew 算法求凸包 # 二维凸包 把所有点以横坐标为第一关键字，纵坐标为第二关键字排序，排序后最小元素和最大元素一定在凸包上 从一个点出发逆时针走，出现右拐，则不在凸包上，使用单调栈来维护上下凸壳 伪代码 1234567891011121314151617181920212223242526// C++ Version// stk[]...

[toc] 三角剖分有很多种，在刷题中常见的三角剖分一般是 Delaunay三角剖分 这个三角剖分有很多很好的性质 # Delaunay 三角剖分 什么事三角剖分，即对任意多边形进行三角形化 且三角形化后的外边缘是这些三角形集合的凸包 # 定义 唯一性 DT 三角剖分是唯一的，且任意四点不共圆以及外接圆内不会有其他任何一个剖分中的点。 最大化最小角 比如上图，在算法中会选择右边作为最终的三角剖分，以保证最小角是最大的 (交换对角线不会导致最小角变大)。 # 性质 最接近 ： 以最接近的三点形成三角形，且个线段均不相交 唯一性 ：...

[toc] # 二维计算几何 # 正弦定理 在三角形 ABC 内，若角 A,B,C 所对的边分别为 a,b,c, 则: 其中 R 为三角形 ABC 的外接圆半径 fracasinA=fracbsinB=fraccsinC=2R\\frac{a}{sinA}=\\frac{b}{sinB}=\\frac{c}{sinC}=2R fracasinA=fracbsinB=fraccsinC=2R # 余弦定理 在三角形 ABC 中，若角 A,B,C 所对边分别为 a,b,c, 则有: a^2=b^2+c^2-2bcCosA $$ $$...

[toc] https://oiwiki.com/graph/ # Dancing Links Dacing Links 主要可以用来解决 精确覆盖问题 # 精确覆盖问题 OI Wiki 上对与精确覆盖问题是这样定义的：精确覆盖问题: (Exact Cover Problem) 是指给定许多集合S_i(1<=i<=N)S\_i(1<=i<=N)S_i(1<=i<=N) 以及一个集合 X, 求满足以下条件的无序多元组...

[toc] # 各种 Map 只用来记录一些 Map 中所需要特别注意的一些地方 # NormalMap - 法线贴图 简单来说，NormalMap 是用来解决简单表面的细节不足的问题的 # 切线空间 - TBN 切线空间的实际意义: 切线空间是在计算物体表面法线时，通过将副切线映射到 UV 坐标的 V, 切线映射到 UV 坐标的 U, 法线方向为垂直于 UV 贴图的方向 这三个轴建立 基坐标系 然后在基坐标系下通过 rgb 对 TBN 的权重来计算世界坐标下的向量，每个顶点都有属于自己的切线空间 法线贴图定义在切线空间中 T 沿着 U 增大的方向 B 沿着 V 减小的方向 N...

[toc] 简单来说，几何着色器可以控制三角形片元的细分或者增加之类的 # 引用 Oregon State University 关于曲面细分的课件 - GLSL Geometry Shader–Mike Bailey– # 基于几何着色器的粒子化消融 方法: 将一个三角形划分为无数个小的三角形，其中几何着色器可以选择输出的是点还是三角形 # 细分算法 以 V0 为原点 以 V0V1 为方向，V0V2 为方向将 V0V1 和 V0V2 等分划分成 numLayrs 个. 每次细分的以最小的三角形为基准 #...

# 单调队列 # 算法原理 单调队列只允许从队尾加入元素 单调队列可以从队尾和队头弹出元素 单调队列每次进入元素时会把小于 / 大于它的元素从队尾弹出 # 算法性质 保证了队列中必然是有序递减 / 递增的 队头必然是最大 / 最小的元素 相对有序性，即元素在队列中的顺序和实际的 相对顺序 一致 但是要注意的其实还以几个，那就是 比如滑动窗口中，如果窗口过了，那么只需要判断队头元素是否等于弹出的值，等于弹出即可 入队元素如果比队头小 / 大，满足递减 / 递增性，是不会被弹出的 # 应用 如滑动窗口问题，比如找滑动窗口内的最大值，滑动窗口每次会添加一个新值，然后把最后一个元素弹出。...

[toc] # 什么是 wwise wwise 是一款常用于游戏开发的音频插件，它的界面更接近于 Unity, 且可以通过 wwise 实现复杂音频切换的设计。 其中 wwise 最重要的一个作用就是，将音频的控制逻辑和程序进行了分离。 # ActionEvent https://www.audiokinetic.com/zh/library/edge/?source=WwiseFundamentalApproach&id=action_events wwise 使用动作 Event 来驱动游戏中的声音、音乐和振动。 一张图解释 event 作用 可以看出，程序侧发出...

[toc] 什么是帧 在传统的动画中，帧代表的是一秒内播放的图片的数量，其中每个图片代表一帧 在游戏开发中，帧同样也是同样的东西，即每隔渲染 (计算) 的结果是一帧 # 前置概念 # 骨骼动画 / 普通动画 骨骼动画是用来模拟 3D 动画的一种技术， 通过对虚拟骨骼进行插值来计算出每帧下模型的顶点数据 普通动画，比如 2D 动画，实际上是有很直观的帧数据的。 但通常，基于插值的动画数据是会和时间绑定起来的，这个时候，就需要抽象出时间轴上的帧这一概念 # 时间轴上的帧 通过插值计算出来的动画，通常是基于数学公式作为黑盒，时间作为输入，动画数据作为输出而存在的。...