2d skyline bin packing algorithm

[ 자료1 ]에서 소개된 알고리즘을 javascript로 포팅하였습니다.

---

bin-packing 알고리즘은 굉장히 많이 쓴다. 

1d bin-packing의 대표적 예시가 메모리 어느 지점에 프로세스를 적재할 것인지 결정하는 알고리즘이

될 것이고, 2d bin-packing의 대표적 예시는 다양한 크기의 glyph를 atlas상에 배치 하거나,

여러 sprite 이미지를 큰 atlas이미지에 압축하는 것이 될 것이다.

                                                                               [그림1 출처]

[그림1] texture atlas 예시

[ 자료2 ] 에서와 같이 수많은 bin packing 알고리즘이 있지만, 개중에 하나인

skyline bottom-left bin packing algorithm를 소개하고자 한다.

 

 바로 본론으로 들어가서, skyline bottom-left는 빈공간을 추적하고 있는데, 이것들 node라고 한다.

이 빈공간은 아주 단순한 형태로 저장하고 있는데, [ x, y, width ]의 형태로 저장하고 있다.

x : 추적하는 빈공간 node의 왼쪽 시작 지점

y : 추적하는 빈공간 node의 위쪽 시작 지점

width : 추적하는 빈공간 node의 너비

 

height가 없어서 의아할 수 있는데, skyline bottome-left가 추적하는 "빈공간"을 알면 이해할 수 있다.

다음 그림을 보면,

[그림2] box를 3개 채운 시점의 node들

box를 채웠을때, 생성된 node의 아래쪽은 전부 해당 node가 추적중인 "빈공간"으로 간주하기

때문에, height정보가 필요없다.

항상 box들의 아래쪽 빈공간을 추적하기 때문에 box크기가 들쑥날쑥하면, 정렬시켜서 넣던가 하는

휴리스틱들을 추가로 적용해보아햐 한다.

[그림3] 추적되지 않는 공간 예시

이제 실제 packing 과정을 살펴보자.

var bestWidth = Number.MAX_SAFE_INTEGER;
var bestHeight = Number.MAX_SAFE_INTEGER;
var bestIndex = -1;
var region = [0, 0, width, height];

//1) 모든 노드들을 돌면서 들어갈 수 있는 곳을 탐색한다.
for (var i = 0; i < this._nodes.length; ++i) {
	//1-1) fit에서 width 만큼의 node중 가장 큰 봉우리를 찾는다
	var y = this.fit(i, width, height);

	//1-2) y가 minus가 아니라면 들어갈 수 있는 봉우리를 찾았다.
	if (y >= 0) {
		var node = this._nodes[i];

		//1-3) 봉우리중에 (하늘에서)가장 낮은 놈이 best다
		if ( y + height < bestHeight || (y + height == bestHeight && node[2] < bestWidth)) {
			bestHeight = y + height;
			bestIndex = i;
			bestWidth = node[2];
			region = [node[0], y, width, height];
		}
	}
}

모든 노들을 돌면서, fit과정을 거치는데, fit은 width만큼 단순히 node들을 방문하면서 (하늘에서)가장 높은

봉우리를 찾는다. width만큼 방문하기 때문에, 높아야 겹치지 않고 배치할 수 있기 때문이다.

[그림4] 새로운 박스의 fit

[그림4] 에서는 1번 node쪽 봉우리가 가장높으므로 해당 봉우리의 y값을 취한다.

그리고 그렇게 선택된 봉우리중에 가장 "낮은"값을 취하여 region( 박스가 배치될 영역 )을 갱신한다.

//2) 들어갈만한 적당한 곳이 없다
if (bestIndex == -1) {
	return undefined;
}

//3) 적당한 곳이 결정되어 node를 넣는다.
var node = [region[0], region[1] + height, width];
this._nodes.insert(bestIndex, node);

//4) 현재 노드가 들어감으로 기존노드와 겹침이 있을 수 있으므로 shrink작업을 한다
var i = bestIndex + 1;
while (i < this._nodes.length) {
	node = this._nodes[i];
	var prevNode = this._nodes[i - 1];

	//4-1) 이전 노드의 위치 + width 보다 작다 => 겹친다
	if (node[0] < prevNode[0] + prevNode[2]) {
		var shrink = prevNode[0] + prevNode[2] - node[0];

		var x = node[0];
		var y = node[1];
		var w = node[2];

		//4-2) shrink
		this._nodes[i][0] = x + shrink;
		this._nodes[i][1] = y;
		this._nodes[i][2] = w - shrink;

		//4-3) width가 minus라면 그 node는 삭제
		if (this._nodes[i][2] <= 0) {
			this._nodes.splice(i, 1);
			i -= 1;
		}
	} else {
		break; // 겹침이 없다면 괜춘괜춘
	}

	i += 1;
}

그리고 그렇게 배치가 되면 새로운 빈공간( 새로 배치된 박스의 아래부분 )이 생기므로 node를 추가한다.

새로운 node가 들어감으로, 기존 노드와의 영역다툼 해소를 위해 shrink를 해준다.

이때, shrink도중 음수가 나오게 되면 해당 node는 invalid로 제거한다.

 

//5) y위치가 같은 노드가 있다면 하나의 node로 만든다
this.merge();

//6) 사용량 추적용
this._used += width * height;

return region;

마지막으로, y위치( = 봉우리)가 같은 node가 있다면, merge하여 하나의 node로 만들어서 여러모로 계산도 줄이고,

