« June 2009 | Main | August 2009 »

July 29, 2009

3d engine 中的贴图资源管理

今天有同事问了我一个涉及贴图管理的问题,看起来他们是想改进他们项目现在用的 3d engine (前些年由网易方舟工作室开发的)。我们随便聊了一下,最后的结果是他们取消了一开始的一个需求。

是的,知道自己最终需要什么是特别重要的,不要把过程当成目的。

下面要写的和今天的讨论无关,只是想记录一下:我们的 3d engine 中的贴图资源管理方案。

资源管理是一个很复杂的模块,当然我们应该尽量简化它。在此之前,我曾经记录过我们的资源管理模块的设计变迁。上篇文章到现在也有几个月了,我又做了些设计上的简化,不过变化不大,暂时不提。

而贴图资源作为一种特殊资源,又有所不同。仔细斟酌之后,我把它放在高一层次专门管理。

如前辈所言:确保特殊的情况是真的特殊。在《The Elements of Programming Style》和 《Unix 编程艺术》中都有提及。

那么,第一个问题是:为什么其是特殊的?

在 3d engine 中,贴图往往占用的是显存,而不是内存。系统显存的上限和内存上限是独立的。显存的使用策略,和相关 api 限制(比如多线程因素)稍微复杂一点。

另外,贴图并不总是可以直接从外存加载进来。在支持换装系统的 3d engine 中,某些贴图是由多张小贴图,或多张贴图的一部分组合起来的。比如把人物的上衣、皮带、裤子等等分放在不同的贴图上,使用的时候再组合成一整张。这是因为,对于显卡来说,零碎的贴图会极大的降低性能。

组合贴图这点破事,看起来很好实现。实际上优雅的管理它们,又兼顾一些性能,还是不太容易的。据我所见,至少网易已经运营的 3d 游戏所用的 engine 中(天下所用之 bigworld 和大唐系列所用之大唐)并无很好的管理方案。其结果是,人物换装不那么细腻。而在 wow 中,你可以单独更换身体的许多细节部分,而在外观上表现出来(哪怕只有一小点变化)。

ps. 当然,换装系统不仅仅是更换贴图。

我所用的方法是定义一个贴图组(Texture bundle)数据文件。里面描述了不只一张贴图。对于 engine ,直接使用贴图组的默认贴图。但是可以动态组织它。

如果需要整张贴图更换,直接设置贴图组的状态,切换到某一张具体贴图数据上。

这样做的原因是,模型由美术制作好后,并非可以任意更换贴图数据。往往只是某几张特制的贴图可以互换。如果由使用者为模型任意指定贴图显然是不合适的,而切换贴图组的状态则更为易用、健壮。

如果需要拼接贴图,则在贴图组中描述出矩形的区域划分。每张具体贴图都按统一的划分方案制作局部图案。

单张贴图可以只有局部图案,而不需要全部区域填满。

使用的时候,使用者提供一个 pattern 来组合出最终需要的贴图。即:每个区域使用第几张贴图。

在实现的时候,我采用方便解析又适合做 hash key 的单个字符串来描述 pattern 。


关于贴图的管理:

采用一个两级 hash map 和一个 list 的复合数据结构。

第一级 hash map 用来从一个资源对象检索出贴图数据块(对应一个贴图组)。第二级 hash map 用来 cache 从一个特定的贴图数据中,以一个特定 pattern 组合出的需要的贴图。

list 是一个先入先出的按使用频率排序的最终贴图对象列表。

从第一级 hash map 得到的贴图数据块,以一个永久有效的 handle 索引。(因为它一定会对应唯一数据文件,数量有限,故而我们不需删除 handle )

engine 使用贴图前,都需要从上述 handle 中拣选出所需要 pattern 。使用者不可认为拣选出来的真正贴图对象一直有效。事实上,engine 只保证其有效期维持到当前帧渲染完毕。

这个设计可以让 engine 的贴图管理模块,以类似操作系统管理物理内存那样,根据实际资源情况释放掉暂时不在使用的显存。并 cache 住那些常用的贴图 pattern 。


由于贴图数据的特殊性,有时候,我们需要其以 id 的形式纳入显卡驱动层的管理下;而另一些时候,我们可能需要访问其数据。所以贴图对象有两种存在于 engine 内的形式。

我们在设计的时候,参考了 freetype 2 对字模的管理方式。让这些数据以 slot 的形式存在并让用户去访问。访问之前,调用对应的 api 加载即可。而不用理会其生命期。(engine 保证数据到当前帧渲染完毕前都有效)


btw, 对于 DXT 类的压缩贴图。了解了它的原理和数据格式 后,也是可以直接切分和组合的。只是要按 4x4 像素为一最小单元去操作。

July 26, 2009

