假如《宫》被改编成RPG…

 这周休息,看完了最后十集的《宫》。突然想到,如果本剧能改编为3D RPG for pc就更好了。

Comments

样条插值的一般方法(上)

  没有接触过计算机曲线、面生成技术的人可能会想到,如果我们给定一个点集序列,再根据该集合生成一条经过每个点的曲线,同时曲线的形态还可以依据点的相互位置而定。

 然而当我们初步接触了Bezier curve,敬佩之余还带有稍许失望。不过在这之前我们必须承认,“控制点”生成曲线的方法早已是老祖宗的专利,后来Citroen的de Casteljau和Renault的Bezier先后终于完成了样条曲线的数学定义。Bezier曲线的成功得益于其三个出色的特性:控制点简单、光滑度较好且可控以及允许Bezier反算。下面是直接根据三次Bezier公式生成带有四个控制点的Bezier曲线的过程。

 应当注意的是,工业标准的Bezier曲线生成往往采用基于de Casteljau算法的递归细分策略,其目的是为了确保进行计算机数值计算的稳定性,进一步提高曲线的精度。 现在我们希望解决文章开始的疑问,其实质是利用Bezier曲线进行插值,以构建能够通过“所有”控制点(实际上Bezier曲线往往通过首尾两个控制点)的曲线。

 通过对Bezier的学习我们知道,Bezier曲线必然通过首尾控制点的特性其实完全可以被用于插值算法。我们把有序点序列相邻两点作为首尾控制点,据此生成分段Bezier曲线,即可满足要求。这一过程需要解决两个问题:

 1、若采用分段三次Bezier曲线,如何确定除首尾控制点的另外两点;

 2、连接若干分段三次Bezier曲线的平滑性如何得以保证;

 早在1974年,Edwin Catmull和Raphael Rom发表《A class of local interpolating splines》一文,就解决了上述问题,而且至今仍是最重要的曲线插值方法。

 值得一提的是,Edwin Catmull是计算机图形学领域一名做出过许多突出贡献的科学家(如纹理映射、双三次Bezier曲面、反走样算法、曲面细分的优化算法,还独立发明了Z-Buffer技术),而且还是现代影视动画工业的奠基人之一。1979年,Catmull离开了纽约理工学院计算机图形学实验室,加盟Lucas的工业光魔并领导其计算机动画部门。1986年该部门被Steve Jobs收购,Catmull也成为新公司Pixar的CTO。2006年Disney收购Pixar,Catmull成为现任Disney Animation Studios&Pixar Animation Studios总裁。

 假设有m+1个插值点p0,…pm,现在要才用分段三次Bezier曲线,则Catmull-Rom样条曲线包含m-2条Bezier曲线,其中第i条Bezier曲线起始于pi终止于pi+1。设:

 li=½(pi+1 - pi-1)

 且

 pi+ = pi + 1/3li以及pi- = pi - 1/3li

 然后设qi(u)是pipi+pi+1-pi+1为控制点的Bezier曲线—曲线的定义域被变成了i<=u<=i+1。将这些Bezier曲线拼接在一起,就构成了完整的Catmull-Rom样条曲线q(u),使得对于任何i<=u<=i+1都有q(u)=qi(u)。

 其示例如图:

 Catmull-Rom存在一定的不足,当某相邻点间距明显小于其它点的平均相邻距离时,生成的曲线会发生“漂离现象”,也就是导致G1不连续。实际上Catmull-Rom的问题主要在于额外的控制点位置异常,采用被称作Bessel-Overhauser的样条函数即可解决这一问题,这就是不同于均匀参数化的弦长参数化方法,此外还有一种节点值参数化方法,即向心参数化方法。有兴趣的读者可以查阅其它相关文献。

 本文的参考资料来源于Samuel R.Buss的《3D computer graphics—a mathmatical introduction with OpenGL》相关章节,以及两篇分别来自T.Y.Kim和Christopher Twigg的论文。下次我们将讨论构造曲面的一般方法(当然具体日期要根据下周的空余时间而定了)。

Comments

Flowingdata:2010年的10个最佳数据可视化工程

 本周是开学第一周,事务繁多,故无暇进行相关专题讨论了。这里仅转载一篇来自flowingdata的有趣文章,值得一提的是,数据可视化、可视分析等都是最近几年才逐渐兴起的新兴科学,尽管下面这篇文章仅仅能代表原作者的个人观点,但我们似乎能从中一窥可视化技术在未来的科学和经济价值。

 10 Best Data Visualization Projects of the Year – 2010

 同时,这里给出译言网相应译文地址:

 http://article.yeeyan.org/view/191841/163084

 最后,在这里贴一张同样是来自flowingdata的图片(原作者是Moritz Resl)。

 

 对于这张过于“简单”的状态图,Moritz在swiss-miss上也给出了自己的解释:

 Let’s not forget though that sometimes doing stuff you like leads to sad, and more importantly, doing stuff you don’t like can lead to happy.

 我想,到目前为止这句话至少有半句是对的,因为你必须了解:

 What’s something you really like,more.

Comments

Qt与现有系统字符集的兼容问题研究

