Math for Game Programmers: Interaction With 3D Geometry

Welcome to this last section of the day entitled interacting with your 3D geometry. Um, you probably guessed I was a professional bodybuilder, but you're wrong. I'm actually a graphic software engineer with Intel. Okay. All right. So, games, graphics, there's all sorts of fun stuff. You got particle systems, lens flares, cameras, lights, but any sort of meaningful interaction between the player and his environment happens with those geometric objects, whether it's rigid bodies, skin characters, or the some of those soft body things that are becoming more and more important. And these all things they all have meshes. Okay. So, we're going to cover a lot of wide variety of things today. I'm going to first cover a lot of basics, review for some people, but I know it's fundamentals we want everybody to know. Following that, I'm going to dive deep into the convex meshes. Then we'll take a look at solid meshes and spatial properties thereof that affect motion. And then we're going to finish off with some springy things. And hopefully lots of practical examples that'll be fun for you guys. And yeah, you're welcome to take pictures, of

course, but these slides will be available online later on. Okay. This is math tutorial today. So, you were warned there'd be some math in this course. But don't worry, a lot of it is very very straightforward. In fact, just knowing your basic vector arithmetic, dot product, and cross product, that's going to give you guys 99% of what you need in this industry to succeed. Uh, for example, you know, your standard lighting equations in your shaders on your GPU. I mean, it's n.l, you know, to get your diffuse lighting. Just dot product. You're writing some game script code for, let's say, some robot, right? And you want to know, okay, if the player walks in front of you, you know, you have to shoot him down. Well, simply take the dot product of the direction the robot is facing with the vector from the robot to the player, and if that vector's close to one, he's in front, fire away. If that's if it's negative, you know, save your ammo, he's somewhere behind you, you don't see him. Okay. In addition to some of that basic math, there's going to be a few new things we're going to introduce today. Um, you know, shown here on the right, um, you know, the outer products and the

Jacobians and stuff. Um, you're probably wondering, outer product, what's that? Well, the dot product or inner product is something you're already familiar with. You can think of that as a row vector times a column vector, and that gives us the scalar we're all familiar with. The outer product, now think of it as a column vector times a row vector. The rules of matrix multiplication produce give you a 3 by 3 matrix. Um, you're probably scratching head wondering, okay, well, you know, I started out with six numbers, I've got nine. That's like lossy file lossy compression where the result is bigger than the original file size. What's the point? Well, this this is actually useful and we'll see why, but first let's take a look at um, sort of a geometric understanding of what the how the outer product might be used. Okay. We already know that um you know, what the dot product is. Let's say we have a vector that's of unit length U. And we have some other vector V, and we take the dot product. And that gives us this distance of V as if we projected along U. Now, that's a scalar.

If you want, let's say, a vector along that line, then we multiply U.V times U, and that gives us this line. So, V projected onto that line. Okay. So, now can we So, that's if So, if we have U times U.V, can we change the brackets and move it over to the left so it's U.U times V? Well, that doesn't work because that's just one times V, which is actually V, which is different than this projection vector that we wanted. So, to do that, it's actually you take the outer product of U with itself, and that gives you a 3 by 3 matrix that if I multiply that matrix by any vector, it projects it onto that line. Okay. So, think of how you might write your player navigation code. You know, you got some guy running around your world, you know, and the user hits the W key and he's running along and he hits a wall. And well, you don't want him to go through the wall, but you don't maybe you don't want to have him stick there. You want to have him maybe slide along the wall. So, you've probably written a

routine like this called slide along wall, where, you know, you take the the intended velocity or vector of the user V, and you know, you have this U, let's say this U vector's now sticking into the wall. And you subtract out the that component of the motion, and you're left with what the green arrow there. The you know, so the player's sliding along the wall. All right. So, in that little equation, we see V show up in there twice. Can we factor that out? Well, indeed you can. And what you get is the identity matrix minus this outer product is now this 3 by 3 matrix that you can use to project uh, vectors onto a plane of which U is the normal of. Okay. Now, why it's better to have some why sometimes useful to have things in that matrix form instead of just some function is well, certain things you can you can, you know, pass matrices into like other systems of equations and so on, where you can't necessarily stuff an arbitrary function. Okay. And we'll see more uses of this later on. Okay. Now, at first, because there's a lot of geometry

algorithms that we're going to writing, you know, this is the bane of existence of these things is numerical precision issues. If you're doing graphics and lighting, you know, everything just kind of works out, you know, you know, that pixel will always be the right color. But, you know, the problems are more when you're doing things with geometry like slicing and dicing and stuff. Now, it it comes to this. When we have a line, for example, it's a continuous thing. And if you sort of zoom in, zoom in, zoom in to like the lowest bits of precision, and you start looking at points along that line, well, they're not really on the line anymore because you don't quite have the precision to do to do that. And you're thinking, well, you know, floating point, you got 23-bit mantissa, this should be more than enough precision. Well, the problem is not is you're still not enough because you might have a long line segment, and you're chopping it, let's say, really close down to the making something really short. And as a result, you can sort of change the direction of that line a little bit, and can throw things off. Or you have those two lines that are sort of like this, you saw examples in the previous talk. Or you might be doing successive operations, and you get numerical drift, and things get really

bad. Okay. And we're going to see examples of this issue later on cuz it's just something that we have to be aware of. Okay. So, geometry, let's take a look at the building blocks. Now, um, you know, triangles and planes. And your college math class probably taught you that a plane is a 2D subset of a 3D space. In games and graphics, of course, we, you know, our planes and triangles have to specify an above and a below, you know, or on top or in front, behind, whatever you'd like to call it. So, for triangles, typically, there'll be a normal vector for the triangle saying which way is above, and maybe a counterclockwise convention to the vertices. Uh, for planes, it's that A, B, and C of the plane equation that define the normal which points up above. Okay? Also note that I I prefer to use a convention ax + by + cz + d = 0 cuz then I can think of my plane-to-point test as this 4D dot product of the of the homogeneous coordinate or homogeneous point with the plane equation itself. Uh, one more small note, um, often instead of saying A, B, C, D, you know,

people will interchange and say X, Y, Z, W because that's the same convention used for quaternions and homogeneous coordinates and float four registers and da da da da da. Okay. So, So, now, one of the things that we're going to need to be able to do is, uh, you know, maybe find the intersection of three planes. Where do they all meet? You could have three faces on a mesh, and you want to know that vertex location. All right. Well, this is a classic linear algebra problem of three equations and three unknowns. The X and Y and Z components of your position V are the unknowns. So, take your three normals from the plane equations, put them in a 3 by 3 matrix, invert that, multiply it by this vector that composed of the W coordinates, and voila, you get your answer. Now, if you have two planes that are parallel, well, that matrix won't be invertible, and there's no answer anyway. So, all the math kind of nicely works out. Okay. All right. So, what if we have four planes? Well, okay, I have to explain what I mean by this problem. And I'm going to do it with an example. Let's say I'm building a house. I start with this floor, and I build up the walls, and then I'm constructing the roof. And before I'm done, you know, I

