用于边界表示的面和边连通性的压缩的方法和系统

摘要

公开了一种用于重构图模型的边界表示数据的系统、方法及计算机程序产品。该方法包括接收图模型的边界表示数据，其中边界表示数据包括边和有向边。该方法包括根据边界表示数据来构建顶点表和边表，其中顶点表具有图模型的多个顶点的坐标，边表将图模型的每条边与图模型的多个顶点中的至少一个顶点相关联。该方法包括存储所构建的与边界表示数据相关联的边表和顶点表。

说明书

技术领域

本公开内容总体上涉及在计算机辅助设计、制造、工程、建模、可视 化（单独地和共同地，称为“CAD”和“CAD系统”）中使用的系统和方 法以及在产品生命周期管理（“PLM”）系统中使用的系统和方法。

背景技术

很多工业产品首先在计算机辅助设计系统中进行设计和建模，并且制 造商、零售商、消费者及其他用户使用产品生命周期管理系统来管理不同 产品的设计、使用和处理。期望的是改进的系统。

发明内容

各种公开的实施方式包括用于重构图模型的边界表示（B-Rep）数据 的系统、方法及计算机程序产品。该方法包括接收图模型的边界表示数据， 其中边界表示数据包括边和有向边。该方法包括根据边界表示数据来构建 顶点表和边表，其中顶点表具有图模型的多个顶点的坐标，边表将图模型 的每条边与图模型的多个顶点中的至少一个顶点相关联。该方法包括存储 与边界表示数据相关联的边表和顶点表。

上述内容大致概述了本公开内容的特征和技术优点，以使得本领域普 通技术人员能够较好的理解下述具体实施方式。在下文中，将描述本公开 内容的形成权利要求的主题的另外的特点及优点。本领域普通技术人员将 会理解：他们可以很容易地以所公开的构思和具体实施方式为基础来修改 或设计用于实现与本公开内容相同目的其他结构。本领域普通技术人员也 将会认识到：这样的等同结构不脱离本公开内容的最宽泛形式的精神和范 围。

在进行下面的具体实施方式之前，有必要对本专利文献全文中使用的 某些词或短语的定义进行说明：术语“包括”及其派生词表示没有限制的 包括；术语“或”是包括性的，表示“和/或”；短语“与…相关联”及其 派生词可以表示包括、包括在…内、与…互连、包含、包含在范围内、连 接至或与…相连、耦接至或与…耦接、与…可通信、与…配合、交错、并 置、接近、缚接至或与…缚接、具有、具有其属性”等；术语“控制器” 表示控制至少一个操作的任何装置及系统或其部件，而不管这样的装置是 以硬件、固件、软件还是以它们中的至少两个的组合实现的。应当注意的 是，与任何特定的控制器相关联的功能可以是集中式或分布式的，无论本 地的还是远程的。在本专利文献全文中，提供了对某些词或短语的定义， 但本领域普通技术人员将会理解：在许多（即便不是大部分）情况下，这 样的定义应用在这样定义的用词和短语的当前以及将来的使用中。尽管一 些术语可以包括各种各样的实施方式，但是所附权利要求可以针对具体实 施方式特别地限制这些术语。

附图说明

为了更透彻地理解本公开内容及其优点，现在参照结合了附图的以下 描述，其中相同的附图标记表示相同的对象，并且在附图中：

图1示出了实施方式可以在其中实施的数据处理系统的框图；

图2示出了表现不同的边界表示拓扑元素之间的拓扑关系的边界表 示拓扑；

图3A和3B示出了根据所公开的实施方式的面连通性压缩；

图4示出了根据所公开的实施方式的边连通性表示示例模型以及相 应的边表和顶点表；

图5示出了根据所公开的实施方式的边连通性示例；

图6示出了根据所公开的实施方式的边表和顶点表的重构；以及

图7和图8示出了根据所公开的实施方式的过程的流程图。