本文是假期完成的最后一篇文章,之后我将回到学校,届时更新频率将恢复为每周0-2篇左右。

众所周知,Qt在国际化方面的实现是非常方便的。但有时我们会面临一些问题,如在Windows系统中GB2312/GBK和unicode字符集的不兼容,以及在与现有网络程序实现通信的过程中发生的字符集不兼容问题。当然,此类问题可能比较罕见,而且事实上不只Qt面临这一棘手的情况。经过查阅一些资料并进行实践开发,我们相信Qt提供了目前最为便捷的字符集兼容解决方案。我们的最终应用是实现与Unix/Windows主机上的现有服务端程序进行通信,以实现如http、ftp等低级别应用层协议。

首先介绍GB2312-80、BIG-5、Unicode、GBK以及GB18030。

====================以下内容来自wikipedia====================

GB2312-80是中国国家标准简体中文字符集,全称《信息交换用汉字编码字符集-基本集》,又称GB0,由中国国家标准总局发布,1981年5月1日实施。GB2312中对所收汉字进行了“分区”处理,每区含有94个汉字/符号。这种表示方式也称为区位码。其中:01-09区为特殊符号;16-55区为一级汉字,按拼音排序;56-87区为二级汉字,按部首/笔画排序;10-15区及88-94区则未有编码。

在使用GB2312的程序通常采用EUC储存方法,以便兼容于ASCII。浏览器编码表上的“GB2312”,通常都是指“EUC-CN”表示法。每个汉字及符号以两个字节来表示。第一个字节称为“高位字节”,第二个字节称为“低位字节”。“高位字节”使用了0xA1-0xF7(把01-87区的区号加上0xA0),“低位字节”使用了0xA1-0xFE(把01-94加上0xA0)。由于一级汉字从16区起始,汉字区的“高位字节”的范围是0xB0-0xF7,“低位字节”的范围是0xA1-0xFE,占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。

Big5,又称为大五码或五大码,是使用繁体中文社区中最常用的电子计算机汉字字符集标准,共收录13,060个汉字。Big5码是一套双字节字符集,使用了双八码存储方法,以两个字节来安放一个字。第一个字节称为“高位字节”,第二个字节称为“低位字节”。“高位字节”使用了0x81-0xFE,“低位字节”使用了0x40-0x7E,及0xA1-0xFE。

Unicode是为了解决传统的字符编码方式的局限而产生的,例如ISO 8859所定义的字符虽然在不同的国家中广泛地使用,可是在不同国家间却经常出现不兼容的情况。很多传统的编码方式都具有一个共同的问题,即其容许电脑进行双语环境式的处理(通常使用拉丁字母以及其本地语言),但却无法同时支持多语言环境式的处理(指可同时处理混合多种语言的情况)。

大概来说,Unicode编码系统可分为编码方式和实现方式两个层次。

1、编码方式

Unicode的编码方式与ISO 10646的通用字符集(Universal Character Set,UCS)概念相对应,目前实际应用的Unicode版本对应于UCS-2,使用16位的编码空间。也就是每个字符占用2个字节。这样理论上一共最多可以表示216即65536个字符。基本满足各种语言的使用。实际上当前版本的Unicode尚未填充满这16位编码,保留了大量空间作为特殊使用或将来扩展。上述16位Unicode字符构成基本多文种平面(Basic Multilingual Plane,简称BMP)。最新(但未实际广泛使用)的Unicode版本定义了16个辅助平面,两者合起来至少需要占据21位的编码空间,比3字节略少。但事实上辅助平面字符仍然占用4字节编码空间,与UCS-4保持一致。未来版本会扩充到ISO 10646-1实现级别3,即涵盖UCS-4的所有字符。UCS-4是一个更大的尚未填充完全的31位字符集,加上恒为0的首位,共需占据32位,即4字节。理论上最多能表示231个字符,完全可以涵盖一切语言所用的符号。BMP字符的Unicode编码表示为U+hhhh,其中每个h 代表一个十六进制数位。与UCS-2编码完全相同。对应的4字节UCS-4编码后两个字节一致,前两个字节的所有位均为0。

2、实现方式

Unicode的实现方式不同于编码方式。一个字符的Unicode编码是确定的。但是在实际传输过程中,由于不同系统平台的设计不一定一致,以及出于节省空间的目的,对Unicode编码的实现方式有所不同。Unicode的实现方式称为Unicode转换格式(Unicode Translation Format,简称为UTF)。

