raytraced comic rendering

前段时间买了一本叫做noir comics的书。作者介绍了一种完全用黑白两色来表现的画风。下面引述前言的一些话：
black is my favorite color.
although there is a debate on whether black and white are actual colors - such as red, yellow, or blue - to me black is the most vibrant. when applied, black is undeniably striking. it defines, it punctuates, it makes a statement.
the french word for the color black is noir. over time, noir has come to reflect a mood, a tone, and most appropriately, a style. suggestive of danger or violence, film noir is characterized by low-key lighting in a bleak urban setting with corrupt, cynical characters. in my approach, the word noir simply celebrates the color black; it is not confined to a specific genre.
这种画风我很喜欢：现实里略带些残酷。

光线追踪这门课要求我们扩展pbrt。一开始我打算做participating的渲染。但是看到的那个paper设计到很多参数，例如说牛奶中蛋白质和维生素的比例。这些都无从知晓。还有公式的单位也没有讲，看的很头大。例如光的波长用的是纳米还是什么?最后发现用的是米！
诸多不便，最后让我不得不换个题目。用raytracer实现以下noir comic的这种画风。
用raytracer做NPR的好像不多。我能找到的文章讲NPR的都是建立在realtime的基础上的。虽然很多商业的渲染器都支持这个功能，但是毕竟raytracer追求的是真实，很多功能，例如全局光，path tracing这些东西，都在noir这种画风中用不到。所以我要做的是简化raytracer的shader程序，另外加上silhouette detection。下面是一些结果，我还基本满意，不过还有些小问题：

用CUDA在GPU上实现一个神经网络

这个学期选修了显卡体系结构的课。作为课程设计，我们在GPU上实现了一个简单的神经网络，可以辨识手写的数字输入。效果还不错。速度比CPU的提高了200多倍，而准确率差不多，都是90多。详细的情况我发在了codeproject上面了。http://www.codeproject.com/KB/graphics/GPUNN.aspx

pbrt渲染器的一个bug

pbrt这个渲染器有个bug，渲染带光子贴图的场景时，会产生access violation。原因是kdtree.h这个文件有问题。第96行，

把
std::nth_element(&buildNodes[start], &buildNodes[splitPos],
&buildNodes[end], CompareNode(splitAxis));
改成
std::nth_element(buildNodes.begin() + start, buildNodes.begin() + splitPos,
buildNodes.begin() + end, CompareNode(splitAxis));

就好了。

感觉是个挺奇怪的问题。还没有细想过。
kdtree是存储光子贴图的结构。

使用sse指令的类为什么要自定义new和delete操作符

最近在用sse写一个效率好一点的向量类，但是运行的时候总会出现access violation的错误。很久以前，我用sse指令尝试写过一些向量运算的代码。当时印象特别深的就是凡是用到__m128类型成员的类，需要自己定义new和delete。今天再次看到当时的程序：

static void* operator new(size_t size)
{
void *p=_aligned_malloc(size,512);
return p;
};

始终不明白的一点就是，那个512是什么意思。随便改成了64，发现也能运行。
但是这个程序频繁出现access violation。
查了google，得到如下答案：

It is much more likely that you're getting this error because dynamically allocated variables are not 16-byte aligned, also not with __declspec(align(16)). You will need _aligned_malloc (http://msdn2.microsoft.com/8z34s9c6.aspx) for that. Another alternative is to use static variables (which the compiler can align on the stack).

于是把64改成16，就运行成功了。

Good news everyone, OpenGL on Vista.

很久以前，当微软因为捆绑IE被别人指为垄断而送上法庭的时候，我没什么感觉。但是当听说Vista不支持OpenGL的时候，我才觉得微软的垄断确实太过分了。这么做不仅仅是垄断了市场，更重要的是扼杀了技术。我当时就想，如果微软真的这么胡来，我就再也不用Windows了。那时我还给nVidia写过邮件，提过意见。

今天上gamedev的时候注意到一些关于OpenGL新进展的消息，其中之一就是来自nVidia的OpenGL on Vista，是个ppt文档，翻译如下：

好消息！
去年的这个时候…
Windows Vista上的OpenGL是建立在DirectX上面的，为的是能够使用“玻璃透明效果”。
而今天的情况是…
Windows Vista完全支持OpenGL加速驱动。
OpenGL和玻璃效果可以完全兼容。
新的驱动可以确保运行的效率和在Windows XP上运行的程序不相上下。

细节
Direct3D和OpenGL使用的是共同的窗口管理接口
- 分配资源和向图形显示硬件发送命令
Windows Vista CD不包含驱动
- 驱动需要到Windows XP一样的站点下载
微软保留建立在Direct3D基础上的OpenGL，用来实现一些基本的功能
- 仅仅当用户计算机没有安装OpenGL驱动的时候

感谢
感谢OpenGL社区
联系微软，提出了Windows Vista上硬件加速OpenGL的需要。（哈哈，这里面有我的贡献！）
感谢微软
开始回应市场需要
通力合作，我们可以创建Windows Vista上最完美的用户体验。

--------------------------------------------

另外想起来：前段时间看到有人跟IE小组抱怨IE6不支持透明png的事。那个人说，从IE5的时代，大家就都在喊着要透明png的功能，但是居然到了IE7才实现，这说明IE小组对于市场需要的判断实在是太迟缓了。
我觉得如果OpenGL在Windows系统上消失的话，也将是自杀的举动，是市场判断的严重失误。

