Collision Detection in Video Games

Collision Detection in Video Games

Benjamin Rodrigue
Copyright: © 2012 |Pages: 32
DOI: 10.4018/978-1-4666-1634-9.ch010
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

This chapter will describe several methods of detecting collision events within a 3D environment. It will also discuss some of the bounding volumes, and their intersection tests that can be used to contain the graphical representation of objects in a video game. The first part of the chapter will cover the use of Axially Aligned Bounding Boxes (AABBs) and Radial Collision Volumes. The use of hierarchies with bounding volumes will be discussed. The next section of the chapter will focus on Object Oriented Bounding Boxes (OOBs). The third section is concerned with the Gilbert-Johnson-Keerthi distance algorithm (GJK). The last three sections will focus on ways of optimizing the collision detection process by culling unnecessary intersection tests through the use of type lists, sorted lists and spatial partitioning.
Chapter Preview
Top

Background

This chapter is organized into three parts. The first section is a math primer on vectors and matrices. The math primer is not meant to be comprehensive, but it will present a couple of the rules for matrices and vectors. The second topic will focus on collision detection volumes that improve detection performance over pixel by pixel overlapping tests. The collision volumes are Axially Aligned Bounding Boxes (AABB), Radial Volumes, Binary Volume Hierarchies (BVH), Object Oriented Boxes (OOB) and the Gilbert-Johnson-Keerthi distance algorithm (GJK). These bounding volumes are arranged in order of increasing complexity and precision.

The last topic will describe ways to reduce the number of necessary collision tests. This part is split up into three sections. These sections describe the ways of reducing the number of detection tests based on object type and object location. The first part of this section describes how to use dynamic and static object lists. The next section is concerned with the sort and sweep algorithm. The last section describes spatial partitioning using Quadtrees and Octrees.

Complete Chapter List

Search this Book:
Reset