Tags: Programming

STL中的红黑树

平时用STL通常只是顺手把vector, map之类常用的类拿来用用就完了,也没有想到去仔细研究里面都有些什么东西。这两天有一个算法程序需要将一堆对象排序,并且会非常频繁的插入删除,对效率的要求极高。原本想用priority queue,但是发现它是对一个数组进行堆排序的方式来操作,效率并不高。在STL的文档里面找了找发现居然没有红黑树,google了一下才知道set, map底层都是用红黑树实现的,只是这个红黑树没有暴露出来给人用。

也不知道是出于什么考虑,性能优秀的红黑树虽然标准库里面有,但是却遮遮掩掩不直接提供给大家用。值得注意的是,因为红黑树是内部使用的类,各个STL实现中的红黑树还不一样。

在VC的实现中红黑树是在xtree文件中的_Tree类,用法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include 
#include 
#include 
 
using namespace std;
 
typedef _Tree< _Tset_traits, allocator, false > > rb_tree;
 
int main()
{
    rb_tree* tree = new rb_tree( less(), allocator() );
    for(int i=35; iinsert(i);
 
    printf("output: %d ", *tree->begin() );
}

gcc中的实现则是在bits/stl_tree.h文件中,而且类的名字和用法都不一样:

1
2
3
4
5
6
7
8
9
10
11
12
#include 
 
typedef _Rb_tree,
                 less > rb_tree;
typedef rb_tree::iterator rb_tree_iter;
 
int main()
{
    rb_tree queue;
    queue._M_insert_unique( int );
    printf("size: %d", queue.size() );
}

尝试给开源项目打补丁

最近开始尝试给开源项目打补丁。首先是跑到Gnome Love上面去逛了一圈。GnomeLove是Gnome官方为了降低开源开发者加入的门槛而搞的一个页面,上面有一些帮助入门的文档链接,从GTK开发到git的使用都有。然后再到Bugzilla上面用GnomeLove作为关键词,能够搜索出一堆比较容易改的bug。
我抓了Empathy的一个bug开始改。Empathy有一个问题就是,它的聊天窗口不会记忆联系人边栏的位置,每次打开一个窗口都需要自己重新拖动它。修改这个bug也很简单,在聊天窗口创建的时候加入一个事件响应函数。然后再在窗口边栏位置变化的时候把这个位置保存在GConf里面,下次窗口打开的时候再把这个数读出来就好了。上次Jesse给Gnome给数独游戏修改bug的时候对方一个多月以后才有反应,不知道这个bug多久以后会有人理我?

用GAE开发wiki

  我越来越发现我out了,GAE都出来这么久了我才发现在google code上面有一个google官方的项目,里面塞满了各种使用GAE来做应用的例子。于是国庆这段时间把它整个下了下来,将其中的cccwiki这个例子修改了一下成了一个可用性更强一点(但是功能仍然很弱,国庆闲暇时候做的东西不要有太高期待哈)的wiki。点这里可以看到例子,如果对源代码感兴趣的话可以在这里找到(使用Mercurial版本管理)。

wiki-screenshot

wiki-screenshot

  最初的cccwiki只是很简单的把每一个页面的html源代码保存并展示出来。我做了以下修改:

  • 增加了revision功能,把修改的历史记录都全部保存了下来
  • 使用wiki标记语法,而不是直接标记html
  • 用MarkItUp替代原先的TinyMCE作为编辑器。因为前者支持wiki语法,而且貌似也更灵活
  • 加入了CreoleParser来解析wiki标记语法。不过Creole语法和MarkItUp所支持的wiki语法不大一样,还需要对MarkItUp进行修改
  • 对界面进行了一点点修改,看起来似乎是要好一些了?

  整个修改的过程非常的顺利。我是用的Eclipse+Aptana PyDev来开发的,虽然整个过程中没有用一个完整的rails或者django之类的框架,但是效率并不低,很多功能很快就实现了。

  一方面是因为GAE特殊的数据存储机制。GAE中不能使用通常意义上的数据库,而是用的google自己开发的使用的分布式数据存储(官方管这个叫做 Google App Engine datastore)。感觉上应该很适合wiki这种数据。经过GAE包装以后感觉用起来非常像Ruby on Rails中存储数据的方式--你只需要声明一个类,然后把数据直接赋值给它的某些成员变量,然后调用一个叫做put的成员函数就保存进去了。对于查询也可以用类似Rails的类成员函数的方法来进行,同样的如果想要进行复杂的查询的话也可以使用GQL(一个google自己搞的类似于SQL的语言)来弄。总而言之,你不需要也不能和数据库打交道,也就免去了很多数据存储方面的代码量。这方面整体感觉和Rails非常像。
另一方面,虽然GAE并没有提供创建项目的一些脚本,但是这对于开发效率的影响其实也并不大。众所周知,那些脚本无非是给你创建一些文件夹和没有多少行代码的文件,在Eclipse中干这些事情也不会多花几分钟。

  django的粉丝肯定会对GAE非常不爽,因为数据库不能用直接导致django的MVC中的Model一层完全就不能用了。不过另一方面,自己重新写一个Model层也不会很费事,google已经把datastore弄得很好用了。真正让人觉得不舒服的是GAE中的诸多限制。你只能通过GAE中的接口通过http方式访问外部的资源,发邮件也是如此。如果你的程序太消耗CPU,或是带宽,或是其他什么硬件资源,那么它会被停掉。不过相对于其他的免费空间GAE已经算是很不错了。

  GAE上线到现在时间已经不短了,但是仍然没有多少出名的应用部署在GAE上面。这个结果似乎也是显而易见的:虽然GAE的软件部分已经开源了,但是其中的关键技术--分布式的计算和存储--却是其他人所很难复制的。为了开发GAE上面的应用我必须遵从它的软件接口,那也就意味着这个东西如果不想在google上面跑的时候就必须面临大量改动。而且谁也不能保证什么时候google会不会像关闭其他半途而废的项目一样关掉GAE。对GAE这个东西玩玩就好了,要是真想做东西的话还是用django吧。

OgreOpcode碰撞检测使用概述


OgreOpcode几乎是不使用物理引擎时Ogre下的唯一选择,但是这个天杀的库文档实在是太少了,约等于没有。下面把这两天使用它的经验整理一下。

下载&编译

OgreOpcode没有任何Release,获取它的唯一办法是从SVN中下载源代码进行编译,SVN地址如下:
https://ogreconglo.svn.sourceforge.net/svnroot/ogreconglo/ogreopcode/trunk
在script文件夹找到自己用的编译器的项目文件,直接编译就可以了。需要注意的是,SVN中的exmples是无法正确编译的–这些例子运行所需要的一些文件没有在SVN里面!另外就是doc目录中的Doxygen配置文件中居然用的是绝对路径,不经修改是无法运行的。此外我在使用VS2005的时候发现,它的项目文件中少包含了一个叫OgreCapsuleMeshCollisionShape.cpp的文件,导致编译无法通过。需要自己把它加到OgreOpcode项目中才可以编译成功。另外在项目的“生成后事件”中会执行一个拷贝的命令,但是在svn的文件夹结构中目标文件夹是不存在的!这也会导致编译失败。
实在是被这个项目的维护人员打败了…这么多纰漏…
我知道是个人都会觉得从svn里面编译很麻烦,所以我吧它编译好了上传上来了,点这里下载ogreopcodebin。里面包括编译好的debug和release版的dll。

使用

要使用OgreOpcode,基本上可以分为这么几步:

  1. 创建一个Manager
  2. 创建一个Context
  3. 加入参加碰撞的物体
  4. 碰撞检测

初始化

    // 创建Manager。这个Manager使用Singleton实现
    CollisionManager* mCollisionMgr = new CollisionManager(sceneMgr);
    // 创建context 不同的context中可以添加不同的物体,发生不同的碰撞关系
    mCollisionContext = mCollisionMgr->createContext( "test" );

    // 创建碰撞类,并且设置不同类型之间碰撞的检测方式
    mCollisionMgr->addCollClass("charactor");
    mCollisionMgr->addCollClass("scene");
    // COLLTYPE_QUICK 表示两个charactor之间的碰撞使用简单的球体进行检测
    mCollisionMgr->addCollType("charactor", "charactor", COLLTYPE_QUICK);
    // COLLTYPE_IGNORE 表示忽略场景物体之间的碰撞
    mCollisionMgr->addCollType("scene", "scene", COLLTYPE_IGNORE);
    // COLLTYPE_EXACT 表示计算charactor和scene碰撞时的所有交点
    mCollisionMgr->addCollType("charactor", "scene", COLLTYPE_EXACT);

加入物体

OgreOpcode中的物体主要有以下几种:Box, Capsule, Sphere, Terrain, Mesh, Entity, Ptr,调用CollisionManager::createXXXXCollisionShape函数来创建。从函这些物体的名称大体上可以才到它的用法。其中Ptr是从一个三角形数组中得到一个碰撞物体的形状。

    // 根据一个entity的网格模型信息来创建碰撞形状
    EntityCollisionShape *shape = CollisionManager::getSingletonPtr()->
        createEntityCollisionShape(ent->getName());
    // 制定该shape所关联的entity
    shape->load(ent);
    // 创建一个碰撞物体
    CollisionObject* pCollisionObject = mCollisionContext->createObject( ent->getName() );
    // 设置该物体的类型,这里应该是第一步中设置的"charactor","scene"之一
    pCollisionObject->setCollClass( type.c_str() );
    // 设置object的形状
    pCollisionObject->setShape( shape );
    pCollisionObject->setForcedUpdate(forceupdate);
    // 把这个object加到我们创建的CollisionContext中去
    mCollisionContext->addObject( pCollisionObject );

其他设置

在每一帧都需要调用CollisionContext::Collide(time)来更新状态,否则是无法检测到碰撞的。

另外在所有物体都已经添加到CollisionContext中了以后需要调用一次CollisionContext::reset()。

碰撞检测

OgreOpcode中的碰撞检测包括射线(rayCheck)、球体(sphereCheck)、移动球体(sweptSphereCheck)三种方式。rayCheck就是传入一个Ray对象,检查射线上有没有和其他物体相交。sphereCheck则是创建一个虚拟的球体,检查这个球体有没有碰撞。sweptSphereCheck则是创建一个虚拟球体,并且让它沿着某个方向移动,检查在这个过程中是否有交点。

下面给出一个rayCheck的例子:

    Ogre::Ray ray(Vector(0,30,0), Vector(0,-1,0));
    Ogre::Real dist = 100;
    std::vector vectorList;
    CollisionPair** collisionPair = NULL;
    if( mCollisionContext->rayCheck(ray, dist ,
            COLLTYPE_EXACT, COLLTYPE_ALWAYS_EXACT, collisionPair ) > 0)
    {
        int count= mCollisionContext->getNumCollisions();
        for( int i = 0; i < count; i ++ )
        {
            vectorList.push_back( collisionPair [i]->contact );
        }
    }

其他

其实OgreOpcode的接口并不是那么那么的复杂,但是没有文档使得使用它变成了一个比较头疼的事情。官方网站也仅仅是一个并不活跃的论坛,让人很是怀疑这个库是不是值得去深入学习。其它的碰撞检测库如GIMPACT虽然文档上好很多,但是却没有Ogre下的wrapper。说不是什么时候我心血来潮了就会写一个这样的wrapper?

被OgreOpcode折磨中

用了很长时间的开源软件,大多是时候都用的是开发时间很长很成熟的代码。这次因为要在Ogre里面作碰撞检测,但是又不想用物理引擎这么重量级的东西,所以选择了OgreOpcode。但是没有想到的是,整个项目没有任何Release,没有文档,论坛里面门可罗雀,运行Doxygen生成的还是没有多少有价值的东西。想看看samples里面是怎么做的,但是缺少场景、模型等文件,不能运行…
google搜索OgreOpcode,唯一有价值的东西还是Azure在blog里面写的一个很简略的介绍,其他的基本上都是转载的这个。

这真的是Ogre引擎下用的最广泛的碰撞检测库么…?

GLSL编程必备程序库

因为做毕设的原因,最近一段时间都在写一个全局光照的shader。期间用了不少开源库,把自己用了以后的经验大致罗列如下。

图像载入

图像载入的库非常多,而且很多都已经很成熟了。选择很多,基本上是萝卜青菜各有所爱,用什么都没关系

DevIL

网上不少shader的示例程序都用了这个DevIL库来读取图像。这个库的程序接口和OpenGL风格类似,调用起来很方便,支持的格式也非常多,只是可以保存的图片格式稍微少一些。不过平常自己的程序也需要保存图片为奇奇怪怪的格式。
http://openil.sourceforge.net/

Simple OpenGL Image Library

这个简称soil的图像库使用起来非常简单,只需要一个函数就可以把图像读取到OpenGL中去。我的Shader Demo用的就是这个库,目前还没有发现什么问题。
http://www.lonesock.net/soil.html

模型载入

网上的模型格式可谓各式各样,每个游戏基本上都会有一个自己专用的模型格式。个人感觉有一个能够读取各种格式模型的库还是挺有必要的。

gl3ds

这个项目是glee的一部分。从名字就可以看得出来,这是专门用来读取3ds文件格式的轻量级库。不过它也仅仅能用来读取3ds模型。
http://sourceforge.net/projects/glee/

Open Asset Import Library

如果手头模型格式五花八门,那么可以用这个大家伙来解决你的问题。它能导入十几种模型格式,同时提供C/C++接口。缺点是对于一个简单的Demo程序而言可能有点过于巨大–我的程序在链接了它的静态库以后体积达到了6M…
另外一点就是,这个库独立于OpenGL/DirectX,并不提供针对OpenGL的接口。也就是说你还是得自己写一个循环来绘制模型,不过好在这并不麻烦。
http://assimp.sourceforge.net/

基础框架

大多数人都是比较懒的,懒人都是不会为了一个demo而去从win32 api开始写代码的。

GLUT

没什么可说的,读过红宝书的人肯定对于这个库都非常熟悉。优点是简单,缺点是不方便于面对对象编程,库也非常老了。
http://www.opengl.org/resources/libraries/glut/

FreeGLUT

GLUT的开源实现版本。如果你对于没有glut的源代码而耿耿于怀的话可以用它。不过也不要抱太大希望,这个库和glut几乎一模一样,同时有glut的优点和缺点
http://freeglut.sourceforge.net/

Humus’s Framework

Humus的个人网站上有一卡车一卡车的Shader Demo程序,而他的程序都是用自己的Framework 3写的。这个库很强大的样子,跨平台支持Windows, Linux, 能够用于OpenGL和DirectX,可谓大小通吃。不过缺点是虽然你能下载到它的所有源代码,但是却完全没有文档,连注释都没有。作者最近正在写支持OpenGL 3.0的Framework 4,让咱们祈祷他能写点注释生成个Doxygen文档吧…
http://www.humus.name/

Ogre

这算是这几个里面最重量级的框架了吧。完整的渲染引擎,可以用同样的代码调用DirectX和OpenGL渲染。Ogre的脚本系统很是强大,只需要用脚本就可以搞定Shader渲染中的大部分工作–包括创建Render Target, 载入纹理,实现各个Pass间的交接等等。但是最大的问题是,学习和使用Ogre本身就是一个很大的工作量。如果你已经有使用Ogre的经验的话不妨考虑一下。
http://www.ogre3d.org/

数学库

如果你用了很多第三方库的话,数学库可能会编程很麻烦的一个东西。你会发现你的摄像机、GLSL抽象类、模型载入库分别用了一套不同的库(这正是我现在正在郁闷的一个问题)。没办法,既然不想自己写所有的代码那就只能忍忍了。

GLM

GLM也就是GL Mathematics的缩写。这个库提供的类接口和GLSL中内置的数学接口非常相似,但是缺少一些常用的函数,不是特别方便
http://glm.sourceforge.net/

OgreMax使用经验

对于Ogre的3ds max导出插件目前只用过oFusion和OgreMax,其中oFusion免费版因为有功能限制几乎没法儿用来做真正的开发。所以大部分时间就是用oFusion在3ds max中的即时预览功能,然后用OgreMax来做真正的导出。

自定义数据

使用OgreMax很重要的一点就是导出自定义数据。要做到这一点首先需要自己写一个xml文档来说明自定义数据的类型,在OgreMax文档的"Custom User Data Types"页面中有很详细的例子,比如下面是我正在做的项目中截出来的一段:

<userDataTypes>
<class name="charactor" displayName="角色 " usage="private">
<data name="name" displayName="名称 " type="string"/>
<data name="wayname" displayName="路径名 " type="string"/>
<data name="meshname" displayName="模型名称 " type="string"/>
<data name="common_skeleton" displayName="公用骨骼 " type="bool" defaultValue="true"/>
</class>
</userDataTypes>

在OgreMax->Object Settings->User Data中载入以后就可以在type中选择"角色"类型了,并且会按照xml中定义的数据显示。

导出以后在.scene文件中会有类似如下的xml块:

<![CDATA[
<player>
<name>DefaultPlayer</name>
<wayname></wayname>
<common_skeleton>true</common_skeleton>
<meshname>robot</meshname>
</player>
]]>

上面这一段CDATA可能包含在一个Entity或者Node节点中,具体取决与你在OgreMax中的设置。

物体属性设置

前面也提到了,在OgreMax->Object Settings中可以对导出物体的属性进行设置。这里介绍一下其中比较重要的一些选项。

General

  • Type 这一项决定了导出物体在.scene文件中的类型。最常用的是Entity/Mesh,这个类型在导出以后会生成一个node以及挂载在该node上面的entity,同时会把3ds
    max中的该物体导出为一个.mesh文件。然后就比较常用的就是Empty,这种类型会导出为一个没有挂任何东西的node。比如说我用一个box来代表NPC出现的位置,那么这个box就可以设置为Empty类型。
  • Rendering 在这里设置物体的可见性、渲染顺序、shader参数等等

Node Animation

在这里设置物体的Node动画,即位置、旋转、缩放上的动画。物体模型本身变化的动画在Mesh Animation中设置。具体的用法还没有仔细研究。

User Data

自己游戏所需要的自定义数据就在这里设置了。点Configure…按钮添加上面所说的userdatatypes.xml文件以后,User Data Class中就会出现自定义的数据类型。这样就可以直接把3ds
max作为一个关卡编辑器来使用了。虽说还是没有专门的编辑器那么方便,不过大多数情况下还是够用了。

Mesh

Mesh Name和Skeleton Name可以制定输出的模型和骨骼的文件名,如果不指定的话则会以3ds max中物体的名字命名。

Mesh Animation

这里用来设置顶点动画或骨骼动画。可以把整个场景中物体的任意某一段动画制定某个名字以供程序调用。点击Add..会弹出Animation Settings窗口。通常其中的Track类型已经设置好了,骨骼动画是Physicue,
定点动画是Morph。只需要制定动作的起始帧号就可以了。要注意的是一个场景中某个物体的骨骼动画只能导出为一个skeleton文件,如果你需要把不同的动作导出为不同的动画的话,需要把骨骼动画保存为不同的max文件然后飞别导出。

自定义文件的读取

OgreMax提供了从3ds max中导出为.scene文件的机制,然是我们还是缺一个读取它的程序。虽然OgreMax中自带了一个Viewer程序,但是要处理自定义数据显然还是得自己动手写一个。这里可以参考Ogre
Wiki中的一个.scene文件读取程序的例子,在它的基础上进行修改:

http://www.ogre3d.org/wiki/index.php/New_DotScene_Loader

但是这个程序在很多地方都只是写了一个函数名而没有实现,并且对场景文件的处理和OgreMax导出的格式还是有所区别,需要自己进行大量修改。这里附上我自己的场景读取程序:SceneLoader

Ogre在运行时绑定骨骼

通常一个骨骼动画用的模型用插件从建模软件里面导出的时候都会绑定所用的骨骼,但是有的时候需要在运行时动态的绑定骨骼。比如说我有很多个不同的角色模型,但是他们都共用走路、跳跃的骨骼动画,那么就可以在把这些模型载入以后再制定他们使用的骨骼。

Ogre的官方文档几乎没有提及具体应该怎么做,在Ogre的wiki和论坛中搜索了半天,发现有好些人都有这样的问题,但是都没有一个明确的解决方法。最后反而是在一个中文博客的留言里面发现了实现的方法:
* 假设我有一个角色char01.mesh,以及它所用的几个骨骼动画,比如说sit.skeleton, attack.skeleton,并且char01.mesh默认绑定了一个idle.skeleton
* 和通常一样载入char01.mesh,得到一个Entity*指针ent
* 进行如下操作

SkeletonInstance* oldSkel = ent->getSkeleton();
oldSkel->addLinkedSkeletonAnimationSource("sit.skeleton");
ent->refreshAvailableAnimationState()

这样就搞定了

VS2005下多人共享调试配置

很长时间以来用VS2005都是单人工作的状态,这段时间开始在使用SVN在不同机器上用VS2005编译项目,然后发现了一个很尴尬的问题–在项目属性中的调试设置到了另外一台机器上就全部失效了。

研究了一下项目文件,对于一个名叫app的项目会生成app.vsproj和app.vsproj.machine.username.user的两个文件,其中machine和username分别是当前计算机的名字和用户名。比如说app.vsproj.home.raymond.user。所有调试相关的设置都是在这个.user文件里面的。这样就造成一个问题:在不同的机器上面会读取不同的.user文件,同样的项目拷贝到另外一台机器上就不能正常调试了!

在网上搜索了半天,发现也有很多人遇到这个问题,但是就是没有搜索到解决方法。干脆打开下载的开源库文件的VS2005项目文件,发现其中有一个类似于app.vsproj.user的文件(没有中间的机器名和用户名)。再试验了一下发现在目录中只存在这样一个不包含机器名用户名的.user文件的时候,VS2005会把该文件中的内容拷贝一份为加上用户名的.user文件(说的好绕,不知道说清楚了没有)。而存在用户特定的.user文件时会忽略其他.user文件。

因此在分发自己的项目的时候只需要把自己机器上的.user文件名中的机器名用户名去掉就可以了。

缺胳膊少腿的Ogre

Ogre算是目前最成功的一个开源引擎,引擎功能不差,也有不少项目都是使用它在作为渲染引擎。不过这段时间用Ogre做游戏还是发现了它的不少弱点。
最麻烦的一点就是Ogre只是提供一个渲染的程序库,而开发用的工具基本上没有什么像样的东西。用了几个从建模软件里面导出模型用的插件,结果功能强大一些如oFusion的居然卖价比Photoshop还贵,其它的插件倒是能用,但是却都或多或少有这样那样的问题。专门的关卡编辑器之类的东西则更是没有了。Ogre的官方wiki上面有一些类似与Ogre IDE之类的项目,但是都已经很长时间没有更新了,有的连官方网站都已经失效了。

不过Ogre在主页上就已经说得很清楚,它是一个图形渲染引擎,不是游戏引擎。不知道这是作者为自己开脱还是他打算专注于提升引擎。另外一个选择就是使用基于Ogre开发的游戏引擎。不过现在看来这样的项目规模都比较小,网站也很简陋。反正我是不敢把自己的项目架在这样的质量不清不楚的东西上面。

最近花了很多时间实现自定义的关卡格式。主要就是在OgreMax导出的.scene文件夹中加入自己的数据,然后用自己的XML解析程序把数据从里面读出来。现在可以在3ds max里面创建关卡时指定游戏用的路点和角色了。不过作为一个典型的想把一切都纳入自己掌控之中的C++使用者,我总是很郁闷自己的程序得依赖OgreMax的导出插件,而又不想花时间去研究3ds max插件的写法(自己是不是有点太贪婪了?)。OgreMax的作者在论坛上面发了一篇帖子说支持Ogre 1.6的插件正在开发中,不知道什么时候会出来。

另外一个工作就是在游戏里面集成了LuaPlus,比想象中的要容易。没写多少代码就完成了脚本和游戏函数之间互相调用的功能。其它的选择像LuaBind因为要使用庞大的Boost,而我不希望编译自己的程序得下载一个和我的程序差不多大的库,放弃使用了(放弃它的另外一个原因是因为LuaBind大量使用了模板编程,这会让本来就已经很慢了的项目编译变得更加让人无法忍受)。毕竟对于脚本我的要求就是能够很容易的实现Lua和C++的相互调用就行了,所以其它的也不是很重要。

然后考察了一下物理引擎。之前曾经参加的一个开源游戏项目中,PM曾经对几个物理引擎进行了一个性能的测试。具体数字机不清楚了,只记得ODE, Newton之类的性能都差不多,而Physix即使是在没有物理加速的情况下仍然是大幅领先几个开源引擎。但是Physix一个比较郁闷的地方是它不是免费提供源代码。它现在只提供Windows, Red Hat, Debian的SDK。如果说想要在其它Linux下编译的话得话50美刀买它的源代码。源代码的许可协议没有仔细读,还不知道是不是能和开源项目一块儿发布。看来只能放弃Physix了。