CN108876834A - The curved surface sample normal direction transmission method of multilayer Riemann's constraint diagram - Google Patents

Abstract

The purpose of the present invention is to provide a method for normal propagation of surface samples applicable to multi-layer Riemann graph constraints of massive complex sampling point set data, which belongs to the field of product reverse engineering. Multi-layer partitioning to construct multi-resolution models of surface samples. Then, a Riemann diagram is constructed for the nodes of the model, forming a multi-layer Riemann diagram. Finally, combined with preorder traversal and MST algorithm, a top-down strategy is adopted to realize the propagation of normal vectors in multi-layer Riemann graphs. Experimental results show that for large-scale physical surface samples, the algorithm can improve the accuracy of normal uniformity, and the computational efficiency and memory utilization are significantly improved.

Description

Surface Sample Normal Propagation Method Constrained by Multilayer Riemann Diagram

technical field

The invention provides a method for normal propagation of curved surface samples constrained by multi-layer Riemann graphs, which is suitable for massive complex curved surface samples and belongs to the field of product reverse engineering.

Background technique

The normal estimation of surface samples is an important problem in the surface reconstruction process. For the approximation or interpolation reconstruction of surface samples, the correctness of the reconstruction results and the computational efficiency of the reconstruction process all depend on the correct estimation results of the normal direction of the samples. For any sample point on the surface, the normal direction can be estimated based on the approximation of the local shape of the surface reflected by the position information of the sample point and its adjacent sample points. The normal direction of the sample points obtained by normal direction estimation is ambiguous, that is, the normal direction of any sample point may be opposite to that of its adjacent sample points. This problem is the core problem in the research of surface reconstruction and has been paid much attention for a long time.

The existing methods for unifying the normal direction of surface samples are mainly divided into solid method and surface method. The solid method is to divide the surface sample into several subsets, and determine the normal direction of the sample point by judging the inner and outer surfaces of the model. However, this method relies on the visibility judgment of the sampling point and the calculation cost of the surface sample segmentation process is too high, so it is not suitable for complex surface structures. Massive Data. The surface method was first proposed by Hoppe et al. This method assumes that the sampling surface is smooth everywhere. On this basis, a Riemann diagram is constructed for the surface sample, and the edges of the undirected graph are constructed with 1-|n _i n _j | as the weight function , realize the propagation of sample normal vector by traversing the minimum spanning tree. However, this method is very prone to failure in areas with large curvature changes such as sharp, thin walls, and near walls. On the basis of the algorithm proposed by Hoppe, Kong et al. used the smoothness of the Hermite surface of local surface samples as the basis for judging the priority of normal propagation, which is suitable for the propagation of normal vectors in characteristic areas such as thin walls and near walls. Lee et al. used the Laplace-Beltrami algorithm of point clouds as the weight function, which effectively improved the accuracy of normal vector propagation in sharp feature regions. Wang Xingce et al. added tangential constraints on the basis of the weight function to ensure that the normal propagates along the tangential direction of the surface, effectively improving the accuracy of the normal vector propagation at the adjacent surface. Liu et al. realized the normal propagation of sample points by combining automatic and interactive manual selection of multiple propagation source points, which effectively improved the correctness of normal consistency.

Contents of the invention

In order to improve the situation that the existing point cloud normal estimation method is not applicable to a large number of complex surface samples, the purpose of the present invention is to propose a multi-layer Riemann graph-constrained normal propagation method. This method can take into account the propagation efficiency and accuracy of the normal direction among a large number of complex surface samples, and its implementation scheme is as follows:

A normal propagation method constrained by a multi-layer Riemann graph, characterized in that the steps are as follows: (1) constructing a k-d tree for a surface sample P, and initializing the state of the sample point in P as a free point; (2) for P Construct a multi-resolution model T(P); (3) Use a top-down strategy to traverse the nodes of each layer of the surface sample multi-resolution model T(P), and construct a Riemannian model for the subset contained in each node Figure, the multi-layer Riemann graph RG(P) that constitutes P; (4) Perform normal propagation on surface samples based on the multi-layer Riemann graph.

In order to realize the purpose of the invention, the normal propagation method of the described multi-layer Riemann diagram constraint, in step (2), the structure of the point cloud multi-resolution model T is: (1) each node of T stores the One sample point, and the sample points stored by any two nodes in the same layer are different; (2) The sample point stored by any node T is a point composed of the sample points stored in the sub-nodes of T in P The nearest sample point of the mean point of the set; (3) The root node does not store sample points.

