2021 3D Technology Review

Today is New Year’s Eve in 2021, and it’s time to review the progress of science and technology around us in the past year. The main theme this year is still the fight against the epidemic. Viruses are the most primitive form of life. They only have a piece of information, but they have subverted human history time and time again. Human cells are completely replaced every 7 months, but DNA information remains unchanged. This is enough to show that the essence of human beings is information, so information science is of fundamental importance. Looking at the development of information science in the past one or two decades, especially the development of three-dimensional technology, the author believes that there are three fundamental key natural science factors: 1. The introduction of new physical ideas, physical laws, and breakthroughs in physical methods; 2. The introduction of new mathematical ideas and the application of mathematical theorems; 3. The solidification of software algorithms, the improvement of chip integration, and the improvement of computing power. Other economic and sociological factors are naturally essential and indispensable.

3D vision

Input structured light image.

The core task of computer vision is to restore three-dimensional geometric information from two-dimensional images. Since the birth of computer vision, binocular stereo vision has always occupied a dominant position. Binocular stereo vision simulates the human eye and uses triangular rules to reconstruct three-dimensional information based on the principle of geometric optics (epipolar geometry). However, high-precision, high-speed 3D reconstruction is often based on the structured light method of wave optics, of which the highest quality is the phase translation algorithm. This method comes from the precision measurement method based on laser interference fringes. It is the most common method for industrial inspection and precision robots. In the field of mechanical engineering, this method has a long history, and the key breakthrough was the emergence of DMD chips twenty years ago. Before DMD technology, the accuracy of digital projection technology could not meet the requirements, and accurate 3D reconstruction could not be obtained. After decades of investment regardless of cost, Texas Instruments has finally integrated millions of small mirrors onto a DMD chip. Each pixel corresponds to a small mirror. By rapidly rotating and oscillating each small mirror, the reflection angle and light intensity can be finely controlled. In this way, the structured light method based on phase translation interference fringes has become a reality. Twenty years ago, the author followed Mr. Qiu Chengtong and team members such as Professor Zhang and Professor Wang to develop high-speed and high-resolution three-dimensional scanning technology. We have demonstrated it at international graphics and computer vision conferences such as siggraph and cvpr. A key idea from Mr. Qiu at that time increased our scanning speed several times. A Japanese research institution spent hundreds of thousands of dollars to customize a system, and the Avatar crew also took the initiative to find us for cooperation.

Phase anti-wrapping.

Around 2000, Mr. Qiu organized many academic conferences at Zhejiang University. We invited Israeli applied mathematicians to explain our high-speed 3D scanning technology. They were very excited and asked us for papers and technical details. Soon Israeli applied mathematicians established a similar company, which was soon acquired by Intel for $100 million. Intel has the ability to integrate the industry chain and quickly launched a 3D scanning device such as Real Sense, which became popular around the world. Although Chinese scholars developed key technologies in the early stage, the country may have lacked visionary investors and a complete industrial chain at that time, and many key components were unable to be produced independently. Early CCD digital cameras were relatively expensive, and the image quality of the CMOS chip was very poor, so they could only be used in low-end devices such as optical fingerprint recognition. Twenty years later, CMOS optical sensors are of very good quality and can almost completely replace CCD cameras. However, DMD chips are still monopolized by Texas Instruments, and high-quality digital projection equipment is still expensive. Fortunately, Mems technology (micro-electro-mechanical systems) is advancing rapidly, and laser plus mems can provide a stable structured light source. Currently, with the explosion of the Metaverse, many international 3D vision companies have launched cheap 3D cameras, with prices dropping to around US$500. In North America, there are also delivery boys who carry 3D cameras and provide customers with door-to-door 3D scanning and modeling services.

The reconstructed 3D point cloud is added with texture information.

A core difficulty in 3D geometric reconstruction lies in camera calibration. In traditional 3D vision models, the cameras are all pinhole cameras and the lenses are all spherical lenses. However, due to the processing technology and aging of the lens, this model often brings errors. The classic Zhang Zhengyou calibration algorithm is based on nonlinear optimization to measure lens distortion parameters, which is complex and the optimal solution is not unique. At the same time, this model has too few distortion parameters, and the mathematical model of distortion has a narrow scope of application. It is not applicable to mobile phone cameras, fisheye lenses, and the traditional methods of light field cameras that have become popular in recent years. How to improve the accuracy of calibration and apply it to a wider range of camera models is currently a research direction in the academic community.

