CN103914865B - 形成几何图案的面的组 - Google Patents

Abstract

提供了一种用于设计三维建模对象的计算机实现方法。该方法包括提供(S10)建模对象的边界表示；确定(S20)面的集合的子集，对于面的集合的子集来说，面是另一个的副本；在子集内形成(S30)第一组面，所述第一组面形成几何图案；以及关联(S40)至少一个第二组面到第一组面，对于第二组的每个面，其邻近第一组的各自面，以及对于第二组的每对面，其符合刚性运动，所述刚性运动将成对面所邻近的第一组的各自面转换成另一个。这样的方法改进了3D建模对象的设计。

Description

形成几何图案的面的组

技术领域

本发明涉及计算机程序和系统领域，并且更具体地涉及一种用于设计三维建模(3D)模型化对象的方法、系统和程序。

背景技术

市场上提供了用于设计、管理和制造对象的许多系统和程序。CAD是计算机辅助设计的首字母缩写词，例如，它涉及用于设计对象的软件解决方案。CAE是计算机辅助工程的首字母缩写词，例如，它涉及用于模拟未来产品的物理行为的软件解决方案。CAM是计算机辅助制造的首字母缩写词，例如，它涉及用于定义制造流程和操作的软件解决方案。在这样的系统中，图形用户界面(GUI)对于该技术的效率起着重要的作用。这些技术可嵌入在产品生命周期管理(PLM)系统内。PLM是指帮助企业跨越扩展企业的理念而共享产品数据，运用一般流程，并权衡用于从构思到它们使用寿命结束的产品开发的企业知识的商业策略。

由Dassau1t系统(商标CATIA、ENOVIA和DELMIA)提供的PLM解决方案提供了工程中心、制造中心、以及企业中心，所述工程中心组织产品工程知识，所述制造中心管理制造工程知识、所述企业中心能够使得企业整合和连接到工程和制造中心。该系统一起提供了链接产品、流程、资源的开放对象模型，以实现动态的、基于知识的产品产生和驱动优化的产品限定、制造准备、生产和服务的决策支持。

许多CAD系统现在允许用户基于提供给用户的建模对象的边界表示(B-Rep)来设计3D建模对象。B-Rep是包括面的集合的数据格式，每个面被定义为各个支持表面的边界部分。用户可以通过修改现有的面、创建新面、删去一些面、和/或定义面上和/或面之间的限制、或由CAD系统在使用时提供的任何行动而作用于面的集合。在这种情况下，为了效率，立体的历史通常对用户不可用。

发展中的这样的3D设计的方面之一被称为“图案识别”。术语“图案”是指相同的几何特征的副本的正常布局。识别图案在设计期间允许将这样的图案处理为单个元素，从而拓宽了一系列的设计可能性。举例来说，并非逐个修改图案的元素，得益于先前的图案识别，用户例如可以用单个动作而全局执行图案修改。图案识别涉及CAD的不同领域，诸如机械设计、消费品、建筑结构、航天或其他领域。

图案识别可涉及特征识别。特征识别对识别给定的3D对象(通常是表示机械部件的立体)上的特征形状有帮助。机械设计关注的特征形状例如包括孔、挤压垫、挤压凹处、圆角或圆、外卷垫和/或外卷凹处。识别特性形状相当于通过更好的语义层面来识别其规格，例如挤压或外卷形状的轮廓、外卷形状的旋转轴、圆和圆角的半径值、挤压方向、和/或挤压深度。该信息或者用于例如通过编辑挤压轮廓而修改形状，或者用于馈送到下游工序，例如加工工序。

通过以下步骤可在商用CAD系统中使用特征识别能力。用户可选择特征的类型以进行识别。然后，任选地，用户选择立体上特征的一个或多个面，以便初始化搜索。系统执行识别并得到识别出特征的规格。

当意图局部改变输入立体的形状时，也可使用“直接编辑”能力。这项技术(也称为“无历史建模”)由CAD编辑晋升为历史设计的替代物。目标是通过仅使用其B-Rep而容易地改变立体的形状。为了从用户角度来看使得编辑简单，“直接编辑”技术必须识别立体的局部形状。例如，该系统必须保持孔的圆柱形状(并不将圆柱改变为自由形式表面)，保持凹处的壁的垂直方向，和/或维持形状的外卷或挤压特性。因此，即使在“直接编辑”领域，特征识别也是不可避免的。

传统的特征识别一次处理一个特征。它不识别给定特征的多个副本，并且它不识别这些副本的布局。至于图案识别，该主题仍在开发中，但现有解决方案似乎需要很多的用户干预。

因此，现有解决方案缺乏效率，特别是从用户利用的观点和穷举的观点来看。在此背景下，仍然有必要设计一种用于3D建模对象的改进的解决方案。

发明内容

根据一个方面，因此提供一种用于设计3D建模对象的计算机实现方法。该方法包括提供建模对象的边界表示。边界表示包括面的集合，每个集合被定义为各自支持表面的边界部分。该方法还包括：确定所述边界表示的面的集合的子集，对于所述子集，面是另一个的副本。该方法还包括形成所述子集中的第一组面，所述第一组面形成几何图案。并且所述方法包括关联至少一个第二组面到所述第一组面。对于所述第二组的每个面，所述第二组的面邻近所述第一组的各自面。对于所述第二组的每一对面，所述第二组面也符合刚性运动，所述刚性运动将成对的面所邻近的第一组的各自面转换成另一个。

该方法可以包括下列一项或多项：

-对于关联，当所述刚性运动还将对应于一对面的支持表面转换成另一个时，至少在该对面邻近第一组的各个面的区域中，该对面被评估为符合将该对面所邻近的第一组的各个面转换为另一个的刚性运动；

-第二组面的数量大于第一组面的数量减去预定阈值；

-所述方法还包括关联至少一组面的块到第一组面，对于每个块，所述至少一组面的块是邻近所述第二组的各自的面的连接面的集合，以及对于每对块，所述至少一组面的块符合所述刚性运动；

-所述方法被迭代，在迭代中包含于所述第一组且关联到所述第一组的面针对下一迭代而被丢弃；

-在所述子集内形成第一组面包括：测试几何图案的预定集合之一的发生是否存在于子集内；

-该几何图案的预定集合包括循环定义的图案的集合：

-所述循环地定义的图案的集合包括一维图案和/或网格图案，所述一维图案包括线性图案和/或圆形图案，所述网格图案包括矩形网格图案和/或圆形网格图案；

-测试包括根据优先级次序浏览几何图案的预定集合；

-该几何图案的预定集合包括：圆形网格图案、矩形网格图案、圆形图案，以及然后线性图案；和/或

-测试包括根据优先级次序浏览几何图案的预定集合，所述优先级次序从最高优先级到最低优先级排序圆形网格图案、矩形网格图案、圆形图案，以及然后线性图案。

此外提出一种包括用于执行上述方法的指令的计算机程序。该计算机程序适合于被记录在计算机可读存储介质上。

此外提出一种其上记录有上述计算机程序的计算机可读存储介质。

此外提出一种包括耦合到存储器和图形用户界面的处理器的CAD系统，所述存储器其上记录有上述计算机程序。

附图说明

现在将通过非限制性示例的方式并参照附图描述本发明的实施例，其中：

图1示出该方法的示例的流程图；

图2示出图形用户界面的示例；

图3示出客户端计算机系统的示例；以及

图4-61示出该方法的示例。

具体实施方式

图1显示了用于设计3D建模对象的计算机实现方法的流程图。该方法包括提供S10建模对象的边界表示。该边界表示包括面的集合。每个面被定义为各自支持表面的边界部分。该方法还包括：确定S20边界表示的面的集合的子集，对于该子集，面是另一个的副本。该方法还包括形成S30子集中的第一组面，所述第一组面形成几何图案。以及该方法包括关联S40至少一个第二组面到第一组面。对于第二组面的每一个，第二组的面邻近所述第一组中的各自面。以及对于第二组的每一对面，第二组的面符合刚性运动，所述刚性运动将成对面所邻近的第一组的各自面转换成另一个。

