Posts tagged 3d

在3D游戏中采用场景管理的意义

0
1 year ago
by windam in ,

我们常说3D引擎应当包含若干功能：材质，模型，动画等等，这些功能我们很好理解，模型是我们需要渲染的几何体，材质表现的是几何体如何对光照如何做出回应，动画（特别的，骨骼动画）往往是3D世界中可运动模型的基础。除了这些与渲染直接关联的概念之外，往往还有个与渲染看似无关的概念：场景管理。

游戏渲染当中常用的场景管理往往被称为Scene Graph：它的实现通常采用树状结构，构成它的基本单位是节点，一个节点可以有若干个子节点，并且（除了根节点之外）往往有且只有一个父节点。

在实际游戏当中，对于需要渲染的几何体，比如静态的Mesh或者有Skeleton的Mesh，其本身不包含世界变换信息，而是由其所处的节点决定其位置与朝向。很久以前读Ogre的源码看到它就是这么做的，然而问题是，为什么必须要这么做？我一直心存疑惑，如果不采用Scene Graph的方案，我们给每一个需要渲染的模型赋予世界变换信息，那么这个模型不是一样可以渲染么？为什么非要把变换信息与模型本身分离开？分开有什么好处？而不这样做又有什么缺点呢？

(more…)

DissolveMiddle.jpg

溶解效果的原理与实现#1

0
1 year ago
by windam in ,

在游戏中实现溶解效果，往往有两种选择：其一是采用多重纹理；其二是采用模板缓冲。

本文说明采用多重纹理方案时如何实现溶解效果，采用模板缓冲的方案容后再补。

Dissolve-Middle

上图是一个利用PixelShader达成的效果，其原理是，当我们把一个面片绘制到渲染表面上时，将特定像素的Alpha值设为0，从而在绘制到表面与背景混合时，达到镂空的效果。镂空的图案由美术指定一张Mask纹理确定。譬如在上图的效果中，我利用了下面这样的两张纹理图（左图是前景贴图，右图作为Mask），美术可以通过指定不同的Mask图，实现不同类型的逐渐消解/生成的效果：

06_11_2_moon dissolve

实现此效果需要两张贴图，一张是物体表面的纹理，另一张作为溶解的Mask图。

 

 

(more…)

2ae8af3cdeb4.png

Hermite Curve 在绘制轨迹中的应用

0
1 year ago
by windam in

 

在3D游戏的粒子系统中，往往可能有这样一类需求——伴随着人的动作，一条光带划过，或者伴随着武器的劈砍动作，一条刀光划过。

如果我们简单的在每次Tick的时候采样当前的位置朝向，并创建一截新的面片，往往会形成类似于如下图的粗陋效果：

不连续轨迹

之所以会产生一截一截的感觉，是由于在每次进行采样的时候，我们只能得到当前时刻的位置信息。因此尽管在从上一次到本次采样的过程中，轨迹实际经过的路程是一条平滑的曲线，可由于每一帧之间的时间不可能小到足够提供平滑曲线的采样精度，我们所能获得的总是一截截的折线。

怎样才能够通过为数不多的关键点，创造出一条平滑的曲线来呢？

Charles Hermite 提出的Hermite Curve解决了上面的问题。通过一系列的三维空间关键点，可以得到每个点处的切线，再经过Hermite Base Function的多项式计算，则可以得到插值点。

如图：

HermiteCurve示意

设P1，P2为平面上的两个点，T1，T2为两点处的切线，由点及点的切线，Hermite Spline就可以给出一个平滑过渡的曲线。

Hermite Base 多项式的参数如下表，其中t是从上一个点到当前点的插值系数。上一个点处为0，当前点为1。

Ogre在其Ogre::SimpleSpline类中实现了HermiteCurve。感兴趣的同学可以做以参考。

 

  expanded factorized
h00(t) t3 − 3t2 + 1 1 + 2t)(1 − t)2
h10(t) t3 − 2t2 + t t(1 − t)2
h01(t) − 2t3 + 3t2 t2(3 − 2t)
h11(t) t3 − t2 t2(t − 1)

事实上，上述做法也不过就是对Hermite Curve类型的样条曲线的利用而已。样条曲线实际上并不陌生，贝塞尔曲线就是一种我们关注最多的样条曲线。尽管其不适用于我们前述的场合——原因是贝塞尔曲线通过控制点计算出的曲线并非一条依次经过控制点的曲线。如下图所示（图片来源于:http://escience.anu.edu.au/lecture/cg/Spline/printCG.en.html）：

bezier_spline 

参考资料：