In order to realize the purpose of the invention, the normal propagation method of the described multi-layer Riemann graph constraint, in step (2), the tree structure of the point cloud multi-resolution model T (P) starts from the leaf layer node and builds up layer by layer , if the leaf nodes are set as the first layer nodes of the tree, and each node stores a sample point in the point cloud P, then the construction method of i>1 layer non-root nodes includes the following process in turn: (1) Divide the i-1th layer node of T(P) into the set {O _j ^i-1 }, j=1,2,...,n _i-1 ,n _i-1 where the intersection of any two elements is empty >1; (2) Construct node T ⁱ _j in the i-th layer of T(P); (3) Extract sample points contained in each node in O _j ^i-1 to form point set P _j ^i-1 ; ( 4) Calculate the mean point c _j ^{i-1 of P j i-1} _; ⁽ 5) Select the sample point x closest to c _j ^i-1 from P _j ^i-1 ; (6) Store x in T ⁱ _j , and take all the nodes in O _j ^i-1 as the child nodes of T ⁱ _j .

In order to realize the purpose of the invention, in the described point cloud multi-resolution model construction step (1), the i-1th layer node of T(P) is divided into the process of set {O _j ^i-1 } which comprises the following steps in turn: (1) Construct a kd tree ψ for the sample points contained in the i-1th layer node of T(P), and establish a one-to-one correspondence between the sample points in ψ and the i-1th layer node of T(P) (2) Let the set O be an empty set, for any node T _j ^i-1 in the i-1th layer node of T(P), the k>1 neighbor query method based on ψ can obtain the distance T _j ⁱ The set λ _j ^i-1 composed of the nearest k sample points of the sample points contained in ^-1 , let the ^i- 1th layer nodes of T(P) corresponding to each sample point in λ _j i-1 form a set O _j ^{i -1} , if any node in O _j ^i-1 does not appear in O, store O _j ^i-1 as an element in O; (3) For the set O obtained in step (2) ={O _j ^i-1 }, extract the sample points contained in each node in O _j ^i-1 , form a point set P _j , calculate the mean point c _j of P _j , form the mean point set {c _j }, and establish The one-to-one correspondence between {c _j } and each node set in O; (4) Let the i-1th layer nodes of T(P) not belonging to O constitute a set U _i-1 , for U _i-1 For any sample point u _j , select the mean point c _min closest to the sample points included in u _j from {c _j }, and store u _j into the node set corresponding to c _min in O.

In order to achieve the purpose of the invention, the multi-layer Riemann diagram constraint is not a forward propagation method. In step (2), the construction process of the root node of the multi-resolution model is to approach P _j with the spline surface S _j ^{i-1 i-1} , estimate the Gaussian curvature value C(x) of sample point x based on S _j ^i-1 , if C(x) is greater than the preset curvature threshold ε, the construction process of T(P) is terminated, and the i-th layer is deleted All the nodes in the i+1th layer are constructed as the root node of T(P), and the i-th layer nodes of T(P) are used as the child nodes of the root node.

In order to realize the purpose of the invention, the non-normal propagation method of the multi-layer Riemann graph constraint, in step (4), the process of carrying out normal propagation to the surface sample based on the multi-layer Riemann graph is, to the multi-layer Riemann graph node Perform preorder traversal, take the current traversal node as the Riemann graph, and assign the weight of the edge in the Riemann graph to w=1-|n _i n _j |, n _i and n _j respectively represent the Riemann graph For the normal vector corresponding to the end point of the edge (p _i , p _j ), use the Prim algorithm to calculate the minimum spanning tree of the Riemann diagram, use the associated vertex of the Riemann diagram as the starting point, and use the direction of the normal vector of this point as the reference method Propagate the normal vector to traverse the minimum spanning tree of the Riemann graph. If n _i ·n _j =-1, then perform normal vector flipping, and the traversal ends, that is, the process of normal vector propagation is completed.

Compared with the prior art, the present invention has the following advantages:

(1) The point cloud multi-resolution model construction method based on cluster analysis and curvature deviation control realizes a hierarchical simplified model of mass complex shape point clouds from bottom to top, and divides and conquers the normal propagation area of samples in terms of data structure Processing lays the groundwork.

