CN106981095B - A kind of improved smooth free-form deformation - Google Patents

Abstract

The invention discloses an improved smooth free deformation algorithm, belonging to the technical field of computer image processing. The algorithm includes a triangular uniform division step. In the triangular uniform division step, by using equal segment length control parameters, the division generates The side length of the sub-triangle is close to the control parameter of equal segment length, which effectively avoids the generation of narrow and long triangles or degenerate triangles, making smooth free deformation more robust and efficient.

Description

An Improved Smooth Free Deformation Method

technical field

The invention relates to the technical field of computer image processing, in particular to an improved smooth free deformation algorithm.

Background technique

In geometric modeling and computer animation, spatial deformation is one of the key technologies for geometric shape editing and flexible body animation generation. Among them, the most representative is free deformation technology (FFD), which has developed many variants, such as precise Free deformation methods, smooth free deformation methods, etc., have been integrated into commercial software such as 3DS Max, Maya, Softimage XSI, etc. due to their ease of use and powerful functions.

Because the deformation of the traditional free deformation method acts on the sampling points of the model to be edited, and then restores the deformation results of the model from the deformed positions of the sampling points, resulting in aliasing due to the too small density of sampling points during the deformation process. question.

In order to solve the aliasing problem, the density of sampling points is usually increased, but it will cause a large performance overhead; a further method is to adaptively determine the sampling density according to the patch size and the curvature of the surface, although the performance overhead is reduced, but the The adaptation algorithm is relatively complex to implement and cannot handle some singular cases well.

As a method to solve the aliasing problem in FFD, precise free deformation is to cut the initial triangular patch along the node box, calculate the deformed position of a sufficient number of sampling points on the triangular patch, and then use sampling point interpolation to calculate the original triangular patch after deformation. exact results.

The smooth free deformation method improves upon the exact free deformation method in the following six steps:

(1) Define the deformation space step

Select the B-spline body as the deformation space, denoted as R(μ,ν,ω):

in, represents m _μ ×m _ν ×m _ω control vertices, is the B-spline basis function.

Then use the deformation space to wrap the model to be deformed.

(2) Triangulation steps

Split the initial triangular patch by node boxes on the B-spline body.

(3) Model embedding step

In this step, the embedding process is the process of calculating the parameter coordinates of the model to be deformed in the deformation space. Specifically, the sampling point is mapped from the world coordinate system to the deformation space through the embedding function U=E(X), where X is the sampling point in the deformation space. The coordinates in the world coordinate system, U is the parameter coordinates of the sampling point in the deformation space.

The embedding function E is determined by the deformation space. In smooth free deformation, the B-spline body is usually constructed by a certain method, so that the parameter coordinates of the point in the embedded deformation space are equal to the coordinates of the point in the world coordinate system, that is, E(X) =X to simplify calculations during embedding.

Usually, cubic Bezier surfaces are used to fit accurate deformation results. Since each triangle generated by cutting will obtain a triangular Bezier surface after deformation, sampling should be performed on each triangle generated by cutting. , a total of 3 × 3 constraint points and m (m is determined by the number of deformation space) fitting points are required, that is, a total of 9+m sampling points are required for smooth free deformation.

Then use E(X)=X to calculate the parameter coordinates of the sampling point in the deformation space, and at the same time calculate the normal direction of the sampling point through the barycentric coordinate interpolation.

(4) Geometric deformation steps

The geometric deformation process is a process of changing the deformation space and transferring the deformation to the to-be-deformed model. Specifically, the sampling points are embedded in the B-spline body to transmit the deformation of the deformation space to the to-be-deformed model through these sampling points. When the user changes the position of the control vertex of the B-spline body, first substitute the parameter coordinates of the sampling point and the position of the control vertex into the formula used to define the deformation space to obtain the deformed position of the sampling point; then use these new positions As input, the control vertices of the triangular Bezier surface as the deformation result are obtained by a fitting method with constraints.

(5) Normal deformation step

