CAD模型面的拓扑缺陷检测算法的设计.pdf

《CAD模型面的拓扑缺陷检测算法的设计.pdf》由会员分享，可在线阅读，更多相关《CAD模型面的拓扑缺陷检测算法的设计.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机工程与设计 C o m p u t e r E n g in e e ri n g a n d D e s ig n 2 0 1 0，3 1(1 5)3 5 2 1 开发与应用 C A D模型面的拓扑缺陷检测算法的设计 胡超，徐 明华(江苏_ T-业学院 数理学院，江苏 常州 2 1 3 1 6 4)摘要：C AD模型在并行工程和协同设计环境下，在数据转换过程 中可能会产生多种数据缺 陷。针对这一问题，依据 C A D数 据 质量 标准，结合 C A D模型 面的拓扑 结构 的特点，对容 易引发 转换错 误 的反 向 的法 向、边缘 方位 不一致、微 小 面数 据缺 陷进 行 了分类和描

2、述。对前两类缺陷采用基 于向量内积及夹角来构造检测算法，对微小面设计了基于二分扫描线的检测算法。利用vc+和U G O p e r t A P I 开发 了面的拓扑缺 陷检测系统，并通过3个代表性的实例验证算法的有效性。关键 词：拓扑 缺 陷；C A D模 型；微 小面；二分扫描 线；检 测 中图法分类号：T P 3 9 1 文献标识码：A 文章编号：1 0 0 0 7 0 2 4(2 0 1 0)1 5 3 5 2 1 0 5 De s i g n f o r t o p o l o g y e r r o r c h e c k a l g o r i t h m o f CAD mo d

3、 e l f a c e HU Ch a o XU M i n g h u a (S c h o o l o f Ma t h e ma t i c s and P h y s i c s，J i a n g s u P o l y t e c n i c U n i v e r s i t y,C h a n g z h o u 2 1 3 1 6 4，C h i n a)Ab s t r a c t：I n t h e e n v i r o n me n t o f c o n c u r r e n t e n g i n e e ri n g a n d c o l l a b o

4、r a t i v e d e s i g n，C AD mo d e l ma y p r o d u c e a v a r i e t y o f d a t a e rro r s d u r i n g the d a ta c o n v e r s i o n p r o c e s s T o s o l v e t h i s p r o b l e m，b a s e d o n C AD d a t a q u a l i ty s t a n d a r d s an d t o p o l o g y c h a r a c t e ri s t i c s o f

5、C AD mo d e l f a c e，data e r r o r s s u c h a s r e v e r s e n o r ma l，the e d g e d i r e c t i o n i n c o n s i s t e n t an d t i n y f a c e wh i c h p r o n e t o p r o d u c e c o n v e r s i o n e rro are c l a s s i fi e d a n d d e s c ri b e d T h e p r o d u c t a n d t h e a n g l

6、e b e t we e n v e c t o r s a r e u s e d t o c o n s t r u c t c h e c k a l g o ri t h m f o r the fi r s t t wo e rro，a n d the b i s e c t i o n S C an l i n e c h e c k alg o ri t h m i s p r o p o s e d f o r the t i n y f a c e Us i n g VC+and UG Op e n AP I d e v e l o p the c h e c k s y s

7、 t e m o f f a c e t o p o l o g y e r r o r,an d c h e c k a l g o r i t h m i s v e ri fie d v a l i d b y t h r e e t y p i c a l i n s t an c e s Ke y wo r d s：t o p o l o g y e r r o r；CAD mo d e l；t i n y f a c e；b i s e c t i o n S C an l ine；c h e c k 0 引 言 在并行工程和协 同设计环 境下，C AD模 型的数据可在 各 种格式

8、如产 品模 型数 据交换标准(S T E P)或者初始化 图形交 换 规范(I G E S)之间进行转换，但无论是因为数据转换造成的数 据丢失还是 因为通用文件格 式结构缺 陷都会 导致 C AD模 型 的缺 陷发生。尽管企 业建立 了相应 的数据 建模规 范和标准，以支持产 品并行 设计与制造。但 由于 不同系统之 间和 用户操 作的精度偏差约 束不一致等，造成 了C A D模型产生 了各种数 据缺陷，而这些缺 陷可 能会 引起后续应用 的各种 问题。比如 模型中的微小边、微 小面及实 体在数据 交换过程 中容易丢失；面的法矢方 向存在反 向、面的边缘方位不 一致等。显然，机 械 的人工检测

