【论文阅读】简单稳健的三角形表面布尔运算

Simple and Robust Boolean Operations for Triangulated Surfaces${}^{†}$

Abstract

Boolean operations on geometric models are important in numerical simulation and serve as essential tools in the fields of computer-aided design and computer graphics. The accuracy of these operations is heavily influenced by finite precision arithmetic, a commonly employed technique in geometric calculations, which introduces numerical approximations. To ensure robustness in Boolean operations, numerical methods relying on rational numbers or geometric predicates have been developed. These methods circumvent the accumulation of rounding errors during computation, thus preserving accuracy. Nonetheless, it is worth noting that these approaches often entail more intricate operation rules and data structures, consequently leading to longer computation times. In this paper, we present a straightforward and robust method for performing Boolean operations on both closed and open triangulated surfaces. Our approach aims to eliminate errors caused by floatingpoint operations by relying solely on entity indexing operations, without the need for coordinate computation. By doing so, we ensure the robustness required for Boolean operations. Our method consists of two main stages: (1) Firstly, candidate triangle intersection pairs are identified using an octree data structure, and then parallel algorithms are employed to compute the intersection lines for all pairs of triangles. (2) Secondly, closed or open intersection rings, sub-surfaces, and sub-blocks are formed, which is achieved entirely by cleaning and updating the mesh topology without geometric solid coordinate computation. Furthermore, we propose a novel method based on entity indexing to differentiate between the union, subtraction, and intersection of Boolean operation results, rather than relying on inner and outer classification. We validate the effectiveness of our method through various types of Boolean operations on triangulated surfaces.

几何模型上的布尔运算在数值模拟中非常重要，并且是计算机辅助设计和计算机图形学领域中的基本工具。这些运算的准确性在很大程度上受到有限精度算术的影响，这是几何计算中常用的一种技术，它引入了数值近似。为了确保布尔运算的鲁棒性，已经开发了依赖于有理数或几何谓词的数值方法。这些方法避免了计算过程中舍入误差的累积，从而保持了准确性。然而，值得注意的是，这些方法通常涉及更复杂的操作规则和数据结构，因此导致更长的计算时间。在本文中，我们提出了一种简单而鲁棒的方法，用于在封闭和开放的三角化表面上执行布尔运算。我们的方法旨在通过仅依赖实体索引操作来消除浮点运算引起的误差，而无需进行坐标计算。通过这样做，我们确保了布尔运算所需的鲁棒性。我们的方法包括两个主要阶段：（1）首先，使用八叉树数据结构识别候选三角形相交对，然后使用并行算法计算所有三角形对的交线。（2）其次，形成封闭或开放的交环、子表面和子块，这完全通过清理和更新网格拓扑来实现，而无需进行几何实体坐标计算。此外，我们提出了一种基于实体索引的新方法，用于区分布尔运算结果的并集、差集和交集，而不是依赖于内外分类。我们通过对三角化表面进行各种类型的布尔运算来验证我们方法的有效性。

1. Introduction

Numerical modeling methods have garnered extensive usage within the engineering domain. Ensuring the precision of these models necessitates the construction of accurate geometric representations. The construction of geometric models commonly employs various techniques such as boundary representation (B-Rep) [1], wireframe representation [2], and voxel representation [3]. Among these, B-Rep is the predominant method employed for constructing geometric models, primarily relying on parametric surfaces such as non-uniform rational basis spline (NURBS) surfaces or discrete surfaces. The discrete surface represents the decomposition of a specific surface domain, with polygonal meshes, particularly triangular meshes, emerging as the favored form of representation.

数值建模方法在工程领域得到了广泛的应用。确保这些模型的精度需要构建准确的几何表示。几何模型的构建通常采用各种技术，如边界表示（B-Rep）[1]、线框表示[2]和体素表示[3]。其中，B-Rep是构建几何模型的主要方法，主要依赖于参数化曲面，如非均匀有理B样条（NURBS）曲面或离散曲面。离散曲面表示特定曲面域的分解，其中多边形网格，特别是三角网格，成为首选的表示形式。

In the majority of cases, triangular meshes are typically expected to maintain manifold characteristics. However, certain situations, such as dynamic collisions or extensive deformations, may lead to the loss of this property. To restore manifoldness to such meshes, mesh reconstruction becomes necessary [4]. Mesh reconstruction involves employing Boolean operations, which aim to obtain the union, subtraction, and intersection of geometric models in order to reconstruct the desired geometric models.

在大多数情况下，三角网格通常期望保持流形特性。然而，某些情况，如动态碰撞或大范围变形，可能导致这一特性的丧失。为了恢复这些网格的流形性，网格重建变得必要[4]。网格重建涉及使用布尔运算，其目的是获得几何模型的并集、差集和交集，以重建所需的几何模型。

Boolean operations on geometric models are a core element in the field of computeraided design and graphics, and are the basic algorithms for constructing solid geometric models. They are used in the construction industry [5], manufacturing industry [6,7], computer vision [8–10], graphics [11,12], and other scientific research fields [13,14]. Boolean operations are needed to combine and truncate geometric models to generate complex 3D models; therefore, Boolean operations have important research significance.

几何模型上的布尔运算是计算机辅助设计和图形领域的核心元素，是构建实体几何模型的基本算法。它们被应用于建筑行业[5]、制造业[6,7]、计算机视觉[8–10]、图形学[11,12]以及其他科研领域[13,14]。布尔运算用于组合和截断几何模型以生成复杂的三维模型；因此，布尔运算具有重要的研究意义。

Various implementations of Boolean operations can be found in the literature, which can be broadly classified based on three main properties: the type of input data, the type of computation, and the type of output data [15]. Input models encompass a range of sources, including those generated by B-Rep based on NURBS surfaces [16,17], curved surfaces [18], and polygonal meshes [15,19,20], which can be manifold or non-manifold [21]. Most methods focus on performing Boolean operations on manifold surfaces. In terms of computation, Tayebi et al. [16] categorized them into four distinct categories: exact arithmetic methods [19], approximate arithmetic methods [22], interval computation methods, and volumetric methods [23,24]. Among these computation types, exact arithmetic methods and interval computation methods directly calculate Booleans on the initial surfaces, while the other two methods employ indirect approaches.

文献中可以找到布尔运算的各种实现，这些实现可以根据三个主要属性进行大致分类：输入数据的类型、计算的类型和输出数据的类型[15]。输入模型包括一系列来源，包括基于NURBS曲面的B-Rep生成的模型[16,17]、曲面[18]以及多边形网格[15,19,20]，这些网格可以是流形或非流形[21]。大多数方法专注于在流形表面上执行布尔运算。在计算方面，Tayebi等人[16]将其分为四个不同的类别：精确算术方法[19]、近似算术方法[22]、区间计算方法和体积方法[23,24]。在这些计算类型中，精确算术方法和区间计算方法直接在初始表面上计算布尔运算，而其他两种方法则采用间接方法。

During the implementation of direct Boolean operations for mesh models, two crucial procedures significantly impact the effectiveness and efficiency of the overall algorithm. The first procedure involves robustly obtaining intersection lines and loops of all intersected entities in the quickest manner possible. The key aspect of this procedure lies in accurately identifying all potentially intersected entities within a short timeframe to minimize computational costs. Numerous techniques have been developed to achieve this objective, including binary space partitions (BSP) [19], octree [15], OBB trees [25], bipartite graph structure [26], and tracking neighbors [18,27]. The second key procedure pertains to correctly assembling and distinguishing the union, subtraction, and intersection of intersected models. The most straightforward approach is to perform an inside/outside classification [28], which involves examining the location of vertices or facets within the resulting volumes. Different algorithms for direct Boolean operations devise their solutions for addressing these two aforementioned challenges.

在实现网格模型的直接布尔运算过程中，有两个关键步骤显著影响整个算法的有效性和效率。第一个步骤涉及以最快的方式稳健地获取所有相交实体的交线和交环。 该步骤的关键在于在短时间内准确识别所有可能相交的实体，以最小化计算成本。为了实现这一目标，已经开发了许多技术，包括二叉空间分割（BSP）[19]、八叉树[15]、OBB树[25]、二分图结构[26]以及跟踪邻居[18,27]。第二个关键步骤涉及正确组装和区分相交模型的并集、差集和交集。 最直接的方法是执行内外分类[28]，这涉及检查顶点或面在结果体积中的位置。不同的直接布尔运算算法针对上述两个挑战提出了各自的解决方案。

One of the primary challenges encountered in implementing Boolean operations is the utilization of finite precision arithmetic. In geometric calculations, floating-point arithmetic is commonly employed for computing point coordinates [29–31]. Nonetheless, owing to the finite precision nature of floating-point arithmetic, the introduction of rounding errors and loss of precision becomes inevitable [32,33]. Consequently, when calculating and comparing intersection points, small errors may arise, leading to slight deviations from the actual intersection position. These errors may accumulate and produce larger errors in subsequent calculations, thus affecting the final result.

实施布尔运算时遇到的主要挑战之一是有限精度算术的利用。在几何计算中，浮点算术通常用于计算点坐标[29–31]。然而，由于浮点算术的有限精度性质，不可避免地会引入舍入误差和精度损失[32,33]。因此，在计算和比较交点时，可能会出现小误差，导致与实际的交点位置略有偏差。这些误差可能会累积并在后续计算中产生更大的误差，从而影响最终结果。