want to know, well, what's the top of that house going to look like? You know, how do those four planes come together just based on the plane equations? And there's three possibilities for that. I can have sort of the north-south come together first, or the east-west, or they might all actually meet at a point. Well, using what you just learned from a previous slide, you can think, oh, I'll grab three of the planes, generate a point, test it against the fourth plane. And yes, that will work, but one of the things that we like to do whenever we construct algorithms is, you know, can we do it in such a way where we're not sort of, you know, picking, you know, how do I pick the three, who's the odd man out, and so and so on. So, instead of that, let's try putting all four plane equations now in a 4 by 4 matrix. Now, if they all do meet at a point, well, then I'll have a solution to the equation that's shown on the slide here. But I'm multiplying something by something else, and I'm getting zero. That's only going to happen if that matrix is singular. And we know a simple test for that already. And that's saying if the determinant of the matrix is zero. Furthermore, if my other plane equa- if my plane equations are in this, uh, matrix in a, you know, in a nice, you

know, clockwise counterclockwise order, and I I don't put any of my roofing material on upside down, then I can use the sign of the determinant to distinguish between the other two cases. Okay. Now, you've seen this, but I'm just going to, you know, ram it down your throat because everyone needs to know this. So, sorry if it's review. But, intersecting a line with a plane, I've got two points, and I want to know where they meet. V0 to V1 is my line segment. I can do that test, and I know the distance above and or below the plane. Okay. And so, I think of now as I'm traveling from V0 to V1. Okay, think of yourself moving that direction. And so, I'm just it's a matter of just solving, uh, you know, for what at what time do I cross that plane? And shown on the right is that's high school math to find that value of T or for time. So, once you've got that, then you take that value, shove it back in your equation, sort of move along that line, you know, T, you know, that that fraction T, and you've got your 3D point of impact. Okay. All right. So, getting back to doing some interaction in in a game, well,

things are made of triangles. So, if I've let's say the user clicks on his mouse, you want to know well, what did he click on? Or you've got some bullet flying through the scene and does it hit the bad guy? So, yeah, here we have to test this ray, the path of the bullet against our geometry, say a triangle. So, we you know, we the triangle sits on a plane. We find the point on the plane where it hits. And and then we say, well, we don't know if it's inside or out. So, we test against all of the edges. Okay, this is the simple easy, you know, simplistic way of doing it. And um in order to test against an edge, you know, you have the edge cross product with the, you know, from one of the edge vertices to that point. And if that cross product vector points the same direction as the normal, then yeah, it's on the inside of that edge. On the inside of all three edges, you hit the triangle. Outside any of the edges, obviously you missed. Okay. Right. And that's the same that's sort of the simple first implementation you might write and implement. Okay, but things in your game, they have like thousands of triangles on them.

Well, the answer is simple. Just check against all of the triangles. Now, okay, that's obviously going to be fairly inefficient. And I invite you all tomorrow to attend Gino's talk on spatial structures cuz he'll tell you how to rule out many of those tests all together. Okay, but just conceptually for now, you can sort of think of it that way. But also keep in mind, depending on how you traverse the structures spatial structures and this and what's in your scene, you know, if you if you detect a hit, oh, I got a triangle. Well, you might have to keep checking cuz there might be something closer, right? You know, that hit. So, as you're checking, you sort of shorten your ray and keep going. You know, cuz you don't want to spray it like a, you know, a bunch of bullets against the crowd and have the people in the back fall down. No, no, you want the zombies in the front to fall down. Okay. Next, here's an issue you need to be aware of is I can have two triangles, you know, nicely sitting together. And I shoot a ray and whoa, it goes right through. You know, but but the same edge, they got the same points. And that's because of this naive implementation. When I'm checking against one triangle, I generate a point on that plane. And let's say, you know, numerical precision just just falls outside an edge. Check the other triangle. Well, I'm projecting onto a

different plane. So, I'm generating a different point. Okay? And and so, you know, you have to kind of be aware of this. I mean, a simple fix would be to kind of make the triangles a little bigger or something. Or, you know, you can go back and study Gino's slides and you know, with Plücker coordinates and do this all the correct way. Now, and finally, your meshes themselves, well, they have to be intact. You know, if you've got teeny sections that are holes, you can imagine a bullet flying right through where there's a missing triangle. And that brings us to this notion of solid geometry. And this should have, you know, we touched on that a little bit in the last section, you saw that. And that's this idea where you have a borderless manifold mesh. So, anytime you have an edge, there's a face on both sides. And the poly and the normals are sort of all consistently facing outward and so on. And then it's all watertight. Nothing could leak in or out. And so, the mesh itself becomes this infinitely thin boundary representation separating solid matter from empty space. Okay. And then, given that, I can I can take a point and I can say whether that point definitively is inside or outside of my

mesh. Just simply cast a long ray. If you first hit the backside of a polygon, it has to be on the inside of the object. Otherwise, it's free and in the clear in in in empty space outside. Okay. All right. So, that's a little bit of review for everyone. Um now I'm going to dive deep into convex meshes. Okay. Now, your university classes or textbooks might have described a convex set is one for which any two elements, if you have picked any two elements in that set, the line segment between them must also be contained in that set. Okay. Now, a more intuitive way to understand a convex mesh is to think anytime you've got two neighboring faces, their normals are going to be tilting away from each other instead of towards each other. A test for that, take the cross product of, you know, triangle face A with face B and the and the result should run in the same direction as the edge according to face A. Um you can also think of a convex mesh as a volume bounded by a number of planes. The intersection of a number of half spaces, essentially. Or, you can think of every vertex lies at or below

every other face. Okay. So, the reason for convex meshes is that all a lot of algorithms become so much easier to implement. Okay. For example, an in and out test. Well, to test if a point's inside a convex mesh, I just have to check with all the plane equations. If you're underneath any all the planes, you're inside. I don't have to worry about those edge tests and corner cases, numerical robustness and all that. So, that gets a little easier. Um testing a ray, if, you know, like like that bullet flying through space, whatever. For a ray intersecting a convex, well, for okay, so I've I've got that ray and and then for, you know, I've got this thing made out of planes and just for whenever I've I take all the planes that are facing against the ray, so like the dot product of the ray and that plane normal is less than zero. And then it's just cropping any part of the ray that lies above, right? So, here I'm sort of moving the back start of the ray, this V0, moving it up, you know, as it's being chopped by each of these planes. And then what if I'm left with something of positive length, then that V0 is now the point of

impact. The last plane that sliced it is the normal of impact. And this generalizes, of course, to a general line segment uh with two end points. And it's sort of in addition to trimming, you know, from V0 with the front facing planes, I trim V1 with sort of the back facing planes. And if I'm left with something of positive length at the end, then that's what's stuck inside my object. All right. So, convex to convexes. Well, there's a nice property here that if there if two convex objects are not interpenetrating, they'll be a separating plane between them. And I'm sure the physics sessions tomorrow, if you attend those, they'll tell you all about fast ways to find these. Furthermore, if they you if they are separated, one of the planes that will separate the two will be either a face from one, a face from the other, or something that takes an edge from each and the cross product is its normal. Okay. Um learn more about that tomorrow, I'm sure. If two convexes are touching, then the area or contact patch where they're touching will be either a point, a line

