"Papers I Have Loved" by Casey Muratori

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
my name is Casey Muratori, I'm a game developer. As I could sort of tell from the last talk in the quality of service packets thing is not the common person who's at this conference, so just to sort of give you some background on the talk when they asked me to speak here, I was like, OK, that sounds cool, but what do you want me to talk about? And they were like, well, we just want to know like what do you guys do, have you used research, how do you use it, give us some examples of times when you used research and it's inspired you to do something cool, I think was the sort of the way that it was phrased and so I was like, OK, I can do that. So what I've done is I've picked three papers from way way back in history, well, way way back in my history, for game development that are really pretty important, they're used for a lot of things. And which I had sort of a personal relationship with. Like I read the papers and really loved them and then did some work in the gaming industry that was related to them and I'm going to kind of go through those. Now, my assumption is since it's not a gamer-centric conference. I apologize for a game developer you're going to be like I already know this stuff already, so what can I say in this is actually how my slides are looked. This is kind of like you're coming in and I don't want you to be scared away but this is actually what my slides are going to look. You don't have to read the slides hardly at all. They're usually just there for diagrams. So from here on out I'm going to be very, very fast, I'm going to be going on 2X speed on the little YouTube drop-down, because I'm assuming you're not going to go home and implement these papers. NORMA: Thank you very much. I love that! >> If you do, that's even better, come up and talk to me afterwards. >> Which I'm old, so that's actually, you know, that was what, 18, 19, something at the time, so it's actually not that long ago in sort of in my mental history but it probably seems long for some of you who weren't even born then. So in 1996 this is my first first job. And the reason that I kind of wanted to start here is because ironically and for this conference, it actually happened to be a job based entirely on a paper. Now, this is not one of the papers I'm actually going to be talking about that I have loved. Um aim not saying I don't love it it's just not one of the three. If you've ever been to one of the fancy restaurants where they say there's going to be three courses but then you order that and but then this thing comes out one of the courses this is an amuse bouche, it's cream celery with a crouton, or something, I don't know what. This is a paper called evolving virtual creatures by Karl Sims. So what they did in this, you know, in this paper, I guess I shouldn't say they, because I guess it was just he. He actually made a system that sort of like simulates nature, like fer realz. It's a controller sort of graph thing that could make the creature actually move its joints and they made a simulation and they could run these virtual creatures through tests, right. >> They could kind of give them things to do and see what they did. Now the whole point of this thing was to simulate nature what they were doing is they would randomly generate some of this DNA and they would let whatever creature popped out, just stumble around, but they would then grade all of the random creatures on how well they did, so for example, let's say that the creature needed to get from one end of the thing and there was an obstacle in the middle right, and rank them. They'd take the trees for morphologies and their brains and they would do a sexual reproduction thing. And shockingly as I'm saying this, I think was in 1993, 94, you should go look at paper if you're interested in this stuff because it's a fun read. I highly recommend looking at it if this piques your interest at all. You would expect this to fail completely but actually it was pretty good, right? The things that come out of it actually really neat and they can do a bunch of things like following a light source or getting over an obstacle or something like that. So it was actually pretty cool. But what wasn't necessarily pretty cool somebody thought that it would be a good idea to make a game based on that concept. Now, in the abstract that's a good idea but when you think about the context in which this paper was really implemented it was a CM5. It was a supercomputer at that time, 32CPUs which is even high for today. Well, it depends on what kind of gamer you are, but most of them don't and it took three hours to run one of these things so if you think about what you were trying to do in thaterra terms of turning this into a game it's a stupid idea and you only had ten seconds or something, probably. How long is a user going to wait? No one's going to want to play that game, right? So this was doomed to failure, but fortunately for me, that part wasn't my job. My job in this particular context was to create the environments in which the creatures would do whatever their thing is that they were going to do much and the mandate was sort of that these environments would be organically, they would be like let's say we were making viruses or something inside the human body so where these would play out would be inside the human body or something that would felt if you were watching an episode of old cultural references House, let's say, and they would zoom into the bloodstream. It should look kind of like that, all right? So that's what they told me to do and remember, I'm very little. I wasn't actually, this is an age and experience thing, not a height thing, I didn't get this short when I was 18, that would be weird, but point being, basically I didn't know very much about research in any particular way. I had not been to college, I don't really know what that means, but at this point they said, well, you know constructive solid geometry is a thing that a lot of game engines are using now, it's kind of a new thing. There are games like Quake and Unreal and those sorts of things, and they were using constructed solid geometry, but point being I was sort of told I was sort of told go look at that because that's generally how levers are built. Figure that out: I didn't know how to find papers or -- I had no idea and the internet is this kind of like this blossoming flower at this point, right, it's kind of a thing that well, you know, we have a 14-4 baud modem or whatever it was that at the time, it makes the noise when you connect. That's how you got into onto the internet if you weren't at a university or something like that that had a serious connection so that's the kind of thing that we were doing. And at that point, sightseer, I think had come up. So the idea of going on the internet to find papers and thing like that was kind of exciting and interesting. And what happened was just kind of a fortuitous reading through papers oh, that looks interesting, I found a paper that talked about something called alpha-shapes and I don't even know how to search any more. I tried halfheartedly to see if I could dig it up, but I couldn't. Basically they were talking about the concept that when I have two shapes and I want to kind of merge them together, couldn't I do something that made them kind of blobbily go together instead of rigidly going together? If you look at this drawing. The one on the top is the kind of the blobby coming together and you can imagine in your mind the difference between that if you took two circles and put them over each other, you get kind of a cusp where they intersect and that's not very organic. Unless you're talking about a tusk or something like this, usually they kind of blob together and certainly the things we were looking that inside the human body, you would expect these smoothness necessary and I'm like, oh, man, this could be perfect for what I want to do and for those of you who don't remember what anyone Terminator 2 or is that way too far back? OK, a couple of people. So there's this weird cyborg metallic guy ready to conform into things. And occasionally he freezes and he shatters. And things turn into the blobs and they get closer together and they kind of suck into each other like mercury if you've ever seen that happen. So that is what this paper led to me to. Alpha-shapes are guess not that interesting or whatever because most of the literature on doing those actual kinds of things with surfaces was in the implicit surface literature. That's what it's called. Implicit surfaces will give you an idea of what they do now, because if you're not familiar with grames or graphics you've probably never heard of them or don't care about them. But instead of modeling with things concretely which is kind of what we're more used to do with most software packages would experience, if you're in something like Adobe Illustrator or something like that, I'm making solid shapes and I'm saying this is exactly the solid shape that I want and then I'm done, right? But implicit shapes are modeling with more many energy fields that they give off that's the actual thing I'm modeling with and what happens when you move two of these shapes together you get constructive interference. So as their energy fields overlap something happens in there -- point being if I want to define a surface, like an actual thing that I modeled from this kind of a thing, I can simply say, let's find where the energy equals some number, and I can pick out kind of a band as it goes, right? And you can see, you know, where that constructive interference was, everything else kind of follows the shapes exactly, but where the constructive interferes is, you can see that you get that curvature and the reason is because those fields are adding together, they're creating like an additive constructive interference that creates the bending. That in my mind I was like, that's where we want to go to get that field, right. There's something I want to say that's relevant to the rest of this which is that when you have a definition like this, you end up with some interesting things that just sort of magically happen. One of the things that is actually very difficult to do. One of the things that might be a little bit difficult to do if you have a traditional definition of a shape or a surface or something like that is to say what is inside the surface and what is outside of the surface and one of the reasons is because the surface might not be complete. Even if you know that the surface is completely closed, and you want to ask a question like am I inside it, or am I outside it, then you have these problems of like, OK, I have to do start doing intersection testing and there's robustness problems. And all these other sorts of things, right, but with an implicit surface definition it's actually extremely easy to know whether you're inside or out, because the whole definition of surface is based on some kind of a field like this, so at any point you know, if I'm outside, if I'm inside, or if I'm on the surface, because the definition directly gives you that information, so it kind of flips the model around. It turns out that it's exactly inverse, with an implicit function or an implicit surface, I know whether I'm inside or outside at any point in the world. But what is difficult is to define the entire surface. Because all I know. I know exactly what the shell is, but I have to do real work to figure out whether I'm inside of it or outside of T for those of you who like mathy sorts of things. These are not difficult math. The math for implicit surfaces is basically trivial. All they are is field ex functions. They sake some point in space and they produce some real value, like a scaler out the other end and that scaler is kind of the energy that I was referring to, so at any point in space, and it doesn't matter if it's 2D, 3D, 1D, 9D, it doesn't matter, it's some point where you're inputting at the space that you're talking about, and out comes that value, right? Now, oftentimes I should point out the value. We can pick what energy level we use to figure out what the surface is that we actually want, and, well, you know, actually if you care about the math of it at all that's not really how it works, when you pick that energy level, you usually end up kind of making a new function where you subtract that energy level away. Because it's always more convenient to talk about 0 as being the solution, right? So you kind of want to talk about 0 as being where the surface is, so we end up with convention where when I input something into that function, when I get 0 out I am exactly on the surface, greater than 0 inside the surface and less than 0, outside. Did I say that right? Hopefully I did, if not, the slide is right. Don't listen to me. Once again those of you who love math. It's so simple. One of the most common ones is metaballs. Which is a point feeling, right? And the way that those are implemented is just 1 over the distance. That's it. Like if I want to know a point in space how much is it influenced, how much energy does this meta ball contribute it's just one over the distance of the borrel, right? Nobody ever uses that so usually you use something else that just fitted to that function, but it's basically that. Really, really really simple math for the implicit function but for the part that wasn't so simple until this paper, right, is that we assume as essentially have three steps to this thing if. If I want to get out the actual surface, right, then I have a problem. In Step 1, I can trivially just take as many implicit surfaces as I want so I can add them all together. And they don't have to be meta balls, they can be anything, any function you can imagine that goes FXYZ because all I need at the end of the day is a scaler, right? And step 3, if we leave out magic Step 2 is I have the actual surface. I have something that I could feed into a standard open geo. OBJ. I -- something you can output into a PLY file, let's say that. OK, so that's where the first paper I've loved comes in, it's called marching cubes and it's got a really long subtitle. But this is the paper. It's by Lorensen and Kline. But it's a way of filling in that missing Step 2, where all the question marks were, OK? Now, here is how the paper works, OK? I need to figure out some way, something to get some traction on this problem. I have an entire world filled of values that I can evaluate, but I have no idea where the surface actually is, and furthermore, if you think about what happens, assuming that it is just a surface, a 2D surface, right, embedded in a 3D space, takes up almost none of the space. That's kind of how 2D -- volume squared is always much lower than cubed, no matter what the value that you picked unless you're less than 1. So anyway, you kind of have this problem of the chances of you randomly finding the surface is none. So usually you're going to get some other points. So we kind of need to figure out just to get some traction on the problem, how do I even know where a 0 is? Just give me something to work with here, right? And so what I can do is pick two random points anywhere in the field that I want to. And I could evaluate the surface at those two points. That's trivial to do. I said it's easy math. Put in XYZ, out comes the scaler and we're done. So there's only three cases that can happen when I do that the first case is that they both return positive values, which means they're both inside the surface, right the other case is they could be both outside the surface and in both of those cases right, they both return less than 0, in both of those cases I have learned absolutely nothing about what happens in between these two points and the reason I have learned nothing about that is because I don't know if the field kind of came in and just touched some of those middle points there, so I could have been both in and both out, but missed what happened in the middle, right but the third case is the important one. If one of them is less than 0 and the other one isn't, then I finally do know something about what happens in between and more importantly I know exactly the thing that I wanted to know. I know that the surface is in between, right? Because in order to go from a positive value to a negative value along the line between them at some point I had to have crossed 0, at some point. Even if the function is discontinous, the discontinuity hadn't happened between us so it's going to happen. And that's all I need to know. Once I know that any of you who are familiar with numeric computation, this should be easy for you it's basically root finding. What's the result? That will tell me which way to go, right? If the result is the same result as A, then I want to go towards B more. If the result is the same as B, I want to go towards A more. I want to push away from the one that I got the same of. So I'm going to just keep hopping until I get to where the surface is. And get to where the surface is kind of an ambiguous phrase. So really what I mean is go down to the -- where you actually compute actual results from things but assuming you're computing on an actual computer, you only 24 bits really to work with anyway, so 24 steps of bisection will get you to the most accurate answer you could get to anyway. So last step to the algorithm. Now we know that if I have two points and I see if there's you know, one is positive and one is negative in terms of value in the function, I can find where the surface is, right? So now the question is how do I go from that to an actual representation of the whole surface that I could use. And this is where the marching cubes thing comes in it's really elegant and really simple. You. In the you either take a rectangle or a cube and you evaluate the points, all four of them or eight of them depending on which one we're talking about. And what you will get is a series of negatives and positives, right? What you then can do is take any edge that is coming off a positive and going to a negative and do that root-finding step that I just talked about. You now know where the surface crosses the rectangle or the cube. Right? And all that's left to do is connect them. And now you've got either an outline of your surface, or a triangulations of your surface, as long as you just do this to basically the entire area that you care about. And you can see that this is a pretty easy thing to kind of compartmentalize, if you think about the way positives and negatives can actually work on these things, if you have a rectangle there's 4 points, there can only be 2 to the 4th combinations of positives and negatives in this thing so you only have to implement 16 cases and by the way, those 16 cases really aren't 16 cases because they're highly symmetric. If only one point is positive and the other three are negative. Well, it's the same case just rotated, right, to a couple different ways. So you really only have to implement a few cases and figure out which one you're looking at. Same is true for the cube. Worst case is if you typed in 256 things, but most of them are not close to that. And then like I said, you just apply this to your entire plane, area that you want to figure out what the surface looks like there or the volume. And I didn't draw the volume because oh, my God, my drawing skills are not up to that. You will just get a mesh that occupies that volume and is exactly where the surface is, am I going too fast? Because I know I'm going fast, but are we good? We're totally good. Awesome, that's what we need to know. Brief moment of silence, little tiny tiny moment of silence, there was going to be a brain teaser in here, it got it cut for time. OK, 1999, we are going three years forward here. And this I was working on a character animation system. This was not a crazy project. This was actually a good project. This was reasonable. This was not something a sort of conjured up by people who have ludicrous ideas of what's possible. And one of the things that's true about animation in general, if you've ever worked with it, is that rotations are really, really big deal in terms of what you're going to have to deal with. And the reason that I say that is because anything that might have been hard in position space is much much harder in rotation space, now if you've never worked with 3D graphs and that sort of thing you'll be like I don't know what he's talking about and that's true, neither did I until I started working on these things. The problem with rotations is they don't obey the same kind of laws in 3 dimensions as we normally would like things to obey when we want to work with them. So for example, if you think about positions, and you think about the kind of laws they obey, they're really, really nice from a mathematical standpoint. Like you don't have to sit down and like, go, OK, here's all the weird things that are going to happen with positions while you're working with them. No, they're just vectors, they're fine, you can move them around. Everything that you think intuitively will work will just work but rotations are not that way. And the I don't pretend to know remotely even enough abstract math to tell you philosophically why this is true, I can simply tell you practically. If I do two rotations A and B, I will not necessarily get the same rotation if I switch the order. Right right? With movement and positions, that sort of stuff doesn't happen. You can rearrange the order.Ites all the math things you want, but rotation is absolutely not that way. So at the time in 1999, my first incarnation -- sometimes you just want a slide when you're talking, you want it is. You've got some numbers, they've got some subscripts on them, it's great. Rotation indices are inefficient for representation rotation because they're massively over degree of freedommed, if you will. A 3 by 3 matrix can do all sorts of things to your data, it can skew it, it can rotate it, it can do all sorts of stuff except move it. So it's really not a good representation for representation, because you've got way more orientation there than you need. In the game industry we care a lot about efficiency in these sorts of things. So typically when you are using more data than you need, it ends up costing you in terms of efficiency and not just in terms of storage of the if all of those values have to be correct in order for my program to work, that means I had to do work to get them there. So if the thing that I'm trying to represent only needed 3 or 4 numbers and I'm using 9, that means I'm 3 times worse than I should be. End of story. The next paper that I wanted to talk about is quaternions, and I picked it very specifically because it is the kind of paper because it doesn't tell you anything new literally. As far as I know this has nothing in it that wasn't known by people many, many years before anyone even had a personal computer. So it's all old news, but it was the first paper that really made quaternions, which I will tell you in a second as a rotation representation accessible to people who didn't want to spend a ton of time sifting through the math literature. And believe me this is a real practical concern. It doesn't have anything to do with whether or not you're good at math or whether you could be good at math. The bottom line is it takes a lot of time to work through common math stuff. Nits very different if you have a paper that go here. That clicks really quickly and for people who are programming hon a budget, on a timeline, right? That makes a big difference. So I wanted to pick this one because of sort of that interesting aspect of it and I'll tell you why I think that's important kind of at the end of this segment. How we doing on time, by the way? Good? Thumbs up? All right, so quaternions are very odd things. I'm not going to try to explain them in this talk because I would need at least an hour to do that, but what a quaternion is basically an extension of numbers. I'm not ha math person. Who knows. Well, a quaternion, you can think of it a lot like that, it's a very similar concept in that you have the sort of additional bases that stack up after your comfortable real number, right? It's a comfort thing, right? It's like I'm really comfortable with the A and the BI it's like oh, man, I didn't study as hard that part of the math so I'm a little nervous, well quaternions are adding two more of those bad numbers that you didn't study at the end, OK? Quaternions are a doubly complex number or maybe a three times complex number if you want. When you write you just write the actual coefficients obviously the same way if you're talking about a complex number you don't bother writing the i all the time. You end up vectorizing so typicaIly quaternions are just seen as foreign numbers. You kind of just know at some point that's what they are. So at some level they're 4 dimensional vectors. So what do they do, what they do at a high level is they encode orientation and they encode orientation by their direction. Now, this is not how it is normally introduced. Not even in that paper. I can just say that that's sort of how it works. What happens is the length of quaternion in 4 dimensions, so if you imagine taking any quaternion that you had, you'd have the same information as far as what we care about in computer graphics, right? Now, that's not making a statement about quaternions in general because there's probably plenty of times when you do care about that but as far as encoding rotations in the way that we do, that's all that matters. So on the right 2D, in 4D, I can't draw that I can't even really think in 4D. I usually have to use analogies when I'm working with quaternions in my head. So the A and the B are the same rotation, because one of them is just the longer vector than the other one but they're both pointing in the same direction. The C on the other hand is a different orientation, because it's pointing in a different direction, even though it's roughly the same length as. A, right so length is irrelevant, but direction is crucial. So imagine that in 4TD. There's probably people who can see in 4D. I'm not one of them. If you can, that's awesome, now the reason that these were created and the reason they have that weird structure is because a guy named William Hamilton -- where like computer games and graphics went and took some math that was for something else and used it for games or anything like this, this is actually what they were trying to do, they were trying to study mechanics problems and they wanted ways of capturing so this guy named William Hamilton. This is not Alexander Hamilton, the guy that the musical is about. So yeah, like I mentioned before, rotations don't commute, they're weird and what Hamilton was trying to capture when he came up with this structure is that lack of commutation so he wanted to have it so if you wanted A then B, you'd get C. That's how it works in the real world, and they wanted the math to work that way. Right? And he did it, right? That's why he's famous, well, math famous, not -- he doesn't have a musical yet, but maybe someday he will, when math is more important to society. So 3D rotations if you were to say the words A then B. In matrices, because matrices, as well, I'm not enough much a math philosopher to tell you, matrix multiplication also obeys this property. So if you encode rotations as matrices, you will get this property. So you can do it in matrices, like I said, though, not very efficient. Quaternions have the exact same thing. So the multiplication both obey that ... ... But there's a didn't like them in 199 is because of that. I know that's an ironic thing to say. You always want it both ways. The best possible thing you can have in representation is everything that you want, not just one of the things that you want and one of the things that you often do want when you're dealing with these things is nonorder dependence, right so I love the fact that he when I'm trying to capture the order dependence of rotations that I can do it but I don't love the fact that in those parts of the code where I really don't want to care about the order, I have to care, right? And I'll motivate that a little bit more in a second here. So if I wanted to make an order for quaternions where I did A op P and B op A. We didn't know how to do it and the math didn't know, either. Nobody knew. It was just not known. OK, so why do we care. I'll tell you the reason in a second. But typically when we're working with animation, in a lot of other cases is a lot of times we have human input, and I'm on two ends of the scale. So I should say we have a lots of human input on both ends. We have artists who need to make assets and then we have players and they've got a game pad in their hand or a mouse and a keyboard or whatever and they're doing lots of inputs to control the characters on the screen. So two things need to synch up but we don't know. Who knows what they're going to do, right so we fundamentally in the game industry and like the film industry it's efficient to have these things, but in the game industry it's a must. We need ways of ordering content where we don't know exactly what it is. So typically what has to happen is we produce a bunch of possible asset cases and then we need to get to a specific, like, nobody ever authored it, a specific asset case at end and to give that a little more concrete flooring there, imagine I had enough money to make art for the guy with his hand kind of waving at the top there and another one where he's kind of sad and I don't know what the player wants to set for how happy their character is. I want a whole range of happinesses but I only had budget for two happiness ranges. But that's what we want. Right? So in that context, we start to get into cases where we don't want to care about the order in which we're doing things. Because this starts to multiply out. Let's say that I have more sort of axes on which I would like to do. I want percent happy, I also want percent something else hand size, percent coordination, does he not know what he's doing? So I might have some sort of multidirectional grid of samples and I'm trying to get what it looks like in some specific area inside that thing, right? So at that point, I can't start really talking about order. There's just samples and I'm weighting them or trying to grab all of the algorithms I might think about there, they don't have order involved. They're not doing this, then this then that. I'm combining a set of things. And combining doesn't work that way. I get all these fields, I add them together and I get something out, right? So we had something it's called spherical linear interpolation. Really, really simple it's just saying I have one thing and I want to linearly go between them using some percentage, right? So I want to get the things in the middle use willing some percentage, right? Well, spherical linear interpolation is the opposite of that when instead of talking about linear motion through space I'm actually talking about an arc, right that's where the spherical in spherical interpolation is, it's talking about an arc. If you think about what I said before, it's because quaternions encode things by their direction, not their length so when we talk about interpollating between them. What we're trying to do is talk about their directions. So in order to move smoopghtly between two things and not have speed discontinuities there, we need to take into account the fact that we move in an arc and not a line, right? I know it's a little complicated to think about. It's 4 dimensions, what do you want? It's crazy. [laughter] We had this SLERP. Thing, but it starts to get really inefficient if you do that and then what if you accidentally switch the order somewhere, the code has to remember all the orders wrong, you get a different result and all. A sudden your thing would change. There's all kinds of problems with it, right? So could we do something where we just fed everything in there and have that work, right? So fast forward to 2001, the spoiler warning for the 19989, 2000, 2001 years I didn't solve the problem. So the problem is still unknown. And to the extent to which -- yeah, I thought I had a slide here for this. The extent to which we did did not understand how to do this cannot be overstated. I'm not talking about us sitting around going, yeah, gosh, that's a hard problem, all right, let's go to lunch. I'm talking about people wrote dozens of papers on how to solve it that sucked. These papers were awful. They had to write optimization things, crazy things that we would never do at runtime in a game, right? So it was really, really mysterious. So here's the how we solved the problem. So the way we ended up solving the problem is, you know, we don't really understand it that way. We're using the SLERP thing, we're using this math, but did we ever really look at how they actually work in practice? Right? And so what we did is we wrote a program that could visualize how the SLERP was actually working in practice. And the way that it worked was you could put in two rotations and it would draw coordinate frames for them. So again if you're not familiar with graphs this is going to be a little hard to relate to. But if you could imagine XYZ axes that you might draw in math class. You could set two of those wand you could look at what the interpolation was going to do between them. So when the X axis would rotate to the other X axis, it would show the arc between those and on the arc it would mark notches to show where the interpolator was if it was at 0%, 20%, 30%, 40%, right. This was the first step that was going to be taken to try to solve this problem. It mapped I'm just going to say in that program we mapped four things. Matrices, the exponential map which I'm skipping. It was another way of doing interpolation, SLERP and just for the heck of it, LERP, which is linear interpolation. So we don't even care, we throw opt the fact that they're quaternions entirely and we would run them through the same old code that we would run for anything else and to our surprise what we found when we looked at the actual results of this is that LERP and SLERP are almost identical for all of the angle distances that we ever cared about, right? So I've drawn two sets of notches here. The top one is LERP, the bottom one SLERP. In between there, LERP on the sides is going to be a little bit -- it's going to have just a little bit of a speed variance as it gets towards 0 and 100%. But they're really, really close together and this was completely unexpected because we had always been thinking, oh, LERP, you can't use that. No one ever tried it, no one ever even thought about it but it turns out it's actually almost the same for everything we cared about, right? So that four hours which was supposed to be the start of things was supposed to be the end of it. That was the answer. Then it was trivial for us to do all the rest of our algorithms using this information, right? We could use n-way blending now. We can do faster 2-way blending, because there was stuff in SLERP that you don't want to do implementation-wise that makes it slow. You can do sblines, and it was awesome beings it was a panacea, it was so good. And if you worked backwards from that which is always easier, hindsight is always 2020, it's actually obvious why this might be true. But the reason that it's true is that if you think about what happens just in any space, forget 4 dimensions, just think about 2 dimensions, if you have two endpoints. Well, if all I care about is the resulting direction, then it's just the projection of those -- of that line onto the arc and we all know what happens when you project a line onto an arc, you get a little bit of bowing on the edges, it's correct in the middle and the two sides, right? It's exactly what we should have expected but we never thought about it, so it wasn't ever really done, right and by the way as an aside for those of you who might be math people and who care about this a little bit more, I'll point out that that there's a reason why quaternions LERP and matrices don't LERP as well. If you care about that talk to me after and I can give you more information. It's really neat, but it would take another 30 minutes to get there. In this case, dumb was really good. It turned out the simplest solution was the best solution. One of the reasons I want to kind of plug this sort of paper is because if you think about what it took to get to this answer, it did not really take any math. There wasn't really any insight or mathematical or algebraic insight that let to this. What it took was someone sitting down and bothering to write a bunch of code and typically often, many, many times, the people who sit down and write things like visualizers aren't mathematicians, trade programmers do code all day and they are very, very fast and they can do something like that really, really easily but they may not have the algebra knowledge or whatever the math knowledge is necessary to understand quaternions from whole cloth or even know that they exist, right? There's so much mathematics out there, how do you even know it exists, right so one of the reasons papers like this are so valuable is when you give people whose expertise is just making stuff access to the domain and so this is one example of how that paper did that but I bet there's lots of other examples, too, because I know lots of people in our industry and probably lots of our industries, never would have learned about quaternions if there wasn't that paper and possibly since there have been other ones, but who knows whether any of that would have happened for a long time if he hadn't written that paper. How am I doing on time? Thumbs up. Now we go to 2003, and this is the last paper. I've talked about two types of papers I've loved basically. The other one is I didn't come up with anything but here is this cool thing in math and I came up with a good way to explain it and in some sense in my mind coming up with the explanation is almost the invention itself. Because there's sometimes people who do all kinds of math and work with it but they don't understand it not at the deep enough level to really communicate with a it. It's the coming up with how you explain something is real work and that's a great paper, too. And now I'm going to talk about a third type of paper and that is a paper that has a great contribution in terms of new ideas, new insights, mind blowingly awesome. But written by someone who has no idea how to communicate that to anyone ever. It might as well be encrypted with because no one is ever getting at the information in this paper, OK. All right, so this is the paper it's called a fast procedure of computing distance between complex objects in three dimensional space. It's by three guys, they're from robotics and I'm not going to try to explain it the way they explain it, because it's nuts. The paper is full banana cakes. I'm boring that phrase. It's a great phrase. You read through it, it's got tons of notation to it, tons of lemmas, tons of all these sorts of things if you look back at section 4.321. And you're like I don't even remember that being mentioned, I don't even remember what section you're talking about. Theaps the kind of paper it is, all right? But trust me, this is what the paper actually does in terms of what you care about. Let's say I've got two shapes. They're conveniently here square and triangle. It's just a given, I won't try to justify it. Let's say that these two shapes are intersecting so I move A and B and I move them in such a way that they are colliding in some way. They are taking up the same space. This paper is about figuring out whether that happened. Here I want to get the answer, no, they aren't colliding and here yes, they are colliding and maybe other things, too, how far are they colliding, this paper I'm not kidding when I say it's brilliant. It's one of those papers that I looked at it and wow, this is crazy how smart you have to be to make these leaps. The first thing that's really cool is it starts from a really interesting basic algebraic principle which is rarely what you start with when you're dealing with something as concrete as collision of shapes defined by their boundaries, which is a very discrete kind of thing, right? I can't have two things that collide that don't share any points. It doesn't make any sense. They have to share some of their interior, otherwise be, we wouldn't consider them colliding and it turns out we can write this in a mathematical way. We can say what that is. And what that means is if they have. A and they have B and they intersect then I should be able to find at least one point on A and one point on B that are the same point. Because otherwise, if I couldn't find any points that have that be true, then obviously these things don't intersect. And with trivial subtraction, I can say equivalently that somewhere there are two points which when I subtract one from the other I am get 0. There is no separation between these points. I have to be able to find just one pair and if I can find only one pair they intersect. Maybe only at one point, but they intersect somewhere. Now, second crazy leap. Because that's kind of smart to begin with. Maybe it doesn't sound smart to you. So they were thinking about it from these interesting first principles of calculation, like molecules in the world occupying the same space or something, it was kind of cool. Next thing is OK, what good does that do me? What am I going to do iterate through all the points? Not only is it an n squared problem, but all the ns are infinite. There's way too many of them. But they borrowed something called the Minkowski sum which is an algebraic thing which allows you to add shapes together for real mathematically. Okay, and what this is if you imagine I take a rectangle and I add a circle I get a rounded rectangle, right it's like I'm adding these two shapes together and they both are represented. Now, how do you form this? You imagine taking one of the shapes and you put the other shape in that shape, everywhere it can go. If I my circle and my square you can see the origins of them. If I put it inside the square and I move it all around everywhere it can possibly go and I take the resulting shape everywhere I ever filled when I did that and I get the result, right? So it's very rigorously mathematically defined. So on the other side I did like a weird quadrilateral and a triangle. You can do it with everything. You can do it in any dimensions, you want it's just a true thing about filling volumes, OK? Now this is math, not art, right, although math is kind of an art sometimes. I don't want to bias you in a way of thinking about it. But the point being, it's rigorous. Because art could be rigorous if it wanted to be. They are actually a set of points for reals, with an origin and values. What that means is if my shape is offset from its origin, that displacement actually occurs when I do that sweep. Remember I said you put the origin everywhere inside the first shape, right, not the shape itself. The origin goes everywhere and then I get the result. So if theres a net displacement in one of the shapes, that net displacement will occur in the result. That's really important. I'm not just saying that because I think it's cool. It's really important to the result. And what you can kind of see here is I wanted to illustrate that a little further, but if you go back to what I said in the first sort of slide about this, when I put up that algebra, I said I should be able to point 1 Point A, and 1 Point B where if I subtract them I want to get 0. If you think about what happens when I start transforming the problem into this Minkowski sum space, right? I want to be able to find whether there were any points where if I subtracted the two of them I would have gotten 0 and 0 in that equation, right, 0 is the origin in the Minkowski sum sum, right because if I took one shape and I subtracted the other shape, if they had any points in common, the origin would lie in the resulting shape, right? Because at some two points subtracted would come out to 0, right? Little to hard to understand. I'm sorry if that's a little rough. Everything else easy. If you take a look at what happens here, I said A-B, right? I said I wanted to take some point on A and some point on B and subtract them. But the only thing is that I wanted to do is summing the two reactions together, right? But it's trivial to turn a plus B but so on the top, I have an example of square minus circle, on the bottom all I've done is negate the circle and turned it into a sum. So even though Minkowski doesn't technically define a difference, it doesn't matter it's just a sum without a negative, OK? Let's say I have those two shapes now I want to know, does the circle and the square, do they collide, or don't they? I do the subtraction, I see where the origin is. The origin is outside the shape and hey, that's the right result. These two shapes aren't intersecting or the origin isn't side the resulting shape. OK. How bad is that? Anyone really feeling no, I don't get it. I don't get it. it's OK, I'm sure I didn't get it the first time, either, so you're actually a kindred spirit if you didn't. OK, so here as the next insight. The next insight is OK, for concave shapes if I were to perform the Minkowski sum, I would get a concave shape. The reason it will probably be concave is because when you do the sum usually the features of both shapes come through. So if one of the shapes is concave and I add it to the other shape, well, I'm probably going to get a concave shape on the outside. That's certainly not a guarantee and you can't base an algorithm on it. However, if they are convection, then when I add them together, I will always get a convection shape, and why? Because there is no place for the concavity to come from, right? I'm only adding solids together, so all they can do is inflate each other, they can never create sort of a crenulation, because I never had any to start with, and remember, all the definition of all this is all the points plus all the other points, right? OK, so reason I call that an insight and not an observation is because you had to figure out that you even cared about that, but you do care about that, and the reason that you care about that is the next insight in this paper. For every point on the convection shape there is some direction that I can pick where it is the furthest. I can never, ever, ever pick a point where some other point is always going to be further along any direction I might pick, right so take a look on the left, you can see all of the points have some direction I could pick where they're the furthest. There is no other point that supersedes them. But on the right you can see that that is not true. There is a concave shape and that point in the middle, no matter what direction I pick, I can pick any direction I want, there is always some other point that's further along that direction. Right? Always some other point. I challenge you to do T you if can do it, come up after and tell me you've broken mathematics. But this turns out to be incredibly important. Why? Right. This is why I calls these insights, because even recounting them with the knowledge that's true I have to keep explaining to you why these are important. The reason is because let's suppose, five minutes? Is that what that is? OK, we're almost done. That's actually not that bad, I'll speed back up. [laughter] So let's suppose that we have one of these Minkowski sums, right? It's abstract mathematics, right but if you think about what actually has to happen if I wanted to start commuting with them I'm in a lot of trouble, right? Even just the thing that I said was an easy way to visualize subtracting all the and tessellate the geometry and starts to be a real problem, right? So I need some way of doing computations with these Minkowski sums. So I need some shortcut. And here it is. But I can pick random direction, right, and I can find the points that are furthest along. And if I do that in several directions I will eventually form a volume or a solid or an area in 2D, right? And that area is guaranteed to be part of the resulting shape. It's completely contained inside it. There is nothing in there that isn't also inside the Minkowski sum. That's really important. Because now we can work with it. If this was a concave shape, you can imagine if the bottom was just poking up, that wouldn't be true anymore. Not everything inside my triangle would be inside the Minkowski sum. I can find points on the Minkowski sum on their boundary, and I do it, but you're saying, OK, Casey, maybe I sort of see what you're saying there a little bit, but OK, in order to find the points that are furthest away, I'd have to build the Minkowski sum and I didn't want to do that you're contradicting yourself. There's got to be another insight, right? And that insight is that when I build the Minkowski sum, because it is a sum, if I just do that operation on the individual shapes I'm summing first, I can add the results, so what that means is I can just take the two shapes that I was inputting, find the furthest point on those, and add the result together, and that's trivial. We can also easily figure out for any shape, right, for any mesh we actually have we want to input or any shape you want to do, we can easily find the point that's that far on the projection. We've never constructed the Minkowski sum on those shapes, but we've found a point on the surface, without even making it, right? It's So let's go ahead and give credit to the part here that I'm about to say. So I was talking about how this had to be a talk about papers that led us to do something cool, well, the sel cool here was to figure out how to implement this grim efficiently and I'm going to explain it the way that we implement it which is really efficient, but the actual paper itself was so obtuse that they actually, I think, maybe missed what was actually going on in the algorithm. They kind of used a bunch of math to get to the result, but it was a very expensive set of steps that they used and it turns out that if you think about the problem more intuitively, you can do it in a much more efficient way so I want to give credit to Jay Stelly for that. I'll skip what he actually said because we're low on time. Just to recap we have a function and I didn't say it was on the title slide before, but it's called the support direction. The thing that tells you the point. You tell me the point on the Minkowski sum that's the furthest one in that direction, right? We have that, we want to do our actual intersection test. OK, so here's how it goes. What he say what's the point. It's the point down the lower left corner. We know what the origin is. Then we say OK, in the direction of the origin, that's the next support function call, so give me the point that's as far in that direction as it possibly can be, and already, just for those two steps, which hopefully are very easy to understand, we can know whether these two shapes intersect or not. We have our first clue, if the point is not on the other side of the origin when viewed from the perspective of that direction we're going, then the shapes can intersect. Because if that's the furthest point in that direction, how would I ever enclose the origin? The resulting shape could never enclose the origin. There's nothing beyond that line. There's no way to ever enclose that origin. It's on the other side of it. So if I couldn't get past the origin, the Minkowski sum that I'm looking at must never have enclosed it. But let's say I got back the opposite result. I did get a point on the Minkowski sum boundary that's on the other side of it, right? Now all I do is I continue. I say take that edge, go in a perpendicular direction of it and give me the next side of it. Now I have a triangle. If the origin is inside the triangle, remember, this is the triangle that is in the Minkowski sum, it's inside that shape, right, if that contains it, we're done, the shapes intersect, because 0 is in there so you must be able to find two points in the object that could surround it. If let's say the origin was inside the triangle instead it was in the A space or the B space, all I do is pick the edge that's closest to the edge and go back to the edge step with that new edge. All you do is iterate that until you get one of those two conditions, either the failure case where you can't enclose the origin or the case of the triangle. The answer the entire algorithm. It's trivial to implement. It takes no time at all. All you have to do is implement that little bit of math that I've put there and right there you've got something that can do almost anything. It's crazy what this thing can do. Because the Minkowski sums are actually generalized, right, that support function distributes over any number of operators, which means that the two things that I collide when I pass to t I could do sum objects that are surrounded. So I could actually do the Minkowski sum of those first, then do the subtract, and so I could collide shapes that I can't really find the result of, right? Which is even awesomer. So now we're at the end of the talk which hopefully I'm not too far over time. I told them I was going to be over time so I feel like that's OK. Is that true? How bad am I? OK. I said at the beginning of the talk that OK, these were things that led to something cool. If you remember the marching cubes thing, I never said it led to anything cool. Well, it turns out that this is one of those like in the movies where like the bad guy is dead and he's burned and he's lying in a ditch or whatever and the very last frame of the movie his hand comes up and's not dead. It turns out this is 20 years after, right, this is 20 years after I first read the marching cubes paper around we were trying to do a walk system that had some really interesting constraints, we wanted all these robustness constraints and things like that and it turned out that the way I ended up solving the problem is largely built off that original marching cubes stuff that I read 20 years earlier. So yeah, there's my contact info and sorry I went so fast but like I said, there's a lot of stuff in there I wanted to not miss any of it. So thank you very much. [applause] ZEESHAN: Take a couple of questions. >> Do we have time for questions? >> >> Hi, just a question regarding a LERP and SLERP. It seems that you can get like with LERP you can get the exact midpoint and if you get the exact midpoint, you can get the exact SLERP. >> yes, you you can. But remember what we're trying to do is do it as fast as possible, so if you have to keep going those computations it's way too costly. Because if you want to implement SLERP it's an inverse transcendental. But it doesn't actually help in that particular case if that makes sense. For LERP and SLERP -- when you were doing SLERP, you talked about doing a rotational pass and therefore length of the WXYZ vector doesn't matter, but when you're doing LERP, I assume length does matter because you're going to have to take the equal points for distance so do you normalize the vector for length before you do that -- >> Got it so the answer to that question is definitely and I cut out a ton of stuff, right, because it was just kind of give the basics. In actuality there's a lot of things you care about, all of which are fairly easy to manage but which you do need to know. Some of them are, yes, once you switch from SLERP to LERP and I think potentially even in SLERP, I really don't remember, you do have times when you want to keep those together. Actually it doesn't encode only the rotations that we think about in the real world but actually an additional set of rotations, it's actually double-covered is what it's called where you can actually represent a 360-degree rotations and then another 360 degrees that aren't the same and I know this sounds really weird but if you're into their the et cal physics or whatever, go up and look up double-cover rotations. And you also have this other thing called neighborhooding that you have to do. You have to understand it all and when you do the pipeline it's easy to set it up so that it all works properly but you do have to know all the things that you're talking about and a couple that I didn't mention. So I don't want people to get the wrong idea that that's all you need to do. There is actually a lot more to it, but in terms of the actual computation ZEESHAN: Maybe one more question if anyone has one ZEESHAN: O'right, Thank you Casey!
Info
Channel: PapersWeLove
Views: 46,384
Rating: 4.9538355 out of 5
Keywords: pwlconf, papers we love, marching cubes, quaternions, video game programming, handmade hero, molly rocket, casey muratori
Id: SDS5gLSiLg0
Channel Id: undefined
Length: 68min 4sec (4084 seconds)
Published: Mon Sep 26 2016
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.