几款重口味的桌游

我从小就追求复杂的游戏,如果一个游戏不够复杂,就想办法改进它。

好吧,从我周遭的朋友圈来看,像我这样重口味的玩家不算多。天知道有多少同好,反正,现在想凑齐人好好玩上一局冰与火之歌是满难的。上次难得碰上几位,居然一盘玩了七小时。这还没加入两个扩展包。

昨天难得休息,拉了一车人去桌游吧想开一局 AA50 。可惜没有。只是试了一下老版的 AA 。游戏过程中老有人钻过来旁观,貌似一大桌豪华阵容颇能吸引旁观者。只是我心里晓得,真正愿意自己玩的人还是少数。就好象许多号称自己是游戏迷的人只喜欢看人打游戏,让他自己来就不行了。

无数弱智网游能够风靡全国也是可以理解的。我已经听过太多人说:休息的时候还让我动脑子,累不累啊。

嗯,突然想起来,博文的周老师送我的一本《把时间当作朋友》,前两天休年假,我花了一天读完。原本答应写书评的,可又不知道可以写什么。感觉书里说的都是至理。可是可是,明明都是应该人人皆知的道理嘛。真的有人不懂这些么?不需要多加评论吧。我想,应该真的是有人不懂的。但,不懂这些道理的人显然不会动念头读这本书了。还真是个悖论。

劝人做一些在他的思维结构中没意义的事,是件很不靠谱的事儿。即使这事儿你觉得多有价值,那也是对你自己而言。

话说回来。AA 系列(Axis and Allies)是个好游戏。不过我没打算自己入手一套。AA50 也太贵了,貌似买下来也不一定有机会找到人一起玩。不过手痒的话,有开源的程序实现,叫做 TripleA (三个 A 嘛)。可惜,前几天被人告了,下载安装包被撤了下来。侵犯了版权。也是,毕竟游戏的规则和数值设定才是精髓。写个程序实现和山寨一套性质差不多。有兴趣的朋友自己 checkout 源代码吧,或者自己找一下,也是找的到下载的。

另一个和冰与火类似的游戏是 Starcraft 。值得推荐一下。别觉得起了这么俗的名字就不屑一顾。其实还是很值得一玩的。

近期我这里开过的游戏,还有小世界和佣兵队长,都还不错。可以满足快餐游戏的要求。

银河竞逐依旧是我们办公室里的最爱。第二扩展已经出了,某同学答应从美国帮我带一套回来,非常期待。唉,taobao 上怎么还不见有卖的呢?

ps. 最近还想入手一套港口(Le Havre)。

July 24, 2009

老人言

《The Elements of Programming Style 》是一本很古老的书。尽管 Fortran 我们不太使用,尽管新奇的语言层出不穷,但这些,30 年的岁月依旧无法掩盖其中的真知灼见。

英文版的 google 一下到处有,云风试着摘译几条。

  • 把代码写清楚,别耍小聪明。
  • 想干什么,讲的简单点、直接点。
  • 只要有可能,使用库函数。
  • 避免使用太多的临时变量。
  • “效率”不是牺牲清晰性的理由。
  • 让机器去干那些脏活。
  • 重复的表达式应该换成函数调用。
  • 加上括号、避免歧义。
  • 不要使用含糊不清的变量名。
  • 把不必要的分支去掉。
  • 使用语言的好特性,不要使用那些糟糕的特性。
  • 该用逻辑表达式的时候,不要使用过多的条件分支。
  • 如果逻辑表达式不好理解,就试着做下变形。
  • 选择让程序更简洁的数据表达形式。
  • 先用伪代码写,再翻译成你使用的语言。
  • 模块化。使用过程和函数。
  • 只要你能保证程序的可读性,能不用 goto 就别用 。
  • 不要给糟糕的代码打补丁 - 重写就是了。
  • 把大的程序分成一小片一小片来写,分块测试。
  • 使用递归程序来处理递归定义的数据结构。
  • 正确和错误的输入数据都要测试。
  • 确保输入不会超出程序的限制。
  • 依靠文件结束来终止输入,而不是依赖一个记数。
  • 把文件结束作为一个输入状态来处理。
  • 识别出错误的输入;如果有可能就修复它。
  • 让输入数据很容易构造出来,让输出数据不言自明。
  • 使用统一的输入格式。
  • 让输入容易校对。
  • 如有可能,提供更自由的输入格式。
  • 使用输入提示,允许使用默认值。并把它们显示出来。
  • 把输入输出放到子程序里。
  • 确保所有的变量在使用前都有初始化。
  • 不要因为一个 bug 而停止不前。
  • 打开编译程序的调试选项。
  • 常量结构用数据声明初始化,变量结构用执行代码初始化。
  • 小心 off-by-one 错误。
  • 当循环中有多个跳出点时要小心。
  • 如果什么都不做,那么也要优雅的表现出这个意思。
  • 用边界值测试程序。
  • 手工检查一些答案。
  • 防御式编程 - 为不可能的情况写几句代码。
  • 10.0 乘 0.1 很难保证永远是 1.0 。
  • 7/8 等于 0 ,而 7.0/8.0 不等于 0 。
  • 不要直接判断两个浮点数相等。
  • 先做对,再弄快。
  • 先使其可靠,再让其更快。
  • 先把代码弄干净,再让它变快。
  • 别为了获得一丁点“性能”就牺牲掉整洁。
  • 让编译器做些简单的优化。
  • 不要过分追求重用代码;下次用的时候重新组织一下即可。
  • 确保特殊的情况是真的特殊。
  • 保持简洁以获得速度。
  • 不要死磕代码来加快速度 - 找个更好的算法。
  • 用工具分析你的程序。在做“性能”改进前先评测一下。
  • 确保注释和代码一致。
  • 不要在注释里仅仅重复代码 - 让每处注释都有价值。
  • 不要给糟糕的代码做注释 - 应该重写它。
  • 给变量都起个有意义的名字。
  • 把程序重新整理一下,让阅读代码的人更容易理解。
  • 为你的数据布局写一个文档。
  • 不要过分注释。

