当我们完全了解UE4的多线程是怎么进行时，我们就需要看一下UE4的主线程和渲染线程到底如何进行的同步的。 UE4多线程架构 GameThread、RenderThread、RHI Thread和GPU之间的渲染器同步是一个非常复杂的主题。简而言之，虚幻引擎4通常配置为"后一帧（single frame behind）“渲染器。这意味着当RenderThread处理第N帧时GameThread处理第N + 1帧，除非RenderThread的运行速度比GameThread快。 添加RHI线程使同步过程更为复杂化，因为当RHI线程处理第N帧时，RenderThread能够通过完成第N+1帧的可视性计算而移动到RHI线程之前。最终结果是，当GameThread处理第N+1帧时，RenderThread可以处理第N帧或第N+1帧的命令，RHI线程也可以平移第N帧或第N+1帧的命令，具体取决于执行时间。 在帧的末尾，我们将执行主线程和渲染线程的同步。通过静态的FFrameEndSync来进行线程间的同步。 1 2 3 4 5 6 7 8 //同步主线程和渲染线程 { SCOPE_CYCLE_COUNTER(STAT_FrameSyncTime); static FFrameEndSync FrameEndSync; static auto CVarAllowOneFrameThreadLag =IConsoleManager::Get().FindTConsoleVariableDataInt(TEXT("r.OneFrameThreadLag")); FrameEndSync.Sync(CVarAllowOneFrameThreadLag -> GetValueOnGameThread() != 0); } 我们来看一下FFrameEndSync的数据结构 1 2 3 4 5 6 7 8 9 10 11 12 13 class FFrameEndSync { /** Pair of fences. */ FRenderCommandFence Fence[2]; /** Current index into events array. */ int32 EventIndex; public: /** * Syncs the game thread with the render thread.

目前刚接触UE4，想要得到最后更优质的图像，简单的研究了一下Light Propagation Volume。 Light Propagation Volume： CryEngine的开发者发明了Light Propagation Volume (LPV) ，主张不使用预计算，在运行时直接计算动态间接光照。通过对LPV进行marching，可以产生半光泽材质的反射：它的做法简单总结是先生成一些虚拟的点光源来近似间接光照。每个点光源都要渲染一个reflective shadow map，然后将shadow map的光照信息注入到一个专门用球谐系数形式保存光照的volume 3D纹理里面，然后在纹理内部将最初的光照传递分散开来，渲染的时候直接从这个volume texture里读取要着色的点位置的颜色作为间接光照。这个方法可以达到不错的间接漫反射。缺点第一是volume texture太费显存，第二是基于体素化之后的光照信息也会有“格子”样的artifact，而且也是非常耗费计算的一个技术，因为每一个虚拟点光源都要渲染一个reflective shadow map。 这个功能是默认没有打开的(为啥没开不用多说了吧!)，必须要修改配置文件，r.LightPropagation=1 加入consolevariables.ini 文件最后。 遇到问题 漏光问题，拥有体积的面片墙无法遮挡光线渗透。之前项目的脑残做法是用一个额外的box进行遮挡阳光。我服了。 可通过调整Light Injection Bias 来规避问题。别问为什么，我现在也不知道。 阴影平坦，调整Occlusion 结论 总之呢，目前来说，由于灯光全都是动态光，mesh也是动态的，不能进行bake的话，LPV这是比较好的解决方案，但是并无法产生最好的图像。

之前的白噪声确实不太行，因为我们现实生活中并不是那样的完全嗡嗡。 我们接下来就是要生成这样的纹理。 一维noize 接下来看不同方式生成的一维noize 1 2 3 4 5 float i = floor(x); // 整数（i 代表 integer） float f = fract(x); // 小数（f 代表 fraction） y = rand(i); //rand() 在之前的章节提过 y = mix(rand(i), rand(i + 1.0), f); y = mix(rand(i), rand(i + 1.0), smoothstep(0.,1.,f)); y = mix(rand(i), rand(i + 1.0), f);使用的是线性插值 y = mix(rand(i), rand(i + 1.0), smoothstep(0.,1.,f));顶点的变化如何变得顺滑了起来 二维Noise 在 2D 中，除了在一条线的两点（fract(x) 和 fract(x)+1.0）中插值，我们将在一个平面上的方形的四角（fract(st)， fract(st)+vec2(1.,0.)， fract(st)+vec2(0.,1.) 和 fract(st)+vec2(1.,1.)）中插值。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 uniform vec2 u_resolution; uniform vec2 u_mouse; uniform float u_time; // 2D Random float random (in vec2 st) { return fract(sin(dot(st.

