{'fraction_non_alphanumeric': 0.04353941992095921, 'fraction_numerical': 0.010717395672851498, 'mean_word_length': 4.470868449981678, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quadrilateral mesh fitting that preserves sharp features based on multi-normals for Laplacian energy

Because the cost of performance testing using actual products is expensive, manufacturers use lower-cost computer-aided design simulations for this function. In this paper, we propose using hexahedral meshes, which are more accurate than tetrahedral meshes, for finite element analysis. We propose automatic hexahedral mesh generation with sharp features to precisely represent the corresponding features of a target shape. Our hexahedral mesh is generated using a voxel-based algorithm. In our previous works, we fit the surface of the voxels to the target surface using Laplacian energy minimization. We used normal vectors in the fitting to preserve sharp features. However, this method could not represent concave sharp features precisely. In this proposal, we improve our previous Laplacian energy minimization by adding a term that depends on multi-normal vectors instead of using normal vectors. Furthermore, we accentuate a convex/concave surface subset to represent concave sharp features.


Introduction
In manufacturing, the cost of computer simulations is lower than testing actual prototypes. Thus, most manufacturers run simulations, which require volume meshes. Up until a decade ago, the simulation process started from surface meshes that were made using computer aided design (CAD) software. However, there were differences in the shape between the actual products and the CAD model, a result of manufacturing factors such as springback in production presses. Even if manufacturers used metal dies with the same shapes as in the CAD models, the parts obtained from the processes such as press working do not have the same shape as the CAD model. Thus, the actual products are different from the CAD model. For realistic simulations, the CAD model must be identical to the products. Today, the simulation process starts from point clouds scanned from the actual products. This process is called reverse engineering.
Tetrahedral/hexahedral meshes generated from such point clouds directly affect the results in finite element method (FEM) analysis. Hexahedral meshes are important because they are superior to tetrahedral meshes (see Figure 1(a)) in terms of accurate analysis. Thus, in this paper, we use hexa-hedral volume meshes (see Figure 1(b)) whose elements are only hexahedral cells (called all-hexahedral meshes) and consider their surface.
In the structural analysis between two objects, the peak stress occurs near or around the contact regions. Such regions are often sharp features. A sharp feature is typically a cusp part (such as an edge or point) of an object. Thus, to obtain accurate simulation results, the surface mesh must represent sharp features.
In this paper, we consider a voxel-based hexahedral mesh generation algorithm [1,2]. In addition, the volume mesh for the FEM must satisfy the constraint that all Jacobians are positive. The Jacobian is a triple scalar product • c , where , and are vectors (edges) adjacent to the corner vertex of a cell. Our ultimate goal is automatic hexahedral mesh generation without negative Jacobians. In this paper, we discuss the quadrilateral surface of a hexahedral mesh (The algorithm we investigated in previous studies is voxelbased [1,2]). Thus, our inputs are the target surface mesh and the quadrilateral mesh that is the surface of the voxel mesh. Generically, we can classify the methods of boundaryfitted hexahedral meshing as voxel-based [3,4], advancing front [5][6][7], whisker waving [8], cycle elimination [9], medial axis-based [10], and sweep/mapped methods [11,12], although other types exist. Hexahedral mesh generation algorithms can be fully or semi-automatic, but there is no scheme that guarantees all Jacobians will be positive. On the other hand, there is a scheme that guarantees that positive Jacobians does exist for tetrahedral meshes. Before considering how to achieve positive Jacobians, we generate quadrilateral surfaces of the all-hexahedral meshes that represent the target surfaces. In this paper, we propose an automatic fitting algorithm with sharp features based on previous works [1,2,13].

Previous hexahedral meshing
First, we summarize the previous hexahedral mesh generation algorithm [1,2,13]. The underlying algorithm can be broken down as follows.
3. Extract the boundary surface of voxels. In Step 4 above, we fit the boundary surface of voxels to the target surface mesh. We call this the fitting part. We proposed a fitting algorithm that did not represent sharp features (see Figure 2(c)) [1,2]. Thus, we proposed a modified fitting algorithm [13]. The modified algorithm represents convex sharp features (see Figure 2(d)). However, it could not represent concave sharp features. Therefore, we are now proposing a new fitting algorithm based on multinormal vectors and convex/concave accentuation.

Fitting algorithm
In this section, we explain the new fitting algorithm. Let is the user-defined maximum iteration number ( 30 in this paper). The minimizing of the quadratic energy function is as follows: Surface Laplacian smoothing is used to prevent vertices from becoming congested near the sharp features of the target surface. Ordinary Laplacian smoothing, however, erases sharp features. Thus, we use feature-preserving Laplacian smoothing instead of ordinary Laplacian smoothing.
The first term in the above minimization is the difference between successive Laplacians. The second term is the difference between and . The third term is the difference between and . The fourth term is the non-matching rate between the multi-normal vectors n , 1,2,3 ⋯ and n , 1,2,3 ⋯ . We describe multi-normal vectors and the non-matching rate in detail in Section 4. In this term, the multi-normal vector n , 1,2,3, ⋯is a set of linear formulas of (not unit vectors). In a previous study, we used a similar minimization (Eq. (2)) [13].
The corresponding fourth term of Eq. (2) is a quadratic formula (not linear) that represents the non-matching rate between normal vectors and similarly. However, the value of the fourth term of Eq. (2) does not change by using instead of . Therefore, let a normal T Figure 3. Bolt with reverse part.
vector be a minimizer of the corresponding fourth term of Eq. (2). Then, is also a minimizer, because the corresponding fourth term is quadratic. Figure 3 shows the resulting mesh with a reverse part. Thus, we set to be very small. In this case, the resulting mesh does not represent convex/concave sharp features (see Figure 5(c)). Figures 5(a) and 5(b) show the target surface and voxels of the bolt, respectively. Thus, we define a new fourth term of Eq. (1) as a linear formula.
In one approach [16], is the closest point to on the target surface mesh. In others [1,2], however, is the closest vertex on the target surface mesh. These two definitions of are distinctly different. We increased the number of vertices on the target surface mesh by upsampling [1,2]. We chose subdividing triangles for upsampling. As in the loop subdividing method, we subdivided each triangle on the target surface into four triangles. We applied this subdivision five times. Let , j 0,1,2, ⋯ be vertices (including up-sampling) on the target surface. Let be the unit normal vector at on the target surface. The definition of in this paper is: This definition is based on a non-matching rate between and . In this case, 0.8.
The old definition of is [1,2]: Another old definition of is [13]: The normal vector of a candidate vertex is closer to , and the vertex tends to be chosen as . The new fitting algorithm consists of two parts. In the first part, we apply the fitting algorithm with Eq. (1). We set 0.0 and 2. In the second part, we apply the algorithm with Eq. (1) with 0.01, resetting to 0, and 30 0 30 .

Fitting algorithm that represents concave sharp features
In this section, we explain the multi-normal vector and convex/concave accentuation in the new fitting algorithm. First, we explain the non-matching rate and corresponding point of based on a multi-normal vector. In a previous study [13], we defined and as averages of normal vectors of triangles at step and step +1, respectively. Here, we realize that even if has the same direction as , the normal vector of each triangle (face) connected to may not be parallel to the normal vector of each triangle (face) connected to . A face of the boundary surface of an all-hexahedral mesh is quadrilateral. We consider a quadrilateral face that has four triangles and four normal vectors. Therefore, we set the multi-normal vector of as the normal vectors of such triangles to . We combine several parallel vectors of this multi-normal vector into one vector and apply this operation repeatedly. As a result, this multi-normal vector has no subset of parallel normal vectors. For example, if all triangles adjacent to are on a plane, then the multi-normal vector of has only one element that is a normal vector of the plane.
We set , 1, 2, 3 ⋯ as this contracted multinormal vector. We apply this process similarly for . We set the multi-normal vector , 1, 2, 3, ⋯ as normal vectors of the triangles including similarly. Let , be the numbers of normal vectors of , after the above process.

Convex/concave accentuation
In this subsection, we add a new step to Algorithm 1 of Section 3 at the second part (considering the normal vector) to represent concave sharp features. In concrete terms, before the determination of in step 1 of Algorithm 1, we add convex/concave accentuation for the subset of the boundary surface of the all-hexahedral mesh.
To represent sharp features, that connects sharp boundary edges corresponding to sharp features must be on the corresponding sharp edges. Therefore, it is important that the corresponding is on the sharp edges. Therefore, before the minimization (decision of ), we accentuate the convex/concave subset of the boundary surface of the allhexahedral mesh. Figure 4 shows the convex/concave accentuation. The black line denotes the target surface. The red line denotes the boundary surface of the all-hexahedral mesh. In this case, the red vertices are not on the convex and concave corners of the black line, and so the boundary surface does not represent sharp features.
To represent sharp features, we first calculate the Laplacian vector at of the boundary surface. Let be a vector that is parallel to the average of , 1, 2, 3, ⋯ , whose norm is equal to the inner product between the average of the multi-normal vector and the Laplacian vector. If the inner product is negative, the direction of is opposite to the average of , 1, 2, 3, ⋯ , . Let be the length of an edge of an initial voxel, and be a userdefined coefficient (in this paper, we set this to 0.5).
Our convex/concave accentuation is is not a multiple of 3, we do not apply accentuation. After the first part that does not depend on a normal vector, ‖ ‖ 1, 2, 3 ⋯ are almost 0, because the third term of in Eq. (1) becomes almost 0 .
Thus, in the second part, without convex/concave accentuation, does not change for all because the inside term of minimizing on the right side of Eq. (3) is always almost 0 at the same . Therefore, we use convex/concave accentuation to separate from . After this accentuation, the probability that is on a corner (sharp feature) increases.

Matching rate between multi-normals
In this section, we explain the matching rate between multi-normal vectors , 1, 2, 3, ⋯ , and , , t 1, 2, 3, ⋯ , . In order to do this, we calculate all the inner products between multi-normal vectors , 1, 2, 3, ⋯ , and , t 1, 2, 3, ⋯ , (See Table 1). The range of the inner product is [-1, 1], because and are unit vectors. First, we obtain the maximums of each row and each column. We define ∑ • , as the sum of the maximums (bottom right cell of Table 1). In Table 1, we show the matching. The Red/Green cells are the maximum cells of the row/column. The Blue cells are the maximum cells of both the row and column. The bottom right cell shows the total of the row and column maximums.
We use this value as the matching rate between , 1, 2, 3, ⋯ , and , t 1, 2, 3, ⋯ , . Let be the number of rows and columns in

Fitting algorithm based on multi-normal vector
In this section, we explain Eq. (1) and Eq. (3) in detail. In Eq. (3), we use a scaled matching rate between multi-normal vectors and . The definition of in this paper reflects the details of the target surface.
Next, we explain the fourth term of Eq. (1).
is an element of , ,⋯ . Thus, we have a multi-normal vector and a normal vector matching table for . Let be the number of normal vectors of . There is a multi-normal vector , t 1, 2, 3, ⋯ , . In order to define the fourth term as linear formulas of , we define ∑ • , as the sum of the inner products between (linear formula) and at the colored cells in the normal vector matching table for . (At the Blue cells, we add the inner product to the sum twice).
Let be the twofold triangle area that corresponds to , and be the number of rows and columns in the normal vector matching table for . During minimizing, is constant. After the second part, we carry out post-processing to improve the quality of the resulting all-hexahedral mesh.

Result
In this section, we show the experimental results of our method. Figure 5(d) shows the boundary quadrilateral surface mesh of the all-hexahedral mesh (bolt model) calculated by our method. Figures 6(a), 6(b), 6(c), and 6(d) are the target surface, the boundary quadrilateral surface mesh of the bearing model using a previous method [13], voxels, and the all-hexahedral mesh calculated by our method for the bearing model, respectively. The concave sharp features of the bolt and bearing models are successfully represented. Similarly, our method can represent convex sharp features of the target surface mesh.
The smooth-feature model in Figure 7 has a convex sharp feature that diminishes gradually. Figures 7(a), 7(b), and 7(c) are the target surface, voxels, and result of our method for a smooth-feature model, respectively.
The computation times for our experiments were only a few seconds. Let be the number of vertices of the boundary surface of voxels, and be the number of vertices (including up-sampling) of the target surface. We solve the  . Thus, using octree, we decrease the actual computation time.

Conclusions
We have proposed a new fitting algorithm based on multinormal vectors and convex/concave accentuation in order to represent convex/concave sharp features on a target surface. Using this algorithm for automatic hexahedral mesh generation, we obtained boundary surfaces of all-hexahedral meshes with convex/concave sharp features. In future work, we intend to determine the best coefficients for our algorithm. In addition to the surface mesh, we would like to expand this research to internal vertices.