viewport culling과 spatial index

node가 많아지면 화면 밖 node까지 모두 그리고 모두 hit test하는 방식은 금방 한계가 옵니다.

viewport culling을 먼저 구현하는 코드

spatial index 전에 world bounds와 viewport intersection만으로도 많은 node를 줄일 수 있습니다.

function intersects(a, b) {
  return (
    a.x < b.x + b.width &&
    a.x + a.width > b.x &&
    a.y < b.y + b.height &&
    a.y + a.height > b.y
  );
}

function visibleNodes(nodes, camera, viewportSize) {
  const viewportWorld = screenRectToWorld(
    { x: 0, y: 0, width: viewportSize.width, height: viewportSize.height },
    camera
  );

  return nodes.filter((node) => {
    if (node.visible === false) return false;
    return intersects(node.worldBounds, viewportWorld);
  });
}

screenRectToWorld도 camera inverse와 같은 문제입니다.

function screenRectToWorld(rect, camera) {
  const leftTop = {
    x: rect.x / camera.zoom + camera.x,
    y: rect.y / camera.zoom + camera.y
  };
  const rightBottom = {
    x: (rect.x + rect.width) / camera.zoom + camera.x,
    y: (rect.y + rect.height) / camera.zoom + camera.y
  };

  return {
    x: leftTop.x,
    y: leftTop.y,
    width: rightBottom.x - leftTop.x,
    height: rightBottom.y - leftTop.y
  };
}

render 후보와 hit test 후보가 같은 viewport world bounds를 쓰면 “보이지 않는 node가 선택되는” 버그를 줄일 수 있습니다.

먼저 bounds cache를 만든다

node local bounds
world matrix
world AABB
viewport intersection

이 bounds cache는 culling과 hit test 후보 추리기에 함께 쓰입니다.

index는 나중에 붙인다

처음부터 quadtree나 R-tree를 넣을 필요는 없습니다. 전체 순회가 느려진다는 측정이 나온 뒤에 붙이는 것이 더 안전합니다.

오늘의 핵심

culling은 GPU 최적화이면서 CPU 자료구조 문제입니다. draw 후보와 hit 후보를 같은 정책으로 좁혀야 합니다.