如何在八叉树里寻找离某位置最近的点?

July 29th, 2021 No comments

第一步:如果给定点 z 在八叉树包围盒内就从所属的最末端的子包围盒叶子节点开始,如果在八叉树外的话就从任意最靠近的叶子节点开始,先找一个最靠近 z 的候选点 A,如果叶子节点包围盒是空的,就递归向上,总之先找到第一个候选点 A。

第二步:以 z 为圆心,z 到 A 的距离为半径,做一个球体 S,把球体 S 同八叉树求交(离 z 最近的点一定落在这个球体范围内),筛选出有交集的叶子节点包围盒,然后迭代这些叶子节点包围盒里的点,一旦找到更近的就缩小球的范围,这样就能找到离 z 最近的点了。

如果要找前 k 个距离最近的点,你需要维护一个长度为 K 的优先队列(或者最大堆),在找到最近邻居的基础上,将兄弟节点邻近的候选点都填充到队列里,直到队列里装满 k 个点,此时以 z 为圆心,队列里第 k 个离 z 最近的点为半径,对八叉树做一次范围搜索(前 k 个点一定落在该范围内),搜索过程中不断更新优先队列并及时根据最新的第 k 个点离 z 的距离调整半径。

Categories: 图形编程 Tags:

新版瑞士军刀:socat

January 31st, 2021 No comments

我在《用好你的瑞士军刀:netcat》中介绍过 nc 和它的几个实现(bsd, gnu, nmap),netcat 还有一个最重要的变种 socat (socket cat),值得花一篇完整的文章介绍一下,它不仅语义统一,功能灵活,除了完成 nc 能完成的所有任务外,还有很多实用的用法:

基本命令就是:

socat [参数]  <地址1>  <地址2>

使用 socat 需要提供两个地址,然后 socat 做的事情就是把这两个地址的数据流串起来,把第左边地址的输出数据传给右边,同时又把右边输出的数据传到左边。

最简单的地址就是一个减号“-”,代表标准输入输出,而在命令行输入:

socat - -              # 把标准输入和标准输出对接,输入什么显示什么

就会对接标准输入和标准输出,你键盘敲什么屏幕上就显示什么,类似无参数的 cat 命令。除了减号地址外,socat 还支持:TCP, TCP-LISTEN, UDP, UDP-LISTEN, OPEN, EXEC, SOCKS, PROXY 等多种地址,用于端口监听、链接,文件和进程读写,代理桥接等等。

因此使用 socat 其实就是学习各类地址的定义及搭配方法,我们继续以实用例子开始。

网络测试

这个类似 nc 的连通性测试,两台主机到底网络能否联通:

socat - TCP-LISTEN:8080               # 终端1 上启动 server 监听 TCP
socat - TCP:localhost:8080            # 终端2 上启动 client 链接 TCP

在终端 1 上输入第一行命令作为服务端,并在终端 2 上输入第二行命令作为客户端去链接。

联通后在终端2上随便输入点什么,就能显示在终端1上,反之亦然,因为两条命令都是把标准输入输出和网络串起来,因此把两个地址交换一下也是等价的:

socat TCP-LISTEN:8080 -               # 终端1 上启动 server 监听 TCP
socat TCP:localhost:8080 -            # 终端2 上启动 client 链接 TCP

因为 socat 就是把左右两个地址的输入输出接在一起,因此颠倒左右两个地址影响不大,除非前面指明 -u 或者 -U 显示指明数据“从左到右”还是“从右到左”。

同 netcat 一样,如果客户端结束的话,服务端也会结束,但是 socat 还可以加额外参数:

socat - TCP-LISTEN:8080,fork,reuseaddr      # 终端1 上启动 server
socat - TCP:localhost:8080                  # 终端2 上启动 client

服务端在 TCP-LISTEN 地址后面加了 fork 的参数后,就能同时应答多个链接过来的客户端,每个客户端会 fork 一个进程出来进行通信,加上 reuseaddr 可以防止链接没断开玩无法监听的问题。

刚才也说了使用 socat 主要就是学习描述各种地址,那么想测试 UDP 的话修改一下就行:

socat - UDP-LISTEN:8080               # 终端1 上启动 server 监听 UDP
socat - UDP:localhost:8080            # 终端2 上启动 client 链接 UDP

即可进行测试。

端口转发

在主机上监听一个 8080 端口,将 8080 端口所有流量转发给远程机器的 80 端口:

socat TCP-LISTEN:8080,fork,reuseaddr  TCP:192.168.1.3:80

那么连到这台机器上 8080 端口的所有链接,相当于链接了 192.168.1.3 这台机器的 80 端口,命令中交换左右两个地址一样是等价的。

(点击 Read more 展开)

Read more…