To address this issue, researchers have employed different approaches. One method involves using rational numbers to represent point coordinates, enabling accurate representation of point locations and ensuring topological correctness of the calculation results [34]. For instance, Hu et al. [32] combined exact rational number calculations with geometric tolerance to robustly solve problems such as self-intersections and gaps in Boolean operations. Trettner et al. [35] and Nehring-Wirxel et al. [36] introduced homogeneous integer coordinates to ensure the accuracy of Boolean operations. However, it is important to note that rational number calculations involve more complex arithmetic rules and data structures, resulting in slower computations compared to floating-point arithmetic, typically by 1 to 2 orders of magnitude. Another alternative approach is to use implicit representation, where the position of a point is described based on specific properties and relationships of the geometry, rather than directly representing the coordinate values. This approach circumvents precision issues inherent in floating-point arithmetic. For example, Attene et al. [37] and Diazzi et al. [38] employ the concept of indirect geometric predicates to handle intersections, ensuring the robustness and speed of Boolean operations.

为了解决这个问题，研究人员采用了不同的方法。一种方法是使用有理数来表示点的坐标，从而能够准确表示点的位置并确保计算结果的拓扑正确性[34]。例如，Hu等人[32]将精确的有理数计算与几何容差相结合，以稳健地解决布尔操作中的自交和间隙等问题。Trettner等人[35]和Nehring-Wirxel等人[36]引入了齐次整数坐标，以确保布尔操作的准确性。然而，需要注意的是，有理数计算涉及更复杂的算术规则和数据结构，导致计算速度比浮点运算慢，通常慢1到2个数量级。另一种替代方法是使用隐式表示，其中点的位置基于几何的特定属性和关系来描述，而不是直接表示坐标值。这种方法绕过了浮点运算固有的精度问题。例如，Attene等人[37]和Diazzi等人[38]采用间接几何谓词的概念来处理交点，确保布尔操作的鲁棒性和速度。

Many novel studies about Boolean operations on polygonal meshes have been presented. For example, Feito [39] introduced an efficient and robust approach for regularized Boolean operations on triangular meshes, encompassing union, subtraction, and intersection operations. This method proves particularly useful in constructing computational models with complex meshes. Gao [40] developed a rasterization-based algorithm, leveraging a many-core GPU, to perform Boolean operations on arbitrarily closed polygons. The algorithm demonstrates higher computational efficiency when handling polygons with a large number of vertices. Qin [41] proposed a fast method for triangle intersection in Boolean operations involving geometric models with triangle meshes. This method, based on the intersection distance criterion, finds utility in modeling underground space engineering. Wang [42] constructed a complex geological model using a robust Boolean operations method. The method prioritizes the robustness of geometric calculations, addressing calculation errors and data inaccuracies. Furthermore, the well-known library CGAL [43] and various open-source packages such as MeshLab [44], OpenFlipper [45], and MEPP [46], also offer robust implementations of Boolean operations. These resources provide additional tools and functionality for reliably performing Boolean operations.

许多关于多边形网格布尔操作的新研究已经提出。例如，Feito [39] 引入了一种高效且稳健的方法，用于在三角网格上进行正则化布尔操作，包括并集、差集和交集操作。这种方法在构建具有复杂网格的计算模型时特别有用。Gao [40] 开发了一种基于光栅化的算法，利用多核 GPU 对任意闭合多边形执行布尔操作。该算法在处理具有大量顶点的多边形时表现出更高的计算效率。Qin [41] 提出了一种在涉及三角网格的几何模型布尔操作中快速计算三角形相交的方法。该方法基于相交距离准则，在地下空间工程建模中找到了应用。Wang [42] 使用一种稳健的布尔操作方法构建了一个复杂的地质模型。该方法优先考虑几何计算的稳健性，解决了计算误差和数据不准确的问题。此外，著名的库 CGAL [43] 和各种开源包，如 MeshLab [44]、OpenFlipper [45] 和 MEPP [46]，也提供了稳健的布尔操作实现。这些资源为可靠地执行布尔操作提供了额外的工具和功能。

When devising algorithms to address specific problems, it is often the case that faster and more efficient algorithms tend to possess higher complexity compared to slower ones. This observation holds for Boolean operations performed on triangular meshes. In this paper, we aim to strike a relative balance between efficiency and complexity in the algorithms we propose. We seek to develop a simple and robust approach for Boolean operations that also exhibits satisfactory efficiency. Here are several key highlights of our method:
(1) An octree-based method for locating and searching possible intersecting triangle pairs is proposed, and a parallel algorithm is used to calculate the intersection lines of candidate intersecting triangle pairs.
(2) An entity index-based method is proposed to obtain intersection rings of triangular surfaces, create sub-surfaces and sub-blocks, and distinguish between merging, intersecting, and subtracting volumes of two intersecting surfaces.
(3) Through these techniques, we reduce computational effort, enhance robustness, and cater to a wide range of triangulated surface Boolean operations.

在设计算法以解决特定问题时，通常更快、更高效的算法往往比速度较慢的算法具有更高的复杂性。这一观察结果同样适用于在三角网格上执行的布尔运算。在本文中，我们旨在提出的算法中在效率和复杂性之间取得相对平衡。我们寻求开发一种简单且稳健的布尔运算方法，同时展现出令人满意的效率。以下是我们方法的几个关键亮点：
(1) 提出了一种基于八叉树的方法来定位和搜索可能的相交三角形对，并使用并行算法计算候选相交三角形对的交线。
(2) 提出了一种基于实体索引的方法来获取三角面的交环，创建子面和子块，并区分两个相交面的合并、相交和相减体积。
(3) 通过这些技术，我们减少了计算量，增强了鲁棒性，并适用于广泛的三角面布尔运算。

The rest of this paper is organized as follows. Section 2 presents the details of the proposed algorithm. Section 3 utilizes five examples to demonstrate the effectiveness of the proposed method. Section 4 discusses the advantages and limitations of the proposed method and future research directions. Section 5 summarizes the work of this paper.

本文的其余部分组织如下。第2节介绍了所提出算法的细节。第3节利用五个例子展示了所提出方法的有效性。第4节讨论了所提出方法的优点和局限性以及未来的研究方向。第5节总结了本文的工作。

2. The Proposed Method

2.1. Overview

In the context of Boolean operations, floating-point arithmetic is commonly used for calculating intersection point coordinates. However, the finite precision of floating-point arithmetic introduces rounding errors and loss of precision. This can result in calculated results that slightly deviate from the actual intersection locations. The accumulation of errors during subsequent calculations can impact the final results. To address this issue, researchers have explored methods to reduce numerical approximation errors. Some approaches involve using rational arithmetic and geometric predicates instead of floatingpoint arithmetic. However, these alternative methods often involve complex arithmetic procedures and data structures.

在布尔运算的上下文中，浮点算术通常用于计算交点坐标。然而，浮点算术的有限精度引入了舍入误差和精度损失。这可能导致计算结果与实际交点位置略有偏差。在后续计算过程中，误差的累积可能会影响最终结果。为了解决这个问题，研究人员探索了减少数值近似误差的方法。一些方法涉及使用有理数算术和几何谓词代替浮点算术。然而，这些替代方法通常涉及复杂的算术程序和数据结构。

This paper presents a straightforward and reliable approach for performing Boolean operations. The proposed method eliminates the need for geometric coordinate calculations by utilizing entity indexing, thus mitigating the accumulation of numerical approximation errors. By focusing on mesh topology elimination and updates, the method constructs intersecting rings, generates sub-surfaces, assembles blocks, and distinguishes between different types of volumes. It is specifically designed to handle Boolean operations on triangulated surfaces, including open and closed surfaces, as well as surfaces that combine both open and closed regions. It is important to note that the triangulated surfaces used in the computation should be populated and free from self-intersections.

本文提出了一种简单可靠的方法来执行布尔运算。所提出的方法通过利用实体索引消除了几何坐标计算的需要，从而减少了数值近似误差的累积。通过专注于网格拓扑的消除和更新，该方法构建了相交环，生成了子表面，组装了块，并区分了不同类型的体积。它专门设计用于处理三角化表面的布尔运算，包括开放和封闭表面，以及结合开放和封闭区域的表面。需要注意的是，计算中使用的三角化表面应被填充且没有自相交。

The proposed method can be summarized into six steps, as depicted in Figure 1. These steps can be categorized into two distinct states: the first state involves computations for entity coordinates, while the second state focuses on operations related to entity indexes. In the first state, the method initially searches for intersected triangle pairs. Once identified, it calculates the intersection lines for each pair of triangles. Subsequently, re-triangulation and updates are performed on the resulting surface meshes. The second stage of the method solely operates on the indexes of entities. It involves forming intersection loops, creating sub-surfaces, and assembling and distinguishing sub-blocks based on the entity indexes.

所提出的方法可以总结为六个步骤，如图1所示。这些步骤可以分为两个不同的状态：第一个状态涉及实体坐标的计算，而第二个状态则专注于与实体索引相关的操作。在第一个状态中，该方法首先搜索相交的三角形对。一旦识别出这些三角形对，它就会计算每对三角形的交线。随后，对生成的表面网格进行重新三角剖分和更新。该方法的第二阶段仅对实体的索引进行操作。它包括形成交线环、创建子表面，以及基于实体索引组装和区分子块。

