CN114611359A - Grid-parameter hybrid model modeling method and system - Google Patents

Abstract

The application discloses a mesh-parameter mixed model modeling method and a system, wherein point cloud data of an object to be measured are obtained, the point cloud data are converted into a mesh curved surface by using a mesh generation technology, mesh offset processing and boundary stitching processing are carried out on the mesh curved surface, and the mesh curved surface is converted into a closed mesh model; setting characteristic parameters of an object to be detected, establishing a parameter model, and carrying out gridding processing on the parameter model; and synthesizing a grid model and a parameter model into a mixed model based on Boolean operation, wherein the mixed model is characterized by using a grid. The system comprises a point cloud data module, a grid model module, a parameter model module and a Boolean operation module. The grid-parameter mixed model established by the method not only keeps the precision of the original measurement model, but also has the characteristic of user-defined addition, and not only can be used for operating the grid model, but also can be used for operating the parameter model, so that the precision and the efficiency of subsequent redesign are improved.

Description

A mesh-parameter mixed model modeling method and system

technical field

The present application belongs to the technical field of computer design, and in particular relates to a grid-parameter hybrid model modeling method and system.

Background technique

Computer-aided design technology is an important part of electronic information technology. It changes the content and method of product design work, subverts the traditional manual design and drawing method, and greatly improves the speed and design accuracy of product development.

The development of modeling technology has gone through the development process of 2D modeling, 3D geometric modeling, feature modeling and product integration modeling. Three-dimensional geometric modeling is divided into wireframe modeling, surface modeling and solid modeling. The surface model mainly describes the shape of three-dimensional objects according to the topological elements in vertices, edges, and patches and their mutual topological relationships. It constructs and represents three-dimensional objects through curved surfaces, and can obtain three-dimensional information on the surface of the object.

In recent years, with the great improvement of measurement accuracy, the discrete mesh surface model obtained by reverse engineering is also used in design modeling. Among them, the triangular mesh model uses a lightweight triangular patch structure to describe the topological relationship between data points, which has the advantages of fast and flexible and strong topology adaptability when expressing surface models.

Mesh surface has the advantages of high geometric accuracy, good integrity and strong topology consistency, but the amount of data increases with the increase of accuracy, which is suitable for describing complex surfaces; parametric surface has the advantages of small amount of data and high accuracy for describing simple surfaces. However, there is a large error in describing complex surfaces.

How to integrate the advantages of mesh surface and parametric surface while avoiding the disadvantages of both, and establishing a mesh-parametric hybrid model has become the focus of research in the field of modeling.

SUMMARY OF THE INVENTION

This application proposes a mesh-parameter hybrid model modeling method and system, which are applied to the fields of 3D prototype redesign, additive manufacturing, and 3D model rendering. The point cloud prototype extracted from the 3D model is converted into a mesh model, and a redesign tool is provided by means of parametric modeling. The mesh model obtained by this modeling method is watertight and free of topology errors, and has a certain thickness. volume models, suitable for additive manufacturing as well as rendering.

To achieve the above purpose, the application provides the following solutions:

A mesh-parameter mixed model modeling method, comprising the following steps:

Obtain the point cloud data of the object to be measured, use the grid generation technology to convert the point cloud data into a grid surface, perform grid offset processing and boundary stitching processing on the grid surface, and convert the grid surface to the grid surface. converted to closed said mesh model;

Setting characteristic parameters of the object to be measured, establishing a parametric model based on the characteristic parameters, and performing grid processing on the parametric model, and the parametric model is represented by a grid;

Based on Boolean operations, the mesh model and the parametric model are combined into a hybrid model, which is characterized using the mesh.

Optionally, use an improved greedy projection triangulation method to obtain the mesh surface;

The improved greedy projection triangulation method includes the following steps:

Smoothing the point cloud data using the moving least squares method to obtain an MLS fitting surface;

Based on the MLS fitting surface, obtain point cloud normal vectors of all the point cloud data;

Based on the point cloud normal vector, the greedy projection triangulation method is used for reconstruction to obtain the mesh surface.

Optionally, the grid offset processing method includes:

Based on the influence of the shape of the triangle, the distance of the centroid and the angle of the vertex on the vertex normal, a new weight factor λ is established;

It is assumed that there are n continuous boundary vertices on the left and right sides of the boundary vertex v _i , which are the left boundary vertex (v _l , l=i-1, i-2,...,in) and the right boundary vertex (v _r , r=i+1,i+2,...,i+n), the left and right sides of the boundary vertex are respectively connected to the left boundary vertex and the right boundary vertex through the boundary vertex v _i , Each obtains n vectors, denoted as left vector ( _ei,l ,l=i-1,i-2,...,in) and right vector ( _ei,r ,r=i+1,i+ 2,...,i+n);

Based on the left vector and the right vector, calculate the left vector _el and the right _{vector er} ;

Based on the left vector _{e l} and the right _{vector er} , a correction vector Ne is established;

A boundary vertex weight k ₁ and a correction vector weight k ₂ are respectively allocated to the initial normal vector N _v and the correction vector _Ne of the boundary vertex v _i , based on the initial normal vector N _v , the correction vector _Ne , The boundary vertex weight k ₁ and the correction vector weight k ₂ are used to calculate the corrected boundary vertex normal vector N _b ;

Based on the new weight factor λ, the left vector e _l , the right _{vector er} , and the boundary vertex normal vector N _b , the modified normal vector of the boundary vertex v _i is obtained, and the mesh biasing is completed. set processing.

Optionally, the method for boundary stitching processing includes:

After offsetting each vertex of the mesh surface along the vertex normal vector, a mesh offset surface is obtained;

establishing a seam surface between the mesh surface and the mesh offset surface, the seam surface is a collection of discrete triangular patches;

Use the labeling algorithm to optimize the triangular patch, and sequentially generate new triangular patches, insert the new triangular patch between the mesh surface and the mesh offset surface, and complete the mesh The surface and the boundary of the mesh offset surface are stitched.

Optionally, the method for the Boolean operation includes:

Detecting triangular mesh patches that intersect between the mesh model and the parametric model;

Perform local remeshing on the meshes of the intersecting triangular mesh patch area and its neighbors to adjust the mesh density of the intersection area;

Detect the intersecting triangular mesh patches again, and delete them from the mesh. The mesh model after deleting the intersection area is divided into different mesh patches;