Categories: 网络编程 Tags:

如何实现一款 1KB 大小的空战游戏?

October 9th, 2020 No comments

经常看到知乎上有人在问:那些只有几 KB 的游戏是如何制作出来的?刚好这种代码我也写过,1KB 大小的空战游戏,很久以前读书时写的:

WINXP 下(或者 DOSBOX)在 DOS 窗口中运行 DEBUG,然后把横线下的内容复制、粘贴到 DEBUG 窗口中,回车就可以见到了。

(点击 Read more 展开)

Read more…

Categories: 游戏开发 Tags:

如何使用 C++ 写一个可编程软件渲染器?

September 24th, 2020 No comments

今天你想用最新的 D3D12 画一个三角形,少说也要上千行代码了,对于初学者来讲,这个门槛是非常高的,太多干扰了,而一千多行代码,已经足够你重头实现一个简易版 D3D 了,为什么不呢?比起从图形 API 入门,不如从画点开始,同样一千行代码,却能让你对 GPU 的工作原理有一个直观的了解。

因此,为了让希望学习渲染的人更快入门,我开源了一个 C++ 实现可编程渲染管线的教程:

那么网上软件渲染器其实不少,这个 RenderHelp 和他们有什么区别么?区别有三:

第一:实现精简,没依赖,就是一个 RenderHelp.h 文件,单独 include 它就能编译了,不用复杂的工程,导入一堆源文件,vim/vscode 里设置个 gcc 命令行,F9 编译单文件即可。

第二:模型标准,计算精确,网上很多软渲染器实现有很多大大小小的问题:比如纹理不是透视正确的,比如邻接三角形的边没有处理正确,比如 Edge Equation 其实没用对,比如完全没有裁剪,比如到屏幕坐标的计算有误差,应该以像素点方框的中心对齐,结果他们对齐到左上角去了,导致模型动起来三角形边缘会有跳变的感觉,太多问题了,对于强迫症,画错个点都是难接受的,RenderHelp 采用标准模型,不画错一个点,不算错一处坐标。

第三:可读性高,全中文注释,一千多行代码 1/3 是注释,网上很多同类项目,属于作者自己的习作,重在实现,做完了事,注释量不足 5%,一串矩阵套矩阵的操作过去,连行说明都没有,你想搜索下相关概念,连个关键字都不知道。RenderHelp.h 是面向可读性编写的,虽然也比较小巧,但重点计算全部展开,每一处计算都有解释。某些代码其实可以提到外层运行更快些,但为了可读性,还是写到了相关位置上,便于理解。

渲染效果图片:

使用很简单,include 项目内的 RenderHelp.h 即可,VS 和 PS 之间传参,主要使用一个 ShaderContext 的结构体,里面都是一堆各种类型的 varying:

// 着色器上下文,由 VS 设置,再由渲染器按像素逐点插值后,供 PS 读取
struct ShaderContext {
    std::map<int, float> varying_float;    // 浮点数 varying 列表
    std::map<int, Vec2f> varying_vec2f;    // 二维矢量 varying 列表
    std::map<int, Vec3f> varying_vec3f;    // 三维矢量 varying 列表
    std::map<int, Vec4f> varying_vec4f;    // 四维矢量 varying 列表
};

外层需要提供给渲染器 VS 的函数指针,并在渲染器的 DrawPrimitive 函数进行顶点初始化时对三角形的三个顶点依次调用:

// 顶点着色器:因为是 C++ 编写,无需传递 attribute,传个 0-2 的顶点序号
// 着色器函数直接在外层根据序号读取响应数据即可,最后需要返回一个坐标 pos
// 各项 varying 设置到 output 里,由渲染器插值后传递给 PS 
typedef std::function<Vec4f(int index, ShaderContext &output)> VertexShader;

每次调用时,渲染器会依次将三个顶点的编号 0, 1, 2 通过 index 字段传递给 VS 程序,方便从外部读取顶点数据。

渲染器对三角形内每个需要填充的点调用像素着色器:

// 像素着色器:输入 ShaderContext,需要返回 Vec4f 类型的颜色
// 三角形内每个点的 input 具体值会根据前面三个顶点的 output 插值得到
typedef std::function<Vec4f(ShaderContext &input)> PixelShader;

像素着色程序返回的颜色会被绘制到 Frame Buffer 的对应位置。

完整例子很简单,只需要下面几行代码就能工作了:(点击 Read more 展开)

Read more…

Categories: 图形编程 Tags:

OpenGL / DirectX 如何在知道顶点的情况下得到像素位置?

August 13th, 2020 No comments

DirectX 和 OpenGL 是如何得知对应屏幕空间对应的纹理坐标和顶点色的呢?一句话回答就是光栅化。