例如,如果一个仅包含基本7位ASCII字符的Unicode文件,如果每个字符都使用2字节的原Unicode编码传输,其第一字节的8位始终为0。这就造成了比较大的浪费。对于这种情况,可以使用UTF-8编码,这是一种变长编码,它将基本7位ASCII字符仍用7位编码表示,占用一个字节(首位补0)。而遇到与其他Unicode字符混合的情况,将按一定算法转换,每个字符使用1-3个字节编码,并利用首位为0或1进行识别。这样对以7位ASCII字符为主的西文文档就大大节省了编码长度(具体方案参见UTF-8)。类似的,对未来会出现的需要4个字节的辅助平面字符和其他UCS-4扩充字符,2字节编码的UTF-16也需要通过一定的算法进行转换。再如,如果直接使用与Unicode编码一致(仅限于BMP字符)的UTF-16编码,由于每个字符占用了两个字节,在Macintosh (Mac)机和PC机上,对字节顺序的理解是不一致的。这时同一字节流可能会被解释为不同内容,如某字符为十六进制编码4E59,按两个字节拆分为4E和59,在Mac上读取时是从低字节开始,那么在Mac OS会认为此4E59编码为594E,找到的字符为“奎”,而在Windows上从高字节开始读取,则编码为U+4E59的字符为“乙”。就是说在Windows下以UTF-16编码保存一个字符“乙”,在Mac OS里打开会显示成“奎”。此类情况说明UTF-16的编码顺序若不加以人为定义就可能发生混淆,于是在UTF-16编码实现方式中使用了大端序(Big-Endian, 简写为UTF-16 BE)、小端序(Little-Endian,简写为UTF-16 LE)的概念,以及可附加的字节顺序记号解决方案,目前在PC机上的Windows系统和Linux系统对于UTF-16编码默认使用UTF-16 LE。

此外Unicode的实现方式还包括UTF-7、Punycode、CESU-8、SCSU、UTF-32等,这些实现方式有些仅在一定的国家和地区使用,有些则属于未来的规划方式。目前通用的实现方式是UTF-16小尾序(LE)、UTF-16大尾序(BE)和UTF-8。在微软公司Windows XP操作系统附带的记事本(Notepad)中,“另存为”对话框可以选择的四种编码方式除去非Unicode编码的ANSI(对于英文系统即ASCII编码,中文系统则为GB2312或Big5编码) 外,其余三种为“Unicode”(对应UTF-16 LE)、“Unicode big endian”(对应UTF-16 BE)和“UTF-8”。

目前辅助平面的工作主要集中在第二和第三平面的中日韩统一表意文字中,因此包括GBK、GB18030、Big5等简体中文、繁体中文、日文、韩文以及越南喃字的各种编码与Unicode的协调性被重点关注。考虑到Unicode最终要涵盖所有的字符,从某种意义而言,这些编码方式也可视作Unicode的出现于其之前的既成事实的实现方式,如同ASCII及其扩展Latin-1一样,后两者的字符在16位Unicode编码空间中的编码第一字节各位全为0,第二字节编码与原编码完全一致。但上述东亚语言编码与Unicode编码的对应关系要复杂得多。

GBK即汉字内码扩展规范,K为汉语拼音 Kuo Zhan(扩展)中“扩”字的声母。英文全称Chinese Internal Code Specification。字符有一字节和双字节编码,00–7F范围内是一位,和ASCII保持一致,此范围内严格上说有96个文字和32个控制符号。之后的双字节中,前一字节是双字节的第一位。总体上说第一字节的范围是81–FE(也就是不含80和FF),第二字节的一部分领域在40–FE,其他领域在80–FE。

GB18030,全称:国家标准GB 18030-2005《信息技术中文编码字符集》,是中华人民共和国现时最新的内码字集,是GB 18030-2000《信息技术信息交换用汉字编码字符集 基本集的扩充》的修订版。与GB 2312-1980完全兼容,与GBK基本兼容,支持GB 13000及Unicode的全部统一汉字,共收录汉字70244个。

GB 18030主要有以下特点:与 UTF-8 相同,采用多字节编码,每个字可以由1个、2个或4个字节组成。编码空间庞大,最多可定义161万个字符。支持中国国内少数民族的文字,不需要动用造字区。汉字收录范围包含繁体汉字以及日韩汉字。

GB 18030的字节结构如下:单字节,其值从0到0x7F。双字节,第一个字节的值从0x81到0xFE,第二个字节的值从0x40到0xFE(不包括0x7F)。四字节,第一个字节的值从0x81到0xFE,第二个字节的值从0x30到0x39,第三个字节从0x81到0xFE,第四个字节从0x30到0x39。

====================以上内容来自wikipedia====================

事实上,上述wiki内容是没有必要细究的:),下面进入正题。

Qt中的内置字符串类为QString,它是以16位unicode编码(unicode 4.0/unicode-16)存储的。QString被应用于所有涉及字符串操作的API中,也就是说,如果你要用Qt构建应用程序,那么研究QString是不可避免的。

下面是一种比较自由的字符集转换方式:

[code] QByteArray encodedString = "mp77的技术交流频道"; //为什么要用QByteArray? QTextCodec *codec = QTextCodec::codecForName("gb2312"); QString string = codec->toUnicode(encodedString); [/code]

QTextCodec为我们提供了针对超过30种常用字符集间互相转换的机制,但这种简单实现代码量较大,不适合字符串操作较多的情况。那么下面这种方案则受到广大程序员的欢迎:

[code] QTextCodec::setCodecForTr(QTextCodec::codecForName("gb2312")); //beginning of code …… QString string = QObject::tr("mp77的技术交流频道"); [/code]

QTextCodec提供了一种类似国际化接口的操作,所有的字符集规定在代码行首部完成,之后只需要借助国际化的方法初始化任意字符串即可(尽管这与真正的国际化功能有所区别)。现在我们解释首段代码中为何使用QByteArray接收中文字符串,如果不做任何处理直接运行:

[code] QString string = "mp77的技术交流频道"; [/code]

由于系统采用ANSI编码(包括Multi-Byte Chactacter System,MBCS字符集),那么上述语句执行后,字符串string在内存中的内容实际上是以ANSI编码。由于对ansi的操作与unicode完全不兼容,那么此后QT中所有的字符串操作都会受到影响,最终输出时就会出现所谓的“乱码”。因此,类似的直接赋值形式应当尽量避免。

我们注意到在vc6时代经常采用以下赋值方式:

[code] const char* string = "mp77的技术交流频道"; [/code]

这一句包括了申请内存、写入内容并以“\0”结尾等操作,其在内存中的字符编码形态自然也是ANSI的。Qt特别提供的QByteArray类就是为了兼容这种情况,而且官方手册声称它比const char *的声明初始化方式要好很多(如采用implicit sharing,简单地说就是COW技术),而且使用上也方便许多。

这里介绍一个我们在实际应用中遇到的例子。题目是实现FTP协议,当然,要想实现一个稳定的FTP协议难度并不小,这主要是因为相关RFC文档并没有提供足够的协议细节,导致目前几乎没有绝对通用的FTP服务端或客户端。当然,目前仍有能够兼容大多数平台的客户端/服务端程序,且在日常使用中似乎没有发现什么问题。

Qt实现FTP客户端很容易——只要使用现成的QFtp即可,但关键的服务端需要手动完成了。我们在使用cuteFTP和FlashFXP这种常用客户端软件进行测试时立即发现了一个严重问题,即服务端返回的目录list中出现汉字乱码。我们检查了服务端生成目录list的函数,并未对任何字符串进行编码操作。于是直接在服务端socket的数据信息中添加了toUtf8的操作。事实表明这一修改没有解决任何问题。

继续检查后我们注意到类似如下一行关键代码:

[code]

QString string;

string = "…";

string += local.toString(fileinfo.lastModified()," MMM dd yyyy ") + filename+"\r\n";

[/code]

上面实际上利用了QString对+/+=的重载进行字符串的简单构建,其中filename是出现乱码的地方——也就是唯一存在中文可能的文件或目录名称。由于字符串常量的存在,我们对string进行直接赋值实际上就导致内存信息为ansi编码,而filename来自于fileinfo.completeBaseName(),是Qt有关目录操作函数返回的文件名信息,其编码自然是utf-16。查阅QString对+/+=的重载说明知,Qt为了提升字符串操作的性能,只是在目标字符串的尾部申请了一块额外的内存空间,并直接将源字符串所在的内存块复制到新空间中。由此可见,string中实际上是ansi和utf-16两种编码的字符串混合,无论我们今后采用何种编码转换方式,都无法实现完整内容的正确转换。

一种解决方案是:

[code]

QString string;

string = "…";

string += local.toString(fileinfo.lastModified()," MMM dd yyyy ") + filename.toLocal8Bit()+"\r\n";

[/code]

toLocal8Bit函数返回的是QByteArray类型的本地字符集串,如此就能保证string保持唯一的字符集了。

近期的文章中我们将介绍如何使用Qt构建网络应用程序,并提供一个代码示例。

Comments

Qt的命运

Nokia的自救终于有了实质性的举动,那就是放弃Meego、过渡Symbian、抵制Android、拥抱WP。相应的,主要用于S60和Meego的Qt将会面临更加严峻的形势。

当然,在经过2011-2012年的Microkia过渡期之后,Qt未必就和移动设备彻底无缘。然而事实是Qt似乎又一次丧失了进军主流消费市场的机会,并被打回到开发者社区的襁褓之中。人们完全可以理解Nokia的举动——这几乎关系到其自身的生死存亡,但这一次Nokia像是有些孤注一掷了:毕竟Microsoft在本次合作中所承受的风险要比合作伙伴低很多,而潜在受益则又高很多。不过,WP本身就是killer OS,只不过受制于载体而令销量裹足不前,既然Moto能携Android焕发第二春,Nokia又何尝没有机会东山再起呢。但试想一下,即使Nokia真的凭借WP上演王者归来,那么到那时“王者”的定义恐怕就完全与当初不可同日而语了。

话说回来,Qt自身的魅力本不在寄宿于S60或是一直处在传说中的Meego,而在其新颖的核心机制,华丽的UI资源,丰富的功能模块和强大的跨平台特性。预测今后的移动消费市场,如果不出意外最晚在2013年起(到时候可能WP8早就继位了),天下三分的局面就将形成。届时大部分求变的动力将主要来自三家内部,而Qt有绝佳的机会成为联系三大体系的唯一技术解决方案(当然目前这只是一厢情愿的YY…)。

对我们自己而言,大多数爱好者毕竟不是真的靠Qt吃饭,少量利益相关的开发者也并未只从事移动领域的开发工作。作为一名工匠,人们往往乐于使用自己喜欢的工具谋生,但现实经常是,大部分人正在从事的并非是自己所认为的最佳选择。Qt在过去和现在所扮演的角色,今后很长一段时间恐怕还要继续下去。