Recombining the grid patches based on the Boolean operation and the inner and outer distribution of the grid patches, and the combined model is a grid patch with gaps;

Based on the recombined mesh patches, the boundary edge loops of the mesh with gaps are extracted, the corresponding relationship between the boundary edge loops is established by voting, and the corresponding boundary edge loops are connected by an iterative forward stitching method to generate a mesh- Parametric Mixture Model.

Optionally, the method for judging the intersection of triangular meshes includes the following steps:

By adopting the method of octree, the grid model and the parameter model are respectively divided into octrees with a given number of points and space size, so as to obtain grid octrees and parameter octrees respectively;

Detect whether all leaf nodes corresponding to the grid octree and the parameter octree intersect in space, and if they intersect, perform traversal intersection detection on all one-ring adjacent surfaces of the vertices in the corresponding leaf nodes.

Optionally, the method for adjusting the grid density of the intersection area includes the following steps:

Set the vertex control edge length of the intersecting triangular mesh patch to a given edge length, perform curvature adaptive control edge length calculation on its neighborhood, and then perform weighted smoothing on the mesh control edge length of the entire area, calculate After the control side length is obtained, the local mesh is re-meshed by the method of local topology adjustment to complete the adjustment of the mesh density in the intersection area.

Optionally, the method for recombining the grid patches includes:

According to the Boolean operation, firstly, the inner and outer judgment of the grid patch is performed, and the inner and outer judgment of the grid patch is determined according to the calculation of the three-dimensional winding number;

Using the voting method, select the corresponding nearest boundary ring for each vertex on the boundary ring. If the corresponding vertices in the boundary ring also make the same vote, that is, the two boundary rings are corresponding, and it is determined to be stitched. The corresponding relationship of the boundary ring, complete the recombination of mesh patches.

In order to achieve the above purpose, the present application also provides a grid-parameter hybrid model modeling system, including a point cloud data module, a grid model module, a parameter model module and a Boolean operation module;

The point cloud data module is used to obtain point cloud data of the object to be measured;

The grid model module is used to convert the point cloud data into a grid surface by using grid generation technology, perform grid offset processing and boundary stitching processing on the grid surface, and convert the grid surface is the closed mesh model;

The parameter model module is used to set the characteristic parameters of the object to be measured, establish a parameter model based on the characteristic parameters, and perform grid processing on the parameter model, and the parameter model is characterized by a grid;

The Boolean operation module is configured to synthesize the mesh model and the parametric model into a mixed model based on the Boolean operation, and the mixed model is characterized by using the mesh.

Optionally, the Boolean operation module includes a cross detection unit, a grid density adjustment unit, a grid patch unit and a stitching unit:

The intersection detection unit is configured to detect the triangular mesh face that intersects between the mesh model and the parametric model;

The mesh density adjustment unit is used to locally re-mesh the meshes of the intersecting triangular mesh patch area and its neighborhood, so as to adjust the mesh density of the intersection area;

The mesh patch unit is used to detect the intersecting triangular mesh patches again, and delete them from the mesh. The mesh model after deleting the intersection area is divided into different mesh patches, based on Boolean operations and The inner and outer distributions of the grid patches recombine the grid patches, and the combined model is a grid patch with gaps;

The stitching unit is used to extract the boundary edge loops of the mesh with gaps based on the recombined mesh patches, establish the corresponding relationship between the boundary edge loops by voting, and connect the corresponding boundary edge loops by an iterative forward stitching method. up, generate a mesh-parameter hybrid model.

The beneficial effects of this application are:

The present application discloses a mesh-parameter hybrid model modeling method and system, which are applied to the fields of three-dimensional prototype redesign, additive manufacturing, and three-dimensional model rendering, etc. Grid surface model, and then perform grid offset and boundary stitching on the surface model to make it a closed grid model; the parametric model is derived from various user-defined features, and is characterized by grid; then The Boolean operation of the two models allows the two models to be combined into one model, which not only maintains the accuracy of the original measurement model but also has a hybrid model with user-defined added features. At the same time, the hybrid model is represented by a grid, and the user-defined parameter features are retained at the feature added by the user. This feature enables the hybrid model to apply the operations of the grid model (such as grid reconstruction, smoothing, single The addition and deletion of patches, etc.), and the operation of the parametric model (such as direct stretching and deformation of the model, etc.) can be applied to improve the accuracy and efficiency of subsequent redesign.

Description of drawings

In order to illustrate the technical solutions of the present application more clearly, the following briefly introduces the accompanying drawings that need to be used in the embodiments. Obviously, the drawings in the following description are only some embodiments of the present application. As far as technical personnel are concerned, other drawings can also be obtained based on these drawings without the need for creative labor.

1 is a schematic diagram of the overall flow of the grid-parameter hybrid model modeling method according to Embodiment 1 of the present application;

2 is a schematic diagram of a ring neighborhood of an arbitrary vertex v _i according to Embodiment 1 of the present application;

3 is a schematic diagram of the estimation error of vertex normal vector at the boundary in Embodiment 1 of the present application;

FIG. 4 is a schematic diagram of using a ring of neighborhood patch normal vector estimation in Embodiment 1 of the present application;

5 is a schematic diagram of a method for generating a triangular patch sequence T in a directed graph G according to Embodiment 1 of the present application;

6 is a schematic diagram of an octree division method in Embodiment 1 of the present application;

7 is a schematic flowchart of determining whether two triangular patches in a space intersect in Embodiment 1 of the present application;

8 is the relationship between the approximate tolerance ε and the target side length l in the first embodiment of the application, wherein a describes the 2D situation, and b describes the 3D situation;

FIG. 9 is a schematic diagram of a local remeshing method in Embodiment 1 of the present application;

10 is a schematic diagram of a method for judging whether a triangular mesh patch is located inside or outside another triangular mesh model in Embodiment 1 of the application;

11 is a schematic diagram of an iterative stitching method in Embodiment 1 of the present application;

FIG. 12 is a schematic structural diagram of a grid-parameter hybrid model modeling system according to Embodiment 2 of the present application.

FIG. 13 is a diagram of a specific example of the grid-parameter hybrid model modeling method and system according to Embodiment 3 of the present application.

Detailed ways