9、不符合现代 设计的需求，特别 是对 于一个包括 成 千上万零件的装配体，仅凭人力来检测是不现实的。因此，设 计算法 实现对C A D模型数据缺 陷进行检测，对 于提高产 品的 设计质量有着显著的意义。我 国在 2 0 0 2年 推 出了 C AD C AM 数 据质 量方面 的 国家 标准(GB T 1 8 7 8 4 2 0 0 2)“。但是，由于各企 业需要 制定适 应本 行业 需求的 C AD模 型质 量标准 或规 范，故没有 得到确 实有 效 地执行。而 且，研究工 作主要 针对模 型 的几 何数 据缺 陷，而 对拓 扑数 据缺 陷方 面 的研 究很少。研 究人 员在 平面 上不 规

10、则多边 形 的面积 计算方 面进行 了较深 入 的研 究 2-3 1。文献 3】提 出了一个 基于 扫描线 方法 的不规 则多边 形划分面 积计 算 公式获 取算法。然而，在 面 向精密 仪器 生产、检 测等应 用 领 域的 C A D系统 中扫描 线算 法不 能直接使 用。因为不 仅存 在微 小边、微 小面、微小 实体 问题，且对面积计 算方法有 特殊 的需求：算法要求 很好 的交互性，能根据对象 不 同，满足 不同 的精 度要求。本文依据 C A D数据质量标准，结合C AD 模型面的拓扑 结构的特 点，对容 易引发数 据转换错误 的反 向的法向、边 缘方 位 不一致、微小面数据缺 陷进行

11、 了描述和分析，分别提 出了向 量 内积法检 测算法和二 分扫描线 的检 测算法。并利 用 V c+和 U G O p e n A P I 开发 了面 的拓 扑缺 陷检测系统。该检测系统 不 仅可 以避 免对 模型缺 陷进 行重复 的检 测，而且可 根据输入 的检测标准、误差，对模型的缺陷进行交互、批量检测。通过 模 型检测系统可 解决部分缺 陷人工难 以发觉 的问题，并可通 过 图示 和报 告的方式指 出模 型中存在 的问题。确保 下游 使用 者收 到的模型，尤其 是 已经投产 的模型 的质量。收稿日期：2 0 0 9 1 0 2 9：修订日期：2 0 1 0 0 6 1 8。基金项 目：江

12、 苏工业学院数理学科基金项 目(Z F 0 9 0 2 0 0 2 1)。作者简介：胡超(1 9 7 8-)，男，江苏睢宁人，硕士，讲师，研究方向为 C A D&C G；徐明华(1 9 6 5-)，男，江苏姜堰人，博士，教授，研究方 向为计算数学、控制与优化。E-ma i l：h c k 0 b e 1 6 3 c o rn 3 5 2 2 2 0 1 0，3 1(1 5)计算机工程与设计 C o m p u t e r E n g i n e e r i n g a n d De s i g n 1 基础理论 1 1 向量内积、夹角 设任意两个 n维向量。F=t，)和-，)，则 向 量a 和

13、p 的内积 定义为：(a S)=x,y i=x 。+。若a ，-a 砉 ,0=E C cos，称0 为 n维 向量a 与 B 的夹 角。这样，两个互相 垂直的 向量 的内 积 总是零。在计算 机 图形学 中利 用 内积可进行 向量方 向性判 断：两 向量 内积大于 0，则它们 的方 向朝 向相近；如果 小于 0，则方 向相反。1 2 扩展多边形 边不 自交且至少有一条边为 圆弧 的平 面多边形称为扩展 多边形。由圆弧构成多边 形的边称为 曲线边，其它边称 为直 线边，给 出如下 代数描 述：有 直线边，曲线边c，扩展 多边形 E P=f l j厶，厶)u c ，c：，c=，其中，是曲线方程，和