Step 1: The first step of the proposed method involves searching for candidate intersected triangle pairs. To optimize computational efficiency, a robust and rapid search algorithm is employed to identify potentially intersected triangles. In this study, we utilize the octree structure [47], which enables efficient location and identification of these candidate pairs.
Step 2: Once the candidate intersected triangle pairs have been identified, the next step is to compute the intersection line for each pair. To achieve this, we adopt the algorithm developed by Möller [48], known for its robustness and efficiency. In scenarios where a large number of triangle pairs require intersection calculations, parallel computation techniques based on OpenMP [49] are implemented to enhance performance.
Step 3: After calculating the intersection lines, the next task is to merge and renumber all vertices, as well as update and clear the meshes. The intersection process generates new vertices, while the intersected triangles undergo re-triangulation. To ensure a valid topology, all vertices are merged and renumbered, and all triangles are updated accordingly. This step guarantees the maintenance of a consistent and accurate mesh representation.
Step 4: The fourth step of the proposed method involves connecting the computed intersection lines into closed or open loops. After computing the intersections for each pair of triangles, a set of discrete edges is obtained. These edges need to be connected to form closed or open-oriented loops. If there is no closed loop present on an intersected surface, it indicates that no closed block bounded by triangular facets will be formed.
Step 5: The next step is to obtain sub-surfaces based on the closed loops. A sub-surface comprises the closed loop and all of its incident triangles. The edges of a closed loop are designated as the advancing front, and a new surface is “grown” based on the topology until the number of faces in the sub-surface ceases to increase.
Step 6: Finally, the method proceeds to assemble and distinguish sub-blocks. Sub-blocks can be easily created by assembling related sub-surfaces. Additionally, the boundary closed loops generated in Step 4 can be utilized to represent sub-surfaces. Assembling and distinguishing operations are performed based on these boundary-closed loops.

步骤1：所提出方法的第一步是搜索候选相交三角形对。为了优化计算效率，采用了一种稳健且快速的搜索算法来识别可能相交的三角形。在本研究中，我们使用了八叉树结构[47]，它能够高效地定位和识别这些候选对。
步骤2：一旦识别出候选相交三角形对，下一步就是计算每对的交线。为此，我们采用了Möller[48]开发的算法，该算法以其稳健性和高效性而闻名。在需要计算大量三角形对交线的情况下，基于OpenMP[49]的并行计算技术被用来提升性能。
步骤3：在计算交线之后，接下来的任务是合并并重新编号所有顶点，以及更新和清理网格。相交过程会生成新的顶点，而相交的三角形会进行重新三角化。为了确保拓扑结构的有效性，所有顶点都会被合并并重新编号，所有三角形也会相应更新。此步骤保证了网格表示的一致性和准确性。
步骤4：所提出方法的第四步涉及将计算出的交线连接成闭合或开放的环。在计算每对三角形的交线后，会得到一组离散的边。这些边需要被连接起来形成闭合或开放方向的环。如果在相交表面上没有闭合环，则表明不会形成由三角面片界定的闭合块。
第5步：下一步是基于闭合环获取子表面。子表面包括闭合环及其所有相邻的三角形。闭合环的边被指定为推进前沿，并根据拓扑结构“生长”出一个新的表面，直到子表面中的面数不再增加。
第6步：最后，该方法继续组装和区分子块。通过组装相关的子表面可以轻松创建子块。此外，第4步中生成的边界闭合环可用于表示子表面。组装和区分操作基于这些边界闭合环进行。

2.2. Data Structure and Notation

In this section, we introduce notations for various geometric entities and define additional properties, such as direction, for some of them.

在本节中，我们介绍了各种几何实体的符号，并为其中一些定义了额外的属性，例如方向。

Definition 1. Directed edge is a segment with a specified direction. It consists of two vertices, where the first vertex is referred to as the head and the second vertex as the tail.
Definition 2. Orientated loop is a collection of connected directed edges that can be either closed or open. It can also be represented as an ordered set of vertices. If two oriented loops have the same vertices but in opposite order, they are defined as twins.
Definition 3. Normalized face is a coplanar polygon with a defined normal. In the context of this paper, a normalized face refers to either a triangle or a polygon.

定义1. 有向边是具有指定方向的线段。它由两个顶点组成，其中第一个顶点称为头，第二个顶点称为尾。
定义2. 有向环是一组连接的有向边，可以是闭合的或开放的。它也可以表示为一个有序的顶点集合。如果两个有向环具有相同的顶点但顺序相反，则它们被定义为孪生环。
定义3. 归一化面是具有定义法线的共面多边形。在本文的上下文中，归一化面指的是三角形或多边形。

To facilitate the description of our algorithm in the subsequent sections, we adopt several common geometric objects and allocate arrays to store the corresponding geometric entities.
The “m_aVerts” array comprises vertices representing the intersections and mergers of triangle pairs. It is necessary to verify and renumber all the vertices in this array.
The “m_aEdges” array consists of edges that represent the intersection lines resulting from the intersection of all triangle pairs. The head and tail attributes of each edge in this array are updated following the merging and renumbering of all vertices.
The “m_aLoops” array stores closed or open intersection loops. The ordered set of vertices within each loop must have their IDs updated to reflect the changes.
The “m_aPolys” array contains polygons that are the outcome of intersecting triangle pairs. Each polygon in this array will be decomposed into new triangles through polygon triangulation.
The “m_aTrgls” array is composed of triangles that have been updated through the intersection and merging operations. These triangles originate from two sources: (1) the original triangles that do not intersect with others, and (2) the newly generated triangles resulting from re-triangulating the polygons obtained from intersecting triangle pairs.
The “m_aSurfs” array contains surfaces representing sub-surfaces that have been created. Each sub-surface in this array is associated with one or more boundary sub-loops, which are prepared for the assembly of sub-blocks.
The “m_aBlocks” array stores assembled sub-blocks, encompassing the collected sub-surfaces.

为了便于在后续章节中描述我们的算法，我们采用了几个常见的几何对象，并分配数组来存储相应的几何实体。
“m_aVerts”数组包含表示三角形对的交点和合并的顶点。需要验证并重新编号此数组中的所有顶点。
“m_aEdges”数组由表示所有三角形对相交产生的交线的边组成。在此数组中，每条边的头和尾属性在所有顶点合并和重新编号后更新。
“m_aLoops”数组存储闭合或开放的相交环。每个环内的有序顶点集必须更新其ID以反映这些变化。
“m_aPolys”数组包含作为三角形对相交结果的多边形。此数组中的每个多边形将通过多边形三角剖分分解为新的三角形。
“m_aTrgls”数组由通过相交和合并操作更新的三角形组成。这些三角形来自两个来源：(1) 不与其他三角形相交的原始三角形，以及(2) 通过重新三角剖分从相交三角形对获得的多边形生成的新三角形。
“m_aSurfs”数组包含表示已创建的子表面的表面。此数组中的每个子表面与一个或多个边界子环相关联，这些子环为子块的组装做准备。
“m_aBlocks”数组存储已组装的子块，包括收集的子表面。

2.3. Details of the Proposed Method

In this section, we will provide a comprehensive and detailed description of the six steps involved in our approach. Each step will be discussed individually, highlighting its purpose and methodology. Furthermore, we will explain several procedures, including the clearing of the triangular mesh and the creation of sub-surfaces and sub-blocks. To facilitate understanding and implementation, we will accompany these procedures with pseudocode examples, illustrating the specific algorithms and logic employed.

在本节中，我们将全面详细地描述我们方法中涉及的六个步骤。每个步骤将单独讨论，重点介绍其目的和方法。此外，我们将解释几个程序，包括三角网格的清理以及子表面和子块的创建。为了便于理解和实施，我们将通过伪代码示例来配合这些程序，展示所使用的具体算法和逻辑。

2.3.1. Searching Intersected Triangle Pairs

Before calculating the intersection between any pair of triangles, it is essential to identify which pairs have the potential to intersect. One straightforward but inefficient approach is to conduct a bounding box intersection test between each triangle on a surface and every other triangle. To enhance efficiency, we employ an octree data structure to locate and identify candidate triangle pairs that may intersect.

在计算任何一对三角形之间的交集之前，必须确定哪些对有可能相交。一种简单但效率低下的方法是在表面上的每个三角形与所有其他三角形之间进行边界框交集测试。为了提高效率，我们采用八叉树数据结构来定位和识别可能相交的候选三角形对。

Given two surface meshes, $S_A$ and $S_B$, compute their smallest AABBs denoted as $Bo{x}_A$ and $Bo{x}_B$, respectively, and then calculate the intersection $Bo{x}_{AB}$ of $Bo{x}_A$ and $Bo{x}_B$ ($Bo{x}_{AB}=Bo{x}_A\cap Bo{x}_B$); check each triangle of $S_A$ and $S_B$ whether it is outside of the volume $Bo{x}_{AB}$, and divide $S_A$ and $S_B$ into two sub-arrays where $S_{Aout}+S_{Ain}=S_A,S_{Bout}+S_{Bin}=S_B$; and then extend the volume $Bo{x}_{AB}$ into a cube to be an AABB for the triangles from both $S_{Ain}$ and $S_{Bin}$ ($S_{Ain}\cup S_{Bin}$).

给定两个表面网格 $S_A$ 和 $S_B$，计算它们的最小 AABB，分别记为 $Bo{x}_A$ 和 $Bo{x}_B$，然后计算 $Bo{x}_A$ 和 $Bo{x}_B$ 的交集 $Bo{x}_{AB}$（$Bo{x}_{AB}=Bo{x}_A\cap Bo{x}_B$）；检查 $S_A$ 和 $S_B$ 的每个三角形是否在 $Bo{x}_{AB}$ 的体积之外，并将 $S_A$ 和 $S_B$ 分为两个子数组，其中 $S_{Aout}+S_{Ain}=S_A,S_{Bout}+S_{Bin}=S_B$；然后将 $Bo{x}_{AB}$ 的体积扩展为一个立方体，作为 $S_{Ain}$ 和 $S_{Bin}$ 的三角形的 AABB（$S_{Ain}\cup S_{Bin}$）。

To construct the octree, we begin with a bounding cube as the root node. This root node is then recursively subdivided into eight octants, creating a hierarchical structure. At each interior node of the octree, we keep track of the number of triangles that intersect it from two different sets, denoted as $N_a$ and $N_b$, corresponding to the triangles from $S_{Ain}$ and $S_{Bin}$ , respectively. The recursion process continues until certain termination conditions are met, at which point a node becomes a leaf node. The termination conditions are as follows:
(1) The depth of the node reaches a user-specified maximum depth;
(2) Both $N_a$ and $N_b$ less than a given allowable number;
(3) $N_a$ or $N_b$ is zero.