虽然简单的包围盒技术能够减少计算开销，但是对于整个光线跟踪算法来讲算法的效率还是没有显著地提高，究其原因主要在于，每一根被跟踪的光线都需要与场景的包围盒进行计算，算法的效率还是受到限制，其算法的复杂度为 O(N)，其中 N 为场景中物体的个数，即三角形数目。为了提高包围盒技术的效率，通过将包围盒组织成层次结构来改进简单的包诶和技术。其基本的思想为将整个场景按照场景的包围盒进行组织，根据物体在场景中的分布，相距很近的物体形成局部场景，然后这些局部场景又可组成更大的组，这样就形成了整个场景的树形层次结构。 如何分组时形成树形层次结构的关键步骤，理想的分组是建立在理想状况下物体间的相距距离，通过距离的远近对场景进行分组。层次结构的形状取决于场景中景物的空 间分布，通常越靠近树状结构的底层，包围盒则越小。建立层次结构常用的策略即“中分面”技术，该技术通过二叉剖分技术对场景进行从上到下的递归分组。 使用层次包围盒技术的光线跟踪算法，跟踪光线首先和场景包围盒求交，与场景包围盒相交后再和场景包围盒割分的包围盒求交，知道光线和最小包围盒相交后与最小包围盒内包含的物体面片求交，最终求得交点或是光线与物体无交。在建立场景的层次结构时最重要的步骤就是对整个场景中的物体进行合理的分组，一个理想的层次结构是基于物体之间距离的远近来进行分组的，层次结构的形状则依赖于场景中物体在空间的分布情况，一般来说，越靠近底层的结点，其包围盒会越小。在建立包围盒层次结构时常用的方法是——中分面（median-cut）技术，该技术使用二叉剖分技术对整个场景进行自上而下的递归划分。在每一结点处，首先将其所包含的景物按其 x 坐标轴的值进行大小排序，并将该结点的包围盒的 x 方向的中分面作为分割面对所含物体划分为两组而产生其两个子结点，再将两个子结点各自依次沿 y 轴和 z 轴两个方向依照 x 轴进行分组。将上述步骤递归进行，直至当前结点只包含一个物体为止。 可以看出，层次包围盒技术一方面利用包围盒技术避免了跟踪光线与不相交物体进行无效求交测试，同时又利用包围盒比较简单容易与光线进行求交测试，快速的确定于光线相交的物体。这与上小节中论述的内包围盒的改进算法有相似之处。本方法最终是只包含一个物体，光线只同一个物体进行求交测试，之前的大部分求交都是同包围盒的求交测试（比较简单）。 层次包围盒极大的降低了光线与景物求交测试的计算复杂度，但是计算量仍然很大，包围盒通常在空间是无序的，而光线跟踪需要找到离光线起始点最近的交点，而对于位 于光线后的物体求交计算式无用的。同时光线与物体的求交的效率通常与划分的层次结构有关，不同场景求交的效率可能大不相同。虽然包围体的形状可以是千奇百怪，可以 使球形也可以是立方体，但是要快速判断光线与包围盒的关系，那么轴对齐包围盒（AABB）是最简单的包围结构，所以通常都选用轴对齐包围盒作为结点类型 。 均匀网格 传统光线跟踪算法效率不高的主要原因在于光线与物体求交的盲目性、广泛性，跟踪光线必须和场景中的所有物体逐一进行求交测试，而且由于光线与物体求交测试的无序性，求交后还要对各交点进行远近排序以找到最近的交点。从提高光线跟踪算法效率的方面看，一方面一些物体和光线根本不相交还要作求交测试，另一方面在交点排序中排在后面的交点的求取是无用的。对每一条跟踪光线，我们所需要的仅仅是它在场景中最先相交的那个物体交点 [2] 。 考虑到场景中的各物体的空间位置是固定的，为了减少光线求交的盲目性，可以将场景空间进行剖分，剖分成很多位置固定的小方格。这些小方格在空间的位置是固定的，而且相互紧密连接着跟踪光线依次穿越小方格，光线只与它穿越的小方格中的物体面片求交，这就是空间剖分技术。这些小方格有序的被组织成了层次结构，其叶节点记录了它所包含的物体面片表，光线跟踪时只需要与它依次跨越的各网格空间内所含物体作求交测试；另一方面，由于网格空间排列的有序性，光线总会和它最先相遇的物体作求交测试，一旦有交则该光线的跟踪就结束，该交点即为最近交点，避免了对最近交点后面物体的求交测试计算及交点的排序。这也是空间剖分技术的优势之处。 1986 年，Fujimoto 等提出了一个基于空间均匀网格剖分技术的快速光线跟踪算法。该技术将场景空间剖分成一系列的大小均匀的三维网格，每个网格包含一系列的面片。 从而建立起一个称为 SEADS 的辅助数据结构（Spatially Enumerated Auxiliary Data structure）通过指针将包含在网格内的面片一一链接起来，在跟踪光线时，只需要计算跟光线经过空间的网格内的面片进行求交计算。如图 3.1 给出了包含 10 个面片二维场景的网格剖分及其 SEADS 结构。从图 3.1 中可以看出，光线 1 只需与面片 7 进行求交测试，而光线 2 则需要分别于面片 5、6、3、4 和 0 进行求交测试，最后得到的交点位于面片 4上。 在 SEADS 机构中，每一个剖分出的小立方体可用一个整数的三维空间坐标（i，j，k）来标示其位置，每个立方体中均含有其所包含的物体面片信息。光线只与其跟踪方向上的立方体相交，而且最先穿越的还是最近的，光线和它索穿越的立方体中的物体面片求交，一旦求得交点即为最近交点，这就是 3d-DDA 算法。 （1）若光线和垂直于 i、j 坐标轴的当前网格界面均相交，那么将距光线起点较近的交点所处界面相对应的坐标方向设为增量方向；若光线和这两个边界面无交，取主轴方向为增量方向；若和一个边界面相交，将和光线相交的边界面相对应的坐标方向设为增量方向。 （2）当前网格沿第(1)步确定的增量方向位移一格，即得到下一网格的坐标。 虽然均匀网格能够提高光线跟踪算法的效率，但是它仍然存在一定的弊端，它要求场景中的三角形面片分布比较均匀，这样在仿真时对场景要进行限制，如果场景中的面片分布不均匀，则均匀网格则不能达到很好的加速效果。特别是当场景中物体的三角形面片分布相当的稀疏时，对网格的划分会包含很多空白网格，这些网格不包含三角形面片，然而在光线在到达含有交点的网格之前，需要穿过很多这样的空白网格，这样会大大降低算法的效率。同时由于它在空间划分的特殊性，多个体素很可能包含相同三角形的多个引用，这就意味相同的光线与相同的三角形存在多次求交测试。

