Tag Archives: 图形

第一步：如果给定点 z 在八叉树包围盒内就从所属的最末端的子包围盒叶子节点开始，如果在八叉树外的话就从任意最靠近的叶子节点开始，先找一个最靠近 z 的候选点 A，如果叶子节点包围盒是空的，就递归向上，总之先找到第一个候选点 A。 第二步：以 z 为圆心，z 到 A 的距离为半径，做一个球体 S，把球体 S 同八叉树求交（离 z 最近的点一定落在这个球体范围内），筛选出有交集的叶子节点包围盒，然后迭代这些叶子节点包围盒里的点，一旦找到更近的就缩小球的范围，这样就能找到离 z 最近的点了。 如果要找前 k 个距离最近的点，你需要维护一个长度为 K 的优先队列（或者最大堆），在找到最近邻居的基础上，将兄弟节点邻近的候选点都填充到队列里，直到队列里装满 k 个点，此时以 z 为圆心，队列里第 k 个离 z 最近的点为半径，对八叉树做一次范围搜索（前 k 个点一定落在该范围内），搜索过程中不断更新优先队列并及时根据最新的第 k 个点离 z 的距离调整半径。

今天你想用最新的 D3D12 画一个三角形，少说也要上千行代码了，对于初学者来讲，这个门槛是非常高的，太多干扰了，而一千多行代码，已经足够你重头实现一个简易版 D3D 了，为什么不呢？比起从图形 API 入门，不如从画点开始，同样一千行代码，却能让你对 GPU 的工作原理有一个直观的了解。 因此，为了让希望学习渲染的人更快入门，我开源了一个 C++ 实现可编程渲染管线的教程： https://github.com/skywind3000/RenderHelp 那么网上软件渲染器其实不少，这个 RenderHelp 和他们有什么区别么？区别有三： 第一：实现精简，没依赖，就是一个 RenderHelp.h 文件，单独 include 它就能编译了，不用复杂的工程，导入一堆源文件，vim/vscode 里设置个 gcc 命令行，F9 编译单文件即可。 第二：模型标准，计算精确，网上很多软渲染器实现有很多大大小小的问题：比如纹理不是透视正确的，比如邻接三角形的边没有处理正确，比如 Edge Equation 其实没用对，比如完全没有裁剪，比如到屏幕坐标的计算有误差，应该以像素点方框的中心对齐，结果他们对齐到左上角去了，导致模型动起来三角形边缘会有跳变的感觉，太多问题了，对于强迫症，画错个点都是难接受的，RenderHelp 采用标准模型，不画错一个点，不算错一处坐标。 第三：可读性高，全中文注释，一千多行代码 1/3 是注释，网上很多同类项目，属于作者自己的习作，重在实现，做完了事，注释量不足 5%，一串矩阵套矩阵的操作过去，连行说明都没有，你想搜索下相关概念，连个关键字都不知道。RenderHelp.h 是面向可读性编写的，虽然也比较小巧，但重点计算全部展开，每一处计算都有解释。某些代码其实可以提到外层运行更快些，但为了可读性，还是写到了相关位置上，便于理解。 渲染效果图片： 使用很简单，include 项目内的 RenderHelp.h 即可，VS … Continue reading →

DirectX 和 OpenGL 是如何得知对应屏幕空间对应的纹理坐标和顶点色的呢？一句话回答就是光栅化。具体一点，实现的话，一般有两种方法：Edge Walking 和 Edge Equation。 两个我都完整实现过，下面分别介绍下具体原理： Edge Walking 基本上所有基于 CPU 的软件渲染器都使用 Edge Walking 进行求解，因为计算量少，但是逻辑又相对复杂一点，适合 CPU 计算。具体做法分为三个阶段： 第一阶段：拆分三角形，将一个三角形拆分成上下两个平底梯形（或者一个），每个梯形由左右两条边和上下两条水平线（上底，下底）表示。 普通三角形可以拆分成上下两个平底三角形，不管是上面的那一半还是下面的那一半，都可以用一个平底梯形来表示（即上底 y 值 和下底 y 值，以及左右两边的线段），这样再送入统一的逻辑中渲染具体某一个平底梯形。 第二阶段：按行迭代，然后以梯形为单位进行渲染，先从左右两条边开始，一行一行的往下迭代，每迭代一次，y坐标下移1像素，先根据左右两边线段的端点计算出左右两边线段与水平线 y 的交点： 然后继续插值出左右两边交点的纹理坐标，RGB 值 之类的 varying 型变量，然后进入扫描线绘制阶段。 第三阶段：按像素迭代，有了上面步骤计算出来的一条水平线，以及左右端点的各种 varying 变量的值，那么就进入一个 draw_scanline 的紧凑循环，按点进行插值，相当于 fragment … Continue reading →