出于对Qt的欣赏和喜爱,本博将在今后继续坚持Qt专题的写作。但愿Nokia的决定不至于严重影响现有的Qt开发者团队。

qt
Comments

2010年终总结暨hanyi.name重建三年纪念暨……

本博并非是什么牛博。

从2010年5月初百度统计上线ip数据至2010年12月31日,有效访问ip也仅2003个,且相信其中相当一部分流量来源于本人。此外,去年明显对此博怠慢许多,全年文章数竟还不到40篇,其中纯粹的技术类更是寥寥……究其原因,恐怕是心有余而力不足,本文从抬笔到发布也整整磨蹭了一周时间。

我自小就懒,主要是懒得动,中学以前就退而求其次喜爱上画画,然而画作没有丝毫技术含量,也基本没人能看得懂。不想后来导致钢笔字惨不忍睹,人称“狗爬体”——于是小学师傅劝家里送我去学书法。谁知这玩意技术含量颇高,课堂作品往往又被人称作“骨头体”——人看了不适狗看了兴奋,就无奈放弃了。然而这次小经历让我认识了颜公真卿和他的颜勤礼碑,以及笔墨宣纸等物,好不风雅!后来一次随家人出游,沿着溪边摸到一碗鹅卵石,寻思着揣回去做砚台用(后来想想可能还真不如墨盒实用),用旧报纸包了回家藏好,可惜很快还是被主人家当做垃圾清理了。

大概十年前,我的初中语文老师教我养成了写文章的嗜好,每周一至两篇,题目体裁不限,大概每节课前要众同学轮流上去宣读自己的文章。然而真正自己写文章的并不多,坚持每次都自己写的就更少,我向来不喜去抄别人的文章:名作太长且不易蒙混过关,其余作者大家水平都是一般,何必互相抄来抄去呢——于是就慢慢习惯了。 记得当时我在那小册子上也是无所不写,下至童话短篇,上至新闻政治,无所不包。后来因此事必躬亲遭人讥讽,遂题名“孤芳自赏集”聊以自慰。有幸在台上宣读了两篇,直捣得众人时而笑得前仰后合,连绵不绝,整整占去了半节课的光景,教师也毫不在意。不幸的是这两本小册子在上次搬家时不知所踪,四年前突闻启蒙师长英年早逝,实在令人惋惜, 然而写文章的习惯就自此保留至今了。

惭愧的是,自2007年底至今的三年多时间里,本博共发布的文章尚不足三百篇,且不少还是所谓的“纯技术类”。这与我2008年决定真正从事计算机,并决定读研是有关系的:试想我与“高档”计算机“共事”也有十二、三年,接触带个芯片就能做字处理的机器就更久了,然而竟从来不能真正令其思己所想,做己所作,纵然“人机”相识也已近七十年,在各个领域离各路专家宣扬的“和谐共生”也还差得极远。换句话说,这领域尚有如此多的文章可做,何愁今后没有文章可写呢?

如果在此概括的话,2010年确是荒废之年。那么2010年荒废在何处呢?

首先是年初面临研究生入学考试,这一折腾至少要到5月份才逐渐平息,实在是没有必要且浪费时间(当然也有到二月底就长痛不如短痛的猛士了)。其间夹杂着做了毕设,找老师选了题目,先是坦白自己基本零基础,编程大概只会部分html这种伪语言,其余只能承认课堂上貌似有介绍过了。老师倒也不介意,邮件给发个网址kitware,自己回去琢磨去吧。我倒是对这老师万分感激,起码最后至少也给评了“优”。然而后来发现,教师行业如今也是背景为上,资历次之,学识为轻——这绝非偶然现象,只是如果现世皆如此,众生倒也见怪不怪了。

毕设时对vtk/itk/gdcm/CT/MRI感兴趣,于是开了vtk的话题,并入可视化部分,但是没好好写过几篇。5月份报了驾校,教练倒是君子,只是不时骂的狗血喷头,无奈此时已晚报了一个多月,入夏以后再就没去过,如今校长三天两头催着考科二科三,只好待开春以后再说了。

毕设结束就意味着毕业,兄弟各自谋生的谋生、奔前程的奔前程、泡妞的泡妞,我在家休息了半天就重新拉回学校干活,热翻整个七月。七月份唯一有意思的是和阿仝在东哥宿舍留宿了几周,话说近年来我已少有在夏天出门了。不过东哥找工作的压力还不小,我只好逼着他把天龙八部删了又删,只留下一个自己突然颇感兴趣的连连看,可恶越往后打越难,可在整个七月份那就是唯一的乐趣了。

八月份带着半残疾回家休整,恰逢又一款中文RPG发售,和年初的云之遥呈现交相辉映之势。赶紧把游戏通了关,又听闻wlk要推出。wow这个东西简直让人又爱又恨,从2003年听说到崇拜,2004年随公会打进wowar、nga,建模拟器抢先体验,经历2005年初的万人号,2006年的折磨到疯狂,2007年的放弃到回归,2008年的再放弃到再回归,2009年的彻底决裂,直到2010年的八月又被暴雪这帮奸商给拉了回去。不过我似乎已经不属于这个游戏所处的时空维度了,wow的元素在我看来已成为了精致的计算机图形学工程产品,其中蕴含的才是我应当追求的。  12月是失去的月份,本应当去体验一下久违一年的自习之趣,无奈俗务缠身,差点考试都没法应付,然而又让我彻底与wow隔绝了。