segment, or itself a convex polygon. So, you can understand why physics engines really like these things. Okay. So, I've sold you that, hey, convexes are cool. We want to use these for a lot of reasons. But I've got things in my scene and oh, they're not convex. What do I do? Well, in that case, you generate a convex hull of those for those uh meshes, which is simply the smallest convex mesh that contains the original mesh. Well, so how do you do that? Uh this is something that people have been doing for like 40 years now. And there's two general categories of approaches for generating convex hulls. You can start with like a big bounding box and you kind of shrink it down and try slice it, chop it, you know, whatever, until you get something that tightly fits all your points. Or, you can start with a small with like, you know, maybe a couple back-to-back triangles or tetrahedron, something convex, and then you add points to it, keeping it convex as you grow it out until you've grown it out to contain all your points. Okay. So, the most popular implementation out there is QHull, based on the Quickhull paper. And it's one of these expansionist types

of algorithms. Um it works in an arbitrary number of dimensions, but typically if you're going to use it, you're going to use it for three-dimensional things. Uh and it's the one of these expansionist approaches. And so, I've just illustrated what that looks like on the right. You know, I've got some convex mesh and there's new point that we're going to add. Find all the faces for which it's above. Okay, then you throw those away and there's left with a silhouette and then you fill fill that hole with uh a new fan of polygons. An issue is you got uh oh, and then just continue for the next vertex and and so on until until you've grown it up as big as you want. But at each step, you have this issue where um you know, you have to make sure that things are still intact and convex. And even the original Quickhull paper says, yeah, we have these numerical robustness issues, they always show up. You just have to, you know, constantly scan for them and fix them when you see them. What that might look like is as follows. Here I've got some little hole and I grow it with this new yellow point out here. Throw away a couple triangles and I add these three. And notice that one of them

is kind of skinny. And so, it may you can see where, you know, if something's skinny like that, you know, the normal might be bent over in a in a weird way and it might not be convex. And so, maybe flipping an edge or something will fix that sort of thing. Okay. And and these algorithms typically work with um you know, winged edge data structures, which are very effective for this. But there's also a simple approach for hull generation um just based on triangle meshes, and also works. And that's to think of again, it's this one of these expansionist approaches. So, you have this triangulated mesh. And anytime I want to uh iteratively grow the hull with new points, I find all the triangles for which it's above. Then I take a tetrahedron and I glue it on top. Okay? So, where the three, you know, the three other points are the three vertices of the triangle that I'm putting it on top of, and the fourth point is my new point up here. And then, you know, cuz we you know, we don't want all these all the stuff inside, you know, we sort of just delete all the back-to-back triangles. And I'm left with just the boundary representation on the outside. So, you know, fairly simple, fairly elegant. But

it's it, too, runs into this numerical robustness problem. Um cuz you can get generate the folds and stuff even with this approach. So, uh I'm going to sort of dive into a little an example here to illustrate uh how they happen and how to fix them. So, imagine I've got some point cloud and a bunch of vertices that I'm generating convex hull for. And five of these points, A B C D E, are all at one end of the of this cloud and they're all sort of coplanarish. And at some point, you know, I've generated a intermediate hull that's got all the points except for E. And and now we want to add E to our hull for whatever reason. And okay, so I I test E with the left triangle and using, you know, six-bit mathematics, it, you know, tells me that it's below. Okay. And then I test with the right triangle and, you know, bad numerical precision, it tells me, oh yeah, you're but you're above that triangle. So, then I have to slap a tetrahedron on top of the right triangle, lift it up, and that this new vertex is over to E. Well, look what happened. I've got this upside-down red triangle that's facing the wrong way. So

as long as I have one point that's inside my convex hull, I can, you know, test for these and detect them. The solution is as simple as the way we're generating these hulls. You just take a new tetrahedron and you shove it in there. What it does, it deletes the bad triangle and the and the one that we didn't lift up in the first place, generates the two green triangles shown on the far right, and I'm left with this nice convex hull, everything facing outward as we like. Okay. And that's how that works. All right. So a lot of the off-the-shelf convex hull algorithms out there are going to generate your complete hull with all points on the extreme, but you may not really need all of those. Imagine if you've got a, you know, a whole bunch of points in a point cloud and there's sort of this round feature on the side. It's all of those, you know, every single one of those points, if they're extreme all are going to be included. The thing is a convex hull's already this gross approximation, right? I mean, you don't need that many points. You know, maybe 30 will probably be more than enough. So the quick hull algorithm, it's order n log n time, and that's the contribution of the paper. One of the reasons that it that it is that way is because of the way they sort

of order vertices to add to the hull. So instead of that, I mean, we don't really care about order n log n because this is offline processing typically. We're just kind of preparing our stuff to use at runtime. This isn't at runtime. So but let's instead at each step, let's always pick the best vertex. So we're always picking the best one to increase our volume of our hull the most. And then we can just stop if we adding new vertices doesn't improve it or if we've kind of reached a threshold, we don't want any more vertices than that. Okay. So that's the way to, you know, make your stuff game efficient. Okay. Furthermore, there's uh there's trade-off between minimizing the number of planes versus minimizing the number of points. What I've shown up here is two platonic solids that illustrate this trade-off perfectly. One has fewer planes, one has fewer points. Now, the algorithms I described for simp- creating simplified hull work on vertices and they're triangulated, but if you uh you you can use what's known as a geometric dual to solve for the other one. And I'll I'll just kind of

leave it as an exercise to to look that up and study and study it because I don't have a whole lot of time to get into it in a lot of detail, but essentially you by taking the dual and, you know, so I have all these points that are actually the plane equations from this original full hull, when you compute a simplified hull that minimizes vertices, you're actually minimizing planes, take the dual back, and you've got, you know, this a hull that will look more like the one on the right, you know, vertices will typically have a valence of three, um and, you know, faces will have, you know, five or six sides as opposed to something that looks triangulated. Okay. Um some of the There's and there's a trade-off. Sometimes you want uh fewer vertices if it's uh something like you're doing GJK a lot. Sometimes if you're doing, you know, like a lot of plane tests, then you want to have fewer planes. So it's there there's trade-offs for which is better. All right. Okay, so you you know how to generate convex hulls, but you know, let's say I've got some objects that it's not realistic enough, you know, I'm things are colliding in the air and it just doesn't look right, you know, the fidelity is is missing. So the solution

there is to take, you know, more complicated objects and break them down into convex parts, so you get a tighter fit. An artist can do this in 3ds Max or Maya, but fortu- fortunately, uh that could be a bit of work. Fortunately, there's a couple tools out there that can help. Uh John Ratcliff on the physics team now at Nvidia and Khaled Mamou who now works at AMD, both of these guys have uh written software that's open source, free to download and use, that you can throw in your game engine and it'll do exactly this for you. Alternatively, if you've got skin characters, well, you've already kind of done the work cuz you've got it's rigged, you've got bones. You can grab a the for for any of the for all the bones, simply sample your skin mesh, find any vertices that are weighted to that bone, and generate a hull or collision volume based on that. Okay. So an example of that is shown here. And okay, I I mean, you all seen, you know, ragdolls falling downstairs demos and that sort of thing. So here, you know, you see this the skin mesh that we're that we're drawing and showing. Okay. And but instead of the actual skin mesh

