In the summer of 2022, the entire world is still ravaged by war and plague, but the epidemic has eased, and academic exchanges and business activities have gradually resumed. Recently, many old friends have come to New York for meetings or travel, and they have been able to meet Lao Gu. These old classmates and friends include leaders in the financial world, successful people in the real estate field, Google executives and well-known professors in academia. We have not seen each other for many years, the world's current situation has undergone tremendous changes, and each of us is confused and sighing about the aftermath of the disaster. During an accidental conversation, I suddenly discovered that many old classmates had passed away. Professors who were successful in their academic and professional careers were the most likely to die young. Secondly, several old classmates who were still blindly confident in their own health in middle age died in accidents during intense exercise. I visited Yale two days ago and recalled a Chinese restaurant called "Shangri-La". An old friend loved the special snails in it. This old friend became mentally disturbed due to the setbacks in his life and died in random shooting by the West Coast police. Another friend from Yale whose father died of intestinal cancer at an early age had been undergoing physical examinations since he was young due to the gene he carried, and has been fine so far. He often says that every day of his life after the age of 40 is a gift from God, and he is now very successful in the financial field.
The old classmates all have rich life experiences, with honors and disgrace half their lives, and they look down on prosperity. They will gain a lot of life insights during heart-to-heart conversations. Once, I had a small gathering with Senior Brother Wang in a "thatched cottage" in Manhattan. As a Google executive, Senior Brother Wang still works diligently for nearly 10 hours a day and frequently travels between the East and West coasts. Brother Wang feels very grateful that he chose the computer major in this life. When they applied for Tsinghua University, children like Brother Wang and Lao Gu who came from areas with backward technology and poor educational resources had no idea what computer science was. But in the past thirty years, the development of the computer industry has become the core force for the progress of human civilization, and it has become more and more powerful. Through the efforts of a generation represented by Senior Brother Wang, IT companies such as Google have enabled the entire human race to be immersed in a sea of information all day long. The bottleneck for everyone's information intake is no longer content generation or network bandwidth, but the physiological limit of the brain's ability to process and digest information. Although he has achieved a respectable social status and favorable living conditions by relying on computer technology, the senior brother feels that daily computer work lacks intellectual challenge and even resents the superficiality of computer science. Therefore, he very much hopes that his children will learn more modern mathematics. Brother Wang and Lao Gu both conducted research in the field of computer-aided geometric design (CAD) at Tsinghua University and have been tracking the development of 3D technology for many years. With the rise of the metaverse, the demand for industrial software has increased, and computer-aided design and 3D geometry technology have gradually entered the center of the computer industry stage. However, their theoretical foundations still have essential flaws.
Mathematics and Engineering Technology
Mathematics has been ahead of engineering technology for decades. When Senior Brother Wang and Lao Gu started their studies, the topological geometry theory used in the field of computer science was very simple. With the development of the times, the mathematics required in the computer field today is no longer what it used to be. Lao Gu has personally experienced many instances and has a deep understanding of this. In his doctoral thesis supervised by Mr. Qiu Chengtong, Lao Gu developed a calculation method for surface conformal structures. Later there were many applications, such as virtual colonoscopy technology in medical images, where conformal geometry was used for precise registration between rectal surfaces, and this patent was adopted by Siemens. Twenty years later, the governments of Japan and South Korea encouraged all citizens to use virtual colonoscopy technology for early screening of bowel cancer, and the solutions used were basically derived from Siemens technology. For another example, Mr. Qiu developed the theory of the Monge-Ampere equation in the 1970s and proposed 100 open problems in geometry in 1993. The 19th problem was how to invent an efficient and stable numerical algorithm to solve the spherical Monge-Ampere equation. Brenier theory in optimal transmission theory is equivalent to solving the Monge-Ampere equation. We resolved this issue raised by Mr. Qiu in 2019. In the past two years, the theory and algorithm of optimal transmission have been widely used in deep learning and have become the theoretical basis of deep learning. Deep learning based on optimal transmission has increasingly become a branch field. We also believe that in the foreseeable future, the affine differential geometry theory and Monge-Ampere equation theory pioneered by Mr. Qiu Chengtong and Professor Zheng Shaoyuan will play a guiding role in the development of industrial software.
Spline theory and affine geometry
In the 1970s, computers began to be used in the automobile, shipbuilding, and aviation industries, giving rise to the field of computer-aided design (CAD). However, the early founders were mostly engineers and computational mathematicians. The CAD theories and methods they designed only considered the design of surface patches with simple topology, but did not consider the overall design of complex topological surfaces, so they had great limitations. With the rapid development of the machinery industry and the formulation of CAD industry standards, these limitations have been fixed. Huge amounts of capital have been injected into these industries, and top-level technologies have been updated many times (such as numerical simulation, CNC machine tools, 3D printing), and the limitations of the bottom-level have become even more entrenched. These hidden dangers have become huge difficulties that are difficult to solve in today's CAD industry. Investigate its fundamentals,The root cause of these difficulties is that the founders of the CAD field only considered local differential geometry and ignored large-domain (overall) differential geometry.. Below we briefly analyze some of the most basic issues.
Figure 0. CAD model of Dodge (Kendrick Shepherd).
In the fields of animation, games and 3D printing, surfaces are represented by triangular meshes. The surface represented by this method is only continuous but not differentiable. In the field of CAD, surfaces are represented by piecewise rational polynomials (NURBS), which have high-order derivatives. When processing with CNC machine tools, we can calculate the speed and acceleration of the turning tool.The ultimate goal of spline surfaces is to design a pieced algebraic surface that can approximate topological and geometrically complex surfaces with arbitrary precision, achieve automatic seamless splicing, and have continuous (smooth) curvature everywhere.。
In the one-dimensional case, a curve with smooth curvature is approximated by a piecewise polynomial curve. The shape of the curve is determined by several control points. Any point on the curve is obtained by the weighted average of several adjacent control points, and its weight depends on the parameters of the point and the parameters (knots) corresponding to the control points. The specific mathematical expression is as follows: a parametric curve is expressed as a single-variable polynomial mapping:,
- Symmetry: Let Yes any arrangement of , then
- Affineness: Blossom is affine with respect to every variable, given ,
- Identity:
Figure 1. B-spline curve and control points.
The most commonly used spline is cubic to ensure that the curvature is continuous. Given a parametric straight line, knots are distinct points
Every three adjacent knots correspond to a control point. Given the parameters, we can calculate it using the affine properties of the polar form, as shown in the figure:
Figure 2. deBoor evaluation algorithm.
Express the sum of linear groups that form a sum:
Here the weight
is called the barycentric coordinate of . by affine
In the deBoor algorithm, each node is obtained by a linear combination of two upper nodes, and the combination coefficient is equal to the center of gravity coordinates. A polynomial curve is obtained from four adjacent control points, and polynomial curves in different segments are automatically connected. We see that if we perform an affine transformation on the parameters (including knots), the center of gravity coordinates remain unchanged, the deBoor evaluation process remains unchanged, and the resulting B-spline curve remains unchanged. This means that the barycentric coordinates are invariant under affine transformations, and B-spline curves are invariant under affine transformations. That is to sayB-spline theory (flowering theory) is based on affine geometry。
We can directly generalize the theory of spline curves to spline surfaces. One approach is to generalize the blooming theory to higher dimensions. Given a plane parameter area, given knots, each control point is associated with 3 knots, and the triangulation of these knots is calculated. For any point in the parameter area, the corresponding triangle containing point is obtained by triangulation, the center of gravity coordinates are calculated, and the points on the spline surface are calculated by blooming theory. Some combinatorial properties of triangulation are required here. This kind of spline surface can be defined on top of triangulation and also hasParametric affine invariance property. Given a closed surface, we can construct a triangulation on . Can this B-spline surface be defined on ? If we can, then we get an overall smooth piecewise polynomial surface. But this method cannot be implemented,The core reason is that the blooming theory is based on affine geometry, and affine geometric structures cannot be defined on general surfaces.。
general geometry
According to Klein's Erlangen program, different geometries study invariants under different transformation groups. Let be a homogeneous space, a diffeomorphic Lie group, acting on , so that has a geometry determined by the symmetry group. A surface is given, covered by a family of open sets. Each open set has a local coordinate map, called a local coordinate card. Assume, local coordinate transformation
If all local coordinate transformations are in the group, then the atlas is said to be an atlas. -The equivalence class of the album is called a -structure. If a surface is equipped with a structure, we can define the corresponding geometry on the surface. For example, if it is a complex plane and a biholomorphic mapping group, the corresponding structure is a conformal structure. Under the conformal structure, the concept of angle is well-defined, but the concept of length cannot be defined. If it is a real projective plane and a projective transformation group, the corresponding structure is a projective structure. We can define common concepts in projective geometry on the surface, such as projective straight lines, projective conic sections, real intersection ratios, etc. If it is a unit sphere and a linear fraction group, it is a complex projective structure. At this time, concepts such as complex intersection ratios, angles, and arcs are still globally defined. If it is an affine plane and an affine transformation group, then the - structure is an affine structure. At this time, the center of gravity coordinates are meaningful. With the help of the construction method of the affine structure B-spline surface, it can be directly defined on the surface.
Figure 3. Complex projective structure and real projective structure of the genus 2 surface.
However, the presence or absence of affine structures depends on the topology of the surface. It can be directly proved that if there exists an affine atlas for an orientable closed surface, then we can globally define a special connection whose induced Gaussian curvature is zero. According to the Gauss-Bonnet theorem, the Euler characteristic number of a surface is zero and its genus is . For other genus closed surfaces, the affine structure does not exist. this meansDue to topological obstacles, the classic local spline theory cannot be generalized to general global surfaces.. On the contrary, real projective and complex projective structures are widespread. If we can invent an algebraic structure based on projective invariants, such as real intersection ratio or complex comparison ratio, then we can invent a spline surface that is automatically spliced as a whole and the curvature is continuous everywhere. To date, this construction has not been invented.
Singular points and vector cluster properties
Since there is generally no affine structure on high genus surfaces, automatic splicing and globally smooth spline construction cannot be realized. People speculate that secondly, the existence of singular points is allowed. At the singular points, the smoothness of the surface becomes worse, the high-order derivatives become infinite, and the turning tool may break during the machining process. Appeared at this timeAnother central issue in CAD: the setting of singular points. The spline surface combination construction based on triangulation is too complex, and the industry usually uses a simpler tensor product spline surface:
Here and are both one-dimensional B-spline curves.
Figure 4. Tensor product spline surface.
It is an overall piecewise (rational) polynomial surface. The domain of each piece is a rectangle on the plane. In this way, we get a segmentation of the surface. Each cell is a topological quadrilateral, that is, we get a quadrilateral mesh segmentation of the surface. Each vertex is adjacent to multiple quadrilateral faces, and this number of faces is called the topological degree of the vertex. Vertices with different topological degrees are singular points of the quadrilateral mesh. The selection of these singular points should meet stringent topological and geometric conditions, which fundamentally determines the quality of the mesh. Topologically speaking, if we make each face a planar square, the discrete Gaussian curvature of each vertex is
The local coordinate transformation group is a special subgroup of the plane rigid body transformation group. Its translation component is an integer translation, and the rotation angle of the rotation component is an integer multiple of . So we get a structure, here is the Euclidean plane,
When we generalize B-spline to T-spline, we can relax the integer translation condition, but the rotation angle limit remains unchanged. The Riemannian metric obtained in this way is a straight metric with a cone singular point, and a tangent vector is moved parallel along any closed path, and the rotation angle is an integer multiple of . This condition is also called a special harmonic group condition.
For a long time, there was no theoretical explanation for this problem. In practice, engineers relied on their accumulated practical experience to make manual adjustments, often pressing the gourd and lifting the gourd. This means that the issue is essentially a global one. Due to the lack of theoretical guidance, in industry people are forced to construct multiple pieces of splines and then try to glue them together. The surface obtained in this way has many gaps that are difficult to detect with the naked eye. How to check and eliminate these gaps has become a difficult problem in the CAD field. Essentially, this is still an engineering flaw caused by a lack of deep understanding of the overall differential geometry.
Figure 5. T-spline surface and singular points on it.
After long-term exploration, we finally found the governing equations of this geometric structure, thus laying the theoretical foundation for overall quadrilateral mesh generation and spline surface construction. We can prove that: if the surface has the geometric structure defined by equation (2), then the surface is equipped with a flat metric with cone singular points, and the quadrilateral mesh induces a meromorphic fourth differential, whose singular point configuration is equivalent to the divisor of,
Suppose it is any holomorphic subdifferential, then it is a meromorphic function, and its divisor satisfies Abel's theorem: Let be the periodic matrix of the Riemann surface, be the Jacobi variety of the Riemann surface, be the Abel-Jacobi map, and embed the Riemann surface holomorphically into the Jacobi variety. Abel's theorem asserts:
By solving the Abel equation, we can determine the location and topology of singular points, thereby determining the quadrilateral mesh or T-grid and constructing a spline surface. The divisor described by the Abel-Jacobi equation here is essentially the representative class of the holopure line bundle on the Riemann surface, while the meromorphic fourth differential is a global cross-section of the holopure line bundle.
Figure 6. The singular point set of T-spline surface satisfies the Abel-Jacobi condition.
Calculation of geometric structures
We see that CAD applications require the calculation of specific geometries. Given a closed surface with a Riemannian metric, itsconformal structureIt can be obtained by calculating its holomorphic 1-form. First, we calculate the basis of the simple hypohomology group of the surface, then calculate the basis of the dual de Rham cohomology group, and obtain the harmonic 1-form through Hodge decomposition. Each harmonic form is paired with its conjugate to obtain the holomorphic 1-form. From this, we can calculate the periodic matrix, Jacobi cluster and Abel-Jacobi mapping of the surface, so that we can obtain the Abel-Jacobi equation (3) and obtain the location of the singular point.
High genus surfacecomplex projective structureandreal projective structureIt can be calculated by the surface Ricci flow method. Assuming that the Riemannian metric of the surface is and the Gauss curvature is, we hope to calculate the real-valued function so that the Gauss curvature is constant. This is equivalent to solving the Yamabe equation:
This can be calculated by the surface Ricci flow method:
Here is the initial area of the surface. The resulting Riemannian metric is called a single-valued metric. We embed the universal covering space of the surface equidistantly on the hyperbolic plane. If we use the Poincare model, the covering transformation is a Mobius transformation, and we obtain a complex projective structure of the surface; if we use the Klein model, the covering transformation is a real projective transformation, and we obtain a real projective structure of the surface.
If we obtain the divisor by solving the Abel-Jacobi equation (3), then we set the target curvature
Use Ricci flow to obtain the induced metric and satisfy the harmonic group conditions, thus obtaining the required geometric structure of the spline surface. The splines constructed in this way can be automatically spliced seamlessly, and the global curvature is smooth (except for singular points).
open question
As mentioned above, various geometric structures determined by the Riemannian metric of the surface can currently be calculated, but the calculation of the modulus space of these geometric structures is an open problem that has not been solved for a long time. Given a topological surface, all possible conformal structures on it constitute the so-called Teichmuller space. We fix a conformal structure on the surface, and other conformal structures differ directly from each other by a Teichmuller map, whose Beltrami differential is given by a holomorphic quadratic differential. Therefore, the calculation of conformal structures boils down to the calculation of holomorphic quadratic differential groups. One approach is to compute graph-valued harmonic maps. The Hopf differential induced by the harmonic map gives a holomorphic quadratic differential. Another algorithm is based on the Abel-Jacobi theorem and the Ricci flow method. From this we see that the Teichmuller space dimension is, here is the genus of the surface.
The complex projective structure of the surface is determined by, which is a conformal structure and a holomorphic developing map that satisfies the Schwarzian derivative equation:
That is determined by a holomorphic second differential. There is currently no algorithm for computing the moduli space of complex projective structures. We can see that the dimension of this modulus space is. Currently, there is no algorithm that can calculate the moduli space of complex projective structures.
The calculation of the real projective structure is more complicated. It is assumed that the genus of the surface has a - structure. By pasting the local coordinate card of the surface using local coordinate transformation, the universal overlapping space of the surface can be embedded into a convex set, which will be equal to the plane in , then all rays passing through the origin and the sum will form a cone. There is an affine ball inside the cone, which is a graph of a certain convex function. It is determined by a certain function, satisfies the Monge-Ampere equation, and has Dirichlet boundary conditions:
. The Hessian of the convex function gives the affine metric of the affine sphere, which is also a Riemannian metric, thus obtaining the Levi-Civita connection and a conformal structure. There are also affine connections on the affine sphere, and its geodesics are projective geodesics. Then the difference between these two connections is characterized by a holomorphic third differential and conformal structure. Thus a real projective structure is determined by, here is a conformal structure, which is a holomorphic third differential, - the dimension of the structural modulus space is. There is currently no algorithm that can compute the moduli space of real projective structures.
Summary and outlook
We can see that the theoretical basis of geometric modeling in industrial software is affine differential geometry. The traditional spline surface construction relies on the affine structure, and the tensor product spline surface relies on the following structure
The singular set of this structure satisfies the Abel-Jacobi condition, and its calculation relies on the algorithm of holomorphic differentials and the algorithm of Ricci flow. This structure can realize automatic splicing of the entire spline surface. Except for singular sets, the global curvature is continuous. Furthermore, if we can construct splines based on projective invariants, then we can obtain globally smooth spline surfaces. The complex projective and real projective structures of the surface determined by the Riemannian metric can be obtained by the surface Ricci flow algorithm. More general geometric structure algorithms have not yet been invented.
Figure 7. Topology optimized BMW motorcycle frame (BMW).
Although industrial software, CAD modeling software, and CAE simulation software are ubiquitous today, their theoretical foundations have great limitations. The core reason is that traditional methods only consider local differential geometry. When extended to global surfaces, topological obstacles will inevitably be encountered, manifested as representative classes of special vector bundles. Therefore, current CAD methods are inherently difficult. Especially in recent years, 3D printing technology has advanced by leaps and bounds, and topology optimization has become the fastest growing direction in industrial software. The design solution obtained after topology optimization is too complex to be processed by traditional CNC machine tools, but it can be manufactured using metal 3D printing. A current development hotspot is how to convert the surface generated by topology optimization into a traditional spline surface. This urgent need requires that the theoretical foundation of CAD must be broadened and deepened, and the shortcomings of traditional methods must be made up. We believe that fundamentally the solution lies in integral differential geometry. The improved method needs to be able to calculate the overall geometric structure. In the long run, the holomorphic differential algorithm based on Hodge's theorem, the standard metric algorithm based on Ricci flow, and the affine sphere algorithm based on the Monge-Ampere equation will be indispensable. We hope that the introduction of modern geometric ideas and methods will further promote the development of industrial software.
summer courses
At present, these algorithms do not belong to traditional numerical partial differential equation solutions, and young students cannot study and study them in depth. To this end, we are planning to offer an online "Computational Conformal Geometry" course to specifically explain these modern geometric theories and calculations. Our online courses are scheduled to start in July 2022, 4 times a week, 8:30-10:00pm each time. The specific course link will be released soon, so stay tuned.
Machine-translated from the Chinese original 计算机辅助几何设计（CAD）理论的缺陷和全局微分几何 (published 2022-06-24). WeChat original ↗