<转>C/C++中枚举类型(enum)

如果一个变量你需要几种可能存在的值，那么就可以被定义成为枚举类型。之所以叫枚举就是说将变量或者叫对象可能存在的情况也可以说是可能的值一一例举出来。

　　举个例子来说明一吧，为了让大家更明白一点，比如一个铅笔盒中有一支笔，但在没有打开之前你并不知道它是什么笔，可能是铅笔也可能是钢笔，这里有两种可能，那么你就可以定义一个枚举类型来表示它！

enum box{pencil,pen};//这里你就定义了一个枚举类型的变量叫box，这个枚举变量内含有两个元素也称枚举元素在这里是pencil和pen，分别表示铅笔和钢笔。

　　这里要说一下，如果你想定义两个具有同样特性枚举类型的变量那么你可以用如下的两种方式进行定义！

enum box{pencil,pen};

enum box box2;//或者简写成box box2;

　　再有一种就是在声明的时候同时定义。

enum {pencil,pen}box,box2; //在声明的同时进行定义！

　　枚举变量中的枚举元素系统是按照常量来处理的，故叫枚举常量，他们是不能进行普通的算术赋值的，(pencil=1;)这样的写发是错误的，但是你可以在声明的时候进行赋值操作！

enum box{pencil=1,pen=2};

但是这里要特别注意的一点是，如果你不进行元素赋值操作那么元素将会被系统自动从0开始自动递增的进行赋值操作，说到自动赋值，如果你只定义了第一个那么系统将对下一个元素进行前一个元素的值加1操作，例如

enum box{pencil=3,pen};//这里pen就是4系统将自动进行pen=4的定义赋值操作！

　　前面说了那么多，下面给出一个完整的例子大家可以通过以下的代码的学习进行更完整的学习！

#include
using namespace std;

void main(void)
{
enum egg {a,b,c};
enum egg test; //在这里你可以简写成egg test;

test = c; //对枚举变量test进行赋予元素操作，这里之所以叫赋元素操作不叫赋值操作就是为了让大家明白枚举变量是不能直接赋予算数值的，例如(test=1;)这样的操作都是不被编译器所接受的，正确的方式是先进行强制类型转换例如(test = (enum egg) 0;)！

if (test==c)
{
cout <<"枚举变量判断:test枚举对应的枚举元素是c" << endl;
}

if (test==2)
{
cout <<"枚举变量判断:test枚举元素的值是2" << endl;
}

cout << a << "|" << b << "|" << test <
test = (enum egg) 0; //强制类型转换
cout << "枚举变量test值改变为:" << test < cin.get();
}

　　看到这里要最后说一个问题，就是枚举变量中的枚举元素(或者叫枚举常量)在特殊情况下是会被自动提升为算术类型的！

using namespace std;

void main(void)
{
enum test {a,b};
int c=1+b; //自动提升为算术类型
cout << c < cin.get();
}

<转>c++ static用法总结

static关键字是C, C++中都存在的关键字, 它主要有三种使用方式, 其中前两种只指在C语言中使用, 第三种在C++中使用(C,C++中具体细微操作不尽相同, 本文以C++为准).
(1)局部静态变量
(2)外部静态变量/函数
(3)静态数据成员/成员函数

下面就这三种使用方式及注意事项分别说明
 一、局部静态变量
在C/C++中, 局部变量按照存储形式可分为三种auto, static, register
与auto类型(普通)局部变量相比, static局部变量有三点不同

1. 存储空间分配不同
auto类型分配在栈上, 属于动态存储类别, 占动态存储区空间, 函数调用结束后自动释放, 而static分配在静态存储区, 在程序整个运行期间都不释放. 两者之间的作用域相同, 但生存期不同.

2. static局部变量在所处模块在初次运行时进行初始化工作, 且只操作一次3. 对于局部静态变量, 如果不赋初值, 编译期会自动赋初值0或空字符, 而auto类型的初值是不确定的. (对于C++中的class对象例外, class的对象实例如果不初始化, 则会自动调用默认构造函数, 不管是否是static类型)

 特点: static局部变量的”记忆性”与生存期的”全局性”
所谓”记忆性”是指在两次函数调用时, 在第二次调用进入时, 能保持第一次调用退出时的值.

示例程序一

#include
using namespace std;
void staticLocalVar()
{
   static int a = 0; // 运行期时初始化一次, 下次再调用时, 不进行初始化工作   cout<<"a="<// 第一次调用, 输出a=0  staticLocalVar(); // 第二次调用, 记忆了第一次退出时的值, 输出a=1  return 0;
}

应用:
利用”记忆性”, 记录函数调用的次数(示例程序一)
利用生存期的”全局性”, 改善”return a pointer / reference to a local object”的问题. Local object的问题在于退出函数, 生存期即结束,. 利用static的作用, 延长变量的生存期.

示例程序二:

// IP address to string format
// Used in Ethernet Frame and IP Header analysis
const char * IpToStr(UINT32 IpAddr)
{
static char strBuff[16]; // static局部变量, 用于返回地址有效
const unsigned char *pChIP = (const unsigned char *)&IpAddr;
sprintf(strBuff, "%u.%u.%u.%u", pChIP[0], pChIP[1], pChIP[2], pChIP[3]);
return strBuff;
}

 注意事项:
1. “记忆性”, 程序运行很重要的一点就是可重复性, 而static变量的”记忆性”破坏了这种可重复性, 造成不同时刻至运行的结果可能不同.

2. “生存期”全局性和唯一性. 普通的local变量的存储空间分配在stack上, 因此每次调用函数时, 分配的空间都可能不一样, 而static具有全局唯一性的特点, 每次调用时, 都指向同一块内存, 这就造成一个很重要的问题 ---- 不可重入性!

这样在多线程程序设计或递归程序设计中, 要特别注意这个问题.

 下面针对示例程序二, 分析在多线程情况下的不安全性.(为方便描述, 标上行号)
① const char * IpToStr(UINT32 IpAddr)
② {
③ static char strBuff[16]; // static局部变量, 用于返回地址有效
④ const unsigned char *pChIP = (const unsigned char *)&IpAddr;
⑤ sprintf(strBuff, "%u.%u.%u.%u", pChIP[0], pChIP[1], pChIP[2], pChIP[3]);
⑥ return strBuff;
⑦ }

假设现在有两个线程A,B运行期间都需要调用IpToStr()函数, 将32位的IP地址转换成点分10进制的字符串形式. 现A先获得执行机会, 执行IpToStr(), 传入的参数是0x0B090A0A, 顺序执行完应该返回的指针存储区内容是:”10.10.9.11”, 现执行到⑥时, 失去执行权, 调度到B线程执行, B线程传入的参数是0xA8A8A8C0, 执行至⑦, 静态存储区的内容是192.168.168.168. 当再调度到A执行时, 从⑥继续执行, 由于strBuff的全局唯一性, 内容已经被B线程冲掉, 此时返回的将是192.168.168.168字符串, 不再是10.10.9.11字符串.

 二、外部静态变量／函数
在C中 static有了第二种含义：用来表示不能被其它文件访问的全局变量和函数。, 但为了限制全局变量/函数的作用域, 函数或变量前加static使得函数成为静态函数。但此处“static”的含义不是指存储方式，而是指对函数的作用域仅局限于本文件(所以又称内部函数)。注意此时, 对于外部(全局)变量, 不论是否有static限制, 它的存储区域都是在静态存储区, 生存期都是全局的. 此时的static只是起作用域限制作用, 限定作用域在本模块(文件)内部.
使用内部函数的好处是：不同的人编写不同的函数时，不用担心自己定义的函数，是否会与其它文件中的函数同名。