本片文章主要讲述如何利用shader生成随机数。 一维随机 y = fract(sin(x)*1.0); 上面的例子中，我们提取了sin函数其波形的分数部分.我们可以用这种效果通过把正弦函数打散成小片段来得到一些伪随机数如何实现呢？通过在sin(x)的值上乘以大些的数。 y = fract(sin(x)*10.240); y = fract(sin(x)*100.0); y = fract(sin(x)*1000.0); y = fract(sin(x)*10000.0); 当我们不断的进行增大时，其实我们增大的是sin函数的幅度，但是由于fract的限制，这其实是增加fract的定义域，它会形成-1——1之间的更加密集的点。 细看，你可以看到 sin() 在 -1.5707 和 1.5707 上有较大波动——那就是sin取得最大值和最小值的地方。并且我们的中部更加的集中。 我们当然可以使用一些其他的变化 1 2 3 4 y = rand(x); y = rand(x)*rand(x); y = sqrt(rand(x)); y = pow(rand(x),5.); 这些都是伪随机，也就是说给定特定的数，生成的是特定的随机。 二维随机 我们要进行二维随机，其实就是能够把两个轴分开来看待。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #ifdef GL_ES precision mediump float; #endif uniform vec2 u_resolution; uniform vec2 u_mouse; uniform float u_time; float random (vec2 st) { return fract(sin(dot(st.

