2003-1-6
新的一年开始了，在这里我祝所有阅读过Looking开发日记的程序员朋友们新年快乐、工作愉快。
最近东北的天气异常寒冷，不过，我很喜欢这种天气。每当我工作了一个通宵，清晨，我都会来到阳台，呼吸着冰冷的空气，在耀眼的阳光照耀下，周围一片萧杀，那真是一种别样的感觉。在我的程序人生里，很多重要的项目都是在这样的季节完成的，因此，我喜欢这样的季节。
在上一篇Looking日记中我提到了T-junctions，在这里我解释一下为什么会出现这种现象。T-junctions的存在是由于浮点运算的误差所导致的。如下面的图片所示，当polygon ABCD被分割为ABC和BDC两个三角性后，三角形BDC又被分割为BDE和EDC两个三角形。这时候原始polygon被分割为三角形1、2、3。在理想状况下，点E应该与点B、C共线。但，实际情况却不是这样，点E会出现在三角形ABC或BDC的内。当点E出现在BDC内时，就会出现一个空白，三角形BEC。这时候就出现了T-junctions。为了研究T-junctions的出现几率，我在LJet中发展了一个审计系统。该审计系统在LJet的release版中不会存在，它由#if #endif之类的编译宏扩起来，毕竟它要花费大量的cpu。最终他会把审计结果输出生成一个HTML文件，供调试、研究之用。T-junctions的出现几率有多大？非常大。当多边形切割次数达到一定的数量级（1000次以上）时，就会稳定的有1/4的切割出现T-junctions。它令我对浮点运算的误差有了深刻的认识。当一个plane切割一个线段时，切割点处于什么位置？可能即不在平面上也不在线段上。因此，在最终运行时，我们看到的平面只是一个逼近的平面。因此，只要出现polygon切割就会出现T-junctions，想要避免T-junctions是徒劳的。但是T-junctions所导致的斑点是我们所不能接受的，因此要对其进行修补。在图例中T-junctions fix的办法就是把三角形ABC修补成polygon ABEC。当然这也是一种理想状态，因为要判断一个点是否在两点之间（E是否在B、C之间）也要进行浮点运算，因此这种判断是不精准的。点E很有可能在B、C之外。如果出现这种情况，T-junctions fix后的polygon将不再是Convex polygon。用过opengl或d3d的程序员都知道，convex polygon是3d render的基础。幸运的是，在最终渲染的时候使用的是triangle，可以有很多方法把concave polygon转化成多个triangle。当我从opengl向d3d过渡的时候，对于d3d render的基本单位是triangle非常不理解，但从浮点精度考虑，在最终render的时候，使用triangle确实是非常好的想法，因为无论如何triangle的3个顶点必然共面。另外，对于3d graphic card来说，它的输入数据可以非常整齐（9个浮点数），非常利于优化。我想，opengl最终还是要把polygon转化成多个triangle的。
我发现很多程序员在编写3d系统的时候，都会反复强调使用opengl还是使用d3d。这其实是完全多余的，只是在浪费精力。如果出现了第三种非常流行的render engine该怎么办？为了编写Looking，我研究了很多3d系统的源代码。它们中的大多数都会提出一个Driver的概念。不同的Driver代表不同的render engine，例如opengl或d3d。Driver标准化了render engine的功能。对于3d系统来说，它并不关心到底使用什么Driver。
在研究T-junctions和编写T-junctions fix代码时，一个阴影始终在我的脑海里挥之不去：经过T-junctions fix后的polygon还能继续参加以后的切割运算么？我感觉，这是不可能的，毕竟很多T-junctions fix后的polygon已经是concave polygon了。T-junctions fix应该是3d系统中关于polygon切割最后一步完成的工作。那么，我在Looking Editor中进行csg操作时就忍受那些斑点么？这令我非常困惑。在这里我想说一下我调试csg的初衷。调试csg可以让我在相对简单的场景中调试bsp树和bsp算法。我可以很容易的看到结果是否正确，发现问题所在。现在看来，这个目的已经达到，并且收获要比最初想像的多得多。但是，显然新的问题出现了。
昨天，一位Looking开发日记的读者发EMail给我，问我关于csg的问题。在这里我想谈谈我对csg的理解，希望有机会和感兴趣的程序员共同探讨。在调试csg前，我查阅了很多关于csg算法的文章。总的来说csg大体有两种实现方式：
1、基于polygon切割的算法。
2、基于渲染的算法。
基于polygon切割的算法相对比较麻烦，它把polygon进行某种形式的切割，然后有选择的丢弃无用的polygon。这种算法一般比较复杂，但最终的render速度是最好的。Looking Editor使用的就是这种算法，在切割polygon时使用的是bsp算法。基于render的算法实现相对简单一些，并且算法的种类也非常的丰富。在opengl的老家sgi有一篇使用Stencil Buffer渲染CSG效果的文章http://www.sgi.com/software/opengl/advanced96/notes.html。另外，在internet上还有一篇使用Z-Buffer渲染CSG的文章，我记不清楚文章的URL了，不过文章的文件名是egsggh98.pdf，在google上应该很容易查到。基于render的算法总的来说是一种可见面分析算法。
为了研究csg，我用3dmax反复进行一些boolean操作，我总感觉3dmax的实现方式是基于render的算法，因为它的效果太完美了。为了证实我的想法，我用3dmax作了一个boolean操作，并把结果export成3ds文件，最后用conv3ds.exe转化成.x文件来察看其效果。结果令我大跌眼镜。3dmax使用的完全是polygon切割算法，其结果实在是太完美了。其结果如下面的图例所示。
csg开发到这里，对于Looking来说其实已经完成了历史使命。但当我看到3dmax的效果后，我产生了强烈的愤怒感。我的愤怒来自我对自己的无能而感到的失望。如果csg就这样结束了，我想我对我自己是没法交待的。如何达到3dmax的程度，成了我心中的一个大疙瘩。我离开了我的计算机，每天捧着一大堆草纸不停的画。这让我想起了当年学机械制图的时候。那时候我大一，那可能是我和同寝的同学们在大学里唯一好好学习的半个学期。那时候，吃剩下的干馒头是最抢手的东西，每当有人想不明白了，就会去抢干馒头，然后用小刀割成机械模型，然后比对着完成作业。教我们机械制图的是一位60多岁的老太太，我算是她比较得意的门生。一次我随便画了张图充数，她给我打的分是“不及格负”，现在想起来都感到好笑。那时，也是冬天，在一包香烟，一张制图板和刘德华的音乐的陪伴下，我经常要忙上一个通宵。
在研究csg优化算法时，我的注意力集中在polygon合并上。我想，如果我使用bsp算法，那么就必然存在polygon分割，那么我能不能把分割后的结果合并成3dmax的那种效果哪？最终我觉得，这非常有可能。要说明这一点，就的从polygon合并说起。在我的概念中polygon合并有两个原则：
1、如果一个polygon分割后所产生的两个polygon在最终结果里都保留下来，那么就应该还原原始polygon。
2、如果两个polygon可以合并成一个convex polygon，那么就应该把它们合并起来。
显然，原则1是最有效的一个方法，而原则2如果在有方向的合并情况下也是非常有效的。但是这种方向性从哪里得到哪？我想使用bsp算法想要减少切割是很难的，如果要让结果在合并时有方向性，那么就要增加切割。这些切割将是以后合并的导向。具体的方法是这样的：
1、SolidA和SolidB进行csg操作。
2、构造SolidA的bsp tree，构造SolidB的bsp tree。
3、当SolidA的一个polygon被push到SolidB的bsp tree之前，寻找SolidB与该polygon的交点。这种交点不是随便的SolidB上的线段与polygon所在的平面的交点，而是SolidB的“棱”在polygon在上的交点。寻找这些“棱”要判断一个线段是否属于两个face，并且这两个face所在的plane不同。
4、用这些交点分割该polygon。入图例所示。polygon ABCD被交点E分成ABE、BCE、CDE、DAE四个triangle。triangle CDE又被交点F分割为ECF、CDF、DEF三个triangle。依此类推。
5、把分割后的triangle都push到SolidB的bsp tree中。
6、对SolidB作2－5的操作。
该操作的目的就是最大程度上减少csg操作所产生的新的顶点。这种顶点的减少是通过polygon合并完成的。按道理来说，经过polygon合并后，将产生3dmax那样的效果，事实也确实如此。对此我感到非常的高兴。Looking的结果如图例所示。
当然这个算法还是有一些瑕疵的，在某些情况下还是会出现一些不必要的新的顶点，这些顶点会出现在两个Solid的交叉部分，但数量可以控制。这时我有了一个新的想法。在说明这个想法之前，我要说一下csg操作的必要条件，那就是：SolidA和SolidB必须是闭合的。举个例子，写过3D的可能都知道那个大茶壶，它是一个典型的非闭合体，在壶嘴和壶盖上都不是闭合的。当用它作csg操作时，无论是3dmax还是looking，效果都不好。因此可以假定SolidB的棱在SolidA上所留下的切割痕迹是一个或多个闭合polygon，当然不一定是convex polygon。但是可以用它的边缘把SolidA分割成多个convex polygon。然后再把SolidA用于csg操作，这样就不会再出现不必要的顶点了。这时候，又一个想法出现在我的脑海里，我发现我绕了一个非常愚蠢的大圈子。为什么要把这些可怜的polygon扔到bsp tree这个绞肉机里哪？3dmax作上面的那个csg操作速度飞快，而Looking却要花费5秒钟的时间，我想问题可能就出在这里。不过，我可不想在csg上继续下去了，我已经离开主题太远了。我把这些想法记录在Looking的PUL（possible update log）里，以后再解决吧。
谈到3dmax的csg，我真是颇有感想。3dmax发展了很多年，看看3dmax的copyright，1996-2002。但我记得好像在我使用dos的时候就有3dmax了。而csg是在3dmax4及其以后版本中才出现。这说明3dmax是在一个相对平稳但不断前进的过程中发展起来的。再看看国内的公司，真是够让人心寒的。国内的公司就像那些整天幻想着一夜暴富的人，东吃一口，西吃一口，真正有自己的重头产品的软件公司却一个也没有。我现在所在的公司，虽然算不上国内的正规军，但也是一个300来人的大公司，项目来源及其旺盛。今年，当我写完那个网管系统后，我向公司建议让我继续深入发展该系统。不需要给我很多人，3、4个足以；不需要给我公司的主力，新毕业的学生就行。3年后，它肯定能发展成一个非常有竞争力的产品，而且公司会多出一批生力军。但是，一句不符合公司发展方向就把我踢了回来。呵呵，当然了，如果公司同意了，也就没有Looking开发日记了。
写完csg，我感到非常的疲劳。于是我又开始“腾挪”了，于是工作又回到了Looking Editor。面对我的问题是系统的收缩问题。这可能是我在Looking开发日记里第二次提到“收缩”这个词。它相对于系统的扩张（呵呵，当然，这都是俚语）。我在写系统的时候，为了不打断思路有时会出现一些短期行为。尽管随着开发经验的增长，这些行为有所减少，但对于我来说还是不可避免的。收缩的过程就是对这些行为的调整，收缩并不意味著只是修补以前的代码，而是修补以前的思路，把自己从高度前冲的状态中解脱出来，回过头来好好总结总结。我在写项目的时候，非常喜欢那种推进感，逢山开道，遇水搭桥。但到了一定程度，我会自动停下来进行调整。这就象盖楼，把基础墩实，然后再继续前进。
我首先开刀的是那些component。当时为了好玩，一口气写了一大堆，但没有考虑component间的共性问题，因此出现了大量的重复代码。呵呵，这是典型的短期行为。我在用C写程序的时候有一个习惯：
1、如果一个表达式出现了两次，哪怕是在一个函数里出现的，必用宏去替换。
2、如果表达式经过发展复杂到一定程度，就用函数去替换。
如果用OOP编程，当在共性中出现个性分支，必要派生子类。在修补那些component的时候，新的问题又产生了。那些component的共性问题，我想通过继承来解决，至于聚合，我根本就不打算考虑。因为系统还在发展中，因此component的interface不可能定义的非常周到，如果使用聚合只会给自己增加麻烦。但是Looking的component的interface是以一种继承的形式存在的。LESolid继承于LEBaseSolid，LEBaseSolid继承于LEObject。这种形式不是Looking必须的，但是Looking的属性编辑器所要求的。ATL的类的继承和Interface的继承就产生了冲突。当时，还真蒙住了。后来，突然想到ATL的继承关系是倒过来的，也就是CComObject是子类，而我定义的类是父类。那么，我定义的共性基类应该在CComObject和CXXXSolidObject之间，也就是我的继承关系也应该是倒过来的。这时候，我想，我的反应能力已经降到一定程度了，真是该休息了。
不过在彻底放假前，还是有很多工作要完成的。首先，Looking Editor在创建对象时，使用delphi那样的方式拉出一个矩形框，然后构造对象。但在3维系统里这样的数据就显得太少了。3dmax是使用一次鼠标操作就可以调整被创建对象的长、宽、高。而且3dmax在创建对象时，不同的对象有不同的鼠标操作。要完成这种功能，就需要把鼠标操作的行为由Looking Editor来控制，但对于行为的解释要由component来解释。其次，component的功能需要进行扩展。component只是用来创建solid么？在3dmax中显然不是这样。3dmax的boolean操作按钮实现的是功能，但它是以component的形式存在的。既然3dmax这样作，我也要这样作。这样的设计带来了新的问题。在以前的模式下，Looking Eitdotr是主体，而component是完全被动的。但在新的模式下，component会与Looking Editor产生交互。在这种模式下，Looking Editor就象一个篮球场，而Component则变成了球场上的球员。举一个简单的例子：要完成3dmax那样的boolean操作component，component必须知道looking editor选中了两个Solid对象，当boolean component完成操作后，这两个solid对象在Looking Editor中就不存在了，它们成了新的Solid对象的两个子对象。因此，新的模式必须要对Looking Editor有所了解，也就是对Looking Editor的Document有所了解。那么，现在问题又变成了了解多少和怎么了解？对于一个开放接口，全部了解非常可怕，但到底应该了解多少才够，我心里也没有底。先让它全部了解再说，以后再归纳其特性。至于说怎么了解，倒是很简单。我把Looking Editor的Document封装到一个Com组件里，命名为IWorkspace。然后把它扔给component，以后要收缩component的了解程度，就修改IWorkspace。仔细想想，会发现这样的布局有意想不到的好处：
1、把Looking Editor的功能收缩到单纯的界面控制，它所知道的事情非常有限，这样有利于模块的划分、系统的变化。
2、把component和Looking Editor完全的隔离开。component不关心Looking Editor，Looking Editor也不知道component是如何存在的，component是如何工作的。它们之间的桥梁是IWorkspace。而com的优势就在于组件的无缝替换。
3、IWorkspace可以被其它模块反复利于。比如，IWorkspace必然要完成serialization任务，当我们在编写Looking编译器的时候，是否还要写一个文件解释代码？显然那是不应该的。
写着写着，我感到有些泄气。Looking慢慢地已经发展成一个2万多行的大系统了。要想方方面面的说清楚真是非常困难。本来想在这篇日记中提到6个问题，但只说了一半，我的手就已经写酸了。很想侃侃程序人生，唉，下次再说吧。
新的一年，新的开始，大家都在精神饱满的开始新的冲刺吧。呵呵，我比较没出息，从1号睡到了5号，每天16个小时。
