通过Mesh投影来实现贴花系统

在做FPS之类的游戏中,如果枪打到了墙角,并不能简单放置一来弹孔面片了事。而是要像一张贴纸一样,完全与墙角贴合。这时就需要去实现一个贴花系统来达到这种效果。

贴花系统有几种不同的实现方式,但这里仅考虑通过Mesh投影来实现贴花系统的实现原理。

这种方式的本质是,找到视野中贴花资源会影响的Mesh, 并创建一个同样大小以贴花资源为纹理的Mesh覆盖上去,从而达到贴花的目的。主要分下面两步来实现。

1. 先找到会受影响的物体,比如将弹孔贴在两面墙的夹角,那么受影响的物体就是两面墙。

怎么找到这两面墙不同的需求可能实现方式也不一样, 在场景编辑器中通过贴花来实现静态点缀效果,可以通过创建贴花资源的AABB盒来实现。如果是运行时动态创建弹孔也可以通过四次射线检测来达到,总之方式有很多。

2. 先创建一个半径为0.5单位的裁切立方体,在裁切坐标系中,贴花资源就被放在y=0平面中,贴花资源的中心就是裁切坐标系的(0, 0, 0)点。

需要说明的时这一步实际上并没有代码操作,只是一个数学抽象。我们的目的是要将所有受影响的三角形投影到y=0平面上,以便可以正确的采样贴花纹理。

3. 将受影响物体Mesh的所有三角形均转换到裁切立方体的坐标系之下对立方体的8个平面进行裁切。

在进行裁切之前,有一种情况需要处理,因为三角形是有朝向的,这个朝向是通过面法线来确定的(Unity中三角形的法线为Cross(v2-v1, v3-v1)),在正常的渲染流程中法线不能射入眼睛时,是不会被渲染的。在Unity中视锥体坐标系中,Vector3(0, 0, -1)是前向,因此眼睛的位置在Vector3(0, 0, 1)处。

在这个裁切立方体同样如此,不可能将纹理投影到一个三角形平面的背面,所以需要先先判断三角形的法线与Vector3(0, 0, 1)的夹角是否小于90度,只有小于90度才可能会被投影,才需要被裁切。

裁切时会出现,三角形完全在立方体外, 三角形完全在立方体内,三角形一部分在立方体外一部分在立方体内。前两种情况很好处理,但是第三种情况有可能会将一个三解形切成2个,因此需要格外注意。具体的裁切算法视锥体裁切算法一致,这里就不赘述。

4. 纹理采样,在创建三角形时,我们需要为每个一顶点指定一个uv坐标。前面已经说过了,我们的实现方式是将裁切后合法的三角形投影到裁切坐标系的y=0平面上, 投影之后的坐标为(x, 0, z). 因此uv可直接执行u = Lerp(0.0f, 1.0f, x + 0.5f), v = Lerp(0.0f, 1.0f, z + 0.5f).这里之所以加0.5f修正是因为立方体中心坐标为(0, 0, 0),这也意味着x,y,z的最小值均为-0.5f.

说了这么多附上源码一篇。需要说明的是,这个源码并不是我实现的,是我从网上找来之后修改的,毕竟我对Unity3d没有那么熟悉。

ps.单位相同的裁切立方体如何适应不同尺寸的贴花资源?在Unity中可以通过设置Scale拉伸坐标轴来实现,所以说3D数学真奇妙。

pps.在实现过程中发现,新创建的Mesh不能紧贴被覆盖的Mesh, 因为在相同的深度情况下,新创建的Mesh并不能保证一定在被覆盖的Mesh之后渲染,这会概率性出现新创建的Mesh与被覆盖的Mesh相互覆盖的情况。因为在创建完Mesh之后,需要根据平面法线上浮一点,以保证Z-Buffer正常工作。

三角形光栅化时遇到的坑

前一段时间打算写一个完整的游戏, 客户采用Unity3D引擎, 服务端则采用我自己的Silly网络框架