July 07, 2009

GNU Make 下创建目录的问题

很多时候,我们的 Makefile 在工作的时候,往往需要把中间文件放在独立目录中。这个独立目录一开始又没有创建出来。所以,Makefile 就有责任创建它们。

正确的创建目录,对于 Make 来说可是一个头痛的事情。

直观的写法是让目标依赖目录。比如:

foo.c : out/foo.o

out/foo.o : out

out :
    mkdir $@

这样做的问题在于,out 作为一个特殊文件(目录文件),时间戳是不受控的。

如果你删除或添加新文件到 out 目录下,都会更改 out 的时间戳,这会进一步的影响其依赖的目标。

我以前的解决方法是,放一个 probe 文件在目标目录下。这个文件的时间戳就是正常的,它在目录第一次被建立时建立,以后不再更改。

out/foo.o :foo.c  out/.probe

out/.probe :
    mkdir -p $(dir $@) && touch $@

这个方法我用了半年,总是有点不爽(因为那个多余的文件)。尤其是在 Windows 下时,dir 不会隐藏 . 开头的文件,让我不能眼不见心不烦。跟 svn 在目录目录下创建一个 .svn 目录一样的让人恼火。

今天仔细研究了一下,发现 GNU Make 3.80 以后的版本可以比较完美的解决这个问题。

方法是,把目录作为 order-only 的依赖。写法是在填依赖关系时加一个 |

out/foo.o : foo.c | out

或是写成两行

out/foo.o : foo.c
out/foo.o : | out

out 前修饰了 | ,这样,只有在 out 不存在时,才会提前(在构建 out/foo.o 前)去构建。当 out 已经存在,out/foo.o 则不依赖 out 的时间戳。

参考:GNU Make 手册:4.3 依赖的类型


如果一个项目需要大量创建中间目录,手写每个目录的构建规则肯定不合适。那么如何批量创建目录呢?

我的方法是,每次依赖一个中间目录时,就把目录名加到一个变量中。如:

MKDIRS += out

然后在 Makefile 的末尾:

$(sort $(MKDIRS)) :
    mkdir -p $@

不过,这样做还有一个缺陷。如果需要创建的目录有父子关系,一个更深层次的目录被创建出来后;随后创建的目录就会因为存在而创建失败。

固然,我们可以在 mkdir 前加上 - 忽略出错信息。但这不符合我的审美观。

我的解决方法是,过滤出有父子关系的目录,让浅的目录依赖深的目录,只在深层目录上真正 mkdir 。

代码如下:

MKDIRS := $(sort $(MKDIRS))

define SAFE_MKDIR
  CHILD := $(firstword $(filter $(1)/%,$(MKDIRS)))
  ifeq ($$(strip $$(CHILD)),)
    $(1) :
    $(MKDIR) $$(call pathname,$$@)
  else
    $(1) : | $$(CHILD)
  endif
endef

$(foreach dir,$(MKDIRS),$(eval $(call SAFE_MKDIR,$(dir))))

如果你想直接使用,请注意以上的空格和 Tab 的区别。

July 02, 2009

关于“群”的那些破事

在 QQ 增加所谓“群” 这个功能之前,我就不用 qq 了。(所以找我要 qq 号的朋友不要再问了)

但是“群”这个讨厌的东西,总是阴魂不散的游荡在我的网络世界里。