In order to solve the problem that the result is not smooth and natural in the precise free deformation, the normal direction of the sampling point is estimated by the barycentric coordinate interpolation, and then the value of the normal vector of the sampling point after deformation is calculated; then, using the same method as in the geometric deformation step, Taking the deformed normal vector of the sampling point as the input, the normal vector field of the deformed triangular surface patch is fitted by the cubic Bezier surface patch. In the subdivision stage, the normal vector field is subdivided at the same time, and the normal vector field is used as the normal direction of the subdivided triangle, so that visually G ¹ continuous geometry and G ⁰ continuous normal vector field can be obtained on both sides of the smooth edge; Side G ⁰ continuous geometry and G ^-1 continuous normal vector field.

(6) Geometry fine-tuning steps

In order to obtain visually more delicate deformation results, it is also necessary to fine-tune the control vertices of the triangular Bezier patches representing the geometry according to the normal information.

(7) Subdivision drawing steps

Paint after subdividing the results from the normal deformation step and the geometry fine-tuning step.

After the processing of the above seven steps, by applying CUDA to the precise free deformation, it can not only achieve a calculation speed about 50 times faster than the precise free deformation method, but also improve the visual aesthetics of the deformation results. However, in the step of uniform triangulation, it cuts triangles along the node box, which has the following problems: (1) It is easy to cut out long and narrow triangles and degenerate triangles, which not only wastes computing resources, but may also cause floating-point calculation errors, resulting in The running speed of the program becomes slower, and the robustness becomes worse; (2) Usually, the smaller the triangle produced by cutting, the smaller the error after deformation, but in this step, the size of the cut triangle is determined by the distribution of node boxes and the distribution of model triangles. It is decided that it is difficult for the user to control the cutting results, that is, the size of the error after the model is deformed cannot be controlled.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide an improved smooth free deformation algorithm to solve the problems existing in the triangulation step in the existing smooth free deformation algorithm, so as to make the smooth free deformation more robust and efficient.

In order to achieve the above purpose, the smooth free deformation algorithm provided by the present invention includes the step of triangulation uniform division; the triangular uniform division step includes:

Step 1, obtain the initial triangular patch;

Step 2, according to the equal segment length control parameter, equally divide both sides of the minimum interior angle of the initial triangular facet;

Step 3, connect the two equal points adjacent to the vertex of the smallest interior angle to form the top triangle and the quadrilateral to be divided;

Step 4, taking the common endpoint of the quadrilateral to be divided and the top triangle as the starting point, correspondingly connecting the equal points on the quadrilateral to be divided, and dividing it into several trapezoid-like shapes;

Step 5: According to the equal segment length control parameter, divide the top and bottom edges of the trapezoid into equal parts, and connect the equal points to triangulate the trapezoid; if the number of equal parts on both sides of the minimum interior angle is not equal, repeat Steps 4 and 5: Triangulate the quadrilateral to be triangulated with the trapezoid that is farthest away from the vertex of the smallest interior angle, and start from the vertex located on the side with less equal points of the smallest interior angle.

In the above step of uniform triangulation, the equal segment length control parameters are used to make the side lengths of the sub-triangles generated by cutting close to the equal segment length control parameters, that is, the sub-triangles generated by segmentation are closer to regular triangles, which effectively avoids narrow and long triangles. Or the generation of degenerate triangles, making the smooth free deformation process more robust and efficient.

A specific solution is that the steps of dividing the sides equally according to the equal-segment length control parameter include: dividing the sides equally according to the equal-segment number, and the equal-segment number is the upward direction of the quotient of the edge length and the equal-segment length control parameter. Round value. The algorithm is simple.

Another specific solution is that step 2 includes: receiving the setting of the peer segment length control parameter. By receiving the setting of the user's peer-to-peer segment length control parameters, it is convenient for the user to control the size of the sub-triangles generated by the segmentation, so as to control the deformation error according to the requirements and the performance of the hardware.