AssortedWidgets, 我的开源界面库

最近很少写博，一直在埋头编程。下面隆重推出一直埋头编写的AssortedWidgets——我的开源界面库。可能会用在我的下一版pillow中。

我曾经多次在博客的日志中提到了我对选择C++的界面库犹豫不决，似乎每一款现成的界面都不尽人意。前段时间发现www.bramstein.nl上面的基于OpenGL和SDL的界面库，从它的介绍上看，和我理想中的界面很一致，比如有java swing的代码风格，可以自定义外观等等。但是因为它是一个刚刚开始的工程，所以很多东西都不完善，所以如果我打算用这个界面的话，势必还要自己写很多的东西。而且看过它的代码之后，觉得很多东西还是不理想。我觉得与其把时间浪费在比较不同的界面上，不如干脆按照自己的想法来实现一个界面库。这样，我的AssortedWidgets计划就产生了。起AssortedWidgets这样一个名字是因为有一天吃巧克力的时候看到它盒子上写的Assorted Chocolate。程序至今已经写了两个多星期了。

AssortedWidgets的特色：
开源，BSD协议。
类似C#的delegate代码风格。
可以自定义界面的外观。
有跨平台的可能(OpenGL和SDL)。
可以替换其它的io库(目前用的SDL，但是应该可以替换成glut)。

AssortedWidgets目前支持:
控件:Button, Label, Text Field, Drop List, Check, Radio, Menu, Progress Bar, Slider
容器:Scroll Panel, Panel, Dialog
布局:Flow Layout, Border Layout, Gird Layout

以下是目前演示程序的截图效果，程序在我的网络硬盘中可以下载：




下面是我关于界面的一些思考，想到什么写什么，没有什么调理：
1、好的界面应该提供给用户自定义外观的可能。这种可能应该是代码级别上的，而不仅仅是支持自定义外部的皮肤文件。这样做的好处就是可以让界面满足任意的外观需要。要做到这一点，界面库应当将程序的绘制部分和处理消息，场景管理的部分分开。在界面外观的问题上，不同的程序有不同的追求，像wxWidgets就希望它的程序能和操作系统的外观尽量一致。同样的一个wxWidgets程序，在xp上运行就是xp的样子，在苹果上运行就是苹果的样子。我觉得这样的设计是好的，但是不应该把它限制死，毕竟不同的使用者有不同的需求。在我的AssortedWidgets中，我定义了一个抽象的类，叫做绘制引擎，任何实现了这个类的类都可以担负绘制界面的工作。这个绘制引擎是唯一负责和绘制有关工作的类。因此它也是唯一能出现OpenGL函数的地方。如果有人希望把AssortedWidgets搬到DirectX上去，他就可以利用DirectX的函数来实现一个自己的绘制引擎。总之我觉得把绘制单独出来可以最大限度保证程序的灵活性。

2、界面的布局用程序代码来定义，不要用外部文件。用一种外部文件来定义程序的布局好像是最近比较时兴的。CEGUI就支持XML的布局文件，直接编辑好一个XML，再在程序里面调用就可以得到一个对话框之类的东西。另外还有一些编辑GTK+的工具，最开始都是直接生成代码的，到后来变成生成文件。有的wxWidgets编辑工具也一样。我不喜欢这样，因为这样的外部文件会使得最后的程序很累赘，另外效率也受一些影响，而且存在文件被别人改动的可能。最关键的就是有时候写xml太麻烦了。

3、通过边界盒来检测鼠标。我觉得边界盒的方法是最直接和高效的检测鼠标是否在某个位置的方法。在 的那个界面的作者写了一篇文章介绍在OpenGL中最常用到的检测鼠标的方法，有边界盒发，投影射线法，还有颜色拾取法。在他的界面程序中，他用的颜色拾取法。我觉得很奇怪，这个是我在做pillow的3D拾取的时候用到的方法，界面既然都是2D的，觉得没有必要。用颜色拾取的方法倒是一劳永逸，但是效率不高，而且这样一来在非绘制的程序中势必要夹在一些OpenGL的函数，我觉得这样不好。我写过邮件问那个作者，为什么用颜色拾取。他说他有什么3D界面，只能用颜色拾取。我当时不明白他说的3D界面是什么东西，现在想起来估计是他把界面绘制到一个贴图上，再把贴图贴到3D物体上面。

4、最好是java的代码风格。我最早接触的面向对象就是java，一直觉得很方便。后来适应了wxWidgets那种mfc风格之后，觉得也还行。不过java的另一个好处就是有很多方便的布局管理器。但是在C++里面，完全模仿java swing也有不方便的地方，我之前写过了。所幸后来发现了FastDelegate这个东西，现在实现的是类似C#的方式。

5、场景应该组织成树的结构。场景组织成树的好处就是可以尽快地检测到鼠标碰撞。比如说首先确定鼠标在一个对话框中，那它只可能和这个对话框中包含的控件发生碰撞，而不在这个对话框中的就根本不用考虑了。但是这样也有问题，有些控件的外形会变化，比如说菜单栏和下拉列表都会展开，展开之后可能会超出包含它的对话框，这样超出的部分就不可能响应鼠标了。这是我最开始没有考虑周全的地方，后来只好对这类控件单独处理，绕了一些弯子。

SDL_image不认png格式的解决办法

我想利用SDL来生成OpenGL的贴图，但是总是出现unsupported image format的错误信息。
我的程序是这样的：