为了构建八叉树，我们首先以一个边界立方体作为根节点。然后，这个根节点被递归地细分为八个八分体，形成一个层次结构。在八叉树的每个内部节点中，我们跟踪来自两个不同集合的与其相交的三角形数量，分别表示为$N_a$和$N_b$，对应于$S_{Ain}$和$S_{Bin}$中的三角形。递归过程持续进行，直到满足某些终止条件，此时节点成为叶节点。终止条件如下：
(1) 节点的深度达到用户指定的最大深度；
(2) $N_a$ 和 $N_b$ 都小于给定的允许数量；
(3) $N_a$ 或 $N_b$ 为零。

To determine whether a triangle from either $S_{Ain}$ or $S_{Bin}$ is contained within a node of the octree, a straightforward approach is to conduct an intersection test between the bounding box of the triangle and the node of the octree. If the bounding box and the node intersect, it can be inferred that the triangle is inside the node. It is important to note that a triangle may intersect multiple nodes within the octree. To mitigate the computational cost of calculating the bounding box for each triangle individually, we optimize the process by precomputing the bounding boxes for all triangles in $S_{Ain}$ and $S_{Bin}$ beforehand. By calculating these bounding boxes in advance, we can reuse them when necessary, eliminating the need for repeated computations during the intersection tests.

要确定来自 $S_{Ain}$ 或 $S_{Bin}$ 的三角形是否包含在八叉树的节点中，一种直接的方法是进行三角形的包围盒与八叉树节点之间的相交测试。如果包围盒与节点相交，则可以推断该三角形位于节点内。需要注意的是，一个三角形可能会与八叉树中的多个节点相交。为了减少为每个三角形单独计算包围盒的计算成本，我们通过预先计算 $S_{Ain}$ 和 $S_{Bin}$ 中所有三角形的包围盒来优化这一过程。通过提前计算这些包围盒，我们可以在需要时重复使用它们，从而避免在相交测试期间进行重复计算。

2.3.2. Intersecting of Triangles and Re-Triangulating

The intersection of triangles is a task that has been extensively studied, and Möller [48] has developed a robust and efficient algorithm along with its corresponding code for this purpose. In this paper, we directly utilize Möller’s work as our chosen method for performing triangle intersection calculations.

三角形相交是一个被广泛研究的任务，Möller [48] 为此开发了一种稳健且高效的算法及其相应的代码。在本文中，我们直接利用 Möller 的工作作为我们进行三角形相交计算的选择方法。

Given the scenario where a substantial number of triangle pairs require intersection calculations, it becomes crucial to employ an effective parallel strategy. In this step, the intersection calculation for each pair of triangles is independent, enabling us to utilize the OpenMP API [49] to parallelize the computations.

在需要大量三角形对进行相交计算的情况下，采用有效的并行策略变得至关重要。在这一步骤中，每对三角形的相交计算是独立的，这使得我们可以利用 OpenMP API [49] 来并行化这些计算。

#pragma omp parallel for 
for each pair of triangles pi { 
	Calculate the intersection of pi; 
	Save the intersection edge of pi if it exists; 
}

Once the intersection calculation for all triangle pairs is completed, it is common for individual intersected triangles to contain multiple intersection edges within them. This occurs because a triangle may intersect with several other triangles, resulting in the division of the original triangle into multiple sub-polygons along these intersection edges. To generate these sub-polygonal faces for a given triangle, denoted as $T_i$, we follow a series of steps. First, we identify all the intersection edges associated with $T_i$. Then, we connect these edges to form one or more open or closed loops. Finally, we iteratively divide the newly formed polygons using any remaining unused intersection loops until all loops of $T_i$ are utilized. This process is illustrated in Figure 2.

一旦所有三角形对的交集计算完成，通常单个相交的三角形内部会包含多条交边。这是因为一个三角形可能与多个其他三角形相交，导致原始三角形沿着这些交边被分割成多个子多边形。为了为给定三角形$T_i$生成这些子多边形面，我们遵循一系列步骤。首先，我们识别与$T_i$相关的所有交边。然后，我们连接这些边以形成一个或多个开放或闭合的环。最后，我们迭代地使用任何剩余的未使用的交环来分割新形成的多边形，直到$T_i$的所有环都被利用。这个过程如图2所示。

图2. 相交三角形与重新三角剖分。(a) 一个三角形及其边环。(b) 原三角形被分割为2个多边形。© 原三角形完全分割。(d) 子多边形的三角剖分。

As mentioned above, the resulting polygonal faces from the intersection of triangles need to be decomposed into triangles for easier manipulation of the surface mesh in subsequent steps. This can be achieved using an ear-clipping algorithm [50]. However, before applying the ear-clipping algorithm, it is necessary to perform some preprocessing steps due to its validity for planar and counter-clockwise polygons. The partitioning of a polygon P into triangles can be obtained through the following three steps:
Step 1: Compute the local coordinate system of $P$ and transform $P$ into its local representation, denoted as $P^{\prime }$;
Step 2: Determine the orientation of $P^{\prime }$ by evaluating the order of its vertices as either counterclockwise (CCW) or clockwise (CW). If the orientation is CW, reverse the order of vertices in $P^{\prime }$ to ensure it is CCW;
Step 3: Generate the polygon triangulation $T^{\prime }$ of $P^{\prime }$ via ear-clipping and then directly obtain $T$ for $P$ according to $P^{\prime }$, because the topologies of $T$ and $T^{\prime }$ are exactly the same while the coordinates of vertices differ (Figure 2d).

如上所述，三角形相交产生的多边形面需要分解为三角形，以便在后续步骤中更容易操作表面网格。这可以通过使用耳切算法[50]来实现。然而，在应用耳切算法之前，由于其适用于平面和逆时针多边形，因此需要执行一些预处理步骤。将多边形$P$分割为三角形可以通过以下三个步骤实现：
步骤1：计算$P$的局部坐标系，并将$P$转换为其局部表示，记为$P^{\prime }$；
步骤2：通过评估$P^{\prime }$顶点的顺序来确定其方向，即逆时针（CCW）或顺时针（CW）。如果方向为CW，则反转$P^{\prime }$中的顶点顺序，以确保其为CCW；
步骤3：通过耳切生成$P^{\prime }$的多边形三角剖分$T^{\prime }$，然后根据$P^{\prime }$直接获得$P$的$T$，因为$T$和$T^{\prime }$的拓扑结构完全相同，而顶点的坐标不同（图2d）。

2.3.3. Merging and Updating

After intersecting pairs of triangles, new vertices are generated, and the original intersected triangles are replaced with re-triangulated triangles. To ensure a valid topology for subsequent operations, the surfaces need to be merged and updated. The following steps are performed to achieve this:
(1) All vertices are merged and renumbered;
(2) The vertex indexes are updated for each triangle and loop;
(3) Each triangle and loop are checked to identify if there are any vertices with the same index;
(4) The newly generated triangles are reversed (Figure 3).
After the clearing process, several requirements need to be satisfied: there should be no duplicate vertices, no degenerate triangles, no identical vertices within a loop, and no duplicate edges.

在相交的三角形对之后，会生成新的顶点，并且原始的相交三角形会被重新三角化的三角形所取代。为了确保后续操作的有效拓扑，需要合并和更新表面。以下是实现这一目标的步骤：
(1) 所有顶点被合并并重新编号；
(2) 更新每个三角形和环的顶点索引；
(3) 检查每个三角形和环，以确定是否存在具有相同索引的顶点；
(4) 新生成的三角形被反转（图3）。
在清理过程之后，需要满足几个要求：不能有重复的顶点，不能有退化的三角形，环内不能有相同的顶点，也不能有重复的边。

Apart from merging and renumbering vertices, clearing the topology is essential for subsequent procedures such as connecting loops and creating sub-surfaces. In Figure 3, (a) represents the original triangular meshes with three invalid faces that share edges with their adjacent triangles, while (b) shows the cleared version after addressing these issues.

除了合并和重新编号顶点外，清理拓扑结构对于后续的流程（如连接循环和创建子表面）至关重要。在图3中，(a) 表示原始的三角网格，其中包含三个无效面，这些面与相邻的三角形共享边，而 (b) 则展示了在解决这些问题后清理过的版本。

Figure 3. Clear the topology of triangular meshes. (a) Original meshes with invalid triangles $T_0$, $T_1$, and $T_2$. (b) Cleared meshes without same edges.

图3. 清除三角形网格的拓扑。 （a）含无效的三角形 $T_0$，$T_1$ 和 $T_2$ 的原始网格。 (b) 清理后的网格，没有相同的边。

2.3.4. Forming Intersection Loops

As defined in Section 2.2, Oriented loop is a set of connected directed edges, which can be closed as a cycle or open as a polyline. An open loop is an intersection loop in which either the first or the last vertex is shared only by one intersection edge, while each of the other vertices is shared by two edges. A close loop is an intersection loop in which each vertex is shared by at least two intersection edges. We classify the closed intersection loops into hard closed and soft closed:

如第2.2节所定义，定向环是一组连接的有向边，可以闭合为循环或开放为折线。开放环是一种交环，其中第一个或最后一个顶点仅由一条交边共享，而其他每个顶点由两条边共享。闭合环是一种交环，其中每个顶点至少由两条交边共享。我们将闭合交环分为硬闭合和软闭合：

Hard closed loop is characterized by each vertex being shared exclusively by two intersection edges. For example, Figure 4a exhibits six instances of hard closed loops.

硬闭合环的特点是每个顶点仅由两条相交边共享。例如，图4a展示了六个硬闭合环的实例。

