IS50B Week 2 - Convex Hulls
1We continue our development of a toolset of code that we can use to do cool things in video games. Today we talked about the concept of a 2D convex hull, which is the tightest polygon that can wrap around all the points in a point cloud, such that all the points in the point cloud are to the right of each directed line segment. They are used in a lot of circumstances, but today we just focused on using it with a 2D Point for collision detection and point contents.
Collision detection is the notion of being able to tell if one thing is inside another thing, and so if a 2D Point is within the polygon or not. We also talked about wrapping the hull in a circle, since testing to see if something is inside a sphere is a quick and dirty way to eliminate two objects colliding if they are very far apart. You can use the bounding circle to see if it's near the hull, and then use the crossproduct on each of the directed line segments of the hull to see if the point is inside the hull.
I pulled up the source code to QuakeWorld, and showed how they used hulls for a similar purpose so that the code could tell if someone is in water, and if they are in water if they are waist-deep or completely underwater by testing the point contents at multiple places. QuakeWorld uses a Binary Space Partition system which is better than the one I talk about in class today, which is a bad system for a number of reasons, but has the advantage of being simple to teach.