The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application. Obviously, the described embodiments are only a part of the embodiments of the present application, rather than all the embodiments. Based on the embodiments in the present application, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present application.

In order to make the above objects, features and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and specific embodiments.

The following embodiments are all developed based on the technical requirements for the design and manufacture of rehabilitation aids at the calf of the human body.

Example 1

As shown in FIG. 1 , it is a schematic diagram of the overall flow of the grid-parameter mixed model modeling method according to an embodiment of the present application. First, a grid model and a parameter model need to be obtained. In this embodiment, the grid model comes from the actual measurement data of the human calf. After the measurement point cloud of the leg is obtained, the point cloud data needs to be converted into The initial mesh surface model, and then the mesh offset and boundary stitching are performed on the surface model to make it a closed mesh model. The parametric model is a variety of geometric features defined by the user, and meshing operations are performed to characterize them using meshes.

After completing the acquisition of the initial mesh model and parameter model, it is necessary to perform Boolean operations on the two models to combine the two models into one model. Density adjustment of regions and reorganization and stitching of mesh patch patches result in a hybrid model that retains the accuracy of the original leg data and has user-defined added geometric features.

Below, the operation steps involved in this embodiment are described in detail:

1. Conversion of point cloud data to mesh model

The first step in mesh-parametric hybrid modeling is to obtain a mesh model of the measurements with sufficient accuracy. With the development and application of visual measurement technology, the acquisition of three-dimensional information of objects has become more accurate and efficient. The data obtained using visual measurement are mainly disordered scattered data set points, namely point cloud data. The point cloud data can be reconstructed by a reconstruction algorithm to restore a mesh model that approximates the surface of the object.

In the traditional greedy projection triangulation algorithm, the point cloud normal vector accuracy has a direct impact on the reconstruction results. Using the point cloud normal vector obtained by PCA, even if the point cloud is on the same plane, the normal vector direction will not be strictly consistent. Therefore, in this embodiment, moving least squares (MLS) is used for resampling to estimate the normal vector. This method can also smooth the input point cloud data to improve the reconstruction effect of greedy projection triangulation. In the curve-surface fitting process of discrete point clouds, MLS can provide higher fitting accuracy than PCA and LS when the curve and surface form is unknown.

On the local subdomain of the point cloud, the fitting function f(x) is expressed as:

where α(x)=[α ₁ (x),α ₂ (x),...,α _n (x)] ^T is the coefficient to be determined, ρ(x)=[ρ ₁ (x),ρ ₂ ( x),...,ρ _n (x)] ^T is the basis function.

Given that node X=[x ₁ , x ₂ ,...,x _m ] ^T , the node value corresponding to each node is Y=[y ₁ , y ₂ ,..., y _m ] ^T , formula (1 ), the fitting function must satisfy,

Substituting equation (1) into equation (2), we get

时，式(3)有极小值Obviously, when

When , equation (3) has a minimum value

B(x)＝[w(x-x₁)p(x₁),...,w(x-x_m)p(x_m)]，则式(4)可写成矩阵形式：make

B(x)=[w(xx ₁ )p(x ₁ ),...,w(xx _m )p(x _m )], then equation (4) can be written in matrix form:

Solutions have to

α(x)=A ^-1 (x)B(x)Y (6)

Substitute into equation (1) to get the fitting function,

f(x)=ρ ^T (x)A ^-1 (x)B(x)Y (7)

s_max是影响区域的半径，则可以使用如下三次样条函数作为权函数：After selecting the basis function and the weight function, the fitting function of the local subdomain can be obtained by formula (7). The weight function also plays a very important role in MLS, and it should have compact support, that is, it should not be equal to 0 in the current subdomain, and be all 0 outside the subdomain. The weight function should be non-negative in the subdomain and decrease as ||xx _i || ₂ increases. The commonly used weight function is the spline function, denoted s=xx _i , and the distance of the entire point cloud domain is normalized at the same time

s _max is the radius of the affected area, then the following cubic spline function can be used as the weight function:

Usually s _max needs to be large enough to ensure that A ^-1 (x) in equation (7) is meaningful. At the same time, since the basis function is a linear basis, in the process of surface fitting, the affected area should contain at least three nodes that are not on the same straight line.

After selecting the basis function and weight function, use equation (7) to find the fitting surface. Generally, the weight function can guarantee C ¹ continuity. Since the fitting function will inherit the smoothness of the weight function, the fitting function also has at least C ¹ continuity. The point cloud can be made smoother by projecting it onto the fitted surface.

After obtaining the fitted surface, the normal vector of the node can be obtained by formula (9):

Therefore, the process of the improved greedy projection triangulation algorithm is as follows:

Step1. Use the MLS smoothing operation on the point cloud data to improve the smoothness of the point cloud data;

Step2. Calculate all point cloud normal vectors based on the surface fitted by MLS;

Step3. Use the greedy projection triangulation method to reconstruct.

2. Grid Bias

The point cloud data obtained by the scanning technology is only the surface data of the object, and the surface of the object is also generated using the grid generation technology. For the non-closed point cloud, the mesh model obtained by this operation will be a non-closed thin patch, which cannot be applied to actual manufacturing. Through the mesh offset operation, the sheet can be expanded into two surfaces with the same topological connection relationship and similar geometric shapes, and a closed mesh model can be obtained by boundary stitching.

The triangular mesh model uses a lightweight triangular patch structure to describe the topological relationship between data points. It has the advantages of fast flexibility and strong topology adaptability when expressing surface models. It is widely used in CAD/CAE/CAM systems. In the process of surface offset, surface reconstruction, model noise reduction and smoothing, mesh hole repair, etc., the normal vector information of the mesh model is indispensable, and the accuracy of the normal vector estimation will seriously affect the subsequent model processing effect. .

Using the estimated normal vector for mesh offset, a non-closed mesh surface model can be extended to a volume model. In the model with large curvature change, due to the error of vertex normal vector estimation and the lack of geometric information of boundary vertices, the topological quality of the offset surface is degraded, and its shape is difficult to keep consistent with the original surface. This deviation increases as the offset distance increases.

^A parametric surface is a continuous map from R2 to ^R3 , which can usually be represented using an analytical expression. Each node on the parametric surface can accurately calculate its normal vector. Unlike parametric surfaces, a mesh surface is a discrete representation and cannot accurately represent all nodes with one analytical expression.