具体实施方式

在本专利文献中，下述图1至图8和用于描述本公开内容的原理的各 种实施方式仅是为了说明，而不应当被认为以任何方式来限制本公开内容 的范围。本领域普通技术人员将会理解，本公开内容的原理可以以任何合 适设置的设备来实现。将参照示例性的非限制性实施方式来描述本申请的 各种创新性教导。

3D设计信息的协同可视化在延伸性企业的产品生命周期管理（PLM） 环境中起着非常重要的作用，3D产品信息在职能不同且实体上分散的不 同组织机构之间的有效传递是重要的。如果一幅图片相当于一千个字，那 么3D视觉信息的有效性则相当于一千幅图片。尽管3D信息主要用于传 统的工程性目的，如设计和制造，但是3D信息的应用正在迅速扩展至产 品生命周期的许多非工程性活动中，如培训，维护及市场销售。因此，在 产品生命周期管理环境中3D可视化信息的易获得性将会给延伸性企业的 许多部门带来巨大的生产力价值。

在产品生命周期管理环境中，3D视觉数据可以存储在服务器数据处 理系统上，并且可以被客户端使用通过局域网或广域网连接到服务器的客 户端数据处理系统来进行访问。客户端可以位于全球各地，并且对于许多 客户端来说，相应的服务器位于远程的不同的地理区域甚至不同的国家。 降低3D视觉数据的存储量提高了它在客户端-服务器架构中的可访问性， 这是因为将数据从服务器传输到客户端所需的时间减少了，尤其是在具有 有限带宽的网络上传输的情况下。因此，成功的3D视觉格式应当在磁盘 上具有轻量的存储，但仍支持复杂的视觉显示及几何分析任务。

边界表示或B-Rep已成为现代CAD软件包中用于3D几何表示的实 际行业标准。B-Rep允许对自由形式的曲线和表面进行表示，通常以非均 匀有理B样条（NURBS）的形式表示，并且B-Rep可以用于精确地表示 3D几何设计信息。已知的是：传统的边界表示在视觉表示时具有不期望 的大的存储需求。

所公开的实施方式包括超轻量且精确（ULP）的3D视觉格式，该3D 视觉格式基于对边界表示施加高级压缩以获得在磁盘上的轻量存储。由于 ULP共享与基于NURBS的B-Rep相同的数学基础，所以ULP具有如下 优点：支持在单个B-Rep表面内的连续性，并且格式可以很容易被主流 的实体建模内核支持，如西门子产品生命周期管理软件公司的Parasolid 软件。

图1示出了实施方式可以在其中实施的数据处理系统的框图，该数据 处理系统用作在此描述的用于管理3D数据的客户端系统或服务器系统。 所描绘的数据处理系统包括处理器102，该处理器102连接到二级缓存/ 桥104，而二级缓存/桥104又连接到局部系统总线106。举例来说，局部 系统总线106可以是外围部件互连（PCI）架构总线。在所述示例中，连 接到局部系统总线的还有主存储器108和图形适配器110。图形适配器可 以连接到显示设备111。

其他外设，如局域网（LAN）/广域网/无线(如WiFi)适配器112也可 以连接到局部系统总线106。扩展总线接口114将局部系统总线106连接 到输入/输出（I/O）总线116。I/O总线116连接到键盘/鼠标适配器118、 磁盘控制器120以及I/O适配器122。磁盘控制器120可以连接到存储设 备126，该存储设备126可以是任何合适的机器可用或机器可读的存储介 质，其包括但不限于：非易失性硬编码型介质，如只读存储器（ROM） 或电可擦可编程只读存储器（EEPROM）、磁带存储器；用户可记录型介 质，如软盘、硬盘驱动器、只读光盘存储器（CD-ROM）或数字多功能 盘（DVD）；以及其它已知的光、电或磁存储设备。

