A*A + B*B = C*C
Outline the code for a program which moves multiple objects around on the screen, and has the objects bounce off of each other when they collide.
You don't have to write actual code. If you do write a program, I still want to see a pseudo-code outline of what it does.
Things you should think about and describe:
Distance between two points P0 (x0,y0) and P1 (x1,y1):
A = x1 - x0 B = y1 - y0 (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0) = C*C dist = C = sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0))
Distance between two 3D points P0 (x0,y0,z0) and P1 (x1,y1,z1):
dist = sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0) + (z1-z0)*(z1-z0))
Note: sqrt is considered an expensive (i.e. slow) function
Simple representation of approximate area covered by an object
Always completely contains the object
Typically a box or a circle/sphere
To determine if a point (x,y) is inside a bounding box:
(x >= minX) and (x <= maxX) and
(y >= minY) and (y <= maxY) and
(z >= minZ) and (z <= maxZ)
To compute a bounding box of an object, assuming its vertices are contained in the list obj.vertices:
minX = obj.vertices[0][0]
maxX = obj.vertices[0][0]
minY = obj.vertices[0][1]
maxY = obj.vertices[0][1]
minZ = obj.vertices[0][2]
maxZ = obj.vertices[0][2]
for v in obj.vertices:
if minX > v[0]:
minX = v[0]
elif maxX < v[0]:
maxX = v[0]
if minY > v[1]:
minY = v[1]
elif maxY < v[1]:
maxY = v[1]
if minZ > v[2]:
minZ = v[2]
elif maxZ < v[2]:
maxZ = v[2]
To determine if a point (x,y,z) is inside a bounding sphere:
distance(center, (x,y,z)) <= radius
To compute a bounding sphere, find a center, and then the most distant vertex:
xsum,ysum,zsum = 0,0,0
for v in obj.vertices:
xsum += v[0]
ysum += v[1]
zsum += v[2]
center = [ xsum / len(obj.vertices) , ysum / len(obj.vertices), zsum / len(obj.vertices) ]
radius = 0
for v in obj.vertices:
d = distance(v, center)
if d > radius:
radius = d
Compute the overlap of two boxes - the region of points which are contained in both boxes. If an overlap exists, they collide.
def BoxCollidesWithBox(box1, box2):
minx = max(box1.minX, box2.minX)
maxx = min(box1.maxX, box2.maxX)
miny = max(box1.minY, box2.minY)
maxy = min(box1.maxY, box2.maxY)
minz = max(box1.minZ, box2.minZ)
maxz = min(box1.maxZ, box2.maxZ)
return (minx <= maxx) and (miny <= maxy) and (minz <= maxz)
Compute distance between the centers of the two spheres. If it's less than the sum of the radii, then there exist points that lie within both spheres -> the spheres overlap.
def SphereCollidesWithSphere(s1, s2):
d = s1.center.distanceSquared(s2.center)
rsum = s1.radius + s2.radius
return (d <= rsum*rsum)
sin(A) = opposite / hypotenuse cos(A) = adjacent / hypotenuse tan(A) = opposite / adjacent
or
opposite = hypotenuse * sin(A) adjacent = hypotenuse * cos(a)
x = radius * cos(A) y = radius * sin(A)
Standard math library functions use radians
360 degrees = 1 full circle = 2 π radians
(Circumference of unit circle = 2 π)
radians = degrees / 360.0 * 2 * pi
or
radians = degrees / 180.0 * pi
(or use Python's pre-defined functions math.radians(d) and math.degrees(r))
glBegin(GL_LINE_LOOP)
for degrees in range(0, 360):
angleInRadians = math.radians(degrees)
x = math.cos(angleInRadians) * radius
y = math.sin(angleInRadians) * radius
glVertex2f(x,y)
glEnd()
Vehicle has direction and speed of travel
Direction is orientation - rotation about Z
To move forward:
distance = speed * time
dx = math.cos(direction) * distance
dy = math.sin(direction) * distance
x = x + dx
y = y + dy
atan2 converts from (X,Y) coordinates back to angles
Note: it takes arguments in the order Y, X
angle = math.degrees( math.atan2(y,x) )
Deriving a value for something from two pre-defined values (extremes)
e.g. Moving object from one position to another, over time
Interpolation expressed as fractional distance between the two extremes
Ranges from 0.0 to 1.0
0.0 = first point; 1.0 = second point
For a single value, with extremes V0 & V1 and interpolation fraction A:
V = (1 - A) * V0 + A * V1
For multiple values, such as XYZ position, use the same fraction A for all:
X = (1 - A) * X0 + A * X1
Y = (1 - A) * Y0 + A * Y1
Z = (1 - A) * Z0 + A * Z1
To interpolate over time, compute interpolation fraction based on the amount of time that has passed.
Example:
def startAnimation():
animating = True
startTime = time.time()
duration = 5
def computeAnimation():
if animating:
t = time.time() - startTime
if t <= duration:
a = t / duration
else:
animating = False
a = 1
x = (1-a)*startX + a*endX
y = (1-a)*startY + a*endY
z = (1-a)*startZ + a*endZ
| Linear | Slow-in Slow-out |
|---|---|
 |  |
| X = t | X = -2*t*t*t + 3*t*t |
A2 = -2*A*A*A + 3*A*A V = (1-A2) * V0 + A2 * V1
We often would like the behavior of a program to change or be unpredictable - to not be exactly the same every time we run it.
In other cases, randomness helps eliminate unwanted artifacts, such as obvious, excessively regular or repeated patterns. These include patterns in the appearance and in the movement of objects.
 | 
|
Things that can be randomized include:
Randomness is added to programs by using random numbers. These are generated by random number functions.
Python has a package called random.
Two of the functions it provides are:
Returns a random floating point number between 0 and 1.
Returns a random floating point number between a and b.
In C, the standard random number functions are:
Returns a random integer between 0 and RAND_MAX
Returns a random float between 0 and 1
Random numbers can come in different distributions - how frequently the various numbers occur.
e.g. rolling a fair die many times will yield roughly
the same number of 1s, 2s, 3s, 4s, 5s, and 6s.
A loaded die can produce one number more frequently.
random() & uniform()
return uniform distributions - each possible number is equally
likely to be returned.
If you call the function a large number of times, then you
can expect each possible number to be returned about (but not exactly)
the same number of times.
(Flipping a coin 1,000,000 times, you would expect to get roughly
500,000 heads and 500,000 tails.)
This plot is from calling int(random() * 100) 100,000 times. It shows how many times each of the possible values (from 0 to 99) was returned.
Sometimes we want a different distribution.
A common distribution is the bell curve (or gaussian distribution). In this distribution, one small range of numbers is returned more frequently than others, with values further from the center of the distribution returned less and less frequently.
The function random.gauss(center, deviation) returns random numbers in a gaussian distribution.
The first argument (center) is the central number that the return
values will be clustered around. The second argument (deviation)
is the standard deviation of the distribution - this measures how broad the
bell curve is; roughly 2/3 of all returned values will be within +/- deviation
of the center value.
Example: a gaussian distribution lets you place objects randomly, but clustered about a center.
| Uniform | Gaussian |
|---|---|
| 
|
