CAD模型修复的保结构

《CAD模型修复的保结构》由会员分享，可在线阅读，更多相关《CAD模型修复的保结构（12页珍藏版）》请在装配图网上搜索。

1、CAD模型修复的结构维护摘要有两种主要方法转换镶嵌的CAD模型，它们所包含的不一致就像存在于流 形封闭三角形网格中的缝隙或自交叉。面向表面算法通过扰乱部分输入尝试修复 不一致，但他们往往不能处理特殊情况。另一方面体积算法产生有保证的流形网 格，但由于全球重采样大多输入镶嵌结构被破坏。在本文中，我们将结合这两种 方法的优点：我们利用素网格拓扑的简洁性在自交叉和缝隙附近重建一个已清 理的表面，但在远离这些不一致的区域保留了输入的镶嵌性。因此，我们能够保 留可能存在于输入镶嵌结构的任何特征（即iso参数或曲率线）。我们的算法缩 小缝隙至用户定义的最大直径，解决自交叉、处理不兼容的补丁取向并生成保持

2、在输入模型容错范围内功能敏感的流行输出。简介今天CAM生产环境的一个共同难题具有不同的几何表现，它一方面采用CAD 系统，另一方面采用下游应用程序。而CAD系统通常代表一个模型通过一套被 整理的NURBS补丁或其他表面基元（可能是从CSG代表提取的），下游应用程序 如计算流体或结构仿真，快速原型和依靠封闭一致的流形三角形网格作为输入流 的数控加工。从一个到另一个表示的转换不仅要考虑时间是一个主要瓶颈,而且 也要考虑输出的准确性和质量，这直接影响所有后续生产阶段。常见的镶嵌算法可以有效准确地将单一表面基元转换成三角形网格，但通常 不能处理不同原语之间连续性限制或检测和解决交叉几何。这导致工件像缝

3、隙、 重叠、交叉或方向不一致的镶嵌补丁一样，往往不得不进行手动修复和繁琐的后 处理步骤。由于这个原因，已投入相当的努力使算法能够自动修复这种模型。有两种主要方法转换镶嵌的CAD模型，它们所包含的不一致就像存在于十 净流形三角形网格中的缝隙或自交叉。面向表面算法设法明确地计算或识别（子 -）补丁，它们是通过临时边界元素缝合在一起的。这些算法输入补丁变化很小， 但由于数值问题不能保证输出网格的一致性，因此通常需要用户交互。另一方面 体积算法使用一个标志距离网格作为中间表示，能够保证流形重建。不幸的是， 由于全球重采样这些算法破坏了输入镶嵌结构。此外，该决议的基础网格限制了 重建质量。在本文中，我们

4、结合这两种方法的优点：我们利用素网格拓扑的简洁性在自 交叉和缝隙附近重建一个已清理的表面，但在远离这些不一致的区域保留了输入 的镶嵌性。因此，我们是能够保留可能存在于输入镶嵌结构的任何特征（即iso 参数或曲率线）。我们的算法缩小缝隙全用户定义的最大直径，解决自交叉、处 理不兼容的补丁取向并生成保持在输入模型容错范围内功能敏感的流行输出。其基本思路是，首先确定包含像文物一样的缝隙和重叠的关键区域，然后有 选择地在这些地区运用体积重建算法，最后将未修改外部元件加入重建。由于其 选择性我们的算法一方面能达到较高的网格分辨率和文物附近的较高的重建质 量，另一方面也不会引发全球重建算法的输入的性能开销

5、。图1：我们的算法将镶嵌的CAD模型转换成一个无交集和封闭三角形网格，它 涵盖所有的差距达到一定规模。左：输入补丁被创建通过由385个修剪NURBS 曲面组成的镶嵌CAD模型。中：一个标准体积重建算法在全球重新取样并销毁 镶嵌结构。右：我们的算法仅在本地文物附近重新取样比如缺口和交叉点，因此 保留了大部分输入镶嵌。2.前期工作基于表面算法直接在输入镶嵌上工作并使用大量技术来检测和解决文物。这些技 术包括，例如：相互捕捉边界元素，投影和插入边界边成面，明确计算面之间的 交叉，补丁之间正常领域的传播BW92, BS95, BDK98, GTLH01，MD93，小 块补丁拼接缝隙TL94，Lie03