具体一点,实现的话,一般有两种方法:

Edge Walking

基本上所有基于 CPU 的软件渲染器都使用 Edge Walking 进行求解,因为计算量少,但是逻辑又相对复杂一点,适合 CPU 计算。具体做法分为三个阶段:

第一阶段:拆分三角形,将一个三角形拆分成上下两个平底梯形(或者一个),每个梯形由左右两条边和上下两条水平线(上底,下底)表示。

普通三角形可以拆分成上下两个平底三角形,不管是上面的那一半还是下面的那一半,都可以用一个平底梯形来表示(即上底 y 值 和下底 y 值,以及左右两边的线段),这样再送入统一的逻辑中渲染具体某一个平底梯形。

第二阶段:按行迭代,然后以梯形为单位进行渲染,先从左右两条边开始,一行一行的往下迭代,每迭代一次,y坐标下移1像素,先根据左右两边线段的端点计算出左右两边线段与水平线 y 的交点:

然后继续插值出左右两边交点的纹理坐标,RGB 值 之类的 varying 型变量,然后进入扫描线绘制阶段。

第三阶段:按像素迭代,有了上面步骤计算出来的一条水平线,以及左右端点的各种 varying 变量的值,那么就进入一个 draw_scanline 的紧凑循环,按点进行插值,相当于 fragment shader 干的事情。

计算 varying 变量插值的时候需要进行透视矫正,根据平面方程和透视投影公式,可以证明屏幕空间内的像素和 1/w 是线性相关的,而三维空间的 x / w, y / w, z / w 和屏幕空间也是线性相关的,也即各个 varying 变量按屏幕空间插值时需要先 / w,然后按照屏幕空间每迭代一个点时再除以最新的(1/w)就可以还原改点的真实 varying 变量值。

这部分可以参考我写的 700 行软件渲染器:

上面是第一种方法。

Edge Equation

这个方法简单粗暴,虽然计算量较大,但是计算方法简洁而单一,适合 GPU 实现,即按照三角形外接矩形(或者屏幕上任意矩形),两层 for 循环迭代每一个一个像素,先走一遍 Edge Equation 判断是否再三角形范围内,如果否的话就跳出,如果是的话,使用插值方式得到各个 varying 变量的值(纹理坐标,RGB顶点色和法线等)。

由于没有像 Edge Walking 一样迭代左右两边的每个像素,所以插值使用了一种“重心坐标”的公式,直接参考三个顶点的位置和当前点重心坐标来插值:(点击 Read more 展开)

Read more…

Categories: 图形编程 Tags:

关于 “帧同步” 说法的历史由来

August 2nd, 2020 No comments

关于游戏同步的话题说的太多了,我是不想再谈了,但是碰到一些含糊和容易引起混淆的地方,必须澄清一下,云风在 2018 年在《lockstep 网络游戏同步方案》中有一段:

首先,我认为把 lockstep 翻译成帧同步,还有与之对应的所谓“状态同步” (我在多次面试中听过这个名词),都是对同步算法的错误理解造成的。把自己所理解的算法牵强附会到已有的在欧美游戏先行者中经过实践的方案上。

最近网易雷火工作室的一篇文章《细谈网络同步在游戏历史中的发展变化》谈到了类似的观点,那么为了避免产生混乱,有必要对 “帧同步”这个说法做一次澄清。

帧同步不是单指某个具体算法,而是范指 “保证每帧(逻辑帧)输入一致” 的一系列算法,传统实现有帧锁定,乐观帧锁定,lockstep,bucket 同步等等,但凡满足“每帧输入一致”的方法皆可以归纳为帧同步类别,至于要不要回滚?服务端要不要跑一套完整逻辑?操作要不要是键盘鼠标?还是高阶命令?客户端要不要像视频播放器一样保证平滑缓存 1-2 帧?或者要不要保证平滑加一层显示对象的坐标插值?这些都是具体优化手段。

我在 2009 年公司应届生培训的《服务端开发培训》课程内,最早开始做同步技术培训:

这个 “帧间同步”喊着喊着就被喊成了“帧同步”,这应届生培训持续了好几年,应该数百人听过这个课程,后面的讲师又接着迭代这个 ppt 接着讲了好几年,听过的应届生们自己摸索后,又写了新的技术分享放到网上,兴许从那时候 “帧同步”和 “状态同步”的说法就流传开了吧。

(点击 Read more 展开)

Read more…

Categories: 游戏开发 Tags:

定点数优化:性能成倍提升

June 20th, 2020 No comments

定点数这玩意儿并不是什么新东西,早年 CPU 浮点性能不够,定点数技巧大量活跃于各类图形图像处理的热点路径中。今天 CPU 浮点上来了,但很多情况下整数仍然快于浮点,因此比如:libcario (gnome/quartz 后端)及 pixman 之类的很多库里你仍然找得到定点数的身影。那么今天我们就来看看使用定点数到底能快多少。