Soft closed loop is identified by the first and last vertices being shared by more than two intersection edges, while each intermediate vertex is shared by two edges. Figure 4b illustrates four occurrences of soft closed loops.

软闭合环的特征是首尾顶点被两个以上的相交边共享，而每个中间顶点仅被两条边共享。图4b展示了四个软闭合环的实例。

Only closed intersection loops, which include both hard closed and soft closed loops, are eligible for the creation of sub-surfaces, as mentioned in Section 2.3.5. Loops, whether closed or open, can be formed by directly connecting the head of one edge with the tail of another edge, or vice versa. The process of assembling these loops continues until no more connected edges can be found. The resulting closed or open loops can be visualized as a collection of edges and can also be represented as an ordered set of vertices. When working with an original surface, multiple loops may be present. To determine whether a loop is closed or open, one simply needs to compare the head of the first edge with the tail of the last edge.

如第2.3.5节所述，只有闭合的交集环（包括硬闭合环和软闭合环）才具备创建子曲面的资格。无论是闭合环还是开放环，都可以通过直接连接一条边的头与另一条边的尾（或反之）来形成。组装这些环的过程将持续到找不到更多相连的边为止。最终形成的闭合或开放环可视为边的集合，也可表示为有序顶点集。在处理原始曲面时，可能存在多个环。要判断一个环是闭合还是开放的，只需比较首条边的头与末条边的尾即可。

2.3.5. Creating Sub-Surfaces

Assuming that there is at least one closed loop in the original surface, the process of creating sub-surfaces begins by selecting a closed loop. Each sub-surface consists of the closed loop and the triangles that are incident to it. The edges of the closed loop are designated as the advancing edge front, which gradually expands or “grows” until the number of faces in the sub-surface no longer increases. The growth of the advancing edge front is guided by the topology of the updated surface. To determine the next face in the growing process, a search is performed among the incident faces of the advancing front edge. After each growth step, all advancing front edges must be updated to prepare for the subsequent expansion until a complete sub-surface is formed. The growing process continues until all closed loops have been utilized, at which point the growth terminates (refer to Algorithm 1).

假设原始表面中至少存在一个闭合环，创建子表面的过程从选择一个闭合环开始。每个子表面由闭合环及其相邻的三角形组成。闭合环的边被指定为推进边前沿，该前沿逐渐扩展或“生长”，直到子表面中的面数不再增加。推进边前沿的生长由更新后的表面拓扑结构引导。为了确定生长过程中的下一个面，在推进前沿边的相邻面中进行搜索。在每次生长步骤后，所有推进前沿边都必须更新，为后续扩展做好准备，直到形成一个完整的子表面。生长过程持续进行，直到所有闭合环都被利用，此时生长终止（参见算法1）。

In general, an original surface can give rise to multiple sub-surfaces, which can be classified as either public or private.

一般来说，原始表面可以产生多个子表面，这些子表面可以分为公共或私有两种类型。

Definition 4. Private sub-surface: a sub-surface is considered private when it contains only one closed loop. In this case, the sub-surface is exclusively owned by that loop.
Definition 5. Public sub-surface: a sub-surface is deemed public when it contains more than one closed loop. In such instances, multiple closed loops share the same sub-surface. It is worth noting that if a public sub-surface is generated from an original open surface, it must also include a closed boundary loop in addition to the intersecting closed loop(s).
Definition 6. Sub-surface owner: the sub-surface owner refers to either the single closed loop that possesses a private sub-surface or the collection of multiple closed loops that share a public sub-surface.

定义4. 私有子曲面：当子曲面仅包含一个闭合环时，该子曲面被视为私有。此时，该子曲面由该闭合环独占所有。
定义5. 公共子曲面：当子曲面包含多个闭合环时，该子曲面被视为公共。在此情况下，多个闭合环共享同一子曲面。需注意的是，若公共子曲面由原始开放曲面生成，则除相交闭合环外，还必须包含一个闭合边界环。
定义6. 子曲面所有者：指独占私有子曲面的单个闭合环，或共享公共子曲面的多个闭合环集合。

Remark 1. There can be no more than one public sub-surface present.
Remark 2. There is always at least one private sub-surface in the overall structure.

注1. 结构中最多只能存在一个公共子曲面。
注2. 整体结构中始终存在至少一个私有子曲面。

2.3.6. Assembling and Distinguishing Sub-Blocks

(1) Assembling All Possible Sub-Blocks

After intersecting two original surfaces, $S_A$ and $S_B$, a set of sub-surfaces is obtained. Let us consider a sub-surface, $SS$, from the original surface $S_A$, which consists of n closed loops denoted as $L_i(i=0,...,n-1)$. This implies that there are n owners who share the sub-surface $SS$. If we can identify $n$ private surfaces from the original surface $S_B$, with each private sub-surface solely owned by the corresponding closed-loop $L_i$, it becomes possible to assemble a sub-block. This sub-block comprises the sub-surface $SS$ from surface $S_A$ and the n private surfaces from surface $S_B$. The process of assembling sub-blocks is detailed in Algorithm 2. Furthermore, several conclusions can be drawn regarding the assembly of sub-blocks.

在相交两个原始曲面 $S_A$ 和 $S_B$ 后，得到了一组子曲面。让我们考虑从原始曲面 $S_A$ 中的一个子曲面 $SS$，它由 $n$ 个闭合环 $L_i(i=0,...,n-1)$ 组成。这意味着有 $n$ 个所有者共享这个子曲面 $SS$。如果我们能够从原始曲面 $S_B$ 中识别出 $n$ 个私有曲面，每个私有子曲面仅由相应的闭合环 $L_i$ 拥有，那么就有可能组装一个子块。这个子块由曲面 $S_A$ 中的子曲面 $SS$ 和曲面 $S_B$ 中的 $n$ 个私有曲面组成。组装子块的过程在算法 2 中有详细描述。此外，关于子块的组装可以得出几个结论。

Remark 3. A private sub-surface can be utilized either once or twice in the process of assembling sub-blocks.
Remark 4. A public sub-surface, which does not include a boundary loop, can also be employed once or twice in the assembly of sub-blocks.
Remark 5. A public sub-surface that includes a boundary loop, generated from an original open surface, cannot be used to assemble sub-blocks. This is due to the inability to find a sub-surface that is also owned by the boundary closed loop in the intersected original surface.

注 3. 在组装子块的过程中，私有子表面可以使用一次或两次。
注 4. 不包含边界环的公共子表面也可以在子块组装中使用一次或两次。
注 5. 包含边界环的公共子表面，如果是从原始开放表面生成的，则不能用于组装子块。这是由于在相交的原始表面中无法找到同样由边界闭合环拥有的子表面。

(2) Distinguishing

Based on Algorithm 2, we can generate all possible sub-blocks. Now, the question arises: given two blocks $B_A$ and $B_B$ (Figure 5a), how do we differentiate between their union, intersection, and subtraction? To address this problem, we have developed a novel and straightforward method, which is outlined in Figure 6. The specific flow of this method is presented to provide a solution.

基于算法2，我们可以生成所有可能的子块。现在，问题出现了：给定两个块$B_A$和$B_B$（图5a），我们如何区分它们的并集、交集和差集？为了解决这个问题，我们开发了一种新颖且简单的方法，如图6所示。该方法的具体流程被呈现出来以提供解决方案。

Step 1: To determine the non-subtraction (union and intersection) between blocks, we rely on the orientation of closed intersection loops during the assembly of sub-blocks.

第一步：为了确定块之间的非减法（并集和交集），我们依赖于在子块组装过程中闭合交线环的方向。

However, at this stage, we can only identify whether sub-blocks are subtracted; we cannot clearly distinguish whether they form a union or intersection.

然而，在这个阶段，我们只能识别子块是否被减去；我们无法清楚地区分它们是否形成并集或交集。

Let us consider a sub-block $S_B$, which consists of a total of n closed loops denoted as $L_i(i=0,...,n-1)$. Each closed loop $L_i$ has two opposing versions: $L_i^{+}$ represents the loop with its original orientation, while $L_i^{-}$ represents the loop with the same vertices as $L_i^{+}$ but with the opposite orientation (as illustrated in Figure 7). These two loops, $L_i^{+}$ and $L_i^{-}$ , are referred to as twins in Section 2.2. The loop $L_i$ either owns or shares two sub-surfaces, denoted as $S{S}_{L_i}^A$ and $S{S}_{L_i}^B$ , originating from two different original surfaces, $S_A$ and $S_B$, respectively. To determine the sub-block $S_B$, we can apply the following conditions:

让我们考虑一个子块 $S_B$，它由总共 n 个闭合环组成，记为 $L_i(i=0,...,n-1)$。每个闭合环 $L_i$ 有两个相反的版本：$L_i^{+}$ 表示具有原始方向的环，而 $L_i^{-}$ 表示与 $L_i^{+}$ 具有相同顶点但方向相反的环（如图 7 所示）。这两个环 $L_i^{+}$ 和 $L_i^{-}$ 在第 2.2 节中被称为孪生环。环 $L_i$ 拥有或共享两个子表面，分别记为 $S{S}_{L_i}^A$ 和 $S{S}_{L_i}^B$，它们分别来自两个不同的原始表面 $S_A$ 和 $S_B$。为了确定子块 $S_B$，我们可以应用以下条件：

Case 1: if $S{S}_{L_i}^A$ and $S{S}_{L_i}^B$ are owned or shared by $L_i^{+}$ and $L_i^{-}$ , respectively, or if $S{S}_{L_i}^A$ and $S{S}_{L_i}^B$ are owned or shared by $L_i^{+}$ and $L_i^{-}$ , respectively, then the sub-block $S_B$ is union or intersection volume.