Another difficulty in the phase-based structured light algorithm lies in the phase unwrap algorithm. If a multi-wavelength method is used, the phase ambiguity can be reduced, but the scanning speed will be slowed down. Algorithms with better computational performance include solving the Poisson equation, or using the Markov random field method for discrete optimization. Solving the Poisson equation requires an FFT chip, and Markov random field optimization requires a dedicated chip to accelerate it. Perhaps following the wave of the metaverse, this kind of dedicated chip will appear.

Light field cameras are a natural extension of traditional cameras. Just like the compound eyes of insects, drones or robots based on light field cameras have some advantages, such as wider depth of field, wider viewing angles, and higher geometric positioning and reconstruction accuracy. For ordinary users, light field cameras can "press the shutter first and then adjust the focus." The microlens array processing technology of light field cameras is more mature, and more complex freeform lenses can be realized using recent 3D printing technology. Many years ago, Microsoft launched a game based on light field ideas, which did not cause much response. Both Lytro and Magic Leap have failed commercially in recent years. After communicating with many experts in the industry, everyone thinks that Lytro cameras require high-resolution CMOS sensors, which is a bit advanced. Magic Leap technology has too high requirements for GPU computing power and is too aggressive in the market. But light field technology is still developing steadily. The author's friends and several Harvard students are working hard to start a business that combines light fields with online shopping. There are currently some naked-eye 3D display products, but their support for light field display still needs to be improved. The method of high-speed projection and special optical devices still remains in the laboratory.

SLAM

With the increasing popularity of autonomous driving, SLAM technology has achieved unprecedented development. The core algorithms in SLAM include point cloud fusion, geometric shape matching, etc. The most challenging problem in point cloud fusion is the so-called "loop close" condition, that is, global consistency. Assume that the robot walks around a scene and scans the environment from different positions and angles, thereby obtaining many point clouds. The robot needs to fuse these point clouds into an overall geometric surface to create a 3D map. We regard each point cloud as a node, and if two point clouds overlap, add an edge, thus obtaining the so-called view graph. The relative rotation and translation of the camera at the two endpoints are recorded on each edge. For any loop on the view graph, the relative steel body transformations on all edges are compounded in sequence, and finally the identity mapping is obtained. This is called the "loop close" condition. The classic SLAM method locally applies the iterative closest point (ICP) algorithm. From a mathematical point of view, Loop closedness is a global consistency problem, not a local problem. The most appropriate mathematical tool should be some kind of cohomology on the Lie group. According to the author, so far, the ideas and methods of cohomology have not been systematically applied to SLAM technology, and this should be the next development direction.

In robot positioning and autonomous driving, it is of fundamental importance to accurately compare the scanned point cloud with the 3D map. The current traditional method still performs nonlinear optimization in the 6-dimensional steel body transformation group to find approximate solutions. This method is incapable of matching the geometric shapes of large deformations and flexible objects. If the manipulator grasps a flexible object, the geometric deformation is non-rigid. Therefore, the author believes that this situation requires the introduction of more sophisticated differential geometry tools. This kind of deformation is generally close to isometric transformation, that is, although the spatial deformation is relatively large, the geodesic change between any two points on the surface is small. At this time, surface Ricci flow should be used to map the surface to the standard constant curvature space for comparison. So far, the only algorithm for calculating the Riemannian metric through Gaussian curvature is the Ricci flow method. We have spent more than ten years establishing a rigorous mathematical theory and developing an efficient and stable algorithm. This algorithm requires dynamic triangulation and the conjugate gradient method to solve the Poisson equation. For topologically complex surfaces, hyperbolic geometry needs to be applied. The traditional double precision standard cannot directly meet the accuracy requirements of calculations and requires a lot of mathematical and engineering skills. We also look forward to the emergence of dedicated hardware for digital geometry processing.

The 3D point cloud ultimately needs to be converted into a triangular mesh, and the current traditional method is based on normal vector estimation and Poisson reconstruction. The triangulation obtained in this way is too dense and needs to be compressed; more seriously, the quality of the triangulation obtained at this time is very poor and cannot be directly used in computational mechanics and physical simulation. A rigorous and efficient algorithm for geometry compression and high-quality mesh generation relies on the surface Ricci flow algorithm. After the large-scale price reduction of 3D cameras, point cloud processing and digital geometry software will become the key to the development of the industry.

