Recently on tenure, someone came to congratulate: “Now you can freely decline review requests!”. I thought about it, and it seems that this is really the case for the change in mentality. I thought maybe I could write something to commemorate it. Then, from the age of 19 to 31, is there anything to remember? There seems to be a lot, but if you don’t organize them, you don’t know where to start. Then just write it directly. From undergraduate physics, to CS PhD, CS faculty, and mathematics tenure, this seemingly tortuous 12 years was actually doing the same research, and not a year was wasted. Along the way, there are many things worth remembering and summarizing, which may help to think about the future. By the way, I wrote down the awesome things I did along the way and the awesome people I met. It should be very refreshing to watch.
- Chapter 0: My Trident
- Chapter 1: Origin
- Chapter 2: One shot blasts out two pits
- Chapter 3: Romance of Snow and Sea
- Chapter 4: Friction Friction, On Slippery Roads, Friction
- Chapter 5: Young Hero Hu Yuanming
- Chapter 6: Getting to know timestep
- Chapter 7: The third battle of friction and collision, the IPC magic boy comes into the world
- Chapter 8: The Next “Timestep”
Chapter 0: My Trident
In the past twelve years, I have done some physical simulation-related scientific research for computer graphics. There are three representative directions of the shot: Material Point Method (MPM), Affine Particle In Cell (APIC), and Incremental Potential Contact (IPC). The people and things of each method will be recalled in the following chapters. In this chapter, a general overview will be given first.
The first direction: MPM. When it comes to the material point method, according to the usual practice, you may have to mention the Frozen that you have participated in more or less. After I discovered MPM in 2012, I did something else, and other students in the group used MPM to verify snow; I didn’t participate in the original SIGGRAPH work in the early days. The code of Disney Studio is very bloated, far more than 99 lines, and Disney’s lawyers are not vegetarians, there has always been a desert island survival painting Mickey said. Since you can’t describe too much code, just put good stills:
It became a stereotype that MPMs were good at making snow in the short term. So I decided to spend some effort to reshape the image of MPM. From a technical point of view, MPM is just a basic Galerkin space architecture. The real technical point of numerical simulation of physical process lies in the discrete algorithm of time and space, the design of constitutive model, the acceleration of performance, and the ingenious solution of numerical solutions of partial differential equations. different means. MPM is a high-quality canvas, and the innovation of these technical points is the real stroke. But the technical point is the lining, and the MPM is the face. So what I can see from the face is that I and a group of like-minded people use MPM to flatten all kinds of solids and fluids in the physical world: chocolate, jelly, bread, toothpaste, ice cream, foam, mud, lava, steak, Dongpo meat, oranges, watermelons, muscles, bones, internal organs, fabrics, sweaters, hair, snow-capped mountains, sandy seas, glaciers, rivers, drones, explosives, etc. There are solids, Newtonian fluids, non-Newtonian fluids, granular bodies, solid-liquid mixtures, and human bodies. As big as mountains and rivers, as small as rain and dew, MPM has gradually expanded from an iron-headed skill to a book of seventy-two stunts.
Later, I started a company with people and wrote a practical MPM special effect solver. Recently Autodesk bought it and put it into Maya. I believe that in the next few years, more movies will see the application of MPM.
The second direction: Affine Particle Cell Method (APIC). This is my proud article in 2015. It was completed by myself in Disney’s Big Hat studio during Christmas 2014. Burbank, where Disney is located, is a desert city in the Greater Los Angeles area, but I became attached to the desert and the sea. So that year, APIC enhanced the water in Pocahontas with many rich details.
Fast forward to 2017, a young man surnamed Hu came to visit me, and together we pushed the APIC and MPM series work to a climax: Moving Least Squares MPM (MLS-MPM). Among them, the origin of @taiji graphics and the expansion of MPM in the field of differentiable simulation have been well documented.
The third direction: IPC. On December 31, 2020, the Computer Graphics Center of the University of Pennsylvania, at 23:59, the coffee in my hand was still hot. There was a stone that filled the sky. It was filled with the essence of heaven, earth, aura, sun and moon, and suddenly burst open. Incremental potential energy contact method IPC was born. Po Wang sells melons and brags: I secretly believe that IPC improved solid simulation, started the “industrial revolution”, and brought the simulation science of continuous solids (not only in graphics) into the “steam engine era”. In 2022, its spinoff story continues:
Chapter 1: Origin
In 2010, I met three people who changed my life. The first person is my wife; in these twelve years, we have been in love for five years and married for seven years. Every decision I have made in the past 12 years is the right decision in retrospect, ranging from career paths to meticulous words. Behind many of my far-reaching choices, she has silently paid and spent time without sleep to accompany me to demystify and analyze them rationally. . I majored in plasma physics in the junior class of the University of Science and Technology of China. I wanted to switch to computer science after enrolling at UCLA in 2010. If it wasn’t for her to calm my impatience and help me plan reasonable steps, I might not have even completed my first semester. After reading it, I gave up on myself and didn’t know what to do. She will accompany me a long way.
Two other people who changed my life in 2010 were my PhD co-tutors Demetri Terzopoulos and Joseph Teran. Their achievements are the goals of my life.
My supervisor in the UCLA CS department, Demetri, is an academician of the Royal Society (joint with Newton, Benjamin Franklin, Hawking, etc.), an Oscar winner for technology, and he was the first person to do physical simulation in computer graphics in the 1980s. Father of the Metaverse Physics Engine. He is also a computer vision guru and invented the snake algorithm. In fact, together with Hinton, he published the world’s first graphics article using neural networks for physical simulation more than 20 years ago, which seems to be often missed by people. My co-advisor in the mathematics department is Joseph, a colleague of Tao Zhexuan (and I am now), the grandson and colleague of Stan Osher, the inventor of level set, who was once named one of the 20 smartest brains under the age of 40 by discover ( 20 Best Brains Under 40 ), he is the most famous person in graphics doing finite element solid simulation.
In the fall of 2010, I contacted Demetri with a friend, as well as teachers Joseph and Zhu Songchun. Teacher Zhu gave a very rational answer of disapproving of my transfer. (Later, Mr. Zhu changed his opinion on me, joined my doctoral committee with Osher, and later formed a close academic cooperation relationship through a close friend, now Professor Zhu Yixin of the School of Intelligence at Peking University. This is a later story.) Demetri and Joseph risked a lot of The risk of big financial waste in the lab, looking at my crappy spring simulation code (written in MATLAB), but considering that I have published papers related to relativity before, I should not be stupid, and gave me a chance. I quickly ate Red Bull, spent several nights forcibly reading through a textbook, and reproduced a siggraph article on finite element muscle simulation. Such behavior is the most concise and effective means of impress graphics professors. It has been out of control ever since.
Writing code and graphics, I’m very late to entry. @HU Yuanming has written a rigid body engine game in junior high school, and I am still learning C++ templates by myself. Like many aspiring graphics or gaming enthusiasts, building your own engine from scratch is an irresistible urge. At the beginning of 2012, after completing all computer and applied mathematics courses, I combined my physics background and figured out a long-term goal: to reconstruct the world with physical simulation. Demetri also encouraged me: you are more suitable than anyone else to close the gap between virtual reality and physical reality, to open up the virtual world with the physical world. There was no such thing as a metaverse at that time, but my two mentors were both deep enthusiasts of the digital double virtual human body, which had a great impact on my research interests. Going back to the concept of the physics engine, action is not as good as heartbeat. The world is ever-changing, so this engine is called the Rubik’s Cube, oh no, it’s ever-changing! And so ditto was born:
Ditto contains several hands-on projects for solid simulation and collision handling, especially 3D cloth simulation with implicit finite element. If there was taichi language at that time, it should be written to get an A+ as a major GAMES201 homework. Unfortunately, after Ditto has been maintained for half a year, I have devoted myself to the specific work of a siggraph article, and it has not been updated. Later, in 2018, the CEO of z-emotion /ZelusFX company suddenly contacted me, saying that the ditto code he asked me in 2012 helped him create a cloth design software company, and now there are many users. I was happy for a long time.
Chapter 2: One shot blasts out two pits
The first project I worked on for two years during my PhD was object fragmentation. Some people on the Internet say that computer graphics is one of the three major romances of programmers (the other two are operating systems and compilation principles), but I didn’t see romance at that time, only crazy and cool, and I just wanted to The most handsome demo on siggraph, be the most beautiful boy.
By then I had finished Computational Solid Mechanics. Like many beginners doing simulation, everything starts with simulating jelly, after all, jelly is the most typical elastic body, and tends to be very soft, and does not bring too much stiffness to the time-step discrete format of ODE (ordinary differential equations). Either the dt is small, or the numerical problem is intractable to the system. So in the elastoplastic solid, I found a case that I wanted to simulate: a bullet shot through a jelly. At that time and even today, there are not many more cool live-action videos than this:
During my current teaching period, I often tell my students what scientific research they want to do. After roughly investigating the relevant work and determining the academic grade and potential influence, they can start coding directly, and don’t worry too much about the lack of technical contribution. Because after you start, you will soon encounter problems that you probably did not expect before, and solving them will be the main contribution of your article. We used finite element to write jelly breaking, and within half a month, we encountered two major problems: (1) how to break naturally, that is, the ugly appearance of triangles cannot be seen on the split surface, and (2) how to robustly Handling frictional collisions between complex fragments.
Which topological change is stronger, levelset dares to be king. To achieve natural fracture, it is a very clever idea to combine finite element and level set methods. The level set is very flexible, can split the tetrahedron from various natural angles, and can completely avoid remesh.
Stan Osher, the inventor of the Levelset method, at UCLA, gave us some valuable advice, and soon the cracking problem was solved.
In this article, my main responsibility is to do friction and collision. After the modeling broke, this was the next biggest headache. Levelset’s marching tetrahedra cut resulted in countless “disgusting” shapes of jelly shards: on the split face, some were triangular as thin as a bolt of lightning, while others were as flat as a pie. In computational geometry, these peculiar triangles are called “ill conditioning”, and we want to use ordinary geometric methods to deal with their collisions. Not to mention the cases of the collision algorithm itself, it is difficult to list the cases. Misjudgment is enough to make people sigh. I spent a year trying out many algorithms and failing.
The most worthwhile algorithm is a very bold idea. I project the solved solid onto a regular grid, then let the grid pretend to see an incompressible fluid, solve a Poisson equation, make the velocity field divergent-free, and interpolate back to the solid . This actually gives a very nice impenetrable solution! But the disadvantage is that the movement of the object is changed to be too light and agile like a fluid, and it lacks the stubbornness that is unique to the solid. I went to ask my mentor Joseph if there is a method for solving solids similar to this method for solving fluids, and I want to try it on collisions. He recalled for a long time and named me a name that I continued to focus on for ten years: MPM.
MPM was invented in 1995 in a national laboratory in the United States. It is a solid solution method that mixes Lagrangian particles and Euler grids. Going back to the Particle-In-Cell (PIC method, originally used to solve Maxwell’s equations in plasma physics) in the 1960s and the Fluid-Implicit-Particle-Method (FLIP method, used for fluid settlement, originally used for solving plasma physics) in the 1980s Mentor Robert Bridson, my uncle, introduced graphics in 2005). Like a fluid, it automatically prevents penetration between materials, and it can solve equations for solids beautifully. Taking the MPM over for collision processing, in my opinion at the time, couldn’t be more appropriate:
Finally, I handed in an answer sheet that is far from perfect in retrospect:
The size of this bullet is a bit exaggerated, more like a cannonball. It was named Best Paper Award at SCA 2013. It also exploded two academic pits brought by MPM: multi-materials with topological changes, and frictional collisions handled automatically. MPM and I were brought together, from ambiguous to addicted.
Easter egg: The article also tortured an armadillo for the first time, causing discomfort to many readers of the article. But later this scene was followed many times by other researchers as a benchmark, so it’s not my fault.
Chapter 3: Romance of Snow and Sea
During the few months of learning MPM, Alexey, a Russian brother in the same group, also joined the fan team and led the widely circulated article “MPM snow”. For a time, the marriage between our group and Disney became a legend. Several students, including myself, went to Disney to intern and participate in writing Production software code. At the celebration feast of Frozen, I tasted the joy of technology industrialization for the first time.
After Frozen, Disney made a Big Hero 6 super marine. There, MPM was used to simulate some strange material, a message that wasn’t much publicized.
Disney’s Big Hero 6
Time then shifted to 2014. I plan to graduate with a Ph.D. and want to do something more mathematical and basic in MPM and PIC. At the same time, I hope to make useful changes in the existing FLIP fluids and MPM solids. So looking back, what is the unreasonable mathematical hack in the process of using FLIP for fluids and MPM for solids? The insider will definitely point out: it is the FLIP-PIC blending ratio. FLIP and PIC can actually refer to the step of interpolating the grid to the particles in the hybrid particle grid method. PIC directly interpolates the velocity field, but will introduce huge numerical viscosity, FLIP interpolates the velocity increment, but will introduce huge instability. So in 2005, Professor Robert Bridson, a fluid master in graphics, proposed to multiply the FLIP result by 0.97, then multiply the PIC result by 0.03, and then add them up. This number is a user adjustable parameter, but adjustable but not controllable! Different numbers will give very different results in different scenarios. It’s an artist’s nightmare, an obsessive-compulsive hell. So I decided to take a big vote and get rid of this thing, because I have a belief that a simulation algorithm that needs to set heuristic parameters can never be the final form of a good algorithm.
Combined with the theoretical analysis of the angular momentum conservation equation, skipping some technical details, Affine Particle In Cell (APIC) was deduced by mistake. FLIP fluids and MPM solids enter a new chapter, making it easier for artists to get the viscosity they need for simulation results, whether it’s mountains, rivers, or lava. In my heart, they are a romance comparable to ice and snow.
Disney is very happy and can’t wait to use APIC in Moana:
In the summer of 2015, I graduated and got married. The wedding was in the glass cathedral south of Los Angeles, with mountains, seas and trees. At SIGGRAPH that summer, I met many, many like-minded friends. The deepest impression is that in the fluid session, I saw a suave silver-haired teenager. He came to me and asked, “There are so many good articles this year, which ones can be circulated for a long time?” I dealt with them casually. He said: “This year’s articles, there are two most diao, one is my IVOCK , the other is your APIC.” I was surprised, and quickly exchanged names. It turns out that this domineering young man is called @张心新. He is now leading “Zesen Science and Technology” to fight for Chinese special effects. At that time, pure us, in the reflection of each other’s eyes, all saw a brave man, holding a giant sword that we had built, and challenging an evil dragon called numerical dissipation in blood. Since that day, we have also started working side by side for the past seven years.
After graduation, I continued to work on MPM solids and fluids. People in academia actually like to set up flags. I have always tried to stick to a basic principle: even if my simulation articles are submitted to graphics conferences and journals, I will never do any hacks that do not conform to the principles of physics and mathematics for visual effects; I need every algorithm All apply to the entire computational physics. This principle has brought many benefits to me during the later teaching period: including (1) the favor of the Natural Science Research Fund, (2) the MPM natural disaster prediction technology (avalanche, landslide, mudslide, glaciers) published in the Nature sub-journal fragmentation, tsunami),
And (3) the hospital’s favorite virtual trauma and surgery simulation platform:
They may not be as romantic as the snow and the sea, but they have a more real and direct impact on the world, and even help save lives. This work has also earned more respect from the physics simulation colleagues in graphics in the natural sciences and medicine, correcting the misconceptions of those in other fields that graphics are constantly importing what they do. After all, many graphics papers like to call this contribution: “We introduce the XXX method to computer graphics.” What I want to do is to ask people in physics and mathematics to write the same sentence, but with “to” Change to “from”. A colleague of classical mechanics I met recently exclaimed: “What a wave of reverse output!”
Now that I think of the application of solid-state simulation in medicine, an additional flash of memory comes to my mind. In 2016, I especially wanted to industrialize the virtual human body, and I also explored many different directions. One of the more interesting ones is the prediction of plastic surgery discussed with Ding Xiaowei, the current CEO of Voxel Technology, who is also a good buddy. At that time, I ran a demo of breast augmentation dynamics prediction (including a full-scale simulation of breast soft tissue, skin, and silicone prosthesis), and also chatted with some plastic surgeons in Los Angeles, but I felt that the market demand was not large enough, so I did not continue. go down. I don’t know how the Metaverse is becoming more and more popular today, and how this direction is going now.
[There is a video here, but I can’t put it]
Chapter 4: Friction Friction, On Slippery Roads, Friction
As mentioned earlier, in 2012, I used the idea of MPM to try to deal with the collision of objects in the crushing simulation. But that algorithm can only deal with collisions between different fragments, and has nothing to do with self collision. MPM is a discrete format that uses particles to describe objects. After all, it is naturally most suitable for particles like ice, snow and sand.
Cloth and fur are something that everyone who does solid simulation wants to conquer. Scientific research should try to be people-oriented, and the relationship between cloth and hair is really too big. There are many algorithms for dealing with friction and collisions, and they are all equally good at what they do well, but varied in what they do badly. So in 2017, I returned to the battlefield of friction and collision. I, who was in a 105-degree love with MPM, chose an idea that no one had thought about: using MPM plasticity to challenge this topic.
By then I had learned the Druker-Prager plastic yield surface and had successfully made MPM sand from it. The constitutive model of sand has two elements: first, it supports separation, but does not support extrusion; second, when it slides up the edge, the tangential force and the normal force must satisfy the Coulomb friction law. After careful reflection, these two characteristics are obviously not only unique to sand! Cloth, hair, rubber, rigid body, etc., which common solid collision does not follow these two laws?
So I decided to abandon the traditional concept of friction and collision based on the geometric intersection of points and triangles, edges and edges (the one implemented in ditto), but to adopt the MPM “continuum mechanics” point of view. No matter if it is fabric or hair, it is just some continuous space occupied. In this view, the only difference between them and sand is that sand is a three-dimensional “body”, and they are two-dimensional and one-dimensional surfaces in three-dimensional space, respectively. Thinking of this, everything suddenly became clear: if Drucker-Prager plasticity can make the three-dimensional MPM sand meet the properties of friction and collision, then I only need to deduce the corresponding plasticity in the two-dimensional and one-dimensional subspaces, and I can make MPM cloth and hair meet the same automatic friction and collision properties!
Taking cloth as an example, through the QR decomposition of the deformation gradient, we can design a delicate elastic energy and plastic yield surface to “manage” the stress conditions that the cloth needs to meet in the normal friction and collision force. Intuitively, in the direction of the curved surface, the cloth is like bundles of interwoven sand and gravel. Looking along the tangential direction of the cloth, the two words “Kulun” are written all over the cloth.
Realizing this, dealing with friction collisions with one-dimensional, two-dimensional surfaces is no different than dealing with friction collisions with three-dimensional sand. Just write this new constitutive model to the vertices on the surface, and MPM silently handles the rest automatically. From cloth to fur, from carpet to sweater, all traditional collision detection and collision processing are abandoned, and a handful of particles and a mesh can generate a beautiful animation. This subversive modeling method, when I look back now, still thinks that it has stepped out of the devil’s pace and is the most satisfying MPM paper in my academic career.
That year, I went to siggraph 2017 to preach the material point method. The emotion I expressed can only be described by the classic lines of the late teacher Lee Shau Kee, “It’s more poetic than my first love.”
The 2D version of this article has also been implemented in Taichi language ( Orange Cat: Taichi implements 2D Anisotropic Elastoplasticity Cloth ), the code is very concise and wonderful.
Later in the second year of SIGGRAPH2018, Columbia University came out with a stalwart @Raymond Fei , combined this footwork with APIC, and did an amazing work on the interaction of cloth and water ( libwetcloth ), 100% pleasing to the eye.
At SIGGRAPH 2017, I had an additional purpose: to recruit my first student. At the time of the meeting, I was alone at the beginning of my assistant professor career at the University of Pennsylvania. There were feasting parties and bustling bars. I was looking for a little friend who could chat and laugh together for a few years outside the venue at night. Advanced hunters disguise themselves as prey. In a dimly lit corner, I saw a familiar figure drinking alone under the moon, watching me. Wasn’t that @李敏陈, who was introduced to me by Zhang Xinxin at the barbecue restaurant a year ago? I remember him! A strong and handsome guy from UBC wrote a fluid article with Zhang Xinxin. I ordered two fiery apple martinis and wobbled over. “Remember me?” “Remember, come and make a cup!” That cup kicked off the next five-year academic banquet.
Chapter 5: Young Hero Hu Yuanming
The summer of 2017 is destined to meet more extraordinary people. The story is divided into two parts. Earlier in the year before Li Minchen first met in a bar, such an urban legend was widely circulated in the field of graphics. There is a young warrior who rides a horse and whips the whip. He has not published a SIGGRAPH paper, but he has implemented a hundred; he has not open-sourced a set of code, but he has a million lines to be released; the graphics he took over Learning to simulate the implementation, the efficiency can be increased tenfold overnight; he did not sleep for three days, he reproduced all the MPM papers in the past four years, and proposed a hundred ways to improve. Is he the incarnation of a fairy? Or the messenger of hell? Rumors arose for a while, and some even said that he was going to establish a new computer graphics order. I still can’t sleep at night thinking about the MPM problem. Where is this boy holy?
As expected, he came to the door. @Hu Yuanming , who was as beautiful as imagined, took a friend who was more mysterious and shy than him, and killed me from Tsinghua to the door of my UPenn laboratory. “We’re here to do MPM with you.” His words were short and powerful. “Okay, let’s get started.” At that time, we didn’t talk politely. We only needed to see a common research goal and everything was silent. At that time, the little helper he brought was called Fang Huoao, I went to google, oh, Fang Yanyù. The reality is by no means smooth sailing. We have experienced some failed scientific research projects in high-speed iteration, and finally we have the invention and follow-up of MLS-MPM, which is concise and wonderful.
At that time, I had a set of my own C++ library, far more than the ditto of the year. My library is called “jixie” (mechanical). Hu Yuanming brought his library, called “taichi” (Tai Chi). At that time Tai Chi was still a C++ library. The two libraries have their own merits, and they collide with many warm sparks. Hu Yuanming has played a very inspiring role in the research focus of my assistant professor career, especially in the pursuit of draining computer performance.
Heroes cherish each other, and we must say goodbye. Hu Yuanming will go to MIT to do other projects. I will say goodbye at the pizza shop. “The development of MPM will slow down!” I was disappointed. He smiled and told me that there was still one person who went with me to play MPM multi-physics simulation. I glanced at it and woke up suddenly. During this time, there was another hero boy who was younger than him while chatting and laughing together in the shadow of swords and swords! He doesn’t speak much, but on the battlefield of scientific research, although he is not as dazzling and gorgeous as Hu Yuanming, he exudes a more fierce fiery.
Fang Yi became my second student. If Minchen is a cup of strong wine, and the background is gradually mature, Fang Yi is a bloodthirsty knife, more and more sharp and cruel. In the following 5 years, he achieved the speed of the realization of old papers and the attempt of new ideas like Iai Slash, and he was killed with a knife.
During those days, under the hard work of Fang Yi, Min Chen, and other fighters, we have been promoting high-performance MPM multi-physics simulation, until the simulation of billions of particles has become easy and freehand. Through cooperation with the Supercomputing Center, we have developed MPM to a supercomputer capable of exascale computing, which can calculate 10 to the 18th power of floating-point operations per second. In this way, we are serious about the pursuit of high resolution.
Later, my lab brought together a larger group of high-spirited children, Qu Ziyin@ziyin ( ziyin: Beijing Film Academy issued a top computer conference paper full of mathematical formulas and open sourced its code ), Qiu Yuxing , @王新乐, Li Xuan, Chen Yunuo, @Cao Yadi , etc., they revolved around the C++ simulation engine ziran (natural), which was dominated by Fang Yi, and played in the ocean of physical simulation. Their elegant academic dance music is still being written, and with them by my side, I feel that I have captured my youth forever, and every day is an academic “cake breaking party”:
To break bread is to affirm trust, confidence, and comfort with an individual or group of people.
On the historical mission of helping human beings get through the virtual world and the real world, we are committed to emulating this point and spreading out tens of thousands of branches and leaves with the hard core foundation. The following are the directions that my lab has been researching over the years. These achievements are also full of precious experience and help from predecessors such as Professor Zhu Songchun of Peking University, Professor Chen Baoquan, and Professor Tang Min of Zhejiang University.
Chapter 6: Getting to know timestep
The walker is the foundation of one’s whole body and the pivot of movement. – “Ten Essentials of Taijiquan”
In the “infrastructure” of the Metaverse, if modeling is internal skills and rendering is moves, then physical simulation is footwork or movement. Footwork is closely bound up with time and movement, differentiate and integrate in time, predict the future from the past, and use the future to guide the past. (To guide the past, it relies on differentiable simulation.) Whether it is the Limbo microstep of the Freelance School, Tyson’s butterfly footwork, or Olajuwon’s dream footsteps, they all reflect a truth: there is a mature set of steps Law is a reliable guarantee for a master to be invincible.
In dynamic physics simulation, one of the most common words is timestep: time step, Delta t. The process of forward physical simulation is often the process of integrating differential equations on the time axis in essence. This process is also called timestepping method; I would like to translate it as “time stepping method”.
Time in reality is continuous, but time in simulation is discrete. For a 24 FPS animation, the ideal situation per second is for the simulation algorithm to take 24 steps forward from a past moment, each step taking 1/24 of a second, generating 24 geometric shapes. Unless you want to pursue more extreme accuracy in the approximation of reality, a general graphics algorithm should preferably have the ability to only take 24 steps. If you predict that you need to take 48 steps, or 240 steps, 2400 steps forward for 1 second, then the efficiency will often be doubled.
Unfortunately, until around 2015, and even today, there are still countless graphics simulation algorithms that require substeps. What’s more painful is that even after taking substeps, the vast majority of them still cannot guarantee the stability of the value, commonly known as “burst”:
Misplaced picture. The burst simulation actually looks like this:
If the simulation explodes, it means that you have to adjust the parameters and run the program again. I was an intern at ILM in 2011. My intern tutor told me that ILM was helping the Hulk of the Avengers to design a muscle simulation algorithm. When the Hulk exerted force, the program exploded, and the rerun could not stop. The delta t can’t be too small, and the air conditioning cost of the computer room will cost millions.
To be able to take steps of 1/24th of a second or more, I started working on optimization-based time-pacing. Non-linear non-convex numerical optimization is a very powerful field, and the entire neural network and deep learning rely on it today. The most fundamental physical law of this universe: the second law of thermodynamics (the principle of increasing entropy) itself defines an optimization problem. Therefore, more and more applied mathematicians begin to rethink the numerical solutions of dynamic partial differential equations with the ideas of optimization and variational methods.
The equation for an elastic body simulation is an optimization problem that can be redefined as finding a minimum! Under this framework, the time step can be made arbitrarily large without breaking the egg.
There is a lot of work here, and the early work in graphics is more representative, including Liu Tiantian’s ingenious projection dynamics “Projective Dynamics: Fusing Constraint Projections for Fast Simulation” in 2014 and his 2017 “Quasi-Newton Methods for Real” -time Simulation of Hyperelastic Materials” ( 2019 (8th) University of Science and Technology of China “Frontiers of Computer Graphics” summer course_bilibili_bilibili ) ( Freezing Point Blue: Frontiers of Computer Graphics (2019) Towards Real-time Simulation of Deformable Objects ), and the relatively decent Newton’s method “Optimization Integrator for Large Time Steps” that I participated in in 2015. My lab later focused on the following four places:
Li Minchen combined the quasi-Newton method with domain decomposition in 2019, defeated a series of competitors, and obtained a very high-speed finite element elastic body solution Decomposed Optimization Time Integrator “DOT” (point-point finite element method):
Wang Xinlei took a different approach, considering multi-scale grid multigrid, allowing MPM to reach a large time step, and invented the Hierarchical Optimization Time Integrator “HOT” (hot material point method), which can efficiently handle super “hard” elastic-plastic bodies , to aid in the simulation of engineering mechanics design:
方燠则跳出牛顿和拟牛顿的思路，以“快”为目的，把MPM的加速结合上了交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）上。这个方法被称为“Silly Rubber”（愚人橡皮法），可以快速模拟各种MPM适合的材料，比如奶油：
我们最为得意的，也是最新搞出来的，便是李轩、李旻辰和我一起用几支烂笔头推导出来的SIGGRAPH 2022论文Energetically Consistent Inelasticity （ECI）。这个工作在数值计算理论上，我认为有很可观的意义：它首次让塑性力可以迈着同样大的步伐，被真正隐式求解了！也就是说之前的方法，包括上面提到的，都不准，都对塑性力做了一个强相关于delta t 的其实很不准确的近似。那算的准有什么好处呢？当然是去跟现实对照了。跟现实连定性的视觉效果都对不上的虚拟物体，步法不够稳健，不能叫数字孪生，永远都只是游戏（没错， 这里说的的正是PhysX/PBD）。我们的坚持，是第一性原理，是我们希望一直尽力朝着真正的数字孪生方向前行的一些固执的原则。
第七章：摩擦碰撞的第三次战役，IPC魔童降世
开始的那些年，从最初level set fracture中的一炮双响，到MPM布料，我一直在跟“摩擦碰撞”这个难题对干。每一场仗都打的很漂亮，但都还是存在很多Limitation。以2017年的MPM布料为例，作为它的缔造者，我比任何人都能更清晰的看到它光芒下令我不堪面对的缺憾。作为一个MPM方法，它在隐式积分条件下性能非常差。它对粒子和网格的依赖给几何体强加了许多苛刻的要求：比如两者的分辨率需要尽量吻合。同时，它又像一台看似美好的特斯拉自动驾驶汽车，一不小心甩给你一个不大也不小的错误（数值粘性和偶尔的数值穿透），让你在使用时总是心怀忌惮。比如正如下图所示，MPM布料做毛衣虽然厉害，但是仔细看去，还是出现了许多穿透：
穿透会非常严重的影响仿真的精度和可信度。它不只是模型视觉上的错误，随之而来的弹性力和摩擦力也会因穿透而变得离谱和虚幻。因此，长久以来，至少在布料这一个小方向上，我并没有能够把MPM从特效和游戏的应用中打出去。换而言之，因我坚信元宇宙和游戏的最重要区别是对“准”的把握上（这也是我不认为NVIDIA的omniverse拿着一个基于不物理方法推导出来的PhysX引擎可以做成真正元宇宙物理引擎的根本原因），MPM在布料这个方向上要走的路还很长，还需要后来者的努力。
时钟拨到2020年前夕，没有征兆又似蛰伏许久的一件事情发生了。之前我把旻辰比作美酒，他便真的是这样一个学生，在陈酿的千锤百炼中一不小心就饱满丰厚，醇香持久。没几年，他便从一个学生潇潇洒洒地蜕变为一个成熟的合作伙伴。那晚，我郑重的告诉旻辰，“你刚完成的这个叫做IPC的项目，把一个困扰了计算机图形学和工程力学无数研究者几十年的一个领域给终结掉了，完美本无法触及，但IPC是我入行以来见过的，最接近完美的仿真技术。”在这一年后，旻辰以IPC斩获SIGGRAPH年度最佳博士论文奖，毫无悬念。
IPC的全称是Incremental Potential Contact，中文作增量势能接触，很拗口，还是就叫IPC吧。它的算法冗长而又毫不晦涩，刚猛而又不失优雅。在数值优化的框架下，IPC把所有基于mesh的物理仿真中“不许穿透”这个令学术界和产业界都为之痴迷的难题，从仿真问题的数学形态上就直接通过一个灵巧的定义给彻底毙掉了，其后的算法自然是如出入无人之境。“从此穿模是路人。”
技术上，IPC提出了一个崭新而又巧妙的关于“碰撞”的数学描述方法：所谓碰撞，便是在动力学过程的最小作用量原理下，要求任何非邻接几何表面之间的欧氏距离在连续的时间轴上恒大于零。它正是又一个timestepping的时间步法！如此一来，我们得到了一个可以用数学完美描述的约束优化问题。再配以些许精巧而不诡野的算法设计，最终的IPC技术在数学、算法和实现上都令人信服。毫不夸张的说，IPC是数值仿真自发明以来，唯一的把精确碰撞和摩擦这两个要求完美解决掉的办法。它唯一的缺点是计算效率不够快；被我们后来攻克，按下不表。
IPC及其2021年后续工作赋能了无数之前计算机仿真界根本做不了的事情，以绝对的稳定性、精确性、和数值收敛性涵盖了三维柔性体（“百万四面体的毛球”和“是绳子就坚持一百秒”）：
二维布料（轻松处理打结，和*任意多层*布料上身，这里只展示了四层，毕竟我们的建模制版技能点加的比较少）：
二维薄壳（跟真实的一叠扑克牌的厚度完全吻合，没有任何别的方法可以做到）（这是不是可以拿去开元宇宙赌场？）：
以及首次有“不穿透保证”与“精准摩擦力”两个性质的的一维细杆（面条、毛发）：
旻辰向来沉稳低调，他宣传IPC的文章（李旻辰：IPC: SIGGRAPH 2020开源有限元碰撞独家处理方案）也跟他的人一样靠谱实在。2020年1月，我在IPC的第一篇论文里，写下过这么一段总结（中文意译略有改写）：
“IPC技术适用于所有基于网格的固体模拟。无论是自碰撞、外碰撞、甚至是来自于低维曲面的碰撞，IPC都是一个绝顶灵活、有效、和无条件保证成功的解决方案。IPC对图形学和工程力学基于或不基于有限元的全部应用都提供了有史以来第一个几何不穿透，体积不反转的可证明的直接保证。从此以后，跑固体仿真只需要输入真实世界可以测量的物理参数和几何参数，而再不需要去调节所谓的数值参数。在此之上，IPC承诺必定能够对任意复杂的状态给出求解，并且这个解就是这个世界上现存所有算法能给出的，最接近真实世界摩擦碰撞结果的解。”
几年过去了，这个总结被图形学、机械工程、以及机器人领域的同行不断的引述和验证。作为一个学者，我从未如此夸过一个工作，毕竟有吹牛皮之嫌。但是IPC不一样，我不担心，因为这个牛皮是钢铁铸成，永远也吹不破。
IPC这么完美，还有什么可以改善的呢？正如上文所说，它的计算效率存在一定的问题。在我们一筹莫展之计，一位老友突然与我们取得了联系。此人名作阴阳（ @Yin Yang ），继胡渊鸣之后成为第二个让我瞧见八卦图头像便能开怀之人。克莱姆森大学的杨垠教授（现在迁去了犹他大学）姗姗来迟，他是降维仿真和GPU加速仿真的代表人物。我们一拍即合，开始建立深厚的革命友谊。自那天起，杨垠、旻辰和我开始了围绕IPC技术的一系列深度合作项目。在我们的思维火花碰撞之下，浩如烟海的脑洞和研发项目扑面而来。以2022年为例，我们便让IPC生态系统在刚体仿真和实时仿真两个方向取得了不亚于原始IPC的崭新成果。
第一个成果，是我们在刚体仿真上取得的重大成就。刚体与柔性体自古以来便被分开处理，求解它们的方法不能说是关系不大，只能说是几乎毫无关系。在IPC的加持下，我们提出了崭新的“Affine Body Dynamics (ABD)” 仿射体动力学，在淘汰传统刚体模拟的路上直接飙到终点，让刚体重新回归成它们在真实世界中的样子：即使最硬的物体，也会微小的形变，硬度是振金还是木头，该是多少就是多少，不需要被假设成绝对刚体。在ABD技术的加持下，我们在拥有所有IPC优点的同时，达到了媲美现有刚体引擎的速度和全方位碾压的精度。高速而又精准的机械体仿真首次成为可能。
真实碰撞驱动的齿轮：
及其受力分析：
带传动结构的小车（含简易气缸）：
及其传动引擎的简易气缸运动的可视化（活塞运动带动旋转）
铁链弹性波的传播：
比较传统的场景当然也不在话下：
值得一提的是，ABD在机器人抓取的任务上，已经被机器人领域的学界和工业界同行验证，其成功率和对接触力/摩擦力的准确性上，已经远远超过了PBD、Bullet、Mujoco等一众现有刚体引擎；强化学习在我们的solver上，轻松训练出了真正可以转化到物理世界的控制算法，误差之小，模拟过程之惬意，非机器人业内人士不可言喻：
英伟达Omniverse也宣传了很多工业机器人的场景，它的技术仍然基于PhysX（PBD），那套简单易学但毫无真实物理原则的手段。剩下的一切，还何须多言呢？也许在有些人心中，元宇宙只需要以假乱真，”看上去差不多就行了。”那么，就等时间给出“自然”选择的答案。
我从方法论上表述我自己的观点。我认为，像PBD一类的技术，以快为出发点，在当年的低下算力和就是面向游戏的两个前提下，无可厚非。但是由于对数学和物理原理的修改与简化，使其在元宇宙的未来想要从快到准，路途难如蜀道。与它们截然不同的是，IPC直接先把“准”这一步做到了几乎完美，那么在这个前提下，再做快有多难呢？在算数、算法、算力的三重加持下，IPC加速之路顺畅无阻。举例而言，我们2022年的第二个成果，便轻松地实现了多层布料的实时交互仿真，并且，没有牺牲任何IPC在碰撞上所承诺的美好保证：
第八章：下一个“Timestep”
十二年，我从C++都不会写的等离子体物理专业的学生，到拿到CS PhD，去常青藤做CS教授，再到UCLA应用数学拿tenure，回想一下，这其中竟没有一年被浪费，纯粹跟着喜爱的研究走，顺其自然。记得网上常有人讨论@计算机图形学的交叉学科本质。我想我本人应该就是一个不错的活标本吧。十二年的职业道路上，我也是无比幸运（毕竟射手座），遇到了太多牛逼的师长、同学、挚友、和学生，每个人都让我学到了很多。
那下一个十二年，我应该主要做些什么呢？思考了许久，不为立志，但求有一个计划。我想， “closing the gap between virtual reality and physical reality”，这个目标绝没有变，围绕物理仿真这一指引运动规律的轴心的原则也依旧在我心上打着思想钢印。在此之外，我与携有同样想法的三个人（ @李旻辰，方燠，杨垠@Yin Yang ）一起成立了Timestep，致力于稳健、精准、高效、普适的物理仿真“步法”及它们在不同产业中的应用，并在国内以及世界多地积极打造和布局一个可持续发展的体系。万水千山不停步，希望在下一个十二年，我们跟更多同道中人一起，通过有趣和有用的技术和想法把虚拟世界和现实世界真正打通。
来源：知乎www.zhihu.com
作者： 蒋陈凡夫
【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载
本文转自： http://zhuanlan.zhihu.com/p/560415998?utm_campaign=rss&utm_medium=rss&utm_source=rss&utm_content=title
This site is for inclusion only, and the copyright belongs to the original author.