CGAL中的3D布尔运算

CGAL是Computational Geometry Algorithms Library 的简称，主页是：http://www.cgal.org/。在主页的左栏有Mailing Lists，在这里有很多人在使用该库遇到问题时寻求帮助，然后专业人士给予解答。因此解决问题相对权威一点。在这里多看看， 还可以学到地道的专业英语呢， 嘿嘿！

回到正题，如何使用CGAL进行布尔运算。使用CGAL是一个比较麻烦的过程，首先是配置环境问题，这是一项很耗大的工程，比较完整的配法在这里：http://acg.cs.tau.ac.il/cgal-at-tau/installing-cgal-and-related-programs-on-windows。 其实也没有必要完全照搬这里的配置办法，我的建议是最好下载安装版来（即setup.exe）安装比较好，如果是Source Code则相对较麻烦些。 我的安装笔记如下：

Preparations before Installing CGAL
1. If you use Visual Studio 2008, then you must install SP1.
2. No matter when your computer is 64-bit or 32-bit, please note that you should choose 32-bit when you configure, not only in the process of installing CGAL.exe, but also in configuration with CMAKE.
3. in the process of installing Boost or CGAL, should choose the option: Add to path.
4. download relevant exe files: cmake-2.8.0-win32-x86.exe; boost_1_40_setup.exe; CGAL-3.5.1-Setup.exe

NOTE: Don't leave blank in the installation paths.

Installing:
Step 1. Install boost 1.40. Don't forget to copy "tools/jam/src/bin.ntx86/bjam.exe" to the BOOST_ROOT directory. And then run it.
Step 2. Install CMake 2.8.
Step 3. Install CGAL 3.5.1. Platform: choose 32-bit

After this, go into the CGAL root directory (dos mode), type "cmake-gui ." command, then do the following configuration:
[Advanced view]: must add following variables
BOOST_ROOT = .../boost_1_40
Boost_INCLUDE_DIR (=C:/boost/boost_1_40), and edit the variables Boost_THREAD_LIBRARY_DEBUG (=C:/boost/boost_1_40_0/lib/libboost_thread-vc90-mt-gd-1_40.lib) and Boost_THREAD_LIBRARY_RELEASE (= C:/boost/boost_1_40_0/lib/libboost_thread-vc90-mt-1_40.lib)
Then configure and generate...
[Debug and Release]

NOTE: If you configure improperly and want to reconfigure it, then you must delete CMakeFiles folder and CMakeCache.txt which generated by configuring.

After this, there is a solution *.sln in the CGAL root directory. Just build it in Debug and Release mode.

Done.

NOTE: environment variable(right click my computer > properties > advanced > environment variables) like this:
PATH=....;C:/boost/boost_1_38
_0/bin;C:/Program Files/CMake
 2.6/bin;C:/CGAL/CGAL-3.4/auxiliary/gmp/lib

Create a new project with VS2008, you should add the following paths at tools > options > Projects and Solutions > VC++ Directories:

include files:
C:/CGAL/CGAL-3.4/auxiliary/gmp/include
C:/boost/boost_1_38_0
C:/CGAL/CGAL-3.4/include

lib files:
C:/CGAL/CGAL-3.4/auxiliary/gmp/lib
C:/CGAL/CGAL-3.4/lib
C:/boost/boost_1_38_0/lib

Additionally, right click project > Configurations Properties > c/c++ > code generation > Runtime Library, set it as following

Debug:
Multi-threaded Debug DLL (/MDd)
Release:
Multi-threaded DLL (/MD)

注意：

在用Cmake编译时，会出现这样的错误。“The C++ compiler "C:/Program Files (x86)/Microsoft Visual Studio   10.0/VC/bin/cl.exe" is not able to compile a simple test program.” 原因是因为卸载了早期的microsoft visual studio而没有卸载干净。可以打开工程，测试小程序看看编译是否正常。针对这个问题，解决方案如下：

终极解决方案：
VS2010在经历一些更新后，建立Win32 Console Project时会出“error LNK1123” 错误，解决方案为将 项目|项目属性|配置属性|清单工具|输入和输出|嵌入清单 “是”改为“否”即可，但是没新建一个项目都要这样设置一次。
在建立VS2010 Win32 Project项目时，按照上面解决方案依然发生了“error LNK1123”错误，经过上网查资料，解决方案为：
第一步：与上相同。
第二步：将 项目|项目属性|配置属性|连接器|清单文件|嵌入清单 “是”改为“否”。
第三步：一般计算机经过上两步设置就能解决问题了，但是如果还有问题，那就按一下方法解决：
计算机是否为64bit操作系统，如是，继续2。
查找是否有两个cvtres.exe。一个是C:\Program Files(x86)\Microsoft Visual Studio 10.0\vc\bin\cvtres.exe， 另一个是C:\Windows\Microsoft.NET\Framework\v
4.0.30319\cvtres.exe。右键属性|详细信息 查看两者版本号，删除/重命名较旧的版本，或者重新设置Path变量。