being doing the interaction, it's really the underlying bones that are that are doing all the collision detection and interacting in the scene. Okay. So that that's that would be the way to do it. And not just characters like full body, but, you know, other types of objects as well, you, you know, you would do the same sort of thing. And there's our ragdoll hand, for example. Okay. Okay. Next I'm going to we're going to take a little detour and take a look at Boolean operations, another fun subject in computational solid geometry. So this is when you have a mesh, you remember they're solid, they define sort of empty and solid space. And if I have two of them, I can do set operations, union, intersection, and subtraction. Couple examples are shown in this video. Uh now in the general case, you know, you want to have a good winged edge data structure to to implement this, and what you would do is you would take all the edges of one, slice them with all the faces of the other, and vice versa. And then whenever one passes in or out of the other, you have to sort of tessellate along it, you know, adding

new edges, and for the other one as well, and then match those edges, and then sort of take half of one, half of the other, stick them together, you got your Boolean operation. Okay. Now, what I described in a few sentences actually a heck of a lot harder to implement. You know, you've got all those corner cases, numerical robustness, you know, tolerance issues. It's it's not easy. So let's take a step back and think, okay, where where are we going to use this the this stuff? You know, certainly level design, modeling, there's applications there, but a lot of your art tools, they already have this stuff built in. Um so if you're thinking at runtime, well, you know, hey, you know, destruction is kind of fun or geomodder I'm traveling through through some environments and that. But in these cases, you know, I don't have an artist who's like finally tweaking and placing points. No, no, I'm like chucking grenades and blowing stuff up. So you know, you might be thinking, okay, is there like a, you know, a quick and dirty simple approach, maybe something based on convexes since we've been looking at those recently. And sure, okay, let's explore that a

little bit. So um we've already seen, you know, mesh cropping or sli- or slicing where we, you know, chopping all the edges. If you uh crop a convex mesh, you have this nice property that there's, you know, you get an open loop, okay, but there's only going to be one. Okay, in general mesh, you can get more. And but in that loop is also going to be a convex polygon. So it'll be easy to triangulate if you when you get to that step for rendering. So intersecting two convexes, you can think of it as cropping one with all the planes of the other. Okay, but you wait wait wait a sec. You saw I took a convex mesh earlier and another convex mesh, and I subtracted one from the other, and the result wasn't convex. How how does that work? Well, that's because I mean, that was a subtraction, not a not an intersection. The subtraction with the with the solid is the same as doing an intersection with all the stuff around it. So you can do non-convex operands as a union of all these of a bunch of convex operands. So

basically do all those convex to convex intersections and then just, you know, throw the result together. Okay. All right. But even crop- Okay, we saw convex hull, you know, bisect- you know, chopping a line, even chopping a convex object, you're subject to those annoying numerical robustness issues. Um and, you know, this is you can do things like, you know, okay, check the planes, make sure, you know, you're not generating any sort of twist because if you have a plane that's coming very close to a vertex, you might if you make a mistake and you you sort of, you know, chop these edges instead of those ones, you can generate little problems at the corners. Um you know, but and then it still gets more hairy because, you know, may- you might have more than four planes. You might have like five or six. And so uh you're probably thinking, oh, there's too many corner cases. Is there something simple I can do like a snap to grid or something and just not have to deal with any of this stuff. Okay, so here's a little trick that I've been doing for geomodder for a while that kind of works. And and that's uh not snap to grid, but it's something a little different. It's quantize the plane equations.

So uh so any of the Boolean operands will only have plane equations that satisfy certain conditions. And what it is is I take for Remember our plane equations are ax + by + cz + d = 0. If I multiply those numbers by some number, it's still the same plane. So I make sure for any of the plane equations I have, there exists some number I can multiply by so that a, b, c, d are all integers. Furthermore, a, b, and c are integers less than a small constant. All right. So now recall how when I have a vertex, it's going to be the intersection of three more planes. And how do we compute that? Well, we have this matrix, right? And that M matrix there of the normals, that's all integer values now. I invert it and multiply by this vector, which are all integer values now. And so the result is going to be this point V, of which its x, y, and z components are all going to be rational numbers, where the where the denominator is no larger than the determinant. Because when I take an inverse of a matrix, I have to divide by the determinant. So that means for any two points I

generate, if they're not the same point, they'll have to be at least one that one over that determinant distance apart from each other. Well, what this gives me is a hard-coded fixed epsilon I can throw in my code, you know, to test whether to tell me whether two points are the same or not. Okay. And based on that, you know, I can throw rocks at this piece of glass all day and nothing is ever going to break. Well, the glass is going to break, but the code isn't. Okay. So now now even though I'm doing this, there's no integer math in the implementation. No, no, no. All that stuff you saw in the last slide, that was just proof that this works. The implementation itself is, you know, floating point math, 32-bit, you know, don't need double precision. Uh normals are of unit length, you know, just as you'd like, but the code itself doesn't have all those fancy all those crazy corner cases if then else statements and and this and that. So, although here it's running on in just, you know, single core CPU, I mean, it's potentially could run on a GPU fairly easily like GP GPU type of

implementation. And it's fairly efficient. I can do many Boolean operations per frame. Break lots of break lots of glass. I can take the the part that I take that I chunk out and I can generate little pieces of fragments or extra rigid bodies from them. Okay. So, hey, that new that number theory course I took in university was actually useful for something. Okay. Next, we're going to take a look at some of their spatial properties of our solid objects. So, when we have these meshes and they're solid, again, I'm stressing that's an important factor, we can correctly calculate the volume, center mass, and the inertia of our objects, which will affect motions, we'll see. Okay. So, I'm going to cover a little bit of review material for or new or introductory material, depending on your perspective. Okay, so the center of mass of a triangle. Now, there's many ways to define center, but this is the center of mass. If I chuck the triangle up in the air, what point is it going to spin around? That happens to be the the point where if I take the three vertices and divide by three, that's

that point. Okay. Uh the area of a triangle, well, if I if I take two edges, take the cross product, uh figure out its magnitude, uh half of that is going to be the triangle area. Now, if I have a triangle with a predefined normal, well, then instead of, you know, taking the magnitude, I can just take the dot product with that normal. An advantage is here is actually get a signed area, so I could have triangles of negative area negative area, and soon we will see why that's useful. Okay. Okay. Now, just to make it clear to everyone, it doesn't matter which two edges you pick, you know, when you take the cross product, you're going to get the exact same result, unless you're going the other way, and then you'll get the negative result. Okay. So, how do I get the area of a polygon, something with n points? Well, break it down into a bunch of triangles. Find some reference point P, could be the origin, doesn't matter. And for every edge on my polygon, take those two vertices, my reference point, that's a triangle, and just add all those areas together.

But what if this point P is on the outside of my polygon? Or if my polygon is all sorts of concavities and stuff, it's not convex. It doesn't matter, this still works because, you know, sure, I'm covering a bunch of area that's on the outside, so I'm you know, but I've also going to be adding uh these negative uh area triangles, so it's going to cancel all that out. So, you get the same result. It just works. Okay. Oh, here Okay, so here, if I've got a tetrahedron, and now if I take the cross product from all four of the sides and combine them together, they cancel each other out. Okay. So, add these four vectors and the result is zero. Now, remember how we generated those convex hulls with the slapping the tetrahedrons together and then removing the back-to-back triangles, which obviously those two normals will cancel out. So, if in this So, by mathematical induction, you can conclude that for any mesh that's closed and solid, adding up all the area weighted normals is going to add up to zero. And that lets us actually And that's why this works.

