搞清楚“为什么”
前几天写了篇关于整数和浮点互相转换的blog，那个数字的确奇妙。我当时想，原理也不应该复杂，就没去管它。
今天程序里突然发现一个 bug，就是由这个技巧引起的。有的地方对，有的地方不对。转出来成了0。
百思不得其解，只好老老实实研究这个技巧是如何工作的。然后才明白是浮点精度控制问题。我们的项目使用 d3d 的 client 在 d3d 设备初始化后，由于 d3d 修改了double 运算的精度。
要想放心的用任何一个技巧，know why 永远是前提啊。
« January 2006 | Main | March 2006 »
前几天写了篇关于整数和浮点互相转换的blog，那个数字的确奇妙。我当时想，原理也不应该复杂，就没去管它。
今天程序里突然发现一个 bug，就是由这个技巧引起的。有的地方对，有的地方不对。转出来成了0。
百思不得其解，只好老老实实研究这个技巧是如何工作的。然后才明白是浮点精度控制问题。我们的项目使用 d3d 的 client 在 d3d 设备初始化后，由于 d3d 修改了double 运算的精度。
要想放心的用任何一个技巧，know why 永远是前提啊。
本来挺清净的写字楼，自从楼上装修开始敲敲打打后，我就没得到过宁静。跟物业投诉过一次，然后打电话过来说已经打过招呼了。没想到最近几天，一过晚上六点，头顶上的横梁就开始剧烈的震动起来，振耳欲聋，似乎连灰都飘落下来，恐怖得很。办公室里通讯基本靠吼，然后我们就欲发的觉得 popo 的重要性起来。已经有好些同事终于忍受不住，在八点之前回家了。我试了一次，早早的回家看看电视也不错。
这两天周末，楼上的更加变本加利，恃无忌惮。似乎每天都要进行到晚上十点。我试图从敲打声中找到一些节奏，这样就可以阿Q似的当打击乐听。当然在隔壁休息室内玩一下 PS2 ，把音箱开到最大也算是一种抗议。
天啊，最宝贵的傍晚和周末两个编程时间段就这样被无比的噪音劫持了。现在回想前两个月在会议室装抱石墙的那几天，隔壁的那家也怪可怜的。难道真是一报还一报，可我们失去人性的在墙上打洞的日子只有两天，怎么报应就这么久呢。
3d游戏中的室外场景通常用高度图来表示，用一个二维数组来描述对应平面坐标的高度信息。
如果每个高度信息用一个 byte 来表示，很多情况下不太够用。因为对于很大的场景， 256 级的高度是远远不够的。通常我们会选择用 word 或者 float 来表示。
相比较而言，float 最为合适。这样，我们不太需要考虑缩放因子这个问题。但是 float 需要 4 个字节，这导致数据量很大。这里云风给出一个有损压缩方案用于压缩这些信息。
我们认为高度图上的信息大多数情况下是平滑过度的，这是这个有损压缩方案的前提。下面以一个 256x256 的高度图为例：
1. 生成 8 张序列图，分别为 128x128, 64x64, 32x32, ... 1x1 。生成的算法直接用上一级的图片每相临四个点取平均值记录下来。即，最后一张 1 像素的图上只有一个 float 信息，且为整个高度图的平均高度，这个值我们称作第 0 级高度图。下面，我们把 2x2 的图称做第1级高度图，4x4 的图称作第3级高度图，... ，原图称作第 8 级高度图。
2. 保存第0级高度图，即平均高度信息(最后一张 1x1 的图)
3. 迭代处理 1~8级高度图。对于第 n 级的高度图运算如下：
将这张图上，每相临四个坐标都对应到第 n-1 级高度图上一个坐标。每个坐标上的高度信息都减去其对应坐标的高度信息。这样把整张高度图转换为对应低一级高度图的差值。
扫描转换后的高度图，找到最小值(min)和最大值(max)，记录下来。
将所有差值信息[min,max]映射成 [0,255] 的整数，并记录下来。这样，我们就用 size*size+8 个字节记录下来这级高度图(size 为当前级的高度图的大小)。
用运算结果(size*size个 byte) 算回绝对高度信息，为下一级的运算做准备。
最后，我们就得到了一组用17 个 float 和 2x2+4x4+8x8+...+256x256=87380 个 byte 的数据(87448字节)共，用于表示 256x256 的高度图。相比较之前需要用 256x256x4=262144 个字节记录，压缩比为 87448/262144=33%
关于有损压缩后的误差，我没有做数学上的严格计算，用一张我们编辑器实际产生的比较复杂的地形图测试，误差为万分之一点五左右。从这个实际效果来看，效果是非常的好的。
如果一开始高度图就只有 256 级，我们把 [0,255] 的高度信息转换成 [0,1] 的浮点数后，依然可以用这个算法压缩。只不过，输出数据保存为 [0,15] 的整数即可。这样，每个字节可以保存 2 个点，既而可以得到一些压缩率。我用一些黑白图片做了测试，误差是非常的小的（肉眼不可分辨差别）。
这个压缩方案带来的额外好处就是，我们可以根据需要得到低精度的高度图。
写 blog 不是写论文，就点到为止啦 :) 恕不提供插图，代码，和更为精确的文字描述。
---
补充：<a href="http://blog.codingnow.com/2008/09/height_map_border.html)">高度图压缩后的边界处理</a>
这一天等了很久，终于看到了这则消息：
Lua 5.1 (final) is now available at http://www.lua.org/ftp/lua-5.1.tar.gz
Thank you very much for your patience during this long release process. Special thanks to everyone that sent suggestions. They have helped make Lua still better.
Enjoy! We can now focus on 5.2 :-) --lhf
昨天在 gtalk 还在跟孟岩聊天，并介绍 lua 5.1 rc 的进展。当时我推断 final release 就在这几天，没想到来的这么快。
今天做了下 diff ， 发现相对 rc4 做的最后一次修改正是满足了我前天提的一个需求，关于编译模块的 debug 信息的，真是荣幸啊。而 rc3 到 rc4 也是偶参乎的，关于 16 进制数的支持。这两个都是在一天之内被加到正式版中去的，不仅感叹国外开源组织的效率。
顺便再赞一个 luaJIT ，光是 DynASM 这个子项目就是精巧非常了。没见识过的朋友可以看看 examples 。
昨天晚上聊天的主要话题就是 lua 这种开源社区的效率和严谨。我觉得 lua 最大的优势在于，它的 source code 如此的精巧，以至于每个人都可以去把它读一遍，这样，整个 lua 对你就再没有秘密。用起来也会比 python 之流更加得心应手。如果有人去写一本 lua 源码剖析，那么绝对是一本经典的 C 语言教程。我从阅读 lua 的源码学到了许多以前不曾知道的 C 语言标准库，以及一些用 C 语言构建大规模项目的技巧。
lua 项目的严谨从 5.0 到 5.1 一个小版本的升级就花掉三年时间可以看出(而这三年保持着不衰的活跃) 。5.1 的代码比 5.0.2 漂亮了许多，光是多出一个 luaconf.h 的内容就可以体会作者之匠心。
而整个 lua 并没有因为版本升级而变得庞大的臃肿，恐怕跟他们的小团队有关。据说 lua 标准委员会只有 3 个人。(正是这样，合理的要求就会被迅速通过，正如我前几天提的一些特性的需求。当然你要理解 lua 的设计哲学。还可以勇敢的抛弃掉老版本中不太合理的东西。对比 C++ 标准，那简直太可怕了)同样的，受同事的影响，我对 freebsd 的好感远大于 linux 。freebsd 也拥有一个小团队，这使得他们的源码要漂亮许多。看过 crt 里的那些头文件的组织，我就有了这样的感慨。
我觉得我们游戏引擎的开发团队也要保持住现在的规模，呵呵。
lua 从 5.1 开始终于官方提供统一的 module 实现标准了，这是个值得庆幸的事。今天读了下相关的源码和文档，把这套机制搞清楚了，还是很巧妙的。从简洁这个角度看，要比 python 强 :)
有一点容易被忽略掉(我的同事在用的时候就忽略掉了)，module 指令运行完后，整个环境被压栈，所以前面全局的东西再看不见了。比如定义了一个 test 模块，使用
module("test")
后，下面不再看的见前面的全局环境。如果在这个模块里想调用 print 输出调试信息怎么办呢？一个简单的方法是
local print=print
module("test")
这样 print 是一个 local 变量，下面也是可见的。或者可以用
local _G=_G
module("test")
那么 _G.print 也是可以用的。
当然还有一种巧妙的方式，lua 5.1 提供了一个 package.seeall 可以作为 module 的option 传入
module("test",package.seeall)
这样就 OK 了。至于它们是如何工作的，还是自己读源码会理解的清楚一些。
在读源码时可以发现很多 lua 的技巧，还有一些 undocumented 的东西，比如 newproxy :) 它是一个 unsupported 且 undocumented 的东西，但是它希望实现的却是个巧妙的玩意。
前段时间写过一篇 blog: _ftol 的优化。 今天在读 lua 5.1 的 source 的时候，发现一个更加有趣的技巧。把 double 转成 int 居然可以这样的简单。
union luai_Cast { double l_d; long l_l; };
#define lua_number2int(i,d) { volatile union luai_Cast u; \
u.l_d = (d) + 6755399441055744.0; (i) = u.l_l; }
这个宏神奇的在正数和负数的双精度浮点数时都可以正确工作，以四舍五入方式转换为 32 位整数。
这个数字是 1.5*2^52 :) 小于 2^31 的数字在和这个magic number 相加的时候，按浮点加法的规则（以科学计数法记数），和一定按幂大的一个对齐。而 1.5 是2进制的 1.1 在浮点标准中，小数点前的 1 是不需要记录的。这样，double 的前四字节就被空出来。而需要转换的整数将因为加法恰当的被置入对应的位置。
这个技巧并不总是适用，比如初始化 D3D9 以后，就会失效。因为 D3d 默认会调整浮点运算的精度。在低精度模式下，这个技巧显然不能工作。关于这一点的讨论可以参考MSDN 上的一个帖子
今天 lua 5.1 rc4 发布了。看了一下，比较 rc3 只改了两个地方，一个是 luaconf.h 里的 lua_popen 的宏。还有一个是增加了 hex number 的支持。
前两天在 mailist 里讨论了这个问题，其实早就有呼声加上 16 进制数了。其实我自己也写过 patch 加上，lua maillist 里 Roberto 提了个方案，只需要修改 luaconf.h 里的 #define lua_str2number(s,p) 这个宏就可以了。我测试了一下，很巧妙，还顺手附和了两句。
不过这个方法对 16 进制数前面加了负号是有问题的（虽然我认为一般不会这么用），结果还是对词法分析代码打了 patch，改动不大，而且同样也很巧妙。Roberto 这次很大方，这么快就加到官方版本并发布了。
这次因为这么小的改变就发布新的 rc ，看来 lua 5.1 的正式 release 很近了。期待，这样 lua 就拥有了官方的模块化解决方案。
今天看到一篇 blog ， 浮点数 和 EPSILON 。 这个问题我关注过好几次，最早是为了公司里台球的项目在公司内部 wiki 上写过。后来在留言本上也写过帖子。 http://www.codingnow.com/2004/board/view.php?paster=412&reply=0
想起来，去年 gdc2005 时完整的听过一个讲座，叫做 Numerical Robustness for Geometric Calculations 对这个问题谈的比较深入，google 了一把，把 PPT 找出来了 :) http://realtimecollisiondetection.net/pubs/ 有兴趣可以下载看看。
<a href="http://www.freebsd.org">http://www.freebsd.org</a> 访问不了了。同事开始抱怨，cvs update 不了，也 commit 不了。
我还是很喜欢 freebsd 的 source code 的，项目管理的很好，代码仓库很整洁，想找点东西非常方便。谁知道去哪投诉啊？
上学时喜欢下围棋，喜欢下棋甚至超过编程。不过我想我不是下棋的料，水平老是不见长。工作了后兴趣逐渐转移，生活节奏快了，偶尔在网上下两局快棋也是越下越臭。我原本就是长考型的选手，擅长屠龙之战，偶爱创造性思维，思考时间短了自然下不过人家。不过网络对围棋也不是坏事，比如打谱就方便了许多。
今天看了一盘棋，<a href="http://weiqi.sports.tom.com/php/dqipu.php?id=8441">第10届三星杯半决赛第三局:罗洗河执白7目半胜崔哲瀚</a>。不算新，都一个多月以前了。不过我才看到，实在精彩。
小猪真是天才，居然临场想到了这么大的一条龙都是可以弃掉的。
我最后一盘棋是前年过年在家，把高中的棋友请到家里，窗明几净，泡上一壶茶，整整下了一下午。十年前，我几乎没赢过他，十年后还是输了。很巧的是，那一盘我也是弃了一条超级大龙，我同样做了个大胆的计划。不同的是，我弃掉后依旧输了。我本以为输了很多，只到最后点目的时候，才发现我只输了一目半。
那天非常的高兴，若是十年前，就是我胜了，还是盘绝妙好棋。可惜过了十年，黑棋从贴五目半变成七目半。
希望有一天还能这样盘腿坐在窗台下，在小茶几上，一下午一盘棋。