在所示示例中，连接到I/O总线116上的还有音频适配器124，该音 频适配器可以连接至扬声器（未示出），用于播放声音。键盘/鼠标适配器 118为定点设备（未示出）如鼠标、轨迹球、轨迹指示器等提供连接。

本领域普通技术人员将会理解：图1示出的硬件可以针对特定的实施 而不同。例如，也可以额外使用其他外围设备（如光盘驱动器等），或使 用其他外围设备来取代所述硬件。所述示例仅是出于说明的目的，并非意 在对于本公开内容暗示对架构上的限制。

根据本公开内容的实施方式的数据处理系统包括采用图形用户接口 的操作系统。该操作系统允许在图形用户接口中同时出现多个显示窗口， 其中每个显示窗口向不同的应用或同一应用的不同事例提供接口。用户可 以通过定点设备来操作在图形用户接口中的光标。可以改变光标的位置和 /或产生诸如点击鼠标的事件来启动期望的响应。

各种商业操作系统中的一个系统——如位于华盛顿州雷德蒙市的微 软公司的产品（某一版的Microsoft Windows^TM系统）——在适当的修改 之后可以被采用。可以根据所描述的本公开内容来对操作系统进行修改或 创建。

LAN/WAN/无线适配器112可以连接到网络130（其不是数据处理系 统100的一部分），该网络130可以是本领域普通技术人员公知的任何公 共或专用数据处理系统网络或这些网络的组合，包括因特网。数据处理系 统100可以通过网络130与服务器系统140进行通信，该服务器系统140 也不是数据处理系统100的一部分，但是该服务器系统140也可以被实施 为例如独立的数据处理系统100。

图2示出了根据文中公开的各种实施方式的、表现不同的B-Rep拓 扑元素之间的拓扑关系的B-Rep拓扑，在该情况下，针对区域、壳、面、 环、有向边、边以及顶点拓扑信息示出了模型拓扑205与CAD几何210 之间的关系。如此处所示出的，面拓扑由表面几何（geometry）表示，有 向边拓扑由UV曲线几何（UV曲线网络定义由曲线的排列表示的B样条 表面）表示，边拓扑由XYZ曲线几何表示，而顶点拓扑由点几何表示。

在B-Rep表示中，每条边曲线具有双重表示。该边曲线的模型空间 几何由XYZ曲线表示而它的参数空间几何由用于该边曲线的两个相关联 的表面中的每个表面的UV曲线表示。UV曲线可以看作相关联的有向边 的几何表示，而XYZ曲线可看作相关联的边的几何表示。

与NURBS表面相关联的所有UV曲线的集合在NURBS表面的参数 域内构成一个或更多个闭环。这些闭环一起形成了修整（trim）NURBS 表面几何的一个或更多个区域。在模型空间中，修整的表面几何以XYZ 曲线的集合为界。该修整的表面几何被看作为B-Rep面的几何表示。

一种ULP技术通过适当地对元素进行组织来非常有效地压缩一些拓 扑信息（例如区域-壳，壳-面，面-环以及环-有向边关系），如在下面引用 的“Truform”文章中所述的。

利用这样的方法，所有属于相同区域的壳在壳数组中是连续的，所有 属于相同壳的面在面数组中是连续的，所有属于相同面的环在环数组中是 连续的，所有属于相同环的有向边在有向边数组中是连续的。一般而言， 有向边表现了面或线对于边的使用。若同一个面位于边的两侧，则边被该 面使用了两次，因此该边具有涉及该面的两条有向边。若面仅位于边的一 侧，则该边被该面使用了一次，该边仅有一条涉及该面的有向边。在边位 于多于一个面上的情况下，则该边具有针对每个面的每次使用的有向边。 位于面上的每条有向边属于所述面的环。环中的有向边形成回路，其中每 个有向边的前端附连到下一条有向边的末端。环中的有向边形成双链路的 列表，其中每条有向边指向其在环中的下一条和前一条有向边。