这就是我的一篇针对2010年的粗粒度总结。值得一提的是,今年(2011)2月5日,本博将迎来三周年,记得一周年(2009)时我略数了下大概有文章百篇,到了今年竟只有250、260篇左右,文章数显得略少。后来想想,本博的观者每天也不到十人,而且跳出率有十分之九那么高,著书立说实在谈不上,倒不如写写杂记,技术上的东西有了足够积累才能有所领悟,倒也不愿强求指标了。

2010唯一郁闷的就是,某官方名为扫黄打非实际醉翁之意不在酒,先是恐吓着要封了全国的个人网站,后来又威胁要夺我的cn域名,我这域名没什么普世寓意本值不了多少钱,结果硬是被他们挥刀自宫,毁掉了我们在高速发展的互联网上弘扬自己悠久历史文化的契机和未来,而这点仅存的果实,如今竟也变成了紧俏货。

Comments

从SIGGRAPH看《Tangled》

2010年11月24日,Disney的第五十部动画长片《tangled》(中译:魔发奇缘)在北美公映。尽管影片剧情与格林童话原作《Rapunzel》相差了十万八千里,但是观众口碑颇佳,本作被公认为Disney近年来少有的佳作,超过了《Tinker bell》系列和09年的《The Princess and the Frog》。值得关注的是,本片由于未能通过中国大陆有关部门的审查而无法在内地公映。而从近年的动画大片票房趋势来看,Disney的童话系列往往叫好不叫座;Dreamworks的《shrek》系列已经显现疲软,今明两年的《Kung Fu Panda 2》和《Madagascar 3》将担负SKG的重任;与前两者相比,Blue sky的《ice age》显得势单力薄一些。而目前动画片既叫好又叫座的盟主恐怕非pixar莫属了——这恰恰印证了创意与技术的完美结合——才是当代动画产业的关键路径。

本文是在SIGGRAPH2010年会发布的一篇讨论文章《Simulating Rapunzel’s Hair in Disney’s Tangled》的基础上完成的,在此感谢原作者Kelly Ward、 Maryann Simmons、Andy Milne、Hidetaka Yosumi和Xinmin Zhao。针对与此相关的一篇正式论文研究将提交至本站新推出的mp77’s paper review子站中。鉴于acm和ieee等组织的版权和一些其它因素,今后涉及有关已正式发表的论文的研究文章将提交至上述受限站点,同时我们也欢迎与有类似专业兴趣的同学展开交流,我目前的研究方向是计算机三维人物头发的模拟技术。2010年SIGGRAPH年会是于2010年7月25日-29日在美国加州洛杉矶举办的。

众所周知,头发模拟是动画制作中难以解决的问题。在《Tangled》中我们(这里的“我们”是指walt disney animation studio的相关工作人员)更是遇到了一个“极限任务”——模拟影片女主角Rapunzel长达70英尺的头发。除了头发精密且蓬松的结构和特点,如此长度的头发还对相关的模拟技术提出了许多特殊的挑战。此外,影片特定的艺术指导也进一步增加了模拟工作的复杂程度。

我们使用了自主研发的基于弹簧质点系统生成动态曲线的头发模拟软件dynamicWires来模拟Rapunzel的头发。 在应对Rapunzel独特头发的过程中,我们对dynamicWires进行了一些改进。

头发堆叠和形态保持

影片中Rapunzel的头发经常堆叠在场景中的地面或其它物体和角色上。在模拟过程中,把弹力应用于当头发处于飞行过程中的碰撞部分,以维持相应的形态,并起到头发股之间相互作用和分离时所产生的摩擦力效果。这种弹力只有在曲线段之间的运动距离超过了一定阈值,并引发直接接触和分离时才会生效,该阈值是基于足以令头发股间发生滑动和粘连程度值而界定的。考虑到实时性,我们通过首先生成较为稀疏的引导曲线集来降低模拟海量长发的复杂度,该集合的容量在200条左右。这种低密度的曲线集覆盖在人物的头部最显著区域,使得外层显著区域的头发能够轻易落入头发体内部底层的空隙中。为了解决这一问题,我们引入了额外的碰撞支持机制以填充头发体内部的空隙:首先连接相邻曲线的控制点,并使这些线段与现有系统发生一般碰撞关系,已生成的模拟曲线再和上述机制发生碰撞关系即可。

轻松拖拽

在现实中,Rapunze恐怕需要比较费力地拖拽她后面的长发。影片的艺术指导要求Rapunze能够熟练地拖动这些长发,且当女主角移动时头发需要平稳地在人物身上滑动,并避免人物动作因负重而显得僵硬,在人物停止运动时还需要一定的喘息。

为了控制头发拉动的程度,我们增加了一个切向摩擦参数,以模拟发生地面接触时沿头发股各个切线方向的摩擦力分量。这种切向摩擦分量随后会被比之少两个数量级的其余摩擦力削减一部分。头发就能够根据其长度进行平稳滑动,而非当人物停止运动时,拖动在地面的头发就会立即停止滑动。

