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 vertices:
minX = vertices[0][0]
maxX = vertices[0][0]
minY = vertices[0][1]
maxY = vertices[0][1]
minZ = vertices[0][2]
maxZ = vertices[0][2]
for v in 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 vertices:
xsum += v[0]
ysum += v[1]
zsum += v[2]
center = [ xsum / len(vertices) , ysum / len(vertices), zsum / len(vertices) ]
radius = 0
for v in vertices:
d = distance(v, center)
if d > radius:
radius = d
Note that this computes a bounding sphere, but generally not the smallest bounding sphere - that is a more complex problem.
Compute the overlap of two boxes - the region of points which are contained in both boxes. If an overlap exists, they collide.
OR
If the boxes don't overlap, then box1 must be entirely to the left of box2, or box1 is to the right of box2, or box1 is above box2, etc. For box1 to be left of box2, it's minX will be greater than box2's maxX; similar tests apply for the other 5 cases. Testing for overlap is then the negation of this.
def BoxCollidesWithBox(box1, box2):
return (box1.minX <= box2.maxX) and
(box1.maxX >= box2.minX) and
(box1.minY <= box2.maxY) and
(box1.maxY >= box2.minY) and
(box1.minZ <= box2.maxZ) and
(box1.maxZ >= box2.minZ)
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)
A vector is a direction and magnitude (length). Vectors are used to represent many different things - for example, object motion or relative locations of objects. In 3D, vectors are used extensively in lighting.
We normally describe a vector as a pair of (X, Y) values (in 2 dimensions), or a triplet of (X, Y, Z) values (in 3 dimensions) - (vx, vy, vz) represents a vector that points vx units in the direction of the X axis, vy units in the direction of the Y axis, and vz units in the direction of the Z axis.
e.g., (2, 0, 0) is a vector pointing in the direction of the X axis, 2 units long. (1, 1, 0) is a vector pointing at a 45 degree angle between the X and Y axes, 1.414 units long.
The magnitude of a vector (x,y,z) is its Euclidean length - the square root of vx2 + vy2 + vz2.
Two vectors can be combined by adding their corresponding components
together.
i.e. (vx, vy, vz) +
(wx, wy, wz) is
(vx+wx, vy+wy, vz+wz
).
Or, written more expansively:
The result is a vector that is equivalent to sticking the vector W onto the end of vector V, and creating a new vector from the beginning of V to the end of W.
A vector can be multiplied by a single number (a "scalar") to change its length without changing its direction.
The dot product of two vectors is an operation defined as:
The result is a single number, which is equal to the product of the lengths of the two vectors and the cosine of the angle between them.
It can tell us how much two vectors point in the same direction - it is maximum when they point in exactly the same direction, and it's 0 when they're at right angles.
Creating a vector class allows one to work with vectors more simply.
Vector operations just require a single statement, rather than a loop or separate statements for X, Y, & Z components.
a = Vector3(1, 2, 3)
b = Vector3(0, -1, 0)
c = a + 2 * b
d = a.dot(b)
A vector can be used to represent the motion of an object.
The vector indicates the object's velocity - the direction of the vector is the direction that the object is moving, the magnitude of the vector is the speed.
The vector corresponds to how the object will move in one unit of time.
e.g., a velocity vector of (2, 0, 0) indicates that the object is
moving 2 meters/second along the X axis (assuming our units are meters
and seconds).
If it starts at (3, 1, 0), then after 1 second its position will be
(5, 1, 0). After 2 seconds, its position will be (7, 1, 0).
[Note that the choice of units is arbitrary, and is up to you when writing your programs; all that matters is that you be consistent within a program, and not, for instance, try to combine meters per second with miles per hour.]
In general, if an object starts at position P0, with velocity V, then after t time units, its position P(t) will be:
P(t) = P0 + t * V
The previous formula only works if the object moves with a constant velocity.
In many cases, objects' velocities change over time.
In such a case, velocity is a function that we integrate.
Displacement = 
Velocity dt
In complex motion, there isn't an analytical solution (i.e. a simple formula).
Euler integration approximates an integral by step-wise addition.
At each time step, we move the object in a straight line using the current velocity:
dt = t1 - t0
P(t1) = P(t0) + V * dt
Velocity is the integral of acceleration:
Acceleration dt
Applying Euler integration again gives:
dt = t1 - t0
Acc = computeAcceleration()
Vel = Vel + Acc * dt
Pos = Pos + Vel * dt
Gravity near the Earth's surface produces a constant acceleration of 9.8 m/sec2
In this case:
Acc = Vector3(0, -9.8, 0)
Example: gravbounce.py
Newton's 2nd Law of Motion:
Which can be rewritten as
If an object has mass M, and force F is applied to it,
its motion can be calculated via Euler integration:
Acc = F / M
Vel += Acc * dt
Pos += Vel * dt
Note that F, Acc, Vel, and Pos are all vectors. M is a scalar.
F = (G * M1 * M2) / d2
For a complete simulation, we need to calculate the force on each object every frame.
When multiple forces are applied, their vectors are added.
Example: gravorbit.py