示例程序三:

 //file1.cpp
static int varA;
int varB;
extern void funA()
{
……
}
static void funB()
{
……
}
//file2.cpp
extern int varB; // 使用file1.cpp中定义的全局变量
extern int varA; // 错误! varA是static类型, 无法在其他文件中使用
extern vod funA(); // 使用file1.cpp中定义的函数
extern void funB(); // 错误! 无法使用file1.cpp文件中static函数

 三、静态数据成员／成员函数(C++特有)
C+ +重用了这个关键字，并赋予它与前面不同的第三种含义：表示属于一个类而不是属于此类的任何特定对象的变量和函数. 这是与普通成员函数的最大区别, 也是其应用所在, 比如在对某一个类的对象进行计数时, 计数生成多少个类的实例, 就可以用到静态数据成员. 在这里面, static既不是限定作用域的, 也不是扩展生存期的作用, 而是指示变量/函数在此类中的唯一性. 这也是”属于一个类而不是属于此类的任何特定对象的变量和函数”的含义. 因为它是对整个类来说是唯一的, 因此不可能属于某一个实例对象的. (针对静态数据成员而言, 成员函数不管是否是static, 在内存中只有一个副本, 普通成员函数调用时, 需要传入this指针, static成员函数调用时, 没有this指针. )

 class EnemyTarget {
public:
EnemyTarget() { ++numTargets; }
EnemyTarget(const EnemyTarget&) { ++numTargets; }
~EnemyTarget() { --numTargets; }
static size_t numberOfTargets() { return numTargets; }
bool destroy(); // returns success of attempt to destroy EnemyTarget object
private:
static size_t numTargets; // object counter};
// class statics must be defined outside the class;
// initialization is to 0 by default
size_t EnemyTarget::numTargets;

 在这个例子中, 静态数据成员numTargets就是用来计数产生的对象个数的.
另外, 在设计类的多线程操作时, 由于POSIX库下的线程函数pthread_create()要求是全局的, 普通成员函数无法直接做为线程函数, 可以考虑用Static成员函数做线程函数.

<转>堆与栈的区别

一、预备知识—程序的内存分配

一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。

二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456在常量区，p3在栈上。
static int c =0； 全局（静态）初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
}
分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。

二、堆和栈的理论知识

2.1申请方式
stack:
由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = (char *)malloc(10);
但是注意p1、p2本身是在栈中的。

2.2 申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，
会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。

2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。

2.5堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

2.6存取效率的比较
char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
} 

对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al

第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到edx中，在根据edx读取字符，显然慢了。

2.7小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆和栈的区别主要分：
操作系统方面的堆和栈，如上面说的那些，不多说了。
还有就是数据结构方面的堆和栈，这些都是不同的概念。这里的堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权；栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈，堆栈的说法是连起来叫，但是他们还是有很大区别的，连着叫只是由于历史的原因。

指向数组的指针

举例：int (*p)[10];
注意和int *p[10]；的区别是后者是一个有10个元素的数组　用来存放int类型的指针(int*)。

用法举例：

int a[2][2] = {{1,2},{3,4}}; 
int (*p)[2] = a; 
printf("%d\n", p[1][0]);

结果是3

如果将第二行的int (*p)[2] 改为 intint (*p)[3], 则会出现编译错误　“ cannot convert from 'int [2][2]' to 'int (*)[3]'。所以一般指针维数需要和数组对应，但是可以做指针强制转换：

int a[2][2] = {{1,2},{3,4}};
int (*p)[3] = (int (*)[3])a;
printf("%d\n", p[1][0]);

结果是4

以上定义的是一个二维数组指针, n维数组指针都可以按 (*p)[a1][a2]...[a(n-1)]定义。

P.S.
多维数组初始化可以用一个一维数组初始化，如上面的初始化用下面这句也可以：

int a[2][2] = {1,2,3,4};

OpenGL, GLSL, DirectX, HLSL中的矩阵存储形式

OpenGL:  按列存储矩阵(column-major)。调用API形成的矩阵用来和一个列向量相乘，矩阵在左，列向量在右
GLSL:  　存储方式和OpenGL相同(column-major)
DirectX:    按行存储矩阵(row-major)。调用API形成的矩阵用来和一个行向量相乘，矩阵在右，行向量在左
HLSL：　存储方式和DirectX相反(column-major)

因此，若HLSL的矩阵也是用来右乘行向量，则应将DX API构造的矩阵做Transpose，这样数学上HLSL会将Transpose后的矩阵视为 和DX API构造的矩阵是同一个矩阵，但是实际数值的存储顺序不同。若用来将矩阵左乘列向量，则可以不必做Transpose。

因此，一般的传入shader的操作是原封不动的将用来存储矩阵的array导入shader。但是如果是用的effect system里的setMatrix(),　则会先自动将矩阵由row-major改为colunn-major存储，再将其导入shader。这种情况下则无需在导入前手动Transpose 矩阵。

Bump Mapping [转]

Bump mapping is very much like Texture Mapping. However, where Texture Mapping added colour to a polygon, Bump Mapping adds, what appears to be surface roughness. This can have a dramatic effect on the look of a polygonal object. Bump Mapping can add minute detail to an object which would otherwise require a large number of polygons. Note that the polygon is still physically flat, but appears to a be bumpy.

Take a look at the cube on the left. If you look closely, you can see lots of detail on it. It looks as if it must have been made from millions of tiny polygons, but is made from just 6. You might ask how this differs from Texture Mapping. The difference is that a Bump Map is a Texture Map that responds to the direction of the light.

The theory behind Bump Mapping

Take a close look at a rough surface. From a distance, the only way you know it is rough is by the fact that it's brightness changes up and down across it's surface. Your brain can pick out these bright and dark patterns and interpret them as bumps on the surface.

The little picture on the left illustrates this. You see what looks like an embossed surface. Some rectangles and letters have been pressed into it, but if you touch it, it just feels like the glass of your monitor.Nothing more has been done than change the brightness if the image in just the right places, your brain does the rest. This technique can be used to add real feeling to a polygon.

So how did I know which bits to make bright, and which to make dark? It's easy. Most people spend their lives in an environment where the main light source is above them (except us spods of course, whose main light source comes from the monitor). So surfaces angled upwards tend to be brightly lit, and downward inclined surfaces tend to be darker. Therefore it follows that if your eyes see light and dark areas on an object, they will interpret them as bumps; lighter bits it takes as up-facing, and darker bits it takes as down-facing. So, I just coloured the lines on the image accordingly.

As if you needed any more evidence, here is exactly the same image, but rotated 180 degrees. It appears to be the inverse of the previous one. Those areas that appeared to be pushed in, now seem to have popped out, and vice-versa.

Now, your brain is not entirely stupid. If you had visual evidence that the inverted image was lit from underneath, your brain would again interpret it as the first image. Infact, if you stare, and think hard enough about a light source comming from the bottom right, you can make that happen.

What is a Bump Map

A bump map is very much like a texture map. However, rather than containing colours, it contains bumps. The most common way to represent bumps is by the height field method. A greyscaled texture map is used, where the brightness of each pixel represents how much it sticks out from the surface (see image on right). This is a very convenient way to store a bump map, and it's simple to make. How this information is used by the renderer will become apparent later.