14、 为 曲线两端 点，为半径。1 3 扫描线算法 扫描线 算法 描述 如下：若扫 描线y=e 与 多边形 G P的边 一。相交，记其 交点的横坐标为 设。，“是该扫 描线 与多边形G P的边界各交点横坐标的递增序列，此序列具有如 下性质：在该扫 描线上，只有 区段)，=1，3，5，l-1 位 于 多边形 内，其余都在 G PP 。扫描 线算法充分利 用 了多边形 区 域的连续性、扫描 线的连续性和边 的连续性，避免对像素 的逐 点判断和反复求交运算，提高了算法速度。但在运用扫描线 算法 的过程中必须处理 奇点情况。2 拓扑缺陷分类及描述 拓扑结构描述 空间实体之 间的相关度，而壳、面、封 闭回

15、路、棱线、顶 点都属于拓 扑学空间实体，当这些 空间实体在 C AD模型 中定义不 明确，或者相互关联不合理，拓扑缺陷就会 存在。下 面介绍拓扑数据缺 陷的分类，对部分缺 陷进 行详细 描述 并提 出检 测算法。2 1 拓扑数据缺陷分类 结合 C AD数据质量 标准，根据 C A D实体模型 的表 达方 式及 C A D模型几何和拓 扑结构 的特 点，把模 型数据缺 陷分为 几何缺陷和拓 扑缺 陷两类。拓 扑数据缺 陷又 分为拓扑层 的精 度 缺陷、拓扑异构缺 陷及微小元素缺 陷。(1)拓扑层的精度缺陷：C A D模型中的拓扑对象界定与几 何信息是相关联的系统，所以说系统采用的精度会影响着模

16、型的拓扑数据。例 如常见的精度缺 陷：曲面之 间的裂缝或重 叠，如果是拓 扑层的裂缝，只需要通过 曲面重新求 交，然后重 设 参数就可 以纠正，不需要修 改底 层的数学定义。常见 的拓 扑数据 的精度缺 陷除了面与面 的裂缝，还有边 与边 的裂缝 以 及边 与顶点的裂缝。当出现两 条拓扑边相 交于顶点 时，由于 偏 差的影响，计算后 的顶 点与 实际交点有一定 的误 差。对于 这些误差可通过使用文献 5 的算法来求它们之间的最小距离，并通过判 断距离是否在给 定的误差 中来检 测。(2)拓 扑异 构缺 陷：拓 扑异构是指 C AD模型 中的模型拓扑 关系在计算机 中的描 述方法不同，因此在文件

17、 转换时，会 出现 拓扑不相容等 问题。在 C AD造型里，在定义有 界曲面时，如 果 出现不一致，在某些系统 中会导致面 的 自交问题发生。另 外，有界 曲面 必须满足切矢 或 曲率连续 的基本 条件，否则，系 统 或公差范围一旦发生变化，拓扑关系可能会丢失，或者增加 了一些新 的缺 陷。对 一个实体来说，对其表面 的法 向矢量的 方 向进 行统一是必要 的，以便在工 艺设计 中确定铣 削的加 工 方 向，通 过表面法 向确 定零 件的装夹方位 等等。限于篇幅，本 文 中主要讨论 反向的法向、边 缘方位不一致这两种缺陷情况。(3)微小元素缺 陷：微小元素 主要指微小 的边、曲线、面等，受接

18、口和 系统 内部参数 的精度等级 的影 响，微小元素可 能在 数据交换 时出现丢失现象。微小元素 问题往 往与计算机辅助 设计过程和 实体 的可 实现 性密切相关。对 于微小边和 曲线 可 以归纳在拓 扑层的精度缺 陷中检 测，即检测微 小边和 曲线 的两个顶点 间距 离是否在满足给 定的误差 中。故 在微小元素 缺陷中，本文主要讨 论微小面 的检测。为了确 保 C A D模型 的完整 性，有效 的修复 C AD模型缺 陷，我们必须对缺 陷的根源进行描述和分析，进而设计 出对应 的检测算法。2 2 缺陷描述及检测算法 C A D模 型拓扑数据缺 陷的表现形式 多样，通 常有悬面、悬边、曲面裂缝

