Introduction

In a computer animation simulation where there are a number of objects in motion, there exists the possibility of interpenetration of objects. If realistic motion of the objects is desired, then any such interpenetrations need to be detected (collision detection) and responded to (collision response). For example, if a ball fell and hit a surface, the fact that it has collided with something needs to be recognized. If this event is ignored, then an unrealistic result would occur where the ball continues through the surface. Once the fact that the ball has hit the ground has been recognized, the ball then has to respond in a realistic manner by bouncing and moving in the expected way. Producing realistic motion of the ball after it hits the ground can involve complicated dynamics equations that take into account such factors as velocity, mass, elasticity, and friction.

Detection of collisions can be an expensive operation to carry out as a simulation may involve a large number of complex objects in motion. Typically, testing for a collision between a given pair of complex objects is an expensive task, so techniques are needed that reduce the number of full intersection tests carried out. The focus of this project is to produce an efficient collision detection module that can be used by animation simulators to help produce realistic animations.

To test the collision detection module, the growth of a vine like plant through an environment was simulated. The plant's growth is considered slow enough so that when collisions do occur with objects in the environment, complex dynamics equations aren't needed to correctly model its response. The plant growth algorithm is based upon the method presented by Arvo and Kirk [AK]. Further details can be found in Chapter which details the implementation of the plant growing module, and also the collision detection module.

Chapter contains results and statistics obtained from the program, chapter includes a discussion of the results, problems encountered, and possible enhancements to the program, while chapter holds the conclusions reached. The next chapter, , contains the results of the literature survey undertaken and deals with collision detection in animation simulations, and techniques that can be used to increase efficiency.