在拓扑表中，每个拓扑实体存储关于它的子实体的信息，但不存储它 的父实体的信息。由于所有子实体在数组中是连续的，以在子数组中的它 的最后一个子实体的索引足以表示子实体信息。这是因为第一元素的起始 子实体索引通常为0，并且任何其他元素的起始索引可以从同一数组中的 前一个元素的最后子实体索引获得。

由于最后的子实体索引对于每种元素类型是单调递增的，更好的方法 是对两个相邻的最后子实体索引之差（即每个元素的子实体的个数）进行 编码。更具体地，

·属于一个区域的壳用该区域中的壳的个数来表示

·属于一个壳的面用该壳中的面的个数来表示

·属于一个面的环用该面中的环的个数来表示

·属于一个环的有向边用该环中的有向边的个数来表示

然而，使用已知的技术不能够有效地压缩其他拓扑信息，如表示面连 通性信息的有向边-边、表示边连通性信息的边-顶点。随着对ULP中的 其他拓扑信息的有效压缩，面和边连通性信息的量成为存储介质上的 ULP拓扑的非常重要的部分。

所公开的系统和方法实现对B-Rep中的面和边连通性信息的更有效 压缩。

图3A和图3B示出了根据所公开的实施方式的面连通性压缩。在这 些图中，实线表示边，虚线表示有向边。

如果边被随意索引，则以每条有向边中的边索引号所表示的面连通性 信息的存储量非常大。这是因为两条有向边可以涉及相同的边，因此存在 与其他拓扑信息相比要少的数值关系。图3A和3B示出了具有三个面的 简单模型305和315，面之间的连通性通过标注来自每条有向边的边来进 行表示。当边被随意索引时，针对模型305使用简单的方法，必须存储 12个数字，如图3A的表310中所示。在该示例中，针对有向边0的第一 表条目标注边7，针对有向边1的第二表条目标注边5。分别针对有向边 2和5的第三和第六条目均标注边6。应指出，只要两个相邻面拥有的有 向边涉及相同的边索引，在该示例中边数组中的边的确切索引是无意义 的。

如图3B所示，当顺序地访问有向边时，基于标注的顺序来从父有向 边中选择边索引。对于标注仍未被标注的边的每条有向边，例如标注边2 的有向边2，存储无效索引（例如-1）就足够了，这是因为可以通过当循 环数组时保持对-1的计数的跟踪来推断出实际的边索引。对于标注已被标 注的边的每条有向边，例如标注公共边2的有向边5，由于用于边2的-1 条目已经用于有向边2，则存储实际的边索引。如图3B的表320中所示， 仍然有12个数字需要存储。不过由于这些数字中的一半或多于一半具有 相同的值，所以数组的熵大大减小。利用熵编码器，如哈夫曼编码器或算 术编码器，磁盘上的面连通性信息可以以特殊的边索引方式减少50%或 更多。

图4示出了边连通性表示示例模型405以及相应的边表410和顶点表 415，其可以用于表示B-Rep模型405。

如图4所示，模型405的每个B-Rep边具有两个边界顶点（bounding  vertex）：一个起始顶点和一个结束顶点。每条边查阅其在边表410中的 起始顶点和结束顶点、通过起始顶点和结束顶点的索引查阅表示顶点几何 的顶点表415。每条边的方向可以任意选择。边连通性信息可隐含地表示 为：若两条边共同享同一顶点，则这两条边彼此连接。例如，边1和边2 是连接的，这是因为这两条边共享顶点3。

顶点表中的顶点的确切排序是无意义的，顶点索引用作避免边表中的 顶点几何出现重复的工具。然而，并没有一种本领域中已知的有效方式来 将顶点排序，使得边表和/或顶点表的熵大幅度减小。因此，边表和顶点 表的大小成为磁盘上的ULP表示的重要部分。

