Shadow Volume详解(3)

事隔几个月之后，终于有时间把代码贴上来了。代码下载
今天在搞Hardware shadow map，有一点小进展，但是还是有不少距离。期待写shadow map系列















1.先说一下3ds文件的结构吧，只说跟投影有关的东西，就是它是包含多个object的，读进来的模型也是包含多个object的。
// 模型信息结构体

struct t3DModel
{
UINT    texture[MAX_TEXTURES];
    int     numOfObjects;               // 模型中对象的数目
    int     numOfMaterials;             // 模型中材质的数目
std::vector <tMaterialInfo> pMaterials;// 材质链表信息
std::vector <t3DObject> pObject;       // 模型中对象链表信息
};

2.首先执行阴影的初始化工作

//载入模型
g_model.Import3DS(fileName);  
// 初始化阴影
g_modelShadow.Init(g_model.GetModel(), g_lightPos); 

以下是ModelShadow::Init的定义

bool ModelShadow::Init(const t3DModel &model,const float *lightPos)
{
// 获取object的数目
objNum_         =   model.numOfObjects;
objInfoTable_.resize(objNum_);
for(int objIndex = 0 ; objIndex < objNum_ ; objIndex++ )
{
....
}
glClearStencil(0);
....
SetConnectivity(); // 设置三角形之间的链接关系
CalcPlane();         // 计算每个三角形的平面方程
....
}

3.初始化之后就可以渲染了

// 绘制模型，阴影
// 重设光源位置，如果光源位置不便可以忽略
g_modelShadow.ResetLightPos(g_lightPos);    
// 这里获取当前的model view matrix(MVM)
g_modelShadow.GetCurMatrix();                    
glPushMatrix();
// 放置物体
glTranslatef(g_modelPos[0], g_modelPos[1], g_modelPos[2]);       
// 这里又获取了一次model view matrix
g_model.Draw();                                       
g_modelShadow.Draw();
glPopMatrix();

通过两次获得的矩阵的差异就可以算出中间做了那些变换，比如(glTranslatef(g_modelPos[0], g_modelPos[1], g_modelPos[2]); )
现在看一下ModelShadow::Draw的实现

void ModelShadow::Draw() const
{
glClear(GL_STENCIL_BUFFER_BIT);

GLfloat objMatrix[16];
glGetFloatv(GL_MODELVIEW_MATRIX, objMatrix);

// 求逆矩阵，这四条语句就是在求物体的局部坐标系里灯的坐标
InverseMatrix16(objMatrix);  
MultiplyMatrix16(objMatrix, curMatrix_);
memcpy(lightPos_, orignLightPos_, 4 * sizeof(float));
Mtx16MultVect4(objMatrix, lightPos_);

//Cast the shadow
CastShadow();
}

再看ModelShadow::castShadow

void ModelShadow::CastShadow() const
{
SetVisibility();  // 设置每个三角形的可见性
....
// 第一趟渲染，通过模板测试的话模版值增一
glFrontFace(GL_CCW);
glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
DoShadowPass();

// 第二趟渲染，通过模板测试的话模版值减一
glFrontFace(GL_CW);
glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
DoShadowPass();
....
glStencilFunc(GL_NOTEQUAL, 0, 1);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);

//在全屏幕混合一张图
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
glColor4f(0, 0, 0, 0.3f);
....
}

有一些问题，我在（2）里说错了的

glLoadIdentity();
glBegin(GL_TRIANGLE_STRIP);
glVertex3f(-0.1f,  0.1f, -0.10f);
glVertex3f(-0.1f, -0.1f, -0.10f);
glVertex3f( 0.1f,  0.1f, -0.10f);
glVertex3f( 0.1f, -0.1f, -0.10f);
glEnd();

这个覆盖全屏真是投机取巧
gluPerspective(45.0, (GLfloat)width/(GLfloat)height, 0.1, 100.0);
如果那个角度比45.0f大就无法覆盖了
正确的做法是改用正投影。

One of blizzard's christmas flash

蛮温暖的呵，苦工老弟都开始玩了。

Words on:图形程序开发人员指南(一)

书的英文名是《Michael Abrash's classic Graphics Programming Black Book》。Michael Abrash是图形学的先驱者之一，《DOOM启示录》也有描述。云风的书(《游戏之旅－我的编程感悟》)上也多次提到了这本书。我摘录了一些，但是是非技术的。以后多贴点技术的。
在东校区图书馆无意间发现的，大家要到东校区借书的话来找我。:D

