Week 2 Lecture 2 - Lloyd's Algorithm and Collision Detection
0We started off by talking about the Lloyd's Relaxation algorithm for the Voroni tessellation. Basically, for each city, you will average together all the rows to get an average row, and average all the columns to get an average column. This is the centerpoint of the country, which is called the centroid, or center of mass. Centroids are used in a lot of different ways - today we're just going to move the city to the centroid and re-run the Voroni tesselation. This has the effect of smoothing out the really sharp and irregular regions at the cost of making the map a little more boring and round, especially if you do it too many times.
We then started talking about the computer science behind video games, focusing on collision detection, tracing, and pointcontents. Today we mostly talked about collision detection, including how to figure out if two axis-aligned bounding boxes (AABBs) touch, if two circles touch, if two triangles touch, if two convex hulls touch, if a circle contains a point, if a convex hull contains a point, if a cylinder contains a point, and how high up on a cylinder you hit to determine if it's a headshot or leg shot.
We also talked about how simple methods are easier to code and faster to run, so a lot of video games just bite the bullet and use really simple hit detection systems with either AABBs, cylinders, capsules, or spheres. UE4 does handle finer-grained collision detection, but it comes at a cost of more CPU time.