这样的方法构成用于设计3D建模对象的改进解决方案。通过形成S30构成几何图案的第一组面，该方法识别几何图案，从而向用户开放基于图案的设计功能。通过以该方法的具体方式关联S40至少一个第二组面到第一组面，该方法允许识别图案的适当扩展，以更好地把握所需图案并更佳地利于设计。因为该方法工作于面的级别，并包括涉及面的特征识别，所述面例如是彼此的副本并符合具有给定刚性运动的成对的面，该方法可以被容易地实现并因此自动化，从而以详尽和快速的方式识别有意义的图案。这在下面的讨论中全被详细描述。

建模对象是由存储在计算机系统的存储器中的数据所定义的任何对象。推而广之，表述“建模对象”指定数据本身。“设计3D建模对象”指定作为精细制作3D建模对象的至少部分过程的任何动作或动作序列。因此，该方法可以包括：从头开始创建3D建模对象。可替换地，所述方法可包括提供先前创建的3D建模对象，然后修改该3D建模对象。

3D建模对象可以是CAD建模对象或CAD建模对象的一部分。在任何情况下，由该方法设计的3D建模对象可以表示CAD建模对象或它的至少一部分，例如由CAD建模对象占用的3D空间。CAD建模对象是由存储在CAD系统的存储器中的数据所定义的任何对象。根据系统的类型，该建模对象可由不同类型的数据来定义。CAD系统是至少适用于基于建模对象的图形表示设计建模对象的任何系统，诸如CATIA。因此，定义CAD建模对象的数据包括：允许表示建模对象的数据(例如，几何数据，例如包括空间中的相对位置)。

该方法可以包括在制造过程中，其可包括：在执行该方法之后，例如根据通过该方法识别出的几何图案(在这种情况下，向制造过程馈送关于所述几何图案的信息)，而产生对应于所述建模对象的物理产品。在任何情况下，由该方法设计的建模对象可以表示制造对象。因此，建模对象可以是建模立体(即表示立体的建模对象)。制造对象可以是产品，诸如部件或部件的组件。因为该方法改进了建模对象的设计，该方法还改进了产品的制造，从而提高了制造过程的生产率。该方法可以使用CAM系统(诸如DELMIA)来实现。CAM系统是至少适用于定义、模拟和控制制造过程和操作的任何系统。

该方法是计算机实现的。这意味着：该方法可以在至少一台计算机或者任何类似系统上执行。例如，该方法可以在CAD系统上实现。因此，该方法的步骤由计算机执行，可能全自动地或半自动地执行(例如由用户触发的步骤和/或涉及用户交互的步骤)。值得注意的是：提供S10和/或确定S20可以由用户来触发。形成S30和/或关联S40可自动(即无需任何用户干预)或半自动(即涉及例如轻微的用户干预，例如用于验证结果或向/从组添加/删除用户确定的元素)执行。

该方法的计算机实现的典型示例是使用适用于该目的的系统来执行所述方法。该系统可以包括存储器，其上记录有用于执行该方法的指令。换句话说，软件已经准备在存储器上，用于立即使用。该系统因而适于无需安装任何其他软件而执行该方法。这样的系统还可以包括和存储器耦合的用于执行指令的至少一个处理器。换句话说，该系统包括在耦合到处理器的存储器上编码的指令，所述指令提供用于执行该方法的手段。这样的系统是用于设计3D建模对象的有效工具。

这样的系统可以是CAD系统。该系统还可以是CAE和/或CAM系统，并且CAD建模对象也可以是CAE建模对象和/或CAM建模对象。当然，CAD、CAE和CAM系统不是彼此排斥的，因为建模对象可以由对应于这些系统中的任何组合的数据来定义。

该系统可以包括至少一个GUI，用于例如由用户启动指令的执行。值得注意的是：GUI可以允许用户触发提供S10的步骤，然后，如果用户例如通过启动特定功能(例如，名为“图案识别”)而决定这样做，以触发确定S20。然后，可以自动或半自动地执行形成S30，以及然后执行关联S40。

3D建模对象是3D(即三维)的。这意味着，建模对象是由允许其3D表示的数据来定义的。值得注意的是：B-Rep的面是3D的，以及支持表面是3D表面(即，以3D定义它们，以至于所有支持表面的联合可以是非平面的)。3D表示允许从所有角度观看表示。例如，当3D表示时，建模对象可以被处理并围绕它的任何轴或围绕在其上显示表示的屏幕中的任何轴转动。这尤其不包括2D图标(其不是3D建模)，即使当它们以2D立体图表示某物时。3D表示的显示便于设计(即，增加设计者统计上完成他们的任务的速度)。因为产品设计是制造过程的一部分，这加快了工业中的制造过程。注意的是：即使附图的一些示例以2D表示，但关于该方法的3D特征的论述也适用。必须理解：这些示例仅用于理解本方法的目的。

图2示出典型的CAD系统的GUI的示例。

GUI2100可以是典型的类CAD的界面，其具有标准的菜单栏2110、2120、以及底部和侧面工具栏2140、2150。如本领域已知的，这种菜单和工具栏包含一组用户可选择图标，每个图标与一个或多个操作或功能相关联。这些图标中的一些和软件工具关联，适用于编辑和/或作用于GUI2100中显示的3D建模对象2000。软件工具可以被分组到工作台中。每个工作台包括软件工具的子集。具体而言，工作台中的一个是编辑工作台，适于编辑建模产品2000的几何特性。在操作中，设计者例如可以预先选择对象2000的一部分，然后通过选择适当的图标来启动操作(例如，造型操作，或如改变维度、颜色等的任何其他操作)或编辑几何限制。例如，典型的CAD操作是对屏幕上显示的3D建模对象的冲压或折叠的建模。

GUI例如可以显示涉及所显示的产品2000的数据2500。在图2的示例中，数据2500(显示为“特征树”)以及它们的3D表示2000涉及包括制动钳和盘的制动组件。GUI还可以示出各种类型的图形工具2130、2070、2080，例如用于利于对象的3D定向，用于触发所编辑产品的操作的模拟或呈现所显示产品2000的各种属性。光标2060可以由触觉设备控制，以允许用户与图形工具交互。

图3示出了作为客户端计算机系统(例如，用户工作站)的系统的体系结构的示例。

客户端计算机包括连接到内部通信总线1000的中央处理单元(CPU)1010，也连接到BUS的随机存取存储器(RAM)1070。客户端计算机还配备有图形处理单元(GPU)1110，该图形处理单元1110与连接到总线的视频随机存取存储器1100相关联。在本领域中，视频RAM1100已知为帧缓冲器。大容量存储设备控制器1020管理对于大容量存储设备(诸如硬盘驱动器1030)的访问。适合于有形地体现计算机程序指令和数据的大容量存储设备包括所有形式的非易失性存储器，例如包括半导体存储器设备，如EPROM，EEPROM和闪存设备；磁盘，诸如内部硬盘和可移动磁盘，磁光盘，以及CD-ROM盘1040。任何前述可由专门设计的ASIC(专用集成电路)补充，或者并入专门设计的ASIC中。网络适配器1050管理对于网络1060的访问。客户端计算机还可以包括触觉设备1090，诸如光标控制设备，键盘等。光标控制设备用于客户端计算机中，以允许用户在屏幕1080上的任何期望的位置选择性地定位光标，正如参考图2所提及的。通过屏幕，

它是指在其上执行显示的任何支持件，例如计算机显示器。此外，光标控制设备允许用户选择各种命令，并输入控制信号。光标控制设备包括许多信号生成设备，用于将控制信号输入到系统。典型地，光标控制设备可以是鼠标，鼠标的按钮被用来生成信号。

