Deliverables

This week there is only one demo, but it will require some substantial “upgrades” to the scene and body abstractions. These “upgrades” would have been necessary to implement for your game anyway, though. The “upgrades” include:

• Collision Detection (but NOT resolution–that’s next week)
• A void * “info” body field
• Giving the scene information about which bodies are associated with force creators
• Deferred body removal (see below)

Physics Engine

As usual, we will need more features to implement the new demo. Most of them are described in the docmentation, but we repeat some important information in the spec below.

Collisions

This week, you will implement collision detection, i.e. checking if two polygons intersect. For simplicity, we will assume the polygons are convex. You must implement the separating axis method to check for collisions:

Check if there is a line that separates the polygons, putting one polygon on each side of the line. This method will require minimal modifications to implement collision resolution next week, since it already computes the direction that the polygons bounce off.

Separating axis

Aside: Projection

The projection of a polygon onto a line is the line segment containing the projections of all points in the polygon onto the line, shown as the thick blue line below. For example, if the line is the x-axis, the projection of the polygon is the segment from the minimum x value of any vertex to the maximum x value of any vertex.

The projection of a vertex onto a general line can be found by the dot product of the vertex with a unit vector pointing along the line, since that computes the component of the vertex in the direction of the line.

To find the projection of a polygon onto a line, we compute the dot product of each vertex with the line’s unit vector and take the minimum and maximum values.

Separation

Two polygons do not intersect iff the projections of the polygons onto some axis (black) do not overlap. The red line perpendicular to this axis is a separating axis: the axis splits the plane with one polygon on each side.

Two polygons intersect iff the projections of the polygons onto all axes overlap. The red line shows the overlap.

It is not sufficient to check a single axis, since every pair of polygons has some axis where their projections overlap. However, if there is a separating axis, then without loss of generality, there is a separating axis perpendicular to an edge of one of the polygons. For example, if one polygon has 3 sides and the other has 6, we need to check 9 axes (those perpendicular to the 9 edges) to be sure the polygons intersect.

If the projections of the polygons onto one of those axes do not overlap, you should conclude that the polygons do not intersect and skip the other axes. If the polygons are far apart, then their projections onto most axes will not overlap and this algorithm will quickly determine that they do not intersect.

An example with all axes drawn (from http://www.dyn4j.org/2010/01/sat/):

An example where some projections overlap, but others do not such that there is a separating axis (red):

For more information see http://www.dyn4j.org/2010/01/sat/ or https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem–gamedev-169.

Copying files Over

First, copy over the following library files from last week’s project:

• list.c
• polygon.c
• vector.c

You may/may not also have to copy code from last week’s forces.c and forces.h if your teammate added helper functions/structs.

You will have to copy other files over as well, but they will be specified for you in the guide.

Body “info” field

Different applications will need to use different extra information about bodies. For example, for Space Invaders, you will need to be able to differentiate between the player and enemies. Thus, we will need to add auxilliary data to the body as a void *.
Since this means there is extra information to pass into body_init, this will necessitate creating a second constructor that includes a value for the void *. The new body struct is provided in the code.

Giving the scene additional information about force creators

Because our demo this week uses destructive collisions, bodies will be removed by collisoins which needs to trigger the removal of related force creators. To do this, we’ll keep track of a list of bodies that each force creator is responsible for.

Aside: You may have noticed that each aux already contains a list of bodies, and now each force creator will also keep track of a list of bodies. These lists should contain pointers to the exact same bodies! The current design is a little bit redundant due to a lot of refactoring of the projects from last year, but for now, we’ll stick with this.

To manage the list of bodies, we’ll need to “deprecate” the old function scene_add_force_creator. Library writers can mark functions as “deprecated” if they should no longer be used, but they still need to exist for backwards compatibility. The new function scene_add_bodies_force_creator will replace this function and allow the scene to store which bodies are associated with which force creators. scene_add_force_creator has been modified for you to call the new one instead of duplicating functionality.

Because of these changes, the create force creator functions in force.c are now modified to pass in a list of relevant bodies. We have implemented this for you already. Note that bodies passed into body_aux_init and scene_add_bodies_force_creator are the exact same bodies yet part of different lists.

Aside: An alternative to creating two different lists would’ve been having the aux and the force creator point to the same list. However, this would create confusion over who actually “owns” the list of bodies, so we duplicate the list. Notice that for both, free_func_t for the list of bodies is always NULL. This is because the scene has ownership of the bodies.

Delayed body and force creator removal

Giving the scene access to the relationship between bodies and force creators allows it to take ownership of managing their lifetimes. That is, the scene can now be responsible for actually freeing the bodies and removing the force creators from itself.

This gets very convoluted very quickly if we attempt to have the force creators do this work; so, we’ll employ another design pattern: delaying action. We will make scene_tick responsible for actually doing the removal at the end.

This is why your teammate last week coded body_remove to “set a flag” to indicate that it is ready to be deleted by the scene rather than immediately actually deleting itself. Make sure to review the documentation in the body and scene header files for specifics.

Consequently, we’ll deprecate scene_remove_body; all body removals should be done with body_remove moving forward. However, like before, we want to ensure backward compatability. Thus, you’ll have to modify scene_remove_body so that it uses body_remove instead of actually removing the body from the list of bodies.

We’ve added a force_creators field to the scene_t struct this week to keep track of the list of force creators. You may have done this last week already, but we refer to it in the starter code, so rename all occurrences to avoid any confusion.

Next, you’ll implement scene_add_bodies_force_creator and scene_remove_body while ensuring backward compatability. Before you do that though, you might need to update forces.c (and possible forces.h) so that your force creator struct (if you have one) can take in a list of bodies. This depends on how your teammate implemented force creators last week.

Finally, you’ll have to implement our new scene_tick method. The order of removing and free’ing things can get pretty complex, so we’ve included some pseudocode and helpful hints. Make sure to replace the comments with your code once you’re done; they are there for clarification.

Note: Since we’re traversing through lists and removing items, we’ll have to decrement the index whenever we remove something (since the for loop will increment it back in the next iteration). However, there may be a case where the index is 0 and we try to decrement it before incrementing it, which will cause a size_t underflow. Thus, we’ll have to use a ssize_t instead of size_t.

Collision Implementation

We know collision detection is complicated. Thus, we’ve provided you with a few helper functions and helpful hints in collision.c. Once you’ve understood the algorithm, read over collision.c in its entirety before you start coding. This will make coding it a lot easier.

Testing

We will provide tests for the physics engine files. All provided tests must pass in order to receive full credit.

Remember that you can run all the tests with make test.