(2) Based on the point cloud multi-resolution model, the construction method of the multi-layer Riemann diagram and the propagation method of the normal direction of the sample points in the multi-layer Riemann diagram are proposed, which effectively improves the calculation efficiency of the unified process of the normal direction of massive complex shape point clouds with accuracy.

(3) In the normal propagation process, the nodes of the multi-layer Riemann graph are respectively propagated in the normal direction, which reduces the time complexity and improves the efficiency of the normal propagation; and releases the memory in real time, improving the utilization of the memory The rate increases the throughput of the algorithm and is suitable for the processing of massive data.

Description of drawings

Fig. 1 is the program flow diagram of the normal propagation method of multilayer Riemann graph constraint of the present invention;

Figure 2 is a schematic diagram of the construction of a multi-layer Riemann diagram;

Fig. 3 is a schematic diagram of normal direction unification;

Fig. 4 is sampling data in embodiment one;

Fig. 5 is a schematic diagram of sampling data normal direction estimation in Embodiment 1;

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Fig. 1 is a flow chart of the program implementation of the normal propagation method constrained by the multi-layer Riemann diagram of the present invention, which can be realized by using the C programming language. The main modules of the program for the normal propagation method constrained by multi-layer Riemann diagrams include the construction of multi-resolution models for sample points on the surface of objects, the construction of multi-layer Riemann diagrams, and the normal propagation based on multi-layer Riemann diagrams.

The multi-resolution model is a tree structure that starts from the leaf layer node and builds up layer by layer. If the leaf node is set as the first layer node of the tree, and each node stores a sample point in the point cloud P, then the i-th The construction method of non-root nodes >1 layer includes the following processes in turn. The main steps of the construction process are: (1) Initialize i←1 and set the threshold ε; The point is divided into the set {O _j ^i-1 },j=1,2,…,n _i-1 , where the intersection of any two elements is empty, and n _i-1 >1;(3)j←1; (4 ) Construct node T ⁱ _j in the i-th layer of T(P); (5) Extract the sample points contained in each node in O _j ^i-1 to form a point set P _j ^i-1 ; (4) Calculate P _j The mean point c _j i- ¹ of ^i-1 ; (5) select the sample point x closest to c _j ^i-1 from P _j ^i-1 ; (6) calculate the x Gaussian curvature value C(x); (7 ) If C(x) is greater than the preset curvature threshold ε, execute step (11); (8) store x in T ⁱ _j , and set all nodes in O _j ^i-1 as children of T ⁱ _j node; (9) if i<n _i-1 , then i←i+1, execute step (2); (10) j←j+1; (11) repeat (3)-(10); (11 ) Delete all the nodes in the i-th layer, construct a node in the i+1-th layer as the root node of T(P), and obtain the multi-resolution model T(P).

In the above step (2), the specific steps of dividing the i-1th layer node of T(P) into the set {O _j ^i-1 } whose intersection of any two elements is empty are: (1) Initialize O, C is an empty set; (2) Construct a kd tree ψ for the sample points contained in the i-1th layer node of T(P), and construct the kd tree ψ for the sample points in ψ and the i-1th layer node of T(P) (3) j←1 (4) Based on ψ query the sample point neighbor set λ _j i- ¹ contained in T _j ^i-1 ; (5) at the i-1th of T(P) In the layer nodes, search for the nodes corresponding to each sample point in λ _j ^i-1 to form a set O _j ^i-1 (6) If O exists in the node in O _j ^i-1 , perform step (9); (7) O←O∪O _j ^i-1 ; (8) Extract the sample points contained in each node in O _j ^i-1 to form a point set P _j , and calculate the mean point c _{j of P j (} 9)C←C∪c _j , and establish a one-to-one correspondence between elements in C and each node set in O; (9) j←j+1; (10) repeat (2)-(9); (11) set T that does not belong to O The i-1th layer nodes of (P) form a set U _i-1 , for any sample point u _j in U _i-1 , select the mean point c _min closest to the sample point contained in u _j from C, and set Store u _j into the node set corresponding to c _min in O; (12) Get the set {O _j ^i-1 } where the intersection of any two elements is empty.