Of course, you needn't limit yourself to such simple patterns. You can have wood, stone, peeling paint, anything you want.

So how's it done

Bump mapping is an extension of the Phong Shading technique. In Phong Shading, the surface normal was interpolated over the polygon, and that vector was used to calculate the brightness of that pixel. When you add bump mapping, you are altering the normal vector slightly, based on information in the bump map. Adjusting the normal vector causes changes in the brightness of the pixels in the polygon. Simple.

Now, there are several ways of acheving this. I have never actually programmed real phong shading or bump mapping, only the fast versions (which work very nicely thankyou), so I am kind of making this next bit up as I go along. Bare with me.

OK, so we need a method for converting the height information on the bump map into vector adjustment information for the phong shader. This is not so hard to do, but it might be tricky to explain.

OK, so first you'll need a way to convert the bumps on the bumpmap into little vectors, one vector for each pixel. Take a look at the zoomed-in view of a bumpmap on the left. The lighter pixels stick out more than the darker ones. Get the picture? Now, for each pixel, a vector must be computed. These vectors represent the incline of the surface at that pixel. The picture on the right represents this. The little red vectors point in the 'downhill' direction.

There are many ways to calculate these vectors. Some are more accurate than others, but it depends exactly what you mean by accurate. One of the most common methods is to calculate the X and Y gradient at that pixel:

x_gradient = pixel(x-1, y) - pixel(x+1, y)
 y_gradient = pixel(x, y-1) - pixel(x, y+1)

With these two gradients, you will now need to adjust the normal vector of the polygon at that point.

 

Here is the polygon, with it's origional normal vector, n. Also shown are the two vectors which are going to be used to adjust the normal vector for this pixel. The two vectors must be aligned with the bumpmap for the polygon to be rendered correctly. I.E. the vectors are parallel to the axes of the bumpmap.

On the right are the bump map, and the polygon. Both pictures show the U and V vectors.

Now you can see the new Normal vector after adjustment. The adjustment is simply:

New_Normal = Normal + (U * x_gradient) + (V * y_gradient)

With this New_Normal vector, you can procede to calculate the brightness of the polygon at that point, using the usual phong shading technique.



From: http://freespace.virgin.net/hugo.elias/graphics/x_polybm.htm

Texture types in OpenGL

GL_TEXTURE_1D: Images in this texture all are 1-dimensional. They have width, but no height or depth.

GL_TEXTURE_2D: Images in this texture all are 2-dimensional. They have width and height, but no depth.

GL_TEXTURE_3D: Images in this texture all are 3-dimensional. They have width, height, and depth.

GL_TEXTURE_RECTANGLE: The image in this texture (only one image. No mipmapping) is 2-dimensional. Texture coordinates used for these textures are not normalized.

GL_TEXTURE_BUFFER: The image in this texture (only one image. No mipmapping) is 1-dimensional. The storage for this data comes from a Buffer Object.

GL_TEXTURE_CUBE_MAP: There are exactly 6 distinct sets of 2D images, all of the same size. They act as 6 faces of a cube.

GL_TEXTURE_1D_ARRAY: Images in this texture all are 1-dimensional. However, it contains multiple sets of 1-dimensional images, all within one texture. The array length is part of the texture's size.

GL_TEXTURE_2D_ARRAY Array: Images in this texture all are 2-dimensional. However, it contains multiple sets of 2-dimensional images, all within one texture. The array length is part of the texture's size.

GL_TEXTURE_2D_MULTISAMPLE: The image in this texture (only one image. No mipmapping) is 2-dimensional. Each pixel in these images contains multiple samples instead of just one value.

GL_TEXTURE_2D_MULTISAMPLE_ARRAY: Combines 2D array and 2D multisample types. No mipmapping.

From: http://www.opengl.org/wiki/Texture

Texture Address Mode (Clamp, Wrap)

1. Clamp
这个寻址模式让所有的纹理坐标截取到[0,1]范围内，所有小于0的坐标截取到0，大于1的截取到1。
结果是，超出[0,1] 范围的纹理坐标的所有像素的颜色为纹理边缘的颜色。

2. Wrap
使用这个模式，显卡会从坐标加上或减去1直到坐标仍回到[0,1]范围。
这会导致原始纹理被复制。

下图是两种addressing mode的比较，左为Clamp, 右为Wrap。

纹理过滤模式中的Bilinear、Trilinear以及Anistropic Filtering <转>

1、 为什么在纹理采样时需要texture filter（纹理过滤）。

我们的纹理是要贴到三维图形表面的，而三维图形上的pixel中心和纹理上的texel中心并不一至（pixel不一定对应texture上的采样中心texel），大小也不一定一至。当纹理大于三维图形表面时，导至一个像素被映射到许多纹理像素上;当维理小于三维图形表面时，许多个象素都映射到同一纹理。

当这些情况发生时，贴图就会变得模糊或发生错位，马赛克。要解决此类问题，必须通过技术平滑texel和pixel之间的对应。这种技术就是纹理滤波。

不同的过滤模式，计算复杂度不一样，会得到不同的效果。过滤模式由简单到复杂包括：Nearest Point Sampling（最近点采样），Bilinear（双线性过滤）、Trilinear（三线性过滤）、Anisotropic Filtering（各向异性过滤）。

在了解这些之前，有必要了解什么是MipMap和什么时各向同性，各向异性。

2、 什么是MipMap?

