How to smash a polygon into pieces, quick and dirty

Smashing polygons into smaller polygon pieces with a quick, memorable and efficient algorithm!

If you've ever worked with game development, game modding, whatever it is, you've likely tampered with lower level computer graphics - whether it be shaders, render functions, manual drawing, 3D perspective rendering or anything else. You'll know it's possible to make much nicer, more advanced looking effects with stuff like this, and it'll also be efficient as all hell.

So, when you look at an effect like breaking the screen apart into shards and making it fall, you'll likely think that also requires lower-level access. And while it does to some extent, it's actually surprisingly simple.

I'll be making the example code in LOVE2D, but you're free to use whatever engine you prefer. All you need is direct access to rendering polygons! (I promise you they're not that scary.)

You'll want to start out with a basic polygon. This can be of any shape, but preferably a rectangle. (This'll make handling further parts of this much easier.)

Store all of the vertices of the polygon in some sort of array, and create an array of arrays of vertices. Basically, define yourself an array of polygons which consist of 2D points. For example, in my case it'd be like this:

local polygon = {}

local padding = 15
local sw, sh = love.graphics.getDimensions()
table.insert(polygon, {
  {padding, padding},
  {sw - padding, padding},
  {sw - padding, sh - padding},
  {padding, sh - padding}
})

Once you're done, create code that renders each element in the array as a polygon, and you end up with a rectangle!

Good! This is what we are going to violently destroy. (If you want to render textures to the polygons, you'd want to handle the texture mapping code now, as it's better to do this sooner than later.)

So, you may be wondering, how exactly do you even shatter something in the first place? Well, the method we'll be using is casting several rays. Each ray will split every polygon it hits into two (and only two, be sure to keep this in mind!), effectively doubling the amount of polygons at best.

There's definitely better random polygon algorithms out there, but this one is easy and fast, and is easy to tweak to look more like glass shattering.

So, you'd want to pick a random point on the rectangle and a random angle. For a rectangle, picking a random spot is going to be easy: you generate a random number from x and x+w for the X coordinate, and a random number from y and y+h for the Y coordinate, and since we're starting out with a rectangle as the base shape, we're only going to need this algorithm.

Basically, once you have your ray and polygon(s), you're going to cast a ray for each line in that polygon. To get every line in a polygon, simply get every pair of points in the array - (p[0], p[1]), (p[1], p[2]), (p[2], p[3]), (p[3], p[0]). Afterwards, use a line segment intersection algorithm by extending your ray to a line segment like this:

local x = math.random(0, sw)
local y = math.random(0, sh)
local angle = math.random() * math.pi * 2

local ax, ay = math.cos(angle) * (sw + sh), math.sin(angle) * (sw + sh)
local x1, y1 = x + ax, y + ay
local x2, y2 = x - ax, y - ay

While we could use a ray-line segment intersection algorithm, this is simply easier to handle for me. I'm not the biggest fan of geometry. But after we get this, we can plug it into a line intersection algorithm:

-- see if 2 line segments intersect
local function ccw(a, b, c)
  return (c[2] - a[2]) * (b[1] - a[1]) > (b[2] - a[2]) * (c[1] - a[1])
end

local function areIntersecting(a, b, c, d)
  return ccw(a, c, d) ~= ccw(b, c, d) and ccw(a, b, c) ~= ccw(a, b, d)
end

-- now check _where_
-- this applies to lines and not line segments, which is why we do the
-- above check aswell
local function line(p1, p2)
  A = (p1[2] - p2[2])
  B = (p2[1] - p1[1])
  C = (p1[1] * p2[2] - p2[1] * p1[2])
  return {A, B, -C}
end

local function intersection(L1, L2)
  D  = L1[1] * L2[2] - L1[2] * L2[1]
  Dx = L1[3] * L2[2] - L1[2] * L2[3]
  Dy = L1[1] * L2[3] - L1[3] * L2[1]
  if D ~= 0 then
    x = Dx / D
    y = Dy / D
    return {x, y}
  else
    return false
  end
end

Got all that? Now, let's implement it in code.

You want to iterate through each point on your polygon. Create yourself 2 arrays: P1 and P2. This is where we're going to sort the points of each of the two newly created polygons.

Set yourself a variable called something like currentP and set it to 1. Then, start iterating:

1. Push the current vertex into P1 or P2, depending on if currentP is 1 or 2, respectively
2. Create a line from the current point to the next, wrapping around the array if needed.
3. Does your ray hit this line? (Use the above algorithm).
4. If so, push the point the ray has hit to both P1 and P2 and switch currentP to 1 if it's 2, and to 2 if it's 1.
5. Repeat!

