Add padding support to the texture packer

[liquidev]

No padding often results in weird artifacts, especially visible when rendering text. A single pixel of padding should be able to fix the issue.

[mrgaturus]

i made a port of skyline algorithm used in fontstash, i got very efficent and fast results here is the code:

type
  SKYNode = object
    x, y, w: int16
  MYAtlas = object
    # Your Atlas Stuff
    # ....
    # Skyline Packing
    w, h: int32
    nodes: seq[SKYNode]

proc rectFits(atlas: var MYAtlas, idx: int32, w,h: int16): int16 =
  if atlas.nodes[idx].x + w > atlas.w: return -1
  var # Check if there is enough space at location i
    y = atlas.nodes[idx].y
    spaceLeft = w
    i = idx
  while spaceLeft > 0:
    if i == len(atlas.nodes): 
      return -1
    y = max(y, atlas.nodes[i].y)
    if y + h > atlas.h: 
      return -1
    spaceLeft -= atlas.nodes[i].w
    inc(i)
  return y # Yeah, Rect Fits

proc addSkylineNode(atlas: var MYAtlas, idx: int32, x,y,w,h: int16) =
  block: # Add New Node, not OOM checked
    var node: SKYNode
    node.x = x; node.y = y+h; node.w = w
    atlas.nodes.insert(node, idx)
  var i = idx+1 # New Iterator
  # Delete skyline segments that fall under the shadow of the new segment
  while i < len(atlas.nodes):
    let # Prev Node and i-th Node
      pnode = addr atlas.nodes[i-1]
      inode = addr atlas.nodes[i]
    if inode.x < pnode.x + pnode.w:
      let shrink =
        pnode.x - inode.x + pnode.w
      inode.x += shrink
      inode.w -= shrink
      if inode.w <= 0:
        atlas.nodes.delete(i)
        dec(i) # Reverse i-th
      else: break
    else: break
    inc(i) # Next Node
  # Merge same height skyline segments that are next to each other
  i = 0 # Reset Iterator
  while i < high(atlas.nodes):
    let # Next Node and i-th Node
      nnode = addr atlas.nodes[i+1]
      inode = addr atlas.nodes[i]
    if inode.y == nnode.y:
      inode.w += nnode.w
      atlas.nodes.delete(i+1)
      dec(i) # Reverse i-th
    inc(i) # Next Node

# ---- Use this for pack your rect ----
proc pack*(atlas: var MYAtlas, w, h: int16): tuple[x, y: int16] =
  var # Initial Best Fits
    bestIDX = -1'i32
    bestX = -1'i16
    bestY = -1'i16
  block: # Find Best Fit
    var # Temporal Vars
      bestH = atlas.h
      bestW = atlas.w
      i: int32 = 0
    while i < len(atlas.nodes):
      let y = atlas.rectFits(i, w, h)
      if y != -1: # Fits
        let node = addr atlas.nodes[i]
        if y + h < bestH or y + h == bestH and node.w < bestW:
          bestIDX = i
          bestW = node.w
          bestH = y + h
          bestX = node.x
          bestY = y
      inc(i) # Next Node
  if bestIDX != -1: # Can be packed
    addSkylineNode(atlas, bestIDX, bestX, bestY, w, h)
    # Return Packing Position
    result.x = bestX; result.y = bestY
  else: result.x = -1; result.y = -1 # Not Packed

[liquidev]

Is it capable of packing rects lazily (on demand)? If so, I might be able to use this algorithm for the texture packer in the future.

Don't open a PR yet, I'm currently working on removing global state and extracting all the OpenGL operations into a separate library and I'm afraid there may be conflicts when I actually get to merging it.

[mrgaturus]

Yes, it can. fontstash is a very lightweight atlas creator on-demand, basically i made a port of it on Nim but without fancy effects like blur, glow, shadows, different font sizes (if you need these, generate SDF fonts instead), etc. Ah, i forgot mention that you need create initial data for use that packing algorithm

# When Creating first time the atlas
atlas.w = some_width
atlas.nodes.add SKYNode(w: int16 atlas.w)
# When Expanding the atlas, only when width is expanded
atlas.nodes.add SKYNode(x: int16 prev_width, y: 0, w: int16 new_width - prev_width)

i used int16 for memory efficent, and i dont know if my atlas can exceed the max texture size of a modern gpu (32678*32768).

[liquidev]

Thanks for this algorithm, I'll try to replace the old packer with this one in the future.