Collision Detection in Three Dimensions
About
CollisionSim:
The goal of this project is to demonstrate real time collision detection in three dimensions. The simulator does this by allowing the user to set up a scene how they wish, adding an arbritrary number of objects determined and customized by the user. It then uses various ray tracing techniques and a simplified physics model to simulate collisions between objects in real time. To evaluate the system, numererical integration (Euler) is used. Ultimately, it was my goal to simulate collision detection between complex objects with a very realistic physics model, however I soon came to realize that I did not have time enough to do everything I had hoped. Also, after researching a bit on 3D collision detection methods, I found that most algorithms for complex shape collision detection rely on either axis-aligned bounding boxes (AABBs) or opposing-face algorithms, neither which would fit well into what I had planned for the preliminary steps of the program. However, although I had to scale back some of the originally anticipated features, the result is still an interesting and veratile simulation environment with great usability.
At the core of the simluation is the collision detection algorithm. What it must do is decide whether any objects within the scene will hit each other between and a given time step value, and if so at exactly when. It does this several ways, depending on the types of objects it is evaluating. The simplist example and the easiest to get working by far was a moving sphere and a plane. Since planes have to edges to speak of, I could simply solve for the time at which a ray representing the ball intersected the surface described by a point and a normal, throwing out any time values which were past the given time step or negative (meaning the collision already happened). This solution does have a couple special cases, however. I check the dot product of the ray velocity and the plane normal and make sure it isn't zero or positive, meaning the ray plane are parallel or diverging. This helps throw out many cases without having to compute them. There is one detail I have left out, however, which is the actual process of representing a moving sphere with a ray. In order to properly detect the collision, we must be checking for the point on the sphere which will intersect the plane first, not the center. In order to find that point, I simply scaled the plane normal by the -(ball radius). This point along with the velocity vector of the sphere are enough to represent it as a ray. The next case, an intersection between two moving spheres, is a little more difficult. For this case, I used the common trick of treating the second ball as stationary and the first as having a velocity vector equal the the balls' relative velocities. The first two cases I check for are the relative velocity dot the relative position being zero or greater than one, meaning either there is no change in their distance over time or they are diverging. If neither of those are true, then I check to see if a ray defined by the first ball's center and the relative velocity is within a distance of the sum of the radii of the center of the second sphere. If so, then I must determine if the collision happens after, before or during the given time step. To do this, I resort to a second numerical integration over the time step. I know mathmatical solutions to the problem exist, however I did not have enough time to expirement with implimenting them after I had this working... Thus, unfortunately, this is the routine which makes or breaks the performance of the simulator. Since most the simulations involve a high number of moving spheres, most the physics loop is spent here meaning the number of ealy cases I can throw out and the secondary integration step are critical to performance. I settled on a rather large step, which means that while performance is pretty good, collisions between spheres are not nearly as accurate as they could be. This can be observed by noticing the difference between a sphere sitting stationary on a plane, where it is always perfectly intersecting the surface, and a ball sitting on top of another ball, where it will hover and 'bounce' slightly because the detected collision time is only as accurate as the integration step. Another choice in this function turned out to be more important than it seemed at the time, throwing out collisions between spheres which may be intersecting yet are diverging means that two objects can occupy the same space. This is probably the function which went through the most changes during development, and I experimented with a few different ways of handling the sphere collision. I settled on this method because of a) the fact that the interface makes it really easy to create two objects occupying the same space, and otherwise I'd have to delete all user created objects which accidentally might intersect or handle the problem some other way and b) the interesting effects which this method allowed me to produce. For instance, the top two pictures were both taken of a scene in which a high number of spheres were originially placed at the center, with velocities generated by random spherical coordinates. As the simulation begins, the spheres begin expanding in a nice... well, spherical shape (that is, until they begin hitting things!)
This brings me to the last type of collision detection implimented by the simulator, which unfortunately does not work as nicely as the other two. This is the collision between a ball and a rectangular prism. Since this shape has edges past which the ball will not collide with it, I have to also check for the collision point being within the volume of the prism, after the regular sphere-plane intersection test. However, this solution is not totally complete as it does not provide any means to check for intersection between spheres and the edges of the prism. Since planes have no edges, I cannot get away with simply doing planar tests and bounds checking the results. There needs to be a secondary check, which finds the case where the sphere fails the first test yet still intersects an edge (think of a sphere rolling off the surface of a table- as it rolls off, the moment its center is not directly above the surface, it cannot be touching it - however it is touching the edge, until the distance from the center to the edge is greater than the radius.) I attempted to impliment this by representing the edge as a line segment, and checking the intersection of the all-to-familiar ray representing the moving sphere. However, my solution seems extremely slow and only worked in about half the cases (or very sporadically), so for performance reasons I decided to comment out the checks completely. Perhaps with just a bit more time the routine would have worked, but since it doesn't there are some times when the simulator very obviously misses a collision between a sphere and a prism, or even allows a sphere to pass completely through through a prism if it approaches the edge just right.
The other half to the simulation is the physics model. It is not too complicated, but it adapts well to many situations and is very customizable. The only force which acts upon the spheres is gravity, which is user defined. Thus the simulator has only to model the effect of this force on the balls over time, given the user-defined initial velocity vectors and collision detection algorithm. To do this I use Euler integration. I track the time since the last frame render, then integrate over that time period using the user-defined integration step, remembering to calculate the remaining fraction of time smaller than a time step. Over each of these integration steps, I adjust velocities for the forces acting upon them (gravity), then check to see if any collisions happen within the remaining time step. If so, I advance the simulation to the collision time, calculate the reflected velocities based on the objects (including their mass - see picture below) and the friction coefficient, then check for collisions again using the remainder of the time step after the collision until the time step has been reduced to zero. If there are no collisions, I simply advance each object by the amount of time in the time step, and repeat the process with another step until I have caught up with the frame render time. Besides the integration step, the user can customize another parameter which affects this process, the time skew factor. What this variable does is stretch or shrink the measured time value, in order to speed up or slow down the simulation. Since it is independent of the integration step, the user can use the time skew to adjust the simulation speed without affecting accuracy. Meaning, the frame rate can be improved by evaluating less and slowing things down (decreasing time skew.) With a minimal time skew value and the largest integration step, over 400 spheres can be simulated at an interactive framerate on a decent machine. At the other end of the scale, the user can specify parameters accurate enough to realisticly simulate effects such as a stack of spheres toppling over (see images below and the video clip at the bottom of the page.) Since creating a specifying the parameters for 100s of spheres in a scene is extremely tedious, there are various preset scenes which the user may load to watch or play with and alter - which brings me to the user interface guide.
User Interface:
Using the simulator is pretty straightforward, but there are a couple things you need to know off the bat or it may seem a bit confusing. First off, the pause/break key will start/stop the simulation. Note that you have to have the simulation window active (not object settings or simulation parameters windows) for this to work (FLTK's keyboard event model seems a little convoluted to me.) Once you know this, you can easily load preset scenes through the preset menu and load them (by clicking the load button, if that wasn't obvious) to watch.
Now might be a good time to introduce the camera controls. To rotate the camera, click somewhere in the scene (not in empty space or on an object) and drag with the left mouse button. This will manipulate the quaternion-based trackball. Currently the trackball suffers from gimbal lock when the user has rotated such that the camera is looking straight down the y axis from above with no rotation about the y axis, which, ironically, was not a problem of the trackball before I converted the class to a quaternion vs. Euler angle model. To translate the scene in the xy window plane, click and drag with the right mouse button the same as for rotation. Dragging with the middle mouse button will controll the zoom (z translation.)
Now that you can simulate preset scenes and alter the camera, you may want to be able to manipulate scenes yourself! To insert a new ball into a scene, click the new ball button (the one with a ball and a red plus sign, again if that wasn't completely obvious.) If no ball is currently selected, a ball with default parameters is placed at the center of the scene. If a ball is currently selected, an exactly copy of it is placed where the selected ball is (you won't see anything happen.) You can click on the selected ball to seperate it from the identical newly created ball and do what you want with it. To manipulate a ball, select it by clicking it with any mouse button. Once selected, you can drag with the left button to translate it in the xy window plane (the mouse coordinates are unprojected into world space coordinates so that this translation vector always acts as the user expects it), the middle button to translate it along the z axis (again, unprojected), or drag with the right button to increase the radius (and mass) of the ball. Manipulating boxes (recangular prisms) within the scene is pretty similar. The only difference is that you must use the object settings window to change box size, the mouse is only for translation. The object settings window can be accessed by highlighting an object and clicking the object settings button. If the object is deselected, the proper settings window is brought up for the newly selected object, or it is close if nothing is selected. Here you can see the actual values for the object parameters, and adjust them manually if you like. If you wish to use the mouse and settings window at the same time, that's ok, they stay current with each other. Note that you have to click the 'apply' button to actually adjust the settings, if you close the window or manipulate the object with the mouse your typed in values will disappear. If you decide you're tired of an object you can get rid of it by clicking the delete (X) button.
Besides manipulating the objects within a scene, you can alter the parameters for the physics simulation itself. To do so, click the sim settings button to bring up the Simulation Settings window. Here you can change the time skew, integration step, friction coefficient (note that when it is set to one certain optimizations are implimented, so altering this value will affect performance), gravity vector and specify whether to draw the velocity vectors of objects while simulating (they are always drawn while paused.)
That about wraps up my introduction to the user interface, I'm pretty sure I covered everything. Remember you can resize the window, and quit either through the file menu or by closing the window.
Known Problems/Bugs:
* Trackball rotation suffers from gimbal lock in rare cases.
* Focus may still not be properly returned to simulation window with certain buttons (requires user to manually click on window)
* Simulation of friction is rather fast and dirty, it can cause problems in situations where one ball on top of another ball should roll off but doesn't, or does so too slowly because each frame the velocities are being scaled down by the same friction coefficient regardless of the relative speed of the balls.
* Due to the 100% detection nature of the collision detection algorithm (it never throws out a collision it can find), extremely complex scenes have the possibility of generating the occasional exception due to overflow. (This may have been corrected, it is difficult to say due to the elusive nature of the problem.)
* Edge collisions were not sufficiently implimented and thus are removed. In general, it is not very noticable, but in certain cases this omission is very obvious.
Downloads:
Windows Installer
Spherical Explosion - requires XViD MPEG-4 codec
Toppling Stack - requires XViD MPEG-4 codec
Spherical Explosion - (no XViD)
Toppling Stack - (no XViD)
The goal of this project is to demonstrate real time collision detection in three dimensions. The simulator does this by allowing the user to set up a scene how they wish, adding an arbritrary number of objects determined and customized by the user. It then uses various ray tracing techniques and a simplified physics model to simulate collisions between objects in real time. To evaluate the system, numererical integration (Euler) is used. Ultimately, it was my goal to simulate collision detection between complex objects with a very realistic physics model, however I soon came to realize that I did not have time enough to do everything I had hoped. Also, after researching a bit on 3D collision detection methods, I found that most algorithms for complex shape collision detection rely on either axis-aligned bounding boxes (AABBs) or opposing-face algorithms, neither which would fit well into what I had planned for the preliminary steps of the program. However, although I had to scale back some of the originally anticipated features, the result is still an interesting and veratile simulation environment with great usability.
At the core of the simluation is the collision detection algorithm. What it must do is decide whether any objects within the scene will hit each other between and a given time step value, and if so at exactly when. It does this several ways, depending on the types of objects it is evaluating. The simplist example and the easiest to get working by far was a moving sphere and a plane. Since planes have to edges to speak of, I could simply solve for the time at which a ray representing the ball intersected the surface described by a point and a normal, throwing out any time values which were past the given time step or negative (meaning the collision already happened). This solution does have a couple special cases, however. I check the dot product of the ray velocity and the plane normal and make sure it isn't zero or positive, meaning the ray plane are parallel or diverging. This helps throw out many cases without having to compute them. There is one detail I have left out, however, which is the actual process of representing a moving sphere with a ray. In order to properly detect the collision, we must be checking for the point on the sphere which will intersect the plane first, not the center. In order to find that point, I simply scaled the plane normal by the -(ball radius). This point along with the velocity vector of the sphere are enough to represent it as a ray. The next case, an intersection between two moving spheres, is a little more difficult. For this case, I used the common trick of treating the second ball as stationary and the first as having a velocity vector equal the the balls' relative velocities. The first two cases I check for are the relative velocity dot the relative position being zero or greater than one, meaning either there is no change in their distance over time or they are diverging. If neither of those are true, then I check to see if a ray defined by the first ball's center and the relative velocity is within a distance of the sum of the radii of the center of the second sphere. If so, then I must determine if the collision happens after, before or during the given time step. To do this, I resort to a second numerical integration over the time step. I know mathmatical solutions to the problem exist, however I did not have enough time to expirement with implimenting them after I had this working... Thus, unfortunately, this is the routine which makes or breaks the performance of the simulator. Since most the simulations involve a high number of moving spheres, most the physics loop is spent here meaning the number of ealy cases I can throw out and the secondary integration step are critical to performance. I settled on a rather large step, which means that while performance is pretty good, collisions between spheres are not nearly as accurate as they could be. This can be observed by noticing the difference between a sphere sitting stationary on a plane, where it is always perfectly intersecting the surface, and a ball sitting on top of another ball, where it will hover and 'bounce' slightly because the detected collision time is only as accurate as the integration step. Another choice in this function turned out to be more important than it seemed at the time, throwing out collisions between spheres which may be intersecting yet are diverging means that two objects can occupy the same space. This is probably the function which went through the most changes during development, and I experimented with a few different ways of handling the sphere collision. I settled on this method because of a) the fact that the interface makes it really easy to create two objects occupying the same space, and otherwise I'd have to delete all user created objects which accidentally might intersect or handle the problem some other way and b) the interesting effects which this method allowed me to produce. For instance, the top two pictures were both taken of a scene in which a high number of spheres were originially placed at the center, with velocities generated by random spherical coordinates. As the simulation begins, the spheres begin expanding in a nice... well, spherical shape (that is, until they begin hitting things!)
This brings me to the last type of collision detection implimented by the simulator, which unfortunately does not work as nicely as the other two. This is the collision between a ball and a rectangular prism. Since this shape has edges past which the ball will not collide with it, I have to also check for the collision point being within the volume of the prism, after the regular sphere-plane intersection test. However, this solution is not totally complete as it does not provide any means to check for intersection between spheres and the edges of the prism. Since planes have no edges, I cannot get away with simply doing planar tests and bounds checking the results. There needs to be a secondary check, which finds the case where the sphere fails the first test yet still intersects an edge (think of a sphere rolling off the surface of a table- as it rolls off, the moment its center is not directly above the surface, it cannot be touching it - however it is touching the edge, until the distance from the center to the edge is greater than the radius.) I attempted to impliment this by representing the edge as a line segment, and checking the intersection of the all-to-familiar ray representing the moving sphere. However, my solution seems extremely slow and only worked in about half the cases (or very sporadically), so for performance reasons I decided to comment out the checks completely. Perhaps with just a bit more time the routine would have worked, but since it doesn't there are some times when the simulator very obviously misses a collision between a sphere and a prism, or even allows a sphere to pass completely through through a prism if it approaches the edge just right.
The other half to the simulation is the physics model. It is not too complicated, but it adapts well to many situations and is very customizable. The only force which acts upon the spheres is gravity, which is user defined. Thus the simulator has only to model the effect of this force on the balls over time, given the user-defined initial velocity vectors and collision detection algorithm. To do this I use Euler integration. I track the time since the last frame render, then integrate over that time period using the user-defined integration step, remembering to calculate the remaining fraction of time smaller than a time step. Over each of these integration steps, I adjust velocities for the forces acting upon them (gravity), then check to see if any collisions happen within the remaining time step. If so, I advance the simulation to the collision time, calculate the reflected velocities based on the objects (including their mass - see picture below) and the friction coefficient, then check for collisions again using the remainder of the time step after the collision until the time step has been reduced to zero. If there are no collisions, I simply advance each object by the amount of time in the time step, and repeat the process with another step until I have caught up with the frame render time. Besides the integration step, the user can customize another parameter which affects this process, the time skew factor. What this variable does is stretch or shrink the measured time value, in order to speed up or slow down the simulation. Since it is independent of the integration step, the user can use the time skew to adjust the simulation speed without affecting accuracy. Meaning, the frame rate can be improved by evaluating less and slowing things down (decreasing time skew.) With a minimal time skew value and the largest integration step, over 400 spheres can be simulated at an interactive framerate on a decent machine. At the other end of the scale, the user can specify parameters accurate enough to realisticly simulate effects such as a stack of spheres toppling over (see images below and the video clip at the bottom of the page.) Since creating a specifying the parameters for 100s of spheres in a scene is extremely tedious, there are various preset scenes which the user may load to watch or play with and alter - which brings me to the user interface guide.
User Interface:
Using the simulator is pretty straightforward, but there are a couple things you need to know off the bat or it may seem a bit confusing. First off, the pause/break key will start/stop the simulation. Note that you have to have the simulation window active (not object settings or simulation parameters windows) for this to work (FLTK's keyboard event model seems a little convoluted to me.) Once you know this, you can easily load preset scenes through the preset menu and load them (by clicking the load button, if that wasn't obvious) to watch.
Now might be a good time to introduce the camera controls. To rotate the camera, click somewhere in the scene (not in empty space or on an object) and drag with the left mouse button. This will manipulate the quaternion-based trackball. Currently the trackball suffers from gimbal lock when the user has rotated such that the camera is looking straight down the y axis from above with no rotation about the y axis, which, ironically, was not a problem of the trackball before I converted the class to a quaternion vs. Euler angle model. To translate the scene in the xy window plane, click and drag with the right mouse button the same as for rotation. Dragging with the middle mouse button will controll the zoom (z translation.)
Now that you can simulate preset scenes and alter the camera, you may want to be able to manipulate scenes yourself! To insert a new ball into a scene, click the new ball button (the one with a ball and a red plus sign, again if that wasn't completely obvious.) If no ball is currently selected, a ball with default parameters is placed at the center of the scene. If a ball is currently selected, an exactly copy of it is placed where the selected ball is (you won't see anything happen.) You can click on the selected ball to seperate it from the identical newly created ball and do what you want with it. To manipulate a ball, select it by clicking it with any mouse button. Once selected, you can drag with the left button to translate it in the xy window plane (the mouse coordinates are unprojected into world space coordinates so that this translation vector always acts as the user expects it), the middle button to translate it along the z axis (again, unprojected), or drag with the right button to increase the radius (and mass) of the ball. Manipulating boxes (recangular prisms) within the scene is pretty similar. The only difference is that you must use the object settings window to change box size, the mouse is only for translation. The object settings window can be accessed by highlighting an object and clicking the object settings button. If the object is deselected, the proper settings window is brought up for the newly selected object, or it is close if nothing is selected. Here you can see the actual values for the object parameters, and adjust them manually if you like. If you wish to use the mouse and settings window at the same time, that's ok, they stay current with each other. Note that you have to click the 'apply' button to actually adjust the settings, if you close the window or manipulate the object with the mouse your typed in values will disappear. If you decide you're tired of an object you can get rid of it by clicking the delete (X) button.
Besides manipulating the objects within a scene, you can alter the parameters for the physics simulation itself. To do so, click the sim settings button to bring up the Simulation Settings window. Here you can change the time skew, integration step, friction coefficient (note that when it is set to one certain optimizations are implimented, so altering this value will affect performance), gravity vector and specify whether to draw the velocity vectors of objects while simulating (they are always drawn while paused.)
That about wraps up my introduction to the user interface, I'm pretty sure I covered everything. Remember you can resize the window, and quit either through the file menu or by closing the window.
Known Problems/Bugs:
* Trackball rotation suffers from gimbal lock in rare cases.
* Focus may still not be properly returned to simulation window with certain buttons (requires user to manually click on window)
* Simulation of friction is rather fast and dirty, it can cause problems in situations where one ball on top of another ball should roll off but doesn't, or does so too slowly because each frame the velocities are being scaled down by the same friction coefficient regardless of the relative speed of the balls.
* Due to the 100% detection nature of the collision detection algorithm (it never throws out a collision it can find), extremely complex scenes have the possibility of generating the occasional exception due to overflow. (This may have been corrected, it is difficult to say due to the elusive nature of the problem.)
* Edge collisions were not sufficiently implimented and thus are removed. In general, it is not very noticable, but in certain cases this omission is very obvious.
Downloads:
Windows Installer
Spherical Explosion - requires XViD MPEG-4 codec
Toppling Stack - requires XViD MPEG-4 codec
Spherical Explosion - (no XViD)
Toppling Stack - (no XViD)