Jan 1

关于Euclideon的"无限细节"引擎的技术分析

游戏开发

 昨天看了一个震撼的视频, 地址在这里 http://www.tudou.com/programs/view/2oH1zMMCWqY/, 视频中宣称的无限细节引擎技术与现在主流的3d引擎技术完全不同, 传统的3d引擎技术基于多边形, 画面细节的丰富程度取决于多边形的个数和贴图的细节, 而"无限细节"技术则采用和自然界一样的原子排列方式来渲染图像, 或者说点云技术, 根据视频宣称可以比现在3d引擎提高10万倍的细节丰富程度, 而且完全不采用显卡的3d计算能力, 完全纯软件技术, 并最终达到20fps, 如果这一切都是真的, 那必将颠覆现有的3d渲染技术, 为此我思考了一个晚上也百思不得其解, 今天在其官网上找到了一些技术细节.

Unlimited Detail's method is very different to any 3D method that has been invented so far. The three current systems used in 3D graphics are ray tracing polygons and point clouds/voxels, they all have strengths and weaknesses. Polygons run fast but have poor geometry, ray-tracing and voxels have perfect geometry but run very slowly.
Unlimited Detail is a fourth system, which is more like a search algorithm than a 3D engine. It is best explained like this: if you had a word document and you went to the search tool and typed in a word like 'money' the search tool quickly searches for every place that word appeared in the document. Google and Bing are also search engines that go looking for things very quickly. Unlimited Detail is basically a point cloud search algorithm. We can build enormous worlds with huge numbers of points, then compress them down to be very small. The Unlimited Detail engine works out which direction the camera is facing and then searches the data to find only the points it needs to put on the screen it doesn’t touch any unneeded points, all it wants is 1024*768 (if that is our resolution) points, one for each pixel of the screen. It has a few tricky things to work out, like: what objects are closest to the camera, what objects cover each other, how big should an object be as it gets further back. But all of this is done by a new sort of method that we call "mass connected processing". Mass connected processing is where we have a way of processing masses of data at the same time and then applying the small changes to each part at the end.
The result is a perfect pure bug free 3D engine that gives Unlimited Geometry running super fast, and it's all done in software.

 

看完之后,我大概了解了其原理,虽然还是感觉不可思议.

1)与传统3d技术不同, 该技术更像一种搜索技术, 一种点云搜索算法;

2)通过把世界用海量的点来描述, 然后压缩这些点数据便于使用;

3)通过相机的位置和面向, 搜索出画面里需要的点, 任何不需要的点都不会出现在搜索结果集里;

4)如果我们画面分辨率为1024x768, 那么最终的搜索返回的结果点也是1024x768;

5)在搜索的过程需要考虑: 那些太靠近相机的点, 那些互相覆盖的对象等;

6)所有这些通过一种新的排序方法, 叫做"mass connected processing"来完成;

7)最终这些点被用于渲染画面, 所有这些过程全部都是在cpu内软件完成.

 

该技术确实不同于传统的3d渲染引擎, 该技术的核心算法应该是搜索和排序, 如果最终返回的点集是1024x768, 那么确实在渲染上和gpu关系不大了, 纯软件渲染足够了. 

Sep 29

让我们来聊聊Flash 11

游戏开发

"Let’s talk iPhone", 这是即将发布的苹果大会广告语, 新版的iPhone5预计会在大会上发布,差不多的时间Flash11正式版也会发布,so, Let's talk flash11.

 

新版的Flash11最让人瞩目的特性就是硬件3d加速,并提供一套基于actionscript3的3d api,这将是web game一个新的起点,未来3d webgame应该会成为主流, adobe官方把新的3d技术叫做molehill, 它定位与高端图形渲染, 在windows上基于dx9, mac/linux上基于ogl1.3, 移动设备上基于openGL ES2.

molehill是所谓真正意义的3d, 比之前flash10的2.5要高效很多,flash10采用的是基于矢量的三角形变化,没有z-buffer,没有硬件加速,所以一般同屏就能处理千八百个三角形; 而molehill则是完全基于本地3d api, 基于shader的可编程管线, 可以全高清的情况下,以60帧率,渲染上百万个三角形, 这是官方的一个demo, 已经不低于客户端3d引擎的效果了.

在新的渲染架构下, video frame和3d buffer不再基于display list, 而是基于texture, 这将允许直接渲染到显卡内存里, 没有回读导致的gpu暂停, 从而根本上提高硬件渲染效率, 准确的说3d渲染是在最底层的,2d渲染在其上层,如图(就是游戏的做法,底层是3d渲染场景,上层是2d渲染ui等)

Stage3D Model

