C++学习笔记

动画与仿真理论电影24帧，游戏144hz 关键帧动画 先画关键帧，再画过渡 插值的技术 物理模拟 分析受力模型 质点弹簧系统 基础单元：一个弹簧连接两个质点 加入摩擦力 模拟一块布 切变问题：内部加连线 有限元方法，用于车辆碰撞 粒子系统，用于雾，烟花等 运动学 关节，分为pin，ball，prismatic 逆向运动学：固定终点，解转动角度 rigging骨胳绑定 给东西添加动作，造型，类似控制木偶 添加控制点，类似贝塞尔曲线 动作捕捉 不是创建控制点，而是用真人上的点 贴片 计算单粒子模拟 是什么：已知速度，求任意时刻位置 怎么解决：解ODE常微分方程 具体方法：（数值分析内容） 欧拉方法，上一时刻求下一时刻，但不稳定 中点法：用2次欧拉方法 自适应步长：是否继续使用欧拉方法，取决于两次结果差的多不多，差得多就往下分 隐式欧拉方法：后向欧拉方法，用未来的速度，稳定 ...

相机，透镜，光场成像方法 合成：包括光栅化和光线追踪 捕捉：相机 焦距 曝光=时间×irradiance 快门时间，时间相对于高速运动物体太长，会造成运动模糊或者扭曲 光圈大小，大光圈景深小，清晰范围小，会模糊 iso感光度，iso变大，噪声也会跟着放大 透镜/镜头 circle of confusion弥散圆，引起景深的原因 颜色和感知光场 全光函数：描述看到的所有东西，7维函数 光场是全光函数的一部分，4维函数 角度转换为uvst，在观测处和真实物体之间两个屏幕光场照相机 特点：先拍照片，可以后期调焦距 原理：原本的相机成像平面是一个个像素，现在换成了微透镜阵列，可以把每一个像素接收到的光再分散，所以可以分散后选择接收哪条光线 如果选择的方向统一，就是相当于虚拟的移动相机位置 如果不统一，而是根据一些东西计算方向，就可以调整焦距 其实有点像复眼，但是复眼接收到的是一个像素，而这个接收到的是光场（各个方向） 缺点：分辨率低 颜色的物理基础 SP ...

高级光线传播和材质无偏光线传播 BDPT，双向路径追踪，相机和光源都发出光线 MLT，Metropolis传播，马尔科夫链蒙特卡洛积分局部性适合复杂场景，例如位置奇怪的光源，caustics焦散不知道收敛速度 有偏光线传播 photon mapping光子映射适合复杂路径，焦散光源发出光线到漫反射停止，相机发出光线到漫反射停止 VCM结合BDPT和光子映射 IR实时辐射度算法 VPL一个光源变很多光源 外观建模非表面模型 participating Media散射介质雾，云相位函数 头发marschner model，描述如何与头发作用头发类似玻璃圆柱散射出的是圆锥分为三种类型，R直接反射，TT折射进折射出，TRT 动物毛皮圆柱内有个髓质，负责散射 granular颗粒材质 表面模型 半透明材质次表面散射，在表面下发生的散射BRDF->BSSRDF，多了一个出射位置计算量太大，优化成两个光源来近似次表面散射 布料直接当成物体表面，不太准确转化成散射介质渲染，计算量很夸张转化成头发。计算量更夸张 复杂材质例如划痕，各向同性金属加工，使不完美，更接近真实微表面模型 ...

材质和外观材质就是BRDF如果不吸收光，fr=1/pi反射率ρ，fr=ρ/pi glossy有点像金属，类似铜镜reflective反射，玻璃，水refractive折射 caustics焦散 snell window/circle 菲涅尔项，描述反射折射能量和角度的关系 绝缘体：视角越平行离法线越远，反射能量越大 导体：视角无论在哪，反射能量都挺高 菲尼尔项简化：Schlicks公式 微表面材质：从很远很远看，基本变粗糙的平面 远处看粗糙平面，是材质 近处看凹凸镜面，是几何 微表面法线分布 集中-glossy 分散-diffuse粗糙，磨砂 微表面BRDFfr=F菲涅尔·G几何项（遮挡）·D法线分布 isotropic各向同性/各向异性材质 各向同性：普通金属 各向异性： 金属加工工艺 尼龙 天鹅绒 测量BRDF

5光线追踪5.1占位和光栅化是两种成像的方式光栅化不能很好表示全局效果，包括软阴影光泽反射mirror（相对模糊反射glossy而言）间接光照 光栅化的特点：快，近似光线追踪：慢，精确，适合离线offline 光线定义三个假设直线传播不会碰撞光路可逆 光线生成让光线从眼睛发射出去，形成眼睛-像素光路连接像素-光源光路，看有没有物体阻挡 此时只弹射了一次，因此用Whitted-Style光线追踪，递归算法光线可以继续折射和反射1979年要74min，2006年要6s，2012的GPU只要1/30s 求光线和物体表面交点隐式表面，求方程的解显式表面求光线和三角形交点：MT算法，利用重心坐标求解要计算三角形数量的次数，太慢解决办法：计算光线和包围盒的交点（本质是剪枝）光线进入盒子时：光线进入了所有对面，进入时间取最大光线出盒子时：光线离开了任一对面，离开时间取最小 离开时间<0：盒子在光源背后，无交点离开时间>0，进入时间<0：光源在盒子里，有交点总结：如果有焦点，则进入时间<离开时间，且离开时间>0 利用包围盒加速 均匀格子：把包围盒划 ...