为了使得该系统执行所述方法，提供了一种包括用于由计算机执行的指令的计算机程序，所述指令包括用于此目的的手段。该程序例如可以在数字电子电路中、或者在计算机硬件、固件、软件或它们的组合中实现。本发明的装置可以实施在有形地体现在机器可读存储设备中的计算机程序产品中，用于由可编程处理器执行；以及本发明的方法步骤可以由执行指令程序的可编程处理器来执行，以通过操作输入数据并生成输出而执行本发明的功能。该指令可以有利地在一个或多个计算机程序中执行，该计算机程序可在可编程系统中执行，该可编程系统包括：至少一个可编程处理器，其被耦合以从数据存储系统接收数据和指令，并且将数据和指令发送到数据存储系统；至少一个输入设备；以及至少一个输出设备。该应用程序可以用高级过程语言或面向对象的编程语言实现，或如果希望的话则用汇编或机器语言来实现；且在任何情况下，该语言可以是编译或解释语言。该程序可以是完整的安装程序或更新程序。在后一种情况下，程序将现有的CAD系统更新到其中所述系统适合于执行该方法的状态。

现在讨论提供S10。

该方法包括提供S10建模对象的B-Rep。所述提供S10可由工作于建模对象上(这种情况下，工作于它的边界表示)的设计者产生，或者可由该方法可应用于已存在的B-Rep(例如在现有库中取回的)这一事实产生。在任何情况下，建模对象在S10处被提供为B-Rep。边界表示是用于根据3D对象的包络(即它的外表面)建模3D对象的众所周知的格式。B-Rep从而指定可以包括几何数据和拓扑数据的特定格式的数据。几何数据是提供几何实体的数据，几何实体是根据3D位置描述的实体。拓扑数据是提供拓扑实体的数据，拓扑实体是根据对几何实体的引用和/或与其他拓扑实体的关系(例如相对定位)描述的实体。典型地，该关系可以包括使拓扑实体与其他拓扑实体相关联的“被划界(is bounded by)”关系，通过该关系，它们被拓扑地划界。

提供S10可以排除任何历史数据。换句话说，在S10处提供的建模对象可以是无历史的。这意味着，所建模的对象与指示其设计历史的任何数据不相关联，而是仅通过包括B-Rep的声明数据。因此，该方法在设计者不占有建模对象的历史的背景下工作，这尤其暗示在建模对象上设计的几何图案不像在S10所提供的建模对象上一样被定义。

在该方法的情况下，(例如，几何的)数据至少包括所谓的“支持表面”，例如参数化表面(即，根据与定义2D域的参数相关联的3D位置建模的3D表面)。支持表面典型地可以是N_urbs表面，而且可以是平面的、规范化的或程序上的曲面。(例如，拓扑的)数据至少包括面的集合，每个面被定义为(以几何数据提供的)各自的支持表面的有界部分。因此，面对应于修整表面。所述支持表面因此是在其上以任何方式、通过修整操作定义面(从而“支持”面)的表面。

尽管众所周知，但现在进一步通过可在S10提供的建模对象的示例讨论B-Rep的概念。然而，对于至少一些拓扑实体，本方法可以设想B-Re_p的其他示例，例如具有不同于“被划界”关系的关系。

正如已经提到的，建模对象的B-Rep可包括拓扑实体和几何实体。几何实体可以包括作为表面(例如平面)、曲线(例如线)和/或点的3D对象。表面可被提供为两个参数的函数。曲线可以简单地被提供为一个参数的函数。点可以被提供为3D位置。该拓扑实体可以包括面、边和/或顶点。通过它的定义，面对应于各个表面的边界部分，命名为“支持表面”。术语“面”可因此中立地指定表面的这种边界部分或2D域的相应边界部分。类似地，边对应于曲线的边界部分，例如命名为“支持曲线”。术语“边”因此可指定曲线或其域的边界部分。顶点可以被定义为到3D空间中的点的链接。这些实体如下地彼此相关。曲线的边界部分由位于曲线上的2个点(顶点)定义。表面的边界部分由它的边界定义，该边界是位于表面上的边的集合。面的边界的边通过共享顶点连接在一起。面通过共享边连接在一起。通过定义，如果两个面共享一条边，则它们是相邻的。类似地，如果两条边共享一个顶点，则它们是相邻的。表面、曲线和点可以通过它们的参数化而链接在一起。例如，定义曲线的参量函数的参数值可以被提供以限定边界顶点。类似地，将曲线参数链接到表面的两个参数的函数可以被提供以限定边界边。然而，B-Rep的这种拓扑数据的非常详细的结构超出本说明的范围。

图4和图5示出可以是在S10提供的建模对象并且在附图中由编号为1、2和3的三个面(顶部平面1和两个侧圆柱面2和3)组成的圆柱槽80的B-Rep模型。图4示出槽80的立体图。图5示出所有面的分解图。重复的数字说明共享的边和顶点。面1是平面的有界部分。面1的边界包括边4和边5，它们中的每个由顶点10和11划界。它们都具有相同的支持圆。面2由全位于无限圆柱表面(即面2的支持表面)上的边6、8、5和13划界。面1和2是相邻的，因为它们共享边5。面2和面3是相邻的，因为它们共享边8和边13。面1和面3是相邻的，因为它们共享边4。

图6示出槽80的B-Rep模型的“被划界”拓扑关系。较高层101的节点是面，中间层103的节点是边，而较低层105的节点是顶点。图7和图8图示了拓扑实体(面、边、顶点)和支持的几何形状(无限圆柱体、无限平面、无限线、点)之间的关系。在CAD系统中，B-Rep模型以合适的数据结构聚集“被划界”关系及拓扑实体和支持几何形状之间的关系，以及支持的几何形状的数学描述。换句话说，显示在图6和7中的数据结构是本示例的部分拓扑数据，其中包括几何数据的几何实体的链接(这是图7)和拓扑实体之间的链接(这是图6)。

现在讨论方法的其他动作(即步骤S20-S40)。

例如当用户触发时，该方法包括确定S20边界表示的面的集合的子集，对于所述子集，面是另一个的副本。面的子集因此是作为彼此的副本的面的集合，或者换句话说，是是彼此在几何上等同的，或者是其他的几何复制。该子集可以在S20根据普通技术人员所希望的任何实现方式来确定。例如，所述方法可以包括执行成对的面之间的比较，该面被按任意次序浏览。这样的比较可以以任意方式来进行。稍后提供示例。此外，如CAD领域已知的，涉及数值计算的任何决定须受到由系统应用的所需数值逼近。在目前的情况下，尽管它们在理论上略有不同，面可以在S20被确定为彼此的副本。因此，该方法实际上可在S20确定实质上是另一个的副本的面的子集。然而，实施逼近的方式不是本讨论的主题，因而“实质上是另一个的副本”和“是另一个的副本”未在以下进行区别。实际上只考虑：该方法遵循用于区分两个面是否是另一个的副本的预定标准。

该方法然后包括在形成几何图案的子集内形成S30第一组面。当在S30形成时，第一组面(为方便起见，被称为“第一”)是子集的面的集合，因而是作为另一个的副本的面的集合。通过“形成”组，意思是：数据被添加到建模对象，以便指示所述组的存在。例如，创建组名，并将所述组的面和组名之间的链接添加到(数据定义的)建模对象。将元素连接在一起的这种方式也可以被实施用于确定S20。虽然在形成S30的情况下，组的形成意味着存储在永久性存储器上的新数据，或对于用户作用于几何图案来说至少足够长，而这不一定是用于指示在确定S20中创建的子集的新数据的情况，该新数据被创建主要是用于执行形成S30的目的。这些只是本领域技术人员已知的实施事项。