情况1：如果$S{S}_{L_i}^A$和$S{S}_{L_i}^B$分别由$L_i^{+}$和$L_i^{-}$拥有或共享，或者如果$S{S}_{L_i}^A$和$S{S}_{L_i}^B$分别由$L_i^{+}$和$L_i^{-}$拥有或共享，那么子块$S_B$是并集或交集体积。

Case 2: if both $S{S}_{L_i}^A$ and $S{S}_{L_i}^B$ are owned or shared by $L_i^{+}$, or if both $S{S}_{L_i}^A$ and $S{S}_{L_i}^B$ are owned or shared by $L_i^{-}$ , then the sub-block SB is subtraction volume.

情况2：如果$S{S}_{L_i}^A$和$S{S}_{L_i}^B$都由$L_i^{+}$拥有或共享，或者如果$S{S}_{L_i}^A$和$S{S}_{L_i}^B$都由$L_i^{-}$拥有或共享，那么子块SB就是减法体积。

Step 2: To distinguish between the union and intersection operations, we follow the following approach.

第2步：为了区分并集和交集操作，我们采用以下方法。

As previously mentioned, we denote $(B_A\cup B_B)$, $(B_A\cap B_B)$, $(B_A-B_B)$, and $(B_B-B_A)$ as the union, intersection, and subtraction operations between a pair of blocks $B_A$ and $B_B$. It is evident that the relationship $(B_A\cap B_B)$≤ $(B_A\cup B_B)$ holds. The exception to this relationship occurs only when BA and BB coincide, which can be identified and addressed separately, and thus does not need to be considered at this stage. Consequently, we conclude that $(B_A\cap B_B)$ < $(B_A\cup B_B)$. The aforementioned result establishes that the intersection operation between two blocks is consistently smaller in size than their corresponding union operation. Furthermore, it indicates that the minimum coordinates of all vertices within the intersection are never smaller than those of the union, while the maximum coordinates of the intersection are never larger than those of the union. Consequently, the minimum and maximum coordinates of the vertices obtained from both the union and intersection are precisely equal to those derived solely from the union.

如前所述，我们将$(B_A\cup B_B)$、$(B_A\cap B_B)$、$(B_A-B_B)$和$(B_B-B_A)$分别表示为一对块$B_A$和$B_B$之间的并集、交集和差集操作。显然，关系$(B_A\cap B_B)$≤ $(B_A\cup B_B)$成立。此关系的例外情况仅当$B_A$和$B_B$重合时发生，这种情况可以单独识别和处理，因此在此阶段无需考虑。因此，我们得出结论$(B_A\cap B_B)$ < $(B_A\cup B_B)$。上述结果证明，两个块之间的交集操作在大小上始终小于其对应的并集操作。此外，它还表明交集中所有顶点的最小坐标永远不会小于并集的最小坐标，而交集的最大坐标永远不会大于并集的最大坐标。因此，从并集和交集中获得的顶点的最小和最大坐标恰好等于仅从并集中获得的坐标。

Thus, we can distinguish the union and the intersection by following three sub-procedures.
Step 2-1: By sorting all vertices, we can easily obtain the maximum and minimum coordinates of both the intersection and union, denoted as $N_{max}^{Total}$ and $N_{min}^{Total}$ , respectively, (Figure 6). These coordinates can be stored during the merging and updating of vertices.
Step 2-2: To identify the union volume, we compare the maximum and minimum coordinates of each candidate union sub-block, denoted as $N_{max}^{SB}$ and $N_{min}^{SB}$, respectively (Figure 6). If these coordinates match the values obtained in Step 2-1, then it signifies the presence of only union volume (Figure 5c).
Step 2-3: The remaining sub-block(s) are considered to be the intersection volume (Figure 5c).

因此，我们可以通过以下三个子步骤来区分并集和交集。
步骤2-1：通过对所有顶点进行排序，可以轻松获得交集和并集的最大及最小坐标，分别记为$N^{Total}max$和$N^{Total}min$（图6）。这些坐标可以在顶点合并和更新过程中存储。
步骤2-2：为了识别并集体积，我们将每个候选并集子块的最大和最小坐标（分别记为$N^{SB}max$和$N^{SB}min$）与步骤2-1中获得的值进行比较（图6）。如果这些坐标匹配，则表明仅存在并集体积（图5c）。
步骤2-3：剩余的子块被视为交集体积（图5c）。

It is important to note that these procedures are not applicable in special cases where mesh $B_A$ is contained within $B_B$ or vice versa. These exceptional cases should be handled separately during the preprocessing stage.

重要的是要注意，这些过程不适用于在 $B_B$ 中包含网格 $B_A$ (或相反) 的特殊情况下。这些例外情况应在预处理阶段分别处理。

Step 3: Determine all subtractions

步骤3：确定所有减法

After classifying the union and intersection, the subtractions $(B_A-B_B)$ and $(B_B-B_A)$ can be easily determined: define all sub-surfaces that comprise the only union volume as outer ones, while those from the intersection volume(s) as inner, for each undistinguished sub-block,
(1) Identify the sub-surfaces within the sub-block. If any of the sub-surfaces belong to the original block $B_A$ and are classified as outer surfaces, then the sub-block is considered as part of the $(B_A-B_B)$ subtraction operation. Otherwise, if the sub-surfaces belong to the original block $B_B$ and are classified as outer surfaces, the sub-block is considered as part of the $(B_B-B_A)$ subtraction operation.
(2) Similarly, if any of the sub-surfaces within the sub-block are classified as inner surfaces (part of the intersection volume), and they belong to the original block BA, then the sub-block is considered as part of the $(B_B-B_A)$ subtraction operation. Conversely, if the inner sub-surface(s) belong to the original block BB, the sub-block is considered as part of the $(B_A-B_B)$ subtraction operation.
After distinguishing the subtractions, all triangles within the inner sub-surfaces of the subtraction operations are reversed. This ensures a valid topology for the entire mesh model and ensures that the normals of all facets are oriented outward.

在分类并集和交集之后，可以轻松确定减法 $(B_A-B_B)$ 和 $(B_B-B_A)$：将仅包含并集体积的所有子表面定义为外部表面，而将来自交集体积的子表面定义为内部表面，对于每个未区分的子块，
(1) 识别子块内的子表面。如果任何子表面属于原始块 $B_A$ 并被分类为外部表面，则该子块被视为 $(B_A-B_B)$ 减法操作的一部分。否则，如果子表面属于原始块 $B_B$ 并被分类为外部表面，则该子块被视为 $(B_B-B_A)$ 减法操作的一部分。
(2) 类似地，如果子块内的任何子表面被分类为内部表面（交集体积的一部分），并且它们属于原始块 $B_A$，则该子块被视为 $(B_B-B_A)$ 减法操作的一部分。相反，如果内部子表面属于原始块 $B_B$，则该子块被视为 $(B_A-B_B)$ 减法操作的一部分。
在区分减法操作后，减法操作内部子表面内的所有三角形都会被反转。这确保了整个网格模型的有效拓扑，并确保所有面的法线朝外。

3. Results

As outlined in Section 1, our objective is to execute Boolean operations on a pair of surfaces. These surfaces can either be open or closed. In this section, we demonstrate the Boolean operations for various pairs of surfaces, encompassing open-and-open scenarios (Figure 8), open-and-closed scenarios (Figures 9 and 10), as well as closed-and-closed scenarios (Figures 11 and 12). Through these examples, we aim to showcase the effectiveness of our approach.

如第1节所述，我们的目标是在一对表面上执行布尔运算。这些表面可以是开放的或封闭的。在本节中，我们展示了各种表面对的布尔运算，包括开放与开放的情况（图8）、开放与封闭的情况（图9和图10），以及封闭与封闭的情况（图11和图12）。通过这些示例，我们旨在展示我们方法的有效性。

The intersection of a pair of open triangulated surfaces is tested in Figure 8. Before considering the boundary outer loops of the original surfaces, four open intersection loops can be formed for each surface, and then the boundary loop is divided into five closed loops; therefore, five corresponding sub-surfaces can be created for each surface.

在图8中测试了一对开放三角曲面的交集。在考虑原始曲面的边界外环之前，每个曲面可以形成四个开放交集环，然后将边界环划分为五个闭合环；因此，每个曲面可以创建五个相应的子曲面。

To evaluate the Boolean operations between an open surface and a closed surface, we conduct a division of a planar meshed surface using a triangulated Chinese lion model. The Chinese lion model (Figure 9) is sourced from http://shapes.aim-at-shape.net/, accessed on 1 June 2013. As depicted in Figure 9, three closed loops can be identified in both the Chinese lion and the surface. Figure 10 illustrates the division results, where four subsurfaces are generated for each original surface, and the lion model is partitioned into four sub-blocks. These outcomes demonstrate the successful execution of the Boolean operations and the creation of distinct sub-surfaces and sub-blocks.

为了评估开放表面和闭合表面之间的布尔操作，我们使用三角化的中国狮子模型对一个平面网格表面进行分割。中国狮子模型（图9）来源于http://shapes.aim-at-shape.net/，访问日期为2013年6月1日。如图9所示，在中国狮子和表面上都可以识别出三个闭合环。图10展示了分割结果，其中每个原始表面生成了四个子表面，狮子模型被分割成四个子块。这些结果证明了布尔操作的成功执行以及不同子表面和子块的创建。

To test the Boolean operations on two closed surfaces, we provide examples of such operations using a pair of cylinders (Figure 11) and a pair of toruses (Figure 12). When computing the intersection edges of triangles for the cylinders, we observe the formation of four soft closed intersection loops (as defined in Section 2.3.4). These soft closed loops exhibit the characteristic that both the first and last vertices are shared by four intersection edges. Utilizing these soft closed loops, we can create four sub-surfaces for each cylinder and subsequently assemble and distinguish sub-blocks, including union, intersection, and subtractions, based on the sub-surfaces. Figure 12 illustrates the Boolean operations performed on a pair of toruses with identical inner radii. The process is similar to that of the cylinders but slightly more intricate. In these examples, only soft closed loops are generated. However, Figure 5 provides a simple example where hard closed loops are obtained.