19、、反 向的法 向、边缘 方位不一致及微小面等缺 陷。前面 3 个 缺陷很容易观察 到，而后面 3个缺 陷需要设计 算法 检测。下面结合 C AD模 型中拓扑数据 的特 点，对后 3 个 缺 陷进 行详细描述：(1)反 向的法 向 在一组相邻的面集合中，保持一致的法矢朝 向，在工程应 用 中非常重要，例如确定铣削 的阴影描绘，或定义测量接触表 面都要求有统 一的法矢朝 向。检查是否具 有一致的法 向准则 前，首先计算 需要 的拓 扑信 息。使用拓扑信 息判断每个连接 的区域 中面法 线的方 向是否一 致，记录其方 向偏离多数面法 线的那些 面的法线。反 向的法 向示例如 图 1 所示。检测步骤：

20、1)按面特征遍 历模型，获取面标识并在每 个面上取一点(不在边 界上)，分 别记为P。，。2)将上述 点进行如 下的凸组合，得到一个参考 点P =(尸 t+P +P 3 3)计算 向量P P,与点P 所 对应 的面法 向量蔬的内积P P,蔬，结合 1 1中向量 内积、夹角基础理论可知：若 内积 大于 0，则认 为 指 向外面，否则指 向里面。4)根 据指 向里面和指 向外 面法 向的统计 的个数多少，输 出指 向较少 的(如果个数相 同，输 出指 向里面的)法 向对应面的 标识、法矢位 置点及法 向矢量 值。(2)边缘 方位不一致 在C A D造型里，棱线、曲线、封 闭回路及面等都是有方 向

21、的。在 定义一个有界 曲面时，拓扑数据 结构中包含 了一个专 门的标识来指 明曲线和 棱线的方 向是否一致，如果不一致，在 某些 系统 中会导致不希望 出现的 曲面 自相 交和退化。边缘方 位不一致示例 如图 2所示。检测步骤：胡超，徐明华：C A D模型面的拓扑缺陷检测算法的设计 2 0 1 0，3 1(1 5)3 5 2 3 图 1 反向的法向 图 2 边界曲线的旋转方向 1)取独立片体上一点尸(要求不在边界 曲线上)以及法 向量而；2)边 界曲线 的任 一段(线段或 弧)，设起 点为，终点为，计算 向量，与 向量P B 的叉乘(向量积，x P B,，得到 向量，i=1,2，”；3)计算

22、向量 与 向量而 的内积；4)若上述 内积均小于零或均 大于零，则独立片体 的边界 曲线的方 向一致，否则不一致，据此可 以将方 向相 反的那 些边 缘 的标识 T a g输 出。(3)微小面 给 出微小面 的描述：如果模型 中一个面 的面积 比较 小，小 于一个指定 阀值，则称该面为微 小面。计算给定 模型 的每个 面的面积。如果面 的面积小于指定 阀值，则发生准则冲 突。设计 算法 实现 遍历 实体 和片 体上 的所有 面并 计算 其面 积，对于每一个面判 断是否符合微 小面的定义。若存在微小 面，则高亮显示 该面的边界，输出下 限约束 值、微 小面的标识(T A G值)及面积。关于多边形

23、面积 的计算，文献 2 和 3 提出了检测方法，但 在实 际应用 中由于检测 的对 象是 C A D实体模 型，其特 征类型 多且复杂，也存在微小边，微小区域及端点的实数坐标问题，原扫描线算法不能直接使用，因此，需要对原扫描线算法 改进，提 出了二分扫描线算法。下面先 介绍算法对应的数据结构。3 算法数据结构 下面将应用边表和活性边表，建立适合应用于 C AD 模型中 微小边、微小面的数据 结构，并给 出Y桶表及活性边表 的描述。3 1 数据结构 结合 C AD模型 的特 点，给 出模型 的边 结构体E DG E 描 述，边结构体保存扫描 线算法中需要 的边信 息，其结构用 C+语 言定义如下