Mipmap由Lance Williams 在1983的一篇文章“Pyramidal parametrics”中提出。Wiki中有很详细的介绍( http://en.wikipedia.org/wiki/Mipmap ) . 比如一张256X256的图，在长和宽方向每次减少一倍，生成：128X128,64X64,32X32,16X16,8X8,4X4,2X2,1X1，八张图，组成MipMap,如下图示。

Mipmap早已被硬件支持，硬件会自动为创建的Texture生成mipmap的各级。在D3D的API：CreateTexture中有一个参数levels，就是用于指定生成mipmap到哪个级别，当不指定时就一直生成到1X1。

3、 什么是各向同性和各向异性？

当需要贴图的三维表面平行于屏幕(viewport)，则是各向同性的。当要贴图的三维表面与屏幕有一定角度的倾斜，则是各向异性的。

也可以这样理解，当一个texture贴到三维表面上从Camera看来没有变形，投射到屏幕空间中后U方向和V方向比例仍然是一样的，便可以理解成各向同性。反之则认为是各向异性。

4、 Nearest Point Sampling（最近点采样）

这个最简单，每个像素的纹理坐标，并不是刚好对应Texture上的一个采样点texel，怎么办呢？最近点采样取最接近的texel进行采样。

当纹理的大小与贴图的三维图形的大小差不多时，这种方法非常有效和快捷。如果大小不同，纹理就需要进行放大或缩小，这样，结果就会变得矮胖、变形或模糊。

5、 Bilinear（双线性过滤）

双线性过滤以pixel对应的纹理坐标为中心，采该纹理坐标周围4个texel的像素，再取平均，以平均值作为采样值。

双线性过滤像素之间的过渡更加平滑，但是它只作用于一个MipMap Level,它选取texel和pixel之间大小最接近的那一层MipMap进行采样。当和pixel大小匹配的texel大小在两层Mipmap level之间时，双线性过滤在有些情况效果就不太好。于是就有了三线性过滤。

6、 Trilinear（三线性过滤）

三线性过滤以双线性过滤为基础。会对pixel大小与texel大小最接近的两层Mipmap level分别进行双线性过滤，然后再对两层得到的结果进生线性插值。

三线性过滤在一般情况下效果非常理想了。但是到目前为止，我们均是假设是texture投射到屏幕空间是各向同性的。但是当各向异性的情况时，效果仍然不理想，于是产生了Anisotropic Filtering（各向异性过滤）。

7、 Anisotropic Filtering（各向异性过滤）

先看效果，左边的图采用三线性过滤，右边的图采用各向异性过滤。

各向同性的过滤在采样的时候，是对正方形区域里行采样。各向异性过滤把纹理与屏幕空间的角度这个因素考虑时去。简单地说，它会考滤一个pixel(x:y=1:1)对应到纹理空间中在u和v方向上u和v的比例关系，当u:v不是1:1时，将会按比例在各方向上采样不同数量的点来计算最终的结果(这时采样就有可能是长方形区域)。

我们一般指的Anisotropic Filtering(AF)均是基于三线过滤的Anisotropic Filtering，因此当u:v不为1:1时，则Anisotropic Filtering比Trilinear需要采样更多的点，具体要采多少，取决于是多少X的AF,现在的显卡最多技持到16X AF。

当开启16X AF的时候，硬件并不是对所有的texture采样都用16X AF，而是需要先计算屏幕空间与纹理空间的夹角(量化后便是上面所说的u:v)，只有当夹角大到需要16X时，才会真正使用16X.

如果想了解AF的实现原理，可以查阅此篇Paper: “Implementing an anisotropic texture filter”. 现在AF都是硬件实现，因此只有少数人才清楚AF就尽是怎样实现了（其实细节我也没搞清楚），其实完全可以由Pixel Shader来实现AF，当然性能和由硬件做是没得比的。

8、 各过滤模式性能比较。

 下表是各种过滤模式采一个pixel需要sample的次数：

	Sample Number
Nearest Point Sampling	1
Bilinear	4
Trilinear	8
Anisotropic Filtering 4X	32
Anisotropic Filtering 16X	128

  

Anisotropic Filtering 16X效果最好，但是显卡Performance会下降很多，当然也是测试你手中显卡Texture Unit的好方法。如果你觉得你的显卡够牛，那么就把AA和AF都打到最高再试试吧：）

<转>导数和微分的区别

1、一元函数，可导就是可微，没有本质区别，完全是一个意思的两种表述：
   可导强调的是曲线的斜率、变量的牵连变化率；
   可微强调的是可以分割性、连续性、光滑性。

   dx、dy: 可微性；  dy/dx: 可导性

   dy = (dy/dx)dx，  在工程应用中,变成： Δy = (dy/dx)Δx  

     这就是可导、可微之间的关系：
   可导 = 可微 = Differentiable。 
   导数 = 微分 = Differentiation，Derivative
     不可导 = 不可微 = Undifferentiable

  【说穿了，可以说是中文在玩游戏，也可以说中文概念更精确性】

   
2、二元和二元以上的多元函数有偏导(Partial Differentiation)的概念， 
   有全导数、全微分(Total Differentiatin)的概念。
  【说穿了，可以说也是中文在玩游戏，也可以说中文概念更有思辩性】
   多元函数有方向导数(Directional Differentiation/Derivative)的概念

   一元函数，无所谓偏导、全导，也没有全微分、偏微分、方向导数的概念。


3、对于多元函数，沿任何坐标轴方向的导数都是偏导数，
   a、沿任何特定方向的导数都是方向导数。
   b、方向导数取得最大值的方向导数就是梯度(Gradient)。
   c、英文中有全导数的概念(Total Differentian),只是我们的教学不太习惯
      这样称呼，我们习惯称为全微分，其实是完全等同的意思。

   一元函数没有这些概念。偏导就是全导，全导就是偏导。

4、dx、dy、du都是微分，只有在写成du=(∂f/∂x)dx + (∂f/∂y)dy时，
   du才是全微分，而dx、dy就是偏微分，只是我们不习惯这样讲罢了。 
   而∂f、∂x、∂y还是微分的概念，是df、dx、dy在多元函数中的变形。

x的单独变化会引起u的变化，du=(∂f/∂x)dx
y的单独变化会引起u的变化，du=(∂f/∂y)dy
其中的 ∂f/∂x、∂f/∂y 就是二元函数f分别对x,y的偏导数。
∂f/∂x 就是由于x的变化单独引起的f的变化率，部分原因引起，为“偏”；
∂f/∂y 就是由于y的变化单独引起的f的变化率，部分原因引起，为“偏”。

x、y同时变化，引起u的变化是：
du=(∂f/∂x)dx + (∂f/∂y)dy
这就是全微分，所有原因共同引起为“全”。

总而言之，言而总之：
对一元函数，可导与可微没有本质区别；
对多元函数，可微是指所有方向可以偏导，可微的要求更高。

<转>文本文件和二进制文件的区别

从文件编码的方式来看，文件可分为ASCII码文件和二进制码文件两种。

ASCII文件也称为文本文件，这种文件在磁盘中存放时每个字符对应一个字节，用于存放对应的ASCII码。例如，数5678的存储形式为：

ASC码:    00110101 00110110 00110111 00111000

                        ↓ 　　　    ↓　　　     ↓ 　　　    ↓

十进制码：   5　　　　  6　　　　  7　　　　  8

共占用4个字节。ASCII码文件可在屏幕上按字符显示，例如源程序文件就是ASCII文件，用DOS命令TYPE可显示文件的内容。由于是按字符显示，因此能读懂文件内容。

二进制文件是按二进制的编码方式来存放文件的。例如，数5678的存储形式为：00010110 00101110只占二个字节。二进制文件虽然也可在屏幕上显示，但其内容无法读懂。C系统在处理这些文件时，并不区分类型，都看成是字符流，按字节进行处理。 输入输出字符流的开始和结束只由程序控制而不受物理符号(如回车符)的控制。因此也把这种文件称作“流式文件”。

一个文件可以以文本模式或二进制模式打开，这两种的区别是：在文本模式中回车被当成一个字符'\n'，而二进制模式认为它是两个字符0x0D,0x0A；如果在文件中读到0x1B，文本模式会认为这是文件结束符，也就是二进制模型不会对文件进行处理，而文本方式会按一定的方式对数据作相应的转换。

[转] Phong lighting model

From wikipedia:

Phong reflection is an empirical model of local illumination. It describes the way a surface reflects light as a combination of the diffuse reflection of rough surfaces with the specular reflection of shiny surfaces. It is based on Bui Tuong Phong's informal observation that shiny surfaces have small intense specular highlights, while dull surfaces have large highlights that fall off more gradually. The reflection model also includes an ambient term to account for the small amount of light that is scattered about the entire scene.

For each light source in the scene, we define the components is and id as the intensities (often as RGB values) of the specular and diffuse components of the light sources respectively. A single term ia controls the ambient lighting; it is sometimes computed as a sum of contributions from all light sources.

For each material in the scene, we define:

ks: specular reflection constant, the ratio of reflection of the specular term of incoming light

kd: diffuse reflection constant, the ratio of reflection of the diffuse term of incoming light (Lambertian reflectance)

ka: ambient reflection constant, the ratio of reflection of the ambient term present in all points in the scene rendered

α: is a shininess constant for this material, which is larger for surfaces that are smoother and more mirror-like. When this constant is large the specular highlight is small.

We further define lights as the set of all light sources, L as the direction vector from the point on the surface toward each light source, N as the normal at this point on the surface, R as the direction that a perfectly reflected ray of light would take from this point on the surface, and V as the direction pointing towards the viewer (such as a virtual camera).

Note L, N, R, V are all unit vecters.

Then the Phong reflection model provides an equation for computing the shading value of each surface point Ip:

The diffuse term is not affected by the viewer direction (V). The specular term is large only when the viewer direction (V) is aligned with the reflection direction R. Their alignment is measured by the α power of the cosine of the angle between them. The cosine of the angle between the normalized vectors R and V is equal to their dot product. When α is large, in the case of a nearly mirror-like reflection, the specular highlight will be small, because any viewpoint not aligned with the reflection will have a cosine less than one which rapidly approaches zero when raised to a high power.

When we have color representations as RGB values, this equation will typically be calculated separately for R, G and B intensities.

Although the above formulation is the common way of presenting the Phong model, a particular term in the sum should only be included if it is positive, i.e. the equation is formally incorrect.

Therefore, in the above fomulation, (Lm·N) should be exactly max(Lm·N, 0) and similarly (Rm·V) should be max(Rm·V, 0).

Normal transformation matrix的推导

normal的transformation matrixh和vertex的transformation matrix并不相同。以下是推导：

vertex上的normal可以定义一个平面,  顶点在平面上，则有(nx, ny, nz, q)*(x0, yo, zo, w)' = 0。当顶点做完model-view transformation后，M为model-view transfornation matrix, 则有(nx, ny, nz, q)*inverse(M)*M*(x0, yo, zo, w)' = 0。变换后的(nx, ny, nz, q)为(nx', ny', nz', q') = (nx, ny, nz, q)*inverse(M), 由于我们并不需要q, 变换后的normal可以写成(nx', ny', nz'）＝ (nx, ny, nz)*inverse(Mu)，Mu为M的左上３×３submatrix。最后对(nx', ny', nz')做normalization使其变为unit vector完成变换。

由此得出若使用row vector表示normal则transformation matrix为inverse(Mu)，使用column vector表示normal则transformation matrix为inverse(Mu)'

Projective Texture Mapping

Projective Texture Mapping是将texture用投影的方法投射到物体上的一种texture mapping方法。从顶点到texture坐标的变换如下图右所示：

在OpenGL里，实现projective mapping可以用两种texture生成方法, object linear和eye linear,　其变换矩阵分别如下图：

Object Linear Texgen

Eye Linear Texgen

Object Linear Texgen左乘的对象是顶点在object space的坐标，Eye Linear Texgen左乘的对象则是顶点在view space的坐标，一般使用Eye Linear Texgen来实现不同object coordinate system的物体的统一投影效果（如shadow mapping)。用OpenGL的实现Eye Linear Texgen，如果用R表示 [0,1] range transformation matrix，则需要将R*Pp*Vp的四个row vector分别设为s,t,r,q的eye plane。