[Michael Abrash]        我想说的是我们现在日益进入一个紧密互联，高度逼真的空间，我希望那些人意识到3D编程的难度和潜能实际上比以前更大。关键在于不要沉溺于已经实现的技术，必须不断奋斗，力争"用不同的方式，用更少的代码，编写出更好的程序。"不断学习，改变并尝试新的方法，直至生命的终结，这样就能为将来留下自己的烙印。
        当说到这种乐趣是我生活的目的时，我认为我并没有言过其实（当然也许有一点点），我很高兴这么多读者都有这种热情。
        要敢于尝试不可能的事情，知道什么是不可以的也是有用的知识－一些意想不到的成功可能会让你顿悟：多数不可能的事情其实是可能的。
        这十年是微机程序员的十年，我庆幸自己不仅能成为其中的一员，而且能够在历史的发展中留下自己的痕迹。但愿未来的十年依然充满兴奋和喜悦。

[John carmack]编程不是一个零和的游戏，教给你的同行一些东西并不会丢失它们，我与人分享我能够做到的一切时感到很高兴，因为我深深的热爱编程。一辆法拉利小轿车不过时一种物质享受，但做人最重要的是真诚。

尝试了一下gDEBugger

以前就装过这个东西，不过没怎么用。NVPerfKit的一个部分。
装NVPerfKit要先卸载本机的NVidia显卡驱动（驱动,:D），NVPerfKit会替换那个驱动，这样它就可以在底层截取渲染操作的信息。控制面板里的NVidia developer control panel也可以用了。
今天碰到了问题，前几天把ModelShadow（模型的阴影渲染）重写了一下，在Nehe的框架下写的。现在要转到xophiix的框架下。两边的操作基本上完全一样，但是那个阴影死活不出来。sigh.

于是就试了一下gDEBugger.gDEBugger分了八栏：OpenGL function calls history,OpenGL State Variables,Call stack,Properities,performance graph,counter, performance Dashboard,Function Calls Statistics.今天主要用的四OpenGL function calls history和OpenGL State Variables.监视了一下GL_CULL_FACE,GL_CULL_FACE_MODE,GL_STENCIL_BITS这个个关系比较大的状态变量，没对比出什么区别来。

然后把OpenGL function call录制了一遍，这个功能真的很好。有一个红色的小球样子的按钮就是了。录完点右边的一个按钮就可以在浏览器里看到，我对比了一下阴影渲染部分的主要调用，真的是没有太大不同。

还有就是可以设置断点，在出现OpenGL错误或者接到NVidia GLexpert的报告时中断，还可以自行设置在执行某些OpenGL函数时中断。如果支持条件中断就更好了。发现了一个以前的小bug，一个错误的OpenGL调用。

还可以在性能分析(profile)模式下工作，这个我并不了解，用NVPerfHUD也许更好吧,不过NVPerfHUD是为D3D程序工作的.....。最后，可惜gDEBugger不是免费的，只能用30天。

下载NVPerfKit

PS:今天又发现一些新的功能，比如同步显示代码（类似VTune)和Shader编辑器。profile也比我想象的更强。

卡马克（John Carmack) 的blog

卡马克(john carmack)最近写blog了，id开始涉足手机游戏
一个很有趣的事情是：这个网站是一群火箭爱好者的地盘
新发布的一款是<<Orcs & Elves>>，有多种版本，NOKIA的好像要求N70以上。还蛮高的。以前好像有另一款产品叫做DoomRPG
想想罗梅洛，离开id之后也是去做手机游戏了

时代已经不同了。游戏的商业价值已经被完全重视起来。id可以在技术上成为leader,在市场上恐怕很难了。即便手机游戏这样的特殊市场，gameloft等厂商也已经占先了。id本次的开发平台选用了BREW和java，各有两种平台的高端和低端产品。
[carmack]:In hindsight, we made a strategic mistake at the start of O&E development. We were fresh off the high end BREW version of DoomRPG, and we all liked developing on BREW a lot better than Java. ...The high end version is really wonderful, with all the graphics, sound, and gameplay we aimed for, but when we went to do the low end versions, we found that even after cutting the media as we planned, we were still a long way over the 280k java application limit.
开来carmack仍然那么追求效果，不过现在手持设备的能力毕竟与桌面电脑有差距。
[carmack]:The download size limits are probably the most significant restriction for gaming on the high end phones. I don't really understand why the carriers encourage streaming video traffic, but balk at a couple megs of game media.

Shadow Volume详解(2)

