/images/avatar.png

Papalqi

多边形裁剪算法

多边形裁剪算法 刚参加工作就跟多边形刚上了,对于多边形的裁剪做一些简单的总结。 多边形裁剪主要有四种算法 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 首次提出的下面简单介绍 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$$ 例如平面,球体,圆柱体,二次曲面,圆环.

基础shader函数 与对应曲线

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.

UE4材质制作UV贴图

我们想要制作一张uv贴图,是一个什么意思呢?我们知道一般来说,我们都是根据uv来采样贴图,一般来说这个事情都是美术同学来制作的,所以我们想要进行的是在UE4中,动态或者根据自己的实际情况来生成一张贴图,并且我们要存储的内容也可以自己定。你可以自己生成法线贴图,或者是世界坐标的贴图,等等,并不拘泥于只存储颜色信息。 那么,我们如何进行相关的操作呢。 渲染目标 首先我们要做的就是生成一张RT,也就是renderTarget, 在内容浏览器中,我们进行创建,这里我们要创建两个RT。创建后,打开它们并将分辨率设置为所需的分辨率。一个大概的尺寸是1024x1024。你可以随便给它们起个名字,但我建议给它们起个名字:rt_scenecapture然后rt_expanded以避免以后混淆。 展开材质 制作一个新材质,并将其设置为“Unlit ”和“Two Sided”(防止任何光照贴图UV都被镜像,这将导致它们在展开时背面不清晰)。然后将这些节点插入到材质的世界位置偏移输入中。“Size”将是您设置的Scene Capture actor的Orthographic width。在本例中,我们将使用之前文章提到的BoundingBox0-1UV连接到自发光上。这很有用,因为它可以用于在光线跟踪或光子映射时检查材质中的光线位置。 The Actor Blueprint 接下来我们将制作一个新的蓝图Actor并添加一个“场景捕捉组件2d”组件。 选择组件并将“投影类型”(Projection Type)设置为“正交”(Orthographic)并将“正交宽度”(Ortho Width)设置为1000,以匹配“UV展开大小”(UV Unwrap Size)1000。将纹理目标设置为我们在第一步中创建的rt_scenecapture。同时将位置设置为0,0,500,并将旋转设置为-90,-90,0。这是为了从自顶向下的视图匹配UV展开的方向。最后,将“Capture Every Frame”设置为false,以防止它无缘无故地连续捕捉。 接下来,将“静态网格”组件添加到蓝图中,并将其所有设置保留为默认值。然后添加一个新变量,使其成为“静态网格”类型并使其可编辑(变量右侧的这个小眼球按钮)。 现在转到蓝图的构造脚本,放置一个“set static mesh”节点,该节点将静态网格组件设置为使用您创建的“static mesh”变量。接下来,添加一个“Set Material”节点并指定前面提到的展开材质。具有多个材质元素的静态网格可以使用“get num materials”-1作为最后一个索引的forloop将展开材质指定给所有元素。 现在我们只需要在事件图中添加一些蓝图节点。首先,我们放置一个“自定义事件”并将其命名为“Dilate”。在这次活动中,我们只做了两件事。首先我们告诉场景捕捉来捕捉图像。然后我们调用“Draw Material to Render Target”函数。我们将膨胀材质用作材质,将第二个渲染目标rt_expand用作指定的渲染目标。 一旦将此数据写入渲染目标,通常可以使用实际的渲染目标执行所需的任何操作,因为位置贴图在HDR形式下最有效。如果要创建扩张纹理的静态纹理,可以在内容浏览器中的渲染目标上单击鼠标右键,然后选择“创建静态纹理”:

UE4 编译系统

UE4 编译 UE4的游戏代码工程,从工程的属性可以得知,Build/Clean/Rebuild都是依赖于UBT(Build.bat、Clean.bat和Rebuild.bat)。生成sln文件也依赖于UBT。 1 2 3 4 5 6 # Build Engine\Build\BatchFiles\Build.bat # ReBuild Engine\Build\BatchFiles\Rebuild.bat # Clean Engine\Build\BatchFiles\Clean.bat Generate 这里面的所有配置其实都是我们调用Generate的时候自动为我们添加进去的,我们需要首先看我们Generate 的时候会发生什么,之后是分析这些脚本主要是做了什么。 Generate Visual Studio project files 我们Generate的时候,依旧是调用UE4的脚本GenerateProjectFiles.bat。 1 2 3 4 5 call "%~dp0GetMSBuildPath.bat" call "%~dp0FixDependencyFiles.bat" call "%~dp0FindPlatformExtensionSources.bat" ..\Binaries\DotNET\UnrealBuildTool.exe -ProjectFiles %* GetMSBuildPath.bat:首先我们查看系统中是否存在MSBuild。MSBuild全称(Microsoft Build Engine),是用于构建应用程序的平台。在使用VS做开发,那么一定时时刻刻在使用它。因为是它在背后为你管理生成你的项目文件。当新建一个项目时,注意下项目文件夹中的*.*proj文件就是为MSBuild提供的,这是个文本文件,基于XML格式,里面包含有项目所包含的文件,生成配置,输出配置等信息。 FixDependencyFiles.bat:检测编辑器使用的Icon。 md ..\Intermediate\Build >nul 2>nul将对应目录清空 Intermediate文件主要初始化了一些马上要用的空文件夹,和在/Build/BuileRules文件夹下的UBT扫描模块时生成的地址(.txt),动态库(.dll),pdb(调试信息文件);还在ProjectFiles文件夹中生成了一些UE4和项目的工程配置文件。 dir /s /b Programs\UnrealBuildTool\*.

Shader曲线总结

Impulse 曲线 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 #ifdef GL_ES precision mediump float; #endif uniform vec2 u_resolution; uniform vec2 u_mouse; uniform float u_time; // Function from Iñigo Quiles // www.iquilezles.org/www/articles/functions/functions.htm float impulse( float k, float x ){ float h = k*x; return h*exp(1.