- 博客(44)
- 收藏
- 关注
RSS订阅原创 【Vulkan学习记录-基础篇-5】多线程渲染
现代的图形API都具备对多线程渲染友好的特性，所谓的多线程并不是指GPU端的多线程图像渲染，而是指在CPU提交DrawCall时所做的一系列工作可以并行化，也就是说多线程渲染其实是在CPU端提升程序的性能。在使用D3D 11或者OpenGL的时候，每次提交DrawCall之前，都需要将相关的状态进行更新，将需要用的资源进行绑定，在提交DrawCall时，还要进行相关的参数检查等工作，这些看上去耗...
2019-10-23 20:24:29
2594
原创 圆面、球面上的采样方法
（本文内容主要来自《pbrt》13.5、13.6）如果yyy满足概率密度分布p(y)p(y)p(y)，如果要随机地获取一个yyy的话，可以先获取一个随机数ttt，然后代入它的累积概率密度P(y)=tP(y)=tP(y)=t，然后求解出yyy即可。但是很多情况需要的不仅是对单个变量做采样，往往需要对多个维度下的多个变量进行采样，而这些多个变量之间很有可能有互相关联，并且直接采样也不容易，可以考虑...
2019-10-23 17:37:24
5681
1
原创 【Vulkan学习记录-基础篇-4】Vulkan中的同步机制
在Vulkan中，对资源读写所需要做的同步是应用程序的职责，Vulkan本身只提供了很少的隐式同步机制，其余的都需要在程序中显式地使用Vulkan中的同步机制来实现。提交顺序提交顺序是Vulkan中的一个非常基本的概念，它本身并不具有任何同步的意义，但是不管是Vulkan提供的隐式同步，还是用户要自己实现的显式同步，都要以这个精确的概念为前提。在Vulkan中，用户需要将命令写入Comman...
2019-09-27 23:37:50
3315
原创 【Vulkan学习记录-基础篇-3】纹理和模型导入、生成Mipmap
前两篇的代码是在太过于冗杂，于是我做了一下简单的封装，现在的代码结构为：VKApp 负责初始化窗口以及VkInstance、VkDeviceVKResourceCreator 负责创建各种资源（Image、ImageView、Buffer等）VKScene 负责初始化Pipeline RenderPass等，在每一帧中执行渲染VKCommand 负责创建所有可复用的命令（CopyBuff...
2019-08-09 23:48:26
1134
2
原创 【Vulkan学习记录-基础篇-2】用Vulkan画两个重叠的矩形
在前一篇中完成了对Vulkan的初始化和三角形的绘制，其中很多东西还没有被用到，这一节最终将绘制这样两个重叠的矩形，并且它们会一直绕着屏幕中心点进行旋转。将要补充使用的内容有：VertexBuffer、IndexBuffer、StagingBuffer、UniformBuffer的创建和使用，深度缓冲的创建和设定。代码将基于第一节的内容进行增添和修改。1. 创建VertexBuffer、I...
2019-08-06 11:21:50
1486
原创 【Vulkan学习记录-基础篇-1】用Vulkan画一个三角形
好久没有更新过博客了，上半年一直忙着找实习的事情，不过现在已经入职一段时间了，也可以抽出时间来继续整理一些内容，所以最近会尽量变得勤快一点来写博客。Vulkan是新一代的图形API，具有跨平台、高性能的优势，它强调减少对驱动的依赖性，和传统的图形API（例如OpenGL、Direct3D）相比，它需要程序员自己在程序方面做以往驱动做的事情，因此Vulkan的代码量会比传统的图形API多很多，学习...
2019-07-30 14:59:57
6952
3
原创 TrueType字体文件解析和字体光栅化
本文主要记录一下这几天做的一个小Demo，它能够读取.ttf格式的字体文件，获取其中的相关数据，将得到的字体信息光栅化处理后输出到一张PNG文件中，最终输出的结果如下：有兴趣的可以参考一下源码：https://github.com/syddf/TTFFontRenderTTF文件解析首先要注意ttf采用的是大端编址，即最低位的字节在最后面，而最高位的字节在最前面，如果所在的环境用的是小...
2019-03-16 16:42:05
8541
7
原创 pbrt源码中用全主元消去法求矩阵逆的实现
《pbrt》一书配套源码上对于矩阵求逆使用的是全主元消去法，但是它的实现与我所见到过的全主元消去法还是略有不同的，有的地方还是值得思考一下的。学过线性代数的应该都知道求矩阵的逆有伴随矩阵法和初等变换法等方法，而高斯消元法、列主元消去法、全主元消去法这些算法都基于初等变换法，简单说一下，对于矩阵AAA，我们想要求一个矩阵BBB，使得AB=IAB=IAB=I，那么可以先对AAA做一系列的初等行（列）...
2019-02-06 01:10:47
486
原创 平方根倒数的一个快速近似计算算法
已知一个浮点数xxx，现在需要求1x\frac{1}{\sqrt{x}}x1，这是一个非线性方程组的求解问题，可以采用不动点迭代法、牛顿迭代法之类的方法来解决。但是早在上个世纪，在游戏《Quake III》中，开发者就采用了一种非常快速求解这个问题的算法，这个算法非常有意思，而且现在也被一些GPU在硬件上实现，下面来看一下它的思路。首先，设xxx按照IEEE浮点数表示规则对应的无符号整数为I...
2019-01-01 22:09:27
1573
原创 非线性方程的数值解法
设有一个单变量的非线性方程f(x)=0f(x) = 0f(x)=0，往往这样的方程没有直接的求根公式，因此没有直接方法计算，只能使用迭代法来求数值解，二分法就是这样的一种方法，这里介绍一下其他的几种方法不动点迭代法我们可以将非线性方程f(x)=0f(x) = 0f(x)=0改写为x=ϕ(x)x = \phi(x)x=ϕ(x)，满足这样式子的x称作ϕ(x)\phi(x)ϕ(x)的一个不动点，求f...
2018-12-30 20:48:48
3483
原创 快速傅里叶变换与快速数论变换
在拉格朗日插值法与牛顿插值多项式中有说明当给定n+1个点值序列(x0,y0)，(x1,y1)，⋅⋅⋅，(xn,yn)(x_0,y_0)，(x_1,y_1)，···，(x_n,y_n)(x0,y0)，(x1,y1)，⋅⋅⋅，(xn,yn)，其中任意两个xxx都互不相同时，有且只有一个n次多项式函数包含这些点值，换句话说，一个n次多项式可以由n+1n+1n+1个点值来表示，如果我们需要获...
2018-12-28 22:26:08
499
原创 拉格朗日插值法与牛顿插值多项式
多项式插值先有一个函数f(x)f(x)f(x)，如果给定在区间[a,b][a,b][a,b]上的n+1n+1n+1个点a&lt;=x0&lt;x1&lt;⋅⋅⋅&lt;xn&lt;=ba&lt;=x_0&lt;x_1&lt;···&lt;x_n&lt;=ba<=x0<x1<⋅⋅⋅<xn&
2018-12-28 18:57:37
10881
原创 TSP问题总结归纳
TSP问题即旅行商问题，经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密尔顿回路。旅行商问题有很多种不同的问法，最近做了几个关于TSP的题，下面总结一下。由于大部分TSP问题都是NP-Hard的，因此很难得到什么高效...
2018-10-26 13:02:07
70491
5
原创 智能指针内容整理
智能指针这个东西想必学过C++的人都应该听说过或者使用过，但是应该有一些人和我一样对其只有一点浅显的认识，今天查了一些关于智能指针的资料，下面对其做一些整理：为什么要有智能指针在用C++动态内存分配的时候，使用new操作获取了一块内存，那么一定要在合适的地方将其delete掉，否则就会造成内存泄漏，这一点都明白，但是实际操作的时候总是会忘记这个delete操作，而智能指针就是为了避免这样一个问...
2018-10-03 17:32:58
507
原创 求解最大流的四种算法介绍、利用最大流模型解题入门
上一篇中介绍了网络流的基础，最大流最小割定理的证明，下面来看如何求一个容量网络的最大流，这里介绍四种算法：EK算法、SAP算法、DINIC算法、HLPP算法。这四种算法中，前三种基于增广路，最后一种基于预流推进。基于增广路的算法Ford-Fulkerson算法先来简单提一下Ford-Fulkerson算法。在上一节中证明了，如果一个可行流中没有增广路，那么此时这个可行流的流量就是最大流，因...
2018-09-22 15:03:41
30969
2
原创 网络流基础、最大流最小割定理以及证明
网络流的基本概念网络流问题都是建立在类似上图的有向图之上，有向图的边的权值代表容量。其中A代表源点，C代表汇点，一般考察的问题情景就是从A中流出流量，经过这些有向边，最终汇集到C中。像这样的具有源点和汇点，并且每条边的权值均为正数的有向图就被称作是容量网络，图中的这些边被称作是弧，弧的权值被称作弧的容量，它代表着能够通过这条弧的最大流量。而经过弧上的实际流量被称作弧的流量，所有这些弧的...
2018-09-15 17:10:45
11901
4
原创 线性时间求解点集所有点最近邻的Felzenszwalb算法
最近在做字体渲染的相关内容，利用FreeType可以提取出ttf文件中具体某个字符的轮廓图，这个轮廓图是二值化的图像，后续的处理需要用到图像上的每个点到字体轮廓线的最近距离，即要求平面上的每个点与轮廓线的最近邻。可以考虑使用KD树，这里介绍一下Felzenszwalb算法，它可以在O(KN)的复杂度内完成所有点的最近邻求解，其中K是点集的维度，N是点的总个数。一维情形的求解首先介绍一维...
2018-09-10 22:43:50
2432
1
原创 带权并查集
带权并查集需要先理解一般的并查集，不明白的可自行先搜索有关内容一般的并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性，如下图所示，这是一个并查集，其中箭头表示父子关系，可以看到这些边没有记录其他的任何信息。而有的时候在这些边中添加一些额外的信息可以更好的处理需要解决的问题，在每条边中记录额外的信息的并查集就是带权并...
2018-09-02 16:03:09
30553
31
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录6-离散傅里叶变换
本篇对应视频19-22节，讲义第六章离散傅里叶变换(DFT)的引入上一节提到了，一个信号不可能同时在时域和频域受限，而我们现实世界中的信号往往在时域和频域中都是有限的，因此这两者存在很大的冲突。在计算机中，也不能够处理连续的信号，只能将处理它的离散形式。也就是说我们的目标是： 1.将时间ttt限制在一定范围内：0&amp;lt;=t&amp;lt;=L0&amp;lt;=t&amp;lt;=L0sss限制在一定范围：0...
2018-08-22 23:49:43
562
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录5-采样和插值
本片对应视频16-19节 讲义第五章Ш函数的引入 现在有一个函数如上图左所示，如果要把它周期延拓至无穷远如上右图，可以写出Pρ(x)Pρ(x)P_ρ(x)的表达式为：Pρ(x)=∑k=−∞∞P(x−kT)=∑k=−∞∞P(x)∗δ(x−kT)Pρ(x)=∑k=−∞∞P(x−kT)=∑k=−∞∞P(x)∗δ(x−kT)P_ρ(x) = \sum_{k=-\infty}^{\infty}...
2018-08-21 17:21:47
814
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录4-分布以及分布的傅里叶变换
本篇对应视频11-15节，讲义第四章。在第三章中，曾经提到了，对于函数f(x)=1f(x)=1f(x) = 1，是没有办法求它的傅里叶变换的，原因在于f^=∫∞−∞e2πist⋅1dtf^=∫−∞∞e2πist·1dt\hat{f} = \int_{-\infty}^{\infty}e^{2\pi ist} · 1 dt中等式右侧的这个积分式在经典微积分理论下是不可积的，还有比如说f(x)=s...
2018-08-21 13:51:21
2121
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录3-卷积
本文是对斯坦福大学公开课-傅里叶变换及其应用的一些学习总结 对应的课程视频链接为：课程链接 课程用到的讲义下载地址：讲义链接本篇对应视频8-10节，讲义第三章，有关卷积的一些内容。卷积的由来对于两个函数fff、ggg，它们的傅里叶变换为f^f^\hat{f}、g^g^\hat{g}，不难得出f^+g^=f+g^f^+g^=f+g^\hat{f}+\hat{g} = \hat{f...
2018-08-19 00:04:42
1425
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录2-傅里叶变换
本文是对斯坦福大学公开课-傅里叶变换及其应用的一些学习总结 对应的课程视频链接为：课程链接 课程用到的讲义下载地址：讲义链接傅里叶变换的内容对应课程5-8节，讲义第二章。由傅里叶级数到傅里叶变换在前面介绍了利用傅里叶级数将一个周期函数表达为由一组正交的函数组线性表出的形式，那么对于那些非周期函数，是否也能将其以这样的形式表示呢？注意到，对于每个非周期函数，其实可以将其看做是周期...
2018-08-17 15:54:27
2481
原创 斯坦福大学公开课-傅里叶变换及其应用-学习记录1-傅里叶级数
本文是对斯坦福大学公开课-傅里叶变换及其应用的一些学习总结 对应的课程视频链接为：课程链接 课程用到的讲义下载地址：讲义链接傅里叶变换这一名词已经在很多地方都有见过了，之前也是对其有一些粗略的了解，那么现在想跟着这个课程与讲义稍微深入一点地学习，在这里记录一下个人的总结与感悟。第一篇对应课程的第1-5节，讲义的第一章，即傅里叶级数。傅里叶级数在高数中已经学过了，但是当时只是以应付考试的...
2018-08-16 00:47:29
1963
原创 洛谷P1032-子串变换 广搜和STL
题目大意是给定原始字符串A和目标字符串B 并提供一些子串的提供方案，如果串中存在某个子串a，则可以将其替换为子串b。 求解的问题是至少经过多少次子串替换可以让A变换到B，如果替换次数超过10次或者不能变换到B，则表示问题无解。例如输入： abcd xyz abc xu ud y y yz 输出为3 表示abcd经过3次子串替换后可以得到xyz。这个题很显然是一个广搜题，因为...
2018-08-12 10:57:13
173
原创 关于四元数的一些总结
关于四元数的内容也是看过两次了，但总是容易忘记，这次打算好好总结一下以免再忘了= = 为什么要用四元数在计算机图形学中，作旋转变换有两种方法，一种是欧拉角，另一种就是四元数。用欧拉角会有万向节死锁的问题，而四元数则弥补了这个缺陷，是最好的实现旋转的方案。 欧拉角与万向节死锁 在线性代数中肯定学到了旋转矩阵这个东西，它可以用来作旋转变换，而这里的旋转矩阵只能代表绕着某个坐标...
2018-08-11 10:53:56
5277
3
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-6-High Level Shading Language
Introduction在DirectX中，编写可编程Shader的时候所使用的语言为High Level Shading Language(HLSL)，它是由C/C++衍生出来的一种语言，具有一些特性，它的语言风格与C语言非常相似，但是又有很大的不同。最重要的不同之处在于在HLSL中没有指针、没有C++中的template、不支持动态的内存分配。HLSL语言写出来的程序，都要在C/C++中提...
2018-07-31 17:40:14
272
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-5-The Computation Pipeline
Introduction在前面已经介绍了Rendering Pipeline，而在这本书的开头就说过，Direct3D中的流水线有两个，一个是Renering Pipeline，而另一个是Computation Pipeline，它只有一个阶段，Compute Shader Stage，代表着一种叫做DirectCompute技术的实现。现在的GPU是由非常多的可以并行运行的小型处理器构成的，...
2018-07-30 20:58:37
256
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-4-The Tessellation Pipeline
在前一章中有介绍到Tessellation的三个阶段：Hull Shader、Tessellation、Domain Shader，但是有一些细节是没有讲到的，这一章更加详细的讲述了跟Tessellation有关的内容。Introduction表示一个参数曲面的方式通常有两种：NURBS和SubDivisionSurfaces，前者是以数学的形式表达的曲面，具有很好的光滑性；而后者则通...
2018-07-30 15:29:43
239
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-3-Direct3D 11 The Rendering Pipeline
本章是这本书最长的一章，也比较枯燥= = 这一章详细介绍了流水线各个阶段的一些细节。对于流水线的每一个环节，需要注意它的输入、配置、处理过程、输出。 下面进行逐个的总结：Input AssemblerInput Assembler(输入装配阶段)是流水线的第一个阶段，在一个流水线中，被处理的对象都是一系列的顶点，因此在这个阶段就进行将顶点的数据以流水线中规定的形式输入到流水线中。 ...
2018-07-28 22:39:34
822
原创 天空盒(SkyBox)的实现原理与细节
天空盒的原理在实时渲染中，如果要绘制非常远的物体，例如远处的山、天空等，随着观察者的距离的移动，这个物体的大小是几乎没有什么变化的，想象一下远处有一座山，即使人走进十米、百米、甚至千米，这座山的大小也是几乎不怎么改变的，这个时候可以考虑采用天空盒技术。 所谓的天空盒其实就是将一个立方体展开，然后在六个面上贴上相应的贴图，如上图所示。 在实际的渲染中，将这个立方体始终罩在摄像机的周围，让...
2018-07-26 17:26:22
56714
3
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-2-Direct3D 11 Resources
这本书的第二章花了近80页的篇幅来具体介绍D3D11中的资源，并给出了一些资源创建使用的具体方法，各种资源有些非常相似而又有不同，因此很有必要做一个总结归纳。资源总览首先要明确一点，资源的本质就是内存块，这些内存块可以被GPU来读取和操控。 在第一章中已经提到了，D3D11中的资源无非就两类：Buffer和Texture，并且它们各自都有自己的子类，但不同种类的资源的本质都是相同的，...
2018-07-20 17:47:42
832
原创 BRDF·基于物理的着色技术学习总结
基于物理的着色真的不是特别好理解···在这里记录一下自己比较粗浅的认识···立体角要了解BRDF的相关内容，首先要对立体角有一定的理解。立体角是对平面角在三维空间的一个扩展。平面角就是一个顶点两条射线围成的那个角度，它的大小等于单位圆上的弧长，单位是弧度或者度，那么类比到三维空间，立体角就是从一个顶点发出的一个锥体所围成的一个三维角度，它的大小等于单位球上的面积，单位是球面度，一个单位...
2018-07-18 15:41:13
13731
2
原创 《Practical Rendering & Computation with Direct3D11》读书总结 Chapter-1-Overview Of Direct3D 11
章节概括本章主要简要描述了Direct3D的架构以及它是如何与GPU硬件交互的、简要探讨了D3D11中的Pipeline，介绍了一些组件，最后以一个简短的Direct3D初始化的例子介绍了对于Dx的初始化需要做哪些工作。1.1 Direct3D 的框架Direct3D是一套用来与显卡交流并控制显卡的Native API，并以此来渲染图像。之所以说它是Native的，是因为它被设计成可以...
2018-07-15 00:24:46
727
原创 洛谷-P2024 食物链 并查集应用
题目描述 动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道 它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是“1 X Y”，表示 X 和 Y 是同类。 第二种说法是“2 X Y”，表示 X 吃...
2018-07-14 14:16:21
322
2
原创 LeetCode 10 & 44 正则表达式匹配 & 通配符匹配 字符串匹配问题
10 正则表达式匹配 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符。 ‘*’ 匹配零个或多个前面的元素。 匹配应该覆盖整个字符串 (s) ，而不是部分字符串。说明:s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 示例 1:输入:...
2018-07-13 12:35:09
1400
原创 几种凹凸贴图(Bump Mapping)的学习记录
凹凸贴图简介凹凸贴图是纹理的一种应用，它主要用来实现类似砖块、墙体的那种凹凸不平的效果，相较于一般的纹理映射，它并不是通过纹理映射来改变材质本身的颜色，而是改变或扰动其法线的方向，而法线的方向被用在光线模型中，改变法线的方向就可以影响物体表面光照的明暗效果。因此，凹凸贴图实际上是一种欺骗式的手段，它并没有改变顶点的位置，让物体本身的模型变得凹凸不平，而是影响用户的视觉效果，让用户以为模型是凹凸...
2018-07-12 21:31:58
20829
3
原创 leetcode 32 - 最长有效括号
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。示例 1:输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2:输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”分析： 一种想法是用栈来解决括号匹配问题，这种方法可行，但我更想用DP的方法来解决。 一开始是考虑用dp[i][j] 表...
2018-07-12 11:14:52
960
2
原创 LeetCode 31 & 81 旋转数组搜索问题
31假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。示例 1:输入: nums = [4,5,6,7,0,1,2], target =...
2018-07-10 11:26:00
413
原创 LeetCode 18 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为：[ [-...
2018-07-09 10:46:26
144
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人