然而,最终这个项目烂尾了。烂尾的原因有很多,比如缺少资源,在不断寻找资源过程中使自己开发的热情消失殆尽等。但更为重要的是,我发现在使用Unity3D过程中,除了拼接UI逻辑时,没有碰到太大困难外。在实现一些3D效果时竟处处掣肘,甚至连最简单的贴花系统都实现不了。

而此时我的图形学背景是,《3D数学基础:图形与游戏开发》,《DirectX9.9 3D游戏开发编程基础》,《Unity Shader入门精要》和其他一些Unity操作手册。

这使我意识到,我的图形学知识结构出现了根本性问题。之后偶然的一个机会,我在网上接触到了“光栅化软件渲染器”的概念。深挖之下,发现这正是我目前所缺少的知识。

《3D数学基础:图形与游戏开发》介绍了“物体坐标系”,“世界坐标系”,“摄相机坐标系”等各种坐标系,以及如何实现一个数学引擎来实现各坐标系之间的转换。

《DirectX9.9 3D游戏开发编程基础》则介绍的是我们如何使用DirectX提供的各种API来使用相机,光照等各种抽象好的模型。

但是,这两本书之间存在着明显的断层,很难明白在调用DirectX提供的API之后,底层渲染是如何工作。例如,一个物体到底是如何一步一步画到屏幕上的,纹理是如何映射到3D物体上的,Shader到底是如何工作等。虽然这几本书,每一本都会讲一遍渲染流水线,但是这些细节很难被提到。

从零实现一个“光栅化软件渲染器”可以完美的填充这个空白,哪是一个效率很低的”软件渲染器”,这对理解3D渲染是如何工作起着至关重要的作用。幸运的是刚好有一本《3D游戏编程大师技巧》讲的就是这些内容(虽然我不是很认可他的章节安排:D)。


按照《3D游戏编程大师技巧》实现自己的软件渲染器的过程中,数学引擎,坐标系转换,甚至连光照都没碰到什么大问题,在最后一步将屏幕坐标系下的2D三角形光栅化时,踩了一个3连坑,导致一下耽搁了半个月才终于在昨天找到问题所在。

在光栅化的过程中,为了防止重复绘制相素,一般会采用左上(top-left)填充规则。例如绘制一个对角定点为(0, 0), (6,6)的正方形时,会避免为第6行和第6列绘制相素。大概实现伪码如下:

//void draw_pixel(int x, int y, int color);
int x, y;
for (y = 0; y < 6; y++) {
        for (x = 0; x < 6; x++) {
                draw_pixel(x, y, color);
        }
        ... do something ...
}

然而,看实简单的代码背后,却隐藏着各种坑。

在经过渲染流水线计算之后的图元(一般为三角形)坐标一般为float类型,而且大部分情况下都会有小数部分,比如(94.65, 331.64)。这时就需要制定一个规则,是向上取整(即将坐标变成(95,332))或者向下取整(即将坐标变成(94,331))。

为了省事,我的第一版直接采用了相下取整进行坐标映射,渲染伪码如下(这里仅仅将x,y的类型从int变成了float,因为向draw_pixel传参时,将float转成int采用的就是去1法):

//这里仅假设光栅化一个平顶三角形【(x0,y0), (x1, y1), (x2, y2)】并且(x0 < x1 && y0 == y1 && y0 < y2)。
//void draw_pixel(int x, int y, int color);
void draw(float x0, float y0, float x1, float y1, float x2, float y2)
{
        float x, y;
        float h = y2 - y1;
        float xleft_step = (x2 - x0) / h;
        float xright_step = (x2 - x1) / h;
        xleft = x0;
        xright = x1;
        for (y = y0; y < y2; y++) {
                for (x = xleft; x < xright; x++) {
                        draw_pixel(x, y, color);
                }
                xleft += xleft_step;
                xright += xright_step;
        }
}

然而这是不对的,一个最简单的例子,当【xstart=9.1,xend = 18.5】时,由于采用去1法映射相素坐标,因此理论上x方向绘制的相素坐标最大值应该小于18。但是当x=18.1上仍然会执行draw_pixel函数,此时经过传参转换后,x的值为18,这违反了左上规则(y轴同样存在这个问题)。

改良后第二版如下:

