Mercurial > games > semicongine

annotate semicongine/algorithms.nim @ 1138:02e1d2658ff5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
did: more renaming
author sam <sam@basx.dev>
date Tue, 04 Jun 2024 22:08:48 +0700
parents a4aa9f374d44
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
1 import std/algorithm
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
2
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
3 import ./core
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
4
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
5 type
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
6 Rect = tuple
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
7 i: int
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
8 x, y, w, h: uint32
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
9
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
10 func between(a1, a2, b: uint32): bool =
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
11 a1 <= b and b <= a2
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
12
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
13 func overlap(a1, a2, b1, b2: uint32): bool =
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
14 return between(a1, a2, b1) or
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
15 between(a1, a2, b2) or
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
16 between(b1, b2, a1) or
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
17 between(b1, b2, a2)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
18
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
19 # FYI: also serves as "overlaps"
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
20 func advanceIfOverlap(fix, newRect: Rect): (bool, uint32) =
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
21 let overlapping = overlap(fix.x, fix.x + fix.w - 1, newRect.x, newRect.x + newRect.w - 1) and
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
22 overlap(fix.y, fix.y + fix.h - 1, newRect.y, newRect.y + newRect.h - 1)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
23 if overlapping: (true, fix.x + fix.w) # next free x coordinate to the right
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
24 else: (false, newRect.x) # current position is fine
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
25
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
26 proc find_insertion_position(alreadyPlaced: seq[Rect], area: tuple[i: int, w, h: uint32], maxDim: uint32): (bool, Rect) =
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
27 var newRect = (i: area.i, x: 0'u32, y: 0'u32, w: area.w, h: area.h)
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
28
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
29 while newRect.y + newRect.h <= maxDim:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
30 var hasOverlap = false
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
31 var advanceX: uint32
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
32
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
33 for placed in alreadyPlaced:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
34 (hasOverlap, advanceX) = placed.advanceIfOverlap(newRect)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
35 if hasOverlap: # rects were overlapping and newRect needs to be shifted to the right
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
36 newRect.x = advanceX
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
37 break
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
38
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
39 if not hasOverlap: # found a collision free position
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
40 return (true, newRect)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
41
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
42 if newRect.x + newRect.w >= maxDim: # move to next scanline
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
43 newRect.x = 0
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
44 newRect.y += 1
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
45
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
46 return (false, newRect)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
47
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
48
1138
02e1d2658ff5 did: more renaming
sam <sam@basx.dev>
parents: 1137
diff changeset
49 proc Pack*[T: Pixel](images: seq[Image[T]]): tuple[atlas: Image[T], coords: seq[tuple[x: uint32, y: uint32]]] =
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
50 const MAX_ATLAS_SIZE = 4096'u32
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
51 var areas: seq[tuple[i: int, w, h: uint32]]
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
52
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
53 for i in 0 ..< images.len:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
54 areas.add (i, images[i].width, images[i].height)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
55
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
56 let areasBySize = areas.sortedByIt(-(it[1] * it[2]).int64)
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
57 var assignedAreas: seq[Rect]
959
c104dbf5bbb8 did: adjust integer sizes to match vulkan API (more) directly
sam <sam@basx.dev>
parents: 418
diff changeset
58 var maxDim = 128'u32
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
59
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
60 for area in areasBySize:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
61 var pos = find_insertion_position(assignedAreas, area, maxDim)
418
009d93d69170 add: correct version of text-alignment, and a few improvments
Sam <sam@basx.dev>
parents: 414
diff changeset
62 while not pos[0]: # this should actually never loop more than once, but weird things happen ¯\_(ツ)_/¯
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
63 maxDim = maxDim * 2
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
64 assert maxDim <= MAX_ATLAS_SIZE, &"Atlas gets bigger than {MAX_ATLAS_SIZE}, cannot pack images"
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
65 pos = find_insertion_position(assignedAreas, area, maxDim)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
66
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
67 assignedAreas.add pos[1]
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
68
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
69 # check there are overlaps
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
70 for i in 0 ..< assignedAreas.len - 1:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
71 for j in i + 1 ..< assignedAreas.len:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
72 assert not assignedAreas[i].advanceIfOverlap(assignedAreas[j])[0], &"{assignedAreas[i]} and {assignedAreas[j]} overlap!"
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
73
1137
a4aa9f374d44 did: more renaming
sam <sam@basx.dev>
parents: 959
diff changeset
74 result.atlas = NewImage[T](maxDim, maxDim)
414
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
75 result.coords.setLen(images.len)
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
76 for rect in assignedAreas:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
77 for y in 0 ..< rect.h:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
78 for x in 0 ..< rect.w:
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
79 assert result.atlas[rect.x + x, rect.y + y] == 0, "Atlas texture packing encountered an overlap error"
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
80 result.atlas[rect.x + x, rect.y + y] = images[rect.i][x, y]
0deefe1c8af6 add: 2d-packing algorithm for texture-atlas generation
Sam <sam@basx.dev>
parents:
diff changeset
81 result.coords[rect.i] = (x: rect.x, y: rect.y)