Assignment 3: Hierarchically Defined Objects and Collision Detection

CS 426 Assignment 3

Hierarchically Defined Objects and Collision Detection

Due 1159 PM, Friday, November 8

First of all: this assignment should be done in teams of two. If you have trouble finding a partner, send us e-mail, so we can assign you one.

Introduction

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.

The objects

The most basic object you could implement is a "face" made up of circles and triangles, for example:

A more complicated shape could be -->

<-- Or maybe something like this

Especially with an object like the last one you wouldn't start out with that many features, but with a simpler shape, and you would add features as you go along.

Object behaviour

Your objects move around in a rectangular box. You will need to be able to determine when two objects intersect, and when an object intersects the boundary of the box. So for the simplest shape this would be:

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

Generally speaking, something should happen when two shapes intersect. In particular, a shape should change its generation (either up or down, depending on the rules you set for this).

For example, 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 two eyes and a mouth inside -->

<-- A generation 3 version of the face has a smaller version of the face in each of the eyes.

The key issue here is that it should be possible for a basic shape to reappear in higher generation versions of itself.

Collision rules

If two shapes collide, each changes its generation by one. The objects obey the laws of physics, conservation of energy and momentum (you can assume objects are circular in shape even if they're not, and you can assume all objects have equal mass or have mass increase with the generation).

If a shape collides with a wall, it bounces back with the same velocity and reflected direction.

Implementation issues

Use a hierarchical data structure for your shapes. Implement matrices & transformation yourself, i.e. don't use OpenGL's matrix functions.

You (the two of you) are to write all code yourself for this assignment. 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 shapes to a scene.

Every shape starts at generation 1 and is always of the same size. The user places it by a mouse click and also gives it a velocity with magnitude and direction. The shape moves with this velocity until it either hits another face or hits a wall.

Extra credit

If you implement the assignment described so far for the "face" shape, you score 8 out of 10. Extra credit suggestions are:

make parts of your shape move in their parent shape: for example, rotate faces inside the eyes of a parent face
make your shapes elastic: when two collide, they'll get smaller and expand, etc. until they're back to normal. Add a slider to set the elasticity of shapes
implement a more complicated shape (like the second or third example above), and do correct collision detection for these shapes
implement more complicated rules for interaction between the shapes
raise the entire environment to 3D: replace circles by spheres and triangles by tetrahedra. Collision detection isn't much harder but you must handle various viewing issues

Literature

Ed Emberley's Little Drawing Book of Birds, Edward R. Emberley, Little, Brown & Company, Canada, 1973

But seriously:

the lecture notes
chapter 5 of Hearn & Baker: Two-Dimensional Geometric Transformations
chapter 7: Structures and Hierarchical Modelling
appendix A: Mathematics for Computer Graphics

CS426, CS Department, Princeton University

Last modified: Thu Oct 17 12:04:15 1996