此外，该方法选择面以形成第一组，使得它们形成几何图案。表述“几何图案”指的是第一组的面构成以可预测方式(即根据预定的规则)定位其元素(即第一组的面或面的集合)的几何结构，从而排除了完整的随机性。通过形成S30构成几何图案的面的组，该方法开始识别在建模对象内的几何图案。因为几何图案的面被首先选择为另一个的副本，该方法识别具有根据设计意图的意思的几何图案。这允许更容易地设计。首先，这允许稍后向用户展示几何图案。因此，用户可以把握设计者的意图。如前所述，这也允许在几何图案上全局执行的以后设计的动作(即，以自动统一的方式)。例如，用户可用单一的“拖放”动作来平移整个几何图案。或者，用户可通过选择图案并且然后仅为其元素输入一次新的尺寸而增加几何图案的所有元素的尺寸。这些仅仅是示例。该方法可包括任何或一些这样的后来的设计动作。这一般在CAD的领域中是有用的，因为该方法允许用较少的用户动作来实现涉及几何图案的一些特定设计。这在机械设计领域中特别有用，当建模对象表示产品时，在这种情况下，属于全球性的工业过程的方法需要其所有阶段的时间优化。该方法还可以包括向制造过程馈送所识别出的几何图案。

形成S30可以包括测试几何图案的预定集合之一的发生是否存在于子集内。换言之，该方法基于几何图案的类型的预定集合，其可能是预定的或用户定义的，例如存储在永久性存储器上，而对于形成S30，该方法测试在S20处确定的子集是否包括遵守/构成属于预定集合的几何图案的面。根据预期的设计的任何领域，在这种预定集合上工作允许尽可能高效地执行该方法。值得注意的是：预定集合可以是可修改的。预定集合可包括2D图案(即平面布局)和/或3D图案(即非平面分布)。

几何图案的预定集合可包括循环定义图案的集合。这些图案通常用在机械设计领域中，因此它们的识别是特别有用的。循环定义图案是这样定义的图案：通过一个或多个初始几何元素(例如面，例如一个或两个初始面)，并通过用于从初始元素和/或从先前生成的元素中生成其他元素的一个或多个规则。当规则被全局定义并且不附连到循环的特定索引时(该规则被定义用于通用索引，例如：n或2n和2n+1，或3n和3n+1和3n+2，即不是用于特定的值)，任何循环定义图案可以是规则的。因此，为了形成S30第一组，该方法可以包括在S20确定的子集内测试是否存在根据对应于所考虑的几何图案的规则而已生成的面的集合。这可以通过浏览预定图案集合的图案而被重复多次。换句话说，根据测试的几何图案，该方法可以包括定义一个或几个面(取决于图案是否具有一个或几个初始元素)，然后检查根据向定义的初始面应用图案规则而是否出现几何图案的发生。稍后提供循环定义图案和测试其发生的方式的示例。

当在S30形成第一组时，无论几何图案识别出什么以及无论过程为其使用何物，该方法然后包括关联S40面的所谓“第二组”到面的第一组。

换句话说，就像在S30，在S40创建新的数据，该新的数据包括第一组和已不在第一组中的B-Rep的其他面之间链接。因此，关联S40将所识别出的几何图案“扩展”到新的面。因此，表达“几何图案”可以指定以下初始几何图案的该扩展版本。在下文中，由该方法识别的任何几何图案因而至少包括是另一个的副本的“第一组”面，以及遵守如下解释的某些约束的“第二组”面。

第二组面是在S10提供的B-Rep的面的整个集合的子集的面的集合。第二组面具有特异性/约束，对于第二组的每个面，第二组面邻近第一组的各自面。换句话说，第二组的每个面和第一组的面共享一条边。在下文中，该第一组面被设计成“‘各自的’第一组面”，以表明其与相邻的第二组面的关系。第二组面的另一特异性/约束在于：对于第二组的每对面，它们符合特定的刚性运动。面可以被看作是点集(并由此像这样由该方法处理)，即三维空间R³的子集。刚性运动是在两个点集合之间由D(x)＝Rx+T定义的映射D：R³→R³，其中R是旋转向量，而T是平移向量(可能为空)。刚性运动是可逆的，因为y＝D(x)等价于x＝D^-1(y)，其中D^-1(y)＝R^-1y-R^-1T。因为第一组面是另一个的副本，给定第一组的两个面，通过施加刚性运动，一个可能源自另一个。现在，对于将成为在S40关联到第一组的部分面的邻近面，该方法需要它们是两个两个地符合刚性运动，所述刚性运动将它们各自的第一组的邻近面转换为另一个。这可能意味着：这样的刚性运动用于例如由该方法实施的特定测试中，以确定邻近第一组面的面是否可以添加到第二组。

符合的概念意味着：第二组的面经由所述特定的各自的刚性运动而两个两个地几何链接，但是它们不必然使用所述特定的各自的刚性运动从另一个中导出(即，在这种情况下，该标准比“是副本”标准更“松散”)。这可由技术人员可以设想的任何方式来实现。例如，当刚性运动还将相应于成对的面的支持表面转换成另一个时，至少在成对的面与第一组各自的面邻近的区域中，该方法可评估成对的面符合特定的刚性运动(即，将成对的面所邻近的第一组的各自面转换成另一个的刚性运动)。邻接区域实际上可以是第二组的面上邻接边的预定邻域(即由两个相邻的面共享的边)。邻域的尺寸可以以技术人员可设想的任何方式来定义。它可以被限制到各个支持表面的一部分。通过将一个各自的第一组的面转换成另一个的刚性运动，该方法然后可评估：支持表面是否是在邻近区域中另一个的副本。通过将第一组的面转换为另一个的刚性运动，另一个示例是评估：邻接边是否(只是)另一个面的副本(这个不一定，即使第一组的面是另一个的副本，因为表面衍生的一些信息可以被附加到相邻边，例如，如稍后所讨论的，附加到以边为界的潜在第二组面的本地轴系统)。可替换地，如果刚性运动还将整个各自的支持表面转换为另一个，则该方法可以评估成对的面符合特定的刚性运动。在任何情况下，对于关联S40(相比于形成S30)的松散的几何比较标准允许更频繁地扩展几何图案，利用已经存在的信息：基于更严格的标准，在S30已经确定几何图案存在。此外，结果更易于由用户处理(因为用户例如可以删除在S40关联的几何图案的一些元素，如果它们对用户而言不是几何图案的一部分，这与增加对他而言已经忘记的元素更容易)。

因此，通过基于面定义来执行简单的几何计算，并通过识别是另一个的副本并形成几何图案的第一组面，然后通过适当地以相邻面扩展第一组，该方法有效地识别可能是复杂的(比一次只一面的图案更详尽)几何图案，而不需要用户识别(即预先选择)用于帮助识别的建模对象上的任何特定面或位置。该方法实际上可以排除由用户做出的这种识别。因此，该方法允许适于建模对象的边界表示的图案的有效识别。该方法不需要任何用户的几何结构视觉分析。该方法通过系统地分析输入的几何结构而集中对复制几何结构的配置。因为用户不直接参与处理，因此节约时间用于其它任务。此外，如后面所解释，该方法可以用于产生复制的几何结构的所有配置作为最终结果。这是一个一次性过程。因此，本发明缩短了用于图案识别所花费的时间，并提供最佳的可能结果。

现在，注意的是：该方法可以被迭代。执行该迭代，使得迭代中在S30的第一组中包括的面或在S40处关联于第一组的面被丢弃，用于下一个迭代。值得注意的是：该方法可以包括如上所述的一个初始提供S10(B-Re_p实际上最初被提供，但随后存在至少直到方法结束)。然后该方法可包括用户执行触发步骤以启动图案识别。然后，该方法可以例如自动地(即无需任何用户干预)迭代确定S20、形成S30和关联S40，直到识别所有图案(可由本方法识别的所有图案)。在每次迭代中，“已使用”的任何面(包括形成第一组的部分的面以及关联于第二组的面，以及属于后面讨论的所谓的“面的块”的面)可以被搁置(即丢弃)，以便它不会在接下来的迭代中使用。这是为了保持图案识别简单，并且具有最多属于一个几何图案的给定面。

