Building Collision Simulations: An Introduction to Computer Graphics

this right here is a simulation of 250 particles in an enclosed space by the end of this video you have a good idea of how to create something like this but the way i see it this video is actually more than that physics-based simulations are nice playground resorts to explore a variety of interesting ideas in a field of computer science called computer graphics in the process of learning how to build these simulations we will encounter a lot of problems and the tools that we will use to solve these problems show up all the time in computer graphics so here's the plan for the video before we understand simulations we'll take a look at some of the core principles of animation from a computer graphics perspective with this framework we will then build our first simulation which will introduce a variety of ideas in particle dynamics collision detection and collision responses the last half of this video will then be dedicated to managing the complexity of larger scale simulations not surprisingly the more particles you add the harder it is to make accurate simulations in an efficient manner this complexity leads to a variety of interesting ideas that show up all over the field of computer graphics alright let's get started let's say i want to generate a simple animation that moves a circle from point a to point b here's two different animations one of them looks better than the other and the reason why is a nice way to introduce how animation works in practice you see when you view an animation you're not actually seeing one fluid motion from point a to point b what you're really seeing is a sequence of frames in the first animation we have 15 frames that are played in one second some of you have probably heard of the phrase frames per second or frame rate used to describe performance of video games or cameras and this is basically what they're talking about when we unpack the second animation we have 60 frames played in one second because of the higher frame rate to our eyes this animation looks significantly more smooth now the main point here is that when generating animations or simulations we have to find some way to create the frames in this particular example that's done through interpolation which is something we'll touch on later but in more complex simulations what we are going to focus on is figuring out how to generate each frame from the initial assumptions of our system thinking about animation from this frame by frame perspective makes our life significantly easier so let's start simple here we have a single particle bouncing along the edges of a box there are three different ideas at play here the first involves particle dynamics at every frame a particle will have a position velocity and acceleration to keep things simple we can enforce the constraint that in all simulations the acceleration will be constant in most of our simulations later on in fact we'll keep this acceleration at zero but it's worth understanding how to incorporate the acceleration into the dynamics of our simulation now what's nice about the frame by frame perspective that we are taking here is that we know the time between each frame of the animation for example if our animation is generated at 60 frames per second the time between frames is 1 over 60 seconds a particle will have some initial position velocity and acceleration given that our acceleration is constant we get the following updates to our dynamics frame by frame here's a quick example of how this plays out in a few frames to make sure this is clear when you put all the frames together we have the following now when the particle reaches the edge of this box that kicks off the second major idea at play collision detection this actually turns out to be not too difficult of a problem let's solve it for the left edge at a particular frame collision detection between the particle and left edge just requires a comparison between a point and a line in this case the point is the leftmost point of the circle if the x-coordinate of our point is less than or equal to the x-coordinate of the points on the left edge we have a collision the logic for all other edges is the same basic principle with slightly different conditions to show an example in our animation this is the frame we actually detect a collision after detecting a collision the third and final idea involves resolving collisions resolving a collision requires updating the dynamics of our colliding objects in a sensible manner based on the assumptions of our overall system collision response can get quite complicated in terms of the math and physics involved so to make things simple we will make an assumption that all collisions between the particle and the wall are totally elastic collisions so no kinetic energy is lost and we will treat the walls as having infinite mass in the case of a collision with the left or the right edges of the box all this means is the sign of the horizontal component of our velocity is flipped after a collision has been detected for the top and bottom edges we flip the y component of our velocity after detecting a collision here are a few more frames to show you what a collision with the bottom edge looks like notice that the updates to our dynamics to velocity and position happen regardless of a collision let's put this all together and see what an implementation of this logic looks like let's assume we have a particle object that contains information about dynamics we'll also have a box object that represents the enclosed space in most animation or game engine frameworks there's a nice paradigm for updating information frame by frame how it's usually defined is by an update function where we are given the time between frames and all we have to do is define how our object's properties change over time the engine then takes care of calling this function from frame to frame given this fact our update function is actually not too hard to define we define how the dynamics change from frame to frame and then we define another function to specifically handle collision detection handling collision detection is just a matter of converting the logic we have already defined into code here's what that looks like so what we just implemented is one example of discrete collision detection before we add complexity it's worth taking some time to address some of the limitations of this framework some of you may be thinking what happens if between one frame to another the particle completely passes through an edge this can happen especially if the particle is moving quite fast this issue is so common that it's actually given a name tunneling let me show you an example of tunneling yeah it can be pretty ugly there are two easy solutions to tunneling and one that is substantially more complex the first easy solution involves making sure particles don't move too fast discrete collision detection does have some randomness involved when particles move slowly we are more likely to detect collisions and resolve them at an appropriate time another solution is a variation of the same idea instead of slowing down particles just take more frames both of these solutions work but obviously they are not ideal and definitely do not work in all cases the third solution requires taking a bit of a different approach by the nature of discrete collision detection tunneling will always be a possible issue there's another paradigm in collision detection called continuous collision detection that directly attempts to solve this problem continuous collision detection is a great showcase for quite a few concepts in computer graphics so let me give you an overview of how the basic ideas play out the core problem is that we end up missing a collision because it occurs at some point between the frames so let's label the positions of the particle in these two frames as follows frames are played at constant time steps so let's define the actual coordinates of the starting and ending point of a particle in terms of a time let the start be at time 0 and the end of time 1. what i'm basically doing here is i'm parameterizing the x and y coordinates of our particle over time this is particularly useful since it allows us to easily define the points of a line given the starting and ending point this process is called linear interpolation and is actually used all over the place in graphics an easy way to think about linear interpolation is it's just the weighted average of the starting and ending points for example if t is equal to one-half you get the midpoint if t is equal to one-fourth you get a point one quarter of the way along the line from the starting point the goal of continuous collision detection is to fill out the missing information between frames what we are really interested in is the exact point of collision which we can label as follows [Music] now the entire idea behind continuous collision detection is to solve for this point by using the constraints laid out by a collision detection system in the case of particle collision with a horizontal edge one constraint is as follows we know the exact point of collision will occur when the center of the particle is distance r above the edge of the box where r is the radius of our particle this gives us the following relation we can then combine this constraint with the linear interpolation constraint and get a system of linear equations which we can then solve for our unknown parameter tc or the time of collision in our particular example this happens to be about 0.23 so now that we have the time of collision the second part of continuous collision detection is to figure out the change in trajectory of our object after the collision in our example this can be done with some simple geometry now that we have the point of collision the rest of the trajectory is just going to be the original trajectory flipped over a horizontal line passing through our point of collision the reason this works is because we know after a collision the y component of our velocity will be flipped which geometrically is equivalent to this reflection we now have a corrected trajectory of our position which we can then pass into our animation engine whenever necessary and this is a nice solution to tunneling in practice however continuous collision detection can become fairly complex a lot of times it's not as simple as solving a linear equation you're often dealing with distances multiple dimensions and more complicated geometries which requires more sophisticated root finding algorithms that can quickly become much more computationally intensive if you aren't careful there's entire chapters of books dedicated to this so there's a lot more i could talk about but the goal here is to just give you an overview of the basic principles all right switching back to the world of discrete collision detection let's move to a slightly more complex simulation which involves two particles in an enclosed space everything from before still applies but now we have one more feature particle particle collision detection and responses i have some good news and sort of bad news here first the good news collision detection between two circles is super easy all we have to do is check if the distance between the center of the two circles is less than or equal to the sum of the two radii now the bad news collision response is significantly trickier we need to first define particle velocities particle masses and then velocities after a collision to solve collision response for two particles we need to use conservation of momentum and conservation of kinetic energy i tried working through the equations on my own for two dimensions and long story short it wasn't fun so i'm just going to show you the final expressions and i'll leave a link in the description to someone who is way better deriving and explaining solutions to 2d collisions than i am i will freely admit that i'm a little bit rusty on my physics and my physics teachers would definitely be disappointed but i'll live with the shame so this simulation on the side that i've been casually ignoring is basically created with an implementation of the particle dynamics collision detection and collision response logic we just went through it actually works quite well as long as the particles aren't moving ridiculously fast now let's add the final and trickiest layer of complexity scaling up these simulations the goal here is to create efficient methods of handling hundreds of particles to show the concepts more clearly though i'm going to demonstrate the ideas in the context of just six particles we have a framework to detect and provide responses to collisions between two particles how do we extend it to multiple particles well the first idea is to just check collisions between every pair of particles this works but it gets expensive really fast for example on just 100 particles we would have to perform roughly 5 000 collision detection tests this doesn't sound too bad until you realize you have to perform these tests for every single frame in your simulation so if you wanted to run a simulation at 60 frames per second for a minute that would be a total of 3 600 frames leading to roughly 18 million collision tests i had the awful idea of trying this on my macbook just for curiosity and the sounds it made throughout the 1 hour and 40 minutes of rendering were quite scary don't try this at home and honestly you don't even really need these data points to tell you that this naive method of handling collisions among a large number of particles is just an awful algorithm there are so many pairs of particles in the simulation that we would just never even consider testing right let's go over a few clever and common optimizations from a computer graphics perspective a common framework for thinking about solving collision detection problems at a larger scale is in three distinct phases broad phase narrow phase and then actually solving a collision broad phase is all about detecting which objects could possibly be colliding while narrow phase is all about taking the set of possible collisions and finding out what actually collides and then solving the collisions is all about figuring out the appropriate responses of the objects that did indeed collide for this particular problem we've actually already covered the narrow phase and collision response phase the optimizations that follow are all about the broad phase let's break down these optimizations on a specific frame these particles all lie on a coordinate plane and one idea of an optimization could be the following if we take all our particles and project the particles on one axis this could give us some insight on which particles could be colliding once we take this projection perspective we can now simplify particles to intervals and the idea here is that if there's no intersection between intervals of two particles there's no way the actual particles will collide when applied to this particular example instead of having to check all 15 pairs of particles we now narrow down a search to two possible collisions so let's break down how this algorithm which is formally called the sweep and prune algorithm is implemented in practice the first step involves taking all our particles and sorting it by a particular axis in our example we chose the x-axis now we can think of each particle as an interval on the x-axis so what we want to do is then maintain a list of active intervals initially the active interval is going to be the first particle in our sorted list the key idea that makes this algorithm work is that any time a particle intersects with the current active interval we have a possible collision for example the orange particles interval along the x-axis intersects with the pink particles interval so we report one possible collision what's also important here is now we update the active interval to include both the pink and orange particles another way to think about this is that any time there are multiple particles in an active interval we have to check collisions among all pairs of particles as long as we make sure the active intervals are updated appropriately this algorithm is guaranteed to report any particles that actually do collide within its list of possible collisions the rest of the algorithm proceeds as follows the next particle in our sorted list is the blue particle which doesn't actually intersect either of the particles in the active interval so we now update our active interval to include just the blue particle we then repeat this process on all other particles in our sorted list there are several further optimizations we can make to this approach such as performing this simultaneously over multiple axes or picking the axis with the larger variance in particle positions this can make a difference because there are certain bad inputs where if we pick one axis we don't do much better than a naive scheme but turns out that in a lot of practical collision detection systems even the simplest version of the sweep and prune approach results in drastic improvements for example when i implemented this particular algorithm to render 100 particles at 60 frames per second for a minute it only took 3 minutes to render yeah i'm serious the time reduced from 1 hour and 40 minutes to 3 minutes that's how much of a difference these optimizations make so sweep and prune is pretty good for these type of simulations but there are other options the next big optimization idea involves space partitioning i want to spend some time on space partitioning since it shows up in all sorts of applications not only in graphics but also in other fields such as machine learning the simplest space partitioning approach involves uniform grids the idea is exactly what you would expect we split our space into a grid of some length and width now what we do is we go through all particles in our simulation and assign them to a cell in our grid if a particle lies in the intersection of multiple grid cells we simply keep track of the particle in all the relevant cells once we have every particle assigned our set of collisions will only include all pairs of particles within a cell which will in practice give you much better performance one aspect here that's important is the number of rows and columns we choose as part of our uniform grid strategy as with most ideas there is a trade-off if we have fewer cells less memory will be used but more collision checks may be required if we use a larger number of cells we're more likely to have fewer possible collisions but we will need more memory to store our grid another aspect that's a little inefficient about the uniform grid space partitioning approach especially when there are a lot of cells is that there could be cases where a large number of the cells are empty and therefore a waste of memory the next type of space partitioning approach tries to utilize the structure of the particles in the scene to prevent this issue let me introduce you to kd trees instead of uniformly splitting the space let's pick an axis and split the space by the median so for example here we chose the y axis and if we sort objects along the y-axis the median passes through the pink and the red particles we now have split the space into two subspaces and the key idea behind kd trees is we're going to repeat the process on each of these subspaces on the opposite axis so since we initially picked the y axis we're going to split out two subspaces along the median of the x-axis on the bottom subspace we have four objects if we sort them along the x-axis and find the median we get the following split we repeat the process on the top subspace now notice what we have done with just three splits we've balanced out the objects in each space in other words every space is being used to store objects which may be advantageous if we don't want to waste any memory this type of split also naturally gives us a tree structure and trees tend to be more efficient to traverse than grid-like data structures now we could stop here but usually with kd trees we generally have some termination condition determination conditions can be a variety of things some simple such as the limit on the number of splits or the number of particles in a partition of the space some more advanced techniques also exist where we basically continue splitting until we can no longer partition the space in a way that is advantageous here let me show you an example of what this means we can add one more split to the upper left space since that will give the two new spaces only one particle spaces with one particle are really nice since we don't have to worry about any collisions in those partitions we can do the same split on the upper right and lower left spaces giving us the following tree the bottom right space however is a special case since any potential split along the median of the two particles will not be beneficial since both spaces will still have two particles so in this case it makes sense for this space to no longer be divided making this our final tree structure when figuring out which particles could potentially collide all we have to do is traverse the tree and get the leaves of the tree for any leaves that have more than one particle we include all pairs into the set of possible collusions in this case there's only one possible collision which happens to be the only collision in our example the final scheme i want to show you takes a slightly different approach sometimes it's really annoying to have objects in multiple spaces this is especially true if the object in our collision detection schemes are complex geometries where performing collision checks is a more expensive task in this case space partitioning schemes can actually be quite awful so another idea is to use an object partitioning approach where the key idea requires that we never allow objects to overlap spaces the most common object partitioning method that shows up in a ton of computer graphics applications is bounding volume hierarchies these data structures are so important in graphics that there are entire chapters of books dedicated to them but i'll give you some insight into the basic ideas of how these work there are many methods for constructing bounding volume hierarchies but one of the most common ways to do it is as follows we first pick an axis and then pick the median object along the axis this is a little bit different from the kd tree because we are now going to use this median object to split our initial set of objects into two distinct subsets here let me show you what i mean if we use the x-axis there's no single median object we end up having to choose between the following two objects so what we do is we assign everything to the left of the blue particle to a set and everything to the right of the red particle to another distinct set we now define a tight bounding box to encompass the objects of both these sets now what have we done here we have now split our space into two subspaces but the key advantage to this scheme is no object will overlap two spaces but of course this is at the expense that spaces could potentially overlap so as with everything there's a trade-off to finish constructing a bounding volume hierarchy for this scene we are basically going to repeat this process until a termination condition which can once again be something simple like the number of bounding volumes we create or a limit on the number of objects in a volume for this scheme let's continue until we get to one object in each bounding box starting with bounding box a let's pick the y-axis and split among the median of the three enclosed objects the median in this case is a singular object which we can assign arbitrarily to be part of the bottom left bounding box c leaving the orange particle to be the only particle in the upper left bounding box we can repeat a similar process for bounding box b [Music] continuing on to bounding box c we can further split it into singular sets of particles and we can do the exact same thing with bounding volume d now notice that the bounding volumes that contain the red and yellow particles intersect and that's the key idea behind finding possible collisions if bounding volumes don't intersect there is no way objects in them will ever collide which eliminates a significant number of collision checks the algorithm for finding possible collisions is a little bit more involved in spatial partitions but the core idea involves traversing the tree and checking for intersections between the bounding volumes that encompass the nodes i'll add a few resources in the description that go through this algorithm in more detail for those of you that are interested like i said there are entire chapters of books that focus on this topic so this is really meant to be an intro to the big ideas so let's do a quick recap we covered a lot of diverse topics in this video all motivated by a simulation of particles in an enclosed space through that simple idea we understood a framework for thinking about animation which led to some of the key ideas in discrete collision detection and continuous collision detection but the biggest challenge was figuring out how to scale the simulations in an efficient manner which led us to some really important ideas involving space partitioning and object partitioning these ideas show up all over computer graphics from geometry processing to ray tracing and we'll definitely see them again in future videos but until then thanks for watching and i'll see you in the next one

Channel: Reducible

Views: 139,331

Keywords: Collision_Detection, Collision-Simulation

Id: eED4bSkYCB8

Length: 28min 5sec (1685 seconds)

Published: Tue Jan 19 2021