Computational conformal geometry is an emerging interdisciplinary discipline that integrates modern basic mathematics and geometry with computer science, extends the theories in modern topology and differential geometry to discrete situations, develops computational methods and is widely used in fields such as computer graphics, computer vision, geometric modeling, networks, computational mechanics, and medical imaging. Its basic algorithms have been adopted by the industry. For example, conformal virtual colonoscopy technology is promoted by Siemens, surface parameterization technology is adopted by the animation film and television industry, and some core algorithms are adopted by game companies (such as Blizzard).
For the past ten years, Lao Gu has taught the course "Computational Conformal Geometry" at the Yau Shing-tung Mathematics Center of Tsinghua University every summer. The course is completely free and open to the entire society. Students come from all over the country, and some students come from Europe, the United States, Hong Kong and Macao. The backgrounds of the students include computer, electronics, automation and other engineering majors, including mathematics, physics and other science majors, as well as biomedicine and other majors; many engineers come from animation design, industrial testing, computational mechanics, fluid mechanics, and doctors in the field of radiology and imaging. Mr. Qiu Chengtong and Lao Gu compiled the contents taught over the years into a book and published "Computational Conformal Geometry - Theory". We will use this book as a teaching material in the future.
Conformal geometry is rooted in basic mathematics and is the intersection of many fields: Riemann surface theory, complex analysis, differential geometry, algebraic topology, geometric partial differential equations, algebraic curves, etc. Computational conformal geometry is also related to computational geometry, digital geometry, and numerical partial differential equations in computer science. The birth of this discipline is due to the vigorous rise of 3D technology, especially 3D scanning technology (such as phase translation technology based on structured light), computer graphics technology (such as surface parameterization, texture mapping technology), computer vision technology (such as surface registration and registration, The rapid development of facial expression capture has made it impossible for traditional Euclidean geometry and linear algebra methods to solve the profound problems raised in these fields. The field of engineering and medical care must systematically introduce the ideas and methods of modern differential geometry and topology to develop rigorous and practical calculation methods. Computational conformal geometry responds to the call of the times and promotes the development of science and technology based on first principles.
Textbook Chapter Summary
The first part of the tutorial is algebraic topology and differential topology. It mainly explains the concepts of homotopy groups and homology groups. It uses this as a tool to explain the covering space theory, Brouwer and Lefschetz fixed point theory, the principle of regional invariance, especially the calculus on differential manifolds, the promotion of field theory in differential form and external differentiation, and the Poincare-Hopf index theorem of singular points in vector fields. Especially the de Rham cohomology theory in differential topology and the Hodge decomposition theory. Figure 1 shows two conjugate harmonic differential forms on the surface, that is, irrotational and divergence-free vector fields. All such harmonic fields constitute the cohomology group of the surface. This means that the dimension of the solution space for elliptic partial differential equations on a Riemannian manifold is related to the topology of the manifold, which is the essence of the index theorem.
Figure 1. Harmonic forms and holomorphic differentials on surfaces.
The second part is the geometric theory of complex variable functions, mainly using the normal function family and the principle of geometric variation to prove the Riemann mapping theorem, the surface conformal standard form and the singularization theorem. As shown in Figure 2, all zero-genus surfaces can be mapped into planar rings, and each boundary is mapped into a concentric arc.
Figure 2. Surface conformal standard type.
The third part is the differential geometry of surfaces, which mainly explains Riemannian metrics, measure lines, parallel movements, basic forms, especially the moving frame method, Gauss-Bonnet theorem, and geometric approximation theory. As shown in Figure 3, there are two geodesic lines on the face surface.
Figure 3. Geodesics on a surface, concept of conjugate points.
The fourth part, the harmonic mapping theory, mainly proves the existence, uniqueness and differential homeomorphism of the harmonic mapping of the surface. The singular point Bochner theory of harmonic mapping gives the calculation method; the figure shows the harmonic mapping of the zero-genus closed surface to the unit sphere. The Hopf differential of the harmonic map is a holomorphic second differential, and the holomorphic second differential on the sphere is 0, so the harmonic map must be a conformal map.
Figure 4. Harmonic mapping of Stanford rabbit to spherical surface (worked by Wen Chengfeng and Qi Xin).
The fifth part is the theory of Riemann surfaces, which mainly introduces the meromorphic differentials on the Riemann surface and the Riemann-Roch theorem; Figure 5 shows the meromorphic fourth differential on the Riemann surface with a genus of two. Its horizontal vertical trajectory generates a quadrilateral grid, and its singular points satisfy the Abel-Jacobi theorem.
Figure 5. Quadrilateral mesh induced by meromorphic fourth differential on the surface.
The sixth part is Teichmuller quasi-conformal mapping theory, which introduces the existence and uniqueness of Teichmuller space and Teichmuller mapping. All metric surfaces can be classified by conformal equivalence relations, and all equivalence classes constitute Teichmuller spaces. As shown in Figure 6, there are 15 holes on the surface of the human face, which can be conformally mapped to a flat disk, and each hole is mapped into a circular hole. We need 45 parameters to describe the location and size of these circular holes. But we can use Möbius mapping to transform the right frame, so the Teichmuller space corresponding to this topological surface is 42-dimensional.
Figure 6. Teichmuller coordinates of the Riemann surface.
The last part of the textbook is the discrete surface Ricci flow theory, which uses the principle of geometric variation to prove the existence, uniqueness, and discrete singularization theorem of Ricci flow solutions. Ricci flow is currently the only method that can use curvature to design the Riemannian metric. Almost all geometric calculation problems can be reduced to computing the Riemannian metric, so this algorithm is of fundamental importance. Ricci flow deforms the Riemannian metric so that the deformation rate is proportional to the current curvature. The curvature follows the diffusion-reaction equation. If the diffusion term suppresses the reaction term, the Ricci flow diagram stably converges to a constant curvature metric. Figure 7 is the artistic expression of surface singularization, and Figure 8 is the algorithmic expression of this theorem. All surfaces in real life can be conformally transformed into constant curvature surfaces, namely spheres, Euclidean planes and hyperbolic planes. The high-dimensional generalization of this theorem is the historical theme of the development of differential geometry.
Figure 7. Escher’s Demons and Angels, artistically demonstrating the singularization theorem.
Figure 8. The singularization theorem of closed surfaces, obtained by the Ricci flow algorithm.
Echoing these theories, we give corresponding calculation methods. We have online demonstrations and videos for all the main algorithms and main theorems. Students only need to scan the QR code of the corresponding chapter in the book to see it. At the same time, we have prepared after-class assignments. Students can implement the main algorithms in the book based on the skeleton source code provided, and test them with the data provided in the course. Full-time teaching assistants will provide students with necessary assistance.
Basic concepts and central theorem
Figure 9. Conformal properties of conformal transformation.
Conformal geometry is the study of invariants under conformal transformations. The so-called conformal transformation is a mapping that keeps the angle unchanged. As shown in Figure 9, we map the three-dimensional face surface to a two-dimensional flat disk. We draw two intersecting curves on the face at will. The curve on the surface is mapped to the plane curve, but the intersection angle remains unchanged.
Figure 10. Conformal transformation and general diffeomorphism.
On each tangent plane of the surface, the derivative map of the conformal map is a similarity transformation, but the similarity ratios are different from each other on different tangent planes. As shown in Figure 10, we spread small circles on a flat disc and reflect it back on the face surface. If the shape of the small circles is maintained, then this mapping is conformal. General mapping will map a small circle on the plane into an ellipse. Figure 11 shows that conformal mapping preserves local shape.
Figure 11. Conformal mapping preserves local shape.
Conformal mapping keeps the angle unchanged, and area-preserving mapping keeps the bins unchanged. As shown in Figure 12, the Maitreya Buddha image is mapped to a flat disk. The left frame is a conformal transformation that keeps the local shape unchanged; the right frame is a face-preserving mapping, and the three-dimensional area of each region is equal to the two-dimensional area of its image.
Figure 12. Angle-preserving transformation and area-preserving transformation (by Su Kehua).
The most profound and basic theorem in conformal geometry and surface differential geometry is the grand unification theorem: Poincare-Koebe's singularization theorem. As shown in Figure 8, a closed metric surface can be periodically and conformally mapped to one of three standard spaces: the unit sphere, the Euclidean plane, and the hyperbolic disk. This periodic embedding is described by a certain symmetry group, which reflects the overall properties of the surface, that is, the conformal structure of the surface.
Figure 13. Unification theorem for surfaces with edges.
The singularization theorem still holds for surfaces with edges. As shown in Figure 13, all surfaces can be conformally mapped into standard space, and all boundaries are mapped into geodesic circles. Currently, only the Ricci flow method for discrete surfaces can calculate surface singularization.
The core context of computational conformal geometry mathematics is to prove the existence, uniqueness, regularity, and well-posedness of the understanding of single-valued theorems, especially how to extend it to discrete surfaces and even discrete graphs. The core of computer science is computability, that is, how to design algorithms to calculate single-valued theorems. Human beings have accumulated the essence of theory for hundreds of years; in our generation, the theory has been developed into rigorous and efficient algorithms; in the next generation, algorithms will naturally be widely used in engineering and medical care to truly benefit mankind.
Direct application
Figure 14. Surface parameterization.
Figure 15. Texture map.
Conformal geometry has many applications in the field of computer graphics. The most basic one isSurface parameterizationandtexture map, as shown in Figure 14-16. The so-called surface parameterization is to map the curved surface to a flat area to minimize the distortion caused by the mapping; the so-called texture mapping is to apply the flat image to the curved surface through parameterization. Texture mapping technology is one of the basic technologies of the entire film, television and animation industry. Recently, Unreal Engine 5 has integrated virtual geometry technology to unify texture and geometric data, further liberating the creativity of digital artists. This will have a revolutionary impact on games, geometric big data, geographic information systems and other fields.
Figure 16. Surface texture map.
Figure 17. Geometry compression, mesh generation.
In traditional graphics, surfaces are represented by triangular meshes. How to generate high-qualitytriangulation, how to implementGeometry compression, using the fewest vertices and faces to express as precise geometric features as possible, all of which require conformal geometry algorithms. As shown in Figure 17, we conformally map the original surface to a planar area, and then use the Delaunay Refinement method to generate a triangular mesh on the planar disk. Since the conformal mapping is conformal, the Delaunay triangulation of the plane thus obtained is pulled back to the surface, and the geodesic triangulation of the surface is obtained. By changing the sampling density, we obtain surface triangular meshes with different resolutions.
Figure 18. Geometric image.
Recently, virtual geometry technology has emerged in the gaming industry, aiming to support real-time rendering of massive geometric data. This technology is likely to begeometric imageTechnology related, as shown in Figure 18, based on the surface parameterization in Figure 14, we map Michelangelo's King David statue to a planar area, and then uniformly sample the planar area to obtain the image in the upper left corner. The color value of each pixel of the image represents the spatial coordinates of the sampling point, thus obtaining the geometric image; the upper right corner is the normal vector map, and the bottom row shows the rendering effect of the geometric image with different sampling rates. This technology unifies the geometric data structure and image data structure, and can directly apply virtual texture technology to process massive geometric data while simplifying software and hardware systems. This is likely to become a growth point for new technologies in the gaming field.
Figure 19. Surface registration and registration (by Wen Chengfeng).
In computer vision,Surface registrationIt is a basic problem. The so-called registration is to find the bijection between two surfaces and correspond the main feature points while minimizing the geometric distortion. Figure 19 shows the calculation method based on conformal geometry. We use Riemann mapping to map the 3D curved surface to the planar disk, and then establish a differential homeomorphism between the planar disks, thus converting the registration problem of the 3D surface into a mapping problem of the planar area. All feature points in the figure are marked as red points. Looking closely, we see that the small circles on the girl's face are mapped into the small ovals on the boy's face, and that all ovals have the same eccentricity. Theoretically, this mapping is called a Teichmuller mapping and has minimal distortion.
Figure 20. Facial expression motion capture.
As shown in Figure 20, this method can also establish registration between dynamic surfaces to achieveexpression capture. This technology is widely used in the film and television animation industry.
Figure 21. Holomorphic differential on the surface (by Zheng Xiaopeng).
Teichmuller theory is used to find the differential homeomorphism with minimal distortion between given surfaces, as shown in Figure 19, and this optimal mapping relies on the holomorphic quadratic differential on the surface. Figure 21 shows the holomorphic quadratic differential on the kitten surface. This can also be understood as the conformal structures on all given topological surfaces form a finite-dimensional manifold, the so-called Teichmuller space. The tangent space of Teichmuller is all holomorphic quadratic differentials on the surface.
Figure 22. Surface regular quadrilateral segmentation (by Zheng Xiaopeng).
In computational mechanics, finite element calculations require regular decomposition of geometric entities. For example, to generate a curved surfacequadrilateral mesh, as shown in Figure 22. In essence, the quadrilateral mesh of the surface is equivalent to the meromorphic fourth differential on the Riemann surface, and its singular points satisfy the Abel-Jacobi theorem. This theorem is essentially an representative class of holopure line bundles on the Riemann surface. After decades of practical exploration, this intrinsic and secret connection has finally been revealed. In recent years, research in this area has been in the ascendant.
Figure 23. Spline surface (by He Ying).
In the fields of industrial design, mechanical design, and digital manufacturing, surfaces are expressed by spline surfaces.Construct splinesIt is essentially an algorithm for calculating the affine structure of a surface, which ultimately boils down to conformal geometry.如图23所示，黄色点为曲面的奇异点，我们构造一个黎曼度量，将所有曲率集中在奇异点处，如此得到的度量诱导曲面的一个仿射图册，从而我们可以构造样条曲面。 This special Riemannian metric can be obtained using the Ricci flow method for surfaces.
Figure 24. Graph embedding.
In the past few years, graph networks have developed rapidly, and the problem of graph embedding has aroused great interest. Applying the method of conformal geometry, we can calculateGraph embedding,It is crucial for the design of network routing algorithm. Figure 24 shows the embedding of an abstract graph on a sphere. This embedding can be regarded as the generalization of the conformal singularization theorem on graphs.
Figure 25. Metamaterial design (by Chen Shikui).
Figure 25 shows the metamaterial design in additive manufacturing, frame (d) shows a mask designed with negative Poisson's ratio material. Traditional metamaterial design can only be implemented on a flat area. Using conformal geometry, we can design and simulate on any curved surface.
|
|
|
Figure 26. Conformal brain map.
Figure 26 shows that the curved surface of the cerebral cortex is conformally mapped to a planar area, and the sulci on the brain are reflected as circular boundaries on the planar surface. In this way, we can compare different cerebral cortical surfaces and monitor the progression of neurological diseases, such as Alzheimer's disease and others.
Figure 27. Virtual colonoscopy.
Figure 27 shows the virtual colonoscopy technology. We tile the curved surface of the rectum onto a flat surface, thereby unfolding all folds and exposing all rectal polyps, monitoring the growth of polyps and preventing the occurrence of cancer.
Tutorial summary
Computational conformal geometry provides a great opportunity for young people with engineering and technical backgrounds to systematically study modern topology and geometric theory, truly combining abstract mathematical theory with practical high-tech. Almost all basic concepts and important theorems have computer algorithms corresponding to them. We conduct detailed analysis of a large number of key engineering issues and reveal the topological and geometric essence behind them.
We found that in the field of engineering, many basic problems have been studied for decades. Although engineering has continued to improve, the nature of the problem has not been clearly explained. In many cases, engineering and technical personnel have very good intuition and have accumulated various know-hows, but they cannot rise to the theoretical level and cannot be accumulated from generation to generation. For example, in the field of mechanical design, a large number of CAD models need to be represented as spline surfaces, but how to design splines that smoothly cover the entire surface and remove singular points has always been an unsolvable problem. We found that the construction of traditional spline surfaces relies on affine invariants, so the affine structure of the manifold is required. But there is no affine structure on general manifolds, and we must introduce singular points. For another example, the key to quadrilateral mesh generation is singular point design. How to specify the location of singular points can ensure that the generated quadrilateral mesh is conformal to the original surface. Research in this area has lasted for decades, but there has been no satisfactory answer. Although a large number of commercial software claims to solve this problem, their solutions all require manual intervention. In fact, this problem ultimately boils down to the representational class theory of holopure line bundles. Another example is how game engines support real-time rendering of massive complex geometric data. This has always been a key issue in this field. A promising solution is to convert the triangular mesh into a texture representation and use virtual texture technology to dynamically schedule active pages between the hard disk and GPU memory. The bottleneck of this technology lies in the global parameterization of geometric big data, which relies on conformal geometry algorithms. Perhaps the emergence of Unreal Engine 5 can promote the explosion of virtual geometry technology. Sublimating the accumulated engineering intuition into a rigorous and self-consistent theoretical system is exactly the purpose of this book.
We hope that this tutorial can inspire students to understand the truth of nature through both brain and hands-on approaches, implement next-generation geometric algorithms, and make substantial contributions in their respective fields. With the development of science and technology, most computer textbooks are quickly obsolete. The geometric concepts and theories in this book are part of nature and independent of human society. Therefore, we hope that this book can accompany readers throughout their lives. The geometric principles explained in the book will be integrated into the readers' blood, and the geometric topological theoretical structure in the book will become part of the readers' knowledge structure. I hope this book will become a common reference book for engineering and technical personnel. They can look up common topological geometry concepts in engineering at any time, find proofs of common theorems, and find practical topological geometry algorithms. By reading it frequently, you can find inspiration for artistic design and breakthrough points in engineering technology. We hope that the theories and algorithms for calculating conformal geometry can withstand the test of time and remain relevant throughout history!
The QR code of "Computational Conformal Geometry - Theory".
Machine-translated from the Chinese original 《计算共形几何-理论篇》教程简介 (published 2020-06-08). WeChat original ↗