当然如果有需求把3d渲染放到2d上面, molehill提供了一个方法把3d渲染结果画到BitmapData里,当然这可能需要video memory read back了,在不同机器上效率不同,我之前有多篇blog介绍这个问题,有兴趣的朋友可以自行搜索.

ps:对于硬件不支持的机器, molehill自动采用软件渲染, 并保留全部硬件支持的特性, 对于程序员完全透明, 即便完全软件渲染, 也比之前flash10快10倍, 因为据说这部分技术是使用的SwiftShader,人家专业做纯软件渲染.

ps:molehill完全不支持固定管线渲染, 必须使用可编程管线,与dx10保持看齐.

Shaders

ps:现在已经有不少基于flash11的3d引擎面试,其中不乏open source的,比如away3d, 据说adobe自己也在开发自有3d 引擎,帮助程序员快速搭建3d应用.

看到这些你是不是已经非常期待flash11的到来? 不管你期待与否 ,我是非常期待.

Apr 12

关于游戏里的ui

游戏开发

今天要说的是游戏里的ui, 说到ui, 我的经验是最丰富的, 之前进入网易先开始搞的就是梦幻西游的ui, 是一个图文混排的控件, 可以理解为richview, 允许表情包子和颜色文字混排, 实现聊天记录的实现和编辑. 后来搞天下贰也完整的实现一套3d游戏环境下的ui系统.

按理说ui系统是游戏开发过程中一小部分工作, 但它却贯穿了整个游戏开发的全过程, 直到我离开天下贰项目组, 都还在不断的根据需求修改ui引擎实现新的功能, 可以说整整搞了5年的ui, 所以到我们自己出来创业搞xero引擎, 我一点都不想再搞ui系统了. 所以ui说是小系统, 但却实实在在是一个大问题. 写这篇blog的缘由是上周去参加bigworld开发者大会, 其间与w公司一个技术人员讨论ui实现, bigworld可是说提供了完善丰富的3d引擎基础功能, 但ui系统这块欠奉, 或者不尽如人意, 据我所知, 所有购买bigworld的国内公司, 都需要重新独立研发一套的新的ui系统, 这里需要考虑的问题如下:

1) 功能完整

2) 性能

3) 脚本封装

今天我只说下功能完整性这个问题, 到底什么样的功能才算完整的, 很多初次实现ui系统的同学会类比windows mfc或者vcl等ui框架, 把各种功能的控件, 控件的操作方法都实现到ui系统里, 这样来体现ui系统的强大. 我个人不以为然, 至少在游戏ui系统中, 只要实现几种基础控件, 就能满足游戏里大部分需求. 比如ListView和TreeView这样的控件, 到底有没有必要在ui引擎中提供(注意这里是说的ui引擎级别, 不是应用层面, 从应用层面肯定需要这个控件), 我个人认为没有必要, 但我听很多童鞋抱怨过treeview控件又加入新的需求了--- 要在每个treeitem后面加入一个图标, 因为在标准windows控件里没有这个需求, 一般都是前面有个图标, 后面一个文字, 所以很多ui系统的实现者都会想当然的按照windows的习惯来实现这个treeview控件.

ui实现最重要的原则是抽象, 而不是具象, 以上面的treeview为例, 更抽象的实现是只实现:

Image显示图片(支持动态图片)

Label显示文字

Panel控件容器, 可以作为View, 可以支持裁剪.

剩下的工作就是在脚本应用层面:

使用Panel作为TreeItemView, 根据鼠标操作动态的layout treeview控件, 如果在panel中放入[Label], 那它就是一个基本的文字treeview, 如果放入[图片-Label-图片]就是上面需要的TreeViewItemEx, 将整个TreeViewItem layout进入一个新的panel, 就得到了一个支持裁剪的TreeViewEx控件. 一般这里使用Adapter模式来做TreeView和TreeViewItem的适配, 同时做到数据和view的分离.

关于允许拖动改变窗口的大小

这个问题是我同w公司的同学争论最多的一个问题, 这是一个功能完整性的问题. 他的意思是要支持这个功能, 或者说提供SetSize这样的功能, 于此同时要支持其中的子控件自动relayout, 这里说的不是Windows窗口改变大小后, 如何适应尺寸变化的问题, 我的意思是这是过度设计, 或者是windows想法的照搬. 更重要的是, 他们w公司要因为这个需求重新设计推翻之前的ui系统重新实现,而推动这次ui重构的根本原因, 在于策划早期ui需求的多变不确定性, 需要不断尝试不同大小, 不同布局的ui表现, 所以又是策划一句话,程序跑断腿, 当然这是一个理念和需求问题, 而不是对错的问题. 争论了半天也没有结论, 各执一词.