然后重设模板测试比较函数：glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
绘制阴影体的所有背向视点的面
也就是当片于通过模板测试时，相应的模板缓存区域的值减一。接着红色区域＋棕色区域的那个四边形被渲染。但是这个四边形位于红色的三角形的背后的部分无法通过深度测试，那个区域片元的位置比三角形离视点更远。













左图中棕色区域的模板缓存相应位置的值减1。经过这两次渲染，模板缓存中不为0的地方就是右边的淡蓝色区域减左边的棕色区域。
那个区域就是棕色区域下面的三角形区域，也就是阴影区。
实际上标准的做法是把场景渲染两遍的，这个下面我会翻译。现在使用的是NeHe的做法，直接给整个屏幕蒙上一个蒙板，非阴影区颜色不变，阴影区颜色加深。

glStencilFunc(GL_NOTEQUAL, 0, 0xffffffff);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);

//draw a shadowing rectangle covering the entire screen
glColor4f(0.0f, 0.0f, 0.0f, 0.4f);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

glPushMatrix();
//将当前矩阵load indentity后，绘制任意大小的矩形都将覆盖整个屏幕。
//xophiix告诉我，我才想起来的
glLoadIdentity();
glBegin(GL_TRIANGLE_STRIP);
 glVertex3f(-0.1f,  0.1f, -0.10f);
 glVertex3f(-0.1f, -0.1f, -0.10f);
 glVertex3f( 0.1f,  0.1f, -0.10f);
 glVertex3f( 0.1f, -0.1f, -0.10f);
glEnd();
glPopMatrix();

然后就可以恢复OpenGL状态机设置，绘制物体本身。

Shadow Volume详解(1)

利用每天夜里的一部分时间写一下，这也是热爱吧。主要是翻译reference(1)里的，也讲一下Nehe的实现。现在使用的还是z-pass方法，以后会把z-fail,Nvidia 的改进z-pass乃至soft shadow加进来。
感谢两个人的话：
DancingWind:如果我能让读者在读我的书的时候节省一分钟，那么这个班上有60个同学，我就节约了一个小时。好的教程往往可以事办功倍。
Emilmatthew:让更多人受益。
虽然我能力所限做不出好的教程，但是会尽力的。
Reference:
(1).Volume Shadows Tutorial by John Tsiombikas
(2).Nehe OpenGL tutorial:lesson 27 by Nehe
Steps:
[1]原理

[原理]首先，讲一下阴影体原理
我会尽我所能的讲得清楚一些，但是我仍然希望读者队模板缓存(stencil buffer),深度(depth)有基本得了解。我自己得学习过程也遇到很多困难，所得到得经验就是要先把原理弄明白，而不是急于看别人写好的code。













这个图是很理想的，足够简单又能说明原理。黄色的点代表光源，红色的平面代表一个三角形的物体，紫色，蓝色，棕色的平面就是构成阴影体的面（实际上这三个面应该在被离光源的方向上继续延长的，现在还是继续使用它吧)。灰色的代表阴影投射到的平面。

我们一边渲染一边讲：
[首先把要绘制阴影之外的物体绘制]，这也是一个原则阴影物体要最后被绘制，这样做的目的是为了获取深度信息。深度：depth也就是物体离视点的距离，深度信息通常用做遮挡判断。比如在三维空间里绘制了一前一后两个平面，就要通过深度信息来判断两个平面的前后位置，进而其中一个平面判断那些位置被遮挡了。绘制完成之后屏幕上每点的深度值都已经确定下来，然后使深度缓存不可写
比如:glDepthMask(GL_FALSE);(DX下有类似的做法）
但是允许深度测试:glEnable(GL_DEPTH_TEST);
测试函数为:glDepthFunc(GL_LEQUAL);
也就是说只有深度小于原象素的象素才会被接受。


[然后绘制阴影体]
先清空模板缓存:glClearStencil(0);
开启模板缓存测试：glEnable(GL_STENCIL_TEST);
设置测试比较函数为： glStencilFunc(GL_ALWAYS, 1, 0xffffffff);
然后设置片元通过或者未通过模板测试时如何队模板缓存中的数据进行更改： glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);也就是通过测试时增1。
然后绘制阴影体的所有朝向你的面，阴影体是这样形成的，以光源为一个顶点，物体边缘的一条边为边的三角形无限延伸所形成的四边形(理论上讲应该是一个无限的，但实际上长用一个足够长的来模拟)，本例中就是紫色和蓝色的面。容易发现，这两个面上的所有片元都可以通过测试
相对应位置的模板缓存的值都会加1。
但是相应位置的深度信息不变，因为深度缓存被设置为不可写。
结果如右图所示：淡蓝色的区域模板缓存值增1。