24、：t y p e d e f s t r u c t E D G E fl o a t x：边上具有较 小 Y坐标 值的 X坐标 fl o a t y mi n，y m a x；边的最小、最大顶 点 Y坐标 fl o a t d x；直线 的斜 率的倒数，满足关 系：A x=d x A Y，y为当前扫描线 间距2 E D G E*p n e x t；指 向下 一条边的指针 i n t s g n；边 的类 型 fl o a t a,b，r；圆弧中心坐标和半径 E D G E；3 2 Y桶表及活性边表 基 于上述 的边结构 体 E DG E，分别给 出 Y桶表和活 性边 表描述。(1)Y桶表：Y

25、桶表存储所有边，每条边按边中较小的Y 值 依次存入桶 中的相应位 置，在 同一行 中按x的值和增量排序。用 一指针数 组定义实现：E D G E Y【MAx ；数组元素为指向各边表的首边 的指 针。(2)活性边表：活性边 表是一个 动态 表，包含一组与 当前扫 描 线相交 的所 有边，并 按边与扫描线 的交点 X 坐标 值递增排 序，指 向活动边表 首边的指针 定义为：EDGE AET；在活 性边 表中，边 结构的 数据成员就 是边与当前扫描线 交 点的 坐标，而交 点的 坐标 就是当前扫 描线的Y 值。因此，遍历整 个活性边表，就可 以很 容易求得 当前扫描线上 的所有 交 点，并且 交点是

26、按从左 到右 的顺序排 列 的。4 微小面检测算法 依据上述给 出的微 小边、微 小面 的数据结构，结合 Y桶 表、活性边表 的描述，给 出微 小面检测算法。4 1 数据 处 理(1)坐 标二维化：按面特征类 型对 C A D模型进行遍 历，获 取其所 有的面标识号及各 面的类型；再根据边特征遍历各面，继 而可获取边 的类型及顶 点信 息。对 C AD模型 中当前面的 各 顶点三维坐标 进行二维化 处理，即转化为 二维坐标。这样，当前 面就转化成 一个多边形 并转换到屏幕 坐标系下。设转换 后顶 点为P。，对 多边形中每条边转换成边结构表示，并 插入 到 Y桶 中。(2)奇 点处理：应用扫描线

27、算法需要解 决两个取舍 问题：扫 描线 与多边形顶 点相交时交 点的取舍 问题；多边形边界 附近 区域 的取 舍 问题。前 者保证交 点正确 配对，后者避免获取 区 域 的扩大化。将边界上 的点也看成交 点，这 样 问题合二 为一。由多边形 的连续性可知，每 一条扫描线 与多边形边 的交 点个数是偶 数。但是 当扫描线 与多边形边 的交点是多边形 的 顶点时(该顶 点称为奇 点)，若是把每个奇 点简单 的计为一个 交点，则交点个数可 能出现奇数。可通过如 下方法来判断奇 点：对 于顶点只，设其 y 坐标为Y ，与其相关联边 的另外端点 y 坐 标分别 为，若满 足 一 一 f)+10，则称P

28、为极值 点(如 图 3中的P。P：P，尸 5)，否 则，称只为非极 值点(如图 3中的只，)。由于本 文 中讨论扩 展多边形，可能 出现 扫描线与圆 弧 相切 的情况，这 时，也认为切 点为极值点。在存在 奇点的情 况下，为保证扫描线算法 的适用性，规定 当奇点是极值 点时，该 点按照两个 交点计算，否则，按一个交 图 3 多边形 的奇点处理 3 5 2 4 2 0 1 0，3 1(1 5)计算机工程与设计 C o mp u t e r E n g i n e e r i n g a n d D e s i g n 点计算。4 2 检测算法 在 2 2 节中提到对微小面检测 的二分扫描线算法，

29、下面 结 合 图示介绍算法 的设计过程。(1)算法 描述 二 分扫 描线 算法 就 是把 原扫 描线 算 法 中间距 修 改为2 (4 尼 0)中任一个 数，即间距是可调 节的。根据检 测对象不 同，选 择合适 的k，把 多边形区域分割 为多个小梯形 和三角形 区域。依据 算法中选择 的k 和对应分 割的区 间端 点，很容易计 算 出小梯形 和三角形 区域面 积。这样，可通 过判断两次不 同k 所计算的多边形面积误 差是否满足给定 的精度要求 来决定是 否继续分割。由实例测试经验可知，k 的最佳选择顺 序为 O，一 1，-2，一 3，-4。根据 多边形边 的端 点y 坐标范 围和扫描线间距可确