由于这种迭代，该方法可以以具有最少用户干预的穷举方式来识别足够详细/精细的几何图案。在这里注意的是：第一确定S20可以确定是另一个的副本的面的所有子集，然后每个迭代的确定S20包括在这些最初确定的子集之间的选择。可以根据本方法的其他动作的迭代来修改最初子集，如稍后参考本方法的示例讨论的。还应当指出：可以一次又一次迭代地交替该方法的步骤S30和S40，或可替换地执行形成S30的几个迭代以及然后执行关联S40的仅仅几个迭代。其中该方法的步骤被重复的精确次序对于图案识别的详尽性是没有必要的。稍后提供如何在每次迭代执行所述方法的步骤的方式的示例。本领域技术人员可实现的任何变化都在当前讨论的范围内。

因此，该方法允许自动寻找在输入对象内的几何特征的所有副本，以及所有这些副本的各自配置。在输入对象上(典型地，立体的B-Rep)执行该任务，无需任何用户选择。该算法根据需要输出图案以描述所有的复制特征。在示例中，该方法首先考虑输入立体作为独立面的集合。在示例的第一步骤中，以相同的刚性运动为模的面聚集成子集。这使得面的初始集合被分割为不相交的子集。粗略地说，给定同一个子集中的任意两个面a，b，存在刚性运动D，使得b＝D(a)。在示例的第二步骤中，在面的每个子集内，该算法识别所有的特性图案。如在后面提供的示例描述的，一维图案是等距间隔对象的线性或环状序列，二维图案是矩形网格或同心和圆形配置。本示例的第三步骤是扩展图案特征。

在提供一些定义之后，现在讨论方法的示例。

给定点集X，如果存在刚性运动使得Y＝{D(x)，x∈X}(简短表示为Y＝D(X))，则点集Y是X的“复制品”。

“定向点集”是二元组(X，u_x)，其中XR³是点集，而u_x是映射u_x：X→S²，其中S²是R³的单位向量的集合。换言之，在任意点x∈X，定义单位向量u_x(x)。

如果Y是保存定向的X的复制品，则定向点集(Y，u_y)是定向点集(X，u_x)的“副本”。更精确地说，对于所有x∈X，在该复制品上的对应点D(x)的单位向量是在点x处的X的旋转单位向量。正式地说，对于所有x∈X，u_Y(D(x))＝Ru_x(x)，表示如下示图是可交换的。

确定S20所依赖的点集上的“是副本”关系是等价关系。为了证明，检查如下属性就足够了，这并不困难：(1)点集是自己的副本，(2)如果Y是X的副本，则X是Y的副本，以及(3)如果Y是X的副本且Z是Y的副本，则Z是X的副本。

根据基本代数，给定点集的有限集合G(意味着G的元素是点集)，等价关系“是副本”将G划分为副本的不相交且最大的子集G_i。这意味着：如果i≠j，则，G＝U_iG_i，如果X，Y∈G_i，则Y是X的副本，以及如果X∈G_i且，则Y不是X的副本。通过参考等价关系的等价类，子集G_i事实上是点集的“类”。

之前的理论应用于(但不限制于)立体的面(即，建模对象例如是立体)。面起着点集的作用，而立体的B-Rep是集合G。换而言之，为了实施确定S20，技术人员可将面表示为点集并且将在S10提供的B-Rep表示为如上定义的集合G。

现在讨论确定S20的示例。

给定建模对象，例如其表示立体，在S10提供的所述立体的B-Re_p被认为是独立面的集合。意味着G＝{f1，...fn}，其中fi是立体的第i个面。最先步骤是根据“是副本”关系来计算(即，确定S20)G的子集。整体算法如下。

可以看出，使用稍后解释的所确定子集的可能修改，因此在开始时确定副本的所有子集。

现在讨论如何为面实施“是副本”关系的示例。

如之前所解释的，由支持表面(例如，平面)以及由边界边定义立体的面。在示例中，面装备有立体的外部法向量。根据该法向量定向边界边。边界边由共享顶点连接。

为了执行比较并寻找刚性运动，每个面都装备有多个轴系统。在面的每个顶点v，如下创建轴系统。原点P的坐标是顶点v的坐标。第一向量(标为U)与v的输入边界边相切，使得如边界边一样定位-U。第二向量(标为V)与v的输出边界边相切，并在边界边方向中定向。根据该面的法向量，词语“输入”和“输出”和边界边的拓扑定向相关。第三向量是在顶点v处计算出的面的外部法向量N。尽管N总是垂直于U和V，但应该注意到轴系统(P，U，V，N)一般不是直接的且正交的。

图9-11示出了半圆柱面90的轴系统。图9显示面90和其法向量92。图10显示由法向量92推导的边界边94的拓扑定向。边界边a是顶点v的输入边。边界边b是顶点v的输出边。图11显示在每个边界顶点处的轴系统的向量U、V和N。

现在，在示例中，该方法可在确定S20内通过搜索两个面之间的刚性运动确定两个面是否是另一个的副本，如果有的话。设f，g为各自装备有(相同数量的)本地轴系统的两个面。如果面f，g没有数量相同的本地轴系统，则意味着它们不具有相同数量的边界顶点，因此确定它们不是彼此的副本，并且不启动刚性运动搜索。

第一步是计算分别将面f的第i个轴系统改变成面g的第j个轴系统的刚性运动D_i，J。因为i，j＝1，...，m，所以存在至多m²个这样的刚性运动。正式而言，刚性运动是这样的：注意，并且D_i，j(x)＝R_i，jx+T_i，j。这通过首先解决以下线性系统而实现，记住，未知数是矩阵R_i，j的系数和向量T_i，j的坐标。

其次，为了确保矩阵R_i，j是旋转，必须检查两个下列的条件。

det(R_i，j)＝1

否则，因为R_i,j不是旋转，因此D_i，j不是刚性运动。

然后，如果有的话，从预先计算出的D_i，j中寻找将f改变为g的刚性运动D*。现在的问题是要回答问题：给定f，g和刚性运动D，D(f)＝g为真？这可以通过以下来完成：用3D点x_k(K＝1，...，q)的收集来采样面f，以及通过检查点D(x_k)面g之间的距离比起用于等同对象的预定数值阈值而言是足够小。如果在D_i，j中几个刚性运动可将f变为g，则在可能时选择纯平移。这是执行确定S20的有效途径，导致结果符合用户意图。

现在讨论用于在S20的迭代处确定的子集的数据结构的示例。

现在讨论：刚性运动和相关点集可以被存储在合适的数据结构中，以便取回给定点集的副本(对应于给定面)和相关联的刚性运动。从概念上讲，该数据结构包含定向图W＝(P，A，α，ω)，其中节点P是点集，以及弧A用刚性运动标记。标记是映射m：A→SE(3)，其中SE(3)是三维刚性运动的组。更确切地说，弧u∈A开始于节点α(u)＝x∈P并结束于节点ω(u)＝y∈P的写入意味着点集x和y是彼此的副本，刚性运动m(u)将x变为y，并指出：y＝m(u)x。现在，假设弧v∈A连接x和z∈P，其被写为α(v)＝x和ω(v)＝z。将x变为z的刚性运动是z＝m(v)x。然后，z也是y的副本，且将y变为z的刚性运动是z＝m(v)m(u)^-1y。相反，将z变为y的刚性运动是y＝m(u)m(v)^-1z。这些信息可以通过数据结构获取。

本质上，计算初始子集的算法创建了由深度-1树图表组成的图表，其中每个都是子集。根据定义，深度-1树是以没有输入弧(根节点)的一个节点以及没有输出弧节点(叶节点)的所有其他节点为特征的树图表。换句话说，所有的非根节点都连接到根节点。因此，假定深度-1树图表内的任何两个节点，仅存在一条连接它们的弧的路径，以及该唯一路径仅包括两个弧。