SDL_Surface *surface=IMG_Load("Font.png");
SDL_LockSurface(surface);
glEnable(GL_TEXTURE_2D);
glGenTextures(1,&resourceID);
glBindTexture(GL_TEXTURE_2D,resourceID);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, surface->w, surface->h, 0, GL_RGBA, GL_UNSIGNED_BYTE, surface->pixels);
glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER,GL_LINEAR);
glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glDisable(GL_TEXTURE_2D);
SDL_UnlockSurface(surface);
SDL_FreeSurface(surface);

程序是没问题的，但是就是出错。我在网上看到SDL_image需要libpng和zlib的支持，我添加了这些dll文件之后，问题依旧。我突然想起来当时编译SDL_image并没有要这些支持的文件，而且编译成功了。我又重新打开SDL_image，重新编译，依然通过，而且根本不需要libpng。奇怪！后来我从官方网站上下载了已经编译的二进制替换了我自己编译的dll，问题就解决了。看来编译SDL_image确实是应该有libpng支持的，但是不知道是不是默认的情况下png的功能被禁用了，因而在没有libpng的时候编译也通过了。但是还是不知道应该如何设置。

sse指令的小不明白

最近尝试用sse指令来改我的数学库，但是遇到些问题。比如我自定义一个类Vector，类似：

#pragma once
#include <xmmintrin.h>

namespace Pillow
{
 namespace Math
 {
  class Vector
  {
  private:
   __m128 data;
  public:
   float &x;
   float &y;
   float &z;
   float &w;
  public:
   Vector(void)
    :x(data.m128_f32[0]),
    y(data.m128_f32[1]),
    z(data.m128_f32[2]),
    w(data.m128_f32[3])
   {
    data.m128_f32[0]=0.0f;
    data.m128_f32[1]=0.0f;
    data.m128_f32[2]=0.0f;
    data.m128_f32[3]=1.0f;
   };
   ........
   friend void operator+=(Vector& v1, const Vector& v2);
   public:
    ~Vector(void){};
  };
  inline void operator+=(Vector& v1,const Vector& v2)
  {
   v1.data=_mm_add_ps(v1.data,v2.data);
  }
 }
}

然后测试的时候，如果我这样就没问题：

Pillow::Math::Vector v1;
Pillow::Math::Vector v2;
v1+=v2;

但是这样就会出现access violation的错误：

Pillow::Math::Vector *v1=new Pillow::Math::Vector();
Pillow::Math::Vector *v2=new Pillow::Math::Vector();
(*v1)+=(*v2);

后来我在codeguru上问到：如果类中包含__m128类型的成员，需要用_aligned_malloc和_aligned_free重载new和delete。然后我就在类里添加如下内容就解决了：

static void* operator new(size_t size)
{
 void *p=_aligned_malloc(size,512);
 return p;
};

static void operator delete (void *p)
{
 _aligned_free(p);
}

但是我还是不知道为什么。不知道这个问题是否和我的amd有关，还是说intel的运行也一样？

Displacement mapping简介

我很想把pillow做成像zbrush和mudbox那样的笔刷建模工具，因为这样的工具可以做出很逼真的细节。实现这个想法就要用到displacement mapping。我习惯叫这个东西置换贴图，但是今天看到有人翻译成位移映射，似乎更准确。翻译一篇介绍，原文来自维基百科。

位移映射是同凹凸贴图，法线贴图，切线贴图相区别的另一种制造凹凸细节的技术，它使用一个高度贴图制造出几何物体表面上点的位置被替换到另一位置的效果。这种效果通常是让点的位置沿面法线移动一个贴图中定义的距离。它使得贴图具备了表现细节和深度的能力，且可以同时允许自我遮盖，自我投影和呈现边缘轮廓。而另一方面，这种技术是同类技术中消耗性能最大的，因为它需要额外的增加大量几何信息。
很多年来，位移映射是高端渲染器独有的功能，比如说RenderMan，而那些实时的程序接口，比如说OpenGL和DirectX，则缺少对这个技术的支持。一个原因是，最初的实现方法需要对物体表面进行自适应细分来得到许多微小的面，这些面的尺寸投影到屏幕上刚好是一个像素的大小。
现在图形硬件已经支持Shader Model 3.0了，位移映射可以通过一种向量贴图的方式来实现，这个向量贴图并不像普通贴图那样改变物体表面的颜色，而是改变物体表面点的位置。它不像凹凸贴图，法线和切线贴图，因为这些技术都是在制造凹凸效果的假象，而位移应设是真正通过贴图的方式制造出凹凸的表面。它必须要配合细分算法，增加渲染的多边形数目来制造出细节的效果。

Brief of pillow in English

Pillow is a light weight application on which I' m working lately, the current aim is to make a simple modeller along the lines of commercial modeller silo. The project is at a very early stage implementing some basic modelling operations, such as "move", "rotate", "scale", "weld", "split" on objects and sub-objects like vertices, edges and faces, and also catmull-clark subdivision. Because pillow is under developing, there are problems, but it is still a good start point for me, 'cause as far as I know, lots of teams of identical applications take a long time to develop, normally in years, and pillow is only a 2-month job that I' m doing alone.