30、定 向 扫描线个数。再通过获取边 的类 型和奇 点规 则很容易求 出扫 描线 与边的系列交 点。对该交 点矩 阵 中的交 点按扫描方 向进 行有序排列，对其每一条扫描线的 矬 标重新排序，即可确定 所有 的在多边形 区域 内的扫描线 区间。这样，由相邻两扫描 线 区间端 点及 扩展 多边形的边所 围成 的三 角形和梯形形状面 积就可 以计算 出来，继而求 出多边 形的总面积。重 新取k，重 复上述操 作。根据相邻 两次k 的取值，对应总面积 的计算误差 大小是否满足给定 的精 度要求，决定是否进行下一次逼近。当 然，也可根据 需求，自行设定k 值，一次计算输 出结果。(2)算法设 计 依据上述

31、算法 描述，给出算法设计 步骤：步骤 1：多边形边的加载，确定y 向区间范围。取数 据处理后 的多边形所有边 的顶点二维坐标数 据，并 根据坐标求出多边形所有边 的端 点中y 坐标最 小值、最 大值 分 别为 蜢)。设扫描 线 间距 为2 ，则 向扫描线可 表示 为 In+i 2 ，(O，l，m)，其 中，m=v m _m)，2 。步骤 2：置活 动边表 A E T=N U L L；若单独设 定k 值检测，则 算 法执行一次结束。否则从k=O，即扫描线 间距为 1 开始。步骤 3：对 每一条扫描线i=完成 以下 操作：1)对 A E T表中所有边 的 =f 的边表，其 值 增加一个增 量 A

32、x=d x 2 。2)对 A E T表 中所有边 的 =f 的边，按边 的 值大 小插入到 A E T中；详 细求交过 程如下：设第i 条 句扫描线共与n 条边相交，与第，条边的交点为(x )，第，条边的两顶点坐标分别为(、(一 f)。若 s g n为 1，边 的类型是 直线，则劫=-J O 一 再)，十 f。若s g n 为0，则扫描线与 圆弧相交，由4 1 数据处理 中可知，圆弧 的 中心坐标，6)、半径，可 以获 取到，再根 据圆 的标准方 程 一+(y 一 6)=，很容 易求出扫描线 与圆弧 的交 点。这样，所有的扫描线与1 条边求交，可得到交点矩阵 )(f=0，l，m，：0，1，一1

33、)。对该 交点矩阵 中的交 点进行奇 点处理，按 扫 描方 向进行有序排 列，即可得到第i 条扫描 线在多边形 内部 区域的各区 间端 点。步骤 4：向、】，向两两依 次连 接各 区间端点坐标，就形成 了若干个三角形和梯 形区域。三角 形和梯形 的高均为 扫描线 间距2 ，结合对应面 积公式，很容易计算 出在区域 内的相邻扫 描线围成的梯形和三角形面积。这样，扩展多边形总面积就 可 以计 算出来。步骤 5：取后 =k-1，重复步骤 3 和 步骤 4操作，计算 出七 对 应 的扩展 多边 形总面积。这样，算法可根据相邻 两次面积 的计算 结果之间 的误差 大小是否满足给定 的限定条件，决 定是

34、否进行下 一次逼近。事 实上 影响这部分计算量 的主要 因素是对计算精确程度的要求。5 实验结果及分析 基于上述各缺陷检测算法，采用 v C+和U G O p e n A P I 设 计 了面拓扑数据缺 陷检 测系统。通过 U G OP E NMe n u S c r i p t 建立 了工 具栏和菜 单，实现与 U G界 面融合，也方便用户操作。面拓 扑数据缺 陷检测 界面如 图 4 所示。图4面拓扑数据缺 陷检测界面 在 图 4的检 测界面上可 以根 据检测需求实现 3 种检 测项 目的切换检测，提供 了交互和批量两 种检测方式。对应微 小 面项 目检测中，误差精度可以直接输入或指定k 值

