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!