pack.go raw

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