Okay. Generating the polygon normals the normal of a polygon with n points, and this could be a polygon I shouldn't have drawn a convex one cuz it can actually work with something that's concave concave and points slightly off the plane equation and stuff. It's a matter of adding up all uh combining all the uh triangle normals. It's the same sort of triangle summation. Not the magnitudes, but, you know, taking those vectors, combining them together, and getting this long green vector shown in the bottom right that is the normal of the polygon um and length is double the area. Okay. And again, if this point P lies on lies on further away, sure, you know, those arrows are going to grow on top because there's more area, but there's also, you know, negative things pointing down that sort of cancel each other out. The reference point P doesn't even have to lie in the same plane as all the other points. Uh the only way it's going to break down is if that if P is so far away that you're going to run into rounding error. Okay. All right, so that's the 2D stuff. Now, let's start looking at the 3D uh things.

You may have guessed that the center of mass of a tetrahedron is the average of the four vertices. And volume. Okay, well, that's sort of base times height, let's think of that. Uh the base uh uh area um is, you know, we have that cross product, which conveniently gives us this vector that points straight up. Okay. So, half of that um now, in this vector form, we we don't we can take as our, you know, instead of cuz we don't know the height per se, but we can take any edge leading up to our fourth vertex and dot product with that because only the you know, this orthogonal component's going to matter, and that will give us our volume. But it's actually 1/3 because it's a pyramid. Okay. So, this cross dot combos also known as the triple product, and as mentioned in an earlier talk, it is mathematically equivalent to taking those three vectors, the three three edges from this tetrahedron, shoving them in a matrix, and taking the determinant. Okay. All right. So, whatever we can deduce

through simple geometric reasoning, we can also solve through very complicated calculus. So, what I've shown here at the top is this is the definite integral where the limits of the integration de- uh describe the the limits or the region of the tetrahedron. And I can pass any function I want into there. So, if I take my unit function, I pass it in and run off for a few days and write out all this calculus and make sure I'm right, I I'll will come back with a formula for the volume. If I pass in a function that's uh that basically returns the position, you know, that with adjusted for for volume, then I get back my center of mass. Okay. Now, I'm going to invoke this a little bit later, I just wanted to take the opportunity now to scare everybody with it. Okay. So, all right, you don't have a whole lot of four-sided four poly objects in your game, you probably have like thousand tens of thousands of triangles on your objects. So, how do you get the volume of them? Well, now, just like we saw a triangle

summation, what we do here is tetrahedron summation. For all the triangles, you know, the three points plus some reference point, perhaps the origin, we just add up all these tetrahedron volumes, and that gives us the volume over our entire object. And again, the same principle of, you know, uh things falling on the outside and negative weighted or negative volume tetrahedrons canceling out, it all just works. Center of mass, well, as you'd expect, it's just a volume weighted average of all the center of masses of all the little tetrahedrons. Okay. So, getting the right center of mass is a good thing to do. So, here in here we have this catapult arm sort of thing, and it's got uh sort you know, we throw it in physics scene, rig it up with a hinge joint, and there's sort of this large volume at the other end of the at the end of the handle. So, the center of mass, you know, you know, if we calculate right, it's going to be somewhere around there. And then we just kind of let it fly in a game environment, we kind of get this nice behavior that we'd expect. Now, we didn't have to write any custom code. We didn't There's no springs here. This is just emergent behavior, the way that we like to enable artists to build things. Had I taken the bounding box of this

object and taken its center and used that as a center of mass, we wouldn't have had this kind of behavior. Okay, so having solid meshes and solid matter matters. Okay. All right, so the third aspect of uh spatial properties that affects motion is the inertia. Uh hopefully everyone's familiar with the moment of inertia in 2D, and you have this idea that if you've got something spinning, you know, something orbiting around a fixed axis, then, you know, uh it it for stuff that's further away from that axis, it takes a little bit more energy to get it up to speed. Okay. So, I've I've rewritten this moment of inertia calculation in in a couple ways here, so you can try to understand it as, you know, it's sort of the variance along X plus the variance along Y to give you the moment of something spinning around Z. Cuz when we step up to three dimensions, you know, it's not a scalar anymore. We have a 3x3 matrix known as the inertia tensor that describes uh the motion of an object. And it's And the form of that shown in the in the bottom right, and

there's a high relationship between this matrix and the covariance matrix. So, in order to compute inertia, we're actually going to compute covariance cuz, you know, with one you have the other and vice versa. Okay. So, if you studied statistics, this might look familiar to you. Um if not, it's still pretty easy. Imagine if I have an object that consists of a number of discrete little point masses. Okay. To compute its covariance, it's simply, you know, summing up, you know, the outer product of all those positions with themselves in a matrix. Okay. So, yes, here's yet another use of that outer product that I mentioned at the beginning. Okay. So, all right, that works for that gives me the covariance of something with a bunch of points, but our objects are these continuous solids. So, what we're going to try to do is one of those uh tetrahedron summation tricks. So, now if I just get the covariance contribution from a single tetrahedron, then I'm done. Um so, what I'm going to Now, I'm going to reinvoke that scary triple integral, but I'm going to shove inside of it the

that outer product. Okay. And um I I did this online on WolframAlpha, where I'd like shove in the equation, but then it timed out on me. So, I had to like put in part of the equation and then get half the result and then shove in the rest, you know, cuz the the free version online just, you know, it doesn't give you enough free cycles or something. But um you have to trust me that the answer at the bottom there is the right. So, if Now, I know this calculus might go over the heads of some people, don't worry about it. What we have now is a formula for getting the covariance contribution from a single tetrahedron. And then, remember we wanted to get the inertia. And so, we have this covariance, and I've rewritten in the middle line there as in another form cuz it's a 3x3 matrix, so each of the IJ elements of that matrix looks exactly like this and we're summing over the mesh where UV and W are the are sort of the the three vertices of each triangle, but because we know things are, you know, will spin about their center of mass, we can't use any reference point. We have to use the center of mass as we do this

summation. Okay, so let's say, you know, we got covariance and then to get to inertia, it's that formula that I that's shown at the bottom. It's it's a because if you look at the top you know, we see the Y Y plus Z Z in the upper left hand corner of the inertia matrix. That's because, you know, if you're spinning around X it's the stuff along X that doesn't matter it's sort of the other two and that, you know, the relationship between the two. But the matrices covariance and inertia they have the same eigenvectors they diagonalize the same so it's all good. So anyway, enough of that. We you know, we've got our inertia matrix. So let's you know, how do we use this? And what the inertia is is it defines the relationship between angular momentum and angular spin. But but spin also depends on the current orientation. So here here we've got some spinning some spinning objects. They all have they're all the same object. They have the same angular momentum, but the spin is very different because they started at different orientations. So you can see