4. Discussion

4.1. Comparative Analysis with Other Methods

4.1.1. Advantages of the Proposed Algorithm

This paper presents a straightforward and reliable algorithm for conducting Boolean operations on manifold triangulated surfaces, while the algorithm does not account for self-intersecting meshes, it demonstrates its effectiveness in handling diverse types of triangulated surfaces. The proposed algorithm offers several notable advantages, including simplicity, improved computational efficiency, and enhanced robustness. It introduces a dependable approach for executing Boolean operations and finds applicability across various scenarios involving triangulated surfaces. The subsequent analysis provides a comprehensive comparison highlighting the specific improvements achieved by the proposed algorithm in contrast to commonly employed algorithms.

本文提出了一种简单可靠的算法，用于在流形三角化表面上进行布尔运算。虽然该算法未考虑自交网格，但它展示了在处理各种类型三角化表面时的有效性。所提出的算法具有几个显著优势，包括简单性、提高的计算效率和增强的鲁棒性。它引入了一种执行布尔运算的可靠方法，并适用于涉及三角化表面的各种场景。随后的分析提供了全面的比较，突出了所提出算法相对于常用算法的具体改进。

(1) The proposed algorithm offers reduced computational effort and improved computational efficiency for Boolean operations on geometric models. Traditionally, obtaining the intersection lines and intersection rings of intersecting entities is a crucial step. In this paper, an octree-based method is employed to locate and search intersecting triangle pairs, while a parallel algorithm is used to compute the intersection lines of these pairs.
Compared to algorithms based on BSP [19], the octree algorithm addresses the efficiency problem caused by unnecessary partitioning during BSP tree construction. Additionally, the octree algorithm overcomes the limitation of BSP trees, which can only perform Boolean operations on two models. The proposed method leverages the octree algorithm to reduce the overall computational effort required for Boolean operations when obtaining candidate intersecting triangle pairs of triangulated surfaces. Furthermore, the use of a parallel algorithm enhances the computational efficiency when calculating the intersection lines of intersecting triangle pairs.

(1) 该算法为几何模型的布尔运算提供了计算量缩减和计算效率提升的创新方案。传统方法中，获取相交实体的交线与交环是关键步骤。本研究采用八叉树方法定位搜索相交三角面片对，并运用并行算法计算这些面片对的交线。相较于基于BSP[19]的算法，八叉树算法解决了BSP树构建过程中不必要分割导致的效率问题，同时突破了BSP树仅能对两个模型进行布尔运算的局限。本方法利用八叉树算法在获取三角化曲面候选相交面片对时，降低了布尔运算整体计算量；此外，通过并行算法计算相交面片对的交线，进一步提升了运算效率。

(2) The proposed algorithm enhances the robustness of Boolean operations by addressing the correct assembly and differentiation of merge, subtraction, and intersection regions in intersecting models. Once the intersection lines of triangulated surfaces are obtained, the subsequent task is to accurately determine these regions. In this paper, a solid index-based method is introduced to create sub-surfaces, sub-blocks, and other entities by manipulating the mesh topology through elimination and updates. Building upon this approach, the direction of directed rings on the newly generated sub-surfaces is utilized to identify the merge, intersection, and subtraction regions resulting from the Boolean operation. A previously proposed method, called BoolSurf, by Riso et al. [51], enables Boolean operations between shapes bounded by freely intersecting curves on any surface, including open surfaces. However, BoolSurf relies on standard floating-point arithmetic, which introduces numerical approximation errors during computation. Additionally, it employs traditional inner and outer classification methods to distinguish the outcomes of merging, intersecting, and subtracting operations.
In contrast, our method improves the Boolean operation process by introducing an entity index-based approach that eliminates the need for coordinate calculations, thereby avoiding numerical approximation errors and enhancing the robustness of Boolean operations. Moreover, the entity index-based method is employed to accurately differentiate between merge, intersection, and subtraction regions, eliminating the requirement for an extensive point or face calculations based on the position of the entity model using traditional classification methods of inner and outer regions.

（2）所提算法通过解决相交模型中合并域、差集域与交集域的正确组装与区分问题，增强了布尔运算的鲁棒性。在获得三角化曲面交线后，后续核心任务是精确判定这些区域。本文提出基于实体索引的方法，通过网格拓扑的消除与更新操作生成子曲面、子区块等实体。在此基础之上，利用新生子曲面上有向环的方向性来识别布尔运算产生的合并域、交集域和差集域。Riso等人[51]先前提出的BoolSurf方法支持任意曲面（包括开放曲面）上自由相交曲线所界定形状间的布尔运算，但该方法依赖标准浮点运算机制，会在计算过程中引入数值近似误差；同时采用传统内外分类法来区分并、交、差运算结果。
相较而言，本方法通过引入基于实体索引的运算机制，避免了坐标计算需求，从而规避数值近似误差并提升布尔运算鲁棒性。此外，采用实体索引法精确区分合并域、交集域与差集域，无需基于实体模型位置通过传统内外区域分类法进行大量点面计算。

(3) The proposed method achieves a balance between computational efficiency and computational accuracy. The widely recognized computational geometry library CGAL utilizes rational number arithmetic for exact computations, ensuring high robustness by avoiding rounding errors in floating-point arithmetic [43,52]. However, the reliance on rational number arithmetic introduces complexity to the computation process. Additionally, CGAL requires the input model to be converted to Nef polygons, which involves a complex data structure and imposes a substantial memory footprint at runtime [53].
In contrast, our method improves upon the necessity of rational number arithmetic for computing intersection coordinates, thereby enhancing robustness. Instead of relying on rational number arithmetic, we employ the entity indexing method for Boolean operations. Notably, our method does not impose any additional requirements on the input model and avoids the need for excessive preprocessing. As a result, our approach strikes a favorable balance between computational efficiency and computational accuracy.

（3）所提出的方法在计算效率与计算精度之间实现了平衡。广受认可的计算几何库CGAL采用有理数算术进行精确计算，通过避免浮点运算中的舍入误差确保了高鲁棒性[43,52]。然而，依赖有理数算术会为计算过程引入复杂性。此外CGAL要求将输入模型转换为Nef多边形，这涉及复杂的数据结构并在运行时占用大量内存[53]。
相比之下，我们的方法改进了计算交点坐标时对有理数算术的依赖，从而提升了鲁棒性。我们采用实体索引法进行布尔运算，而非依赖有理数算术。值得注意的是，该方法不对输入模型提出额外要求，也避免了繁琐的预处理步骤。因此，本方法在计算效率和计算精度之间取得了良好平衡。

(4) The proposed algorithm extends the range of geometric models to which Boolean operations can be applied. Diazzi et al. [38] introduced a method that utilizes indirect geometric predicates to generate a convex polyhedral mesh representing the internal volume of a triangular input surface. This method explicitly defines the solid model based on the geometric properties of the input polygons. Employing an implicit approach avoids the need for coordinate calculations during Boolean operations and minimizes the occurrence of numerical approximation errors. However, this method is limited in its ability to handle Boolean operations on open surfaces.
In contrast to the Boolean method based on indirect geometric predicates proposed by Diazzi et al. [38], our proposed method is not restricted to specific surface types or combinations. The algorithm we present is effective and applicable regardless of whether it involves open surfaces, closed surfaces, or a combination of both. This versatility is particularly valuable in fields such as computational and aided design, computer graphics, and numerical simulation, where complex geometric processing and analysis are required. By extending the applicability of Boolean operations to a wider range of geometric models, our method offers increased flexibility and utility in various domains.
（4）所提算法将布尔运算的适用范围扩展至更多几何模型。Diazzi等人[38]提出一种利用间接几何谓词的方法，可生成表示三角面片输入表面内部体积的凸多面体网格。该方法基于输入多边形的几何特性明确定义实体模型，采用隐式处理避免布尔运算过程中的坐标计算，并显著减少数值近似误差的出现。但该方法处理开放曲面布尔运算的能力有限。
与Diazzi等人[38]基于间接几何谓词的布尔方法不同，我们提出的方法不受特定曲面类型或组合的限制。无论涉及开放曲面、封闭曲面还是两者混合，本文算法均能有效适用。这种通用性在需要复杂几何处理与分析的计算辅助设计、计算机图形学和数值仿真等领域尤为重要。通过将布尔运算的适用性扩展到更广泛的几何模型，本方法为各领域提供了更强的灵活性与实用性。

4.1.2. Disadvantages of the Proposed Algorithm

Although the triangulated surface Boolean algorithm proposed in this paper shows good robustness in handling various types of flow triangulated surfaces, it is necessary to acknowledge its drawbacks and challenges.

尽管本文提出的三角网格表面布尔算法在处理各种类型的流动三角网格表面时表现出良好的鲁棒性，但必须承认其存在的缺点和挑战。

(1) The proposed method introduces a complex data structure and involves numerous judgments and checks during the computation process. In contrast to the floating-point arithmetic-based method BoolSurf [51], the entity index-based Boolean operation presented in this paper necessitates the construction and management of intricate data structures to represent surface relationships. Consequently, this leads to computational and memory overheads. Although coordinate computation is not required for creating sub-surfaces and sub-blocks, determining the merge, intersection, and subtraction regions of the model after Boolean operations entail a substantial amount of judgment and checking.