根据所公开的实施方式，系统可以完全省略对边表和顶点表的存储， 而基于其他已存储的B-Rep信息来重构缺失的信息。对于每条边，它的 两个边界顶点的几何可以根据其相关联的XYZ曲线的几何来计算，并且 所述边与其他边的连通性可以根据环-有向边拓扑和有向边-边拓扑信息 来有效地计算。

图5示出了使用模型505的边连通性示例，并且可以用于说明根据所 公开的实施方式的过程。

图6示出了根据所公开的实施方式的边表和顶点表的重构。

使用图5中示出的示例来逐步说明用于复原边连通性和顶点几何形 状的过程。应指出，根据定义，在单个环中的有向边形成首尾连接。

当一条边重复时，如果这个边还没有计算出来，系统将重复所有的边， 并计算每条边的起始顶点和结束顶点的信息。如果顶点信息没有被计算 出，则系统在顶点表中创建顶点、使用面连通性和环-有向边拓扑信息来 重复链合在同一顶点上的所有边、以及将该顶点设置到所有的这些边上。 每条边的XYZ曲线提供用于顶点几何的值，并且将根据所有这些边计算 的顶点几何进行平均，以在顶点表中产生最终顶点几何。如果已经算出顶 点信息，则处理下一条边。

更广泛地讲，在各种的实施方式中，系统接收包括边和有向边的图模 型的B-Rep数据，并且根据该B-Rep数据来构建顶点表和边表，随后将 其存储到系统中，其中所述顶点表具有图模型的多个顶点的坐标，所述边 表将图模型的每条边与图模型的多个顶点中的至少一个顶点相关联。以此 方式，根据B-Rep数据来重构边表和顶点表，但是边表和顶点表没有必 要与模型一起永久地存储或者与其他B-Rep数据一起传送。在一些实施 方式中，B-Rep数据在其原始数据存储装置中不包括边表信息或顶点表信 息或者在从该存储装置传送时不包括边表信息或顶点表信息。系统遍历每 条边，以确定该边的起始顶点和结束顶点。在许多情况下，每条边具有至 少一条相应的有向边，并且每条有向边都包括在有向边环内。在下面的更 为详细地描述的遍历通常包括从每条边到相应的有向边、再从该有向边到 其有向边环中的第二有向边、再从第二有向边到相应的第二边的遍历。系 统可以然后识别在第一边与第二边之间的公共顶点，并使用该公共顶点作 为边表和顶点表中的一个或更多个条目。

图6分步骤地示出了图5所示的每个顶点的计算。在每个步骤中，示 出了对于链合到该顶点的所有边的遍历，结果在每个步骤之后，获得更新 的边表和顶底表。在该图中，黑体箭头表示面连通性，普通箭头表示同一 环中的下一条有向边，而虚线箭头表示同一环中的前一条有向边。以较大 的形式显示的边表示结束顶点正被计算（步骤605中的e1和e8，步骤610 中的e0和e3，步骤615中的e5，步骤620中的e2，步骤625中的e4， 步骤630中的e6和步骤635中的e7）。“e”表示已编号的边，“c”表示已 编号的有向边，“v”表示已编号的顶点。

在步骤605中，计算边e0的起始顶点v5。将边e0的起始顶点v5存 入边表中，将v5的坐标存入顶点表中。系统遍历有向边以确定其他哪些 边连接至v5。边e0与c0具有面连通性，其中c0指向下一条有向边c1。 有向边c1与边e1具有面连通性。系统确定边e1必定也连接至v5，并将 边e1以v5作为结束顶点存入边表中。系统确定边e1还具有有向边c10， 并且c10指向c11，其中c11与边e8具有面连通性。系统确定边e8必定 也连接至v5，并将边e8以v5作为结束顶点存入边表中。