最后发两张NV教学文档里的效果图：

 

glTexGen中object linear和eye linear的区别

根据red book的解释，在eye linear模式下，t = p1' * Xe + p2' * Ye + p3' * Ze + p4' ，Xe,Ye,Ze是顶点在viewing space的坐标， 故有(Xe, Ye, Ze, We) = M * (x0, y0, z0, w0)，x0 , y0 , z0 ,w0为顶点在object space的坐标。而( p1' , p2', p3', p4') = (p1, p2 , p3 ,p4)*inverse(M)，这样看来 t =  (p1, p2, p3, p4) * (x0 , y0 , z0 ,w0), 生成的texture coordinates和在object linear模式下完全相同。怎么会这样呢？

实际上，在( p1' , p2', p3', p4') = (p1, p2 , p3 ,p4)*inverse(M)中，M为调用glTexGen时的Model-view矩阵，在生成坐标过程中不会再变化，而(Xe , Ye , Ze , We) = M * (x0 , y0 , z0 ,w0)中的M则是定义(x0 , y0 , z0 ,w0)时当前的Model-view矩阵，在定义不同顶点时Model-view矩阵可能会有所不同。只有在调用glTexGen后Model-view矩阵没有变化的情况下，在两种模式下生成的texture coordinates相同。简单的说，object linear模式中的纹理坐标跟据顶点的object coordinate(也就是glVertex定义的坐标)做一个固定的变换而生成，而eye linear模式则是把顶点变换到当先的viewing space，根据得到的viewing coordinate做一个固定的变换而生成。

关于空集

空集不含任何元素，Ø 是空集，｛Ø｝不是空集，因为｛Ø｝含有元素Ø

对任意集合 A，空集是 A 的子集；
∀A: Ø ⊆ A

对任意集合 A, 空集和 A 的并集为 A：
∀A: A ∪ Ø = A

对任意集合 A, 空集和 A 的交集为空集：
∀A: A ∩ Ø = Ø

对任意集合 A, 空集和 A 的笛卡尔积为空集：
∀A: A × Ø = Ø

空集的唯一子集是空集本身：
∀A: A ⊆ Ø ⇒ A = Ø

空集的元素个数（即它的势）为零；特别的，空集是有限的：
Card(Ø) = 0
 
 空集是任何非空集合的真子集。.Ø  只有一个子集，没有真子集。｛Ø｝有两个子集，一个是Ø ， 一个是它本身

<转>malloc和calloc的区别

函数malloc()和calloc()都可以用来动态分配内存空间,但两者稍有区别。

malloc()函数有一个参数,即要分配的内存空间的大小:

void*malloc(size_tsize);

calloc()函数有两个参数,分别为元素的数目和每个元素的大小,这两个参数的乘积就是要分配的内存空间的大小。

void*calloc(size_tnumElements,size_tsizeOfElement);

如果调用成功,函数malloc()和函数calloc()都将返回所分配的内存空间的首地址。

函数malloc()和函数calloc() 的主要区别是前者不能初始化所分配的内存空间,而后者能。如果由malloc()函数分配的内存空间原来没有被使用过，则其中的每一位可能都是0;反之, 如果这部分内存曾经被分配过,则其中可能遗留有各种各样的数据。也就是说，使用malloc()函数的程序开始时(内存空间还没有被重新分配)能正常进 行,但经过一段时间(内存空间还已经被重新分配)可能会出现问题。

函数calloc() 会将所分配的内存空间中的每一位都初始化为零,也就是说,如果你是为字符类型或整数类型的元素分配内存,那麽这些元素将保证会被初始化为0;如果你是为指 针类型的元素分配内存,那麽这些元素通常会被初始化为空指针;如果你为实型数据分配内存,则这些元素会被初始化为浮点型的零。

<转>如何在VS2008中编译64位程序

安装64位操作系统不是编译64位程序的必要条件，关键是要装64位程序的编译器。虽然标题写着如何在VS2008中编译，但其实2005也是类似。

1. 选择“Build” – “Configuration Manager”菜单，打开配置管理器。点击新建解决方案平台。




2. 选择“x64”平台，点击确定按钮。



3. 这时候配置管理器中的平台已经改成刚才选择的x64了，这时候编译出来的就是64位程序了。可以在工具栏的平台下拉框中快速切换目标平台。



4. 如果在选择平台的下拉列表里找不到x64，可能是没有安装x64编译支持。在VS安装程序里再装上就可以了。



一点心得：

x64编译环境下的程序所依赖的库文件也必须是x64下编译而成，x64程序不能调用32位库，否则链接时会报错。