Fig. 2 is a schematic diagram of constructing a multi-layer Riemann diagram based on a multi-resolution model of surface samples. After obtaining the multi-resolution model of the surface sample, traverse the nodes of each layer in the model from top to bottom, construct a Riemann diagram for the subset contained in each node, and select this node as the Riemann diagram associated vertices.

In the process of constructing the Riemann diagram, the minimum spanning tree algorithm is simplified as: within the range of the k neighborhood of the vertex v, the Riemann diagram is constructed by using the Euclidean distance between the vertices as the weight of the edge, but this The Riemann diagram constructed by this method tends to generate a large number of redundant edges. In order to ensure that there are no redundant edges in the Riemann graph, the uniqueness of each edge needs to be verified, that is, if there are two edges between two vertices, one edge must be a redundant edge. To do this, traverse each edge in the Riemann graph, and if e _i,j , e _j,i exist, delete one of them. With the advancement of the subdivision level in the multi-layer Riemann diagram, the expression of the original data set is more detailed. The top Riemann diagram covers the entire model, and the lower Riemann diagram is a detailed description of the nodes in the top Riemann diagram, and the larger the number of layers, the more accurate the local surface details reflected by the Riemann diagram, as shown in Figure 2 , where samples of different sizes represent samples located in different levels of the Riemann diagram.

In order to ensure that the direction of the normal vector is consistent with the direction of the normal vector of the upper node, a top-down method can be used to realize the normal propagation between the Riemann diagrams, that is, starting from the root node, traversing the nodes of the multi-layer Riemann diagram in turn Implements normal propagation of surface samples. The preorder traversal algorithm can better solve the node traversal problem. First, input a multi-layer Riemann diagram, and use the root node as the current node, perform access operations on the current node during the traversal process, and then access the child nodes of the current node in turn. This process is iteratively performed until all nodes have been visited.

The access to each node in the multi-layer Riemann graph is the unification of the normal vectors of the Riemann graph. For each Riemann graph, the following normal propagation method is given: (1) Assign the weight of the edge of the Riemann graph to w=1-| _{n i n j} | The normal vector corresponding to the endpoint of the edge (p _i ,p _j ) in the Mann graph. (2) Use the Prim algorithm to calculate the minimum spanning tree of the Riemann diagram. (3) The associated vertex of the Riemann diagram is used as a starting point, and the direction of the normal vector of the point is used as a reference to traverse the minimum spanning tree of the Riemann diagram and propagate the normal vector. If n _i ·n _j =-1, perform normal flipping.

Let λ(p) be the set of neighboring sample points of p∈P, and take the sample points in λ(p) as control points, then set the bicubic Bézier surface approximation function as:

m=n=3, The cubic Bézier surface can be calculated based on local samples, and the curvature of p is calculated using the Gaussian curvature formula as:

In the formula, n represents the normal vector of the sample point p, Su and S _v are the first _- order partial derivatives of the parametric surface fitted based on λ(p), and S _uv , _Suuu and S _vv are the second-order partial derivatives. Error control can be realized based on the Gaussian curvature of the sample point p. If c(p)>ε, ε is the error control threshold, the construction process of the multi-resolution model will be terminated.

Embodiment 1: apply the method described herein to unify the normal direction of the sampled data, wherein the normal direction is calculated by the PCA algorithm. The model has a large scale and complex structure, including sharp features, transition surfaces and other complex geometric feature areas, which can be used as model data to verify the effectiveness of the method described in this paper. By observing Figure 4, it can be seen that the method in this paper can correctly realize the normal unification of sharp features and transitional surface regions.

The above is only a preferred embodiment of the present invention, and is not intended to limit the present invention to other forms. Any skilled person who is familiar with this profession may use the technical content explained above to change or remodel it into an equivalent change. Example. But everything does not depart from the content of the technical solution of the present invention, and any simple modification, equivalent change and modification made to the above embodiments according to the technical essence of the present invention still belong to the protection scope of the technical solution of the present invention.

Claims (7)

1. a kind of curved surface sample normal direction transmission method of multilayer Riemann constraint diagram, it is characterised in that step is followed successively by：It (1) is curved surface Sample P constructs kd tree, and is free point by the sampling point state initialization in P；(2) multi-resolution models T (P) is constructed for P；(3) Using each layer node of top-down strategy traversal curved surface sample multi-resolution models, the subset structure for including by each node Riemann's figure is made, the multilayer Riemann for constituting P schemes RG (P)；(4) normal direction propagation is carried out to curved surface sample based on multilayer Riemann figure.