意外的是，治本的办法是第三步，删除旧版本的cvtres.exe后，就不需要每次都设置配置了。

下面详细记下布尔运算：

第一阶段：

1. 掌握了Nef_Polyhedron与 Polyhedron的相互转化，用Polyhedron来构造Nef_Polyhedron；调用Nef_Polyhedron的convert_to_polyhedron(Polyhedron)函数将Nef_Polyhedron转化为Polyhedron。

2. 在CGAL中进行布尔运算，首先导入.off文件到Polyhedron变量，将其转化为Nef_Polyhedron进行布尔运算，然后将运算的结果再转化为Polyhedron以.off的形式导出。

第二阶段：

1. 会用.off与plane生成的半空间进行布尔运算，注意要使用半空间，则必定要包含头文件#include <CGAL/Extended_homogeneous.h>。得到结果比较耗时，而且对于稍微复杂的.off文件与plane生成的半空间，以及两个稍稍复杂的.off文件都无法运行，会提示：Constructor is not available for this kenerl,虽然编译没有错误. 贴出代码,注意:使用该代码时，需要将.off文件放在该程序所在的文件夹。

#include "stdafx.h" #include <CGAL/Extended_homogeneous.h> #include <CGAL/Nef_polyhedron_3.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/IO/Polyhedron_iostream.h> #include <CGAL/IO/Nef_polyhedron_iostream_3.h> #include <fstream> #include <iostream> #include <Windows.h> typedef CGAL::Extended_homogeneous<CGAL::Gmpz> Kernel; typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron; typedef CGAL::Polyhedron_3<Kernel> Polyhedron; typedef Kernel::Plane_3 Plane_3; using namespace std; int main() { int begingTime<mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js"></mce:script><mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js"></mce:script> = GetTickCount(); //calculate time consumed //load cube.off ifstream inFile1("cube.off"); Polyhedron cube; inFile1 >> cube; inFile1.close(); Nef_polyhedron nef_cube(cube); //construct a halfspace with a plane Nef_polyhedron N(Plane_3(1,-1,1,-1)); //operation //Nef_polyhedron nef_res = nef_cube * N; if (nef_res.is_simple()) { Polyhedron result; nef_res.convert_to_polyhedron(result); #ifdef _DEBUG ofstream out("bool.off"); #else ofstream out("bool_release.off"); #endif out << result; out.close(); } else { cerr << "nef_res is not a 2-manifold." << endl; } int endTime = GetTickCount(); cout << "Total time:" << (endTime - begingTime) / 1000.0 << " seconds./n"; system("pause"); return 0; }  

第三阶段

终于找到布尔运算的办法啦，可以进行两个.off文件的布尔元素，而且效率提高了很多。当然要在release模式下进行。关键所在是kernel的定义，在这里要用这个kernel:typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;故程序的头文件需要包括头文件#include <CGAL/Exact_predicates_exact_constructions_kernel.h>。贴出代码：

#include "stdafx.h" #include <CGAL/Nef_polyhedron_3.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/IO/Polyhedron_iostream.h> #include <CGAL/IO/Nef_polyhedron_iostream_3.h> #include <CGAL/Exact_predicates_exact_constructions_kernel.h> #include <fstream> #include <iostream> #include <Windows.h> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;//this kernel for .off boolean operation, fast and precise typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron; typedef CGAL::Polyhedron_3<Kernel> Polyhedron; typedef Kernel::Plane_3 Plane_3; using namespace std; int main() { int begingTime = GetTickCount(); //load cube.off ifstream inFile1("cube.off"); Polyhedron cube; inFile1 >> cube; inFile1.close(); Nef_polyhedron nef_cube(cube); //load torus.off ifstream inFile("torus.off"); Polyhedron torus; inFile >> torus; inFile.close(); Nef_polyhedron nef_torus(torus); //operation Nef_polyhedron nef_res = nef_torus * nef_cube; if (nef_res.is_simple()) { Polyhedron result; nef_res.convert_to_polyhedron(result); #ifdef _DEBUG ofstream out("bool.off"); #else ofstream out("bool_release.off"); #endif out << result; out.close(); } else { cerr << "nef_res is not a 2-manifold." << endl; } int endTime = GetTickCount(); cout << "Total time:" << (endTime - begingTime) / 1000.0 << " seconds./n"; system("pause"); return 0; }  

完毕。

参考网站： http://www.cs.tau.ac.il/cgal/Manuals/doc_html/

在这里不仅可以找到一般的例子程序，还可以看到类的内部结构。