The coordinates of each vertex of the mesh model can be accurately obtained. Combined with the topological relationship output by the model, the normal vector information of each patch can be accurately obtained, and the vertex normal vector can be estimated by using the surface normal vector, that is, all the information in the model can be calculated. Effective use, while reducing the error introduced by the fitting process, makes the vertex normal vector estimation result more accurate.

A triangular mesh model can be represented as a linear table composed of vertices and triangular patches, M={V,F}, where V={v _i |1≤i≤n} is the set of all vertices in the model, F={ f _j |1≤j≤m} is the set of all the patches in the model.

为所求顶点法矢量，f_j表示与该顶点相接的三角面片，

为三角形f_j的质心，G_j为质心到顶点v_i的欧式距离，a_j为三角形f_j在顶点v_i处的顶角，

为三角面片f_j的外法向。Fig. 2 is a schematic diagram of a ring neighborhood patch of a vertex v _i of the triangular mesh model,

is the normal vector of the desired vertex, f _j represents the triangular patch connected to the vertex,

is the centroid of the triangle f _j , G _j is the Euclidean distance from the centroid to the vertex v _i , a _j is the vertex angle of the triangle f _j at the vertex v _i ,

is the outward normal of the triangular patch f _j .

定义为：

defined as:

由下式定义：

is defined by:

The normal vector of each patch can be accurately calculated by Equation (11). Obviously, the weight selection in Equation (10) determines the estimation accuracy of the vertex normal.

There are many geometric properties of triangles, such as area, distance from centroid to vertex, vertex angle, etc. Generally speaking, the larger the area and apex angle of a triangle, the closer the shape is to a regular triangle, and the greater its contribution to the vertex normal vector; The contribution of the normal vector will be smaller. According to these features, a certain geometric feature can be selected as the weight, or a combination of these features can be used to form a combined weight factor. However, for the weight factor of a single feature, there is a problem that the geometric shapes of the triangles are quite different but the same weight is expressed. As shown in Figure 2, the two pairs of triangles in the figure have the same area, vertex angle and centroid distance, but their shapes are quite different. Under the measurement of a single weight, the two pairs of triangles will express equal weights. Therefore, the measurement of a single weight is difficult to accurately reflect the true contribution of the patch to the vertex normal.

In order to improve the accuracy of the weight factor describing various geometric properties of triangles, a shape factor μ that can express the shape of the triangle is introduced, which is defined as twice the ratio of the radius of the circumcircle to the radius of the inscribed circle of the triangle.

where a, b, and c are the lengths of the three sides of the triangle, respectively. Combined with the shape centroid distance method of this shape factor, different weights are given to triangular patches of different shapes.

In order to improve the estimation accuracy of the vertex normal vector in characteristic areas such as large curvature change and sharp edges, the improvement is made on the basis of the shape centroid weight, and the influence of the shape of the triangle, the centroid distance and the angle of the vertex angle on the vertex normal vector is comprehensively considered. , and propose a new weighting factor. The expression is as formula (11):

where α is the angle of the vertex of the triangle.

The boundary vertex of the model, due to the insufficient number of surrounding patches, leads to the lack of geometric information, which makes the estimation accuracy of the normal vector at this location low.

Figure 3 is a schematic diagram of the error of the normal vector estimation of the boundary vertex. When the outer side is convex, the triangle at the boundary has a tendency to deflect inward, so the estimated normal vector will be biased towards the model direction (N _convex vector in Figure 3), when the outer side is When the surface is concave, the situation is opposite (the N _cnocave vector in Fig. 3), so the normal vector estimation result needs to be corrected at the boundary.

As shown in FIG. 4 , the N _v vector in the figure is a value estimated by using the normal vector of a ring of neighborhood patches. If this vector is to be deflected toward the true normal vector, a correction vector _Ne is required. Obtain and set n continuous boundary vertices on the left and right sides of the boundary vertex v _i , respectively (v _l ,l=i-1,i-2,...,in), (v _r ,r=i +1,i+2,...,i+n). On the left and right sides, it can be connected to v _l , v _r through v _i respectively, and each obtains n vectors, which are respectively recorded as (e _i,l ,l=i-1,i-2,...,in) and (e _i,r ,r=i+1,i+2,...,i+n).

After obtaining the two vector sets, use equation (14) to calculate the two edge vectors e _l , _er . where n=round(b _size /10), where b _size is the number of vertices on the current boundary.

The correction _vector Ne is defined as the cross product of _{e l} and er:

In order to make the initial normal vector N _v of vi tend to the correction vector Ne smoothly, two weights _{k 1} , k ₂ are _assigned to N _v and _Ne respectively, and the selection of the weight is related to the curvature of the vertical outward direction at the boundary , the greater the curvature of the direction |k ₂ | Therefore, the corrected boundary vertex normal vector N _b is determined by:

N _b =k ₁ N _v +k _{2 Ne} ,|k ₁ |+|k ₂ |=1 (16)

Substituting the new weight factor proposed above into the normal vector estimation, we get

3. Border stitching

Based on the above, after offsetting each vertex of the original model along the vertex normal, the offset model can be obtained. The offset position of the vertex is determined by:

表示偏置后顶点位置，

表示原顶点位置，dis表示偏置的距离。in

represents the vertex position after offset,

Represents the original vertex position, and dis represents the offset distance.

The vertices of the two models correspond to each other, and the topological connections between the vertices are the same. To get a closed volume model, two faces need to be stitched together. Denote the boundary point set of the original model and the boundary point set of the biased model as P and Q respectively, where:

P={p ₀ ,p ₁ ,p ₂ ,...,p _m-1 } (19)

Q={q ₀ ,q ₁ ,q ₂ ,...,q _n-1 } (20)

Each of the two boundaries contains m, n points, and the boundary is connected by m, n line segments.

Stitching is done by constructing a surface between two discrete curves. This surface, like the two models, is a collection of discrete triangular patches. The vertices of these patches are boundary points, and a stitched patch is formed by picking two points from one boundary sequence and one point from another boundary sequence. So each triangular patch can be defined as {pi ,p _j ,q _k } or { _pi ,q _j , _{q k }} .

Obviously, each newly generated triangular patch satisfies:

(1) Each patch consists of a "silhouette edge" (edge whose two vertices are in the same boundary sequence, such as p _i p _j ) and two "bridge edges" (edge whose two vertices are not in the same boundary sequence) , such as p _i q _k , p _j q _k );

(2) There is a common bridging edge for every two adjacent triangular patches;

(3) For any two bridging edges p _i q _j , p _k q _l , if i≤k, then j≤l, and vice versa.

The problem of obtaining this set of triangle sequences can be viewed as a graph theory problem. First define a directed graph G=<V, Arc> to describe all bridging edges between two contours. where V represents the set of nodes in the directed graph G:

V={v _i,j |i=0,1,2,...,m-1,j=0,1,2,...,n-1} (21)

Arc is a collection of arcs:

Arc={ _ak =< _vk,l ,vs _,t >|s=k and l=t-1 or s=k-1 and l=t} (22)

Obviously, in the directed graph G, each arc uniquely corresponds to a triangular patch (each arc actually determines 3 vertices). Therefore, any path from the source node v _0,0 to the end node v _m-1,n-1 can determine a unique triangular patch sequence T, as shown in Figure 5.

In order to make the shape of the newly generated patch as regular as possible, formula (12) is used to describe the shape regularity of the new triangular patch. The goal of optimization is to maximize the sum of the shape factors of all triangular patches in the triangular patch sequence (regardless of the sequence, the total number of all triangular patches is the same m+n-2). Use the labeling algorithm to find the optimal path of this directed graph G.

Denote the label of node v _i,j as (i,j,μ _a ,Dis _i,j ,prev), where i,j are node subscripts, μ is the shape factor defined by equation (12), Dis _{i, j} represents the weighted length from the source node to the current node, and prev is the position of the previous node of vi _,j in the current path relative to it.

The distance from the source node to the current node is the maximum distance from the source node to the previous node of the current node plus the current weighted arc length:

Dis _i,j =max(Dis _i,j-1 ,Dis _i-1,j )+μ _a (23)

The algorithm flow for finding the optimal path is as follows:

Step1. Initialize the label of v _0,0 ;

Step2. Calculate Dis _i,j+1 and Dis _i+1,j and select the larger value of the two, and update the next node to be a node with a larger weighted length;

Step3. Record the prev value in the label. When Dis _{i, j+1} is large, prev=0, and when Dis _{i+1, j} is large, prev=1;

Step4. Repeat Step2, Step3.

Step5. Output the sequence of prev.

Determining the sequence of prev means determining the triangular patch sequence T in the directed graph G that satisfies the optimization objective. It is only necessary to generate new triangular patches in turn according to the sequence and insert them into the contour boundary to complete the stitching of the two models.

4. Parametric Surface Meshing

The overall process of generating parametric surface meshing is as follows:

1) Read in the combined parametric surface model and specify the size control information.

2) Identify the adjacent features and curvature features in the model, and then combine the specified size control information to perform geometrically adaptive discretization on all curves in the model, and create a geometrically adaptive density field at the same time.

3) Generate meshes one by one for the surface patches in the model according to the specified size control information and the geometric adaptive density field.

4.1. Geometrically adaptive surface boundary discretization process

All surface boundary curves are sampled with a sufficiently small le to generate a set of sampling points, and a global size value is set at each sampling point. Both the global size value and le can be set by the user, the former defaults to 1/10 of the size of the outer bounding box of the model, and the latter defaults to 1/100 of the size of the outer bounding box of the model. In the sampling process, the curve length L is calculated for each curve by the iterative composite Simpson numerical integration formula, and the number of sampling points on the curve can be determined as m=L/le+1; then the coordinates of each sampling point are obtained according to the arc length. .

Using the sampled boundary as input, perform surface CDT on the set of sampled points. For each sampling point, the minimum value of the radius of the circumcircle of several units to which it belongs is used as the adjacent feature distance, and the adaptive size of the adjacent feature is obtained. The size value is compared with the original size value and the smaller value is taken as the new size value. .

Traverse the sampling points, if the sampling point has curvature features, find the adaptive size of the curvature feature and compare it with the existing size value of the point, and take the smaller value as the new size value.

If there are other size control methods, traverse the sampling points, compare the size obtained by other size control methods with the existing size value of the point, and take the smaller value as the new size value.

Discrete each boundary curve to ensure a reasonable transition of the size of the obtained discrete points.

4.2 Creating a Geometrically Adaptive Density Field

The geometric adaptive density field is created on the CDT result of the sampling point of the surface boundary. Since the result has been obtained in the process of boundary adaptive discretization, it does not need to be recalculated, which can reduce a lot of calculation. On the CDT result, first set the value of the adaptive size of the adjacent features at the outer center of the triangle element. This value can be obtained by using the radius of the circumcircle of the triangle as the distance of the adjacent features, and using the same adaptive calculation process of the adjacent features for the boundary points.

4.3 Mesh generation

This embodiment adopts a surface mesh generation method based on the mapping method and the advancing front technique (AFT). The method carries out frontier advancement on the parameter plane, and supports two advancement standards: the shortest edge first and the oldest edge first; the algorithm efficiency of generating the optimal point of the frontier can be improved by checking the grid validity and element quality on the parameter plane; Finally, the mesh quality is optimized by edge swapping and smoothing. The geometric self-adaptive discrete result of the combined surface boundary is used as the input of this method. When generating a frontier candidate point, the self-adaptive size value at the candidate point is obtained by using the surface geometric self-adaptive density field, and other size control methods are considered comprehensively. The obtained size value, take the minimum value as the size value of the point, and finally generate the geometric adaptive mesh of the combined parametric surface.

5. Detection of the intersection area

In this embodiment, the method of adaptive octree is used to speed up the detection process of the intersection area. The basic method is to divide the octree of the given number of points and the space size for the two grid models respectively, and then detect the two grid models. Whether all the leaf nodes corresponding to each octree intersect in space, and if so, perform traversal and intersection detection on all the adjacent surfaces of the vertices in the corresponding leaf node. For a higher-level octree node (ie, a node close to the octree's root node), if it does not intersect with all octree nodes at the same level, there is no need to further octree it. The specific division process is shown in Figure 6.

The process of judging whether two triangular patches in space intersect is shown in Figure 7:

分别计算出它们相对于另一个三角面片所在的平面的有向距离

1) According to the six vertices of the input two triangular patches (T ₁ , T ₂ )