从理念角度讲, 如果你的ui系统是为了更通用, 能够独立服务更多游戏ui需求, 他的意思是无可厚非的, 但其实大部分游戏的大部分ui表现没有这个需求, 在游戏中大概99%的ui, 都是只有固定大小, 不需要改变尺寸, 不需要重排, 因为几乎所有ui都是一张复杂的底图, 当然也有例外, 比如聊天记录框, 为了让用户看到更多的历史记录, 需要根据用户喜好调整合适View尺寸, 一般这种窗口的实现都是9-patch平铺来实现,有这个需求, 实现一个9-patch的Panel控件就解决问题了, 真的需要到重新实现ui系统花费5个月时间吗?

关于ScaleForm

这是个好东西,特别是4.0后,这个ui实现变的更快了,星际二也用它作为ui系统,我之前的博客还写过这个东西, 还自己实现了一个类似的SFlash的替代方案, 它唯一的问题是会flash, 懂得ui, 懂点程序, 懂点游戏逻辑的人太难找, 简单说就是使用门槛太高, 直接导致人力成本提升.

Mar 10

Google的C++代码风格指南(1)

程序人生

不经意看到李开复的微博说google的代码规范是全球最好的,没有之一,于是好奇到底好在哪里, google找到地址:http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml, 阅读了部分, 深有同感, 写些心得.

首先关于定义define保护宏, 我很早之前写代码有这个习惯,那个时候记得应该是vc6的时代, 就是类似这样的代码:

#ifndef FOO_BAR_BAZ_H_#define FOO_BAR_BAZ_H_...#endif  // FOO_BAR_BAZ_H_

目的是为了不会重复引用, 但后来vc增加一个关键字, 如果没有记错的话,这个关键字是从borland c发展而来的, 就是:

#pragma once

也能起到同样效果, 告诉编译器这个头文件仅引用一次, 不重复包含.

我刚才特意到g++上测试了下,也是支持#pragma once这个指使字的.

关于匿名名字空间

Google是鼓励使用匿名名字空间的, 记得之前看过一篇文章说, 匿名名字空间会带来代码调试的困难, 深感不以为然, 今天再次看到google的规范鼓励匿名名字空间, 深得我心. 使用匿名名字空间的好处在于运行时命名冲突, 一般解决这个问题还有一个方法是static.

关于局部变量的位置

int i;i = f();      // Bad -- initialization separate from declaration.
int j = g();  // Good -- declaration has initialization.

Bad的写法是习惯了c语法的童鞋, 因为c语言要求变量要在函数头部申明, 这样在函数头部放了一堆变量申明, 代码改动多了之后, 也不知道哪些变量后来有没有用到, 反正摆了一堆, 喜庆的是c99后来也不强制要求了.

Good的写法是我一直的书写习惯, 按照google的说法, 就是变量的申明尽量在使用它的地方, 最好能一眼看到在那里申明的, 当然为了某些效率考虑, 可以例外, 比如:

Bad

// Inefficient implementation:for (int i = 0; i < 1000000; ++i) {  Foo f;  // My ctor and dtor get called 1000000 times each.  f.DoSomething(i);}

Good

Foo f;  // My ctor and dtor get called once each.for (int i = 0; i < 1000000; ++i) {  f.DoSomething(i);}

不建议使用全局类变量(包括static), 因为这将导致某些bug很难发现, 因为无法决定类的构造顺序.

我点我更是感同身受, 之前在写big world代码时候, 就发现了这个问题, BW里充斥了各种static 全局变量作为singleton, 我还特别写了篇blog说明这个问题, 当时是为了检查内存泄露, 经常是不同singleton退出时依赖, 导致各种退出crash, 后来没有办法都只能直接new一个就不管了, 靠os回收.

Feb 23

把iphone的联系人,短信导入魅族M9

程序人生

最近业余开发android系统, 随便买了个国产神机M9,之前一直在用iphone,于是想把iphone的联系人和短信导入新的手机, 下载了个91手机助手,发现他有android系统一键转机,可惜试用后发现不支持魅族深度定制的android系统, 随手又试了试其他android转换软件也没有合适的,无奈之下自己研究,发现可用方法,为此也写了个python转换脚本.

先说说通讯录:

我的方法是用91导出vcf通讯录文件, 然后转换编码为utf8格式, 存入SD/Contacts目录,在使用M9"导入SD卡联系人功能",就可以了,如果不转换utf8格式会有乱码.

麻烦的是短信:

我iphone用了2年多,积攒了5-6k条短信,不想就这样丢了,经过不断试验研究魅族sms.xml格式, 写出转换脚本

# Convert iphone sms to M9 
# Author: Siney (siney#yeah.net) 
from sqlite3 import * 
from xml.sax.saxutils import escape 
import codecs 
import re 
f = codecs.open('sms.xml','w','utf-8') 
f.write ('''<?xml version='1.0' encoding='UTF-8' standalone='yes' ?> 
<SmsTable> 
<Product>M9</Product> 
<SoftwareVersion>1.0.0</SoftwareVersion>''')