6、，通过识别和切割处理GW01解决拓扑噪声等。基于表面的方法只能在文物附近小范围地区修改输入的几何形状。因此，尽可 能保留输入镶嵌。然而，这些方法通常不能提供任何输出质量担保：有可能没有 全球一致的定位输入补丁，一些文物比如重叠几何或“双墙”很难处理交叉点 是很难发现和解决的；这是由于一个健全和有效实施的数值问题是一项挑战。面向体积的方法转换成输入体积的表示，即一个标志距离领域或定向网格的距 离NT03，Ju04，FPRJ00。从这个立方体表示提取表面使用类似移动立方体 LC87, KBSS01或双轮廓Gib98, JLSW02, Ju04技术。体积技术生产保证流形 输出。此外，拓扑文物和孔可以

7、使用不同的过滤器操作轻松删除ABA02， DMGL02，NT03。算法我们算法的输入是一个镶嵌的CAD模型M0 = P1,.,Pn它由n个元素Pi组成。 每个元素Pi是一个流形三角形网格,并通过元素的ID i唯一识别。此外，规定误差 极限口0和最大直径误差口0。输出是一个无交集的封闭三角形网格T，它接近 M0达到最大误差口0并且所有缝隙的直径 =口0。我们的算法进行几个阶段（见图2）：转换M0到封闭网格M （第3.1）确定一个关键点的集合封闭所有的交叉点和所有直径缝隙（第3.2）使C削减至一个最小的集合（第3.3）将C0转变为关键顶点集合D，它封闭所有缝隙和所有交叉（第3.4）对D削减M （第

8、3.4）在D内几何模型的重建（第3.5）7.后处理，以减少输出的复杂性（第3.6）1.输入修补程序4.剪辑图2：我们算法的阶段。们2.关键点3.关键的单元格5.初试.重建6.结果输入修补程序通常像展览文物的缝隙和交叉（1）我确定一（较大）关键点，在附近围绕这些文物（2）然后将这些顶点转换为一组（较 小）的关键单元格（3）输入被剪切的关键单元格的修补程序（4）,单元格的内部重 新构造使用变量行进的立方体算法（5）初步重建，然后将之简化，获得最后的结 果（6）请注意，请注意几何模型远离文物不受我们的重建算法的影响，因此任何 结构中，输入修补程序是完好的。3.1.安装程序下面我们假定二不失一般性，对

9、输入模型进行缩放和翻译，这样的错误误差 0= 1，并且一个整数网格的范围使M0对于某些k是封闭 的。注意:格子的大小就等于误差差值口0。我们还假设给出最大差距直径口0 = 2口 口为正整数。我们经常通过网格顶点或网格单元格的小的集合将数据相关联。为提高内存效 率，这些数据被存储为深度为k的八叉树的最优结点。八叉树是自适应改进需求 的，例如当我们访问网格顶点或网格单元格时。对于每一个修补程序-.，通过复制Pi和扭转每个三角形的方向设定一个镜像修补程序-。然后我们沿着 三角形的交界的共同边Si合并Pi和-。增量是一个新的封闭的修补程序Qi它 通过共同边表示Pi。我们在新模型、=二-中集合新的修补程

10、序。注意：M是 封闭的，但对于M0仍包含在的同一文物中。还要注意的是，以此构筑的算法 输入的修补程序方向不变。如果事实证明，由此产生的“双墙“没有必要保证主 结构的重建，他们将在后处理阶段被删除，见第3.6节。3.2.关键区域接着我们计算一个关键网格顶点的集合Cg。我们认为，这些关键点作为颗粒填 充两个或多个修补程序M的空区域使之更接近2口。这些关键的地区包括所有直 径=2 口的缝隙，特别是所有不同修补程序的交点。该算法的后期将提取面之间 的关键和非关键顶点来创建表面修补程序，实际上缩小了缝隙并解决了交叉。11 -是由两个或多个修补程序M相交的如果1我们认为网格顶点，-是模糊的。如果v是一个模