35、快速计算。如 图所示，当前面积 阀值 为 2，误差精度 为 O O 1。检测 结果提 供 了图形 化和列表框两种 方式显示数据，并且支持保存数据 到 日志文 件或数据库 中。在 图形化输 出中提供 了检测前 实体 图、线框模式 图及检测后效果 图，各检测项 目检测效 果图如图 5所示。图 5(a)是边缘方位检测项 目对 应的模型实体图，而 图5(d)(a)(b)(c)(d)(e)(f)图 5 模型各检测项 目检测效果 胡超，徐明华：C A D模型面的拓扑缺陷检测算法的设计 2 0 1 0，3 1(1 5)3 5 2 5 是其检测结果。从检 测效果 图上看，模型 中有 B C、DE、F G及 H

36、 A共4条直线，、bc、G 日共4条圆弧，根据检测算法检 测 出圆弧DC 方 向与其 它圆弧不一致，则使用虚线 红色箭头标 出其方 向，另外 3条圆弧方 向都用黑色实心箭 头输 出。图 5(b)是 由 6 个面组成 的汽车覆盖件模型实 体图，从图 5 (e)的检测效 果图中可 以看出共有 3个面 的法 向指 向覆 盖件里 面，3个面法 向指 向外 面。根据检测算 法当指 向个数相 等时，用虚线红色箭头 输出指 向覆盖件里 面的法 向，而指 向外面 的 3 个面法 向都用黑色实心箭 头输出。由于微 小面检测项 目中的模型很 小，为 了能更好地描述 检测过程，在 检测前对模型 实体进行放大 1 O