图12-13示出由计算初始子集的算法产生的图表数据结构(确定S20)。图12示出由四个对齐的圆柱形槽组成的建模对象的B-Rep120，其具有编号从1到12的面。根据拓扑数据结构中的一些任意存储对它们编号。图13示出图表130，包括两个深度-1树132。

因此，通过组合沿着连接两个所述点集的弧的路径的刚性运动，计算将一个点集变为任意另一点集的刚性运动。因为该路径包括两个弧，因此仅组合两个刚性运动。计算子集内任何两个点集相关的刚性运动的这种设施被广泛地用于方法的这个示例中。

现在讨论形成S30的示例。在这些示例中，在子集内形成S30第一组面包括：测试预定一组几何图案之一的发生是否存在于子集中。提供测试和后续动作的示例，用于包括一组循环定义图案的预定组的几何图案。更具体地说，示例的该组循环定义的图案包括一维图案(包括线性图案和/或圆形图案)和网格图案(包括矩形网格图案和/或圆形网格图案)。这种结构特别适合于机械设计，在机械设计中，这些图案经常发生。基于包含所有这四种图案(即，预定的几何图形集合包括：圆形网格图案、矩形网格图案、圆形图案和线性图案)的集合执行形成S30，因此允许掌握机械设计人最想要的图案。如果该集合包括这四种图案，也能确保很好地权衡该方法的执行速度。

现在为这些图案的每一种提供测试和随后动作的定义和示例。

给定点集的集合G，使得是在S20确定的G的子集。这意味着H的所有元素都是彼此的副本。

H的一维图案是二元组(H’，D)，其中H’＝{h₁，...，h_p}是H中包括的集合，其中D是刚性运动，使得h_i+1＝D(h_i)，i＝1，...，p-1。

线性图案是一维图案，其中刚性运动D是平移，如图14所示，其显示了由半圆柱面140形成的线性图案，该半圆柱面140是另一个的副本并经过平移。

圆形图案是一维图案，其中刚性运动D是旋转，如图15所示，其示出了盘面150的圆形图案。

网格图案是具有非平行的两个刚性运动的2D布局图案。

H的矩形网格图案是三元组(H’，D，B)，其中H’＝(h_i，j；i＝1，...，p；j＝1，...，q)是H的子集，以至于：

●刚性运动B和D是非共线的平移；

●h_i，j+1＝B(h_1，j)，j＝1，...，q-1；以及

●h_i+1，j＝D(h_i，J)，i＝1，...，p-1；以及j＝1，...，q。

图16说明了盘面160的矩形网格图案。

H的圆形网格图案是三元组(H’，R，T)，其中H’＝{h_i，j；i＝1，...，p；j＝1，...，q)是H的子集，其中T是平移以及R是旋转，以至于：

●平移T正交于R的旋转轴；

●h_1，j+1＝T(h_1，j)，j＝1，...，q-1；以及

●h_i+1，j＝R(h_i，j)，i＝1，...，p-1；以及j＝1，...，q。

图17说明了三角面170的圆形网格图案。

在该示例中，形成S30包括：通过试图形成图案(如果可能的话)(称为“初始化”图案)，并且然后在子集内扩展图案，而测试上文讨论的几何图案之一的出现是否存在子集内。

现在讨论初始化一维图案的方式的示例。

在这个示例中，测试包括试图找到形成一维图案的三个要素。寻找一维图案的前三个元素的算法如下。设H是点集的子集(意味着H的元素h是彼此的副本)。在算法开始时，所有的元素都是未使用的，这意味着它们还没有参与任何图案。可以以任何方式选择第一个给定的未使用的元素(标为h₁)。

步骤(1)：通过增加距离h₁的距离，在列表L(i)(i＝1，...，n)中排序所有其他未使用的元素，意思是：对于i＝1，...，n，Dist(L(i+1)，h₁)≥Dist(L(i)，h₁)。

步骤(2)：设h₂是列表L中第一个元素。设D是刚性运动，使得h₂＝D(h₁)。搜索另一个未使用的元素h₃，使得h₃＝D(h₂)。如果该h3存在，则图案({h₁，h₂，h₃}，D)被初始化，元素h₁，h₂，h₃被使用，并且算法停止。

步骤(3)：否则，搜索另一个未使用的元素h₀，使得h₁＝D(h₀)。如果该h₀存在，则图案({h₀，h₁，h₂}，D)被初始化，h₀，h₁，h2被使用，并且算法停止。

步骤(4)：如果没有这样的h₃和h₀元素存在，则通过以h₂为列表L中的下一个元素，进入步骤(2)。如果列表L中的所有元素都被访问，则没有任何图案从h₁初始化。

在步骤(2)和(3)，平移D初始化线性图案；旋转D初始化圆形图案。

图18-19说明线性图案初始化。

图20说明了为什么列表L是有用的。当用元素h₁＝a开始图案初始化时，列表L是L＝(g，b，c，d，e，f)。与a最近的元素是h₂＝L(1)＝g，以及使得g＝T₁ ^-1(a)。但是，没有元素h₃或h₀，使得h₃＝T₁ ^-1(g)或者a＝T₁ ^-1(h0)。然后，通过考虑列表L中的下一个元素，L(2)＝b，存在h₃＝c，使得h₃＝T2(b)以及初始化图案({a，b，c}，T₂)。

现在讨论初始化圆形网格图案的方式的示例。

在这个示例中，测试包括试图找到形成圆形网格图案的四个元素。寻找圆形网格图案的前四个元素的算法如下。设H是点集的子集(意味着H的元素h是彼此的副本)。在初始状态，所有的元素都是未使用的，这意味着他们还没有参与任何图案。第一个给定的未使用元素标为h_1，1。

步骤(1)：通过增加距h1，1的距离，在列表L(i)(i＝1，...，n)中排序所有其他的未使用元素，意味着：对于i＝0，...，n-1，Dist(L(i+1)，h_1，1)≥Dist(L(i)，h_1，1)。

步骤(2)：在列表L中，搜索第一元素，标为h_2，1，使得将h_1，1变为h_2，1的刚性运动R(即，h_2，1＝R(h_1，1))是旋转。如果没有这样的h_2，1元素存在，则没有任何圆形图案从h_1，初始化。

步骤(3)：在列表L中搜索第一元素，标为h_1，2，使得将h_1，1变为h_1，2的刚性运动T(即，h_1，2＝T(h_1，1))是正交于旋转R的轴的平移。如果没有这样的h_1，2元素存在，用列表L的下一个元素h_2，1进行到步骤(2)。

步骤(4)：最后，搜索另一个未使用的元素h_2，2，使得h_2，2＝R(h_1，2)。如果这样的h_2，2元素存在，则图案({h_i，j；i＝1，2；j＝1，2}，R，T)被初始化，以及使用h_i，i；i＝1，2。如果没有这样的元素h_2，2存在，则用列表L的下一个元素h_1，2进行到步骤(3)。

图21说明圆形网格图案初始化。

现在讨论初始化矩形网格图案的方式的示例。

在该示例中，测试包括试图寻找形成矩形网格图案的四个元素。寻找矩形网格图案的前四个元素的算法如下。设H是点集的子集(意味着H的元素h是彼此的副本)。在最初状态，所有元素h都是未使用的，这意味着他们还没有参与任何图案。第一给定的未使用元素被标为h_1，1。

步骤(1)：通过增加距h_1，1的距离，在列表L(i)(i＝1，...，n)中排序所有其他的未使用元素，意味着：对于i＝0_，...，n-1，Dist(L(i+1)，h_1，1)≥Dist(L(i)，h_1，1)。

步骤(2)：在列表L中，搜索第一元素，标为h_2，1，使得将h_1，1变为h_2，1的刚性运动D(即，h_2，j＝D(h_1，1))是旋转。如果没有这样的h_2，1元素存在，则没有任何矩形图案从h_1，1初始化。