Bentley 于 1975 年在 中提出一种多维二叉查找树，即 kd-tree，其中k代表查找空间的维度。kd-tree 可将一个给定的空间根据其存储的记录进行多级分割，每一级轮换使用各个维度并抽取一个记录在该维度上的值将空间或子空间一分为二。 比如 2d-tree，第一级抽取一个记录的 x 值按 x 维度分割，得到两个子空间，接着对两个子空间分别抽取其它记录的 y 值按 y 维度分割，再到下一级时又按 x 维度分割，最终每个分得的子空间最多包含一个记录。查找记录时从根节点开始，每级只采取一个相应的维度值进行比较，然后进入子级继续比较，如此可以快速过滤无关记录。 一.kd-tree 的构建及记录的插入 建立根节点，取出1r 并作为根节点中存储的记录； 取出r2访问根节点，根节点中已存储记录r1 ，则以r1 的 x 坐标值为横向分割面将根节点分为左右两部分建立两个子树节点，r2 的 x 坐标值大于r1 ，因此将r2存储在右节点； 取出r3 ，访问根节点，r3 的 x 坐标值大于r1 ，因此访问右子树，而右子树已存储2r ，又因其父节点是按 x 坐标横向分割的，因此r2 所在子树将以r2 的 y 坐标值纵向分割为两个子树节点，r3的 y 坐标值大于r2r ，因此将r3存储在右节点； 取出r4 ，经根节点与r1 的 x 坐标值比较进入右子树，与r2的 y 坐标值比较进入右子树到达r3 所在子树，则r3 所在子树以r3 的 x 坐标值横向分割为两子树节点r4的 x坐标值大于r3 ，则r3存储在右节点。 取出r5经根节点与r1 x 坐标值比较进入左子树，左子树为空，则直接将r5子树，无需再此分割 其时间复杂度同样为 Ologn 二.结构优化 由于 kd-tree 的构造形态跟插入记录的先后顺序有关，因此构造所得的树结构不一定是平衡的，图 所示的树结构即为不平衡二叉树。为了获取更稳定的查找速度，可以对树结构进行平衡化。但结构优化的时间复杂度很高，故仅适用于静态记录集。

多边形裁剪算法 刚参加工作就跟多边形刚上了，对于多边形的裁剪做一些简单的总结。 多边形裁剪主要有四种算法 Greiner-Hormann裁剪算法 Sutherland-Hodgman算法 Vatti裁剪算法 Weiler-Atherton裁剪算法 作为一名想要成为优秀算法工程师的程序员，我们不能只会使用，而不知道其原理，倘若如此，我们无法做到应用于本身业务上的定制化的修改。 一.Greiner–Hormann算法 Greiner–Hormann算法的性能要比 Vatti裁剪算法的性能高，但无法处理退化问题，它可以处理自相交和非凸多边形。可以简单地推广计算多边形上的其他布尔运算，例如并集和差集。 我们看如图4的实例，我们的任务是使用用虚线围成的多边形C裁剪我们的虚点围成的多边形S。 我们首先确定S多边形边界的哪些部分位于C多边形内.如图5。 我们可以通过考虑以下类比情况：想象一下沿着S多边形边界推动粉笔车。我们从S多边形的某个顶点开始，如果该顶点位于C多边形内，则在开始处用粉笔画。然后，我们沿着s多边形推动推车，每当我们穿过c多边形的边缘时，就会切换是否用粉笔画（打开/关闭）。当我们到达起始顶点时停止。然后，s多边形中位于c多边形内的部分将用粉笔标记。 完美！ 我们使用相同的技术，但这次沿着c多边形运行粉笔车，以发现c多边形中位于s多边形内的那些部分（图6）。 一旦我们找到了位于另一个多边形内的多边形边缘的所有部分，我们就合并这些部分以获得最后裁剪过的多边形（图7）。 merge过程很容易，考虑到将在结果中的s多边形的每个部分都由s多边形和c多边形的两个交点限定。这些顶点也是在c多边形的一个相关部分的开始或结束。因此，如果您跟踪交叉点和它们来自的部位，那么以正确的顺序连接支撑部位很容易。 二.Sutherland–Hodgman algorithm Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。 它的基本思想是什么呢，首先我们将c多边形的每一条边在两个方向上无限延伸，将整个空间一分为二。其中，空间中有一侧是我们要保留的可见侧，还有一侧是我们不需要的。 如果s多边形的顶点位于c多边形边上线的可见侧，则保留他们，生成新的多边形。 对每个c多边形边重复此过程，使用一个阶段的输出作为下一个阶段的输入。处理完c多边形的所有边后，最终生成的顶点列表将定义一个完全可见的多边形。请注意，如果s多边形在c多边形外的顶点处是凹形的，则新多边形可能有重合（即重叠）的边-这对于渲染是可以接受的，但对于其他应用程序（如计算阴影）则不是。 三.Vatti裁剪算法 与Sutherland-Hodgman和Weiler-Atherton多边形裁剪算法不同，Vatti算法不限制可用作s或c的多边形类型。甚至可以处理复杂（自相交）多边形和带孔的多边形。 目前来说，我使用的三方库Clipper就是使用的Vatti算法。所以这个方法非常的重要。 但是，文献要钱，网上找不到相关介绍，暂时算了，以后补上。 四.Weiler-Atherton 说实话，我本来就是要说剖析一下Clipper里用的布尔运算的算法，由于Vatti的原因，心情很沮丧，所以没心情了，放个链接把 https://blog.csdn.net/yangxi_pekin/article/details/37738219/