//这里仅假设光栅化一个平顶三角形【(x0,y0), (x1, y1), (x2, y2)】并且(x0 < x1 && y0 == y1 && y0 < y2)。
//void draw_pixel(int x, int y, int color);
void draw(float x0, float y0, float x1, float y1, float x2, float y2)
{
        int x, y;
        float h = y2 - y1;
        float xleft_step = (x2 - x0) / h;
        float xright_step = (x2 - x1) / h;
        xleft = x0;
        xright = x1;
        for (y = (int)y0; y < (int)y2; y++) {
                for (x = (int)xleft; x < (int)xright; x++) {
                        draw_pixel(x, y, color);
                }
                xleft += xleft_step;
                xright += xright_step;
        }
}

但是这依然不对, 当(x0, y0) = (2.1, 0.5)并且(x2, y2) = (7.1, 5.5) 时,代码实际绘制的第一个相素坐标为(2,0)。

但是根据直线【(x0, y0),(x2,y2)】的斜率可以算出当y=0时,x的值应该为1.1,换句话说理论上应该绘制的第一个相素坐标为(1, 0)。因此上述代码完美的将相素坐标(1,0)给避过去了,大部分情况下这种现象表现为,两个相邻的图元(这里指三角形)之间会有一条空白线(即两个三角形均没有绘制这条线)。

因此,当我们将y向下取整时,需要根据舍去去的小数修正x的值(因为斜率可能会非常大,有可能y只舍去了0.1,但是x会偏差好几个像素)。

修正版的代码如下:

//这里仅假设光栅化一个平顶三角形【(x0,y0), (x1, y1), (x2, y2)】并且(x0 < x1 && y0 == y1 && y0 < y2)。
//void draw_pixel(int x, int y, int color);
void draw(float x0, float y0, float x1, float y1, float x2, float y2)
{
        int x, y;
        float h = y2 - y1;
        float xleft_step = (x2 - x0) / h;
        float xright_step = (x2 - x1) / h;
        xleft = x0 - (y0 - (int)y0) * xleft_step;
        xright = x1 - (y0 - (int)y0) * xright_step;
        for (y = (int)y0; y < (int)y2; y++) {
                for (x = (int)xleft; x < (int)xright; x++) {
                        draw_pixel(x, y, color);
                }
                xleft += xleft_step;
                xright += xright_step;
        }
}

你以为事情就结束了么= =!

当直线【(x0, y0),(x2,y2)】的斜率为20时,y坐标向上取整时舍去y坐标0.5,x坐标会向左偏移10个坐标。这样原本(x0, y0) = (100, 10.5)的坐标经过取整后就会变成(80, 10)。这种错误大部分情况下表现为,三角形的顶部或底部突然多出一条直线。将所有逻辑改为向上取整,即可解决此问题。因为向上取整会保证所有坐标点都会落在原始三角形内,而向下取整会导致某些不在三角形内部。

修正版代码如下:

//这里仅假设光栅化一个平顶三角形【(x0,y0), (x1, y1), (x2, y2)】并且(x0 < x1 && y0 == y1 && y0 < y2)。
//void draw_pixel(int x, int y, int color);
void draw(float x0, float y0, float x1, float y1, float x2, float y2)
{
        int x, y;
        float h = y2 - y1;
        float xleft_step = (x2 - x0) / h;
        float xright_step = (x2 - x1) / h;
        xleft = x0 +(ceil(y0) - y0) * xleft_step;
        xright = x1 + (ceil(y0) - y0) * xright_step;
        for (y = ceil(y0); y < ceil(y2); y++) {
                for (x = ceil(xleft); x < ceil(xright); x++) {
                        draw_pixel(x, y, color);
                }
                xleft += xleft_step;
                xright += xright_step;
        }
}

至此,三连坑才算被踩完.


3月25日补充:

在进行仿射纹理映射时, 同样踩了两个坑。

1. 当y坐标向上取整时,相应的uv坐标需要采用与xleft和lright一样的算法进行修正。
2. 所有的纹理坐标范围是(0.0~1.0),在向位图坐标转换时(假设位图宽度为64×64)需要转换为(0, 63)

完整的修复代码在这里