步骤(3)：在列表L中搜索第一元素，标为h_1，2，使得将h_1，1变为h_1，2的刚性运动B(即，h_1，2＝B(h_1，1))是不与平移D共线的平移。如果没有这样的h_1，2元素存在，则用列表L的下一个元素h_2，1进行到步骤(2)。

步骤(4)：最后，搜索另一未使用元素h_2，2，使得h_2，2＝D(h_1，2)。如果这样的h_2，2元素存在，则图案({h_i，j；i＝1，2；j＝1，2}，D，B)被初始化，以及使用h_i，j；i，j＝1，2。如果没有这样的元素h_2，2存在，则用列表L的下一个元素h_1，2进行到步骤(3)。

图22示出矩形网格图案初始化。

现在讨论在形成S30期间在S20处确定出的子集内扩展一维图案的方式的示例。

假定点集的子集H以及在该子集内初始化的图案P，目的在于计算包括最初图案P的最大图案。假定一维图案P＝({h₁，...，h_n}，D)，h₁被命名为P的第一元素，并被标为f(P)；h_n被命名为P的最后元素，并被标为1(P)。

扩展算法包括向前扩展步骤：

以及向后扩展步骤：

在“while”循环结束时，完成子集H内的最大的一维图案P。

现在讨论在形成S30期间在S20处确定出的子集内扩展二维图案(例如，网格图案)的方式的示例。

假定点集的子集H以及在该子集内初始化的图案P，目标是计算包括初始图案P的最大图案。扩展处理包括：前向行扩展算法、后向行扩展算法、前向列扩展算法以及后向列扩展算法。假定二维图案P＝({h_i，d；i＝1，...，p；j＝1，...，q}，D，B)，前向行扩展算法如图23的流程图所示。

图24-27按时间次序示出了圆形网格图案的前向行扩展算法。虚线是不包含在被扩展的圆形图案内的点集。在此示例中，q＝2而p＝4。

前向列扩展算法如图28的流程图所示。图29-31按时间次序说明圆形网格图案上的前向列算法。虚线是不包含在被扩展的圆形图案中的点集。在此示例中，q＝3而p＝3。

前向行和前向列扩展算法被设计用于矩形和圆形网格图案。未详述后向行和列的扩展算法，因为它们能容易地从前向扩展版本推导出。例如，一种方式是反向行编号并反向列编号。

在所有情况下，测试可以包括根据优先级次序浏览几何图案的预定集合。换句话说，预定的(可能是用户定义的)优先级次序被关联到图案的预定集合，并且形成S30可试图通过根据该次序执行测试而寻找这些图案的出现。的确，在确定S20之后，该方法查找在S20确定出的副本的子集内的图案。为了使得本方法更适应于预期应用，这可以根据不同图案之间的一些优先级次序进行重复。例如，在S30形成最高优先级图案的所有出现(如果有的话)，然后是下一优先级的所有出现(如果有的话)，等等，直至最低优先级。

参照上面所讨论的图案的具体示例，所述优先次序可从最高优先级到最低优先级排序圆形网格图案、矩形网格图案、圆形图案，以及然后线性图案。这种结构特别适合(根据为一组不同用户观察到的统计计算时间)于机械设计领域。

该方法的示例重要的是处理如下图案类型：1D线性、2D线性、1D圆形及2D圆形。由该算法根据下列递减的优先级列表搜索图案：

1.2D圆形(即圆形网格)

2.2D线性(即矩形网格)

3.1D圆形

4.1D线性。

这个优先级列表是基于以下启发式考虑，该考虑在实践中给出了很好的效果。

一种启发在于：2D圆形比2D线性更好。给定图32示出的输入几何结构，理论上可以识别2D线性(图33)和2D圆形(图34)图案。然而，2D圆形图案被选为最合理的设计意图。

另一种启发在于：2D线性比1D圆形更好。给定图35示出的输入几何结构，在理论上可以识别1D圆形(图36)和2D线性(图37)图案。然而，2D线性图案被选作最合理的设计意图。

另一种启发在于：1D圆形比1D线性更好。给定图38示出的输入几何结构，在理论上可以识别局部1D线性(图39)和局部1D圆形(图40)图案。1D圆形图案被选作最合理的设计意图。

现在讨论关联S40的示例。

可通过前面示例的算法在每个子集内计算最大图案。关联S40的一个目标是尽可能多地扩展图案化的点集(即，面的几何图案)。原理是为了执行到相邻面的拓扑扩展。换句话说，对于每个图案P和该图案中的每一元素，目的在于：当所述面保存图案P的结构时从其它图案或子集抓取邻近于所述元素的面。从数据结构的角度看，这样的面可以被移出其自身的图案或子集进入图案P(换句话说，该方法可修改在先前迭代中确定出的子集以及几何图案)。

此拓扑扩展被如下增强。再次，通过访问相邻面来扩展元素，但示例的目的是：识别在立体上复制时没以同样方式修剪的副本。示例中的原则是：在图案化元素中包括适合以下标准的面。(1)候选面邻接图案化元素。注意，e_i，i＝1，…，n，候选面和图案化元素共用的边。(2)候选面的支持表面适合图案结构。(3)边e_i的顶点的本地轴系统(如以上定义)适应图案结构。

例如，应用于图41的立体410的图案识别算法在S30的迭代中识别和形成图42所示并包括正方形焊盘414的四个顶面412的线性图案420。

在图41-42的示例中，图案化的面的相邻面不是彼此的副本，这就是为什么它们不属于任何图案。如图43所示，面432、433和434不是面431的副本。然而，因为它们适合拓扑扩展标准，所以它们包括在该图案中。在包括了所有侧面之后，最初图案420成为图44所示的图案440。

第二组面的数量可以高于第一组面的数量减去预定的阈值，例如1。换句话说，在执行关联S40时，该方法在创建第二组之前强加另一约束：它必须具有一定数量的面，该数量可低于第一组面的数量，但高于减去预定阈值的这个数量(因此它必须大于最小值)。该想法不是用比第一组小得多的第二组(在元素数量方面而言)扩展图案，因为这将意味着，所考虑的相邻面可能不是为了遵循图案。然而，让第二组大于第一组是没有必要的，因为这可能过于严格和不充分地丢弃情况，在该情况中，在设计期间该图案建立后发生局部变化。因此，该方法可为这种局部变化留下一定余量。用于预定阈值的数量1是假阳性和假阴性之间的良好折衷。

因此，拓扑扩展到相邻面可以考虑没有出现在所有副本上的面。例如，考虑图45-47上显示的立体450(为清楚起见，使用三种不同视图)。

该图案算法在形成S30识别正方形垫的顶面452的线性序列，如图48上所示。在S30，没有其他面可以包括在图49所示的图案490中。

本示例的方法然后在S40包括：相邻初始图案的面的面，以及使得所述支持表面适合图案规格(即，用相邻于第一组面的几个第二组面几次迭代S40)。如图50-52按时间次序显示：这逐渐产生图案490的修改。

现在，本方法还可以包括将至少一组面的所谓“块”关联到第一组面。每个块是邻接第二组的各自面的连接面的集合(即，块是一个或多个面的集合，其例如经由可转变的共用边连接在一起)，对于每对块，其符合刚性运动。换句话说，在使在S30形成的几何图案在S40扩展之后，该方法进一步该几何图案扩展到不相邻于第一组面但连接到第二组面的新面。

为符合性保持的标准可以和为关联保持的标准完全相同。换句话说，成对块的相应面必须具有支持表面，所述支持表面是可以经由刚性运动从另一个推导出的，至少在所考虑的面邻近图案的各自面的区域中(如当前扩展地)，所述刚性运动将各自的第一组面转换成另一个。在当前示例的情况下，关于关联S40，支持表面实际上正是(即完全)是可从另一个推导出的。