工程属性－配置属性－C/C++. 检测64位可移植问题设为　是
工程属性－配置属性－链接器－高级，目标计算机设为　MachineX64

另外将工程设置为x64平台后需要重新添加include，lib等路径。x64与win32是分开设置的。

<转>最接近点对问题

　　这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n²)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。

    这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S₁和S₂，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S₁和S₂的最接近点对，如何求得原集合S中的最接近点对，因为S₁和S₂的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S₁中或都在S₂中，则问题很容易解决。但是，如果这2个点分别在S₁和S₂中，则对于S₁中任一点p，S₂中最多只有n/2个点与它构成最接近点对的候选者，仍需做n²/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n²)。整个算法所需计算时间T(n)应满足:　

T(n)=2T(n/2)+O(n²)

    它的解为T(n)=O(n²)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。

    为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x₁,x₂,..,x_n。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x₁,x₂,..,x_n排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。

    假设我们用x轴上某个点m将S划分为2个子集S₁和S₂，使得S₁={x∈S|x≤m}；S₂={x∈S|x>m}。这样一来，对于所有p∈S₁和q∈S₂有p

    递归地在S₁和S₂上找出其最接近点对{p₁,p₂}和{q₁,q₂}，并设δ=min{|p₁-p₂|,|q₁-q₂|}，S中的最接近点对或者是{p₁,p₂}，或者是{q₁,q₂}，或者是某个{p₃,q₃}，其中p₃∈S₁且q₃∈S₂。如图1所示。

图1 一维情形的分治法

    我们注意到，如果S的最接近点对是{p₃,q₃}，即|p₃-q₃|<δ，则p₃和q₃两者与m的距离不超过δ，即|p₃-m|<δ，|q₃-m|<δ，也就是说，p₃∈(m-δ,m]，q₃∈(m,m+δ]。由于在S₁中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S₁和S₂的分割点，因此(m-δ,m]中至多包含S中的一个点。同理，(m,m+δ]中也至多包含S中的一个点。由图1可以看出，如果(m-δ,m]中有S中的点，则此点就是S₁中最大点。同理，如果(m,m+δ]中有S中的点，则此点就是S₂中最小点。因此，我们用线性时间就能找到区间(m-δ,m]和(m,m+δ]中所有点，即p₃和q₃。从而我们用线性时间就可以将S₁的解和S₂的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢？还有一个问题需要认真考虑，即分割点m的选取，及S₁和S₂的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S₁∪S₂ ，S₁∩S₂⁼Φ，且S₁{x|x≤m}；S₂{x|x>m}。容易看出，如果选取m=[max(S)+min(S)]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S₁={x∈S|x≤m}和S₂={x∈S|x>m}。然而，这样选取分割点m，有可能造成划分出的子集S₁和S₂的不平衡。例如在最坏情况下，|S₁|=1，|S₂|=n-1，由此产生的分治法在最坏情况下所需的计算时间T(n)应满足递归方程:

   T(n)=T(n-1)+O(n)

    它的解是T(n)=O(n²)。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S₁和S₂中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m。

    至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法CPAIR1如下。

function CPAIR1(S);
begin
  if |S|=2 then δ=|x[2]-x[1]| // x[1..n]存放的是S中n个点的坐标
           else if (|S|=1) 
                   then δ:=∞
                   else begin
                          m:=S中各点的坐标值的中位数;
                          构造S1和S2,使S1={x∈S|x≤m}，S2={x∈S|x>m};
                          δ1:=CPAIRI(S1);
                          δ2:=CPAIRI(S2);
                           p:=max(S1);
                           q:=min(S2);
                          δ:=min(δ1,δ2,q-p);
                        end;
  return(δ);
end;

    由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计算时间T(n)满足递归方程：

    解此递归方程可得T(n)=O(nlogn)。

    这个算法看上去比用排序加扫描的算法复杂，然而这个算法可以向二维推广。

    下面我们来考虑二维的情形。此时S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S₁和S₂，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S₁={p∈S|p_x≤m}和S₂={p∈S|p_x>m}。从而使S₁和S₂分别位于直线l的左侧和右侧，且S=S₁∪S₂ 。由于m是S中各点x坐标值的中位数，因此S₁和S₂中的点数大致相等。

    递归地在S₁和S₂上解最接近点对问题，我们分别得到S₁和S₂中的最小距离δ₁和δ₂。现设δ=min(δ₁,δ₁)。若S的最接近点对(p,q)之间的距离d(p,q)<δ则p和q必分属于S₁和S₂。不妨设p∈S₁，q∈S₂。那么p和q距直线l的距离均小于δ。因此，我们若用P₁和P₂分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈S₁，q∈S₂，如图2所示。

图2 距直线l的距离小于δ的所有点

    在一维的情形，距分割点距离为δ的2个区间(m-δ,m](m,m+δ]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P₁中所有点与P₂中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n²/4对这样的候选者。但是P₁和P₂中的点具有以下的稀疏性质，它使我们不必检查所有这n²/4对候选者。考虑P₁中任意一点p,它若与P₂中的点q构成最接近点对的候选者，则必有d(p,q)<δ。满足这个条件的P₂中的点有多少个呢？容易看出这样的点一定落在一个δ×2δ的矩形R中，如图3所示。

图3 包含点q的δ×2δ的矩形R

由δ的意义可知P₂中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2δ的边3等分，将它的长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形。如图4(a)所示。

图4 矩形R中点的稀疏性

    若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则

    因此d(u,v)≤5δ/6<δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P₁中任一点p，P₂中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n²/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能作出这个结论，因为我们只知道对于P₁中每个S₁中的点p最多只需要检查P₂中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P₂中所有S₂的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S₂中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于δ。由上面的分析可知，这种投影点最多只有6个。因此，若将P₁和P₂中所有S的点按其y坐标排好序，则对P₁中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P₁中每一点最多只要检查P₂中排好序的相继6个点。

    至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下:

function CPAIR2(S);
begin
  if |S|=2 then δ:=S中这2点的距离
     else if |S|=0 
           then δ:=∞
           else begin
                 1.  m:=S中各点x坐标值的中位数;
                     构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px>m}
                 2.  δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);
                 3.  δm:=min(δ1,δ2);
                 4.  设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合，
                     P2是S2中距分割线l的距离在δm之内所有点组成的集合。将P1和
                     P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排
                     好序的点列;
                 5.  通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的
                     所有点(最多6个)可以完成合并。当P1*中的扫描指针逐次向上移动
                     时，P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按
                     这种扫描方式找到的点对间的最小距离;
                 6.  δ=min(δm,δl);
               end;
  return(δ);
end;

    下面我们来分析一下算法CPAIR2的计算复杂性。设对于n个点的平面点集S，算法耗时T(n)。算法的第1步和第5步用了O(n)时间，第3步和第6步用了常数时间，第2步用了2T(n/2)时间。若在每次执行第4步时进行排序，则在最坏情况下第4步要用O(nlogn)时间。这不符合我们的要求。因此，在这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P^*。在执行分治法的第4步时，只要对P^*作一次线性扫描，即可抽取出我们所需要的排好序的点列P₁^*和P₂^*。然后，在第5步中再对P₁^*作一次线性扫描，即可求得δ_l。因此，第4步和第5步的两遍扫描合在一起只要用O(n)时间。这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)满足递归方程：

    显而易见T(n)=O(nlogn)，预排序所需的计算时间为O(n1ogn)。因此，整个算法所需的计算时间为O(nlogn)。在渐近的意义下，此算法已是最优的了。