简单用一下的话,下面这几行宏就够了:

#define cfixed_from_int(i)      (((cfixed)(i)) << 16)
#define cfixed_from_float(x)    ((cfixed)((x) * 65536.0f))
#define cfixed_from_double(d)   ((cfixed)((d) * 65536.0))
#define cfixed_to_int(f)        ((f) >> 16)
#define cfixed_to_float(x)      ((float)((x) / 65536.0f))
#define cfixed_to_double(f)     ((double)((f) / 65536.0))
#define cfixed_const_1          (cfixed_from_int(1))
#define cfixed_const_half       (cfixed_const_1 >> 1)
#define cfixed_const_e          ((cfixed)(1))
#define cfixed_const_1_m_e      (cfixed_const_1 - cfixed_const_e)
#define cfixed_frac(f)          ((f) & cfixed_const_1_m_e)
#define cfixed_floor(f)         ((f) & (~cfixed_const_1_m_e))
#define cfixed_ceil(f)          (cfixed_floor((f) + 0xffff))
#define cfixed_mul(x, y)        ((cfixed)((((int64_t)(x)) * (y)) >> 16))
#define cfixed_div(x, y)        ((cfixed)((((int64_t)(x)) << 16) / (y)))
#define cfixed_const_max        ((int64_t)0x7fffffff)
#define cfixed_const_min        (-((((int64_t)1) << 31)))
typedef int32_t cfixed;

类型狂可以写成 inline 函数,封装狂可以封装成一系列 operator xx,如果需要更高的精度,可以将上面用 int32_t 表示的 16.16 定点数改为用 int64_t 表示的 32.32 定点数。

那么我们找个浮点数的例子优化一下吧,比如 libyuv 中的 ARGBAffineRow_C 函数:

void ARGBAffineRow_C(const uint8_t* src_argb,
                     int src_argb_stride,
                     uint8_t* dst_argb,
                     const float* uv_dudv,
                     int width) {
  int i;
  // Render a row of pixels from source into a buffer.
  float uv[2];
  uv[0] = uv_dudv[0];
  uv[1] = uv_dudv[1];
  for (i = 0; i < width; ++i) {
    int x = (int)(uv[0]);
    int y = (int)(uv[1]);
    *(uint32_t*)(dst_argb) = *(const uint32_t*)(src_argb + y * src_argb_stride + x * 4);
    dst_argb += 4;
    uv[0] += uv_dudv[2];
    uv[1] += uv_dudv[3];
  }
}

这个函数是干什么用的呢?给图像做 仿射变换(affine transformation) 用的,比如 2D 图像库或者 ActionScript 中可以给 Bitmap 设置一个 3×3 的矩阵,然后让 Bitmap 按照该矩阵进行变换绘制:

基本上二维图像所有:缩放,旋转,扭曲都是通过仿射变换完成,这个函数就是从图像的起点(u, v)开始按照步长(du, dv)进行采样,放入临时缓存中,方便下一步一次性整行写入 frame buffer。

这个采样函数有几个特点:

  • 运算简单:没有复杂的运算,计算无越界,不需要求什么 log/exp 之类的复杂函数。
  • 范围可控:大部分图像长宽尺寸都在 32768 范围内,用 16.16 的定点数即可。
  • 转换频繁:每个点的坐标都需要从浮点转换成整数,这个操作很费事。

适合用定点数简单重写一下:(点击 Read more 展开)

Read more…

Categories: 编程技术 Tags:

快除 255:到底能有多快?

June 13th, 2020 No comments

真金不怕火炼,我先前在《C 语言有什么奇技淫巧?》中给出的整数快速除以 255 的公式:

#define div_255_fast(x)    (((x) + (((x) + 257) >> 8)) >> 8)

有人觉得并没有快多少,还给出了测试

红色为 255 快除法的消耗时间,看他的测试好像也只快了那么一点,是这样的么?

并非如此,我们只要把测试用例中的 long long j 改成 int j 就有比较大的性能提升了:

链接:http://quick-bench.com/t3Y2-b4isYIwnKwMaPQi3n9dmtQ

这才是真实的快除法性能。

原评测的作者其他地方都是用 int ,这里故意改成 64 位去和原始的 / 255 对齐,引入一个干扰项,得到一个比较慢的结果,到底是为了黑而黑呢?还是别的什么原因?

编译器生成的 / 255 方法是把 x / 255 换成定点数的 x * (1/255):

(点击 Read more 展开)

Read more…

Categories: 编程技术 Tags:
Wordpress Social Share Plugin powered by Ultimatelysocial