在步骤610中，从e0开始，系统跟随前一条有向边c0找到有向边c3， 其中c3与边e3具有面连通性，因此e3与e0必定共享顶点v6。将边e0 的结束顶点v6存入边表中，并将v6的坐标存入顶点表中。顶点v6作为 边e3的结束顶点也存入边表中。

在步骤615中，系统从边e1移动至有向边c1，并再移动至其下一条 有向边c2，其中c2与边e2具有面连通性，因此边e2与边e1必定共享顶 点v3。将v3作为e2的起始顶点存入边表，并将v3的坐标存入顶点表中。 e2也与有向边c5具有面连通性，系统跟随至下一条有向边c6，并找到与 其具有面连通性的e5。顶点v3因此作为边e5的结束顶点存入边表中。 系统找到e5的另一条有向边c9，并跟随c9至其下一条有向边c10，其中 c10与边e1共享面连通性，而该e1已经存在于边表中。因此获知顶点v3 是边e1的起始顶点，并将此存入边表中。

在步骤620中，系统从边e2移动，对于边e2，仅知道起始顶点v3， 系统跟随有向边c5至其前一条有向边c4，其中c4与边e4共享面连通性。 因此发现顶点v0是边e2的结束顶点以及边e4的起始顶点，并且这些均 被存入边表中，而顶点v0的坐标存入顶点表中。系统跟随边e2的另一条 有向边c2至其下一条有向边c3，以找到边e3，并确定边e3也共享顶点 v0并且顶点v0是它的起始顶点，并将此存入边表中。

在步骤625中，系统跟随边e4的有向边c4至其前一条有向边c7，以 找到边e6，并确定边e6以顶点v1作为其起始顶点，并将这存入边表中 以及将顶点v1的坐标存入顶点表中。

在步骤630中，系统跟随边e5的有向边c6至其下一条有向边c7，以 找到边e6，并确定边e6以顶点v2作为其结束顶点，并将这存入边表中 以及将顶点v2的坐标存入顶点表中。系统跟随边e5的另一条有向边c9 至其前一条有向边c8，以找到边e7，并确定边e7以顶点v2作为起始顶 点，将这存入边表中。此时，只有顶点v4还没有确定。

在步骤635中，系统跟随边e7的有向边c8至其前一条有向边c11， 以找到边e8，其中e8在步骤605中已经找到。系统确定边e7和e8共享 顶点v4，并将v4作为e7的缺失的结束顶点和e8的起始顶点进行存储。 系统将顶点v4的坐标存入顶点表中。

此时，仅使用B-Rep的边和有向边数据就已经完全地重构出边表和 顶点表。

图7和图8示出了根据所公开的实施方式的过程的流程图。图7示出 了边连通性计算过程的流程图，而图8示出了边遍历过程的流程图，该边 遍历过程可以应用于图7的过程中的步骤740和/或步骤765。在图8中， 符号^用于表示异或（XOR）运算，其定义为：1^0=1，0^1=1，0^0=0， 1^1=0。

在图7中，系统开始于接收模型的B-Rep数据（步骤705）。此处使 用的“接收”可以包括：从存储设备加载、从数据处理系统或在数据处理 系统上执行的程序接收、从用户接收、或以本领域普通技术人员已知的其 他方式接收。注意的是，根据各种实施方式，在该步骤中接收到的B-Rep 数据不包括边表数据或顶点表数据。“表”不特定地只指表数据结构，而 是还可以包括本领域普通技术人员所已知的功能等同结构。

系统通过首先确认是否存在剩余的待处理的边（步骤710）来遍历模 型的B-Rep数据的每条边。如果不存在，该过程结束（步骤715）。

如果仍然存在待处理的剩余边，系统处理下一条边（步骤720）。系 统确定边的起始顶点是否已经计算出来（步骤725）。如果没有，则系统 在顶点表中创建新的条目（该条目可能为空或当处理第一边时仍未创建） （步骤730）。系统将边表中的起始顶点字段设置为该边的第一顶点（步 骤735）。