(1) 所提出的方法引入了复杂的数据结构，并在计算过程中涉及大量的判断和检查。与基于浮点运算的方法 BoolSurf [51] 相比，本文提出的基于实体索引的布尔运算需要构建和管理复杂的数据结构来表示表面关系。因此，这导致了计算和内存开销。尽管在创建子表面和子块时不需要进行坐标计算，但在布尔运算后确定模型的合并、相交和相减区域需要进行大量的判断和检查。

(2) The proposed method has difficulties in dealing with models with defective inputs. In comparison to Boolean methods based on indirect geometric predicates [38], the entity index-based approach may encounter difficulties when dealing with complex geometric scenarios or inputs that contain defects. These defects include self-intersecting surfaces, non-manifold surfaces, and surfaces with voids or gaps. Ensuring the correctness of Boolean operations in such cases may require additional processing and repair steps. These additional steps introduce complexity and implementation challenges to the algorithm.

（2）所提出的方法在处理输入模型存在缺陷时面临困难。与基于间接几何谓词的布尔方法[38]相比，基于实体索引的方法在应对复杂几何场景或含有缺陷的输入时可能遇到困难。这些缺陷包括自相交表面、非流形表面以及带有孔洞或间隙的表面。在此类情况下确保布尔运算的正确性可能需要额外的处理和修复步骤，这些额外步骤会给算法带来复杂性和实施挑战。

(3) The entity index-based Boolean operation method may face performance and scalability challenges as the size of geometric data increases. When dealing with highresolution grids, the proposed method requires significant memory and computational resources for constructing and maintaining data structures. The judgment and checking processes performed on a large number of triangular surfaces contribute to increased execution time. To address performance challenges, researchers have proposed various techniques. For instance, Cherchi et al. [33] introduced an improved mesh arrangement method and a new internal and external classification system based on exact ray projection. This approach aimed to enhance the efficiency of triangular mesh Boolean operations, particularly for interactive applications. However, it still exhibits limitations when applied to very high-resolution meshes, typically exceeding 200K triangles. In light of the rapid development of computer technology, parallel strategies utilizing multicore GPUs hold significant potential in improving computational efficiency. For example, Xiao et al. [54] developed a multi-core GPU-based triangle intersection algorithm capable of detecting around 1.5 billion triangle pairs in less than 0.5 s.

(3) 基于实体索引的布尔运算方法在几何数据规模增加时可能面临性能和可扩展性挑战。在处理高分辨率网格时，所提出的方法需要大量的内存和计算资源来构建和维护数据结构。对大量三角面片进行的判断和检查过程会导致执行时间增加。为了解决性能挑战，研究人员提出了各种技术。例如，Cherchi等人[33]引入了一种改进的网格排列方法和基于精确射线投影的新内外分类系统。该方法旨在提高三角网格布尔运算的效率，特别是在交互式应用中。然而，当应用于通常超过20万个三角形的高分辨率网格时，它仍然表现出局限性。鉴于计算机技术的快速发展，利用多核GPU的并行策略在提高计算效率方面具有巨大潜力。例如，Xiao等人[54]开发了一种基于多核GPU的三角形相交算法，能够在不到0.5秒的时间内检测约15亿个三角形对。

4.2. Outlook and Future Work

Boolean operations on triangulated surfaces play a crucial role in computer-aided design, computer vision and graphics, and numerical simulation. These operations enable the manipulation of complex geometries by performing merging, intersection, and subtraction operations. The application of Boolean operations has a significant impact on various industries, including aerospace, automotive, architecture, medical, agricultural, and entertainment. By leveraging Boolean operations, designers and engineers can enhance their design capabilities and create intricate and customized objects. This, in turn, contributes to improved product design and development processes. Overall, Boolean operations on triangulated surfaces offer numerous benefits across various fields, enabling advanced design capabilities, cost-effective manufacturing processes, sophisticated simulations, and a deeper understanding of real-world phenomena.

在三角化表面上的布尔运算在计算机辅助设计、计算机视觉与图形学以及数值模拟中扮演着至关重要的角色。这些运算通过执行合并、相交和相减操作，使得复杂几何形状的操控成为可能。布尔运算的应用对多个行业产生了重大影响，包括航空航天、汽车、建筑、医疗、农业和娱乐。通过利用布尔运算，设计师和工程师能够增强其设计能力，并创造出复杂且定制化的物体。这进而有助于改进产品设计和开发流程。总体而言，三角化表面上的布尔运算在各个领域提供了诸多益处，使得先进的设计能力、成本效益高的制造流程、复杂的模拟以及对现实世界现象的深入理解成为可能。

Although the proposed algorithm in this paper exhibits good robustness, it also has some limitations and areas for further improvement. In future research, the focus will be on enhancing the proposed method by simplifying the data structure and reducing the computational overhead caused by numerous judgments and checks, while still maintaining the robustness of Boolean operations. Additionally, further research is needed to address specific challenges associated with trigonometric surfaces, such as complex topological relationships, self-intersections, defects, and other special cases that commonly occur in practical applications. Developing strategies to handle these scenarios will enhance the algorithm’s versatility and make it more applicable in real-world situations.

尽管本文提出的算法表现出良好的鲁棒性，但它也存在一些局限性和需要进一步改进的地方。在未来的研究中，重点将放在通过简化数据结构和减少由大量判断和检查引起的计算开销来增强所提出的方法，同时仍保持布尔运算的鲁棒性。此外，还需要进一步研究以解决与三角曲面相关的具体挑战，例如复杂的拓扑关系、自交、缺陷以及在实际应用中常见的其他特殊情况。开发处理这些场景的策略将增强算法的多功能性，使其在现实世界中更具适用性。

Furthermore, it is crucial to explore the integration of the proposed algorithms with existing efficient data structures, parallel algorithms, and optimization techniques. This integration can significantly improve the computational efficiency and scalability of the algorithm, particularly when dealing with large-scale triangulated surfaces or high-resolution models. The ability to process such data in real-time and interactive applications is essential for practical implementation.

此外，探索将所提出的算法与现有的高效数据结构、并行算法和优化技术相结合至关重要。这种集成可以显著提高算法的计算效率和可扩展性，特别是在处理大规模三角化表面或高分辨率模型时。在实际应用中，能够实时和交互式地处理此类数据是至关重要的。

In conclusion, future research endeavors will focus on simplifying the algorithm, addressing complex geometric scenarios, and integrating it with efficient data structures, parallel algorithms, and optimization techniques. These advancements will contribute to improving the overall performance and scalability of the proposed method, thus enhancing its applicability in various domains.

总之，未来的研究工作将集中于简化算法、处理复杂的几何场景，并将其与高效的数据结构、并行算法和优化技术相结合。这些进展将有助于提高所提出方法的整体性能和可扩展性，从而增强其在各个领域的适用性。

5. Conclusions

This paper presents simple and robust algorithms for Boolean operations in geometric modeling. The proposed algorithms are validated using various pairs of surfaces, including open–open, open–closed, and closed–closed cases. Our approach utilizes exact arithmetic methods for computation and employs octree for efficient triangle location and intersection detection. Furthermore, a parallel algorithm is utilized to calculate the intersection lines of triangles. We classify intersection loops into open, hard closed, and soft closed categories, and use them to create sub-surfaces by expanding from the closed intersection loops. Sub-blocks are then easily assembled based on the boundary loops of sub-surfaces and distinguished by comparing the minimum and maximum coordinates of the updated vertices.

本文提出了几何建模中布尔运算的简单且鲁棒的算法。所提出的算法通过多种表面组合进行了验证，包括开放-开放、开放-闭合和闭合-闭合的情况。我们的方法采用精确算术方法进行计算，并利用八叉树进行高效的三角形定位和相交检测。此外，使用并行算法计算三角形的交线。我们将相交环分类为开放、硬闭合和软闭合三类，并通过从闭合相交环扩展来创建子表面。然后，根据子表面的边界环轻松组装子块，并通过比较更新顶点的最小和最大坐标来区分它们。

Our approach consists of two stages. The first stage involves calculating intersection lines for triangles and subsequently merging and updating the resulting surfaces. This stage requires coordinate calculations to handle geometric entities. In the second stage, we focus on forming intersection loops, creating sub-surfaces, assembling sub-blocks, and distinguishing between them. Unlike the first stage, this stage operates solely on the cleared and updated topology of triangular meshes without involving coordinate computations of geometric entities. We have demonstrated the effectiveness of our approach through several test examples.

我们的方法包括两个阶段。第一阶段涉及计算三角形的交线，随后合并和更新生成的表面。此阶段需要进行坐标计算以处理几何实体。在第二阶段，我们专注于形成交线环、创建子表面、组装子块并区分它们。与第一阶段不同，此阶段仅操作清理和更新后的三角网格拓扑，而不涉及几何实体的坐标计算。我们通过几个测试示例展示了我们方法的有效性。

While the proposed triangular surface Boolean algorithm demonstrates robustness in handling a wide range of triangular surfaces without self-intersection, such as open and closed surfaces, it may encounter challenges when dealing with complex geometric problems or defective inputs. Additionally, as geometric data scales up, Boolean methods based on entity indexes may experience performance and scalability issues. Future research will focus on addressing Boolean operations for triangulated surfaces with complex topological relations, self-intersections, defects, and other special cases. This will involve incorporating efficient data structures, parallel computing, and optimization algorithms to enhance the computational efficiency and scalability of the proposed algorithms.

尽管所提出的三角面布尔算法在处理各种无自交的三角面（如开放和闭合表面）时表现出鲁棒性，但在处理复杂几何问题或有缺陷的输入时可能会遇到挑战。此外，随着几何数据规模的扩大，基于实体索引的布尔方法可能会遇到性能和可扩展性问题。未来的研究将集中于解决具有复杂拓扑关系、自交、缺陷和其他特殊情况的三角面布尔操作。这将涉及引入高效的数据结构、并行计算和优化算法，以提高所提出算法的计算效率和可扩展性。