英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
三维三角网格切片的优化算法
关键字：增材制造 三角形平面交叉 轮廓构造算法 算法复杂度 工艺规划
摘要：本文描述了一种用一系列平行平面分割非结构化三角形网格模型的算法。证明了该算法是渐近最优的:对于非规则间隔切片平面，其时间复杂度为O(n log k k m)，其中n为三角形数，k为切片平面数，m为三角形平面相交段数。如果平面是均匀间隔的或者三角形是按适当的顺序给定的，那么时间复杂度也会降低为(n k m)。本文还描述了一种渐近最优线性时间算法，用于从切片步骤生成的未排序的线段列表构造一组多边形，并将所提出的算法与文献中已知的方法进行了理论和实验比较。
- 引言
增材制造，也被称为3D打印，是一种通过放置连续的材料层来构建物理对象的技术。该对象通常由CAD系统创建的三维几何模型、计算机断层扫描或磁共振数据[1,2]或其他方法生成。
几何模型在被发送到3D打印机之前，必须进行流程规划，这意味着一系列的任务，这包括:在打印机的工作区中对对象进行定位和定位，将几何模型切割成层，在需要时添加支持结构，最后规划打印机的工具路径[3]。
切片过程可分为4个子任务，如图1所示。这些步骤可以消耗高达60%的整个流程规划时间[4]。
本文描述了求解网格剖分步骤(第3节)和轮廓构造步骤(第4节)的最优算法，为简单起见，本文仅将网格切片任务称为切片。
1.1切片
在切片步骤中，几何模型与平行平面相交，得到各材料层的轮廓。本文不涉及这些平面的选择——它们需要事先知道。参见图2。这一步可以用一个恒定的层厚(均匀切片)或可变的层厚(自适应切片)来完成。自适应切片在打印模型的关键特性中提供了更好的表面质量，同时在可接受粗加工的[3]区域节省了时间。
为了更好的通用性，3D打印软件通常假设几何模型被简化为一组无序的、非结构化的三角形，这些三角形近似于物体的表面。这种表示实际上是一种行业标准，集中体现在目前非常流行的STereoLithography (STL)文件格式中。因此，切片步骤的主要结果也是每个切片平面上的一组无序的、非结构化的线段。
1.2 外形结构
切片产生的切片必须形成一个或多个封闭的多边形，这些多边形将物体的内部(即物体内部有无材料的区域)划分在相应的层上。参见图3。
这个轮廓构建步骤是必需的，因为大多数3D打印过程中，机器控制代码的生成都需要对截面的多边形描述，该描述提供了其周长(用于精确构建对象的表面)和封闭区域(用于填充对象的内部)。此外，许多过程需要计算偏置轮廓，例如补偿喷嘴、耗材直径等，或沉积规定厚度或不同成分的物体外壳;偏移算法通常需要多边形，而不是非结构化的段列表。
图1切片过程
1.3网格一致性
为了便于3D打印，三角形网格必须将空间划分为两个区域，即实体对象的内部和外部。为此，它必须是一个封闭的有向的二维流型，没有自交或虚接触。值得注意的是，任意两个三角形之间的交集必须是空的，或者是两个三角形的一条边，或者是两个三角形的一个顶点。每条边必须恰好由两个反向使用这条边的三角形共享，并且与任何顶点关联的三角形必须构成单锥体[5]。
然而，我们希望处理网格的软件应该是强壮的，即能够容忍输入网格的缺陷，例如可能由获取和舍入错误、模型不同部分之间的接触以及之前处理步骤中的错误造成的缺陷。即使软件没有纠正这些缺陷，它也应该最终能够正常终止任务，并输出一个良好的结果，尽可能地保留关于输入网格的信息。例如，如果输入网格没有被停止，那么切片和终止步骤的输出应该是作为开放多边形线组织的正确的线段组。
1.4贡献
本文的贡献三个方面:(1)最优算法对任意层厚度的三角形网格分割问题,运行在O(n日志k k m)其中n是三角形的数量,k是飞机的数量,m是段的总数(平面三角形路口)模型。如果层厚均匀，或者三角形之前是按z坐标排序的，则算法运行时间为O(n k m);(2) 证明未分类非均匀切片问题的下界是Ω(nlogk k m); （3）轮廓构造的最优（线性时间）算法。
1.5论文结构
本文的其余部分安排如下。第2节回顾了一些相关工作。切片和轮廓构造算法分别在第3节和第4节中描述，第5节给出了两种算法的实验比较，第6节说明结论。
图2三维物体模型表面三角形网格(A)，均匀切片(b)，自适应切片(c)的例子
- 相关工作
在这一节中，本文回顾了与本文所考虑的问题密切相关的增材制造流程规划的文献，即三角形网格切片算法和轮廓构造算法。
2.1网格分割
Pandey [6]等人的调查涵盖了截至2003年的主要切片算法。根据他们的观点，这些算法可以被广泛地分为以三角形网格为输入的细化模型的切片，以及直接在更通用的CAD模型(如NURBS)上工作的直接切片。直接切片策略可以避免曲面三角化带来的误差，从而提供更准确的结果[7,8]。然而，在某些应用程序中，对象模型已经以细化的形式获得。
由Chalasani和Grogan在[9]中描述的朴素切片算法，是用每个三角形切割每个切割平面。因此，其时间复杂度为O(kn)。这种朴素算法至今仍被广泛使用，有很多论文通过并行化[4]和内存使用优化等方法对其进行改进[10,11]。然而，关于减少其计算时间的研究相对较少。
1998年，Tata 等人[12]描述了一种更快的算法，该算法使用两级树结构来减少三角形-平面相交测试的数量。在其算法中，三角形按最小z坐标Zmin排序，然后分组，使具有相同Zmin值的三角形成为一组。然后，根据每个组的最大z坐标Zmax，将它们分成子组。这种树形结构运行于O(n log n)的时间。然后将朴素算法的nk三角形-平面相交检验替换为平面-子群相交检验，因为每个平面要么与子群中的所有三角形相交，要么一个也不相交。在有利的情况下(每个子组有许多三角形)，这种方法可以节省大量的时间。然而，在最坏的情况下(当所有顶点都有不同的z坐标)，算法仍然需要O(nk)时间。
1999年，McMains和Sequin[5]描述了一种用于切割结构化网格的扫描平面算法。他们的算法模拟了连续地将平面扫过三角网格的过程，保留了构成其与平面相交的多边形集合。每当扫描平面碰到网格的顶点，或者与指定的切片平面重合时，就会更新这些多边形。模型与扫描的交集平面形成一组闭合回路，从而省去了单独的轮廓构造步骤。McMains和Sequin声称他们的算法运行在O(n log n m)的时间内对于具有简单拓扑(低常数属)的模型,但可能需要Ω(n2)的时间对于具有Ω(n)的属。另一方面，该算法需要一个具有完整拓扑(邻接和切入)信息的输入网格，而不仅仅是一组三角形。Bechet 等人[13]描述了一种从STL文件中恢复网格拓扑的算法，该算法使用存储和排序顶点的二叉树;这种方法在最坏的情况下以时间O(n log n)运行。
一个理想的算法将只检索由每个平面分割的三角形集，并且工作量应该是线性的，在这个集的大小上，说花费时间是O(n k m)而不是o (nk)。对于均匀切片，Huang等人[14](2012)的算法实现了最优时间复杂度。然而，该算法依赖于层厚恒定来确定与给定三角形相交的平面，因此不能应用于自适应切片。
图3增材分层制造工艺规划中选定的步骤:(a)将三角形网格切片，在每个平面上生成一组(b)线段，线段连接成闭环(c)。
2.2外形结构
朴素轮廓构造算法从输入列表s中的任意段s开始，该段成为新多边形的第一条边。然后在S中寻找另一个端点与S的一个端点重合的段r。如果输入是一个格式良好的二维流行的切片，那么这个段必定存在。一旦找到这样的段，它将根据需要重新定向，并附加到多边形;用r代替s重复搜索，直到得到一个闭合循环。在处理过程中，从S中删除段。重复整个过程以获得其它的等高线，直到S为空。当有m条线段时，需要时间为O（m2）。。
2003年，Park[15]提出使用Bentley-Ottmann[16]扫线算法来解决轮廓构造问题。一般的Bentley-Ottmann算法运行时间为O((m p) logm)，其中m为线段数，p为线段之间的交点数。如果唯一的交集是段端点(对于格式良好的输入也是如此)，则p = 2m。从而简化了Bentley-Ottmann算法，运行时间为O(m logm)。
曾等人[8]和Qi等人[17]提出利用层深法向图像(layer depth normal image, LDNI)采样分解将STL模型转换为网格层，即通过一组平行线对每个目标层进行采样，得到一个点列表。然后利用邻域信息将这些点连接起来进行轮廓构造。正如作者所描述的，根据STL模型的不同，可能需要采用高采样分辨率来保留清晰的特征。
图4三角形的属性
- 切片算法
3.1问题陈述
形式上，切片问题的输入由n个三角形T = (T[1]， T[2]，hellip; T[n])，顺序随意;还有k个垂直于Z轴的切片平面，由一系列增加的Z坐标P = (P[1]， P[2]，hellip;P[k])组成，他们之间的间距为常数(用于均匀切片)或任意间距(用于自适应切片)。
每个三角形T[j]由三个顶点T[j].v1, T[j].v2和T[j].v3定义。对于给定的三角形，顶点的最低和最高z坐标分别称为T [j].Zmin和T [j].Zmax，见图4。
切片问题的输出是一个列表S[i]，其中包含所有与平面P[i]相交的三角形生成的线段。
设ni为在z坐标P[i]处与平面相交的三角形数，kj为与三角形T [j]相交的平面数。n是ni的平均值，k是kj的平均值，也就是：
然后切片问题的输出由三角平面相交得到的m = nk = kn段组成。
在切片算法中，我们假设所有切片平面的z坐标与所有顶点的z坐标是不同的。我们保证这种情况在输入模型数据时,通过舍入所有顶点坐标,甚至一些基本单位的倍数ϵ(0.005毫米)和所有平面Z坐标ϵ奇倍数。那么三角形T [j]与P[i]相交当且仅当P[i]严格在T [j].Zmin和T [j].Zmax之间。特别注意的是，坐标可以在输入网格文件中四舍五入。
我们也丢弃任何有两个或两个以上重合顶点的三角形。注意，这种清理不会改变依赖于网格的三维空间模型。
图5算法1步骤3中zmin(黑点表示)三角分组的一个例子。得到的列表有:L1 = {t1}， L2 = {}， L3 = {t2, t3, t4, t5}， L4 = {t6, t7}， L5 ={}和L6 = {t8}。步骤7 i = 4后，假设扫面位于P3和P4之间，活动集为A = {t5, t3, t6, t7}。
3.2主要的算法
本文的切片算法(算法1)使用了一种类似于McMains和Sequin[5]的扫描平面策略，但是对于非结构化的三角形集进行了高度简化和优化。列表的输入数据包括三角形T,P平面z坐标的列表,层厚度delta;,和一个布尔参数srt。参数delta;应该是正的(甚至是ϵ的多倍)如果平面有均匀的厚度,也就是P[i]=[iminus;1] delta;对所有的iisin;{ 2,...，k };否则,该参数delta;应设置为零。当且仅当三角形列表T已经按照Zmin坐标排序时，布尔参数srt应该为真。
Algorithm 1
1: function Incremental-Slicing (n, T [1 . . . n], k, P[1 . . . k], delta;, srt)
2: // Split the triangle list.
3: L[1 . . . k 1] larr; build-triangle-lists (n, T , k, P, delta;, srt);
4:/ / Perform a plane sweep.
5: Alarr;{ };
6: for iisin;{1, . . . , k} do
7: Alarr; Acup;L[i];
8: S[i]larr;empty;;
9: for each t isin; A do
10: if t.zmax lt; P[i] then
11: Alarr; A \ {t};
12: else
13: (q1, q2)larr; compute-intersection (t, P[i]);
14: S[i] larr; S[i] cup; {(q1, q2)};
15: end if
16: end for
17: end for
18: return S[1 . . . k];
19: end function
在算法1的步骤3中，输入三角形列表T[1hellip;n]划分为k 1个三角形列表L[1]，L[2]，hellip;L[k 1],其中L[i]由Zmin处于P[i-1]和P[i]之间的所有三角形组成。而P[0]和[k 1]被分别认为是minus;infin;, infin;。这一步骤如图5所示，详见3.3节。
在步骤6-17中，我们计算每个平面的三角平面交点。具体地说，本文模拟了一个平面扫过网格的过程，从每个切面跳到下一个切面。在仿真过程中，我们保留了一组活动三角形A，这些三角形可能在坐标P[i]处与下一个切片平面相交。在步骤7中,我们将所有Zmin位于P[i-1]和P[i]之间的三角型添加到A。在步骤11中，我们从A中删除那些Zmax小于P[i]的三角形，因为
全文共16631字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2736]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