今天在 twitter 上看见 Fenng 说 “我真受不了我可爱的同事们了,你们就不能不用"群"啊? 这是 IM 工具最烂的一个设计。除了浪费时间,还能干什么?” ,真是心有戚戚啊。

当然,人和人对事物的看法见解是不一样的。物以类聚、人以群分吧。我还真见过真心喜爱“群”的同学,大体上和 xmpp 同学以及Fenng 随后的发言一致。虽然分享“小笑话、新闻链接、有趣的小图片” 我觉得应该属于 google reader 的事情,

popo 作为网易内部交流工具,当初设计群的时候,我是发过言的。情况大致是这样:

一开始,dingdang 认为 popo 没有一个专门做产品的人,都是程序员自己在想应该怎样怎样。这样是做不好产品的。姑且不论程序员主导开发好或不好。我当时也是很赞同应该有人专门去考虑 popo 作为一个产品应该怎么制作和发展的。

IM 是个不错的东西,(虽然我个人更喜欢 email)。应该好好做。我那段时间跟 popo 的人聊的很多。这大约是 03/04 年的事情。

我是很反对增加“群”这个东西的。但是据说“用户”很需要。虽然我一直都觉得,不要听用户的 ,但是,做一个类似但更好的东西是有必要的。

更早一点,大约是 02 年。当时 popo 组的负责人黄(后来去做飞信的那位兄弟)曾经问我,除了游戏和 IM 我们还可以做点什么?我想了一下说,个人意见是:互联网上最需要的还是人和人的沟通。但不局限于 IM 。从那时起我就在想,到底我们需要一种怎样的沟通工具,可以让更多的人发出的有用的信息方便的聚集到自己这里。

所以、在 popo 增加群功能前,我把自己的想法写了几千字,希望可以做一个更好的“群”。不过 popo 组的人最终拒绝了我的提案。因为很难跟用户解释。用户没有见过这样的东西,而“群”已经深入人心,只要做一个一样的,就至少不会错了。

记得当时我们争论的问题还有类似的许多。比如到底是否存在一种最好的信息组织方式。用户的行为能不能引导。比如说,我坚持,搜索是一种比分类更好的方式,只要适当引导,用户会更偏向前者;但是反对的声音是,有人天生就热衷与自己分类,大类分小类的分下去;搜索只会让信息更乱。(所以、popo 差点就在好友管理中加入树状分类结构,最终只是程序和 UI 设计人员觉得麻烦而没能实施)

话说回来、当时我的建议归结起来很简单:就是类似 twitter 的方式。每个人的消息不要有准确的接收者,而是尽可能的广播出去。在消息里加入适当的关键词。(类似 twitter 的 @ 和 # )。而后,接收者自己选择过滤出自己感兴趣的信息。

作为 IM ,还可以针对特定消息随时展开聊天室讨论。讨论的过程可以全文从 web 上查阅历史。从这点上有点点类似于后来出现的贴吧。就是以某个主题为线索展开,而不是以固定的人群,固定的聊天室。这也是对需要闲聊扯谈的人的一个满足。

时隔五年,现在这些概念相对好解释的多。因为现在我们有了 twitter 有了 facebook google reader …… 而用户,接收了它们。但我还记得当年,花了两个小时,才给一个人解释清楚我想要的是什么。而他在听完之后的第一反应是:高频率的广播消息?用户会受不了的。

后来、群的功能被加上。如同 qq 的 clone 。

如我所料、在群的忠实用户之外,还有一群如我一样的用户,即使被加入了群,也几乎不去查看群的信息。久而久之、许多群已经失去了当初设计他的人希望达到的功能。(当然,作为 clone 产品,我们需要的并不是考虑为用户带来点什么、也不必要去希望达到什么功能,而是考虑如何 clone 的跟本体一样就行了)

又过了几年,终于公司内部发通知,要求员工上班不得使用群。(虽然部分所谓工作群除外,但事实上否定了群的意义)


本质上,网易是个不愿意创新的公司,这点几乎写到了骨头里。不过这也不算坏事。这样,公司的发展更为稳重、少犯错误。我也不因此抱怨。即使脑子里总会蹦出些新奇的想法,但不至于冲动的立刻去干,在这样的环境下,会有更多的时间思考。因为、大部分新想法其实是不切实际的。

哦,我说的是“创”新。对于被验证过好的新事物,公司还是跟的很紧的。比如,gmail 刚内部测试放号的时候,我弄了一个玩。立刻惊叹于基于 ajax 的 web mail 可以这样好用。当天晚上就跟丁说,我们的 web email 系统也应该这样做。然后没多久,163 的 email 就更新了。老板推动的事情总是很积极的 :) 。


btw, 我们的 popo pidgin 插件已经可以收发群消息了。需要的同事去 sf checkout 代码自己编译使用。