1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
// SPDX-License-Identifier: Unlicense OR MIT
package gpu
import (
"image"
)
// packer packs a set of many smaller rectangles into
// much fewer larger atlases.
type packer struct {
maxDims image.Point
spaces []image.Rectangle
sizes []image.Point
pos image.Point
}
type placement struct {
Idx int
Pos image.Point
}
// add adds the given rectangle to the atlases and
// return the allocated position.
func (p *packer) add(s image.Point) (placement, bool) {
if place, ok := p.tryAdd(s); ok {
return place, true
}
p.newPage()
return p.tryAdd(s)
}
func (p *packer) clear() {
p.sizes = p.sizes[:0]
p.spaces = p.spaces[:0]
}
func (p *packer) newPage() {
p.pos = image.Point{}
p.sizes = append(p.sizes, image.Point{})
p.spaces = p.spaces[:0]
p.spaces = append(p.spaces, image.Rectangle{
Max: image.Point{X: 1e6, Y: 1e6},
})
}
func (p *packer) tryAdd(s image.Point) (placement, bool) {
var (
bestIdx = -1
bestSpace image.Rectangle
bestSize = p.maxDims
)
// Go backwards to prioritize smaller spaces.
for i, space := range p.spaces {
rightSpace := space.Dx() - s.X
bottomSpace := space.Dy() - s.Y
if rightSpace < 0 || bottomSpace < 0 {
continue
}
idx := len(p.sizes) - 1
size := p.sizes[idx]
if x := space.Min.X + s.X; x > size.X {
if x > p.maxDims.X {
continue
}
size.X = x
}
if y := space.Min.Y + s.Y; y > size.Y {
if y > p.maxDims.Y {
continue
}
size.Y = y
}
if size.X*size.Y < bestSize.X*bestSize.Y {
bestIdx = i
bestSpace = space
bestSize = size
}
}
if bestIdx == -1 {
return placement{}, false
}
// Remove space.
p.spaces[bestIdx] = p.spaces[len(p.spaces)-1]
p.spaces = p.spaces[:len(p.spaces)-1]
// Put s in the top left corner and add the (at most)
// two smaller spaces.
pos := bestSpace.Min
if rem := bestSpace.Dy() - s.Y; rem > 0 {
p.spaces = append(p.spaces, image.Rectangle{
Min: image.Point{X: pos.X, Y: pos.Y + s.Y},
Max: image.Point{X: bestSpace.Max.X, Y: bestSpace.Max.Y},
})
}
if rem := bestSpace.Dx() - s.X; rem > 0 {
p.spaces = append(p.spaces, image.Rectangle{
Min: image.Point{X: pos.X + s.X, Y: pos.Y},
Max: image.Point{X: bestSpace.Max.X, Y: pos.Y + s.Y},
})
}
idx := len(p.sizes) - 1
p.sizes[idx] = bestSize
return placement{Idx: idx, Pos: pos}, true
}
|
