Optimize tile-based collision boxes to lines

[MadByte]

Hello everyone, long time no see.

I'm currently looking for options to optimize collision handling in tile-based levels for a project of mine.
Please note: I just lost 2 hours of writing a detailed post about this because for some reason I was logged on, then tried to preview the post, had to log in again and after doing so everything was deleted (even going back in the browser didn't bring the post back). So I will keep this as short as possible this time...

Let's look at this example:


I want to trace the the outlines of the tiles to generate a table of lines to check collisions against as shown in the image.

Can you guys think of any good way of doing this? I'm thankful for any advice, pointers to tutorials, code examples that match my use case.
Feel free to ask for more details if needed.

Attached is the code example for the map without any collision shapes, AABBs, lines whatever.

Thanks in advance.

[ReFreezed]

I think this tutorial I saw recently might be of help:

It shows how to convert a tile map to geometry (around the 7 minute mark). It doesn't handle diagonals, but you should just be able to count the four diagonals as four extra "sides" (top-left, top-right, bottom-left, bottom-right) to each 4-sided tile with the appropriate diagonal neighbor-checking.

(Also, a website suddenly saying you're logged out or something if you take too long filling out a form is the reason I always copy what I've written before pressing submit/preview, or I write everything in a separate text editor from the beginning, just in case. It's a good habit. )

[pgimeno]

This is how I'd do it. I'd use two steps: first construct the polygon, then simplify it.

The method below is not suitable for big maps because it would be too costly.

Constructing the polygon

You would need a polygon per tile: empty tiles would have zero points, full tiles would have four points, and triangular tiles would have three points. Be careful that all of them go around the filled area in the same direction: either all clockwise or all counter-clockwise. I'll choose counter-clockwise for this description. For example, if the tile size is tw, th then a filled tile () would have the following vertices in this order (with Löve's coordinate convention that positive Y is down): (0, 0), (0, th), (tw, th), (tw, 0). An empty polygon would have no vertices. A triangular polygon in "ascending staircase" (◢) position could have: (0, th), (tw, th), (tw, 0).

Now you would add the segments of each tile (after displacing it to its location on the map) to a list. You need to add both the start and end vertex of each segment (including the segment from the last vertex to the first vertex), so in the end every vertex will appear at least twice in the list of segments.

Next, you would go through the list, looking for pairs of segments with the same vertices but in opposite order, and remove both segments each time you find one such pair. After that, you have the contours. You'd go from this:

rect13796.png (7.66 KiB) Viewed 4087 times

to this:

rect13798.png (4.07 KiB) Viewed 4087 times

You can now follow the contours. In most cases there should not be more than one segment starting at the end of a given one, but it's not impossible, like in this case:

rect14002.png (6.36 KiB) Viewed 4087 times

These cases are best avoided when making your maps, but if you absolutely need to handle that, we can discuss it separately.

Simplifying the polygon

For this step I'd suggest creating the simplified set of contours in a separate list, so you can delete segments from the original one in order to know easily which ones are still unprocessed.

It's possible that you're not interested in the outer contour; that one should be easy to identify so you can remove all the segments that belong to it before starting.

So, you can now choose an arbitrary segment from the list and start with the optimization. To avoid the case where you happen to start in the middle of a long span, I'd start by going backwards until you find the start of this segment:

Check if there is another segment that ends where this one starts, and whose (end - start) equals the (end - start) of this one in both X and Y (maybe with some tolerance, if you're not using integer coordinates). If so, choose it as the current segment and repeat. If not, you're ready for starting the actual optimization.

Choose a segment as the current segment, delete it from the segment list, and add its points to the current span (which you haven't added yet). Now, check if there's another segment that starts where this one ends, and has the same (end - start) as the current one. If so, make it the current segment, delete it from the list, replace the current span's end with the end of this segment, and repeat. When the next segment's (end - start) is different, add the current span to the contour list and start again with the new segment as the current segment. If there's no other segment that starts where this one ends, add the current span to the contour list and prepare to open a new contour.

It's somewhat convoluted. I can try to work out an example if you have trouble understanding.

[MadByte]

Thanks, you guys are great!

I think this tutorial I saw recently might be of help:
...
It shows how to to convert a tile map to geometry (around the 7 minute mark).

The video seems promising, but I see a couple potential issues with the slope stuff already... I have to try some things out first I guess.

...

It's somewhat convoluted. (...)

For me? For sure! Thanks for writing it up, regardless.

(...) . I can try to work out an example if you have trouble understanding.

Thanks, that would be great but you really don't have to.

I'll look more into each of the ideas and come back to you.

[pgimeno]

Well, here it is. I've actually kept the units as tiles for simplicity, and transformed them when rendering.

Code: Select all

--[[
love.graphics.setDefaultFilter("nearest", "nearest")
love.graphics.setLineStyle("rough")

local window_width, window_height = love.graphics.getDimensions()
local game_width = 320
local game_height = 180
local scale_x = window_width/game_width
local scale_y = window_height/game_height
local canvas = love.graphics.newCanvas()
local image = love.graphics.newImage("sprites.png")
local iw, ih = image:getDimensions()
local sprites = {
    ["Air"] = false,
    ["Wall"] = love.graphics.newQuad(0, 0, 16, 16, iw, ih),
    ["Slope"] = love.graphics.newQuad(16, 0, 16, 16, iw, ih),
}
local tiles = {}
--]]
local tilewidth = 16
--[[
local map_width = 20
local map_height = 11
--]]
local tile_ids = {
    [0] = {name="Air", rotation=0, poly={}},
    [1] = {name="Wall", rotation=0, poly={{0,0},{0,1},{1,1},{1,0}}},
    [2] = {name="Slope", rotation=0, poly={{0,1},{1,1},{1,0}}}, --up left
    [3] = {name="Slope", rotation=90, poly={{0,0},{0,1},{1,1}}}, -- up right
    [4] = {name="Slope", rotation=-90, poly={{0,0},{1,1},{1,0}}}, -- down left
    [5] = {name="Slope", rotation=180, poly={{0,0},{0,1},{1,0}}}, -- down right
}

local tilemap = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 4, 1, 1, 1, 1, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 4, 1, 1, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 4, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 3, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 1, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 2, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 2, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 2, 1, 1, 1, 1, 1, 1, 3, 0, 1, 1, 3, 0, 0, 0, 1, 1, 1, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
}


-- Construct the list of segments

local segments = {}

for y = 1, #tilemap do
  local row = tilemap[y]
  for x = 1, #row do
    local tile = row[x]
    local poly = tile_ids[tile].poly
    if poly[1] then -- if not empty
      -- Insert the consecutive pairs, in their positions
      for i = 1, #poly - 1 do
        local displaced_pt_1 = {poly[i][1] + (x-1), poly[i][2] + (y-1)}
        local displaced_pt_2 = {poly[i+1][1] + (x-1), poly[i+1][2] + (y-1)}
        table.insert(segments, {displaced_pt_1, displaced_pt_2})
      end
      -- Insert the pair that joins the last vertex with the first
      local displaced_pt_1 = {poly[#poly][1] + (x-1), poly[#poly][2] + (y-1)}
      local displaced_pt_2 = {poly[1][1] + (x-1), poly[1][2] + (y-1)}
      table.insert(segments, {displaced_pt_1, displaced_pt_2})
    end
  end
end

-- Draw what we have so far.
local t = tilewidth*2

local function vlen(x, y)
  return math.sqrt(x*x+y*y)
end

local function drawSegments(segments)
  love.graphics.setColor(1, 1, 1, 0.5)
  love.graphics.setLineJoin("none")
  love.graphics.setLineWidth(2)
  love.graphics.translate(400, 300)
  for i = 1, #segments do
    local seg = segments[i]
    local p1 = seg[1]
    local p1x = p1[1]*t
    local p1y = p1[2]*t
    local p2 = seg[2]
    local p2x = p2[1]*t
    local p2y = p2[2]*t
    love.graphics.circle("fill", p1x, p1y, 3) -- draw 1st vertex
    love.graphics.circle("fill", p2x, p2y, 3) -- draw 2nd vertex
    local l = vlen(p2x-p1x,p2y-p1y)
    local c = -8/l
    local s = 3/l
    local arrow1x = p2x + (p2x - p1x)*c - (p2y - p1y)*s
    local arrow1y = p2y + (p2x - p1x)*s + (p2y - p1y)*c
    local arrow2x = p2x + (p2x - p1x)*c + (p2y - p1y)*s
    local arrow2y = p2y - (p2x - p1x)*s + (p2y - p1y)*c
    love.graphics.line(p1x, p1y, p2x, p2y) -- segment itself
    love.graphics.line(arrow1x, arrow1y,p2x,p2y,arrow2x,arrow2y) -- arrowhead
  end
  love.graphics.setColor(1, 1, 1, 1)
  love.graphics.setLineWidth(1)
  love.graphics.setLineJoin("miter")
  love.graphics.origin()
end

local phase1 = love.graphics.newCanvas()
love.graphics.setCanvas(phase1)
love.graphics.clear(0, 0, 0, 0)
drawSegments(segments)
love.graphics.setCanvas()

-- We have the segments. Now delete the pairs that go in opposite directions.
-- Iterate in reverse so that table.remove doesn't screw up our indices.
for i = #segments - 1, 1, -1 do
  local seg1 = segments[i]
  -- A segment is a double array: two points (start and end), each with two
  -- coordinates.
  for j = #segments, i + 1, -1 do
    local seg2 = segments[j]
    if seg1[1][1] == seg2[2][1] -- if the 1st segment's start X equals the 2nd's end X
      and seg1[1][2] == seg2[2][2] -- and ditto for Y
      and seg1[2][1] == seg2[1][1] -- and same with start and end reversed
      and seg1[2][2] == seg2[1][2]
    then
      -- Delete both segments from the pool, first j then i
      table.remove(segments, j)
      table.remove(segments, i)
      break -- we're done with seg1, advance to the next
    end
  end
end

-- Draw what we have so far.
local phase2 = love.graphics.newCanvas()
love.graphics.setCanvas(phase2)
love.graphics.clear(0, 0, 0, 0)
drawSegments(segments)
love.graphics.setCanvas()


-- Next step is to optimize each contour and move it into a new table, in order
local contours = {}
local ncontours = 0
local nsegments = #segments
-- Process each contour in the array
while nsegments ~= 0 do
  local segidx = nsegments
  local seg = segments[segidx] -- pick any segment - we choose the last one
  -- Now follow it backwards
  local i = 1
  while i <= nsegments do
    local prevSeg = segments[i]
    -- Check if the end x and y of this segment match the start x and y
    -- of the current segment
    if prevSeg[2][1] == seg[1][1] and prevSeg[2][2] == seg[1][2] then
      -- It's a match - if they are aligned in the same way then
      -- select the new segment, otherwise our search has ended
      if (prevSeg[2][1] - prevSeg[1][1]) * (seg[2][2] - seg[1][2])
        == (seg[2][1] - seg[1][1]) * (prevSeg[2][2] - prevSeg[1][2])
      then
        -- Same alignment - prevSeg is part of the same span, so select it
        seg = prevSeg
        segidx = i
        i = 1 -- Restart search
      else
        break
      end
    else
      -- This segment is not the previous to current - check the next one
      i = i + 1
    end
  end

  -- Now we can start finding segments and adding the whole span of the same
  -- alignment to contours.
  local contour = {seg}
  local nSegsInContour = 1
  table.remove(segments, segidx)
  nsegments = nsegments - 1
  i = nsegments
  while i >= 1 do
    local seg2 = segments[i]
    -- Does the start of seg2 match the end of seg?
    if seg2[1][1] == seg[2][1] and seg2[1][2] == seg[2][2] then
      -- Found the continuation of this poly. Check if same alignment.
      if (seg2[2][1] - seg2[1][1]) * (seg[2][2] - seg[1][2])
        == (seg[2][1] - seg[1][1]) * (seg2[2][2] - seg2[1][2])
      then
        -- They have the same alignment - grow the current segment in the
        -- contour.
        contour[nSegsInContour][2] = seg2[2]
      else
        -- Otherwise add this segment to the contour.
        nSegsInContour = nSegsInContour + 1
        contour[nSegsInContour] = seg2
      end
      -- Delete the new segment from the list of segments.
      table.remove(segments, i)
      nsegments = nsegments - 1
      -- And make the new one current.
      seg = seg2
      -- And restart the search.
      i = nsegments
    else
      i = i - 1
    end
  end
  contours[#contours + 1] = contour

end


local phase3 = love.graphics.newCanvas()
love.graphics.setCanvas(phase3)
for i = 1, #contours do
  drawSegments(contours[i])
end
love.graphics.setCanvas()


-- Extra bonus: find and remove the contour that contains point (0,0)
local found = false
for i = 1, #contours do
  for j = 1, #contours[i] do
    if contours[i][j][1][1] == 0 and contours[i][j][1][2] == 0 then
      found = true
      break
    end
  end
  if found then
    table.remove(contours, i)
    break
  end
end
      


-- Transform the contour into a polyline suitable for love.graphics.polygon()

local polylines = {}
for i = 1, #contours do
  local poly = {}
  local nv = 0
  for j = 1, #contours[i] do
    local startpoint = contours[i][j][1]
    poly[nv + 1] = startpoint[1] * t
    poly[nv + 2] = startpoint[2] * t
    nv = nv + 2
  end
  polylines[#polylines + 1] = poly
end

local phase4 = love.graphics.newCanvas()
love.graphics.setCanvas(phase4)
love.graphics.clear(0, 0, 0, 0)
love.graphics.translate(400, 300)
love.graphics.setLineWidth(2)
for i = 1, #polylines do
--  love.graphics.polygon("line", polylines[i])
  love.graphics.polygon("line", polylines[i])
end
love.graphics.setLineWidth(1)	
love.graphics.origin()
love.graphics.setCanvas()

-- Print the canvases

local k = false
local canvasnum = 1
local canvases = {phase1, phase2, phase3, phase4}
function love.draw()
  love.graphics.setBlendMode("alpha", "premultiplied")
  love.graphics.draw(canvases[canvasnum])
  love.graphics.setBlendMode("alpha", "alphamultiply")
  love.graphics.print("Phase " .. canvasnum, 400, 250)
  local oldk = k
  k = love.keyboard.isScancodeDown("space")
  if not oldk and k then
    canvasnum = canvasnum + 1
    if canvasnum > #canvases then
      canvasnum = 1
    end
  end
end

function love.keypressed(key)
    if key == "escape" then love.event.quit() end
end

[MadByte]

Well, here it is. I've actually kept the units as tiles for simplicity, and transformed them when rendering.

Code: Select all

--[[
love.graphics.setDefaultFilter("nearest", "nearest")
love.graphics.setLineStyle("rough")

local window_width, window_height = love.graphics.getDimensions()
local game_width = 320
local game_height = 180
local scale_x = window_width/game_width
local scale_y = window_height/game_height
local canvas = love.graphics.newCanvas()
local image = love.graphics.newImage("sprites.png")
local iw, ih = image:getDimensions()
local sprites = {
    ["Air"] = false,
    ["Wall"] = love.graphics.newQuad(0, 0, 16, 16, iw, ih),
    ["Slope"] = love.graphics.newQuad(16, 0, 16, 16, iw, ih),
}
local tiles = {}
--]]
local tilewidth = 16
--[[
local map_width = 20
local map_height = 11
--]]
local tile_ids = {
    [0] = {name="Air", rotation=0, poly={}},
    [1] = {name="Wall", rotation=0, poly={{0,0},{0,1},{1,1},{1,0}}},
    [2] = {name="Slope", rotation=0, poly={{0,1},{1,1},{1,0}}}, --up left
    [3] = {name="Slope", rotation=90, poly={{0,0},{0,1},{1,1}}}, -- up right
    [4] = {name="Slope", rotation=-90, poly={{0,0},{1,1},{1,0}}}, -- down left
    [5] = {name="Slope", rotation=180, poly={{0,0},{0,1},{1,0}}}, -- down right
}

local tilemap = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 4, 1, 1, 1, 1, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 4, 1, 1, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 4, 1, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 3, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 1, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 2, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 2, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 2, 1, 1, 1, 1, 1, 1, 3, 0, 1, 1, 3, 0, 0, 0, 1, 1, 1, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
}


-- Construct the list of segments

local segments = {}

for y = 1, #tilemap do
  local row = tilemap[y]
  for x = 1, #row do
    local tile = row[x]
    local poly = tile_ids[tile].poly
    if poly[1] then -- if not empty
      -- Insert the consecutive pairs, in their positions
      for i = 1, #poly - 1 do
        local displaced_pt_1 = {poly[i][1] + (x-1), poly[i][2] + (y-1)}
        local displaced_pt_2 = {poly[i+1][1] + (x-1), poly[i+1][2] + (y-1)}
        table.insert(segments, {displaced_pt_1, displaced_pt_2})
      end
      -- Insert the pair that joins the last vertex with the first
      local displaced_pt_1 = {poly[#poly][1] + (x-1), poly[#poly][2] + (y-1)}
      local displaced_pt_2 = {poly[1][1] + (x-1), poly[1][2] + (y-1)}
      table.insert(segments, {displaced_pt_1, displaced_pt_2})
    end
  end
end

-- Draw what we have so far.
local t = tilewidth*2

local function vlen(x, y)
  return math.sqrt(x*x+y*y)
end

local function drawSegments(segments)
  love.graphics.setColor(1, 1, 1, 0.5)
  love.graphics.setLineJoin("none")
  love.graphics.setLineWidth(2)
  love.graphics.translate(400, 300)
  for i = 1, #segments do
    local seg = segments[i]
    local p1 = seg[1]
    local p1x = p1[1]*t
    local p1y = p1[2]*t
    local p2 = seg[2]
    local p2x = p2[1]*t
    local p2y = p2[2]*t
    love.graphics.circle("fill", p1x, p1y, 3) -- draw 1st vertex
    love.graphics.circle("fill", p2x, p2y, 3) -- draw 2nd vertex
    local l = vlen(p2x-p1x,p2y-p1y)
    local c = -8/l
    local s = 3/l
    local arrow1x = p2x + (p2x - p1x)*c - (p2y - p1y)*s
    local arrow1y = p2y + (p2x - p1x)*s + (p2y - p1y)*c
    local arrow2x = p2x + (p2x - p1x)*c + (p2y - p1y)*s
    local arrow2y = p2y - (p2x - p1x)*s + (p2y - p1y)*c
    love.graphics.line(p1x, p1y, p2x, p2y) -- segment itself
    love.graphics.line(arrow1x, arrow1y,p2x,p2y,arrow2x,arrow2y) -- arrowhead
  end
  love.graphics.setColor(1, 1, 1, 1)
  love.graphics.setLineWidth(1)
  love.graphics.setLineJoin("miter")
  love.graphics.origin()
end

local phase1 = love.graphics.newCanvas()
love.graphics.setCanvas(phase1)
love.graphics.clear(0, 0, 0, 0)
drawSegments(segments)
love.graphics.setCanvas()

-- We have the segments. Now delete the pairs that go in opposite directions.
-- Iterate in reverse so that table.remove doesn't screw up our indices.
for i = #segments - 1, 1, -1 do
  local seg1 = segments[i]
  -- A segment is a double array: two points (start and end), each with two
  -- coordinates.
  for j = #segments, i + 1, -1 do
    local seg2 = segments[j]
    if seg1[1][1] == seg2[2][1] -- if the 1st segment's start X equals the 2nd's end X
      and seg1[1][2] == seg2[2][2] -- and ditto for Y
      and seg1[2][1] == seg2[1][1] -- and same with start and end reversed
      and seg1[2][2] == seg2[1][2]
    then
      -- Delete both segments from the pool, first j then i
      table.remove(segments, j)
      table.remove(segments, i)
      break -- we're done with seg1, advance to the next
    end
  end
end

-- Draw what we have so far.
local phase2 = love.graphics.newCanvas()
love.graphics.setCanvas(phase2)
love.graphics.clear(0, 0, 0, 0)
drawSegments(segments)
love.graphics.setCanvas()


-- Next step is to optimize each contour and move it into a new table, in order
local contours = {}
local ncontours = 0
local nsegments = #segments
-- Process each contour in the array
while nsegments ~= 0 do
  local segidx = nsegments
  local seg = segments[segidx] -- pick any segment - we choose the last one
  -- Now follow it backwards
  local i = 1
  while i <= nsegments do
    local prevSeg = segments[i]
    -- Check if the end x and y of this segment match the start x and y
    -- of the current segment
    if prevSeg[2][1] == seg[1][1] and prevSeg[2][2] == seg[1][2] then
      -- It's a match - if they are aligned in the same way then
      -- select the new segment, otherwise our search has ended
      if (prevSeg[2][1] - prevSeg[1][1]) * (seg[2][2] - seg[1][2])
        == (seg[2][1] - seg[1][1]) * (prevSeg[2][2] - prevSeg[1][2])
      then
        -- Same alignment - prevSeg is part of the same span, so select it
        seg = prevSeg
        segidx = i
        i = 1 -- Restart search
      else
        break
      end
    else
      -- This segment is not the previous to current - check the next one
      i = i + 1
    end
  end

  -- Now we can start finding segments and adding the whole span of the same
  -- alignment to contours.
  local contour = {seg}
  local nSegsInContour = 1
  table.remove(segments, segidx)
  nsegments = nsegments - 1
  i = nsegments
  while i >= 1 do
    local seg2 = segments[i]
    -- Does the start of seg2 match the end of seg?
    if seg2[1][1] == seg[2][1] and seg2[1][2] == seg[2][2] then
      -- Found the continuation of this poly. Check if same alignment.
      if (seg2[2][1] - seg2[1][1]) * (seg[2][2] - seg[1][2])
        == (seg[2][1] - seg[1][1]) * (seg2[2][2] - seg2[1][2])
      then
        -- They have the same alignment - grow the current segment in the
        -- contour.
        contour[nSegsInContour][2] = seg2[2]
      else
        -- Otherwise add this segment to the contour.
        nSegsInContour = nSegsInContour + 1
        contour[nSegsInContour] = seg2
      end
      -- Delete the new segment from the list of segments.
      table.remove(segments, i)
      nsegments = nsegments - 1
      -- And make the new one current.
      seg = seg2
      -- And restart the search.
      i = nsegments
    else
      i = i - 1
    end
  end
  contours[#contours + 1] = contour

end


local phase3 = love.graphics.newCanvas()
love.graphics.setCanvas(phase3)
for i = 1, #contours do
  drawSegments(contours[i])
end
love.graphics.setCanvas()


-- Extra bonus: find and remove the contour that contains point (0,0)
local found = false
for i = 1, #contours do
  for j = 1, #contours[i] do
    if contours[i][j][1][1] == 0 and contours[i][j][1][2] == 0 then
      found = true
      break
    end
  end
  if found then
    table.remove(contours, i)
    break
  end
end
      


-- Transform the contour into a polyline suitable for love.graphics.polygon()

local polylines = {}
for i = 1, #contours do
  local poly = {}
  local nv = 0
  for j = 1, #contours[i] do
    local startpoint = contours[i][j][1]
    poly[nv + 1] = startpoint[1] * t
    poly[nv + 2] = startpoint[2] * t
    nv = nv + 2
  end
  polylines[#polylines + 1] = poly
end

local phase4 = love.graphics.newCanvas()
love.graphics.setCanvas(phase4)
love.graphics.clear(0, 0, 0, 0)
love.graphics.translate(400, 300)
love.graphics.setLineWidth(2)
for i = 1, #polylines do
--  love.graphics.polygon("line", polylines[i])
  love.graphics.polygon("line", polylines[i])
end
love.graphics.setLineWidth(1)	
love.graphics.origin()
love.graphics.setCanvas()

-- Print the canvases

local k = false
local canvasnum = 1
local canvases = {phase1, phase2, phase3, phase4}
function love.draw()
  love.graphics.setBlendMode("alpha", "premultiplied")
  love.graphics.draw(canvases[canvasnum])
  love.graphics.setBlendMode("alpha", "alphamultiply")
  love.graphics.print("Phase " .. canvasnum, 400, 250)
  local oldk = k
  k = love.keyboard.isScancodeDown("space")
  if not oldk and k then
    canvasnum = canvasnum + 1
    if canvasnum > #canvases then
      canvasnum = 1
    end
  end
end

function love.keypressed(key)
    if key == "escape" then love.event.quit() end
end

This is pretty cool, thanks a lot!