some things are going to be spinning a little faster because they're going around, you know, sort of the long axis versus the short axis, right? Even though they have the same momentum. So as we knock these things around, you know, we sort of get the behavior of the way things process process and all that stuff. Now there's no gravity, but you know, hopefully that yeah, as we hit things it takes less energy to get them sort of spin sort of the short way versus the long way and stuff. Here I've added gravity back in, but apparently not a whole lot of gravity so this looks like you know, kind of in slow motion like, you know, got a GoPro camera and you're like filming your skateboarding tricks or something. Um but you know, hopefully the behavior looks yeah, this is kind of what you'd expect, you know, you could do kickflips in an environment like this. Um yeah. I made it perfect. Okay. Oh yeah, the equation is, you know, sort of shown shown on the right there. And you you probably notice also that the spin vector sort of changes. It's the momentum that stays constant, but the spin actually changes from frame to frame. Okay. So what we looked at so far was the volume integration or calculating these properties of our objects. So

now you know, that's sort of the work half and now let's study the other half the fun half a little bit more and that's this time integration. Okay, so volume integration and then now time integration. Well, that's just fancy terminology for how you update some objects from its current state to where it is at the next time step. So for position, you've got some guy, you know, position PT at time T. His position at PT plus delta T is simply you add its his velocity times the time step and you got the new position. So okay, this morning you took a class about quaternions you're thinking, hey, I've got a spin vector. I know how to create a quaternion from that that, you know, based on the spin and so I can multiply that quaternion pre-multiply that quaternion by my orientation to get my new orientation. And yeah, that sort of works, but one of the things and we'll see why in in a minute is that we what we'd like to do is form these time integration equations as adding instead of multiplication. So the form on the on

the right here is where I've got my next state my next orientation is my current quaternion current orientation plus this derivative plus the derivative I E how that quaternion is going to change times the the time step value like how much I'm going to or how much time has elapsed. Okay. So it gets a little trickier. Another important thing is that remember that spin vector we saw that was sort of changing? Um the thing is when I'm doing this orientation update and and this is the problem that that it's only valid at the beginning of the time step. So I can't really apply that same vector that same spin for the entire time step. Um you get this thing called numerical drift and it's best explained by, you know, if the classic example of, you know, you're following the path of a circle. So say I'm, you know, following the path of a circle I, you know, what I would do is I would look down, what's the tangent, take a step, okay? Look down, what's the tangent or the derivative, take another

step and so on. But if I'm taking big steps shown in the little picture there in the upper right, I'm going to be slightly, you know, getting further away from the origin or falling out of orbit. Okay. And that's that's what happens with the typical what's sort of known as a forward Euler update. You sort of, you know, take that derivative from the current time step and you apply delta T time to that. So now instead let's say I'm going to I'm going to use a different approach to follow a follow the path of a circle. Okay, using this Runge-Kutta technique. What what you do is okay, you look down at the circle you say what's, you know, what's the tangent? Okay, then instead of taking a full step using that along that tangent you sort of look half a step forward in that direction, look down, what's the tangent at that point or the derivative at that point? Ah, okay, now you've got a new derivative. Lean back, take a half step along that direction, look down, what's the tangent or derivative here? Okay, got it same value, lean back. Now reach look lean

sort of forward a full step with that latest tangent vector, look down, okay, what's the derivative or tangent out here? And then instead of using that last one you take actually this weighted average of all four of those derivatives or all four of those tangents and you and that's how you advance yourself, okay? And this works great for people who like to walk around in circles and it's a perfect way to update our orientation in our in our games. So first I'm going to show objects with a very high angular momentum. Okay, and I'm going to turn on that forward Euler update. And look what happens. Okay, my object gained a whole bunch of energy and then the spin sort of converged to one of the principal axes of the object. Here I'm doing that Runge-Kutta update and it's not gaining energy. This just kind of works. It's, you know, sort of spinning getting that nice behavior as we'd expect and spin sort of orbits around the the momentum which is, you know, what this shape of object is going to give us. Okay. All right. So

we've looked so far sort of at rigid body objects and how they kind of work. Now we're going to explore the soft stuff a little bit. Okay. So instead of an object with a position and an orientation, don't worry about orientation, but every vertex on the object has its own position. Now. And but all these vertices are going to sort of be connected with some sort of constraint or spring. Okay. And okay, so when we when we build these sorts of things, you know, there will be a visual mesh for objects, but the way we connect them with these springs or constraints might actually differ from that. Cloth is a classic classic example. So let's take a look at how we'd build like a a cloth mesh for for simulation. Um you know, you've you've got a whole bunch of vertices or points and you're going to create these strong connections with their immediate neighbors because, you know, cloth doesn't really stretch or compress all that much, you know, along that dimension. And then okay, there's going to be some sort of, you know, do an example here if this works, you

know, sort of, you know, you're going to it might shear a little bit like this, but there will be some resistance to it. So for the, you know, for every vertex, you know, along the diagonals you're going to create some sort of connection with maybe a slightly less stiff connection between them. And to resist bending, something bending over like this, you know, you have connections between every vertex and two over in each direction, okay? And you'd have like stiffer connections for something like leather or for something like silk they'd be very weak or non-existent. Okay. And it's not just cloth. I mean, you can build like rubber ducks or things out of 3D lattices of, you know, all sorts of connections. Okay. So for implementing these it really comes down to the time integration, you know, how do you simulate these soft objects? And there's two schools of thought. There's you know, the kinematic approach and the dynamic approach. Now the kinematic approach is to think of, you know, anytime I have a connection between two vertices that's a constraint. Those two things belong at this, you know, this distance apart from

each other. And so for the implementation every frame you'll see if two points oh, if they're further away than they need to be then you sort of nudge them closer. Maybe not move them all the way, maybe you nudge them a little bit closer, maybe do a few passes or something like that. And if they're too close they need just kind of nudge them apart. So it's very easy to implement just your basic vector arithmetic that I'm sure everyone is familiar with. Oh, plus you also have to know how to take a square root assuming you can do that too. Then you can implement this and you can find many references sort of sort of reference implementations and and papers on how to do it. A nice thing is that these systems they don't explode because you're always pushing stuff closer where it's supposed to be. You're not going to get any weird behavior where things all of a sudden you know, vaporize and go off in space. And not surprisingly it's the most common system used out there in games and physics engines. The only caveat is that, you know, because you're the way you're sort of implementing if you have things that are under sort of a true stress either compression or stretch, you know, is there are they guaranteed to converge to some sort of force

correct state? I'm sure there's implementations where people have figured out how to do that, but the alternative is to use a dynamic approach to solving cloth. And this is, you know, more of the pure physics approach and it's to think whenever I have two two vertices that are connected they're connected with a spring that applies force. Okay. So if I've got springs that are fairly weak in force, it's easy to implement. You just sort of, you know, add a little velocity to each of those end points and and it moves and so on. But if I have a let's say a very very stiff spring and let's say because, you know, a character in a game kind of moves one end point or something. Now Now, this spring that's that's stretched out. And if it's a very high force, and I want to simulate that, even if it's only 1/60 of a second, I can like, you know, bang to you know, pull it back together, but it'll overshoot because of the force is just so high. And then it's like, oh, now it's even more out of whack, and then it shoots, and then boom boom it and these things just explode, right? So, the all even if you try to run cutter integration, well, you know, you're sort of looking at half steps, but I mean half of a huge number is