On history:
I got the idea of doing a modeller of myself in Oct 2004, at that time I was learning directx by myself, and I thought of actually making something to get familiar with the skills, so I decided to write this application. I set the silo modeller as my goal, for one thing, silo adapts a reasonable set of shortcut keys which I believe can speed up the progress of modelling, and also, silo is small in size. However, after I had the idea, I didn't have the time to concrete it until this summer, I got myself graduated. I have bunch of names for this application, first "cedar" and then "polygon studio" and "clayshop", and now I' m calling it "pillow".

On code:
Since I decided to practice directx with pillow, the first version is written with c# and managed directx. I also used a game engine called truevision3d, because functions like object-picking are out there already. But due to the huge data structures of game engine, the code's performance was very poor. So, then, I tried to code directly with directx. The current version is rewritten with c++ and opengl. The GUI library I use is wxwidget. I always care a lot about the user interface of my program. I don't think the appearance of products is of trifle. If the gorgeous design of apple computer was taken away, the company that never compatible with others would not survive in the market. However, I cannot find a good GUI library for my job, I need a cross platform, open source, skinable library with plenty of controls. While doing this application, I tried cegui, wxwidget, qt4, and picked up wxwidget finally.

The code is divided into 3 main layers, the ui layer undertakes the job of interacting with users, and displays the result of operations. The scene layer is in the middle, managing the 3d scene, converting the graphics operations to primitive operations on data structures. This part is actually the core of the whole program. The data structure is in the deepest layer which contains the data of the scene. The communication between the scene layer and the data layer is strictly defined as a set of commands; every command is tracked by a thing called history manager to enable users to restore at any time. As in the image, blue arrow is the flows of commands, the purple one is commands recording and the red ones are the data flows.

Currently, pillow doesn't support undo and redo. Although I already implement these operations, I didn't combine them with the ui. Because this part is easy to leak memory, I need to make sure other parts works fine before I add these functions.

when I was coding undo and redo part, I first thought of making commands, and every command has its inversion, and when I need to undo an operation, I simply call the inverse command. Yet, some operations, say calculating the average number, don't have commands in inversion. I could keep a record of the situation before the average happens, but this is a silly way. and then I thought up dividing the operations into layers, because no matter how complex a graphics command might be, it finally modifies the primitive data structures and the primitive operations on data structures can be simply defined as "new", "modify", "remove", so I only need to keep a record of these basic operations to hold the history of all the graphics operations. Actually, there are dozens of primitive operations defined in my code, more than just "new", "remove" and "modify".

So what is history manager? It is an undo queue and a redo stack, commands are pushed into the head of the queue, if they reach the end of the queue, and they are discarded. When the user wants to undo a step, a command will be popped and executed, at the same time, an inverse command be pushed into the redo stack. And if redo happens, just do everything in the backward.

How to prevent memory leak? My design is centralizing the management of all pointers; this is what I call data pool. It is actually a dynamic array to store pointers. Every function can use the data, but cannot new it or release it. There are two ways to release the data, first, if the remove operation needs to be recorded by the history manager, pass the pointer to the history manager, and as the record log is discarded by the history manager, the pointer is released. Second, if the operation does not need to be recorded, release it directly through the data pool. By adopting this, I can guarantee that, at any time, every data in the heap has at least one pointer stored in the data pool.

One more thing:
When I first showed people my idea of doing pillow, somebody asked what the unique feature of my polygon modeller is, since there are so many of them. I do want to do something special, but just before going creative, I need a base. And this is why I make pillow. I dreamed of making an application that combines the traditional sculpture progress with the cg making operations enabling people to create the shape more directly. I have already found some directions like the commercial software zbrush, mudbox and the teddy demo. So this is what I really wanna do in the future. Hope I can insist on doing this.

Some resources:
A tutorial on box modelling in pillow:
http://billconan.blogspot.com/2006/10/pillow-01a.html
A piece of flash showing how pillow works in action:
http://billconan.blogspot.com/2006/10/wink.html

学究一下，编了一个radiosity辐射度渲染程序