Calculate their respective directed distances relative to the plane on which the other triangular patch lies

2) According to whether the six directional distances are zero, determine whether the two triangular facets are coplanar;

3) For coplanar triangular patches, calculate the number of windings corresponding to the six vertices. If the winding numbers are all zero, it means that the two triangular patches do not intersect. otherwise intersect;

4) For two triangular patches that are not coplanar, it is necessary to determine whether they are located on the same side of the other plane according to whether the signs of the directional distances of the vertices of each triangular patch are the same. On the same side of another plane, the two triangular patches do not intersect;

5) For triangular patches on different sides, further judgment is needed according to whether their parts at the intersection of the plane overlap.

6. Density adjustment of the intersection area

In this embodiment, the mesh density is adjusted by performing local re-mesh on the intersecting triangular mesh area and its neighboring meshes, and the core lies in the determination of the mesh control side length in this area. In order to achieve better mesh quality, select the intersecting triangular mesh patch area and its neighbors of three to five rings for density control: set the vertex control side length of the intersecting triangular patch to the given side length, For its neighborhood, the curvature-adaptive control edge length is calculated. Finally, in order to prevent the density mutation, the mesh control edge length of the entire region is weighted and smoothed. After the control side length is calculated, the local mesh is re-meshed by means of local topology adjustment.

6.1 Calculation of Controlled Side Length with Curvature Adaptive

Figure 8 (a depicts the 2D case, b depicts the 3D case) shows the relationship between the approximation error ε and the target side length l. Assuming that a straight line of edge l is used to approximate the circular arc, the maximum approximation error ε, that is, the maximum deviation from the straight line to the circular arc, follows the constraint relationship:

Applying the formula (24) to the process of fitting the curved surface by the triangular patch, corresponding to Figure 8b, the relationship between the side length of the triangular patch (approximately a regular triangle) and the error ε and the local curvature is:

For the expression of the mesh model, the shorter the edge length of the triangular mesh, the smaller the error ε, the closer the mesh is to the surface, and the control of the mesh edge length is achieved through the error ε and the local curvature κ of the mesh . In order to achieve finer control, the maximum normal curvature κ ₁ (p) is selected to calculate the radius of curvature r of the mesh, so that the control side length of the mesh is as short as possible.

When dealing with grids of nearly the same resolution, it is acceptable to choose a common error ε to control the entire grid. But when dealing with meshes of significantly different resolutions, there is still a waste of triangles. Because it is difficult to define a suitable ε, for conservative estimation, ε needs to fit into denser parts, which leads to over-subdivision in low-curvature regions. To avoid over-subdivision of the entire mesh, ε cannot be too large, otherwise it will lead to under-subdivision of areas of high curvature. In short, a uniform ε will limit the adaptability of the mesh edge length to the curvature.

Therefore, it is necessary to control the edge length of the mesh through the adaptive error ε(x), and the original local edge length of the mesh can be used to control the mesh error in different regions. If the error control of the mesh in the local area is positively related to its shortest side length, that is, control ε(x)=αl _min (x).

In this embodiment, the local average side length and the shortest side length are combined to control the local side length of the mesh. In order to measure the distribution of local edge lengths, a local measurement factor is introduced:

Measure the local edge length distribution using weighting factors

e ^-λ(ω(x)-1) (27)

_lmin (x) and _Laver (x) are interpolated, and the control error is a linear term of the interpolation. Without loss of generality, the local error can be controlled as

Among them, α and λ are self-defined control coefficients, among which α is the main control coefficient, and its size determines the size of the error, and λ is an auxiliary control coefficient, which can control the interpolation process. At the same time, in order to avoid the generation of too long or too short sides in the calculation process, the length of the control side needs to be trimmed, so that

L(x)∈[ _Lmin (x), _Lmax (x)] (29)

in

L _min (x)=γε(x) (30)

L _max (x)=δε(x) (31)

γ, δ are self-defined coefficients. The final local control side length L(x) is consistent with the local side length and curvature.

L(x) is relative to the vertex, for the edge e(v ₁ , v ₂ ), its length should be controlled

L(e)=min(L(v ₁ ),L(v ₂ )) (32)

6.2 Local remeshing method

The input to remeshing is a mesh represented by a half-edge data structure, which provides a convenient loop method for vertices, edges, faces, and their topology information. To preserve the shape of the mesh model, the vertices are reprojected back to the mesh through a k-d tree background field built from the initial mesh. The whole process is shown in Figure 9, and specifically, it is implemented according to the following steps.

1) Cyclically update local information around vertices, including local minimum edge length, local average length, and curvature of 1-ring neighbors.

2) According to the updated information, loop the vertices again, calculate the target local length L(v), and limit L(v) ∈ [L _min (v), L _max (v)].

3) Circular edge table, adjust the mesh according to the control edge length L(e)=min(L(v1), L(v2)), split the edges that are too long (longer than 4/3L(e)), and shrink the ones that are too short side (shorter than 4/5L(e)).

4) Circular edge table, if flipping reduces the degrees of freedom of the vertex, flip the edge.

5) Circulate the vertex table, perform tangent relaxation on each vertex, and reproject it back to the initial mesh through the k-d tree background. This embodiment uses Laplace smoothing to relax the vertex.

6) Repeat steps 3) to 4) for 5-10 iterations.

7. Patch Patch Recombination

The mesh model is recombined according to the definition of the Boolean operation, and the inner and outer judgments of the triangular patch patches are firstly performed. The Boolean intersection is defined as the combination of mesh patches located inside the two triangular mesh models, the Boolean union is defined as the patch located outside the two mesh models, and the Boolean difference is a combination of one inside and one outside, and the result of Boolean difference is not unique. . The inner and outer determination of the grid patch can be determined according to the calculation of the three-dimensional winding number. In this embodiment, the judgment is made by means of ray projection. As shown in Figure 10, if you want to determine whether the divided triangular mesh patch is inside or outside of another triangular mesh model, you can randomly select N vertices on the mesh patch, and use kdTree to calculate its location in another mesh. The closest point on the model, calculate the ray from this point to the closest point, calculate the inner product of the ray and the plane normal to the closest point, and determine whether the point is inside or outside the grid model. To eliminate the special case, the same operation is done for N vertices to determine the inner and outer information of the mesh patch in the case of more than N/2 vertices.