网上有很多 256 个字节实现图形渲染的 “引擎”，他们的原理是什么呢？ 全都不是基于正统3D引擎的多边形绘制，而是基于少数特定情况的简化版光线跟踪算法 只能渲染特定几种物体，并不能渲染通用物体。 无资源或者少资源（基本靠生成），重复 16位代码，COM格式的可执行（没有PE头，代码数据和栈都在一个段内，指针只有两字节） 尽可能用汇编来写 你自己花点时间也能做出来， 具体解释一下： 简化版的 raycasting，实现起来的代码量比通用的多边形绘制方法至少 N个量级。 基本的光线跟踪，在 320×200 的解析度下，从摄像机中心射出 320×200条光线，屏幕上每个点对应一条光线，首先碰撞到的物体的位置颜色，就是屏幕上这个点的颜色： 可以描述为下面这段代码： for (int y = 0; y < 200; y++) { for (int x = 0; x < 320; x++) { DWORD … Continue reading →

写了文章《如何写一个软件渲染器》以后，不少网友希望进一步解释背后的数学公式，询问以及自己加一个 phong 光照该如何加，本文将对透视纹理映射的插值原理做一个简单的解释，希望能帮助到大家： 透视纹理绘制发生在最后阶段，坐标已经完成 projection，剔除，裁剪了，然后顶点/w，开始批量绘制扫描线之前，这时候开始计算纹理的位置。 使用 w 还是用 z，关系不大，早年的 3D 引擎，直接 /z 的，只是后面标准化了以后，发现 w 更好用，可以同时表示透视投影和正交投影。同时顶点经过标准的 mvp 矩阵运算后，w 和 z 是承线性关系的，方便对 z/w 做 [0,1] 的 cvv 裁剪。你可以理解成 w 就是另外一个 z。以前屏幕坐标： x’ = x / z * d + A y’ = … Continue reading →

如何正确的使用 OpenGL “封装一个2D引擎” ？以下几个步骤： 1. 别用什么 glBegin/glEnd，至少写兼容GLES2代码，不然手机上跑不起来。 2. 用两个三角形的纹理拼凑出一个2D的图块出来，不是搞啥每个点自己画。 3. 2D图像库基本就是要把显示对象树给做出来就得了。 4. 每个显示对象除了自己外还有很多儿子节点。 5. 每个显示对象有一个变换矩阵，用来设置位置和角度还有缩放，最后是节点的显示效果。 6. 渲染的时候需要从远到近排序，并尽量归并相同效果（fs）及纹理。 7. 把常用纹理管理起来，提供资源加载，可以换进换出，提供类 LRU的机制。 8. 在此基础上提供一些动画（精灵）和场景控制的api，提供显示字体，即可。 最后推荐两个现成的轻量级2D引擎供阅读： StarEngine：GitHub – StarEngine/engine: Crossplatform C++11 2D Game Engine for Desktop and Mobile games EJoy2D：GitHub – ejoy/ejoy2d: A … Continue reading →

以前 DOS下做游戏，操作系统除了磁盘和文件管理外基本不管事情，所有游戏都是直接操作显卡和声卡的，用不了什么驱动。 虽然没有驱动，但是硬件标准还是放在那里，VGA, SVGA, VESA, VESA2.0 之类的硬件标准，最起码，你只做320x200x256c的游戏，或者 ModeX 下 320x240x256c 的游戏的话，需要用到VGA和部分 SVGA标准，而要做真彩高彩，更高分辨率的游戏的话，就必须掌握 VESA的各项规范了。 翻几段以前写的代码演示下： 例子1： 初始化 VGA/VESA 显示模式 基本是参考 VGA的编程手册来做： INT 10,0 – Set Video Mode AH = 00 AL = 00 40×25 B/W text (CGA,EGA,MCGA,VGA) = 01 40×25 16 … Continue reading →

开源一个高性能位图库，之前对我的二维图形库 pixellib 的部分代码进行了精简和重写，最终形成一个只包含两个文件（BasicBitmap.h, BasicBitmap.cpp）的图形基础库。 在今天 GPU 绘制横行天下的时候，任然有很多时候需要使用到纯 CPU实现的图形库，比如图像处理，视频预处理与合成，界面，以及GPU无法使用的情况（比如某个应用把gpu占满了，或者无法通过gpu做一些十分灵活的事情时），纹理处理，简单图片加载保存等。 支持 SSE2/AVX 优化，比 DirectDraw 快 40%（全系统内存绘制），比 SDL 快 10%，比GDI快 38%。如果你需要一个方便的高性能位图库，足够高性能的同时保证足够紧凑。 如果你有上述需求，那么你和我一样需要用到 BasicBitmap，只需要把 BasicBitmap.h/.cpp 两个文件拷贝到你的代码中即可。我正是为了这个目的编写了这两个文件。 项目地址 https://github.com/skywind3000/BasicBitmap 特性介绍 高度优化的 C++ 代码，可以在任意平台编译并运行 多重像素格式，从8位到32位：A8R8G8B8, R8G8B8, A4R4G4B4, R5G6B5, A8, 等. Blit (Bit Blt) ，包含透明和非透明的模式。 像素格式快速转换 使用不同的 … Continue reading →