我特别羡慕那些有强烈兴趣爱好，懂得自我发掘，而且做出一定成果的人。我不是这样的人，我的兴趣太多，又不太有常性。以前我在旧的博客上天南地北地扯了不少，却很少专注于自己的事业，所以当初决定把博客搬到这里的时候，我给自己规定的基调是尽量走学术路线。其直接的后果是，流量下降，评论大幅度减少，女Fans更是一个不剩，现在基本上已经属于是自娱自乐了。学究当到底，今天我编了一个radiosity的偷懒算法程序。
很早以前，我在azure的博客上看到他做了一个辐射度的渲染程序。当时我没有仔细看，但是有一点印象特别深，就是他把摄影机摆在patch上来模拟能量的入射。我不知道这个想法是不是他原创，但是真的是太聪明的一个偷懒办法了。传统的辐射度需要做很多射线，然后再和多边形求交，现在可以用现成的摄影机来替代，简直太省事了。
这样一来，辐射度程序实际上变成了这样的一个过程：
首先组织好一个场景，这一步我是在3D Max里随便做了一个房间，房间上开了一个窗户，用来透进点亮光，作为初始的光源。房间的中间放了一个柱子，主要我想看看这个柱子能形成什么样的影子。在3D Max中导出成obj格式的文件，然后把里面的数据直接粘帖到代码里，改了改，存放在数组中。
然后为每个面开辟光照贴图的空间，并且计算法线，切线。
将贴图分解成小patch，计算每个小patch中心点在3D场景中的位置，在这个位置上放置摄影机，拍摄当前的场景。将patch中心映射到3D场景中的公式是这样的（四边形v1、v2、v3、v4）：
v1+(v2-v1)*u+(v4-v1)v 其中uv是贴图坐标，v1、v2、v3、v4是四边形的端点。
渲染的场景存放到一个空间中，我的程序里是一个64见方的数组。然后对这个数据进行分析，得到一个当前patch的颜色。分析的过程是，首先计算这个64见方的图像上每个象素距离中心点的距离，根据这个距离得到一个权重。为什么需要权重呢？因为在传统的辐射度算法中用的是射线来模拟光照，光照对于颜色的影响取决于入射的角度。因为我这里没有用射线，所以无法得到角度，但是摄影机得到的图像中，点的位置离中心越远，说明生成它的入射光线的入射角就越大，所以在最后决定颜色的时候越不重要，这样将所有点的权重计算出来作一个加权平均，得到一个颜色值。但是这还没完，还需要乘以一个数值，这个数值是一个近似的能量衰减。光在传播的过程中能量是衰减的。实际上这个衰减和光的传播距离应该是相关的。在传统的辐射度计算中，射线和多边形相交的同时可以得到这个距离，这样就比较容易计算精确的衰减。但是因为这个是偷懒版的程序，不能得到光源距离当前面长度。所以就简化假设任意距离的光源产生的光照都要衰减一个固定的比例。我的程序里用的0.2。当然也可以这样来假设，光源距离当前物体非常远，而当前物体中（我的这个房子）的所有面之间的距离相对于这个光源与这个房子之间的距离可以忽略不计，这样的话房子中各物体的衰减差别不大，就近似成一样的。
以上就是我的懒汉版光照模型。
一开始我在这个程序中用的贴图是128*128的，感觉稍微有些粗糙，后来改用256*256的，速度明显变慢了。不过最后出来的结果我总觉得别扭，但是又看不出来问题。不知道是不是我的懒汉光照模型有问题，还是我的程序什么地方疵了。有时间再看看。左边这个图显示的是如何从最开始的初始场景逐步照亮的过程，就第一次辐射变化比较明显，后面的变化及其细微。

Pillow简介

一直缺少一篇关于Pillow的介绍，现在补上。Pillow是一个我编的轻量级多边形3D建模程序，目前的目标是在模仿silo(www.nevercenter.com)的功能。这个程序还处于初级阶段，实现了一些基本的多边形建模操作，比如对点、边、面、体的挪动旋转以及缩放操作、删除、焊接、切割等等，另外还有catmull-clark细分，出于速度的考虑，目前人为地限定在最大5次细分，实际上细分的次数可以不限。因为这个程序还在起步的阶段，还存在很多需要解决的问题，但是不管怎么说是个不错的开始。据我所知很多小规模的建模工具都要开发很多年，而我这个才2个多月,何况我这个项目只有我一个人在搞。急不得。

下面介绍一下历史：
大概是在2004年10月的时候我开始有自己编一个建模工具的想法。当时是要学DirectX，我觉得学编程必须要动手才行，所以想到写个像silo的程序。之所以要模仿silo是因为我当时觉得silo是一个面向使用的程序，它能够合理的把操作分配到左右手，感觉工作的效率提高了。另外一个原因就是silo是所有3D建模工具里规模比较小的。有了这个想法之后很长时间都没有什么进展，光磨了嘴皮子。不过在这段时间里我思考了很多东西。直到今年7月分毕业，我才重新开始写这个程序。我给这个程序起过好多的名字，最开始叫cedar，然后叫polygon studio，再然后叫clayshop，直到现在的pillow。这些都可以在我旧的博客上看到。

下面介绍一下程序：
因为最开始是为了练习DirectX，所以最早是想用c#和managed directx来写。当时还用过一个truevision3d的引擎。原因很明显，引擎里屏幕拾取等操作已经都给你做好了。但是因为引擎的数据结构特别大，效率很低，所以后来我就直接用directx来编了。而我现在的这个程序则是重新用c++和opengl写的。最开始有人问我为什么不选择opengl，我的回答是每一个图形库都很有学问，一个尚且学不好，怎么能顾得上学另一个。不过自从接触过opengl之后，我觉得opengl没有directx封装的利害，感觉用起来很直接。我真的很喜欢opengl。用c++的目的首先是因为要用opengl，当然tao framework我也试过，不爽。第二个原因是因为效率，交互性强的程序太需要效率了。第三个原因是因为我一直对c++不太开窍，有点不甘心。c++应该是编图形程序的首选语言。至于程序的界面，我选择了wxWidgets。我编程的时候特别会做表面文章，非常在意界面。我认为外观设计不是什么无足轻重的东西，如果苹果公司没有它的工业设计，这样一个不兼容的怪胎早就被淘汰了。不过很遗憾，我找不到满足我要求的c++界面库。我希望能够有一个跨平台，最好开源，可以换肤，控件比较丰富的界面库，但是没有。编这个程序的时候我先后用了cegui，wxWidget，qt4，但是哪个都不满意。最后选择wxWidget也是因为silo也用的是它。

