<转>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)

<转>VS2008 如何添加H文件目录和LIB目录

H文件目录:

依次点击“项目——配置属性——C/C++——常规”，在“附加包含目录”中加入H文件所在的文件夹


LIB目录:
依次点击“项目——配置属性——链接器——常规”，在“附加库目录”中加入LIB所在目录

还没完，在“链接器”中找到“输入”，在“附加依赖项”中加入lua51.lib

或用 #pragma comment(lib,"lua51.lib")