Index

1. Collision detection: bounding boxes, bounding spheres

• accurate collision detection can be expensive
• this is particularly true in PGE which will calculate the time of next collision
• sometimes an accurate time of next collision is not necessary
• for example if the objects are sufficiently far apart and are travelling slowly
• an inexpensive way to determine whether objects are not going to collide is to use the bounded shape technique

4. Bounding boxes, bounding spheres

• these approaches can be very useful as they allow us to treat polygons as circles
• and circles as polygons
• for the purpose of collision detection
• we can also combine shapes into an aggregate circle or rectangle
• finally creating bounding circles will help detect whether a rotating object will not collide (within a time period)
• should provide a significant optimisation for rotating objects which are spinning but not moving
• a bounding circle is a single object, compared to a polygon - which must have at least 3 vertices

5. Implementing bounding circle in PGE

• recall that polygons are represented by an array of vertices
• each vertice has a polor coordinate from the center of gravity
• we need to find the longest point away from the centre of gravity and this will become our radius
• the polar coordinates are defined by a radius and angle

• Sandpit/git-pge/c/polar.c

```struct polar_Polar_r {
double r;
double w;
};```

• we can ignore the angle and choose the largest radius
• at this point we have a bounded circle which can be used to test against other circles
• we can see the collision detection commences in the function findCollision

• \$HOME/Sandpit/pge/c/twoDsim.c

```static void findCollision (Object iptr, Object jptr,
eventDesc *edesc, double *tc)
{
if (! (iptr->fixed && jptr->fixed))
{
/* avoid gcc warning by using compound statement even
if not strictly necessary.  */
if ((iptr->object == circleOb) && (jptr->object == circleOb))
findCollisionCircles (iptr, jptr, edesc, tc);
else if ((iptr->object == circleOb) && (jptr->object == polygonOb))
findCollisionCirclePolygon (iptr, jptr, edesc, tc);
else if ((iptr->object == polygonOb) && (jptr->object == circleOb))
findCollisionCirclePolygon (jptr, iptr, edesc, tc);
else if ((iptr->object == polygonOb) && (jptr->object == polygonOb))
findCollisionPolygonPolygon (jptr, iptr, edesc, tc);
}
}```

• we can see the engine categorise the various objects under collision
• potentially we can optimise these calls one at a time

6. Optimising earlierCircleCollision

• notice that the parameters to earlierCircleCollision define both circles, position, velocity, acceleration and radius
• is the radius for circle, i
• is the x position for circle, i
• is the y position for circle, i
• is the velocity for circle, i, along the x axis
• is the velocity for circle, i, along the y axis
• is the acceleration for circle, i, along the x axis
• is the acceleration for circle, i, along the y axis
• is the radius for circle, j
• is the x position for circle, j
• is the y position for circle, j
• is the velocity for circle, j, along the x axis
• is the velocity for circle, j, along the y axis
• is the acceleration for circle, j, along the x axis
• is the acceleration for circle, j, along the y axis

7. Implementing a short circuit test to determine whether circles might collidein near future

• we know that they touch when the circles are units apart
• we know the current distance apart is
• so when

• can simply this to

• the circles have a gap between them
• if the total relative distance travelled between the circles over the next frame is less than this gap we know they cannot collide in the next frame
• this might be less expensive than completing the function earlierCircleCollision
• recall that the distance an object travels over time if we know its acceleration, velocity is
• we can separate out the x and y velocity and acceleration
• and use Pythagoras to determine the length of vector distance travelled
• let
• if the value then there will be no collision in the next frame by these objects

8. Tutorial

• implement a short circuit function for two moving circles in earlierCircleCollision
• observe the frames per second in your new optimised PGE
• does it make a noticable difference?
• a careful implementation will allow this short circuit function to be called from within polygon/polygon and polygon/circle tests (using bounded circles)

Index

1. Collision detection: bounding boxes, bounding spheres
2. Bounding rectangle (boxes)
3. Bounding circle
4. Bounding boxes, bounding spheres
5. Implementing bounding circle in PGE
6. Optimising earlierCircleCollision
7. Implementing a short circuit test to determine whether circles might collidein near future
8. Tutorial
Index

This document was produced using groff-1.22.