1. Hermite Curve Interpolation. Hamburg (Germany), the 30th March 1998

2. Cubic Hermite spline

3D地形学习笔记1–地形生成

0
2 years ago
by windam in

地形生成是一个很有意思的话题，通过简单的函数以及一些参数配置，就可以轻松的生成接近于自然地貌的地形。

 

两种众所周知的地形生成算法分别是

1、  Fault Formation

2、  Midponit displacement (又名diamond square)

 

Fault Formation 算法

这个算法的本质其实很简单。想象一个方块，在这个方块中随机取一个点为起始点，再随机选择一个方向，形成一条射线，然后将高度图中这个射线左侧（或者右侧）的部分全部添加一个Delta。重复上述步骤若干次，每次将添加的Delta减小一些，一个简单的高度图就可以生成出来了。

Delta应当与当前迭代次数与总迭代次数的比值成线性关系。

Delta = MaxHeight – (MaxHeight – MinHeight) * CurrentItr / TotalItr;

这样第一次迭代所产生的影响最大，而后的迭代中对整个高度图的影响依次递减，在之前的高度基础上继续增加高度图中的细节。通常来说，迭代次数越多，效果会越好。

 

实现FaultFormation的伪码如下:

 

Do_Formation(float* pfBuffer, int iLen, Point ptStart, Point ptEnd, float fDelta)

{

         Point ptDir = ptEnd – ptStart;

 

         For (int z = 0; z < iLen; ++z)

                   For (int x = 0; x < iLen; ++x)

                   {

                            Point ptDirCur = Point(x – ptStart.x, z – ptStart.z);

                            // 直线方程，判断一个点位于直线的上方或下方

                            If (ptDirCur.x * ptDir.x – ptCurDir.z * ptDir.z > 0)

                                     pfBuffer[z * iLen + x] += fDelta;

}

}

 

Proc_Fault_Formation(float* pfBuffer, int iLen, int iMinDelta, int iMaxDelta, int iIterationTimes)

{

         for (int iCurIteration; iCurIteration < iIterationTimes; ++iCurIteration)

         {

                   float fDelta = iMaxDelta – (iMaxDelta – iMinDelta) * iCurIteration / iIterationTimes;

                   Point ptStart = randomPoint();

                   Point ptEnd;

Do

ptEnd = randomPoint();

                   While (ptEnd == ptStart);

                   Do_Formation(pfBuffer, iLen, ptStart, ptEnd, fDelta);

}

}

 

按照上述思路实现的高度图生成算法，产生的图片如下：

迭代1次及32次时的效果：(为了区别背景色，我给图片增加了1像素的边框)

 

 

 

 

 

 

 

 

 

但是如果我们直接用这张图做地形的话，会遇到一个问题。地形的高度变化的边缘部分太过突兀了。我们需要增加一个模糊的步骤用以平滑高度突变(模糊可以采用任何一种模糊算法，比如常见的高斯模糊-有关高斯模糊的内容参考本文的附录)。

 

下图为增加了模糊处理，迭代32次的高度图。

 

使用Fault Formation算法生成地形的一个好处是分辨率不受限制，我们可以设置任意宽高的高度图。但是缺点是生成的地形细节往往不够丰富，不足以模拟大规模的地形场景。

 

Mid-point displacement算法是一种过程生成机制，特别适合用于生成较大规模的地形场景。

一篇很全面的介绍Mid-point displacement的文章可以参考 这里

关于Mid-point displacement的原理也可以参考 这里

 

单纯从算法上来看，Mid-point displacement所做的事情是很简单的：

该算法只能生成边长（一条边上的顶点数目）为2^n + 1的高度图。为什么有这个限制？原因是这个算法必须要以一个正方形为一个递归单元，每次处理完一个正方形后，都必须将其划分为4个更小的正方形加以处理。只有2^n + 1边长的正方形才能满足此切分条件。(2 = 2^0 + 1, 3 = 2 ^ 1 + 1, 5 = 2 ^ 2 + 1, 33 = 2 ^5 + 1, 1025 = 2 ^ 10 + 1 以此类推)

Midpoint displacement算法又名Diamond-square算法。该算法分为两个步骤：Diamond-step及Square-step。

 

算法的初始，我们需要给地形的四个角的顶点赋初值。这个值可以指定，或者随机产生。

如上图，四个角的值已有，为0, 2, 4, 8。而后，我们需要计算中点的值，图示中的3.5点的位置即为该图的中点。

中点值通过将四个角做算术平均，并增加一个小的随机值得到，随机值可以为正也可以为负。

上述步骤被称为Diamond-step。

