Mercurial > games > semicongine
annotate semiconginev2/contrib/algorithms/texture_packing.nim @ 1243:7e55fde39ca8
did: prepare for gltf importer and cleanup old engine code
| author | sam <sam@basx.dev> |
|---|---|
| date | Mon, 22 Jul 2024 17:49:48 +0700 |
| parents | 841e12f33c47 |
| children | c15770761865 |
| rev | line source |
|---|---|
| 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: | |
|
1234
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
75 when T is Gray: |
|
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
76 assert result.atlas[rect.x + x, rect.y + y] == [0'u8], "Atlas texture packing encountered an overlap error" |
|
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
77 elif T is RGBA: |
|
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
78 assert result.atlas[rect.x + x, rect.y + y] == [0'u8, 0'u8, 0'u8, 0'u8], "Atlas texture packing encountered an overlap error" |
|
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
79 else: |
|
841e12f33c47
add: text & font rendering, not tested yet
sam <sam@basx.dev>
parents:
1228
diff
changeset
|
80 {.error: "Unsupported type for texture packing".} |
| 1228 | 81 result.atlas[rect.x + x, rect.y + y] = images[rect.i][x, y] |
| 1226 | 82 result.coords[rect.i] = (x: rect.x, y: rect.y) |