11、糊顶点，我们设置所有关|牛=u g时V）一.-。图3显示了 M的一些配置和相应的模糊关键顶点。图3：patch ambiguous vertexcutsOcritical vertex 丘 G补程序是示例配置。一些修补程序：,的配置如上显示。请注意，每个修 个封闭的三角形网格。这些关键点作为颗粒填充两个或多个修补程序M的空区域使之更接近2口。切口有效提供附近子像素的准确性。模糊顶点利用一个深度为k的（临时）八叉树能够有效地定位。我们通过类似最优 级八叉树节点的中心的整数坐标；转移的八叉树的起点，即它们对应的网格顶点。如果n是八叉树的一个节点，我们通过L表示八叉树的中点，-表示八叉树的深度。因此

12、，如果n是一个最优级节点（dn = k）我们要检查是否通过两个或多个不同修补程序的相交。我们的想法是建立一个和八叉树层次结构相匹配的盒子嵌套层次结构。因此，如果n是一 个内部八叉树节点，那么包含所有子节点n的盒子Box（n）会被选定。一个简短的计算表明，通过让七- - 该属性是满足的。特别注意，一个三角形相交框中的一个最优级节点n也会和所有祖先n的框相 交。我们现在以递归方式向每个三角形M插入八叉树用一个类似Ju Ju04的算法。 从根节点开始，一个三角形被插入一个节点n如果它与Box(n)相交。这可以使用 分离轴定理GLM96有效地进行测试。如果一个节点n包括的三角形属于不同 的修补程序，n

13、被拆分，三角形被分发给其子节点。最后，一 I中心的每个 属于两个或多个修补程序的三角形的最优级节点n表示一个模糊顶点。为了提高附近关键区域的解决方案，我们还计算出每个关键顶点三从 拍摄光线M沿着坐标轴的直线距离(图3)。幸运的是，我们建立了上面的临时 八叉树已经提供了一个空间搜索结构来加快射线模型相交测试。如果我们发现一 个单位距离内的交叉点，我们用顶点v组成三元组，以三=为方向，以n I二I为距离作为切口。这些切口将 在以后用于几何结构体中所有点，的重采样。数字显示，切口用小箭头附加 到V并指向方向d来举例说明，请参见图3。3.3.侵蚀，在前一阶段我们计算一个集：的关键顶点，我们认为是填补所

14、有缝隙的粒子。算法的后期将提取边界C创建表面修补程序，实际上缩小这些缝隙 并解决了交叉。由于这些填充应尽可能少的改变M，所以C应该尽可能的小。 因此我们通过填充所有空隙的最小集，-替换C。我们通过对C应用拓扑维护侵蚀算子得到，即我们从简单的C开始先后删除关键顶点。(请注意我 们只能删除关键顶点但不是切口)。直观地，一个顶点称为简单点，如果删除不 会更改拓扑结构C，即如果它不创建或处理新的连接组件。简单点的确切定义， 以一种有效的方法确定一个顶点是否简单是从其26个邻居BK03中确定的。 然而，我们必须考虑，在我们的例子中切口代表物质，而在BK03切口代表空白区 域。我们的过程如下：对于每个关键

15、顶点V，我们计算它到边界：的距离d(v)。如果 v有一个非关键邻域，我们令d(v) = 0。其他关键点距离的计算是通过在代表切口的上距离变换实现的，即距离不会在一个切点上传送。然后，我们删除二 层简单关键点来得到一个新的关键点集合：(图4(左)和图5)：层=0,1,., ?对于所有d(v)=层的顶点v，如果V是简单的那么设置V为非关键的。正如下面 的重建工作将沿着切点发生，切点应在非关键点和关键点之间。此外，切点不在顶点， 和M之间（图4（右）和图5）。因此，如果V是一个关键点，我们会删除所有切点和而不是向所有关于V的非关键的6个邻域W中插入切点。在这里，来表达重建算法的是一个特殊 值，.：.

