Euclidean Distance

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))

Bounds

Simple representation of approximate area covered by an object

Always completely contains the object

Typically a box or a circle/sphere

Bounding Box

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)

Bounding Box

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]

Bounding Sphere

To determine if a point (x,y,z) is inside a bounding sphere:

    distance(center, (x,y,z)) <= radius

Bounding Sphere

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

Note that this computes a bounding sphere, but generally not the smallest bounding sphere - that is a much more complex problem.

Simple Collision Detection

Box-Box Collision

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)

Simple Collision Detection

Sphere-Sphere Collision

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)

This document is by Dave Pape, and is released under a Creative Commons License.