接下来，我们只需要根据已有的四个顶点处的值，计算四条边的中点的算术平均值即可。

这一步被称为Square-step。

完成上述步骤之后，我们得到了四个更小一级的方块，分别对这四个方块重复上述步骤，直到当前块的边长为2时即可结束。

 

实际实现中，我们需要对所做的Displacement操作（即给中点附加一个随机值的操作），在每次迭代中，将随机的范围跟随当前边长逐步缩小。这样可以保障最终的高度图是逐步收敛并趋于稳定的。

 

该算法的实现伪码如下：

 

Displace(float cur_len, float total_len)

         Return (rand(0.0f, 1.0f) – 0.5f) * cur_len / total_len * 1.5f;

MidpointDisplacement(float* pfBuffer

, int x

, int y

, int len

, int pitch

, float top_left

, float top_right

, float bottom_left

, float bottom_right)

{

         Float mid_top, mid_left, mid_right, mid_bottom;

         Float middle;

         Int new_len = len / 2;

         If (len == 2)

         {

                   pfBuffer[y * pitch + x] = top_left;

                   pfBuffer[y * pitch + x + 1] = top_right;

                   pfBuffer[(y + 1) * pitch + x] = bottom_left;

                   pfBuffer[(y + 1) * pitch + x + 1] = bottom_right;

                   return;

}

 

Middle = (top_left + top_right + bottom_left + bottom_right) / 4 + Displacement(len, pitch);

Mid_top = (top_left + top_right) / 2;

Mid_left = (top_left + bottom_left) / 2;

Mid_bottom = (bottom_left + bottom_right) / 2;

Mid_right = (top_right + bottom_right) / 2;

 

         Clamp(middle, 0.f, 1.f);

         MidpointDisplacement(pfBuffer, x, y, new_len, pitch, top_left, mid_top, mid_left, middle);

         MidpointDisplacement(pfBuffer, x + new_len, y, new_len, pitch, mid_top, right_top, middle, mid_right);

         MidpointDisplacement(pfBuffer, x, y + new_len, new_len, pitch, mid_left, middle, bottom_left, mid_bottom);

         MidpointDisplacement(pfBuffer, x + new_len, y + new_len, new_len, pitch, middle, mid_right, mid_bottom, bottom_right);

 

}

 

使用上述算法所得的高度图如下：

 

左图是未经过模糊的版本，颗粒状比较明显，如果在实际的地形中，会导致凹凸感较强的失真情况，右图是经过模糊的版本。

 

参考文章：

Focus on 3D Terrain Programming (Trend Polack)

http://gameprogrammer.com/fractal.html

 

附录：关于高斯模糊

http://en.wikipedia.org/wiki/Gaussian_blur

 

二维高斯模糊的方程如下：

上述方程，用于通过制定的参数构造一个高斯滤波器（高斯滤波器是一个低通滤波器，会滤除信号中的高频部分–通俗的说就是突变较大的部分），该滤波器本质上就是一个R*R的矩阵，以该矩阵的中心点为原点，对矩阵中的每一个点(x,y)，将其值赋为G(x,y) ，则在该矩阵即被构造完成。

 

理论上说，高斯矩阵的所有项之和应当为1。

Wiki中给了一个当(with σ = 0.84089642)，R为7时的参考高斯矩阵：

 

0.00000067 0.00002292 0.00019117 0.00038771 0.00019117 0.00002292 0.00000067
0.00002292 0.00078633 0.00655965 0.01330373 0.00655965 0.00078633 0.00002292
0.00019117 0.00655965 0.05472157 0.11098164 0.05472157 0.00655965 0.00019117
0.00038771 0.01330373 0.11098164 0.22508352 0.11098164 0.01330373 0.00038771
0.00019117 0.00655965 0.05472157 0.11098164 0.05472157 0.00655965 0.00019117
0.00002292 0.00078633 0.00655965 0.01330373 0.00655965 0.00078633 0.00002292
0.00000067 0.00002292 0.00019117 0.00038771 0.00019117 0.00002292 0.00000067

 

 

高斯模糊的过程就是对原图像的每一个像素点，将上述矩阵的中心点对准该像素点，并以矩阵中的值为系数，将原图像上的位于当前矩阵范围内的像素点的值，乘以对应矩阵项的系数，并求和，而后重新赋予当前像素的过程。

 

模糊的过程较为简单，但是需要注意的是边界情况处理，当处理高斯矩阵的部分项超出原图像边界时，需要做一些特殊处理，以保障边界处的模糊是平滑的即可。

 

p.s.接下来的目标是整理一下地形渲染中纹理，光照，以及LOD的内容。

Go to Top