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!