In general, two intersecting mesh models will be divided into different numbers of mesh patches. After the patches to be stitched are combined based on the above method, the corresponding relationship of the boundary rings to be stitched needs to be determined. It can be determined by voting. For each vertex on the boundary ring, select its corresponding nearest boundary ring, if the corresponding vertex in the boundary ring also makes the same vote, that is, the two boundary rings are corresponding.

8. Mesh patch stitching algorithm

The last step in the Boolean calculation process is to connect the triangular meshes with gaps. In this embodiment, an iterative forward stitching strategy is adopted.

The specific algorithm implementation can be summarized as the following steps:

1) Query the respective boundary rings l ₁ ={V ₀ ,V ₁ ,...,V _n } and l ₂ ={U ₀ ,U ₁ ,...,U _n } of the two mesh models;

为l₂中离V_i最近的顶点，然后将V_i向

移动，更新

2) For each vertex V _i in l ₁ , query

is the vertex closest to _Vi in l ₂ , and then move _Vi towards

move, update

3) for each vertex U _i in l ₂ , take the same processing in step 2);

4) Use the aforementioned remeshing method to reconstruct a ring neighborhood of _l1 and _l2 .

The above steps are performed iteratively until the number of vertices in l ₁ and l ₂ are the same and the distance between the closest vertices is below a threshold. Finally, replace the corresponding points in l ₁ and l ₂ with an identical vertex, that is, stitching can be achieved. The process of iterative stitching is shown in Figure 11:

If in the process of establishing the correspondence between the points of the two boundaries, if there is a situation where a vertex has two corresponding points, then the distance between the two vertices will become very close in the iterative process. The process of local reconstruction of the mesh will shrink two vertices that are very close to one vertex, and finally establish a one-to-one correspondence. Similarly, if an edge is stretched very long in the process of topology adjustment, in the process of edge splitting, new vertices will be split to establish a corresponding relationship. Going back to the whole process of reconnection again, due to the updating process of the vertex position, the vertex may be updated to any region in the space. This is inconsistent with the actual mesh. In order to better fit the actual situation, after each update of the vertex position, it is re-projected back to the nearest triangular patch in the original mesh model. .

Embodiment 2

As shown in FIG. 12 , it is a schematic structural diagram of the grid-parameter hybrid model modeling system according to the second embodiment of the application, which mainly includes a point cloud data module, a grid model module, a parameter model module and a Boolean operation module;

Specifically, in this embodiment, the point cloud data module is used to acquire point cloud data of the object to be measured.

The mesh model module is used to convert point cloud data into mesh surfaces by using mesh generation technology, perform mesh offset processing and boundary stitching processing on mesh surfaces, and convert mesh surfaces into closed mesh models.

The parametric model module is used to set the characteristic parameters of the object to be measured, establish a parametric model based on the characteristic parameters, and perform grid processing on the parametric model, and the parametric model is represented by a grid.

The Boolean operation module is used to synthesize a mesh model and a parametric model into a mixed model based on Boolean operations. The mixed model is characterized by mesh, including intersection detection unit, mesh density adjustment unit, mesh patch unit and stitching unit.

The intersection detection unit is used to detect the triangular mesh patches that intersect between the mesh model and the parametric model. The mesh density adjustment unit is used to locally re-mesh the meshes of the intersecting triangular mesh area and its neighborhood, so as to adjust the mesh density of the intersection area. The mesh patch unit is used to re-detect the intersecting triangular mesh patches and delete them from the mesh. The mesh model after deleting the intersection area is divided into different mesh patches, based on Boolean operations and meshes The inner and outer distributions of the patches recombine the mesh patches, and the combined model is a mesh patch with gaps. The stitching unit is used to extract the boundary edge loops of the mesh with gaps based on the recombined mesh patches, establish the corresponding relationship between the boundary edge loops by voting, and connect the corresponding boundary edge loops by an iterative forward stitching method. Generate mesh-parametric hybrid models.

Embodiment 3

As shown in FIG. 13 , it is a specific application example diagram of the grid-parameter hybrid model modeling method and system according to the third embodiment of the present application, which shows the redesign process of the rehabilitation aid at the lower leg of the human body.

The 3D model of the human calf is scanned by the vision sensor to obtain the point cloud prototype, and the point cloud model is applied to the point cloud data module to generate the mesh model, and then the mesh model module performs mesh offset processing and boundary stitching on the mesh surface. processing, a closed mesh model is obtained, and the accuracy of the original model is preserved.

In the actual design process of rehabilitation aids, in order to meet the needs of saving materials, reducing product weight, improving the breathability of rehabilitation aids, and improving wearing comfort during the manufacturing process, it is necessary to perform drilling operations on the basis of the original model. The parametric method is used to define the cylindrical feature, and the parametrically defined cylindrical feature is meshed, and multiple models are aligned in the three-dimensional space. Finally, the Boolean difference between the initial protective gear model and the custom hole is calculated by the Boolean operation module.

In the whole process, the watertightness and good topological properties of the mesh model are ensured. At the same time, the example involved in the calculation is a solid model with thickness, and the final result is saved as a 3D mesh surface model, which can be used to generate wearable meshes with 3D printing technology. rehabilitation aids.

Claims (10)

1. A grid-parameter hybrid model modeling method is characterized by comprising the following steps:

acquiring point cloud data of an object to be detected, converting the point cloud data into a mesh curved surface by utilizing a mesh generation technology, carrying out mesh offset processing and boundary stitching processing on the mesh curved surface, and converting the mesh curved surface into a closed mesh model;

setting characteristic parameters of the object to be detected, establishing a parameter model based on the characteristic parameters, and carrying out gridding processing on the parameter model, wherein the parameter model is characterized by using grids;

and synthesizing the grid model and the parameter model into a hybrid model based on Boolean operation, wherein the hybrid model is characterized by using a grid.

2. The grid-parameter hybrid model modeling method according to claim 1,

obtaining the mesh surface by using an improved greedy projection triangulation method;

the improved greedy projection triangularization method comprises the following steps:

smoothing the point cloud data by using a moving least square method to obtain an MLS fitting curved surface;

based on the MLS fitting curved surface, point cloud normal vectors of all the point cloud data are obtained;

and based on the point cloud method vector, reconstructing by using a greedy projection triangulation method to obtain the mesh curved surface.

