« November 2009 | Main | January 2010 »

December 29, 2009

点光源的管理

我们 3d engine 的点光源相关的代码,以前设计的是比较糟糕的。最近几天,我决定自己动手重新设计和实现这块东西。性能倒是次要的东西,重要的是要把模块分离,减低耦合度。

这个光源模块设计要解决的问题在于:

GPU 的处理能力,目前看来比较有限,不可能实时处理无限数量的光源。所以,当你的场景里设置了许多的光源时,必须可以拣选出最可能影响被渲染物体的光源信息,把这个信息交给驱动去处理。

前任负责人在实现时,把光源揉杂在场景管理模块和渲染模块中去写,虽然功能实现了,但是维护麻烦。而且里面有很多需要性能优化的地方,由于结构设计不佳,导致动起来比较困难。更别说换个人去维护了。

增加关于光的新特性也会相对复杂。

经过一些思考后,我决定重新设计和实现。


虚拟场景是树状层次结构的,这个是很自然的设计。但是树状结构也比较难操作。而光源的管理,假设不处理复杂的遮挡(暂时我们游戏也没这个需求,有的话,也不违背以下设计),其实我们要的仅仅是知道所有激活光源在世界中的绝对位置。

所以,我把光源的位置管理藏在光的管理模块内部,在接口上并不暴露出这一信息。

作为光管理模块,我们需要的仅仅是把逐个光源设置进它自己内部维护的一个虚拟场景中(无层次结构)。然后在真正渲染时,取回空间中某个位置附近的光源而已。

为了给以后的优化留下足够的信息。我增加了一个受光体的概念。受光体保留自己在光场景中位置。我们向光的管理模块提供受光体对象,而不直接提交位置信息。这样可以留下 cache 层,加快查询速度。


这样,渲染流程就变成了:遍历场景树,将每个场景节点提交到下一层次。若是可渲染物,就提交到了渲染队列;若是光源,就把光源提交到了光管理模块。

在低一个层次,处理渲染队列时,经过若干排序和筛选操作后,真正渲染前,依据每个渲染物绑定的受光体对象,去光管理模块查询附近的光源,把这些光源包含的光信息提交给驱动层。


这里可以做的优化:

每个渲染帧,从接口上看,其实都从头构建了光源和受光体构成的场景(藏于光管理模块的内部,独立于场景树)。我们可以 cache 上一帧的场景,并加以比较。对于不变的对象,从受光体的内部取出以前计算好的值,直接返回。

光源位置管理,可以使用八叉树。如果是固定第三人称视角的游戏,四叉树也足够了。或者更简单一点,使用网格。设置光源坐标时,帧之间加上脏标记,可以轻易的获知是否需要重复运算。这个优化手段,可以把所谓静态光源和动态光源的处理细节隐藏在接口的背后。

打格子的方法可能是最简单有效的优化手段,比用其它复杂的算法计算一个受光体附近最近的若干光源更符合 KISS 原则。为了使格子简单有效,可以把格子的边长设置为略小于一个点光源大约可以影响的半径之内。每个点光源提交的时候,以围绕其坐标,以等边三角形的方位,提交三次即可。最终,只需要遍历受光体所在格子,就可以快速查到其附近的光源。

当然,一开始,我们不需要作任何优化手段。用最苯的 O(N*N) 的算法,检索所有提交的光源即可。先做对,再做好。

December 25, 2009

最近玩的几个游戏

上周末去上海参加了华东桌游嘉年华。

之前在杭州赛区赢了几个项目的预赛,拿到入场卷,所以门票就免了。最后以至于票多出来都没人要了。

赛场是在一个 LOFT 里,上面透风。同去的 A 同学的女朋友一直叫冷,我觉得还好,把外套借出去了。没想到感冒了,差点失声。估计另一个原因是我讲太多话了。

我在第一场现代艺术预赛里拿了5人组的第2。没得到第一纯粹是被一个不会玩的 mm 害了。然后去参加电力公司的复赛。由于时间太长,只好放弃了现代艺术的后续赛程。一开始有点可惜,后来听 A 同学讲述了半决赛经历后,我认为我们都没戏争夺冠军的。

几场比赛都深刻的领略了专业/职业玩家的实力。电力公司我参加的一个三人组,亏我一度以为赢定了,结果居然是第三 -_-

不过这个游戏我们玩的都不多,也就是打打酱油罢了。

前段因为出国旅游,错过了杭州赛区的报名,没得拿到银河竞逐的比赛入场卷。这个应该算是我个人最好的项目了吧。

