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 dt seconds apart. The position and velocity of the ball at time t=0 are p0 and v0 respectively. The ball should not intersect any triangles in this position though it may touch one or more. The only forces acting on the ball are gravity and those due to collisions. Our objective is to compute the position and velocity of the ball dt seconds later. An overview of the algorithm follows.

  1. Approximate the average velocity of the ball across the time step assuming no collisions occur.
  2. Compute the ball's path assuming constant velocity and no collisions over the time step.
  3. Determine if and when the ball first collides with a triangle while moving along the path.
  4. If a collision occurs before the end of the path:
    1. Move the ball to the point of collision.
    2. Compute the change in velocity due to the collision.
    3. Compute the remaining time in the time step.
    4. Return to step 1 and simulate the movement of the ball over the remaining time in the time step based on the new position and velocity.
  5. Move the ball to the end of the path.
The simulation then repeats for the next time step. The remainder of this document fills in the details.

  1. Velocity Computation
    In an absence of a collision and other forces, the velocity of the ball at the end of the time step is
    v1= v0 + g dt
    where v0 is the initial velocity of the ball and g is the acceleration due to gravity.

    We approximate the average velocity over the time step as
    vavg =(v1+ v0)/2.
  2. Path Computation
    We approximate the ball's movement by assuming that, in the absence of a collision, the ball moves with constant velocity vavg across the time step. Under these assumptions the ball will move from its current position, p0, to the point
    p1   =   p0 + vavg dt   =   p0 + v0 dt + 0.5g dt2
    during the time step.

  3. Collision Detection
    The collision detection algorithm takes as input the path endpoints p0 and p1, the ball's radius r, and a description of the triangles in the scene. The algorithm returns α in [0,1], which is the fraction of the path the ball can travel before colliding with a triangle. If no collision occurs the collision detection algorithm returns α=1. To clarify, the algorithm returns 0 if the ball is colliding with a triangle in its initial position, p0. The algorithm returns 1 if no collision occurs or if a collision occurs exactly when the ball reaches the end of its path, p1. The algorithm returns α in (0,1) if the first collision occurs αdt seconds into the time step.

    If a collision is detected during the time step, the collision detection algorithm also returns the surface normal at the point of collision.

    A description of the collision detection algorithm can be found here.

  4. Collision response (α < 1):
    If the collision detection algorithm returns α < 1, we do the following.
    1. Reset the ball's center to
      p'0 = p0 + vavg αdt.
      In this position the ball is touching but not intersecting any triangles.
    2. Reset the ball's velocity to
      v'0 = d[ vavg - 2(vavg • n) n ]
      where d in [0,1] is a damping factor and n is the surface normal at the point of collision. The geometric interpretation of this computation is shown in the figure below. The derivation of the velocity computation is given in separate notes.


    3. Reset the time step length to dt' = (1- α)dt.
    4. Sttart a new simulation with the ball's initial position set to p'0, its velocity set to v'0, and a time step length of dt'. (Note that dt' > 0.)

  5. Move to end of path (α=1):
    When the collision detection algorithm returns α=1, then either there is no collision in the current time step or it occurs exactly when the ball reaches the end of its path. In either case, we reset the ball's position to the end of the path and go on to simulate the next time step. (If the ball is colliding with a triangle in this position, the collision will be detected at the start of the next time step.)



    Last updated 2/26/04