16、,对应于一个填充并且相应的顶点在后处理阶段应该是平滑的。图4：侵蚀。左图，我们看到集合：的关键顶点填补了两个修补程序之间的空 隙。绿色顶点已被拓扑维护侵蚀算子删除。没有断开的两个修补程序不能删除红 色顶点。右图：每个剩余（蓝色）顶点被替换通过指向顶点的切点。现在所有的 切点形成面，在算法的后阶段被提取用来填补表面修补程序的缝隙。口关键单元格 属于：的关键点 -1 -删除切口 心 额外切口 图5：示例配置（续），拓扑维护侵蚀算子（3.3节）缩小到对于一个由额外 切点包围的较小集合。网格单元格是与属于的关键顶点相邻的或和被标记 为关键的多个修补程序相交的（3.4节）。3.4.剪切在这一阶段，我们将

17、一个关键的网格单元格D集合将M剪切成一个内部和 一个外部组件，内部组件包含所有组件的模型。然后丢弃内部组件，取而代之的 是一个如3.5节所描述的完好重建。首先，我们要确定关键网格单元格D的集合。D应包括M的所有组件，即 所有的交叉点和所有的缝隙，我们设定这个网格单元为关键的，如果它包含M 的两个或多个修补程序（交叉点）或如果其事件顶点之一是关键的（缝隙）图5显示了 M的某些示例配置和它们相应的关键网格单元格。下面，我们 将表示一个网格面为关键，如果它共享一个非关键和关键的单元格。网格边称为 关键事件，如果事件是一个关键面。其基本思想是分裂沿着关键面M的所有三角形为子三角形，这样每个子三 角形要

18、么完全在关键区域D的内部要么完全在关键区域D的外部。然后，我们 简单地抛弃那些完全位于内部的三角形。虽然相交平面的数学问题简单，而实际执行一个有效的数值模拟的裁剪算法 是一个困难的问题。下面我们将提出一个专门为我们设置的新的算法。在运行算法的所有时期内，网格将保留在三角形网格中。我们没有处理任意价的 一般多边形，包括孔等。实际上，我们仅仅使用欧拉操作拆分1-3和拆分2-4 （边缘剥离）来修改网格，并提供大多数网库的基本操作。通过使用一个混合定点/自适应精度表示顶点的位置，我们获得没有健壮性和 准确性的相对加速比。这三个阶段中的剪切收益在图6中说明。在第一阶段，关键边相交、模型面和 插入交叉点到

19、该模型使用1至3或2至4拆分。在第二阶段，相交的关键面和模 型边缘，再次插入相交点使用2-4拆分。这个过程会自动产生边，这些边是由 所有包含关键网格面的三角形模型相交产生的。因此每个三角形现在不是完全位 于关键单元格的内部就是完全位于关键单元格的外部。在第三阶段我们则只是丢 弃那些重心在关键单元格中的三角形。为了有效地枚举关键边和关键面，我们使用由朱报JLSW02提出的递归八 叉树遍历技术。然而，为了加快算法，在下降到八叉树单元格之前，我们首先测 试是否当前三角形真的与使用分离轴定理的单元格相交。初始配置第一阶段第二阶段第三阶段图6：初始配置：三角形网格就是对一组关键网格单元格进行裁剪。第一阶

20、段: 通过1到3次拆分或2到4次拆分三角形网格的交叉边被插入到网格。第二阶段: 通过2到4次拆分边缘网格和网格面的交集被插入到网格。现在每个三角形不是 完全位于关键单元格集合的内部就是完全位于关键单元格集合的外部。第三阶 段：内部三角形将被删除。执行如果交叉点被可靠地检测并正确地计算上述算法才能执行。然而，切换到 精确算法，算法会缓慢下来。出于这个原因，我们使用混合形式表示。将该模型 输入顶点的位置量化到N位。对于每个顶点v，我们将存储其确切位置I使用一种自适应精度表示Pri91 ,She97。及其近似位置使用一个固定的点表示N位宽度。例如，（请记住，网格的度为：）：I ：当计算交点时我们可以