第一天一直缠着主持人让他给我加个名额。只到第2天等到 C 组有人没到场,我才参了进去。可惜一开始友谊赛比的好好的,一正式比赛就输了 :( 还输的挺惨,拿到我有史以来最低分。中间算错对手一张牌,然后就崩盘了。毕竟还是跟高手打少了。我们自己人都玩的太休闲,经验是足够的,就是没真的参加什么比赛而已。没啥胜负心,所以也就嗑不下来。

当然,没加扩展包,也是很不习惯的。


这次学会不少新游戏,感觉非常爽快。最后还拍到几款想要的游戏,价格还算公道。

其中比较喜欢的是《历史巨轮》,就是一 文明 on table 。流程相当的长,我们玩短版都从晚饭后一直玩到半夜两点。想找到时间登上月球,实现共产主义,估计得一整天了。 :D

这个周末打算花一天时间来开《 Star Craft 》,这次自己买了,可以在公司开。


其实,桌面游戏的玩家群还真不小呢。

December 24, 2009

不要像小贝那样学习C++

小贝

今儿在 google reader 上看到有人推荐这篇文章,谈学计算机的问题。

上面的图是转过来的,《蜗居》第24集3:30秒截图 。这部片子同事前段 copy 给我,带在旅游的路上看的。我也就打发飞机上的时间看了一点。据说很火,但是跟我没什么共鸣,也就没啥欲望看完。

话说,《大规模C++程序设计》这本书,就胡乱翻过电子版的几页吧。算是本不错的书,可惜我对 C++ 失去兴趣已久,不太想读了。但就我读到的只言片语来说,这本书更多的是对 C++ 的友好批判。其实是很适合 C++ 中毒的程序员去读的。

正如引言中所述:”与主流观点相反,从根本上说,最普通形式的面向对象程序要比对应的面向过程的程序更难测试和校验。“

嗯,小贝为啥做的那么失败。不是因为他学计算机,不是因为他搞 C++ 。而是因为他就没好好去搞。

你看见他桌子上有别的书没?没有。桌子上就这么一本书。这本并不是工具书,翻了一半压在那里。这是本谈设计的书。

显然,小贝并不是一个富有经验的资深程序员。从他的年龄,以及生活状态就知道。那么他看这本书,仅仅只是出于学习,而不是工作需要。

而且这种学习,很可能不是出于内心的。若有自发的冲动,这本书翻了一大半没看完,一定会抱回家躺在床上读完的。你看见他在家读书了吗?

上班时,有这么多工夫读闲书(相对于工作直接需要的书),看起来事情不是很多的样子。在头几集里,小贝一开始是西装革履的出场。说明,他工作的公司还是挺在乎这个方面的。不是个纯粹的技术开发公司。这个小贝,平时用的开发语言,很可能并不是 C++ 。,而是用一些他自己看不起的语言(比如 js 之类)写写无聊的东西。

注意,我并不鄙视 js ,但是这个小贝应该是从内心鄙视他正在做的工作了。你看他桌面,一本相关的手册都没有。也无其它的资料。不仅如此,他旁边的工位,全部都空空如也。说明他处于的环境均如此。他认为,自己做的事情没有什么价值,无非一份工作而已。平时用的东西也很简单,根本用不着研究和学习。看 C++ 只是想跳出现在的工作,觉得 C++ 更为高级一些而已。

起手就读《大规模C++程序设计》,显然超出了自己的经验和能力。一个没有大规模程序设计实践经历的小孩子,能有多少领悟呢?难怪他读了一半倒扣在那里就读不下去了。

可惜啊,如此功利心,怎么才能真正学好东西呢?


小贝背后的同学稍微好点,桌上插了本《设计模式》 :) (见第 8 集 3 分 45 秒) 打酱油的群众

December 03, 2009

C++ 会议第一天

Lippman 大牛的第一场,关于大型可伸缩性的软件开发的, Chen Shuo 同学翻译的很不错 :D

找到电源,所以可以写写了。

果然是牛人啊,上来就讲形而上的东西。我听的有趣,就做了点笔记,但是记的不多。

我们从自然界去寻找灵感,然后在计算机领域去搞出来。以前的计算机是没有内存的,后来冯大侠说,计算机就像大脑,大脑是有记忆的,所以有了内存。

我们现在说大脑就像计算机,是本末倒置了。人们总是从自然界的角度来思考,然后解决软件里的问题。Lippman 牛的想法是,把软件比作生物,从 DNA ,细胞核开始向上一层层的。

系统的基础组织部分是 Data Structure 和 Data Stream ,这个就像细胞一样;在应用领域方面,Executive Function 和 Type Information 就好比生物的各个器官。

大牛参加了许多项目,他抱怨了一轮,说好多都可耻的失败鸟。大项目就是容易失败。程序员辛苦啊,根本不是所谓白领。而且每个程序员都是不可替代的。因为每个人的学习经历不同,看待问题不同,写出来的程序就不同。人们对编程的理解并不像想象的那么美好。现在慢慢的我们提高了抽象层次,按这个宇宙存在的方式去运作。但是从 java 开始学习编程,对程序员来说是有很大代价的,以前用 pascal 开始学习程序也有很大代价。大约是说,失去了对某些本质的理解。形成的对程序世界的世界观会有问题。

说回大项目,比如他参加的 Visual Studio 就不是啥成功的产品。用 .net 做 Windows 也很失败,那玩意根本就跑不快。微软做软件的哲学有问题,所以做不好。