still a pretty huge number, so that doesn't work. The only way to actually implement integrate these properly is with implicit integration or backward Euler. Um and and we're going to take a look at that. But, first let's compare with the kinematic approach. Now, it's easy to implement, you can have like this is actually running on a single core a lot of cloth, it's easy to do. Now, excuse the my shading, it might look a little plasticky, but, you know, hopefully you think and look at this, think, yeah, that behavior works. You know, fairly responsive, I could use this in a game. And yeah, you know, it kind of does the job, you know, and chances are this is probably is good enough for most people. Um the only caveat, as I mentioned, is I'm sort of pulling on things. I have all these constraints that are sort of fighting against each other, and the way these things are connected, you can kind of get this continued oscillation because you're not sort of you know, it's not getting to this relaxed force converge state. It's no no, you're constantly fighting. So, it's only So, that's the only case where these things may break down. Might depend on the implementation, too. Um but we're going to now take a look at sort of the implicit integration approach because it's kind of

interesting, you might actually learn something. Um and and like I said, it's it's based on forces and springs. And the forward Euler approach is as follows. Um you have for every point in your cloth or soft object, you know, it's got a velocity, and then all these springs connected to it, and gravity, and and wind, or whatever else. So, at each point there's a net force being applied to a point or a vertex. So, the forward Euler update would be to, okay, uh divide that net force by your mass, and that would just be your acceleration. Apply that, and you got your velocity for the next time step. Okay, we've already described why that's going to break down because things might explode. So, the implicit approach, what you do is instead of applying the forces at a point based on the forces of the current at the start of the time step, you use the forces from the end of the time step. But, wait a second, those are forces from the future. We're not yet there yet. We don't know what they are cuz we

don't know where everything's going to be. I mean, how can we even do that? And so, that's why for this approach, you you end up creating one of these linear systems and solving for those forces. And in order to do that, you need to know the derivatives of the forces. That is, how the force at a point will change based on a change in position and a change in velocity. Okay. So, now, the thing is with force in springs in a 3D world, it's is a 3D vector, and the I can move something as I move a spring, I can move that point in 3D. So, the derivative is this now this 3x3 matrix known as a Jacobian, and the general form is shown in the upper right. So, that's what we would have to derive to implement these systems. Now, we don't have a whole lot of time left to, you know, go deep deep into a whole bunch of calculus, but fortunately we don't have to. Let's try some geometric intuition instead. When I have a spring, it's, you know, a simple, you know, kind of a linear thing. So, let's first look at what how

does the force change, this derivative of force, along the spring direction? Well, if I have a spring, and let's say one point's at the origin, and the other points at point P, or you can think of it as vector P cuz one side's the origin. If it's compressed, then there's a force at at the end kind of facing out, away from the spring. As I move that out, and I stretch it, now there's a force coming towards me. So, the change in force for a change in position is simply minus K, that spring constant. Okay. Now, surprisingly, if, you know, if the force is minus K minus K times P, well, the derivative with respect to P is just minus K, you know, standard calculus. Okay. Well, that's only half the equation. Now, consider if I move that end point sort of up or down. If my spring is at its rest length, and I grab this other point, and if I move it up or down, well, there's no there's no force, and there's no change in force cuz, you know, because for a small change up or down. But, this really changes. If my spring is now stretched out, then it's got then

and I'm holding it up here, there's a force kind of coming down towards me from that end point. I move that my arm down, and now there's a force coming up towards me. So, there's a change in force, you know, from this to this, right? So, the change is up. But, if but if it was compressed, now I've got this force pointing up, and as I lower the end point, now I've got a force pointing down. So, my change in force for a change in position, you know, anything orthogonal to the spring direction, now depends on where we are relative to the rest length, R, which is shown in the bottom right there. So, for somebody if they actually went off and they solved all that calculus and came back, they would have come back with this, right? That's what the calculus would have given you. But, hopefully, you know, if you follow the geometric intuition, well, and remembered what I talked about the very beginning with those outer products, this should look obvious because it's simply minus K times that first thing in the brackets there, that's, you know, P outer product P divided by P, which is essentially unit length vector along that direction uh outer product with itself. Okay, and that describes this motion, and then the perpendicular

motion simply I minus that for the other term, right? So, cool, you know, now you understand what a Jacobian is, okay? Um the spring equation is probably easiest difference equation, so this is probably easiest example for trying to learn what a Jacobian is that you can think of. Um now, you do the same thing to get change in force for change in velocity, um cuz that's the other, you know, some lower derivatives you need. And then you have all these things, and you can put them in the linear system. Now, I don't have time to go into all the algebra and all the details of it, but essentially it's one of those things where you've got one of those big matrices, you know, AX = B, but X, the unknown, is now delta V. And A, this matrix, is sort of identity minus that term, and and so on, and B is the other vector. And it's a little more tricky because, okay, you you know, it's not just, you know, one 3D vector, but you you know, your your velocity state and your position state are basically this concatenation of all the points in your in your spring mesh. And this So, this A matrix becomes this big sparse linear system and stuff. Um all that stuff's you know, there's

sources I can point you to later that describe it all, but I just kind of want to get some of this geometric intuition so you can kind of see how these things work. Okay. So, I'm going to illustrate, you know, what that can look like at run time. First, you know, we'll take see the what the weak springs look like with that forward Euler update. You see, okay, this is kind of jello-y type behavior. Maybe you could do some ocean waves with this, but it's not real cloth. If you want something to like touch and feel like real cloth stuff, you know, you got to, you know, use those stiffer springs if you're using the the spring-based approach. So, here, you know, it's there's the underlying spring network that you would have, and yeah, okay, this I mean, you already saw this kind of stuff with the kinetic approach. Um Or can Sorry, kinematic approach. Um you know, what's the advantage of the of the implicit integration? Well, here it is, it's when you have these things under stress, right? You know, there's no jitter, no billowing, no energy leaking in the system. In fact, when you pull back a slingshot, you cuz you're actually calculating the forces on all these things. So, if you put a projectile there, you would know how much force to apply to it, so you could launch it, right? It's all sort of force correct. And here's examples of sort of

like 3D objects kind of connected with a bunch of stiff springs, so on. All right. Okay. Now, um that was a kind of a big whirlwind of topics, and you know, we started off looking at some basic stuff, you know, how four planes come together to meet, you know, building that roof, or so on. Um Now, and we looked at sort of solids in motion, and all those kind of things. The main objective here was to try to get people to first of all, to think of their meshes as not just a bag of triangles. But, once you start thinking of a mesh as a solid, you know, and you can have this tetrahedral decomposition, or breaking stuff into convex meshes for collision detection, you know, you have this more intuitive powerful understanding of your geometry. And furthermore, then we sort of looked at, you know, things in motion. Um And you know, a lot of people you with graphics you get this fairly good understanding of, you know, your basic linear algebra, but when you start exploring some of the physics space and geometry space, you step a little bit beyond, you know, some

