|
1226
|
1 type
|
|
|
2 Rect = tuple
|
|
|
3 i: int
|
|
|
4 x, y, w, h: uint32
|
|
|
5
|
|
|
6 func between(a1, a2, b: uint32): bool =
|
|
|
7 a1 <= b and b <= a2
|
|
|
8
|
|
|
9 func overlap(a1, a2, b1, b2: uint32): bool =
|
|
|
10 return between(a1, a2, b1) or
|
|
|
11 between(a1, a2, b2) or
|
|
|
12 between(b1, b2, a1) or
|
|
|
13 between(b1, b2, a2)
|
|
|
14
|
|
|
15 # FYI: also serves as "overlaps"
|
|
|
16 func advanceIfOverlap(fix, newRect: Rect): (bool, uint32) =
|
|
|
17 let overlapping = overlap(fix.x, fix.x + fix.w - 1, newRect.x, newRect.x + newRect.w - 1) and
|
|
|
18 overlap(fix.y, fix.y + fix.h - 1, newRect.y, newRect.y + newRect.h - 1)
|
|
|
19 if overlapping: (true, fix.x + fix.w) # next free x coordinate to the right
|
|
|
20 else: (false, newRect.x) # current position is fine
|
|
|
21
|
|
|
22 proc find_insertion_position(alreadyPlaced: seq[Rect], area: tuple[i: int, w, h: uint32], maxDim: uint32): (bool, Rect) =
|
|
|
23 var newRect = (i: area.i, x: 0'u32, y: 0'u32, w: area.w, h: area.h)
|
|
|
24
|
|
|
25 while newRect.y + newRect.h <= maxDim:
|
|
|
26 var hasOverlap = false
|
|
|
27 var advanceX: uint32
|
|
|
28
|
|
|
29 for placed in alreadyPlaced:
|
|
|
30 (hasOverlap, advanceX) = placed.advanceIfOverlap(newRect)
|
|
|
31 if hasOverlap: # rects were overlapping and newRect needs to be shifted to the right
|
|
|
32 newRect.x = advanceX
|
|
|
33 break
|
|
|
34
|
|
|
35 if not hasOverlap: # found a collision free position
|
|
|
36 return (true, newRect)
|
|
|
37
|
|
|
38 if newRect.x + newRect.w >= maxDim: # move to next scanline
|
|
|
39 newRect.x = 0
|
|
|
40 newRect.y += 1
|
|
|
41
|
|
|
42 return (false, newRect)
|
|
|
43
|
|
|
44
|
|
1228
|
45 proc Pack*[T: PixelType](images: seq[Image[T]]): tuple[atlas: Image[T], coords: seq[tuple[x: uint32, y: uint32]]] =
|
|
1226
|
46 const MAX_ATLAS_SIZE = 4096'u32
|
|
|
47 var areas: seq[tuple[i: int, w, h: uint32]]
|
|
|
48
|
|
1228
|
49 for i in 0 ..< images.len:
|
|
|
50 areas.add (i, images[i].width, images[i].height)
|
|
1226
|
51
|
|
|
52 let areasBySize = areas.sortedByIt(-(it[1] * it[2]).int64)
|
|
|
53 var assignedAreas: seq[Rect]
|
|
|
54 var maxDim = 128'u32
|
|
|
55
|
|
|
56 for area in areasBySize:
|
|
|
57 var pos = find_insertion_position(assignedAreas, area, maxDim)
|
|
|
58 while not pos[0]: # this should actually never loop more than once, but weird things happen ¯\_(ツ)_/¯
|
|
|
59 maxDim = maxDim * 2
|
|
1228
|
60 assert maxDim <= MAX_ATLAS_SIZE, &"Atlas gets bigger than {MAX_ATLAS_SIZE}, cannot pack images"
|
|
1226
|
61 pos = find_insertion_position(assignedAreas, area, maxDim)
|
|
|
62
|
|
|
63 assignedAreas.add pos[1]
|
|
|
64
|
|
|
65 # check there are overlaps
|
|
|
66 for i in 0 ..< assignedAreas.len - 1:
|
|
|
67 for j in i + 1 ..< assignedAreas.len:
|
|
|
68 assert not assignedAreas[i].advanceIfOverlap(assignedAreas[j])[0], &"{assignedAreas[i]} and {assignedAreas[j]} overlap!"
|
|
|
69
|
|
1228
|
70 result.atlas = Image[T](width: maxDim, height: maxDim, data: newSeq[T](maxDim * maxDim))
|
|
|
71 result.coords.setLen(images.len)
|
|
1226
|
72 for rect in assignedAreas:
|
|
|
73 for y in 0 ..< rect.h:
|
|
|
74 for x in 0 ..< rect.w:
|
|
|
75 assert result.atlas[rect.x + x, rect.y + y] == 0, "Atlas texture packing encountered an overlap error"
|
|
1228
|
76 result.atlas[rect.x + x, rect.y + y] = images[rect.i][x, y]
|
|
1226
|
77 result.coords[rect.i] = (x: rect.x, y: rect.y)
|