computer graphics

2021 is a landmark year for computer graphics, mainly because of the breakthroughs in two core technologies.

nVidia RTX real-time ray tracing.

The core algorithm for high-quality 3D rendering is naturally the ray tracing method based on geometric optics. Twenty years ago, ray tracing could only be computed on expensive Sun or SGI workstations. As time goes by, more and more physical rules are added to the algorithm process, and the rendering effect becomes more and more realistic. Almost all movie special effects are based on optical tracking, and a movie often requires thousands of Linux servers to calculate for several years. Real-time ray tracing computing has long been a dream. Finally, this year this dream came true, and Nvidia’s GPU technology accumulation reached this critical point.

Another technological breakthrough is Unreal Engine 5's Nanite virtual geometry technology, which can support real-time rendering of billions of triangle meshes, greatly liberating the creative power of digital artists and playing a revolutionary role in the gaming industry. The core of virtual geometry technology is based on the geometric image idea proposed by the author twenty years ago. In the year when Nvidia was born, a GPU company (ATI) was also established in the suburbs of Boston to compete with it. After the author's geometric image paper was published, the technical director of ATI's research department approached the author. At that time, the structural design of the GPU was not fully formed. There were two pipelines inside the GPU, one processing texture images and the other processing triangular meshes. The idea of ​​geometric images is to use images to express surfaces, thereby replacing triangular meshes, which can greatly simplify GPU hardware design. At that time ATI was very interested in this technical approach. Of course, ATI has now been lost in the dust of history, but this idea has been reborn on Unreal Engine.

Unreal5 ，nanite virtual micropolygon technique

The core issue of game engines is how to strike a balance between rendering speed and geometric quality. Overly complex geometries require a large number of triangles, making it impossible to achieve real-time rendering. This is mainly because the data structure of the triangular mesh is too large to be placed in the GPU's memory. At the same time, the topological relationship is complex, making memory addressing difficult. Previous versions of Unreal Engine combined virtual memory technology with texture mapping technology to support texture images with huge amounts of data in real time; the current version represents geometric surfaces as geometric images, with the red, green and blue of each pixel representing the three-dimensional coordinates of the corresponding vertex, thereby unifying geometry and texture, and promoting virtual texture technology to virtual geometry technology. This improves the quality of complex 3D games by several orders of magnitude.

Geometric image generation method based on algebraic geometry principles.

Following the rise of the Metaverse, many companies began to plan Metaverse rendering engines. Since the Metaverse merges the real world with the virtual world, the amount of geometric data is bound to be unprecedentedly large. Real-time rendering in this situation relies heavily on virtual geometry technology. Converting traditional triangular meshes into geometric images is a very challenging problem that is intrinsically tied to surface quadrilateralization. After years of thinking and research, the author's team finally recognized that the latter is equivalent to the representative class theory of holopure line bundles on the Riemannian surface.

In history, countless scholars and engineers have studied this problem, and there are various empirical algorithms, but they all remain at a relatively phenomenological level and are often limited to treating headaches, treating headaches, and treating pains. By applying the profound principles of algebraic geometry to 3D technology, we may be able to effectively promote the development of virtual geometry technology.

3D printing

Twenty years ago, the first 3D printer company, Z-Corp, appeared in the suburbs of Boston, selling each unit for $40,000 to $50,000. Twenty years later, 3D printing has entered ordinary households on a large scale, and the companies that occupy the largest share of the North American market are basically from Shenzhen, and the price of each unit has dropped to about US$400. A large number of 3D printing materials are also produced domestically. Looking at a 3D printer, the core components are precision-controlled stepper motors and ball screws. Due to the optimization and integration of the domestic industrial chain, it is currently very affordable and high-quality, which indeed shows the great progress of China's manufacturing industry.

