Week 2 Day 3 - Collision Detection, Traceline, BVHs
0Today we continued our lectures on the computer science behind 3D game engines. Collision detection and tracing are two of the most important elements to a video game, as that's how objects work with each other.
We went through the math of how to do the following:
1) See if two line segments intersect
2) See if a line intersects with a circle
3) See if two circles intersect
4) See if a line intersects with a box
5) See if a box intersects a box
6) See if a line hits a cylinder
7) See if a line hits a convex hull
8) See if a convex hull intersects another convex hull
Again, we talked about AABBs (Axis-Aligned Bounding Boxes) which are super easy and fast to work with, and circles (which are also fast and easy if you remember to optimize out the sqrts). The same principles (usually) apply in 2D and 3D, you just add a z or two to the equations.
We then talked about BVHs, which are behind the RTX technology (RTX is hardware BVH acceleration). A BVH is a "bounding volume hierarchy" which means you have an outer bounding box to do a quick and fast rejection if the object is far away, and then children bounding boxes for more fine grained and accurate collision detection. (My game engine actually used hierarchical spheres instead of bounding boxes, but the principle is the same.)
When you do ray tracing graphics on an RTX card, you shoot out a ray (or more) for each pixel on the screen and your RTX card accelerates the collision lookup, and tells you what the line hit. It starts off simple enough - see what you hit and then shoot a shadow ray to each light it might see to see if the spot is lit, and report back the color. But it gets complicated when you are dealing with reflections and refraction as these usually cause additional rays to be shot out. Hence the need for graphics acceleration on it. The quality of the final image is based in part on how many total rays you shoot out. A faster card can shoot faster rays.