系统然后遍历“链合（hinged）”在第一顶点上的所有相邻边（步骤 740），包括：将第一顶点设置为边表中的每条相邻边的起始顶点或结束顶 点；以及累计顶点几何。图8中的过程可用于该步骤中。

系统然后计算第一顶点的所有顶点几何的平均值，并存储平均值（步 骤745）。每个顶点几何基于不同的XYZ曲线几何被计算多次。以顶点v0 为例，该顶点v0的几何根据与边e2、e3和e4相关联的XYZ曲线来计算。 尽管理论上，该顶点根据不同的XYZ曲线计算的几何应当是相同的，但 实际上它们通常略有差别。因此，获得三个位置v0-e2、v0-e3、v0-e4。在 遍历过程中，每个顶点的这些位置被累计，使得遍历之后顶点v0的累计 几何为v0-e2+v0-e3+v0-e4。步骤“计算几何平均值”指的是公式v0= （v0-e2+v0-e3+v0-e4）/3，其中3是在顶点v0处链合的边的个数，从而 考虑在该顶点处的所有的附接的XYZ曲线来获得最佳顶点几何。

此时，如果边的起始顶点已经计算出来（步骤725），系统确定边的 结束顶点是否计算出来（步骤750）。如果没有计算出来，则系统在顶点 表中创建新的条目（该条目可能为空或当处理第一边时仍未创建）（步骤 755）。系统将边表中的结束顶点字段设置为该边的第二顶点（步骤760）。

系统然后遍历“链合”在第二顶点上的所有相邻边（步骤740），包 括：将第二顶点设置为边表中的每条相邻边的起始顶点或结束顶点；以及 累计顶点几何。图8中的过程可用于该步骤中。

系统然后如上所述计算并存储第一顶点的所有顶点几何的平均值（步 骤770）。

图8中的过程可用于步骤740和/或760中。

在下述过程中，如下所述，“e_s”代表遍历算法中的第一边，该第一 边可以从链合到正被考虑的顶点上的所有的边中任意选择。“e”代表环中 的被考虑的当前边。最初，“e”等同于“e_s”，但随着遍历的进行，“e” 可能变为下一条边“e_n”。“v”代表正被考虑的顶点，“p”代表“v”的几何。 “p”最初包含根据e_s计算的顶点几何，但随着遍历的进一步进行，它累 计了根据后续边计算的附加的几何（参见在0059处的解释）。“c_p0”指的 是与边“e_s”相关联的第一有向边，而“c_p1”指的是与边“e_s”相关联 的第二有向边，其可能存在或可能不存在。选择哪一条有向边（当两条有 向边都存在时）作为“c_p0”无关紧要。“c_s”等同于“c_p0”，并用于强 调它是遍历过程中的起始有向边。“w”代表当有向边与其相关联的边相比 时有向边的方向关系。如果两个方向相同，则值为1，当方向相反时，则 值为0。“c”代表正被处理的当前有向边，并且在遍历过程中可能改变， 而“l”代表有向边“c”的父环。“c_n”代表在其父环“l”中与“c”紧邻的 有向边，“c_n”应当在“c”之前还是之后取决于“f”与“w”之间的标志关 系。“c_o”代表与同一边“c_n”相关联的其他有向边。当“c_o”变得与“c_s” 相同时（例如，顶点v3将出现此结果）或者当“c_o”变为NULL（空） 时，第一次遍历结束。当“c_o”变为NULL时，意味着在遍历不能再在 当前方向进行下去，则选取边“e_s”的第二有向边“c_p1”用于另一个方 向的遍历。如果需要，该第二遍历与第一次遍历具有完全相同的逻辑，除 了第二遍历开始于“c_p1”，而不是“c_p0”。通常在“c_o”为NULL时， 第二遍历结束。

例如当系统从如图7的父过程中调用该遍历过程时，过程开始（步骤 805）。