The users of 3D printing are no longer limited to special geeks, but have already spread to thousands of households. AutoCAD launches Fusion 360, which is very convenient for everyone to design 3D objects by themselves. It has a friendly interface, stable calculation, convenient and practical. Specialized 3D websites have emerged. You can search and download the 3D items you need, such as water cups, mice, Rubik's cubes, etc., and then print them out and use them directly. The author often needs to design some optical experimental equipment. In the past, aluminum alloy materials were processed by CNC machine tools, which was very time-consuming and labor-intensive. The availability of 3D printing equipment is very convenient and greatly improves the speed of scientific research. In 2021, the author gave his scanned, modeled and 3D printed sculptures as gifts to friends who came from a distance, which changed the previous way of socializing. In 2021, the author and my friends also discussed the technical path of 3D printing on curved surfaces and color 3D printing. I believe it will become a reality soon.

Of course, because 3D geometric modeling and design is very time-consuming and laborious, people are very enthusiastic about NFT technology.

In traditional Internet companies, most of the content is created by ordinary users, but the benefits belong to the network platform. This distribution method is naturally unfair. Through NFT and blockchain technology, each inventor’s invention rights can be guaranteed not to be infringed. The NFT encryption mechanism is essentially based on the arithmetic theory of algebraic curves, especially elliptic curve encryption, which is another profound application of Riemann surface theory.

Ten years ago, one of my doctoral students joined a digital dentistry company after graduation. Ten years later, the author went for dental implants. From oral scanning to 3D modeling to 3D printing, the technology has been relatively perfect. A dentist couple friend of the author very much hopes that their children will learn computer technology, because 3D modeling and 3D printing technology are irresistibly changing the entire dental field.

Currently, high-precision optical lenses and freeform-designed optical devices can be 3D printed; metal accessories can also be 3D printed. 3D printing additive manufacturing is revolutionizing the entire manufacturing industry. Two or three years ago, a doctoral student in the author's team went to a topology optimization company. At present, the company's value has doubled. Topology optimization and computational mechanics have become the growth points of the manufacturing industry. A large number of products made with topology optimization technology have appeared on the market, such as various seat cushions, car bumpers, etc.

In 2021, the author's friend's child went to a geometric search engine company after graduation. With the popularization of 3D technology and the large-scale price reduction of 3D cameras, there will be a large number of 3D models on the Internet. How to search these models is a very challenging practical problem. The author believes that more profound differential geometry and algebraic topology theories will increasingly penetrate into this industry, and the most appropriate theoretical tool should be Teichmuller's quasi-conformal geometry theory.

Outlook

Twenty years ago, the most popular keyword in the scientific and technological world was "neural network"; twenty years later, the most popular keyword in the scientific and technological world is still "neural network", but its depth and breadth are no longer the same. History has been spiraling, and the preferences and choices of engineering technology have always followed the historical law of negation of negation.

2021 is the year when 3D geometry technology explodes. Real-time ray tracing algorithms, virtual geometry technology, and 3D printer prices have dropped by several orders of magnitude, giving rise to 3D design network exchange platforms and 3D search engines. Due to the large-scale popularization of MEMS devices and the improvement of CMOS sensor quality, 3D cameras have also begun to reduce prices by several orders of magnitude. It is foreseeable that society will have great demand for 3D point cloud and digital geometry processing software; Metaverse and digital twins will further promote the development of virtual geometry technology; 3D medical technology, additive manufacturing, and topology optimization will continue to develop rapidly.

For young people, the knowledge structure and programming skills required by 3D geometry technology are very different from traditional network technology and deep learning technology. It often takes several years to understand abstract and profound geometric topological concepts, such as the often mentioned Riemannian metric and layer cohomology. The current standard curriculum of computer science departments around the world is very lacking, and mastering these theories is often more difficult than pure engineering skills. Any high school student can learn a classic algorithm in 3D vision in two weeks, but cannot understand the profound meaning of the Riemannian metric in one year.

From another perspective, geometric programming has high standards for engineering capabilities. In the past few years, the vast majority of students have experienced systematic training in deep learning, but are unable to write an efficient and robust three-dimensional geometric data structure (such as volumetric dart library) from scratch. Generally speaking, if young people want to master geometric programming skills, they will need several years to hone their skills. The author knows many masters in the field of digital geometry, and they have spent decades honing their skills. Just as large-scale aviation designs around the world rely on French geometry software, 3D geometry technology requires years of tempering and cultivation, especially persistent accumulation. We look forward to another major breakthrough in 3D geometry technology in 2022, and abstract modern geometric theory to be further integrated into this rapidly developing field.

Machine-translated from the Chinese original 2021三维技术回顾 (published 2022-01-03). WeChat original ↗