2. the multi-resolution models T (P) as described in step (2) in claim 1, it is characterised in that：(1) each node of T (P) A sampling point in P is stored, and the sampling point that same layer any two node is stored is different；(2) any one node T is stored Sampling point is the nearest sampling point of the average point for the point set that the sampling point stored in child node in P away from T is constituted；(3) root node is not deposited Sample storage point.

3. point cloud multi-resolution models T (P) as described in claim 2, it is characterised in that：Tree is opened from leaf layer node Begin successively building upwards, if setting the 1st layer of node that leaf node is tree, a sampling point in each node storage cloud P, then i-th> The building method of 1 layer of non-root node successively includes following procedure：(1) (i-1)-th layer of node of T (P) is divided into any two member The intersection of element is empty set { O_j ^i-1, j=1,2 ..., n_i-1, n_i-1>1；(2) in i-th layer of structural knot of T (P)(3) it mentions Take O_j ^i-1In each node sampling point for including, form point set P_j ^i-1；(4) P is calculated_j ^i-1Average point c_j ^i-1；(5) from P_j ^i-1Middle selection Away from c_j ^i-1Nearest sampling point x；(6) x is stored in Tⁱ _j, and by O_j ^i-1In node whole conductChild node.

4. point cloud multi-resolution models T (P) as described in claim 2, it is characterised in that：If the construction process of T (P) is i>1 layer of termination then constructs root node of the node as T (P) in i+1 layer, and using i-th layer of node of T (P) as root knot The child node of point.

5. putting the building method of i-th layer of node in cloud multi-resolution models T (P) as described in claim 3, feature exists In：(i-1)-th layer of node of T (P) is divided into set { O in step (1)_j ^i-1Process successively comprise the steps of：It (1) is T (P) sampling point that (i-1)-th layer of node is included constructs k-d tree ψ, and (i-1)-th layer of node for sampling point and T (P) in ψ establishes one One corresponding relationship；(2) set O is set as empty set, for any node T in (i-1)-th layer of node of T (P)_j ^i-1, the k based on ψ>1 is close Adjacent querying method is obtained away from T_j ^i-1The set λ that k nearest sampling point of the sampling point for being included is constituted_j ^i-1If λ_j ^i-1In each sampling point institute (i-1)-th layer of node of corresponding T (P) constitutes set O_j ^i-1If O_j ^i-1In any node do not occur in O, then by Φ_j ^i-1Make O is stored in for element；(3) set O={ O obtained for step (2)_j ^i-1, extract O_j ^i-1In each node sampling point for including, Form point set P_j, calculate P_jAverage point c_j, form mean value point set { c_j, and establish { c_jWith O in each node set one by one Corresponding relationship；(4) the (i-1)-th layer of node composition set U for being not belonging to the T (P) of O is set_i-1, for U_i-1In any sampling point u_j, from { c_j} Middle selection is away from u_jThe nearest average point c of the sampling point for being included_min, by u_jIt is stored in c_minThe corresponding node set in O.

6. point cloud multi-resolution models T (P) i-th as claimed in claim 3>The building method of 1 layer of non-root node, feature exist In：With spline surface S_j ^i-1Approach P_j ^i-1, it is based on S_j ^i-1The Gaussian curvature value C (x) for the sampling point x that estimating step (5) obtains, if C (x) it is greater than preset curvature threshold ε, then terminates the construction process of T (P), i-th layer of whole nodes is deleted, with claim 4 institute It states method and constructs root node at i-th layer for T (P).

7. the normal direction transmission method of multilayer Riemann constraint diagram as described in claim 1, it is characterised in that in step (4)：To more Layer Riemann's figure node carries out preorder traversal, is Riemann's figure with current traversing nodes, the weight on the side in Riemann's figure is assigned to w=1- |n_i·n_j|, n_i、n_jRespectively indicate side (p in Riemann's figure_i,p_j) the corresponding normal vector of endpoint, utilize Prim algorithm calculate Riemann The minimum spanning tree of figure, using the incident vertex of Riemann's figure as starting point, and being oriented with reference to normal direction with the normal vector It traverses Riemann and schemes the propagation that minimum spanning tree carries out normal vector, if n_i·n_j=-1 then carries out normal direction overturning, and traversal terminates, i.e., complete Normal communication process.