## Minkowski sums and differences

There are many ways to do collision detection, but a fairly general one is Minkowski differences. The idea is that you do a binary operation on two shapes to get a new shape, and if the origin (the zero vector) is inside that shape, then they are colliding. The minkowski sum lets you define some interesting shapes that are both easy to draw and easy to do collision detection on.

### The Minkowski sum

What does it mean to add shapes?

One representation of a shape is a (possibly infinite) set of points. so, a point is just a set with one element, and a circle is the set , or the set of all points within radius of a centre point .

The minkowski sum of and is the set of all points that are the sum of any point in and . The formula is:

### Some examples

To instill you with intuition of what a minkowski sum looks like, here are a few examples:

The sum of any shape and a point is that shape translated by that point.

The sum of any shape and two points is two translated (possibly overlapping) copies of that shape.

The sum of two circles is a larger circle (sum the radii) with its centre at the sum of the centres of the smaller circles.

The sum of any shape and a line is that shape swept through that line. Think of placing your shape in sand, and dragging it along the line.

Similarly, the sum of a shape and any curve is what you’d get by sweeping the shape through the curve.

The sum of two parallel lines is a longer line.

For perpendicular lines, you get a square.

### Minkowski difference

The minkowski difference is what you get by taking the minkowski sum of a shape and the mirror of another shape. So, your second shape gets flipped about the origin (all of its points are negated).

And if we ask “are these objects colliding?”, we’re really asking if they have any points in common. If they do have a point in common, then must be in the Minkowski difference. If they do not share a point, then is never , because . So, we have reduced the collision detection problem to a Minkowski sum problem.

### Associativity and Commutativity

The Minkowski sum is associative and commutative, so and . This means that we can rearrange sums to make our calculations easier.

So, let’s say you have two circles of radius with centre at point and a square of width at centre and at angle , and you want to find . that not so fun, but you can think about it more easily if you rearrange it as , where is a circle at the origin with radius , and is the square centred at the origin. also, you can further decompose into the sum of two line segments, so then you’re just sweeping a circle through a line, and then sweeping the resultant capsule through another line, and then you can translate the whole thing.

The Minkowski difference is not commutative, because subtraction is not commutative. It is anticommutative, though, which is just about as good. Any time you flip the order of a difference, you have to negate the result. It’s the same as regular subtraction that way.

### Convex polygons and lines

This comes up frequently because you will often want to extrude your shapes along their direction of motion, so that if you’re checking for collisions at regular intervals, fast-moving objects won’t be able to jump over other objects in a single step.

The sum of a polygon and a line is an interesting case, both because it’s simple to compute, and because it comes up naturally in collision detection. Suppose you have a polygon represented by line segments, and each line segment has a normal point out. If you take a new line segment , you can split the polygon’s edges into three groups: those parallel to , those with their normal pointing the same direction as , or , and those with their normal pointing the opposite direction. If there are no parallel edges, then 2 of the points between edges on the polygon will be between an opposite and a same direction edge. You can insert the new line segment on those points, or extend the existing parallel lines, and then you’ll have a new polygon.

This doesn’t work quite right with non-convex polygons, because after the operation, the new polygon can intersect itself. You could modify the method to fix the polygon afterward, but it’s gross, and not something you want to be doing in your physics calulations.

### Higher dimensions

The Minkowski difference method will work in any number of dimensions. There’s also a technique to improve on the sweep-test method described above.

Say you’re working in 2D, and you have fast-moving objects. Sometimes, they will cross paths in a single time step, but they shouldn’t actually collide. if you did a sweep test, they would get marked as having collided, though. One way you can solve this is by going up a dimension to 3D, with time as the third dimension, so instead of extruding in the direction of the velocity, you can extrude in the direction of the velocity with the time component set to 1, instead of 0.

You can cheat a little bit here and bring it back down to a 2D problem by noticing that you only have to worry about the slice of the sum where time = 0. You can rearrange the sum into , and then we can look at , which is a parallelogram, and find the line segment in it where time = 0.

### Support functions and line segments

A support function is a function on a set such that, given a direction, you get the point in the set that is furthest in the direction. if there is more than one furthest point, any one of them will do. So, for a circle, you get , and for a rectangle, you get a function that returns one of the corners.

a useful property of the support function is that the support function of a Minkowski sum of shapes is the sum of the support functions of those shapes.

If you have a convex shape with a support function, and you’re working in 2D, you can easily find the sum of that shape and a line segment:

find the support points in the directions perpendicular to the line segment (there are two). Then, create a parallelogram from the line segment, and the segment between the two support points. The new shape is the union of the parallelogram, and a copy of the shape at each end of the line segment.

you can also do pretty cool things with Minkowski sums of shapes with support functions and polygons, but i’ll leave alone for today.

here’s some javascript code as an example of what i mean about line segments: starting with a circle, and adding 1, 2, then 3 lines.

```
var example = document.getElementById('example');
var context = example.getContext('2d');
function draw_parallelogram(l1, l2,x,y) {
context.beginPath();
context.moveTo(x+l1.start.x + l2.start.x, y+l1.start.y + l2.start.y);
context.lineTo(x+l1.start.x + l2.end.x, y+l1.start.y + l2.end.y);
context.lineTo(x+l1.end.x + l2.end.x, y+l1.end.y + l2.end.y);
context.lineTo(x+l1.end.x + l2.start.x, y+l1.end.y + l2.start.y);
context.fill();
}
function draw_circle(c, x, y) {
context.beginPath();
context.arc(x+c.x, y + c.y, c.r, 0, 2*3.141592653589793);
context.fill();
}
function add_line(shape, line) {
return {
draw: function(p) {
shape.draw({x: line.start.x + p.x, y: line.start.y+p.y});
shape.draw({x: line.end.x + p.x, y: line.end.y + p.y});
a = shape.support({x:-line.end.y + line.start.y, y:line.end.x - line.start.x});
b = shape.support({x: line.end.y - line.start.y,y: -line.end.x + line.start.y});
context.fillStyle = 'red';
draw_parallelogram({start: a, end: b},line, p.x, p.y);
},
support: function(d) {
s = shape.support(d);
x = d.x; y = d.y;
dot = x*(line.end.x-line.start.x) + y*(line.end.y-line.start.y);
p = dot > 0 ? line.end : line.start;
return {x: s.x+p.x, y:s.y+p.y };
}
}
}
function make_circle(r, x, y) {
c = {x:x,y:y,r:r};
return {
draw: function(p) { context.fillStyle = 'white'; draw_circle(c, p.x, p.y); },
support: function(d) {
l = Math.sqrt(d.x*d.x+d.y*d.y);
return {x:d.x/l * r+x, y: d.y/l * r + y};
}
}
}
circ = make_circle(20, 0,0);
capsule = add_line(circ, {start: {x:0,y:0}, end:{x:30,y:50}});
round_square = add_line(capsule, {start: {x:0,y:0}, end:{x:50,y:-30}});
hex = add_line(round_square, {start:{x:10,y:0}, end:{x:60,y:30}});
circ.draw({x:300,y:300});
capsule.draw({x:100,y:100});
round_square.draw({x:200,y:100});
hex.draw({x:100,y:300});
```

and the output:

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

## Archive

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst