CS121 Project 2

Physics Engine



In Project 2 you'll build a one-hole miniature golf game. The difficult aspect of this project is the physics engine, particularly the problem of collision detection and response. You'll start by building a physics engine to simulate a ball bouncing around a 3D room; the room may contain closed surfaces defined by triangle meshes. These notes describe a general strategy for building the simulation. In addition, you'll build an OpenGL interface to display the simulation. For help with that problem, you should refer to the OpenGL tutorial.

Overview
We can simulate the movement of the ball by computing its position at a series of discrete times dt0 seconds apart; dt0=1/30 is an appropriate setting. We assume that the position and velocity of the ball at time t=0 are p0 and v0 respectively. We require that the ball is not intersecting any triangles in this position though it may be touching one. Our objective is to compute the position and velocity of the ball dt0 seconds later. An overview of the algorithm follows.

  1. Approximate the average velocity of the ball the across the time step.
  2. Compute the ball's path assuming constant velocity over the time step.
  3. Determine if the ball collides with any triangles when moving along the path.
  4. Move the ball to the first point of collision or, if no collision occurs, to the end of the path.
  5. Compute the time the ball reaches the new position and the time remaining in the time step.
  6. If time remains in the time step, compute the change in velocity due to the collision then continue the simulation with the new position, velocity, and time step length.
The remainder of this document fills in the details.

1. Velocity Computation
We approximate the velocity of the ball across the time step as

v1= v0 + mg dt0
where v0 is the initial velocity of the ball, m is the ball's mass, and g is the acceleration due to gravity.

2. Path Computation
We approximate the ball's movement by assuming that, in the absence of a collision, the ball moves with constant velocity v1 across the time step. Under these assumptions the ball will move from its current position, p0, to the point

p1= p0 + dt0v0
during the time step.

3. Collision Detection
The collision detection algorithm takes as input the path endpoints p0 and p1. The algorithm returns α in [0,1], which is the fraction of the path the ball can travel before colliding with a triangle. Note that the algorithm returns 0 if the ball is colliding with (in other words touching) a triangle in its initial position. The algorithm returns 1 if no collision occurs or if a collision occurs exactly when the ball reaches the end of its path the algorithm returns 1. When α is between 0 and 1, a collision occurs α Note that the algorithm returns α=1 when there is no collision or when a collision occurs when the ball reaches the end of its path. In this case, we reset the ball's position to p'0 and go on to simulate the next time step. The algorithm returns 1 if If ball does colli, it returns the normal of the surface the ball c Details of the collison detection algorithm are given here.

If the collision detection algorithm returns α=1, then either there is no collision or it occurs exactly when the ball reaches the end of its path. In this case, we reset the ball's position to p'0 and go on to simulate the next time step. If the ball is touching a triangles in this position, the collision will be detected at the start of the next time step.

If the algorithm returns an α < 1, a collision occurs t0= α dt0 seconds into the time step. We reset the ball's center to

p1 = p0 + v0 t0.
In this position the ball is touching but not intersecting any triangles. We then compute the new velocity of the ball.

Collision Response
When a collision is detected, the collision detection algorithm also returns the normal, n, of the surface at the point of the collision. We reset the ball's velocity, as shown in Figure 1, to

v1 = 2d[ v1 - (v1 . n) n ]
where d is a damping factor. The derivation of the velocity computation is given in separate notes.

Repeat
We continue the simulation with the computation of the new path given that the ball is positioned at p1 with a velocity of v1 and the remaining time step length is dt1 = dt0-t0. (Note that dt1 > 0.)