模拟冻结

考虑到头发的可见长度和动作以及最小长度需要在每个镜头发生变化,我们采用了模拟冻结机制以降低对头发背面的模拟程度,这种机制允许我们在每一幅画面调整头发模拟的长度,并且显著提升头发模拟的速度。

在某些场景中长发的背面并不可见,然而人物却仍然非常活跃的情况下,将那些不可见且不进行模拟的部分头发与其余头发分离,令其不再成为有效的部分。当这种分离令头发的浓度过于稀疏时,为了保证长发具有一定的浓度错觉,需要强制停止模拟的部分缓慢恢复状态。

有时当大量可见头发拖在地面上且没有任何动作时,头发的这些无效的部分仍然与有效部分发生视觉联系,我们通过保持相关的模拟冻结区域并使用弹力,使模拟部分和非模拟部分能够平滑地混合在一起。那么头发模拟的计算资源就可以被高效地用于高度活跃的头发区域——而不是在不运动的头发模拟上浪费时间。

头发的内部约束机制

头发的内部约束机制能够使其在特殊情形下仍可以自然地运动。我们在相邻的曲线间加入了较小的弹力,以精确控制头发使其保持相对静止的状态,避免其轻易四散开来:例如散落在人物的肩部、面部和身体部分。根据一个特定的距离分离参数,这些约束机制能够在超过一定距离时自动减弱它们的强度,并在超越另一距离值时令其完全分离。这就保证头发通常能处于聚集状态而非迫使其发生单股头发的运动,并且能够根据人物整体动作的程度自然而然地允许部分头发分离成不同的部分。

结语

上述的模拟特性帮助我们实现了对Rapunzel超乎寻常长发的模拟。模拟冻结和碰撞支持机制允许我们只需要在每个镜头中模拟人物的一部分头发,减少大量头发模拟的复杂性负担。轻松拖拽和头发的内部约束机制使我们能够严格根据影片艺术指导的要求控制头发的自然运动。

应当注意,本文仅仅是针对《Tangled》中的关键需求所提出的技术解决方案的粗略讨论,而非真正提供详细的实现。我幸运地在makingof上找到了针对本文原作者之一Kelly Ward女士的视频讲解,由于我们缺乏SIGGRAPH现场视频资料,相信这部长约14分钟的视频能给我们带来更深层次的启发。

Comments

向前线进发:WebGL初试

非常幸运的是,我们生活在一个正处于高速变革中的时代里。新的技术、理念乃至行业标准即将定稿,虽然我们无从参与任何权威文件的最终发布,却能全程体验这一史无前例的飞速发展的全貌。

从1996年VRML1.0发布时起,Web3D就追赶上了互联网高速发展的黄金时期。然而端上的资源匮乏严重制约了VRML前进的脚步,这期间又经历了针对Java Applet的普遍质疑。如今,除了Princeton 3D Model Search Engine闻名于学术界以外,似乎就很难再找到如此振奋人心的killer platform了。 2004年,w3c开始着手筹备html5。一系列高级功能,如表单控制、应用程序接口(APIs)、多媒体、结构化和语义化等计划被引入新的标准。由于这些全新概念的引入(实际上在pc领域这些早已算不上是“全新”了),Web3D的支持者们终于看到了新的突破点:直接在浏览器中引入3D API,再通过一系列底层优化,甚至采用硬件加速来提升效率和稳定性。这次Khronos Group终于可以携自己的OpenGL ES 2.0大展身手了。本文的目的旨在向读者介绍WebGL当前的标准制定和研发进度,并提供一些关于平台demo的建议。本文剩余的内容是基于learningwebgl.com整合而成的,在此对相关作者表示感谢。

首先要说明的是,要想率先体验WebGL所带来全新的视觉冲击力,你至少需要安装一款支持它的浏览器。幸运的是,目前除了微软的IE系列,几乎所有主流浏览器的开发版本都支持WebGL。那么我们如今的问题就变成了:如何为你现有的系统配置一款WebGL支持良好的浏览器。

对于windows操作系统而言,如果你拥有一块性能不差的ATI或Nvidia显卡,那么试着安装Firefox或是Chromium,它们也是目前win系统上最好的浏览器。如果你的机器只配置了一套来自Intel的集成图形芯片组(目前普通笔记本电脑普遍集成了这种配置),那么情况可能变得有些糟:这是因为Intel的图形硬件驱动并不能很好地支持OpenGL,而事实上目前的WebGL主要是基于OpenGL的(尽管这种情况在今后将会有所改善)。在这种情况下即使你安装了Firefox或Chromium,浏览器可能还是不会正常地运行WebGL程序——当然对此有更好的解决办法,我们可以使用带软件渲染的Firefox浏览器(这种软件渲染方式即把针对3D图形的运算全部交由CPU执行而非显卡,这将大大降低WebGL的运行效率……但至少我们很大程度上解决了这一问题)。