21、使用近似位置评价“易排斥“。考虑例如一个边e和网格面f = fmin，fmax的交集。我们首先检查 是否与框 成 - r I 1:相交。这个 测试使用最大只有3N位的Ju04方法准确地评价定点算法。只有这次测试成功， 我们才能使用精确算法计算真正的相交点。类似的考虑也适用于三角形边相交、 边边相交、三角形单元格相交等。3.5 .重建现在，我们提出了一个算法来重构内部关键单元格的表面。这种算法使用特征元 素的敏感性移动立方体和由Kobbelt等人提出的双轮廓算法。但是，除了要功能 敏感外，我们的算法可以处理每个边的多个切点和外部几何在关键单元格内部重 建的无缝连接。我们首先枚举所有内部网格的面，

22、再次使用八叉树的递归遍历技术。对于每个内 部网格的面，我们收集位于这些面边缘的切点。请注意网格边缘可能存在两个以 上的切点，如果一个修补程序与该边缘相交多次。通过构造，切点的数量总是偶 数。此外，切点指向顺时针（CW）方向与切点指向逆时针（CCW）方向相互交 替。我们现在通过边连接这些切点：顺时针切点连接到下一个逆时针切点以逆 时针方式围绕网格表面（图7,左），也可以看。如果我们连接来 自同一网格边缘的两个切点，我们在面的中心处插入一个辅助点来防止拓扑退 化。请注意，通过构造，边不相交。然后我们依次访问每个关键单元格。创建如上所述的单元格表面的边或者是 外部几何边界的边。在任何情况下，这些边缘

23、在单元格周围形成一个或多个连接 循环。每一个循环通过三角形扇形成三角形（图7,右）。由于边不相交，循环 不会交叉所以是三角形风扇。图7：我们通过边连接切口到一个网格面上（左）。对于每个网格单元格，外部 几何体的边和边界边在单元格周围形成循环。每一个循环通过三角形扇形成三角 形（右）。风扇的中心顶点位置p的计算是取相交网格单元格中Lin00的三角形平面距 离的最小值。注意如果该单元格包含一个特征边或角，这种结构将确定p。如果 计算出点p碰巧超出该单元格，或如果它不在所有的支撑平面内，它将被设置 为无效。无效的顶点在后处理阶段是平滑的。最后，我们翻转内部网格面的边， 使中心顶点相连接。这可以保证邻

24、近单元格的特征顶点通过一个（特征）边连接（图 8）。平滑顶点。采样顶5置（续键网格单点中仰何体替换一个重建表面R，R 款方体算法提取的。图苹是从切点通过使用变进行采样。由过，其他对应于R的那些部分覆盖M的缝隙。这些顶点的位置是 由一个迭代的平滑筛选器决定的。R的一些顶点可以直接从M中3.6 .后处理平滑 之后的重建阶段处理以下类型的顶点的位置尚未确定。对应于重建部分的顶点跨越M的缝隙，因此没有确定的位置。这些顶点要么从切点分离出来要么在三角形扇的中心创建一个空的网格单元格。在网格单元中的三角形风扇中心的顶点包含冲突几何通常由于一个不足细 化深度k。在这两种情况下我们通过应用迭代平滑过滤器Tau

25、95平滑顶点位置。抽取 重建算法的输出是一个封闭的流形三角形网格T，它接近输入模型M 并已解决所有项目。然而，由于缝隙附近的人工细化T通常比M0包含更多的顶 点和面。这可以归因于两方面因素：每个修补程序的输入模型通过共同边T表示。基础网格的分辨率越高，在关键区域重建模型就需要越多的三角形。因此，我们有两个选择减少输出的复杂性。首先，网格T通常包括多个相关连 的组件，只有少数几个对M的外部有真正的作用。其他组件只是从内部被分成 三角形M，因此可以很容易地确定并丢弃。该标识可以通过洪水手动或自动填 充过程如Ju04。第二，我们应用一个标准功能敏感网格抽取算法到T GH97。 然而，为了保持M的输入