Another specific solution is that step 2 includes: calculating the length of both sides of the minimum interior angle according to the vertex coordinates of the initial triangular facet; calculating the number of equal segments on both sides of the minimum interior angle, and the number of equal segments is the sum of the side length and the equal segment length control parameter. The quotient is rounded up; based on the coordinates of the endpoints on both sides, the coordinates of the bisection point are calculated.

In another specific solution, step 1 includes: reading the to-be-deformed model from a file; and triangulating the to-be-deformed model to form an initial triangular patch.

In another specific solution, step 2 includes: calculating the length of each side according to the vertex coordinates of the initial triangular patch, and the minimum interior angle is the interior angle opposite to the shortest side.

In another specific solution, the step of triangulating the trapezoid by connecting the bisectors includes: along the same connection direction, connecting the corresponding bisectors on the upper base and the lower base of the trapezoid to form a number of quadrilaterals, and connecting short diagonal lines. Divide the quadrilateral.

A preferred solution further includes step 6: using the CVT optimization method to optimize the subdivision result. It can make the segmentation result more uniform.

A further preferred solution is to perform 5 CVT optimizations on the segmentation results. Better balance optimization effect and computational overhead.

Compared with the existing method, the beneficial effects of the present invention are:

(1) The algorithm does not include plane intersection, which is more efficient and robust.

(2) The divided sub-triangles are close to equilateral triangles and their areas are close to the same, and no new elongated or degenerate triangles will be generated.

Description of drawings

Fig. 1 is the working flow chart of the embodiment of the present invention;

Fig. 2 is the working flow chart of triangular uniform dissection step in the embodiment of the present invention;

3 is a schematic diagram of part of the process of the triangular uniform division step in the embodiment of the present invention, wherein (a) is the initial triangular patch, (b) is the minimum interior angle of the initial triangular patch, and (c) is the two sides of the minimum interior angle. Divide into equal parts, (d) is the top triangle to be divided, (e) is the first trapezoid to be divided, and (f) is the equal division of the upper and lower bases of the first trapezoid.

4 is a schematic diagram of other parts of the process of the triangulation uniform division step in the embodiment of the present invention, (a) triangulates the first trapezoid, (b) triangulates the second trapezoid, ( c) is the last trapezoid to be triangulated, (d) is the partial triangulation of the last trapezoid, (e) is the triangulation result, and (f) is the CVT optimization of the triangulation result.

Detailed ways

The present invention will be further described below with reference to the embodiments and the accompanying drawings.

Example

Referring to FIG. 1, the improved smooth free deformation algorithm of the present invention includes a step S1 of defining a deformation space, a step S2 of triangular uniform division, a step S3 of model embedding, a step of geometric deformation S4, a step of normal deformation S5, a step of fine-tuning geometry S6 and subdivision rendering Step S7.

Defining the deformation space Step S1, defining a B-spline body as the deformation space wrapping the to-be-deformed model.

In step S2 of uniform triangulation, the initial triangular patch in the model to be deformed is divided into several sub-triangles by the uniform triangulation algorithm, so as to reduce the error after deformation.

Referring to FIG. 2 , the triangular uniform division step S2 includes an acquisition step S21 , an equalization step S22 , a connection equalization point step S23 , a quadrilateral division step S24 , a classified trapezoidal division step S25 , and an optimization step S26 .

Obtaining step S21, obtaining an initial triangular patch.

Read the model to be deformed from the file;

Triangulate the to-be-deformed model to form the initial triangular patch 1 as shown in Figure 3(a).

In step S22 of equal division, according to the equal division length control parameter 1, two sides of the minimum interior angle of the initial triangular facet are equally divided.

Receive the setting of the peer-to-peer segment length control parameter l, and the user sets the control parameter l through the input interface according to the initial triangular facet size and its accuracy requirements, so that the user can better control the deformation error.

As shown in Figure 3(b), according to the vertex coordinates of the initial triangular patch 1, calculate the lengths of its side 11, side 12 and side 13, and then use the sorting method to arrange the lengths of the three sides in ascending order. The angle α subtended by the side 13 is the smallest interior angle of the initial triangular patch 1 .