　　若有多种点求不同种点间的最接近点对，该方法不适用, 由于无法找到合适的bounding, 对于每一个点无法只检测常数个点 ,merging部分时间复杂度大于o(n),　因此无法在0(nlogn)时间内完成。

在vs2008下使用CGAL（转自CGAL官网）

Installing CGAL and related programs on Windows operating system

The following section explains how to install CGAL 3.4 with Boost 1.38 with QT4.5 on Windows XP/Vista with Visual Studio 2008/2005

Note that during the entire setup you need internet connection!

Note that the installation requires significant disk space. Make sure to free enough disk space before the installation.

Instructions on adding Enviroment Variables in Windows are at the end.

1. Downloading stuff
1. First download CGAL (3.4) windows installer from here. (it is at the bottom of the page)
2. Get the latest version of CMake (currently 2.6.3) from here.
3. Download the latest version of QT (currently 4.5) from here.
4. Download the latest version of Boost (currently 1.38) from here OR the automated windows installer from here (I installed it by compiling myself but other people installed it with the installer with no problems).
2. Install CMake
1. Use the default configuration and don't forget to add C:\Program Files\CMake
    2.6\bin to the PATH (if it wasn't added for you)
3. Install Boost

  There are several options/configurations for installing boost. The minimal requirements for CGAL will be added soon. In the meantime, if in doubt, perform a full install.

1.  If you donwloaded the installer just install boost and continue to the next section otherwise continue to step 2.
2. Create a directory c:\boost and copy boost_1_38_0.7z into it.
3. Extract the Boost files to the C:\boost\boost_1_38_0 directory (right-click the file, go to 7zip and press extract here. If you don't have 7zip download and install from here)
4. Don't delete boost_1_38_0.7z file after you are done extracting!!!
5. open cmd (Strart->Run->cmd) and do : cd c:\boost\boost_1_38_0
6. in the cmd type cmake-gui .  ( <-- this dot is important!!!)
7. Create a new Visual Studio 2008 Generator (or the generator that fits your version of VS) by pressing Configure
8. Press "Add Entry" and create a boolean item called CMAKE_IS_EXPERIMENTAL and set the value to true
9. Press "configure"
10. Select "Build Static" if it not yet selected (infact you should have all the BUILD_XXXXX flags set to true except from BUILD_TESTING)
11. Click Configure until the Generate button becomes available
12. Click Generate
13. Close CMake. (here the dot is not important)
14. Open the newly generated solution in the boost directory and press Build -> Clean Solution when this is done press Build -> Rebuild Solution
15. Wait a long time.... If it asks you to save and restart visual studio using some sort of macro agree to it and let the macro finish.
16. add C:\boost\boost_1_38_0\bin directory to the PATH
17. Remeber I told you not to delete the 7zip file?
18. Extract the Boost files to the C:\boost\boost_1_38_0 directory (right-click the file, go to 7zip and press extract here) tell it to overwrite all existing files. (In case you are having a de-ja-vu from step 2. You are right. For some unknown reason CMake destroys some of the files so you need to extract them all over again)
19. Thats it Boost is installed.
1. Install QT
1. Be warned! This installation took me 5 hours to complete so you might want to start it at the evening and leave it for the night.
2. Run the QT installer executable (no, this is not the 5 hour part).
3. Yes, you might need MinGW (not the source code) so download and install that to C:\MinGW. It is easiest to install directly through the QT installer. If you run into problems (with trolltech mirror), you can download the minGW installer seperately from sourceforge.net (currently version 5.1.4), install it, and then continue the QT installation, disregarding the warning message about version compatibility. 
4. once the installation of QT is finished Add C:\MinGW\bin to the path (if it wasnt done for you)
5. If you open the lib directory of QT you will see it is filled with a bunch of files but non of them are lib files. So now lets create the lib files.
6. Open Visual Studio Command Prompt (Start->Programs->Visual Studio->Visual Studio Tools->Visual Studio CommandPrompt) and write "cd c:\QT\4.5.0"
7. in the black window write "configure"
8. agree to the license and wait a while (still not 7 hours but I would go eat dinner about now)
9. in the cmd window write "nmake" and go to sleep. This will take about 5 hours (at least on my old slow computer)
10. Add C:\Qt\4.5.0\bin to the path
11. Thats it QT is installed
12. Restart your computer (don't forget to bookmark this page or something)
2.  Install CGAL
1. Finally we install the crown jewel. Run the installer and select your compiler and all the variants, next, next.
2. I sugest installing CGAL to C:\CGAL\CGAL-3.4  ; in any case never install CGAL to a path with spaces
3. Tell the setup to create all the enviroment variables and wait for the install to complete. Including the downloads at the end.
4. Add the enviroment variable QTDIR = C:\Qt\4.5.0 
5. Add the enviroment variable BOOST_ROOT = C:\boost\boost_1_38
6. Open the command prompt (start->run->cmd)
7. Type cd C:\CGAL\CGAL-3.4
8. run cmake-gui . (<-- this dot is important again!)
9. press configure and select your compiler
10. If you have Cygwin installed (like me) the configure will fail becuase it was looking for the GMP and the MPFR code in the wrong place. Edit the GMP_INCLUDE_DIR and MPFR_INCLUDE_DIR to be C:/CGAL/CGAL-3.4/auxiliary/gmp/include
11. Edit the CMAKE_BUILD_TYPE to Debug
12. Select WITH_demos and WITH_examples if you wish the demos and the examples to be installed (although I don't see any reason to include those. You can just compile what you need when you need it).
13. You may need to add the variable Boost_INCLUDE_DIR (=C:/boost/boost_1_38_0), and edit the variables Boost_THREAD_LIBRARY_DEBUG (=C:/boost/boost_1_38_0/lib/libboost_thread-vc90-mt-gd-1_38.lib) and Boost_THREAD_LIBRARY_RELEASE (= C:/boost/boost_1_38_0/lib/libboost_thread-vc90-mt-1_38.lib)
14. Press Configure until you can press Generate and then press Generate
15. A solution file will be created here : C:\CGAL\CGAL-3.4. Open it with your visual studio.
16. Close CMAKE
17. Press Build->Clean Solution, Press Build->Rebuild Solution. If you did everything I wrote before, including step 17 in the boost install the compile should work without problems (maybe some examples will not compile because you are missing 3rd party components but that isn't important).
18. You are done! CGAL is installed.

At the end of the installation, your PATH should look something like that (this is my PATH) :

PATH=C:\Windows\system32;C:\Windows;C:\Windows\System32\Wbem;
C:\Program Files\ATI Technologies\ATI.ACE\Core-Static;c:\Program Files\Microsoft
 SQL Server\90\Tools\binn\;C:\cygwin\bin;C:\cygwin\usr\bin;C:\cygwin\usr\local\b
in;C:\cygwin\usr\X11R6\bin;C:\gs\gs8.63\bin;C:\gs\gs8.63\lib;C:\boost\boost_1_38
_0\bin;C:\cygwin\usr\include;C:\MinGW\bin;C:\Qt\4.5.0\bin;C:\Program Files\CMake
 2.6\bin;C:\CGAL\CGAL-3.4\auxiliary\gmp\lib

1. Creating a Visual Studio Project that uses CGAL and QT
1. Now that you have installed CGAL you need to configure your visual studio to work with it.
2. Open an empty C++ project using the Win32 Console Application wizard (select empty project and click finish) File->New->Project  ... Other Languages -> C++ -> Win32 -> Win32 Console Application
3. When the solution loads up go to Tools->Options ... Projects and Solutions -> VC++ Directories
1. Make sure that Executable Files (Combobox at the top right)  contains the $(PATH) variable (at the end there)
2. Select Include Files in the combobox and add :
1. C:\CGAL\CGAL-3.4\auxiliary\gmp\include
2. C:\Qt\4.5.0\include
3. C:\boost\boost_1_38_0
4. C:\CGAL\CGAL-3.4\include
3. They should appear at that order at the topmost part of the list (use the arrows to move items up and down)
4. Select Library Files from the combobox and add :
1. C:\CGAL\CGAL-3.4\auxiliary\gmp\lib
2. C:\CGAL\CGAL-3.4\lib
3. C:\boost\boost_1_38_0\lib
4. C:\Qt\4.5.0\lib
5. Press OK until you are back at the main window
6. Right click your project and select Properties
7. Go to Configuration Properties -> C/C++ -> General. In there you will see Additional Include Directories. Copy this line there :"C:\Qt\4.5.0\include\QtCore","C:\Qt\4.5.0\include\QtCore","C:\Qt\4.5.0\include\QtGui","C:\Qt\4.5.0\include\QtGui","C:\Qt\4.5.0\include","C:\Qt\4.5.0\include\ActiveQt","debug",".",C:\Qt\4.5.0\mkspecs\win32-msvc2005
8. QT has a bunch of directories in their include so you need to add each directory individualy. The ones I write there should be enough for a beginner
9. Go to Configuration Properties -> Linker -> Input and copy the following line to the Additional Dependancies line : C:\Qt\4.5.0\lib\qtmaind.lib C:\Qt\4.5.0\lib\QtGuid4.lib C:\Qt\4.5.0\lib\QtCored4.lib
10. You will generaly need some of the libs as dependant files. The ones I gave above should be enoguh for a beginner program.
11. Thats it, you can write your code and compile it here is an example of a main.cpp that should compile now :

----------------- CUT HERE ------------------

#include
#include
#include
#include <CGAL/Qt/GraphicsViewNavigation.h>
#include
#include
int main(int argc, char **argv)
{
QApplication app(argc, argv);
QGraphicsScene scene;
scene.setSceneRect(0,0, 100, 100);
scene.addRect(QRectF(0,0, 100, 100), QPen(QColor(255,0,0)));
scene.addLine(QLineF(0,0, 100, 100));
scene.addLine(QLineF(0,100, 100, 0));
QGraphicsView* view = new QGraphicsView(&scene);
CGAL::Qt::GraphicsViewNavigation navigation;
view->installEventFilter(&navigation);
view->viewport()->installEventFilter(&navigation);
view->setRenderHint(QPainter::Antialiasing);
view->show();
return app.exec();
}

----------------- CUT HERE -------------------

Good Luck and feel free to ask us questions.

Setting up PATH variable or other Enviroment variables on windows systems

1. From the desktop, right-click My Computer and click properties.
2. (on Vista click Advanced system settings on the left side)
3. In the System Properties window, click on the Advanced tab.
4. In the Advanced section, click the Environment Variables button. 
5. Finally, in the Environment Variables window, highlight the path variable in the Systems Variable section and click edit. Add or modify the path lines with the paths you wish the computer to access. Each different directory is separated with a semicolon as shown below.
   
   C:\Program Files;C:\Winnt;C:\Winnt\System32

The following section explains how to install older versions of CGAL:

1. Install Microsoft Compiler
1. CGAL needs at least Visual C++ 7.1 (or, of course, gcc running under Cygwin – but this is not the subject of this document).
2. The best free options is probably to download the Express version of Visual C++.
2. Installing Boost - installing boost is quite easy using the BoostPro Computing installer (at the time this document was written the updated version of boost was 1.36.0).
3. Installing CGAL
1. The Windows installer is pretty convenient: http://www.cgal.org/download.html
   (Notice that you should tell the installer where Boost is installed).
2. Visual Studio 2008 users:The CGAL installation contains no binaries for Visual Studio 2008 (VC9.0). You need to compile GMP and MPFR or download this archive file that contains the compiled binaries for CGAL, GMP and MPFR (x86) and also updated auto_link.h to enable auto-linking of projects. Just open the archive to the CGAL installation directory.

CGAL 3.5.1和boost 1.42不兼容，最后编译vs solution时会报错。换用boost 1.41一切正常。QT编译时间很长，可下载带注册机的qt for vs2008 commercial edition.　boost用boostpro installer装会方便很多。

编写GLSL及其glew需要注意的几个问题

GLSL
1.uniform variable is read-only.
2.给float变量赋值要加.0
3.类型转换是int(variable)而不是(int)variable
4.数组index若用vaiable访问(no matter read or write) 则必须事先定义好大小.若index只用constant则不必

glew
1.要在main中调用glewInit()，否则程序运行到某些库函数时会产生异常，但编译不会报错
2.setShader()部分要在glutMainLoop()之前，否则shader会不起作用
3.GLboolean glewIsSupported (const char* name)可用来检测是否对某个extension支持
4.某些extension对其余extension会有dependence.这时需要在shader起始位置加上类似下面的语句

#extension GL_EXT_gpu_shader4 : enable

矩阵行列式及向量外积

矩阵行列式

行列式的计算用下图表示：主对角线上的元素和反对角线上的元素各自相乘，然后用各主对角线上元素积的和减去各反对角线上元素积的和。

3×3的行列式

如果将3 x 3阶矩阵的行解释为3个向量

行列式的一些重要性质：

（1）矩阵积的行列式等于矩阵行列式的积：|AB| = |A||B|
        这可以扩展到多个矩阵：  |M1 M2 ... Mn| = |M1| |M2| ... |Mn-1| |Mn|
（2）矩阵转置的行列式等于原矩阵的行列式：|MT| = |M|
（3）如果矩阵的任意行或列全为0，那么它的行列式等于0.
（4）交换矩阵的任意两行或两列，行列式变负。
（5）任意行或列的非零积加到另一行或列上不会改变行列式的积。

行列式的几何意义：

行列式等于以基向量为两边的平行四边形的有符号面积（如图9.1所示）。有符号面积是指如果平行四边形相对于原来的方位”翻转“，那么面积变负。

3D中，行列式等于以变换后的基向量为三边的平行六面体的有符号的体积。3D中，如果变换使得平行六面体”有里向外“翻转，则行列式变负。


行列式与矩阵变换导致的尺寸改变相关，其中行列式的绝对值与面积（2D）、体积（3D）的改变相关，行列式的符号说明了变换矩阵是否包含镜像或投影。

矩阵的行列式还能对矩阵所代表的变换进行分类。如果矩阵的行列式为0，那么该矩阵包含投影。如果矩阵的行列式为负，那么该矩阵包含镜像。

向量外积

几何意义是：数量上（即模）等于原来两个向量为邻边的平行四边形面积；方向垂直与原来两向量所在的平面，并按右手法则确定正向。三维直角坐标系中， X × Y = Z。

加法的分配律： 

a × (b + c) = a × b + a × c

与标量乘法兼容：

(ra) × b = a × (rb) = r(a × b)

不满足结合律，但满足 雅可比恒等式：

a × (b × c) + b × (c × a) + c × (a × b) = 0

拉格朗日公式

a × (b × c) = b(a · c) − c(a · b)