# HG changeset patch
# User Sam <sam@basx.dev>
# Date 1706189002 -25200
# Node ID a9d2f56556c5043d3ad3dd7c1cc879e79d1999a9
# Parent  a91219ef6ef99c16b46cf4651d83ad4a6ea1267a
add: 2d-packing algorithm for texture-atlas generation

diff -r a91219ef6ef9 -r a9d2f56556c5 semicongine/algorithms.nim
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/semicongine/algorithms.nim	Thu Jan 25 20:23:22 2024 +0700
@@ -0,0 +1,95 @@
+import std/algorithm
+import std/sequtils
+
+import ./core
+
+type
+  Rect = tuple
+    i, x, y, w, h: int
+
+func between(a1, a2, b: int): bool =
+  a1 <= b and b <= a2
+
+func overlap(a1, a2, b1, b2: int): bool =
+  return between(a1, a2, b1) or
+         between(a1, a2, b2) or
+         between(b1, b2, a1) or
+         between(b1, b2, a2)
+
+# FYI: also serves as "overlaps"
+func advanceIfOverlap(fix, newRect: Rect): (bool, int) =
+  let
+    p1 = [
+      (fix.x,             fix.y),
+      (fix.x + fix.w - 1, fix.y),
+      (fix.x,             fix.y + fix.h - 1),
+      (fix.x + fix.w - 1, fix.y + fix.h - 1)
+    ]
+    p2 = [
+      (newRect.x,                 newRect.y),
+      (newRect.x + newRect.w - 1, newRect.y),
+      (newRect.x,                 newRect.y + newRect.h - 1),
+      (newRect.x + newRect.w - 1, newRect.y + newRect.h - 1)
+    ]
+  let overlapping = overlap(fix.x, fix.x + fix.w - 1, newRect.x, newRect.x + newRect.w - 1) and
+                    overlap(fix.y, fix.y + fix.h - 1, newRect.y, newRect.y + newRect.h - 1)
+  if overlapping: (true, fix.x + fix.w) # next free x coordinate to the right
+  else: (false, newRect.x) # current position is fine
+
+proc find_insertion_position(alreadyPlaced: seq[Rect], area: tuple[i, w, h: int], maxDim: int): (bool, Rect) =
+  var newRect = (i: area.i, x: 0, y: 0, w: area.w, h: area.h)
+
+  while newRect.y + newRect.h <= maxDim:
+    var hasOverlap = false
+    var advanceX: int
+
+    for placed in alreadyPlaced:
+      (hasOverlap, advanceX) = placed.advanceIfOverlap(newRect)
+      if hasOverlap: # rects were overlapping and newRect needs to be shifted to the right
+        newRect.x = advanceX
+        break
+
+    if not hasOverlap: # found a collision free position
+      return (true, newRect)
+
+    if newRect.x + newRect.w >= maxDim: # move to next scanline
+      newRect.x = 0
+      newRect.y += 1
+
+  return (false, newRect)
+
+
+proc pack*[T: Pixel](images: seq[Image[T]]): tuple[atlas: Image[T], coords: seq[tuple[x: int, y: int]]] =
+  const MAX_ATLAS_SIZE = 4096
+  var areas: seq[tuple[i, w, h: int]]
+
+  for i in 0 ..< images.len:
+    areas.add (i, images[i].width, images[i].height)
+
+  let areasBySize = areas.sortedByIt(-(it[1] * it[2]))
+  var assignedAreas: seq[Rect]
+  var maxDim = 128
+
+  for area in areasBySize:
+    var pos = find_insertion_position(assignedAreas, area, maxDim)
+    while not pos[0]: # this should actually never loop more than once, but weird things happen ¯\_(ツ)_/¯ 
+      maxDim = maxDim * 2
+      assert maxDim <= MAX_ATLAS_SIZE, &"Atlas gets bigger than {MAX_ATLAS_SIZE}, cannot pack images"
+      pos = find_insertion_position(assignedAreas, area, maxDim)
+
+    assignedAreas.add pos[1]
+
+  # check there are overlaps
+  for i in 0 ..< assignedAreas.len - 1:
+    for j in i + 1 ..< assignedAreas.len:
+      assert not assignedAreas[i].advanceIfOverlap(assignedAreas[j])[0], &"{assignedAreas[i]} and {assignedAreas[j]} overlap!"
+
+  result.atlas = newImage[T](maxDim, maxDim)
+  result.coords.setLen(images.len)
+  for rect in assignedAreas:
+    for y in 0 ..< rect.h:
+      for x in 0 ..< rect.w:
+        let v = images[rect.i][x, y]
+        assert result.atlas[rect.x + x, rect.y + y] == 0, "Atlas texture packing encountered an overlap error"
+        result.atlas[rect.x + x, rect.y + y] = images[rect.i][x, y]
+        result.coords[rect.i] = (x: rect.x, y: rect.y)