4几何隐式几何：不容易画，容易判断内外 显式几何：容易画，不容易判断内外 构造立体几何法：几何交并补操作 距离函数：描述复杂的几何，水滴飞溅等等 分形 4.1显示几何表示 点云 曲线 贝塞尔曲线：控制点的线性组合系数是多项式 逐段贝塞尔曲线：PS的钢笔 样条：B样条 曲面 贝塞尔曲面 多边形网格 4.2多边形网格相关操作①网格细分，更多三角形 loop细分方法： 增加三角形数量 调整三角形位置 新顶点的值是周围点的平均 旧顶点，周围顶点和自己加权平均 Catmull细分：loop只能细分三角形 第一次细分：非四边形面有多少个，就会变为多少个奇异点；之后的细分不再有非四边形面了，只会增加四边形面的数量 顶点位置的更新：分为新·面的中点，新·边的中点，旧顶点 ②网格简化（粗分），更少三角形 方法：边坍缩，把边的两个顶点往中间捏 衡量坍缩哪条边，需要用到二次度量误差，类似L2距离，即点到别的面的距离的平方和最小 先坍缩二次度量误差最小的，坍缩后再更新受影响的二次度量误差，需要用到优先队列结构 实际上类似贪心算法 ③网格正规化，三角形接近正三角形4.3阴影阴影 ...

2光栅化定义视锥的话，需要定义一个宽高比和垂直可视角度 光栅，德语的屏幕，光栅化就是在屏幕上显示出来 视口变换：[-1,1]的立方体映射到[width,height]，先不管z 采样：1判断像素点在不在三角形内‘ 光栅化：对像素点进行赋值 2.1反走样和深度缓冲 一些失真 走样：锯齿的别名 摩尔纹 车轮效应 原因：采样率太低 解决办法：先滤波（模糊），再采样 实际：每个像素不再是二值，而是取像素内颜色的平均 MSAA：像素内不同颜色面积不好求，变为求4个点的覆盖率 FXAA TAA 超分辨率：低分辨率到高分辨率 3着色3.1遮挡 画家算法：先画远的，再画近的，不行，有bug Z-buffering深度缓冲：深度表，一直更新最小深度处理不了透明物体 3.2着色模型着色定义：对物体应用不同材质 区域分类：高光，漫反射，环境光 漫反射输入：观测方向v，法线方向n，光照方向i，表面参数着色≠阴影输出：着色点亮度Ld公式：正比于入射角，反比于距离 高光观察方向和镜面反射方向接近，即半程向量和法线方向接近输出：Ls 环境光 输出：La，常数 3.3着色频率平面着色， ...

Overview计算机图形学应用1. video gamses技术上判定标准：看整个画面亮不亮-全局光照 2. 卡通风格如何表述 3. movies各种特效，越真实的越难 4. 面部捕捉 5. animations动画，包括盐雾粒子头发衣服 6. design设计 7. visualization可视化 8. virtual reality虚拟现实 9. digital illustration 10. simulation物理模拟，仿真，动画 11. GUI 12. typography 字体 计算机图形学设计内容1. rasterization光栅化 实时：1秒30帧，相对的叫offline离线 2. curves and meshes曲线和曲面 表示 3. ray tracing光线追踪 4. animation/simulation动画， 模拟 1变换线性代数预备知识 点乘：找夹角 如>0，说明两个向量同向forward；<0说明反向backward 叉乘：判断左右和内外 1.1变换应用 模型变换modeling：摆东西 视图变换viewing：摆照相机 ...

二叉树解题技巧1遍历方式1.1前序遍历（中左右） 递归法思路： 确定递归函数的参数和返回值：节点和数组、返回void 确定终止条件：节点为空 确定单层递归逻辑：中左右顺序 伪代码：123456void traversal(TreeNode* cur, vector<int>& vec)if (cur==null) return******递归部分******vec.push_back(cur->val); // 中traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右 迭代法思路： 利用栈，顺序是栈顶元素（中）弹出，再按右左的顺序入栈 伪代码123456789101112131415vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> result; if (root == NULL) return re ...

二叉树种类 满二叉树：2^k-1 完全二叉树：除底层其他满，底层连续 二叉搜索树：节点有一定顺序 平衡二叉搜索树：左子树和右子树高度差不超过1 存储方式 链式存储：左右指针 顺序存储：两个子节点2i+1，2i+2 一般把二叉树当作一个链表来构造 遍历方式 深度优先搜索：递归法和迭代法，栈 前序遍历，中左右 中序遍历，左中右 后序遍历，左右中 广度优先搜索：迭代法，队列，一层一层/一圈一圈地遍历 层序遍历 定义（ACM模式）1234567struct TreeNode{ int val; TreeNode* left; TreeNode* right; //构造函数... 略}