Calculate the length of side 11 and side 12 of the minimum interior angle; according to the equal-segment length control parameter 1, calculate the equal-segment number of side 11 and side 12, where the equal-segment number is the side length and equal-segment length control parameter l The rounded up value of the quotient of , that is, the number of equal segments of side 11 and side 12 are in is the length of side 11, is the length of side 12.

According to the coordinates of the endpoints of side 11 and side 12, calculate the coordinates of the bisector. For a specific side of the minimum interior angle, such as side 11, set the coordinates of its two endpoints to be P ₁ and P ₂ , then is the coordinates of each equal segment on side 11, where n is the number of equal segments, and t ranges from 0 to n. The two sides 11 and 12 of the smallest interior angle of the initial triangular patch 1 are equally divided, and the result is shown in Figure 3(c).

The step S23 of connecting the bisected points, referring to FIG. 3(d), connects two bisected points adjacent to the vertex of the smallest interior angle to form the top triangle 2 and the quadrilateral to be divided 3.

Step S24 of dividing the quadrilateral, as shown in FIG. 3(d), taking the common endpoint of the quadrilateral 3 to be divided and the top triangle 2 as the starting point, correspondingly connecting the equal points on the quadrilateral to be divided 3, and dividing it into several trapezoid-like shapes , the solid line part of Fig. 3(e) is the first trapezoid 31.

In step S25, the first class trapezoid 31 as shown in FIG. 3(e) is taken as an example, and the upper base and the lower base of the first class trapezoid 31 are equally divided according to the equal segment length control parameter 1. , the result is shown in Figure 3(f); along the same connection direction, such as from left to right in the figure, divide the quadrilateral formed by the corresponding connection points of the upper and lower bases with its short diagonals, the result As shown in Figure 4(a).

From top to bottom, triangulate each trapezoid in sequence. During the triangulation process, as shown in Figure 4(b), the second trapezoid 32 has an equal number of equal segments of the upper and lower bases, and is connected to The upper base and the lower base correspond to bisected points to form several quadrilaterals. Calculate the length of its two diagonals according to the four vertices of the quadrilateral, and divide the quadrilateral along the shorter diagonal, and finally make each quadrilateral Divide into two triangles.

As shown in Fig. 4(c), the number of upper and lower segments of the third trapezoid-like 33 is 1 less than that of the lower base, and the average points of the upper and lower bases are numbered, and the number of the upper base is 1 to k, the number of the lower base is from 1 to k+1 from left to right. On the third trapezoid 33, first connect the points with the same number of the upper and lower bases. In addition, for each point in the upper base, if its number is j, connect it to the point numbered j+1 in the lower base, and finally divide the third trapezoid 33 into multiple sawtooth shaped triangle.

If the number of equal points on both sides of the minimum interior angle is not equal, as shown in Fig. 4(c) and Fig. 4(d), repeat steps S24 and S25, and take the trapezoid 34 that is farthest from the vertex of the minimum interior angle as the quadrilateral to be divided Triangulates starting from vertices that lie on the edge with fewer points bisected by the smallest interior angle. Rotate the trapezoid 33 farthest from the vertex of the smallest interior angle by 90 degrees counterclockwise, so that this trapezoid 33 is similar to the quadrilateral 3 to be divided in Fig. The remaining part of the other side of the triangle constitutes a triangle, and the triangle is regarded as the original triangular patch as shown in Figure 3(a), and steps S22 to S25 are performed on it. In the division process, the initial triangular patch 1 It is divided as shown in Figure 4(d) until the triangular facet 1 is divided as shown in Figure 4(e).

In optimization step S26, as shown in Fig. 4(f), the CVT optimization method is used to optimize the initial triangular patch 1 subdivision result, and 5 CVT optimizations are performed on the result to make the sub-triangles more uniform. The CVT optimization method is the method introduced in DU Q, FABER V, GUNZBURGER M. CentroidalVoronoi tessellations: applications and algorithms[J].SIAM review,1999,41(4):637–676.

