Studying math for hours can, most likely, lead to blankly staring into the abyss of notes feeling unsure if you learned anything in the past few hours. Hell, I've just been reading Wikipedia page after Wikipedia page on mathematical topics and decided to title my blog post, "Does Frankenstining Geometry(Convex) Prove Intersection?" Now, I know you just stumbled into a math blog, possibly by mistake, intrigued to see how I manage to relate some grotesque monster with an abnormal brain and Frankenstein's creature. I'm not even sure how I will be able to consistently relate the two nor promise to throughout this, but hopefully, by the end of this post, you will walk away with something more than your brain on fire trapped in a burning windmill. I'll go over how we will "stitch" two simple geometric shapes together and lightly describe the concept of the GJK algorithm which can give you insight on whether an intersection between the two simple geometric shapes we put together exists or not. An added bonus is just a simple glossary of terms you're already probably familiar with along with some images I drew in MS paint. Enjoy.
Can you make a loop? Yes. Can you add or subtract vectors? Yes. Congratulations, you can make your own Frankenstein geometry! It's called the Minkowski Sum and Difference and it's extremely useful to know, especially in collision detection. All that is required is that you have two sets of points representing convex shapes and you add or subtract each point in the first set with each point in the second set. I'm going to show you pseudocode and then list some of the things you may find it useful for.
Pseudocode:
int Minkowski Sum(
// [in]
Point* _a,
const unsigned int& _a_size,
Point* _b,
const unsigned int& _b_size,
// [out]
Point* _out
unsigned int& _out_size)
{
for ( i = 0; i < _a_size; ++i )
{
for ( j = 0; j < _b_size; ++j )
{
// Add _a[i] to _b[j]
}
}
return DoYouEvenCodeBruh ? 13375P34K : ALLYOURBASEAREBELONGTOME; // A fine dilema indeed.
}
Yes, this pseudocode is not my best work, but now you get the idea of the Minkowski sum implementation. The Minkowski difference is just this implementation, but with subtraction. Reducing the set produced by the function is a whole other topic in itself probably involving a very common computer science problem of efficiently calculating the convex hull. A brief description of the convex hull is found below and I might possibly blog about it some other time.
Here are some interesting things you can do with the Minkowski Sum when used on the following:
Shape + Point = Translated Shape
Shape + 2 Points = Two Translated Copies of the Shape
Circle + Circle = A larger Circle located at the sum of the centers
Shape + (Line or Curve) = Shape-swept Shape
Line + Line parallel to the first Line = Longer Line
Line + Line perpendicular to the first Line = Square
And interestingly for the Minkowski Difference:
Shape + Shape = Larger Shape
If two shapes overlap they will contain the origin.
Notice that the set of points produced by the Minkowski Difference will contain the origin if they intersect. This is extremely useful for checking convex shapes against each other and leads me to the next topic of the GJK algorithm. You see, the Minkowski operations set up the set of points, but we still need to determine if the origin is contained within this convex set. I won't be able to provide pseudocode for this algorithm as I'm still actively researching it, but I'll try to provide a little insight on it from what I currently understand. The GJK algorithm iterates through the set of convex points by checking to see if a triangle(2D) or tetrahedron(3D) can be formed by that set of points around the origin. If so, then you guessed it, there is an intersection. Here's an image I made to illustrate how I think the algorithm works in a 2D case:
(Figure 1) My idea of how GJK works for 2D space given a convex hull through the Minkowski Difference.
Bonus Glossary
(Figure 2) A helpful representation of some of the volumes used in collision detection. I got lazy after drawing the skull.
Point - The main structure of all other geometrical structures is based on in this glossary. For the sake of simplicity, the point will be defined as a vector representing a position in 2D or 3D Euclidean space.
Line - A set of points that can be produced by a function calculating the linear combination between two distinct points: L(t) = ( 1 - t ) PointA + t * PointB where -∞ < t < ∞ a.k.a the parametric line equation. A line divides 2D space into two subspaces.
Line Segment - A subset of points within the parametric line equation in which the parameter t is clamped to 0 ≤ t ≤ 1.
Line Ray - A half-infinite line that can be formed by the equation L(t) = PointA + t( PointB - PointA) where t ≥ 0.
Plane - A flat surface that divides 3D space into two subspaces since it extends in all directions infinitely. It can be represented as three points that are non-collinear, a normal and a point on the plane, or a normal and a distance from the origin.
Polygon - A 2D shape composed of n vertices which are connected through an equal amount of n edges where n is finite. It is a closed figure which means that the last edge connects to the first vertex. Polygons have multiple classifications such as being convex(all angles ≤ 180°) or concave(at least one angle > 180°).
Polyhedron - A 3D shape composed of a finite number of polygonal faces. Each face's edge is shared exactly with one other face. Like polygons, polyhedrons have multiple classifications. A polyhedron considered convex will contain vertices that all lie to one side of a given face for every face the shape has.
Simplex - A shape that is the simplest of its dimension. If any point that defined the shape is removed then its dimensionality will be reduced i.e. removing a point that forms a triangle would cause it to become a line. Examples: Point(0D), Line Segment(1D), Triangle(2D), Tetrahedron(3D), Cell(4D), ..., etc.
Axis-Aligned Bounding Box(AABB) - A rectangle in 2D or cuboid in 3D with all of its face normals permanently parallel with the coordinate axes. Common representations are min and max position, a min position, height, width, and depth, and a center position, height extent, width extent, and depth extent.
Circle - 2D shape composed of a center and radius.
Sphere - Similar to the circle except existing in 3D space. It has a center and radius.
Oriented Bounding Box(OBB) - Similar to the AABB, OBBs are rectangles in 2D or cuboids in 3D with the added data describing its orientation.
Capsule - A sphere-swept line.
Lozenge - A sphere-swept rectangle.
Slab - A slab in a region that extends infinitely and bound by two planes.
Discrete-Orientated Polytope(DOP) - A volume of intersecting extents along with some number of directions. Most volumes, such as AABBs and OBBs, are a specific type of DOP. Their axes do not have to be orthogonal.
Support Map - A function that maps a direction into a supporting point. Simple convex shapes can be mapped using elementary mathematical functions, while, more complex geometry will require numerical methods.
Supporting Plane - A supporting point within a plane that possesses a normal same as the given direction.
Supporting Point a.k.a. Extreme Point - A point furthest along a direction for a given geometry.
Supporting Vertex - A vertex that is a supporting point.
Separating Plane - A plane that has no intersections with two convex sets, each entire convex set is in a separate halfspace.
Separating Axis - A separating plane that has a normal orthogonal to an axis.
Convex Hull - A subset of convex points from a set of points representing convex geometry in its respective dimension i.e. convex polygons in 2D and convex polyhedrons in 3D.
Minkowski Sum and Difference - Operations that are applied to sets of points and return a set of points. The returning set of points can interestingly yield some useful information or shapes depending on which operation is used. The Minkowski sum can translate a shape, copy a shape and translate both the original and copy, create a shape-swept shape, and more. The Minkowski difference will produce a convex shape and if that shape encompasses the origin, then the two original sets of points are intersecting.
