Crashing into the New Year: Collision Detection

Начало книги

The last several years have moved at an incredible pace. It was a year with amazing advances in the visual quality of games. The predictions that 3D hardware would become a major force in the industry have come true.

Consumers can now buy cards for under $100 that deliver 3D graphics performance that would have cost thousands only a few years ago. This added processing power leaves game developers more and more time to dedicate to exploring other areas in computer simulation.

I'm continually amazed that learning a simple trick or technique can open the door to so many different effects and applications. In this article, I’m going to investigate the problem of collision detection. Collision detection is a huge issue in graphics simulation. In fact, it's an active area of research, so SIGGRAPH and professional journals are a great source of information.

Let me start off by looking at some common problems that can be important to a variety of game applications. These routines, though fairly simple, are very handy to have in your library. The first issue is how to determine whether a point is inside an arbitrary area. Detecting whether a point is inside a convex polygon can be determined very easily. Figure 1 shows a point inside a simple four-sided polygon. Our first step is to create perpendicular vectors for each of the polygon edges and a vector from the test point to the first vertex of each edge. The perpendicular of a 2D vector can be created by simply creating the vector, swap the X and Y components, and then negate the X. As you may recall from previous columns, the dot product of two vectors defines the cosine of the angle between those vectors.

Читать дальше →