최적화를 한다. 그리고 region을 반환하면 끝!

[그림5] 다양한 box를 채워넣은 모습

---

+ full source

Array.prototype.insert = function (index, item) {
  this.splice(index, 0, item);
};

class RectBox {
  constructor(x, y, width, height, color) {
    this._x = x;
    this._y = y;
    this._width = width;
    this._height = height;
    this._color = color;

    this.render = this.render.bind(this);
  }

  render(context) {
    context.fillStyle = this._color;
    context.fillRect(this._x, this._y, this._width, this._height);
  }
}

class Bin {
  constructor() {
    this._handle = null;

    this.addRect = this.addRect.bind(this);
    this.fill = this.fill.bind(this);
    this.draw = this.draw.bind(this);

    this.pack = this.pack.bind(this);
    this.fit = this.fit.bind(this);
    this.merge = this.merge.bind(this);

    var canvas = document.getElementById("myCanvas");
    var addButton = document.getElementById("addRect");
    addButton.onclick = this.addRect;

    this._canvasContext = canvas.getContext("2d");

    this._width = 512;
    this._height = 512;
    this._nodes = [[0, 0, this._width]];
    this._used = 0;

    this._rects = [];
  }

  fill() {
    var width = Math.floor(Math.random() * 100 + 30); // 30 ~ 130
    var height = Math.floor(Math.random() * 100 + 30); // 30 ~ 130

    var region = this.pack(width, height);
    if (undefined == region) {
      return;
    }

    var color = "#" + (((1 << 24) * Math.random()) | 0).toString(16);

    var newRect = new RectBox(
      region[0],
      region[1],
      region[2],
      region[3],
      color
    );
    this._rects.push(newRect);

    this.draw();
  }

  addRect() {
    this.fill();
  }

  draw() {
    for (var i = 0; i < this._rects.length; ++i) {
      this._rects[i].render(this._canvasContext);
    }
  }

  fit(index, width, height) {
    var node = this._nodes[index];
    var x = node[0];
    var y = node[1];
    var widthLeft = width;

    if (x + width > this._width) {
      return -1;
    }

    var i = index;
    while (widthLeft > 0) {
      node = this._nodes[i];
      y = Math.max(y, node[1]);
      if (y + height > this._height) {
        return -1;
      }

      widthLeft -= node[2];
      i += 1;
    }

    return y;
  }

  merge() {
    var i = 0;
    while (i < this._nodes.length - 1) {
      var node = this._nodes[i];
      var nextNode = this._nodes[i + 1];
      if (node[1] == nextNode[1]) {
        this._nodes[i][0] = node[0];
        this._nodes[i][1] = node[1];
        this._nodes[i][2] = node[2] + nextNode[2];
        this._nodes.splice(i + 1, 1);
      } else {
        i += 1;
      }
    }
  }

  pack(width, height) {
    var bestWidth = Number.MAX_SAFE_INTEGER;
    var bestHeight = Number.MAX_SAFE_INTEGER;
    var bestIndex = -1;
    var region = [0, 0, width, height];

    //1) 모든 노드들을 돌면서 들어갈 수 있는 곳을 탐색한다.
    for (var i = 0; i < this._nodes.length; ++i) {
      //1-1) fit에서 width 만큼의 node중 가장 큰 봉우리를 찾는다
      var y = this.fit(i, width, height);

      //1-2) y가 minus가 아니라면 들어갈 수 있는 봉우리를 찾았다.
      if (y >= 0) {
        var node = this._nodes[i];

        //1-3) 봉우리중에 (하늘에서)가장 낮은 놈이 best다
        if (
          y + height < bestHeight ||
          (y + height == bestHeight && node[2] < bestWidth)
        ) {
          bestHeight = y + height;
          bestIndex = i;
          bestWidth = node[2];
          region = [node[0], y, width, height];
        }
      }
    }

    //2) 들어갈만한 적당한 곳이 없다
    if (bestIndex == -1) {
      return undefined;
    }

    //3) 적당한 곳이 결정되어 node를 넣는다.
    var node = [region[0], region[1] + height, width];
    this._nodes.insert(bestIndex, node);

    //4) 현재 노드가 들어감으로 기존노드와 겹침이 있을 수 있으므로 shrink작업을 한다
    var i = bestIndex + 1;
    while (i < this._nodes.length) {
      node = this._nodes[i];
      var prevNode = this._nodes[i - 1];

      //4-1) 이전 노드의 위치 + width 보다 작다 => 겹친다
      if (node[0] < prevNode[0] + prevNode[2]) {
        var shrink = prevNode[0] + prevNode[2] - node[0];

        var x = node[0];
        var y = node[1];
        var w = node[2];

        //4-2) shrink
        this._nodes[i][0] = x + shrink;
        this._nodes[i][1] = y;
        this._nodes[i][2] = w - shrink;

        //4-3) width가 minus라면 그 node는 삭제
        if (this._nodes[i][2] <= 0) {
          this._nodes.splice(i, 1);
          i -= 1;
        }
      } else {
        break; // 겹침이 없다면 괜춘괜춘
      }

      i += 1;
    }

    //5) y위치가 같은 노드가 있다면 하나의 node로 만든다
    this.merge();

    //6) 사용량 추적용
    this._used += width * height;

    return region;
  }
}

var s_bin = null;
window.onload = () => {
  s_bin = new Bin();
};