关于程序的结构：
我的程序大体分成了三个层次，界面层负责和使用者交互，并且把操作的结果显示出来。中间的控制层负责管理整个场景，负责将图形的操作转换成对于数据的操作。这部分实际上是整个程序的核心。最里面的是数据层，存储的是场景的图形数据。场景管理器和数据层之间的交互被严格定义为一组命令，并且每一个命令都会被一个叫做历史管理器的东西记录下来，便于随时将操作进行回退。在图中，蓝颜色的箭头表示的是命令的走向，紫颜色表示的是记录命令，红颜色是显示数据的走向。
目前我的程序还不具备undo和redo的功能，但是实际上我在程序中已经实现了。但是和界面结合的时候我没有把这个添上。因为在和界面结合的时候，程序写的有点乱。之前对于如何实现程序的核心部分，我考虑了很长时间，但是和界面结合的东西我考虑的不多。另外也是因为没有找到一个我觉得很得心应手的界面包，而我又尝试了很多的界面方案，几乎每一种界面都有自己的一套编程风格。因为历史记录这个部分是比较容易出问题的部分，尤其是容易内存泄露，我就暂时没有把它包含进来。
当初要实现undo和redo的时候我想到要用命令的方式，每个命令都有个逆命令，操作的时候记录每条命令，需要回退的时候再调用相应的逆命令。但是很多操作，比如说求平均，是没有逆命令的。把求平均之前的情况都记录下来显然也是个比较笨的办法。后来我想到把操作分层，因为不管一个图形操作的过程有多么复杂，归根结底都是要改变数据，改变数据的方式无非就是添加、删除和改动这几种，所以我只要记录这些简单的操作，就可以应对复杂的图形操作了。实际上在我的程序中定义的简单操作要有几十种，并不只是添加、删除和修改这几种。
什么是历史管理器呢，实际上是一个队列和栈的结构，命令被压入一个叫undo的队列头部，如果超过了队列的长度，则从队列的尾部直接抛弃。如果用户想要回退一步操作，就直接弹出在队列头部的一个命令进行回退，同时把这个命令翻译成逆命令放到redo中去，这个redo是一个栈的结构，如果要重做这步操作就弹出redo栈，执行，然后把命令翻译成逆命令再次放到undo队列中。
要如何防止内存泄露呢，我的设计是这样的：把所有在堆中的数据的指针进行统一的管理，这个结构我叫做data pool，实际上是个动态数组。任何其它的操作只能够引用这些数据，引用是通过数组的下标，而不是指针。释放指针由这个data pool统一进行，有两种方式，一种是直接释放，另一种是当需要记录删除操作的时候，把这个指针交给历史管理器，然后当历史管理器也不需要这个指针的时候，再释放掉它的空间。这样就可以防止指针已经丢失但是空间没有释放的情况，因为任何时候被分配的空间都至少在data pool中保留了一个指向它的指针。然后通过data pool释放这个指针，就可以释放掉这个空间。基本上就是这样。

总结：
最开始我把我编这个程序的想法告诉别人，有人就问我，这个程序到底有什么创新的地方，既然天下多边形建模工具已经那么多了。应该说目前还没有，但是以后会有的。现在这个程序虽然很普通，但是这是今后创新的一个平台，未来有可能在这个基础上做一些真正自己的东西。通过编这个程序我学到了不少东西，也多了不少认识。我感觉c++是一个陷阱，确切地说指针是陷阱，用的时候觉得很方便，肆无忌惮。但是当程序大到一定程度，就会突然发现已经是千疮百孔了。处处都有可能造成泄露。但是一个图形的程序又怎么能不用指针呢。我也想过把它都换成smart pointer，但是不知道效率上会打多大的折扣。
我在我的网盘里面放了一个pillow的程序，但是有些bug还没有修复，我已经编不动了，要换换脑子。我很想自己写个界面，sdl和opengl的界面，但是无疑又是个巨大的工程，不知道能不能实现。

一些资源：
之前写的一个pillow的教程：
http://billconan.blogspot.com/2006/10/pillow-01a.html
以及一小段演示动画：
http://billconan.blogspot.com/2006/10/wink.html

仙剑奇侠传3模型文件格式分析(2)

这个上接我这个博客的第一篇日志：仙剑奇侠传3模型文件格式分析(1)。实际上我真正看这个模型的时候好像是六月份。而写上一篇文章的时候在8月份。而这一篇拖了很久。我最开始想至少写3篇，因为虽然模型的扩展名是一样的，都是pol文件，但是实际上里面的数据有差别。比如说场景模型有个光照贴图的坐标，而在物体模型里面就没有。而现在主要分析的是物体的模型。我最初想写这个东西是因为我想要记录一下我当时思考的过程，结果倒是次要的。因为把仙剑奇侠转3的模型拆出来一看其实也就那么回事。但是现在隔的时间有点太长了，很多东西只能记得结论，当时怎么想的现在已经想不起来了。
上回说到发现一个模型文件可能会包含很多组模型，并且在头部0x08的位置有个数值记录了这个数目。这样通过分析拥有多个模型的文件和只有单个模型的文件可以得到模型的头部长。计算的方法是这样的：
假设整个文件有个公共的头部长度x，而每个模型有个自己的头长度为y，文件中包含的模型数目为c，假设一个只有1个模型的文件数据开始位置是a，一个有3个模型的文件数据开始是b，那么这样列个方程,就可以求出每个模型的头部长度。

x+y=a;
x+3y=b;