c = connect('sms.db') 
curs = c.cursor() 
curs.execute('''SELECT address,date,text,flags FROM message WHERE flags<5 ORDER BY date asc''') 
for row in curs: 
        a= escape(unicode(row[0])) 
        d = escape(unicode(row[1])) 
        t = row[3]-1 
        t = str(t) 
        b = re.sub('"',"'",escape(unicode(row[2]))) 
        if b!="None": 
            f.write(u''' 
<Sms> 
<MobileNumber>%s</MobileNumber> 
<Body>%s</Body> 
<Read>1</Read> 
<Status>-1</Status> 
<Type>%s</Type> 
<MessageType>0</MessageType> 
<ReportDate>0</ReportDate> 
<SendDate>%s000</SendDate> 
<Protocol>0</Protocol> 
<ErrorCode>0</ErrorCode> 
<Seen>0</Seen> 
<Port>0</Port> 
</Sms>'''%(a,b,t,d))

f.write('''</SmsTable>''' )

首先使用91助手,导出iphone短信数据库sms.db, 然后把上面的脚本放入sms.db相同目录,python运行脚本得到sms.xml文件, 这个文件就是m9可是识别的短信备份文件,在m9中恢复用户数据->短信就可以恢复全部短信(不包括彩信).

Feb 15

过年宅7天, 杂记

程序人生

过年回家,准确说,回哥哥家,成都,宅了7天,其中穿插着看了"非诚勿扰"和伪穿越剧"宫", 自从那个宝马马诺走后就一直没有关注过"非诚勿扰", 感觉话题超做完了, 就没有什么看点了, 但新年实在无其他好看, 勉强看下去, 感觉还是不错的, 感觉江苏卫视选择男嘉宾时故意选择一些容易产生话题的, 每期必有几个看着与众不同的男士, 总感觉跟真实生活中接触的人有差距, 还是上了电视, 大家一紧张, 露馅了?

还有那个伪穿越剧,bug太多,实在不忍细看,网上吐槽的一大堆,唯一让我感觉好的就是, 湖南卫视总算能拍出tvb感觉的片子了.

1.ipad 植物大战僵尸又通关一遍,实在无聊拿出来把玩,结果无意间又通关了,pvz2啥时候能出来啊,一定支持正版.

2.看了传说中的三体1,2,3,之前看过球状闪电,"球"写的一般,还在豆瓣上写了篇差评的评论,没来没有对三体抱太大希望,结果出乎意料感觉三体写的确实不错,作者的有些想法我很小的时候也想过,比如所谓的宇宙社会学,我也写过程序模拟这种可能的竞争冲突.当看到三体世界的描述时,自然产生对地球物理科学的怀疑,也许一切都是巧合而已,何谓科学/定理?

3.看了成都的房价, 感叹成都竞争力很大啊, 在北京五环外买一所破房子的价格可以在成都更好位置买一栋豪宅,还尚风尚水.

4.做了个所谓专业的性格,职业测试, 又是答题,又是画画,又是冥想,结果和自己对自己的认识差不多,不知道这种测试的意义在那里?

Jan 19

Android sdk中使用源代码调试

编程心得

最近尝试了下android平台开发, 动不动Android api就抛出异常, 而异常了也没有明确的错误说明, 默认情况下Android sdk发行的开发包里是不包含源代码的,所以异常错误了就是一个"Attach source"按钮,甚是不爽,不得已必须调试其源代码,搞明白为啥异常了, 方法如下:

首先需要安装git, 这是一个分布式代码版本控制软件, 可以参考我之前的博客.

然后进入 git bash 执行如下命令:

git clone git://git.source.android.com/platform/frameworks/base android-api

这一步需要很多时间, 也有可能被墙..., 如果搞不定的童鞋可以留下email,我发给你, 仅限于2.2。


cd android-api
git checkout android-2.2-r1.3 #这一步是切换到某个版本的代码分支,这里使用2.2
jar cvf ../android-src.jar -C core/java .
jar uvf ../android-src.jar -C graphics/java .
jar uvf ../android-src.jar -C location/java .
jar uvf ../android-src.jar -C media/java .
jar uvf ../android-src.jar -C opengl/java .
jar uvf ../android-src.jar -C sax/java .
jar uvf ../android-src.jar -C services/java .
jar uvf ../android-src.jar -C telephony/java .
jar uvf ../android-src.jar -C wifi/java .

这样变产生了android-src.jar文件, 把他加入到Android Library里,或者在出现"Attach source"按钮是指定这个文件,变可以基于源代码调试了.