A Scalable Galerkin Multigrid Method for Real-time Simulation of Deformable Objects - full talk

hello everyone this is attention from Microsoft Research Asia today I'm going to talk about our super of age of 2019 work a scalable gallery multigrid method for real-time simulation of deformable objects the former bones are everywhere in our real world my closest deformable or hares are deformable if you punch me in my face you may also find it deformable they are after essential elements in their virtual world providing us nice experiences in many applications such as animations games or virtual surgeries you name it the state-of-the-art deformable simulators such as projective dynamics suffer from scalability problems around slowly own large meshes such as this octopus which point 1 million tetrahedra our goal was to produce visually similar results with much better performance like shown on the right when talking about performance let's first take a look at a common pipeline to simulate a deformable object it can be as simple as this euphy the current state as an initial gas tun an optimization framework and it spit out the next day for you you keep iterating this days and finally get an animation and to solve the optimization problem a successive linearization is usually required bringing the linear solve as the main bottleneck for most of the large-scale simulators many works down to accelerate this linear self over a decade for example there are methods using pre factorize the system matrix to approximate the real stiffness matrix like projector dynamics there are also methods trying to apply iterative solvers to the nonlinear optimization problem directly such as position base the dynamics or the chebyshev some are iterative solver the scalability of those full space approximation methods usually gets hindered by a third a high memory cost all a bad convergence behavior subspace masters provide a very nice solution for fast simulations since these master restricts the size of the linear solves to be fairly small however the motion of the corresponding simulation is also restricted by the choice of the subspaces the multi grip mastered of course is an intuitive solution when we want to solve large linear systems since our method is also a multi grease over here I like to elaborate it a bit more the key idea of the multi grid is to only solve a linear system very crudely using a few Jacobi or gauss seidel iterations which are referred as smoothers and then pass a residual to coarser levels to be further smooth then the course-level passes the correction backed with final levels and do we do some extra posted smoothing through the system to get an approximated solution the balances of a multi grid structure come from two aspects first usually the solvers of course linear systems are cheaper compared to final level ones because they are smaller second the iterative solvers are working as smoothers they eliminate high frequency errors pretty well and a low frequency error that a smoother cannot handle becomes a high frequency one in coarser levels this is a holy grail of the multi grid method just keep in mind we are going to use this piece of information later so how do we set up the multi-resolution problems we can either set up the problems geometrically from Reedus creation of different resolution meshes but that needs some expertise to set up and is currently limited to regular grid structures or we can use galerkin projections to recursively set up the a matrices this one is much simpler to set up and it should work for any meshes and any restriction and prolongation schemes however it just does not work well with trivial pics of you matrices what we want is to inherit all the nice points from galaxy multi grid methods and make it scalable now that you matrix is a prolongation matrix that passes cross level correction into the final levels who also use you transpose as the restriction matrix that passes the final level residuals to coarser levels to make the entire system symmetric so let's see how do we build our multi grid to build this we first uniformly sampled across all have over desist from final levels using furthers the point sampling and then we want to build an interpolation scheme that can be used to pass the information between levels as we know that you matrix the U matrix is an interpolation matrix that determines two things first it decides the degrees of freedom of course a level nodes what kind of information do we want to interpolate alright and second it decides the interpolation weight which is how we interpolate the key idea of our and mastered answer these two questions exactly to be more specific we allow course level nodes to move in and higher dimensional coordinate and we use piecewise constant ways to interpolate them we first lift the degrees of freedom of a coarser level nodes from 3 to 12 which lies in an affine transformation space we called it skinning space coordinates because we were inspired by alex 2012 secret paper the fast automatic scanning transformations this space encodes more geometrically meaningful information such as scaling shearing linearized rotation and translation compared to the traditional positional space and we find it it will be useful to cut down the size of coarse grit more aggressively typically an order of magnitude smaller and the second thing we want to do is to decide the interpolation weights between two resolutions here we are only going to use piecewise constant weights which is the kind of counterintuitive why well um we actually try smooth weights at first but they have problems let's say there are two notes now v1 and v2 from the fine level and v1 is smoothly controlled by n cross level nodes shown in red and v2 is controlled by M course level nodes shown in blue any edge between v1 and v2 in the fine level which is one single nonzero in the matrix will end up with M by M non-zeros in the coarser level matrix u tau this is very common to see in an unstructured mesh making the sparsity of the course-level matrix is much worse than it should be and those non zeros will be passed further into deeper levels causing many issues in the memory footprint we can see this problem were clearly in an actual matrix with 117 Queiroz in the columns and ten point four non-zeroes per roll on average this is the fine level matrix when interpolated using smooth weights the cross level matrix which has only four point K rows and columns will have on average a hundred and ninety three non zeros per row in our choice of piecewise constant weights will reduce number 237 notice that this is only a two grit V cycle as a toy case when we pass those non zeros into denser and denser coarser level matrices using smooth weights it will hurt the performance of course level solves a lot while our choice of piecewise constant weights we'll end up with more than twenty times faster compared to smooth ones in a big V cycle but what do we lose piecewise constant interpolation is supposed to be bad at skating right well let's see how bad it is let's say now the blue thing is our fine level mash being controlled by only two green dots as a crosser level nodes if we move one green dot upward a smooth weighting scheme with linear blending looks okay ish while the piecewise constant ways tear it apart that's the reason why people always say piecewise constant interpolation is bad but we find the cliff caused by piecewise constant weights is not that bad in our multi grid scheme the error created compared to the exact solution look like an impulse function which is extremely high frequency remember that high frequency errors are easy to remove when applied with some smoothers we observe that the piecewise constant weighs might be bad as skinny but they are acceptable in the multi grade framework as a result we choose to stick with the piecewise constant waiting strategy because this one is a key to maintain a sparsity of our course a level matrices without causing too much trouble moreover it is also the key to enable us to update multi-resolution system matrices efficiently when the finest matrix a has changing numbers to bring everything together we follow a gallery in multi grid pipeline with our choice of U matrices there are some more details about the acceleration of constructing the multi-resolution matrices and irregular writing some degenerating cases but I don't think I have time for those so please refer to our paper for more details our method is not assuming a specific shape of multi grid cycle you can use a DV cycle or a wider W cycle without changing anything we are also not favorable towards any specific nonlinear optimization scheme we can run the quasi Newton or a DMM or Newton's method as well for example here we've shown an example of running Newton's method to simulate a closed with zero point for Springs at real time it can handle dynamics matrix change caused by the non-linearity of the mass spring systems and the collisions as well generating vivid wrinkles here we show the examples we had in our paper ranging from thousands to nearly a million elements all of them are running in real time in a single and video 2080 card and the pre computation time is under 30 seconds which is not a terrible number those times are used for sampling the course-level knows computing the you matrices and allocating memory space for the multi-resolution a matrices to visually test the skill ability of a marathoner method we simulate a Hania Modelo with the same material but different resolutions and they look quite similar we plot the memory cost in the red graph and time costing the blue one in a log-log scale the plot where the x-axis is the number of tetrahedra here we also draw a green line which is the line with slope equals to 1 indicating linear behavior we see that the memory cost of our multi grid sovereign scales linearly which is very nice and the performance goes better than linear initially with the help of paralyzation and it will eventually converts to linear for large masses we also validate our choice of an interpolation scheme using the armadillo example is 44 kg degrees of freedom here we pick a 2 great V cycle where the coarse current solves this linear problem exactly we use the error reduction rate row to see how good or bad our choice of U matrix is Rho is the ratio between the error after the coarser level solve and the error of the bullet of course we are not expecting row to be Darrow which is too good to be true we still want Rho to be as small as possible to see the power of multi grid we first test the effects of using skinny space coordinates in coarser levels we can see that our method on the first row produces much better error reduction rate compared to using positional space D laughs well to make it a more fair comparison we can increase the number of course level vertices to 400 to make total degrees of freedom the same with our method and still we can see that the choice of scanning space coordinates does matter a lot to reduce the error and order of magnitude smaller we'd also like to see how bad our master day is compared to smooth weights thanks to the smoother our interpolation scheme is producing three times worse error compared to the smooth one but since it around 20 times faster we still pick the piecewise constant ways in the end we compare our method with other GPU methods based on iterative solvers the blue curve is our method the green one is a championship some are iterative mastered and the red and pink ones at the vivace solver running with different gauss seidel iterations as we can see when terminated at 30 milliseconds our method reduces the relative error much better and in order to reach the same amount of error it will cause the chebyshev more than 300 milliseconds to run and be virtually more than 500 milliseconds we also visualize that this kind of difference here are some illusions are produced by projective dynamics with different solving strategies the top left one is the ground shoes produced by pre factorization in vanilla PD the top right one is using our remote degree solver which resembles a ground truth solution a lot the bottom two are chebyshev and vivace solve where we fine-tune the simulation parameters to their best performance you can still see that the early termination of these masters courses and the octopus look much stretch here than it should be with our method as a backbone of linear solve we can interact with the D form of a dragon with 0.7 million elements and around 40 frames per second well let's summarize our talk today we aim for a fast deformable body simulation and we can choose any nonlinear optimization framework to begin with such as Newton's method or projective dynamics or a DMM we apply a multi-grade solver to solve their linearized systems based on galerkin projections and eventually we show that our construct that uses piecewise constant ways to interpolate the skinning space coordinates is able to elevate the entire problem making the real time deformable simulation scales to another level of course there are limitations that are mastered the biggest limitation of our method is to handle topological changes of a match during the simulation because that will end up with new set of u matrices and the repeating the pre-computation of our method prevent us to keep its real time performance we are also currently assuming homogeneous materials so we sample the multi-resolution knows only uniformly when a heterogeneous material is 1t reduce some smarter pics of the multi grid is needed last but not least we sincerely express our gratitude to our friends and colleagues for many insightful discussions - you shall go to help us with lots of useful CUDA programming tips - ha me one - for providing his GPU simulating framework and to all the reviewers for their valuable feedbacks well that should conclude my talk today thank you very much for listening we also have our source code available online right now feel free to try it on on your need thank you

Channel: Tiantian Liu

Views: 775

Rating: 5 out of 5

Keywords:

Id: sG6aCZoc_2w

Length: 16min 24sec (984 seconds)

Published: Wed Dec 11 2019