An Effective Method for Slicing Triangle Meshes Using a Freeform Curve

Abstract

Slicing 3D polygonal meshes is a fundamental operation in various applications such as virtual surgery, garment simulation, and game development. Existing methods primarily slice meshes using either a single line or a set of line segments approximating a smooth curve. This paper introduces a novel approach to freely slice a triangle mesh using a freeform curve without discretizing it into line segments. The user draws a stroke on the screen, defining the desired cutting trajectory. Subsequently, a freeform curve approximating this stroke is generated and extended into a ruled surface in the user’s viewing direction. To efficiently compute intersections between the ruled surface and a triangle mesh, the Line–Surface Intersection (LSI) problem is broken down into two subproblems: Plane–Curve Intersection (PCI) followed by Line–Line Intersection (LLI). Intersection points are then connected to form polylines, effectively cutting the mesh into multiple submeshes. To ensure the solidity of the submeshes, cross-sections are generated by trimming the ruled surface along the polylines and merged with the corresponding submeshes. Our method empowers users to slice triangle meshes along arbitrary trajectories encompassing both straight and freely curved paths while preserving efficiency and accuracy. The effectiveness of the proposed approach is demonstrated through experimental results showing various examples of mesh slicing.

1. Introduction

Polygonal meshes are widely used in computer graphics and geometric modeling for their simplicity and effectiveness in representing three-dimensional shapes. Over the past few decades, various techniques [1,2,3,4] have been developed for polygon mesh processing (PMP), including remeshing, smoothing, decimation, deformation, and more. Mesh slicing refers to dividing a mesh into multiple submeshes, and numerous algorithms have been developed for this purpose; however, most methods rely on user-specified lines for slicing polygonal meshes, with less focus on using freeform curves. In this paper, we propose an effective method for slicing solid-type triangle meshes using a freeform curve, assuming that the resulting sliced submeshes are also solid-type.

Slicing a triangle mesh with a single line is a relatively straightforward process, essentially reduced to solving the intersection problem between triangle edges and the slicing plane formed by extruding the line in the viewing direction (refer to Figure 1a,b). By substituting the parametric line equations $l\left(t\right)=\left(x\right(t),y(t),z(t\left)\right)$ of triangle edges into the implicit plane equation $ax+by+cz+d=0$, the intersection points can be easily computed. Subsequently, the triangle mesh is cut by the polylines connecting these intersection points, resulting in multiple submeshes with open boundaries (holes). Each boundary is then filled with the cross-section formed by hole-filling or a simple triangulation method. Figure 1b shows the result of slicing the Bunny model using a line, with both resulting submeshes being solid. While plane-based mesh slicing is straightforward and simple, it can lead to undesired results due to the infinite extension of the slicing plane boundary. To address this limitation, Lee et al. [5] proposed a method using a bounded plane to selectively slice only the desired portion. However, even when using a bounded plane, slicing into submeshes with complex shapes requires significant user intervention.

Mesh slicing with a freeform curve offers users greater flexibility and potential; however, existing methods [6,7,8] take a simple approach to discretizing a freeform curve into a set of line segments and applying a line-based method, as shown in Figure 2b. This approach inevitably leads to approximation errors and generates an excessive number of unnecessary boundary edges, as shown in Figure 2d. In this paper, we propose a new method for mesh slicing using a freeform curve without discretizing it into line segments. We directly compute the intersection points between a freeform curve and triangles (see Figure 2a) and cut the triangles by connecting these intersection points, resulting in optimal boundary edges (see Figure 2c).

Our method starts with a two-dimensional curve $C\left(u\right)$ and extends it to a ruled surface $R(u,v)=C\left(u\right)+v\overrightarrow{r}$ by linearly extruding it in the user’s viewing direction $\overrightarrow{r}$ (see Figure 1c,d). Then, we compute the intersection points between edges of triangles and the ruled surface, which is reduced to a Line–Surface Intersection (LSI) problem. In general, for a parametric surface $S(u,v)=\left(x_1(u,v),y_1(u,v),z_1(u,v)\right)$ and a line $l\left(t\right)=\left(x_2\left(t\right),y_2\left(t\right),z_2\left(t\right)\right)$, the LSI problem can be formulated as follows:

$$\left\{\begin{array}{ccc}{x}_1(u,v)& =& x_2\left(t\right)\\ y_1(u,v)& =& y_2\left(t\right)\\ z_1(u,v)& =& z_2\left(t\right)\end{array}.\right.$$

(1)

By eliminating the linear variable t of $l\left(t\right)$, we can obtain a system of nonlinear equations with two unknowns u and v, as follows:

$$\left\{\begin{array}{ccc}f(u,v)& =& 0\\ g(u,v)& =& 0\end{array}.\right.$$

(2)

This system can be efficiently solved by guessing an initial solution $(u_0,v_0)$ through iterative subdivision of the parametric domain, then applying the Newton–Raphson method [9]. However, this approach may incur significant computational costs when dealing with a large number of lines, i.e., edges of all triangles.

In this paper, we confine the LSI problem to a ruled surface $R(u,v)$ and propose an efficient algorithm for calculating the intersection points with a line $l\left(t\right)$. Our method decomposes the LSI problem of a ruled surface into two subproblems: Plane–Curve Intersection (PCI) followed by Line–Line Intersection (LLI). First, an intermediate intersection point $C\left(u^{*}\right)$ is determined by solving the PCI problem. Subsequently, the final intersection point $R(u^{*},v^{*})$ is computed by solving the LLI problem. Similar to the case with the line, the triangle mesh is cut by the polylines connecting intersection points. When using a curve, the cross-section is not planar anymore, and should be a subregion of the ruled surface $R(u,v)$. As all intersection parameters are computed within the parameter domain of $R(u,v)$, it is relatively straightforward to generate the cross-section by cutting the ruled surface. Figure 1d shows the result of slicing the Bunny model using a freeform curve. The overall process of the proposed method is illustrated in Figure 3.

Our method has several advantages, which can be summarized as follows:

• Effectiveness. The proposed method enables an effective slicing of a given triangle mesh into multiple submeshes both for straight strokes and for highly complex strokes provided by the user.
• Flexibility. Our method provides easy control over the resolution of the generated cross-sections by adjusting the number of sampling points on the ruled surface.
• Efficiency and robustness. The LSI problem is decomposed into two subproblems, first the PCI problem and then the LLI problem. This decomposition reduces the computational cost of calculating intersection points while simultaneously improving the robustness of the proposed method.

The remainder of this paper is organized as follows. In Section 2, we provide a brief review of previous works on surface mesh slicing. Section 3 describes the mesh slicing algorithm using a freeform curve. Various experimental results and potential applications are presented in Section 4, then we discuss the results, conclude the paper, and propose future work in Section 5.

2. Related Work

In this section, we examine previous research directly related to the contributions of this paper, particularly including mesh slicing techniques and the computation of intersections among diverse freeform models. Similar to the line-based approach mentioned in Section 1, most methods involve the step of creating a cutting plane to slice a 3D object. Chu et al. [10] introduced a method for creating a cutting plane to slice large models that exceed the general 3D printer’s printable size. They used a user-specified line to define the cutting plane, allowing the user to partition the model for 3D printing. Kang and Kim [11] explored the process of cutting a 3D garment model into patches. Their method overcomes the limitations of slicing using only a line by allowing for user-defined cutting lines composed of multiple line segments. If the cutting line is a single segment, a traditional slicing plane is generated; however, for complex lines, users must connect them, creating a projected 2D polygon on the screen. Subsequently, triangles are intersected with either a plane or a polygon to define the patches. This approach is limited to cutting only the front side of the mesh, whereas our method supports completely cutting the mesh into submeshes. Owada et al. [12] presented a method where user strokes are converted into straight lines approximating them. A slicing plane is then created by extruding these lines in the viewing direction. These methods have the common limitation of approximating the user’s strokes using a series of line segments, resulting in reduced slicing freedom and lower precision. To overcome this limitation, Mitani [6] proposed a slicing algorithm in which the user defines a cutting path with freehand strokes on the screen. This method performs intersection checks in 2D by projecting the polygonal mesh onto the screen, and prioritizes simplicity and robustness over precision by employing techniques such as node-snapping, vertex-to-line movement, and path simplification. While this approach offers ease of use and prevents degenerate triangles that could cause computational errors, the significant modifications to the stroke can compromise the precision of the slicing boundary.

Owada et al. [8] presented a slicing algorithm similar to our approach, featuring an interactive interface for volumetric mesh slicing visualized with a polygonal mesh to reveal the inner texture. A user-drawn freeform stroke is sampled into line segments and swept in a direction orthogonal to the screen, generating a curved discrete plane that slices the volumetric mesh through a constructive solid geometry (CSG) operation. This method then parameterizes the cross-section to visualize the inner texture of the polygonal mesh. Although this addresses the freedom of stroke issue, the issue of discretizing the freeform stroke remains.

Several methods [13,14,15] have explored virtual cutting tools for mesh manipulation. Khan et al. [13] presented a method for cutting polygonal meshes. Their approach removes faces that intersect with the slicing plane defined by a virtual scalpel blade. Subsequently, the boundary is regenerated by connecting the intersection points to the boundaries of the remaining faces. For generating a cross-section, they refined an initial triangulation through a multi-level refinement process. Kamarianakis et al. [14] addressed potential mesh subdivision issues during virtual scalpel interactions. When an intersection with a tetrahedral polygon is detected, the intersecting vertex is projected onto the scalpel’s path to prevent unnecessary subdivision. The mesh is subsequently separated along this projected path. Caligiana et al. [15] employed a haptic device (Phantom) to facilitate interaction with a virtual surgical tool for mesh slicing, where intersecting triangles are subdivided using a longest-edge refinement strategy. While these virtual tool approaches offer real-time interaction and may be well-suited for specific applications, they could require additional hardware or introduce complexities in tool manipulation. In contrast, our stroke-based approach prioritizes user intuition and ease of use while maintaining efficient mesh slicing functionality.

Mesh slicing algorithms can be categorized based on the intersection types involved: discrete-discrete (plane–plane, plane–line, line–line), discrete-freeform (plane–surface, plane–curve, line–surface, line–curve), and freeform-freeform (surface–surface, curve–surface, curve–curve). Our method can be classified as a discrete-freeform case, wherein a triangle intersects with a ruled surface. Lu et al. [16] discretized the surface into square patches and analyzed the signs of each patch’s corner vertices by substituting the parameters into the implicit plane equation. If opposite signs are detected on an edge, this indicates that an intersection point lies on that edge. Sharma et al. [17] proposed a tracing method for finding the intersection between a parametric Bézier triangular surface and a plane, specifically focusing on triangular domains. Their method utilizes the parametric equations of the Bézier surface and the plane equation to efficiently compute their intersection points. The tracing method starts from an initial intersection point and iteratively follows the intersection curve until it reaches a boundary or meets a predefined stopping condition.

Li et al. [18] introduced a method for intersecting a ruled surface with a plane, similar to our approach. Their method involves discretizing the ruled surface by sampling the directrix curve and generating line segments along the generator direction to find intersections with the plane; however, unlike our approach, this suffers from the drawback of discretizing the ruled surface. Beer et al. [19] explored iterative approaches to solving the Line-Surface Intersection (LSI) problem, which entails finding the closest point on the surface to a given point on the line, then presented alternative solutions to the LSI. Martin et al. [20] proposed a numerical approach to the LSI problem, framing it as a ray tracing problem. A ray is considered as the intersection line between two planes with normals perpendicular to the ray’s direction and passing through the ray’s origin. By substituting the surface point into the implicit equations of these two planes, the system of equations is solved using Newton’s method. Busé et al. [21] introduced a matrix-based implicit representation for Bézier patches (MRep) to solve the LSI problem, while Shen et al. [22] tackled degenerate cases in the general MRep method, resulting in higher accuracy.

3. Mesh Slicing Using a Freeform Curve

3.1. Ruled Surface Generation

This section outlines the process of generating a ruled surface from the user’s freehand stroke on the screen. A ruled surface, which is a specific kind of freeform surface, is considered akin to a curved plane due to its planarity (having zero Gaussian curvature). Figure 4 illustrates an example of a user’s freehand stroke (depicted in black) on the screen. Points are sampled at regular intervals along the stroke. For each sampled point ${\mathbf{s}}_i$, a ray $r\left(t\right)$ is cast in the viewing direction to calculate the intersection points ${\mathbf{p}}_i$ and ${\mathbf{q}}_i$ with the bounding planes ${\pi }_1$ and ${\pi }_2$ of a triangle mesh, as demonstrated in Figure 4. A cubic B-spline curve $C\left(u\right)$ is then constructed to approximate the intersection points ${\mathbf{p}}_i$ on ${\pi }_1$ within an error bound $ϵ$. Subsequently, the parametric ruled surface is defined as

$$R(u,v)=C\left(u\right)+v\overrightarrow{r},\mathrm{for}0\le u,v\le 1,$$

(3)

where $\overrightarrow{r}={\mathbf{q}}_i-{\mathbf{p}}_i$ represents the constant directional vector of the generator of $R(u,v)$. Figure 4 shows the ruled surface (in red) generated using the proposed method. While a ruled surface exhibits planar characteristics, it cannot be represented by an implicit function such as a plane; therefore, slicing a mesh with a ruled surface requires more computational steps compared to using a plane. Our technique requires the user’s stroke to intersect the mesh fully, accommodating both freeform curves and conventional straight lines.

3.2. Ruled Slicing

When the ruled surface $R(u,v)$ has been generated from the user’s freehand stroke, the next step involves computing the intersection lines between the ruled surface and the triangles of a mesh to slice the mesh effectively. We refer to this process as ruled slicing. Because only a subset of the mesh’s triangles intersect with the ruled surface, identifying these candidate triangles is crucial for improving computational efficiency. To facilitate this, we tessellate the ruled surface into triangles and construct its Bounding Volume Hierarchy (BVH), then carry out intersection tests between the mesh triangles and the constructed BVH. For our study, we employed a straightforward Axis-Aligned Bounding Box (AABB) as the BVH type. Figure 5 illustrates the triangles (highlighted in yellow) of the Bunny model that intersect with the ruled surface, identified using the BVH of $R(u,v)$.

Let $T=\{{\Delta }_1,{\Delta }_2,\cdots ,{\Delta }_n\}$ represent a set of candidate triangles. For each triangle ${\Delta }_i$, we need to compute the exact intersection segment. We denote $l_j\left(t\right)$, where $j=1,2,3$, as the parametric equations for the edges of triangle ${\Delta }_i$. We then calculate the intersection points of $l_j\left(t\right)$ with $R(u,v)$. This task is commonly referred to as a Line–Surface Intersection (LSI) problem, for which various methods [20,21,23] have been devised to address it efficiently. In this paper, we focus on the LSI problem of a ruled surface with a line, as depicted in Figure 6a. Our LSI problem is decomposed into two simpler subproblems: (1) Plane–Curve Intersection (PCI) and (2) Line–Line Intersection (LLI), as follows:

• PCI problem (Figure 6b)
  • Construct a plane $\pi$ that contains $l\left(t\right)$ and the generator vector $\overrightarrow{r}$.
  • Determine the intersection point $C\left(u^{*}\right)$ between $C\left(u\right)$ and $\pi$.
• LLI problem (Figure 6c)
  • Generate the ruling line $m\left(v\right)$ originating from $C\left(u^{*}\right)$ in the direction of $\overrightarrow{r}$.
  • Calculate the intersection point $R(u^{*},v^{*})$ between ruling line $m\left(v\right)$ and line $l\left(t\right)$.

In Figure 6, let $l\left(t\right)=\mathbf{p}+t\overrightarrow{d}$ denote the line segment of a triangle edge. A plane $\pi$ passing through $\mathbf{p}$ with normal vector $\overrightarrow{n}=\overrightarrow{d}\times \overrightarrow{r}$ is intersected with $C\left(u\right)$ as shown in Figure 6b. The corresponding intersection point $C\left(u^{*}\right)$ can be found by solving the following equation:

$$<C\left(u\right)-\mathbf{p},\overrightarrow{n}>=0,$$

(4)

where $<·,·>$ represents an inner product. Equation (4) identifies the point lying simultaneously on the curve $C\left(u\right)$ and the plane $\pi$. Because Equation (4) involves only one unknown u, the corresponding intersection point can be computed more efficiently than the general LSI problem in Equation (2). Starting from the intersection point $C\left(u^{*}\right)$, we create a line $m\left(v\right)=C\left(u^{*}\right)+v\overrightarrow{r}$. As $m\left(v\right)$ has the direction of $\overrightarrow{r}$, it also lies on the plane $\pi$; thus, the final intersection point $R(u^{*},v^{*})$ can be found by solving a simple LLI problem between $l\left(t\right)$ and $m\left(v\right)$, formulated as the following linear system:

$$\left[\begin{array}{cc}\overrightarrow{r}& \overrightarrow{d}\end{array}\right]\left[\begin{array}{c}v\\ t\end{array}\right]=\mathbf{p}-C\left(u^{*}\right).$$

(5)

Consequently, our method decomposes Equation (2) with two unknowns u and v into two simpler ones, that is, Equations (4) and (5), based on geometric interpretation. These simpler equations can be easily solved sequentially, enabling efficient and robust computation of intersection points. Algorithm 1 shows how to compute the intersection lines between a triangle mesh and a ruled surface using the proposed method.

Algorithm1: Intersection of candidate triangles with a ruled surface

Require: $T=\left\{{\Delta }_i\right\}$: a set of candidate triangles, $R(u,v)=C\left(u\right)+v\overrightarrow{r}$: a ruled surface 1: for  ${\Delta }_i$  in  T  do 2:     for $e_j$ in ${\Delta }_i$ do 3:         $l_j\left(t\right)\leftarrow$ parametric line of $e_j$ 4:         Create plane $\pi \leftarrow$ containing $l_j\left(t\right)$ and generator vector $\overrightarrow{r}$ 5:         Compute intersection point $C\left(u^{*}\right)$ between $\pi$ and $C\left(u\right)$ 6:         $m\left(v\right)\leftarrow$ parametric line starting from $C\left(u^{*}\right)$ 7:         Compute intersection point $R(u^{*},v^{*})$ between $l_j\left(t\right)$ and $m\left(v\right)$ 8:     end for 9: end for

The next step is to create polylines to subdivide the mesh into several submeshes by connecting the previously computed intersection points. To achieve this, we categorize the potential intersections of a triangle with a ruled surface into two types: (1) single intersections and (2) double intersections, as depicted in Figure 7. It is necessary to prune the single intersections (Figure 7a) to remove the degenerate cut segments. When the degenerate segments have been removed, the remaining cut segments are connected to form a polyline. This polyline consists of the points on the edges, as the cut segments are produced by the intersection points with the ruled surface on the triangle’s edges. Every triangle that includes a cut segment is refined and split into two or three smaller ones, creating submeshes (see Figure 8). As shown in Figure 8b, these newly created submeshes have open boundaries (holes). To make sure the submeshes are solid, cross-sections need to be generated to fill these holes, which will be explained in the next subsection.

3.3. Cross-Section Creation and Merging

The ruled slicing method described above can result in multiple submeshes with open boundaries (holes). While conventional hole-filling techniques [24,25,26,27] can be utilized to fill these holes, the resulting cross-sections may not align perfectly with those of the ruled surface. To address this issue and ensure that the cross-sections precisely match the ruled surface, it is imperative to generate the cross-section patch directly from the ruled surface. In our method, all intersection points have corresponding parameters $(u^{*},v^{*})$ in the parametric domain $\Omega =[0,1]\times [0,1]$ of a ruled surface. By connecting these points we can easily create a polyline in $\Omega$, as illustrated in Figure 9b. We uniformly sample points in $\Omega$ and create a subpatch $\varphi (u,v)$ bounded by the polyline using the constrained Delaunay triangulation [28]. Figure 10a–d shows examples of the generated subpatch $\varphi (u,v)$ with varying numbers of sampling points. The corresponding subpatch $X(u,v)$ of $R(u,v)$ can be defined as $X(u,v)=R·\varphi (u,v)$ and is utilized as the cross-section to fill the open boundary of a submesh, as shown in Figure 11.

After a cross-section is created for each polyline in $\Omega$, a merging step is necessary to ensure that the submeshes are solid. Merging the cross-section and submesh directly may lead to inconsistencies in orientation. To address this, we compare the boundary direction of the cross-section with that of the submesh. If both boundaries have the same direction, this indicates that the orientation of the cross-section is inconsistent with the submesh and must be flipped. If not, we simply merge them to make the submesh solid. Algorithm 2 illustrates the overall process of the proposed technique.

Algorithm 2: Mesh slicing algorithm

Require: Target mesh M, freeform curve $C\left(u\right)$, and generator vector $\overrightarrow{r}$ 1: $R(u,v)\leftarrow$ ruled surface generated by $C\left(u\right)$ and $\overrightarrow{r}$ 2: $T=\left\{{\Delta }_i\right\}\leftarrow$ set of candidate triangles of M intersected with BVH of $R(u,v)$ 3: for ${\Delta }_i$  in   T do 4:     Compute intersection segment $s_i$ of ${\Delta }_i$ with $R(u,v)$ (Algorithm 1) 5: end for 6: $L=\left\{l_i\right\}\leftarrow$ set of polylines on M generated by connecting intersection segments 7: $\widehat{L}=\left\{{\widehat{l}}_i\right\}\leftarrow$ set of polylines in the parametric domain of $R(u,v)$ 8: Subdivide $M=M_1\cup M_2\cup \cdots \cup M_n$ using $l_i$ 9: Create cross sections $X=\left\{X_i\right\}$ by cutting $R(u,v)$ with ${\widehat{l}}_i$ 10: for $M_i$  in M do 11:     for $B_j$ in boundaries of $M_i$ do 12:         Find the cross-section $X_k$ that matches with $B_j$ 13:         if normal of $X_k$ is inconsistent with $B_j$ then 14:            Flip normal of $X_k$ 15:         end if 16:         Fill $B_j$ by merging $X_k$ with $B_j$ 17:     end for 18: end for

4. Experimental Results

The proposed technique was implemented using the C++ language on a PC equipped with an Intel i7-9700F CPU running at 3.00 GHz, 40.0 GB of memory and an NVIDIA GeForce RTX 2060 graphics card. Mesh slicing experiments using a ruled surface were conducted with various 3D mesh models exhibiting different geometric characteristics.

Table 1. Statistics of the models.

Models	Box	Knot	Bunny	Camel	Armadillo	Pumpkin Creature
# of vertices	1538	9450	8327	9770	43,243	58,657
# of faces	3027	18,900	16,650	19,536	86,462	117,310
Feature	Sharp edges	Genus > 1	Complex	Complex	Complex	Complex
			Smooth surface	Smooth surface	High noise	High noise

lists the geometric details of the models used in the experiment.

4.1. Mesh Slicing Results

Our method offers users two types of strokes: a straight line and a freeform curve. For a straight line, the user defines the start and end points of the cutting line by mouse clicking, dragging, and releasing. Subsequently, a ruled surface is generated from the B-spline curve that passes through two end points. It is important to note that although the generated ruled surface is essentially a plane, it is confined by the two end points; therefore, our method enables precise slicing of a desired region as shown in Figure 12. Various results of mesh slicing using straight lines are illustrated in Figure 13, where the blue dashed lines denote the user’s strokes and the red solid lines correspond to the cutting polylines on the meshes. Note that the blue line may intersect with the mesh multiple times, resulting in multiple submeshes. Figure 14 shows the results of mesh slicing using freeform curves, where the curves intersect with the target meshes once, resulting in two submeshes, respectively. Our method allows a freeform curve to intersect with the target mesh multiple times, generating multiple submeshes, as shown in Figure 15 (refer to the attached video for a real-time demonstration (https://youtu.be/UqQaKZTj_Zo (accessed on 23 April 2024) or see the Video S1).

The user’s stroke is approximated by a freeform curve, then the target mesh is sliced by the ruled surface generated from the freeform curve. However, certain users may prefer more sophisticated control over the slicing result by editing the generated freeform curve. To accommodate this, our method provides the flexibility for users to modify the slicing curve. Figure 16 illustrates an example of manual editing of the generated freeform curve. As the user draws the slicing trajectory on the screen, the initial approximation curve is generated. By adjusting the control points (the green circle), the curve is modified as the user intends.

4.2. Performance Analysis

Table 2. Elapsed time (in ms) of mesh slicing algorithm.

Models	Box	Knot	Bunny	Camel	Armadillo	Pumpkin Creature
Ruled surface creation	0	0	0	0	0	0
# of Candidate Faces	387	609	457	578	1170	3050
Intersection computation	73	80	88	159	230	499
Submesh creation	21	84	32	133	530	1183
Cross-section creation	2	2	2	4	4	12
Normal correction	1	3	1	3	7	14
Merging cross-section	13	41	19	87	298	506
Total	110	210	142	386	1069	2214

lists the elapsed times for slicing various meshes into submeshes, corresponding to each step of the slicing process depicted in Figure 13, Figure 14 and Figure 15. The elapsed time for each step is then summed to determine the total elapsed time. Regardless of the diverse features among the models, the majority of the elapsed time is measured on the intersection computation, submesh creation, and merging steps. Even in the case of models such as the Armadillo and Pumpkin Creature, which have significantly larger numbers of vertices and faces, most experiments yielded satisfactory results within approximately 1 to 2 s. This observation suggests that the elapsed time is primarily influenced by the number of candidate faces listed in the third row, rather than the complexity of the model.

To demonstrate its computational efficiency, we compared the elapsed times of our method (decomposition into PCI and LLI) with a general LSI computation in Equation (2). We performed mesh slicing 100 times on various models and computed the average elapsed time for each method. Figure 17 shows the comparative results of the two methods. The blue line corresponds to our method and the orange line to general LSI computation. The elapsed time of our method is significantly less than that of the general LSI method. Moreover, the difference between the two methods becomes larger as the number of candidate faces increases. This confirms that our method is much faster and more efficient than the general LSI method.

4.3. Comparison to Existing Methods

To demonstrate the effectiveness of our method for generating cross-sections, we compared our method with the state-of-the-art surface fairing technique from [24], which fills holes with a minimal surface while keeping its boundary fixed. For the user’s identical strokes, Figure 18 shows the cross-sections generated by the minimal surface and our method, respectively. As shown in Figure 18a, the hole-filling method based on the surface fairing is not suitable for the desired cross-section, whereas our method produces the cross-section by directly cutting the ruled surface. Therefore, as shown in Figure 18b, it exactly matches the slicing cross-section. This effectiveness highlights the advantage of our method, which allows for the generation of accurate cross-sections with arbitrary boundary configurations.

We additionally compared the mesh slicing results by discretizing the freeform curve into a set of line segments and directly computing the intersection points between the curve and the triangular mesh. Figure 19 demonstrates the effectiveness of our method. Figure 19b,c shows excessive complexity and unnecessary refined triangles due to the refinement of the triangles at the endpoints of the line segments. On the other hand, our method refines the triangles only at the intersection points while avoiding unnecessary refinements, and produces concise and optimal triangles, as shown in Figure 19a.

To quantitatively compare the quality of the slicing results generated using our method and the discretization method, we sliced each model in Table 1 using an identical freeform curve.

Table 3. Comparison of the number of intersection points and degenerate triangles between our method and the discretization method (triangles with an area less than $ϵ=\left({10}^{-3}\right)$ are classified as degenerate triangles).

Models	# of Intersection Points			# of Degenerate Faces
	Our	Discretization (30 Samples)	Discretization (100 Samples)	Our	Discretization (30 Samples)	Discretization (100 Samples)
Box	207	343	661	0	8	12
Knot	447	583	911	0	12	18
Bunny	365	470	715	4	21	38
Camel	373	494	795	0	2	16
Armadillo	859	973	1238	5	13	10
Pumpkin Creature	1182	1320	1683	33	54	60

lists the number of intersection points (vertices) and degenerate triangles at the boundaries of the cross-sections generated by our method and the discretization method with different numbers of sample points. The discretization method generates more intersection points and degenerate triangles as the number of sample points increases, resulting in higher geometric complexity of the cross-sections, as shown in Figure 19b,c. Conversely, our method produces fewer intersection points and degenerate triangles, resulting in more effective and robust slicing results.

4.4. Application

Our method can be easily applied in various applications, such as custom 3D puzzle generation. As an example, we sliced the Bunny model into eight pieces, as shown in Figure 20. Figure 20a shows the results of slicing the Bunny model, while Figure 20b shows the 3D printed puzzle pieces using a fused deposition modeling (FDM) method, where the melted filament is stacked layer-by-layer to form the 3D model. While this process can introduce slight errors, the resulting pieces still provide satisfying results. When assembled (Figure 20c), these pieces perfectly reconstruct the original Bunny model. Expanding this application to the manufacturing industry could facilitate the creation of even more intricate and highly sophisticated 3D puzzles.

5. Conclusions and Discussion

This paper introduces an efficient method for slicing a triangle mesh using a freeform curve. The method utilizes a ruled surface generated based on the user’s stroke, and has been successfully tested on various triangle meshes with different characteristics. The user interaction involves drawing a stroke on the screen, which is then approximated by a B-spline curve. Subsequently, the curve is extruded in the viewing direction, creating a ruled surface. To achieve efficient slicing, we leverage the BVH of the ruled surface to identify candidate faces for potential intersections. When the candidate faces have been identified, we compute the exact intersection points between the ruled surface and these faces. This process is efficiently performed by decomposing the LSI problem into PCI and LLI problems. This decomposition allows for efficient computation of the intersection parameters u and v, improving both accuracy and robustness. Intersection points are then connected to form polylines, effectively cutting the mesh into multiple submeshes. To ensure the solidity of the submeshes, cross-sections are generated by trimming the ruled surface along the polylines, then merged with the corresponding submeshes. We have demonstrated the effectiveness of the proposed method by comparing it with existing methods and showing various examples of mesh slicing.

Our approach offers several advantages. First, our method enables users to slice triangle meshes along arbitrary trajectories, encompassing both straight and freely curved paths by editing the freeform curves. Second, unlike existing methods that limit mesh slicing to two pieces per stroke, our approach allows for slicing the mesh into multiple submeshes regardless of the mesh topology. The decomposition of LSI into PCI and LLI further improves the efficiency and robustness of the method by enabling separate computations of intersection parameters. Finally, our cross-sections can be easily generated from the ruled surface, while existing methods rely on a hole-filling method.

Despite the numerous advantages mentioned above, the current implementation is not able to handle volumetric meshes. This poses a significant challenge, as volume elements such as tetrahedra involve a considerably greater number of intersection points compared to triangles, leading to an exponential increase in computational cost. In future work, we aim to enhance the efficiency of our technique by incorporating GPU-based parallel programming, enabling real-time slicing of volumetric meshes.