COS 426 Assignment 4

Hierarchically defined objects and collision detection

Due 1159 PM Tuesday November 14

In this assignment you will learn to build complex objects, to test whether complex objects intersect with one another, and to create an animation of a collection of objects which responds to intersections among the objects.

1. The objects we build will be based on circles and triangles. We will begin with boundaries which are circular objects. These objects will be moving in a rectangular box that you define as a viewport on the screen. You will need to be able to determine when 2 objects intersect and also when an object intersects the boundary of the box. The primitive operations you must implement first are

   • A procedure to detect when 2 circles (possibly of different radii) intersect.
   • A procedure to detect when a circle intersects a line segment. You can assume here that the line segment is either vertical or horizontal.

2. Next you need to create a procedure to create shapes of ever increasing complexity. We will being with a shape that is meant to be a face with 2 round eyes and a triangular mouth. An example of this shape is
   
   This will be our generation 1 version of the shape. Note that the centers of the circles of the two eyes and the face itself all have the same y-coordinate. The radius of each of the smaller (eye) circles is half that of the larger (face) circle.

   A generation 2 version of the face has a smaller version of the face in one of the eyes. That is, the eye now serves as the face with 2 eyes and a mouth inside. For example,
   
   

   A generation 3 version of the face has a smaller version of the face in each of the eyes. For example,
   
   

   We can proceed in this way creating generation 4, 5, 6, 7 faces each having more eyes converted to faces. Similarly, generations 8 through 15 add another level of recursion.

   What you need to create here is a procedure to generate a face of any generation. Model the face in such a way that it will be easy to move it, to rotate it, ...

3. Now that you have faces and intersection detection routines, you're ready to proceed. You are to write all of your code yourself in this animation. You can build upon Tcl/Tk or OpenGL scaffolding provided in previous assignments but we will provide no shell for you.

   Your world will evolve in a rectangular window. The user must be allowed to change the size of the window in standard fashion. You must provide a user interface that allows the user to add new faces to a scene. Every face starts at generation 1 and is always of the same size. The user places it by a mouse click and also gives it a rotation and a velocity with magnitude and direction. The face moves with this velocity until it either hits another face or hits a wall.

   The rules for collisions are as follows:

   • If two faces collide, each increases its generation by one. The objects obey the laws of physics, conservation of energy and momentum (you can either assume all objects are the same mass or have mass increase with the generation). This is sufficient to assign them new velocities and directions after a collision.
   • If a face collides with a wall, it bounces back with the same velocity and reflected direction. It does not change generation.

   Begin by having one face moving in the rectangular window. When you're comfortable with this, introduce another face. As things progress, add more faces.

4. Now that you're comfortable with this scenario, you are ready to enhance the universe you have created. First, you must add a feature to the existing bodies. This is a rotational feature from which you will learn a lot about transformation matrices. Give each eye (regardless of generation level) some spin. Thus the head will have its eyes rolling as it moves around the screen. You can assign rotations as you wish. However, the rotation should be noticeable as the face moves and eyes within eyes should have different rotations from their parent eye, ... It's up to you whether the two eyes of a face rotate the same way,
5. For your final addition to the assignment, you must take the infrastructure you've built here and apply it to more complex objects. Rather than having the objects grow within themselves, you should define objects that grow with collisions. You will also want to use bounding shapes that are more complex than circles so that intersection detection will be more challenging.

   Very easy changes you can make are to replace circles living within circles by triangles living within triangles or squares living within squares. You might want to do this as a test of the quality of your code. It should be a simple change. You will get partial credit for doing this change and no other.

   A related change that is acceptable is to raise the entire environment to 3D. Replace circles by spheres and triangles by polyhedra. Collision detection isn't much harder but you must handle various viewing issues.