The model embedding step S3 is to embed the model into the deformation space, and calculate the parameter coordinates and normal directions in the deformation space of the sampling points of each triangular patch generated after the division.

In the geometric deformation step S4, the user changes the control vertex of the deformation space to deform the deformation space. Keep the parameter coordinates of the sampling point unchanged in the deformation space, calculate the new position of the sampling point in the world coordinate system, and use the constrained fitting method to calculate the deformed shape of each triangular patch according to the deformed sampling point. As a result, the result is represented by a triangular Bezier patch.

Normal deformation step S5: Calculate the new normal direction of the sampling point in the world coordinate system, and calculate the deformed normal vector of each triangular patch by the fitting method with constraints according to the normal direction of the deformed sampling point. field, the result is represented by a triangular Bezier patch.

The geometric fine-tuning step S6 is to adjust the control vertices of the triangular Bezier surface sheet obtained in the geometric deformation step S4 to make the deformation result more smooth and natural.

In the subdivision drawing step S7, the results in the normal deformation step S5 and the geometric fine-tuning step S6 are subdivided and drawn.

Claims (9)

1. An improved smooth free deformation method, comprising the step of defining deformation space, the step of triangulation uniform division, the step of model embedding, the step of geometric deformation, the step of normal deformation, the step of geometric fine-tuning and the step of subdivision drawing, characterized in that the The above triangulation steps are implemented on the GPU platform, including: Step 1, obtain the initial triangular patch; Step 2, according to the equal segment length control parameter, equally divide both sides of the minimum interior angle of the initial triangular facet; Step 3, connect the two equal points adjacent to the vertex of the smallest interior angle to form the top triangle and the quadrilateral to be divided; Step 4, taking the common endpoint of the quadrilateral to be divided and the top triangle as the starting point, correspondingly connecting the equal points on the quadrilateral to be divided, and dividing it into several trapezoid-like shapes; Step 5, according to the equal segment length control parameter, equally divide the upper base and lower base of the trapezoid, and connect the equal points to triangulate the trapezoid; if the number of equal points on both sides of the minimum interior angle is not equal, Then repeat steps 4 and 5, and triangulate the quadrilateral to be triangulated with the trapezoid that is farthest from the vertex of the smallest interior angle, and start from the vertex located on the side with fewer equal points of the smallest interior angle. 2. smooth free deformation method according to claim 1, is characterized in that, the step that the edge is equally divided according to the equal segment length control parameter comprises: The sides are equally divided according to the number of equal segments, and the number of equal segments is the upward rounded value of the quotient of the length of the side and the control parameter of the length of equal segments. 3. The smooth free deformation method according to claim 1, wherein the step 2 comprises: A setting for the equal segment length control parameter is received. 4. The smooth free deformation method according to claim 1, wherein the step 2 comprises: Calculate the lengths of both sides of the smallest interior angle according to the vertex coordinates of the initial triangular patch; Calculate the number of equal segments on both sides of the minimum interior angle, and the number of equal segments is the rounded-up value of the quotient of the side length and the control parameter of equal segment length; Based on the coordinates of the endpoints on both sides, calculate the coordinates of the bisection point. 5. The smooth free deformation method according to claim 1, wherein the step 1 comprises: Read the model to be deformed from the file; Triangulate the model to be deformed to form an initial triangular patch. 6. The smooth free deformation method according to claim 1, wherein the step 2 comprises: According to the vertex coordinates of the initial triangular patch, the length of each side is calculated, and the minimum interior angle is the interior angle opposite to the shortest side. 7. The smooth free deformation method according to claim 1, wherein the step of triangulating the trapezoid-like shape by connecting the bisected points comprises: Along the same connection direction, connect the corresponding bisected points of the trapezoid-like upper base and lower base to form several quadrilaterals, and connect short diagonal lines to divide the quadrilaterals. 8. The smooth free deformation method according to any one of claims 1 to 7, characterized in that, further comprising: Step 6, using the CVT optimization method to optimize the subdivision results. 9. smooth free deformation method according to claim 8, is characterized in that: Five CVT optimizations were performed on the dissection results.