The outbreak of the Russo-Ukrainian War profoundly changed the course of history. It is conceivable that in the future computer science will focus more on serving the real industry. In the fields of computer-aided design (CAD), computer-aided engineering (CAE) and computer-aided manufacturing (CAM), industrial software plays a decisive role. The underlying logic of industrial software is as follows: During the design process of various industrial products, people need to simulate them in order to discover defects and modify the design plan. The core of simulation is to use computers to solve various physical differential and integral equations to predict mechanical physical behaviors, such as distribution changes of electromagnetic fields, thermodynamic phenomena, stress and strain, fluid phenomena, etc. To solve partial differential equations on surfaces or entities with complex topology and geometry, the finite element method, finite volume method or isogeometric analysis method is usually used. These methods all rely strongly on the mesh generation of surface entities. Finite element method and finite volume method require unstructured triangulation, and can also be generated based on structured mesh (such as quadrilateral and hexahedral meshing) to further improve calculation accuracy. The isogeometric analysis method relies entirely on structured mesh generation. Therefore, the usual industrial software has three main functional modules: grid generation, differential equation solving and visualization. In practical applications, grid generation accounts for about 73% of the time cost and economic cost. It can be seen that grid generation is the core foundation of modern industrial software.
Although grid generation technology is crucial, compared with numerical partial differential equation solving and visualization technology, its maturity level is far lower than the other two, and many very basic theoretical issues remain unresolved for a long time. In all computer science, applied mathematics, mechanical mechanics and other departments, mathematical physics equations, numerical algebra, and numerical differential equations are basic courses, and computer graphics and visualization are also required courses in the computer department. Classic numerical methods have been accommodated by software such as Matlab and turned into simple instructions; traditional graphics rendering algorithms have also been solidified into GPU hardware and turned into simple function calls. However, few universities offer grid generation courses, and even if there are similar graduate courses, there are no textbooks that can cover a complete knowledge system, but rather an integration of sporadic algorithms. Although there is a huge demand in the industry, because this field has a long history, easy-to-solve problems have long been solved, and the remaining problems are too difficult. Real breakthroughs require relatively profound modern topological geometry theory. Whether it is learning theoretical knowledge or accumulating engineering, it takes ten years of sitting on the bench. For young scholars in the field of computer science, it is too risky to rush into research, so this field cannot become popular in the academic world.
The situation in industry is that of a semi-artisan workshop. Many of the world's top companies have relevant research departments that have been studying grid generation technology for decades; on the design front line, the company has specially trained senior engineers who are well versed in this technique to manually adjust the grid generated by the software through intuitive insights. This specialized technology has also been passed down from hand to ear and accumulated from generation to generation, but it still has not formed a complete theory and algorithm system. The difficulty of the problems that the industry has spent huge amounts of resources on for decades without solving them is conceivable, and there are definitely essential obstacles at the basic theoretical level, not at the engineering level.
After years of research and accumulation, our team has gradually realized that the basic theory of grid generation is not only closely connected with topology and Riemannian geometry, but also the more critical ideas come from conformal geometry and algebraic geometry (such as the representative theory of pure line bundles). Its theoretical basis, especially computational theory (such as discrete surface Ricci flow theory, 2018), has only matured in recent years. Below, we take surface mesh generation as an example to briefly introduce the recent progress in this area.
Surface triangulation
Traditional finite element methods focus on solving elliptic partial differential equations in the region of Euclidean space. For example, the area is triangulated, a function primitive is constructed for each cell, and the linear combination of the basis functions obtains the function space of the finite element. Transform partial differential equations using discrete or variational methods, and perform energy optimization in the finite element function space to obtain algebraic equations. Solve algebraic equations and obtain weak solutions. The triangulation is encrypted and a series of weak solutions are obtained. If the triangulation satisfies certain conditions, the series of weak solutions converges to a smooth solution. Here, the quality of triangulation is crucial, which is related to the convergence of weak solution sequences, the numerical stability of algebraic equations, etc. The quality of triangulation is mainly measured by two indicators, one is the shape of the triangle and the other is the size of the triangle. Usually we require the triangle to be as close as possible to an equilateral triangle, and the minimum angle has a strict positive lower bound; the sampling density of the triangle vertices is related to the calculation accuracy requirements. Classic computational geometry theory provides mature algorithms. For example, Chew's algorithm can ensure that the minimum angle of triangulation is greater than and the triangle size is uniform; Rupert's Delaunay Refinement algorithm ensures that the minimum angle is greater than and so on.
Figure 1. Rupert Delaunay Refinement algorithm for plane triangulation.
The essential difficulty of the problem lies in extending the planar algorithm to curved surfaces with complex topology and geometry. At this time, conformal geometry becomes the core theoretical tool to solve the problem. The more famous univaluation theorem states that any surface with a Riemannian metric can be conformally mapped to the unit sphere (mapped to a plane using spherical projection), the Euclidean plane and the hyperbolic plane, thus converting surface mesh generation into planar mesh generation. We first use the classic Delaunay Refinement algorithm to generate a high-quality plane mesh on a sphere, Euclidean plane or hyperbolic plane, and then map the plane mesh back to the curved surface. Because the mapping is conformal, the quality of the mesh on the curved surface is guaranteed.
Figure 2. Through conformal Riemannian mapping, surface triangulation is converted into plane triangulation.
So, how to calculate the singularization theorem becomes the key to surface mesh generation. At the same time, there is a potential trap here: the input surface of the discrete surface Ricci flow algorithm. The input surface on the computer is represented by a triangular mesh. Isn't this a circular argument? In order to generate a mesh, we need to input the mesh? In fact, the key to the problem is that our discrete Ricci flow theory [2] can ensure that the algorithm does not have any requirements for the triangulation of the input surface. No matter how poor the quality of the input mesh is, it will not affect the Ricci flow algorithm, so that the conformal transformation is mapped to the standard surface. High-quality triangulation on the standard surface results in high-quality triangulation on the initial surface. The calculation of the discrete surface Ricci flow here is not a direct extension of the traditional finite element method on the surface, but a novel method developed based on the principle of geometric variation, so it is not sensitive to the initial mesh quality. It can be seen that the key to the theory of unstructured mesh generation on general surfaces lies in the discrete singularization theorem and the surface Ricci theory [2].
Figure 3. Surface unitization calculated using Ricci method.
Structured quadrilateral mesh generation
In the field of computer-aided design (CAD), geometric surfaces are represented by piecewise rational polynomials, the so-called spline surfaces (NURBS, T-NURBS). Spline surfaces require structured quadrilateral meshing of the surface. On the other hand, structured quadrilateral meshing improves computational accuracy and is therefore in great demand in engineering applications. Structured quadrilateral mesh generation is more challenging than unstructured triangulation.
Over the years, academic circles have been trying to establish various theories and develop various algorithms to solve quadrilateral meshing. For example, there are many related papers in the fields of computer science, computational mathematics, computational mechanics, etc., and the most popular methods recently are based on Frame Field. In fact, from a theoretical perspective, the frame field depends on the differential structure and Riemannian metric structure of the surface, while quadrilateral meshing is fundamentally determined by the conformal structure of the surface. Therefore, the traditional frame field method does not reveal the essence of the problem and is more based on intuitive phenomenological analogy.
Figure 4. Quadrilateral mesh in the plane area, singular point configuration "one hair can affect the whole body".
Figure 4 shows the quadrilateral division of the planar area. Each face is close to a square and the streamlines are smooth and smooth. The normal vertex topology degree is 4 and is adjacent to 4 faces; the red vertex topology degree is not equal to 4 and is called a singular point. Streamlines passing through singular points are marked in red and are called singular orbits. The positions and topological degrees of all singular points are called the configuration of the singular points. We can imagine that the overall layout of the quadrilateral grid depends on the configuration of the singular points, which can affect the whole body. The singular points are not independent of each other, but are restrained by each other, thus having some overall properties.
Figure 5. There is no quadrilateral mesh with only two singular points (3,5) on the topological tire.
By examining a simpler example, we can get a stronger sense of some global obstacle. As we all know, we can perform quadrilateral meshing on a closed surface (topological tire) of genus , so that there are no singular points. A long-standing open question is whether topological tires exist with a quadrilateral meshing with only two singular points, one with topological degree , and the other with topological degree ? In fact, such a quadrilateral mesh does not exist, but its proof is anything but elementary. If we assume that such a quadrilateral mesh exists and is recorded as , then it satisfies Euler's formula: point + surface - edge = surface Euler characteristic number. Therefore, its existence is not inconsistent with topology, which means that the essence of this problem transcends the topological category. Then we assume that each surface is a planar Euclidean square, thus obtaining a straight metric of the surface, which is called the Riemannian metric induced by the quadrilateral mesh. The metric has two cone singular points. The point with topology degree becomes the vertex of a cone surface, and the cone angle is . The point with topology degree becomes the vertex of another cone surface, and the cone angle is . This Riemannian metric satisfies the classic Gauss-Bonnet theorem, that is, the total Gauss curvature is equal to the product of the Euler characteristic number. Furthermore, according to the singularization theorem of discrete surfaces mentioned above, we can prove the existence of this Riemannian metric with cone singularities. Therefore, we still cannot rule out the existence of using elementary Riemannian geometry.
Figure 6. Quadrilateral grid metric-induced harmonic clusters.
The observations that really reveal the nature of the problem come from the holonomy of measurement. We select a loop composed of faces on the quadrilateral grid, put a unit frame in the first face, the coordinate axis is parallel to the two opposite sides of the quadrilateral, and then move parallel to the next face. Move parallel along the loop in this way until you return to the original surface. The difference between the parallel-moved frame obtained in this way and the initial frame is one rotation, and the rotation angle is an integer multiple of . The resulting harmonic group of the metric surface is
subgroup of , which is called the harmony condition of the quadrilateral mesh. Although the flatness metric we obtained using the discrete surface Ricci method satisfies the conditions of the Gauss-Bonnet theorem, it does not necessarily satisfy the Harmony condition, which becomes the key to the problem. So, how to characterize the harmony conditions of the Riemannian metric induced by the quadrilateral mesh? The answer also comes from conformal geometry.
Grid-induced meromorphic fourth differential
Given a quadrilateral mesh on a surface, induce a natural conformal structure, the conformal atlas, denoted by , This conformal structure is compatible with the Riemannian metric. Compatibility here means that on any local complex coordinate system, the Riemannian metric satisfies the formula:
The atlas can be constructed as follows: each face is regarded as a square on the complex plane, defining local coordinates; each edge is regarded as a rectangle on the complex plane, defining local coordinates; each normal vertex is regarded as a unit open circle on the complex plane. These direct transformations of local coordinates are rigid body transformations on the plane, with the form
Nature is both pure and pure. The key is to examine the neighborhood of the singular point. Suppose it is a singular vertex with topological degree , its neighborhood is equidistant from a cone surface, it is the vertex of the cone, and the cone angle is . The local coordinates flatten the cone to a planar disk via an exponential mapping. Assume that it is an adjacent surface that is equidistant from the cone surface. It might as well be located at the lower left corner of the plane square, then the transformation between local coordinates is:
In the same way, it is easy to see that all transformations between local coordinates are doubly holomorphic, and a conformal atlas is obtained, which becomes a Riemann surface.
More essentially, the quadrilateral grid not only induces a conformal structure, but also induces a meromorphic fourth differential. The singular point configuration of the quadrilateral grid is equivalent to the poles (singular points with a topological degree less than) and zero points (singular points with a topological degree greater than). The idea is very intuitive. Construct a holomorphic 1-form on each surface, and construct a holomorphic differential on each edge. From the local coordinate transformation formula (1), we get
This means that the holomorphic 1-form thus constructed is not globally defined. Examining the singular point neighborhood, from the local coordinate transformation formula (2), we get
However, if we consider the power of equation (3), then
Considering the power of formula (4), we get
From this we get that it is a meromorphic fourth differential, and it is globally defined. At the same time, from formula (5) we see that singular points with topological degree become poles of order, and singular points with degree become zero points of order. Therefore, the configuration of the singular points of the quadrilateral grid is equivalent to the zero and pole points of the meromorphic fourth differential, that is, the divisor, which is written as
Here is the order at the point.
Abel's theorem
On the Riemann surface, the divisor of meromorphic differentials satisfies the famous Abel theorem, that is, the divisor satisfies special differential and integral equations.
Figure 7. Canonical fundamental group basis.
Suppose it is a closed Riemannian surface with a genus of , and the canonical basis of its fundamental group is
The holomorphic 1-form basis of the Riemann surface is
From this we get the periodic matrix of the Riemann surface
here
constitute grid points
Figure 8. Holopure 1-form substrate.
The Jacobi variety of the Riemannian surface is defined as
The red parallelogram in Figure 5 shows the Jacobi cluster of topological tires, that is, the flat torus. Points of Jacobi clusters are clustered under addition. The Jacobi map embeds the Riemannian surface holomorphically into the Jacobi variety: Let, we choose a path connecting the base points and,
Theorem(Abel) The divisor of a meromorphic function on the Riemann surface is mapped by Jacobi to the zero points of the Jacobi variety:
We assume that the genus of the Riemann surface is , and give a simple proof of Abel's theorem. We first prove a lemma:
LemmaAssuming that the Riemann surface is a topological tire, which is a holomorphic mapping from the sphere to the Riemann surface, it will be mapped to a point on.
We upgrade the mapping to the universal overlay space, which is a holomorphic mapping. The universal covering space of the topological tire is conformally equivalent to the complex plane, and we obtain the holomorphic mapping. The sphere is a compact set and the image set is bounded. According to Liouville's theorem, the holomorphic mapping is a constant value mapping, here is a projection mapping, so it is a constant value mapping.
Now, we prove Abel's theorem. Given a meromorphic function, it can be regarded as a holomorphic mapping from the Riemann surface to the sphere. At a fixed point, the original image is a divisor, and the Jacobi map maps it to a point on the flat ring, from which we obtain the holomorphic mapping. According to the lemma, it is a constant value mapping. From this we have:
This is Abel's theorem. This elementary proof can be generalized to the Riemannian surface of any genus.
Fundamental theorem of surface quadrilateral mesh
From Abel's theorem, we obtain the basic theorem of the singular point configuration of the quadrilateral grid.
Figure 9. The surface quadrilateral mesh is equivalent to the meromorphic fourth differential. The singular point configuration "has a single influence on the whole body", which is expressed as the Abel-Jacobi condition.
Theorem(Quadrilateral mesh singular point configuration [3]): Given a quadrilateral mesh, its induced meromorphic fourth differential is, let it be any holomorphic 1-form, then it is a meromorphic function,
Now let's go back and use the basic theorem to prove that there is no quadrilateral meshing of 3-5 singular points on the tire surface: Assume it is a quadrilateral mesh, a singular point with a topological degree of 3 and a singular point with a topological degree of; there is a holomorphic 1-form on the tire surface, without zero poles and divisors. From the above basic theorem, we have
This means dots and coincidences, contradictions. Therefore, there is no quadrilateral mesh with 3-5 singular points on the tire. Readers can think about it, is there a triangulation on the tire surface, each vertex has a topological degree of , but there are two singular points, one with a topological degree of , and the other with a topological degree of ?
Figure 7. Buddha surface converted to T-spline.
With the basic theorem in hand, the manual empirical algorithm for surface quadrilateral mesh generation can be upgraded to a theoretically rigorous automatic algorithm. By optimizing the configuration of the singular points to satisfy the Abel-Jacobi condition (6) of the basic theorem, and then using the surface Ricci flow method to construct a straight metric with cone singular points, a meromorphic fourth differential is obtained, and a quadrilateral grid, or T-spline, is constructed.
Summary
From a modern point of view, the essence of the Abel-Jacobi theorem is the theory of representative classes of holopure line bundles on the Riemann surface. Meromorphic differentials can be regarded as the global cross-section of holopure line bundles, and their divisors constitute the representative class of line bundles. The natural extension of this theory to high-dimensional complex manifolds is the famous Kunihiko Kodaira theorem in algebraic geometry [1].
We have seen that one of the most challenging technologies for industrial software is surface and solid mesh generation. This technology is both engineering and theoretically difficult. Decades of research and development in the industry have been difficult to achieve breakthrough progress, because its theoretical basis requires the use of very modern core theorems of differential geometry, conformal geometry and algebraic geometry, and the corresponding core algorithms (such as discrete surface Ricci flow [2]) have only been developed in recent years. The structured four-deformation mesh of the curved surface has strong geometric properties, and everyone who comes into contact with this problem will immediately have the intuition that "one hair can affect the whole body". Our work is essentially to express this intuition in the language of strict algebraic geometry, thus improving the empirical algorithm into a rigorous and automatic algorithm.
At present, the "numerical calculation engine" is very mature. Classic linear algebra algorithms, numerical differential equation algorithms and optimization algorithms have become simple commands of Matlab; but the "geometry engine" is still in its infancy. Young students are trying to calculate the geodesic between two points on a surface, the harmonic leaf structure of a surface, or overlapping spaces, single-valued measurements, etc., but they cannot find convenient calculation software at all. We hope that a “geometry engine” can be developed in the future, and differential geometry, algebraic geometry, and conformal geometry theoretical methods will soon be popularized in the industry to truly improve productivity.
【1】Shing-Tung Yau, "From Riemann and Kodaira to Modern Developments on Complex Manifolds", ICCM Notice, 2017.
【2】X. Gu, F. Luo, J. Sun and T. Wu, "A Discrete Uniformization Theorem for Polyhedral Surfaces I", Journal of Differential Geometry (JDG), Volume 109, Number 2, Pages 223-256, 2018.
【3】N. Lei, X. Zheng, Z. Luo, F. Luo and X. Gu, "Quadrilateral Mesh Generation II: Meoromorphic Quartic Differentials and Abel-Jacobi Condition", Computer Methods in Applied Mechanics and Engineering, 2020.
Machine-translated from the Chinese original 浅谈曲面网格生成的理论基础 (published 2022-03-29). WeChat original ↗