经过比较几个模型文件，我发现很多模型的数据开始的位置（0x58）都是1500 0000。这个是一个比较奇怪的现象，因为按照我先前的分析，这个应该是贴图坐标，但是这么多的模型的贴图坐标怎么可能这么一致呢？再发现，如果按照先前假设的，FFFF FFFF 是顶点信息的结束标志，那么为什么最后一个顶点（box.pol文件）的FFFF FFFF 后面紧跟着一个295C 7F3F 295C 7F3F ，而这个数据和前面一个顶点的295C 7F3F 00D7 233B 数据这么相像。所以我开始意识到，FFFF FFFF 应该不是顶点的结束标志。因为一开始我先入为主地认为顶点有结束标志，所以我认为在头部没有顶点的总数信息，但是现在看来应该是有的。由于已知这个文件中有16个顶点，所以一眼就能看到在顶点数据区前面，0x5c的位置上有个1000 0000 数值，这不正是顶点的数目么。这下也就说明顶点的数据开始于0x60，且0x5c是顶点的数目，FFFF FFFF 不是顶点数据的结束标志，顶点的结构应该是这样的：

struct vertex
{
float x;
float y;
float z;
int FFFFFFFF;
float u;
float v;
}

通过和其他的文件比较可以发现，每个模型的头部有24字节长。每个顶点数据区域最开始有个头，其中最后4个字节是顶点的数目。整个文件的头有56字节长，第5个字节开始是文件包含的模型数目。
按照这个理论把程序改了一下，发现贴图坐标也正常了。
所以现在的结论是这样的：

文件头
-文件标识
-不知道的内容
-文件所包含的模型数目
-不知道的内容
每个模型的头
每个模型的数据
-顶点的数据
--顶点数据区的头
--每个顶点的数据
---顶点位置坐标
---FFFF FFFF
---顶点贴图坐标
-贴图数据（固定长度）
-面数据
--面数据头（包含了面的数目）
--面的数据

按照这个理论实现的程序：
xj3Model.c
这个程序运行以后可以把仙剑3的模型转换成obj的格式。经过测试，可以转换90%的模型，还有很多2K左右的文件处理不了，估计是索引文件，我没有仔细研究了。导入到3D Max里面基本上就是这个样子：



总结：愣看文件格式需要耐心和运气，像我看这个模型格式的运气就在于有一个box.pol的文件，这个文件名给了我暗示。另外就是文件中存在的FFFF FFFF ，虽然我最开始的假设是错误的，但是些字节还是整个文件的一个突破口。不过真把模型拆出来觉得意思也不大，感觉这些模型做的挺普通的。有时间我会把拆场景模型的文章也补上。

试验一下wink

昨天ShiningRay建议我做个视频的教程，今天试了一下他推荐的wink，确实是个好东西。只可惜我先前的截图不太连贯，只能下次再做点什么别的东西把它录下来。不过wink生成的文件实在是有点大，试了一下，演示了一些基本操作：

刚才试了好半天也没能让这个swf显示完整，一直以为是wink或者firefox的问题，结果发现是google pages上传的问题。难道有大小限制？现在这个用的我的网盘，慢且可能要统计流量。

Pillow 0.1a的操作教程

这是我先前说要写的那个Pillow的教程，主要是要演示一下我这个建模程序的使用方法（程序我在我的网络硬盘里面放了一个，点击导航条的download可以下载，但是还有bug没有修复）。模型做的比较粗糙。这个是完成之后的效果，在3D Max里面简单渲染的：
在开始之前，我先介绍一下Pillow的基本操作。Pillow是一个模仿silo的程序，因而在操作方法上高度一致。silo把建模的操作合理分配到左右手，我觉得能很好地提高工作的效率。简单的来说是这样的：

alt健加鼠标左键拖动用来旋转视角
alt键加鼠标中建拖动用来平移视角
alt键加鼠标滚轮用来缩放视角
鼠标左键拖动用来单面选择
鼠标中键拖动用来双面选择
c为增加细分
v为减少细分
ctrl为沿视平面进行平移，前提是选择了物体
shift为增加选择内容
z为突出面或者边
w为移动模式
e为旋转模式
r为缩放模式
1-7为切换不同的视角
delete为移除点或边，其中点只能是有两个邻接边的点，这个操作目前有bug

Pillow的界面大概就是这样：
所有的操作都集中在菜单里面，而编辑窗口有几个我用opengl做的工具栏，这里面都是最常用的一些操作。把界面设计成这样是因为我曾经用过的一个silo的界面，记得当时我在cgercn发过（现在好像叫cgfinal了）。silo可以自定义部分界面以及快捷键，但是我这个还不行。左侧的按钮选择编辑物体的编辑层次。右面的是选择窗口的层次。上面一条是文件操作，建立新物体和编辑新物体，还有截图快捷键和帮助。下面是选择显示的形式和选择照相机的形式。

下面讲建模的过程：
我做模型的时候比较喜欢box modelling的方式，总是从一个盒子的形状开始，这样比较容易从大局上把握形状，但是也容易让人忽视掉细节。我做模型的时候比较喜欢用参考图。关于参考图，我的经验是从电影电视剧或者mv中去找，因为这样比较容易找到不同角度的参考，而如果直接去找照片的话，正面照好找，侧面照就比较少了。有了参考图之后，要对正面和侧面的图进行一定的缩放和旋转，使得它们的比例一致。在这个过程中我比较喜欢用photoshop的标尺，在photoshop中让两个参考图的下巴和头顶处于水平，鼻尖和眼睛的高度一样，还有嘴角和耳根也要一样。我的这个侧面参考图不完整，所以我用鼠标补了一些脑袋。对齐之后剪裁成两个高度一致的图。

