1 绪论
1.1 研究背景
通过使用简单图元的组合来创建复杂模型是计算机辅助几何设计中的常见操作，其使用的图元既可以是球体、圆柱体和立方体一类的简单图元，也可以使用任意复杂的实体三维模型。这种通过简单图元组合复杂模型的计算称为布尔运算，其包含并集、交集和差集运算。布尔运算是计算机辅助设计中必不可少的工具，拥有着长久发展历史，其作为 3D 建模的基础性算法被广泛应用于计算机辅助设计与制造（CAD/CAM）、虚拟现实与数字雕刻等领域。
近 年来，随着 3D 打印技术的发展与自动化制造成本的降低，布尔中涉及的数据量急剧增加。在产品设计过程中，设计人员需要对模型重复执行布尔运算。如图 1.1(a)、(b)所示，该模型为戒指设计的一个中间状态，整个过程需要反复进行戒指外圈的修改高达20 次以上[1]。此操作在主流的 CAD 设计软件上，如 CATIA、Rhino、Solidworks，单次修改等待时间以小时计，从而极大的影响设计的效率和最终产品获取的效率。图 1.1(c)为打孔操作，该模型需要进行 300 个布尔“差”运算。在面对此类有着高速甚至实时布尔运算需求且模型复杂度高的应用场景，现有的布尔运算方法很难满足。
随着图形处理设备发展，光线追踪算法速度有了极大提升。主流图形显卡厂商NVIDIA 与 AMD 均推出了支持光线追踪硬件加速的图形显卡。在新一代 NVIDIA GPU上的 RTX 光线追踪技术可以执行具有硬件加速的射线/图元相交测试，射线/图元相交测试速度有了极大提升，这对布尔运算具有非凡意义。光线追踪作为未来图形显卡的主要发展方向之一，必将对 CAD 领域产生重要影响。除硬件外，软件方面光线追踪引擎也获得极大发展使其速度也有了巨大提升，即使在 CPU 端，光线追踪依然可获得满意的速度。
...............................
1.2 研究现状
三角网格模型进行布尔运算面临的问题主要是速度与稳定性。大量学者使用了诸多不同的方法来提高网格模型布尔运的效率与稳定性。本节将从速度与稳定性两个方面对布尔运算研究现状进行分析。
大规模网格模型在进行布尔运算时会由于庞大的三角面片数量使得运算效率极其低下，为加速此过程，通常采用包围体技术[2]与空间剖分技术[3]两类方式。包围体技术最常用的是轴向包络盒[4,5]，如 Qin 等人[5]使用轴向包络盒二叉树加速于三角形相交测试阶段以此来提高布尔运算的效率。其他方式还包括方向包络盒[6–8]，K-Dop[9][10]，包围球[11]等。此类方法的主要思想是通过有效的构建包围体来降低模型间三角面片相交测试次数从而加速布尔运算过程。空间剖分技术常见的有：八叉树[12–15]、均匀网格[16,17]、KD 树[18][19][20]、BSP 树[21,22]等。空间剖分技术对比于包围体技术的一大优势在于可以轻易实现并行运算实现加速，其中最为常用的为八叉树[12][1][23][13]。也有学者以八叉树与 BSP 树相结合的方式同时兼顾效率和内存使用量，如 Campen 等人[24]的方法。Douze 等人[18]的Quick CSG 使用 KD 树索引并通过并行运算实现了非常高速的网格模型布尔运算。除以上方式，也有通过 Layered Depth Image (LDI)[25]加速于网格布尔运算，Chen 等人[26]通过LDI 与拓扑信息结合进行加速于布尔运算三角形内外判定阶段，极大的减少了内外判定的计算量。Wang 等人[27]使用 Layered Depth-Normal Image(LDNI)[27][28]将模型进行离散化采样并通过对采样点云内外判定获得布尔运算结果点集，其后使用三维等值面提取[29]把点云重建为多边形网格。此方法完在 GPU 上进行运算，消除了内存与显存之间访问的速度瓶颈，与此类似的还有 Zhao 等人[30]的方法。Zhao 等人通过像素压缩的 LDI(Compact Layered Depth Image，CLDI)[30]进行射线采样，其内存消耗相较于 LDI 大幅减少；杨等人[1]也通过自适应 LDI 射线采样完成近似布尔运算后通过基于点的渲染达到了可与基于面片渲染媲美的布尔运算视觉效果，并通过插值处理模型交点获得模型相交线。
.........................
2 相关基础理论及方法
2.1 布尔运算概述
网格模型间的布尔运算是指将处理二值间关系的与、或、非和异或逻辑运算应用于三维网格模型间的运算。假设参与布尔运算的模型分别为1M 与2M ，x 为1M 与2M 之间被判定位于模型内部的部分，常见的四种布尔运算可表示为：
软件工程论文怎么写
2.2 图元相交测试
图元相交测试为基于边界表示法布尔运流程中不可避免的步骤。最常见的问题为三角形相交测试，三角形相交问题也可简化为射线与三角形相交问题。射线与三角形相交检测也为计算机图形学中常见的问题，在光线追踪算法中的应用颇为广泛。本节将对射线与三角形相交算法和三角形与三角形的相交算法进行介绍。
三角形测试是基于三角面片的布尔运算方法中不可避免步骤，三角形相交测试的目的在于找出模型中互相相交的三角形对。三角形相交问题作为在三角相交测试过程中的原子问题也存在多种不同相交类型。如图 2.3 所示，三角形所在的平面1P 与2P 存在平行、共面与相交三种情况，尤其为共面情况，往往需要作为特殊情况额外单独处理，如图 2.3(b)所示，位于平面上的三角形也存在着相交或不相交的情况。在网格模型质量差的情况下三角形本身也会面临退化问题，可能会退化为一条线会个点，这些问题都进一步增加了三角形相交测试的复杂性，给相交测试来了更大的挑战。
本节首先介绍对有限点集的 Delaunay 三角剖分[44]。将有限点集三角化的方法中用得最多为 Delaunay 三角剖分。Delaunay 三角剖分并不是一种三角剖分的具体算法，而是保证三角剖分网格质量的一种标准。Delaunay 三角剖分可以避免扁平三角形的出现，由于此类三角形非常的细长，因此在插值计算或栅格化过程中会对算法稳定性造成影响，在三角化时应尽量避免此类三角形的产生。
对一实数域上的有限点集 V 进行三角剖分，若其结果只包含 Delaunay 边，则可称此三角剖分为 Delaunay 三角剖分。Delaunay 边的定义如下，将有限点集 V 中的点作为端点构成的边的集合记为 E，假设 E 中的一条边为 e，其端点分别为 a、b，若存在一个圆经过 a 与 b 两点且圆内不包含 V 中的其它点（圆上最多三点共圆），则称 e 为 Delaunay边。因此 Delaunay 三角剖分必须符合空圆特性与最大化最小角特征两个重要准则。
.....................
3 基于射线采样的视觉布尔运算 ................................. 22
3.1 光线追踪射线采样 ................................ 22
3.2 射线采样模型一维布尔运算 ................................. 24
4 光线追踪三角网格模型布尔运算 .............................. 33
4.1 网格模型相交测试 ........................................ 33
4.2 网格模型再三角化 .......................................... 34
5 布尔运算系统设计与实现 ............................................. 44
5.1 视觉布尔运算系统 ............................................. 44
5.2 网格模型布尔运算系统 ............................................. 45
5 布尔运算系统设计与实现
5.1 视觉布尔运算系统
视觉布尔运算系统通过 C++在 Linux 环境下采用采用 LibIGL 库中基于 OpenGL 3.0与 ImGUI 图形界面库实现交互视窗的显示。系统主要设计模块如图 5.1 所示，系统界面如图 5.2 所示。
软件工程论文参考
(1) 通过图形界面加载本地三角网格模型到系统中用于后续的布尔运算，模型文件支持.OBJ、OFF、PLY 等多种格式，本系统只读取模型网格顶点与顶点索引信息。
(2) 将加载后三角网格模型信息送入Optix 光线追踪引擎生成光线追踪BVH加速结构，以视窗大小为射线数目并在当前视角下构建射线。在完成射线构建后通过加速机构求取射线与模型的交点，接着完成对采样点的内外判定。其后根据布尔预算类型判断射线上需要保留的采样点，最后渲染距离射线起点最近的采样点形成与视窗大小相同的布尔运算结果图片。
............................
6 总结与展望
6.1 本文工作总结
三维网格模型间的布尔运算作为一种基础性工具应用于诸多领域，如计算几何、计算机仿真和计算机辅助设计与制造。光线追踪技术作为近年来图显卡发展的热点技术已经对图形渲染领域产生了革命性影响，如游戏、动画制作，但是在计算机辅助领域其应用还乏善可陈。本文主要针对布尔运算的效率问题，基于光线追踪算法进行了以下两个方面的研究：
(1) 射线采样点云获取与实时视觉布尔运算渲染
针对在设计阶段无法对大型网格模型进行立等可得的布尔运算问题，本文提出了一种基于光线追踪的实时视觉布尔运算结果的方法。该方法通过光线追踪实现射线采样点云模型的获取，并通过单邻接采样点查询实现了内外判定。此方法很好的克服了由模型质量或采样视角原因造成射线上奇数采样点数使得内外信息判定错误的问题。实验结果表明，该方法可以实现实时视觉布尔运算渲染，这对于通过大规模通过布尔运算设计复杂形状具有重要意义。
(2) 大规模网格模型快速布尔运算
本文针对布尔运算在大规模网格模型上的效率和稳定性瓶颈问题，提出了一种新颖且高效布尔运算方法。该方法通过光线追踪技术加速布尔运算，大幅提高了布尔运算的速度与稳定性。具体而言，本文方法使用光线追踪加速于十分耗时相交测试与内外判定阶段。针对浮点数舍入误差产生的扁平三角形进行了优化处理以提高布尔运算操作的稳定性。大量实验结果表明，相较于其它主流算法该方法具有明显的效率优势。
参考文献（略）