系统将边设置为e_s，并且当过程正在计算起始顶点时将顶点标志f_s 设置为0，或当过程正在计算结束顶点时将顶点标志f_s设置为1。系统 设置f＝f_s（步骤810）。当然，此处使用的变量和自变量是任意的。

系统在顶点表中创建顶点v及其几何点p（步骤815）。

系统获得父有向边c_p0及其方向w（步骤820）。如果是与e相反的 方向时，系统将w设置为1，而如果是与e相同方向时，将w设置为0。 系统设置c_s=c=c_p0。

系统在边表中将顶点v设置到边e上（步骤825），并使用来自边e 的贡献来更新顶点表中的p。

系统获得有向边c的父环l（步骤830）。

系统确定环l是否具有单个边（步骤835）。如果具有，过程结束（步 骤840）。

如果环l具有多于一条的边，系统确定是否f＝＝w（步骤845）。如果 f＝＝w，系统将有向边c_n设置为环l中在c之前的有向边（步骤865）。 如果f≠w，系统将有向边c_n设置为环l中在c之后的有向边（步骤850）。

系统获得有向边c_n的边e_n（步骤855）。

系统获得边c_o及其方向w_o（步骤860），其中所述边c_o与e_n 相关联但与有向边c_n方向相反。

系统确定是否c_o==NULL(步骤865)。

如果c_o≠NULL，系统设置e=e_n，c=c_o，w=1 XOR w_0 XOR w XOR f（步骤890），然后返回到步骤825。

如果c_o==NULL（在步骤870处），系统确定是否c_o==c_s（步骤 875）。如果c_o==c_s，过程结束（步骤840）。

如果c_o≠c_s（在步骤875处），系统获得另一个父有向边c_p1及其 方向w，并设置c=c_p1（步骤880）。系统确定是否c==NULL（步骤885）。 如果c==NULL，则过程结束（步骤840）。

如果c≠NULL（在步骤885处），系统返回到步骤825。

因此，图8中的过程遍历与给定边相关的所有边，以根据链合的有向 边来确定顶点。

以美国专利公开2008/0043030公开的美国专利申请11/837,371通过 引用并入本文。

本领域普通技术人员将会认识到，为了简单和清楚起见，适于与本公 开内容一起使用的所有数据处理系统的完整结构和操作将不在此进行描 绘或描述。而是，只对这么多的数据数理系统对于本发明是特有的或对于 本公开内容的理解是必要的内容进行描绘和描述。数据处理系统100的其 他结构和操作可以遵循本领域已知的各种当前的实施和实践中的任一种。

重点要注意的是，尽管本公开内容包括了在全功能系统情况下的描 述，但本领域普通技术人员将会理解的是，本公开内容的机构中的至少一 些部分能够以以任何形式包含在机器可用、计算机可用、计算机可读介质 中的指令的形式进行分布；还要注意的是，本公开内容均进行同样的应用， 而不管用于实际执行该分布的指令或信号承载介质或存储介质的特定类 型如何。机器可用/可读或计算机可用/可读介质的实例包括：非易失性硬 编码型介质，如只读存储器（ROM）或电可擦除可编程只读存储器 （EEPROM）；以及可记录型介质，如软盘、硬盘驱动器和只读光盘 （CD-ROM）或数字多功能磁盘（DVD）。

尽管已经详细地描述了本公开内容的示例性实施方式，本领域普通技 术人员将会理解的是，可以在不脱离本公开内容的最宽泛形式的精神和范 围的情况下，对文中所公开的内容进行各种改变、替代、变化、改进。

本申请中的描述都不应当被理解为含有如下之意：任何特定元件、步 骤或功能是必须被包括在权利要求范围内的基本元素。本专利的主题的范 围仅由所附权利要求限定。此外，没有任何权利要求意在援引35 USC 112 节第六段，除非确切的用词“指的是”跟随有分词。