然后开始建模了，首先就是要在Pillow中指定参考图(option->set viewport image)，silo中可以直接用鼠标来调节参考图位置，但是我这个还不行，需要手动输入位置。然后新建一个box(create->cube)。然后对这个方盒子分别在前视图和侧视图中进行调节，使得在前视图近似为头的一半大小，在侧视图中刚好覆盖头部。调整好之后在透视图中删除中间的面，也就是说我们要镜像复制一个当前的模型，因为脸是对称的。点击菜单上的（create->mirror instance）复制出镜像，对称平面为默认。

然后按图进行切割，这个切割线分别对应了头的眼睛位置和耳朵的位置。目前Pillow只支持在一个边的中间进行切割，其实核心的程序允许在任意位置切割，但是和界面整合的时候我偷了点懒。然后将显示模式切换到线框模式，分别在前视图和侧视图中调节点的位置，使得这个造型和参考图近似。
可以随时对模型细分进行观察，目前Pillow在编辑模型的时候还不能实时地更新法线，主要是我还没有想好有什么快的局部更新法线的算法。所以如果想观察光照效果需要从菜单执行更新法线的命令（modify->update normal）。然后新增加一条竖线，这条线要对应人的瞳孔和嘴角。

然后要不断的调节点的位置，使得模型接近参考图。现在继续切割出两条线，一条是在额头，另一条在嘴的位置。同样要在各个视图中调节位置。让线条过渡自然一点。

然后横向切割出鼻子，并且调节。随时可以细分进行观察。在调节好点的位置之后要切割出眼睛和嘴的大致形状。

然后在视图中调节，同时增加眼睛的细节。继续增加细节和调节点。调节点，可以用线框模式来显示，这样比较便于观察。

仍然是增加细节和调节点的工作。继续增加细节，但是这个时候要清楚线条的走向。建模有个原则--线条要符合肌肉的走向，就是图中我用红线画出来的线条。眼睛和嘴的线条要形成一个圈。


在增加线条的同时要不断切割出新的边，但是同时还要删除旧的边。因为我们是盒子建模，一开始的边都是横平竖直的，这个会对我们的最终模型产生一定影响。所谓盒子建模不容易把握细节，很大程度上就是这个原因。其实我觉得懂得如何删要比懂得如何添要重要的多。


如果你最后的成品依然有很多横平竖直的线条，那一定是很失败的作品。继续添加鼻翼附近的线条，这样也是为了增加嘴部的细节。


当嘴的细节到达一定的程度就可以进一步刻画了。要做出黑人厚嘴唇的效果。在眼睛的位置切割出更多的边。

在鼻子上切割更多的边，这个是为了增加细节好开出鼻孔。现在可以依据参考图开出鼻孔了。首先切割出一个矩形的区域。


在这个区域上使用突出(modify->extrude)几次，做出洞来，然后要调节点。时不时细分一下来观看效果。继续增加鼻子的细节，一方面要做出鼻翼凸起的效果，另一方面是修改三角面，尽量把三角面改成四边形。


继续制作鼻翼。现在增加眼睛周围的圈数，增加细节准备做眼睛。

不断调整眼睛周围点的位置，然后选中眼睛上的面删除。删除之后就形成了眼眶。

如果把握不好眼睛的造型，可以生成一个球体作为眼球，放在眼睛的后面作为依据。细致刻画眼睑的效果。


选中眼睛镂空的一圈边，然后将视角转动到头的里侧，按住z键，拖拽出眼睛没入脑袋的部分。继续调节点的位置，让模型有厚度，不是像面具一样只是一个面片。

这是目前侧视图的效果。将嘴上的一组面删除，将嘴裂开，同时增加更多的边，做出嘴唇鼓起的效果。


要在侧视图中进行调节，细分观察效果。做出镜像的效果观察。

调节脸型鼻子和嘴上的点。和做眼睛类似，选择嘴镂空的一圈边之后将视图转动到脑袋里侧，按住z键突出处一些面。

然后调节这些面。现在要做出下巴骨，不知道应该怎么说。让这个地方的线条更加明显，这个线条要成直角。


如图红色的地方，让点往里缩，这样可以显现出下巴骨的线条。然后要制作脖子了，选择脖子位置的面删除。然后再脖子镂空的地方，选择一圈边进行突出。


突出以后在前侧视图调节点的位置，使得它们契合参考图。不要忘了在透视图中进行调节。注意途中红线的位置，这个地方要做出一个凸起。

如图增加细节，做出凸起的效果。调节，细分。

换个角度。复制出镜像来观察。

下面做耳朵，在侧视图中删除耳朵位置上的面。在侧视图中调整出一个耳朵的轮廓。选择一个边突出一小部分，然后以这个突出的部分为基础按照图中的顺序继续突出记下，形成一个耳朵的轮廓。

还要到头视图里面调整这个轮廓的位置。然后细分进行观察。

这个地方我做的比较糙。实际上应该做出耳朵里面的褶皱，但是我偷懒了。我这里简单的把耳朵的轮廓进行了延展，然后焊接，也就是把上面的框框给封起来了。不要忘了调整耳根后面的点，这个地方的点要往里收缩。

这个时候要把脑袋后面一些刚才忽略的细节给补上。基本就算完成了，然后细分一下，使一个重新定义控制点（subdivision->redefine control mesh），把模型定格在细分的状态，如图：