有一个土星登陆器的项目,一代代技术都更新了。他作为技术顾问,提了些建议。主架构师纠结于用 java 还是用 C++ 这种问题上。其实架构师根本不应该关心用啥语言做。语言好不好都是屁话,把事情做好才对。最终项目是失败了。有很多问题都不是常规方法可以处理的。比如通讯的问题,因为土星上有什么什么,导致有时候信号 5,6 小时发不出去,等等。传统的通讯连接方式就不适用。

还有好多项目(有具体列举,没一一记了),做着做着,做了好几年,程序员心都凉了。

另一个是 MMO 项目,花了几千万,还是可耻的失败鸟。做出来后,什么都好,什么都很完美,只能支持 40-50 人在线。公司还说圣诞就要上。高层说,无所谓,不能玩也无所谓,做出来就好。结果当然是不能用的。开发人员心那是拔凉拔凉的。

再话说,Sun AT&T 几个公司想用 C++ 重写 Unix 。还有 IBM 等等用 Unix 的公司,搞了个啥邪恶同盟。反正最后也是可耻的失败鸟。

还有 Bell Labs 的 Plan 9 。东西是好的。不过根本不能成为一个产品。这里,提醒各位同学,找工作要小心。先侦察一下,如果公司就是要做个啥项目光冲着赚钱去的,这心态就有问题,肯定玩完。还有管理人员一定要懂技术,要知道做的东西是怎么回事。否则碰到这种倒霉事赶紧卷铺盖走人,别浪费青春。

接下去又说了好多悲剧,比如 IBM 的 OS/2 啥的。说着说着,说不下去了,名单太长,全是血泪史啊。

Lippman 接着自比江湖百晓生。我觉得他是自谦,想说自己其实只是倚老卖老,知道许多事情,参与了很多项目而已。


正题其实是说怎么做大规模可伸缩性的项目。结论很悲观,说 C++ 其实不适合做这个。最后我问了个问题,说那什么合适呢。他没正面回答。不过举了个例子,提了爱因斯坦的相对论,还有量子力学。大约是想说,C++ 更像是 BS 大牛个人的作品,他一个人构架了 C++ 的大部分东西。但是我们未来需要新的语言来解决问题的话,应该参考量子力学的发展过程,大家一起来构架。C++ 呢,说这个最后可能会被我们带进坟墓。不是 C++ 不好,是因为细节太多,没人全搞的明白。结果每个人写出来的程序都不一样。指定规范很难。最后会有很多人不愿意学。

正题里围绕的实际例子是在动画工业中的。其实做动画,好多工具都是用完即弃的。提高可复用性,关键在于要把可复用单元做的足够小。做大就没人理你了。

他们有人(貌似说的 pixar)做了个神奇的东西,反正就是类似 method 注册啦,动态生成类型啦之类的一个奇妙的 C++ 玩具。可以把代码动态的以字符串形式注册进去。动态生成一些类,一些接口调用之类。大约加了两个间接层。代码里充斥着所谓的注册代码。往往多达几千个。当然性能上也因为这个间接层,下降了几十倍。

当然,大型可伸缩的项目,性能也不是关键的东西。

这里还插了几句关于脚本的。说是有 C++ 程序员说,其实我拿 C++ 写什么什么也很快的。不过那不行,因为 C++ 程序员太少。你用 C++ 写没问题,不过要求你写完了翻译成 perl 代码.

不过这个东西很复杂,所以除了写它的人,没人愿意去看怎么实现的。后来做这个的那个家伙回巴黎去了。那些代码也很可怕,很复杂,里面也有很多 bug 。

后来 Lippman 也做了个类似的东西,也是号称 Metaprogramming ,不过不是所谓 template metaprogramming ,而是代码生成代码。最终自动生成的是 C 结构。不过主要目的达到,就是隐藏众多细节。有人说这个不是 OOP ,没有 class 啥的,不过他认为这个也是 OOP 。OOP 不能看表象。他说,他其实只是想明白个事,关于静态数据和动态部分之类。

这个例子我很有感触,因为我们公司曾经也有个类似的东西。做了个 C++ 和 lua 的巨复杂的粘合层。弄的看起来很高级。结果发明和维护的人走了后,用它的项目组都以把这坨东西从项目中去掉为荣。


说起大项目,Lippman 说,一切失败的大项目都有个通病。就是时间很长,经过几年后,就变成了一个封闭王国。结果没人知道在干啥。里面拉帮结派,为了一些无所谓的技术问题争来吵去。其实争论的都不是要干的事情。

另外,项目太大了后,就没人了解项目的全部细节。渐渐的,大家都只关心自己做的那一块。这样很糟糕。他思考后,认为解决的方法是,应该把结构旋转 90 度,变成一个有层次的结构。从上到下一层层剥离。同一层次上就不要横向切了。

嗯,这个问题我也很有感触,虽然我的项目不算特别巨大。但是只有我一个人了解项目全部的细节,这让人很累。当然如果要每个人都了解全部细节,就会让每个人都很累。


以上是我凌乱的一些听课笔记。很多有趣的东西没来的及记下。可能也有很多我的误解在里面。同学们姑且看之吧。