of that math and learning, you know, the value of things like outer product, and, you know, Jacobians, and all that sort of thing. And that can open the door to new new and interesting fun things you can do in your game experiences. Okay. So, now, admittedly, that was probably quite a lot for some people to digest. Um and you might have questions, and you might not think of them right away, you might think of them like an hour after you leave here. I'll be around all week, so feel free to flag me down, just look for the bodybuilder in the crowd, that's me, and, you know, we can have coffee, and I'll explain things further. Um in the meantime, if there's any questions that someone has right now, I think we might have a few minutes left to answer. Yeah, got a couple minutes. Uh someone has a burning question. I had a non-math related question, which is just what uh kind of input were you using for those hand gesture demos? Um oh, it's one of It's like a depth camera-based thing, so But, like it was it was a Kinect or a Leap? Um well, in this case, I was actually using uh a a time-of-flight camera.

Um so, what I do uh now just we I just got my paper published, um and and uh a coworker demoed this at I3D last week at demo poster session. Uh we take the depth, you know, we have a sort of a model of the hand, um and then we take the depth data, and we want to fit that model to the depth data. I mean, there's a lot of people have been trying to solve this problem. I'm sort of like a math 3D physics guy, and I like, you know, I I was tasked with like um you know, assume that I already have this, and then build cool experiences and interactions. I'm like, but but I need software to track the hand, so I had to like build it cuz nobody had it. So, uh yeah, I took the depth depth data um and then I basically got it like a rigid body model of a hand and all constructed. And I've got, you know, the Oh, okay, I'll Sorry, I'll try to be quick. The you know, the the you know, the constraints You learn about this one. You should go to the physics class, you know, cuz it's really just a an extension of like a physics engine. You know, you have all these connections, you know, that are constraints on on on the joints. You have collision constraints. And then all those little depth values are like

little magnets or something and you just kind of like pull on the surface. You know, you have There's a few things you want to do. You make them a little weaker because you might mismatch, you know, points to where they lie on the surface. And it relies a little bit on temporal coherence because, you know, if you if you're starting from a bad frame, it's not going to the depth data is pretty bad, right? Like for, you know, you know, the speed and fidelity cuz there's can be depth noise and no collisions and all that stuff. So, you really kind of need to take advantage of temporal coherence anyway in the solution. But yeah, we can talk about that online. I can show you I got like a camera here if you're interested. Yeah. But yeah, it's not really related to this talk, but um Sorry. Uh any other questions? Sure. Hey, thanks for that. Um touch to touch in the last part with uh like the spring network. Uh and when you when you do basically uh integration of uh like within that time step uh

Uh do do you have to uh uh take into account all the like the the uh spring springs next to your current basically if you have a if you have a a mass node basically uh with springs uh Uh you have you have mass nodes and they they are interconnected with springs. So, basically all the all the nodes next to your current node uh they kind of have to affect uh the position or or the next position of of the node. Do you have to cache all those like the states of all those nodes that affect your current Yeah. Do you do you understand Yeah, so I'm having problems expressing myself. Yeah. So, yeah, when you're solving any sort of these these systems like even a general rigid body system, you have to solve a lot of these equations simultaneously. Yeah. And then with the implicit integration, it's even worse because it's you're sort of solving kind

of future like velocity and position kind of simultaneously as well. So, it does get very tricky because they everything connects with everything else and they have to solve them all together. So, you end up um and then, you know, you end up sort of adding all these little Jacobians uh you know, in that system and then sort of solving into sort of an answer that will uh you know, you know, energy minimizing type of type of thing. Yeah. But in the middle you you then you will then have quite a lot of data basically. More more data than you begin with to kind of Yeah, it's still going to be all It's going to be order of the size, so it's it's going to be uh you know, the the topology the like the connections uh of each point um you know, that's like every point can be connected um to for 12, say um neighbors. And so, they'll you know, there's you're going to have an amount of data to process like your math equations are going to have that much stuff in them. So, it's going to be like, you know, you

know, over 10 times the number of points in your matrix or in your mesh. Yeah. Right? And it's in 3D, so it's I mean these are, you know, and with position and velocity and other other things going on. So, yeah, there's there's a bigger data footprint. Yeah, certainly the kinematic approach, I mean they have a very small data footprint. It's very um uh that it's it's one of the What helps make them more efficient is that makes it cache efficient as well, too, cuz they have a much smaller data footprint. Yeah. You're absolutely right. There's there's a huge data footprint cost as specifically I'm I'm just trying to create this really flowy water surface and trying get away with like as as as little problem like Yeah. Water you can you can start out with like the the forward Euler systems um cuz you get sort of that nice wavy behavior and then that's that's a good place to start. And then for, you know, for the implicit type things, I mean that's there's a damping to it that just is natural with the integration. So, like the cloth will sort of settle and it's you know,

sometimes you have to do things to kind of create that life back into objects cuz it's even without adding damping terms, it will dampen itself. Um which is, you know, one of something that can happen. Well, Yeah. I've been I've been using the like data from the previous step to integrate like within the integrations and I've been getting away with it. For some reason it works. Maybe maybe my like coefficients are like low enough to for it to work, but Yeah, yeah, if the coefficients are low enough, yeah, the forward Euler's if I if I just ignore about that. Yeah. Okay, thank you. Yeah, no problem. Okay. Oh, sorry, one more. Um so, a lot of this is actually really new to me, but also seemed really interesting. Um so, if we're actually trying to like understand the concepts more in detail and really like get it down, um would you recommend more like just jumping in and trying to write tech demos that kind of follow this or would you Absolutely. Absolutely. Even even if you're using, you know, at work if you're using like an off-the-shelf physics engine or something, it's nice to

you know, uh write your own code of the same thing. Like when I used to work at a GA on the like the PhysX SDK and stuff, one of the one of the things that helped me be of benefit to my employer was the fact that I had done a lot of that kind of stuff on my own in the past before, like similar things. Uh maybe not to the same extent because it's quite a large engine. Um so, yeah, I would encourage anybody like, you know, try writing a GJK algorithm or a you know, a little you know, a little solver for springs, you know, and constantly challenge yourself because then, you know, even if you're working using off-the-shelf systems, I mean you'll understand those systems and the and the issues involved with them. Right? Like that famous force uh that the mass ratio issue with rigid body uh rag dolls and stuff, right? Like what is that? If you've ever kind of tinkered with the equations, it's like, "Oh, you got it." And then you'll be the guy in the room that, you know, everyone's saying, "Ah, we can't ship our game cuz it's broken." And you'll just know, right? So, yeah, I would totally encourage that. It's like, you know, it's the same thing as like if you take a math course without ever solving any of the exercises at the end of each chapter, you're not really going to learn the math as well. So, it

That's my personal opinion, but yeah, definitely tinkering is always worthwhile. But you have to balance it out because, you know, you want to get paid and, you know, you can't spend all your time sort of, you know, reinventing the wheel and stuff, so. Yeah, I guess I was a little lucky because I'm a little bit older, so like when I was at Bioware in the '90s, none of this stuff existed and we just had to kind of re invent, you know, I I got the opportunity to kind of implement all this stuff when it was first around. So, I know it's a little harder for, you know, new guys coming in the industry because all this stuff's already written. No one's going to pay you to write the stuff that I got paid to write when, you know, 15 years ago. So, sorry about that, but yeah, you know. Um but yeah, definitely, you know, ha- hack on this on on the side. It it I I can't stress enough that's very good way to learn. All right, thank you. Yeah. All right, well, is that all? I guess thanks guys for coming.