地形生成

本来地形这个东东可以用柏林噪声之类的生成不错的东西，还有四叉树，但是现在情况比较特殊。组长希望：远处有山。所以做生成有点麻烦（其实也不麻烦）。现在是用生成好的bmp高程图。有专门的软件做这个事情。 World Machine，国外做的东西，有点复杂，但是很强大，也很好用。现在还在学习中。bmp文件其实并不很合适，那个头部的定义就够BT了。而且生成的图是24bit信息的，其实8位就够了，不需要那么高的精度。居然还有48位的，太。。。了，也许是因为专业吧。我用的还是trail版，pro简直难以想象了。
昨天的纹理问题今天解决的差不多了，还有法线一会儿也能解决。那就无敌了。可惜cactus同学嫌VSS服务器文件太大，把整个data目录给。。喀。。了，所以文理图不敢改，改了只有我这里是最新的，又会回到手动源代码管理的时代了。唉，得想点办法。

NeHe的OpenGL教程（完全版）下载

NeHe的OpenGL教程（完全版）下载(chm)
但是不附带代码，代码可以去http://www.xophiix.com.cn下载，是打了包的，或者NeHe的网站
或者看电子书的时候看到那里，就下那一章的，书里有链接。NeHe的教程还是不错的，如果能从头到尾学下来，也有一定水平了。可惜最近不怎么更新了。

Shadow Volume

弄了一天的 Shadow Volume,还是有点收获的。基本的过程是了解了。
单个三角形的情况还很容易理解，多个的还没想明白。要努力啊
整整弄了一天，也没有War3。快开学了，时间不多了，该做点事了
xophiix回来了，自己感觉还是很受鼓励的。
06.09.05
今天是非常的不爽，在代码即将写完的时候，VS.NET 2003顺利崩溃。更为致命的是产生了罕见的蓝屏错误，然后启动失败。然后启动了若干次启动到安全模式。check hard disk，这个硬盘一直有问题。哎，本来准备今天见到效果 的。
06.09.05
今天重写了，所有的物体都出来了，偏偏阴影不见了。3维程序调试起来也很麻烦，跟普通的不一样，他是看效果的。
06.09.06
终于改出一个能用的了。从NeHe的27课弄出来的。因为昨天写的那个是VS.NET 2003写的，用xophiix的框架，现在VS彻底崩了，无法编译了。NeHe的一个做法让我很不解，他从文件里读顶点信息，也就是说你要画一个物体，必须提前计算出所有顶点。实际上多个面可能有一个公共的顶点的。在OGL里就可以画每个面的时候都glVertex..... ，判断两个面是否相邻时判断顶点的坐标是否相等。我重载了struct SVertex的 == 操作符。尽管重载并不是好事。

bool operator== (SVertex p1, SVertex p2)
{
if(p1.x == p2.x && p1.y == p2.y && p1.z == p2.z )
    return true;
else
    return false;
}

还有矩阵那一部分也要改一下，其实没必要重新生成一个矩阵，用逆矩阵就可以了。实际上他那个矩阵变换我还是有点不明白的。
06.09.06
现在明白NeHe为什么那样读取数据了，很多模型文件（比如3ds)都是在前面存模型的顶点，面的信息里只有顶点的索引。听xophiix说的。
看来线性代数的东西还是比较重要，连个矩阵求逆都不会了。还到处找资料^_^
06.09.08
NeHe求逆矩阵的方法真是奇怪，按相反方向进行变换，然后glGetFloatv(GL_MODELVIEW_MATRIX, curMatrix);
其实有专门的矩阵函数的............，比如高斯-约旦法。不过我只有代码，具体的数学知识并不清楚。要开始研究3DS文件了。程序员们总喜欢做抽象层。。。
从NeHe的网站上看到一段话，会让很多人汗颜了
One final note, if you see code that you feel is similar to someone else's code, please contact me. I assure you, any code I borrow from or learn from either comes from the MSDN or from sites created to help teach people in a similar way that my site teaches GL. I never intentionally take code, and never would without giving the proper person credit. There may be instances where I get code from a free site not knowing that site took it from someone else, so if that happens, please contact me. I will either rewrite the code, or remove it from my program. Most the code should be original however, I only borrow when I absolutely have no idea how to accomplish something, and even then I make sure I understand the code before I decide to include it in my program. If you spot mistakes in any of the lessons, no matter how tiny the mistake may be, please let me know.
现在看来把阴影加到3DS模型里还是比较容易的，3DS文件的定义和需要的数据差不多。明天得补一下功课了。可惜矩阵变换那一部分还是有点不明白，必须用我认为错误的方法才能得到正确的结果。。。
Z-PASS + 3DS基本上弄得差不多了，发张图先