After you're done with this, you should end up with P1 and P2. Push both these arrays to your polygons array and discard the current one. And congrats! You have split a polygon into 2 polygons.

If the lines don't intersect, you'll end up with P2 being empty and P1 just being the original polygon - so before pushing P1 and P2 to the polygon array make sure they're not empty. And there you go! Now, you'll have something like this:

And - that is correct! We've now cut a polygon in half.

You'd want to run, say, 10 iterations of this to result in a broken version of your original rectangle. You can change the amount of iterations to change how broken it is!

Now, you may notice that this all just looks like we've cut the rectangle a bunch of times and that's it. To fix this, instead of iterating through every polygon and casting the same ray, cast a unique ray per each polygon. You should end up with something like this!

There we are. Now, you may notice that this is kind of uneven, maybe too uneven. (If you don't, that's fine! This part and the next parts are entirely optional, but I think it looks nicer.) This is because each time we're casting a ray per each polygon, we may end up with a situation where the ray hasn't actually cut the polygon at all. So, let's try retrying to cast rays until we get a split on each polygon!

This is looking a lot more glass-shard like, isn't it? However, there's one last thing we need to fix.

You'll notice there's lots of polygons that are extremely tiny. This is not ideal, so let's fix that!

To do this, we're going to have to calculate the areas of P1 and P2 after their creation. Then, if they're too uneven, we'll discard and try splitting again.

Here's yet another algorithm - this one will calculate the area! (There are dozens of ways to do this, but this is the simplest one I've found.)

local function findArea(p)
  local area = 0
  for i = 1, #p - 2, 2 do
     area = area + p[i+1][1] * (p[i+2][2]-p[i][2]) + p[i+1][2] * (p[i][1]-p[i+2][1]);
  end
  return area / 2
end

Once we have area1 and area2 of P1 and P2 respectively, we can now compare it. The way I've done it is define a threshold t = 0.4, and see if area1 / area2 > t and area2 / area1 > t. (I know there's a better way of doing this, but this is the easiest to comprehend and read.)

I think that looks quite nice. (Though, you may want to also add a check if the original polygon is above a threshold!)

Before we move on to the last step, to show that it's truly splitting the polygons and not just drawing extra polygons, let's scale down the polygons in the render code. We do this by getting an average X and Y value out of all the vertices, and then scaling it with that as the middle:

local scale = 0.9

local sumX, sumY = 0, 0
for _, v in ipairs(p) do
  sumX = sumX + v[1]
  sumY = sumY + v[2]
end
local avgX, avgY = sumX / #p, sumY / #p

local scaledP = {}
for _, v in ipairs(p) do
  table.insert(scaledP, {(v[1] - avgX) * scale + avgX, (v[2] - avgY) * scale + avgY})
end

-- now use scaledP for the render instead!

Alright, one more extra thing to make this look better! You'll notice that when glass is smashed, there's usually loads more shards in the middle.

You can achieve this by having a random chance to ignore all of our checks and allow in shards anyways using randomness and how close the polygon is to the middle (in this case, that's where the breaking point would be):

local dist = math.sqrt((p[1][1] - sw/2) * (p[1][1] - sw/2) + (p[1][2] - sh/2) * (p[1][2] - sh/2)) / (sw * sh) -- using the first point as a lazy hack
local includePolygon = poly1 > 0 and #poly2 > 0 and (area1 / area2 > 0.6 and area2 / area1 > 0.6) or (math.random() > dist)

However, in this case, you'd want to also lower the threshold t value to make sure there's less glass shards outside of this range.

And this does somewhat work! It leans towards the bottom right as it's checking the top left corner of each polygon for the distance, and you'll make it more accurate if you instead get the average, just like above. You can definitely play around more with the values to get a better result, and maybe make t be controlled by the distance.

I'm pretty happy with this end result! While it isn't the most realistic, it's a very quick solution and it looks nice enough to an average viewer.

This can be done with any 2D polygon, actually! It'll get slower the more vertices you have, however. Here's me smashing a circle (however it did require changing t drastically):

As an exercise to the reader to end on, think of a way to make this more user-intuitive - instead of passing in the amount of iterations, pass something else in - maybe a stopping point? Maybe a threshold value? Some area? Basically, try to make this more friendly to a non-developer.

I hope you learnt something today! This was an interesting experiment for me as I wasn't 100% sure on how it'd work, but I think it looks real nice. Here's the original source code for the LOVE2D project used to make all of the screenshots!