在Macintosh系统中,如果你采用了Snow Leopard操作系统(版本号OS X 10.6),那么我建议你使用WebKit的开发版本,它将是Safari的替代版本。如果你使用的是Leopard (版本号OS X 10.5),你可能无法运行WebKit开发版,那么Firefox或Chromium就是你最好的选择。当然,Snow Leopard的用户也可以采用上述两款浏览器。遗憾的是,我目前尚无法确定WebKit在更旧版本的Mac操作系统上的运行情况。

如果你正在使用Linux,那么解决方案可能和windows差不多。但需要注意,如果你的集成显卡不能很好地支持WebGL,那么在采用软件渲染之前,你需要安装Mesa,然后再安装最新版本的Firefox即可。

由于笔者的配置环境是ATI HD5650/Windows 7 ultimate,故我们以chromium浏览器的安装为例介绍这一流程。

目前chrome的开发者强烈建议用户使用Chromium的nightly build版本,它可以看成是chrome的一种实验版本,由于nightly build版本的存在使得其发展速度要全面领先于chrome,后者的缺点主要是功能较前者而言欠缺一些,但运行更加稳定。chromium的安装因操作系统的差异有所区别,这里我们仅给出windows操作系统的chromium安装流程。

1、首先下载chrome-win32.zip并解压之;

2、运行chrome.exe;

3、开始在google上搜索WebGL纷繁复杂的demo欣赏吧!

值得一提的是,本站的首页采用了WebGL的展示技术,如果你的浏览器不支持WebGL,今后可能就无法正常浏览这里的全部信息了。

Comments

天启还是自决

 我之前从未接触过导演Stanley Kubrick的作品,虽然至少也听闻过《lolita》、《发条橙》、《2001》这些,但也仅限于少量的影评而已。过去喜欢看科幻片,以为这些只是异人们想象力四溢的结果,后来发现科幻片大师普遍更加看好影片所蕴含的metaphor,动机大概都不是太纯的——然而这才是真正的大师之路。

 《2001:a space odyssey》是一部让人非常熟悉但又陌生的影片,熟悉大概是以前找科幻片看时总会见到它的介绍,但看看出品时间——1968——比Neil Armstrong‎登月还早个将近一年,于是只好放弃。前几天在emule上找《发条橙》,又见到了该片,可惜源比较少,网络居然有个在线的但很不清楚,玷污了名作,等等倒也值得。但在看影片的过程中发现这厮根本不是什么科幻,开始就是黑屏加诡异音乐,以为又浪费一个2g的假源——快进几分钟后来发现确实是有画面——几只明显是人扮的假黑猩猩讲进化,就是人类降临。后来讲一堆科学家去到月亮上去挖石头,照集体相留个念一个个还被突然的鬼叫吓得半死。第三部分是后续——木星任务,牛逼电脑差点造反成功,最后令人心酸地“死去”。最后生还的科学家抵达目的地,却被石头引入各种幻觉、诡异、以及较现代片子更细粒度的生殖场景,也有一说是玩起了穿越——因为更老的科学家本人接连出现,吃饭、饮水、睡觉、等死——终于最后时刻到来,一切仿佛又回到了原点。

 当年影片的票房不错,估计还是因为画面和科技元素带给人巨大的震撼力——想想四十年前的“我们”。然而影片的科技情节都呈现的颇具艺术性,包括画面和配乐,这些手法在后来的《star wars》、《eva》,以及前段时间有趣的《moon》都令人感到似曾相识,“开山鼻祖”一说看来真的不假。但是剧情方面让人看着有点摸不到头脑,各种各样metaphor的充斥考验着观众,也成就了导演本人。尽管影片公映至今已超过四十年,但却没有一个人敢声称自己了解了导演真正的意图。我认为,《2001》之所以聚集了现代社会的根本基奠——宗教、科学和艺术,把这些内容按是否取决于人自身的意志的标准进行分类,我们可以看到人的命运既有天启的成分,也有人类自决的成分。人类面对天启是毫无招架之力的、甚至连亵渎与蔑视都不要想。对于人类可以自决的部分,往往在为人类服务的同时又引入新的问题,那么这种双刃剑到底有没有解决起码部分问题呢?

 答案似乎是肯定的,毕竟人类凭借智慧统治着这个星球。《2001》中的黑猩猩起初是和野猪?一样只吃草的,只是意外掌握了大杀器才能真正开回荤,野猪毕竟是野猪,依旧在黑猩猩周围平静地吃草——尽管自己的同类正被当作猩猩们的午餐。于是差距不断扩大,直到当年未开化的恶邻变成如今的主宰。然而主宰的行为如今可能危及整个生态系统,甚至引起这些行为所导致的后果反噬主体自身。这就令人期待如何能把握天启和自决间的平衡:之所以是把握而非控制,是因为天启对人而言似乎是不可随便预知的,那么我们对天平另一端的控制也似乎缺少了点自信。

 因此要谨慎地观察、并把握时机,人们往往崇尚“凤凰涅盘”和“浴火重生”,然而如果火候没把握住,最后甚至连渣都不剩了,“不死鸟”恐怕未免复活的也尴尬。

Comments

 上月底就草写的两篇Qt文章始终无法发布……最近甚至忙得连考试都顾不上了,赶紧收工放假吧。

Comments