This week I worked on expanding my vector-based simulation from last week. I set out to make the balls collide with each other and with other arbitrary shapes.
When I began the project, I intended to check collisions with other balls as I checked collisions with the boundaries of the plane last week, by checking if any balls were overlapping, fixing their position, and updating their velocity. As I was implementing this, however, I was deeply unsatisfied. If the balls were moving fast enough, they would simply pass through each other and handling complex situations in which multiple objects collide would be difficult.
My solution was to handle the ball collisions as if the were moving continuously instead of discretely. To do this, I had each ball look for collisions along its velocity line before moving. The ball would find the closest collision if it was going to collide in that movement step, the ball would instead move to exactly the point of collision and then adjust its (and the colliding ball's) velocity. This process would then repeat until the ball had "used its velocity" and completed the time step.
To handle the actual collisions and update the balls velocities, I followed the steps outlined here and added several methods to my vector class from last week.
Then after several painful days of debugging... the balls bounced!
Some balls are colored red so they are easier to follow
Here are four hundred balls. You can see the algorithm isn't quite perfect and balls occasionally pass through one another.
Next, I wanted to make arbitrary shapes for the balls to bounce off of. Chris Scammell got me interested in an algorithm to find the convex hull of a set of points. The convex hull of a shape or set of points is the smallest shape containing it where any point between two others in the shape is also in the shape. I learned the algorithm is called a Graham scan, and I set to work implementing it.
The algorithm first finds the point with the least y coordinate (using x coordinates to break ties) and making this the starting point. It then sorts every other point on the list by their angle with respect to the starting point. Points are added in order to the set of points which will define the convex hull. Each time a point is added, its orientation with respect to the last two points is calculated. If the point is a clockwise turn from the last instead of a counterclockwise turn, the last point is not on the convex hull and must be removed. This process repeats, slowly refining the convex hull until it has reached the last point.
My obstacle class which implemented this algorithm used the convex hull of the given points to define the lines that constitute the obstacle. Collision checking with this set of lines proved to be quite difficult. I decided to use discrete collision detection to handle the collisions between the balls and the obstacles.
To start, I had to figure out when balls were inside an obstacle. Each was given a bounding sphere which is the smallest circle centered at the average point in the shape which completely contains the entire shape. This sphere allowed points to be quickly disqualified before beginning the more resource intensive checks. To further check if a ball was inside the shape, each line which constituted it was used to divide the plane into two parts. For a ball to be inside the shape, it needed to be on the interior side of each division or close enough to the division line so it overlapped.
Once a ball was determined to be inside an obstacle, I had to figure out which side it entered the obstacle to properly fix its position and update its velocity. Using the velocity of the ball and lots of geometry, I would use the line the ball entered the shape to fix its position by reflecting it outside the shape and then reflect its velocity perpendicular to the line.
Here it is in action.
Unfortunately, as you can see, my algorithms have some lingering bugs I didn't have time to sort out.
Here is another example with different shapes. You can see the bugs more apparently as balls teleport through one side of a shape.
After this, I also quickly ported over some of the different ball types I made last week and updated them to work in this new system.
This is a gravity ball repelling the others.
And these balls have constant acceleration tangent to their velocity and move in circles.
Everything above is off book and is somewhat of an extension itself. Here is some of the math I did to get the above (not) working:
- Distance between points
- Projecting points onto infinite lines and calculating the distance to the projection
- Distance between infinite lines
- Distance between line segments and points, and other line segments
- Checks for whether or not two line segments are intersecting
- Intersection points between infinite lines or segments
- Checks for whether a point lies within a line segments bounding square
- Orientation of points (using cross product)
- Orientation of points with respect to a line
- Trigonometry :-(
- Calculating unit, tangent, and normal vectors
- Rotating vectors
I also implemented a SkipList (no indexing) and used it heavily for this project, though I used it only as an iterator and had no useful application for it.
This was by far my most ambitious project and I think I have the least to show for it. My code has several major bugs which I don't have time to fix and because I tried to implement such a wide breadth of features, my code is somewhat haphazard. Still, this was an incredible learning experience. I did a lot of research into the (many) problems I was having and I feel like I got a pretty decent crash course on collision detection theory and practice. I've definitely learned more in this project than in any of the others thus far.
I wish I had more time to work out the bugs and finish a more unified collision system. Now that I more fully understand the task, I think I'm better equipped to organize the code and prevent some of the hard to find bugs from popping up again.
Thanks to: Bruce and Dale for the conversations about the project, Chris Scammell for setting me onto convex hulls, Nick Cameron for trying to bug test for me, and the internet.
Here are some links I found particularly helpful and that I would encourage reading if you have a spare several days. The first is highly recommended.