3. The grid-parameter hybrid model modeling method according to claim 1,

the grid offset processing method comprises the following steps:

establishing a new weight factor lambda based on the influence of the shape, the centroid distance and the angle of the vertex angle of the triangle on the vertex normal vector;

setting boundary vertex v_iThe left and right sides of the frame have n continuous boundary vertices, namely, a left boundary vertex (v)_lI-1, i-2,.., i-n) and a right boundary vertex (v)_rR ═ i +1, i + 2.., i + n), passing through the boundary vertex v on both sides of the boundary vertex_iRespectively connected with the left boundary vertex and the right boundary vertex to respectively obtain n vectors which are respectively marked as left vectors (e)_i,lI-1, i-2, a_i,r,r＝i+1,i+2,...,i+n)；

Calculating a left vector e based on the left vector and the right vector_lAnd the right vector e_r；

Based on the left vector e_lAnd stationThe right vector e_rEstablishing a correction vector N_e；

Respectively the boundary vertex v_iOf the initial normal vector N_vAnd the correction vector N_eAssigning boundary vertex weights k₁And the correction vector weight k₂Based on said initial normal vector N_vThe correction vector N_eThe boundary vertex weight k₁And the correction vector weight k₂Calculating a corrected boundary vertex normal vector N_b；

Based on the new weight factor λ, the left vector e_lThe right vector e_rAnd said boundary vertex normal vector N_bObtaining the boundary vertex v_iAnd (4) correcting the normal vector to finish the grid bias processing.

4. The grid-parameter hybrid model modeling method according to claim 3,

the method for border stitch processing includes:

after each vertex of the mesh curved surface is offset along a vertex normal vector, a mesh offset curved surface is obtained;

establishing a stitching curved surface between the mesh curved surface and the mesh offset curved surface, wherein the stitching curved surface is a set of discrete triangular surface patches;

and optimizing the triangular surface patch by using a labeling algorithm, sequentially generating new triangular surface patches, inserting the new triangular surface patches between the mesh curved surface and the mesh offset curved surface, and finishing the boundary stitching of the mesh curved surface and the mesh offset curved surface.

5. The grid-parameter hybrid model modeling method according to claim 1,

the Boolean operation method comprises the following steps:

detecting triangular mesh patches which are crossed between the mesh model and the parameter model;

local regridding is carried out on the triangular mesh patch area which generates the intersection and the mesh of the neighborhood thereof, so as to realize the adjustment of the mesh density of the intersection area;

detecting the triangular mesh patch generating the intersection again, deleting the triangular mesh patch from the mesh, and dividing the mesh model with the intersection area deleted into different mesh patches;

recombining the grid patches based on Boolean operation and internal and external distribution of the grid patches, wherein the combined model is a grid patch with gaps;

and extracting boundary side rings of the grid with gaps based on the recombined grid patches, establishing a corresponding relation of the boundary side rings in a voting mode, and connecting the corresponding boundary side rings by an iterative forward stitching method to generate a grid-parameter mixed model.

6. The grid-parameter hybrid model modeling method according to claim 5,

the judgment method for the intersection of the triangular mesh patches comprises the following steps:

dividing the octree with the number of given points and the space size for the grid model and the parameter model by adopting an octree method to obtain a grid octree and a parameter octree respectively;

detecting whether all leaf nodes corresponding to the grid octree and the parameter octree are crossed in space, and if so, performing traversal crossing detection on all ring-adjacent faces of the vertexes in the corresponding leaf nodes.

7. The grid-parameter hybrid model modeling method according to claim 5,

the method for adjusting the grid density of the cross region comprises the following steps:

setting the vertex control side length of the crossed triangular mesh patch as a given side length, carrying out curvature self-adaptive control side length calculation on the neighborhood of the triangle patch, then carrying out weighting smoothing on the mesh control side length of the whole area, after calculating the control side length, re-gridding the local mesh by using a local topology adjustment method, and finishing adjustment of the mesh density of the crossed area.

8. The grid-parameter hybrid model modeling method according to claim 5,

the method for recombining the grid patches comprises the following steps:

according to Boolean operation, firstly, carrying out internal and external judgment on a grid patch, wherein the internal and external judgment of the grid patch is judged according to the calculation of the number of three-dimensional windings;

and selecting the nearest boundary ring corresponding to each vertex on the boundary ring by using a voting mode, and determining the corresponding relation of the boundary rings to be stitched if the vertexes in the boundary rings corresponding to the vertexes are voted the same, i.

9. A grid-parameter mixed model modeling system is characterized by comprising a point cloud data module, a grid model module, a parameter model module and a Boolean operation module;

the point cloud data module is used for acquiring point cloud data of an object to be detected;

the mesh model module is used for converting the point cloud data into a mesh curved surface by using a mesh generation technology, carrying out mesh offset processing and boundary stitching processing on the mesh curved surface, and converting the mesh curved surface into a closed mesh model;

the parameter model module is used for setting characteristic parameters of the object to be measured, establishing a parameter model based on the characteristic parameters, and carrying out gridding processing on the parameter model, wherein the parameter model is characterized by grids;

the Boolean operation module is used for synthesizing the grid model and the parameter model into a mixed model based on Boolean operation, and the mixed model is characterized by using grids.

10. The grid-parameter hybrid model modeling system of claim 9,

the Boolean operation module comprises a cross detection unit, a grid density adjustment unit, a grid patch unit and a stitching unit:

the intersection detection unit is used for detecting a triangular mesh patch which is intersected between the mesh model and the parameter model;

the mesh density adjusting unit is used for carrying out local regridding on a triangular mesh patch area which generates intersection and a mesh in a neighborhood thereof so as to realize adjustment of mesh density of the intersection area;

the grid patch unit is used for detecting a triangular grid patch generating intersection again, deleting the triangular grid patch from the grid, dividing a grid model with an intersection area deleted into different grid patches, recombining the grid patches based on Boolean operation and internal and external distribution of the grid patches, and obtaining a combined model which is a grid patch with gaps;

the stitching unit is used for extracting boundary edge rings of the grid with gaps based on the recombined grid patches, establishing a corresponding relation of the boundary edge rings in a voting mode, connecting the corresponding boundary edge rings by an iterative forward stitching method, and generating a grid-parameter mixed model.

Images