此外，尽管相应的第二组面的数量可低于第一组面的数量(以预定阈值为模)，块的数量可以被限制为等于第二组面的数量。这是因为块已经“远离”第一组面。

通过允许邻近某些副本并在其他副本中丢失的面，并通过扩展图案到块；计算图53的图案530。如示例的方法所确定的，这个得到的图案530对应于以下设计意图：在图55所示的立体550上复制图54上所示的特征540。

现在通过示例讨论涉及方法的步骤的上述示例的迭代的问题。因为通过将面从一个移动到另一个，图案扩展修正图案和子集，所以迭代对于调查修改的图案和子集是必要的。

例如，在S10提供的初始模型可以是图56所示的11个小正方形和4个大正方形的排列560。小正方形8、9、10和11分别邻近大正方形12、13、14和15。初始子集计算算法可直接产生小正方形的子集C＝{1，...11}以及大正方形的子集C′＝{12，...，15}。子集内的图案识别可产生大正方形的线性图案P′＝({12，...，15}，D)以及小正方形的线性网格图案P＝({1，2，3，4，5，7，8，9，10，11}，D，B)。图57说明了子集和图案状态。

因为小和大正方形邻近以及因为T＝D，所以图案扩展算法发现图案P′可以抓取小正方形8、9、10、11的面。该操作将面从图案P移动到图案P′并删除图案P。更新图案P′是P′＝({{8，12}，{19，13}，{10，14}，{11，15}}，T)。此外，因为元素8至11有助于图案P′，以及因为子集C′的所有元素都参与了图案P′而被删除，所以子集C现在是C＝{1，...，7}，如图58所示。

由于修改了子集C，所以迭代启动。如图59所示，发现了线性图案P″＝({1，...，6}，T)。子集C被减少为单个元素以及迭代停止。

现在讨论具体细节。

本发明中所述的图案识别算法提供单个结果，不管可能存在几种解决方案。例如，图60-61说明了对于盘的相同初始输入的矩形图案的两个可能解决方案(以虚线圆圈)，以及存在先验，没有理由相对于一个而优选另一个。该方法可以随机地在这两个之间计算一个。

另外，在识别图案之后，可能需要被复制特征的参考版本。由于参考特征的所有副本可通过修整操作来改变，所以计算“未开发”的参考功能可能是有用的，例如用于编辑目的。根据任意实施方式，该方法可以包括参考版本的这种确定。

Claims (24)

1.一种用于设计三维建模对象的计算机实现方法，包括：

提供(S10)建模对象的边界表示，所述边界表示包括面的集合，每个被定义为各自支持表面的边界部分；

确定(S20)所述边界表示的所述面的集合的子集，对于该子集，所述面中的任何一个面是所述面中的任何另一个面的副本；

形成(S30)所述子集中的第一组面，所述第一组面形成几何图案；以及

关联(S40)至少一个第二组面到所述第一组面，对于所述第二组的每个面，其邻近所述第一组的各自面，对于所述第二组的每一成对的面，其符合将所述成对的面中的一个面所邻近的第一组的各自面转换成所述成对的面中的另一个面所邻近的第一组的各自面的刚性运动。

2.如权利要求1所述的方法，其中，对于所述关联(S40)，当所述刚性运动还将对应于一对面的支持表面转换成另一个时，至少在该对面邻近第一组的各自面的区域中，该对面被评估为符合将该对面所邻近的第一组的各自面转换为另一个的刚性运动。

3.如权利要求1或2所述的方法，其中所述第二组面的数量大于所述第一组面的数量减去预定阈值。

4.如权利要求1或2所述的方法，其中所述方法还包括：关联至少一组由面形成的块到所述第一组面，对于每个块，所述至少一组由面形成的块是邻近所述第二组的各自的面的连接面的集合，以及对于每对块，所述至少一组由面形成的块符合所述刚性运动。

5.如权利要求1或2所述的方法，其中所述方法被迭代，在迭代中包含于所述第一组且关联到所述第一组的面针对下一迭代而被丢弃。

6.如权利要求1或2所述的方法，其中在子集内形成(S30)第一组面包括：测试几何图案的预定集合中的一个的发生是否存在于所述子集内。

7.如权利要求6所述的方法，其中所述几何图案的预定集合包括循环定义的图案的集合。

8.如权利要求7所述的方法，其中所述循环定义的图案的集合包括一维图案和/或网格图案，所述一维图案包括线性图案和/或圆形图案，所述网格图案包括矩形网格图案和/或圆形网格图案。

9.如权利要求8所述的方法，其中所述测试包括：根据优先级次序浏览所述几何图案的预定集合。

10.如权利要求6所述的方法，其中所述几何图案的预定集合包括：圆形网格图案、矩形网格图案、圆形图案以及线性图案。

11.如权利要求10所述的方法，其中所述测试包括：根据优先级次序浏览几何图案的预定集合，所述优先级次序从最高优先级到最低优先级排序所述圆形网格图案、所述矩形网格图案、所述圆形图案以及所述线性图案。

12.一种用于设计三维建模对象的装置，包括：

提供模块，用于提供(S10)建模对象的边界表示，所述边界表示包括面的集合，每个被定义为各自支持表面的边界部分；

确定模块，用于确定(S20)所述边界表示的所述面的集合的子集，对于该子集，所述面中的任何一个面是所述面中的任何另一个面的副本；

形成模块，用于形成(S30)所述子集中的第一组面，所述第一组面形成几何图案；以及

关联模块，用于关联(S40)至少一个第二组面到所述第一组面，对于所述第二组的每个面，其邻近所述第一组的各自面，对于所述第二组的每一成对的面，其符合将所述成对的面中的一个面所邻近的第一组的各自面转换成所述成对的面中的另一个面所邻近的第一组的各自面的刚性运动。

13.如权利要求12所述的装置，其中，对于所述关联(S40)，当所述刚性运动还将对应于一对面的支持表面转换成另一个时，至少在该对面邻近第一组的各自面的区域中，该对面被评估为符合将该对面所邻近的第一组的各自面转换为另一个的刚性运动。

14.如权利要求12或13所述的装置，其中所述第二组面的数量大于所述第一组面的数量减去预定阈值。

15.如权利要求12或13所述的装置，其中所述装置还包括：用于关联至少一组由面形成的块到所述第一组面的模块，对于每个块，所述至少一组由面形成的块是邻近所述第二组的各自的面的连接面的集合，以及对于每对块，所述至少一组由面形成的块符合所述刚性运动。

16.如权利要求12或13所述的装置，其中所述提供模块、所述确定模块、所述形成模块以及所述关联模块的操作被迭代，在迭代中包含于所述第一组且关联到所述第一组的面针对下一迭代而被丢弃。

17.如权利要求12或13所述的装置，其中在子集内形成(S30)第一组面包括：测试几何图案的预定集合中的一个的发生是否存在于所述子集内。

18.如权利要求17所述的装置，其中所述几何图案的预定集合包括循环定义的图案的集合。

19.如权利要求18所述的装置，其中所述循环定义的图案的集合包括一维图案和/或网格图案，所述一维图案包括线性图案和/或圆形图案，所述网格图案包括矩形网格图案和/或圆形网格图案。

20.如权利要求19所述的装置，其中所述测试包括：根据优先级次序浏览所述几何图案的预定集合。

21.如权利要求17所述的装置，其中所述几何图案的预定集合包括：圆形网格图案、矩形网格图案、圆形图案以及线性图案。

22.如权利要求21所述的装置，其中所述测试包括：根据优先级次序浏览几何图案的预定集合，所述优先级次序从最高优先级到最低优先级排序所述圆形网格图案、所述矩形网格图案、所述圆形图案以及所述线性图案。

23.一种其上记录有用于执行如权利要求1-11所述的方法的指令的数据存储介质。

24.一种包括耦合到存储器和图形用户界面的处理器的CAD系统，所述存储器其上记录有用于执行如权利要求1-11所述的方法的指令。