37、倍显示，对应 的 模 型实体图如图 5(c)所示。图 5(0的检测 效果 图是k 取 3时，微 小面 所对 应扩展多边形 的分割情况。根据微小面检 测算法 中步骤 4操作，扩展多边形 被分割成 3 个 三角形和 2 O个梯形 区域，最终输 出的面积 为 1 8 9 8。这和直 接用 UG软件 测量的 结果 1 8 9 8 0 4 2是一致 的。通过 查看 日志文件 中k 取一 2时，计 算 输 出的面积 为 1 8 9 2，误差 为 0 0 0 6 0 0 l，可知计算结果也满 足 精度要求。根据 给定微小面积 阀值，可知标识 号为 2 5 0 8 8的 面是微小面。上述给定的3个代表性的模型

38、实例检测结果，较好地说 明了算法的有效性和 可行 性。同时，设计检测算法 时也充分 考虑 了通用性、扩展性、移植性，仅使用 了和数据输入、输 出相 关 的 U G O p e n A P I 函数。所 以，只要通 过统一 的接 口规范，该 系统就可 以轻 松移植到其它 C A D平台。6 结束语 本文 对 C A D模型 中反 向的法 向、边缘方 位不一致 微 小 面 3个拓扑数据缺 陷进 行 了分类和描 述，并提 出了对应 的检 测算法，特别 是基 于传统 的扫描 线算法改进 的二分扫描线算 法。二分扫描 线算法不仅 实现可动态调 整扫描线 的间距，适 用 于快速求一般 C AD模型 的面积

39、，而 且也适用于求 计算精度 要求高的微小面积。当然，要求的计算精度越高，计算所耗费 的时间也就越长。最后，依据算法开发 了可视化 的 C A D模 型 缺 陷检测 系统，实现 自动检测模 型中 的缺 陷，这对于大 型的 C AD模 型检测有很大 的优势。微 小面检测 算法局限性主 要体 现在适合 对边界 由直 线和圆弧组 成的平面检测，对边界是抛 物 线或双 曲线 的平面检 测算法还有待 于进一步完善。参考文献：1 G B，r l 8 7 8 4 2 0 0 2，C A D C A M数据质量 s】中华人民共和国国 家标准【2】郭尚，苏鸿根 基于像素的计算大量连通区域面积的快速算法 J 计算

40、机工程与设计，2 0 0 8，2 9(7)：1 7 6 0 1 7 6 3 【3 刘勇，徐从富，陈卫东，等_ 带圆弧简单多边形的面积公式获取算 法 J _ 计算机辅助设计与图形学学报，2 0 0 5，1 7(4)：7 4 8 7 5 3 【4】Y a n g J，Ha rt S H，P a r k S H A me t h o d f o r v e rifi c a t i o n o f C AD mo d e l e r r o r s J J E n g D e s 2 0 0 5，1 6(3)：3 3 7 3 5 2 5】胡超，徐明华 U G模型零件间最小距离检测算法的设计及应 用

41、J 江苏工业学院学报，2 0 0 9，2 1(3)：5 1 5 4 【6】尹卫星，胡青泥，齐晓松，等 改进 C A D模型数据质量的研究 J 机械工程师，2 0 0 6(2)：3 9-4 0 【7】Y a n g J,Ha n S H，P a r k S H,e t a 1 I n v e s t i g a t i o n o f p r o d u c t d a t a q u a-l i t y i n t h e K o r a n a u t o mo t i v e i n d u s t r y J T r a n s S o e C A D C A M E n g，2 0 0

42、 4，1 0(4)：2 7 4 2 8 3 【8 周敏，邓学雄，陈君梅uG二次开发技术及其应用【J 工程图学 学报，2 0 0 5(5)：4 2-4 4 9】郑战光，潘淑琴，夏薇，等 利用 MF C进行 U G二次开发研究 J 计算机工程与设计，2 0 0 7，2 8(2 3)：5 7 8 7 5 7 9 1 (上接第 3 5 2 0页)当两个参 与 比较的两个 时间序列长度较 长时，运算 效率的提 高更 为明显。4 结束语 本文 在现有D T W算法 的基 础上，通 过事先构造好 的查找 表来保存部分 限制 信息，避 免了该算法 中每前 进一步都要 计 算限制信 息的重复操作，从 而在一定程

43、度上提高 了运算效 率，这在理论上保 证了改进 后的算法 比原算法 具有较高的运算效 率，当参与比较的两个时间序列长度较长时，改进后的算法在 参与比较 的两个时 间序 列长度较长 的情 况下运行，运 算效率 的提高效果更为 明显；通过在相 同的实验 环境下，对 长度 不同 的时间序列进行实验，并把所消耗 的时间进行对 比，对 比结果 也表 明改进后 的算法在参与 比较 的两个时 间序列长度较 长的 情况下运行，运算效率的提高效果更为明显。参考文献：【1】李邵梅，刘力雄，陈鸿昶 实时说话人辨识系统中改进 的DT W 算法 J 计算机工程，2 0 0 8，3 4(4)：2 1 8 2 1 9 翁颖

44、钧，朱仲英 基于动态时间弯 曲的时序数据聚类算法的研 究 J 计算机仿真，2 0 0 4，2 1(3)：3 7 3 9 Be md t D J,Cl i ffo r d J Us i n g d y na mi c t i me wa r p t o find pa t t e n s i n t i me s e rie s【C】A A AI Wo r k s h o p o n Kn o wl e d g e Di s c o v e r y i n Da tab a s e AAAI P r e s s，1 9 9 4：3 59-3 7 0 潘定，沈钧毅 时态数据挖掘的相似性发现技术 J

45、 软件学报，2 0 0 7，1 8(2)：2 4 6 2 5 8 何强，何英 Ma t l a b扩展编程【M】北京：清华大学 出版社，2 00 2 H e t t i c h S，B a y S D T h e UC I K D D ar c h i v e E B O L I r v i n e，C A：Uni ve r s i ty o f Ca l i f or ni a，De p a r t me n t o f I n f o r ma t i o n a nd Co m-p ut e r S c i e nc eht t p：kd d i c s u c i e d u，1 9 99 贾澎涛，何华灿，刘丽，等 时间序列数据挖掘综述【J】_ 计算机应 用研究，2 0 0 7，2 4(1 1)：1 5 1 7 吴晓婕，胡占义，吴毅红 基于 S e g me n t a 1 D T W 的无监督行为序 列分割 J 软件学报，2 0 0 8，1 9(9)：2 2 8 5 2 2 9 2