Bézier 方法是法国雷工程师 Bézier 首次提出的下面简单介绍 Bézier 曲线、曲面。该曲线是于 1962年提出的一种以逼近为基础的曲线，通过Bernstein 多项式得到。随着曲线和曲面研究的发展和深入，人们又提出了许多类似于Bézier 曲线的曲线。 Bézier 曲线的定义 一条 n 次 Bézier 曲线可以表示成下面的形式 $$ C ( u ) = ∑ i = 0 n B i , n ( u ) P i , 0 ≤ u ≤ 1 C(u)=\sum_{i=0}^{n}B_{i,n}(u)P_{i},0\leq u\leq 1 C(u )= i =0 ∑ n ​ B i,n ​ (u)P i ​ ,0≤u ≤1$$ 其中，基函数 $B i , n ( u ) B_{i,n}(u) B i,n ​ (u)$ 是n 次 Bernstein 多项式。其定义为， $B i , n ( u = C n i u i ( 1 − t ) n − i ) , i = 0 , 1 , 2 , 3 … … n B_{i,n}(u=C_n^iu^i(1-t)^{n-i}),i=0,1,2,3……n B i,n ​ (u= C n i ​ u i (1− t) n−i ),i =0 ,1, 2,3 ……n $。 第一哥狮子中的系数 $P i P_i P i $​ 称为控制顶点。由控制顶点之间的顺次连线组成的多边形我们成为控制多边形。

对于简单的mesh来说，我们当然不需要如此兴师动众的进行讨论。但是对于大多数的mesh来说，由于其表面是曲面，所以才需要我们进行讨论。 一.可能遇到的问题 最简单的，分段线性逼近需要很多块才能看起来good(逼真、光滑等)。 单个曲面点的集合将占用大量的内存存储。 二.解决方案 使用曲面坐标的高阶公式 上面的不行，那将曲面细分为可由简单公式表示的小块 问题是很明显的，首先是不够精确，第二是比较难实现 ##表示方法 有两种表示方法，第一是参数式的，第二是隐式的 参数式： $$( x , y , z ) = ( f ( u , v ) , g ( u , v ) , h ( u , v ) ) (x,y,z)=(f(u,v), g(u,v), h(u,v)) (x, y,z) =(f (u,v) ,g(u, v),h (u,v) )$$ 例如平面、球体、圆柱体、圆环、扫掠曲面等。 参数式可以通过控制u，v来控制精度。 非常适合生成多边形网格。 可以用于复杂的求交问题，如光线和平面，点是否在范围内。 隐式的： $$F ( x , y , z ) = 0 F(x,y,z) = 0 F(x ,y,z)= 0$$ 例如平面，球体，圆柱体，二次曲面，圆环.

Fract 得到这个值的小数部分 1 2 3 4 5 float fract(float x) vec2 fract(vec2 x) vec3 fract(vec3 x) vec4 fract(vec4 x) ![fract(x).png][1] y = fract(x); Mod 得到两个值的模,其实就是余数 1 2 3 4 5 6 7 8 float mod(float x, float y) vec2 mod(vec2 x, vec2 y) vec3 mod(vec3 x, vec3 y) vec4 mod(vec4 x, vec4 y) vec2 mod(vec2 x, float y) vec3 mod(vec3 x, float y) vec4 mod(vec4 x, float y) y = mod(x,1.