Direct Illumination Problems and Advantages
Direct Illumination is a term that covers the principal lighting methods used by old school rendering engines such as 3D Studio and POV. A scene consists of two types of entity: Objects and Lights. Lights cast light onto Objects, unless there is another Object in the way, in which case a shadow is left behind.
Ray Tracing:
- Can render both mathematically described objects and polygons
- Allows you to do some cool volumetric effects
- Slow
- Very sharp shadows and reflections
Shadow Volumes:
- Can be modified to render soft shadows (very tricky)
- Tricky to implement
- Very sharp shadows
- Polygons only
Z-Buffer:
- Easy to implement
- Fast (real-time)
- Sharp shadows with aliasing problems
Global Illumination Problems and Advantages
Images produced by global illumination methods can look very convincing indeed; in a league of their own, leaving old skool renderers to churn out sad cartoons. But, and it's a big 'but': 'BUT!' they are slower. Just as once you may have left your ray tracer all day, and come back to be thrilled by the image it produced, you will be doing the same here.
Radiosity:
- Very realistic lighting for diffuse surfaces
- Conceptually simple and easy to implement
- Easy to optimise with 3D hardware
- Slow
- Does not handle point sources well - nor shiny surfaces
- Always over complicated and poorly explained in books
Monte Carlo Method:
- Very, very good results.
- Can simulate pretty well any optical phenomenon
- Slow
- Slightly difficult
- Requires some cleverness to optimise
- Always over complicated and poorly explained in books
Reference:http://freespace.virgin.net/hugo.elias/radiosity/radiosity.htm
2009-08-24
2009-08-23
Food of HKU.
刚来HKU的时候，头三天的时候，吃了食堂的东西，一边吃一赞，貌似很丰盛。一个星期后，开始徘徊在食堂给出的菜单前面，10秒钟点好菜；现在三个星期，开始迷惘在菜单前面，1分钟才能决定吃什么。
香港的饮食太清淡，实在是有些受不了。抛开甜不说，盐也不够，酱油没有，辣椒，做梦才有。现在最想吃的就两样：红汤酸菜鱼+红烧仔鸡，想着就流口水。
香港的饮食太清淡，实在是有些受不了。抛开甜不说，盐也不够，酱油没有，辣椒，做梦才有。现在最想吃的就两样：红汤酸菜鱼+红烧仔鸡，想着就流口水。
有图为证：
无意间看到美国的一个博友描写美国食堂的情况，看来这是个全球问题。呵呵。
水调歌头 食堂诉苦
包子几时有，汉堡不新鲜。
我问pizza hut，为什么弄这么咸？
我欲乘船归去，又恐老板不许，上学真叫烦，
深夜梦烙饼，馋在卫生间。
2009-08-22
Study of Computer Graphic.
Reference: 3D Games - Real time rendering and software technology Volume I.
1. 仿射变换(affine transformations):旋转、缩放、平移、错切变换；
2. 法线：向量叉积；向量夹角：点积(V.W>0,θ<90;v.w=0,θ=90...)；
投影：点积（v单位向量，w对v进行投影：|x|=v.w）。
3. 双线性插值(bi-linear interpolation):顶点-->边；边-->多边形内部；
4. 模型表示方法：
- polygonal--ploygon or triangle(Problem:continuous LOD is hard, avoiding popping).
- bi-cubic parametric patches(双三次曲面）= curved quadrilaterals(曲面四边形）(Problem:smoothness between quadrilaterals,inapposite for complex object. BUT easy for LOD).
- constructive solid geometry,CSG(intersection,union,subtraction).
- spatial subdivision techniques(空间细分技术）.
- implicit representation(隐式表示）.
- Triangle chains
- LOD
6.Terrain modeling
- fractal geometry(分形几何学)
- terrain LOD: triangle bintree(三角二叉树）
- Bezier curve:
- 平行六面体
- 四个control point Pi(i=0,1,2,3);
- 基函数Bi为(1-u)^3,3u(1-u)^2,3u^2(1-u),u^3; 曲线Q(u)= ∑PiBi.
- Disadvantage: global effection when manipulating one control point; smoothness of multi Bezier connection;
- B样条：任意个控制点，任意4个一组；内在连续性；局部性（任意个控制点改变，影响4个曲线段）。
- 非均匀有理B样条（NURBS）
8. Rendering
- 视见体裁剪；
- 局部反射模型：计算顶点的光强；明暗算法：由定点得到面片的每一点的光强；
- 局部反射模型：Phong—反射光=环境光+漫反射+镜面反射，这个是Phong光照模型；
- 明暗算法：
- Gouraud—Ip=interpolation(Ia,Ib),对顶点a，b的亮度进行插值，不会有高光出现;
- Phong—对法向插值，得到插值点的Np，再求亮度。这个是Phong着色模型。
- 一般Gouraud球漫反射分量，Phong求镜面发射分量。
- 隐面剔除：Z缓冲—在搜索的同时，将Z值最小的像素写入Frame Buffer；需要x*y*n大小。
- function
- 1)common color of pixel: color of texture与局部反射模型计算得到的漫反射系数相乘；
- 2)specular color: 进行环境映射贴图，避免完全光线跟踪；沿着反射后的视见向量，在场景中寻找纹理，可倒映出环境中有光泽的物体；
- 3)凹凸纹理（bump mapping）: normal vector perturbation;
- 4)transparent:控制透明物体的不透明程度；
- bitmap-->planar, cylinder, sphere-->object
2009-08-21
Study about Fourier Transform
Reference：http://blog.csdn.net/dznlong/archive/2008/04/08/2261150%20.aspx。
1.傅里叶变换是一种逼近表示，而非精确表示；
2.选用正弦、余弦波形表示是否唯一？不是，只是为了方便。
3. 傅里叶变换的四种分类：
非周期性连续信号 --- 傅立叶变换（Fourier Transform）
周期性连续信号 --- 傅立叶级数(Fourier Series)
非周期性离散信号 --- 离散时域傅立叶变换（Discrete Time Fourier Transform）
周期性离散信号 --- 离散傅立叶变换(Discrete Fourier Transform)
4. 傅立叶变换是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的. 非无穷怎么办？扩展即可。
5. 傅里叶变换实质：将信号分解为若干个离散的、不同频率的正弦、余弦信号分量。
1.傅里叶变换是一种逼近表示，而非精确表示；
2.选用正弦、余弦波形表示是否唯一？不是，只是为了方便。
3. 傅里叶变换的四种分类：
非周期性连续信号 --- 傅立叶变换（Fourier Transform）
周期性连续信号 --- 傅立叶级数(Fourier Series)
非周期性离散信号 --- 离散时域傅立叶变换（Discrete Time Fourier Transform）
周期性离散信号 --- 离散傅立叶变换(Discrete Fourier Transform)
4. 傅立叶变换是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的. 非无穷怎么办？扩展即可。
5. 傅里叶变换实质：将信号分解为若干个离散的、不同频率的正弦、余弦信号分量。
2009-08-14
Derivation of AFX
用MS的编程也有n多年，今天突然想起afx是什么意思，网上一查，如下：
是MFC小组早期的代号，AFX，当时是指applecation freamwork,如果你的程序用到了MFC，那这个头文件是一定要包含的。
Microsoft的程序员开始试图将C++和面向对象的编程概念应用于Windows编程中，经编写出一个可以使windows编程工作更加简便的应用程序框架。他们把这个应用程序框架叫做AFX(AFX这个词来源于Application FrameWork,但奇怪的是这个词组中并没有包含"X"这个字母)。直到今天，AFX小组早已不存在了，AFX这个名称也于1994年初不再使用，但在Visual C++和MFC中，AFX的影子却随处可见，很多全局函数、结构和宏的标识符都被加上了AFX的前缀。
在九十年代初的时候OO被炒得很热,许多人以为OO是无所不能的.微软也这么认为,所以他们想搞出一套类库来封装全部的OS特性,使得程序可以在WINDOWS,OS/2,X等等任何的GUI系统上运行,结果可想而知,这个东西当然是没做出来到94年微软放弃了AFX,把AFX中已经完工的部分做了一点改进,形成了MFC,至今MFC还有LINUX版本,也算是AFX计划的一点残留吧.
是MFC小组早期的代号，AFX，当时是指applecation freamwork,如果你的程序用到了MFC，那这个头文件是一定要包含的。
Microsoft的程序员开始试图将C++和面向对象的编程概念应用于Windows编程中，经编写出一个可以使windows编程工作更加简便的应用程序框架。他们把这个应用程序框架叫做AFX(AFX这个词来源于Application FrameWork,但奇怪的是这个词组中并没有包含"X"这个字母)。直到今天，AFX小组早已不存在了，AFX这个名称也于1994年初不再使用，但在Visual C++和MFC中，AFX的影子却随处可见，很多全局函数、结构和宏的标识符都被加上了AFX的前缀。
在九十年代初的时候OO被炒得很热,许多人以为OO是无所不能的.微软也这么认为,所以他们想搞出一套类库来封装全部的OS特性,使得程序可以在WINDOWS,OS/2,X等等任何的GUI系统上运行,结果可想而知,这个东西当然是没做出来到94年微软放弃了AFX,把AFX中已经完工的部分做了一点改进,形成了MFC,至今MFC还有LINUX版本,也算是AFX计划的一点残留吧.
2009-08-10
HK Victoria Peak.
太平山就在香港大学的后面。本着锻炼身体的目的，我和leo在下午5：00做出发爬山。一出港大后，一个很陡的坡就给了我一个下马威。恩，好长时间没有锻炼身体了，一路气喘吁吁地往上爬，中间还休息了n次。估计一个小时后，到了山顶。
山顶游人如织，呵呵，可以俯瞰香港中环及维多利亚港。不过，天还没有全黑，所以没有看到夜景。而正好没有相机，也不打算等了，到山顶的McDonald吃了一点，开始下山。知道7：30才到港大，历时二个多小时。
只能用手机随便拍了照片。期待发工资，然后去买单反，O(∩_∩)O~
山顶游人如织，呵呵，可以俯瞰香港中环及维多利亚港。不过，天还没有全黑，所以没有看到夜景。而正好没有相机，也不打算等了，到山顶的McDonald吃了一点，开始下山。知道7：30才到港大，历时二个多小时。
只能用手机随便拍了照片。期待发工资，然后去买单反，O(∩_∩)O~
0x5f3759df, Magic?
昨天无意看到网上有一个开平方根的快速算法，其实是很老的一个帖子，大约在2000年出现的：
---------------------------------------------------
有人在Quake III的源代码里面发现这么一段用来求平方根的代码:
/*================SquareRootFloat================*/
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 ); //注意这一行
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
0x5f3759df？ 这是个什么东西？ 学过数值分析就知道，算法里面求平方根一般采用
的是无限逼近的方法，比如牛顿迭代法，抱歉当年我数值分析学的太烂，也讲不清楚
。简单来说比如求5的平方根，选一个猜测值比如2，那么我们可以这么算
5/2 = 2.5; 2.5+2/2 = 2.25; 5/2.25 = xxx; 2.25+xxx/2 = xxxx ...
这样反复迭代下去，结果必定收敛于sqrt(5)，没错，一般的求平方根都是这么算的
。而卡马克的不同之处在于，他选择了一个神秘的猜测值0x5f3759df作为起始，使得
整个逼近过程收敛速度暴涨，对于Quake III所要求的精度10的负三次方，只需要一
次迭代就能够得到结果。
好吧，如果这还不算牛b，接着看。
普渡大学的数学家Chris Lomont看了以后觉得有趣，决定要研究一下卡马克弄出来的
这个猜测值有什么奥秘。Lomont也是个牛人，在精心研究之后从理论上也推导出一个
最佳猜测值，和卡马克的数字非常接近, 0x5f37642f。卡马克真牛，他是外星人吗？
传奇并没有在这里结束。Lomont计算出结果以后非常满意，于是拿自己计算出的起始
值和卡马克的神秘数字做比赛，看看谁的数字能够更快更精确的求得平方根。结果是
卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的。
最后Lomont怒了，采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数
字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴
力得出的数字是0x5f375a86。
Lomont为此写下一篇论文，"Fast Inverse Square Root"。
-------------------------------------------------
于是我写了一段程序来验证，程序参考了Lomont的程序，http://www.lomont.org/Math/Papers/2003/InvSqrtCode.zip。但是号称快四倍的神秘算法，我一直未能得到很多的结果，程序表明两个算法性能差不多。奇怪中！
---------------------------------------------------------
float InvSqrtExact(float x)
{
return (float)(1.0/sqrt(x));
} // InvSqrtExact
/// "Carmack" version of fast inverse sqrt,
/// based on Newton method, 1 iteration
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1); // hidden initial guess, fast
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
// x = x*(1.5f-xhalf*x*x); // add this in for added precision, or many more...
return x;
} // InvSqrt
/// Chris Lomont version of fast inverse sqrt,
/// based on Newton method, 1 iteration, more accurate
float InvSqrt_Lomont(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f375a86 - (i>>1); // hidden initial guess, fast - LOMONT
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
// x = x*(1.5f-xhalf*x*x); // add this in for added precision, or many more...
return x;
} // InvSqrt_Lomont
/// given a function, a number of passes, and a value to test, do it
void TimeFunction(float (*func)(float), int passes, float v)
{
unsigned long used;
used = timeGetTime();
for (int pos = 0; pos < passes; pos++)
func(v);
used = timeGetTime() - used;
cout << used << " ms used for " << passes << " passes, avg ";
cout << (double)used/passes << " ms\n";
} // TimeFunction
int main(void)
{
// timing of versions
int passes = 10000000;
float v = 1.234f; // test value
cout << "Timing basic function\n";
TimeFunction(InvSqrtExact,passes,v);
cout << "Timing Carmack function\n";
TimeFunction(InvSqrt,passes,v);
cout << "Timing Lomont function\n";
TimeFunction(InvSqrt_Lomont,passes,v);
cout << "Done. By Chris Lomont 2003\n";
return 0;
} // main
---------------------------------------------------------
运算结果相差无几，难道我的程序有什么问题？
继续探索，发现同样的程序在VC6.0和VC20008下面竟然表现不同，怪事！
VC++.net 2008
-------------------------------------
Timing basic function
2187 ms used for 10000000 passes, avg 0.0002187 ms
Timing Carmack function
828 ms used for 10000000 passes, avg 8.28e-005 ms
Timing Lomont function
844 ms used for 10000000 passes, avg 8.44e-005 ms
Done. By Chris Lomont 2003
VC++ 6.0
--------------------------------------
Timing basic function
625 ms used for 10000000 passes, avg 6.25e-005 ms
Timing Carmack function
453 ms used for 10000000 passes, avg 4.53e-005 ms
Timing Lomont function
453 ms used for 10000000 passes, avg 4.53e-005 ms
Done. By Chris Lomont 2003
------------------------------------
貌似跟“using namespace std”有一定的关系，可能是sqrt的函数库版本不太一样，因为我是用VC++6.0，崩溃中......
看来0x5f3759df也不是那么神奇吧，另外，也可以看出.net程序的性能确实不怎样。
---------------------------------------------------
有人在Quake III的源代码里面发现这么一段用来求平方根的代码:
/*================SquareRootFloat================*/
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 ); //注意这一行
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
0x5f3759df？ 这是个什么东西？ 学过数值分析就知道，算法里面求平方根一般采用
的是无限逼近的方法，比如牛顿迭代法，抱歉当年我数值分析学的太烂，也讲不清楚
。简单来说比如求5的平方根，选一个猜测值比如2，那么我们可以这么算
5/2 = 2.5; 2.5+2/2 = 2.25; 5/2.25 = xxx; 2.25+xxx/2 = xxxx ...
这样反复迭代下去，结果必定收敛于sqrt(5)，没错，一般的求平方根都是这么算的
。而卡马克的不同之处在于，他选择了一个神秘的猜测值0x5f3759df作为起始，使得
整个逼近过程收敛速度暴涨，对于Quake III所要求的精度10的负三次方，只需要一
次迭代就能够得到结果。
好吧，如果这还不算牛b，接着看。
普渡大学的数学家Chris Lomont看了以后觉得有趣，决定要研究一下卡马克弄出来的
这个猜测值有什么奥秘。Lomont也是个牛人，在精心研究之后从理论上也推导出一个
最佳猜测值，和卡马克的数字非常接近, 0x5f37642f。卡马克真牛，他是外星人吗？
传奇并没有在这里结束。Lomont计算出结果以后非常满意，于是拿自己计算出的起始
值和卡马克的神秘数字做比赛，看看谁的数字能够更快更精确的求得平方根。结果是
卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的。
最后Lomont怒了，采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数
字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴
力得出的数字是0x5f375a86。
Lomont为此写下一篇论文，"Fast Inverse Square Root"。
-------------------------------------------------
于是我写了一段程序来验证，程序参考了Lomont的程序，http://www.lomont.org/Math/Papers/2003/InvSqrtCode.zip。但是号称快四倍的神秘算法，我一直未能得到很多的结果，程序表明两个算法性能差不多。奇怪中！
---------------------------------------------------------
float InvSqrtExact(float x)
{
return (float)(1.0/sqrt(x));
} // InvSqrtExact
/// "Carmack" version of fast inverse sqrt,
/// based on Newton method, 1 iteration
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1); // hidden initial guess, fast
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
// x = x*(1.5f-xhalf*x*x); // add this in for added precision, or many more...
return x;
} // InvSqrt
/// Chris Lomont version of fast inverse sqrt,
/// based on Newton method, 1 iteration, more accurate
float InvSqrt_Lomont(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f375a86 - (i>>1); // hidden initial guess, fast - LOMONT
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
// x = x*(1.5f-xhalf*x*x); // add this in for added precision, or many more...
return x;
} // InvSqrt_Lomont
/// given a function, a number of passes, and a value to test, do it
void TimeFunction(float (*func)(float), int passes, float v)
{
unsigned long used;
used = timeGetTime();
for (int pos = 0; pos < passes; pos++)
func(v);
used = timeGetTime() - used;
cout << used << " ms used for " << passes << " passes, avg ";
cout << (double)used/passes << " ms\n";
} // TimeFunction
int main(void)
{
// timing of versions
int passes = 10000000;
float v = 1.234f; // test value
cout << "Timing basic function\n";
TimeFunction(InvSqrtExact,passes,v);
cout << "Timing Carmack function\n";
TimeFunction(InvSqrt,passes,v);
cout << "Timing Lomont function\n";
TimeFunction(InvSqrt_Lomont,passes,v);
cout << "Done. By Chris Lomont 2003\n";
return 0;
} // main
---------------------------------------------------------
运算结果相差无几，难道我的程序有什么问题？
继续探索，发现同样的程序在VC6.0和VC20008下面竟然表现不同，怪事！
VC++.net 2008
-------------------------------------
Timing basic function
2187 ms used for 10000000 passes, avg 0.0002187 ms
Timing Carmack function
828 ms used for 10000000 passes, avg 8.28e-005 ms
Timing Lomont function
844 ms used for 10000000 passes, avg 8.44e-005 ms
Done. By Chris Lomont 2003
VC++ 6.0
--------------------------------------
Timing basic function
625 ms used for 10000000 passes, avg 6.25e-005 ms
Timing Carmack function
453 ms used for 10000000 passes, avg 4.53e-005 ms
Timing Lomont function
453 ms used for 10000000 passes, avg 4.53e-005 ms
Done. By Chris Lomont 2003
------------------------------------
貌似跟“using namespace std”有一定的关系，可能是sqrt的函数库版本不太一样，因为我是用VC++6.0，崩溃中......
看来0x5f3759df也不是那么神奇吧，另外，也可以看出.net程序的性能确实不怎样。
2009-08-06
2009-08-02
2009-05-14
Wise Words.
有人总结出了《新闻联播》这个节目的规律：
1.前面十分钟，国家领导人很忙，不是出国就是下乡。
2.中间十分钟，全国人民很幸福，不是致富就是丰收。
3.最后十分钟，其他国家都很惨，不是爆炸就是造反。
观后感：生活在中国真幸福!
1.前面十分钟，国家领导人很忙，不是出国就是下乡。
2.中间十分钟，全国人民很幸福，不是致富就是丰收。
3.最后十分钟，其他国家都很惨，不是爆炸就是造反。
观后感：生活在中国真幸福!
订阅：
博文 (Atom)