26、镶嵌，我们只能在重建地区这么做。4结果在大量不同复杂性的CAD模型中我们评价了我们的方法（图9, 10，11）。所有的节点被送到一个2 GB，3.2 GHz的奔腾4电脑上。输入参数的选择我们的算法只重构文物附近的地区和本地重建在后加工阶 段进一步被消灭，输出复杂性的典型增长通过次级线性体现网格决议。因此，我 们可以使用高网格决议来提高三角形重建质量而不会产生不必要的开销。如果输 入修补程序的镶嵌是足够准确地，我们可以设置 即使对于高决议也不会错 过任何缝隙。渐近行为如果工件形成一维子空间例如沿着两个相交表面或沿两个毗邻补丁， 关键顶点和单元格的数量关于网格决议对常数.在理论上呈线性增长。我们的

27、实 验结果与理论描述相吻合，只有相机模型（图10）是个例外因为它包括许多内 部几何和“双墙”。这些工件不能有效地得到解决，因此，关键点和单元格实际 上形成了一个二维或三维子空间。在这些地区八叉树不得不细化到最大深度，这 会导致内存使用量显著增加。Helicopter, 10 k triangles in 60 patches. y= Iresolution10243204S340时El砂Scritical Venice s242 k505 k1037 k2079 k#critical cells68 k141 k277 k561 k#oucput triangles28 k34 k44k60

28、ktime47 s116 s291 s868 sCamera, E k inangles in 83 patches 7= IrcsolulioT&#LrilEcat vertices192 k655 k1978 kttcrilical ceilE83 k270 k74k#oulpuL triangles33 k6 k81 ktime56 s145 s639 s图9直升机图10:相机5.讨论我们已经提出了一种新型高效的算法来充分自动选择性地修复CAD镶嵌 模型。不管怎样，一些问题仍然为今后的工作开放。工件的单一个修补程序 我们的算法能可靠地检测和解决工件之间不同的 修补程序。但是，它不能解决工

29、件的单一个修补程序，例如像自交叉。当然，我 们可以扩大我们的算法来处理这些工件，但会明显降低其性能。其原因在于，在 八叉树顶点的建设过程中，我们经常要检查一个特定的盒子是否包含两个或多个 修补程序。目前这项检查是非常快的，因为我们只需要比较与会三角形修补程序 的ID。但是，如果我们还想在单一修补程序中检测自交叉，我们实际上必须使 各个三角形与框中的所有其他三角形相交。这可以非常快的实现SAUK04，但 我们的模型没有自相交的修补程序，我们得出结论，这种情况在实践中并不经常 发生。如果是这样，用户必须手动将修补程序分离成非自交的子程序。？选择性 我们的算法只是修改模型的关键区域，即这些区域仍包括

30、缝隙和 交叉点并保留了各处的镶嵌结构。这些关键区域是完全自动地通过全球用户定义 的参数,来确定的。但是，它应该能让参数本地取决于底层模型几何体，并使不 同大小的缝隙更接近。它也可以适用于面向网格表面的修复算法，在预处理阶段 部分输入较大的流形修补程序，我们的算法只适用于那些面向表面方法失败的地 区。？重构我们使用一种新的网格轮廓算法重建关键区域的表面。该算法正确 地解决网格面附近切点基于本地配置的任意自交叉。但是，其他（可能是全局） 标准也可能会被纳入。例如，我们也许会争取一小种或一定数量连接元件的重建。 而标准网格的标志距离和行军立方体算法，已经通过Andujar et al等I盘：；的 探

31、讨。空间和时间效率 由于它的选择性，我们的算法已经被证明具有一定的空间和时间效率。在我们的实现过程中，我们已经使用了八叉树和网状数据结构的标准库 及准确算法和网格抽取框架的标准库。我们相信，我们能取得相当大的速度和更 低的内存如果我们使用特定的数据结构和算法代替。由于我们的算法只是在局部 信息上运行，它也应该可以很容易地推广到并行机上。Ventilator 269 k triangtes in 12 patches, y = 2图性贝1通风机IO24J20458192-ttcritical vertices23Sk460 k&28 k1649 kcritical cells64kI13k229 k523 k#ou(put triangles503 k512k529 k536 kLime83 s123 s193 s303 s