Discrete Differential Geometry - Helping Machines (and People) Think Clearly about Shape

the following program is brought to you by Caltech alright guys I guess we'll get started good afternoon my name is Elizabeth I'm the chair of the Eberhardt committee and welcome to the first lecture of the Eberhardt lecture series I'm glad that you guys can all come the other art lecture series is a program funded by the Graduate elfis and supported by the Graduate Student Council and it's a forum to encourage interdisciplinary interactions among graduate students and faculty to share ideas about recent recent research research developments and controversies and to recognize the exemplary research abilities and presentation skills of Cal Tech's graduate students each fall 3 lecturers are selected by an interdisciplinary committee composed by graduate students from Cal Tech and they're determined based on their speaking skills their ability to communicate their research material to a broader audience and their impact on the scientific community as you all know Cal Tech's graduate students are incredibly outstanding and we always have a very difficult time making this decision thankfully we've selected three members this year and we're very happy to present Keenan as our first lecturer so without further adieu we'll have a professor Schroeder come up to give Keenan's introduction well it's a great pleasure to be given this honor here to introduce Kenan and to see one of my graduate students actually be recognized in this way so I'll just say a few words because I know he wants every minute he can get he came to us from UIUC in 2007 and it was one of those lucky circumstances because his grades were terrible is his advisor send us a private note it said don't worry about the grades just take it and since we knew him well and liked him we trusted him and sure enough that was a very good decision for everyone involved he's yesterday I asked him to send me his latest CB just to sort of make up a few things to tell you here and I have to say I was quite impressed actually players a graduate student really is ready to be out there and he's already collaborating with researchers in other countries I guess you have now what Germany Austria and Switzerland on your list there and starting his own projects there also already which for graduate student is quite special invited to special meetings a mobile void for example the mathematicians in the audience well we'll start drooling when they hear that quite unusual for graduate student to be that far along Keenan has received a Google fellowship for his or during his stay here at Cal Tech and he could be done this year but he said to me well I'm not that much in a hurry and I quietly said so he's going to be around for a little while longer and today we have the joy to hear about his research and in fact at least one of those collaborations with researchers in Germany that he sort of spun up already by himself because he's already so well sought after but with that I'll just let you get started so thanks really thanks for that very kind introduction so hey how you guys doing thanks for showing up as Peter said I'm Kenan crane from the department of computing and mathematical sciences here at Cal Tech I'll get out of your way here and I'm going to talk to you today about some work I've been doing in a rapidly developing field called discrete differential geometry but put really simply all I want to do is help computers think more clearly about shape okay and when I say shape what I'm usually thinking of is something like this some very explicit very detailed piece of geometry which in this case is described by a big collection of triangles sort of glued together at the edges and you may be sitting in the audience and you work in a wet lab all day long or you spend your time in front of a chalkboard and you might be wondering well why do I care about something like this and one really good reason is that if you don't have tools for reasoning about this kind of very detailed geometry then you have to make some pretty crude assumptions and you've all seen things like this before so assume that the distribution is radially symmetric or to assume that the membrane is an infinite sheets or assume that the mantle is a spherical shell or hey since we're already talking about the earth why not assume that the earth is flat sounds pretty good right so these assumptions are really convenient they make the analysis a whole lot easier when we go to write down this problem but they can often have unintended consequences as depicted here in the lower right in other words they betray the fact that in reality the effect of geometry on a system can be quite subtle so just little Wiggles in the surface can be the difference between taking flight or being stuck on the ground or between a healthy individual and one with a debilitating disease and so if we really want to understand systems like this we have to incorporate detailed geometry into our models okay but then the question becomes well how do we analyze problems like this that had this very detailed geometry if we're not going to replace the brain with a perfectly round sphere then we need a way to talk about all those little folds and wrinkles and actually part of the answer is going to come from a place you might not expect which is the entertainment industry so when you go see a cartoon at the movies you're probably not thinking too much about geometry you know you're just there to have a good time but the fact of the matter is there's a lot of pretty serious technology under the hood to make an image like this and unlike scientists filmmakers don't have the luxury of just replacing their geometry with some crude proxy or crude approximation because whatever they do is going to end up right there on the screen you know so just imagine hey come see our new movie Rango you know now in 3d no way the kids aren't going to buy it okay they really want to see this guy so there are a lot of really nice tools we can take advantage of here and these days there's also a lot of dirt-cheap processing power that we can use to manipulate this really detailed kind of geometry but there are still a lot of fundamental questions that need to be answered if we really want to capture the way shape behaves in nature in other words it's not enough that we just make nice pictures we really want to get the answer right and so if we go over into the mathematical world they're already all sorts of tools that faithfully capture the way shape behaves one of these that's particularly nice is called differential geometry so the idea here is that we're going to understand shape in terms of local change how fast are we moving along a curve or how quickly is a surface bending and so on so differential geometry is something that's been wildly successful in describing all the things we see in nature there are geometric theories of fluids and relativity and everything else that have been written down in this way it's something that we've really come to know and love and trust and so you would think that to get nice algorithms night nice numerical procedures for dealing with geometry it should be pretty simple we should just be able to take these geometric objects and chop them up into little discrete pieces that our computer can understand in other words we should just be able to take our continuous theory turn the crank so apply some standard numerical method and out pops a discrete theory that we can use to analyze our data so that certainly sounds nice and sometimes this does work but what we've seen time and time again is that by adding a little bit of geometric insight to our problem and in B in particular being very careful about which objects we choose to stick into that machine we often end up with something a lot nicer and what do I mean by nicer or better here well in this talk I'm going to take a look at three different problems where by being very careful about what geometry we choose to discretize we end up with algorithms that are faster and simpler and more able to deal with the kind of data that comes from the real world so in particular I'm going to look at how something called a trivial connection helps us work with vector fields I'm going to talk about how something called heat-flow helps us compute the distance between two points and I'm going to talk about how using a curvature representation of surfaces helps us smooth out all the little folds and wrinkles and so these things on the bottom in the bottom row here are sort of fundamental operations that you need when working with this kind of detailed geometry and what I really want to focus on here is what is the computational cost or what is the effort that you need to actually solve these problems and what we'll see is that a problem that starts out looking like a very difficult non convex optimization problem turns into something nice and convex something that's usually viewed as a nonlinear system of equations now becomes linear and something that starts out life as a partial differential equation now becomes a much simpler ordinary differential equation and if you don't understand what all this jargon means it's it's no big deal what I'm really trying to say here is that if you want to manipulate your geometry in this way then you're going to have to end up waiting a lot less time or equivalently you can work with something much more detailed for the same amount of mutation okay but before I really dive in I want to give just one sort of toy example that gives you a flavor for what it means to discretize an object and the kinds of issues that we usually encounter and the example I'm thinking of is something called the Gauss Bonilla theorem so the Gauss Bonet theorem is a beautiful canonical classical example of what's called a local global theorem in differential geometry the idea is that by just making little local measurements so you can imagine we can only investigate our geometry by looking under a microscope we're going to be able to infer something about its global structure or shape so something that we'd only see if we took a step back from the microscope and looked at the shape as a whole okay and so the local quantity we're going to look at is something called the Gaussian curvature which tells us how the surface is bending locally so if we have zero Gaussian curvature that means that there's no bending along at least one direction so a cylinder is sort of flat along its length so it has zero Gaussian curvature a plane would be something else that has zero Gaussian curvature if we have bending in two different directions like with this saddle then we get negative Gaussian curvature and if the bending is the same along all directions then we have positive Gaussian curvature like this dome and the global property we want to figure out is what is the genus of this surface in other words how many holes or handles does it have so here we see a sphere has genus 0 a torus has genus 1 a double torus has genus 2 and so on and so what the Gauss beaune theorem tells us is that if we integrate this curvature over the entire surface in other words we move our microscope microscope all around and we add up this number K at every point then we get another number that's always equal to 2 pi times 2 minus twice the genus ok so what can we do with that well imagine that we've looked all over our surface we've added up these numbers and we find out that the total curvature is zero well then we know ok two PI's that's not zero and so we must have two G equals two or in other words the genus is one we know just by looking under our microscope that this surface must be something like a doughnut or a coffee cup or maybe the city of st. Louis okay so that's actually pretty cool but now we have to ask what can we do the same thing for a discrete surface like this triangle mesh that we looked at earlier and when you first look at this problem it seems like well you can't really get much information because it sort of looks like the whole surface is flat it seems like there's zero curvature everywhere so you won't be able to figure anything out for instance these triangles there certainly flat and if we go to one of these edges well there's one direction along which it's not bending the direction of the edge but then you start thinking well maybe there's some curvature at these vertices at the place where all these triangles meet and so then you ask can we define negative and positive Gaussian curvature for these discrete surfaces and what is this Gauss bonet Theorem mean so this is exactly the kind of question that you run into when trying to translate an idea from this smooth differential geometry into this discrete world and the answer isn't always so obvious in this case there turns out to be a really nice solution which has been known basically since the time of decart which is to define the gaussian curvature at vertices as just 2 pi minus the sum of these interior angles theta and so you can play with this definition in at least check that it's sort of sane so if I have a completely flat mesh then I get 2 pi minus 2 pi or a flat mesh has zero curvature that sounds pretty reasonable but the really cool thing that happens is if I then go and I add up this discrete Gaussian curvature at every single vertex then again I get exactly 2 pi times 2 minus twice the genus and when I say exactly I really mean exactly no matter how much noise is in your data or how coarsely this is discretized how few triangles you have you're always going to get the right answer so this is something that's really useful at a practical level from taking measurements from the real world and I have these these measurement errors and the point of this whole story is really to say that this is not a conclusion we would have gotten to by just turning the crank and applying some standard numerical method if you went out and grabbed a book on finite element analysis or use standard finite differences you would never come to this conclusion of this nice exact formula it only comes from really thinking about the discrete geometry and what it represents ok so now I'm going to talk about some more recent work that I've done here at Caltech and the first thing I'm going to look at is working with tangent vector fields on surfaces so what's a tangent vector field you imagine I have a surface like this sphere and at every point I have a little arrow that's lying flat along the surface and so together this big collection of arrows you can think of it's describing some sort of flow and so maybe one nice mental image here is that this is the direction of the wind swirling around on the surface of the earth and one really important thing to notice about this flow is that there are these spots where the wind stands completely still and that's what's called a singularity in this vector field as it turns out understanding singularities is absolutely critical when working with vector fields on surfaces because of something called and excuse the name the hairy ball theorem so the idea so what you're looking at here is literally a billiard ball and I glued lots of pink hairs all over the surface and what the hairy ball theorem says is that no matter how hard I try I can never comb all these hairs so that they lie flat along the surface I'm always going to end up with at least one spot where I have sort of a cowlick or a swirl and so then you can start thinking about well just how well can I do you know one idea is I could comb the hair from the North Pole to the South Pole and I end up with these two singularities or if I'm a little more clever I can figure out that I can comb it this way something that looks sort of like a magnetic dipole and just end up with one singularity but that's it I can't do any better I can never remove that singularity and if you think about what this means in terms of the wind on the surface of the earth it's sort of saying at any point in time there's always going to be one spot where the wind stands perfectly still so that's kind of a neat neat fact ok and since singularities are sort of a fact of life when dealing with tangent vector fields it's going to make sense to be able to solve problems like this one somebody hands you a detailed piece of geometry like this bunny which we'll see over and over again in this talk and a set of singularities and they say I want to find a vector field that's as smooth as possible everywhere except at these singular points so you really want to be able to guarantee them that no matter where else you look on the surface no extra singularities pop up and obviously there are a lot of interesting things you can do with this so one thing you might do is an artist might want to design the direction of fur on an animal or an engineer might want to use a vector field like this to split up a surface into nice quadrilateral pieces that they can use for simulation and so this is clearly a problem a lot of people are interested in solving and if you go back through the literature and see how people have formulated this problem you might think it's a very very difficult problem you might actually think that it's something called a non convex optimization problem what does this mean it just means you have a function with lots of little local minima and it's very hard to find the solution that the optimal solution but what we're going to see today is that by adding a little geometric insight to this problem we can really find the global solution by doing only a little bit of computation okay so let's take a closer look at this idea of a singularity so one way we can sort of classify singularities is to talk about how many times does a vector spin around as we walk around the singularity so for this guy you can see it spins around one whole time so we say it has index 1 and here are just a few other examples of different singularities and their indices okay and so when we go over to the discreet picture you might think well that sounds like a reasonable definition for singularity here to here I've got on each triangle I glued a little arrow and again I can check how many times is that arrow spin around as I walk around this black dot so here it's pretty clear the answer is 1 right but if I now hand you a vector field that looks like this it becomes a lot harder to figure out exactly what this the index should be here these arrows really jump around sort of randomly and it's not clear what the index should be or really whether this thing should be called the singularity in the first place ok and so what we discover is that in the discrete setting weirdly enough vectors are not the greatest represent age for vector fields kind of a strange fact what we're going to do instead is represent vector fields using something called a trivial connection and when I say trivial here I don't mean that it's really easy trivial is going to end up meaning something like zero okay so in general connections are an idea that was sort of fleshed out by a guy named carton and the idea is it's going to tell us how some quantity changes as we move along a space and this is a very general notion that shows up all over geometry and physics and so forth for instance in mechanic's we might be able to use a connection to describe the way changes in the shape of a fish so fish is flapping its fins around result in motion through the water but today I'm going to stick to a much more pedestrian example of just how does the direction of a vector field change as we walk around on a surface okay now what we said just a minute ago is that we want a really smooth vector field on our surface and in the plane this is pretty easy to think about there's sort of one smoothest vector field on the suit on on the plane which is just a constant vector field vectors pointing the same direction at every point and so if we want to construct a constant vector field on a mesh in the plane it's no big deal we start out with some initial vector we transport it over to one of its neighbors we copy that guy to one of its neighbors and so forth and this process is called parallel transport we're sliding this vector around while keeping it parallel to the initial vector and so you might think well can we apply this same idea to a curved surface can we just parallel transport some vector around to get a nice smooth vector field well one thing we have going for us is that if I have any two pair any two triangles next to each other I can unfold them out flat in the plane right and so then it becomes easy to apply this same sliding process I start out with my pair of triangles I unfold them I slide the vector across keeping it parallel like I did before and then I just fold these vectors back into their initial configuration all right sounds pretty good but let's see what happens if we try to do this around a vertex like this guy so we start out with this vector we imagine we unfold we slide we refold and then we continue to do this all the way around denoted a to do and wait a minute this vector we got at the end is not the same as the one that we started out with there's some difference in angle okay and this is a problem if we're trying to consistently define a vector field because now we have two different notions of which direction this vector field points in this triangle so this difference of angle here is has a special name it's called the hollow Namie of our connection and in this case actually turns out to be exactly the same as this discrete Gaussian curvature that we looked at earlier when we were talking about Gauss bonet okay so what we've just discovered is that this really naive procedure just sliding vectors from one triangle to another doesn't work we need we need to do something else and and the idea here is that instead of just sliding we're going to rotate a little our vectors a little each time to account for this change in angle so in other words we're going to store an angle let's call it Omega on each edge that says when we go from the triangle on the left to the triangle on the right we're not just going to translate but we're also going to apply a little rotation okay so our whole procedure now looks like this we unfold we translate rotate and refold okay and the goal here is to come up with a set of angles such that no matter how this vector Wiggles around is we're walking around this vertex it eventually gets back to the one that we started with that doesn't sound too hard you know you just come up with some set of angles that add up to the right number except there's one sort of niggling detail here that is going to cause us problems and that's something that I mentioned just a few seconds ago which is that the hollow Namie around this loop determines the curvature of this connection and so asking for 0 hollow Namie everywhere asking that we always get back to the beginning is the same as asking for the curvature of our surface to be zero everywhere and a few of you might already understand what the problem here is it's this Gauss Monet theater and we looked at earlier that says the total curvature of the surface well it's not always zero it might be some nonzero number 2 pi times 2 minus 2 G okay and so we have sort of a contradiction here on the one hand we want to make sure that our vectors always get back to where they started from and on the other hand we have to have curvature somewhere so we're going to play a little trick instead of asking that the vector doesn't change an angle when we go around the loop we ask that it can change an angle by some multiple of two pi so now for instance the vector could rotate around one whole time as we go around but it still ends up back where it started in other words the Hollin ami is now some multiple of two pi instead of zero okay and so what we're really doing here is we're sort of concentrating all this curvature at vertices again in increments of two pi and that's what we call a singularity in the discrete setting the really important thing to realize here is that we're no longer representing the vector field by these little black arrows okay we're really representing it by this change in angle omega as we go from one face to another and the reason this is important is that we can store arbitrary large angles on each of these edges so we can encode a huge amount of spinning around as we walk around one of these singularities so if we go back to this picture on the left again we just see the vectors and as the index gets bigger and bigger it becomes really hard to tell what's going on at the singularity on the other hand if we try to reconstruct this flow from the connection like on the right we get some nice smooth curves and it's really easy to tell what's going on okay so what does this mean computationally well it's just what we said we want a sum of angles as we walk around the vertex that add up to some integer multiple of two pi so this is a really nice simple what's called the linear condition for our connection to define a vector field and the other thing we said is we want this thing to be as smooth as possible in other words we want as little turn as possible as we go from one face to the next and so we're going to say we want to minimize the norm of all these angles just the sum of the squares of all these angles and if you know a little bit about optimization you might already recognize that this is something called a convex optimization problem this is something that's very easy to find the globally optimal solution and actually for this particular problem we can find the solution by solving something called a sparse linear system so sparse linear systems are going to show up a few times in this presentation the thing that's really nice about them is over the last 100 years there's been a lot of great algorithms and software developed to solve this kind of system for millions and millions of variables so if I have a mesh with lots and lots of detail lots and lots of triangles this is something that we can solve very very efficiently okay and here what you can see is that the computational effort that we need to to spend here to make one of these vector fields is directly proportional to the number of triangles this is sort of the best thing you could possibly hope for so something really good happens here okay the other really nice thing about this formulation is that it deals really well with the kind of measurement errors that you see in real data so if we start out with this nice surface on the left and we just artificially add some uniform noise or some crazy outliers you can see that the solution doesn't change very much this flow on the surface stays looking pretty much the same even though the data has been perturbed in this kind of nasty way and that's something that's really valuable for practical applications okay so now I'm going to move on and talk about a different topic which is computing the distance between two points all right so the problem is I've got these two points and I want to find well what's the distance between them and some of you are sitting there in the audience thinking man they got this guy due to the ever heard I know how to do this you just draw a straight line between these two points and then the distance is something like the square root of x squared plus y squared what's the big deal right but now suppose I tell you these points are actually two cities on the glue so now unless you have a really nice vehicle that can tunnel through the earth that's probably not the distance you wanted you were probably thinking about something more like this but again you say well no big deal I know that the distance is you know some distance along an arc of a great circle passing through these two points okay that's a little bit better but remember now that the earth is spinning really fast and so actually it's a little bit squashed so really what you wanted is maybe more like the distance along this ellipse but then there's more stuff to remember about the earth for instance one thing you guys may have experienced is it has these little bumps on it called mountains and so this is a really great example of where if you make really crude approximations of your geometry you end up doing more work than you really wanted to right okay so in general the problem is we have some detailed piece of geometry like this Bunny and we have a distinguished point like this blue mole on his cheek and now we want to know what's the what's the shortest distance to every other point on the surface and here these white lines represent lines of equal distance so imagine one centimeter two centimeters three centimeters and so on and again I want to emphasize that I'm not looking for sort of the straight line distance through space what I want to know is what's the distance of the shortest path from one point to the other okay and obviously again this is a problem a lot of people have thought about solving and have come up with different numerical methods for doing so and so this is sort of the typical story you can imagine I have this little orange particle down on the left and I'm going to have them just take a straight walk along the surface at unit speed so imagine one meter per second and so to compute the distance everywhere I can shoot a bunch of these particles out from the middle and keep track of where they are after one second after two seconds after three seconds of course this isn't really a practical computational procedure because you'd have to shoot out an enormous number of particles to eventually cover the whole surface and so what people do instead is they write down an equation for the wavefront propagating out from this source and then do the same thing they keep track of where's this wavefront after one second two seconds and three seconds and so on and this wavefront equation has a special name it's called the eye Conal equation what does this guy say basically if V is the distance to the source it says that the gradient of this distance function has unit length or put a lot more simply the distance to the source changes at 1 meter per meter okay sounds pretty basic and you might wonder well you know what else do we really have to say here that's that's the whole story but actually it turns out that the simplest way of writing down a problem doesn't always lead to the most efficient way of computing the solution okay so let's go back to this story about a particle and give him sort of a different motion so now instead of walking along straight lines he's going to take this random walk you'd imagine he's just gotten out of the bar and now he's trying to make his way home and and now you're thinking well what does this have to do with shortest paths you know this is sort of the longest path home not the shortest one but let's just stick with this story for a while and see where it goes so again we're going to shoot a bunch of these particles out from the source and now you see something interesting you see something that you may have seen actually under a microscope so this is something called Brownian motion which describes the way for instance little pollen grains jiggle around in a liquid and something that was really worked out by Albert Einstein is that if you keep on adding more and more and more particles to this process it stops looking like jiggling pollen grains and starts looking like a nice smooth diffusion process and really now if I take a slice through this pile of particles and I plot the density I end up with this nice Gaussian curve which over time describes something called the heat kernel okay and another way to think about this heat kernel is I take a scorching hot needle and I touch it to a point on a surface and I see the way that heat diffuses out over time okay and so the heat kernel solves something not surprisingly called the heat equation which as we've just seen says nothing more than well big bumps get smoothed out over time all right so random walks give us heat flow but now you might be wondering well why are we talking about heat flow what's the relationship between heat and computing distance which is what we wanted to do in the first place and the answer to that question was really worked out by a mathematician named Vera Don and so what Vera Don said is that there's actually a very simple relationship between a heat Colonel for a very small time so we we tap our needle on the surface and let the heat flow just a little bit and the geodesic distance on a surface and it takes or a more general piece of geometry and it takes a little bit of work to really state that all formally but there's some nice intuition we can apply here to understand what's going on so if we go back to this picture of random Walker's traveling out from the source then my claim is or what or Vera Don's claim is that if I find one of these particles really far away from the source after a short amount of time then it must have travelled along a really straight path okay and why is that true because if I tell you that you can only walk it one meter per second and then I give you a second to walk okay now I find you way over here a meter away from the source what did you do the only thing you could have done is walked along a perfectly straight line right and the other thing that's going on here is that it's pretty unlikely that one of these random walkers one of these drunk guys stumbling around is going to walk along a really straight path so as we get further and further away from the source along a geodesic we're going to see fewer and fewer particles we're going to see less and less heat another way of saying this is that the gradient of the heat kernel points along these geodesics along these straight lines and that's the key geometric insight we're going to use to formulate an algorithm for computing distance so what we've developed is something called the heat method and the idea is you compute this heat kernel for a small time T you then and you do this by solving the heat equation you then compute its gradient so you just look at the direction of steepest ascent and you notice well these arrows are pointing you know they're pointing along they're pointing along the gradient of the distance function but they're pointing in the wrong direction and they have the wrong length remember the I Connell equation says that the gradient of the distance function should have unit length so what do we do we just turn these arrows around and we divide by length and that gives us this vector field X and now to recover the distance function itself we solve something which I haven't really talked about called a Poisson equation that just says give me the function whose gradient is the same as this vector field X okay so let's compare these two stories on the one hand we have particles walking along straight paths and we end up with the AI Conal equation on the other hand we have particles taking random walks and we end up solving a heat equation and a Poisson equation and the only important thing about these two guys on the right is that they are linear equations there are these sparse linear systems that I talked about when we were looking at vector fields things that are really easy to solve for really detailed geometry and if we write out this icono equation a little more explicitly it's pretty easy to see that it is a nonlinear equation something where we don't necessarily have lots of tools already available to solve we have to maybe write our own implementation that might not you know be as fast might have other issues one thing for instance that's really nice about these linear systems is we can do something called pre factorization so we can do a lot of the work up front if we want to solve many similar problems we can do a lot of the work up front and reuse this work very quickly to get solutions for instance computing the distance to lots of different points on this Bunny so for instance if we compare the difference between these two approaches for computing the distance between every pair of points on the bunny it's going to make a really big difference if we solve for distance using the psycho Niall equation something called the fast marching method it's going to take an hour whereas if we use this heat method it's just going to take a matter of minutes and this is going to make a really big difference if we're trying to gain some intuition about our problem if we're getting feedback every hour versus just after a few minutes it's going to make a big difference in terms of what we can understand about the system that we're investigating okay of course we should check that all these efficiency doesn't come at the cost of accuracy or correctness remember I said earlier it's not enough just that we want to make a nice picture we really want to get the answer right and so here what you see are three different solutions one is the reference solution sort of the correct answer and two of the other ones are the numerical approximations computed using these two methods so there's the front and there's the back and can anybody tell me which one is which it's probably pretty hard to do right so actually turns out that the one on the right is the correct solution and these two on the left are just numerical approximations but both very good approximations so we have less than one percent error in each case another really nice thing about working with this heat equation is it's something that people have studied for a very long time and figured out how to solve on all sorts of funky geometric domains so earlier we looked at nice triangle meshes but here we have a hippo made of some funkier polygons so octagons and quadrilaterals and so forth and the same principle applies maybe more interesting is a data set that looks like this just a big collection of scattered points and this starts to look more like the kind of data that you would get from the real world so you have holes you have noise you have outliers and nonetheless we can still apply this heat method directly to this data and get a nice distance function here's just another example demonstrating how robust this heat flow process is now we have a triangle mesh and again it has holes it has these long slender triangles it has lots of noise and so forth and so it's really nice to be able to just work directly with data like this rather than having to massage it into some really nice form before you can actually understand what's going on okay so the third and final problem I'm going to look at today is something called curvature flow and the idea here is we're going to take a detailed piece of geometry like you guessed it this Bunny and we're going to find smoother and smoother and smoother approximations over time and you're probably thinking this is pretty abstract this is pretty weird actually why are you turning a bunny into a sphere right and there are a lot of different reasons you might want to do this kind of curvature float the most typical one is something like this you have again data from the real world that has lots of measurement errors lots of noise and what you'd like to do is smooth out this noise to recover something that looks more like the original piece of geometry the original data so this is sort of analogous to a doctor who's got an x-ray and they want to remove noise so they can get a better idea of you know where did the bone break or where is the tumor growing or whatever it is that doctors do so I so the other thing that you might want to do with curvature flow it's actually something that's very interesting to mathematicians for instance there's a problem called the wilmore problem which asks how smooth can you possibly make a given surface so on the left here we have this nice round doughnut which is conjectured to be the smoothest possible surface of genus 1 okay and again this starts to sound really abstract why do I care about the smoothest possible surface you can make well in this case there's a really nice connection to biology so here are some pictures from a paper in nature and along the top row we have some kind of biological membrane I think it's a bilipid membrane and on the bottom we have a numerical simulation where we're trying to find a surface that's as smooth as possible subject to certain constraints such as the total enclosed volume stays the same and as you can see quite clearly these pictures really match pretty well ok so again having numerical tools for investigating this kind of question can be really valuable especially in cases where it might be difficult to construct certain conditions in the lab all right but what is a curvature flow well the idea is we're going to define some function or what we call an energy which I'll write E and what it does is you stick in a surface like this Bunny and it spits out a number and the bigger the number this is if I have a really big number it means the surface has lots of little bumps and wrinkles on it if this number is small then it means it's nice and smooth and so if you imagine that every point on the screen here represents a different shape then we can sort of plot what this energy looks like it's sort of a potential energy that says you know how curved is our surface so we start out with something that has really big potential energy then they get something smoother we're just going to follow the gradient of the potential in other words we're going to ski downhill until we find some smoother surface so we get this sequence of progressively smoother and smoother bunnies in this case all right so that sounds pretty nice but again the issue is that if I just turn the crank and apply some standard numerical method there are a lot of computational problems I can run into for one thing when you're trying to solve a problem like this the quality of the mesh is really important so ideally what you want is lots of triangles that look like these guys very close to equilateral triangles unfortunately if you're really naive about your discretization and start running one of these flows these triangles that start out really nice can easily collapse into really long skinny slender slivers and for a variety of numerical reasons this is a real problem because the algorithm can't make any more progress you're taking lots and lots and lots of tiny steps hundreds and hundreds of tiny little steps and the surface isn't changing at all okay the other thing that can happen is if you try to be too aggressive you try to ski down this potential too fast then you get something like this you get this numerical blow-up where the vertices just go to random locations and you do you don't get anything like smoothing okay so this is actually a pretty delicate problem when it comes to solving it on a computer and again we're going to tackle these these issues by applying some geometric insight in this case what we're going to do is we're going to talk about shape in terms of changes in curvature so I have this nice round sphere and I'm going to paint on a function like this so here I think purple means negative green means positive and that's going to give me a surface that looks like this green spots bulge out and purple spots bulge in and the really critical thing to understand here is what are the conditions on this function which changes in curvature can actually be achieved by a real surface so for instance with the sphere because of something like Gauss beaune we know that we couldn't possibly remove all the curvature we can never get a completely flat sphere and so this is what we did we with a with a mathematician named Ulrich Pinkle we worked out exactly what are these conditions on curvature that were allowed or on the change in curvature that we're allowed to make okay and this is the geometric insight that's going to lead to a really nice algorithm for curvature flow um to keep things simple instead of talking about surfaces I'm just going to talk about curves in particular discrete curves like this one and just like in the case of surfaces remember we talked about Gaussian curvature in terms of these angles around each vertex well here curvature is also going to be an angle it's going to be this exterior angle which I'll call Kappa and how do you measure the smoothness of a curve well in the continuous setting I might just integrate the curvature squared if the curvature is really big it's not very smooth in the discrete case you do something very similar you just add up the curvatures squared okay and so the standard way of trying to smooth out a curve like this is to just take these little vertices and try to figure out the way to jiggle them around such that these angles get smaller but it's a pretty tricky thing to do I mean what what direction should I move these vertices such that these angles get smaller as quickly as possible and one thing that's particularly tricky is depending on how I jiggle one vertex it's going to affect the best way of jiggling the vertex next to it all right so we're going to do something a little simpler here which is to work directly with the curvatures themselves if I want to make the curvature smaller well why don't I just cut them all in half and now I can reconstruct a new curve a smoother curve from these angles so I start out with some initial edge my next edge I just rotate it by this angle Kappa do that same thing with the next edge and so forth and so now I get a curve that's a little smoother than the one I started with one particularly nice thing about this procedure is that it's really easy to preserve the length of edges in the curve because again I get to choose which edges I use to construct this curve so if I know the lengths of the edges in the initial curve I can get the same length in the next curve no problem okay well that sounds really nice sounds really simple and you might wonder why doesn't why doesn't everybody do this it seems a lot better than jiggling these vertices around well as usual there's a problem that we run into and we see this problem when we try to work with something like a closed loop like this Bunny so this time around if we just do something completely arbitrary to the angles cut them in half or whatever there's no reason to expect that the curve we reconstruct is going to close back up it's probably going to have a little gap in it where the first point doesn't meet the end the last point and so what we really need to understand is what are the valid changes in the curvature what are we allowed to do to the curvature as we make the curves smoother because we really want to get something that looks like this so the question we're really asking here is is what are the integra bility conditions on the curvature so this idea of integra bility shows up again all over differential geometry basically it's a classical question where you're asking what kind of data is sufficient to describe a piece of geometry in the case of a loop it turns out there are just two conditions one is that well we can think of a closed loop as we take some piece of a line and we bend it into the shape via a map gamma that puts the starting point gamma at zero at the same place as the end point gamma at L okay so that's one of our conditions and the other one is another one of these local global theorems something very much like the Galvan aether and we looked at earlier so this time around we're saying that if we integrate the curvature over the whole curve so we walk along the curve add up this number Kappa then we get two pi times K where K is an integer called the winding number so it just tells us how many times does this curve loop around so this is something called the Whitney Grouch 9 theorem right so these these are conditions on the curvature Kappa but what we really wanted to know is what are valid changes in the curvature and we can very easily you know just by some algebraic manipulations find the equivalent conditions let's say what how can we change the curvature and keep this loop closed so for Whitney Grouch 9 for instance we say well we wanted it to be equal to some 2pi times some integer we can maintain that condition as long as the total change in curvature is 0 okay but the details of all these conditions are really not important the really important part is again they're linear really easy to compute so geometrically what's going on is if this black arrow represents one of my constraint directions and this orange arrow represents the direction in which curvature is changing then all I have to do is remove the component of this orange arrow in the direction of the black arrow all right but the the really interesting thing that happens is if we go back and we look at this energy that we're using to measure the smoothness of our curve and what we said is to make the curve smoother we're going to go downhill we're going to follow the gradient of the energy now if I write down this whole thing in terms of the positions of the curve the positions of these vertices along my curve this whole system gets pretty hard to evaluate and the real tough thing is that the curvature is not a straightforward function of the position it involves derivatives of the position or in the discrete case differences of adjacent vertices and that means that it's it becomes something called a partial differential equation and that's what leads to all these numerical problems we saw before the blowing up the the stopping of the algorithm and so forth but now that we're working directly with these curvature variables the gradient of this function is really easy how do you take the gradient of x squared well it's 2x right and so this curvature flow just becomes now a really nice simple ordinary differential equation meaning something that just works independently at every different point of our surface so it becomes very easy or a curve in this case so becomes very easy to solve numerically so if you didn't understand all that the point is again we get something really nice alright and what do we get well here's one example we have a curve which is this bunny on the top and over time it gets smoother and smoother and smoother until it's a perfectly round circle and on the bottom here I've sort of zoomed in to this region around the ears and I visualize the curve as a chain to emphasize the fact that the edges are not getting stretched out as the curve flows remember that I said the edge lengths are going to be preserved by this flow now the really beautiful thing that happens is that this entire story that we've been talking about about flows on curves carries over directly to the case of surfaces okay so again we have linear integral and the flow itself is just a nice simple OD E and what's going on in this picture is we have this Frog that starts out with all sorts of bumps and details on it and really in 1 2 3 steps it turns into a nice perfectly round sphere so this is a lot better than what we saw before with this Bunny where we're taking hundreds and hundreds and hundreds of steps and not making any progress at all I'm the other nice feature about this setup is well in the curve case we said we're preserving the lengths lengths don't get stretched out in the case of surfaces what's going to happen these angles will be preserved so in other words we're working with something called a conformal map between each surface and the next one and what this means practically is that if we zoom in on this frog and look at the individual triangles that make up his his surface then these triangles stay nice and equilateral throughout the flow which is something that we asked for all right um finally one issue that I didn't really have time to go into detail on is well we're talking about this whole thing in terms of curvature but eventually I need a way to take this curvature and recover the position of the surface if I want to draw that frog that we just saw I need to know where all those vertices sit in space and one really nice connection that we found while working on this problem is that the routine or the procedure for recovering positions from curvatures is actually the same as solving a very standard equation in physic something called the time-dependent time independent Dirac equation so this is just a relativistic version of the more familiar Schrodinger equation that you find in quantum mechanics and so this is kind of neat we've now developed not only an algorithm for doing this curvature flows but also one for solving for wave functions so if I have for instance a spherical shell I can talk I can think about an electron that's constrained to sit on this shell and we have a numerical method that will tell us what's the probability that this electron shows up at different places regions of the sphere but for the sphere you might tell me that's not very interesting I can just sit down and I can grind out oh yeah the solutions are these closed-form expressions that a lot that look a lot like these familiar spherical harmonics so maybe that's not interesting but remember what I was talking about at the very beginning the point of developing all these tools is so that we can work with more interesting detailed geometries like for instance what shape am i going to use the bunny right so this is what one of these electron wave functions look like if I constrain the electron to walk around only on the surface of a bunny and what you're seeing here is basically the ears have become really enormous right and the body is now really tiny and so what this is saying is that the electron likes to hang out in the ears of the bunny all right and I have no clue why you would want to compute electron wave functions on a bunny it seems like a pretty ridiculous thing to do but if you're sitting in the audience and you happen to work on electron structure calculations and you're interested in working with some more interesting geometry than just a sphere or a plane or whatever something that's easy to write down by hand then I'd be really interested in talking to you okay so that's pretty much all I have to say what we did today is we looked at a lot of different concepts from differential geometry and you guys really sat through a lot of this stuff and we saw that if we pull something off this menu and try to use it to come up with a numerical algorithm we often get some really nice problems sparse linear systems convex problems ordinary differential equations and so on I'd like to thank all my co-authors who did this work with me and of course the funding agencies that made the work possible and finally I'd like to GSC and the grad office that made the Everhart series go so thanks very much for your attention I'm glad to take any questions at this time you

Channel: Keenan Crane

Views: 43,569

Keywords: science, mathematics, math, computer science, geometry, differential geometry, topology, vector field, distance, geodesic, curvature, curvature flow, Willmore flow, numerics, algorithms, surfaces, curves, technology

Id: Mcal5Cy7r4E

Length: 54min 41sec (3281 seconds)

Published: Sun Jun 03 2012