要z-fail了，会是一个难点啊。还有今天因为要用Import3DS这个函数而从CLoad3DS继承了CBW3DSShadow被cactus和xophiix。。。。
的确是经验啊，继承不该被滥用。而且，有些成员为了这次继承变成了protected,又是滥用.......
06.09.14
今天例会又讲了一下Shadow Volume，才发现有些地方还是没真正弄明白，只是弄了一个能用的东西而已。像glLoadIdentity之后glRect产生的图形将覆盖整个屏幕。老是以为相机已经设定好了。还要改进啊，z-fail并不急，先用NV的改进方法吧。场景还要改善，新的地形和光束....
06.09.26
终于把ShadowVolume真正弄明白了，耶，还有soft shadow呢。4点多了。

简单的三维树生成及渲染

这个暑假写的学的东西，最近整理起来，刚刚学OpenGL,很多方面做得都不好。
压缩包里有介绍
DEMO下载
源文件下载

pre： 先反省一下，以前写的确实过于简略，代码又没有设么注释。感谢EmilMatthew的话，让更多人受益 源代码正在改写，以前变量命名很随意，反正很不清晰，更提不上elegant了。另一方面也在进行优化
核心算法描述：（实际上并不算是什么算法） 树主要分两部分：树枝和树干。树干使用二次曲面圆柱（gluCylinder，注意这个圆柱是可以上下半径不等的）近似，树叶就贴一片纹理。 树的绘制是递归进行的，也就是说：在一段树桩上接上三段树枝所形成的东西仍然叫做树（DEMO里每一段树枝上都有三段小树枝 ，递归的深度是四，可以自己调整）。用代码来写的话:

void DrawTree(int depth)
{
  DrawStem();            //绘制树桩     
  if (2 < m_ndepthtop ="=">
     //未绘制到顶层的话继续递归绘制
  MoveToStemTop();       //移动到树桩顶部（注意圆柱体是没有上下表面的，所以要用树枝挡住）
  DrawTree(depth + 1);   //绘制第一个树枝

  MoveToProperPos();     //移动到适当位置（glPushMatrix();glRotatef();glTranlatef();...）
  DrawTree(depth + 1);   //绘制第二个树枝
  MoveToProperPos();     //移动到适当位置
  DrawTree(depth + 1);   //绘制第三个树枝
}

绘制函数可以这样被调用：DrawTree(1); m_nDepth指的是树的递归层数，加深一层速度会慢三倍，但是可以得到更繁茂的树。 DEMO里只有四层，只是用了很大的叶子去掩盖，并且一片纹理图上就有五片叶子。不过总比一棵树上贴五片树枝纹理图，然后用billboard 好的多，很多著名游戏都是这么干的。
post： 还有一点别的事情，树的顶端树枝很细，所以我并没有使用二次曲面进行模拟，而是使用了长方体。这样会稍微快一点。 比较粗的树干上通常是没有叶子的，所以绘制的过程中有相关的判断，地层的树枝上不会有叶子。 我用AMD CodeAnalyst 对程序进行了分析，可惜并没有找到真正的热点。对于代码优化来讲，算法上的优化通常会更优。 在我的机器（AMD Sempron 2800+ 1.6G,512MB,6600LE 128MB）上，把绘制树的过程做成显示列表后，调用一次列表的时间大约为0.85ms ，使用近似之后可以节约大约0.04ms。目前对我来说主要问题还是效率，我希望效率可以提升一倍，反正要比导入模型更快。 最近主要针对的是消除递归，树是递归定义的，希望消除递归能提高效率。主要方法还是用栈，二叉树和三叉树消除递归好像差不多。 还有隐藏面消除，显卡也会完成隐藏面消除，我希望要的结果是不需要绘制的面（或者点）的信息就不要传给显卡，估计自己做可能倒不如传给显卡。 还有更快的圆柱体绘制方法。 还有使用更小更精巧的纹理，看WAR3的纹理图给了我一点启发，一张256X256的图片巧妙的交错存储了两种植物的纹理。30多个面，50多个顶点 做出来的植物也是非常逼真，不过WAR3并不是以真实感为卖点的游戏，其实树做的就很搓，实时性可能更重要一些。 如果有人对这个感兴趣的话可以在我的blog上留言。
注：递归消除部分的代码已经写完，但是效率并没有得到提高