分区结构的分区扫描路径生成算法

分区结构的分区扫描路径生成算法

快速生产是一种分层制造技术。在零件制造过程中，最基本的步骤之一是选择合适的扫描路径，并扫描每个零件的截面。目前,按照填充扫描路径的不同,扫描路径可分为三种:(1)平行扫描路径。采用这种扫描方式加工零件,所有扫描线均平行,见图1a,这是一种应用最为广泛的平行线的往复扫描方法。为了提高加工零件的性能,许多专家提出了往复扫描的多种改进形式;同时为了提高扫描效率,对扫描矢量方向进行了优化处理。(2)轮廓平行扫描。这种扫描方式的扫描线沿平行于边界轮廓线的方向进行,即按照截面轮廓的等距线进行扫描,见图1b扫描挢开生成算法小脑多边形的多种操作,比较复杂。(3)分形扫描方法。这种扫描方法的扫描路径是由短小的折线组成,见图1c。扫描路径的产生就是对截面轮廓进行填充,由STL模型分层得到的截面轮廓是一系列封闭的多边形,这些多边形是由顺序连接的顶点链构成。多边形可能是凸的或凹的,包围的区域可能是单连通的或多连通的。所以,截面轮廓的填充问题就转化为复杂多边形的填充问题,是计算机图形学领域的基本运算。现在介绍一种新的分区往复扫描路径生成算法,这种算法不仅简单,速度快,可以在加工控制过程中生成;同时,将复杂截面轮廓分割成若干个简单的无内孔的子区域,在每个简单的子区域内可以连续扫描,依次扫描每个子区域。这样避免了简单的平行扫描路径需要跨越内孔的非加工路径,提高了加工效率。1径反向旋转角区域的分割与扫描路径的方向有关,下面按照水平扫描路径方向进行区域分割和扫描路径生成,如果优化的扫描线方向与x坐标轴成α角,可以按以下步骤规划扫描路径:①将当前截面按顺时针方向旋转α角;②按水平方向规划扫描路径;③将得到的扫描路径反向旋转α角。区域分割的目的就是将复杂区域分割为简单的单调区域,在每个单调区域内可进行连续的扫描加工,避免跨越非加工区域。截面轮廓的区域分割就是将复杂的轮廓多边形形成的区域划分为沿扫描路径垂线L方向的单调多边形形成的单调域,要进行区域分割首先要找到L方向的轮廓多边形的极值点。复杂轮廓多边形划分为单调多边形的数目与极值点的数目有关,一般情况下,复杂轮廓多边形沿L方向划分单调多边形的数目等于L方向的平凡极大值或平凡极小值。如图2所示,一个截面轮廓由一个外轮廓12345和一个内轮廓6789组成,沿L方向,截面轮廓被划分为3个单调多边形,这3个单调多边形围成了3个单调区域Ⅰ、Ⅱ和Ⅲ,每个单调区域均处在一个极小值和一个极大值之间。这样在每个单调区域内,沿扫描方向都可以进行连续的扫描。2扫描变量的分段生成算法2.1边形边线的点扫描线为水平直线在截面轮廓区域内的部分,扫描线与多边形的交点就是水平直线与轮廓多边形边线的交点。A、B为多边形边线的两顶点,坐标分别为(xa,ya),(xb,yb),水平直线为:y=y0。相交情况分为两种,一种是重合情况,一种是非重合情况,见图3。重合时,交点有无数多个,此时记交点为(xa,y0);当正常相交时,其交点坐标为2.2头终点的数据结构为了方便地进行扫描路径的规划和记录扫描线与截面轮廓的交点,设计一个二维的交点表进行交点数据的存储,见图4。每条单链表存储一条扫描线与截面轮廓的所有多边形交点的x坐标,每条单链表的头结点存储扫描线的序号和该链表存储的交点数,所有单链表形成一个链表数组。头结点的数据结构为,typedefstructCrossHead{intScanLine;//扫描线序号,intPointNum;//扫描线的交点数,structCrossPoint*next;//数据结点指针};数据结点的数据结构为:typedefstructCrossPoint{floatx_crosspoint;//扫描线的交点数,structCrossPoint*next;//数据结点指针};2.3在扫描向量的区域内生成算法描述下面详细讨论扫描矢量的分区域生成算法:(1)有非小值点的极值点因为假设扫描线方向为水平方向,搜索截面轮廓的各多边形,得到y方向的所有极值点。当遇到非平凡极值点时,只保留x值较大的非平凡极值点,此时极大值点的个数应当和极小值点的个数相等。然后将极大值点和极小值点按照y坐标从小到大排序。(2)扫描线农业面为面的理论线和截面轮廓的点扫描线在y=0到最小的极小值之间,扫描线与截面轮廓没有交点,扫描线直接在y=ymin+scandis处计算交点,ymin为最小的极值点,scandis为扫描线间距。求得交点后,将交点存储在相应的扫描线链表中,同时该扫描线甸表的头结点的交点数加2。求解交点时,每遇到一个极小值,交点数增加两个;每遇到一个极大值,交点数减少两个;当遇到最大的极大值时,扫描线与截面轮廓的交点数减少到零,此时扫描结束。将每条扫描线的交点按照x坐标从小到大进行排序。这样,每条扫描线相邻两个交点的x坐标,与该扫描线的y坐标合成填充矢量,构成了扫描线与轮廓区域的相交敬意,每个相交区间对应扫描线上的一条填充段。(3)充填矢量的提取从第一条交点数不为零的扫描线链表中提取最前的两个元素,与该条扫描线的y坐标合成一条扫描矢量,存入扫描矢量文件。然后,从下一条扫描线中提取最前的两个元素构成扫描矢量,如果该条扫描线的交点数与上一条扫描线的交点数不同,此时需要判断形成的扫描矢量是否还属于同一区域,判断的方法采用文献中的方法,即判断这两条矢量在x轴上的投影是否有重叠的部分。同时,每形成一条填充矢量,应从相应的链表中删掉最前的两个元素,头结点中的交点数减2。当处理编号为偶数的填充矢量时,应将矢量的起点和终点位置互换,倒置矢量的方向,从而形成往复扫描。逐条扫描线提取属于同一区域的填充矢量,直到下一条扫描线中已经没有属于同一区域的填充矢量或者该条扫描线的交点数已为零,此时,该区域的填充矢量已提取完毕。当一个区域的填充矢量提取完毕时,搜索极值点中与最后一条扫描矢量的y坐标差值最近的极值点。如果是极小值,则按照y坐标值增加的顺序提取扫描线上的填充矢量;如果是极大值,则按照y坐标值减小的顺序提取;如果扫描线上的交点数已为零,则查找另一个邻近的极值点,直到所有扫描线的交点数都为零,则该截面轮廓的填充矢量提取完毕。这样填充完一个区域之后,就可以找到距离最近的一个区域,有效减少了空行程的距离,提高加工效率。如图5所示为截面轮廓的填充过程,首先提取到第一条填充矢量,以y坐标值增加的顺序填充的区域Ⅰ区,填充完毕之后找到Ⅱ区的极大值,以y坐标值减小的顺序填充Ⅱ区;之后,以y坐标值减小的顺序填充Ⅲ区;最后,以y坐标值增加的顺序填充Ⅳ区。3扫描矢量的合成(1)在提取同一区域的填充矢量时,只是在扫描线的交点数发生变化时,才对填充矢量是否属于该区域进行判断;如果下一条扫描线的交点数不发生变化,表示没有空洞或凹点出现,提取扫描线链表最前的两个元素与y坐标合成的矢量,就是同一区域的填充矢量。这样大减少了扫描矢量的判断次数,有效提高了程序的运行效率。(2)文献中,各个区域的扫描顺序是按照每个区域的扫描矢量的最小y坐标值排列的,对每个区域扫描总是从最低的矢量开始,这样在一个区域扫描完毕之后,可能要有很长的“空行程”路线,见图6所示。这里对各个区域的扫描顺序是按照上一个区域的最后一个矢量的终点与